[LLVMdev] Question on Loop Normalization in LLVM

[Michael Zolotukhin]

Hi Karthik,

This is what SCEV (ScalarEvolution) does in LLVM, though it doesn’t have to be directly reflected in the IR.

SCEV analyzes the program and for all expressions in a loop tries to compute a descriptor of its behavior (called SCEV-expression). E.g for you first loop for induction variable it will compute a SCEV expression: <7,+,1>, which means an induction variable with start value 7 and positive stride 1. These expressions could be nested, i.e. start value could be an induction variable of outer loop, for instance. With this info, one don’t need to rewrite the loop IR unless it’s profitable for some other reason (e.g. Loop Strength Reduction, LSR, can do that to make code faster).

Best regards,
Michael

> On Jan 30, 2015, at 5:28 AM, KARTHIK VENKATESH BHAT <kv.bhat at samsung.com> wrote:
> 
> Hi All,
> I was going through http://en.wikipedia.org/wiki/Normalized_loop and some other documents on Normalized Loops. 
> LLVM currently doesn't seem to normalize the loop as mentioned in the link (i.e. to start with 0 and have a unit step).
> I wrote a pass to convert a loop into normalized form as in the link  (i.e. to have start value of 0 and step of 1 whenever possible) but I'm not sure if this will be beneficial or end up making the code slower. 
> This is because we are introducing an additional instruction inside the loop(e.g. an add to adjust the memory access after the normalization in the example below) to achieve this kind of normalization.
> For e.g. 
> for ( i = 7; i < MAX; i++)
>  a[I] = b[I]+c[I];
> is transformed into -
> for ( i = 0; i < MAX -7; i++)
>  a[I+7] = b[I+7]+c[I+7];
> 
> as we can see in this case we have introduced an additional instruction (i.e. add) in the loop to get I+7 and another instruction in preheader for modified exit condition (i.e. sub to get MAX-7). 
> So my question is "Is this kind of normalization helpful in llvm?"
> 
> One advantage I can think of is that it can make transforms such as loop fusion easier as we would have a common start and step.
> Is there any other advantage of having this kind of normalized loops?
> 
> Thanks and Regards
> Karthik Bhat
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev