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