前往小程序，Get更优阅读体验！
立即前往
文档建议反馈控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
发布
首页
学习
活动
专区
工具
TVP最新优惠活动
返回腾讯云官网
社区首页 >专栏 >使用 Inkwell 生成 LLVM IR

使用 Inkwell 生成 LLVM IR

原创
作者头像
谛听
发布于 2023-06-13 07:52:47
8720
发布于 2023-06-13 07:52:47
举报
文章被收录于专栏：随意记录随意记录

源码：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 核心基础设施的核心“全局”数据，包括类型和常量统一表。

代码语言：javascript
复制
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 对象的顶级容器。每个模块直接包含全局变量列表、函数列表、该模块所依赖的库（或其它模块）列表、符号表以及有关目标特性的各种数据。

代码语言：javascript
复制
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。

代码语言：javascript
复制
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 减去操作数.

代码语言：javascript
复制
builder.build_int_neg(exp, "int_neg")

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

代码语言：javascript
复制
builder.build_int_compare(
    IntPredicate::EQ,
    compiler.int_type.const_int(0_u64, true),
    exp,
    "logical_not_result_int",
)

2.2 算术表达式

代码语言：javascript
复制
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 比较和逻辑表达式

比较表达式

代码语言：javascript
复制
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")

逻辑表达式

代码语言：javascript
复制
builder.build_and(lhs, rhs, "logical_and")
builder.build_or(lhs, rhs, "logical_or")

3 常量和变量

3.1 常量

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

3.2 变量和赋值

例子：

代码语言：javascript
复制
int main() {
  int x = 10;
  x = x + 1;
  return x;
}

int x = 10

  1. 为变量 x 申请一块内存，返回内存指针 ptr
  2. 将常量 10 赋值给 ptr
代码语言：javascript
复制
// 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：

代码语言：javascript
复制
// 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
代码语言：javascript
复制
// 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：

代码语言：javascript
复制
// 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 新的作用域，退出时，弹出作用域。

代码语言：javascript
复制
// 在进入 block 时，push 新的作用域
scopes.push(HashMap::new());

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

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

5 if 语句

例子：

代码语言：javascript
复制
int main() {
    if (1 < 2) {

    } else {

    }
    return 0;
}

LLVM：

代码语言：javascript
复制
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：

代码语言：javascript
复制
br i1 true, label %if_block, label %else_block

if_block:

else_block:

after_block:

6 while 语句

例子：

代码语言：javascript
复制
int main() {
    int i = 0;
    while (i < 10) {
        i = i + 1;
    }
    return 0;
}

LLVM：

代码语言：javascript
复制
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：

代码语言：javascript
复制
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 函数定义

例子：

代码语言：javascript
复制
int half(int x) {
	 return x / 2;
}

void f() {}

函数签名：

代码语言：javascript
复制
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：

代码语言：javascript
复制
let function = module.add_function(&self.id, fn_type, None);

开始实现函数：

代码语言：javascript
复制
let entry_block = context.append_basic_block(function, "entry");

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

创建新的作用域：

代码语言：javascript
复制
compiler.scopes.push(HashMap::new());

加载入参：

代码语言：javascript
复制
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：

代码语言：javascript
复制
self.block.generate(compiler)?;

退出作用域：

代码语言：javascript
复制
compiler.scopes.pop();

生成的 LLVM IR：

代码语言：javascript
复制
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 函数调用

例子：

代码语言：javascript
复制
int main() {
  f();
  return half(10);
}

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

代码语言：javascript
复制
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(),
    });
}

生成参数类型：

代码语言：javascript
复制
let llvm_params_value = self.args
  .iter()
  .by_ref()
  .map(|arg| arg.generate(compiler).unwrap().into())
  .collect::<Vec<BasicMetadataValueEnum>>();

调用函数：

代码语言：javascript
复制
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：

代码语言：javascript
复制
define i32 @main() {
entry:
  call void @f()
  %half = call i32 @half(i32 10)
  ret i32 %half
}

7.3 全局变量和常量

例子：

代码语言：javascript
复制
int var;

const int one = 1;

int main() {
  return var + one;
}

全局常量：

代码语言：javascript
复制
// 将全局常量添加到 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);

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

全局变量：

代码语言：javascript
复制
// 为全局变量分配内存
let global = module.add_global(context.i32_type(), None, &self.id);

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

生成的 LLVM IR：

代码语言：javascript
复制
@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 全局数组

例子：

代码语言：javascript
复制
int a[2][3];

int main() {
		return 0;
}
  1. 为数组每一维的长度进行编译期求值：
代码语言：javascript
复制
let dims = self.dims
    .iter()
    .rev()
    .map(|x| {
        x.eval(compiler).unwrap() as u32
    })
    .collect::<Vec<u32>>();

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

  1. 生成数组类型：
代码语言：javascript
复制
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：
代码语言：javascript
复制
module.add_global(llvm_type, None, &self.id);

生成的 LLVM IR：

代码语言：javascript
复制
; ModuleID = 'module'
source_filename = "module"

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

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

8.1.2 局部数组

例子：

代码语言：javascript
复制
int main() {
		int a[2][3];
}
  1. 为数组每一维的长度进行编译期求值，同 8.1.1
  2. 生成数组类型，同 8.1.1
  3. 为数组分配空间
代码语言：javascript
复制
let ptr = compiler.builder.build_alloca(llvm_type, &self.id);

生成的 LLVM IR：

代码语言：javascript
复制
; ModuleID = 'module'
source_filename = "module"

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

8.2 数组初始化

例子：

代码语言：javascript
复制
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 初始化列表

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

代码语言：javascript
复制
int arr[2][3] = {1, 2, 3, {4}};

我们需要将其补充完整：

代码语言：javascript
复制
int arr[2][3] = {{1, 2, 3}, {4, 0, 0}};

步骤：

  1. 从最低维起，记录各维度的长度 len_1, len_2, …, len_n 和总长度 total_1, total_2, …, total_n。 例如，对于 int arr[2][3]，会得到 [(3, 3), (2, 6)]；对于 int arr[2][3][4]，会得到 [(4, 4), (3, 12), (2, 24)]
  2. 初始化待填充列表 reshaped，会比实际多一维。 例如，对于 int a[2][3]，得到 [][][]
  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 变化过程如下所示：

代码语言：javascript
复制
// 初始化待填充列表
[][][][]

// 依次填充最低维
[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 后的初始化列表平铺成一个列表

例如，将

代码语言：javascript
复制
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}}
};

改为

代码语言：javascript
复制
{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 步生成的列表构建数组：

代码语言：javascript
复制
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 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} 的变化过程为：

代码语言：javascript
复制
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}}}

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

代码语言：javascript
复制
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 a[2][3] = {1, 2, 3, {4}}; 生成的 IR 为：

代码语言：javascript
复制
@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：

代码语言：javascript
复制
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;
}
代码语言：javascript
复制
; 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 到局部数组：

代码语言：javascript
复制
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();

例如，对于

代码语言：javascript
复制
int main() {
    int d[2][3] = {1, 2, 3, {4}};
    return 0;
}

会得到

代码语言：javascript
复制
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 中，如果初始化列表中有变量，则先加载变量，然后赋值给数组。赋值的时候，需要先根据下标获得当前数组元素地址：

代码语言：javascript
复制
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);
}

例如，对于：

代码语言：javascript
复制
int e = 1
int g[2] = {e, 2};

生成的 IR 为：

代码语言：javascript
复制
%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：

代码语言：javascript
复制
void f() {
    int e = 1;
    int g[2] = {e, 2};
    return;
}

int main() {
    int d[2][3] = {1, 2, 3, {4}};
    return 0;
}
代码语言：javascript
复制
; 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 数组参数

例子：

代码语言：javascript
复制
void f(int a[][3]) {
    return;
}

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

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

代码语言：javascript
复制
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 arr[2][3]，array_type 是 [2 x [3 x i32]]，生成方式为：

代码语言：javascript
复制
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 arr[2][3] 传给 f(arr) 时，会生成：

