xref: /illumos-gate/usr/src/tools/smatch/src/smatch_math.c (revision 31ad075e90bf5afda8ab4b8cc4d3ca3e89946115)
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 bool get_rl_sval(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *sval_res);
24 static bool get_rl_internal(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res);
25 static bool handle_variable(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval);
26 static struct range_list *(*custom_handle_variable)(struct expression *expr);
27 
28 static bool get_implied_value_internal(struct expression *expr, int *recurse_cnt, sval_t *res_sval);
29 static int get_absolute_rl_internal(struct expression *expr, struct range_list **rl, int *recurse_cnt);
30 
31 static sval_t zero  = {.type = &int_ctype, {.value = 0} };
32 static sval_t one   = {.type = &int_ctype, {.value = 1} };
33 
34 static int fast_math_only;
35 
36 struct range_list *rl_zero(void)
37 {
38 	static struct range_list *zero_perm;
39 
40 	if (!zero_perm)
41 		zero_perm = clone_rl_permanent(alloc_rl(zero, zero));
42 	return zero_perm;
43 }
44 
45 struct range_list *rl_one(void)
46 {
47 	static struct range_list *one_perm;
48 
49 	if (!one_perm)
50 		one_perm = clone_rl_permanent(alloc_rl(one, one));
51 
52 	return one_perm;
53 }
54 
55 enum {
56 	RL_EXACT,
57 	RL_HARD,
58 	RL_FUZZY,
59 	RL_IMPLIED,
60 	RL_ABSOLUTE,
61 	RL_REAL_ABSOLUTE,
62 };
63 
64 static bool last_stmt_rl(struct statement *stmt, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
65 {
66 	struct expression *expr;
67 
68 	if (!stmt)
69 		return false;
70 
71 	stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
72 	if (stmt->type == STMT_LABEL) {
73 		if (stmt->label_statement &&
74 		    stmt->label_statement->type == STMT_EXPRESSION)
75 			expr = stmt->label_statement->expression;
76 		else
77 			return false;
78 	} else if (stmt->type == STMT_EXPRESSION) {
79 		expr = stmt->expression;
80 	} else {
81 		return false;
82 	}
83 	return get_rl_sval(expr, implied, recurse_cnt, res, res_sval);
84 }
85 
86 static bool handle_expression_statement_rl(struct expression *expr, int implied,
87 		int *recurse_cnt, struct range_list **res, sval_t *res_sval)
88 {
89 	return last_stmt_rl(get_expression_statement(expr), implied, recurse_cnt, res, res_sval);
90 }
91 
92 static bool handle_address(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
93 {
94 	struct range_list *rl;
95 	static int recursed;
96 	sval_t sval;
97 
98 	if (recursed > 10)
99 		return false;
100 	if (implied == RL_EXACT)
101 		return false;
102 
103 	if (custom_handle_variable) {
104 		rl = custom_handle_variable(expr);
105 		if (rl) {
106 			*res = rl;
107 			return true;
108 		}
109 	}
110 
111 	recursed++;
112 	if (get_mtag_sval(expr, &sval)) {
113 		recursed--;
114 		*res_sval = sval;
115 		return true;
116 	}
117 
118 	if (get_address_rl(expr, res)) {
119 		recursed--;
120 		return true;
121 	}
122 	recursed--;
123 	return 0;
124 }
125 
126 static bool handle_ampersand_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
127 {
128 	return handle_address(expr, implied, recurse_cnt, res, res_sval);
129 }
130 
131 static bool handle_negate_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
132 {
133 	if (known_condition_true(expr->unop)) {
134 		*res_sval = zero;
135 		return true;
136 	}
137 	if (known_condition_false(expr->unop)) {
138 		*res_sval = one;
139 		return true;
140 	}
141 
142 	if (implied == RL_EXACT)
143 		return false;
144 
145 	if (implied_condition_true(expr->unop)) {
146 		*res_sval = zero;
147 		return true;
148 	}
149 	if (implied_condition_false(expr->unop)) {
150 		*res_sval = one;
151 		return true;
152 	}
153 
154 	*res = alloc_rl(zero, one);
155 	return true;
156 }
157 
158 static bool handle_bitwise_negate(struct expression *expr, int implied, int *recurse_cnt, sval_t *res_sval)
159 {
160 	struct range_list *rl;
161 	sval_t sval = {};
162 
163 	if (!get_rl_sval(expr->unop, implied, recurse_cnt, &rl, &sval))
164 		return false;
165 	if (!sval.type && !rl_to_sval(rl, &sval))
166 		return false;
167 	sval = sval_preop(sval, '~');
168 	sval_cast(get_type(expr->unop), sval);
169 	*res_sval = sval;
170 	return true;
171 }
172 
173 static bool untrusted_type_min(struct expression *expr)
174 {
175 	struct range_list *rl;
176 
177 	rl = var_user_rl(expr);
178 	return rl && sval_is_min(rl_min(rl));
179 }
180 
181 static bool handle_minus_preop(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
182 {
183 	struct range_list *rl;
184 	struct range_list *ret = NULL;
185 	struct symbol *type;
186 	sval_t neg_one = { 0 };
187 	sval_t zero = { 0 };
188 	sval_t sval = {};
189 
190 	neg_one.value = -1;
191 	zero.value = 0;
192 
193 	if (!get_rl_sval(expr->unop, implied, recurse_cnt, &rl, &sval))
194 		return false;
195 	if (sval.type) {
196 		*res_sval = sval_preop(sval, '-');
197 		return true;
198 	}
199 	/*
200 	 * One complication is that -INT_MIN is still INT_MIN because of integer
201 	 * overflows...  But how many times do we set a time out to INT_MIN?
202 	 * So normally when we call abs() then it does return a positive value.
203 	 *
204 	 */
205 	type = rl_type(rl);
206 	neg_one.type = zero.type = type;
207 
208 	if (sval_is_negative(rl_min(rl))) {
209 		struct range_list *neg;
210 		struct data_range *drange;
211 		sval_t new_min, new_max;
212 
213 		neg = alloc_rl(sval_type_min(type), neg_one);
214 		neg = rl_intersection(rl, neg);
215 
216 		if (sval_is_min(rl_min(neg)) && !sval_is_min(rl_max(neg)))
217 			neg = remove_range(neg, sval_type_min(type), sval_type_min(type));
218 
219 		FOR_EACH_PTR(neg, drange) {
220 			new_min = drange->max;
221 			new_min.value = -new_min.value;
222 			new_max = drange->min;
223 			new_max.value = -new_max.value;
224 			add_range(&ret, new_min, new_max);
225 		} END_FOR_EACH_PTR(drange);
226 
227 		if (untrusted_type_min(expr))
228 			add_range(&ret, sval_type_min(type), sval_type_min(type));
229 	}
230 
231 	if (!sval_is_negative(rl_max(rl))) {
232 		struct range_list *pos;
233 		struct data_range *drange;
234 		sval_t new_min, new_max;
235 
236 		pos = alloc_rl(zero, sval_type_max(type));
237 		pos = rl_intersection(rl, pos);
238 
239 		FOR_EACH_PTR(pos, drange) {
240 			new_min = drange->max;
241 			new_min.value = -new_min.value;
242 			new_max = drange->min;
243 			new_max.value = -new_max.value;
244 			add_range(&ret, new_min, new_max);
245 		} END_FOR_EACH_PTR(drange);
246 	}
247 
248 	*res = ret;
249 	return true;
250 }
251 
252 static bool handle_preop_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
253 {
254 	switch (expr->op) {
255 	case '&':
256 		return handle_ampersand_rl(expr, implied, recurse_cnt, res, res_sval);
257 	case '!':
258 		return handle_negate_rl(expr, implied, recurse_cnt, res, res_sval);
259 	case '~':
260 		return handle_bitwise_negate(expr, implied, recurse_cnt, res_sval);
261 	case '-':
262 		return handle_minus_preop(expr, implied, recurse_cnt, res, res_sval);
263 	case '*':
264 		return handle_variable(expr, implied, recurse_cnt, res, res_sval);
265 	case '(':
266 		return handle_expression_statement_rl(expr, implied, recurse_cnt, res, res_sval);
267 	default:
268 		return false;
269 	}
270 }
271 
272 static bool handle_divide_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res)
273 {
274 	struct range_list *left_rl = NULL;
275 	struct range_list *right_rl = NULL;
276 	struct symbol *type;
277 
278 	type = get_type(expr);
279 
280 	get_rl_internal(expr->left, implied, recurse_cnt, &left_rl);
281 	left_rl = cast_rl(type, left_rl);
282 	get_rl_internal(expr->right, implied, recurse_cnt, &right_rl);
283 	right_rl = cast_rl(type, right_rl);
284 
285 	if (!left_rl || !right_rl)
286 		return false;
287 
288 	if (implied != RL_REAL_ABSOLUTE) {
289 		if (is_whole_rl(left_rl) || is_whole_rl(right_rl))
290 			return false;
291 	}
292 
293 	*res = rl_binop(left_rl, '/', right_rl);
294 	return true;
295 }
296 
297 static int handle_offset_subtraction(struct expression *expr)
298 {
299 	struct expression *left, *right;
300 	struct symbol *left_sym, *right_sym;
301 	struct symbol *type;
302 	int left_offset, right_offset;
303 
304 	type = get_type(expr);
305 	if (!type || type->type != SYM_PTR)
306 		return -1;
307 	type = get_real_base_type(type);
308 	if (!type || (type_bits(type) != 8 && (type != &void_ctype)))
309 		return -1;
310 
311 	left = strip_expr(expr->left);
312 	right = strip_expr(expr->right);
313 
314 	if (left->type != EXPR_PREOP || left->op != '&')
315 		return -1;
316 	left = strip_expr(left->unop);
317 
318 	left_sym = expr_to_sym(left);
319 	right_sym = expr_to_sym(right);
320 	if (!left_sym || left_sym != right_sym)
321 		return -1;
322 
323 	left_offset = get_member_offset_from_deref(left);
324 	if (right->type == EXPR_SYMBOL)
325 		right_offset = 0;
326 	else {
327 		if (right->type != EXPR_PREOP || right->op != '&')
328 			return -1;
329 		right = strip_expr(right->unop);
330 		right_offset = get_member_offset_from_deref(right);
331 	}
332 	if (left_offset < 0 || right_offset < 0)
333 		return -1;
334 
335 	return left_offset - right_offset;
336 }
337 
338 static bool handle_subtract_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res)
339 {
340 	struct symbol *type;
341 	struct range_list *left_orig, *right_orig;
342 	struct range_list *left_rl, *right_rl;
343 	sval_t min, max, tmp;
344 	int comparison;
345 	int offset;
346 
347 	type = get_type(expr);
348 
349 	offset = handle_offset_subtraction(expr);
350 	if (offset >= 0) {
351 		tmp.type = type;
352 		tmp.value = offset;
353 
354 		*res = alloc_rl(tmp, tmp);
355 		return true;
356 	}
357 
358 	comparison = get_comparison(expr->left, expr->right);
359 
360 	left_orig = NULL;
361 	get_rl_internal(expr->left, implied, recurse_cnt, &left_orig);
362 	left_rl = cast_rl(type, left_orig);
363 	right_orig = NULL;
364 	get_rl_internal(expr->right, implied, recurse_cnt, &right_orig);
365 	right_rl = cast_rl(type, right_orig);
366 
367 	if ((!left_rl || !right_rl) &&
368 	    (implied == RL_EXACT || implied == RL_HARD || implied == RL_FUZZY))
369 		return false;
370 
371 	if (!left_rl)
372 		left_rl = alloc_whole_rl(type);
373 	if (!right_rl)
374 		right_rl = alloc_whole_rl(type);
375 
376 	/* negative values complicate everything fix this later */
377 	if (sval_is_negative(rl_min(right_rl)))
378 		return false;
379 	max = rl_max(left_rl);
380 	min = sval_type_min(type);
381 
382 	switch (comparison) {
383 	case '>':
384 	case SPECIAL_UNSIGNED_GT:
385 		min = sval_type_val(type, 1);
386 		max = rl_max(left_rl);
387 		break;
388 	case SPECIAL_GTE:
389 	case SPECIAL_UNSIGNED_GTE:
390 		min = sval_type_val(type, 0);
391 		max = rl_max(left_rl);
392 		break;
393 	case SPECIAL_EQUAL:
394 		min = sval_type_val(type, 0);
395 		max = sval_type_val(type, 0);
396 		break;
397 	case '<':
398 	case SPECIAL_UNSIGNED_LT:
399 		max = sval_type_val(type, -1);
400 		break;
401 	case SPECIAL_LTE:
402 	case SPECIAL_UNSIGNED_LTE:
403 		max = sval_type_val(type, 0);
404 		break;
405 	default:
406 		if (!left_orig || !right_orig)
407 			return false;
408 		*res = rl_binop(left_rl, '-', right_rl);
409 		return true;
410 	}
411 
412 	if (!sval_binop_overflows(rl_min(left_rl), '-', rl_max(right_rl))) {
413 		tmp = sval_binop(rl_min(left_rl), '-', rl_max(right_rl));
414 		if (sval_cmp(tmp, min) > 0)
415 			min = tmp;
416 	}
417 
418 	if (!sval_is_max(rl_max(left_rl))) {
419 		tmp = sval_binop(rl_max(left_rl), '-', rl_min(right_rl));
420 		if (sval_cmp(tmp, max) < 0)
421 			max = tmp;
422 	}
423 
424 	if (sval_is_min(min) && sval_is_max(max))
425 		return false;
426 
427 	*res = cast_rl(type, alloc_rl(min, max));
428 	return true;
429 }
430 
431 static bool handle_mod_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res)
432 {
433 	struct range_list *rl;
434 	sval_t left, right, sval;
435 
436 	if (implied == RL_EXACT) {
437 		if (!get_implied_value(expr->right, &right))
438 			return false;
439 		if (!get_implied_value(expr->left, &left))
440 			return false;
441 		sval = sval_binop(left, '%', right);
442 		*res = alloc_rl(sval, sval);
443 		return true;
444 	}
445 	/* if we can't figure out the right side it's probably hopeless */
446 	if (!get_implied_value_internal(expr->right, recurse_cnt, &right))
447 		return false;
448 
449 	right = sval_cast(get_type(expr), right);
450 	right.value--;
451 
452 	if (get_rl_internal(expr->left, implied, recurse_cnt, &rl) && rl &&
453 	    rl_max(rl).uvalue < right.uvalue)
454 		right.uvalue = rl_max(rl).uvalue;
455 
456 	*res = alloc_rl(sval_cast(right.type, zero), right);
457 	return true;
458 }
459 
460 static bool handle_bitwise_AND(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res)
461 {
462 	struct symbol *type;
463 	struct range_list *left_rl, *right_rl;
464 	int new_recurse;
465 
466 	if (implied != RL_IMPLIED && implied != RL_ABSOLUTE && implied != RL_REAL_ABSOLUTE)
467 		return false;
468 
469 	type = get_type(expr);
470 
471 	if (!get_rl_internal(expr->left, implied, recurse_cnt, &left_rl))
472 		left_rl = alloc_whole_rl(type);
473 	left_rl = cast_rl(type, left_rl);
474 
475 	new_recurse = *recurse_cnt;
476 	if (*recurse_cnt >= 200)
477 		new_recurse = 100;  /* Let's try super hard to get the mask */
478 	if (!get_rl_internal(expr->right, implied, &new_recurse, &right_rl))
479 		right_rl = alloc_whole_rl(type);
480 	right_rl = cast_rl(type, right_rl);
481 	*recurse_cnt = new_recurse;
482 
483 	*res = rl_binop(left_rl, '&', right_rl);
484 	return true;
485 }
486 
487 static bool use_rl_binop(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res)
488 {
489 	struct symbol *type;
490 	struct range_list *left_rl, *right_rl;
491 
492 	if (implied != RL_IMPLIED && implied != RL_ABSOLUTE && implied != RL_REAL_ABSOLUTE)
493 		return false;
494 
495 	type = get_type(expr);
496 
497 	get_absolute_rl_internal(expr->left, &left_rl, recurse_cnt);
498 	get_absolute_rl_internal(expr->right, &right_rl, recurse_cnt);
499 	left_rl = cast_rl(type, left_rl);
500 	right_rl = cast_rl(type, right_rl);
501 	if (!left_rl || !right_rl)
502 		return false;
503 
504 	*res = rl_binop(left_rl, expr->op, right_rl);
505 	return true;
506 }
507 
508 static bool handle_right_shift(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res)
509 {
510 	struct range_list *left_rl, *right_rl;
511 	sval_t min, max;
512 
513 	if (implied == RL_EXACT || implied == RL_HARD)
514 		return false;
515 
516 	if (get_rl_internal(expr->left, implied, recurse_cnt, &left_rl)) {
517 		max = rl_max(left_rl);
518 		min = rl_min(left_rl);
519 	} else {
520 		if (implied == RL_FUZZY)
521 			return false;
522 		max = sval_type_max(get_type(expr->left));
523 		min = sval_type_val(get_type(expr->left), 0);
524 	}
525 
526 	if (get_rl_internal(expr->right, implied, recurse_cnt, &right_rl) &&
527 	    !sval_is_negative(rl_min(right_rl))) {
528 		min = sval_binop(min, SPECIAL_RIGHTSHIFT, rl_max(right_rl));
529 		max = sval_binop(max, SPECIAL_RIGHTSHIFT, rl_min(right_rl));
530 	} else if (!sval_is_negative(min)) {
531 		min.value = 0;
532 		max = sval_type_max(max.type);
533 	} else {
534 		return false;
535 	}
536 
537 	*res = alloc_rl(min, max);
538 	return true;
539 }
540 
541 static bool handle_left_shift(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res)
542 {
543 	struct range_list *left_rl, *rl;
544 	sval_t right;
545 
546 	if (implied == RL_EXACT || implied == RL_HARD)
547 		return false;
548 	/* this is hopeless without the right side */
549 	if (!get_implied_value_internal(expr->right, recurse_cnt, &right))
550 		return false;
551 	if (!get_rl_internal(expr->left, implied, recurse_cnt, &left_rl)) {
552 		if (implied == RL_FUZZY)
553 			return false;
554 		left_rl = alloc_whole_rl(get_type(expr->left));
555 	}
556 
557 	rl = rl_binop(left_rl, SPECIAL_LEFTSHIFT, alloc_rl(right, right));
558 	if (!rl)
559 		return false;
560 	*res = rl;
561 	return true;
562 }
563 
564 static bool handle_known_binop(struct expression *expr, sval_t *res)
565 {
566 	sval_t left, right;
567 
568 	if (!get_value(expr->left, &left))
569 		return false;
570 	if (!get_value(expr->right, &right))
571 		return false;
572 	*res = sval_binop(left, expr->op, right);
573 	return true;
574 }
575 
576 static int has_actual_ranges(struct range_list *rl)
577 {
578 	struct data_range *tmp;
579 
580 	FOR_EACH_PTR(rl, tmp) {
581 		if (sval_cmp(tmp->min, tmp->max) != 0)
582 			return 1;
583 	} END_FOR_EACH_PTR(tmp);
584 	return 0;
585 }
586 
587 static struct range_list *handle_implied_binop(struct range_list *left_rl, int op, struct range_list *right_rl)
588 {
589 	struct range_list *res_rl;
590 	struct data_range *left_drange, *right_drange;
591 	sval_t res;
592 
593 	if (!left_rl || !right_rl)
594 		return NULL;
595 	if (has_actual_ranges(left_rl))
596 		return NULL;
597 	if (has_actual_ranges(right_rl))
598 		return NULL;
599 
600 	if (ptr_list_size((struct ptr_list *)left_rl) * ptr_list_size((struct ptr_list *)right_rl) > 20)
601 		return NULL;
602 
603 	res_rl = NULL;
604 
605 	FOR_EACH_PTR(left_rl, left_drange) {
606 		FOR_EACH_PTR(right_rl, right_drange) {
607 			if ((op == '%' || op == '/') &&
608 			    right_drange->min.value == 0)
609 				return NULL;
610 			res = sval_binop(left_drange->min, op, right_drange->min);
611 			add_range(&res_rl, res, res);
612 		} END_FOR_EACH_PTR(right_drange);
613 	} END_FOR_EACH_PTR(left_drange);
614 
615 	return res_rl;
616 }
617 
618 static bool handle_binop_rl_helper(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
619 {
620 	struct symbol *type;
621 	struct range_list *left_rl = NULL;
622 	struct range_list *right_rl = NULL;
623 	struct range_list *rl;
624 	sval_t min, max;
625 
626 	type = get_promoted_type(get_type(expr->left), get_type(expr->right));
627 	get_rl_internal(expr->left, implied, recurse_cnt, &left_rl);
628 	left_rl = cast_rl(type, left_rl);
629 	get_rl_internal(expr->right, implied, recurse_cnt, &right_rl);
630 	right_rl = cast_rl(type, right_rl);
631 	if (!left_rl && !right_rl)
632 		return false;
633 
634 	rl = handle_implied_binop(left_rl, expr->op, right_rl);
635 	if (rl) {
636 		*res = rl;
637 		return true;
638 	}
639 
640 	switch (expr->op) {
641 	case '%':
642 		return handle_mod_rl(expr, implied, recurse_cnt, res);
643 	case '&':
644 		return handle_bitwise_AND(expr, implied, recurse_cnt, res);
645 	case '|':
646 	case '^':
647 		return use_rl_binop(expr, implied, recurse_cnt, res);
648 	case SPECIAL_RIGHTSHIFT:
649 		return handle_right_shift(expr, implied, recurse_cnt, res);
650 	case SPECIAL_LEFTSHIFT:
651 		return handle_left_shift(expr, implied, recurse_cnt, res);
652 	case '-':
653 		return handle_subtract_rl(expr, implied, recurse_cnt, res);
654 	case '/':
655 		return handle_divide_rl(expr, implied, recurse_cnt, res);
656 	}
657 
658 	if (!left_rl || !right_rl)
659 		return false;
660 
661 	if (sval_binop_overflows(rl_min(left_rl), expr->op, rl_min(right_rl)))
662 		return false;
663 	if (sval_binop_overflows(rl_max(left_rl), expr->op, rl_max(right_rl)))
664 		return false;
665 
666 	min = sval_binop(rl_min(left_rl), expr->op, rl_min(right_rl));
667 	max = sval_binop(rl_max(left_rl), expr->op, rl_max(right_rl));
668 
669 	*res = alloc_rl(min, max);
670 	return true;
671 
672 }
673 
674 static bool handle_binop_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
675 {
676 	struct smatch_state *state;
677 	struct range_list *rl;
678 	sval_t val;
679 
680 	if (handle_known_binop(expr, &val)) {
681 		*res_sval = val;
682 		return true;
683 	}
684 	if (implied == RL_EXACT)
685 		return false;
686 
687 	if (custom_handle_variable) {
688 		rl = custom_handle_variable(expr);
689 		if (rl) {
690 			*res = rl;
691 			return true;
692 		}
693 	}
694 
695 	state = get_extra_state(expr);
696 	if (state && !is_whole_rl(estate_rl(state))) {
697 		if (implied != RL_HARD || estate_has_hard_max(state)) {
698 			*res = clone_rl(estate_rl(state));
699 			return true;
700 		}
701 	}
702 
703 	return handle_binop_rl_helper(expr, implied, recurse_cnt, res, res_sval);
704 }
705 
706 static int do_comparison(struct expression *expr)
707 {
708 	struct range_list *left_ranges = NULL;
709 	struct range_list *right_ranges = NULL;
710 	int poss_true, poss_false;
711 	struct symbol *type;
712 
713 	type = get_type(expr);
714 	get_absolute_rl(expr->left, &left_ranges);
715 	get_absolute_rl(expr->right, &right_ranges);
716 
717 	left_ranges = cast_rl(type, left_ranges);
718 	right_ranges = cast_rl(type, right_ranges);
719 
720 	poss_true = possibly_true_rl(left_ranges, expr->op, right_ranges);
721 	poss_false = possibly_false_rl(left_ranges, expr->op, right_ranges);
722 
723 	if (!poss_true && !poss_false)
724 		return 0x0;
725 	if (poss_true && !poss_false)
726 		return 0x1;
727 	if (!poss_true && poss_false)
728 		return 0x2;
729 	return 0x3;
730 }
731 
732 static bool handle_comparison_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
733 {
734 	sval_t left, right;
735 	int cmp;
736 
737 	if (expr->op == SPECIAL_EQUAL && expr->left->type == EXPR_TYPE) {
738 		struct symbol *left, *right;
739 
740 		if (expr->right->type != EXPR_TYPE)
741 			return false;
742 
743 		left = get_real_base_type(expr->left->symbol);
744 		right = get_real_base_type(expr->right->symbol);
745 		if (type_bits(left) == type_bits(right) &&
746 		    type_positive_bits(left) == type_positive_bits(right))
747 			*res_sval = one;
748 		else
749 			*res_sval = zero;
750 		return true;
751 	}
752 
753 	if (get_value(expr->left, &left) && get_value(expr->right, &right)) {
754 		struct data_range tmp_left, tmp_right;
755 
756 		tmp_left.min = left;
757 		tmp_left.max = left;
758 		tmp_right.min = right;
759 		tmp_right.max = right;
760 		if (true_comparison_range(&tmp_left, expr->op, &tmp_right))
761 			*res_sval = one;
762 		else
763 			*res_sval = zero;
764 		return true;
765 	}
766 
767 	if (implied == RL_EXACT)
768 		return false;
769 
770 	cmp = do_comparison(expr);
771 	if (cmp == 1) {
772 		*res_sval = one;
773 		return true;
774 	}
775 	if (cmp == 2) {
776 		*res_sval = zero;
777 		return true;
778 	}
779 
780 	*res = alloc_rl(zero, one);
781 	return true;
782 }
783 
784 static bool handle_logical_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
785 {
786 	sval_t left, right;
787 	int left_known = 0;
788 	int right_known = 0;
789 
790 	if (implied == RL_EXACT) {
791 		if (get_value(expr->left, &left))
792 			left_known = 1;
793 		if (get_value(expr->right, &right))
794 			right_known = 1;
795 	} else {
796 		if (get_implied_value_internal(expr->left, recurse_cnt, &left))
797 			left_known = 1;
798 		if (get_implied_value_internal(expr->right, recurse_cnt, &right))
799 			right_known = 1;
800 	}
801 
802 	switch (expr->op) {
803 	case SPECIAL_LOGICAL_OR:
804 		if (left_known && left.value)
805 			goto one;
806 		if (right_known && right.value)
807 			goto one;
808 		if (left_known && right_known)
809 			goto zero;
810 		break;
811 	case SPECIAL_LOGICAL_AND:
812 		if (left_known && right_known) {
813 			if (left.value && right.value)
814 				goto one;
815 			goto zero;
816 		}
817 		break;
818 	default:
819 		return false;
820 	}
821 
822 	if (implied == RL_EXACT)
823 		return false;
824 
825 	*res = alloc_rl(zero, one);
826 	return true;
827 
828 zero:
829 	*res_sval = zero;
830 	return true;
831 one:
832 	*res_sval = one;
833 	return true;
834 }
835 
836 static bool handle_conditional_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
837 {
838 	struct expression *cond_true;
839 	struct range_list *true_rl, *false_rl;
840 	struct symbol *type;
841 	int final_pass_orig = final_pass;
842 
843 	cond_true = expr->cond_true;
844 	if (!cond_true)
845 		cond_true = expr->conditional;
846 
847 	if (known_condition_true(expr->conditional))
848 		return get_rl_sval(cond_true, implied, recurse_cnt, res, res_sval);
849 	if (known_condition_false(expr->conditional))
850 		return get_rl_sval(expr->cond_false, implied, recurse_cnt, res, res_sval);
851 
852 	if (implied == RL_EXACT)
853 		return false;
854 
855 	if (implied_condition_true(expr->conditional))
856 		return get_rl_sval(cond_true, implied, recurse_cnt, res, res_sval);
857 	if (implied_condition_false(expr->conditional))
858 		return get_rl_sval(expr->cond_false, implied, recurse_cnt, res, res_sval);
859 
860 	/* this becomes a problem with deeply nested conditional statements */
861 	if (fast_math_only || low_on_memory())
862 		return false;
863 
864 	type = get_type(expr);
865 
866 	__push_fake_cur_stree();
867 	final_pass = 0;
868 	__split_whole_condition(expr->conditional);
869 	true_rl = NULL;
870 	get_rl_internal(cond_true, implied, recurse_cnt, &true_rl);
871 	__push_true_states();
872 	__use_false_states();
873 	false_rl = NULL;
874 	get_rl_internal(expr->cond_false, implied, recurse_cnt, &false_rl);
875 	__merge_true_states();
876 	__free_fake_cur_stree();
877 	final_pass = final_pass_orig;
878 
879 	if (!true_rl || !false_rl)
880 		return false;
881 	true_rl = cast_rl(type, true_rl);
882 	false_rl = cast_rl(type, false_rl);
883 
884 	*res = rl_union(true_rl, false_rl);
885 	return true;
886 }
887 
888 static bool get_fuzzy_max_helper(struct expression *expr, sval_t *max)
889 {
890 	struct smatch_state *state;
891 	sval_t sval;
892 
893 	if (get_hard_max(expr, &sval)) {
894 		*max = sval;
895 		return true;
896 	}
897 
898 	state = get_extra_state(expr);
899 	if (!state || !estate_has_fuzzy_max(state))
900 		return false;
901 	*max = sval_cast(get_type(expr), estate_get_fuzzy_max(state));
902 	return true;
903 }
904 
905 static bool get_fuzzy_min_helper(struct expression *expr, sval_t *min)
906 {
907 	struct smatch_state *state;
908 	sval_t sval;
909 
910 	state = get_extra_state(expr);
911 	if (!state || !estate_rl(state))
912 		return false;
913 
914 	sval = estate_min(state);
915 	if (sval_is_negative(sval) && sval_is_min(sval))
916 		return false;
917 
918 	if (sval_is_max(sval))
919 		return false;
920 
921 	*min = sval_cast(get_type(expr), sval);
922 	return true;
923 }
924 
925 int get_const_value(struct expression *expr, sval_t *sval)
926 {
927 	struct symbol *sym;
928 	sval_t right;
929 
930 	if (expr->type != EXPR_SYMBOL || !expr->symbol)
931 		return 0;
932 	sym = expr->symbol;
933 	if (!(sym->ctype.modifiers & MOD_CONST))
934 		return 0;
935 	if (get_value(sym->initializer, &right)) {
936 		*sval = sval_cast(get_type(expr), right);
937 		return 1;
938 	}
939 	return 0;
940 }
941 
942 struct range_list *var_to_absolute_rl(struct expression *expr)
943 {
944 	struct smatch_state *state;
945 	struct range_list *rl;
946 
947 	state = get_extra_state(expr);
948 	if (!state || is_whole_rl(estate_rl(state))) {
949 		state = get_real_absolute_state(expr);
950 		if (state && state->data && !estate_is_whole(state))
951 			return clone_rl(estate_rl(state));
952 		if (get_mtag_rl(expr, &rl))
953 			return rl;
954 		if (get_db_type_rl(expr, &rl) && !is_whole_rl(rl))
955 			return rl;
956 		return alloc_whole_rl(get_type(expr));
957 	}
958 	/* err on the side of saying things are possible */
959 	if (!estate_rl(state))
960 		return alloc_whole_rl(get_type(expr));
961 	return clone_rl(estate_rl(state));
962 }
963 
964 static bool handle_variable(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
965 {
966 	struct smatch_state *state;
967 	struct range_list *rl;
968 	sval_t sval, min, max;
969 	struct symbol *type;
970 
971 	if (get_const_value(expr, &sval)) {
972 		*res_sval = sval;
973 		return true;
974 	}
975 
976 	if (implied == RL_EXACT)
977 		return false;
978 
979 	if (custom_handle_variable) {
980 		rl = custom_handle_variable(expr);
981 		if (rl) {
982 			if (!rl_to_sval(rl, res_sval))
983 				*res = rl;
984 		} else {
985 			*res = var_to_absolute_rl(expr);
986 		}
987 		return true;
988 	}
989 
990 	if (get_mtag_sval(expr, &sval)) {
991 		*res_sval = sval;
992 		return true;
993 	}
994 
995 	type = get_type(expr);
996 	if (type &&
997 	    (type->type == SYM_ARRAY ||
998 	     type->type == SYM_FN))
999 		return handle_address(expr, implied, recurse_cnt, res, res_sval);
1000 
1001 	/* FIXME: call rl_to_sval() on the results */
1002 
1003 	switch (implied) {
1004 	case RL_HARD:
1005 	case RL_IMPLIED:
1006 	case RL_ABSOLUTE:
1007 		state = get_extra_state(expr);
1008 		if (!state) {
1009 			if (implied == RL_HARD)
1010 				return false;
1011 			if (get_mtag_rl(expr, res))
1012 				return true;
1013 			if (get_db_type_rl(expr, res))
1014 				return true;
1015 			if (is_array(expr) && get_array_rl(expr, res))
1016 				return true;
1017 			return false;
1018 		}
1019 		if (implied == RL_HARD && !estate_has_hard_max(state))
1020 			return false;
1021 		*res = clone_rl(estate_rl(state));
1022 		return true;
1023 	case RL_REAL_ABSOLUTE: {
1024 		struct smatch_state *abs_state;
1025 
1026 		state = get_extra_state(expr);
1027 		abs_state = get_real_absolute_state(expr);
1028 
1029 		if (estate_rl(state) && estate_rl(abs_state)) {
1030 			*res = clone_rl(rl_intersection(estate_rl(state),
1031 							estate_rl(abs_state)));
1032 			return true;
1033 		} else if (estate_rl(state)) {
1034 			*res = clone_rl(estate_rl(state));
1035 			return true;
1036 		} else if (estate_is_empty(state)) {
1037 			/*
1038 			 * FIXME: we don't handle empty extra states correctly.
1039 			 *
1040 			 * The real abs rl is supposed to be filtered by the
1041 			 * extra state if there is one.  We don't bother keeping
1042 			 * the abs state in sync all the time because we know it
1043 			 * will be filtered later.
1044 			 *
1045 			 * It's not totally obvious to me how they should be
1046 			 * handled.  Perhaps we should take the whole rl and
1047 			 * filter by the imaginary states.  Perhaps we should
1048 			 * just go with the empty state.
1049 			 *
1050 			 * Anyway what we currently do is return NULL here and
1051 			 * that gets translated into the whole range in
1052 			 * get_real_absolute_rl().
1053 			 *
1054 			 */
1055 			return false;
1056 		} else if (estate_rl(abs_state)) {
1057 			*res = clone_rl(estate_rl(abs_state));
1058 			return true;
1059 		}
1060 
1061 		if (get_mtag_rl(expr, res))
1062 			return true;
1063 		if (get_db_type_rl(expr, res))
1064 			return true;
1065 		if (is_array(expr) && get_array_rl(expr, res))
1066 			return true;
1067 		return false;
1068 	}
1069 	case RL_FUZZY:
1070 		if (!get_fuzzy_min_helper(expr, &min))
1071 			min = sval_type_min(get_type(expr));
1072 		if (!get_fuzzy_max_helper(expr, &max))
1073 			return false;
1074 		/* fuzzy ranges are often inverted */
1075 		if (sval_cmp(min, max) > 0) {
1076 			sval = min;
1077 			min = max;
1078 			max = sval;
1079 		}
1080 		*res = alloc_rl(min, max);
1081 		return true;
1082 	}
1083 	return false;
1084 }
1085 
1086 static sval_t handle_sizeof(struct expression *expr)
1087 {
1088 	struct symbol *sym;
1089 	sval_t ret;
1090 
1091 	ret = sval_blank(expr);
1092 	sym = expr->cast_type;
1093 	if (!sym) {
1094 		sym = evaluate_expression(expr->cast_expression);
1095 		if (!sym) {
1096 			__silence_warnings_for_stmt = true;
1097 			sym = &int_ctype;
1098 		}
1099 #if 0
1100 		/*
1101 		 * Expressions of restricted types will possibly get
1102 		 * promoted - check that here.  I'm not sure how this works,
1103 		 * the problem is that sizeof(le16) shouldn't be promoted and
1104 		 * the original code did that...  Let's if zero this out and
1105 		 * see what breaks.
1106 		 */
1107 
1108 		if (is_restricted_type(sym)) {
1109 			if (type_bits(sym) < bits_in_int)
1110 				sym = &int_ctype;
1111 		}
1112 #endif
1113 		if (is_fouled_type(sym))
1114 			sym = &int_ctype;
1115 	}
1116 	examine_symbol_type(sym);
1117 
1118 	ret.type = size_t_ctype;
1119 	if (type_bits(sym) <= 0) /* sizeof(void) */ {
1120 		if (get_real_base_type(sym) == &void_ctype)
1121 			ret.value = 1;
1122 		else
1123 			ret.value = 0;
1124 	} else
1125 		ret.value = type_bytes(sym);
1126 
1127 	return ret;
1128 }
1129 
1130 static bool handle_strlen(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
1131 {
1132 	struct expression *arg, *tmp;
1133 	sval_t tag;
1134 	sval_t ret = { .type = &ulong_ctype };
1135 	struct range_list *rl;
1136 
1137 	arg = get_argument_from_call_expr(expr->args, 0);
1138 	if (!arg)
1139 		return false;
1140 	if (arg->type == EXPR_STRING) {
1141 		ret.value = arg->string->length - 1;
1142 		*res_sval = ret;
1143 		return true;
1144 	}
1145 	if (implied == RL_EXACT)
1146 		return false;
1147 	if (get_implied_value(arg, &tag) &&
1148 	    (tmp = fake_string_from_mtag(tag.uvalue))) {
1149 		ret.value = tmp->string->length - 1;
1150 		*res_sval = ret;
1151 		return true;
1152 	}
1153 
1154 	if (implied == RL_HARD || implied == RL_FUZZY)
1155 		return false;
1156 
1157 	if (get_implied_return(expr, &rl)) {
1158 		*res = rl;
1159 		return true;
1160 	}
1161 
1162 	return false;
1163 }
1164 
1165 static bool handle_builtin_constant_p(struct expression *expr, int implied, int *recurse_cnt, sval_t *res_sval)
1166 {
1167 	struct expression *arg;
1168 	struct range_list *rl;
1169 
1170 	arg = get_argument_from_call_expr(expr->args, 0);
1171 	if (get_rl_internal(arg, RL_EXACT, recurse_cnt, &rl))
1172 		*res_sval = one;
1173 	else
1174 		*res_sval = zero;
1175 	return true;
1176 }
1177 
1178 static bool handle__builtin_choose_expr(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
1179 {
1180 	struct expression *const_expr, *expr1, *expr2;
1181 	sval_t sval;
1182 
1183 	const_expr = get_argument_from_call_expr(expr->args, 0);
1184 	expr1 = get_argument_from_call_expr(expr->args, 1);
1185 	expr2 = get_argument_from_call_expr(expr->args, 2);
1186 
1187 	if (!get_value(const_expr, &sval) || !expr1 || !expr2)
1188 		return false;
1189 	if (sval.value)
1190 		return get_rl_sval(expr1, implied, recurse_cnt, res, res_sval);
1191 	else
1192 		return get_rl_sval(expr2, implied, recurse_cnt, res, res_sval);
1193 }
1194 
1195 static bool handle_call_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
1196 {
1197 	struct range_list *rl;
1198 
1199 	if (sym_name_is("__builtin_constant_p", expr->fn))
1200 		return handle_builtin_constant_p(expr, implied, recurse_cnt, res_sval);
1201 
1202 	if (sym_name_is("__builtin_choose_expr", expr->fn))
1203 		return handle__builtin_choose_expr(expr, implied, recurse_cnt, res, res_sval);
1204 
1205 	if (sym_name_is("__builtin_expect", expr->fn) ||
1206 	    sym_name_is("__builtin_bswap16", expr->fn) ||
1207 	    sym_name_is("__builtin_bswap32", expr->fn) ||
1208 	    sym_name_is("__builtin_bswap64", expr->fn)) {
1209 		struct expression *arg;
1210 
1211 		arg = get_argument_from_call_expr(expr->args, 0);
1212 		return get_rl_sval(arg, implied, recurse_cnt, res, res_sval);
1213 	}
1214 
1215 	if (sym_name_is("strlen", expr->fn))
1216 		return handle_strlen(expr, implied, recurse_cnt, res, res_sval);
1217 
1218 	if (implied == RL_EXACT || implied == RL_HARD || implied == RL_FUZZY)
1219 		return false;
1220 
1221 	if (custom_handle_variable) {
1222 		rl = custom_handle_variable(expr);
1223 		if (rl) {
1224 			*res = rl;
1225 			return true;
1226 		}
1227 	}
1228 
1229 	/* Ugh...  get_implied_return() sets *rl to NULL on failure */
1230 	if (get_implied_return(expr, &rl)) {
1231 		*res = rl;
1232 		return true;
1233 	}
1234 	rl = db_return_vals(expr);
1235 	if (rl) {
1236 		*res = rl;
1237 		return true;
1238 	}
1239 	return false;
1240 }
1241 
1242 static bool handle_cast(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
1243 {
1244 	struct range_list *rl;
1245 	struct symbol *type;
1246 	sval_t sval = {};
1247 
1248 	type = get_type(expr);
1249 	if (get_rl_sval(expr->cast_expression, implied, recurse_cnt, &rl, &sval)) {
1250 		if (sval.type)
1251 			*res_sval = sval_cast(type, sval);
1252 		else
1253 			*res = cast_rl(type, rl);
1254 		return true;
1255 	}
1256 	if (implied == RL_ABSOLUTE || implied == RL_REAL_ABSOLUTE) {
1257 		*res = alloc_whole_rl(type);
1258 		return true;
1259 	}
1260 	if (implied == RL_IMPLIED && type &&
1261 	    type_bits(type) > 0 && type_bits(type) < 32) {
1262 		*res = alloc_whole_rl(type);
1263 		return true;
1264 	}
1265 	return false;
1266 }
1267 
1268 static bool get_offset_from_down(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
1269 {
1270 	struct expression *index;
1271 	struct symbol *type = expr->in;
1272 	struct range_list *rl;
1273 	struct symbol *field;
1274 	int offset = 0;
1275 	sval_t sval = { .type = ssize_t_ctype };
1276 	sval_t tmp_sval = {};
1277 
1278 	/*
1279 	 * FIXME:  I don't really know what I'm doing here.  I wish that I
1280 	 * could just get rid of the __builtin_offset() function and use:
1281 	 * "&((struct bpf_prog *)NULL)->insns[fprog->len]" instead...
1282 	 * Anyway, I have done the minimum ammount of work to get that
1283 	 * expression to work.
1284 	 *
1285 	 */
1286 
1287 	if (expr->op != '.' || !expr->down ||
1288 	    expr->down->type != EXPR_OFFSETOF ||
1289 	    expr->down->op != '[' ||
1290 	    !expr->down->index)
1291 		return false;
1292 
1293 	index = expr->down->index;
1294 
1295 	examine_symbol_type(type);
1296 	type = get_real_base_type(type);
1297 	if (!type)
1298 		return false;
1299 	field = find_identifier(expr->ident, type->symbol_list, &offset);
1300 	if (!field)
1301 		return false;
1302 
1303 	type = get_real_base_type(field);
1304 	if (!type || type->type != SYM_ARRAY)
1305 		return false;
1306 	type = get_real_base_type(type);
1307 
1308 	if (get_implied_value_internal(index, recurse_cnt, &sval)) {
1309 		res_sval->type = ssize_t_ctype;
1310 		res_sval->value = offset + sval.value * type_bytes(type);
1311 		return true;
1312 	}
1313 
1314 	if (!get_rl_sval(index, implied, recurse_cnt, &rl, &tmp_sval))
1315 		return false;
1316 
1317 	/*
1318 	 * I'm not sure why get_rl_sval() would return an sval when
1319 	 * get_implied_value_internal() failed but it does when I
1320 	 * parse drivers/net/ethernet/mellanox/mlx5/core/en/monitor_stats.c
1321 	 *
1322 	 */
1323 	if (tmp_sval.type) {
1324 		res_sval->type = ssize_t_ctype;
1325 		res_sval->value = offset + sval.value * type_bytes(type);
1326 		return true;
1327 	}
1328 
1329 	sval.value = type_bytes(type);
1330 	rl = rl_binop(rl, '*', alloc_rl(sval, sval));
1331 	sval.value = offset;
1332 	*res = rl_binop(rl, '+', alloc_rl(sval, sval));
1333 	return true;
1334 }
1335 
1336 static bool get_offset_from_in(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
1337 {
1338 	struct symbol *type = get_real_base_type(expr->in);
1339 	struct symbol *field;
1340 	int offset = 0;
1341 
1342 	if (expr->op != '.' || !type || !expr->ident)
1343 		return false;
1344 
1345 	field = find_identifier(expr->ident, type->symbol_list, &offset);
1346 	if (!field)
1347 		return false;
1348 
1349 	res_sval->type = size_t_ctype;
1350 	res_sval->value = offset;
1351 
1352 	return true;
1353 }
1354 
1355 static bool handle_offsetof_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
1356 {
1357 	if (get_offset_from_down(expr, implied, recurse_cnt, res, res_sval))
1358 		return true;
1359 
1360 	if (get_offset_from_in(expr, implied, recurse_cnt, res, res_sval))
1361 		return true;
1362 
1363 	evaluate_expression(expr);
1364 	if (expr->type == EXPR_VALUE) {
1365 		*res_sval = sval_from_val(expr, expr->value);
1366 		return true;
1367 	}
1368 	return false;
1369 }
1370 
1371 static bool get_rl_sval(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *sval_res)
1372 {
1373 	struct range_list *rl = (void *)-1UL;
1374 	struct symbol *type;
1375 	sval_t sval = {};
1376 
1377 	type = get_type(expr);
1378 	expr = strip_parens(expr);
1379 	if (!expr)
1380 		return false;
1381 
1382 	if (++(*recurse_cnt) >= 200)
1383 		return false;
1384 
1385 	switch(expr->type) {
1386 	case EXPR_CAST:
1387 	case EXPR_FORCE_CAST:
1388 	case EXPR_IMPLIED_CAST:
1389 		handle_cast(expr, implied, recurse_cnt, &rl, &sval);
1390 		goto out_cast;
1391 	}
1392 
1393 	expr = strip_expr(expr);
1394 	if (!expr)
1395 		return false;
1396 
1397 	switch (expr->type) {
1398 	case EXPR_VALUE:
1399 		sval = sval_from_val(expr, expr->value);
1400 		break;
1401 	case EXPR_FVALUE:
1402 		sval = sval_from_fval(expr, expr->fvalue);
1403 		break;
1404 	case EXPR_PREOP:
1405 		handle_preop_rl(expr, implied, recurse_cnt, &rl, &sval);
1406 		break;
1407 	case EXPR_POSTOP:
1408 		get_rl_sval(expr->unop, implied, recurse_cnt, &rl, &sval);
1409 		break;
1410 	case EXPR_BINOP:
1411 		handle_binop_rl(expr, implied, recurse_cnt, &rl, &sval);
1412 		break;
1413 	case EXPR_COMPARE:
1414 		handle_comparison_rl(expr, implied, recurse_cnt, &rl, &sval);
1415 		break;
1416 	case EXPR_LOGICAL:
1417 		handle_logical_rl(expr, implied, recurse_cnt, &rl, &sval);
1418 		break;
1419 	case EXPR_PTRSIZEOF:
1420 	case EXPR_SIZEOF:
1421 		sval = handle_sizeof(expr);
1422 		break;
1423 	case EXPR_SELECT:
1424 	case EXPR_CONDITIONAL:
1425 		handle_conditional_rl(expr, implied, recurse_cnt, &rl, &sval);
1426 		break;
1427 	case EXPR_CALL:
1428 		handle_call_rl(expr, implied, recurse_cnt, &rl, &sval);
1429 		break;
1430 	case EXPR_STRING:
1431 		if (get_mtag_sval(expr, &sval))
1432 			break;
1433 		if (implied == RL_EXACT)
1434 			break;
1435 		rl = alloc_rl(valid_ptr_min_sval, valid_ptr_max_sval);
1436 		break;
1437 	case EXPR_OFFSETOF:
1438 		handle_offsetof_rl(expr, implied, recurse_cnt, &rl, &sval);
1439 		break;
1440 	case EXPR_ALIGNOF:
1441 		evaluate_expression(expr);
1442 		if (expr->type == EXPR_VALUE)
1443 			sval = sval_from_val(expr, expr->value);
1444 		break;
1445 	default:
1446 		handle_variable(expr, implied, recurse_cnt, &rl, &sval);
1447 	}
1448 
1449 out_cast:
1450 	if (rl == (void *)-1UL)
1451 		rl = NULL;
1452 
1453 	if (sval.type || (rl && rl_to_sval(rl, &sval))) {
1454 		*sval_res = sval;
1455 		return true;
1456 	}
1457 	if (implied == RL_EXACT)
1458 		return false;
1459 
1460 	if (rl) {
1461 		*res = rl;
1462 		return true;
1463 	}
1464 	if (type && (implied == RL_ABSOLUTE || implied == RL_REAL_ABSOLUTE)) {
1465 		*res = alloc_whole_rl(type);
1466 		return true;
1467 	}
1468 	return false;
1469 }
1470 
1471 static bool get_rl_internal(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res)
1472 {
1473 	struct range_list *rl = NULL;
1474 	sval_t sval = {};
1475 
1476 	if (!get_rl_sval(expr, implied, recurse_cnt, &rl, &sval))
1477 		return false;
1478 
1479 	if (sval.type)
1480 		*res = alloc_rl(sval, sval);
1481 	else
1482 		*res = rl;
1483 	return true;
1484 }
1485 
1486 static bool get_rl_helper(struct expression *expr, int implied, struct range_list **res)
1487 {
1488 	struct range_list *rl = NULL;
1489 	sval_t sval = {};
1490 	int recurse_cnt = 0;
1491 
1492 	if (get_value(expr, &sval)) {
1493 		*res = alloc_rl(sval, sval);
1494 		return true;
1495 	}
1496 
1497 	if (!get_rl_sval(expr, implied, &recurse_cnt, &rl, &sval))
1498 		return false;
1499 
1500 	if (sval.type)
1501 		*res = alloc_rl(sval, sval);
1502 	else
1503 		*res = rl;
1504 	return true;
1505 }
1506 
1507 struct {
1508 	struct expression *expr;
1509 	sval_t sval;
1510 } cached_results[24];
1511 static int cache_idx;
1512 
1513 void clear_math_cache(void)
1514 {
1515 	memset(cached_results, 0, sizeof(cached_results));
1516 }
1517 
1518 void set_fast_math_only(void)
1519 {
1520 	fast_math_only++;
1521 }
1522 
1523 void clear_fast_math_only(void)
1524 {
1525 	fast_math_only--;
1526 }
1527 
1528 /*
1529  * Don't cache EXPR_VALUE because values are fast already.
1530  *
1531  */
1532 static bool get_value_literal(struct expression *expr, sval_t *res_sval)
1533 {
1534 	struct expression *tmp;
1535 	int recurse_cnt = 0;
1536 
1537 	tmp = strip_expr(expr);
1538 	if (!tmp || tmp->type != EXPR_VALUE)
1539 		return false;
1540 
1541 	return get_rl_sval(expr, RL_EXACT, &recurse_cnt, NULL, res_sval);
1542 }
1543 
1544 /* returns 1 if it can get a value literal or else returns 0 */
1545 int get_value(struct expression *expr, sval_t *res_sval)
1546 {
1547 	struct range_list *(*orig_custom_fn)(struct expression *expr);
1548 	int recurse_cnt = 0;
1549 	sval_t sval = {};
1550 	int i;
1551 
1552 	if (get_value_literal(expr, res_sval))
1553 		return 1;
1554 
1555 	/*
1556 	 * This only handles RL_EXACT because other expr statements can be
1557 	 * different at different points.  Like the list iterator, for example.
1558 	 */
1559 	for (i = 0; i < ARRAY_SIZE(cached_results); i++) {
1560 		if (expr == cached_results[i].expr) {
1561 			if (cached_results[i].sval.type) {
1562 				*res_sval = cached_results[i].sval;
1563 				return true;
1564 			}
1565 			return false;
1566 		}
1567 	}
1568 
1569 	orig_custom_fn = custom_handle_variable;
1570 	custom_handle_variable = NULL;
1571 	get_rl_sval(expr, RL_EXACT, &recurse_cnt, NULL, &sval);
1572 
1573 	custom_handle_variable = orig_custom_fn;
1574 
1575 	cached_results[cache_idx].expr = expr;
1576 	cached_results[cache_idx].sval = sval;
1577 	cache_idx = (cache_idx + 1) % ARRAY_SIZE(cached_results);
1578 
1579 	if (!sval.type)
1580 		return 0;
1581 
1582 	*res_sval = sval;
1583 	return 1;
1584 }
1585 
1586 static bool get_implied_value_internal(struct expression *expr, int *recurse_cnt, sval_t *res_sval)
1587 {
1588 	struct range_list *rl;
1589 
1590 	res_sval->type = NULL;
1591 
1592 	if (!get_rl_sval(expr, RL_IMPLIED, recurse_cnt, &rl, res_sval))
1593 		return false;
1594 	if (!res_sval->type && !rl_to_sval(rl, res_sval))
1595 		return false;
1596 	return true;
1597 }
1598 
1599 int get_implied_value(struct expression *expr, sval_t *sval)
1600 {
1601 	struct range_list *rl;
1602 
1603 	if (!get_rl_helper(expr, RL_IMPLIED, &rl) ||
1604 	    !rl_to_sval(rl, sval))
1605 		return 0;
1606 	return 1;
1607 }
1608 
1609 int get_implied_value_fast(struct expression *expr, sval_t *sval)
1610 {
1611 	struct range_list *rl;
1612 	static int recurse;
1613 	int ret = 0;
1614 
1615 	if (recurse)
1616 		return 0;
1617 
1618 	recurse = 1;
1619 	set_fast_math_only();
1620 	if (get_rl_helper(expr, RL_IMPLIED, &rl) &&
1621 	    rl_to_sval(rl, sval))
1622 		ret = 1;
1623 	clear_fast_math_only();
1624 	recurse = 0;
1625 
1626 	return ret;
1627 }
1628 
1629 int get_implied_min(struct expression *expr, sval_t *sval)
1630 {
1631 	struct range_list *rl;
1632 
1633 	if (!get_rl_helper(expr, RL_IMPLIED, &rl) || !rl)
1634 		return 0;
1635 	*sval = rl_min(rl);
1636 	return 1;
1637 }
1638 
1639 int get_implied_max(struct expression *expr, sval_t *sval)
1640 {
1641 	struct range_list *rl;
1642 
1643 	if (!get_rl_helper(expr, RL_IMPLIED, &rl) || !rl)
1644 		return 0;
1645 	*sval = rl_max(rl);
1646 	return 1;
1647 }
1648 
1649 int get_implied_rl(struct expression *expr, struct range_list **rl)
1650 {
1651 	if (!get_rl_helper(expr, RL_IMPLIED, rl) || !*rl)
1652 		return 0;
1653 	return 1;
1654 }
1655 
1656 static int get_absolute_rl_internal(struct expression *expr, struct range_list **rl, int *recurse_cnt)
1657 {
1658 	*rl = NULL;
1659 	get_rl_internal(expr, RL_ABSOLUTE, recurse_cnt, rl);
1660 	if (!*rl)
1661 		*rl = alloc_whole_rl(get_type(expr));
1662 	return 1;
1663 }
1664 
1665 int get_absolute_rl(struct expression *expr, struct range_list **rl)
1666 {
1667 	*rl = NULL;
1668 	 get_rl_helper(expr, RL_ABSOLUTE, rl);
1669 	if (!*rl)
1670 		*rl = alloc_whole_rl(get_type(expr));
1671 	return 1;
1672 }
1673 
1674 int get_real_absolute_rl(struct expression *expr, struct range_list **rl)
1675 {
1676 	*rl = NULL;
1677 	get_rl_helper(expr, RL_REAL_ABSOLUTE, rl);
1678 	if (!*rl)
1679 		*rl = alloc_whole_rl(get_type(expr));
1680 	return 1;
1681 }
1682 
1683 int custom_get_absolute_rl(struct expression *expr,
1684 			   struct range_list *(*fn)(struct expression *expr),
1685 			   struct range_list **rl)
1686 {
1687 	int ret;
1688 
1689 	*rl = NULL;
1690 	custom_handle_variable = fn;
1691 	ret = get_rl_helper(expr, RL_REAL_ABSOLUTE, rl);
1692 	custom_handle_variable = NULL;
1693 	return ret;
1694 }
1695 
1696 int get_implied_rl_var_sym(const char *var, struct symbol *sym, struct range_list **rl)
1697 {
1698 	struct smatch_state *state;
1699 
1700 	state = get_state(SMATCH_EXTRA, var, sym);
1701 	*rl = estate_rl(state);
1702 	if (*rl)
1703 		return 1;
1704 	return 0;
1705 }
1706 
1707 int get_hard_max(struct expression *expr, sval_t *sval)
1708 {
1709 	struct range_list *rl;
1710 
1711 	if (!get_rl_helper(expr, RL_HARD, &rl) || !rl)
1712 		return 0;
1713 	*sval = rl_max(rl);
1714 	return 1;
1715 }
1716 
1717 int get_fuzzy_min(struct expression *expr, sval_t *sval)
1718 {
1719 	struct range_list *rl;
1720 	sval_t tmp;
1721 
1722 	if (!get_rl_helper(expr, RL_FUZZY, &rl) || !rl)
1723 		return 0;
1724 	tmp = rl_min(rl);
1725 	if (sval_is_negative(tmp) && sval_is_min(tmp))
1726 		return 0;
1727 	*sval = tmp;
1728 	return 1;
1729 }
1730 
1731 int get_fuzzy_max(struct expression *expr, sval_t *sval)
1732 {
1733 	struct range_list *rl;
1734 	sval_t max;
1735 
1736 	if (!get_rl_helper(expr, RL_FUZZY, &rl) || !rl)
1737 		return 0;
1738 	max = rl_max(rl);
1739 	if (max.uvalue > INT_MAX - 10000)
1740 		return 0;
1741 	*sval = max;
1742 	return 1;
1743 }
1744 
1745 int get_absolute_min(struct expression *expr, sval_t *sval)
1746 {
1747 	struct range_list *rl;
1748 	struct symbol *type;
1749 
1750 	type = get_type(expr);
1751 	if (!type)
1752 		type = &llong_ctype;  // FIXME: this is wrong but places assume get type can't fail.
1753 	rl = NULL;
1754 	get_rl_helper(expr, RL_REAL_ABSOLUTE, &rl);
1755 	if (rl)
1756 		*sval = rl_min(rl);
1757 	else
1758 		*sval = sval_type_min(type);
1759 
1760 	if (sval_cmp(*sval, sval_type_min(type)) < 0)
1761 		*sval = sval_type_min(type);
1762 	return 1;
1763 }
1764 
1765 int get_absolute_max(struct expression *expr, sval_t *sval)
1766 {
1767 	struct range_list *rl;
1768 	struct symbol *type;
1769 
1770 	type = get_type(expr);
1771 	if (!type)
1772 		type = &llong_ctype;
1773 	rl = NULL;
1774 	get_rl_helper(expr, RL_REAL_ABSOLUTE, &rl);
1775 	if (rl)
1776 		*sval = rl_max(rl);
1777 	else
1778 		*sval = sval_type_max(type);
1779 
1780 	if (sval_cmp(sval_type_max(type), *sval) < 0)
1781 		*sval = sval_type_max(type);
1782 	return 1;
1783 }
1784 
1785 int known_condition_true(struct expression *expr)
1786 {
1787 	sval_t tmp;
1788 
1789 	if (!expr)
1790 		return 0;
1791 
1792 	if (__inline_fn && get_param_num(expr) >= 0) {
1793 		if (get_implied_value(expr, &tmp) && tmp.value)
1794 			return 1;
1795 		return 0;
1796 	}
1797 
1798 	if (get_value(expr, &tmp) && tmp.value)
1799 		return 1;
1800 
1801 	return 0;
1802 }
1803 
1804 int known_condition_false(struct expression *expr)
1805 {
1806 	sval_t tmp;
1807 
1808 	if (!expr)
1809 		return 0;
1810 
1811 	if (__inline_fn && get_param_num(expr) >= 0) {
1812 		if (get_implied_value(expr, &tmp) && tmp.value == 0)
1813 			return 1;
1814 		return 0;
1815 	}
1816 
1817 	if (expr_is_zero(expr))
1818 		return 1;
1819 
1820 	return 0;
1821 }
1822 
1823 int implied_condition_true(struct expression *expr)
1824 {
1825 	sval_t tmp;
1826 
1827 	if (!expr)
1828 		return 0;
1829 
1830 	if (known_condition_true(expr))
1831 		return 1;
1832 	if (get_implied_value(expr, &tmp) && tmp.value)
1833 		return 1;
1834 
1835 	if (expr->type == EXPR_POSTOP)
1836 		return implied_condition_true(expr->unop);
1837 
1838 	if (expr->type == EXPR_PREOP && expr->op == SPECIAL_DECREMENT)
1839 		return implied_not_equal(expr->unop, 1);
1840 	if (expr->type == EXPR_PREOP && expr->op == SPECIAL_INCREMENT)
1841 		return implied_not_equal(expr->unop, -1);
1842 
1843 	expr = strip_expr(expr);
1844 	switch (expr->type) {
1845 	case EXPR_COMPARE:
1846 		if (do_comparison(expr) == 1)
1847 			return 1;
1848 		break;
1849 	case EXPR_PREOP:
1850 		if (expr->op == '!') {
1851 			if (implied_condition_false(expr->unop))
1852 				return 1;
1853 			break;
1854 		}
1855 		break;
1856 	default:
1857 		if (implied_not_equal(expr, 0) == 1)
1858 			return 1;
1859 		break;
1860 	}
1861 	return 0;
1862 }
1863 
1864 int implied_condition_false(struct expression *expr)
1865 {
1866 	struct expression *tmp;
1867 	sval_t sval;
1868 
1869 	if (!expr)
1870 		return 0;
1871 
1872 	if (known_condition_false(expr))
1873 		return 1;
1874 
1875 	switch (expr->type) {
1876 	case EXPR_COMPARE:
1877 		if (do_comparison(expr) == 2)
1878 			return 1;
1879 	case EXPR_PREOP:
1880 		if (expr->op == '!') {
1881 			if (implied_condition_true(expr->unop))
1882 				return 1;
1883 			break;
1884 		}
1885 		tmp = strip_expr(expr);
1886 		if (tmp != expr)
1887 			return implied_condition_false(tmp);
1888 		break;
1889 	default:
1890 		if (get_implied_value(expr, &sval) && sval.value == 0)
1891 			return 1;
1892 		break;
1893 	}
1894 	return 0;
1895 }
1896 
1897 
1898