gotools/go/ssa/dom.go

// Idom returns the block that immediately dominates b:
// its parent in the dominator tree, if any.
// Neither the entry node (b.Index==0) nor recover node
// (b==b.Parent().Recover()) have a parent.
func (b *BasicBlock) Idom() *BasicBlock { … }

// Dominees returns the list of blocks that b immediately dominates:
// its children in the dominator tree.
func (b *BasicBlock) Dominees() []*BasicBlock { … }

// Dominates reports whether b dominates c.
func (b *BasicBlock) Dominates(c *BasicBlock) bool { … }

// DomPreorder returns a new slice containing the blocks of f
// in a preorder traversal of the dominator tree.
func (f *Function) DomPreorder() []*BasicBlock { … }

// DomPostorder returns a new slice containing the blocks of f
// in a postorder traversal of the dominator tree.
// (This is not the same as a postdominance order.)
func (f *Function) DomPostorder() []*BasicBlock { … }

type domInfo …

type ltState …

// dfs implements the depth-first search part of the LT algorithm.
func (lt *ltState) dfs(v *BasicBlock, i int32, preorder []*BasicBlock) int32 { … }

// eval implements the EVAL part of the LT algorithm.
func (lt *ltState) eval(v *BasicBlock) *BasicBlock { … }

// link implements the LINK part of the LT algorithm.
func (lt *ltState) link(v, w *BasicBlock) { … }

// buildDomTree computes the dominator tree of f using the LT algorithm.
// Precondition: all blocks are reachable (e.g. optimizeBlocks has been run).
func buildDomTree(f *Function) { … }

// numberDomTree sets the pre- and post-order numbers of a depth-first
// traversal of the dominator tree rooted at v.  These are used to
// answer dominance queries in constant time.
func numberDomTree(v *BasicBlock, pre, post int32) (int32, int32) { … }

// sanityCheckDomTree checks the correctness of the dominator tree
// computed by the LT algorithm by comparing against the dominance
// relation computed by a naive Kildall-style forward dataflow
// analysis (Algorithm 10.16 from the "Dragon" book).
func sanityCheckDomTree(f *Function) { … }

// printDomTreeText prints the dominator tree as text, using indentation.
func printDomTreeText(buf *bytes.Buffer, v *BasicBlock, indent int) { … }

// printDomTreeDot prints the dominator tree of f in AT&T GraphViz
// (.dot) format.
func printDomTreeDot(buf *bytes.Buffer, f *Function) { … }