这篇文章上次修改于 402 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

源码：https://github.com/felicityin/sysy-rs

本文中的例子拷贝自：https://pku-minic.github.io/online-doc

实现语言的过程大概为：词法分析、语法分析、语义分析、优化、代码生成。

可以使用 larlpop 进行词法、语法解析，这部分的文档较为充足，既可以阅读官方的教程，也可以阅读该教程：https://michael-f-bryan.github.io/calc/book/html/intro.html。

本文主要讲述在用 larlpop 生成 AST (Abstract Syntax Tree) 后，如何使用 inkwell 将其转为 LLVM IR，该过程会进行一些语义分析和优化。最后将 LLVM IR 交给 LLVM，LLVM 将其生成指定平台的目标代码。

• IR 指中间表达方式，介于高级语言和汇编语言之间。与高级语言相比，丢弃了语法和语义特征，比如作用域、面向对象等；与汇编语言相比，不会有硬件相关的细节，比如目标机器架构、操作系统等。

本文不考虑浮点型，整型只考虑 i32。

1 LLVM 数据结构

Context: 拥有和管理 LLVM 核心基础设施的核心“全局”数据，包括类型和常量统一表。

let context = Context::create();
let builder = context.create_module("module");
let module = context.create_builder();

context.f64_type().const_float(0.0)
context.append_basic_block(function, "then");

Module: 是所有其它 LLVM IR 对象的顶级容器。每个模块直接包含全局变量列表、函数列表、该模块所依赖的库（或其它模块）列表、符号表以及有关目标特性的各种数据。

module.add_function(proto.name.as_str(), fn_type, None);
module.add_global(llvm_type, None, var_name);
module.get_first_global().unwrap()
module.get_last_global().unwrap()

let global_value = self.module.add_global(llvm_type, None, var_name);
global_value.set_linkage(Linkage::Common);
global_value.set_constant(true);
global_value.set_initializer(&value_after_cast);
global_value.set_initializer(&llvm_type.const_zero());
global_value.as_pointer_value()

Builder: 生成 LLVM 指令。追踪当前指令要插入的位置，创建新指令。一个 basic block 中可包含多条指令，一个函数中可包含多个 basic block。

builder.build_conditional_branch(cond, then_bb, else_bb);
builder.position_at_end(then_bb);
builder.build_phi(self.context.f64_type(), "iftmp");
builder.build_store(start_alloca, start);
builder.build_load(start_alloca, var_name);
builder.build_float_add(lhs, rhs, "tmpadd")),
builder.build_call(fun, &[lhs.into(), rhs.into()], "tmpbin")

2 表达式

2.1 一元表达式

变补 (取负数): 0 减去操作数.

builder.build_int_neg(exp, "int_neg")

逻辑取反: 操作数和 0 比较相等

builder.build_int_compare(
    IntPredicate::EQ,
    compiler.int_type.const_int(0_u64, true),
    exp,
    "logical_not_result_int",
)

2.2 算术表达式

builder.build_int_add(lhs, rhs, "int_add")
builder.build_int_sub(lhs, rhs, "int_sub")

builder.build_int_mul(lhs, rhs, "int_mul")
builder.build_int_signed_div(lhs, rhs, "int_div")
builder.build_int_signed_rem(lhs, rhs, "int_mod")

2.3 比较和逻辑表达式

比较表达式

builder.build_int_compare(IntPredicate::EQ, lhs, rhs, "int_eq")
builder.build_int_compare(IntPredicate::NE, lhs, rhs, "int_ne")

builder.build_int_compare(IntPredicate::SLT, lhs, rhs, "int_lt")
builder.build_int_compare(IntPredicate::SGT, lhs, rhs, "int_gt")
builder.build_int_compare(IntPredicate::SLE, lhs, rhs, "int_le")
builder.build_int_compare(IntPredicate::SGE, lhs, rhs, "int_ge")

逻辑表达式

builder.build_and(lhs, rhs, "logical_and")
builder.build_or(lhs, rhs, "logical_or")

3 常量和变量

3.1 常量

常量会在编译期直接求值，存到作用域列表中，后面用到的时候直接取出来。

3.2 变量和赋值

例子：

int main() {
  int x = 10;
  x = x + 1;
  return x;
}

int x = 10

1. 为变量 x 申请一块内存，返回内存指针 ptr
2. 将常量 10 赋值给 ptr

// 1
let ptr = builder.build_alloca(context.i32_type(), "x");

// 2
let v = context.i32_type().const_int(v, false);
builder.build_store(ptr, v);

1. 将变量 x 添加到作用域列表中，无 IR

int x = 10 生成的 LLVM IR：

// 1
%x = alloca i32, align 4

// 2
store i32 10, ptr %x, align 4

x = x + 1

