Documentation
¶
Index ¶
- Constants
- Variables
- func Run(program *bytecode.Program, level Level) error
- type Analyzer
- type BasicBlock
- type Builder
- type ConstantPropagationPass
- type ControlFlowGraph
- type Level
- type LivenessAnalysisPass
- type LivenessInfo
- type Pass
- type PassContext
- type PassResult
- type PeepholePass
- type Pipeline
- type PipelineResult
- type RegisterCoalescingPass
Constants ¶
const ( LivenessAnalysisPassName = "liveness-analysis" LivenessAnalysis = "liveness" )
const ConstantPropagationPassName = "constant-propagation"
const PeepholePassName = "peephole"
const RegisterCoalescingPassName = "register-coalescing"
Variables ¶
var ( ErrCFGBuildFailed = errors.New("failed to build control flow graph") ErrPassFailed = errors.New("optimization pass failed") ErrMissingDependency = errors.New("missing optimization pass dependency") ErrDependencyRefreshModified = errors.New("refreshed optimization dependency modified program") )
Functions ¶
Types ¶
type Analyzer ¶
type Analyzer struct {
// contains filtered or unexported fields
}
Analyzer provides analysis capabilities for control flow graphs
func NewAnalyzer ¶
func NewAnalyzer(cfg *ControlFlowGraph) *Analyzer
NewAnalyzer creates a new CFG analyzer
func (*Analyzer) CalculateDominators ¶
func (a *Analyzer) CalculateDominators() map[int]*BasicBlock
CalculateDominators computes the dominator tree for the CFG A block A dominates block B if all paths from entry to B go through A
func (*Analyzer) FindBackEdges ¶
func (a *Analyzer) FindBackEdges() [][2]*BasicBlock
FindBackEdges identifies back edges in the CFG (edges that create loops) A back edge is an edge from a node to one of its ancestors in a DFS traversal
func (*Analyzer) FindReachableBlocks ¶
func (a *Analyzer) FindReachableBlocks() []*BasicBlock
FindReachableBlocks returns all blocks reachable from the entry block
func (*Analyzer) FindUnreachableBlocks ¶
func (a *Analyzer) FindUnreachableBlocks() []*BasicBlock
FindUnreachableBlocks returns all blocks not reachable from the entry block
type BasicBlock ¶
type BasicBlock struct {
Instructions []bytecode.Instruction
Successors []*BasicBlock
Predecessors []*BasicBlock
ID int
Start int
End int
}
BasicBlock represents a sequence of instructions with a single entry and exit point
func NewBasicBlock ¶
func NewBasicBlock(id, start int) *BasicBlock
NewBasicBlock creates a new basic block with the given ID and start position
func (*BasicBlock) AddInstruction ¶
func (bb *BasicBlock) AddInstruction(inst bytecode.Instruction)
AddInstruction adds an instruction to the basic block
func (*BasicBlock) AddSuccessor ¶
func (bb *BasicBlock) AddSuccessor(succ *BasicBlock)
AddSuccessor adds a successor block to this block
func (*BasicBlock) IsTerminator ¶
func (bb *BasicBlock) IsTerminator() bool
IsTerminator returns true if the block ends with a terminator instruction
func (*BasicBlock) String ¶
func (bb *BasicBlock) String() string
String returns a string representation of the basic block
type Builder ¶
type Builder struct {
// contains filtered or unexported fields
}
Builder constructs a control flow graph from bytecode
func NewBuilder ¶
NewBuilder creates a new CFG builder for the given program
func (*Builder) Build ¶
func (b *Builder) Build() (*ControlFlowGraph, error)
Build constructs the control flow graph for the program
type ConstantPropagationPass ¶
type ConstantPropagationPass struct{}
ConstantPropagationPass performs a simple constant propagation and folding. It is conservative across control-flow merges: a register is considered constant only if all predecessors agree on the same constant value.
func (*ConstantPropagationPass) Name ¶
func (p *ConstantPropagationPass) Name() string
func (*ConstantPropagationPass) Requires ¶
func (p *ConstantPropagationPass) Requires() []string
func (*ConstantPropagationPass) Run ¶
func (p *ConstantPropagationPass) Run(ctx *PassContext) (*PassResult, error)
type ControlFlowGraph ¶
type ControlFlowGraph struct {
Entry *BasicBlock // Entry block (first instruction)
Exit *BasicBlock // Exit block (virtual block representing program exit)
Blocks []*BasicBlock // All basic blocks in the program
}
ControlFlowGraph represents the control flow structure of a bytecode program
func (*ControlFlowGraph) String ¶
func (cfg *ControlFlowGraph) String() string
String returns a human-readable representation of the CFG
func (*ControlFlowGraph) ToDOT ¶
func (cfg *ControlFlowGraph) ToDOT() string
ToDOT converts the CFG to Graphviz DOT format for visualization
type LivenessAnalysisPass ¶
type LivenessAnalysisPass struct{}
LivenessAnalysisPass performs liveness analysis to determine which registers are live (potentially used) at each program point
func (*LivenessAnalysisPass) Name ¶
func (p *LivenessAnalysisPass) Name() string
Name returns the pass name
func (*LivenessAnalysisPass) Requires ¶
func (p *LivenessAnalysisPass) Requires() []string
func (*LivenessAnalysisPass) Run ¶
func (p *LivenessAnalysisPass) Run(c *PassContext) (*PassResult, error)
Run executes liveness analysis on the program
type LivenessInfo ¶
type LivenessInfo struct {
LiveIn map[int]bool // Registers live at block entry
LiveOut map[int]bool // Registers live at block exit
Use map[int]bool // Registers used in block before definition
Def map[int]bool // Registers defined in block
}
LivenessInfo contains liveness information for a basic block
type Pass ¶
type Pass interface {
Name() string
Requires() []string
Run(ctx *PassContext) (*PassResult, error)
}
func NewConstantPropagationPass ¶
func NewConstantPropagationPass() Pass
NewConstantPropagationPass creates a new constant propagation pass.
func NewLivenessAnalysisPass ¶
func NewLivenessAnalysisPass() Pass
NewLivenessAnalysisPass creates a new liveness analysis pass
func NewRegisterCoalescingPass ¶
func NewRegisterCoalescingPass() Pass
NewRegisterCoalescingPass creates a new register coalescing pass
type PassContext ¶
type PassContext struct {
Program *bytecode.Program
CFG *ControlFlowGraph
Metadata map[string]any // Shared metadata between passes
}
type PassResult ¶
PassResult contains the result of running a pass
type PeepholePass ¶
type PeepholePass struct{}
PeepholePass performs simple local rewrites to remove redundant instructions.
func (*PeepholePass) Requires ¶
func (p *PeepholePass) Requires() []string
Requires returns dependencies for the pass.
func (*PeepholePass) Run ¶
func (p *PeepholePass) Run(ctx *PassContext) (*PassResult, error)
Run executes the peephole optimizations on the program.
type Pipeline ¶
type Pipeline struct {
// contains filtered or unexported fields
}
Pipeline manages a sequence of passes to be executed on a program
type PipelineResult ¶
type PipelineResult struct {
Modified bool
}
PipelineResult contains the results of running a pipeline
type RegisterCoalescingPass ¶
type RegisterCoalescingPass struct{}
RegisterCoalescingPass performs register coalescing to reduce register usage by renumbering registers based on liveness intervals
func (*RegisterCoalescingPass) Name ¶
func (p *RegisterCoalescingPass) Name() string
Name returns the pass name
func (*RegisterCoalescingPass) Requires ¶
func (p *RegisterCoalescingPass) Requires() []string
func (*RegisterCoalescingPass) Run ¶
func (p *RegisterCoalescingPass) Run(ctx *PassContext) (*PassResult, error)
Run executes register coalescing on the program
Source Files
¶
- analysis.go
- basic_block.go
- builder.go
- cfg.go
- coalescing.go
- const_eval.go
- const_fold.go
- const_fold_result.go
- errors.go
- interference.go
- pass.go
- pass_constant_propagation.go
- pass_liveness.go
- pass_peephole.go
- pass_register_coalescing.go
- peephole_helpers.go
- peephole_remap.go
- pipeline.go
- pipeline_test_pass.go
- renumbering.go
- set_helpers.go
- use_def_collector.go