// 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...

// https://doi.acm.org/10.1145/115372.115320

//

// Cooper, Harvey, Kennedy. 2001. A Simple, Fast Dominance Algorithm.

// Software Practice and Experience 2001, 4:1-10.

// https://www.hipersoft.rice.edu/grads/publications/dom14.pdf

//

// Daniel Berlin, llvmdev mailing list, 2012.

// https://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 (

"encoding/binary"

"fmt"

"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 BlockMap[[]*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 {

preds := b.Preds[0:len(b.Preds):len(b.Preds)]

if b == fn.Exit {

for i, v := range fn.fakeExits.values {

if v {

preds = append(preds, fn.Blocks[i])

}

}

}

if len(preds) >= 2 {

for _, p := range 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 BlockMap[[]*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 {

succs := b.Succs[0:len(b.Succs):len(b.Succs)]

if fn.fakeExits.Has(b) {

succs = append(succs, fn.Exit)

}

if len(succs) >= 2 {

for _, s := range 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

}

}

func numberNodesPerBlock(f *Function) {

for _, b := range f.Blocks {

var base ID

for _, instr := range b.Instrs {

if instr == nil {

continue

}

instr.setID(base)

base++

}

}

}

// 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) bool {

// 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 BlockMap[[]newPhi]

var newSigmas BlockMap[[]newSigma]

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

instructions := make(BlockMap[liftInstructions], len(fn.Blocks))

for i := range instructions {

instructions[i].insertInstructions = map[Instruction][]Instruction{}

}

// Number nodes, for liftable

numberNodesPerBlock(fn)

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, instructions) {

instr.index = -1

continue

}

if numAllocs == 0 {

df = buildDomFrontier(fn)

rdf = buildPostDomFrontier(fn)

if len(fn.Blocks) > 2 {

closure = transitiveClosure(fn)

}

newPhis = make(BlockMap[[]newPhi], len(fn.Blocks))

newSigmas = make(BlockMap[[]newSigma], 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)

}

}

}

}

instr.index = numAllocs

numAllocs++

case *Defer:

usesDefer = true

case *RunDefers:

b.rundefers++

}

}

}

if numAllocs > 0 {

for _, b := range fn.Blocks {

work := instructions[b.Index]

for _, rename := range work.renameAllocs {

for _, instr_ := range b.Instrs[rename.startingAt:] {

replace(instr_, rename.from, rename.to)

}

}

}

for _, b := range fn.Blocks {

work := instructions[b.Index]

if len(work.insertInstructions) != 0 {

newInstrs := make([]Instruction, 0, len(fn.Blocks)+len(work.insertInstructions)*3)

for _, instr := range b.Instrs {

if add, ok := work.insertInstructions[instr]; ok {

newInstrs = append(newInstrs, add...)

}

newInstrs = append(newInstrs, instr)

}

b.Instrs = newInstrs

}

}

// TODO(dh): remove inserted allocs that end up unused after lifting.

for _, b := range fn.Blocks {

for _, instr := range b.Instrs {

if instr, ok := instr.(*Alloc); ok && instr.index >= 0 {

liftAlloc(closure, df, rdf, instr, newPhis, newSigmas)

}

}

}

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

simplifyPhisAndSigmas(newPhis, newSigmas)

// 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]

return numAllocs > 0

}

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 BlockMap[[]newPhi], newSigmas BlockMap[[]newSigma]) {

// Phis and sigmas may become dead due to optimization passes. We may also insert more nodes than strictly

// necessary, e.g. sigma nodes for constants, which will never be used.

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

}

}

}

// simplifyPhisAndSigmas removes duplicate phi and sigma nodes,

// and 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 simplifyPhisAndSigmas(newPhis BlockMap[[]newPhi], newSigmas BlockMap[[]newSigma]) {

// temporary numbering of values used in phis so that we can build map keys

var id ID

for _, npList := range newPhis {

for _, np := range npList {

for _, edge := range np.phi.Edges {

edge.setID(id)

id++

}

}

}

// 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 simplifyPhisAndSigmas

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

}

}

}

// Replace duplicate sigma nodes with a single node. These nodes exist when multiple allocs get replaced with the

// same dominating store.

for _, sigmaList := range newSigmas {

primarySigmas := map[struct {

succ int

v Value

}]*Sigma{}

for _, sigmas := range sigmaList {

for succ, sigma := range sigmas.sigmas {

if sigma == nil {

continue

}

if sigma.live {

// we're reusing 'live' to mean 'dead' in the context of simplifyPhisAndSigmas

continue

}

key := struct {

succ int

v Value

}{succ, sigma.X}

if alt, ok := primarySigmas[key]; ok {

replaceAll(sigma, alt)

sigma.live = true

changed = true

} else {

primarySigmas[key] = sigma

}

}

}

}

// Replace duplicate phi nodes with a single node. As far as we know, these duplicate nodes only ever exist

// because of the previous sigma deduplication.

keyb := make([]byte, 0, 4*8)

for _, npList := range newPhis {

primaryPhis := map[string]*Phi{}

for _, np := range npList {

if np.phi.live {

continue

}

if n := len(np.phi.Edges) * 8; cap(keyb) >= n {

keyb = keyb[:n]

} else {

keyb = make([]byte, n, n*2)

}

for i, e := range np.phi.Edges {

binary.LittleEndian.PutUint64(keyb[i*8:i*8+8], uint64(e.ID()))

}

if alt, ok := primaryPhis[string(keyb)]; ok {

replaceAll(np.phi, alt)

np.phi.live = true

changed = true

} else {

primaryPhis[string(keyb)] = np.phi

}

}

}

}

