Source file src/cmd/compile/internal/ssa/block.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 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 // Subsequent blocks, if any. The number and order depend on the block kind. 35 Succs []Edge 36 37 // Inverse of successors. 38 // The order is significant to Phi nodes in the block. 39 // TODO: predecessors is a pain to maintain. Can we somehow order phi 40 // arguments by block id and have this field computed explicitly when needed? 41 Preds []Edge 42 43 // A list of values that determine how the block is exited. The number 44 // and type of control values depends on the Kind of the block. For 45 // instance, a BlockIf has a single boolean control value and BlockExit 46 // has a single memory control value. 47 // 48 // The ControlValues() method may be used to get a slice with the non-nil 49 // control values that can be ranged over. 50 // 51 // Controls[1] must be nil if Controls[0] is nil. 52 Controls [2]*Value 53 54 // Auxiliary info for the block. Its value depends on the Kind. 55 Aux interface{} 56 AuxInt int64 57 58 // The unordered set of Values that define the operation of this block. 59 // After the scheduling pass, this list is ordered. 60 Values []*Value 61 62 // The containing function 63 Func *Func 64 65 // Storage for Succs, Preds and Values. 66 succstorage [2]Edge 67 predstorage [4]Edge 68 valstorage [9]*Value 69 } 70 71 // Edge represents a CFG edge. 72 // Example edges for b branching to either c or d. 73 // (c and d have other predecessors.) 74 // b.Succs = [{c,3}, {d,1}] 75 // c.Preds = [?, ?, ?, {b,0}] 76 // d.Preds = [?, {b,1}, ?] 77 // These indexes allow us to edit the CFG in constant time. 78 // In addition, it informs phi ops in degenerate cases like: 79 // b: 80 // if k then c else c 81 // c: 82 // v = Phi(x, y) 83 // Then the indexes tell you whether x is chosen from 84 // the if or else branch from b. 85 // b.Succs = [{c,0},{c,1}] 86 // c.Preds = [{b,0},{b,1}] 87 // means x is chosen if k is true. 88 type Edge struct { 89 // block edge goes to (in a Succs list) or from (in a Preds list) 90 b *Block 91 // index of reverse edge. Invariant: 92 // e := x.Succs[idx] 93 // e.b.Preds[e.i] = Edge{x,idx} 94 // and similarly for predecessors. 95 i int 96 } 97 98 func (e Edge) Block() *Block { 99 return e.b 100 } 101 func (e Edge) Index() int { 102 return e.i 103 } 104 func (e Edge) String() string { 105 return fmt.Sprintf("{%v,%d}", e.b, e.i) 106 } 107 108 // kind controls successors 109 // ------------------------------------------ 110 // Exit [return mem] [] 111 // Plain [] [next] 112 // If [boolean Value] [then, else] 113 // Defer [mem] [nopanic, panic] (control opcode should be OpStaticCall to runtime.deferproc) 114 type BlockKind int8 115 116 // short form print 117 func (b *Block) String() string { 118 return fmt.Sprintf("b%d", b.ID) 119 } 120 121 // long form print 122 func (b *Block) LongString() string { 123 s := b.Kind.String() 124 if b.Aux != nil { 125 s += fmt.Sprintf(" {%s}", b.Aux) 126 } 127 if t := b.AuxIntString(); t != "" { 128 s += fmt.Sprintf(" [%s]", t) 129 } 130 for _, c := range b.ControlValues() { 131 s += fmt.Sprintf(" %s", c) 132 } 133 if len(b.Succs) > 0 { 134 s += " ->" 135 for _, c := range b.Succs { 136 s += " " + c.b.String() 137 } 138 } 139 switch b.Likely { 140 case BranchUnlikely: 141 s += " (unlikely)" 142 case BranchLikely: 143 s += " (likely)" 144 } 145 return s 146 } 147 148 // NumControls returns the number of non-nil control values the 149 // block has. 150 func (b *Block) NumControls() int { 151 if b.Controls[0] == nil { 152 return 0 153 } 154 if b.Controls[1] == nil { 155 return 1 156 } 157 return 2 158 } 159 160 // ControlValues returns a slice containing the non-nil control 161 // values of the block. The index of each control value will be 162 // the same as it is in the Controls property and can be used 163 // in ReplaceControl calls. 164 func (b *Block) ControlValues() []*Value { 165 if b.Controls[0] == nil { 166 return b.Controls[:0] 167 } 168 if b.Controls[1] == nil { 169 return b.Controls[:1] 170 } 171 return b.Controls[:2] 172 } 173 174 // SetControl removes all existing control values and then adds 175 // the control value provided. The number of control values after 176 // a call to SetControl will always be 1. 177 func (b *Block) SetControl(v *Value) { 178 b.ResetControls() 179 b.Controls[0] = v 180 v.Uses++ 181 } 182 183 // ResetControls sets the number of controls for the block to 0. 184 func (b *Block) ResetControls() { 185 if b.Controls[0] != nil { 186 b.Controls[0].Uses-- 187 } 188 if b.Controls[1] != nil { 189 b.Controls[1].Uses-- 190 } 191 b.Controls = [2]*Value{} // reset both controls to nil 192 } 193 194 // AddControl appends a control value to the existing list of control values. 195 func (b *Block) AddControl(v *Value) { 196 i := b.NumControls() 197 b.Controls[i] = v // panics if array is full 198 v.Uses++ 199 } 200 201 // ReplaceControl exchanges the existing control value at the index provided 202 // for the new value. The index must refer to a valid control value. 203 func (b *Block) ReplaceControl(i int, v *Value) { 204 b.Controls[i].Uses-- 205 b.Controls[i] = v 206 v.Uses++ 207 } 208 209 // CopyControls replaces the controls for this block with those from the 210 // provided block. The provided block is not modified. 211 func (b *Block) CopyControls(from *Block) { 212 if b == from { 213 return 214 } 215 b.ResetControls() 216 for _, c := range from.ControlValues() { 217 b.AddControl(c) 218 } 219 } 220 221 // Reset sets the block to the provided kind and clears all the blocks control 222 // and auxiliary values. Other properties of the block, such as its successors, 223 // predecessors and values are left unmodified. 224 func (b *Block) Reset(kind BlockKind) { 225 b.Kind = kind 226 b.ResetControls() 227 b.Aux = nil 228 b.AuxInt = 0 229 } 230 231 // resetWithControl resets b and adds control v. 232 // It is equivalent to b.Reset(kind); b.AddControl(v), 233 // except that it is one call instead of two and avoids a bounds check. 234 // It is intended for use by rewrite rules, where this matters. 235 func (b *Block) resetWithControl(kind BlockKind, v *Value) { 236 b.Kind = kind 237 b.ResetControls() 238 b.Aux = nil 239 b.AuxInt = 0 240 b.Controls[0] = v 241 v.Uses++ 242 } 243 244 // resetWithControl2 resets b and adds controls v and w. 245 // It is equivalent to b.Reset(kind); b.AddControl(v); b.AddControl(w), 246 // except that it is one call instead of three and avoids two bounds checks. 247 // It is intended for use by rewrite rules, where this matters. 248 func (b *Block) resetWithControl2(kind BlockKind, v, w *Value) { 249 b.Kind = kind 250 b.ResetControls() 251 b.Aux = nil 252 b.AuxInt = 0 253 b.Controls[0] = v 254 b.Controls[1] = w 255 v.Uses++ 256 w.Uses++ 257 } 258 259 // truncateValues truncates b.Values at the ith element, zeroing subsequent elements. 260 // The values in b.Values after i must already have had their args reset, 261 // to maintain correct value uses counts. 262 func (b *Block) truncateValues(i int) { 263 tail := b.Values[i:] 264 for j := range tail { 265 tail[j] = nil 266 } 267 b.Values = b.Values[:i] 268 } 269 270 // AddEdgeTo adds an edge from block b to block c. Used during building of the 271 // SSA graph; do not use on an already-completed SSA graph. 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. 283 func (b *Block) removePred(i int) { 284 n := len(b.Preds) - 1 285 if i != n { 286 e := b.Preds[n] 287 b.Preds[i] = e 288 // Update the other end of the edge we moved. 289 e.b.Succs[e.i].i = i 290 } 291 b.Preds[n] = Edge{} 292 b.Preds = b.Preds[:n] 293 b.Func.invalidateCFG() 294 } 295 296 // removeSucc removes the ith output edge from b. 297 // It is the responsibility of the caller to remove 298 // the corresponding predecessor edge. 299 func (b *Block) removeSucc(i int) { 300 n := len(b.Succs) - 1 301 if i != n { 302 e := b.Succs[n] 303 b.Succs[i] = e 304 // Update the other end of the edge we moved. 305 e.b.Preds[e.i].i = i 306 } 307 b.Succs[n] = Edge{} 308 b.Succs = b.Succs[:n] 309 b.Func.invalidateCFG() 310 } 311 312 func (b *Block) swapSuccessors() { 313 if len(b.Succs) != 2 { 314 b.Fatalf("swapSuccessors with len(Succs)=%d", len(b.Succs)) 315 } 316 e0 := b.Succs[0] 317 e1 := b.Succs[1] 318 b.Succs[0] = e1 319 b.Succs[1] = e0 320 e0.b.Preds[e0.i].i = 1 321 e1.b.Preds[e1.i].i = 0 322 b.Likely *= -1 323 } 324 325 // LackingPos indicates whether b is a block whose position should be inherited 326 // from its successors. This is true if all the values within it have unreliable positions 327 // and if it is "plain", meaning that there is no control flow that is also very likely 328 // to correspond to a well-understood source position. 329 func (b *Block) LackingPos() bool { 330 // Non-plain predecessors are If or Defer, which both (1) have two successors, 331 // which might have different line numbers and (2) correspond to statements 332 // in the source code that have positions, so this case ought not occur anyway. 333 if b.Kind != BlockPlain { 334 return false 335 } 336 if b.Pos != src.NoXPos { 337 return false 338 } 339 for _, v := range b.Values { 340 if v.LackingPos() { 341 continue 342 } 343 return false 344 } 345 return true 346 } 347 348 func (b *Block) AuxIntString() string { 349 switch b.Kind.AuxIntType() { 350 case "int8": 351 return fmt.Sprintf("%v", int8(b.AuxInt)) 352 case "uint8": 353 return fmt.Sprintf("%v", uint8(b.AuxInt)) 354 default: // type specified but not implemented - print as int64 355 return fmt.Sprintf("%v", b.AuxInt) 356 case "": // no aux int type 357 return "" 358 } 359 } 360 361 func (b *Block) Logf(msg string, args ...interface{}) { b.Func.Logf(msg, args...) } 362 func (b *Block) Log() bool { return b.Func.Log() } 363 func (b *Block) Fatalf(msg string, args ...interface{}) { b.Func.Fatalf(msg, args...) } 364 365 type BranchPrediction int8 366 367 const ( 368 BranchUnlikely = BranchPrediction(-1) 369 BranchUnknown = BranchPrediction(0) 370 BranchLikely = BranchPrediction(+1) 371 ) 372