; RUN: opt < %s -loop-deletion -verify-dom-info -S | FileCheck %s

; Checking that we can delete loops that are never executed.
; We do not change the constant conditional branch statement (where the not-taken target
; is the loop) to an unconditional one.

; delete the infinite loop because it is never executed.
define void @test1(i64 %n, i64 %m) nounwind {
; CHECK-LABEL: test1
; CHECK-LABEL: entry:
; CHECK-NEXT: br i1 true, label %return, label %bb.preheader
; CHECK-NOT: bb:
entry:
  br i1 true, label %return, label %bb

bb:
  %x.0 = phi i64 [ 0, %entry ], [ %t0, %bb ]
  %t0 = add i64 %x.0, 1
  %t1 = icmp slt i64 %x.0, %n
  %t3 = icmp sgt i64 %x.0, %m
  %t4 = and i1 %t1, %t3
  br i1 true, label %bb, label %return

return:
  ret void
}

; FIXME: We can delete this infinite loop. Currently we do not,
; because the infinite loop has no exit block.
define void @test2(i64 %n, i64 %m) nounwind {
; CHECK-LABEL: test2
; CHECK-LABEL: entry:
; CHECK-NEXT: br i1 true, label %return, label %bb.preheader
; CHECK-LABEL: bb:
; CHECK: br label %bb
entry:
  br i1 true, label %return, label %bb

bb:
  %x.0 = phi i64 [ 0, %entry ], [ %t0, %bb ]
  %t0 = add i64 %x.0, 1
  %t1 = icmp slt i64 %x.0, %n
  %t3 = icmp sgt i64 %x.0, %m
  %t4 = and i1 %t1, %t3
  br label %bb

return:
  ret void
}

; There are multiple exiting blocks and a single exit block. 
; Since it is a never executed loop, we do not care about the values
; from different exiting paths and we can
; delete the loop.
define i64 @test3(i64 %n, i64 %m, i64 %maybe_zero) nounwind {

; CHECK-NOT: bb:
; CHECK-NOT: bb2:
; CHECK-NOT: bb3:
; CHECK-LABEL: return.loopexit:
; CHECK-NEXT: %x.lcssa.ph = phi i64 [ undef, %bb.preheader ]
; CHECK-NEXT: br label %return
; CHECK-LABEL: return:
; CHECK-NEXT: %x.lcssa = phi i64 [ 20, %entry ], [ %x.lcssa.ph, %return.loopexit ]
; CHECK-NEXT: ret i64 %x.lcssa
entry:
  br i1 false, label %bb, label %return

bb:
  %x.0 = phi i64 [ 0, %entry ], [ %t0, %bb3 ]
  %t0 = add i64 %x.0, 1
  %t1 = icmp slt i64 %x.0, %n
  br i1 %t1, label %bb2, label %return

bb2:
  %t2 = icmp slt i64 %x.0, %m
  %unused1 = udiv i64 42, %maybe_zero
  br i1 %t2, label %bb3, label %return

bb3:
  %t3 = icmp slt i64 %x.0, %m
  %unused2 = sdiv i64 42, %maybe_zero
  br i1 %t3, label %bb, label %return

return:
; the only valid value fo x.lcssa is 20.
  %x.lcssa = phi i64 [ 12, %bb ], [ 14, %bb2 ], [ 16, %bb3 ], [20, %entry ]
  ret i64 %x.lcssa
}

; Cannot delete the loop, since it may be executed at runtime.
define void @test4(i64 %n, i64 %m, i1 %cond) {
; CHECK-LABEL: test4
; CHECK-LABEL: bb:
entry:
  br i1 %cond, label %looppred1, label %looppred2

looppred1:
  br i1 true, label %return, label %bb

looppred2:
  br i1 false, label %return, label %bb

bb:
  %x.0 = phi i64 [ 0, %looppred1 ], [ 1, %looppred2 ], [ %t0, %bb ]
  %t0 = add i64 %x.0, 1
  %t1 = icmp slt i64 %x.0, %n
  %t3 = icmp sgt i64 %x.0, %m
  %t4 = and i1 %t1, %t3
  br i1 true, label %bb, label %return

return:
  ret void
}

; multiple constant conditional branches with loop not-taken in all cases.
define void @test5(i64 %n, i64 %m, i1 %cond) nounwind {
; CHECK-LABEL: test5
; CHECK-LABEL: looppred1:
; CHECK-NEXT: br i1 true, label %return, label %bb.preheader
; CHECK-LABEL: looppred2:
; CHECK-NEXT: br i1 true, label %return, label %bb.preheader
; CHECK-NOT: bb:
entry:
  br i1 %cond, label %looppred1, label %looppred2

looppred1:
  br i1 true, label %return, label %bb

looppred2:
  br i1 true, label %return, label %bb

bb:
  %x.0 = phi i64 [ 0, %looppred1 ], [ 1, %looppred2 ], [ %t0, %bb ]
  %t0 = add i64 %x.0, 1
  %t1 = icmp slt i64 %x.0, %n
  %t3 = icmp sgt i64 %x.0, %m
  %t4 = and i1 %t1, %t3
  br i1 true, label %bb, label %return

return:
  ret void
}

