<div dir="ltr"><div>I am currently working on this. </div><div>that I wanted to ask is, is there are any wrong things for SCEV's concept?</div></div><div class="gmail_extra"><br><div class="gmail_quote">2017-11-20 13:57 GMT+09:00 Jun Ryung Ju <span dir="ltr"><<a href="mailto:junryoungju@gmail.com" target="_blank">junryoungju@gmail.com</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>The Problem?</div><div><br></div><div>Nowaday, SCEV called "Scalar Evolution" does only evolate instructions that has predictable operand,</div><div>Constant-Based operand. such as that can evolute as a constant. </div><div>otherwise we couldn't evolate it as SCEV node, evolated as SCEVUnknown.</div><div>important thing that we remember is, we do not use SCEV only for Loop Deletion,</div><div>which that doesn't really needed on nature loops (usually programmers do not write non-nature loops), it doesn't really need to evolute some conditional-variables.</div><div>but, LLVM uses SCEV for otherall loop-analysis, typically Loop Unroll, etc.</div><div>That really does need to anaylze conditional-expressions, lets see following C/C++ code.</div><div><br></div><div>void UnpredictableBackedgeTakenCoun<wbr>tFunc1() {</div><div><br></div><div> for(unsigned int i = 0; i != 10; ++i) {</div><div> // Exception of variable i...</div><div> if(i == 4) ++i; // when the variable i is 4, we increase it. so its 5.</div><div> if(i == 7) ++i; // when the variable i is 7, we increase it. so its 8.</div><div><br></div><div> // do something here....</div><div> }</div><div>}</div><div><br></div><div>Is this loop-count for this code predictable? </div><div>yes, it does. its "actually" predictable, also unrollable.</div><div>lets see following IR and Assembly that clang(lastest version, 2017-11-17) emitted.</div><div><br></div><div>**IR OUTPUT with (clang.exe -ggdb0 -O3 -S -emit-llvm)**</div><div>define void @<wbr>UnpredictableBackedgeTakenCoun<wbr>tFunc1() { </div><div> br label %1 ; goto %1</div><div><br></div><div> %2 = phi i32 [ 0, %0 ], [ %10, %5 ] ; if(%2 from %0) %2 = 0</div><div> ; if(%2 from %5) %2 = %10 </div><div> ;</div><div> switch i32 %2, label %5 [ ; switch(%2) default: goto %5</div><div> i32 10, label %3 ; case 10: goto %3</div><div> i32 4, label %4 ; case 4 : goto %4</div><div> ]</div><div><br></div><div> ret void ; return;</div><div><br></div><div> br label %5 ; goto %5;</div><div><br></div><div> %6 = phi i32 [ 5, %4 ], [ %2, %1 ] </div><div> %7 = icmp eq i32 %6, 7 ; %7 = (%6 == 7)</div><div> %8 = zext i1 %7 to i32 ; %8 = (i1)%7</div><div> %9 = add i32 %6, 1 ; %9 = %6 + 1</div><div> %10 = add i32 %9, %8 ; %10 = %9 + %8</div><div> br label %1 ; goto %1;</div><div>}</div><div><br></div><div>**ASSEMBLY OUTPUT (clang.exe -ggdb0 -O3 -S)**</div><div>UnpredictableBackedgeTakenCoun<wbr>tFunc1():</div><div> xor eax, eax ; eax = 0</div><div> cmp eax, 4 ; cmpv = (eax == 4)</div><div> jne .LBB0_2 ; if(cmpv == false) goto LBB0_2</div><div> jmp .LBB0_4 ; goto LBB0_4</div><div>.LBB0_5:</div><div> xor ecx, ecx ; ecx = 0</div><div> cmp eax, 7 ; cmpv = (ecx == 7)</div><div> sete cl ; cl = cmpv</div><div> lea eax, [rax + rcx] ; eax = *(rax + rcx)</div><div> add eax, 1 ; eax++</div><div> cmp eax, 4 ; cmpv = (ecx == 4)</div><div> je .LBB0_4 ; if(cmpv == true) goto LBB0_4</div><div>.LBB0_2:</div><div> cmp eax, 10 ; cmpv = (eax == 10)</div><div> jne .LBB0_5 ; if(cmpv == false) goto LBB0_5</div><div> jmp .LBB0_3 ; goto LBB0_3</div><div>.LBB0_4:</div><div> mov eax, 5 ; eax = 5</div><div> jmp .LBB0_5 ; goto LBB0_5</div><div>.LBB0_3:</div><div> ret ; return;</div><div>.Lfunc_end0:</div><div><br></div><div>The loop doesn't even deleted! whats happening to SCEV!</div><div>Yes, reason why SCEV cannot delete this loop because SCEV doesn't handle conditional-variables dynamically when calculating backedge-taken count.</div><div>So now, this is why I am suggesting that SCEV to handle conditional-variables.</div><div><br></div><div><br></div><div>Solve Problem?</div><div><br></div><div>First, before we solve the problem, we need to remember that SCEV should NOT include cyclic SCEV node.</div><div>this is really important, if we create cyclic SCEV node, it will be resolved as SCEVUnknown. will not optimized.</div><div><br></div><div>Okay. now, lets try to optimized the code that I wrote on top.</div><div><br></div><div>void UnpredictableBackedgeTakenCoun<wbr>tFunc1() {</div><div><br></div><div> for(unsigned int i = 0; i != 10; ++i) {</div><div> // Exception of variable i...</div><div> if(i == 4) ++i; // when the variable i is 4, we increase it. so its 5.</div><div> if(i == 7) ++i; // when the variable i is 7, we increase it. so its 8.</div><div><br></div><div> // do something here....</div><div> }</div><div>}</div><div><br></div><div>lets try to evolute "i" as add-recurrence</div><div> %0 -> label %0;</div><div> %1 -> 0</div><div> %1 -> if(%1 == 10) </div><div> goto %6;</div><div> else </div><div> %i = %2;</div><div><br></div><div> %2 -> %2 = (%1 == 4) + %3;</div><div> %3 -> %3 = (%1 == 7) + %4;</div><div> %4 -> %4 = 1;</div><div> %5 -> goto %1;</div><div> %6 -> label %6;</div><div><br></div><div>This is a current add-recurrence SCEV node emmited from SCEV.</div><div>for now, %2 and %3 cannot be evoluted.</div><div><br></div><div>we cannot calculate the backedge-taken count for this node.</div><div>the SCEVAddRec node can only handle a constant variable. so it will be like..</div><div><br></div><div>SCEV:</div><div> What is Loop-Latch? : %1</div><div> Is The Loop-Latch is only one? : Yes</div><div> Is the Loop-Latch is conditional? : Yes</div><div> Is The Loop-Latch has Exit? : Yes</div><div> What is Loop-Latch's Exit? : %5</div><div> What is %1 value? : %2</div><div> What is %2 value? : (%1 == 4) + %3</div><div> What is first operand value? : </div><div> Unknown! We don't know it can be 4! We cannot add it! it can be 0 or 1! </div><div> Stop analyzing! return SCEVUnknown.</div><div> (%1 == 4) = SCEVUnknown(%1 == 4)</div><div> %2 = SCEVUnknown(%1 == 4) + %3</div><div> %1 = SCEVUnknown(%2)</div><div><br></div><div> Done Node Analyzing.</div><div><br></div><div>SCEV backedge-taken count analyzing:</div><div> Initialize : </div><div> %1 = 0;</div><div> Is Latch condition true? : false.</div><div> Count 1 :</div><div> %1 is Unknown! We cannot calculate backedge-taken count!.</div><div><br></div><div> Its Unpredictable!.</div><div><br></div><div>Loop Deletion:</div><div> Is loop changes other loop outside variables? : false.</div><div> Is loop volatile? : false</div><div> Is loop backedge can taken(loop count predictable) : false</div><div><br></div><div> Loop Optimized : false.</div><div><br></div><div>Printing analysis 'Scalar Evolution Analysis' for function '<wbr>UnpredictableBackedgeTakenCoun<wbr>tFunc1':</div><div>Classifying expressions for: @<wbr>UnpredictableBackedgeTakenCoun<wbr>tFunc1</div><div> %2 = phi i32 [ 0, %0 ], [ %10, %5 ]</div><div> --> %2 U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %1: Variant }</div><div> %6 = phi i32 [ 5, %4 ], [ %2, %1 ]</div><div> --> %6 U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %1: Variant }</div><div> %8 = zext i1 %7 to i32</div><div> --> (zext i1 %7 to i32) U: [0,2) S: [0,2) Exits: <<Unknown>> LoopDispositions: { %1: Variant }</div><div> %9 = add i32 %6, 1</div><div> --> (1 + %6) U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %1: Variant }</div><div> %10 = add i32 %9, %8</div><div> --> (1 + (zext i1 %7 to i32) + %6) U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %1: Variant }</div><div>Determining loop execution counts for: @<wbr>UnpredictableBackedgeTakenCoun<wbr>tFunc1</div><div>Loop %1: Unpredictable backedge-taken count.</div><div>Loop %1: Unpredictable max backedge-taken count.</div><div>Loop %1: Unpredictable predicated backedge-taken count.</div><div><br></div><div>This is actual optimization dump with opt executable. (opt.exe -S -scalar-evolution -analyze)</div><div><br></div><div>Why? because it only creates a node, %1 doesn't modified yet!</div><div>The (%1 == 4) can be 1 or 0. depend on %1 we cannot assume it as constant variable. its variant!</div><div><br></div><div>Now what happens on new one that I suggesting.</div><div>Instruction to SCEV node analyzing:</div><div> What is Loop-Latch? : %1</div><div> Is The Loop-Latch is only one? : Yes</div><div> Is the Loop-Latch is conditional? : Yes</div><div> Is The Loop-Latch has Exit? : Yes</div><div> What is Loop-Latch's Exit? : %5</div><div> What is %1 value? : %2</div><div> What is %2 value? : (%1 == 4) + %3</div><div> What is first operand value? : </div><div> Its conditional! do not analyze yet!</div><div> Keep analyze it! we are going to calculate later when calculating backedge-taken count!</div><div> (%1 == 4) = SCEVConditional(%1 == 4)</div><div> What is second operand value? : %3</div><div> What is %3 value? : (%1 == 7) + %4</div><div> What is first opernad value? : </div><div> Its conditional! do not analyze yet!</div><div> Keep analyze it! we are going to calculate later when calculating backedge-taken count!</div><div> (%1 == 7) = SCEVConditional(%1 == 7)</div><div> What is second operand value? : %4</div><div> What is %4 value? : Constant 1</div><div> %4 = SCEVConstant(1)</div><div> %3 = SCEVConditional(%1 == 7) + SCEVConstant(1)</div><div> %3 = SCEVAddRecExpr[%1, +, SCEVConditional(%1 == 7) +, SCEVConstant(1))]</div><div> %2 = SCEVAddRecExpr[%1, +, SCEVConditional(%1 == 4), +, %3)]</div><div> %1 = %2 </div><div><br></div><div> What is Latch conditional(%5) value? : %1</div><div> Done Node Analyzing!</div><div><br></div><div>SCEV backedge-taken count analyzing:</div><div> Initialize : </div><div> %1 = 0;</div><div> Is Latch condition true? : false.</div><div> </div><div> Count 1 : </div><div> %1 = %2;</div><div> %2 = (%1(0) == 4) + %3</div><div> %2 = (%1(0) == 4) + %3</div><div> %3 = (%1(0) == 7) + %4</div><div> %3 = (%1(0) == 7) + %4</div><div> %4 = 1</div><div> %3 = (%1(0) == 7) + %4(1)</div><div> %3 = 1</div><div> %2 = (%1(0) == 4) + %3(1)</div><div> %2 = 1</div><div> %1 += %2(1)</div><div> %1 = 1</div><div> </div><div> Current %1 value : 1</div><div> Is Latch condition true? : false.</div><div> </div><div> Count 2 : </div><div> %1 = %2;</div><div> %2 = (%1(1) == 4) + %3</div><div> %2 = (%1(1) == 4) + %3</div><div> %3 = (%1(1) == 7) + %4</div><div> %3 = (%1(1) == 7) + %4</div><div> %4 = 1</div><div> %3 = (%1(1) == 7) + %4(1)</div><div> %3 = 1</div><div> %2 = (%1(1) == 4) + %3(1)</div><div> %2 = 1</div><div> %1 += %2(1)</div><div> %1 = 2</div><div> </div><div> Current %1 value : 2</div><div> Is Latch condition true? : false.</div><div><br></div><div> Count ... :</div><div> ...</div><div><br></div><div><br></div><div> Backedge-Taken Count : 7</div><div> Its predictable!</div><div><br></div><div>Loop Deletion:</div><div> Is loop changes other outside variables? : false.</div><div> Is loop volatile? : false</div><div> Is loop backedge can taken(loop count predictable) : true</div><div><br></div><div> Removing Loop!</div><div> Loop Optimized : true.</div><div><br></div><div>Okay, now we got a optimized loop!</div><div>The way that I resolving this is, visiting conditional-expressions each step when calculating backedge-taken count.</div><div>not only focus on SCEV node predicates, we can still assume it the loop can predictable.</div><div><br></div><div><br></div></div>
</blockquote></div><br></div>