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 pools_overlap(struct state_list_stack *pools1,
  60                         struct state_list_stack *pools2)
  61 {
  62         struct state_list *one;
  63         struct state_list *two;
  64
  65         PREPARE_PTR_LIST(pools1, one);
  66         PREPARE_PTR_LIST(pools2, two);
  67         for (;;) {
  68                 if (!one || !two)
  69                         return 0;
  70
  71                 if (one < two) {
  72                         NEXT_PTR_LIST(one);
  73                 } else if (one == two) {
  74                         return 1;
  75                 } else {
  76                         NEXT_PTR_LIST(two);
  77                 }
  78         }
  79         FINISH_PTR_LIST(two);
  80         FINISH_PTR_LIST(one);
  81         return 0;
  82 }
  83
  84 struct sm_state *remove_my_pools(struct sm_state *sm,
  85                                 struct state_list_stack *pools, int *modified)
  86 {
  87         struct sm_state *ret = NULL;
  88         struct sm_state *pre;
  89         struct sm_state *tmp_keep;
  90         struct state_list *keep = NULL;
  91
  92         if (pools_overlap(sm->my_pools, pools)) {
  93                 DIMPLIED("removed %s = %s from %d\n", sm->name,
  94                         show_state(sm->state), sm->line);
  95                 *modified = 1;
  96                 return NULL;
  97         }
  98
  99         if (is_merged(sm)) {
 100                 int removed = 0;
 101
 102                 DIMPLIED("checking %s = %s from %d\n", sm->name,
 103                         show_state(sm->state), sm->line);
 104                 FOR_EACH_PTR(sm->pre_merge, pre) {
 105                         tmp_keep = remove_my_pools(pre, pools, &removed);
 106                         if (tmp_keep)
 107                                 add_ptr_list(&keep, tmp_keep);
 108                 } END_FOR_EACH_PTR(pre);
 109                 if (!removed) {
 110                         DIMPLIED("kept %s = %s from %d\n", sm->name, show_state(sm->state), sm->line);
 111                         return sm;
 112                 }
 113                 *modified = 1;
 114                 if (!keep) {
 115                         DIMPLIED("removed %s = %s from %d\n", sm->name, show_state(sm->state), sm->line);
 116                         return NULL;
 117                 }
 118
 119                 FOR_EACH_PTR(keep, tmp_keep) {
 120                         if (!ret)
 121                                 ret = tmp_keep;
 122                         else
 123                                 ret = merge_sm_states(ret, tmp_keep);
 124                 } END_FOR_EACH_PTR(tmp_keep);
 125                 merge_pools(&ret->my_pools, sm->my_pools);
 126                 DIMPLIED("partial %s = %s from %d\n", sm->name, show_state(sm->state), sm->line);
 127                 return ret;
 128         }
 129         DIMPLIED("kept %s = %s from %d\n", sm->name, show_state(sm->state),
 130                 sm->line);
 131         return sm;
 132 }
 133
 134 static struct state_list *filter_stack(struct state_list *pre_list,
 135                                 struct state_list_stack *stack)
 136 {
 137         struct state_list *ret = NULL;
 138         struct sm_state *tmp;
 139         struct sm_state *filtered_state;
 140         int modified = 0;
 141
 142         if (!stack)
 143                 return NULL;
 144
 145         FOR_EACH_PTR(pre_list, tmp) {
 146                 filtered_state = remove_my_pools(tmp, stack, &modified);
 147                 if (filtered_state && modified)
 148                         add_ptr_list(&ret, filtered_state);
 149         } END_FOR_EACH_PTR(tmp);
 150         return ret;
 151 }
 152
 153 static int is_checked(struct state_list *checked, struct sm_state *sm)
 154 {
 155         struct sm_state *tmp;
 156
 157         FOR_EACH_PTR(checked, tmp) {
 158                 if (tmp == sm)
 159                         return 1;
 160         } END_FOR_EACH_PTR(tmp);
 161         return 0;
 162 }
 163
 164 static void separate_pools(struct sm_state *sm_state, int comparison, int num,
 165                         int left,
 166                         struct state_list_stack **true_stack,
 167                         struct state_list_stack **false_stack,
 168                         struct state_list **checked)
 169 {
 170         struct state_list *list;
 171         struct sm_state *s;
 172         int istrue, isfalse;
 173         int free_checked = 0;
 174         struct state_list *checked_states = NULL;
 175         static int stopper;
 176
 177         if (checked == NULL) {
 178                 stopper = 0;
 179                 checked = &checked_states;
 180                 free_checked = 1;
 181         }
 182         if (is_checked(*checked, sm_state)) {
 183                 return;
 184         }
 185         add_ptr_list(checked, sm_state);
 186
 187         if (stopper++ >= 500) {
 188                 smatch_msg("internal error:  too much recursion going on here");
 189                 return;
 190         }
 191
 192         FOR_EACH_PTR(sm_state->my_pools, list) {
 193                 s = get_sm_state_slist(list, sm_state->name, sm_state->owner,
 194                                     sm_state->sym);
 195                 istrue = !possibly_false(comparison,
 196                                         (struct data_info *)s->state->data, num,
 197                                         left);
 198                 isfalse = !possibly_true(comparison,
 199                                         (struct data_info *)s->state->data,
 200                                         num, left);
 201
 202                 if (debug_implied_states || debug_states) {
 203                         if (istrue && isfalse) {
 204                                 printf("'%s = %s' from %d does not exist. %p\n",
 205                                         s->name, show_state(s->state),
 206                                         s->line, list);
 207                         } else if (istrue) {
 208                                 printf("'%s = %s' from %d is true. %p\n",
 209                                         s->name, show_state(s->state),
 210                                         s->line, list);
 211                         } else if (isfalse) {
 212                                 printf("'%s = %s' from %d is false. %p\n",
 213                                         s->name, show_state(s->state),
 214                                         s->line, list);
 215                         } else {
 216                                 printf("'%s = %s' from %d could be true or "
 217                                         "false. %p\n", s->name,
 218                                         show_state(s->state), s->line, list);
 219                         }
 220                 }
 221                 if (istrue) {
 222                         add_pool(true_stack, list);
 223                 }
 224                 if (isfalse) {
 225                         add_pool(false_stack, list);
 226                 }
 227         } END_FOR_EACH_PTR(list);
 228         FOR_EACH_PTR(sm_state->pre_merge, s) {
 229                 separate_pools(s, comparison, num, left, true_stack, false_stack, checked);
 230         } END_FOR_EACH_PTR(s);
 231         if (free_checked)
 232                 free_slist(checked);
 233 }
 234
 235 static void get_eq_neq(struct sm_state *sm_state, int comparison, int num,
 236                 int left,
 237                 struct state_list *pre_list,
 238                 struct state_list **true_states,
 239                 struct state_list **false_states)
 240 {
 241         struct state_list_stack *true_stack = NULL;
 242         struct state_list_stack *false_stack = NULL;
 243
 244         if (debug_implied_states || debug_states) {
 245                 if (left)
 246                         smatch_msg("checking implications: (%s %s %d)",
 247                                 sm_state->name, show_special(comparison), num);
 248                 else
 249                         smatch_msg("checking implications: (%d %s %s)",
 250                                 num, show_special(comparison), sm_state->name);
 251         }
 252
 253         separate_pools(sm_state, comparison, num, left, &true_stack, &false_stack, NULL);
 254
 255         DIMPLIED("filtering true stack.\n");
 256         *true_states = filter_stack(pre_list, false_stack);
 257         DIMPLIED("filtering false stack.\n");
 258         *false_states = filter_stack(pre_list, true_stack);
 259         free_stack(&true_stack);
 260         free_stack(&false_stack);
 261         if (debug_implied_states || debug_states) {
 262                 printf("These are the implied states for the true path:\n");
 263                 __print_slist(*true_states);
 264                 printf("These are the implied states for the false path:\n");
 265                 __print_slist(*false_states);
 266         }
 267 }
 268
 269 static char *get_implication_variable(struct expression *expr, struct symbol **symp)
 270 {
 271         expr = strip_expr(expr);
 272         if (expr->type == EXPR_ASSIGNMENT)
 273                 return get_implication_variable(expr->left, symp);
 274         return get_variable_from_expr(expr, symp);
 275 }
 276
 277 static void handle_comparison(struct expression *expr,
 278                               struct state_list **implied_true,
 279                               struct state_list **implied_false)
 280 {
 281         struct symbol *sym;
 282         char *name;
 283         struct sm_state *state;
 284         int value;
 285         int left = 0;
 286
 287         value = get_value(expr->left);
 288         if (value == UNDEFINED) {
 289                 value = get_value(expr->right);
 290                 if (value == UNDEFINED)
 291                         return;
 292                 left = 1;
 293         }
 294         if (left)
 295                 name = get_implication_variable(expr->left, &sym);
 296         else
 297                 name = get_implication_variable(expr->right, &sym);
 298         if (!name || !sym)
 299                 goto free;
 300         state = get_sm_state(name, SMATCH_EXTRA, sym);
 301         if (!state)
 302                 goto free;
 303         if (!is_merged(state)) {
 304                 DIMPLIED("%d '%s' is not merged.\n", get_lineno(), state->name);
 305                 goto free;
 306         }
 307         get_eq_neq(state, expr->op, value, left, __get_cur_slist(), implied_true, implied_false);
 308         delete_state_slist(implied_true, name, SMATCH_EXTRA, sym);
 309         delete_state_slist(implied_false, name, SMATCH_EXTRA, sym);
 310 free:
 311         free_string(name);
 312 }
 313
 314 static void get_tf_states(struct expression *expr,
 315                           struct state_list **implied_true,
 316                           struct state_list **implied_false)
 317 {
 318         struct symbol *sym;
 319         char *name;
 320         struct sm_state *state;
 321
 322         if (expr->type == EXPR_COMPARE) {
 323                 handle_comparison(expr, implied_true, implied_false);
 324                 return;
 325         }
 326         if (expr->type == EXPR_ASSIGNMENT) {
 327                 /* most of the time ->my_pools will be empty here because we
 328                    just set the state, but if have assigned a conditional
 329                    function there are implications. */
 330                 expr = expr->left;
 331         }
 332
 333         name = get_variable_from_expr(expr, &sym);
 334         if (!name || !sym)
 335                 goto free;
 336         state = get_sm_state(name, SMATCH_EXTRA, sym);
 337         if (!state)
 338                 goto free;
 339         if (!is_merged(state)) {
 340                 DIMPLIED("%d '%s' has no pools.\n", get_lineno(), state->name);
 341                 goto free;
 342         }
 343         get_eq_neq(state, SPECIAL_NOTEQUAL, 0, 1, __get_cur_slist(), implied_true, implied_false);
 344         delete_state_slist(implied_true, name, SMATCH_EXTRA, sym);
 345         delete_state_slist(implied_false, name, SMATCH_EXTRA, sym);
 346 free:
 347         free_string(name);
 348 }
 349
 350 static void implied_states_hook(struct expression *expr)
 351 {
 352         struct sm_state *state;
 353         struct sm_state *clone;
 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                 clone = clone_state(state);
 364                 __set_true_false_sm(clone, NULL);
 365         } END_FOR_EACH_PTR(state);
 366         free_slist(&implied_true);
 367
 368         FOR_EACH_PTR(implied_false, state) {
 369                 clone = clone_state(state);
 370                 __set_true_false_sm(NULL, clone);
 371         } END_FOR_EACH_PTR(state);
 372         free_slist(&implied_false);
 373 }
 374
 375 void get_implications(char *name, struct symbol *sym, int comparison, int num,
 376                       struct state_list **true_states,
 377                       struct state_list **false_states)
 378 {
 379         struct sm_state *sm;
 380
 381         sm = get_sm_state(name, SMATCH_EXTRA, sym);
 382         if (!sm)
 383                 return;
 384         if (slist_has_state(sm->possible, &undefined))
 385                 return;
 386         get_eq_neq(sm, comparison, num, 1, __get_cur_slist(), true_states, false_states);
 387 }
 388
 389 struct state_list *__implied_case_slist(struct expression *switch_expr,
 390                                         struct expression *case_expr,
 391                                         struct state_list **raw_slist)
 392 {
 393         char *name = NULL;
 394         struct symbol *sym;
 395         struct sm_state *sm;
 396         struct sm_state *true_sm;
 397         struct sm_state *false_sm;
 398         struct state_list *true_states = NULL;
 399         struct state_list *false_states = NULL;
 400         struct state_list *true_clone;
 401         struct state_list *false_clone;
 402         struct state_list *ret = clone_slist(*raw_slist);
 403         long long val;
 404
 405         if (!case_expr)
 406                 return ret;
 407         name = get_variable_from_expr(switch_expr, &sym);
 408         if (!name || !sym)
 409                 goto free;
 410         sm = get_sm_state_slist(*raw_slist, name, SMATCH_EXTRA, sym);
 411         val = get_value(case_expr);
 412         if (val == UNDEFINED)
 413                 goto free;
 414         if (sm) {
 415                 get_eq_neq(sm, SPECIAL_EQUAL, val, 1, *raw_slist, &true_states, &false_states);
 416         }
 417
 418         true_sm = get_sm_state_slist(true_states, name, SMATCH_EXTRA, sym);
 419         if (!true_sm)
 420                 set_state_slist(&true_states, name, SMATCH_EXTRA, sym, alloc_extra_state(val));
 421         false_sm = get_sm_state_slist(false_states, name, SMATCH_EXTRA, sym);
 422         if (!false_sm)
 423                 set_state_slist(&false_states, name, SMATCH_EXTRA, sym, add_filter(sm?sm->state:NULL, val));
 424         true_clone = clone_slist_and_states(true_states);
 425         false_clone = clone_slist_and_states(false_states);
 426         overwrite_slist(false_clone, raw_slist);
 427         overwrite_slist(true_clone, &ret);
 428         free_slist(&true_clone);
 429         free_slist(&false_clone);
 430         free_slist(&true_states);
 431         free_slist(&false_states);
 432 free:
 433         free_string(name);
 434         return ret;
 435 }
 436
 437 void __extra_match_condition(struct expression *expr);
 438 void register_implications(int id)
 439 {
 440         add_hook(&implied_states_hook, CONDITION_HOOK);
 441         add_hook(&__extra_match_condition, CONDITION_HOOK);
 442 }