ssa

package
v0.1.4 Latest Latest
Warning

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

Go to latest
Published: Nov 18, 2022 License: Apache-2.0 Imports: 21 Imported by: 0

Documentation

Index

Constants

View Source
const (
	K_sys  = 0
	K_zero = 1
	K_temp = 2
	K_arch = 3
	K_norm = 4
)
View Source
const (
	N_size = _M_name + 1
)

Variables

View Source
var (
	MinInt65 = Int65{0, 1}
	MaxInt65 = Int65{math.MaxUint64, 0}
)
View Source
var Passes = [...]PassDescriptor{
	{Name: "Early Constant Propagation", Pass: new(ConstProp)},
	{Name: "Early Reduction", Pass: new(Reduce)},
	{Name: "Branch Elimination", Pass: new(BranchElim)},
	{Name: "Return Spreading", Pass: new(ReturnSpread)},
	{Name: "Value Reordering", Pass: new(Reorder)},
	{Name: "Late Constant Propagation", Pass: new(ConstProp)},
	{Name: "Late Reduction", Pass: new(Reduce)},
	{Name: "Machine Dependent Lowering", Pass: new(Lowering)},
	{Name: "Zero Register Substitution", Pass: new(ZeroReg)},
	{Name: "Write Barrier Insertion", Pass: new(WriteBarrier)},
	{Name: "ABI-Specific Lowering", Pass: new(ABILowering)},
	{Name: "Instruction Fusion", Pass: new(Fusion)},
	{Name: "Instruction Compaction", Pass: new(Compaction)},
	{Name: "Block Merging", Pass: new(BlockMerge)},
	{Name: "Critical Edge Splitting", Pass: new(SplitCritical)},
	{Name: "Phi Propagation", Pass: new(PhiProp)},
	{Name: "Operand Allocation", Pass: new(OperandAlloc)},
	{Name: "Constant Rematerialize", Pass: new(Rematerialize)},
	{Name: "Pre-allocation TDCE", Pass: new(TDCE)},
	{Name: "Register Allocation", Pass: new(RegAlloc)},
	{Name: "Stack Liveness Analysis", Pass: new(StackLiveness)},
	{Name: "Function Layout", Pass: new(Layout)},
}
View Source
var Reductions = []PassDescriptor{
	{Name: "Common Sub-expression Elimination", Pass: new(CSE)},
	{Name: "Phi Elimination", Pass: new(PhiElim)},
	{Name: "Copy Elimination", Pass: new(CopyElim)},
	{Name: "Trivial Dead Code Elimination", Pass: new(TDCE)},
}

Functions

func IrTryIntoCopy added in v0.1.4

func IrTryIntoCopy(v IrNode) (Reg, Reg, bool)

Types

type ABILowering added in v0.1.1

type ABILowering struct{}

ABILowering lowers ABI-specific instructions to machine specific instructions.

func (ABILowering) Apply added in v0.1.1

func (self ABILowering) Apply(cfg *CFG)

type BasicBlock

type BasicBlock struct {
	Id   int
	Phi  []*IrPhi
	Ins  []IrNode
	Pred []*BasicBlock
	Term IrTerminator
}

func (*BasicBlock) String added in v0.1.4

func (self *BasicBlock) String() string

type BasicBlockIter added in v0.1.2

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

func (*BasicBlockIter) Block added in v0.1.2

func (self *BasicBlockIter) Block() *BasicBlock

func (*BasicBlockIter) ForEach added in v0.1.2

func (self *BasicBlockIter) ForEach(action func(bb *BasicBlock))

func (*BasicBlockIter) Next added in v0.1.2

func (self *BasicBlockIter) Next() bool

func (*BasicBlockIter) Reversed added in v0.1.2

func (self *BasicBlockIter) Reversed() []*BasicBlock

type BlockMerge

type BlockMerge struct{}

BlockMerge merges redundant intermediate blocks (blocks with a single outgoing edge which goes to another block with a single incoming edge).

func (BlockMerge) Apply

func (BlockMerge) Apply(cfg *CFG)

type BranchElim

type BranchElim struct{}

BranchElim removes branches that can be proved unreachable.

func (BranchElim) Apply

func (self BranchElim) Apply(cfg *CFG)

type CFG

type CFG struct {
	Func              FuncData
	Root              *BasicBlock
	Depth             map[int]int
	Layout            *abi.FunctionLayout
	DominatedBy       map[int]*BasicBlock
	DominatorOf       map[int][]*BasicBlock
	DominanceFrontier map[int][]*BasicBlock
	// contains filtered or unexported fields
}

func Compile

func Compile(p hir.Program, fn interface{}) (cfg *CFG)

func (*CFG) CreateBlock added in v0.1.1

func (self *CFG) CreateBlock() (r *BasicBlock)

func (*CFG) CreateRegister added in v0.1.1

func (self *CFG) CreateRegister(ptr bool) Reg

func (*CFG) CreateUnreachable added in v0.1.1

func (self *CFG) CreateUnreachable(bb *BasicBlock) (ret *BasicBlock)

func (*CFG) MaxBlock

func (self *CFG) MaxBlock() int

func (*CFG) PostOrder

func (self *CFG) PostOrder() *BasicBlockIter

func (*CFG) Rebuild

func (self *CFG) Rebuild()

type CSE

type CSE struct{}

CSE performs the Common Sub-expression Elimintation optimization.

func (CSE) Apply

func (self CSE) Apply(cfg *CFG)

type ConstProp

type ConstProp struct{}

ConstProp propagates constant through the expression tree.

func (ConstProp) Apply

func (self ConstProp) Apply(cfg *CFG)

type Constness added in v0.1.1

type Constness uint8
const (
	Const Constness = iota
	Volatile
)

func (Constness) String added in v0.1.1

func (self Constness) String() string

type CopyElim

type CopyElim struct{}

CopyElim removes unnessecery register copies.

func (CopyElim) Apply

func (CopyElim) Apply(cfg *CFG)

type FuncData added in v0.1.4

type FuncData struct {
	Code     []byte
	Layout   *FuncLayout
	Liveness map[Pos]SlotSet
	StackMap map[uintptr]*rt.StackMap
}

type FuncLayout added in v0.1.4

type FuncLayout struct {
	Ins   []IrNode
	Start map[int]int
	Block map[int]*BasicBlock
}

func (*FuncLayout) String added in v0.1.4

func (self *FuncLayout) String() string

type Int65

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

func Int65i

func Int65i(v int64) Int65

func (Int65) Compare

func (self Int65) Compare(other Int65) int

func (Int65) CompareZero

func (self Int65) CompareZero() int

func (Int65) OneLess

func (self Int65) OneLess() (r Int65)

func (Int65) OneMore

func (self Int65) OneMore() (r Int65)

func (Int65) String

func (self Int65) String() string

type IrAlias added in v0.1.2

type IrAlias struct {
	R Reg
	V Reg
}

func (*IrAlias) Clone added in v0.1.2

func (self *IrAlias) Clone() IrNode

func (*IrAlias) Definitions added in v0.1.2

func (self *IrAlias) Definitions() []*Reg

func (*IrAlias) String added in v0.1.2

func (self *IrAlias) String() string

func (*IrAlias) Usages added in v0.1.2

func (self *IrAlias) Usages() []*Reg

type IrBinaryExpr

type IrBinaryExpr struct {
	R  Reg
	X  Reg
	Y  Reg
	Op IrBinaryOp
}

func (*IrBinaryExpr) Clone added in v0.1.1

func (self *IrBinaryExpr) Clone() IrNode

func (*IrBinaryExpr) Definitions added in v0.1.1

func (self *IrBinaryExpr) Definitions() []*Reg

func (*IrBinaryExpr) String

func (self *IrBinaryExpr) String() string

func (*IrBinaryExpr) Usages

func (self *IrBinaryExpr) Usages() []*Reg

type IrBinaryOp

type IrBinaryOp uint8
const (
	IrOpAdd IrBinaryOp = iota
	IrOpSub
	IrOpMul
	IrOpAnd
	IrOpOr
	IrOpXor
	IrOpShr
	IrCmpEq
	IrCmpNe
	IrCmpLt
	IrCmpLtu
	IrCmpGeu
)

func (IrBinaryOp) String

func (self IrBinaryOp) String() string

type IrBitTestSet

type IrBitTestSet struct {
	T Reg
	S Reg
	X Reg
	Y Reg
}

func (*IrBitTestSet) Clone added in v0.1.1

func (self *IrBitTestSet) Clone() IrNode

func (*IrBitTestSet) Definitions added in v0.1.1

func (self *IrBitTestSet) Definitions() []*Reg

func (*IrBitTestSet) String

func (self *IrBitTestSet) String() string

func (*IrBitTestSet) Usages

func (self *IrBitTestSet) Usages() []*Reg

type IrBranch added in v0.1.1

type IrBranch struct {
	To         *BasicBlock
	Likeliness Likeliness
}

func IrLikely added in v0.1.1

func IrLikely(bb *BasicBlock) *IrBranch

func IrUnlikely added in v0.1.1

func IrUnlikely(bb *BasicBlock) *IrBranch

func (*IrBranch) Clone added in v0.1.4

func (self *IrBranch) Clone() *IrBranch

func (*IrBranch) String added in v0.1.1

func (self *IrBranch) String() string

type IrBreakpoint

type IrBreakpoint struct{}

func (*IrBreakpoint) Clone added in v0.1.1

func (*IrBreakpoint) Clone() IrNode

func (*IrBreakpoint) String

func (*IrBreakpoint) String() string

type IrCallFunc added in v0.1.1

type IrCallFunc struct {
	R    Reg
	In   []Reg
	Out  []Reg
	Func *abi.FunctionLayout
}

func (*IrCallFunc) Clone added in v0.1.1

func (self *IrCallFunc) Clone() IrNode

func (*IrCallFunc) Definitions added in v0.1.1

func (self *IrCallFunc) Definitions() []*Reg

func (*IrCallFunc) String added in v0.1.1

func (self *IrCallFunc) String() string

func (*IrCallFunc) Usages added in v0.1.1

func (self *IrCallFunc) Usages() []*Reg

type IrCallMethod added in v0.1.1

type IrCallMethod struct {
	T    Reg
	V    Reg
	In   []Reg
	Out  []Reg
	Slot int
	Func *abi.FunctionLayout
}

func (*IrCallMethod) Clone added in v0.1.1

func (self *IrCallMethod) Clone() IrNode

func (*IrCallMethod) Definitions added in v0.1.1

func (self *IrCallMethod) Definitions() []*Reg

func (*IrCallMethod) String added in v0.1.1

func (self *IrCallMethod) String() string

func (*IrCallMethod) Usages added in v0.1.1

func (self *IrCallMethod) Usages() []*Reg

type IrCallNative added in v0.1.1

type IrCallNative struct {
	R   Reg
	In  []Reg
	Out Reg
}

func (*IrCallNative) Clone added in v0.1.1

func (self *IrCallNative) Clone() IrNode

func (*IrCallNative) Definitions added in v0.1.1

func (self *IrCallNative) Definitions() []*Reg

func (*IrCallNative) String added in v0.1.1

func (self *IrCallNative) String() string

func (*IrCallNative) Usages added in v0.1.1

func (self *IrCallNative) Usages() []*Reg

type IrClobberList added in v0.1.4

type IrClobberList struct {
	R []Reg
}

func IrMarkClobber added in v0.1.4

func IrMarkClobber(r ...Reg) *IrClobberList

func (*IrClobberList) Clone added in v0.1.4

func (self *IrClobberList) Clone() IrNode

func (*IrClobberList) String added in v0.1.4

func (self *IrClobberList) String() string

func (*IrClobberList) Usages added in v0.1.4

func (self *IrClobberList) Usages() []*Reg

type IrConstInt

type IrConstInt struct {
	R Reg
	V int64
}

func (*IrConstInt) Clone added in v0.1.1

func (self *IrConstInt) Clone() IrNode

func (*IrConstInt) Definitions added in v0.1.1

func (self *IrConstInt) Definitions() []*Reg

func (*IrConstInt) String

func (self *IrConstInt) String() string

type IrConstPtr

type IrConstPtr struct {
	R Reg
	P unsafe.Pointer
	M Constness
}

func (*IrConstPtr) Clone added in v0.1.1

func (self *IrConstPtr) Clone() IrNode

func (*IrConstPtr) Definitions added in v0.1.1

