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  	"fmt"
    11  
    12  	"cmd/compile/internal/ir"
    13  	"cmd/compile/internal/ssa/ssaop"
    14  	"cmd/compile/internal/types"
    15  	"cmd/internal/src"
    16  )
    17  
    18  func NewStackAllocState(f *Func) *StackAllocState {
    19  	s := f.Cache.stackAllocState
    20  	if s == nil {
    21  		return new(StackAllocState)
    22  	}
    23  	if s.f != nil {
    24  		f.Fe.Fatalf(src.NoXPos, "newStackAllocState called without previous free")
    25  	}
    26  	return s
    27  }
    28  
    29  func PutStackAllocState(s *StackAllocState) {
    30  	clear(s.values)
    31  	clear(s.interfere)
    32  	clear(s.names)
    33  	s.f.Cache.stackAllocState = s
    34  	s.f = nil
    35  	s.Live = nil
    36  	s.NArgSlot, s.NNotNeed, s.NNamedSlot, s.NReuse, s.NAuto, s.NSelfInterfere = 0, 0, 0, 0, 0, 0
    37  }
    38  
    39  type StackAllocState struct {
    40  	f *Func
    41  
    42  	// Live is the output of stackalloc.
    43  	// Live[b.id] = Live values at the end of block b.
    44  	Live [][]ID
    45  
    46  	// The following slices are reused across multiple users
    47  	// of stackAllocState.
    48  	values    []stackValState
    49  	interfere [][]ID // interfere[v.id] = values that interfere with v.
    50  	names     []LocalSlot
    51  
    52  	NArgSlot, // Number of Values sourced to arg slot
    53  	NNotNeed, // Number of Values not needing a stack slot
    54  	NNamedSlot, // Number of Values using a named stack slot
    55  	NReuse, // Number of values reusing a stack slot
    56  	NAuto, // Number of autos allocated for stack slots.
    57  	NSelfInterfere int32 // Number of self-interferences
    58  }
    59  
    60  func hasAnyArgOp(v *Value) bool {
    61  	return v.Op == ssaop.OpArg || v.Op == ssaop.OpArgIntReg || v.Op == ssaop.OpArgFloatReg
    62  }
    63  
    64  type stackUseBlock struct {
    65  	b       *Block
    66  	liveout bool
    67  }
    68  
    69  type stackValState struct {
    70  	typ       *types.Type
    71  	spill     *Value
    72  	needSlot  bool
    73  	isArg     bool
    74  	defBlock  ID
    75  	useBlocks []stackUseBlock
    76  }
    77  
    78  // addUseBlock adds a block to the set of blocks that uses this value.
    79  // Note that we only loosely enforce the set property by checking the last
    80  // block that was appended to the list and duplicates may occur.
    81  // Because we add values block by block (barring phi-nodes), the number of duplicates is
    82  // small and we deduplicate as part of the liveness algorithm later anyway.
    83  func (sv *stackValState) addUseBlock(b *Block, liveout bool) {
    84  	entry := stackUseBlock{
    85  		b:       b,
    86  		liveout: liveout,
    87  	}
    88  	if sv.useBlocks == nil || sv.useBlocks[len(sv.useBlocks)-1] != entry {
    89  		sv.useBlocks = append(sv.useBlocks, stackUseBlock{
    90  			b:       b,
    91  			liveout: liveout,
    92  		})
    93  	}
    94  }
    95  
    96  func (s *StackAllocState) Init(f *Func, spillLive [][]ID) {
    97  	s.f = f
    98  
    99  	// Initialize value information.
   100  	if n := f.NumValues(); cap(s.values) >= n {
   101  		s.values = s.values[:n]
   102  	} else {
   103  		s.values = make([]stackValState, n)
   104  	}
   105  	for _, b := range f.Blocks {
   106  		for _, v := range b.Values {
   107  			s.values[v.ID].typ = v.Type
   108  			s.values[v.ID].needSlot = !v.Type.IsMemory() && !v.Type.IsVoid() && !v.Type.IsFlags() && f.GetHome(v.ID) == nil && !v.Rematerializeable() && !v.OnWasmStack
   109  			s.values[v.ID].isArg = hasAnyArgOp(v)
   110  			s.values[v.ID].defBlock = b.ID
   111  			if f.Pass.Debug > StackDebug && s.values[v.ID].needSlot {
   112  				fmt.Printf("%s needs a stack slot\n", v)
   113  			}
   114  			if v.Op == ssaop.OpStoreReg {
   115  				s.values[v.Args[0].ID].spill = v
   116  			}
   117  		}
   118  	}
   119  
   120  	// Compute liveness info for values needing a slot.
   121  	s.computeLive(spillLive)
   122  
   123  	// Build interference graph among values needing a slot.
   124  	s.buildInterferenceGraph()
   125  }
   126  
   127  func (s *StackAllocState) Stackalloc() {
   128  	f := s.f
   129  
   130  	// Build map from values to their names, if any.
   131  	// A value may be associated with more than one name (e.g. after
   132  	// the assignment i=j). This step picks one name per value arbitrarily.
   133  	if n := f.NumValues(); cap(s.names) >= n {
   134  		s.names = s.names[:n]
   135  	} else {
   136  		s.names = make([]LocalSlot, n)
   137  	}
   138  	names := s.names
   139  	empty := LocalSlot{}
   140  	for _, name := range f.Names {
   141  		// Note: not "range f.NamedValues" above, because
   142  		// that would be nondeterministic.
   143  		for _, v := range f.NamedValues[name] {
   144  			if v.Op == ssaop.OpArgIntReg || v.Op == ssaop.OpArgFloatReg {
   145  				aux := v.Aux.(*AuxNameOffset)
   146  				// Never let an arg be bound to a differently named thing.
   147  				if name.N != aux.Name || name.Off != aux.Offset {
   148  					if f.Pass.Debug > StackDebug {
   149  						fmt.Printf("stackalloc register arg %s skipping name %s\n", v, name)
   150  					}
   151  					continue
   152  				}
   153  			} else if name.N.Class == ir.PPARAM && v.Op != ssaop.OpArg {
   154  				// PPARAM's only bind to OpArg
   155  				if f.Pass.Debug > StackDebug {
   156  					fmt.Printf("stackalloc PPARAM name %s skipping non-Arg %s\n", name, v)
   157  				}
   158  				continue
   159  			}
   160  
   161  			if names[v.ID] == empty {
   162  				if f.Pass.Debug > StackDebug {
   163  					fmt.Printf("stackalloc value %s to name %s\n", v, name)
   164  				}
   165  				names[v.ID] = name
   166  			}
   167  		}
   168  	}
   169  
   170  	// Allocate args to their assigned locations.
   171  	for _, v := range f.Entry.Values {
   172  		if !hasAnyArgOp(v) {
   173  			continue
   174  		}
   175  		if v.Aux == nil {
   176  			f.Fatalf("%s has nil Aux\n", v.LongString())
   177  		}
   178  		if v.Op == ssaop.OpArg {
   179  			loc := LocalSlot{N: v.Aux.(*ir.Name), Type: v.Type, Off: v.AuxInt}
   180  			if f.Pass.Debug > StackDebug {
   181  				fmt.Printf("stackalloc OpArg %s to %s\n", v, loc)
   182  			}
   183  			f.SetHome(v, loc)
   184  			continue
   185  		}
   186  		// You might think this below would be the right idea, but you would be wrong.
   187  		// It almost works; as of 105a6e9518 - 2021-04-23,
   188  		// GOSSAHASH=11011011001011111 == cmd/compile/internal/noder.(*noder).embedded
   189  		// is compiled incorrectly.  I believe the cause is one of those SSA-to-registers
   190  		// puzzles that the register allocator untangles; in the event that a register
   191  		// parameter does not end up bound to a name, "fixing" it is a bad idea.
   192  		//
   193  		//if f.DebugTest {
   194  		//	if v.Op == OpArgIntReg || v.Op == OpArgFloatReg {
   195  		//		aux := v.Aux.(*AuxNameOffset)
   196  		//		loc := LocalSlot{N: aux.Name, Type: v.Type, Off: aux.Offset}
   197  		//		if f.pass.debug > stackDebug {
   198  		//			fmt.Printf("stackalloc Op%s %s to %s\n", v.Op, v, loc)
   199  		//		}
   200  		//		names[v.ID] = loc
   201  		//		continue
   202  		//	}
   203  		//}
   204  
   205  	}
   206  
   207  	// For each type, we keep track of all the stack slots we
   208  	// have allocated for that type. This map is keyed by
   209  	// strings returned by types.LinkString. This guarantees
   210  	// type equality, but also lets us match the same type represented
   211  	// by two different types.Type structures. See issue 65783.
   212  	locations := map[string][]LocalSlot{}
   213  
   214  	// Each time we assign a stack slot to a value v, we remember
   215  	// the slot we used via an index into locations[v.Type].
   216  	slots := f.Cache.AllocIntSlice(f.NumValues())
   217  	defer f.Cache.FreeIntSlice(slots)
   218  	for i := range slots {
   219  		slots[i] = -1
   220  	}
   221  
   222  	// Pick a stack slot for each value needing one.
   223  	used := f.Cache.AllocBoolSlice(f.NumValues())
   224  	defer f.Cache.FreeBoolSlice(used)
   225  	for _, b := range f.Blocks {
   226  		for _, v := range b.Values {
   227  			if !s.values[v.ID].needSlot {
   228  				s.NNotNeed++
   229  				continue
   230  			}
   231  			if hasAnyArgOp(v) {
   232  				s.NArgSlot++
   233  				continue // already picked
   234  			}
   235  
   236  			// If this is a named value, try to use the name as
   237  			// the spill location.
   238  			var name LocalSlot
   239  			if v.Op == ssaop.OpStoreReg {
   240  				name = names[v.Args[0].ID]
   241  			} else {
   242  				name = names[v.ID]
   243  			}
   244  			if name.N != nil && v.Type.Compare(name.Type) == types.CMPeq {
   245  				for _, id := range s.interfere[v.ID] {
   246  					h := f.GetHome(id)
   247  					if h != nil && h.(LocalSlot).N == name.N && h.(LocalSlot).Off == name.Off {
   248  						// A variable can interfere with itself.
   249  						// It is rare, but it can happen.
   250  						s.NSelfInterfere++
   251  						goto noname
   252  					}
   253  				}
   254  				if f.Pass.Debug > StackDebug {
   255  					fmt.Printf("stackalloc %s to %s\n", v, name)
   256  				}
   257  				s.NNamedSlot++
   258  				f.SetHome(v, name)
   259  				continue
   260  			}
   261  
   262  		noname:
   263  			// Set of stack slots we could reuse.
   264  			typeKey := v.Type.LinkString()
   265  			locs := locations[typeKey]
   266  			// Mark all positions in locs used by interfering values.
   267  			for i := 0; i < len(locs); i++ {
   268  				used[i] = false
   269  			}
   270  			for _, xid := range s.interfere[v.ID] {
   271  				slot := slots[xid]
   272  				if slot >= 0 {
   273  					used[slot] = true
   274  				}
   275  			}
   276  			// Find an unused stack slot.
   277  			var i int
   278  			for i = 0; i < len(locs); i++ {
   279  				if !used[i] {
   280  					s.NReuse++
   281  					break
   282  				}
   283  			}
   284  			// If there is no unused stack slot, allocate a new one.
   285  			if i == len(locs) {
   286  				s.NAuto++
   287  				locs = append(locs, LocalSlot{N: f.NewLocal(v.Pos, v.Type), Type: v.Type, Off: 0})
   288  				locations[typeKey] = locs
   289  			}
   290  			// Use the stack variable at that index for v.
   291  			loc := locs[i]
   292  			if f.Pass.Debug > StackDebug {
   293  				fmt.Printf("stackalloc %s to %s\n", v, loc)
   294  			}
   295  			f.SetHome(v, loc)
   296  			slots[v.ID] = i
   297  		}
   298  	}
   299  }
   300  
   301  // computeLive computes a map from block ID to a list of
   302  // stack-slot-needing value IDs live at the end of that block.
   303  func (s *StackAllocState) computeLive(spillLive [][]ID) {
   304  
   305  	// Because values using stack slots are few and far inbetween
   306  	// (compared to the set of all values), we use a path exploration
   307  	// algorithm to calculate liveness here.
   308  	f := s.f
   309  	for _, b := range f.Blocks {
   310  		for _, spillvid := range spillLive[b.ID] {
   311  			val := &s.values[spillvid]
   312  			val.addUseBlock(b, true)
   313  		}
   314  		for _, v := range b.Values {
   315  			for i, a := range v.Args {
   316  				val := &s.values[a.ID]
   317  				useBlock := b
   318  				forceLiveout := false
   319  				if v.Op == ssaop.OpPhi {
   320  					useBlock = b.Preds[i].B
   321  					forceLiveout = true
   322  					if spill := val.spill; spill != nil {
   323  						//TODO: remove?  Subsumed by SpillUse?
   324  						s.values[spill.ID].addUseBlock(useBlock, true)
   325  					}
   326  				}
   327  				if !val.needSlot {
   328  					continue
   329  				}
   330  				val.addUseBlock(useBlock, forceLiveout)
   331  			}
   332  		}
   333  	}
   334  
   335  	s.Live = make([][]ID, f.NumBlocks())
   336  	push := func(bid, vid ID) {
   337  		l := s.Live[bid]
   338  		if l == nil || l[len(l)-1] != vid {
   339  			l = append(l, vid)
   340  			s.Live[bid] = l
   341  		}
   342  	}
   343  	// TODO: If we can help along the interference graph by calculating livein sets,
   344  	// we can do so trivially by turning this sparse set into an array of arrays
   345  	// and checking the top for the current value instead of inclusion in the sparse set.
   346  	seen := f.NewSparseSet(f.NumBlocks())
   347  	defer f.RetSparseSet(seen)
   348  	// instead of pruning out duplicate blocks when we build the useblocks slices
   349  	// or when we add them to the queue, rely on the seen set to stop considering
   350  	// them. This is slightly faster than building the workqueues as sets
   351  	//
   352  	// However, this means that the queue can grow larger than the number of blocks,
   353  	// usually in very short functions. Returning a slice with values appended beyond the
   354  	// original allocation can corrupt the allocator state, so cap the queue and return
   355  	// the originally allocated slice regardless.
   356  	allocedBqueue := f.Cache.AllocBlockSlice(f.NumBlocks())
   357  	defer f.Cache.FreeBlockSlice(allocedBqueue)
   358  	bqueue := allocedBqueue[:0:f.NumBlocks()]
   359  
   360  	for vid, v := range s.values {
   361  		if !v.needSlot {
   362  			continue
   363  		}
   364  		seen.Clear()
   365  		bqueue = bqueue[:0]
   366  		for _, b := range v.useBlocks {
   367  			if b.liveout {
   368  				push(b.b.ID, ID(vid))
   369  			}
   370  			bqueue = append(bqueue, b.b)
   371  		}
   372  		for len(bqueue) > 0 {
   373  			work := bqueue[len(bqueue)-1]
   374  			bqueue = bqueue[:len(bqueue)-1]
   375  			if seen.Contains(work.ID) || work.ID == v.defBlock {
   376  				continue
   377  			}
   378  			seen.Add(work.ID)
   379  			for _, e := range work.Preds {
   380  				push(e.B.ID, ID(vid))
   381  				bqueue = append(bqueue, e.B)
   382  			}
   383  		}
   384  	}
   385  
   386  	if s.f.Pass.Debug > StackDebug {
   387  		for _, b := range s.f.Blocks {
   388  			fmt.Printf("stacklive %s %v\n", b, s.Live[b.ID])
   389  		}
   390  	}
   391  }
   392  
   393  func (f *Func) GetHome(vid ID) Location {
   394  	if int(vid) >= len(f.RegAlloc) {
   395  		return nil
   396  	}
   397  	return f.RegAlloc[vid]
   398  }
   399  
   400  func (f *Func) SetHome(v *Value, loc Location) {
   401  	for v.ID >= ID(len(f.RegAlloc)) {
   402  		f.RegAlloc = append(f.RegAlloc, nil)
   403  	}
   404  	f.RegAlloc[v.ID] = loc
   405  }
   406  
   407  func (s *StackAllocState) buildInterferenceGraph() {
   408  	f := s.f
   409  	if n := f.NumValues(); cap(s.interfere) >= n {
   410  		s.interfere = s.interfere[:n]
   411  	} else {
   412  		s.interfere = make([][]ID, n)
   413  	}
   414  	live := f.NewSparseSet(f.NumValues())
   415  	defer f.RetSparseSet(live)
   416  	for _, b := range f.Blocks {
   417  		// Propagate liveness backwards to the start of the block.
   418  		// Two values interfere if one is defined while the other is live.
   419  		live.Clear()
   420  		live.addAll(s.Live[b.ID])
   421  		for i := len(b.Values) - 1; i >= 0; i-- {
   422  			v := b.Values[i]
   423  			if s.values[v.ID].needSlot {
   424  				live.Remove(v.ID)
   425  				for _, id := range live.Contents() {
   426  					// Note: args can have different types and still interfere
   427  					// (with each other or with other values). See issue 23522.
   428  					if s.values[v.ID].typ.Compare(s.values[id].typ) == types.CMPeq || hasAnyArgOp(v) || s.values[id].isArg {
   429  						s.interfere[v.ID] = append(s.interfere[v.ID], id)
   430  						s.interfere[id] = append(s.interfere[id], v.ID)
   431  					}
   432  				}
   433  			}
   434  			for _, a := range v.Args {
   435  				if s.values[a.ID].needSlot {
   436  					live.Add(a.ID)
   437  				}
   438  			}
   439  			if hasAnyArgOp(v) && s.values[v.ID].needSlot {
   440  				// OpArg is an input argument which is pre-spilled.
   441  				// We add back v.ID here because we want this value
   442  				// to appear live even before this point. Being live
   443  				// all the way to the start of the entry block prevents other
   444  				// values from being allocated to the same slot and clobbering
   445  				// the input value before we have a chance to load it.
   446  
   447  				// TODO(register args) this is apparently not wrong for register args -- is it necessary?
   448  				live.Add(v.ID)
   449  			}
   450  		}
   451  	}
   452  	if f.Pass.Debug > StackDebug {
   453  		for vid, i := range s.interfere {
   454  			if len(i) > 0 {
   455  				fmt.Printf("v%d interferes with", vid)
   456  				for _, x := range i {
   457  					fmt.Printf(" v%d", x)
   458  				}
   459  				fmt.Println()
   460  			}
   461  		}
   462  	}
   463  }
   464
View as plain text