cmd/compile: allocate backing store for append on the stack

When appending, if the backing store doesn't escape and a
constant-sized backing store is big enough, use a constant-sized
stack-allocated backing store instead of allocating it from the heap.

cmd/go is <0.1% bigger.

As an example of how this helps, if you edit strings/strings.go:FieldsFunc
to replace
    spans := make([]span, 0, 32)
with
    var spans []span

then this CL removes the first 2 allocations that are part of the growth sequence:

                            │    base      │                 exp                  │
                            │  allocs/op   │  allocs/op   vs base                 │
FieldsFunc/ASCII/16-24         3.000 ± ∞ ¹   2.000 ± ∞ ¹  -33.33% (p=0.008 n=5)
FieldsFunc/ASCII/256-24        7.000 ± ∞ ¹   5.000 ± ∞ ¹  -28.57% (p=0.008 n=5)
FieldsFunc/ASCII/4096-24      11.000 ± ∞ ¹   9.000 ± ∞ ¹  -18.18% (p=0.008 n=5)
FieldsFunc/ASCII/65536-24      18.00 ± ∞ ¹   16.00 ± ∞ ¹  -11.11% (p=0.008 n=5)
FieldsFunc/ASCII/1048576-24    30.00 ± ∞ ¹   28.00 ± ∞ ¹   -6.67% (p=0.008 n=5)
FieldsFunc/Mixed/16-24         2.000 ± ∞ ¹   2.000 ± ∞ ¹        ~ (p=1.000 n=5)
FieldsFunc/Mixed/256-24        7.000 ± ∞ ¹   5.000 ± ∞ ¹  -28.57% (p=0.008 n=5)
FieldsFunc/Mixed/4096-24      11.000 ± ∞ ¹   9.000 ± ∞ ¹  -18.18% (p=0.008 n=5)
FieldsFunc/Mixed/65536-24      18.00 ± ∞ ¹   16.00 ± ∞ ¹  -11.11% (p=0.008 n=5)
FieldsFunc/Mixed/1048576-24    30.00 ± ∞ ¹   28.00 ± ∞ ¹   -6.67% (p=0.008 n=5)

(Of course, people have spotted and fixed a bunch of allocation sites
like this, but now we're ~automatically doing it everywhere going forward.)

No significant increases in frame sizes in cmd/go.

Change-Id: I301c4d9676667eacdae0058960321041d173751a
Reviewed-on: https://go-review.googlesource.com/c/go/+/664299
Reviewed-by: Keith Randall <khr@google.com>
Reviewed-by: Cherry Mui <cherryyz@google.com>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Auto-Submit: Keith Randall <khr@golang.org>

1 files changed, 25 insertions, 1 deletions

diff --git a/src/runtime/runtime_test.go b/src/runtime/runtime_test.go
index f23581acbe..0f2998b35b 100644
--- a/src/runtime/runtime_test.go
+++ b/src/runtime/runtime_test.go
@@ -9,6 +9,7 @@ import (
 	"fmt"
 	"internal/cpu"
 	"internal/runtime/atomic"
+	"internal/testenv"
 	"io"
 	"math/bits"
 	. "runtime"
@@ -307,7 +308,7 @@ func TestTrailingZero(t *testing.T) {
 	}
 }
 
-func TestAppendGrowth(t *testing.T) {
+func TestAppendGrowthHeap(t *testing.T) {
 	var x []int64
 	check := func(want int) {
 		if cap(x) != want {
@@ -324,6 +325,29 @@ func TestAppendGrowth(t *testing.T) {
 			want = 2 * i
 		}
 	}
+	Escape(&x[0]) // suppress stack-allocated backing store
+}
+
+func TestAppendGrowthStack(t *testing.T) {
+	var x []int64
+	check := func(want int) {
+		if cap(x) != want {
+			t.Errorf("len=%d, cap=%d, want cap=%d", len(x), cap(x), want)
+		}
+	}
+
+	check(0)
+	want := 32 / 8 // 32 is the default for cmd/compile/internal/base.DebugFlags.VariableMakeThreshold
+	if Raceenabled || testenv.OptimizationOff() {
+		want = 1
+	}
+	for i := 1; i <= 100; i++ {
+		x = append(x, 1)
+		check(want)
+		if i&(i-1) == 0 {
+			want = max(want, 2*i)
+		}
+	}
 }
 
 var One = []int64{1}