Open14

Cranelift IR

kkent030315kkent030315

https://cranelift.dev/

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

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(),
    );

https://github.com/bytecodealliance/wasmtime/blob/10d2cbc59d35b14c3027a8542f636c591b2ec96b/cranelift/codegen/meta/src/shared/instructions.rs

kkent030315kkent030315
kkent030315kkent030315

https://github.com/bytecodealliance/wasmtime/blob/10d2cbc59d35b14c3027a8542f636c591b2ec96b/cranelift/frontend/src/frontend.rs#L114-L122

IRが値を出力しない場合、make_instで構築する。

IRが単一または複数の値を持つ場合、make_inst_resultsが出力としてのSSA値を構築する。

https://github.com/bytecodealliance/wasmtime/blob/10d2cbc59d35b14c3027a8542f636c591b2ec96b/cranelift/codegen/src/ir/dfg.rs#L1008-L1047

各IRに定義されている”制約”を基に出力としてのSSA値が構築される。

https://github.com/bytecodealliance/wasmtime/blob/10d2cbc59d35b14c3027a8542f636c591b2ec96b/cranelift/codegen/src/ir/instructions.rs#L780-L788

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

https://github.com/bytecodealliance/wasmtime/blob/10d2cbc59d35b14c3027a8542f636c591b2ec96b/cranelift/codegen/src/ir/instructions.rs#L873-L911

kkent030315kkent030315

最適化の正当性検証については、ロードマップにSMTソルバについて言及されているものを見つけた
https://github.com/bytecodealliance/rfcs/blob/main/accepted/cranelift-roadmap-2022.md#formal-verification

veri(多分short for verification)という内部クレートでeasy-smtというクレートを使っている

https://github.com/bytecodealliance/wasmtime/tree/10d2cbc59d35b14c3027a8542f636c591b2ec96b/cranelift/isle/veri

kkent030315kkent030315
kkent030315kkent030315

例えば[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に記載されたマッチャーが働く

kkent030315kkent030315

CLIRにおける副作用について

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

CLIRにおける制約について

  • オペランド制約は命令の入力と出力オペランドに適用される制限を定義する

https://github.com/bytecodealliance/wasmtime/blob/0f36d5dbe6e358636b110b669146fbb97c25f5c9/cranelift/codegen/src/ir/instructions.rs#L860-L870

  • Same: 複数にまたがってオペランドが同じ型を持つ
  • LaneOf: SIMD操作においてオペランドがベクトル型のレーン要素型と一致する必要がある
  • Concrete: オペランドが特定の具体的な型でなければならない
  • etc