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