LLVM IR和Go

在本文中，我们将研究如何构建Go程序，例如编译器或静态分析器，该程序使用LLVM IR汇编语言与LLVM编译框架进行交互。

TL； DR，我们编写了一个库，用于在纯Go上与LLVM IR进行交互，请参见代码链接和示例项目。

LLVM IR的简单示例

（熟悉LLVM IR的人可以跳到下一部分）。

LLVM IR是LLVM编译框架使用的低级中间表示形式。 您可以将LLVM IR视为具有无限数量的本地寄存器的独立于平台的汇编器。

在设计编译器时，将源语言编译为中间表示形式（IR，中间表示形式）而不是将其编译为目标体系结构（例如x86）具有巨大优势。


由于许多优化技术是通用的（例如，删除未使用的代码，分配常量），因此这些优化过程可以直接在IR级别执行，并可供所有目标平台使用。


因此，编译器通常由三部分组成：前端，中间地带和后端，它们各自执行自己的任务，接受输入和/或提供IR输出。

• 前端：在IR中编译源语言
• Middleland：优化IR
• 后端：将IR编译为机器代码

LLVM IR汇编程序示例程序

为了了解LLVM IR汇编器的外观，请考虑以下程序。

int f(int a, int b) { return a + 2*b; } int main() { return f(10, 20); } 

我们使用Clang并将上述C代码编译为LLVM IR汇编程序。

 define i32 @f(i32 %a, i32 %b) { ; <label>:0 %1 = mul i32 2, %b %2 = add i32 %a, %1 ret i32 %2 } define i32 @main() { ; <label>:0 %1 = call i32 @f(i32 10, i32 20) ret i32 %1 } 

查看上面的LLVM IR汇编器代码，我们可以注意到一些值得注意的LLVM IR功能，即：

LLVM IR是静态类型的（即i32类型与32位整数相交）。

局部变量在函数中具有作用域（即main中的％1与@f中的％1不同）。

在每个函数中，未命名的（临时寄存器）以升序接收本地标识符（例如，％1，％2）。 每个功能可以使用无限数量的寄存器（不限于32个通用寄存器）。 全局标识符（例如@f）和本地标识符（例如％a，％1）通过前缀（分别为@和％）来区分。

大多数命令可以完成您期望的操作，因此mul可以执行乘法，加法运算等。

注释以汇编语言的惯例开头；

LLMV IR组装器结构

LLVM IR程序集文件的内容是一个模块。 该模块包含高级声明，例如全局变量和函数。

函数声明不包含基本块，函数定义包含一个或多个基本块（即函数主体）。

LLVM IR模块的更详细示例如下。 包括全局变量@foo的定义和包含三个基本块（％入口，％block_1和％block_2）的@f函数的定义。

 ;  ,  32-  21 @foo = global i32 21 ; f  42,   cond ,  0    define i32 @f(i1 %cond) { ;       ,     ;      entry: ;     br    block_1,  %cond ; ,   block_2   . br i1 %cond, label %block_1, label %block_2 ;     ,    ,     block_1: %tmp = load i32, i32* @foo %result = mul i32 %tmp, 2 ret i32 %result ;     ,     ,     block_2: ret i32 0 } 

基本单位

基本单元是不是过渡命令（终止命令）的命令序列。 基本单元的关键思想是，如果执行了基本单元的一个命令，则将执行基本单元的所有其他命令。 这简化了执行流程的分析。

团队

不是跳转命令的命令通常执行计算或内存访问（例如，添加，加载），但不会更改程序的控制流。

终止团队

终止命令位于每个基本单元的末尾，并确定将在基本单元的末尾进行转换的位置。 例如，终止ret命令返回调用函数的控制流，并且br执行有条件或无条件的转换。

SSA表格

LLVM IR的一个非常重要的特性是它以SSA形式（静态单一分配）编写，这实际上意味着每个寄存器仅分配一次。 此属性简化了数据流的静态分析。

要处理在原始源代码中多次分配的变量，在LLVM IR中使用phi命令。 phi命令实际上从一组输入值中返回一个值，具体取决于到达此命令的执行路径。 因此，每个输入值都与前一个输入块关联。

