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 "fmt" 8 9 // Block represents a basic block in the control flow graph of a function. 10 type Block struct { 11 // A unique identifier for the block. The system will attempt to allocate 12 // these IDs densely, but no guarantees. 13 ID ID 14 15 // Line number for block's control operation 16 Line int32 17 18 // The kind of block this is. 19 Kind BlockKind 20 21 // Likely direction for branches. 22 // If BranchLikely, Succs[0] is the most likely branch taken. 23 // If BranchUnlikely, Succs[1] is the most likely branch taken. 24 // Ignored if len(Succs) < 2. 25 // Fatal if not BranchUnknown and len(Succs) > 2. 26 Likely BranchPrediction 27 28 // After flagalloc, records whether flags are live at the end of the block. 29 FlagsLiveAtEnd bool 30 31 // Subsequent blocks, if any. The number and order depend on the block kind. 32 Succs []Edge 33 34 // Inverse of successors. 35 // The order is significant to Phi nodes in the block. 36 // TODO: predecessors is a pain to maintain. Can we somehow order phi 37 // arguments by block id and have this field computed explicitly when needed? 38 Preds []Edge 39 40 // A value that determines how the block is exited. Its value depends on the kind 41 // of the block. For instance, a BlockIf has a boolean control value and BlockExit 42 // has a memory control value. 43 Control *Value 44 45 // Auxiliary info for the block. Its value depends on the Kind. 46 Aux interface{} 47 48 // The unordered set of Values that define the operation of this block. 49 // The list must include the control value, if any. (TODO: need this last condition?) 50 // After the scheduling pass, this list is ordered. 51 Values []*Value 52 53 // The containing function 54 Func *Func 55 56 // Storage for Succs, Preds, and Values 57 succstorage [2]Edge 58 predstorage [4]Edge 59 valstorage [9]*Value 60 } 61 62 // Edge represents a CFG edge. 63 // Example edges for b branching to either c or d. 64 // (c and d have other predecessors.) 65 // b.Succs = [{c,3}, {d,1}] 66 // c.Preds = [?, ?, ?, {b,0}] 67 // d.Preds = [?, {b,1}, ?] 68 // These indexes allow us to edit the CFG in constant time. 69 // In addition, it informs phi ops in degenerate cases like: 70 // b: 71 // if k then c else c 72 // c: 73 // v = Phi(x, y) 74 // Then the indexes tell you whether x is chosen from 75 // the if or else branch from b. 76 // b.Succs = [{c,0},{c,1}] 77 // c.Preds = [{b,0},{b,1}] 78 // means x is chosen if k is true. 79 type Edge struct { 80 // block edge goes to (in a Succs list) or from (in a Preds list) 81 b *Block 82 // index of reverse edge. Invariant: 83 // e := x.Succs[idx] 84 // e.b.Preds[e.i] = Edge{x,idx} 85 // and similarly for predecessors. 86 i int 87 } 88 89 func (e Edge) Block() *Block { 90 return e.b 91 } 92 func (e Edge) Index() int { 93 return e.i 94 } 95 96 // kind control successors 97 // ------------------------------------------ 98 // Exit return mem [] 99 // Plain nil [next] 100 // If a boolean Value [then, else] 101 // Defer mem [nopanic, panic] (control opcode should be OpDeferCall) 102 type BlockKind int8 103 104 // short form print 105 func (b *Block) String() string { 106 return fmt.Sprintf("b%d", b.ID) 107 } 108 109 // long form print 110 func (b *Block) LongString() string { 111 s := b.Kind.String() 112 if b.Aux != nil { 113 s += fmt.Sprintf(" %s", b.Aux) 114 } 115 if b.Control != nil { 116 s += fmt.Sprintf(" %s", b.Control) 117 } 118 if len(b.Succs) > 0 { 119 s += " ->" 120 for _, c := range b.Succs { 121 s += " " + c.b.String() 122 } 123 } 124 switch b.Likely { 125 case BranchUnlikely: 126 s += " (unlikely)" 127 case BranchLikely: 128 s += " (likely)" 129 } 130 return s 131 } 132 133 func (b *Block) SetControl(v *Value) { 134 if w := b.Control; w != nil { 135 w.Uses-- 136 } 137 b.Control = v 138 if v != nil { 139 v.Uses++ 140 } 141 } 142 143 // AddEdgeTo adds an edge from block b to block c. Used during building of the 144 // SSA graph; do not use on an already-completed SSA graph. 145 func (b *Block) AddEdgeTo(c *Block) { 146 i := len(b.Succs) 147 j := len(c.Preds) 148 b.Succs = append(b.Succs, Edge{c, j}) 149 c.Preds = append(c.Preds, Edge{b, i}) 150 b.Func.invalidateCFG() 151 } 152 153 // removePred removes the ith input edge from b. 154 // It is the responsibility of the caller to remove 155 // the corresponding successor edge. 156 func (b *Block) removePred(i int) { 157 n := len(b.Preds) - 1 158 if i != n { 159 e := b.Preds[n] 160 b.Preds[i] = e 161 // Update the other end of the edge we moved. 162 e.b.Succs[e.i].i = i 163 } 164 b.Preds[n] = Edge{} 165 b.Preds = b.Preds[:n] 166 b.Func.invalidateCFG() 167 } 168 169 // removeSucc removes the ith output edge from b. 170 // It is the responsibility of the caller to remove 171 // the corresponding predecessor edge. 172 func (b *Block) removeSucc(i int) { 173 n := len(b.Succs) - 1 174 if i != n { 175 e := b.Succs[n] 176 b.Succs[i] = e 177 // Update the other end of the edge we moved. 178 e.b.Preds[e.i].i = i 179 } 180 b.Succs[n] = Edge{} 181 b.Succs = b.Succs[:n] 182 b.Func.invalidateCFG() 183 } 184 185 func (b *Block) swapSuccessors() { 186 if len(b.Succs) != 2 { 187 b.Fatalf("swapSuccessors with len(Succs)=%d", len(b.Succs)) 188 } 189 e0 := b.Succs[0] 190 e1 := b.Succs[1] 191 b.Succs[0] = e1 192 b.Succs[1] = e0 193 e0.b.Preds[e0.i].i = 1 194 e1.b.Preds[e1.i].i = 0 195 b.Likely *= -1 196 } 197 198 func (b *Block) Logf(msg string, args ...interface{}) { b.Func.Logf(msg, args...) } 199 func (b *Block) Log() bool { return b.Func.Log() } 200 func (b *Block) Fatalf(msg string, args ...interface{}) { b.Func.Fatalf(msg, args...) } 201 202 type BranchPrediction int8 203 204 const ( 205 BranchUnlikely = BranchPrediction(-1) 206 BranchUnknown = BranchPrediction(0) 207 BranchLikely = BranchPrediction(+1) 208 ) 209
