Escape analysis has a hard time with tree-like
structures (see #13493 and #14858).
This is unlikely to change.
As a result, when invoking a function that accepts
a **Node parameter, we usually allocate a *Node
on the heap. This happens a whole lot.

This CL changes functions from taking a **Node
to acting more like append: It both modifies
the input and returns a replacement for it.

Because of the cascading nature of escape analysis,
in order to get the benefits, I had to modify
almost all such functions. The remaining functions
are in racewalk and the backend. I would be happy
to update them as well in a separate CL.

This CL was created by manually updating the
function signatures and the directly impacted
bits of code. The callsites were then automatically
updated using a bespoke script:
https://gist.github.com/josharian/046b1be7aceae244de39

For ease of reviewing and future understanding,
this CL is also broken down into four CLs,
mailed separately, which show the manual
and the automated changes separately.
They are CLs 20990, 20991, 20992, and 20993.

Passes toolstash -cmp.

name       old time/op     new time/op     delta
Template       335ms ± 5%      324ms ± 5%   -3.35%        (p=0.000 n=23+24)
Unicode        176ms ± 9%      165ms ± 6%   -6.12%        (p=0.000 n=23+24)
GoTypes        1.10s ± 4%      1.07s ± 2%   -2.77%        (p=0.000 n=24+24)
Compiler       5.31s ± 3%      5.15s ± 3%   -2.95%        (p=0.000 n=24+24)
MakeBash       41.6s ± 1%      41.7s ± 2%     ~           (p=0.586 n=23+23)

name       old alloc/op    new alloc/op    delta
Template      63.3MB ± 0%     62.4MB ± 0%   -1.36%        (p=0.000 n=25+23)
Unicode       42.4MB ± 0%     41.6MB ± 0%   -1.99%        (p=0.000 n=24+25)
GoTypes        220MB ± 0%      217MB ± 0%   -1.11%        (p=0.000 n=25+25)
Compiler       994MB ± 0%      973MB ± 0%   -2.08%        (p=0.000 n=24+25)

name       old allocs/op   new allocs/op   delta
Template        681k ± 0%       574k ± 0%  -15.71%        (p=0.000 n=24+25)
Unicode         518k ± 0%       413k ± 0%  -20.34%        (p=0.000 n=25+24)
GoTypes        2.08M ± 0%      1.78M ± 0%  -14.62%        (p=0.000 n=25+25)
Compiler       9.26M ± 0%      7.64M ± 0%  -17.48%        (p=0.000 n=25+25)

name       old text-bytes  new text-bytes  delta
HelloSize       578k ± 0%       578k ± 0%     ~     (all samples are equal)
CmdGoSize      6.46M ± 0%      6.46M ± 0%     ~     (all samples are equal)

name       old data-bytes  new data-bytes  delta
HelloSize       128k ± 0%       128k ± 0%     ~     (all samples are equal)
CmdGoSize       281k ± 0%       281k ± 0%     ~     (all samples are equal)

name       old exe-bytes   new exe-bytes   delta
HelloSize       921k ± 0%       921k ± 0%     ~     (all samples are equal)
CmdGoSize      9.86M ± 0%      9.86M ± 0%     ~     (all samples are equal)

Change-Id: I277d95bd56d51c166ef7f560647aeaa092f3f475
Reviewed-on: https://go-review.googlesource.com/20959Reviewed-by: Dave Cheney <dave@cheney.net>
Reviewed-by: Ian Lance Taylor <iant@golang.org>

These new methods help find the compilation unit to pass to the
LineReader method in order to find the line information for a PC.
The Ranges method also helps identify the specific function for a PC,
needed to determine the function name.

This uses the .debug.ranges section if necessary, and changes the object
file format packages to pass in the section contents if available.

Change-Id: I5ebc3d27faaf1a126ffb17a1e6027efdf64af836
Reviewed-on: https://go-review.googlesource.com/20769Reviewed-by: Austin Clements <austin@google.com>
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>

Change-Id: I64dd09e76d811000a914776fdad47808e3895690
Reviewed-on: https://go-review.googlesource.com/20989Reviewed-by: Dave Cheney <dave@cheney.net>

Required to pass the issue9400 test.

Change-Id: I595223c403b12faade54e2e46510f8537150af39
Reviewed-on: https://go-review.googlesource.com/20940Reviewed-by: Ian Lance Taylor <iant@golang.org>
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>

Change-Id: I81376f524e76db25fd52cc5bec2c80fbf618a0c5
Reviewed-on: https://go-review.googlesource.com/20877Reviewed-by: Minux Ma <minux@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>

Adds a new R_PCRELDBL relocation for 2-byte aligned relative
relocations on s390x. Should be removed once #14218 is
implemented.

Change-Id: I79dd2d8e746ba8cbc26c570faccfdd691e8161e8
Reviewed-on: https://go-review.googlesource.com/20941Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>

There is a special case for slicing s[i:j] when the resulting
slice has zero capacity, to prevent pointing to the next object
in memory.

Change this special case code from:
  rptr := rcap == 0 ? ptr : ptr+i*elemsize
to
  rptr := ptr + (rcap == 0 ? 0 : i) * elemsize

This change leads to slightly smaller generated code, replacing
a load with a register zero.

old:
	0x002e 00046 (slice.go:8)	CMPQ	BX, $0
	0x0032 00050 (slice.go:8)	JEQ	$0, 78
	0x0034 00052 (slice.go:8)	MOVQ	"".a+8(FP), BP
	0x0039 00057 (slice.go:8)	LEAQ	(BP)(CX*8), AX
	0x003e 00062 ... rest of function ...

	0x004e 00078 (slice.go:7)	MOVQ	"".a+8(FP), AX
	0x0053 00083 (slice.go:8)	JMP	62

new:
	0x002e 00046 (slice.go:8)	CMPQ	BX, $0
	0x0032 00050 (slice.go:8)	JEQ	$0, 78
	0x0034 00052 (slice.go:8)	MOVQ	"".a+8(FP), BP
	0x0039 00057 (slice.go:8)	LEAQ	(BP)(CX*8), AX
	0x003e 00062 ... rest of function...

	0x004e 00078 (slice.go:8)	MOVQ	$0, CX
	0x0050 00080 (slice.go:8)	JMP	52

Change-Id: I2a396616b0d7b090c226a47c92a7ba14b128401f
Reviewed-on: https://go-review.googlesource.com/20994Reviewed-by: David Chase <drchase@google.com>

Fixes #14901

Change-Id: Ia32e09767374a341c9a36c5d977d47d7d1a82315
Reviewed-on: https://go-review.googlesource.com/20967Reviewed-by: Ian Lance Taylor <iant@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Run-TryBot: David Crawshaw <crawshaw@golang.org>

Should let the s390x builder progress a little further.

Change-Id: I5eab5f384b0b039f8e246ba69ecfb24de08625d2
Reviewed-on: https://go-review.googlesource.com/20965Reviewed-by: Minux Ma <minux@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>

Allow names to be used for subexpressions of match rules.
For example:

(OpA x:(OpB y)) -> ..use x here to refer to the OpB value..

This gets rid of the .Args[0].Args[0]... way of naming we
used to use.

While we're here, give all subexpression matches names instead
of recomputing them with .Args[i] sequences each time they
are referenced.  Makes the generated rule code a bit smaller.

Change-Id: Ie42139f6f208933b75bd2ae8bd34e95419bc0e4e
Reviewed-on: https://go-review.googlesource.com/20997
Run-TryBot: Todd Neal <todd@tneal.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Todd Neal <todd@tneal.org>

Don't write back parts of a slicing operation if they
are unchanged from the source of the slice.  For example:

x.s = x.s[0:5]         // don't write back pointer or cap
x.s = x.s[:5]          // don't write back pointer or cap
x.s = x.s[:5:7]        // don't write back pointer

There is more to be done here, for example:

x.s = x.s[:len(x.s):7] // don't write back ptr or len

This CL can't handle that one yet.

Fixes #14855

Change-Id: Id1e1a4fa7f3076dc1a76924a7f1cd791b81909bb
Reviewed-on: https://go-review.googlesource.com/20954Reviewed-by: Austin Clements <austin@google.com>
Run-TryBot: Keith Randall <khr@golang.org>

For the following example, but there are a few more in the stdlib:
func histogram(b []byte, h *[256]int32) {
        for _, t := range b {
                h[t]++
        }
}

Change-Id: I56615f341ae52e02ef34025588dc6d1c52122295
Reviewed-on: https://go-review.googlesource.com/20924Reviewed-by: Keith Randall <khr@golang.org>
Run-TryBot: Alexandru Moșoi <alexandru@mosoi.ro>
TryBot-Result: Gobot Gobot <gobot@golang.org>

Allow inlining of functions with switch statements as long as they don't
contain a break or type switch.

Fixes #13071

Change-Id: I057be351ea4584def1a744ee87eafa5df47a7f6d
Reviewed-on: https://go-review.googlesource.com/20824Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>

Converting a big.Float value x to a float32/64 value did not correctly
round x up to the smallest denormal float32/64 if x was smaller than the
smallest denormal float32/64, but larger than 0.5 of a smallest denormal
float32/64.

Handle this case explicitly and simplify some code in the turn.

For #14651.

Change-Id: I025e24bf8f0e671581a7de0abf7c1cd7e6403a6c
Reviewed-on: https://go-review.googlesource.com/20816
Run-TryBot: Robert Griesemer <gri@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Alan Donovan <adonovan@google.com>

The inserted early bound checks cause the slice
to expand beyond the original length of the slice.

Change-Id: Ib38891605f4a9a12d3b9e2071a5f77640b083d2d
Reviewed-on: https://go-review.googlesource.com/20981Reviewed-by: Keith Randall <khr@golang.org>
Reviewed-by: Minux Ma <minux@golang.org>

MOVSB is quite a bit faster for unaligned moves.
Possibly we should use MOVSB all of the time, but Intel folks
say it might be a bit faster to use MOVSQ on some processors
(but not any I have access to at the moment).

benchmark                              old ns/op     new ns/op     delta
BenchmarkMemmove4096-8                 93.9          93.2          -0.75%
BenchmarkMemmoveUnalignedDst4096-8     256           151           -41.02%
BenchmarkMemmoveUnalignedSrc4096-8     175           90.5          -48.29%

Fixes #14630

Change-Id: I568e6d6590eb3615e6a699fb474020596be665ff
Reviewed-on: https://go-review.googlesource.com/20293Reviewed-by: Ian Lance Taylor <iant@golang.org>

Passes toolstash -cmp.

Change-Id: I8725dee490778be9c1fd31990a6b27df9713c3c9
Reviewed-on: https://go-review.googlesource.com/20957Reviewed-by: Ian Lance Taylor <iant@golang.org>

Left over from CL 20931.

Change-Id: I3b8dd9ef748bcbf70b5118da28135aaa1e5ba3a8
Reviewed-on: https://go-review.googlesource.com/20955
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
Reviewed-by: Minux Ma <minux@golang.org>

Constant comparisons against 0 are reasonably common.
Special-case and avoid allocating a new zero value each time.

Change-Id: I6c526c8ab30ef7f0fef59110133c764b7b90ba05
Reviewed-on: https://go-review.googlesource.com/20956Reviewed-by: Alan Donovan <adonovan@google.com>

Also give them more idiomatic Go names. Adding godocs is outside the
scope of this CL. (Besides, the method names almost all directly
parallel an underlying math/big.Int or math/big.Float method.)

CL prepared mechanically with sed (for rewriting mpint.go/mpfloat.go)
and gofmt (for rewriting call sites).

Passes toolstash -cmp.

Change-Id: Id76f4aee476ba740f48db33162463e7978c2083d
Reviewed-on: https://go-review.googlesource.com/20909
Run-TryBot: Matthew Dempsky <mdempsky@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Robert Griesemer <gri@golang.org>

Fixed bug that slipped probably slipped in after rebasing and
explain why it failed on nacl/netbsd/plan9, which set default
maxparallelism to 1.

Change-Id: I4d59682fb2843d138b320334189f53fcdda5b2f6
Reviewed-on: https://go-review.googlesource.com/20980
Run-TryBot: Russ Cox <rsc@golang.org>
Reviewed-by: Russ Cox <rsc@golang.org>

Fixes #14890.

Change-Id: Ie790276b0e2ef94c92db3a777042d750269f876a
Reviewed-on: https://go-review.googlesource.com/20953Reviewed-by: Alan Donovan <adonovan@google.com>

The Linux ABI takes arguments in a different order on s390x.

Change-Id: Ic9cfcc22a5ea3d8ef77d4dd0b915fc266ff3e5f7
Reviewed-on: https://go-review.googlesource.com/20960Reviewed-by: Ian Lance Taylor <iant@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>

Minimum architecture of z196 required so that GCC can assemble
gcc_s390x.S in runtime/cgo.

Change-Id: I603ed2edd39f826fb8193740ece5bd11d18c3dc5
Reviewed-on: https://go-review.googlesource.com/20876Reviewed-by: Ian Lance Taylor <iant@golang.org>

Updates #10848

Change-Id: I8353100ed01cb0e8fc19225157f5709bae388612
Reviewed-on: https://go-review.googlesource.com/20975Reviewed-by: Rob Pike <r@golang.org>

Fixes this test on s390x.

Change-Id: Ie5b70e8191169867765ec9248d827ca12c6405f4
Reviewed-on: https://go-review.googlesource.com/20964Reviewed-by: Minux Ma <minux@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>

Change-Id: I928532b406a3457d2c5f75f4de7d46a3f795192e
Reviewed-on: https://go-review.googlesource.com/20939Reviewed-by: Minux Ma <minux@golang.org>
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>

It was just a funny way of saying len(Ctxt.Allsym) by now.

Change-Id: Iff75e73c9f7ec4ba26cfef479bbd05d7dcd172f5
Reviewed-on: https://go-review.googlesource.com/20973
Run-TryBot: Michael Hudson-Doyle <michael.hudson@canonical.com>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>

Nothing cares about it.

I did this after looking at the memprof output, but it helps performance a bit:

name       old s/op    new s/op    delta
LinkCmdGo   0.44 ± 3%   0.43 ± 3%  -2.20%   (p=0.000 n=94+90)
LinkJuju    3.98 ± 5%   3.94 ± 5%  -1.19%  (p=0.000 n=100+91)

As well as MaxRSS (i.e. what /usr/bin/time -f '%M' prints):

name       old MaxRSS  new MaxRSS  delta
LinkCmdGo   130k ± 0%   120k ± 3%  -7.79%   (p=0.000 n=79+90)
LinkJuju    862k ± 6%   827k ± 8%  -4.01%  (p=0.000 n=100+99)

Change-Id: I6306b7b3369576a688659e2ecdb0815b4152ae96
Reviewed-on: https://go-review.googlesource.com/20972
Run-TryBot: Michael Hudson-Doyle <michael.hudson@canonical.com>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>

Change-Id: I0ea74dc1b11fad8ded9e649a3c1e4213ea6639b8
Reviewed-on: https://go-review.googlesource.com/20974
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>

Change-Id: Iedd01ef3a9d2831cb55c53b7a1984e7e932f4249
Reviewed-on: https://go-review.googlesource.com/20932Reviewed-by: Ian Lance Taylor <iant@golang.org>

Introduce garbage-free LookupN to replace most users of Lookupf.

Also, remove the string interning from LookupBytes which was hurting
more than helping.

name       old alloc/op    new alloc/op    delta
Template      63.0MB ± 0%     62.7MB ± 0%  -0.48%         (p=0.000 n=10+9)
Unicode       43.0MB ± 0%     43.0MB ± 0%  -0.17%         (p=0.000 n=10+7)
GoTypes        219MB ± 0%      218MB ± 0%  -0.14%        (p=0.000 n=10+10)
Compiler       992MB ± 0%      991MB ± 0%  -0.12%        (p=0.000 n=10+10)

name       old allocs/op   new allocs/op   delta
Template        683k ± 0%       681k ± 0%  -0.38%         (p=0.000 n=10+8)
Unicode         541k ± 0%       541k ± 0%  -0.11%        (p=0.000 n=10+10)
GoTypes        2.09M ± 0%      2.08M ± 0%  -0.40%        (p=0.000 n=10+10)
Compiler       9.28M ± 0%      9.24M ± 0%  -0.36%        (p=0.000 n=10+10)

Size of $GOROOT/pkg/darwin_amd64 drops from 40124 KB to 40100 KB too,
removing the zero padding as suggested by josharian.

Updates #6853

Change-Id: I3c557266e9325fe29c459cef8e5b8954913e7abb
Reviewed-on: https://go-review.googlesource.com/20931Reviewed-by: Josh Bleecher Snyder <josharian@gmail.com>
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>

Allows the compiler to recognise s390x specific files and s390x
build tags.

Change-Id: I7c62ab7361cf708181b1d9cfbe9b1fcb01be31e0
Reviewed-on: https://go-review.googlesource.com/20872Reviewed-by: Minux Ma <minux@golang.org>
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>

This deletes unused code and helpers from tests.

Change-Id: Ie31d46115f558ceb8da6efbf90c3c204e03b0d7e
Reviewed-on: https://go-review.googlesource.com/20927Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>

An instruction consisting of all 0s causes an illegal instruction
signal on s390x. Since 0s are the default in this test this CL just
makes it explicit.

Change-Id: Id6e060eed1a588f4b10a4e4861709fcd19b434ac
Reviewed-on: https://go-review.googlesource.com/20962Reviewed-by: Minux Ma <minux@golang.org>
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>

Change-Id: I39aa6569c9a6f327f7aaa01f8b4ace814fd5b766
Reviewed-on: https://go-review.googlesource.com/20943Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>

Debugasm can never be set in cmd/link, so delete it and the code it enables.

Change-Id: If828db0b09f1a9e512dc660ac2750657a769094c
Reviewed-on: https://go-review.googlesource.com/20971
Run-TryBot: Michael Hudson-Doyle <michael.hudson@canonical.com>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>

This expression in readsym:

    dup != nil && len(dup.P) > 0 && strings.HasPrefix(s.Name, "gclocals·")

can never be true: if dup != nil, then s.Name is ".dup" (and this is not new:
the same broken logic is present in 1.4, at least). Delete the whole block.

Change-Id: I33b14d9a82b292116d6fd79d22b38e3842501317
Reviewed-on: https://go-review.googlesource.com/20970
Run-TryBot: Michael Hudson-Doyle <michael.hudson@canonical.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>

The obj.Nocache helper was only used by the arm back end, move it there.

Change-Id: I5c9faf995499991ead1f3d8c8ffc3b6af7346876
Reviewed-on: https://go-review.googlesource.com/20868Reviewed-by: Ian Lance Taylor <iant@golang.org>
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>

Add a special helper for its one external use.

This is in preparation for an upcoming CL.

Passes toolstash -cmp / buildall.

Change-Id: I9d3463792afe220cc4bc89269bdecf0279abd281
Reviewed-on: https://go-review.googlesource.com/20933
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Ian Lance Taylor <iant@golang.org>