Source file src/pkg/cmd/compile/internal/ssa/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	// 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, nil)
    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		order := make([]*Block, 0, len(f.Blocks))
    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