[LLVMdev] Unrolling loops into constant-time expressions

[Duncan Sands]

Hi Juliusz,

> I've come across another example:

this looks like a different issue to the previous example.
If you run the output of clang a second time through the
optimizers it gets simplified.

Ciao,

Duncan.

>
> I'm compiling with
> clang -S -emit-llvm -std=gnu99 -O3
> clang version 2.9 (trunk 118238)
> Target: x86_64-unknown-linux-gnu
> Thread model: posix
>
> I take the code:
> int loops(int x) {
>        int ret = 0;
>        for(int i = 0; i<  x; i++) {
>            for(int j = 0; j<  x; j++) {
>                ret += 1;
>            }
>        }
>        return ret;
> }
>
> and the generated code is:
> define i32 @loops(i32 %x) nounwind readnone {
> ;<label>:0
>      %1 = icmp sgt i32 %x, 0
>      br i1 %1, label %2, label %._crit_edge6
>
> ;<label>:2                                       ; preds = %0, %2
>      %i.03.us = phi i32 [ %3, %2 ], [ 0, %0 ]
>      %ret.14.us = phi i32 [ %tmp, %2 ], [ 0, %0 ]
>      %tmp = add i32 %ret.14.us, %x
>      %3 = add nsw i32 %i.03.us, 1
>      %exitcond = icmp eq i32 %3, %x
>      br i1 %exitcond, label %._crit_edge6, label %2
>
> ._crit_edge6:                                     ; preds = %2, %0
>      %ret.1.lcssa = phi i32 [ 0, %0 ], [ %tmp, %2 ]
>      ret i32 %ret.1.lcssa
> }
>
> This code:
> * unrolls the inner loop simplifying the code to sth like:
>      for(int i = 0; i<  x; i++) {
>          ret += x;
> * But it is unable to also unroll the outer loop, even though it is a
> simple expression.
>
> On the other hand it is able to unroll a complicated expression inside
> one loop into a constant-time expression, like here:
> int loop(int x) {
>        int ret = 0;
>        for(int i = 0; i<  x; i++) {
>            ret += 1+i*i + i*(i+2);
>        }
>        return ret;
> }
> generates:
> define i32 @loop(i32 %x) nounwind readnone {
>      %1 = icmp sgt i32 %x, 0
>      br i1 %1, label %bb.nph, label %3
>
> bb.nph:                                           ; preds = %0
>      %tmp4 = add i32 %x, -1
>      %tmp6 = add i32 %x, -2
>      %tmp16 = add i32 %x, -3
>      %tmp7 = zext i32 %tmp6 to i33
>      %tmp5 = zext i32 %tmp4 to i33
>      %tmp17 = zext i32 %tmp16 to i33
>      %tmp15 = mul i33 %tmp5, %tmp7
>      %tmp18 = mul i33 %tmp15, %tmp17
>      %tmp8 = mul i32 %tmp4, %tmp6
>      %tmp19 = lshr i33 %tmp18, 1
>      %2 = shl i32 %tmp8, 2
>      %tmp20 = trunc i33 %tmp19 to i32
>      %tmp12 = mul i32 %x, 5
>      %tmp1125 = and i32 %2, -8
>      %tmp21 = mul i32 %tmp20, 1431655764
>      %tmp13 = add i32 %tmp1125, %tmp12
>      %tmp14 = add i32 %tmp13, -4
>      %tmp22 = sub i32 %tmp14, %tmp21
>      ret i32 %tmp22
>
> ;<label>:3                                       ; preds = %0
>      ret i32 0
> }
> which has no loop, which means that clang -O3 is capable of:
> * unrolling expressions like
>        for(int i = 0; i<  n; i++)
>            ret += i (or i*i, or i*i*i... i checked up to i6 AFAIR)
>      into a constant-time formula
> * unrolling such polynomial-like expressions into a constant time
> formula, and discarding the loop at all.
>
> Even though it can perform such complicated tricks on one loop, it never
> unrolls two nested loop into a constant even in a simple case.
>
> Is there a way to make it do so?
>
> Cheers,
> Juliusz Sompolski
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev