cmd/compile: improve stp merging for non-sequent cases

Original algorithm merges stores with the first
mergeable store in the chain, but it misses some
cases. Additional reordering stores in increasing order
of memory access in the chain allows merging in these cases.

Fixes #71987

There are the results of sweet benchmarks and
the difference between sizes of sections .text

                        │ old.results │            new.results             │
                        │   sec/op    │   sec/op     vs base               │
BleveIndexBatch100-4      7.614 ± 2%    7.548 ± 1%       ~ (p=0.190 n=10)
ESBuildThreeJS-4         821.3m ± 0%   819.0m ± 1%       ~ (p=0.165 n=10)
ESBuildRomeTS-4          206.2m ± 1%   204.4m ± 1%  -0.90% (p=0.023 n=10)
EtcdPut-4                64.89m ± 1%   64.94m ± 2%       ~ (p=0.684 n=10)
EtcdSTM-4                318.4m ± 0%   319.2m ± 1%       ~ (p=0.631 n=10)
GoBuildKubelet-4          157.4 ± 0%    157.6 ± 0%       ~ (p=0.105 n=10)
GoBuildKubeletLink-4      12.42 ± 2%    12.41 ± 1%       ~ (p=0.529 n=10)
GoBuildIstioctl-4         124.4 ± 0%    124.4 ± 0%       ~ (p=0.579 n=10)
GoBuildIstioctlLink-4     8.700 ± 1%    8.693 ± 1%       ~ (p=0.912 n=10)
GoBuildFrontend-4         46.52 ± 0%    46.50 ± 0%       ~ (p=0.971 n=10)
GoBuildFrontendLink-4     2.282 ± 1%    2.272 ± 1%       ~ (p=0.529 n=10)
GoBuildTsgo-4             75.02 ± 1%    75.31 ± 1%       ~ (p=0.436 n=10)
GoBuildTsgoLink-4         1.229 ± 1%    1.219 ± 1%  -0.82% (p=0.035 n=10)
GopherLuaKNucleotide-4    34.77 ± 5%    34.31 ± 1%  -1.33% (p=0.015 n=10)
MarkdownRenderXHTML-4    286.6m ± 0%   285.7m ± 1%       ~ (p=0.315 n=10)
Tile38QueryLoad-4        657.2µ ± 1%   660.3µ ± 0%       ~ (p=0.436 n=10)
geomean                   2.570         2.563       -0.24%

Executable            Old .text  New .text     Change
-------------------------------------------------------
benchmark               6504820    6504020     -0.01%
bleve-index-bench       3903860    3903636     -0.01%
esbuild                 4801012    4801172     +0.00%
esbuild-bench           1256404    1256340     -0.01%
etcd                    9188148    9187076     -0.01%
etcd-bench              6462228    6461524     -0.01%
go                      5924468    5923892     -0.01%
go-build-bench          1282004    1281940     -0.00%
gopher-lua-bench        1639540    1639348     -0.01%
markdown-bench          1478452    1478356     -0.01%
tile38-bench            2753524    2753300     -0.01%
tile38-server          10241380   10240068     -0.01%

Change-Id: Ieb4fdfd656aca458f65fc45938de70550632bd13
Reviewed-on: https://go-review.googlesource.com/c/go/+/698097
Reviewed-by: Keith Randall <khr@golang.org>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Auto-Submit: Keith Randall <khr@golang.org>
Reviewed-by: Mark Freeman <markfreeman@google.com>
Reviewed-by: Keith Randall <khr@google.com>

1 files changed, 19 insertions, 2 deletions

diff --git a/test/codegen/memcombine.go b/test/codegen/memcombine.go
index fa0e902ac2..9457d15f6a 100644
--- a/test/codegen/memcombine.go
+++ b/test/codegen/memcombine.go
@@ -1053,17 +1053,34 @@ func dwstoreF32(p *struct{ a, b float32 }, x, y float32) {
 }
 
 func dwstoreBig(p *struct{ a, b, c, d, e, f int64 }, a, b, c, d, e, f int64) {
-	// This is not perfect. We merge b+a, then d+e, then c and f have no pair.
+	// arm64:`STP\s\(R[0-9]+, R[0-9]+\), 16\(R[0-9]+\)`
 	p.c = c
+	// arm64:`STP\s\(R[0-9]+, R[0-9]+\), 32\(R[0-9]+\)`
 	p.f = f
 	// arm64:`STP\s\(R[0-9]+, R[0-9]+\), \(R[0-9]+\)`
 	p.a = a
-	// arm64:`STP\s\(R[0-9]+, R[0-9]+\), 24\(R[0-9]+\)`
 	p.e = e
 	p.d = d
 	p.b = b
 }
 
+func dwstoreUnorderedArray(p *struct{ a, b, c, d int }, a, b, c, d int) {
+	// arm64:`STP\s\(R[0-9]+, R[0-9]+\), 16\(R[0-9]+\)`
+	p.c = c
+	p.d = d
+	// arm64:`STP\s\(R[0-9]+, R[0-9]+\), \(R[0-9]+\)`
+	p.a = a
+	p.b = b
+}
+
+func dwstoreBigNil(p *struct{ i, j struct{ a, b, c int } }) {
+	// arm64:`STP\s\(ZR, ZR\), 32\(R[0-9]+\)`
+	// arm64:`STP\s\(ZR, ZR\), 16\(R[0-9]+\)`
+	p.j = struct{ a, b, c int }{}
+	// arm64:`STP\s\(ZR, ZR\), \(R[0-9]+\)`
+	p.i = struct{ a, b, c int }{}
+}
+
 func dwstoreRet() [2]int {
 	// arm64:"STP\t"
 	return [2]int{5, 6}