additive-folding.cpp revision 1d8db493f86761df9470254a2ad572fc6abf1bf6 
1// RUN: %clang_cc1 -analyze -analyzer-checker=core,experimental.deadcode.UnreachableCode,unix.Malloc -verify -analyzer-constraints=basic %s
2// RUN: %clang_cc1 -analyze -analyzer-checker=core,experimental.deadcode.UnreachableCode,unix.Malloc -verify -analyzer-constraints=range %s
3
4// These are used to trigger warnings.
5typedef typeof(sizeof(int)) size_t;
6void *malloc(size_t);
7void free(void *);
8#define NULL ((void*)0)
9#define UINT_MAX (~0U)
10#define INT_MAX (UINT_MAX & (UINT_MAX >> 1))
11#define INT_MIN (-INT_MAX - 1)
12
13//---------------
14//  Plus/minus
15//---------------
16
17void separateExpressions (int a) {
18  int b = a + 1;
19  --b;
20
21  void *buf = malloc(1);
22  if (a != 0 && b == 0)
23    return; // expected-warning{{never executed}}
24  free(buf);
25}
26
27void oneLongExpression (int a) {
28  // Expression canonicalization should still allow this to work, even though
29  // the first term is on the left.
30  int b = 15 + a + 15 - 10 - 20;
31
32  void *buf = malloc(1);
33  if (a != 0 && b == 0)
34    return; // expected-warning{{never executed}}
35  free(buf);
36}
37
38void mixedTypes (int a) {
39  void *buf = malloc(1);
40
41  // Different additive types should not cause crashes when constant-folding.
42  // This is part of PR7406.
43  int b = a + 1LL;
44  if (a != 0 && (b-1) == 0) // not crash
45    return; // expected-warning{{never executed}}
46
47  int c = a + 1U;
48  if (a != 0 && (c-1) == 0) // not crash
49    return; // expected-warning{{never executed}}
50
51  free(buf);
52}
53
54//---------------
55//  Comparisons
56//---------------
57
58// Equality and inequality only
59void eq_ne (unsigned a) {
60  void *b = NULL;
61  if (a == UINT_MAX)
62    b = malloc(1);
63  if (a+1 != 0)
64    return; // no-warning
65  if (a-1 != UINT_MAX-1)
66    return; // no-warning
67  free(b);
68}
69
70void ne_eq (unsigned a) {
71  void *b = NULL;
72  if (a != UINT_MAX)
73    b = malloc(1);
74  if (a+1 == 0)
75    return; // no-warning
76  if (a-1 == UINT_MAX-1)
77    return; // no-warning
78  free(b);
79}
80
81// Mixed typed inequalities (part of PR7406)
82// These should not crash.
83void mixed_eq_ne (int a) {
84  void *b = NULL;
85  if (a == 1)
86    b = malloc(1);
87  if (a+1U != 2)
88    return; // no-warning
89  if (a-1U != 0)
90    return; // expected-warning{{never executed}}
91  free(b);
92}
93
94void mixed_ne_eq (int a) {
95  void *b = NULL;
96  if (a != 1)
97    b = malloc(1);
98  if (a+1U == 2)
99    return; // no-warning
100  if (a-1U == 0)
101    return; // expected-warning{{never executed}}
102  free(b);
103}
104
105
106// Simple order comparisons with no adjustment
107void baselineGT (unsigned a) {
108  void *b = NULL;
109  if (a > 0)
110    b = malloc(1);
111  if (a == 0)
112    return; // no-warning
113  free(b);
114}
115
116void baselineGE (unsigned a) {
117  void *b = NULL;
118  if (a >= UINT_MAX)
119    b = malloc(1);
120  if (a == UINT_MAX)
121    free(b);
122  return; // no-warning
123}
124
125void baselineLT (unsigned a) {
126  void *b = NULL;
127  if (a < UINT_MAX)
128    b = malloc(1);
129  if (a == UINT_MAX)
130    return; // no-warning
131  free(b);
132}
133
134void baselineLE (unsigned a) {
135  void *b = NULL;
136  if (a <= 0)
137    b = malloc(1);
138  if (a == 0)
139    free(b);
140  return; // no-warning
141}
142
143
144// Adjustment gives each of these an extra solution!
145void adjustedGT (unsigned a) {
146  void *b = NULL;
147  if (a-1 > UINT_MAX-1)
148    b = malloc(1);
149  return; // expected-warning{{leak}}
150}
151
152void adjustedGE (unsigned a) {
153  void *b = NULL;
154  if (a-1 >= UINT_MAX-1)
155    b = malloc(1);
156  if (a == UINT_MAX)
157    free(b);
158  return; // expected-warning{{leak}}
159}
160
161void adjustedLT (unsigned a) {
162  void *b = NULL;
163  if (a+1 < 1)
164    b = malloc(1);
165  return; // expected-warning{{leak}}
166}
167
168void adjustedLE (unsigned a) {
169  void *b = NULL;
170  if (a+1 <= 1)
171    b = malloc(1);
172  if (a == 0)
173    free(b);
174  return; // expected-warning{{leak}}
175}
176
177
178// Tautologies
179void tautologyGT (unsigned a) {
180  void *b = malloc(1);
181  if (a > UINT_MAX)
182    return; // no-warning
183  free(b);
184}
185
186void tautologyGE (unsigned a) {
187  void *b = malloc(1);
188  if (a >= 0) // expected-warning{{always true}}
189    free(b);
190  return; // no-warning
191}
192
193void tautologyLT (unsigned a) {
194  void *b = malloc(1);
195  if (a < 0) // expected-warning{{always false}}
196    return; // expected-warning{{never executed}}
197  free(b);
198}
199
200void tautologyLE (unsigned a) {
201  void *b = malloc(1);
202  if (a <= UINT_MAX)
203    free(b);
204  return; // no-warning
205}
206
207
208// Tautologies from outside the range of the symbol
209void tautologyOutsideGT(unsigned char a) {
210  void *b = malloc(1);
211  if (a > 0x100)
212    return; // expected-warning{{never executed}}
213  if (a > -1)
214    free(b);
215  return; // no-warning
216}
217
218void tautologyOutsideGE(unsigned char a) {
219  void *b = malloc(1);
220  if (a >= 0x100)
221    return; // expected-warning{{never executed}}
222  if (a >= -1)
223    free(b);
224  return; // no-warning
225}
226
227void tautologyOutsideLT(unsigned char a) {
228  void *b = malloc(1);
229  if (a < -1)
230    return; // expected-warning{{never executed}}
231  if (a < 0x100)
232    free(b);
233  return; // no-warning
234}
235
236void tautologyOutsideLE (unsigned char a) {
237  void *b = malloc(1);
238  if (a <= -1)
239    return; // expected-warning{{never executed}}
240  if (a <= 0x100)
241    free(b);
242  return; // no-warning
243}
244
245void tautologyOutsideEQ(unsigned char a) {
246  if (a == 0x100)
247    malloc(1); // expected-warning{{never executed}}
248  if (a == -1)
249    malloc(1); // expected-warning{{never executed}}
250}
251
252void tautologyOutsideNE(unsigned char a) {
253  void *sentinel = malloc(1);
254  if (a != 0x100)
255    free(sentinel);
256
257  sentinel = malloc(1);
258  if (a != -1)
259    free(sentinel);
260}
261
262
263// Wraparound with mixed types. Note that the analyzer assumes
264// -fwrapv semantics.
265void mixedWraparoundSanityCheck(int a) {
266  int max = INT_MAX;
267  int min = INT_MIN;
268
269  int b = a + 1;
270  if (a == max && b != min)
271    return; // expected-warning{{never executed}}
272}
273
274void mixedWraparoundGT(int a) {
275  int max = INT_MAX;
276
277  if ((a + 2) > (max + 1LL))
278    return; // expected-warning{{never executed}}
279}
280
281void mixedWraparoundGE(int a) {
282  int max = INT_MAX;
283  int min = INT_MIN;
284
285  if ((a + 2) >= (max + 1LL))
286    return; // expected-warning{{never executed}}
287
288  void *sentinel = malloc(1);
289  if ((a - 2LL) >= min)
290    free(sentinel);
291  return; // expected-warning{{leak}}
292}
293
294void mixedWraparoundLT(int a) {
295  int min = INT_MIN;
296
297  if ((a - 2) < (min - 1LL))
298    return; // expected-warning{{never executed}}
299}
300
301void mixedWraparoundLE(int a) {
302  int max = INT_MAX;
303  int min = INT_MIN;
304
305  if ((a - 2) <= (min - 1LL))
306    return; // expected-warning{{never executed}}
307
308  void *sentinel = malloc(1);
309  if ((a + 2LL) <= max)
310    free(sentinel);
311  return; // expected-warning{{leak}}
312}
313
314void mixedWraparoundEQ(int a) {
315  int max = INT_MAX;
316
317  if ((a + 2) == (max + 1LL))
318    return; // expected-warning{{never executed}}
319}
320
321void mixedWraparoundNE(int a) {
322  int max = INT_MAX;
323
324  void *sentinel = malloc(1);
325  if ((a + 2) != (max + 1LL))
326    free(sentinel);
327  return; // no-warning
328}
329
330
331// Mixed-signedness comparisons.
332void mixedSignedness(int a, unsigned b) {
333  int sMin = INT_MIN;
334  unsigned uMin = INT_MIN;
335  if (a == sMin && a != uMin)
336    return; // expected-warning{{never executed}}
337  if (b == uMin && b != sMin)
338    return; // expected-warning{{never executed}}
339}
340
341
342// PR12206/12510 - When SimpleSValBuilder figures out that a symbol is fully
343// constrained, it should cast the value to the result type in a binary
344// operation...unless the binary operation is a comparison, in which case the
345// two arguments should be the same type, but won't match the result type.
346//
347// This is easier to trigger in C++ mode, where the comparison result type is
348// 'bool' and is thus differently sized from int on pretty much every system.
349//
350// This is not directly related to additive folding, but we use SValBuilder's
351// additive folding to tickle the bug. ExprEngine will simplify fully-constrained
352// symbols, so SValBuilder will only see them if they are (a) part of an evaluated
353// SymExpr (e.g. with additive folding) or (b) generated by a checker (e.g.
354// unix.cstring's strlen() modelling).
355void PR12206(int x) {
356  // Build a SymIntExpr, dependent on x.
357  int local = x - 1;
358
359  // Constrain the value of x.
360  int value = 1 + (1 << (8 * sizeof(1 == 1))); // not representable by bool
361  if (x != value) return;
362
363  // Constant-folding will turn (local+1) back into the symbol for x.
364  // The point of this dance is to make SValBuilder be responsible for
365  // turning the symbol into a ConcreteInt, rather than ExprEngine.
366
367  // Test relational operators.
368  if ((local + 1) < 2)
369    malloc(1); // expected-warning{{never executed}}
370  if (2 > (local + 1))
371    malloc(1); // expected-warning{{never executed}}
372
373  // Test equality operators.
374  if ((local + 1) == 1)
375    malloc(1); // expected-warning{{never executed}}
376  if (1 == (local + 1))
377    malloc(1); // expected-warning{{never executed}}
378}
379
380void PR12206_truncation(signed char x) {
381  // Build a SymIntExpr, dependent on x.
382  signed char local = x - 1;
383
384  // Constrain the value of x.
385  if (x != 1) return;
386
387  // Constant-folding will turn (local+1) back into the symbol for x.
388  // The point of this dance is to make SValBuilder be responsible for
389  // turning the symbol into a ConcreteInt, rather than ExprEngine.
390
391  // Construct a value that cannot be represented by 'char',
392  // but that has the same lower bits as x.
393  signed int value = 1 + (1 << 8);
394
395  // Test relational operators.
396  if ((local + 1) >= value)
397    malloc(1); // expected-warning{{never executed}}
398  if (value <= (local + 1))
399    malloc(1); // expected-warning{{never executed}}
400
401  // Test equality operators.
402  if ((local + 1) == value)
403    malloc(1); // expected-warning{{never executed}}
404  if (value == (local + 1))
405    malloc(1); // expected-warning{{never executed}}
406}
407
408void multiplicativeSanityTest(int x) {
409  // At one point we were ignoring the *4 completely -- the constraint manager
410  // would see x < 8 and then declare the next part unreachable.
411  if (x*4 < 8)
412    return;
413  if (x == 3)
414    malloc(1);
415  return; // expected-warning{{leak}}
416}
417