for _, npList := range newPhis {

for _, np := range npList {

np.phi.live = false

for _, edge := range np.phi.Edges {

edge.setID(0)

}

}

}

for _, sigmaList := range newSigmas {

for _, sigmas := range sigmaList {

for _, sigma := range sigmas.sigmas {

if sigma != nil {

sigma.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 BlockMap[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) {

// TODO(dh): the 'current' argument seems to be unused

// TODO(dh): there's no reason for this to be a method

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(BlockMap[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

}

type liftInstructions struct {

insertInstructions map[Instruction][]Instruction

renameAllocs []struct {

from *Alloc

to *Alloc

startingAt int

}

}

// liftable determines if alloc can be lifted, and records instructions to split partially liftable allocs.

//

// In the trivial case, all uses of the alloc can be lifted. This is the case when it is only used for storing into and

// loading from. In that case, no instructions are recorded.

//

// In the more complex case, the alloc is used for storing into and loading from, but it is also used as a value, for

// example because it gets passed to a function, e.g. fn(&x). In this case, uses of the alloc fall into one of two

// categories: those that can be lifted and those that can't. A boundary forms between these two categories in the

// function's control flow: Once an unliftable use is encountered, the alloc is no longer liftable for the remainder of

// the basic block the use is in, nor in any blocks reachable from it.

//

// We record instructions that split the alloc into two allocs: one that is used in liftable uses, and one that is used

// in unliftable uses. Whenever we encounter a boundary between liftable and unliftable uses or blocks, we emit a pair

// of Load and Store that copy the value from the liftable alloc into the unliftable alloc. Taking these instructions

// into account, the normal lifting machinery will completely lift the liftable alloc, store the correct lifted values

// into the unliftable alloc, and will not at all lift the unliftable alloc.

//

// In Go syntax, the transformation looks somewhat like this:

//

// func foo() {

// x := 32

// if cond {

// println(x)

// escape(&x)

// println(x)

// } else {

// println(x)

// }

// println(x)

// }

//

// transforms into

//

// func fooSplitAlloc() {

// x := 32

// var x_ int

// if cond {

// println(x)

// x_ = x

// escape(&x_)

// println(x_)

// } else {

// println(x)

// x_ = x

// }

// println(x_)

// }

func liftable(alloc *Alloc, instructions BlockMap[liftInstructions]) bool {

fn := alloc.block.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

}

}

}

type blockDesc struct {

// is the block (partially) unliftable, because it contains unliftable instructions or is reachable by an unliftable block

isUnliftable bool

hasLiftableLoad bool

hasLiftableOther bool

// we need to emit stores in predecessors because the unliftable use is in a phi

storeInPreds bool

lastLiftable int

firstUnliftable int

}

blocks := make(BlockMap[blockDesc], len(fn.Blocks))

for _, b := range fn.Blocks {

blocks[b.Index].lastLiftable = -1

blocks[b.Index].firstUnliftable = len(b.Instrs) + 1

}

// Look at all uses of the alloc and deduce which blocks have liftable or unliftable instructions.

for _, instr := range alloc.referrers {

// Find the first unliftable use

desc := &blocks[instr.Block().Index]

hasUnliftable := false

inHead := false

switch instr := instr.(type) {

case *Store:

if instr.Val == alloc {

hasUnliftable = true

}

case *Load:

case *DebugRef:

case *Phi, *Sigma:

inHead = true

hasUnliftable = true

default:

hasUnliftable = true

}

if hasUnliftable {

desc.isUnliftable = true

if int(instr.ID()) < desc.firstUnliftable {

desc.firstUnliftable = int(instr.ID())

}

if inHead {

desc.storeInPreds = true

desc.firstUnliftable = 0

}

}

}

for _, instr := range alloc.referrers {

// Find the last liftable use, taking the previously calculated firstUnliftable into consideration

desc := &blocks[instr.Block().Index]

if int(instr.ID()) >= desc.firstUnliftable {

continue

}

hasLiftable := false

switch instr := instr.(type) {

case *Store:

if instr.Val != alloc {

desc.hasLiftableOther = true

hasLiftable = true

}

case *Load:

desc.hasLiftableLoad = true

hasLiftable = true

case *DebugRef:

desc.hasLiftableOther = true

}

if hasLiftable {

if int(instr.ID()) > desc.lastLiftable {

desc.lastLiftable = int(instr.ID())

}

}

}

for i := range blocks {

// Update firstUnliftable to be one after lastLiftable. We do this to include the unliftable's preceding

// DebugRefs in the renaming.

if blocks[i].lastLiftable == -1 && !blocks[i].storeInPreds {

// There are no liftable instructions (for this alloc) in this block. Set firstUnliftable to the

// first non-head instruction to avoid inserting the store before phi instructions, which would

// fail validation.

first := -1

instrLoop:

for i, instr := range fn.Blocks[i].Instrs {

switch instr.(type) {

case *Phi, *Sigma:

default:

first = i

break instrLoop

}

}

blocks[i].firstUnliftable = first

} else {

blocks[i].firstUnliftable = blocks[i].lastLiftable + 1

}

}

// If a block is reachable by a (partially) unliftable block, then the entirety of the block is unliftable. In that

// case, stores have to be inserted in the predecessors.

//

// TODO(dh): this isn't always necessary. If the block is reachable by itself, i.e. part of a loop, then if the

// Alloc instruction is itself part of that loop, then there is a subset of instructions in the loop that can be

// lifted. For example:

//

// for {