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 clear(b.Values[i:]) 268 b.Values = b.Values[:i] 269 } 270 271 // AddEdgeTo adds an edge from block b to block c. 272 func (b *Block) AddEdgeTo(c *Block) { 273 i := len(b.Succs) 274 j := len(c.Preds) 275 b.Succs = append(b.Succs, Edge{c, j}) 276 c.Preds = append(c.Preds, Edge{b, i}) 277 b.Func.invalidateCFG() 278 } 279 280 // removePred removes the ith input edge from b. 281 // It is the responsibility of the caller to remove 282 // the corresponding successor edge, and adjust any 283 // phi values by calling b.removePhiArg(v, i). 284 func (b *Block) removePred(i int) { 285 n := len(b.Preds) - 1 286 if i != n { 287 e := b.Preds[n] 288 b.Preds[i] = e 289 // Update the other end of the edge we moved. 290 e.b.Succs[e.i].i = i 291 } 292 b.Preds[n] = Edge{} 293 b.Preds = b.Preds[:n] 294 b.Func.invalidateCFG() 295 } 296 297 // removeSucc removes the ith output edge from b. 298 // It is the responsibility of the caller to remove 299 // the corresponding predecessor edge. 300 // Note that this potentially reorders successors of b, so it 301 // must be used very carefully. 302 func (b *Block) removeSucc(i int) { 303 n := len(b.Succs) - 1 304 if i != n { 305 e := b.Succs[n] 306 b.Succs[i] = e 307 // Update the other end of the edge we moved. 308 e.b.Preds[e.i].i = i 309 } 310 b.Succs[n] = Edge{} 311 b.Succs = b.Succs[:n] 312 b.Func.invalidateCFG() 313 } 314 315 func (b *Block) swapSuccessors() { 316 if len(b.Succs) != 2 { 317 b.Fatalf("swapSuccessors with len(Succs)=%d", len(b.Succs)) 318 } 319 e0 := b.Succs[0] 320 e1 := b.Succs[1] 321 b.Succs[0] = e1 322 b.Succs[1] = e0 323 e0.b.Preds[e0.i].i = 1 324 e1.b.Preds[e1.i].i = 0 325 b.Likely *= -1 326 } 327 328 // Swaps b.Succs[x] and b.Succs[y]. 329 func (b *Block) swapSuccessorsByIdx(x, y int) { 330 if x == y { 331 return 332 } 333 ex := b.Succs[x] 334 ey := b.Succs[y] 335 b.Succs[x] = ey 336 b.Succs[y] = ex 337 ex.b.Preds[ex.i].i = y 338 ey.b.Preds[ey.i].i = x 339 } 340 341 // removePhiArg removes the ith arg from phi. 342 // It must be called after calling b.removePred(i) to 343 // adjust the corresponding phi value of the block: 344 // 345 // b.removePred(i) 346 // for _, v := range b.Values { 347 // 348 // if v.Op != OpPhi { 349 // continue 350 // } 351 // b.removePhiArg(v, i) 352 // 353 // } 354 func (b *Block) removePhiArg(phi *Value, i int) { 355 n := len(b.Preds) 356 if numPhiArgs := len(phi.Args); numPhiArgs-1 != n { 357 b.Fatalf("inconsistent state for %v, num predecessors: %d, num phi args: %d", phi, n, numPhiArgs) 358 } 359 phi.Args[i].Uses-- 360 phi.Args[i] = phi.Args[n] 361 phi.Args[n] = nil 362 phi.Args = phi.Args[:n] 363 phielimValue(phi) 364 } 365 366 // uniquePred returns the predecessor of b, if there is exactly one. 367 // Returns nil otherwise. 368 func (b *Block) uniquePred() *Block { 369 if len(b.Preds) != 1 { 370 return nil 371 } 372 return b.Preds[0].b 373 } 374 375 // LackingPos indicates whether b is a block whose position should be inherited 376 // from its successors. This is true if all the values within it have unreliable positions 377 // and if it is "plain", meaning that there is no control flow that is also very likely 378 // to correspond to a well-understood source position. 379 func (b *Block) LackingPos() bool { 380 // Non-plain predecessors are If or Defer, which both (1) have two successors, 381 // which might have different line numbers and (2) correspond to statements 382 // in the source code that have positions, so this case ought not occur anyway. 383 if b.Kind != BlockPlain { 384 return false 385 } 386 if b.Pos != src.NoXPos { 387 return false 388 } 389 for _, v := range b.Values { 390 if v.LackingPos() { 391 continue 392 } 393 return false 394 } 395 return true 396 } 397 398 func (b *Block) AuxIntString() string { 399 switch b.Kind.AuxIntType() { 400 case "int8": 401 return fmt.Sprintf("%v", int8(b.AuxInt)) 402 case "uint8": 403 return fmt.Sprintf("%v", uint8(b.AuxInt)) 404 case "": // no aux int type 405 return "" 406 default: // type specified but not implemented - print as int64 407 return fmt.Sprintf("%v", b.AuxInt) 408 } 409 } 410 411 // likelyBranch reports whether block b is the likely branch of all of its predecessors. 412 func (b *Block) likelyBranch() bool { 413 if len(b.Preds) == 0 { 414 return false 415 } 416 for _, e := range b.Preds { 417 p := e.b 418 if len(p.Succs) == 1 || len(p.Succs) == 2 && (p.Likely == BranchLikely && p.Succs[0].b == b || 419 p.Likely == BranchUnlikely && p.Succs[1].b == b) { 420 continue 421 } 422 return false 423 } 424 return true 425 } 426 427 func (b *Block) Logf(msg string, args ...interface{}) { b.Func.Logf(msg, args...) } 428 func (b *Block) Log() bool { return b.Func.Log() } 429 func (b *Block) Fatalf(msg string, args ...interface{}) { b.Func.Fatalf(msg, args...) } 430 431 type BranchPrediction int8 432 433 const ( 434 BranchUnlikely = BranchPrediction(-1) 435 BranchUnknown = BranchPrediction(0) 436 BranchLikely = BranchPrediction(+1) 437 ) 438 439 type Hotness int8 // Could use negative numbers for specifically non-hot blocks, but don't, yet. 440 const ( 441 // These values are arranged in what seems to be order of increasing alignment importance. 442 // Currently only a few are relevant. Implicitly, they are all in a loop. 443 HotNotFlowIn Hotness = 1 << iota // This block is only reached by branches 444 HotInitial // In the block order, the first one for a given loop. Not necessarily topological header. 445 HotPgo // By PGO-based heuristics, this block occurs in a hot loop 446 447 HotNot = 0 448 HotInitialNotFlowIn = HotInitial | HotNotFlowIn // typically first block of a rotated loop, loop is entered with a branch (not to this block). No PGO 449 HotPgoInitial = HotPgo | HotInitial // special case; single block loop, initial block is header block has a flow-in entry, but PGO says it is hot 450 HotPgoInitialNotFLowIn = HotPgo | HotInitial | HotNotFlowIn // PGO says it is hot, and the loop is rotated so flow enters loop with a branch 451 ) 452