[LLVMdev] Unrolling loops into constant-time expressions

[Juliusz Sompolski]

Hello,

I've come across another example:

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