cmd/compile: generate commutative rules when a condition is present

The commutative rule generator has an optimization
where given (Add x y) with no other uses of x and y in the matching rule,
it doesn't generate the commutative match (Add y x).

However, if there is also a condition referring to x or y,
such as (Add x y) && isFoo(x), then we should generate the commutative rule.
This change parses the condition, extracts all idents, and takes them
into consideration.

This doesn't yield any new optimizations now.
However, it is the right thing to do;
otherwise we'll have to track it down and fix it again later.

It is also expensive now, in terms of additional generated code.
However, it will be much, much less expensive soon,
once our generated code for commutative ops gets smaller.

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

1 files changed, 285 insertions, 10 deletions

diff --git a/src/cmd/compile/internal/ssa/rewrite386.go b/src/cmd/compile/internal/ssa/rewrite386.go
index d1ea5c5a4d..dba61cf347 100644
--- a/src/cmd/compile/internal/ssa/rewrite386.go
+++ b/src/cmd/compile/internal/ssa/rewrite386.go
@@ -165,7 +165,7 @@ func rewriteValue386(v *Value) bool {
 	case Op386MOVWloadidx2:
 		return rewriteValue386_Op386MOVWloadidx2_0(v)
 	case Op386MOVWstore:
-		return rewriteValue386_Op386MOVWstore_0(v)
+		return rewriteValue386_Op386MOVWstore_0(v) || rewriteValue386_Op386MOVWstore_10(v)
 	case Op386MOVWstoreconst:
 		return rewriteValue386_Op386MOVWstoreconst_0(v)
 	case Op386MOVWstoreconstidx1:
@@ -4015,6 +4015,28 @@ func rewriteValue386_Op386LEAL_0(v *Value) bool {
 		v.AddArg(y)
 		return true
 	}
+	// match: (LEAL [c] {s} (ADDL y x))
+	// cond: x.Op != OpSB && y.Op != OpSB
+	// result: (LEAL1 [c] {s} x y)
+	for {
+		c := v.AuxInt
+		s := v.Aux
+		v_0 := v.Args[0]
+		if v_0.Op != Op386ADDL {
+			break
+		}
+		x := v_0.Args[1]
+		y := v_0.Args[0]
+		if !(x.Op != OpSB && y.Op != OpSB) {
+			break
+		}
+		v.reset(Op386LEAL1)
+		v.AuxInt = c
+		v.Aux = s
+		v.AddArg(x)
+		v.AddArg(y)
+		return true
+	}
 	// match: (LEAL [off1] {sym1} (LEAL [off2] {sym2} x))
 	// cond: is32Bit(off1+off2) && canMergeSym(sym1, sym2)
 	// result: (LEAL [off1+off2] {mergeSym(sym1,sym2)} x)
@@ -4918,6 +4940,30 @@ func rewriteValue386_Op386MOVBload_0(v *Value) bool {
 		v.AddArg(mem)
 		return true
 	}
+	// match: (MOVBload [off] {sym} (ADDL idx ptr) mem)
+	// cond: ptr.Op != OpSB
+	// result: (MOVBloadidx1 [off] {sym} ptr idx mem)
+	for {
+		off := v.AuxInt
+		sym := v.Aux
+		mem := v.Args[1]
+		v_0 := v.Args[0]
+		if v_0.Op != Op386ADDL {
+			break
+		}
+		ptr := v_0.Args[1]
+		idx := v_0.Args[0]
+		if !(ptr.Op != OpSB) {
+			break
+		}
+		v.reset(Op386MOVBloadidx1)
+		v.AuxInt = off
+		v.Aux = sym
+		v.AddArg(ptr)
+		v.AddArg(idx)
+		v.AddArg(mem)
+		return true
+	}
 	// match: (MOVBload [off] {sym} (SB) _)
 	// cond: symIsRO(sym)
 	// result: (MOVLconst [int64(read8(sym, off))])
@@ -5193,6 +5239,32 @@ func rewriteValue386_Op386MOVBstore_0(v *Value) bool {
 		v.AddArg(mem)
 		return true
 	}
+	// match: (MOVBstore [off] {sym} (ADDL idx ptr) val mem)
+	// cond: ptr.Op != OpSB
+	// result: (MOVBstoreidx1 [off] {sym} ptr idx val mem)
+	for {
+		off := v.AuxInt
+		sym := v.Aux
+		mem := v.Args[2]
+		v_0 := v.Args[0]
+		if v_0.Op != Op386ADDL {
+			break
+		}
+		ptr := v_0.Args[1]
+		idx := v_0.Args[0]
+		val := v.Args[1]
+		if !(ptr.Op != OpSB) {
+			break
+		}
+		v.reset(Op386MOVBstoreidx1)
+		v.AuxInt = off
+		v.Aux = sym
+		v.AddArg(ptr)
+		v.AddArg(idx)
+		v.AddArg(val)
+		v.AddArg(mem)
+		return true
+	}
 	// match: (MOVBstore [i] {s} p (SHRWconst [8] w) x:(MOVBstore [i-1] {s} p w mem))
 	// cond: x.Uses == 1 && clobber(x)
 	// result: (MOVWstore [i-1] {s} p w mem)
@@ -5251,6 +5323,9 @@ func rewriteValue386_Op386MOVBstore_0(v *Value) bool {
 		v.AddArg(mem)
 		return true
 	}
+	return false
+}
+func rewriteValue386_Op386MOVBstore_10(v *Value) bool {
 	// match: (MOVBstore [i] {s} p w x:(MOVBstore {s} [i+1] p (SHRWconst [8] w) mem))
 	// cond: x.Uses == 1 && clobber(x)
 	// result: (MOVWstore [i] {s} p w mem)
@@ -5280,9 +5355,6 @@ func rewriteValue386_Op386MOVBstore_0(v *Value) bool {
 		v.AddArg(mem)
 		return true
 	}
-	return false
-}
-func rewriteValue386_Op386MOVBstore_10(v *Value) bool {
 	// match: (MOVBstore [i] {s} p w x:(MOVBstore {s} [i+1] p (SHRLconst [8] w) mem))
 	// cond: x.Uses == 1 && clobber(x)
 	// result: (MOVWstore [i] {s} p w mem)
@@ -6466,6 +6538,30 @@ func rewriteValue386_Op386MOVLload_0(v *Value) bool {
 		v.AddArg(mem)
 		return true
 	}
+	// match: (MOVLload [off] {sym} (ADDL idx ptr) mem)
+	// cond: ptr.Op != OpSB
+	// result: (MOVLloadidx1 [off] {sym} ptr idx mem)
+	for {
+		off := v.AuxInt
+		sym := v.Aux
+		mem := v.Args[1]
+		v_0 := v.Args[0]
+		if v_0.Op != Op386ADDL {
+			break
+		}
+		ptr := v_0.Args[1]
+		idx := v_0.Args[0]
+		if !(ptr.Op != OpSB) {
+			break
+		}
+		v.reset(Op386MOVLloadidx1)
+		v.AuxInt = off
+		v.Aux = sym
+		v.AddArg(ptr)
+		v.AddArg(idx)
+		v.AddArg(mem)
+		return true
+	}
 	// match: (MOVLload [off] {sym} (SB) _)
 	// cond: symIsRO(sym)
 	// result: (MOVLconst [int64(int32(read32(sym, off, config.BigEndian)))])
@@ -6814,6 +6910,32 @@ func rewriteValue386_Op386MOVLstore_0(v *Value) bool {
 		v.AddArg(mem)
 		return true
 	}
+	// match: (MOVLstore [off] {sym} (ADDL idx ptr) val mem)
+	// cond: ptr.Op != OpSB
+	// result: (MOVLstoreidx1 [off] {sym} ptr idx val mem)
+	for {
+		off := v.AuxInt
+		sym := v.Aux
+		mem := v.Args[2]
+		v_0 := v.Args[0]
+		if v_0.Op != Op386ADDL {
+			break
+		}
+		ptr := v_0.Args[1]
+		idx := v_0.Args[0]
+		val := v.Args[1]
+		if !(ptr.Op != OpSB) {
+			break
+		}
+		v.reset(Op386MOVLstoreidx1)
+		v.AuxInt = off
+		v.Aux = sym
+		v.AddArg(ptr)
+		v.AddArg(idx)
+		v.AddArg(val)
+		v.AddArg(mem)
+		return true
+	}
 	// match: (MOVLstore {sym} [off] ptr y:(ADDLload x [off] {sym} ptr mem) mem)
 	// cond: y.Uses==1 && clobber(y)
 	// result: (ADDLmodify [off] {sym} ptr x mem)
@@ -6889,6 +7011,9 @@ func rewriteValue386_Op386MOVLstore_0(v *Value) bool {
 		v.AddArg(mem)
 		return true
 	}
+	return false
+}
+func rewriteValue386_Op386MOVLstore_10(v *Value) bool {
 	// match: (MOVLstore {sym} [off] ptr y:(XORLload x [off] {sym} ptr mem) mem)
 	// cond: y.Uses==1 && clobber(y)
 	// result: (XORLmodify [off] {sym} ptr x mem)
@@ -6914,9 +7039,6 @@ func rewriteValue386_Op386MOVLstore_0(v *Value) bool {
 		v.AddArg(mem)
 		return true
 	}
-	return false
-}
-func rewriteValue386_Op386MOVLstore_10(v *Value) bool {
 	// match: (MOVLstore {sym} [off] ptr y:(ADDL l:(MOVLload [off] {sym} ptr mem) x) mem)
 	// cond: y.Uses==1 && l.Uses==1 && clobber(y) && clobber(l)
 	// result: (ADDLmodify [off] {sym} ptr x mem)
@@ -7182,6 +7304,9 @@ func rewriteValue386_Op386MOVLstore_10(v *Value) bool {
 		v.AddArg(mem)
 		return true
 	}
+	return false
+}
+func rewriteValue386_Op386MOVLstore_20(v *Value) bool {
 	// match: (MOVLstore {sym} [off] ptr y:(ADDLconst [c] l:(MOVLload [off] {sym} ptr mem)) mem)
 	// cond: y.Uses==1 && l.Uses==1 && clobber(y) && clobber(l) && validValAndOff(c,off)
 	// result: (ADDLconstmodify [makeValAndOff(c,off)] {sym} ptr mem)
@@ -7210,9 +7335,6 @@ func rewriteValue386_Op386MOVLstore_10(v *Value) bool {
 		v.AddArg(mem)
 		return true
 	}
-	return false
-}
-func rewriteValue386_Op386MOVLstore_20(v *Value) bool {
 	// match: (MOVLstore {sym} [off] ptr y:(ANDLconst [c] l:(MOVLload [off] {sym} ptr mem)) mem)
 	// cond: y.Uses==1 && l.Uses==1 && clobber(y) && clobber(l) && validValAndOff(c,off)
 	// result: (ANDLconstmodify [makeValAndOff(c,off)] {sym} ptr mem)
@@ -8381,6 +8503,30 @@ func rewriteValue386_Op386MOVSDload_0(v *Value) bool {
 		v.AddArg(mem)
 		return true
 	}
+	// match: (MOVSDload [off] {sym} (ADDL idx ptr) mem)
+	// cond: ptr.Op != OpSB
+	// result: (MOVSDloadidx1 [off] {sym} ptr idx mem)
+	for {
+		off := v.AuxInt
+		sym := v.Aux
+		mem := v.Args[1]
+		v_0 := v.Args[0]
+		if v_0.Op != Op386ADDL {
+			break
+		}
+		ptr := v_0.Args[1]
+		idx := v_0.Args[0]
+		if !(ptr.Op != OpSB) {
+			break
+		}
+		v.reset(Op386MOVSDloadidx1)
+		v.AuxInt = off
+		v.Aux = sym
+		v.AddArg(ptr)
+		v.AddArg(idx)
+		v.AddArg(mem)
+		return true
+	}
 	return false
 }
 func rewriteValue386_Op386MOVSDloadidx1_0(v *Value) bool {
@@ -8609,6 +8755,32 @@ func rewriteValue386_Op386MOVSDstore_0(v *Value) bool {
 		v.AddArg(mem)
 		return true
 	}
+	// match: (MOVSDstore [off] {sym} (ADDL idx ptr) val mem)
+	// cond: ptr.Op != OpSB
+	// result: (MOVSDstoreidx1 [off] {sym} ptr idx val mem)
+	for {
+		off := v.AuxInt
+		sym := v.Aux
+		mem := v.Args[2]
+		v_0 := v.Args[0]
+		if v_0.Op != Op386ADDL {
+			break
+		}
+		ptr := v_0.Args[1]
+		idx := v_0.Args[0]
+		val := v.Args[1]
+		if !(ptr.Op != OpSB) {
+			break
+		}
+		v.reset(Op386MOVSDstoreidx1)
+		v.AuxInt = off
+		v.Aux = sym
+		v.AddArg(ptr)
+		v.AddArg(idx)
+		v.AddArg(val)
+		v.AddArg(mem)
+		return true
+	}
 	return false
 }
 func rewriteValue386_Op386MOVSDstoreidx1_0(v *Value) bool {
@@ -8855,6 +9027,30 @@ func rewriteValue386_Op386MOVSSload_0(v *Value) bool {
 		v.AddArg(mem)
 		return true
 	}
+	// match: (MOVSSload [off] {sym} (ADDL idx ptr) mem)
+	// cond: ptr.Op != OpSB
+	// result: (MOVSSloadidx1 [off] {sym} ptr idx mem)
+	for {
+		off := v.AuxInt
+		sym := v.Aux
+		mem := v.Args[1]
+		v_0 := v.Args[0]
+		if v_0.Op != Op386ADDL {
+			break
+		}
+		ptr := v_0.Args[1]
+		idx := v_0.Args[0]
+		if !(ptr.Op != OpSB) {
+			break
+		}
+		v.reset(Op386MOVSSloadidx1)
+		v.AuxInt = off
+		v.Aux = sym
+		v.AddArg(ptr)
+		v.AddArg(idx)
+		v.AddArg(mem)
+		return true
+	}
 	return false
 }
 func rewriteValue386_Op386MOVSSloadidx1_0(v *Value) bool {
@@ -9083,6 +9279,32 @@ func rewriteValue386_Op386MOVSSstore_0(v *Value) bool {
 		v.AddArg(mem)
 		return true
 	}
+	// match: (MOVSSstore [off] {sym} (ADDL idx ptr) val mem)
+	// cond: ptr.Op != OpSB
+	// result: (MOVSSstoreidx1 [off] {sym} ptr idx val mem)
+	for {
+		off := v.AuxInt
+		sym := v.Aux
+		mem := v.Args[2]
+		v_0 := v.Args[0]
+		if v_0.Op != Op386ADDL {
+			break
+		}
+		ptr := v_0.Args[1]
+		idx := v_0.Args[0]
+		val := v.Args[1]
+		if !(ptr.Op != OpSB) {
+			break
+		}
+		v.reset(Op386MOVSSstoreidx1)
+		v.AuxInt = off
+		v.Aux = sym
+		v.AddArg(ptr)
+		v.AddArg(idx)
+		v.AddArg(val)
+		v.AddArg(mem)
+		return true
+	}
 	return false
 }
 func rewriteValue386_Op386MOVSSstoreidx1_0(v *Value) bool {
@@ -9530,6 +9752,30 @@ func rewriteValue386_Op386MOVWload_0(v *Value) bool {
 		v.AddArg(mem)
 		return true
 	}
+	// match: (MOVWload [off] {sym} (ADDL idx ptr) mem)
+	// cond: ptr.Op != OpSB
+	// result: (MOVWloadidx1 [off] {sym} ptr idx mem)
+	for {
+		off := v.AuxInt
+		sym := v.Aux
+		mem := v.Args[1]
+		v_0 := v.Args[0]
+		if v_0.Op != Op386ADDL {
+			break
+		}
+		ptr := v_0.Args[1]
+		idx := v_0.Args[0]
+		if !(ptr.Op != OpSB) {
+			break
+		}
+		v.reset(Op386MOVWloadidx1)
+		v.AuxInt = off
+		v.Aux = sym
+		v.AddArg(ptr)
+		v.AddArg(idx)
+		v.AddArg(mem)
+		return true
+	}
 	// match: (MOVWload [off] {sym} (SB) _)
 	// cond: symIsRO(sym)
 	// result: (MOVLconst [int64(read16(sym, off, config.BigEndian))])
@@ -9918,6 +10164,32 @@ func rewriteValue386_Op386MOVWstore_0(v *Value) bool {
 		v.AddArg(mem)
 		return true
 	}
+	// match: (MOVWstore [off] {sym} (ADDL idx ptr) val mem)
+	// cond: ptr.Op != OpSB
+	// result: (MOVWstoreidx1 [off] {sym} ptr idx val mem)
+	for {
+		off := v.AuxInt
+		sym := v.Aux
+		mem := v.Args[2]
+		v_0 := v.Args[0]
+		if v_0.Op != Op386ADDL {
+			break
+		}
+		ptr := v_0.Args[1]
+		idx := v_0.Args[0]
+		val := v.Args[1]
+		if !(ptr.Op != OpSB) {
+			break
+		}
+		v.reset(Op386MOVWstoreidx1)
+		v.AuxInt = off
+		v.Aux = sym
+		v.AddArg(ptr)
+		v.AddArg(idx)
+		v.AddArg(val)
+		v.AddArg(mem)
+		return true
+	}
 	// match: (MOVWstore [i] {s} p (SHRLconst [16] w) x:(MOVWstore [i-2] {s} p w mem))
 	// cond: x.Uses == 1 && clobber(x)
 	// result: (MOVLstore [i-2] {s} p w mem)
@@ -9947,6 +10219,9 @@ func rewriteValue386_Op386MOVWstore_0(v *Value) bool {
 		v.AddArg(mem)
 		return true
 	}
+	return false
+}
+func rewriteValue386_Op386MOVWstore_10(v *Value) bool {
 	// match: (MOVWstore [i] {s} p (SHRLconst [j] w) x:(MOVWstore [i-2] {s} p w0:(SHRLconst [j-16] w) mem))
 	// cond: x.Uses == 1 && clobber(x)
 	// result: (MOVLstore [i-2] {s} p w0 mem)