Source file src/pkg/cmd/compile/internal/ssa/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/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			loc := LocalSlot{N: v.Aux.(GCNode), Type: v.Type, Off: v.AuxInt}
   157			if f.pass.debug > stackDebug {
   158				fmt.Printf("stackalloc %s to %s\n", v, loc)
   159			}
   160			f.setHome(v, loc)
   161		}
   162	
   163		// For each type, we keep track of all the stack slots we
   164		// have allocated for that type.
   165		// TODO: share slots among equivalent types. We would need to
   166		// only share among types with the same GC signature. See the
   167		// type.Equal calls below for where this matters.
   168		locations := map[*types.Type][]LocalSlot{}
   169	
   170		// Each time we assign a stack slot to a value v, we remember
   171		// the slot we used via an index into locations[v.Type].
   172		slots := s.slots
   173		if n := f.NumValues(); cap(slots) >= n {
   174			slots = slots[:n]
   175		} else {
   176			slots = make([]int, n)
   177			s.slots = slots
   178		}
   179		for i := range slots {
   180			slots[i] = -1
   181		}
   182	
   183		// Pick a stack slot for each value needing one.
   184		var used []bool
   185		if n := f.NumValues(); cap(s.used) >= n {
   186			used = s.used[:n]
   187		} else {
   188			used = make([]bool, n)
   189			s.used = used
   190		}
   191		for _, b := range f.Blocks {
   192			for _, v := range b.Values {
   193				if !s.values[v.ID].needSlot {
   194					s.nNotNeed++
   195					continue
   196				}
   197				if v.Op == OpArg {
   198					s.nArgSlot++
   199					continue // already picked
   200				}
   201	
   202				// If this is a named value, try to use the name as
   203				// the spill location.
   204				var name LocalSlot
   205				if v.Op == OpStoreReg {
   206					name = names[v.Args[0].ID]
   207				} else {
   208					name = names[v.ID]
   209				}
   210				if name.N != nil && v.Type.Compare(name.Type) == types.CMPeq {
   211					for _, id := range s.interfere[v.ID] {
   212						h := f.getHome(id)
   213						if h != nil && h.(LocalSlot).N == name.N && h.(LocalSlot).Off == name.Off {
   214							// A variable can interfere with itself.
   215							// It is rare, but it can happen.
   216							s.nSelfInterfere++
   217							goto noname
   218						}
   219					}
   220					if f.pass.debug > stackDebug {
   221						fmt.Printf("stackalloc %s to %s\n", v, name)
   222					}
   223					s.nNamedSlot++
   224					f.setHome(v, name)
   225					continue
   226				}
   227	
   228			noname:
   229				// Set of stack slots we could reuse.
   230				locs := locations[v.Type]
   231				// Mark all positions in locs used by interfering values.
   232				for i := 0; i < len(locs); i++ {
   233					used[i] = false
   234				}
   235				for _, xid := range s.interfere[v.ID] {
   236					slot := slots[xid]
   237					if slot >= 0 {
   238						used[slot] = true
   239					}
   240				}
   241				// Find an unused stack slot.
   242				var i int
   243				for i = 0; i < len(locs); i++ {
   244					if !used[i] {
   245						s.nReuse++
   246						break
   247					}
   248				}
   249				// If there is no unused stack slot, allocate a new one.
   250				if i == len(locs) {
   251					s.nAuto++
   252					locs = append(locs, LocalSlot{N: f.fe.Auto(v.Pos, v.Type), Type: v.Type, Off: 0})
   253					locations[v.Type] = locs
   254				}
   255				// Use the stack variable at that index for v.
   256				loc := locs[i]
   257				if f.pass.debug > stackDebug {
   258					fmt.Printf("stackalloc %s to %s\n", v, loc)
   259				}
   260				f.setHome(v, loc)
   261				slots[v.ID] = i
   262			}
   263		}
   264	}
   265	
   266	// computeLive computes a map from block ID to a list of
   267	// stack-slot-needing value IDs live at the end of that block.
   268	// TODO: this could be quadratic if lots of variables are live across lots of
   269	// basic blocks. Figure out a way to make this function (or, more precisely, the user
   270	// of this function) require only linear size & time.
   271	func (s *stackAllocState) computeLive(spillLive [][]ID) {
   272		s.live = make([][]ID, s.f.NumBlocks())
   273		var phis []*Value
   274		live := s.f.newSparseSet(s.f.NumValues())
   275		defer s.f.retSparseSet(live)
   276		t := s.f.newSparseSet(s.f.NumValues())
   277		defer s.f.retSparseSet(t)
   278	
   279		// Instead of iterating over f.Blocks, iterate over their postordering.
   280		// Liveness information flows backward, so starting at the end
   281		// increases the probability that we will stabilize quickly.
   282		po := s.f.postorder()
   283		for {
   284			changed := false
   285			for _, b := range po {
   286				// Start with known live values at the end of the block
   287				live.clear()
   288				live.addAll(s.live[b.ID])
   289	
   290				// Propagate backwards to the start of the block
   291				phis = phis[:0]
   292				for i := len(b.Values) - 1; i >= 0; i-- {
   293					v := b.Values[i]
   294					live.remove(v.ID)
   295					if v.Op == OpPhi {
   296						// Save phi for later.
   297						// Note: its args might need a stack slot even though
   298						// the phi itself doesn't. So don't use needSlot.
   299						if !v.Type.IsMemory() && !v.Type.IsVoid() {
   300							phis = append(phis, v)
   301						}
   302						continue
   303					}
   304					for _, a := range v.Args {
   305						if s.values[a.ID].needSlot {
   306							live.add(a.ID)
   307						}
   308					}
   309				}
   310	
   311				// for each predecessor of b, expand its list of live-at-end values
   312				// invariant: s contains the values live at the start of b (excluding phi inputs)
   313				for i, e := range b.Preds {
   314					p := e.b
   315					t.clear()
   316					t.addAll(s.live[p.ID])
   317					t.addAll(live.contents())
   318					t.addAll(spillLive[p.ID])
   319					for _, v := range phis {
   320						a := v.Args[i]
   321						if s.values[a.ID].needSlot {
   322							t.add(a.ID)
   323						}
   324						if spill := s.values[a.ID].spill; spill != nil {
   325							//TODO: remove?  Subsumed by SpillUse?
   326							t.add(spill.ID)
   327						}
   328					}
   329					if t.size() == len(s.live[p.ID]) {
   330						continue
   331					}
   332					// grow p's live set
   333					s.live[p.ID] = append(s.live[p.ID][:0], t.contents()...)
   334					changed = true
   335				}
   336			}
   337	
   338			if !changed {
   339				break
   340			}
   341		}
   342		if s.f.pass.debug > stackDebug {
   343			for _, b := range s.f.Blocks {
   344				fmt.Printf("stacklive %s %v\n", b, s.live[b.ID])
   345			}
   346		}
   347	}
   348	
   349	func (f *Func) getHome(vid ID) Location {
   350		if int(vid) >= len(f.RegAlloc) {
   351			return nil
   352		}
   353		return f.RegAlloc[vid]
   354	}
   355	
   356	func (f *Func) setHome(v *Value, loc Location) {
   357		for v.ID >= ID(len(f.RegAlloc)) {
   358			f.RegAlloc = append(f.RegAlloc, nil)
   359		}
   360		f.RegAlloc[v.ID] = loc
   361	}
   362	
   363	func (s *stackAllocState) buildInterferenceGraph() {
   364		f := s.f
   365		if n := f.NumValues(); cap(s.interfere) >= n {
   366			s.interfere = s.interfere[:n]
   367		} else {
   368			s.interfere = make([][]ID, n)
   369		}
   370		live := f.newSparseSet(f.NumValues())
   371		defer f.retSparseSet(live)
   372		for _, b := range f.Blocks {
   373			// Propagate liveness backwards to the start of the block.
   374			// Two values interfere if one is defined while the other is live.
   375			live.clear()
   376			live.addAll(s.live[b.ID])
   377			for i := len(b.Values) - 1; i >= 0; i-- {
   378				v := b.Values[i]
   379				if s.values[v.ID].needSlot {
   380					live.remove(v.ID)
   381					for _, id := range live.contents() {
   382						// Note: args can have different types and still interfere
   383						// (with each other or with other values). See issue 23522.
   384						if s.values[v.ID].typ.Compare(s.values[id].typ) == types.CMPeq || v.Op == OpArg || s.values[id].isArg {
   385							s.interfere[v.ID] = append(s.interfere[v.ID], id)
   386							s.interfere[id] = append(s.interfere[id], v.ID)
   387						}
   388					}
   389				}
   390				for _, a := range v.Args {
   391					if s.values[a.ID].needSlot {
   392						live.add(a.ID)
   393					}
   394				}
   395				if v.Op == OpArg && s.values[v.ID].needSlot {
   396					// OpArg is an input argument which is pre-spilled.
   397					// We add back v.ID here because we want this value
   398					// to appear live even before this point. Being live
   399					// all the way to the start of the entry block prevents other
   400					// values from being allocated to the same slot and clobbering
   401					// the input value before we have a chance to load it.
   402					live.add(v.ID)
   403				}
   404			}
   405		}
   406		if f.pass.debug > stackDebug {
   407			for vid, i := range s.interfere {
   408				if len(i) > 0 {
   409					fmt.Printf("v%d interferes with", vid)
   410					for _, x := range i {
   411						fmt.Printf(" v%d", x)
   412					}
   413					fmt.Println()
   414				}
   415			}
   416		}
   417	}
   418	

View as plain text