type MergeLocalsState … type candRegion … type cstate … // 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 { … } // 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 { … } // IsLeader returns whether a variable n is the leader (first element) // in a sharing partition. func (mls *MergeLocalsState) IsLeader(n *ir.Name) bool { … } // Leader returns the leader variable for subsumed var n. func (mls *MergeLocalsState) Leader(n *ir.Name) *ir.Name { … } // 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 { … } // 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) { … } // check tests for various inconsistencies and problems in mls, // returning an error if any problems are found. func (mls *MergeLocalsState) check() error { … } func (mls *MergeLocalsState) String() string { … } // 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() { … } // genRegions generates a set of regions within cands corresponding // to potentially overlappable/mergeable variables. func (cs *cstate) genRegions(cands []*ir.Name) ([]*ir.Name, []candRegion) { … } func (cs *cstate) dumpFunc() { … } func (cs *cstate) dumpFuncIfSelected() { … } // 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) { … } // 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) { … } type nameCount … // 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, cj *ir.Name) bool { … } // 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 { … } // 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, en int) { … } // 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 { … } // 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() { … } func fmtFullPos(p src.XPos) string { … } func dumpCand(c *ir.Name, i int) { … } // for unit testing only. func MakeMergeLocalsState(partition map[*ir.Name][]int, vars []*ir.Name) (*MergeLocalsState, error) { … }
Codebase Browser
go