go/src/cmd/compile/internal/ssa/sparsetree.go

type SparseTreeNode …

func (s *SparseTreeNode) String() string { … }

func (s *SparseTreeNode) Entry() int32 { … }

func (s *SparseTreeNode) Exit() int32 { … }

const AdjustBefore …

const AdjustWithin …

const AdjustAfter …

type SparseTree …

// newSparseTree creates a SparseTree from a block-to-parent map (array indexed by Block.ID).
func newSparseTree(f *Func, parentOf []*Block) SparseTree { … }

// newSparseOrderedTree creates a SparseTree from a block-to-parent map (array indexed by Block.ID)
// children will appear in the reverse of their order in reverseOrder
// in particular, if reverseOrder is a dfs-reversePostOrder, then the root-to-children
// walk of the tree will yield a pre-order.
func newSparseOrderedTree(f *Func, parentOf, reverseOrder []*Block) SparseTree { … }

// treestructure provides a string description of the dominator
// tree and flow structure of block b and all blocks that it
// dominates.
func (t SparseTree) treestructure(b *Block) string { … }

func (t SparseTree) treestructure1(b *Block, i int) string { … }

func (t SparseTree) numberBlock(b *Block, n int32) int32 { … }

// Sibling returns a sibling of x in the dominator tree (i.e.,
// a node with the same immediate dominator) or nil if there
// are no remaining siblings in the arbitrary but repeatable
// order chosen. Because the Child-Sibling order is used
// to assign entry and exit numbers in the treewalk, those
// numbers are also consistent with this order (i.e.,
// Sibling(x) has entry number larger than x's exit number).
func (t SparseTree) Sibling(x *Block) *Block { … }

// Child returns a child of x in the dominator tree, or
// nil if there are none. The choice of first child is
// arbitrary but repeatable.
func (t SparseTree) Child(x *Block) *Block { … }

// Parent returns the parent of x in the dominator tree, or
// nil if x is the function's entry.
func (t SparseTree) Parent(x *Block) *Block { … }

// IsAncestorEq reports whether x is an ancestor of or equal to y.
func (t SparseTree) IsAncestorEq(x, y *Block) bool { … }

// isAncestor reports whether x is a strict ancestor of y.
func (t SparseTree) isAncestor(x, y *Block) bool { … }

// domorder returns a value for dominator-oriented sorting.
// Block domination does not provide a total ordering,
// but domorder two has useful properties.
//  1. If domorder(x) > domorder(y) then x does not dominate y.
//  2. If domorder(x) < domorder(y) and domorder(y) < domorder(z) and x does not dominate y,
//     then x does not dominate z.
//
// Property (1) means that blocks sorted by domorder always have a maximal dominant block first.
// Property (2) allows searches for dominated blocks to exit early.
func (t SparseTree) domorder(x *Block) int32 { … }