; Don't delete this infinite loop because the loop 
; is executable at runtime.
define void @test6(i64 %n, i64 %m) nounwind {
; CHECK-LABEL: test6
; CHECK-LABEL: entry:
; CHECK-NEXT: br i1 true, label %bb.preheader, label %bb.preheader
; CHECK: bb:
entry:
  br i1 true, label %bb, label %bb

bb:
  %x.0 = phi i64 [ 0, %entry ], [ 0, %entry ], [ %t0, %bb ]
  %t0 = add i64 %x.0, 1
  %t1 = icmp slt i64 %x.0, %n
  %t3 = icmp sgt i64 %x.0, %m
  %t4 = and i1 %t1, %t3
  br i1 true, label %bb, label %return

return:
  ret void
}

declare i64 @foo(i64)
; The loop L2 is never executed and is a subloop, with an 
; exit block that branches back to parent loop.
; Here we can delete loop L2, while L1 still exists.
define i64 @test7(i64 %n) {
; CHECK-LABEL: test7
; CHECK-LABEL: L1:
; CHECK: br i1 true, label %L1Latch, label %L2.preheader
; CHECK-LABEL: L2.preheader:
; CHECK-NEXT: br label %L1Latch.loopexit
; CHECK-LABEL: L1Latch.loopexit:
; CHECK: br label %L1Latch
; CHECK-LABEL: L1Latch:
; CHECK-NEXT: %y = phi i64 [ %y.next, %L1 ], [ %y.L2.lcssa, %L1Latch.loopexit ]
; CHECK: br i1 %cond2, label %exit, label %L1
entry: 
  br label %L1

L1:
  %y.next = phi i64 [ 0, %entry ], [ %y.add, %L1Latch ]
  br i1 true, label %L1Latch, label %L2

L2:
  %x = phi i64 [ 0, %L1 ], [ %x.next, %L2 ]
  %x.next = add i64 %x, 1
  %y.L2 = call i64 @foo(i64 %x.next)
  %cond = icmp slt i64 %x.next, %n
  br i1 %cond, label %L2, label %L1Latch

L1Latch:
 %y = phi i64 [ %y.next, %L1 ], [ %y.L2, %L2 ]
 %y.add = add i64 %y, %n
 %cond2 = icmp eq i64 %y.add, 42
 br i1 %cond2, label %exit, label %L1

exit:
 ret i64 %y.add
}


; Show recursive deletion of loops. Since we start with subloops and progress outward 
; to parent loop, we first delete the loop L2. Now loop L1 becomes a non-loop since it's backedge
; from L2's preheader to L1's exit block is never taken. So, L1 gets deleted as well.
define void @test8(i64 %n) {
; CHECK-LABEL: test8
; CHECK-LABEL: entry:
; CHECK-NEXT: br label %exit
; CHECK-LABEL: exit:
; CHECK-NEXT: ret void
entry: 
  br label %L1

L1:
  br i1 true, label %exit, label %L2

L2:
  %x = phi i64 [ 0, %L1 ], [ %x.next, %L2 ]
  %x.next = add i64 %x, 1
  %y.L2 = call i64 @foo(i64 %x.next)
  %cond = icmp slt i64 %x.next, %n
  br i1 %cond, label %L2, label %L1

exit:
 ret void
}


; Delete a loop (L2) which has subloop (L3).
; Here we delete loop L2, but leave L3 as is.
; FIXME: Can delete L3 as well, by iteratively going backward through the single
; predecessor of L3 until we reach L1's block that guarantees L3 is never
; executed.
define void @test9(i64 %n) {
; CHECK-LABEL: test9
; CHECK-LABEL: L2.preheader:
; CHECK-NEXT: br label %L3.preheader
; CHECK-NOT: L2:
; CHECK-LABEL: L3.preheader:
; CHECK-NEXT: %y.L2.lcssa = phi i64 [ undef, %L2.preheader ]
; CHECK-NEXT: br label %L3
; CHECK-LABEL: L3:
; CHECK: br i1 %cond2, label %L3, label %L1.loopexit
entry: 
  br label %L1

L1:
  br i1 true, label %exit, label %L2

L2:
  %x = phi i64 [ 0, %L1 ], [ %x.next, %L2 ]
  %x.next = add i64 %x, 1
  %y.L2 = call i64 @foo(i64 %x.next)
  %cond = icmp slt i64 %x.next, %n
  br i1 %cond, label %L2, label %L3

L3: 
  %cond2 = icmp slt i64 %y.L2, %n
  br i1 %cond2, label %L3, label %L1

exit:
 ret void
}

