1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
2
3; RUN: opt < %s -basic-aa -dse -S | FileCheck %s
4
5target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
6declare void @unknown_func()
7declare void @llvm.lifetime.start.p0i8(i64, i8* nocapture) nounwind
8declare void @llvm.lifetime.end.p0i8(i64, i8* nocapture) nounwind
9declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture, i8* nocapture, i64, i1) nounwind
10declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i32, i1) nounwind
11
12declare noalias i8* @calloc(i64, i64) #5
13declare noalias i8* @malloc(i64) #0
14declare noalias i8* @strdup(i8* nocapture readonly) #1
15declare void @free(i8* nocapture) #2
16
17define void @test16(i32* noalias %P) {
18; CHECK-LABEL: @test16(
19; CHECK-NEXT:    [[P2:%.*]] = bitcast i32* [[P:%.*]] to i8*
20; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB3:%.*]]
21; CHECK:       bb1:
22; CHECK-NEXT:    br label [[BB3]]
23; CHECK:       bb3:
24; CHECK-NEXT:    call void @free(i8* [[P2]])
25; CHECK-NEXT:    store i32 1, i32* [[P]]
26; CHECK-NEXT:    ret void
27;
28  %P2 = bitcast i32* %P to i8*
29  store i32 1, i32* %P
30  br i1 true, label %bb1, label %bb3
31bb1:
32  store i32 1, i32* %P
33  br label %bb3
34bb3:
35  call void @free(i8* %P2)
36  store i32 1, i32* %P
37  ret void
38}
39
40; We cannot remove the store in the entry block, because @unknown_func could
41; unwind and the stored value could be read by the caller.
42define void @test17(i32* noalias %P) {
43; CHECK-LABEL: @test17(
44; CHECK-NEXT:    [[P2:%.*]] = bitcast i32* [[P:%.*]] to i8*
45; CHECK-NEXT:    store i32 1, i32* [[P]], align 4
46; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB3:%.*]]
47; CHECK:       bb1:
48; CHECK-NEXT:    call void @unknown_func()
49; CHECK-NEXT:    br label [[BB3]]
50; CHECK:       bb3:
51; CHECK-NEXT:    call void @free(i8* [[P2]])
52; CHECK-NEXT:    ret void
53;
54  %P2 = bitcast i32* %P to i8*
55  store i32 1, i32* %P
56  br i1 true, label %bb1, label %bb3
57bb1:
58  call void @unknown_func()
59  store i32 1, i32* %P
60  br label %bb3
61bb3:
62  call void @free(i8* %P2)
63  ret void
64}
65
66define void @test17_read_after_free(i32* noalias %P) {
67; CHECK-LABEL: @test17_read_after_free(
68; CHECK-NEXT:    [[P2:%.*]] = bitcast i32* [[P:%.*]] to i8*
69; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB3:%.*]]
70; CHECK:       bb1:
71; CHECK-NEXT:    br label [[BB3]]
72; CHECK:       bb3:
73; CHECK-NEXT:    call void @free(i8* [[P2]])
74; CHECK-NEXT:    [[LV:%.*]] = load i8, i8* [[P2]]
75; CHECK-NEXT:    ret void
76;
77  %P2 = bitcast i32* %P to i8*
78  store i32 1, i32* %P
79  br i1 true, label %bb1, label %bb3
80bb1:
81  store i32 1, i32* %P
82  br label %bb3
83bb3:
84  call void @free(i8* %P2)
85  %lv = load i8, i8* %P2
86  ret void
87}
88
89define void @test19(i32* noalias %P) {
90; CHECK-LABEL: @test19(
91; CHECK-NEXT:  entry:
92; CHECK-NEXT:    [[ARRAYIDX0:%.*]] = getelementptr inbounds i32, i32* [[P:%.*]], i64 1
93; CHECK-NEXT:    [[P3:%.*]] = bitcast i32* [[ARRAYIDX0]] to i8*
94; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 4 [[P3]], i8 0, i64 28, i1 false)
95; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
96; CHECK:       bb1:
97; CHECK-NEXT:    br label [[BB3:%.*]]
98; CHECK:       bb2:
99; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds i32, i32* [[P]], i64 1
100; CHECK-NEXT:    store i32 1, i32* [[ARRAYIDX1]], align 4
101; CHECK-NEXT:    br label [[BB3]]
102; CHECK:       bb3:
103; CHECK-NEXT:    ret void
104;
105entry:
106  %arrayidx0 = getelementptr inbounds i32, i32* %P, i64 1
107  %p3 = bitcast i32* %arrayidx0 to i8*
108  call void @llvm.memset.p0i8.i64(i8* %p3, i8 0, i64 28, i32 4, i1 false)
109  br i1 true, label %bb1, label %bb2
110bb1:
111  br label %bb3
112bb2:
113  %arrayidx1 = getelementptr inbounds i32, i32* %P, i64 1
114  store i32 1, i32* %arrayidx1, align 4
115  br label %bb3
116bb3:
117  ret void
118}
119
120
121define void @test20(i32* noalias %P) {
122; CHECK-LABEL: @test20(
123; CHECK-NEXT:  entry:
124; CHECK-NEXT:    [[ARRAYIDX0:%.*]] = getelementptr inbounds i32, i32* [[P:%.*]], i64 1
125; CHECK-NEXT:    [[P3:%.*]] = bitcast i32* [[ARRAYIDX0]] to i8*
126; CHECK-NEXT:    [[TMP0:%.*]] = getelementptr inbounds i8, i8* [[P3]], i64 4
127; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 4 [[TMP0]], i8 0, i64 24, i1 false)
128; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
129; CHECK:       bb1:
130; CHECK-NEXT:    br label [[BB3:%.*]]
131; CHECK:       bb2:
132; CHECK-NEXT:    br label [[BB3]]
133; CHECK:       bb3:
134; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds i32, i32* [[P]], i64 1
135; CHECK-NEXT:    store i32 1, i32* [[ARRAYIDX1]], align 4
136; CHECK-NEXT:    ret void
137;
138entry:
139  %arrayidx0 = getelementptr inbounds i32, i32* %P, i64 1
140  %p3 = bitcast i32* %arrayidx0 to i8*
141  call void @llvm.memset.p0i8.i64(i8* %p3, i8 0, i64 28, i32 4, i1 false)
142  br i1 true, label %bb1, label %bb2
143bb1:
144  br label %bb3
145bb2:
146  br label %bb3
147bb3:
148  %arrayidx1 = getelementptr inbounds i32, i32* %P, i64 1
149  store i32 1, i32* %arrayidx1, align 4
150  ret void
151}
152
153define i8* @test26() {
154; CHECK-LABEL: @test26(
155; CHECK-NEXT:  bb1:
156; CHECK-NEXT:    br i1 true, label [[BB2:%.*]], label [[BB3:%.*]]
157; CHECK:       bb2:
158; CHECK-NEXT:    [[M:%.*]] = call noalias i8* @malloc(i64 10)
159; CHECK-NEXT:    store i8 1, i8* [[M]]
160; CHECK-NEXT:    br label [[BB3]]
161; CHECK:       bb3:
162; CHECK-NEXT:    [[R:%.*]] = phi i8* [ null, [[BB1:%.*]] ], [ [[M]], [[BB2]] ]
163; CHECK-NEXT:    ret i8* [[R]]
164;
165bb1:
166  br i1 true, label %bb2, label %bb3
167bb2:
168  %m = call noalias i8* @malloc(i64 10)
169  store i8 1, i8* %m
170  br label %bb3
171bb3:
172  %r = phi i8* [ null, %bb1 ], [ %m, %bb2 ]
173  ret i8* %r
174}
175
176
177define void @test27() {
178; CHECK-LABEL: @test27(
179; CHECK-NEXT:  bb1:
180; CHECK-NEXT:    br i1 true, label [[BB2:%.*]], label [[BB3:%.*]]
181; CHECK:       bb2:
182; CHECK-NEXT:    [[M:%.*]] = call noalias i8* @malloc(i64 10)
183; CHECK-NEXT:    store i8 1, i8* [[M]], align 1
184; CHECK-NEXT:    br label [[BB3]]
185; CHECK:       bb3:
186; CHECK-NEXT:    [[R:%.*]] = phi i8* [ null, [[BB1:%.*]] ], [ [[M]], [[BB2]] ]
187; CHECK-NEXT:    ret void
188;
189bb1:
190  br i1 true, label %bb2, label %bb3
191bb2:
192  %m = call noalias i8* @malloc(i64 10)
193  store i8 1, i8* %m
194  br label %bb3
195bb3:
196  %r = phi i8* [ null, %bb1 ], [ %m, %bb2 ]
197  ret void
198}
199
200
201define i8* @test28() {
202; CHECK-LABEL: @test28(
203; CHECK-NEXT:  bb0:
204; CHECK-NEXT:    [[M:%.*]] = call noalias i8* @malloc(i64 10)
205; CHECK-NEXT:    [[MC0:%.*]] = bitcast i8* [[M]] to i8*
206; CHECK-NEXT:    [[MC1:%.*]] = bitcast i8* [[MC0]] to i8*
207; CHECK-NEXT:    [[MC2:%.*]] = bitcast i8* [[MC1]] to i8*
208; CHECK-NEXT:    [[MC3:%.*]] = bitcast i8* [[MC2]] to i8*
209; CHECK-NEXT:    [[MC4:%.*]] = bitcast i8* [[MC3]] to i8*
210; CHECK-NEXT:    [[MC5:%.*]] = bitcast i8* [[MC4]] to i8*
211; CHECK-NEXT:    [[MC6:%.*]] = bitcast i8* [[MC5]] to i8*
212; CHECK-NEXT:    [[M0:%.*]] = bitcast i8* [[MC6]] to i8*
213; CHECK-NEXT:    store i8 2, i8* [[M]]
214; CHECK-NEXT:    ret i8* [[M0]]
215;
216bb0:
217  %m = call noalias i8* @malloc(i64 10)
218  %mc0 = bitcast i8* %m to i8*
219  %mc1 = bitcast i8* %mc0 to i8*
220  %mc2 = bitcast i8* %mc1 to i8*
221  %mc3 = bitcast i8* %mc2 to i8*
222  %mc4 = bitcast i8* %mc3 to i8*
223  %mc5 = bitcast i8* %mc4 to i8*
224  %mc6 = bitcast i8* %mc5 to i8*
225  %m0 = bitcast i8* %mc6 to i8*
226  store i8 2, i8* %m
227  ret i8* %m0
228}
229
230%struct.SystemCallMapElementStruct = type { i8*, i32, %struct.NodePtrVecStruct* }
231%struct.NodePtrVecStruct = type { i32, i32, %struct.NodeStruct** }
232%struct.NodeStruct = type { i32, i32, i8*, i32, i32, %struct.NodeStruct*, %struct.NodeListStruct*, %struct.EdgeListStruct*, i32, i32 }
233%struct.NodeListStruct = type { %struct.NodeStruct*, %struct.NodeListStruct* }
234%struct.EdgeListStruct = type { i32, %struct.NodeStruct*, %struct.EdgeListStruct* }
235%struct.SystemCallMapStruct = type { i32, i32, %struct.SystemCallMapElementStruct** }
236
237declare %struct.NodePtrVecStruct* @NodePtrVec_new(i32)
238
239define noalias %struct.SystemCallMapElementStruct* @SystemCallMapElement_new(i8* nocapture readonly %label, i32 %initialSize) {
240; CHECK-LABEL: @SystemCallMapElement_new(
241; CHECK-NEXT:  entry:
242; CHECK-NEXT:    [[CALL:%.*]] = tail call dereferenceable_or_null(24) i8* @malloc(i64 24) #6
243; CHECK-NEXT:    [[TMP0:%.*]] = bitcast i8* [[CALL]] to %struct.SystemCallMapElementStruct*
244; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i8* [[CALL]], null
245; CHECK-NEXT:    br i1 [[TOBOOL]], label [[CLEANUP:%.*]], label [[IF_THEN:%.*]]
246; CHECK:       if.then:
247; CHECK-NEXT:    [[CALL1:%.*]] = tail call i8* @strdup(i8* [[LABEL:%.*]])
248; CHECK-NEXT:    [[LABEL2:%.*]] = bitcast i8* [[CALL]] to i8**
249; CHECK-NEXT:    store i8* [[CALL1]], i8** [[LABEL2]], align 8
250; CHECK-NEXT:    [[INDEX:%.*]] = getelementptr inbounds i8, i8* [[CALL]], i64 8
251; CHECK-NEXT:    [[TMP1:%.*]] = bitcast i8* [[INDEX]] to i32*
252; CHECK-NEXT:    store i32 -1, i32* [[TMP1]], align 8
253; CHECK-NEXT:    [[TOBOOL4:%.*]] = icmp eq i8* [[CALL1]], null
254; CHECK-NEXT:    br i1 [[TOBOOL4]], label [[IF_THEN5:%.*]], label [[IF_END:%.*]]
255; CHECK:       if.then5:
256; CHECK-NEXT:    tail call void @free(i8* nonnull [[CALL]])
257; CHECK-NEXT:    br label [[CLEANUP]]
258; CHECK:       if.end:
259; CHECK-NEXT:    [[CALL6:%.*]] = tail call %struct.NodePtrVecStruct* @NodePtrVec_new(i32 [[INITIALSIZE:%.*]]) #4
260; CHECK-NEXT:    [[NODES:%.*]] = getelementptr inbounds i8, i8* [[CALL]], i64 16
261; CHECK-NEXT:    [[TMP2:%.*]] = bitcast i8* [[NODES]] to %struct.NodePtrVecStruct**
262; CHECK-NEXT:    store %struct.NodePtrVecStruct* [[CALL6]], %struct.NodePtrVecStruct** [[TMP2]], align 8
263; CHECK-NEXT:    [[TOBOOL8:%.*]] = icmp eq %struct.NodePtrVecStruct* [[CALL6]], null
264; CHECK-NEXT:    br i1 [[TOBOOL8]], label [[IF_THEN9:%.*]], label [[CLEANUP]]
265; CHECK:       if.then9:
266; CHECK-NEXT:    tail call void @free(i8* nonnull [[CALL]])
267; CHECK-NEXT:    br label [[CLEANUP]]
268; CHECK:       cleanup:
269; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi %struct.SystemCallMapElementStruct* [ null, [[IF_THEN9]] ], [ null, [[IF_THEN5]] ], [ [[TMP0]], [[IF_END]] ], [ [[TMP0]], [[ENTRY:%.*]] ]
270; CHECK-NEXT:    ret %struct.SystemCallMapElementStruct* [[RETVAL_0]]
271;
272entry:
273  %call = tail call dereferenceable_or_null(24) i8* @malloc(i64 24) #4
274  %0 = bitcast i8* %call to %struct.SystemCallMapElementStruct*
275  %tobool = icmp eq i8* %call, null
276  br i1 %tobool, label %cleanup, label %if.then
277
278if.then:                                          ; preds = %entry
279  %call1 = tail call i8* @strdup(i8* %label)
280  %label2 = bitcast i8* %call to i8**
281  store i8* %call1, i8** %label2, align 8
282  %index = getelementptr inbounds i8, i8* %call, i64 8
283  %1 = bitcast i8* %index to i32*
284  store i32 -1, i32* %1, align 8
285  %tobool4 = icmp eq i8* %call1, null
286  br i1 %tobool4, label %if.then5, label %if.end
287
288if.then5:                                         ; preds = %if.then
289  tail call void @free(i8* nonnull %call)
290  br label %cleanup
291
292if.end:                                           ; preds = %if.then
293  %call6 = tail call %struct.NodePtrVecStruct* @NodePtrVec_new(i32 %initialSize) #2
294  %nodes = getelementptr inbounds i8, i8* %call, i64 16
295  %2 = bitcast i8* %nodes to %struct.NodePtrVecStruct**
296  store %struct.NodePtrVecStruct* %call6, %struct.NodePtrVecStruct** %2, align 8
297  %tobool8 = icmp eq %struct.NodePtrVecStruct* %call6, null
298  br i1 %tobool8, label %if.then9, label %cleanup
299
300if.then9:                                         ; preds = %if.end
301  tail call void @free(i8* nonnull %call)
302  br label %cleanup
303
304cleanup:                                          ; preds = %entry, %if.end, %if.then9, %if.then5
305  %retval.0 = phi %struct.SystemCallMapElementStruct* [ null, %if.then9 ], [ null, %if.then5 ], [ %0, %if.end ], [ %0, %entry ]
306  ret %struct.SystemCallMapElementStruct* %retval.0
307}
308
309%struct.BitfieldStruct = type { i32, i8* }
310
311define noalias %struct.BitfieldStruct* @Bitfield_new(i32 %bitsNeeded) {
312; CHECK-LABEL: @Bitfield_new(
313; CHECK-NEXT:  entry:
314; CHECK-NEXT:    [[CALL:%.*]] = tail call dereferenceable_or_null(16) i8* @malloc(i64 16) #6
315; CHECK-NEXT:    [[TMP0:%.*]] = bitcast i8* [[CALL]] to %struct.BitfieldStruct*
316; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i8* [[CALL]], null
317; CHECK-NEXT:    br i1 [[TOBOOL]], label [[CLEANUP:%.*]], label [[IF_END:%.*]]
318; CHECK:       if.end:
319; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[BITSNEEDED:%.*]], 7
320; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 [[ADD]], 8
321; CHECK-NEXT:    [[CONV:%.*]] = sext i32 [[DIV]] to i64
322; CHECK-NEXT:    [[CALL1:%.*]] = tail call i8* @calloc(i64 [[CONV]], i64 1) #7
323; CHECK-NEXT:    [[BITFIELD:%.*]] = getelementptr inbounds i8, i8* [[CALL]], i64 8
324; CHECK-NEXT:    [[TMP1:%.*]] = bitcast i8* [[BITFIELD]] to i8**
325; CHECK-NEXT:    store i8* [[CALL1]], i8** [[TMP1]], align 8
326; CHECK-NEXT:    [[TOBOOL3:%.*]] = icmp eq i8* [[CALL1]], null
327; CHECK-NEXT:    br i1 [[TOBOOL3]], label [[IF_THEN4:%.*]], label [[IF_END5:%.*]]
328; CHECK:       if.then4:
329; CHECK-NEXT:    tail call void @free(i8* nonnull [[CALL]])
330; CHECK-NEXT:    br label [[CLEANUP]]
331; CHECK:       if.end5:
332; CHECK-NEXT:    [[BITSNEEDED6:%.*]] = bitcast i8* [[CALL]] to i32*
333; CHECK-NEXT:    store i32 [[BITSNEEDED]], i32* [[BITSNEEDED6]], align 8
334; CHECK-NEXT:    br label [[CLEANUP]]
335; CHECK:       cleanup:
336; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi %struct.BitfieldStruct* [ [[TMP0]], [[IF_END5]] ], [ null, [[IF_THEN4]] ], [ null, [[ENTRY:%.*]] ]
337; CHECK-NEXT:    ret %struct.BitfieldStruct* [[RETVAL_0]]
338;
339entry:
340  %call = tail call dereferenceable_or_null(16) i8* @malloc(i64 16) #4
341  %0 = bitcast i8* %call to %struct.BitfieldStruct*
342  %tobool = icmp eq i8* %call, null
343  br i1 %tobool, label %cleanup, label %if.end
344
345if.end:                                           ; preds = %entry
346  %add = add nsw i32 %bitsNeeded, 7
347  %div = sdiv i32 %add, 8
348  %conv = sext i32 %div to i64
349  %call1 = tail call i8* @calloc(i64 %conv, i64 1) #3
350  %bitfield = getelementptr inbounds i8, i8* %call, i64 8
351  %1 = bitcast i8* %bitfield to i8**
352  store i8* %call1, i8** %1, align 8
353  %tobool3 = icmp eq i8* %call1, null
354  br i1 %tobool3, label %if.then4, label %if.end5
355
356if.then4:                                         ; preds = %if.end
357  tail call void @free(i8* nonnull %call)
358  br label %cleanup
359
360if.end5:                                          ; preds = %if.end
361  %bitsNeeded6 = bitcast i8* %call to i32*
362  store i32 %bitsNeeded, i32* %bitsNeeded6, align 8
363  br label %cleanup
364
365cleanup:                                          ; preds = %entry, %if.end5, %if.then4
366  %retval.0 = phi %struct.BitfieldStruct* [ %0, %if.end5 ], [ null, %if.then4 ], [ null, %entry ]
367  ret %struct.BitfieldStruct* %retval.0
368}
369
370attributes #0 = { nofree nounwind allocsize(0) }
371attributes #1 = { nofree nounwind }
372attributes #2 = { nounwind }
373attributes #3 = { allocsize(0,1) }
374attributes #4 = { allocsize(0) }
375attributes #5 = { nofree nounwind allocsize(0,1) }
376