dom.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  // This file contains code to compute the dominator tree
     8  // of a control-flow graph.
     9  
    10  // postorder computes a postorder traversal ordering for the
    11  // basic blocks in f. Unreachable blocks will not appear.
    12  func postorder(f *Func) []*Block {
    13  	return postorderWithNumbering(f, nil)
    14  }
    15  
    16  type blockAndIndex struct {
    17  	b     *Block
    18  	index int // index is the number of successor edges of b that have already been explored.
    19  }
    20  
    21  // postorderWithNumbering provides a DFS postordering.
    22  // This seems to make loop-finding more robust.
    23  func postorderWithNumbering(f *Func, ponums []int32) []*Block {
    24  	seen := make([]bool, f.NumBlocks())
    25  
    26  	// result ordering
    27  	order := make([]*Block, 0, len(f.Blocks))
    28  
    29  	// stack of blocks and next child to visit
    30  	// A constant bound allows this to be stack-allocated. 32 is
    31  	// enough to cover almost every postorderWithNumbering call.
    32  	s := make([]blockAndIndex, 0, 32)
    33  	s = append(s, blockAndIndex{b: f.Entry})
    34  	seen[f.Entry.ID] = true
    35  	for len(s) > 0 {
    36  		tos := len(s) - 1
    37  		x := s[tos]
    38  		b := x.b
    39  		if i := x.index; i < len(b.Succs) {
    40  			s[tos].index++
    41  			bb := b.Succs[i].Block()
    42  			if !seen[bb.ID] {
    43  				seen[bb.ID] = true
    44  				s = append(s, blockAndIndex{b: bb})
    45  			}
    46  			continue
    47  		}
    48  		s = s[:tos]
    49  		if ponums != nil {
    50  			ponums[b.ID] = int32(len(order))
    51  		}
    52  		order = append(order, b)
    53  	}
    54  	return order
    55  }
    56  
    57  type linkedBlocks func(*Block) []Edge
    58  
    59  const nscratchslices = 7
    60  
    61  // experimentally, functions with 512 or fewer blocks account
    62  // for 75% of memory (size) allocation for dominator computation
    63  // in make.bash.
    64  const minscratchblocks = 512
    65  
    66  func (cache *Cache) scratchBlocksForDom(maxBlockID int) (a, b, c, d, e, f, g []ID) {
    67  	tot := maxBlockID * nscratchslices
    68  	scratch := cache.domblockstore
    69  	if len(scratch) < tot {
    70  		// req = min(1.5*tot, nscratchslices*minscratchblocks)
    71  		// 50% padding allows for graph growth in later phases.
    72  		req := (tot * 3) >> 1
    73  		if req < nscratchslices*minscratchblocks {
    74  			req = nscratchslices * minscratchblocks
    75  		}
    76  		scratch = make([]ID, req)
    77  		cache.domblockstore = scratch
    78  	} else {
    79  		// Clear as much of scratch as we will (re)use
    80  		scratch = scratch[0:tot]
    81  		for i := range scratch {
    82  			scratch[i] = 0
    83  		}
    84  	}
    85  
    86  	a = scratch[0*maxBlockID : 1*maxBlockID]
    87  	b = scratch[1*maxBlockID : 2*maxBlockID]
    88  	c = scratch[2*maxBlockID : 3*maxBlockID]
    89  	d = scratch[3*maxBlockID : 4*maxBlockID]
    90  	e = scratch[4*maxBlockID : 5*maxBlockID]
    91  	f = scratch[5*maxBlockID : 6*maxBlockID]
    92  	g = scratch[6*maxBlockID : 7*maxBlockID]
    93  
    94  	return
    95  }
    96  
    97  func dominators(f *Func) []*Block {
    98  	preds := func(b *Block) []Edge { return b.Preds }
    99  	succs := func(b *Block) []Edge { return b.Succs }
   100  
   101  	//TODO: benchmark and try to find criteria for swapping between
   102  	// dominatorsSimple and dominatorsLT
   103  	return f.dominatorsLTOrig(f.Entry, preds, succs)
   104  }
   105  
   106  // dominatorsLTOrig runs Lengauer-Tarjan to compute a dominator tree starting at
   107  // entry and using predFn/succFn to find predecessors/successors to allow
   108  // computing both dominator and post-dominator trees.
   109  func (f *Func) dominatorsLTOrig(entry *Block, predFn linkedBlocks, succFn linkedBlocks) []*Block {
   110  	// Adapted directly from the original TOPLAS article's "simple" algorithm
   111  
   112  	maxBlockID := entry.Func.NumBlocks()
   113  	semi, vertex, label, parent, ancestor, bucketHead, bucketLink := f.Cache.scratchBlocksForDom(maxBlockID)
   114  
   115  	// This version uses integers for most of the computation,
   116  	// to make the work arrays smaller and pointer-free.
   117  	// fromID translates from ID to *Block where that is needed.
   118  	fromID := make([]*Block, maxBlockID)
   119  	for _, v := range f.Blocks {
   120  		fromID[v.ID] = v
   121  	}
   122  	idom := make([]*Block, maxBlockID)
   123  
   124  	// Step 1. Carry out a depth first search of the problem graph. Number
   125  	// the vertices from 1 to n as they are reached during the search.
   126  	n := f.dfsOrig(entry, succFn, semi, vertex, label, parent)
   127  
   128  	for i := n; i >= 2; i-- {
   129  		w := vertex[i]
   130  
   131  		// step2 in TOPLAS paper
   132  		for _, e := range predFn(fromID[w]) {
   133  			v := e.b
   134  			if semi[v.ID] == 0 {
   135  				// skip unreachable predecessor
   136  				// not in original, but we're using existing pred instead of building one.
   137  				continue
   138  			}
   139  			u := evalOrig(v.ID, ancestor, semi, label)
   140  			if semi[u] < semi[w] {
   141  				semi[w] = semi[u]
   142  			}
   143  		}
   144  
   145  		// add w to bucket[vertex[semi[w]]]
   146  		// implement bucket as a linked list implemented
   147  		// in a pair of arrays.
   148  		vsw := vertex[semi[w]]
   149  		bucketLink[w] = bucketHead[vsw]
   150  		bucketHead[vsw] = w
   151  
   152  		linkOrig(parent[w], w, ancestor)
   153  
   154  		// step3 in TOPLAS paper
   155  		for v := bucketHead[parent[w]]; v != 0; v = bucketLink[v] {
   156  			u := evalOrig(v, ancestor, semi, label)
   157  			if semi[u] < semi[v] {
   158  				idom[v] = fromID[u]
   159  			} else {
   160  				idom[v] = fromID[parent[w]]
   161  			}
   162  		}
   163  	}
   164  	// step 4 in toplas paper
   165  	for i := ID(2); i <= n; i++ {
   166  		w := vertex[i]
   167  		if idom[w].ID != vertex[semi[w]] {
   168  			idom[w] = idom[idom[w].ID]
   169  		}
   170  	}
   171  
   172  	return idom
   173  }
   174  
   175  // dfs performs a depth first search over the blocks starting at entry block
   176  // (in arbitrary order).  This is a de-recursed version of dfs from the
   177  // original Tarjan-Lengauer TOPLAS article.  It's important to return the
   178  // same values for parent as the original algorithm.
   179  func (f *Func) dfsOrig(entry *Block, succFn linkedBlocks, semi, vertex, label, parent []ID) ID {
   180  	n := ID(0)
   181  	s := make([]*Block, 0, 256)
   182  	s = append(s, entry)
   183  
   184  	for len(s) > 0 {
   185  		v := s[len(s)-1]
   186  		s = s[:len(s)-1]
   187  		// recursing on v
   188  
   189  		if semi[v.ID] != 0 {
   190  			continue // already visited
   191  		}
   192  		n++
   193  		semi[v.ID] = n
   194  		vertex[n] = v.ID
   195  		label[v.ID] = v.ID
   196  		// ancestor[v] already zero
   197  		for _, e := range succFn(v) {
   198  			w := e.b
   199  			// if it has a dfnum, we've already visited it
   200  			if semi[w.ID] == 0 {
   201  				// yes, w can be pushed multiple times.
   202  				s = append(s, w)
   203  				parent[w.ID] = v.ID // keep overwriting this till it is visited.
   204  			}
   205  		}
   206  	}
   207  	return n
   208  }
   209  
   210  // compressOrig is the "simple" compress function from LT paper
   211  func compressOrig(v ID, ancestor, semi, label []ID) {
   212  	if ancestor[ancestor[v]] != 0 {
   213  		compressOrig(ancestor[v], ancestor, semi, label)
   214  		if semi[label[ancestor[v]]] < semi[label[v]] {
   215  			label[v] = label[ancestor[v]]
   216  		}
   217  		ancestor[v] = ancestor[ancestor[v]]
   218  	}
   219  }
   220  
   221  // evalOrig is the "simple" eval function from LT paper
   222  func evalOrig(v ID, ancestor, semi, label []ID) ID {
   223  	if ancestor[v] == 0 {
   224  		return v
   225  	}
   226  	compressOrig(v, ancestor, semi, label)
   227  	return label[v]
   228  }
   229  
   230  func linkOrig(v, w ID, ancestor []ID) {
   231  	ancestor[w] = v
   232  }
   233  
   234  // dominators computes the dominator tree for f. It returns a slice
   235  // which maps block ID to the immediate dominator of that block.
   236  // Unreachable blocks map to nil. The entry block maps to nil.
   237  func dominatorsSimple(f *Func) []*Block {
   238  	// A simple algorithm for now
   239  	// Cooper, Harvey, Kennedy
   240  	idom := make([]*Block, f.NumBlocks())
   241  
   242  	// Compute postorder walk
   243  	post := f.postorder()
   244  
   245  	// Make map from block id to order index (for intersect call)
   246  	postnum := make([]int, f.NumBlocks())
   247  	for i, b := range post {
   248  		postnum[b.ID] = i
   249  	}
   250  
   251  	// Make the entry block a self-loop
   252  	idom[f.Entry.ID] = f.Entry
   253  	if postnum[f.Entry.ID] != len(post)-1 {
   254  		f.Fatalf("entry block %v not last in postorder", f.Entry)
   255  	}
   256  
   257  	// Compute relaxation of idom entries
   258  	for {
   259  		changed := false
   260  
   261  		for i := len(post) - 2; i >= 0; i-- {
   262  			b := post[i]
   263  			var d *Block
   264  			for _, e := range b.Preds {
   265  				p := e.b
   266  				if idom[p.ID] == nil {
   267  					continue
   268  				}
   269  				if d == nil {
   270  					d = p
   271  					continue
   272  				}
   273  				d = intersect(d, p, postnum, idom)
   274  			}
   275  			if d != idom[b.ID] {
   276  				idom[b.ID] = d
   277  				changed = true
   278  			}
   279  		}
   280  		if !changed {
   281  			break
   282  		}
   283  	}
   284  	// Set idom of entry block to nil instead of itself.
   285  	idom[f.Entry.ID] = nil
   286  	return idom
   287  }
   288  
   289  // intersect finds the closest dominator of both b and c.
   290  // It requires a postorder numbering of all the blocks.
   291  func intersect(b, c *Block, postnum []int, idom []*Block) *Block {
   292  	// TODO: This loop is O(n^2). It used to be used in nilcheck,
   293  	// see BenchmarkNilCheckDeep*.
   294  	for b != c {
   295  		if postnum[b.ID] < postnum[c.ID] {
   296  			b = idom[b.ID]
   297  		} else {
   298  			c = idom[c.ID]
   299  		}
   300  	}
   301  	return b
   302  }
   303
View as plain text