llvm/test/Transforms/LoopFlatten/loop-flatten.ll

   1 ; RUN: opt < %s -S -loop-flatten -verify-loop-info -verify-dom-info -verify-scev -verify | FileCheck %s
   2
   3 target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
   4
   5 ; CHECK-LABEL: test1
   6 ; Simple loop where the IV's is constant
   7 define i32 @test1(i32 %val, i16* nocapture %A) {
   8 entry:
   9   br label %for.body
  10 ; CHECK: entry:
  11 ; CHECK:   %flatten.tripcount = mul i32 20, 10
  12 ; CHECK:   br label %for.body
  13
  14 for.body:                                         ; preds = %entry, %for.inc6
  15   %i.018 = phi i32 [ 0, %entry ], [ %inc7, %for.inc6 ]
  16   %mul = mul nuw nsw i32 %i.018, 20
  17   br label %for.body3
  18 ; CHECK: for.body:
  19 ; CHECK:   %i.018 = phi i32 [ 0, %entry ], [ %inc7, %for.inc6 ]
  20 ; CHECK:   %mul = mul nuw nsw i32 %i.018, 20
  21 ; CHECK:   br label %for.body3
  22
  23 for.body3:                                        ; preds = %for.body, %for.body3
  24   %j.017 = phi i32 [ 0, %for.body ], [ %inc, %for.body3 ]
  25   %add = add nuw nsw i32 %j.017, %mul
  26   %arrayidx = getelementptr inbounds i16, i16* %A, i32 %add
  27   %0 = load i16, i16* %arrayidx, align 2
  28   %conv16 = zext i16 %0 to i32
  29   %add4 = add i32 %conv16, %val
  30   %conv5 = trunc i32 %add4 to i16
  31   store i16 %conv5, i16* %arrayidx, align 2
  32   %inc = add nuw nsw i32 %j.017, 1
  33   %exitcond = icmp ne i32 %inc, 20
  34   br i1 %exitcond, label %for.body3, label %for.inc6
  35 ; CHECK: for.body3:
  36 ; CHECK:   %j.017 = phi i32 [ 0, %for.body ]
  37 ; CHECK:   %add = add nuw nsw i32 %j.017, %mul
  38 ; CHECK:   %arrayidx = getelementptr inbounds i16, i16* %A, i32 %i.018
  39 ; CHECK:   %0 = load i16, i16* %arrayidx, align 2
  40 ; CHECK:   %conv16 = zext i16 %0 to i32
  41 ; CHECK:   %add4 = add i32 %conv16, %val
  42 ; CHECK:   %conv5 = trunc i32 %add4 to i16
  43 ; CHECK:   store i16 %conv5, i16* %arrayidx, align 2
  44 ; CHECK:   %inc = add nuw nsw i32 %j.017, 1
  45 ; CHECK:   %exitcond = icmp ne i32 %inc, 20
  46 ; CHECK:   br label %for.inc6
  47
  48 for.inc6:                                         ; preds = %for.body3
  49   %inc7 = add nuw nsw i32 %i.018, 1
  50   %exitcond19 = icmp ne i32 %inc7, 10
  51   br i1 %exitcond19, label %for.body, label %for.end8
  52 ; CHECK: for.inc6:
  53 ; CHECK:   %inc7 = add nuw nsw i32 %i.018, 1
  54 ; CHECK:   %exitcond19 = icmp ne i32 %inc7, %flatten.tripcount
  55 ; CHECK:   br i1 %exitcond19, label %for.body, label %for.end8
  56
  57 for.end8:                                         ; preds = %for.inc6
  58   ret i32 10
  59 }
  60
  61
  62 ; CHECK-LABEL: test2
  63 ; Same as above but non constant IV (which still cannot overflow)
  64 define i32 @test2(i8 zeroext %I, i32 %val, i16* nocapture %A) {
  65 entry:
  66   %conv = zext i8 %I to i32
  67   %cmp26 = icmp eq i8 %I, 0
  68   br i1 %cmp26, label %for.end13, label %for.body.lr.ph.split.us
  69
  70 for.body.lr.ph.split.us:                          ; preds = %entry
  71   br label %for.body.us
  72 ; CHECK: for.body.lr.ph.split.us:
  73 ; CHECK:   %flatten.tripcount = mul i32 %conv, %conv
  74 ; CHECK:   br label %for.body.us
  75
  76 for.body.us:                                      ; preds = %for.cond2.for.inc11_crit_edge.us, %for.body.lr.ph.split.us
  77   %i.027.us = phi i32 [ 0, %for.body.lr.ph.split.us ], [ %inc12.us, %for.cond2.for.inc11_crit_edge.us ]
  78   %mul.us = mul nuw nsw i32 %i.027.us, %conv
  79   br label %for.body6.us
  80 ; CHECK: for.body.us:
  81 ; CHECK:   %i.027.us = phi i32 [ 0, %for.body.lr.ph.split.us ], [ %inc12.us, %for.cond2.for.inc11_crit_edge.us ]
  82 ; CHECK:   %mul.us = mul nuw nsw i32 %i.027.us, %conv
  83 ; CHECK:   br label %for.body6.us
  84
  85 for.body6.us:                                     ; preds = %for.body.us, %for.body6.us
  86   %j.025.us = phi i32 [ 0, %for.body.us ], [ %inc.us, %for.body6.us ]
  87   %add.us = add nuw nsw i32 %j.025.us, %mul.us
  88   %arrayidx.us = getelementptr inbounds i16, i16* %A, i32 %add.us
  89   %0 = load i16, i16* %arrayidx.us, align 2
  90   %conv823.us = zext i16 %0 to i32
  91   %add9.us = add i32 %conv823.us, %val
  92   %conv10.us = trunc i32 %add9.us to i16
  93   store i16 %conv10.us, i16* %arrayidx.us, align 2
  94   %inc.us = add nuw nsw i32 %j.025.us, 1
  95   %exitcond = icmp ne i32 %inc.us, %conv
  96   br i1 %exitcond, label %for.body6.us, label %for.cond2.for.inc11_crit_edge.us
  97 ; CHECK: for.body6.us:
  98 ; CHECK:   %j.025.us = phi i32 [ 0, %for.body.us ]
  99 ; CHECK:   %add.us = add nuw nsw i32 %j.025.us, %mul.us
 100 ; CHECK:   %arrayidx.us = getelementptr inbounds i16, i16* %A, i32 %i.027.us
 101 ; CHECK:   %0 = load i16, i16* %arrayidx.us, align 2
 102 ; CHECK:   %conv823.us = zext i16 %0 to i32
 103 ; CHECK:   %add9.us = add i32 %conv823.us, %val
 104 ; CHECK:   %conv10.us = trunc i32 %add9.us to i16
 105 ; CHECK:   store i16 %conv10.us, i16* %arrayidx.us, align 2
 106 ; CHECK:   %inc.us = add nuw nsw i32 %j.025.us, 1
 107 ; CHECK:   %exitcond = icmp ne i32 %inc.us, %conv
 108 ; CHECK:   br label %for.cond2.for.inc11_crit_edge.us
 109
 110 for.cond2.for.inc11_crit_edge.us:                 ; preds = %for.body6.us
 111   %inc12.us = add nuw nsw i32 %i.027.us, 1
 112   %exitcond28 = icmp ne i32 %inc12.us, %conv
 113   br i1 %exitcond28, label %for.body.us, label %for.end13.loopexit
 114 ; CHECK: for.cond2.for.inc11_crit_edge.us:                 ; preds = %for.body6.us
 115 ; CHECK:   %inc12.us = add nuw nsw i32 %i.027.us, 1
 116 ; CHECK:   %exitcond28 = icmp ne i32 %inc12.us, %flatten.tripcount
 117 ; CHECK:   br i1 %exitcond28, label %for.body.us, label %for.end13.loopexit
 118
 119 for.end13.loopexit:                               ; preds = %for.cond2.for.inc11_crit_edge.us
 120   br label %for.end13
 121
 122 for.end13:                                        ; preds = %for.end13.loopexit, %entry
 123   %i.0.lcssa = phi i32 [ 0, %entry ], [ %conv, %for.end13.loopexit ]
 124   ret i32 %i.0.lcssa
 125 }
 126
 127
 128 ; CHECK-LABEL: test3
 129 ; Same as above, uses load to determine it can't overflow
 130 define i32 @test3(i32 %N, i32 %val, i16* nocapture %A) local_unnamed_addr #0 {
 131 entry:
 132   %cmp21 = icmp eq i32 %N, 0
 133   br i1 %cmp21, label %for.end8, label %for.body.lr.ph.split.us
 134
 135 for.body.lr.ph.split.us:                          ; preds = %entry
 136   br label %for.body.us
 137 ; CHECK: for.body.lr.ph.split.us:
 138 ; CHECK:   %flatten.tripcount = mul i32 %N, %N
 139 ; CHECK:   br label %for.body.us
 140
 141 for.body.us:                                      ; preds = %for.cond1.for.inc6_crit_edge.us, %for.body.lr.ph.split.us
 142   %i.022.us = phi i32 [ 0, %for.body.lr.ph.split.us ], [ %inc7.us, %for.cond1.for.inc6_crit_edge.us ]
 143   %mul.us = mul i32 %i.022.us, %N
 144   br label %for.body3.us
 145 ; CHECK: for.body.us:
 146 ; CHECK:   %i.022.us = phi i32 [ 0, %for.body.lr.ph.split.us ], [ %inc7.us, %for.cond1.for.inc6_crit_edge.us ]
 147 ; CHECK:   %mul.us = mul i32 %i.022.us, %N
 148 ; CHECK:   br label %for.body3.us
 149
 150 for.body3.us:                                     ; preds = %for.body.us, %for.body3.us
 151   %j.020.us = phi i32 [ 0, %for.body.us ], [ %inc.us, %for.body3.us ]
 152   %add.us = add i32 %j.020.us, %mul.us
 153   %arrayidx.us = getelementptr inbounds i16, i16* %A, i32 %add.us
 154   %0 = load i16, i16* %arrayidx.us, align 2
 155   %conv18.us = zext i16 %0 to i32
 156   %add4.us = add i32 %conv18.us, %val
 157   %conv5.us = trunc i32 %add4.us to i16
 158   store i16 %conv5.us, i16* %arrayidx.us, align 2
 159   %inc.us = add nuw i32 %j.020.us, 1
 160   %exitcond = icmp ne i32 %inc.us, %N
 161   br i1 %exitcond, label %for.body3.us, label %for.cond1.for.inc6_crit_edge.us
 162 ; CHECK: for.body3.us:
 163 ; CHECK:   %j.020.us = phi i32 [ 0, %for.body.us ]
 164 ; CHECK:   %add.us = add i32 %j.020.us, %mul.us
 165 ; CHECK:   %arrayidx.us = getelementptr inbounds i16, i16* %A, i32 %i.022.us
 166 ; CHECK:   %0 = load i16, i16* %arrayidx.us, align 2
 167 ; CHECK:   %conv18.us = zext i16 %0 to i32
 168 ; CHECK:   %add4.us = add i32 %conv18.us, %val
 169 ; CHECK:   %conv5.us = trunc i32 %add4.us to i16
 170 ; CHECK:   store i16 %conv5.us, i16* %arrayidx.us, align 2
 171 ; CHECK:   %inc.us = add nuw i32 %j.020.us, 1
 172 ; CHECK:   %exitcond = icmp ne i32 %inc.us, %N
 173 ; CHECK:   br label %for.cond1.for.inc6_crit_edge.us
 174
 175 for.cond1.for.inc6_crit_edge.us:                  ; preds = %for.body3.us
 176   %inc7.us = add nuw i32 %i.022.us, 1
 177   %exitcond23 = icmp ne i32 %inc7.us, %N
 178   br i1 %exitcond23, label %for.body.us, label %for.end8.loopexit
 179 ; CHECK: for.cond1.for.inc6_crit_edge.us:
 180 ; CHECK:   %inc7.us = add nuw i32 %i.022.us, 1
 181 ; CHECK:   %exitcond23 = icmp ne i32 %inc7.us, %flatten.tripcount
 182 ; CHECK:   br i1 %exitcond23, label %for.body.us, label %for.end8.loopexit
 183
 184 for.end8.loopexit:                                ; preds = %for.cond1.for.inc6_crit_edge.us
 185   br label %for.end8
 186
 187 for.end8:                                         ; preds = %for.end8.loopexit, %entry
 188   %i.0.lcssa = phi i32 [ 0, %entry ], [ %N, %for.end8.loopexit ]
 189   ret i32 %i.0.lcssa
 190 }
 191
 192
 193 ; CHECK-LABEL: test4
 194 ; Multiplication cannot overflow, so we can replace the original loop.
 195 define void @test4(i16 zeroext %N, i32* nocapture %C, i32* nocapture readonly %A, i32 %scale) {
 196 entry:
 197   %conv = zext i16 %N to i32
 198   %cmp30 = icmp eq i16 %N, 0
 199   br i1 %cmp30, label %for.cond.cleanup, label %for.body.lr.ph.split.us
 200 ; CHECK: entry:
 201 ; CHECK: %[[LIMIT:.*]] = zext i16 %N to i32
 202 ; CHECK: br i1 %{{.*}} label %for.cond.cleanup, label %for.body.lr.ph.split.us
 203
 204 for.body.lr.ph.split.us:                          ; preds = %entry
 205   br label %for.body.us
 206 ; CHECK: for.body.lr.ph.split.us:
 207 ; CHECK: %[[TRIPCOUNT:.*]] = mul i32 %[[LIMIT]], %[[LIMIT]]
 208 ; CHECK: br label %for.body.us
 209
 210 for.body.us:                                      ; preds = %for.cond2.for.cond.cleanup6_crit_edge.us, %for.body.lr.ph.split.us
 211   %i.031.us = phi i32 [ 0, %for.body.lr.ph.split.us ], [ %inc15.us, %for.cond2.for.cond.cleanup6_crit_edge.us ]
 212   %mul.us = mul nuw nsw i32 %i.031.us, %conv
 213   br label %for.body7.us
 214 ; CHECK: for.body.us:
 215 ; CHECK: %[[OUTER_IV:.*]] = phi i32
 216 ; CHECK: br label %for.body7.us
 217
 218 for.body7.us:                                     ; preds = %for.body.us, %for.body7.us
 219 ; CHECK: for.body7.us:
 220   %j.029.us = phi i32 [ 0, %for.body.us ], [ %inc.us, %for.body7.us ]
 221   %add.us = add nuw nsw i32 %j.029.us, %mul.us
 222   %arrayidx.us = getelementptr inbounds i32, i32* %A, i32 %add.us
 223 ; CHECK: getelementptr inbounds i32, i32* %A, i32 %[[OUTER_IV]]
 224   %0 = load i32, i32* %arrayidx.us, align 4
 225   %mul9.us = mul nsw i32 %0, %scale
 226 ; CHECK: getelementptr inbounds i32, i32* %C, i32 %[[OUTER_IV]]
 227   %arrayidx13.us = getelementptr inbounds i32, i32* %C, i32 %add.us
 228   store i32 %mul9.us, i32* %arrayidx13.us, align 4
 229   %inc.us = add nuw nsw i32 %j.029.us, 1
 230   %exitcond = icmp ne i32 %inc.us, %conv
 231   br i1 %exitcond, label %for.body7.us, label %for.cond2.for.cond.cleanup6_crit_edge.us
 232 ; CHECK: br label %for.cond2.for.cond.cleanup6_crit_edge.us
 233
 234 for.cond2.for.cond.cleanup6_crit_edge.us:         ; preds = %for.body7.us
 235   %inc15.us = add nuw nsw i32 %i.031.us, 1
 236   %exitcond32 = icmp ne i32 %inc15.us, %conv
 237   br i1 %exitcond32, label %for.body.us, label %for.cond.cleanup.loopexit
 238 ; CHECK: for.cond2.for.cond.cleanup6_crit_edge.us:
 239 ; CHECK: br i1 %exitcond32, label %for.body.us, label %for.cond.cleanup.loopexit
 240
 241 for.cond.cleanup.loopexit:                        ; preds = %for.cond2.for.cond.cleanup6_crit_edge.us
 242   br label %for.cond.cleanup
 243 ; CHECK: for.cond.cleanup.loopexit:
 244 ; CHECK: br label %for.cond.cleanup
 245
 246 for.cond.cleanup:                                 ; preds = %for.cond.cleanup.loopexit, %entry
 247   ret void
 248 ; CHECK: for.cond.cleanup:
 249 ; CHECK: ret void
 250 }
 251
 252
 253 ; CHECK-LABEL: test5
 254 define i32 @test5(i8 zeroext %I, i16 zeroext %J) {
 255 entry:
 256   %0 = lshr i8 %I, 1
 257   %div = zext i8 %0 to i32
 258   %cmp30 = icmp eq i8 %0, 0
 259   br i1 %cmp30, label %for.cond.cleanup, label %for.body.lr.ph
 260
 261 for.body.lr.ph:                                   ; preds = %entry
 262   %1 = lshr i16 %J, 1
 263   %div5 = zext i16 %1 to i32
 264   %cmp627 = icmp eq i16 %1, 0
 265   br i1 %cmp627, label %for.body.lr.ph.split, label %for.body.lr.ph.split.us
 266
 267 for.body.lr.ph.split.us:                          ; preds = %for.body.lr.ph
 268   br label %for.body.us
 269 ; CHECK: for.body.lr.ph.split.us:
 270 ; CHECK:   %flatten.tripcount = mul i32 %div5, %div
 271 ; CHECK:   br label %for.body.us
 272
 273 for.body.us:                                      ; preds = %for.cond3.for.cond.cleanup8_crit_edge.us, %for.body.lr.ph.split.us
 274   %i.032.us = phi i32 [ 0, %for.body.lr.ph.split.us ], [ %inc13.us, %for.cond3.for.cond.cleanup8_crit_edge.us ]
 275   %x.031.us = phi i32 [ 1, %for.body.lr.ph.split.us ], [ %xor.us.lcssa, %for.cond3.for.cond.cleanup8_crit_edge.us ]
 276   br label %for.body9.us
 277 ; CHECK: for.body.us:
 278 ; CHECK:   %i.032.us = phi i32 [ 0, %for.body.lr.ph.split.us ], [ %inc13.us, %for.cond3.for.cond.cleanup8_crit_edge.us ]
 279 ; CHECK:   %x.031.us = phi i32 [ 1, %for.body.lr.ph.split.us ], [ %xor.us.lcssa, %for.cond3.for.cond.cleanup8_crit_edge.us ]
 280 ; CHECK:   br label %for.body9.us
 281
 282 for.body9.us:                                     ; preds = %for.body.us, %for.body9.us
 283   %j.029.us = phi i32 [ 0, %for.body.us ], [ %inc.us, %for.body9.us ]
 284   %x.128.us = phi i32 [ %x.031.us, %for.body.us ], [ %xor.us, %for.body9.us ]
 285   %call.us = tail call i32 @func(i32 1)
 286   %sub.us = sub nsw i32 %call.us, %x.128.us
 287   %xor.us = xor i32 %sub.us, %x.128.us
 288   %inc.us = add nuw nsw i32 %j.029.us, 1
 289   %cmp6.us = icmp ult i32 %inc.us, %div5
 290   br i1 %cmp6.us, label %for.body9.us, label %for.cond3.for.cond.cleanup8_crit_edge.us
 291 ; CHECK: for.body9.us:
 292 ; CHECK:   %j.029.us = phi i32 [ 0, %for.body.us ]
 293 ; CHECK:   %x.128.us = phi i32 [ %x.031.us, %for.body.us ]
 294 ; CHECK:   %call.us = tail call i32 @func(i32 1)
 295 ; CHECK:   %sub.us = sub nsw i32 %call.us, %x.128.us
 296 ; CHECK:   %xor.us = xor i32 %sub.us, %x.128.us
 297 ; CHECK:   %inc.us = add nuw nsw i32 %j.029.us, 1
 298 ; CHECK:   %cmp6.us = icmp ult i32 %inc.us, %div5
 299 ; CHECK:   br label %for.cond3.for.cond.cleanup8_crit_edge.us
 300
 301 for.cond3.for.cond.cleanup8_crit_edge.us:         ; preds = %for.body9.us
 302   %xor.us.lcssa = phi i32 [ %xor.us, %for.body9.us ]
 303   %inc13.us = add nuw nsw i32 %i.032.us, 1
 304   %cmp.us = icmp ult i32 %inc13.us, %div
 305   br i1 %cmp.us, label %for.body.us, label %for.cond.cleanup.loopexit
 306 ; CHECK: for.cond3.for.cond.cleanup8_crit_edge.us:
 307 ; CHECK:   %xor.us.lcssa = phi i32 [ %xor.us, %for.body9.us ]
 308 ; CHECK:   %inc13.us = add nuw nsw i32 %i.032.us, 1
 309 ; CHECK:   %cmp.us = icmp ult i32 %inc13.us, %flatten.tripcount
 310 ; CHECK:   br i1 %cmp.us, label %for.body.us, label %for.cond.cleanup.loopexit
 311
 312 for.body.lr.ph.split:                             ; preds = %for.body.lr.ph
 313   br label %for.body
 314
 315 for.cond.cleanup.loopexit:                        ; preds = %for.cond3.for.cond.cleanup8_crit_edge.us
 316   %xor.us.lcssa.lcssa = phi i32 [ %xor.us.lcssa, %for.cond3.for.cond.cleanup8_crit_edge.us ]
 317   br label %for.cond.cleanup
 318
 319 for.cond.cleanup.loopexit34:                      ; preds = %for.body
 320   br label %for.cond.cleanup
 321
 322 for.cond.cleanup:                                 ; preds = %for.cond.cleanup.loopexit34, %for.cond.cleanup.loopexit, %entry
 323   %x.0.lcssa = phi i32 [ 1, %entry ], [ %xor.us.lcssa.lcssa, %for.cond.cleanup.loopexit ], [ 1, %for.cond.cleanup.loopexit34 ]
 324   ret i32 %x.0.lcssa
 325
 326 for.body:                                         ; preds = %for.body.lr.ph.split, %for.body
 327   %i.032 = phi i32 [ 0, %for.body.lr.ph.split ], [ %inc13, %for.body ]
 328   %inc13 = add nuw nsw i32 %i.032, 1
 329   %cmp = icmp ult i32 %inc13, %div
 330   br i1 %cmp, label %for.body, label %for.cond.cleanup.loopexit34
 331 }
 332
 333
 334 ; CHECK-LABEL: test6
 335 define i32 @test6(i8 zeroext %I, i16 zeroext %J) {
 336 entry:
 337   %0 = lshr i8 %I, 1
 338   %div = zext i8 %0 to i32
 339   %cmp30 = icmp eq i8 %0, 0
 340   br i1 %cmp30, label %for.cond.cleanup, label %for.body.lr.ph
 341
 342 for.body.lr.ph:                                   ; preds = %entry
 343   %1 = lshr i16 %J, 1
 344   %div5 = zext i16 %1 to i32
 345   %cmp627 = icmp eq i16 %1, 0
 346   br i1 %cmp627, label %for.body.lr.ph.split, label %for.body.lr.ph.split.us
 347
 348 for.body.lr.ph.split.us:                          ; preds = %for.body.lr.ph
 349   br label %for.body.us
 350 ; CHECK: for.body.lr.ph.split.us:
 351 ; CHECK:   %flatten.tripcount = mul i32 %div5, %div
 352 ; CHECK:   br label %for.body.us
 353
 354 for.body.us:                                      ; preds = %for.cond3.for.cond.cleanup8_crit_edge.us, %for.body.lr.ph.split.us
 355   %i.032.us = phi i32 [ 0, %for.body.lr.ph.split.us ], [ %inc13.us, %for.cond3.for.cond.cleanup8_crit_edge.us ]
 356   %x.031.us = phi i32 [ 1, %for.body.lr.ph.split.us ], [ %xor.us.lcssa, %for.cond3.for.cond.cleanup8_crit_edge.us ]
 357   %mul.us = mul nuw nsw i32 %i.032.us, %div5
 358   br label %for.body9.us
 359 ; CHECK: for.body.us:
 360 ; CHECK:   %i.032.us = phi i32 [ 0, %for.body.lr.ph.split.us ], [ %inc13.us, %for.cond3.for.cond.cleanup8_crit_edge.us ]
 361 ; CHECK:   %x.031.us = phi i32 [ 1, %for.body.lr.ph.split.us ], [ %xor.us.lcssa, %for.cond3.for.cond.cleanup8_crit_edge.us ]
 362 ; CHECK:   %mul.us = mul nuw nsw i32 %i.032.us, %div5
 363 ; CHECK:   br label %for.body9.us
 364
 365 for.body9.us:                                     ; preds = %for.body.us, %for.body9.us
 366   %j.029.us = phi i32 [ 0, %for.body.us ], [ %inc.us, %for.body9.us ]
 367   %x.128.us = phi i32 [ %x.031.us, %for.body.us ], [ %xor.us, %for.body9.us ]
 368   %add.us = add nuw nsw i32 %j.029.us, %mul.us
 369   %call.us = tail call i32 @func(i32 %add.us)
 370   %sub.us = sub nsw i32 %call.us, %x.128.us
 371   %xor.us = xor i32 %sub.us, %x.128.us
 372   %inc.us = add nuw nsw i32 %j.029.us, 1
 373   %cmp6.us = icmp ult i32 %inc.us, %div5
 374   br i1 %cmp6.us, label %for.body9.us, label %for.cond3.for.cond.cleanup8_crit_edge.us
 375 ; CHECK: for.body9.us:
 376 ; CHECK:   %j.029.us = phi i32 [ 0, %for.body.us ]
 377 ; CHECK:   %x.128.us = phi i32 [ %x.031.us, %for.body.us ]
 378 ; CHECK:   %add.us = add nuw nsw i32 %j.029.us, %mul.us
 379 ; CHECK:   %call.us = tail call i32 @func(i32 %i.032.us)
 380 ; CHECK:   %sub.us = sub nsw i32 %call.us, %x.128.us
 381 ; CHECK:   %xor.us = xor i32 %sub.us, %x.128.us
 382 ; CHECK:   %inc.us = add nuw nsw i32 %j.029.us, 1
 383 ; CHECK:   %cmp6.us = icmp ult i32 %inc.us, %div5
 384 ; CHECK:   br label %for.cond3.for.cond.cleanup8_crit_edge.us
 385
 386 for.cond3.for.cond.cleanup8_crit_edge.us:         ; preds = %for.body9.us
 387   %xor.us.lcssa = phi i32 [ %xor.us, %for.body9.us ]
 388   %inc13.us = add nuw nsw i32 %i.032.us, 1
 389   %cmp.us = icmp ult i32 %inc13.us, %div
 390   br i1 %cmp.us, label %for.body.us, label %for.cond.cleanup.loopexit
 391 ; CHECK: for.cond3.for.cond.cleanup8_crit_edge.us:
 392 ; CHECK:   %xor.us.lcssa = phi i32 [ %xor.us, %for.body9.us ]
 393 ; CHECK:   %inc13.us = add nuw nsw i32 %i.032.us, 1
 394 ; CHECK:   %cmp.us = icmp ult i32 %inc13.us, %flatten.tripcount
 395 ; CHECK:   br i1 %cmp.us, label %for.body.us, label %for.cond.cleanup.loopexit
 396
 397 for.body.lr.ph.split:                             ; preds = %for.body.lr.ph
 398   br label %for.body
 399
 400 for.cond.cleanup.loopexit:                        ; preds = %for.cond3.for.cond.cleanup8_crit_edge.us
 401   %xor.us.lcssa.lcssa = phi i32 [ %xor.us.lcssa, %for.cond3.for.cond.cleanup8_crit_edge.us ]
 402   br label %for.cond.cleanup
 403
 404 for.cond.cleanup.loopexit34:                      ; preds = %for.body
 405   br label %for.cond.cleanup
 406
 407 for.cond.cleanup:                                 ; preds = %for.cond.cleanup.loopexit34, %for.cond.cleanup.loopexit, %entry
 408   %x.0.lcssa = phi i32 [ 1, %entry ], [ %xor.us.lcssa.lcssa, %for.cond.cleanup.loopexit ], [ 1, %for.cond.cleanup.loopexit34 ]
 409   ret i32 %x.0.lcssa
 410
 411 for.body:                                         ; preds = %for.body.lr.ph.split, %for.body
 412   %i.032 = phi i32 [ 0, %for.body.lr.ph.split ], [ %inc13, %for.body ]
 413   %inc13 = add nuw nsw i32 %i.032, 1
 414   %cmp = icmp ult i32 %inc13, %div
 415   br i1 %cmp, label %for.body, label %for.cond.cleanup.loopexit34
 416 }
 417
 418 ; CHECK-LABEL: test7
 419 ; Various inner phis and conditions which we can still work with
 420 define signext i16 @test7(i32 %I, i32 %J, i32* nocapture readonly %C, i16 signext %limit) {
 421 entry:
 422   %cmp43 = icmp eq i32 %J, 0
 423   br i1 %cmp43, label %for.end17, label %for.body.lr.ph
 424
 425 for.body.lr.ph:                                   ; preds = %entry
 426   %conv = sext i16 %limit to i32
 427   br label %for.body.us
 428 ; CHECK: for.body.lr.ph:
 429 ; CHECK:   %conv = sext i16 %limit to i32
 430 ; CHECK:   %flatten.tripcount = mul i32 %J, %J
 431 ; CHECK:   br label %for.body.us
 432
 433 for.body.us:                                      ; preds = %for.cond1.for.inc15_crit_edge.us, %for.body.lr.ph
 434   %i.047.us = phi i32 [ 0, %for.body.lr.ph ], [ %inc16.us, %for.cond1.for.inc15_crit_edge.us ]
 435   %ret.046.us = phi i16 [ 0, %for.body.lr.ph ], [ %ret.2.us.lcssa, %for.cond1.for.inc15_crit_edge.us ]
 436   %prev.045.us = phi i32 [ 0, %for.body.lr.ph ], [ %.lcssa, %for.cond1.for.inc15_crit_edge.us ]
 437   %tmp.044.us = phi i32 [ 0, %for.body.lr.ph ], [ %tmp.2.us.lcssa, %for.cond1.for.inc15_crit_edge.us ]
 438   %mul.us = mul i32 %i.047.us, %J
 439   br label %for.body3.us
 440 ; CHECK: for.body.us:
 441 ; CHECK:   %i.047.us = phi i32 [ 0, %for.body.lr.ph ], [ %inc16.us, %for.cond1.for.inc15_crit_edge.us ]
 442 ; CHECK:   %ret.046.us = phi i16 [ 0, %for.body.lr.ph ], [ %ret.2.us.lcssa, %for.cond1.for.inc15_crit_edge.us ]
 443 ; CHECK:   %prev.045.us = phi i32 [ 0, %for.body.lr.ph ], [ %.lcssa, %for.cond1.for.inc15_crit_edge.us ]
 444 ; CHECK:   %tmp.044.us = phi i32 [ 0, %for.body.lr.ph ], [ %tmp.2.us.lcssa, %for.cond1.for.inc15_crit_edge.us ]
 445 ; CHECK:   %mul.us = mul i32 %i.047.us, %J
 446 ; CHECK:   br label %for.body3.us
 447
 448 for.body3.us:                                     ; preds = %for.body.us, %if.end.us
 449   %j.040.us = phi i32 [ 0, %for.body.us ], [ %inc.us, %if.end.us ]
 450   %ret.139.us = phi i16 [ %ret.046.us, %for.body.us ], [ %ret.2.us, %if.end.us ]
 451   %prev.138.us = phi i32 [ %prev.045.us, %for.body.us ], [ %0, %if.end.us ]
 452   %tmp.137.us = phi i32 [ %tmp.044.us, %for.body.us ], [ %tmp.2.us, %if.end.us ]
 453   %add.us = add i32 %j.040.us, %mul.us
 454   %arrayidx.us = getelementptr inbounds i32, i32* %C, i32 %add.us
 455   %0 = load i32, i32* %arrayidx.us, align 4
 456   %add4.us = add nsw i32 %0, %tmp.137.us
 457   %cmp5.us = icmp sgt i32 %add4.us, %conv
 458   br i1 %cmp5.us, label %if.then.us, label %if.else.us
 459 ; CHECK: for.body3.us:
 460 ; CHECK:   %j.040.us = phi i32 [ 0, %for.body.us ]
 461 ; CHECK:   %ret.139.us = phi i16 [ %ret.046.us, %for.body.us ]
 462 ; CHECK:   %prev.138.us = phi i32 [ %prev.045.us, %for.body.us ]
 463 ; CHECK:   %tmp.137.us = phi i32 [ %tmp.044.us, %for.body.us ]
 464 ; CHECK:   %add.us = add i32 %j.040.us, %mul.us
 465 ; CHECK:   %arrayidx.us = getelementptr inbounds i32, i32* %C, i32 %i.047.us
 466 ; CHECK:   %0 = load i32, i32* %arrayidx.us, align 4
 467 ; CHECK:   %add4.us = add nsw i32 %0, %tmp.137.us
 468 ; CHECK:   %cmp5.us = icmp sgt i32 %add4.us, %conv
 469 ; CHECK:   br i1 %cmp5.us, label %if.then.us, label %if.else.us
 470
 471 if.else.us:                                       ; preds = %for.body3.us
 472   %cmp10.us = icmp sgt i32 %0, %prev.138.us
 473   %cond.us = zext i1 %cmp10.us to i32
 474   %conv1235.us = zext i16 %ret.139.us to i32
 475   %add13.us = add nuw nsw i32 %cond.us, %conv1235.us
 476   br label %if.end.us
 477 ; CHECK: if.else.us:
 478 ; CHECK:   %cmp10.us = icmp sgt i32 %0, %prev.138.us
 479 ; CHECK:   %cond.us = zext i1 %cmp10.us to i32
 480 ; CHECK:   %conv1235.us = zext i16 %ret.139.us to i32
 481 ; CHECK:   %add13.us = add nuw nsw i32 %cond.us, %conv1235.us
 482 ; CHECK:   br label %if.end.us
 483
 484 if.then.us:                                       ; preds = %for.body3.us
 485   %conv7.us = sext i16 %ret.139.us to i32
 486   %add8.us = add nsw i32 %conv7.us, 10
 487   br label %if.end.us
 488 ; CHECK: if.then.us:
 489 ; CHECK:   %conv7.us = sext i16 %ret.139.us to i32
 490 ; CHECK:   %add8.us = add nsw i32 %conv7.us, 10
 491 ; CHECK:   br label %if.end.us
 492
 493 if.end.us:                                        ; preds = %if.then.us, %if.else.us
 494   %tmp.2.us = phi i32 [ 0, %if.then.us ], [ %add4.us, %if.else.us ]
 495   %ret.2.in.us = phi i32 [ %add8.us, %if.then.us ], [ %add13.us, %if.else.us ]
 496   %ret.2.us = trunc i32 %ret.2.in.us to i16
 497   %inc.us = add nuw i32 %j.040.us, 1
 498   %exitcond = icmp ne i32 %inc.us, %J
 499   br i1 %exitcond, label %for.body3.us, label %for.cond1.for.inc15_crit_edge.us
 500 ; CHECK: if.end.us:
 501 ; CHECK:   %tmp.2.us = phi i32 [ 0, %if.then.us ], [ %add4.us, %if.else.us ]
 502 ; CHECK:   %ret.2.in.us = phi i32 [ %add8.us, %if.then.us ], [ %add13.us, %if.else.us ]
 503 ; CHECK:   %ret.2.us = trunc i32 %ret.2.in.us to i16
 504 ; CHECK:   %inc.us = add nuw i32 %j.040.us, 1
 505 ; CHECK:   %exitcond = icmp ne i32 %inc.us, %J
 506 ; CHECK:   br label %for.cond1.for.inc15_crit_edge.us
 507
 508 for.cond1.for.inc15_crit_edge.us:                 ; preds = %if.end.us
 509   %tmp.2.us.lcssa = phi i32 [ %tmp.2.us, %if.end.us ]
 510   %ret.2.us.lcssa = phi i16 [ %ret.2.us, %if.end.us ]
 511   %.lcssa = phi i32 [ %0, %if.end.us ]
 512   %inc16.us = add nuw i32 %i.047.us, 1
 513   %exitcond49 = icmp ne i32 %inc16.us, %J
 514   br i1 %exitcond49, label %for.body.us, label %for.end17.loopexit
 515 ; CHECK: for.cond1.for.inc15_crit_edge.us:
 516 ; CHECK:   %tmp.2.us.lcssa = phi i32 [ %tmp.2.us, %if.end.us ]
 517 ; CHECK:   %ret.2.us.lcssa = phi i16 [ %ret.2.us, %if.end.us ]
 518 ; CHECK:   %.lcssa = phi i32 [ %0, %if.end.us ]
 519 ; CHECK:   %inc16.us = add nuw i32 %i.047.us, 1
 520 ; CHECK:   %exitcond49 = icmp ne i32 %inc16.us, %flatten.tripcount
 521 ; CHECK:   br i1 %exitcond49, label %for.body.us, label %for.end17.loopexit
 522
 523 for.end17.loopexit:                               ; preds = %for.cond1.for.inc15_crit_edge.us
 524   %ret.2.us.lcssa.lcssa = phi i16 [ %ret.2.us.lcssa, %for.cond1.for.inc15_crit_edge.us ]
 525   br label %for.end17
 526
 527 for.end17:                                        ; preds = %for.end17.loopexit, %entry
 528   %ret.0.lcssa = phi i16 [ 0, %entry ], [ %ret.2.us.lcssa.lcssa, %for.end17.loopexit ]
 529   ret i16 %ret.0.lcssa
 530 }
 531
 532 ; CHECK-LABEL: test8
 533 ; Same as test1, but with different continue block order
 534 ; (uses icmp eq and loops on false)
 535 define i32 @test8(i32 %val, i16* nocapture %A) {
 536 entry:
 537   br label %for.body
 538 ; CHECK: entry:
 539 ; CHECK:   %flatten.tripcount = mul i32 20, 10
 540 ; CHECK:   br label %for.body
 541
 542 for.body:                                         ; preds = %entry, %for.inc6
 543   %i.018 = phi i32 [ 0, %entry ], [ %inc7, %for.inc6 ]
 544   %mul = mul nuw nsw i32 %i.018, 20
 545   br label %for.body3
 546 ; CHECK: for.body:
 547 ; CHECK:   %i.018 = phi i32 [ 0, %entry ], [ %inc7, %for.inc6 ]
 548 ; CHECK:   %mul = mul nuw nsw i32 %i.018, 20
 549 ; CHECK:   br label %for.body3
 550
 551 for.body3:                                        ; preds = %for.body, %for.body3
 552   %j.017 = phi i32 [ 0, %for.body ], [ %inc, %for.body3 ]
 553   %add = add nuw nsw i32 %j.017, %mul
 554   %arrayidx = getelementptr inbounds i16, i16* %A, i32 %add
 555   %0 = load i16, i16* %arrayidx, align 2
 556   %conv16 = zext i16 %0 to i32
 557   %add4 = add i32 %conv16, %val
 558   %conv5 = trunc i32 %add4 to i16
 559   store i16 %conv5, i16* %arrayidx, align 2
 560   %inc = add nuw nsw i32 %j.017, 1
 561   %exitcond = icmp eq i32 %inc, 20
 562   br i1 %exitcond, label %for.inc6, label %for.body3
 563 ; CHECK: for.body3:
 564 ; CHECK:   %j.017 = phi i32 [ 0, %for.body ]
 565 ; CHECK:   %add = add nuw nsw i32 %j.017, %mul
 566 ; CHECK:   %arrayidx = getelementptr inbounds i16, i16* %A, i32 %i.018
 567 ; CHECK:   %0 = load i16, i16* %arrayidx, align 2
 568 ; CHECK:   %conv16 = zext i16 %0 to i32
 569 ; CHECK:   %add4 = add i32 %conv16, %val
 570 ; CHECK:   %conv5 = trunc i32 %add4 to i16
 571 ; CHECK:   store i16 %conv5, i16* %arrayidx, align 2
 572 ; CHECK:   %inc = add nuw nsw i32 %j.017, 1
 573 ; CHECK:   %exitcond = icmp eq i32 %inc, 20
 574 ; CHECK:   br label %for.inc6
 575
 576 for.inc6:                                         ; preds = %for.body3
 577   %inc7 = add nuw nsw i32 %i.018, 1
 578   %exitcond19 = icmp eq i32 %inc7, 10
 579   br i1 %exitcond19, label %for.end8, label %for.body
 580 ; CHECK: for.inc6:
 581 ; CHECK:   %inc7 = add nuw nsw i32 %i.018, 1
 582 ; CHECK:   %exitcond19 = icmp eq i32 %inc7, %flatten.tripcount
 583 ; CHECK:   br i1 %exitcond19, label %for.end8, label %for.body
 584
 585 for.end8:                                         ; preds = %for.inc6
 586   ret i32 10
 587 }
 588
 589 ; When the inner loop trip count is a constant and the step
 590 ; is 1, the InstCombine pass causes the transformation e.g.
 591 ; icmp ult i32 %inc, 20 -> icmp ult i32 %j, 19. This doesn't
 592 ; match the pattern (OuterPHI * InnerTripCount) + InnerPHI but
 593 ; we should still flatten the loop as the compare is removed
 594 ; later anyway.
 595 define i32 @test9(i32* nocapture %A) {
 596 entry:
 597   br label %for.cond1.preheader
 598 ; CHECK-LABEL: test9
 599 ; CHECK: entry:
 600 ; CHECK: %flatten.tripcount = mul i32 20, 11
 601 ; CHECK: br label %for.cond1.preheader
 602
 603 for.cond1.preheader:
 604   %i.017 = phi i32 [ 0, %entry ], [ %inc6, %for.cond.cleanup3 ]
 605   %mul = mul i32 %i.017, 20
 606   br label %for.body4
 607 ; CHECK: for.cond1.preheader:
 608 ; CHECK:   %i.017 = phi i32 [ 0, %entry ], [ %inc6, %for.cond.cleanup3 ]
 609 ; CHECK:   %mul = mul i32 %i.017, 20
 610 ; CHECK:   br label %for.body4
 611
 612 for.cond.cleanup3:
 613   %inc6 = add i32 %i.017, 1
 614   %cmp = icmp ult i32 %inc6, 11
 615   br i1 %cmp, label %for.cond1.preheader, label %for.cond.cleanup
 616 ; CHECK: for.cond.cleanup3:
 617 ; CHECK:   %inc6 = add i32 %i.017, 1
 618 ; CHECK:   %cmp = icmp ult i32 %inc6, %flatten.tripcount
 619 ; CHECK:   br i1 %cmp, label %for.cond1.preheader, label %for.cond.cleanup
 620
 621 for.body4:
 622   %j.016 = phi i32 [ 0, %for.cond1.preheader ], [ %inc, %for.body4 ]
 623   %add = add i32 %j.016, %mul
 624   %arrayidx = getelementptr inbounds i32, i32* %A, i32 %add
 625   store i32 30, i32* %arrayidx, align 4
 626   %inc = add nuw nsw i32 %j.016, 1
 627   %cmp2 = icmp ult i32 %j.016, 19
 628   br i1 %cmp2, label %for.body4, label %for.cond.cleanup3
 629 ; CHECK: for.body4
 630 ; CHECK:   %j.016 = phi i32 [ 0, %for.cond1.preheader ]
 631 ; CHECK:   %add = add i32 %j.016, %mul
 632 ; CHECK:   %arrayidx = getelementptr inbounds i32, i32* %A, i32 %i.017
 633 ; CHECK:   store i32 30, i32* %arrayidx, align 4
 634 ; CHECK:   %inc = add nuw nsw i32 %j.016, 1
 635 ; CHECK:   %cmp2 = icmp ult i32 %j.016, 19
 636 ; CHECK:   br label %for.cond.cleanup3
 637
 638 for.cond.cleanup:
 639   %0 = load i32, i32* %A, align 4
 640   ret i32 %0
 641 }
 642
 643 declare i32 @func(i32)
 644