例如，请考虑以下LLVM IR功能：

 define i32 @f(i32 %a) { ; <label>:0 switch i32 %a, label %default [ i32 42, label %case1 ] case1: %x.1 = mul i32 %a, 2 br label %ret default: %x.2 = mul i32 %a, 3 br label %ret ret: %x.0 = phi i32 [ %x.2, %default ], [ %x.1, %case1 ] ret i32 %x.0 } 

上面的示例中的phi命令（有时也称为phi节点）使用一组可能的输入值模拟各种分配，每个输入值对应执行线程中的每个可能路径，从而导致变量分配。 例如，数据流中的相应路径之一如下：



通常，在开发将源代码转换为LLVM IR的编译器时，所有本地源代码变量都可以转换为SSA形式，但使用其地址的变量除外。

为了简化LLVM前端的实现，建议将源语言中的局部变量建模为在内存中分配的变量（使用alloca），将对局部变量的分配模拟为对存储器的写入，并使用局部变量作为对内存的读取。 原因是将源语言直接转换为SSA形式的LLVM IR可能是一项艰巨的任务。 只要内存访问遵循某些模式，我们就可以依靠mem2reg优化过程作为LLVM的一部分将内存中分配的局部变量转换为SSA形式的寄存器（必要时使用phi节点）。

纯Go上的LLVM IR库

Go中有两个用于处理LLVM IR的主要库：

https://godoc.org/llvm.org/llvm/bindings/go/llvm：Go语言的官方LLVM绑定。
github.com/llir/llvm ：一个干净的Go库，用于与LLVM IR交互。

用于Go语言的官方LLVM绑定使用Cgo提供对LLVM编译器框架的丰富而强大的API的访问，而llir / llvm项目完全是用Go编写的，并使用LLVM IR与LLVM框架进行交互。

本文重点介绍llir / llvm，但可以概括为与其他库一起使用。

为什么要写一个新的图书馆？

开发用于与LLVM IR交互的简洁的Go库的主要动机是使基于LLVM IR编译框架的编写编译器和静态分析工具更加有趣。 这也受到以下事实的影响：基于Go的官方LLVM绑定的项目的编译时间可能很长（由于TinyGo的作者@aykevl，与LLVM 4的标准版本相反，由于动态链接，现在可以加快编译速度）。


另一个主要动机是尝试从头开始开发Go API。 Go和llir / llvm的LLVM绑定API之间的主要区别在于LLVM值的建模方式。 在Go的LLVM绑定器中，LLVM值被建模为一种具体的结构类型，实质上，它包含了所有可能的LLVM值的所有可能方法。 我使用此API的亲身经历表明，很难知道允许哪个方法子集调用给定值。 例如，要获取指令操作码，请调用InstructionOpcode方法，该方法很直观。 但是，如果改为调用Opcode方法（该方法旨在获取常量表达式的操作码），则会收到运行时错误：“类型不兼容的cast（）参数！” （将参数转换为不兼容的类型）。

llir / llvm库旨在在编译时检查类型，并确保它们与Go类型系统一起正确使用。 llir / llvm中的LLVM值被建模为接口类型。 此方法仅使所有值共享的最小方法集可用，并且如果要访问特定方法或字段，请使用类型切换（如下例所示）。

使用范例

现在让我们看一些特定用途的例子。 让我们拥有一个库，但是LLVM IR应该怎么做？

首先，我们可能要解析由其他工具（例如Clang和优化器LLVM opt）生成的LLVM IR（请参见下面的示例输入）。

其次，我们可能要处理LLVM IR并对其进行分析，或者进行自己的优化遍历，或者实现解释器或JIT编译器（请参见下面的分析示例）。

第三，我们可能想生成一个LLVM IR，它将作为其他工具的输入。 如果我们正在为新的编程语言开发前端，那么可以选择这种方法（请参见下面的示例输出代码）。

样本输入代码-LLVM IR解析

 //       LLVM IR,    //     package main import ( "fmt" "github.com/llir/llvm/asm" ) func main() { //    LLVM IR. m, err := asm.ParseFile("foo.ll") if err != nil { panic(err) } // ,    LLVM IR. // Print LLVM IR module. fmt.Println(m) } 

