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; Verify that having the switch block as a determinator is handled correctly.
113define i32 @main() {
114; CHECK: < bb43 bb59 bb3 bb31 bb41 > [ 77, bb43 ]
115; CHECK-NEXT: < bb43 bb49 bb59 bb3 bb31 bb41 > [ 77, bb43 ]
116bb:
117  %i = alloca [420 x i8], align 1
118  %i2 = getelementptr inbounds [420 x i8], [420 x i8]* %i, i64 0, i64 390
119  br label %bb3
120
121bb3:                                              ; preds = %bb59, %bb
122  %i4 = phi i8* [ %i2, %bb ], [ %i60, %bb59 ]
123  %i5 = phi i8 [ 77, %bb ], [ %i64, %bb59 ]
124  %i6 = phi i32 [ 2, %bb ], [ %i63, %bb59 ]
125  %i7 = phi i32 [ 26, %bb ], [ %i62, %bb59 ]
126  %i8 = phi i32 [ 25, %bb ], [ %i61, %bb59 ]
127  %i9 = icmp sgt i32 %i7, 2
128  %i10 = select i1 %i9, i32 %i7, i32 2
129  %i11 = add i32 %i8, 2
130  %i12 = sub i32 %i11, %i10
131  %i13 = mul nsw i32 %i12, 3
132  %i14 = add nsw i32 %i13, %i6
133  %i15 = sext i32 %i14 to i64
134  %i16 = getelementptr inbounds i8, i8* %i4, i64 %i15
135  %i17 = load i8, i8* %i16, align 1
136  %i18 = icmp sgt i8 %i17, 0
137  br i1 %i18, label %bb21, label %bb31
138
139bb21:                                             ; preds = %bb3
140  br i1 true, label %bb59, label %bb43
141
142bb59:                                             ; preds = %bb49, %bb43, %bb31, %bb21
143  %i60 = phi i8* [ %i44, %bb49 ], [ %i44, %bb43 ], [ %i34, %bb31 ], [ %i4, %bb21 ]
144  %i61 = phi i32 [ %i45, %bb49 ], [ %i45, %bb43 ], [ %i33, %bb31 ], [ %i8, %bb21 ]
145  %i62 = phi i32 [ %i47, %bb49 ], [ %i47, %bb43 ], [ %i32, %bb31 ], [ %i7, %bb21 ]
146  %i63 = phi i32 [ %i48, %bb49 ], [ %i48, %bb43 ], [ 2, %bb31 ], [ %i6, %bb21 ]
147  %i64 = phi i8 [ %i46, %bb49 ], [ %i46, %bb43 ], [ 77, %bb31 ], [ %i5, %bb21 ]
148  %i65 = icmp sgt i32 %i62, 0
149  br i1 %i65, label %bb3, label %bb66
150
151bb31:                                             ; preds = %bb3
152  %i32 = add nsw i32 %i7, -1
153  %i33 = add nsw i32 %i8, -1
154  %i34 = getelementptr inbounds i8, i8* %i4, i64 -15
155  %i35 = icmp eq i8 %i5, 77
156  br i1 %i35, label %bb59, label %bb41
157
158bb41:                                             ; preds = %bb31
159  tail call void @baz()
160  br label %bb43
161
162bb43:                                             ; preds = %bb41, %bb21
163  %i44 = phi i8* [ %i34, %bb41 ], [ %i4, %bb21 ]
164  %i45 = phi i32 [ %i33, %bb41 ], [ %i8, %bb21 ]
165  %i46 = phi i8 [ 77, %bb41 ], [ %i5, %bb21 ]
166  %i47 = phi i32 [ %i32, %bb41 ], [ %i7, %bb21 ]
167  %i48 = phi i32 [ 2, %bb41 ], [ %i6, %bb21 ]
168  tail call void @baz()
169  switch i8 %i5, label %bb59 [
170    i8 68, label %bb49
171    i8 73, label %bb49
172  ]
173
174bb49:                                             ; preds = %bb43, %bb43
175  tail call void @baz()
176  br label %bb59
177
178bb66:                                             ; preds = %bb59
179  ret i32 0
180}
181