optimize

package
v1.0.2 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Jul 6, 2026 License: MIT Imports: 11 Imported by: 0

Documentation

Overview

Package optimize holds CFG optimization passes, ported from sonolus.py's sonolus/backend/optimize. Passes operate in place on an ir.BasicBlock CFG and return the (possibly new) entry block.

Package optimize implements the ~40-pass IR optimizer ported from sonolus.py.

Pipeline pass ordering is documented in PIPELINE.md. The Go pipeline contains several intentional improvements over the Python reference:

  • Earlier CoalesceSmallConditionalBlocks (pre-SSA) for more DCE opportunities
  • UnflattenAssociativeOps after FromSSA to clean up SSA destruction
  • Extra cleanup round (Coalesce + UCE + DCE) after AdvancedDCE
  • RenumberVars at end of Standard for deterministic output
  • Tiered allocation: AllocateBasic (Minimal), TryAllocateBasic (Fast), AllocateLive (Standard)

See PIPELINE.md for the full divergence rationale and pass-by-pass comparison.

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func Optimize

func Optimize(gen *ir.IDGen, entry *ir.BasicBlock, mode ir.Mode, callback string, tempBlock int, level Level) (*ir.BasicBlock, error)

Optimize runs the optimization pipeline for the given level and returns the (possibly new) entry block. A pass dependency violation returns an error instead of panicking — this indicates a programming error in the pipeline definition and should be treated as a fatal error by callers.

func OptimizeCtx

func OptimizeCtx(gen *ir.IDGen, entry *ir.BasicBlock, mode ir.Mode, callback string, tempBlock int, level Level, ctx context.Context) (*ir.BasicBlock, error)

OptimizeCtx is like Optimize but checks ctx after every pass for cancellation. If ctx is nil, cancellation is skipped (same behavior as Optimize).

func RunPasses

func RunPasses(gen *ir.IDGen, entry *ir.BasicBlock, passes ...Pass) *ir.BasicBlock

RunPasses runs passes in order, threading the entry block through each. Passes that implement PassWithDom receive a cached dominance tree that is shared across the pipeline, avoiding redundant O(N²) recomputation.

func RunPassesCtx

func RunPassesCtx(gen *ir.IDGen, entry *ir.BasicBlock, ctx context.Context, passes ...Pass) *ir.BasicBlock

RunPassesCtx is like RunPasses but checks ctx after every pass. If ctx is nil or ctx.Done() is nil, cancellation is skipped entirely (zero overhead).

func VerifyPasses

func VerifyPasses(passes ...Pass) error

VerifyPasses checks that the given pass sequence is valid without running it. Useful for testing the Standard pipeline.

Types

type AdvancedDCE

type AdvancedDCE struct{}

AdvancedDCE uses LivenessAnalysis to remove stores to temps that are never read after the store point.

func (AdvancedDCE) Destroys

func (AdvancedDCE) Destroys() []Analysis

Destroys implements ManagedPass.

func (AdvancedDCE) Name

func (AdvancedDCE) Name() string

func (AdvancedDCE) Preserves

func (AdvancedDCE) Preserves() []Analysis

Preserves implements ManagedPass.

func (AdvancedDCE) Requires

func (AdvancedDCE) Requires() []Analysis

Requires implements ManagedPass — AdvancedDCE operates on liveness data.

func (AdvancedDCE) Run

func (AdvancedDCE) Run(gen *ir.IDGen, entry *ir.BasicBlock) *ir.BasicBlock

type AllocateBasic

type AllocateBasic struct {
	BlockID int // temporary memory block ID (defaults to DefaultTempMemoryBlock)
}

AllocateBasic assigns TempBlock offsets sequentially in CFG preorder without liveness analysis. It mirrors sonolus.py's allocate.AllocateBasic: each TempBlock encountered gets a contiguous offset, and TempBlock references in BlockPlace.Block are rewritten to the concrete block ID.

AllocateBasic is faster than AllocateLive (no dataflow analysis, no interval packing) but consumes more temporary memory since non-overlapping lifetimes are not reused. It is appropriate for MINIMAL and FAST compilation levels where compile speed matters more than output compactness.

func (AllocateBasic) Name

func (AllocateBasic) Name() string

func (AllocateBasic) Run

func (a AllocateBasic) Run(gen *ir.IDGen, entry *ir.BasicBlock) *ir.BasicBlock

type AllocateLive

type AllocateLive struct {
	BlockID int
}

AllocateLive assigns TempBlocks to minimal concrete slots using live-interval packing. Non-overlapping live ranges reuse the same slot. It is called directly (not via RunPasses) as the final allocation step.

func (AllocateLive) Run

func (a AllocateLive) Run(gen *ir.IDGen, entry *ir.BasicBlock) *ir.BasicBlock

Run performs the live-interval allocation and returns entry unchanged.

type Analysis

type Analysis string

Analysis names a CFG analysis that passes may depend on. Port of sonolus.py's pass analysis system.

const (
	AnalysisDominance Analysis = "Dominance"
	AnalysisSSA       Analysis = "SSA"
)

type BlockOracle

type BlockOracle interface {
	Writable(block int, callback string) bool
	RuntimeConstant(block int) bool
}

BlockOracle answers queries about Sonolus memory blocks that the optimizer needs. Implementations are provided by the IR layer (ir.BlockSet) and can be mocked for testing.

type CSE

type CSE struct{}

CSE is global common-subexpression elimination using the dominator tree. Port of sonolus.py cse.CommonSubexpressionElimination.

func (CSE) Destroys

func (CSE) Destroys() []Analysis

Destroys implements ManagedPass.

func (CSE) Name

func (CSE) Name() string

func (CSE) Preserves

func (CSE) Preserves() []Analysis

Preserves implements ManagedPass.

func (CSE) Requires

func (CSE) Requires() []Analysis

Requires implements ManagedPass — CSE operates on SSA form.

func (CSE) Run

func (CSE) Run(gen *ir.IDGen, entry *ir.BasicBlock) *ir.BasicBlock

func (CSE) RunWithDom

func (CSE) RunWithDom(gen *ir.IDGen, entry *ir.BasicBlock, dc *DominanceCache) *ir.BasicBlock

type CoalesceFlow

type CoalesceFlow struct{}

CoalesceFlow simplifies control flow: it skips over empty pass-through blocks, removes duplicate edges to a default target, and merges linear block chains. Port of sonolus.py simplify.CoalesceFlow (phi handling omitted).

func (CoalesceFlow) Destroys

func (CoalesceFlow) Destroys() []Analysis

func (CoalesceFlow) Name

func (CoalesceFlow) Name() string

func (CoalesceFlow) Preserves

func (CoalesceFlow) Preserves() []Analysis

func (CoalesceFlow) Requires

func (CoalesceFlow) Requires() []Analysis

Requires: none (runs early, before dominance/SSA).

func (CoalesceFlow) Run

func (CoalesceFlow) Run(gen *ir.IDGen, entry *ir.BasicBlock) *ir.BasicBlock

type CoalesceSmallConditionalBlocks

type CoalesceSmallConditionalBlocks struct{}

CoalesceSmallConditionalBlocks merges blocks with 1 outgoing edge whose target has <= 1 statement. This collapses trivial passthroughs produced by frontend constructs (switch cases, if/else empty branches) without the full complexity of CoalesceFlow (which needs phi handling).

func (CoalesceSmallConditionalBlocks) Destroys

func (CoalesceSmallConditionalBlocks) Name

func (CoalesceSmallConditionalBlocks) Preserves

func (CoalesceSmallConditionalBlocks) Requires

func (CoalesceSmallConditionalBlocks) Run

type CombineExitBlocks

type CombineExitBlocks struct{}

CombineExitBlocks merges empty exit blocks (no statements, no outgoing edges) into a single canonical exit, reducing block count.

func (CombineExitBlocks) Destroys

func (CombineExitBlocks) Destroys() []Analysis

func (CombineExitBlocks) Name

func (CombineExitBlocks) Name() string

func (CombineExitBlocks) Preserves

