Convert Julia's unstructured SSA IR into structured control flow representation (SCF-style operations).
julia> using IRStructurizer
julia> f(x) = x > 0 ? x + 1 : x - 1
julia> code_structured(f, Tuple{Int})
1-element Vector{Pair{StructuredIRCode, DataType}}:
StructuredIRCode(
│ %1 = intrinsic Base.slt_int(0, _2)::Bool
│ %7 = if %1 -> Nothing
│ ├ then:
│ │ %3 = intrinsic Base.add_int(_2, 1)::Int64
│ │ return %3
│ ├ else:
│ │ %5 = intrinsic Base.sub_int(_2, 1)::Int64
│ └ return %5
) => Int64
julia> sci, ret_type = code_structured(f, Tuple{Int}) |> onlyGet structured IR for function f with argument types argtypes.
validate: ThrowUnstructuredControlFlowErrorif unstructured control flow remainsexceptions: how to treat try/catch, as forStructuredIRCode
Construct structured IR from Julia's IRCode (obtained via Base.code_ircode).
structurize: Convert unstructured control flow (GotoNode/GotoIfNot) into structured operationsvalidate: ThrowUnstructuredControlFlowErrorif unstructured control flow remainsexceptions::error(default) throwsUnstructuredControlFlowErroron try/catch;:structuredlifts it toTryOp(see Exceptions). Withstructurize=falseit is not looked at: the flat IR keeps itsEnterNodes
Iterate over instructions in a block as Inst objects. Each Inst bundles an SSA index, statement, and type.
for inst in instructions(block)
inst[:stmt] # underlying statement (Expr, ControlFlowOp, etc.)
inst[:type] # Julia type of the instruction result (or value_type(inst))
inst[:flag] # IR_FLAG_* bitmask (see Compiler/src/optimize.jl)
inst.block # containing block
endGet or set the block's terminator (ReturnNode, YieldOp, ContinueOp, BreakOp, ConditionOp, LeaveOp, or nothing).
Get the carried-value operands of a terminator. Provides uniform access regardless of terminator type (.values for YieldOp/ContinueOp/BreakOp/LeaveOp, .args for ConditionOp).
Get the values flowing into a control flow operation from the parent scope:
IfOp→[condition]ForOp→[lower, upper, step, init_values...]WhileOp→copy(init_values)LoopOp→copy(init_values)TryOp→[scope](or empty)
Extract data operands from an instruction's statement. Handles Expr (:call/:invoke/:new/:splatnew), PiNode, and ControlFlowOp. Returns Any[] for unknown types. Extensible via operands(::Block, s::MyType) for domain-specific IR nodes.
Get the block arguments (loop-carried values, induction variables).
Get the immediate sub-blocks of a control flow operation (non-recursive, one level only).
Navigate the block tree. parent returns the containing block (or StructuredIRCode for the entry block). root walks up to the StructuredIRCode.
Walk all instructions in the IR, calling f(inst, block) for each. The callback returns a control symbol:
:advance— continue normally (default if callback returnsnothing):skip— don't recurse into this op's sub-blocks (preorder only):interrupt— stop the walk immediately
Supports :preorder (default) and :postorder via the order keyword.
Pre-order traversal of all blocks, recursing into nested control flow ops.
Find the block containing a given instruction.
Collect the block's own terminator plus all loop exits (ContinueOp/BreakOp) reachable through nested IfOps. YieldOp and ConditionOp are captured by their enclosing IfOp/WhileOp and not propagated outward.
Check whether a statement is a :call or :invoke expression.
Extract the resolved function and operands from a call expression. Resolves GlobalRef to the bound value. Returns nothing for non-call statements or unresolvable functions.
Get the raw function reference from a call expression without resolving GlobalRef.
Get the operand arguments of a call expression (excludes the function reference).
Find the instruction that defines an SSA value. The instruction's block field gives the containing block. Performs a linear scan — for repeated queries, use defs(root).
Pre-built index for O(1) definition lookup. Analogous to uses(block) which returns a UseIndex.
idx = defs(sci)
inst = def(idx, SSAValue(3))
if inst !== nothing
inst[:stmt] # the statement
inst.block # the containing block
endAll insertion functions auto-allocate fresh SSA indices.
Append or prepend an instruction.
Insert relative to an existing Inst or SSAValue.
Move an instruction from its current block to before/after target in target's block. The instruction retains its SSA index. Analogous to MLIR's Operation::moveBefore/moveAfter.
Remove an instruction from a block.
Remove all instructions from the block body, preserving args, terminator, and parent.
Check if a value is defined in this block. Returns true for SSAValues in the body and BlockArguments in the args; false for everything else (constants, Arguments, etc.).
Check whether a value is defined outside a block (and all its descendants), or outside a loop operation's regions. The loop-op overloads handle values like ForOp.iv_arg that aren't in the body's block args. Analogous to MLIR's LoopLikeOpInterface::isDefinedOutsideOfLoop.
Access or mutate the entry at an SSA index. block[idx] returns the Instruction handle (throws KeyError if absent — pair with haskey(block, idx)). block[idx] = nt accepts any NamedTuple subset of (stmt, type, flag); fields not mentioned are preserved. So block[idx] = (type=Float64,) overwrites only the type, keeping stmt and flag.
Read or write a single field of an instruction's live entry. Modeled on Core.Compiler.Instruction (Compiler/src/ssair/ir.jl). Reads and writes go through the block's storage, so inst[:type] = T; inst[:type] round-trips. inst[:ssa_idx] and inst[:block] are also exposed.
When swapping :stmt for one with a different opcode, the old flag bits describe the OLD op and may be stale for the new one. Pass inst[:flag] = IR_FLAG_NULL (or block[idx] = (stmt=…, flag=IR_FLAG_NULL) for an atomic write), mirroring LLVM's "fresh instruction, then opt-in copyIRFlags" pattern.
Add a new BlockArg to a block.
Build an index of all use sites in a block (recursively). The returned UseIndex supports idx[val] → Vector{UseRef} and haskey(idx, val).
Keys can be SSAValue, BlockArg, Argument, Inst, or plain Int (treated as SSA index).
Find all use sites of val in a block. Linear scan — for repeated queries, prefer uses(block).
Replace all uses of old with new_val (recursively).
Get a view over a ForOp/LoopOp/WhileOp's carried values. Encapsulates the positional coupling between init_values, body BlockArgs, and terminator values.
Supports iteration, indexed access, filter!, deleteat!, and push!.
Each element of a LoopCarries is a CarryRef with read/write access:
init_value(c)/init_value!(c, val)— the value passed into the loopbody_arg(c)— theBlockArgvisible inside the loop body (beforeregion forWhileOp)after_arg(c)— theafter-regionBlockArg(WhileOponly)term_value(c, terminator)/term_value!(c, terminator, val)— the value passed back at aContinueOp,BreakOp,YieldOp, orConditionOp
filter!(pred, carries)→Dict{Int,Int}— keep carries wherepred(::CarryRef)is truedeleteat!(carries, indices)→Dict{Int,Int}— remove carries at given indicespush!(carries, init_val, body_arg_type)→CarryRef— append a new carry
All three return (or produce) an old→new index mapping and maintain consistency across init values, block args, and all reachable terminators.
The structurizer turns Julia's unstructured SSA IR (GotoNode, GotoIfNot, PhiNode)
into nested control flow operations: IfOp, ForOp, WhileOp, and LoopOp. It uses the
mutate-then-lift approach of MLIR's CFGToSCF pass (Bahmann et al. 2015).
code_ircode → IRCode
│ ingest (structurize/ingest.jl)
▼
MCFG explicit-edge CFG: block args + per-edge operands
│ normalize_cf! (structurize/normalize.jl)
▼
MCFG (single-entry, reducible)
│ lift_mcfg → structurize (structurize.jl, walk.jl, loops.jl)
▼
StructuredIRCode nested Blocks with IfOp/ForOp/WhileOp/LoopOp
│ promote_loops! (structurize/promote.jl)
▼
StructuredIRCode (loops classified)
Julia's IRCode is dense (an SSA value is its own position) and falls through from a
GotoIfNot to the next block on a true condition, so you cannot redirect an edge in place.
ingest reads it once into an MCFG. There, each block has a stable id, explicit block
arguments, and a terminator whose edges each carry one operand per target argument. Block
arguments and per-edge operands replace phi nodes, so the value a predecessor P passes to
block B's k-th argument is just the operand on the edge from P to B. Redirecting an edge
stays local.
The lift only handles single-entry, reducible regions, so normalize_cf! runs first and
rewrites everything else into that shape. Several situations send a block more than one
entry edge: irreducible loop headers, multi-exit loops, and short-circuit continuations
among them. Each is routed through a single edge multiplexer (EdgeMux), an inserted entry
block that picks the real target from a discriminator argument. The pass repeats to a
fixpoint, so a region reaches the lift only once it is single-entry.
structurize_region! walks the normalized MCFG and emits structured ops. A natural loop
becomes a LoopOp whose body re-enters with ContinueOp and exits with BreakOp. A branch
whose arms reconverge becomes an IfOp, each arm a nested region, with merge values passed
out through YieldOp. Phi results become BlockArguments, and the value each predecessor
feeds in reads off its outgoing edge.
The lift emits only LoopOp. The promote_loops! post-pass rewrites the ones it
recognizes: a loop driven by an integer induction variable with a constant step becomes a
ForOp, and a loop that tests its condition before the body becomes a WhileOp. The rest
stay LoopOp.
By default an EnterNode (try/catch, try/finally, @with) throws
UnstructuredControlFlowError. With exceptions=:structured, an EnterNode and its
catch block become a TryOp at the enter's SSA index. Its
body region is the protected code, and its handler region is the catch block,
which runs with the handler popped. The catch block's PhiCNodes become handler
block arguments, and TryOp.upsilons lists the UpsilonNodes that feed each one.
:leave disappears: leaving the body pops the handler. The body ends in a
YieldOp, and a nested region that exits it uses LeaveOp, which is like
BreakOp but for the innermost try body. :the_exception and :pop_exception %t
stay as statements on Julia's exception stack.
Regions come from a handler-stack dataflow, and normalize_cf! gives each try a
single continuation before the other passes run. See
docs/exceptions.md for the design and the mapping to Wasm
try_table.
The reverse direction (unstructurize.jl) lowers a StructuredIRCode back to IRCode
through IRCode(sci). It is there for the tests, which round-trip the structurizer against
Julia's own IR. cuTile consumes the StructuredIRCode directly.
This package started from Cédric Belmant's SPIRV.jl structurization code. The structurizer now follows MLIR's CFGToSCF pass (Bahmann et al. 2015).