golang stackalloc 代码
文件路径：/src/cmd/compile/internal/ssa/stackalloc.go
/ Copyright 2015 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.
/ TODO: live at start of block instead?
package ssa
import (
"cmd/compile/internal/ir"
"cmd/compile/internal/types"
"cmd/internal/src"
"fmt"
)
type stackAllocState struct {
f *Func
/ live is the output of stackalloc.
/ live[b.id] = live values at the end of block b.
live [][]ID
/ The following slices are reused across multiple users
/ of stackAllocState.
values []stackValState
interfere [][]ID / interfere[v.id] = values that interfere with v.
names []LocalSlot
slots []int
used []bool
nArgSlot, / Number of Values sourced to arg slot
nNotNeed, / Number of Values not needing a stack slot
nNamedSlot, / Number of Values using a named stack slot
nReuse, / Number of values reusing a stack slot
nAuto, / Number of autos allocated for stack slots.
nSelfInterfere int32 / Number of self-interferences
}
func newStackAllocState(f *Func) *stackAllocState {
s := f.Cache.stackAllocState
if s == nil {
return new(stackAllocState)
}
if s.f != nil {
f.fe.Fatalf(src.NoXPos, "newStackAllocState called without previous free")
}
return s
}
func putStackAllocState(s *stackAllocState) {
for i := range s.values {
s.values[i] = stackValState{}
}
for i := range s.interfere {
s.interfere[i] = nil
}
for i := range s.names {
s.names[i] = LocalSlot{}
}
for i := range s.slots {
s.slots[i] = 0
}
for i := range s.used {
s.used[i] = false
}
s.f.Cache.stackAllocState = s
s.f = nil
s.live = nil
s.nArgSlot, s.nNotNeed, s.nNamedSlot, s.nReuse, s.nAuto, s.nSelfInterfere = 0, 0, 0, 0, 0, 0
}
type stackValState struct {
typ *types.Type
spill *Value
needSlot bool
isArg bool
}
/ stackalloc allocates storage in the stack frame for
/ all Values that did not get a register.
/ Returns a map from block ID to the stack values live at the end of that block.
func stackalloc(f *Func, spillLive [][]ID) [][]ID {
if f.pass.debug > stackDebug {
fmt.Println("before stackalloc")
fmt.Println(f.String())
}
s := newStackAllocState(f)
s.init(f, spillLive)
defer putStackAllocState(s)
s.stackalloc()
if f.pass.stats > 0 {
f.LogStat("stack_alloc_stats",
s.nArgSlot, "arg_slots", s.nNotNeed, "slot_not_needed",
s.nNamedSlot, "named_slots", s.nAuto, "auto_slots",
s.nReuse, "reused_slots", s.nSelfInterfere, "self_interfering")
}
return s.live
}
func (s *stackAllocState) init(f *Func, spillLive [][]ID) {
s.f = f
/ Initialize value information.
if n := f.NumValues(); cap(s.values) >= n {
s.values = s.values[:n]
} else {
s.values = make([]stackValState, n)
}
for _, b := range f.Blocks {
for _, v := range b.Values {
s.values[v.ID].typ = v.Type
s.values[v.ID].needSlot = !v.Type.IsMemory() && !v.Type.IsVoid() && !v.Type.IsFlags() && f.getHome(v.ID) == nil && !v.rematerializeable() && !v.OnWasmStack
s.values[v.ID].isArg = hasAnyArgOp(v)
if f.pass.debug > stackDebug && s.values[v.ID].needSlot {
fmt.Printf("%s needs a stack slot\n", v)
}
if v.Op == OpStoreReg {
s.values[v.Args[0].ID].spill = v
}
}
}
/ Compute liveness info for values needing a slot.
s.computeLive(spillLive)
/ Build interference graph among values needing a slot.
s.buildInterferenceGraph()
}
func (s *stackAllocState) stackalloc() {
f := s.f
/ Build map from values to their names, if any.
/ A value may be associated with more than one name (e.g. after
/ the assignment i=j). This step picks one name per value arbitrarily.
if n := f.NumValues(); cap(s.names) >= n {
s.names = s.names[:n]
} else {
s.names = make([]LocalSlot, n)
}
names := s.names
empty := LocalSlot{}
for _, name := range f.Names {
/ Note: not "range f.NamedValues" above, because
/ that would be nondeterministic.
for _, v := range f.NamedValues[*name] {
if v.Op == OpArgIntReg || v.Op == OpArgFloatReg {
aux := v.Aux.(*AuxNameOffset)
/ Never let an arg be bound to a differently named thing.
if name.N != aux.Name || name.Off != aux.Offset {
if f.pass.debug > stackDebug {
fmt.Printf("stackalloc register arg %s skipping name %s\n", v, name)
}
continue
}
} else if name.N.Class == ir.PPARAM && v.Op != OpArg {
/ PPARAM's only bind to OpArg
if f.pass.debug > stackDebug {
fmt.Printf("stackalloc PPARAM name %s skipping non-Arg %s\n", name, v)
}
continue
}
if names[v.ID] == empty {
if f.pass.debug > stackDebug {
fmt.Printf("stackalloc value %s to name %s\n", v, *name)
}
names[v.ID] = *name
}
}
}
/ Allocate args to their assigned locations.
for _, v := range f.Entry.Values {
if !hasAnyArgOp(v) {
continue
}
if v.Aux == nil {
f.Fatalf("%s has nil Aux\n", v.LongString())
}
if v.Op == OpArg {
loc := LocalSlot{N: v.Aux.(*ir.Name), Type: v.Type, Off: v.AuxInt}
if f.pass.debug > stackDebug {
fmt.Printf("stackalloc OpArg %s to %s\n", v, loc)
}
f.setHome(v, loc)
continue
}
/ You might think this below would be the right idea, but you would be wrong.
/ It almost works; as of 105a6e9518 - 2021-04-23,
/ GOSSAHASH=11011011001011111 == cmd/compile/internal/noder.(*noder).embedded
/ is compiled incorrectly. I believe the cause is one of those SSA-to-registers
/ puzzles that the register allocator untangles; in the event that a register
/ parameter does not end up bound to a name, "fixing" it is a bad idea.
/
/if f.DebugTest {
/ if v.Op == OpArgIntReg || v.Op == OpArgFloatReg {
/ aux := v.Aux.(*AuxNameOffset)
/ loc := LocalSlot{N: aux.Name, Type: v.Type, Off: aux.Offset}
/ if f.pass.debug > stackDebug {
/ fmt.Printf("stackalloc Op%s %s to %s\n", v.Op, v, loc)
/ }
/ names[v.ID] = loc
/ continue
/ }
/}
}
/ For each type, we keep track of all the stack slots we
/ have allocated for that type.
/ TODO: share slots among equivalent types. We would need to
/ only share among types with the same GC signature. See the
/ type.Equal calls below for where this matters.
locations := map[*types.Type][]LocalSlot{}
/ Each time we assign a stack slot to a value v, we remember
/ the slot we used via an index into locations[v.Type].
slots := s.slots
if n := f.NumValues(); cap(slots) >= n {
slots = slots[:n]
} else {
slots = make([]int, n)
s.slots = slots
}
for i := range slots {
slots[i] = -1
}
/ Pick a stack slot for each value needing one.
var used []bool
if n := f.NumValues(); cap(s.used) >= n {
used = s.used[:n]
} else {
used = make([]bool, n)
s.used = used
}
for _, b := range f.Blocks {
for _, v := range b.Values {
if !s.values[v.ID].needSlot {
s.nNotNeed++
continue
}
if hasAnyArgOp(v) {
s.nArgSlot++
continue / already picked
}
/ If this is a named value, try to use the name as
/ the spill location.
var name LocalSlot
if v.Op == OpStoreReg {
name = names[v.Args[0].ID]
} else {
name = names[v.ID]
}
if name.N != nil && v.Type.Compare(name.Type) == types.CMPeq {
for _, id := range s.interfere[v.ID] {
h := f.getHome(id)
if h != nil && h.(LocalSlot).N == name.N && h.(LocalSlot).Off == name.Off {
/ A variable can interfere with itself.
/ It is rare, but it can happen.
s.nSelfInterfere++
goto noname
}
}
if f.pass.debug > stackDebug {
fmt.Printf("stackalloc %s to %s\n", v, name)
}
s.nNamedSlot++
f.setHome(v, name)
continue
}
noname:
/ Set of stack slots we could reuse.
locs := locations[v.Type]
/ Mark all positions in locs used by interfering values.
for i := 0; i < len(locs); i++ {
used[i] = false
}
for _, xid := range s.interfere[v.ID] {
slot := slots[xid]
if slot >= 0 {
used[slot] = true
}
}
/ Find an unused stack slot.
var i int
for i = 0; i < len(locs); i++ {
if !used[i] {
s.nReuse++
break
}
}
/ If there is no unused stack slot, allocate a new one.
if i == len(locs) {
s.nAuto++
locs = append(locs, LocalSlot{N: f.fe.Auto(v.Pos, v.Type), Type: v.Type, Off: 0})
locations[v.Type] = locs
}
/ Use the stack variable at that index for v.
loc := locs[i]
if f.pass.debug > stackDebug {
fmt.Printf("stackalloc %s to %s\n", v, loc)
}
f.setHome(v, loc)
slots[v.ID] = i
}
}
}
/ computeLive computes a map from block ID to a list of
/ stack-slot-needing value IDs live at the end of that block.
/ TODO: this could be quadratic if lots of variables are live across lots of
/ basic blocks. Figure out a way to make this function (or, more precisely, the user
/ of this function) require only linear size & time.
func (s *stackAllocState) computeLive(spillLive [][]ID) {
s.live = make([][]ID, s.f.NumBlocks())
var phis []*Value
live := s.f.newSparseSet(s.f.NumValues())
defer s.f.retSparseSet(live)
t := s.f.newSparseSet(s.f.NumValues())
defer s.f.retSparseSet(t)
/ Instead of iterating over f.Blocks, iterate over their postordering.
/ Liveness information flows backward, so starting at the end
/ increases the probability that we will stabilize quickly.
po := s.f.postorder()
for {
changed := false
for _, b := range po {
/ Start with known live values at the end of the block
live.clear()
live.addAll(s.live[b.ID])
/ Propagate backwards to the start of the block
phis = phis[:0]
for i := len(b.Values) - 1; i >= 0; i-- {
v := b.Values[i]
live.remove(v.ID)
if v.Op == OpPhi {
/ Save phi for later.
/ Note: its args might need a stack slot even though
/ the phi itself doesn't. So don't use needSlot.
if !v.Type.IsMemory() && !v.Type.IsVoid() {
phis = append(phis, v)
}
continue
}
for _, a := range v.Args {
if s.values[a.ID].needSlot {
live.add(a.ID)
}
}
}
/ for each predecessor of b, expand its list of live-at-end values
/ invariant: s contains the values live at the start of b (excluding phi inputs)
for i, e := range b.Preds {
p := e.b
t.clear()
t.addAll(s.live[p.ID])
t.addAll(live.contents())
t.addAll(spillLive[p.ID])
for _, v := range phis {
a := v.Args[i]
if s.values[a.ID].needSlot {
t.add(a.ID)
}
if spill := s.values[a.ID].spill; spill != nil {
/TODO: remove? Subsumed by SpillUse?
t.add(spill.ID)
}
}
if t.size() == len(s.live[p.ID]) {
continue
}
/ grow p's live set
s.live[p.ID] = append(s.live[p.ID][:0], t.contents()...)
changed = true
}
}
if !changed {
break
}
}
if s.f.pass.debug > stackDebug {
for _, b := range s.f.Blocks {
fmt.Printf("stacklive %s %v\n", b, s.live[b.ID])
}
}
}
func (f *Func) getHome(vid ID) Location {
if int(vid) >= len(f.RegAlloc) {
return nil
}
return f.RegAlloc[vid]
}
func (f *Func) setHome(v *Value, loc Location) {
for v.ID >= ID(len(f.RegAlloc)) {
f.RegAlloc = append(f.RegAlloc, nil)
}
f.RegAlloc[v.ID] = loc
}
func (s *stackAllocState) buildInterferenceGraph() {
f := s.f
if n := f.NumValues(); cap(s.interfere) >= n {
s.interfere = s.interfere[:n]
} else {
s.interfere = make([][]ID, n)
}
live := f.newSparseSet(f.NumValues())
defer f.retSparseSet(live)
for _, b := range f.Blocks {
/ Propagate liveness backwards to the start of the block.
/ Two values interfere if one is defined while the other is live.
live.clear()
live.addAll(s.live[b.ID])
for i := len(b.Values) - 1; i >= 0; i-- {
v := b.Values[i]
if s.values[v.ID].needSlot {
live.remove(v.ID)
for _, id := range live.contents() {
/ Note: args can have different types and still interfere
/ (with each other or with other values). See issue 23522.
if s.values[v.ID].typ.Compare(s.values[id].typ) == types.CMPeq || hasAnyArgOp(v) || s.values[id].isArg {
s.interfere[v.ID] = append(s.interfere[v.ID], id)
s.interfere[id] = append(s.interfere[id], v.ID)
}
}
}
for _, a := range v.Args {
if s.values[a.ID].needSlot {
live.add(a.ID)
}
}
if hasAnyArgOp(v) && s.values[v.ID].needSlot {
/ OpArg is an input argument which is pre-spilled.
/ We add back v.ID here because we want this value
/ to appear live even before this point. Being live
/ all the way to the start of the entry block prevents other
/ values from being allocated to the same slot and clobbering
/ the input value before we have a chance to load it.
/ TODO(register args) this is apparently not wrong for register args -- is it necessary?
live.add(v.ID)
}
}
}
if f.pass.debug > stackDebug {
for vid, i := range s.interfere {
if len(i) > 0 {
fmt.Printf("v%d interferes with", vid)
for _, x := range i {
fmt.Printf(" v%d", x)
}
fmt.Println()
}
}
}
}
func hasAnyArgOp(v *Value) bool {
return v.Op == OpArg || v.Op == OpArgIntReg || v.Op == OpArgFloatReg
}