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 "fmt" 9 "strings" 10 ) 11 12 type SparseTreeNode struct { 13 child *Block 14 sibling *Block 15 parent *Block 16 17 // Every block has 6 numbers associated with it: 18 // entry-1, entry, entry+1, exit-1, and exit, exit+1. 19 // entry and exit are conceptually the top of the block (phi functions) 20 // entry+1 and exit-1 are conceptually the bottom of the block (ordinary defs) 21 // entry-1 and exit+1 are conceptually "just before" the block (conditions flowing in) 22 // 23 // This simplifies life if we wish to query information about x 24 // when x is both an input to and output of a block. 25 entry, exit int32 26 } 27 28 func (s *SparseTreeNode) String() string { 29 return fmt.Sprintf("[%d,%d]", s.entry, s.exit) 30 } 31 32 func (s *SparseTreeNode) Entry() int32 { 33 return s.entry 34 } 35 36 func (s *SparseTreeNode) Exit() int32 { 37 return s.exit 38 } 39 40 const ( 41 // When used to lookup up definitions in a sparse tree, 42 // these adjustments to a block's entry (+adjust) and 43 // exit (-adjust) numbers allow a distinction to be made 44 // between assignments (typically branch-dependent 45 // conditionals) occurring "before" the block (e.g., as inputs 46 // to the block and its phi functions), "within" the block, 47 // and "after" the block. 48 AdjustBefore = -1 // defined before phi 49 AdjustWithin = 0 // defined by phi 50 AdjustAfter = 1 // defined within block 51 ) 52 53 // A SparseTree is a tree of Blocks. 54 // It allows rapid ancestor queries, 55 // such as whether one block dominates another. 56 type SparseTree []SparseTreeNode 57 58 // newSparseTree creates a SparseTree from a block-to-parent map (array indexed by Block.ID) 59 func newSparseTree(f *Func, parentOf []*Block) SparseTree { 60 t := make(SparseTree, f.NumBlocks()) 61 for _, b := range f.Blocks { 62 n := &t[b.ID] 63 if p := parentOf[b.ID]; p != nil { 64 n.parent = p 65 n.sibling = t[p.ID].child 66 t[p.ID].child = b 67 } 68 } 69 t.numberBlock(f.Entry, 1) 70 return t 71 } 72 73 // newSparseOrderedTree creates a SparseTree from a block-to-parent map (array indexed by Block.ID) 74 // children will appear in the reverse of their order in reverseOrder 75 // in particular, if reverseOrder is a dfs-reversePostOrder, then the root-to-children 76 // walk of the tree will yield a pre-order. 77 func newSparseOrderedTree(f *Func, parentOf, reverseOrder []*Block) SparseTree { 78 t := make(SparseTree, f.NumBlocks()) 79 for _, b := range reverseOrder { 80 n := &t[b.ID] 81 if p := parentOf[b.ID]; p != nil { 82 n.parent = p 83 n.sibling = t[p.ID].child 84 t[p.ID].child = b 85 } 86 } 87 t.numberBlock(f.Entry, 1) 88 return t 89 } 90 91 // treestructure provides a string description of the dominator 92 // tree and flow structure of block b and all blocks that it 93 // dominates. 94 func (t SparseTree) treestructure(b *Block) string { 95 return t.treestructure1(b, 0) 96 } 97 func (t SparseTree) treestructure1(b *Block, i int) string { 98 s := "\n" + strings.Repeat("\t", i) + b.String() + "->[" 99 for i, e := range b.Succs { 100 if i > 0 { 101 s += "," 102 } 103 s += e.b.String() 104 } 105 s += "]" 106 if c0 := t[b.ID].child; c0 != nil { 107 s += "(" 108 for c := c0; c != nil; c = t[c.ID].sibling { 109 if c != c0 { 110 s += " " 111 } 112 s += t.treestructure1(c, i+1) 113 } 114 s += ")" 115 } 116 return s 117 } 118 119 // numberBlock assigns entry and exit numbers for b and b's 120 // children in an in-order walk from a gappy sequence, where n 121 // is the first number not yet assigned or reserved. N should 122 // be larger than zero. For each entry and exit number, the 123 // values one larger and smaller are reserved to indicate 124 // "strictly above" and "strictly below". numberBlock returns 125 // the smallest number not yet assigned or reserved (i.e., the 126 // exit number of the last block visited, plus two, because 127 // last.exit+1 is a reserved value.) 128 // 129 // examples: 130 // 131 // single node tree Root, call with n=1 132 // entry=2 Root exit=5; returns 7 133 // 134 // two node tree, Root->Child, call with n=1 135 // entry=2 Root exit=11; returns 13 136 // entry=5 Child exit=8 137 // 138 // three node tree, Root->(Left, Right), call with n=1 139 // entry=2 Root exit=17; returns 19 140 // entry=5 Left exit=8; entry=11 Right exit=14 141 // 142 // This is the in-order sequence of assigned and reserved numbers 143 // for the last example: 144 // root left left right right root 145 // 1 2e 3 | 4 5e 6 | 7 8x 9 | 10 11e 12 | 13 14x 15 | 16 17x 18 146 147 func (t SparseTree) numberBlock(b *Block, n int32) int32 { 148 // reserve n for entry-1, assign n+1 to entry 149 n++ 150 t[b.ID].entry = n 151 // reserve n+1 for entry+1, n+2 is next free number 152 n += 2 153 for c := t[b.ID].child; c != nil; c = t[c.ID].sibling { 154 n = t.numberBlock(c, n) // preserves n = next free number 155 } 156 // reserve n for exit-1, assign n+1 to exit 157 n++ 158 t[b.ID].exit = n 159 // reserve n+1 for exit+1, n+2 is next free number, returned. 160 return n + 2 161 } 162 163 // Sibling returns a sibling of x in the dominator tree (i.e., 164 // a node with the same immediate dominator) or nil if there 165 // are no remaining siblings in the arbitrary but repeatable 166 // order chosen. Because the Child-Sibling order is used 167 // to assign entry and exit numbers in the treewalk, those 168 // numbers are also consistent with this order (i.e., 169 // Sibling(x) has entry number larger than x's exit number). 170 func (t SparseTree) Sibling(x *Block) *Block { 171 return t[x.ID].sibling 172 } 173 174 // Child returns a child of x in the dominator tree, or 175 // nil if there are none. The choice of first child is 176 // arbitrary but repeatable. 177 func (t SparseTree) Child(x *Block) *Block { 178 return t[x.ID].child 179 } 180 181 // isAncestorEq reports whether x is an ancestor of or equal to y. 182 func (t SparseTree) isAncestorEq(x, y *Block) bool { 183 if x == y { 184 return true 185 } 186 xx := &t[x.ID] 187 yy := &t[y.ID] 188 return xx.entry <= yy.entry && yy.exit <= xx.exit 189 } 190 191 // isAncestor reports whether x is a strict ancestor of y. 192 func (t SparseTree) isAncestor(x, y *Block) bool { 193 if x == y { 194 return false 195 } 196 xx := &t[x.ID] 197 yy := &t[y.ID] 198 return xx.entry < yy.entry && yy.exit < xx.exit 199 } 200 201 // domorder returns a value for dominator-oriented sorting. 202 // Block domination does not provide a total ordering, 203 // but domorder two has useful properties. 204 // (1) If domorder(x) > domorder(y) then x does not dominate y. 205 // (2) If domorder(x) < domorder(y) and domorder(y) < domorder(z) and x does not dominate y, 206 // then x does not dominate z. 207 // Property (1) means that blocks sorted by domorder always have a maximal dominant block first. 208 // Property (2) allows searches for dominated blocks to exit early. 209 func (t SparseTree) domorder(x *Block) int32 { 210 // Here is an argument that entry(x) provides the properties documented above. 211 // 212 // Entry and exit values are assigned in a depth-first dominator tree walk. 213 // For all blocks x and y, one of the following holds: 214 // 215 // (x-dom-y) x dominates y => entry(x) < entry(y) < exit(y) < exit(x) 216 // (y-dom-x) y dominates x => entry(y) < entry(x) < exit(x) < exit(y) 217 // (x-then-y) neither x nor y dominates the other and x walked before y => entry(x) < exit(x) < entry(y) < exit(y) 218 // (y-then-x) neither x nor y dominates the other and y walked before y => entry(y) < exit(y) < entry(x) < exit(x) 219 // 220 // entry(x) > entry(y) eliminates case x-dom-y. This provides property (1) above. 221 // 222 // For property (2), assume entry(x) < entry(y) and entry(y) < entry(z) and x does not dominate y. 223 // entry(x) < entry(y) allows cases x-dom-y and x-then-y. 224 // But by supposition, x does not dominate y. So we have x-then-y. 225 // 226 // For contractidion, assume x dominates z. 227 // Then entry(x) < entry(z) < exit(z) < exit(x). 228 // But we know x-then-y, so entry(x) < exit(x) < entry(y) < exit(y). 229 // Combining those, entry(x) < entry(z) < exit(z) < exit(x) < entry(y) < exit(y). 230 // By supposition, entry(y) < entry(z), which allows cases y-dom-z and y-then-z. 231 // y-dom-z requires entry(y) < entry(z), but we have entry(z) < entry(y). 232 // y-then-z requires exit(y) < entry(z), but we have entry(z) < exit(y). 233 // We have a contradiction, so x does not dominate z, as required. 234 return t[x.ID].entry 235 } 236