stackalloc.go

     1  // Copyright 2015 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  // TODO: live at start of block instead?
     6  
     7  package ssa
     8  
     9  import (
    10  	"cmd/compile/internal/ir"
    11  	"cmd/compile/internal/types"
    12  	"cmd/internal/src"
    13  	"fmt"
    14  )
    15  
    16  type stackAllocState struct {
    17  	f *Func
    18  
    19  	// live is the output of stackalloc.
    20  	// live[b.id] = live values at the end of block b.
    21  	live [][]ID
    22  
    23  	// The following slices are reused across multiple users
    24  	// of stackAllocState.
    25  	values    []stackValState
    26  	interfere [][]ID // interfere[v.id] = values that interfere with v.
    27  	names     []LocalSlot
    28  	slots     []int
    29  	used      []bool
    30  
    31  	nArgSlot, // Number of Values sourced to arg slot
    32  	nNotNeed, // Number of Values not needing a stack slot
    33  	nNamedSlot, // Number of Values using a named stack slot
    34  	nReuse, // Number of values reusing a stack slot
    35  	nAuto, // Number of autos allocated for stack slots.
    36  	nSelfInterfere int32 // Number of self-interferences
    37  }
    38  
    39  func newStackAllocState(f *Func) *stackAllocState {
    40  	s := f.Cache.stackAllocState
    41  	if s == nil {
    42  		return new(stackAllocState)
    43  	}
    44  	if s.f != nil {
    45  		f.fe.Fatalf(src.NoXPos, "newStackAllocState called without previous free")
    46  	}
    47  	return s
    48  }
    49  
    50  func putStackAllocState(s *stackAllocState) {
    51  	for i := range s.values {
    52  		s.values[i] = stackValState{}
    53  	}
    54  	for i := range s.interfere {
    55  		s.interfere[i] = nil
    56  	}
    57  	for i := range s.names {
    58  		s.names[i] = LocalSlot{}
    59  	}
    60  	for i := range s.slots {
    61  		s.slots[i] = 0
    62  	}
    63  	for i := range s.used {
    64  		s.used[i] = false
    65  	}
    66  	s.f.Cache.stackAllocState = s
    67  	s.f = nil
    68  	s.live = nil
    69  	s.nArgSlot, s.nNotNeed, s.nNamedSlot, s.nReuse, s.nAuto, s.nSelfInterfere = 0, 0, 0, 0, 0, 0
    70  }
    71  
    72  type stackValState struct {
    73  	typ      *types.Type
    74  	spill    *Value
    75  	needSlot bool
    76  	isArg    bool
    77  }
    78  
    79  // stackalloc allocates storage in the stack frame for
    80  // all Values that did not get a register.
    81  // Returns a map from block ID to the stack values live at the end of that block.
    82  func stackalloc(f *Func, spillLive [][]ID) [][]ID {
    83  	if f.pass.debug > stackDebug {
    84  		fmt.Println("before stackalloc")
    85  		fmt.Println(f.String())
    86  	}
    87  	s := newStackAllocState(f)
    88  	s.init(f, spillLive)
    89  	defer putStackAllocState(s)
    90  
    91  	s.stackalloc()
    92  	if f.pass.stats > 0 {
    93  		f.LogStat("stack_alloc_stats",
    94  			s.nArgSlot, "arg_slots", s.nNotNeed, "slot_not_needed",
    95  			s.nNamedSlot, "named_slots", s.nAuto, "auto_slots",
    96  			s.nReuse, "reused_slots", s.nSelfInterfere, "self_interfering")
    97  	}
    98  
    99  	return s.live
   100  }
   101  
   102  func (s *stackAllocState) init(f *Func, spillLive [][]ID) {
   103  	s.f = f
   104  
   105  	// Initialize value information.
   106  	if n := f.NumValues(); cap(s.values) >= n {
   107  		s.values = s.values[:n]
   108  	} else {
   109  		s.values = make([]stackValState, n)
   110  	}
   111  	for _, b := range f.Blocks {
   112  		for _, v := range b.Values {
   113  			s.values[v.ID].typ = v.Type
   114  			s.values[v.ID].needSlot = !v.Type.IsMemory() && !v.Type.IsVoid() && !v.Type.IsFlags() && f.getHome(v.ID) == nil && !v.rematerializeable() && !v.OnWasmStack
   115  			s.values[v.ID].isArg = hasAnyArgOp(v)
   116  			if f.pass.debug > stackDebug && s.values[v.ID].needSlot {
   117  				fmt.Printf("%s needs a stack slot\n", v)
   118  			}
   119  			if v.Op == OpStoreReg {
   120  				s.values[v.Args[0].ID].spill = v
   121  			}
   122  		}
   123  	}
   124  
   125  	// Compute liveness info for values needing a slot.
   126  	s.computeLive(spillLive)
   127  
   128  	// Build interference graph among values needing a slot.
   129  	s.buildInterferenceGraph()
   130  }
   131  
   132  func (s *stackAllocState) stackalloc() {
   133  	f := s.f
   134  
   135  	// Build map from values to their names, if any.
   136  	// A value may be associated with more than one name (e.g. after
   137  	// the assignment i=j). This step picks one name per value arbitrarily.
   138  	if n := f.NumValues(); cap(s.names) >= n {
   139  		s.names = s.names[:n]
   140  	} else {
   141  		s.names = make([]LocalSlot, n)
   142  	}
   143  	names := s.names
   144  	empty := LocalSlot{}
   145  	for _, name := range f.Names {
   146  		// Note: not "range f.NamedValues" above, because
   147  		// that would be nondeterministic.
   148  		for _, v := range f.NamedValues[*name] {
   149  			if v.Op == OpArgIntReg || v.Op == OpArgFloatReg {
   150  				aux := v.Aux.(*AuxNameOffset)
   151  				// Never let an arg be bound to a differently named thing.
   152  				if name.N != aux.Name || name.Off != aux.Offset {
   153  					if f.pass.debug > stackDebug {
   154  						fmt.Printf("stackalloc register arg %s skipping name %s\n", v, name)
   155  					}
   156  					continue
   157  				}
   158  			} else if name.N.Class == ir.PPARAM && v.Op != OpArg {
   159  				// PPARAM's only bind to OpArg
   160  				if f.pass.debug > stackDebug {
   161  					fmt.Printf("stackalloc PPARAM name %s skipping non-Arg %s\n", name, v)
   162  				}
   163  				continue
   164  			}
   165  
   166  			if names[v.ID] == empty {
   167  				if f.pass.debug > stackDebug {
   168  					fmt.Printf("stackalloc value %s to name %s\n", v, *name)
   169  				}
   170  				names[v.ID] = *name
   171  			}
   172  		}
   173  	}
   174  
   175  	// Allocate args to their assigned locations.
   176  	for _, v := range f.Entry.Values {
   177  		if !hasAnyArgOp(v) {
   178  			continue
   179  		}
   180  		if v.Aux == nil {
   181  			f.Fatalf("%s has nil Aux\n", v.LongString())
   182  		}
   183  		if v.Op == OpArg {
   184  			loc := LocalSlot{N: v.Aux.(*ir.Name), Type: v.Type, Off: v.AuxInt}
   185  			if f.pass.debug > stackDebug {
   186  				fmt.Printf("stackalloc OpArg %s to %s\n", v, loc)
   187  			}
   188  			f.setHome(v, loc)
   189  			continue
   190  		}
   191  		// You might think this below would be the right idea, but you would be wrong.
   192  		// It almost works; as of 105a6e9518 - 2021-04-23,
   193  		// GOSSAHASH=11011011001011111 == cmd/compile/internal/noder.(*noder).embedded
   194  		// is compiled incorrectly.  I believe the cause is one of those SSA-to-registers
   195  		// puzzles that the register allocator untangles; in the event that a register
   196  		// parameter does not end up bound to a name, "fixing" it is a bad idea.
   197  		//
   198  		//if f.DebugTest {
   199  		//	if v.Op == OpArgIntReg || v.Op == OpArgFloatReg {
   200  		//		aux := v.Aux.(*AuxNameOffset)
   201  		//		loc := LocalSlot{N: aux.Name, Type: v.Type, Off: aux.Offset}
   202  		//		if f.pass.debug > stackDebug {
   203  		//			fmt.Printf("stackalloc Op%s %s to %s\n", v.Op, v, loc)
   204  		//		}
   205  		//		names[v.ID] = loc
   206  		//		continue
   207  		//	}
   208  		//}
   209  
   210  	}
   211  
   212  	// For each type, we keep track of all the stack slots we
   213  	// have allocated for that type.
   214  	// TODO: share slots among equivalent types. We would need to
   215  	// only share among types with the same GC signature. See the
   216  	// type.Equal calls below for where this matters.
   217  	locations := map[*types.Type][]LocalSlot{}
   218  
   219  	// Each time we assign a stack slot to a value v, we remember
   220  	// the slot we used via an index into locations[v.Type].
   221  	slots := s.slots
   222  	if n := f.NumValues(); cap(slots) >= n {
   223  		slots = slots[:n]
   224  	} else {
   225  		slots = make([]int, n)
   226  		s.slots = slots
   227  	}
   228  	for i := range slots {
   229  		slots[i] = -1
   230  	}
   231  
   232  	// Pick a stack slot for each value needing one.
   233  	var used []bool
   234  	if n := f.NumValues(); cap(s.used) >= n {
   235  		used = s.used[:n]
   236  	} else {
   237  		used = make([]bool, n)
   238  		s.used = used
   239  	}
   240  	for _, b := range f.Blocks {
   241  		for _, v := range b.Values {
   242  			if !s.values[v.ID].needSlot {
   243  				s.nNotNeed++
   244  				continue
   245  			}
   246  			if hasAnyArgOp(v) {
   247  				s.nArgSlot++
   248  				continue // already picked
   249  			}
   250  
   251  			// If this is a named value, try to use the name as
   252  			// the spill location.
   253  			var name LocalSlot
   254  			if v.Op == OpStoreReg {
   255  				name = names[v.Args[0].ID]
   256  			} else {
   257  				name = names[v.ID]
   258  			}
   259  			if name.N != nil && v.Type.Compare(name.Type) == types.CMPeq {
   260  				for _, id := range s.interfere[v.ID] {
   261  					h := f.getHome(id)
   262  					if h != nil && h.(LocalSlot).N == name.N && h.(LocalSlot).Off == name.Off {
   263  						// A variable can interfere with itself.
   264  						// It is rare, but it can happen.
   265  						s.nSelfInterfere++
   266  						goto noname
   267  					}
   268  				}
   269  				if f.pass.debug > stackDebug {
   270  					fmt.Printf("stackalloc %s to %s\n", v, name)
   271  				}
   272  				s.nNamedSlot++
   273  				f.setHome(v, name)
   274  				continue
   275  			}
   276  
   277  		noname:
   278  			// Set of stack slots we could reuse.
   279  			locs := locations[v.Type]
   280  			// Mark all positions in locs used by interfering values.
   281  			for i := 0; i < len(locs); i++ {
   282  				used[i] = false
   283  			}
   284  			for _, xid := range s.interfere[v.ID] {
   285  				slot := slots[xid]
   286  				if slot >= 0 {
   287  					used[slot] = true
   288  				}
   289  			}
   290  			// Find an unused stack slot.
   291  			var i int
   292  			for i = 0; i < len(locs); i++ {
   293  				if !used[i] {
   294  					s.nReuse++
   295  					break
   296  				}
   297  			}
   298  			// If there is no unused stack slot, allocate a new one.
   299  			if i == len(locs) {
   300  				s.nAuto++
   301  				locs = append(locs, LocalSlot{N: f.fe.Auto(v.Pos, v.Type), Type: v.Type, Off: 0})
   302  				locations[v.Type] = locs
   303  			}
   304  			// Use the stack variable at that index for v.
   305  			loc := locs[i]
   306  			if f.pass.debug > stackDebug {
   307  				fmt.Printf("stackalloc %s to %s\n", v, loc)
   308  			}
   309  			f.setHome(v, loc)
   310  			slots[v.ID] = i
   311  		}
   312  	}
   313  }
   314  
   315  // computeLive computes a map from block ID to a list of
   316  // stack-slot-needing value IDs live at the end of that block.
   317  // TODO: this could be quadratic if lots of variables are live across lots of
   318  // basic blocks. Figure out a way to make this function (or, more precisely, the user
   319  // of this function) require only linear size & time.
   320  func (s *stackAllocState) computeLive(spillLive [][]ID) {
   321  	s.live = make([][]ID, s.f.NumBlocks())
   322  	var phis []*Value
   323  	live := s.f.newSparseSet(s.f.NumValues())
   324  	defer s.f.retSparseSet(live)
   325  	t := s.f.newSparseSet(s.f.NumValues())
   326  	defer s.f.retSparseSet(t)
   327  
   328  	// Instead of iterating over f.Blocks, iterate over their postordering.
   329  	// Liveness information flows backward, so starting at the end
   330  	// increases the probability that we will stabilize quickly.
   331  	po := s.f.postorder()
   332  	for {
   333  		changed := false
   334  		for _, b := range po {
   335  			// Start with known live values at the end of the block
   336  			live.clear()
   337  			live.addAll(s.live[b.ID])
   338  
   339  			// Propagate backwards to the start of the block
   340  			phis = phis[:0]
   341  			for i := len(b.Values) - 1; i >= 0; i-- {
   342  				v := b.Values[i]
   343  				live.remove(v.ID)
   344  				if v.Op == OpPhi {
   345  					// Save phi for later.
   346  					// Note: its args might need a stack slot even though
   347  					// the phi itself doesn't. So don't use needSlot.
   348  					if !v.Type.IsMemory() && !v.Type.IsVoid() {
   349  						phis = append(phis, v)
   350  					}
   351  					continue
   352  				}
   353  				for _, a := range v.Args {
   354  					if s.values[a.ID].needSlot {
   355  						live.add(a.ID)
   356  					}
   357  				}
   358  			}
   359  
   360  			// for each predecessor of b, expand its list of live-at-end values
   361  			// invariant: s contains the values live at the start of b (excluding phi inputs)
   362  			for i, e := range b.Preds {
   363  				p := e.b
   364  				t.clear()
   365  				t.addAll(s.live[p.ID])
   366  				t.addAll(live.contents())
   367  				t.addAll(spillLive[p.ID])
   368  				for _, v := range phis {
   369  					a := v.Args[i]
   370  					if s.values[a.ID].needSlot {
   371  						t.add(a.ID)
   372  					}
   373  					if spill := s.values[a.ID].spill; spill != nil {
   374  						//TODO: remove?  Subsumed by SpillUse?
   375  						t.add(spill.ID)
   376  					}
   377  				}
   378  				if t.size() == len(s.live[p.ID]) {
   379  					continue
   380  				}
   381  				// grow p's live set
   382  				s.live[p.ID] = append(s.live[p.ID][:0], t.contents()...)
   383  				changed = true
   384  			}
   385  		}
   386  
   387  		if !changed {
   388  			break
   389  		}
   390  	}
   391  	if s.f.pass.debug > stackDebug {
   392  		for _, b := range s.f.Blocks {
   393  			fmt.Printf("stacklive %s %v\n", b, s.live[b.ID])
   394  		}
   395  	}
   396  }
   397  
   398  func (f *Func) getHome(vid ID) Location {
   399  	if int(vid) >= len(f.RegAlloc) {
   400  		return nil
   401  	}
   402  	return f.RegAlloc[vid]
   403  }
   404  
   405  func (f *Func) setHome(v *Value, loc Location) {
   406  	for v.ID >= ID(len(f.RegAlloc)) {
   407  		f.RegAlloc = append(f.RegAlloc, nil)
   408  	}
   409  	f.RegAlloc[v.ID] = loc
   410  }
   411  
   412  func (s *stackAllocState) buildInterferenceGraph() {
   413  	f := s.f
   414  	if n := f.NumValues(); cap(s.interfere) >= n {
   415  		s.interfere = s.interfere[:n]
   416  	} else {
   417  		s.interfere = make([][]ID, n)
   418  	}
   419  	live := f.newSparseSet(f.NumValues())
   420  	defer f.retSparseSet(live)
   421  	for _, b := range f.Blocks {
   422  		// Propagate liveness backwards to the start of the block.
   423  		// Two values interfere if one is defined while the other is live.
   424  		live.clear()
   425  		live.addAll(s.live[b.ID])
   426  		for i := len(b.Values) - 1; i >= 0; i-- {
   427  			v := b.Values[i]
   428  			if s.values[v.ID].needSlot {
   429  				live.remove(v.ID)
   430  				for _, id := range live.contents() {
   431  					// Note: args can have different types and still interfere
   432  					// (with each other or with other values). See issue 23522.
   433  					if s.values[v.ID].typ.Compare(s.values[id].typ) == types.CMPeq || hasAnyArgOp(v) || s.values[id].isArg {
   434  						s.interfere[v.ID] = append(s.interfere[v.ID], id)
   435  						s.interfere[id] = append(s.interfere[id], v.ID)
   436  					}
   437  				}
   438  			}
   439  			for _, a := range v.Args {
   440  				if s.values[a.ID].needSlot {
   441  					live.add(a.ID)
   442  				}
   443  			}
   444  			if hasAnyArgOp(v) && s.values[v.ID].needSlot {
   445  				// OpArg is an input argument which is pre-spilled.
   446  				// We add back v.ID here because we want this value
   447  				// to appear live even before this point. Being live
   448  				// all the way to the start of the entry block prevents other
   449  				// values from being allocated to the same slot and clobbering
   450  				// the input value before we have a chance to load it.
   451  
   452  				// TODO(register args) this is apparently not wrong for register args -- is it necessary?
   453  				live.add(v.ID)
   454  			}
   455  		}
   456  	}
   457  	if f.pass.debug > stackDebug {
   458  		for vid, i := range s.interfere {
   459  			if len(i) > 0 {
   460  				fmt.Printf("v%d interferes with", vid)
   461  				for _, x := range i {
   462  					fmt.Printf(" v%d", x)
   463  				}
   464  				fmt.Println()
   465  			}
   466  		}
   467  	}
   468  }
   469  
   470  func hasAnyArgOp(v *Value) bool {
   471  	return v.Op == OpArg || v.Op == OpArgIntReg || v.Op == OpArgFloatReg
   472  }
   473
View as plain text