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