--- /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 ir
+
+// 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 φ- and σ-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.)
+//
+// C. Scott Ananian. 1997. The static single information form.
+//
+// Jeremy Singer. 2006. Static program analysis based on virtual register renaming.
+
+// 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/types"
+ "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) {
+ df[u.Index] = append(df[u.Index], v)
+}
+
+// build builds the dominance frontier df for the dominator tree of
+// fn, using the algorithm found in A Simple, Fast Dominance
+// Algorithm, Figure 5.
+//
+// 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(fn *Function) {
+ for _, b := range fn.Blocks {
+ if len(b.Preds) >= 2 {
+ for _, p := range b.Preds {
+ runner := p
+ for runner != b.dom.idom {
+ df.add(runner, b)
+ runner = runner.dom.idom
+ }
+ }
+ }
+ }
+}
+
+func buildDomFrontier(fn *Function) domFrontier {
+ df := make(domFrontier, len(fn.Blocks))
+ df.build(fn)
+ return df
+}
+
+type postDomFrontier [][]*BasicBlock
+
+func (rdf postDomFrontier) add(u, v *BasicBlock) {
+ rdf[u.Index] = append(rdf[u.Index], v)
+}
+
+func (rdf postDomFrontier) build(fn *Function) {
+ for _, b := range fn.Blocks {
+ if len(b.Succs) >= 2 {
+ for _, s := range b.Succs {
+ runner := s
+ for runner != b.pdom.idom {
+ rdf.add(runner, b)
+ runner = runner.pdom.idom
+ }
+ }
+ }
+ }
+}
+
+func buildPostDomFrontier(fn *Function) postDomFrontier {
+ rdf := make(postDomFrontier, len(fn.Blocks))
+ rdf.build(fn)
+ return rdf
+}
+
+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]
+}
+
+func clearInstrs(instrs []Instruction) {
+ for i := range instrs {
+ instrs[i] = nil
+ }
+}
+
+// lift replaces local and new Allocs accessed only with
+// load/store by IR registers, inserting φ- and σ-nodes where necessary.
+// The result is a program in pruned SSI 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.
+ var df domFrontier
+ var rdf postDomFrontier
+ var closure *closure
+ var newPhis newPhiMap
+ var newSigmas newSigmaMap
+
+ // 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
+
+ // 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:
+ if !liftable(instr) {
+ instr.index = -1
+ continue
+ }
+ index := -1
+ if numAllocs == 0 {
+ df = buildDomFrontier(fn)
+ rdf = buildPostDomFrontier(fn)
+ if len(fn.Blocks) > 2 {
+ closure = transitiveClosure(fn)
+ }
+ newPhis = make(newPhiMap, len(fn.Blocks))
+ newSigmas = make(newSigmaMap, len(fn.Blocks))
+
+ 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)
+ }
+ }
+ }
+ }
+ liftAlloc(closure, df, rdf, instr, newPhis, newSigmas)
+ index = numAllocs
+ numAllocs++
+ instr.index = index
+ case *Defer:
+ usesDefer = true
+ case *RunDefers:
+ b.rundefers++
+ }
+ }
+ }
+
+ if numAllocs > 0 {
+ // 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, newSigmas)
+
+ simplifyPhis(newPhis)
+
+ // Eliminate dead φ- and σ-nodes.
+ markLiveNodes(fn.Blocks, newPhis, newSigmas)
+ }
+
+ // Prepend remaining live φ-nodes to each block and possibly kill rundefers.
+ for _, b := range fn.Blocks {
+ var head []Instruction
+ if numAllocs > 0 {
+ nps := newPhis[b.Index]
+ head = make([]Instruction, 0, len(nps))
+ for _, pred := range b.Preds {
+ nss := newSigmas[pred.Index]
+ idx := pred.succIndex(b)
+ for _, newSigma := range nss {
+ if sigma := newSigma.sigmas[idx]; sigma != nil && sigma.live {
+ head = append(head, sigma)
+
+ // we didn't populate referrers before, as most
+ // sigma nodes will be killed
+ if refs := sigma.X.Referrers(); refs != nil {
+ *refs = append(*refs, sigma)
+ }
+ } else if sigma != nil {
+ sigma.block = nil
+ }
+ }
+ }
+ for _, np := range nps {
+ if np.phi.live {
+ head = append(head, np.phi)
+ } else {
+ for _, edge := range np.phi.Edges {
+ if refs := edge.Referrers(); refs != nil {
+ *refs = removeInstr(*refs, np.phi)
+ }
+ }
+ np.phi.block = nil
+ }
+ }
+ }
+
+ rundefersToKill := b.rundefers
+ if usesDefer {
+ rundefersToKill = 0
+ }
+
+ j := len(head)
+ if j+b.gaps+rundefersToKill == 0 {
+ continue // fast path: no new phis or gaps
+ }
+
+ // We could do straight copies instead of element-wise copies
+ // when both b.gaps and rundefersToKill are zero. However,
+ // that seems to only be the case ~1% of the time, which
+ // doesn't seem worth the extra branch.
+
+ // Remove dead instructions, add phis and sigmas
+ ns := len(b.Instrs) + j - b.gaps - rundefersToKill
+ if ns <= cap(b.Instrs) {
+ // b.Instrs has enough capacity to store all instructions
+
+ // OPT(dh): check cap vs the actually required space; if
+ // there is a big enough difference, it may be worth
+ // allocating a new slice, to avoid pinning memory.
+ dst := b.Instrs[:cap(b.Instrs)]
+ i := len(dst) - 1
+ for n := len(b.Instrs) - 1; n >= 0; n-- {
+ instr := dst[n]
+ if instr == nil {
+ continue
+ }
+ if !usesDefer {
+ if _, ok := instr.(*RunDefers); ok {
+ continue
+ }
+ }
+ dst[i] = instr
+ i--
+ }
+ off := i + 1 - len(head)
+ // aid GC
+ clearInstrs(dst[:off])
+ dst = dst[off:]
+ copy(dst, head)
+ b.Instrs = dst
+ } else {
+ // not enough space, so allocate a new slice and copy
+ // over.
+ dst := make([]Instruction, ns)
+ copy(dst, head)
+
+ 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]
+}
+
+func hasDirectReferrer(instr Instruction) bool {
+ for _, instr := range *instr.Referrers() {
+ switch instr.(type) {
+ case *Phi, *Sigma:
+ // ignore
+ default:
+ return true
+ }
+ }
+ return false
+}
+
+func markLiveNodes(blocks []*BasicBlock, newPhis newPhiMap, newSigmas newSigmaMap) {
+ // Phi and sigma nodes are considered live if a non-phi, non-sigma
+ // node uses them. Once we find a node that is live, we mark all
+ // of its operands as used, too.
+ for _, npList := range newPhis {
+ for _, np := range npList {
+ phi := np.phi
+ if !phi.live && hasDirectReferrer(phi) {
+ markLivePhi(phi)
+ }
+ }
+ }
+ for _, npList := range newSigmas {
+ for _, np := range npList {
+ for _, sigma := range np.sigmas {
+ if sigma != nil && !sigma.live && hasDirectReferrer(sigma) {
+ markLiveSigma(sigma)
+ }
+ }
+ }
+ }
+ // Existing φ-nodes due to && and || operators
+ // are all considered live (see Go issue 19622).
+ for _, b := range blocks {
+ for _, phi := range b.phis() {
+ markLivePhi(phi.(*Phi))
+ }
+ }
+}
+
+func markLivePhi(phi *Phi) {
+ phi.live = true
+ for _, rand := range phi.Edges {
+ switch rand := rand.(type) {
+ case *Phi:
+ if !rand.live {
+ markLivePhi(rand)
+ }
+ case *Sigma:
+ if !rand.live {
+ markLiveSigma(rand)
+ }
+ }
+ }
+}
+
+func markLiveSigma(sigma *Sigma) {
+ sigma.live = true
+ switch rand := sigma.X.(type) {
+ case *Phi:
+ if !rand.live {
+ markLivePhi(rand)
+ }
+ case *Sigma:
+ if !rand.live {
+ markLiveSigma(rand)
+ }
+ }
+}
+
+// simplifyPhis replaces trivial phis with non-phi alternatives. Phi
+// nodes where all edges are identical, or consist of only the phi
+// itself and one other value, may be replaced with the value.
+func simplifyPhis(newPhis newPhiMap) {
+ // find all phis that are trivial and can be replaced with a
+ // non-phi value. run until we reach a fixpoint, because replacing
+ // a phi may make other phis trivial.
+ for changed := true; changed; {
+ changed = false
+ for _, npList := range newPhis {
+ for _, np := range npList {
+ if np.phi.live {
+ // we're reusing 'live' to mean 'dead' in the context of simplifyPhis
+ continue
+ }
+ if r, ok := isUselessPhi(np.phi); ok {
+ // useless phi, replace its uses with the
+ // replacement value. the dead phi pass will clean
+ // up the phi afterwards.
+ replaceAll(np.phi, r)
+ np.phi.live = true
+ changed = true
+ }
+ }
+ }
+ }
+
+ for _, npList := range newPhis {
+ for _, np := range npList {
+ np.phi.live = false
+ }
+ }
+}
+
+type BlockSet struct {
+ idx int
+ values []bool
+ count int
+}
+
+func NewBlockSet(size int) *BlockSet {
+ return &BlockSet{values: make([]bool, size)}
+}
+
+func (s *BlockSet) Set(s2 *BlockSet) {
+ copy(s.values, s2.values)
+ s.count = 0
+ for _, v := range s.values {
+ if v {
+ s.count++
+ }
+ }
+}
+
+func (s *BlockSet) Num() int {
+ return s.count
+}
+
+func (s *BlockSet) Has(b *BasicBlock) bool {
+ if b.Index >= len(s.values) {
+ return false
+ }
+ return s.values[b.Index]
+}
+
+// add adds b to the set and returns true if the set changed.
+func (s *BlockSet) Add(b *BasicBlock) bool {
+ if s.values[b.Index] {
+ return false
+ }
+ s.count++
+ s.values[b.Index] = true
+ s.idx = b.Index
+
+ return true
+}
+
+func (s *BlockSet) Clear() {
+ for j := range s.values {
+ s.values[j] = false
+ }
+ s.count = 0
+}
+
+// take removes an arbitrary element from a set s and
+// returns its index, or returns -1 if empty.
+func (s *BlockSet) Take() int {
+ // [i, end]
+ for i := s.idx; i < len(s.values); i++ {
+ if s.values[i] {
+ s.values[i] = false
+ s.idx = i
+ s.count--
+ return i
+ }
+ }
+
+ // [start, i)
+ for i := 0; i < s.idx; i++ {
+ if s.values[i] {
+ s.values[i] = false
+ s.idx = i
+ s.count--
+ return i
+ }
+ }
+
+ return -1
+}
+
+type closure struct {
+ span []uint32
+ reachables []interval
+}
+
+type interval uint32
+
+const (
+ flagMask = 1 << 31
+ numBits = 20
+ lengthBits = 32 - numBits - 1
+ lengthMask = (1<<lengthBits - 1) << numBits
+ numMask = 1<<numBits - 1
+)
+
+func (c closure) has(s, v *BasicBlock) bool {
+ idx := uint32(v.Index)
+ if idx == 1 || s.Dominates(v) {
+ return true
+ }
+ r := c.reachable(s.Index)
+ for i := 0; i < len(r); i++ {
+ inv := r[i]
+ var start, end uint32
+ if inv&flagMask == 0 {
+ // small interval
+ start = uint32(inv & numMask)
+ end = start + uint32(inv&lengthMask)>>numBits
+ } else {
+ // large interval
+ i++
+ start = uint32(inv & numMask)
+ end = uint32(r[i])
+ }
+ if idx >= start && idx <= end {
+ return true
+ }
+ }
+ return false
+}
+
+func (c closure) reachable(id int) []interval {
+ return c.reachables[c.span[id]:c.span[id+1]]
+}
+
+func (c closure) walk(current *BasicBlock, b *BasicBlock, visited []bool) {
+ visited[b.Index] = true
+ for _, succ := range b.Succs {
+ if visited[succ.Index] {
+ continue
+ }
+ visited[succ.Index] = true
+ c.walk(current, succ, visited)
+ }
+}
+
+func transitiveClosure(fn *Function) *closure {
+ reachable := make([]bool, len(fn.Blocks))
+ c := &closure{}
+ c.span = make([]uint32, len(fn.Blocks)+1)
+
+ addInterval := func(start, end uint32) {
+ if l := end - start; l <= 1<<lengthBits-1 {
+ n := interval(l<<numBits | start)
+ c.reachables = append(c.reachables, n)
+ } else {
+ n1 := interval(1<<31 | start)
+ n2 := interval(end)
+ c.reachables = append(c.reachables, n1, n2)
+ }
+ }
+
+ for i, b := range fn.Blocks[1:] {
+ for i := range reachable {
+ reachable[i] = false
+ }
+
+ c.walk(b, b, reachable)
+ start := ^uint32(0)
+ for id, isReachable := range reachable {
+ if !isReachable {
+ if start != ^uint32(0) {
+ end := uint32(id) - 1
+ addInterval(start, end)
+ start = ^uint32(0)
+ }
+ continue
+ } else if start == ^uint32(0) {
+ start = uint32(id)
+ }
+ }
+ if start != ^uint32(0) {
+ addInterval(start, uint32(len(reachable))-1)
+ }
+
+ c.span[i+2] = uint32(len(c.reachables))
+ }
+
+ return c
+}
+
+// newPhi is a pair of a newly introduced φ-node and the lifted Alloc
+// it replaces.
+type newPhi struct {
+ phi *Phi
+ alloc *Alloc
+}
+
+type newSigma struct {
+ alloc *Alloc
+ sigmas []*Sigma
+}
+
+// newPhiMap records for each basic block, the set of newPhis that
+// must be prepended to the block.
+type newPhiMap [][]newPhi
+type newSigmaMap [][]newSigma
+
+func liftable(alloc *Alloc) 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
+ }
+
+ fn := alloc.Parent()
+ // Don't lift named return values in functions that defer
+ // calls that may recover from panic.
+ if fn.hasDefer {
+ for _, nr := range fn.namedResults {
+ if nr == alloc {
+ return false
+ }
+ }
+ }
+
+ for _, instr := range *alloc.Referrers() {
+ 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")
+ }
+ case *Load:
+ if instr.X != alloc {
+ panic("Alloc.Referrers is inconsistent")
+ }
+
+ case *DebugRef:
+ // ok
+ default:
+ return false
+ }
+ }
+
+ return true
+}
+
+// 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.
+func liftAlloc(closure *closure, df domFrontier, rdf postDomFrontier, alloc *Alloc, newPhis newPhiMap, newSigmas newSigmaMap) {
+ fn := alloc.Parent()
+
+ defblocks := fn.blockset(0)
+ useblocks := fn.blockset(1)
+ Aphi := fn.blockset(2)
+ Asigma := fn.blockset(3)
+ W := fn.blockset(4)
+
+ // Compute defblocks, the set of blocks containing a
+ // definition of the alloc cell.
+ 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:
+ defblocks.Add(instr.Block())
+ case *Load:
+ useblocks.Add(instr.Block())
+ for _, ref := range *instr.Referrers() {
+ useblocks.Add(ref.Block())
+ }
+ }
+ }
+ // 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())
+ }
+
+ // Φ-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.
+
+ // Initialize W and work to defblocks.
+
+ for change := true; change; {
+ change = false
+ {
+ // Traverse iterated dominance frontier, inserting φ-nodes.
+ W.Set(defblocks)
+
+ for i := W.Take(); i != -1; i = W.Take() {
+ n := fn.Blocks[i]
+ for _, y := range df[n.Index] {
+ if Aphi.Add(y) {
+ if len(*alloc.Referrers()) == 0 {
+ continue
+ }
+ live := false
+ if closure == nil {
+ live = true
+ } else {
+ for _, ref := range *alloc.Referrers() {
+ if _, ok := ref.(*Load); ok {
+ if closure.has(y, ref.Block()) {
+ live = true
+ break
+ }
+ }
+ }
+ }
+ if !live {
+ continue
+ }
+
+ // Create φ-node.
+ // It will be prepended to v.Instrs later, if needed.
+ phi := &Phi{
+ Edges: make([]Value, len(y.Preds)),
+ }
+
+ phi.source = alloc.source
+ phi.setType(deref(alloc.Type()))
+ phi.block = y
+ if debugLifting {
+ fmt.Fprintf(os.Stderr, "\tplace %s = %s at block %s\n", phi.Name(), phi, y)
+ }
+ newPhis[y.Index] = append(newPhis[y.Index], newPhi{phi, alloc})
+
+ for _, p := range y.Preds {
+ useblocks.Add(p)
+ }
+ change = true
+ if defblocks.Add(y) {
+ W.Add(y)
+ }
+ }
+ }
+ }
+ }
+
+ {
+ W.Set(useblocks)
+ for i := W.Take(); i != -1; i = W.Take() {
+ n := fn.Blocks[i]
+ for _, y := range rdf[n.Index] {
+ if Asigma.Add(y) {
+ sigmas := make([]*Sigma, 0, len(y.Succs))
+ anyLive := false
+ for _, succ := range y.Succs {
+ live := false
+ for _, ref := range *alloc.Referrers() {
+ if closure == nil || closure.has(succ, ref.Block()) {
+ live = true
+ anyLive = true
+ break
+ }
+ }
+ if live {
+ sigma := &Sigma{
+ From: y,
+ X: alloc,
+ }
+ sigma.source = alloc.source
+ sigma.setType(deref(alloc.Type()))
+ sigma.block = succ
+ sigmas = append(sigmas, sigma)
+ } else {
+ sigmas = append(sigmas, nil)
+ }
+ }
+
+ if anyLive {
+ newSigmas[y.Index] = append(newSigmas[y.Index], newSigma{alloc, sigmas})
+ for _, s := range y.Succs {
+ defblocks.Add(s)
+ }
+ change = true
+ if useblocks.Add(y) {
+ W.Add(y)
+ }
+ }
+ }
+ }
+ }
+ }
+ }
+}
+
+// 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(fn *Function, renaming []Value, alloc *Alloc) Value {
+ v := renaming[alloc.index]
+ if v == nil {
+ v = emitConst(fn, zeroConst(deref(alloc.Type())))
+ renaming[alloc.index] = v
+ }
+ return v
+}
+
+// rename implements the Cytron et al-based SSI 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.
+//
+// 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, newSigmas newSigmaMap) {
+ // Each φ-node becomes the new name for its associated Alloc.
+ for _, np := range newPhis[u.Index] {
+ 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())
+ }
+ if refs := instr.Addr.Referrers(); refs != nil {
+ *refs = removeInstr(*refs, instr)
+ }
+ if refs := instr.Val.Referrers(); refs != nil {
+ *refs = removeInstr(*refs, instr)
+ }
+ // Delete the Store.
+ u.Instrs[i] = nil
+ u.gaps++
+ }
+
+ case *Load:
+ if alloc, ok := instr.X.(*Alloc); ok && alloc.index >= 0 { // load of Alloc cell
+ // In theory, we wouldn't be able to replace loads
+ // directly, because a loaded value could be used in
+ // different branches, in which case it should be
+ // replaced with different sigma nodes. But we can't
+ // simply defer replacement, either, because then
+ // later stores might incorrectly affect this load.
+ //
+ // To avoid doing renaming on _all_ values (instead of
+ // just loads and stores like we're doing), we make
+ // sure during code generation that each load is only
+ // used in one block. For example, in constant switch
+ // statements, where the tag is only evaluated once,
+ // we store it in a temporary and load it for each
+ // comparison, so that we have individual loads to
+ // replace.
+ newval := renamed(u.Parent(), renaming, alloc)
+ if debugLifting {
+ fmt.Fprintf(os.Stderr, "\tupdate load %s = %s with %s\n",
+ instr.Name(), instr, newval)
+ }
+ replaceAll(instr, newval)
+ u.Instrs[i] = nil
+ u.gaps++
+ }
+
+ case *DebugRef:
+ if x, ok := instr.X.(*Alloc); ok && x.index >= 0 {
+ if instr.IsAddr {
+ instr.X = renamed(u.Parent(), renaming, x)
+ 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++
+ }
+ }
+ }
+ }
+
+ // update all outgoing sigma nodes with the dominating store
+ for _, sigmas := range newSigmas[u.Index] {
+ for _, sigma := range sigmas.sigmas {
+ if sigma == nil {
+ continue
+ }
+ sigma.X = renamed(u.Parent(), renaming, sigmas.alloc)
+ }
+ }
+
+ // For each φ-node in a CFG successor, rename the edge.
+ for succi, v := range u.Succs {
+ phis := newPhis[v.Index]
+ if len(phis) == 0 {
+ continue
+ }
+ i := v.predIndex(u)
+ for _, np := range phis {
+ phi := np.phi
+ alloc := np.alloc
+ // if there's a sigma node, use it, else use the dominating value
+ var newval Value
+ for _, sigmas := range newSigmas[u.Index] {
+ if sigmas.alloc == alloc && sigmas.sigmas[succi] != nil {
+ newval = sigmas.sigmas[succi]
+ break
+ }
+ }
+ if newval == nil {
+ newval = renamed(u.Parent(), 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.
+ r := make([]Value, len(renaming))
+ for _, v := range u.dom.children {
+ // XXX add debugging
+ copy(r, renaming)
+
+ // on entry to a block, the incoming sigma nodes become the new values for their alloc
+ if idx := u.succIndex(v); idx != -1 {
+ for _, sigma := range newSigmas[u.Index] {
+ if sigma.sigmas[idx] != nil {
+ r[sigma.alloc.index] = sigma.sigmas[idx]
+ }
+ }
+ }
+ rename(v, r, newPhis, newSigmas)
+ }
+
+}
projects / dotfiles / .git / blobdiff