1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
2; RUN: opt -codegenprepare -S < %s | FileCheck %s
3target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
4target triple = "x86_64-unknown-linux-gnu"
5
6declare void @use(i32) local_unnamed_addr
7declare void @useptr([2 x i8*]*) local_unnamed_addr
8
9; CHECK: @simple.targets = constant [2 x i8*] [i8* blockaddress(@simple, %bb0), i8* blockaddress(@simple, %bb1)], align 16
10@simple.targets = constant [2 x i8*] [i8* blockaddress(@simple, %bb0), i8* blockaddress(@simple, %bb1)], align 16
11
12; CHECK: @multi.targets = constant [2 x i8*] [i8* blockaddress(@multi, %bb0), i8* blockaddress(@multi, %bb1)], align 16
13@multi.targets = constant [2 x i8*] [i8* blockaddress(@multi, %bb0), i8* blockaddress(@multi, %bb1)], align 16
14
15; CHECK: @loop.targets = constant [2 x i8*] [i8* blockaddress(@loop, %bb0), i8* blockaddress(@loop, %bb1)], align 16
16@loop.targets = constant [2 x i8*] [i8* blockaddress(@loop, %bb0), i8* blockaddress(@loop, %bb1)], align 16
17
18; CHECK: @nophi.targets = constant [2 x i8*] [i8* blockaddress(@nophi, %bb0), i8* blockaddress(@nophi, %bb1)], align 16
19@nophi.targets = constant [2 x i8*] [i8* blockaddress(@nophi, %bb0), i8* blockaddress(@nophi, %bb1)], align 16
20
21; CHECK: @noncritical.targets = constant [2 x i8*] [i8* blockaddress(@noncritical, %bb0), i8* blockaddress(@noncritical, %bb1)], align 16
22@noncritical.targets = constant [2 x i8*] [i8* blockaddress(@noncritical, %bb0), i8* blockaddress(@noncritical, %bb1)], align 16
23
24; Check that we break the critical edge when an jump table has only one use.
25define void @simple(i32* nocapture readonly %p) {
26; CHECK-LABEL: @simple(
27; CHECK-NEXT:  entry:
28; CHECK-NEXT:    [[INCDEC_PTR:%.*]] = getelementptr inbounds i32, i32* [[P:%.*]], i64 1
29; CHECK-NEXT:    [[INITVAL:%.*]] = load i32, i32* [[P]], align 4
30; CHECK-NEXT:    [[INITOP:%.*]] = load i32, i32* [[INCDEC_PTR]], align 4
31; CHECK-NEXT:    switch i32 [[INITOP]], label [[EXIT:%.*]] [
32; CHECK-NEXT:    i32 0, label [[BB0_CLONE:%.*]]
33; CHECK-NEXT:    i32 1, label [[BB1_CLONE:%.*]]
34; CHECK-NEXT:    ]
35; CHECK:       bb0:
36; CHECK-NEXT:    br label [[DOTSPLIT:%.*]]
37; CHECK:       .split:
38; CHECK-NEXT:    [[MERGE:%.*]] = phi i32* [ [[PTR:%.*]], [[BB0:%.*]] ], [ [[INCDEC_PTR]], [[BB0_CLONE]] ]
39; CHECK-NEXT:    [[MERGE2:%.*]] = phi i32 [ 0, [[BB0]] ], [ [[INITVAL]], [[BB0_CLONE]] ]
40; CHECK-NEXT:    tail call void @use(i32 [[MERGE2]])
41; CHECK-NEXT:    br label [[INDIRECTGOTO:%.*]]
42; CHECK:       bb1:
43; CHECK-NEXT:    br label [[DOTSPLIT3:%.*]]
44; CHECK:       .split3:
45; CHECK-NEXT:    [[MERGE5:%.*]] = phi i32* [ [[PTR]], [[BB1:%.*]] ], [ [[INCDEC_PTR]], [[BB1_CLONE]] ]
46; CHECK-NEXT:    [[MERGE7:%.*]] = phi i32 [ 1, [[BB1]] ], [ [[INITVAL]], [[BB1_CLONE]] ]
47; CHECK-NEXT:    tail call void @use(i32 [[MERGE7]])
48; CHECK-NEXT:    br label [[INDIRECTGOTO]]
49; CHECK:       indirectgoto:
50; CHECK-NEXT:    [[P_ADDR_SINK:%.*]] = phi i32* [ [[MERGE5]], [[DOTSPLIT3]] ], [ [[MERGE]], [[DOTSPLIT]] ]
51; CHECK-NEXT:    [[PTR]] = getelementptr inbounds i32, i32* [[P_ADDR_SINK]], i64 1
52; CHECK-NEXT:    [[NEWP:%.*]] = load i32, i32* [[P_ADDR_SINK]], align 4
53; CHECK-NEXT:    [[IDX:%.*]] = sext i32 [[NEWP]] to i64
54; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds [2 x i8*], [2 x i8*]* @simple.targets, i64 0, i64 [[IDX]]
55; CHECK-NEXT:    [[NEWOP:%.*]] = load i8*, i8** [[ARRAYIDX]], align 8
56; CHECK-NEXT:    indirectbr i8* [[NEWOP]], [label [[BB0]], label %bb1]
57; CHECK:       exit:
58; CHECK-NEXT:    ret void
59; CHECK:       bb0.clone:
60; CHECK-NEXT:    br label [[DOTSPLIT]]
61; CHECK:       bb1.clone:
62; CHECK-NEXT:    br label [[DOTSPLIT3]]
63;
64entry:
65  %incdec.ptr = getelementptr inbounds i32, i32* %p, i64 1
66  %initval = load i32, i32* %p, align 4
67  %initop = load i32, i32* %incdec.ptr, align 4
68  switch i32 %initop, label %exit [
69  i32 0, label %bb0
70  i32 1, label %bb1
71  ]
72
73bb0:
74  %p.addr.0 = phi i32* [ %incdec.ptr, %entry ], [ %ptr, %indirectgoto ]
75  %opcode.0 = phi i32 [ %initval, %entry ], [ 0, %indirectgoto ]
76  tail call void @use(i32 %opcode.0)
77  br label %indirectgoto
78
79bb1:
80  %p.addr.1 = phi i32* [ %incdec.ptr, %entry ], [ %ptr, %indirectgoto ]
81  %opcode.1 = phi i32 [ %initval, %entry ], [ 1, %indirectgoto ]
82  tail call void @use(i32 %opcode.1)
83  br label %indirectgoto
84
85indirectgoto:
86  %p.addr.sink = phi i32* [ %p.addr.1, %bb1 ], [ %p.addr.0, %bb0 ]
87  %ptr = getelementptr inbounds i32, i32* %p.addr.sink, i64 1
88  %newp = load i32, i32* %p.addr.sink, align 4
89  %idx = sext i32 %newp to i64
90  %arrayidx = getelementptr inbounds [2 x i8*], [2 x i8*]* @simple.targets, i64 0, i64 %idx
91  %newop = load i8*, i8** %arrayidx, align 8
92  indirectbr i8* %newop, [label %bb0, label %bb1]
93
94exit:
95  ret void
96}
97
98; Don't try to break critical edges when several indirectbr point to a single block
99define void @multi(i32* nocapture readonly %p) {
100; CHECK-LABEL: @multi(
101; CHECK-NEXT:  entry:
102; CHECK-NEXT:    [[INCDEC_PTR:%.*]] = getelementptr inbounds i32, i32* [[P:%.*]], i64 1
103; CHECK-NEXT:    [[INITVAL:%.*]] = load i32, i32* [[P]], align 4
104; CHECK-NEXT:    [[INITOP:%.*]] = load i32, i32* [[INCDEC_PTR]], align 4
105; CHECK-NEXT:    switch i32 [[INITOP]], label [[EXIT:%.*]] [
106; CHECK-NEXT:    i32 0, label [[BB0:%.*]]
107; CHECK-NEXT:    i32 1, label [[BB1:%.*]]
108; CHECK-NEXT:    ]
109; CHECK:       bb0:
110; CHECK-NEXT:    [[P_ADDR_0:%.*]] = phi i32* [ [[INCDEC_PTR]], [[ENTRY:%.*]] ], [ [[NEXT0:%.*]], [[BB0]] ], [ [[NEXT1:%.*]], [[BB1]] ]
111; CHECK-NEXT:    [[OPCODE_0:%.*]] = phi i32 [ [[INITVAL]], [[ENTRY]] ], [ 0, [[BB0]] ], [ 1, [[BB1]] ]
112; CHECK-NEXT:    tail call void @use(i32 [[OPCODE_0]])
113; CHECK-NEXT:    [[NEXT0]] = getelementptr inbounds i32, i32* [[P_ADDR_0]], i64 1
114; CHECK-NEXT:    [[NEWP0:%.*]] = load i32, i32* [[P_ADDR_0]], align 4
115; CHECK-NEXT:    [[IDX0:%.*]] = sext i32 [[NEWP0]] to i64
116; CHECK-NEXT:    [[ARRAYIDX0:%.*]] = getelementptr inbounds [2 x i8*], [2 x i8*]* @multi.targets, i64 0, i64 [[IDX0]]
117; CHECK-NEXT:    [[NEWOP0:%.*]] = load i8*, i8** [[ARRAYIDX0]], align 8
118; CHECK-NEXT:    indirectbr i8* [[NEWOP0]], [label [[BB0]], label %bb1]
119; CHECK:       bb1:
120; CHECK-NEXT:    [[P_ADDR_1:%.*]] = phi i32* [ [[INCDEC_PTR]], [[ENTRY]] ], [ [[NEXT0]], [[BB0]] ], [ [[NEXT1]], [[BB1]] ]
121; CHECK-NEXT:    [[OPCODE_1:%.*]] = phi i32 [ [[INITVAL]], [[ENTRY]] ], [ 0, [[BB0]] ], [ 1, [[BB1]] ]
122; CHECK-NEXT:    tail call void @use(i32 [[OPCODE_1]])
123; CHECK-NEXT:    [[NEXT1]] = getelementptr inbounds i32, i32* [[P_ADDR_1]], i64 1
124; CHECK-NEXT:    [[NEWP1:%.*]] = load i32, i32* [[P_ADDR_1]], align 4
125; CHECK-NEXT:    [[IDX1:%.*]] = sext i32 [[NEWP1]] to i64
126; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds [2 x i8*], [2 x i8*]* @multi.targets, i64 0, i64 [[IDX1]]
127; CHECK-NEXT:    [[NEWOP1:%.*]] = load i8*, i8** [[ARRAYIDX1]], align 8
128; CHECK-NEXT:    indirectbr i8* [[NEWOP1]], [label [[BB0]], label %bb1]
129; CHECK:       exit:
130; CHECK-NEXT:    ret void
131;
132entry:
133  %incdec.ptr = getelementptr inbounds i32, i32* %p, i64 1
134  %initval = load i32, i32* %p, align 4
135  %initop = load i32, i32* %incdec.ptr, align 4
136  switch i32 %initop, label %exit [
137  i32 0, label %bb0
138  i32 1, label %bb1
139  ]
140
141bb0:
142  %p.addr.0 = phi i32* [ %incdec.ptr, %entry ], [ %next0, %bb0 ], [ %next1, %bb1 ]
143  %opcode.0 = phi i32 [ %initval, %entry ], [ 0, %bb0 ], [ 1, %bb1 ]
144  tail call void @use(i32 %opcode.0)
145  %next0 = getelementptr inbounds i32, i32* %p.addr.0, i64 1
146  %newp0 = load i32, i32* %p.addr.0, align 4
147  %idx0 = sext i32 %newp0 to i64
148  %arrayidx0 = getelementptr inbounds [2 x i8*], [2 x i8*]* @multi.targets, i64 0, i64 %idx0
149  %newop0 = load i8*, i8** %arrayidx0, align 8
150  indirectbr i8* %newop0, [label %bb0, label %bb1]
151
152bb1:
153  %p.addr.1 = phi i32* [ %incdec.ptr, %entry ], [ %next0, %bb0 ], [ %next1, %bb1 ]
154  %opcode.1 = phi i32 [ %initval, %entry ], [ 0, %bb0 ], [ 1, %bb1 ]
155  tail call void @use(i32 %opcode.1)
156  %next1 = getelementptr inbounds i32, i32* %p.addr.1, i64 1
157  %newp1 = load i32, i32* %p.addr.1, align 4
158  %idx1 = sext i32 %newp1 to i64
159  %arrayidx1 = getelementptr inbounds [2 x i8*], [2 x i8*]* @multi.targets, i64 0, i64 %idx1
160  %newop1 = load i8*, i8** %arrayidx1, align 8
161  indirectbr i8* %newop1, [label %bb0, label %bb1]
162
163exit:
164  ret void
165}
166
167; Make sure we do the right thing for cases where the indirectbr branches to
168; the block it terminates.
169define void @loop(i64* nocapture readonly %p) {
170; CHECK-LABEL: @loop(
171; CHECK-NEXT:  entry:
172; CHECK-NEXT:    br label [[DOTSPLIT:%.*]]
173; CHECK:       bb0:
174; CHECK-NEXT:    br label [[DOTSPLIT]]
175; CHECK:       .split:
176; CHECK-NEXT:    [[MERGE:%.*]] = phi i64 [ [[I_NEXT:%.*]], [[BB0:%.*]] ], [ 0, [[BB0_CLONE:%.*]] ]
177; CHECK-NEXT:    [[TMP0:%.*]] = getelementptr inbounds i64, i64* [[P:%.*]], i64 [[MERGE]]
178; CHECK-NEXT:    store i64 [[MERGE]], i64* [[TMP0]], align 4
179; CHECK-NEXT:    [[I_NEXT]] = add nuw nsw i64 [[MERGE]], 1
180; CHECK-NEXT:    [[IDX:%.*]] = srem i64 [[MERGE]], 2
181; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds [2 x i8*], [2 x i8*]* @loop.targets, i64 0, i64 [[IDX]]
182; CHECK-NEXT:    [[TARGET:%.*]] = load i8*, i8** [[ARRAYIDX]], align 8
183; CHECK-NEXT:    indirectbr i8* [[TARGET]], [label [[BB0]], label %bb1]
184; CHECK:       bb1:
185; CHECK-NEXT:    ret void
186;
187entry:
188  br label %bb0
189
190bb0:
191  %i = phi i64 [ %i.next, %bb0 ], [ 0, %entry ]
192  %tmp0 = getelementptr inbounds i64, i64* %p, i64 %i
193  store i64 %i, i64* %tmp0, align 4
194  %i.next = add nuw nsw i64 %i, 1
195  %idx = srem i64 %i, 2
196  %arrayidx = getelementptr inbounds [2 x i8*], [2 x i8*]* @loop.targets, i64 0, i64 %idx
197  %target = load i8*, i8** %arrayidx, align 8
198  indirectbr i8* %target, [label %bb0, label %bb1]
199
200bb1:
201  ret void
202}
203
204; Don't do anything for cases that contain no phis.
205define void @nophi(i32* %p) {
206; CHECK-LABEL: @nophi(
207; CHECK-NEXT:  entry:
208; CHECK-NEXT:    [[INCDEC_PTR:%.*]] = getelementptr inbounds i32, i32* [[P:%.*]], i64 1
209; CHECK-NEXT:    [[INITOP:%.*]] = load i32, i32* [[INCDEC_PTR]], align 4
210; CHECK-NEXT:    switch i32 [[INITOP]], label [[EXIT:%.*]] [
211; CHECK-NEXT:    i32 0, label [[BB0:%.*]]
212; CHECK-NEXT:    i32 1, label [[BB1:%.*]]
213; CHECK-NEXT:    ]
214; CHECK:       bb0:
215; CHECK-NEXT:    tail call void @use(i32 0)
216; CHECK-NEXT:    br label [[INDIRECTGOTO:%.*]]
217; CHECK:       bb1:
218; CHECK-NEXT:    tail call void @use(i32 1)
219; CHECK-NEXT:    br label [[INDIRECTGOTO]]
220; CHECK:       indirectgoto:
221; CHECK-NEXT:    [[TMP0:%.*]] = bitcast i32* [[P]] to i8*
222; CHECK-NEXT:    [[SUNKADDR:%.*]] = getelementptr inbounds i8, i8* [[TMP0]], i64 4
223; CHECK-NEXT:    [[TMP1:%.*]] = bitcast i8* [[SUNKADDR]] to i32*
224; CHECK-NEXT:    [[NEWP:%.*]] = load i32, i32* [[TMP1]], align 4
225; CHECK-NEXT:    [[IDX:%.*]] = sext i32 [[NEWP]] to i64
226; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds [2 x i8*], [2 x i8*]* @nophi.targets, i64 0, i64 [[IDX]]
227; CHECK-NEXT:    [[NEWOP:%.*]] = load i8*, i8** [[ARRAYIDX]], align 8
228; CHECK-NEXT:    indirectbr i8* [[NEWOP]], [label [[BB0]], label %bb1]
229; CHECK:       exit:
230; CHECK-NEXT:    ret void
231;
232entry:
233  %incdec.ptr = getelementptr inbounds i32, i32* %p, i64 1
234  %initop = load i32, i32* %incdec.ptr, align 4
235  switch i32 %initop, label %exit [
236  i32 0, label %bb0
237  i32 1, label %bb1
238  ]
239
240bb0:
241  tail call void @use(i32 0)  br label %indirectgoto
242
243bb1:
244  tail call void @use(i32 1)
245  br label %indirectgoto
246
247indirectgoto:
248  %newp = load i32, i32* %incdec.ptr, align 4
249  %idx = sext i32 %newp to i64
250  %arrayidx = getelementptr inbounds [2 x i8*], [2 x i8*]* @nophi.targets, i64 0, i64 %idx
251  %newop = load i8*, i8** %arrayidx, align 8
252  indirectbr i8* %newop, [label %bb0, label %bb1]
253
254exit:
255  ret void
256}
257
258; Don't do anything if the edge isn't critical.
259define i32 @noncritical(i32 %k, i8* %p)
260; CHECK-LABEL: @noncritical(
261; CHECK-NEXT:  entry:
262; CHECK-NEXT:    [[D:%.*]] = add i32 [[K:%.*]], 1
263; CHECK-NEXT:    indirectbr i8* [[P:%.*]], [label [[BB0:%.*]], label %bb1]
264; CHECK:       bb0:
265; CHECK-NEXT:    [[R0:%.*]] = sub i32 [[K]], [[D]]
266; CHECK-NEXT:    br label [[EXIT:%.*]]
267; CHECK:       bb1:
268; CHECK-NEXT:    [[R1:%.*]] = sub i32 [[D]], [[K]]
269; CHECK-NEXT:    br label [[EXIT]]
270; CHECK:       exit:
271; CHECK-NEXT:    [[V:%.*]] = phi i32 [ [[R0]], [[BB0]] ], [ [[R1]], [[BB1:%.*]] ]
272; CHECK-NEXT:    ret i32 0
273;
274{
275entry:
276  %d = add i32 %k, 1
277  indirectbr i8* %p, [label %bb0, label %bb1]
278
279bb0:
280  %v00 = phi i32 [%k, %entry]
281  %v01 = phi i32 [%d, %entry]
282  %r0 = sub i32 %v00, %v01
283  br label %exit
284
285bb1:
286  %v10 = phi i32 [%d, %entry]
287  %v11 = phi i32 [%k, %entry]
288  %r1 = sub i32 %v10, %v11
289  br label %exit
290
291exit:
292  %v = phi i32 [%r0, %bb0], [%r1, %bb1]
293  ret i32 0
294}
295