xref: /llvm-project/llvm/test/Transforms/DeadStoreElimination/multiblock-loop-carried-dependence.ll (revision f497a00da968b0ff90d8c98caa184d14b9a92495) 
1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
2
3; RUN: opt -passes=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 both %l.0 and
10; %l.1 read the value stored by the previous iteration. Hence, the store in
11; %loop.2 is not dead at the end of the function.
12define void @test.1() {
13; CHECK-LABEL: @test.1(
14; CHECK-NEXT:  entry:
15; CHECK-NEXT:    [[A:%.*]] = alloca [100 x i32], align 4
16; CHECK-NEXT:    br label [[LOOP_1:%.*]]
17; CHECK:       loop.1:
18; CHECK-NEXT:    [[IV_1:%.*]] = phi i64 [ 1, [[ENTRY:%.*]] ], [ [[IV_1_NEXT:%.*]], [[LOOP_1]] ]
19; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds [100 x i32], ptr [[A]], i64 0, i64 [[IV_1]]
20; CHECK-NEXT:    store i32 0, ptr [[ARRAYIDX1]], align 4
21; CHECK-NEXT:    [[IV_1_NEXT]] = add nsw i64 [[IV_1]], 1
22; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i64 [[IV_1_NEXT]], 100
23; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP_1]], label [[LOOP_2_PH:%.*]]
24; CHECK:       loop.2.ph:
25; CHECK-NEXT:    br label [[LOOP_2:%.*]]
26; CHECK:       loop.2:
27; CHECK-NEXT:    [[IV_2:%.*]] = phi i64 [ [[IV_2_NEXT:%.*]], [[LOOP_2]] ], [ 0, [[LOOP_2_PH]] ]
28; CHECK-NEXT:    [[PTR_IV_2:%.*]] = getelementptr inbounds [100 x i32], ptr [[A]], i64 0, i64 [[IV_2]]
29; CHECK-NEXT:    [[L_0:%.*]] = load i32, ptr [[PTR_IV_2]], align 4
30; CHECK-NEXT:    call void @use(i32 [[L_0]])
31; CHECK-NEXT:    [[ADD:%.*]] = add nsw i64 [[IV_2]], 1
32; CHECK-NEXT:    [[PTR_IV_2_ADD_1:%.*]] = getelementptr inbounds [100 x i32], ptr [[A]], i64 0, i64 [[ADD]]
33; CHECK-NEXT:    store i32 10, ptr [[PTR_IV_2_ADD_1]], align 4
34; CHECK-NEXT:    [[L_1:%.*]] = load i32, ptr [[PTR_IV_2]], align 4
35; CHECK-NEXT:    call void @use(i32 [[L_1]])
36; CHECK-NEXT:    [[IV_2_NEXT]] = add nsw i64 [[IV_2]], 1
37; CHECK-NEXT:    [[C_2:%.*]] = icmp slt i64 [[IV_2_NEXT]], 100
38; CHECK-NEXT:    br i1 [[C_2]], label [[LOOP_2]], label [[EXIT:%.*]]
39; CHECK:       exit:
40; CHECK-NEXT:    ret void
41;
42entry:
43  %A = alloca [100 x i32], align 4
44  br label %loop.1
45
46loop.1:
47  %iv.1 = phi i64 [ 1, %entry ], [ %iv.1.next, %loop.1 ]
48  %arrayidx1 = getelementptr inbounds [100 x i32], ptr %A, i64 0, i64 %iv.1
49  store i32 0, ptr %arrayidx1, align 4
50  %iv.1.next = add nsw i64 %iv.1, 1
51  %c.1 = icmp slt i64 %iv.1.next, 100
52  br i1 %c.1, label %loop.1, label %loop.2.ph
53
54loop.2.ph:
55  br label %loop.2
56
57loop.2:
58  %iv.2 = phi i64 [ %iv.2.next, %loop.2 ], [ 0, %loop.2.ph ]
59  %ptr.iv.2 = getelementptr inbounds [100 x i32], ptr %A, i64 0, i64 %iv.2
60  %l.0 = load i32, ptr %ptr.iv.2, align 4
61  call void @use(i32 %l.0)
62  %add = add nsw i64 %iv.2, 1
63  %ptr.iv.2.add.1 = getelementptr inbounds [100 x i32], ptr %A, i64 0, i64 %add
64  store i32 10, ptr %ptr.iv.2.add.1, align 4
65  %l.1 = load i32, ptr %ptr.iv.2, align 4
66  call void @use(i32 %l.1)
67  %iv.2.next = add nsw i64 %iv.2, 1
68  %c.2 = icmp slt i64 %iv.2.next, 100
69  br i1 %c.2, label %loop.2, label %exit
70
71exit:
72  ret void
73}
74
75; Test cases with a loop carried dependence in %loop.2, where both %l.0 and
76; %l.1 read the value stored by the previous iteration. Hence, the store in
77; %loop.2 is not dead at the end of the function or after the call to lifetime.end().
78define void @test.2() {
79; CHECK-LABEL: @test.2(
80; CHECK-NEXT:  entry:
81; CHECK-NEXT:    [[A:%.*]] = alloca [100 x i32], align 4
82; CHECK-NEXT:    br label [[LOOP_1:%.*]]
83; CHECK:       loop.1:
84; CHECK-NEXT:    [[IV_1:%.*]] = phi i64 [ 1, [[ENTRY:%.*]] ], [ [[IV_1_NEXT:%.*]], [[LOOP_1]] ]
85; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds [100 x i32], ptr [[A]], i64 0, i64 [[IV_1]]
86; CHECK-NEXT:    store i32 0, ptr [[ARRAYIDX1]], align 4
87; CHECK-NEXT:    [[IV_1_NEXT]] = add nsw i64 [[IV_1]], 1
88; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i64 [[IV_1_NEXT]], 100
89; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP_1]], label [[LOOP_2_PH:%.*]]
90; CHECK:       loop.2.ph:
91; CHECK-NEXT:    br label [[LOOP_2:%.*]]
92; CHECK:       loop.2:
93; CHECK-NEXT:    [[IV_2:%.*]] = phi i64 [ [[IV_2_NEXT:%.*]], [[LOOP_2]] ], [ 0, [[LOOP_2_PH]] ]
94; CHECK-NEXT:    [[PTR_IV_2:%.*]] = getelementptr inbounds [100 x i32], ptr [[A]], i64 0, i64 [[IV_2]]
95; CHECK-NEXT:    [[L_0:%.*]] = load i32, ptr [[PTR_IV_2]], align 4
96; CHECK-NEXT:    call void @use(i32 [[L_0]])
97; CHECK-NEXT:    [[ADD:%.*]] = add nsw i64 [[IV_2]], 1
98; CHECK-NEXT:    [[PTR_IV_2_ADD_1:%.*]] = getelementptr inbounds [100 x i32], ptr [[A]], i64 0, i64 [[ADD]]
99; CHECK-NEXT:    store i32 10, ptr [[PTR_IV_2_ADD_1]], align 4
100; CHECK-NEXT:    [[L_1:%.*]] = load i32, ptr [[PTR_IV_2]], align 4
101; CHECK-NEXT:    call void @use(i32 [[L_1]])
102; CHECK-NEXT:    [[IV_2_NEXT]] = add nsw i64 [[IV_2]], 1
103; CHECK-NEXT:    [[C_2:%.*]] = icmp slt i64 [[IV_2_NEXT]], 100
104; CHECK-NEXT:    br i1 [[C_2]], label [[LOOP_2]], label [[EXIT:%.*]]
105; CHECK:       exit:
106; CHECK-NEXT:    call void @llvm.lifetime.end.p0(i64 400, ptr nonnull [[A]])
107; CHECK-NEXT:    ret void
108;
109entry:
110  %A = alloca [100 x i32], align 4
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], ptr %A, i64 0, i64 %iv.1
116  store i32 0, ptr %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], ptr %A, i64 0, i64 %iv.2
127  %l.0 = load i32, ptr %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], ptr %A, i64 0, i64 %add
131  store i32 10, ptr %ptr.iv.2.add.1, align 4
132  %l.1 = load i32, ptr %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.p0(i64 400, ptr nonnull %A) #5
140  ret void
141}
142
143declare void @llvm.lifetime.end.p0(i64 immarg, ptr nocapture)
144
145; Make sure `store i32 10, ptr %ptr.2` in %cond.store is not removed. The
146; stored value may be read by `%use = load i32, ptr %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:    [[C_1:%.*]] = call i1 @cond(i32 1)
153; CHECK-NEXT:    br i1 [[C_1]], label [[CLEANUP:%.*]], label [[LOOP_HEADER:%.*]]
154; CHECK:       loop.header:
155; CHECK-NEXT:    [[DEPTH_1:%.*]] = phi i32 [ [[DEPTH_1_BE:%.*]], [[LOOP_LATCH:%.*]] ], [ 3, [[ENTRY:%.*]] ]
156; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[DEPTH_1]], 0
157; CHECK-NEXT:    br i1 [[CMP]], label [[COND_READ:%.*]], label [[COND_STORE:%.*]]
158; CHECK:       cond.read:
159; CHECK-NEXT:    [[SUB:%.*]] = add nsw i32 [[DEPTH_1]], -3
160; CHECK-NEXT:    [[PTR_1:%.*]] = getelementptr inbounds [12 x i32], ptr [[NODESTACK]], i32 0, i32 [[SUB]]
161; CHECK-NEXT:    [[USE:%.*]] = load i32, ptr [[PTR_1]], align 4
162; CHECK-NEXT:    [[C_2:%.*]] = call i1 @cond(i32 [[USE]])
163; CHECK-NEXT:    br i1 [[C_2]], label [[LOOP_LATCH]], label [[COND_STORE]]
164; CHECK:       cond.store:
165; CHECK-NEXT:    [[PTR_2:%.*]] = getelementptr inbounds [12 x i32], ptr [[NODESTACK]], i32 0, i32 [[DEPTH_1]]
166; CHECK-NEXT:    store i32 10, ptr [[PTR_2]], align 4
167; CHECK-NEXT:    [[INC:%.*]] = add nsw i32 [[DEPTH_1]], 1
168; CHECK-NEXT:    [[C_3:%.*]] = call i1 @cond(i32 20)
169; CHECK-NEXT:    br i1 [[C_3]], label [[CLEANUP]], label [[LOOP_LATCH]]
170; CHECK:       loop.latch:
171; CHECK-NEXT:    [[DEPTH_1_BE]] = phi i32 [ [[SUB]], [[COND_READ]] ], [ [[INC]], [[COND_STORE]] ]
172; CHECK-NEXT:    br label [[LOOP_HEADER]]
173; CHECK:       cleanup:
174; CHECK-NEXT:    call void @llvm.lifetime.end.p0(i64 48, ptr nonnull [[NODESTACK]])
175; CHECK-NEXT:    ret void
176;
177entry:
178  %nodeStack = alloca [12 x i32], align 4
179  %c.1 = call i1 @cond(i32 1)
180  br i1 %c.1, label %cleanup, label %loop.header
181
182loop.header:                                       ; preds = %entry, %while.cond.backedge
183  %depth.1 = phi i32 [ %depth.1.be, %loop.latch ], [ 3, %entry ]
184  %cmp = icmp sgt i32 %depth.1, 0
185  br i1 %cmp, label %cond.read, label %cond.store
186
187cond.read:                                        ; preds = %while.cond
188  %sub = add nsw i32 %depth.1, -3
189  %ptr.1 = getelementptr inbounds [12 x i32], ptr %nodeStack, i32 0, i32 %sub
190  %use = load i32, ptr %ptr.1, align 4
191  %c.2 = call i1 @cond(i32 %use)
192  br i1 %c.2, label %loop.latch, label %cond.store
193
194cond.store:
195  %ptr.2 = getelementptr inbounds [12 x i32], ptr %nodeStack, i32 0, i32 %depth.1
196  store i32 10, ptr %ptr.2, align 4
197  %inc = add nsw i32 %depth.1, 1
198  %c.3 = call i1 @cond(i32 20)
199  br i1 %c.3, label %cleanup, label %loop.latch
200
201loop.latch:
202  %depth.1.be = phi i32 [ %sub, %cond.read ], [ %inc, %cond.store ]
203  br label %loop.header
204
205cleanup:                                          ; preds = %while.body, %while.end, %entry
206  call void @llvm.lifetime.end.p0(i64 48, ptr nonnull %nodeStack) #3
207  ret void
208}
209
210define void @store_to_invariant_loc() {
211; CHECK-LABEL: @store_to_invariant_loc(
212; CHECK-NEXT:  entry:
213; CHECK-NEXT:    [[A:%.*]] = alloca [100 x i32], align 4
214; CHECK-NEXT:    [[PTR_20:%.*]] = getelementptr inbounds [100 x i32], ptr [[A]], i64 0, i64 20
215; CHECK-NEXT:    br label [[LOOP:%.*]]
216; CHECK:       loop:
217; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[LOOP]] ], [ 0, [[ENTRY:%.*]] ]
218; CHECK-NEXT:    [[PTR_IV:%.*]] = getelementptr inbounds [100 x i32], ptr [[A]], i64 0, i64 [[IV]]
219; CHECK-NEXT:    [[L_0:%.*]] = load i32, ptr [[PTR_IV]], align 4
220; CHECK-NEXT:    call void @use(i32 [[L_0]])
221; CHECK-NEXT:    store i32 10, ptr [[PTR_20]], align 4
222; CHECK-NEXT:    [[IV_NEXT]] = add nsw i64 [[IV]], 1
223; CHECK-NEXT:    [[C:%.*]] = icmp slt i64 [[IV_NEXT]], 100
224; CHECK-NEXT:    br i1 [[C]], label [[LOOP]], label [[EXIT:%.*]]
225; CHECK:       exit:
226; CHECK-NEXT:    ret void
227;
228entry:
229  %A = alloca [100 x i32], align 4
230  %ptr.20 = getelementptr inbounds [100 x i32], ptr %A, i64 0, i64 20
231  br label %loop
232
233loop:
234  %iv = phi i64 [ %iv.next, %loop ], [ 0, %entry ]
235  %ptr.iv = getelementptr inbounds [100 x i32], ptr %A, i64 0, i64 %iv
236  %l.0 = load i32, ptr %ptr.iv, align 4
237  call void @use(i32 %l.0)
238  store i32 10, ptr %ptr.20, align 4
239  %iv.next = add nsw i64 %iv, 1
240  %c = icmp slt i64 %iv.next, 100
241  br i1 %c, label %loop , label %exit
242
243exit:
244  ret void
245}
246
247declare i1 @cond(i32)
248