Xir Passes

XIR Passes: Authoring Guide

This skill captures hard-won knowledge from implementing the CFG normalization pipeline. Read before touching anything under src/xir/passes/ or include/luisa/xir/passes/.

Layout & Registration

• Header: include/luisa/xir/passes/<name>.h
• Impl: src/xir/passes/<name>.cpp
• Register impl in src/xir/CMakeLists.txt (look for the passes/ block, ~line 80-90; alphabetical).
• Test: src/tests/unit/xir/test_xir_pass_<name>.cpp, registered in src/tests/CMakeLists.txt (look for test_xir_pass_* block).

Standard Pass Interface

Every pass exposes a <Name>Info POD with counters plus two entry points:

struct FooPassInfo {
    size_t did_something_count = 0u;
};

[[nodiscard]] LUISA_XIR_API FooPassInfo foo_pass_run_on_function(Function *function) noexcept;
[[nodiscard]] LUISA_XIR_API FooPassInfo foo_pass_run_on_module(Module *module, PassReport *report = nullptr) noexcept;

The function-level entry point should accept Function * (so it also works on external declarations) and use function->definition() to obtain a FunctionDefinition * before touching basic blocks. The module entry point iterates module->function_list() and dispatches by function->definition():

FooPassInfo foo_pass_run_on_module(Module *module, PassReport *report) noexcept {
    FooPassInfo info;
    for (auto *func : module->function_list()) {
        if (auto def = func->definition()) {
            info = foo_pass_run_on_function(func); // or operate directly on def
        }
    }
    if (report != nullptr) {
        report->set("did_something", info.did_something_count);
    }
    return info;
}

Some passes (e.g., sroa_pass_run_on_module, algebraic_simplify_pass_run_on_module) also take an options struct before PassReport *. Always consult the header for the exact signature.

PassPipeline and PassReport

Most module-level passes can write statistics into a PassReport:

PassReport report;
auto info = dce_pass_run_on_module(&m, &report);
for (auto &e : report.entries()) {
    // e.key, e.value
}

For end-to-end pipelines, prefer the canned pipelines in pass_pipeline.h:

auto pipeline = create_basic_optimization_pipeline({.enable_fast_math = false});
auto stats = pipeline.run(&m);
stats.log("my-pipeline");

Custom pipelines can be built with PassPipeline::add (single run) and PassPipeline::add_fixed_point (fixed-point sub-pipeline).

Comments

