diff options
Diffstat (limited to 'src/cmd/compile/internal/ssa/sparsetreemap.go')
| -rw-r--r-- | src/cmd/compile/internal/ssa/sparsetreemap.go | 104 |
1 files changed, 62 insertions, 42 deletions
diff --git a/src/cmd/compile/internal/ssa/sparsetreemap.go b/src/cmd/compile/internal/ssa/sparsetreemap.go index 61276985b1..3e6f296796 100644 --- a/src/cmd/compile/internal/ssa/sparsetreemap.go +++ b/src/cmd/compile/internal/ssa/sparsetreemap.go @@ -14,8 +14,8 @@ import "fmt" // the nearest tree ancestor of a given node such that the // ancestor is also in the set. // -// Given a set of blocks {B1, B2, B3} within the dominator tree, established by -// stm.Insert()ing B1, B2, B3, etc, a query at block B +// Given a set of blocks {B1, B2, B3} within the dominator tree, established +// by stm.Insert()ing B1, B2, B3, etc, a query at block B // (performed with stm.Find(stm, B, adjust, helper)) // will return the member of the set that is the nearest strict // ancestor of B within the dominator tree, or nil if none exists. @@ -49,9 +49,9 @@ type SparseTreeMap RBTint32 // packages, such as gc. type SparseTreeHelper struct { Sdom []SparseTreeNode // indexed by block.ID - Po []*Block // exported data - Dom []*Block // exported data - Ponums []int32 // exported data + Po []*Block // exported data; the blocks, in a post-order + Dom []*Block // exported data; the dominator of this block. + Ponums []int32 // exported data; Po[Ponums[b.ID]] == b; the index of b in Po } // NewSparseTreeHelper returns a SparseTreeHelper for use @@ -79,11 +79,19 @@ func makeSparseTreeHelper(sdom SparseTree, dom, po []*Block, ponums []int32) *Sp // A sparseTreeMapEntry contains the data stored in a binary search // data structure indexed by (dominator tree walk) entry and exit numbers. // Each entry is added twice, once keyed by entry-1/entry/entry+1 and -// once keyed by exit+1/exit/exit-1. (there are three choices of paired indices, not 9, and they properly nest) +// once keyed by exit+1/exit/exit-1. +// +// Within a sparse tree, the two entries added bracket all their descendant +// entries within the tree; the first insertion is keyed by entry number, +// which comes before all the entry and exit numbers of descendants, and +// the second insertion is keyed by exit number, which comes after all the +// entry and exit numbers of the descendants. type sparseTreeMapEntry struct { - index *SparseTreeNode - block *Block // TODO: store this in a separate index. - data interface{} + index *SparseTreeNode // references the entry and exit numbers for a block in the sparse tree + block *Block // TODO: store this in a separate index. + data interface{} + sparseParent *sparseTreeMapEntry // references the nearest ancestor of this block in the sparse tree. + 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. } // Insert creates a definition within b with data x. @@ -98,12 +106,25 @@ func (m *SparseTreeMap) Insert(b *Block, adjust int32, x interface{}, helper *Sp // assert unreachable return } - entry := &sparseTreeMapEntry{index: blockIndex, data: x} + // sp will be the sparse parent in this sparse tree (nearest ancestor in the larger tree that is also in this sparse tree) + sp := m.findEntry(b, adjust, helper) + entry := &sparseTreeMapEntry{index: blockIndex, block: b, data: x, sparseParent: sp, adjust: adjust} + right := blockIndex.exit - adjust _ = rbtree.Insert(right, entry) left := blockIndex.entry + adjust _ = rbtree.Insert(left, entry) + + // This newly inserted block may now be the sparse parent of some existing nodes (the new sparse children of this block) + // Iterate over nodes bracketed by this new node to correct their parent, but not over the proper sparse descendants of those nodes. + _, d := rbtree.Lub(left) // Lub (not EQ) of left is either right or a sparse child + for tme := d.(*sparseTreeMapEntry); tme != entry; tme = d.(*sparseTreeMapEntry) { + tme.sparseParent = entry + // all descendants of tme are unchanged; + // next sparse sibling (or right-bracketing sparse parent == entry) is first node after tme.index.exit - tme.adjust + _, d = rbtree.Lub(tme.index.exit - tme.adjust) + } } // Find returns the definition visible from block b, or nil if none can be found. @@ -118,45 +139,41 @@ func (m *SparseTreeMap) Insert(b *Block, adjust int32, x interface{}, helper *Sp // // Another way to think of this is that Find searches for inputs, Insert defines outputs. func (m *SparseTreeMap) Find(b *Block, adjust int32, helper *SparseTreeHelper) interface{} { + v := m.findEntry(b, adjust, helper) + if v == nil { + return nil + } + return v.data +} + +func (m *SparseTreeMap) findEntry(b *Block, adjust int32, helper *SparseTreeHelper) *sparseTreeMapEntry { rbtree := (*RBTint32)(m) if rbtree == nil { return nil } blockIndex := &helper.Sdom[b.ID] + + // The Glb (not EQ) of this probe is either the entry-indexed end of a sparse parent + // or the exit-indexed end of a sparse sibling _, v := rbtree.Glb(blockIndex.entry + adjust) - for v != nil { - otherEntry := v.(*sparseTreeMapEntry) - otherIndex := otherEntry.index - // Two cases -- either otherIndex brackets blockIndex, - // or it doesn't. - // - // Note that if otherIndex and blockIndex are - // the same block, then the glb test only passed - // because the definition is "before", - // i.e., k == blockIndex.entry-1 - // allowing equality is okay on the blocks check. - if otherIndex.exit >= blockIndex.exit { - // bracketed. - return otherEntry.data + + if v == nil { + return nil + } + + otherEntry := v.(*sparseTreeMapEntry) + if otherEntry.index.exit >= blockIndex.exit { // otherEntry exit after blockIndex exit; therefore, brackets + return otherEntry + } + // otherEntry is a sparse Sibling, and shares the same sparse parent (nearest ancestor within larger tree) + sp := otherEntry.sparseParent + if sp != nil { + if sp.index.exit < blockIndex.exit { // no ancestor found + return nil } - // In the not-bracketed case, we could memoize the results of - // walking up the tree, but for now we won't. - // Memoize plan is to take the gap (inclusive) - // from otherIndex.exit+1 to blockIndex.entry-1 - // and insert it into this or a second tree. - // Said tree would then need adjusting whenever - // an insertion occurred. - - // Expectation is that per-variable tree is sparse, - // therefore probe siblings instead of climbing up. - // Note that each sibling encountered in this walk - // to find a defining ancestor shares that ancestor - // because the walk skips over the interior -- each - // Glb will be an exit, and the iteration is to the - // Glb of the entry. - _, v = rbtree.Glb(otherIndex.entry - 1) + return sp } - return nil // nothing found + return nil } func (m *SparseTreeMap) String() string { @@ -165,5 +182,8 @@ func (m *SparseTreeMap) String() string { } func (e *sparseTreeMapEntry) String() string { - return fmt.Sprintf("index=%v, data=%v", e.index, e.data) + if e == nil { + return "nil" + } + return fmt.Sprintf("(index=%v, block=%v, data=%v)->%v", e.index, e.block, e.data, e.sparseParent) } |