...
Run Format

Source file src/cmd/compile/internal/ssa/dom.go

Documentation: cmd/compile/internal/ssa

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

View as plain text