test/Analysis/ScalarEvolution/different-loops-recs.ll

   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 }