1 // Copyright 2016 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 // A SparseTreeMap encodes a subset of nodes within a tree 10 // used for sparse-ancestor queries. 11 // 12 // Combined with a SparseTreeHelper, this supports an Insert 13 // to add a tree node to the set and a Find operation to locate 14 // the nearest tree ancestor of a given node such that the 15 // ancestor is also in the set. 16 // 17 // Given a set of blocks {B1, B2, B3} within the dominator tree, established 18 // by stm.Insert()ing B1, B2, B3, etc, a query at block B 19 // (performed with stm.Find(stm, B, adjust, helper)) 20 // will return the member of the set that is the nearest strict 21 // ancestor of B within the dominator tree, or nil if none exists. 22 // The expected complexity of this operation is the log of the size 23 // the set, given certain assumptions about sparsity (the log complexity 24 // could be guaranteed with additional data structures whose constant- 25 // factor overhead has not yet been justified.) 26 // 27 // The adjust parameter allows positioning of the insertion 28 // and lookup points within a block -- one of 29 // AdjustBefore, AdjustWithin, AdjustAfter, 30 // where lookups at AdjustWithin can find insertions at 31 // AdjustBefore in the same block, and lookups at AdjustAfter 32 // can find insertions at either AdjustBefore or AdjustWithin 33 // in the same block. (Note that this assumes a gappy numbering 34 // such that exit number or exit number is separated from its 35 // nearest neighbor by at least 3). 36 // 37 // The Sparse Tree lookup algorithm is described by 38 // Paul F. Dietz. Maintaining order in a linked list. In 39 // Proceedings of the Fourteenth Annual ACM Symposium on 40 // Theory of Computing, pages 122–127, May 1982. 41 // and by 42 // Ben Wegbreit. Faster retrieval from context trees. 43 // Communications of the ACM, 19(9):526–529, September 1976. 44 type SparseTreeMap RBTint32 45 46 // A SparseTreeHelper contains indexing and allocation data 47 // structures common to a collection of SparseTreeMaps, as well 48 // as exposing some useful control-flow-related data to other 49 // packages, such as gc. 50 type SparseTreeHelper struct { 51 Sdom []SparseTreeNode // indexed by block.ID 52 Po []*Block // exported data; the blocks, in a post-order 53 Dom []*Block // exported data; the dominator of this block. 54 Ponums []int32 // exported data; Po[Ponums[b.ID]] == b; the index of b in Po 55 } 56 57 // NewSparseTreeHelper returns a SparseTreeHelper for use 58 // in the gc package, for example in phi-function placement. 59 func NewSparseTreeHelper(f *Func) *SparseTreeHelper { 60 dom := f.Idom() 61 ponums := make([]int32, f.NumBlocks()) 62 po := postorderWithNumbering(f, ponums) 63 return makeSparseTreeHelper(newSparseTree(f, dom), dom, po, ponums) 64 } 65 66 func (h *SparseTreeHelper) NewTree() *SparseTreeMap { 67 return &SparseTreeMap{} 68 } 69 70 func makeSparseTreeHelper(sdom SparseTree, dom, po []*Block, ponums []int32) *SparseTreeHelper { 71 helper := &SparseTreeHelper{Sdom: []SparseTreeNode(sdom), 72 Dom: dom, 73 Po: po, 74 Ponums: ponums, 75 } 76 return helper 77 } 78 79 // A sparseTreeMapEntry contains the data stored in a binary search 80 // data structure indexed by (dominator tree walk) entry and exit numbers. 81 // Each entry is added twice, once keyed by entry-1/entry/entry+1 and 82 // once keyed by exit+1/exit/exit-1. 83 // 84 // Within a sparse tree, the two entries added bracket all their descendant 85 // entries within the tree; the first insertion is keyed by entry number, 86 // which comes before all the entry and exit numbers of descendants, and 87 // the second insertion is keyed by exit number, which comes after all the 88 // entry and exit numbers of the descendants. 89 type sparseTreeMapEntry struct { 90 index *SparseTreeNode // references the entry and exit numbers for a block in the sparse tree 91 block *Block // TODO: store this in a separate index. 92 data interface{} 93 sparseParent *sparseTreeMapEntry // references the nearest ancestor of this block in the sparse tree. 94 adjust int32 // at what adjustment was this node entered into the sparse tree? The same block may be entered more than once, but at different adjustments. 95 } 96 97 // Insert creates a definition within b with data x. 98 // adjust indicates where in the block should be inserted: 99 // AdjustBefore means defined at a phi function (visible Within or After in the same block) 100 // AdjustWithin means defined within the block (visible After in the same block) 101 // AdjustAfter means after the block (visible within child blocks) 102 func (m *SparseTreeMap) Insert(b *Block, adjust int32, x interface{}, helper *SparseTreeHelper) { 103 rbtree := (*RBTint32)(m) 104 blockIndex := &helper.Sdom[b.ID] 105 if blockIndex.entry == 0 { 106 // assert unreachable 107 return 108 } 109 // sp will be the sparse parent in this sparse tree (nearest ancestor in the larger tree that is also in this sparse tree) 110 sp := m.findEntry(b, adjust, helper) 111 entry := &sparseTreeMapEntry{index: blockIndex, block: b, data: x, sparseParent: sp, adjust: adjust} 112 113 right := blockIndex.exit - adjust 114 _ = rbtree.Insert(right, entry) 115 116 left := blockIndex.entry + adjust 117 _ = rbtree.Insert(left, entry) 118 119 // This newly inserted block may now be the sparse parent of some existing nodes (the new sparse children of this block) 120 // Iterate over nodes bracketed by this new node to correct their parent, but not over the proper sparse descendants of those nodes. 121 _, d := rbtree.Lub(left) // Lub (not EQ) of left is either right or a sparse child 122 for tme := d.(*sparseTreeMapEntry); tme != entry; tme = d.(*sparseTreeMapEntry) { 123 tme.sparseParent = entry 124 // all descendants of tme are unchanged; 125 // next sparse sibling (or right-bracketing sparse parent == entry) is first node after tme.index.exit - tme.adjust 126 _, d = rbtree.Lub(tme.index.exit - tme.adjust) 127 } 128 } 129 130 // Find returns the definition visible from block b, or nil if none can be found. 131 // Adjust indicates where the block should be searched. 132 // AdjustBefore searches before the phi functions of b. 133 // AdjustWithin searches starting at the phi functions of b. 134 // AdjustAfter searches starting at the exit from the block, including normal within-block definitions. 135 // 136 // Note that Finds are properly nested with Inserts: 137 // m.Insert(b, a) followed by m.Find(b, a) will not return the result of the insert, 138 // but m.Insert(b, AdjustBefore) followed by m.Find(b, AdjustWithin) will. 139 // 140 // Another way to think of this is that Find searches for inputs, Insert defines outputs. 141 func (m *SparseTreeMap) Find(b *Block, adjust int32, helper *SparseTreeHelper) interface{} { 142 v := m.findEntry(b, adjust, helper) 143 if v == nil { 144 return nil 145 } 146 return v.data 147 } 148 149 func (m *SparseTreeMap) findEntry(b *Block, adjust int32, helper *SparseTreeHelper) *sparseTreeMapEntry { 150 rbtree := (*RBTint32)(m) 151 if rbtree == nil { 152 return nil 153 } 154 blockIndex := &helper.Sdom[b.ID] 155 156 // The Glb (not EQ) of this probe is either the entry-indexed end of a sparse parent 157 // or the exit-indexed end of a sparse sibling 158 _, v := rbtree.Glb(blockIndex.entry + adjust) 159 160 if v == nil { 161 return nil 162 } 163 164 otherEntry := v.(*sparseTreeMapEntry) 165 if otherEntry.index.exit >= blockIndex.exit { // otherEntry exit after blockIndex exit; therefore, brackets 166 return otherEntry 167 } 168 // otherEntry is a sparse Sibling, and shares the same sparse parent (nearest ancestor within larger tree) 169 sp := otherEntry.sparseParent 170 if sp != nil { 171 if sp.index.exit < blockIndex.exit { // no ancestor found 172 return nil 173 } 174 return sp 175 } 176 return nil 177 } 178 179 func (m *SparseTreeMap) String() string { 180 tree := (*RBTint32)(m) 181 return tree.String() 182 } 183 184 func (e *sparseTreeMapEntry) String() string { 185 if e == nil { 186 return "nil" 187 } 188 return fmt.Sprintf("(index=%v, block=%v, data=%v)->%v", e.index, e.block, e.data, e.sparseParent) 189 } 190