diff options
author | Alexandru Moșoi <mosoi@google.com> | 2016-03-02 12:58:27 +0100 |
---|---|---|
committer | Alexandru Moșoi <alexandru@mosoi.ro> | 2016-04-01 09:37:58 +0000 |
commit | b91cc5303364c4aae758ff1f0b4efc66b7802700 (patch) | |
tree | 0e2e96fb803283c9a34c3a44de37f096afd4f596 /test/loopbce.go | |
parent | ea306ae625d001a43ef20163739593a21be51f97 (diff) | |
download | go-git-b91cc5303364c4aae758ff1f0b4efc66b7802700.tar.gz |
cmd/compile/internal/ssa: BCE for induction variables
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>
Diffstat (limited to 'test/loopbce.go')
-rw-r--r-- | test/loopbce.go | 176 |
1 files changed, 176 insertions, 0 deletions
diff --git a/test/loopbce.go b/test/loopbce.go new file mode 100644 index 0000000000..eb44092705 --- /dev/null +++ b/test/loopbce.go @@ -0,0 +1,176 @@ +// +build amd64 +// errorcheck -0 -d=ssa/loopbce/debug=3 + +package main + +func f0a(a []int) int { + x := 0 + for i := range a { // ERROR "Induction variable with minimum 0 and increment 1$" + x += a[i] // ERROR "Found redundant IsInBounds$" + } + return x +} + +func f0b(a []int) int { + x := 0 + for i := range a { // ERROR "Induction variable with minimum 0 and increment 1$" + b := a[i:] // ERROR "Found redundant IsSliceInBounds$" + x += b[0] + } + return x +} + +func f0c(a []int) int { + x := 0 + for i := range a { // ERROR "Induction variable with minimum 0 and increment 1$" + b := a[:i+1] // ERROR "Found redundant IsSliceInBounds \(len promoted to cap\)$" + x += b[0] + } + return x +} + +func f1(a []int) int { + x := 0 + for _, i := range a { // ERROR "Induction variable with minimum 0 and increment 1$" + x += i + } + return x +} + +func f2(a []int) int { + x := 0 + for i := 1; i < len(a); i++ { // ERROR "Induction variable with minimum 1 and increment 1$" + x += a[i] // ERROR "Found redundant IsInBounds$" + } + return x +} + +func f4(a [10]int) int { + x := 0 + for i := 0; i < len(a); i += 2 { // ERROR "Induction variable with minimum 0 and increment 2$" + x += a[i] // ERROR "Found redundant IsInBounds$" + } + return x +} + +func f5(a [10]int) int { + x := 0 + for i := -10; i < len(a); i += 2 { // ERROR "Induction variable with minimum -10 and increment 2$" + x += a[i] + } + return x +} + +func f6(a []int) { + for i := range a { // ERROR "Induction variable with minimum 0 and increment 1$" + b := a[0:i] // ERROR "Found redundant IsSliceInBounds \(len promoted to cap\)$" + f6(b) + } +} + +func g0a(a string) int { + x := 0 + for i := 0; i < len(a); i++ { // ERROR "Induction variable with minimum 0 and increment 1$" + x += int(a[i]) // ERROR "Found redundant IsInBounds$" + } + return x +} + +func g0b(a string) int { + x := 0 + for i := 0; len(a) > i; i++ { // ERROR "Induction variable with minimum 0 and increment 1$" + x += int(a[i]) // ERROR "Found redundant IsInBounds$" + } + return x +} + +func g1() int { + a := "evenlength" + x := 0 + for i := 0; i < len(a); i += 2 { // ERROR "Induction variable with minimum 0 and increment 2$" + x += int(a[i]) // ERROR "Found redundant IsInBounds$" + } + return x +} + +func g2() int { + a := "evenlength" + x := 0 + for i := 0; i < len(a); i += 2 { // ERROR "Induction variable with minimum 0 and increment 2$" + j := i + if a[i] == 'e' { // ERROR "Found redundant IsInBounds$" + j = j + 1 + } + x += int(a[j]) + } + return x +} + +func g3a() { + a := "this string has length 25" + for i := 0; i < len(a); i += 5 { // ERROR "Induction variable with minimum 0 and increment 5$" + useString(a[i:]) // ERROR "Found redundant IsSliceInBounds$" + useString(a[:i+3]) + } +} + +func g3b(a string) { + for i := 0; i < len(a); i++ { // ERROR "Induction variable with minimum 0 and increment 1$" + useString(a[i+1:]) // ERROR "Found redundant IsSliceInBounds$" + } +} + +func g3c(a string) { + for i := 0; i < len(a); i++ { // ERROR "Induction variable with minimum 0 and increment 1$" + useString(a[:i+1]) // ERROR "Found redundant IsSliceInBounds$" + } +} + +func h1(a []byte) { + c := a[:128] + for i := range c { // ERROR "Induction variable with minimum 0 and increment 1$" + c[i] = byte(i) // ERROR "Found redundant IsInBounds$" + } +} + +func h2(a []byte) { + for i := range a[:128] { // ERROR "Induction variable with minimum 0 and increment 1$" + a[i] = byte(i) + } +} + +func nobce1() { + // tests overflow of max-min + a := int64(9223372036854774057) + b := int64(-1547) + z := int64(1337) + + if a%z == b%z { + panic("invalid test: modulos should differ") + } + + for i := b; i < a; i += z { + // No induction variable is possible because i will overflow a first iteration. + useString("foobar") + } +} + +func nobce2(a string) { + for i := int64(0); i < int64(len(a)); i++ { // ERROR "Induction variable with minimum 0 and increment 1$" + useString(a[i:]) // ERROR "Found redundant IsSliceInBounds$" + } + for i := int64(0); i < int64(len(a))-31337; i++ { // ERROR "Induction variable with minimum 0 and increment 1$" + useString(a[i:]) // ERROR "Found redundant IsSliceInBounds$" + } + for i := int64(0); i < int64(len(a))+int64(-1<<63); i++ { // ERROR "Induction variable with minimum 0 and increment 1$" + // tests an overflow of StringLen-MinInt64 + useString(a[i:]) + } +} + +//go:noinline +func useString(a string) { +} + +func main() { +} |