1. 将 x 从作用域列表中取出，无 IR

2. 计算 x + 1

   1. 将 x 加载到内存
   2. 计算
3. 将 x + 1 的结果赋值给 l_x
4. 将新的 x 存回作用域列表，无 IR

// 1
let x_l = get_from_scope();

// 2.a
let x_r = builder.build_load(context.i32_type(), x_l, "x");

// 2.b
let v = context.i32_type().const_int(10, false);
builder.build_int_add(x_r, v, "int_add")

// 3
builder.build_store(x_r, x_l);

// 4
insert_to_scope(x_l);

x = x + 1 生成 LLVM IR：

// 2.a
%x1 = load i32, ptr %x, align 4

// 2.b
%int_add = add i32 %x1, 1

// 3
store i32 %int_add, ptr %x, align 4

4 语句块和作用域

语句块语法

一个大括号内的内容为一个语句块。

作用域

• 支持作用域嵌套
• 在进入和退出代码块时更新符号表的层次结构
• 只在当前作用域添加符号
• 能够跨作用域查询符号定义

作用域实现

生成 block IR 时，在进入 block 时，push 新的作用域，退出时，弹出作用域。

// 在进入 block 时，push 新的作用域
scopes.push(HashMap::new());

// 为 block 内的每个元素生成 IR
for item in &self.items {
    item.generate(compiler)?;
}

// 退出 block 时，弹出作用域
compiler.scopes.pop();

5 if 语句

例子：

int main() {
    if (1 < 2) {

    } else {

    }
    return 0;
}

LLVM：

let if_block = context.append_basic_block(func, "if_block");
let else_block = context.append_basic_block(func, "else_block");
let after_block = context.append_basic_block(func, "after_block");

// 生成 condition expr 的 IR
let cond_value = self.cond_expr.generate()?;  

// 生成条件分支
builder.build_conditional_branch(cond_value.into_int_value(), if_block, else_block);

// 移动到 if block 
builder.position_at_end(if_block);

// 生成 if block 的 IR
self.then_stmt.generate(compiler)?;

// if block 中可能会嵌套别的 block，cur block 不一定是 if block
// 如果 cur block 有 return 的话，直接退出 if block
if cur_block.unwrap().get_terminator().is_some() {
    builder.build_unconditional_branch(after_block);
}

// 移动到 else block 
builder.position_at_end(else_block);

// 生成 else block 的 IR
self.else_stmt.generate(compiler)?;

生成的 LLVM IR：

br i1 true, label %if_block, label %else_block

if_block:

else_block:

after_block:

6 while 语句

例子：

int main() {
    int i = 0;
    while (i < 10) {
        i = i + 1;
    }
    return 0;
}

LLVM：

let while_head = context.append_basic_block(func, "while_head");
let while_body = context.append_basic_block(func, "while_body");
let after_while = context.append_basic_block(func, "after_while");

// 从外边跳到本循环
builder.build_unconditional_branch(while_head);

// 移动到 while head
builder.position_at_end(while_head);

// 生成 condition expr 的 IR
let cond_value = self.cond_expr.generate()?;

// 生成条件分支
builder.build_conditional_branch(cond_value.into_int_value(), while_body, after_while);

// 记录本循环信息，以便后续 return 后 continue 时找到本循环
loops.push(Loop {
    loop_head: while_head,
    after_loop: after_while,
});

// 移动到 while body
builder.position_at_end(while_body);

// 生成循环体的 IR
self.body.generate(compiler)?;

// while body 中可能会嵌套别的 block，cur block 不一定是 while body
// 如果 cur block 没有 return 的话，跳回 while head
if cur_block.unwrap().get_terminator().is_none() {
    builder.build_unconditional_branch(while_head);
}

// 删掉本循环信息
loops.pop();

// 移到 after while block，从而退出 while body block
builder.position_at_end(after_while);

生成的 LLVM IR：

define i32 @main() {
entry:
  %i = alloca i32, align 4
  store i32 0, ptr %i, align 4
  br label %while_head

while_head:                                       ; preds = %while_body, %entry
  %i1 = load i32, ptr %i, align 4
  %int_lt = icmp slt i32 %i1, 10
  br i1 %int_lt, label %while_body, label %after_while

while_body:                                       ; preds = %while_head
  %i2 = load i32, ptr %i, align 4
  %int_add = add i32 %i2, 1
  store i32 %int_add, ptr %i, align 4
  br label %while_head

after_while:                                      ; preds = %while_head
  ret i32 0
}

7 函数和全局变量

7.1 函数定义

例子：

int half(int x) {
     return x / 2;
}

void f() {}

函数签名：

