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