1 ; RUN: opt -analyze -scalar-evolution < %s | FileCheck %s 2 3 ; This test set ensures that we can correctly operate with recurrencies from 4 ; different loops. 5 6 ; Check that we can evaluate a sum of phis from two different loops in any 7 ; order. 8 9 define void @test_00() { 10 11 ; CHECK-LABEL: Classifying expressions for: @test_00 12 ; CHECK: %sum1 = add i32 %phi1, %phi2 13 ; CHECK-NEXT: --> {14,+,3}<%loop1> 14 ; CHECK: %sum2 = add i32 %sum1, %phi3 15 ; CHECK-NEXT: --> {20,+,6}<%loop1> 16 ; CHECK: %sum3 = add i32 %phi4, %phi5 17 ; CHECK-NEXT: --> {116,+,3}<%loop2> 18 ; CHECK: %sum4 = add i32 %sum3, %phi6 19 ; CHECK-NEXT: --> {159,+,6}<%loop2> 20 ; CHECK: %s1 = add i32 %phi1, %phi4 21 ; CHECK-NEXT: --> {{{{}}73,+,1}<%loop1>,+,1}<%loop2> 22 ; CHECK: %s2 = add i32 %phi5, %phi2 23 ; CHECK-NEXT: --> {{{{}}57,+,2}<%loop1>,+,2}<%loop2> 24 ; CHECK: %s3 = add i32 %sum1, %sum3 25 ; CHECK-NEXT: --> {{{{}}130,+,3}<%loop1>,+,3}<%loop2> 26 ; CHECK: %s4 = add i32 %sum4, %sum2 27 ; CHECK-NEXT: --> {{{{}}179,+,6}<%loop1>,+,6}<%loop2> 28 ; CHECK: %s5 = add i32 %phi3, %sum3 29 ; CHECK-NEXT: --> {{{{}}122,+,3}<%loop1>,+,3}<%loop2> 30 ; CHECK: %s6 = add i32 %sum2, %phi6 31 ; CHECK-NEXT: --> {{{{}}63,+,6}<%loop1>,+,3}<%loop2> 32 33 entry: 34 br label %loop1 35 36 loop1: 37 %phi1 = phi i32 [ 10, %entry ], [ %phi1.inc, %loop1 ] 38 %phi2 = phi i32 [ 4, %entry ], [ %phi2.inc, %loop1 ] 39 %phi3 = phi i32 [ 6, %entry ], [ %phi3.inc, %loop1 ] 40 %phi1.inc = add i32 %phi1, 1 41 %phi2.inc = add i32 %phi2, 2 42 %phi3.inc = add i32 %phi3, 3 43 %sum1 = add i32 %phi1, %phi2 44 %sum2 = add i32 %sum1, %phi3 45 %cond1 = icmp ult i32 %sum2, 1000 46 br i1 %cond1, label %loop1, label %loop2 47 48 loop2: 49 %phi4 = phi i32 [ 63, %loop1 ], [ %phi4.inc, %loop2 ] 50 %phi5 = phi i32 [ 53, %loop1 ], [ %phi5.inc, %loop2 ] 51 %phi6 = phi i32 [ 43, %loop1 ], [ %phi6.inc, %loop2 ] 52 %phi4.inc = add i32 %phi4, 1 53 %phi5.inc = add i32 %phi5, 2 54 %phi6.inc = add i32 %phi6, 3 55 %sum3 = add i32 %phi4, %phi5 56 %sum4 = add i32 %sum3, %phi6 57 %cond2 = icmp ult i32 %sum4, 1000 58 br i1 %cond2, label %loop2, label %exit 59 60 exit: 61 %s1 = add i32 %phi1, %phi4 62 %s2 = add i32 %phi5, %phi2 63 %s3 = add i32 %sum1, %sum3 64 %s4 = add i32 %sum4, %sum2 65 %s5 = add i32 %phi3, %sum3 66 %s6 = add i32 %sum2, %phi6 67 ret void 68 } 69 70 ; Check that we can evaluate a sum of phis+invariants from two different loops 71 ; in any order. 72 73 define void @test_01(i32 %a, i32 %b) { 74 75 ; CHECK-LABEL: Classifying expressions for: @test_01 76 ; CHECK: %sum1 = add i32 %phi1, %phi2 77 ; CHECK-NEXT: --> {(%a + %b),+,3}<%loop1> 78 ; CHECK: %sum2 = add i32 %sum1, %phi3 79 ; CHECK-NEXT: --> {(6 + %a + %b),+,6}<%loop1> 80 ; CHECK: %is1 = add i32 %sum2, %a 81 ; CHECK-NEXT: --> {(6 + (2 * %a) + %b),+,6}<%loop1> 82 ; CHECK: %sum3 = add i32 %phi4, %phi5 83 ; CHECK-NEXT: --> {116,+,3}<%loop2> 84 ; CHECK: %sum4 = add i32 %sum3, %phi6 85 ; CHECK-NEXT: --> {159,+,6}<%loop2> 86 ; CHECK: %is2 = add i32 %sum4, %b 87 ; CHECK-NEXT: --> {(159 + %b),+,6}<%loop2> 88 ; CHECK: %ec2 = add i32 %is1, %is2 89 ; CHECK-NEXT: --> {{{{}}(165 + (2 * %a) + (2 * %b)),+,6}<%loop1>,+,6}<%loop2> 90 ; CHECK: %s1 = add i32 %phi1, %is1 91 ; CHECK-NEXT: --> {(6 + (3 * %a) + %b),+,7}<%loop1> 92 ; CHECK: %s2 = add i32 %is2, %phi4 93 ; CHECK-NEXT: --> {(222 + %b),+,7}<%loop2> 94 ; CHECK: %s3 = add i32 %is1, %phi5 95 ; CHECK-NEXT: --> {{{{}}(59 + (2 * %a) + %b),+,6}<%loop1>,+,2}<%loop2> 96 ; CHECK: %s4 = add i32 %phi2, %is2 97 ; CHECK-NEXT: --> {{{{}}(159 + (2 * %b)),+,2}<%loop1>,+,6}<%loop2> 98 ; CHECK: %s5 = add i32 %is1, %is2 99 ; CHECK-NEXT: --> {{{{}}(165 + (2 * %a) + (2 * %b)),+,6}<%loop1>,+,6}<%loop2> 100 ; CHECK: %s6 = add i32 %is2, %is1 101 ; CHECK-NEXT: --> {{{{}}(165 + (2 * %a) + (2 * %b)),+,6}<%loop1>,+,6}<%loop2> 102 103 entry: 104 br label %loop1 105 106 loop1: 107 %phi1 = phi i32 [ %a, %entry ], [ %phi1.inc, %loop1 ] 108 %phi2 = phi i32 [ %b, %entry ], [ %phi2.inc, %loop1 ] 109 %phi3 = phi i32 [ 6, %entry ], [ %phi3.inc, %loop1 ] 110 %phi1.inc = add i32 %phi1, 1 111 %phi2.inc = add i32 %phi2, 2 112 %phi3.inc = add i32 %phi3, 3 113 %sum1 = add i32 %phi1, %phi2 114 %sum2 = add i32 %sum1, %phi3 115 %is1 = add i32 %sum2, %a 116 %cond1 = icmp ult i32 %is1, 1000 117 br i1 %cond1, label %loop1, label %loop2 118 119 loop2: 120 %phi4 = phi i32 [ 63, %loop1 ], [ %phi4.inc, %loop2 ] 121 %phi5 = phi i32 [ 53, %loop1 ], [ %phi5.inc, %loop2 ] 122 %phi6 = phi i32 [ 43, %loop1 ], [ %phi6.inc, %loop2 ] 123 %phi4.inc = add i32 %phi4, 1 124 %phi5.inc = add i32 %phi5, 2 125 %phi6.inc = add i32 %phi6, 3 126 %sum3 = add i32 %phi4, %phi5 127 %sum4 = add i32 %sum3, %phi6 128 %is2 = add i32 %sum4, %b 129 %ec2 = add i32 %is1, %is2 130 %cond2 = icmp ult i32 %ec2, 1000 131 br i1 %cond2, label %loop2, label %exit 132 133 exit: 134 %s1 = add i32 %phi1, %is1 135 %s2 = add i32 %is2, %phi4 136 %s3 = add i32 %is1, %phi5 137 %s4 = add i32 %phi2, %is2 138 %s5 = add i32 %is1, %is2 139 %s6 = add i32 %is2, %is1 140 ret void 141 } 142 143 ; Check that we can correctly evaluate a sum of phis+variants from two different 144 ; loops in any order. 145 146 define void @test_02(i32 %a, i32 %b, i32* %p) { 147 148 ; CHECK-LABEL: Classifying expressions for: @test_02 149 ; CHECK: %sum1 = add i32 %phi1, %phi2 150 ; CHECK-NEXT: --> {(%a + %b),+,3}<%loop1> 151 ; CHECK: %sum2 = add i32 %sum1, %phi3 152 ; CHECK-NEXT: --> {(6 + %a + %b),+,6}<%loop1> 153 ; CHECK: %is1 = add i32 %sum2, %v1 154 ; CHECK-NEXT: --> ({(6 + %a + %b),+,6}<%loop1> + %v1) 155 ; CHECK: %sum3 = add i32 %phi4, %phi5 156 ; CHECK-NEXT: --> {(%a + %b),+,3}<%loop2> 157 ; CHECK: %sum4 = add i32 %sum3, %phi6 158 ; CHECK-NEXT: --> {(43 + %a + %b),+,6}<%loop2> 159 ; CHECK: %is2 = add i32 %sum4, %v2 160 ; CHECK-NEXT: --> ({(43 + %a + %b),+,6}<%loop2> + %v2) 161 ; CHECK: %is3 = add i32 %v1, %sum2 162 ; CHECK-NEXT: --> ({(6 + %a + %b),+,6}<%loop1> + %v1) 163 ; CHECK: %ec2 = add i32 %is1, %is3 164 ; CHECK-NEXT: --> (2 * ({(6 + %a + %b),+,6}<%loop1> + %v1)) 165 ; CHECK: %s1 = add i32 %phi1, %is1 166 ; CHECK-NEXT: --> ({(6 + (2 * %a) + %b),+,7}<%loop1> + %v1) 167 ; CHECK: %s2 = add i32 %is2, %phi4 168 ; CHECK-NEXT: --> ({(43 + (2 * %a) + %b),+,7}<%loop2> + %v2) 169 ; CHECK: %s3 = add i32 %is1, %phi5 170 ; CHECK-NEXT: --> {({(6 + (2 * %b) + %a),+,6}<%loop1> + %v1),+,2}<%loop2> 171 ; CHECK: %s4 = add i32 %phi2, %is2 172 ; CHECK-NEXT: --> ({{{{}}(43 + (2 * %b) + %a),+,2}<%loop1>,+,6}<%loop2> + %v2) 173 ; CHECK: %s5 = add i32 %is1, %is2 174 ; CHECK-NEXT: --> ({({(49 + (2 * %a) + (2 * %b)),+,6}<%loop1> + %v1),+,6}<%loop2> + %v2) 175 ; CHECK: %s6 = add i32 %is2, %is1 176 ; CHECK-NEXT: --> ({({(49 + (2 * %a) + (2 * %b)),+,6}<%loop1> + %v1),+,6}<%loop2> + %v2) 177 178 entry: 179 br label %loop1 180 181 loop1: 182 %phi1 = phi i32 [ %a, %entry ], [ %phi1.inc, %loop1 ] 183 %phi2 = phi i32 [ %b, %entry ], [ %phi2.inc, %loop1 ] 184 %phi3 = phi i32 [ 6, %entry ], [ %phi3.inc, %loop1 ] 185 %phi1.inc = add i32 %phi1, 1 186 %phi2.inc = add i32 %phi2, 2 187 %phi3.inc = add i32 %phi3, 3 188 %v1 = load i32, i32* %p 189 %sum1 = add i32 %phi1, %phi2 190 %sum2 = add i32 %sum1, %phi3 191 %is1 = add i32 %sum2, %v1 192 %cond1 = icmp ult i32 %is1, 1000 193 br i1 %cond1, label %loop1, label %loop2 194 195 loop2: 196 %phi4 = phi i32 [ %a, %loop1 ], [ %phi4.inc, %loop2 ] 197 %phi5 = phi i32 [ %b, %loop1 ], [ %phi5.inc, %loop2 ] 198 %phi6 = phi i32 [ 43, %loop1 ], [ %phi6.inc, %loop2 ] 199 %phi4.inc = add i32 %phi4, 1 200 %phi5.inc = add i32 %phi5, 2 201 %phi6.inc = add i32 %phi6, 3 202 %v2 = load i32, i32* %p 203 %sum3 = add i32 %phi4, %phi5 204 %sum4 = add i32 %sum3, %phi6 205 %is2 = add i32 %sum4, %v2 206 %is3 = add i32 %v1, %sum2 207 %ec2 = add i32 %is1, %is3 208 %cond2 = icmp ult i32 %ec2, 1000 209 br i1 %cond2, label %loop2, label %exit 210 211 exit: 212 %s1 = add i32 %phi1, %is1 213 %s2 = add i32 %is2, %phi4 214 %s3 = add i32 %is1, %phi5 215 %s4 = add i32 %phi2, %is2 216 %s5 = add i32 %is1, %is2 217 %s6 = add i32 %is2, %is1 218 ret void 219 } 220 221 ; Mix of previous use cases that demonstrates %s3 can be incorrectly treated as 222 ; a recurrence of loop1 because of operands order if we pick recurrencies in an 223 ; incorrect order. It also shows that we cannot safely fold v1 (SCEVUnknown) 224 ; because we cannot prove for sure that it doesn't use Phis of loop 2. 225 226 define void @test_03(i32 %a, i32 %b, i32 %c, i32* %p) { 227 228 ; CHECK-LABEL: Classifying expressions for: @test_03 229 ; CHECK: %v1 = load i32, i32* %p 230 ; CHECK-NEXT: --> %v1 231 ; CHECK: %s1 = add i32 %phi1, %v1 232 ; CHECK-NEXT: --> ({%a,+,1}<%loop1> + %v1) 233 ; CHECK: %s2 = add i32 %s1, %b 234 ; CHECK-NEXT: --> ({(%a + %b),+,1}<%loop1> + %v1) 235 ; CHECK: %s3 = add i32 %s2, %phi2 236 ; CHECK-NEXT: --> ({{{{}}((2 * %a) + %b),+,1}<%loop1>,+,2}<%loop2> + %v1) 237 238 entry: 239 br label %loop1 240 241 loop1: 242 %phi1 = phi i32 [ %a, %entry ], [ %phi1.inc, %loop1 ] 243 %phi1.inc = add i32 %phi1, 1 244 %cond1 = icmp ult i32 %phi1, %c 245 br i1 %cond1, label %loop1, label %loop2 246 247 loop2: 248 %phi2 = phi i32 [ %a, %loop1 ], [ %phi2.inc, %loop2 ] 249 %phi2.inc = add i32 %phi2, 2 250 %v1 = load i32, i32* %p 251 %s1 = add i32 %phi1, %v1 252 %s2 = add i32 %s1, %b 253 %s3 = add i32 %s2, %phi2 254 %cond2 = icmp ult i32 %s3, %c 255 br i1 %cond2, label %loop2, label %exit 256 257 exit: 258 259 ret void 260 } 261 262 ; Another mix of previous use cases that demonstrates that incorrect picking of 263 ; a loop for a recurrence may cause a crash of SCEV analysis. 264 define void @test_04() { 265 266 ; CHECK-LABEL: Classifying expressions for: @test_04 267 ; CHECK: %tmp = phi i64 [ 2, %bb ], [ %tmp4, %bb3 ] 268 ; CHECK-NEXT: --> {2,+,1}<nuw><nsw><%loop1> 269 ; CHECK: %tmp2 = trunc i64 %tmp to i32 270 ; CHECK-NEXT: --> {2,+,1}<%loop1> 271 ; CHECK: %tmp4 = add nuw nsw i64 %tmp, 1 272 ; CHECK-NEXT: --> {3,+,1}<nuw><%loop1> 273 ; CHECK: %tmp7 = phi i64 [ %tmp15, %loop2 ], [ 2, %loop1 ] 274 ; CHECK-NEXT: --> {2,+,1}<nuw><nsw><%loop2> 275 ; CHECK: %tmp10 = sub i64 %tmp9, %tmp7 276 ; CHECK-NEXT: --> ((sext i8 %tmp8 to i64) + {-2,+,-1}<nw><%loop2>) 277 ; CHECK: %tmp11 = add i64 %tmp10, undef 278 ; CHECK-NEXT: --> ((sext i8 %tmp8 to i64) + {(-2 + undef),+,-1}<nw><%loop2>) 279 ; CHECK: %tmp13 = trunc i64 %tmp11 to i32 280 ; CHECK-NEXT: --> ((sext i8 %tmp8 to i32) + {(-2 + (trunc i64 undef to i32)),+,-1}<%loop2>) 281 ; CHECK: %tmp14 = sub i32 %tmp13, %tmp2 282 ; `{{[{][{]}}` is the ugliness needed to match `{{` 283 ; CHECK-NEXT: --> ((sext i8 %tmp8 to i32) + {{[{][{]}}(-4 + (trunc i64 undef to i32)),+,-1}<%loop1>,+,-1}<%loop2>) 284 ; CHECK: %tmp15 = add nuw nsw i64 %tmp7, 1 285 ; CHECK-NEXT: --> {3,+,1}<nuw><nsw><%loop2> 286 287 bb: 288 br label %loop1 289 290 loop1: 291 %tmp = phi i64 [ 2, %bb ], [ %tmp4, %bb3 ] 292 %tmp2 = trunc i64 %tmp to i32 293 br i1 undef, label %loop2, label %bb3 294 295 bb3: 296 %tmp4 = add nuw nsw i64 %tmp, 1 297 br label %loop1 298 299 bb5: 300 ret void 301 302 loop2: 303 %tmp7 = phi i64 [ %tmp15, %loop2 ], [ 2, %loop1 ] 304 %tmp8 = load i8, i8 addrspace(1)* undef, align 1 305 %tmp9 = sext i8 %tmp8 to i64 306 %tmp10 = sub i64 %tmp9, %tmp7 307 %tmp11 = add i64 %tmp10, undef 308 %tmp13 = trunc i64 %tmp11 to i32 309 %tmp14 = sub i32 %tmp13, %tmp2 310 %tmp15 = add nuw nsw i64 %tmp7, 1 311 %tmp16 = icmp slt i64 %tmp15, %tmp 312 br i1 %tmp16, label %loop2, label %bb5 313 } 314 315 @A = weak global [1000 x i32] zeroinitializer, align 32 316 317 ; Demonstrate a situation when we can add two recs with different degrees from 318 ; the same loop. 319 define void @test_05(i32 %N) { 320 321 ; CHECK-LABEL: Classifying expressions for: @test_05 322 ; CHECK: %SQ = mul i32 %i.0, %i.0 323 ; CHECK-NEXT: --> {4,+,5,+,2}<%bb3> 324 ; CHECK: %tmp4 = mul i32 %i.0, 2 325 ; CHECK-NEXT: --> {4,+,2}<nuw><nsw><%bb3> 326 ; CHECK: %tmp5 = sub i32 %SQ, %tmp4 327 ; CHECK-NEXT: --> {0,+,3,+,2}<%bb3> 328 329 entry: 330 %"alloca point" = bitcast i32 0 to i32 ; <i32> [#uses=0] 331 br label %bb3 332 333 bb: ; preds = %bb3 334 %tmp = getelementptr [1000 x i32], [1000 x i32]* @A, i32 0, i32 %i.0 ; <i32*> [#uses=1] 335 store i32 123, i32* %tmp 336 %tmp2 = add i32 %i.0, 1 ; <i32> [#uses=1] 337 br label %bb3 338 339 bb3: ; preds = %bb, %entry 340 %i.0 = phi i32 [ 2, %entry ], [ %tmp2, %bb ] ; <i32> [#uses=3] 341 %SQ = mul i32 %i.0, %i.0 342 %tmp4 = mul i32 %i.0, 2 343 %tmp5 = sub i32 %SQ, %tmp4 344 %tmp3 = icmp sle i32 %tmp5, 9999 ; <i1> [#uses=1] 345 br i1 %tmp3, label %bb, label %bb5 346 347 bb5: ; preds = %bb3 348 br label %return 349 350 return: ; preds = %bb5 351 ret void 352 } 353 354 ; Check that we can add Phis from different loops with different nesting, nested 355 ; loop comes first. 356 define void @test_06() { 357 358 ; CHECK-LABEL: Classifying expressions for: @test_06 359 ; CHECK: %s1 = add i32 %phi1, %phi2 360 ; CHECK-NEXT: --> {{{{}}30,+,1}<%loop1>,+,2}<%loop2> 361 ; CHECK: %s2 = add i32 %phi2, %phi1 362 ; CHECK-NEXT: --> {{{{}}30,+,1}<%loop1>,+,2}<%loop2> 363 ; CHECK: %s3 = add i32 %phi1, %phi3 364 ; CHECK-NEXT: --> {{{{}}40,+,1}<%loop1>,+,3}<%loop3> 365 ; CHECK: %s4 = add i32 %phi3, %phi1 366 ; CHECK-NEXT: --> {{{{}}40,+,1}<%loop1>,+,3}<%loop3> 367 ; CHECK: %s5 = add i32 %phi2, %phi3 368 ; CHECK-NEXT: --> {{{{}}50,+,2}<%loop2>,+,3}<%loop3> 369 ; CHECK: %s6 = add i32 %phi3, %phi2 370 ; CHECK-NEXT: --> {{{{}}50,+,2}<%loop2>,+,3}<%loop3> 371 372 entry: 373 br label %loop1 374 375 loop1: 376 %phi1 = phi i32 [ 10, %entry ], [ %phi1.inc, %loop1.exit ] 377 br label %loop2 378 379 loop2: 380 %phi2 = phi i32 [ 20, %loop1 ], [ %phi2.inc, %loop2 ] 381 %phi2.inc = add i32 %phi2, 2 382 %cond2 = icmp ult i32 %phi2.inc, 1000 383 br i1 %cond2, label %loop2, label %loop1.exit 384 385 loop1.exit: 386 %phi1.inc = add i32 %phi1, 1 387 %cond1 = icmp ult i32 %phi1.inc, 1000 388 br i1 %cond1, label %loop1, label %loop3 389 390 loop3: 391 %phi3 = phi i32 [ 30, %loop1.exit ], [ %phi3.inc, %loop3 ] 392 %phi3.inc = add i32 %phi3, 3 393 %cond3 = icmp ult i32 %phi3.inc, 1000 394 br i1 %cond3, label %loop3, label %exit 395 396 exit: 397 %s1 = add i32 %phi1, %phi2 398 %s2 = add i32 %phi2, %phi1 399 %s3 = add i32 %phi1, %phi3 400 %s4 = add i32 %phi3, %phi1 401 %s5 = add i32 %phi2, %phi3 402 %s6 = add i32 %phi3, %phi2 403 ret void 404 } 405 406 ; Check that we can add Phis from different loops with different nesting, nested 407 ; loop comes second. 408 define void @test_07() { 409 410 ; CHECK-LABEL: Classifying expressions for: @test_07 411 ; CHECK: %s1 = add i32 %phi1, %phi2 412 ; CHECK-NEXT: --> {{{{}}30,+,1}<%loop1>,+,2}<%loop2> 413 ; CHECK: %s2 = add i32 %phi2, %phi1 414 ; CHECK-NEXT: --> {{{{}}30,+,1}<%loop1>,+,2}<%loop2> 415 ; CHECK: %s3 = add i32 %phi1, %phi3 416 ; CHECK-NEXT: --> {{{{}}40,+,3}<%loop3>,+,1}<%loop1> 417 ; CHECK: %s4 = add i32 %phi3, %phi1 418 ; CHECK-NEXT: --> {{{{}}40,+,3}<%loop3>,+,1}<%loop1> 419 ; CHECK: %s5 = add i32 %phi2, %phi3 420 ; CHECK-NEXT: --> {{{{}}50,+,3}<%loop3>,+,2}<%loop2> 421 ; CHECK: %s6 = add i32 %phi3, %phi2 422 ; CHECK-NEXT: --> {{{{}}50,+,3}<%loop3>,+,2}<%loop2> 423 424 entry: 425 br label %loop3 426 427 loop3: 428 %phi3 = phi i32 [ 30, %entry ], [ %phi3.inc, %loop3 ] 429 %phi3.inc = add i32 %phi3, 3 430 %cond3 = icmp ult i32 %phi3.inc, 1000 431 br i1 %cond3, label %loop3, label %loop1 432 433 loop1: 434 %phi1 = phi i32 [ 10, %loop3 ], [ %phi1.inc, %loop1.exit ] 435 br label %loop2 436 437 loop2: 438 %phi2 = phi i32 [ 20, %loop1 ], [ %phi2.inc, %loop2 ] 439 %phi2.inc = add i32 %phi2, 2 440 %cond2 = icmp ult i32 %phi2.inc, 1000 441 br i1 %cond2, label %loop2, label %loop1.exit 442 443 loop1.exit: 444 %phi1.inc = add i32 %phi1, 1 445 %cond1 = icmp ult i32 %phi1.inc, 1000 446 br i1 %cond1, label %exit, label %loop1 447 448 exit: 449 %s1 = add i32 %phi1, %phi2 450 %s2 = add i32 %phi2, %phi1 451 %s3 = add i32 %phi1, %phi3 452 %s4 = add i32 %phi3, %phi1 453 %s5 = add i32 %phi2, %phi3 454 %s6 = add i32 %phi3, %phi2 455 ret void 456 } 457 458 ; Make sure that a complicated Phi does not get folded with rec's start value 459 ; of a loop which is above. 460 define void @test_08() { 461 462 ; CHECK-LABEL: Classifying expressions for: @test_08 463 ; CHECK: %tmp11 = add i64 %iv.2.2, %iv.2.1 464 ; CHECK-NEXT: --> ({0,+,-1}<nsw><%loop_2> + %iv.2.1) 465 ; CHECK: %tmp12 = trunc i64 %tmp11 to i32 466 ; CHECK-NEXT: --> ((trunc i64 %iv.2.1 to i32) + {0,+,-1}<%loop_2>) 467 ; CHECK: %tmp14 = mul i32 %tmp12, %tmp7 468 ; CHECK-NEXT: --> (((trunc i64 %iv.2.1 to i32) + {0,+,-1}<%loop_2>) * {-1,+,-1}<%loop_1>) 469 ; CHECK: %tmp16 = mul i64 %iv.2.1, %iv.1.1 470 ; CHECK-NEXT: --> ({2,+,1}<nuw><nsw><%loop_1> * %iv.2.1) 471 472 entry: 473 br label %loop_1 474 475 loop_1: 476 %iv.1.1 = phi i64 [ 2, %entry ], [ %iv.1.1.next, %loop_1_back_branch ] 477 %iv.1.2 = phi i32 [ -1, %entry ], [ %iv.1.2.next, %loop_1_back_branch ] 478 br label %loop_1_exit 479 480 dead: 481 br label %loop_1_exit 482 483 loop_1_exit: 484 %tmp5 = icmp sgt i64 %iv.1.1, 2 485 br i1 %tmp5, label %loop_2_preheader, label %loop_1_back_branch 486 487 loop_1_back_branch: 488 %iv.1.1.next = add nuw nsw i64 %iv.1.1, 1 489 %iv.1.2.next = add nsw i32 %iv.1.2, 1 490 br label %loop_1 491 492 loop_2_preheader: 493 %tmp6 = sub i64 1, %iv.1.1 494 %tmp7 = trunc i64 %tmp6 to i32 495 br label %loop_2 496 497 loop_2: 498 %iv.2.1 = phi i64 [ 0, %loop_2_preheader ], [ %tmp16, %loop_2 ] 499 %iv.2.2 = phi i64 [ 0, %loop_2_preheader ], [ %iv.2.2.next, %loop_2 ] 500 %iv.2.3 = phi i64 [ 2, %loop_2_preheader ], [ %iv.2.3.next, %loop_2 ] 501 %tmp11 = add i64 %iv.2.2, %iv.2.1 502 %tmp12 = trunc i64 %tmp11 to i32 503 %tmp14 = mul i32 %tmp12, %tmp7 504 %tmp16 = mul i64 %iv.2.1, %iv.1.1 505 %iv.2.3.next = add nuw nsw i64 %iv.2.3, 1 506 %iv.2.2.next = add nsw i64 %iv.2.2, -1 507 %tmp17 = icmp slt i64 %iv.2.3.next, %iv.1.1 508 br i1 %tmp17, label %loop_2, label %exit 509 510 exit: 511 %tmp10 = add i32 %iv.1.2, 3 512 ret void 513 } 514 515 define i64 @test_09(i32 %param) { 516 517 ; CHECK-LABEL: Classifying expressions for: @test_09 518 ; CHECK: %iv1 = phi i64 [ %iv1.next, %guarded ], [ 0, %outer.loop ] 519 ; CHECK-NEXT: --> {0,+,1}<nuw><nsw><%loop1> 520 ; CHECK: %iv1.trunc = trunc i64 %iv1 to i32 521 ; CHECK-NEXT: --> {0,+,1}<%loop1> 522 ; CHECK: %iv1.next = add nuw nsw i64 %iv1, 1 523 ; CHECK-NEXT: --> {1,+,1}<nuw><nsw><%loop1> 524 ; CHECK: %iv2 = phi i32 [ %iv2.next, %loop2 ], [ %param, %loop2.preheader ] 525 ; CHECK-NEXT: --> {%param,+,1}<%loop2> 526 ; CHECK: %iv2.next = add i32 %iv2, 1 527 ; CHECK-NEXT: --> {(1 + %param),+,1}<%loop2> 528 ; CHECK: %iv2.ext = sext i32 %iv2.next to i64 529 ; CHECK-NEXT: --> (sext i32 {(1 + %param),+,1}<%loop2> to i64) 530 ; CHECK: %ret = mul i64 %iv1, %iv2.ext 531 ; CHECK-NEXT: --> ((sext i32 {(1 + %param),+,1}<%loop2> to i64) * {0,+,1}<nuw><nsw><%loop1>) 532 533 entry: 534 br label %outer.loop 535 536 outer.loop: ; preds = %loop2.exit, %entry 537 br label %loop1 538 539 loop1: ; preds = %guarded, %outer.loop 540 %iv1 = phi i64 [ %iv1.next, %guarded ], [ 0, %outer.loop ] 541 %iv1.trunc = trunc i64 %iv1 to i32 542 %cond1 = icmp ult i64 %iv1, 100 543 br i1 %cond1, label %guarded, label %deopt 544 545 guarded: ; preds = %loop1 546 %iv1.next = add nuw nsw i64 %iv1, 1 547 %tmp16 = icmp slt i32 %iv1.trunc, 2 548 br i1 %tmp16, label %loop1, label %loop2.preheader 549 550 deopt: ; preds = %loop1 551 unreachable 552 553 loop2.preheader: ; preds = %guarded 554 br label %loop2 555 556 loop2: ; preds = %loop2, %loop2.preheader 557 %iv2 = phi i32 [ %iv2.next, %loop2 ], [ %param, %loop2.preheader ] 558 %iv2.next = add i32 %iv2, 1 559 %cond2 = icmp slt i32 %iv2, %iv1.trunc 560 br i1 %cond2, label %loop2, label %exit 561 562 exit: ; preds = %loop2.exit 563 %iv2.ext = sext i32 %iv2.next to i64 564 %ret = mul i64 %iv1, %iv2.ext 565 ret i64 %ret 566 } 567 568 define i64 @test_10(i32 %param) { 569 570 ; CHECK-LABEL: Classifying expressions for: @test_10 571 ; CHECK: %uncle = phi i64 [ %uncle.outer.next, %uncle.loop.backedge ], [ 0, %outer.loop ] 572 ; CHECK-NEXT: --> {0,+,1}<%uncle.loop> 573 ; CHECK: %iv1 = phi i64 [ %iv1.next, %guarded ], [ 0, %uncle.loop ] 574 ; CHECK-NEXT: --> {0,+,1}<nuw><nsw><%loop1> 575 ; CHECK: %iv1.trunc = trunc i64 %iv1 to i32 576 ; CHECK-NEXT: --> {0,+,1}<%loop1> 577 ; CHECK: %iv1.next = add nuw nsw i64 %iv1, 1 578 ; CHECK-NEXT: --> {1,+,1}<nuw><nsw><%loop1> 579 ; CHECK: %uncle.outer.next = add i64 %uncle, 1 580 ; CHECK-NEXT: --> {1,+,1}<%uncle.loop> 581 ; CHECK: %iv2 = phi i32 [ %iv2.next, %loop2 ], [ %param, %loop2.preheader ] 582 ; CHECK-NEXT: --> {%param,+,1}<%loop2> 583 ; CHECK: %iv2.next = add i32 %iv2, 1 584 ; CHECK-NEXT: --> {(1 + %param),+,1}<%loop2> 585 ; CHECK: %iv2.ext = sext i32 %iv2.next to i64 586 ; CHECK-NEXT: --> (sext i32 {(1 + %param),+,1}<%loop2> to i64) 587 ; CHECK: %ret = mul i64 %iv1, %iv2.ext 588 ; CHECK-NEXT: --> ((sext i32 {(1 + %param),+,1}<%loop2> to i64) * {0,+,1}<nuw><nsw><%loop1>) 589 590 entry: 591 br label %outer.loop 592 593 outer.loop: ; preds = %entry 594 br label %uncle.loop 595 596 uncle.loop: ; preds = %uncle.loop.backedge, %outer.loop 597 %uncle = phi i64 [ %uncle.outer.next, %uncle.loop.backedge ], [ 0, %outer.loop ] 598 br label %loop1 599 600 loop1: ; preds = %guarded, %uncle.loop 601 %iv1 = phi i64 [ %iv1.next, %guarded ], [ 0, %uncle.loop ] 602 %iv1.trunc = trunc i64 %iv1 to i32 603 %cond1 = icmp ult i64 %iv1, 100 604 br i1 %cond1, label %guarded, label %deopt 605 606 guarded: ; preds = %loop1 607 %iv1.next = add nuw nsw i64 %iv1, 1 608 %tmp16 = icmp slt i32 %iv1.trunc, 2 609 br i1 %tmp16, label %loop1, label %uncle.loop.backedge 610 611 uncle.loop.backedge: ; preds = %guarded 612 %uncle.outer.next = add i64 %uncle, 1 613 %cond.uncle = icmp ult i64 %uncle, 120 614 br i1 %cond.uncle, label %loop2.preheader, label %uncle.loop 615 616 deopt: ; preds = %loop1 617 unreachable 618 619 loop2.preheader: ; preds = %uncle.loop.backedge 620 br label %loop2 621 622 loop2: ; preds = %loop2, %loop2.preheader 623 %iv2 = phi i32 [ %iv2.next, %loop2 ], [ %param, %loop2.preheader ] 624 %iv2.next = add i32 %iv2, 1 625 %cond2 = icmp slt i32 %iv2, %iv1.trunc 626 br i1 %cond2, label %loop2, label %exit 627 628 exit: ; preds = %loop2 629 %iv2.ext = sext i32 %iv2.next to i64 630 %ret = mul i64 %iv1, %iv2.ext 631 ret i64 %ret 632 } 633