let mut params_type = Vec::new();
for param in self.params.iter() {
    params_type.push(BasicMetadataTypeEnum::from(context.i32_type());
}

let fn_type = match self.ty {
    FuncType::Int => context.i32_type().fn_type(params_type.as_ref(), false),
    FuncType::Void => context.i32_type().fn_type(params_type.as_ref(), false),
};

将函数添加到 module：

let function = module.add_function(&self.id, fn_type, None);

开始实现函数：

let entry_block = context.append_basic_block(function, "entry");

// 移动到 entry block
builder.position_at_end(entry_block);

创建新的作用域：

compiler.scopes.push(HashMap::new());

加载入参：

for (idx, param) in self.params.iter().enumerate() {
    // 为入参分配空间
    let ptr = compiler.builder.build_alloca(context.i32_type(), &param.id);
    
    // 获取第 n 个参数
    let value = function
        .get_nth_param(idx as u32)
        .expect("the function signatures have been added before");
    
    // option：为参数设置名称，方便阅读生成的 LLVM IR
    value.set_name(&param.id);
    
    // 加载入参
    builder.build_store(ptr, value);
    
    // 将入参添加到当前作用域
    compiler.new_value(&param.id, Variable::new_mut(ptr, llvm_type, array_type))?;
}

生成函数体 IR：

self.block.generate(compiler)?;

退出作用域：

compiler.scopes.pop();

生成的 LLVM IR：

define i32 @half(i32 %x1) {
entry:
  %x = alloca i32, align 4
  store i32 %x1, ptr %x, align 4
  %x2 = load i32, ptr %x, align 4
  %int_div = sdiv i32 %x2, 2
  ret i32 %int_div
}

define void @f() {
entry:
  ret void
}

7.2 函数调用

例子：

int main() {
  f();
  return half(10);
}

从 module 中获取已经定义好的函数，并检查参数个数是否匹配：

let fv = module.get_function(&self.id).unwrap();
if self.args.len() != fv.get_type().count_param_types() as usize {
    return Err(CompileErr::ArgCountMismatch {
        id: self.id.clone(),
        expect: fv.get_type().count_param_types() as usize,
        found: self.args.len(),
    });
}

生成参数类型：

let llvm_params_value = self.args
  .iter()
  .by_ref()
  .map(|arg| arg.generate(compiler).unwrap().into())
  .collect::<Vec<BasicMetadataValueEnum>>();

调用函数：

compiler.builder.build_call(
    fv,
    llvm_params_value.as_slice(),
    &self.id,
)
.try_as_basic_value()
.left()
.unwrap_or(compiler.int_type.const_zero().as_basic_value_enum())

生成的 LLVM IR：

define i32 @main() {
entry:
  call void @f()
  %half = call i32 @half(i32 10)
  ret i32 %half
}

7.3 全局变量和常量

例子：

int var;

const int one = 1;

int main() {
  return var + one;
}

全局常量：

// 将全局常量添加到 module
let global = module.add_global(context.i32_type(), None, &self.id);

// 初始化
let v = context.i32_type().const_int(init, false).as_basic_value_enum();
global.set_initializer(&v);

// 将全局常量添加到作用域符号表
...

全局变量：

// 为全局变量分配内存
let global = module.add_global(context.i32_type(), None, &self.id);

// 将全局变量添加到作用域符号表
...

生成的 LLVM IR：

@var = external global i32

define i32 @main() {
entry:
  %var = load i32, ptr @var, align 4
  %int_add = add i32 %var, 1
  ret i32 %int_add
}

8 数组

8.1 声明数组

8.1.1 全局数组

例子：

int a[2][3];

int main() {
        return 0;
}

1. 为数组每一维的长度进行编译期求值：

let dims = self.dims
    .iter()
    .rev()
    .map(|x| {
        x.eval(compiler).unwrap() as u32
    })
    .collect::<Vec<u32>>();

例如，对于 a1+1 会得到 [2, 3]，逆序后，得到 [3, 2]

1. 生成数组类型：

let array_type = dims.iter()
    .fold(
        compiler.int_type.as_basic_type_enum(),
        |acc, len| acc.array_type(len.to_owned()).as_basic_type_enum(),
    )
};

1. 添加到 module：

module.add_global(llvm_type, None, &self.id);

生成的 LLVM IR：

; ModuleID = 'module'
source_filename = "module"

@a = external global [2 x [3 x i32]]

define i32 @main() {
entry:
  ret i32 0
}

8.1.2 局部数组

例子：

int main() {
        int a[2][3];
}

1. 为数组每一维的长度进行编译期求值，同 8.1.1
2. 生成数组类型，同 8.1.1
3. 为数组分配空间

let ptr = compiler.builder.build_alloca(llvm_type, &self.id);

生成的 LLVM IR：

; ModuleID = 'module'
source_filename = "module"

define i32 @main() {
entry:
  %a = alloca [2 x [3 x i32]], align 4
  ret i32 0
}

