From 75198b9a9ccdacc3e9ed87a2406b0b87acb1fbac Mon Sep 17 00:00:00 2001 From: Josh Bleecher Snyder Date: Fri, 17 May 2019 11:48:37 -0700 Subject: [PATCH] cmd/compile: simplify postorder Use a bool instead of markKind; it doesn't save space, but the semantics are more obvious. Move type markKind closer to its only remaining use. Change-Id: I9945a7baaeb764295a2709f83120ce3a82fa3beb Reviewed-on: https://go-review.googlesource.com/c/go/+/177880 Run-TryBot: Josh Bleecher Snyder TryBot-Result: Gobot Gobot Reviewed-by: David Chase --- src/cmd/compile/internal/ssa/dom.go | 33 +++++++------------ .../compile/internal/ssa/loopreschedchecks.go | 10 ++++++ 2 files changed, 21 insertions(+), 22 deletions(-) diff --git a/src/cmd/compile/internal/ssa/dom.go b/src/cmd/compile/internal/ssa/dom.go index 3d186fc562..f31e7df724 100644 --- a/src/cmd/compile/internal/ssa/dom.go +++ b/src/cmd/compile/internal/ssa/dom.go @@ -4,16 +4,6 @@ package ssa -// mark values -type markKind uint8 - -const ( - notFound markKind = 0 // block has not been discovered yet - notExplored markKind = 1 // discovered and in queue, outedges not processed yet - explored markKind = 2 // discovered and in queue, outedges processed - done markKind = 3 // all done, in output ordering -) - // This file contains code to compute the dominator tree // of a control-flow graph. @@ -31,7 +21,7 @@ type blockAndIndex struct { // postorderWithNumbering provides a DFS postordering. // This seems to make loop-finding more robust. func postorderWithNumbering(f *Func, ponums []int32) []*Block { - mark := make([]markKind, f.NumBlocks()) + seen := make([]bool, f.NumBlocks()) // result ordering order := make([]*Block, 0, len(f.Blocks)) @@ -41,26 +31,25 @@ func postorderWithNumbering(f *Func, ponums []int32) []*Block { // enough to cover almost every postorderWithNumbering call. s := make([]blockAndIndex, 0, 32) s = append(s, blockAndIndex{b: f.Entry}) - mark[f.Entry.ID] = explored + seen[f.Entry.ID] = true for len(s) > 0 { tos := len(s) - 1 x := s[tos] b := x.b - i := x.index - if i < len(b.Succs) { + if i := x.index; i < len(b.Succs) { s[tos].index++ bb := b.Succs[i].Block() - if mark[bb.ID] == notFound { - mark[bb.ID] = explored + if !seen[bb.ID] { + seen[bb.ID] = true s = append(s, blockAndIndex{b: bb}) } - } else { - s = s[:tos] - if len(ponums) > 0 { - ponums[b.ID] = int32(len(order)) - } - order = append(order, b) + continue + } + s = s[:tos] + if ponums != nil { + ponums[b.ID] = int32(len(order)) } + order = append(order, b) } return order } diff --git a/src/cmd/compile/internal/ssa/loopreschedchecks.go b/src/cmd/compile/internal/ssa/loopreschedchecks.go index 30ba1e9d66..1932f9d23a 100644 --- a/src/cmd/compile/internal/ssa/loopreschedchecks.go +++ b/src/cmd/compile/internal/ssa/loopreschedchecks.go @@ -452,6 +452,16 @@ func findLastMems(f *Func) []*Value { return lastMems } +// mark values +type markKind uint8 + +const ( + notFound markKind = iota // block has not been discovered yet + notExplored // discovered and in queue, outedges not processed yet + explored // discovered and in queue, outedges processed + done // all done, in output ordering +) + type backedgesState struct { b *Block i int -- 2.50.0