xir-passes

name	xir_passes
description	XIR transformation pass authoring under src/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

Terminator	Header	Key API
BranchInst (br)	instructions/branch.h	target_block(), set_target_block(BasicBlock*)
ConditionalBranchInst (cond_br)	instructions/branch.h	Getters: condition(), true_block(), false_block(). Setters: set_true_target / set_false_target (asymmetric naming — getter says block, setter says target)
SwitchInst	instructions/switch.h	value(), default_block(), case_count(), case_value(i), case_block(i), set_case_block(i, bb), set_default_block(bb), add_case(v, bb)
ReturnInst	instructions/return.h	value()
UnreachableInst	instructions/unreachable.h	none
RasterDiscardInst	instructions/raster_discard.h	none
IfInst (structured)	instructions/if.h	condition(), true_block(), false_block(), merge_block()
LoopInst (structured)	instructions/loop.h	prepare_block(), body_block(), update_block(), merge_block(). No condition() getter. AST lowering normally creates prepare: cond_br(cond, body, merge), but restructure_cfg may create an internally exiting natural loop with . Both retain distinct prepare/body/update/merge roles. Setters: , , . Creators: , , .

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.

Pass	Status	File
Pipeline A lower_break_continue	✅ done (12 tests)	lower_break_continue.{h,cpp}
Pipeline A lower_ray_query_loop	✅ existing (lowers to RayQueryPipelineInst — NOT reusable for Pipeline B)	lower_ray_query_loop.{h,cpp}
Pipeline A lower_ray_query_loop_to_loop	✅ done (lowers to structured LoopInst + nested IfInst dispatch)	lower_ray_query_loop_to_loop.{h,cpp}
Pipeline A early_return_elimination	✅ done (implemented + unit tests)	early_return_elimination.{h,cpp}
Pipeline B Pass 1 destructure_cfg	✅ done (12 tests, 46 asserts)	destructure_cfg.{h,cpp}
Pipeline B Pass 2 simplify_cfg	✅ done (8 tests, 22 asserts)	simplify_cfg.{h,cpp}
Pipeline B Pass 3 restructure_cfg	✅ done (unit tests)	restructure_cfg.{h,cpp}
Structured switch	✅ SwitchInst is preserved; raw multi-way CFG uses IndexedBranchInst and restructure_cfg reconstructs the merge	switch.{h,cpp}, indexed_branch.{h,cpp}
convergence_region	✅ done (region analysis used by restructure_cfg)	convergence_region.{h,cpp}
early_cse	✅ done (local common subexpression elimination)	early_cse.{h,cpp}
pass_pipeline	✅ done (driver + canned pipelines)	pass_pipeline.{h,cpp}
Round-trip Pipeline B test	✅ verified (path_tracing_cutout PSNR>30)	via test_path_tracing_cutout vk

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 . Run before so the input is phi-free; assert this as a precondition.

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)

Tag	Examples
ARITHMETIC	all ops — no memory side effects
CAST	all cast ops
GEP	pointer arithmetic only, no dereference
RESOURCE_QUERY	buffer_size, texture_size — read-only metadata
CLOCK	hardware timer read — treated as a memory read (non-deterministic, not safe to value-number or reorder across loop iterations)

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

Tag	Examples
LOAD	local alloca/GEP load
RESOURCE_READ	buffer_read, texture_read, byte_buffer_read
RAY_QUERY_OBJECT_READ	IS_TERMINATED, COMMITTED_HIT, etc. — reads mutable per-thread ray query state that changes after PROCEED/COMMIT/TERMINATE

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

Tag	Examples
STORE	local alloca/GEP store
RESOURCE_WRITE	buffer_write, texture_write, byte_buffer_write
CALL (to definitions)	may have arbitrary side effects
ATOMIC	read-modify-write
PRINT	observable side effect
ASSERT / ASSUME	control flow / UB
AUTODIFF_INTRINSIC (non-GRADIENT)	tape manipulation

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).

XIR Pass	LLVM Equivalent(s)	Notes
aggregate_field_bitmask	—	XIR-specific aggregate field bit-range analysis.
algebraic_simplify	llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp (and siblings)	Peephole algebraic simplifications; also see AggressiveInstCombine.
alias_analysis	llvm/lib/Analysis/BasicAliasAnalysis.cpp	Basic and type-based alias analysis.
autodiff	—	XIR-specific autodiff pass. Reverse mode closes the generated CFG with a narrow cross-block-rvalue reg2mem repair so the pass returns dominance-valid XIR.
call_graph	llvm/lib/Analysis/CallGraph.cpp	Call-graph construction and SCC passes.
const_fold	llvm/lib/Analysis/ConstantFolding.cpp	Constant folding of instructions and intrinsics.
convergence_region	—	XIR-specific convergence-region / region-of-interest analysis used by restructure_cfg.
cvp	llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp	Correlated value propagation (range/branch info).
dce	llvm/lib/Transforms/Scalar/DCE.cpp	Standard dead-code elimination. Also see ADCE.cpp, BDCE.cpp, GlobalDCE.cpp.
dead_arg_elim	llvm/lib/Transforms/IPO/DeadArgumentElimination.cpp	Remove unused arguments from internal functions.
dead_store_elimination	llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp	Memory-write DSE (FastDSE / ClassicDSE).
destructure_cfg	llvm/lib/Transforms/Scalar/StructurizeCFG.cpp	XIR: structured → unstructured. LLVM does the inverse (unstructured → structured). Also see .

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.