切片 Slice
slice
是存储一系列元素的数组。具体来说,koopa_raw_slice_t
是一个结构体,用于表示一个元素数组及其长度。其定义如下:
typedef struct {
// 数组指针
const void **buffer;
// 数组长度
uint32_t len;
// 数组中元素的类型
koopa_raw_slice_item_kind_t kind;
} koopa_raw_slice_t;
cbuffer
:指向元素数组的指针。数组中的每个元素都是const void *
类型,这意味着它可以指向任何类型的对象。len
:数组的长度,即数组中元素的数量。kind
:数组中元素的类型,用koopa_raw_slice_item_kind_t
枚举类型表示,可以是类型、函数、基本块或值等。
基本块 Basic Block
basic block
就是一系列的指令集合,在其内逻辑流不会发生跳转。
需要注意的是,基本块的结尾必须是
br
,jump
或ret
指令其中之一 (并且,这些指令只能出现在基本块的结尾)。也就是说,即使两个基本块是相邻的,例如上述程序的%else
基本块和%end
基本块,如果你想表达执行完前者之后执行后者的语义,你也必须在前者基本块的结尾添加一条目标为后者的jump
指令。这点和汇编语言中 label 的概念有所不同。
比如一段代码:
int main() {
int b = 1;
if (b == 1) {
return 1;
}
else {
return 2;
}
}
c其被翻译为如下的 KoopaIR:
fun @main(): i32 {
%main_entry:
@b_2 = alloc i32
store 1, @b_2
%0 = load @b_2
%1 = eq %0, 1
br %1, %then_0, %else_0
%then_0:
ret 1
%jump_0:
jump %end_0
%else_0:
ret 2
%jump_1:
jump %end_0
%end_0:
ret 0
}
asm这里,每个标号分开的区域就是一个基本块。
值 value
value
对应 koopa_raw_value_t
类型,表示指向一个值的指针,多数情况下,你可以认为它是一个指令的相关信息,因为我们知道,在 KoopaIR 中是静态单赋值,它总是类似下面这种只赋值一次的指令:
@b_2 = alloc i32
store 1, @b_2
@c_2 = alloc i32
store 2, @c_2
@d_2 = alloc i32
store 3, @d_2
@e_2 = alloc i32
store 4, @e_2
%0 = load @b_2
%1 = load @c_2
%2 = add %0, %1
%3 = load @d_2
%4 = add %2, %3
%5 = load @e_2
%6 = add %4, %5
ret %6
asm所以,这里你会发现,大多数指令就是一个 值,他们总是引用了一些别的值,做了一些事情。
比如,%0 = load @b_2
,就会引用两个值,一个是 @b_2
,另一个是 %0
。
这些引用的值记作这个 value
的 data
,根据操作的不同,其会有不同的字段,比如对于 load
指令,你需要如下访问到他的 data:
value->kind.data.load
c它会有两个属性:
src
:代表被加载的值dest
:代表存放加载结果的值
这两者类型也都为 koopa_raw_value_t
。
value
所谓的这个值也可以是代表 KoopaIR 中用到的一些“东西”,如 interger
代表一个数,又如 aggregate
代表一个初始化列表。其的定义链如下:
typedef const koopa_raw_value_data_t *koopa_raw_value_t;
typedef struct koopa_raw_value_data koopa_raw_value_data_t;
c所以,对其解引用后就会得到 koopa_raw_value_data
类型,其定义如下:
struct koopa_raw_value_data {
// 值的静态类型
koopa_raw_type_t ty;
// 值的名称
const char *name;
// 值被哪些值使用
koopa_raw_slice_t used_by;
// 值的具体种类,代表值的动态行为
koopa_raw_value_kind_t kind;
};
cty
:值的类型信息,用于描述值的静态类型,对应koopa_raw_type_t
类型,一个值可以是int32
、pointer
、function
等。name
:值的名称,如@a_0
,@main
等,只对func
和alloc
指令有意义。used_by
:值被哪些值使用,对应koopa_raw_slice_t
类型,表示值被哪些指令使用。kind
:值的类型和依赖关系,用于描述值的动态行为,对应koopa_raw_value_kind_t
类型,表示指令的类型,如integer
,aggregate
等。
typedef struct {
koopa_raw_value_tag_t tag;
union {
koopa_raw_integer_t integer;
koopa_raw_aggregate_t aggregate;
koopa_raw_func_arg_ref_t func_arg_ref;
koopa_raw_block_arg_ref_t block_arg_ref;
koopa_raw_global_alloc_t global_alloc;
koopa_raw_load_t load;
koopa_raw_store_t store;
koopa_raw_get_ptr_t get_ptr;
koopa_raw_get_elem_ptr_t get_elem_ptr;
koopa_raw_binary_t binary;
koopa_raw_branch_t branch;
koopa_raw_jump_t jump;
koopa_raw_call_t call;
koopa_raw_return_t ret;
} data;
} koopa_raw_value_kind_t;
ctag
:值的种类,对应koopa_raw_value_tag_t
枚举类型。data
:值的具体数据,根据tag
的不同,有不同的结构体。如上文所说的load
指令,其tag
为KOOPA_RVT_LOAD
,其data
为koopa_raw_load_t
类型,而koopa_raw_load_t
又会有load
指令所需的src
和dest
两个指令字面字段。
类型 type
类型 type
对应 koopa_raw_type_t
类型,表示指向一个 koopa_raw_type_kind_t
类型的指针,用于描述值的静态类型,一个值可以是 int32
、pointer
、function
等。
typedef const koopa_raw_type_kind_t *koopa_raw_type_t;
typedef struct koopa_raw_type_kind {
koopa_raw_type_tag_t tag;
union {
struct {
const struct koopa_raw_type_kind *base;
size_t len;
} array;
struct {
const struct koopa_raw_type_kind *base;
} pointer;
struct {
koopa_raw_slice_t params;
const struct koopa_raw_type_kind *ret;
} function;
} data;
} koopa_raw_type_kind_t;
ctag
:类型标签,表示类型的种类,对应koopa_raw_type_tag_t
枚举类型。data
:类型数据,根据tag
的不同,有不同的结构体,也可能没有数据只是分配了空间。
typedef enum {
// 32 位整数
KOOPA_RTT_INT32,
// 空类型
KOOPA_RTT_UNIT,
// 数组
KOOPA_RTT_ARRAY,
// 指针
KOOPA_RTT_POINTER,
// 函数
KOOPA_RTT_FUNCTION,
} koopa_raw_type_tag_t;
c初始化列表 aggregate
一个数组:
int a[2][2] = {1, 2, 3, 4};
c会被 KoopaIR 翻译为:
global @a_0 = alloc [[i32, 2], 2], {{1, 2}, {3, 4}}
c那么 {{1, 2}, {3, 4}}
就是一个 aggregate
,它的元素是两个 aggregate
,即 {1, 2}
和 {3, 4}
,其中每个 aggregate
的元素是两个 integer
。
指针 get_ptr
/ get_elem_ptr
若一个 value
的 kind.tag
为 KOOPA_RVT_GET_PTR
或 KOOPA_RVT_GET_ELEM_PTR
,则其 kind.data
为 koopa_raw_get_ptr_t
或 koopa_raw_get_elem_ptr_t
,里面存放了值的依赖关系:
typedef struct {
// 源
koopa_raw_value_t src;
// 索引
koopa_raw_value_t index;
} koopa_raw_get_ptr_t;
typedef struct {
// 源
koopa_raw_value_t src;
// 索引
koopa_raw_value_t index;
} koopa_raw_get_elem_ptr_t;
c举例说明,对于指令:
%0 = get_ptr @a_0, 1
%0 = get_elem_ptr @a_0, 1
asm@a_0
是src
1
是index
那么,有时候我们还会想要获得指针所指向范围的大小,那么我们就可以使用 get_alloc_size
函数。
int get_alloc_size(const koopa_raw_type_t ty) {
switch (ty->tag) {
// 空类型不占用空间
case KOOPA_RTT_UNIT:
return 0;
// 函数类型不占用空间
case KOOPA_RTT_FUNCTION:
return 0;
// 32 位整数占用 4 字节
case KOOPA_RTT_INT32:
return 4;
// 指针类型占用 4 字节
case KOOPA_RTT_POINTER:
return 4;
// 数组类型占用空间为数组长度乘以数组元素类型占用空间
case KOOPA_RTT_ARRAY:
return ty->data.array.len * get_alloc_size(ty->data.array.base);
default:
printf("Invalid type: %s\n", koopaRawTypeTagToString(ty->tag).c_str());
assert(false);
}
}
c- 对于一个
value.kind.tag = KOOPA_RVT_GET_PTR
的value
,我们使用get_alloc_size(value.kind.data.get_ptr.src->ty->data.pointer.base)
来获得指针的步长 - 对于一个
value.kind.tag = KOOPA_RVT_GET_ELEM_PTR
的value
,我们使用get_alloc_size(value.kind.data.get_elem_ptr.src->ty->data.pointer.base)
来获得指针的步长
一时间也想不到什么很好的说法来通俗的说明…