cmd/compile/internal: merge stack slots for selected local auto vars

[This is a partial roll-forward of CL 553055, the main change here
is that the stack slot overlap operation is flagged off by default
(can be enabled by hand with -gcflags=-d=mergelocals=1) ]

Preliminary compiler support for merging/overlapping stack slots of
local variables whose access patterns are disjoint.

This patch includes changes in AllocFrame to do the actual
merging/overlapping based on information returned from a new
liveness.MergeLocals helper. The MergeLocals helper identifies
candidates by looking for sets of AUTO variables that either A) have
the same size and GC shape (if types contain pointers), or B) have the
same size (but potentially different types as long as those types have
no pointers). Variables must be greater than (3*types.PtrSize) in size
to be considered for merging.

After forming candidates, MergeLocals collects variables into "can be
overlapped" equivalence classes or partitions; this process is driven
by an additional liveness analysis pass. Ideally it would be nice to
move the existing stackmap liveness pass up before AllocFrame
and "widen" it to include merge candidates so that we can do just a
single liveness as opposed to two passes, however this may be difficult
given that the merge-locals liveness has to take into account
writes corresponding to dead stores.

This patch also required a change to the way ssa.OpVarDef pseudo-ops
are generated; prior to this point they would only be created for
variables whose type included pointers; if stack slot merging is
enabled then the ssagen code creates OpVarDef ops for all auto vars
that are merge candidates.

Note that some temporaries created late in the compilation process
(e.g. during ssa backend) are difficult to reason about, especially in
cases where we take the address of a temp and pass it to the runtime.
For the time being we mark most of the vars created post-ssagen as
"not a merge candidate".

Stack slot merging for locals/autos is enabled by default if "-N" is
not in effect, and can be disabled via "-gcflags=-d=mergelocals=0".

Fixmes/todos/restrictions:
- try lowering size restrictions
- re-evaluate the various skips that happen in SSA-created autotmps

Updates #62737.
Updates #65532.
Updates #65495.

Change-Id: Ifda26bc48cde5667de245c8a9671b3f0a30bb45d
Reviewed-on: https://go-review.googlesource.com/c/go/+/575415
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Reviewed-by: Cherry Mui <cherryyz@google.com>

1 files changed, 83 insertions, 0 deletions

diff --git a/src/cmd/compile/internal/test/testdata/mergelocals/integration.go b/src/cmd/compile/internal/test/testdata/mergelocals/integration.go
new file mode 100644
index 0000000000..d640c6fce8
--- /dev/null
+++ b/src/cmd/compile/internal/test/testdata/mergelocals/integration.go
@@ -0,0 +1,83 @@
+// Copyright 2024 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package p
+
+// This type and the following one will share the same GC shape and size.
+type Pointery struct {
+	p *Pointery
+	x [1024]int
+}
+
+type Pointery2 struct {
+	p *Pointery2
+	x [1024]int
+}
+
+// This type and the following one will have the same size.
+type Vanilla struct {
+	np uintptr
+	x  [1024]int
+}
+
+type Vanilla2 struct {
+	np uintptr
+	x  [1023]int
+	y  int
+}
+
+type Single struct {
+	np uintptr
+	x  [1023]int
+}
+
+func ABC(i, j int) int {
+	r := 0
+
+	// here v1 interferes with v2 but could be overlapped with v3.
+	// we can also overlap v1 with v3.
+	var v1 Vanilla
+	if i < 101 {
+		var v2 Vanilla
+		v1.x[i] = j
+		r += v1.x[j]
+		v2.x[i] = j
+		r += v2.x[j]
+	}
+
+	{
+		var v3 Vanilla2
+		v3.x[i] = j
+		r += v3.x[j]
+	}
+
+	var s Single
+	s.x[i] = j
+	r += s.x[j]
+
+	// Here p1 and p2 interfere, but p1 could be overlapped with xp3.
+	var p1, p2 Pointery
+	p1.x[i] = j
+	r += p1.x[j]
+	p2.x[i] = j
+	r += p2.x[j]
+	{
+		var xp3 Pointery2
+		xp3.x[i] = j
+		r += xp3.x[j]
+	}
+
+	if i == j*2 {
+		// p2 live on this path
+		p2.x[i] += j
+		r += p2.x[j]
+	} else {
+		// p2 not live on this path
+		var xp4 Pointery2
+		xp4.x[i] = j
+		r += xp4.x[j]
+	}
+
+	return r
+}