1 /*
2 * Copyright (C) 2010 Dan Carpenter.
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License
6 * as published by the Free Software Foundation; either version 2
7 * of the License, or (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
16 */
17
18 #include "symbol.h"
19 #include "smatch.h"
20 #include "smatch_slist.h"
21 #include "smatch_extra.h"
22
23 static struct range_list *_get_rl(struct expression *expr, int implied, int *recurse_cnt);
24 static struct range_list *handle_variable(struct expression *expr, int implied, int *recurse_cnt);
25 static struct range_list *(*custom_handle_variable)(struct expression *expr);
26
27 static int get_implied_value_internal(struct expression *expr, sval_t *sval, int *recurse_cnt);
28 static int get_absolute_rl_internal(struct expression *expr, struct range_list **rl, int *recurse_cnt);
29
30 static sval_t zero = {.type = &int_ctype, {.value = 0} };
31 static sval_t one = {.type = &int_ctype, {.value = 1} };
32
33 struct range_list *rl_zero(void)
34 {
35 static struct range_list *zero_perm;
36
37 if (!zero_perm)
38 zero_perm = clone_rl_permanent(alloc_rl(zero, zero));
39 return zero_perm;
40 }
41
42 struct range_list *rl_one(void)
43 {
44 static struct range_list *one_perm;
45
46 if (!one_perm)
47 one_perm = clone_rl_permanent(alloc_rl(one, one));
48
49 return one_perm;
50 }
51
52 enum {
53 RL_EXACT,
54 RL_HARD,
55 RL_FUZZY,
56 RL_IMPLIED,
57 RL_ABSOLUTE,
58 RL_REAL_ABSOLUTE,
59 };
60
61 static struct range_list *last_stmt_rl(struct statement *stmt, int implied, int *recurse_cnt)
62 {
63 struct expression *expr;
64
65 if (!stmt)
66 return NULL;
67
68 stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
69 if (stmt->type == STMT_LABEL) {
70 if (stmt->label_statement &&
71 stmt->label_statement->type == STMT_EXPRESSION)
72 expr = stmt->label_statement->expression;
73 else
74 return NULL;
75 } else if (stmt->type == STMT_EXPRESSION) {
76 expr = stmt->expression;
77 } else {
78 return NULL;
79 }
80 return _get_rl(expr, implied, recurse_cnt);
81 }
82
83 static struct range_list *handle_expression_statement_rl(struct expression *expr, int implied, int *recurse_cnt)
84 {
85 return last_stmt_rl(get_expression_statement(expr), implied, recurse_cnt);
86 }
87
88 static struct range_list *handle_ampersand_rl(struct expression *expr, int implied, int *recurse_cnt)
89 {
90 struct range_list *rl;
91 sval_t sval;
92
93 if (implied == RL_EXACT || implied == RL_HARD)
94 return NULL;
95 if (get_mtag_sval(expr, &sval))
96 return alloc_rl(sval, sval);
97 if (get_address_rl(expr, &rl))
98 return rl;
99 return alloc_rl(valid_ptr_min_sval, valid_ptr_max_sval);
100 }
101
102 static struct range_list *handle_negate_rl(struct expression *expr, int implied, int *recurse_cnt)
103 {
104 if (known_condition_true(expr->unop))
105 return rl_zero();
106 if (known_condition_false(expr->unop))
107 return rl_one();
108
109 if (implied == RL_EXACT)
110 return NULL;
111
112 if (implied_condition_true(expr->unop))
113 return rl_zero();
114 if (implied_condition_false(expr->unop))
115 return rl_one();
116 return alloc_rl(zero, one);
117 }
118
119 static struct range_list *handle_bitwise_negate(struct expression *expr, int implied, int *recurse_cnt)
120 {
121 struct range_list *rl;
122 sval_t sval;
123
124 rl = _get_rl(expr->unop, implied, recurse_cnt);
125 if (!rl_to_sval(rl, &sval))
126 return NULL;
127 sval = sval_preop(sval, '~');
128 sval_cast(get_type(expr->unop), sval);
129 return alloc_rl(sval, sval);
130 }
131
132 static struct range_list *handle_minus_preop(struct expression *expr, int implied, int *recurse_cnt)
133 {
134 struct range_list *rl;
135 sval_t min, max;
136
137 rl = _get_rl(expr->unop, implied, recurse_cnt);
138 min = sval_preop(rl_max(rl), '-');
139 max = sval_preop(rl_min(rl), '-');
140 return alloc_rl(min, max);
141 }
142
143 static struct range_list *handle_preop_rl(struct expression *expr, int implied, int *recurse_cnt)
144 {
145 switch (expr->op) {
146 case '&':
147 return handle_ampersand_rl(expr, implied, recurse_cnt);
148 case '!':
149 return handle_negate_rl(expr, implied, recurse_cnt);
150 case '~':
151 return handle_bitwise_negate(expr, implied, recurse_cnt);
152 case '-':
153 return handle_minus_preop(expr, implied, recurse_cnt);
154 case '*':
155 return handle_variable(expr, implied, recurse_cnt);
156 case '(':
157 return handle_expression_statement_rl(expr, implied, recurse_cnt);
158 default:
159 return NULL;
160 }
161 }
162
163 static struct range_list *handle_divide_rl(struct expression *expr, int implied, int *recurse_cnt)
164 {
165 struct range_list *left_rl, *right_rl;
166 struct symbol *type;
167
168 type = get_type(expr);
169
170 left_rl = _get_rl(expr->left, implied, recurse_cnt);
171 left_rl = cast_rl(type, left_rl);
172 right_rl = _get_rl(expr->right, implied, recurse_cnt);
173 right_rl = cast_rl(type, right_rl);
174
175 if (!left_rl || !right_rl)
176 return NULL;
177
178 if (implied != RL_REAL_ABSOLUTE) {
179 if (is_whole_rl(left_rl) || is_whole_rl(right_rl))
180 return NULL;
181 }
182
183 return rl_binop(left_rl, '/', right_rl);
184 }
185
186 static int handle_offset_subtraction(struct expression *expr)
187 {
188 struct expression *left, *right;
189 struct symbol *left_sym, *right_sym;
190 struct symbol *type;
191 int left_offset, right_offset;
192
193 type = get_type(expr);
194 if (!type || type->type != SYM_PTR)
195 return -1;
196 type = get_real_base_type(type);
197 if (!type || (type_bits(type) != 8 && (type != &void_ctype)))
198 return -1;
199
200 left = strip_expr(expr->left);
201 right = strip_expr(expr->right);
202
203 if (left->type != EXPR_PREOP || left->op != '&')
204 return -1;
205 left = strip_expr(left->unop);
206
207 left_sym = expr_to_sym(left);
208 right_sym = expr_to_sym(right);
209 if (!left_sym || left_sym != right_sym)
210 return -1;
211
212 left_offset = get_member_offset_from_deref(left);
213 if (right->type == EXPR_SYMBOL)
214 right_offset = 0;
215 else {
216 if (right->type != EXPR_PREOP || right->op != '&')
217 return -1;
218 right = strip_expr(right->unop);
219 right_offset = get_member_offset_from_deref(right);
220 }
221 if (left_offset < 0 || right_offset < 0)
222 return -1;
223
224 return left_offset - right_offset;
225 }
226
227 static struct range_list *handle_subtract_rl(struct expression *expr, int implied, int *recurse_cnt)
228 {
229 struct symbol *type;
230 struct range_list *left_orig, *right_orig;
231 struct range_list *left_rl, *right_rl;
232 sval_t max, min, tmp;
233 int comparison;
234 int offset;
235
236 type = get_type(expr);
237
238 offset = handle_offset_subtraction(expr);
239 if (offset >= 0) {
240 tmp.type = type;
241 tmp.value = offset;
242
243 return alloc_rl(tmp, tmp);
244 }
245
246 comparison = get_comparison(expr->left, expr->right);
247
248 left_orig = _get_rl(expr->left, implied, recurse_cnt);
249 left_rl = cast_rl(type, left_orig);
250 right_orig = _get_rl(expr->right, implied, recurse_cnt);
251 right_rl = cast_rl(type, right_orig);
252
253 if ((!left_rl || !right_rl) &&
254 (implied == RL_EXACT || implied == RL_HARD || implied == RL_FUZZY))
255 return NULL;
256
257 if (!left_rl)
258 left_rl = alloc_whole_rl(type);
259 if (!right_rl)
260 right_rl = alloc_whole_rl(type);
261
262 /* negative values complicate everything fix this later */
263 if (sval_is_negative(rl_min(right_rl)))
264 return NULL;
265 max = rl_max(left_rl);
266 min = sval_type_min(type);
267
268 switch (comparison) {
269 case '>':
270 case SPECIAL_UNSIGNED_GT:
271 min = sval_type_val(type, 1);
272 max = rl_max(left_rl);
273 break;
274 case SPECIAL_GTE:
275 case SPECIAL_UNSIGNED_GTE:
276 min = sval_type_val(type, 0);
277 max = rl_max(left_rl);
278 break;
279 case SPECIAL_EQUAL:
280 min = sval_type_val(type, 0);
281 max = sval_type_val(type, 0);
282 break;
283 case '<':
284 case SPECIAL_UNSIGNED_LT:
285 max = sval_type_val(type, -1);
286 break;
287 case SPECIAL_LTE:
288 case SPECIAL_UNSIGNED_LTE:
289 max = sval_type_val(type, 0);
290 break;
291 default:
292 if (!left_orig || !right_orig)
293 return NULL;
294 return rl_binop(left_rl, '-', right_rl);
295 }
296
297 if (!sval_binop_overflows(rl_min(left_rl), '-', rl_max(right_rl))) {
298 tmp = sval_binop(rl_min(left_rl), '-', rl_max(right_rl));
299 if (sval_cmp(tmp, min) > 0)
300 min = tmp;
301 }
302
303 if (!sval_is_max(rl_max(left_rl))) {
304 tmp = sval_binop(rl_max(left_rl), '-', rl_min(right_rl));
305 if (sval_cmp(tmp, max) < 0)
306 max = tmp;
307 }
308
309 if (sval_is_min(min) && sval_is_max(max))
310 return NULL;
311
312 return cast_rl(type, alloc_rl(min, max));
313 }
314
315 static struct range_list *handle_mod_rl(struct expression *expr, int implied, int *recurse_cnt)
316 {
317 struct range_list *rl;
318 sval_t left, right, sval;
319
320 if (implied == RL_EXACT) {
321 if (!get_implied_value(expr->right, &right))
322 return NULL;
323 if (!get_implied_value(expr->left, &left))
324 return NULL;
325 sval = sval_binop(left, '%', right);
326 return alloc_rl(sval, sval);
327 }
328 /* if we can't figure out the right side it's probably hopeless */
329 if (!get_implied_value_internal(expr->right, &right, recurse_cnt))
330 return NULL;
331
332 right = sval_cast(get_type(expr), right);
333 right.value--;
334
335 rl = _get_rl(expr->left, implied, recurse_cnt);
336 if (rl && rl_max(rl).uvalue < right.uvalue)
337 right.uvalue = rl_max(rl).uvalue;
338
339 return alloc_rl(sval_cast(right.type, zero), right);
340 }
341
342 static sval_t sval_lowest_set_bit(sval_t sval)
343 {
344 int i;
345 int found = 0;
346
347 for (i = 0; i < 64; i++) {
348 if (sval.uvalue & 1ULL << i) {
349 if (!found++)
350 continue;
351 sval.uvalue &= ~(1ULL << i);
352 }
353 }
354 return sval;
355 }
356
357 static struct range_list *handle_bitwise_AND(struct expression *expr, int implied, int *recurse_cnt)
358 {
359 struct symbol *type;
360 struct range_list *left_rl, *right_rl;
361 sval_t known;
362 int new_recurse;
363
364 if (implied != RL_IMPLIED && implied != RL_ABSOLUTE && implied != RL_REAL_ABSOLUTE)
365 return NULL;
366
367 type = get_type(expr);
368
369 if (get_implied_value_internal(expr->left, &known, recurse_cnt)) {
370 sval_t min;
371
372 min = sval_lowest_set_bit(known);
373 left_rl = alloc_rl(min, known);
374 left_rl = cast_rl(type, left_rl);
375 add_range(&left_rl, sval_type_val(type, 0), sval_type_val(type, 0));
376 } else {
377 left_rl = _get_rl(expr->left, implied, recurse_cnt);
378 if (left_rl) {
379 left_rl = cast_rl(type, left_rl);
380 left_rl = alloc_rl(sval_type_val(type, 0), rl_max(left_rl));
381 } else {
382 if (implied == RL_HARD)
383 return NULL;
384 left_rl = alloc_whole_rl(type);
385 }
386 }
387
388 new_recurse = *recurse_cnt;
389 if (*recurse_cnt >= 200)
390 new_recurse = 100; /* Let's try super hard to get the mask */
391 if (get_implied_value_internal(expr->right, &known, &new_recurse)) {
392 sval_t min, left_max, mod;
393
394 *recurse_cnt = new_recurse;
395
396 min = sval_lowest_set_bit(known);
397 right_rl = alloc_rl(min, known);
398 right_rl = cast_rl(type, right_rl);
399 add_range(&right_rl, sval_type_val(type, 0), sval_type_val(type, 0));
400
401 if (min.value != 0) {
402 left_max = rl_max(left_rl);
403 mod = sval_binop(left_max, '%', min);
404 if (mod.value) {
405 left_max = sval_binop(left_max, '-', mod);
406 left_max.value++;
407 if (left_max.value > 0 && sval_cmp(left_max, rl_max(left_rl)) < 0)
408 left_rl = remove_range(left_rl, left_max, rl_max(left_rl));
409 }
410 }
411 } else {
412 right_rl = _get_rl(expr->right, implied, recurse_cnt);
413 if (right_rl) {
414 right_rl = cast_rl(type, right_rl);
415 right_rl = alloc_rl(sval_type_val(type, 0), rl_max(right_rl));
416 } else {
417 if (implied == RL_HARD)
418 return NULL;
419 right_rl = alloc_whole_rl(type);
420 }
421 }
422
423 return rl_intersection(left_rl, right_rl);
424 }
425
426 static struct range_list *use_rl_binop(struct expression *expr, int implied, int *recurse_cnt)
427 {
428 struct symbol *type;
429 struct range_list *left_rl, *right_rl;
430
431 if (implied != RL_IMPLIED && implied != RL_ABSOLUTE && implied != RL_REAL_ABSOLUTE)
432 return NULL;
433
434 type = get_type(expr);
435
436 get_absolute_rl_internal(expr->left, &left_rl, recurse_cnt);
437 get_absolute_rl_internal(expr->right, &right_rl, recurse_cnt);
438 left_rl = cast_rl(type, left_rl);
439 right_rl = cast_rl(type, right_rl);
440 if (!left_rl || !right_rl)
441 return NULL;
442
443 return rl_binop(left_rl, expr->op, right_rl);
444 }
445
446 static struct range_list *handle_right_shift(struct expression *expr, int implied, int *recurse_cnt)
447 {
448 struct range_list *left_rl;
449 sval_t right;
450 sval_t min, max;
451
452 if (implied == RL_EXACT || implied == RL_HARD)
453 return NULL;
454
455 left_rl = _get_rl(expr->left, implied, recurse_cnt);
456 if (left_rl) {
457 max = rl_max(left_rl);
458 min = rl_min(left_rl);
459 } else {
460 if (implied == RL_FUZZY)
461 return NULL;
462 max = sval_type_max(get_type(expr->left));
463 min = sval_type_val(get_type(expr->left), 0);
464 }
465
466 if (get_implied_value_internal(expr->right, &right, recurse_cnt)) {
467 min = sval_binop(min, SPECIAL_RIGHTSHIFT, right);
468 max = sval_binop(max, SPECIAL_RIGHTSHIFT, right);
469 } else if (!sval_is_negative(min)) {
470 min.value = 0;
471 max = sval_type_max(max.type);
472 } else {
473 return NULL;
474 }
475
476 return alloc_rl(min, max);
477 }
478
479 static struct range_list *handle_left_shift(struct expression *expr, int implied, int *recurse_cnt)
480 {
481 struct range_list *left_rl, *res;
482 sval_t right;
483 sval_t min, max;
484 int add_zero = 0;
485
486 if (implied == RL_EXACT || implied == RL_HARD)
487 return NULL;
488 /* this is hopeless without the right side */
489 if (!get_implied_value_internal(expr->right, &right, recurse_cnt))
490 return NULL;
491 left_rl = _get_rl(expr->left, implied, recurse_cnt);
492 if (left_rl) {
493 max = rl_max(left_rl);
494 min = rl_min(left_rl);
495 if (min.value == 0) {
496 min.value = 1;
497 add_zero = 1;
498 }
499 } else {
500 if (implied == RL_FUZZY)
501 return NULL;
502 max = sval_type_max(get_type(expr->left));
503 min = sval_type_val(get_type(expr->left), 1);
504 add_zero = 1;
505 }
506
507 max = sval_binop(max, SPECIAL_LEFTSHIFT, right);
508 min = sval_binop(min, SPECIAL_LEFTSHIFT, right);
509 res = alloc_rl(min, max);
510 if (add_zero)
511 res = rl_union(res, rl_zero());
512 return res;
513 }
514
515 static struct range_list *handle_known_binop(struct expression *expr)
516 {
517 sval_t left, right;
518
519 if (!get_value(expr->left, &left))
520 return NULL;
521 if (!get_value(expr->right, &right))
522 return NULL;
523 left = sval_binop(left, expr->op, right);
524 return alloc_rl(left, left);
525 }
526
527 static int has_actual_ranges(struct range_list *rl)
528 {
529 struct data_range *tmp;
530
531 FOR_EACH_PTR(rl, tmp) {
532 if (sval_cmp(tmp->min, tmp->max) != 0)
533 return 1;
534 } END_FOR_EACH_PTR(tmp);
535 return 0;
536 }
537
538 static struct range_list *handle_implied_binop(struct range_list *left_rl, int op, struct range_list *right_rl)
539 {
540 struct range_list *res_rl;
541 struct data_range *left_drange, *right_drange;
542 sval_t res;
543
544 if (!left_rl || !right_rl)
545 return NULL;
546 if (has_actual_ranges(left_rl))
547 return NULL;
548 if (has_actual_ranges(right_rl))
549 return NULL;
550
551 if (ptr_list_size((struct ptr_list *)left_rl) * ptr_list_size((struct ptr_list *)right_rl) > 20)
552 return NULL;
553
554 res_rl = NULL;
555
556 FOR_EACH_PTR(left_rl, left_drange) {
557 FOR_EACH_PTR(right_rl, right_drange) {
558 if ((op == '%' || op == '/') &&
559 right_drange->min.value == 0)
560 return NULL;
561 res = sval_binop(left_drange->min, op, right_drange->min);
562 add_range(&res_rl, res, res);
563 } END_FOR_EACH_PTR(right_drange);
564 } END_FOR_EACH_PTR(left_drange);
565
566 return res_rl;
567 }
568
569 static struct range_list *handle_binop_rl(struct expression *expr, int implied, int *recurse_cnt)
570 {
571 struct smatch_state *state;
572 struct symbol *type;
573 struct range_list *left_rl, *right_rl, *rl;
574 sval_t min, max;
575
576 rl = handle_known_binop(expr);
577 if (rl)
578 return rl;
579 if (implied == RL_EXACT)
580 return NULL;
581
582 if (custom_handle_variable) {
583 rl = custom_handle_variable(expr);
584 if (rl)
585 return rl;
586 }
587
588 state = get_extra_state(expr);
589 if (state && !is_whole_rl(estate_rl(state))) {
590 if (implied != RL_HARD || estate_has_hard_max(state))
591 return clone_rl(estate_rl(state));
592 }
593
594 type = get_type(expr);
595 left_rl = _get_rl(expr->left, implied, recurse_cnt);
596 left_rl = cast_rl(type, left_rl);
597 right_rl = _get_rl(expr->right, implied, recurse_cnt);
598 right_rl = cast_rl(type, right_rl);
599
600 if (!left_rl && !right_rl)
601 return NULL;
602
603 rl = handle_implied_binop(left_rl, expr->op, right_rl);
604 if (rl)
605 return rl;
606
607 switch (expr->op) {
608 case '%':
609 return handle_mod_rl(expr, implied, recurse_cnt);
610 case '&':
611 return handle_bitwise_AND(expr, implied, recurse_cnt);
612 case '|':
613 case '^':
614 return use_rl_binop(expr, implied, recurse_cnt);
615 case SPECIAL_RIGHTSHIFT:
616 return handle_right_shift(expr, implied, recurse_cnt);
617 case SPECIAL_LEFTSHIFT:
618 return handle_left_shift(expr, implied, recurse_cnt);
619 case '-':
620 return handle_subtract_rl(expr, implied, recurse_cnt);
621 case '/':
622 return handle_divide_rl(expr, implied, recurse_cnt);
623 }
624
625 if (!left_rl || !right_rl)
626 return NULL;
627
628 if (sval_binop_overflows(rl_min(left_rl), expr->op, rl_min(right_rl)))
629 return NULL;
630 if (sval_binop_overflows(rl_max(left_rl), expr->op, rl_max(right_rl)))
631 return NULL;
632
633 min = sval_binop(rl_min(left_rl), expr->op, rl_min(right_rl));
634 max = sval_binop(rl_max(left_rl), expr->op, rl_max(right_rl));
635
636 return alloc_rl(min, max);
637 }
638
639 static int do_comparison(struct expression *expr)
640 {
641 struct range_list *left_ranges = NULL;
642 struct range_list *right_ranges = NULL;
643 int poss_true, poss_false;
644 struct symbol *type;
645
646 type = get_type(expr);
647 get_absolute_rl(expr->left, &left_ranges);
648 get_absolute_rl(expr->right, &right_ranges);
649
650 left_ranges = cast_rl(type, left_ranges);
651 right_ranges = cast_rl(type, right_ranges);
652
653 poss_true = possibly_true_rl(left_ranges, expr->op, right_ranges);
654 poss_false = possibly_false_rl(left_ranges, expr->op, right_ranges);
655
656 if (!poss_true && !poss_false)
657 return 0x0;
658 if (poss_true && !poss_false)
659 return 0x1;
660 if (!poss_true && poss_false)
661 return 0x2;
662 return 0x3;
663 }
664
665 static struct range_list *handle_comparison_rl(struct expression *expr, int implied, int *recurse_cnt)
666 {
667 sval_t left, right;
668 int res;
669
670 if (expr->op == SPECIAL_EQUAL && expr->left->type == EXPR_TYPE) {
671 struct symbol *left, *right;
672
673 left = get_real_base_type(expr->left->symbol);
674 right = get_real_base_type(expr->left->symbol);
675 if (left == right)
676 return rl_one();
677 return rl_zero();
678 }
679
680 if (get_value(expr->left, &left) && get_value(expr->right, &right)) {
681 struct data_range tmp_left, tmp_right;
682
683 tmp_left.min = left;
684 tmp_left.max = left;
685 tmp_right.min = right;
686 tmp_right.max = right;
687 if (true_comparison_range(&tmp_left, expr->op, &tmp_right))
688 return rl_one();
689 return rl_zero();
690 }
691
692 if (implied == RL_EXACT)
693 return NULL;
694
695 res = do_comparison(expr);
696 if (res == 1)
697 return rl_one();
698 if (res == 2)
699 return rl_zero();
700
701 return alloc_rl(zero, one);
702 }
703
704 static struct range_list *handle_logical_rl(struct expression *expr, int implied, int *recurse_cnt)
705 {
706 sval_t left, right;
707 int left_known = 0;
708 int right_known = 0;
709
710 if (implied == RL_EXACT) {
711 if (get_value(expr->left, &left))
712 left_known = 1;
713 if (get_value(expr->right, &right))
714 right_known = 1;
715 } else {
716 if (get_implied_value_internal(expr->left, &left, recurse_cnt))
717 left_known = 1;
718 if (get_implied_value_internal(expr->right, &right, recurse_cnt))
719 right_known = 1;
720 }
721
722 switch (expr->op) {
723 case SPECIAL_LOGICAL_OR:
724 if (left_known && left.value)
725 return rl_one();
726 if (right_known && right.value)
727 return rl_one();
728 if (left_known && right_known)
729 return rl_zero();
730 break;
731 case SPECIAL_LOGICAL_AND:
732 if (left_known && right_known) {
733 if (left.value && right.value)
734 return rl_one();
735 return rl_zero();
736 }
737 break;
738 default:
739 return NULL;
740 }
741
742 if (implied == RL_EXACT)
743 return NULL;
744
745 return alloc_rl(zero, one);
746 }
747
748 static struct range_list *handle_conditional_rl(struct expression *expr, int implied, int *recurse_cnt)
749 {
750 struct expression *cond_true;
751 struct range_list *true_rl, *false_rl;
752 struct symbol *type;
753 int final_pass_orig = final_pass;
754
755 cond_true = expr->cond_true;
756 if (!cond_true)
757 cond_true = expr->conditional;
758
759 if (known_condition_true(expr->conditional))
760 return _get_rl(cond_true, implied, recurse_cnt);
761 if (known_condition_false(expr->conditional))
762 return _get_rl(expr->cond_false, implied, recurse_cnt);
763
764 if (implied == RL_EXACT)
765 return NULL;
766
767 if (implied_condition_true(expr->conditional))
768 return _get_rl(cond_true, implied, recurse_cnt);
769 if (implied_condition_false(expr->conditional))
770 return _get_rl(expr->cond_false, implied, recurse_cnt);
771
772
773 /* this becomes a problem with deeply nested conditional statements */
774 if (low_on_memory())
775 return NULL;
776
777 type = get_type(expr);
778
779 __push_fake_cur_stree();
780 final_pass = 0;
781 __split_whole_condition(expr->conditional);
782 true_rl = _get_rl(cond_true, implied, recurse_cnt);
783 __push_true_states();
784 __use_false_states();
785 false_rl = _get_rl(expr->cond_false, implied, recurse_cnt);
786 __merge_true_states();
787 __free_fake_cur_stree();
788 final_pass = final_pass_orig;
789
790 if (!true_rl || !false_rl)
791 return NULL;
792 true_rl = cast_rl(type, true_rl);
793 false_rl = cast_rl(type, false_rl);
794
795 return rl_union(true_rl, false_rl);
796 }
797
798 static int get_fuzzy_max_helper(struct expression *expr, sval_t *max)
799 {
800 struct smatch_state *state;
801 sval_t sval;
802
803 if (get_hard_max(expr, &sval)) {
804 *max = sval;
805 return 1;
806 }
807
808 state = get_extra_state(expr);
809 if (!state || !estate_has_fuzzy_max(state))
810 return 0;
811 *max = sval_cast(get_type(expr), estate_get_fuzzy_max(state));
812 return 1;
813 }
814
815 static int get_fuzzy_min_helper(struct expression *expr, sval_t *min)
816 {
817 struct smatch_state *state;
818 sval_t sval;
819
820 state = get_extra_state(expr);
821 if (!state || !estate_rl(state))
822 return 0;
823
824 sval = estate_min(state);
825 if (sval_is_negative(sval) && sval_is_min(sval))
826 return 0;
827
828 if (sval_is_max(sval))
829 return 0;
830
831 *min = sval_cast(get_type(expr), sval);
832 return 1;
833 }
834
835 int get_const_value(struct expression *expr, sval_t *sval)
836 {
837 struct symbol *sym;
838 sval_t right;
839
840 if (expr->type != EXPR_SYMBOL || !expr->symbol)
841 return 0;
842 sym = expr->symbol;
843 if (!(sym->ctype.modifiers & MOD_CONST))
844 return 0;
845 if (get_value(sym->initializer, &right)) {
846 *sval = sval_cast(get_type(expr), right);
847 return 1;
848 }
849 return 0;
850 }
851
852 struct range_list *var_to_absolute_rl(struct expression *expr)
853 {
854 struct smatch_state *state;
855 struct range_list *rl;
856
857 state = get_extra_state(expr);
858 if (!state || is_whole_rl(estate_rl(state))) {
859 state = get_real_absolute_state(expr);
860 if (state && state->data && !estate_is_whole(state))
861 return clone_rl(estate_rl(state));
862 if (get_local_rl(expr, &rl) && !is_whole_rl(rl))
863 return rl;
864 if (get_mtag_rl(expr, &rl))
865 return rl;
866 if (get_db_type_rl(expr, &rl) && !is_whole_rl(rl))
867 return rl;
868 return alloc_whole_rl(get_type(expr));
869 }
870 /* err on the side of saying things are possible */
871 if (!estate_rl(state))
872 return alloc_whole_rl(get_type(expr));
873 return clone_rl(estate_rl(state));
874 }
875
876 static struct range_list *handle_variable(struct expression *expr, int implied, int *recurse_cnt)
877 {
878 struct smatch_state *state;
879 struct range_list *rl;
880 sval_t sval, min, max;
881 struct symbol *type;
882
883 if (get_const_value(expr, &sval))
884 return alloc_rl(sval, sval);
885
886 if (custom_handle_variable) {
887 rl = custom_handle_variable(expr);
888 if (!rl)
889 return var_to_absolute_rl(expr);
890 return rl;
891 }
892
893 if (implied == RL_EXACT)
894 return NULL;
895
896 if (get_mtag_sval(expr, &sval))
897 return alloc_rl(sval, sval);
898
899 type = get_type(expr);
900 if (type && type->type == SYM_FN)
901 return alloc_rl(fn_ptr_min, fn_ptr_max);
902
903 switch (implied) {
904 case RL_HARD:
905 case RL_IMPLIED:
906 case RL_ABSOLUTE:
907 state = get_extra_state(expr);
908 if (!state || !state->data) {
909 if (implied == RL_HARD)
910 return NULL;
911 if (get_local_rl(expr, &rl))
912 return rl;
913 if (get_mtag_rl(expr, &rl))
914 return rl;
915 if (get_db_type_rl(expr, &rl))
916 return rl;
917 if (is_array(expr) && get_array_rl(expr, &rl))
918 return rl;
919 return NULL;
920 }
921 if (implied == RL_HARD && !estate_has_hard_max(state))
922 return NULL;
923 return clone_rl(estate_rl(state));
924 case RL_REAL_ABSOLUTE: {
925 struct smatch_state *abs_state;
926
927 state = get_extra_state(expr);
928 abs_state = get_real_absolute_state(expr);
929
930 if (estate_rl(state) && estate_rl(abs_state)) {
931 return clone_rl(rl_intersection(estate_rl(state),
932 estate_rl(abs_state)));
933 } else if (estate_rl(state)) {
934 return clone_rl(estate_rl(state));
935 } else if (estate_is_empty(state)) {
936 /*
937 * FIXME: we don't handle empty extra states correctly.
938 *
939 * The real abs rl is supposed to be filtered by the
940 * extra state if there is one. We don't bother keeping
941 * the abs state in sync all the time because we know it
942 * will be filtered later.
943 *
944 * It's not totally obvious to me how they should be
945 * handled. Perhaps we should take the whole rl and
946 * filter by the imaginary states. Perhaps we should
947 * just go with the empty state.
948 *
949 * Anyway what we currently do is return NULL here and
950 * that gets translated into the whole range in
951 * get_real_absolute_rl().
952 *
953 */
954 return NULL;
955 } else if (estate_rl(abs_state)) {
956 return clone_rl(estate_rl(abs_state));
957 }
958
959 if (get_local_rl(expr, &rl))
960 return rl;
961 if (get_mtag_rl(expr, &rl))
962 return rl;
963 if (get_db_type_rl(expr, &rl))
964 return rl;
965 if (is_array(expr) && get_array_rl(expr, &rl))
966 return rl;
967 return NULL;
968 }
969 case RL_FUZZY:
970 if (!get_fuzzy_min_helper(expr, &min))
971 min = sval_type_min(get_type(expr));
972 if (!get_fuzzy_max_helper(expr, &max))
973 return NULL;
974 /* fuzzy ranges are often inverted */
975 if (sval_cmp(min, max) > 0) {
976 sval = min;
977 min = max;
978 max = sval;
979 }
980 return alloc_rl(min, max);
981 }
982 return NULL;
983 }
984
985 static sval_t handle_sizeof(struct expression *expr)
986 {
987 struct symbol *sym;
988 sval_t ret;
989
990 ret = sval_blank(expr);
991 sym = expr->cast_type;
992 if (!sym) {
993 sym = evaluate_expression(expr->cast_expression);
994 if (!sym) {
995 __silence_warnings_for_stmt = true;
996 sym = &int_ctype;
997 }
998 #if 0
999 /*
1000 * Expressions of restricted types will possibly get
1001 * promoted - check that here. I'm not sure how this works,
1002 * the problem is that sizeof(le16) shouldn't be promoted and
1003 * the original code did that... Let's if zero this out and
1004 * see what breaks.
1005 */
1006
1007 if (is_restricted_type(sym)) {
1008 if (type_bits(sym) < bits_in_int)
1009 sym = &int_ctype;
1010 }
1011 #endif
1012 if (is_fouled_type(sym))
1013 sym = &int_ctype;
1014 }
1015 examine_symbol_type(sym);
1016
1017 ret.type = size_t_ctype;
1018 if (type_bits(sym) <= 0) /* sizeof(void) */ {
1019 if (get_real_base_type(sym) == &void_ctype)
1020 ret.value = 1;
1021 else
1022 ret.value = 0;
1023 } else
1024 ret.value = type_bytes(sym);
1025
1026 return ret;
1027 }
1028
1029 static struct range_list *handle_strlen(struct expression *expr, int implied, int *recurse_cnt)
1030 {
1031 struct range_list *rl;
1032 struct expression *arg, *tmp;
1033 sval_t tag;
1034 sval_t ret = { .type = &ulong_ctype };
1035
1036 if (implied == RL_EXACT)
1037 return NULL;
1038
1039 arg = get_argument_from_call_expr(expr->args, 0);
1040 if (!arg)
1041 return NULL;
1042 if (arg->type == EXPR_STRING) {
1043 ret.value = arg->string->length - 1;
1044 return alloc_rl(ret, ret);
1045 }
1046 if (get_implied_value(arg, &tag) &&
1047 (tmp = fake_string_from_mtag(tag.uvalue))) {
1048 ret.value = tmp->string->length - 1;
1049 return alloc_rl(ret, ret);
1050 }
1051
1052 if (implied == RL_HARD || implied == RL_FUZZY)
1053 return NULL;
1054
1055 if (get_implied_return(expr, &rl))
1056 return rl;
1057
1058 return NULL;
1059 }
1060
1061 static struct range_list *handle_builtin_constant_p(struct expression *expr, int implied, int *recurse_cnt)
1062 {
1063 struct expression *arg;
1064 struct range_list *rl;
1065 sval_t sval;
1066
1067 arg = get_argument_from_call_expr(expr->args, 0);
1068 rl = _get_rl(arg, RL_EXACT, recurse_cnt);
1069 if (rl_to_sval(rl, &sval))
1070 return rl_one();
1071 return rl_zero();
1072 }
1073
1074 static struct range_list *handle__builtin_choose_expr(struct expression *expr, int implied, int *recurse_cnt)
1075 {
1076 struct expression *const_expr, *expr1, *expr2;
1077 sval_t sval;
1078
1079 const_expr = get_argument_from_call_expr(expr->args, 0);
1080 expr1 = get_argument_from_call_expr(expr->args, 1);
1081 expr2 = get_argument_from_call_expr(expr->args, 2);
1082
1083 if (!get_value(const_expr, &sval) || !expr1 || !expr2)
1084 return NULL;
1085 if (sval.value)
1086 return _get_rl(expr1, implied, recurse_cnt);
1087 return _get_rl(expr2, implied, recurse_cnt);
1088 }
1089
1090 static struct range_list *handle_call_rl(struct expression *expr, int implied, int *recurse_cnt)
1091 {
1092 struct range_list *rl;
1093
1094 if (sym_name_is("__builtin_constant_p", expr->fn))
1095 return handle_builtin_constant_p(expr, implied, recurse_cnt);
1096
1097 if (sym_name_is("__builtin_choose_expr", expr->fn))
1098 return handle__builtin_choose_expr(expr, implied, recurse_cnt);
1099
1100 if (sym_name_is("__builtin_expect", expr->fn) ||
1101 sym_name_is("__builtin_bswap16", expr->fn) ||
1102 sym_name_is("__builtin_bswap32", expr->fn) ||
1103 sym_name_is("__builtin_bswap64", expr->fn)) {
1104 struct expression *arg;
1105
1106 arg = get_argument_from_call_expr(expr->args, 0);
1107 return _get_rl(arg, implied, recurse_cnt);
1108 }
1109
1110 if (sym_name_is("strlen", expr->fn))
1111 return handle_strlen(expr, implied, recurse_cnt);
1112
1113 if (implied == RL_EXACT || implied == RL_HARD || implied == RL_FUZZY)
1114 return NULL;
1115
1116 if (custom_handle_variable) {
1117 rl = custom_handle_variable(expr);
1118 if (rl)
1119 return rl;
1120 }
1121
1122 if (get_implied_return(expr, &rl))
1123 return rl;
1124 return db_return_vals(expr);
1125 }
1126
1127 static struct range_list *handle_cast(struct expression *expr, int implied, int *recurse_cnt)
1128 {
1129 struct range_list *rl;
1130 struct symbol *type;
1131
1132 type = get_type(expr);
1133 rl = _get_rl(expr->cast_expression, implied, recurse_cnt);
1134 if (rl)
1135 return cast_rl(type, rl);
1136 if (implied == RL_ABSOLUTE || implied == RL_REAL_ABSOLUTE)
1137 return alloc_whole_rl(type);
1138 if (implied == RL_IMPLIED && type &&
1139 type_bits(type) > 0 && type_bits(type) < 32)
1140 return alloc_whole_rl(type);
1141 return NULL;
1142 }
1143
1144 static struct range_list *_get_rl(struct expression *expr, int implied, int *recurse_cnt)
1145 {
1146 struct range_list *rl;
1147 struct symbol *type;
1148 sval_t sval;
1149
1150 type = get_type(expr);
1151 expr = strip_parens(expr);
1152 if (!expr)
1153 return NULL;
1154
1155 if (++(*recurse_cnt) >= 200)
1156 return NULL;
1157
1158 switch(expr->type) {
1159 case EXPR_CAST:
1160 case EXPR_FORCE_CAST:
1161 case EXPR_IMPLIED_CAST:
1162 rl = handle_cast(expr, implied, recurse_cnt);
1163 goto out_cast;
1164 }
1165
1166 expr = strip_expr(expr);
1167 if (!expr)
1168 return NULL;
1169
1170 switch (expr->type) {
1171 case EXPR_VALUE:
1172 sval = sval_from_val(expr, expr->value);
1173 rl = alloc_rl(sval, sval);
1174 break;
1175 case EXPR_PREOP:
1176 rl = handle_preop_rl(expr, implied, recurse_cnt);
1177 break;
1178 case EXPR_POSTOP:
1179 rl = _get_rl(expr->unop, implied, recurse_cnt);
1180 break;
1181 case EXPR_BINOP:
1182 rl = handle_binop_rl(expr, implied, recurse_cnt);
1183 break;
1184 case EXPR_COMPARE:
1185 rl = handle_comparison_rl(expr, implied, recurse_cnt);
1186 break;
1187 case EXPR_LOGICAL:
1188 rl = handle_logical_rl(expr, implied, recurse_cnt);
1189 break;
1190 case EXPR_PTRSIZEOF:
1191 case EXPR_SIZEOF:
1192 sval = handle_sizeof(expr);
1193 rl = alloc_rl(sval, sval);
1194 break;
1195 case EXPR_SELECT:
1196 case EXPR_CONDITIONAL:
1197 rl = handle_conditional_rl(expr, implied, recurse_cnt);
1198 break;
1199 case EXPR_CALL:
1200 rl = handle_call_rl(expr, implied, recurse_cnt);
1201 break;
1202 case EXPR_STRING:
1203 rl = NULL;
1204 if (get_mtag_sval(expr, &sval))
1205 rl = alloc_rl(sval, sval);
1206 break;
1207 default:
1208 rl = handle_variable(expr, implied, recurse_cnt);
1209 }
1210
1211 out_cast:
1212 if (rl)
1213 return rl;
1214 if (type && (implied == RL_ABSOLUTE || implied == RL_REAL_ABSOLUTE))
1215 return alloc_whole_rl(type);
1216 return NULL;
1217 }
1218
1219 struct {
1220 struct expression *expr;
1221 struct range_list *rl;
1222 } cached_results[24];
1223 static int cache_idx;
1224
1225 void clear_math_cache(void)
1226 {
1227 memset(cached_results, 0, sizeof(cached_results));
1228 }
1229
1230 /* returns 1 if it can get a value literal or else returns 0 */
1231 int get_value(struct expression *expr, sval_t *sval)
1232 {
1233 struct range_list *(*orig_custom_fn)(struct expression *expr);
1234 struct range_list *rl;
1235 int recurse_cnt = 0;
1236 sval_t tmp;
1237 int i;
1238
1239 /*
1240 * This only handles RL_EXACT because other expr statements can be
1241 * different at different points. Like the list iterator, for example.
1242 */
1243 for (i = 0; i < ARRAY_SIZE(cached_results); i++) {
1244 if (expr == cached_results[i].expr)
1245 return rl_to_sval(cached_results[i].rl, sval);
1246 }
1247
1248 orig_custom_fn = custom_handle_variable;
1249 custom_handle_variable = NULL;
1250 rl = _get_rl(expr, RL_EXACT, &recurse_cnt);
1251 if (!rl_to_sval(rl, &tmp))
1252 rl = NULL;
1253 custom_handle_variable = orig_custom_fn;
1254
1255 cached_results[cache_idx].expr = expr;
1256 cached_results[cache_idx].rl = rl;
1257 cache_idx = (cache_idx + 1) % ARRAY_SIZE(cached_results);
1258
1259 if (!rl)
1260 return 0;
1261
1262 *sval = tmp;
1263 return 1;
1264 }
1265
1266 static int get_implied_value_internal(struct expression *expr, sval_t *sval, int *recurse_cnt)
1267 {
1268 struct range_list *rl;
1269
1270 rl = _get_rl(expr, RL_IMPLIED, recurse_cnt);
1271 if (!rl_to_sval(rl, sval))
1272 return 0;
1273 return 1;
1274 }
1275
1276 int get_implied_value(struct expression *expr, sval_t *sval)
1277 {
1278 struct range_list *rl;
1279 int recurse_cnt = 0;
1280
1281 rl = _get_rl(expr, RL_IMPLIED, &recurse_cnt);
1282 if (!rl_to_sval(rl, sval))
1283 return 0;
1284 return 1;
1285 }
1286
1287 int get_implied_min(struct expression *expr, sval_t *sval)
1288 {
1289 struct range_list *rl;
1290 int recurse_cnt = 0;
1291
1292 rl = _get_rl(expr, RL_IMPLIED, &recurse_cnt);
1293 if (!rl)
1294 return 0;
1295 *sval = rl_min(rl);
1296 return 1;
1297 }
1298
1299 int get_implied_max(struct expression *expr, sval_t *sval)
1300 {
1301 struct range_list *rl;
1302 int recurse_cnt = 0;
1303
1304 rl = _get_rl(expr, RL_IMPLIED, &recurse_cnt);
1305 if (!rl)
1306 return 0;
1307 *sval = rl_max(rl);
1308 return 1;
1309 }
1310
1311 int get_implied_rl(struct expression *expr, struct range_list **rl)
1312 {
1313 int recurse_cnt = 0;
1314
1315 *rl = _get_rl(expr, RL_IMPLIED, &recurse_cnt);
1316 if (*rl)
1317 return 1;
1318 return 0;
1319 }
1320
1321 static int get_absolute_rl_internal(struct expression *expr, struct range_list **rl, int *recurse_cnt)
1322 {
1323 *rl = _get_rl(expr, RL_ABSOLUTE, recurse_cnt);
1324 if (!*rl)
1325 *rl = alloc_whole_rl(get_type(expr));
1326 return 1;
1327 }
1328
1329 int get_absolute_rl(struct expression *expr, struct range_list **rl)
1330 {
1331 int recurse_cnt = 0;
1332
1333 *rl = _get_rl(expr, RL_ABSOLUTE, &recurse_cnt);
1334 if (!*rl)
1335 *rl = alloc_whole_rl(get_type(expr));
1336 return 1;
1337 }
1338
1339 int get_real_absolute_rl(struct expression *expr, struct range_list **rl)
1340 {
1341 int recurse_cnt = 0;
1342
1343 *rl = _get_rl(expr, RL_REAL_ABSOLUTE, &recurse_cnt);
1344 if (!*rl)
1345 *rl = alloc_whole_rl(get_type(expr));
1346 return 1;
1347 }
1348
1349 int custom_get_absolute_rl(struct expression *expr,
1350 struct range_list *(*fn)(struct expression *expr),
1351 struct range_list **rl)
1352 {
1353 int recurse_cnt = 0;
1354
1355 *rl = NULL;
1356 custom_handle_variable = fn;
1357 *rl = _get_rl(expr, RL_REAL_ABSOLUTE, &recurse_cnt);
1358 custom_handle_variable = NULL;
1359 return 1;
1360 }
1361
1362 int get_implied_rl_var_sym(const char *var, struct symbol *sym, struct range_list **rl)
1363 {
1364 struct smatch_state *state;
1365
1366 state = get_state(SMATCH_EXTRA, var, sym);
1367 *rl = estate_rl(state);
1368 if (*rl)
1369 return 1;
1370 return 0;
1371 }
1372
1373 int get_hard_max(struct expression *expr, sval_t *sval)
1374 {
1375 struct range_list *rl;
1376 int recurse_cnt = 0;
1377
1378 rl = _get_rl(expr, RL_HARD, &recurse_cnt);
1379 if (!rl)
1380 return 0;
1381 *sval = rl_max(rl);
1382 return 1;
1383 }
1384
1385 int get_fuzzy_min(struct expression *expr, sval_t *sval)
1386 {
1387 struct range_list *rl;
1388 sval_t tmp;
1389 int recurse_cnt = 0;
1390
1391 rl = _get_rl(expr, RL_FUZZY, &recurse_cnt);
1392 if (!rl)
1393 return 0;
1394 tmp = rl_min(rl);
1395 if (sval_is_negative(tmp) && sval_is_min(tmp))
1396 return 0;
1397 *sval = tmp;
1398 return 1;
1399 }
1400
1401 int get_fuzzy_max(struct expression *expr, sval_t *sval)
1402 {
1403 struct range_list *rl;
1404 sval_t max;
1405 int recurse_cnt = 0;
1406
1407 rl = _get_rl(expr, RL_FUZZY, &recurse_cnt);
1408 if (!rl)
1409 return 0;
1410 max = rl_max(rl);
1411 if (max.uvalue > INT_MAX - 10000)
1412 return 0;
1413 *sval = max;
1414 return 1;
1415 }
1416
1417 int get_absolute_min(struct expression *expr, sval_t *sval)
1418 {
1419 struct range_list *rl;
1420 struct symbol *type;
1421 int recurse_cnt = 0;
1422
1423 type = get_type(expr);
1424 if (!type)
1425 type = &llong_ctype; // FIXME: this is wrong but places assume get type can't fail.
1426 rl = _get_rl(expr, RL_REAL_ABSOLUTE, &recurse_cnt);
1427 if (rl)
1428 *sval = rl_min(rl);
1429 else
1430 *sval = sval_type_min(type);
1431
1432 if (sval_cmp(*sval, sval_type_min(type)) < 0)
1433 *sval = sval_type_min(type);
1434 return 1;
1435 }
1436
1437 int get_absolute_max(struct expression *expr, sval_t *sval)
1438 {
1439 struct range_list *rl;
1440 struct symbol *type;
1441 int recurse_cnt = 0;
1442
1443 type = get_type(expr);
1444 if (!type)
1445 type = &llong_ctype;
1446 rl = _get_rl(expr, RL_REAL_ABSOLUTE, &recurse_cnt);
1447 if (rl)
1448 *sval = rl_max(rl);
1449 else
1450 *sval = sval_type_max(type);
1451
1452 if (sval_cmp(sval_type_max(type), *sval) < 0)
1453 *sval = sval_type_max(type);
1454 return 1;
1455 }
1456
1457 int known_condition_true(struct expression *expr)
1458 {
1459 sval_t tmp;
1460
1461 if (!expr)
1462 return 0;
1463
1464 if (get_value(expr, &tmp) && tmp.value)
1465 return 1;
1466
1467 return 0;
1468 }
1469
1470 int known_condition_false(struct expression *expr)
1471 {
1472 if (!expr)
1473 return 0;
1474
1475 if (is_zero(expr))
1476 return 1;
1477
1478 return 0;
1479 }
1480
1481 int implied_condition_true(struct expression *expr)
1482 {
1483 sval_t tmp;
1484
1485 if (!expr)
1486 return 0;
1487
1488 if (known_condition_true(expr))
1489 return 1;
1490 if (get_implied_value(expr, &tmp) && tmp.value)
1491 return 1;
1492
1493 if (expr->type == EXPR_POSTOP)
1494 return implied_condition_true(expr->unop);
1495
1496 if (expr->type == EXPR_PREOP && expr->op == SPECIAL_DECREMENT)
1497 return implied_not_equal(expr->unop, 1);
1498 if (expr->type == EXPR_PREOP && expr->op == SPECIAL_INCREMENT)
1499 return implied_not_equal(expr->unop, -1);
1500
1501 expr = strip_expr(expr);
1502 switch (expr->type) {
1503 case EXPR_COMPARE:
1504 if (do_comparison(expr) == 1)
1505 return 1;
1506 break;
1507 case EXPR_PREOP:
1508 if (expr->op == '!') {
1509 if (implied_condition_false(expr->unop))
1510 return 1;
1511 break;
1512 }
1513 break;
1514 default:
1515 if (implied_not_equal(expr, 0) == 1)
1516 return 1;
1517 break;
1518 }
1519 return 0;
1520 }
1521
1522 int implied_condition_false(struct expression *expr)
1523 {
1524 struct expression *tmp;
1525 sval_t sval;
1526
1527 if (!expr)
1528 return 0;
1529
1530 if (known_condition_false(expr))
1531 return 1;
1532
1533 switch (expr->type) {
1534 case EXPR_COMPARE:
1535 if (do_comparison(expr) == 2)
1536 return 1;
1537 case EXPR_PREOP:
1538 if (expr->op == '!') {
1539 if (implied_condition_true(expr->unop))
1540 return 1;
1541 break;
1542 }
1543 tmp = strip_expr(expr);
1544 if (tmp != expr)
1545 return implied_condition_false(tmp);
1546 break;
1547 default:
1548 if (get_implied_value(expr, &sval) && sval.value == 0)
1549 return 1;
1550 break;
1551 }
1552 return 0;
1553 }
1554
1555 int can_integer_overflow(struct symbol *type, struct expression *expr)
1556 {
1557 int op;
1558 sval_t lmax, rmax, res;
1559
1560 if (!type)
1561 type = &int_ctype;
1562
1563 expr = strip_expr(expr);
1564
1565 if (expr->type == EXPR_ASSIGNMENT) {
1566 switch(expr->op) {
1567 case SPECIAL_MUL_ASSIGN:
1568 op = '*';
1569 break;
1570 case SPECIAL_ADD_ASSIGN:
1571 op = '+';
1572 break;
1573 case SPECIAL_SHL_ASSIGN:
1574 op = SPECIAL_LEFTSHIFT;
1575 break;
1576 default:
1577 return 0;
1578 }
1579 } else if (expr->type == EXPR_BINOP) {
1580 if (expr->op != '*' && expr->op != '+' && expr->op != SPECIAL_LEFTSHIFT)
1581 return 0;
1582 op = expr->op;
1583 } else {
1584 return 0;
1585 }
1586
1587 get_absolute_max(expr->left, &lmax);
1588 get_absolute_max(expr->right, &rmax);
1589
1590 if (sval_binop_overflows(lmax, op, rmax))
1591 return 1;
1592
1593 res = sval_binop(lmax, op, rmax);
1594 if (sval_cmp(res, sval_type_max(type)) > 0)
1595 return 1;
1596 return 0;
1597 }