func (self *IrConstPtr) Definitions() []*Reg

func (*IrConstPtr) String

func (self *IrConstPtr) String() string

type IrDefinitions added in v0.1.1

type IrDefinitions interface {
	IrNode
	Definitions() []*Reg
}

type IrEntry added in v0.1.1

type IrEntry struct {
	R []Reg
}

func (*IrEntry) Clone added in v0.1.1

func (self *IrEntry) Clone() IrNode

func (*IrEntry) Definitions added in v0.1.1

func (self *IrEntry) Definitions() []*Reg

func (*IrEntry) String added in v0.1.1

func (self *IrEntry) String() string

type IrImmovable added in v0.1.1

type IrImmovable interface {
	IrNode
	// contains filtered or unexported methods
}

type IrImpure added in v0.1.1

type IrImpure interface {
	IrNode
	// contains filtered or unexported methods
}

type IrLEA

type IrLEA struct {
	R   Reg
	Mem Reg
	Off Reg
}

func (*IrLEA) Clone added in v0.1.1

func (self *IrLEA) Clone() IrNode

func (*IrLEA) Definitions added in v0.1.1

func (self *IrLEA) Definitions() []*Reg

func (*IrLEA) String

func (self *IrLEA) String() string

func (*IrLEA) Usages

func (self *IrLEA) Usages() []*Reg

type IrLoad

type IrLoad struct {
	R    Reg
	Mem  Reg
	Size uint8
}

func (*IrLoad) Clone added in v0.1.1

func (self *IrLoad) Clone() IrNode

func (*IrLoad) Definitions added in v0.1.1

func (self *IrLoad) Definitions() []*Reg

func (*IrLoad) String

func (self *IrLoad) String() string

func (*IrLoad) Usages

func (self *IrLoad) Usages() []*Reg

type IrLoadArg

type IrLoadArg struct {
	R Reg
	I int
}

func (*IrLoadArg) Clone added in v0.1.1

func (self *IrLoadArg) Clone() IrNode

func (*IrLoadArg) Definitions added in v0.1.1

func (self *IrLoadArg) Definitions() []*Reg

func (*IrLoadArg) String

func (self *IrLoadArg) String() string

type IrNode

type IrNode interface {
	fmt.Stringer
	Clone() IrNode
	// contains filtered or unexported methods
}

func IrCopy

func IrCopy(r Reg, v Reg) IrNode

func IrCreateSpill added in v0.1.4

func IrCreateSpill(reg Reg, id int, op IrSpillOp) IrNode

func IrCreateSpillEx added in v0.1.4

func IrCreateSpillEx(reg Reg, ptr bool, id int, op IrSpillOp) IrNode

func IrSlotGen added in v0.1.4

func IrSlotGen(s IrSpillSlot) IrNode

type IrNop added in v0.1.1

type IrNop struct{}

func (*IrNop) Clone added in v0.1.1

func (*IrNop) Clone() IrNode

func (*IrNop) String added in v0.1.1

func (*IrNop) String() string

type IrPhi

type IrPhi struct {
	R Reg
	V map[*BasicBlock]*Reg
}

func (*IrPhi) Clone added in v0.1.1

func (self *IrPhi) Clone() IrNode

func (*IrPhi) Definitions added in v0.1.1

func (self *IrPhi) Definitions() []*Reg

func (*IrPhi) String

func (self *IrPhi) String() string

func (*IrPhi) Usages

func (self *IrPhi) Usages() []*Reg

type IrReturn

type IrReturn struct {
	R []Reg
}

func (*IrReturn) Clone added in v0.1.1

func (self *IrReturn) Clone() IrNode

func (*IrReturn) String

func (self *IrReturn) String() string

func (*IrReturn) Successors

func (self *IrReturn) Successors() IrSuccessors

func (*IrReturn) Usages

func (self *IrReturn) Usages() []*Reg

type IrSlotAlive added in v0.1.4

type IrSlotAlive struct {
	S []IrSpillSlot
}

func (*IrSlotAlive) Clone added in v0.1.4

func (self *IrSlotAlive) Clone() IrNode

func (*IrSlotAlive) String added in v0.1.4

func (self *IrSlotAlive) String() string