; We cannot delete L3 because of call within it.
; Since L3 is not deleted, and entirely contained within L2, L2 is also not
; deleted.
; FIXME: We can delete unexecutable loops having
; subloops contained entirely within them.
define void @test10(i64 %n) {
; CHECK-LABEL: test10
; CHECK: L2:
; CHECK: L3:
entry: 
  br label %L1

L1:
  br i1 true, label %exit, label %L2

L2:
  %x = phi i64 [ 0, %L1 ], [ %x.next, %L3 ]
  %x.next = add i64 %x, 1
  %y.L2 = call i64 @foo(i64 %x.next)
  %cond = icmp slt i64 %x.next, %n
  br i1 %cond, label %L1, label %L3

L3:
  %y.L3 = phi i64 [ %y.L2, %L2 ], [ %y.L3.next, %L3 ]
  %y.L3.next = add i64 %y.L3, 1
  %dummy = call i64 @foo(i64 %y.L3.next)
  %cond2 = icmp slt i64 %y.L3, %n
  br i1 %cond2, label %L3, label %L2

exit:
 ret void
}

; same as test10, but L3 does not contain call.
; So, in the first iteration, all statements of L3 are made invariant, and L3 is
; deleted.
; In the next iteration, since L2 is never executed and has no subloops, we delete
; L2 as well. Finally, the outermost loop L1 is deleted.
define void @test11(i64 %n) {
; CHECK-LABEL: test11
; CHECK-LABEL: entry:
; CHECK-NEXT: br label %exit
; CHECK-LABEL: exit:
; CHECK-NEXT: ret void
entry: 
  br label %L1

L1:
  br i1 true, label %exit, label %L2

L2:
  %x = phi i64 [ 0, %L1 ], [ %x.next, %L3 ]
  %x.next = add i64 %x, 1
  %y.L2 = call i64 @foo(i64 %x.next)
  %cond = icmp slt i64 %x.next, %n
  br i1 %cond, label %L1, label %L3

L3: 
  %y.L3 = phi i64 [ %y.L2, %L2 ], [ %y.L3.next, %L3 ]
  %y.L3.next = add i64 %y.L3, 1
  %cond2 = icmp slt i64 %y.L3, %n
  br i1 %cond2, label %L3, label %L2

exit:
 ret void
}


; 2 edges from a single exiting block to the exit block.
define i64 @test12(i64 %n){
;CHECK-LABEL: @test12
; CHECK-NOT: L1:
; CHECK-NOT: L1Latch:
; CHECK-LABEL: L1.preheader:
; CHECK-NEXT:    br label %exit
; CHECK-LABEL: exit:
; CHECK-NEXT:    %y.phi = phi i64 [ undef, %L1.preheader ]
; CHECK-NEXT:    ret i64 %y.phi

entry:
  br i1 true, label %exit1, label %L1

exit1:
  ret i64 42

L1:                                               ; preds = %L1Latch, %entry
  %y.next = phi i64 [ 0, %entry ], [ %y.add, %L1Latch ]
  br i1 true, label %L1Latch, label %exit

L1Latch:                                          ; preds = %L1
  %y = phi i64 [ %y.next, %L1 ]
  %y.add = add i64 %y, %n
  %cond2 = icmp eq i64 %y.add, 42
  switch i64 %n, label %L1 [
    i64 10, label %exit
    i64 20, label %exit
  ]

exit:                                             ; preds = %L1Latch, %L1Latch
  %y.phi = phi i64 [ 10, %L1Latch ], [ 10, %L1Latch ], [ %y.next, %L1]
  ret i64 %y.phi
}

; multiple edges to exit block from the same exiting blocks
define i64 @test13(i64 %n) {
; CHECK-LABEL: @test13
; CHECK-NOT: L1:
; CHECK-NOT: L1Latch:
; CHECK-LABEL: L1.preheader:
; CHECK-NEXT:    br label %exit
; CHECK-LABEL: exit:
; CHECK-NEXT:    %y.phi = phi i64 [ undef, %L1.preheader ]
; CHECK-NEXT:    ret i64 %y.phi

entry:
  br i1 true, label %exit1, label %L1

exit1:
  ret i64 42

L1:                                               ; preds = %L1Latch, %entry
  %y.next = phi i64 [ 0, %entry ], [ %y.add, %L1Latch ]
  br i1 true, label %L1Block, label %exit

L1Block:                                          ; preds = %L1
  %y = phi i64 [ %y.next, %L1 ]
  %y.add = add i64 %y, %n
  %cond2 = icmp eq i64 %y.add, 42
  switch i64 %n, label %L1Latch [
    i64 10, label %exit
    i64 20, label %exit
  ]

L1Latch:
  switch i64 %n, label %L1 [
    i64 30, label %exit
    i64 40, label %exit
  ]

exit:                                             ; preds = %L1Block, %L1, %L1Latch
  %y.phi = phi i64 [ 10, %L1Block ], [ 10, %L1Block ], [ %y.next, %L1 ], [ 30, %L1Latch ], [ 30, %L1Latch ]
  ret i64 %y.phi
}