llvm/test/Analysis/ScalarEvolution/tripmultiple_calculation.ll

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