func (CombineExitBlocks) Preserves() []Analysis

func (CombineExitBlocks) Requires

func (CombineExitBlocks) Requires() []Analysis

func (CombineExitBlocks) Run

func (CombineExitBlocks) Run(gen *ir.IDGen, entry *ir.BasicBlock) *ir.BasicBlock

type CopyCoalesce

type CopyCoalesce struct{}

CopyCoalesce merges temp-block copies introduced by FromSSA's phi resolution. It scans the CFG for Set(t1, Get(t2)) where t1 and t2 are both size-1 temps, then replaces all uses of t1 with t2 and drops the copy using union-find. For multi-predecessor blocks, copies are only coalesced when the destination temp has a single definition, preventing interference between simultaneously live temps. Port of sonolus.py copy_coalesce.CopyCoalesce.

func (CopyCoalesce) Name

func (CopyCoalesce) Name() string

func (CopyCoalesce) Run

func (CopyCoalesce) Run(gen *ir.IDGen, entry *ir.BasicBlock) *ir.BasicBlock

type DeadCodeElimination

type DeadCodeElimination struct{}

DeadCodeElimination removes stores to temp blocks (and SSA places) whose value is never used, and drops self-copies, while preserving side effects. Port of sonolus.py dead_code.DeadCodeElimination (SSA/phi/array handling omitted; our definable places are size-1 TempBlocks).

func (DeadCodeElimination) Destroys

func (DeadCodeElimination) Destroys() []Analysis

func (DeadCodeElimination) Name

func (DeadCodeElimination) Name() string

func (DeadCodeElimination) Preserves

func (DeadCodeElimination) Preserves() []Analysis

func (DeadCodeElimination) Requires

func (DeadCodeElimination) Requires() []Analysis

func (DeadCodeElimination) Run

func (DeadCodeElimination) Run(gen *ir.IDGen, entry *ir.BasicBlock) *ir.BasicBlock

type Dominance

type Dominance struct {
	Order       []*ir.BasicBlock
	Num         map[*ir.BasicBlock]int
	IDom        map[*ir.BasicBlock]*ir.BasicBlock
	DomChildren map[*ir.BasicBlock][]*ir.BasicBlock
	DF          map[*ir.BasicBlock]map[*ir.BasicBlock]bool
}

Dominance holds dominator information for a CFG: reverse-postorder, block numbering, immediate dominators, the dominator-tree children, and dominance frontiers. Port of sonolus.py dominance.DominanceFrontiers (returned as data rather than stored on blocks).

func ComputeDominance

func ComputeDominance(entry *ir.BasicBlock) *Dominance

ComputeDominance computes dominators and dominance frontiers for the CFG rooted at entry using the Cooper-Harvey-Kennedy algorithm.

type DominanceCache

type DominanceCache struct {
	// contains filtered or unexported fields
}

DominanceCache caches the dominance tree across multiple passes within a single Optimize() invocation. It invalidates automatically when the CFG structure changes (detected via structural hash).

func (*DominanceCache) Get

func (c *DominanceCache) Get(entry *ir.BasicBlock) *Dominance

Get returns the cached dominance tree, recomputing it if the CFG structure has changed since the last call.

func (*DominanceCache) Invalidate

func (c *DominanceCache) Invalidate()

Invalidate forces the next Get to recompute the dominance tree regardless of CFG structure changes. Call after passes that modify the CFG structurally.

type FlattenAssociativeOps

type FlattenAssociativeOps struct{}

FlattenAssociativeOps flattens nested Add/Add chains: a+(b+c) -> a+b+c. This lets RemoveRedundantArguments see and strip identity elements (+0, *1).

func (FlattenAssociativeOps) Name

func (FlattenAssociativeOps) Run

type FromSSA

type FromSSA struct{}

FromSSA destroys SSA form: it splits each phi-carrying block's incoming edges with a "between" block, materializes phis as copies on those edges, and maps each SSA value back to a temp block named "name.num". Port of sonolus.py ssa.FromSSA. allocateTempBlocks must run afterward before finalization.

