Source file src/cmd/compile/internal/liveness/mergelocals.go

     1  // Copyright 2024 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package liveness
     6  
     7  import (
     8  	"cmd/compile/internal/base"
     9  	"cmd/compile/internal/bitvec"
    10  	"cmd/compile/internal/ir"
    11  	"cmd/compile/internal/ssa"
    12  	"cmd/compile/internal/ssa/ssaop"
    13  	"cmd/internal/src"
    14  	"fmt"
    15  	"os"
    16  	"path/filepath"
    17  	"slices"
    18  	"sort"
    19  	"strings"
    20  )
    21  
    22  // MergeLocalsState encapsulates information about which AUTO
    23  // (stack-allocated) variables within a function can be safely
    24  // merged/overlapped, e.g. share a stack slot with some other auto).
    25  // An instance of MergeLocalsState is produced by MergeLocals() below
    26  // and then consumed in ssagen.AllocFrame. The map 'partition'
    27  // contains entries of the form <N,SL> where N is an *ir.Name and SL
    28  // is a slice holding the indices (within 'vars') of other variables
    29  // that share the same slot, specifically the slot of the first
    30  // element in the partition, which we'll call the "leader". For
    31  // example, if a function contains five variables where v1/v2/v3 are
    32  // safe to overlap and v4/v5 are safe to overlap, the MergeLocalsState
    33  // content might look like
    34  //
    35  //	vars: [v1, v2, v3, v4, v5]
    36  //	partition: v1 -> [1, 0, 2], v2 -> [1, 0, 2], v3 -> [1, 0, 2]
    37  //	           v4 -> [3, 4], v5 -> [3, 4]
    38  //
    39  // A nil MergeLocalsState indicates that no local variables meet the
    40  // necessary criteria for overlap.
    41  type MergeLocalsState struct {
    42  	// contains auto vars that participate in overlapping
    43  	vars []*ir.Name
    44  	// maps auto variable to overlap partition
    45  	partition map[*ir.Name][]int
    46  }
    47  
    48  // candRegion is a sub-range (start, end) corresponding to an interval
    49  // [st,en] within the list of candidate variables.
    50  type candRegion struct {
    51  	st, en int
    52  }
    53  
    54  // cstate holds state information we'll need during the analysis
    55  // phase of stack slot merging but can be discarded when the analysis
    56  // is done.
    57  type cstate struct {
    58  	fn             *ir.Func
    59  	f              *ssa.Func
    60  	lv             *Liveness
    61  	cands          []*ir.Name
    62  	nameToSlot     map[*ir.Name]int32
    63  	regions        []candRegion
    64  	indirectUE     map[ssa.ID][]*ir.Name
    65  	ivs            []Intervals
    66  	hashDeselected map[*ir.Name]bool
    67  	trace          int // debug trace level
    68  }
    69  
    70  // MergeLocals analyzes the specified ssa function f to determine which
    71  // of its auto variables can safely share the same stack slot, returning
    72  // a state object that describes how the overlap should be done.
    73  func MergeLocals(fn *ir.Func, f *ssa.Func) *MergeLocalsState {
    74  
    75  	// Create a container object for useful state info and then
    76  	// call collectMergeCandidates to see if there are vars suitable
    77  	// for stack slot merging.
    78  	cs := &cstate{
    79  		fn:    fn,
    80  		f:     f,
    81  		trace: base.Debug.MergeLocalsTrace,
    82  	}
    83  	cs.collectMergeCandidates()
    84  	if len(cs.regions) == 0 {
    85  		return nil
    86  	}
    87  
    88  	// Kick off liveness analysis.
    89  	//
    90  	// If we have a local variable such as "r2" below that's written
    91  	// but then not read, something like:
    92  	//
    93  	//      vardef r1
    94  	//      r1.x = ...
    95  	//      vardef r2
    96  	//      r2.x = 0
    97  	//      r2.y = ...
    98  	//      <call foo>
    99  	//      // no subsequent use of r2
   100  	//      ... = r1.x
   101  	//
   102  	// then for the purpose of calculating stack maps at the call, we
   103  	// can ignore "r2" completely during liveness analysis for stack
   104  	// maps, however for stack slock merging we most definitely want
   105  	// to treat the writes as "uses".
   106  	cs.lv = newliveness(fn, f, cs.cands, cs.nameToSlot, 0)
   107  	cs.lv.conservativeWrites = true
   108  	cs.lv.prologue()
   109  	cs.lv.solve()
   110  
   111  	// Compute intervals for each candidate based on the liveness and
   112  	// on block effects.
   113  	cs.computeIntervals()
   114  
   115  	// Perform merging within each region of the candidates list.
   116  	rv := cs.performMerging()
   117  	if err := rv.check(); err != nil {
   118  		base.FatalfAt(fn.Pos(), "invalid mergelocals state: %v", err)
   119  	}
   120  	return rv
   121  }
   122  
   123  // Subsumed returns whether variable n is subsumed, e.g. appears
   124  // in an overlap position but is not the leader in that partition.
   125  func (mls *MergeLocalsState) Subsumed(n *ir.Name) bool {
   126  	if sl, ok := mls.partition[n]; ok && mls.vars[sl[0]] != n {
   127  		return true
   128  	}
   129  	return false
   130  }
   131  
   132  // IsLeader returns whether a variable n is the leader (first element)
   133  // in a sharing partition.
   134  func (mls *MergeLocalsState) IsLeader(n *ir.Name) bool {
   135  	if sl, ok := mls.partition[n]; ok && mls.vars[sl[0]] == n {
   136  		return true
   137  	}
   138  	return false
   139  }
   140  
   141  // Leader returns the leader variable for subsumed var n.
   142  func (mls *MergeLocalsState) Leader(n *ir.Name) *ir.Name {
   143  	if sl, ok := mls.partition[n]; ok {
   144  		if mls.vars[sl[0]] == n {
   145  			panic("variable is not subsumed")
   146  		}
   147  		return mls.vars[sl[0]]
   148  	}
   149  	panic("not a merge candidate")
   150  }
   151  
   152  // Followers writes a list of the followers for leader n into the slice tmp.
   153  func (mls *MergeLocalsState) Followers(n *ir.Name, tmp []*ir.Name) []*ir.Name {
   154  	tmp = tmp[:0]
   155  	sl, ok := mls.partition[n]
   156  	if !ok {
   157  		panic("no entry for leader")
   158  	}
   159  	if mls.vars[sl[0]] != n {
   160  		panic("followers invoked on subsumed var")
   161  	}
   162  	for _, k := range sl[1:] {
   163  		tmp = append(tmp, mls.vars[k])
   164  	}
   165  	slices.SortStableFunc(tmp, func(a, b *ir.Name) int {
   166  		return strings.Compare(a.Sym().Name, b.Sym().Name)
   167  	})
   168  	return tmp
   169  }
   170  
   171  // EstSavings returns the estimated reduction in stack size (number of bytes) for
   172  // the given merge locals state via a pair of ints, the first for non-pointer types and the second for pointer types.
   173  func (mls *MergeLocalsState) EstSavings() (int, int) {
   174  	totnp := 0
   175  	totp := 0
   176  	for n := range mls.partition {
   177  		if mls.Subsumed(n) {
   178  			sz := int(n.Type().Size())
   179  			if n.Type().HasPointers() {
   180  				totp += sz
   181  			} else {
   182  				totnp += sz
   183  			}
   184  		}
   185  	}
   186  	return totnp, totp
   187  }
   188  
   189  // check tests for various inconsistencies and problems in mls,
   190  // returning an error if any problems are found.
   191  func (mls *MergeLocalsState) check() error {
   192  	if mls == nil {
   193  		return nil
   194  	}
   195  	used := make(map[int]bool)
   196  	seenv := make(map[*ir.Name]int)
   197  	for ii, v := range mls.vars {
   198  		if prev, ok := seenv[v]; ok {
   199  			return fmt.Errorf("duplicate var %q in vslots: %d and %d\n",
   200  				v.Sym().Name, ii, prev)
   201  		}
   202  		seenv[v] = ii
   203  	}
   204  	for k, sl := range mls.partition {
   205  		// length of slice value needs to be more than 1
   206  		if len(sl) < 2 {
   207  			return fmt.Errorf("k=%q v=%+v slice len %d invalid",
   208  				k.Sym().Name, sl, len(sl))
   209  		}
   210  		// values in the slice need to be var indices
   211  		for i, v := range sl {
   212  			if v < 0 || v > len(mls.vars)-1 {
   213  				return fmt.Errorf("k=%q v=+%v slpos %d vslot %d out of range of m.v", k.Sym().Name, sl, i, v)
   214  			}
   215  		}
   216  	}
   217  	for k, sl := range mls.partition {
   218  		foundk := false
   219  		for i, v := range sl {
   220  			vv := mls.vars[v]
   221  			if i == 0 {
   222  				if !mls.IsLeader(vv) {
   223  					return fmt.Errorf("k=%s v=+%v slpos 0 vslot %d IsLeader(%q) is false should be true", k.Sym().Name, sl, v, vv.Sym().Name)
   224  				}
   225  			} else {
   226  				if !mls.Subsumed(vv) {
   227  					return fmt.Errorf("k=%s v=+%v slpos %d vslot %d Subsumed(%q) is false should be true", k.Sym().Name, sl, i, v, vv.Sym().Name)
   228  				}
   229  				if mls.Leader(vv) != mls.vars[sl[0]] {
   230  					return fmt.Errorf("k=%s v=+%v slpos %d vslot %d Leader(%q) got %v want %v", k.Sym().Name, sl, i, v, vv.Sym().Name, mls.Leader(vv), mls.vars[sl[0]])
   231  				}
   232  			}
   233  			if vv == k {
   234  				foundk = true
   235  				if used[v] {
   236  					return fmt.Errorf("k=%s v=+%v val slice used violation at slpos %d vslot %d", k.Sym().Name, sl, i, v)
   237  				}
   238  				used[v] = true
   239  			}
   240  		}
   241  		if !foundk {
   242  			return fmt.Errorf("k=%s v=+%v slice value missing k", k.Sym().Name, sl)
   243  		}
   244  		vl := mls.vars[sl[0]]
   245  		for _, v := range sl[1:] {
   246  			vv := mls.vars[v]
   247  			if vv.Type().Size() > vl.Type().Size() {
   248  				return fmt.Errorf("k=%s v=+%v follower %s size %d larger than leader %s size %d", k.Sym().Name, sl, vv.Sym().Name, vv.Type().Size(), vl.Sym().Name, vl.Type().Size())
   249  			}
   250  			if vv.Type().HasPointers() && !vl.Type().HasPointers() {
   251  				return fmt.Errorf("k=%s v=+%v follower %s hasptr=true but leader %s hasptr=false", k.Sym().Name, sl, vv.Sym().Name, vl.Sym().Name)
   252  			}
   253  			if vv.Type().Alignment() > vl.Type().Alignment() {
   254  				return fmt.Errorf("k=%s v=+%v follower %s align %d greater than leader %s align %d", k.Sym().Name, sl, vv.Sym().Name, vv.Type().Alignment(), vl.Sym().Name, vl.Type().Alignment())
   255  			}
   256  		}
   257  	}
   258  	for i := range used {
   259  		if !used[i] {
   260  			return fmt.Errorf("pos %d var %q unused", i, mls.vars[i])
   261  		}
   262  	}
   263  	return nil
   264  }
   265  
   266  func (mls *MergeLocalsState) String() string {
   267  	var leaders []*ir.Name
   268  	for n, sl := range mls.partition {
   269  		if n == mls.vars[sl[0]] {
   270  			leaders = append(leaders, n)
   271  		}
   272  	}
   273  	slices.SortFunc(leaders, func(a, b *ir.Name) int {
   274  		return strings.Compare(a.Sym().Name, b.Sym().Name)
   275  	})
   276  	var sb strings.Builder
   277  	for _, n := range leaders {
   278  		sb.WriteString(n.Sym().Name + ":")
   279  		sl := mls.partition[n]
   280  		for _, k := range sl[1:] {
   281  			n := mls.vars[k]
   282  			sb.WriteString(" " + n.Sym().Name)
   283  		}
   284  		sb.WriteString("\n")
   285  	}
   286  	return sb.String()
   287  }
   288  
   289  // collectMergeCandidates visits all of the AUTO vars declared in
   290  // function fn and identifies a list of candidate variables for
   291  // merging / overlapping. On return the "cands" field of cs will be
   292  // filled in with our set of potentially overlappable candidate
   293  // variables, the "regions" field will hold regions/sequence of
   294  // compatible vars within the candidates list, "nameToSlot" field will
   295  // be populated, and the "indirectUE" field will be filled in with
   296  // information about indirect upwards-exposed uses in the func.
   297  func (cs *cstate) collectMergeCandidates() {
   298  	var cands []*ir.Name
   299  
   300  	// Collect up the available set of appropriate AUTOs in the
   301  	// function as a first step, and bail if we have fewer than
   302  	// two candidates.
   303  	for _, n := range cs.fn.Dcl {
   304  		if !n.Used() {
   305  			continue
   306  		}
   307  		if !ssa.IsMergeCandidate(n) {
   308  			continue
   309  		}
   310  		cands = append(cands, n)
   311  	}
   312  	if len(cands) < 2 {
   313  		return
   314  	}
   315  
   316  	// Sort by pointerness, size, and then name.
   317  	sort.SliceStable(cands, func(i, j int) bool {
   318  		return nameLess(cands[i], cands[j])
   319  	})
   320  
   321  	if cs.trace > 1 {
   322  		fmt.Fprintf(os.Stderr, "=-= raw cand list for func %v:\n", cs.fn)
   323  		for i := range cands {
   324  			dumpCand(cands[i], i)
   325  		}
   326  	}
   327  
   328  	// Now generate an initial pruned candidate list and regions list.
   329  	// This may be empty if we don't have enough compatible candidates.
   330  	initial, _ := cs.genRegions(cands)
   331  	if len(initial) < 2 {
   332  		return
   333  	}
   334  
   335  	// Set up for hash bisection if enabled.
   336  	cs.setupHashBisection(initial)
   337  
   338  	// Create and populate an indirect use table that we'll use
   339  	// during interval construction. As part of this process we may
   340  	// wind up tossing out additional candidates, so check to make
   341  	// sure we still have something to work with.
   342  	cs.cands, cs.regions = cs.populateIndirectUseTable(initial)
   343  	if len(cs.cands) < 2 {
   344  		return
   345  	}
   346  
   347  	// At this point we have a final pruned set of candidates and a
   348  	// corresponding set of regions for the candidates. Build a
   349  	// name-to-slot map for the candidates.
   350  	cs.nameToSlot = make(map[*ir.Name]int32)
   351  	for i, n := range cs.cands {
   352  		cs.nameToSlot[n] = int32(i)
   353  	}
   354  
   355  	if cs.trace > 1 {
   356  		fmt.Fprintf(os.Stderr, "=-= pruned candidate list for fn %v:\n", cs.fn)
   357  		for i := range cs.cands {
   358  			dumpCand(cs.cands[i], i)
   359  		}
   360  	}
   361  }
   362  
   363  // genRegions generates a set of regions within cands corresponding
   364  // to potentially overlappable/mergeable variables.
   365  func (cs *cstate) genRegions(cands []*ir.Name) ([]*ir.Name, []candRegion) {
   366  	var pruned []*ir.Name
   367  	var regions []candRegion
   368  	st := 0
   369  	for {
   370  		en := nextRegion(cands, st)
   371  		if en == -1 {
   372  			break
   373  		}
   374  		if st == en {
   375  			// region has just one element, we can skip it
   376  			st++
   377  			continue
   378  		}
   379  		pst := len(pruned)
   380  		pen := pst + (en - st)
   381  		if cs.trace > 1 {
   382  			fmt.Fprintf(os.Stderr, "=-= addregion st=%d en=%d: add part %d -> %d\n", st, en, pst, pen)
   383  		}
   384  
   385  		// non-empty region, add to pruned
   386  		pruned = append(pruned, cands[st:en+1]...)
   387  		regions = append(regions, candRegion{st: pst, en: pen})
   388  		st = en + 1
   389  	}
   390  	if len(pruned) < 2 {
   391  		return nil, nil
   392  	}
   393  	return pruned, regions
   394  }
   395  
   396  func (cs *cstate) dumpFunc() {
   397  	fmt.Fprintf(os.Stderr, "=-= mergelocalsdumpfunc %v:\n", cs.fn)
   398  	ii := 0
   399  	for k, b := range cs.f.Blocks {
   400  		fmt.Fprintf(os.Stderr, "b%d:\n", k)
   401  		for _, v := range b.Values {
   402  			pos := base.Ctxt.PosTable.Pos(v.Pos)
   403  			fmt.Fprintf(os.Stderr, "=-= %d L%d|C%d %s\n", ii, pos.RelLine(), pos.RelCol(), v.LongString())
   404  			ii++
   405  		}
   406  	}
   407  }
   408  
   409  func (cs *cstate) dumpFuncIfSelected() {
   410  	if base.Debug.MergeLocalsDumpFunc == "" {
   411  		return
   412  	}
   413  	if !strings.HasSuffix(fmt.Sprintf("%v", cs.fn),
   414  		base.Debug.MergeLocalsDumpFunc) {
   415  		return
   416  	}
   417  	cs.dumpFunc()
   418  }
   419  
   420  // setupHashBisection checks to see if any of the candidate
   421  // variables have been de-selected by our hash debug. Here
   422  // we also implement the -d=mergelocalshtrace flag, which turns
   423  // on debug tracing only if we have at least two candidates
   424  // selected by the hash debug for this function.
   425  func (cs *cstate) setupHashBisection(cands []*ir.Name) {
   426  	if base.Debug.MergeLocalsHash == "" {
   427  		return
   428  	}
   429  	deselected := make(map[*ir.Name]bool)
   430  	selCount := 0
   431  	for _, cand := range cands {
   432  		if !base.MergeLocalsHash.MatchPosWithInfo(cand.Pos(), "mergelocals", nil) {
   433  			deselected[cand] = true
   434  		} else {
   435  			deselected[cand] = false
   436  			selCount++
   437  		}
   438  	}
   439  	if selCount < len(cands) {
   440  		cs.hashDeselected = deselected
   441  	}
   442  	if base.Debug.MergeLocalsHTrace != 0 && selCount >= 2 {
   443  		cs.trace = base.Debug.MergeLocalsHTrace
   444  	}
   445  }
   446  
   447  // populateIndirectUseTable creates and populates the "indirectUE" table
   448  // within cs by doing some additional analysis of how the vars in
   449  // cands are accessed in the function.
   450  //
   451  // It is possible to have situations where a given ir.Name is
   452  // non-address-taken at the source level, but whose address is
   453  // materialized in order to accommodate the needs of
   454  // architecture-dependent operations or one sort or another (examples
   455  // include things like LoweredZero/DuffZero, etc). The issue here is
   456  // that the SymAddr op will show up as touching a variable of
   457  // interest, but the subsequent memory op will not. This is generally
   458  // not an issue for computing whether something is live across a call,
   459  // but it is problematic for collecting the more fine-grained live
   460  // interval info that drives stack slot merging.
   461  //
   462  // To handle this problem, make a forward pass over each basic block
   463  // looking for instructions of the form vK := SymAddr(N) where N is a
   464  // raw candidate. Create an entry in a map at that point from vK to
   465  // its use count. Continue the walk, looking for uses of vK: when we
   466  // see one, record it in a side table as an upwards exposed use of N.
   467  // Each time we see a use, decrement the use count in the map, and if
   468  // we hit zero, remove the map entry. If we hit the end of the basic
   469  // block and we still have map entries, then evict the name in
   470  // question from the candidate set.
   471  func (cs *cstate) populateIndirectUseTable(cands []*ir.Name) ([]*ir.Name, []candRegion) {
   472  
   473  	// main indirect UE table, this is what we're producing in this func
   474  	indirectUE := make(map[ssa.ID][]*ir.Name)
   475  
   476  	// this map holds the current set of candidates; the set may
   477  	// shrink if we have to evict any candidates.
   478  	rawcands := make(map[*ir.Name]struct{})
   479  
   480  	// maps ssa value V to the ir.Name it is taking the addr of,
   481  	// plus a count of the uses we've seen of V during a block walk.
   482  	pendingUses := make(map[ssa.ID]nameCount)
   483  
   484  	// A temporary indirect UE tab just for the current block
   485  	// being processed; used to help with evictions.
   486  	blockIndirectUE := make(map[ssa.ID][]*ir.Name)
   487  
   488  	// temporary map used to record evictions in a given block.
   489  	evicted := make(map[*ir.Name]bool)
   490  	for _, n := range cands {
   491  		rawcands[n] = struct{}{}
   492  	}
   493  	for k := 0; k < len(cs.f.Blocks); k++ {
   494  		clear(pendingUses)
   495  		clear(blockIndirectUE)
   496  		b := cs.f.Blocks[k]
   497  		for _, v := range b.Values {
   498  			if n, e := affectedVar(v); n != nil {
   499  				if _, ok := rawcands[n]; ok {
   500  					if e&ssaop.SymAddr != 0 && v.Uses != 0 {
   501  						// we're taking the address of candidate var n
   502  						if _, ok := pendingUses[v.ID]; ok {
   503  							// should never happen
   504  							base.FatalfAt(v.Pos, "internal error: apparent multiple defs for SSA value %d", v.ID)
   505  						}
   506  						// Stash an entry in pendingUses recording
   507  						// that we took the address of "n" via this
   508  						// val.
   509  						pendingUses[v.ID] = nameCount{n: n, count: v.Uses}
   510  						if cs.trace > 2 {
   511  							fmt.Fprintf(os.Stderr, "=-= SymAddr(%s) on %s\n",
   512  								n.Sym().Name, v.LongString())
   513  						}
   514  					}
   515  				}
   516  			}
   517  			for idx, arg := range v.Args {
   518  				if nc, ok := pendingUses[arg.ID]; ok {
   519  					if !v.AddrSinkArg(idx) {
   520  						// If this op may propagate its input address
   521  						// to somewhere else, we must track where that
   522  						// somewhere else might be. See issue 80127.
   523  						if v.Type.IsMemory() {
   524  							// Might be stored to memory. Give up.
   525  							continue
   526  						}
   527  						// Some sort of address arithmetic.
   528  						if _, ok := pendingUses[v.ID]; ok {
   529  							// v has used multiple addresses, which is something
   530  							// we can't keep track of. Give up.
   531  							continue
   532  						}
   533  						// Treat this op as producing the address of the same variable
   534  						// that its argument was the address of.
   535  						pendingUses[v.ID] = nameCount{n: nc.n, count: v.Uses}
   536  					}
   537  					// We found a use of some value that took the
   538  					// address of nc.n. Record this inst as a
   539  					// potential indirect use.
   540  					if cs.trace > 2 {
   541  						fmt.Fprintf(os.Stderr, "=-= add indirectUE(%s) count=%d on %s\n", nc.n.Sym().Name, nc.count, v.LongString())
   542  					}
   543  					blockIndirectUE[v.ID] = append(blockIndirectUE[v.ID], nc.n)
   544  					nc.count--
   545  					if nc.count == 0 {
   546  						// That was the last use of the value. Clean
   547  						// up the entry in pendingUses.
   548  						if cs.trace > 2 {
   549  							fmt.Fprintf(os.Stderr, "=-= last use of v%d\n",
   550  								arg.ID)
   551  						}
   552  						delete(pendingUses, arg.ID)
   553  					} else {
   554  						// Not the last use; record the decremented
   555  						// use count and move on.
   556  						pendingUses[arg.ID] = nc
   557  					}
   558  				}
   559  			}
   560  		}
   561  
   562  		// We've reached the end of this basic block: if we have any
   563  		// leftover entries in pendingUses, then evict the
   564  		// corresponding names from the candidate set. The idea here
   565  		// is that if we materialized the address of some local and
   566  		// that value is flowing out of the block off somewhere else,
   567  		// we're going to treat that local as truly address-taken and
   568  		// not have it be a merge candidate.
   569  		clear(evicted)
   570  		if len(pendingUses) != 0 {
   571  			for id, nc := range pendingUses {
   572  				if cs.trace > 2 {
   573  					fmt.Fprintf(os.Stderr, "=-= evicting %q due to pendingUse %d count %d\n", nc.n.Sym().Name, id, nc.count)
   574  				}
   575  				delete(rawcands, nc.n)
   576  				evicted[nc.n] = true
   577  			}
   578  		}
   579  		// Copy entries from blockIndirectUE into final indirectUE. Skip
   580  		// anything that we evicted in the loop above.
   581  		for id, sl := range blockIndirectUE {
   582  			for _, n := range sl {
   583  				if evicted[n] {
   584  					continue
   585  				}
   586  				indirectUE[id] = append(indirectUE[id], n)
   587  				if cs.trace > 2 {
   588  					fmt.Fprintf(os.Stderr, "=-= add final indUE v%d name %s\n", id, n.Sym().Name)
   589  				}
   590  			}
   591  		}
   592  	}
   593  	if len(rawcands) < 2 {
   594  		return nil, nil
   595  	}
   596  	cs.indirectUE = indirectUE
   597  	if cs.trace > 2 {
   598  		fmt.Fprintf(os.Stderr, "=-= iuetab:\n")
   599  		ids := make([]ssa.ID, 0, len(indirectUE))
   600  		for k := range indirectUE {
   601  			ids = append(ids, k)
   602  		}
   603  		slices.Sort(ids)
   604  		for _, id := range ids {
   605  			fmt.Fprintf(os.Stderr, "  v%d:", id)
   606  			for _, n := range indirectUE[id] {
   607  				fmt.Fprintf(os.Stderr, " %s", n.Sym().Name)
   608  			}
   609  			fmt.Fprintf(os.Stderr, "\n")
   610  		}
   611  	}
   612  
   613  	pruned := cands[:0]
   614  	for k := range rawcands {
   615  		pruned = append(pruned, k)
   616  	}
   617  	sort.Slice(pruned, func(i, j int) bool {
   618  		return nameLess(pruned[i], pruned[j])
   619  	})
   620  	var regions []candRegion
   621  	pruned, regions = cs.genRegions(pruned)
   622  	if len(pruned) < 2 {
   623  		return nil, nil
   624  	}
   625  	return pruned, regions
   626  }
   627  
   628  type nameCount struct {
   629  	n     *ir.Name
   630  	count int32
   631  }
   632  
   633  // nameLess compares ci with cj to see if ci should be less than cj in
   634  // a relative ordering of candidate variables. This is used to sort
   635  // vars by pointerness (variables with pointers first), then in order
   636  // of decreasing alignment, then by decreasing size. We are assuming a
   637  // merging algorithm that merges later entries in the list into
   638  // earlier entries. An example ordered candidate list produced by
   639  // nameLess:
   640  //
   641  //	idx   name    type       align    size
   642  //	0:    abc     [10]*int   8        80
   643  //	1:    xyz     [9]*int    8        72
   644  //	2:    qrs     [2]*int    8        16
   645  //	3:    tuv     [9]int     8        72
   646  //	4:    wxy     [9]int32   4        36
   647  //	5:    jkl     [8]int32   4        32
   648  func nameLess(ci, cj *ir.Name) bool {
   649  	if ci.Type().HasPointers() != cj.Type().HasPointers() {
   650  		return ci.Type().HasPointers()
   651  	}
   652  	if ci.Type().Alignment() != cj.Type().Alignment() {
   653  		return cj.Type().Alignment() < ci.Type().Alignment()
   654  	}
   655  	if ci.Type().Size() != cj.Type().Size() {
   656  		return cj.Type().Size() < ci.Type().Size()
   657  	}
   658  	if ci.Sym().Name != cj.Sym().Name {
   659  		return ci.Sym().Name < cj.Sym().Name
   660  	}
   661  	return fmt.Sprintf("%v", ci.Pos()) < fmt.Sprintf("%v", cj.Pos())
   662  }
   663  
   664  // nextRegion starts at location idx and walks forward in the cands
   665  // slice looking for variables that are "compatible" (potentially
   666  // overlappable, in the sense that they could potentially share the
   667  // stack slot of cands[idx]); it returns the end of the new region
   668  // (range of compatible variables starting at idx).
   669  func nextRegion(cands []*ir.Name, idx int) int {
   670  	n := len(cands)
   671  	if idx >= n {
   672  		return -1
   673  	}
   674  	c0 := cands[idx]
   675  	szprev := c0.Type().Size()
   676  	alnprev := c0.Type().Alignment()
   677  	for j := idx + 1; j < n; j++ {
   678  		cj := cands[j]
   679  		szj := cj.Type().Size()
   680  		if szj > szprev {
   681  			return j - 1
   682  		}
   683  		alnj := cj.Type().Alignment()
   684  		if alnj > alnprev {
   685  			return j - 1
   686  		}
   687  		szprev = szj
   688  		alnprev = alnj
   689  	}
   690  	return n - 1
   691  }
   692  
   693  // mergeVisitRegion tries to perform overlapping of variables with a
   694  // given subrange of cands described by st and en (indices into our
   695  // candidate var list), where the variables within this range have
   696  // already been determined to be compatible with respect to type,
   697  // size, etc. Overlapping is done in a greedy fashion: we select the
   698  // first element in the st->en range, then walk the rest of the
   699  // elements adding in vars whose lifetimes don't overlap with the
   700  // first element, then repeat the process until we run out of work.
   701  // Ordering of the candidates within the region [st,en] is important;
   702  // within the list the assumption is that if we overlap two variables
   703  // X and Y where X precedes Y in the list, we need to make X the
   704  // "leader" (keep X's slot and set Y's frame offset to X's) as opposed
   705  // to the other way around, since it's possible that Y is smaller in
   706  // size than X.
   707  func (cs *cstate) mergeVisitRegion(mls *MergeLocalsState, st, en int) {
   708  	if cs.trace > 1 {
   709  		fmt.Fprintf(os.Stderr, "=-= mergeVisitRegion(st=%d, en=%d)\n", st, en)
   710  	}
   711  	n := en - st + 1
   712  	used := bitvec.New(int32(n))
   713  
   714  	nxt := func(slot int) int {
   715  		for c := slot - st; c < n; c++ {
   716  			if used.Get(int32(c)) {
   717  				continue
   718  			}
   719  			return c + st
   720  		}
   721  		return -1
   722  	}
   723  
   724  	navail := n
   725  	cands := cs.cands
   726  	ivs := cs.ivs
   727  	if cs.trace > 1 {
   728  		fmt.Fprintf(os.Stderr, "  =-= navail = %d\n", navail)
   729  	}
   730  	for navail >= 2 {
   731  		leader := nxt(st)
   732  		used.Set(int32(leader - st))
   733  		navail--
   734  
   735  		if cs.trace > 1 {
   736  			fmt.Fprintf(os.Stderr, "  =-= begin leader %d used=%s\n", leader,
   737  				used.String())
   738  		}
   739  		elems := []int{leader}
   740  		lints := ivs[leader]
   741  
   742  		for succ := nxt(leader + 1); succ != -1; succ = nxt(succ + 1) {
   743  
   744  			// Skip if de-selected by merge locals hash.
   745  			if cs.hashDeselected != nil && cs.hashDeselected[cands[succ]] {
   746  				continue
   747  			}
   748  			// Skip if already used.
   749  			if used.Get(int32(succ - st)) {
   750  				continue
   751  			}
   752  			if cs.trace > 1 {
   753  				fmt.Fprintf(os.Stderr, "  =-= overlap of %d[%v] {%s} with %d[%v] {%s} is: %v\n", leader, cands[leader], lints.String(), succ, cands[succ], ivs[succ].String(), lints.Overlaps(ivs[succ]))
   754  			}
   755  
   756  			// Can we overlap leader with this var?
   757  			if lints.Overlaps(ivs[succ]) {
   758  				continue
   759  			} else {
   760  				// Add to overlap set.
   761  				elems = append(elems, succ)
   762  				lints = lints.Merge(ivs[succ])
   763  			}
   764  		}
   765  		if len(elems) > 1 {
   766  			// We found some things to overlap with leader. Add the
   767  			// candidate elements to "vars" and update "partition".
   768  			off := len(mls.vars)
   769  			sl := make([]int, len(elems))
   770  			for i, candslot := range elems {
   771  				sl[i] = off + i
   772  				mls.vars = append(mls.vars, cands[candslot])
   773  				mls.partition[cands[candslot]] = sl
   774  			}
   775  			navail -= (len(elems) - 1)
   776  			for i := range elems {
   777  				used.Set(int32(elems[i] - st))
   778  			}
   779  			if cs.trace > 1 {
   780  				fmt.Fprintf(os.Stderr, "=-= overlapping %+v:\n", sl)
   781  				for i := range sl {
   782  					dumpCand(mls.vars[sl[i]], sl[i])
   783  				}
   784  				for i, v := range elems {
   785  					fmt.Fprintf(os.Stderr, "=-= %d: sl=%d %s\n", i, v, ivs[v])
   786  				}
   787  			}
   788  		}
   789  	}
   790  }
   791  
   792  // performMerging carries out variable merging within each of the
   793  // candidate ranges in regions, returning a state object
   794  // that describes the variable overlaps.
   795  func (cs *cstate) performMerging() *MergeLocalsState {
   796  	cands := cs.cands
   797  
   798  	mls := &MergeLocalsState{
   799  		partition: make(map[*ir.Name][]int),
   800  	}
   801  
   802  	// Dump state before attempting overlap.
   803  	if cs.trace > 1 {
   804  		fmt.Fprintf(os.Stderr, "=-= cands live before overlap:\n")
   805  		for i := range cands {
   806  			c := cands[i]
   807  			fmt.Fprintf(os.Stderr, "%d: %v sz=%d ivs=%s\n",
   808  				i, c.Sym().Name, c.Type().Size(), cs.ivs[i].String())
   809  		}
   810  		fmt.Fprintf(os.Stderr, "=-= regions (%d): ", len(cs.regions))
   811  		for _, cr := range cs.regions {
   812  			fmt.Fprintf(os.Stderr, " [%d,%d]", cr.st, cr.en)
   813  		}
   814  		fmt.Fprintf(os.Stderr, "\n")
   815  	}
   816  
   817  	// Apply a greedy merge/overlap strategy within each region
   818  	// of compatible variables.
   819  	for _, cr := range cs.regions {
   820  		cs.mergeVisitRegion(mls, cr.st, cr.en)
   821  	}
   822  	if len(mls.vars) == 0 {
   823  		return nil
   824  	}
   825  	return mls
   826  }
   827  
   828  // computeIntervals performs a backwards sweep over the instructions
   829  // of the function we're compiling, building up an Intervals object
   830  // for each candidate variable by looking for upwards exposed uses
   831  // and kills.
   832  func (cs *cstate) computeIntervals() {
   833  	lv := cs.lv
   834  	ibuilders := make([]IntervalsBuilder, len(cs.cands))
   835  	nvars := int32(len(lv.vars))
   836  	liveout := bitvec.New(nvars)
   837  
   838  	cs.dumpFuncIfSelected()
   839  
   840  	// Count instructions.
   841  	ninstr := 0
   842  	for _, b := range lv.f.Blocks {
   843  		ninstr += len(b.Values)
   844  	}
   845  	// current instruction index during backwards walk
   846  	iidx := ninstr - 1
   847  
   848  	// Make a backwards pass over all blocks
   849  	for k := len(lv.f.Blocks) - 1; k >= 0; k-- {
   850  		b := lv.f.Blocks[k]
   851  		be := lv.blockEffects(b)
   852  
   853  		if cs.trace > 2 {
   854  			fmt.Fprintf(os.Stderr, "=-= liveout from tail of b%d: ", k)
   855  			for j := range lv.vars {
   856  				if be.liveout.Get(int32(j)) {
   857  					fmt.Fprintf(os.Stderr, " %q", lv.vars[j].Sym().Name)
   858  				}
   859  			}
   860  			fmt.Fprintf(os.Stderr, "\n")
   861  		}
   862  
   863  		// Take into account effects taking place at end of this basic
   864  		// block by comparing our current live set with liveout for
   865  		// the block. If a given var was not live before and is now
   866  		// becoming live we need to mark this transition with a
   867  		// builder "Live" call; similarly if a var was live before and
   868  		// is now no longer live, we need a "Kill" call.
   869  		for j := range lv.vars {
   870  			isLive := liveout.Get(int32(j))
   871  			blockLiveOut := be.liveout.Get(int32(j))
   872  			if isLive {
   873  				if !blockLiveOut {
   874  					if cs.trace > 2 {
   875  						fmt.Fprintf(os.Stderr, "=+= at instr %d block boundary kill of %v\n", iidx, lv.vars[j])
   876  					}
   877  					ibuilders[j].Kill(iidx)
   878  				}
   879  			} else if blockLiveOut {
   880  				if cs.trace > 2 {
   881  					fmt.Fprintf(os.Stderr, "=+= at block-end instr %d %v becomes live\n",
   882  						iidx, lv.vars[j])
   883  				}
   884  				ibuilders[j].Live(iidx)
   885  			}
   886  		}
   887  
   888  		// Set our working "currently live" set to the previously
   889  		// computed live out set for the block.
   890  		liveout.Copy(be.liveout)
   891  
   892  		// Now walk backwards through this block.
   893  		for i := len(b.Values) - 1; i >= 0; i-- {
   894  			v := b.Values[i]
   895  
   896  			if cs.trace > 2 {
   897  				fmt.Fprintf(os.Stderr, "=-= b%d instr %d: %s\n", k, iidx, v.LongString())
   898  			}
   899  
   900  			// Update liveness based on what we see happening in this
   901  			// instruction.
   902  			pos, e := lv.valueEffects(v)
   903  			becomeslive := e&uevar != 0
   904  			iskilled := e&varkill != 0
   905  			if becomeslive && iskilled {
   906  				// we do not ever expect to see both a kill and an
   907  				// upwards exposed use given our size constraints.
   908  				panic("should never happen")
   909  			}
   910  			if iskilled && liveout.Get(pos) {
   911  				ibuilders[pos].Kill(iidx)
   912  				liveout.Unset(pos)
   913  				if cs.trace > 2 {
   914  					fmt.Fprintf(os.Stderr, "=+= at instr %d kill of %v\n",
   915  						iidx, lv.vars[pos])
   916  				}
   917  			} else if becomeslive && !liveout.Get(pos) {
   918  				ibuilders[pos].Live(iidx)
   919  				liveout.Set(pos)
   920  				if cs.trace > 2 {
   921  					fmt.Fprintf(os.Stderr, "=+= at instr %d upwards-exposed use of %v\n",
   922  						iidx, lv.vars[pos])
   923  				}
   924  			}
   925  
   926  			if cs.indirectUE != nil {
   927  				// Now handle "indirect" upwards-exposed uses.
   928  				ues := cs.indirectUE[v.ID]
   929  				for _, n := range ues {
   930  					if pos, ok := lv.idx[n]; ok {
   931  						if !liveout.Get(pos) {
   932  							ibuilders[pos].Live(iidx)
   933  							liveout.Set(pos)
   934  							if cs.trace > 2 {
   935  								fmt.Fprintf(os.Stderr, "=+= at instr %d v%d indirect upwards-exposed use of %v\n", iidx, v.ID, lv.vars[pos])
   936  							}
   937  						}
   938  					}
   939  				}
   940  			}
   941  			iidx--
   942  		}
   943  
   944  		// This check disabled for now due to the way scheduling works
   945  		// for ops that materialize values of local variables. For
   946  		// many architecture we have rewrite rules of this form:
   947  		//
   948  		// (LocalAddr <t> {sym} base mem) && t.Elem().HasPointers() => (MOVDaddr {sym} (SPanchored base mem))
   949  		// (LocalAddr <t> {sym} base _)  && !t.Elem().HasPointers() => (MOVDaddr {sym} base)
   950  		//
   951  		// which are designed to ensure that if you have a pointerful
   952  		// variable "abc" sequence
   953  		//
   954  		//    v30 = VarDef <mem> {abc} v21
   955  		//    v31 = LocalAddr <*SB> {abc} v2 v30
   956  		//    v32 = Zero <mem> {SB} [2056] v31 v30
   957  		//
   958  		// this will be lowered into
   959  		//
   960  		//    v30 = VarDef <mem> {sb} v21
   961  		//   v106 = SPanchored <uintptr> v2 v30
   962  		//    v31 = MOVDaddr <*SB> {sb} v106
   963  		//     v3 = DUFFZERO <mem> [2056] v31 v30
   964  		//
   965  		// Note the SPanchored: this ensures that the scheduler won't
   966  		// move the MOVDaddr earlier than the vardef. With a variable
   967  		// "xyz" that has no pointers, however, if we start with
   968  		//
   969  		//    v66 = VarDef <mem> {t2} v65
   970  		//    v67 = LocalAddr <*T> {t2} v2 v66
   971  		//    v68 = Zero <mem> {T} [2056] v67 v66
   972  		//
   973  		// we might lower to
   974  		//
   975  		//    v66 = VarDef <mem> {t2} v65
   976  		//    v29 = MOVDaddr <*T> {t2} [2032] v2
   977  		//    v43 = LoweredZero <mem> v67 v29 v66
   978  		//    v68 = Zero [2056] v2 v43
   979  		//
   980  		// where that MOVDaddr can float around arbitrarily, meaning
   981  		// that we may see an upwards-exposed use to it before the
   982  		// VarDef.
   983  		//
   984  		// One avenue to restoring the check below would be to change
   985  		// the rewrite rules to something like
   986  		//
   987  		// (LocalAddr <t> {sym} base mem) && (t.Elem().HasPointers() || isMergeCandidate(t) => (MOVDaddr {sym} (SPanchored base mem))
   988  		//
   989  		// however that change will have to be carefully evaluated,
   990  		// since it would constrain the scheduler for _all_ LocalAddr
   991  		// ops for potential merge candidates, even if we don't
   992  		// actually succeed in any overlaps. This will be revisitged in
   993  		// a later CL if possible.
   994  		//
   995  		const checkLiveOnEntry = false
   996  		if checkLiveOnEntry && b == lv.f.Entry {
   997  			for j, v := range lv.vars {
   998  				if liveout.Get(int32(j)) {
   999  					lv.f.Fatalf("%v %L recorded as live on entry",
  1000  						lv.fn.Nname, v)
  1001  				}
  1002  			}
  1003  		}
  1004  	}
  1005  	if iidx != -1 {
  1006  		panic("iidx underflow")
  1007  	}
  1008  
  1009  	// Finish intervals construction.
  1010  	ivs := make([]Intervals, len(cs.cands))
  1011  	for i := range cs.cands {
  1012  		var err error
  1013  		ivs[i], err = ibuilders[i].Finish()
  1014  		if err != nil {
  1015  			cs.dumpFunc()
  1016  			base.FatalfAt(cs.cands[i].Pos(), "interval construct error for var %q in func %q (%d instrs): %v", cs.cands[i].Sym().Name, ir.FuncName(cs.fn), ninstr, err)
  1017  		}
  1018  	}
  1019  	cs.ivs = ivs
  1020  }
  1021  
  1022  func fmtFullPos(p src.XPos) string {
  1023  	var sb strings.Builder
  1024  	sep := ""
  1025  	base.Ctxt.AllPos(p, func(pos src.Pos) {
  1026  		sb.WriteString(sep)
  1027  		sep = "|"
  1028  		file := filepath.Base(pos.Filename())
  1029  		fmt.Fprintf(&sb, "%s:%d:%d", file, pos.Line(), pos.Col())
  1030  	})
  1031  	return sb.String()
  1032  }
  1033  
  1034  func dumpCand(c *ir.Name, i int) {
  1035  	fmt.Fprintf(os.Stderr, " %d: %s %q sz=%d hp=%v align=%d t=%v\n",
  1036  		i, fmtFullPos(c.Pos()), c.Sym().Name, c.Type().Size(),
  1037  		c.Type().HasPointers(), c.Type().Alignment(), c.Type())
  1038  }
  1039  
  1040  // for unit testing only.
  1041  func MakeMergeLocalsState(partition map[*ir.Name][]int, vars []*ir.Name) (*MergeLocalsState, error) {
  1042  	mls := &MergeLocalsState{partition: partition, vars: vars}
  1043  	if err := mls.check(); err != nil {
  1044  		return nil, err
  1045  	}
  1046  	return mls, nil
  1047  }
  1048  

View as plain text