Koopa IR 笔记

Lv2 目标代码生成

任务要求从 Koopa IR 生成 RISC-V ASM。

Koopa IR 提供了 Rust binding，因此只需 DFS 遍历 Program，通过匹配 Value 生成汇编语句。

我剛到 Rust，不熟地方（

好在教程提示了通过 impl trait 递归查找下层结构。

下面拆解分析 Koopa IR in-memory form 结构：

Koopa IR entities, including programs ([Program]), functions ([Function], [FunctionData]), basic blocks ([BasicBlock], [BasicBlockData]) and values ([Value], [ValueData]).

rust

pub struct Program {
  pub(in crate::ir) values: Rc<RefCell<HashMap<Value, ValueData>>>,
  pub(in crate::ir) inst_layout: Vec<Value>,
  funcs: HashMap<Function, FunctionData>,
  func_tys: Rc<RefCell<HashMap<Function, Type>>>,
  func_layout: Vec<Function>,
}

Koopa IR 使用 Program 结构体表示程序

values：Rc<RefCell<>> 参考圣经，用于多可变引用（类似 C++ std::shared_ptr）；内部使用 HashMap 记录 (Value, ValueData) 对应关系(Value 即为 ASM instruction，具体可参考 SSA IR）。

rust

pub struct ValueData {
  ty: Type,
  name: Option<String>,
  kind: ValueKind,
  pub(in crate::ir) used_by: HashSet<Value>,
}

ValueData 记录类型/名称/调用，注意此处 ty 类型为 Rust built-in type，kind 类型为 Koopa IR instruction type，Rust 实现为枚举类型。

inst_layout: 记录指令顺序。

注意 Rust 一般使用 Vec (VecArray) 作为有序列表结构，LinkedList 引用处理复杂且无性能优势。

funcs: 记录 (Function, FunctionData) 对应关系。

rust

pub struct FunctionData {
  ty: Type,
  name: String,
  params: Vec<Value>,
  dfg: DataFlowGraph,
  layout: Layout,
}

FunctionData 较为复杂。记录函数类型/名称/参数列表，以及 dfg, layout 两个复杂的结构。

rust

/// Data flow graph of a function.
///
/// `DataFlowGraph` holds all data of values ([`ValueData`]) and basic
/// blocks ([`BasicBlockData`]), and maintains their use-define and
/// define-use chain.
pub struct DataFlowGraph {
  pub(in crate::ir) globals: GlobalValueMapCell,
  pub(in crate::ir) func_tys: FuncTypeMapCell,
  values: HashMap<Value, ValueData>,
  bbs: HashMap<BasicBlock, BasicBlockData>,
}

rust

/// Layout of instructions and basic blocks in a function.
///
/// `Layout` maintains the order of instructions ([`Value`]) and basic
/// blocks ([`BasicBlock`]) in function.
pub struct Layout {
  bbs: BasicBlockList,
  inst_bb: Rc<RefCell<HashMap<Value, BasicBlock>>>,
}

rust

pub(in crate::ir) type GlobalValueMapCell = Weak<RefCell<HashMap<Value, ValueData>>>;

pub(in crate::ir) type FuncTypeMapCell = Weak<RefCell<HashMap<Function, Type>>>;

pub type BasicBlockList = KeyNodeList<BasicBlock, BasicBlockNode, BasicBlockMap>;

/// The node in [`BasicBlockList`] that holds the instruction list
/// ([`InstList`]) in the basic block.
pub struct BasicBlockNode {
  insts: InstList,
  prev: Option<BasicBlock>,
  next: Option<BasicBlock>,
}

pub type InstList = KeyNodeList<Value, InstNode, InstMap>;

pub struct InstNode {
  prev: Option<Value>,
  next: Option<Value>,
}

func_tys: Rc<RefCell<>> 包裹内部 HashMap<Function, Type>> 记录函数对应类型。
func_layout: Vec<Function> 函数有序列表。

Koopa IR 笔记 ​

Lv2 目标代码生成 ​

Koopa IR 笔记

Lv2 目标代码生成