分析示例-处理LLVM IR

 //      LLVM IR     //  Graphviz DOT package main import ( "bytes" "fmt" "io/ioutil" "github.com/llir/llvm/asm" "github.com/llir/llvm/ir" ) func main() { //    LLVM IR. m, err := asm.ParseFile("foo.ll") if err != nil { panic(err) } //    . callgraph := genCallgraph(m) //      Graphviz DOT. if err := ioutil.WriteFile("callgraph.dot", callgraph, 0644); err != nil { panic(err) } } // genCallgraph      Graphviz DOT    LLVM IR func genCallgraph(m *ir.Module) []byte { buf := &bytes.Buffer{} buf.WriteString("digraph {\n") //      for _, f := range m.Funcs { //   caller := f.Ident() fmt.Fprintf(buf, "\t%q\n", caller) //       for _, block := range f.Blocks { //   ,       . for _, inst := range block.Insts { //  .   call. switch inst := inst.(type) { case *ir.InstCall: callee := inst.Callee.Ident() //        . fmt.Fprintf(buf, "\t%q -> %q\n", caller, callee) } } //     switch term := block.Term.(type) { case *ir.TermRet: //  - _ = term } } } buf.WriteString("}") return buf.Bytes() } 

样本输出代码-LLVM IR生成

 //     LLVM IR,    C, //    . // // int abs(int x); // // int seed = 0; // // // ref: https://en.wikipedia.org/wiki/Linear_congruential_generator // // a = 0x15A4E35 // // c = 1 // int rand(void) { // seed = seed*0x15A4E35 + 1; // return abs(seed); // } package main import ( "fmt" "github.com/llir/llvm/ir" "github.com/llir/llvm/ir/constant" "github.com/llir/llvm/ir/types" ) func main() { //      i32 := types.I32 zero := constant.NewInt(i32, 0) a := constant.NewInt(i32, 0x15A4E35) //  PRNG. c := constant.NewInt(i32, 1) //  PRNG. //    LLVM IR. m := ir.NewModule() //         . // // int abs(int x); abs := m.NewFunc("abs", i32, ir.NewParam("x", i32)) //         . // // int seed = 0; seed := m.NewGlobalDef("seed", zero) //        . // // int rand(void) { ... } rand := m.NewFunc("rand", i32) //           `rand`. entry := rand.NewBlock("") //         . tmp1 := entry.NewLoad(seed) tmp2 := entry.NewMul(tmp1, a) tmp3 := entry.NewAdd(tmp2, c) entry.NewStore(tmp3, seed) tmp4 := entry.NewCall(abs, tmp3) entry.NewRet(tmp4) //   LLVM IR  . fmt.Println(m) } 

结论

llir / llvm的开发和实施是由一群贡献者进行的，他们不仅编写代码，而且还领导讨论，配对编程会议，调试，剖析并显示了学习过程中的好奇心。

llir / llvm项目最困难的部分之一是为LLVM IR构建EBNF语法，涵盖LLVM 7.0之前的整个LLVM IR语言。 这里的困难不在于过程本身，而在于没有覆盖所有语言的正式发布语法。 一些开源社区试图为LLVM汇编程序定义正式的语法，但据我们所知，它们仅覆盖语言的子集。

语法LLVM IR为有趣的项目铺平了道路。 例如，语法有效的LLVM IR汇编程序的生成可用于使用LLVM IR的各种工具和库，GoSmith中使用了类似的方法。 这可用于以其他语言实现的LLVM项目的交叉验证，以及检查漏洞和实现错误。

未来是美好的，快乐的黑客！

参考文献

1.最初的LLVM项目的作者克里斯·拉特纳（Chris Lattner）在“开源应用程序的体系结构”一书中写了一篇有关LLVM的非常好的文章。

2. 《使用LLVM实施语言》教程 （通常也称为《万花筒语言指南》）详细描述了如何实施以LLVM IR编译的简单编程语言。 本文介绍了编写前端的所有主要阶段，包括词法分析器，解析器和代码生成。

3.对于那些有兴趣从输入语言编写到LLVM IR的编译器的人，推荐本书“将高级构造映射到LLVM IR ”。

LLVM详细介绍了很多，其中介绍了重要的LLVM IR概念，介绍了LLVM C ++ API，并介绍了一些非常有用的LLVM优化文章。

LLVM的官方Go绑定适用于许多项目，它们表示LLVM C API，功能强大且稳定。

Go中的LLVM简介是该帖子的一个很好补充。