func (FromSSA) Destroys

func (FromSSA) Destroys() []Analysis

Destroys implements ManagedPass — FromSSA exits SSA form.

func (FromSSA) Name

func (FromSSA) Name() string

func (FromSSA) Preserves

func (FromSSA) Preserves() []Analysis

Preserves implements ManagedPass.

func (FromSSA) Requires

func (FromSSA) Requires() []Analysis

Requires implements ManagedPass.

func (FromSSA) Run

func (FromSSA) Run(gen *ir.IDGen, entry *ir.BasicBlock) *ir.BasicBlock

type InlineVars

type InlineVars struct {
	Aggressive bool
	Callback   string
	Oracle     BlockOracle
}

InlineVars inlines SSA value definitions into their uses, collapsing read-once temporaries and copies. Port of sonolus.py inlining.InlineVars.

func (InlineVars) Destroys

func (v InlineVars) Destroys() []Analysis

func (InlineVars) Name

func (InlineVars) Name() string

func (InlineVars) Preserves

func (v InlineVars) Preserves() []Analysis

func (InlineVars) Requires

func (v InlineVars) Requires() []Analysis

func (InlineVars) Run

func (v InlineVars) Run(gen *ir.IDGen, entry *ir.BasicBlock) *ir.BasicBlock

func (InlineVars) RunWithDom

func (v InlineVars) RunWithDom(gen *ir.IDGen, entry *ir.BasicBlock, dc *DominanceCache) *ir.BasicBlock

type LICM

type LICM struct {
	Oracle BlockOracle
}

LICM hoists loop-invariant expressions out of loop bodies into pre-headers. Loop detection uses dominance-tree back-edges (FindLoops in optimize.go): an edge B→H is a back-edge when H dominates B. The loop body is the set of blocks reachable backward from the latch, stopped at the header.

IMPORTANT: LICM copies loop-invariant expressions into pre-header blocks but does NOT rewrite uses inside the loop body. A subsequent CSE pass (CommonSubexpressionElimination) deduplicates the hoisted copy against the original, effectively rewiring loop-body reads to the pre-header value. This coupling matches the original sonolus.py design (sonolus/backend/ optimize/licm.py:31-33). The Standard pipeline runs LICM immediately before CSE to satisfy this invariant.

Port of sonolus.py licm.LoopInvariantCodeMotion.

func (LICM) Destroys

func (LICM) Destroys() []Analysis

Destroys implements ManagedPass.

func (LICM) Name

func (LICM) Name() string

func (LICM) Preserves

func (LICM) Preserves() []Analysis

Preserves implements ManagedPass.

func (LICM) Requires

func (LICM) Requires() []Analysis

Requires implements ManagedPass — LICM operates on SSA form.

func (LICM) Run

func (l LICM) Run(gen *ir.IDGen, entry *ir.BasicBlock) *ir.BasicBlock

func (LICM) RunWithDom

func (l LICM) RunWithDom(gen *ir.IDGen, entry *ir.BasicBlock, dc *DominanceCache) *ir.BasicBlock

type Level

type Level int

Level selects an optimisation preset.

const (
	LevelMinimal  Level = iota + 1 // only essential cleanup, no SSA
	LevelFast                      // single SSA round, no LICM/CSE
	LevelStandard                  // full pipeline (~40 passes)
)

type LivenessResult

type LivenessResult struct {
	LiveIn  map[*ir.BasicBlock]map[*ir.TempBlock]bool
	LiveOut map[*ir.BasicBlock]map[*ir.TempBlock]bool
	Live    map[int]map[*ir.TempBlock]bool // live-after for each statement (by Instr.ID)
	Defs    map[int]map[*ir.TempBlock]bool // temps defined by each statement
	Uses    map[int]map[*ir.TempBlock]bool // temps used by each statement (precomputed)
}

LivenessResult holds per-block live-in/live-out and per-statement live-after sets. Statement keys are ir.Instr.ID values (monotonic, comparable).

type Loop

type Loop struct {
	Header  *ir.BasicBlock
	Latches []*ir.BasicBlock
	Body    map[*ir.BasicBlock]bool
}

