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
23static bool get_rl_sval(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *sval_res);
24static bool get_rl_internal(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res);
25static bool handle_variable(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval);
26static struct range_list *(*custom_handle_variable)(struct expression *expr);
27
28static bool get_implied_value_internal(struct expression *expr, int *recurse_cnt, sval_t *res_sval);
29static int get_absolute_rl_internal(struct expression *expr, struct range_list **rl, int *recurse_cnt);
30
31static sval_t zero  = {.type = &int_ctype, {.value = 0} };
32static sval_t one   = {.type = &int_ctype, {.value = 1} };
33
34static int fast_math_only;
35
36struct 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
45struct 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
55enum {
56	RL_EXACT,
57	RL_HARD,
58	RL_FUZZY,
59	RL_IMPLIED,
60	RL_ABSOLUTE,
61	RL_REAL_ABSOLUTE,
62};
63
64static 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
86static 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
92static 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
126static 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
131static 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
158static 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
173static 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
181static 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
252static 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
272static 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
297static 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
338static 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
431static 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
460static 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
487static 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
508static 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
541static 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
564static 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
576static 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
587static 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
618static 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
674static 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
706static 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
732static 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
784static 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
828zero:
829	*res_sval = zero;
830	return true;
831one:
832	*res_sval = one;
833	return true;
834}
835
836static 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
888static 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
905static 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
925int 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
942struct 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
964static 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
1086static 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
1130static 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
1165static 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
1178static 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
1195static 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
1242static 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
1268static 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
1336static 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
1355static 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
1371static 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
1449out_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
1471static 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
1486static 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
1507struct {
1508	struct expression *expr;
1509	sval_t sval;
1510} cached_results[24];
1511static int cache_idx;
1512
1513void clear_math_cache(void)
1514{
1515	memset(cached_results, 0, sizeof(cached_results));
1516}
1517
1518void set_fast_math_only(void)
1519{
1520	fast_math_only++;
1521}
1522
1523void 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 */
1532static 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 */
1545int 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
1586static 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
1599int 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
1609int 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
1629int 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
1639int 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
1649int 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
1656static 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
1665int 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
1674int 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
1683int 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
1696int 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
1707int 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
1717int 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
1731int 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
1745int 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
1765int 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
1785int 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
1804int 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
1823int 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
1864int 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