; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; RUN: opt -passes=dse -S %s | FileCheck %s
target datalayout = "e-m:e-i64:64-n32:64-v256:256:256-v512:512:512"
declare void @use(i32)
; Test cases with a loop carried dependence in %loop.2, where both %l.0 and
; %l.1 read the value stored by the previous iteration. Hence, the store in
; %loop.2 is not dead at the end of the function.
define void @test.1() {
; CHECK-LABEL: @test.1(
; CHECK-NEXT: entry:
; CHECK-NEXT: [[A:%.*]] = alloca [100 x i32], align 4
; CHECK-NEXT: br label [[LOOP_1:%.*]]
; CHECK: loop.1:
; CHECK-NEXT: [[IV_1:%.*]] = phi i64 [ 1, [[ENTRY:%.*]] ], [ [[IV_1_NEXT:%.*]], [[LOOP_1]] ]
; CHECK-NEXT: [[ARRAYIDX1:%.*]] = getelementptr inbounds [100 x i32], ptr [[A]], i64 0, i64 [[IV_1]]
; CHECK-NEXT: store i32 0, ptr [[ARRAYIDX1]], align 4
; CHECK-NEXT: [[IV_1_NEXT]] = add nsw i64 [[IV_1]], 1
; CHECK-NEXT: [[C_1:%.*]] = icmp slt i64 [[IV_1_NEXT]], 100
; CHECK-NEXT: br i1 [[C_1]], label [[LOOP_1]], label [[LOOP_2_PH:%.*]]
; CHECK: loop.2.ph:
; CHECK-NEXT: br label [[LOOP_2:%.*]]
; CHECK: loop.2:
; CHECK-NEXT: [[IV_2:%.*]] = phi i64 [ [[IV_2_NEXT:%.*]], [[LOOP_2]] ], [ 0, [[LOOP_2_PH]] ]
; CHECK-NEXT: [[PTR_IV_2:%.*]] = getelementptr inbounds [100 x i32], ptr [[A]], i64 0, i64 [[IV_2]]
; CHECK-NEXT: [[L_0:%.*]] = load i32, ptr [[PTR_IV_2]], align 4
; CHECK-NEXT: call void @use(i32 [[L_0]])
; CHECK-NEXT: [[ADD:%.*]] = add nsw i64 [[IV_2]], 1
; CHECK-NEXT: [[PTR_IV_2_ADD_1:%.*]] = getelementptr inbounds [100 x i32], ptr [[A]], i64 0, i64 [[ADD]]
; CHECK-NEXT: store i32 10, ptr [[PTR_IV_2_ADD_1]], align 4
; CHECK-NEXT: [[L_1:%.*]] = load i32, ptr [[PTR_IV_2]], align 4
; CHECK-NEXT: call void @use(i32 [[L_1]])
; CHECK-NEXT: [[IV_2_NEXT]] = add nsw i64 [[IV_2]], 1
; CHECK-NEXT: [[C_2:%.*]] = icmp slt i64 [[IV_2_NEXT]], 100
; CHECK-NEXT: br i1 [[C_2]], label [[LOOP_2]], label [[EXIT:%.*]]
; CHECK: exit:
; CHECK-NEXT: ret void
;
entry:
%A = alloca [100 x i32], align 4
br label %loop.1
loop.1:
%iv.1 = phi i64 [ 1, %entry ], [ %iv.1.next, %loop.1 ]
%arrayidx1 = getelementptr inbounds [100 x i32], ptr %A, i64 0, i64 %iv.1
store i32 0, ptr %arrayidx1, align 4
%iv.1.next = add nsw i64 %iv.1, 1
%c.1 = icmp slt i64 %iv.1.next, 100
br i1 %c.1, label %loop.1, label %loop.2.ph
loop.2.ph:
br label %loop.2
loop.2:
%iv.2 = phi i64 [ %iv.2.next, %loop.2 ], [ 0, %loop.2.ph ]
%ptr.iv.2 = getelementptr inbounds [100 x i32], ptr %A, i64 0, i64 %iv.2
%l.0 = load i32, ptr %ptr.iv.2, align 4
call void @use(i32 %l.0)
%add = add nsw i64 %iv.2, 1
%ptr.iv.2.add.1 = getelementptr inbounds [100 x i32], ptr %A, i64 0, i64 %add
store i32 10, ptr %ptr.iv.2.add.1, align 4
%l.1 = load i32, ptr %ptr.iv.2, align 4
call void @use(i32 %l.1)
%iv.2.next = add nsw i64 %iv.2, 1
%c.2 = icmp slt i64 %iv.2.next, 100
br i1 %c.2, label %loop.2, label %exit
exit:
ret void
}
; Test cases with a loop carried dependence in %loop.2, where both %l.0 and
; %l.1 read the value stored by the previous iteration. Hence, the store in
; %loop.2 is not dead at the end of the function or after the call to lifetime.end().
define void @test.2() {
; CHECK-LABEL: @test.2(
; CHECK-NEXT: entry:
; CHECK-NEXT: [[A:%.*]] = alloca [100 x i32], align 4
; CHECK-NEXT: br label [[LOOP_1:%.*]]
; CHECK: loop.1:
; CHECK-NEXT: [[IV_1:%.*]] = phi i64 [ 1, [[ENTRY:%.*]] ], [ [[IV_1_NEXT:%.*]], [[LOOP_1]] ]
; CHECK-NEXT: [[ARRAYIDX1:%.*]] = getelementptr inbounds [100 x i32], ptr [[A]], i64 0, i64 [[IV_1]]
; CHECK-NEXT: store i32 0, ptr [[ARRAYIDX1]], align 4
; CHECK-NEXT: [[IV_1_NEXT]] = add nsw i64 [[IV_1]], 1
; CHECK-NEXT: [[C_1:%.*]] = icmp slt i64 [[IV_1_NEXT]], 100
; CHECK-NEXT: br i1 [[C_1]], label [[LOOP_1]], label [[LOOP_2_PH:%.*]]
; CHECK: loop.2.ph:
; CHECK-NEXT: br label [[LOOP_2:%.*]]
; CHECK: loop.2:
; CHECK-NEXT: [[IV_2:%.*]] = phi i64 [ [[IV_2_NEXT:%.*]], [[LOOP_2]] ], [ 0, [[LOOP_2_PH]] ]
; CHECK-NEXT: [[PTR_IV_2:%.*]] = getelementptr inbounds [100 x i32], ptr [[A]], i64 0, i64 [[IV_2]]
; CHECK-NEXT: [[L_0:%.*]] = load i32, ptr [[PTR_IV_2]], align 4
; CHECK-NEXT: call void @use(i32 [[L_0]])
; CHECK-NEXT: [[ADD:%.*]] = add nsw i64 [[IV_2]], 1
; CHECK-NEXT: [[PTR_IV_2_ADD_1:%.*]] = getelementptr inbounds [100 x i32], ptr [[A]], i64 0, i64 [[ADD]]
; CHECK-NEXT: store i32 10, ptr [[PTR_IV_2_ADD_1]], align 4
; CHECK-NEXT: [[L_1:%.*]] = load i32, ptr [[PTR_IV_2]], align 4
; CHECK-NEXT: call void @use(i32 [[L_1]])
; CHECK-NEXT: [[IV_2_NEXT]] = add nsw i64 [[IV_2]], 1
; CHECK-NEXT: [[C_2:%.*]] = icmp slt i64 [[IV_2_NEXT]], 100
; CHECK-NEXT: br i1 [[C_2]], label [[LOOP_2]], label [[EXIT:%.*]]
; CHECK: exit:
; CHECK-NEXT: call void @llvm.lifetime.end.p0(i64 400, ptr nonnull [[A]])
; CHECK-NEXT: ret void
;
entry:
%A = alloca [100 x i32], align 4
br label %loop.1
loop.1:
%iv.1 = phi i64 [ 1, %entry ], [ %iv.1.next, %loop.1 ]
%arrayidx1 = getelementptr inbounds [100 x i32], ptr %A, i64 0, i64 %iv.1
store i32 0, ptr %arrayidx1, align 4
%iv.1.next = add nsw i64 %iv.1, 1
%c.1 = icmp slt i64 %iv.1.next, 100
br i1 %c.1, label %loop.1, label %loop.2.ph
loop.2.ph:
br label %loop.2
loop.2:
%iv.2 = phi i64 [ %iv.2.next, %loop.2 ], [ 0, %loop.2.ph ]
%ptr.iv.2 = getelementptr inbounds [100 x i32], ptr %A, i64 0, i64 %iv.2
%l.0 = load i32, ptr %ptr.iv.2, align 4
call void @use(i32 %l.0)
%add = add nsw i64 %iv.2, 1
%ptr.iv.2.add.1 = getelementptr inbounds [100 x i32], ptr %A, i64 0, i64 %add
store i32 10, ptr %ptr.iv.2.add.1, align 4
%l.1 = load i32, ptr %ptr.iv.2, align 4
call void @use(i32 %l.1)
%iv.2.next = add nsw i64 %iv.2, 1
%c.2 = icmp slt i64 %iv.2.next, 100
br i1 %c.2, label %loop.2, label %exit
exit:
call void @llvm.lifetime.end.p0(i64 400, ptr nonnull %A) #5
ret void
}
declare void @llvm.lifetime.end.p0(i64 immarg, ptr nocapture)
; Make sure `store i32 10, ptr %ptr.2` in %cond.store is not removed. The
; stored value may be read by `%use = load i32, ptr %ptr.1` in a future
; iteration.
define [email protected]() {
; CHECK-LABEL: @test.3(
; CHECK-NEXT: entry:
; CHECK-NEXT: [[NODESTACK:%.*]] = alloca [12 x i32], align 4
; CHECK-NEXT: [[C_1:%.*]] = call i1 @cond(i32 1)
; CHECK-NEXT: br i1 [[C_1]], label [[CLEANUP:%.*]], label [[LOOP_HEADER:%.*]]
; CHECK: loop.header:
; CHECK-NEXT: [[DEPTH_1:%.*]] = phi i32 [ [[DEPTH_1_BE:%.*]], [[LOOP_LATCH:%.*]] ], [ 3, [[ENTRY:%.*]] ]
; CHECK-NEXT: [[CMP:%.*]] = icmp sgt i32 [[DEPTH_1]], 0
; CHECK-NEXT: br i1 [[CMP]], label [[COND_READ:%.*]], label [[COND_STORE:%.*]]
; CHECK: cond.read:
; CHECK-NEXT: [[SUB:%.*]] = add nsw i32 [[DEPTH_1]], -3
; CHECK-NEXT: [[PTR_1:%.*]] = getelementptr inbounds [12 x i32], ptr [[NODESTACK]], i32 0, i32 [[SUB]]
; CHECK-NEXT: [[USE:%.*]] = load i32, ptr [[PTR_1]], align 4
; CHECK-NEXT: [[C_2:%.*]] = call i1 @cond(i32 [[USE]])
; CHECK-NEXT: br i1 [[C_2]], label [[LOOP_LATCH]], label [[COND_STORE]]
; CHECK: cond.store:
; CHECK-NEXT: [[PTR_2:%.*]] = getelementptr inbounds [12 x i32], ptr [[NODESTACK]], i32 0, i32 [[DEPTH_1]]
; CHECK-NEXT: store i32 10, ptr [[PTR_2]], align 4
; CHECK-NEXT: [[INC:%.*]] = add nsw i32 [[DEPTH_1]], 1
; CHECK-NEXT: [[C_3:%.*]] = call i1 @cond(i32 20)
; CHECK-NEXT: br i1 [[C_3]], label [[CLEANUP]], label [[LOOP_LATCH]]
; CHECK: loop.latch:
; CHECK-NEXT: [[DEPTH_1_BE]] = phi i32 [ [[SUB]], [[COND_READ]] ], [ [[INC]], [[COND_STORE]] ]
; CHECK-NEXT: br label [[LOOP_HEADER]]
; CHECK: cleanup:
; CHECK-NEXT: call void @llvm.lifetime.end.p0(i64 48, ptr nonnull [[NODESTACK]])
; CHECK-NEXT: ret void
;
entry:
%nodeStack = alloca [12 x i32], align 4
%c.1 = call i1 @cond(i32 1)
br i1 %c.1, label %cleanup, label %loop.header
loop.header: ; preds = %entry, %while.cond.backedge
%depth.1 = phi i32 [ %depth.1.be, %loop.latch ], [ 3, %entry ]
%cmp = icmp sgt i32 %depth.1, 0
br i1 %cmp, label %cond.read, label %cond.store
cond.read: ; preds = %while.cond
%sub = add nsw i32 %depth.1, -3
%ptr.1 = getelementptr inbounds [12 x i32], ptr %nodeStack, i32 0, i32 %sub
%use = load i32, ptr %ptr.1, align 4
%c.2 = call i1 @cond(i32 %use)
br i1 %c.2, label %loop.latch, label %cond.store
cond.store:
%ptr.2 = getelementptr inbounds [12 x i32], ptr %nodeStack, i32 0, i32 %depth.1
store i32 10, ptr %ptr.2, align 4
%inc = add nsw i32 %depth.1, 1
%c.3 = call i1 @cond(i32 20)
br i1 %c.3, label %cleanup, label %loop.latch
loop.latch:
%depth.1.be = phi i32 [ %sub, %cond.read ], [ %inc, %cond.store ]
br label %loop.header
cleanup: ; preds = %while.body, %while.end, %entry
call void @llvm.lifetime.end.p0(i64 48, ptr nonnull %nodeStack) #3
ret void
}
define void @store_to_invariant_loc() {
; CHECK-LABEL: @store_to_invariant_loc(
; CHECK-NEXT: entry:
; CHECK-NEXT: [[A:%.*]] = alloca [100 x i32], align 4
; CHECK-NEXT: [[PTR_20:%.*]] = getelementptr inbounds [100 x i32], ptr [[A]], i64 0, i64 20
; CHECK-NEXT: br label [[LOOP:%.*]]
; CHECK: loop:
; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[LOOP]] ], [ 0, [[ENTRY:%.*]] ]
; CHECK-NEXT: [[PTR_IV:%.*]] = getelementptr inbounds [100 x i32], ptr [[A]], i64 0, i64 [[IV]]
; CHECK-NEXT: [[L_0:%.*]] = load i32, ptr [[PTR_IV]], align 4
; CHECK-NEXT: call void @use(i32 [[L_0]])
; CHECK-NEXT: store i32 10, ptr [[PTR_20]], align 4
; CHECK-NEXT: [[IV_NEXT]] = add nsw i64 [[IV]], 1
; CHECK-NEXT: [[C:%.*]] = icmp slt i64 [[IV_NEXT]], 100
; CHECK-NEXT: br i1 [[C]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK: exit:
; CHECK-NEXT: ret void
;
entry:
%A = alloca [100 x i32], align 4
%ptr.20 = getelementptr inbounds [100 x i32], ptr %A, i64 0, i64 20
br label %loop
loop:
%iv = phi i64 [ %iv.next, %loop ], [ 0, %entry ]
%ptr.iv = getelementptr inbounds [100 x i32], ptr %A, i64 0, i64 %iv
%l.0 = load i32, ptr %ptr.iv, align 4
call void @use(i32 %l.0)
store i32 10, ptr %ptr.20, align 4
%iv.next = add nsw i64 %iv, 1
%c = icmp slt i64 %iv.next, 100
br i1 %c, label %loop , label %exit
exit:
ret void
}
declare i1 @cond(i32)
Codebase Browser
llvm