[llvm-dev] Nowaday Scalar Evolution's Problem.
Jun Ryung Ju via llvm-dev
llvm-dev at lists.llvm.org
Mon Nov 20 17:44:55 PST 2017
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>
More information about the llvm-dev
mailing list