<div style="line-height:1.7;color:#000000;font-size:14px;font-family:arial"><div>At 2013-08-16 22:32:30,"Tobias Grosser" <tobias@grosser.es> wrote:</div><div>>></div><div>>> Yes, I have changed the original code to the form you suggested:</div><div>>> for (i</div><div>>> for (j</div><div>>> ...</div><div>>> x=1</div><div>></div><div>>Sorry, I meant</div><div>> x[0] +=</div><div>></div><div><br></div><div>It is interesting that Polly would run much faster if we change the "x=0" to "X[0]=0" or "X[0]+=0 in the nested loops.</div><div>First, if the nested loop only contains a statement "X[0]+=0", like this:</div><div>// SingleAcc.c</div><div>#include <stdio.h></div><div>#include <stdlib.h></div><div>int main(int argc, !
char *argv[]) {</div><div> int n = ((argc == 2) ? atoi(argv[1]) : 46);</div><div> int a, b, c, d, e, f, x=0;</div><div> int X[10];</div><div> for (a=0; a<n; a++)</div><div> for (b=0; b<n; b++)</div><div> for (c=0; c<n; c++)</div><div> for (d=0; d<n; d++)</div><div> for (e=0; e<n; e++)</div><div> for (f=0; f<n; f++)</div><div> X[0]+=1; // could be X[0]+=1, X[0]=1 or x=1</div><div> printf("%d\n", X[0]); // could be X[0] or x</div><div> return 0;</div><div>}</div><div>Then the scops results would be:</div><div><br></div><div>$ clang -O0 -emit-llvm -S SingleAcc.c -o SingleAcc.ll</div><div># Run everything up to the offending pass</div><div>$ polly-opt SingleAcc.ll -targetlibinfo -no-aa ... -polly-indvars -o SingleAcc.preopt.ll -S</div><div!
># Print the scop info:</div><div>$ polly-opt -basicaa -polly-prepare
-polly-scops SingleAcc.preopt.ll -analyze </div><div>(*Note: you can download SingleAcc.preopt.ll on http://llvm.org/bugs/attachment.cgi?id=11059)</div><div><br></div><div>Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'for.cond2.preheader => for.end32' in function 'main':</div><div> Context:</div><div> [cond.reload] -> { : cond.reload >= -2147483648 and cond.reload <= 2147483647 }</div><div> p0: %cond.reload</div><div> Statements {</div><div> <span class="Apple-tab-span" style="white-space:pre"> </span>Stmt_for_body16</div><div> Domain :=</div><div> [cond.reload] -> { Stmt_for_body16[i0, i1, i2, i3, i4, i5] : i0 >= 0 and i0 <= -1 + cond.reload and i1 >= 0 and i1 <= -1 + cond.reload and i2 >= 0 and i2 <= -1 + cond.reload and i3 >= 0 and i3!
<= -1 + cond.reload and i4 >= 0 and i4 <= -1 + cond.reload and i5 >= 0 and i5 <= -1 + cond.reload and cond.reload >= 1 };</div><div> Scattering :=</div><div> [cond.reload] -> { Stmt_for_body16[i0, i1, i2, i3, i4, i5] -> scattering[0, i0, 0, i1, 0, i2, 0, i3, 0, i4, 0, i5, 0] };</div><div> ReadAccess := </div><div> [cond.reload] -> { Stmt_for_body16[i0, i1, i2, i3, i4, i5] -> MemRef_X[0] };</div><div> MustWriteAccess := </div><div> [cond.reload] -> { Stmt_for_body16[i0, i1, i2, i3, i4, i5] -> MemRef_X[0] };</div><div> }</div><div><br></div><div>Similarly, the scops result for "X[0]=0" would be:</div><div><br></div><div>$ polly-opt -b!
asicaa -polly-prepare -polly-scops SingleAssign.preopt.ll -analyze&nbs
p;</div><div>(*Note: you can download SingleAssign.preopt.ll on http://llvm.org/bugs/attachment.cgi?id=11060)</div><div><br></div><div>Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'for.cond2.preheader => for.end32' in function 'main':</div><div> Context:</div><div> [cond.reload] -> { : cond.reload >= -2147483648 and cond.reload <= 2147483647 }</div><div> p0: %cond.reload</div><div> Statements {</div><div> <span class="Apple-tab-span" style="white-space:pre"> </span>Stmt_for_body16</div><div> Domain :=</div><div> [cond.reload] -> { Stmt_for_body16[i0, i1, i2, i3, i4, i5] : i0 >= 0 and i0 <= -1 + cond.reload and i1 >= 0 and i1 <= -1 + cond.reload and i2 >= 0 and i2 <= -1 + cond.reload and i3 >= 0 and i3 <= -1 + cond.reload and i4 >= 0 and!
i4 <= -1 + cond.reload and i5 >= 0 and i5 <= -1 + cond.reload and cond.reload >= 1 };</div><div> Scattering :=</div><div> [cond.reload] -> { Stmt_for_body16[i0, i1, i2, i3, i4, i5] -> scattering[0, i0, 0, i1, 0, i2, 0, i3, 0, i4, 0, i5, 0] };</div><div> MustWriteAccess := </div><div> [cond.reload] -> { Stmt_for_body16[i0, i1, i2, i3, i4, i5] -> MemRef_X[0] };</div><div> }</div><div><br></div><div>Unfortunately, the scops for "x=1" is much more complicated as follows:</div><div><br></div><div>$ polly-opt -basicaa -polly-prepare -polly-scops nestedloop.preopt.ll -analyze </div><div>(*Note: you can download nestedloop.preopt.ll on http://llvm.org/bugs/attachment.cgi?id=11045)</div><div><br></div><div>Printing analysis 'Polly - Create polyhed!
ral description of Scops' for region: 'for.cond2.preheader => for.e
nd31' in function 'main':</div><div> Context:</div><div> [cond.reload] -> { : cond.reload >= -2147483648 and cond.reload <= 2147483647 }</div><div> p0: %cond.reload</div><div> Statements {</div><div> <span class="Apple-tab-span" style="white-space:pre"> </span>Stmt_for_cond2_preheader</div><div> Domain :=</div><div> [cond.reload] -> { Stmt_for_cond2_preheader[i0] : i0 >= 0 and i0 <= -1 + cond.reload };</div><div> Scattering :=</div><div> [cond.reload] -> { Stmt_for_cond2_preheader[i0] -> scattering[0, i0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] };</div><div> ReadAccess := </div><div> [cond.reload] -&g!
t; { Stmt_for_cond2_preheader[i0] -> MemRef_x_018_reg2mem[0] };</div><div> MustWriteAccess := </div><div> [cond.reload] -> { Stmt_for_cond2_preheader[i0] -> MemRef_x_018_reload_s2a[0] };</div><div> MustWriteAccess := </div><div> [cond.reload] -> { Stmt_for_cond2_preheader[i0] -> MemRef_x_1_lcssa_reg2mem[0] };</div><div> <span class="Apple-tab-span" style="white-space:pre"> </span>Stmt_for_cond5_preheader_lr_ph</div><div> Domain :=</div><div> [cond.reload] -> { Stmt_for_cond5_preheader_lr_ph[i0] : i0 >= 0 and i0 <= -1 + cond.reload and cond.reload >= 1 };</div><div> Scattering :=</div><div> !
[cond.reload] -> { Stmt_
for_cond5_preheader_lr_ph[i0] -> scattering[0, i0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] };</div><div> ReadAccess := </div><div> [cond.reload] -> { Stmt_for_cond5_preheader_lr_ph[i0] -> MemRef_x_018_reload_s2a[0] };</div><div> MustWriteAccess := </div><div> [cond.reload] -> { Stmt_for_cond5_preheader_lr_ph[i0] -> MemRef_x_114_reg2mem[0] };</div><div> <span class="Apple-tab-span" style="white-space:pre"> </span>Stmt_for_cond5_preheader</div><div> Domain :=</div><div> [cond.reload] -> { Stmt_for_cond5_preheader[i0, i1] : i0 >= 0 and i0 <= -1 + cond.reload and i1 >= 0 and i1 <= -1 + cond.reload and cond.reload >= 1 };</div><div> &nb!
sp; Scattering :=</div><div> [cond.reload] -> { Stmt_for_cond5_preheader[i0, i1] -> scattering[0, i0, 2, i1, 0, 0, 0, 0, 0, 0, 0, 0, 0] };</div><div> ReadAccess := </div><div> [cond.reload] -> { Stmt_for_cond5_preheader[i0, i1] -> MemRef_x_114_reg2mem[0] };</div><div> MustWriteAccess := </div><div> [cond.reload] -> { Stmt_for_cond5_preheader[i0, i1] -> MemRef_x_114_reload_s2a[0] };</div><div> MustWriteAccess := </div><div> [cond.reload] -> { Stmt_for_cond5_preheader[i0, i1] -> MemRef_x_2_lcssa_reg2mem[0] };</div><div> [...]</div><div> <spa!
n class="Apple-tab-span" style="white-space:pre"> </span>Stmt_for_inc2
9</div><div> Domain :=</div><div> [cond.reload] -> { Stmt_for_inc29[i0] : i0 >= 0 and i0 <= -1 + cond.reload };</div><div> Scattering :=</div><div> [cond.reload] -> { Stmt_for_inc29[i0] -> scattering[0, i0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] };</div><div> ReadAccess := </div><div> [cond.reload] -> { Stmt_for_inc29[i0] -> MemRef_x_1_lcssa_reg2mem[0] };</div><div> MustWriteAccess := </div><div> [cond.reload] -> { Stmt_for_inc29[i0] -> MemRef_x_1_lcssa_lcssa_reg2mem[0] };</div><div> MustWriteAccess := </div><div> &n!
bsp; [cond.reload] -> { Stmt_for_inc29[i0] -> MemRef_x_018_reg2mem[0] };</div><div> <span class="Apple-tab-span" style="white-space:pre"> </span>Stmt_for_cond_for_end31_crit_edge</div><div> Domain :=</div><div> [cond.reload] -> { Stmt_for_cond_for_end31_crit_edge[] };</div><div> Scattering :=</div><div> [cond.reload] -> { Stmt_for_cond_for_end31_crit_edge[] -> scattering[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] };</div><div> ReadAccess := </div><div> [cond.reload] -> { Stmt_for_cond_for_end31_crit_edge[] -> MemRef_x_1_lcssa_lcssa_reg2mem[0] };</div><div> MustWriteAccess :=&!
nbsp;</div><div>  
; [cond.reload] -> { Stmt_for_cond_for_end31_crit_edge[] -> MemRef_x_0_lcssa_reg2mem[0] };</div><div> }</div><div><br></div><div>The compile time of polly-dependence analysis for the three cases would be:</div><div>loop with "X[0]+=1":<span class="Apple-tab-span" style="white-space:pre"> </span>0.130s</div><div>loop with "X[0] =1":<span class="Apple-tab-span" style="white-space:pre"> </span> 0.053s</div><div>loop with "x=1":<span class="Apple-tab-span" style="white-space:pre"> </span>1.037s</div><div><br></div><div>>> There is no data dependence at all. However, it seems that -polly-prepare still introduces a lot of allocs and store instructions.</div><div>>></div><div>>>> Meaning one alloc instruction and a single load and store in the</div><div>>>> innermost loop, without any non-induction variable PHI nodes.</div><div>>>></div><div>>>> When implementing this in C, LLVM may introduce again PHI nodes. !
So it</div><div>>>> may possibly be necessary to write this directly in LLVM-IR.</div><div>></div><div>>This is the important one. I wonder what the performance of the </div><div>>dependence analysis is for increasing loop depth, if we have only a </div><div>>single statement, that just reads and writes from the very same memory </div><div>>location, but that does not have all the mess from the </div><div>>non-induction-variable PHI nodes.</div><div><br></div><div>If we change the "x=1" to "X[0]+=1", then there would be only one "store" instruction and one "load" instructions in the loop no matter how much the depth of the loop nest. In such a case, the compile time would increase exponentially as the depth of the loop nest increases:</div><div><br></div><div>nest-2: 0.063s</div><div>nest-4: 0.110s</div><div>nest-6: 0.221s</div><div>nest-8: 0.465s</div><div>nest-10: 0.893s</div><div>nest-12: 1.710s</div><div><br></div><div>Chee!
rs,</div><div>Star Tan</div></div>