cmd/compile: statically remove type switch in instantiated generic code

[dsnet]

Using Go1.19

Consider this benchmark, which has three functions:

• lessUTF16 is a generic function that operates on either []byte or string. It relies on a type switch to call either utf8.DecodeRune or utf8.DecodeRuneInString.
• lessUTF16Bytes is identical to lessUTF16 but is manually instantiated for []byte.
• lessUTF16String is identical to lessUTF16 but is manually instantiated for string.

The diff from lessUTF16 to lessUTF16Bytes is:

-		var rx, ry rune
-		var nx, ny int
-		switch any(x).(type) {
-		case string:
-			rx, nx = utf8.DecodeRuneInString(string(x))
-			ry, ny = utf8.DecodeRuneInString(string(y))
-		case []byte:
-			rx, nx = utf8.DecodeRune([]byte(x))
-			ry, ny = utf8.DecodeRune([]byte(y))
-		}
+		rx, nx := utf8.DecodeRune(x)
+		ry, ny := utf8.DecodeRune(y)

Similarly, the diff from lessUTF16 to lessUTF16String is:

-		var rx, ry rune
-		var nx, ny int
-		switch any(x).(type) {
-		case string:
-			rx, nx = utf8.DecodeRuneInString(string(x))
-			ry, ny = utf8.DecodeRuneInString(string(y))
-		case []byte:
-			rx, nx = utf8.DecodeRune([]byte(x))
-			ry, ny = utf8.DecodeRune([]byte(y))
-		}
+		rx, nx := utf8.DecodeRuneInString(x)
+		ry, ny := utf8.DecodeRuneInString(y)

I would expect lessUTF16[[]byte] to perform identically to lessUTF16Bytes and lessUTF16[string] to perform identically to lessUTF16String since the compiler can prove that only one of the cases are possibly executable. However, that is not what the benchmarks show:

BenchmarkString           	 1752459	       686.0 ns/op	       0 B/op	       0 allocs/op
BenchmarkBytes            	 1573508	       765.1 ns/op	       0 B/op	       0 allocs/op
BenchmarkGenericString    	 1595708	       744.2 ns/op	       0 B/op	       0 allocs/op
BenchmarkGenericBytes     	 1527207	       793.7 ns/op	       0 B/op	       0 allocs/op

\cc @randall77

[prattmic]

cc @golang/compiler

[cuonglm]

I think it's not the type switch, but the extra cost comes from the tail call in the wrapper function to the shape version. For example, lessUTF16[string] is roughly compiled to:

func lessUTF16[string](x, y string) bool {
    return lessUTF16[go.shape.string](.dict.lessUTF16[string], x, y)
}

cc @mdempsky

[gopherbot]

Change https://go.dev/cl/767640 mentions this issue: cmd/compile: eliminate impossible type assertions in generic functions

[jakebailey]

I sent CL 767640 which partially addresses this by removing the dead code.

I have not really figured out how to prove the opposite, that a specific case will positively match. It's challenging due to how much stuff is lost during the stenciling process.