From 078ba138d370d1752e78c558e795ea9d01d6d1db Mon Sep 17 00:00:00 2001 From: Todd Neal Date: Sun, 5 Jul 2015 18:23:25 -0500 Subject: [PATCH] [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 --- src/cmd/compile/internal/ssa/dom.go | 200 ++++++++++++++++++++++- src/cmd/compile/internal/ssa/dom_test.go | 124 ++++++++++++-- 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) } -- 2.48.1