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 ; Test a widened IV that is used by a phi on different paths within the loop. 361 ; 362 ; CHECK: for.body: 363 ; CHECK: phi i64 364 ; CHECK: trunc i64 365 ; CHECK: if.then: 366 ; CHECK: for.inc: 367 ; CHECK: phi i32 368 ; CHECK: for.end: 369 define void @phiUsesTrunc() nounwind { 370 entry: 371 br i1 undef, label %for.body, label %for.end 372 373 for.body: 374 %iv = phi i32 [ %inc, %for.inc ], [ 1, %entry ] 375 br i1 undef, label %if.then, label %if.else 376 377 if.then: 378 br i1 undef, label %if.then33, label %for.inc 379 380 if.then33: 381 br label %for.inc 382 383 if.else: 384 br i1 undef, label %if.then97, label %for.inc 385 386 if.then97: 387 %idxprom100 = sext i32 %iv to i64 388 br label %for.inc 389 390 for.inc: 391 %kmin.1 = phi i32 [ %iv, %if.then33 ], [ 0, %if.then ], [ %iv, %if.then97 ], [ 0, %if.else ] 392 %inc = add nsw i32 %iv, 1 393 br i1 undef, label %for.body, label %for.end 394 395 for.end: 396 ret void 397 } 398
