Source file src/cmd/compile/internal/ssa/block.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 package ssa 6 7 import ( 8 "cmd/internal/src" 9 "fmt" 10 ) 11 12 // Block represents a basic block in the control flow graph of a function. 13 type Block struct { 14 // A unique identifier for the block. The system will attempt to allocate 15 // these IDs densely, but no guarantees. 16 ID ID 17 18 // Source position for block's control operation 19 Pos src.XPos 20 21 // The kind of block this is. 22 Kind BlockKind 23 24 // Likely direction for branches. 25 // If BranchLikely, Succs[0] is the most likely branch taken. 26 // If BranchUnlikely, Succs[1] is the most likely branch taken. 27 // Ignored if len(Succs) < 2. 28 // Fatal if not BranchUnknown and len(Succs) > 2. 29 Likely BranchPrediction 30 31 // After flagalloc, records whether flags are live at the end of the block. 32 FlagsLiveAtEnd bool 33 34 // A block that would be good to align (according to the optimizer's guesses) 35 Hotness Hotness 36 37 // Subsequent blocks, if any. The number and order depend on the block kind. 38 Succs []Edge 39 40 // Inverse of successors. 41 // The order is significant to Phi nodes in the block. 42 // TODO: predecessors is a pain to maintain. Can we somehow order phi 43 // arguments by block id and have this field computed explicitly when needed? 44 Preds []Edge 45 46 // A list of values that determine how the block is exited. The number 47 // and type of control values depends on the Kind of the block. For 48 // instance, a BlockIf has a single boolean control value and BlockExit 49 // has a single memory control value. 50 // 51 // The ControlValues() method may be used to get a slice with the non-nil 52 // control values that can be ranged over. 53 // 54 // Controls[1] must be nil if Controls[0] is nil. 55 Controls [2]*Value 56 57 // Auxiliary info for the block. Its value depends on the Kind. 58 Aux Aux 59 AuxInt int64 60 61 // The unordered set of Values that define the operation of this block. 62 // After the scheduling pass, this list is ordered. 63 Values []*Value 64 65 // The containing function 66 Func *Func 67 68 // Storage for Succs, Preds and Values. 69 succstorage [2]Edge 70 predstorage [4]Edge 71 valstorage [9]*Value 72 } 73 74 // Edge represents a CFG edge. 75 // Example edges for b branching to either c or d. 76 // (c and d have other predecessors.) 77 // 78 // b.Succs = [{c,3}, {d,1}] 79 // c.Preds = [?, ?, ?, {b,0}] 80 // d.Preds = [?, {b,1}, ?] 81 // 82 // These indexes allow us to edit the CFG in constant time. 83 // In addition, it informs phi ops in degenerate cases like: 84 // 85 // b: 86 // if k then c else c 87 // c: 88 // v = Phi(x, y) 89 // 90 // Then the indexes tell you whether x is chosen from 91 // the if or else branch from b. 92 // 93 // b.Succs = [{c,0},{c,1}] 94 // c.Preds = [{b,0},{b,1}] 95 // 96 // means x is chosen if k is true. 97 type Edge struct { 98 // block edge goes to (in a Succs list) or from (in a Preds list) 99 b *Block 100 // index of reverse edge. Invariant: 101 // e := x.Succs[idx] 102 // e.b.Preds[e.i] = Edge{x,idx} 103 // and similarly for predecessors. 104 i int 105 } 106 107 func (e Edge) Block() *Block { 108 return e.b 109 } 110 func (e Edge) Index() int { 111 return e.i 112 } 113 func (e Edge) String() string { 114 return fmt.Sprintf("{%v,%d}", e.b, e.i) 115 } 116 117 // BlockKind is the kind of SSA block. 118 type BlockKind uint8 119 120 // short form print 121 func (b *Block) String() string { 122 return fmt.Sprintf("b%d", b.ID) 123 } 124 125 // long form print 126 func (b *Block) LongString() string { 127 s := b.Kind.String() 128 if b.Aux != nil { 129 s += fmt.Sprintf(" {%s}", b.Aux) 130 } 131 if t := b.AuxIntString(); t != "" { 132 s += fmt.Sprintf(" [%s]", t) 133 } 134 for _, c := range b.ControlValues() { 135 s += fmt.Sprintf(" %s", c) 136 } 137 if len(b.Succs) > 0 { 138 s += " ->" 139 for _, c := range b.Succs { 140 s += " " + c.b.String() 141 } 142 } 143 switch b.Likely { 144 case BranchUnlikely: 145 s += " (unlikely)" 146 case BranchLikely: 147 s += " (likely)" 148 } 149 return s 150 } 151 152 // NumControls returns the number of non-nil control values the 153 // block has. 154 func (b *Block) NumControls() int { 155 if b.Controls[0] == nil { 156 return 0 157 } 158 if b.Controls[1] == nil { 159 return 1 160 } 161 return 2 162 } 163 164 // ControlValues returns a slice containing the non-nil control 165 // values of the block. The index of each control value will be 166 // the same as it is in the Controls property and can be used 167 // in ReplaceControl calls. 168 func (b *Block) ControlValues() []*Value { 169 if b.Controls[0] == nil { 170 return b.Controls[:0] 171 } 172 if b.Controls[1] == nil { 173 return b.Controls[:1] 174 } 175 return b.Controls[:2] 176 } 177 178 // SetControl removes all existing control values and then adds 179 // the control value provided. The number of control values after 180 // a call to SetControl will always be 1. 181 func (b *Block) SetControl(v *Value) { 182 b.ResetControls() 183 b.Controls[0] = v 184 v.Uses++ 185 } 186 187 // ResetControls sets the number of controls for the block to 0. 188 func (b *Block) ResetControls() { 189 if b.Controls[0] != nil { 190 b.Controls[0].Uses-- 191 } 192 if b.Controls[1] != nil { 193 b.Controls[1].Uses-- 194 } 195 b.Controls = [2]*Value{} // reset both controls to nil 196 } 197 198 // AddControl appends a control value to the existing list of control values. 199 func (b *Block) AddControl(v *Value) { 200 i := b.NumControls() 201 b.Controls[i] = v // panics if array is full 202 v.Uses++ 203 } 204 205 // ReplaceControl exchanges the existing control value at the index provided 206 // for the new value. The index must refer to a valid control value. 207 func (b *Block) ReplaceControl(i int, v *Value) { 208 b.Controls[i].Uses-- 209 b.Controls[i] = v 210 v.Uses++ 211 } 212 213 // CopyControls replaces the controls for this block with those from the 214 // provided block. The provided block is not modified. 215 func (b *Block) CopyControls(from *Block) { 216 if b == from { 217 return 218 } 219 b.ResetControls() 220 for _, c := range from.ControlValues() { 221 b.AddControl(c) 222 } 223 } 224 225 // Reset sets the block to the provided kind and clears all the blocks control 226 // and auxiliary values. Other properties of the block, such as its successors, 227 // predecessors and values are left unmodified. 228 func (b *Block) Reset(kind BlockKind) { 229 b.Kind = kind 230 b.ResetControls() 231 b.Aux = nil 232 b.AuxInt = 0 233 } 234 235 // resetWithControl resets b and adds control v. 236 // It is equivalent to b.Reset(kind); b.AddControl(v), 237 // except that it is one call instead of two and avoids a bounds check. 238 // It is intended for use by rewrite rules, where this matters. 239 func (b *Block) resetWithControl(kind BlockKind, v *Value) { 240 b.Kind = kind 241 b.ResetControls() 242 b.Aux = nil 243 b.AuxInt = 0 244 b.Controls[0] = v 245 v.Uses++ 246 } 247 248 // resetWithControl2 resets b and adds controls v and w. 249 // It is equivalent to b.Reset(kind); b.AddControl(v); b.AddControl(w), 250 // except that it is one call instead of three and avoids two bounds checks. 251 // It is intended for use by rewrite rules, where this matters. 252 func (b *Block) resetWithControl2(kind BlockKind, v, w *Value) { 253 b.Kind = kind 254 b.ResetControls() 255 b.Aux = nil 256 b.AuxInt = 0 257 b.Controls[0] = v 258 b.Controls[1] = w 259 v.Uses++ 260 w.Uses++ 261 } 262 263 // truncateValues truncates b.Values at the ith element, zeroing subsequent elements. 264 // The values in b.Values after i must already have had their args reset, 265 // to maintain correct value uses counts. 266 func (b *Block) truncateValues(i int) { 267 tail := b.Values[i:] 268 for j := range tail { 269 tail[j] = nil 270 } 271 b.Values = b.Values[:i] 272 } 273 274 // AddEdgeTo adds an edge from block b to block c. 275 func (b *Block) AddEdgeTo(c *Block) { 276 i := len(b.Succs) 277 j := len(c.Preds) 278 b.Succs = append(b.Succs, Edge{c, j}) 279 c.Preds = append(c.Preds, Edge{b, i}) 280 b.Func.invalidateCFG() 281 } 282 283 // removePred removes the ith input edge from b. 284 // It is the responsibility of the caller to remove 285 // the corresponding successor edge, and adjust any 286 // phi values by calling b.removePhiArg(v, i). 287 func (b *Block) removePred(i int) { 288 n := len(b.Preds) - 1 289 if i != n { 290 e := b.Preds[n] 291 b.Preds[i] = e 292 // Update the other end of the edge we moved. 293 e.b.Succs[e.i].i = i 294 } 295 b.Preds[n] = Edge{} 296 b.Preds = b.Preds[:n] 297 b.Func.invalidateCFG() 298 } 299 300 // removeSucc removes the ith output edge from b. 301 // It is the responsibility of the caller to remove 302 // the corresponding predecessor edge. 303 // Note that this potentially reorders successors of b, so it 304 // must be used very carefully. 305 func (b *Block) removeSucc(i int) { 306 n := len(b.Succs) - 1 307 if i != n { 308 e := b.Succs[n] 309 b.Succs[i] = e 310 // Update the other end of the edge we moved. 311 e.b.Preds[e.i].i = i 312 } 313 b.Succs[n] = Edge{} 314 b.Succs = b.Succs[:n] 315 b.Func.invalidateCFG() 316 } 317 318 func (b *Block) swapSuccessors() { 319 if len(b.Succs) != 2 { 320 b.Fatalf("swapSuccessors with len(Succs)=%d", len(b.Succs)) 321 } 322 e0 := b.Succs[0] 323 e1 := b.Succs[1] 324 b.Succs[0] = e1 325 b.Succs[1] = e0 326 e0.b.Preds[e0.i].i = 1 327 e1.b.Preds[e1.i].i = 0 328 b.Likely *= -1 329 } 330 331 // Swaps b.Succs[x] and b.Succs[y]. 332 func (b *Block) swapSuccessorsByIdx(x, y int) { 333 if x == y { 334 return 335 } 336 ex := b.Succs[x] 337 ey := b.Succs[y] 338 b.Succs[x] = ey 339 b.Succs[y] = ex 340 ex.b.Preds[ex.i].i = y 341 ey.b.Preds[ey.i].i = x 342 } 343 344 // removePhiArg removes the ith arg from phi. 345 // It must be called after calling b.removePred(i) to 346 // adjust the corresponding phi value of the block: 347 // 348 // b.removePred(i) 349 // for _, v := range b.Values { 350 // 351 // if v.Op != OpPhi { 352 // continue 353 // } 354 // b.removePhiArg(v, i) 355 // 356 // } 357 func (b *Block) removePhiArg(phi *Value, i int) { 358 n := len(b.Preds) 359 if numPhiArgs := len(phi.Args); numPhiArgs-1 != n { 360 b.Fatalf("inconsistent state for %v, num predecessors: %d, num phi args: %d", phi, n, numPhiArgs) 361 } 362 phi.Args[i].Uses-- 363 phi.Args[i] = phi.Args[n] 364 phi.Args[n] = nil 365 phi.Args = phi.Args[:n] 366 phielimValue(phi) 367 } 368 369 // LackingPos indicates whether b is a block whose position should be inherited 370 // from its successors. This is true if all the values within it have unreliable positions 371 // and if it is "plain", meaning that there is no control flow that is also very likely 372 // to correspond to a well-understood source position. 373 func (b *Block) LackingPos() bool { 374 // Non-plain predecessors are If or Defer, which both (1) have two successors, 375 // which might have different line numbers and (2) correspond to statements 376 // in the source code that have positions, so this case ought not occur anyway. 377 if b.Kind != BlockPlain { 378 return false 379 } 380 if b.Pos != src.NoXPos { 381 return false 382 } 383 for _, v := range b.Values { 384 if v.LackingPos() { 385 continue 386 } 387 return false 388 } 389 return true 390 } 391 392 func (b *Block) AuxIntString() string { 393 switch b.Kind.AuxIntType() { 394 case "int8": 395 return fmt.Sprintf("%v", int8(b.AuxInt)) 396 case "uint8": 397 return fmt.Sprintf("%v", uint8(b.AuxInt)) 398 case "": // no aux int type 399 return "" 400 default: // type specified but not implemented - print as int64 401 return fmt.Sprintf("%v", b.AuxInt) 402 } 403 } 404 405 // likelyBranch reports whether block b is the likely branch of all of its predecessors. 406 func (b *Block) likelyBranch() bool { 407 if len(b.Preds) == 0 { 408 return false 409 } 410 for _, e := range b.Preds { 411 p := e.b 412 if len(p.Succs) == 1 || len(p.Succs) == 2 && (p.Likely == BranchLikely && p.Succs[0].b == b || 413 p.Likely == BranchUnlikely && p.Succs[1].b == b) { 414 continue 415 } 416 return false 417 } 418 return true 419 } 420 421 func (b *Block) Logf(msg string, args ...interface{}) { b.Func.Logf(msg, args...) } 422 func (b *Block) Log() bool { return b.Func.Log() } 423 func (b *Block) Fatalf(msg string, args ...interface{}) { b.Func.Fatalf(msg, args...) } 424 425 type BranchPrediction int8 426 427 const ( 428 BranchUnlikely = BranchPrediction(-1) 429 BranchUnknown = BranchPrediction(0) 430 BranchLikely = BranchPrediction(+1) 431 ) 432 433 type Hotness int8 // Could use negative numbers for specifically non-hot blocks, but don't, yet. 434 const ( 435 // These values are arranged in what seems to be order of increasing alignment importance. 436 // Currently only a few are relevant. Implicitly, they are all in a loop. 437 HotNotFlowIn Hotness = 1 << iota // This block is only reached by branches 438 HotInitial // In the block order, the first one for a given loop. Not necessarily topological header. 439 HotPgo // By PGO-based heuristics, this block occurs in a hot loop 440 441 HotNot = 0 442 HotInitialNotFlowIn = HotInitial | HotNotFlowIn // typically first block of a rotated loop, loop is entered with a branch (not to this block). No PGO 443 HotPgoInitial = HotPgo | HotInitial // special case; single block loop, initial block is header block has a flow-in entry, but PGO says it is hot 444 HotPgoInitialNotFLowIn = HotPgo | HotInitial | HotNotFlowIn // PGO says it is hot, and the loop is rotated so flow enters loop with a branch 445 ) 446