Page MenuHomePhabricator
Differential D93734 Diff 319447 llvm/test/Transforms/LoopDeletion/early-exits.ll

Changeset View

Standalone View

View Options

llvm/test/Transforms/LoopDeletion/early-exits.ll

  • This file was added.
; RUN: opt < %s -loop-deletion -S | FileCheck %s
;
; Test insertion of early exits from dead paths.
@g = external global i8
; Known trip count. If %loop branches to %latch, the loop is dead.
define void @f0() {
; CHECK-LABEL: @f0(
entry:
br label %loop
loop:
; CHECK-LABEL: loop:
; CHECK: br i1 %cmp, label %body, label %exit
%IV = phi i64 [ 0, %entry ], [ %next, %latch ]
%b = load i8, i8* @g
%cmp = icmp ne i8 %b, 0
br i1 %cmp, label %body, label %latch
body:
call void @foo()
br label %latch
latch:
%next = add i64 %IV, 1
%cmp2 = icmp ne i64 %IV, 128
br i1 %cmp2, label %loop, label %exit
exit:
ret void
}
; Loop has mustprogress attribute and @Rb_tree_increment is readonly.
; If %loop branches to %latch, the loop is dead.
%0 = type { i32, %0*, %0*, %0* }
define void @f1() {
; CHECK-LABEL: @f1(
entry:
br label %loop
loop: ; preds = %entry, %latch
; CHECK-LABEL: loop:
; CHECK: br i1 %i3.i3.not, label %body, label %exit
%i2.i2 = load i8, i8* inttoptr (i64 8 to i8*)
%0 = and i8 %i2.i2, 1
%i3.i3.not = icmp eq i8 %0, 0
br i1 %i3.i3.not, label %body, label %latch
body: ; preds = %loop
tail call void @foo()
br label %latch
latch: ; preds = %body, %loop
%i2.i = tail call %0* @Rb_tree_increment() #0
%i5.i.not = icmp eq %0* %i2.i, null
br i1 %i5.i.not, label %exit, label %loop, !llvm.loop !1
exit: ; preds = %latch
ret void
}
; Header has side-effects
define void @f2() {
; CHECK-LABEL: @f2(
entry:
br label %loop
loop:
; CHECK-LABEL: loop:
; CHECK: br i1 %cmp, label %body, label %latch
%IV = phi i64 [ 0, %entry ], [ %next, %latch ]
%b = load volatile i8, i8* @g
%cmp = icmp ne i8 %b, 0
br i1 %cmp, label %body, label %latch
body:
call void @foo()
br label %latch
latch:
%next = add i64 %IV, 1
%cmp2 = icmp ne i64 %IV, 128
br i1 %cmp2, label %loop, label %exit
exit:
ret void
}
; Latch has side-effects
define void @f3(i64* %dst) {
; CHECK-LABEL: @f3(
entry:
br label %loop
loop:
; CHECK-LABEL: loop:
; CHECK: br i1 %cmp, label %body, label %latch
%IV = phi i64 [ 0, %entry ], [ %next, %latch ]
%b = load i8, i8* @g
%cmp = icmp ne i8 %b, 0
br i1 %cmp, label %body, label %latch
body:
call void @foo()
br label %latch
latch:
%next = add i64 %IV, 1
store volatile i64 0, i64* %dst
%cmp2 = icmp ne i64 %IV, 128
br i1 %cmp2, label %loop, label %exit
exit:
ret void
}
; Condition is not loop-invariant
define void @f4(i64 %src) {
; CHECK-LABEL: @f4(
entry:
br label %loop
loop:
; CHECK-LABEL: loop:
; CHECK: br i1 %cmp, label %body, label %latch
%IV = phi i64 [ %src, %entry ], [ %next, %latch ]
%cmp = icmp eq i64 %IV, 0
br i1 %cmp, label %body, label %latch
body:
call void @foo()
br label %latch
latch:
%next = add i64 %IV, 1
%cmp2 = icmp ne i64 %IV, 128
br i1 %cmp2, label %loop, label %exit
exit:
ret void
}
; Header successors: one has side-effects.
define void @f5(i64 %src) {
; CHECK-LABEL: @f5(
entry:
br label %loop
loop:
; CHECK-LABEL: loop:
; CHECK: br i1 %cmp, label %exit, label %body1
%IV = phi i64 [ %src, %entry ], [ %next, %latch ]
%b = load i8, i8* @g
%cmp = icmp eq i8 %b, 0
br i1 %cmp, label %body0, label %body1
body0:
; CHECK-LABEL: body0:
; CHECK: br label %exit
br label %latch
body1:
; CHECK-LABEL: body1:
; CHECK: br i1 %cmp1, label %body2, label %latch
call void @foo()
%cmp1 = icmp ne i8 %b, 2
br i1 %cmp1, label %body2, label %latch
body2:
; CHECK-LABEL: body2:
; CHECK: br label %latch
call void @foo()
br label %latch
latch:
%next = add i64 %IV, 1
%cmp2 = icmp ne i64 %IV, 128
br i1 %cmp2, label %loop, label %exit
exit:
ret void
}
; Switch instruction and multiple latches: only early-exit from those with no
; side-effects.
define void @f6(i64 %src) mustprogress {
; CHECK-LABEL: @f6(
entry:
br label %loop
loop:
; CHECK-LABEL: loop:
; CHECK: switch i64 %src, label %exit [
; CHECK-NEXT: i64 2, label %latch2
; CHECK-NEXT: i64 4, label %exit
%IV = phi i64 [ %src, %entry ], [ %next1, %latch1 ],
[ %next2, %latch2 ], [ %next4, %latch4 ]
switch i64 %src, label %latch1 [ i64 2, label %latch2
i64 4, label %latch4 ]
latch1:
%next1 = add i64 %IV, 1
%cmp1 = icmp ne i64 %IV, 128
br i1 %cmp1, label %loop, label %exit
latch2:
call void @foo()
%next2 = add i64 %IV, 2
%cmp2 = icmp ne i64 %IV, 128
br i1 %cmp2, label %loop, label %exit
latch4:
%next4 = add i64 %IV, 4
%cmp4 = icmp ne i64 %IV, 128
br i1 %cmp4, label %loop, label %exit
exit:
ret void
}
; This loop has two exits which means deleteLoopIfDead() will bail. The loop
; will however be eliminated after inserting an early exit.
define void @f7(i1 %arg, i1 %arg2) mustprogress {
; CHECK-LABEL: @f7(
entry:
br label %loop
loop:
; CHECK-LABEL: loop:
; CHECK: br i1 %arg, label %exit1, label %exit0
br i1 %arg, label %exit1, label %body
body: ; preds = %bb1
br i1 %arg2, label %exit0, label %latch
exit0: ; preds = %bb2
unreachable
latch: ; preds = %bb2
br label %loop
exit1: ; preds = %bb1
ret void
}
; Another loop with two exits, containing just two dead blocks.
define void @f8() {
; CHECK-LABEL: @f8(
entry:
br label %header
header:
; CHECK-LABEL: header:
; CHECK: br i1 false, label %exit1, label %exit0
%i4 = phi i32 [ 0, %entry ], [ %i5, %latch ]
%i5 = add nuw i32 %i4, 1
br i1 false, label %exit1, label %latch
exit1:
unreachable
latch:
%i = icmp ult i32 %i5, undef
br i1 %i, label %header, label %exit0
exit0:
unreachable
}
; Exiting block with an edge to a no-side-effects latch
define void @f9(i64* %dst) {
; CHECK-LABEL: @f9(
entry:
br label %loop
loop:
; CHECK-LABEL: loop:
; CHECK: br i1 %cmp, label %body, label %body2
%IV = phi i64 [ 0, %entry ], [ %next, %latch ]
%b = load i8, i8* @g
%cmp = icmp ne i8 %b, 0
br i1 %cmp, label %body, label %body2
body:
call void @foo()
br label %latch
body2:
; CHECK-LABEL: body2:
; CHECK: br i1 false, label %latch, label %exit
br i1 false, label %latch, label %exit
latch:
%next = add i64 %IV, 1
store volatile i64 0, i64* %dst
%cmp2 = icmp ne i64 %IV, 128
br i1 %cmp2, label %loop, label %exit
exit:
ret void
}
; Branch from Top (not header) to a Bot (not latch)
define void @f10() {
; CHECK-LABEL: @f10(
entry:
br label %loop
loop:
; CHECK-LABEL: loop:
; CHECK: br i1 %cmp, label %body, label %body2
%IV = phi i64 [ 0, %entry ], [ %next, %latch ]
%b = load i8, i8* @g
%cmp = icmp ne i8 %b, 0
br i1 %cmp, label %body, label %body2
body:
call void @foo()
br label %latch
body2:
; CHECK-LABEL: body2:
; CHECK: br i1 false, label %body, label %exit
br i1 false, label %body, label %bot
bot:
; CHECK-LABEL: bot:
; CHECK: br label %exit
br label %latch
latch:
%next = add i64 %IV, 1
%cmp2 = icmp ne i64 %IV, 128
br i1 %cmp2, label %loop, label %exit
exit:
ret void
}
; Multiple exits, but only one on dead path.
define void @f11() {
; CHECK-LABEL: @f11(
entry:
br label %loop
loop:
; CHECK-LABEL: loop:
; CHECK: br i1 %cmp, label %body, label %exit
%IV = phi i64 [ 0, %entry ], [ %next, %latch ]
%b = load i8, i8* @g
%cmp = icmp ne i8 %b, 0
br i1 %cmp, label %body, label %bot1
body:
call void @foo()
br label %latch
bot0:
br i1 false, label %bot1, label %bot2
bot1:
; CHECK-LABEL: bot1:
; CHECK: br i1 false, label %exit, label %exit
br i1 false, label %latch, label %exit
bot2:
br i1 false, label %latch, label %exit2
latch:
%next = add i64 %IV, 1
%cmp2 = icmp ne i64 %IV, 128
br i1 %cmp2, label %loop, label %exit
exit:
ret void
exit2:
ret void
}
; Branches to two different blocks in Bot, two different and usable exit blocks.
define void @f12() mustprogress {
; CHECK-LABEL: @f12(
entry:
br label %loop
loop:
; CHECK-LABEL: loop:
; CHECK: br i1 %cmp, label %body, label %top1
%IV = phi i64 [ 0, %entry ], [ %next, %latch ]
%b = load i8, i8* @g
%cmp = icmp ne i8 %b, 0
br i1 %cmp, label %body, label %top1
body:
call void @foo()
br label %latch
top1:
; CHECK-LABEL: top1:
; CHECK: br i1 false, label %exit, label %exit2
br i1 false, label %bot1, label %bot2
bot1:
br i1 false, label %latch, label %exit
bot2:
br i1 false, label %latch, label %exit2
latch:
%next = add i64 %IV, 1
br label %loop
exit:
ret void
exit2:
ret void
}
; %loop branches to %bot1, but not a single exit block. %bot1 branches to %bot2,
; from wich there is only one exit block.
define void @f13() mustprogress {
; CHECK-LABEL: @f13(
entry:
br label %loop
loop:
; CHECK-LABEL: loop:
; CHECK: br i1 %cmp, label %body, label %bot1
%IV = phi i64 [ 0, %entry ], [ %next, %latch ]
%b = load i8, i8* @g
%cmp = icmp ne i8 %b, 0
br i1 %cmp, label %body, label %bot1
body:
call void @foo()
br label %latch
bot1:
; CHECK-LABEL: bot1:
; CHECK: br i1 false, label %exit2, label %exit
br i1 false, label %bot2, label %exit
bot2:
br i1 false, label %latch, label %exit2
latch:
%next = add i64 %IV, 1
br label %loop
exit:
ret void
exit2:
ret void
}
; Loop nest
define void @f14() mustprogress {
; CHECK-LABEL: @f14(
entry:
br label %loop1
loop1:
; CHECK-LABEL: loop1:
; CHECK: br i1 %cmp, label %loop2.preheader, label %exit1
%IV = phi i64 [ 0, %entry ], [ %next, %latch1 ]
%b = load i8, i8* @g
%cmp = icmp ne i8 %b, 0
br i1 %cmp, label %loop2.preheader, label %latch1
loop2.preheader:
br label %loop2
loop2:
; CHECK-LABEL: loop2:
; CHECK: br i1 false, label %body2, label %exit2
br i1 false, label %body2, label %latch2
body2:
call void @foo()
br label %latch2
latch2:
br i1 true, label %loop2, label %exit2
exit2:
br label %latch1
latch1:
%next = add i64 %IV, 1
%cmp2 = icmp ne i64 %IV, 128
br i1 %cmp2, label %loop1, label %exit1
exit1:
ret void
}
declare void @foo()
declare %0* @Rb_tree_increment()
attributes #0 = { nounwind readonly }
!1 = distinct !{!1, !2, !3}
!2 = !{!"llvm.loop.mustprogress"}
!3 = !{!"llvm.loop.unroll.disable"}