sparsetree.go

     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  
     5  package ssa
     6  
     7  import (
     8  	"fmt"
     9  	"strings"
    10  )
    11  
    12  type 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  
    28  func (s *SparseTreeNode) String() string {
    29  	return fmt.Sprintf("[%d,%d]", s.entry, s.exit)
    30  }
    31  
    32  func (s *SparseTreeNode) Entry() int32 {
    33  	return s.entry
    34  }
    35  
    36  func (s *SparseTreeNode) Exit() int32 {
    37  	return s.exit
    38  }
    39  
    40  const (
    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.
    56  type SparseTree []SparseTreeNode
    57  
    58  // newSparseTree creates a SparseTree from a block-to-parent map (array indexed by Block.ID)
    59  func 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.
    77  func 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.
    94  func (t SparseTree) treestructure(b *Block) string {
    95  	return t.treestructure1(b, 0)
    96  }
    97  func (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  
   147  func (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).
   170  func (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.
   177  func (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.
   183  func (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.
   188  func (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.
   198  func (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  // Property (1) means that blocks sorted by domorder always have a maximal dominant block first.
   214  // Property (2) allows searches for dominated blocks to exit early.
   215  func (t SparseTree) domorder(x *Block) int32 {
   216  	// Here is an argument that entry(x) provides the properties documented above.
   217  	//
   218  	// Entry and exit values are assigned in a depth-first dominator tree walk.
   219  	// For all blocks x and y, one of the following holds:
   220  	//
   221  	// (x-dom-y) x dominates y => entry(x) < entry(y) < exit(y) < exit(x)
   222  	// (y-dom-x) y dominates x => entry(y) < entry(x) < exit(x) < exit(y)
   223  	// (x-then-y) neither x nor y dominates the other and x walked before y => entry(x) < exit(x) < entry(y) < exit(y)
   224  	// (y-then-x) neither x nor y dominates the other and y walked before y => entry(y) < exit(y) < entry(x) < exit(x)
   225  	//
   226  	// entry(x) > entry(y) eliminates case x-dom-y. This provides property (1) above.
   227  	//
   228  	// For property (2), assume entry(x) < entry(y) and entry(y) < entry(z) and x does not dominate y.
   229  	// entry(x) < entry(y) allows cases x-dom-y and x-then-y.
   230  	// But by supposition, x does not dominate y. So we have x-then-y.
   231  	//
   232  	// For contradiction, assume x dominates z.
   233  	// Then entry(x) < entry(z) < exit(z) < exit(x).
   234  	// But we know x-then-y, so entry(x) < exit(x) < entry(y) < exit(y).
   235  	// Combining those, entry(x) < entry(z) < exit(z) < exit(x) < entry(y) < exit(y).
   236  	// By supposition, entry(y) < entry(z), which allows cases y-dom-z and y-then-z.
   237  	// y-dom-z requires entry(y) < entry(z), but we have entry(z) < entry(y).
   238  	// y-then-z requires exit(y) < entry(z), but we have entry(z) < exit(y).
   239  	// We have a contradiction, so x does not dominate z, as required.
   240  	return t[x.ID].entry
   241  }
   242
View as plain text