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 value that determines how the block is exited. Its value depends on the kind 44 // of the block. For instance, a BlockIf has a boolean control value and BlockExit 45 // has a memory control value. 46 Control *Value 47 48 // Auxiliary info for the block. Its value depends on the Kind. 49 Aux interface{} 50 51 // The unordered set of Values that define the operation of this block. 52 // The list must include the control value, if any. (TODO: need this last condition?) 53 // After the scheduling pass, this list is ordered. 54 Values []*Value 55 56 // The containing function 57 Func *Func 58 59 // Storage for Succs, Preds, and Values 60 succstorage [2]Edge 61 predstorage [4]Edge 62 valstorage [9]*Value 63 } 64 65 // Edge represents a CFG edge. 66 // Example edges for b branching to either c or d. 67 // (c and d have other predecessors.) 68 // b.Succs = [{c,3}, {d,1}] 69 // c.Preds = [?, ?, ?, {b,0}] 70 // d.Preds = [?, {b,1}, ?] 71 // These indexes allow us to edit the CFG in constant time. 72 // In addition, it informs phi ops in degenerate cases like: 73 // b: 74 // if k then c else c 75 // c: 76 // v = Phi(x, y) 77 // Then the indexes tell you whether x is chosen from 78 // the if or else branch from b. 79 // b.Succs = [{c,0},{c,1}] 80 // c.Preds = [{b,0},{b,1}] 81 // means x is chosen if k is true. 82 type Edge struct { 83 // block edge goes to (in a Succs list) or from (in a Preds list) 84 b *Block 85 // index of reverse edge. Invariant: 86 // e := x.Succs[idx] 87 // e.b.Preds[e.i] = Edge{x,idx} 88 // and similarly for predecessors. 89 i int 90 } 91 92 func (e Edge) Block() *Block { 93 return e.b 94 } 95 func (e Edge) Index() int { 96 return e.i 97 } 98 99 // kind control successors 100 // ------------------------------------------ 101 // Exit return mem [] 102 // Plain nil [next] 103 // If a boolean Value [then, else] 104 // Defer mem [nopanic, panic] (control opcode should be OpStaticCall to runtime.deferproc) 105 type BlockKind int8 106 107 // short form print 108 func (b *Block) String() string { 109 return fmt.Sprintf("b%d", b.ID) 110 } 111 112 // long form print 113 func (b *Block) LongString() string { 114 s := b.Kind.String() 115 if b.Aux != nil { 116 s += fmt.Sprintf(" %s", b.Aux) 117 } 118 if b.Control != nil { 119 s += fmt.Sprintf(" %s", b.Control) 120 } 121 if len(b.Succs) > 0 { 122 s += " ->" 123 for _, c := range b.Succs { 124 s += " " + c.b.String() 125 } 126 } 127 switch b.Likely { 128 case BranchUnlikely: 129 s += " (unlikely)" 130 case BranchLikely: 131 s += " (likely)" 132 } 133 return s 134 } 135 136 func (b *Block) SetControl(v *Value) { 137 if w := b.Control; w != nil { 138 w.Uses-- 139 } 140 b.Control = v 141 if v != nil { 142 v.Uses++ 143 } 144 } 145 146 // AddEdgeTo adds an edge from block b to block c. Used during building of the 147 // SSA graph; do not use on an already-completed SSA graph. 148 func (b *Block) AddEdgeTo(c *Block) { 149 i := len(b.Succs) 150 j := len(c.Preds) 151 b.Succs = append(b.Succs, Edge{c, j}) 152 c.Preds = append(c.Preds, Edge{b, i}) 153 b.Func.invalidateCFG() 154 } 155 156 // removePred removes the ith input edge from b. 157 // It is the responsibility of the caller to remove 158 // the corresponding successor edge. 159 func (b *Block) removePred(i int) { 160 n := len(b.Preds) - 1 161 if i != n { 162 e := b.Preds[n] 163 b.Preds[i] = e 164 // Update the other end of the edge we moved. 165 e.b.Succs[e.i].i = i 166 } 167 b.Preds[n] = Edge{} 168 b.Preds = b.Preds[:n] 169 b.Func.invalidateCFG() 170 } 171 172 // removeSucc removes the ith output edge from b. 173 // It is the responsibility of the caller to remove 174 // the corresponding predecessor edge. 175 func (b *Block) removeSucc(i int) { 176 n := len(b.Succs) - 1 177 if i != n { 178 e := b.Succs[n] 179 b.Succs[i] = e 180 // Update the other end of the edge we moved. 181 e.b.Preds[e.i].i = i 182 } 183 b.Succs[n] = Edge{} 184 b.Succs = b.Succs[:n] 185 b.Func.invalidateCFG() 186 } 187 188 func (b *Block) swapSuccessors() { 189 if len(b.Succs) != 2 { 190 b.Fatalf("swapSuccessors with len(Succs)=%d", len(b.Succs)) 191 } 192 e0 := b.Succs[0] 193 e1 := b.Succs[1] 194 b.Succs[0] = e1 195 b.Succs[1] = e0 196 e0.b.Preds[e0.i].i = 1 197 e1.b.Preds[e1.i].i = 0 198 b.Likely *= -1 199 } 200 201 // LackingPos indicates whether b is a block whose position should be inherited 202 // from its successors. This is true if all the values within it have unreliable positions 203 // and if it is "plain", meaning that there is no control flow that is also very likely 204 // to correspond to a well-understood source position. 205 func (b *Block) LackingPos() bool { 206 // Non-plain predecessors are If or Defer, which both (1) have two successors, 207 // which might have different line numbers and (2) correspond to statements 208 // in the source code that have positions, so this case ought not occur anyway. 209 if b.Kind != BlockPlain { 210 return false 211 } 212 if b.Pos != src.NoXPos { 213 return false 214 } 215 for _, v := range b.Values { 216 if v.LackingPos() { 217 continue 218 } 219 return false 220 } 221 return true 222 } 223 224 func (b *Block) Logf(msg string, args ...interface{}) { b.Func.Logf(msg, args...) } 225 func (b *Block) Log() bool { return b.Func.Log() } 226 func (b *Block) Fatalf(msg string, args ...interface{}) { b.Func.Fatalf(msg, args...) } 227 228 type BranchPrediction int8 229 230 const ( 231 BranchUnlikely = BranchPrediction(-1) 232 BranchUnknown = BranchPrediction(0) 233 BranchLikely = BranchPrediction(+1) 234 ) 235