When inlining a closure with captured variables, walk up the
param chain to find the one that is defined inside the scope
into which the function is being inlined, and map occurrences
of the captures to temporary inlvars, similarly to what is
done for function parameters.

No noticeable impact on compilation speed and binary size.

Minor improvements to go1 benchmarks on darwin/amd64

name                     old time/op    new time/op    delta
BinaryTree17-4              2.59s ± 3%     2.58s ± 1%    ~     (p=0.470 n=19+19)
Fannkuch11-4                3.15s ± 2%     3.15s ± 1%    ~     (p=0.647 n=20+19)
FmtFprintfEmpty-4          43.7ns ± 3%    43.4ns ± 4%    ~     (p=0.178 n=18+20)
FmtFprintfString-4         74.0ns ± 2%    77.1ns ± 7%  +4.13%  (p=0.000 n=20+20)
FmtFprintfInt-4            77.2ns ± 3%    79.2ns ± 6%  +2.53%  (p=0.000 n=20+20)
FmtFprintfIntInt-4          112ns ± 4%     112ns ± 2%    ~     (p=0.672 n=20+19)
FmtFprintfPrefixedInt-4     136ns ± 1%     135ns ± 2%    ~     (p=0.827 n=16+20)
FmtFprintfFloat-4           232ns ± 2%     233ns ± 1%    ~     (p=0.194 n=20+20)
FmtManyArgs-4               490ns ± 2%     484ns ± 2%  -1.28%  (p=0.001 n=20+20)
GobDecode-4                6.68ms ± 2%    6.72ms ± 2%    ~     (p=0.113 n=20+19)
GobEncode-4                5.62ms ± 2%    5.71ms ± 2%  +1.64%  (p=0.000 n=20+19)
Gzip-4                      235ms ± 3%     236ms ± 2%    ~     (p=0.607 n=20+19)
Gunzip-4                   37.1ms ± 2%    36.8ms ± 3%    ~     (p=0.060 n=20+20)
HTTPClientServer-4         61.9µs ± 2%    62.7µs ± 4%  +1.24%  (p=0.007 n=18+19)
JSONEncode-4               12.5ms ± 2%    12.4ms ± 3%    ~     (p=0.192 n=20+20)
JSONDecode-4               51.6ms ± 3%    51.0ms ± 3%  -1.19%  (p=0.008 n=20+19)
Mandelbrot200-4            4.12ms ± 6%    4.06ms ± 5%    ~     (p=0.063 n=20+20)
GoParse-4                  3.12ms ± 5%    3.10ms ± 2%    ~     (p=0.402 n=19+19)
RegexpMatchEasy0_32-4      80.7ns ± 2%    75.1ns ± 9%  -6.94%  (p=0.000 n=17+20)
RegexpMatchEasy0_1K-4       197ns ± 2%     186ns ± 2%  -5.43%  (p=0.000 n=20+20)
RegexpMatchEasy1_32-4      77.5ns ± 4%    71.9ns ± 7%  -7.25%  (p=0.000 n=20+18)
RegexpMatchEasy1_1K-4       341ns ± 3%     341ns ± 3%    ~     (p=0.732 n=20+20)
RegexpMatchMedium_32-4      113ns ± 2%     112ns ± 3%    ~     (p=0.102 n=20+20)
RegexpMatchMedium_1K-4     36.6µs ± 2%    35.8µs ± 2%  -2.26%  (p=0.000 n=18+20)
RegexpMatchHard_32-4       1.75µs ± 3%    1.74µs ± 2%    ~     (p=0.473 n=20+19)
RegexpMatchHard_1K-4       52.6µs ± 2%    52.0µs ± 3%  -1.15%  (p=0.005 n=20+20)
Revcomp-4                   381ms ± 4%     377ms ± 2%    ~     (p=0.067 n=20+18)
Template-4                 57.3ms ± 2%    57.7ms ± 2%    ~     (p=0.108 n=20+20)
TimeParse-4                 291ns ± 3%     292ns ± 2%    ~     (p=0.585 n=20+20)
TimeFormat-4                314ns ± 3%     315ns ± 1%    ~     (p=0.681 n=20+20)
[Geo mean]                 47.4µs         47.1µs       -0.73%

name                     old speed      new speed      delta
GobDecode-4               115MB/s ± 2%   114MB/s ± 2%    ~     (p=0.115 n=20+19)
GobEncode-4               137MB/s ± 2%   134MB/s ± 2%  -1.63%  (p=0.000 n=20+19)
Gzip-4                   82.5MB/s ± 3%  82.4MB/s ± 2%    ~     (p=0.612 n=20+19)
Gunzip-4                  523MB/s ± 2%   528MB/s ± 3%    ~     (p=0.060 n=20+20)
JSONEncode-4              155MB/s ± 2%   156MB/s ± 3%    ~     (p=0.192 n=20+20)
JSONDecode-4             37.6MB/s ± 3%  38.1MB/s ± 3%  +1.21%  (p=0.007 n=20+19)
GoParse-4                18.6MB/s ± 4%  18.7MB/s ± 2%    ~     (p=0.405 n=19+19)
RegexpMatchEasy0_32-4     396MB/s ± 2%   426MB/s ± 8%  +7.56%  (p=0.000 n=17+20)
RegexpMatchEasy0_1K-4    5.18GB/s ± 2%  5.48GB/s ± 2%  +5.79%  (p=0.000 n=20+20)
RegexpMatchEasy1_32-4     413MB/s ± 4%   444MB/s ± 6%  +7.46%  (p=0.000 n=20+19)
RegexpMatchEasy1_1K-4    3.00GB/s ± 3%  3.00GB/s ± 3%    ~     (p=0.678 n=20+20)
RegexpMatchMedium_32-4   8.82MB/s ± 2%  8.90MB/s ± 3%  +0.99%  (p=0.044 n=20+20)
RegexpMatchMedium_1K-4   28.0MB/s ± 2%  28.6MB/s ± 2%  +2.32%  (p=0.000 n=18+20)
RegexpMatchHard_32-4     18.3MB/s ± 3%  18.4MB/s ± 2%    ~     (p=0.482 n=20+19)
RegexpMatchHard_1K-4     19.5MB/s ± 2%  19.7MB/s ± 3%  +1.18%  (p=0.004 n=20+20)
Revcomp-4                 668MB/s ± 4%   674MB/s ± 2%    ~     (p=0.066 n=20+18)
Template-4               33.8MB/s ± 2%  33.6MB/s ± 2%    ~     (p=0.104 n=20+20)
[Geo mean]                124MB/s        126MB/s       +1.54%

Updates #15561
Updates #18270

Change-Id: I980086efe28b36aa27f81577065e2a729ff03d4e
Reviewed-on: https://go-review.googlesource.com/72490Reviewed-by: Hugues Bruant <hugues.bruant@gmail.com>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>
Run-TryBot: Daniel Martí <mvdan@mvdan.cc>
TryBot-Result: Gobot Gobot <gobot@golang.org>

CL 65071 enabled inlining for local closures with no captures.

To determine safety of inlining a call sites, we check whether the
variable holding the closure has any assignments after its original
definition.

Unfortunately, that check did not catch OAS2MAPR and OAS2DOTTYPE,
leading to incorrect inlining when a variable holding a closure was
subsequently reassigned through a type conversion or a 2-valued map
access.

There was another more subtle issue wherein reassignment check would
always return a false positive for closure calls inside other
closures. This was caused by the Name.Curfn field of local variables
pointing to the OCLOSURE node instead of the corresponding ODCLFUNC,
which resulted in reassigned walking an empty Nbody and thus never
seeing any reassignments.

This CL fixes these oversights and adds many more tests for closure
inlining which ensure not only that inlining triggers but also the
correctness of the resulting code.

Updates #15561

Change-Id: I74bdae849c4ecfa328546d6d62b512e8d54d04ce
Reviewed-on: https://go-review.googlesource.com/75770Reviewed-by: Hugues Bruant <hugues.bruant@gmail.com>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>

Previously, anytime we exported a function or method declaration
(which includes methods for every type transitively exported), we
included the inline function bodies, if any. However, in many cases,
it's impossible (or at least very unlikely) for the importing package
to call the method.

For example:

    package p
    type T int
    func (t T) M() { t.u() }
    func (t T) u() {}
    func (t T) v() {}

T.M and T.u are inlineable, and they're both reachable through calls
to T.M, which is exported. However, t.v is also inlineable, but cannot
be reached.

Exception: if p.T is embedded in another type q.U, p.T.v will be
promoted to q.U.v, and the generated wrapper function could have
inlined the call to p.T.v. However, in practice, this doesn't happen,
and a missed inlining opportunity doesn't affect correctness.

To implement this, this CL introduces an extra flood fill pass before
exporting to mark inline bodies that are actually reachable, so the
exporter can skip over methods like t.v.

This reduces Kubernetes build time (as measured by "time go build -a
k8s.io/kubernetes/cmd/...") on an HP Z620 measurably:

    == before ==
    real    0m44.658s
    user    11m19.136s
    sys     0m53.844s

    == after ==
    real    0m41.702s
    user    10m29.732s
    sys     0m50.908s

It also significantly cuts down the cost of enabling mid-stack
inlining (-l=4):

    == before (-l=4) ==
    real    1m19.236s
    user    20m6.528s
    sys     1m17.328s

    == after (-l=4) ==
    real    0m59.100s
    user    13m12.808s
    sys     0m58.776s

Updates #19348.

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

Eliminates lots of ad hoc code for recognizing the same thing in
different ways.

Passes toolstash-check.

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

Currently, benchmarking compile performance under -l=4 is confounded
by -l=2 enabling eager typechecking of unused inline function bodies
for debugging. This isn't logically an "inlining aggressiveness"
level, so instead move this logic under the -d umbrella flag.

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

Fixes #22342.

Change-Id: Ic942162e98dce5749e381a31d58b0bf16c7d6f98
Reviewed-on: https://go-review.googlesource.com/72132
Run-TryBot: Matthew Dempsky <mdempsky@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Austin Clements <austin@google.com>

Calls to a closure held in a local, non-escaping,
variable can be inlined, provided the closure body
can be inlined and the variable is never written to.

The current implementation has the following limitations:

 - closures with captured variables are not inlined because
   doing so naively triggers invariant violation in the SSA
   phase
 - re-assignment check is currently approximated by checking
   the Addrtaken property of the variable which should be safe
   but may miss optimization opportunities if the address is
   not used for a write before the invocation

Updates #15561

Change-Id: I508cad5d28f027bd7e933b1f793c14dcfef8b5a1
Reviewed-on: https://go-review.googlesource.com/65071
Run-TryBot: Daniel Martí <mvdan@mvdan.cc>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Hugues Bruant <hugues.bruant@gmail.com>
Reviewed-by: Keith Randall <khr@golang.org>

mkinlcall1 already guards against recursively inlining functions into
themselves, so there's no need to clear and restore fn.Func.Inl during
recursive inlining.

Passes toolstash-check.

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

We've supported inlining methods called as functions for a while now.

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

When debugging inliner with -m -m print cost of complex functions,
instead of simple "function too complex". This helps to understand,
how close to inlining is this particular function.

Change-Id: I6871f69b5b914d23fd0b43a24d7c6fc928f4b716
Reviewed-on: https://go-review.googlesource.com/63330
Run-TryBot: Ilya Tocar <ilya.tocar@intel.com>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>

Previously, after inlining a call, we made a second pass to rewrite
the AST's position information to record the inlined stack frame. The
call arguments were part of this AST, but it would be incorrect to
rewrite them too, so extra effort was made to temporarily remove them
while the position rewriting was done.

However, this extra logic was only done for regular arguments: it was
not done for receiver arguments. Consequently if m was inlined in
"f().m(g(), h())", g and h would have correct call frames, but f would
appear to be called by m.

The fix taken by this CL is to merge setpos into inlsubst and only
rewrite position information for nodes that were actually copied from
the original function AST body. As a side benefit, this eliminates an
extra AST pass and some AST walking code.

Fixes #21879.

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

Avoid counting nodes that don't generate code (eg, constants) against the
inlining budget.

Fixes #21749

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

Arguments to inlined calls are hidden from setPos as follows:

    args := as.Rlist
    as.Rlist.Set(nil)
    // setPos...
    as.Rlist.Set(args.Slice())

Previously, this code had no effect since the value of as was
overwritten by the assignment in the retvars loop.

Fixes #19799.

Change-Id: Iaf97259f82fdba8b236136337cc42b2774c7fef5
Reviewed-on: https://go-review.googlesource.com/44351
Run-TryBot: David Lazar <lazard@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>
Reviewed-by: Josh Bleecher Snyder <josharian@gmail.com>

Node.Used was written to from the backend
concurrently with reads of Node.Class
for the same ONAME Nodes.
I do not know why it was not failing consistently
under the race detector, but it is a race.

This is likely also a problem with Node.HasVal and Node.HasOpt.
They will be handled in a separate CL.

Fix Used by moving it to gc.Name and making it a separate bool.
There was one non-Name use of Used, marking OLABELs as used.
That is no longer needed, now that goto and label checking
happens early in the front end.

Leave the getters and setters in place,
to ease changing the representation in the future
(or changing to an interface!).

Updates #20144

Change-Id: I9bec7c6d33dcb129a4cfa9d338462ea33087f9f7
Reviewed-on: https://go-review.googlesource.com/42015
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>

Put it at position zero, since it is fairly hot.

This shrinks gc.Node into a smaller size class on 64 bit systems.

name        old time/op       new time/op       delta
Template          193ms ± 5%        192ms ± 3%    ~     (p=0.353 n=94+93)
Unicode          86.1ms ± 5%       85.0ms ± 4%  -1.23%  (p=0.000 n=95+98)
GoTypes           546ms ± 3%        544ms ± 4%  -0.40%  (p=0.007 n=94+97)
Compiler          2.56s ± 3%        2.54s ± 3%  -0.67%  (p=0.000 n=99+97)
SSA               5.13s ± 2%        5.10s ± 3%  -0.55%  (p=0.000 n=94+98)
Flate             122ms ± 6%        121ms ± 4%  -0.75%  (p=0.002 n=97+95)
GoParser          144ms ± 5%        144ms ± 4%    ~     (p=0.298 n=98+97)
Reflect           348ms ± 4%        349ms ± 4%    ~     (p=0.350 n=98+97)
Tar               105ms ± 5%        104ms ± 5%    ~     (p=0.154 n=96+98)
XML               200ms ± 5%        198ms ± 4%  -0.71%  (p=0.015 n=97+98)
[Geo mean]        330ms             328ms       -0.52%

name        old user-time/op  new user-time/op  delta
Template          229ms ±11%        224ms ± 7%  -2.16%  (p=0.001 n=100+87)
Unicode           109ms ± 5%        109ms ± 6%    ~     (p=0.897 n=96+91)
GoTypes           712ms ± 4%        709ms ± 4%    ~     (p=0.085 n=96+98)
Compiler          3.41s ± 3%        3.36s ± 3%  -1.43%  (p=0.000 n=98+98)
SSA               7.46s ± 3%        7.31s ± 3%  -2.02%  (p=0.000 n=100+99)
Flate             145ms ± 6%        143ms ± 6%  -1.11%  (p=0.001 n=99+97)
GoParser          177ms ± 5%        176ms ± 5%  -0.78%  (p=0.018 n=95+95)
Reflect           432ms ± 7%        435ms ± 9%    ~     (p=0.296 n=100+100)
Tar               121ms ± 7%        121ms ± 5%    ~     (p=0.072 n=100+95)
XML               241ms ± 4%        239ms ± 5%    ~     (p=0.085 n=97+99)
[Geo mean]        413ms             410ms       -0.73%

name        old alloc/op      new alloc/op      delta
Template         38.4MB ± 0%       37.7MB ± 0%  -1.85%  (p=0.008 n=5+5)
Unicode          30.1MB ± 0%       28.8MB ± 0%  -4.09%  (p=0.008 n=5+5)
GoTypes           112MB ± 0%        110MB ± 0%  -1.69%  (p=0.008 n=5+5)
Compiler          470MB ± 0%        461MB ± 0%  -1.91%  (p=0.008 n=5+5)
SSA              1.13GB ± 0%       1.11GB ± 0%  -1.70%  (p=0.008 n=5+5)
Flate            25.0MB ± 0%       24.6MB ± 0%  -1.67%  (p=0.008 n=5+5)
GoParser         31.6MB ± 0%       31.1MB ± 0%  -1.66%  (p=0.008 n=5+5)
Reflect          77.1MB ± 0%       75.8MB ± 0%  -1.69%  (p=0.008 n=5+5)
Tar              26.3MB ± 0%       25.7MB ± 0%  -2.06%  (p=0.008 n=5+5)
XML              41.9MB ± 0%       41.1MB ± 0%  -1.93%  (p=0.008 n=5+5)
[Geo mean]       73.5MB            72.0MB       -2.03%

name        old allocs/op     new allocs/op     delta
Template           383k ± 0%         383k ± 0%    ~     (p=0.690 n=5+5)
Unicode            343k ± 0%         343k ± 0%    ~     (p=0.841 n=5+5)
GoTypes           1.16M ± 0%        1.16M ± 0%    ~     (p=0.310 n=5+5)
Compiler          4.43M ± 0%        4.42M ± 0%  -0.17%  (p=0.008 n=5+5)
SSA               9.85M ± 0%        9.85M ± 0%    ~     (p=0.310 n=5+5)
Flate              236k ± 0%         236k ± 1%    ~     (p=0.841 n=5+5)
GoParser           320k ± 0%         320k ± 0%    ~     (p=0.421 n=5+5)
Reflect            988k ± 0%         987k ± 0%    ~     (p=0.690 n=5+5)
Tar                252k ± 0%         251k ± 0%    ~     (p=0.095 n=5+5)
XML                399k ± 0%         399k ± 0%    ~     (p=1.000 n=5+5)
[Geo mean]         741k              740k       -0.07%

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

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

The inliner's ishairy passes a budget and a reason down through the
walk. Lift these into a visitor object and turn ishairy and its
helpers into methods.

This will make it easy to add more state.

Change-Id: Ic6ae246e1affd67ed283c3205f9595ae33e22215
Reviewed-on: https://go-review.googlesource.com/41151
Run-TryBot: Austin Clements <austin@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>

Response to code review feedback on CL 40693.

This CL was prepared by:

(1) manually adding new implementations and the Ctxt var to package types

(2) running eg with template:

func before(s *types.Sym) *obj.LSym { return gc.Linksym(s) }
func after(s *types.Sym) *obj.LSym  { return s.Linksym() }

(3) running gofmt -r:

gofmt -r 'isblanksym(a) -> a.IsBlank()'

(4) manually removing old implementations from package gc

Passes toolstash-check.

Change-Id: I39c35def7cae5bcbcc7c77253e5d2b066b981dea
Reviewed-on: https://go-review.googlesource.com/41302
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Robert Griesemer <gri@golang.org>

runtime.getcaller{pc,sp} expect their argument to be a pointer to the
caller's first function argument. This assumption breaks when the caller
is inlined. For example, with -l=4, calls to runtime.entersyscall (which
calls getcallerpc) are inlined and that breaks multiple cgo tests.

This change modifies the compiler to refuse to inline functions that
call runtime.getcaller{pc,sp}. Alternatively, we could mark these
functions //go:noinline but that limits optimization opportunities if
the calls to getcaller{pc,sp} are eliminated as dead code.

Previously TestCgoPprofPIE, TestCgoPprof, and TestCgoCallbackGC failed
with -l=4. Now all of the runtime tests pass with -l=4.

Change-Id: I258bca9025e20fc451e673a18f862b5da1e07ae7
Reviewed-on: https://go-review.googlesource.com/40998
Run-TryBot: David Lazar <lazard@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>
Reviewed-by: Austin Clements <austin@google.com>

Change-Id: Ie8fd7839806b4a6bcfac5ac1f984db7ab282c3b5
Reviewed-on: https://go-review.googlesource.com/41150
Run-TryBot: Austin Clements <austin@google.com>
Reviewed-by: David Lazar <lazard@golang.org>

This is a more thorough and cleaner fix
than doing dead code elimination separately
during inlining, escape analysis, and export.

Unfortunately, it does add another full walk of the AST.
The performance impact is very small, but not non-zero.

If a label or goto is present in the dead code, it is not eliminated.
This restriction can be removed once label/goto checking occurs
much earlier in the compiler. In practice, it probably doesn't
matter much.

Updates #19699
Fixes #19705

name       old alloc/op      new alloc/op      delta
Template        39.2MB ± 0%       39.3MB ± 0%  +0.28%  (p=0.008 n=5+5)
Unicode         29.8MB ± 0%       29.8MB ± 0%    ~     (p=1.000 n=5+5)
GoTypes          113MB ± 0%        113MB ± 0%  -0.55%  (p=0.008 n=5+5)
SSA             1.25GB ± 0%       1.25GB ± 0%  +0.02%  (p=0.008 n=5+5)
Flate           25.3MB ± 0%       25.3MB ± 0%  -0.24%  (p=0.032 n=5+5)
GoParser        31.7MB ± 0%       31.8MB ± 0%  +0.31%  (p=0.008 n=5+5)
Reflect         78.2MB ± 0%       78.3MB ± 0%    ~     (p=0.421 n=5+5)
Tar             26.6MB ± 0%       26.7MB ± 0%  +0.21%  (p=0.008 n=5+5)
XML             42.2MB ± 0%       42.2MB ± 0%    ~     (p=0.056 n=5+5)

name       old allocs/op     new allocs/op     delta
Template          385k ± 0%         387k ± 0%  +0.51%  (p=0.016 n=5+5)
Unicode           321k ± 0%         321k ± 0%    ~     (p=1.000 n=5+5)
GoTypes          1.14M ± 0%        1.14M ± 0%    ~     (p=1.000 n=5+5)
SSA              9.71M ± 0%        9.72M ± 0%  +0.10%  (p=0.008 n=5+5)
Flate             234k ± 1%         234k ± 1%    ~     (p=0.690 n=5+5)
GoParser          315k ± 0%         317k ± 0%  +0.71%  (p=0.008 n=5+5)
Reflect           980k ± 0%         983k ± 0%  +0.30%  (p=0.032 n=5+5)
Tar               251k ± 0%         252k ± 0%  +0.55%  (p=0.016 n=5+5)
XML               392k ± 0%         393k ± 0%  +0.30%  (p=0.008 n=5+5)

Change-Id: Ia10ff4bbf5c6eae782582cc9cbc9785494d4fb83
Reviewed-on: https://go-review.googlesource.com/38773
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>

This comment was out of date since the bump to 80 done as the same time
as inlining transitive functions in:

  commit 77ccb16e
  Author: Russ Cox <rsc@golang.org>
  Date:   Tue Feb 24 12:19:01 2015 -0500

      cmd/internal/gc: transitive inlining

Adjust the comment at the top of the file accordingly.

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

I had too many failed attempts trying to remove iterFields that I
decided to overhaul this function. Much simpler and easier to
understand now (at least IMO).

Passes toolstash-check -all.

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

- created new package cmd/compile/internal/types
- moved Pkg, Sym, Type to new package
- to break cycles, for now we need the (ugly) types/utils.go
  file which contains a handful of functions that must be installed
  early by the gc frontend
- to break cycles, for now we need two functions to convert between
  *gc.Node and *types.Node (the latter is a dummy type)
- adjusted the gc's code to use the new package and the conversion
  functions as needed
- made several Pkg, Sym, and Type methods functions as needed
- renamed constructors typ, typPtr, typArray, etc. to types.New,
  types.NewPtr, types.NewArray, etc.

Passes toolstash-check -all.

Change-Id: I8adfa5e85c731645d0a7fd2030375ed6ebf54b72
Reviewed-on: https://go-review.googlesource.com/39855Reviewed-by: Matthew Dempsky <mdempsky@google.com>

name              old time/op  new time/op  delta
LeadingZeros-4    2.00ns ± 0%  1.34ns ± 1%  -33.02%  (p=0.000 n=8+10)
LeadingZeros16-4  1.62ns ± 0%  1.57ns ± 0%   -3.09%  (p=0.001 n=8+9)
LeadingZeros32-4  2.14ns ± 0%  1.48ns ± 0%  -30.84%  (p=0.002 n=8+10)
LeadingZeros64-4  2.06ns ± 1%  1.33ns ± 0%  -35.08%  (p=0.000 n=8+8)

8-bit args is a special case - the Go code is really fast because
it is just a single table lookup.  So I've disabled that for now.
Intrinsics were actually slower:
LeadingZeros8-4   1.22ns ± 3%  1.58ns ± 1%  +29.56%  (p=0.000 n=10+10)

Update #18616

Change-Id: Ia9c289b9ba59c583ea64060470315fd637e814cf
Reviewed-on: https://go-review.googlesource.com/38311
Run-TryBot: Keith Randall <khr@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Robert Griesemer <gri@golang.org>

After benchmarking with a compiler modified to have better
spill location, it became clear that this method of checking
was actually faster on (at least) two different architectures
(ppc64 and amd64) and it also provides more timely interruption
of loops.

This change adds a modified FOR loop node "FORUNTIL" that
checks after executing the loop body instead of before (i.e.,
always at least once).  This ensures that a pointer past the
end of a slice or array is not made visible to the garbage
collector.

Without the rescheduling checks inserted, the restructured
loop from this  change apparently provides a 1% geomean
improvement on PPC64 running the go1 benchmarks; the
improvement on AMD64 is only 0.12%.

Inserting the rescheduling check exposed some peculiar bug
with the ssa test code for s390x; this was updated based on
initial code actually generated for GOARCH=s390x to use
appropriate OpArg, OpAddr, and OpVarDef.

NaCl is disabled in testing.

Change-Id: Ieafaa9a61d2a583ad00968110ef3e7a441abca50
Reviewed-on: https://go-review.googlesource.com/36206
Run-TryBot: David Chase <drchase@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Cherry Zhang <cherryyz@google.com>

Without this, literals keep their original source positions through
inlining, which results in strange jumps in line numbers of inlined
function bodies. By copying literals, inlining can update their source
position like other nodes.

Fixes #15453.

Change-Id: Iad5d9bbfe183883794213266dc30e31bab89ee69
Reviewed-on: https://go-review.googlesource.com/37232
Run-TryBot: David Lazar <lazard@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>
Reviewed-by: Russ Cox <rsc@golang.org>

In order to generate accurate tracebacks, the runtime needs to know the
inlined call stack for a given PC. This creates two tables per function
for this purpose. The first table is the inlining tree (stored in the
function's funcdata), which has a node containing the file, line, and
function name for every inlined call. The second table is a PC-value
table that maps each PC to a node in the inlining tree (or -1 if the PC
is not the result of inlining).

To give the appearance that inlining hasn't happened, the runtime also
needs the original source position information of inlined AST nodes.
Previously the compiler plastered over the line numbers of inlined AST
nodes with the line number of the call. This meant that the PC-line
table mapped each PC to line number of the outermost call in its inlined
call stack, with no way to access the innermost line number.

Now the compiler retains line numbers of inlined AST nodes and writes
the innermost source position information to the PC-line and PC-file
tables. Some tools and tests expect to see outermost line numbers, so we
provide the OutermostLine function for displaying line info.

To keep track of the inlined call stack for an AST node, we extend the
src.PosBase type with an index into a global inlining tree. Every time
the compiler inlines a call, it creates a node in the global inlining
tree for the call, and writes its index to the PosBase of every inlined
AST node. The parent of this node is the inlining tree index of the
call. -1 signifies no parent.

For each function, the compiler creates a local inlining tree and a
PC-value table mapping each PC to an index in the local tree.  These are
written to an object file, which is read by the linker.  The linker
re-encodes these tables compactly by deduplicating function names and
file names.

This change increases the size of binaries by 4-5%. For example, this is
how the go1 benchmark binary is impacted by this change:

section             old bytes   new bytes   delta
.text               3.49M ± 0%  3.49M ± 0%   +0.06%
.rodata             1.12M ± 0%  1.21M ± 0%   +8.21%
.gopclntab          1.50M ± 0%  1.68M ± 0%  +11.89%
.debug_line          338k ± 0%   435k ± 0%  +28.78%
Total               9.21M ± 0%  9.58M ± 0%   +4.01%

Updates #19348.

Change-Id: Ic4f180c3b516018138236b0c35e0218270d957d3
Reviewed-on: https://go-review.googlesource.com/37231
Run-TryBot: David Lazar <lazard@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Austin Clements <austin@google.com>

This reduces compiler memory usage by up to 4% - see compilebench
results below.

name       old time/op     new time/op     delta
Template       245ms ± 4%      241ms ± 2%  -1.88%  (p=0.029 n=10+10)
Unicode        126ms ± 3%      124ms ± 3%    ~     (p=0.105 n=10+10)
GoTypes        805ms ± 2%      813ms ± 3%    ~     (p=0.515 n=8+10)
Compiler       3.95s ± 2%      3.83s ± 1%  -2.96%  (p=0.000 n=9+10)
MakeBash       47.4s ± 4%      46.6s ± 1%  -1.59%  (p=0.028 n=9+10)

name       old user-ns/op  new user-ns/op  delta
Template        324M ± 5%       326M ± 3%    ~     (p=0.935 n=10+10)
Unicode         186M ± 5%       178M ±10%    ~     (p=0.067 n=9+10)
GoTypes        1.08G ± 7%      1.09G ± 4%    ~     (p=0.956 n=10+10)
Compiler       5.34G ± 4%      5.31G ± 1%    ~     (p=0.501 n=10+8)

name       old alloc/op    new alloc/op    delta
Template      41.0MB ± 0%     39.8MB ± 0%  -3.03%  (p=0.000 n=10+10)
Unicode       32.3MB ± 0%     31.0MB ± 0%  -4.13%  (p=0.000 n=10+10)
GoTypes        119MB ± 0%      116MB ± 0%  -2.39%  (p=0.000 n=10+10)
Compiler       499MB ± 0%      487MB ± 0%  -2.48%  (p=0.000 n=10+10)

name       old allocs/op   new allocs/op   delta
Template        380k ± 1%       379k ± 1%    ~     (p=0.436 n=10+10)
Unicode         324k ± 1%       324k ± 0%    ~     (p=0.853 n=10+10)
GoTypes        1.15M ± 0%      1.15M ± 0%    ~     (p=0.481 n=10+10)
Compiler       4.41M ± 0%      4.41M ± 0%  -0.12%  (p=0.007 n=10+10)

name       old text-bytes  new text-bytes  delta
HelloSize       623k ± 0%       623k ± 0%    ~     (all equal)
CmdGoSize      6.64M ± 0%      6.64M ± 0%    ~     (all equal)

name       old data-bytes  new data-bytes  delta
HelloSize      5.81k ± 0%      5.81k ± 0%    ~     (all equal)
CmdGoSize       238k ± 0%       238k ± 0%    ~     (all equal)

name       old bss-bytes   new bss-bytes   delta
HelloSize       134k ± 0%       134k ± 0%    ~     (all equal)
CmdGoSize       152k ± 0%       152k ± 0%    ~     (all equal)

name       old exe-bytes   new exe-bytes   delta
HelloSize       967k ± 0%       967k ± 0%    ~     (all equal)
CmdGoSize      10.2M ± 0%      10.2M ± 0%    ~     (all equal)

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

Change-Id: I0d14d68b57e8605cdae8a45d6fa97255a42297d8
Reviewed-on: https://go-review.googlesource.com/37521
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>

Constant evaluation provides some rudimentary
knowledge of dead code at inlining decision time.
Use it.

This CL addresses only dead code inside if statements.
For statements are never inlined anyway,
and dead code inside for statements is rare.
Analyzing switch statements is worth doing,
but it is more complicated, since we would have
to evaluate each case; leave it for later.

Fixes #9274

After this CL, the following functions in std+cmd
can be newly inlined:

cmd/internal/obj/x86/asm6.go:3122: can inline subreg
cmd/vendor/golang.org/x/arch/x86/x86asm/decode.go:172: can inline instPrefix
cmd/vendor/golang.org/x/arch/x86/x86asm/decode.go:202: can inline truncated
go/constant/value.go:234: can inline makeFloat
go/types/labels.go:52: can inline (*block).insert
math/big/float.go:231: can inline (*Float).Sign
math/bits/bits.go:57: can inline OnesCount
net/http/server.go:597: can inline (*Server).newConn
runtime/hashmap.go:1165: can inline reflect_maplen
runtime/proc.go:207: can inline os_beforeExit
runtime/signal_unix.go:55: can inline init.5
runtime/stack.go:1081: can inline gostartcallfn

Change-Id: I4c92fb96aa0c3d33df7b3f2da548612e79b56b5b
Reviewed-on: https://go-review.googlesource.com/37499Reviewed-by: Matthew Dempsky <mdempsky@google.com>

Intrinsics are ok to inline as they don't rewrite to actual calls.

Change-Id: Ieb19c834c61579823c62c6d1a1b425d6c4d4de23
Reviewed-on: https://go-review.googlesource.com/34272
Run-TryBot: Keith Randall <khr@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: David Chase <drchase@google.com>

Many non-inlineable functions were not being
reported in '-m -m' mode.

Updates #17858.

Change-Id: I7d96361b39dd317f5550e57334a8a6dd1a836598
Reviewed-on: https://go-review.googlesource.com/32971
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>

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>

Various minor adjustments.

Change-Id: Iedfb97989f7bedaa3e9e8993b167e05f162434a7
Reviewed-on: https://go-review.googlesource.com/34136Reviewed-by: David Lazar <lazard@golang.org>

Adjust cmd/compile accordingly.

This will make it easier to replace the underlying implementation.

Change-Id: I33645850bb18c839b24785b6222a9e028617addb
Reviewed-on: https://go-review.googlesource.com/34133Reviewed-by: David Lazar <lazard@golang.org>

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>

Now the net tests pass with -gcflags '-l=4'.

Fixes #18125.

Change-Id: I4e3a46eb0cb3a93b203e74f5bc99c5822331f535
Reviewed-on: https://go-review.googlesource.com/33722Reviewed-by: Keith Randall <khr@golang.org>

This fixes a bug in -l=3 or higher.

To inline a variadic function, the compiler generates code that constructs
a slice of arguments for the variadic parameter. Consider the function

  func Foo(xs ...string)

and the call Foo("hello", "world"). To inline the call to Foo, the
compiler used to generate

  xs := [2]string{"hello", "world"}[:]

which doesn't type check:

  invalid operation [2]string literal[:] (slice of unaddressable value).

Now, the compiler generates

  xs := []string{"hello", "world"}

which does type check.

Fixes #18116.

Change-Id: I0ee531ef2e6cc276db6fb12602b25a46d6d5db21
Reviewed-on: https://go-review.googlesource.com/33671Reviewed-by: Keith Randall <khr@golang.org>

Use a local map during inlining instead.

Change-Id: I10cd19885e7124f812bb04a79dbda52bfebfe1a1
Reviewed-on: https://go-review.googlesource.com/32225
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>