11f5207b7SJohn Levon /* 21f5207b7SJohn Levon * Copyright (C) 2010 Dan Carpenter. 31f5207b7SJohn Levon * 41f5207b7SJohn Levon * This program is free software; you can redistribute it and/or 51f5207b7SJohn Levon * modify it under the terms of the GNU General Public License 61f5207b7SJohn Levon * as published by the Free Software Foundation; either version 2 71f5207b7SJohn Levon * of the License, or (at your option) any later version. 81f5207b7SJohn Levon * 91f5207b7SJohn Levon * This program is distributed in the hope that it will be useful, 101f5207b7SJohn Levon * but WITHOUT ANY WARRANTY; without even the implied warranty of 111f5207b7SJohn Levon * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 121f5207b7SJohn Levon * GNU General Public License for more details. 131f5207b7SJohn Levon * 141f5207b7SJohn Levon * You should have received a copy of the GNU General Public License 151f5207b7SJohn Levon * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt 161f5207b7SJohn Levon */ 171f5207b7SJohn Levon 181f5207b7SJohn Levon #include "symbol.h" 191f5207b7SJohn Levon #include "smatch.h" 201f5207b7SJohn Levon #include "smatch_slist.h" 211f5207b7SJohn Levon #include "smatch_extra.h" 221f5207b7SJohn Levon 23efe51d0cSJohn Levon static bool get_rl_sval(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *sval_res); 24efe51d0cSJohn Levon static bool get_rl_internal(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res); 25efe51d0cSJohn Levon static bool handle_variable(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval); 261f5207b7SJohn Levon static struct range_list *(*custom_handle_variable)(struct expression *expr); 271f5207b7SJohn Levon 28efe51d0cSJohn Levon static bool get_implied_value_internal(struct expression *expr, int *recurse_cnt, sval_t *res_sval); 291f5207b7SJohn Levon static int get_absolute_rl_internal(struct expression *expr, struct range_list **rl, int *recurse_cnt); 301f5207b7SJohn Levon 311f5207b7SJohn Levon static sval_t zero = {.type = &int_ctype, {.value = 0} }; 321f5207b7SJohn Levon static sval_t one = {.type = &int_ctype, {.value = 1} }; 331f5207b7SJohn Levon 34*c85f09ccSJohn Levon static int fast_math_only; 35*c85f09ccSJohn Levon 361f5207b7SJohn Levon struct range_list *rl_zero(void) 371f5207b7SJohn Levon { 381f5207b7SJohn Levon static struct range_list *zero_perm; 391f5207b7SJohn Levon 401f5207b7SJohn Levon if (!zero_perm) 411f5207b7SJohn Levon zero_perm = clone_rl_permanent(alloc_rl(zero, zero)); 421f5207b7SJohn Levon return zero_perm; 431f5207b7SJohn Levon } 441f5207b7SJohn Levon 451f5207b7SJohn Levon struct range_list *rl_one(void) 461f5207b7SJohn Levon { 471f5207b7SJohn Levon static struct range_list *one_perm; 481f5207b7SJohn Levon 491f5207b7SJohn Levon if (!one_perm) 501f5207b7SJohn Levon one_perm = clone_rl_permanent(alloc_rl(one, one)); 511f5207b7SJohn Levon 521f5207b7SJohn Levon return one_perm; 531f5207b7SJohn Levon } 541f5207b7SJohn Levon 551f5207b7SJohn Levon enum { 561f5207b7SJohn Levon RL_EXACT, 571f5207b7SJohn Levon RL_HARD, 581f5207b7SJohn Levon RL_FUZZY, 591f5207b7SJohn Levon RL_IMPLIED, 601f5207b7SJohn Levon RL_ABSOLUTE, 611f5207b7SJohn Levon RL_REAL_ABSOLUTE, 621f5207b7SJohn Levon }; 631f5207b7SJohn Levon 64efe51d0cSJohn Levon static bool last_stmt_rl(struct statement *stmt, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval) 651f5207b7SJohn Levon { 661f5207b7SJohn Levon struct expression *expr; 671f5207b7SJohn Levon 681f5207b7SJohn Levon if (!stmt) 69efe51d0cSJohn Levon return false; 701f5207b7SJohn Levon 711f5207b7SJohn Levon stmt = last_ptr_list((struct ptr_list *)stmt->stmts); 721f5207b7SJohn Levon if (stmt->type == STMT_LABEL) { 731f5207b7SJohn Levon if (stmt->label_statement && 741f5207b7SJohn Levon stmt->label_statement->type == STMT_EXPRESSION) 751f5207b7SJohn Levon expr = stmt->label_statement->expression; 761f5207b7SJohn Levon else 77efe51d0cSJohn Levon return false; 781f5207b7SJohn Levon } else if (stmt->type == STMT_EXPRESSION) { 791f5207b7SJohn Levon expr = stmt->expression; 801f5207b7SJohn Levon } else { 81efe51d0cSJohn Levon return false; 821f5207b7SJohn Levon } 83efe51d0cSJohn Levon return get_rl_sval(expr, implied, recurse_cnt, res, res_sval); 841f5207b7SJohn Levon } 851f5207b7SJohn Levon 86efe51d0cSJohn Levon static bool handle_expression_statement_rl(struct expression *expr, int implied, 87efe51d0cSJohn Levon int *recurse_cnt, struct range_list **res, sval_t *res_sval) 881f5207b7SJohn Levon { 89efe51d0cSJohn Levon return last_stmt_rl(get_expression_statement(expr), implied, recurse_cnt, res, res_sval); 901f5207b7SJohn Levon } 911f5207b7SJohn Levon 92efe51d0cSJohn Levon static bool handle_address(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval) 931f5207b7SJohn Levon { 941f5207b7SJohn Levon struct range_list *rl; 95efe51d0cSJohn Levon static int recursed; 961f5207b7SJohn Levon sval_t sval; 971f5207b7SJohn Levon 98efe51d0cSJohn Levon if (recursed > 10) 99efe51d0cSJohn Levon return false; 100efe51d0cSJohn Levon if (implied == RL_EXACT) 101efe51d0cSJohn Levon return false; 102efe51d0cSJohn Levon 103efe51d0cSJohn Levon if (custom_handle_variable) { 104efe51d0cSJohn Levon rl = custom_handle_variable(expr); 105efe51d0cSJohn Levon if (rl) { 106efe51d0cSJohn Levon *res = rl; 107efe51d0cSJohn Levon return true; 108efe51d0cSJohn Levon } 109efe51d0cSJohn Levon } 110efe51d0cSJohn Levon 111efe51d0cSJohn Levon recursed++; 112efe51d0cSJohn Levon if (get_mtag_sval(expr, &sval)) { 113efe51d0cSJohn Levon recursed--; 114efe51d0cSJohn Levon *res_sval = sval; 115efe51d0cSJohn Levon return true; 116efe51d0cSJohn Levon } 117efe51d0cSJohn Levon 118efe51d0cSJohn Levon if (get_address_rl(expr, res)) { 119efe51d0cSJohn Levon recursed--; 120efe51d0cSJohn Levon return true; 121efe51d0cSJohn Levon } 122efe51d0cSJohn Levon recursed--; 123efe51d0cSJohn Levon return 0; 124efe51d0cSJohn Levon } 125efe51d0cSJohn Levon 126efe51d0cSJohn Levon static bool handle_ampersand_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval) 127efe51d0cSJohn Levon { 128efe51d0cSJohn Levon return handle_address(expr, implied, recurse_cnt, res, res_sval); 1291f5207b7SJohn Levon } 1301f5207b7SJohn Levon 131efe51d0cSJohn Levon static bool handle_negate_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval) 1321f5207b7SJohn Levon { 133efe51d0cSJohn Levon if (known_condition_true(expr->unop)) { 134efe51d0cSJohn Levon *res_sval = zero; 135efe51d0cSJohn Levon return true; 136efe51d0cSJohn Levon } 137efe51d0cSJohn Levon if (known_condition_false(expr->unop)) { 138efe51d0cSJohn Levon *res_sval = one; 139efe51d0cSJohn Levon return true; 140efe51d0cSJohn Levon } 1411f5207b7SJohn Levon 1421f5207b7SJohn Levon if (implied == RL_EXACT) 143efe51d0cSJohn Levon return false; 1441f5207b7SJohn Levon 145efe51d0cSJohn Levon if (implied_condition_true(expr->unop)) { 146efe51d0cSJohn Levon *res_sval = zero; 147efe51d0cSJohn Levon return true; 148efe51d0cSJohn Levon } 149efe51d0cSJohn Levon if (implied_condition_false(expr->unop)) { 150efe51d0cSJohn Levon *res_sval = one; 151efe51d0cSJohn Levon return true; 152efe51d0cSJohn Levon } 153efe51d0cSJohn Levon 154efe51d0cSJohn Levon *res = alloc_rl(zero, one); 155efe51d0cSJohn Levon return true; 1561f5207b7SJohn Levon } 1571f5207b7SJohn Levon 158efe51d0cSJohn Levon static bool handle_bitwise_negate(struct expression *expr, int implied, int *recurse_cnt, sval_t *res_sval) 1591f5207b7SJohn Levon { 1601f5207b7SJohn Levon struct range_list *rl; 161efe51d0cSJohn Levon sval_t sval = {}; 1621f5207b7SJohn Levon 163efe51d0cSJohn Levon if (!get_rl_sval(expr->unop, implied, recurse_cnt, &rl, &sval)) 164efe51d0cSJohn Levon return false; 165efe51d0cSJohn Levon if (!sval.type && !rl_to_sval(rl, &sval)) 166efe51d0cSJohn Levon return false; 1671f5207b7SJohn Levon sval = sval_preop(sval, '~'); 1681f5207b7SJohn Levon sval_cast(get_type(expr->unop), sval); 169efe51d0cSJohn Levon *res_sval = sval; 170efe51d0cSJohn Levon return true; 1711f5207b7SJohn Levon } 1721f5207b7SJohn Levon 173efe51d0cSJohn Levon static bool untrusted_type_min(struct expression *expr) 1741f5207b7SJohn Levon { 1751f5207b7SJohn Levon struct range_list *rl; 1761f5207b7SJohn Levon 177efe51d0cSJohn Levon rl = var_user_rl(expr); 178efe51d0cSJohn Levon return rl && sval_is_min(rl_min(rl)); 1791f5207b7SJohn Levon } 1801f5207b7SJohn Levon 181efe51d0cSJohn Levon static bool handle_minus_preop(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval) 182efe51d0cSJohn Levon { 183efe51d0cSJohn Levon struct range_list *rl; 184efe51d0cSJohn Levon struct range_list *ret = NULL; 185efe51d0cSJohn Levon struct symbol *type; 186efe51d0cSJohn Levon sval_t neg_one = { 0 }; 187efe51d0cSJohn Levon sval_t zero = { 0 }; 188efe51d0cSJohn Levon sval_t sval = {}; 189efe51d0cSJohn Levon 190efe51d0cSJohn Levon neg_one.value = -1; 191efe51d0cSJohn Levon zero.value = 0; 192efe51d0cSJohn Levon 193efe51d0cSJohn Levon if (!get_rl_sval(expr->unop, implied, recurse_cnt, &rl, &sval)) 194efe51d0cSJohn Levon return false; 195efe51d0cSJohn Levon if (sval.type) { 196efe51d0cSJohn Levon *res_sval = sval_preop(sval, '-'); 197efe51d0cSJohn Levon return true; 198efe51d0cSJohn Levon } 199efe51d0cSJohn Levon /* 200efe51d0cSJohn Levon * One complication is that -INT_MIN is still INT_MIN because of integer 201efe51d0cSJohn Levon * overflows... But how many times do we set a time out to INT_MIN? 202efe51d0cSJohn Levon * So normally when we call abs() then it does return a positive value. 203efe51d0cSJohn Levon * 204efe51d0cSJohn Levon */ 205efe51d0cSJohn Levon type = rl_type(rl); 206efe51d0cSJohn Levon neg_one.type = zero.type = type; 207efe51d0cSJohn Levon 208efe51d0cSJohn Levon if (sval_is_negative(rl_min(rl))) { 209efe51d0cSJohn Levon struct range_list *neg; 210efe51d0cSJohn Levon struct data_range *drange; 211efe51d0cSJohn Levon sval_t new_min, new_max; 212efe51d0cSJohn Levon 213efe51d0cSJohn Levon neg = alloc_rl(sval_type_min(type), neg_one); 214efe51d0cSJohn Levon neg = rl_intersection(rl, neg); 215efe51d0cSJohn Levon 216efe51d0cSJohn Levon if (sval_is_min(rl_min(neg)) && !sval_is_min(rl_max(neg))) 217efe51d0cSJohn Levon neg = remove_range(neg, sval_type_min(type), sval_type_min(type)); 218efe51d0cSJohn Levon 219efe51d0cSJohn Levon FOR_EACH_PTR(neg, drange) { 220efe51d0cSJohn Levon new_min = drange->max; 221efe51d0cSJohn Levon new_min.value = -new_min.value; 222efe51d0cSJohn Levon new_max = drange->min; 223efe51d0cSJohn Levon new_max.value = -new_max.value; 224efe51d0cSJohn Levon add_range(&ret, new_min, new_max); 225efe51d0cSJohn Levon } END_FOR_EACH_PTR(drange); 226efe51d0cSJohn Levon 227efe51d0cSJohn Levon if (untrusted_type_min(expr)) 228efe51d0cSJohn Levon add_range(&ret, sval_type_min(type), sval_type_min(type)); 229efe51d0cSJohn Levon } 230efe51d0cSJohn Levon 231efe51d0cSJohn Levon if (!sval_is_negative(rl_max(rl))) { 232efe51d0cSJohn Levon struct range_list *pos; 233efe51d0cSJohn Levon struct data_range *drange; 234efe51d0cSJohn Levon sval_t new_min, new_max; 235efe51d0cSJohn Levon 236efe51d0cSJohn Levon pos = alloc_rl(zero, sval_type_max(type)); 237efe51d0cSJohn Levon pos = rl_intersection(rl, pos); 238efe51d0cSJohn Levon 239efe51d0cSJohn Levon FOR_EACH_PTR(pos, drange) { 240efe51d0cSJohn Levon new_min = drange->max; 241efe51d0cSJohn Levon new_min.value = -new_min.value; 242efe51d0cSJohn Levon new_max = drange->min; 243efe51d0cSJohn Levon new_max.value = -new_max.value; 244efe51d0cSJohn Levon add_range(&ret, new_min, new_max); 245efe51d0cSJohn Levon } END_FOR_EACH_PTR(drange); 246efe51d0cSJohn Levon } 247efe51d0cSJohn Levon 248efe51d0cSJohn Levon *res = ret; 249efe51d0cSJohn Levon return true; 250efe51d0cSJohn Levon } 251efe51d0cSJohn Levon 252efe51d0cSJohn Levon static bool handle_preop_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval) 2531f5207b7SJohn Levon { 2541f5207b7SJohn Levon switch (expr->op) { 2551f5207b7SJohn Levon case '&': 256efe51d0cSJohn Levon return handle_ampersand_rl(expr, implied, recurse_cnt, res, res_sval); 2571f5207b7SJohn Levon case '!': 258efe51d0cSJohn Levon return handle_negate_rl(expr, implied, recurse_cnt, res, res_sval); 2591f5207b7SJohn Levon case '~': 260efe51d0cSJohn Levon return handle_bitwise_negate(expr, implied, recurse_cnt, res_sval); 2611f5207b7SJohn Levon case '-': 262efe51d0cSJohn Levon return handle_minus_preop(expr, implied, recurse_cnt, res, res_sval); 2631f5207b7SJohn Levon case '*': 264efe51d0cSJohn Levon return handle_variable(expr, implied, recurse_cnt, res, res_sval); 2651f5207b7SJohn Levon case '(': 266efe51d0cSJohn Levon return handle_expression_statement_rl(expr, implied, recurse_cnt, res, res_sval); 2671f5207b7SJohn Levon default: 268efe51d0cSJohn Levon return false; 2691f5207b7SJohn Levon } 2701f5207b7SJohn Levon } 2711f5207b7SJohn Levon 272efe51d0cSJohn Levon static bool handle_divide_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res) 2731f5207b7SJohn Levon { 274efe51d0cSJohn Levon struct range_list *left_rl = NULL; 275efe51d0cSJohn Levon struct range_list *right_rl = NULL; 2761f5207b7SJohn Levon struct symbol *type; 2771f5207b7SJohn Levon 2781f5207b7SJohn Levon type = get_type(expr); 2791f5207b7SJohn Levon 280efe51d0cSJohn Levon get_rl_internal(expr->left, implied, recurse_cnt, &left_rl); 2811f5207b7SJohn Levon left_rl = cast_rl(type, left_rl); 282efe51d0cSJohn Levon get_rl_internal(expr->right, implied, recurse_cnt, &right_rl); 2831f5207b7SJohn Levon right_rl = cast_rl(type, right_rl); 2841f5207b7SJohn Levon 2851f5207b7SJohn Levon if (!left_rl || !right_rl) 286efe51d0cSJohn Levon return false; 2871f5207b7SJohn Levon 2881f5207b7SJohn Levon if (implied != RL_REAL_ABSOLUTE) { 2891f5207b7SJohn Levon if (is_whole_rl(left_rl) || is_whole_rl(right_rl)) 290efe51d0cSJohn Levon return false; 2911f5207b7SJohn Levon } 2921f5207b7SJohn Levon 293efe51d0cSJohn Levon *res = rl_binop(left_rl, '/', right_rl); 294efe51d0cSJohn Levon return true; 2951f5207b7SJohn Levon } 2961f5207b7SJohn Levon 2971f5207b7SJohn Levon static int handle_offset_subtraction(struct expression *expr) 2981f5207b7SJohn Levon { 2991f5207b7SJohn Levon struct expression *left, *right; 3001f5207b7SJohn Levon struct symbol *left_sym, *right_sym; 3011f5207b7SJohn Levon struct symbol *type; 3021f5207b7SJohn Levon int left_offset, right_offset; 3031f5207b7SJohn Levon 3041f5207b7SJohn Levon type = get_type(expr); 3051f5207b7SJohn Levon if (!type || type->type != SYM_PTR) 3061f5207b7SJohn Levon return -1; 3071f5207b7SJohn Levon type = get_real_base_type(type); 3081f5207b7SJohn Levon if (!type || (type_bits(type) != 8 && (type != &void_ctype))) 3091f5207b7SJohn Levon return -1; 3101f5207b7SJohn Levon 3111f5207b7SJohn Levon left = strip_expr(expr->left); 3121f5207b7SJohn Levon right = strip_expr(expr->right); 3131f5207b7SJohn Levon 3141f5207b7SJohn Levon if (left->type != EXPR_PREOP || left->op != '&') 3151f5207b7SJohn Levon return -1; 3161f5207b7SJohn Levon left = strip_expr(left->unop); 3171f5207b7SJohn Levon 3181f5207b7SJohn Levon left_sym = expr_to_sym(left); 3191f5207b7SJohn Levon right_sym = expr_to_sym(right); 3201f5207b7SJohn Levon if (!left_sym || left_sym != right_sym) 3211f5207b7SJohn Levon return -1; 3221f5207b7SJohn Levon 3231f5207b7SJohn Levon left_offset = get_member_offset_from_deref(left); 3241f5207b7SJohn Levon if (right->type == EXPR_SYMBOL) 3251f5207b7SJohn Levon right_offset = 0; 3261f5207b7SJohn Levon else { 3271f5207b7SJohn Levon if (right->type != EXPR_PREOP || right->op != '&') 3281f5207b7SJohn Levon return -1; 3291f5207b7SJohn Levon right = strip_expr(right->unop); 3301f5207b7SJohn Levon right_offset = get_member_offset_from_deref(right); 3311f5207b7SJohn Levon } 3321f5207b7SJohn Levon if (left_offset < 0 || right_offset < 0) 3331f5207b7SJohn Levon return -1; 3341f5207b7SJohn Levon 3351f5207b7SJohn Levon return left_offset - right_offset; 3361f5207b7SJohn Levon } 3371f5207b7SJohn Levon 338efe51d0cSJohn Levon static bool handle_subtract_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res) 3391f5207b7SJohn Levon { 3401f5207b7SJohn Levon struct symbol *type; 3411f5207b7SJohn Levon struct range_list *left_orig, *right_orig; 3421f5207b7SJohn Levon struct range_list *left_rl, *right_rl; 343efe51d0cSJohn Levon sval_t min, max, tmp; 3441f5207b7SJohn Levon int comparison; 3451f5207b7SJohn Levon int offset; 3461f5207b7SJohn Levon 3471f5207b7SJohn Levon type = get_type(expr); 3481f5207b7SJohn Levon 3491f5207b7SJohn Levon offset = handle_offset_subtraction(expr); 3501f5207b7SJohn Levon if (offset >= 0) { 3511f5207b7SJohn Levon tmp.type = type; 3521f5207b7SJohn Levon tmp.value = offset; 3531f5207b7SJohn Levon 354efe51d0cSJohn Levon *res = alloc_rl(tmp, tmp); 355efe51d0cSJohn Levon return true; 3561f5207b7SJohn Levon } 3571f5207b7SJohn Levon 3581f5207b7SJohn Levon comparison = get_comparison(expr->left, expr->right); 3591f5207b7SJohn Levon 360efe51d0cSJohn Levon left_orig = NULL; 361efe51d0cSJohn Levon get_rl_internal(expr->left, implied, recurse_cnt, &left_orig); 3621f5207b7SJohn Levon left_rl = cast_rl(type, left_orig); 363efe51d0cSJohn Levon right_orig = NULL; 364efe51d0cSJohn Levon get_rl_internal(expr->right, implied, recurse_cnt, &right_orig); 3651f5207b7SJohn Levon right_rl = cast_rl(type, right_orig); 3661f5207b7SJohn Levon 3671f5207b7SJohn Levon if ((!left_rl || !right_rl) && 3681f5207b7SJohn Levon (implied == RL_EXACT || implied == RL_HARD || implied == RL_FUZZY)) 369efe51d0cSJohn Levon return false; 3701f5207b7SJohn Levon 3711f5207b7SJohn Levon if (!left_rl) 3721f5207b7SJohn Levon left_rl = alloc_whole_rl(type); 3731f5207b7SJohn Levon if (!right_rl) 3741f5207b7SJohn Levon right_rl = alloc_whole_rl(type); 3751f5207b7SJohn Levon 3761f5207b7SJohn Levon /* negative values complicate everything fix this later */ 3771f5207b7SJohn Levon if (sval_is_negative(rl_min(right_rl))) 378efe51d0cSJohn Levon return false; 3791f5207b7SJohn Levon max = rl_max(left_rl); 3801f5207b7SJohn Levon min = sval_type_min(type); 3811f5207b7SJohn Levon 3821f5207b7SJohn Levon switch (comparison) { 3831f5207b7SJohn Levon case '>': 3841f5207b7SJohn Levon case SPECIAL_UNSIGNED_GT: 3851f5207b7SJohn Levon min = sval_type_val(type, 1); 3861f5207b7SJohn Levon max = rl_max(left_rl); 3871f5207b7SJohn Levon break; 3881f5207b7SJohn Levon case SPECIAL_GTE: 3891f5207b7SJohn Levon case SPECIAL_UNSIGNED_GTE: 3901f5207b7SJohn Levon min = sval_type_val(type, 0); 3911f5207b7SJohn Levon max = rl_max(left_rl); 3921f5207b7SJohn Levon break; 3931f5207b7SJohn Levon case SPECIAL_EQUAL: 3941f5207b7SJohn Levon min = sval_type_val(type, 0); 3951f5207b7SJohn Levon max = sval_type_val(type, 0); 3961f5207b7SJohn Levon break; 3971f5207b7SJohn Levon case '<': 3981f5207b7SJohn Levon case SPECIAL_UNSIGNED_LT: 3991f5207b7SJohn Levon max = sval_type_val(type, -1); 4001f5207b7SJohn Levon break; 4011f5207b7SJohn Levon case SPECIAL_LTE: 4021f5207b7SJohn Levon case SPECIAL_UNSIGNED_LTE: 4031f5207b7SJohn Levon max = sval_type_val(type, 0); 4041f5207b7SJohn Levon break; 4051f5207b7SJohn Levon default: 4061f5207b7SJohn Levon if (!left_orig || !right_orig) 407efe51d0cSJohn Levon return false; 408efe51d0cSJohn Levon *res = rl_binop(left_rl, '-', right_rl); 409efe51d0cSJohn Levon return true; 4101f5207b7SJohn Levon } 4111f5207b7SJohn Levon 4121f5207b7SJohn Levon if (!sval_binop_overflows(rl_min(left_rl), '-', rl_max(right_rl))) { 4131f5207b7SJohn Levon tmp = sval_binop(rl_min(left_rl), '-', rl_max(right_rl)); 4141f5207b7SJohn Levon if (sval_cmp(tmp, min) > 0) 4151f5207b7SJohn Levon min = tmp; 4161f5207b7SJohn Levon } 4171f5207b7SJohn Levon 4181f5207b7SJohn Levon if (!sval_is_max(rl_max(left_rl))) { 4191f5207b7SJohn Levon tmp = sval_binop(rl_max(left_rl), '-', rl_min(right_rl)); 4201f5207b7SJohn Levon if (sval_cmp(tmp, max) < 0) 4211f5207b7SJohn Levon max = tmp; 4221f5207b7SJohn Levon } 4231f5207b7SJohn Levon 4241f5207b7SJohn Levon if (sval_is_min(min) && sval_is_max(max)) 425efe51d0cSJohn Levon return false; 4261f5207b7SJohn Levon 427efe51d0cSJohn Levon *res = cast_rl(type, alloc_rl(min, max)); 428efe51d0cSJohn Levon return true; 4291f5207b7SJohn Levon } 4301f5207b7SJohn Levon 431efe51d0cSJohn Levon static bool handle_mod_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res) 4321f5207b7SJohn Levon { 4331f5207b7SJohn Levon struct range_list *rl; 4341f5207b7SJohn Levon sval_t left, right, sval; 4351f5207b7SJohn Levon 4361f5207b7SJohn Levon if (implied == RL_EXACT) { 4371f5207b7SJohn Levon if (!get_implied_value(expr->right, &right)) 438efe51d0cSJohn Levon return false; 4391f5207b7SJohn Levon if (!get_implied_value(expr->left, &left)) 440efe51d0cSJohn Levon return false; 4411f5207b7SJohn Levon sval = sval_binop(left, '%', right); 442efe51d0cSJohn Levon *res = alloc_rl(sval, sval); 443efe51d0cSJohn Levon return true; 4441f5207b7SJohn Levon } 4451f5207b7SJohn Levon /* if we can't figure out the right side it's probably hopeless */ 446efe51d0cSJohn Levon if (!get_implied_value_internal(expr->right, recurse_cnt, &right)) 447efe51d0cSJohn Levon return false; 4481f5207b7SJohn Levon 4491f5207b7SJohn Levon right = sval_cast(get_type(expr), right); 4501f5207b7SJohn Levon right.value--; 4511f5207b7SJohn Levon 452efe51d0cSJohn Levon if (get_rl_internal(expr->left, implied, recurse_cnt, &rl) && rl && 453efe51d0cSJohn Levon rl_max(rl).uvalue < right.uvalue) 4541f5207b7SJohn Levon right.uvalue = rl_max(rl).uvalue; 4551f5207b7SJohn Levon 456efe51d0cSJohn Levon *res = alloc_rl(sval_cast(right.type, zero), right); 457efe51d0cSJohn Levon return true; 4581f5207b7SJohn Levon } 4591f5207b7SJohn Levon 460efe51d0cSJohn Levon static bool handle_bitwise_AND(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res) 4611f5207b7SJohn Levon { 4621f5207b7SJohn Levon struct symbol *type; 4631f5207b7SJohn Levon struct range_list *left_rl, *right_rl; 4641f5207b7SJohn Levon int new_recurse; 4651f5207b7SJohn Levon 4661f5207b7SJohn Levon if (implied != RL_IMPLIED && implied != RL_ABSOLUTE && implied != RL_REAL_ABSOLUTE) 467efe51d0cSJohn Levon return false; 4681f5207b7SJohn Levon 4691f5207b7SJohn Levon type = get_type(expr); 4701f5207b7SJohn Levon 471efe51d0cSJohn Levon if (!get_rl_internal(expr->left, implied, recurse_cnt, &left_rl)) 472efe51d0cSJohn Levon left_rl = alloc_whole_rl(type); 473efe51d0cSJohn Levon left_rl = cast_rl(type, left_rl); 4741f5207b7SJohn Levon 4751f5207b7SJohn Levon new_recurse = *recurse_cnt; 4761f5207b7SJohn Levon if (*recurse_cnt >= 200) 4771f5207b7SJohn Levon new_recurse = 100; /* Let's try super hard to get the mask */ 478efe51d0cSJohn Levon if (!get_rl_internal(expr->right, implied, &new_recurse, &right_rl)) 479efe51d0cSJohn Levon right_rl = alloc_whole_rl(type); 480efe51d0cSJohn Levon right_rl = cast_rl(type, right_rl); 481efe51d0cSJohn Levon *recurse_cnt = new_recurse; 4821f5207b7SJohn Levon 483efe51d0cSJohn Levon *res = rl_binop(left_rl, '&', right_rl); 484efe51d0cSJohn Levon return true; 4851f5207b7SJohn Levon } 4861f5207b7SJohn Levon 487efe51d0cSJohn Levon static bool use_rl_binop(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res) 4881f5207b7SJohn Levon { 4891f5207b7SJohn Levon struct symbol *type; 4901f5207b7SJohn Levon struct range_list *left_rl, *right_rl; 4911f5207b7SJohn Levon 4921f5207b7SJohn Levon if (implied != RL_IMPLIED && implied != RL_ABSOLUTE && implied != RL_REAL_ABSOLUTE) 493efe51d0cSJohn Levon return false; 4941f5207b7SJohn Levon 4951f5207b7SJohn Levon type = get_type(expr); 4961f5207b7SJohn Levon 4971f5207b7SJohn Levon get_absolute_rl_internal(expr->left, &left_rl, recurse_cnt); 4981f5207b7SJohn Levon get_absolute_rl_internal(expr->right, &right_rl, recurse_cnt); 4991f5207b7SJohn Levon left_rl = cast_rl(type, left_rl); 5001f5207b7SJohn Levon right_rl = cast_rl(type, right_rl); 5011f5207b7SJohn Levon if (!left_rl || !right_rl) 502efe51d0cSJohn Levon return false; 5031f5207b7SJohn Levon 504efe51d0cSJohn Levon *res = rl_binop(left_rl, expr->op, right_rl); 505efe51d0cSJohn Levon return true; 5061f5207b7SJohn Levon } 5071f5207b7SJohn Levon 508efe51d0cSJohn Levon static bool handle_right_shift(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res) 5091f5207b7SJohn Levon { 510efe51d0cSJohn Levon struct range_list *left_rl, *right_rl; 5111f5207b7SJohn Levon sval_t min, max; 5121f5207b7SJohn Levon 5131f5207b7SJohn Levon if (implied == RL_EXACT || implied == RL_HARD) 514efe51d0cSJohn Levon return false; 5151f5207b7SJohn Levon 516efe51d0cSJohn Levon if (get_rl_internal(expr->left, implied, recurse_cnt, &left_rl)) { 5171f5207b7SJohn Levon max = rl_max(left_rl); 5181f5207b7SJohn Levon min = rl_min(left_rl); 5191f5207b7SJohn Levon } else { 5201f5207b7SJohn Levon if (implied == RL_FUZZY) 521efe51d0cSJohn Levon return false; 5221f5207b7SJohn Levon max = sval_type_max(get_type(expr->left)); 5231f5207b7SJohn Levon min = sval_type_val(get_type(expr->left), 0); 5241f5207b7SJohn Levon } 5251f5207b7SJohn Levon 526efe51d0cSJohn Levon if (get_rl_internal(expr->right, implied, recurse_cnt, &right_rl) && 527efe51d0cSJohn Levon !sval_is_negative(rl_min(right_rl))) { 528efe51d0cSJohn Levon min = sval_binop(min, SPECIAL_RIGHTSHIFT, rl_max(right_rl)); 529efe51d0cSJohn Levon max = sval_binop(max, SPECIAL_RIGHTSHIFT, rl_min(right_rl)); 5301f5207b7SJohn Levon } else if (!sval_is_negative(min)) { 5311f5207b7SJohn Levon min.value = 0; 5321f5207b7SJohn Levon max = sval_type_max(max.type); 5331f5207b7SJohn Levon } else { 534efe51d0cSJohn Levon return false; 5351f5207b7SJohn Levon } 5361f5207b7SJohn Levon 537efe51d0cSJohn Levon *res = alloc_rl(min, max); 538efe51d0cSJohn Levon return true; 5391f5207b7SJohn Levon } 5401f5207b7SJohn Levon 541efe51d0cSJohn Levon static bool handle_left_shift(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res) 5421f5207b7SJohn Levon { 543efe51d0cSJohn Levon struct range_list *left_rl, *rl; 5441f5207b7SJohn Levon sval_t right; 5451f5207b7SJohn Levon 5461f5207b7SJohn Levon if (implied == RL_EXACT || implied == RL_HARD) 547efe51d0cSJohn Levon return false; 5481f5207b7SJohn Levon /* this is hopeless without the right side */ 549efe51d0cSJohn Levon if (!get_implied_value_internal(expr->right, recurse_cnt, &right)) 550efe51d0cSJohn Levon return false; 551efe51d0cSJohn Levon if (!get_rl_internal(expr->left, implied, recurse_cnt, &left_rl)) { 5521f5207b7SJohn Levon if (implied == RL_FUZZY) 553efe51d0cSJohn Levon return false; 554efe51d0cSJohn Levon left_rl = alloc_whole_rl(get_type(expr->left)); 5551f5207b7SJohn Levon } 5561f5207b7SJohn Levon 557efe51d0cSJohn Levon rl = rl_binop(left_rl, SPECIAL_LEFTSHIFT, alloc_rl(right, right)); 558efe51d0cSJohn Levon if (!rl) 559efe51d0cSJohn Levon return false; 560efe51d0cSJohn Levon *res = rl; 561efe51d0cSJohn Levon return true; 5621f5207b7SJohn Levon } 5631f5207b7SJohn Levon 564efe51d0cSJohn Levon static bool handle_known_binop(struct expression *expr, sval_t *res) 5651f5207b7SJohn Levon { 5661f5207b7SJohn Levon sval_t left, right; 5671f5207b7SJohn Levon 5681f5207b7SJohn Levon if (!get_value(expr->left, &left)) 569efe51d0cSJohn Levon return false; 5701f5207b7SJohn Levon if (!get_value(expr->right, &right)) 571efe51d0cSJohn Levon return false; 572efe51d0cSJohn Levon *res = sval_binop(left, expr->op, right); 573efe51d0cSJohn Levon return true; 5741f5207b7SJohn Levon } 5751f5207b7SJohn Levon 5761f5207b7SJohn Levon static int has_actual_ranges(struct range_list *rl) 5771f5207b7SJohn Levon { 5781f5207b7SJohn Levon struct data_range *tmp; 5791f5207b7SJohn Levon 5801f5207b7SJohn Levon FOR_EACH_PTR(rl, tmp) { 5811f5207b7SJohn Levon if (sval_cmp(tmp->min, tmp->max) != 0) 5821f5207b7SJohn Levon return 1; 5831f5207b7SJohn Levon } END_FOR_EACH_PTR(tmp); 5841f5207b7SJohn Levon return 0; 5851f5207b7SJohn Levon } 5861f5207b7SJohn Levon 5871f5207b7SJohn Levon static struct range_list *handle_implied_binop(struct range_list *left_rl, int op, struct range_list *right_rl) 5881f5207b7SJohn Levon { 5891f5207b7SJohn Levon struct range_list *res_rl; 5901f5207b7SJohn Levon struct data_range *left_drange, *right_drange; 5911f5207b7SJohn Levon sval_t res; 5921f5207b7SJohn Levon 5931f5207b7SJohn Levon if (!left_rl || !right_rl) 5941f5207b7SJohn Levon return NULL; 5951f5207b7SJohn Levon if (has_actual_ranges(left_rl)) 5961f5207b7SJohn Levon return NULL; 5971f5207b7SJohn Levon if (has_actual_ranges(right_rl)) 5981f5207b7SJohn Levon return NULL; 5991f5207b7SJohn Levon 6001f5207b7SJohn Levon if (ptr_list_size((struct ptr_list *)left_rl) * ptr_list_size((struct ptr_list *)right_rl) > 20) 6011f5207b7SJohn Levon return NULL; 6021f5207b7SJohn Levon 6031f5207b7SJohn Levon res_rl = NULL; 6041f5207b7SJohn Levon 6051f5207b7SJohn Levon FOR_EACH_PTR(left_rl, left_drange) { 6061f5207b7SJohn Levon FOR_EACH_PTR(right_rl, right_drange) { 6071f5207b7SJohn Levon if ((op == '%' || op == '/') && 6081f5207b7SJohn Levon right_drange->min.value == 0) 6091f5207b7SJohn Levon return NULL; 6101f5207b7SJohn Levon res = sval_binop(left_drange->min, op, right_drange->min); 6111f5207b7SJohn Levon add_range(&res_rl, res, res); 6121f5207b7SJohn Levon } END_FOR_EACH_PTR(right_drange); 6131f5207b7SJohn Levon } END_FOR_EACH_PTR(left_drange); 6141f5207b7SJohn Levon 6151f5207b7SJohn Levon return res_rl; 6161f5207b7SJohn Levon } 6171f5207b7SJohn Levon 618efe51d0cSJohn Levon static bool handle_binop_rl_helper(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval) 6191f5207b7SJohn Levon { 6201f5207b7SJohn Levon struct symbol *type; 621efe51d0cSJohn Levon struct range_list *left_rl = NULL; 622efe51d0cSJohn Levon struct range_list *right_rl = NULL; 623efe51d0cSJohn Levon struct range_list *rl; 6241f5207b7SJohn Levon sval_t min, max; 6251f5207b7SJohn Levon 626efe51d0cSJohn Levon type = get_promoted_type(get_type(expr->left), get_type(expr->right)); 627efe51d0cSJohn Levon get_rl_internal(expr->left, implied, recurse_cnt, &left_rl); 6281f5207b7SJohn Levon left_rl = cast_rl(type, left_rl); 629efe51d0cSJohn Levon get_rl_internal(expr->right, implied, recurse_cnt, &right_rl); 6301f5207b7SJohn Levon right_rl = cast_rl(type, right_rl); 6311f5207b7SJohn Levon if (!left_rl && !right_rl) 632efe51d0cSJohn Levon return false; 6331f5207b7SJohn Levon 6341f5207b7SJohn Levon rl = handle_implied_binop(left_rl, expr->op, right_rl); 635efe51d0cSJohn Levon if (rl) { 636efe51d0cSJohn Levon *res = rl; 637efe51d0cSJohn Levon return true; 638efe51d0cSJohn Levon } 6391f5207b7SJohn Levon 6401f5207b7SJohn Levon switch (expr->op) { 6411f5207b7SJohn Levon case '%': 642efe51d0cSJohn Levon return handle_mod_rl(expr, implied, recurse_cnt, res); 6431f5207b7SJohn Levon case '&': 644efe51d0cSJohn Levon return handle_bitwise_AND(expr, implied, recurse_cnt, res); 6451f5207b7SJohn Levon case '|': 6461f5207b7SJohn Levon case '^': 647efe51d0cSJohn Levon return use_rl_binop(expr, implied, recurse_cnt, res); 6481f5207b7SJohn Levon case SPECIAL_RIGHTSHIFT: 649efe51d0cSJohn Levon return handle_right_shift(expr, implied, recurse_cnt, res); 6501f5207b7SJohn Levon case SPECIAL_LEFTSHIFT: 651efe51d0cSJohn Levon return handle_left_shift(expr, implied, recurse_cnt, res); 6521f5207b7SJohn Levon case '-': 653efe51d0cSJohn Levon return handle_subtract_rl(expr, implied, recurse_cnt, res); 6541f5207b7SJohn Levon case '/': 655efe51d0cSJohn Levon return handle_divide_rl(expr, implied, recurse_cnt, res); 6561f5207b7SJohn Levon } 6571f5207b7SJohn Levon 6581f5207b7SJohn Levon if (!left_rl || !right_rl) 659efe51d0cSJohn Levon return false; 6601f5207b7SJohn Levon 6611f5207b7SJohn Levon if (sval_binop_overflows(rl_min(left_rl), expr->op, rl_min(right_rl))) 662efe51d0cSJohn Levon return false; 6631f5207b7SJohn Levon if (sval_binop_overflows(rl_max(left_rl), expr->op, rl_max(right_rl))) 664efe51d0cSJohn Levon return false; 6651f5207b7SJohn Levon 6661f5207b7SJohn Levon min = sval_binop(rl_min(left_rl), expr->op, rl_min(right_rl)); 6671f5207b7SJohn Levon max = sval_binop(rl_max(left_rl), expr->op, rl_max(right_rl)); 6681f5207b7SJohn Levon 669efe51d0cSJohn Levon *res = alloc_rl(min, max); 670efe51d0cSJohn Levon return true; 671efe51d0cSJohn Levon 672efe51d0cSJohn Levon } 673efe51d0cSJohn Levon 674efe51d0cSJohn Levon static bool handle_binop_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval) 675efe51d0cSJohn Levon { 676efe51d0cSJohn Levon struct smatch_state *state; 677efe51d0cSJohn Levon struct range_list *rl; 678efe51d0cSJohn Levon sval_t val; 679efe51d0cSJohn Levon 680efe51d0cSJohn Levon if (handle_known_binop(expr, &val)) { 681efe51d0cSJohn Levon *res_sval = val; 682efe51d0cSJohn Levon return true; 683efe51d0cSJohn Levon } 684efe51d0cSJohn Levon if (implied == RL_EXACT) 685efe51d0cSJohn Levon return false; 686efe51d0cSJohn Levon 687efe51d0cSJohn Levon if (custom_handle_variable) { 688efe51d0cSJohn Levon rl = custom_handle_variable(expr); 689efe51d0cSJohn Levon if (rl) { 690efe51d0cSJohn Levon *res = rl; 691efe51d0cSJohn Levon return true; 692efe51d0cSJohn Levon } 693efe51d0cSJohn Levon } 694efe51d0cSJohn Levon 695efe51d0cSJohn Levon state = get_extra_state(expr); 696efe51d0cSJohn Levon if (state && !is_whole_rl(estate_rl(state))) { 697efe51d0cSJohn Levon if (implied != RL_HARD || estate_has_hard_max(state)) { 698efe51d0cSJohn Levon *res = clone_rl(estate_rl(state)); 699efe51d0cSJohn Levon return true; 700efe51d0cSJohn Levon } 701efe51d0cSJohn Levon } 702efe51d0cSJohn Levon 703efe51d0cSJohn Levon return handle_binop_rl_helper(expr, implied, recurse_cnt, res, res_sval); 7041f5207b7SJohn Levon } 7051f5207b7SJohn Levon 7061f5207b7SJohn Levon static int do_comparison(struct expression *expr) 7071f5207b7SJohn Levon { 7081f5207b7SJohn Levon struct range_list *left_ranges = NULL; 7091f5207b7SJohn Levon struct range_list *right_ranges = NULL; 7101f5207b7SJohn Levon int poss_true, poss_false; 7111f5207b7SJohn Levon struct symbol *type; 7121f5207b7SJohn Levon 7131f5207b7SJohn Levon type = get_type(expr); 7141f5207b7SJohn Levon get_absolute_rl(expr->left, &left_ranges); 7151f5207b7SJohn Levon get_absolute_rl(expr->right, &right_ranges); 7161f5207b7SJohn Levon 7171f5207b7SJohn Levon left_ranges = cast_rl(type, left_ranges); 7181f5207b7SJohn Levon right_ranges = cast_rl(type, right_ranges); 7191f5207b7SJohn Levon 7201f5207b7SJohn Levon poss_true = possibly_true_rl(left_ranges, expr->op, right_ranges); 7211f5207b7SJohn Levon poss_false = possibly_false_rl(left_ranges, expr->op, right_ranges); 7221f5207b7SJohn Levon 7231f5207b7SJohn Levon if (!poss_true && !poss_false) 7241f5207b7SJohn Levon return 0x0; 7251f5207b7SJohn Levon if (poss_true && !poss_false) 7261f5207b7SJohn Levon return 0x1; 7271f5207b7SJohn Levon if (!poss_true && poss_false) 7281f5207b7SJohn Levon return 0x2; 7291f5207b7SJohn Levon return 0x3; 7301f5207b7SJohn Levon } 7311f5207b7SJohn Levon 732efe51d0cSJohn Levon static bool handle_comparison_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval) 7331f5207b7SJohn Levon { 7341f5207b7SJohn Levon sval_t left, right; 735efe51d0cSJohn Levon int cmp; 7361f5207b7SJohn Levon 7371f5207b7SJohn Levon if (expr->op == SPECIAL_EQUAL && expr->left->type == EXPR_TYPE) { 7381f5207b7SJohn Levon struct symbol *left, *right; 7391f5207b7SJohn Levon 740efe51d0cSJohn Levon if (expr->right->type != EXPR_TYPE) 741efe51d0cSJohn Levon return false; 742efe51d0cSJohn Levon 7431f5207b7SJohn Levon left = get_real_base_type(expr->left->symbol); 744efe51d0cSJohn Levon right = get_real_base_type(expr->right->symbol); 745efe51d0cSJohn Levon if (type_bits(left) == type_bits(right) && 746efe51d0cSJohn Levon type_positive_bits(left) == type_positive_bits(right)) 747efe51d0cSJohn Levon *res_sval = one; 748efe51d0cSJohn Levon else 749efe51d0cSJohn Levon *res_sval = zero; 750efe51d0cSJohn Levon return true; 7511f5207b7SJohn Levon } 7521f5207b7SJohn Levon 7531f5207b7SJohn Levon if (get_value(expr->left, &left) && get_value(expr->right, &right)) { 7541f5207b7SJohn Levon struct data_range tmp_left, tmp_right; 7551f5207b7SJohn Levon 7561f5207b7SJohn Levon tmp_left.min = left; 7571f5207b7SJohn Levon tmp_left.max = left; 7581f5207b7SJohn Levon tmp_right.min = right; 7591f5207b7SJohn Levon tmp_right.max = right; 7601f5207b7SJohn Levon if (true_comparison_range(&tmp_left, expr->op, &tmp_right)) 761efe51d0cSJohn Levon *res_sval = one; 762efe51d0cSJohn Levon else 763efe51d0cSJohn Levon *res_sval = zero; 764efe51d0cSJohn Levon return true; 7651f5207b7SJohn Levon } 7661f5207b7SJohn Levon 7671f5207b7SJohn Levon if (implied == RL_EXACT) 768efe51d0cSJohn Levon return false; 7691f5207b7SJohn Levon 770efe51d0cSJohn Levon cmp = do_comparison(expr); 771efe51d0cSJohn Levon if (cmp == 1) { 772efe51d0cSJohn Levon *res_sval = one; 773efe51d0cSJohn Levon return true; 774efe51d0cSJohn Levon } 775efe51d0cSJohn Levon if (cmp == 2) { 776efe51d0cSJohn Levon *res_sval = zero; 777efe51d0cSJohn Levon return true; 778efe51d0cSJohn Levon } 7791f5207b7SJohn Levon 780efe51d0cSJohn Levon *res = alloc_rl(zero, one); 781efe51d0cSJohn Levon return true; 7821f5207b7SJohn Levon } 7831f5207b7SJohn Levon 784efe51d0cSJohn Levon static bool handle_logical_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval) 7851f5207b7SJohn Levon { 7861f5207b7SJohn Levon sval_t left, right; 7871f5207b7SJohn Levon int left_known = 0; 7881f5207b7SJohn Levon int right_known = 0; 7891f5207b7SJohn Levon 7901f5207b7SJohn Levon if (implied == RL_EXACT) { 7911f5207b7SJohn Levon if (get_value(expr->left, &left)) 7921f5207b7SJohn Levon left_known = 1; 7931f5207b7SJohn Levon if (get_value(expr->right, &right)) 7941f5207b7SJohn Levon right_known = 1; 7951f5207b7SJohn Levon } else { 796efe51d0cSJohn Levon if (get_implied_value_internal(expr->left, recurse_cnt, &left)) 7971f5207b7SJohn Levon left_known = 1; 798efe51d0cSJohn Levon if (get_implied_value_internal(expr->right, recurse_cnt, &right)) 7991f5207b7SJohn Levon right_known = 1; 8001f5207b7SJohn Levon } 8011f5207b7SJohn Levon 8021f5207b7SJohn Levon switch (expr->op) { 8031f5207b7SJohn Levon case SPECIAL_LOGICAL_OR: 8041f5207b7SJohn Levon if (left_known && left.value) 805efe51d0cSJohn Levon goto one; 8061f5207b7SJohn Levon if (right_known && right.value) 807efe51d0cSJohn Levon goto one; 8081f5207b7SJohn Levon if (left_known && right_known) 809efe51d0cSJohn Levon goto zero; 8101f5207b7SJohn Levon break; 8111f5207b7SJohn Levon case SPECIAL_LOGICAL_AND: 8121f5207b7SJohn Levon if (left_known && right_known) { 8131f5207b7SJohn Levon if (left.value && right.value) 814efe51d0cSJohn Levon goto one; 815efe51d0cSJohn Levon goto zero; 8161f5207b7SJohn Levon } 8171f5207b7SJohn Levon break; 8181f5207b7SJohn Levon default: 819efe51d0cSJohn Levon return false; 8201f5207b7SJohn Levon } 8211f5207b7SJohn Levon 8221f5207b7SJohn Levon if (implied == RL_EXACT) 823efe51d0cSJohn Levon return false; 8241f5207b7SJohn Levon 825efe51d0cSJohn Levon *res = alloc_rl(zero, one); 826efe51d0cSJohn Levon return true; 827efe51d0cSJohn Levon 828efe51d0cSJohn Levon zero: 829efe51d0cSJohn Levon *res_sval = zero; 830efe51d0cSJohn Levon return true; 831efe51d0cSJohn Levon one: 832efe51d0cSJohn Levon *res_sval = one; 833efe51d0cSJohn Levon return true; 8341f5207b7SJohn Levon } 8351f5207b7SJohn Levon 836efe51d0cSJohn Levon static bool handle_conditional_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval) 8371f5207b7SJohn Levon { 8381f5207b7SJohn Levon struct expression *cond_true; 8391f5207b7SJohn Levon struct range_list *true_rl, *false_rl; 8401f5207b7SJohn Levon struct symbol *type; 8411f5207b7SJohn Levon int final_pass_orig = final_pass; 8421f5207b7SJohn Levon 8431f5207b7SJohn Levon cond_true = expr->cond_true; 8441f5207b7SJohn Levon if (!cond_true) 8451f5207b7SJohn Levon cond_true = expr->conditional; 8461f5207b7SJohn Levon 8471f5207b7SJohn Levon if (known_condition_true(expr->conditional)) 848efe51d0cSJohn Levon return get_rl_sval(cond_true, implied, recurse_cnt, res, res_sval); 8491f5207b7SJohn Levon if (known_condition_false(expr->conditional)) 850efe51d0cSJohn Levon return get_rl_sval(expr->cond_false, implied, recurse_cnt, res, res_sval); 8511f5207b7SJohn Levon 8521f5207b7SJohn Levon if (implied == RL_EXACT) 853efe51d0cSJohn Levon return false; 8541f5207b7SJohn Levon 8551f5207b7SJohn Levon if (implied_condition_true(expr->conditional)) 856efe51d0cSJohn Levon return get_rl_sval(cond_true, implied, recurse_cnt, res, res_sval); 8571f5207b7SJohn Levon if (implied_condition_false(expr->conditional)) 858efe51d0cSJohn Levon return get_rl_sval(expr->cond_false, implied, recurse_cnt, res, res_sval); 8591f5207b7SJohn Levon 8601f5207b7SJohn Levon /* this becomes a problem with deeply nested conditional statements */ 861*c85f09ccSJohn Levon if (fast_math_only || low_on_memory()) 862efe51d0cSJohn Levon return false; 8631f5207b7SJohn Levon 8641f5207b7SJohn Levon type = get_type(expr); 8651f5207b7SJohn Levon 8661f5207b7SJohn Levon __push_fake_cur_stree(); 8671f5207b7SJohn Levon final_pass = 0; 8681f5207b7SJohn Levon __split_whole_condition(expr->conditional); 869efe51d0cSJohn Levon true_rl = NULL; 870efe51d0cSJohn Levon get_rl_internal(cond_true, implied, recurse_cnt, &true_rl); 8711f5207b7SJohn Levon __push_true_states(); 8721f5207b7SJohn Levon __use_false_states(); 873efe51d0cSJohn Levon false_rl = NULL; 874efe51d0cSJohn Levon get_rl_internal(expr->cond_false, implied, recurse_cnt, &false_rl); 8751f5207b7SJohn Levon __merge_true_states(); 8761f5207b7SJohn Levon __free_fake_cur_stree(); 8771f5207b7SJohn Levon final_pass = final_pass_orig; 8781f5207b7SJohn Levon 8791f5207b7SJohn Levon if (!true_rl || !false_rl) 880efe51d0cSJohn Levon return false; 8811f5207b7SJohn Levon true_rl = cast_rl(type, true_rl); 8821f5207b7SJohn Levon false_rl = cast_rl(type, false_rl); 8831f5207b7SJohn Levon 884efe51d0cSJohn Levon *res = rl_union(true_rl, false_rl); 885efe51d0cSJohn Levon return true; 8861f5207b7SJohn Levon } 8871f5207b7SJohn Levon 888efe51d0cSJohn Levon static bool get_fuzzy_max_helper(struct expression *expr, sval_t *max) 8891f5207b7SJohn Levon { 8901f5207b7SJohn Levon struct smatch_state *state; 8911f5207b7SJohn Levon sval_t sval; 8921f5207b7SJohn Levon 8931f5207b7SJohn Levon if (get_hard_max(expr, &sval)) { 8941f5207b7SJohn Levon *max = sval; 895efe51d0cSJohn Levon return true; 8961f5207b7SJohn Levon } 8971f5207b7SJohn Levon 8981f5207b7SJohn Levon state = get_extra_state(expr); 8991f5207b7SJohn Levon if (!state || !estate_has_fuzzy_max(state)) 900efe51d0cSJohn Levon return false; 9011f5207b7SJohn Levon *max = sval_cast(get_type(expr), estate_get_fuzzy_max(state)); 902efe51d0cSJohn Levon return true; 9031f5207b7SJohn Levon } 9041f5207b7SJohn Levon 905efe51d0cSJohn Levon static bool get_fuzzy_min_helper(struct expression *expr, sval_t *min) 9061f5207b7SJohn Levon { 9071f5207b7SJohn Levon struct smatch_state *state; 9081f5207b7SJohn Levon sval_t sval; 9091f5207b7SJohn Levon 9101f5207b7SJohn Levon state = get_extra_state(expr); 9111f5207b7SJohn Levon if (!state || !estate_rl(state)) 912efe51d0cSJohn Levon return false; 9131f5207b7SJohn Levon 9141f5207b7SJohn Levon sval = estate_min(state); 9151f5207b7SJohn Levon if (sval_is_negative(sval) && sval_is_min(sval)) 916efe51d0cSJohn Levon return false; 9171f5207b7SJohn Levon 9181f5207b7SJohn Levon if (sval_is_max(sval)) 919efe51d0cSJohn Levon return false; 9201f5207b7SJohn Levon 9211f5207b7SJohn Levon *min = sval_cast(get_type(expr), sval); 922efe51d0cSJohn Levon return true; 9231f5207b7SJohn Levon } 9241f5207b7SJohn Levon 9251f5207b7SJohn Levon int get_const_value(struct expression *expr, sval_t *sval) 9261f5207b7SJohn Levon { 9271f5207b7SJohn Levon struct symbol *sym; 9281f5207b7SJohn Levon sval_t right; 9291f5207b7SJohn Levon 9301f5207b7SJohn Levon if (expr->type != EXPR_SYMBOL || !expr->symbol) 9311f5207b7SJohn Levon return 0; 9321f5207b7SJohn Levon sym = expr->symbol; 9331f5207b7SJohn Levon if (!(sym->ctype.modifiers & MOD_CONST)) 9341f5207b7SJohn Levon return 0; 9351f5207b7SJohn Levon if (get_value(sym->initializer, &right)) { 9361f5207b7SJohn Levon *sval = sval_cast(get_type(expr), right); 9371f5207b7SJohn Levon return 1; 9381f5207b7SJohn Levon } 9391f5207b7SJohn Levon return 0; 9401f5207b7SJohn Levon } 9411f5207b7SJohn Levon 9421f5207b7SJohn Levon struct range_list *var_to_absolute_rl(struct expression *expr) 9431f5207b7SJohn Levon { 9441f5207b7SJohn Levon struct smatch_state *state; 9451f5207b7SJohn Levon struct range_list *rl; 9461f5207b7SJohn Levon 9471f5207b7SJohn Levon state = get_extra_state(expr); 9481f5207b7SJohn Levon if (!state || is_whole_rl(estate_rl(state))) { 9491f5207b7SJohn Levon state = get_real_absolute_state(expr); 9501f5207b7SJohn Levon if (state && state->data && !estate_is_whole(state)) 9511f5207b7SJohn Levon return clone_rl(estate_rl(state)); 9521f5207b7SJohn Levon if (get_mtag_rl(expr, &rl)) 9531f5207b7SJohn Levon return rl; 9541f5207b7SJohn Levon if (get_db_type_rl(expr, &rl) && !is_whole_rl(rl)) 9551f5207b7SJohn Levon return rl; 9561f5207b7SJohn Levon return alloc_whole_rl(get_type(expr)); 9571f5207b7SJohn Levon } 9581f5207b7SJohn Levon /* err on the side of saying things are possible */ 9591f5207b7SJohn Levon if (!estate_rl(state)) 9601f5207b7SJohn Levon return alloc_whole_rl(get_type(expr)); 9611f5207b7SJohn Levon return clone_rl(estate_rl(state)); 9621f5207b7SJohn Levon } 9631f5207b7SJohn Levon 964efe51d0cSJohn Levon static bool handle_variable(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval) 9651f5207b7SJohn Levon { 9661f5207b7SJohn Levon struct smatch_state *state; 9671f5207b7SJohn Levon struct range_list *rl; 9681f5207b7SJohn Levon sval_t sval, min, max; 9691f5207b7SJohn Levon struct symbol *type; 9701f5207b7SJohn Levon 971efe51d0cSJohn Levon if (get_const_value(expr, &sval)) { 972efe51d0cSJohn Levon *res_sval = sval; 973efe51d0cSJohn Levon return true; 974efe51d0cSJohn Levon } 975efe51d0cSJohn Levon 976efe51d0cSJohn Levon if (implied == RL_EXACT) 977efe51d0cSJohn Levon return false; 9781f5207b7SJohn Levon 9791f5207b7SJohn Levon if (custom_handle_variable) { 9801f5207b7SJohn Levon rl = custom_handle_variable(expr); 981efe51d0cSJohn Levon if (rl) { 982efe51d0cSJohn Levon if (!rl_to_sval(rl, res_sval)) 983efe51d0cSJohn Levon *res = rl; 984efe51d0cSJohn Levon } else { 985efe51d0cSJohn Levon *res = var_to_absolute_rl(expr); 986efe51d0cSJohn Levon } 987efe51d0cSJohn Levon return true; 9881f5207b7SJohn Levon } 9891f5207b7SJohn Levon 990efe51d0cSJohn Levon if (get_mtag_sval(expr, &sval)) { 991efe51d0cSJohn Levon *res_sval = sval; 992efe51d0cSJohn Levon return true; 993efe51d0cSJohn Levon } 9941f5207b7SJohn Levon 9951f5207b7SJohn Levon type = get_type(expr); 996efe51d0cSJohn Levon if (type && 997efe51d0cSJohn Levon (type->type == SYM_ARRAY || 998efe51d0cSJohn Levon type->type == SYM_FN)) 999efe51d0cSJohn Levon return handle_address(expr, implied, recurse_cnt, res, res_sval); 1000efe51d0cSJohn Levon 1001efe51d0cSJohn Levon /* FIXME: call rl_to_sval() on the results */ 10021f5207b7SJohn Levon 10031f5207b7SJohn Levon switch (implied) { 10041f5207b7SJohn Levon case RL_HARD: 10051f5207b7SJohn Levon case RL_IMPLIED: 10061f5207b7SJohn Levon case RL_ABSOLUTE: 10071f5207b7SJohn Levon state = get_extra_state(expr); 1008efe51d0cSJohn Levon if (!state) { 10091f5207b7SJohn Levon if (implied == RL_HARD) 1010efe51d0cSJohn Levon return false; 1011efe51d0cSJohn Levon if (get_mtag_rl(expr, res)) 1012efe51d0cSJohn Levon return true; 1013efe51d0cSJohn Levon if (get_db_type_rl(expr, res)) 1014efe51d0cSJohn Levon return true; 1015efe51d0cSJohn Levon if (is_array(expr) && get_array_rl(expr, res)) 1016efe51d0cSJohn Levon return true; 1017efe51d0cSJohn Levon return false; 10181f5207b7SJohn Levon } 10191f5207b7SJohn Levon if (implied == RL_HARD && !estate_has_hard_max(state)) 1020efe51d0cSJohn Levon return false; 1021efe51d0cSJohn Levon *res = clone_rl(estate_rl(state)); 1022efe51d0cSJohn Levon return true; 10231f5207b7SJohn Levon case RL_REAL_ABSOLUTE: { 10241f5207b7SJohn Levon struct smatch_state *abs_state; 10251f5207b7SJohn Levon 10261f5207b7SJohn Levon state = get_extra_state(expr); 10271f5207b7SJohn Levon abs_state = get_real_absolute_state(expr); 10281f5207b7SJohn Levon 10291f5207b7SJohn Levon if (estate_rl(state) && estate_rl(abs_state)) { 1030efe51d0cSJohn Levon *res = clone_rl(rl_intersection(estate_rl(state), 10311f5207b7SJohn Levon estate_rl(abs_state))); 1032efe51d0cSJohn Levon return true; 10331f5207b7SJohn Levon } else if (estate_rl(state)) { 1034efe51d0cSJohn Levon *res = clone_rl(estate_rl(state)); 1035efe51d0cSJohn Levon return true; 10361f5207b7SJohn Levon } else if (estate_is_empty(state)) { 10371f5207b7SJohn Levon /* 10381f5207b7SJohn Levon * FIXME: we don't handle empty extra states correctly. 10391f5207b7SJohn Levon * 10401f5207b7SJohn Levon * The real abs rl is supposed to be filtered by the 10411f5207b7SJohn Levon * extra state if there is one. We don't bother keeping 10421f5207b7SJohn Levon * the abs state in sync all the time because we know it 10431f5207b7SJohn Levon * will be filtered later. 10441f5207b7SJohn Levon * 10451f5207b7SJohn Levon * It's not totally obvious to me how they should be 10461f5207b7SJohn Levon * handled. Perhaps we should take the whole rl and 10471f5207b7SJohn Levon * filter by the imaginary states. Perhaps we should 10481f5207b7SJohn Levon * just go with the empty state. 10491f5207b7SJohn Levon * 10501f5207b7SJohn Levon * Anyway what we currently do is return NULL here and 10511f5207b7SJohn Levon * that gets translated into the whole range in 10521f5207b7SJohn Levon * get_real_absolute_rl(). 10531f5207b7SJohn Levon * 10541f5207b7SJohn Levon */ 1055efe51d0cSJohn Levon return false; 10561f5207b7SJohn Levon } else if (estate_rl(abs_state)) { 1057efe51d0cSJohn Levon *res = clone_rl(estate_rl(abs_state)); 1058efe51d0cSJohn Levon return true; 10591f5207b7SJohn Levon } 10601f5207b7SJohn Levon 1061efe51d0cSJohn Levon if (get_mtag_rl(expr, res)) 1062efe51d0cSJohn Levon return true; 1063efe51d0cSJohn Levon if (get_db_type_rl(expr, res)) 1064efe51d0cSJohn Levon return true; 1065efe51d0cSJohn Levon if (is_array(expr) && get_array_rl(expr, res)) 1066efe51d0cSJohn Levon return true; 1067efe51d0cSJohn Levon return false; 10681f5207b7SJohn Levon } 10691f5207b7SJohn Levon case RL_FUZZY: 10701f5207b7SJohn Levon if (!get_fuzzy_min_helper(expr, &min)) 10711f5207b7SJohn Levon min = sval_type_min(get_type(expr)); 10721f5207b7SJohn Levon if (!get_fuzzy_max_helper(expr, &max)) 1073efe51d0cSJohn Levon return false; 10741f5207b7SJohn Levon /* fuzzy ranges are often inverted */ 10751f5207b7SJohn Levon if (sval_cmp(min, max) > 0) { 10761f5207b7SJohn Levon sval = min; 10771f5207b7SJohn Levon min = max; 10781f5207b7SJohn Levon max = sval; 10791f5207b7SJohn Levon } 1080efe51d0cSJohn Levon *res = alloc_rl(min, max); 1081efe51d0cSJohn Levon return true; 10821f5207b7SJohn Levon } 1083efe51d0cSJohn Levon return false; 10841f5207b7SJohn Levon } 10851f5207b7SJohn Levon 10861f5207b7SJohn Levon static sval_t handle_sizeof(struct expression *expr) 10871f5207b7SJohn Levon { 10881f5207b7SJohn Levon struct symbol *sym; 10891f5207b7SJohn Levon sval_t ret; 10901f5207b7SJohn Levon 10911f5207b7SJohn Levon ret = sval_blank(expr); 10921f5207b7SJohn Levon sym = expr->cast_type; 10931f5207b7SJohn Levon if (!sym) { 10941f5207b7SJohn Levon sym = evaluate_expression(expr->cast_expression); 10951f5207b7SJohn Levon if (!sym) { 10961f5207b7SJohn Levon __silence_warnings_for_stmt = true; 10971f5207b7SJohn Levon sym = &int_ctype; 10981f5207b7SJohn Levon } 10991f5207b7SJohn Levon #if 0 11001f5207b7SJohn Levon /* 11011f5207b7SJohn Levon * Expressions of restricted types will possibly get 11021f5207b7SJohn Levon * promoted - check that here. I'm not sure how this works, 11031f5207b7SJohn Levon * the problem is that sizeof(le16) shouldn't be promoted and 11041f5207b7SJohn Levon * the original code did that... Let's if zero this out and 11051f5207b7SJohn Levon * see what breaks. 11061f5207b7SJohn Levon */ 11071f5207b7SJohn Levon 11081f5207b7SJohn Levon if (is_restricted_type(sym)) { 11091f5207b7SJohn Levon if (type_bits(sym) < bits_in_int) 11101f5207b7SJohn Levon sym = &int_ctype; 11111f5207b7SJohn Levon } 11121f5207b7SJohn Levon #endif 11131f5207b7SJohn Levon if (is_fouled_type(sym)) 11141f5207b7SJohn Levon sym = &int_ctype; 11151f5207b7SJohn Levon } 11161f5207b7SJohn Levon examine_symbol_type(sym); 11171f5207b7SJohn Levon 11181f5207b7SJohn Levon ret.type = size_t_ctype; 11191f5207b7SJohn Levon if (type_bits(sym) <= 0) /* sizeof(void) */ { 11201f5207b7SJohn Levon if (get_real_base_type(sym) == &void_ctype) 11211f5207b7SJohn Levon ret.value = 1; 11221f5207b7SJohn Levon else 11231f5207b7SJohn Levon ret.value = 0; 11241f5207b7SJohn Levon } else 11251f5207b7SJohn Levon ret.value = type_bytes(sym); 11261f5207b7SJohn Levon 11271f5207b7SJohn Levon return ret; 11281f5207b7SJohn Levon } 11291f5207b7SJohn Levon 1130efe51d0cSJohn Levon static bool handle_strlen(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval) 11311f5207b7SJohn Levon { 11321f5207b7SJohn Levon struct expression *arg, *tmp; 11331f5207b7SJohn Levon sval_t tag; 11341f5207b7SJohn Levon sval_t ret = { .type = &ulong_ctype }; 1135efe51d0cSJohn Levon struct range_list *rl; 11361f5207b7SJohn Levon 11371f5207b7SJohn Levon arg = get_argument_from_call_expr(expr->args, 0); 11381f5207b7SJohn Levon if (!arg) 1139efe51d0cSJohn Levon return false; 11401f5207b7SJohn Levon if (arg->type == EXPR_STRING) { 11411f5207b7SJohn Levon ret.value = arg->string->length - 1; 1142efe51d0cSJohn Levon *res_sval = ret; 1143efe51d0cSJohn Levon return true; 11441f5207b7SJohn Levon } 1145efe51d0cSJohn Levon if (implied == RL_EXACT) 1146efe51d0cSJohn Levon return false; 11471f5207b7SJohn Levon if (get_implied_value(arg, &tag) && 11481f5207b7SJohn Levon (tmp = fake_string_from_mtag(tag.uvalue))) { 11491f5207b7SJohn Levon ret.value = tmp->string->length - 1; 1150efe51d0cSJohn Levon *res_sval = ret; 1151efe51d0cSJohn Levon return true; 11521f5207b7SJohn Levon } 11531f5207b7SJohn Levon 11541f5207b7SJohn Levon if (implied == RL_HARD || implied == RL_FUZZY) 1155efe51d0cSJohn Levon return false; 11561f5207b7SJohn Levon 1157efe51d0cSJohn Levon if (get_implied_return(expr, &rl)) { 1158efe51d0cSJohn Levon *res = rl; 1159efe51d0cSJohn Levon return true; 1160efe51d0cSJohn Levon } 11611f5207b7SJohn Levon 1162efe51d0cSJohn Levon return false; 11631f5207b7SJohn Levon } 11641f5207b7SJohn Levon 1165efe51d0cSJohn Levon static bool handle_builtin_constant_p(struct expression *expr, int implied, int *recurse_cnt, sval_t *res_sval) 11661f5207b7SJohn Levon { 11671f5207b7SJohn Levon struct expression *arg; 11681f5207b7SJohn Levon struct range_list *rl; 11691f5207b7SJohn Levon 11701f5207b7SJohn Levon arg = get_argument_from_call_expr(expr->args, 0); 1171efe51d0cSJohn Levon if (get_rl_internal(arg, RL_EXACT, recurse_cnt, &rl)) 1172efe51d0cSJohn Levon *res_sval = one; 1173efe51d0cSJohn Levon else 1174efe51d0cSJohn Levon *res_sval = zero; 1175efe51d0cSJohn Levon return true; 11761f5207b7SJohn Levon } 11771f5207b7SJohn Levon 1178efe51d0cSJohn Levon static bool handle__builtin_choose_expr(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval) 11791f5207b7SJohn Levon { 11801f5207b7SJohn Levon struct expression *const_expr, *expr1, *expr2; 11811f5207b7SJohn Levon sval_t sval; 11821f5207b7SJohn Levon 11831f5207b7SJohn Levon const_expr = get_argument_from_call_expr(expr->args, 0); 11841f5207b7SJohn Levon expr1 = get_argument_from_call_expr(expr->args, 1); 11851f5207b7SJohn Levon expr2 = get_argument_from_call_expr(expr->args, 2); 11861f5207b7SJohn Levon 11871f5207b7SJohn Levon if (!get_value(const_expr, &sval) || !expr1 || !expr2) 1188efe51d0cSJohn Levon return false; 11891f5207b7SJohn Levon if (sval.value) 1190efe51d0cSJohn Levon return get_rl_sval(expr1, implied, recurse_cnt, res, res_sval); 1191efe51d0cSJohn Levon else 1192efe51d0cSJohn Levon return get_rl_sval(expr2, implied, recurse_cnt, res, res_sval); 11931f5207b7SJohn Levon } 11941f5207b7SJohn Levon 1195efe51d0cSJohn Levon static bool handle_call_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval) 11961f5207b7SJohn Levon { 11971f5207b7SJohn Levon struct range_list *rl; 11981f5207b7SJohn Levon 11991f5207b7SJohn Levon if (sym_name_is("__builtin_constant_p", expr->fn)) 1200efe51d0cSJohn Levon return handle_builtin_constant_p(expr, implied, recurse_cnt, res_sval); 12011f5207b7SJohn Levon 12021f5207b7SJohn Levon if (sym_name_is("__builtin_choose_expr", expr->fn)) 1203efe51d0cSJohn Levon return handle__builtin_choose_expr(expr, implied, recurse_cnt, res, res_sval); 12041f5207b7SJohn Levon 12051f5207b7SJohn Levon if (sym_name_is("__builtin_expect", expr->fn) || 12061f5207b7SJohn Levon sym_name_is("__builtin_bswap16", expr->fn) || 12071f5207b7SJohn Levon sym_name_is("__builtin_bswap32", expr->fn) || 12081f5207b7SJohn Levon sym_name_is("__builtin_bswap64", expr->fn)) { 12091f5207b7SJohn Levon struct expression *arg; 12101f5207b7SJohn Levon 12111f5207b7SJohn Levon arg = get_argument_from_call_expr(expr->args, 0); 1212efe51d0cSJohn Levon return get_rl_sval(arg, implied, recurse_cnt, res, res_sval); 12131f5207b7SJohn Levon } 12141f5207b7SJohn Levon 12151f5207b7SJohn Levon if (sym_name_is("strlen", expr->fn)) 1216efe51d0cSJohn Levon return handle_strlen(expr, implied, recurse_cnt, res, res_sval); 12171f5207b7SJohn Levon 12181f5207b7SJohn Levon if (implied == RL_EXACT || implied == RL_HARD || implied == RL_FUZZY) 1219efe51d0cSJohn Levon return false; 12201f5207b7SJohn Levon 12211f5207b7SJohn Levon if (custom_handle_variable) { 12221f5207b7SJohn Levon rl = custom_handle_variable(expr); 1223efe51d0cSJohn Levon if (rl) { 1224efe51d0cSJohn Levon *res = rl; 1225efe51d0cSJohn Levon return true; 1226efe51d0cSJohn Levon } 12271f5207b7SJohn Levon } 12281f5207b7SJohn Levon 1229efe51d0cSJohn Levon /* Ugh... get_implied_return() sets *rl to NULL on failure */ 1230efe51d0cSJohn Levon if (get_implied_return(expr, &rl)) { 1231efe51d0cSJohn Levon *res = rl; 1232efe51d0cSJohn Levon return true; 1233efe51d0cSJohn Levon } 1234efe51d0cSJohn Levon rl = db_return_vals(expr); 1235efe51d0cSJohn Levon if (rl) { 1236efe51d0cSJohn Levon *res = rl; 1237efe51d0cSJohn Levon return true; 1238efe51d0cSJohn Levon } 1239efe51d0cSJohn Levon return false; 12401f5207b7SJohn Levon } 12411f5207b7SJohn Levon 1242efe51d0cSJohn Levon static bool handle_cast(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval) 12431f5207b7SJohn Levon { 12441f5207b7SJohn Levon struct range_list *rl; 12451f5207b7SJohn Levon struct symbol *type; 1246efe51d0cSJohn Levon sval_t sval = {}; 12471f5207b7SJohn Levon 12481f5207b7SJohn Levon type = get_type(expr); 1249efe51d0cSJohn Levon if (get_rl_sval(expr->cast_expression, implied, recurse_cnt, &rl, &sval)) { 1250efe51d0cSJohn Levon if (sval.type) 1251efe51d0cSJohn Levon *res_sval = sval_cast(type, sval); 1252efe51d0cSJohn Levon else 1253efe51d0cSJohn Levon *res = cast_rl(type, rl); 1254efe51d0cSJohn Levon return true; 1255efe51d0cSJohn Levon } 1256efe51d0cSJohn Levon if (implied == RL_ABSOLUTE || implied == RL_REAL_ABSOLUTE) { 1257efe51d0cSJohn Levon *res = alloc_whole_rl(type); 1258efe51d0cSJohn Levon return true; 1259efe51d0cSJohn Levon } 12601f5207b7SJohn Levon if (implied == RL_IMPLIED && type && 1261efe51d0cSJohn Levon type_bits(type) > 0 && type_bits(type) < 32) { 1262efe51d0cSJohn Levon *res = alloc_whole_rl(type); 1263efe51d0cSJohn Levon return true; 1264efe51d0cSJohn Levon } 1265efe51d0cSJohn Levon return false; 12661f5207b7SJohn Levon } 12671f5207b7SJohn Levon 1268efe51d0cSJohn Levon static bool get_offset_from_down(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval) 12691f5207b7SJohn Levon { 1270efe51d0cSJohn Levon struct expression *index; 1271efe51d0cSJohn Levon struct symbol *type = expr->in; 12721f5207b7SJohn Levon struct range_list *rl; 1273efe51d0cSJohn Levon struct symbol *field; 1274efe51d0cSJohn Levon int offset = 0; 1275efe51d0cSJohn Levon sval_t sval = { .type = ssize_t_ctype }; 1276efe51d0cSJohn Levon sval_t tmp_sval = {}; 1277efe51d0cSJohn Levon 1278efe51d0cSJohn Levon /* 1279efe51d0cSJohn Levon * FIXME: I don't really know what I'm doing here. I wish that I 1280efe51d0cSJohn Levon * could just get rid of the __builtin_offset() function and use: 1281efe51d0cSJohn Levon * "&((struct bpf_prog *)NULL)->insns[fprog->len]" instead... 1282efe51d0cSJohn Levon * Anyway, I have done the minimum ammount of work to get that 1283efe51d0cSJohn Levon * expression to work. 1284efe51d0cSJohn Levon * 1285efe51d0cSJohn Levon */ 1286efe51d0cSJohn Levon 1287efe51d0cSJohn Levon if (expr->op != '.' || !expr->down || 1288efe51d0cSJohn Levon expr->down->type != EXPR_OFFSETOF || 1289efe51d0cSJohn Levon expr->down->op != '[' || 1290efe51d0cSJohn Levon !expr->down->index) 1291efe51d0cSJohn Levon return false; 1292efe51d0cSJohn Levon 1293efe51d0cSJohn Levon index = expr->down->index; 1294efe51d0cSJohn Levon 1295efe51d0cSJohn Levon examine_symbol_type(type); 1296efe51d0cSJohn Levon type = get_real_base_type(type); 1297efe51d0cSJohn Levon if (!type) 1298efe51d0cSJohn Levon return false; 1299efe51d0cSJohn Levon field = find_identifier(expr->ident, type->symbol_list, &offset); 1300efe51d0cSJohn Levon if (!field) 1301efe51d0cSJohn Levon return false; 1302efe51d0cSJohn Levon 1303efe51d0cSJohn Levon type = get_real_base_type(field); 1304efe51d0cSJohn Levon if (!type || type->type != SYM_ARRAY) 1305efe51d0cSJohn Levon return false; 1306efe51d0cSJohn Levon type = get_real_base_type(type); 1307efe51d0cSJohn Levon 1308efe51d0cSJohn Levon if (get_implied_value_internal(index, recurse_cnt, &sval)) { 1309efe51d0cSJohn Levon res_sval->type = ssize_t_ctype; 1310efe51d0cSJohn Levon res_sval->value = offset + sval.value * type_bytes(type); 1311efe51d0cSJohn Levon return true; 1312efe51d0cSJohn Levon } 1313efe51d0cSJohn Levon 1314efe51d0cSJohn Levon if (!get_rl_sval(index, implied, recurse_cnt, &rl, &tmp_sval)) 1315efe51d0cSJohn Levon return false; 1316efe51d0cSJohn Levon 1317efe51d0cSJohn Levon /* 1318efe51d0cSJohn Levon * I'm not sure why get_rl_sval() would return an sval when 1319efe51d0cSJohn Levon * get_implied_value_internal() failed but it does when I 1320efe51d0cSJohn Levon * parse drivers/net/ethernet/mellanox/mlx5/core/en/monitor_stats.c 1321efe51d0cSJohn Levon * 1322efe51d0cSJohn Levon */ 1323efe51d0cSJohn Levon if (tmp_sval.type) { 1324efe51d0cSJohn Levon res_sval->type = ssize_t_ctype; 1325efe51d0cSJohn Levon res_sval->value = offset + sval.value * type_bytes(type); 1326efe51d0cSJohn Levon return true; 1327efe51d0cSJohn Levon } 1328efe51d0cSJohn Levon 1329efe51d0cSJohn Levon sval.value = type_bytes(type); 1330efe51d0cSJohn Levon rl = rl_binop(rl, '*', alloc_rl(sval, sval)); 1331efe51d0cSJohn Levon sval.value = offset; 1332efe51d0cSJohn Levon *res = rl_binop(rl, '+', alloc_rl(sval, sval)); 1333efe51d0cSJohn Levon return true; 1334efe51d0cSJohn Levon } 1335efe51d0cSJohn Levon 1336efe51d0cSJohn Levon static bool get_offset_from_in(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval) 1337efe51d0cSJohn Levon { 1338efe51d0cSJohn Levon struct symbol *type = get_real_base_type(expr->in); 1339efe51d0cSJohn Levon struct symbol *field; 1340efe51d0cSJohn Levon int offset = 0; 1341efe51d0cSJohn Levon 1342efe51d0cSJohn Levon if (expr->op != '.' || !type || !expr->ident) 1343efe51d0cSJohn Levon return false; 1344efe51d0cSJohn Levon 1345efe51d0cSJohn Levon field = find_identifier(expr->ident, type->symbol_list, &offset); 1346efe51d0cSJohn Levon if (!field) 1347efe51d0cSJohn Levon return false; 1348efe51d0cSJohn Levon 1349efe51d0cSJohn Levon res_sval->type = size_t_ctype; 1350efe51d0cSJohn Levon res_sval->value = offset; 1351efe51d0cSJohn Levon 1352efe51d0cSJohn Levon return true; 1353efe51d0cSJohn Levon } 1354efe51d0cSJohn Levon 1355efe51d0cSJohn Levon static bool handle_offsetof_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval) 1356efe51d0cSJohn Levon { 1357efe51d0cSJohn Levon if (get_offset_from_down(expr, implied, recurse_cnt, res, res_sval)) 1358efe51d0cSJohn Levon return true; 1359efe51d0cSJohn Levon 1360efe51d0cSJohn Levon if (get_offset_from_in(expr, implied, recurse_cnt, res, res_sval)) 1361efe51d0cSJohn Levon return true; 1362efe51d0cSJohn Levon 1363efe51d0cSJohn Levon evaluate_expression(expr); 1364efe51d0cSJohn Levon if (expr->type == EXPR_VALUE) { 1365efe51d0cSJohn Levon *res_sval = sval_from_val(expr, expr->value); 1366efe51d0cSJohn Levon return true; 1367efe51d0cSJohn Levon } 1368efe51d0cSJohn Levon return false; 1369efe51d0cSJohn Levon } 1370efe51d0cSJohn Levon 1371efe51d0cSJohn Levon static bool get_rl_sval(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *sval_res) 1372efe51d0cSJohn Levon { 1373efe51d0cSJohn Levon struct range_list *rl = (void *)-1UL; 13741f5207b7SJohn Levon struct symbol *type; 1375efe51d0cSJohn Levon sval_t sval = {}; 13761f5207b7SJohn Levon 13771f5207b7SJohn Levon type = get_type(expr); 13781f5207b7SJohn Levon expr = strip_parens(expr); 13791f5207b7SJohn Levon if (!expr) 1380efe51d0cSJohn Levon return false; 13811f5207b7SJohn Levon 13821f5207b7SJohn Levon if (++(*recurse_cnt) >= 200) 1383efe51d0cSJohn Levon return false; 13841f5207b7SJohn Levon 13851f5207b7SJohn Levon switch(expr->type) { 13861f5207b7SJohn Levon case EXPR_CAST: 13871f5207b7SJohn Levon case EXPR_FORCE_CAST: 13881f5207b7SJohn Levon case EXPR_IMPLIED_CAST: 1389efe51d0cSJohn Levon handle_cast(expr, implied, recurse_cnt, &rl, &sval); 13901f5207b7SJohn Levon goto out_cast; 13911f5207b7SJohn Levon } 13921f5207b7SJohn Levon 13931f5207b7SJohn Levon expr = strip_expr(expr); 13941f5207b7SJohn Levon if (!expr) 1395efe51d0cSJohn Levon return false; 13961f5207b7SJohn Levon 13971f5207b7SJohn Levon switch (expr->type) { 13981f5207b7SJohn Levon case EXPR_VALUE: 13991f5207b7SJohn Levon sval = sval_from_val(expr, expr->value); 14001f5207b7SJohn Levon break; 14011f5207b7SJohn Levon case EXPR_PREOP: 1402efe51d0cSJohn Levon handle_preop_rl(expr, implied, recurse_cnt, &rl, &sval); 14031f5207b7SJohn Levon break; 14041f5207b7SJohn Levon case EXPR_POSTOP: 1405efe51d0cSJohn Levon get_rl_sval(expr->unop, implied, recurse_cnt, &rl, &sval); 14061f5207b7SJohn Levon break; 14071f5207b7SJohn Levon case EXPR_BINOP: 1408efe51d0cSJohn Levon handle_binop_rl(expr, implied, recurse_cnt, &rl, &sval); 14091f5207b7SJohn Levon break; 14101f5207b7SJohn Levon case EXPR_COMPARE: 1411efe51d0cSJohn Levon handle_comparison_rl(expr, implied, recurse_cnt, &rl, &sval); 14121f5207b7SJohn Levon break; 14131f5207b7SJohn Levon case EXPR_LOGICAL: 1414efe51d0cSJohn Levon handle_logical_rl(expr, implied, recurse_cnt, &rl, &sval); 14151f5207b7SJohn Levon break; 14161f5207b7SJohn Levon case EXPR_PTRSIZEOF: 14171f5207b7SJohn Levon case EXPR_SIZEOF: 14181f5207b7SJohn Levon sval = handle_sizeof(expr); 14191f5207b7SJohn Levon break; 14201f5207b7SJohn Levon case EXPR_SELECT: 14211f5207b7SJohn Levon case EXPR_CONDITIONAL: 1422efe51d0cSJohn Levon handle_conditional_rl(expr, implied, recurse_cnt, &rl, &sval); 14231f5207b7SJohn Levon break; 14241f5207b7SJohn Levon case EXPR_CALL: 1425efe51d0cSJohn Levon handle_call_rl(expr, implied, recurse_cnt, &rl, &sval); 14261f5207b7SJohn Levon break; 14271f5207b7SJohn Levon case EXPR_STRING: 14281f5207b7SJohn Levon if (get_mtag_sval(expr, &sval)) 1429efe51d0cSJohn Levon break; 1430efe51d0cSJohn Levon if (implied == RL_EXACT) 1431efe51d0cSJohn Levon break; 1432efe51d0cSJohn Levon rl = alloc_rl(valid_ptr_min_sval, valid_ptr_max_sval); 1433efe51d0cSJohn Levon break; 1434efe51d0cSJohn Levon case EXPR_OFFSETOF: 1435efe51d0cSJohn Levon handle_offsetof_rl(expr, implied, recurse_cnt, &rl, &sval); 1436efe51d0cSJohn Levon break; 1437efe51d0cSJohn Levon case EXPR_ALIGNOF: 1438efe51d0cSJohn Levon evaluate_expression(expr); 1439efe51d0cSJohn Levon if (expr->type == EXPR_VALUE) 1440efe51d0cSJohn Levon sval = sval_from_val(expr, expr->value); 14411f5207b7SJohn Levon break; 14421f5207b7SJohn Levon default: 1443efe51d0cSJohn Levon handle_variable(expr, implied, recurse_cnt, &rl, &sval); 14441f5207b7SJohn Levon } 14451f5207b7SJohn Levon 14461f5207b7SJohn Levon out_cast: 1447efe51d0cSJohn Levon if (rl == (void *)-1UL) 1448efe51d0cSJohn Levon rl = NULL; 1449efe51d0cSJohn Levon 1450efe51d0cSJohn Levon if (sval.type || (rl && rl_to_sval(rl, &sval))) { 1451efe51d0cSJohn Levon *sval_res = sval; 1452efe51d0cSJohn Levon return true; 1453efe51d0cSJohn Levon } 1454efe51d0cSJohn Levon if (implied == RL_EXACT) 1455efe51d0cSJohn Levon return false; 1456efe51d0cSJohn Levon 1457efe51d0cSJohn Levon if (rl) { 1458efe51d0cSJohn Levon *res = rl; 1459efe51d0cSJohn Levon return true; 1460efe51d0cSJohn Levon } 1461efe51d0cSJohn Levon if (type && (implied == RL_ABSOLUTE || implied == RL_REAL_ABSOLUTE)) { 1462efe51d0cSJohn Levon *res = alloc_whole_rl(type); 1463efe51d0cSJohn Levon return true; 1464efe51d0cSJohn Levon } 1465efe51d0cSJohn Levon return false; 1466efe51d0cSJohn Levon } 1467efe51d0cSJohn Levon 1468efe51d0cSJohn Levon static bool get_rl_internal(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res) 1469efe51d0cSJohn Levon { 1470efe51d0cSJohn Levon struct range_list *rl = NULL; 1471efe51d0cSJohn Levon sval_t sval = {}; 1472efe51d0cSJohn Levon 1473efe51d0cSJohn Levon if (!get_rl_sval(expr, implied, recurse_cnt, &rl, &sval)) 1474efe51d0cSJohn Levon return false; 1475efe51d0cSJohn Levon 1476efe51d0cSJohn Levon if (sval.type) 1477efe51d0cSJohn Levon *res = alloc_rl(sval, sval); 1478efe51d0cSJohn Levon else 1479efe51d0cSJohn Levon *res = rl; 1480efe51d0cSJohn Levon return true; 1481efe51d0cSJohn Levon } 1482efe51d0cSJohn Levon 1483efe51d0cSJohn Levon static bool get_rl_helper(struct expression *expr, int implied, struct range_list **res) 1484efe51d0cSJohn Levon { 1485efe51d0cSJohn Levon struct range_list *rl = NULL; 1486efe51d0cSJohn Levon sval_t sval = {}; 1487efe51d0cSJohn Levon int recurse_cnt = 0; 1488efe51d0cSJohn Levon 1489efe51d0cSJohn Levon if (get_value(expr, &sval)) { 1490efe51d0cSJohn Levon *res = alloc_rl(sval, sval); 1491efe51d0cSJohn Levon return true; 1492efe51d0cSJohn Levon } 1493efe51d0cSJohn Levon 1494efe51d0cSJohn Levon if (!get_rl_sval(expr, implied, &recurse_cnt, &rl, &sval)) 1495efe51d0cSJohn Levon return false; 1496efe51d0cSJohn Levon 1497efe51d0cSJohn Levon if (sval.type) 1498efe51d0cSJohn Levon *res = alloc_rl(sval, sval); 1499efe51d0cSJohn Levon else 1500efe51d0cSJohn Levon *res = rl; 1501efe51d0cSJohn Levon return true; 15021f5207b7SJohn Levon } 15031f5207b7SJohn Levon 15041f5207b7SJohn Levon struct { 15051f5207b7SJohn Levon struct expression *expr; 1506efe51d0cSJohn Levon sval_t sval; 15071f5207b7SJohn Levon } cached_results[24]; 15081f5207b7SJohn Levon static int cache_idx; 15091f5207b7SJohn Levon 15101f5207b7SJohn Levon void clear_math_cache(void) 15111f5207b7SJohn Levon { 15121f5207b7SJohn Levon memset(cached_results, 0, sizeof(cached_results)); 15131f5207b7SJohn Levon } 15141f5207b7SJohn Levon 1515*c85f09ccSJohn Levon void set_fast_math_only(void) 1516*c85f09ccSJohn Levon { 1517*c85f09ccSJohn Levon fast_math_only++; 1518*c85f09ccSJohn Levon } 1519*c85f09ccSJohn Levon 1520*c85f09ccSJohn Levon void clear_fast_math_only(void) 1521*c85f09ccSJohn Levon { 1522*c85f09ccSJohn Levon fast_math_only--; 1523*c85f09ccSJohn Levon } 1524*c85f09ccSJohn Levon 1525efe51d0cSJohn Levon /* 1526efe51d0cSJohn Levon * Don't cache EXPR_VALUE because values are fast already. 1527efe51d0cSJohn Levon * 1528efe51d0cSJohn Levon */ 1529efe51d0cSJohn Levon static bool get_value_literal(struct expression *expr, sval_t *res_sval) 1530efe51d0cSJohn Levon { 1531efe51d0cSJohn Levon struct expression *tmp; 1532efe51d0cSJohn Levon int recurse_cnt = 0; 1533efe51d0cSJohn Levon 1534efe51d0cSJohn Levon tmp = strip_expr(expr); 1535efe51d0cSJohn Levon if (!tmp || tmp->type != EXPR_VALUE) 1536efe51d0cSJohn Levon return false; 1537efe51d0cSJohn Levon 1538efe51d0cSJohn Levon return get_rl_sval(expr, RL_EXACT, &recurse_cnt, NULL, res_sval); 1539efe51d0cSJohn Levon } 1540efe51d0cSJohn Levon 15411f5207b7SJohn Levon /* returns 1 if it can get a value literal or else returns 0 */ 1542efe51d0cSJohn Levon int get_value(struct expression *expr, sval_t *res_sval) 15431f5207b7SJohn Levon { 15441f5207b7SJohn Levon struct range_list *(*orig_custom_fn)(struct expression *expr); 15451f5207b7SJohn Levon int recurse_cnt = 0; 1546efe51d0cSJohn Levon sval_t sval = {}; 15471f5207b7SJohn Levon int i; 15481f5207b7SJohn Levon 1549efe51d0cSJohn Levon if (get_value_literal(expr, res_sval)) 1550efe51d0cSJohn Levon return 1; 1551efe51d0cSJohn Levon 15521f5207b7SJohn Levon /* 15531f5207b7SJohn Levon * This only handles RL_EXACT because other expr statements can be 15541f5207b7SJohn Levon * different at different points. Like the list iterator, for example. 15551f5207b7SJohn Levon */ 15561f5207b7SJohn Levon for (i = 0; i < ARRAY_SIZE(cached_results); i++) { 1557efe51d0cSJohn Levon if (expr == cached_results[i].expr) { 1558efe51d0cSJohn Levon if (cached_results[i].sval.type) { 1559efe51d0cSJohn Levon *res_sval = cached_results[i].sval; 1560efe51d0cSJohn Levon return true; 1561efe51d0cSJohn Levon } 1562efe51d0cSJohn Levon return false; 1563efe51d0cSJohn Levon } 15641f5207b7SJohn Levon } 15651f5207b7SJohn Levon 15661f5207b7SJohn Levon orig_custom_fn = custom_handle_variable; 15671f5207b7SJohn Levon custom_handle_variable = NULL; 1568efe51d0cSJohn Levon get_rl_sval(expr, RL_EXACT, &recurse_cnt, NULL, &sval); 1569efe51d0cSJohn Levon 15701f5207b7SJohn Levon custom_handle_variable = orig_custom_fn; 15711f5207b7SJohn Levon 15721f5207b7SJohn Levon cached_results[cache_idx].expr = expr; 1573efe51d0cSJohn Levon cached_results[cache_idx].sval = sval; 15741f5207b7SJohn Levon cache_idx = (cache_idx + 1) % ARRAY_SIZE(cached_results); 15751f5207b7SJohn Levon 1576efe51d0cSJohn Levon if (!sval.type) 15771f5207b7SJohn Levon return 0; 15781f5207b7SJohn Levon 1579efe51d0cSJohn Levon *res_sval = sval; 15801f5207b7SJohn Levon return 1; 15811f5207b7SJohn Levon } 15821f5207b7SJohn Levon 1583efe51d0cSJohn Levon static bool get_implied_value_internal(struct expression *expr, int *recurse_cnt, sval_t *res_sval) 15841f5207b7SJohn Levon { 15851f5207b7SJohn Levon struct range_list *rl; 15861f5207b7SJohn Levon 1587efe51d0cSJohn Levon res_sval->type = NULL; 1588efe51d0cSJohn Levon 1589efe51d0cSJohn Levon if (!get_rl_sval(expr, RL_IMPLIED, recurse_cnt, &rl, res_sval)) 1590efe51d0cSJohn Levon return false; 1591efe51d0cSJohn Levon if (!res_sval->type && !rl_to_sval(rl, res_sval)) 1592efe51d0cSJohn Levon return false; 1593efe51d0cSJohn Levon return true; 15941f5207b7SJohn Levon } 15951f5207b7SJohn Levon 15961f5207b7SJohn Levon int get_implied_value(struct expression *expr, sval_t *sval) 15971f5207b7SJohn Levon { 15981f5207b7SJohn Levon struct range_list *rl; 15991f5207b7SJohn Levon 1600efe51d0cSJohn Levon if (!get_rl_helper(expr, RL_IMPLIED, &rl) || 1601efe51d0cSJohn Levon !rl_to_sval(rl, sval)) 16021f5207b7SJohn Levon return 0; 16031f5207b7SJohn Levon return 1; 16041f5207b7SJohn Levon } 16051f5207b7SJohn Levon 16061f5207b7SJohn Levon int get_implied_min(struct expression *expr, sval_t *sval) 16071f5207b7SJohn Levon { 16081f5207b7SJohn Levon struct range_list *rl; 16091f5207b7SJohn Levon 1610efe51d0cSJohn Levon if (!get_rl_helper(expr, RL_IMPLIED, &rl) || !rl) 16111f5207b7SJohn Levon return 0; 16121f5207b7SJohn Levon *sval = rl_min(rl); 16131f5207b7SJohn Levon return 1; 16141f5207b7SJohn Levon } 16151f5207b7SJohn Levon 16161f5207b7SJohn Levon int get_implied_max(struct expression *expr, sval_t *sval) 16171f5207b7SJohn Levon { 16181f5207b7SJohn Levon struct range_list *rl; 16191f5207b7SJohn Levon 1620efe51d0cSJohn Levon if (!get_rl_helper(expr, RL_IMPLIED, &rl) || !rl) 16211f5207b7SJohn Levon return 0; 16221f5207b7SJohn Levon *sval = rl_max(rl); 16231f5207b7SJohn Levon return 1; 16241f5207b7SJohn Levon } 16251f5207b7SJohn Levon 16261f5207b7SJohn Levon int get_implied_rl(struct expression *expr, struct range_list **rl) 16271f5207b7SJohn Levon { 1628efe51d0cSJohn Levon if (!get_rl_helper(expr, RL_IMPLIED, rl) || !*rl) 1629efe51d0cSJohn Levon return 0; 1630efe51d0cSJohn Levon return 1; 16311f5207b7SJohn Levon } 16321f5207b7SJohn Levon 16331f5207b7SJohn Levon static int get_absolute_rl_internal(struct expression *expr, struct range_list **rl, int *recurse_cnt) 16341f5207b7SJohn Levon { 1635efe51d0cSJohn Levon *rl = NULL; 1636efe51d0cSJohn Levon get_rl_internal(expr, RL_ABSOLUTE, recurse_cnt, rl); 16371f5207b7SJohn Levon if (!*rl) 16381f5207b7SJohn Levon *rl = alloc_whole_rl(get_type(expr)); 16391f5207b7SJohn Levon return 1; 16401f5207b7SJohn Levon } 16411f5207b7SJohn Levon 16421f5207b7SJohn Levon int get_absolute_rl(struct expression *expr, struct range_list **rl) 16431f5207b7SJohn Levon { 1644efe51d0cSJohn Levon *rl = NULL; 1645efe51d0cSJohn Levon get_rl_helper(expr, RL_ABSOLUTE, rl); 16461f5207b7SJohn Levon if (!*rl) 16471f5207b7SJohn Levon *rl = alloc_whole_rl(get_type(expr)); 16481f5207b7SJohn Levon return 1; 16491f5207b7SJohn Levon } 16501f5207b7SJohn Levon 16511f5207b7SJohn Levon int get_real_absolute_rl(struct expression *expr, struct range_list **rl) 16521f5207b7SJohn Levon { 1653efe51d0cSJohn Levon *rl = NULL; 1654efe51d0cSJohn Levon get_rl_helper(expr, RL_REAL_ABSOLUTE, rl); 16551f5207b7SJohn Levon if (!*rl) 16561f5207b7SJohn Levon *rl = alloc_whole_rl(get_type(expr)); 16571f5207b7SJohn Levon return 1; 16581f5207b7SJohn Levon } 16591f5207b7SJohn Levon 16601f5207b7SJohn Levon int custom_get_absolute_rl(struct expression *expr, 16611f5207b7SJohn Levon struct range_list *(*fn)(struct expression *expr), 16621f5207b7SJohn Levon struct range_list **rl) 16631f5207b7SJohn Levon { 1664efe51d0cSJohn Levon int ret; 16651f5207b7SJohn Levon 16661f5207b7SJohn Levon *rl = NULL; 16671f5207b7SJohn Levon custom_handle_variable = fn; 1668efe51d0cSJohn Levon ret = get_rl_helper(expr, RL_REAL_ABSOLUTE, rl); 16691f5207b7SJohn Levon custom_handle_variable = NULL; 1670efe51d0cSJohn Levon return ret; 16711f5207b7SJohn Levon } 16721f5207b7SJohn Levon 16731f5207b7SJohn Levon int get_implied_rl_var_sym(const char *var, struct symbol *sym, struct range_list **rl) 16741f5207b7SJohn Levon { 16751f5207b7SJohn Levon struct smatch_state *state; 16761f5207b7SJohn Levon 16771f5207b7SJohn Levon state = get_state(SMATCH_EXTRA, var, sym); 16781f5207b7SJohn Levon *rl = estate_rl(state); 16791f5207b7SJohn Levon if (*rl) 16801f5207b7SJohn Levon return 1; 16811f5207b7SJohn Levon return 0; 16821f5207b7SJohn Levon } 16831f5207b7SJohn Levon 16841f5207b7SJohn Levon int get_hard_max(struct expression *expr, sval_t *sval) 16851f5207b7SJohn Levon { 16861f5207b7SJohn Levon struct range_list *rl; 16871f5207b7SJohn Levon 1688efe51d0cSJohn Levon if (!get_rl_helper(expr, RL_HARD, &rl) || !rl) 16891f5207b7SJohn Levon return 0; 16901f5207b7SJohn Levon *sval = rl_max(rl); 16911f5207b7SJohn Levon return 1; 16921f5207b7SJohn Levon } 16931f5207b7SJohn Levon 16941f5207b7SJohn Levon int get_fuzzy_min(struct expression *expr, sval_t *sval) 16951f5207b7SJohn Levon { 16961f5207b7SJohn Levon struct range_list *rl; 16971f5207b7SJohn Levon sval_t tmp; 16981f5207b7SJohn Levon 1699efe51d0cSJohn Levon if (!get_rl_helper(expr, RL_FUZZY, &rl) || !rl) 17001f5207b7SJohn Levon return 0; 17011f5207b7SJohn Levon tmp = rl_min(rl); 17021f5207b7SJohn Levon if (sval_is_negative(tmp) && sval_is_min(tmp)) 17031f5207b7SJohn Levon return 0; 17041f5207b7SJohn Levon *sval = tmp; 17051f5207b7SJohn Levon return 1; 17061f5207b7SJohn Levon } 17071f5207b7SJohn Levon 17081f5207b7SJohn Levon int get_fuzzy_max(struct expression *expr, sval_t *sval) 17091f5207b7SJohn Levon { 17101f5207b7SJohn Levon struct range_list *rl; 17111f5207b7SJohn Levon sval_t max; 17121f5207b7SJohn Levon 1713efe51d0cSJohn Levon if (!get_rl_helper(expr, RL_FUZZY, &rl) || !rl) 17141f5207b7SJohn Levon return 0; 17151f5207b7SJohn Levon max = rl_max(rl); 17161f5207b7SJohn Levon if (max.uvalue > INT_MAX - 10000) 17171f5207b7SJohn Levon return 0; 17181f5207b7SJohn Levon *sval = max; 17191f5207b7SJohn Levon return 1; 17201f5207b7SJohn Levon } 17211f5207b7SJohn Levon 17221f5207b7SJohn Levon int get_absolute_min(struct expression *expr, sval_t *sval) 17231f5207b7SJohn Levon { 17241f5207b7SJohn Levon struct range_list *rl; 17251f5207b7SJohn Levon struct symbol *type; 17261f5207b7SJohn Levon 17271f5207b7SJohn Levon type = get_type(expr); 17281f5207b7SJohn Levon if (!type) 17291f5207b7SJohn Levon type = &llong_ctype; // FIXME: this is wrong but places assume get type can't fail. 1730efe51d0cSJohn Levon rl = NULL; 1731efe51d0cSJohn Levon get_rl_helper(expr, RL_REAL_ABSOLUTE, &rl); 17321f5207b7SJohn Levon if (rl) 17331f5207b7SJohn Levon *sval = rl_min(rl); 17341f5207b7SJohn Levon else 17351f5207b7SJohn Levon *sval = sval_type_min(type); 17361f5207b7SJohn Levon 17371f5207b7SJohn Levon if (sval_cmp(*sval, sval_type_min(type)) < 0) 17381f5207b7SJohn Levon *sval = sval_type_min(type); 17391f5207b7SJohn Levon return 1; 17401f5207b7SJohn Levon } 17411f5207b7SJohn Levon 17421f5207b7SJohn Levon int get_absolute_max(struct expression *expr, sval_t *sval) 17431f5207b7SJohn Levon { 17441f5207b7SJohn Levon struct range_list *rl; 17451f5207b7SJohn Levon struct symbol *type; 17461f5207b7SJohn Levon 17471f5207b7SJohn Levon type = get_type(expr); 17481f5207b7SJohn Levon if (!type) 17491f5207b7SJohn Levon type = &llong_ctype; 1750efe51d0cSJohn Levon rl = NULL; 1751efe51d0cSJohn Levon get_rl_helper(expr, RL_REAL_ABSOLUTE, &rl); 17521f5207b7SJohn Levon if (rl) 17531f5207b7SJohn Levon *sval = rl_max(rl); 17541f5207b7SJohn Levon else 17551f5207b7SJohn Levon *sval = sval_type_max(type); 17561f5207b7SJohn Levon 17571f5207b7SJohn Levon if (sval_cmp(sval_type_max(type), *sval) < 0) 17581f5207b7SJohn Levon *sval = sval_type_max(type); 17591f5207b7SJohn Levon return 1; 17601f5207b7SJohn Levon } 17611f5207b7SJohn Levon 17621f5207b7SJohn Levon int known_condition_true(struct expression *expr) 17631f5207b7SJohn Levon { 17641f5207b7SJohn Levon sval_t tmp; 17651f5207b7SJohn Levon 17661f5207b7SJohn Levon if (!expr) 17671f5207b7SJohn Levon return 0; 17681f5207b7SJohn Levon 1769*c85f09ccSJohn Levon if (__inline_fn && get_param_num(expr) >= 0) { 1770*c85f09ccSJohn Levon if (get_implied_value(expr, &tmp) && tmp.value) 1771*c85f09ccSJohn Levon return 1; 1772*c85f09ccSJohn Levon return 0; 1773*c85f09ccSJohn Levon } 1774*c85f09ccSJohn Levon 17751f5207b7SJohn Levon if (get_value(expr, &tmp) && tmp.value) 17761f5207b7SJohn Levon return 1; 17771f5207b7SJohn Levon 17781f5207b7SJohn Levon return 0; 17791f5207b7SJohn Levon } 17801f5207b7SJohn Levon 17811f5207b7SJohn Levon int known_condition_false(struct expression *expr) 17821f5207b7SJohn Levon { 1783*c85f09ccSJohn Levon sval_t tmp; 1784*c85f09ccSJohn Levon 17851f5207b7SJohn Levon if (!expr) 17861f5207b7SJohn Levon return 0; 17871f5207b7SJohn Levon 1788*c85f09ccSJohn Levon if (__inline_fn && get_param_num(expr) >= 0) { 1789*c85f09ccSJohn Levon if (get_implied_value(expr, &tmp) && tmp.value == 0) 1790*c85f09ccSJohn Levon return 1; 1791*c85f09ccSJohn Levon return 0; 1792*c85f09ccSJohn Levon } 1793*c85f09ccSJohn Levon 1794*c85f09ccSJohn Levon if (expr_is_zero(expr)) 17951f5207b7SJohn Levon return 1; 17961f5207b7SJohn Levon 17971f5207b7SJohn Levon return 0; 17981f5207b7SJohn Levon } 17991f5207b7SJohn Levon 18001f5207b7SJohn Levon int implied_condition_true(struct expression *expr) 18011f5207b7SJohn Levon { 18021f5207b7SJohn Levon sval_t tmp; 18031f5207b7SJohn Levon 18041f5207b7SJohn Levon if (!expr) 18051f5207b7SJohn Levon return 0; 18061f5207b7SJohn Levon 18071f5207b7SJohn Levon if (known_condition_true(expr)) 18081f5207b7SJohn Levon return 1; 18091f5207b7SJohn Levon if (get_implied_value(expr, &tmp) && tmp.value) 18101f5207b7SJohn Levon return 1; 18111f5207b7SJohn Levon 18121f5207b7SJohn Levon if (expr->type == EXPR_POSTOP) 18131f5207b7SJohn Levon return implied_condition_true(expr->unop); 18141f5207b7SJohn Levon 18151f5207b7SJohn Levon if (expr->type == EXPR_PREOP && expr->op == SPECIAL_DECREMENT) 18161f5207b7SJohn Levon return implied_not_equal(expr->unop, 1); 18171f5207b7SJohn Levon if (expr->type == EXPR_PREOP && expr->op == SPECIAL_INCREMENT) 18181f5207b7SJohn Levon return implied_not_equal(expr->unop, -1); 18191f5207b7SJohn Levon 18201f5207b7SJohn Levon expr = strip_expr(expr); 18211f5207b7SJohn Levon switch (expr->type) { 18221f5207b7SJohn Levon case EXPR_COMPARE: 18231f5207b7SJohn Levon if (do_comparison(expr) == 1) 18241f5207b7SJohn Levon return 1; 18251f5207b7SJohn Levon break; 18261f5207b7SJohn Levon case EXPR_PREOP: 18271f5207b7SJohn Levon if (expr->op == '!') { 18281f5207b7SJohn Levon if (implied_condition_false(expr->unop)) 18291f5207b7SJohn Levon return 1; 18301f5207b7SJohn Levon break; 18311f5207b7SJohn Levon } 18321f5207b7SJohn Levon break; 18331f5207b7SJohn Levon default: 18341f5207b7SJohn Levon if (implied_not_equal(expr, 0) == 1) 18351f5207b7SJohn Levon return 1; 18361f5207b7SJohn Levon break; 18371f5207b7SJohn Levon } 18381f5207b7SJohn Levon return 0; 18391f5207b7SJohn Levon } 18401f5207b7SJohn Levon 18411f5207b7SJohn Levon int implied_condition_false(struct expression *expr) 18421f5207b7SJohn Levon { 18431f5207b7SJohn Levon struct expression *tmp; 18441f5207b7SJohn Levon sval_t sval; 18451f5207b7SJohn Levon 18461f5207b7SJohn Levon if (!expr) 18471f5207b7SJohn Levon return 0; 18481f5207b7SJohn Levon 18491f5207b7SJohn Levon if (known_condition_false(expr)) 18501f5207b7SJohn Levon return 1; 18511f5207b7SJohn Levon 18521f5207b7SJohn Levon switch (expr->type) { 18531f5207b7SJohn Levon case EXPR_COMPARE: 18541f5207b7SJohn Levon if (do_comparison(expr) == 2) 18551f5207b7SJohn Levon return 1; 18561f5207b7SJohn Levon case EXPR_PREOP: 18571f5207b7SJohn Levon if (expr->op == '!') { 18581f5207b7SJohn Levon if (implied_condition_true(expr->unop)) 18591f5207b7SJohn Levon return 1; 18601f5207b7SJohn Levon break; 18611f5207b7SJohn Levon } 18621f5207b7SJohn Levon tmp = strip_expr(expr); 18631f5207b7SJohn Levon if (tmp != expr) 18641f5207b7SJohn Levon return implied_condition_false(tmp); 18651f5207b7SJohn Levon break; 18661f5207b7SJohn Levon default: 18671f5207b7SJohn Levon if (get_implied_value(expr, &sval) && sval.value == 0) 18681f5207b7SJohn Levon return 1; 18691f5207b7SJohn Levon break; 18701f5207b7SJohn Levon } 18711f5207b7SJohn Levon return 0; 18721f5207b7SJohn Levon } 18731f5207b7SJohn Levon 18741f5207b7SJohn Levon 1875