test/Transforms/LoopUnroll/runtime-loop-multiple-exits.ll

   1 ; RUN: opt < %s -loop-unroll -unroll-runtime=true -unroll-runtime-epilog=true -unroll-runtime-multi-exit=true -verify-loop-lcssa -verify-dom-info -verify-loop-info -S | FileCheck %s -check-prefix=EPILOG-NO-IC
   2 ; RUN: opt < %s -loop-unroll -unroll-runtime=true -unroll-runtime-epilog=true -unroll-runtime-multi-exit=true -verify-loop-lcssa -verify-dom-info -verify-loop-info -instcombine -S | FileCheck %s -check-prefix=EPILOG
   3 ; RUN: opt < %s -loop-unroll -unroll-runtime -unroll-count=2 -unroll-runtime-epilog=true -unroll-runtime-multi-exit=true -verify-loop-lcssa -verify-dom-info -verify-loop-info -instcombine
   4 ; RUN: opt < %s -loop-unroll -unroll-runtime=true -unroll-runtime-epilog=false -unroll-runtime-multi-exit=true -verify-loop-lcssa -verify-dom-info -verify-loop-info -instcombine -S | FileCheck %s -check-prefix=PROLOG
   5 ; RUN: opt < %s -loop-unroll -unroll-runtime -unroll-runtime-epilog=false -unroll-count=2 -unroll-runtime-multi-exit=true -verify-loop-lcssa -verify-dom-info -verify-loop-info -instcombine
   6
   7 ; REQUIRES: asserts
   8
   9 ; the third and fifth RUNs generate an epilog/prolog remainder block for all the test
  10 ; cases below (it does not generate a loop).
  11
  12 ; test with three exiting and three exit blocks.
  13 ; none of the exit blocks have successors
  14 define void @test1(i64 %trip, i1 %cond) {
  15 ; EPILOG: test1(
  16 ; EPILOG-NEXT:  entry:
  17 ; EPILOG-NEXT:    [[TMP0:%.*]] = add i64 [[TRIP:%.*]], -1
  18 ; EPILOG-NEXT:    [[XTRAITER:%.*]] = and i64 [[TRIP]], 7
  19 ; EPILOG-NEXT:    [[TMP1:%.*]] = icmp ult i64 [[TMP0]], 7
  20 ; EPILOG-NEXT:    br i1 [[TMP1]], label %exit2.loopexit.unr-lcssa, label [[ENTRY_NEW:%.*]]
  21 ; EPILOG:       entry.new:
  22 ; EPILOG-NEXT:    [[UNROLL_ITER:%.*]] = sub i64 [[TRIP]], [[XTRAITER]]
  23 ; EPILOG-NEXT:    br label [[LOOP_HEADER:%.*]]
  24 ; EPILOG:  loop_latch.epil:
  25 ; EPILOG-NEXT:     %epil.iter.sub = add i64 %epil.iter, -1
  26 ; EPILOG-NEXT:     %epil.iter.cmp = icmp eq i64 %epil.iter.sub, 0
  27 ; EPILOG-NEXT:     br i1 %epil.iter.cmp, label %exit2.loopexit.epilog-lcssa, label %loop_header.epil
  28 ; EPILOG:  loop_latch.7:
  29 ; EPILOG-NEXT:     %niter.nsub.7 = add i64 %niter, -8
  30 ; EPILOG-NEXT:     %niter.ncmp.7 = icmp eq i64 %niter.nsub.7, 0
  31 ; EPILOG-NEXT:     br i1 %niter.ncmp.7, label %exit2.loopexit.unr-lcssa.loopexit, label %loop_header
  32
  33 ; PROLOG: test1(
  34 ; PROLOG-NEXT:  entry:
  35 ; PROLOG-NEXT:    [[TMP0:%.*]] = add i64 [[TRIP:%.*]], -1
  36 ; PROLOG-NEXT:    [[XTRAITER:%.*]] = and i64 [[TRIP]], 7
  37 ; PROLOG-NEXT:    [[TMP1:%.*]] = icmp eq i64 [[XTRAITER]], 0
  38 ; PROLOG-NEXT:    br i1 [[TMP1]], label %loop_header.prol.loopexit, label %loop_header.prol.preheader
  39 ; PROLOG:       loop_header.prol:
  40 ; PROLOG-NEXT:    %iv.prol = phi i64 [ 0, %loop_header.prol.preheader ], [ %iv_next.prol, %loop_latch.prol ]
  41 ; PROLOG-NEXT:    %prol.iter = phi i64 [ [[XTRAITER]], %loop_header.prol.preheader ], [ %prol.iter.sub, %loop_latch.prol ]
  42 ; PROLOG-NEXT:    br i1 %cond, label %loop_latch.prol, label %loop_exiting_bb1.prol
  43 ; PROLOG:       loop_latch.prol:
  44 ; PROLOG-NEXT:    %iv_next.prol = add i64 %iv.prol, 1
  45 ; PROLOG-NEXT:    %prol.iter.sub = add i64 %prol.iter, -1
  46 ; PROLOG-NEXT:    %prol.iter.cmp = icmp eq i64 %prol.iter.sub, 0
  47 ; PROLOG-NEXT:    br i1 %prol.iter.cmp, label %loop_header.prol.loopexit.unr-lcssa, label %loop_header.prol
  48 ; PROLOG:  loop_latch.7:
  49 ; PROLOG-NEXT:     %iv_next.7 = add i64 %iv, 8
  50 ; PROLOG-NEXT:     %cmp.7 = icmp eq i64 %iv_next.7, %trip
  51 ; PROLOG-NEXT:     br i1 %cmp.7, label %exit2.loopexit.unr-lcssa, label %loop_header
  52 entry:
  53   br label %loop_header
  54
  55 loop_header:
  56   %iv = phi i64 [ 0, %entry ], [ %iv_next, %loop_latch ]
  57   br i1 %cond, label %loop_latch, label %loop_exiting_bb1
  58
  59 loop_exiting_bb1:
  60   br i1 false, label %loop_exiting_bb2, label %exit1
  61
  62 loop_exiting_bb2:
  63   br i1 false, label %loop_latch, label %exit3
  64
  65 exit3:
  66   ret void
  67
  68 loop_latch:
  69   %iv_next = add i64 %iv, 1
  70   %cmp = icmp ne i64 %iv_next, %trip
  71   br i1 %cmp, label %loop_header, label %exit2.loopexit
  72
  73 exit1:
  74  ret void
  75
  76 exit2.loopexit:
  77   ret void
  78 }
  79
  80
  81 ; test with three exiting and two exit blocks.
  82 ; The non-latch exit block has 2 unique predecessors.
  83 ; There are 2 values passed to the exit blocks that are calculated at every iteration.
  84 ; %sum.02 and %add. Both of these are incoming values for phi from every exiting
  85 ; unrolled block.
  86 define i32 @test2(i32* nocapture %a, i64 %n) {
  87 ; EPILOG: test2(
  88 ; EPILOG: for.exit2.loopexit:
  89 ; EPILOG-NEXT:    %retval.ph = phi i32 [ 42, %for.exiting_block ], [ %sum.02, %header ], [ %add, %for.body ], [ 42, %for.exiting_block.1 ], [ %add.1, %for.body.1 ], [ 42, %for.exiting_block.2 ], [ %add.2, %for.body.2 ], [ 42, %for.exiting_block.3 ],
  90 ; EPILOG-NEXT:    br label %for.exit2
  91 ; EPILOG: for.exit2.loopexit2:
  92 ; EPILOG-NEXT:    %retval.ph3 = phi i32 [ 42, %for.exiting_block.epil ], [ %sum.02.epil, %header.epil ]
  93 ; EPILOG-NEXT:    br label %for.exit2
  94 ; EPILOG: for.exit2:
  95 ; EPILOG-NEXT:    %retval = phi i32 [ %retval.ph, %for.exit2.loopexit ], [ %retval.ph3, %for.exit2.loopexit2 ]
  96 ; EPILOG-NEXT:    ret i32 %retval
  97 ; EPILOG: %niter.nsub.7 = add i64 %niter, -8
  98
  99 ; PROLOG: test2(
 100 ; PROLOG: for.exit2.loopexit:
 101 ; PROLOG-NEXT:    %retval.ph = phi i32 [ 42, %for.exiting_block ], [ %sum.02, %header ], [ %add, %for.body ], [ 42, %for.exiting_block.1 ], [ %add.1, %for.body.1 ], [ 42, %for.exiting_block.2 ], [ %add.2, %for.body.2 ], [ 42, %for.exiting_block.3 ],
 102 ; PROLOG-NEXT:    br label %for.exit2
 103 ; PROLOG: for.exit2.loopexit1:
 104 ; PROLOG-NEXT:    %retval.ph2 = phi i32 [ 42, %for.exiting_block.prol ], [ %sum.02.prol, %header.prol ]
 105 ; PROLOG-NEXT:    br label %for.exit2
 106 ; PROLOG: for.exit2:
 107 ; PROLOG-NEXT:    %retval = phi i32 [ %retval.ph, %for.exit2.loopexit ], [ %retval.ph2, %for.exit2.loopexit1 ]
 108 ; PROLOG-NEXT:    ret i32 %retval
 109 ; PROLOG: %indvars.iv.next.7 = add i64 %indvars.iv, 8
 110
 111 entry:
 112   br label %header
 113
 114 header:
 115   %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %entry ]
 116   %sum.02 = phi i32 [ %add, %for.body ], [ 0, %entry ]
 117   br i1 false, label %for.exit2, label %for.exiting_block
 118
 119 for.exiting_block:
 120  %cmp = icmp eq i64 %n, 42
 121  br i1 %cmp, label %for.exit2, label %for.body
 122
 123 for.body:
 124   %arrayidx = getelementptr inbounds i32, i32* %a, i64 %indvars.iv
 125   %0 = load i32, i32* %arrayidx, align 4
 126   %add = add nsw i32 %0, %sum.02
 127   %indvars.iv.next = add i64 %indvars.iv, 1
 128   %exitcond = icmp eq i64 %indvars.iv.next, %n
 129   br i1 %exitcond, label %for.end, label %header
 130
 131 for.end:                                          ; preds = %for.body
 132   %sum.0.lcssa = phi i32 [ %add, %for.body ]
 133   ret i32 %sum.0.lcssa
 134
 135 for.exit2:
 136   %retval = phi i32 [ %sum.02, %header ], [ 42, %for.exiting_block ]
 137   ret i32 %retval
 138 }
 139
 140 ; test with two exiting and three exit blocks.
 141 ; the non-latch exiting block has a switch.
 142 define void @test3(i64 %trip, i64 %add) {
 143 ; EPILOG: test3(
 144 ; EPILOG-NEXT:  entry:
 145 ; EPILOG-NEXT:    [[TMP0:%.*]] = add i64 [[TRIP:%.*]], -1
 146 ; EPILOG-NEXT:    [[XTRAITER:%.*]] = and i64 [[TRIP]], 7
 147 ; EPILOG-NEXT:    [[TMP1:%.*]] = icmp ult i64 [[TMP0]], 7
 148 ; EPILOG-NEXT:    br i1 [[TMP1]], label %exit2.loopexit.unr-lcssa, label [[ENTRY_NEW:%.*]]
 149 ; EPILOG:       entry.new:
 150 ; EPILOG-NEXT:    %unroll_iter = sub i64 [[TRIP]], [[XTRAITER]]
 151 ; EPILOG-NEXT:    br label [[LOOP_HEADER:%.*]]
 152 ; EPILOG:  loop_header:
 153 ; EPILOG-NEXT:     %sum = phi i64 [ 0, %entry.new ], [ %sum.next.7, %loop_latch.7 ]
 154 ; EPILOG-NEXT:     %niter = phi i64 [ %unroll_iter, %entry.new ], [ %niter.nsub.7, %loop_latch.7 ]
 155 ; EPILOG:  loop_exiting_bb1.7:
 156 ; EPILOG-NEXT:     switch i64 %sum.next.6, label %loop_latch.7
 157 ; EPILOG:  loop_latch.7:
 158 ; EPILOG-NEXT:     %sum.next.7 = add i64 %sum.next.6, %add
 159 ; EPILOG-NEXT:     %niter.nsub.7 = add i64 %niter, -8
 160 ; EPILOG-NEXT:     %niter.ncmp.7 = icmp eq i64 %niter.nsub.7, 0
 161 ; EPILOG-NEXT:     br i1 %niter.ncmp.7, label %exit2.loopexit.unr-lcssa.loopexit, label %loop_header
 162
 163 ; PROLOG:  test3(
 164 ; PROLOG-NEXT:  entry:
 165 ; PROLOG-NEXT:    [[TMP0:%.*]] = add i64 [[TRIP:%.*]], -1
 166 ; PROLOG-NEXT:    [[XTRAITER:%.*]] = and i64 [[TRIP]], 7
 167 ; PROLOG-NEXT:    [[TMP1:%.*]] = icmp eq i64 [[XTRAITER]], 0
 168 ; PROLOG-NEXT:    br i1 [[TMP1]], label %loop_header.prol.loopexit, label %loop_header.prol.preheader
 169 ; PROLOG:  loop_header:
 170 ; PROLOG-NEXT:     %iv = phi i64 [ %iv.unr, %entry.new ], [ %iv_next.7, %loop_latch.7 ]
 171 ; PROLOG-NEXT:     %sum = phi i64 [ %sum.unr, %entry.new ], [ %sum.next.7, %loop_latch.7 ]
 172 ; PROLOG:  loop_exiting_bb1.7:
 173 ; PROLOG-NEXT:     switch i64 %sum.next.6, label %loop_latch.7
 174 ; PROLOG:  loop_latch.7:
 175 ; PROLOG-NEXT:     %iv_next.7 = add nuw nsw i64 %iv, 8
 176 ; PROLOG-NEXT:     %sum.next.7 = add i64 %sum.next.6, %add
 177 ; PROLOG-NEXT:     %cmp.7 = icmp eq i64 %iv_next.7, %trip
 178 ; PROLOG-NEXT:     br i1 %cmp.7, label %exit2.loopexit.unr-lcssa, label %loop_header
 179 entry:
 180   br label %loop_header
 181
 182 loop_header:
 183   %iv = phi i64 [ 0, %entry ], [ %iv_next, %loop_latch ]
 184   %sum = phi i64 [ 0, %entry ], [ %sum.next, %loop_latch ]
 185   br i1 undef, label %loop_latch, label %loop_exiting_bb1
 186
 187 loop_exiting_bb1:
 188    switch i64 %sum, label %loop_latch [
 189      i64 24, label %exit1
 190      i64 42, label %exit3
 191    ]
 192
 193 exit3:
 194   ret void
 195
 196 loop_latch:
 197   %iv_next = add nuw nsw i64 %iv, 1
 198   %sum.next = add i64 %sum, %add
 199   %cmp = icmp ne i64 %iv_next, %trip
 200   br i1 %cmp, label %loop_header, label %exit2.loopexit
 201
 202 exit1:
 203  ret void
 204
 205 exit2.loopexit:
 206   ret void
 207 }
 208
 209 ; FIXME: Support multiple exiting blocks to the same latch exit block.
 210 ; Three exiting blocks where header and latch exit to same LatchExit.
 211 define i32 @hdr_latch_same_exit(i32* nocapture %a, i64 %n, i1 %cond) {
 212 ; EPILOG: hdr_latch_same_exit(
 213 ; EPILOG-NOT: .unr
 214 ; EPILOG-NOT: .epil
 215
 216 ; PROLOG: hdr_latch_same_exit(
 217 ; PROLOG-NOT: .unr
 218 ; PROLOG-NOT: .prol
 219 entry:
 220   br label %header
 221
 222 header:
 223   %indvars.iv = phi i64 [ %indvars.iv.next, %latch ], [ 0, %entry ]
 224   %sum.02 = phi i32 [ %add, %latch ], [ 0, %entry ]
 225   br i1 %cond, label %latchExit, label %for.exiting_block
 226
 227 for.exiting_block:
 228  %cmp = icmp eq i64 %n, 42
 229  br i1 %cmp, label %for.exit2, label %latch
 230
 231 latch:                                         ; preds = %latch, %entry
 232   %arrayidx = getelementptr inbounds i32, i32* %a, i64 %indvars.iv
 233   %0 = load i32, i32* %arrayidx, align 4
 234   %add = add nsw i32 %0, %sum.02
 235   %indvars.iv.next = add i64 %indvars.iv, 1
 236   %exitcond = icmp eq i64 %indvars.iv.next, %n
 237   br i1 %exitcond, label %latchExit, label %header
 238
 239 latchExit:                                          ; preds = %latch, %entry
 240   %result = phi i32 [ 0, %header ], [ %add, %latch ]
 241   ret i32 %result
 242
 243 for.exit2:
 244   ret i32 42
 245 }
 246
 247 ; Two exiting blocks to latch where the exiting blocks are Latch and a
 248 ; non-header
 249 ; FIXME: We should unroll this loop.
 250 define i32 @otherblock_latch_same_exit(i32* nocapture %a, i64 %n, i1 %cond) {
 251 ; EPILOG: otherblock_latch_same_exit(
 252 ; EPILOG-NOT: .unr
 253 ; EPILOG-NOT: .epil
 254
 255 ; PROLOG: otherblock_latch_same_exit(
 256 ; PROLOG-NOT: .unr
 257 ; PROLOG-NOT: .prol
 258 entry:
 259   br label %header
 260
 261 header:
 262   %indvars.iv = phi i64 [ %indvars.iv.next, %latch ], [ 0, %entry ]
 263   %sum.02 = phi i32 [ %add, %latch ], [ 0, %entry ]
 264   br i1 %cond, label %for.exit2, label %for.exiting_block
 265
 266 for.exiting_block:
 267  %cmp = icmp eq i64 %n, 42
 268  br i1 %cmp, label %latchExit, label %latch
 269
 270 latch:                                         ; preds = %latch, %entry
 271   %arrayidx = getelementptr inbounds i32, i32* %a, i64 %indvars.iv
 272   %0 = load i32, i32* %arrayidx, align 4
 273   %add = add nsw i32 %0, %sum.02
 274   %indvars.iv.next = add i64 %indvars.iv, 1
 275   %exitcond = icmp eq i64 %indvars.iv.next, %n
 276   br i1 %exitcond, label %latchExit, label %header
 277
 278 latchExit:                                          ; preds = %latch, %entry
 279   %result = phi i32 [ 2, %for.exiting_block ], [ %add, %latch ]
 280   ret i32 %result
 281
 282 for.exit2:
 283   ret i32 42
 284 }
 285
 286 ; Two exiting blocks to latch where the exiting blocks are Latch and a
 287 ; non-header
 288 ; Same as above test except the incoming value for latch Phi is from the header
 289 ; FIXME: We should be able to runtime unroll.
 290 define i32 @otherblock_latch_same_exit2(i32* nocapture %a, i64 %n, i1 %cond) {
 291 ; EPILOG: otherblock_latch_same_exit2(
 292 ; EPILOG-NOT: .unr
 293 ; EPILOG-NOT: .epil
 294
 295 ; PROLOG: otherblock_latch_same_exit2(
 296 ; PROLOG-NOT: .unr
 297 ; PROLOG-NOT: .prol
 298 entry:
 299   br label %header
 300
 301 header:
 302   %indvars.iv = phi i64 [ %indvars.iv.next, %latch ], [ 0, %entry ]
 303   %sum.02 = phi i32 [ %add, %latch ], [ 0, %entry ]
 304   br i1 %cond, label %for.exit2, label %for.exiting_block
 305
 306 for.exiting_block:
 307  %cmp = icmp eq i64 %n, 42
 308  br i1 %cmp, label %latchExit, label %latch
 309
 310 latch:                                         ; preds = %latch, %entry
 311   %arrayidx = getelementptr inbounds i32, i32* %a, i64 %indvars.iv
 312   %0 = load i32, i32* %arrayidx, align 4
 313   %add = add nsw i32 %0, %sum.02
 314   %indvars.iv.next = add i64 %indvars.iv, 1
 315   %exitcond = icmp eq i64 %indvars.iv.next, %n
 316   br i1 %exitcond, label %latchExit, label %header
 317
 318 latchExit:                                          ; preds = %latch, %entry
 319   %result = phi i32 [ %sum.02, %for.exiting_block ], [ %add, %latch ]
 320   ret i32 %result
 321
 322 for.exit2:
 323   ret i32 42
 324 }
 325
 326 ; Two exiting blocks to latch where the exiting blocks are Latch and a
 327 ; non-header
 328 ; Same as above test except the incoming value for cloned latch Phi is from the
 329 ; for.exiting_block.
 330 ; FIXME: We should be able to runtime unroll.
 331 define i32 @otherblock_latch_same_exit3(i32* nocapture %a, i64 %n, i1 %cond) {
 332 ; EPILOG: otherblock_latch_same_exit3(
 333 ; EPILOG-NOT: .unr
 334 ; EPILOG-NOT: .epil
 335
 336 ; PROLOG: otherblock_latch_same_exit3(
 337 ; PROLOG-NOT: .unr
 338 ; PROLOG-NOT: .prol
 339 entry:
 340   br label %header
 341
 342 header:
 343   %indvars.iv = phi i64 [ %indvars.iv.next, %latch ], [ 0, %entry ]
 344   %sum.02 = phi i32 [ %add, %latch ], [ 0, %entry ]
 345   br i1 %cond, label %for.exit2, label %for.exiting_block
 346
 347 for.exiting_block:
 348  %arrayidx = getelementptr inbounds i32, i32* %a, i64 %indvars.iv
 349  %0 = load i32, i32* %arrayidx, align 4
 350  %add = add nsw i32 %0, %sum.02
 351  %cmp = icmp eq i64 %n, 42
 352  br i1 %cmp, label %latchExit, label %latch
 353
 354 latch:                                         ; preds = %latch, %entry
 355   %indvars.iv.next = add i64 %indvars.iv, 1
 356   %exitcond = icmp eq i64 %indvars.iv.next, %n
 357   br i1 %exitcond, label %latchExit, label %header
 358
 359 latchExit:                                          ; preds = %latch, %entry
 360   %result = phi i32 [ %sum.02, %for.exiting_block ], [ %add, %latch ]
 361   ret i32 %result
 362
 363 for.exit2:
 364   ret i32 42
 365 }
 366
 367 ; FIXME: Support multiple exiting blocks to the unique exit block (LatchExit).
 368 ; Only 2 blocks in loop: header and latch where both exit to same LatchExit.
 369 define void @unique_exit(i32 %arg) {
 370 ; EPILOG: unique_exit(
 371 ; EPILOG-NOT: .unr
 372 ; EPILOG-NOT: .epil
 373
 374 ; PROLOG: unique_exit(
 375 ; PROLOG-NOT: .unr
 376 ; PROLOG-NOT: .prol
 377 entry:
 378   %tmp = icmp sgt i32 undef, %arg
 379   br i1 %tmp, label %preheader, label %returnblock
 380
 381 preheader:                                 ; preds = %entry
 382   br label %header
 383
 384 header:                                           ; preds = %preheader, %latch
 385   %tmp4 = phi i32 [ %inc, %latch ], [ %arg, %preheader ]
 386   %inc = add nsw i32 %tmp4, 1
 387   br i1 true, label %latchExit, label %latch
 388
 389 latch:                                            ; preds = %header
 390   %cmp = icmp slt i32 %inc, undef
 391   br i1 %cmp, label %header, label %latchExit
 392
 393 latchExit:                                ; preds = %header, %latch
 394   %tmp2.ph = phi i32 [ %tmp4, %header ], [ -1, %latch ]
 395   br label %returnblock
 396
 397 returnblock:                                         ; preds = %latchExit, %entry
 398   %tmp2 = phi i32 [ -1, %entry ], [ %tmp2.ph, %latchExit ]
 399   ret void
 400 }
 401
 402 ; two exiting and two exit blocks.
 403 ; the non-latch exiting block has duplicate edges to the non-latch exit block.
 404 define i64 @test5(i64 %trip, i64 %add, i1 %cond) {
 405 ; EPILOG: test5(
 406 ; EPILOG:   exit1.loopexit:
 407 ; EPILOG-NEXT:      %result.ph = phi i64 [ %ivy, %loop_exiting ], [ %ivy, %loop_exiting ], [ %ivy.1, %loop_exiting.1 ], [ %ivy.1, %loop_exiting.1 ], [ %ivy.2, %loop_exiting.2 ],
 408 ; EPILOG-NEXT:      br label %exit1
 409 ; EPILOG:   exit1.loopexit2:
 410 ; EPILOG-NEXT:      %ivy.epil = add i64 %iv.epil, %add
 411 ; EPILOG-NEXT:      br label %exit1
 412 ; EPILOG:   exit1:
 413 ; EPILOG-NEXT:      %result = phi i64 [ %result.ph, %exit1.loopexit ], [ %ivy.epil, %exit1.loopexit2 ]
 414 ; EPILOG-NEXT:      ret i64 %result
 415 ; EPILOG:   loop_latch.7:
 416 ; EPILOG:      %niter.nsub.7 = add i64 %niter, -8
 417
 418 ; PROLOG: test5(
 419 ; PROLOG:   exit1.loopexit:
 420 ; PROLOG-NEXT:      %result.ph = phi i64 [ %ivy, %loop_exiting ], [ %ivy, %loop_exiting ], [ %ivy.1, %loop_exiting.1 ], [ %ivy.1, %loop_exiting.1 ], [ %ivy.2, %loop_exiting.2 ],
 421 ; PROLOG-NEXT:      br label %exit1
 422 ; PROLOG:   exit1.loopexit1:
 423 ; PROLOG-NEXT:      %ivy.prol = add i64 %iv.prol, %add
 424 ; PROLOG-NEXT:      br label %exit1
 425 ; PROLOG:   exit1:
 426 ; PROLOG-NEXT:      %result = phi i64 [ %result.ph, %exit1.loopexit ], [ %ivy.prol, %exit1.loopexit1 ]
 427 ; PROLOG-NEXT:      ret i64 %result
 428 ; PROLOG:   loop_latch.7:
 429 ; PROLOG:      %iv_next.7 = add nuw nsw i64 %iv, 8
 430 entry:
 431   br label %loop_header
 432
 433 loop_header:
 434   %iv = phi i64 [ 0, %entry ], [ %iv_next, %loop_latch ]
 435   %sum = phi i64 [ 0, %entry ], [ %sum.next, %loop_latch ]
 436   br i1 %cond, label %loop_latch, label %loop_exiting
 437
 438 loop_exiting:
 439    %ivy = add i64 %iv, %add
 440    switch i64 %sum, label %loop_latch [
 441      i64 24, label %exit1
 442      i64 42, label %exit1
 443    ]
 444
 445 loop_latch:
 446   %iv_next = add nuw nsw i64 %iv, 1
 447   %sum.next = add i64 %sum, %add
 448   %cmp = icmp ne i64 %iv_next, %trip
 449   br i1 %cmp, label %loop_header, label %latchexit
 450
 451 exit1:
 452  %result = phi i64 [ %ivy, %loop_exiting ], [ %ivy, %loop_exiting ]
 453  ret i64 %result
 454
 455 latchexit:
 456   ret i64 %sum.next
 457 }
 458
 459 ; test when exit blocks have successors.
 460 define i32 @test6(i32* nocapture %a, i64 %n, i1 %cond, i32 %x) {
 461 ; EPILOG: test6(
 462 ; EPILOG:   for.exit2.loopexit:
 463 ; EPILOG-NEXT:      %retval.ph = phi i32 [ 42, %for.exiting_block ], [ %sum.02, %header ], [ %add, %latch ], [ 42, %for.exiting_block.1 ], [ %add.1, %latch.1 ], [ 42, %for.exiting_block.2 ], [ %add.2, %latch.2 ],
 464 ; EPILOG-NEXT:      br label %for.exit2
 465 ; EPILOG:   for.exit2.loopexit2:
 466 ; EPILOG-NEXT:      %retval.ph3 = phi i32 [ 42, %for.exiting_block.epil ], [ %sum.02.epil, %header.epil ]
 467 ; EPILOG-NEXT:      br label %for.exit2
 468 ; EPILOG:   for.exit2:
 469 ; EPILOG-NEXT:      %retval = phi i32 [ %retval.ph, %for.exit2.loopexit ], [ %retval.ph3, %for.exit2.loopexit2 ]
 470 ; EPILOG-NEXT:      br i1 %cond, label %exit_true, label %exit_false
 471 ; EPILOG:   latch.7:
 472 ; EPILOG:           %niter.nsub.7 = add i64 %niter, -8
 473
 474 ; PROLOG: test6(
 475 ; PROLOG:   for.exit2.loopexit:
 476 ; PROLOG-NEXT:      %retval.ph = phi i32 [ 42, %for.exiting_block ], [ %sum.02, %header ], [ %add, %latch ], [ 42, %for.exiting_block.1 ], [ %add.1, %latch.1 ], [ 42, %for.exiting_block.2 ], [ %add.2, %latch.2 ],
 477 ; PROLOG-NEXT:      br label %for.exit2
 478 ; PROLOG:   for.exit2.loopexit1:
 479 ; PROLOG-NEXT:      %retval.ph2 = phi i32 [ 42, %for.exiting_block.prol ], [ %sum.02.prol, %header.prol ]
 480 ; PROLOG-NEXT:      br label %for.exit2
 481 ; PROLOG:   for.exit2:
 482 ; PROLOG-NEXT:      %retval = phi i32 [ %retval.ph, %for.exit2.loopexit ], [ %retval.ph2, %for.exit2.loopexit1 ]
 483 ; PROLOG-NEXT:      br i1 %cond, label %exit_true, label %exit_false
 484 ; PROLOG: latch.7:
 485 ; PROLOG:   %indvars.iv.next.7 = add i64 %indvars.iv, 8
 486 entry:
 487   br label %header
 488
 489 header:
 490   %indvars.iv = phi i64 [ %indvars.iv.next, %latch ], [ 0, %entry ]
 491   %sum.02 = phi i32 [ %add, %latch ], [ 0, %entry ]
 492   br i1 false, label %for.exit2, label %for.exiting_block
 493
 494 for.exiting_block:
 495  %cmp = icmp eq i64 %n, 42
 496  br i1 %cmp, label %for.exit2, label %latch
 497
 498 latch:
 499   %arrayidx = getelementptr inbounds i32, i32* %a, i64 %indvars.iv
 500   %load = load i32, i32* %arrayidx, align 4
 501   %add = add nsw i32 %load, %sum.02
 502   %indvars.iv.next = add i64 %indvars.iv, 1
 503   %exitcond = icmp eq i64 %indvars.iv.next, %n
 504   br i1 %exitcond, label %latch_exit, label %header
 505
 506 latch_exit:
 507   %sum.0.lcssa = phi i32 [ %add, %latch ]
 508   ret i32 %sum.0.lcssa
 509
 510 for.exit2:
 511   %retval = phi i32 [ %sum.02, %header ], [ 42, %for.exiting_block ]
 512   %addx = add i32 %retval, %x
 513   br i1 %cond, label %exit_true, label %exit_false
 514
 515 exit_true:
 516   ret i32 %retval
 517
 518 exit_false:
 519   ret i32 %addx
 520 }
 521
 522 ; test when value in exit block does not have VMap.
 523 define i32 @test7(i32 %arg, i32 %arg1, i32 %arg2) {
 524 ; EPILOG-NO-IC: test7(
 525 ; EPILOG-NO-IC: loopexit1.loopexit:
 526 ; EPILOG-NO-IC-NEXT:  %sext3.ph = phi i32 [ %shft, %header ], [ %shft, %latch ], [ %shft, %latch.1 ], [ %shft, %latch.2 ], [ %shft, %latch.3 ], [ %shft, %latch.4 ], [ %shft, %latch.5 ], [ %shft, %latch.6 ]
 527 ; EPILOG-NO-IC-NEXT:  br label %loopexit1
 528 ; EPILOG-NO-IC: loopexit1.loopexit1:
 529 ; EPILOG-NO-IC-NEXT:  %sext3.ph2 = phi i32 [ %shft, %header.epil ]
 530 ; EPILOG-NO-IC-NEXT:  br label %loopexit1
 531 ; EPILOG-NO-IC: loopexit1:
 532 ; EPILOG-NO-IC-NEXT:   %sext3 = phi i32 [ %sext3.ph, %loopexit1.loopexit ], [ %sext3.ph2, %loopexit1.loopexit1 ]
 533 bb:
 534   %tmp = icmp slt i32 undef, 2
 535   %sext = sext i32 undef to i64
 536   %shft = ashr exact i32 %arg, 16
 537   br i1 %tmp, label %loopexit2, label %preheader
 538
 539 preheader:                                              ; preds = %bb2
 540   br label %header
 541
 542 header:                                              ; preds = %latch, %preheader
 543   %tmp6 = phi i64 [ 1, %preheader ], [ %add, %latch ]
 544   br i1 false, label %loopexit1, label %latch
 545
 546 latch:                                              ; preds = %header
 547   %add = add nuw nsw i64 %tmp6, 1
 548   %tmp9 = icmp slt i64 %add, %sext
 549   br i1 %tmp9, label %header, label %latchexit
 550
 551 latchexit:                                             ; preds = %latch
 552   unreachable
 553
 554 loopexit2:                                             ; preds = %bb2
 555  ret i32 %shft
 556
 557 loopexit1:                                             ; preds = %header
 558   %sext3 = phi i32 [ %shft, %header ]
 559   ret i32 %sext3
 560 }
 561
 562 ; Nested loop and inner loop is unrolled
 563 ; FIXME: we cannot unroll with epilog remainder currently, because
 564 ; the outer loop does not contain the epilog preheader and epilog exit (while
 565 ; infact it should). This causes us to choke up on LCSSA form being incorrect in
 566 ; outer loop. However, the exit block where LCSSA fails, is infact still within
 567 ; the outer loop. For now, we just bail out in presence of outer loop and epilog
 568 ; loop is generated.
 569 ; The outer loop header is the preheader for the inner loop and the inner header
 570 ; branches back to the outer loop.
 571 define void @test8() {
 572 ; EPILOG: test8(
 573 ; EPILOG-NOT: niter
 574
 575 ; PROLOG: test8(
 576 ; PROLOG: outerloop:
 577 ; PROLOG-NEXT: phi i64 [ 3, %bb ], [ 0, %outerloop.loopexit ]
 578 ; PROLOG:      %lcmp.mod = icmp eq i64
 579 ; PROLOG-NEXT: br i1 %lcmp.mod, label %innerH.prol.loopexit, label %innerH.prol.preheader
 580 ; PROLOG: latch.6:
 581 ; PROLOG-NEXT: %tmp4.7 = add nuw nsw i64 %tmp3, 8
 582 ; PROLOG-NEXT: br i1 false, label %outerloop.loopexit.loopexit, label %latch.7
 583 ; PROLOG: latch.7
 584 ; PROLOG-NEXT: %tmp6.7 = icmp ult i64 %tmp4.7, 100
 585 ; PROLOG-NEXT: br i1 %tmp6.7, label %innerH, label %exit.unr-lcssa
 586 bb:
 587   br label %outerloop
 588
 589 outerloop:                                              ; preds = %innerH, %bb
 590   %tmp = phi i64 [ 3, %bb ], [ 0, %innerH ]
 591   br label %innerH
 592
 593 innerH:                                              ; preds = %latch, %outerloop
 594   %tmp3 = phi i64 [ %tmp4, %latch ], [ %tmp, %outerloop ]
 595   %tmp4 = add nuw nsw i64 %tmp3, 1
 596   br i1 false, label %outerloop, label %latch
 597
 598 latch:                                              ; preds = %innerH
 599   %tmp6 = icmp ult i64 %tmp4, 100
 600   br i1 %tmp6, label %innerH, label %exit
 601
 602 exit:                                              ; preds = %latch
 603   ret void
 604 }
 605
 606 declare i8 addrspace(1)* @foo(i32)
 607 ; inner loop prolog unrolled
 608 ; a value from outer loop is used in exit block of inner loop.
 609 ; Don't create VMap entries for such values (%trip).
 610 define i8 addrspace(1)* @test9(i8* nocapture readonly %arg, i32 %n) {
 611 ; PROLOG: test9(
 612 ; PROLOG: header.prol:
 613 ; PROLOG-NEXT: %phi.prol = phi i64 [ 0, %header.prol.preheader ], [ %iv.next.prol, %latch.prol ]
 614 ; PROLOG: latch.prol:
 615 ; PROLOG-NOT: trip
 616 ; PROLOG:     br i1 %prol.iter.cmp, label %header.prol.loopexit.unr-lcssa, label %header.prol
 617 bb:
 618   br label %outerloopHdr
 619
 620 outerloopHdr:                                              ; preds = %outerLatch, %bb
 621   %trip = add i32 %n, -1
 622   %outercnd = icmp slt i32 0, %trip
 623   br i1 %outercnd, label %preheader, label %outerLatch
 624
 625 preheader:                                              ; preds = %outerloopHdr
 626   %tmp4 = zext i32 0 to i64
 627   br label %header
 628
 629 header:                                              ; preds = %latch, %preheader
 630   %phi = phi i64 [ %tmp4, %preheader ], [ %iv.next, %latch ]
 631   %tmp7 = trunc i64 %phi to i32
 632   br i1 true, label %latch, label %innerexit
 633
 634 innerexit:                                              ; preds = %header
 635   %tmp9 = call i8 addrspace(1)* @foo(i32 %trip)
 636   ret i8 addrspace(1)* %tmp9
 637
 638 latch:                                             ; preds = %header
 639   %tmp11 = add nsw i32 %tmp7, 1
 640   %innercnd = icmp slt i32 %tmp11, %trip
 641   %iv.next = add nuw nsw i64 %phi, 1
 642   br i1 %innercnd, label %header, label %outerLatch
 643
 644 outerLatch:                                             ; preds = %latch, %outerloopHdr
 645   br label %outerloopHdr
 646 }