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 23*efe51d0cSJohn Levon static bool get_rl_sval(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *sval_res); 24*efe51d0cSJohn Levon static bool get_rl_internal(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res); 25*efe51d0cSJohn 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 28*efe51d0cSJohn 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 341f5207b7SJohn Levon struct range_list *rl_zero(void) 351f5207b7SJohn Levon { 361f5207b7SJohn Levon static struct range_list *zero_perm; 371f5207b7SJohn Levon 381f5207b7SJohn Levon if (!zero_perm) 391f5207b7SJohn Levon zero_perm = clone_rl_permanent(alloc_rl(zero, zero)); 401f5207b7SJohn Levon return zero_perm; 411f5207b7SJohn Levon } 421f5207b7SJohn Levon 431f5207b7SJohn Levon struct range_list *rl_one(void) 441f5207b7SJohn Levon { 451f5207b7SJohn Levon static struct range_list *one_perm; 461f5207b7SJohn Levon 471f5207b7SJohn Levon if (!one_perm) 481f5207b7SJohn Levon one_perm = clone_rl_permanent(alloc_rl(one, one)); 491f5207b7SJohn Levon 501f5207b7SJohn Levon return one_perm; 511f5207b7SJohn Levon } 521f5207b7SJohn Levon 531f5207b7SJohn Levon enum { 541f5207b7SJohn Levon RL_EXACT, 551f5207b7SJohn Levon RL_HARD, 561f5207b7SJohn Levon RL_FUZZY, 571f5207b7SJohn Levon RL_IMPLIED, 581f5207b7SJohn Levon RL_ABSOLUTE, 591f5207b7SJohn Levon RL_REAL_ABSOLUTE, 601f5207b7SJohn Levon }; 611f5207b7SJohn Levon 62*efe51d0cSJohn Levon static bool last_stmt_rl(struct statement *stmt, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval) 631f5207b7SJohn Levon { 641f5207b7SJohn Levon struct expression *expr; 651f5207b7SJohn Levon 661f5207b7SJohn Levon if (!stmt) 67*efe51d0cSJohn Levon return false; 681f5207b7SJohn Levon 691f5207b7SJohn Levon stmt = last_ptr_list((struct ptr_list *)stmt->stmts); 701f5207b7SJohn Levon if (stmt->type == STMT_LABEL) { 711f5207b7SJohn Levon if (stmt->label_statement && 721f5207b7SJohn Levon stmt->label_statement->type == STMT_EXPRESSION) 731f5207b7SJohn Levon expr = stmt->label_statement->expression; 741f5207b7SJohn Levon else 75*efe51d0cSJohn Levon return false; 761f5207b7SJohn Levon } else if (stmt->type == STMT_EXPRESSION) { 771f5207b7SJohn Levon expr = stmt->expression; 781f5207b7SJohn Levon } else { 79*efe51d0cSJohn Levon return false; 801f5207b7SJohn Levon } 81*efe51d0cSJohn Levon return get_rl_sval(expr, implied, recurse_cnt, res, res_sval); 821f5207b7SJohn Levon } 831f5207b7SJohn Levon 84*efe51d0cSJohn Levon static bool handle_expression_statement_rl(struct expression *expr, int implied, 85*efe51d0cSJohn Levon int *recurse_cnt, struct range_list **res, sval_t *res_sval) 861f5207b7SJohn Levon { 87*efe51d0cSJohn Levon return last_stmt_rl(get_expression_statement(expr), implied, recurse_cnt, res, res_sval); 881f5207b7SJohn Levon } 891f5207b7SJohn Levon 90*efe51d0cSJohn Levon static bool handle_address(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval) 911f5207b7SJohn Levon { 921f5207b7SJohn Levon struct range_list *rl; 93*efe51d0cSJohn Levon static int recursed; 941f5207b7SJohn Levon sval_t sval; 951f5207b7SJohn Levon 96*efe51d0cSJohn Levon if (recursed > 10) 97*efe51d0cSJohn Levon return false; 98*efe51d0cSJohn Levon if (implied == RL_EXACT) 99*efe51d0cSJohn Levon return false; 100*efe51d0cSJohn Levon 101*efe51d0cSJohn Levon if (custom_handle_variable) { 102*efe51d0cSJohn Levon rl = custom_handle_variable(expr); 103*efe51d0cSJohn Levon if (rl) { 104*efe51d0cSJohn Levon *res = rl; 105*efe51d0cSJohn Levon return true; 106*efe51d0cSJohn Levon } 107*efe51d0cSJohn Levon } 108*efe51d0cSJohn Levon 109*efe51d0cSJohn Levon recursed++; 110*efe51d0cSJohn Levon if (get_mtag_sval(expr, &sval)) { 111*efe51d0cSJohn Levon recursed--; 112*efe51d0cSJohn Levon *res_sval = sval; 113*efe51d0cSJohn Levon return true; 114*efe51d0cSJohn Levon } 115*efe51d0cSJohn Levon 116*efe51d0cSJohn Levon if (get_address_rl(expr, res)) { 117*efe51d0cSJohn Levon recursed--; 118*efe51d0cSJohn Levon return true; 119*efe51d0cSJohn Levon } 120*efe51d0cSJohn Levon recursed--; 121*efe51d0cSJohn Levon return 0; 122*efe51d0cSJohn Levon } 123*efe51d0cSJohn Levon 124*efe51d0cSJohn Levon static bool handle_ampersand_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval) 125*efe51d0cSJohn Levon { 126*efe51d0cSJohn Levon return handle_address(expr, implied, recurse_cnt, res, res_sval); 1271f5207b7SJohn Levon } 1281f5207b7SJohn Levon 129*efe51d0cSJohn Levon static bool handle_negate_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval) 1301f5207b7SJohn Levon { 131*efe51d0cSJohn Levon if (known_condition_true(expr->unop)) { 132*efe51d0cSJohn Levon *res_sval = zero; 133*efe51d0cSJohn Levon return true; 134*efe51d0cSJohn Levon } 135*efe51d0cSJohn Levon if (known_condition_false(expr->unop)) { 136*efe51d0cSJohn Levon *res_sval = one; 137*efe51d0cSJohn Levon return true; 138*efe51d0cSJohn Levon } 1391f5207b7SJohn Levon 1401f5207b7SJohn Levon if (implied == RL_EXACT) 141*efe51d0cSJohn Levon return false; 1421f5207b7SJohn Levon 143*efe51d0cSJohn Levon if (implied_condition_true(expr->unop)) { 144*efe51d0cSJohn Levon *res_sval = zero; 145*efe51d0cSJohn Levon return true; 146*efe51d0cSJohn Levon } 147*efe51d0cSJohn Levon if (implied_condition_false(expr->unop)) { 148*efe51d0cSJohn Levon *res_sval = one; 149*efe51d0cSJohn Levon return true; 150*efe51d0cSJohn Levon } 151*efe51d0cSJohn Levon 152*efe51d0cSJohn Levon *res = alloc_rl(zero, one); 153*efe51d0cSJohn Levon return true; 1541f5207b7SJohn Levon } 1551f5207b7SJohn Levon 156*efe51d0cSJohn Levon static bool handle_bitwise_negate(struct expression *expr, int implied, int *recurse_cnt, sval_t *res_sval) 1571f5207b7SJohn Levon { 1581f5207b7SJohn Levon struct range_list *rl; 159*efe51d0cSJohn Levon sval_t sval = {}; 1601f5207b7SJohn Levon 161*efe51d0cSJohn Levon if (!get_rl_sval(expr->unop, implied, recurse_cnt, &rl, &sval)) 162*efe51d0cSJohn Levon return false; 163*efe51d0cSJohn Levon if (!sval.type && !rl_to_sval(rl, &sval)) 164*efe51d0cSJohn Levon return false; 1651f5207b7SJohn Levon sval = sval_preop(sval, '~'); 1661f5207b7SJohn Levon sval_cast(get_type(expr->unop), sval); 167*efe51d0cSJohn Levon *res_sval = sval; 168*efe51d0cSJohn Levon return true; 1691f5207b7SJohn Levon } 1701f5207b7SJohn Levon 171*efe51d0cSJohn Levon static bool untrusted_type_min(struct expression *expr) 1721f5207b7SJohn Levon { 1731f5207b7SJohn Levon struct range_list *rl; 1741f5207b7SJohn Levon 175*efe51d0cSJohn Levon rl = var_user_rl(expr); 176*efe51d0cSJohn Levon return rl && sval_is_min(rl_min(rl)); 1771f5207b7SJohn Levon } 1781f5207b7SJohn Levon 179*efe51d0cSJohn Levon static bool handle_minus_preop(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval) 180*efe51d0cSJohn Levon { 181*efe51d0cSJohn Levon struct range_list *rl; 182*efe51d0cSJohn Levon struct range_list *ret = NULL; 183*efe51d0cSJohn Levon struct symbol *type; 184*efe51d0cSJohn Levon sval_t neg_one = { 0 }; 185*efe51d0cSJohn Levon sval_t zero = { 0 }; 186*efe51d0cSJohn Levon sval_t sval = {}; 187*efe51d0cSJohn Levon 188*efe51d0cSJohn Levon neg_one.value = -1; 189*efe51d0cSJohn Levon zero.value = 0; 190*efe51d0cSJohn Levon 191*efe51d0cSJohn Levon if (!get_rl_sval(expr->unop, implied, recurse_cnt, &rl, &sval)) 192*efe51d0cSJohn Levon return false; 193*efe51d0cSJohn Levon if (sval.type) { 194*efe51d0cSJohn Levon *res_sval = sval_preop(sval, '-'); 195*efe51d0cSJohn Levon return true; 196*efe51d0cSJohn Levon } 197*efe51d0cSJohn Levon /* 198*efe51d0cSJohn Levon * One complication is that -INT_MIN is still INT_MIN because of integer 199*efe51d0cSJohn Levon * overflows... But how many times do we set a time out to INT_MIN? 200*efe51d0cSJohn Levon * So normally when we call abs() then it does return a positive value. 201*efe51d0cSJohn Levon * 202*efe51d0cSJohn Levon */ 203*efe51d0cSJohn Levon type = rl_type(rl); 204*efe51d0cSJohn Levon neg_one.type = zero.type = type; 205*efe51d0cSJohn Levon 206*efe51d0cSJohn Levon if (sval_is_negative(rl_min(rl))) { 207*efe51d0cSJohn Levon struct range_list *neg; 208*efe51d0cSJohn Levon struct data_range *drange; 209*efe51d0cSJohn Levon sval_t new_min, new_max; 210*efe51d0cSJohn Levon 211*efe51d0cSJohn Levon neg = alloc_rl(sval_type_min(type), neg_one); 212*efe51d0cSJohn Levon neg = rl_intersection(rl, neg); 213*efe51d0cSJohn Levon 214*efe51d0cSJohn Levon if (sval_is_min(rl_min(neg)) && !sval_is_min(rl_max(neg))) 215*efe51d0cSJohn Levon neg = remove_range(neg, sval_type_min(type), sval_type_min(type)); 216*efe51d0cSJohn Levon 217*efe51d0cSJohn Levon FOR_EACH_PTR(neg, drange) { 218*efe51d0cSJohn Levon new_min = drange->max; 219*efe51d0cSJohn Levon new_min.value = -new_min.value; 220*efe51d0cSJohn Levon new_max = drange->min; 221*efe51d0cSJohn Levon new_max.value = -new_max.value; 222*efe51d0cSJohn Levon add_range(&ret, new_min, new_max); 223*efe51d0cSJohn Levon } END_FOR_EACH_PTR(drange); 224*efe51d0cSJohn Levon 225*efe51d0cSJohn Levon if (untrusted_type_min(expr)) 226*efe51d0cSJohn Levon add_range(&ret, sval_type_min(type), sval_type_min(type)); 227*efe51d0cSJohn Levon } 228*efe51d0cSJohn Levon 229*efe51d0cSJohn Levon if (!sval_is_negative(rl_max(rl))) { 230*efe51d0cSJohn Levon struct range_list *pos; 231*efe51d0cSJohn Levon struct data_range *drange; 232*efe51d0cSJohn Levon sval_t new_min, new_max; 233*efe51d0cSJohn Levon 234*efe51d0cSJohn Levon pos = alloc_rl(zero, sval_type_max(type)); 235*efe51d0cSJohn Levon pos = rl_intersection(rl, pos); 236*efe51d0cSJohn Levon 237*efe51d0cSJohn Levon FOR_EACH_PTR(pos, drange) { 238*efe51d0cSJohn Levon new_min = drange->max; 239*efe51d0cSJohn Levon new_min.value = -new_min.value; 240*efe51d0cSJohn Levon new_max = drange->min; 241*efe51d0cSJohn Levon new_max.value = -new_max.value; 242*efe51d0cSJohn Levon add_range(&ret, new_min, new_max); 243*efe51d0cSJohn Levon } END_FOR_EACH_PTR(drange); 244*efe51d0cSJohn Levon } 245*efe51d0cSJohn Levon 246*efe51d0cSJohn Levon *res = ret; 247*efe51d0cSJohn Levon return true; 248*efe51d0cSJohn Levon } 249*efe51d0cSJohn Levon 250*efe51d0cSJohn Levon static bool handle_preop_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval) 2511f5207b7SJohn Levon { 2521f5207b7SJohn Levon switch (expr->op) { 2531f5207b7SJohn Levon case '&': 254*efe51d0cSJohn Levon return handle_ampersand_rl(expr, implied, recurse_cnt, res, res_sval); 2551f5207b7SJohn Levon case '!': 256*efe51d0cSJohn Levon return handle_negate_rl(expr, implied, recurse_cnt, res, res_sval); 2571f5207b7SJohn Levon case '~': 258*efe51d0cSJohn Levon return handle_bitwise_negate(expr, implied, recurse_cnt, res_sval); 2591f5207b7SJohn Levon case '-': 260*efe51d0cSJohn Levon return handle_minus_preop(expr, implied, recurse_cnt, res, res_sval); 2611f5207b7SJohn Levon case '*': 262*efe51d0cSJohn Levon return handle_variable(expr, implied, recurse_cnt, res, res_sval); 2631f5207b7SJohn Levon case '(': 264*efe51d0cSJohn Levon return handle_expression_statement_rl(expr, implied, recurse_cnt, res, res_sval); 2651f5207b7SJohn Levon default: 266*efe51d0cSJohn Levon return false; 2671f5207b7SJohn Levon } 2681f5207b7SJohn Levon } 2691f5207b7SJohn Levon 270*efe51d0cSJohn Levon static bool handle_divide_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res) 2711f5207b7SJohn Levon { 272*efe51d0cSJohn Levon struct range_list *left_rl = NULL; 273*efe51d0cSJohn Levon struct range_list *right_rl = NULL; 2741f5207b7SJohn Levon struct symbol *type; 2751f5207b7SJohn Levon 2761f5207b7SJohn Levon type = get_type(expr); 2771f5207b7SJohn Levon 278*efe51d0cSJohn Levon get_rl_internal(expr->left, implied, recurse_cnt, &left_rl); 2791f5207b7SJohn Levon left_rl = cast_rl(type, left_rl); 280*efe51d0cSJohn Levon get_rl_internal(expr->right, implied, recurse_cnt, &right_rl); 2811f5207b7SJohn Levon right_rl = cast_rl(type, right_rl); 2821f5207b7SJohn Levon 2831f5207b7SJohn Levon if (!left_rl || !right_rl) 284*efe51d0cSJohn Levon return false; 2851f5207b7SJohn Levon 2861f5207b7SJohn Levon if (implied != RL_REAL_ABSOLUTE) { 2871f5207b7SJohn Levon if (is_whole_rl(left_rl) || is_whole_rl(right_rl)) 288*efe51d0cSJohn Levon return false; 2891f5207b7SJohn Levon } 2901f5207b7SJohn Levon 291*efe51d0cSJohn Levon *res = rl_binop(left_rl, '/', right_rl); 292*efe51d0cSJohn Levon return true; 2931f5207b7SJohn Levon } 2941f5207b7SJohn Levon 2951f5207b7SJohn Levon static int handle_offset_subtraction(struct expression *expr) 2961f5207b7SJohn Levon { 2971f5207b7SJohn Levon struct expression *left, *right; 2981f5207b7SJohn Levon struct symbol *left_sym, *right_sym; 2991f5207b7SJohn Levon struct symbol *type; 3001f5207b7SJohn Levon int left_offset, right_offset; 3011f5207b7SJohn Levon 3021f5207b7SJohn Levon type = get_type(expr); 3031f5207b7SJohn Levon if (!type || type->type != SYM_PTR) 3041f5207b7SJohn Levon return -1; 3051f5207b7SJohn Levon type = get_real_base_type(type); 3061f5207b7SJohn Levon if (!type || (type_bits(type) != 8 && (type != &void_ctype))) 3071f5207b7SJohn Levon return -1; 3081f5207b7SJohn Levon 3091f5207b7SJohn Levon left = strip_expr(expr->left); 3101f5207b7SJohn Levon right = strip_expr(expr->right); 3111f5207b7SJohn Levon 3121f5207b7SJohn Levon if (left->type != EXPR_PREOP || left->op != '&') 3131f5207b7SJohn Levon return -1; 3141f5207b7SJohn Levon left = strip_expr(left->unop); 3151f5207b7SJohn Levon 3161f5207b7SJohn Levon left_sym = expr_to_sym(left); 3171f5207b7SJohn Levon right_sym = expr_to_sym(right); 3181f5207b7SJohn Levon if (!left_sym || left_sym != right_sym) 3191f5207b7SJohn Levon return -1; 3201f5207b7SJohn Levon 3211f5207b7SJohn Levon left_offset = get_member_offset_from_deref(left); 3221f5207b7SJohn Levon if (right->type == EXPR_SYMBOL) 3231f5207b7SJohn Levon right_offset = 0; 3241f5207b7SJohn Levon else { 3251f5207b7SJohn Levon if (right->type != EXPR_PREOP || right->op != '&') 3261f5207b7SJohn Levon return -1; 3271f5207b7SJohn Levon right = strip_expr(right->unop); 3281f5207b7SJohn Levon right_offset = get_member_offset_from_deref(right); 3291f5207b7SJohn Levon } 3301f5207b7SJohn Levon if (left_offset < 0 || right_offset < 0) 3311f5207b7SJohn Levon return -1; 3321f5207b7SJohn Levon 3331f5207b7SJohn Levon return left_offset - right_offset; 3341f5207b7SJohn Levon } 3351f5207b7SJohn Levon 336*efe51d0cSJohn Levon static bool handle_subtract_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res) 3371f5207b7SJohn Levon { 3381f5207b7SJohn Levon struct symbol *type; 3391f5207b7SJohn Levon struct range_list *left_orig, *right_orig; 3401f5207b7SJohn Levon struct range_list *left_rl, *right_rl; 341*efe51d0cSJohn Levon sval_t min, max, tmp; 3421f5207b7SJohn Levon int comparison; 3431f5207b7SJohn Levon int offset; 3441f5207b7SJohn Levon 3451f5207b7SJohn Levon type = get_type(expr); 3461f5207b7SJohn Levon 3471f5207b7SJohn Levon offset = handle_offset_subtraction(expr); 3481f5207b7SJohn Levon if (offset >= 0) { 3491f5207b7SJohn Levon tmp.type = type; 3501f5207b7SJohn Levon tmp.value = offset; 3511f5207b7SJohn Levon 352*efe51d0cSJohn Levon *res = alloc_rl(tmp, tmp); 353*efe51d0cSJohn Levon return true; 3541f5207b7SJohn Levon } 3551f5207b7SJohn Levon 3561f5207b7SJohn Levon comparison = get_comparison(expr->left, expr->right); 3571f5207b7SJohn Levon 358*efe51d0cSJohn Levon left_orig = NULL; 359*efe51d0cSJohn Levon get_rl_internal(expr->left, implied, recurse_cnt, &left_orig); 3601f5207b7SJohn Levon left_rl = cast_rl(type, left_orig); 361*efe51d0cSJohn Levon right_orig = NULL; 362*efe51d0cSJohn Levon get_rl_internal(expr->right, implied, recurse_cnt, &right_orig); 3631f5207b7SJohn Levon right_rl = cast_rl(type, right_orig); 3641f5207b7SJohn Levon 3651f5207b7SJohn Levon if ((!left_rl || !right_rl) && 3661f5207b7SJohn Levon (implied == RL_EXACT || implied == RL_HARD || implied == RL_FUZZY)) 367*efe51d0cSJohn Levon return false; 3681f5207b7SJohn Levon 3691f5207b7SJohn Levon if (!left_rl) 3701f5207b7SJohn Levon left_rl = alloc_whole_rl(type); 3711f5207b7SJohn Levon if (!right_rl) 3721f5207b7SJohn Levon right_rl = alloc_whole_rl(type); 3731f5207b7SJohn Levon 3741f5207b7SJohn Levon /* negative values complicate everything fix this later */ 3751f5207b7SJohn Levon if (sval_is_negative(rl_min(right_rl))) 376*efe51d0cSJohn Levon return false; 3771f5207b7SJohn Levon max = rl_max(left_rl); 3781f5207b7SJohn Levon min = sval_type_min(type); 3791f5207b7SJohn Levon 3801f5207b7SJohn Levon switch (comparison) { 3811f5207b7SJohn Levon case '>': 3821f5207b7SJohn Levon case SPECIAL_UNSIGNED_GT: 3831f5207b7SJohn Levon min = sval_type_val(type, 1); 3841f5207b7SJohn Levon max = rl_max(left_rl); 3851f5207b7SJohn Levon break; 3861f5207b7SJohn Levon case SPECIAL_GTE: 3871f5207b7SJohn Levon case SPECIAL_UNSIGNED_GTE: 3881f5207b7SJohn Levon min = sval_type_val(type, 0); 3891f5207b7SJohn Levon max = rl_max(left_rl); 3901f5207b7SJohn Levon break; 3911f5207b7SJohn Levon case SPECIAL_EQUAL: 3921f5207b7SJohn Levon min = sval_type_val(type, 0); 3931f5207b7SJohn Levon max = sval_type_val(type, 0); 3941f5207b7SJohn Levon break; 3951f5207b7SJohn Levon case '<': 3961f5207b7SJohn Levon case SPECIAL_UNSIGNED_LT: 3971f5207b7SJohn Levon max = sval_type_val(type, -1); 3981f5207b7SJohn Levon break; 3991f5207b7SJohn Levon case SPECIAL_LTE: 4001f5207b7SJohn Levon case SPECIAL_UNSIGNED_LTE: 4011f5207b7SJohn Levon max = sval_type_val(type, 0); 4021f5207b7SJohn Levon break; 4031f5207b7SJohn Levon default: 4041f5207b7SJohn Levon if (!left_orig || !right_orig) 405*efe51d0cSJohn Levon return false; 406*efe51d0cSJohn Levon *res = rl_binop(left_rl, '-', right_rl); 407*efe51d0cSJohn Levon return true; 4081f5207b7SJohn Levon } 4091f5207b7SJohn Levon 4101f5207b7SJohn Levon if (!sval_binop_overflows(rl_min(left_rl), '-', rl_max(right_rl))) { 4111f5207b7SJohn Levon tmp = sval_binop(rl_min(left_rl), '-', rl_max(right_rl)); 4121f5207b7SJohn Levon if (sval_cmp(tmp, min) > 0) 4131f5207b7SJohn Levon min = tmp; 4141f5207b7SJohn Levon } 4151f5207b7SJohn Levon 4161f5207b7SJohn Levon if (!sval_is_max(rl_max(left_rl))) { 4171f5207b7SJohn Levon tmp = sval_binop(rl_max(left_rl), '-', rl_min(right_rl)); 4181f5207b7SJohn Levon if (sval_cmp(tmp, max) < 0) 4191f5207b7SJohn Levon max = tmp; 4201f5207b7SJohn Levon } 4211f5207b7SJohn Levon 4221f5207b7SJohn Levon if (sval_is_min(min) && sval_is_max(max)) 423*efe51d0cSJohn Levon return false; 4241f5207b7SJohn Levon 425*efe51d0cSJohn Levon *res = cast_rl(type, alloc_rl(min, max)); 426*efe51d0cSJohn Levon return true; 4271f5207b7SJohn Levon } 4281f5207b7SJohn Levon 429*efe51d0cSJohn Levon static bool handle_mod_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res) 4301f5207b7SJohn Levon { 4311f5207b7SJohn Levon struct range_list *rl; 4321f5207b7SJohn Levon sval_t left, right, sval; 4331f5207b7SJohn Levon 4341f5207b7SJohn Levon if (implied == RL_EXACT) { 4351f5207b7SJohn Levon if (!get_implied_value(expr->right, &right)) 436*efe51d0cSJohn Levon return false; 4371f5207b7SJohn Levon if (!get_implied_value(expr->left, &left)) 438*efe51d0cSJohn Levon return false; 4391f5207b7SJohn Levon sval = sval_binop(left, '%', right); 440*efe51d0cSJohn Levon *res = alloc_rl(sval, sval); 441*efe51d0cSJohn Levon return true; 4421f5207b7SJohn Levon } 4431f5207b7SJohn Levon /* if we can't figure out the right side it's probably hopeless */ 444*efe51d0cSJohn Levon if (!get_implied_value_internal(expr->right, recurse_cnt, &right)) 445*efe51d0cSJohn Levon return false; 4461f5207b7SJohn Levon 4471f5207b7SJohn Levon right = sval_cast(get_type(expr), right); 4481f5207b7SJohn Levon right.value--; 4491f5207b7SJohn Levon 450*efe51d0cSJohn Levon if (get_rl_internal(expr->left, implied, recurse_cnt, &rl) && rl && 451*efe51d0cSJohn Levon rl_max(rl).uvalue < right.uvalue) 4521f5207b7SJohn Levon right.uvalue = rl_max(rl).uvalue; 4531f5207b7SJohn Levon 454*efe51d0cSJohn Levon *res = alloc_rl(sval_cast(right.type, zero), right); 455*efe51d0cSJohn Levon return true; 4561f5207b7SJohn Levon } 4571f5207b7SJohn Levon 458*efe51d0cSJohn Levon static bool handle_bitwise_AND(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res) 4591f5207b7SJohn Levon { 4601f5207b7SJohn Levon struct symbol *type; 4611f5207b7SJohn Levon struct range_list *left_rl, *right_rl; 4621f5207b7SJohn Levon int new_recurse; 4631f5207b7SJohn Levon 4641f5207b7SJohn Levon if (implied != RL_IMPLIED && implied != RL_ABSOLUTE && implied != RL_REAL_ABSOLUTE) 465*efe51d0cSJohn Levon return false; 4661f5207b7SJohn Levon 4671f5207b7SJohn Levon type = get_type(expr); 4681f5207b7SJohn Levon 469*efe51d0cSJohn Levon if (!get_rl_internal(expr->left, implied, recurse_cnt, &left_rl)) 470*efe51d0cSJohn Levon left_rl = alloc_whole_rl(type); 471*efe51d0cSJohn Levon left_rl = cast_rl(type, left_rl); 4721f5207b7SJohn Levon 4731f5207b7SJohn Levon new_recurse = *recurse_cnt; 4741f5207b7SJohn Levon if (*recurse_cnt >= 200) 4751f5207b7SJohn Levon new_recurse = 100; /* Let's try super hard to get the mask */ 476*efe51d0cSJohn Levon if (!get_rl_internal(expr->right, implied, &new_recurse, &right_rl)) 477*efe51d0cSJohn Levon right_rl = alloc_whole_rl(type); 478*efe51d0cSJohn Levon right_rl = cast_rl(type, right_rl); 479*efe51d0cSJohn Levon *recurse_cnt = new_recurse; 4801f5207b7SJohn Levon 481*efe51d0cSJohn Levon *res = rl_binop(left_rl, '&', right_rl); 482*efe51d0cSJohn Levon return true; 4831f5207b7SJohn Levon } 4841f5207b7SJohn Levon 485*efe51d0cSJohn Levon static bool use_rl_binop(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res) 4861f5207b7SJohn Levon { 4871f5207b7SJohn Levon struct symbol *type; 4881f5207b7SJohn Levon struct range_list *left_rl, *right_rl; 4891f5207b7SJohn Levon 4901f5207b7SJohn Levon if (implied != RL_IMPLIED && implied != RL_ABSOLUTE && implied != RL_REAL_ABSOLUTE) 491*efe51d0cSJohn Levon return false; 4921f5207b7SJohn Levon 4931f5207b7SJohn Levon type = get_type(expr); 4941f5207b7SJohn Levon 4951f5207b7SJohn Levon get_absolute_rl_internal(expr->left, &left_rl, recurse_cnt); 4961f5207b7SJohn Levon get_absolute_rl_internal(expr->right, &right_rl, recurse_cnt); 4971f5207b7SJohn Levon left_rl = cast_rl(type, left_rl); 4981f5207b7SJohn Levon right_rl = cast_rl(type, right_rl); 4991f5207b7SJohn Levon if (!left_rl || !right_rl) 500*efe51d0cSJohn Levon return false; 5011f5207b7SJohn Levon 502*efe51d0cSJohn Levon *res = rl_binop(left_rl, expr->op, right_rl); 503*efe51d0cSJohn Levon return true; 5041f5207b7SJohn Levon } 5051f5207b7SJohn Levon 506*efe51d0cSJohn Levon static bool handle_right_shift(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res) 5071f5207b7SJohn Levon { 508*efe51d0cSJohn Levon struct range_list *left_rl, *right_rl; 5091f5207b7SJohn Levon sval_t min, max; 5101f5207b7SJohn Levon 5111f5207b7SJohn Levon if (implied == RL_EXACT || implied == RL_HARD) 512*efe51d0cSJohn Levon return false; 5131f5207b7SJohn Levon 514*efe51d0cSJohn Levon if (get_rl_internal(expr->left, implied, recurse_cnt, &left_rl)) { 5151f5207b7SJohn Levon max = rl_max(left_rl); 5161f5207b7SJohn Levon min = rl_min(left_rl); 5171f5207b7SJohn Levon } else { 5181f5207b7SJohn Levon if (implied == RL_FUZZY) 519*efe51d0cSJohn Levon return false; 5201f5207b7SJohn Levon max = sval_type_max(get_type(expr->left)); 5211f5207b7SJohn Levon min = sval_type_val(get_type(expr->left), 0); 5221f5207b7SJohn Levon } 5231f5207b7SJohn Levon 524*efe51d0cSJohn Levon if (get_rl_internal(expr->right, implied, recurse_cnt, &right_rl) && 525*efe51d0cSJohn Levon !sval_is_negative(rl_min(right_rl))) { 526*efe51d0cSJohn Levon min = sval_binop(min, SPECIAL_RIGHTSHIFT, rl_max(right_rl)); 527*efe51d0cSJohn Levon max = sval_binop(max, SPECIAL_RIGHTSHIFT, rl_min(right_rl)); 5281f5207b7SJohn Levon } else if (!sval_is_negative(min)) { 5291f5207b7SJohn Levon min.value = 0; 5301f5207b7SJohn Levon max = sval_type_max(max.type); 5311f5207b7SJohn Levon } else { 532*efe51d0cSJohn Levon return false; 5331f5207b7SJohn Levon } 5341f5207b7SJohn Levon 535*efe51d0cSJohn Levon *res = alloc_rl(min, max); 536*efe51d0cSJohn Levon return true; 5371f5207b7SJohn Levon } 5381f5207b7SJohn Levon 539*efe51d0cSJohn Levon static bool handle_left_shift(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res) 5401f5207b7SJohn Levon { 541*efe51d0cSJohn Levon struct range_list *left_rl, *rl; 5421f5207b7SJohn Levon sval_t right; 5431f5207b7SJohn Levon 5441f5207b7SJohn Levon if (implied == RL_EXACT || implied == RL_HARD) 545*efe51d0cSJohn Levon return false; 5461f5207b7SJohn Levon /* this is hopeless without the right side */ 547*efe51d0cSJohn Levon if (!get_implied_value_internal(expr->right, recurse_cnt, &right)) 548*efe51d0cSJohn Levon return false; 549*efe51d0cSJohn Levon if (!get_rl_internal(expr->left, implied, recurse_cnt, &left_rl)) { 5501f5207b7SJohn Levon if (implied == RL_FUZZY) 551*efe51d0cSJohn Levon return false; 552*efe51d0cSJohn Levon left_rl = alloc_whole_rl(get_type(expr->left)); 5531f5207b7SJohn Levon } 5541f5207b7SJohn Levon 555*efe51d0cSJohn Levon rl = rl_binop(left_rl, SPECIAL_LEFTSHIFT, alloc_rl(right, right)); 556*efe51d0cSJohn Levon if (!rl) 557*efe51d0cSJohn Levon return false; 558*efe51d0cSJohn Levon *res = rl; 559*efe51d0cSJohn Levon return true; 5601f5207b7SJohn Levon } 5611f5207b7SJohn Levon 562*efe51d0cSJohn Levon static bool handle_known_binop(struct expression *expr, sval_t *res) 5631f5207b7SJohn Levon { 5641f5207b7SJohn Levon sval_t left, right; 5651f5207b7SJohn Levon 5661f5207b7SJohn Levon if (!get_value(expr->left, &left)) 567*efe51d0cSJohn Levon return false; 5681f5207b7SJohn Levon if (!get_value(expr->right, &right)) 569*efe51d0cSJohn Levon return false; 570*efe51d0cSJohn Levon *res = sval_binop(left, expr->op, right); 571*efe51d0cSJohn Levon return true; 5721f5207b7SJohn Levon } 5731f5207b7SJohn Levon 5741f5207b7SJohn Levon static int has_actual_ranges(struct range_list *rl) 5751f5207b7SJohn Levon { 5761f5207b7SJohn Levon struct data_range *tmp; 5771f5207b7SJohn Levon 5781f5207b7SJohn Levon FOR_EACH_PTR(rl, tmp) { 5791f5207b7SJohn Levon if (sval_cmp(tmp->min, tmp->max) != 0) 5801f5207b7SJohn Levon return 1; 5811f5207b7SJohn Levon } END_FOR_EACH_PTR(tmp); 5821f5207b7SJohn Levon return 0; 5831f5207b7SJohn Levon } 5841f5207b7SJohn Levon 5851f5207b7SJohn Levon static struct range_list *handle_implied_binop(struct range_list *left_rl, int op, struct range_list *right_rl) 5861f5207b7SJohn Levon { 5871f5207b7SJohn Levon struct range_list *res_rl; 5881f5207b7SJohn Levon struct data_range *left_drange, *right_drange; 5891f5207b7SJohn Levon sval_t res; 5901f5207b7SJohn Levon 5911f5207b7SJohn Levon if (!left_rl || !right_rl) 5921f5207b7SJohn Levon return NULL; 5931f5207b7SJohn Levon if (has_actual_ranges(left_rl)) 5941f5207b7SJohn Levon return NULL; 5951f5207b7SJohn Levon if (has_actual_ranges(right_rl)) 5961f5207b7SJohn Levon return NULL; 5971f5207b7SJohn Levon 5981f5207b7SJohn Levon if (ptr_list_size((struct ptr_list *)left_rl) * ptr_list_size((struct ptr_list *)right_rl) > 20) 5991f5207b7SJohn Levon return NULL; 6001f5207b7SJohn Levon 6011f5207b7SJohn Levon res_rl = NULL; 6021f5207b7SJohn Levon 6031f5207b7SJohn Levon FOR_EACH_PTR(left_rl, left_drange) { 6041f5207b7SJohn Levon FOR_EACH_PTR(right_rl, right_drange) { 6051f5207b7SJohn Levon if ((op == '%' || op == '/') && 6061f5207b7SJohn Levon right_drange->min.value == 0) 6071f5207b7SJohn Levon return NULL; 6081f5207b7SJohn Levon res = sval_binop(left_drange->min, op, right_drange->min); 6091f5207b7SJohn Levon add_range(&res_rl, res, res); 6101f5207b7SJohn Levon } END_FOR_EACH_PTR(right_drange); 6111f5207b7SJohn Levon } END_FOR_EACH_PTR(left_drange); 6121f5207b7SJohn Levon 6131f5207b7SJohn Levon return res_rl; 6141f5207b7SJohn Levon } 6151f5207b7SJohn Levon 616*efe51d0cSJohn Levon static bool handle_binop_rl_helper(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval) 6171f5207b7SJohn Levon { 6181f5207b7SJohn Levon struct symbol *type; 619*efe51d0cSJohn Levon struct range_list *left_rl = NULL; 620*efe51d0cSJohn Levon struct range_list *right_rl = NULL; 621*efe51d0cSJohn Levon struct range_list *rl; 6221f5207b7SJohn Levon sval_t min, max; 6231f5207b7SJohn Levon 624*efe51d0cSJohn Levon type = get_promoted_type(get_type(expr->left), get_type(expr->right)); 625*efe51d0cSJohn Levon get_rl_internal(expr->left, implied, recurse_cnt, &left_rl); 6261f5207b7SJohn Levon left_rl = cast_rl(type, left_rl); 627*efe51d0cSJohn Levon get_rl_internal(expr->right, implied, recurse_cnt, &right_rl); 6281f5207b7SJohn Levon right_rl = cast_rl(type, right_rl); 6291f5207b7SJohn Levon if (!left_rl && !right_rl) 630*efe51d0cSJohn Levon return false; 6311f5207b7SJohn Levon 6321f5207b7SJohn Levon rl = handle_implied_binop(left_rl, expr->op, right_rl); 633*efe51d0cSJohn Levon if (rl) { 634*efe51d0cSJohn Levon *res = rl; 635*efe51d0cSJohn Levon return true; 636*efe51d0cSJohn Levon } 6371f5207b7SJohn Levon 6381f5207b7SJohn Levon switch (expr->op) { 6391f5207b7SJohn Levon case '%': 640*efe51d0cSJohn Levon return handle_mod_rl(expr, implied, recurse_cnt, res); 6411f5207b7SJohn Levon case '&': 642*efe51d0cSJohn Levon return handle_bitwise_AND(expr, implied, recurse_cnt, res); 6431f5207b7SJohn Levon case '|': 6441f5207b7SJohn Levon case '^': 645*efe51d0cSJohn Levon return use_rl_binop(expr, implied, recurse_cnt, res); 6461f5207b7SJohn Levon case SPECIAL_RIGHTSHIFT: 647*efe51d0cSJohn Levon return handle_right_shift(expr, implied, recurse_cnt, res); 6481f5207b7SJohn Levon case SPECIAL_LEFTSHIFT: 649*efe51d0cSJohn Levon return handle_left_shift(expr, implied, recurse_cnt, res); 6501f5207b7SJohn Levon case '-': 651*efe51d0cSJohn Levon return handle_subtract_rl(expr, implied, recurse_cnt, res); 6521f5207b7SJohn Levon case '/': 653*efe51d0cSJohn Levon return handle_divide_rl(expr, implied, recurse_cnt, res); 6541f5207b7SJohn Levon } 6551f5207b7SJohn Levon 6561f5207b7SJohn Levon if (!left_rl || !right_rl) 657*efe51d0cSJohn Levon return false; 6581f5207b7SJohn Levon 6591f5207b7SJohn Levon if (sval_binop_overflows(rl_min(left_rl), expr->op, rl_min(right_rl))) 660*efe51d0cSJohn Levon return false; 6611f5207b7SJohn Levon if (sval_binop_overflows(rl_max(left_rl), expr->op, rl_max(right_rl))) 662*efe51d0cSJohn Levon return false; 6631f5207b7SJohn Levon 6641f5207b7SJohn Levon min = sval_binop(rl_min(left_rl), expr->op, rl_min(right_rl)); 6651f5207b7SJohn Levon max = sval_binop(rl_max(left_rl), expr->op, rl_max(right_rl)); 6661f5207b7SJohn Levon 667*efe51d0cSJohn Levon *res = alloc_rl(min, max); 668*efe51d0cSJohn Levon return true; 669*efe51d0cSJohn Levon 670*efe51d0cSJohn Levon } 671*efe51d0cSJohn Levon 672*efe51d0cSJohn Levon static bool handle_binop_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval) 673*efe51d0cSJohn Levon { 674*efe51d0cSJohn Levon struct smatch_state *state; 675*efe51d0cSJohn Levon struct range_list *rl; 676*efe51d0cSJohn Levon sval_t val; 677*efe51d0cSJohn Levon 678*efe51d0cSJohn Levon if (handle_known_binop(expr, &val)) { 679*efe51d0cSJohn Levon *res_sval = val; 680*efe51d0cSJohn Levon return true; 681*efe51d0cSJohn Levon } 682*efe51d0cSJohn Levon if (implied == RL_EXACT) 683*efe51d0cSJohn Levon return false; 684*efe51d0cSJohn Levon 685*efe51d0cSJohn Levon if (custom_handle_variable) { 686*efe51d0cSJohn Levon rl = custom_handle_variable(expr); 687*efe51d0cSJohn Levon if (rl) { 688*efe51d0cSJohn Levon *res = rl; 689*efe51d0cSJohn Levon return true; 690*efe51d0cSJohn Levon } 691*efe51d0cSJohn Levon } 692*efe51d0cSJohn Levon 693*efe51d0cSJohn Levon state = get_extra_state(expr); 694*efe51d0cSJohn Levon if (state && !is_whole_rl(estate_rl(state))) { 695*efe51d0cSJohn Levon if (implied != RL_HARD || estate_has_hard_max(state)) { 696*efe51d0cSJohn Levon *res = clone_rl(estate_rl(state)); 697*efe51d0cSJohn Levon return true; 698*efe51d0cSJohn Levon } 699*efe51d0cSJohn Levon } 700*efe51d0cSJohn Levon 701*efe51d0cSJohn Levon return handle_binop_rl_helper(expr, implied, recurse_cnt, res, res_sval); 7021f5207b7SJohn Levon } 7031f5207b7SJohn Levon 7041f5207b7SJohn Levon static int do_comparison(struct expression *expr) 7051f5207b7SJohn Levon { 7061f5207b7SJohn Levon struct range_list *left_ranges = NULL; 7071f5207b7SJohn Levon struct range_list *right_ranges = NULL; 7081f5207b7SJohn Levon int poss_true, poss_false; 7091f5207b7SJohn Levon struct symbol *type; 7101f5207b7SJohn Levon 7111f5207b7SJohn Levon type = get_type(expr); 7121f5207b7SJohn Levon get_absolute_rl(expr->left, &left_ranges); 7131f5207b7SJohn Levon get_absolute_rl(expr->right, &right_ranges); 7141f5207b7SJohn Levon 7151f5207b7SJohn Levon left_ranges = cast_rl(type, left_ranges); 7161f5207b7SJohn Levon right_ranges = cast_rl(type, right_ranges); 7171f5207b7SJohn Levon 7181f5207b7SJohn Levon poss_true = possibly_true_rl(left_ranges, expr->op, right_ranges); 7191f5207b7SJohn Levon poss_false = possibly_false_rl(left_ranges, expr->op, right_ranges); 7201f5207b7SJohn Levon 7211f5207b7SJohn Levon if (!poss_true && !poss_false) 7221f5207b7SJohn Levon return 0x0; 7231f5207b7SJohn Levon if (poss_true && !poss_false) 7241f5207b7SJohn Levon return 0x1; 7251f5207b7SJohn Levon if (!poss_true && poss_false) 7261f5207b7SJohn Levon return 0x2; 7271f5207b7SJohn Levon return 0x3; 7281f5207b7SJohn Levon } 7291f5207b7SJohn Levon 730*efe51d0cSJohn Levon static bool handle_comparison_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval) 7311f5207b7SJohn Levon { 7321f5207b7SJohn Levon sval_t left, right; 733*efe51d0cSJohn Levon int cmp; 7341f5207b7SJohn Levon 7351f5207b7SJohn Levon if (expr->op == SPECIAL_EQUAL && expr->left->type == EXPR_TYPE) { 7361f5207b7SJohn Levon struct symbol *left, *right; 7371f5207b7SJohn Levon 738*efe51d0cSJohn Levon if (expr->right->type != EXPR_TYPE) 739*efe51d0cSJohn Levon return false; 740*efe51d0cSJohn Levon 7411f5207b7SJohn Levon left = get_real_base_type(expr->left->symbol); 742*efe51d0cSJohn Levon right = get_real_base_type(expr->right->symbol); 743*efe51d0cSJohn Levon if (type_bits(left) == type_bits(right) && 744*efe51d0cSJohn Levon type_positive_bits(left) == type_positive_bits(right)) 745*efe51d0cSJohn Levon *res_sval = one; 746*efe51d0cSJohn Levon else 747*efe51d0cSJohn Levon *res_sval = zero; 748*efe51d0cSJohn Levon return true; 7491f5207b7SJohn Levon } 7501f5207b7SJohn Levon 7511f5207b7SJohn Levon if (get_value(expr->left, &left) && get_value(expr->right, &right)) { 7521f5207b7SJohn Levon struct data_range tmp_left, tmp_right; 7531f5207b7SJohn Levon 7541f5207b7SJohn Levon tmp_left.min = left; 7551f5207b7SJohn Levon tmp_left.max = left; 7561f5207b7SJohn Levon tmp_right.min = right; 7571f5207b7SJohn Levon tmp_right.max = right; 7581f5207b7SJohn Levon if (true_comparison_range(&tmp_left, expr->op, &tmp_right)) 759*efe51d0cSJohn Levon *res_sval = one; 760*efe51d0cSJohn Levon else 761*efe51d0cSJohn Levon *res_sval = zero; 762*efe51d0cSJohn Levon return true; 7631f5207b7SJohn Levon } 7641f5207b7SJohn Levon 7651f5207b7SJohn Levon if (implied == RL_EXACT) 766*efe51d0cSJohn Levon return false; 7671f5207b7SJohn Levon 768*efe51d0cSJohn Levon cmp = do_comparison(expr); 769*efe51d0cSJohn Levon if (cmp == 1) { 770*efe51d0cSJohn Levon *res_sval = one; 771*efe51d0cSJohn Levon return true; 772*efe51d0cSJohn Levon } 773*efe51d0cSJohn Levon if (cmp == 2) { 774*efe51d0cSJohn Levon *res_sval = zero; 775*efe51d0cSJohn Levon return true; 776*efe51d0cSJohn Levon } 7771f5207b7SJohn Levon 778*efe51d0cSJohn Levon *res = alloc_rl(zero, one); 779*efe51d0cSJohn Levon return true; 7801f5207b7SJohn Levon } 7811f5207b7SJohn Levon 782*efe51d0cSJohn Levon static bool handle_logical_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval) 7831f5207b7SJohn Levon { 7841f5207b7SJohn Levon sval_t left, right; 7851f5207b7SJohn Levon int left_known = 0; 7861f5207b7SJohn Levon int right_known = 0; 7871f5207b7SJohn Levon 7881f5207b7SJohn Levon if (implied == RL_EXACT) { 7891f5207b7SJohn Levon if (get_value(expr->left, &left)) 7901f5207b7SJohn Levon left_known = 1; 7911f5207b7SJohn Levon if (get_value(expr->right, &right)) 7921f5207b7SJohn Levon right_known = 1; 7931f5207b7SJohn Levon } else { 794*efe51d0cSJohn Levon if (get_implied_value_internal(expr->left, recurse_cnt, &left)) 7951f5207b7SJohn Levon left_known = 1; 796*efe51d0cSJohn Levon if (get_implied_value_internal(expr->right, recurse_cnt, &right)) 7971f5207b7SJohn Levon right_known = 1; 7981f5207b7SJohn Levon } 7991f5207b7SJohn Levon 8001f5207b7SJohn Levon switch (expr->op) { 8011f5207b7SJohn Levon case SPECIAL_LOGICAL_OR: 8021f5207b7SJohn Levon if (left_known && left.value) 803*efe51d0cSJohn Levon goto one; 8041f5207b7SJohn Levon if (right_known && right.value) 805*efe51d0cSJohn Levon goto one; 8061f5207b7SJohn Levon if (left_known && right_known) 807*efe51d0cSJohn Levon goto zero; 8081f5207b7SJohn Levon break; 8091f5207b7SJohn Levon case SPECIAL_LOGICAL_AND: 8101f5207b7SJohn Levon if (left_known && right_known) { 8111f5207b7SJohn Levon if (left.value && right.value) 812*efe51d0cSJohn Levon goto one; 813*efe51d0cSJohn Levon goto zero; 8141f5207b7SJohn Levon } 8151f5207b7SJohn Levon break; 8161f5207b7SJohn Levon default: 817*efe51d0cSJohn Levon return false; 8181f5207b7SJohn Levon } 8191f5207b7SJohn Levon 8201f5207b7SJohn Levon if (implied == RL_EXACT) 821*efe51d0cSJohn Levon return false; 8221f5207b7SJohn Levon 823*efe51d0cSJohn Levon *res = alloc_rl(zero, one); 824*efe51d0cSJohn Levon return true; 825*efe51d0cSJohn Levon 826*efe51d0cSJohn Levon zero: 827*efe51d0cSJohn Levon *res_sval = zero; 828*efe51d0cSJohn Levon return true; 829*efe51d0cSJohn Levon one: 830*efe51d0cSJohn Levon *res_sval = one; 831*efe51d0cSJohn Levon return true; 8321f5207b7SJohn Levon } 8331f5207b7SJohn Levon 834*efe51d0cSJohn Levon static bool handle_conditional_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval) 8351f5207b7SJohn Levon { 8361f5207b7SJohn Levon struct expression *cond_true; 8371f5207b7SJohn Levon struct range_list *true_rl, *false_rl; 8381f5207b7SJohn Levon struct symbol *type; 8391f5207b7SJohn Levon int final_pass_orig = final_pass; 8401f5207b7SJohn Levon 8411f5207b7SJohn Levon cond_true = expr->cond_true; 8421f5207b7SJohn Levon if (!cond_true) 8431f5207b7SJohn Levon cond_true = expr->conditional; 8441f5207b7SJohn Levon 8451f5207b7SJohn Levon if (known_condition_true(expr->conditional)) 846*efe51d0cSJohn Levon return get_rl_sval(cond_true, implied, recurse_cnt, res, res_sval); 8471f5207b7SJohn Levon if (known_condition_false(expr->conditional)) 848*efe51d0cSJohn Levon return get_rl_sval(expr->cond_false, implied, recurse_cnt, res, res_sval); 8491f5207b7SJohn Levon 8501f5207b7SJohn Levon if (implied == RL_EXACT) 851*efe51d0cSJohn Levon return false; 8521f5207b7SJohn Levon 8531f5207b7SJohn Levon if (implied_condition_true(expr->conditional)) 854*efe51d0cSJohn Levon return get_rl_sval(cond_true, implied, recurse_cnt, res, res_sval); 8551f5207b7SJohn Levon if (implied_condition_false(expr->conditional)) 856*efe51d0cSJohn Levon return get_rl_sval(expr->cond_false, implied, recurse_cnt, res, res_sval); 8571f5207b7SJohn Levon 8581f5207b7SJohn Levon /* this becomes a problem with deeply nested conditional statements */ 8591f5207b7SJohn Levon if (low_on_memory()) 860*efe51d0cSJohn Levon return false; 8611f5207b7SJohn Levon 8621f5207b7SJohn Levon type = get_type(expr); 8631f5207b7SJohn Levon 8641f5207b7SJohn Levon __push_fake_cur_stree(); 8651f5207b7SJohn Levon final_pass = 0; 8661f5207b7SJohn Levon __split_whole_condition(expr->conditional); 867*efe51d0cSJohn Levon true_rl = NULL; 868*efe51d0cSJohn Levon get_rl_internal(cond_true, implied, recurse_cnt, &true_rl); 8691f5207b7SJohn Levon __push_true_states(); 8701f5207b7SJohn Levon __use_false_states(); 871*efe51d0cSJohn Levon false_rl = NULL; 872*efe51d0cSJohn Levon get_rl_internal(expr->cond_false, implied, recurse_cnt, &false_rl); 8731f5207b7SJohn Levon __merge_true_states(); 8741f5207b7SJohn Levon __free_fake_cur_stree(); 8751f5207b7SJohn Levon final_pass = final_pass_orig; 8761f5207b7SJohn Levon 8771f5207b7SJohn Levon if (!true_rl || !false_rl) 878*efe51d0cSJohn Levon return false; 8791f5207b7SJohn Levon true_rl = cast_rl(type, true_rl); 8801f5207b7SJohn Levon false_rl = cast_rl(type, false_rl); 8811f5207b7SJohn Levon 882*efe51d0cSJohn Levon *res = rl_union(true_rl, false_rl); 883*efe51d0cSJohn Levon return true; 8841f5207b7SJohn Levon } 8851f5207b7SJohn Levon 886*efe51d0cSJohn Levon static bool get_fuzzy_max_helper(struct expression *expr, sval_t *max) 8871f5207b7SJohn Levon { 8881f5207b7SJohn Levon struct smatch_state *state; 8891f5207b7SJohn Levon sval_t sval; 8901f5207b7SJohn Levon 8911f5207b7SJohn Levon if (get_hard_max(expr, &sval)) { 8921f5207b7SJohn Levon *max = sval; 893*efe51d0cSJohn Levon return true; 8941f5207b7SJohn Levon } 8951f5207b7SJohn Levon 8961f5207b7SJohn Levon state = get_extra_state(expr); 8971f5207b7SJohn Levon if (!state || !estate_has_fuzzy_max(state)) 898*efe51d0cSJohn Levon return false; 8991f5207b7SJohn Levon *max = sval_cast(get_type(expr), estate_get_fuzzy_max(state)); 900*efe51d0cSJohn Levon return true; 9011f5207b7SJohn Levon } 9021f5207b7SJohn Levon 903*efe51d0cSJohn Levon static bool get_fuzzy_min_helper(struct expression *expr, sval_t *min) 9041f5207b7SJohn Levon { 9051f5207b7SJohn Levon struct smatch_state *state; 9061f5207b7SJohn Levon sval_t sval; 9071f5207b7SJohn Levon 9081f5207b7SJohn Levon state = get_extra_state(expr); 9091f5207b7SJohn Levon if (!state || !estate_rl(state)) 910*efe51d0cSJohn Levon return false; 9111f5207b7SJohn Levon 9121f5207b7SJohn Levon sval = estate_min(state); 9131f5207b7SJohn Levon if (sval_is_negative(sval) && sval_is_min(sval)) 914*efe51d0cSJohn Levon return false; 9151f5207b7SJohn Levon 9161f5207b7SJohn Levon if (sval_is_max(sval)) 917*efe51d0cSJohn Levon return false; 9181f5207b7SJohn Levon 9191f5207b7SJohn Levon *min = sval_cast(get_type(expr), sval); 920*efe51d0cSJohn Levon return true; 9211f5207b7SJohn Levon } 9221f5207b7SJohn Levon 9231f5207b7SJohn Levon int get_const_value(struct expression *expr, sval_t *sval) 9241f5207b7SJohn Levon { 9251f5207b7SJohn Levon struct symbol *sym; 9261f5207b7SJohn Levon sval_t right; 9271f5207b7SJohn Levon 9281f5207b7SJohn Levon if (expr->type != EXPR_SYMBOL || !expr->symbol) 9291f5207b7SJohn Levon return 0; 9301f5207b7SJohn Levon sym = expr->symbol; 9311f5207b7SJohn Levon if (!(sym->ctype.modifiers & MOD_CONST)) 9321f5207b7SJohn Levon return 0; 9331f5207b7SJohn Levon if (get_value(sym->initializer, &right)) { 9341f5207b7SJohn Levon *sval = sval_cast(get_type(expr), right); 9351f5207b7SJohn Levon return 1; 9361f5207b7SJohn Levon } 9371f5207b7SJohn Levon return 0; 9381f5207b7SJohn Levon } 9391f5207b7SJohn Levon 9401f5207b7SJohn Levon struct range_list *var_to_absolute_rl(struct expression *expr) 9411f5207b7SJohn Levon { 9421f5207b7SJohn Levon struct smatch_state *state; 9431f5207b7SJohn Levon struct range_list *rl; 9441f5207b7SJohn Levon 9451f5207b7SJohn Levon state = get_extra_state(expr); 9461f5207b7SJohn Levon if (!state || is_whole_rl(estate_rl(state))) { 9471f5207b7SJohn Levon state = get_real_absolute_state(expr); 9481f5207b7SJohn Levon if (state && state->data && !estate_is_whole(state)) 9491f5207b7SJohn Levon return clone_rl(estate_rl(state)); 9501f5207b7SJohn Levon if (get_local_rl(expr, &rl) && !is_whole_rl(rl)) 9511f5207b7SJohn Levon return rl; 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 964*efe51d0cSJohn 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 971*efe51d0cSJohn Levon if (get_const_value(expr, &sval)) { 972*efe51d0cSJohn Levon *res_sval = sval; 973*efe51d0cSJohn Levon return true; 974*efe51d0cSJohn Levon } 975*efe51d0cSJohn Levon 976*efe51d0cSJohn Levon if (implied == RL_EXACT) 977*efe51d0cSJohn Levon return false; 9781f5207b7SJohn Levon 9791f5207b7SJohn Levon if (custom_handle_variable) { 9801f5207b7SJohn Levon rl = custom_handle_variable(expr); 981*efe51d0cSJohn Levon if (rl) { 982*efe51d0cSJohn Levon if (!rl_to_sval(rl, res_sval)) 983*efe51d0cSJohn Levon *res = rl; 984*efe51d0cSJohn Levon } else { 985*efe51d0cSJohn Levon *res = var_to_absolute_rl(expr); 986*efe51d0cSJohn Levon } 987*efe51d0cSJohn Levon return true; 9881f5207b7SJohn Levon } 9891f5207b7SJohn Levon 990*efe51d0cSJohn Levon if (get_mtag_sval(expr, &sval)) { 991*efe51d0cSJohn Levon *res_sval = sval; 992*efe51d0cSJohn Levon return true; 993*efe51d0cSJohn Levon } 9941f5207b7SJohn Levon 9951f5207b7SJohn Levon type = get_type(expr); 996*efe51d0cSJohn Levon if (type && 997*efe51d0cSJohn Levon (type->type == SYM_ARRAY || 998*efe51d0cSJohn Levon type->type == SYM_FN)) 999*efe51d0cSJohn Levon return handle_address(expr, implied, recurse_cnt, res, res_sval); 1000*efe51d0cSJohn Levon 1001*efe51d0cSJohn 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); 1008*efe51d0cSJohn Levon if (!state) { 10091f5207b7SJohn Levon if (implied == RL_HARD) 1010*efe51d0cSJohn Levon return false; 1011*efe51d0cSJohn Levon if (get_local_rl(expr, res)) 1012*efe51d0cSJohn Levon return true; 1013*efe51d0cSJohn Levon if (get_mtag_rl(expr, res)) 1014*efe51d0cSJohn Levon return true; 1015*efe51d0cSJohn Levon if (get_db_type_rl(expr, res)) 1016*efe51d0cSJohn Levon return true; 1017*efe51d0cSJohn Levon if (is_array(expr) && get_array_rl(expr, res)) 1018*efe51d0cSJohn Levon return true; 1019*efe51d0cSJohn Levon return false; 10201f5207b7SJohn Levon } 10211f5207b7SJohn Levon if (implied == RL_HARD && !estate_has_hard_max(state)) 1022*efe51d0cSJohn Levon return false; 1023*efe51d0cSJohn Levon *res = clone_rl(estate_rl(state)); 1024*efe51d0cSJohn Levon return true; 10251f5207b7SJohn Levon case RL_REAL_ABSOLUTE: { 10261f5207b7SJohn Levon struct smatch_state *abs_state; 10271f5207b7SJohn Levon 10281f5207b7SJohn Levon state = get_extra_state(expr); 10291f5207b7SJohn Levon abs_state = get_real_absolute_state(expr); 10301f5207b7SJohn Levon 10311f5207b7SJohn Levon if (estate_rl(state) && estate_rl(abs_state)) { 1032*efe51d0cSJohn Levon *res = clone_rl(rl_intersection(estate_rl(state), 10331f5207b7SJohn Levon estate_rl(abs_state))); 1034*efe51d0cSJohn Levon return true; 10351f5207b7SJohn Levon } else if (estate_rl(state)) { 1036*efe51d0cSJohn Levon *res = clone_rl(estate_rl(state)); 1037*efe51d0cSJohn Levon return true; 10381f5207b7SJohn Levon } else if (estate_is_empty(state)) { 10391f5207b7SJohn Levon /* 10401f5207b7SJohn Levon * FIXME: we don't handle empty extra states correctly. 10411f5207b7SJohn Levon * 10421f5207b7SJohn Levon * The real abs rl is supposed to be filtered by the 10431f5207b7SJohn Levon * extra state if there is one. We don't bother keeping 10441f5207b7SJohn Levon * the abs state in sync all the time because we know it 10451f5207b7SJohn Levon * will be filtered later. 10461f5207b7SJohn Levon * 10471f5207b7SJohn Levon * It's not totally obvious to me how they should be 10481f5207b7SJohn Levon * handled. Perhaps we should take the whole rl and 10491f5207b7SJohn Levon * filter by the imaginary states. Perhaps we should 10501f5207b7SJohn Levon * just go with the empty state. 10511f5207b7SJohn Levon * 10521f5207b7SJohn Levon * Anyway what we currently do is return NULL here and 10531f5207b7SJohn Levon * that gets translated into the whole range in 10541f5207b7SJohn Levon * get_real_absolute_rl(). 10551f5207b7SJohn Levon * 10561f5207b7SJohn Levon */ 1057*efe51d0cSJohn Levon return false; 10581f5207b7SJohn Levon } else if (estate_rl(abs_state)) { 1059*efe51d0cSJohn Levon *res = clone_rl(estate_rl(abs_state)); 1060*efe51d0cSJohn Levon return true; 10611f5207b7SJohn Levon } 10621f5207b7SJohn Levon 1063*efe51d0cSJohn Levon if (get_local_rl(expr, res)) 1064*efe51d0cSJohn Levon return true; 1065*efe51d0cSJohn Levon if (get_mtag_rl(expr, res)) 1066*efe51d0cSJohn Levon return true; 1067*efe51d0cSJohn Levon if (get_db_type_rl(expr, res)) 1068*efe51d0cSJohn Levon return true; 1069*efe51d0cSJohn Levon if (is_array(expr) && get_array_rl(expr, res)) 1070*efe51d0cSJohn Levon return true; 1071*efe51d0cSJohn Levon return false; 10721f5207b7SJohn Levon } 10731f5207b7SJohn Levon case RL_FUZZY: 10741f5207b7SJohn Levon if (!get_fuzzy_min_helper(expr, &min)) 10751f5207b7SJohn Levon min = sval_type_min(get_type(expr)); 10761f5207b7SJohn Levon if (!get_fuzzy_max_helper(expr, &max)) 1077*efe51d0cSJohn Levon return false; 10781f5207b7SJohn Levon /* fuzzy ranges are often inverted */ 10791f5207b7SJohn Levon if (sval_cmp(min, max) > 0) { 10801f5207b7SJohn Levon sval = min; 10811f5207b7SJohn Levon min = max; 10821f5207b7SJohn Levon max = sval; 10831f5207b7SJohn Levon } 1084*efe51d0cSJohn Levon *res = alloc_rl(min, max); 1085*efe51d0cSJohn Levon return true; 10861f5207b7SJohn Levon } 1087*efe51d0cSJohn Levon return false; 10881f5207b7SJohn Levon } 10891f5207b7SJohn Levon 10901f5207b7SJohn Levon static sval_t handle_sizeof(struct expression *expr) 10911f5207b7SJohn Levon { 10921f5207b7SJohn Levon struct symbol *sym; 10931f5207b7SJohn Levon sval_t ret; 10941f5207b7SJohn Levon 10951f5207b7SJohn Levon ret = sval_blank(expr); 10961f5207b7SJohn Levon sym = expr->cast_type; 10971f5207b7SJohn Levon if (!sym) { 10981f5207b7SJohn Levon sym = evaluate_expression(expr->cast_expression); 10991f5207b7SJohn Levon if (!sym) { 11001f5207b7SJohn Levon __silence_warnings_for_stmt = true; 11011f5207b7SJohn Levon sym = &int_ctype; 11021f5207b7SJohn Levon } 11031f5207b7SJohn Levon #if 0 11041f5207b7SJohn Levon /* 11051f5207b7SJohn Levon * Expressions of restricted types will possibly get 11061f5207b7SJohn Levon * promoted - check that here. I'm not sure how this works, 11071f5207b7SJohn Levon * the problem is that sizeof(le16) shouldn't be promoted and 11081f5207b7SJohn Levon * the original code did that... Let's if zero this out and 11091f5207b7SJohn Levon * see what breaks. 11101f5207b7SJohn Levon */ 11111f5207b7SJohn Levon 11121f5207b7SJohn Levon if (is_restricted_type(sym)) { 11131f5207b7SJohn Levon if (type_bits(sym) < bits_in_int) 11141f5207b7SJohn Levon sym = &int_ctype; 11151f5207b7SJohn Levon } 11161f5207b7SJohn Levon #endif 11171f5207b7SJohn Levon if (is_fouled_type(sym)) 11181f5207b7SJohn Levon sym = &int_ctype; 11191f5207b7SJohn Levon } 11201f5207b7SJohn Levon examine_symbol_type(sym); 11211f5207b7SJohn Levon 11221f5207b7SJohn Levon ret.type = size_t_ctype; 11231f5207b7SJohn Levon if (type_bits(sym) <= 0) /* sizeof(void) */ { 11241f5207b7SJohn Levon if (get_real_base_type(sym) == &void_ctype) 11251f5207b7SJohn Levon ret.value = 1; 11261f5207b7SJohn Levon else 11271f5207b7SJohn Levon ret.value = 0; 11281f5207b7SJohn Levon } else 11291f5207b7SJohn Levon ret.value = type_bytes(sym); 11301f5207b7SJohn Levon 11311f5207b7SJohn Levon return ret; 11321f5207b7SJohn Levon } 11331f5207b7SJohn Levon 1134*efe51d0cSJohn Levon static bool handle_strlen(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval) 11351f5207b7SJohn Levon { 11361f5207b7SJohn Levon struct expression *arg, *tmp; 11371f5207b7SJohn Levon sval_t tag; 11381f5207b7SJohn Levon sval_t ret = { .type = &ulong_ctype }; 1139*efe51d0cSJohn Levon struct range_list *rl; 11401f5207b7SJohn Levon 11411f5207b7SJohn Levon arg = get_argument_from_call_expr(expr->args, 0); 11421f5207b7SJohn Levon if (!arg) 1143*efe51d0cSJohn Levon return false; 11441f5207b7SJohn Levon if (arg->type == EXPR_STRING) { 11451f5207b7SJohn Levon ret.value = arg->string->length - 1; 1146*efe51d0cSJohn Levon *res_sval = ret; 1147*efe51d0cSJohn Levon return true; 11481f5207b7SJohn Levon } 1149*efe51d0cSJohn Levon if (implied == RL_EXACT) 1150*efe51d0cSJohn Levon return false; 11511f5207b7SJohn Levon if (get_implied_value(arg, &tag) && 11521f5207b7SJohn Levon (tmp = fake_string_from_mtag(tag.uvalue))) { 11531f5207b7SJohn Levon ret.value = tmp->string->length - 1; 1154*efe51d0cSJohn Levon *res_sval = ret; 1155*efe51d0cSJohn Levon return true; 11561f5207b7SJohn Levon } 11571f5207b7SJohn Levon 11581f5207b7SJohn Levon if (implied == RL_HARD || implied == RL_FUZZY) 1159*efe51d0cSJohn Levon return false; 11601f5207b7SJohn Levon 1161*efe51d0cSJohn Levon if (get_implied_return(expr, &rl)) { 1162*efe51d0cSJohn Levon *res = rl; 1163*efe51d0cSJohn Levon return true; 1164*efe51d0cSJohn Levon } 11651f5207b7SJohn Levon 1166*efe51d0cSJohn Levon return false; 11671f5207b7SJohn Levon } 11681f5207b7SJohn Levon 1169*efe51d0cSJohn Levon static bool handle_builtin_constant_p(struct expression *expr, int implied, int *recurse_cnt, sval_t *res_sval) 11701f5207b7SJohn Levon { 11711f5207b7SJohn Levon struct expression *arg; 11721f5207b7SJohn Levon struct range_list *rl; 11731f5207b7SJohn Levon 11741f5207b7SJohn Levon arg = get_argument_from_call_expr(expr->args, 0); 1175*efe51d0cSJohn Levon if (get_rl_internal(arg, RL_EXACT, recurse_cnt, &rl)) 1176*efe51d0cSJohn Levon *res_sval = one; 1177*efe51d0cSJohn Levon else 1178*efe51d0cSJohn Levon *res_sval = zero; 1179*efe51d0cSJohn Levon return true; 11801f5207b7SJohn Levon } 11811f5207b7SJohn Levon 1182*efe51d0cSJohn Levon static bool handle__builtin_choose_expr(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval) 11831f5207b7SJohn Levon { 11841f5207b7SJohn Levon struct expression *const_expr, *expr1, *expr2; 11851f5207b7SJohn Levon sval_t sval; 11861f5207b7SJohn Levon 11871f5207b7SJohn Levon const_expr = get_argument_from_call_expr(expr->args, 0); 11881f5207b7SJohn Levon expr1 = get_argument_from_call_expr(expr->args, 1); 11891f5207b7SJohn Levon expr2 = get_argument_from_call_expr(expr->args, 2); 11901f5207b7SJohn Levon 11911f5207b7SJohn Levon if (!get_value(const_expr, &sval) || !expr1 || !expr2) 1192*efe51d0cSJohn Levon return false; 11931f5207b7SJohn Levon if (sval.value) 1194*efe51d0cSJohn Levon return get_rl_sval(expr1, implied, recurse_cnt, res, res_sval); 1195*efe51d0cSJohn Levon else 1196*efe51d0cSJohn Levon return get_rl_sval(expr2, implied, recurse_cnt, res, res_sval); 11971f5207b7SJohn Levon } 11981f5207b7SJohn Levon 1199*efe51d0cSJohn Levon static bool handle_call_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval) 12001f5207b7SJohn Levon { 12011f5207b7SJohn Levon struct range_list *rl; 12021f5207b7SJohn Levon 12031f5207b7SJohn Levon if (sym_name_is("__builtin_constant_p", expr->fn)) 1204*efe51d0cSJohn Levon return handle_builtin_constant_p(expr, implied, recurse_cnt, res_sval); 12051f5207b7SJohn Levon 12061f5207b7SJohn Levon if (sym_name_is("__builtin_choose_expr", expr->fn)) 1207*efe51d0cSJohn Levon return handle__builtin_choose_expr(expr, implied, recurse_cnt, res, res_sval); 12081f5207b7SJohn Levon 12091f5207b7SJohn Levon if (sym_name_is("__builtin_expect", expr->fn) || 12101f5207b7SJohn Levon sym_name_is("__builtin_bswap16", expr->fn) || 12111f5207b7SJohn Levon sym_name_is("__builtin_bswap32", expr->fn) || 12121f5207b7SJohn Levon sym_name_is("__builtin_bswap64", expr->fn)) { 12131f5207b7SJohn Levon struct expression *arg; 12141f5207b7SJohn Levon 12151f5207b7SJohn Levon arg = get_argument_from_call_expr(expr->args, 0); 1216*efe51d0cSJohn Levon return get_rl_sval(arg, implied, recurse_cnt, res, res_sval); 12171f5207b7SJohn Levon } 12181f5207b7SJohn Levon 12191f5207b7SJohn Levon if (sym_name_is("strlen", expr->fn)) 1220*efe51d0cSJohn Levon return handle_strlen(expr, implied, recurse_cnt, res, res_sval); 12211f5207b7SJohn Levon 12221f5207b7SJohn Levon if (implied == RL_EXACT || implied == RL_HARD || implied == RL_FUZZY) 1223*efe51d0cSJohn Levon return false; 12241f5207b7SJohn Levon 12251f5207b7SJohn Levon if (custom_handle_variable) { 12261f5207b7SJohn Levon rl = custom_handle_variable(expr); 1227*efe51d0cSJohn Levon if (rl) { 1228*efe51d0cSJohn Levon *res = rl; 1229*efe51d0cSJohn Levon return true; 1230*efe51d0cSJohn Levon } 12311f5207b7SJohn Levon } 12321f5207b7SJohn Levon 1233*efe51d0cSJohn Levon /* Ugh... get_implied_return() sets *rl to NULL on failure */ 1234*efe51d0cSJohn Levon if (get_implied_return(expr, &rl)) { 1235*efe51d0cSJohn Levon *res = rl; 1236*efe51d0cSJohn Levon return true; 1237*efe51d0cSJohn Levon } 1238*efe51d0cSJohn Levon rl = db_return_vals(expr); 1239*efe51d0cSJohn Levon if (rl) { 1240*efe51d0cSJohn Levon *res = rl; 1241*efe51d0cSJohn Levon return true; 1242*efe51d0cSJohn Levon } 1243*efe51d0cSJohn Levon return false; 12441f5207b7SJohn Levon } 12451f5207b7SJohn Levon 1246*efe51d0cSJohn Levon static bool handle_cast(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval) 12471f5207b7SJohn Levon { 12481f5207b7SJohn Levon struct range_list *rl; 12491f5207b7SJohn Levon struct symbol *type; 1250*efe51d0cSJohn Levon sval_t sval = {}; 12511f5207b7SJohn Levon 12521f5207b7SJohn Levon type = get_type(expr); 1253*efe51d0cSJohn Levon if (get_rl_sval(expr->cast_expression, implied, recurse_cnt, &rl, &sval)) { 1254*efe51d0cSJohn Levon if (sval.type) 1255*efe51d0cSJohn Levon *res_sval = sval_cast(type, sval); 1256*efe51d0cSJohn Levon else 1257*efe51d0cSJohn Levon *res = cast_rl(type, rl); 1258*efe51d0cSJohn Levon return true; 1259*efe51d0cSJohn Levon } 1260*efe51d0cSJohn Levon if (implied == RL_ABSOLUTE || implied == RL_REAL_ABSOLUTE) { 1261*efe51d0cSJohn Levon *res = alloc_whole_rl(type); 1262*efe51d0cSJohn Levon return true; 1263*efe51d0cSJohn Levon } 12641f5207b7SJohn Levon if (implied == RL_IMPLIED && type && 1265*efe51d0cSJohn Levon type_bits(type) > 0 && type_bits(type) < 32) { 1266*efe51d0cSJohn Levon *res = alloc_whole_rl(type); 1267*efe51d0cSJohn Levon return true; 1268*efe51d0cSJohn Levon } 1269*efe51d0cSJohn Levon return false; 12701f5207b7SJohn Levon } 12711f5207b7SJohn Levon 1272*efe51d0cSJohn Levon static bool get_offset_from_down(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval) 12731f5207b7SJohn Levon { 1274*efe51d0cSJohn Levon struct expression *index; 1275*efe51d0cSJohn Levon struct symbol *type = expr->in; 12761f5207b7SJohn Levon struct range_list *rl; 1277*efe51d0cSJohn Levon struct symbol *field; 1278*efe51d0cSJohn Levon int offset = 0; 1279*efe51d0cSJohn Levon sval_t sval = { .type = ssize_t_ctype }; 1280*efe51d0cSJohn Levon sval_t tmp_sval = {}; 1281*efe51d0cSJohn Levon 1282*efe51d0cSJohn Levon /* 1283*efe51d0cSJohn Levon * FIXME: I don't really know what I'm doing here. I wish that I 1284*efe51d0cSJohn Levon * could just get rid of the __builtin_offset() function and use: 1285*efe51d0cSJohn Levon * "&((struct bpf_prog *)NULL)->insns[fprog->len]" instead... 1286*efe51d0cSJohn Levon * Anyway, I have done the minimum ammount of work to get that 1287*efe51d0cSJohn Levon * expression to work. 1288*efe51d0cSJohn Levon * 1289*efe51d0cSJohn Levon */ 1290*efe51d0cSJohn Levon 1291*efe51d0cSJohn Levon if (expr->op != '.' || !expr->down || 1292*efe51d0cSJohn Levon expr->down->type != EXPR_OFFSETOF || 1293*efe51d0cSJohn Levon expr->down->op != '[' || 1294*efe51d0cSJohn Levon !expr->down->index) 1295*efe51d0cSJohn Levon return false; 1296*efe51d0cSJohn Levon 1297*efe51d0cSJohn Levon index = expr->down->index; 1298*efe51d0cSJohn Levon 1299*efe51d0cSJohn Levon examine_symbol_type(type); 1300*efe51d0cSJohn Levon type = get_real_base_type(type); 1301*efe51d0cSJohn Levon if (!type) 1302*efe51d0cSJohn Levon return false; 1303*efe51d0cSJohn Levon field = find_identifier(expr->ident, type->symbol_list, &offset); 1304*efe51d0cSJohn Levon if (!field) 1305*efe51d0cSJohn Levon return false; 1306*efe51d0cSJohn Levon 1307*efe51d0cSJohn Levon type = get_real_base_type(field); 1308*efe51d0cSJohn Levon if (!type || type->type != SYM_ARRAY) 1309*efe51d0cSJohn Levon return false; 1310*efe51d0cSJohn Levon type = get_real_base_type(type); 1311*efe51d0cSJohn Levon 1312*efe51d0cSJohn Levon if (get_implied_value_internal(index, recurse_cnt, &sval)) { 1313*efe51d0cSJohn Levon res_sval->type = ssize_t_ctype; 1314*efe51d0cSJohn Levon res_sval->value = offset + sval.value * type_bytes(type); 1315*efe51d0cSJohn Levon return true; 1316*efe51d0cSJohn Levon } 1317*efe51d0cSJohn Levon 1318*efe51d0cSJohn Levon if (!get_rl_sval(index, implied, recurse_cnt, &rl, &tmp_sval)) 1319*efe51d0cSJohn Levon return false; 1320*efe51d0cSJohn Levon 1321*efe51d0cSJohn Levon /* 1322*efe51d0cSJohn Levon * I'm not sure why get_rl_sval() would return an sval when 1323*efe51d0cSJohn Levon * get_implied_value_internal() failed but it does when I 1324*efe51d0cSJohn Levon * parse drivers/net/ethernet/mellanox/mlx5/core/en/monitor_stats.c 1325*efe51d0cSJohn Levon * 1326*efe51d0cSJohn Levon */ 1327*efe51d0cSJohn Levon if (tmp_sval.type) { 1328*efe51d0cSJohn Levon res_sval->type = ssize_t_ctype; 1329*efe51d0cSJohn Levon res_sval->value = offset + sval.value * type_bytes(type); 1330*efe51d0cSJohn Levon return true; 1331*efe51d0cSJohn Levon } 1332*efe51d0cSJohn Levon 1333*efe51d0cSJohn Levon sval.value = type_bytes(type); 1334*efe51d0cSJohn Levon rl = rl_binop(rl, '*', alloc_rl(sval, sval)); 1335*efe51d0cSJohn Levon sval.value = offset; 1336*efe51d0cSJohn Levon *res = rl_binop(rl, '+', alloc_rl(sval, sval)); 1337*efe51d0cSJohn Levon return true; 1338*efe51d0cSJohn Levon } 1339*efe51d0cSJohn Levon 1340*efe51d0cSJohn Levon static bool get_offset_from_in(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval) 1341*efe51d0cSJohn Levon { 1342*efe51d0cSJohn Levon struct symbol *type = get_real_base_type(expr->in); 1343*efe51d0cSJohn Levon struct symbol *field; 1344*efe51d0cSJohn Levon int offset = 0; 1345*efe51d0cSJohn Levon 1346*efe51d0cSJohn Levon if (expr->op != '.' || !type || !expr->ident) 1347*efe51d0cSJohn Levon return false; 1348*efe51d0cSJohn Levon 1349*efe51d0cSJohn Levon field = find_identifier(expr->ident, type->symbol_list, &offset); 1350*efe51d0cSJohn Levon if (!field) 1351*efe51d0cSJohn Levon return false; 1352*efe51d0cSJohn Levon 1353*efe51d0cSJohn Levon res_sval->type = size_t_ctype; 1354*efe51d0cSJohn Levon res_sval->value = offset; 1355*efe51d0cSJohn Levon 1356*efe51d0cSJohn Levon return true; 1357*efe51d0cSJohn Levon } 1358*efe51d0cSJohn Levon 1359*efe51d0cSJohn Levon static bool handle_offsetof_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval) 1360*efe51d0cSJohn Levon { 1361*efe51d0cSJohn Levon if (get_offset_from_down(expr, implied, recurse_cnt, res, res_sval)) 1362*efe51d0cSJohn Levon return true; 1363*efe51d0cSJohn Levon 1364*efe51d0cSJohn Levon if (get_offset_from_in(expr, implied, recurse_cnt, res, res_sval)) 1365*efe51d0cSJohn Levon return true; 1366*efe51d0cSJohn Levon 1367*efe51d0cSJohn Levon evaluate_expression(expr); 1368*efe51d0cSJohn Levon if (expr->type == EXPR_VALUE) { 1369*efe51d0cSJohn Levon *res_sval = sval_from_val(expr, expr->value); 1370*efe51d0cSJohn Levon return true; 1371*efe51d0cSJohn Levon } 1372*efe51d0cSJohn Levon return false; 1373*efe51d0cSJohn Levon } 1374*efe51d0cSJohn Levon 1375*efe51d0cSJohn Levon static bool get_rl_sval(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *sval_res) 1376*efe51d0cSJohn Levon { 1377*efe51d0cSJohn Levon struct range_list *rl = (void *)-1UL; 13781f5207b7SJohn Levon struct symbol *type; 1379*efe51d0cSJohn Levon sval_t sval = {}; 13801f5207b7SJohn Levon 13811f5207b7SJohn Levon type = get_type(expr); 13821f5207b7SJohn Levon expr = strip_parens(expr); 13831f5207b7SJohn Levon if (!expr) 1384*efe51d0cSJohn Levon return false; 13851f5207b7SJohn Levon 13861f5207b7SJohn Levon if (++(*recurse_cnt) >= 200) 1387*efe51d0cSJohn Levon return false; 13881f5207b7SJohn Levon 13891f5207b7SJohn Levon switch(expr->type) { 13901f5207b7SJohn Levon case EXPR_CAST: 13911f5207b7SJohn Levon case EXPR_FORCE_CAST: 13921f5207b7SJohn Levon case EXPR_IMPLIED_CAST: 1393*efe51d0cSJohn Levon handle_cast(expr, implied, recurse_cnt, &rl, &sval); 13941f5207b7SJohn Levon goto out_cast; 13951f5207b7SJohn Levon } 13961f5207b7SJohn Levon 13971f5207b7SJohn Levon expr = strip_expr(expr); 13981f5207b7SJohn Levon if (!expr) 1399*efe51d0cSJohn Levon return false; 14001f5207b7SJohn Levon 14011f5207b7SJohn Levon switch (expr->type) { 14021f5207b7SJohn Levon case EXPR_VALUE: 14031f5207b7SJohn Levon sval = sval_from_val(expr, expr->value); 14041f5207b7SJohn Levon break; 14051f5207b7SJohn Levon case EXPR_PREOP: 1406*efe51d0cSJohn Levon handle_preop_rl(expr, implied, recurse_cnt, &rl, &sval); 14071f5207b7SJohn Levon break; 14081f5207b7SJohn Levon case EXPR_POSTOP: 1409*efe51d0cSJohn Levon get_rl_sval(expr->unop, implied, recurse_cnt, &rl, &sval); 14101f5207b7SJohn Levon break; 14111f5207b7SJohn Levon case EXPR_BINOP: 1412*efe51d0cSJohn Levon handle_binop_rl(expr, implied, recurse_cnt, &rl, &sval); 14131f5207b7SJohn Levon break; 14141f5207b7SJohn Levon case EXPR_COMPARE: 1415*efe51d0cSJohn Levon handle_comparison_rl(expr, implied, recurse_cnt, &rl, &sval); 14161f5207b7SJohn Levon break; 14171f5207b7SJohn Levon case EXPR_LOGICAL: 1418*efe51d0cSJohn Levon handle_logical_rl(expr, implied, recurse_cnt, &rl, &sval); 14191f5207b7SJohn Levon break; 14201f5207b7SJohn Levon case EXPR_PTRSIZEOF: 14211f5207b7SJohn Levon case EXPR_SIZEOF: 14221f5207b7SJohn Levon sval = handle_sizeof(expr); 14231f5207b7SJohn Levon break; 14241f5207b7SJohn Levon case EXPR_SELECT: 14251f5207b7SJohn Levon case EXPR_CONDITIONAL: 1426*efe51d0cSJohn Levon handle_conditional_rl(expr, implied, recurse_cnt, &rl, &sval); 14271f5207b7SJohn Levon break; 14281f5207b7SJohn Levon case EXPR_CALL: 1429*efe51d0cSJohn Levon handle_call_rl(expr, implied, recurse_cnt, &rl, &sval); 14301f5207b7SJohn Levon break; 14311f5207b7SJohn Levon case EXPR_STRING: 14321f5207b7SJohn Levon if (get_mtag_sval(expr, &sval)) 1433*efe51d0cSJohn Levon break; 1434*efe51d0cSJohn Levon if (implied == RL_EXACT) 1435*efe51d0cSJohn Levon break; 1436*efe51d0cSJohn Levon rl = alloc_rl(valid_ptr_min_sval, valid_ptr_max_sval); 1437*efe51d0cSJohn Levon break; 1438*efe51d0cSJohn Levon case EXPR_OFFSETOF: 1439*efe51d0cSJohn Levon handle_offsetof_rl(expr, implied, recurse_cnt, &rl, &sval); 1440*efe51d0cSJohn Levon break; 1441*efe51d0cSJohn Levon case EXPR_ALIGNOF: 1442*efe51d0cSJohn Levon evaluate_expression(expr); 1443*efe51d0cSJohn Levon if (expr->type == EXPR_VALUE) 1444*efe51d0cSJohn Levon sval = sval_from_val(expr, expr->value); 14451f5207b7SJohn Levon break; 14461f5207b7SJohn Levon default: 1447*efe51d0cSJohn Levon handle_variable(expr, implied, recurse_cnt, &rl, &sval); 14481f5207b7SJohn Levon } 14491f5207b7SJohn Levon 14501f5207b7SJohn Levon out_cast: 1451*efe51d0cSJohn Levon if (rl == (void *)-1UL) 1452*efe51d0cSJohn Levon rl = NULL; 1453*efe51d0cSJohn Levon 1454*efe51d0cSJohn Levon if (sval.type || (rl && rl_to_sval(rl, &sval))) { 1455*efe51d0cSJohn Levon *sval_res = sval; 1456*efe51d0cSJohn Levon return true; 1457*efe51d0cSJohn Levon } 1458*efe51d0cSJohn Levon if (implied == RL_EXACT) 1459*efe51d0cSJohn Levon return false; 1460*efe51d0cSJohn Levon 1461*efe51d0cSJohn Levon if (rl) { 1462*efe51d0cSJohn Levon *res = rl; 1463*efe51d0cSJohn Levon return true; 1464*efe51d0cSJohn Levon } 1465*efe51d0cSJohn Levon if (type && (implied == RL_ABSOLUTE || implied == RL_REAL_ABSOLUTE)) { 1466*efe51d0cSJohn Levon *res = alloc_whole_rl(type); 1467*efe51d0cSJohn Levon return true; 1468*efe51d0cSJohn Levon } 1469*efe51d0cSJohn Levon return false; 1470*efe51d0cSJohn Levon } 1471*efe51d0cSJohn Levon 1472*efe51d0cSJohn Levon static bool get_rl_internal(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res) 1473*efe51d0cSJohn Levon { 1474*efe51d0cSJohn Levon struct range_list *rl = NULL; 1475*efe51d0cSJohn Levon sval_t sval = {}; 1476*efe51d0cSJohn Levon 1477*efe51d0cSJohn Levon if (!get_rl_sval(expr, implied, recurse_cnt, &rl, &sval)) 1478*efe51d0cSJohn Levon return false; 1479*efe51d0cSJohn Levon 1480*efe51d0cSJohn Levon if (sval.type) 1481*efe51d0cSJohn Levon *res = alloc_rl(sval, sval); 1482*efe51d0cSJohn Levon else 1483*efe51d0cSJohn Levon *res = rl; 1484*efe51d0cSJohn Levon return true; 1485*efe51d0cSJohn Levon } 1486*efe51d0cSJohn Levon 1487*efe51d0cSJohn Levon static bool get_rl_helper(struct expression *expr, int implied, struct range_list **res) 1488*efe51d0cSJohn Levon { 1489*efe51d0cSJohn Levon struct range_list *rl = NULL; 1490*efe51d0cSJohn Levon sval_t sval = {}; 1491*efe51d0cSJohn Levon int recurse_cnt = 0; 1492*efe51d0cSJohn Levon 1493*efe51d0cSJohn Levon if (get_value(expr, &sval)) { 1494*efe51d0cSJohn Levon *res = alloc_rl(sval, sval); 1495*efe51d0cSJohn Levon return true; 1496*efe51d0cSJohn Levon } 1497*efe51d0cSJohn Levon 1498*efe51d0cSJohn Levon if (!get_rl_sval(expr, implied, &recurse_cnt, &rl, &sval)) 1499*efe51d0cSJohn Levon return false; 1500*efe51d0cSJohn Levon 1501*efe51d0cSJohn Levon if (sval.type) 1502*efe51d0cSJohn Levon *res = alloc_rl(sval, sval); 1503*efe51d0cSJohn Levon else 1504*efe51d0cSJohn Levon *res = rl; 1505*efe51d0cSJohn Levon return true; 15061f5207b7SJohn Levon } 15071f5207b7SJohn Levon 15081f5207b7SJohn Levon struct { 15091f5207b7SJohn Levon struct expression *expr; 1510*efe51d0cSJohn Levon sval_t sval; 15111f5207b7SJohn Levon } cached_results[24]; 15121f5207b7SJohn Levon static int cache_idx; 15131f5207b7SJohn Levon 15141f5207b7SJohn Levon void clear_math_cache(void) 15151f5207b7SJohn Levon { 15161f5207b7SJohn Levon memset(cached_results, 0, sizeof(cached_results)); 15171f5207b7SJohn Levon } 15181f5207b7SJohn Levon 1519*efe51d0cSJohn Levon /* 1520*efe51d0cSJohn Levon * Don't cache EXPR_VALUE because values are fast already. 1521*efe51d0cSJohn Levon * 1522*efe51d0cSJohn Levon */ 1523*efe51d0cSJohn Levon static bool get_value_literal(struct expression *expr, sval_t *res_sval) 1524*efe51d0cSJohn Levon { 1525*efe51d0cSJohn Levon struct expression *tmp; 1526*efe51d0cSJohn Levon int recurse_cnt = 0; 1527*efe51d0cSJohn Levon 1528*efe51d0cSJohn Levon tmp = strip_expr(expr); 1529*efe51d0cSJohn Levon if (!tmp || tmp->type != EXPR_VALUE) 1530*efe51d0cSJohn Levon return false; 1531*efe51d0cSJohn Levon 1532*efe51d0cSJohn Levon return get_rl_sval(expr, RL_EXACT, &recurse_cnt, NULL, res_sval); 1533*efe51d0cSJohn Levon } 1534*efe51d0cSJohn Levon 15351f5207b7SJohn Levon /* returns 1 if it can get a value literal or else returns 0 */ 1536*efe51d0cSJohn Levon int get_value(struct expression *expr, sval_t *res_sval) 15371f5207b7SJohn Levon { 15381f5207b7SJohn Levon struct range_list *(*orig_custom_fn)(struct expression *expr); 15391f5207b7SJohn Levon int recurse_cnt = 0; 1540*efe51d0cSJohn Levon sval_t sval = {}; 15411f5207b7SJohn Levon int i; 15421f5207b7SJohn Levon 1543*efe51d0cSJohn Levon if (get_value_literal(expr, res_sval)) 1544*efe51d0cSJohn Levon return 1; 1545*efe51d0cSJohn Levon 15461f5207b7SJohn Levon /* 15471f5207b7SJohn Levon * This only handles RL_EXACT because other expr statements can be 15481f5207b7SJohn Levon * different at different points. Like the list iterator, for example. 15491f5207b7SJohn Levon */ 15501f5207b7SJohn Levon for (i = 0; i < ARRAY_SIZE(cached_results); i++) { 1551*efe51d0cSJohn Levon if (expr == cached_results[i].expr) { 1552*efe51d0cSJohn Levon if (cached_results[i].sval.type) { 1553*efe51d0cSJohn Levon *res_sval = cached_results[i].sval; 1554*efe51d0cSJohn Levon return true; 1555*efe51d0cSJohn Levon } 1556*efe51d0cSJohn Levon return false; 1557*efe51d0cSJohn Levon } 15581f5207b7SJohn Levon } 15591f5207b7SJohn Levon 15601f5207b7SJohn Levon orig_custom_fn = custom_handle_variable; 15611f5207b7SJohn Levon custom_handle_variable = NULL; 1562*efe51d0cSJohn Levon get_rl_sval(expr, RL_EXACT, &recurse_cnt, NULL, &sval); 1563*efe51d0cSJohn Levon 15641f5207b7SJohn Levon custom_handle_variable = orig_custom_fn; 15651f5207b7SJohn Levon 15661f5207b7SJohn Levon cached_results[cache_idx].expr = expr; 1567*efe51d0cSJohn Levon cached_results[cache_idx].sval = sval; 15681f5207b7SJohn Levon cache_idx = (cache_idx + 1) % ARRAY_SIZE(cached_results); 15691f5207b7SJohn Levon 1570*efe51d0cSJohn Levon if (!sval.type) 15711f5207b7SJohn Levon return 0; 15721f5207b7SJohn Levon 1573*efe51d0cSJohn Levon *res_sval = sval; 15741f5207b7SJohn Levon return 1; 15751f5207b7SJohn Levon } 15761f5207b7SJohn Levon 1577*efe51d0cSJohn Levon static bool get_implied_value_internal(struct expression *expr, int *recurse_cnt, sval_t *res_sval) 15781f5207b7SJohn Levon { 15791f5207b7SJohn Levon struct range_list *rl; 15801f5207b7SJohn Levon 1581*efe51d0cSJohn Levon res_sval->type = NULL; 1582*efe51d0cSJohn Levon 1583*efe51d0cSJohn Levon if (!get_rl_sval(expr, RL_IMPLIED, recurse_cnt, &rl, res_sval)) 1584*efe51d0cSJohn Levon return false; 1585*efe51d0cSJohn Levon if (!res_sval->type && !rl_to_sval(rl, res_sval)) 1586*efe51d0cSJohn Levon return false; 1587*efe51d0cSJohn Levon return true; 15881f5207b7SJohn Levon } 15891f5207b7SJohn Levon 15901f5207b7SJohn Levon int get_implied_value(struct expression *expr, sval_t *sval) 15911f5207b7SJohn Levon { 15921f5207b7SJohn Levon struct range_list *rl; 15931f5207b7SJohn Levon 1594*efe51d0cSJohn Levon if (!get_rl_helper(expr, RL_IMPLIED, &rl) || 1595*efe51d0cSJohn Levon !rl_to_sval(rl, sval)) 15961f5207b7SJohn Levon return 0; 15971f5207b7SJohn Levon return 1; 15981f5207b7SJohn Levon } 15991f5207b7SJohn Levon 16001f5207b7SJohn Levon int get_implied_min(struct expression *expr, sval_t *sval) 16011f5207b7SJohn Levon { 16021f5207b7SJohn Levon struct range_list *rl; 16031f5207b7SJohn Levon 1604*efe51d0cSJohn Levon if (!get_rl_helper(expr, RL_IMPLIED, &rl) || !rl) 16051f5207b7SJohn Levon return 0; 16061f5207b7SJohn Levon *sval = rl_min(rl); 16071f5207b7SJohn Levon return 1; 16081f5207b7SJohn Levon } 16091f5207b7SJohn Levon 16101f5207b7SJohn Levon int get_implied_max(struct expression *expr, sval_t *sval) 16111f5207b7SJohn Levon { 16121f5207b7SJohn Levon struct range_list *rl; 16131f5207b7SJohn Levon 1614*efe51d0cSJohn Levon if (!get_rl_helper(expr, RL_IMPLIED, &rl) || !rl) 16151f5207b7SJohn Levon return 0; 16161f5207b7SJohn Levon *sval = rl_max(rl); 16171f5207b7SJohn Levon return 1; 16181f5207b7SJohn Levon } 16191f5207b7SJohn Levon 16201f5207b7SJohn Levon int get_implied_rl(struct expression *expr, struct range_list **rl) 16211f5207b7SJohn Levon { 1622*efe51d0cSJohn Levon if (!get_rl_helper(expr, RL_IMPLIED, rl) || !*rl) 1623*efe51d0cSJohn Levon return 0; 1624*efe51d0cSJohn Levon return 1; 16251f5207b7SJohn Levon } 16261f5207b7SJohn Levon 16271f5207b7SJohn Levon static int get_absolute_rl_internal(struct expression *expr, struct range_list **rl, int *recurse_cnt) 16281f5207b7SJohn Levon { 1629*efe51d0cSJohn Levon *rl = NULL; 1630*efe51d0cSJohn Levon get_rl_internal(expr, RL_ABSOLUTE, recurse_cnt, rl); 16311f5207b7SJohn Levon if (!*rl) 16321f5207b7SJohn Levon *rl = alloc_whole_rl(get_type(expr)); 16331f5207b7SJohn Levon return 1; 16341f5207b7SJohn Levon } 16351f5207b7SJohn Levon 16361f5207b7SJohn Levon int get_absolute_rl(struct expression *expr, struct range_list **rl) 16371f5207b7SJohn Levon { 1638*efe51d0cSJohn Levon *rl = NULL; 1639*efe51d0cSJohn Levon get_rl_helper(expr, RL_ABSOLUTE, rl); 16401f5207b7SJohn Levon if (!*rl) 16411f5207b7SJohn Levon *rl = alloc_whole_rl(get_type(expr)); 16421f5207b7SJohn Levon return 1; 16431f5207b7SJohn Levon } 16441f5207b7SJohn Levon 16451f5207b7SJohn Levon int get_real_absolute_rl(struct expression *expr, struct range_list **rl) 16461f5207b7SJohn Levon { 1647*efe51d0cSJohn Levon *rl = NULL; 1648*efe51d0cSJohn Levon get_rl_helper(expr, RL_REAL_ABSOLUTE, rl); 16491f5207b7SJohn Levon if (!*rl) 16501f5207b7SJohn Levon *rl = alloc_whole_rl(get_type(expr)); 16511f5207b7SJohn Levon return 1; 16521f5207b7SJohn Levon } 16531f5207b7SJohn Levon 16541f5207b7SJohn Levon int custom_get_absolute_rl(struct expression *expr, 16551f5207b7SJohn Levon struct range_list *(*fn)(struct expression *expr), 16561f5207b7SJohn Levon struct range_list **rl) 16571f5207b7SJohn Levon { 1658*efe51d0cSJohn Levon int ret; 16591f5207b7SJohn Levon 16601f5207b7SJohn Levon *rl = NULL; 16611f5207b7SJohn Levon custom_handle_variable = fn; 1662*efe51d0cSJohn Levon ret = get_rl_helper(expr, RL_REAL_ABSOLUTE, rl); 16631f5207b7SJohn Levon custom_handle_variable = NULL; 1664*efe51d0cSJohn Levon return ret; 16651f5207b7SJohn Levon } 16661f5207b7SJohn Levon 16671f5207b7SJohn Levon int get_implied_rl_var_sym(const char *var, struct symbol *sym, struct range_list **rl) 16681f5207b7SJohn Levon { 16691f5207b7SJohn Levon struct smatch_state *state; 16701f5207b7SJohn Levon 16711f5207b7SJohn Levon state = get_state(SMATCH_EXTRA, var, sym); 16721f5207b7SJohn Levon *rl = estate_rl(state); 16731f5207b7SJohn Levon if (*rl) 16741f5207b7SJohn Levon return 1; 16751f5207b7SJohn Levon return 0; 16761f5207b7SJohn Levon } 16771f5207b7SJohn Levon 16781f5207b7SJohn Levon int get_hard_max(struct expression *expr, sval_t *sval) 16791f5207b7SJohn Levon { 16801f5207b7SJohn Levon struct range_list *rl; 16811f5207b7SJohn Levon 1682*efe51d0cSJohn Levon if (!get_rl_helper(expr, RL_HARD, &rl) || !rl) 16831f5207b7SJohn Levon return 0; 16841f5207b7SJohn Levon *sval = rl_max(rl); 16851f5207b7SJohn Levon return 1; 16861f5207b7SJohn Levon } 16871f5207b7SJohn Levon 16881f5207b7SJohn Levon int get_fuzzy_min(struct expression *expr, sval_t *sval) 16891f5207b7SJohn Levon { 16901f5207b7SJohn Levon struct range_list *rl; 16911f5207b7SJohn Levon sval_t tmp; 16921f5207b7SJohn Levon 1693*efe51d0cSJohn Levon if (!get_rl_helper(expr, RL_FUZZY, &rl) || !rl) 16941f5207b7SJohn Levon return 0; 16951f5207b7SJohn Levon tmp = rl_min(rl); 16961f5207b7SJohn Levon if (sval_is_negative(tmp) && sval_is_min(tmp)) 16971f5207b7SJohn Levon return 0; 16981f5207b7SJohn Levon *sval = tmp; 16991f5207b7SJohn Levon return 1; 17001f5207b7SJohn Levon } 17011f5207b7SJohn Levon 17021f5207b7SJohn Levon int get_fuzzy_max(struct expression *expr, sval_t *sval) 17031f5207b7SJohn Levon { 17041f5207b7SJohn Levon struct range_list *rl; 17051f5207b7SJohn Levon sval_t max; 17061f5207b7SJohn Levon 1707*efe51d0cSJohn Levon if (!get_rl_helper(expr, RL_FUZZY, &rl) || !rl) 17081f5207b7SJohn Levon return 0; 17091f5207b7SJohn Levon max = rl_max(rl); 17101f5207b7SJohn Levon if (max.uvalue > INT_MAX - 10000) 17111f5207b7SJohn Levon return 0; 17121f5207b7SJohn Levon *sval = max; 17131f5207b7SJohn Levon return 1; 17141f5207b7SJohn Levon } 17151f5207b7SJohn Levon 17161f5207b7SJohn Levon int get_absolute_min(struct expression *expr, sval_t *sval) 17171f5207b7SJohn Levon { 17181f5207b7SJohn Levon struct range_list *rl; 17191f5207b7SJohn Levon struct symbol *type; 17201f5207b7SJohn Levon 17211f5207b7SJohn Levon type = get_type(expr); 17221f5207b7SJohn Levon if (!type) 17231f5207b7SJohn Levon type = &llong_ctype; // FIXME: this is wrong but places assume get type can't fail. 1724*efe51d0cSJohn Levon rl = NULL; 1725*efe51d0cSJohn Levon get_rl_helper(expr, RL_REAL_ABSOLUTE, &rl); 17261f5207b7SJohn Levon if (rl) 17271f5207b7SJohn Levon *sval = rl_min(rl); 17281f5207b7SJohn Levon else 17291f5207b7SJohn Levon *sval = sval_type_min(type); 17301f5207b7SJohn Levon 17311f5207b7SJohn Levon if (sval_cmp(*sval, sval_type_min(type)) < 0) 17321f5207b7SJohn Levon *sval = sval_type_min(type); 17331f5207b7SJohn Levon return 1; 17341f5207b7SJohn Levon } 17351f5207b7SJohn Levon 17361f5207b7SJohn Levon int get_absolute_max(struct expression *expr, sval_t *sval) 17371f5207b7SJohn Levon { 17381f5207b7SJohn Levon struct range_list *rl; 17391f5207b7SJohn Levon struct symbol *type; 17401f5207b7SJohn Levon 17411f5207b7SJohn Levon type = get_type(expr); 17421f5207b7SJohn Levon if (!type) 17431f5207b7SJohn Levon type = &llong_ctype; 1744*efe51d0cSJohn Levon rl = NULL; 1745*efe51d0cSJohn Levon get_rl_helper(expr, RL_REAL_ABSOLUTE, &rl); 17461f5207b7SJohn Levon if (rl) 17471f5207b7SJohn Levon *sval = rl_max(rl); 17481f5207b7SJohn Levon else 17491f5207b7SJohn Levon *sval = sval_type_max(type); 17501f5207b7SJohn Levon 17511f5207b7SJohn Levon if (sval_cmp(sval_type_max(type), *sval) < 0) 17521f5207b7SJohn Levon *sval = sval_type_max(type); 17531f5207b7SJohn Levon return 1; 17541f5207b7SJohn Levon } 17551f5207b7SJohn Levon 17561f5207b7SJohn Levon int known_condition_true(struct expression *expr) 17571f5207b7SJohn Levon { 17581f5207b7SJohn Levon sval_t tmp; 17591f5207b7SJohn Levon 17601f5207b7SJohn Levon if (!expr) 17611f5207b7SJohn Levon return 0; 17621f5207b7SJohn Levon 17631f5207b7SJohn Levon if (get_value(expr, &tmp) && tmp.value) 17641f5207b7SJohn Levon return 1; 17651f5207b7SJohn Levon 17661f5207b7SJohn Levon return 0; 17671f5207b7SJohn Levon } 17681f5207b7SJohn Levon 17691f5207b7SJohn Levon int known_condition_false(struct expression *expr) 17701f5207b7SJohn Levon { 17711f5207b7SJohn Levon if (!expr) 17721f5207b7SJohn Levon return 0; 17731f5207b7SJohn Levon 17741f5207b7SJohn Levon if (is_zero(expr)) 17751f5207b7SJohn Levon return 1; 17761f5207b7SJohn Levon 17771f5207b7SJohn Levon return 0; 17781f5207b7SJohn Levon } 17791f5207b7SJohn Levon 17801f5207b7SJohn Levon int implied_condition_true(struct expression *expr) 17811f5207b7SJohn Levon { 17821f5207b7SJohn Levon sval_t tmp; 17831f5207b7SJohn Levon 17841f5207b7SJohn Levon if (!expr) 17851f5207b7SJohn Levon return 0; 17861f5207b7SJohn Levon 17871f5207b7SJohn Levon if (known_condition_true(expr)) 17881f5207b7SJohn Levon return 1; 17891f5207b7SJohn Levon if (get_implied_value(expr, &tmp) && tmp.value) 17901f5207b7SJohn Levon return 1; 17911f5207b7SJohn Levon 17921f5207b7SJohn Levon if (expr->type == EXPR_POSTOP) 17931f5207b7SJohn Levon return implied_condition_true(expr->unop); 17941f5207b7SJohn Levon 17951f5207b7SJohn Levon if (expr->type == EXPR_PREOP && expr->op == SPECIAL_DECREMENT) 17961f5207b7SJohn Levon return implied_not_equal(expr->unop, 1); 17971f5207b7SJohn Levon if (expr->type == EXPR_PREOP && expr->op == SPECIAL_INCREMENT) 17981f5207b7SJohn Levon return implied_not_equal(expr->unop, -1); 17991f5207b7SJohn Levon 18001f5207b7SJohn Levon expr = strip_expr(expr); 18011f5207b7SJohn Levon switch (expr->type) { 18021f5207b7SJohn Levon case EXPR_COMPARE: 18031f5207b7SJohn Levon if (do_comparison(expr) == 1) 18041f5207b7SJohn Levon return 1; 18051f5207b7SJohn Levon break; 18061f5207b7SJohn Levon case EXPR_PREOP: 18071f5207b7SJohn Levon if (expr->op == '!') { 18081f5207b7SJohn Levon if (implied_condition_false(expr->unop)) 18091f5207b7SJohn Levon return 1; 18101f5207b7SJohn Levon break; 18111f5207b7SJohn Levon } 18121f5207b7SJohn Levon break; 18131f5207b7SJohn Levon default: 18141f5207b7SJohn Levon if (implied_not_equal(expr, 0) == 1) 18151f5207b7SJohn Levon return 1; 18161f5207b7SJohn Levon break; 18171f5207b7SJohn Levon } 18181f5207b7SJohn Levon return 0; 18191f5207b7SJohn Levon } 18201f5207b7SJohn Levon 18211f5207b7SJohn Levon int implied_condition_false(struct expression *expr) 18221f5207b7SJohn Levon { 18231f5207b7SJohn Levon struct expression *tmp; 18241f5207b7SJohn Levon sval_t sval; 18251f5207b7SJohn Levon 18261f5207b7SJohn Levon if (!expr) 18271f5207b7SJohn Levon return 0; 18281f5207b7SJohn Levon 18291f5207b7SJohn Levon if (known_condition_false(expr)) 18301f5207b7SJohn Levon return 1; 18311f5207b7SJohn Levon 18321f5207b7SJohn Levon switch (expr->type) { 18331f5207b7SJohn Levon case EXPR_COMPARE: 18341f5207b7SJohn Levon if (do_comparison(expr) == 2) 18351f5207b7SJohn Levon return 1; 18361f5207b7SJohn Levon case EXPR_PREOP: 18371f5207b7SJohn Levon if (expr->op == '!') { 18381f5207b7SJohn Levon if (implied_condition_true(expr->unop)) 18391f5207b7SJohn Levon return 1; 18401f5207b7SJohn Levon break; 18411f5207b7SJohn Levon } 18421f5207b7SJohn Levon tmp = strip_expr(expr); 18431f5207b7SJohn Levon if (tmp != expr) 18441f5207b7SJohn Levon return implied_condition_false(tmp); 18451f5207b7SJohn Levon break; 18461f5207b7SJohn Levon default: 18471f5207b7SJohn Levon if (get_implied_value(expr, &sval) && sval.value == 0) 18481f5207b7SJohn Levon return 1; 18491f5207b7SJohn Levon break; 18501f5207b7SJohn Levon } 18511f5207b7SJohn Levon return 0; 18521f5207b7SJohn Levon } 18531f5207b7SJohn Levon 18541f5207b7SJohn Levon 1855