[dev.ssa] cmd/compile/internal : Implement Lengauer-Tarjan for dominators

Implements the simple Lengauer-Tarjan algorithm for dominator
and post-dominator calculation.

benchmark                           old ns/op     new ns/op     delta
BenchmarkDominatorsLinear-8         1403862       1292741       -7.92%
BenchmarkDominatorsFwdBack-8        1270633       1428285       +12.41%
BenchmarkDominatorsManyPred-8       225932354     1530886       -99.32%
BenchmarkDominatorsMaxPred-8        445994225     1393612       -99.69%
BenchmarkDominatorsMaxPredVal-8     447235248     1246899       -99.72%
BenchmarkNilCheckDeep1-8            829           1259          +51.87%
BenchmarkNilCheckDeep10-8           2199          2397          +9.00%
BenchmarkNilCheckDeep100-8          57325         29405         -48.70%
BenchmarkNilCheckDeep1000-8         6625837       2933151       -55.73%
BenchmarkNilCheckDeep10000-8        763559787     319105541     -58.21%

benchmark                           old MB/s     new MB/s     speedup
BenchmarkDominatorsLinear-8         7.12         7.74         1.09x
BenchmarkDominatorsFwdBack-8        7.87         7.00         0.89x
BenchmarkDominatorsManyPred-8       0.04         6.53         163.25x
BenchmarkDominatorsMaxPred-8        0.02         7.18         359.00x
BenchmarkDominatorsMaxPredVal-8     0.02         8.02         401.00x
BenchmarkNilCheckDeep1-8            1.21         0.79         0.65x
BenchmarkNilCheckDeep10-8           4.55         4.17         0.92x
BenchmarkNilCheckDeep100-8          1.74         3.40         1.95x
BenchmarkNilCheckDeep1000-8         0.15         0.34         2.27x
BenchmarkNilCheckDeep10000-8        0.01         0.03         3.00x

Change-Id: Icec3d774422a9bc64914779804c8c0ab73aa72bf
Reviewed-on: https://go-review.googlesource.com/11971
Reviewed-by: Keith Randall <khr@golang.org>

2 files changed, 304 insertions, 20 deletions

diff --git a/src/cmd/compile/internal/ssa/dom.go b/src/cmd/compile/internal/ssa/dom.go
index b4d47c1350..b6fda0c953 100644
--- a/src/cmd/compile/internal/ssa/dom.go
+++ b/src/cmd/compile/internal/ssa/dom.go
@@ -4,6 +4,14 @@
 
 package ssa
 
+// mark values
+const (
+	notFound    = 0 // block has not been discovered yet
+	notExplored = 1 // discovered and in queue, outedges not processed yet
+	explored    = 2 // discovered and in queue, outedges processed
+	done        = 3 // all done, in output ordering
+)
+
 // This file contains code to compute the dominator tree
 // of a control-flow graph.
 
