Documentation
¶
Overview ¶
Package ssabuild constructs pruned, minimal SSA form for a single function while the caller walks a structured AST, following Braun, Buchwald, Hack et al. "Simple and Efficient Construction of SSA Form" (CC 2013).
Why this package exists ¶
A frontend that lowers into one block with a flat variable->value environment drops branch bodies, cannot model loop-carried values, and never exercises the engine's dominator-based guard precision. This package generalizes that env map into a per-block map of current definitions with PHI nodes inserted on demand, so a frontend can emit a real CFG (blocks + preds/succs + OP_CODE_IF/JUMP/PHI) byte-for-byte the shape the Go frontend emits and the taint engine consumes. It depends only on the gIR value type (pkg/ir/v1) and knows nothing about any source language.
The algorithm (Braun et al.) ¶
SSA is built during the AST walk, not by a separate dominance-frontier pass:
- WriteVariable(name, block, value) records, for a source-level variable, the value that is current at the end of (so far) that block.
- ReadVariable(name, block) returns the value current in that block. If the block has a local definition it is returned directly. Otherwise the value must come from the block's predecessors (readVariableRecursive): a SEALED block with one predecessor forwards that predecessor's value; a SEALED block with >=2 predecessors gets a fresh operandless PHI (recorded immediately to break cycles), then one operand per predecessor, then removeTrivialPhi; an UNSEALED block (a loop header whose back-edge predecessors are not yet known) gets an "incomplete" PHI that is filled in later when the block is sealed.
- Seal(block) is called once ALL of a block's predecessors are known. It fills every incomplete PHI of that block with operands and runs removeTrivialPhi. Loop headers are created, their body built (which reads the loop variables through the header and parks incomplete PHIs), and then sealed once the back-edge is wired — this is how loop-carried values get their PHIs with no dominance computation.
- removeTrivialPhi eliminates a PHI all of whose operands are the same value (or self-references): it is replaced by that single value and every user (including other PHIs, which are then re-checked) is rewritten. This keeps the result minimal.
CFG shape and determinism ¶
SetIf / SetJump set a block's terminator and, as a side effect, record the CFG edges (a block is added as a predecessor of each successor). Finish() materializes []*ir.BasicBlock: PHIs first (parallel operands + "b<idx>" predecessor labels, matching the Go frontend's blockName), then the caller's body instructions (AddInstr), then the terminator (OP_CODE_IF with successors ordered [trueTarget, falseTarget]; OP_CODE_JUMP; or none for a block that just returns). Block ids are sequential ints (BasicBlock.Index). All map iteration is done over sorted keys, so output is byte-stable across runs.
A function with no branches produces exactly ONE block (no PHIs, no terminator inserted by the builder), so straight-line handlers keep the engine's single-block linear fast path and cost nothing extra.
Index ¶
- func Global(name string) *ir.Value
- func Nil() *ir.Value
- func Reg(name string) *ir.Value
- func SetKwargMarker(inst *ir.Instruction, name string, v *ir.Value)
- func Str(s string) *ir.Value
- type BlockID
- type Builder
- func (b *Builder) AddInstr(block BlockID, inst *ir.Instruction)
- func (b *Builder) BodyLoop(cur *BlockID, terminated *bool, lowerBody func(), lowerCond func() *ir.Value)
- func (b *Builder) Finish() []*ir.BasicBlock
- func (b *Builder) HeaderLoop(cur *BlockID, terminated *bool, lowerCond func() *ir.Value, lowerBody func())
- func (b *Builder) IfDiamond(cur *BlockID, terminated *bool, cond *ir.Value, lowerThen, lowerElse func()) (thenEnd, elseEnd, merge BlockID)
- func (b *Builder) NewBlock() BlockID
- func (b *Builder) ReadVariable(name string, block BlockID) *ir.Value
- func (b *Builder) Seal(block BlockID)
- func (b *Builder) SetIf(block BlockID, cond *ir.Value, trueBlk, falseBlk BlockID)
- func (b *Builder) SetJump(block BlockID, target BlockID)
- func (b *Builder) WriteVariable(name string, block BlockID, value *ir.Value)
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func SetKwargMarker ¶
func SetKwargMarker(inst *ir.Instruction, name string, v *ir.Value)
SetKwargMarker stamps inst as a `builtin.kwarg(<name>, <value>)` marker: the intrinsic a frontend emits to tag a keyword argument with the name it was passed under, since gIR carries positional arguments only.
TWO channels, and dropping either fails silently. Operands is what the engine's markTaintFromOperands reads, and builtin.kwarg is an intrinsic propagator, so without it every `f(x=tainted)` loses its taint. Call.Args is what unwrapKwarg reads to give a rule guard `kwargs.<name>`, so without it a guard can see that SOME argument is set but not which. Shared so the pairing is stated once rather than re-derived per frontend.
Types ¶
type BlockID ¶
type BlockID int
BlockID identifies a basic block within one Builder. Ids are sequential ints starting at 0 (the order NewBlock is called), and become BasicBlock.Index.
type Builder ¶
type Builder struct {
// contains filtered or unexported fields
}
Builder incrementally constructs SSA for one function. It is not safe for concurrent use; build one function per Builder.
func NewBuilder ¶
func NewBuilder() *Builder
NewBuilder returns an empty Builder with no blocks. Call NewBlock to create the entry block (and every other block).
func (*Builder) AddInstr ¶
func (b *Builder) AddInstr(block BlockID, inst *ir.Instruction)
AddInstr appends a caller-produced body instruction to a block, in order. Body instructions are emitted after the block's PHIs and before its terminator. The builder inspects them only to resolve operands that referenced a PHI which was later eliminated.
func (*Builder) BodyLoop ¶
func (b *Builder) BodyLoop(cur *BlockID, terminated *bool, lowerBody func(), lowerCond func() *ir.Value)
BodyLoop lowers a body-first loop (do/while: the body runs BEFORE the test) into a loop CFG: the current block jumps into the body block; the body is the loop header (its back-edge comes from the test block), so it is left UNSEALED until the back-edge is wired; the test block runs lowerCond and re-enters the body when true, or falls to exit. Loop-carried taint flows through the body-header PHI. Leaves *cur at the (sealed) exit block, *terminated false.
func (*Builder) Finish ¶
func (b *Builder) Finish() []*ir.BasicBlock
Finish materializes the SSA CFG as []*ir.BasicBlock, in id order, with all operands resolved through the trivial-PHI replacement chains. Call once, after every block has been sealed and terminated.
func (*Builder) HeaderLoop ¶
func (b *Builder) HeaderLoop(cur *BlockID, terminated *bool, lowerCond func() *ir.Value, lowerBody func())
HeaderLoop lowers a header-tested loop (while/for) into a REAL loop CFG: header/body/exit blocks. The current block jumps to the header; the header runs lowerCond and branches (body, exit); lowerBody fills the body, which jumps BACK to the header (the back-edge) — unless it terminated: a body that always returns has no back-edge. The header is left UNSEALED while the body is built, so a loop variable read in the condition or body parks an incomplete PHI that is filled when the header is sealed after the back-edge is wired — this is what gives loop-carried taint: a value written in the body and read at the top of the next iteration flows through the header PHI over [pre-loop, back-edge]. Leaves *cur at the (sealed) exit block, *terminated false.
A frontend puts a loop prologue (binding the iteration variable) at the top of lowerBody and a step (a C-style for's update) at its bottom; an opaque iteration condition (a for-range) is a lowerCond returning a constant placeholder.
func (*Builder) IfDiamond ¶
func (b *Builder) IfDiamond(cur *BlockID, terminated *bool, cond *ir.Value, lowerThen, lowerElse func()) (thenEnd, elseEnd, merge BlockID)
IfDiamond lowers a two-armed conditional into a REAL CFG diamond: the current block ends in an OP_CODE_IF on cond (which the caller has already lowered in *cur) to a fresh then-block and else-block; each arm is lowered in its own block and jumps to a fresh merge block; the merge is sealed once both arm-ends are its known predecessors, so any variable rebound on one or both arms reconciles automatically via an on-demand ReadVariable PHI. An arm that terminated (returned) gets no fall-through edge to the merge, and the merge is dead — *terminated left true — only if BOTH arms terminated. Returns the two arm-end blocks and the merge block so a value-producing conditional (Ruby's if-expression) can reconcile the arms' result values across them; statement-form callers ignore them.
func (*Builder) ReadVariable ¶
ReadVariable returns the value current for name in block, inserting PHIs on demand (and eliminating any that turn out trivial) so the result is the correct SSA value reaching that block.
func (*Builder) Seal ¶
Seal marks a block: all of its predecessors are now known. Any incomplete PHIs are given their operands and simplified. Idempotent.
func (*Builder) SetIf ¶
SetIf makes `block` end in a two-way branch on cond, recording block as a predecessor of both targets. Successors are emitted [trueBlk, falseBlk].
Source Files