1*1f5207b7SJohn Levon /* 2*1f5207b7SJohn Levon * Copyright (C) 2008 Dan Carpenter. 3*1f5207b7SJohn Levon * 4*1f5207b7SJohn Levon * This program is free software; you can redistribute it and/or 5*1f5207b7SJohn Levon * modify it under the terms of the GNU General Public License 6*1f5207b7SJohn Levon * as published by the Free Software Foundation; either version 2 7*1f5207b7SJohn Levon * of the License, or (at your option) any later version. 8*1f5207b7SJohn Levon * 9*1f5207b7SJohn Levon * This program is distributed in the hope that it will be useful, 10*1f5207b7SJohn Levon * but WITHOUT ANY WARRANTY; without even the implied warranty of 11*1f5207b7SJohn Levon * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12*1f5207b7SJohn Levon * GNU General Public License for more details. 13*1f5207b7SJohn Levon * 14*1f5207b7SJohn Levon * You should have received a copy of the GNU General Public License 15*1f5207b7SJohn Levon * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt 16*1f5207b7SJohn Levon */ 17*1f5207b7SJohn Levon 18*1f5207b7SJohn Levon /* 19*1f5207b7SJohn Levon * smatch_extra.c is supposed to track the value of every variable. 20*1f5207b7SJohn Levon * 21*1f5207b7SJohn Levon */ 22*1f5207b7SJohn Levon 23*1f5207b7SJohn Levon #define _GNU_SOURCE 24*1f5207b7SJohn Levon #include <string.h> 25*1f5207b7SJohn Levon 26*1f5207b7SJohn Levon #include <stdlib.h> 27*1f5207b7SJohn Levon #include <errno.h> 28*1f5207b7SJohn Levon #ifndef __USE_ISOC99 29*1f5207b7SJohn Levon #define __USE_ISOC99 30*1f5207b7SJohn Levon #endif 31*1f5207b7SJohn Levon #include <limits.h> 32*1f5207b7SJohn Levon #include "parse.h" 33*1f5207b7SJohn Levon #include "smatch.h" 34*1f5207b7SJohn Levon #include "smatch_slist.h" 35*1f5207b7SJohn Levon #include "smatch_extra.h" 36*1f5207b7SJohn Levon 37*1f5207b7SJohn Levon static int my_id; 38*1f5207b7SJohn Levon static int link_id; 39*1f5207b7SJohn Levon 40*1f5207b7SJohn Levon static void match_link_modify(struct sm_state *sm, struct expression *mod_expr); 41*1f5207b7SJohn Levon 42*1f5207b7SJohn Levon struct string_list *__ignored_macros = NULL; 43*1f5207b7SJohn Levon static int in_warn_on_macro(void) 44*1f5207b7SJohn Levon { 45*1f5207b7SJohn Levon struct statement *stmt; 46*1f5207b7SJohn Levon char *tmp; 47*1f5207b7SJohn Levon char *macro; 48*1f5207b7SJohn Levon 49*1f5207b7SJohn Levon stmt = get_current_statement(); 50*1f5207b7SJohn Levon if (!stmt) 51*1f5207b7SJohn Levon return 0; 52*1f5207b7SJohn Levon macro = get_macro_name(stmt->pos); 53*1f5207b7SJohn Levon if (!macro) 54*1f5207b7SJohn Levon return 0; 55*1f5207b7SJohn Levon 56*1f5207b7SJohn Levon FOR_EACH_PTR(__ignored_macros, tmp) { 57*1f5207b7SJohn Levon if (!strcmp(tmp, macro)) 58*1f5207b7SJohn Levon return 1; 59*1f5207b7SJohn Levon } END_FOR_EACH_PTR(tmp); 60*1f5207b7SJohn Levon return 0; 61*1f5207b7SJohn Levon } 62*1f5207b7SJohn Levon 63*1f5207b7SJohn Levon typedef void (mod_hook)(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state); 64*1f5207b7SJohn Levon DECLARE_PTR_LIST(void_fn_list, mod_hook *); 65*1f5207b7SJohn Levon static struct void_fn_list *extra_mod_hooks; 66*1f5207b7SJohn Levon static struct void_fn_list *extra_nomod_hooks; 67*1f5207b7SJohn Levon 68*1f5207b7SJohn Levon void add_extra_mod_hook(mod_hook *fn) 69*1f5207b7SJohn Levon { 70*1f5207b7SJohn Levon mod_hook **p = malloc(sizeof(mod_hook *)); 71*1f5207b7SJohn Levon *p = fn; 72*1f5207b7SJohn Levon add_ptr_list(&extra_mod_hooks, p); 73*1f5207b7SJohn Levon } 74*1f5207b7SJohn Levon 75*1f5207b7SJohn Levon void add_extra_nomod_hook(mod_hook *fn) 76*1f5207b7SJohn Levon { 77*1f5207b7SJohn Levon mod_hook **p = malloc(sizeof(mod_hook *)); 78*1f5207b7SJohn Levon *p = fn; 79*1f5207b7SJohn Levon add_ptr_list(&extra_nomod_hooks, p); 80*1f5207b7SJohn Levon } 81*1f5207b7SJohn Levon 82*1f5207b7SJohn Levon void call_extra_hooks(struct void_fn_list *hooks, const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state) 83*1f5207b7SJohn Levon { 84*1f5207b7SJohn Levon mod_hook **fn; 85*1f5207b7SJohn Levon 86*1f5207b7SJohn Levon FOR_EACH_PTR(hooks, fn) { 87*1f5207b7SJohn Levon (*fn)(name, sym, expr, state); 88*1f5207b7SJohn Levon } END_FOR_EACH_PTR(fn); 89*1f5207b7SJohn Levon } 90*1f5207b7SJohn Levon 91*1f5207b7SJohn Levon void call_extra_mod_hooks(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state) 92*1f5207b7SJohn Levon { 93*1f5207b7SJohn Levon call_extra_hooks(extra_mod_hooks, name, sym, expr, state); 94*1f5207b7SJohn Levon } 95*1f5207b7SJohn Levon 96*1f5207b7SJohn Levon void call_extra_nomod_hooks(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state) 97*1f5207b7SJohn Levon { 98*1f5207b7SJohn Levon call_extra_hooks(extra_nomod_hooks, name, sym, expr, state); 99*1f5207b7SJohn Levon } 100*1f5207b7SJohn Levon 101*1f5207b7SJohn Levon static bool in_param_set; 102*1f5207b7SJohn Levon void set_extra_mod_helper(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state) 103*1f5207b7SJohn Levon { 104*1f5207b7SJohn Levon remove_from_equiv(name, sym); 105*1f5207b7SJohn Levon call_extra_mod_hooks(name, sym, expr, state); 106*1f5207b7SJohn Levon if ((__in_fake_assign || in_param_set) && 107*1f5207b7SJohn Levon estate_is_unknown(state) && !get_state(SMATCH_EXTRA, name, sym)) 108*1f5207b7SJohn Levon return; 109*1f5207b7SJohn Levon set_state(SMATCH_EXTRA, name, sym, state); 110*1f5207b7SJohn Levon } 111*1f5207b7SJohn Levon 112*1f5207b7SJohn Levon static void set_extra_nomod_helper(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state) 113*1f5207b7SJohn Levon { 114*1f5207b7SJohn Levon call_extra_nomod_hooks(name, sym, expr, state); 115*1f5207b7SJohn Levon set_state(SMATCH_EXTRA, name, sym, state); 116*1f5207b7SJohn Levon } 117*1f5207b7SJohn Levon 118*1f5207b7SJohn Levon static char *get_pointed_at(const char *name, struct symbol *sym, struct symbol **new_sym) 119*1f5207b7SJohn Levon { 120*1f5207b7SJohn Levon struct expression *assigned; 121*1f5207b7SJohn Levon 122*1f5207b7SJohn Levon if (name[0] != '*') 123*1f5207b7SJohn Levon return NULL; 124*1f5207b7SJohn Levon if (strcmp(name + 1, sym->ident->name) != 0) 125*1f5207b7SJohn Levon return NULL; 126*1f5207b7SJohn Levon 127*1f5207b7SJohn Levon assigned = get_assigned_expr_name_sym(sym->ident->name, sym); 128*1f5207b7SJohn Levon if (!assigned) 129*1f5207b7SJohn Levon return NULL; 130*1f5207b7SJohn Levon assigned = strip_parens(assigned); 131*1f5207b7SJohn Levon if (assigned->type != EXPR_PREOP || assigned->op != '&') 132*1f5207b7SJohn Levon return NULL; 133*1f5207b7SJohn Levon 134*1f5207b7SJohn Levon return expr_to_var_sym(assigned->unop, new_sym); 135*1f5207b7SJohn Levon } 136*1f5207b7SJohn Levon 137*1f5207b7SJohn Levon char *get_other_name_sym(const char *name, struct symbol *sym, struct symbol **new_sym) 138*1f5207b7SJohn Levon { 139*1f5207b7SJohn Levon struct expression *assigned; 140*1f5207b7SJohn Levon char *orig_name = NULL; 141*1f5207b7SJohn Levon char buf[256]; 142*1f5207b7SJohn Levon char *ret = NULL; 143*1f5207b7SJohn Levon int skip; 144*1f5207b7SJohn Levon 145*1f5207b7SJohn Levon *new_sym = NULL; 146*1f5207b7SJohn Levon 147*1f5207b7SJohn Levon if (!sym || !sym->ident) 148*1f5207b7SJohn Levon return NULL; 149*1f5207b7SJohn Levon 150*1f5207b7SJohn Levon ret = get_pointed_at(name, sym, new_sym); 151*1f5207b7SJohn Levon if (ret) 152*1f5207b7SJohn Levon return ret; 153*1f5207b7SJohn Levon 154*1f5207b7SJohn Levon skip = strlen(sym->ident->name); 155*1f5207b7SJohn Levon if (name[skip] != '-' || name[skip + 1] != '>') 156*1f5207b7SJohn Levon return NULL; 157*1f5207b7SJohn Levon skip += 2; 158*1f5207b7SJohn Levon 159*1f5207b7SJohn Levon assigned = get_assigned_expr_name_sym(sym->ident->name, sym); 160*1f5207b7SJohn Levon if (!assigned) 161*1f5207b7SJohn Levon return NULL; 162*1f5207b7SJohn Levon if (assigned->type == EXPR_CALL) 163*1f5207b7SJohn Levon return map_call_to_other_name_sym(name, sym, new_sym); 164*1f5207b7SJohn Levon if (assigned->type == EXPR_PREOP || assigned->op == '&') { 165*1f5207b7SJohn Levon 166*1f5207b7SJohn Levon orig_name = expr_to_var_sym(assigned, new_sym); 167*1f5207b7SJohn Levon if (!orig_name || !*new_sym) 168*1f5207b7SJohn Levon goto free; 169*1f5207b7SJohn Levon 170*1f5207b7SJohn Levon snprintf(buf, sizeof(buf), "%s.%s", orig_name + 1, name + skip); 171*1f5207b7SJohn Levon ret = alloc_string(buf); 172*1f5207b7SJohn Levon free_string(orig_name); 173*1f5207b7SJohn Levon return ret; 174*1f5207b7SJohn Levon } 175*1f5207b7SJohn Levon 176*1f5207b7SJohn Levon if (assigned->type != EXPR_DEREF) 177*1f5207b7SJohn Levon goto free; 178*1f5207b7SJohn Levon 179*1f5207b7SJohn Levon orig_name = expr_to_var_sym(assigned, new_sym); 180*1f5207b7SJohn Levon if (!orig_name || !*new_sym) 181*1f5207b7SJohn Levon goto free; 182*1f5207b7SJohn Levon 183*1f5207b7SJohn Levon snprintf(buf, sizeof(buf), "%s->%s", orig_name, name + skip); 184*1f5207b7SJohn Levon ret = alloc_string(buf); 185*1f5207b7SJohn Levon free_string(orig_name); 186*1f5207b7SJohn Levon return ret; 187*1f5207b7SJohn Levon 188*1f5207b7SJohn Levon free: 189*1f5207b7SJohn Levon free_string(orig_name); 190*1f5207b7SJohn Levon return NULL; 191*1f5207b7SJohn Levon } 192*1f5207b7SJohn Levon 193*1f5207b7SJohn Levon void set_extra_mod(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state) 194*1f5207b7SJohn Levon { 195*1f5207b7SJohn Levon char *new_name; 196*1f5207b7SJohn Levon struct symbol *new_sym; 197*1f5207b7SJohn Levon 198*1f5207b7SJohn Levon set_extra_mod_helper(name, sym, expr, state); 199*1f5207b7SJohn Levon new_name = get_other_name_sym(name, sym, &new_sym); 200*1f5207b7SJohn Levon if (new_name && new_sym) 201*1f5207b7SJohn Levon set_extra_mod_helper(new_name, new_sym, expr, state); 202*1f5207b7SJohn Levon free_string(new_name); 203*1f5207b7SJohn Levon } 204*1f5207b7SJohn Levon 205*1f5207b7SJohn Levon static struct expression *chunk_get_array_base(struct expression *expr) 206*1f5207b7SJohn Levon { 207*1f5207b7SJohn Levon /* 208*1f5207b7SJohn Levon * The problem with is_array() is that it only returns true for things 209*1f5207b7SJohn Levon * like foo[1] but not for foo[1].bar. 210*1f5207b7SJohn Levon * 211*1f5207b7SJohn Levon */ 212*1f5207b7SJohn Levon expr = strip_expr(expr); 213*1f5207b7SJohn Levon while (expr && expr->type == EXPR_DEREF) 214*1f5207b7SJohn Levon expr = strip_expr(expr->deref); 215*1f5207b7SJohn Levon return get_array_base(expr); 216*1f5207b7SJohn Levon } 217*1f5207b7SJohn Levon 218*1f5207b7SJohn Levon static int chunk_has_array(struct expression *expr) 219*1f5207b7SJohn Levon { 220*1f5207b7SJohn Levon return !!chunk_get_array_base(expr); 221*1f5207b7SJohn Levon } 222*1f5207b7SJohn Levon 223*1f5207b7SJohn Levon static void clear_array_states(struct expression *array) 224*1f5207b7SJohn Levon { 225*1f5207b7SJohn Levon struct sm_state *sm; 226*1f5207b7SJohn Levon 227*1f5207b7SJohn Levon sm = get_sm_state_expr(link_id, array); 228*1f5207b7SJohn Levon if (sm) 229*1f5207b7SJohn Levon match_link_modify(sm, NULL); 230*1f5207b7SJohn Levon } 231*1f5207b7SJohn Levon 232*1f5207b7SJohn Levon static void set_extra_array_mod(struct expression *expr, struct smatch_state *state) 233*1f5207b7SJohn Levon { 234*1f5207b7SJohn Levon struct expression *array; 235*1f5207b7SJohn Levon struct var_sym_list *vsl; 236*1f5207b7SJohn Levon struct var_sym *vs; 237*1f5207b7SJohn Levon char *name; 238*1f5207b7SJohn Levon struct symbol *sym; 239*1f5207b7SJohn Levon 240*1f5207b7SJohn Levon array = chunk_get_array_base(expr); 241*1f5207b7SJohn Levon 242*1f5207b7SJohn Levon name = expr_to_chunk_sym_vsl(expr, &sym, &vsl); 243*1f5207b7SJohn Levon if (!name || !vsl) { 244*1f5207b7SJohn Levon clear_array_states(array); 245*1f5207b7SJohn Levon goto free; 246*1f5207b7SJohn Levon } 247*1f5207b7SJohn Levon 248*1f5207b7SJohn Levon FOR_EACH_PTR(vsl, vs) { 249*1f5207b7SJohn Levon store_link(link_id, vs->var, vs->sym, name, sym); 250*1f5207b7SJohn Levon } END_FOR_EACH_PTR(vs); 251*1f5207b7SJohn Levon 252*1f5207b7SJohn Levon call_extra_mod_hooks(name, sym, expr, state); 253*1f5207b7SJohn Levon set_state(SMATCH_EXTRA, name, sym, state); 254*1f5207b7SJohn Levon free: 255*1f5207b7SJohn Levon free_string(name); 256*1f5207b7SJohn Levon } 257*1f5207b7SJohn Levon 258*1f5207b7SJohn Levon void set_extra_expr_mod(struct expression *expr, struct smatch_state *state) 259*1f5207b7SJohn Levon { 260*1f5207b7SJohn Levon struct symbol *sym; 261*1f5207b7SJohn Levon char *name; 262*1f5207b7SJohn Levon 263*1f5207b7SJohn Levon if (chunk_has_array(expr)) { 264*1f5207b7SJohn Levon set_extra_array_mod(expr, state); 265*1f5207b7SJohn Levon return; 266*1f5207b7SJohn Levon } 267*1f5207b7SJohn Levon 268*1f5207b7SJohn Levon expr = strip_expr(expr); 269*1f5207b7SJohn Levon name = expr_to_var_sym(expr, &sym); 270*1f5207b7SJohn Levon if (!name || !sym) 271*1f5207b7SJohn Levon goto free; 272*1f5207b7SJohn Levon set_extra_mod(name, sym, expr, state); 273*1f5207b7SJohn Levon free: 274*1f5207b7SJohn Levon free_string(name); 275*1f5207b7SJohn Levon } 276*1f5207b7SJohn Levon 277*1f5207b7SJohn Levon void set_extra_nomod(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state) 278*1f5207b7SJohn Levon { 279*1f5207b7SJohn Levon char *new_name; 280*1f5207b7SJohn Levon struct symbol *new_sym; 281*1f5207b7SJohn Levon struct relation *rel; 282*1f5207b7SJohn Levon struct smatch_state *orig_state; 283*1f5207b7SJohn Levon 284*1f5207b7SJohn Levon orig_state = get_state(SMATCH_EXTRA, name, sym); 285*1f5207b7SJohn Levon 286*1f5207b7SJohn Levon /* don't save unknown states if leaving it blank is the same */ 287*1f5207b7SJohn Levon if (!orig_state && estate_is_unknown(state)) 288*1f5207b7SJohn Levon return; 289*1f5207b7SJohn Levon 290*1f5207b7SJohn Levon new_name = get_other_name_sym(name, sym, &new_sym); 291*1f5207b7SJohn Levon if (new_name && new_sym) 292*1f5207b7SJohn Levon set_extra_nomod_helper(new_name, new_sym, expr, state); 293*1f5207b7SJohn Levon free_string(new_name); 294*1f5207b7SJohn Levon 295*1f5207b7SJohn Levon if (!estate_related(orig_state)) { 296*1f5207b7SJohn Levon set_extra_nomod_helper(name, sym, expr, state); 297*1f5207b7SJohn Levon return; 298*1f5207b7SJohn Levon } 299*1f5207b7SJohn Levon 300*1f5207b7SJohn Levon set_related(state, estate_related(orig_state)); 301*1f5207b7SJohn Levon FOR_EACH_PTR(estate_related(orig_state), rel) { 302*1f5207b7SJohn Levon struct smatch_state *estate; 303*1f5207b7SJohn Levon 304*1f5207b7SJohn Levon if (option_debug_related) 305*1f5207b7SJohn Levon sm_msg("%s updating related %s to %s", name, rel->name, state->name); 306*1f5207b7SJohn Levon estate = get_state(SMATCH_EXTRA, rel->name, rel->sym); 307*1f5207b7SJohn Levon if (!estate) 308*1f5207b7SJohn Levon continue; 309*1f5207b7SJohn Levon set_extra_nomod_helper(rel->name, rel->sym, expr, clone_estate_cast(estate_type(estate), state)); 310*1f5207b7SJohn Levon } END_FOR_EACH_PTR(rel); 311*1f5207b7SJohn Levon } 312*1f5207b7SJohn Levon 313*1f5207b7SJohn Levon void set_extra_nomod_vsl(const char *name, struct symbol *sym, struct var_sym_list *vsl, struct expression *expr, struct smatch_state *state) 314*1f5207b7SJohn Levon { 315*1f5207b7SJohn Levon struct var_sym *vs; 316*1f5207b7SJohn Levon 317*1f5207b7SJohn Levon FOR_EACH_PTR(vsl, vs) { 318*1f5207b7SJohn Levon store_link(link_id, vs->var, vs->sym, name, sym); 319*1f5207b7SJohn Levon } END_FOR_EACH_PTR(vs); 320*1f5207b7SJohn Levon 321*1f5207b7SJohn Levon set_extra_nomod(name, sym, expr, state); 322*1f5207b7SJohn Levon } 323*1f5207b7SJohn Levon 324*1f5207b7SJohn Levon /* 325*1f5207b7SJohn Levon * This is for return_implies_state() hooks which modify a SMATCH_EXTRA state 326*1f5207b7SJohn Levon */ 327*1f5207b7SJohn Levon void set_extra_expr_nomod(struct expression *expr, struct smatch_state *state) 328*1f5207b7SJohn Levon { 329*1f5207b7SJohn Levon struct var_sym_list *vsl; 330*1f5207b7SJohn Levon struct var_sym *vs; 331*1f5207b7SJohn Levon char *name; 332*1f5207b7SJohn Levon struct symbol *sym; 333*1f5207b7SJohn Levon 334*1f5207b7SJohn Levon name = expr_to_chunk_sym_vsl(expr, &sym, &vsl); 335*1f5207b7SJohn Levon if (!name || !vsl) 336*1f5207b7SJohn Levon goto free; 337*1f5207b7SJohn Levon FOR_EACH_PTR(vsl, vs) { 338*1f5207b7SJohn Levon store_link(link_id, vs->var, vs->sym, name, sym); 339*1f5207b7SJohn Levon } END_FOR_EACH_PTR(vs); 340*1f5207b7SJohn Levon 341*1f5207b7SJohn Levon set_extra_nomod(name, sym, expr, state); 342*1f5207b7SJohn Levon free: 343*1f5207b7SJohn Levon free_string(name); 344*1f5207b7SJohn Levon } 345*1f5207b7SJohn Levon 346*1f5207b7SJohn Levon static void set_extra_true_false(const char *name, struct symbol *sym, 347*1f5207b7SJohn Levon struct smatch_state *true_state, 348*1f5207b7SJohn Levon struct smatch_state *false_state) 349*1f5207b7SJohn Levon { 350*1f5207b7SJohn Levon char *new_name; 351*1f5207b7SJohn Levon struct symbol *new_sym; 352*1f5207b7SJohn Levon struct relation *rel; 353*1f5207b7SJohn Levon struct smatch_state *orig_state; 354*1f5207b7SJohn Levon 355*1f5207b7SJohn Levon if (!true_state && !false_state) 356*1f5207b7SJohn Levon return; 357*1f5207b7SJohn Levon 358*1f5207b7SJohn Levon if (in_warn_on_macro()) 359*1f5207b7SJohn Levon return; 360*1f5207b7SJohn Levon 361*1f5207b7SJohn Levon new_name = get_other_name_sym(name, sym, &new_sym); 362*1f5207b7SJohn Levon if (new_name && new_sym) 363*1f5207b7SJohn Levon set_true_false_states(SMATCH_EXTRA, new_name, new_sym, true_state, false_state); 364*1f5207b7SJohn Levon free_string(new_name); 365*1f5207b7SJohn Levon 366*1f5207b7SJohn Levon orig_state = get_state(SMATCH_EXTRA, name, sym); 367*1f5207b7SJohn Levon 368*1f5207b7SJohn Levon if (!estate_related(orig_state)) { 369*1f5207b7SJohn Levon set_true_false_states(SMATCH_EXTRA, name, sym, true_state, false_state); 370*1f5207b7SJohn Levon return; 371*1f5207b7SJohn Levon } 372*1f5207b7SJohn Levon 373*1f5207b7SJohn Levon if (true_state) 374*1f5207b7SJohn Levon set_related(true_state, estate_related(orig_state)); 375*1f5207b7SJohn Levon if (false_state) 376*1f5207b7SJohn Levon set_related(false_state, estate_related(orig_state)); 377*1f5207b7SJohn Levon 378*1f5207b7SJohn Levon FOR_EACH_PTR(estate_related(orig_state), rel) { 379*1f5207b7SJohn Levon set_true_false_states(SMATCH_EXTRA, rel->name, rel->sym, 380*1f5207b7SJohn Levon true_state, false_state); 381*1f5207b7SJohn Levon } END_FOR_EACH_PTR(rel); 382*1f5207b7SJohn Levon } 383*1f5207b7SJohn Levon 384*1f5207b7SJohn Levon static void set_extra_chunk_true_false(struct expression *expr, 385*1f5207b7SJohn Levon struct smatch_state *true_state, 386*1f5207b7SJohn Levon struct smatch_state *false_state) 387*1f5207b7SJohn Levon { 388*1f5207b7SJohn Levon struct var_sym_list *vsl; 389*1f5207b7SJohn Levon struct var_sym *vs; 390*1f5207b7SJohn Levon struct symbol *type; 391*1f5207b7SJohn Levon char *name; 392*1f5207b7SJohn Levon struct symbol *sym; 393*1f5207b7SJohn Levon 394*1f5207b7SJohn Levon if (in_warn_on_macro()) 395*1f5207b7SJohn Levon return; 396*1f5207b7SJohn Levon 397*1f5207b7SJohn Levon type = get_type(expr); 398*1f5207b7SJohn Levon if (!type) 399*1f5207b7SJohn Levon return; 400*1f5207b7SJohn Levon 401*1f5207b7SJohn Levon name = expr_to_chunk_sym_vsl(expr, &sym, &vsl); 402*1f5207b7SJohn Levon if (!name || !vsl) 403*1f5207b7SJohn Levon goto free; 404*1f5207b7SJohn Levon FOR_EACH_PTR(vsl, vs) { 405*1f5207b7SJohn Levon store_link(link_id, vs->var, vs->sym, name, sym); 406*1f5207b7SJohn Levon } END_FOR_EACH_PTR(vs); 407*1f5207b7SJohn Levon 408*1f5207b7SJohn Levon set_true_false_states(SMATCH_EXTRA, name, sym, 409*1f5207b7SJohn Levon clone_estate(true_state), 410*1f5207b7SJohn Levon clone_estate(false_state)); 411*1f5207b7SJohn Levon free: 412*1f5207b7SJohn Levon free_string(name); 413*1f5207b7SJohn Levon } 414*1f5207b7SJohn Levon 415*1f5207b7SJohn Levon static void set_extra_expr_true_false(struct expression *expr, 416*1f5207b7SJohn Levon struct smatch_state *true_state, 417*1f5207b7SJohn Levon struct smatch_state *false_state) 418*1f5207b7SJohn Levon { 419*1f5207b7SJohn Levon char *name; 420*1f5207b7SJohn Levon struct symbol *sym; 421*1f5207b7SJohn Levon sval_t sval; 422*1f5207b7SJohn Levon 423*1f5207b7SJohn Levon if (!true_state && !false_state) 424*1f5207b7SJohn Levon return; 425*1f5207b7SJohn Levon 426*1f5207b7SJohn Levon if (get_value(expr, &sval)) 427*1f5207b7SJohn Levon return; 428*1f5207b7SJohn Levon 429*1f5207b7SJohn Levon expr = strip_expr(expr); 430*1f5207b7SJohn Levon name = expr_to_var_sym(expr, &sym); 431*1f5207b7SJohn Levon if (!name || !sym) { 432*1f5207b7SJohn Levon free_string(name); 433*1f5207b7SJohn Levon set_extra_chunk_true_false(expr, true_state, false_state); 434*1f5207b7SJohn Levon return; 435*1f5207b7SJohn Levon } 436*1f5207b7SJohn Levon set_extra_true_false(name, sym, true_state, false_state); 437*1f5207b7SJohn Levon free_string(name); 438*1f5207b7SJohn Levon } 439*1f5207b7SJohn Levon 440*1f5207b7SJohn Levon static int get_countdown_info(struct expression *condition, struct expression **unop, int *op, sval_t *right) 441*1f5207b7SJohn Levon { 442*1f5207b7SJohn Levon struct expression *unop_expr; 443*1f5207b7SJohn Levon int comparison; 444*1f5207b7SJohn Levon sval_t limit; 445*1f5207b7SJohn Levon 446*1f5207b7SJohn Levon right->type = &int_ctype; 447*1f5207b7SJohn Levon right->value = 0; 448*1f5207b7SJohn Levon 449*1f5207b7SJohn Levon condition = strip_expr(condition); 450*1f5207b7SJohn Levon 451*1f5207b7SJohn Levon if (condition->type == EXPR_COMPARE) { 452*1f5207b7SJohn Levon comparison = remove_unsigned_from_comparison(condition->op); 453*1f5207b7SJohn Levon 454*1f5207b7SJohn Levon if (comparison != SPECIAL_GTE && comparison != '>') 455*1f5207b7SJohn Levon return 0; 456*1f5207b7SJohn Levon if (!get_value(condition->right, &limit)) 457*1f5207b7SJohn Levon return 0; 458*1f5207b7SJohn Levon 459*1f5207b7SJohn Levon unop_expr = condition->left; 460*1f5207b7SJohn Levon if (unop_expr->type != EXPR_PREOP && unop_expr->type != EXPR_POSTOP) 461*1f5207b7SJohn Levon return 0; 462*1f5207b7SJohn Levon if (unop_expr->op != SPECIAL_DECREMENT) 463*1f5207b7SJohn Levon return 0; 464*1f5207b7SJohn Levon 465*1f5207b7SJohn Levon *unop = unop_expr; 466*1f5207b7SJohn Levon *op = comparison; 467*1f5207b7SJohn Levon *right = limit; 468*1f5207b7SJohn Levon 469*1f5207b7SJohn Levon return 1; 470*1f5207b7SJohn Levon } 471*1f5207b7SJohn Levon 472*1f5207b7SJohn Levon if (condition->type != EXPR_PREOP && condition->type != EXPR_POSTOP) 473*1f5207b7SJohn Levon return 0; 474*1f5207b7SJohn Levon if (condition->op != SPECIAL_DECREMENT) 475*1f5207b7SJohn Levon return 0; 476*1f5207b7SJohn Levon 477*1f5207b7SJohn Levon *unop = condition; 478*1f5207b7SJohn Levon *op = '>'; 479*1f5207b7SJohn Levon 480*1f5207b7SJohn Levon return 1; 481*1f5207b7SJohn Levon } 482*1f5207b7SJohn Levon 483*1f5207b7SJohn Levon static struct sm_state *handle_canonical_while_count_down(struct statement *loop) 484*1f5207b7SJohn Levon { 485*1f5207b7SJohn Levon struct expression *iter_var; 486*1f5207b7SJohn Levon struct expression *condition, *unop; 487*1f5207b7SJohn Levon struct sm_state *sm; 488*1f5207b7SJohn Levon struct smatch_state *estate; 489*1f5207b7SJohn Levon int op; 490*1f5207b7SJohn Levon sval_t start, right; 491*1f5207b7SJohn Levon 492*1f5207b7SJohn Levon right.type = &int_ctype; 493*1f5207b7SJohn Levon right.value = 0; 494*1f5207b7SJohn Levon 495*1f5207b7SJohn Levon condition = strip_expr(loop->iterator_pre_condition); 496*1f5207b7SJohn Levon if (!condition) 497*1f5207b7SJohn Levon return NULL; 498*1f5207b7SJohn Levon 499*1f5207b7SJohn Levon if (!get_countdown_info(condition, &unop, &op, &right)) 500*1f5207b7SJohn Levon return NULL; 501*1f5207b7SJohn Levon 502*1f5207b7SJohn Levon iter_var = unop->unop; 503*1f5207b7SJohn Levon 504*1f5207b7SJohn Levon sm = get_sm_state_expr(SMATCH_EXTRA, iter_var); 505*1f5207b7SJohn Levon if (!sm) 506*1f5207b7SJohn Levon return NULL; 507*1f5207b7SJohn Levon if (sval_cmp(estate_min(sm->state), right) < 0) 508*1f5207b7SJohn Levon return NULL; 509*1f5207b7SJohn Levon start = estate_max(sm->state); 510*1f5207b7SJohn Levon if (sval_cmp(start, right) <= 0) 511*1f5207b7SJohn Levon return NULL; 512*1f5207b7SJohn Levon if (!sval_is_max(start)) 513*1f5207b7SJohn Levon start.value--; 514*1f5207b7SJohn Levon 515*1f5207b7SJohn Levon if (op == SPECIAL_GTE) 516*1f5207b7SJohn Levon right.value--; 517*1f5207b7SJohn Levon 518*1f5207b7SJohn Levon if (unop->type == EXPR_PREOP) { 519*1f5207b7SJohn Levon right.value++; 520*1f5207b7SJohn Levon estate = alloc_estate_range(right, start); 521*1f5207b7SJohn Levon if (estate_has_hard_max(sm->state)) 522*1f5207b7SJohn Levon estate_set_hard_max(estate); 523*1f5207b7SJohn Levon estate_copy_fuzzy_max(estate, sm->state); 524*1f5207b7SJohn Levon set_extra_expr_mod(iter_var, estate); 525*1f5207b7SJohn Levon } 526*1f5207b7SJohn Levon if (unop->type == EXPR_POSTOP) { 527*1f5207b7SJohn Levon estate = alloc_estate_range(right, start); 528*1f5207b7SJohn Levon if (estate_has_hard_max(sm->state)) 529*1f5207b7SJohn Levon estate_set_hard_max(estate); 530*1f5207b7SJohn Levon estate_copy_fuzzy_max(estate, sm->state); 531*1f5207b7SJohn Levon set_extra_expr_mod(iter_var, estate); 532*1f5207b7SJohn Levon } 533*1f5207b7SJohn Levon return get_sm_state_expr(SMATCH_EXTRA, iter_var); 534*1f5207b7SJohn Levon } 535*1f5207b7SJohn Levon 536*1f5207b7SJohn Levon static struct sm_state *handle_canonical_for_inc(struct expression *iter_expr, 537*1f5207b7SJohn Levon struct expression *condition) 538*1f5207b7SJohn Levon { 539*1f5207b7SJohn Levon struct expression *iter_var; 540*1f5207b7SJohn Levon struct sm_state *sm; 541*1f5207b7SJohn Levon struct smatch_state *estate; 542*1f5207b7SJohn Levon sval_t start, end, max; 543*1f5207b7SJohn Levon 544*1f5207b7SJohn Levon iter_var = iter_expr->unop; 545*1f5207b7SJohn Levon sm = get_sm_state_expr(SMATCH_EXTRA, iter_var); 546*1f5207b7SJohn Levon if (!sm) 547*1f5207b7SJohn Levon return NULL; 548*1f5207b7SJohn Levon if (!estate_get_single_value(sm->state, &start)) 549*1f5207b7SJohn Levon return NULL; 550*1f5207b7SJohn Levon if (get_implied_max(condition->right, &end)) 551*1f5207b7SJohn Levon end = sval_cast(get_type(iter_var), end); 552*1f5207b7SJohn Levon else 553*1f5207b7SJohn Levon end = sval_type_max(get_type(iter_var)); 554*1f5207b7SJohn Levon 555*1f5207b7SJohn Levon if (get_sm_state_expr(SMATCH_EXTRA, condition->left) != sm) 556*1f5207b7SJohn Levon return NULL; 557*1f5207b7SJohn Levon 558*1f5207b7SJohn Levon switch (condition->op) { 559*1f5207b7SJohn Levon case SPECIAL_UNSIGNED_LT: 560*1f5207b7SJohn Levon case SPECIAL_NOTEQUAL: 561*1f5207b7SJohn Levon case '<': 562*1f5207b7SJohn Levon if (!sval_is_min(end)) 563*1f5207b7SJohn Levon end.value--; 564*1f5207b7SJohn Levon break; 565*1f5207b7SJohn Levon case SPECIAL_UNSIGNED_LTE: 566*1f5207b7SJohn Levon case SPECIAL_LTE: 567*1f5207b7SJohn Levon break; 568*1f5207b7SJohn Levon default: 569*1f5207b7SJohn Levon return NULL; 570*1f5207b7SJohn Levon } 571*1f5207b7SJohn Levon if (sval_cmp(end, start) < 0) 572*1f5207b7SJohn Levon return NULL; 573*1f5207b7SJohn Levon estate = alloc_estate_range(start, end); 574*1f5207b7SJohn Levon if (get_hard_max(condition->right, &max)) { 575*1f5207b7SJohn Levon estate_set_hard_max(estate); 576*1f5207b7SJohn Levon if (condition->op == '<' || 577*1f5207b7SJohn Levon condition->op == SPECIAL_UNSIGNED_LT || 578*1f5207b7SJohn Levon condition->op == SPECIAL_NOTEQUAL) 579*1f5207b7SJohn Levon max.value--; 580*1f5207b7SJohn Levon estate_set_fuzzy_max(estate, max); 581*1f5207b7SJohn Levon } 582*1f5207b7SJohn Levon set_extra_expr_mod(iter_var, estate); 583*1f5207b7SJohn Levon return get_sm_state_expr(SMATCH_EXTRA, iter_var); 584*1f5207b7SJohn Levon } 585*1f5207b7SJohn Levon 586*1f5207b7SJohn Levon static struct sm_state *handle_canonical_for_dec(struct expression *iter_expr, 587*1f5207b7SJohn Levon struct expression *condition) 588*1f5207b7SJohn Levon { 589*1f5207b7SJohn Levon struct expression *iter_var; 590*1f5207b7SJohn Levon struct sm_state *sm; 591*1f5207b7SJohn Levon struct smatch_state *estate; 592*1f5207b7SJohn Levon sval_t start, end; 593*1f5207b7SJohn Levon 594*1f5207b7SJohn Levon iter_var = iter_expr->unop; 595*1f5207b7SJohn Levon sm = get_sm_state_expr(SMATCH_EXTRA, iter_var); 596*1f5207b7SJohn Levon if (!sm) 597*1f5207b7SJohn Levon return NULL; 598*1f5207b7SJohn Levon if (!estate_get_single_value(sm->state, &start)) 599*1f5207b7SJohn Levon return NULL; 600*1f5207b7SJohn Levon if (!get_implied_min(condition->right, &end)) 601*1f5207b7SJohn Levon end = sval_type_min(get_type(iter_var)); 602*1f5207b7SJohn Levon if (get_sm_state_expr(SMATCH_EXTRA, condition->left) != sm) 603*1f5207b7SJohn Levon return NULL; 604*1f5207b7SJohn Levon 605*1f5207b7SJohn Levon switch (condition->op) { 606*1f5207b7SJohn Levon case SPECIAL_NOTEQUAL: 607*1f5207b7SJohn Levon case '>': 608*1f5207b7SJohn Levon if (!sval_is_min(end) && !sval_is_max(end)) 609*1f5207b7SJohn Levon end.value++; 610*1f5207b7SJohn Levon break; 611*1f5207b7SJohn Levon case SPECIAL_GTE: 612*1f5207b7SJohn Levon break; 613*1f5207b7SJohn Levon default: 614*1f5207b7SJohn Levon return NULL; 615*1f5207b7SJohn Levon } 616*1f5207b7SJohn Levon if (sval_cmp(end, start) > 0) 617*1f5207b7SJohn Levon return NULL; 618*1f5207b7SJohn Levon estate = alloc_estate_range(end, start); 619*1f5207b7SJohn Levon estate_set_hard_max(estate); 620*1f5207b7SJohn Levon estate_set_fuzzy_max(estate, estate_get_fuzzy_max(estate)); 621*1f5207b7SJohn Levon set_extra_expr_mod(iter_var, estate); 622*1f5207b7SJohn Levon return get_sm_state_expr(SMATCH_EXTRA, iter_var); 623*1f5207b7SJohn Levon } 624*1f5207b7SJohn Levon 625*1f5207b7SJohn Levon static struct sm_state *handle_canonical_for_loops(struct statement *loop) 626*1f5207b7SJohn Levon { 627*1f5207b7SJohn Levon struct expression *iter_expr; 628*1f5207b7SJohn Levon struct expression *condition; 629*1f5207b7SJohn Levon 630*1f5207b7SJohn Levon if (!loop->iterator_post_statement) 631*1f5207b7SJohn Levon return NULL; 632*1f5207b7SJohn Levon if (loop->iterator_post_statement->type != STMT_EXPRESSION) 633*1f5207b7SJohn Levon return NULL; 634*1f5207b7SJohn Levon iter_expr = loop->iterator_post_statement->expression; 635*1f5207b7SJohn Levon if (!loop->iterator_pre_condition) 636*1f5207b7SJohn Levon return NULL; 637*1f5207b7SJohn Levon if (loop->iterator_pre_condition->type != EXPR_COMPARE) 638*1f5207b7SJohn Levon return NULL; 639*1f5207b7SJohn Levon condition = loop->iterator_pre_condition; 640*1f5207b7SJohn Levon 641*1f5207b7SJohn Levon if (iter_expr->op == SPECIAL_INCREMENT) 642*1f5207b7SJohn Levon return handle_canonical_for_inc(iter_expr, condition); 643*1f5207b7SJohn Levon if (iter_expr->op == SPECIAL_DECREMENT) 644*1f5207b7SJohn Levon return handle_canonical_for_dec(iter_expr, condition); 645*1f5207b7SJohn Levon return NULL; 646*1f5207b7SJohn Levon } 647*1f5207b7SJohn Levon 648*1f5207b7SJohn Levon struct sm_state *__extra_handle_canonical_loops(struct statement *loop, struct stree **stree) 649*1f5207b7SJohn Levon { 650*1f5207b7SJohn Levon struct sm_state *ret; 651*1f5207b7SJohn Levon 652*1f5207b7SJohn Levon /* 653*1f5207b7SJohn Levon * Canonical loops are a hack. The proper way to handle this is to 654*1f5207b7SJohn Levon * use two passes, but unfortunately, doing two passes makes parsing 655*1f5207b7SJohn Levon * code twice as slow. 656*1f5207b7SJohn Levon * 657*1f5207b7SJohn Levon * What we do is we set the inside state here, which overwrites whatever 658*1f5207b7SJohn Levon * __extra_match_condition() does. Then we set the outside state in 659*1f5207b7SJohn Levon * __extra_pre_loop_hook_after(). 660*1f5207b7SJohn Levon * 661*1f5207b7SJohn Levon */ 662*1f5207b7SJohn Levon __push_fake_cur_stree(); 663*1f5207b7SJohn Levon if (!loop->iterator_post_statement) 664*1f5207b7SJohn Levon ret = handle_canonical_while_count_down(loop); 665*1f5207b7SJohn Levon else 666*1f5207b7SJohn Levon ret = handle_canonical_for_loops(loop); 667*1f5207b7SJohn Levon *stree = __pop_fake_cur_stree(); 668*1f5207b7SJohn Levon return ret; 669*1f5207b7SJohn Levon } 670*1f5207b7SJohn Levon 671*1f5207b7SJohn Levon int __iterator_unchanged(struct sm_state *sm) 672*1f5207b7SJohn Levon { 673*1f5207b7SJohn Levon if (!sm) 674*1f5207b7SJohn Levon return 0; 675*1f5207b7SJohn Levon if (get_sm_state(my_id, sm->name, sm->sym) == sm) 676*1f5207b7SJohn Levon return 1; 677*1f5207b7SJohn Levon return 0; 678*1f5207b7SJohn Levon } 679*1f5207b7SJohn Levon 680*1f5207b7SJohn Levon static void while_count_down_after(struct sm_state *sm, struct expression *condition) 681*1f5207b7SJohn Levon { 682*1f5207b7SJohn Levon struct expression *unop; 683*1f5207b7SJohn Levon int op; 684*1f5207b7SJohn Levon sval_t limit, after_value; 685*1f5207b7SJohn Levon 686*1f5207b7SJohn Levon if (!get_countdown_info(condition, &unop, &op, &limit)) 687*1f5207b7SJohn Levon return; 688*1f5207b7SJohn Levon after_value = estate_min(sm->state); 689*1f5207b7SJohn Levon after_value.value--; 690*1f5207b7SJohn Levon set_extra_mod(sm->name, sm->sym, condition->unop, alloc_estate_sval(after_value)); 691*1f5207b7SJohn Levon } 692*1f5207b7SJohn Levon 693*1f5207b7SJohn Levon void __extra_pre_loop_hook_after(struct sm_state *sm, 694*1f5207b7SJohn Levon struct statement *iterator, 695*1f5207b7SJohn Levon struct expression *condition) 696*1f5207b7SJohn Levon { 697*1f5207b7SJohn Levon struct expression *iter_expr; 698*1f5207b7SJohn Levon sval_t limit; 699*1f5207b7SJohn Levon struct smatch_state *state; 700*1f5207b7SJohn Levon 701*1f5207b7SJohn Levon if (!iterator) { 702*1f5207b7SJohn Levon while_count_down_after(sm, condition); 703*1f5207b7SJohn Levon return; 704*1f5207b7SJohn Levon } 705*1f5207b7SJohn Levon 706*1f5207b7SJohn Levon iter_expr = iterator->expression; 707*1f5207b7SJohn Levon 708*1f5207b7SJohn Levon if (condition->type != EXPR_COMPARE) 709*1f5207b7SJohn Levon return; 710*1f5207b7SJohn Levon if (iter_expr->op == SPECIAL_INCREMENT) { 711*1f5207b7SJohn Levon limit = sval_binop(estate_max(sm->state), '+', 712*1f5207b7SJohn Levon sval_type_val(estate_type(sm->state), 1)); 713*1f5207b7SJohn Levon } else { 714*1f5207b7SJohn Levon limit = sval_binop(estate_min(sm->state), '-', 715*1f5207b7SJohn Levon sval_type_val(estate_type(sm->state), 1)); 716*1f5207b7SJohn Levon } 717*1f5207b7SJohn Levon if (!estate_has_hard_max(sm->state) && !__has_breaks()) { 718*1f5207b7SJohn Levon if (iter_expr->op == SPECIAL_INCREMENT) 719*1f5207b7SJohn Levon state = alloc_estate_range(estate_min(sm->state), limit); 720*1f5207b7SJohn Levon else 721*1f5207b7SJohn Levon state = alloc_estate_range(limit, estate_max(sm->state)); 722*1f5207b7SJohn Levon } else { 723*1f5207b7SJohn Levon state = alloc_estate_sval(limit); 724*1f5207b7SJohn Levon } 725*1f5207b7SJohn Levon if (!estate_has_hard_max(sm->state)) { 726*1f5207b7SJohn Levon estate_clear_hard_max(state); 727*1f5207b7SJohn Levon } 728*1f5207b7SJohn Levon if (estate_has_fuzzy_max(sm->state)) { 729*1f5207b7SJohn Levon sval_t hmax = estate_get_fuzzy_max(sm->state); 730*1f5207b7SJohn Levon sval_t max = estate_max(sm->state); 731*1f5207b7SJohn Levon 732*1f5207b7SJohn Levon if (sval_cmp(hmax, max) != 0) 733*1f5207b7SJohn Levon estate_clear_fuzzy_max(state); 734*1f5207b7SJohn Levon } else if (!estate_has_fuzzy_max(sm->state)) { 735*1f5207b7SJohn Levon estate_clear_fuzzy_max(state); 736*1f5207b7SJohn Levon } 737*1f5207b7SJohn Levon 738*1f5207b7SJohn Levon set_extra_mod(sm->name, sm->sym, iter_expr, state); 739*1f5207b7SJohn Levon } 740*1f5207b7SJohn Levon 741*1f5207b7SJohn Levon static struct stree *unmatched_stree; 742*1f5207b7SJohn Levon static struct smatch_state *unmatched_state(struct sm_state *sm) 743*1f5207b7SJohn Levon { 744*1f5207b7SJohn Levon struct smatch_state *state; 745*1f5207b7SJohn Levon 746*1f5207b7SJohn Levon if (unmatched_stree) { 747*1f5207b7SJohn Levon state = get_state_stree(unmatched_stree, SMATCH_EXTRA, sm->name, sm->sym); 748*1f5207b7SJohn Levon if (state) 749*1f5207b7SJohn Levon return state; 750*1f5207b7SJohn Levon } 751*1f5207b7SJohn Levon if (parent_is_gone_var_sym(sm->name, sm->sym)) 752*1f5207b7SJohn Levon return alloc_estate_empty(); 753*1f5207b7SJohn Levon return alloc_estate_whole(estate_type(sm->state)); 754*1f5207b7SJohn Levon } 755*1f5207b7SJohn Levon 756*1f5207b7SJohn Levon static void clear_the_pointed_at(struct expression *expr) 757*1f5207b7SJohn Levon { 758*1f5207b7SJohn Levon struct stree *stree; 759*1f5207b7SJohn Levon char *name; 760*1f5207b7SJohn Levon struct symbol *sym; 761*1f5207b7SJohn Levon struct sm_state *tmp; 762*1f5207b7SJohn Levon 763*1f5207b7SJohn Levon name = expr_to_var_sym(expr, &sym); 764*1f5207b7SJohn Levon if (!name || !sym) 765*1f5207b7SJohn Levon goto free; 766*1f5207b7SJohn Levon 767*1f5207b7SJohn Levon stree = __get_cur_stree(); 768*1f5207b7SJohn Levon FOR_EACH_MY_SM(SMATCH_EXTRA, stree, tmp) { 769*1f5207b7SJohn Levon if (tmp->name[0] != '*') 770*1f5207b7SJohn Levon continue; 771*1f5207b7SJohn Levon if (tmp->sym != sym) 772*1f5207b7SJohn Levon continue; 773*1f5207b7SJohn Levon if (strcmp(tmp->name + 1, name) != 0) 774*1f5207b7SJohn Levon continue; 775*1f5207b7SJohn Levon set_extra_mod(tmp->name, tmp->sym, expr, alloc_estate_whole(estate_type(tmp->state))); 776*1f5207b7SJohn Levon } END_FOR_EACH_SM(tmp); 777*1f5207b7SJohn Levon 778*1f5207b7SJohn Levon free: 779*1f5207b7SJohn Levon free_string(name); 780*1f5207b7SJohn Levon } 781*1f5207b7SJohn Levon 782*1f5207b7SJohn Levon static int is_const_param(struct expression *expr, int param) 783*1f5207b7SJohn Levon { 784*1f5207b7SJohn Levon struct symbol *type; 785*1f5207b7SJohn Levon 786*1f5207b7SJohn Levon type = get_arg_type(expr, param); 787*1f5207b7SJohn Levon if (!type) 788*1f5207b7SJohn Levon return 0; 789*1f5207b7SJohn Levon if (type->ctype.modifiers & MOD_CONST) 790*1f5207b7SJohn Levon return 1; 791*1f5207b7SJohn Levon return 0; 792*1f5207b7SJohn Levon } 793*1f5207b7SJohn Levon 794*1f5207b7SJohn Levon static void match_function_call(struct expression *expr) 795*1f5207b7SJohn Levon { 796*1f5207b7SJohn Levon struct expression *arg; 797*1f5207b7SJohn Levon struct expression *tmp; 798*1f5207b7SJohn Levon int param = -1; 799*1f5207b7SJohn Levon 800*1f5207b7SJohn Levon /* if we have the db this is handled in smatch_function_hooks.c */ 801*1f5207b7SJohn Levon if (!option_no_db) 802*1f5207b7SJohn Levon return; 803*1f5207b7SJohn Levon if (inlinable(expr->fn)) 804*1f5207b7SJohn Levon return; 805*1f5207b7SJohn Levon 806*1f5207b7SJohn Levon FOR_EACH_PTR(expr->args, arg) { 807*1f5207b7SJohn Levon param++; 808*1f5207b7SJohn Levon if (is_const_param(expr->fn, param)) 809*1f5207b7SJohn Levon continue; 810*1f5207b7SJohn Levon tmp = strip_expr(arg); 811*1f5207b7SJohn Levon if (tmp->type == EXPR_PREOP && tmp->op == '&') 812*1f5207b7SJohn Levon set_extra_expr_mod(tmp->unop, alloc_estate_whole(get_type(tmp->unop))); 813*1f5207b7SJohn Levon else 814*1f5207b7SJohn Levon clear_the_pointed_at(tmp); 815*1f5207b7SJohn Levon } END_FOR_EACH_PTR(arg); 816*1f5207b7SJohn Levon } 817*1f5207b7SJohn Levon 818*1f5207b7SJohn Levon static int values_fit_type(struct expression *left, struct expression *right) 819*1f5207b7SJohn Levon { 820*1f5207b7SJohn Levon struct range_list *rl; 821*1f5207b7SJohn Levon struct symbol *type; 822*1f5207b7SJohn Levon 823*1f5207b7SJohn Levon type = get_type(left); 824*1f5207b7SJohn Levon if (!type) 825*1f5207b7SJohn Levon return 0; 826*1f5207b7SJohn Levon get_absolute_rl(right, &rl); 827*1f5207b7SJohn Levon if (type_unsigned(type) && sval_is_negative(rl_min(rl))) 828*1f5207b7SJohn Levon return 0; 829*1f5207b7SJohn Levon if (sval_cmp(sval_type_min(type), rl_min(rl)) > 0) 830*1f5207b7SJohn Levon return 0; 831*1f5207b7SJohn Levon if (sval_cmp(sval_type_max(type), rl_max(rl)) < 0) 832*1f5207b7SJohn Levon return 0; 833*1f5207b7SJohn Levon return 1; 834*1f5207b7SJohn Levon } 835*1f5207b7SJohn Levon 836*1f5207b7SJohn Levon static void save_chunk_info(struct expression *left, struct expression *right) 837*1f5207b7SJohn Levon { 838*1f5207b7SJohn Levon struct var_sym_list *vsl; 839*1f5207b7SJohn Levon struct var_sym *vs; 840*1f5207b7SJohn Levon struct expression *add_expr; 841*1f5207b7SJohn Levon struct symbol *type; 842*1f5207b7SJohn Levon sval_t sval; 843*1f5207b7SJohn Levon char *name; 844*1f5207b7SJohn Levon struct symbol *sym; 845*1f5207b7SJohn Levon 846*1f5207b7SJohn Levon if (right->type != EXPR_BINOP || right->op != '-') 847*1f5207b7SJohn Levon return; 848*1f5207b7SJohn Levon if (!get_value(right->left, &sval)) 849*1f5207b7SJohn Levon return; 850*1f5207b7SJohn Levon if (!expr_to_sym(right->right)) 851*1f5207b7SJohn Levon return; 852*1f5207b7SJohn Levon 853*1f5207b7SJohn Levon add_expr = binop_expression(left, '+', right->right); 854*1f5207b7SJohn Levon type = get_type(add_expr); 855*1f5207b7SJohn Levon if (!type) 856*1f5207b7SJohn Levon return; 857*1f5207b7SJohn Levon name = expr_to_chunk_sym_vsl(add_expr, &sym, &vsl); 858*1f5207b7SJohn Levon if (!name || !vsl) 859*1f5207b7SJohn Levon goto free; 860*1f5207b7SJohn Levon FOR_EACH_PTR(vsl, vs) { 861*1f5207b7SJohn Levon store_link(link_id, vs->var, vs->sym, name, sym); 862*1f5207b7SJohn Levon } END_FOR_EACH_PTR(vs); 863*1f5207b7SJohn Levon 864*1f5207b7SJohn Levon set_state(SMATCH_EXTRA, name, sym, alloc_estate_sval(sval_cast(type, sval))); 865*1f5207b7SJohn Levon free: 866*1f5207b7SJohn Levon free_string(name); 867*1f5207b7SJohn Levon } 868*1f5207b7SJohn Levon 869*1f5207b7SJohn Levon static void do_array_assign(struct expression *left, int op, struct expression *right) 870*1f5207b7SJohn Levon { 871*1f5207b7SJohn Levon struct range_list *rl; 872*1f5207b7SJohn Levon 873*1f5207b7SJohn Levon if (op == '=') { 874*1f5207b7SJohn Levon get_absolute_rl(right, &rl); 875*1f5207b7SJohn Levon rl = cast_rl(get_type(left), rl); 876*1f5207b7SJohn Levon } else { 877*1f5207b7SJohn Levon rl = alloc_whole_rl(get_type(left)); 878*1f5207b7SJohn Levon } 879*1f5207b7SJohn Levon 880*1f5207b7SJohn Levon set_extra_array_mod(left, alloc_estate_rl(rl)); 881*1f5207b7SJohn Levon } 882*1f5207b7SJohn Levon 883*1f5207b7SJohn Levon static void match_vanilla_assign(struct expression *left, struct expression *right) 884*1f5207b7SJohn Levon { 885*1f5207b7SJohn Levon struct range_list *orig_rl = NULL; 886*1f5207b7SJohn Levon struct range_list *rl = NULL; 887*1f5207b7SJohn Levon struct symbol *right_sym; 888*1f5207b7SJohn Levon struct symbol *left_type; 889*1f5207b7SJohn Levon struct symbol *right_type; 890*1f5207b7SJohn Levon char *right_name = NULL; 891*1f5207b7SJohn Levon struct symbol *sym; 892*1f5207b7SJohn Levon char *name; 893*1f5207b7SJohn Levon sval_t sval, max; 894*1f5207b7SJohn Levon struct smatch_state *state; 895*1f5207b7SJohn Levon int comparison; 896*1f5207b7SJohn Levon 897*1f5207b7SJohn Levon if (is_struct(left)) 898*1f5207b7SJohn Levon return; 899*1f5207b7SJohn Levon 900*1f5207b7SJohn Levon save_chunk_info(left, right); 901*1f5207b7SJohn Levon 902*1f5207b7SJohn Levon name = expr_to_var_sym(left, &sym); 903*1f5207b7SJohn Levon if (!name) { 904*1f5207b7SJohn Levon if (chunk_has_array(left)) 905*1f5207b7SJohn Levon do_array_assign(left, '=', right); 906*1f5207b7SJohn Levon return; 907*1f5207b7SJohn Levon } 908*1f5207b7SJohn Levon 909*1f5207b7SJohn Levon left_type = get_type(left); 910*1f5207b7SJohn Levon right_type = get_type(right); 911*1f5207b7SJohn Levon 912*1f5207b7SJohn Levon right_name = expr_to_var_sym(right, &right_sym); 913*1f5207b7SJohn Levon 914*1f5207b7SJohn Levon if (!__in_fake_assign && 915*1f5207b7SJohn Levon !(right->type == EXPR_PREOP && right->op == '&') && 916*1f5207b7SJohn Levon right_name && right_sym && 917*1f5207b7SJohn Levon values_fit_type(left, strip_expr(right)) && 918*1f5207b7SJohn Levon !has_symbol(right, sym)) { 919*1f5207b7SJohn Levon set_equiv(left, right); 920*1f5207b7SJohn Levon goto free; 921*1f5207b7SJohn Levon } 922*1f5207b7SJohn Levon 923*1f5207b7SJohn Levon if (is_pointer(right) && get_address_rl(right, &rl)) { 924*1f5207b7SJohn Levon state = alloc_estate_rl(rl); 925*1f5207b7SJohn Levon goto done; 926*1f5207b7SJohn Levon } 927*1f5207b7SJohn Levon 928*1f5207b7SJohn Levon if (get_implied_value(right, &sval)) { 929*1f5207b7SJohn Levon state = alloc_estate_sval(sval_cast(left_type, sval)); 930*1f5207b7SJohn Levon goto done; 931*1f5207b7SJohn Levon } 932*1f5207b7SJohn Levon 933*1f5207b7SJohn Levon if (__in_fake_assign) { 934*1f5207b7SJohn Levon struct smatch_state *right_state; 935*1f5207b7SJohn Levon sval_t sval; 936*1f5207b7SJohn Levon 937*1f5207b7SJohn Levon if (get_value(right, &sval)) { 938*1f5207b7SJohn Levon sval = sval_cast(left_type, sval); 939*1f5207b7SJohn Levon state = alloc_estate_sval(sval); 940*1f5207b7SJohn Levon goto done; 941*1f5207b7SJohn Levon } 942*1f5207b7SJohn Levon 943*1f5207b7SJohn Levon right_state = get_state(SMATCH_EXTRA, right_name, right_sym); 944*1f5207b7SJohn Levon if (right_state) { 945*1f5207b7SJohn Levon /* simple assignment */ 946*1f5207b7SJohn Levon state = clone_estate(right_state); 947*1f5207b7SJohn Levon goto done; 948*1f5207b7SJohn Levon } 949*1f5207b7SJohn Levon 950*1f5207b7SJohn Levon state = alloc_estate_rl(alloc_whole_rl(left_type)); 951*1f5207b7SJohn Levon goto done; 952*1f5207b7SJohn Levon } 953*1f5207b7SJohn Levon 954*1f5207b7SJohn Levon comparison = get_comparison(left, right); 955*1f5207b7SJohn Levon if (comparison) { 956*1f5207b7SJohn Levon comparison = flip_comparison(comparison); 957*1f5207b7SJohn Levon get_implied_rl(left, &orig_rl); 958*1f5207b7SJohn Levon } 959*1f5207b7SJohn Levon 960*1f5207b7SJohn Levon if (get_implied_rl(right, &rl)) { 961*1f5207b7SJohn Levon rl = cast_rl(left_type, rl); 962*1f5207b7SJohn Levon if (orig_rl) 963*1f5207b7SJohn Levon filter_by_comparison(&rl, comparison, orig_rl); 964*1f5207b7SJohn Levon state = alloc_estate_rl(rl); 965*1f5207b7SJohn Levon if (get_hard_max(right, &max)) { 966*1f5207b7SJohn Levon estate_set_hard_max(state); 967*1f5207b7SJohn Levon estate_set_fuzzy_max(state, max); 968*1f5207b7SJohn Levon } 969*1f5207b7SJohn Levon } else { 970*1f5207b7SJohn Levon rl = alloc_whole_rl(right_type); 971*1f5207b7SJohn Levon rl = cast_rl(left_type, rl); 972*1f5207b7SJohn Levon if (orig_rl) 973*1f5207b7SJohn Levon filter_by_comparison(&rl, comparison, orig_rl); 974*1f5207b7SJohn Levon state = alloc_estate_rl(rl); 975*1f5207b7SJohn Levon } 976*1f5207b7SJohn Levon 977*1f5207b7SJohn Levon done: 978*1f5207b7SJohn Levon set_extra_mod(name, sym, left, state); 979*1f5207b7SJohn Levon free: 980*1f5207b7SJohn Levon free_string(right_name); 981*1f5207b7SJohn Levon } 982*1f5207b7SJohn Levon 983*1f5207b7SJohn Levon static int op_remove_assign(int op) 984*1f5207b7SJohn Levon { 985*1f5207b7SJohn Levon switch (op) { 986*1f5207b7SJohn Levon case SPECIAL_ADD_ASSIGN: 987*1f5207b7SJohn Levon return '+'; 988*1f5207b7SJohn Levon case SPECIAL_SUB_ASSIGN: 989*1f5207b7SJohn Levon return '-'; 990*1f5207b7SJohn Levon case SPECIAL_MUL_ASSIGN: 991*1f5207b7SJohn Levon return '*'; 992*1f5207b7SJohn Levon case SPECIAL_DIV_ASSIGN: 993*1f5207b7SJohn Levon return '/'; 994*1f5207b7SJohn Levon case SPECIAL_MOD_ASSIGN: 995*1f5207b7SJohn Levon return '%'; 996*1f5207b7SJohn Levon case SPECIAL_AND_ASSIGN: 997*1f5207b7SJohn Levon return '&'; 998*1f5207b7SJohn Levon case SPECIAL_OR_ASSIGN: 999*1f5207b7SJohn Levon return '|'; 1000*1f5207b7SJohn Levon case SPECIAL_XOR_ASSIGN: 1001*1f5207b7SJohn Levon return '^'; 1002*1f5207b7SJohn Levon case SPECIAL_SHL_ASSIGN: 1003*1f5207b7SJohn Levon return SPECIAL_LEFTSHIFT; 1004*1f5207b7SJohn Levon case SPECIAL_SHR_ASSIGN: 1005*1f5207b7SJohn Levon return SPECIAL_RIGHTSHIFT; 1006*1f5207b7SJohn Levon default: 1007*1f5207b7SJohn Levon return op; 1008*1f5207b7SJohn Levon } 1009*1f5207b7SJohn Levon } 1010*1f5207b7SJohn Levon 1011*1f5207b7SJohn Levon static void match_assign(struct expression *expr) 1012*1f5207b7SJohn Levon { 1013*1f5207b7SJohn Levon struct range_list *rl = NULL; 1014*1f5207b7SJohn Levon struct expression *left; 1015*1f5207b7SJohn Levon struct expression *right; 1016*1f5207b7SJohn Levon struct expression *binop_expr; 1017*1f5207b7SJohn Levon struct symbol *left_type; 1018*1f5207b7SJohn Levon struct symbol *sym; 1019*1f5207b7SJohn Levon char *name; 1020*1f5207b7SJohn Levon sval_t left_min, left_max; 1021*1f5207b7SJohn Levon sval_t right_min, right_max; 1022*1f5207b7SJohn Levon sval_t res_min, res_max; 1023*1f5207b7SJohn Levon 1024*1f5207b7SJohn Levon left = strip_expr(expr->left); 1025*1f5207b7SJohn Levon 1026*1f5207b7SJohn Levon right = strip_parens(expr->right); 1027*1f5207b7SJohn Levon if (right->type == EXPR_CALL && sym_name_is("__builtin_expect", right->fn)) 1028*1f5207b7SJohn Levon right = get_argument_from_call_expr(right->args, 0); 1029*1f5207b7SJohn Levon while (right->type == EXPR_ASSIGNMENT && right->op == '=') 1030*1f5207b7SJohn Levon right = strip_parens(right->left); 1031*1f5207b7SJohn Levon 1032*1f5207b7SJohn Levon if (expr->op == '=' && is_condition(expr->right)) 1033*1f5207b7SJohn Levon return; /* handled in smatch_condition.c */ 1034*1f5207b7SJohn Levon if (expr->op == '=' && right->type == EXPR_CALL) 1035*1f5207b7SJohn Levon return; /* handled in smatch_function_hooks.c */ 1036*1f5207b7SJohn Levon if (expr->op == '=') { 1037*1f5207b7SJohn Levon match_vanilla_assign(left, right); 1038*1f5207b7SJohn Levon return; 1039*1f5207b7SJohn Levon } 1040*1f5207b7SJohn Levon 1041*1f5207b7SJohn Levon name = expr_to_var_sym(left, &sym); 1042*1f5207b7SJohn Levon if (!name) 1043*1f5207b7SJohn Levon return; 1044*1f5207b7SJohn Levon 1045*1f5207b7SJohn Levon left_type = get_type(left); 1046*1f5207b7SJohn Levon 1047*1f5207b7SJohn Levon res_min = sval_type_min(left_type); 1048*1f5207b7SJohn Levon res_max = sval_type_max(left_type); 1049*1f5207b7SJohn Levon 1050*1f5207b7SJohn Levon switch (expr->op) { 1051*1f5207b7SJohn Levon case SPECIAL_ADD_ASSIGN: 1052*1f5207b7SJohn Levon get_absolute_max(left, &left_max); 1053*1f5207b7SJohn Levon get_absolute_max(right, &right_max); 1054*1f5207b7SJohn Levon if (sval_binop_overflows(left_max, '+', sval_cast(left_type, right_max))) 1055*1f5207b7SJohn Levon break; 1056*1f5207b7SJohn Levon if (get_implied_min(left, &left_min) && 1057*1f5207b7SJohn Levon !sval_is_negative_min(left_min) && 1058*1f5207b7SJohn Levon get_implied_min(right, &right_min) && 1059*1f5207b7SJohn Levon !sval_is_negative_min(right_min)) { 1060*1f5207b7SJohn Levon res_min = sval_binop(left_min, '+', right_min); 1061*1f5207b7SJohn Levon res_min = sval_cast(left_type, res_min); 1062*1f5207b7SJohn Levon } 1063*1f5207b7SJohn Levon if (inside_loop()) /* we are assuming loops don't lead to wrapping */ 1064*1f5207b7SJohn Levon break; 1065*1f5207b7SJohn Levon res_max = sval_binop(left_max, '+', right_max); 1066*1f5207b7SJohn Levon res_max = sval_cast(left_type, res_max); 1067*1f5207b7SJohn Levon break; 1068*1f5207b7SJohn Levon case SPECIAL_SUB_ASSIGN: 1069*1f5207b7SJohn Levon if (get_implied_max(left, &left_max) && 1070*1f5207b7SJohn Levon !sval_is_max(left_max) && 1071*1f5207b7SJohn Levon get_implied_min(right, &right_min) && 1072*1f5207b7SJohn Levon !sval_is_min(right_min)) { 1073*1f5207b7SJohn Levon res_max = sval_binop(left_max, '-', right_min); 1074*1f5207b7SJohn Levon res_max = sval_cast(left_type, res_max); 1075*1f5207b7SJohn Levon } 1076*1f5207b7SJohn Levon if (inside_loop()) 1077*1f5207b7SJohn Levon break; 1078*1f5207b7SJohn Levon if (get_implied_min(left, &left_min) && 1079*1f5207b7SJohn Levon !sval_is_min(left_min) && 1080*1f5207b7SJohn Levon get_implied_max(right, &right_max) && 1081*1f5207b7SJohn Levon !sval_is_max(right_max)) { 1082*1f5207b7SJohn Levon res_min = sval_binop(left_min, '-', right_max); 1083*1f5207b7SJohn Levon res_min = sval_cast(left_type, res_min); 1084*1f5207b7SJohn Levon } 1085*1f5207b7SJohn Levon break; 1086*1f5207b7SJohn Levon case SPECIAL_AND_ASSIGN: 1087*1f5207b7SJohn Levon case SPECIAL_MOD_ASSIGN: 1088*1f5207b7SJohn Levon case SPECIAL_SHL_ASSIGN: 1089*1f5207b7SJohn Levon case SPECIAL_SHR_ASSIGN: 1090*1f5207b7SJohn Levon case SPECIAL_OR_ASSIGN: 1091*1f5207b7SJohn Levon case SPECIAL_XOR_ASSIGN: 1092*1f5207b7SJohn Levon case SPECIAL_MUL_ASSIGN: 1093*1f5207b7SJohn Levon case SPECIAL_DIV_ASSIGN: 1094*1f5207b7SJohn Levon binop_expr = binop_expression(expr->left, 1095*1f5207b7SJohn Levon op_remove_assign(expr->op), 1096*1f5207b7SJohn Levon expr->right); 1097*1f5207b7SJohn Levon if (get_absolute_rl(binop_expr, &rl)) { 1098*1f5207b7SJohn Levon rl = cast_rl(left_type, rl); 1099*1f5207b7SJohn Levon set_extra_mod(name, sym, left, alloc_estate_rl(rl)); 1100*1f5207b7SJohn Levon goto free; 1101*1f5207b7SJohn Levon } 1102*1f5207b7SJohn Levon break; 1103*1f5207b7SJohn Levon } 1104*1f5207b7SJohn Levon rl = cast_rl(left_type, alloc_rl(res_min, res_max)); 1105*1f5207b7SJohn Levon set_extra_mod(name, sym, left, alloc_estate_rl(rl)); 1106*1f5207b7SJohn Levon free: 1107*1f5207b7SJohn Levon free_string(name); 1108*1f5207b7SJohn Levon } 1109*1f5207b7SJohn Levon 1110*1f5207b7SJohn Levon static struct smatch_state *increment_state(struct smatch_state *state) 1111*1f5207b7SJohn Levon { 1112*1f5207b7SJohn Levon sval_t min = estate_min(state); 1113*1f5207b7SJohn Levon sval_t max = estate_max(state); 1114*1f5207b7SJohn Levon 1115*1f5207b7SJohn Levon if (!estate_rl(state)) 1116*1f5207b7SJohn Levon return NULL; 1117*1f5207b7SJohn Levon 1118*1f5207b7SJohn Levon if (inside_loop()) 1119*1f5207b7SJohn Levon max = sval_type_max(max.type); 1120*1f5207b7SJohn Levon 1121*1f5207b7SJohn Levon if (!sval_is_min(min) && !sval_is_max(min)) 1122*1f5207b7SJohn Levon min.value++; 1123*1f5207b7SJohn Levon if (!sval_is_min(max) && !sval_is_max(max)) 1124*1f5207b7SJohn Levon max.value++; 1125*1f5207b7SJohn Levon return alloc_estate_range(min, max); 1126*1f5207b7SJohn Levon } 1127*1f5207b7SJohn Levon 1128*1f5207b7SJohn Levon static struct smatch_state *decrement_state(struct smatch_state *state) 1129*1f5207b7SJohn Levon { 1130*1f5207b7SJohn Levon sval_t min = estate_min(state); 1131*1f5207b7SJohn Levon sval_t max = estate_max(state); 1132*1f5207b7SJohn Levon 1133*1f5207b7SJohn Levon if (!estate_rl(state)) 1134*1f5207b7SJohn Levon return NULL; 1135*1f5207b7SJohn Levon 1136*1f5207b7SJohn Levon if (inside_loop()) 1137*1f5207b7SJohn Levon min = sval_type_min(min.type); 1138*1f5207b7SJohn Levon 1139*1f5207b7SJohn Levon if (!sval_is_min(min) && !sval_is_max(min)) 1140*1f5207b7SJohn Levon min.value--; 1141*1f5207b7SJohn Levon if (!sval_is_min(max) && !sval_is_max(max)) 1142*1f5207b7SJohn Levon max.value--; 1143*1f5207b7SJohn Levon return alloc_estate_range(min, max); 1144*1f5207b7SJohn Levon } 1145*1f5207b7SJohn Levon 1146*1f5207b7SJohn Levon static void clear_pointed_at_state(struct expression *expr) 1147*1f5207b7SJohn Levon { 1148*1f5207b7SJohn Levon struct symbol *type; 1149*1f5207b7SJohn Levon 1150*1f5207b7SJohn Levon /* 1151*1f5207b7SJohn Levon * ALERT: This is sort of a mess. If it's is a struct assigment like 1152*1f5207b7SJohn Levon * "foo = bar;", then that's handled by smatch_struct_assignment.c. 1153*1f5207b7SJohn Levon * the same thing for p++ where "p" is a struct. Most modifications 1154*1f5207b7SJohn Levon * are handled by the assignment hook or the db. Smatch_extra.c doesn't 1155*1f5207b7SJohn Levon * use smatch_modification.c because we have to get the ordering right 1156*1f5207b7SJohn Levon * or something. So if you have p++ where p is a pointer to a standard 1157*1f5207b7SJohn Levon * c type then we handle that here. What a mess. 1158*1f5207b7SJohn Levon */ 1159*1f5207b7SJohn Levon expr = strip_expr(expr); 1160*1f5207b7SJohn Levon type = get_type(expr); 1161*1f5207b7SJohn Levon if (!type || type->type != SYM_PTR) 1162*1f5207b7SJohn Levon return; 1163*1f5207b7SJohn Levon type = get_real_base_type(type); 1164*1f5207b7SJohn Levon if (!type || type->type != SYM_BASETYPE) 1165*1f5207b7SJohn Levon return; 1166*1f5207b7SJohn Levon set_extra_expr_nomod(deref_expression(expr), alloc_estate_whole(type)); 1167*1f5207b7SJohn Levon } 1168*1f5207b7SJohn Levon 1169*1f5207b7SJohn Levon static void unop_expr(struct expression *expr) 1170*1f5207b7SJohn Levon { 1171*1f5207b7SJohn Levon struct smatch_state *state; 1172*1f5207b7SJohn Levon 1173*1f5207b7SJohn Levon if (expr->smatch_flags & Handled) 1174*1f5207b7SJohn Levon return; 1175*1f5207b7SJohn Levon 1176*1f5207b7SJohn Levon switch (expr->op) { 1177*1f5207b7SJohn Levon case SPECIAL_INCREMENT: 1178*1f5207b7SJohn Levon state = get_state_expr(SMATCH_EXTRA, expr->unop); 1179*1f5207b7SJohn Levon state = increment_state(state); 1180*1f5207b7SJohn Levon if (!state) 1181*1f5207b7SJohn Levon state = alloc_estate_whole(get_type(expr)); 1182*1f5207b7SJohn Levon set_extra_expr_mod(expr->unop, state); 1183*1f5207b7SJohn Levon clear_pointed_at_state(expr->unop); 1184*1f5207b7SJohn Levon break; 1185*1f5207b7SJohn Levon case SPECIAL_DECREMENT: 1186*1f5207b7SJohn Levon state = get_state_expr(SMATCH_EXTRA, expr->unop); 1187*1f5207b7SJohn Levon state = decrement_state(state); 1188*1f5207b7SJohn Levon if (!state) 1189*1f5207b7SJohn Levon state = alloc_estate_whole(get_type(expr)); 1190*1f5207b7SJohn Levon set_extra_expr_mod(expr->unop, state); 1191*1f5207b7SJohn Levon clear_pointed_at_state(expr->unop); 1192*1f5207b7SJohn Levon break; 1193*1f5207b7SJohn Levon default: 1194*1f5207b7SJohn Levon return; 1195*1f5207b7SJohn Levon } 1196*1f5207b7SJohn Levon } 1197*1f5207b7SJohn Levon 1198*1f5207b7SJohn Levon static void asm_expr(struct statement *stmt) 1199*1f5207b7SJohn Levon { 1200*1f5207b7SJohn Levon 1201*1f5207b7SJohn Levon struct expression *expr; 1202*1f5207b7SJohn Levon struct symbol *type; 1203*1f5207b7SJohn Levon int state = 0; 1204*1f5207b7SJohn Levon 1205*1f5207b7SJohn Levon FOR_EACH_PTR(stmt->asm_outputs, expr) { 1206*1f5207b7SJohn Levon switch (state) { 1207*1f5207b7SJohn Levon case 0: /* identifier */ 1208*1f5207b7SJohn Levon case 1: /* constraint */ 1209*1f5207b7SJohn Levon state++; 1210*1f5207b7SJohn Levon continue; 1211*1f5207b7SJohn Levon case 2: /* expression */ 1212*1f5207b7SJohn Levon state = 0; 1213*1f5207b7SJohn Levon type = get_type(strip_expr(expr)); 1214*1f5207b7SJohn Levon set_extra_expr_mod(expr, alloc_estate_whole(type)); 1215*1f5207b7SJohn Levon continue; 1216*1f5207b7SJohn Levon } 1217*1f5207b7SJohn Levon } END_FOR_EACH_PTR(expr); 1218*1f5207b7SJohn Levon } 1219*1f5207b7SJohn Levon 1220*1f5207b7SJohn Levon static void check_dereference(struct expression *expr) 1221*1f5207b7SJohn Levon { 1222*1f5207b7SJohn Levon struct smatch_state *state; 1223*1f5207b7SJohn Levon 1224*1f5207b7SJohn Levon if (__in_fake_assign) 1225*1f5207b7SJohn Levon return; 1226*1f5207b7SJohn Levon if (outside_of_function()) 1227*1f5207b7SJohn Levon return; 1228*1f5207b7SJohn Levon state = get_extra_state(expr); 1229*1f5207b7SJohn Levon if (state) { 1230*1f5207b7SJohn Levon struct range_list *rl; 1231*1f5207b7SJohn Levon 1232*1f5207b7SJohn Levon rl = rl_intersection(estate_rl(state), valid_ptr_rl); 1233*1f5207b7SJohn Levon if (rl_equiv(rl, estate_rl(state))) 1234*1f5207b7SJohn Levon return; 1235*1f5207b7SJohn Levon set_extra_expr_nomod(expr, alloc_estate_rl(rl)); 1236*1f5207b7SJohn Levon } else { 1237*1f5207b7SJohn Levon set_extra_expr_nomod(expr, alloc_estate_range(valid_ptr_min_sval, valid_ptr_max_sval)); 1238*1f5207b7SJohn Levon } 1239*1f5207b7SJohn Levon } 1240*1f5207b7SJohn Levon 1241*1f5207b7SJohn Levon static void match_dereferences(struct expression *expr) 1242*1f5207b7SJohn Levon { 1243*1f5207b7SJohn Levon if (expr->type != EXPR_PREOP) 1244*1f5207b7SJohn Levon return; 1245*1f5207b7SJohn Levon /* it's saying that foo[1] = bar dereferences foo[1] */ 1246*1f5207b7SJohn Levon if (is_array(expr)) 1247*1f5207b7SJohn Levon return; 1248*1f5207b7SJohn Levon check_dereference(expr->unop); 1249*1f5207b7SJohn Levon } 1250*1f5207b7SJohn Levon 1251*1f5207b7SJohn Levon static void match_pointer_as_array(struct expression *expr) 1252*1f5207b7SJohn Levon { 1253*1f5207b7SJohn Levon if (!is_array(expr)) 1254*1f5207b7SJohn Levon return; 1255*1f5207b7SJohn Levon check_dereference(get_array_base(expr)); 1256*1f5207b7SJohn Levon } 1257*1f5207b7SJohn Levon 1258*1f5207b7SJohn Levon static void find_dereferences(struct expression *expr) 1259*1f5207b7SJohn Levon { 1260*1f5207b7SJohn Levon while (expr->type == EXPR_PREOP) { 1261*1f5207b7SJohn Levon if (expr->op == '*') 1262*1f5207b7SJohn Levon check_dereference(expr->unop); 1263*1f5207b7SJohn Levon expr = strip_expr(expr->unop); 1264*1f5207b7SJohn Levon } 1265*1f5207b7SJohn Levon } 1266*1f5207b7SJohn Levon 1267*1f5207b7SJohn Levon static void set_param_dereferenced(struct expression *call, struct expression *arg, char *key, char *unused) 1268*1f5207b7SJohn Levon { 1269*1f5207b7SJohn Levon struct symbol *sym; 1270*1f5207b7SJohn Levon char *name; 1271*1f5207b7SJohn Levon 1272*1f5207b7SJohn Levon name = get_variable_from_key(arg, key, &sym); 1273*1f5207b7SJohn Levon if (name && sym) { 1274*1f5207b7SJohn Levon struct smatch_state *orig, *new; 1275*1f5207b7SJohn Levon struct range_list *rl; 1276*1f5207b7SJohn Levon 1277*1f5207b7SJohn Levon orig = get_state(SMATCH_EXTRA, name, sym); 1278*1f5207b7SJohn Levon if (orig) { 1279*1f5207b7SJohn Levon rl = rl_intersection(estate_rl(orig), 1280*1f5207b7SJohn Levon alloc_rl(valid_ptr_min_sval, 1281*1f5207b7SJohn Levon valid_ptr_max_sval)); 1282*1f5207b7SJohn Levon new = alloc_estate_rl(rl); 1283*1f5207b7SJohn Levon } else { 1284*1f5207b7SJohn Levon new = alloc_estate_range(valid_ptr_min_sval, valid_ptr_max_sval); 1285*1f5207b7SJohn Levon } 1286*1f5207b7SJohn Levon 1287*1f5207b7SJohn Levon set_extra_nomod(name, sym, NULL, new); 1288*1f5207b7SJohn Levon } 1289*1f5207b7SJohn Levon free_string(name); 1290*1f5207b7SJohn Levon 1291*1f5207b7SJohn Levon find_dereferences(arg); 1292*1f5207b7SJohn Levon } 1293*1f5207b7SJohn Levon 1294*1f5207b7SJohn Levon static sval_t add_one(sval_t sval) 1295*1f5207b7SJohn Levon { 1296*1f5207b7SJohn Levon sval.value++; 1297*1f5207b7SJohn Levon return sval; 1298*1f5207b7SJohn Levon } 1299*1f5207b7SJohn Levon 1300*1f5207b7SJohn Levon static int handle_postop_inc(struct expression *left, int op, struct expression *right) 1301*1f5207b7SJohn Levon { 1302*1f5207b7SJohn Levon struct statement *stmt; 1303*1f5207b7SJohn Levon struct expression *cond; 1304*1f5207b7SJohn Levon struct smatch_state *true_state, *false_state; 1305*1f5207b7SJohn Levon sval_t start; 1306*1f5207b7SJohn Levon sval_t limit; 1307*1f5207b7SJohn Levon 1308*1f5207b7SJohn Levon /* 1309*1f5207b7SJohn Levon * If we're decrementing here then that's a canonical while count down 1310*1f5207b7SJohn Levon * so it's handled already. We're only handling loops like: 1311*1f5207b7SJohn Levon * i = 0; 1312*1f5207b7SJohn Levon * do { ... } while (i++ < 3); 1313*1f5207b7SJohn Levon */ 1314*1f5207b7SJohn Levon 1315*1f5207b7SJohn Levon if (left->type != EXPR_POSTOP || left->op != SPECIAL_INCREMENT) 1316*1f5207b7SJohn Levon return 0; 1317*1f5207b7SJohn Levon 1318*1f5207b7SJohn Levon stmt = __cur_stmt->parent; 1319*1f5207b7SJohn Levon if (!stmt) 1320*1f5207b7SJohn Levon return 0; 1321*1f5207b7SJohn Levon if (stmt->type == STMT_COMPOUND) 1322*1f5207b7SJohn Levon stmt = stmt->parent; 1323*1f5207b7SJohn Levon if (!stmt || stmt->type != STMT_ITERATOR || !stmt->iterator_post_condition) 1324*1f5207b7SJohn Levon return 0; 1325*1f5207b7SJohn Levon 1326*1f5207b7SJohn Levon cond = strip_expr(stmt->iterator_post_condition); 1327*1f5207b7SJohn Levon if (cond->type != EXPR_COMPARE || cond->op != op) 1328*1f5207b7SJohn Levon return 0; 1329*1f5207b7SJohn Levon if (left != strip_expr(cond->left) || right != strip_expr(cond->right)) 1330*1f5207b7SJohn Levon return 0; 1331*1f5207b7SJohn Levon 1332*1f5207b7SJohn Levon if (!get_implied_value(left->unop, &start)) 1333*1f5207b7SJohn Levon return 0; 1334*1f5207b7SJohn Levon if (!get_implied_value(right, &limit)) 1335*1f5207b7SJohn Levon return 0; 1336*1f5207b7SJohn Levon 1337*1f5207b7SJohn Levon if (sval_cmp(start, limit) > 0) 1338*1f5207b7SJohn Levon return 0; 1339*1f5207b7SJohn Levon 1340*1f5207b7SJohn Levon switch (op) { 1341*1f5207b7SJohn Levon case '<': 1342*1f5207b7SJohn Levon case SPECIAL_UNSIGNED_LT: 1343*1f5207b7SJohn Levon break; 1344*1f5207b7SJohn Levon case SPECIAL_LTE: 1345*1f5207b7SJohn Levon case SPECIAL_UNSIGNED_LTE: 1346*1f5207b7SJohn Levon limit = add_one(limit); 1347*1f5207b7SJohn Levon default: 1348*1f5207b7SJohn Levon return 0; 1349*1f5207b7SJohn Levon 1350*1f5207b7SJohn Levon } 1351*1f5207b7SJohn Levon 1352*1f5207b7SJohn Levon true_state = alloc_estate_range(add_one(start), limit); 1353*1f5207b7SJohn Levon false_state = alloc_estate_range(add_one(limit), add_one(limit)); 1354*1f5207b7SJohn Levon 1355*1f5207b7SJohn Levon /* Currently we just discard the false state but when two passes is 1356*1f5207b7SJohn Levon * implimented correctly then it will use it. 1357*1f5207b7SJohn Levon */ 1358*1f5207b7SJohn Levon 1359*1f5207b7SJohn Levon set_extra_expr_true_false(left->unop, true_state, false_state); 1360*1f5207b7SJohn Levon 1361*1f5207b7SJohn Levon return 1; 1362*1f5207b7SJohn Levon } 1363*1f5207b7SJohn Levon 1364*1f5207b7SJohn Levon bool is_impossible_variable(struct expression *expr) 1365*1f5207b7SJohn Levon { 1366*1f5207b7SJohn Levon struct smatch_state *state; 1367*1f5207b7SJohn Levon 1368*1f5207b7SJohn Levon state = get_extra_state(expr); 1369*1f5207b7SJohn Levon if (state && !estate_rl(state)) 1370*1f5207b7SJohn Levon return true; 1371*1f5207b7SJohn Levon return false; 1372*1f5207b7SJohn Levon } 1373*1f5207b7SJohn Levon 1374*1f5207b7SJohn Levon static void handle_comparison(struct symbol *type, struct expression *left, int op, struct expression *right) 1375*1f5207b7SJohn Levon { 1376*1f5207b7SJohn Levon struct range_list *left_orig; 1377*1f5207b7SJohn Levon struct range_list *left_true; 1378*1f5207b7SJohn Levon struct range_list *left_false; 1379*1f5207b7SJohn Levon struct range_list *right_orig; 1380*1f5207b7SJohn Levon struct range_list *right_true; 1381*1f5207b7SJohn Levon struct range_list *right_false; 1382*1f5207b7SJohn Levon struct smatch_state *left_true_state; 1383*1f5207b7SJohn Levon struct smatch_state *left_false_state; 1384*1f5207b7SJohn Levon struct smatch_state *right_true_state; 1385*1f5207b7SJohn Levon struct smatch_state *right_false_state; 1386*1f5207b7SJohn Levon sval_t dummy, hard_max; 1387*1f5207b7SJohn Levon int left_postop = 0; 1388*1f5207b7SJohn Levon int right_postop = 0; 1389*1f5207b7SJohn Levon 1390*1f5207b7SJohn Levon if (left->op == SPECIAL_INCREMENT || left->op == SPECIAL_DECREMENT) { 1391*1f5207b7SJohn Levon if (left->type == EXPR_POSTOP) { 1392*1f5207b7SJohn Levon left->smatch_flags |= Handled; 1393*1f5207b7SJohn Levon left_postop = left->op; 1394*1f5207b7SJohn Levon if (handle_postop_inc(left, op, right)) 1395*1f5207b7SJohn Levon return; 1396*1f5207b7SJohn Levon } 1397*1f5207b7SJohn Levon left = strip_parens(left->unop); 1398*1f5207b7SJohn Levon } 1399*1f5207b7SJohn Levon while (left->type == EXPR_ASSIGNMENT) 1400*1f5207b7SJohn Levon left = strip_parens(left->left); 1401*1f5207b7SJohn Levon 1402*1f5207b7SJohn Levon if (right->op == SPECIAL_INCREMENT || right->op == SPECIAL_DECREMENT) { 1403*1f5207b7SJohn Levon if (right->type == EXPR_POSTOP) { 1404*1f5207b7SJohn Levon right->smatch_flags |= Handled; 1405*1f5207b7SJohn Levon right_postop = right->op; 1406*1f5207b7SJohn Levon } 1407*1f5207b7SJohn Levon right = strip_parens(right->unop); 1408*1f5207b7SJohn Levon } 1409*1f5207b7SJohn Levon 1410*1f5207b7SJohn Levon if (is_impossible_variable(left) || is_impossible_variable(right)) 1411*1f5207b7SJohn Levon return; 1412*1f5207b7SJohn Levon 1413*1f5207b7SJohn Levon get_real_absolute_rl(left, &left_orig); 1414*1f5207b7SJohn Levon left_orig = cast_rl(type, left_orig); 1415*1f5207b7SJohn Levon 1416*1f5207b7SJohn Levon get_real_absolute_rl(right, &right_orig); 1417*1f5207b7SJohn Levon right_orig = cast_rl(type, right_orig); 1418*1f5207b7SJohn Levon 1419*1f5207b7SJohn Levon split_comparison_rl(left_orig, op, right_orig, &left_true, &left_false, &right_true, &right_false); 1420*1f5207b7SJohn Levon 1421*1f5207b7SJohn Levon left_true = rl_truncate_cast(get_type(strip_expr(left)), left_true); 1422*1f5207b7SJohn Levon left_false = rl_truncate_cast(get_type(strip_expr(left)), left_false); 1423*1f5207b7SJohn Levon right_true = rl_truncate_cast(get_type(strip_expr(right)), right_true); 1424*1f5207b7SJohn Levon right_false = rl_truncate_cast(get_type(strip_expr(right)), right_false); 1425*1f5207b7SJohn Levon 1426*1f5207b7SJohn Levon if (!left_true || !left_false) { 1427*1f5207b7SJohn Levon struct range_list *tmp_true, *tmp_false; 1428*1f5207b7SJohn Levon 1429*1f5207b7SJohn Levon split_comparison_rl(alloc_whole_rl(type), op, right_orig, &tmp_true, &tmp_false, NULL, NULL); 1430*1f5207b7SJohn Levon tmp_true = rl_truncate_cast(get_type(strip_expr(left)), tmp_true); 1431*1f5207b7SJohn Levon tmp_false = rl_truncate_cast(get_type(strip_expr(left)), tmp_false); 1432*1f5207b7SJohn Levon if (tmp_true && tmp_false) 1433*1f5207b7SJohn Levon __save_imaginary_state(left, tmp_true, tmp_false); 1434*1f5207b7SJohn Levon } 1435*1f5207b7SJohn Levon 1436*1f5207b7SJohn Levon if (!right_true || !right_false) { 1437*1f5207b7SJohn Levon struct range_list *tmp_true, *tmp_false; 1438*1f5207b7SJohn Levon 1439*1f5207b7SJohn Levon split_comparison_rl(alloc_whole_rl(type), op, right_orig, NULL, NULL, &tmp_true, &tmp_false); 1440*1f5207b7SJohn Levon tmp_true = rl_truncate_cast(get_type(strip_expr(right)), tmp_true); 1441*1f5207b7SJohn Levon tmp_false = rl_truncate_cast(get_type(strip_expr(right)), tmp_false); 1442*1f5207b7SJohn Levon if (tmp_true && tmp_false) 1443*1f5207b7SJohn Levon __save_imaginary_state(right, tmp_true, tmp_false); 1444*1f5207b7SJohn Levon } 1445*1f5207b7SJohn Levon 1446*1f5207b7SJohn Levon left_true_state = alloc_estate_rl(left_true); 1447*1f5207b7SJohn Levon left_false_state = alloc_estate_rl(left_false); 1448*1f5207b7SJohn Levon right_true_state = alloc_estate_rl(right_true); 1449*1f5207b7SJohn Levon right_false_state = alloc_estate_rl(right_false); 1450*1f5207b7SJohn Levon 1451*1f5207b7SJohn Levon switch (op) { 1452*1f5207b7SJohn Levon case '<': 1453*1f5207b7SJohn Levon case SPECIAL_UNSIGNED_LT: 1454*1f5207b7SJohn Levon case SPECIAL_UNSIGNED_LTE: 1455*1f5207b7SJohn Levon case SPECIAL_LTE: 1456*1f5207b7SJohn Levon if (get_hard_max(right, &dummy)) 1457*1f5207b7SJohn Levon estate_set_hard_max(left_true_state); 1458*1f5207b7SJohn Levon if (get_hard_max(left, &dummy)) 1459*1f5207b7SJohn Levon estate_set_hard_max(right_false_state); 1460*1f5207b7SJohn Levon break; 1461*1f5207b7SJohn Levon case '>': 1462*1f5207b7SJohn Levon case SPECIAL_UNSIGNED_GT: 1463*1f5207b7SJohn Levon case SPECIAL_UNSIGNED_GTE: 1464*1f5207b7SJohn Levon case SPECIAL_GTE: 1465*1f5207b7SJohn Levon if (get_hard_max(left, &dummy)) 1466*1f5207b7SJohn Levon estate_set_hard_max(right_true_state); 1467*1f5207b7SJohn Levon if (get_hard_max(right, &dummy)) 1468*1f5207b7SJohn Levon estate_set_hard_max(left_false_state); 1469*1f5207b7SJohn Levon break; 1470*1f5207b7SJohn Levon } 1471*1f5207b7SJohn Levon 1472*1f5207b7SJohn Levon switch (op) { 1473*1f5207b7SJohn Levon case '<': 1474*1f5207b7SJohn Levon case SPECIAL_UNSIGNED_LT: 1475*1f5207b7SJohn Levon case SPECIAL_UNSIGNED_LTE: 1476*1f5207b7SJohn Levon case SPECIAL_LTE: 1477*1f5207b7SJohn Levon if (get_hard_max(right, &hard_max)) { 1478*1f5207b7SJohn Levon if (op == '<' || op == SPECIAL_UNSIGNED_LT) 1479*1f5207b7SJohn Levon hard_max.value--; 1480*1f5207b7SJohn Levon estate_set_fuzzy_max(left_true_state, hard_max); 1481*1f5207b7SJohn Levon } 1482*1f5207b7SJohn Levon if (get_implied_value(right, &hard_max)) { 1483*1f5207b7SJohn Levon if (op == SPECIAL_UNSIGNED_LTE || 1484*1f5207b7SJohn Levon op == SPECIAL_LTE) 1485*1f5207b7SJohn Levon hard_max.value++; 1486*1f5207b7SJohn Levon estate_set_fuzzy_max(left_false_state, hard_max); 1487*1f5207b7SJohn Levon } 1488*1f5207b7SJohn Levon if (get_hard_max(left, &hard_max)) { 1489*1f5207b7SJohn Levon if (op == SPECIAL_UNSIGNED_LTE || 1490*1f5207b7SJohn Levon op == SPECIAL_LTE) 1491*1f5207b7SJohn Levon hard_max.value--; 1492*1f5207b7SJohn Levon estate_set_fuzzy_max(right_false_state, hard_max); 1493*1f5207b7SJohn Levon } 1494*1f5207b7SJohn Levon if (get_implied_value(left, &hard_max)) { 1495*1f5207b7SJohn Levon if (op == '<' || op == SPECIAL_UNSIGNED_LT) 1496*1f5207b7SJohn Levon hard_max.value++; 1497*1f5207b7SJohn Levon estate_set_fuzzy_max(right_true_state, hard_max); 1498*1f5207b7SJohn Levon } 1499*1f5207b7SJohn Levon break; 1500*1f5207b7SJohn Levon case '>': 1501*1f5207b7SJohn Levon case SPECIAL_UNSIGNED_GT: 1502*1f5207b7SJohn Levon case SPECIAL_UNSIGNED_GTE: 1503*1f5207b7SJohn Levon case SPECIAL_GTE: 1504*1f5207b7SJohn Levon if (get_hard_max(left, &hard_max)) { 1505*1f5207b7SJohn Levon if (op == '>' || op == SPECIAL_UNSIGNED_GT) 1506*1f5207b7SJohn Levon hard_max.value--; 1507*1f5207b7SJohn Levon estate_set_fuzzy_max(right_true_state, hard_max); 1508*1f5207b7SJohn Levon } 1509*1f5207b7SJohn Levon if (get_implied_value(left, &hard_max)) { 1510*1f5207b7SJohn Levon if (op == SPECIAL_UNSIGNED_GTE || 1511*1f5207b7SJohn Levon op == SPECIAL_GTE) 1512*1f5207b7SJohn Levon hard_max.value++; 1513*1f5207b7SJohn Levon estate_set_fuzzy_max(right_false_state, hard_max); 1514*1f5207b7SJohn Levon } 1515*1f5207b7SJohn Levon if (get_hard_max(right, &hard_max)) { 1516*1f5207b7SJohn Levon if (op == SPECIAL_UNSIGNED_LTE || 1517*1f5207b7SJohn Levon op == SPECIAL_LTE) 1518*1f5207b7SJohn Levon hard_max.value--; 1519*1f5207b7SJohn Levon estate_set_fuzzy_max(left_false_state, hard_max); 1520*1f5207b7SJohn Levon } 1521*1f5207b7SJohn Levon if (get_implied_value(right, &hard_max)) { 1522*1f5207b7SJohn Levon if (op == '>' || 1523*1f5207b7SJohn Levon op == SPECIAL_UNSIGNED_GT) 1524*1f5207b7SJohn Levon hard_max.value++; 1525*1f5207b7SJohn Levon estate_set_fuzzy_max(left_true_state, hard_max); 1526*1f5207b7SJohn Levon } 1527*1f5207b7SJohn Levon break; 1528*1f5207b7SJohn Levon case SPECIAL_EQUAL: 1529*1f5207b7SJohn Levon if (get_hard_max(left, &hard_max)) 1530*1f5207b7SJohn Levon estate_set_fuzzy_max(right_true_state, hard_max); 1531*1f5207b7SJohn Levon if (get_hard_max(right, &hard_max)) 1532*1f5207b7SJohn Levon estate_set_fuzzy_max(left_true_state, hard_max); 1533*1f5207b7SJohn Levon break; 1534*1f5207b7SJohn Levon } 1535*1f5207b7SJohn Levon 1536*1f5207b7SJohn Levon if (get_hard_max(left, &hard_max)) { 1537*1f5207b7SJohn Levon estate_set_hard_max(left_true_state); 1538*1f5207b7SJohn Levon estate_set_hard_max(left_false_state); 1539*1f5207b7SJohn Levon } 1540*1f5207b7SJohn Levon if (get_hard_max(right, &hard_max)) { 1541*1f5207b7SJohn Levon estate_set_hard_max(right_true_state); 1542*1f5207b7SJohn Levon estate_set_hard_max(right_false_state); 1543*1f5207b7SJohn Levon } 1544*1f5207b7SJohn Levon 1545*1f5207b7SJohn Levon if (left_postop == SPECIAL_INCREMENT) { 1546*1f5207b7SJohn Levon left_true_state = increment_state(left_true_state); 1547*1f5207b7SJohn Levon left_false_state = increment_state(left_false_state); 1548*1f5207b7SJohn Levon } 1549*1f5207b7SJohn Levon if (left_postop == SPECIAL_DECREMENT) { 1550*1f5207b7SJohn Levon left_true_state = decrement_state(left_true_state); 1551*1f5207b7SJohn Levon left_false_state = decrement_state(left_false_state); 1552*1f5207b7SJohn Levon } 1553*1f5207b7SJohn Levon if (right_postop == SPECIAL_INCREMENT) { 1554*1f5207b7SJohn Levon right_true_state = increment_state(right_true_state); 1555*1f5207b7SJohn Levon right_false_state = increment_state(right_false_state); 1556*1f5207b7SJohn Levon } 1557*1f5207b7SJohn Levon if (right_postop == SPECIAL_DECREMENT) { 1558*1f5207b7SJohn Levon right_true_state = decrement_state(right_true_state); 1559*1f5207b7SJohn Levon right_false_state = decrement_state(right_false_state); 1560*1f5207b7SJohn Levon } 1561*1f5207b7SJohn Levon 1562*1f5207b7SJohn Levon if (estate_rl(left_true_state) && estates_equiv(left_true_state, left_false_state)) { 1563*1f5207b7SJohn Levon left_true_state = NULL; 1564*1f5207b7SJohn Levon left_false_state = NULL; 1565*1f5207b7SJohn Levon } 1566*1f5207b7SJohn Levon 1567*1f5207b7SJohn Levon if (estate_rl(right_true_state) && estates_equiv(right_true_state, right_false_state)) { 1568*1f5207b7SJohn Levon right_true_state = NULL; 1569*1f5207b7SJohn Levon right_false_state = NULL; 1570*1f5207b7SJohn Levon } 1571*1f5207b7SJohn Levon 1572*1f5207b7SJohn Levon /* Don't introduce new states for known true/false conditions */ 1573*1f5207b7SJohn Levon if (rl_equiv(left_orig, estate_rl(left_true_state))) 1574*1f5207b7SJohn Levon left_true_state = NULL; 1575*1f5207b7SJohn Levon if (rl_equiv(left_orig, estate_rl(left_false_state))) 1576*1f5207b7SJohn Levon left_false_state = NULL; 1577*1f5207b7SJohn Levon if (rl_equiv(right_orig, estate_rl(right_true_state))) 1578*1f5207b7SJohn Levon right_true_state = NULL; 1579*1f5207b7SJohn Levon if (rl_equiv(right_orig, estate_rl(right_false_state))) 1580*1f5207b7SJohn Levon right_false_state = NULL; 1581*1f5207b7SJohn Levon 1582*1f5207b7SJohn Levon set_extra_expr_true_false(left, left_true_state, left_false_state); 1583*1f5207b7SJohn Levon set_extra_expr_true_false(right, right_true_state, right_false_state); 1584*1f5207b7SJohn Levon } 1585*1f5207b7SJohn Levon 1586*1f5207b7SJohn Levon static int is_simple_math(struct expression *expr) 1587*1f5207b7SJohn Levon { 1588*1f5207b7SJohn Levon if (!expr) 1589*1f5207b7SJohn Levon return 0; 1590*1f5207b7SJohn Levon if (expr->type != EXPR_BINOP) 1591*1f5207b7SJohn Levon return 0; 1592*1f5207b7SJohn Levon switch (expr->op) { 1593*1f5207b7SJohn Levon case '+': 1594*1f5207b7SJohn Levon case '-': 1595*1f5207b7SJohn Levon case '*': 1596*1f5207b7SJohn Levon return 1; 1597*1f5207b7SJohn Levon } 1598*1f5207b7SJohn Levon return 0; 1599*1f5207b7SJohn Levon } 1600*1f5207b7SJohn Levon 1601*1f5207b7SJohn Levon static void move_known_values(struct expression **left_p, struct expression **right_p) 1602*1f5207b7SJohn Levon { 1603*1f5207b7SJohn Levon struct expression *left = *left_p; 1604*1f5207b7SJohn Levon struct expression *right = *right_p; 1605*1f5207b7SJohn Levon sval_t sval, dummy; 1606*1f5207b7SJohn Levon 1607*1f5207b7SJohn Levon if (get_implied_value(left, &sval)) { 1608*1f5207b7SJohn Levon if (!is_simple_math(right)) 1609*1f5207b7SJohn Levon return; 1610*1f5207b7SJohn Levon if (get_implied_value(right, &dummy)) 1611*1f5207b7SJohn Levon return; 1612*1f5207b7SJohn Levon if (right->op == '*') { 1613*1f5207b7SJohn Levon sval_t divisor; 1614*1f5207b7SJohn Levon 1615*1f5207b7SJohn Levon if (!get_value(right->right, &divisor)) 1616*1f5207b7SJohn Levon return; 1617*1f5207b7SJohn Levon if (divisor.value == 0) 1618*1f5207b7SJohn Levon return; 1619*1f5207b7SJohn Levon *left_p = binop_expression(left, invert_op(right->op), right->right); 1620*1f5207b7SJohn Levon *right_p = right->left; 1621*1f5207b7SJohn Levon return; 1622*1f5207b7SJohn Levon } 1623*1f5207b7SJohn Levon if (right->op == '+' && get_value(right->left, &sval)) { 1624*1f5207b7SJohn Levon *left_p = binop_expression(left, invert_op(right->op), right->left); 1625*1f5207b7SJohn Levon *right_p = right->right; 1626*1f5207b7SJohn Levon return; 1627*1f5207b7SJohn Levon } 1628*1f5207b7SJohn Levon if (get_value(right->right, &sval)) { 1629*1f5207b7SJohn Levon *left_p = binop_expression(left, invert_op(right->op), right->right); 1630*1f5207b7SJohn Levon *right_p = right->left; 1631*1f5207b7SJohn Levon return; 1632*1f5207b7SJohn Levon } 1633*1f5207b7SJohn Levon return; 1634*1f5207b7SJohn Levon } 1635*1f5207b7SJohn Levon if (get_implied_value(right, &sval)) { 1636*1f5207b7SJohn Levon if (!is_simple_math(left)) 1637*1f5207b7SJohn Levon return; 1638*1f5207b7SJohn Levon if (get_implied_value(left, &dummy)) 1639*1f5207b7SJohn Levon return; 1640*1f5207b7SJohn Levon if (left->op == '*') { 1641*1f5207b7SJohn Levon sval_t divisor; 1642*1f5207b7SJohn Levon 1643*1f5207b7SJohn Levon if (!get_value(left->right, &divisor)) 1644*1f5207b7SJohn Levon return; 1645*1f5207b7SJohn Levon if (divisor.value == 0) 1646*1f5207b7SJohn Levon return; 1647*1f5207b7SJohn Levon *right_p = binop_expression(right, invert_op(left->op), left->right); 1648*1f5207b7SJohn Levon *left_p = left->left; 1649*1f5207b7SJohn Levon return; 1650*1f5207b7SJohn Levon } 1651*1f5207b7SJohn Levon if (left->op == '+' && get_value(left->left, &sval)) { 1652*1f5207b7SJohn Levon *right_p = binop_expression(right, invert_op(left->op), left->left); 1653*1f5207b7SJohn Levon *left_p = left->right; 1654*1f5207b7SJohn Levon return; 1655*1f5207b7SJohn Levon } 1656*1f5207b7SJohn Levon 1657*1f5207b7SJohn Levon if (get_value(left->right, &sval)) { 1658*1f5207b7SJohn Levon *right_p = binop_expression(right, invert_op(left->op), left->right); 1659*1f5207b7SJohn Levon *left_p = left->left; 1660*1f5207b7SJohn Levon return; 1661*1f5207b7SJohn Levon } 1662*1f5207b7SJohn Levon return; 1663*1f5207b7SJohn Levon } 1664*1f5207b7SJohn Levon } 1665*1f5207b7SJohn Levon 1666*1f5207b7SJohn Levon /* 1667*1f5207b7SJohn Levon * The reason for do_simple_algebra() is to solve things like: 1668*1f5207b7SJohn Levon * if (foo > 66 || foo + bar > 64) { 1669*1f5207b7SJohn Levon * "foo" is not really a known variable so it won't be handled by 1670*1f5207b7SJohn Levon * move_known_variables() but it's a super common idiom. 1671*1f5207b7SJohn Levon * 1672*1f5207b7SJohn Levon */ 1673*1f5207b7SJohn Levon static int do_simple_algebra(struct expression **left_p, struct expression **right_p) 1674*1f5207b7SJohn Levon { 1675*1f5207b7SJohn Levon struct expression *left = *left_p; 1676*1f5207b7SJohn Levon struct expression *right = *right_p; 1677*1f5207b7SJohn Levon struct range_list *rl; 1678*1f5207b7SJohn Levon sval_t tmp; 1679*1f5207b7SJohn Levon 1680*1f5207b7SJohn Levon if (left->type != EXPR_BINOP || left->op != '+') 1681*1f5207b7SJohn Levon return 0; 1682*1f5207b7SJohn Levon if (can_integer_overflow(get_type(left), left)) 1683*1f5207b7SJohn Levon return 0; 1684*1f5207b7SJohn Levon if (!get_implied_value(right, &tmp)) 1685*1f5207b7SJohn Levon return 0; 1686*1f5207b7SJohn Levon 1687*1f5207b7SJohn Levon if (!get_implied_value(left->left, &tmp) && 1688*1f5207b7SJohn Levon get_implied_rl(left->left, &rl) && 1689*1f5207b7SJohn Levon !is_whole_rl(rl)) { 1690*1f5207b7SJohn Levon *right_p = binop_expression(right, '-', left->left); 1691*1f5207b7SJohn Levon *left_p = left->right; 1692*1f5207b7SJohn Levon return 1; 1693*1f5207b7SJohn Levon } 1694*1f5207b7SJohn Levon if (!get_implied_value(left->right, &tmp) && 1695*1f5207b7SJohn Levon get_implied_rl(left->right, &rl) && 1696*1f5207b7SJohn Levon !is_whole_rl(rl)) { 1697*1f5207b7SJohn Levon *right_p = binop_expression(right, '-', left->right); 1698*1f5207b7SJohn Levon *left_p = left->left; 1699*1f5207b7SJohn Levon return 1; 1700*1f5207b7SJohn Levon } 1701*1f5207b7SJohn Levon 1702*1f5207b7SJohn Levon return 0; 1703*1f5207b7SJohn Levon } 1704*1f5207b7SJohn Levon 1705*1f5207b7SJohn Levon static int match_func_comparison(struct expression *expr) 1706*1f5207b7SJohn Levon { 1707*1f5207b7SJohn Levon struct expression *left = strip_expr(expr->left); 1708*1f5207b7SJohn Levon struct expression *right = strip_expr(expr->right); 1709*1f5207b7SJohn Levon sval_t sval; 1710*1f5207b7SJohn Levon 1711*1f5207b7SJohn Levon /* 1712*1f5207b7SJohn Levon * fixme: think about this harder. We should always be trying to limit 1713*1f5207b7SJohn Levon * the non-call side as well. If we can't determine the limitter does 1714*1f5207b7SJohn Levon * that mean we aren't querying the database and are missing important 1715*1f5207b7SJohn Levon * information? 1716*1f5207b7SJohn Levon */ 1717*1f5207b7SJohn Levon 1718*1f5207b7SJohn Levon if (left->type == EXPR_CALL) { 1719*1f5207b7SJohn Levon if (get_implied_value(left, &sval)) { 1720*1f5207b7SJohn Levon handle_comparison(get_type(expr), left, expr->op, right); 1721*1f5207b7SJohn Levon return 1; 1722*1f5207b7SJohn Levon } 1723*1f5207b7SJohn Levon function_comparison(left, expr->op, right); 1724*1f5207b7SJohn Levon return 1; 1725*1f5207b7SJohn Levon } 1726*1f5207b7SJohn Levon 1727*1f5207b7SJohn Levon if (right->type == EXPR_CALL) { 1728*1f5207b7SJohn Levon if (get_implied_value(right, &sval)) { 1729*1f5207b7SJohn Levon handle_comparison(get_type(expr), left, expr->op, right); 1730*1f5207b7SJohn Levon return 1; 1731*1f5207b7SJohn Levon } 1732*1f5207b7SJohn Levon function_comparison(left, expr->op, right); 1733*1f5207b7SJohn Levon return 1; 1734*1f5207b7SJohn Levon } 1735*1f5207b7SJohn Levon 1736*1f5207b7SJohn Levon return 0; 1737*1f5207b7SJohn Levon } 1738*1f5207b7SJohn Levon 1739*1f5207b7SJohn Levon /* Handle conditions like "if (foo + bar < foo) {" */ 1740*1f5207b7SJohn Levon static int handle_integer_overflow_test(struct expression *expr) 1741*1f5207b7SJohn Levon { 1742*1f5207b7SJohn Levon struct expression *left, *right; 1743*1f5207b7SJohn Levon struct symbol *type; 1744*1f5207b7SJohn Levon sval_t left_min, right_min, min, max; 1745*1f5207b7SJohn Levon 1746*1f5207b7SJohn Levon if (expr->op != '<' && expr->op != SPECIAL_UNSIGNED_LT) 1747*1f5207b7SJohn Levon return 0; 1748*1f5207b7SJohn Levon 1749*1f5207b7SJohn Levon left = strip_parens(expr->left); 1750*1f5207b7SJohn Levon right = strip_parens(expr->right); 1751*1f5207b7SJohn Levon 1752*1f5207b7SJohn Levon if (left->op != '+') 1753*1f5207b7SJohn Levon return 0; 1754*1f5207b7SJohn Levon 1755*1f5207b7SJohn Levon type = get_type(expr); 1756*1f5207b7SJohn Levon if (!type) 1757*1f5207b7SJohn Levon return 0; 1758*1f5207b7SJohn Levon if (type_positive_bits(type) == 32) { 1759*1f5207b7SJohn Levon max.type = &uint_ctype; 1760*1f5207b7SJohn Levon max.uvalue = (unsigned int)-1; 1761*1f5207b7SJohn Levon } else if (type_positive_bits(type) == 64) { 1762*1f5207b7SJohn Levon max.type = &ulong_ctype; 1763*1f5207b7SJohn Levon max.value = (unsigned long long)-1; 1764*1f5207b7SJohn Levon } else { 1765*1f5207b7SJohn Levon return 0; 1766*1f5207b7SJohn Levon } 1767*1f5207b7SJohn Levon 1768*1f5207b7SJohn Levon if (!expr_equiv(left->left, right) && !expr_equiv(left->right, right)) 1769*1f5207b7SJohn Levon return 0; 1770*1f5207b7SJohn Levon 1771*1f5207b7SJohn Levon get_absolute_min(left->left, &left_min); 1772*1f5207b7SJohn Levon get_absolute_min(left->right, &right_min); 1773*1f5207b7SJohn Levon min = sval_binop(left_min, '+', right_min); 1774*1f5207b7SJohn Levon 1775*1f5207b7SJohn Levon set_extra_chunk_true_false(left, NULL, alloc_estate_range(min, max)); 1776*1f5207b7SJohn Levon return 1; 1777*1f5207b7SJohn Levon } 1778*1f5207b7SJohn Levon 1779*1f5207b7SJohn Levon static void match_comparison(struct expression *expr) 1780*1f5207b7SJohn Levon { 1781*1f5207b7SJohn Levon struct expression *left_orig = strip_parens(expr->left); 1782*1f5207b7SJohn Levon struct expression *right_orig = strip_parens(expr->right); 1783*1f5207b7SJohn Levon struct expression *left, *right, *tmp; 1784*1f5207b7SJohn Levon struct expression *prev; 1785*1f5207b7SJohn Levon struct symbol *type; 1786*1f5207b7SJohn Levon int redo, count; 1787*1f5207b7SJohn Levon 1788*1f5207b7SJohn Levon if (match_func_comparison(expr)) 1789*1f5207b7SJohn Levon return; 1790*1f5207b7SJohn Levon 1791*1f5207b7SJohn Levon type = get_type(expr); 1792*1f5207b7SJohn Levon if (!type) 1793*1f5207b7SJohn Levon type = &llong_ctype; 1794*1f5207b7SJohn Levon 1795*1f5207b7SJohn Levon if (handle_integer_overflow_test(expr)) 1796*1f5207b7SJohn Levon return; 1797*1f5207b7SJohn Levon 1798*1f5207b7SJohn Levon left = left_orig; 1799*1f5207b7SJohn Levon right = right_orig; 1800*1f5207b7SJohn Levon move_known_values(&left, &right); 1801*1f5207b7SJohn Levon handle_comparison(type, left, expr->op, right); 1802*1f5207b7SJohn Levon 1803*1f5207b7SJohn Levon left = left_orig; 1804*1f5207b7SJohn Levon right = right_orig; 1805*1f5207b7SJohn Levon if (do_simple_algebra(&left, &right)) 1806*1f5207b7SJohn Levon handle_comparison(type, left, expr->op, right); 1807*1f5207b7SJohn Levon 1808*1f5207b7SJohn Levon prev = get_assigned_expr(left_orig); 1809*1f5207b7SJohn Levon if (is_simple_math(prev) && has_variable(prev, left_orig) == 0) { 1810*1f5207b7SJohn Levon left = prev; 1811*1f5207b7SJohn Levon right = right_orig; 1812*1f5207b7SJohn Levon move_known_values(&left, &right); 1813*1f5207b7SJohn Levon handle_comparison(type, left, expr->op, right); 1814*1f5207b7SJohn Levon } 1815*1f5207b7SJohn Levon 1816*1f5207b7SJohn Levon prev = get_assigned_expr(right_orig); 1817*1f5207b7SJohn Levon if (is_simple_math(prev) && has_variable(prev, right_orig) == 0) { 1818*1f5207b7SJohn Levon left = left_orig; 1819*1f5207b7SJohn Levon right = prev; 1820*1f5207b7SJohn Levon move_known_values(&left, &right); 1821*1f5207b7SJohn Levon handle_comparison(type, left, expr->op, right); 1822*1f5207b7SJohn Levon } 1823*1f5207b7SJohn Levon 1824*1f5207b7SJohn Levon redo = 0; 1825*1f5207b7SJohn Levon left = left_orig; 1826*1f5207b7SJohn Levon right = right_orig; 1827*1f5207b7SJohn Levon if (get_last_expr_from_expression_stmt(left_orig)) { 1828*1f5207b7SJohn Levon left = get_last_expr_from_expression_stmt(left_orig); 1829*1f5207b7SJohn Levon redo = 1; 1830*1f5207b7SJohn Levon } 1831*1f5207b7SJohn Levon if (get_last_expr_from_expression_stmt(right_orig)) { 1832*1f5207b7SJohn Levon right = get_last_expr_from_expression_stmt(right_orig); 1833*1f5207b7SJohn Levon redo = 1; 1834*1f5207b7SJohn Levon } 1835*1f5207b7SJohn Levon 1836*1f5207b7SJohn Levon if (!redo) 1837*1f5207b7SJohn Levon return; 1838*1f5207b7SJohn Levon 1839*1f5207b7SJohn Levon count = 0; 1840*1f5207b7SJohn Levon while ((tmp = get_assigned_expr(left))) { 1841*1f5207b7SJohn Levon if (count++ > 3) 1842*1f5207b7SJohn Levon break; 1843*1f5207b7SJohn Levon left = strip_expr(tmp); 1844*1f5207b7SJohn Levon } 1845*1f5207b7SJohn Levon count = 0; 1846*1f5207b7SJohn Levon while ((tmp = get_assigned_expr(right))) { 1847*1f5207b7SJohn Levon if (count++ > 3) 1848*1f5207b7SJohn Levon break; 1849*1f5207b7SJohn Levon right = strip_expr(tmp); 1850*1f5207b7SJohn Levon } 1851*1f5207b7SJohn Levon 1852*1f5207b7SJohn Levon handle_comparison(type, left, expr->op, right); 1853*1f5207b7SJohn Levon } 1854*1f5207b7SJohn Levon 1855*1f5207b7SJohn Levon static sval_t get_high_mask(sval_t known) 1856*1f5207b7SJohn Levon { 1857*1f5207b7SJohn Levon sval_t ret; 1858*1f5207b7SJohn Levon int i; 1859*1f5207b7SJohn Levon 1860*1f5207b7SJohn Levon ret = known; 1861*1f5207b7SJohn Levon ret.value = 0; 1862*1f5207b7SJohn Levon 1863*1f5207b7SJohn Levon for (i = type_bits(known.type) - 1; i >= 0; i--) { 1864*1f5207b7SJohn Levon if (known.uvalue & (1ULL << i)) 1865*1f5207b7SJohn Levon ret.uvalue |= (1ULL << i); 1866*1f5207b7SJohn Levon else 1867*1f5207b7SJohn Levon return ret; 1868*1f5207b7SJohn Levon 1869*1f5207b7SJohn Levon } 1870*1f5207b7SJohn Levon return ret; 1871*1f5207b7SJohn Levon } 1872*1f5207b7SJohn Levon 1873*1f5207b7SJohn Levon static void handle_AND_op(struct expression *var, sval_t known) 1874*1f5207b7SJohn Levon { 1875*1f5207b7SJohn Levon struct range_list *orig_rl; 1876*1f5207b7SJohn Levon struct range_list *true_rl = NULL; 1877*1f5207b7SJohn Levon struct range_list *false_rl = NULL; 1878*1f5207b7SJohn Levon int bit; 1879*1f5207b7SJohn Levon sval_t low_mask = known; 1880*1f5207b7SJohn Levon sval_t high_mask; 1881*1f5207b7SJohn Levon sval_t max; 1882*1f5207b7SJohn Levon 1883*1f5207b7SJohn Levon get_absolute_rl(var, &orig_rl); 1884*1f5207b7SJohn Levon 1885*1f5207b7SJohn Levon if (known.value > 0) { 1886*1f5207b7SJohn Levon bit = ffsll(known.value) - 1; 1887*1f5207b7SJohn Levon low_mask.uvalue = (1ULL << bit) - 1; 1888*1f5207b7SJohn Levon true_rl = remove_range(orig_rl, sval_type_val(known.type, 0), low_mask); 1889*1f5207b7SJohn Levon } 1890*1f5207b7SJohn Levon high_mask = get_high_mask(known); 1891*1f5207b7SJohn Levon if (high_mask.value) { 1892*1f5207b7SJohn Levon bit = ffsll(high_mask.value) - 1; 1893*1f5207b7SJohn Levon low_mask.uvalue = (1ULL << bit) - 1; 1894*1f5207b7SJohn Levon 1895*1f5207b7SJohn Levon false_rl = orig_rl; 1896*1f5207b7SJohn Levon if (sval_is_negative(rl_min(orig_rl))) 1897*1f5207b7SJohn Levon false_rl = remove_range(false_rl, sval_type_min(known.type), sval_type_val(known.type, -1)); 1898*1f5207b7SJohn Levon false_rl = remove_range(false_rl, low_mask, sval_type_max(known.type)); 1899*1f5207b7SJohn Levon if (type_signed(high_mask.type) && type_unsigned(rl_type(false_rl))) { 1900*1f5207b7SJohn Levon false_rl = remove_range(false_rl, 1901*1f5207b7SJohn Levon sval_type_val(rl_type(false_rl), sval_type_max(known.type).uvalue), 1902*1f5207b7SJohn Levon sval_type_val(rl_type(false_rl), -1)); 1903*1f5207b7SJohn Levon } 1904*1f5207b7SJohn Levon } else if (known.value == 1 && 1905*1f5207b7SJohn Levon get_hard_max(var, &max) && 1906*1f5207b7SJohn Levon sval_cmp(max, rl_max(orig_rl)) == 0 && 1907*1f5207b7SJohn Levon max.value & 1) { 1908*1f5207b7SJohn Levon false_rl = remove_range(orig_rl, max, max); 1909*1f5207b7SJohn Levon } 1910*1f5207b7SJohn Levon set_extra_expr_true_false(var, 1911*1f5207b7SJohn Levon true_rl ? alloc_estate_rl(true_rl) : NULL, 1912*1f5207b7SJohn Levon false_rl ? alloc_estate_rl(false_rl) : NULL); 1913*1f5207b7SJohn Levon } 1914*1f5207b7SJohn Levon 1915*1f5207b7SJohn Levon static void handle_AND_condition(struct expression *expr) 1916*1f5207b7SJohn Levon { 1917*1f5207b7SJohn Levon sval_t known; 1918*1f5207b7SJohn Levon 1919*1f5207b7SJohn Levon if (get_implied_value(expr->left, &known)) 1920*1f5207b7SJohn Levon handle_AND_op(expr->right, known); 1921*1f5207b7SJohn Levon else if (get_implied_value(expr->right, &known)) 1922*1f5207b7SJohn Levon handle_AND_op(expr->left, known); 1923*1f5207b7SJohn Levon } 1924*1f5207b7SJohn Levon 1925*1f5207b7SJohn Levon static void handle_MOD_condition(struct expression *expr) 1926*1f5207b7SJohn Levon { 1927*1f5207b7SJohn Levon struct range_list *orig_rl; 1928*1f5207b7SJohn Levon struct range_list *true_rl; 1929*1f5207b7SJohn Levon struct range_list *false_rl = NULL; 1930*1f5207b7SJohn Levon sval_t right; 1931*1f5207b7SJohn Levon sval_t zero; 1932*1f5207b7SJohn Levon 1933*1f5207b7SJohn Levon if (!get_implied_value(expr->right, &right) || right.value == 0) 1934*1f5207b7SJohn Levon return; 1935*1f5207b7SJohn Levon get_absolute_rl(expr->left, &orig_rl); 1936*1f5207b7SJohn Levon 1937*1f5207b7SJohn Levon zero.value = 0; 1938*1f5207b7SJohn Levon zero.type = rl_type(orig_rl); 1939*1f5207b7SJohn Levon 1940*1f5207b7SJohn Levon /* We're basically dorking around the min and max here */ 1941*1f5207b7SJohn Levon true_rl = remove_range(orig_rl, zero, zero); 1942*1f5207b7SJohn Levon if (!sval_is_max(rl_max(true_rl)) && 1943*1f5207b7SJohn Levon !(rl_max(true_rl).value % right.value)) 1944*1f5207b7SJohn Levon true_rl = remove_range(true_rl, rl_max(true_rl), rl_max(true_rl)); 1945*1f5207b7SJohn Levon 1946*1f5207b7SJohn Levon if (rl_equiv(true_rl, orig_rl)) 1947*1f5207b7SJohn Levon true_rl = NULL; 1948*1f5207b7SJohn Levon 1949*1f5207b7SJohn Levon if (sval_is_positive(rl_min(orig_rl)) && 1950*1f5207b7SJohn Levon (rl_max(orig_rl).value - rl_min(orig_rl).value) / right.value < 5) { 1951*1f5207b7SJohn Levon sval_t add; 1952*1f5207b7SJohn Levon int i; 1953*1f5207b7SJohn Levon 1954*1f5207b7SJohn Levon add = rl_min(orig_rl); 1955*1f5207b7SJohn Levon add.value += right.value - (add.value % right.value); 1956*1f5207b7SJohn Levon add.value -= right.value; 1957*1f5207b7SJohn Levon 1958*1f5207b7SJohn Levon for (i = 0; i < 5; i++) { 1959*1f5207b7SJohn Levon add.value += right.value; 1960*1f5207b7SJohn Levon if (add.value > rl_max(orig_rl).value) 1961*1f5207b7SJohn Levon break; 1962*1f5207b7SJohn Levon add_range(&false_rl, add, add); 1963*1f5207b7SJohn Levon } 1964*1f5207b7SJohn Levon } else { 1965*1f5207b7SJohn Levon if (rl_min(orig_rl).uvalue != 0 && 1966*1f5207b7SJohn Levon rl_min(orig_rl).uvalue < right.uvalue) { 1967*1f5207b7SJohn Levon sval_t chop = right; 1968*1f5207b7SJohn Levon chop.value--; 1969*1f5207b7SJohn Levon false_rl = remove_range(orig_rl, zero, chop); 1970*1f5207b7SJohn Levon } 1971*1f5207b7SJohn Levon 1972*1f5207b7SJohn Levon if (!sval_is_max(rl_max(orig_rl)) && 1973*1f5207b7SJohn Levon (rl_max(orig_rl).value % right.value)) { 1974*1f5207b7SJohn Levon sval_t chop = rl_max(orig_rl); 1975*1f5207b7SJohn Levon chop.value -= chop.value % right.value; 1976*1f5207b7SJohn Levon chop.value++; 1977*1f5207b7SJohn Levon if (!false_rl) 1978*1f5207b7SJohn Levon false_rl = clone_rl(orig_rl); 1979*1f5207b7SJohn Levon false_rl = remove_range(false_rl, chop, rl_max(orig_rl)); 1980*1f5207b7SJohn Levon } 1981*1f5207b7SJohn Levon } 1982*1f5207b7SJohn Levon 1983*1f5207b7SJohn Levon set_extra_expr_true_false(expr->left, 1984*1f5207b7SJohn Levon true_rl ? alloc_estate_rl(true_rl) : NULL, 1985*1f5207b7SJohn Levon false_rl ? alloc_estate_rl(false_rl) : NULL); 1986*1f5207b7SJohn Levon } 1987*1f5207b7SJohn Levon 1988*1f5207b7SJohn Levon /* this is actually hooked from smatch_implied.c... it's hacky, yes */ 1989*1f5207b7SJohn Levon void __extra_match_condition(struct expression *expr) 1990*1f5207b7SJohn Levon { 1991*1f5207b7SJohn Levon struct smatch_state *pre_state; 1992*1f5207b7SJohn Levon struct smatch_state *true_state; 1993*1f5207b7SJohn Levon struct smatch_state *false_state; 1994*1f5207b7SJohn Levon struct range_list *pre_rl; 1995*1f5207b7SJohn Levon 1996*1f5207b7SJohn Levon expr = strip_expr(expr); 1997*1f5207b7SJohn Levon switch (expr->type) { 1998*1f5207b7SJohn Levon case EXPR_CALL: 1999*1f5207b7SJohn Levon function_comparison(expr, SPECIAL_NOTEQUAL, zero_expr()); 2000*1f5207b7SJohn Levon return; 2001*1f5207b7SJohn Levon case EXPR_PREOP: 2002*1f5207b7SJohn Levon case EXPR_SYMBOL: 2003*1f5207b7SJohn Levon case EXPR_DEREF: { 2004*1f5207b7SJohn Levon sval_t zero; 2005*1f5207b7SJohn Levon 2006*1f5207b7SJohn Levon zero = sval_blank(expr); 2007*1f5207b7SJohn Levon zero.value = 0; 2008*1f5207b7SJohn Levon 2009*1f5207b7SJohn Levon pre_state = get_extra_state(expr); 2010*1f5207b7SJohn Levon if (estate_is_empty(pre_state)) 2011*1f5207b7SJohn Levon return; 2012*1f5207b7SJohn Levon if (pre_state) 2013*1f5207b7SJohn Levon pre_rl = estate_rl(pre_state); 2014*1f5207b7SJohn Levon else 2015*1f5207b7SJohn Levon get_absolute_rl(expr, &pre_rl); 2016*1f5207b7SJohn Levon if (possibly_true_rl(pre_rl, SPECIAL_EQUAL, rl_zero())) 2017*1f5207b7SJohn Levon false_state = alloc_estate_sval(zero); 2018*1f5207b7SJohn Levon else 2019*1f5207b7SJohn Levon false_state = alloc_estate_empty(); 2020*1f5207b7SJohn Levon true_state = alloc_estate_rl(remove_range(pre_rl, zero, zero)); 2021*1f5207b7SJohn Levon set_extra_expr_true_false(expr, true_state, false_state); 2022*1f5207b7SJohn Levon return; 2023*1f5207b7SJohn Levon } 2024*1f5207b7SJohn Levon case EXPR_COMPARE: 2025*1f5207b7SJohn Levon match_comparison(expr); 2026*1f5207b7SJohn Levon return; 2027*1f5207b7SJohn Levon case EXPR_ASSIGNMENT: 2028*1f5207b7SJohn Levon __extra_match_condition(expr->left); 2029*1f5207b7SJohn Levon return; 2030*1f5207b7SJohn Levon case EXPR_BINOP: 2031*1f5207b7SJohn Levon if (expr->op == '&') 2032*1f5207b7SJohn Levon handle_AND_condition(expr); 2033*1f5207b7SJohn Levon if (expr->op == '%') 2034*1f5207b7SJohn Levon handle_MOD_condition(expr); 2035*1f5207b7SJohn Levon return; 2036*1f5207b7SJohn Levon } 2037*1f5207b7SJohn Levon } 2038*1f5207b7SJohn Levon 2039*1f5207b7SJohn Levon static void assume_indexes_are_valid(struct expression *expr) 2040*1f5207b7SJohn Levon { 2041*1f5207b7SJohn Levon struct expression *array_expr; 2042*1f5207b7SJohn Levon int array_size; 2043*1f5207b7SJohn Levon struct expression *offset; 2044*1f5207b7SJohn Levon struct symbol *offset_type; 2045*1f5207b7SJohn Levon struct range_list *rl_before; 2046*1f5207b7SJohn Levon struct range_list *rl_after; 2047*1f5207b7SJohn Levon struct range_list *filter = NULL; 2048*1f5207b7SJohn Levon sval_t size; 2049*1f5207b7SJohn Levon 2050*1f5207b7SJohn Levon expr = strip_expr(expr); 2051*1f5207b7SJohn Levon if (!is_array(expr)) 2052*1f5207b7SJohn Levon return; 2053*1f5207b7SJohn Levon 2054*1f5207b7SJohn Levon offset = get_array_offset(expr); 2055*1f5207b7SJohn Levon offset_type = get_type(offset); 2056*1f5207b7SJohn Levon if (offset_type && type_signed(offset_type)) { 2057*1f5207b7SJohn Levon filter = alloc_rl(sval_type_min(offset_type), 2058*1f5207b7SJohn Levon sval_type_val(offset_type, -1)); 2059*1f5207b7SJohn Levon } 2060*1f5207b7SJohn Levon 2061*1f5207b7SJohn Levon array_expr = get_array_base(expr); 2062*1f5207b7SJohn Levon array_size = get_real_array_size(array_expr); 2063*1f5207b7SJohn Levon if (array_size > 1) { 2064*1f5207b7SJohn Levon size = sval_type_val(offset_type, array_size); 2065*1f5207b7SJohn Levon add_range(&filter, size, sval_type_max(offset_type)); 2066*1f5207b7SJohn Levon } 2067*1f5207b7SJohn Levon 2068*1f5207b7SJohn Levon if (!filter) 2069*1f5207b7SJohn Levon return; 2070*1f5207b7SJohn Levon get_absolute_rl(offset, &rl_before); 2071*1f5207b7SJohn Levon rl_after = rl_filter(rl_before, filter); 2072*1f5207b7SJohn Levon if (rl_equiv(rl_before, rl_after)) 2073*1f5207b7SJohn Levon return; 2074*1f5207b7SJohn Levon set_extra_expr_nomod(offset, alloc_estate_rl(rl_after)); 2075*1f5207b7SJohn Levon } 2076*1f5207b7SJohn Levon 2077*1f5207b7SJohn Levon /* returns 1 if it is not possible for expr to be value, otherwise returns 0 */ 2078*1f5207b7SJohn Levon int implied_not_equal(struct expression *expr, long long val) 2079*1f5207b7SJohn Levon { 2080*1f5207b7SJohn Levon return !possibly_false(expr, SPECIAL_NOTEQUAL, value_expr(val)); 2081*1f5207b7SJohn Levon } 2082*1f5207b7SJohn Levon 2083*1f5207b7SJohn Levon int implied_not_equal_name_sym(char *name, struct symbol *sym, long long val) 2084*1f5207b7SJohn Levon { 2085*1f5207b7SJohn Levon struct smatch_state *estate; 2086*1f5207b7SJohn Levon 2087*1f5207b7SJohn Levon estate = get_state(SMATCH_EXTRA, name, sym); 2088*1f5207b7SJohn Levon if (!estate) 2089*1f5207b7SJohn Levon return 0; 2090*1f5207b7SJohn Levon if (!rl_has_sval(estate_rl(estate), sval_type_val(estate_type(estate), 0))) 2091*1f5207b7SJohn Levon return 1; 2092*1f5207b7SJohn Levon return 0; 2093*1f5207b7SJohn Levon } 2094*1f5207b7SJohn Levon 2095*1f5207b7SJohn Levon int parent_is_null_var_sym(const char *name, struct symbol *sym) 2096*1f5207b7SJohn Levon { 2097*1f5207b7SJohn Levon char buf[256]; 2098*1f5207b7SJohn Levon char *start; 2099*1f5207b7SJohn Levon char *end; 2100*1f5207b7SJohn Levon struct smatch_state *state; 2101*1f5207b7SJohn Levon 2102*1f5207b7SJohn Levon strncpy(buf, name, sizeof(buf) - 1); 2103*1f5207b7SJohn Levon buf[sizeof(buf) - 1] = '\0'; 2104*1f5207b7SJohn Levon 2105*1f5207b7SJohn Levon start = &buf[0]; 2106*1f5207b7SJohn Levon while (*start == '*') { 2107*1f5207b7SJohn Levon start++; 2108*1f5207b7SJohn Levon state = get_state(SMATCH_EXTRA, start, sym); 2109*1f5207b7SJohn Levon if (!state) 2110*1f5207b7SJohn Levon continue; 2111*1f5207b7SJohn Levon if (!estate_rl(state)) 2112*1f5207b7SJohn Levon return 1; 2113*1f5207b7SJohn Levon if (estate_min(state).value == 0 && 2114*1f5207b7SJohn Levon estate_max(state).value == 0) 2115*1f5207b7SJohn Levon return 1; 2116*1f5207b7SJohn Levon } 2117*1f5207b7SJohn Levon 2118*1f5207b7SJohn Levon start = &buf[0]; 2119*1f5207b7SJohn Levon while (*start == '&') 2120*1f5207b7SJohn Levon start++; 2121*1f5207b7SJohn Levon 2122*1f5207b7SJohn Levon while ((end = strrchr(start, '-'))) { 2123*1f5207b7SJohn Levon *end = '\0'; 2124*1f5207b7SJohn Levon state = __get_state(SMATCH_EXTRA, start, sym); 2125*1f5207b7SJohn Levon if (!state) 2126*1f5207b7SJohn Levon continue; 2127*1f5207b7SJohn Levon if (estate_min(state).value == 0 && 2128*1f5207b7SJohn Levon estate_max(state).value == 0) 2129*1f5207b7SJohn Levon return 1; 2130*1f5207b7SJohn Levon } 2131*1f5207b7SJohn Levon return 0; 2132*1f5207b7SJohn Levon } 2133*1f5207b7SJohn Levon 2134*1f5207b7SJohn Levon int parent_is_null(struct expression *expr) 2135*1f5207b7SJohn Levon { 2136*1f5207b7SJohn Levon struct symbol *sym; 2137*1f5207b7SJohn Levon char *var; 2138*1f5207b7SJohn Levon int ret = 0; 2139*1f5207b7SJohn Levon 2140*1f5207b7SJohn Levon expr = strip_expr(expr); 2141*1f5207b7SJohn Levon var = expr_to_var_sym(expr, &sym); 2142*1f5207b7SJohn Levon if (!var || !sym) 2143*1f5207b7SJohn Levon goto free; 2144*1f5207b7SJohn Levon ret = parent_is_null_var_sym(var, sym); 2145*1f5207b7SJohn Levon free: 2146*1f5207b7SJohn Levon free_string(var); 2147*1f5207b7SJohn Levon return ret; 2148*1f5207b7SJohn Levon } 2149*1f5207b7SJohn Levon 2150*1f5207b7SJohn Levon static int param_used_callback(void *found, int argc, char **argv, char **azColName) 2151*1f5207b7SJohn Levon { 2152*1f5207b7SJohn Levon *(int *)found = 1; 2153*1f5207b7SJohn Levon return 0; 2154*1f5207b7SJohn Levon } 2155*1f5207b7SJohn Levon 2156*1f5207b7SJohn Levon static int filter_unused_kzalloc_info(struct expression *call, int param, char *printed_name, struct sm_state *sm) 2157*1f5207b7SJohn Levon { 2158*1f5207b7SJohn Levon sval_t sval; 2159*1f5207b7SJohn Levon int found = 0; 2160*1f5207b7SJohn Levon 2161*1f5207b7SJohn Levon /* for function pointers assume everything is used */ 2162*1f5207b7SJohn Levon if (call->fn->type != EXPR_SYMBOL) 2163*1f5207b7SJohn Levon return 0; 2164*1f5207b7SJohn Levon 2165*1f5207b7SJohn Levon /* 2166*1f5207b7SJohn Levon * This is to handle __builtin_mul_overflow(). In an ideal world we 2167*1f5207b7SJohn Levon * would only need this for invalid code. 2168*1f5207b7SJohn Levon * 2169*1f5207b7SJohn Levon */ 2170*1f5207b7SJohn Levon if (!call->fn->symbol) 2171*1f5207b7SJohn Levon return 0; 2172*1f5207b7SJohn Levon 2173*1f5207b7SJohn Levon /* 2174*1f5207b7SJohn Levon * kzalloc() information is treated as special because so there is just 2175*1f5207b7SJohn Levon * a lot of stuff initialized to zero and it makes building the database 2176*1f5207b7SJohn Levon * take hours and hours. 2177*1f5207b7SJohn Levon * 2178*1f5207b7SJohn Levon * In theory, we should just remove this line and not pass any unused 2179*1f5207b7SJohn Levon * information, but I'm not sure enough that this code works so I want 2180*1f5207b7SJohn Levon * to hold off on that for now. 2181*1f5207b7SJohn Levon */ 2182*1f5207b7SJohn Levon if (!estate_get_single_value(sm->state, &sval) || sval.value != 0) 2183*1f5207b7SJohn Levon return 0; 2184*1f5207b7SJohn Levon 2185*1f5207b7SJohn Levon run_sql(¶m_used_callback, &found, 2186*1f5207b7SJohn Levon "select * from return_implies where %s and type = %d and parameter = %d and key = '%s';", 2187*1f5207b7SJohn Levon get_static_filter(call->fn->symbol), PARAM_USED, param, printed_name); 2188*1f5207b7SJohn Levon if (found) 2189*1f5207b7SJohn Levon return 0; 2190*1f5207b7SJohn Levon 2191*1f5207b7SJohn Levon /* If the database is not built yet, then assume everything is used */ 2192*1f5207b7SJohn Levon run_sql(¶m_used_callback, &found, 2193*1f5207b7SJohn Levon "select * from return_implies where %s and type = %d;", 2194*1f5207b7SJohn Levon get_static_filter(call->fn->symbol), PARAM_USED); 2195*1f5207b7SJohn Levon if (!found) 2196*1f5207b7SJohn Levon return 0; 2197*1f5207b7SJohn Levon 2198*1f5207b7SJohn Levon return 1; 2199*1f5207b7SJohn Levon } 2200*1f5207b7SJohn Levon 2201*1f5207b7SJohn Levon struct range_list *intersect_with_real_abs_var_sym(const char *name, struct symbol *sym, struct range_list *start) 2202*1f5207b7SJohn Levon { 2203*1f5207b7SJohn Levon struct smatch_state *state; 2204*1f5207b7SJohn Levon 2205*1f5207b7SJohn Levon /* 2206*1f5207b7SJohn Levon * Here is the difference between implied value and real absolute, say 2207*1f5207b7SJohn Levon * you have: 2208*1f5207b7SJohn Levon * 2209*1f5207b7SJohn Levon * int a = (u8)x; 2210*1f5207b7SJohn Levon * 2211*1f5207b7SJohn Levon * Then you know that a is 0-255. That's real absolute. But you don't 2212*1f5207b7SJohn Levon * know for sure that it actually goes up to 255. So it's not implied. 2213*1f5207b7SJohn Levon * Implied indicates a degree of certainty. 2214*1f5207b7SJohn Levon * 2215*1f5207b7SJohn Levon * But then say you cap "a" at 8. That means you know it goes up to 2216*1f5207b7SJohn Levon * 8. So now the implied value is s32min-8. But you can combine it 2217*1f5207b7SJohn Levon * with the real absolute to say that actually it's 0-8. 2218*1f5207b7SJohn Levon * 2219*1f5207b7SJohn Levon * We are combining it here. But now that I think about it, this is 2220*1f5207b7SJohn Levon * probably not the ideal place to combine it because it should proably 2221*1f5207b7SJohn Levon * be done earlier. Oh well, this is an improvement on what was there 2222*1f5207b7SJohn Levon * before so I'm going to commit this code. 2223*1f5207b7SJohn Levon * 2224*1f5207b7SJohn Levon */ 2225*1f5207b7SJohn Levon 2226*1f5207b7SJohn Levon state = get_real_absolute_state_var_sym(name, sym); 2227*1f5207b7SJohn Levon if (!state || !estate_rl(state)) 2228*1f5207b7SJohn Levon return start; 2229*1f5207b7SJohn Levon 2230*1f5207b7SJohn Levon return rl_intersection(estate_rl(state), start); 2231*1f5207b7SJohn Levon } 2232*1f5207b7SJohn Levon 2233*1f5207b7SJohn Levon struct range_list *intersect_with_real_abs_expr(struct expression *expr, struct range_list *start) 2234*1f5207b7SJohn Levon { 2235*1f5207b7SJohn Levon struct smatch_state *state; 2236*1f5207b7SJohn Levon struct range_list *abs_rl; 2237*1f5207b7SJohn Levon 2238*1f5207b7SJohn Levon state = get_real_absolute_state(expr); 2239*1f5207b7SJohn Levon if (!state || !estate_rl(state)) 2240*1f5207b7SJohn Levon return start; 2241*1f5207b7SJohn Levon 2242*1f5207b7SJohn Levon abs_rl = cast_rl(rl_type(start), estate_rl(state)); 2243*1f5207b7SJohn Levon return rl_intersection(abs_rl, start); 2244*1f5207b7SJohn Levon } 2245*1f5207b7SJohn Levon 2246*1f5207b7SJohn Levon static void struct_member_callback(struct expression *call, int param, char *printed_name, struct sm_state *sm) 2247*1f5207b7SJohn Levon { 2248*1f5207b7SJohn Levon struct range_list *rl; 2249*1f5207b7SJohn Levon 2250*1f5207b7SJohn Levon if (estate_is_whole(sm->state)) 2251*1f5207b7SJohn Levon return; 2252*1f5207b7SJohn Levon if (filter_unused_kzalloc_info(call, param, printed_name, sm)) 2253*1f5207b7SJohn Levon return; 2254*1f5207b7SJohn Levon rl = estate_rl(sm->state); 2255*1f5207b7SJohn Levon rl = intersect_with_real_abs_var_sym(sm->name, sm->sym, rl); 2256*1f5207b7SJohn Levon sql_insert_caller_info(call, PARAM_VALUE, param, printed_name, show_rl(rl)); 2257*1f5207b7SJohn Levon if (estate_has_fuzzy_max(sm->state)) 2258*1f5207b7SJohn Levon sql_insert_caller_info(call, FUZZY_MAX, param, printed_name, 2259*1f5207b7SJohn Levon sval_to_str(estate_get_fuzzy_max(sm->state))); 2260*1f5207b7SJohn Levon } 2261*1f5207b7SJohn Levon 2262*1f5207b7SJohn Levon static void returned_struct_members(int return_id, char *return_ranges, struct expression *expr) 2263*1f5207b7SJohn Levon { 2264*1f5207b7SJohn Levon struct symbol *returned_sym; 2265*1f5207b7SJohn Levon struct sm_state *sm; 2266*1f5207b7SJohn Levon const char *param_name; 2267*1f5207b7SJohn Levon char *compare_str; 2268*1f5207b7SJohn Levon char buf[256]; 2269*1f5207b7SJohn Levon 2270*1f5207b7SJohn Levon returned_sym = expr_to_sym(expr); 2271*1f5207b7SJohn Levon if (!returned_sym) 2272*1f5207b7SJohn Levon return; 2273*1f5207b7SJohn Levon 2274*1f5207b7SJohn Levon FOR_EACH_MY_SM(my_id, __get_cur_stree(), sm) { 2275*1f5207b7SJohn Levon if (!estate_rl(sm->state)) 2276*1f5207b7SJohn Levon continue; 2277*1f5207b7SJohn Levon if (returned_sym != sm->sym) 2278*1f5207b7SJohn Levon continue; 2279*1f5207b7SJohn Levon 2280*1f5207b7SJohn Levon param_name = get_param_name(sm); 2281*1f5207b7SJohn Levon if (!param_name) 2282*1f5207b7SJohn Levon continue; 2283*1f5207b7SJohn Levon if (strcmp(param_name, "$") == 0) 2284*1f5207b7SJohn Levon continue; 2285*1f5207b7SJohn Levon compare_str = name_sym_to_param_comparison(sm->name, sm->sym); 2286*1f5207b7SJohn Levon if (!compare_str && estate_is_whole(sm->state)) 2287*1f5207b7SJohn Levon continue; 2288*1f5207b7SJohn Levon snprintf(buf, sizeof(buf), "%s%s", sm->state->name, compare_str ?: ""); 2289*1f5207b7SJohn Levon 2290*1f5207b7SJohn Levon sql_insert_return_states(return_id, return_ranges, PARAM_VALUE, 2291*1f5207b7SJohn Levon -1, param_name, buf); 2292*1f5207b7SJohn Levon } END_FOR_EACH_SM(sm); 2293*1f5207b7SJohn Levon } 2294*1f5207b7SJohn Levon 2295*1f5207b7SJohn Levon static void db_limited_before(void) 2296*1f5207b7SJohn Levon { 2297*1f5207b7SJohn Levon unmatched_stree = clone_stree(__get_cur_stree()); 2298*1f5207b7SJohn Levon } 2299*1f5207b7SJohn Levon 2300*1f5207b7SJohn Levon static void db_limited_after(void) 2301*1f5207b7SJohn Levon { 2302*1f5207b7SJohn Levon free_stree(&unmatched_stree); 2303*1f5207b7SJohn Levon } 2304*1f5207b7SJohn Levon 2305*1f5207b7SJohn Levon static int rl_fits_in_type(struct range_list *rl, struct symbol *type) 2306*1f5207b7SJohn Levon { 2307*1f5207b7SJohn Levon if (type_bits(rl_type(rl)) <= type_bits(type)) 2308*1f5207b7SJohn Levon return 1; 2309*1f5207b7SJohn Levon if (sval_cmp(rl_max(rl), sval_type_max(type)) > 0) 2310*1f5207b7SJohn Levon return 0; 2311*1f5207b7SJohn Levon if (sval_is_negative(rl_min(rl)) && 2312*1f5207b7SJohn Levon sval_cmp(rl_min(rl), sval_type_min(type)) < 0) 2313*1f5207b7SJohn Levon return 0; 2314*1f5207b7SJohn Levon return 1; 2315*1f5207b7SJohn Levon } 2316*1f5207b7SJohn Levon 2317*1f5207b7SJohn Levon static int basically_the_same(struct range_list *orig, struct range_list *new) 2318*1f5207b7SJohn Levon { 2319*1f5207b7SJohn Levon if (rl_equiv(orig, new)) 2320*1f5207b7SJohn Levon return 1; 2321*1f5207b7SJohn Levon 2322*1f5207b7SJohn Levon /* 2323*1f5207b7SJohn Levon * The whole range is essentially the same as 0,4096-27777777777 so 2324*1f5207b7SJohn Levon * don't overwrite the implications just to store that. 2325*1f5207b7SJohn Levon * 2326*1f5207b7SJohn Levon */ 2327*1f5207b7SJohn Levon if (rl_type(orig)->type == SYM_PTR && 2328*1f5207b7SJohn Levon is_whole_rl(orig) && 2329*1f5207b7SJohn Levon rl_min(new).value == 0 && 2330*1f5207b7SJohn Levon rl_max(new).value == valid_ptr_max) 2331*1f5207b7SJohn Levon return 1; 2332*1f5207b7SJohn Levon return 0; 2333*1f5207b7SJohn Levon } 2334*1f5207b7SJohn Levon 2335*1f5207b7SJohn Levon static void db_param_limit_binops(struct expression *arg, char *key, struct range_list *rl) 2336*1f5207b7SJohn Levon { 2337*1f5207b7SJohn Levon struct range_list *left_rl; 2338*1f5207b7SJohn Levon sval_t zero = { .type = rl_type(rl), }; 2339*1f5207b7SJohn Levon sval_t sval; 2340*1f5207b7SJohn Levon 2341*1f5207b7SJohn Levon if (arg->op != '*') 2342*1f5207b7SJohn Levon return; 2343*1f5207b7SJohn Levon if (!get_implied_value(arg->right, &sval)) 2344*1f5207b7SJohn Levon return; 2345*1f5207b7SJohn Levon if (can_integer_overflow(get_type(arg), arg)) 2346*1f5207b7SJohn Levon return; 2347*1f5207b7SJohn Levon 2348*1f5207b7SJohn Levon left_rl = rl_binop(rl, '/', alloc_rl(sval, sval)); 2349*1f5207b7SJohn Levon if (!rl_has_sval(rl, zero)) 2350*1f5207b7SJohn Levon left_rl = remove_range(left_rl, zero, zero); 2351*1f5207b7SJohn Levon 2352*1f5207b7SJohn Levon set_extra_expr_nomod(arg->left, alloc_estate_rl(left_rl)); 2353*1f5207b7SJohn Levon } 2354*1f5207b7SJohn Levon 2355*1f5207b7SJohn Levon static void db_param_limit_filter(struct expression *expr, int param, char *key, char *value, enum info_type op) 2356*1f5207b7SJohn Levon { 2357*1f5207b7SJohn Levon struct expression *arg; 2358*1f5207b7SJohn Levon char *name; 2359*1f5207b7SJohn Levon struct symbol *sym; 2360*1f5207b7SJohn Levon struct var_sym_list *vsl = NULL; 2361*1f5207b7SJohn Levon struct sm_state *sm; 2362*1f5207b7SJohn Levon struct symbol *compare_type, *var_type; 2363*1f5207b7SJohn Levon struct range_list *rl; 2364*1f5207b7SJohn Levon struct range_list *limit; 2365*1f5207b7SJohn Levon struct range_list *new; 2366*1f5207b7SJohn Levon char *tmp_name; 2367*1f5207b7SJohn Levon struct symbol *tmp_sym; 2368*1f5207b7SJohn Levon 2369*1f5207b7SJohn Levon while (expr->type == EXPR_ASSIGNMENT) 2370*1f5207b7SJohn Levon expr = strip_expr(expr->right); 2371*1f5207b7SJohn Levon if (expr->type != EXPR_CALL) 2372*1f5207b7SJohn Levon return; 2373*1f5207b7SJohn Levon 2374*1f5207b7SJohn Levon arg = get_argument_from_call_expr(expr->args, param); 2375*1f5207b7SJohn Levon if (!arg) 2376*1f5207b7SJohn Levon return; 2377*1f5207b7SJohn Levon 2378*1f5207b7SJohn Levon name = get_chunk_from_key(arg, key, &sym, &vsl); 2379*1f5207b7SJohn Levon if (!name) 2380*1f5207b7SJohn Levon return; 2381*1f5207b7SJohn Levon if (op != PARAM_LIMIT && !sym) 2382*1f5207b7SJohn Levon goto free; 2383*1f5207b7SJohn Levon 2384*1f5207b7SJohn Levon if (strcmp(key, "$") == 0) 2385*1f5207b7SJohn Levon compare_type = get_arg_type(expr->fn, param); 2386*1f5207b7SJohn Levon else 2387*1f5207b7SJohn Levon compare_type = get_member_type_from_key(arg, key); 2388*1f5207b7SJohn Levon 2389*1f5207b7SJohn Levon sm = get_sm_state(SMATCH_EXTRA, name, sym); 2390*1f5207b7SJohn Levon if (sm) 2391*1f5207b7SJohn Levon rl = estate_rl(sm->state); 2392*1f5207b7SJohn Levon else 2393*1f5207b7SJohn Levon rl = alloc_whole_rl(compare_type); 2394*1f5207b7SJohn Levon 2395*1f5207b7SJohn Levon if (op == PARAM_LIMIT && !rl_fits_in_type(rl, compare_type)) 2396*1f5207b7SJohn Levon goto free; 2397*1f5207b7SJohn Levon 2398*1f5207b7SJohn Levon call_results_to_rl(expr, compare_type, value, &limit); 2399*1f5207b7SJohn Levon new = rl_intersection(rl, limit); 2400*1f5207b7SJohn Levon 2401*1f5207b7SJohn Levon var_type = get_member_type_from_key(arg, key); 2402*1f5207b7SJohn Levon new = cast_rl(var_type, new); 2403*1f5207b7SJohn Levon 2404*1f5207b7SJohn Levon /* We want to preserve the implications here */ 2405*1f5207b7SJohn Levon if (sm && basically_the_same(estate_rl(sm->state), new)) 2406*1f5207b7SJohn Levon goto free; 2407*1f5207b7SJohn Levon tmp_name = map_long_to_short_name_sym(name, sym, &tmp_sym); 2408*1f5207b7SJohn Levon if (tmp_name && tmp_sym) { 2409*1f5207b7SJohn Levon free_string(name); 2410*1f5207b7SJohn Levon name = tmp_name; 2411*1f5207b7SJohn Levon sym = tmp_sym; 2412*1f5207b7SJohn Levon } 2413*1f5207b7SJohn Levon 2414*1f5207b7SJohn Levon if (op == PARAM_LIMIT) 2415*1f5207b7SJohn Levon set_extra_nomod_vsl(name, sym, vsl, NULL, alloc_estate_rl(new)); 2416*1f5207b7SJohn Levon else 2417*1f5207b7SJohn Levon set_extra_mod(name, sym, NULL, alloc_estate_rl(new)); 2418*1f5207b7SJohn Levon 2419*1f5207b7SJohn Levon if (op == PARAM_LIMIT && arg->type == EXPR_BINOP) 2420*1f5207b7SJohn Levon db_param_limit_binops(arg, key, new); 2421*1f5207b7SJohn Levon free: 2422*1f5207b7SJohn Levon free_string(name); 2423*1f5207b7SJohn Levon } 2424*1f5207b7SJohn Levon 2425*1f5207b7SJohn Levon static void db_param_limit(struct expression *expr, int param, char *key, char *value) 2426*1f5207b7SJohn Levon { 2427*1f5207b7SJohn Levon db_param_limit_filter(expr, param, key, value, PARAM_LIMIT); 2428*1f5207b7SJohn Levon } 2429*1f5207b7SJohn Levon 2430*1f5207b7SJohn Levon static void db_param_filter(struct expression *expr, int param, char *key, char *value) 2431*1f5207b7SJohn Levon { 2432*1f5207b7SJohn Levon db_param_limit_filter(expr, param, key, value, PARAM_FILTER); 2433*1f5207b7SJohn Levon } 2434*1f5207b7SJohn Levon 2435*1f5207b7SJohn Levon static void db_param_add_set(struct expression *expr, int param, char *key, char *value, enum info_type op) 2436*1f5207b7SJohn Levon { 2437*1f5207b7SJohn Levon struct expression *arg; 2438*1f5207b7SJohn Levon char *name, *tmp_name; 2439*1f5207b7SJohn Levon struct symbol *sym, *tmp_sym; 2440*1f5207b7SJohn Levon struct symbol *param_type, *arg_type; 2441*1f5207b7SJohn Levon struct smatch_state *state; 2442*1f5207b7SJohn Levon struct range_list *new = NULL; 2443*1f5207b7SJohn Levon struct range_list *added = NULL; 2444*1f5207b7SJohn Levon 2445*1f5207b7SJohn Levon while (expr->type == EXPR_ASSIGNMENT) 2446*1f5207b7SJohn Levon expr = strip_expr(expr->right); 2447*1f5207b7SJohn Levon if (expr->type != EXPR_CALL) 2448*1f5207b7SJohn Levon return; 2449*1f5207b7SJohn Levon 2450*1f5207b7SJohn Levon arg = get_argument_from_call_expr(expr->args, param); 2451*1f5207b7SJohn Levon if (!arg) 2452*1f5207b7SJohn Levon return; 2453*1f5207b7SJohn Levon 2454*1f5207b7SJohn Levon arg_type = get_arg_type_from_key(expr->fn, param, arg, key); 2455*1f5207b7SJohn Levon param_type = get_member_type_from_key(arg, key); 2456*1f5207b7SJohn Levon name = get_variable_from_key(arg, key, &sym); 2457*1f5207b7SJohn Levon if (!name || !sym) 2458*1f5207b7SJohn Levon goto free; 2459*1f5207b7SJohn Levon 2460*1f5207b7SJohn Levon state = get_state(SMATCH_EXTRA, name, sym); 2461*1f5207b7SJohn Levon if (state) 2462*1f5207b7SJohn Levon new = estate_rl(state); 2463*1f5207b7SJohn Levon 2464*1f5207b7SJohn Levon call_results_to_rl(expr, arg_type, value, &added); 2465*1f5207b7SJohn Levon added = cast_rl(param_type, added); 2466*1f5207b7SJohn Levon if (op == PARAM_SET) 2467*1f5207b7SJohn Levon new = added; 2468*1f5207b7SJohn Levon else 2469*1f5207b7SJohn Levon new = rl_union(new, added); 2470*1f5207b7SJohn Levon 2471*1f5207b7SJohn Levon tmp_name = map_long_to_short_name_sym_nostack(name, sym, &tmp_sym); 2472*1f5207b7SJohn Levon if (tmp_name && tmp_sym) { 2473*1f5207b7SJohn Levon free_string(name); 2474*1f5207b7SJohn Levon name = tmp_name; 2475*1f5207b7SJohn Levon sym = tmp_sym; 2476*1f5207b7SJohn Levon } 2477*1f5207b7SJohn Levon set_extra_mod(name, sym, NULL, alloc_estate_rl(new)); 2478*1f5207b7SJohn Levon free: 2479*1f5207b7SJohn Levon free_string(name); 2480*1f5207b7SJohn Levon } 2481*1f5207b7SJohn Levon 2482*1f5207b7SJohn Levon static void db_param_add(struct expression *expr, int param, char *key, char *value) 2483*1f5207b7SJohn Levon { 2484*1f5207b7SJohn Levon in_param_set = true; 2485*1f5207b7SJohn Levon db_param_add_set(expr, param, key, value, PARAM_ADD); 2486*1f5207b7SJohn Levon in_param_set = false; 2487*1f5207b7SJohn Levon } 2488*1f5207b7SJohn Levon 2489*1f5207b7SJohn Levon static void db_param_set(struct expression *expr, int param, char *key, char *value) 2490*1f5207b7SJohn Levon { 2491*1f5207b7SJohn Levon in_param_set = true; 2492*1f5207b7SJohn Levon db_param_add_set(expr, param, key, value, PARAM_SET); 2493*1f5207b7SJohn Levon in_param_set = false; 2494*1f5207b7SJohn Levon } 2495*1f5207b7SJohn Levon 2496*1f5207b7SJohn Levon static void db_param_value(struct expression *expr, int param, char *key, char *value) 2497*1f5207b7SJohn Levon { 2498*1f5207b7SJohn Levon struct expression *call; 2499*1f5207b7SJohn Levon char *name; 2500*1f5207b7SJohn Levon struct symbol *sym; 2501*1f5207b7SJohn Levon struct symbol *type; 2502*1f5207b7SJohn Levon struct range_list *rl = NULL; 2503*1f5207b7SJohn Levon 2504*1f5207b7SJohn Levon if (param != -1) 2505*1f5207b7SJohn Levon return; 2506*1f5207b7SJohn Levon 2507*1f5207b7SJohn Levon call = expr; 2508*1f5207b7SJohn Levon while (call->type == EXPR_ASSIGNMENT) 2509*1f5207b7SJohn Levon call = strip_expr(call->right); 2510*1f5207b7SJohn Levon if (call->type != EXPR_CALL) 2511*1f5207b7SJohn Levon return; 2512*1f5207b7SJohn Levon 2513*1f5207b7SJohn Levon type = get_member_type_from_key(expr->left, key); 2514*1f5207b7SJohn Levon name = get_variable_from_key(expr->left, key, &sym); 2515*1f5207b7SJohn Levon if (!name || !sym) 2516*1f5207b7SJohn Levon goto free; 2517*1f5207b7SJohn Levon 2518*1f5207b7SJohn Levon call_results_to_rl(call, type, value, &rl); 2519*1f5207b7SJohn Levon 2520*1f5207b7SJohn Levon set_extra_mod(name, sym, NULL, alloc_estate_rl(rl)); 2521*1f5207b7SJohn Levon free: 2522*1f5207b7SJohn Levon free_string(name); 2523*1f5207b7SJohn Levon } 2524*1f5207b7SJohn Levon 2525*1f5207b7SJohn Levon static void match_call_info(struct expression *expr) 2526*1f5207b7SJohn Levon { 2527*1f5207b7SJohn Levon struct smatch_state *state; 2528*1f5207b7SJohn Levon struct range_list *rl = NULL; 2529*1f5207b7SJohn Levon struct expression *arg; 2530*1f5207b7SJohn Levon struct symbol *type; 2531*1f5207b7SJohn Levon int i = 0; 2532*1f5207b7SJohn Levon 2533*1f5207b7SJohn Levon FOR_EACH_PTR(expr->args, arg) { 2534*1f5207b7SJohn Levon type = get_arg_type(expr->fn, i); 2535*1f5207b7SJohn Levon 2536*1f5207b7SJohn Levon get_absolute_rl(arg, &rl); 2537*1f5207b7SJohn Levon rl = cast_rl(type, rl); 2538*1f5207b7SJohn Levon 2539*1f5207b7SJohn Levon if (!is_whole_rl(rl)) { 2540*1f5207b7SJohn Levon rl = intersect_with_real_abs_expr(arg, rl); 2541*1f5207b7SJohn Levon sql_insert_caller_info(expr, PARAM_VALUE, i, "$", show_rl(rl)); 2542*1f5207b7SJohn Levon } 2543*1f5207b7SJohn Levon state = get_state_expr(SMATCH_EXTRA, arg); 2544*1f5207b7SJohn Levon if (estate_has_fuzzy_max(state)) { 2545*1f5207b7SJohn Levon sql_insert_caller_info(expr, FUZZY_MAX, i, "$", 2546*1f5207b7SJohn Levon sval_to_str(estate_get_fuzzy_max(state))); 2547*1f5207b7SJohn Levon } 2548*1f5207b7SJohn Levon i++; 2549*1f5207b7SJohn Levon } END_FOR_EACH_PTR(arg); 2550*1f5207b7SJohn Levon } 2551*1f5207b7SJohn Levon 2552*1f5207b7SJohn Levon static void set_param_value(const char *name, struct symbol *sym, char *key, char *value) 2553*1f5207b7SJohn Levon { 2554*1f5207b7SJohn Levon struct range_list *rl = NULL; 2555*1f5207b7SJohn Levon struct smatch_state *state; 2556*1f5207b7SJohn Levon struct symbol *type; 2557*1f5207b7SJohn Levon char fullname[256]; 2558*1f5207b7SJohn Levon sval_t dummy; 2559*1f5207b7SJohn Levon 2560*1f5207b7SJohn Levon if (strcmp(key, "*$") == 0) 2561*1f5207b7SJohn Levon snprintf(fullname, sizeof(fullname), "*%s", name); 2562*1f5207b7SJohn Levon else if (strncmp(key, "$", 1) == 0) 2563*1f5207b7SJohn Levon snprintf(fullname, 256, "%s%s", name, key + 1); 2564*1f5207b7SJohn Levon else 2565*1f5207b7SJohn Levon return; 2566*1f5207b7SJohn Levon 2567*1f5207b7SJohn Levon type = get_member_type_from_key(symbol_expression(sym), key); 2568*1f5207b7SJohn Levon str_to_rl(type, value, &rl); 2569*1f5207b7SJohn Levon state = alloc_estate_rl(rl); 2570*1f5207b7SJohn Levon if (estate_get_single_value(state, &dummy)) 2571*1f5207b7SJohn Levon estate_set_hard_max(state); 2572*1f5207b7SJohn Levon set_state(SMATCH_EXTRA, fullname, sym, state); 2573*1f5207b7SJohn Levon } 2574*1f5207b7SJohn Levon 2575*1f5207b7SJohn Levon static void set_param_hard_max(const char *name, struct symbol *sym, char *key, char *value) 2576*1f5207b7SJohn Levon { 2577*1f5207b7SJohn Levon struct range_list *rl = NULL; 2578*1f5207b7SJohn Levon struct smatch_state *state; 2579*1f5207b7SJohn Levon struct symbol *type; 2580*1f5207b7SJohn Levon char fullname[256]; 2581*1f5207b7SJohn Levon sval_t max; 2582*1f5207b7SJohn Levon 2583*1f5207b7SJohn Levon if (strcmp(key, "*$") == 0) 2584*1f5207b7SJohn Levon snprintf(fullname, sizeof(fullname), "*%s", name); 2585*1f5207b7SJohn Levon else if (strncmp(key, "$", 1) == 0) 2586*1f5207b7SJohn Levon snprintf(fullname, 256, "%s%s", name, key + 1); 2587*1f5207b7SJohn Levon else 2588*1f5207b7SJohn Levon return; 2589*1f5207b7SJohn Levon 2590*1f5207b7SJohn Levon state = get_state(SMATCH_EXTRA, fullname, sym); 2591*1f5207b7SJohn Levon if (!state) 2592*1f5207b7SJohn Levon return; 2593*1f5207b7SJohn Levon type = get_member_type_from_key(symbol_expression(sym), key); 2594*1f5207b7SJohn Levon str_to_rl(type, value, &rl); 2595*1f5207b7SJohn Levon if (!rl_to_sval(rl, &max)) 2596*1f5207b7SJohn Levon return; 2597*1f5207b7SJohn Levon estate_set_fuzzy_max(state, max); 2598*1f5207b7SJohn Levon } 2599*1f5207b7SJohn Levon 2600*1f5207b7SJohn Levon struct sm_state *get_extra_sm_state(struct expression *expr) 2601*1f5207b7SJohn Levon { 2602*1f5207b7SJohn Levon char *name; 2603*1f5207b7SJohn Levon struct symbol *sym; 2604*1f5207b7SJohn Levon struct sm_state *ret = NULL; 2605*1f5207b7SJohn Levon 2606*1f5207b7SJohn Levon name = expr_to_known_chunk_sym(expr, &sym); 2607*1f5207b7SJohn Levon if (!name) 2608*1f5207b7SJohn Levon goto free; 2609*1f5207b7SJohn Levon 2610*1f5207b7SJohn Levon ret = get_sm_state(SMATCH_EXTRA, name, sym); 2611*1f5207b7SJohn Levon free: 2612*1f5207b7SJohn Levon free_string(name); 2613*1f5207b7SJohn Levon return ret; 2614*1f5207b7SJohn Levon } 2615*1f5207b7SJohn Levon 2616*1f5207b7SJohn Levon struct smatch_state *get_extra_state(struct expression *expr) 2617*1f5207b7SJohn Levon { 2618*1f5207b7SJohn Levon struct sm_state *sm; 2619*1f5207b7SJohn Levon 2620*1f5207b7SJohn Levon sm = get_extra_sm_state(expr); 2621*1f5207b7SJohn Levon if (!sm) 2622*1f5207b7SJohn Levon return NULL; 2623*1f5207b7SJohn Levon return sm->state; 2624*1f5207b7SJohn Levon } 2625*1f5207b7SJohn Levon 2626*1f5207b7SJohn Levon void register_smatch_extra(int id) 2627*1f5207b7SJohn Levon { 2628*1f5207b7SJohn Levon my_id = id; 2629*1f5207b7SJohn Levon 2630*1f5207b7SJohn Levon add_merge_hook(my_id, &merge_estates); 2631*1f5207b7SJohn Levon add_unmatched_state_hook(my_id, &unmatched_state); 2632*1f5207b7SJohn Levon select_caller_info_hook(set_param_value, PARAM_VALUE); 2633*1f5207b7SJohn Levon select_caller_info_hook(set_param_hard_max, FUZZY_MAX); 2634*1f5207b7SJohn Levon select_return_states_before(&db_limited_before); 2635*1f5207b7SJohn Levon select_return_states_hook(PARAM_LIMIT, &db_param_limit); 2636*1f5207b7SJohn Levon select_return_states_hook(PARAM_FILTER, &db_param_filter); 2637*1f5207b7SJohn Levon select_return_states_hook(PARAM_ADD, &db_param_add); 2638*1f5207b7SJohn Levon select_return_states_hook(PARAM_SET, &db_param_set); 2639*1f5207b7SJohn Levon select_return_states_hook(PARAM_VALUE, &db_param_value); 2640*1f5207b7SJohn Levon select_return_states_after(&db_limited_after); 2641*1f5207b7SJohn Levon } 2642*1f5207b7SJohn Levon 2643*1f5207b7SJohn Levon static void match_link_modify(struct sm_state *sm, struct expression *mod_expr) 2644*1f5207b7SJohn Levon { 2645*1f5207b7SJohn Levon struct var_sym_list *links; 2646*1f5207b7SJohn Levon struct var_sym *tmp; 2647*1f5207b7SJohn Levon struct smatch_state *state; 2648*1f5207b7SJohn Levon 2649*1f5207b7SJohn Levon links = sm->state->data; 2650*1f5207b7SJohn Levon 2651*1f5207b7SJohn Levon FOR_EACH_PTR(links, tmp) { 2652*1f5207b7SJohn Levon if (sm->sym == tmp->sym && 2653*1f5207b7SJohn Levon strcmp(sm->name, tmp->var) == 0) 2654*1f5207b7SJohn Levon continue; 2655*1f5207b7SJohn Levon state = get_state(SMATCH_EXTRA, tmp->var, tmp->sym); 2656*1f5207b7SJohn Levon if (!state) 2657*1f5207b7SJohn Levon continue; 2658*1f5207b7SJohn Levon set_state(SMATCH_EXTRA, tmp->var, tmp->sym, alloc_estate_whole(estate_type(state))); 2659*1f5207b7SJohn Levon } END_FOR_EACH_PTR(tmp); 2660*1f5207b7SJohn Levon set_state(link_id, sm->name, sm->sym, &undefined); 2661*1f5207b7SJohn Levon } 2662*1f5207b7SJohn Levon 2663*1f5207b7SJohn Levon void register_smatch_extra_links(int id) 2664*1f5207b7SJohn Levon { 2665*1f5207b7SJohn Levon link_id = id; 2666*1f5207b7SJohn Levon } 2667*1f5207b7SJohn Levon 2668*1f5207b7SJohn Levon void register_smatch_extra_late(int id) 2669*1f5207b7SJohn Levon { 2670*1f5207b7SJohn Levon add_merge_hook(link_id, &merge_link_states); 2671*1f5207b7SJohn Levon add_modification_hook(link_id, &match_link_modify); 2672*1f5207b7SJohn Levon add_hook(&match_dereferences, DEREF_HOOK); 2673*1f5207b7SJohn Levon add_hook(&match_pointer_as_array, OP_HOOK); 2674*1f5207b7SJohn Levon select_return_implies_hook(DEREFERENCE, &set_param_dereferenced); 2675*1f5207b7SJohn Levon add_hook(&match_function_call, FUNCTION_CALL_HOOK); 2676*1f5207b7SJohn Levon add_hook(&match_assign, ASSIGNMENT_HOOK); 2677*1f5207b7SJohn Levon add_hook(&match_assign, GLOBAL_ASSIGNMENT_HOOK); 2678*1f5207b7SJohn Levon add_hook(&unop_expr, OP_HOOK); 2679*1f5207b7SJohn Levon add_hook(&asm_expr, ASM_HOOK); 2680*1f5207b7SJohn Levon 2681*1f5207b7SJohn Levon add_hook(&match_call_info, FUNCTION_CALL_HOOK); 2682*1f5207b7SJohn Levon add_member_info_callback(my_id, struct_member_callback); 2683*1f5207b7SJohn Levon add_split_return_callback(&returned_struct_members); 2684*1f5207b7SJohn Levon 2685*1f5207b7SJohn Levon // add_hook(&assume_indexes_are_valid, OP_HOOK); 2686*1f5207b7SJohn Levon } 2687