xref: /illumos-gate/usr/src/tools/smatch/src/smatch_math.c (revision 1f5207b7604fb44407eb4342aff613f7c4508508)
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 }
1598