1; REQUIRES: asserts
2; RUN: opt -S -dfa-jump-threading -debug-only=dfa-jump-threading -disable-output %s 2>&1 | FileCheck %s
3
4; This test checks that the analysis identifies all threadable paths in a
5; simple CFG. A threadable path includes a list of basic blocks, the exit
6; state, and the block that determines the next state.
7; < path of BBs that form a cycle > [ state, determinator ]
8define i32 @test1(i32 %num) {
9; CHECK: < for.body for.inc > [ 1, for.inc ]
10; CHECK-NEXT: < for.body case1 for.inc > [ 2, for.inc ]
11; CHECK-NEXT: < for.body case2 for.inc > [ 1, for.inc ]
12; CHECK-NEXT: < for.body case2 si.unfold.false for.inc > [ 2, for.inc ]
13entry:
14  br label %for.body
15
16for.body:
17  %count = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
18  %state = phi i32 [ 1, %entry ], [ %state.next, %for.inc ]
19  switch i32 %state, label %for.inc [
20    i32 1, label %case1
21    i32 2, label %case2
22  ]
23
24case1:
25  br label %for.inc
26
27case2:
28  %cmp = icmp eq i32 %count, 50
29  %sel = select i1 %cmp, i32 1, i32 2
30  br label %for.inc
31
32for.inc:
33  %state.next = phi i32 [ %sel, %case2 ], [ 1, %for.body ], [ 2, %case1 ]
34  %inc = add nsw i32 %count, 1
35  %cmp.exit = icmp slt i32 %inc, %num
36  br i1 %cmp.exit, label %for.body, label %for.end
37
38for.end:
39  ret i32 0
40}
41
42; This test checks that the analysis finds threadable paths in a more
43; complicated CFG. Here the FSM is represented as a nested loop, with
44; fallthrough cases.
45define i32 @test2(i32 %init) {
46; CHECK: < loop.3 case2 > [ 3, loop.3 ]
47; CHECK-NEXT: < loop.3 case2 loop.1.backedge loop.1 loop.2 > [ 1, loop.1 ]
48; CHECK-NEXT: < loop.3 case2 loop.1.backedge si.unfold.false loop.1 loop.2 > [ 4, loop.1.backedge ]
49; CHECK-NEXT: < loop.3 case3 loop.2.backedge loop.2 > [ 0, loop.2.backedge ]
50; CHECK-NEXT: < loop.3 case3 case4 loop.2.backedge loop.2 > [ 3, loop.2.backedge ]
51; CHECK-NEXT: < loop.3 case3 case4 loop.1.backedge loop.1 loop.2 > [ 1, loop.1 ]
52; CHECK-NEXT: < loop.3 case3 case4 loop.1.backedge si.unfold.false loop.1 loop.2 > [ 2, loop.1.backedge ]
53; CHECK-NEXT: < loop.3 case4 loop.2.backedge loop.2 > [ 3, loop.2.backedge ]
54; CHECK-NEXT: < loop.3 case4 loop.1.backedge loop.1 loop.2 > [ 1, loop.1 ]
55; CHECK-NEXT: < loop.3 case4 loop.1.backedge si.unfold.false loop.1 loop.2 > [ 2, loop.1.backedge ]
56entry:
57  %cmp = icmp eq i32 %init, 0
58  %sel = select i1 %cmp, i32 0, i32 2
59  br label %loop.1
60
61loop.1:
62  %state.1 = phi i32 [ %sel, %entry ], [ %state.1.be2, %loop.1.backedge ]
63  br label %loop.2
64
65loop.2:
66  %state.2 = phi i32 [ %state.1, %loop.1 ], [ %state.2.be, %loop.2.backedge ]
67  br label %loop.3
68
69loop.3:
70  %state = phi i32 [ %state.2, %loop.2 ], [ 3, %case2 ]
71  switch i32 %state, label %infloop.i [
72    i32 2, label %case2
73    i32 3, label %case3
74    i32 4, label %case4
75    i32 0, label %case0
76    i32 1, label %case1
77  ]
78
79case2:
80  br i1 %cmp, label %loop.3, label %loop.1.backedge
81
82case3:
83  br i1 %cmp, label %loop.2.backedge, label %case4
84
85case4:
86  br i1 %cmp, label %loop.2.backedge, label %loop.1.backedge
87
88loop.1.backedge:
89  %state.1.be = phi i32 [ 2, %case4 ], [ 4, %case2 ]
90  %state.1.be2 = select i1 %cmp, i32 1, i32 %state.1.be
91  br label %loop.1
92
93loop.2.backedge:
94  %state.2.be = phi i32 [ 3, %case4 ], [ 0, %case3 ]
95  br label %loop.2
96
97case0:
98  br label %exit
99
100case1:
101  br label %exit
102
103infloop.i:
104  br label %infloop.i
105
106exit:
107  ret i32 0
108}
109
110declare void @baz()
111
112; Do not jump-thread those paths where the determinator basic block does not
113; precede the basic block that defines the switch condition.
114;
115; Otherwise, it is possible that the state defined in the determinator block
116; defines the state for the next iteration of the loop, rather than for the
117; current one.
118define i32 @wrong_bb_order() {
119; CHECK-LABEL: DFA Jump threading: wrong_bb_order
120; CHECK-NOT: < bb43 bb59 bb3 bb31 bb41 > [ 77, bb43 ]
121; CHECK-NOT: < bb43 bb49 bb59 bb3 bb31 bb41 > [ 77, bb43 ]
122bb:
123  %i = alloca [420 x i8], align 1
124  %i2 = getelementptr inbounds [420 x i8], [420 x i8]* %i, i64 0, i64 390
125  br label %bb3
126
127bb3:                                              ; preds = %bb59, %bb
128  %i4 = phi i8* [ %i2, %bb ], [ %i60, %bb59 ]
129  %i5 = phi i8 [ 77, %bb ], [ %i64, %bb59 ]
130  %i6 = phi i32 [ 2, %bb ], [ %i63, %bb59 ]
131  %i7 = phi i32 [ 26, %bb ], [ %i62, %bb59 ]
132  %i8 = phi i32 [ 25, %bb ], [ %i61, %bb59 ]
133  %i9 = icmp sgt i32 %i7, 2
134  %i10 = select i1 %i9, i32 %i7, i32 2
135  %i11 = add i32 %i8, 2
136  %i12 = sub i32 %i11, %i10
137  %i13 = mul nsw i32 %i12, 3
138  %i14 = add nsw i32 %i13, %i6
139  %i15 = sext i32 %i14 to i64
140  %i16 = getelementptr inbounds i8, i8* %i4, i64 %i15
141  %i17 = load i8, i8* %i16, align 1
142  %i18 = icmp sgt i8 %i17, 0
143  br i1 %i18, label %bb21, label %bb31
144
145bb21:                                             ; preds = %bb3
146  br i1 true, label %bb59, label %bb43
147
148bb59:                                             ; preds = %bb49, %bb43, %bb31, %bb21
149  %i60 = phi i8* [ %i44, %bb49 ], [ %i44, %bb43 ], [ %i34, %bb31 ], [ %i4, %bb21 ]
150  %i61 = phi i32 [ %i45, %bb49 ], [ %i45, %bb43 ], [ %i33, %bb31 ], [ %i8, %bb21 ]
151  %i62 = phi i32 [ %i47, %bb49 ], [ %i47, %bb43 ], [ %i32, %bb31 ], [ %i7, %bb21 ]
152  %i63 = phi i32 [ %i48, %bb49 ], [ %i48, %bb43 ], [ 2, %bb31 ], [ %i6, %bb21 ]
153  %i64 = phi i8 [ %i46, %bb49 ], [ %i46, %bb43 ], [ 77, %bb31 ], [ %i5, %bb21 ]
154  %i65 = icmp sgt i32 %i62, 0
155  br i1 %i65, label %bb3, label %bb66
156
157bb31:                                             ; preds = %bb3
158  %i32 = add nsw i32 %i7, -1
159  %i33 = add nsw i32 %i8, -1
160  %i34 = getelementptr inbounds i8, i8* %i4, i64 -15
161  %i35 = icmp eq i8 %i5, 77
162  br i1 %i35, label %bb59, label %bb41
163
164bb41:                                             ; preds = %bb31
165  tail call void @baz()
166  br label %bb43
167
168bb43:                                             ; preds = %bb41, %bb21
169  %i44 = phi i8* [ %i34, %bb41 ], [ %i4, %bb21 ]
170  %i45 = phi i32 [ %i33, %bb41 ], [ %i8, %bb21 ]
171  %i46 = phi i8 [ 77, %bb41 ], [ %i5, %bb21 ]
172  %i47 = phi i32 [ %i32, %bb41 ], [ %i7, %bb21 ]
173  %i48 = phi i32 [ 2, %bb41 ], [ %i6, %bb21 ]
174  tail call void @baz()
175  switch i8 %i5, label %bb59 [
176    i8 68, label %bb49
177    i8 73, label %bb49
178  ]
179
180bb49:                                             ; preds = %bb43, %bb43
181  tail call void @baz()
182  br label %bb59
183
184bb66:                                             ; preds = %bb59
185  ret i32 0
186}
187
188; Value %init is not predictable but it's okay since it is the value initial to the switch.
189define i32 @initial.value.positive1(i32 %init) {
190; CHECK: < loop.3 case2 > [ 3, loop.3 ]
191; CHECK-NEXT: < loop.3 case2 loop.1.backedge loop.1 loop.2 > [ 1, loop.1 ]
192; CHECK-NEXT: < loop.3 case2 loop.1.backedge si.unfold.false loop.1 loop.2 > [ 4, loop.1.backedge ]
193; CHECK-NEXT: < loop.3 case3 loop.2.backedge loop.2 > [ 0, loop.2.backedge ]
194; CHECK-NEXT: < loop.3 case3 case4 loop.2.backedge loop.2 > [ 3, loop.2.backedge ]
195; CHECK-NEXT: < loop.3 case3 case4 loop.1.backedge loop.1 loop.2 > [ 1, loop.1 ]
196; CHECK-NEXT: < loop.3 case3 case4 loop.1.backedge si.unfold.false loop.1 loop.2 > [ 2, loop.1.backedge ]
197; CHECK-NEXT: < loop.3 case4 loop.2.backedge loop.2 > [ 3, loop.2.backedge ]
198; CHECK-NEXT: < loop.3 case4 loop.1.backedge loop.1 loop.2 > [ 1, loop.1 ]
199; CHECK-NEXT: < loop.3 case4 loop.1.backedge si.unfold.false loop.1 loop.2 > [ 2, loop.1.backedge ]
200entry:
201  %cmp = icmp eq i32 %init, 0
202  br label %loop.1
203
204loop.1:
205  %state.1 = phi i32 [ %init, %entry ], [ %state.1.be2, %loop.1.backedge ]
206  br label %loop.2
207
208loop.2:
209  %state.2 = phi i32 [ %state.1, %loop.1 ], [ %state.2.be, %loop.2.backedge ]
210  br label %loop.3
211
212loop.3:
213  %state = phi i32 [ %state.2, %loop.2 ], [ 3, %case2 ]
214  switch i32 %state, label %infloop.i [
215    i32 2, label %case2
216    i32 3, label %case3
217    i32 4, label %case4
218    i32 0, label %case0
219    i32 1, label %case1
220  ]
221
222case2:
223  br i1 %cmp, label %loop.3, label %loop.1.backedge
224
225case3:
226  br i1 %cmp, label %loop.2.backedge, label %case4
227
228case4:
229  br i1 %cmp, label %loop.2.backedge, label %loop.1.backedge
230
231loop.1.backedge:
232  %state.1.be = phi i32 [ 2, %case4 ], [ 4, %case2 ]
233  %state.1.be2 = select i1 %cmp, i32 1, i32 %state.1.be
234  br label %loop.1
235
236loop.2.backedge:
237  %state.2.be = phi i32 [ 3, %case4 ], [ 0, %case3 ]
238  br label %loop.2
239
240case0:
241  br label %exit
242
243case1:
244  br label %exit
245
246infloop.i:
247  br label %infloop.i
248
249exit:
250  ret i32 0
251}
252