1 // RUN: %clang_analyze_cc1 %s \
2 // RUN: -analyzer-checker=debug.DumpDominators \
3 // RUN: -analyzer-checker=debug.DumpPostDominators \
4 // RUN: -analyzer-checker=debug.DumpControlDependencies \
5 // RUN: 2>&1 | FileCheck %s
6
7 // Test the DominatorsTree implementation with various control flows
test1()8 int test1()
9 {
10 int x = 6;
11 int y = x/2;
12 int z;
13
14 while(y > 0) {
15 if(y < x) {
16 x = x/y;
17 y = y-1;
18 }else{
19 z = x - y;
20 }
21 x = x - 1;
22 x = x - 1;
23 }
24 z = x+y;
25 z = 3;
26 return 0;
27 }
28
29 // [B9 (ENTRY)] -> [B8] -> [B7] -> [B6] -> [B5] -> [B3] -> [B2]
30 // |\ \ / /
31 // | \ ---> [B4] ---> /
32 // | <---------------------------
33 // V
34 // [B1] -> [B0 (EXIT)]
35
36 // CHECK: Control dependencies (Node#,Dependency#):
37 // CHECK-NEXT: (2,7)
38 // CHECK-NEXT: (3,7)
39 // CHECK-NEXT: (4,6)
40 // CHECK-NEXT: (4,7)
41 // CHECK-NEXT: (5,6)
42 // CHECK-NEXT: (5,7)
43 // CHECK-NEXT: (6,7)
44 // CHECK-NEXT: (7,7)
45 // CHECK-NEXT: Immediate dominance tree (Node#,IDom#):
46 // CHECK-NEXT: (0,1)
47 // CHECK-NEXT: (1,7)
48 // CHECK-NEXT: (2,3)
49 // CHECK-NEXT: (3,6)
50 // CHECK-NEXT: (4,6)
51 // CHECK-NEXT: (5,6)
52 // CHECK-NEXT: (6,7)
53 // CHECK-NEXT: (7,8)
54 // CHECK-NEXT: (8,9)
55 // CHECK-NEXT: (9,9)
56 // CHECK-NEXT: Immediate post dominance tree (Node#,IDom#):
57 // CHECK-NEXT: (0,0)
58 // CHECK-NEXT: (1,0)
59 // CHECK-NEXT: (2,7)
60 // CHECK-NEXT: (3,2)
61 // CHECK-NEXT: (4,3)
62 // CHECK-NEXT: (5,3)
63 // CHECK-NEXT: (6,3)
64 // CHECK-NEXT: (7,1)
65 // CHECK-NEXT: (8,7)
66 // CHECK-NEXT: (9,8)
67
test2()68 int test2()
69 {
70 int x,y,z;
71
72 x = 10; y = 100;
73 if(x > 0){
74 y = 1;
75 }else{
76 while(x<=0){
77 x++;
78 y++;
79 }
80 }
81 z = y;
82
83 return 0;
84 }
85
86 // <-------------
87 // / \
88 // -----------> [B4] -> [B3] -> [B2]
89 // / |
90 // / V
91 // [B7 (ENTRY)] -> [B6] -> [B5] -> [B1] -> [B0 (EXIT)]
92
93 // CHECK: Control dependencies (Node#,Dependency#):
94 // CHECK-NEXT: (2,4)
95 // CHECK-NEXT: (2,6)
96 // CHECK-NEXT: (3,4)
97 // CHECK-NEXT: (3,6)
98 // CHECK-NEXT: (4,6)
99 // CHECK-NEXT: (4,4)
100 // CHECK-NEXT: (5,6)
101 // CHECK-NEXT: Immediate dominance tree (Node#,IDom#):
102 // CHECK-NEXT: (0,1)
103 // CHECK-NEXT: (1,6)
104 // CHECK-NEXT: (2,3)
105 // CHECK-NEXT: (3,4)
106 // CHECK-NEXT: (4,6)
107 // CHECK-NEXT: (5,6)
108 // CHECK-NEXT: (6,7)
109 // CHECK-NEXT: (7,7)
110 // CHECK-NEXT: Immediate post dominance tree (Node#,IDom#):
111 // CHECK-NEXT: (0,0)
112 // CHECK-NEXT: (1,0)
113 // CHECK-NEXT: (2,4)
114 // CHECK-NEXT: (3,2)
115 // CHECK-NEXT: (4,1)
116 // CHECK-NEXT: (5,1)
117 // CHECK-NEXT: (6,1)
118 // CHECK-NEXT: (7,6)
119
test3()120 int test3()
121 {
122 int x,y,z;
123
124 x = y = z = 1;
125 if(x>0) {
126 while(x>=0){
127 while(y>=x) {
128 x = x-1;
129 y = y/2;
130 }
131 }
132 }
133 z = y;
134
135 return 0;
136 }
137
138 // <- [B2] <-
139 // / \
140 // [B8 (ENTRY)] -> [B7] -> [B6] ---> [B5] -> [B4] -> [B3]
141 // \ | \ /
142 // \ | <-------------
143 // \ \
144 // --------> [B1] -> [B0 (EXIT)]
145
146 // CHECK: Control dependencies (Node#,Dependency#):
147 // CHECK-NEXT: (2,6)
148 // CHECK-NEXT: (2,7)
149 // CHECK-NEXT: (3,5)
150 // CHECK-NEXT: (3,6)
151 // CHECK-NEXT: (3,7)
152 // CHECK-NEXT: (4,5)
153 // CHECK-NEXT: (4,6)
154 // CHECK-NEXT: (4,7)
155 // CHECK-NEXT: (5,6)
156 // CHECK-NEXT: (5,5)
157 // CHECK-NEXT: (5,7)
158 // CHECK-NEXT: (6,7)
159 // CHECK-NEXT: (6,6)
160 // CHECK-NEXT: Immediate dominance tree (Node#,IDom#):
161 // CHECK-NEXT: (0,1)
162 // CHECK-NEXT: (1,7)
163 // CHECK-NEXT: (2,5)
164 // CHECK-NEXT: (3,4)
165 // CHECK-NEXT: (4,5)
166 // CHECK-NEXT: (5,6)
167 // CHECK-NEXT: (6,7)
168 // CHECK-NEXT: (7,8)
169 // CHECK-NEXT: (8,8)
170 // CHECK-NEXT: Immediate post dominance tree (Node#,IDom#):
171 // CHECK-NEXT: (0,0)
172 // CHECK-NEXT: (1,0)
173 // CHECK-NEXT: (2,6)
174 // CHECK-NEXT: (3,5)
175 // CHECK-NEXT: (4,3)
176 // CHECK-NEXT: (5,2)
177 // CHECK-NEXT: (6,1)
178 // CHECK-NEXT: (7,1)
179 // CHECK-NEXT: (8,7)
180
test4()181 int test4()
182 {
183 int y = 3;
184 while(y > 0) {
185 if(y < 3) {
186 while(y>0)
187 y ++;
188 }else{
189 while(y<10)
190 y ++;
191 }
192 }
193 return 0;
194 }
195
196 // <----------------------------------
197 // / <----------------- \
198 // / / \ \
199 // [B12 (ENTRY)] -> [B11] -> [B10]-> [B9] -> [B8] ---> [B7] -> [B6] |
200 // | \ \ /
201 // | \ -----> [B2] --------/
202 // | \ /
203 // | -> [B5] -> [B4] -> [B3]
204 // | \ /
205 // | <------------
206 // \
207 // -> [B1] -> [B0 (EXIT)]
208
209 // CHECK: Control dependencies (Node#,Dependency#):
210 // CHECK-NEXT: (2,10)
211 // CHECK-NEXT: (3,5)
212 // CHECK-NEXT: (3,9)
213 // CHECK-NEXT: (3,10)
214 // CHECK-NEXT: (4,5)
215 // CHECK-NEXT: (4,9)
216 // CHECK-NEXT: (4,10)
217 // CHECK-NEXT: (5,9)
218 // CHECK-NEXT: (5,5)
219 // CHECK-NEXT: (5,10)
220 // CHECK-NEXT: (6,8)
221 // CHECK-NEXT: (6,9)
222 // CHECK-NEXT: (6,10)
223 // CHECK-NEXT: (7,8)
224 // CHECK-NEXT: (7,9)
225 // CHECK-NEXT: (7,10)
226 // CHECK-NEXT: (8,9)
227 // CHECK-NEXT: (8,8)
228 // CHECK-NEXT: (8,10)
229 // CHECK-NEXT: (9,10)
230 // CHECK-NEXT: (10,10)
231 // CHECK-NEXT: Immediate dominance tree (Node#,IDom#):
232 // CHECK-NEXT: (0,1)
233 // CHECK-NEXT: (1,10)
234 // CHECK-NEXT: (2,9)
235 // CHECK-NEXT: (3,4)
236 // CHECK-NEXT: (4,5)
237 // CHECK-NEXT: (5,9)
238 // CHECK-NEXT: (6,7)
239 // CHECK-NEXT: (7,8)
240 // CHECK-NEXT: (8,9)
241 // CHECK-NEXT: (9,10)
242 // CHECK-NEXT: (10,11)
243 // CHECK-NEXT: (11,12)
244 // CHECK-NEXT: (12,12)
245 // CHECK-NEXT: Immediate post dominance tree (Node#,IDom#):
246 // CHECK-NEXT: (0,0)
247 // CHECK-NEXT: (1,0)
248 // CHECK-NEXT: (2,10)
249 // CHECK-NEXT: (3,5)
250 // CHECK-NEXT: (4,3)
251 // CHECK-NEXT: (5,2)
252 // CHECK-NEXT: (6,8)
253 // CHECK-NEXT: (7,6)
254 // CHECK-NEXT: (8,2)
255 // CHECK-NEXT: (9,2)
256 // CHECK-NEXT: (10,1)
257 // CHECK-NEXT: (11,10)
258 // CHECK-NEXT: (12,11)
259
test5()260 int test5()
261 {
262 int x,y,z,a,b,c;
263 x = 1;
264 y = 2;
265 z = 3;
266 a = 4;
267 b = 5;
268 c = 6;
269 if ( x < 10 ) {
270 if ( y < 10 ) {
271 if ( z < 10 ) {
272 x = 4;
273 } else {
274 x = 5;
275 }
276 a = 10;
277 } else {
278 x = 6;
279 }
280 b = 10;
281 } else {
282 x = 7;
283 }
284 c = 11;
285 return 0;
286 }
287
288 // [B0 (EXIT)] <--
289 // \
290 // [B11 (ENTY)] -> [B10] -> [B9] -> [B8] -> [B7] -> [B5] -> [B3] -> [B1]
291 // | | | / / /
292 // | | V / / /
293 // | V [B6] --> / /
294 // V [B4] -----------------> /
295 // [B2]--------------------------------->
296
297 // CHECK: Control dependencies (Node#,Dependency#):
298 // CHECK-NEXT: (2,10)
299 // CHECK-NEXT: (3,10)
300 // CHECK-NEXT: (4,9)
301 // CHECK-NEXT: (4,10)
302 // CHECK-NEXT: (5,9)
303 // CHECK-NEXT: (5,10)
304 // CHECK-NEXT: (6,8)
305 // CHECK-NEXT: (6,9)
306 // CHECK-NEXT: (6,10)
307 // CHECK-NEXT: (7,8)
308 // CHECK-NEXT: (7,9)
309 // CHECK-NEXT: (7,10)
310 // CHECK-NEXT: (8,9)
311 // CHECK-NEXT: (8,10)
312 // CHECK-NEXT: (9,10)
313 // CHECK-NEXT: Immediate dominance tree (Node#,IDom#):
314 // CHECK-NEXT: (0,1)
315 // CHECK-NEXT: (1,10)
316 // CHECK-NEXT: (2,10)
317 // CHECK-NEXT: (3,9)
318 // CHECK-NEXT: (4,9)
319 // CHECK-NEXT: (5,8)
320 // CHECK-NEXT: (6,8)
321 // CHECK-NEXT: (7,8)
322 // CHECK-NEXT: (8,9)
323 // CHECK-NEXT: (9,10)
324 // CHECK-NEXT: (10,11)
325 // CHECK-NEXT: (11,11)
326 // CHECK-NEXT: Immediate post dominance tree (Node#,IDom#):
327 // CHECK-NEXT: (0,0)
328 // CHECK-NEXT: (1,0)
329 // CHECK-NEXT: (2,1)
330 // CHECK-NEXT: (3,1)
331 // CHECK-NEXT: (4,3)
332 // CHECK-NEXT: (5,3)
333 // CHECK-NEXT: (6,5)
334 // CHECK-NEXT: (7,5)
335 // CHECK-NEXT: (8,5)
336 // CHECK-NEXT: (9,3)
337 // CHECK-NEXT: (10,1)
338 // CHECK-NEXT: (11,10)
339