test/Transforms/IndVarSimplify/no-iv-rewrite.ll

   1 ; RUN: opt < %s -indvars -S | FileCheck %s
   2 ;
   3 ; Make sure that indvars isn't inserting canonical IVs.
   4 ; This is kinda hard to do until linear function test replacement is removed.
   5
   6 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
   7
   8 define i32 @sum(i32* %arr, i32 %n) nounwind {
   9 entry:
  10   %precond = icmp slt i32 0, %n
  11   br i1 %precond, label %ph, label %return
  12
  13 ph:
  14   br label %loop
  15
  16 ; CHECK: loop:
  17 ;
  18 ; We should only have 2 IVs.
  19 ; CHECK: phi
  20 ; CHECK: phi
  21 ; CHECK-NOT: phi
  22 ;
  23 ; sext should be eliminated while preserving gep inboundsness.
  24 ; CHECK-NOT: sext
  25 ; CHECK: getelementptr inbounds
  26 ; CHECK: exit:
  27 loop:
  28   %i.02 = phi i32 [ 0, %ph ], [ %iinc, %loop ]
  29   %s.01 = phi i32 [ 0, %ph ], [ %sinc, %loop ]
  30   %ofs = sext i32 %i.02 to i64
  31   %adr = getelementptr inbounds i32, i32* %arr, i64 %ofs
  32   %val = load i32, i32* %adr
  33   %sinc = add nsw i32 %s.01, %val
  34   %iinc = add nsw i32 %i.02, 1
  35   %cond = icmp slt i32 %iinc, %n
  36   br i1 %cond, label %loop, label %exit
  37
  38 exit:
  39   %s.lcssa = phi i32 [ %sinc, %loop ]
  40   br label %return
  41
  42 return:
  43   %s.0.lcssa = phi i32 [ %s.lcssa, %exit ], [ 0, %entry ]
  44   ret i32 %s.0.lcssa
  45 }
  46
  47 define i64 @suml(i32* %arr, i32 %n) nounwind {
  48 entry:
  49   %precond = icmp slt i32 0, %n
  50   br i1 %precond, label %ph, label %return
  51
  52 ph:
  53   br label %loop
  54
  55 ; CHECK: loop:
  56 ;
  57 ; We should only have 2 IVs.
  58 ; CHECK: phi
  59 ; CHECK: phi
  60 ; CHECK-NOT: phi
  61 ;
  62 ; %ofs sext should be eliminated while preserving gep inboundsness.
  63 ; CHECK-NOT: sext
  64 ; CHECK: getelementptr inbounds
  65 ; %vall sext should obviously not be eliminated
  66 ; CHECK: sext
  67 ; CHECK: exit:
  68 loop:
  69   %i.02 = phi i32 [ 0, %ph ], [ %iinc, %loop ]
  70   %s.01 = phi i64 [ 0, %ph ], [ %sinc, %loop ]
  71   %ofs = sext i32 %i.02 to i64
  72   %adr = getelementptr inbounds i32, i32* %arr, i64 %ofs
  73   %val = load i32, i32* %adr
  74   %vall = sext i32 %val to i64
  75   %sinc = add nsw i64 %s.01, %vall
  76   %iinc = add nsw i32 %i.02, 1
  77   %cond = icmp slt i32 %iinc, %n
  78   br i1 %cond, label %loop, label %exit
  79
  80 exit:
  81   %s.lcssa = phi i64 [ %sinc, %loop ]
  82   br label %return
  83
  84 return:
  85   %s.0.lcssa = phi i64 [ %s.lcssa, %exit ], [ 0, %entry ]
  86   ret i64 %s.0.lcssa
  87 }
  88
  89 define void @outofbounds(i32* %first, i32* %last, i32 %idx) nounwind {
  90   %precond = icmp ne i32* %first, %last
  91   br i1 %precond, label %ph, label %return
  92
  93 ; CHECK: ph:
  94 ; It's not indvars' job to perform LICM on %ofs
  95 ; CHECK-NOT: sext
  96 ph:
  97   br label %loop
  98
  99 ; CHECK: loop:
 100 ;
 101 ; Preserve exactly one pointer type IV.
 102 ; CHECK: phi i32*
 103 ; CHECK-NOT: phi
 104 ;
 105 ; Don't create any extra adds.
 106 ; CHECK-NOT: add
 107 ;
 108 ; Preserve gep inboundsness, and don't factor it.
 109 ; CHECK: getelementptr inbounds i32, i32* %ptriv, i32 1
 110 ; CHECK-NOT: add
 111 ; CHECK: exit:
 112 loop:
 113   %ptriv = phi i32* [ %first, %ph ], [ %ptrpost, %loop ]
 114   %ofs = sext i32 %idx to i64
 115   %adr = getelementptr inbounds i32, i32* %ptriv, i64 %ofs
 116   store i32 3, i32* %adr
 117   %ptrpost = getelementptr inbounds i32, i32* %ptriv, i32 1
 118   %cond = icmp ne i32* %ptrpost, %last
 119   br i1 %cond, label %loop, label %exit
 120
 121 exit:
 122   br label %return
 123
 124 return:
 125   ret void
 126 }
 127
 128 %structI = type { i32 }
 129
 130 define void @bitcastiv(i32 %start, i32 %limit, i32 %step, %structI* %base)
 131 nounwind
 132 {
 133 entry:
 134   br label %loop
 135
 136 ; CHECK: loop:
 137 ;
 138 ; Preserve casts
 139 ; CHECK: phi i32
 140 ; CHECK: bitcast
 141 ; CHECK: getelementptr
 142 ; CHECK: exit:
 143 loop:
 144   %iv = phi i32 [%start, %entry], [%next, %loop]
 145   %p = phi %structI* [%base, %entry], [%pinc, %loop]
 146   %adr = getelementptr %structI, %structI* %p, i32 0, i32 0
 147   store i32 3, i32* %adr
 148   %pp = bitcast %structI* %p to i32*
 149   store i32 4, i32* %pp
 150   %pinc = getelementptr %structI, %structI* %p, i32 1
 151   %next = add i32 %iv, 1
 152   %cond = icmp ne i32 %next, %limit
 153   br i1 %cond, label %loop, label %exit
 154
 155 exit:
 156   ret void
 157 }
 158
 159 define void @maxvisitor(i32 %limit, i32* %base) nounwind {
 160 entry:
 161  br label %loop
 162
 163 ; Test inserting a truncate at a phi use.
 164 ;
 165 ; CHECK: loop:
 166 ; CHECK: phi i64
 167 ; CHECK: trunc
 168 ; CHECK: exit:
 169 loop:
 170   %idx = phi i32 [ 0, %entry ], [ %idx.next, %loop.inc ]
 171   %max = phi i32 [ 0, %entry ], [ %max.next, %loop.inc ]
 172   %idxprom = sext i32 %idx to i64
 173   %adr = getelementptr inbounds i32, i32* %base, i64 %idxprom
 174   %val = load i32, i32* %adr
 175   %cmp19 = icmp sgt i32 %val, %max
 176   br i1 %cmp19, label %if.then, label %if.else
 177
 178 if.then:
 179   br label %loop.inc
 180
 181 if.else:
 182   br label %loop.inc
 183
 184 loop.inc:
 185   %max.next = phi i32 [ %idx, %if.then ], [ %max, %if.else ]
 186   %idx.next = add nsw i32 %idx, 1
 187   %cmp = icmp slt i32 %idx.next, %limit
 188   br i1 %cmp, label %loop, label %exit
 189
 190 exit:
 191   ret void
 192 }
 193
 194 define void @identityphi(i32 %limit) nounwind {
 195 entry:
 196   br label %loop
 197
 198 ; Test an edge case of removing an identity phi that directly feeds
 199 ; back to the loop iv.
 200 ;
 201 ; CHECK: loop:
 202 ; CHECK-NOT: phi
 203 ; CHECK: exit:
 204 loop:
 205   %iv = phi i32 [ 0, %entry], [ %iv.next, %control ]
 206   br i1 undef, label %if.then, label %control
 207
 208 if.then:
 209   br label %control
 210
 211 control:
 212   %iv.next = phi i32 [ %iv, %loop ], [ undef, %if.then ]
 213   %cmp = icmp slt i32 %iv.next, %limit
 214   br i1 %cmp, label %loop, label %exit
 215
 216 exit:
 217   ret void
 218 }
 219
 220 define i64 @cloneOr(i32 %limit, i64* %base) nounwind {
 221 entry:
 222   ; ensure that the loop can't overflow
 223   %halfLim = ashr i32 %limit, 2
 224   br label %loop
 225
 226 ; This test originally checked that the OR instruction was cloned. Now the
 227 ; ScalarEvolution is able to understand the loop evolution and that '%iv' at the
 228 ; end of the loop is an even value. Thus '%val' is computed at the end of the
 229 ; loop and the OR instruction is replaced by an ADD keeping the result
 230 ; equivalent.
 231 ;
 232 ; CHECK: sext
 233 ; CHECK: loop:
 234 ; CHECK: phi i64
 235 ; CHECK-NOT: sext
 236 ; CHECK: icmp slt i64
 237 ; CHECK: exit:
 238 ; CHECK: add i64
 239 loop:
 240   %iv = phi i32 [ 0, %entry], [ %iv.next, %loop ]
 241   %t1 = sext i32 %iv to i64
 242   %adr = getelementptr i64, i64* %base, i64 %t1
 243   %val = load i64, i64* %adr
 244   %t2 = or i32 %iv, 1
 245   %t3 = sext i32 %t2 to i64
 246   %iv.next = add i32 %iv, 2
 247   %cmp = icmp slt i32 %iv.next, %halfLim
 248   br i1 %cmp, label %loop, label %exit
 249
 250 exit:
 251   %result = and i64 %val, %t3
 252   ret i64 %result
 253 }
 254
 255 ; The i induction variable looks like a wrap-around, but it really is just
 256 ; a simple affine IV.  Make sure that indvars simplifies through.
 257 define i32 @indirectRecurrence() nounwind {
 258 entry:
 259   br label %loop
 260
 261 ; ReplaceLoopExitValue should fold the return value to constant 9.
 262 ; CHECK: loop:
 263 ; CHECK: phi i32
 264 ; CHECK: ret i32 9
 265 loop:
 266   %j.0 = phi i32 [ 1, %entry ], [ %j.next, %cond_true ]
 267   %i.0 = phi i32 [ 0, %entry ], [ %j.0, %cond_true ]
 268   %tmp = icmp ne i32 %j.0, 10
 269   br i1 %tmp, label %cond_true, label %return
 270
 271 cond_true:
 272   %j.next = add i32 %j.0, 1
 273   br label %loop
 274
 275 return:
 276   ret i32 %i.0
 277 }
 278
 279 ; Eliminate the congruent phis j, k, and l.
 280 ; Eliminate the redundant IV increments k.next and l.next.
 281 ; Two phis should remain, one starting at %init, and one at %init1.
 282 ; Two increments should remain, one by %step and one by %step1.
 283 ; CHECK: loop:
 284 ; CHECK: phi i32
 285 ; CHECK: phi i32
 286 ; CHECK-NOT: phi
 287 ; CHECK: add i32
 288 ; CHECK: add i32
 289 ; CHECK: add i32
 290 ; CHECK-NOT: add
 291 ; CHECK: return:
 292 ;
 293 ; Five live-outs should remain.
 294 ; CHECK: lcssa = phi
 295 ; CHECK: lcssa = phi
 296 ; CHECK: lcssa = phi
 297 ; CHECK: lcssa = phi
 298 ; CHECK: lcssa = phi
 299 ; CHECK-NOT: phi
 300 ; CHECK: ret
 301 define i32 @isomorphic(i32 %init, i32 %step, i32 %lim) nounwind {
 302 entry:
 303   %step1 = add i32 %step, 1
 304   %init1 = add i32 %init, %step1
 305   %l.0 = sub i32 %init1, %step1
 306   br label %loop
 307
 308 loop:
 309   %ii = phi i32 [ %init1, %entry ], [ %ii.next, %loop ]
 310   %i = phi i32 [ %init, %entry ], [ %ii, %loop ]
 311   %j = phi i32 [ %init, %entry ], [ %j.next, %loop ]
 312   %k = phi i32 [ %init1, %entry ], [ %k.next, %loop ]
 313   %l = phi i32 [ %l.0, %entry ], [ %l.next, %loop ]
 314   %ii.next = add i32 %ii, %step1
 315   %j.next = add i32 %j, %step1
 316   %k.next = add i32 %k, %step1
 317   %l.step = add i32 %l, %step
 318   %l.next = add i32 %l.step, 1
 319   %cmp = icmp ne i32 %ii.next, %lim
 320   br i1 %cmp, label %loop, label %return
 321
 322 return:
 323   %sum1 = add i32 %i, %j.next
 324   %sum2 = add i32 %sum1, %k.next
 325   %sum3 = add i32 %sum1, %l.step
 326   %sum4 = add i32 %sum1, %l.next
 327   ret i32 %sum4
 328 }
 329
 330 ; Test a GEP IV that is derived from another GEP IV by a nop gep that
 331 ; lowers the type without changing the expression.
 332 %structIF = type { i32, float }
 333
 334 define void @congruentgepiv(%structIF* %base) nounwind uwtable ssp {
 335 entry:
 336   %first = getelementptr inbounds %structIF, %structIF* %base, i64 0, i32 0
 337   br label %loop
 338
 339 ; CHECK: loop:
 340 ; CHECK: phi %structIF*
 341 ; CHECK-NOT: phi
 342 ; CHECK: getelementptr inbounds
 343 ; CHECK-NOT: getelementptr
 344 ; CHECK: exit:
 345 loop:
 346   %ptr.iv = phi %structIF* [ %ptr.inc, %latch ], [ %base, %entry ]
 347   %next = phi i32* [ %next.inc, %latch ], [ %first, %entry ]
 348   store i32 4, i32* %next
 349   br i1 undef, label %latch, label %exit
 350
 351 latch:                         ; preds = %for.inc50.i
 352   %ptr.inc = getelementptr inbounds %structIF, %structIF* %ptr.iv, i64 1
 353   %next.inc = getelementptr inbounds %structIF, %structIF* %ptr.inc, i64 0, i32 0
 354   br label %loop
 355
 356 exit:
 357   ret void
 358 }
 359
 360 declare void @use32(i32 %x)
 361 declare void @use64(i64 %x)
 362
 363 ; Test a widened IV that is used by a phi on different paths within the loop.
 364 ;
 365 ; CHECK: for.body:
 366 ; CHECK: phi i64
 367 ; CHECK: trunc i64
 368 ; CHECK: if.then:
 369 ; CHECK: for.inc:
 370 ; CHECK: phi i32
 371 ; CHECK: for.end:
 372 define void @phiUsesTrunc() nounwind {
 373 entry:
 374   br i1 undef, label %for.body, label %for.end
 375
 376 for.body:
 377   %iv = phi i32 [ %inc, %for.inc ], [ 1, %entry ]
 378   br i1 undef, label %if.then, label %if.else
 379
 380 if.then:
 381   br i1 undef, label %if.then33, label %for.inc
 382
 383 if.then33:
 384   br label %for.inc
 385
 386 if.else:
 387   br i1 undef, label %if.then97, label %for.inc
 388
 389 if.then97:
 390   %idxprom100 = sext i32 %iv to i64
 391   call void @use64(i64 %idxprom100)
 392   br label %for.inc
 393
 394 for.inc:
 395   %kmin.1 = phi i32 [ %iv, %if.then33 ], [ 0, %if.then ], [ %iv, %if.then97 ], [ 0, %if.else ]
 396   call void @use32(i32 %kmin.1)
 397   %inc = add nsw i32 %iv, 1
 398   br i1 undef, label %for.body, label %for.end
 399
 400 for.end:
 401   ret void
 402 }