• Document non-obvious correctness invariants and pass-ordering boundaries where the code alone cannot explain why the ordering matters.
• Avoid comments that merely restate the next statement or preserve obsolete implementation history.
• Keep // namespace foo trailers after namespace closing braces.
• BDD (// given / when / then) is useful in tests when it clarifies the fixture and expected transform.

Core APIs

Module / Function

module->function_list()                          // iterable (NOT `functions()`)
func->is_definition()                            // true for kernel/callable, false for external
auto def = func->definition();                   // returns FunctionDefinition* (nullptr for external)
if (auto def = func->definition()) { ... }       // preferred pattern; never cast_or_null
def->body_block()                                // entry block (NEVER remove)
def->create_basic_block()                        // orphan block
def->basic_blocks()                              // ManagedIntrusiveList<BasicBlock>
def->traverse_basic_blocks(visitor)              // walks only reachable blocks from body_block

BasicBlock

block->instructions()                                  // ManagedIntrusiveList<Instruction>
block->instructions().empty()                          // always false if terminator present
block->instructions().front()                          // first inst
block->is_terminated()                                 // true when the last instruction is a terminator
block->terminator()                                    // last inst (may be nullptr if malformed/unterminated)
block->traverse_instructions(visitor)
block->traverse_predecessors(exclude_self, visit)      // visits via use list
block->traverse_successors(exclude_self, visit)        // visits terminator's target operands
block->remove_self()                                   // returns ManagedPtr<BasicBlock>; detaches from func block list

Constant detection

if (auto v = inst->condition(); v->isa<Constant>()) {
    auto c = static_cast<Constant*>(v);
    bool b = c->as<bool>();    // checks size; safe for bool
}

condition() is the getter on ConditionalBranchInst / IfInst. For other instruction kinds use the appropriate value getter (value(), operand(i), etc.).

Cast pattern

XIR does not have cast_or_null<> or LLVM-style cast<>. Use:

if (v->isa<SomeType>()) {
    auto s = static_cast<SomeType*>(v);
    ...
}

For instruction-tag switch: inst->derived_instruction_tag() returns DerivedInstructionTag::*.

Terminator Inventory & APIs

After Pipeline B destructure_cfg, only the unstructured terminators + SwitchInst + ReturnInst + UnreachableInst + RasterDiscardInst remain.

XIRBuilder

XIRBuilder b;
b.set_insertion_point(block);            // or block->instructions().front() etc.
b.br(target)                             // BranchInst
b.cond_br(cond, true_target, false_target)
b.if_(cond)                              // returns IfInst*; populate sub-blocks via if->true_block() etc.
b.loop()                                 // LoopInst*; fill prepare/body/update
b.simple_loop()                          // SimpleLoopInst*; fill body
b.ray_query_loop()                       // 0 args; query object only passed to ray_query_dispatch
b.ray_query_dispatch(query_value)        // inside dispatch_block
b.call(type, op, operands)               // typed call (read ops)
b.call(op, operands)                     // void call (write ops, e.g., RQ PROCEED)
b.return_(value)
b.unreachable_()
b.break_(target)                         // structured
b.continue_(target)                      // structured

For RQ primitive ops (include/luisa/xir/op.h ~line 170-187):

• RayQueryObjectReadOp::IS_TERMINATED, IS_TRIANGLE_CANDIDATE, IS_PROCEDURAL_CANDIDATE, ...
• RayQueryObjectWriteOp::PROCEED, COMMIT_TRIANGLE, COMMIT_PROCEDURAL, TERMINATE

Mutation Idiom: Two-Phase Collect-Rewrite

You cannot reliably mutate the instruction list while iterating it. Pattern from lower_break_continue.cpp:

luisa::vector<IfInst*> to_lower;
def->traverse_basic_blocks([&](BasicBlock *bb) {
    if (auto t = bb->terminator(); t && t->isa<IfInst>()) {
        to_lower.push_back(static_cast<IfInst*>(t));
    }
});

for (auto if_inst : to_lower) {
    auto bb = if_inst->parent_block();
    auto true_b = if_inst->true_block();
    auto false_b = if_inst->false_block();
    auto cond = if_inst->condition();
    if_inst->remove_self();
    XIRBuilder b; b.set_insertion_point(bb);
    b.cond_br(cond, true_b, false_b);
}

For passes that grow the worklist (e.g., RayQueryLoop → new LoopInst → re-process), wrap in a fixed-point loop:

bool changed = true;
while (changed) {
    changed = false;
    luisa::vector<...> worklist;
    def->traverse_basic_blocks(...);
    if (!worklist.empty()) { changed = true; rewrite(); }
}

Constant Folding / Branch Retargeting

To redirect every reference to block from in a terminator to point at to:

auto retarget = [&](Instruction *term, BasicBlock *from, BasicBlock *to) {
    switch (term->derived_instruction_tag()) {
        case DerivedInstructionTag::BRANCH: {
            auto br = static_cast<BranchInst*>(term);
            if (br->target_block() == from) br->set_target_block(to);
            break;
        }
        case DerivedInstructionTag::CONDITIONAL_BRANCH: {
            auto cb = static_cast<ConditionalBranchInst*>(term);
            if (cb->true_target() == from) cb->set_true_target(to);
            if (cb->false_target() == from) cb->set_false_target(to);
            break;
        }
        case DerivedInstructionTag::SWITCH: {
            auto sw = static_cast<SwitchInst*>(term);
            if (sw->default_block() == from) sw->set_default_block(to);
            for (size_t i = 0; i < sw->case_count(); ++i) {
                if (sw->case_block(i) == from) sw->set_case_block(i, to);
            }
            break;
        }
        default: break;
    }
};

Reachability / Dead Block Removal

def->traverse_basic_blocks(...) already walks only reachable blocks from body_block(). To remove unreachable blocks:

luisa::unordered_set<BasicBlock*> reachable;
def->traverse_basic_blocks([&](BasicBlock *bb) { reachable.insert(bb); });
luisa::vector<BasicBlock*> dead;
for (auto bb : def->basic_blocks()) {
    if (!reachable.contains(bb)) dead.push_back(bb);
}
for (auto bb : dead) bb->remove_self();

Always preserve def->body_block() — never remove it even if it looks empty.

Test Patterns (Boost.UT / doctest?)

XIR unit tests live in src/tests/unit/xir/. Check existing test_xir_pass_*.cpp for framework; they use the project's chosen harness (was boost::ut last checked, see /test skill).

Key test fixtures:

Module m;
auto *k = m.create_kernel();                            // KernelFunction*
auto body = k->create_body_block();                     // entry BB
// or:
auto *c = m.create_callable(Type::of<float>());         // CallableFunction*
auto def = static_cast<FunctionDefinition*>(k);         // both kernel/callable are FunctionDefinitions

XIRBuilder b;
b.set_insertion_point(body);
// build IR ...
b.return_void();

auto info = my_pass_run_on_function(def);

Reachability gotcha: traverse_basic_blocks only visits blocks reachable from body_block. If you build orphan blocks for a test, you must wire them up via br/cond_br from body_block or the pass will see nothing. Trick: m.create_constant_one(Type::of<bool>()) + cond_br(true_const, target, other) to force reachability.

Pipeline B Status (CFG Normalization)

Master plan: src/xir/passes/CFG_NORMALIZATION_PLAN.md.

Note: src/xir/passes/CFG_NORMALIZATION_PLAN.md is the historical master plan; the table above reflects the current implementation state.

destructure_cfg lowerings (reference)

• IfInst → cond_br(cond, true, false); merge_block reachable via inner brs.
• LoopInst → br(prepare).
• SimpleLoopInst → br(body).
• BreakInst / ContinueInst → br(target).
• RayQueryLoopInst → emit LoopInst{prepare→body, body: PROCEED + cond_br cascade on IS_TERMINATED→merge / IS_TRIANGLE_CANDIDATE→on_surface / IS_PROCEDURAL_CANDIDATE→on_procedural / else→update, update→prepare}; rewrite child br dispatch_block → br update_block; remove orphaned RayQueryDispatchInst. New LoopInst destructured on next fixed-point iteration.
• SwitchInst preserved as-is; recursion handled naturally by traverse_basic_blocks.

simplify_cfg ops

1. Constant cond_br fold → br.
2. Empty-block jump-threading (block with only a br C terminator; redirect all preds; never remove body_block).
3. Unreachable block removal (collect reachable from body_block, remove rest).
4. Fixed-point until no change.
5. Counters: folded_constant_cond_br_count, threaded_empty_block_count, merged_straight_line_count, removed_unreachable_block_count.

Pitfalls Catalogue

• ❌ cast_or_null<T>(v) — doesn't exist. Use isa<T> + static_cast.
• ❌ set_true_block / set_false_block on ConditionalBranchInst — wrong names. Asymmetric: getters are true_block() / false_block(), setters are set_true_target / set_false_target.
• ❌ module->functions() — wrong. Use module->function_list().
• ❌ Assuming every Function * is a definition and casting with static_cast<FunctionDefinition*>(func) — unsafe. Use func->definition(); it returns nullptr for external functions.
• ❌ Forgetting PassReport *report on module entry points — most passes now take Module *module, PassReport *report = nullptr. Omitting it compiles, but pass pipelines and tests may expect report entries.
• ❌ inst->cond() — does not exist. The condition getter is condition() (on ConditionalBranchInst / IfInst).
• ❌ b.ray_query_loop(query) — wrong; takes 0 args. Pass query to ray_query_dispatch.
• ❌ Mutating instructions while iterating — always two-phase collect-rewrite.
• ❌ Removing body_block() — never. Even if empty, it must stay.
• ❌ Building orphan test blocks without wiring reachability — traverse_basic_blocks will skip them silently.
• ❌ Forgetting fixed-point loop when transformation creates new candidates (RayQueryLoop → new LoopInst).
• ❌ Touching SwitchInst case-block contents structurally — Pipeline B preserves switches; only fold/thread within cases.
• ❌ Calling LoopInst::condition() — does not exist. Inspect the prepare terminator first. AST-canonical loops use cond_br(cond, body, merge), while internally exiting loops recovered by restructure_cfg may use br(body). Only cast to ConditionalBranchInst after checking the tag. There is no set_condition; rewrite the prepare-block terminator instead.
• ❌ Restructuring CFG with live PhiInst nodes — splitting/inserting blocks (preheaders, latches, exit stubs) invalidates phi incoming_blocks. Run reg2mem_pass_run_on_module before restructure_cfg_pass_run_on_module so the input is phi-free; assert this as a precondition.
• ❌ Computing post-dominators without a virtual exit — multi-sink CFGs (ReturnInst, UnreachableInst, RasterDiscardInst in different blocks) yield wrong/null ipostdoms for blocks whose successors reach different sinks. Add a synthetic virtual exit that all sinks point to before running the iterative ipostdom algorithm.
• ❌ Running generic cleanup (including DCE) between restructure_cfg and SSA recovery in a structured backend pipeline — generic cleanup belongs in the raw/destructured CFG interval, before restructuring. DCE preserves a constant-false canonical LoopInst::prepare_block() conditional branch, but that safeguard does not authorize post-restructure cleanup: other structured role arms can still be folded or erased. For native SPIR-V, use the backend's targeted inactive-role payload cleanup, then run mem2reg immediately to recover SSA. A generic pipeline that truly needs later cleanup must first lower or otherwise protect every structured role and reverify the resulting boundary.
• ❌ Replacing an enclosing region boundary with a nested IfInst/SwitchInst merge during recursive CFG traversal — lowered break/continue edges may bypass the local merge and escape the enclosing region. Carry the immutable outer boundary alongside the current local merge and stop at either.
• ❌ Repairing reverse-autodiff SSA before its generated backward block is reachable — install backward_marker_block -> backward_block, replace the AutodiffScopeInst with parent -> entry, and only then call reg2mem_pass_repair_cross_block_rvalue_uses_on_function. The narrow repair snapshots branch-local primal rvalues used by mirrored backward control flow without lowering unrelated Phi nodes. It deliberately ignores Phi edge operands and lvalue definitions; downstream final mem2reg must consume the typed CROSS_BLOCK spills before codegen.
• ❌ Treating every instruction that names itself as malformed — a loop-carried PhiInst may legally use itself as the incoming value on a backedge to preserve the previous iteration's value. SPIR-V represents this directly with a self-referencing OpPhi. fix_self_referential repairs malformed aggregate INSERT cycles and must leave legal Phi self-references alone.
• ❌ Spending a fixed-point round on one independent candidate — a round budget is a cross-pass cycle guard, not a substitute for draining a phase's finite backlog. One-site rewrites must use a phase-local worklist, recompute invalidated analyses after every mutation, and detect repeated site identities as non-convergence. A fixed cap smaller than the number of legal candidates produces false failures; callers must inspect RestructureCFGInfo::succeeded() before using the result.
• ❌ Using OpCopyMemory on OpTypeRayQueryKHR in SPIR-V emission — forbidden since Rev 15. Instead, remap _value_map[store->variable()] = val so subsequent loads resolve to the source variable directly.
• ❌ Trusting src/xir/passes/CFG_NORMALIZATION_PLAN.md as a task tracker — it is the historical design doc and contains unchecked items that are already implemented (e.g., early_return_elimination, restructure_cfg). Use the table above and the actual headers/sources as the source of truth.

Memory Effects & Instruction Purity

Optimization passes (GVN, DCE, SCCP) must respect memory effects. Instructions fall into three categories:

Pure (safe to value-number, CSE, reorder, DCE if unused)

Memory-reading (safe to DCE if unused, NOT safe to reorder past writes or value-number without alias analysis)

Memory-writing / side-effecting (NEVER DCE, NEVER reorder past other writes/reads to same location)

Implications for pass authors

1. GVN: only value-number pure instructions + RESOURCE_QUERY. RESOURCE_READ and LOAD require memory dependency analysis (not yet implemented) to prove no intervening write.

2. DCE: remove instructions with use_list().empty() ONLY if they are pure or memory-reading. Never remove writes, atomics, calls to definitions, prints, or asserts.

3. SCCP: only fold ARITHMETIC on constant operands. Branch elimination is safe (replaces cond_br with br) but must call term->remove_self() BEFORE builder.set_insertion_point(block) — otherwise the builder targets the tail sentinel and asserts.

4. Code motion: pure instructions can be hoisted/sunk freely. Reads can be hoisted past other reads but not past writes to the same resource. Writes cannot be reordered with respect to other accesses to the same resource.

5. is_safe_to_remove (used by GVN/DCE cleanup): checks use_list().empty() + instruction tag whitelist. Current whitelist: PHI, ALLOCA, LOAD, GEP, ARITHMETIC, CAST, CLOCK, RAY_QUERY_OBJECT_READ, RESOURCE_QUERY, RESOURCE_READ, AUTODIFF_INTRINSIC(GRADIENT).

Checking purity in code

Use get_memory_info() from helpers.h:

#include "helpers.h"  // from src/xir/passes/

auto info = get_memory_info(inst);
info.is_pure()                    // no memory effects, not volatile
info.reads_memory()               // LOCAL or GLOBAL read
info.writes_memory()              // LOCAL or GLOBAL write
info.is_removable_if_unused()     // safe to DCE (no writes, not volatile)
info.is_safe_to_value_number()    // safe for GVN/CSE (pure only)
info.scope                        // NONE, LOCAL, GLOBAL
info.effects                      // NONE, READ, WRITE, READ_WRITE
info.is_volatile                  // barriers, prints, asserts — never remove/reorder

MemoryScope::LOCAL = alloca/load/store (function-private memory). MemoryScope::SHARED = workgroup-shared memory (thread_group barriers/ops). MemoryScope::GLOBAL = buffers, textures, atomics.

Two instructions with different scopes cannot alias. Two LOCAL instructions alias only if they trace to the same alloca (use trace_pointer_base_local_alloca_inst). SHARED memory is visible to all threads in a workgroup — never reorder across barriers.

Build & Test Commands

Create the build directory with the project's bootstrap script if it does not exist:

python bootstrap.py cmake -f cuda -c -o cmake-build-release

Then use the CMake build directory:

# Build XIR library only (fast iteration)
cmake --build cmake-build-release --target luisa-compute-xir -j

# Build one specific pass test
cmake --build cmake-build-release --target test_xir_pass_destructure_cfg -j

# Run the test binary directly
cmake-build-release/bin/test_xir_pass_destructure_cfg

# Or run all XIR pass tests via ctest
ctest --test-dir cmake-build-release -R xir_pass --output-on-failure

Build dir convention: cmake-build-release. On CI you may see build-cmake-verify; the commands above work there too if you substitute the directory name.

LLVM Equivalents

When debugging or implementing an XIR pass, the LLVM project has similar passes for reference. Below is the mapping from XIR pass file to the closest LLVM implementation(s).

Reading LLVM sources for XIR pass debugging

When an XIR pass produces incorrect IR:

1. Look up the XIR pass in the table above.
2. Open the matching LLVM file(s), if not found, ask user.
3. Read the LLVM implementation for the algorithm (e.g., how SROA splits allocas, how StructurizeCFG builds regions).
4. Compare with the XIR implementation in src/xir/passes/<name>.cpp. The XIR passes are often simplified versions of the LLVM algorithms.
5. For passes with no LLVM equivalent (ray query, break/continue lowering, self-referential fix), the XIR pass is the authoritative reference.