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 5package ssa 6 7import ( 8 "cmd/internal/src" 9 "fmt" 10) 11 12// Block represents a basic block in the control flow graph of a function. 13type 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. 88type 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 98func (e Edge) Block() *Block { 99 return e.b 100} 101func (e Edge) Index() int { 102 return e.i 103} 104 105// kind controls successors 106// ------------------------------------------ 107// Exit [return mem] [] 108// Plain [] [next] 109// If [boolean Value] [then, else] 110// Defer [mem] [nopanic, panic] (control opcode should be OpStaticCall to runtime.deferproc) 111type BlockKind int8 112 113// short form print 114func (b *Block) String() string { 115 return fmt.Sprintf("b%d", b.ID) 116} 117 118// long form print 119func (b *Block) LongString() string { 120 s := b.Kind.String() 121 if b.Aux != nil { 122 s += fmt.Sprintf(" {%s}", b.Aux) 123 } 124 if t := b.Kind.AuxIntType(); t != "" { 125 switch t { 126 case "Int8": 127 s += fmt.Sprintf(" [%v]", int8(b.AuxInt)) 128 case "UInt8": 129 s += fmt.Sprintf(" [%v]", uint8(b.AuxInt)) 130 default: 131 s += fmt.Sprintf(" [%v]", b.AuxInt) 132 } 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. 154func (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. 168func (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. 181func (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. 188func (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. 199func (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. 207func (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. 215func (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. 228func (b *Block) Reset(kind BlockKind) { 229 b.Kind = kind 230 b.ResetControls() 231 b.Aux = nil 232 b.AuxInt = 0 233} 234 235// AddEdgeTo adds an edge from block b to block c. Used during building of the 236// SSA graph; do not use on an already-completed SSA graph. 237func (b *Block) AddEdgeTo(c *Block) { 238 i := len(b.Succs) 239 j := len(c.Preds) 240 b.Succs = append(b.Succs, Edge{c, j}) 241 c.Preds = append(c.Preds, Edge{b, i}) 242 b.Func.invalidateCFG() 243} 244 245// removePred removes the ith input edge from b. 246// It is the responsibility of the caller to remove 247// the corresponding successor edge. 248func (b *Block) removePred(i int) { 249 n := len(b.Preds) - 1 250 if i != n { 251 e := b.Preds[n] 252 b.Preds[i] = e 253 // Update the other end of the edge we moved. 254 e.b.Succs[e.i].i = i 255 } 256 b.Preds[n] = Edge{} 257 b.Preds = b.Preds[:n] 258 b.Func.invalidateCFG() 259} 260 261// removeSucc removes the ith output edge from b. 262// It is the responsibility of the caller to remove 263// the corresponding predecessor edge. 264func (b *Block) removeSucc(i int) { 265 n := len(b.Succs) - 1 266 if i != n { 267 e := b.Succs[n] 268 b.Succs[i] = e 269 // Update the other end of the edge we moved. 270 e.b.Preds[e.i].i = i 271 } 272 b.Succs[n] = Edge{} 273 b.Succs = b.Succs[:n] 274 b.Func.invalidateCFG() 275} 276 277func (b *Block) swapSuccessors() { 278 if len(b.Succs) != 2 { 279 b.Fatalf("swapSuccessors with len(Succs)=%d", len(b.Succs)) 280 } 281 e0 := b.Succs[0] 282 e1 := b.Succs[1] 283 b.Succs[0] = e1 284 b.Succs[1] = e0 285 e0.b.Preds[e0.i].i = 1 286 e1.b.Preds[e1.i].i = 0 287 b.Likely *= -1 288} 289 290// LackingPos indicates whether b is a block whose position should be inherited 291// from its successors. This is true if all the values within it have unreliable positions 292// and if it is "plain", meaning that there is no control flow that is also very likely 293// to correspond to a well-understood source position. 294func (b *Block) LackingPos() bool { 295 // Non-plain predecessors are If or Defer, which both (1) have two successors, 296 // which might have different line numbers and (2) correspond to statements 297 // in the source code that have positions, so this case ought not occur anyway. 298 if b.Kind != BlockPlain { 299 return false 300 } 301 if b.Pos != src.NoXPos { 302 return false 303 } 304 for _, v := range b.Values { 305 if v.LackingPos() { 306 continue 307 } 308 return false 309 } 310 return true 311} 312 313func (b *Block) Logf(msg string, args ...interface{}) { b.Func.Logf(msg, args...) } 314func (b *Block) Log() bool { return b.Func.Log() } 315func (b *Block) Fatalf(msg string, args ...interface{}) { b.Func.Fatalf(msg, args...) } 316 317type BranchPrediction int8 318 319const ( 320 BranchUnlikely = BranchPrediction(-1) 321 BranchUnknown = BranchPrediction(0) 322 BranchLikely = BranchPrediction(+1) 323) 324