Black Lives Matter. Support the Equal Justice Initiative.

Source file src/cmd/compile/internal/ssa/stackalloc.go

Documentation: cmd/compile/internal/ssa

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

View as plain text