cmd/compile: optimize sccp for faster convergence

While investigating other optimizations, I found several
opportunities to accelerate sccp convergence:

- Avoid adding duplicate uses to the re-visit worklist
- Prevent queueing uses of values that have already reached the Bottom
- Add an early exit when processing a value that is already Bottom

These changes provide an overall speedup of ~9% for sccp phase
during a full make.bash run. Also they does not change
the number of constants found or the amount of dead code eliminated.

Updates #77325

Change-Id: Iaf83f6ea355eed366c3d09fc38f85561634a5a16
GitHub-Last-Rev: 078c3d309cc1f1e4b7f7a40635ffc4506f2ac1c6
GitHub-Pull-Request: golang/go#77399
Reviewed-on: https://go-review.googlesource.com/c/go/+/740980
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Reviewed-by: David Chase <drchase@google.com>
Reviewed-by: Keith Randall <khr@golang.org>
Reviewed-by: Keith Randall <khr@google.com>
Auto-Submit: Keith Randall <khr@golang.org>

1 files changed, 23 insertions, 7 deletions

diff --git a/src/cmd/compile/internal/ssa/sccp.go b/src/cmd/compile/internal/ssa/sccp.go
index 7ef8d6b7c1..3793e9f86a 100644
--- a/src/cmd/compile/internal/ssa/sccp.go
+++ b/src/cmd/compile/internal/ssa/sccp.go
@@ -50,6 +50,7 @@ type lattice struct {
 type worklist struct {
 	f            *Func               // the target function to be optimized out
 	edges        []Edge              // propagate constant facts through edges
+	inUses       *sparseSet          // IDs already in uses, for duplicate check
 	uses         []*Value            // re-visiting set
 	visited      map[Edge]bool       // visited edges
 	latticeCells map[*Value]lattice  // constant lattices
@@ -71,6 +72,8 @@ func sccp(f *Func) {
 	t.defBlock = make(map[*Value][]*Block)
 	t.latticeCells = make(map[*Value]lattice)
 	t.visitedBlock = f.Cache.allocBoolSlice(f.NumBlocks())
+	t.inUses = f.newSparseSet(f.NumValues())
+	defer f.retSparseSet(t.inUses)
 	defer f.Cache.freeBoolSlice(t.visitedBlock)
 
 	// build it early since we rely heavily on the def-use chain later
@@ -104,6 +107,7 @@ func sccp(f *Func) {
 		if len(t.uses) > 0 {
 			use := t.uses[0]
 			t.uses = t.uses[1:]
+			t.inUses.remove(use.ID)
 			t.visitValue(use)
 			continue
 		}
@@ -251,6 +255,10 @@ func (t *worklist) buildDefUses() {
 			for _, arg := range val.Args {
 				// find its uses, only uses that can become constants take into account
 				if possibleConst(arg) && possibleConst(val) {
+					// Phi may refer to itself as uses, avoid duplicate visits
+					if arg == val {
+						continue
+					}
 					if _, exist := t.defUse[arg]; !exist {
 						t.defUse[arg] = make([]*Value, 0, arg.Uses)
 					}
@@ -270,12 +278,16 @@ func (t *worklist) buildDefUses() {
 // addUses finds all uses of value and appends them into work list for further process
 func (t *worklist) addUses(val *Value) {
 	for _, use := range t.defUse[val] {
-		if val == use {
-			// Phi may refer to itself as uses, ignore them to avoid re-visiting phi
-			// for performance reason
+		// Provenly not a constant, ignore
+		useLt := t.getLatticeCell(use)
+		if useLt.tag == bottom {
 			continue
 		}
-		t.uses = append(t.uses, use)
+		// Avoid duplicate visits
+		if !t.inUses.contains(use.ID) {
+			t.inUses.add(use.ID)
+			t.uses = append(t.uses, use)
+		}
 	}
 	for _, block := range t.defBlock[val] {
 		if t.visitedBlock[block.ID] {
@@ -362,15 +374,19 @@ func computeLattice(f *Func, val *Value, args ...*Value) lattice {
 }
 
 func (t *worklist) visitValue(val *Value) {
+	// Impossible to be a constant, fast fail
 	if !possibleConst(val) {
-		// fast fail for always worst Values, i.e. there is no lowering happen
-		// on them, their lattices must be initially worse Bottom.
 		return
 	}
 
+	// Provenly not a constant, fast fail
 	oldLt := t.getLatticeCell(val)
+	if oldLt.tag == bottom {
+		return
+	}
+
+	// Re-visit all uses of value if its lattice is changed
 	defer func() {
-		// re-visit all uses of value if its lattice is changed
 		newLt := t.getLatticeCell(val)
 		if !equals(newLt, oldLt) {
 			if oldLt.tag > newLt.tag {