Open14
Cranelift IR

- Rustで書かれたCodegenバックエンド、コンパイラ
- WASMバックエンドあり(ここではX86について)
- Cranelift IRという独自のIRを持つ(本旨)
- IRはSSA形式
- PHIΦではなく、ブランチパラメータで各ブロックが引数をとる

IRはビルド時に動的に生成されるRustソースにある
#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
#[cfg_attr(feature = "enable-serde", derive(Serialize, Deserialize))]
#[allow(missing_docs)]
pub enum InstructionData {
AtomicCas {
opcode: Opcode,
args: [Value; 3], // cranelift\codegen\meta\src\gen_inst.rs:76
flags: ir::MemFlags, // cranelift\codegen\meta\src\gen_inst.rs:91
}
, // cranelift\codegen\meta\src\gen_inst.rs:94
...
IRは独自のメタから生成される
cranelift/codegen/meta/src/shared/instructions.rs
pub(crate) fn define(
all_instructions: &mut AllInstructions,
formats: &Formats,
imm: &Immediates,
entities: &EntityRefs,
) {
let mut ig = InstructionGroupBuilder::new(all_instructions);
// ...
ig.push(
Inst::new(
"atomic_cas",
r#"
Perform an atomic compare-and-swap operation on memory at `p`, with expected value `e`,
storing `x` if the value at `p` equals `e`. The old value at `p` is returned,
regardless of whether the operation succeeds or fails. `p` has the type of the target
word size, and `x` and `e` must have the same type and the same size, which may be any
integer type; note that some targets require specific target features to be enabled in order
to support 128-bit integer atomics. The type of the returned value is the same as the type
of `x` and `e`. This operation is sequentially consistent and creates happens-before edges
that order normal (non-atomic) loads and stores.
"#,
&formats.atomic_cas,
)
.operands_in(vec![
Operand::new("MemFlags", &imm.memflags),
Operand::new("p", iAddr),
Operand::new("e", AtomicMem).with_doc("Expected value in CAS"),
Operand::new("x", AtomicMem).with_doc("Value to be atomically stored"),
])
.operands_out(vec![
Operand::new("a", AtomicMem).with_doc("Value atomically loaded"),
])
.can_load()
.can_store()
.other_side_effects(),
);

SSAビルダー

IRビルダー

IRが値を出力しない場合、make_inst
で構築する。
IRが単一または複数の値を持つ場合、make_inst_results
が出力としてのSSA値を構築する。
各IRに定義されている”制約”を基に出力としてのSSA値が構築される。
target/debug/build/cranelift-codegen-d54d57767b252720/out/opcodes.rs
// Table of operand constraint sequences.
const OPERAND_CONSTRAINTS: [OperandConstraint; 83] = [ // cranelift\codegen\meta\src\gen_inst.rs:825
OperandConstraint::Same, // cranelift\codegen\meta\src\gen_inst.rs:832
OperandConstraint::Same, // cranelift\codegen\meta\src\gen_inst.rs:832
OperandConstraint::Same, // cranelift\codegen\meta\src\gen_inst.rs:832
OperandConstraint::Concrete(ir::types::I32), // cranelift\codegen\meta\src\gen_inst.rs:832
OperandConstraint::Same, // cranelift\codegen\meta\src\gen_inst.rs:832
OperandConstraint::LaneOf, // cranelift\codegen\meta\src\gen_inst.rs:832
OperandConstraint::Concrete(ir::types::I8X16), // cranelift\codegen\meta\src\gen_inst.rs:832
OperandConstraint::Concrete(ir::types::I8X16), // cranelift\codegen\meta\src\gen_inst.rs:832
OperandConstraint::Concrete(ir::types::I8X16), // cranelift\codegen\meta\src\gen_inst.rs:832
OperandConstraint::Same, // cranelift\codegen\meta\src\gen_inst.rs:832

テストに定義されているサンプル関数の構築

最適化の正当性検証については、ロードマップにSMTソルバについて言及されているものを見つけた
veri(多分short for verification)という内部クレートでeasy-smt
というクレートを使っている

- CraneliftのIRは実際に単一ではない
- CLIR(Cranelift IR)とVCode(Virtual-register Code)の2重になっている
- CLIRは単一のパスによってVCodeに下ろすことができる
- VCodeはSSAではなく、仮想レジスタによるターゲット固有とIRの1対1(あるいは1対多、多対1)に限りなく近い

命令選択にはISLE(Instruction Selection/Lowering Expressions)と呼ばれるDSL(Domain-Specific Language)が使われている

例えば[base + index*4 + 8]
のようなX86アドレッシングを考えてみる
これをIRに落とすと凡そ複数の些細なアドレス計算になる
v1 = imul_imm v_index, 4
v2 = iadd v_base, v1
v3 = iadd_imm v2, 8
v4 = load.i32 v3
逆にそれをターゲット固有(X86)のマシンコードに下ろすときにlower.isle
に記載されたマッチャーが働く

DLが少ないので怖いけどVSCodeの拡張でISLEハイライトに対応したものがある

CLIRにおける副作用について
- 副作用とは計算値の生成を超えた観測可能な効果を持つ操作
- 例えば特定のメモリアドレスを読む
Load
(.can_load()
)は明確で観測可能な副作用を持つ(e.g., アクセス違反でトラップする可能性やメモリ順序付けなど)
- 例えば特定のメモリアドレスを読む
- 副作用を持つ命令はプログラム状態に観測可能な効果があり、任意に並べ替えたり削除したりできず、正確性のために意味論的な順序を保持する必要がある
- CLIRは副作用をメタデータとして定義できる
-
.can_load()
,.can_store()
,.other_side_effects()
-

- 命令は副作用に基づいてローワリング中にカラー(
InstColor
)が割り当てられる。 - 同じカラーを持つすべての命令は、副作用を持つ操作によって分離されないことが保証される。

CLIRにおける制約について
- オペランド制約は命令の入力と出力オペランドに適用される制限を定義する
-
Same
: 複数にまたがってオペランドが同じ型を持つ -
LaneOf
: SIMD操作においてオペランドがベクトル型のレーン要素型と一致する必要がある -
Concrete
: オペランドが特定の具体的な型でなければならない - etc