xref: /llvm-project/llvm/test/Transforms/DFAJumpThreading/negative.ll (revision 5fb57131b744c52f74919f9487f4a9fa69f455fb) 
1; RUN: opt -passes=dfa-jump-threading -dfa-cost-threshold=25 -pass-remarks-missed='dfa-jump-threading' -pass-remarks-output=%t -disable-output %s
2; RUN: FileCheck --input-file %t --check-prefix=REMARK %s
3; RUN: opt -S -passes=dfa-jump-threading %s | FileCheck %s
4
5; This negative test case checks that the optimization doesn't trigger
6; when the code size cost is too high.
7define i32 @negative1(i32 %num) {
8; REMARK: NotProfitable
9; REMARK-NEXT: negative1
10entry:
11  br label %for.body
12
13for.body:
14  %count = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
15  %state = phi i32 [ 1, %entry ], [ %state.next, %for.inc ]
16  switch i32 %state, label %for.inc [
17  i32 1, label %case1
18  i32 2, label %case2
19  ]
20
21case1:
22  br label %for.inc
23
24case2:
25  %cmp = icmp eq i32 %count, 50
26  %sel = select i1 %cmp, i32 1, i32 2
27  br label %for.inc
28
29for.inc:
30  %state.next = phi i32 [ %sel, %case2 ], [ 1, %for.body ], [ 2, %case1 ]
31  %add1 = add i32 %num, %num
32  %add2 = add i32 %add1, %add1
33  %add3 = add i32 %add2, %add2
34  %add4 = add i32 %add3, %add3
35  %add5 = add i32 %add4, %add4
36  %add6 = add i32 %add5, %add5
37  %add7 = add i32 %add6, %add6
38  %add8 = add i32 %add7, %add7
39  %add9 = add i32 %add8, %add8
40  %add10 = add i32 %add9, %add9
41  %add11 = add i32 %add10, %add10
42  %add12 = add i32 %add11, %add11
43  %add13 = add i32 %add12, %add12
44  %add14 = add i32 %add13, %add13
45  %add15 = add i32 %add14, %add14
46  %add16 = add i32 %add15, %add15
47  %add17 = add i32 %add16, %add16
48  %add18 = add i32 %add17, %add17
49  %add19 = add i32 %add18, %add18
50  %add20 = add i32 %add19, %add19
51  %add21 = add i32 %add20, %add20
52  %add22 = add i32 %add21, %add21
53  %inc = add nsw i32 %count, 1
54  %cmp.exit = icmp slt i32 %inc, %num
55  br i1 %cmp.exit, label %for.body, label %for.end
56
57for.end:
58  ret i32 %add22
59}
60
61declare void @func()
62
63define i32 @negative2(i32 %num) {
64; REMARK: NonDuplicatableInst
65; REMARK-NEXT: negative2
66entry:
67  br label %for.body
68
69for.body:
70  %count = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
71  %state = phi i32 [ 1, %entry ], [ %state.next, %for.inc ]
72  switch i32 %state, label %for.inc [
73  i32 1, label %case1
74  i32 2, label %case2
75  ]
76
77case1:
78  br label %for.inc
79
80case2:
81  %cmp = icmp eq i32 %count, 50
82  %sel = select i1 %cmp, i32 1, i32 2
83  br label %for.inc
84
85for.inc:
86  %state.next = phi i32 [ %sel, %case2 ], [ 1, %for.body ], [ 2, %case1 ]
87  call void @func() noduplicate
88  %inc = add nsw i32 %count, 1
89  %cmp.exit = icmp slt i32 %inc, %num
90  br i1 %cmp.exit, label %for.body, label %for.end
91
92for.end:
93  ret i32 0
94}
95
96define i32 @negative3(i32 %num) {
97; REMARK: ConvergentInst
98; REMARK-NEXT: negative3
99entry:
100  br label %for.body
101
102for.body:
103  %count = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
104  %state = phi i32 [ 1, %entry ], [ %state.next, %for.inc ]
105  switch i32 %state, label %for.inc [
106  i32 1, label %case1
107  i32 2, label %case2
108  ]
109
110case1:
111  br label %for.inc
112
113case2:
114  %cmp = icmp eq i32 %count, 50
115  %sel = select i1 %cmp, i32 1, i32 2
116  br label %for.inc
117
118for.inc:
119  %state.next = phi i32 [ %sel, %case2 ], [ 1, %for.body ], [ 2, %case1 ]
120  call void @func() convergent
121  %inc = add nsw i32 %count, 1
122  %cmp.exit = icmp slt i32 %inc, %num
123  br i1 %cmp.exit, label %for.body, label %for.end
124
125for.end:
126  ret i32 0
127}
128
129define i32 @negative4(i32 %num) {
130; REMARK: SwitchNotPredictable
131; REMARK-NEXT: negative4
132entry:
133  br label %for.body
134
135for.body:
136  %count = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
137  %state = phi i32 [ 1, %entry ], [ %state.next, %for.inc ]
138  switch i32 %state, label %for.inc [
139  i32 1, label %case1
140  i32 2, label %case2
141  ]
142
143case1:
144  br label %for.inc
145
146case2:
147  %cmp = icmp eq i32 %count, 50
148  %sel = select i1 %cmp, i32 1, i32 2
149  br label %for.inc
150
151for.inc:
152  ; the switch variable is not predictable since the exit value for %case1
153  ; is defined through a non-instruction (function argument).
154  %state.next = phi i32 [ %sel, %case2 ], [ 1, %for.body ], [ %num, %case1 ]
155  %inc = add nsw i32 %count, 1
156  %cmp.exit = icmp slt i32 %inc, %num
157  br i1 %cmp.exit, label %for.body, label %for.end
158
159for.end:
160  ret i32 0
161}
162
163; Do not optimize if marked minsize.
164define i32 @negative5(i32 %num) minsize {
165; CHECK-LABEL: @negative5(
166; CHECK-NEXT:  entry:
167; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
168; CHECK:       for.body:
169; CHECK-NEXT:    [[COUNT:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[FOR_INC:%.*]] ]
170; CHECK-NEXT:    [[STATE:%.*]] = phi i32 [ 1, [[ENTRY]] ], [ [[STATE_NEXT:%.*]], [[FOR_INC]] ]
171; CHECK-NEXT:    switch i32 [[STATE]], label [[FOR_INC]] [
172; CHECK-NEXT:    i32 1, label [[CASE1:%.*]]
173; CHECK-NEXT:    i32 2, label [[CASE2:%.*]]
174; CHECK-NEXT:    ]
175; CHECK:       case1:
176; CHECK-NEXT:    br label [[FOR_INC]]
177; CHECK:       case2:
178; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[COUNT]], 50
179; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP]], i32 1, i32 2
180; CHECK-NEXT:    br label [[FOR_INC]]
181; CHECK:       for.inc:
182; CHECK-NEXT:    [[STATE_NEXT]] = phi i32 [ [[SEL]], [[CASE2]] ], [ 1, [[FOR_BODY]] ], [ 2, [[CASE1]] ]
183; CHECK-NEXT:    [[INC]] = add nsw i32 [[COUNT]], 1
184; CHECK-NEXT:    [[CMP_EXIT:%.*]] = icmp slt i32 [[INC]], [[NUM:%.*]]
185; CHECK-NEXT:    br i1 [[CMP_EXIT]], label [[FOR_BODY]], label [[FOR_END:%.*]]
186; CHECK:       for.end:
187; CHECK-NEXT:    ret i32 0
188;
189entry:
190  br label %for.body
191
192for.body:
193  %count = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
194  %state = phi i32 [ 1, %entry ], [ %state.next, %for.inc ]
195  switch i32 %state, label %for.inc [
196  i32 1, label %case1
197  i32 2, label %case2
198  ]
199
200case1:
201  br label %for.inc
202
203case2:
204  %cmp = icmp eq i32 %count, 50
205  %sel = select i1 %cmp, i32 1, i32 2
206  br label %for.inc
207
208for.inc:
209  %state.next = phi i32 [ %sel, %case2 ], [ 1, %for.body ], [ 2, %case1 ]
210  %inc = add nsw i32 %count, 1
211  %cmp.exit = icmp slt i32 %inc, %num
212  br i1 %cmp.exit, label %for.body, label %for.end
213
214for.end:
215  ret i32 0
216}
217
218declare i32 @arbitrary_function()
219
220; Don't confuse %state.2 for the initial switch value.
221; [ 3, %case2 ] can still be threaded.
222define i32 @negative6(i32 %init) {
223; CHECK-LABEL: define i32 @negative6(
224; CHECK-SAME: i32 [[INIT:%.*]]) {
225; CHECK-NEXT:  [[ENTRY:.*:]]
226; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[INIT]], 0
227; CHECK-NEXT:    br label %[[LOOP_2:.*]]
228; CHECK:       [[LOOP_2]]:
229; CHECK-NEXT:    [[STATE_2:%.*]] = call i32 @arbitrary_function()
230; CHECK-NEXT:    br label %[[LOOP_3:.*]]
231; CHECK:       [[LOOP_3]]:
232; CHECK-NEXT:    [[STATE:%.*]] = phi i32 [ [[STATE_2]], %[[LOOP_2]] ]
233; CHECK-NEXT:    switch i32 [[STATE]], label %[[INFLOOP_I:.*]] [
234; CHECK-NEXT:      i32 2, label %[[CASE2:.*]]
235; CHECK-NEXT:      i32 3, label %[[CASE3:.*]]
236; CHECK-NEXT:      i32 4, label %[[CASE4:.*]]
237; CHECK-NEXT:      i32 0, label %[[CASE0:.*]]
238; CHECK-NEXT:      i32 1, label %[[CASE1:.*]]
239; CHECK-NEXT:    ]
240; CHECK:       [[LOOP_3_JT3:.*]]:
241; CHECK-NEXT:    [[STATE_JT3:%.*]] = phi i32 [ 3, %[[CASE2]] ]
242; CHECK-NEXT:    br label %[[CASE3]]
243; CHECK:       [[CASE2]]:
244; CHECK-NEXT:    br label %[[LOOP_3_JT3]]
245; CHECK:       [[CASE3]]:
246; CHECK-NEXT:    br i1 [[CMP]], label %[[LOOP_2_BACKEDGE:.*]], label %[[CASE4]]
247; CHECK:       [[CASE4]]:
248; CHECK-NEXT:    br label %[[LOOP_2_BACKEDGE]]
249; CHECK:       [[LOOP_2_BACKEDGE]]:
250; CHECK-NEXT:    br label %[[LOOP_2]]
251; CHECK:       [[CASE0]]:
252; CHECK-NEXT:    br label %[[EXIT:.*]]
253; CHECK:       [[CASE1]]:
254; CHECK-NEXT:    br label %[[EXIT]]
255; CHECK:       [[INFLOOP_I]]:
256; CHECK-NEXT:    br label %[[INFLOOP_I]]
257; CHECK:       [[EXIT]]:
258; CHECK-NEXT:    ret i32 0
259;
260entry:
261  %cmp = icmp eq i32 %init, 0
262  br label %loop.2
263
264loop.2:
265  %state.2 = call i32 @arbitrary_function()
266  br label %loop.3
267
268loop.3:
269  %state = phi i32 [ %state.2, %loop.2 ], [ 3, %case2 ]
270  switch i32 %state, label %infloop.i [
271    i32 2, label %case2
272    i32 3, label %case3
273    i32 4, label %case4
274    i32 0, label %case0
275    i32 1, label %case1
276  ]
277
278case2:
279  br label %loop.3
280
281case3:
282  br i1 %cmp, label %loop.2.backedge, label %case4
283
284case4:
285  br label %loop.2.backedge
286
287loop.2.backedge:
288  br label %loop.2
289
290case0:
291  br label %exit
292
293case1:
294  br label %exit
295
296infloop.i:
297  br label %infloop.i
298
299exit:
300  ret i32 0
301}
302