diff options
| author | David Chase <drchase@google.com> | 2015-09-06 21:32:24 -0400 |
|---|---|---|
| committer | David Chase <drchase@google.com> | 2015-09-09 23:31:42 +0000 |
| commit | 2a2957656270cf409d11eb2df1d316e97cef2b62 (patch) | |
| tree | e2a098f91b243107d490b5975738388e8b3253f1 /src/cmd/compile/internal/ssa/cse.go | |
| parent | 8a1f6217c57316808e8f23f5f2fa251de3c18a26 (diff) | |
| download | go-2a2957656270cf409d11eb2df1d316e97cef2b62.tar.gz go-2a2957656270cf409d11eb2df1d316e97cef2b62.zip | |
[dev.ssa] cmd/compile: fix N^2 dominator queries in CSE
Added tree numbering data structure.
Changed dominator query in CSE.
Removed skip-for-too-big patch in CSE.
Passes all.bash.
Change-Id: I98d7c61b6015c81f5edab553615db17bc7a58d68
Reviewed-on: https://go-review.googlesource.com/14326
Reviewed-by: Keith Randall <khr@golang.org>
Diffstat (limited to 'src/cmd/compile/internal/ssa/cse.go')
| -rw-r--r-- | src/cmd/compile/internal/ssa/cse.go | 12 |
1 files changed, 4 insertions, 8 deletions
diff --git a/src/cmd/compile/internal/ssa/cse.go b/src/cmd/compile/internal/ssa/cse.go index 003530a9d3..3b007c6192 100644 --- a/src/cmd/compile/internal/ssa/cse.go +++ b/src/cmd/compile/internal/ssa/cse.go @@ -10,11 +10,6 @@ import "sort" // Values are just relinked, nothing is deleted. A subsequent deadcode // pass is required to actually remove duplicate expressions. func cse(f *Func) { - if f.NumBlocks() > 10000 { - f.Unimplementedf("too many blocks: %d", f.NumBlocks()) - return - } - // Two values are equivalent if they satisfy the following definition: // equivalent(v, w): // v.op == w.op @@ -132,6 +127,7 @@ func cse(f *Func) { // Compute dominator tree idom := dominators(f) + sdom := newSparseTree(f, idom) // Compute substitutions we would like to do. We substitute v for w // if v and w are in the same equivalence class and v dominates w. @@ -142,7 +138,7 @@ func cse(f *Func) { // Find a maximal dominant element in e v := e[0] for _, w := range e[1:] { - if dom(w.Block, v.Block, idom) { + if sdom.isAncestorEq(w.Block, v.Block) { v = w } } @@ -152,7 +148,7 @@ func cse(f *Func) { w := e[i] if w == v { e, e[i] = e[:len(e)-1], e[len(e)-1] - } else if dom(v.Block, w.Block, idom) { + } else if sdom.isAncestorEq(v.Block, w.Block) { rewrite[w.ID] = v e, e[i] = e[:len(e)-1], e[len(e)-1] } else { @@ -176,7 +172,7 @@ func cse(f *Func) { } // returns true if b dominates c. -// TODO(khr): faster +// simple and iterative, has O(depth) complexity in tall trees. func dom(b, c *Block, idom []*Block) bool { // Walk up from c in the dominator tree looking for b. for c != nil { |