<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 UnpredictableBackedgeTakenCountFunc1() {</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 @UnpredictableBackedgeTakenCountFunc1() { </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>UnpredictableBackedgeTakenCountFunc1():</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 UnpredictableBackedgeTakenCountFunc1() {</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 'UnpredictableBackedgeTakenCountFunc1':</div><div>Classifying expressions for: @UnpredictableBackedgeTakenCountFunc1</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: @UnpredictableBackedgeTakenCountFunc1</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>