llvm/test/Analysis/ScalarEvolution/tripmultiple_calculation.ll

   1 ; RUN: opt -S -disable-output "-passes=print<scalar-evolution>" < %s 2>&1 2>&1 | FileCheck %s
   2
   3 ; umin is represented using -1 * umax in scalar evolution. -1 is considered as the
   4 ; constant of the multiply expression (-1 * ((-1 + (-1 * %a)) umax (-1 + (-1 * %b)))).
   5 ; Returns the greatest power of 2 divisor by evaluating the minimal trailing zeros
   6 ; for the trip count expression.
   7 ;
   8 ; int foo(uint32_t a, uint32_t b, uint32_t *c) {
   9 ;   for (uint32_t i = 0; i < (uint32_t)(a < b ? a : b) + 1; i++)
  10 ;     c[i] = i;
  11 ;   return 0;
  12 ; }
  13 ;
  14 ; CHECK: Loop %for.body: Trip multiple is 1
  15
  16 define i32 @foo(i32 %a, i32 %b, ptr %c) {
  17 entry:
  18   %cmp = icmp ult i32 %a, %b
  19   %cond = select i1 %cmp, i32 %a, i32 %b
  20   %add = add i32 %cond, 1
  21   %cmp18 = icmp eq i32 %add, 0
  22   br i1 %cmp18, label %for.cond.cleanup, label %for.body.preheader
  23
  24 for.body.preheader:                               ; preds = %entry
  25   br label %for.body
  26
  27 for.cond.cleanup.loopexit:                        ; preds = %for.body
  28   br label %for.cond.cleanup
  29
  30 for.cond.cleanup:                                 ; preds = %for.cond.cleanup.loopexit, %entry
  31   ret i32 0
  32
  33 for.body:                                         ; preds = %for.body.preheader, %for.body
  34   %i.09 = phi i32 [ %inc, %for.body ], [ 0, %for.body.preheader ]
  35   %arrayidx = getelementptr inbounds i32, ptr %c, i32 %i.09
  36   store i32 %i.09, ptr %arrayidx, align 4
  37   %inc = add nuw i32 %i.09, 1
  38   %cmp1 = icmp ult i32 %inc, %add
  39   br i1 %cmp1, label %for.body, label %for.cond.cleanup.loopexit
  40 }
  41
  42 ; Overflow may happen for the multiply expression n * 3, verify that trip
  43 ; multiple is set to 1 if NUW/NSW are not set.
  44 ;
  45 ; __attribute__((noinline)) void a(unsigned n) {
  46 ;   #pragma unroll(3)
  47 ;   for (unsigned i = 0; i != n * 3; ++i)
  48 ;     printf("TEST%u\n", i);
  49 ; }
  50 ; int main() { a(2863311531U); }
  51 ;
  52 ; CHECK: Loop %for.body: Trip multiple is 1
  53
  54 @.str2 = private unnamed_addr constant [8 x i8] c"TEST%u\0A\00", align 1
  55
  56 define void @foo2(i32 %n) {
  57 entry:
  58   %mul = mul i32 %n, 3
  59   %cmp4 = icmp eq i32 %mul, 0
  60   br i1 %cmp4, label %for.cond.cleanup, label %for.body.preheader
  61
  62 for.body.preheader:                               ; preds = %entry
  63   br label %for.body
  64
  65 for.cond.cleanup.loopexit:                        ; preds = %for.body
  66   br label %for.cond.cleanup
  67
  68 for.cond.cleanup:                                 ; preds = %for.cond.cleanup.loopexit, %entry
  69   ret void
  70
  71 for.body:                                         ; preds = %for.body.preheader, %for.body
  72   %i.05 = phi i32 [ %inc, %for.body ], [ 0, %for.body.preheader ]
  73   %call = tail call i32 (ptr, ...) @printf(ptr @.str2, i32 %i.05)
  74   %inc = add nuw i32 %i.05, 1
  75   %cmp = icmp eq i32 %inc, %mul
  76   br i1 %cmp, label %for.cond.cleanup.loopexit, label %for.body
  77 }
  78
  79 declare i32 @printf(ptr nocapture readonly, ...)
  80
  81
  82 ; If we couldn't prove no overflow for the multiply expression 24 * n,
  83 ; returns the greatest power of 2 divisor. If overflows happens
  84 ; the trip count is still divisible by the greatest power of 2 divisor.
  85 ;
  86 ; CHECK: Loop %l3: Trip multiple is 8
  87
  88 declare void @f()
  89
  90 define i32 @foo3(i32 %n) {
  91 entry:
  92   %loop_ctl = mul i32 %n, 24
  93   br label %l3
  94
  95 l3:
  96   %x.0 = phi i32 [ 0, %entry ], [ %inc, %l3 ]
  97   call void @f()
  98   %inc = add i32 %x.0, 1
  99   %exitcond = icmp eq i32 %inc, %loop_ctl
 100   br i1 %exitcond, label %exit, label %l3
 101
 102 exit:
 103   ret i32 0
 104 }
 105
 106 ; If the trip count is a constant, verify that we obtained the trip
 107 ; count itself. For huge trip counts, or zero, we return 1.
 108 ;
 109 ; CHECK: Loop %l3: Trip multiple is 3
 110
 111 define i32 @foo4(i32 %n) {
 112 entry:
 113   br label %l3
 114
 115 l3:
 116   %x.0 = phi i32 [ 0, %entry ], [ %inc, %l3 ]
 117   call void @f()
 118   %inc = add i32 %x.0, 1
 119   %exitcond = icmp eq i32 %inc, 3
 120   br i1 %exitcond, label %exit, label %l3
 121
 122 exit:
 123   ret i32 0
 124 }
 125
 126 ; If there are multiple exits, the result is the GCD of the multiples
 127 ; of each individual exit (since we don't know which is taken).
 128
 129 ; CHECK: Loop %l4: Trip multiple is 50
 130
 131 define i32 @foo5(i32 %n) {
 132 entry:
 133   br label %l4
 134
 135 l4:
 136   %x.0 = phi i32 [ 0, %entry ], [ %inc, %l4-latch ]
 137   call void @f()
 138   %inc = add i32 %x.0, 1
 139   %earlycond = icmp eq i32 %inc, 150
 140   br i1 %earlycond, label %exit, label %l4-latch
 141
 142 l4-latch:
 143   %exitcond = icmp eq i32 %inc, 200
 144   br i1 %exitcond, label %exit, label %l4
 145
 146 exit:
 147   ret i32 0
 148 }
 149