| Age | Commit message (Collapse) | Author |
|---|
|
<= maxint
When the terminating condition is <= X, we need to make sure that
X+step doesn't overflow.
Fixes #53617
Change-Id: I36e5384d05b4d7168e48db6094200fcae409bfe5
Reviewed-on: https://go-review.googlesource.com/c/go/+/415219
Reviewed-by: Than McIntosh <thanm@google.com>
Run-TryBot: David Chase <drchase@google.com>
Reviewed-by: David Chase <drchase@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
Run-TryBot: Keith Randall <khr@golang.org>
(cherry picked from commit 31b8c23c5702f129aca9241bbb2132c90b1929cc)
Reviewed-on: https://go-review.googlesource.com/c/go/+/415415
Reviewed-by: Keith Randall <khr@google.com>
|
|
The generic Greater and Geq ops can always be replaced with the Less and
Leq ops. This CL therefore removes them. This simplifies the compiler since
it reduces the number of operations that need handling in both code and in
rewrite rules. This will be especially true when adding control flow
optimizations such as the integer-in-range optimizations in CL 165998.
Change-Id: If0648b2b19998ac1bddccbf251283f3be4ec3040
Reviewed-on: https://go-review.googlesource.com/c/go/+/220417
Run-TryBot: Michael Munday <mike.munday@ibm.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>
|
|
Once defined, a stack slot holding an open-coded defer arg should always be marked
live, since it may be used at any time if there is a panic. These stack slots are
typically kept live naturally by the open-defer code inlined at each return/exit point.
However, we need to do extra work to make sure that they are kept live if a
function has an infinite loop or a panic exit.
For this fix, only in the case of a function that is using open-coded defers, we
compute the set of blocks (most often empty) that cannot reach a return or a
BlockExit (panic) because of an infinite loop. Then, for each block b which
cannot reach a return or BlockExit or is a BlockExit block, we mark each defer arg
slot as live, as long as the definition of the defer arg slot dominates block b.
For this change, had to export (*Func).sdom (-> Sdom) and SparseTree.isAncestorEq
(-> IsAncestorEq)
Updates #35277
Change-Id: I7b53c9bd38ba384a3794386dd0eb94e4cbde4eb1
Reviewed-on: https://go-review.googlesource.com/c/go/+/204802
Run-TryBot: Dan Scales <danscales@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>
|
|
Control values are used to choose which successor of a block is
jumped to. Typically a control value takes the form of a 'flags'
value that represents the result of a comparison. Some
architectures however use a variable in a register as a control
value.
Up until now we have managed with a single control value per block.
However some architectures (e.g. s390x and riscv64) have combined
compare-and-branch instructions that take two variables in registers
as parameters. To generate these instructions we need to support 2
control values per block.
This CL allows up to 2 control values to be used in a block in
order to support the addition of compare-and-branch instructions.
I have implemented s390x compare-and-branch instructions in a
different CL.
Passes toolstash-check -all.
Results of compilebench:
name old time/op new time/op delta
Template 208ms ± 1% 209ms ± 1% ~ (p=0.289 n=20+20)
Unicode 83.7ms ± 1% 83.3ms ± 3% -0.49% (p=0.017 n=18+18)
GoTypes 748ms ± 1% 748ms ± 0% ~ (p=0.460 n=20+18)
Compiler 3.47s ± 1% 3.48s ± 1% ~ (p=0.070 n=19+18)
SSA 11.5s ± 1% 11.7s ± 1% +1.64% (p=0.000 n=19+18)
Flate 130ms ± 1% 130ms ± 1% ~ (p=0.588 n=19+20)
GoParser 160ms ± 1% 161ms ± 1% ~ (p=0.211 n=20+20)
Reflect 465ms ± 1% 467ms ± 1% +0.42% (p=0.007 n=20+20)
Tar 184ms ± 1% 185ms ± 2% ~ (p=0.087 n=18+20)
XML 253ms ± 1% 253ms ± 1% ~ (p=0.377 n=20+18)
LinkCompiler 769ms ± 2% 774ms ± 2% ~ (p=0.070 n=19+19)
ExternalLinkCompiler 3.59s ±11% 3.68s ± 6% ~ (p=0.072 n=20+20)
LinkWithoutDebugCompiler 446ms ± 5% 454ms ± 3% +1.79% (p=0.002 n=19+20)
StdCmd 26.0s ± 2% 26.0s ± 2% ~ (p=0.799 n=20+20)
name old user-time/op new user-time/op delta
Template 238ms ± 5% 240ms ± 5% ~ (p=0.142 n=20+20)
Unicode 105ms ±11% 106ms ±10% ~ (p=0.512 n=20+20)
GoTypes 876ms ± 2% 873ms ± 4% ~ (p=0.647 n=20+19)
Compiler 4.17s ± 2% 4.19s ± 1% ~ (p=0.093 n=20+18)
SSA 13.9s ± 1% 14.1s ± 1% +1.45% (p=0.000 n=18+18)
Flate 145ms ±13% 146ms ± 5% ~ (p=0.851 n=20+18)
GoParser 185ms ± 5% 188ms ± 7% ~ (p=0.174 n=20+20)
Reflect 534ms ± 3% 538ms ± 2% ~ (p=0.105 n=20+18)
Tar 215ms ± 4% 211ms ± 9% ~ (p=0.079 n=19+20)
XML 295ms ± 6% 295ms ± 5% ~ (p=0.968 n=20+20)
LinkCompiler 832ms ± 4% 837ms ± 7% ~ (p=0.707 n=17+20)
ExternalLinkCompiler 1.58s ± 8% 1.60s ± 4% ~ (p=0.296 n=20+19)
LinkWithoutDebugCompiler 478ms ±12% 489ms ±10% ~ (p=0.429 n=20+20)
name old object-bytes new object-bytes delta
Template 559kB ± 0% 559kB ± 0% ~ (all equal)
Unicode 216kB ± 0% 216kB ± 0% ~ (all equal)
GoTypes 2.03MB ± 0% 2.03MB ± 0% ~ (all equal)
Compiler 8.07MB ± 0% 8.07MB ± 0% -0.06% (p=0.000 n=20+20)
SSA 27.1MB ± 0% 27.3MB ± 0% +0.89% (p=0.000 n=20+20)
Flate 343kB ± 0% 343kB ± 0% ~ (all equal)
GoParser 441kB ± 0% 441kB ± 0% ~ (all equal)
Reflect 1.36MB ± 0% 1.36MB ± 0% ~ (all equal)
Tar 487kB ± 0% 487kB ± 0% ~ (all equal)
XML 632kB ± 0% 632kB ± 0% ~ (all equal)
name old export-bytes new export-bytes delta
Template 18.5kB ± 0% 18.5kB ± 0% ~ (all equal)
Unicode 7.92kB ± 0% 7.92kB ± 0% ~ (all equal)
GoTypes 35.0kB ± 0% 35.0kB ± 0% ~ (all equal)
Compiler 109kB ± 0% 110kB ± 0% +0.72% (p=0.000 n=20+20)
SSA 137kB ± 0% 138kB ± 0% +0.58% (p=0.000 n=20+20)
Flate 4.89kB ± 0% 4.89kB ± 0% ~ (all equal)
GoParser 8.49kB ± 0% 8.49kB ± 0% ~ (all equal)
Reflect 11.4kB ± 0% 11.4kB ± 0% ~ (all equal)
Tar 10.5kB ± 0% 10.5kB ± 0% ~ (all equal)
XML 16.7kB ± 0% 16.7kB ± 0% ~ (all equal)
name old text-bytes new text-bytes delta
HelloSize 761kB ± 0% 761kB ± 0% ~ (all equal)
CmdGoSize 10.8MB ± 0% 10.8MB ± 0% ~ (all equal)
name old data-bytes new data-bytes delta
HelloSize 10.7kB ± 0% 10.7kB ± 0% ~ (all equal)
CmdGoSize 312kB ± 0% 312kB ± 0% ~ (all equal)
name old bss-bytes new bss-bytes delta
HelloSize 122kB ± 0% 122kB ± 0% ~ (all equal)
CmdGoSize 146kB ± 0% 146kB ± 0% ~ (all equal)
name old exe-bytes new exe-bytes delta
HelloSize 1.13MB ± 0% 1.13MB ± 0% ~ (all equal)
CmdGoSize 15.1MB ± 0% 15.1MB ± 0% ~ (all equal)
Change-Id: I3cc2f9829a109543d9a68be4a21775d2d3e9801f
Reviewed-on: https://go-review.googlesource.com/c/go/+/196557
Run-TryBot: Michael Munday <mike.munday@ibm.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Daniel Martí <mvdan@mvdan.cc>
Reviewed-by: Keith Randall <khr@golang.org>
|
|
prove wasn't able to detect induction variables that was bound
by another inducation variable. This happened because an indvar
is a Phi, and thus in case of a dependency, the loop bounding
condition looked as Phi < Phi. This triggered an existing
codepath that checked whether the upper bound was a Phi to
detect loop conditions written in reversed order respect to the
idiomatic way (eg: for i:=0; len(n)>i; i++).
To fix this, we call the indvar pattern matching on both operands
of the loop condition, so that the first operand that matches
will be treated as the indvar.
Updates #24660 (removes a boundcheck from Fannkuch)
Change-Id: Iade83d8deb54f14277ed3f2e37b190e1ed173d11
Reviewed-on: https://go-review.googlesource.com/c/go/+/195220
Reviewed-by: David Chase <drchase@google.com>
|
|
This CL extracts the logic for pattern-matching an induction
variable into a separate function, in preparation for next CL
where we would need to call it multiple times.
No functional changes, passes toolstash -cmp.
Change-Id: Ic52391e6c1b2e72bae32a0f3f65dfea321caaf4f
Reviewed-on: https://go-review.googlesource.com/c/go/+/195737
Reviewed-by: David Chase <drchase@google.com>
|
|
Use the following (suboptimal) script to obtain a list of possible
typos:
#!/usr/bin/env sh
set -x
git ls-files |\
grep -e '\.\(c\|cc\|go\)$' |\
xargs -n 1\
awk\
'/\/\// { gsub(/.*\/\//, ""); print; } /\/\*/, /\*\// { gsub(/.*\/\*/, ""); gsub(/\*\/.*/, ""); }' |\
hunspell -d en_US -l |\
grep '^[[:upper:]]\{0,1\}[[:lower:]]\{1,\}$' |\
grep -v -e '^.\{1,4\}$' -e '^.\{16,\}$' |\
sort -f |\
uniq -c |\
awk '$1 == 1 { print $2; }'
Then, go through the results manually and fix the most obvious typos in
the non-vendored code.
Change-Id: I3cb5830a176850e1a0584b8a40b47bde7b260eae
Reviewed-on: https://go-review.googlesource.com/c/go/+/193848
Reviewed-by: Robert Griesemer <gri@golang.org>
|
|
Would suggest extending capabilities (32-bit, unsigned, etc)
in separate CLs because prove bugs are so mystifying.
This implements the suggestion in this comment
https://go-review.googlesource.com/c/go/+/104041/10/src/cmd/compile/internal/ssa/loopbce.go#164
for inferring properly bounded iteration for loops of the form
for i := K0; i < KNN-(K-1); i += K
for i := K0; i <= KNN-K; i += K
Where KNN is "known non negative" (i.e., len or cap) and K
is also not negative. Because i <= KNN-K, i+K <= KNN and
no overflow occurs.
Also handles decreasing case (K1 > 0)
for i := KNN; i >= K0; i -= K1
which works when MININT+K1 < K0
(i.e. MININT < K0-K1, no overflow)
Signed only, also only 64 bit for now.
Change-Id: I5da6015aba2f781ec76c4ad59c9c48d952325fdc
Reviewed-on: https://go-review.googlesource.com/c/go/+/136375
Run-TryBot: David Chase <drchase@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Alexandru Moșoi <alexandru@mosoi.ro>
|
|
We need to make sure that the terminating comparison has the right
sense given the increment direction. If the increment is positive,
the terminating comparsion must be < or <=. If the increment is
negative, the terminating comparison must be > or >=.
Do a few cleanups, like constant-folding entry==0, adding comments,
removing unused "exported" fields.
Fixes #26116
Change-Id: I14230ee8126054b750e2a1f2b18eb8f09873dbd5
Reviewed-on: https://go-review.googlesource.com/121940
Run-TryBot: Keith Randall <khr@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Heschi Kreinick <heschi@google.com>
|
|
For non-unit increment, loopbce checks to see if the
increment evenly divides the difference between (constant)
loop start and end. This test panics when the increment
is zero.
Fix: check for zero, if found, don't optimize the loop.
Also added missing copyright notice to loopbce.go.
Fixes #26043.
Change-Id: I5f460104879cacc94481949234c9ce8c519d6380
Reviewed-on: https://go-review.googlesource.com/120759
Run-TryBot: David Chase <drchase@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
|
|
Currently, we compile range loops into for loops with the obvious
initialization and update of the index variable. In this form, the
prove pass can see that the body is dominated by an i < len condition,
and findIndVar can detect that i is an induction variable and that
0 <= i < len.
GOEXPERIMENT=preemptibleloops compiles range loops to OFORUNTIL and
we're preparing to unconditionally switch to a variation of this for
#24543. OFORUNTIL moves the increment and condition *after* the body,
which makes the bounds on the index variable much less obvious. With
OFORUNTIL, proving anything about the index variable requires
understanding the phi that joins the index values at the top of the
loop body block.
This interferes with both prove's ability to see that i < len (this is
true on both paths that enter the body, but from two different
conditional checks) and with findIndVar's ability to detect the
induction pattern.
Fix this by teaching prove to detect that the index in the pattern
constructed by OFORUNTIL is an induction variable and add both bounds
to the facts table. Currently this is done separately from findIndVar
because it depends on prove's factsTable, while findIndVar runs before
visiting blocks and building the factsTable.
Without any GOEXPERIMENT, this has no effect on std or cmd. However,
with GOEXPERIMENT=preemptibleloops, this change becomes necessary to
prove 90 conditions in std and cmd.
Change-Id: Ic025d669f81b53426309da5a6e8010e5ccaf4f49
Reviewed-on: https://go-review.googlesource.com/102603
Run-TryBot: Austin Clements <austin@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>
|
|
When a loop has bound len(s)-delta, findIndVar detected it and
returned len(s) as (conservative) upper bound. This little lie
allowed loopbce to drop bound checks.
It is obviously more generic to teach prove about relations like
x+d<w for non-constant "w"; we already handled the case for
constant "w", so we just want to learn that if d<0, then x+d<w
proves that x<w.
To be able to remove the code from findIndVar, we also need
to teach prove that len() and cap() are always non-negative.
This CL allows to prove 633 more checks in cmd+std. Most
of them are cases where the code was already testing before
accessing a slice but the compiler didn't know it. For instance,
take strings.HasSuffix:
func HasSuffix(s, suffix string) bool {
return len(s) >= len(suffix) && s[len(s)-len(suffix):] == suffix
}
When suffix is a literal string, the compiler now understands
that the explicit check is enough to not emit a slice check.
I also found a loopbce test that was incorrectly
written to detect an overflow but had a off-by-one (on the
conservative side), so it unexpectly passed with this CL; I
changed it to really trigger the overflow as intended.
Change-Id: Ib5abade337db46b8811425afebad4719b6e46c4a
Reviewed-on: https://go-review.googlesource.com/105635
Run-TryBot: Giovanni Bajo <rasky@develer.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: David Chase <drchase@google.com>
|
|
To be effective, this also requires being able to relax constraints
on min/max bound inclusiveness; they are now exposed through a flags,
and prove has been updated to handle it correctly.
Change-Id: I3490e54461b7b9de8bc4ae40d3b5e2fa2d9f0556
Reviewed-on: https://go-review.googlesource.com/104041
Run-TryBot: Giovanni Bajo <rasky@develer.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: David Chase <drchase@google.com>
|
|
Test both minimum and maximum bound, and prepare
formatting for more advanced tests (inclusive / esclusive bounds).
Change-Id: Ibe432916d9c938343bc07943798bc9709ad71845
Reviewed-on: https://go-review.googlesource.com/104040
Run-TryBot: Giovanni Bajo <rasky@develer.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
|
|
prove now is able to do what loopbce used to do.
Passes toolstash -cmp.
Compilebench of the whole serie (master 9967582f770f6):
name old time/op new time/op delta
Template 208ms ±18% 198ms ± 4% ~ (p=0.690 n=5+5)
Unicode 99.1ms ±19% 96.5ms ± 4% ~ (p=0.548 n=5+5)
GoTypes 623ms ± 1% 633ms ± 1% ~ (p=0.056 n=5+5)
Compiler 2.94s ± 2% 3.02s ± 4% ~ (p=0.095 n=5+5)
SSA 6.77s ± 1% 7.11s ± 2% +4.94% (p=0.008 n=5+5)
Flate 129ms ± 1% 136ms ± 0% +4.87% (p=0.016 n=5+4)
GoParser 152ms ± 3% 156ms ± 1% ~ (p=0.095 n=5+5)
Reflect 380ms ± 2% 392ms ± 1% +3.30% (p=0.008 n=5+5)
Tar 185ms ± 6% 184ms ± 2% ~ (p=0.690 n=5+5)
XML 223ms ± 2% 228ms ± 3% ~ (p=0.095 n=5+5)
StdCmd 26.8s ± 2% 28.0s ± 5% +4.46% (p=0.032 n=5+5)
name old user-ns/op new user-ns/op delta
Template 252M ± 5% 248M ± 3% ~ (p=1.000 n=5+5)
Unicode 118M ± 7% 121M ± 4% ~ (p=0.548 n=5+5)
GoTypes 790M ± 2% 793M ± 2% ~ (p=0.690 n=5+5)
Compiler 3.78G ± 3% 3.91G ± 4% ~ (p=0.056 n=5+5)
SSA 8.98G ± 2% 9.52G ± 3% +6.08% (p=0.008 n=5+5)
Flate 155M ± 1% 160M ± 0% +3.47% (p=0.016 n=5+4)
GoParser 185M ± 4% 187M ± 2% ~ (p=0.310 n=5+5)
Reflect 469M ± 1% 481M ± 1% +2.52% (p=0.016 n=5+5)
Tar 222M ± 4% 222M ± 2% ~ (p=0.841 n=5+5)
XML 269M ± 1% 274M ± 2% +1.88% (p=0.032 n=5+5)
name old text-bytes new text-bytes delta
HelloSize 664k ± 0% 664k ± 0% ~ (all equal)
CmdGoSize 7.23M ± 0% 7.22M ± 0% -0.06% (p=0.008 n=5+5)
name old data-bytes new data-bytes delta
HelloSize 134k ± 0% 134k ± 0% ~ (all equal)
CmdGoSize 390k ± 0% 390k ± 0% ~ (all equal)
name old exe-bytes new exe-bytes delta
HelloSize 1.39M ± 0% 1.39M ± 0% ~ (all equal)
CmdGoSize 14.4M ± 0% 14.4M ± 0% -0.06% (p=0.008 n=5+5)
Go1 of the whole serie:
name old time/op new time/op delta
BinaryTree17-16 5.40s ± 6% 5.38s ± 4% ~ (p=1.000 n=12+10)
Fannkuch11-16 4.04s ± 3% 3.81s ± 3% -5.70% (p=0.000 n=11+11)
FmtFprintfEmpty-16 60.7ns ± 2% 60.2ns ± 3% ~ (p=0.136 n=11+10)
FmtFprintfString-16 115ns ± 2% 114ns ± 4% ~ (p=0.175 n=11+10)
FmtFprintfInt-16 118ns ± 2% 125ns ± 2% +5.76% (p=0.000 n=11+10)
FmtFprintfIntInt-16 196ns ± 2% 204ns ± 3% +4.42% (p=0.000 n=10+11)
FmtFprintfPrefixedInt-16 207ns ± 2% 214ns ± 2% +3.23% (p=0.000 n=10+11)
FmtFprintfFloat-16 364ns ± 3% 357ns ± 2% -1.88% (p=0.002 n=11+11)
FmtManyArgs-16 773ns ± 2% 775ns ± 1% ~ (p=0.457 n=11+10)
GobDecode-16 11.2ms ± 4% 11.0ms ± 3% -1.51% (p=0.022 n=10+9)
GobEncode-16 9.91ms ± 6% 9.81ms ± 5% ~ (p=0.699 n=11+11)
Gzip-16 339ms ± 1% 338ms ± 1% ~ (p=0.438 n=11+11)
Gunzip-16 64.4ms ± 1% 65.2ms ± 1% +1.28% (p=0.001 n=10+11)
HTTPClientServer-16 157µs ± 7% 160µs ± 5% ~ (p=0.133 n=11+11)
JSONEncode-16 22.3ms ± 4% 23.2ms ± 4% +3.79% (p=0.000 n=11+11)
JSONDecode-16 96.7ms ± 3% 96.6ms ± 1% ~ (p=0.562 n=11+11)
Mandelbrot200-16 6.42ms ± 1% 6.40ms ± 1% ~ (p=0.365 n=11+11)
GoParse-16 5.59ms ± 7% 5.42ms ± 5% -3.07% (p=0.020 n=11+10)
RegexpMatchEasy0_32-16 113ns ± 2% 113ns ± 3% ~ (p=0.968 n=11+10)
RegexpMatchEasy0_1K-16 417ns ± 1% 416ns ± 3% ~ (p=0.742 n=11+10)
RegexpMatchEasy1_32-16 106ns ± 1% 107ns ± 3% ~ (p=0.223 n=11+11)
RegexpMatchEasy1_1K-16 654ns ± 2% 657ns ± 1% ~ (p=0.672 n=11+8)
RegexpMatchMedium_32-16 176ns ± 3% 177ns ± 1% ~ (p=0.664 n=11+9)
RegexpMatchMedium_1K-16 56.3µs ± 3% 56.7µs ± 3% ~ (p=0.171 n=11+11)
RegexpMatchHard_32-16 2.83µs ± 5% 2.83µs ± 4% ~ (p=0.735 n=11+11)
RegexpMatchHard_1K-16 82.7µs ± 2% 82.7µs ± 2% ~ (p=0.853 n=10+10)
Revcomp-16 679ms ± 9% 782ms ±29% +15.16% (p=0.031 n=9+11)
Template-16 118ms ± 1% 109ms ± 2% -7.49% (p=0.000 n=11+11)
TimeParse-16 474ns ± 1% 462ns ± 1% -2.59% (p=0.000 n=11+11)
TimeFormat-16 482ns ± 1% 494ns ± 1% +2.49% (p=0.000 n=10+11)
name old speed new speed delta
GobDecode-16 68.7MB/s ± 4% 69.8MB/s ± 3% +1.52% (p=0.022 n=10+9)
GobEncode-16 77.6MB/s ± 6% 78.3MB/s ± 5% ~ (p=0.699 n=11+11)
Gzip-16 57.2MB/s ± 1% 57.3MB/s ± 1% ~ (p=0.428 n=11+11)
Gunzip-16 301MB/s ± 2% 298MB/s ± 1% -1.07% (p=0.007 n=11+11)
JSONEncode-16 86.9MB/s ± 4% 83.7MB/s ± 4% -3.63% (p=0.000 n=11+11)
JSONDecode-16 20.1MB/s ± 3% 20.1MB/s ± 1% ~ (p=0.529 n=11+11)
GoParse-16 10.4MB/s ± 6% 10.7MB/s ± 4% +3.12% (p=0.020 n=11+10)
RegexpMatchEasy0_32-16 282MB/s ± 2% 282MB/s ± 3% ~ (p=0.756 n=11+10)
RegexpMatchEasy0_1K-16 2.45GB/s ± 1% 2.46GB/s ± 2% ~ (p=0.705 n=11+10)
RegexpMatchEasy1_32-16 299MB/s ± 1% 297MB/s ± 2% ~ (p=0.151 n=11+11)
RegexpMatchEasy1_1K-16 1.56GB/s ± 2% 1.56GB/s ± 1% ~ (p=0.717 n=11+8)
RegexpMatchMedium_32-16 5.67MB/s ± 4% 5.63MB/s ± 1% ~ (p=0.538 n=11+9)
RegexpMatchMedium_1K-16 18.2MB/s ± 3% 18.1MB/s ± 3% ~ (p=0.156 n=11+11)
RegexpMatchHard_32-16 11.3MB/s ± 5% 11.3MB/s ± 4% ~ (p=0.711 n=11+11)
RegexpMatchHard_1K-16 12.4MB/s ± 1% 12.4MB/s ± 2% ~ (p=0.535 n=9+10)
Revcomp-16 370MB/s ± 5% 332MB/s ±24% ~ (p=0.062 n=8+11)
Template-16 16.5MB/s ± 1% 17.8MB/s ± 2% +8.11% (p=0.000 n=11+11)
Change-Id: I41e46f375ee127785c6491f7ef5bd35581261ae6
Reviewed-on: https://go-review.googlesource.com/104039
Run-TryBot: Giovanni Bajo <rasky@develer.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: David Chase <drchase@google.com>
|
|
Reuse findIndVar to discover induction variables, and then
register the facts we know about them into the facts table
when entering the loop block.
Moreover, handle "x+delta > w" while updating the facts table,
to be able to prove accesses to slices with constant offsets
such as slice[i-10].
Change-Id: I2a63d050ed58258136d54712ac7015b25c893d71
Reviewed-on: https://go-review.googlesource.com/104038
Run-TryBot: Giovanni Bajo <rasky@develer.com>
Reviewed-by: David Chase <drchase@google.com>
|
|
Suggested by mdempsky in CL 38232.
This allows us to use the Frontend field
to associate frontend state and information
with a function.
See the following CL in the series for examples.
This is a giant CL, but it is almost entirely routine refactoring.
The ssa test API is starting to feel a bit unwieldy.
I will clean it up separately, once the dust has settled.
Passes toolstash -cmp.
Updates #15756
Change-Id: I71c573bd96ff7251935fce1391b06b1f133c3caf
Reviewed-on: https://go-review.googlesource.com/38327
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>
|
|
This is a mostly mechanical rename followed by manual fixes where necessary.
Change-Id: Ie5c670b133db978f15dc03e50dc2da0c80fc8842
Reviewed-on: https://go-review.googlesource.com/34137
Reviewed-by: David Lazar <lazard@golang.org>
|
|
We compute a lot of stuff based off the CFG: postorder traversal,
dominators, dominator tree, loop nest. Multiple phases use this
information and we end up recomputing some of it. Add a cache
for this information so if the CFG hasn't changed, we can reuse
the previous computation.
Change-Id: I9b5b58af06830bd120afbee9cfab395a0a2f74b2
Reviewed-on: https://go-review.googlesource.com/29356
Reviewed-by: David Chase <drchase@google.com>
|
|
Provide indexes along with block pointers for Preds
and Succs arrays. This allows us to splice edges in
and out of those arrays in constant time.
Fixes worst-case O(n^2) behavior in deadcode and fuse.
benchmark old ns/op new ns/op delta
BenchmarkFuse1-8 2065 2057 -0.39%
BenchmarkFuse10-8 9408 9073 -3.56%
BenchmarkFuse100-8 105238 76277 -27.52%
BenchmarkFuse1000-8 3982562 1026750 -74.22%
BenchmarkFuse10000-8 301220329 12824005 -95.74%
BenchmarkDeadCode1-8 1588 1566 -1.39%
BenchmarkDeadCode10-8 4333 4250 -1.92%
BenchmarkDeadCode100-8 32031 32574 +1.70%
BenchmarkDeadCode1000-8 590407 468275 -20.69%
BenchmarkDeadCode10000-8 17822890 5000818 -71.94%
BenchmarkDeadCode100000-8 1388706640 78021127 -94.38%
BenchmarkDeadCode200000-8 5372518479 168598762 -96.86%
Change-Id: Iccabdbb9343fd1c921ba07bbf673330a1c36ee17
Reviewed-on: https://go-review.googlesource.com/22589
Reviewed-by: Josh Bleecher Snyder <josharian@gmail.com>
Run-TryBot: Keith Randall <khr@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
|
|
These passes do not modify the dominator tree too much.
% benchstat old.txt new.txt
name old time/op new time/op delta
Template 335ms ± 3% 325ms ± 8% ~ (p=0.074 n=8+9)
GoTypes 1.05s ± 1% 1.05s ± 3% ~ (p=0.095 n=9+10)
Compiler 5.37s ± 4% 5.29s ± 1% -1.42% (p=0.022 n=9+10)
MakeBash 34.9s ± 3% 34.4s ± 2% ~ (p=0.095 n=9+10)
name old alloc/op new alloc/op delta
Template 55.4MB ± 0% 54.9MB ± 0% -0.81% (p=0.000 n=10+10)
GoTypes 179MB ± 0% 178MB ± 0% -0.89% (p=0.000 n=10+10)
Compiler 807MB ± 0% 798MB ± 0% -1.10% (p=0.000 n=10+10)
name old allocs/op new allocs/op delta
Template 498k ± 0% 496k ± 0% -0.29% (p=0.000 n=9+9)
GoTypes 1.42M ± 0% 1.41M ± 0% -0.24% (p=0.000 n=10+10)
Compiler 5.61M ± 0% 5.60M ± 0% -0.12% (p=0.000 n=10+10)
Change-Id: I4cd20cfba3f132ebf371e16046ab14d7e42799ec
Reviewed-on: https://go-review.googlesource.com/21806
Run-TryBot: Alexandru Moșoi <alexandru@mosoi.ro>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: David Chase <drchase@google.com>
|
|
Removes 49 more bound checks in make.bash. For example:
var a[100]int
for i := 0; i < 50; i++ {
use a[i+25]
}
Change-Id: I85e0130ee5d07f0ece9b17044bba1a2047414ce7
Reviewed-on: https://go-review.googlesource.com/21379
Reviewed-by: David Chase <drchase@google.com>
Run-TryBot: Alexandru Moșoi <alexandru@mosoi.ro>
TryBot-Result: Gobot Gobot <gobot@golang.org>
|
|
Signed-off-by: Eric Engestrom <eric@engestrom.ch>
Change-Id: I91873aaebf79bdf1c00d38aacc1a1fb8d79656a7
Reviewed-on: https://go-review.googlesource.com/21433
Reviewed-by: Ian Lance Taylor <iant@golang.org>
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
|
|
There are 5293 loop in the main go repository.
A survey of the top most common for loops:
18 for __k__ := 0; i < len(sa.Addr); i++ {
19 for __k__ := 0; ; i++ {
19 for __k__ := 0; i < 16; i++ {
25 for __k__ := 0; i < length; i++ {
30 for __k__ := 0; i < 8; i++ {
49 for __k__ := 0; i < len(s); i++ {
67 for __k__ := 0; i < n; i++ {
376 for __k__ := range __slice__ {
685 for __k__, __v__ := range __slice__ {
2074 for __, __v__ := range __slice__ {
The algorithm to find induction variables handles all cases
with an upper limit. It currently doesn't find related induction
variables such as c * ind or c + ind.
842 out of 22954 bound checks are removed for src/make.bash.
1957 out of 42952 bounds checks are removed for src/all.bash.
Things to do in follow-up CLs:
* Find the associated pointer for `for _, v := range a {}`
* Drop the NilChecks on the pointer.
* Replace the implicit induction variable by a loop over the pointer
Generated garbage can be reduced if we share the sdom between passes.
% benchstat old.txt new.txt
name old time/op new time/op delta
Template 337ms ± 3% 333ms ± 3% ~ (p=0.258 n=9+9)
GoTypes 1.11s ± 2% 1.10s ± 2% ~ (p=0.912 n=10+10)
Compiler 5.25s ± 1% 5.29s ± 2% ~ (p=0.077 n=9+9)
MakeBash 33.5s ± 1% 34.1s ± 2% +1.85% (p=0.011 n=9+9)
name old alloc/op new alloc/op delta
Template 63.6MB ± 0% 63.9MB ± 0% +0.52% (p=0.000 n=10+9)
GoTypes 218MB ± 0% 219MB ± 0% +0.59% (p=0.000 n=10+9)
Compiler 978MB ± 0% 985MB ± 0% +0.69% (p=0.000 n=10+10)
name old allocs/op new allocs/op delta
Template 582k ± 0% 583k ± 0% +0.10% (p=0.000 n=10+10)
GoTypes 1.78M ± 0% 1.78M ± 0% +0.12% (p=0.000 n=10+10)
Compiler 7.68M ± 0% 7.69M ± 0% +0.05% (p=0.000 n=10+10)
name old text-bytes new text-bytes delta
HelloSize 581k ± 0% 581k ± 0% -0.08% (p=0.000 n=10+10)
CmdGoSize 6.40M ± 0% 6.39M ± 0% -0.08% (p=0.000 n=10+10)
name old data-bytes new data-bytes delta
HelloSize 3.66k ± 0% 3.66k ± 0% ~ (all samples are equal)
CmdGoSize 134k ± 0% 134k ± 0% ~ (all samples are equal)
name old bss-bytes new bss-bytes delta
HelloSize 126k ± 0% 126k ± 0% ~ (all samples are equal)
CmdGoSize 149k ± 0% 149k ± 0% ~ (all samples are equal)
name old exe-bytes new exe-bytes delta
HelloSize 947k ± 0% 946k ± 0% -0.01% (p=0.000 n=10+10)
CmdGoSize 9.92M ± 0% 9.91M ± 0% -0.06% (p=0.000 n=10+10)
Change-Id: Ie74bdff46fd602db41bb457333d3a762a0c3dc4d
Reviewed-on: https://go-review.googlesource.com/20517
Reviewed-by: David Chase <drchase@google.com>
Run-TryBot: Alexandru Moșoi <alexandru@mosoi.ro>
|