Loop holds a discovered natural loop: its header, all back-edge latches, and the body blocks (including header and latches).

func FindLoops

func FindLoops(blocks []*ir.BasicBlock, dom *Dominance) []Loop

FindLoops discovers all natural loops in the CFG via dominance back-edges. It is used by both LICM and InlineVars to avoid duplicating loop discovery.

type ManagedPass

type ManagedPass interface {
	Pass
	Requires() []Analysis
	Preserves() []Analysis
	Destroys() []Analysis
}

ManagedPass extends Pass with analysis dependency declarations. Passes that implement this interface can be validated by VerifyPasses.

type NormalizeBlocks

type NormalizeBlocks struct{}

NormalizeBlocks recursively normalizes the IR tree in each block: nil BlockPlace.Index is replaced with Const(0), and all sub-expressions are recursively normalized. Port of sonolus.py simplify.NormalizeBlocks.

func (NormalizeBlocks) Name

func (NormalizeBlocks) Name() string

func (NormalizeBlocks) Run

func (NormalizeBlocks) Run(gen *ir.IDGen, entry *ir.BasicBlock) *ir.BasicBlock

type NormalizeSwitch

type NormalizeSwitch struct{}

NormalizeSwitch normalizes dense sequential cases: {100,101,102,103} becomes {(cond-100)}→{0,1,2,3} by transforming the test expression.

func (NormalizeSwitch) Name

func (NormalizeSwitch) Name() string

func (NormalizeSwitch) Run

func (NormalizeSwitch) Run(gen *ir.IDGen, entry *ir.BasicBlock) *ir.BasicBlock

type Pass

type Pass interface {
	Name() string
	Run(gen *ir.IDGen, entry *ir.BasicBlock) *ir.BasicBlock
}

Pass is a single CFG transformation.

func Fast

func Fast(mode ir.Mode, callback string) []Pass

Fast returns the pass list for the FAST optimisation level. It runs a single SSA round with SCCP and one inlining pass, then exits SSA. It skips LICM, CSE, and the second SCCP round, providing a good balance between compilation speed and output quality.

func Minimal

func Minimal(mode ir.Mode, callback string) []Pass

Minimal returns the pass list for the MINIMAL optimisation level. It runs only essential cleanup (coalesce, unreachable code, dead code) and skips SSA construction, SCCP, inlining, LICM, and CSE entirely. Compilation is fast but output quality may be lower.

mode and callback are accepted for interface consistency with Standard() and Fast() but are not used — the Minimal pipeline is mode-agnostic.

func Standard

func Standard(mode ir.Mode, callback string) []Pass

Standard returns the full Standard-level pass list.

type PassWithDom

type PassWithDom interface {
	Pass
	RunWithDom(gen *ir.IDGen, entry *ir.BasicBlock, dom *DominanceCache) *ir.BasicBlock
}

PassWithDom is an optional interface for passes that benefit from a cached dominance tree. Passes that modify CFG structure should call dom.Invalidate() to force recomputation on the next access.

type RemoveRedundantArguments

type RemoveRedundantArguments struct{}

RemoveRedundantArguments strips identity arguments from pure operations: Add(a,0) → a, Multiply(a,1) → a, Divide(a,1) → a, Add() → 0, Multiply() → 1. Port of sonolus.py simplify.RemoveRedundantArguments.

func (RemoveRedundantArguments) Name

func (RemoveRedundantArguments) Run

type RenumberVars

type RenumberVars struct{}

RenumberVars reassigns sequential names to TempBlocks in preorder so the output is deterministic across runs. Port of sonolus.py simplify.RenumberVars.

func (RenumberVars) Name

func (RenumberVars) Name() string

func (RenumberVars) Run

func (RenumberVars) Run(gen *ir.IDGen, entry *ir.BasicBlock) *ir.BasicBlock

type RewriteToSwitch

type RewriteToSwitch struct{}

RewriteToSwitch converts if-else chains comparing against constants into switch statements. Phase 1 swaps Equal(const, a) tests to make the const the edge condition. Phase 2 merges chained if-else-if blocks that share the same test expression and have empty successor blocks.

