| Age | Commit message (Collapse) | Author |
|---|
|
When the control value of a If block is known for a particular inbound edge
because its value can be inferred from the control value of its predecessor,
then this inbound edge can be redirected to the known successor directly,
This CL optimizes this kind of cases to eliminate unnecessary comparision.
For example, the following piece of code comes from runtime.atoi,
if !neg && un > uint(maxInt) {
return 0, false
}
if neg && un > uint(maxInt)+1 {
return 0, false
}
Before this optimization, if the first "if" statement does not return, both
conditions of the second "if" statement will be checked. But obviously the
value of neg is known through the first "if" statement, and there is no need
to check neg repeatedly.
After this optimization, this redundancy check is eliminated, and the execution
logic becomes as follows.
if !neg {
if un > uint(maxInt) {
return 0, false
}
} else {
if un > uint(maxInt)+1 {
return 0, false
}
}
This CL does not bring significant performance changes, but it makes the code
structure look more reasonable.
Statistical data from tool compilecmp on Linux/amd64:
name old time/op new time/op delta
Template 380ms ± 4% 385ms ± 3% +1.16% (p=0.000 n=50+49)
Unicode 168ms ± 9% 169ms ± 9% ~ (p=0.421 n=49+46)
GoTypes 1.99s ± 4% 2.02s ± 4% +1.48% (p=0.000 n=49+49)
Compiler 188ms ± 8% 188ms ± 9% ~ (p=0.997 n=49+50)
SSA 11.8s ± 2% 12.0s ± 2% +1.24% (p=0.000 n=48+50)
Flate 242ms ± 6% 244ms ± 9% ~ (p=0.307 n=46+49)
GoParser 361ms ± 3% 366ms ± 4% +1.23% (p=0.000 n=48+49)
Reflect 836ms ± 3% 842ms ± 3% +0.70% (p=0.004 n=48+48)
Tar 335ms ± 3% 340ms ± 4% +1.47% (p=0.000 n=49+46)
XML 432ms ± 4% 437ms ± 4% +1.11% (p=0.002 n=49+49)
LinkCompiler 701ms ± 4% 704ms ± 5% ~ (p=0.278 n=49+50)
ExternalLinkCompiler 1.83s ± 3% 1.84s ± 3% +0.51% (p=0.034 n=48+49)
LinkWithoutDebugCompiler 436ms ± 6% 438ms ± 6% ~ (p=0.419 n=48+49)
[Geo mean] 612ms 617ms +0.84%
name old alloc/op new alloc/op delta
Template 38.7MB ± 1% 39.1MB ± 1% +1.19% (p=0.000 n=50+50)
Unicode 28.1MB ± 0% 28.1MB ± 0% +0.20% (p=0.000 n=49+45)
GoTypes 168MB ± 1% 170MB ± 1% +1.05% (p=0.000 n=48+49)
Compiler 23.0MB ± 1% 23.1MB ± 1% +0.63% (p=0.000 n=50+50)
SSA 1.54GB ± 1% 1.55GB ± 1% +0.85% (p=0.000 n=50+50)
Flate 23.6MB ± 1% 23.9MB ± 1% +1.36% (p=0.000 n=43+46)
GoParser 35.0MB ± 1% 35.3MB ± 1% +0.94% (p=0.000 n=50+50)
Reflect 84.7MB ± 1% 86.1MB ± 1% +1.72% (p=0.000 n=49+49)
Tar 34.5MB ± 1% 34.9MB ± 1% +1.07% (p=0.000 n=47+48)
XML 44.2MB ± 3% 44.6MB ± 3% +0.70% (p=0.003 n=50+49)
LinkCompiler 128MB ± 0% 128MB ± 0% +0.01% (p=0.004 n=49+50)
ExternalLinkCompiler 120MB ± 0% 120MB ± 0% +0.01% (p=0.000 n=49+50)
LinkWithoutDebugCompiler 77.3MB ± 0% 77.3MB ± 0% +0.02% (p=0.000 n=50+50)
[Geo mean] 69.1MB 69.6MB +0.75%
file before after Δ %
addr2line 4049276 4051308 +2032 +0.050%
api 5248940 5248996 +56 +0.001%
asm 4868093 4868037 -56 -0.001%
buildid 2627666 2626026 -1640 -0.062%
cgo 4614432 4615040 +608 +0.013%
compile 23298888 23301267 +2379 +0.010%
cover 4591609 4591161 -448 -0.010%
dist 3449638 3450254 +616 +0.018%
doc 3925667 3926363 +696 +0.018%
fix 3322936 3323464 +528 +0.016%
link 6628632 6629560 +928 +0.014%
nm 3991753 3996497 +4744 +0.119%
objdump 4396119 4395615 -504 -0.011%
pack 2399719 2399535 -184 -0.008%
pprof 13616418 13622866 +6448 +0.047%
test2json 2646121 2646081 -40 -0.002%
trace 10233087 10226359 -6728 -0.066%
vet 7117994 7121066 +3072 +0.043%
total 111026988 111039495 +12507 +0.011%
On linux arm64:
name old time/op new time/op delta
Template 284ms ± 1% 286ms ± 1% +0.70% (p=0.000 n=49+50)
Unicode 125ms ± 3% 125ms ± 2% ~ (p=0.548 n=50+50)
GoTypes 1.69s ± 1% 1.71s ± 1% +1.02% (p=0.000 n=49+49)
Compiler 125ms ± 1% 124ms ± 2% -0.35% (p=0.020 n=50+50)
SSA 12.7s ± 1% 12.8s ± 1% +1.21% (p=0.000 n=49+49)
Flate 172ms ± 1% 173ms ± 1% +0.20% (p=0.047 n=50+50)
GoParser 265ms ± 1% 266ms ± 1% +0.64% (p=0.000 n=50+50)
Reflect 651ms ± 1% 650ms ± 1% ~ (p=0.079 n=48+48)
Tar 246ms ± 1% 246ms ± 1% ~ (p=0.202 n=50+46)
XML 328ms ± 1% 332ms ± 1% +1.28% (p=0.000 n=50+49)
LinkCompiler 600ms ± 1% 599ms ± 1% ~ (p=0.264 n=50+50)
ExternalLinkCompiler 1.88s ± 1% 1.90s ± 0% +1.36% (p=0.000 n=50+50)
LinkWithoutDebugCompiler 365ms ± 1% 365ms ± 1% ~ (p=0.602 n=50+46)
[Geo mean] 490ms 492ms +0.47%
name old alloc/op new alloc/op delta
Template 38.8MB ± 1% 39.1MB ± 1% +0.92% (p=0.000 n=44+42)
Unicode 28.4MB ± 0% 28.4MB ± 0% +0.22% (p=0.000 n=44+45)
GoTypes 169MB ± 1% 171MB ± 1% +1.12% (p=0.000 n=50+50)
Compiler 23.2MB ± 1% 23.3MB ± 1% +0.56% (p=0.000 n=42+43)
SSA 1.55GB ± 0% 1.56GB ± 0% +0.91% (p=0.000 n=48+49)
Flate 23.7MB ± 2% 24.0MB ± 1% +1.20% (p=0.000 n=50+50)
GoParser 35.3MB ± 1% 35.6MB ± 1% +0.88% (p=0.000 n=50+50)
Reflect 85.0MB ± 0% 86.5MB ± 0% +1.70% (p=0.000 n=49+48)
Tar 34.5MB ± 1% 34.9MB ± 1% +1.03% (p=0.000 n=47+50)
XML 43.8MB ± 2% 44.0MB ± 0% +0.41% (p=0.002 n=49+38)
LinkCompiler 136MB ± 0% 136MB ± 0% +0.01% (p=0.006 n=50+49)
ExternalLinkCompiler 127MB ± 0% 127MB ± 0% +0.02% (p=0.000 n=49+50)
LinkWithoutDebugCompiler 84.1MB ± 0% 84.1MB ± 0% ~ (p=0.534 n=50+50)
[Geo mean] 70.4MB 70.9MB +0.69%
file before after Δ %
addr2line 4006004 4004556 -1448 -0.036%
api 5029716 5028828 -888 -0.018%
asm 4936863 4934943 -1920 -0.039%
buildid 2594947 2594099 -848 -0.033%
cgo 4399702 4399502 -200 -0.005%
compile 22233139 22230486 -2653 -0.012%
cover 4443681 4443881 +200 +0.005%
dist 3365902 3365486 -416 -0.012%
doc 3776175 3776151 -24 -0.001%
fix 3218624 3218600 -24 -0.001%
link 6365001 6361409 -3592 -0.056%
nm 3923345 3923065 -280 -0.007%
objdump 4295473 4296673 +1200 +0.028%
pack 2390561 2389393 -1168 -0.049%
pprof 12866419 12865115 -1304 -0.010%
test2json 2587113 2585561 -1552 -0.060%
trace 9609814 9610846 +1032 +0.011%
vet 6790272 6789760 -512 -0.008%
total 106832751 106818354 -14397 -0.013%
Update: #37608
Change-Id: I2831238b12e3af5aef2261f64f804bf0a8b43f86
Reviewed-on: https://go-review.googlesource.com/c/go/+/244737
Reviewed-by: eric fang <eric.fang@arm.com>
Reviewed-by: Keith Randall <khr@golang.org>
Trust: eric fang <eric.fang@arm.com>
Run-TryBot: eric fang <eric.fang@arm.com>
TryBot-Result: Go Bot <gobot@golang.org>
|
|
Currently, we keep track of slice len by mapping from slice ID to
len/cap SSA value. However, slice len/cap can have multiple SSA values,
so when updating fact table for slice len/cap, we only update in one
place.
Instead, we can take advantage of the transitive relations provided by
poset. So all duplicated slice lens are set as equal to one another.
When updating fact table for one, that fact will be reflected to all
others. The same mechanism is applied for slice cap.
Removes 15 bounds checks from std/cmd.
Fixes #42603
Change-Id: I32c07968824cc33765b1e441b3ae2c4b5f5997c3
Reviewed-on: https://go-review.googlesource.com/c/go/+/273670
Trust: Cuong Manh Le <cuong.manhle.vn@gmail.com>
Run-TryBot: Cuong Manh Le <cuong.manhle.vn@gmail.com>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>
|
|
addLocalInductiveFacts
CL 244579 added guard clauses to prevent a faulty state that was
possible under the incorrect logic of the uniquePred loop in
addLocalInductiveFacts. That faulty state was still making the
intended optimization, but not for the correct reason.
Removing the faulty state also removed the overly permissive application
of the optimization, and therefore made these two tests fail.
We disabled the tests of this optimization in CL 244579 to allow us to
quickly apply the fix in the CL. This CL now corrects the logic of the
uniquePred loop in order to apply the optimization correctly.
The comment above the uniquePred loop says that it will follow unique
predecessors until it reaches a join point. Without updating the child
node on each iteration, it cannot follow the chain of unique
predecessors more than one step. Adding the update to the child node
on each iteration of the loop allows the logic to follow the chain of
unique predecessors until reaching a join point (because a non-unique
predecessor will signify a join point).
Updates #40502.
Change-Id: I23d8367046a2ab3ce4be969631f9ba15dc533e6c
Reviewed-on: https://go-review.googlesource.com/c/go/+/246157
Run-TryBot: Dmitri Shuralyov <dmitshur@golang.org>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: David Chase <drchase@google.com>
Trust: Dmitri Shuralyov <dmitshur@golang.org>
|
|
Fixes #40746
Change-Id: I539f07d1f958dacee87d846171a8889d03182d25
Reviewed-on: https://go-review.googlesource.com/c/go/+/248397
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>
|
|
block to phi block
Currently in addLocalInductiveFacts, we only check whether
direct edge from if block to phi block exists. If not, the
following logic will treat the phi block as the first successor,
which is wrong.
This patch makes prove pass more conservative, so we disable
some cases in test/prove.go. We will do some optimization in
the following CL and enable these cases then.
Fixes #40367.
Change-Id: I27cf0248f3a82312a6f7dabe11c79a1a34cf5412
Reviewed-on: https://go-review.googlesource.com/c/go/+/244579
Reviewed-by: Zach Jones <zachj1@gmail.com>
Reviewed-by: Keith Randall <khr@golang.org>
Run-TryBot: Keith Randall <khr@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
|
|
Taking over Zach's CL 212277. Just cleaned up and added a test.
For a positive, signed integer, an arithmetic right shift of count
(bit-width - 1) equals zero. e.g. int64(22) >> 63 -> 0. This CL makes
prove replace these right shifts with a zero-valued constant.
These shifts may arise in source code explicitly, but can also be
created by the generic rewrite of signed division by a power of 2.
// Signed divide by power of 2.
// n / c = n >> log(c) if n >= 0
// = (n+c-1) >> log(c) if n < 0
// We conditionally add c-1 by adding n>>63>>(64-log(c))
(first shift signed, second shift unsigned).
(Div64 <t> n (Const64 [c])) && isPowerOfTwo(c) ->
(Rsh64x64
(Add64 <t> n (Rsh64Ux64 <t>
(Rsh64x64 <t> n (Const64 <typ.UInt64> [63]))
(Const64 <typ.UInt64> [64-log2(c)])))
(Const64 <typ.UInt64> [log2(c)]))
If n is known to be positive, this rewrite includes an extra Add and 2
extra Rsh. This CL will allow prove to replace one of the extra Rsh with
a 0. That replacement then allows lateopt to remove all the unneccesary
fixups from the generic rewrite.
There is a rewrite rule to handle this case directly:
(Div64 n (Const64 [c])) && isNonNegative(n) && isPowerOfTwo(c) ->
(Rsh64Ux64 n (Const64 <typ.UInt64> [log2(c)]))
But this implementation of isNonNegative really only handles constants
and a few special operations like len/cap. The division could be
handled if the factsTable version of isNonNegative were available.
Unfortunately, the first opt pass happens before prove even has a
chance to deduce the numerator is non-negative, so the generic rewrite
has already fired and created the extra Ops discussed above.
Fixes #36159
By Printf count, this zeroes 137 right shifts when building std and cmd.
Change-Id: Iab486910ac9d7cfb86ace2835456002732b384a2
Reviewed-on: https://go-review.googlesource.com/c/go/+/232857
Run-TryBot: Keith Randall <khr@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Cherry Zhang <cherryyz@google.com>
|
|
CL 212777 added a check to isNonNegative
to return true for unsigned values.
However, the SSA backend isn't type safe
enough for that to be sound.
The other checks in isNonNegative
look only at the pattern of bits.
Remove the type-based check.
Updates #37753
Change-Id: I059d0e86353453133f2a160dce53af299f42e533
Reviewed-on: https://go-review.googlesource.com/c/go/+/222620
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>
|
|
Instead of writing AuxInt during prove and then zeroing it during lower,
just don't write it in the first place.
Passes toolstash-check -all.
Change-Id: Iea4b555029a9d69332e835536f9cf3a42b8223db
Reviewed-on: https://go-review.googlesource.com/c/go/+/220682
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
Reviewed-by: Cherry Zhang <cherryyz@google.com>
|
|
The gains from this aren't particularly impressive.
Still, it is cheap and easy, and
it will keep me from wondering about whether it
might help to add X every time I look at this function.
This updated function is pretty exhaustive;
I examined every op encountered in a call to isNonNegative
when compiling all the stuff hanging around in my GOPATH,
for both 386 and amd64.
(32 bit architectures were somewhat neglected before.)
Object file size impact, 64 bit:
file before after Δ %
archive/zip.a 359352 359284 -68 -0.019%
cmd/compile/internal/ssa.a 30715960 30717526 +1566 +0.005%
cmd/internal/obj/arm64.a 2972532 2972440 -92 -0.003%
cmd/internal/obj/riscv.a 297714 297672 -42 -0.014%
debug/dwarf.a 656336 655346 -990 -0.151%
debug/gosym.a 183352 183122 -230 -0.125%
encoding/gob.a 901130 900798 -332 -0.037%
image/gif.a 171884 171890 +6 +0.003%
internal/trace.a 506930 507270 +340 +0.067%
math.a 233506 233490 -16 -0.007%
reflect.a 1431740 1431476 -264 -0.018%
runtime.a 3854480 3854332 -148 -0.004%
unicode/utf16.a 8920 8980 +60 +0.673%
total 133000610 133000400 -210 -0.000%
Object file size impact, 32 bit:
file before after Δ %
archive/zip.a 330794 329640 -1154 -0.349%
cmd/compile/internal/gc.a 8090204 8090026 -178 -0.002%
cmd/compile/internal/ssa.a 29392460 29393890 +1430 +0.005%
cmd/internal/goobj2.a 189512 189492 -20 -0.011%
cmd/internal/obj/arm64.a 2444942 2444860 -82 -0.003%
cmd/internal/obj/riscv.a 272848 272806 -42 -0.015%
cmd/link/internal/loader.a 388548 388544 -4 -0.001%
cmd/link/internal/loadpe.a 158776 158684 -92 -0.058%
cmd/vendor/golang.org/x/arch/ppc64/ppc64asm.a 511824 511316 -508 -0.099%
cmd/vendor/golang.org/x/arch/x86/x86asm.a 512812 512704 -108 -0.021%
cmd/vendor/golang.org/x/sys/unix.a 942422 942218 -204 -0.022%
compress/bzip2.a 88768 88680 -88 -0.099%
crypto/tls.a 1655542 1655396 -146 -0.009%
debug/dwarf.a 608520 605822 -2698 -0.443%
debug/gosym.a 168282 168276 -6 -0.004%
debug/pe.a 173146 173108 -38 -0.022%
encoding/gob.a 797978 797724 -254 -0.032%
encoding/hex.a 44080 44020 -60 -0.136%
image/gif.a 152142 152148 +6 +0.004%
internal/xcoff.a 186480 185834 -646 -0.346%
math.a 257866 257854 -12 -0.005%
net/http.a 3588246 3588150 -96 -0.003%
net/textproto.a 162384 162120 -264 -0.163%
reflect.a 1316204 1316058 -146 -0.011%
regexp.a 373346 373248 -98 -0.026%
runtime/pprof.a 345318 345088 -230 -0.067%
runtime.a 3513902 3513714 -188 -0.005%
syscall.a 781406 781018 -388 -0.050%
time.a 483814 483750 -64 -0.013%
unicode/utf16.a 8394 8364 -30 -0.357%
vendor/golang.org/x/crypto/cryptobyte.a 287100 286706 -394 -0.137%
vendor/golang.org/x/net/route.a 175042 174724 -318 -0.182%
total 121677354 121670234 -7120 -0.006%
Change-Id: Ie672752feb5e94dd151836f852181980710e820d
Reviewed-on: https://go-review.googlesource.com/c/go/+/212777
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>
|
|
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>
|
|
The name of the function should mention division.
Eliminate double negatives from the comment describing it.
Change-Id: Icef1a5139b3a91b86acb930af97938f5160f7342
Reviewed-on: https://go-review.googlesource.com/c/go/+/217001
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
Reviewed-by: Daniel Martí <mvdan@mvdan.cc>
|
|
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>
|
|
Instead of using a two-slot array and having to remember which
index is the signed poset, and which is the unsigned one, just
use two different variables.
Change-Id: Ic7f7676436c51bf43a182e999a926f8b7f69434b
Reviewed-on: https://go-review.googlesource.com/c/go/+/196678
Reviewed-by: Keith Randall <khr@golang.org>
|
|
This was a cause of some statements being lost.
Change-Id: I81c95dcf3df6ed8a03b7578a27f9b21d33b3cf39
Reviewed-on: https://go-review.googlesource.com/c/go/+/198484
Run-TryBot: David Chase <drchase@google.com>
Reviewed-by: Jeremy Faller <jeremy@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>
|
|
Now that OpSliceMake is called by runtime.makeslice callers,
prove can see and record the actual length and cap of each
slice being constructed.
This small patch is enough to remove 260 additional bound checks
from cmd+std.
Thanks to Martin Möhrmann for pointing me to CL141822 that
I had missed.
Updates #24660
Change-Id: I14556850f285392051f3f07d13b456b608b64eb9
Reviewed-on: https://go-review.googlesource.com/c/go/+/196784
Run-TryBot: Giovanni Bajo <rasky@develer.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: David Chase <drchase@google.com>
|
|
Array accesses with index types smaller than the machine word size may
involve a sign or zero extension of the index value before bounds
checking. Currently, this defeats prove because the facts about the
original index value don't flow through the sign/zero extension.
This CL fixes this by looking back through value-preserving sign/zero
extensions when adding facts via Update and, where appropriate, applying
the same facts using the pre-extension value. This fix is enhanced by
also looking back through value-preserving extensions within
ft.isNonNegative to infer whether the extended value is known to be
non-negative. Without this additional isNonNegative enhancement, this
logic is rendered significantly less effective by the limitation
discussed in the next paragraph.
In Update, the application of facts to pre-extension values is limited
to cases where the domain of the new fact is consistent with the type of
the pre-extension value. There may be cases where this cross-domain
passing of facts is valid, but distinguishing them from the invalid
cases is difficult for me to reason about and to implement.
Assessing which cases to allow requires details about the context and
inferences behind the fact being applied which are not available
within Update. Additional difficulty arises from the fact that the SSA
does not curently differentiate extensions added by the compiler for
indexing operations, extensions added by the compiler for implicit
conversions, or explicit extensions from the source.
Examples of some cases that would need to be filtered correctly for
cross-domain facts:
(1) A uint8 is zero-extended to int for indexing (a value-preserving
zeroExt). When, if ever, can signed domain facts learned about the int be
applied to the uint8?
(2) An int8 is sign-extended to int16 (value-preserving) for an equality
comparison. Equality comparison facts are currently always learned in both
the signed and unsigned domains. When, if ever, can the unsigned facts
learned about the int16, from the int16 != int16 comparison, be applied
to the original int8?
This is an alternative to CL 122695 and CL 174309. Compared to CL 122695,
this CL differs in that the facts added about the pre-extension value will
pass through the Update method, where additional inferences are processed
(e.g. fence-post implications, see #29964). CL 174309 is limited to bounds
checks, so is narrower in application, and makes the code harder to read.
Fixes #26292.
Fixes #29964.
Fixes #15074
Removes 238 bounds checks from std/cmd.
Change-Id: I1f87c32ee672bfb8be397b27eab7a4c2f304893f
Reviewed-on: https://go-review.googlesource.com/c/go/+/174704
Run-TryBot: Zach Jones <zachj1@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Giovanni Bajo <rasky@develer.com>
|
|
For int8, int16, and int32, comparing their unsigned value to MaxInt64
to determine non-negativity doesn't make sense, because they have
negative values whose unsigned representation is smaller than that.
Fix is simply to compare with the appropriate upper bound based on the
value type's size.
Fixes #32560.
Change-Id: Ie7afad7a56af92bd890ba5ff33c86d1df06cfd9a
Reviewed-on: https://go-review.googlesource.com/c/go/+/181797
Run-TryBot: Matthew Dempsky <mdempsky@google.com>
Reviewed-by: Josh Bleecher Snyder <josharian@gmail.com>
Reviewed-by: David Chase <drchase@google.com>
Reviewed-by: Keith Randall <khr@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
|
|
This is a follow-up CL to https://golang.org/cl/170118, updating a comment made
incorrect by that CL.
Change-Id: I5a29cfae331fbbbb36c96d96f9e4949393a5942d
Reviewed-on: https://go-review.googlesource.com/c/go/+/170123
Reviewed-by: Josh Bleecher Snyder <josharian@gmail.com>
Run-TryBot: Daniel Martí <mvdan@mvdan.cc>
TryBot-Result: Gobot Gobot <gobot@golang.org>
|
|
When branching at a bounds check for indexing or slicing ops, prove currently
only learns from the upper bound. On the positive branch, we currently learn
i < len(a) (or i <= len(a)) in both the signed and unsigned domains.
This CL makes prove also learn from the lower bound. Specifically, on the
positive branch from index or slicing ops, prove will now ALSO learn i >= 0 in
the signed domain (this fact is of no value in the unsigned domain).
The substantive change itself is only an additional call to addRestrictions,
though I've also inverted the nested switch statements around that call for the
sake of clarity.
This CL removes 92 bounds checks from std and cmd. It passes all tests and
shows no deltas on compilecmp.
Fixes #28885
Change-Id: I13eccc36e640eb599fa6dc5aa3be3c7d7abd2d9e
Reviewed-on: https://go-review.googlesource.com/c/go/+/170121
Run-TryBot: Daniel Martí <mvdan@mvdan.cc>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Giovanni Bajo <rasky@develer.com>
|
|
Prove requires access to a zero-valued constant in multiple heavily-used
code paths. Currently, prove is checking for the existence of the constant on
every iteration of these paths, and creating it if not found.
This CL preempts all of these checks by finding or creating the zero constant
Value, just once, when the factsTable is initialised on entry to prove(). The
Method used to initialise the zero constant, func.ConstInt64(), finds an
existing constant if present, or creates one in the entry block otherwise.
Fixes #31141
Change-Id: Ic9a2fd9d79b67025e24d4483f6e87cf8213ead24
Reviewed-on: https://go-review.googlesource.com/c/go/+/170118
Reviewed-by: Giovanni Bajo <rasky@develer.com>
Run-TryBot: Giovanni Bajo <rasky@develer.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
|
|
Prove currently fails to remove bounds checks of the form:
if i >= 0 { // hint that i is non-negative
for i < len(data) { // i becomes Phi in the loop SSA
_ = data[i] // data[Phi]; bounds check!!
i++
}
}
addIndVarRestrictions fails to identify that the loop induction
variable, (Phi), is non-negative. As a result, the restrictions,
i <= Phi < len(data), are only added for the signed domain. When
testing the bounds check, addBranchRestrictions is similarly unable
to infer that Phi is non-negative. As a result, the restriction,
Phi >= len(data), is only added/tested for the unsigned domain.
This CL changes the isNonNegative method to utilise the factTable's
partially ordered set (poset). It also adds field factTable.zero to
allow isNonNegative to query the poset using the zero(0) constant
found or created early in prove.
Fixes #28956
Change-Id: I792f886c652eeaa339b0d57d5faefbf5922fe44f
Reviewed-on: https://go-review.googlesource.com/c/go/+/161437
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Giovanni Bajo <rasky@develer.com>
|
|
In the case of x+d >= w, where d and w are constants, we are
deriving x is within the bound of min=w-d and max=maxInt-d. When
there is an overflow (min >= max), we know only one of x >= min
or x <= max is true, and we derive this by excluding the other.
When excluding x >= min, we did not consider the equal case, so
we could incorrectly derive x <= max when x == min.
Fixes #29502.
Change-Id: Ia9f7d814264b1a3ddf78f52e2ce23377450e6e8a
Reviewed-on: https://go-review.googlesource.com/c/156019
Reviewed-by: David Chase <drchase@google.com>
|
|
prove is able to find 94 occurrences in std cmd where a divisor
can't have the value -1. The change removes
the extraneous fix-up code for these cases.
Fixes #25239
Change-Id: Ic184de971f47cc57c702eb72805b8e291c14035d
Reviewed-on: https://go-review.googlesource.com/c/130215
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>
|
|
Change-Id: Ie3a8c54fe5e1b94f506cc0e6f650aab441d28a75
Reviewed-on: https://go-review.googlesource.com/137115
Reviewed-by: Keith Randall <khr@golang.org>
|
|
Fence-post implications of the form "x-1 >= w && x > min ⇒ x > w"
were not correctly handling unsigned domain, by always checking signed
limits.
This bug was uncovered once we taught prove that len(x) is always
>= 0 in the signed domain.
In the code being miscompiled (s[len(s)-1]), prove checks
whether len(s)-1 >= len(s) in the unsigned domain; if it proves
that this is always false, it can remove the bound check.
Notice that len(s)-1 >= len(s) can be true for len(s) = 0 because
of the wrap-around, so this is something prove should not be
able to deduce.
But because of the bug, the gate condition for the fence-post
implication was len(s) > MinInt64 instead of len(s) > 0; that
condition would be good in the signed domain but not in the
unsigned domain. And since in CL105635 we taught prove that
len(s) >= 0, the condition incorrectly triggered
(len(s) >= 0 > MinInt64) and things were going downfall.
Fixes #27251
Fixes #27289
Change-Id: I3dbcb1955ac5a66a0dcbee500f41e8d219409be5
Reviewed-on: https://go-review.googlesource.com/132495
Reviewed-by: Keith Randall <khr@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>
|
|
Currently, the prove pass derives implicit relations between len and
cap in the code that adds branch conditions. This is fine right now
because that's the only place we can encounter len and cap, but we're
about to add a second way to add assertions to the facts table that
can also produce facts involving len and cap.
Prepare for this by moving the fact derivation from updateRestrictions
(where it only applies on branches) to factsTable.update, which can
derive these facts no matter where the root facts come from.
Passes toolstash -cmp.
Change-Id: If09692d9eb98ffaa93f4cfa58ed2d8ba0887c111
Reviewed-on: https://go-review.googlesource.com/102602
Run-TryBot: Austin Clements <austin@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: David Chase <drchase@google.com>
|
|
Currently, we never add a relation between two constants to prove's
fact table because these are eliminated before prove runs, so it
currently doesn't handle facts like this very well even though they're
easy to prove.
We're about to start asserting some conditions that don't appear in
the SSA, but are constructed from existing SSA values that may both be
constants.
Hence, improve the fact table to understand relations between
constants by initializing the constant bounds of constant values to
the value itself, rather than noLimit.
Passes toolstash -cmp.
Change-Id: I71f8dc294e59f19433feab1c10b6d3c99b7f1e26
Reviewed-on: https://go-review.googlesource.com/102601
Run-TryBot: Austin Clements <austin@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: David Chase <drchase@google.com>
|
|
In prove, reuse posets between different functions by storing them
in the per-worker cache.
Allocation count regression caused by prove improvements is down
from 5% to 3% after this CL.
Updates #25179
Change-Id: I6d14003109833d9b3ef5165fdea00aa9c9e952e8
Reviewed-on: https://go-review.googlesource.com/110455
Run-TryBot: Giovanni Bajo <rasky@develer.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: David Chase <drchase@google.com>
|
|
Proves IsSliceInBounds one additional time building std+cmd,
at encoding/hex/hex.go:187:8.
The code is:
if numAvail := len(d.in) / 2; len(p) > numAvail {
p = p[:numAvail]
}
Previously we were unable to prove that numAvail >= 0.
Change-Id: Ie74e0aef809f9194c45e129ee3dae60bc3eae02f
Reviewed-on: https://go-review.googlesource.com/109415
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Giovanni Bajo <rasky@develer.com>
|
|
Fixes ssacheck build.
Change-Id: Idf1d2ea9a971a1f17f2fca568099e870bb5d913f
Reviewed-on: https://go-review.googlesource.com/110122
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Austin Clements <austin@google.com>
|
|
The prove pass sometimes has bounds information
that later rewrite passes do not.
Use this information to mark shifts as bounded,
and then use that information to generate better code on amd64.
It may prove to be helpful on other architectures, too.
While here, coalesce the existing shift lowering rules.
This triggers 35 times building std+cmd. The full list is below.
Here's an example from runtime.heapBitsSetType:
if nb < 8 {
b |= uintptr(*p) << nb
p = add1(p)
} else {
nb -= 8
}
We now generate better code on amd64 for that left shift.
Updates #25087
vendor/golang_org/x/crypto/curve25519/mont25519_amd64.go:48:20: Proved Rsh8Ux64 bounded
runtime/mbitmap.go:1252:22: Proved Lsh64x64 bounded
runtime/mbitmap.go:1265:16: Proved Lsh64x64 bounded
runtime/mbitmap.go:1275:28: Proved Lsh64x64 bounded
runtime/mbitmap.go:1645:25: Proved Lsh64x64 bounded
runtime/mbitmap.go:1663:25: Proved Lsh64x64 bounded
runtime/mbitmap.go:1808:41: Proved Lsh64x64 bounded
runtime/mbitmap.go:1831:49: Proved Lsh64x64 bounded
syscall/route_bsd.go:227:23: Proved Lsh32x64 bounded
syscall/route_bsd.go:295:23: Proved Lsh32x64 bounded
syscall/route_darwin.go:40:23: Proved Lsh32x64 bounded
compress/bzip2/bzip2.go:384:26: Proved Lsh64x16 bounded
vendor/golang_org/x/net/route/address.go:370:14: Proved Lsh64x64 bounded
compress/flate/inflate.go:201:54: Proved Lsh64x64 bounded
math/big/prime.go:50:25: Proved Lsh64x64 bounded
vendor/golang_org/x/crypto/cryptobyte/asn1.go:464:43: Proved Lsh8x8 bounded
net/ip.go:87:21: Proved Rsh8Ux64 bounded
cmd/internal/goobj/read.go:267:23: Proved Lsh64x64 bounded
cmd/vendor/golang.org/x/arch/arm64/arm64asm/decode.go:534:27: Proved Lsh32x32 bounded
cmd/vendor/golang.org/x/arch/arm64/arm64asm/decode.go:544:27: Proved Lsh32x32 bounded
cmd/internal/obj/arm/asm5.go:1044:16: Proved Lsh32x64 bounded
cmd/internal/obj/arm/asm5.go:1065:10: Proved Lsh32x32 bounded
cmd/internal/obj/mips/obj0.go:1311:21: Proved Lsh32x64 bounded
cmd/compile/internal/syntax/scanner.go:352:23: Proved Lsh64x64 bounded
go/types/expr.go:222:36: Proved Lsh64x64 bounded
crypto/x509/x509.go:1626:9: Proved Rsh8Ux64 bounded
cmd/link/internal/loadelf/ldelf.go:823:22: Proved Lsh8x64 bounded
net/http/h2_bundle.go:1470:17: Proved Lsh8x8 bounded
net/http/h2_bundle.go:1477:46: Proved Lsh8x8 bounded
net/http/h2_bundle.go:1481:31: Proved Lsh64x8 bounded
cmd/compile/internal/ssa/rewriteARM64.go:18759:17: Proved Lsh64x64 bounded
cmd/compile/internal/ssa/sparsemap.go:70:23: Proved Lsh32x64 bounded
cmd/compile/internal/ssa/sparsemap.go:73:45: Proved Lsh32x64 bounded
Change-Id: I58bb72f3e6f12f6ac69be633ea7222c245438142
Reviewed-on: https://go-review.googlesource.com/109776
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Giovanni Bajo <rasky@develer.com>
|
|
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>
|
|
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>
|
|
When a branch is followed, we apply the relation as described
in the domain relation table. In case the relation is in the
positive domain, we can also infer an unsigned relation if,
by that point, we know that both operands are non-negative.
Fixes #20393
Change-Id: Ieaf0c81558b36d96616abae3eb834c788dd278d5
Reviewed-on: https://go-review.googlesource.com/100278
Run-TryBot: Giovanni Bajo <rasky@develer.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Giovanni Bajo <rasky@develer.com>
Reviewed-by: David Chase <drchase@google.com>
|
|
Implement it through a partial order datastructure, which
keeps the relations between SSA values in a forest of DAGs
and is able to discover contradictions.
In make.bash, this patch is able to prove hundreds of conditions
which were not proved before.
Compilebench:
name old time/op new time/op delta
Template 371ms ± 2% 368ms ± 1% ~ (p=0.222 n=5+5)
Unicode 203ms ± 6% 199ms ± 3% ~ (p=0.421 n=5+5)
GoTypes 1.17s ± 4% 1.18s ± 1% ~ (p=0.151 n=5+5)
Compiler 5.54s ± 2% 5.59s ± 1% ~ (p=0.548 n=5+5)
SSA 12.9s ± 2% 13.2s ± 1% +2.96% (p=0.032 n=5+5)
Flate 245ms ± 2% 247ms ± 3% ~ (p=0.690 n=5+5)
GoParser 302ms ± 6% 302ms ± 4% ~ (p=0.548 n=5+5)
Reflect 764ms ± 4% 773ms ± 3% ~ (p=0.095 n=5+5)
Tar 354ms ± 6% 361ms ± 3% ~ (p=0.222 n=5+5)
XML 434ms ± 3% 429ms ± 1% ~ (p=0.421 n=5+5)
StdCmd 22.6s ± 1% 22.9s ± 1% +1.40% (p=0.032 n=5+5)
name old user-time/op new user-time/op delta
Template 436ms ± 8% 426ms ± 5% ~ (p=0.579 n=5+5)
Unicode 219ms ±15% 219ms ±12% ~ (p=1.000 n=5+5)
GoTypes 1.47s ± 6% 1.53s ± 6% ~ (p=0.222 n=5+5)
Compiler 7.26s ± 4% 7.40s ± 2% ~ (p=0.389 n=5+5)
SSA 17.7s ± 4% 18.5s ± 4% +4.13% (p=0.032 n=5+5)
Flate 257ms ± 5% 268ms ± 9% ~ (p=0.333 n=5+5)
GoParser 354ms ± 6% 348ms ± 6% ~ (p=0.913 n=5+5)
Reflect 904ms ± 2% 944ms ± 4% ~ (p=0.056 n=5+5)
Tar 398ms ±11% 430ms ± 7% ~ (p=0.079 n=5+5)
XML 501ms ± 7% 489ms ± 5% ~ (p=0.444 n=5+5)
name old text-bytes new text-bytes delta
HelloSize 670kB ± 0% 670kB ± 0% +0.00% (p=0.008 n=5+5)
CmdGoSize 7.22MB ± 0% 7.21MB ± 0% -0.07% (p=0.008 n=5+5)
name old data-bytes new data-bytes delta
HelloSize 9.88kB ± 0% 9.88kB ± 0% ~ (all equal)
CmdGoSize 248kB ± 0% 248kB ± 0% -0.06% (p=0.008 n=5+5)
name old bss-bytes new bss-bytes delta
HelloSize 125kB ± 0% 125kB ± 0% ~ (all equal)
CmdGoSize 145kB ± 0% 144kB ± 0% -0.20% (p=0.008 n=5+5)
name old exe-bytes new exe-bytes delta
HelloSize 1.43MB ± 0% 1.43MB ± 0% ~ (all equal)
CmdGoSize 14.5MB ± 0% 14.5MB ± 0% -0.06% (p=0.008 n=5+5)
Fixes #19714
Updates #20393
Change-Id: Ia090f5b5dc1bcd274ba8a39b233c1e1ace1b330e
Reviewed-on: https://go-review.googlesource.com/100277
Run-TryBot: Giovanni Bajo <rasky@develer.com>
Reviewed-by: David Chase <drchase@google.com>
|
|
I forgot this in CL 109358.
Change-Id: Ia5e8bd9cf43393f098b101a0d6a0c526e3e4f101
Reviewed-on: https://go-review.googlesource.com/109775
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
|
|
On amd64, Ctz must include special handling of zeros.
But the prove pass has enough information to detect whether the input
is non-zero, allowing a more efficient lowering.
Introduce new CtzNonZero ops to capture and use this information.
Benchmark code:
func BenchmarkVisitBits(b *testing.B) {
b.Run("8", func(b *testing.B) {
for i := 0; i < b.N; i++ {
x := uint8(0xff)
for x != 0 {
sink = bits.TrailingZeros8(x)
x &= x - 1
}
}
})
// and similarly so for 16, 32, 64
}
name old time/op new time/op delta
VisitBits/8-8 7.27ns ± 4% 5.58ns ± 4% -23.35% (p=0.000 n=28+26)
VisitBits/16-8 14.7ns ± 7% 10.5ns ± 4% -28.43% (p=0.000 n=30+28)
VisitBits/32-8 27.6ns ± 8% 19.3ns ± 3% -30.14% (p=0.000 n=30+26)
VisitBits/64-8 44.0ns ±11% 38.0ns ± 5% -13.48% (p=0.000 n=30+30)
Fixes #25077
Change-Id: Ie6e5bd86baf39ee8a4ca7cadcf56d934e047f957
Reviewed-on: https://go-review.googlesource.com/109358
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>
|
|
The logic in addBranchRestrictions didn't allow to correctly
model OpIs(Slice)Bound for signed domain, and it was also partly
implemented within addRestrictions.
Thanks to the previous changes, it is now possible to handle
the negative conditions correctly, so that we can learn
both signed/LT + unsigned/LT on the positive side, and
signed/GE + unsigned/GE on the negative side (but only if
the index can be proved to be non-negative).
This is able to prove ~50 more slice accesses in std+cmd.
Change-Id: I9858080dc03b16f85993a55983dbc4b00f8491b0
Reviewed-on: https://go-review.googlesource.com/104037
Run-TryBot: Giovanni Bajo <rasky@develer.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Austin Clements <austin@google.com>
|
|
addRestrictions was taking a branch parameter, binding its logic
to that of addBranchRestrictions. Since we will need to use it
for updating the facts table for induction variables, refactor it
to remove the branch parameter.
Passes toolstash -cmp.
Change-Id: Iaaec350a8becd1919d03d8574ffd1bbbd906d068
Reviewed-on: https://go-review.googlesource.com/104036
Run-TryBot: Giovanni Bajo <rasky@develer.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Austin Clements <austin@google.com>
|
|
prove used a complex logic when trying to prove branch conditions:
tryPushBranch() was sometimes leaving a checkpoint on the factsTable,
sometimes not, and the caller was supposed to check the return value
to know what to do.
Since we're going to make the prove descend logic a little bit more
complex by adding also induction variables, simplify the tryPushBranch
logic, by removing any factsTable checkpoint handling from it.
Passes toolstash -cmp.
Change-Id: Idfb1703df8a455f612f93158328b36c461560781
Reviewed-on: https://go-review.googlesource.com/104035
Run-TryBot: Giovanni Bajo <rasky@develer.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Austin Clements <austin@google.com>
|
|
The way Value.AuxInt represents unsigned numbers is currently
documented in genericOps.go, which is not the most obvious place for
it. Move that documentation to Value.AuxInt. Furthermore, to make it
harder to use incorrectly, introduce a Value.AuxUnsigned accessor that
returns the zero-extended value of Value.AuxInt.
Change-Id: I85030c3c68761404058a430e0b1c7464591b2f42
Reviewed-on: https://go-review.googlesource.com/102597
Run-TryBot: Austin Clements <austin@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Cherry Zhang <cherryyz@google.com>
|
|
Sometimes, we can end up calling update with a self-relation
about a variable (x REL x). In this case, there is no need
to record anything: the relation is unsatisfiable if and only
if it doesn't contain eq.
This also helps avoiding infinite loop in next CL that will
introduce transitive closure of relations.
Passes toolstash -cmp.
Change-Id: Ic408452ec1c13653f22ada35466ec98bc14aaa8e
Reviewed-on: https://go-review.googlesource.com/100276
Reviewed-by: Austin Clements <austin@google.com>
|
|
When an unsatisfiable relation is recorded in the facts table,
there is no need to compute further relations or updates
additional data structures.
Since we're about to transitively propagate relations, make
sure to fail as fast as possible to avoid doing useless work
in dead branches.
Passes toolstash -cmp.
Change-Id: I23eed376d62776824c33088163c7ac9620abce85
Reviewed-on: https://go-review.googlesource.com/100275
Reviewed-by: Austin Clements <austin@google.com>
|
|
The previous CL introduced isConstDelta. Use it to simplify the
OpSlicemask optimization in the prove pass. This passes toolstash
-cmp.
Change-Id: If2aa762db4cdc0cd1c581a536340530a9831081b
Reviewed-on: https://go-review.googlesource.com/87481
Reviewed-by: Keith Randall <khr@golang.org>
|
|
This adds four new deductions to the prove pass, all related to adding
or subtracting one from a value. This is the first hint of actual
arithmetic relations in the prove pass.
The most effective of these is
x-1 >= w && x > min ⇒ x > w
This helps eliminate bounds checks in code like
if x > 0 {
// do something with s[x-1]
}
Altogether, these deductions prove an additional 260 branches in std
and cmd. Furthermore, they will let us eliminate some tricky
compiler-inserted panics in the runtime that are interfering with
static analysis.
Fixes #23354.
Change-Id: I7088223e0e0cd6ff062a75c127eb4bb60e6dce02
Reviewed-on: https://go-review.googlesource.com/87480
Reviewed-by: Keith Randall <khr@golang.org>
Reviewed-by: Alexandru Moșoi <alexandru@mosoi.ro>
|
|
This adds a few simple deductions to the prove pass' fact table to
derive unsigned concrete limits from signed concrete limits where
possible.
This tweak lets the pass prove 70 additional branch conditions in std
and cmd.
This is based on a comment from the recently-deleted factsTable.get:
"// TODO: also use signed data if lim.min >= 0".
Change-Id: Ib4340249e7733070f004a0aa31254adf5df8a392
Reviewed-on: https://go-review.googlesource.com/87479
Reviewed-by: Alexandru Moșoi <alexandru@mosoi.ro>
Reviewed-by: Keith Randall <khr@golang.org>
|
|
Currently the prove pass uses implication queries. For each block, it
collects the set of branch conditions leading to that block, and
queries this fact table for whether any of these facts imply the
block's own branch condition (or its inverse). This works remarkably
well considering it doesn't do any deduction on these facts, but it
has various downsides:
1. It requires an implementation both of adding facts to the table and
determining implications. These are very nearly duals of each
other, but require separate implementations. Likewise, the process
of asserting facts of dominating branch conditions is very nearly
the dual of the process of querying implied branch conditions.
2. It leads to less effective use of derived facts. For example, the
prove pass currently derives facts about the relations between len
and cap, but can't make use of these unless a branch condition is
in the exact form of a derived fact. If one of these derived facts
contradicts another fact, it won't notice or make use of this.
This CL changes the approach of the prove pass to instead use
*contradiction* instead of implication. Rather than ever querying a
branch condition, it simply adds branch conditions to the fact table.
If this leads to a contradiction (specifically, it makes the fact set
unsatisfiable), that branch is impossible and can be cut. As a result,
1. We can eliminate the code for determining implications
(factsTable.get disappears entirely). Also, there is now a single
implementation of visiting and asserting branch conditions, since
we don't have to flip them around to treat them as facts in one
place and queries in another.
2. Derived facts can be used effectively. It doesn't matter *why* the
fact table is unsatisfiable; a contradiction in any of the facts is
enough.
3. As an added benefit, it's now quite easy to avoid traversing beyond
provably-unreachable blocks. In contrast, the current
implementation always visits all blocks.
The prove pass already has nearly all of the mechanism necessary to
compute unsatisfiability, which means this both simplifies the code
and makes it more powerful.
The only complication is that the current implication procedure has a
hack for dealing with the 0 <= Args[0] condition of OpIsInBounds and
OpIsSliceInBounds. We replace this with asserting the appropriate fact
when we process one of these conditions. This seems much cleaner
anyway, and works because we can now take advantage of derived facts.
This has no measurable effect on compiler performance.
Effectiveness:
There is exactly one condition in all of std and cmd that this fails
to prove that the old implementation could: (int64(^uint(0)>>1) < x)
in encoding/gob. This can never be true because x is an int, and it's
basically coincidence that the old code gets this. (For example, it
fails to prove the similar (x < ^int64(^uint(0)>>1)) condition that
immediately precedes it, and even though the conditions are logically
unrelated, it wouldn't get the second one if it hadn't first processed
the first!)
It does, however, prove a few dozen additional branches. These come
from facts that are added to the fact table about the relations
between len and cap. These were almost never queried directly before,
but could lead to contradictions, which the unsat-based approach is
able to use.
There are exactly two branches in std and cmd that this implementation
proves in the *other* direction. This sounds scary, but is okay
because both occur in already-unreachable blocks, so it doesn't matter
what we chose. Because the fact table logic is sound but incomplete,
it fails to prove that the block isn't reachable, even though it is
able to prove that both outgoing branches are impossible. We could
turn these blocks into BlockExit blocks, but it doesn't seem worth the
trouble of the extra proof effort for something that happens twice in
all of std and cmd.
Tests:
This CL updates test/prove.go to change the expected messages because
it can no longer give a "reason" why it proved or disproved a
condition. It also adds a new test of a branch it couldn't prove
before.
It mostly guts test/sliceopt.go, removing everything related to slice
bounds optimizations and moving a few relevant tests to test/prove.go.
Much of this test is actually unreachable. The new prove pass figures
this out and doesn't try to prove anything about the unreachable
parts. The output on the unreachable parts is already suspect because
anything can be proved at that point, so it's really just a regression
test for an algorithm the compiler no longer uses.
This is a step toward fixing #23354. That issue is quite easy to fix
once we can use derived facts effectively.
Change-Id: Ia48a1b9ee081310579fe474e4a61857424ff8ce8
Reviewed-on: https://go-review.googlesource.com/87478
Reviewed-by: Keith Randall <khr@golang.org>
|
