aboutsummaryrefslogtreecommitdiff
path: root/src/cmd/compile/internal/walk/switch.go
AgeCommit message (Collapse)Author
7 dayscmd/compile: support all constant return types in switch lookup tablesqmuntal
Lookup tables for switch statements can be generalized to also support bools, strings, floats, and complex numbers. Change-Id: Ic3ece41fe2009050fbf08ba6f06ea8a567407974 Reviewed-on: https://go-review.googlesource.com/c/go/+/763320 Reviewed-by: David Chase <drchase@google.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Auto-Submit: Keith Randall <khr@golang.org> Reviewed-by: Keith Randall <khr@golang.org> Reviewed-by: Keith Randall <khr@google.com>
12 dayscmd/compile: optimize switch statements using lookup tablesqmuntal
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>
2024-10-25cmd/compile: optimize type switch for a single runtime known type with a ↵Youlin Feng
case var Change-Id: I03ba70076d6dd3c0b9624d14699b7dd91a3c0e9b Reviewed-on: https://go-review.googlesource.com/c/go/+/618476 Reviewed-by: Keith Randall <khr@golang.org> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: Cuong Manh Le <cuong.manhle.vn@gmail.com> Reviewed-by: Cherry Mui <cherryyz@google.com> Reviewed-by: Keith Randall <khr@google.com> Auto-Submit: Cuong Manh Le <cuong.manhle.vn@gmail.com>
2024-10-07cmd/compile: avoid dynamic type when possibleCuong Manh Le
If the expression type is a single compile-time known type, use that type instead of the dynamic one, so the later passes of the compiler could skip un-necessary runtime calls. Thanks Youlin Feng for writing the original test case. Change-Id: I3f65ab90f041474a9731338a82136c1d394c1773 Reviewed-on: https://go-review.googlesource.com/c/go/+/616975 Auto-Submit: Cuong Manh Le <cuong.manhle.vn@gmail.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: Keith Randall <khr@golang.org> Reviewed-by: Keith Randall <khr@google.com> Reviewed-by: Cherry Mui <cherryyz@google.com>
2024-09-05cmd/compile: use slices.{Sort,SortFunc}Cuong Manh Le
Now that we're bootstrapping from a toolchain that has the slices package. Updates #64751 Change-Id: I2e63d95577d058670d3dc75bd45d6e050c6f0e25 Reviewed-on: https://go-review.googlesource.com/c/go/+/610601 Reviewed-by: Cherry Mui <cherryyz@google.com> Reviewed-by: Dmitri Shuralyov <dmitshur@google.com> Auto-Submit: Cuong Manh Le <cuong.manhle.vn@gmail.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
2024-03-04cmd/compile/internal: use reflectdata.TypeLinksymapocelipes
As the document of Sym.Linksym said, we replace reflectdata.TypeSym(t).Linksym() with reflectdata.TypeLinksym(t). Change-Id: I578eb159e552e60cd05d2aa1560f91797a6629ef GitHub-Last-Rev: d096cba8f08506d7c5248dbf0179e5aef77e8f65 GitHub-Pull-Request: golang/go#66088 Reviewed-on: https://go-review.googlesource.com/c/go/+/568715 Reviewed-by: Michael Knyszek <mknyszek@google.com> Reviewed-by: Keith Randall <khr@golang.org> Auto-Submit: Keith Randall <khr@golang.org> Reviewed-by: Keith Randall <khr@google.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
2024-02-16cmd/compile: use symbolic offsets of fields in internal/abi.ITabKeith Randall
After this CL, we can reorder or pad internal/abi.ITab fields at will (keeping Fun last, and updating ITabTypeOff correctly) without breaking anything. Change-Id: Ib7bb5828519813e0d1aa36be5092f96fcd62b3be Reviewed-on: https://go-review.googlesource.com/c/go/+/549516 Reviewed-by: Keith Randall <khr@google.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: David Chase <drchase@google.com>
2023-10-24cmd/compile: use new runtime type mechanism for type switches and assertsKeith Randall
Change-Id: Ife7d6d6d773ac0d8ac38dbd2da7dccc519998b63 Reviewed-on: https://go-review.googlesource.com/c/go/+/534816 LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: David Chase <drchase@google.com> Reviewed-by: Than McIntosh <thanm@google.com>
2023-10-24cmd/compile: reorganize compiler type descriptor generationKeith Randall
Use the new rttype mechanism to share internal/abi types between the compiler and runtime. Change-Id: I2bbba4d8090c6f7ff20dca15b7b665f5d04e5bfd Reviewed-on: https://go-review.googlesource.com/c/go/+/534936 Reviewed-by: David Chase <drchase@google.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> TryBot-Result: Gopher Robot <gobot@golang.org> Reviewed-by: Carlos Amedee <carlos@golang.org> Run-TryBot: David Chase <drchase@google.com>
2023-10-09cmd/compile: use type hash from itab field instead of type fieldKeith Randall
It is one less dependent load away, and right next to another field in the itab we also load as part of the type switch or type assert. Change-Id: If7aaa7814c47bd79a6c7ed4232ece0bc1d63550e Reviewed-on: https://go-review.googlesource.com/c/go/+/533117 Reviewed-by: Cuong Manh Le <cuong.manhle.vn@gmail.com> Reviewed-by: Keith Randall <khr@google.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: Matthew Dempsky <mdempsky@google.com>
2023-10-09cmd/compile: use internal/abi types in the compilerKeith Randall
It is tricky to use those types directly, because the layout of those types in the compiler may not be the same as the layout of those types in target binary (typically because of 32 vs 64 bit differences). Instead, translate an internal/abi type into a cmd/compile/internal/types type, which will then be laid out for the target machine. Along with the translation, keep track of where all the bits of the type are so we can reference their locations symbolically instead of hardcoding them. Change-Id: I2694c58968d4dc7ead63a2b1b29adfedd90ddd2e Reviewed-on: https://go-review.googlesource.com/c/go/+/532155 Reviewed-by: David Chase <drchase@google.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Auto-Submit: Keith Randall <khr@google.com> Reviewed-by: Keith Randall <khr@google.com>
2023-10-06cmd/compile: add a cache to interface type switchesKeith Randall
That way we don't need to call into the runtime when the type being switched on has been seen many times before. The cache is just a hash table of a sample of all the concrete types that have been switched on at that source location. We record the matching case number and the resulting itab for each concrete input type. The caches seldom get large. The only two in a run of all.bash that get more than 100 entries, even with the sampling rate set to 1, are test/fixedbugs/issue29264.go, with 101 test/fixedbugs/issue29312.go, with 254 Both happen at the type switch in fmt.(*pp).handleMethods, perhaps unsurprisingly. name old time/op new time/op delta SwitchInterfaceTypePredictable-24 25.8ns ± 2% 2.5ns ± 3% -90.43% (p=0.000 n=10+10) SwitchInterfaceTypeUnpredictable-24 37.5ns ± 2% 11.2ns ± 1% -70.02% (p=0.000 n=10+10) Change-Id: I4961ac9547b7f15b03be6f55cdcb972d176955eb Reviewed-on: https://go-review.googlesource.com/c/go/+/526658 Reviewed-by: Cuong Manh Le <cuong.manhle.vn@gmail.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: Matthew Dempsky <mdempsky@google.com> Reviewed-by: Keith Randall <khr@google.com>
2023-10-06cmd/compile: improve interface type switchesKeith Randall
For type switches where the targets are interface types, call into the runtime once instead of doing a sequence of assert* calls. name old time/op new time/op delta SwitchInterfaceTypePredictable-24 26.6ns ± 1% 25.8ns ± 2% -2.86% (p=0.000 n=10+10) SwitchInterfaceTypeUnpredictable-24 39.3ns ± 1% 37.5ns ± 2% -4.57% (p=0.000 n=10+10) Not super helpful by itself, but this code organization allows followon CLs that add caching to the lookups. Change-Id: I7967f85a99171faa6c2550690e311bea8b54b01c Reviewed-on: https://go-review.googlesource.com/c/go/+/526657 Reviewed-by: Matthew Dempsky <mdempsky@google.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: Cuong Manh Le <cuong.manhle.vn@gmail.com> Reviewed-by: Keith Randall <khr@google.com>
2023-09-11cmd/compile/internal/ir: add Type param to NewBasicLitMatthew Dempsky
This CL adds an explicit Type parameter to NewBasicLit so that callers can directly construct typed OLITERAL nodes. Change-Id: I0ab50ac3d7ddb7adcc903633a62ac496921165e9 Reviewed-on: https://go-review.googlesource.com/c/go/+/527096 Auto-Submit: Matthew Dempsky <mdempsky@google.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: Keith Randall <khr@google.com> Reviewed-by: Cuong Manh Le <cuong.manhle.vn@gmail.com>
2023-08-23cmd/compile: use jump tables for large type switchesKeith Randall
For large interface -> concrete type switches, we can use a jump table on some bits of the type hash instead of a binary search on the type hash. name old time/op new time/op delta SwitchTypePredictable-24 1.99ns ± 2% 1.78ns ± 5% -10.87% (p=0.000 n=10+10) SwitchTypeUnpredictable-24 11.0ns ± 1% 9.1ns ± 2% -17.55% (p=0.000 n=7+9) Change-Id: Ida4768e5d62c3ce1c2701288b72664aaa9e64259 Reviewed-on: https://go-review.googlesource.com/c/go/+/521497 Reviewed-by: Keith Randall <khr@google.com> Auto-Submit: Keith Randall <khr@google.com> TryBot-Result: Gopher Robot <gobot@golang.org> Reviewed-by: Cherry Mui <cherryyz@google.com> Run-TryBot: Keith Randall <khr@golang.org>
2023-08-18cmd/compile/internal/typecheck: replace Temp calls with TempAtMatthew Dempsky
Steps towards eliminating implicit dependencies on base.Pos and ir.CurFunc. Mechanical CL produced with gofmt -r. Change-Id: I070015513cb955cbe87f9a148d81db8c0d4b0dc5 Reviewed-on: https://go-review.googlesource.com/c/go/+/520605 Reviewed-by: Cuong Manh Le <cuong.manhle.vn@gmail.com> Run-TryBot: Matthew Dempsky <mdempsky@google.com> TryBot-Result: Gopher Robot <gobot@golang.org> Reviewed-by: Dmitri Shuralyov <dmitshur@google.com> Auto-Submit: Matthew Dempsky <mdempsky@google.com>
2023-08-18cmd/compile: restore zero-copy string->[]byte optimizationMatthew Dempsky
This CL implements the remainder of the zero-copy string->[]byte conversion optimization initially attempted in go.dev/cl/520395, but fixes the tracking of mutations due to ODEREF/ODOTPTR assignments, and adds more comprehensive tests that I should have included originally. However, this CL also keeps it behind the -d=zerocopy flag. The next CL will enable it by default (for easier rollback). Updates #2205. Change-Id: Ic330260099ead27fc00e2680a59c6ff23cb63c2b Reviewed-on: https://go-review.googlesource.com/c/go/+/520599 Auto-Submit: Matthew Dempsky <mdempsky@google.com> TryBot-Result: Gopher Robot <gobot@golang.org> Reviewed-by: Than McIntosh <thanm@google.com> Run-TryBot: Matthew Dempsky <mdempsky@google.com> Reviewed-by: Cuong Manh Le <cuong.manhle.vn@gmail.com>
2023-08-17Revert "cmd/compile: enable zero-copy string->[]byte conversions"Matthew Dempsky
This reverts CL 520395. Reason for revert: thanm@ pointed out failure cases. Change-Id: I3fd60b73118be3652be2c08b77ab39e793b42110 Reviewed-on: https://go-review.googlesource.com/c/go/+/520596 Reviewed-by: Dmitri Shuralyov <dmitshur@golang.org> Run-TryBot: Matthew Dempsky <mdempsky@google.com> Reviewed-by: Than McIntosh <thanm@google.com> TryBot-Result: Gopher Robot <gobot@golang.org> Reviewed-by: Dmitri Shuralyov <dmitshur@google.com> Auto-Submit: Matthew Dempsky <mdempsky@google.com>
2023-08-17cmd/compile: enable zero-copy string->[]byte conversionsMatthew Dempsky
This CL enables the latent support for string->[]byte conversions added go.dev/cl/520259. One catch is that we need to make sure []byte("") evaluates to a non-nil slice, even if "" is (nil, 0). This CL addresses that by adding a "ptr != nil" check for OSTR2BYTESTMP, unless the NonNil flag is set. The existing uses of OSTR2BYTESTMP (which aren't concerned about []byte("") evaluating to nil) are updated to set this flag. Fixes #2205. Change-Id: I35a9cb16c164cd86156b7560915aba5108d8b523 Reviewed-on: https://go-review.googlesource.com/c/go/+/520395 Run-TryBot: Matthew Dempsky <mdempsky@google.com> TryBot-Result: Gopher Robot <gobot@golang.org> Auto-Submit: Matthew Dempsky <mdempsky@google.com> Reviewed-by: Cuong Manh Le <cuong.manhle.vn@gmail.com> Reviewed-by: Dmitri Shuralyov <dmitshur@google.com>
2023-08-17cmd/compile/internal/ir: add typ parameter to NewNameAtMatthew Dempsky
Start making progress towards constructing IR with proper types. Change-Id: Iad32c1cf60f30ceb8e07c31c8871b115570ac3bd Reviewed-on: https://go-review.googlesource.com/c/go/+/520263 Run-TryBot: Matthew Dempsky <mdempsky@google.com> TryBot-Result: Gopher Robot <gobot@golang.org> Auto-Submit: Matthew Dempsky <mdempsky@google.com> Reviewed-by: Dmitri Shuralyov <dmitshur@google.com> Reviewed-by: Cuong Manh Le <cuong.manhle.vn@gmail.com>
2023-03-04cmd/compile/internal/ir: explicit Pos for New{Bool,Int,String}Matthew Dempsky
Stop depending on base.Pos for these. Change-Id: I58dea44f8141eb37b59a6e9f7db0c6baa516ad93 Reviewed-on: https://go-review.googlesource.com/c/go/+/472296 Reviewed-by: Keith Randall <khr@google.com> Run-TryBot: Matthew Dempsky <mdempsky@google.com> Auto-Submit: Matthew Dempsky <mdempsky@google.com> Reviewed-by: Cuong Manh Le <cuong.manhle.vn@gmail.com> Reviewed-by: Keith Randall <khr@golang.org> TryBot-Result: Gopher Robot <gobot@golang.org>
2023-01-27cmd/compile: remove go119UseJumpTables flagKeith Randall
Change-Id: Iaaac46e96b74289096ce0c6186c73000d1fc6faa Reviewed-on: https://go-review.googlesource.com/c/go/+/463224 Reviewed-by: Cherry Mui <cherryyz@google.com> Reviewed-by: Keith Randall <khr@google.com> Run-TryBot: Keith Randall <khr@golang.org> TryBot-Result: Gopher Robot <gobot@golang.org>
2022-12-06cmd/compile: turn off jump tables when spectre retpolines are onKeith Randall
Fixes #57097 Change-Id: I6ab659abbca1ae0ac8710674d39aec116fab0baa Reviewed-on: https://go-review.googlesource.com/c/go/+/455336 Reviewed-by: Keith Randall <khr@google.com> Reviewed-by: Cherry Mui <cherryyz@google.com> TryBot-Result: Gopher Robot <gobot@golang.org> Run-TryBot: Keith Randall <khr@golang.org>
2022-08-31cmd/compile: use better splitting condition for string binary searchKeith Randall
Currently we use a full cmpstring to do the comparison for each split in the binary search for a string switch. Instead, split by comparing a single byte of the input string with a constant. That will give us a much faster split (although it might be not quite as good a split). Fixes #53333 R=go1.20 Change-Id: I28c7209342314f367071e4aa1f2beb6ec9ff7123 Reviewed-on: https://go-review.googlesource.com/c/go/+/414894 TryBot-Result: Gopher Robot <gobot@golang.org> Run-TryBot: Keith Randall <khr@golang.org> Reviewed-by: David Chase <drchase@google.com> Reviewed-by: Heschi Kreinick <heschi@google.com>
2022-08-22cmd/compile: rip out support for OVARKILL from compiler frontendKeith Randall
Change-Id: I2c5b1064084bade68aaa065cf74dca6886fb752f Reviewed-on: https://go-review.googlesource.com/c/go/+/419236 TryBot-Result: Gopher Robot <gobot@golang.org> Reviewed-by: Keith Randall <khr@google.com> Run-TryBot: Keith Randall <khr@golang.org> Reviewed-by: David Chase <drchase@google.com>
2022-06-23[dev.unified] cmd/compile: plumb rtype through OSWITCH/OCASE clausesMatthew Dempsky
For (value) switch statements, we may generate OEQ comparisons between values of interface and concrete type, which in turn may require access to the concrete type's RType. To plumb this through, this CL adds CaseClause.RTypes to hold the rtype values, updates the GOEXPERIMENT=unified frontend to set it, and updates walk to plumb rtypes through into generated OEQ nodes. Change-Id: I6f1de2a1167ce54f5770147498a0a591efb3f012 Reviewed-on: https://go-review.googlesource.com/c/go/+/413361 Reviewed-by: Keith Randall <khr@golang.org> Reviewed-by: David Chase <drchase@google.com> Run-TryBot: Matthew Dempsky <mdempsky@google.com> TryBot-Result: Gopher Robot <gobot@golang.org>
2022-05-16cmd/compile/internal/ir: more idiomatic DynamicType{,AssertExpr}Matthew Dempsky
Rename DynamicType's "X" field to "RType". Split DynamicTypeAssertExpr's "T" field into "RType" and "ITab", the same as DynamicType, updating all uses accordingly. Change-Id: I8cec8171349c93234a10ac50708f800dee6fb1d2 Reviewed-on: https://go-review.googlesource.com/c/go/+/405334 Auto-Submit: Matthew Dempsky <mdempsky@google.com> TryBot-Result: Gopher Robot <gobot@golang.org> Reviewed-by: Keith Randall <khr@golang.org> Reviewed-by: Dmitri Shuralyov <dmitshur@google.com> Run-TryBot: Matthew Dempsky <mdempsky@google.com>
2022-05-05cmd/compile: remove ir.TypeAssertExpr.NtypeMatthew Dempsky
As with ir.CompLitExpr.Ntype, there's no need for ir.TypeAssertExpr.Ntype in a pure-types2 world. Change-Id: Iff48c98330f072fd6b26099e13a19c56adecdc42 Reviewed-on: https://go-review.googlesource.com/c/go/+/403842 Reviewed-by: David Chase <drchase@google.com> Run-TryBot: Matthew Dempsky <mdempsky@google.com> TryBot-Result: Gopher Robot <gobot@golang.org> Reviewed-by: Cuong Manh Le <cuong.manhle.vn@gmail.com>
2022-04-15cmd/compile: turn jump tables off with -NKeith Randall
The noopt builder is broken, because with -N we get two OpSB opcodes (one for the function as a whole, one introduced by the jumptable rewrite rule), and they fight each other for a register. Without -N, the two OpSB get CSEd, so optimized builds are ok. Maybe we fix regalloc to deal with this case, but it's simpler (and maybe more correct?) to disable jump tables with -N. Change-Id: I75c87f12de6262955d1df787f47c53de976f8a5f Reviewed-on: https://go-review.googlesource.com/c/go/+/400455 Run-TryBot: Keith Randall <khr@golang.org> Reviewed-by: Keith Randall <khr@google.com> Auto-Submit: Keith Randall <khr@google.com> TryBot-Result: Gopher Robot <gobot@golang.org> Reviewed-by: Ian Lance Taylor <iant@google.com>
2022-04-14cmd/compile: modify switches of strings to use jump table for lengthsKeith Randall
Reorganize the way we rewrite expression switches on strings, so that jump tables are naturally used for the outer switch on the string length. The changes to the prove pass in this CL are required so as to not repeat the test for string length in each case. name old time/op new time/op delta SwitchStringPredictable 2.28ns ± 9% 2.08ns ± 5% -9.04% (p=0.000 n=10+10) SwitchStringUnpredictable 10.5ns ± 1% 9.5ns ± 1% -9.08% (p=0.000 n=9+10) Update #5496 Update #34381 Change-Id: Ie6846b1dd27f3e472f7c30dfcc598c68d440b997 Reviewed-on: https://go-review.googlesource.com/c/go/+/395714 Run-TryBot: Keith Randall <khr@golang.org> TryBot-Result: Gopher Robot <gobot@golang.org> Reviewed-by: Cherry Mui <cherryyz@google.com> Reviewed-by: Keith Randall <khr@google.com>
2022-04-14cmd/compile: implement jump tablesKeith Randall
Performance is kind of hard to exactly quantify. One big difference between jump tables and the old binary search scheme is that there's only 1 branch statement instead of O(n) of them. That can be both a blessing and a curse, and can make evaluating jump tables very hard to do. The single branch can become a choke point for the hardware branch predictor. A branch table jump must fit all of its state in a single branch predictor entry (technically, a branch target predictor entry). With binary search that predictor state can be spread among lots of entries. In cases where the case selection is repetitive and thus predictable, binary search can perform better. The big win for a jump table is that it doesn't consume so much of the branch predictor's resources. But that benefit is essentially never observed in microbenchmarks, because the branch predictor can easily keep state for all the binary search branches in a microbenchmark. So that benefit is really hard to measure. So predictable switch microbenchmarks are ~useless - they will almost always favor the binary search scheme. Fully unpredictable switch microbenchmarks are better, as they aren't lying to us quite so much. In a perfectly unpredictable situation, a jump table will expect to incur 1-1/N branch mispredicts, where a binary search would incur lg(N)/2 of them. That makes the crossover point at about N=4. But of course switches in real programs are seldom fully unpredictable, so we'll use a higher crossover point. Beyond the branch predictor, jump tables tend to execute more instructions per switch but have no additional instructions per case, which also argues for a larger crossover. As far as code size goes, with this CL cmd/go has a slightly smaller code segment and a slightly larger overall size (from the jump tables themselves which live in the data segment). This is a case where some FDO (feedback-directed optimization) would be really nice to have. #28262 Some large-program benchmarks might help make the case for this CL. Especially if we can turn on branch mispredict counters so we can see how much using jump tables can free up branch prediction resources that can be gainfully used elsewhere in the program. name old time/op new time/op delta Switch8Predictable 1.89ns ± 2% 1.27ns ± 3% -32.58% (p=0.000 n=9+10) Switch8Unpredictable 9.33ns ± 1% 7.50ns ± 1% -19.60% (p=0.000 n=10+9) Switch32Predictable 2.20ns ± 2% 1.64ns ± 1% -25.39% (p=0.000 n=10+9) Switch32Unpredictable 10.0ns ± 2% 7.6ns ± 2% -24.04% (p=0.000 n=10+10) Fixes #5496 Update #34381 Change-Id: I3ff56011d02be53f605ca5fd3fb96b905517c34f Reviewed-on: https://go-review.googlesource.com/c/go/+/357330 Run-TryBot: Keith Randall <khr@golang.org> TryBot-Result: Gopher Robot <gobot@golang.org> Reviewed-by: Cherry Mui <cherryyz@google.com> Reviewed-by: Keith Randall <khr@google.com>
2021-08-09[dev.typeparams] cmd/compile: implement generic type switchesKeith Randall
Add a new dynamicType node, which is used as a case entry when the type being switched to is generic. Change-Id: Ice77c6f224b8fdd3ff574fdf4a8ea5f6c7ddbe75 Reviewed-on: https://go-review.googlesource.com/c/go/+/339429 Trust: Keith Randall <khr@golang.org> Trust: Dan Scales <danscales@google.com> Run-TryBot: Keith Randall <khr@golang.org> Reviewed-by: Dan Scales <danscales@google.com>
2021-01-16[dev.regabi] cmd/compile, runtime: fix up comments/error messages from ↵Dan Scales
recent renames Went in a semi-automated way through the clearest renames of functions, and updated comments and error messages where it made sense. Change-Id: Ied8e152b562b705da7f52f715991a77dab60da35 Reviewed-on: https://go-review.googlesource.com/c/go/+/284216 Trust: Dan Scales <danscales@google.com> Run-TryBot: Dan Scales <danscales@google.com> TryBot-Result: Go Bot <gobot@golang.org> Reviewed-by: Matthew Dempsky <mdempsky@google.com>
2021-01-14[dev.regabi] cmd/compile: use node walked flag to prevent double walk for ↵Cuong Manh Le
walkSwitch CL 283672 added a flag to prevent double walking, use that flag instead of checking SwitchStmt.Compiled field. Passes toolstash -cmp. Change-Id: Idb8f9078412fb789f51ed4fc4206638011e38a93 Reviewed-on: https://go-review.googlesource.com/c/go/+/283733 Trust: Cuong Manh Le <cuong.manhle.vn@gmail.com> Run-TryBot: Cuong Manh Le <cuong.manhle.vn@gmail.com> TryBot-Result: Go Bot <gobot@golang.org> Reviewed-by: Matthew Dempsky <mdempsky@google.com>
2021-01-04[dev.regabi] cmd/compile: fix ICE due to large uint64 constantsMatthew Dempsky
It's an error to call Int64Val on constants that don't fit into int64. CL 272654 made the compiler stricter about detecting misuse, and revealed that we were using it improperly in detecting consecutive integer-switch cases. That particular usage actually did work in practice, but it's easy and best to just fix it. Fixes #43480. Change-Id: I56f722d75e83091638ac43b80e45df0b0ad7d48d Reviewed-on: https://go-review.googlesource.com/c/go/+/281272 Trust: Matthew Dempsky <mdempsky@google.com> Run-TryBot: Matthew Dempsky <mdempsky@google.com> TryBot-Result: Go Bot <gobot@golang.org> Reviewed-by: Cuong Manh Le <cuong.manhle.vn@gmail.com>
2020-12-29[dev.regabi] cmd/compile: use *ir.Name instead of ir.Node for CaseClause.VarCuong Manh Le
Passes toolstash -cmp. Change-Id: Ib0b6ebf5751ffce2c9500dc67d78e54937ead208 Reviewed-on: https://go-review.googlesource.com/c/go/+/279449 Trust: Cuong Manh Le <cuong.manhle.vn@gmail.com> Run-TryBot: Cuong Manh Le <cuong.manhle.vn@gmail.com> TryBot-Result: Go Bot <gobot@golang.org> Reviewed-by: Matthew Dempsky <mdempsky@google.com>
2020-12-28[dev.regabi] cmd/compile: use []*CaseStmt in {Select,Switch}StmtMatthew Dempsky
Select and switch statements only ever contain case statements, so change their Cases fields from Nodes to []*CaseStmt. This allows removing a bunch of type assertions throughout the compiler. CaseStmt should be renamed to CaseClause, and SelectStmt should probably have its own CommClause type instead (like in go/ast and cmd/compile/internal/syntax), but this is a good start. Passes toolstash -cmp. Change-Id: I2d41d616d44512c2be421e1e2ff13d0ee8b238ad Reviewed-on: https://go-review.googlesource.com/c/go/+/280442 Trust: Matthew Dempsky <mdempsky@google.com> Run-TryBot: Matthew Dempsky <mdempsky@google.com> TryBot-Result: Go Bot <gobot@golang.org> Reviewed-by: Cuong Manh Le <cuong.manhle.vn@gmail.com>
2020-12-28[dev.regabi] cmd/compile: always use a Field for ODOTPTR expressionsMatthew Dempsky
During walk, we create ODOTPTR expressions to access runtime struct fields. But rather than using an actual Field for the selection, we were just directly setting the ODOTPTR's Offset field. This CL changes walk to create proper struct fields (albeit without the rest of their enclosing struct type) and use them for creating the ODOTPTR expressions. Passes toolstash -cmp. Change-Id: I08dbac3ed29141587feb0905d15adbcbcc4ca49e Reviewed-on: https://go-review.googlesource.com/c/go/+/280432 Trust: Matthew Dempsky <mdempsky@google.com> Run-TryBot: Matthew Dempsky <mdempsky@google.com> TryBot-Result: Go Bot <gobot@golang.org> Reviewed-by: Cuong Manh Le <cuong.manhle.vn@gmail.com>
2020-12-23[dev.regabi] cmd/compile: change CaseStmt.Vars to VarMatthew Dempsky
There's only ever one variable implicitly declared by a CaseStmt. It's only a slice because we previous used Rlist for this. Passes toolstash -cmp. Change-Id: Idf747f3ec6dfbbe4e94d60546ba04a81754df3fe Reviewed-on: https://go-review.googlesource.com/c/go/+/280012 Trust: Matthew Dempsky <mdempsky@google.com> Run-TryBot: Matthew Dempsky <mdempsky@google.com> TryBot-Result: Go Bot <gobot@golang.org> Reviewed-by: Cuong Manh Le <cuong.manhle.vn@gmail.com>
2020-12-23[dev.regabi] cmd/compile: split up walkexpr1, walkstmt [generated]Russ Cox
walkexpr1 is the second largest non-machine-generated function in the compiler. weighing in at 1,164 lines. Since we are destroying the git blame history anyway, now is a good time to split each different case into its own function, making future work on this function more manageable. Do the same to walkstmt too for consistency, even though it is a paltry 259 lines. [git-generate] cd src/cmd/compile/internal/walk rf ' mv addstr walkAddString mv walkCall walkCall1 mv walkpartialcall walkCallPart mv walkclosure walkClosure mv walkrange walkRange mv walkselect walkSelect mv walkselectcases walkSelectCases mv walkswitch walkSwitch mv walkExprSwitch walkSwitchExpr mv walkTypeSwitch walkSwitchType mv walkstmt walkStmt mv walkstmtlist walkStmtList mv walkexprlist walkExprList mv walkexprlistsafe walkExprListSafe mv walkexprlistcheap walkExprListCheap mv walkexpr walkExpr mv walkexpr1 walkExpr1 mv walkprint walkPrint mv walkappend walkAppend mv walkcompare walkCompare mv walkcompareInterface walkCompareInterface mv walkcompareString walkCompareString mv appendslice appendSlice mv cheapexpr cheapExpr mv copyany walkCopy mv copyexpr copyExpr mv eqfor eqFor mv extendslice extendSlice mv finishcompare finishCompare mv safeexpr safeExpr mv walkStmt:/^\tcase ir.ORECV:/+2,/^\tcase /-2 walkRecv add walk.go:/^func walkRecv/-0 \ // walkRecv walks an ORECV node. mv walkStmt:/^\tcase ir.ODCL:/+2,/^\tcase /-2 walkDecl add walk.go:/^func walkDecl/-0 \ // walkDecl walks an ODCL node. mv walkStmt:/^\tcase ir.OGO:/+2,/^\tcase /-2 walkGoDefer add walk.go:/^func walkGoDefer/-0 \ // walkGoDefer walks an OGO or ODEFER node. mv walkStmt:/^\tcase ir.OFOR,/+2,/^\tcase /-2 walkFor add walk.go:/^func walkFor/-0 \ // walkFor walks an OFOR or OFORUNTIL node. mv walkStmt:/^\tcase ir.OIF:/+2,/^\tcase /-2 walkIf add walk.go:/^func walkIf/-0 \ // walkIf walks an OIF node. mv walkStmt:/^\tcase ir.ORETURN:/+2,/^\tcase /-2 walkReturn add walk.go:/^func walkReturn/-0 \ // walkReturn walks an ORETURN node. mv walkExpr1:/^\tcase ir.ODOT,/+2,/^\tcase /-2 walkDot add walk.go:/^func walkDot/-0 \ // walkDot walks an ODOT or ODOTPTR node. mv walkExpr1:/^\tcase ir.ODOTTYPE,/+2,/^\tcase /-2 walkDotType add walk.go:/^func walkDotType/-0 \ // walkDotType walks an ODOTTYPE or ODOTTYPE2 node. mv walkExpr1:/^\tcase ir.OLEN,/+2,/^\tcase /-2 walkLenCap add walk.go:/^func walkLenCap/-0 \ // walkLenCap walks an OLEN or OCAP node. mv walkExpr1:/^\tcase ir.OANDAND,/+2,/^\tcase /-2 walkLogical add walk.go:/^func walkLogical/-0 \ // walkLogical walks an OANDAND or OOROR node. mv walkExpr1:/^\tcase ir.OCALLINTER,/+2,/^\tcase /-2 walkCall add walk.go:/^func walkCall/-0 \ // walkCall walks an OCALLFUNC, OCALLINTER, or OCALLMETH node. mv walkExpr1:/^\tcase ir.OAS,/+1,/^\tcase /-2 walkAssign add walk.go:/^func walkAssign/-0 \ // walkAssign walks an OAS (AssignExpr) or OASOP (AssignOpExpr) node. mv walkExpr1:/^\tcase ir.OAS2:/+2,/^\tcase /-3 walkAssignList add walk.go:/^func walkAssignList/-0 \ // walkAssignList walks an OAS2 node. mv walkExpr1:/^\tcase ir.OAS2FUNC:/+2,/^\tcase /-4 walkAssignFunc add walk.go:/^func walkAssignFunc/-0 \ // walkAssignFunc walks an OAS2FUNC node. mv walkExpr1:/^\tcase ir.OAS2RECV:/+2,/^\tcase /-3 walkAssignRecv add walk.go:/^func walkAssignRecv/-0 \ // walkAssignRecv walks an OAS2RECV node. mv walkExpr1:/^\tcase ir.OAS2MAPR:/+2,/^\tcase /-2 walkAssignMapRead add walk.go:/^func walkAssignMapRead/-0 \ // walkAssignMapRead walks an OAS2MAPR node. mv walkExpr1:/^\tcase ir.ODELETE:/+2,/^\tcase /-2 walkDelete add walk.go:/^func walkDelete/-0 \ // walkDelete walks an ODELETE node. mv walkExpr1:/^\tcase ir.OAS2DOTTYPE:/+2,/^\tcase /-2 walkAssignDotType add walk.go:/^func walkAssignDotType/-0 \ // walkAssignDotType walks an OAS2DOTTYPE node. mv walkExpr1:/^\tcase ir.OCONVIFACE:/+2,/^\tcase /-2 walkConvInterface add walk.go:/^func walkConvInterface/-0 \ // walkConvInterface walks an OCONVIFACE node. mv walkExpr1:/^\tcase ir.OCONV,/+2,/^\tcase /-2 walkConv add walk.go:/^func walkConv/-0 \ // walkConv walks an OCONV or OCONVNOP (but not OCONVIFACE) node. mv walkExpr1:/^\tcase ir.ODIV,/+2,/^\tcase /-2 walkDivMod add walk.go:/^func walkDivMod/-0 \ // walkDivMod walks an ODIV or OMOD node. mv walkExpr1:/^\tcase ir.OINDEX:/+2,/^\tcase /-2 walkIndex add walk.go:/^func walkIndex/-0 \ // walkIndex walks an OINDEX node. # move type assertion above comment mv walkExpr1:/^\tcase ir.OINDEXMAP:/+/n := n/-+ walkExpr1:/^\tcase ir.OINDEXMAP:/+0 mv walkExpr1:/^\tcase ir.OINDEXMAP:/+2,/^\tcase /-2 walkIndexMap add walk.go:/^func walkIndexMap/-0 \ // walkIndexMap walks an OINDEXMAP node. mv walkExpr1:/^\tcase ir.OSLICEHEADER:/+2,/^\tcase /-2 walkSliceHeader add walk.go:/^func walkSliceHeader/-0 \ // walkSliceHeader walks an OSLICEHEADER node. mv walkExpr1:/^\tcase ir.OSLICE,/+2,/^\tcase /-2 walkSlice add walk.go:/^func walkSlice/-0 \ // walkSlice walks an OSLICE, OSLICEARR, OSLICESTR, OSLICE3, or OSLICE3ARR node. mv walkExpr1:/^\tcase ir.ONEW:/+2,/^\tcase /-2 walkNew add walk.go:/^func walkNew/-0 \ // walkNew walks an ONEW node. # move type assertion above comment mv walkExpr1:/^\tcase ir.OCLOSE:/+/n := n/-+ walkExpr1:/^\tcase ir.OCLOSE:/+0 mv walkExpr1:/^\tcase ir.OCLOSE:/+2,/^\tcase /-2 walkClose add walk.go:/^func walkClose/-0 \ // walkClose walks an OCLOSE node. # move type assertion above comment mv walkExpr1:/^\tcase ir.OMAKECHAN:/+/n := n/-+ walkExpr1:/^\tcase ir.OMAKECHAN:/+0 mv walkExpr1:/^\tcase ir.OMAKECHAN:/+2,/^\tcase /-2 walkMakeChan add walk.go:/^func walkMakeChan/-0 \ // walkMakeChan walks an OMAKECHAN node. mv walkExpr1:/^\tcase ir.OMAKEMAP:/+2,/^\tcase /-2 walkMakeMap add walk.go:/^func walkMakeMap/-0 \ // walkMakeMap walks an OMAKEMAP node. mv walkExpr1:/^\tcase ir.OMAKESLICE:/+2,/^\tcase /-2 walkMakeSlice add walk.go:/^func walkMakeSlice/-0 \ // walkMakeSlice walks an OMAKESLICE node. mv walkExpr1:/^\tcase ir.OMAKESLICECOPY:/+2,/^\tcase /-2 walkMakeSliceCopy add walk.go:/^func walkMakeSliceCopy/-0 \ // walkMakeSliceCopy walks an OMAKESLICECOPY node. mv walkExpr1:/^\tcase ir.ORUNESTR:/+2,/^\tcase /-2 walkRuneToString add walk.go:/^func walkRuneToString/-0 \ // walkRuneToString walks an ORUNESTR node. mv walkExpr1:/^\tcase ir.OBYTES2STR,/+2,/^\tcase /-2 walkBytesRunesToString add walk.go:/^func walkBytesRunesToString/-0 \ // walkBytesRunesToString walks an OBYTES2STR or ORUNES2STR node. mv walkExpr1:/^\tcase ir.OBYTES2STRTMP:/+2,/^\tcase /-2 walkBytesToStringTemp add walk.go:/^func walkBytesToStringTemp/-0 \ // walkBytesToStringTemp walks an OBYTES2STRTMP node. mv walkExpr1:/^\tcase ir.OSTR2BYTES:/+2,/^\tcase /-2 walkStringToBytes add walk.go:/^func walkStringToBytes/-0 \ // walkStringToBytes walks an OSTR2BYTES node. # move type assertion above comment mv walkExpr1:/^\tcase ir.OSTR2BYTESTMP:/+/n := n/-+ walkExpr1:/^\tcase ir.OSTR2BYTESTMP:/+0 mv walkExpr1:/^\tcase ir.OSTR2BYTESTMP:/+2,/^\tcase /-2 walkStringToBytesTemp add walk.go:/^func walkStringToBytesTemp/-0 \ // walkStringToBytesTemp walks an OSTR2BYTESTMP node. mv walkExpr1:/^\tcase ir.OSTR2RUNES:/+2,/^\tcase /-2 walkStringToRunes add walk.go:/^func walkStringToRunes/-0 \ // walkStringToRunes walks an OSTR2RUNES node. mv walkExpr1:/^\tcase ir.OARRAYLIT,/+1,/^\tcase /-2 walkCompLit add walk.go:/^func walkCompLit/-0 \ // walkCompLit walks a composite literal node: \ // OARRAYLIT, OSLICELIT, OMAPLIT, OSTRUCTLIT (all CompLitExpr), or OPTRLIT (AddrExpr). mv walkExpr1:/^\tcase ir.OSEND:/+2,/^\tcase /-2 walkSend add walk.go:/^func walkSend/-0 \ // walkSend walks an OSEND node. mv walkStmt walkStmtList \ walkDecl \ walkFor \ walkGoDefer \ walkIf \ wrapCall \ stmt.go mv walkExpr walkExpr1 walkExprList walkExprListCheap walkExprListSafe \ cheapExpr safeExpr copyExpr \ walkAddString \ walkCall \ walkCall1 \ walkDivMod \ walkDot \ walkDotType \ walkIndex \ walkIndexMap \ walkLogical \ walkSend \ walkSlice \ walkSliceHeader \ reduceSlice \ bounded \ usemethod \ usefield \ expr.go mv \ walkAssign \ walkAssignDotType \ walkAssignFunc \ walkAssignList \ walkAssignMapRead \ walkAssignRecv \ walkReturn \ fncall \ ascompatee \ ascompatee1 \ ascompatet \ reorder3 \ reorder3save \ aliased \ anyAddrTaken \ refersToName \ refersToCommonName \ appendSlice \ isAppendOfMake \ extendSlice \ assign.go mv \ walkCompare \ walkCompareInterface \ walkCompareString \ finishCompare \ eqFor \ brcom \ brrev \ tracecmpArg \ canMergeLoads \ compare.go mv \ walkConv \ walkConvInterface \ walkBytesRunesToString \ walkBytesToStringTemp \ walkRuneToString \ walkStringToBytes \ walkStringToBytesTemp \ walkStringToRunes \ convFuncName \ rtconvfn \ byteindex \ walkCheckPtrAlignment \ walkCheckPtrArithmetic \ convert.go mv \ walkAppend \ walkClose \ walkCopy \ walkDelete \ walkLenCap \ walkMakeChan \ walkMakeMap \ walkMakeSlice \ walkMakeSliceCopy \ walkNew \ walkPrint \ badtype \ callnew \ writebarrierfn \ isRuneCount \ builtin.go mv \ walkCompLit \ sinit.go \ complit.go mv subr.go walk.go ' Change-Id: Ie0cf3ba4adf363c120c134d57cb7ef37934eaab9 Reviewed-on: https://go-review.googlesource.com/c/go/+/279430 Trust: Russ Cox <rsc@golang.org> Run-TryBot: Russ Cox <rsc@golang.org> Reviewed-by: Matthew Dempsky <mdempsky@google.com>
2020-12-23[dev.regabi] cmd/compile: split out package walk [generated]Russ Cox
[git-generate] cd src/cmd/compile/internal/gc rf ' # Late addition to package ir. mv closuredebugruntimecheck ClosureDebugRuntimeCheck mv hasemptycvars IsTrivialClosure mv ClosureDebugRuntimeCheck IsTrivialClosure func.go mv func.go cmd/compile/internal/ir # Late addition to package reflectdata. mv markTypeUsedInInterface MarkTypeUsedInInterface mv markUsedIfaceMethod MarkUsedIfaceMethod mv MarkTypeUsedInInterface MarkUsedIfaceMethod reflect.go mv reflect.go cmd/compile/internal/reflectdata # Late addition to package staticdata. mv litsym InitConst mv InitConst data.go mv data.go cmd/compile/internal/staticdata # Extract staticinit out of walk into its own package. mv InitEntry InitPlan InitSchedule InitSchedule.append InitSchedule.staticInit \ InitSchedule.tryStaticInit InitSchedule.staticcopy \ InitSchedule.staticassign InitSchedule.initplan InitSchedule.addvalue \ statuniqgen staticname stataddr anySideEffects getlit isvaluelit \ sched.go mv InitSchedule.initplans InitSchedule.Plans mv InitSchedule.inittemps InitSchedule.Temps mv InitSchedule.out InitSchedule.Out mv InitSchedule.staticInit InitSchedule.StaticInit mv InitSchedule.staticassign InitSchedule.StaticAssign mv InitSchedule Schedule mv InitPlan Plan mv InitEntry Entry mv anySideEffects AnySideEffects mv staticname StaticName mv stataddr StaticLoc mv sched.go cmd/compile/internal/staticinit # Export API and unexport non-API. mv transformclosure Closure mv walk Walk mv Order orderState mv swt.go switch.go mv racewalk.go race.go mv closure.go order.go range.go select.go switch.go race.go \ sinit.go subr.go walk.go \ cmd/compile/internal/walk ' : # Update format test. cd ../../ go install cmd/compile/... cmd/internal/archive go test -u || go test -u rm -rf ../../../pkg/darwin_amd64/cmd Change-Id: I11c7a45f74d4a9e963da15c080e1018caaa99c05 Reviewed-on: https://go-review.googlesource.com/c/go/+/279478 Trust: Russ Cox <rsc@golang.org> Run-TryBot: Russ Cox <rsc@golang.org> Reviewed-by: Matthew Dempsky <mdempsky@google.com>
generated by cgit v1.3 (git 2.53.0) at 2026-04-15 12:11:15 +0000