smatch_implied.c

   1 /*
   2  * sparse/smatch_implied.c
   3  *
   4  * Copyright (C) 2008 Dan Carpenter.
   5  *
   6  * Licensed under the Open Software License version 1.1
   7  *
   8  */
   9
  10 /*
  11  * Imagine we have this code:
  12  * foo = 1;
  13  * if (bar)
  14  *         foo = 99;
  15  * else
  16  *         frob();
  17  *                   //  <-- point #1
  18  * if (foo == 99)    //  <-- point #2
  19  *         bar->baz; //  <-- point #3
  20  *
  21  *
  22  * At point #3 bar is non null and can be dereferenced.
  23  *
  24  * It's smatch_implied.c which sets bar to non null at point #2.
  25  *
  26  * At point #1 merge_slist() stores the list of states from both
  27  * the true and false paths.  On the true path foo == 99 and on
  28  * the false path foo == 1.  merge_slist() sets their my_pools
  29  * list to show the other states which were there when foo == 99.
  30  *
  31  * When it comes to the if (foo == 99) the smatch implied hook
  32  * looks for all the pools where foo was not 99.  It makes a list
  33  * of those.
  34  *
  35  * Then for bar (and all the other states) it says, ok bar is a
  36  * merged state that came from these previous states.  We'll
  37  * chop out all the states where it came from a pool where
  38  * foo != 99 and merge it all back together.
  39  *
  40  * That is the implied state of bar.
  41  *
  42  * merge_slist() sets up ->my_pools.
  43  * merge_sm_state() sets ->pre_merge.
  44  * If an sm_state is not the same on both sides of a merge, it
  45  *    gets a ->my_pool set for both sides.  The result is a merged
  46  *    state that has it's ->pre_merge pointers set.  Merged states
  47  *    do not immediately have any my_pools set, but maybe will later
  48  *    when they themselves are merged.
  49  * A pool is a list of all the states that were set at the time.
  50  */
  51
  52 #include "smatch.h"
  53 #include "smatch_slist.h"
  54 #include "smatch_extra.h"
  55
  56 int debug_implied_states = 0;
  57 int option_no_implied = 0;
  58
  59 static int pool_in_pools(struct state_list *pool,
  60                         struct state_list_stack *pools)
  61 {
  62         struct state_list *tmp;
  63
  64         FOR_EACH_PTR(pools, tmp) {
  65                 if (tmp == pool)
  66                         return 1;
  67                 if (tmp > pool)
  68                         return 0;
  69         } END_FOR_EACH_PTR(tmp);
  70         return 0;
  71 }
  72
  73 struct sm_state *remove_my_pools(struct sm_state *sm,
  74                                 struct state_list_stack *pools, int *modified)
  75 {
  76         struct sm_state *ret = NULL;
  77         struct sm_state *left;
  78         struct sm_state *right;
  79         int removed = 0;
  80
  81         if (!sm)
  82                 return NULL;
  83
  84         if (pool_in_pools(sm->my_pool, pools)) {
  85                 DIMPLIED("removed %s = %s from %d\n", sm->name,
  86                         show_state(sm->state), sm->line);
  87                 *modified = 1;
  88                 return NULL;
  89         }
  90
  91         if (!is_merged(sm)) {
  92                 DIMPLIED("kept %s = %s from %d\n", sm->name, show_state(sm->state),
  93                         sm->line);
  94                 return sm;
  95         }
  96
  97         DIMPLIED("checking %s = %s from %d\n", sm->name, show_state(sm->state), sm->line);
  98         left = remove_my_pools(sm->pre_left, pools, &removed);
  99         right = remove_my_pools(sm->pre_right, pools, &removed);
 100         if (!removed) {
 101                 DIMPLIED("kept %s = %s from %d\n", sm->name, show_state(sm->state), sm->line);
 102                 return sm;
 103         }
 104         *modified = 1;
 105         if (!left && !right) {
 106                 DIMPLIED("removed %s = %s from %d\n", sm->name, show_state(sm->state), sm->line);
 107                 return NULL;
 108         }
 109
 110         if (!left) {
 111                 ret = clone_state(right);
 112                 ret->merged = 1;
 113                 ret->pre_right = right;
 114                 ret->pre_left = NULL;
 115                 ret->my_pool = sm->my_pool;
 116         } else if (!right) {
 117                 ret = clone_state(left);
 118                 ret->merged = 1;
 119                 ret->pre_left = left;
 120                 ret->pre_right = NULL;
 121                 ret->my_pool = sm->my_pool;
 122         } else {
 123                 ret = merge_sm_states(left, right);
 124                 ret->my_pool = sm->my_pool;
 125         }
 126         DIMPLIED("partial %s = %s from %d\n", sm->name, show_state(sm->state), sm->line);
 127         return ret;
 128 }
 129
 130 static struct state_list *filter_stack(struct state_list *pre_list,
 131                                 struct state_list_stack *stack)
 132 {
 133         struct state_list *ret = NULL;
 134         struct sm_state *tmp;
 135         struct sm_state *filtered_state;
 136         int modified;
 137
 138         if (!stack)
 139                 return NULL;
 140
 141         FOR_EACH_PTR(pre_list, tmp) {
 142                 modified = 0;
 143                 if (out_of_memory())
 144                         return NULL;
 145                 filtered_state = remove_my_pools(tmp, stack, &modified);
 146                 if (filtered_state && modified)
 147                         add_ptr_list(&ret, filtered_state);
 148         } END_FOR_EACH_PTR(tmp);
 149         return ret;
 150 }
 151
 152 static int is_checked(struct state_list *checked, struct sm_state *sm)
 153 {
 154         struct sm_state *tmp;
 155
 156         FOR_EACH_PTR(checked, tmp) {
 157                 if (tmp == sm)
 158                         return 1;
 159         } END_FOR_EACH_PTR(tmp);
 160         return 0;
 161 }
 162
 163 static void separate_pools(struct sm_state *sm_state, int comparison, int num,
 164                         int left,
 165                         struct state_list_stack **true_stack,
 166                         struct state_list_stack **false_stack,
 167                         struct state_list **checked)
 168 {
 169         struct sm_state *s;
 170         int istrue, isfalse;
 171         int free_checked = 0;
 172         struct state_list *checked_states = NULL;
 173         static int stopper;
 174
 175         if (!sm_state)
 176                 return;
 177
 178         if (checked == NULL) {
 179                 stopper = 0;
 180                 checked = &checked_states;
 181                 free_checked = 1;
 182         }
 183         if (is_checked(*checked, sm_state)) {
 184                 return;
 185         }
 186         add_ptr_list(checked, sm_state);
 187
 188         if (stopper++ >= 500) {
 189                 smatch_msg("internal error:  too much recursion going on here");
 190                 return;
 191         }
 192
 193         if (sm_state->my_pool) {
 194                 s = get_sm_state_slist(sm_state->my_pool, sm_state->name, sm_state->owner,
 195                                 sm_state->sym);
 196
 197                 istrue = !possibly_false(comparison,
 198                                         (struct data_info *)s->state->data, num,
 199                                         left);
 200                 isfalse = !possibly_true(comparison,
 201                                         (struct data_info *)s->state->data,
 202                                         num, left);
 203
 204                 if (debug_implied_states || debug_states) {
 205                         if (istrue && isfalse) {
 206                                 printf("'%s = %s' from %d does not exist.\n",
 207                                         s->name, show_state(s->state),
 208                                         s->line);
 209                         } else if (istrue) {
 210                                 printf("'%s = %s' from %d is true.\n",
 211                                         s->name, show_state(s->state),
 212                                         s->line);
 213                         } else if (isfalse) {
 214                                 printf("'%s = %s' from %d is false.\n",
 215                                         s->name, show_state(s->state),
 216                                         s->line);
 217                         } else {
 218                                 printf("'%s = %s' from %d could be true or "
 219                                         "false.\n", s->name,
 220                                         show_state(s->state), s->line);
 221                         }
 222                 }
 223                 if (istrue) {
 224                         add_pool(true_stack, s->my_pool);
 225                 }
 226                 if (isfalse) {
 227                         add_pool(false_stack, s->my_pool);
 228                 }
 229         }
 230         separate_pools(sm_state->pre_left, comparison, num, left, true_stack, false_stack, checked);
 231         separate_pools(sm_state->pre_right, comparison, num, left, true_stack, false_stack, checked);
 232         if (free_checked)
 233                 free_slist(checked);
 234 }
 235
 236 static void get_eq_neq(struct sm_state *sm_state, int comparison, int num,
 237                 int left,
 238                 struct state_list *pre_list,
 239                 struct state_list **true_states,
 240                 struct state_list **false_states)
 241 {
 242         struct state_list_stack *true_stack = NULL;
 243         struct state_list_stack *false_stack = NULL;
 244
 245         if (debug_implied_states || debug_states) {
 246                 if (left)
 247                         smatch_msg("checking implications: (%s %s %d)",
 248                                 sm_state->name, show_special(comparison), num);
 249                 else
 250                         smatch_msg("checking implications: (%d %s %s)",
 251                                 num, show_special(comparison), sm_state->name);
 252         }
 253
 254         separate_pools(sm_state, comparison, num, left, &true_stack, &false_stack, NULL);
 255
 256         DIMPLIED("filtering true stack.\n");
 257         *true_states = filter_stack(pre_list, false_stack);
 258         DIMPLIED("filtering false stack.\n");
 259         *false_states = filter_stack(pre_list, true_stack);
 260         free_stack(&true_stack);
 261         free_stack(&false_stack);
 262         if (debug_implied_states || debug_states) {
 263                 printf("These are the implied states for the true path:\n");
 264                 __print_slist(*true_states);
 265                 printf("These are the implied states for the false path:\n");
 266                 __print_slist(*false_states);
 267         }
 268 }
 269
 270 static char *get_implication_variable(struct expression *expr, struct symbol **symp)
 271 {
 272         expr = strip_expr(expr);
 273         if (expr->type == EXPR_ASSIGNMENT)
 274                 return get_implication_variable(expr->left, symp);
 275         return get_variable_from_expr(expr, symp);
 276 }
 277
 278 static void handle_comparison(struct expression *expr,
 279                               struct state_list **implied_true,
 280                               struct state_list **implied_false)
 281 {
 282         struct symbol *sym;
 283         char *name;
 284         struct sm_state *state;
 285         int value;
 286         int left = 0;
 287
 288         value = get_value(expr->left);
 289         if (value == UNDEFINED) {
 290                 value = get_value(expr->right);
 291                 if (value == UNDEFINED)
 292                         return;
 293                 left = 1;
 294         }
 295         if (left)
 296                 name = get_implication_variable(expr->left, &sym);
 297         else
 298                 name = get_implication_variable(expr->right, &sym);
 299         if (!name || !sym)
 300                 goto free;
 301         state = get_sm_state(name, SMATCH_EXTRA, sym);
 302         if (!state)
 303                 goto free;
 304         if (!is_merged(state)) {
 305                 DIMPLIED("%d '%s' is not merged.\n", get_lineno(), state->name);
 306                 goto free;
 307         }
 308         get_eq_neq(state, expr->op, value, left, __get_cur_slist(), implied_true, implied_false);
 309         delete_state_slist(implied_true, name, SMATCH_EXTRA, sym);
 310         delete_state_slist(implied_false, name, SMATCH_EXTRA, sym);
 311 free:
 312         free_string(name);
 313 }
 314
 315 static void get_tf_states(struct expression *expr,
 316                           struct state_list **implied_true,
 317                           struct state_list **implied_false)
 318 {
 319         struct symbol *sym;
 320         char *name;
 321         struct sm_state *state;
 322
 323         if (expr->type == EXPR_COMPARE) {
 324                 handle_comparison(expr, implied_true, implied_false);
 325                 return;
 326         }
 327         if (expr->type == EXPR_ASSIGNMENT) {
 328                 /* most of the time ->my_pools will be empty here because we
 329                    just set the state, but if have assigned a conditional
 330                    function there are implications. */
 331                 expr = expr->left;
 332         }
 333
 334         name = get_variable_from_expr(expr, &sym);
 335         if (!name || !sym)
 336                 goto free;
 337         state = get_sm_state(name, SMATCH_EXTRA, sym);
 338         if (!state)
 339                 goto free;
 340         if (!is_merged(state)) {
 341                 DIMPLIED("%d '%s' has no pools.\n", get_lineno(), state->name);
 342                 goto free;
 343         }
 344         get_eq_neq(state, SPECIAL_NOTEQUAL, 0, 1, __get_cur_slist(), implied_true, implied_false);
 345         delete_state_slist(implied_true, name, SMATCH_EXTRA, sym);
 346         delete_state_slist(implied_false, name, SMATCH_EXTRA, sym);
 347 free:
 348         free_string(name);
 349 }
 350
 351 static void implied_states_hook(struct expression *expr)
 352 {
 353         struct sm_state *state;
 354         struct state_list *implied_true = NULL;
 355         struct state_list *implied_false = NULL;
 356
 357         if (option_no_implied)
 358                 return;
 359
 360         get_tf_states(expr, &implied_true, &implied_false);
 361
 362         FOR_EACH_PTR(implied_true, state) {
 363                 __set_true_false_sm(state, NULL);
 364         } END_FOR_EACH_PTR(state);
 365         free_slist(&implied_true);
 366
 367         FOR_EACH_PTR(implied_false, state) {
 368                 __set_true_false_sm(NULL, state);
 369         } END_FOR_EACH_PTR(state);
 370         free_slist(&implied_false);
 371 }
 372
 373 void get_implications(char *name, struct symbol *sym, int comparison, int num,
 374                       struct state_list **true_states,
 375                       struct state_list **false_states)
 376 {
 377         struct sm_state *sm;
 378
 379         sm = get_sm_state(name, SMATCH_EXTRA, sym);
 380         if (!sm)
 381                 return;
 382         if (slist_has_state(sm->possible, &undefined))
 383                 return;
 384         get_eq_neq(sm, comparison, num, 1, __get_cur_slist(), true_states, false_states);
 385 }
 386
 387 struct state_list *__implied_case_slist(struct expression *switch_expr,
 388                                         struct expression *case_expr,
 389                                         struct state_list **raw_slist)
 390 {
 391         char *name = NULL;
 392         struct symbol *sym;
 393         struct sm_state *sm;
 394         struct sm_state *true_sm;
 395         struct sm_state *false_sm;
 396         struct state_list *true_states = NULL;
 397         struct state_list *false_states = NULL;
 398         struct state_list *ret = clone_slist(*raw_slist);
 399         long long val;
 400
 401         if (!case_expr)
 402                 return ret;
 403         name = get_variable_from_expr(switch_expr, &sym);
 404         if (!name || !sym)
 405                 goto free;
 406         sm = get_sm_state_slist(*raw_slist, name, SMATCH_EXTRA, sym);
 407         val = get_value(case_expr);
 408         if (val == UNDEFINED)
 409                 goto free;
 410         if (sm) {
 411                 get_eq_neq(sm, SPECIAL_EQUAL, val, 1, *raw_slist, &true_states, &false_states);
 412         }
 413
 414         true_sm = get_sm_state_slist(true_states, name, SMATCH_EXTRA, sym);
 415         if (!true_sm)
 416                 set_state_slist(&true_states, name, SMATCH_EXTRA, sym, alloc_extra_state(val));
 417         false_sm = get_sm_state_slist(false_states, name, SMATCH_EXTRA, sym);
 418         if (!false_sm)
 419                 set_state_slist(&false_states, name, SMATCH_EXTRA, sym, add_filter(sm?sm->state:NULL, val));
 420         overwrite_slist(false_states, raw_slist);
 421         overwrite_slist(true_states, &ret);
 422         free_slist(&true_states);
 423         free_slist(&false_states);
 424 free:
 425         free_string(name);
 426         return ret;
 427 }
 428
 429 void __extra_match_condition(struct expression *expr);
 430 void register_implications(int id)
 431 {
 432         add_hook(&implied_states_hook, CONDITION_HOOK);
 433         add_hook(&__extra_match_condition, CONDITION_HOOK);
 434 }