type IrSpill added in v0.1.4

type IrSpill struct {
	R  Reg
	S  IrSpillSlot
	Op IrSpillOp
}

func (*IrSpill) Clone added in v0.1.4

func (self *IrSpill) Clone() IrNode

func (*IrSpill) Definitions added in v0.1.4

func (self *IrSpill) Definitions() []*Reg

func (*IrSpill) String added in v0.1.4

func (self *IrSpill) String() string

func (*IrSpill) Usages added in v0.1.4

func (self *IrSpill) Usages() []*Reg

type IrSpillOp added in v0.1.4

type IrSpillOp uint8
const (
	IrSpillStore IrSpillOp = iota
	IrSpillReload
)

func (IrSpillOp) String added in v0.1.4

func (self IrSpillOp) String() string

type IrSpillSlot added in v0.1.4

type IrSpillSlot uint64

func (IrSpillSlot) ID added in v0.1.4

func (self IrSpillSlot) ID() int

func (IrSpillSlot) IsPtr added in v0.1.4

func (self IrSpillSlot) IsPtr() bool

func (IrSpillSlot) String added in v0.1.4

func (self IrSpillSlot) String() string

type IrStore

type IrStore struct {
	R    Reg
	Mem  Reg
	Size uint8
}

func (*IrStore) Clone added in v0.1.1

func (self *IrStore) Clone() IrNode

func (*IrStore) String

func (self *IrStore) String() string

func (*IrStore) Usages

func (self *IrStore) Usages() []*Reg

type IrSuccessors

type IrSuccessors interface {
	Next() bool
	Block() *BasicBlock
	Value() (int32, bool)
	Likeliness() Likeliness
	UpdateBlock(bb *BasicBlock)
}

type IrSwitch

type IrSwitch struct {
	V  Reg
	Ln *IrBranch
	Br map[int32]*IrBranch
}

func (*IrSwitch) Clone added in v0.1.1

func (self *IrSwitch) Clone() IrNode

func (*IrSwitch) String

func (self *IrSwitch) String() string

func (*IrSwitch) Successors

func (self *IrSwitch) Successors() IrSuccessors

func (*IrSwitch) Usages

func (self *IrSwitch) Usages() []*Reg

type IrTerminator

type IrTerminator interface {
	IrNode
	Successors() IrSuccessors
	// contains filtered or unexported methods
}

type IrUnaryExpr

type IrUnaryExpr struct {
	R  Reg
	V  Reg
	Op IrUnaryOp
}

func (*IrUnaryExpr) Clone added in v0.1.1

func (self *IrUnaryExpr) Clone() IrNode

func (*IrUnaryExpr) Definitions added in v0.1.1

func (self *IrUnaryExpr) Definitions() []*Reg

func (*IrUnaryExpr) String

func (self *IrUnaryExpr) String() string

func (*IrUnaryExpr) Usages

func (self *IrUnaryExpr) Usages() []*Reg

type IrUnaryOp

type IrUnaryOp uint8
const (
	IrOpNegate IrUnaryOp = iota
	IrOpSwap16
	IrOpSwap32
	IrOpSwap64
	IrOpSx32to64
)

func (IrUnaryOp) String

func (self IrUnaryOp) String() string

type IrUsages

type IrUsages interface {
	IrNode
	Usages() []*Reg
}

type IrWriteBarrier

type IrWriteBarrier struct {
	R   Reg
	M   Reg
	Fn  Reg
	Var Reg
}

func (*IrWriteBarrier) Clone added in v0.1.1

func (self *IrWriteBarrier) Clone() IrNode

func (*IrWriteBarrier) String

func (self *IrWriteBarrier) String() string

func (*IrWriteBarrier) Usages

func (self *IrWriteBarrier) Usages() []*Reg

type Layout added in v0.1.4

type Layout struct{}

Layout flattens the CFG into a linear FuncLayout

func (Layout) Apply added in v0.1.4

func (self Layout) Apply(cfg *CFG)

type Likeliness added in v0.1.1

type Likeliness uint8
const (
	Likely Likeliness = iota
	Unlikely
)

func (Likeliness) String added in v0.1.1

func (self Likeliness) String() string

type Pass

type Pass interface {
	Apply(*CFG)
}

