+++ /dev/null
-// Copyright 2013 The Go Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-package ssa
-
-// This file defines the lifting pass which tries to "lift" Alloc
-// cells (new/local variables) into SSA registers, replacing loads
-// with the dominating stored value, eliminating loads and stores, and
-// inserting φ-nodes as needed.
-
-// Cited papers and resources:
-//
-// Ron Cytron et al. 1991. Efficiently computing SSA form...
-// http://doi.acm.org/10.1145/115372.115320
-//
-// Cooper, Harvey, Kennedy. 2001. A Simple, Fast Dominance Algorithm.
-// Software Practice and Experience 2001, 4:1-10.
-// http://www.hipersoft.rice.edu/grads/publications/dom14.pdf
-//
-// Daniel Berlin, llvmdev mailing list, 2012.
-// http://lists.cs.uiuc.edu/pipermail/llvmdev/2012-January/046638.html
-// (Be sure to expand the whole thread.)
-
-// TODO(adonovan): opt: there are many optimizations worth evaluating, and
-// the conventional wisdom for SSA construction is that a simple
-// algorithm well engineered often beats those of better asymptotic
-// complexity on all but the most egregious inputs.
-//
-// Danny Berlin suggests that the Cooper et al. algorithm for
-// computing the dominance frontier is superior to Cytron et al.
-// Furthermore he recommends that rather than computing the DF for the
-// whole function then renaming all alloc cells, it may be cheaper to
-// compute the DF for each alloc cell separately and throw it away.
-//
-// Consider exploiting liveness information to avoid creating dead
-// φ-nodes which we then immediately remove.
-//
-// Also see many other "TODO: opt" suggestions in the code.
-
-import (
- "fmt"
- "go/token"
- "go/types"
- "math/big"
- "os"
-)
-
-// If true, show diagnostic information at each step of lifting.
-// Very verbose.
-const debugLifting = false
-
-// domFrontier maps each block to the set of blocks in its dominance
-// frontier. The outer slice is conceptually a map keyed by
-// Block.Index. The inner slice is conceptually a set, possibly
-// containing duplicates.
-//
-// TODO(adonovan): opt: measure impact of dups; consider a packed bit
-// representation, e.g. big.Int, and bitwise parallel operations for
-// the union step in the Children loop.
-//
-// domFrontier's methods mutate the slice's elements but not its
-// length, so their receivers needn't be pointers.
-//
-type domFrontier [][]*BasicBlock
-
-func (df domFrontier) add(u, v *BasicBlock) {
- p := &df[u.Index]
- *p = append(*p, v)
-}
-
-// 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) {
- // Encounter each node u in postorder of dom tree.
- for _, child := range u.dom.children {
- df.build(child)
- }
- for _, vb := range u.Succs {
- if v := vb.dom; v.idom != u {
- df.add(u, vb)
- }
- }
- for _, w := range u.dom.children {
- for _, vb := range df[w.Index] {
- // TODO(adonovan): opt: use word-parallel bitwise union.
- if v := vb.dom; v.idom != u {
- df.add(u, vb)
- }
- }
- }
-}
-
-func buildDomFrontier(fn *Function) domFrontier {
- df := make(domFrontier, len(fn.Blocks))
- df.build(fn.Blocks[0])
- if fn.Recover != nil {
- df.build(fn.Recover)
- }
- return df
-}
-
-func removeInstr(refs []Instruction, instr Instruction) []Instruction {
- i := 0
- for _, ref := range refs {
- if ref == instr {
- continue
- }
- refs[i] = ref
- i++
- }
- for j := i; j != len(refs); j++ {
- refs[j] = nil // aid GC
- }
- return refs[:i]
-}
-
-// 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) {
- // TODO(adonovan): opt: lots of little optimizations may be
- // worthwhile here, especially if they cause us to avoid
- // buildDomFrontier. For example:
- //
- // - Alloc never loaded? Eliminate.
- // - Alloc never stored? Replace all loads with a zero constant.
- // - Alloc stored once? Replace loads with dominating store;
- // don't forget that an Alloc is itself an effective store
- // of zero.
- // - Alloc used only within a single block?
- // Use degenerate algorithm avoiding φ-nodes.
- // - Consider synergy with scalar replacement of aggregates (SRA).
- // e.g. *(&x.f) where x is an Alloc.
- // Perhaps we'd get better results if we generated this as x.f
- // i.e. Field(x, .f) instead of Load(FieldIndex(x, .f)).
- // Unclear.
- //
- // But we will start with the simplest correct code.
- df := buildDomFrontier(fn)
-
- if debugLifting {
- title := false
- for i, blocks := range df {
- if blocks != nil {
- if !title {
- fmt.Fprintf(os.Stderr, "Dominance frontier of %s:\n", fn)
- title = true
- }
- fmt.Fprintf(os.Stderr, "\t%s: %s\n", fn.Blocks[i], blocks)
- }
- }
- }
-
- newPhis := make(newPhiMap)
-
- // During this pass we will replace some BasicBlock.Instrs
- // (allocs, loads and stores) with nil, keeping a count in
- // BasicBlock.gaps. At the end we will reset Instrs to the
- // concatenation of all non-dead newPhis and non-nil Instrs
- // for the block, reusing the original array if space permits.
-
- // While we're here, we also eliminate 'rundefers'
- // instructions in functions that contain no 'defer'
- // instructions.
- usesDefer := false
-
- // A counter used to generate ~unique ids for Phi nodes, as an
- // aid to debugging. We use large numbers to make them highly
- // visible. All nodes are renumbered later.
- fresh := 1000
-
- // Determine which allocs we can lift and number them densely.
- // The renaming phase uses this numbering for compact maps.
- numAllocs := 0
- for _, b := range fn.Blocks {
- b.gaps = 0
- b.rundefers = 0
- for _, instr := range b.Instrs {
- switch instr := instr.(type) {
- case *Alloc:
- index := -1
- if liftAlloc(df, instr, newPhis, &fresh) {
- index = numAllocs
- numAllocs++
- }
- instr.index = index
- case *Defer:
- usesDefer = true
- case *RunDefers:
- b.rundefers++
- }
- }
- }
-
- // renaming maps an alloc (keyed by index) to its replacement
- // value. Initially the renaming contains nil, signifying the
- // zero constant of the appropriate type; we construct the
- // Const lazily at most once on each path through the domtree.
- // TODO(adonovan): opt: cache per-function not per subtree.
- renaming := make([]Value, numAllocs)
-
- // Renaming.
- rename(fn.Blocks[0], renaming, newPhis)
-
- // Eliminate dead φ-nodes.
- removeDeadPhis(fn.Blocks, newPhis)
-
- // Prepend remaining live φ-nodes to each block.
- for _, b := range fn.Blocks {
- nps := newPhis[b]
- j := len(nps)
-
- rundefersToKill := b.rundefers
- if usesDefer {
- rundefersToKill = 0
- }
-
- if j+b.gaps+rundefersToKill == 0 {
- continue // fast path: no new phis or gaps
- }
-
- // Compact nps + non-nil Instrs into a new slice.
- // TODO(adonovan): opt: compact in situ (rightwards)
- // if Instrs has sufficient space or slack.
- dst := make([]Instruction, len(b.Instrs)+j-b.gaps-rundefersToKill)
- for i, np := range nps {
- dst[i] = np.phi
- }
- for _, instr := range b.Instrs {
- if instr == nil {
- continue
- }
- if !usesDefer {
- if _, ok := instr.(*RunDefers); ok {
- continue
- }
- }
- dst[j] = instr
- j++
- }
- b.Instrs = dst
- }
-
- // Remove any fn.Locals that were lifted.
- j := 0
- for _, l := range fn.Locals {
- if l.index < 0 {
- fn.Locals[j] = l
- j++
- }
- }
- // Nil out fn.Locals[j:] to aid GC.
- for i := j; i < len(fn.Locals); i++ {
- fn.Locals[i] = nil
- }
- fn.Locals = fn.Locals[:j]
-}
-
-// removeDeadPhis removes φ-nodes not transitively needed by a
-// non-Phi, non-DebugRef instruction.
-func removeDeadPhis(blocks []*BasicBlock, newPhis newPhiMap) {
- // First pass: find the set of "live" φ-nodes: those reachable
- // from some non-Phi instruction.
- //
- // We compute reachability in reverse, starting from each φ,
- // rather than forwards, starting from each live non-Phi
- // instruction, because this way visits much less of the
- // Value graph.
- livePhis := make(map[*Phi]bool)
- for _, npList := range newPhis {
- for _, np := range npList {
- phi := np.phi
- if !livePhis[phi] && phiHasDirectReferrer(phi) {
- markLivePhi(livePhis, phi)
- }
- }
- }
-
- // Existing φ-nodes due to && and || operators
- // are all considered live (see Go issue 19622).
- for _, b := range blocks {
- for _, phi := range b.phis() {
- markLivePhi(livePhis, phi.(*Phi))
- }
- }
-
- // Second pass: eliminate unused phis from newPhis.
- for block, npList := range newPhis {
- j := 0
- for _, np := range npList {
- if livePhis[np.phi] {
- npList[j] = np
- j++
- } else {
- // discard it, first removing it from referrers
- for _, val := range np.phi.Edges {
- if refs := val.Referrers(); refs != nil {
- *refs = removeInstr(*refs, np.phi)
- }
- }
- np.phi.block = nil
- }
- }
- newPhis[block] = npList[:j]
- }
-}
-
-// markLivePhi marks phi, and all φ-nodes transitively reachable via
-// its Operands, live.
-func markLivePhi(livePhis map[*Phi]bool, phi *Phi) {
- livePhis[phi] = true
- for _, rand := range phi.Operands(nil) {
- if q, ok := (*rand).(*Phi); ok {
- if !livePhis[q] {
- markLivePhi(livePhis, q)
- }
- }
- }
-}
-
-// 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 {
- for _, instr := range *phi.Referrers() {
- if _, ok := instr.(*Phi); !ok {
- return true
- }
- }
- return false
-}
-
-type blockSet struct{ big.Int } // (inherit methods from Int)
-
-// add adds b to the set and returns true if the set changed.
-func (s *blockSet) add(b *BasicBlock) bool {
- i := b.Index
- if s.Bit(i) != 0 {
- return false
- }
- s.SetBit(&s.Int, i, 1)
- return true
-}
-
-// take removes an arbitrary element from a set s and
-// returns its index, or returns -1 if empty.
-func (s *blockSet) take() int {
- l := s.BitLen()
- for i := 0; i < l; i++ {
- if s.Bit(i) == 1 {
- s.SetBit(&s.Int, i, 0)
- return i
- }
- }
- return -1
-}
-
-// newPhi is a pair of a newly introduced φ-node and the lifted Alloc
-// it replaces.
-type newPhi struct {
- phi *Phi
- alloc *Alloc
-}
-
-// newPhiMap records for each basic block, the set of newPhis that
-// must be prepended to the block.
-type newPhiMap map[*BasicBlock][]newPhi
-
-// 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 {
- // Don't lift aggregates into registers, because we don't have
- // a way to express their zero-constants.
- switch deref(alloc.Type()).Underlying().(type) {
- case *types.Array, *types.Struct:
- return false
- }
-
- // Don't lift named return values in functions that defer
- // calls that may recover from panic.
- if fn := alloc.Parent(); fn.Recover != nil {
- for _, nr := range fn.namedResults {
- if nr == alloc {
- return false
- }
- }
- }
-
- // Compute defblocks, the set of blocks containing a
- // definition of the alloc cell.
- var defblocks blockSet
- for _, instr := range *alloc.Referrers() {
- // Bail out if we discover the alloc is not liftable;
- // the only operations permitted to use the alloc are
- // loads/stores into the cell, and DebugRef.
- switch instr := instr.(type) {
- case *Store:
- if instr.Val == alloc {
- return false // address used as value
- }
- if instr.Addr != alloc {
- panic("Alloc.Referrers is inconsistent")
- }
- defblocks.add(instr.Block())
- case *UnOp:
- if instr.Op != token.MUL {
- return false // not a load
- }
- if instr.X != alloc {
- panic("Alloc.Referrers is inconsistent")
- }
- case *DebugRef:
- // ok
- default:
- return false // some other instruction
- }
- }
- // The Alloc itself counts as a (zero) definition of the cell.
- defblocks.add(alloc.Block())
-
- if debugLifting {
- fmt.Fprintln(os.Stderr, "\tlifting ", alloc, alloc.Name())
- }
-
- fn := alloc.Parent()
-
- // Φ-insertion.
- //
- // What follows is the body of the main loop of the insert-φ
- // function described by Cytron et al, but instead of using
- // counter tricks, we just reset the 'hasAlready' and 'work'
- // sets each iteration. These are bitmaps so it's pretty cheap.
- //
- // TODO(adonovan): opt: recycle slice storage for W,
- // hasAlready, defBlocks across liftAlloc calls.
- var hasAlready blockSet
-
- // Initialize W and work to defblocks.
- var work blockSet = defblocks // blocks seen
- var W blockSet // blocks to do
- W.Set(&defblocks.Int)
-
- // Traverse iterated dominance frontier, inserting φ-nodes.
- for i := W.take(); i != -1; i = W.take() {
- u := fn.Blocks[i]
- for _, v := range df[u.Index] {
- if hasAlready.add(v) {
- // Create φ-node.
- // It will be prepended to v.Instrs later, if needed.
- phi := &Phi{
- Edges: make([]Value, len(v.Preds)),
- Comment: alloc.Comment,
- }
- // This is merely a debugging aid:
- phi.setNum(*fresh)
- *fresh++
-
- phi.pos = alloc.Pos()
- phi.setType(deref(alloc.Type()))
- phi.block = v
- if debugLifting {
- fmt.Fprintf(os.Stderr, "\tplace %s = %s at block %s\n", phi.Name(), phi, v)
- }
- newPhis[v] = append(newPhis[v], newPhi{phi, alloc})
-
- if work.add(v) {
- W.add(v)
- }
- }
- }
- }
-
- return true
-}
-
-// 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) {
- var rands []*Value
- pxrefs := x.Referrers()
- pyrefs := y.Referrers()
- for _, instr := range *pxrefs {
- rands = instr.Operands(rands[:0]) // recycle storage
- for _, rand := range rands {
- if *rand != nil {
- if *rand == x {
- *rand = y
- }
- }
- }
- if pyrefs != nil {
- *pyrefs = append(*pyrefs, instr) // dups ok
- }
- }
- *pxrefs = nil // x is now unreferenced
-}
-
-// 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 {
- v := renaming[alloc.index]
- if v == nil {
- v = zeroConst(deref(alloc.Type()))
- renaming[alloc.index] = v
- }
- return v
-}
-
-// 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) {
- // Each φ-node becomes the new name for its associated Alloc.
- for _, np := range newPhis[u] {
- phi := np.phi
- alloc := np.alloc
- renaming[alloc.index] = phi
- }
-
- // Rename loads and stores of allocs.
- for i, instr := range u.Instrs {
- switch instr := instr.(type) {
- case *Alloc:
- if instr.index >= 0 { // store of zero to Alloc cell
- // Replace dominated loads by the zero value.
- renaming[instr.index] = nil
- if debugLifting {
- fmt.Fprintf(os.Stderr, "\tkill alloc %s\n", instr)
- }
- // Delete the Alloc.
- u.Instrs[i] = nil
- u.gaps++
- }
-
- case *Store:
- if alloc, ok := instr.Addr.(*Alloc); ok && alloc.index >= 0 { // store to Alloc cell
- // Replace dominated loads by the stored value.
- renaming[alloc.index] = instr.Val
- if debugLifting {
- fmt.Fprintf(os.Stderr, "\tkill store %s; new value: %s\n",
- instr, instr.Val.Name())
- }
- // Remove the store from the referrer list of the stored value.
- if refs := instr.Val.Referrers(); refs != nil {
- *refs = removeInstr(*refs, instr)
- }
- // Delete the Store.
- u.Instrs[i] = nil
- u.gaps++
- }
-
- case *UnOp:
- if instr.Op == token.MUL {
- if alloc, ok := instr.X.(*Alloc); ok && alloc.index >= 0 { // load of Alloc cell
- newval := renamed(renaming, alloc)
- if debugLifting {
- fmt.Fprintf(os.Stderr, "\tupdate load %s = %s with %s\n",
- instr.Name(), instr, newval.Name())
- }
- // Replace all references to
- // the loaded value by the
- // dominating stored value.
- replaceAll(instr, newval)
- // Delete the Load.
- u.Instrs[i] = nil
- u.gaps++
- }
- }
-
- case *DebugRef:
- if alloc, ok := instr.X.(*Alloc); ok && alloc.index >= 0 { // ref of Alloc cell
- if instr.IsAddr {
- instr.X = renamed(renaming, alloc)
- instr.IsAddr = false
-
- // Add DebugRef to instr.X's referrers.
- if refs := instr.X.Referrers(); refs != nil {
- *refs = append(*refs, instr)
- }
- } else {
- // A source expression denotes the address
- // of an Alloc that was optimized away.
- instr.X = nil
-
- // Delete the DebugRef.
- u.Instrs[i] = nil
- u.gaps++
- }
- }
- }
- }
-
- // For each φ-node in a CFG successor, rename the edge.
- for _, v := range u.Succs {
- phis := newPhis[v]
- if len(phis) == 0 {
- continue
- }
- i := v.predIndex(u)
- for _, np := range phis {
- phi := np.phi
- alloc := np.alloc
- newval := renamed(renaming, alloc)
- if debugLifting {
- fmt.Fprintf(os.Stderr, "\tsetphi %s edge %s -> %s (#%d) (alloc=%s) := %s\n",
- phi.Name(), u, v, i, alloc.Name(), newval.Name())
- }
- phi.Edges[i] = newval
- if prefs := newval.Referrers(); prefs != nil {
- *prefs = append(*prefs, phi)
- }
- }
- }
-
- // Continue depth-first recursion over domtree, pushing a
- // fresh copy of the renaming map for each subtree.
- for i, v := range u.dom.children {
- r := renaming
- if i < len(u.dom.children)-1 {
- // On all but the final iteration, we must make
- // a copy to avoid destructive update.
- r = make([]Value, len(renaming))
- copy(r, renaming)
- }
- rename(v, r, newPhis)
- }
-
-}
projects / dotfiles / .git / blobdiff