Back

切片 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;
c
  • buffer:指向元素数组的指针。数组中的每个元素都是 const void * 类型,这意味着它可以指向任何类型的对象。
  • len:数组的长度,即数组中元素的数量。
  • kind:数组中元素的类型,用 koopa_raw_slice_item_kind_t 枚举类型表示,可以是类型、函数、基本块或值等。

基本块 Basic Block

basic block 就是一系列的指令集合,在其内逻辑流不会发生跳转。

需要注意的是,基本块的结尾必须是 brjumpret 指令其中之一 (并且,这些指令只能出现在基本块的结尾)。也就是说,即使两个基本块是相邻的,例如上述程序的 %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

这些引用的值记作这个 valuedata,根据操作的不同,其会有不同的字段,比如对于 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;
};
c
  • ty:值的类型信息,用于描述值的静态类型,对应 koopa_raw_type_t 类型,一个值可以是 int32pointerfunction 等。
  • name:值的名称,如 @a_0@main 等,只对 funcalloc 指令有意义。
  • used_by:值被哪些值使用,对应 koopa_raw_slice_t 类型,表示值被哪些指令使用。
  • kind:值的类型和依赖关系,用于描述值的动态行为,对应 koopa_raw_value_kind_t 类型,表示指令的类型,如 integeraggregate 等。
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;
c
  • tag:值的种类,对应 koopa_raw_value_tag_t 枚举类型。
  • data:值的具体数据,根据 tag 的不同,有不同的结构体。如上文所说的 load 指令,其 tagKOOPA_RVT_LOAD,其 datakoopa_raw_load_t 类型,而 koopa_raw_load_t 又会有 load 指令所需的 srcdest 两个指令字面字段。

类型 type

类型 type 对应 koopa_raw_type_t 类型,表示指向一个 koopa_raw_type_kind_t 类型的指针,用于描述值的静态类型,一个值可以是 int32pointerfunction 等。

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;
c
  • tag:类型标签,表示类型的种类,对应 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

若一个 valuekind.tagKOOPA_RVT_GET_PTRKOOPA_RVT_GET_ELEM_PTR,则其 kind.datakoopa_raw_get_ptr_tkoopa_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_0src
  • 1index

那么,有时候我们还会想要获得指针所指向范围的大小,那么我们就可以使用 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_PTRvalue,我们使用 get_alloc_size(value.kind.data.get_ptr.src->ty->data.pointer.base) 来获得指针的步长
  • 对于一个 value.kind.tag = KOOPA_RVT_GET_ELEM_PTRvalue,我们使用 get_alloc_size(value.kind.data.get_elem_ptr.src->ty->data.pointer.base) 来获得指针的步长

一时间也想不到什么很好的说法来通俗的说明…

Koopa IR 人话版
https://arthals.ink/blog/koopa
Author Arthals
Published at January 14, 2025
Comment seems to stuck. Try to refresh?✨