type PassDescriptor

type PassDescriptor struct {
	Pass Pass
	Name string
}

type PhiElim

type PhiElim struct{}

PhiElim transforms Phi nodes into copies if possible.

func (PhiElim) Apply

func (self PhiElim) Apply(cfg *CFG)

type PhiProp added in v0.1.2

type PhiProp struct{}

PhiProp propagates Phi nodes into it's source blocks, essentially get rid of them. The CFG is no longer in SSA form after this pass.

func (PhiProp) Apply added in v0.1.2

func (self PhiProp) Apply(cfg *CFG)

type Pos added in v0.1.4

type Pos struct {
	B *BasicBlock
	I int
}

func (Pos) String added in v0.1.4

func (self Pos) String() string

type Reduce added in v0.1.1

type Reduce struct{}

Reduce combines CSE, PhiElim, CopyElim and TDCE.

func (Reduce) Apply added in v0.1.1

func (Reduce) Apply(cfg *CFG)

type Reg

type Reg uint64
const (
	Rz Reg = (0 << _B_ptr) | (K_zero << _B_kind)
	Pn Reg = (1 << _B_ptr) | (K_zero << _B_kind)
)

func Pr

func Pr(i int) Reg

func Rv

func Rv(reg hir.Register) Reg

func Tr

func Tr(i int) Reg

func (Reg) Derive added in v0.1.1

func (self Reg) Derive(i int) Reg

func (Reg) Index

func (self Reg) Index() int

func (Reg) Kind added in v0.1.1

func (self Reg) Kind() int

func (Reg) Name added in v0.1.1

func (self Reg) Name() int

func (Reg) Normalize added in v0.1.1

func (self Reg) Normalize(i int) Reg

func (Reg) Ptr

func (self Reg) Ptr() bool

func (Reg) String

func (self Reg) String() string

func (Reg) Zero added in v0.1.1

func (self Reg) Zero() Reg

type RegAlloc added in v0.1.1

type RegAlloc struct{}

RegAlloc performs register allocation on CFG.

func (RegAlloc) Apply added in v0.1.1

func (self RegAlloc) Apply(cfg *CFG)

type Rematerialize added in v0.1.4

type Rematerialize struct{}

Rematerialize recalculates simple values to reduce register pressure.

func (Rematerialize) Apply added in v0.1.4

func (Rematerialize) Apply(cfg *CFG)

type Reorder added in v0.1.1

type Reorder struct{}

Reorder moves value closer to it's usage, which reduces register pressure.

func (Reorder) Apply added in v0.1.1

func (self Reorder) Apply(cfg *CFG)

type ReturnSpread added in v0.1.1

type ReturnSpread struct{}

ReturnSpread spreads the return block to all it's successors, in order to shorten register live ranges.

func (ReturnSpread) Apply added in v0.1.1

func (ReturnSpread) Apply(cfg *CFG)

type SlotSet added in v0.1.4

type SlotSet map[IrSpillSlot]struct{}

func (SlotSet) String added in v0.1.4

func (self SlotSet) String() string

type SplitCritical added in v0.1.4

type SplitCritical struct{}

SplitCritical splits critical edges (those that go from a block with more than one outedge to a block with more than one inedge) by inserting an empty block.

PhiProp wants a critical-edge-free CFG so it can safely remove Phi nodes for RegAlloc.

func (SplitCritical) Apply added in v0.1.4

func (SplitCritical) Apply(cfg *CFG)

type StackLiveness added in v0.1.4

type StackLiveness struct{}

StackLiveness calculates the liveness of each stack slot.

func (StackLiveness) Apply added in v0.1.4

func (self StackLiveness) Apply(cfg *CFG)

type TDCE

type TDCE struct{}

TDCE removes trivial dead-code such as unused register definations from CFG.

func (TDCE) Apply

func (TDCE) Apply(cfg *CFG)

type ZeroReg added in v0.1.1

type ZeroReg struct{}

ZeroReg replaces read to %z or %nil to a register that was initialized to zero for architectures that does not have constant zero registers, such as `x86_64`.

func (ZeroReg) Apply added in v0.1.1

func (self ZeroReg) Apply(cfg *CFG)

Jump to

Keyboard shortcuts

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