@@ -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 " index , e.data )
if e == nil {
return " nil"
}
return fmt.Sprintf (" (index=%v , block=%v , data=%v )->%v " index , e.block , e.data , e.sparseParent )
}