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 "fmt" 9 "strings" 10) 11 12type 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 28func (s *SparseTreeNode) String() string { 29 return fmt.Sprintf("[%d,%d]", s.entry, s.exit) 30} 31 32func (s *SparseTreeNode) Entry() int32 { 33 return s.entry 34} 35 36func (s *SparseTreeNode) Exit() int32 { 37 return s.exit 38} 39 40const ( 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. 56type SparseTree []SparseTreeNode 57 58// newSparseTree creates a SparseTree from a block-to-parent map (array indexed by Block.ID). 59func 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. 77func 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. 94func (t SparseTree) treestructure(b *Block) string { 95 return t.treestructure1(b, 0) 96} 97func (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 147func (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). 170func (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. 177func (t SparseTree) Child(x *Block) *Block { 178 return t[x.ID].child 179} 180 181// Parent returns the parent of x in the dominator tree, or 182// nil if x is the function's entry. 183func (t SparseTree) Parent(x *Block) *Block { 184 return t[x.ID].parent 185} 186 187// IsAncestorEq reports whether x is an ancestor of or equal to y. 188func (t SparseTree) IsAncestorEq(x, y *Block) bool { 189 if x == y { 190 return true 191 } 192 xx := &t[x.ID] 193 yy := &t[y.ID] 194 return xx.entry <= yy.entry && yy.exit <= xx.exit 195} 196 197// isAncestor reports whether x is a strict ancestor of y. 198func (t SparseTree) isAncestor(x, y *Block) bool { 199 if x == y { 200 return false 201 } 202 xx := &t[x.ID] 203 yy := &t[y.ID] 204 return xx.entry < yy.entry && yy.exit < xx.exit 205} 206 207// domorder returns a value for dominator-oriented sorting. 208// Block domination does not provide a total ordering, 209// but domorder two has useful properties. 210// 1. If domorder(x) > domorder(y) then x does not dominate y. 211// 2. If domorder(x) < domorder(y) and domorder(y) < domorder(z) and x does not dominate y, 212// then x does not dominate z. 213// 214// Property (1) means that blocks sorted by domorder always have a maximal dominant block first. 215// Property (2) allows searches for dominated blocks to exit early. 216func (t SparseTree) domorder(x *Block) int32 { 217 // Here is an argument that entry(x) provides the properties documented above. 218 // 219 // Entry and exit values are assigned in a depth-first dominator tree walk. 220 // For all blocks x and y, one of the following holds: 221 // 222 // (x-dom-y) x dominates y => entry(x) < entry(y) < exit(y) < exit(x) 223 // (y-dom-x) y dominates x => entry(y) < entry(x) < exit(x) < exit(y) 224 // (x-then-y) neither x nor y dominates the other and x walked before y => entry(x) < exit(x) < entry(y) < exit(y) 225 // (y-then-x) neither x nor y dominates the other and y walked before y => entry(y) < exit(y) < entry(x) < exit(x) 226 // 227 // entry(x) > entry(y) eliminates case x-dom-y. This provides property (1) above. 228 // 229 // For property (2), assume entry(x) < entry(y) and entry(y) < entry(z) and x does not dominate y. 230 // entry(x) < entry(y) allows cases x-dom-y and x-then-y. 231 // But by supposition, x does not dominate y. So we have x-then-y. 232 // 233 // For contradiction, assume x dominates z. 234 // Then entry(x) < entry(z) < exit(z) < exit(x). 235 // But we know x-then-y, so entry(x) < exit(x) < entry(y) < exit(y). 236 // Combining those, entry(x) < entry(z) < exit(z) < exit(x) < entry(y) < exit(y). 237 // By supposition, entry(y) < entry(z), which allows cases y-dom-z and y-then-z. 238 // y-dom-z requires entry(y) < entry(z), but we have entry(z) < entry(y). 239 // y-then-z requires exit(y) < entry(z), but we have entry(z) < exit(y). 240 // We have a contradiction, so x does not dominate z, as required. 241 return t[x.ID].entry 242} 243