• Alexandru Moșoi's avatar
    cmd/compile/internal/ssa: BCE for induction variables · b91cc530
    Alexandru Moșoi authored
    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/20517Reviewed-by: 's avatarDavid Chase <drchase@google.com>
    Run-TryBot: Alexandru Moșoi <alexandru@mosoi.ro>
    b91cc530
Name
Last commit
Last update
..
bench Loading commit data...
bugs Loading commit data...
chan Loading commit data...
ddd2.dir Loading commit data...
dwarf Loading commit data...
fixedbugs Loading commit data...
import2.dir Loading commit data...
import4.dir Loading commit data...
interface Loading commit data...
intrinsic.dir Loading commit data...
ken Loading commit data...
method4.dir Loading commit data...
safe Loading commit data...
stress Loading commit data...
syntax Loading commit data...
235.go Loading commit data...
64bit.go Loading commit data...
alias.go Loading commit data...
alias1.go Loading commit data...
append.go Loading commit data...
args.go Loading commit data...
assign.go Loading commit data...
assign1.go Loading commit data...
atomicload.go Loading commit data...
bigalg.go Loading commit data...
bigmap.go Loading commit data...
blank.go Loading commit data...
blank1.go Loading commit data...
bom.go Loading commit data...
bombad.go Loading commit data...
bounds.go Loading commit data...
chancap.go Loading commit data...
chanlinear.go Loading commit data...
char_lit.go Loading commit data...
char_lit1.go Loading commit data...
clearfat.go Loading commit data...
closedchan.go Loading commit data...
closure.go Loading commit data...
closure1.go Loading commit data...
closure2.go Loading commit data...
cmp.go Loading commit data...
cmp6.go Loading commit data...
cmplx.go Loading commit data...
cmplxdivide.c Loading commit data...
cmplxdivide.go Loading commit data...
cmplxdivide1.go Loading commit data...
complit.go Loading commit data...
complit1.go Loading commit data...
compos.go Loading commit data...
const.go Loading commit data...
const1.go Loading commit data...
const2.go Loading commit data...
const3.go Loading commit data...
const4.go Loading commit data...
const5.go Loading commit data...
const6.go Loading commit data...
convT2X.go Loading commit data...
convert.go Loading commit data...
convert1.go Loading commit data...
convert3.go Loading commit data...
convlit.go Loading commit data...
convlit1.go Loading commit data...
copy.go Loading commit data...
crlf.go Loading commit data...
ddd.go Loading commit data...
ddd1.go Loading commit data...
ddd2.go Loading commit data...
decl.go Loading commit data...
declbad.go Loading commit data...
defer.go Loading commit data...
deferfin.go Loading commit data...
deferprint.go Loading commit data...
deferprint.out Loading commit data...
divide.go Loading commit data...
divmod.go Loading commit data...
empty.go Loading commit data...
env.go Loading commit data...
eof.go Loading commit data...
eof1.go Loading commit data...
errchk Loading commit data...
escape.go Loading commit data...
escape2.go Loading commit data...
escape2n.go Loading commit data...
escape3.go Loading commit data...
escape4.go Loading commit data...
escape5.go Loading commit data...
escape_array.go Loading commit data...
escape_because.go Loading commit data...
escape_calls.go Loading commit data...
escape_closure.go Loading commit data...
escape_field.go Loading commit data...
escape_iface.go Loading commit data...
escape_indir.go Loading commit data...
escape_level.go Loading commit data...
escape_map.go Loading commit data...
escape_param.go Loading commit data...
escape_slice.go Loading commit data...
escape_struct_param1.go Loading commit data...
escape_struct_param2.go Loading commit data...
escape_struct_return.go Loading commit data...
fibo.go Loading commit data...
finprofiled.go Loading commit data...
float_lit.go Loading commit data...
float_lit2.go Loading commit data...
float_lit3.go Loading commit data...
floatcmp.go Loading commit data...
for.go Loading commit data...
func.go Loading commit data...
func1.go Loading commit data...
func2.go Loading commit data...
func3.go Loading commit data...
func4.go Loading commit data...
func5.go Loading commit data...
func6.go Loading commit data...
func7.go Loading commit data...
func8.go Loading commit data...
funcdup.go Loading commit data...
funcdup2.go Loading commit data...
gc.go Loading commit data...
gc1.go Loading commit data...
gc2.go Loading commit data...
gcstring.go Loading commit data...
goprint.go Loading commit data...
goprint.out Loading commit data...
goto.go Loading commit data...
heapsampling.go Loading commit data...
helloworld.go Loading commit data...
helloworld.out Loading commit data...
if.go Loading commit data...
import.go Loading commit data...
import1.go Loading commit data...
import2.go Loading commit data...
import4.go Loading commit data...
import5.go Loading commit data...
index.go Loading commit data...
index0.go Loading commit data...
index1.go Loading commit data...
index2.go Loading commit data...
indirect.go Loading commit data...
indirect1.go Loading commit data...
init.go Loading commit data...
init1.go Loading commit data...
initcomma.go Loading commit data...
initialize.go Loading commit data...
initializerr.go Loading commit data...
initloop.go Loading commit data...
inline.go Loading commit data...
int_lit.go Loading commit data...
intcvt.go Loading commit data...
intrinsic.go Loading commit data...
iota.go Loading commit data...
label.go Loading commit data...
label1.go Loading commit data...
linkmain.go Loading commit data...
linkmain_run.go Loading commit data...
linkx.go Loading commit data...
linkx_run.go Loading commit data...
literal.go Loading commit data...
live.go Loading commit data...
live1.go Loading commit data...
live2.go Loading commit data...
live_ssa.go Loading commit data...
live_syscall.go Loading commit data...
loopbce.go Loading commit data...
mallocfin.go Loading commit data...
map.go Loading commit data...
map1.go Loading commit data...
maplinear.go Loading commit data...
method.go Loading commit data...
method1.go Loading commit data...
method2.go Loading commit data...
method3.go Loading commit data...
method4.go Loading commit data...
method5.go Loading commit data...
named.go Loading commit data...
named1.go Loading commit data...
nil.go Loading commit data...
nilcheck.go Loading commit data...
nilptr.go Loading commit data...
nilptr2.go Loading commit data...
nilptr3.go Loading commit data...
nilptr3_ssa.go Loading commit data...
nilptr4.go Loading commit data...
nosplit.go Loading commit data...
nul1.go Loading commit data...
opt_branchlikely.go Loading commit data...
parentype.go Loading commit data...
peano.go Loading commit data...
phiopt.go Loading commit data...
print.go Loading commit data...
print.out Loading commit data...
printbig.go Loading commit data...
printbig.out Loading commit data...
prove.go Loading commit data...
range.go Loading commit data...
recover.go Loading commit data...
recover1.go Loading commit data...
recover2.go Loading commit data...
recover3.go Loading commit data...
recover4.go Loading commit data...
reflectmethod1.go Loading commit data...
reflectmethod2.go Loading commit data...
reflectmethod3.go Loading commit data...
reflectmethod4.go Loading commit data...
rename.go Loading commit data...
rename1.go Loading commit data...
reorder.go Loading commit data...
reorder2.go Loading commit data...
return.go Loading commit data...
rotate.go Loading commit data...
rotate0.go Loading commit data...
rotate1.go Loading commit data...
rotate2.go Loading commit data...
rotate3.go Loading commit data...
run.go Loading commit data...
rune.go Loading commit data...
runtime.go Loading commit data...
shift1.go Loading commit data...
shift2.go Loading commit data...
sieve.go Loading commit data...
sigchld.go Loading commit data...
sigchld.out Loading commit data...
simassign.go Loading commit data...
sinit.go Loading commit data...
sinit_run.go Loading commit data...
sizeof.go Loading commit data...
slice3.go Loading commit data...
slice3err.go Loading commit data...
slicecap.go Loading commit data...
sliceopt.go Loading commit data...
solitaire.go Loading commit data...
stack.go Loading commit data...
strength.go Loading commit data...
string_lit.go Loading commit data...
stringrange.go Loading commit data...
struct0.go Loading commit data...
switch.go Loading commit data...
switch2.go Loading commit data...
switch3.go Loading commit data...
switch4.go Loading commit data...
tinyfin.go Loading commit data...
torture.go Loading commit data...
turing.go Loading commit data...
typecheck.go Loading commit data...
typecheckloop.go Loading commit data...
typeswitch.go Loading commit data...
typeswitch1.go Loading commit data...
typeswitch2.go Loading commit data...
typeswitch3.go Loading commit data...
undef.go Loading commit data...
utf.go Loading commit data...
varerr.go Loading commit data...
varinit.go Loading commit data...
writebarrier.go Loading commit data...
zerodivide.go Loading commit data...