llvm/test/Analysis/ScalarEvolution/shift-op.ll

   1 ; RUN: opt -analyze -enable-new-pm=0 -scalar-evolution < %s | FileCheck %s
   2 ; RUN: opt -disable-output "-passes=print<scalar-evolution>" < %s 2>&1 | FileCheck %s
   3
   4 define void @test0(i32 %init) {
   5 ; CHECK-LABEL: Classifying expressions for: @test0
   6 ; CHECK: Loop %loop: max backedge-taken count is 32
   7  entry:
   8   br label %loop
   9
  10  loop:
  11   %iv = phi i32 [ %init, %entry ], [ %iv.shift, %loop ]
  12   %iv.shift = lshr i32 %iv, 1
  13   %exit.cond = icmp eq i32 %iv, 0
  14   br i1 %exit.cond, label %leave, label %loop
  15
  16  leave:
  17   ret void
  18 }
  19
  20 define void @test1(i32 %init) {
  21 ; CHECK-LABEL: Classifying expressions for: @test1
  22 ; CHECK: Loop %loop: max backedge-taken count is 32
  23  entry:
  24   br label %loop
  25
  26  loop:
  27   %iv = phi i32 [ %init, %entry ], [ %iv.shift, %loop ]
  28   %iv.shift = shl i32 %iv, 1
  29   %exit.cond = icmp eq i32 %iv, 0
  30   br i1 %exit.cond, label %leave, label %loop
  31
  32  leave:
  33   ret void
  34 }
  35
  36 define void @test2(i32 %init) {
  37 ; CHECK-LABEL: Determining loop execution counts for: @test2
  38 ; CHECK: Loop %loop: Unpredictable max backedge-taken count.
  39
  40 ; Unpredictable because %iv could "stabilize" to either -1 or 0,
  41 ; depending on %init.
  42  entry:
  43   br label %loop
  44
  45  loop:
  46   %iv = phi i32 [ %init, %entry ], [ %iv.shift, %loop ]
  47   %iv.shift = ashr i32 %iv, 1
  48   %exit.cond = icmp eq i32 %iv, 0
  49   br i1 %exit.cond, label %leave, label %loop
  50
  51  leave:
  52   ret void
  53 }
  54
  55 define void @test3(i32* %init.ptr) {
  56 ; CHECK-LABEL: Determining loop execution counts for: @test3
  57 ; CHECK: Loop %loop: max backedge-taken count is 32
  58  entry:
  59   %init = load i32, i32* %init.ptr, !range !0
  60   br label %loop
  61
  62  loop:
  63   %iv = phi i32 [ %init, %entry ], [ %iv.shift, %loop ]
  64   %iv.shift = ashr i32 %iv, 1
  65   %exit.cond = icmp eq i32 %iv, 0
  66   br i1 %exit.cond, label %leave, label %loop
  67
  68  leave:
  69   ret void
  70 }
  71
  72 define void @test4(i32* %init.ptr) {
  73 ; CHECK-LABEL: Classifying expressions for: @test4
  74 ; CHECK-LABEL: Loop %loop: max backedge-taken count is 32
  75  entry:
  76   %init = load i32, i32* %init.ptr, !range !1
  77   br label %loop
  78
  79  loop:
  80   %iv = phi i32 [ %init, %entry ], [ %iv.shift, %loop ]
  81   %iv.shift = ashr i32 %iv, 1
  82   %exit.cond = icmp eq i32 %iv, -1
  83   br i1 %exit.cond, label %leave, label %loop
  84
  85  leave:
  86   ret void
  87 }
  88
  89 define void @test5(i32* %init.ptr) {
  90 ; CHECK-LABEL: Determining loop execution counts for: @test5
  91 ; CHECK: Loop %loop: Unpredictable max backedge-taken count.
  92
  93 ; %iv will "stabilize" to -1, so this is an infinite loop
  94  entry:
  95   %init = load i32, i32* %init.ptr, !range !1
  96   br label %loop
  97
  98  loop:
  99   %iv = phi i32 [ %init, %entry ], [ %iv.shift, %loop ]
 100   %iv.shift = ashr i32 %iv, 1
 101   %exit.cond = icmp eq i32 %iv, 0
 102   br i1 %exit.cond, label %leave, label %loop
 103
 104  leave:
 105   ret void
 106 }
 107
 108 define void @test6(i32 %init, i32 %shift.amt) {
 109 ; CHECK-LABEL: Determining loop execution counts for: @test6
 110 ; CHECK: Loop %loop: Unpredictable max backedge-taken count.
 111
 112 ; Potentially infinite loop, since %shift.amt could be 0
 113  entry:
 114   br label %loop
 115
 116  loop:
 117   %iv = phi i32 [ %init, %entry ], [ %iv.shift, %loop ]
 118   %iv.shift = lshr i32 %iv, %shift.amt
 119   %exit.cond = icmp eq i32 %iv, 0
 120   br i1 %exit.cond, label %leave, label %loop
 121
 122  leave:
 123   ret void
 124 }
 125
 126 define void @test7(i32 %init) {
 127 ; CHECK-LABEL: Classifying expressions for: @test7
 128 ; CHECK: Loop %loop: max backedge-taken count is 32
 129
 130  entry:
 131   br label %loop
 132
 133  loop:
 134   %iv = phi i32 [ %init, %entry ], [ %iv.shift, %loop ]
 135   %iv.shift = lshr i32 %iv, 1
 136   %exit.cond = icmp eq i32 %iv.shift, 0
 137   br i1 %exit.cond, label %leave, label %loop
 138
 139  leave:
 140   ret void
 141 }
 142
 143 define void @test8(i32 %init) {
 144 ; CHECK-LABEL: Classifying expressions for: @test8
 145 ; CHECK: Loop %loop: Unpredictable max backedge-taken count.
 146
 147 ; In this test case, %iv.test stabilizes to 127, not -1, so the loop
 148 ; is infinite.
 149
 150  entry:
 151   br label %loop
 152
 153  loop:
 154   %iv = phi i32 [ %init, %entry ], [ %iv.shift, %loop ]
 155   %iv.shift = ashr i32 %iv, 1
 156   %iv.test = lshr i32 %iv, 1
 157   %exit.cond = icmp eq i32 %iv.test, -1
 158   br i1 %exit.cond, label %leave, label %loop
 159
 160  leave:
 161   ret void
 162 }
 163
 164 define void @test9() {
 165 ; CHECK-LABEL: Determining loop execution counts for: @test9
 166 ; CHECK: Loop %loop: Unpredictable max backedge-taken count.
 167
 168 ; This is an infinite loop, make sure that it recognized as such.
 169
 170 entry:
 171   br label %loop
 172
 173 leave:
 174   ret void
 175
 176 loop:
 177   %iv = phi i32 [ -20, %entry ], [ %iv.shift, %loop ]
 178   %iv.shift = ashr i32 %iv, 1
 179   %exit.cond = icmp sgt i32 %iv, -1
 180   br i1 %exit.cond, label %leave, label %loop
 181 }
 182
 183 !0 = !{i32 0, i32 50000}
 184 !1 = !{i32 -5000, i32 -1}