const debugLifting … type domFrontier … func (df domFrontier) add(u, v *BasicBlock) { … } // build builds the dominance frontier df for the dominator (sub)tree // rooted at u, using the Cytron et al. algorithm. // // TODO(adonovan): opt: consider Berlin approach, computing pruned SSA // by pruning the entire IDF computation, rather than merely pruning // the DF -> IDF step. func (df domFrontier) build(u *BasicBlock) { … } func buildDomFrontier(fn *Function) domFrontier { … } func removeInstr(refs []Instruction, instr Instruction) []Instruction { … } func removeInstrsIf(refs []Instruction, p func(Instruction) bool) []Instruction { … } // lift replaces local and new Allocs accessed only with // load/store by SSA registers, inserting φ-nodes where necessary. // The result is a program in classical pruned SSA form. // // Preconditions: // - fn has no dead blocks (blockopt has run). // - Def/use info (Operands and Referrers) is up-to-date. // - The dominator tree is up-to-date. func lift(fn *Function) { … } // removeDeadPhis removes φ-nodes not transitively needed by a // non-Phi, non-DebugRef instruction. func removeDeadPhis(blocks []*BasicBlock, newPhis newPhiMap) { … } // markLivePhi marks phi, and all φ-nodes transitively reachable via // its Operands, live. func markLivePhi(livePhis map[*Phi]bool, phi *Phi) { … } // phiHasDirectReferrer reports whether phi is directly referred to by // a non-Phi instruction. Such instructions are the // roots of the liveness traversal. func phiHasDirectReferrer(phi *Phi) bool { … } type blockSet … // add adds b to the set and returns true if the set changed. func (s *blockSet) add(b *BasicBlock) bool { … } // take removes an arbitrary element from a set s and // returns its index, or returns -1 if empty. func (s *blockSet) take() int { … } type newPhi … type newPhiMap … // liftAlloc determines whether alloc can be lifted into registers, // and if so, it populates newPhis with all the φ-nodes it may require // and returns true. // // fresh is a source of fresh ids for phi nodes. func liftAlloc(df domFrontier, alloc *Alloc, newPhis newPhiMap, fresh *int) bool { … } // replaceAll replaces all intraprocedural uses of x with y, // updating x.Referrers and y.Referrers. // Precondition: x.Referrers() != nil, i.e. x must be local to some function. func replaceAll(x, y Value) { … } // renamed returns the value to which alloc is being renamed, // constructing it lazily if it's the implicit zero initialization. func renamed(renaming []Value, alloc *Alloc) Value { … } // rename implements the (Cytron et al) SSA renaming algorithm, a // preorder traversal of the dominator tree replacing all loads of // Alloc cells with the value stored to that cell by the dominating // store instruction. For lifting, we need only consider loads, // stores and φ-nodes. // // renaming is a map from *Alloc (keyed by index number) to its // dominating stored value; newPhis[x] is the set of new φ-nodes to be // prepended to block x. func rename(u *BasicBlock, renaming []Value, newPhis newPhiMap) { … } // deferstackPreamble returns the *Alloc and ssa:deferstack() call for fn.deferstack. func deferstackPreamble(fn *Function) (*Alloc, *Call) { … }