cmd/compile: remove redundant calls to cmpstring

The results of cmpstring are reuseable if the second call has the
same arguments and memory.

Note that this gets rid of cmpstring, but we still generate a
redundant </<= test and branch afterwards, because the compiler
doesn't know that cmpstring only ever returns -1,0,1.

Update #61725

Change-Id: I93a0d1ccca50d90b1e1a888240ffb75a3b10b59b
Reviewed-on: https://go-review.googlesource.com/c/go/+/578835
Reviewed-by: David Chase <drchase@google.com>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Reviewed-by: Cherry Mui <cherryyz@google.com>

4 files changed, 74 insertions, 5 deletions

diff --git a/src/cmd/compile/internal/ssa/_gen/generic.rules b/src/cmd/compile/internal/ssa/_gen/generic.rules
index 4c475d31e00..398601e81b4 100644
--- a/src/cmd/compile/internal/ssa/_gen/generic.rules
+++ b/src/cmd/compile/internal/ssa/_gen/generic.rules
@@ -2794,3 +2794,12 @@
 (Load <t> (OffPtr [off]              (Convert (Addr {sym} _) _)    ) _) && t.IsInteger() && t.Size() == 4 && isFixed32(config, sym, off) => (Const32 [fixed32(config, sym, off)])
 (Load <t> (OffPtr [off] (ITab (IMake          (Addr {sym} _)    _))) _) && t.IsInteger() && t.Size() == 4 && isFixed32(config, sym, off) => (Const32 [fixed32(config, sym, off)])
 (Load <t> (OffPtr [off] (ITab (IMake (Convert (Addr {sym} _) _) _))) _) && t.IsInteger() && t.Size() == 4 && isFixed32(config, sym, off) => (Const32 [fixed32(config, sym, off)])
+
+// Calling cmpstring a second time with the same arguments in the
+// same memory state can reuse the results of the first call.
+// See issue 61725.
+// Note that this could pretty easily generalize to any pure function.
+(StaticLECall {f} x y m:(SelectN [1] c:(StaticLECall {g} x y mem)))
+  && isSameCall(f, "runtime.cmpstring")
+  && isSameCall(g, "runtime.cmpstring")
+=> (MakeResult (SelectN [0] <typ.Int> c) m)
diff --git a/src/cmd/compile/internal/ssa/rewritegeneric.go b/src/cmd/compile/internal/ssa/rewritegeneric.go
index 468e9fa9c61..98c94bc1ba3 100644
--- a/src/cmd/compile/internal/ssa/rewritegeneric.go
+++ b/src/cmd/compile/internal/ssa/rewritegeneric.go
@@ -29311,6 +29311,36 @@ func rewriteValuegeneric_OpStaticLECall(v *Value) bool {
 		v.AddArg2(v0, mem)
 		return true
 	}
+	// match: (StaticLECall {f} x y m:(SelectN [1] c:(StaticLECall {g} x y mem)))
+	// cond: isSameCall(f, "runtime.cmpstring") && isSameCall(g, "runtime.cmpstring")
+	// result: (MakeResult (SelectN [0] <typ.Int> c) m)
+	for {
+		if len(v.Args) != 3 {
+			break
+		}
+		f := auxToCall(v.Aux)
+		_ = v.Args[2]
+		x := v.Args[0]
+		y := v.Args[1]
+		m := v.Args[2]
+		if m.Op != OpSelectN || auxIntToInt64(m.AuxInt) != 1 {
+			break
+		}
+		c := m.Args[0]
+		if c.Op != OpStaticLECall || len(c.Args) != 3 {
+			break
+		}
+		g := auxToCall(c.Aux)
+		if x != c.Args[0] || y != c.Args[1] || !(isSameCall(f, "runtime.cmpstring") && isSameCall(g, "runtime.cmpstring")) {
+			break
+		}
+		v.reset(OpMakeResult)
+		v0 := b.NewValue0(v.Pos, OpSelectN, typ.Int)
+		v0.AuxInt = int64ToAuxInt(0)
+		v0.AddArg(c)
+		v.AddArg2(v0, m)
+		return true
+	}
 	return false
 }
 func rewriteValuegeneric_OpStore(v *Value) bool {
diff --git a/src/cmp/cmp.go b/src/cmp/cmp.go
index 4d1af6a98c4..a13834c3985 100644
--- a/src/cmp/cmp.go
+++ b/src/cmp/cmp.go
@@ -40,13 +40,19 @@ func Less[T Ordered](x, y T) bool {
 func Compare[T Ordered](x, y T) int {
 	xNaN := isNaN(x)
 	yNaN := isNaN(y)
-	if xNaN && yNaN {
-		return 0
+	if xNaN {
+		if yNaN {
+			return 0
+		}
+		return -1
+	}
+	if yNaN {
+		return +1
 	}
-	if xNaN || x < y {
+	if x < y {
 		return -1
 	}
-	if yNaN || x > y {
+	if x > y {
 		return +1
 	}
 	return 0
diff --git a/test/codegen/comparisons.go b/test/codegen/comparisons.go
index 4edf9303dfd..e585045aa47 100644
--- a/test/codegen/comparisons.go
+++ b/test/codegen/comparisons.go
@@ -6,7 +6,10 @@
 
 package codegen
 
-import "unsafe"
+import (
+	"cmp"
+	"unsafe"
+)
 
 // This file contains code generation tests related to the comparison
 // operators.
@@ -801,3 +804,24 @@ func invertLessThanNoov(p1, p2, p3 Point) bool {
 	// arm64:`CMP`,`CSET`,`CSEL`
 	return (p1.X-p3.X)*(p2.Y-p3.Y)-(p2.X-p3.X)*(p1.Y-p3.Y) < 0
 }
+
+func cmpstring1(x, y string) int {
+	// amd64:".*cmpstring"
+	if x < y {
+		return -1
+	}
+	// amd64:-".*cmpstring"
+	if x > y {
+		return +1
+	}
+	return 0
+}
+func cmpstring2(x, y string) int {
+	// We want to fail if there are two calls to cmpstring.
+	// They will both have the same line number, so a test
+	// like in cmpstring1 will not work. Instead, we
+	// look for spill/restore instructions, which only
+	// need to exist if there are 2 calls.
+	//amd64:-`MOVQ\t.*\(SP\)`
+	return cmp.Compare(x, y)
+}