Structs
Interval
struct
#
Interval hols the range [st,en).
type Interval struct {
st int
en int
}
IntervalsBuilder
struct
#
IntervalsBuilder is a helper for constructing intervals based on
live dataflow sets for a series of BBs where we're making a
backwards pass over each BB looking for uses and kills. The
expected use case is:
- invoke MakeIntervalsBuilder to create a new object "b"
- series of calls to b.Live/b.Kill based on a backwards reverse layout
order scan over instructions
- invoke b.Finish() to produce final set
See the Live method comment for an IR example.
type IntervalsBuilder struct {
s Intervals
lidx int
}
Map
struct
#
Map maps from *ssa.Value to StackMapIndex.
Also keeps track of unsafe ssa.Values and ssa.Blocks.
(unsafe = can't be interrupted during GC.)
type Map struct {
Vals map[ssa.ID]objw.StackMapIndex
UnsafeVals map[ssa.ID]bool
UnsafeBlocks map[ssa.ID]bool
DeferReturn objw.StackMapIndex
}
MergeLocalsState
struct
#
MergeLocalsState encapsulates information about which AUTO
(stack-allocated) variables within a function can be safely
merged/overlapped, e.g. share a stack slot with some other auto).
An instance of MergeLocalsState is produced by MergeLocals() below
and then consumed in ssagen.AllocFrame. The map 'partition'
contains entries of the form where N is an *ir.Name and SL
is a slice holding the indices (within 'vars') of other variables
that share the same slot, specifically the slot of the first
element in the partition, which we'll call the "leader". For
example, if a function contains five variables where v1/v2/v3 are
safe to overlap and v4/v5 are safe to overlap, the MergeLocalsState
content might look like
vars: [v1, v2, v3, v4, v5]
partition: v1 -> [1, 0, 2], v2 -> [1, 0, 2], v3 -> [1, 0, 2]
v4 -> [3, 4], v5 -> [3, 4]
A nil MergeLocalsState indicates that no local variables meet the
necessary criteria for overlap.
type MergeLocalsState struct {
vars []*ir.Name
partition map[*ir.Name][]int
}
argLiveness
struct
#
type argLiveness struct {
fn *ir.Func
f *ssa.Func
args []nameOff
idx map[nameOff]int32
be []blockArgEffects
bvset bvecSet
blockIdx map[ssa.ID]int
valueIdx map[ssa.ID]int
}
blockArgEffects
struct
#
type blockArgEffects struct {
livein bitvec.BitVec
liveout bitvec.BitVec
}
blockEffects
struct
#
blockEffects summarizes the liveness effects on an SSA block.
type blockEffects struct {
uevar bitvec.BitVec
varkill bitvec.BitVec
livein bitvec.BitVec
liveout bitvec.BitVec
}
bvecSet
struct
#
bvecSet is a set of bvecs, in initial insertion order.
type bvecSet struct {
index []int
uniq []bitvec.BitVec
}
candRegion
struct
#
candRegion is a sub-range (start, end) corresponding to an interval
[st,en] within the list of candidate variables.
type candRegion struct {
st int
en int
}
cstate
struct
#
cstate holds state information we'll need during the analysis
phase of stack slot merging but can be discarded when the analysis
is done.
type cstate struct {
fn *ir.Func
f *ssa.Func
lv *liveness
cands []*ir.Name
nameToSlot map[*ir.Name]int32
regions []candRegion
indirectUE map[ssa.ID][]*ir.Name
ivs []Intervals
hashDeselected map[*ir.Name]bool
trace int
}
intWithIdx
struct
#
intWithIdx holds an interval i and an index pairIndex storing i's
position (either 0 or 1) within some previously specified interval
pair ; a pairIndex of -1 is used to signal "end of
iteration". Used for Intervals operations, not expected to be
exported.
type intWithIdx struct {
i Interval
pairIndex int
}
liveness
struct
#
A collection of global state used by liveness analysis.
type liveness struct {
fn *ir.Func
f *ssa.Func
vars []*ir.Name
idx map[*ir.Name]int32
stkptrsize int64
be []blockEffects
allUnsafe bool
unsafePoints bitvec.BitVec
unsafeBlocks bitvec.BitVec
livevars []bitvec.BitVec
livenessMap Map
stackMapSet bvecSet
stackMaps []bitvec.BitVec
cache progeffectscache
partLiveArgs map[*ir.Name]bool
doClobber bool
noClobberArgs bool
conservativeWrites bool
}
livenessFuncCache
struct
#
type livenessFuncCache struct {
be []blockEffects
livenessMap Map
}
nameCount
struct
#
type nameCount struct {
n *ir.Name
count int32
}
nameOff
struct
#
name and offset
type nameOff struct {
n *ir.Name
off int64
}
pairVisitor
struct
#
pairVisitor provides a way to visit (iterate through) each interval
within a pair of Intervals in order of increasing start time. Expected
usage model:
func example(i1, i2 Intervals) {
var pairVisitor pv
cur := pv.init(i1, i2);
for !cur.done() {
fmt.Printf("interval %s from i%d", cur.i.String(), cur.pairIndex+1)
cur = pv.nxt()
}
}
Used internally for Intervals operations, not expected to be exported.
type pairVisitor struct {
cur intWithIdx
i1pos int
i2pos int
i1 Intervals
i2 Intervals
}
progeffectscache
struct
#
type progeffectscache struct {
retuevar []int32
tailuevar []int32
initialized bool
}
Functions
ArgLiveness
function
#
ArgLiveness computes the liveness information of register argument spill slots.
An argument's spill slot is "live" if we know it contains a meaningful value,
that is, we have stored the register value to it.
Returns the liveness map indices at each Block entry and at each Value (where
it changes).
func ArgLiveness(fn *ir.Func, f *ssa.Func, pp *objw.Progs) (blockIdx map[ssa.ID]int, valueIdx map[ssa.ID]int)
Compute
function
#
Entry pointer for Compute analysis. Solves for the Compute of
pointer variables in the function and emits a runtime data
structure read by the garbage collector.
Returns a map from GC safe points to their corresponding stack map index,
and a map that contains all input parameters that may be partially live.
func Compute(curfn *ir.Func, f *ssa.Func, stkptrsize int64, pp *objw.Progs) (Map, map[*ir.Name]bool)
EstSavings
method
#
EstSavings returns the estimated reduction in stack size (number of bytes) for
the given merge locals state via a pair of ints, the first for non-pointer types and the second for pointer types.
func (mls *MergeLocalsState) EstSavings() (int, int)
Finish
method
#
func (c *IntervalsBuilder) Finish() (Intervals, error)
Followers
method
#
Followers writes a list of the followers for leader n into the slice tmp.
func (mls *MergeLocalsState) Followers(n *ir.Name, tmp []*ir.Name) []*ir.Name
FrameOffset
method
#
func (a nameOff) FrameOffset() int64
Get
method
#
func (m Map) Get(v *ssa.Value) objw.StackMapIndex
GetUnsafe
method
#
func (m Map) GetUnsafe(v *ssa.Value) bool
GetUnsafeBlock
method
#
func (m Map) GetUnsafeBlock(b *ssa.Block) bool
IsLeader
method
#
IsLeader returns whether a variable n is the leader (first element)
in a sharing partition.
func (mls *MergeLocalsState) IsLeader(n *ir.Name) bool
IsUnsafe
function
#
IsUnsafe indicates that all points in this function are
unsafe-points.
func IsUnsafe(f *ssa.Func) bool
Kill
method
#
Kill method should be invoked on instruction at position p if instr
should be treated as having a kill (lifetime end) for the
resource. See the example in the comment at the beginning of this
file for an example. Note that if we see a kill at position K for a
resource currently live since J, this will result in a lifetime
segment of [K+1,J+1), the assumption being that the first live
instruction will be the one after the kill position, not the kill
position itself.
func (c *IntervalsBuilder) Kill(pos int) error
Leader
method
#
Leader returns the leader variable for subsumed var n.
func (mls *MergeLocalsState) Leader(n *ir.Name) *ir.Name
Live
method
#
Live method should be invoked on instruction at position p if instr
contains an upwards-exposed use of a resource. See the example in
the comment at the beginning of this file for an example.
func (c *IntervalsBuilder) Live(pos int) error
MakeMergeLocalsState
function
#
for unit testing only.
func MakeMergeLocalsState(partition map[*ir.Name][]int, vars []*ir.Name) (*MergeLocalsState, error)
Merge
method
#
Merge combines the intervals from "is" and "is2" and returns
a new Intervals object containing all combined ranges from the
two inputs.
func (is Intervals) Merge(is2 Intervals) Intervals
MergeInto
method
#
MergeInto merges interval i2 into i1. This version happens to
require that the two intervals either overlap or are adjacent.
func (i1 *Interval) MergeInto(i2 Interval) error
MergeLocals
function
#
MergeLocals analyzes the specified ssa function f to determine which
of its auto variables can safely share the same stack slot, returning
a state object that describes how the overlap should be done.
func MergeLocals(fn *ir.Func, f *ssa.Func) *MergeLocalsState
Overlaps
method
#
Overlaps returns true if here is any overlap between i and i2.
func (i Interval) Overlaps(i2 Interval) bool
Overlaps
method
#
Overlaps returns whether any of the component ranges in is overlaps
with some range in is2.
func (is Intervals) Overlaps(is2 Intervals) bool
String
method
#
func (is *Intervals) String() string
String
method
#
func (i Interval) String() string
String
method
#
func (mls *MergeLocalsState) String() string
String
method
#
func (a nameOff) String() string
Subsumed
method
#
Subsumed returns whether variable n is subsumed, e.g. appears
in an overlap position but is not the leader in that partition.
func (mls *MergeLocalsState) Subsumed(n *ir.Name) bool
WriteFuncMap
function
#
WriteFuncMap writes the pointer bitmaps for bodyless function fn's
inputs and outputs as the value of symbol .args_stackmap.
If fn has outputs, two bitmaps are written, otherwise just one.
func WriteFuncMap(fn *ir.Func, abiInfo *abi.ABIParamResultInfo)
add
method
#
add adds bv to the set and returns its index in m.extractUnique,
and whether it is newly added.
If it is newly added, the caller must not modify bv after this.
func (m *bvecSet) add(bv bitvec.BitVec) (int, bool)
adjacent
method
#
adjacent returns true if the start of one interval is equal to the
end of another interval (e.g. they represent consecutive ranges).
func (i1 Interval) adjacent(i2 Interval) bool
affectedVar
function
#
affectedVar returns the *ir.Name node affected by v.
func affectedVar(v *ssa.Value) (*ir.Name, ssa.SymEffect)
blockEffects
method
#
func (lv *liveness) blockEffects(b *ssa.Block) *blockEffects
check
method
#
check tests for various inconsistencies and problems in mls,
returning an error if any problems are found.
func (mls *MergeLocalsState) check() error
check
function
#
check examines the intervals in "is" to try to find internal
inconsistencies or problems.
func check(is Intervals) error
clobber
function
#
clobber generates code to clobber pointer slots in all dead variables
(those not marked in live). Clobbering instructions are added to the end
of b.Values.
func clobber(lv *liveness, b *ssa.Block, live bitvec.BitVec)
clobber
method
#
Inserts code to clobber pointer slots in all the dead variables (locals and args)
at every synchronous safepoint in b.
func (lv *liveness) clobber(b *ssa.Block)
clobberPtr
function
#
clobberPtr generates a clobber of the pointer at offset offset in v.
The clobber instruction is added at the end of b.
func clobberPtr(b *ssa.Block, v *ir.Name, offset int64)
clobberVar
function
#
clobberVar generates code to trash the pointers in v.
Clobbering instructions are added to the end of b.Values.
func clobberVar(b *ssa.Block, v *ir.Name)
clobberWalk
function
#
b = block to which we append instructions
v = variable
offset = offset of (sub-portion of) variable to clobber (in bytes)
t = type of sub-portion of v.
func clobberWalk(b *ssa.Block, v *ir.Name, offset int64, t *types.Type)
collectMergeCandidates
method
#
collectMergeCandidates visits all of the AUTO vars declared in
function fn and identifies a list of candidate variables for
merging / overlapping. On return the "cands" field of cs will be
filled in with our set of potentially overlappable candidate
variables, the "regions" field will hold regions/sequence of
compatible vars within the candidates list, "nameToSlot" field will
be populated, and the "indirectUE" field will be filled in with
information about indirect upwards-exposed uses in the func.
func (cs *cstate) collectMergeCandidates()
compact
method
#
Compact coalesces identical bitmaps from lv.livevars into the sets
lv.stackMapSet.
Compact clears lv.livevars.
There are actually two lists of bitmaps, one list for the local variables and one
list for the function arguments. Both lists are indexed by the same PCDATA
index, so the corresponding pairs must be considered together when
merging duplicates. The argument bitmaps change much less often during
function execution than the local variable bitmaps, so it is possible that
we could introduce a separate PCDATA index for arguments vs locals and
then compact the set of argument bitmaps separately from the set of
local variable bitmaps. As of 2014-04-02, doing this to the godoc binary
is actually a net loss: we save about 50k of argument bitmaps but the new
PCDATA tables cost about 100k. So for now we keep using a single index for
both bitmap lists.
func (lv *liveness) compact(b *ssa.Block)
computeIntervals
method
#
computeIntervals performs a backwards sweep over the instructions
of the function we're compiling, building up an Intervals object
for each candidate variable by looking for upwards exposed uses
and kills.
func (cs *cstate) computeIntervals()
done
method
#
func (iwi intWithIdx) done() bool
dumpCand
function
#
func dumpCand(c *ir.Name, i int)
dumpFunc
method
#
func (cs *cstate) dumpFunc()
dumpFuncIfSelected
method
#
func (cs *cstate) dumpFuncIfSelected()
emit
method
#
func (lv *argLiveness) emit() *obj.LSym
emit
method
#
Dumps a slice of bitmaps to a symbol as a sequence of uint32 values. The
first word dumped is the total number of bitmaps. The second word is the
length of the bitmaps. All bitmaps are assumed to be of equal length. The
remaining bytes are the raw bitmaps.
func (lv *liveness) emit() (argsSym *obj.LSym, liveSym *obj.LSym)
emitStackObjects
method
#
func (lv *liveness) emitStackObjects() *obj.LSym
enableClobber
method
#
func (lv *liveness) enableClobber()
epilogue
method
#
Visits all instructions in a basic block and computes a bit vector of live
variables at each safe point locations.
func (lv *liveness) epilogue()
fmtFullPos
function
#
func fmtFullPos(p src.XPos) string
genRegions
method
#
genRegions generates a set of regions within cands corresponding
to potentially overlappable/mergeable variables.
func (cs *cstate) genRegions(cands []*ir.Name) ([]*ir.Name, []candRegion)
getvariables
function
#
getvariables returns the list of on-stack variables that we need to track
and a map for looking up indices by *Node.
func getvariables(fn *ir.Func) ([]*ir.Name, map[*ir.Name]int32)
grow
method
#
func (m *bvecSet) grow()
hasStackMap
method
#
Returns true for instructions that must have a stack map.
This does not necessarily mean the instruction is a safe-point. In
particular, call Values can have a stack map in case the callee
grows the stack, but not themselves be a safe-point.
func (lv *liveness) hasStackMap(v *ssa.Value) bool
hashbitmap
function
#
func hashbitmap(h uint32, bv bitvec.BitVec) uint32
imax
function
#
TEMPORARY until bootstrap version catches up.
func imax(i int, j int) int
imin
function
#
TEMPORARY until bootstrap version catches up.
func imin(i int, j int) int
init
method
#
init initializes a pairVisitor for the specified pair of intervals
i1 and i2 and returns an intWithIdx object that points to the first
interval by start position within i1/i2.
func (pv *pairVisitor) init(i1 Intervals, i2 Intervals) intWithIdx
initcache
method
#
func (lv *liveness) initcache()
isfat
function
#
isfat reports whether a variable of type t needs multiple assignments to initialize.
For example:
type T struct { x, y int }
x := T{x: 0, y: 1}
Then we need:
var t T
t.x = 0
t.y = 1
to fully initialize t.
func isfat(t *types.Type) bool
last
method
#
func (c *IntervalsBuilder) last() int
markUnsafePoints
method
#
markUnsafePoints finds unsafe points and computes lv.unsafePoints.
func (lv *liveness) markUnsafePoints()
mayFault
function
#
func mayFault(v *ssa.Value) bool
mergeVisitRegion
method
#
mergeVisitRegion tries to perform overlapping of variables with a
given subrange of cands described by st and en (indices into our
candidate var list), where the variables within this range have
already been determined to be compatible with respect to type,
size, etc. Overlapping is done in a greedy fashion: we select the
first element in the st->en range, then walk the rest of the
elements adding in vars whose lifetimes don't overlap with the
first element, then repeat the process until we run out of work.
Ordering of the candidates within the region [st,en] is important;
within the list the assumption is that if we overlap two variables
X and Y where X precedes Y in the list, we need to make X the
"leader" (keep X's slot and set Y's frame offset to X's) as opposed
to the other way around, since it's possible that Y is smaller in
size than X.
func (cs *cstate) mergeVisitRegion(mls *MergeLocalsState, st int, en int)
nameLess
function
#
nameLess compares ci with cj to see if ci should be less than cj in
a relative ordering of candidate variables. This is used to sort
vars by pointerness (variables with pointers first), then in order
of decreasing alignment, then by decreasing size. We are assuming a
merging algorithm that merges later entries in the list into
earlier entries. An example ordered candidate list produced by
nameLess:
idx name type align size
0: abc [10]*int 8 80
1: xyz [9]*int 8 72
2: qrs [2]*int 8 16
3: tuv [9]int 8 72
4: wxy [9]int32 4 36
5: jkl [8]int32 4 32
func nameLess(ci *ir.Name, cj *ir.Name) bool
newliveness
function
#
Constructs a new liveness structure used to hold the global state of the
liveness computation. The cfg argument is a slice of *BasicBlocks and the
vars argument is a slice of *Nodes.
func newliveness(fn *ir.Func, f *ssa.Func, vars []*ir.Name, idx map[*ir.Name]int32, stkptrsize int64) *liveness
nextRegion
function
#
nextRegion starts at location idx and walks forward in the cands
slice looking for variables that are "compatible" (potentially
overlappable, in the sense that they could potentially share the
stack slot of cands[idx]); it returns the end of the new region
(range of compatible variables starting at idx).
func nextRegion(cands []*ir.Name, idx int) int
nxt
method
#
nxt advances the pairVisitor to the next interval by starting
position within the pair, returning an intWithIdx that describes
the interval.
func (pv *pairVisitor) nxt() intWithIdx
performMerging
method
#
performMerging carries out variable merging within each of the
candidate ranges in regions, returning a state object
that describes the variable overlaps.
func (cs *cstate) performMerging() *MergeLocalsState
pointerMap
method
#
Generates live pointer value maps for arguments and local variables. The
this argument and the in arguments are always assumed live. The vars
argument is a slice of *Nodes.
func (lv *liveness) pointerMap(liveout bitvec.BitVec, vars []*ir.Name, args bitvec.BitVec, locals bitvec.BitVec)
populateIndirectUseTable
method
#
populateIndirectUseTable creates and populates the "indirectUE" table
within cs by doing some additional analysis of how the vars in
cands are accessed in the function.
It is possible to have situations where a given ir.Name is
non-address-taken at the source level, but whose address is
materialized in order to accommodate the needs of
architecture-dependent operations or one sort or another (examples
include things like LoweredZero/DuffZero, etc). The issue here is
that the SymAddr op will show up as touching a variable of
interest, but the subsequent memory op will not. This is generally
not an issue for computing whether something is live across a call,
but it is problematic for collecting the more fine-grained live
interval info that drives stack slot merging.
To handle this problem, make a forward pass over each basic block
looking for instructions of the form vK := SymAddr(N) where N is a
raw candidate. Create an entry in a map at that point from vK to
its use count. Continue the walk, looking for uses of vK: when we
see one, record it in a side table as an upwards exposed use of N.
Each time we see a use, decrement the use count in the map, and if
we hit zero, remove the map entry. If we hit the end of the basic
block and we still have map entries, then evict the name in
question from the candidate set.
func (cs *cstate) populateIndirectUseTable(cands []*ir.Name) ([]*ir.Name, []candRegion)
print
method
#
func (lv *argLiveness) print()
printDebug
method
#
Prints the computed liveness information and inputs, for debugging.
This format synthesizes the information used during the multiple passes
into a single presentation.
func (lv *liveness) printDebug()
printLivenessVec
method
#
func (lv *argLiveness) printLivenessVec(bv bitvec.BitVec)
printbvec
method
#
func (lv *liveness) printbvec(printed bool, name string, live bitvec.BitVec) bool
printeffect
method
#
printeffect is like printbvec, but for valueEffects.
func (lv *liveness) printeffect(printed bool, name string, pos int32, x bool) bool
prologue
method
#
Initializes the sets for solving the live variables. Visits all the
instructions in each basic block to summarizes the information at each basic
block
func (lv *liveness) prologue()
reset
method
#
func (m *Map) reset()
sel
method
#
sel is a helper function used by 'init' and 'nxt' above; it selects
the earlier of the two intervals at the current positions within i1
and i2, or a degenerate (pairIndex -1) intWithIdx if we have no
more intervals to visit.
func (pv *pairVisitor) sel() intWithIdx
set
method
#
func (m *Map) set(v *ssa.Value, i objw.StackMapIndex)
setLast
method
#
func (c *IntervalsBuilder) setLast(x int)
setUnsafeBlock
method
#
func (m *Map) setUnsafeBlock(b *ssa.Block)
setUnsafeVal
method
#
func (m *Map) setUnsafeVal(v *ssa.Value)
setupHashBisection
method
#
setupHashBisection checks to see if any of the candidate
variables have been de-selected by our hash debug. Here
we also implement the -d=mergelocalshtrace flag, which turns
on debug tracing only if we have at least two candidates
selected by the hash debug for this function.
func (cs *cstate) setupHashBisection(cands []*ir.Name)
shouldTrack
function
#
shouldTrack reports whether the liveness analysis
should track the variable n.
We don't care about variables that have no pointers,
nor do we care about non-local variables,
nor do we care about empty structs (handled by the pointer check),
nor do we care about the fake PAUTOHEAP variables.
func shouldTrack(n *ir.Name) bool
showlive
method
#
func (lv *liveness) showlive(v *ssa.Value, live bitvec.BitVec)
solve
method
#
Solve the liveness dataflow equations.
func (lv *liveness) solve()
valueEffect
method
#
valueEffect applies the effect of v to live, return whether it is changed.
func (lv *argLiveness) valueEffect(v *ssa.Value, live bitvec.BitVec) bool
valueEffects
method
#
valueEffects returns the index of a variable in lv.vars and the
liveness effects v has on that variable.
If v does not affect any tracked variables, it returns -1, 0.
func (lv *liveness) valueEffects(v *ssa.Value) (int32, liveEffect)