8.2 数组初始化

例子：

int a[2][3] = {1, 2, 3, {4}};

void f() {
    int e = 1;
    int g[2] = {e, 2};
    return;
}

int main() {
    int b[2][3] = {1, 2, 3, {4}};
    return 0;
}

8.2.1 常量数组 or 全局数组

1. 为数组每一维的长度进行编译期求值，同 8.1.1
2. 为初始化列表的元素进行编译期求值

例如，对于 const int arr[2] = {1, 1 + 1}; ，需要得到 const int arr[2] = {1, 2}; 。

1. reshape 初始化列表

用户可能会这样初始化数组：

int arr[2][3] = {1, 2, 3, {4}};

我们需要将其补充完整：

int arr[2][3] = {{1, 2, 3}, {4, 0, 0}};

步骤：

1. 从最低维起，记录各维度的长度 len_1, len_2, …, len_n 和总长度 total_1, total_2, …, total_n。

   例如，对于 int arr2，会得到 [(3, 3), (2, 6)]；对于 int arr2[4]，会得到 [(4, 4), (3, 12), (2, 24)]

2. 初始化待填充列表 reshaped，会比实际多一维。

   例如，对于 int a2，得到 [][][]

3. 依次处理初始化列表，可能会遇到整数或嵌套的初始化列表。

   1. 如果是整数：直接将整数添加到当前所处理维度的 reshaped[0] 中。

      例如，对于 int arr[2][3] = {1, 2}; 看到初始化列表中的第 2 个元素 2 时，将其放到 reshaped[0] 中，得到 [1, 2][][]

   2. 如果是嵌套的初始化列表：说明需要填充待填充列表的下一个维度了，当前已经填充完毕的元素的个数必须是 len_n 的整数倍，否则这个初始化列表没有对齐数组维度的边界，属于语义错误。然后递归处理，把结果添加到 reshaped 的对齐的维度中。

      例如，对于 int arr[2][3] = {{1, 2, 3}, {4}}; 看到 {4} 时，初始化列表应该是 [ [1, 2, 3] ][] ，然后把 {4} 添加到所对齐的维度中，得到 [ [1, 2, 3] [4] ][]

4. carry：如果发现 reshaped[0] 已经达到当前维度的长度 len_n，则将其添加到下一维 reshaped[1] 中，并将 reshaped[0] 丢弃。

   例如，对于 int arr[2][3] = {1, 2, 3}; 当前处理的最低维度为 1，当前维度的长度为 3，当待填充列表成为了 [1, 2, 3][][] 时，应进一步变为 [ [1, 2, 3] ][] 。

5. 补 0：如果发现 reshaped[0] 的长度没有达到当前维度的总长度 total_n，则填充 0。

   例如，对于 int arr[2][3] = {{1, 2, 3}, {4}}; 当前处理的最低维度为 2，当前维度的总长度为 total_n = 6，当待填充列表成为了 [ [1, 2, 3], [4] ][] 时，应进一步变为 [ [1, 2, 3], [4, 0, 0] ][] 。

6. carry： [ [1, 2, 3], [4, 0, 0] ][] —> [ [1, 2, 3], [4, 0, 0] ] 。

一个具体的例子：

int arr[2][3][4] = {1, 2, 3, 4, {5}, {6}, {7, 8}};

reshaped 变化过程如下所示：

// 初始化待填充列表
[][][][]

// 依次填充最低维
[1][][][]
[1, 2, 3, 4][][][]

// carry：处理 (4, 4)，满了 4 个元素，将这 4 个元素作为一个 list，放到下一维
[] [[1, 2, 3, 4]] [] []

// 添加 [5]，递归处理，最终得到：
[] [[1, 2, 3, 4] [5, 0, 0, 0]] [] []

// 添加 [5] 时的递归过程，list = [5]，lens = [(4, 4)]
// [][]
// [5][]
// [5, 0, 0, 0][]  // 补 0，直到达到 total_1 = 4
// [] [[5, 0, 0, 0]]  // carry
// [] [[1, 2, 3, 4] [5, 0, 0, 0]] [] []  // 从递归返回，将递归结果放到当前待填充列表

// 添加 [6]，递归处理，最终得到：
[] [[1, 2, 3, 4] [5, 0, 0, 0] [6, 0, 0, 0]] [] []

// carry：处理 (3, 12)，满了 3 个元素，将这个 3 个元素作为一个 list，添加到下一维
[] [] [[[1, 2, 3, 4] [5, 0, 0, 0] [6, 0, 0, 0]]] []

// 添加 [7, 8]，递归处理，最终得到：
[] [] [[[1, 2, 3, 4] [5, 0, 0, 0] [6, 0, 0, 0]] [[7, 8, 0, 0] [0, 0, 0, 0] [0, 0, 0, 0]]] []

