diff options
author | David Chase <drchase@google.com> | 2017-04-28 16:48:11 -0400 |
---|---|---|
committer | David Chase <drchase@google.com> | 2017-10-05 18:49:10 +0000 |
commit | 9e21e9c5cb27e5f2b5acba14efb6bb6f126595cc (patch) | |
tree | 51167527a921bf25fe00abf5c2326bc0aa4b01b6 /src/cmd/compile/internal/ssa/likelyadjust.go | |
parent | acdb44765d86a5fd66cbbe24735f7dde658a295f (diff) | |
download | go-9e21e9c5cb27e5f2b5acba14efb6bb6f126595cc.tar.gz go-9e21e9c5cb27e5f2b5acba14efb6bb6f126595cc.zip |
cmd/compile: make loop finder more aware of irreducible loops
The loop finder doesn't return good information if it
encounters an irreducible loop. Make a start on improving
this, and set a function-level flag to indicate when there
is such a loop (and the returned information might be flaky).
Use that flag to prevent the loop rotater from getting
confused; the existing code seems to depend on artifacts
of the previous loop-finding algorithm. (There is one
irreducible loop in the go library, in "inflate.go").
Change-Id: If6e26feab38d9b009d2252d556e1470c803bde40
Reviewed-on: https://go-review.googlesource.com/42150
Run-TryBot: David Chase <drchase@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Cherry Zhang <cherryyz@google.com>
Diffstat (limited to 'src/cmd/compile/internal/ssa/likelyadjust.go')
-rw-r--r-- | src/cmd/compile/internal/ssa/likelyadjust.go | 40 |
1 files changed, 30 insertions, 10 deletions
diff --git a/src/cmd/compile/internal/ssa/likelyadjust.go b/src/cmd/compile/internal/ssa/likelyadjust.go index d15037dd95..5f4c5d1ccd 100644 --- a/src/cmd/compile/internal/ssa/likelyadjust.go +++ b/src/cmd/compile/internal/ssa/likelyadjust.go @@ -12,7 +12,7 @@ type loop struct { header *Block // The header node of this (reducible) loop outer *loop // loop containing this loop - // By default, children exits, and depth are not initialized. + // By default, children, exits, and depth are not initialized. children []*loop // loops nested directly within this loop. Initialized by assembleChildren(). exits []*Block // exits records blocks reached by exits from this loop. Initialized by findExits(). @@ -23,7 +23,7 @@ type loop struct { isInner bool // True if never discovered to contain a loop // register allocation uses this. - containsCall bool // if any block in this loop or any loop it contains has a call + containsCall bool // if any block in this loop or any loop within it contains has a call } // outerinner records that outer contains inner @@ -72,11 +72,12 @@ func (l *loop) checkContainsCall(bb *Block) { } type loopnest struct { - f *Func - b2l []*loop - po []*Block - sdom SparseTree - loops []*loop + f *Func + b2l []*loop + po []*Block + sdom SparseTree + loops []*loop + hasIrreducible bool // TODO current treatment of irreducible loops is very flaky, if accurate loops are needed, must punt at function level. // Record which of the lazily initialized fields have actually been initialized. initializedChildren, initializedDepth, initializedExits bool @@ -285,6 +286,12 @@ func loopnestfor(f *Func) *loopnest { sdom := f.sdom() b2l := make([]*loop, f.NumBlocks()) loops := make([]*loop, 0) + visited := make([]bool, f.NumBlocks()) + sawIrred := false + + if f.pass.debug > 2 { + fmt.Printf("loop finding in %s\n", f.Name) + } // Reducible-loop-nest-finding. for _, b := range po { @@ -318,10 +325,17 @@ func loopnestfor(f *Func) *loopnest { b2l[bb.ID] = l l.checkContainsCall(bb) } - } else { // Perhaps a loop header is inherited. + } else if !visited[bb.ID] { // Found an irreducible loop + sawIrred = true + if f.pass != nil && f.pass.debug > 4 { + fmt.Printf("loop finding succ %s of %s is IRRED, in %s\n", bb.String(), b.String(), f.Name) + } + } else if l != nil { + // TODO handle case where l is irreducible. + // Perhaps a loop header is inherited. // is there any loop containing our successor whose // header dominates b? - if l != nil && !sdom.isAncestorEq(l.header, b) { + if !sdom.isAncestorEq(l.header, b) { l = l.nearestOuterLoop(sdom, b) } if f.pass != nil && f.pass.debug > 4 { @@ -331,6 +345,11 @@ func loopnestfor(f *Func) *loopnest { fmt.Printf("loop finding succ %s of %s provides loop with header %s\n", bb.String(), b.String(), l.header.String()) } } + } else { // No loop + if f.pass != nil && f.pass.debug > 4 { + fmt.Printf("loop finding succ %s of %s has no loop\n", bb.String(), b.String()) + } + } if l == nil || innermost == l { @@ -355,9 +374,10 @@ func loopnestfor(f *Func) *loopnest { innermost.checkContainsCall(b) innermost.nBlocks++ } + visited[b.ID] = true } - ln := &loopnest{f: f, b2l: b2l, po: po, sdom: sdom, loops: loops} + ln := &loopnest{f: f, b2l: b2l, po: po, sdom: sdom, loops: loops, hasIrreducible: sawIrred} // Curious about the loopiness? "-d=ssa/likelyadjust/stats" if f.pass != nil && f.pass.stats > 0 && len(loops) > 0 { |