@@ -11,13 +19,6 @@ package ssa
 // basic blocks in f.  Unreachable blocks will not appear.
 func postorder(f *Func) []*Block {
 	mark := make([]byte, f.NumBlocks())
-	// mark values
-	const (
-		notFound    = 0 // block has not been discovered yet
-		notExplored = 1 // discovered and in queue, outedges not processed yet
-		explored    = 2 // discovered and in queue, outedges processed
-		done        = 3 // all done, in output ordering
-	)
 
 	// result ordering
 	var order []*Block
@@ -51,11 +52,196 @@ func postorder(f *Func) []*Block {
 	return order
 }
 
+type linkedBlocks func(*Block) []*Block
+
+// dfs performs a depth first search over the blocks. dfnum contains a mapping
+// from block id to an int indicating the order the block was reached or
+// notFound if the block was not reached.  order contains a mapping from dfnum
+// to block
+func dfs(entry *Block, succFn linkedBlocks) (dfnum []int, order []*Block, parent []*Block) {
+	maxBlockID := entry.Func.NumBlocks()
+
+	dfnum = make([]int, maxBlockID)
+	order = make([]*Block, maxBlockID)
+	parent = make([]*Block, maxBlockID)
+
+	n := 0
+	s := make([]*Block, 0, 256)
+	s = append(s, entry)
+	parent[entry.ID] = entry
+	for len(s) > 0 {
+		node := s[len(s)-1]
+		s = s[:len(s)-1]
+
+		n++
+		for _, w := range succFn(node) {
+			// if it has a dfnum, we've already visited it
+			if dfnum[w.ID] == notFound {
+				s = append(s, w)
+				parent[w.ID] = node
+				dfnum[w.ID] = notExplored
+			}
+		}
+		dfnum[node.ID] = n
+		order[n] = node
+	}
+
+	return
+}
+
 // dominators computes the dominator tree for f.  It returns a slice
 // which maps block ID to the immediate dominator of that block.
 // Unreachable blocks map to nil.  The entry block maps to nil.
 func dominators(f *Func) []*Block {
+	preds := func(b *Block) []*Block { return b.Preds }
+	succs := func(b *Block) []*Block { return b.Succs }
+
+	//TODO: benchmark and try to find criteria for swapping between
+	// dominatorsSimple and dominatorsLT
+	return dominatorsLT(f.Entry, preds, succs)
+}
+
+// postDominators computes the post-dominator tree for f.
+func postDominators(f *Func) []*Block {
+	preds := func(b *Block) []*Block { return b.Preds }
+	succs := func(b *Block) []*Block { return b.Succs }
+
+	if len(f.Blocks) == 0 {
+		return nil
+	}
+
+	// find the exit block, maybe store it as f.Exit instead?
+	var exit *Block
+	for i := len(f.Blocks) - 1; i >= 0; i-- {
+		if f.Blocks[i].Kind == BlockExit {
+			exit = f.Blocks[i]
+			break
+		}
+	}
+
+	// infite loop with no exit
+	if exit == nil {
+		return make([]*Block, f.NumBlocks())
+	}
+	return dominatorsLT(exit, succs, preds)
+}
+
+// dominatorsLt runs Lengauer-Tarjan to compute a dominator tree starting at
+// entry and using predFn/succFn to find predecessors/successors to allow
+// computing both dominator and post-dominator trees.
+func dominatorsLT(entry *Block, predFn linkedBlocks, succFn linkedBlocks) []*Block {
+	// Based on Lengauer-Tarjan from Modern Compiler Implementation in C -
+	// Appel with optimizations from Finding Dominators in Practice -
+	// Georgiadis
+
+	// Step 1. Carry out a depth first search of the problem graph. Number
+	// the vertices from 1 to n as they are reached during the search.
+	dfnum, vertex, parent := dfs(entry, succFn)
+
+	maxBlockID := entry.Func.NumBlocks()
+	semi := make([]*Block, maxBlockID)
+	samedom := make([]*Block, maxBlockID)
+	idom := make([]*Block, maxBlockID)
+	ancestor := make([]*Block, maxBlockID)
+	best := make([]*Block, maxBlockID)
+	bucket := make([]*Block, maxBlockID)
+
+	// Step 2. Compute the semidominators of all vertices by applying
+	// Theorem 4.  Carry out the computation vertex by vertex in decreasing
+	// order by number.
+	for i := maxBlockID - 1; i > 0; i-- {
+		w := vertex[i]
+		if w == nil {
+			continue
+		}
+
+		if dfnum[w.ID] == notFound {
+			// skip unreachable node
+			continue
+		}
 
+		// Step 3. Implicitly define the immediate dominator of each
+		// vertex by applying Corollary 1. (reordered)
+		for v := bucket[w.ID]; v != nil; v = bucket[v.ID] {
+			u := eval(v, ancestor, semi, dfnum, best)
+			if semi[u.ID] == semi[v.ID] {
+				idom[v.ID] = w // true dominator
+			} else {
+				samedom[v.ID] = u // v has same dominator as u
+			}
+		}
+
+		p := parent[w.ID]
+		s := p // semidominator
+
+		var sp *Block
+		// calculate the semidominator of w
+		for _, v := range w.Preds {
+			if dfnum[v.ID] == notFound {
+				// skip unreachable predecessor
+				continue
+			}
+
+			if dfnum[v.ID] <= dfnum[w.ID] {
+				sp = v
+			} else {
+				sp = semi[eval(v, ancestor, semi, dfnum, best).ID]
+			}
+
+			if dfnum[sp.ID] < dfnum[s.ID] {
+				s = sp
+			}
+		}
+
+		// link
+		ancestor[w.ID] = p
+		best[w.ID] = w
+
+		semi[w.ID] = s
+		if semi[s.ID] != parent[s.ID] {
+			bucket[w.ID] = bucket[s.ID]
+			bucket[s.ID] = w
+		}
+	}
+
+	// Final pass of step 3
+	for v := bucket[0]; v != nil; v = bucket[v.ID] {
+		idom[v.ID] = bucket[0]
+	}
+
+	// Step 4. Explictly define the immediate dominator of each vertex,
+	// carrying out the computation vertex by vertex in increasing order by
+	// number.
+	for i := 1; i < maxBlockID-1; i++ {
+		w := vertex[i]
+		if w == nil {
+			continue
+		}
+		// w has the same dominator as samedom[w.ID]
+		if samedom[w.ID] != nil {
+			idom[w.ID] = idom[samedom[w.ID].ID]
+		}
+	}
+	return idom
+}
+
+// eval function from LT paper with path compression
+func eval(v *Block, ancestor []*Block, semi []*Block, dfnum []int, best []*Block) *Block {
+	a := ancestor[v.ID]
+	if ancestor[a.ID] != nil {
+		b := eval(a, ancestor, semi, dfnum, best)
+		ancestor[v.ID] = ancestor[a.ID]
+		if dfnum[semi[b.ID].ID] < dfnum[semi[best[v.ID].ID].ID] {
+			best[v.ID] = b
+		}
+	}
+	return best[v.ID]
+}
+
+// dominators computes the dominator tree for f.  It returns a slice
+// which maps block ID to the immediate dominator of that block.
+// Unreachable blocks map to nil.  The entry block maps to nil.
+func dominatorsSimple(f *Func) []*Block {
 	// A simple algorithm for now
 	// Cooper, Harvey, Kennedy
 	idom := make([]*Block, f.NumBlocks())
diff --git a/src/cmd/compile/internal/ssa/dom_test.go b/src/cmd/compile/internal/ssa/dom_test.go
index 3197a5cc0e..5209e307b7 100644
--- a/src/cmd/compile/internal/ssa/dom_test.go
+++ b/src/cmd/compile/internal/ssa/dom_test.go
@@ -4,9 +4,7 @@
 
 package ssa
 
-import (
-	"testing"
-)
+import "testing"
 
 func BenchmarkDominatorsLinear(b *testing.B)     { benchmarkDominators(b, 10000, genLinear) }
 func BenchmarkDominatorsFwdBack(b *testing.B)    { benchmarkDominators(b, 10000, genFwdBack) }
@@ -173,20 +171,24 @@ func benchmarkDominators(b *testing.B, size int, bg blockGen) {
 	}
 }
 
-func verifyDominators(t *testing.T, f fun, doms map[string]string) {
+type domFunc func(f *Func) []*Block
+
+// verifyDominators verifies that the dominators of fut (function under test)
+// as determined by domFn, match the map node->dominator
+func verifyDominators(t *testing.T, fut fun, domFn domFunc, doms map[string]string) {
 	blockNames := map[*Block]string{}
-	for n, b := range f.blocks {
+	for n, b := range fut.blocks {
 		blockNames[b] = n
 	}
 
-	calcDom := dominators(f.f)
+	calcDom := domFn(fut.f)
 
 	for n, d := range doms {
-		nblk, ok := f.blocks[n]
+		nblk, ok := fut.blocks[n]
 		if !ok {
 			t.Errorf("invalid block name %s", n)
 		}
-		dblk, ok := f.blocks[d]
+		dblk, ok := fut.blocks[d]
 		if !ok {
 			t.Errorf("invalid block name %s", d)
 		}
@@ -208,7 +210,7 @@ func verifyDominators(t *testing.T, f fun, doms map[string]string) {
 		if d == nil {
 			continue
 		}
-		for _, b := range f.blocks {
+		for _, b := range fut.blocks {
 			if int(b.ID) == id {
 				t.Errorf("unexpected dominator of %s for %s", blockNames[d], blockNames[b])
 			}
@@ -217,6 +219,21 @@ func verifyDominators(t *testing.T, f fun, doms map[string]string) {
 
 }
 
+func TestDominatorsSingleBlock(t *testing.T) {
+	c := NewConfig("amd64", DummyFrontend{t})
+	fun := Fun(c, "entry",
+		Bloc("entry",
+			Valu("mem", OpArg, TypeMem, 0, ".mem"),
+			Exit("mem")))
+
+	doms := map[string]string{}
+
+	CheckFunc(fun.f)
+	verifyDominators(t, fun, dominators, doms)
+	verifyDominators(t, fun, dominatorsSimple, doms)
+
+}
+
 func TestDominatorsSimple(t *testing.T) {
 	c := NewConfig("amd64", DummyFrontend{t})
 	fun := Fun(c, "entry",
@@ -239,7 +256,9 @@ func TestDominatorsSimple(t *testing.T) {
 		"exit": "c",
 	}
 
-	verifyDominators(t, fun, doms)
+	CheckFunc(fun.f)
+	verifyDominators(t, fun, dominators, doms)
+	verifyDominators(t, fun, dominatorsSimple, doms)
 
 }
 
@@ -266,8 +285,32 @@ func TestDominatorsMultPredFwd(t *testing.T) {
 		"exit": "c",
 	}
 
-	verifyDominators(t, fun, doms)
+	CheckFunc(fun.f)
+	verifyDominators(t, fun, dominators, doms)
+	verifyDominators(t, fun, dominatorsSimple, doms)
+}
 
+func TestDominatorsDeadCode(t *testing.T) {
+	c := NewConfig("amd64", DummyFrontend{t})
+	fun := Fun(c, "entry",
+		Bloc("entry",
+			Valu("mem", OpArg, TypeMem, 0, ".mem"),
+			Valu("p", OpConst, TypeBool, 0, false),
+			If("p", "b3", "b5")),
+		Bloc("b2", Exit("mem")),
+		Bloc("b3", Goto("b2")),
+		Bloc("b4", Goto("b2")),
+		Bloc("b5", Goto("b2")))
+
+	doms := map[string]string{
+		"b2": "entry",
+		"b3": "entry",
+		"b5": "entry",
+	}
+
+	CheckFunc(fun.f)
+	verifyDominators(t, fun, dominators, doms)
+	verifyDominators(t, fun, dominatorsSimple, doms)
 }
 
 func TestDominatorsMultPredRev(t *testing.T) {
@@ -292,7 +335,10 @@ func TestDominatorsMultPredRev(t *testing.T) {
 		"c":    "b",
 		"exit": "c",
 	}
-	verifyDominators(t, fun, doms)
+
+	CheckFunc(fun.f)
+	verifyDominators(t, fun, dominators, doms)
+	verifyDominators(t, fun, dominatorsSimple, doms)
 }
 
 func TestDominatorsMultPred(t *testing.T) {
@@ -317,5 +363,57 @@ func TestDominatorsMultPred(t *testing.T) {
 		"c":    "entry",
 		"exit": "c",
 	}
-	verifyDominators(t, fun, doms)
+
+	CheckFunc(fun.f)
+	verifyDominators(t, fun, dominators, doms)
+	verifyDominators(t, fun, dominatorsSimple, doms)
+}
+
+func TestPostDominators(t *testing.T) {
+	c := NewConfig("amd64", DummyFrontend{t})
+	fun := Fun(c, "entry",
+		Bloc("entry",
+			Valu("mem", OpArg, TypeMem, 0, ".mem"),
+			Valu("p", OpConst, TypeBool, 0, true),
+			If("p", "a", "c")),
+		Bloc("a",
+			If("p", "b", "c")),
+		Bloc("b",
+			Goto("c")),
+		Bloc("c",
+			If("p", "b", "exit")),
+		Bloc("exit",
+			Exit("mem")))
+
+	doms := map[string]string{"entry": "c",
+		"a": "c",
+		"b": "c",
+		"c": "exit",
+	}
+
+	CheckFunc(fun.f)
+	verifyDominators(t, fun, postDominators, doms)
+}
+
+func TestInfiniteLoop(t *testing.T) {
+	c := NewConfig("amd64", DummyFrontend{t})
+	// note lack of an exit block
+	fun := Fun(c, "entry",
+		Bloc("entry",
+			Valu("mem", OpArg, TypeMem, 0, ".mem"),
+			Valu("p", OpConst, TypeBool, 0, true),
+			Goto("a")),
+		Bloc("a",
+			Goto("b")),
+		Bloc("b",
+			Goto("a")))
+
+	CheckFunc(fun.f)
+	doms := map[string]string{"a": "entry",
+		"b": "a"}
+	verifyDominators(t, fun, dominators, doms)
+
+	// no exit block, so there are no post-dominators
+	postDoms := map[string]string{}
+	verifyDominators(t, fun, postDominators, postDoms)
 }