LLVM IR 笔记

贡献者： addis

预备知识　LLVM 笔记

　　 LLVM IR (Intermediate Representation) 是 LLVM 的一个 portable 的中间语言。使用 LLVM 的编译器会先把高级语言编译成 IR，然后再做进一步优化。LLVM IR 的语法和汇编语言类似。

　　一个完整的例子，可以编译运行

代码 1：test.ll

; Declare the main function
define i32 @main() {
  entry:
    ; Allocate stack space for a single 32-bit integer in the stack memory
    ; `var` is a pointer
    %var = alloca i32

    ; Store the value 42 into the variable on memory stack
    ; * means pointer
    store i32 42, i32* %var

    ; Load the value of the variable into a [virtual] register
    %val = load i32, i32* %var

    ; Return the value of the register
    ret i32 %val
}

　　编译：

llvm-as test.ll -o test.bc # 编译成 bitcode
clang test.bc -o test # 编译成可执行文件
./test # 执行
echo $? # 查看返回值（exit status）

Static Single Assignment (SSA)：每个变量只能赋值一次！
在使用一个变量之前，通常需要把它加载到 register 中，而不是直接 dereference。
例如算数以及 return 都需要先加载到 register 中.

　　以下是一个函数例子：计算两个整数相加。

define i32 @add(i32 %a, i32 %b) {
  entry:
    %sum = add i32 %a, %b
    ret i32 %sum
}

　　调用该函数

define i32 @main() {
  entry:
    ; set a=10, b=20 in registers
    %a = add i32 0, 10
    %b = add i32 0, 20
    %sum = call i32 @add(i32 %a, i32 %b)
    ret i32 %sum
}

　　其中对 a, b 的赋值也可以用

%a = or i32 10, 0
%b = or i32 20, 0

　　第三种方法是从内存 stack 中加载到 register

define i32 @main() {
  entry:
    %a = alloca i32
    %b = alloca i32
    store i32 10, i32* %a
    store i32 20, i32* %b
    %a_val = load i32, i32* %a
    %b_val = load i32, i32* %b
    %sum = call i32 @add(i32 %a_val, i32 %b_val)
    ret i32 %sum
}

另一些例子

　　栈和堆上的矩阵：

define i64 @my_func(i64 signext %"my_var") #0 {
  top:
    ; Allocate an array of 10 doubles on the stack
    %array = alloca [10 x double], align 8

    ; Declare the malloc function
    declare i8* @malloc(i64)

    ; Allocate an array of 10 doubles on the heap
    ; Calculate the size needed: 10 doubles * 8 bytes per double
    %size = mul i64 10, 8
    %malloc_result = call i8* @malloc(i64 %size)
    %array = bitcast i8* %malloc_result to double*

    ; Store a value into the array
    %value = fadd double 0.0, 3.14  ; Example value to store
    ; Get pointer to the 3rd element
    %ptr = getelementptr inbounds [10 x double], \
      [10 x double]* %array, i64 0, i64 2
    store double %value, double* %ptr, align 8

    ; Load a value from the array
    %loaded_value = load double, double* %ptr, align 8
}

1. 常识

合法的本地变量（寄存器）名字如 %x, %var1, %my_var, %func.entry, %tmp-1，也可以用数字开头如 %0, %1a，甚至用字符串 %"my var", %"var@1", %"func.entry#1"。
函数返回用 ret 不是 return
@名字 用于声明全局函数或变量
signext: 指定入参实参应该 sign-extended 到 64 位。一些机器上，如惨可能通过小于 64 位的寄存器上
函数定义的第一行中，#0 是函数属性组。#0 代表一系列在模块中其他地方定义的属性，例如优化提示或调用规范。
标签名: 定义用于跳转的标签。
缩进不重要
名字（变量、函数、label）里面可以包含英文句号 “.”
变量名以 % 开始
注释用 ;
对本地变量，不存在类似 C 语言的 const。
getelementptr（GEP）的格式为 指针 = getelementptr 基类型, 基类型* 指针, 指标类型1 ind1, 指标类型2 ind2 ...。在取数组第 3 个元素时，最后是 i64 0, i64 2，第一个从 指针 中获取数组，第二个从 array 中获取获取第 3 个元素。

2. 判断

br i1 条件, label %真标签, label %假标签 用于判断，i1 是一个 1bit 整数，也就是 bool。如果条件为真，就跳到标签 真标签，否则跳到 假标签
br label %标签 相当于 goto
例如，%cond = icmp eq i32 %x, %y, 然后 br i1 %cond, label %equals, label %notequals
label 的定义：标签名:
判断 $x < y$：icmp slt i32 %x, %y（signed less than），或者 sgt（signed greater than）
ult, ugt（unsigned less/greater than）
与：%and_result = and i1 %a, %b
或：%result = or i1 %cond1, %cond2
phi 函数用于判断变量来自哪个分支

int foo(int x) {
    int y;
    if (x > 0) {
        y = 10;
    } else {
        y = 20;
    }
    return y;
}

define i32 @foo(i32 %x) {
  entry:
    %cmp = icmp sgt i32 %x, 0  ; Compare x > 0
    br i1 %cmp, label %if.then, label %if.else

  if.then:
    br label %merge

  if.else:
    br label %merge

  merge:
    ; Select value based on predecessor
    %y = phi i32 [ 10, %if.then ], [ 20, %if.else ]
    ret i32 %y
}

3. 循环

　　一个什么都不做的空循环，注意这里循环变量 %i 之所以能反复写入而不违反 SSA 是因为使用了 alloca 分配了栈上变量。

define void @countUpTo(i32 %limit) {
  entry:
    ; Initialize loop variable
    %i = alloca i32
    store i32 0, i32* %i

    ; Jump to the loop condition check
    br label %loop.cond

  loop.cond:
    ; Load loop variable
    %i.val = load i32, i32* %i

    ; Check if the loop variable is less than the limit
    %cond = icmp slt i32 %i.val, %limit
    br i1 %cond, label %loop.body, label %loop.end

  loop.body:
    ; Increment the loop variable
    %next.val = add i32 %i.val, 1
    store i32 %next.val, i32* %i

    ; Jump back to the loop condition
    br label %loop.cond

  loop.end:
    ; Exit point of the loop
    ret void
}

　　生成数组 [1,2,3,4]

define void @assignArray() {
  entry:
    ; Allocate an array of 4 integers on the stack
    %array = alloca [4 x i32]

    ; Loop counter
    %i = alloca i32
    store i32 0, i32* %i

    ; Jump to the loop condition
    br label %loop.cond

  loop.cond:
    ; Load the loop counter
    %i.val = load i32, i32* %i

    ; Check if the loop counter is less than 4
    %cond = icmp slt i32 %i.val, 4
    br i1 %cond, label %loop.body, label %loop.end

  loop.body:
    ; Calculate the address of the current array element
    %addr = getelementptr [4 x i32], [4 x i32]* %array, i32 0, i32 %i.val

    ; Assign the corresponding value (i+1) to the array element
    %val = add i32 %i.val, 1
    store i32 %val, i32* %addr

    ; Increment the loop counter
    %next.i = add i32 %i.val, 1
    store i32 %next.i, i32* %i

    ; Jump back to the loop condition
    br label %loop.cond

  loop.end:
    ; Exit point of the loop
    ret void
}

　　要在 heap 中分配内存，取决于所在系统，一般调用 C 语言的 malloc

declare i8* @malloc(i32) ; 声明 malloc

define i32* @createArray() {
  entry:
    ; Calculate the size of the array (4 integers)
    %size = mul i32 4, 4 ; size for 4 integers (assuming i32 is 4 bytes)

    ; Call malloc to allocate memory on the heap
    %arrayPtr = call i8* @malloc(i32 %size)

    ; Cast the returned i8* (generic pointer) to i32* (pointer to integers)
    %typedArrayPtr = bitcast i8* %arrayPtr to i32*

    ; Return the pointer to the allocated memory
    ret i32* %typedArrayPtr
}

　　另一个循环的例子，没有用栈变量，而是用 phi 函数解决多次写入的问题：

int sum(int n) {
    int result = 0;
    for (int i = 0; i < n; i++) {
        result += i;
        if (i % 2 == 0) {
            result += 1;  // Modify result again
        }
    }
    return result;
}

define i32 @sum(i32 %n) {
  entry:
    br label %loop

  loop:
    ; i = 0 (init) or i = i.next (update)
    %i = phi i32 [ 0, %entry ], [ %i.next, %loop.end ]
    ; result = 0 (init) or result = result.next (update)
    %result = phi i32 [ 0, %entry ], [ %result.next, %loop.end ]
    %i.next = add i32 %i, 1  ; i.next = i + 1
    %result.tmp = add i32 %result, %i  ; result.tmp = result + i
    %is_odd = and i32 %i, 1  ; Check if i is even (i % 2 == 0)
    %cmp_even = icmp eq i32 %is_odd, 0  ; Compare is_odd == 0
    br i1 %cmp_even, label %if.even, label %loop.end

  if.even:
    %result.even = add i32 %result.tmp, 1  ; result.even = result.tmp + 1
    br label %loop.end

  loop.end:
    ; Select result.next based on control flow
    %result.next = phi i32 [ %result.tmp, %loop ], [ %result.even, %if.even ]
    %cmp = icmp slt i32 %i.next, %n  ; Compare i.next < n
    br i1 %cmp, label %loop, label %exit

  exit:
    ret i32 %result
}

4. 调库

调用 C 标准库的 printf

; Declare the printf function
declare i32 @printf(i8*, ...)

; Define the format string
@.str = private unnamed_addr constant [14 x i8] c"Hello, World!\00", align 1

define i32 @main() {
entry:
  ; Get a pointer to the format string
  %str = getelementptr inbounds [14 x i8], [14 x i8]* @.str, i64 0, i64 0

  ; Call printf
  call i32 (i8*, ...) @printf(i8* %str)

  ; Return 0
  ret i32 0
}

@变量名 代表全局变量，.str 没什么特殊的，也可以用 @my_string
private 说明仅限于当前 llvm 模块（module）使用
constant 不允许修改，只有全局变量有该关键字
c"..." 表示字符串常量
\00 就是 C 语言的 \0 用于结束字符串。