11f5207bJohn Levon/*
21f5207bJohn Levon * Copyright (C) 2010 Dan Carpenter.
31f5207bJohn Levon *
41f5207bJohn Levon * This program is free software; you can redistribute it and/or
51f5207bJohn Levon * modify it under the terms of the GNU General Public License
61f5207bJohn Levon * as published by the Free Software Foundation; either version 2
71f5207bJohn Levon * of the License, or (at your option) any later version.
81f5207bJohn Levon *
91f5207bJohn Levon * This program is distributed in the hope that it will be useful,
101f5207bJohn Levon * but WITHOUT ANY WARRANTY; without even the implied warranty of
111f5207bJohn Levon * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
121f5207bJohn Levon * GNU General Public License for more details.
131f5207bJohn Levon *
141f5207bJohn Levon * You should have received a copy of the GNU General Public License
151f5207bJohn Levon * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
161f5207bJohn Levon */
171f5207bJohn Levon
181f5207bJohn Levon#include "symbol.h"
191f5207bJohn Levon#include "smatch.h"
201f5207bJohn Levon#include "smatch_slist.h"
211f5207bJohn Levon#include "smatch_extra.h"
221f5207bJohn Levon
23efe51d0John Levonstatic bool get_rl_sval(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *sval_res);
24efe51d0John Levonstatic bool get_rl_internal(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res);
25efe51d0John Levonstatic bool handle_variable(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval);
261f5207bJohn Levonstatic struct range_list *(*custom_handle_variable)(struct expression *expr);
271f5207bJohn Levon
28efe51d0John Levonstatic bool get_implied_value_internal(struct expression *expr, int *recurse_cnt, sval_t *res_sval);
291f5207bJohn Levonstatic int get_absolute_rl_internal(struct expression *expr, struct range_list **rl, int *recurse_cnt);
301f5207bJohn Levon
311f5207bJohn Levonstatic sval_t zero  = {.type = &int_ctype, {.value = 0} };
321f5207bJohn Levonstatic sval_t one   = {.type = &int_ctype, {.value = 1} };
331f5207bJohn Levon
34c85f09cJohn Levonstatic int fast_math_only;
35c85f09cJohn Levon
361f5207bJohn Levonstruct range_list *rl_zero(void)
371f5207bJohn Levon{
381f5207bJohn Levon	static struct range_list *zero_perm;
391f5207bJohn Levon
401f5207bJohn Levon	if (!zero_perm)
411f5207bJohn Levon		zero_perm = clone_rl_permanent(alloc_rl(zero, zero));
421f5207bJohn Levon	return zero_perm;
431f5207bJohn Levon}
441f5207bJohn Levon
451f5207bJohn Levonstruct range_list *rl_one(void)
461f5207bJohn Levon{
471f5207bJohn Levon	static struct range_list *one_perm;
481f5207bJohn Levon
491f5207bJohn Levon	if (!one_perm)
501f5207bJohn Levon		one_perm = clone_rl_permanent(alloc_rl(one, one));
511f5207bJohn Levon
521f5207bJohn Levon	return one_perm;
531f5207bJohn Levon}
541f5207bJohn Levon
551f5207bJohn Levonenum {
561f5207bJohn Levon	RL_EXACT,
571f5207bJohn Levon	RL_HARD,
581f5207bJohn Levon	RL_FUZZY,
591f5207bJohn Levon	RL_IMPLIED,
601f5207bJohn Levon	RL_ABSOLUTE,
611f5207bJohn Levon	RL_REAL_ABSOLUTE,
621f5207bJohn Levon};
631f5207bJohn Levon
64efe51d0John Levonstatic bool last_stmt_rl(struct statement *stmt, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
651f5207bJohn Levon{
661f5207bJohn Levon	struct expression *expr;
671f5207bJohn Levon
681f5207bJohn Levon	if (!stmt)
69efe51d0John Levon		return false;
701f5207bJohn Levon
711f5207bJohn Levon	stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
721f5207bJohn Levon	if (stmt->type == STMT_LABEL) {
731f5207bJohn Levon		if (stmt->label_statement &&
741f5207bJohn Levon		    stmt->label_statement->type == STMT_EXPRESSION)
751f5207bJohn Levon			expr = stmt->label_statement->expression;
761f5207bJohn Levon		else
77efe51d0John Levon			return false;
781f5207bJohn Levon	} else if (stmt->type == STMT_EXPRESSION) {
791f5207bJohn Levon		expr = stmt->expression;
801f5207bJohn Levon	} else {
81efe51d0John Levon		return false;
821f5207bJohn Levon	}
83efe51d0John Levon	return get_rl_sval(expr, implied, recurse_cnt, res, res_sval);
841f5207bJohn Levon}
851f5207bJohn Levon
86efe51d0John Levonstatic bool handle_expression_statement_rl(struct expression *expr, int implied,
87efe51d0John Levon		int *recurse_cnt, struct range_list **res, sval_t *res_sval)
881f5207bJohn Levon{
89efe51d0John Levon	return last_stmt_rl(get_expression_statement(expr), implied, recurse_cnt, res, res_sval);
901f5207bJohn Levon}
911f5207bJohn Levon
92efe51d0John Levonstatic bool handle_address(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
931f5207bJohn Levon{
941f5207bJohn Levon	struct range_list *rl;
95efe51d0John Levon	static int recursed;
961f5207bJohn Levon	sval_t sval;
971f5207bJohn Levon
98efe51d0John Levon	if (recursed > 10)
99efe51d0John Levon		return false;
100efe51d0John Levon	if (implied == RL_EXACT)
101efe51d0John Levon		return false;
102efe51d0John Levon
103efe51d0John Levon	if (custom_handle_variable) {
104efe51d0John Levon		rl = custom_handle_variable(expr);
105efe51d0John Levon		if (rl) {
106efe51d0John Levon			*res = rl;
107efe51d0John Levon			return true;
108efe51d0John Levon		}
109efe51d0John Levon	}
110efe51d0John Levon
111efe51d0John Levon	recursed++;
112efe51d0John Levon	if (get_mtag_sval(expr, &sval)) {
113efe51d0John Levon		recursed--;
114efe51d0John Levon		*res_sval = sval;
115efe51d0John Levon		return true;
116efe51d0John Levon	}
117efe51d0John Levon
118efe51d0John Levon	if (get_address_rl(expr, res)) {
119efe51d0John Levon		recursed--;
120efe51d0John Levon		return true;
121efe51d0John Levon	}
122efe51d0John Levon	recursed--;
123efe51d0John Levon	return 0;
124efe51d0John Levon}
125efe51d0John Levon
126efe51d0John Levonstatic bool handle_ampersand_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
127efe51d0John Levon{
128efe51d0John Levon	return handle_address(expr, implied, recurse_cnt, res, res_sval);
1291f5207bJohn Levon}
1301f5207bJohn Levon
131efe51d0John Levonstatic bool handle_negate_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
1321f5207bJohn Levon{
133efe51d0John Levon	if (known_condition_true(expr->unop)) {
134efe51d0John Levon		*res_sval = zero;
135efe51d0John Levon		return true;
136efe51d0John Levon	}
137efe51d0John Levon	if (known_condition_false(expr->unop)) {
138efe51d0John Levon		*res_sval = one;
139efe51d0John Levon		return true;
140efe51d0John Levon	}
1411f5207bJohn Levon
1421f5207bJohn Levon	if (implied == RL_EXACT)
143efe51d0John Levon		return false;
1441f5207bJohn Levon
145efe51d0John Levon	if (implied_condition_true(expr->unop)) {
146efe51d0John Levon		*res_sval = zero;
147efe51d0John Levon		return true;
148efe51d0John Levon	}
149efe51d0John Levon	if (implied_condition_false(expr->unop)) {
150efe51d0John Levon		*res_sval = one;
151efe51d0John Levon		return true;
152efe51d0John Levon	}
153efe51d0John Levon
154efe51d0John Levon	*res = alloc_rl(zero, one);
155efe51d0John Levon	return true;
1561f5207bJohn Levon}
1571f5207bJohn Levon
158efe51d0John Levonstatic bool handle_bitwise_negate(struct expression *expr, int implied, int *recurse_cnt, sval_t *res_sval)
1591f5207bJohn Levon{
1601f5207bJohn Levon	struct range_list *rl;
161efe51d0John Levon	sval_t sval = {};
1621f5207bJohn Levon
163efe51d0John Levon	if (!get_rl_sval(expr->unop, implied, recurse_cnt, &rl, &sval))
164efe51d0John Levon		return false;
165efe51d0John Levon	if (!sval.type && !rl_to_sval(rl, &sval))
166efe51d0John Levon		return false;
1671f5207bJohn Levon	sval = sval_preop(sval, '~');
1681f5207bJohn Levon	sval_cast(get_type(expr->unop), sval);
169efe51d0John Levon	*res_sval = sval;
170efe51d0John Levon	return true;
1711f5207bJohn Levon}
1721f5207bJohn Levon
173efe51d0John Levonstatic bool untrusted_type_min(struct expression *expr)
1741f5207bJohn Levon{
1751f5207bJohn Levon	struct range_list *rl;
1761f5207bJohn Levon
177efe51d0John Levon	rl = var_user_rl(expr);
178efe51d0John Levon	return rl && sval_is_min(rl_min(rl));
1791f5207bJohn Levon}
1801f5207bJohn Levon
181efe51d0John Levonstatic bool handle_minus_preop(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
182efe51d0John Levon{
183efe51d0John Levon	struct range_list *rl;
184efe51d0John Levon	struct range_list *ret = NULL;
185efe51d0John Levon	struct symbol *type;
186efe51d0John Levon	sval_t neg_one = { 0 };
187efe51d0John Levon	sval_t zero = { 0 };
188efe51d0John Levon	sval_t sval = {};
189efe51d0John Levon
190efe51d0John Levon	neg_one.value = -1;
191efe51d0John Levon	zero.value = 0;
192efe51d0John Levon
193efe51d0John Levon	if (!get_rl_sval(expr->unop, implied, recurse_cnt, &rl, &sval))
194efe51d0John Levon		return false;
195efe51d0John Levon	if (sval.type) {
196efe51d0John Levon		*res_sval = sval_preop(sval, '-');
197efe51d0John Levon		return true;
198efe51d0John Levon	}
199efe51d0John Levon	/*
200efe51d0John Levon	 * One complication is that -INT_MIN is still INT_MIN because of integer
201efe51d0John Levon	 * overflows...  But how many times do we set a time out to INT_MIN?
202efe51d0John Levon	 * So normally when we call abs() then it does return a positive value.
203efe51d0John Levon	 *
204efe51d0John Levon	 */
205efe51d0John Levon	type = rl_type(rl);
206efe51d0John Levon	neg_one.type = zero.type = type;
207efe51d0John Levon
208efe51d0John Levon	if (sval_is_negative(rl_min(rl))) {
209efe51d0John Levon		struct range_list *neg;
210efe51d0John Levon		struct data_range *drange;
211efe51d0John Levon		sval_t new_min, new_max;
212efe51d0John Levon
213efe51d0John Levon		neg = alloc_rl(sval_type_min(type), neg_one);
214efe51d0John Levon		neg = rl_intersection(rl, neg);
215efe51d0John Levon
216efe51d0John Levon		if (sval_is_min(rl_min(neg)) && !sval_is_min(rl_max(neg)))
217efe51d0John Levon			neg = remove_range(neg, sval_type_min(type), sval_type_min(type));
218efe51d0John Levon
219efe51d0John Levon		FOR_EACH_PTR(neg, drange) {
220efe51d0John Levon			new_min = drange->max;
221efe51d0John Levon			new_min.value = -new_min.value;
222efe51d0John Levon			new_max = drange->min;
223efe51d0John Levon			new_max.value = -new_max.value;
224efe51d0John Levon			add_range(&ret, new_min, new_max);
225efe51d0John Levon		} END_FOR_EACH_PTR(drange);
226efe51d0John Levon
227efe51d0John Levon		if (untrusted_type_min(expr))
228efe51d0John Levon			add_range(&ret, sval_type_min(type), sval_type_min(type));
229efe51d0John Levon	}
230efe51d0John Levon
231efe51d0John Levon	if (!sval_is_negative(rl_max(rl))) {
232efe51d0John Levon		struct range_list *pos;
233efe51d0John Levon		struct data_range *drange;
234efe51d0John Levon		sval_t new_min, new_max;
235efe51d0John Levon
236efe51d0John Levon		pos = alloc_rl(zero, sval_type_max(type));
237efe51d0John Levon		pos = rl_intersection(rl, pos);
238efe51d0John Levon
239efe51d0John Levon		FOR_EACH_PTR(pos, drange) {
240efe51d0John Levon			new_min = drange->max;
241efe51d0John Levon			new_min.value = -new_min.value;
242efe51d0John Levon			new_max = drange->min;
243efe51d0John Levon			new_max.value = -new_max.value;
244efe51d0John Levon			add_range(&ret, new_min, new_max);
245efe51d0John Levon		} END_FOR_EACH_PTR(drange);
246efe51d0John Levon	}
247efe51d0John Levon
248efe51d0John Levon	*res = ret;
249efe51d0John Levon	return true;
250efe51d0John Levon}
251efe51d0John Levon
252efe51d0John Levonstatic bool handle_preop_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
2531f5207bJohn Levon{
2541f5207bJohn Levon	switch (expr->op) {
2551f5207bJohn Levon	case '&':
256efe51d0John Levon		return handle_ampersand_rl(expr, implied, recurse_cnt, res, res_sval);
2571f5207bJohn Levon	case '!':
258efe51d0John Levon		return handle_negate_rl(expr, implied, recurse_cnt, res, res_sval);
2591f5207bJohn Levon	case '~':
260efe51d0John Levon		return handle_bitwise_negate(expr, implied, recurse_cnt, res_sval);
2611f5207bJohn Levon	case '-':
262efe51d0John Levon		return handle_minus_preop(expr, implied, recurse_cnt, res, res_sval);
2631f5207bJohn Levon	case '*':
264efe51d0John Levon		return handle_variable(expr, implied, recurse_cnt, res, res_sval);
2651f5207bJohn Levon	case '(':
266efe51d0John Levon		return handle_expression_statement_rl(expr, implied, recurse_cnt, res, res_sval);
2671f5207bJohn Levon	default:
268efe51d0John Levon		return false;
2691f5207bJohn Levon	}
2701f5207bJohn Levon}
2711f5207bJohn Levon
272efe51d0John Levonstatic bool handle_divide_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res)
2731f5207bJohn Levon{
274efe51d0John Levon	struct range_list *left_rl = NULL;
275efe51d0John Levon	struct range_list *right_rl = NULL;
2761f5207bJohn Levon	struct symbol *type;
2771f5207bJohn Levon
2781f5207bJohn Levon	type = get_type(expr);
2791f5207bJohn Levon
280efe51d0John Levon	get_rl_internal(expr->left, implied, recurse_cnt, &left_rl);
2811f5207bJohn Levon	left_rl = cast_rl(type, left_rl);
282efe51d0John Levon	get_rl_internal(expr->right, implied, recurse_cnt, &right_rl);
2831f5207bJohn Levon	right_rl = cast_rl(type, right_rl);
2841f5207bJohn Levon
2851f5207bJohn Levon	if (!left_rl || !right_rl)
286efe51d0John Levon		return false;
2871f5207bJohn Levon
2881f5207bJohn Levon	if (implied != RL_REAL_ABSOLUTE) {
2891f5207bJohn Levon		if (is_whole_rl(left_rl) || is_whole_rl(right_rl))
290efe51d0John Levon			return false;
2911f5207bJohn Levon	}
2921f5207bJohn Levon
293efe51d0John Levon	*res = rl_binop(left_rl, '/', right_rl);
294efe51d0John Levon	return true;
2951f5207bJohn Levon}
2961f5207bJohn Levon
2971f5207bJohn Levonstatic int handle_offset_subtraction(struct expression *expr)
2981f5207bJohn Levon{
2991f5207bJohn Levon	struct expression *left, *right;
3001f5207bJohn Levon	struct symbol *left_sym, *right_sym;
3011f5207bJohn Levon	struct symbol *type;
3021f5207bJohn Levon	int left_offset, right_offset;
3031f5207bJohn Levon
3041f5207bJohn Levon	type = get_type(expr);
3051f5207bJohn Levon	if (!type || type->type != SYM_PTR)
3061f5207bJohn Levon		return -1;
3071f5207bJohn Levon	type = get_real_base_type(type);
3081f5207bJohn Levon	if (!type || (type_bits(type) != 8 && (type != &void_ctype)))
3091f5207bJohn Levon		return -1;
3101f5207bJohn Levon
3111f5207bJohn Levon	left = strip_expr(expr->left);
3121f5207bJohn Levon	right = strip_expr(expr->right);
3131f5207bJohn Levon
3141f5207bJohn Levon	if (left->type != EXPR_PREOP || left->op != '&')
3151f5207bJohn Levon		return -1;
3161f5207bJohn Levon	left = strip_expr(left->unop);
3171f5207bJohn Levon
3181f5207bJohn Levon	left_sym = expr_to_sym(left);
3191f5207bJohn Levon	right_sym = expr_to_sym(right);
3201f5207bJohn Levon	if (!left_sym || left_sym != right_sym)
3211f5207bJohn Levon		return -1;
3221f5207bJohn Levon
3231f5207bJohn Levon	left_offset = get_member_offset_from_deref(left);
3241f5207bJohn Levon	if (right->type == EXPR_SYMBOL)
3251f5207bJohn Levon		right_offset = 0;
3261f5207bJohn Levon	else {
3271f5207bJohn Levon		if (right->type != EXPR_PREOP || right->op != '&')
3281f5207bJohn Levon			return -1;
3291f5207bJohn Levon		right = strip_expr(right->unop);
3301f5207bJohn Levon		right_offset = get_member_offset_from_deref(right);
3311f5207bJohn Levon	}
3321f5207bJohn Levon	if (left_offset < 0 || right_offset < 0)
3331f5207bJohn Levon		return -1;
3341f5207bJohn Levon
3351f5207bJohn Levon	return left_offset - right_offset;
3361f5207bJohn Levon}
3371f5207bJohn Levon
338efe51d0John Levonstatic bool handle_subtract_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res)
3391f5207bJohn Levon{
3401f5207bJohn Levon	struct symbol *type;
3411f5207bJohn Levon	struct range_list *left_orig, *right_orig;
3421f5207bJohn Levon	struct range_list *left_rl, *right_rl;
343efe51d0John Levon	sval_t min, max, tmp;
3441f5207bJohn Levon	int comparison;
3451f5207bJohn Levon	int offset;
3461f5207bJohn Levon
3471f5207bJohn Levon	type = get_type(expr);
3481f5207bJohn Levon
3491f5207bJohn Levon	offset = handle_offset_subtraction(expr);
3501f5207bJohn Levon	if (offset >= 0) {
3511f5207bJohn Levon		tmp.type = type;
3521f5207bJohn Levon		tmp.value = offset;
3531f5207bJohn Levon
354efe51d0John Levon		*res = alloc_rl(tmp, tmp);
355efe51d0John Levon		return true;
3561f5207bJohn Levon	}
3571f5207bJohn Levon
3581f5207bJohn Levon	comparison = get_comparison(expr->left, expr->right);
3591f5207bJohn Levon
360efe51d0John Levon	left_orig = NULL;
361efe51d0John Levon	get_rl_internal(expr->left, implied, recurse_cnt, &left_orig);
3621f5207bJohn Levon	left_rl = cast_rl(type, left_orig);
363efe51d0John Levon	right_orig = NULL;
364efe51d0John Levon	get_rl_internal(expr->right, implied, recurse_cnt, &right_orig);
3651f5207bJohn Levon	right_rl = cast_rl(type, right_orig);
3661f5207bJohn Levon
3671f5207bJohn Levon	if ((!left_rl || !right_rl) &&
3681f5207bJohn Levon	    (implied == RL_EXACT || implied == RL_HARD || implied == RL_FUZZY))
369efe51d0John Levon		return false;
3701f5207bJohn Levon
3711f5207bJohn Levon	if (!left_rl)
3721f5207bJohn Levon		left_rl = alloc_whole_rl(type);
3731f5207bJohn Levon	if (!right_rl)
3741f5207bJohn Levon		right_rl = alloc_whole_rl(type);
3751f5207bJohn Levon
3761f5207bJohn Levon	/* negative values complicate everything fix this later */
3771f5207bJohn Levon	if (sval_is_negative(rl_min(right_rl)))
378efe51d0John Levon		return false;
3791f5207bJohn Levon	max = rl_max(left_rl);
3801f5207bJohn Levon	min = sval_type_min(type);
3811f5207bJohn Levon
3821f5207bJohn Levon	switch (comparison) {
3831f5207bJohn Levon	case '>':
3841f5207bJohn Levon	case SPECIAL_UNSIGNED_GT:
3851f5207bJohn Levon		min = sval_type_val(type, 1);
3861f5207bJohn Levon		max = rl_max(left_rl);
3871f5207bJohn Levon		break;
3881f5207bJohn Levon	case SPECIAL_GTE:
3891f5207bJohn Levon	case SPECIAL_UNSIGNED_GTE:
3901f5207bJohn Levon		min = sval_type_val(type, 0);
3911f5207bJohn Levon		max = rl_max(left_rl);
3921f5207bJohn Levon		break;
3931f5207bJohn Levon	case SPECIAL_EQUAL:
3941f5207bJohn Levon		min = sval_type_val(type, 0);
3951f5207bJohn Levon		max = sval_type_val(type, 0);
3961f5207bJohn Levon		break;
3971f5207bJohn Levon	case '<':
3981f5207bJohn Levon	case SPECIAL_UNSIGNED_LT:
3991f5207bJohn Levon		max = sval_type_val(type, -1);
4001f5207bJohn Levon		break;
4011f5207bJohn Levon	case SPECIAL_LTE:
4021f5207bJohn Levon	case SPECIAL_UNSIGNED_LTE:
4031f5207bJohn Levon		max = sval_type_val(type, 0);
4041f5207bJohn Levon		break;
4051f5207bJohn Levon	default:
4061f5207bJohn Levon		if (!left_orig || !right_orig)
407efe51d0John Levon			return false;
408efe51d0John Levon		*res = rl_binop(left_rl, '-', right_rl);
409efe51d0John Levon		return true;
4101f5207bJohn Levon	}
4111f5207bJohn Levon
4121f5207bJohn Levon	if (!sval_binop_overflows(rl_min(left_rl), '-', rl_max(right_rl))) {
4131f5207bJohn Levon		tmp = sval_binop(rl_min(left_rl), '-', rl_max(right_rl));
4141f5207bJohn Levon		if (sval_cmp(tmp, min) > 0)
4151f5207bJohn Levon			min = tmp;
4161f5207bJohn Levon	}
4171f5207bJohn Levon
4181f5207bJohn Levon	if (!sval_is_max(rl_max(left_rl))) {
4191f5207bJohn Levon		tmp = sval_binop(rl_max(left_rl), '-', rl_min(right_rl));
4201f5207bJohn Levon		if (sval_cmp(tmp, max) < 0)
4211f5207bJohn Levon			max = tmp;
4221f5207bJohn Levon	}
4231f5207bJohn Levon
4241f5207bJohn Levon	if (sval_is_min(min) && sval_is_max(max))
425efe51d0John Levon		return false;
4261f5207bJohn Levon
427efe51d0John Levon	*res = cast_rl(type, alloc_rl(min, max));
428efe51d0John Levon	return true;
4291f5207bJohn Levon}
4301f5207bJohn Levon
431efe51d0John Levonstatic bool handle_mod_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res)
4321f5207bJohn Levon{
4331f5207bJohn Levon	struct range_list *rl;
4341f5207bJohn Levon	sval_t left, right, sval;
4351f5207bJohn Levon
4361f5207bJohn Levon	if (implied == RL_EXACT) {
4371f5207bJohn Levon		if (!get_implied_value(expr->right, &right))
438efe51d0John Levon			return false;
4391f5207bJohn Levon		if (!get_implied_value(expr->left, &left))
440efe51d0John Levon			return false;
4411f5207bJohn Levon		sval = sval_binop(left, '%', right);
442efe51d0John Levon		*res = alloc_rl(sval, sval);
443efe51d0John Levon		return true;
4441f5207bJohn Levon	}
4451f5207bJohn Levon	/* if we can't figure out the right side it's probably hopeless */
446efe51d0John Levon	if (!get_implied_value_internal(expr->right, recurse_cnt, &right))
447efe51d0John Levon		return false;
4481f5207bJohn Levon
4491f5207bJohn Levon	right = sval_cast(get_type(expr), right);
4501f5207bJohn Levon	right.value--;
4511f5207bJohn Levon
452efe51d0John Levon	if (get_rl_internal(expr->left, implied, recurse_cnt, &rl) && rl &&
453efe51d0John Levon	    rl_max(rl).uvalue < right.uvalue)
4541f5207bJohn Levon		right.uvalue = rl_max(rl).uvalue;
4551f5207bJohn Levon
456efe51d0John Levon	*res = alloc_rl(sval_cast(right.type, zero), right);
457efe51d0John Levon	return true;
4581f5207bJohn Levon}
4591f5207bJohn Levon
460efe51d0John Levonstatic bool handle_bitwise_AND(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res)
4611f5207bJohn Levon{
4621f5207bJohn Levon	struct symbol *type;
4631f5207bJohn Levon	struct range_list *left_rl, *right_rl;
4641f5207bJohn Levon	int new_recurse;
4651f5207bJohn Levon
4661f5207bJohn Levon	if (implied != RL_IMPLIED && implied != RL_ABSOLUTE && implied != RL_REAL_ABSOLUTE)
467efe51d0John Levon		return false;
4681f5207bJohn Levon
4691f5207bJohn Levon	type = get_type(expr);
4701f5207bJohn Levon
471efe51d0John Levon	if (!get_rl_internal(expr->left, implied, recurse_cnt, &left_rl))
472efe51d0John Levon		left_rl = alloc_whole_rl(type);
473efe51d0John Levon	left_rl = cast_rl(type, left_rl);
4741f5207bJohn Levon
4751f5207bJohn Levon	new_recurse = *recurse_cnt;
4761f5207bJohn Levon	if (*recurse_cnt >= 200)
4771f5207bJohn Levon		new_recurse = 100;  /* Let's try super hard to get the mask */
478efe51d0John Levon	if (!get_rl_internal(expr->right, implied, &new_recurse, &right_rl))
479efe51d0John Levon		right_rl = alloc_whole_rl(type);
480efe51d0John Levon	right_rl = cast_rl(type, right_rl);
481efe51d0John Levon	*recurse_cnt = new_recurse;
4821f5207bJohn Levon
483efe51d0John Levon	*res = rl_binop(left_rl, '&', right_rl);
484efe51d0John Levon	return true;
4851f5207bJohn Levon}
4861f5207bJohn Levon
487efe51d0John Levonstatic bool use_rl_binop(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res)
4881f5207bJohn Levon{
4891f5207bJohn Levon	struct symbol *type;
4901f5207bJohn Levon	struct range_list *left_rl, *right_rl;
4911f5207bJohn Levon
4921f5207bJohn Levon	if (implied != RL_IMPLIED && implied != RL_ABSOLUTE && implied != RL_REAL_ABSOLUTE)
493efe51d0John Levon		return false;
4941f5207bJohn Levon
4951f5207bJohn Levon	type = get_type(expr);
4961f5207bJohn Levon
4971f5207bJohn Levon	get_absolute_rl_internal(expr->left, &left_rl, recurse_cnt);
4981f5207bJohn Levon	get_absolute_rl_internal(expr->right, &right_rl, recurse_cnt);
4991f5207bJohn Levon	left_rl = cast_rl(type, left_rl);
5001f5207bJohn Levon	right_rl = cast_rl(type, right_rl);
5011f5207bJohn Levon	if (!left_rl || !right_rl)
502efe51d0John Levon		return false;
5031f5207bJohn Levon
504efe51d0John Levon	*res = rl_binop(left_rl, expr->op, right_rl);
505efe51d0John Levon	return true;
5061f5207bJohn Levon}
5071f5207bJohn Levon
508efe51d0John Levonstatic bool handle_right_shift(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res)
5091f5207bJohn Levon{
510efe51d0John Levon	struct range_list *left_rl, *right_rl;
5111f5207bJohn Levon	sval_t min, max;
5121f5207bJohn Levon
5131f5207bJohn Levon	if (implied == RL_EXACT || implied == RL_HARD)
514efe51d0John Levon		return false;
5151f5207bJohn Levon
516efe51d0John Levon	if (get_rl_internal(expr->left, implied, recurse_cnt, &left_rl)) {
5171f5207bJohn Levon		max = rl_max(left_rl);
5181f5207bJohn Levon		min = rl_min(left_rl);
5191f5207bJohn Levon	} else {
5201f5207bJohn Levon		if (implied == RL_FUZZY)
521efe51d0John Levon			return false;
5221f5207bJohn Levon		max = sval_type_max(get_type(expr->left));
5231f5207bJohn Levon		min = sval_type_val(get_type(expr->left), 0);
5241f5207bJohn Levon	}
5251f5207bJohn Levon
526efe51d0John Levon	if (get_rl_internal(expr->right, implied, recurse_cnt, &right_rl) &&
527efe51d0John Levon	    !sval_is_negative(rl_min(right_rl))) {
528efe51d0John Levon		min = sval_binop(min, SPECIAL_RIGHTSHIFT, rl_max(right_rl));
529efe51d0John Levon		max = sval_binop(max, SPECIAL_RIGHTSHIFT, rl_min(right_rl));
5301f5207bJohn Levon	} else if (!sval_is_negative(min)) {
5311f5207bJohn Levon		min.value = 0;
5321f5207bJohn Levon		max = sval_type_max(max.type);
5331f5207bJohn Levon	} else {
534efe51d0John Levon		return false;
5351f5207bJohn Levon	}
5361f5207bJohn Levon
537efe51d0John Levon	*res = alloc_rl(min, max);
538efe51d0John Levon	return true;
5391f5207bJohn Levon}
5401f5207bJohn Levon
541efe51d0John Levonstatic bool handle_left_shift(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res)
5421f5207bJohn Levon{
543efe51d0John Levon	struct range_list *left_rl, *rl;
5441f5207bJohn Levon	sval_t right;
5451f5207bJohn Levon
5461f5207bJohn Levon	if (implied == RL_EXACT || implied == RL_HARD)
547efe51d0John Levon		return false;
5481f5207bJohn Levon	/* this is hopeless without the right side */
549efe51d0John Levon	if (!get_implied_value_internal(expr->right, recurse_cnt, &right))
550efe51d0John Levon		return false;
551efe51d0John Levon	if (!get_rl_internal(expr->left, implied, recurse_cnt, &left_rl)) {
5521f5207bJohn Levon		if (implied == RL_FUZZY)
553efe51d0John Levon			return false;
554efe51d0John Levon		left_rl = alloc_whole_rl(get_type(expr->left));
5551f5207bJohn Levon	}
5561f5207bJohn Levon
557efe51d0John Levon	rl = rl_binop(left_rl, SPECIAL_LEFTSHIFT, alloc_rl(right, right));
558efe51d0John Levon	if (!rl)
559efe51d0John Levon		return false;
560efe51d0John Levon	*res = rl;
561efe51d0John Levon	return true;
5621f5207bJohn Levon}
5631f5207bJohn Levon
564efe51d0John Levonstatic bool handle_known_binop(struct expression *expr, sval_t *res)
5651f5207bJohn Levon{
5661f5207bJohn Levon	sval_t left, right;
5671f5207bJohn Levon
5681f5207bJohn Levon	if (!get_value(expr->left, &left))
569efe51d0John Levon		return false;
5701f5207bJohn Levon	if (!get_value(expr->right, &right))
571efe51d0John Levon		return false;
572efe51d0John Levon	*res = sval_binop(left, expr->op, right);
573efe51d0John Levon	return true;
5741f5207bJohn Levon}
5751f5207bJohn Levon
5761f5207bJohn Levonstatic int has_actual_ranges(struct range_list *rl)
5771f5207bJohn Levon{
5781f5207bJohn Levon	struct data_range *tmp;
5791f5207bJohn Levon
5801f5207bJohn Levon	FOR_EACH_PTR(rl, tmp) {
5811f5207bJohn Levon		if (sval_cmp(tmp->min, tmp->max) != 0)
5821f5207bJohn Levon			return 1;
5831f5207bJohn Levon	} END_FOR_EACH_PTR(tmp);
5841f5207bJohn Levon	return 0;
5851f5207bJohn Levon}
5861f5207bJohn Levon
5871f5207bJohn Levonstatic struct range_list *handle_implied_binop(struct range_list *left_rl, int op, struct range_list *right_rl)
5881f5207bJohn Levon{
5891f5207bJohn Levon	struct range_list *res_rl;
5901f5207bJohn Levon	struct data_range *left_drange, *right_drange;
5911f5207bJohn Levon	sval_t res;
5921f5207bJohn Levon
5931f5207bJohn Levon	if (!left_rl || !right_rl)
5941f5207bJohn Levon		return NULL;
5951f5207bJohn Levon	if (has_actual_ranges(left_rl))
5961f5207bJohn Levon		return NULL;
5971f5207bJohn Levon	if (has_actual_ranges(right_rl))
5981f5207bJohn Levon		return NULL;
5991f5207bJohn Levon
6001f5207bJohn Levon	if (ptr_list_size((struct ptr_list *)left_rl) * ptr_list_size((struct ptr_list *)right_rl) > 20)
6011f5207bJohn Levon		return NULL;
6021f5207bJohn Levon
6031f5207bJohn Levon	res_rl = NULL;
6041f5207bJohn Levon
6051f5207bJohn Levon	FOR_EACH_PTR(left_rl, left_drange) {
6061f5207bJohn Levon		FOR_EACH_PTR(right_rl, right_drange) {
6071f5207bJohn Levon			if ((op == '%' || op == '/') &&
6081f5207bJohn Levon			    right_drange->min.value == 0)
6091f5207bJohn Levon				return NULL;
6101f5207bJohn Levon			res = sval_binop(left_drange->min, op, right_drange->min);
6111f5207bJohn Levon			add_range(&res_rl, res, res);
6121f5207bJohn Levon		} END_FOR_EACH_PTR(right_drange);
6131f5207bJohn Levon	} END_FOR_EACH_PTR(left_drange);
6141f5207bJohn Levon
6151f5207bJohn Levon	return res_rl;
6161f5207bJohn Levon}
6171f5207bJohn Levon
618efe51d0John Levonstatic bool handle_binop_rl_helper(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
6191f5207bJohn Levon{
6201f5207bJohn Levon	struct symbol *type;
621efe51d0John Levon	struct range_list *left_rl = NULL;
622efe51d0John Levon	struct range_list *right_rl = NULL;
623efe51d0John Levon	struct range_list *rl;
6241f5207bJohn Levon	sval_t min, max;
6251f5207bJohn Levon
626efe51d0John Levon	type = get_promoted_type(get_type(expr->left), get_type(expr->right));
627efe51d0John Levon	get_rl_internal(expr->left, implied, recurse_cnt, &left_rl);
6281f5207bJohn Levon	left_rl = cast_rl(type, left_rl);
629efe51d0John Levon	get_rl_internal(expr->right, implied, recurse_cnt, &right_rl);
6301f5207bJohn Levon	right_rl = cast_rl(type, right_rl);
6311f5207bJohn Levon	if (!left_rl && !right_rl)
632efe51d0John Levon		return false;
6331f5207bJohn Levon
6341f5207bJohn Levon	rl = handle_implied_binop(left_rl, expr->op, right_rl);
635efe51d0John Levon	if (rl) {
636efe51d0John Levon		*res = rl;
637efe51d0John Levon		return true;
638efe51d0John Levon	}
6391f5207bJohn Levon
6401f5207bJohn Levon	switch (expr->op) {
6411f5207bJohn Levon	case '%':
642efe51d0John Levon		return handle_mod_rl(expr, implied, recurse_cnt, res);
6431f5207bJohn Levon	case '&':
644efe51d0John Levon		return handle_bitwise_AND(expr, implied, recurse_cnt, res);
6451f5207bJohn Levon	case '|':
6461f5207bJohn Levon	case '^':
647efe51d0John Levon		return use_rl_binop(expr, implied, recurse_cnt, res);
6481f5207bJohn Levon	case SPECIAL_RIGHTSHIFT:
649efe51d0John Levon		return handle_right_shift(expr, implied, recurse_cnt, res);
6501f5207bJohn Levon	case SPECIAL_LEFTSHIFT:
651efe51d0John Levon		return handle_left_shift(expr, implied, recurse_cnt, res);
6521f5207bJohn Levon	case '-':
653efe51d0John Levon		return handle_subtract_rl(expr, implied, recurse_cnt, res);
6541f5207bJohn Levon	case '/':
655efe51d0John Levon		return handle_divide_rl(expr, implied, recurse_cnt, res);
6561f5207bJohn Levon	}
6571f5207bJohn Levon
6581f5207bJohn Levon	if (!left_rl || !right_rl)
659efe51d0John Levon		return false;
6601f5207bJohn Levon
6611f5207bJohn Levon	if (sval_binop_overflows(rl_min(left_rl), expr->op, rl_min(right_rl)))
662efe51d0John Levon		return false;
6631f5207bJohn Levon	if (sval_binop_overflows(rl_max(left_rl), expr->op, rl_max(right_rl)))
664efe51d0John Levon		return false;
6651f5207bJohn Levon
6661f5207bJohn Levon	min = sval_binop(rl_min(left_rl), expr->op, rl_min(right_rl));
6671f5207bJohn Levon	max = sval_binop(rl_max(left_rl), expr->op, rl_max(right_rl));
6681f5207bJohn Levon
669efe51d0John Levon	*res = alloc_rl(min, max);
670efe51d0John Levon	return true;
671efe51d0John Levon
672efe51d0John Levon}
673efe51d0John Levon
674efe51d0John Levonstatic bool handle_binop_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
675efe51d0John Levon{
676efe51d0John Levon	struct smatch_state *state;
677efe51d0John Levon	struct range_list *rl;
678efe51d0John Levon	sval_t val;
679efe51d0John Levon
680efe51d0John Levon	if (handle_known_binop(expr, &val)) {
681efe51d0John Levon		*res_sval = val;
682efe51d0John Levon		return true;
683efe51d0John Levon	}
684efe51d0John Levon	if (implied == RL_EXACT)
685efe51d0John Levon		return false;
686efe51d0John Levon
687efe51d0John Levon	if (custom_handle_variable) {
688efe51d0John Levon		rl = custom_handle_variable(expr);
689efe51d0John Levon		if (rl) {
690efe51d0John Levon			*res = rl;
691efe51d0John Levon			return true;
692efe51d0John Levon		}
693efe51d0John Levon	}
694efe51d0John Levon
695efe51d0John Levon	state = get_extra_state(expr);
696efe51d0John Levon	if (state && !is_whole_rl(estate_rl(state))) {
697efe51d0John Levon		if (implied != RL_HARD || estate_has_hard_max(state)) {
698efe51d0John Levon			*res = clone_rl(estate_rl(state));
699efe51d0John Levon			return true;
700efe51d0John Levon		}
701efe51d0John Levon	}
702efe51d0John Levon
703efe51d0John Levon	return handle_binop_rl_helper(expr, implied, recurse_cnt, res, res_sval);
7041f5207bJohn Levon}
7051f5207bJohn Levon
7061f5207bJohn Levonstatic int do_comparison(struct expression *expr)
7071f5207bJohn Levon{
7081f5207bJohn Levon	struct range_list *left_ranges = NULL;
7091f5207bJohn Levon	struct range_list *right_ranges = NULL;
7101f5207bJohn Levon	int poss_true, poss_false;
7111f5207bJohn Levon	struct symbol *type;
7121f5207bJohn Levon
7131f5207bJohn Levon	type = get_type(expr);
7141f5207bJohn Levon	get_absolute_rl(expr->left, &left_ranges);
7151f5207bJohn Levon	get_absolute_rl(expr->right, &right_ranges);
7161f5207bJohn Levon
7171f5207bJohn Levon	left_ranges = cast_rl(type, left_ranges);
7181f5207bJohn Levon	right_ranges = cast_rl(type, right_ranges);
7191f5207bJohn Levon
7201f5207bJohn Levon	poss_true = possibly_true_rl(left_ranges, expr->op, right_ranges);
7211f5207bJohn Levon	poss_false = possibly_false_rl(left_ranges, expr->op, right_ranges);
7221f5207bJohn Levon
7231f5207bJohn Levon	if (!poss_true && !poss_false)
7241f5207bJohn Levon		return 0x0;
7251f5207bJohn Levon	if (poss_true && !poss_false)
7261f5207bJohn Levon		return 0x1;
7271f5207bJohn Levon	if (!poss_true && poss_false)
7281f5207bJohn Levon		return 0x2;
7291f5207bJohn Levon	return 0x3;
7301f5207bJohn Levon}
7311f5207bJohn Levon
732efe51d0John Levonstatic bool handle_comparison_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
7331f5207bJohn Levon{
7341f5207bJohn Levon	sval_t left, right;
735efe51d0John Levon	int cmp;
7361f5207bJohn Levon
7371f5207bJohn Levon	if (expr->op == SPECIAL_EQUAL && expr->left->type == EXPR_TYPE) {
7381f5207bJohn Levon		struct symbol *left, *right;
7391f5207bJohn Levon
740efe51d0John Levon		if (expr->right->type != EXPR_TYPE)
741efe51d0John Levon			return false;
742efe51d0John Levon
7431f5207bJohn Levon		left = get_real_base_type(expr->left->symbol);
744efe51d0John Levon		right = get_real_base_type(expr->right->symbol);
745efe51d0John Levon		if (type_bits(left) == type_bits(right) &&
746efe51d0John Levon		    type_positive_bits(left) == type_positive_bits(right))
747efe51d0John Levon			*res_sval = one;
748efe51d0John Levon		else
749efe51d0John Levon			*res_sval = zero;
750efe51d0John Levon		return true;
7511f5207bJohn Levon	}
7521f5207bJohn Levon
7531f5207bJohn Levon	if (get_value(expr->left, &left) && get_value(expr->right, &right)) {
7541f5207bJohn Levon		struct data_range tmp_left, tmp_right;
7551f5207bJohn Levon
7561f5207bJohn Levon		tmp_left.min = left;
7571f5207bJohn Levon		tmp_left.max = left;
7581f5207bJohn Levon		tmp_right.min = right;
7591f5207bJohn Levon		tmp_right.max = right;
7601f5207bJohn Levon		if (true_comparison_range(&tmp_left, expr->op, &tmp_right))
761efe51d0John Levon			*res_sval = one;
762efe51d0John Levon		else
763efe51d0John Levon			*res_sval = zero;
764efe51d0John Levon		return true;
7651f5207bJohn Levon	}
7661f5207bJohn Levon
7671f5207bJohn Levon	if (implied == RL_EXACT)
768efe51d0John Levon		return false;
7691f5207bJohn Levon
770efe51d0John Levon	cmp = do_comparison(expr);
771efe51d0John Levon	if (cmp == 1) {
772efe51d0John Levon		*res_sval = one;
773efe51d0John Levon		return true;
774efe51d0John Levon	}
775efe51d0John Levon	if (cmp == 2) {
776efe51d0John Levon		*res_sval = zero;
777efe51d0John Levon		return true;
778efe51d0John Levon	}
7791f5207bJohn Levon
780efe51d0John Levon	*res = alloc_rl(zero, one);
781efe51d0John Levon	return true;
7821f5207bJohn Levon}
7831f5207bJohn Levon
784efe51d0John Levonstatic bool handle_logical_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
7851f5207bJohn Levon{
7861f5207bJohn Levon	sval_t left, right;
7871f5207bJohn Levon	int left_known = 0;
7881f5207bJohn Levon	int right_known = 0;
7891f5207bJohn Levon
7901f5207bJohn Levon	if (implied == RL_EXACT) {
7911f5207bJohn Levon		if (get_value(expr->left, &left))
7921f5207bJohn Levon			left_known = 1;
7931f5207bJohn Levon		if (get_value(expr->right, &right))
7941f5207bJohn Levon			right_known = 1;
7951f5207bJohn Levon	} else {
796efe51d0John Levon		if (get_implied_value_internal(expr->left, recurse_cnt, &left))
7971f5207bJohn Levon			left_known = 1;
798efe51d0John Levon		if (get_implied_value_internal(expr->right, recurse_cnt, &right))
7991f5207bJohn Levon			right_known = 1;
8001f5207bJohn Levon	}
8011f5207bJohn Levon
8021f5207bJohn Levon	switch (expr->op) {
8031f5207bJohn Levon	case SPECIAL_LOGICAL_OR:
8041f5207bJohn Levon		if (left_known && left.value)
805efe51d0John Levon			goto one;
8061f5207bJohn Levon		if (right_known && right.value)
807efe51d0John Levon			goto one;
8081f5207bJohn Levon		if (left_known && right_known)
809efe51d0John Levon			goto zero;
8101f5207bJohn Levon		break;
8111f5207bJohn Levon	case SPECIAL_LOGICAL_AND:
8121f5207bJohn Levon		if (left_known && right_known) {
8131f5207bJohn Levon			if (left.value && right.value)
814efe51d0John Levon				goto one;
815efe51d0John Levon			goto zero;
8161f5207bJohn Levon		}
8171f5207bJohn Levon		break;
8181f5207bJohn Levon	default:
819efe51d0John Levon		return false;
8201f5207bJohn Levon	}
8211f5207bJohn Levon
8221f5207bJohn Levon	if (implied == RL_EXACT)
823efe51d0John Levon		return false;
8241f5207bJohn Levon
825efe51d0John Levon	*res = alloc_rl(zero, one);
826efe51d0John Levon	return true;
827efe51d0John Levon
828efe51d0John Levonzero:
829efe51d0John Levon	*res_sval = zero;
830efe51d0John Levon	return true;
831efe51d0John Levonone:
832efe51d0John Levon	*res_sval = one;
833efe51d0John Levon	return true;
8341f5207bJohn Levon}
8351f5207bJohn Levon
836efe51d0John Levonstatic bool handle_conditional_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
8371f5207bJohn Levon{
8381f5207bJohn Levon	struct expression *cond_true;
8391f5207bJohn Levon	struct range_list *true_rl, *false_rl;
8401f5207bJohn Levon	struct symbol *type;
8411f5207bJohn Levon	int final_pass_orig = final_pass;
8421f5207bJohn Levon
8431f5207bJohn Levon	cond_true = expr->cond_true;
8441f5207bJohn Levon	if (!cond_true)
8451f5207bJohn Levon		cond_true = expr->conditional;
8461f5207bJohn Levon
8471f5207bJohn Levon	if (known_condition_true(expr->conditional))
848efe51d0John Levon		return get_rl_sval(cond_true, implied, recurse_cnt, res, res_sval);
8491f5207bJohn Levon	if (known_condition_false(expr->conditional))
850efe51d0John Levon		return get_rl_sval(expr->cond_false, implied, recurse_cnt, res, res_sval);
8511f5207bJohn Levon
8521f5207bJohn Levon	if (implied == RL_EXACT)
853efe51d0John Levon		return false;
8541f5207bJohn Levon
8551f5207bJohn Levon	if (implied_condition_true(expr->conditional))
856efe51d0John Levon		return get_rl_sval(cond_true, implied, recurse_cnt, res, res_sval);
8571f5207bJohn Levon	if (implied_condition_false(expr->conditional))
858efe51d0John Levon		return get_rl_sval(expr->cond_false, implied, recurse_cnt, res, res_sval);
8591f5207bJohn Levon
8601f5207bJohn Levon	/* this becomes a problem with deeply nested conditional statements */
861c85f09cJohn Levon	if (fast_math_only || low_on_memory())
862efe51d0John Levon		return false;
8631f5207bJohn Levon
8641f5207bJohn Levon	type = get_type(expr);
8651f5207bJohn Levon
8661f5207bJohn Levon	__push_fake_cur_stree();
8671f5207bJohn Levon	final_pass = 0;
8681f5207bJohn Levon	__split_whole_condition(expr->conditional);
869efe51d0John Levon	true_rl = NULL;
870efe51d0John Levon	get_rl_internal(cond_true, implied, recurse_cnt, &true_rl);
8711f5207bJohn Levon	__push_true_states();
8721f5207bJohn Levon	__use_false_states();
873efe51d0John Levon	false_rl = NULL;
874efe51d0John Levon	get_rl_internal(expr->cond_false, implied, recurse_cnt, &false_rl);
8751f5207bJohn Levon	__merge_true_states();
8761f5207bJohn Levon	__free_fake_cur_stree();
8771f5207bJohn Levon	final_pass = final_pass_orig;
8781f5207bJohn Levon
8791f5207bJohn Levon	if (!true_rl || !false_rl)
880efe51d0John Levon		return false;
8811f5207bJohn Levon	true_rl = cast_rl(type, true_rl);
8821f5207bJohn Levon	false_rl = cast_rl(type, false_rl);
8831f5207bJohn Levon
884efe51d0John Levon	*res = rl_union(true_rl, false_rl);
885efe51d0John Levon	return true;
8861f5207bJohn Levon}
8871f5207bJohn Levon
888efe51d0John Levonstatic bool get_fuzzy_max_helper(struct expression *expr, sval_t *max)
8891f5207bJohn Levon{
8901f5207bJohn Levon	struct smatch_state *state;
8911f5207bJohn Levon	sval_t sval;
8921f5207bJohn Levon
8931f5207bJohn Levon	if (get_hard_max(expr, &sval)) {
8941f5207bJohn Levon		*max = sval;
895efe51d0John Levon		return true;
8961f5207bJohn Levon	}
8971f5207bJohn Levon
8981f5207bJohn Levon	state = get_extra_state(expr);
8991f5207bJohn Levon	if (!state || !estate_has_fuzzy_max(state))
900efe51d0John Levon		return false;
9011f5207bJohn Levon	*max = sval_cast(get_type(expr), estate_get_fuzzy_max(state));
902efe51d0John Levon	return true;
9031f5207bJohn Levon}
9041f5207bJohn Levon
905efe51d0John Levonstatic bool get_fuzzy_min_helper(struct expression *expr, sval_t *min)
9061f5207bJohn Levon{
9071f5207bJohn Levon	struct smatch_state *state;
9081f5207bJohn Levon	sval_t sval;
9091f5207bJohn Levon
9101f5207bJohn Levon	state = get_extra_state(expr);
9111f5207bJohn Levon	if (!state || !estate_rl(state))
912efe51d0John Levon		return false;
9131f5207bJohn Levon
9141f5207bJohn Levon	sval = estate_min(state);
9151f5207bJohn Levon	if (sval_is_negative(sval) && sval_is_min(sval))
916efe51d0John Levon		return false;
9171f5207bJohn Levon
9181f5207bJohn Levon	if (sval_is_max(sval))
919efe51d0John Levon		return false;
9201f5207bJohn Levon
9211f5207bJohn Levon	*min = sval_cast(get_type(expr), sval);
922efe51d0John Levon	return true;
9231f5207bJohn Levon}
9241f5207bJohn Levon
9251f5207bJohn Levonint get_const_value(struct expression *expr, sval_t *sval)
9261f5207bJohn Levon{
9271f5207bJohn Levon	struct symbol *sym;
9281f5207bJohn Levon	sval_t right;
9291f5207bJohn Levon
9301f5207bJohn Levon	if (expr->type != EXPR_SYMBOL || !expr->symbol)
9311f5207bJohn Levon		return 0;
9321f5207bJohn Levon	sym = expr->symbol;
9331f5207bJohn Levon	if (!(sym->ctype.modifiers & MOD_CONST))
9341f5207bJohn Levon		return 0;
9351f5207bJohn Levon	if (get_value(sym->initializer, &right)) {
9361f5207bJohn Levon		*sval = sval_cast(get_type(expr), right);
9371f5207bJohn Levon		return 1;
9381f5207bJohn Levon	}
9391f5207bJohn Levon	return 0;
9401f5207bJohn Levon}
9411f5207bJohn Levon
9421f5207bJohn Levonstruct range_list *var_to_absolute_rl(struct expression *expr)
9431f5207bJohn Levon{
9441f5207bJohn Levon	struct smatch_state *state;
9451f5207bJohn Levon	struct range_list *rl;
9461f5207bJohn Levon
9471f5207bJohn Levon	state = get_extra_state(expr);
9481f5207bJohn Levon	if (!state || is_whole_rl(estate_rl(state))) {
9491f5207bJohn Levon		state = get_real_absolute_state(expr);
9501f5207bJohn Levon		if (state && state->data && !estate_is_whole(state))
9511f5207bJohn Levon			return clone_rl(estate_rl(state));
9521f5207bJohn Levon		if (get_mtag_rl(expr, &rl))
9531f5207bJohn Levon			return rl;
9541f5207bJohn Levon		if (get_db_type_rl(expr, &rl) && !is_whole_rl(rl))
9551f5207bJohn Levon			return rl;
9561f5207bJohn Levon		return alloc_whole_rl(get_type(expr));
9571f5207bJohn Levon	}
9581f5207bJohn Levon	/* err on the side of saying things are possible */
9591f5207bJohn Levon	if (!estate_rl(state))
9601f5207bJohn Levon		return alloc_whole_rl(get_type(expr));
9611f5207bJohn Levon	return clone_rl(estate_rl(state));
9621f5207bJohn Levon}
9631f5207bJohn Levon
964efe51d0John Levonstatic bool handle_variable(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
9651f5207bJohn Levon{
9661f5207bJohn Levon	struct smatch_state *state;
9671f5207bJohn Levon	struct range_list *rl;
9681f5207bJohn Levon	sval_t sval, min, max;
9691f5207bJohn Levon	struct symbol *type;
9701f5207bJohn Levon
971efe51d0John Levon	if (get_const_value(expr, &sval)) {
972efe51d0John Levon		*res_sval = sval;
973efe51d0John Levon		return true;
974efe51d0John Levon	}
975efe51d0John Levon
976efe51d0John Levon	if (implied == RL_EXACT)
977efe51d0John Levon		return false;
9781f5207bJohn Levon
9791f5207bJohn Levon	if (custom_handle_variable) {
9801f5207bJohn Levon		rl = custom_handle_variable(expr);
981efe51d0John Levon		if (rl) {
982efe51d0John Levon			if (!rl_to_sval(rl, res_sval))
983efe51d0John Levon				*res = rl;
984efe51d0John Levon		} else {
985efe51d0John Levon			*res = var_to_absolute_rl(expr);
986efe51d0John Levon		}
987efe51d0John Levon		return true;
9881f5207bJohn Levon	}
9891f5207bJohn Levon
990efe51d0John Levon	if (get_mtag_sval(expr, &sval)) {
991efe51d0John Levon		*res_sval = sval;
992efe51d0John Levon		return true;
993efe51d0John Levon	}
9941f5207bJohn Levon
9951f5207bJohn Levon	type = get_type(expr);
996efe51d0John Levon	if (type &&
997efe51d0John Levon	    (type->type == SYM_ARRAY ||
998efe51d0John Levon	     type->type == SYM_FN))
999efe51d0John Levon		return handle_address(expr, implied, recurse_cnt, res, res_sval);
1000efe51d0John Levon
1001efe51d0John Levon	/* FIXME: call rl_to_sval() on the results */
10021f5207bJohn Levon
10031f5207bJohn Levon	switch (implied) {
10041f5207bJohn Levon	case RL_HARD:
10051f5207bJohn Levon	case RL_IMPLIED:
10061f5207bJohn Levon	case RL_ABSOLUTE:
10071f5207bJohn Levon		state = get_extra_state(expr);
1008efe51d0John Levon		if (!state) {
10091f5207bJohn Levon			if (implied == RL_HARD)
1010efe51d0John Levon				return false;
1011efe51d0John Levon			if (get_mtag_rl(expr, res))
1012efe51d0John Levon				return true;
1013efe51d0John Levon			if (get_db_type_rl(expr, res))
1014efe51d0John Levon				return true;
1015efe51d0John Levon			if (is_array(expr) && get_array_rl(expr, res))
1016efe51d0John Levon				return true;
1017efe51d0John Levon			return false;
10181f5207bJohn Levon		}
10191f5207bJohn Levon		if (implied == RL_HARD && !estate_has_hard_max(state))
1020efe51d0John Levon			return false;
1021efe51d0John Levon		*res = clone_rl(estate_rl(state));
1022efe51d0John Levon		return true;
10231f5207bJohn Levon	case RL_REAL_ABSOLUTE: {
10241f5207bJohn Levon		struct smatch_state *abs_state;
1025