llvm/test/Analysis/ValueTracking/recurrence-knownbits.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt < %s -passes=instcombine -S | FileCheck %s
   3
   4 define i64 @test_lshr(i1 %c) {
   5 ; CHECK-LABEL: @test_lshr(
   6 ; CHECK-NEXT:  entry:
   7 ; CHECK-NEXT:    br label [[LOOP:%.*]]
   8 ; CHECK:       loop:
   9 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[EXIT:%.*]], label [[LOOP]]
  10 ; CHECK:       exit:
  11 ; CHECK-NEXT:    ret i64 1023
  12 ;
  13 entry:
  14   br label %loop
  15 loop:
  16   %iv.lshr = phi i64 [1023, %entry], [%iv.lshr.next, %loop]
  17   %iv.lshr.next = lshr i64 %iv.lshr, 1
  18   br i1 %c, label %exit, label %loop
  19 exit:
  20   %res = or i64 %iv.lshr, 1023
  21   ret i64 %res
  22 }
  23
  24 define i64 @test_add(i1 %c) {
  25 ; CHECK-LABEL: @test_add(
  26 ; CHECK-NEXT:  entry:
  27 ; CHECK-NEXT:    br label [[LOOP:%.*]]
  28 ; CHECK:       loop:
  29 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[EXIT:%.*]], label [[LOOP]]
  30 ; CHECK:       exit:
  31 ; CHECK-NEXT:    ret i64 0
  32 ;
  33 entry:
  34   br label %loop
  35 loop:
  36   %iv = phi i64 [8, %entry], [%iv.next, %loop]
  37   %iv.next = add nuw i64 %iv, 4
  38   br i1 %c, label %exit, label %loop
  39 exit:
  40   %res = and i64 %iv, 1
  41   ret i64 %res
  42 }
  43
  44 define i64 @test_sub(i1 %c) {
  45 ; CHECK-LABEL: @test_sub(
  46 ; CHECK-NEXT:  entry:
  47 ; CHECK-NEXT:    br label [[LOOP:%.*]]
  48 ; CHECK:       loop:
  49 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[EXIT:%.*]], label [[LOOP]]
  50 ; CHECK:       exit:
  51 ; CHECK-NEXT:    ret i64 0
  52 ;
  53 entry:
  54   br label %loop
  55 loop:
  56   %iv = phi i64 [8, %entry], [%iv.next, %loop]
  57   %iv.next = sub nuw i64 %iv, 4
  58   br i1 %c, label %exit, label %loop
  59 exit:
  60   %res = and i64 %iv, 1
  61   ret i64 %res
  62 }
  63
  64 define i64 @test_mul(i1 %c) {
  65 ; CHECK-LABEL: @test_mul(
  66 ; CHECK-NEXT:  entry:
  67 ; CHECK-NEXT:    br label [[LOOP:%.*]]
  68 ; CHECK:       loop:
  69 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[EXIT:%.*]], label [[LOOP]]
  70 ; CHECK:       exit:
  71 ; CHECK-NEXT:    ret i64 0
  72 ;
  73 entry:
  74   br label %loop
  75 loop:
  76   %iv = phi i64 [8, %entry], [%iv.next, %loop]
  77   %iv.next = mul i64 %iv, 2
  78   br i1 %c, label %exit, label %loop
  79 exit:
  80   %res = and i64 %iv, 2
  81   ret i64 %res
  82 }
  83
  84 define i64 @test_udiv(i1 %c) {
  85 ; CHECK-LABEL: @test_udiv(
  86 ; CHECK-NEXT:  entry:
  87 ; CHECK-NEXT:    br label [[LOOP:%.*]]
  88 ; CHECK:       loop:
  89 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[EXIT:%.*]], label [[LOOP]]
  90 ; CHECK:       exit:
  91 ; CHECK-NEXT:    ret i64 0
  92 ;
  93 entry:
  94   br label %loop
  95 loop:
  96   %iv = phi i64 [9, %entry], [%iv.next, %loop]
  97   %iv.next = udiv i64 %iv, 3
  98   br i1 %c, label %exit, label %loop
  99 exit:
 100   %res = and i64 %iv, 16
 101   ret i64 %res
 102 }
 103
 104 define i64 @test_udiv_neg(i1 %c) {
 105 ; CHECK-LABEL: @test_udiv_neg(
 106 ; CHECK-NEXT:  entry:
 107 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 108 ; CHECK:       loop:
 109 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 2, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 110 ; CHECK-NEXT:    [[IV_NEXT]] = udiv i64 9, [[IV]]
 111 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[EXIT:%.*]], label [[LOOP]]
 112 ; CHECK:       exit:
 113 ; CHECK-NEXT:    [[RES:%.*]] = and i64 [[IV]], 4
 114 ; CHECK-NEXT:    ret i64 [[RES]]
 115 ;
 116 entry:
 117   br label %loop
 118 loop:
 119   %iv = phi i64 [2, %entry], [%iv.next, %loop]
 120   %iv.next = udiv i64 9, %iv
 121   br i1 %c, label %exit, label %loop
 122 exit:
 123   %res = and i64 %iv, 4
 124   ret i64 %res
 125 }
 126
 127 define i64 @test_urem(i1 %c) {
 128 ; CHECK-LABEL: @test_urem(
 129 ; CHECK-NEXT:  entry:
 130 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 131 ; CHECK:       loop:
 132 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[EXIT:%.*]], label [[LOOP]]
 133 ; CHECK:       exit:
 134 ; CHECK-NEXT:    ret i64 0
 135 ;
 136 entry:
 137   br label %loop
 138 loop:
 139   %iv = phi i64 [3, %entry], [%iv.next, %loop]
 140   %iv.next = urem i64 9, %iv
 141   br i1 %c, label %exit, label %loop
 142 exit:
 143   %res = and i64 %iv, 4
 144   ret i64 %res
 145 }
 146
 147 define i64 @test_and(i1 %c) {
 148 ; CHECK-LABEL: @test_and(
 149 ; CHECK-NEXT:  entry:
 150 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 151 ; CHECK:       loop:
 152 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[EXIT:%.*]], label [[LOOP]]
 153 ; CHECK:       exit:
 154 ; CHECK-NEXT:    ret i64 2047
 155 ;
 156 entry:
 157   br label %loop
 158 loop:
 159   %iv = phi i64 [1025, %entry], [%iv.next, %loop]
 160   %iv.next = and i64 %iv, 1024
 161   br i1 %c, label %exit, label %loop
 162 exit:
 163   %res = or i64 %iv, 1023
 164   ret i64 %res
 165 }
 166
 167 define i64 @test_or(i1 %c) {
 168 ; CHECK-LABEL: @test_or(
 169 ; CHECK-NEXT:  entry:
 170 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 171 ; CHECK:       loop:
 172 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[EXIT:%.*]], label [[LOOP]]
 173 ; CHECK:       exit:
 174 ; CHECK-NEXT:    ret i64 2047
 175 ;
 176 entry:
 177   br label %loop
 178 loop:
 179   %iv = phi i64 [1025, %entry], [%iv.next, %loop]
 180   %iv.next = or i64 %iv, 1024
 181   br i1 %c, label %exit, label %loop
 182 exit:
 183   %res = or i64 %iv, 1023
 184   ret i64 %res
 185 }
 186
 187 define i64 @test_ashr_zeros(i1 %c) {
 188 ; CHECK-LABEL: @test_ashr_zeros(
 189 ; CHECK-NEXT:  entry:
 190 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 191 ; CHECK:       loop:
 192 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[EXIT:%.*]], label [[LOOP]]
 193 ; CHECK:       exit:
 194 ; CHECK-NEXT:    ret i64 1023
 195 ;
 196 entry:
 197   br label %loop
 198 loop:
 199   %iv.ashr = phi i64 [1023, %entry], [%iv.ashr.next, %loop]
 200   %iv.ashr.next = ashr i64 %iv.ashr, 1
 201   br i1 %c, label %exit, label %loop
 202 exit:
 203   %res = or i64 %iv.ashr, 1023
 204   ret i64 %res
 205 }
 206
 207 define i64 @test_ashr_ones(i1 %c) {
 208 ; CHECK-LABEL: @test_ashr_ones(
 209 ; CHECK-NEXT:  entry:
 210 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 211 ; CHECK:       loop:
 212 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[EXIT:%.*]], label [[LOOP]]
 213 ; CHECK:       exit:
 214 ; CHECK-NEXT:    ret i64 -1
 215 ;
 216 entry:
 217   br label %loop
 218 loop:
 219   %iv.ashr = phi i64 [-1023, %entry], [%iv.ashr.next, %loop]
 220   %iv.ashr.next = ashr i64 %iv.ashr, 1
 221   br i1 %c, label %exit, label %loop
 222 exit:
 223   %res = or i64 %iv.ashr, 1023
 224   ret i64 %res
 225 }
 226
 227 ; Same as previous, but swapped operands to phi
 228 define i64 @test_ashr_ones2(i1 %c) {
 229 ; CHECK-LABEL: @test_ashr_ones2(
 230 ; CHECK-NEXT:  entry:
 231 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 232 ; CHECK:       loop:
 233 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[EXIT:%.*]], label [[LOOP]]
 234 ; CHECK:       exit:
 235 ; CHECK-NEXT:    ret i64 -1
 236 ;
 237 entry:
 238   br label %loop
 239 loop:
 240   %iv.ashr = phi i64 [%iv.ashr.next, %loop], [-1023, %entry]
 241   %iv.ashr.next = ashr i64 %iv.ashr, 1
 242   br i1 %c, label %exit, label %loop
 243 exit:
 244   %res = or i64 %iv.ashr, 1023
 245   ret i64 %res
 246 }
 247
 248
 249 ; negative case for when start is unknown
 250 define i64 @test_ashr_unknown(i1 %c, i64 %start) {
 251 ; CHECK-LABEL: @test_ashr_unknown(
 252 ; CHECK-NEXT:  entry:
 253 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 254 ; CHECK:       loop:
 255 ; CHECK-NEXT:    [[IV_ASHR:%.*]] = phi i64 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_ASHR_NEXT:%.*]], [[LOOP]] ]
 256 ; CHECK-NEXT:    [[IV_ASHR_NEXT]] = ashr i64 [[IV_ASHR]], 1
 257 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[EXIT:%.*]], label [[LOOP]]
 258 ; CHECK:       exit:
 259 ; CHECK-NEXT:    [[RES:%.*]] = or i64 [[IV_ASHR]], 1023
 260 ; CHECK-NEXT:    ret i64 [[RES]]
 261 ;
 262 entry:
 263   br label %loop
 264 loop:
 265   %iv.ashr = phi i64 [%start, %entry], [%iv.ashr.next, %loop]
 266   %iv.ashr.next = ashr i64 %iv.ashr, 1
 267   br i1 %c, label %exit, label %loop
 268 exit:
 269   %res = or i64 %iv.ashr, 1023
 270   ret i64 %res
 271 }
 272
 273 ; Negative case where we don't have a (shift) recurrence because the operands
 274 ; of the ashr are swapped.  (This does end up being a divide recurrence.)
 275 define i64 @test_ashr_wrong_op(i1 %c, i64 %start) {
 276 ; CHECK-LABEL: @test_ashr_wrong_op(
 277 ; CHECK-NEXT:  entry:
 278 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 279 ; CHECK:       loop:
 280 ; CHECK-NEXT:    [[IV_ASHR:%.*]] = phi i64 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_ASHR_NEXT:%.*]], [[LOOP]] ]
 281 ; CHECK-NEXT:    [[IV_ASHR_NEXT]] = lshr i64 1, [[IV_ASHR]]
 282 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[EXIT:%.*]], label [[LOOP]]
 283 ; CHECK:       exit:
 284 ; CHECK-NEXT:    [[RES:%.*]] = or i64 [[IV_ASHR]], 1023
 285 ; CHECK-NEXT:    ret i64 [[RES]]
 286 ;
 287 entry:
 288   br label %loop
 289 loop:
 290   %iv.ashr = phi i64 [%start, %entry], [%iv.ashr.next, %loop]
 291   %iv.ashr.next = ashr i64 1, %iv.ashr
 292   br i1 %c, label %exit, label %loop
 293 exit:
 294   %res = or i64 %iv.ashr, 1023
 295   ret i64 %res
 296 }
 297
 298
 299 define i64 @test_shl(i1 %c) {
 300 ; CHECK-LABEL: @test_shl(
 301 ; CHECK-NEXT:  entry:
 302 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 303 ; CHECK:       loop:
 304 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[EXIT:%.*]], label [[LOOP]]
 305 ; CHECK:       exit:
 306 ; CHECK-NEXT:    ret i64 0
 307 ;
 308 entry:
 309   br label %loop
 310 loop:
 311   %iv.shl = phi i64 [8, %entry], [%iv.shl.next, %loop]
 312   %iv.shl.next = shl i64 %iv.shl, 1
 313   br i1 %c, label %exit, label %loop
 314 exit:
 315   %res = and i64 %iv.shl, 7
 316   ret i64 %res
 317 }