llvm dev - Nov 2017 - Nowaday Scalar Evolution's Problem.

The Problem?

Nowaday, SCEV called "Scalar Evolution" does only evolate instructions
that
has predictable operand,
Constant-Based operand. such as that can evolute as a constant.
otherwise we couldn't evolate it as SCEV node, evolated as SCEVUnknown.
important thing that we remember is, we do not use SCEV only for Loop
Deletion,
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.
but, LLVM uses SCEV for otherall loop-analysis, typically Loop Unroll, etc.
That really does need to anaylze conditional-expressions, lets see
following C/C++ code.

void UnpredictableBackedgeTakenCountFunc1() {

    for(unsigned int i = 0; i != 10; ++i) {
        // Exception of variable i...
        if(i == 4) ++i; // when the variable i is 4, we increase it. so its
5.
        if(i == 7) ++i; // when the variable i is 7, we increase it. so its
8.

        // do something here....
    }
}

Is this loop-count for this code predictable?
yes, it does. its "actually" predictable, also unrollable.
lets see following IR and Assembly that clang(lastest version, 2017-11-17)
emitted.

**IR OUTPUT with (clang.exe -ggdb0 -O3 -S -emit-llvm)**
define void @UnpredictableBackedgeTakenCountFunc1() {
  br label %1                           ; goto %1

  %2 = phi i32 [ 0, %0 ], [ %10, %5 ]   ; if(%2 from %0) %2 = 0
                                        ; if(%2 from %5) %2 = %10
                                        ;
  switch i32 %2, label %5 [             ; switch(%2) default: goto %5
  i32 10, label %3                      ; case 10: goto %3
  i32 4, label %4                       ; case 4 : goto %4
  ]

  ret void                              ; return;

  br label %5                           ; goto %5;

  %6 = phi i32 [ 5, %4 ], [ %2, %1 ]
  %7 = icmp eq i32 %6, 7                ; %7  = (%6 == 7)
  %8 = zext i1 %7 to i32                ; %8  = (i1)%7
  %9 = add i32 %6, 1                    ; %9  = %6 + 1
  %10 = add i32 %9, %8                  ; %10 = %9 + %8
  br label %1                           ; goto %1;
}

**ASSEMBLY OUTPUT (clang.exe -ggdb0 -O3 -S)**
UnpredictableBackedgeTakenCountFunc1():
  xor eax, eax                          ; eax = 0
  cmp eax, 4                            ; cmpv = (eax == 4)
  jne .LBB0_2                           ;   if(cmpv == false) goto LBB0_2
  jmp .LBB0_4                           ;   goto LBB0_4
.LBB0_5:
  xor ecx, ecx                          ; ecx = 0
  cmp eax, 7                            ; cmpv = (ecx == 7)
  sete cl                               ;   cl = cmpv
  lea eax, [rax + rcx]                  ; eax = *(rax + rcx)
  add eax, 1                            ; eax++
  cmp eax, 4                            ; cmpv = (ecx == 4)
  je .LBB0_4                            ;   if(cmpv == true) goto LBB0_4
.LBB0_2:
  cmp eax, 10                           ; cmpv = (eax == 10)
  jne .LBB0_5                           ;   if(cmpv == false) goto LBB0_5
  jmp .LBB0_3                           ;   goto LBB0_3
.LBB0_4:
  mov eax, 5                            ; eax = 5
  jmp .LBB0_5                           ; goto LBB0_5
.LBB0_3:
  ret                                   ; return;
.Lfunc_end0:

The loop doesn't even deleted! whats happening to SCEV!
Yes, reason why SCEV cannot delete this loop because SCEV doesn't handle
conditional-variables dynamically when calculating backedge-taken count.
So now, this is why I am suggesting that SCEV to handle
conditional-variables.


Solve Problem?

First, before we solve the problem, we need to remember that SCEV should
NOT include cyclic SCEV node.
this is really important, if we create cyclic SCEV node, it will be
resolved as SCEVUnknown. will not optimized.

Okay. now, lets try to optimized the code that I wrote on top.

void UnpredictableBackedgeTakenCountFunc1() {

    for(unsigned int i = 0; i != 10; ++i) {
        // Exception of variable i...
        if(i == 4) ++i; // when the variable i is 4, we increase it. so its
5.
        if(i == 7) ++i; // when the variable i is 7, we increase it. so its
8.

        // do something here....
    }
}

lets try to evolute "i" as add-recurrence
    %0 ->   label %0;
    %1 ->   0
    %1 ->   if(%1 == 10)
                goto %6;
            else
                %i = %2;

        %2 ->   %2 = (%1 == 4) + %3;
        %3 ->   %3 = (%1 == 7) + %4;
        %4 ->   %4 = 1;
    %5 ->   goto %1;
    %6 ->   label %6;

This is a current add-recurrence SCEV node emmited from SCEV.
for now, %2 and %3 cannot be evoluted.

we cannot calculate the backedge-taken count for this node.
the SCEVAddRec node can only handle a constant variable. so it will be
like..

SCEV:
    What is Loop-Latch? : %1
        Is The Loop-Latch is only one? : Yes
        Is the Loop-Latch is conditional? : Yes
        Is The Loop-Latch has Exit? : Yes
        What is Loop-Latch's Exit? : %5
    What is %1 value? : %2
        What is %2 value? : (%1 == 4) + %3
            What is first operand value? :
                Unknown! We don't know it can be 4! We cannot add it! it
can be 0 or 1!
                Stop analyzing! return SCEVUnknown.
            (%1 == 4) = SCEVUnknown(%1 == 4)
        %2 = SCEVUnknown(%1 == 4) + %3
    %1 = SCEVUnknown(%2)

    Done Node Analyzing.

SCEV backedge-taken count analyzing:
    Initialize :
        %1 = 0;
        Is Latch condition true? : false.
    Count 1 :
        %1 is Unknown! We cannot calculate backedge-taken count!.

    Its Unpredictable!.

Loop Deletion:
    Is loop changes other loop outside variables? : false.
    Is loop volatile? : false
    Is loop backedge can taken(loop count predictable) : false

    Loop Optimized : false.

Printing analysis 'Scalar Evolution Analysis' for function
'UnpredictableBackedgeTakenCountFunc1':
Classifying expressions for: @UnpredictableBackedgeTakenCountFunc1
  %2 = phi i32 [ 0, %0 ], [ %10, %5 ]
  -->  %2 U: full-set S: full-set               Exits:
<<Unknown>>
    LoopDispositions: { %1: Variant }
  %6 = phi i32 [ 5, %4 ], [ %2, %1 ]
  -->  %6 U: full-set S: full-set               Exits:
<<Unknown>>
    LoopDispositions: { %1: Variant }
  %8 = zext i1 %7 to i32
  -->  (zext i1 %7 to i32) U: [0,2) S: [0,2)            Exits:
<<Unknown>>
            LoopDispositions: { %1: Variant }
  %9 = add i32 %6, 1
  -->  (1 + %6) U: full-set S: full-set         Exits:
<<Unknown>>
    LoopDispositions: { %1: Variant }
  %10 = add i32 %9, %8
  -->  (1 + (zext i1 %7 to i32) + %6) U: full-set S: full-set
 Exits: <<Unknown>>          LoopDispositions: { %1: Variant }
Determining loop execution counts for: @UnpredictableBackedgeTakenCountFunc1
Loop %1: Unpredictable backedge-taken count.
Loop %1: Unpredictable max backedge-taken count.
Loop %1: Unpredictable predicated backedge-taken count.

This is actual optimization dump with opt executable. (opt.exe -S
-scalar-evolution -analyze)

Why? because it only creates a node, %1 doesn't modified yet!
The (%1 == 4) can be 1 or 0. depend on %1 we cannot assume it as constant
variable. its variant!

Now what happens on new one that I suggesting.
Instruction to SCEV node analyzing:
    What is Loop-Latch? : %1
        Is The Loop-Latch is only one? : Yes
        Is the Loop-Latch is conditional? : Yes
        Is The Loop-Latch has Exit? : Yes
        What is Loop-Latch's Exit? : %5
    What is %1 value? : %2
        What is %2 value? : (%1 == 4) + %3
            What is first operand value? :
                Its conditional! do not analyze yet!
                Keep analyze it! we are going to calculate later when
calculating backedge-taken count!
            (%1 == 4) = SCEVConditional(%1 == 4)
            What is second operand value? : %3
                What is %3 value? : (%1 == 7) + %4
                    What is first opernad value? :
                        Its conditional! do not analyze yet!
                        Keep analyze it! we are going to calculate later
when calculating backedge-taken count!
                    (%1 == 7) = SCEVConditional(%1 == 7)
                    What is second operand value? : %4
                        What is %4 value? : Constant 1
                    %4 = SCEVConstant(1)
                %3 = SCEVConditional(%1 == 7) + SCEVConstant(1)
            %3 = SCEVAddRecExpr[%1, +, SCEVConditional(%1 == 7) +,
SCEVConstant(1))]
        %2 = SCEVAddRecExpr[%1, +, SCEVConditional(%1 == 4), +, %3)]
    %1 = %2

    What is Latch conditional(%5) value? : %1
    Done Node Analyzing!

SCEV backedge-taken count analyzing:
    Initialize :
        %1 = 0;
        Is Latch condition true? : false.

    Count 1 :
        %1 = %2;
            %2 = (%1(0) == 4) + %3
            %2 = (%1(0) == 4) + %3
                %3 = (%1(0) == 7) + %4
                %3 = (%1(0) == 7) + %4
                    %4 = 1
                %3 = (%1(0) == 7) + %4(1)
                %3 = 1
            %2 = (%1(0) == 4) + %3(1)
            %2 = 1
        %1 += %2(1)
        %1 = 1

        Current %1 value : 1
        Is Latch condition true? : false.

    Count 2 :
        %1 = %2;
            %2 = (%1(1) == 4) + %3
            %2 = (%1(1) == 4) + %3
                %3 = (%1(1) == 7) + %4
                %3 = (%1(1) == 7) + %4
                    %4 = 1
                %3 = (%1(1) == 7) + %4(1)
                %3 = 1
            %2 = (%1(1) == 4) + %3(1)
            %2 = 1
        %1 += %2(1)
        %1 = 2

        Current %1 value : 2
        Is Latch condition true? : false.

    Count ... :
    ...


    Backedge-Taken Count : 7
    Its predictable!

Loop Deletion:
    Is loop changes other outside variables? : false.
    Is loop volatile? : false
    Is loop backedge can taken(loop count predictable) : true

    Removing Loop!
    Loop Optimized : true.

Okay, now we got a optimized loop!
The way that I resolving this is, visiting conditional-expressions each
step when calculating backedge-taken count.
not only focus on SCEV node predicates, we can still assume it the loop can
predictable.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20171120/942dd411/attachment.html>

I am currently working on this.
that I wanted to ask is, is there are any wrong things for SCEV's concept?

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

We have ScalarEvolution::computeExitCountExhaustively, which sort of 
does what you're proposing (if you insert some code before the if 
statement to prevent SimplifyCFG from forming the switch, SCEV uses it 
to compute the trip count of your loop).  Improvements there welcome, 
but we should also consider changing SimplifyCFG to generate better IR; 
forming a switch here isn't really useful.

-Eli

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

-- 
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux
Foundation Collaborative Project

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20171120/519fcf5f/attachment-0001.html>