func (RewriteToSwitch) Destroys

func (RewriteToSwitch) Destroys() []Analysis

func (RewriteToSwitch) Name

func (RewriteToSwitch) Name() string

func (RewriteToSwitch) Preserves

func (RewriteToSwitch) Preserves() []Analysis

func (RewriteToSwitch) Requires

func (RewriteToSwitch) Requires() []Analysis

func (RewriteToSwitch) Run

func (RewriteToSwitch) Run(gen *ir.IDGen, entry *ir.BasicBlock) *ir.BasicBlock

type SCCP

type SCCP struct{}

SCCP is sparse conditional constant propagation. Port of sonolus.py constant_evaluation.SparseConditionalConstantPropagation. Supports frozenset lattice for phi nodes and multi-way switch-edge pruning. Foldable op set: 42 ops (full sonolus.py arithmetic/comparison/logic/trig).

func (SCCP) Destroys

func (SCCP) Destroys() []Analysis

func (SCCP) Name

func (SCCP) Name() string

func (SCCP) Preserves

func (SCCP) Preserves() []Analysis

func (SCCP) Requires

func (SCCP) Requires() []Analysis

func (SCCP) Run

func (SCCP) Run(gen *ir.IDGen, entry *ir.BasicBlock) *ir.BasicBlock

type ToSSA

type ToSSA struct{}

ToSSA converts size-1 temp-block variables into SSA form: it inserts phi nodes at the iterated dominance frontiers of each variable's definitions, then renames definitions and uses into versioned SSA places. Port of sonolus.py ssa.ToSSA.

func (ToSSA) Destroys

func (ToSSA) Destroys() []Analysis

Destroys implements ManagedPass.

func (ToSSA) Name

func (ToSSA) Name() string

func (ToSSA) Preserves

func (ToSSA) Preserves() []Analysis

Preserves implements ManagedPass — ToSSA produces SSA form.

func (ToSSA) Requires

func (ToSSA) Requires() []Analysis

Requires implements ManagedPass.

func (ToSSA) Run

func (ToSSA) Run(gen *ir.IDGen, entry *ir.BasicBlock) *ir.BasicBlock

func (ToSSA) RunWithDom

func (ToSSA) RunWithDom(gen *ir.IDGen, entry *ir.BasicBlock, dc *DominanceCache) *ir.BasicBlock

type TryAllocateBasic

type TryAllocateBasic struct {
	BlockID  int
	MaxSlots int
}

TryAllocateBasic implements the tiered allocation strategy used by the Fast optimisation level in sonolus.py: it attempts sequential allocation first (AllocateBasic) and falls back to liveness-based allocation (AllocateLive) when the basic allocator exceeds the slot threshold.

func (TryAllocateBasic) Name

func (TryAllocateBasic) Name() string

func (TryAllocateBasic) Run

func (a TryAllocateBasic) Run(gen *ir.IDGen, entry *ir.BasicBlock) *ir.BasicBlock

type UnflattenAssociativeOps

type UnflattenAssociativeOps struct{}

UnflattenAssociativeOps restores binary form: a+b+c -> ((a+b)+c). Sonolus opcodes are binary, so this must run before finalization.

func (UnflattenAssociativeOps) Name

func (UnflattenAssociativeOps) Run

type UnreachableCodeElimination

type UnreachableCodeElimination struct{}

UnreachableCodeElimination folds constant branch tests (keeping only the taken edge) and removes edges originating from blocks that become unreachable. Port of sonolus.py dead_code.UnreachableCodeElimination (phi handling omitted).

func (UnreachableCodeElimination) Destroys

func (UnreachableCodeElimination) Destroys() []Analysis

func (UnreachableCodeElimination) Name

func (UnreachableCodeElimination) Preserves

func (UnreachableCodeElimination) Preserves() []Analysis

func (UnreachableCodeElimination) Requires

func (UnreachableCodeElimination) Requires() []Analysis

func (UnreachableCodeElimination) Run

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL