aboutsummaryrefslogtreecommitdiff
path: root/src/cmd/compile/internal/ssa/sparsemap.go
AgeCommit message (Collapse)Author
2025-07-24cmd/compile: use ,ok return idiom for sparsemap.getKeith Randall
Change-Id: I89719b94de74a32402d02309515dffc4989484db Reviewed-on: https://go-review.googlesource.com/c/go/+/681575 LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: David Chase <drchase@google.com> Reviewed-by: Keith Randall <khr@google.com> Auto-Submit: Keith Randall <khr@google.com>
2025-07-24cmd/compile: use generics for sparse mapKeith Randall
So it is easier to reuse this code with different key/value types. Change-Id: I5a9e669769cf359b32f2fe784594868acdee4d02 Reviewed-on: https://go-review.googlesource.com/c/go/+/681175 Reviewed-by: Keith Randall <khr@google.com> Reviewed-by: David Chase <drchase@google.com> Auto-Submit: Keith Randall <khr@google.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: Cherry Mui <cherryyz@google.com>
2022-10-31cmd/compile: separate out sparsemaps that need positionKeith Randall
Make them a separate type, so the normal sparse maps don't need the extra storage. Change-Id: I3a0219487c35ea63723499723b0c742e321d97c4 Reviewed-on: https://go-review.googlesource.com/c/go/+/444819 Reviewed-by: Heschi Kreinick <heschi@google.com> TryBot-Result: Gopher Robot <gobot@golang.org> Run-TryBot: Keith Randall <khr@golang.org> Reviewed-by: David Chase <drchase@google.com>
2018-06-01all: update comment URLs from HTTP to HTTPS, where possibleTim Cooper
Each URL was manually verified to ensure it did not serve up incorrect content. Change-Id: I4dc846227af95a73ee9a3074d0c379ff0fa955df Reviewed-on: https://go-review.googlesource.com/115798 Reviewed-by: Ian Lance Taylor <iant@golang.org> Run-TryBot: Ian Lance Taylor <iant@golang.org>
2018-03-15cmd/compile: cache sparse maps across ssa passesDaniel Martí
This is done for sparse sets already, but it was missing for sparse maps. Only affects deadstore and regalloc, as they're the only ones that use sparse maps. name old time/op new time/op delta DSEPass-4 247µs ± 0% 216µs ± 0% -12.75% (p=0.008 n=5+5) DSEPassBlock-4 3.05ms ± 1% 2.87ms ± 1% -6.02% (p=0.002 n=6+6) CSEPass-4 2.30ms ± 0% 2.32ms ± 0% +0.53% (p=0.026 n=6+6) CSEPassBlock-4 23.8ms ± 0% 23.8ms ± 0% ~ (p=0.931 n=6+5) DeadcodePass-4 51.7µs ± 1% 51.5µs ± 2% ~ (p=0.429 n=5+6) DeadcodePassBlock-4 734µs ± 1% 742µs ± 3% ~ (p=0.394 n=6+6) MultiPass-4 152µs ± 0% 149µs ± 2% ~ (p=0.082 n=5+6) MultiPassBlock-4 2.67ms ± 1% 2.41ms ± 2% -9.77% (p=0.008 n=5+5) name old alloc/op new alloc/op delta DSEPass-4 41.2kB ± 0% 0.1kB ± 0% -99.68% (p=0.002 n=6+6) DSEPassBlock-4 560kB ± 0% 4kB ± 0% -99.34% (p=0.026 n=5+6) CSEPass-4 189kB ± 0% 189kB ± 0% ~ (all equal) CSEPassBlock-4 3.10MB ± 0% 3.10MB ± 0% ~ (p=0.444 n=5+5) DeadcodePass-4 10.5kB ± 0% 10.5kB ± 0% ~ (all equal) DeadcodePassBlock-4 164kB ± 0% 164kB ± 0% ~ (all equal) MultiPass-4 240kB ± 0% 199kB ± 0% -17.06% (p=0.002 n=6+6) MultiPassBlock-4 3.60MB ± 0% 2.99MB ± 0% -17.06% (p=0.002 n=6+6) name old allocs/op new allocs/op delta DSEPass-4 8.00 ± 0% 4.00 ± 0% -50.00% (p=0.002 n=6+6) DSEPassBlock-4 240 ± 0% 120 ± 0% -50.00% (p=0.002 n=6+6) CSEPass-4 9.00 ± 0% 9.00 ± 0% ~ (all equal) CSEPassBlock-4 1.35k ± 0% 1.35k ± 0% ~ (all equal) DeadcodePass-4 3.00 ± 0% 3.00 ± 0% ~ (all equal) DeadcodePassBlock-4 9.00 ± 0% 9.00 ± 0% ~ (all equal) MultiPass-4 11.0 ± 0% 10.0 ± 0% -9.09% (p=0.002 n=6+6) MultiPassBlock-4 165 ± 0% 150 ± 0% -9.09% (p=0.002 n=6+6) Change-Id: I43860687c88f33605eb1415f36473c5cfe8fde4a Reviewed-on: https://go-review.googlesource.com/98449 Run-TryBot: Daniel Martí <mvdan@mvdan.cc> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Josh Bleecher Snyder <josharian@gmail.com>
2017-01-09[dev.inline] cmd/internal/src: introduce compact source position representationRobert Griesemer
XPos is a compact (8 instead of 16 bytes on a 64bit machine) source position representation. There is a 1:1 correspondence between each XPos and each regular Pos, translated via a global table. In some sense this brings back the LineHist, though positions can track line and column information; there is a O(1) translation between the representations (no binary search), and the translation is factored out. The size increase with the prior change is brought down again and the compiler speed is in line with the master repo (measured on the same "quiet" machine as for prior change): name old time/op new time/op delta Template 256ms ± 1% 262ms ± 2% ~ (p=0.063 n=5+4) Unicode 132ms ± 1% 135ms ± 2% ~ (p=0.063 n=5+4) GoTypes 891ms ± 1% 871ms ± 1% -2.28% (p=0.016 n=5+4) Compiler 3.84s ± 2% 3.89s ± 2% ~ (p=0.413 n=5+4) MakeBash 47.1s ± 1% 46.2s ± 2% ~ (p=0.095 n=5+5) name old user-ns/op new user-ns/op delta Template 309M ± 1% 314M ± 2% ~ (p=0.111 n=5+4) Unicode 165M ± 1% 172M ± 9% ~ (p=0.151 n=5+5) GoTypes 1.14G ± 2% 1.12G ± 1% ~ (p=0.063 n=5+4) Compiler 5.00G ± 1% 4.96G ± 1% ~ (p=0.286 n=5+4) Change-Id: Icc570cc60ab014d8d9af6976f1f961ab8828cc47 Reviewed-on: https://go-review.googlesource.com/34506 Run-TryBot: Robert Griesemer <gri@golang.org> Reviewed-by: Matthew Dempsky <mdempsky@google.com> Reviewed-by: Austin Clements <austin@google.com> TryBot-Result: Gobot Gobot <gobot@golang.org>
2016-12-09[dev.inline] cmd/internal/src: introduce NoPos and use it instead Pos{}Robert Griesemer
Using a variable instead of a composite literal makes the code independent of implementation changes of Pos. Per David Lazar's suggestion. Change-Id: I336967ac12a027c51a728a58ac6207cb5119af4a Reviewed-on: https://go-review.googlesource.com/34148 Run-TryBot: Robert Griesemer <gri@golang.org> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Matthew Dempsky <mdempsky@google.com>
2016-12-08[dev.inline] cmd/internal/src: make Pos implementation abstractRobert Griesemer
Adjust cmd/compile accordingly. This will make it easier to replace the underlying implementation. Change-Id: I33645850bb18c839b24785b6222a9e028617addb Reviewed-on: https://go-review.googlesource.com/34133 Reviewed-by: David Lazar <lazard@golang.org>
2016-12-08[dev.inline] cmd/compile: introduce cmd/internal/src.Pos type for line numbersRobert Griesemer
This is a step toward chosing a different position representation. By introducing an explicit type, it will be easier to make the transition step-wise while ensuring everything keeps running. This has been reviewed via https://go-review.googlesource.com/#/c/34025/. Change-Id: Ibceddcd62d8f346321ac3250e3940e9c436ed684 Reviewed-on: https://go-review.googlesource.com/34132 Run-TryBot: Robert Griesemer <gri@golang.org> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: David Lazar <lazard@golang.org>
2016-09-16cmd/compile: label LoadReg with line number of the useCherry Zhang
A tentative fix of #16380. It adds "line" everywhere... This also reduces binary size slightly (cmd/go on ARM as an example): before after total binary size 8068097 8018945 (-0.6%) .gopclntab 1195341 1179929 (-1.3%) .debug_line 689692 652017 (-5.5%) Change-Id: Ibda657c6999783c5bac180cbbba487006dbf0ed7 Reviewed-on: https://go-review.googlesource.com/25082 Reviewed-by: David Chase <drchase@google.com> Run-TryBot: Cherry Zhang <cherryyz@google.com> TryBot-Result: Gobot Gobot <gobot@golang.org>
2016-05-18cmd/compile: reduce element size of arrays in sparse{map,set}David Chase
sparseSet and sparseMap only need 32 bit integers in their arrays, since a sparseEntry key is also limited to 32 bits. This appears to reduce the space allocated for at least one pathological compilation by 1%, perhaps more. Not necessarily for 1.7, but it saves a little and is very low-risk. Change-Id: Icf1185859e9f5fe1261a206b441e02c34f7d02fd Reviewed-on: https://go-review.googlesource.com/22972 Run-TryBot: David Chase <drchase@google.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Keith Randall <khr@golang.org> Reviewed-by: Russ Cox <rsc@golang.org>
2016-04-13cmd/compile: move spills to loop exits when easy.David Chase
For call-free inner loops. Revised statistics: 85 inner loop spills sunk 341 inner loop spills remaining 1162 inner loop spills that were candidates for sinking ended up completely register allocated 119 inner loop spills could have been sunk were used in "shuffling" at the bottom of the loop. 1 inner loop spill not sunk because the register assigned changed between def and exit, Understanding how to make an inner loop definition not be a candidate for from-memory shuffling (to force the shuffle code to choose some other value) should pick up some of the 119 other spills disqualified for this reason. Modified the stats printing based on feedback from Austin. Change-Id: If3fb9b5d5a028f42ccc36c4e3d9e0da39db5ca60 Reviewed-on: https://go-review.googlesource.com/21037 Reviewed-by: Keith Randall <khr@golang.org> Run-TryBot: David Chase <drchase@google.com> TryBot-Result: Gobot Gobot <gobot@golang.org>
2015-11-12[dev.ssa] cmd/compile: better register allocationKeith Randall
Use a more precise computation of next use. It properly detects lifetime holes and deallocates values during those holes. It also uses a more precise version of distance to next use which affects which values get spilled. Change-Id: I49eb3ebe2d2cb64842ecdaa7fb4f3792f8afb90b Reviewed-on: https://go-review.googlesource.com/16760 Run-TryBot: Keith Randall <khr@golang.org> Reviewed-by: David Chase <drchase@google.com>
generated by cgit v1.3 (git 2.53.0) at 2026-04-15 23:58:42 +0000