Documentation
¶
Index ¶
- Variables
- func BlockTransformPassBlock(block *ir.Block, f func(*ir.Block) (*ir.Block, bool)) (*ir.Block, bool)
- func BlockTransformPassBlocks(blocks []*ir.Block, f func(*ir.Block) (*ir.Block, bool)) ([]*ir.Block, bool)
- func EmptyLoopReplacement(block *ir.Block) (*ir.Block, bool)
- func EmptyLoopReplacementPass(policy *ir.Policy) *ir.Policy
- func GetSatUnsatForBlock(block *ir.Block, offset int, unsatisfied UnsatMap, satisfied SatMap) (UnsatMap, SatMap)
- func GetSatUnsatForBlocks(blocks []*ir.Block, offset int, unsatisfied UnsatMap, satisfied SatMap) (UnsatMap, SatMap)
- func GetSatUnsatForStmts(stmts []ir.Stmt, offset int, unsatisfied UnsatMap, satisfied SatMap) (UnsatMap, SatMap)
- func LoopInvariantCodeMotionPass(policy *ir.Policy) *ir.Policy
- func LoopPassBlock(block *ir.Block, f func(LoopTransformState) (LoopTransformState, bool)) (*ir.Block, bool)
- func LoopPassBlocks(blocks []*ir.Block, f func(LoopTransformState) (LoopTransformState, bool)) ([]*ir.Block, bool)
- func RewriteBreakStmtsForLifting(stmt ir.Stmt, depth uint32) (ir.Stmt, bool)
- func RunPasses(policy *ir.Policy, schedule []*IROptPass) (*ir.Policy, error)
- type IROptPass
- type LoopTransformState
- type OptimizationPassFlags
- func (opf *OptimizationPassFlags) GetCLIFlagNames() []string
- func (opf *OptimizationPassFlags) GetFieldNames() []string
- func (opf *OptimizationPassFlags) GetFieldPtrMapping() map[string]*bool
- func (opf *OptimizationPassFlags) GetFlag(name string) bool
- func (opf *OptimizationPassFlags) GetFlagToFieldsMapping() map[string]string
- func (opf *OptimizationPassFlags) MergeDisables(other *OptimizationPassFlags) *OptimizationPassFlags
- func (opf *OptimizationPassFlags) MergeEnables(other *OptimizationPassFlags) *OptimizationPassFlags
- func (opf *OptimizationPassFlags) SetFlag(name string, value bool)
- type SatMap
- type UnsatMap
Constants ¶
This section is empty.
Variables ¶
var RegoVMIROptimizationPassSchedule []*IROptPass
Functions ¶
func BlockTransformPassBlock ¶
func BlockTransformPassBlock(block *ir.Block, f func(*ir.Block) (*ir.Block, bool)) (*ir.Block, bool)
Recursively applies the transform for lower blocks, and after assembling the (possibly transformed) instructions into a block, applies the transform at this level of the plan before returning the results.
func BlockTransformPassBlocks ¶
func BlockTransformPassBlocks(blocks []*ir.Block, f func(*ir.Block) (*ir.Block, bool)) ([]*ir.Block, bool)
Recursively descends the block list, applying the block transformation to the deepest-nested blocks first.
func EmptyLoopReplacement ¶
Replaces empty ScanStmt loops with a short sequence of non-looping instructions with the same early-exit effects as the loop.
func GetSatUnsatForBlock ¶
func GetSatUnsatForBlock(block *ir.Block, offset int, unsatisfied UnsatMap, satisfied SatMap) (UnsatMap, SatMap)
offset provides the index offset in the overall instruction numbering.
func GetSatUnsatForBlocks ¶
func GetSatUnsatForBlocks(blocks []*ir.Block, offset int, unsatisfied UnsatMap, satisfied SatMap) (UnsatMap, SatMap)
Builds a graph of locals (registers) from a blocklist. offset provides the index offset in the overall instruction numbering.
func GetSatUnsatForStmts ¶
func GetSatUnsatForStmts(stmts []ir.Stmt, offset int, unsatisfied UnsatMap, satisfied SatMap) (UnsatMap, SatMap)
offset provides the index offset in the overall instruction numbering.
func LoopInvariantCodeMotionPass ¶
The pass design allows us to wire this into the global pass structure.
func LoopPassBlock ¶
func LoopPassBlock(block *ir.Block, f func(LoopTransformState) (LoopTransformState, bool)) (*ir.Block, bool)
func LoopPassBlocks ¶
func LoopPassBlocks(blocks []*ir.Block, f func(LoopTransformState) (LoopTransformState, bool)) ([]*ir.Block, bool)
Recursively descends the block list, until it finds the innermost loop body, and then applies the loop transform repeatedly until no further modifications are made.
func RewriteBreakStmtsForLifting ¶
Returns (possibly rewritten) stmt, and whether it was modified or not.
Types ¶
type IROptPass ¶
type IROptPass struct {
// contains filtered or unexported fields
}
Borrowed from OPA's compiler stage struct:
func NewIROptLevel0Schedule ¶
func NewIROptLevel0Schedule(cliEnableFlags, _ *OptimizationPassFlags) []*IROptPass
Generates a new optimization pass schedule for -O=0, taking into account -of and -ofno flags. Note(philip): Eventually, we'll add back the `cliEnableFlags` parameter, but for now, no passes need manual enabling at -O=0.
func NewIROptLevel1Schedule ¶
func NewIROptLevel1Schedule(cliEnableFlags, cliDisableFlags *OptimizationPassFlags) []*IROptPass
func NewIROptLevel2Schedule ¶
func NewIROptLevel2Schedule(cliEnableFlags, cliDisableFlags *OptimizationPassFlags) []*IROptPass
type LoopTransformState ¶
type LoopTransformState struct {
Before []ir.Stmt
After []ir.Stmt
Loop ir.Stmt // ScanStmt with a body appended.
}
Encodes the state of preamble, postamble, and loop body instructions for the loop.
func LoopInvariantCodeMotion ¶
func LoopInvariantCodeMotion(state LoopTransformState) (LoopTransformState, bool)
Performs Loop Invariant Code Motion for this loop. Behavior Notes:
- Assumes it's the innermost loop, and that LICM has already happened for any nested ScanStmt loops in its loop body.
- Runs until it hits a fixpoint, which happens when there are no further instructions to move.
Edge-Case Notes:
- BreakStmt :: Has an implicit control dependency on all upstream instructions in the block. -- Resolved by *always* being the last thing moved out of a loop. If it is not the only member of the loop, it cannot be moved. -- If lifted, it usually has to be rewritten, to ensure its jump target is the same. --- We don't have to recursively rewrite the levels, because the jumps are *relative*, and only direct movement of the statement requires a rewrite, because that's changing its relative placement in the block hierarchy, relative to sibling blocks.
- AssignVarOnceStmt, ObjectInsertOnceStmt :: Implicit control dependency, similar to BreakStmt. -- We always lift these last out of a loop. No rewriting is performed. --- Note(philip): This may prove unsafe, in which case we'll just have to treat them as unmovable.
- Nondeterministic Builtin function calls :: Generally cannot be moved out of the loop. Have ordering dependencies relative to each other. (Ex: http.send calls) -- Applies to: some CallStmt, almost all CallDynamicStmt -- HACK: Resolved by never lifting ND builtins out of the loop, and thus they'll end up being in-order at the end. -- TODO: We *can* do better down the road, but for now, it's easier to just treat them as unmovable. --- The down-the-road way of "doing better" will be to track which ND builtin calls are really unmovable, and treating them as movement barriers.
Mark-and-Lift Algorithm:
- Because sometimes it's convenient to create a temp var in a loop, we have to check the reaching definition property of each instruction in the loop-- does any downstream instruction overwrite that instruction's write target register(s)?
- We can continue to do a linear forward pass by marking each liftable instruction index, and then only at the end (before the next pass) lifting all the truly safe-to-lift instructions at once.
type OptimizationPassFlags ¶
type OptimizationPassFlags struct {
LoopInvariantCodeMotion bool `cli:"licm"`
}
NOTE(philip): We use struct tags to encode the CLI-visible names for each pass. Ref: https://stackoverflow.com/a/30889373
func (*OptimizationPassFlags) GetCLIFlagNames ¶
func (opf *OptimizationPassFlags) GetCLIFlagNames() []string
func (*OptimizationPassFlags) GetFieldNames ¶
func (opf *OptimizationPassFlags) GetFieldNames() []string
func (*OptimizationPassFlags) GetFieldPtrMapping ¶
func (opf *OptimizationPassFlags) GetFieldPtrMapping() map[string]*bool
HACK(philip): More horrific reflection hackery, also for the CLI. Ref: https://stackoverflow.com/a/29185381
func (*OptimizationPassFlags) GetFlag ¶
func (opf *OptimizationPassFlags) GetFlag(name string) bool
func (*OptimizationPassFlags) GetFlagToFieldsMapping ¶
func (opf *OptimizationPassFlags) GetFlagToFieldsMapping() map[string]string
HACK(philip): Relies on pass names and CLI flags being the same length.
func (*OptimizationPassFlags) MergeDisables ¶
func (opf *OptimizationPassFlags) MergeDisables(other *OptimizationPassFlags) *OptimizationPassFlags
func (*OptimizationPassFlags) MergeEnables ¶
func (opf *OptimizationPassFlags) MergeEnables(other *OptimizationPassFlags) *OptimizationPassFlags
func (*OptimizationPassFlags) SetFlag ¶
func (opf *OptimizationPassFlags) SetFlag(name string, value bool)
HACK(philip): Horrible reflection hack, thankfully only needed to make CLI enable/disable flags easier to work with. Ref: https://stackoverflow.com/a/18931036
Source Files