cmd/compile: optimize switch statements using lookup tables

Switch statement containing integer constant cases and case bodies just
returning a constant should be optimizable to a simpler and faster table
lookup instead of a jump table.

That is, a switch like this:

    switch x {
    case 0: return 10
    case 1: return 20
    case 2: return 30
    case 3: return 40
    default: return -1
    }

Could be optimized to this:

    var table = [4]int{10, 20, 30, 40}
    if uint(x) < 4 { return table[x] }
    return -1

The resulting code is smaller and faster, especially on platforms where
jump tables are not supported.

goos: windows
goarch: arm64
pkg: cmd/compile/internal/test
                               │  .\old.txt  │              .\new.txt              │
                               │   sec/op    │   sec/op     vs base                │
SwitchLookup8Predictable-12      2.708n ± 6%   2.249n ± 5%  -16.97% (p=0.000 n=10)
SwitchLookup8Unpredictable-12    8.758n ± 7%   3.272n ± 4%  -62.65% (p=0.000 n=10)
SwitchLookup32Predictable-12     2.672n ± 5%   2.373n ± 6%  -11.21% (p=0.000 n=10)
SwitchLookup32Unpredictable-12   9.372n ± 7%   3.385n ± 6%  -63.89% (p=0.000 n=10)
geomean                          4.937n        2.772n       -43.84%

Fixes #78203

Change-Id: I74fa3d77ef618412951b2e5c3cb6ebc760ce4ff1
Reviewed-on: https://go-review.googlesource.com/c/go/+/756340
Reviewed-by: Keith Randall <khr@google.com>
Reviewed-by: Junyang Shao <shaojunyang@google.com>
Reviewed-by: Keith Randall <khr@golang.org>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>

1 files changed, 30 insertions, 2 deletions

diff --git a/test/codegen/switch.go b/test/codegen/switch.go
index d59ef4f2eb..07850522ab 100644
--- a/test/codegen/switch.go
+++ b/test/codegen/switch.go
@@ -21,13 +21,41 @@ func f(x string) int {
 	}
 }
 
-// use jump tables for 8+ int cases
-func square(x int) int {
+// use jump tables for 8+ string cases
+// Using multiple return values prevent lookup tables.
+func squareJump(x int) (int, int) {
 	// amd64:`JMP \(.*\)\(.*\)$`
 	// arm64:`MOVD \(R.*\)\(R.*<<3\)` `JMP \(R.*\)$`
 	// loong64: `ALSLV` `MOVV` `JMP`
 	switch x {
 	case 1:
+		return 1, 1
+	case 2:
+		return 4, 2
+	case 3:
+		return 9, 3
+	case 4:
+		return 16, 4
+	case 5:
+		return 25, 5
+	case 6:
+		return 36, 6
+	case 7:
+		return 49, 7
+	case 8:
+		return 64, 8
+	default:
+		return x * x, x
+	}
+}
+
+// use lookup tables for 8+ int cases returning constants
+func squareLookup(x int) int {
+	// amd64:`LEAQ .*\(SB\)` `MOVQ .*\(.*\)\(.*\*8\)` -`JMP \(.*\)\(.*\)$`
+	// arm64:`MOVD \(R.*\)\(R.*<<3\)` -`JMP \(R.*\)$`
+	// loong64:`SLLV` `MOVV \(R.*\)\(R.*\)` -`ALSLV`
+	switch x {
+	case 1:
 		return 1
 	case 2:
 		return 4