1 ; RUN: opt -S -indvars %s | FileCheck %s 2 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" 3 target triple = "x86_64-unknown-linux-gnu" 4 5 define void @test1(i64 %start) { 6 ; CHECK-LABEL: @test1 7 entry: 8 br label %loop 9 10 loop: 11 %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %loop ] 12 %indvars.iv.next = add nsw i64 %indvars.iv, 1 13 ; CHECK: %cmp1 = icmp slt i64 %start, -1 14 %cmp1 = icmp slt i64 %indvars.iv, -1 15 br i1 %cmp1, label %for.end, label %loop 16 17 for.end: ; preds = %if.end, %entry 18 ret void 19 } 20 21 define void @test2(i64 %start) { 22 ; CHECK-LABEL: @test2 23 entry: 24 br label %loop 25 26 loop: 27 %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %loop ] 28 %indvars.iv.next = add nsw i64 %indvars.iv, 1 29 ; CHECK: %cmp1 = icmp sle i64 %start, -1 30 %cmp1 = icmp sle i64 %indvars.iv, -1 31 br i1 %cmp1, label %for.end, label %loop 32 33 for.end: ; preds = %if.end, %entry 34 ret void 35 } 36 37 ; As long as the test dominates the backedge, we're good 38 define void @test3(i64 %start) { 39 ; CHECK-LABEL: @test3 40 entry: 41 br label %loop 42 43 loop: 44 %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %backedge ] 45 %indvars.iv.next = add nsw i64 %indvars.iv, 1 46 %cmp = icmp eq i64 %indvars.iv.next, 25 47 br i1 %cmp, label %backedge, label %for.end 48 49 backedge: 50 ; prevent flattening, needed to make sure we're testing what we intend 51 call void @foo() 52 ; CHECK: %cmp1 = icmp slt i64 %start, -1 53 %cmp1 = icmp slt i64 %indvars.iv, -1 54 br i1 %cmp1, label %for.end, label %loop 55 56 for.end: ; preds = %if.end, %entry 57 ret void 58 } 59 60 define void @test4(i64 %start) { 61 ; CHECK-LABEL: @test4 62 entry: 63 br label %loop 64 65 loop: 66 %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %backedge ] 67 %indvars.iv.next = add nsw i64 %indvars.iv, 1 68 %cmp = icmp eq i64 %indvars.iv.next, 25 69 br i1 %cmp, label %backedge, label %for.end 70 71 backedge: 72 ; prevent flattening, needed to make sure we're testing what we intend 73 call void @foo() 74 ; CHECK: %cmp1 = icmp sgt i64 %start, -1 75 %cmp1 = icmp sgt i64 %indvars.iv, -1 76 br i1 %cmp1, label %loop, label %for.end 77 78 for.end: ; preds = %if.end, %entry 79 ret void 80 } 81 82 define void @test5(i64 %start) { 83 ; CHECK-LABEL: @test5 84 entry: 85 br label %loop 86 87 loop: 88 %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %backedge ] 89 %indvars.iv.next = add nuw i64 %indvars.iv, 1 90 %cmp = icmp eq i64 %indvars.iv.next, 25 91 br i1 %cmp, label %backedge, label %for.end 92 93 backedge: 94 ; prevent flattening, needed to make sure we're testing what we intend 95 call void @foo() 96 ; CHECK: %cmp1 = icmp ugt i64 %start, 100 97 %cmp1 = icmp ugt i64 %indvars.iv, 100 98 br i1 %cmp1, label %loop, label %for.end 99 100 for.end: ; preds = %if.end, %entry 101 ret void 102 } 103 104 define void @test6(i64 %start) { 105 ; CHECK-LABEL: @test6 106 entry: 107 br label %loop 108 109 loop: 110 %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %backedge ] 111 %indvars.iv.next = add nuw i64 %indvars.iv, 1 112 %cmp = icmp eq i64 %indvars.iv.next, 25 113 br i1 %cmp, label %backedge, label %for.end 114 115 backedge: 116 ; prevent flattening, needed to make sure we're testing what we intend 117 call void @foo() 118 ; CHECK: %cmp1 = icmp ult i64 %start, 100 119 %cmp1 = icmp ult i64 %indvars.iv, 100 120 br i1 %cmp1, label %for.end, label %loop 121 122 for.end: ; preds = %if.end, %entry 123 ret void 124 } 125 126 define void @test7(i64 %start, i64* %inc_ptr) { 127 ; CHECK-LABEL: @test7 128 entry: 129 %inc = load i64, i64* %inc_ptr, !range !0 130 %ok = icmp sge i64 %inc, 0 131 br i1 %ok, label %loop, label %for.end 132 133 loop: 134 %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %loop ] 135 %indvars.iv.next = add nsw i64 %indvars.iv, %inc 136 ; CHECK: %cmp1 = icmp slt i64 %start, -1 137 %cmp1 = icmp slt i64 %indvars.iv, -1 138 br i1 %cmp1, label %for.end, label %loop 139 140 for.end: ; preds = %if.end, %entry 141 ret void 142 } 143 144 ; Negative test - we can't show that the internal branch executes, so we can't 145 ; fold the test to a loop invariant one. 146 define void @test1_neg(i64 %start) { 147 ; CHECK-LABEL: @test1_neg 148 entry: 149 br label %loop 150 151 loop: 152 %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %backedge ] 153 %indvars.iv.next = add nsw i64 %indvars.iv, 1 154 %cmp = icmp eq i64 %indvars.iv.next, 25 155 br i1 %cmp, label %backedge, label %skip 156 skip: 157 ; prevent flattening, needed to make sure we're testing what we intend 158 call void @foo() 159 ; CHECK: %cmp1 = icmp slt i64 %indvars.iv, -1 160 %cmp1 = icmp slt i64 %indvars.iv, -1 161 br i1 %cmp1, label %for.end, label %backedge 162 backedge: 163 ; prevent flattening, needed to make sure we're testing what we intend 164 call void @foo() 165 br label %loop 166 167 for.end: ; preds = %if.end, %entry 168 ret void 169 } 170 171 ; Slightly subtle version of @test4 where the icmp dominates the backedge, 172 ; but the exit branch doesn't. 173 define void @test2_neg(i64 %start) { 174 ; CHECK-LABEL: @test2_neg 175 entry: 176 br label %loop 177 178 loop: 179 %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %backedge ] 180 %indvars.iv.next = add nsw i64 %indvars.iv, 1 181 %cmp = icmp eq i64 %indvars.iv.next, 25 182 ; CHECK: %cmp1 = icmp slt i64 %indvars.iv, -1 183 %cmp1 = icmp slt i64 %indvars.iv, -1 184 br i1 %cmp, label %backedge, label %skip 185 skip: 186 ; prevent flattening, needed to make sure we're testing what we intend 187 call void @foo() 188 br i1 %cmp1, label %for.end, label %backedge 189 backedge: 190 ; prevent flattening, needed to make sure we're testing what we intend 191 call void @foo() 192 br label %loop 193 194 for.end: ; preds = %if.end, %entry 195 ret void 196 } 197 198 ; The branch has to exit the loop if the condition is true 199 define void @test3_neg(i64 %start) { 200 ; CHECK-LABEL: @test3_neg 201 entry: 202 br label %loop 203 204 loop: 205 %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %loop ] 206 %indvars.iv.next = add nsw i64 %indvars.iv, 1 207 ; CHECK: %cmp1 = icmp slt i64 %indvars.iv, -1 208 %cmp1 = icmp slt i64 %indvars.iv, -1 209 br i1 %cmp1, label %loop, label %for.end 210 211 for.end: ; preds = %if.end, %entry 212 ret void 213 } 214 215 define void @test4_neg(i64 %start) { 216 ; CHECK-LABEL: @test4_neg 217 entry: 218 br label %loop 219 220 loop: 221 %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %backedge ] 222 %indvars.iv.next = add nsw i64 %indvars.iv, 1 223 %cmp = icmp eq i64 %indvars.iv.next, 25 224 br i1 %cmp, label %backedge, label %for.end 225 226 backedge: 227 ; prevent flattening, needed to make sure we're testing what we intend 228 call void @foo() 229 ; CHECK: %cmp1 = icmp sgt i64 %indvars.iv, -1 230 %cmp1 = icmp sgt i64 %indvars.iv, -1 231 232 ; %cmp1 can be made loop invariant only if the branch below goes to 233 ; %the header when %cmp1 is true. 234 br i1 %cmp1, label %for.end, label %loop 235 236 for.end: ; preds = %if.end, %entry 237 ret void 238 } 239 240 define void @test5_neg(i64 %start, i64 %inc) { 241 ; CHECK-LABEL: @test5_neg 242 entry: 243 br label %loop 244 245 loop: 246 %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %loop ] 247 %indvars.iv.next = add nsw i64 %indvars.iv, %inc 248 ; CHECK: %cmp1 = icmp slt i64 %indvars.iv, -1 249 %cmp1 = icmp slt i64 %indvars.iv, -1 250 br i1 %cmp1, label %for.end, label %loop 251 252 for.end: ; preds = %if.end, %entry 253 ret void 254 } 255 256 define void @test8(i64 %start, i64* %inc_ptr) { 257 ; CHECK-LABEL: @test8 258 entry: 259 %inc = load i64, i64* %inc_ptr, !range !1 260 %ok = icmp sge i64 %inc, 0 261 br i1 %ok, label %loop, label %for.end 262 263 loop: 264 %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %loop ] 265 %indvars.iv.next = add nsw i64 %indvars.iv, %inc 266 ; CHECK: %cmp1 = icmp slt i64 %indvars.iv, -1 267 %cmp1 = icmp slt i64 %indvars.iv, -1 268 br i1 %cmp1, label %for.end, label %loop 269 270 for.end: ; preds = %if.end, %entry 271 ret void 272 } 273 274 ; check to handle loops without preheaders, but invariant operands 275 ; (we handle this today by inserting a preheader) 276 define void @test9(i1 %cnd, i64 %start) { 277 ; CHECK-LABEL: @test9 278 ; CHECK-LABEL: loop.preheader: 279 entry: 280 br i1 %cnd, label %entry1, label %entry2 281 entry1: 282 br label %loop 283 entry2: 284 br label %loop 285 loop: 286 %indvars.iv = phi i64 [ %start, %entry1 ],[ %start, %entry2 ], [ %indvars.iv.next, %loop ] 287 %indvars.iv.next = add nsw i64 %indvars.iv, 1 288 ; CHECK: %cmp1 = icmp slt i64 %start, -1 289 %cmp1 = icmp slt i64 %indvars.iv, -1 290 br i1 %cmp1, label %for.end, label %loop 291 292 for.end: ; preds = %if.end, %entry 293 ret void 294 } 295 296 declare void @use(i1 %x) 297 298 ; check that we handle conditions with loop invariant operands which 299 ; *aren't* in the header - this is a very rare and fragile case where 300 ; we have a "loop" which is known to run exactly one iteration but 301 ; haven't yet simplified the uses of the IV 302 define void @test10() { 303 ; CHECK-LABEL: @test10 304 entry: 305 br label %loop 306 307 loop: 308 %phi1 = phi i32 [ %phi2, %latch ], [ 0, %entry ] 309 %dec = add i32 %phi1, -1 310 br i1 false, label %left, label %right 311 312 left: 313 br label %latch 314 315 right: 316 br label %latch 317 318 latch: 319 %phi2 = phi i32 [ %phi1, %left ], [ %dec, %right ] 320 ; CHECK: %cmp = icmp slt i32 -1, undef 321 %cmp = icmp slt i32 %phi2, undef 322 br i1 true, label %exit, label %loop 323 324 exit: 325 call void @use(i1 %cmp) 326 ret void 327 } 328 329 ; check that we can figure out that iv.next > 1 from the facts that iv >= 0 and 330 ; iv.start != 0. 331 define void @test11(i64* %inc_ptr) { 332 ; CHECK-LABEL: @test11 333 entry: 334 %inc = load i64, i64* %inc_ptr, !range !0 335 %ne.cond = icmp ne i64 %inc, 0 336 br i1 %ne.cond, label %loop, label %exit 337 338 loop: 339 %iv = phi i64 [ %inc, %entry ], [ %iv.next, %backedge ] 340 %iv.next = add i64 %iv, 1 341 %brcond = icmp sgt i64 %iv.next, 1 342 ; CHECK: br i1 true, label %if.true, label %if.false 343 br i1 %brcond, label %if.true, label %if.false 344 345 if.true: 346 br label %backedge 347 348 if.false: 349 br label %backedge 350 351 backedge: 352 %loopcond = icmp slt i64 %iv, 200 353 br i1 %loopcond, label %loop, label %exit 354 355 exit: 356 ret void 357 } 358 359 ; check that we can prove that a recurrency is greater than another recurrency 360 ; in the same loop, with the same step, and with smaller starting value. 361 define void @test12(i64* %inc_ptr) { 362 ; CHECK-LABEL: @test12 363 entry: 364 %inc = load i64, i64* %inc_ptr, !range !0 365 %inc.minus.1 = sub i64 %inc, 1 366 br label %loop 367 368 loop: 369 %iv = phi i64 [ %inc, %entry ], [ %iv.next, %backedge ] 370 %iv.minus.1 = phi i64 [ %inc.minus.1, %entry ], [ %iv.minus.1.next, %backedge ] 371 %iv.next = add i64 %iv, 1 372 %iv.minus.1.next = add i64 %iv.minus.1, 1 373 %brcond = icmp sgt i64 %iv.next, %iv.minus.1.next 374 ; CHECK: br i1 true, label %if.true, label %if.false 375 br i1 %brcond, label %if.true, label %if.false 376 377 if.true: 378 br label %backedge 379 380 if.false: 381 br label %backedge 382 383 backedge: 384 %loopcond = icmp slt i64 %iv, 200 385 br i1 %loopcond, label %loop, label %exit 386 387 exit: 388 ret void 389 } 390 391 !0 = !{i64 0, i64 100} 392 !1 = !{i64 -1, i64 100} 393 394 declare void @foo() 395