// 添加 [7, 8] 时的递归过程，list = [7, 8]，lens = [(4, 4), (3, 12)]
// [][][]
// [7, 8][][]
// [7, 8, 0, 0] [] []  // 补 0，直到达到 total_2 = 12
// [] [[7, 8, 0, 0]] []  // 补 0 的过程中会发生 carry
// [0, 0, 0, 0] [[7, 8, 0, 0]] [] // 继续补 0
// [] [[7, 8, 0, 0] [0, 0, 0, 0]] [] // carry
// [] [[7, 8, 0, 0] [0, 0, 0, 0] [0, 0, 0, 0]] [] // 继续补 0，carry
// [] [] [[[7, 8, 0, 0] [0, 0, 0, 0] [0, 0, 0, 0]]]  // carry
// 从递归返回，将递归结果放到当前待填充列表：
// [] [] [[[1, 2, 3, 4] [5, 0, 0, 0] [6, 0, 0, 0]] [[7, 8, 0, 0] [0, 0, 0, 0] [0, 0, 0, 0]]] []

// carry：处理 (2, 24)，满了 2 个元素，将这个 2 个元素作为一个 list，添加到下一维
[] [] [] [[[[1, 2, 3, 4] [5, 0, 0, 0] [6, 0, 0, 0]] [[7, 8, 0, 0] [0, 0, 0, 0] [0, 0, 0, 0]]]]

// 最终得到：
int arr[2][3][4] = {
  {{1, 2, 3, 4}, {5, 0, 0, 0}, {6, 0, 0, 0}},
  {{7, 8, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}}
};

1. 将 reshape 后的初始化列表平铺成一个列表

例如，将

int arr[2][3][4] = {
  {{1, 2, 3, 4}, {5, 0, 0, 0}, {6, 0, 0, 0}},
  {{7, 8, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}}
};

改为

