Giant blob of minor changes

[dotfiles/.git] / .config / coc / extensions / coc-go-data / tools / pkg / mod / honnef.co / go / tools@v0.0.1-2020.1.5 / ir / lift.go

// 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)
        }

}