Source file src/cmd/compile/internal/ssa/sparsetreemap.go

Documentation: cmd/compile/internal/ssa

     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  

View as plain text