{1, 2, 3, 4, 5, 0, 0, 0, 6, 0, 0, 0, 7, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

1. 初始化全局数组

声明数组的时候，需要确保数组类型是正确的。

从低维开始根据第 5 步生成的列表构建数组：

let mut dims = dims.iter();
let top_size = *dims.next().unwrap();

// 处理最低维度，会得到 ArrayValue 列表
let mut arrays = values
    .chunks(top_size as usize)
    .map(|a| context.i32_type().const_array(a))
    .collect::<Vec<ArrayValue>>();

let mut ty = context.i32_type().array_type(top_size);

// 处理剩下的每个维度
for d in dims {
    arrays = arrays
        .chunks(*d as usize)
        .map(|a| ty.const_array(a))
        .collect::<Vec<ArrayValue>>();

    ty = ty.array_type(*d);
}

例如，int arr2[4] = {1, 2, 3, 4, 5, 0, 0, 0, 6, 0, 0, 0, 7, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0} 的变化过程为：

1, 2, 3, 4, 5, 0, 0, 0, 6, 0, 0, 0, 7, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

// 处理最低维度，每 4 个 i32 一组，得到 6 组 [4 x i32]
{1, 2, 3, 4}, {5, 0, 0, 0}, {6, 0, 0, 0}, {7, 8, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}

// 处理较高维度，每 3 个 [4 x i32] 一组，得到 2 组 [3 x [4 x i32]]
{{1, 2, 3, 4}, {5, 0, 0, 0}, {6, 0, 0, 0}}, {{7, 8, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}}

// 处理最高维度，每 2 个 [3 x [4 x i32]] 一组，得到 1 组 [2 x [3 x [4 x i32]]]
{{{1, 2, 3, 4}, {5, 0, 0, 0}, {6, 0, 0, 0}}, {{7, 8, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}}}

将数组添加到全局符号，为数组设置初始化列表，将数组设为常量：

let const_array = module.add_global(
    ty,
    Some(AddressSpace::default()),
    &id
);

// arrays 最后只剩下一个元素
const_array.set_initializer(&arrays[0]);
const_array.set_constant(true);

最终，const int a2 = {1, 2, 3, {4}}; 生成的 IR 为：

@arr = constant [2 x [3 x [4 x i32]]] [[3 x [4 x i32]] [[4 x i32] [i32 1, i32 2, i32 3, i32 4], [4 x i32] [i32 5, i32 0, i32 0, i32 0], [4 x i32] [i32 6, i32 0, i32 0, i32 0]], [3 x [4 x i32]] [[4 x i32] [i32 7, i32 8, i32 0, i32 0], [4 x i32] zeroinitializer, [4 x i32] zeroinitializer]]

一个完整例子的 LLVM IR：

const int a[2][3] = {1, 2, 3, {4}};
int c[2][3] = {1, 2, 3, {4}};

int main() {
    const int b[2][3] = {1, 2, 3, {4}};
    return 0;
}

; ModuleID = 'module'
source_filename = "module"

@a = constant [2 x [3 x i32]] [[3 x i32] [i32 1, i32 2, i32 3], [3 x i32] [i32 4, i32 0, i32 0]]
@c = constant [2 x [3 x i32]] [[3 x i32] [i32 1, i32 2, i32 3], [3 x i32] [i32 4, i32 0, i32 0]]
@b = private unnamed_addr constant [2 x [3 x i32]] [[3 x i32] [i32 1, i32 2, i32 3], [3 x i32] [i32 4, i32 0, i32 0]]

define i32 @main() {
entry:
  %b = alloca [2 x [3 x i32]], align 4
  call void @llvm.memcpy.p0.p0.i32(ptr align 4 %b, ptr align 4 @b, i32 24, i1 false)
  ret i32 0
}

; Function Attrs: argmemonly nocallback nofree nounwind willreturn
declare void @llvm.memcpy.p0.p0.i32(ptr noalias nocapture writeonly, ptr noalias nocapture readonly, i32, i1 immarg) #0

attributes #0 = { argmemonly nocallback nofree nounwind willreturn }

8.2.2 局部数组

1. 为数组每一维的长度进行编译期求值，同 8.1.1
2. 为数组分配空间，同 8.1.2

3. 如果有初始化列表：

   1. 求初始化列表

      1. 如果初始化列表中的元素都是常量，进行编译器求值即可，同 8.1.1
      2. 如果初始化列表中有变量，为初始化列表中的每个元素生成 IR
   2. reshape 初始化列表，同 8.1.1
   3. 将初始化列表赋值给数组

步骤 3.c 中，如果初始化列表中都是常量，可以采用 8.2.1 中的方法先声明一个临时全局常量数组 const_array，然后将该数组 memcpy 到局部数组：

const_array.set_visibility(inkwell::GlobalVisibility::Hidden);
const_array.set_linkage(inkwell::module::Linkage::Private);
const_array.set_unnamed_addr(true);

let bytes_to_copy = len * std::mem::size_of::<i32>();
builder.build_memcpy(
    ptr,
    4,
    const_array.as_pointer_value(),
    4,
    compiler.int_type.const_int(bytes_to_copy as u64, false)
).unwrap();

例如，对于

int main() {
    int d[2][3] = {1, 2, 3, {4}};
    return 0;
}

会得到

d = private unnamed_addr constant [2 x [3 x i32]] [[3 x i32] [i32 1, i32 2, i32 3], [3 x i32] [i32 4, i32 0, i32 0]]

define i32 @main() {
entry:
  %d = alloca [2 x [3 x i32]], align 4
  call void @llvm.memcpy.p0.p0.i32(ptr align 4 %d, ptr align 4 @d, i32 24, i1 false)
  ret i32 0
}

步骤 3.c 中，如果初始化列表中有变量，则先加载变量，然后赋值给数组。赋值的时候，需要先根据下标获得当前数组元素地址：

for (i, v) in init.iter().enumerate() {
        // 计算数组当前元素下标
    let mut index = vec![context.i32_type().const_zero()];
    let mut e = i as u32;
    for d in dims.iter() {
        index.insert(1, context.i32_type().const_int((e % d).into(), false));
        e /= d;
    }

        // 获得当前数组元素地址
    let elemptr = unsafe {
        builder.build_in_bounds_gep(array_type, ptr, &index, &format!("elemptr{i}"))
    };

        // 从初始化列表获得常量或变量
    let elem = match v {
        Initializer::Const(c) => context.i32_type()
            .const_int(c.to_owned(), false)
            .as_basic_value_enum(),
        Initializer::Value(v) => v.to_owned(),
        _ => unreachable!(),
    };

        // 赋值
    builder.build_store(elemptr, elem);
}

例如，对于：

int e = 1
int g[2] = {e, 2};

生成的 IR 为：

%e = alloca i32, align 4
store i32 1, ptr %e, align 4

%g = alloca [2 x i32], align 4

%e1 = load i32, ptr %e, align 4
%elemptr0 = getelementptr inbounds [2 x i32], ptr %g, i32 0, i32 0
store i32 %e1, ptr %elemptr0, align 4

%elemptr1 = getelementptr inbounds [2 x i32], ptr %g, i32 0, i32 1
store i32 2, ptr %elemptr1, align 4

getelementptr 用来进行地址计算，非常类似于数组的索引和字段选择，但是又有点不同，它会需要一个额外的 0 索引，详见：经常被误解的 GetElementPtr(GEP) 指令

一个完整例子的 LLVM IR：

void f() {
    int e = 1;
    int g[2] = {e, 2};
    return;
}

int main() {
    int d[2][3] = {1, 2, 3, {4}};
    return 0;
}

; ModuleID = 'module'
source_filename = "module"

@d = private unnamed_addr constant [2 x [3 x i32]] [[3 x i32] [i32 1, i32 2, i32 3], [3 x i32] [i32 4, i32 0, i32 0]]

define void @f() {
entry:
  %e = alloca i32, align 4
  store i32 1, ptr %e, align 4

  %g = alloca [2 x i32], align 4

  %e1 = load i32, ptr %e, align 4
  %elemptr0 = getelementptr inbounds [2 x i32], ptr %g, i32 0, i32 0
  store i32 %e1, ptr %elemptr0, align 4

  %elemptr1 = getelementptr inbounds [2 x i32], ptr %g, i32 0, i32 1
  store i32 2, ptr %elemptr1, align 4
  ret void
}

define i32 @main() {
entry:
  %d = alloca [2 x [3 x i32]], align 4
  call void @llvm.memcpy.p0.p0.i32(ptr align 4 %d, ptr align 4 @d, i32 24, i1 false)
  ret i32 0
}

; Function Attrs: argmemonly nocallback nofree nounwind willreturn
declare void @llvm.memcpy.p0.p0.i32(ptr noalias nocapture writeonly, ptr noalias nocapture readonly, i32, i1 immarg) #0

attributes #0 = { argmemonly nocallback nofree nounwind willreturn }

8.3 数组参数

例子：

void f(int a[][3]) {
    return;
}

int main() {
    int arr[2][3];
    f(arr);
    return 0;
}

在调用函数时，需要为 FuncCall 生成 IR，应先构造入参，当入参是数组时，需要获取数组首元素的地址：

unsafe {
    builder.build_in_bounds_gep(
        array_type,
        ptr,
        vec![context.i32_type().const_zero(), context.i32_type().const_zero()].as_ref(),
        "array"
    ).as_basic_value_enum()
}

其中，array_type 是数组类型，ptr 是数组地址。例如，对于 int arr2，array_type 是 [2 x [3 x i32]]，生成方式为：

let array_type = dims.iter()
    .fold(
        context.i32_type().as_basic_type_enum(),
        |acc, len| acc.array_type(len.to_owned()).as_basic_type_enum(),
    )

ptr 是 builder.build_alloca() 时生成的地址。

所以，将 int arr2 传给 f(arr) 时，会生成：

%array = getelementptr inbounds [2 x [3 x i32]], ptr %arr, i32 0, i32 0

在为函数定义 FuncDef 生成 IR 时，在将函数添加到 module 时，需要先为参数生成 IR，当参数是数组参数时，参数的类型为指针：

let param_type = if param.dims.is_some() {
    BasicMetadataTypeEnum::from(
        context.i32_type().ptr_type(AddressSpace::default())
    )
}

在函数中，需要获取数组参数类型：

let param_type = if let Some(ref dims) = param.dims {
    context.i32_type().ptr_type(AddressSpace::default()).as_basic_type_enum()
}

然后与之前非数组参数一样，为参数分配空间，加载参数：

let ptr = builder.build_alloca(param_type, &param.id);
let value = function.get_nth_param(idx as u32).unwrap();
builder.build_store(ptr, value);

一个完整例子的 LLVM IR：

void f(int a[][3]) {
    return;
}

int main() {
    int arr[2][3];
    f(arr);
    return 0;
}

; ModuleID = 'module'
source_filename = "module"

define void @f(ptr %a1) {
entry:
  %a = alloca ptr, align 8
  store ptr %a1, ptr %a, align 8
  ret void
}

define i32 @main() {
entry:
  %arr = alloca [2 x [3 x i32]], align 4
  %array = getelementptr inbounds [2 x [3 x i32]], ptr %arr, i32 0, i32 0
  call void @f(ptr %array)
  ret i32 0
}

8.4 访问数组

8.4.1 访问非参数数组

例子：

int main() {
    int arr[2][3] = {1, 2, 3, {4}};
    int b = arr[1][2];
    return 0;
}

数组元素作为右值，先获取数组元素地址，然后加载到内存：

let mut idx_vals = vec![context.i32_type().const_zero()];
idx_vals.extend(lval.indices
    .iter()
    .map(|expr| context.i32_type()
        .const_int(expr.eval(compiler).unwrap() as u64, false)
    ),
);

builder.build_load(
    context.i32_type(),
    unsafe {
        builder.build_in_bounds_gep(
            array_type,
            ptr,
            idx_vals.as_ref(),
            "index_access"
        )
    },
    "array_item"
)

生成的 LLVM IR：

; ModuleID = 'module'
source_filename = "module"

@arr = private unnamed_addr constant [2 x [3 x i32]] [[3 x i32] [i32 1, i32 2, i32 3], [3 x i32] [i32 4, i32 0, i32 0]]

define i32 @main() {
entry:
  %arr = alloca [2 x [3 x i32]], align 4
  call void @llvm.memcpy.p0.p0.i32(ptr align 4 %arr, ptr align 4 @arr, i32 24, i1 false)
  
  %b = alloca i32, align 4

  %index_access = getelementptr inbounds [2 x [3 x i32]], ptr %arr, i32 0, i32 1, i32 2
  %array_item = load i32, ptr %index_access, align 4

  store i32 %array_item, ptr %b, align 4

  ret i32 0
}

; Function Attrs: argmemonly nocallback nofree nounwind willreturn
declare void @llvm.memcpy.p0.p0.i32(ptr noalias nocapture writeonly, ptr noalias nocapture readonly, i32, i1 immarg) #0

attributes #0 = { argmemonly nocallback nofree nounwind willreturn }

8.4.2 访问参数数组

例子：

void f(int a[][3]) {
    int b = a[1][2];
    return;
}

参数数组元素作为右值，先获取数组元素地址，然后加载到内存：

let idx_vals = lval.indices
  .iter()
  .map(|expr| context.i32_type()
      .const_int(expr.eval(compiler).unwrap() as u64, false)
  ).collect::<Vec<IntValue>>();

builder.build_load(
  context.i32_type(),
  unsafe {
      compiler.builder.build_in_bounds_gep(
          array_type,
          ptr,
          idx_vals.as_ref(),
          "index_access"
      )
  },
  "array_item"
)

想对于 8.4.1，只是下标有所不同，少了一个 0。

一个完整例子的 LLVM IR：

void f(int a[][3]) {
    int b = a[1][2];
    return;
}

; ModuleID = 'module'
source_filename = "module"

define void @f(ptr %a1) {
entry:
  %a = alloca ptr, align 8
  store ptr %a1, ptr %a, align 8

  %b = alloca i32, align 4

  %index_access = getelementptr inbounds [3 x i32], ptr %a, i32 1, i32 2
  %array_item = load i32, ptr %index_access, align 4
  store i32 %array_item, ptr %b, align 4

  ret void
}

8.5 修改数组

8.5.1 修改非参数数组

例子：

int main() {
    int arr[2][3];
    arr[1][2] = 5;
    return 0;
}

数组元素作为左值，需要先获取地址：

let mut idx_vals = vec![context.i32_type().const_zero()];
idx_vals.extend(self.indices
    .iter()
    .map(|expr| context.i32_type()
        .const_int(expr.eval(compiler).unwrap() as u64, false)
    ),
);

Ok(unsafe {
    builder.build_in_bounds_gep(
        array_type,
        ptr,
        idx_vals.as_ref(),
        "index_access"
    ).as_basic_value_enum()
})

生成的 LLVM IR：

; ModuleID = 'module'
source_filename = "module"

define i32 @main() {
entry:
  %arr = alloca [2 x [3 x i32]], align 4

  %index_access = getelementptr inbounds [2 x [3 x i32]], ptr %arr, i32 0, i32 1, i32 2
  
    store i32 5, ptr %index_access, align 4
  ret i32 0
}

8.5.2 修改参数数组

例子：

void f(int a[][3]) {
    a[1][2] = 3;
    return;
}

参数数组元素作为左值，需要先加载数组，然后获取数组元素地址：

let ptr = builder.build_load(
    context.i32_type().ptr_type(AddressSpace::default()),
    ptr,
    "array_ptr"
).into_pointer_value();

let idx_vals = self.indices
    .iter()
    .map(|expr| context.i32_type()
        .const_int(expr.eval(compiler).unwrap() as u64, false)
    ).collect::<Vec<IntValue>>();

Ok(unsafe {
    builder.build_in_bounds_gep(
        array_type,
        ptr,
        idx_vals.as_ref(),
        "index_access"
    ).as_basic_value_enum()
})

相对于 8.5.1，只是多了第一行中的加载数组。

生成的 LLVM IR：

; ModuleID = 'module'
source_filename = "module"

define void @f(ptr %a1) {
entry:
  %a = alloca ptr, align 8
  store ptr %a1, ptr %a, align 8

  %array_ptr = load ptr, ptr %a, align 8
  %index_access = getelementptr inbounds [3 x i32], ptr %array_ptr, i32 1, i32 2

  store i32 3, ptr %index_access, align 4
  ret void
}

9 小技巧

先大概明白生成的 LLVM IR 应该是什么样子，然后再使用 Inkwell 写出对应的 LLVM IR。如果不知道 LLVM IR 应该是什么样的，可以先写出 C 代码，然后用如下命令生成 LLVM IR：

clang -emit-llvm -S your_code.c -o your_code.ll