1 // RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -analyzer-config unroll-loops=true,cfg-loopexit=true -verify -std=c++11 -analyzer-config exploration_strategy=unexplored_first_queue %s
2 // RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -analyzer-config unroll-loops=true,cfg-loopexit=true,exploration_strategy=dfs -verify -std=c++11 -DDFS=1 %s
3 
4 void clang_analyzer_numTimesReached();
5 void clang_analyzer_warnIfReached();
6 
7 int getNum();
8 void foo(int &);
9 
10 int simple_unroll1() {
11   int a[9];
12   int k = 42;
13   for (int i = 0; i < 9; i++) {
14     clang_analyzer_numTimesReached(); // expected-warning {{9}}
15     a[i] = 42;
16   }
17   int b = 22 / (k - 42); // expected-warning {{Division by zero}}
18   return 0;
19 }
20 
21 int simple_unroll2() {
22   int a[9];
23   int k = 42;
24   int i;
25   for (i = 0; i < 9; i++) {
26     clang_analyzer_numTimesReached(); // expected-warning {{9}}
27     a[i] = 42;
28   }
29 
30   for (int j = 0; j <= 9; ++j) {
31     clang_analyzer_numTimesReached(); // expected-warning {{10}}
32     a[j] = 42;
33   }
34 
35   int b = 22 / (k - 42); // expected-warning {{Division by zero}}
36   return 0;
37 }
38 
39 int simple_unroll3_unsigned() {
40   int a[9];
41   int k = 42;
42   for (unsigned i = 0; i < 9; i++) {
43     clang_analyzer_numTimesReached(); // expected-warning {{9}}
44     a[i] = 42;
45   }
46   int b = 22 / (k - 42); // expected-warning {{Division by zero}}
47   return 0;
48 }
49 
50 int simple_unroll4_unsigned() {
51   int a[9];
52   int k = 42;
53   unsigned i;
54   for (i = (0); i < 9; i++) {
55     clang_analyzer_numTimesReached(); // expected-warning {{9}}
56     a[i] = 42;
57   }
58   int b = 22 / (k - 42); // expected-warning {{Division by zero}}
59   return 0;
60 }
61 
62 int simple_no_unroll1() {
63   int a[9];
64   int k = 42;
65   for (int i = 0; i < 9; i++) {
66     clang_analyzer_numTimesReached(); // expected-warning {{4}}
67     a[i] = 42;
68     foo(i);
69   }
70   int b = 22 / (k - 42); // expected-warning {{Division by zero}}
71   return 0;
72 }
73 
74 int simple_no_unroll2() {
75   int a[9];
76   int k = 42;
77   int i;
78   for (i = 0; i < 9; i++) {
79     clang_analyzer_numTimesReached(); // expected-warning {{4}}
80     a[i] = 42;
81     i += getNum();
82   }
83   int b = 22 / (k - 42); // expected-warning {{Division by zero}}
84   return 0;
85 }
86 
87 int simple_no_unroll3() {
88   int a[9];
89   int k = 42;
90   for (int i = 0; i < 9; i++) {
91     clang_analyzer_numTimesReached(); // expected-warning {{4}}
92     a[i] = 42;
93     (void)&i;
94   }
95   int b = 22 / (k - 42); // no-warning
96   return 0;
97 }
98 
99 int simple_no_unroll4() {
100   int a[9];
101   int k = 42;
102   int i;
103   for (i = 0; i < 9; i++) {
104     clang_analyzer_numTimesReached(); // expected-warning {{4}}
105     a[i] = 42;
106     int &j = i;
107   }
108   int b = 22 / (k - 42); // no-warning
109   return 0;
110 }
111 
112 int simple_no_unroll5() {
113   int a[9];
114   int k = 42;
115   int i;
116   for (i = 0; i < 9; i++) {
117     clang_analyzer_numTimesReached(); // expected-warning {{4}}
118     a[i] = 42;
119     int &j{i};
120   }
121   int b = 22 / (k - 42); // no-warning
122   return 0;
123 }
124 
125 int no_unroll_assignment() {
126   for (int i = 0; i < 9; i++) {
127     i = i + 1;
128     clang_analyzer_numTimesReached(); // expected-warning {{4}}
129   }
130   return 0;
131 }
132 
133 int no_unroll_assignment2() {
134   for (int i = 0; i < 9; i++) {
135     i *= 2;
136     clang_analyzer_numTimesReached(); // expected-warning {{4}}
137   }
138   return 0;
139 }
140 
141 int no_unroll_assignment3() {
142   for (int i = 128; i > 0; i--) {
143     i /= 2;
144     clang_analyzer_numTimesReached(); // expected-warning {{4}}
145   }
146   return 0;
147 }
148 
149 int no_unroll_assignment4() {
150   for (int i = 0; i < 9; i++) {
151     i -= 2;
152     clang_analyzer_numTimesReached(); // expected-warning {{4}}
153   }
154   return 0;
155 }
156 
157 int no_unroll_assignment5() {
158   for (int i = 0; i < 9; i++) {
159     i += 1;
160     clang_analyzer_numTimesReached(); // expected-warning {{4}}
161   }
162   return 0;
163 }
164 
165 int no_unroll_assignment6() {
166   for (int i = 128; i > 0; i--) {
167     i >>= 1;
168     clang_analyzer_numTimesReached(); // expected-warning {{4}}
169   }
170   return 0;
171 }
172 
173 int no_unroll_assignment7() {
174   for (int i = 0; i < 512; i++) {
175     i <<= 1;
176     clang_analyzer_numTimesReached(); // expected-warning {{4}}
177   }
178   return 0;
179 }
180 
181 int no_unroll_assignment8() {
182   for (int i = 0; i < 9; i++) {
183     i %= 8;
184     clang_analyzer_numTimesReached(); // expected-warning {{4}}
185   }
186   return 0;
187 }
188 
189 int no_unroll_assignment9() {
190   for (int i = 0; i < 9; i++) {
191     i &= 31;
192     clang_analyzer_numTimesReached(); // expected-warning {{4}}
193   }
194   return 0;
195 }
196 
197 int no_unroll_assignment10() {
198   for (int i = 0; i < 9; i++) {
199     i |= 2;
200     clang_analyzer_numTimesReached(); // expected-warning {{4}}
201   }
202   return 0;
203 }
204 
205 int no_unroll_assignment11() {
206   for (int i = 0; i < 9; i++) {
207     i ^= 2;
208     clang_analyzer_numTimesReached(); // expected-warning {{4}}
209   }
210   return 0;
211 }
212 
213 int make_new_branches_loop_cached() {
214   for (int i = 0; i < 8; i++) {
215     clang_analyzer_numTimesReached(); // expected-warning {{4}}
216     if (getNum()) {
217       (void)i; // Since this Stmt does not change the State the analyzer
218                // won't make a new execution path but reuse the earlier nodes.
219     }
220   }
221   clang_analyzer_warnIfReached(); // no-warning
222   return 0;
223 }
224 
225 int make_new_branches_loop_uncached() {
226   int l = 2;
227   for (int i = 0; i < 8; i++) {
228     clang_analyzer_numTimesReached(); // expected-warning {{10}}
229     if (getNum()) {
230       ++l;
231     }
232   }
233   clang_analyzer_warnIfReached(); // no-warning
234   return 0;
235 }
236 
237 int make_new_branches_loop_uncached2() {
238   int l = 2;
239   for (int i = 0; i < 8; i++) {
240     clang_analyzer_numTimesReached(); // expected-warning {{10}}
241     if (getNum()) {
242       ++l;
243     }
244     (void)&i; // This ensures that the loop won't be unrolled.
245   }
246   clang_analyzer_warnIfReached(); // no-warning
247   return 0;
248 }
249 
250 
251 int escape_before_loop_no_unroll1() {
252   int a[9];
253   int k = 42;
254   int i;
255   int &j = i;
256   for (i = 0; i < 9; i++) {
257     clang_analyzer_numTimesReached(); // expected-warning {{4}}
258     a[i] = 42;
259   }
260   int b = 22 / (k - 42); // no-warning
261   return 0;
262 }
263 
264 int escape_before_loop_no_unroll2() {
265   int a[9];
266   int k = 42;
267   int i;
268   int *p = &i;
269   for (i = 0; i < 9; i++) {
270     clang_analyzer_numTimesReached(); // expected-warning {{4}}
271     a[i] = 42;
272   }
273   int b = 22 / (k - 42); // no-warning
274   return 0;
275 }
276 
277 int escape_before_loop_no_unroll3() {
278   int a[9];
279   int k = 42;
280   int i;
281   foo(i);
282   for (i = 0; i < 9; i++) {
283     clang_analyzer_numTimesReached(); // expected-warning {{4}}
284     a[i] = 42;
285   }
286   int b = 22 / (k - 42); // no-warning
287   return 0;
288 }
289 
290 int nested_outer_unrolled() {
291   int a[9];
292   int k = 42;
293   int j = 0;
294   for (int i = 0; i < 9; i++) {
295     clang_analyzer_numTimesReached(); // expected-warning {{1}}
296     for (j = 0; j < 9; ++j) {
297       clang_analyzer_numTimesReached(); // expected-warning {{4}}
298       a[j] = 22;
299       (void)&j; // ensures that the inner loop won't be unrolled
300     }
301     a[i] = 42;
302   }
303   int b = 22 / (k - 42); // no-warning
304   return 0;
305 }
306 
307 int nested_inner_unrolled() {
308   int a[9];
309   int k = 42;
310   int j = 0;
311   for (int i = 0; i < getNum(); i++) {
312     clang_analyzer_numTimesReached(); // expected-warning {{4}}
313     for (j = 0; j < 8; ++j) {
314       clang_analyzer_numTimesReached(); // expected-warning {{32}}
315       a[j] = 22;
316     }
317     a[i] = 42;
318   }
319   int b = 22 / (k - 42); // expected-warning {{Division by zero}}
320   return 0;
321 }
322 
323 int nested_both_unrolled() {
324   int a[9];
325   int k = 42;
326   int j = 0;
327   for (int i = 0; i < 7; i++) {
328     clang_analyzer_numTimesReached(); // expected-warning {{7}}
329     for (j = 0; j < 6; ++j) {
330       clang_analyzer_numTimesReached(); // expected-warning {{42}}
331       a[j] = 22;
332     }
333     a[i] = 42;
334   }
335   int b = 22 / (k - 42); // expected-warning {{Division by zero}}
336   return 0;
337 }
338 
339 int simple_known_bound_loop() {
340   for (int i = 2; i < 12; i++) {
341     // This function is inlined in nested_inlined_unroll1()
342     clang_analyzer_numTimesReached(); // expected-warning {{90}}
343   }
344   return 0;
345 }
346 
347 int simple_unknown_bound_loop() {
348   for (int i = 2; i < getNum(); i++) {
349 #ifdef DFS
350     clang_analyzer_numTimesReached(); // expected-warning {{10}}
351 #else
352     clang_analyzer_numTimesReached(); // expected-warning {{13}}
353 #endif
354   }
355   return 0;
356 }
357 
358 int nested_inlined_unroll1() {
359   int k;
360   for (int i = 0; i < 9; i++) {
361     clang_analyzer_numTimesReached(); // expected-warning {{9}}
362     k = simple_known_bound_loop();    // no reevaluation without inlining
363   }
364   int a = 22 / k; // expected-warning {{Division by zero}}
365   return 0;
366 }
367 
368 int nested_inlined_no_unroll1() {
369   int k;
370   for (int i = 0; i < 9; i++) {
371     clang_analyzer_numTimesReached(); // expected-warning {{15}}
372     k = simple_unknown_bound_loop();  // reevaluation without inlining, splits the state as well
373   }
374   int a = 22 / k; // no-warning
375   return 0;
376 }
377 
378 int recursion_unroll1(bool b) {
379   int k = 2;
380   for (int i = 0; i < 5; i++) {
381     clang_analyzer_numTimesReached(); // expected-warning {{13}}
382     if (i == 0 && b)                  // Splits the state in the first iteration but the recursion
383                                       // call will be unrolled anyway since the condition is known there.
384       recursion_unroll1(false);
385     clang_analyzer_numTimesReached(); // expected-warning {{14}}
386   }
387   int a = 22 / k; // no-warning
388   return 0;
389 }
390 
391 int recursion_unroll2(bool b) {
392   int k = 0;
393   for (int i = 0; i < 5; i++) {
394     clang_analyzer_numTimesReached(); // expected-warning {{9}}
395     if (i == 0 && b)
396       recursion_unroll2(false);
397     clang_analyzer_numTimesReached(); // expected-warning {{9}}
398   }
399   int a = 22 / k; // expected-warning {{Division by zero}}
400   return 0;
401 }
402 
403 int recursion_unroll3(bool b) {
404   int k = 2;
405   for (int i = 0; i < 5; i++) {
406     clang_analyzer_numTimesReached(); // expected-warning {{10}}
407     if (i == 4 && b) {
408       recursion_unroll3(false);
409       break;
410     }
411     clang_analyzer_numTimesReached(); // expected-warning {{10}}
412   }
413   int a = 22 / k;
414   return 0;
415 }
416 
417 int recursion_unroll4(bool b) {
418   int k = 2;
419   for (int i = 0; i < 5; i++) {
420     clang_analyzer_numTimesReached(); // expected-warning {{13}}
421     if (i == 0 && b) {
422       recursion_unroll4(false);
423       continue;
424     }
425     clang_analyzer_numTimesReached(); // expected-warning {{13}}
426   }
427   int a = 22 / k;
428   return 0;
429 }
430 
431 int loop_exit_while_empty_loop_stack() {
432   if (getNum())
433     for (int i = 1; i < 8; i++)
434       ;
435   return 0;
436 }
437 
438 int num_steps_on_limit() {
439   for (int i = 0; i < 128; i++) {
440     clang_analyzer_numTimesReached(); // expected-warning {{128}}
441   }
442   clang_analyzer_numTimesReached(); // expected-warning {{1}}
443   return 0;
444 }
445 
446 int num_steps_over_limit1() {
447   for (int i = 0; i < 129; i++) {
448     clang_analyzer_numTimesReached(); // expected-warning {{4}}
449   }
450   return 0;
451 }
452 
453 int num_steps_on_limit2() {
454   for (int i = 0; i < 2; i++) {
455     for (int j = 0; j < 64; j++) {
456       clang_analyzer_numTimesReached(); // expected-warning {{128}}
457     }
458   }
459   return 0;
460 }
461 
462 int num_steps_over_limit2() {
463   for (int i = 0; i < 2; i++) {
464     clang_analyzer_numTimesReached(); // expected-warning {{1}}
465     for (int j = 0; j <= 64; j++) {
466       clang_analyzer_numTimesReached(); // expected-warning {{4}}
467     }
468   }
469   return 0;
470 }
471 
472 int num_steps_on_limit3() {
473   for (int i = 0; i < getNum(); i++) {
474     clang_analyzer_numTimesReached(); // expected-warning {{4}}
475     for (int j = 0; j < 32; j++) {
476       clang_analyzer_numTimesReached(); // expected-warning {{128}}
477     }
478   }
479   return 0;
480 }
481 
482 int num_steps_over_limit3() {
483   for (int i = 0; i < getNum(); i++) {
484     clang_analyzer_numTimesReached(); // expected-warning {{1}}
485     for (int j = 0; j < 33; j++) {
486       clang_analyzer_numTimesReached(); // expected-warning {{4}}
487     }
488   }
489   return 0;
490 }
491 
492 
493 void pr34943() {
494   for (int i = 0; i < 6L; ++i) {
495     clang_analyzer_numTimesReached(); // expected-warning {{6}}
496   }
497 }
498