代码语言：javascript
复制
%array = getelementptr inbounds [2 x [3 x i32]], ptr %arr, i32 0, i32 0

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

代码语言：javascript
复制
let param_type = if param.dims.is_some() {
    BasicMetadataTypeEnum::from(
        context.i32_type().ptr_type(AddressSpace::default())
    )
}

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

代码语言：javascript
复制
let param_type = if let Some(ref dims) = param.dims {
    context.i32_type().ptr_type(AddressSpace::default()).as_basic_type_enum()
}

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

代码语言：javascript
复制
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：

代码语言：javascript
复制
void f(int a[][3]) {
    return;
}

int main() {
    int arr[2][3];
    f(arr);
    return 0;
}
代码语言：javascript
复制
; 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 访问非参数数组

例子：

代码语言：javascript
复制
int main() {
	int arr[2][3] = {1, 2, 3, {4}};
	int b = arr[1][2];
	return 0;
}

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

代码语言：javascript
复制
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：

代码语言：javascript
复制
; 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 访问参数数组

例子：

代码语言：javascript
复制
void f(int a[][3]) {
    int b = a[1][2];
    return;
}

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

代码语言：javascript
复制
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：

代码语言：javascript
复制
void f(int a[][3]) {
    int b = a[1][2];
    return;
}
代码语言：javascript
复制
; 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 修改非参数数组

例子：

代码语言：javascript
复制
int main() {
	int arr[2][3];
	arr[1][2] = 5;
	return 0;
}

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

代码语言：javascript
复制
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：

代码语言：javascript
复制
; 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 修改参数数组

例子：

代码语言：javascript
复制
void f(int a[][3]) {
    a[1][2] = 3;
    return;
}

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

代码语言：javascript
复制
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：

代码语言：javascript
复制
; 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：

代码语言：javascript
复制
clang -S -emit-llvm hello.c

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

llvm
llvm-ir
rust

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

llvm
llvm-ir
rust
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
LV.
文章
0
获赞
0
目录
  • 1 LLVM 数据结构
  • 2 表达式
    • 2.1 一元表达式
      • 2.2 算术表达式
        • 2.3 比较和逻辑表达式
        • 3 常量和变量
          • 3.1 常量
            • 3.2 变量和赋值
            • 4 语句块和作用域
            • 5 if 语句
            • 6 while 语句
            • 7 函数和全局变量
              • 7.1 函数定义
                • 7.2 函数调用
                  • 7.3 全局变量和常量
                  • 8 数组
                    • 8.1 声明数组
                      • 8.1.1 全局数组
                      • 8.1.2 局部数组
                    • 8.2 数组初始化
                      • 8.2.1 常量数组 or 全局数组
                      • 8.2.2 局部数组
                    • 8.3 数组参数
                      • 8.4 访问数组
                        • 8.4.1 访问非参数数组
                        • 8.4.2 访问参数数组
                      • 8.5 修改数组
                        • 8.5.1 修改非参数数组
                        • 8.5.2 修改参数数组
                    • 9 小技巧
                    相关产品与服务
                    容器服务
                    腾讯云容器服务（Tencent Kubernetes Engine, TKE）基于原生 kubernetes 提供以容器为核心的、高度可扩展的高性能容器管理服务，覆盖 Serverless、边缘计算、分布式云等多种业务部署场景，业内首创单个集群兼容多种计算节点的容器资源管理模式。同时产品作为云原生 Finops 领先布道者，主导开源项目Crane，全面助力客户实现资源优化、成本控制。
                    产品介绍产品文档
                    618年中盛惠，限时抢
                    领券

                    腾讯云开发者

                    扫码关注腾讯云开发者

                    扫码关注腾讯云开发者

                    领取腾讯云代金券

                    热门产品

                    热门推荐

                    更多推荐

                    Copyright © 2013 - 2024 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

                    深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 深公网安备号 44030502008569

                    腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号 | 京公网安备号11010802020287

                    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

                    Copyright © 2013 - 2024 Tencent Cloud.

                    All Rights Reserved. 腾讯云 版权所有

                    登录 后参与评论