1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
2
3; RUN: opt -dse -S %s | FileCheck %s
4
5target datalayout = "e-m:e-i64:64-n32:64-v256:256:256-v512:512:512"
6
7declare void @use(i32)
8
9; Test cases with a loop carried dependence in %loop.2, where %l.2 reads the
10; value stored by the previous iteration. Hence, the store in %loop.2 is not
11; dead at the end of the function or after the call to lifetime.end().
12
13define void @test.1() {
14; CHECK-LABEL: @test.1(
15; CHECK-NEXT:  entry:
16; CHECK-NEXT:    [[A:%.*]] = alloca [100 x i32], align 4
17; CHECK-NEXT:    br label [[LOOP_1:%.*]]
18; CHECK:       loop.1:
19; CHECK-NEXT:    [[IV_1:%.*]] = phi i64 [ 1, [[ENTRY:%.*]] ], [ [[IV_1_NEXT:%.*]], [[LOOP_1]] ]
20; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds [100 x i32], [100 x i32]* [[A]], i64 0, i64 [[IV_1]]
21; CHECK-NEXT:    store i32 0, i32* [[ARRAYIDX1]], align 4
22; CHECK-NEXT:    [[IV_1_NEXT]] = add nsw i64 [[IV_1]], 1
23; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i64 [[IV_1_NEXT]], 100
24; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP_1]], label [[LOOP_2_PH:%.*]]
25; CHECK:       loop.2.ph:
26; CHECK-NEXT:    br label [[LOOP_2:%.*]]
27; CHECK:       loop.2:
28; CHECK-NEXT:    [[IV_2:%.*]] = phi i64 [ [[IV_2_NEXT:%.*]], [[LOOP_2]] ], [ 0, [[LOOP_2_PH]] ]
29; CHECK-NEXT:    [[PTR_IV_2:%.*]] = getelementptr inbounds [100 x i32], [100 x i32]* [[A]], i64 0, i64 [[IV_2]]
30; CHECK-NEXT:    [[L_0:%.*]] = load i32, i32* [[PTR_IV_2]], align 4
31; CHECK-NEXT:    call void @use(i32 [[L_0]])
32; CHECK-NEXT:    [[ADD:%.*]] = add nsw i64 [[IV_2]], 1
33; CHECK-NEXT:    [[PTR_IV_2_ADD_1:%.*]] = getelementptr inbounds [100 x i32], [100 x i32]* [[A]], i64 0, i64 [[ADD]]
34; CHECK-NEXT:    store i32 10, i32* [[PTR_IV_2_ADD_1]], align 4
35; CHECK-NEXT:    [[L_1:%.*]] = load i32, i32* [[PTR_IV_2]], align 4
36; CHECK-NEXT:    call void @use(i32 [[L_1]])
37; CHECK-NEXT:    [[IV_2_NEXT]] = add nsw i64 [[IV_2]], 1
38; CHECK-NEXT:    [[C_2:%.*]] = icmp slt i64 [[IV_2_NEXT]], 100
39; CHECK-NEXT:    br i1 [[C_2]], label [[LOOP_2]], label [[EXIT:%.*]]
40; CHECK:       exit:
41; CHECK-NEXT:    ret void
42;
43entry:
44  %A = alloca [100 x i32], align 4
45  br label %loop.1
46
47loop.1:
48  %iv.1 = phi i64 [ 1, %entry ], [ %iv.1.next, %loop.1 ]
49  %arrayidx1 = getelementptr inbounds [100 x i32], [100 x i32]* %A, i64 0, i64 %iv.1
50  store i32 0, i32* %arrayidx1, align 4
51  %iv.1.next = add nsw i64 %iv.1, 1
52  %c.1 = icmp slt i64 %iv.1.next, 100
53  br i1 %c.1, label %loop.1, label %loop.2.ph
54
55loop.2.ph:
56  br label %loop.2
57
58loop.2:
59  %iv.2 = phi i64 [ %iv.2.next, %loop.2 ], [ 0, %loop.2.ph ]
60  %ptr.iv.2 = getelementptr inbounds [100 x i32], [100 x i32]* %A, i64 0, i64 %iv.2
61  %l.0 = load i32, i32* %ptr.iv.2, align 4
62  call void @use(i32 %l.0)
63  %add = add nsw i64 %iv.2, 1
64  %ptr.iv.2.add.1 = getelementptr inbounds [100 x i32], [100 x i32]* %A, i64 0, i64 %add
65  store i32 10, i32* %ptr.iv.2.add.1, align 4
66  %l.1 = load i32, i32* %ptr.iv.2, align 4
67  call void @use(i32 %l.1)
68  %iv.2.next = add nsw i64 %iv.2, 1
69  %c.2 = icmp slt i64 %iv.2.next, 100
70  br i1 %c.2, label %loop.2, label %exit
71
72exit:
73  ret void
74}
75
76define void @test.2() {
77; CHECK-LABEL: @test.2(
78; CHECK-NEXT:  entry:
79; CHECK-NEXT:    [[A:%.*]] = alloca [100 x i32], align 4
80; CHECK-NEXT:    [[A_CAST:%.*]] = bitcast [100 x i32]* [[A]] to i8*
81; CHECK-NEXT:    br label [[LOOP_1:%.*]]
82; CHECK:       loop.1:
83; CHECK-NEXT:    [[IV_1:%.*]] = phi i64 [ 1, [[ENTRY:%.*]] ], [ [[IV_1_NEXT:%.*]], [[LOOP_1]] ]
84; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds [100 x i32], [100 x i32]* [[A]], i64 0, i64 [[IV_1]]
85; CHECK-NEXT:    store i32 0, i32* [[ARRAYIDX1]], align 4
86; CHECK-NEXT:    [[IV_1_NEXT]] = add nsw i64 [[IV_1]], 1
87; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i64 [[IV_1_NEXT]], 100
88; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP_1]], label [[LOOP_2_PH:%.*]]
89; CHECK:       loop.2.ph:
90; CHECK-NEXT:    br label [[LOOP_2:%.*]]
91; CHECK:       loop.2:
92; CHECK-NEXT:    [[IV_2:%.*]] = phi i64 [ [[IV_2_NEXT:%.*]], [[LOOP_2]] ], [ 0, [[LOOP_2_PH]] ]
93; CHECK-NEXT:    [[PTR_IV_2:%.*]] = getelementptr inbounds [100 x i32], [100 x i32]* [[A]], i64 0, i64 [[IV_2]]
94; CHECK-NEXT:    [[L_0:%.*]] = load i32, i32* [[PTR_IV_2]], align 4
95; CHECK-NEXT:    call void @use(i32 [[L_0]])
96; CHECK-NEXT:    [[ADD:%.*]] = add nsw i64 [[IV_2]], 1
97; CHECK-NEXT:    [[PTR_IV_2_ADD_1:%.*]] = getelementptr inbounds [100 x i32], [100 x i32]* [[A]], i64 0, i64 [[ADD]]
98; CHECK-NEXT:    store i32 10, i32* [[PTR_IV_2_ADD_1]], align 4
99; CHECK-NEXT:    [[L_1:%.*]] = load i32, i32* [[PTR_IV_2]], align 4
100; CHECK-NEXT:    call void @use(i32 [[L_1]])
101; CHECK-NEXT:    [[IV_2_NEXT]] = add nsw i64 [[IV_2]], 1
102; CHECK-NEXT:    [[C_2:%.*]] = icmp slt i64 [[IV_2_NEXT]], 100
103; CHECK-NEXT:    br i1 [[C_2]], label [[LOOP_2]], label [[EXIT:%.*]]
104; CHECK:       exit:
105; CHECK-NEXT:    call void @llvm.lifetime.end.p0i8(i64 400, i8* nonnull [[A_CAST]])
106; CHECK-NEXT:    ret void
107;
108entry:
109  %A = alloca [100 x i32], align 4
110  %A.cast = bitcast [100 x i32]* %A to i8*
111  br label %loop.1
112
113loop.1:
114  %iv.1 = phi i64 [ 1, %entry ], [ %iv.1.next, %loop.1 ]
115  %arrayidx1 = getelementptr inbounds [100 x i32], [100 x i32]* %A, i64 0, i64 %iv.1
116  store i32 0, i32* %arrayidx1, align 4
117  %iv.1.next = add nsw i64 %iv.1, 1
118  %c.1 = icmp slt i64 %iv.1.next, 100
119  br i1 %c.1, label %loop.1, label %loop.2.ph
120
121loop.2.ph:
122  br label %loop.2
123
124loop.2:
125  %iv.2 = phi i64 [ %iv.2.next, %loop.2 ], [ 0, %loop.2.ph ]
126  %ptr.iv.2 = getelementptr inbounds [100 x i32], [100 x i32]* %A, i64 0, i64 %iv.2
127  %l.0 = load i32, i32* %ptr.iv.2, align 4
128  call void @use(i32 %l.0)
129  %add = add nsw i64 %iv.2, 1
130  %ptr.iv.2.add.1 = getelementptr inbounds [100 x i32], [100 x i32]* %A, i64 0, i64 %add
131  store i32 10, i32* %ptr.iv.2.add.1, align 4
132  %l.1 = load i32, i32* %ptr.iv.2, align 4
133  call void @use(i32 %l.1)
134  %iv.2.next = add nsw i64 %iv.2, 1
135  %c.2 = icmp slt i64 %iv.2.next, 100
136  br i1 %c.2, label %loop.2, label %exit
137
138exit:
139  call void @llvm.lifetime.end.p0i8(i64 400, i8* nonnull %A.cast) #5
140  ret void
141}
142
143declare void @llvm.lifetime.end.p0i8(i64 immarg, i8* nocapture)
144
145; Make sure `store i32 10, i32* %ptr.2` in %cond.store is not removed. The
146; stored value may be read by `%use = load i32, i32* %ptr.1` in a future
147; iteration.
148define void@test.3() {
149; CHECK-LABEL: @test.3(
150; CHECK-NEXT:  entry:
151; CHECK-NEXT:    [[NODESTACK:%.*]] = alloca [12 x i32], align 4
152; CHECK-NEXT:    [[NODESTACK_CAST:%.*]] = bitcast [12 x i32]* [[NODESTACK]] to i8*
153; CHECK-NEXT:    [[C_1:%.*]] = call i1 @cond(i32 1)
154; CHECK-NEXT:    br i1 [[C_1]], label [[CLEANUP:%.*]], label [[LOOP_HEADER:%.*]]
155; CHECK:       loop.header:
156; CHECK-NEXT:    [[DEPTH_1:%.*]] = phi i32 [ [[DEPTH_1_BE:%.*]], [[LOOP_LATCH:%.*]] ], [ 3, [[ENTRY:%.*]] ]
157; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[DEPTH_1]], 0
158; CHECK-NEXT:    br i1 [[CMP]], label [[COND_READ:%.*]], label [[COND_STORE:%.*]]
159; CHECK:       cond.read:
160; CHECK-NEXT:    [[SUB:%.*]] = add nsw i32 [[DEPTH_1]], -3
161; CHECK-NEXT:    [[PTR_1:%.*]] = getelementptr inbounds [12 x i32], [12 x i32]* [[NODESTACK]], i32 0, i32 [[SUB]]
162; CHECK-NEXT:    [[USE:%.*]] = load i32, i32* [[PTR_1]], align 4
163; CHECK-NEXT:    [[C_2:%.*]] = call i1 @cond(i32 [[USE]])
164; CHECK-NEXT:    br i1 [[C_2]], label [[LOOP_LATCH]], label [[COND_STORE]]
165; CHECK:       cond.store:
166; CHECK-NEXT:    [[PTR_2:%.*]] = getelementptr inbounds [12 x i32], [12 x i32]* [[NODESTACK]], i32 0, i32 [[DEPTH_1]]
167; CHECK-NEXT:    store i32 10, i32* [[PTR_2]], align 4
168; CHECK-NEXT:    [[INC:%.*]] = add nsw i32 [[DEPTH_1]], 1
169; CHECK-NEXT:    [[C_3:%.*]] = call i1 @cond(i32 20)
170; CHECK-NEXT:    br i1 [[C_3]], label [[CLEANUP]], label [[LOOP_LATCH]]
171; CHECK:       loop.latch:
172; CHECK-NEXT:    [[DEPTH_1_BE]] = phi i32 [ [[SUB]], [[COND_READ]] ], [ [[INC]], [[COND_STORE]] ]
173; CHECK-NEXT:    br label [[LOOP_HEADER]]
174; CHECK:       cleanup:
175; CHECK-NEXT:    call void @llvm.lifetime.end.p0i8(i64 48, i8* nonnull [[NODESTACK_CAST]])
176; CHECK-NEXT:    ret void
177;
178entry:
179  %nodeStack = alloca [12 x i32], align 4
180  %nodeStack.cast = bitcast [12 x i32]* %nodeStack to i8*
181  %c.1 = call i1 @cond(i32 1)
182  br i1 %c.1, label %cleanup, label %loop.header
183
184loop.header:                                       ; preds = %entry, %while.cond.backedge
185  %depth.1 = phi i32 [ %depth.1.be, %loop.latch ], [ 3, %entry ]
186  %cmp = icmp sgt i32 %depth.1, 0
187  br i1 %cmp, label %cond.read, label %cond.store
188
189cond.read:                                        ; preds = %while.cond
190  %sub = add nsw i32 %depth.1, -3
191  %ptr.1 = getelementptr inbounds [12 x i32], [12 x i32]* %nodeStack, i32 0, i32 %sub
192  %use = load i32, i32* %ptr.1, align 4
193  %c.2 = call i1 @cond(i32 %use)
194  br i1 %c.2, label %loop.latch, label %cond.store
195
196cond.store:
197  %ptr.2 = getelementptr inbounds [12 x i32], [12 x i32]* %nodeStack, i32 0, i32 %depth.1
198  store i32 10, i32* %ptr.2, align 4
199  %inc = add nsw i32 %depth.1, 1
200  %c.3 = call i1 @cond(i32 20)
201  br i1 %c.3, label %cleanup, label %loop.latch
202
203loop.latch:
204  %depth.1.be = phi i32 [ %sub, %cond.read ], [ %inc, %cond.store ]
205  br label %loop.header
206
207cleanup:                                          ; preds = %while.body, %while.end, %entry
208  call void @llvm.lifetime.end.p0i8(i64 48, i8* nonnull %nodeStack.cast) #3
209  ret void
210}
211
212declare i1 @cond(i32)
213