cmd/compile: use loops to handle commutative ops in rules

Prior to this change, we generated additional rules at rulegen time
for all possible combinations of args to commutative ops.
This is simple and works well, but leads to lots of generated rules.
This in turn has increased the size of the compiler,
made it hard to compile package ssa on small machines,
and provided a disincentive to mark some ops as commutative.

This change reworks how we handle commutative ops.
Instead of generating a rule per argument permutation,
we generate a series of nested loops, one for each commutative op.
Each loop tries both possible argument orderings.

I also considered attempting to canonicalize the inputs to the
rewrite rules. However, because either or both arguments might be
nothing more than an identifier, and because there can be arbitrary
conditions to evaluate during matching, I did not see how to proceed.

The duplicate rule detection now sorts arguments to commutative ops,
so that it can detect commutative-only duplicates.

There may be further optimizations to the new generated code.
In particular, we may not be removing as many bounds checks as before;
I have not investigated deeply. If more work here is needed,
we could do it with more hints or with improvements to the prove pass.

This change has almost no impact on the generated code.
It does not pass toolstash-check, however. In a handful of functions,
for reasons I do not understand, there are minor position changes.

For the entire series ending at this change,
there is negligible compiler performance impact.

The compiler binary shrinks by about 15%,
and package ssa shrinks by about 25%.
Package ssa also compiles ~25% faster with ~25% less memory.

Change-Id: Ia2ee9ceae7be08a17342319d4e31b0bb238a2ee4
Reviewed-on: https://go-review.googlesource.com/c/go/+/213703
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>

1 files changed, 3 insertions, 3 deletions

diff --git a/src/cmd/compile/internal/ssa/rewritedec.go b/src/cmd/compile/internal/ssa/rewritedec.go
index ca29f1cf17..d6624b1083 100644
--- a/src/cmd/compile/internal/ssa/rewritedec.go
+++ b/src/cmd/compile/internal/ssa/rewritedec.go
@@ -33,7 +33,7 @@ func rewriteValuedec(v *Value) bool {
 	return false
 }
 func rewriteValuedec_OpComplexImag_0(v *Value) bool {
-	// match: (ComplexImag (ComplexMake _ imag))
+	// match: (ComplexImag (ComplexMake _ imag ))
 	// result: imag
 	for {
 		v_0 := v.Args[0]
@@ -49,7 +49,7 @@ func rewriteValuedec_OpComplexImag_0(v *Value) bool {
 	return false
 }
 func rewriteValuedec_OpComplexReal_0(v *Value) bool {
-	// match: (ComplexReal (ComplexMake real _))
+	// match: (ComplexReal (ComplexMake real _ ))
 	// result: real
 	for {
 		v_0 := v.Args[0]
@@ -265,7 +265,7 @@ func rewriteValuedec_OpSliceLen_0(v *Value) bool {
 	return false
 }
 func rewriteValuedec_OpSlicePtr_0(v *Value) bool {
-	// match: (SlicePtr (SliceMake ptr _ _))
+	// match: (SlicePtr (SliceMake ptr _ _ ))
 	// result: ptr
 	for {
 		v_0 := v.Args[0]