2 * Copyright (C) 2008 Dan Carpenter.
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License
6 * as published by the Free Software Foundation; either version 2
7 * of the License, or (at your option) any later version.
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
19 * Imagine we have this code:
26 * if (foo == 99) // <-- point #2
27 * bar->baz; // <-- point #3
30 * At point #3 bar is non null and can be dereferenced.
32 * It's smatch_implied.c which sets bar to non null at point #2.
34 * At point #1 merge_slist() stores the list of states from both
35 * the true and false paths. On the true path foo == 99 and on
36 * the false path foo == 1. merge_slist() sets their pool
37 * list to show the other states which were there when foo == 99.
39 * When it comes to the if (foo == 99) the smatch implied hook
40 * looks for all the pools where foo was not 99. It makes a list
43 * Then for bar (and all the other states) it says, ok bar is a
44 * merged state that came from these previous states. We'll
45 * chop out all the states where it came from a pool where
46 * foo != 99 and merge it all back together.
48 * That is the implied state of bar.
50 * merge_slist() sets up ->pool. An sm_state only has one ->pool and
51 * that is the pool where it was first set. The my pool gets set when
52 * code paths merge. States that have been set since the last merge do
54 * merge_sm_state() sets ->left and ->right. (These are the states which were
55 * merged to form the current state.)
56 * a pool: a pool is an slist that has been merged with another slist.
62 #include "smatch_slist.h"
63 #include "smatch_extra.h"
65 char *implied_debug_msg
;
66 #define DIMPLIED(msg...) do { if (option_debug_implied) printf(msg); } while (0)
68 int option_debug_implied
= 0;
75 * It messes things up to free range list allocations. This helper fuction
76 * lets us reuse memory instead of doing new allocations.
78 static struct range_list
*tmp_range_list(long long num
)
80 static struct range_list
*my_list
= NULL
;
81 static struct data_range
*my_range
;
83 __free_ptr_list((struct ptr_list
**)&my_list
);
84 my_range
= alloc_range(ll_to_sval(num
), ll_to_sval(num
));
85 add_ptr_list(&my_list
, my_range
);
89 static void print_debug_tf(struct sm_state
*sm
, int istrue
, int isfalse
)
91 if (!option_debug_implied
&& !option_debug
)
94 if (istrue
&& isfalse
) {
95 printf("'%s = %s' from %d does not exist.\n", sm
->name
,
96 show_state(sm
->state
), sm
->line
);
98 printf("'%s = %s' from %d is true. [stree %d]\n", sm
->name
, show_state(sm
->state
),
99 sm
->line
, get_stree_id(sm
->pool
));
100 } else if (isfalse
) {
101 printf("'%s = %s' from %d is false. [stree %d]\n", sm
->name
, show_state(sm
->state
),
102 sm
->line
, get_stree_id(sm
->pool
));
104 printf("'%s = %s' from %d could be true or false. [stree %d]\n", sm
->name
,
105 show_state(sm
->state
), sm
->line
, get_stree_id(sm
->pool
));
110 * add_pool() adds a slist to *pools. If the slist has already been
111 * added earlier then it doesn't get added a second time.
113 void add_pool(struct stree_stack
**pools
, struct stree
*new)
117 FOR_EACH_PTR(*pools
, tmp
) {
120 else if (tmp
== new) {
123 INSERT_CURRENT(new, tmp
);
126 } END_FOR_EACH_PTR(tmp
);
127 add_ptr_list(pools
, new);
131 * If 'foo' == 99 add it that pool to the true pools. If it's false, add it to
132 * the false pools. If we're not sure, then we don't add it to either.
134 static void do_compare(struct sm_state
*sm
, int comparison
, struct range_list
*rl
,
136 struct stree_stack
**true_stack
,
137 struct stree_stack
**false_stack
)
143 struct range_list
*var_rl
;
148 if (is_implied(sm
)) {
149 s
= get_sm_state_stree(sm
->pool
,
157 if (option_debug_implied
|| option_debug
)
158 sm_msg("%s from %d, has borrowed implications.",
163 type
= estate_type(sm
->state
);
164 if (type_positive_bits(rl_type(rl
)) > type_positive_bits(type
))
166 if (type_positive_bits(type
) < 31)
168 var_rl
= cast_rl(type
, estate_rl(s
->state
));
169 rl
= cast_rl(type
, rl
);
171 if (left_right
== LEFT
) {
172 istrue
= !possibly_false_rl(var_rl
, comparison
, rl
);
173 isfalse
= !possibly_true_rl(var_rl
, comparison
, rl
);
175 istrue
= !possibly_false_rl(rl
, comparison
, var_rl
);
176 isfalse
= !possibly_true_rl(rl
, comparison
, var_rl
);
179 print_debug_tf(s
, istrue
, isfalse
);
182 add_pool(true_stack
, s
->pool
);
185 add_pool(false_stack
, s
->pool
);
188 static int pool_in_pools(struct stree
*pool
,
189 const struct stree_stack
*pools
)
193 FOR_EACH_PTR(pools
, tmp
) {
198 } END_FOR_EACH_PTR(tmp
);
202 static int is_checked(struct state_list
*checked
, struct sm_state
*sm
)
204 struct sm_state
*tmp
;
206 FOR_EACH_PTR(checked
, tmp
) {
209 } END_FOR_EACH_PTR(tmp
);
215 * Example code: if (foo == 99) {
217 * Say 'foo' is a merged state that has many possible values. It is the combination
218 * of merges. separate_pools() iterates through the pools recursively and calls
219 * do_compare() for each time 'foo' was set.
221 static void separate_pools(struct sm_state
*sm
, int comparison
, struct range_list
*rl
,
223 struct stree_stack
**true_stack
,
224 struct stree_stack
**false_stack
,
225 struct state_list
**checked
)
227 int free_checked
= 0;
228 struct state_list
*checked_states
= NULL
;
234 Sometimes the implications are just too big to deal with
235 so we bail. Theoretically, bailing out here can cause more false
236 positives but won't hide actual bugs.
238 if (sm
->nr_children
> 4000) {
239 if (option_debug
|| option_debug_implied
) {
240 static char buf
[1028];
241 snprintf(buf
, sizeof(buf
), "debug: separate_pools: nr_children over 4000 (%d). (%s %s)",
242 sm
->nr_children
, sm
->name
, show_state(sm
->state
));
243 implied_debug_msg
= buf
;
248 if (checked
== NULL
) {
249 checked
= &checked_states
;
252 if (is_checked(*checked
, sm
))
254 add_ptr_list(checked
, sm
);
256 do_compare(sm
, comparison
, rl
, left_right
, true_stack
, false_stack
);
258 separate_pools(sm
->left
, comparison
, rl
, left_right
, true_stack
, false_stack
, checked
);
259 separate_pools(sm
->right
, comparison
, rl
, left_right
, true_stack
, false_stack
, checked
);
264 struct sm_state
*filter_pools(struct sm_state
*sm
,
265 const struct stree_stack
*remove_stack
,
266 const struct stree_stack
*keep_stack
,
269 struct sm_state
*ret
= NULL
;
270 struct sm_state
*left
;
271 struct sm_state
*right
;
277 if (sm
->nr_children
> 4000) {
278 if (option_debug
|| option_debug_implied
) {
279 static char buf
[1028];
280 snprintf(buf
, sizeof(buf
), "debug: %s: nr_children over 4000 (%d). (%s %s)",
281 __func__
, sm
->nr_children
, sm
->name
, show_state(sm
->state
));
282 implied_debug_msg
= buf
;
287 if (pool_in_pools(sm
->pool
, remove_stack
)) {
288 DIMPLIED("removed %s from %d [stree %d]\n", show_sm(sm
), sm
->line
, get_stree_id(sm
->pool
));
293 if (!is_merged(sm
) || pool_in_pools(sm
->pool
, keep_stack
)) {
294 DIMPLIED("kept %s from %d [stree %d]\n", show_sm(sm
), sm
->line
, get_stree_id(sm
->pool
));
298 DIMPLIED("checking %s from %d (%d) [stree %d] left = %s [stree %d] right = %s [stree %d]\n",
299 show_sm(sm
), sm
->line
, sm
->nr_children
, get_stree_id(sm
->pool
),
300 sm
->left
? show_sm(sm
->left
) : "<none>", sm
->left
? get_stree_id(sm
->left
->pool
) : -1,
301 sm
->right
? show_sm(sm
->right
) : "<none>", sm
->right
? get_stree_id(sm
->right
->pool
) : -1);
302 left
= filter_pools(sm
->left
, remove_stack
, keep_stack
, &removed
);
303 right
= filter_pools(sm
->right
, remove_stack
, keep_stack
, &removed
);
305 DIMPLIED("kept %s from %d [stree %d]\n", show_sm(sm
), sm
->line
, get_stree_id(sm
->pool
));
309 if (!left
&& !right
) {
310 DIMPLIED("removed %s from %d <none> [stree %d]\n", show_sm(sm
), sm
->line
, get_stree_id(sm
->pool
));
315 ret
= clone_sm(right
);
319 ret
->pool
= sm
->pool
;
321 ret
= clone_sm(left
);
325 ret
->pool
= sm
->pool
;
327 ret
= merge_sm_states(left
, right
);
328 ret
->pool
= sm
->pool
;
331 DIMPLIED("partial %s => ", show_sm(sm
));
332 DIMPLIED("%s from %d [stree %d]\n", show_sm(ret
), sm
->line
, get_stree_id(sm
->pool
));
336 static int highest_stree_id(struct sm_state
*sm
)
341 if (!sm
->left
&& !sm
->right
)
345 left
= get_stree_id(sm
->left
->pool
);
347 right
= get_stree_id(sm
->right
->pool
);
354 static struct stree
*filter_stack(struct sm_state
*gate_sm
,
355 struct stree
*pre_stree
,
356 const struct stree_stack
*remove_stack
,
357 const struct stree_stack
*keep_stack
)
359 struct stree
*ret
= NULL
;
360 struct sm_state
*tmp
;
361 struct sm_state
*filtered_sm
;
367 FOR_EACH_SM(pre_stree
, tmp
) {
370 if (highest_stree_id(tmp
) < highest_stree_id(gate_sm
)) {
371 DIMPLIED("skipping %s. set before. %d vs %d\n",
372 tmp
->name
, highest_stree_id(tmp
),
373 highest_stree_id(gate_sm
));
377 filtered_sm
= filter_pools(tmp
, remove_stack
, keep_stack
, &modified
);
378 if (filtered_sm
&& modified
) {
379 /* the assignments here are for borrowed implications */
380 filtered_sm
->name
= tmp
->name
;
381 filtered_sm
->sym
= tmp
->sym
;
382 avl_insert(&ret
, filtered_sm
);
387 } END_FOR_EACH_SM(tmp
);
391 static void separate_and_filter(struct sm_state
*sm
, int comparison
, struct range_list
*rl
,
393 struct stree
*pre_stree
,
394 struct stree
**true_states
,
395 struct stree
**false_states
)
397 struct stree_stack
*true_stack
= NULL
;
398 struct stree_stack
*false_stack
= NULL
;
399 struct timeval time_before
;
400 struct timeval time_after
;
402 gettimeofday(&time_before
, NULL
);
404 if (!is_merged(sm
)) {
405 DIMPLIED("%d '%s' is not merged.\n", get_lineno(), sm
->name
);
409 if (option_debug_implied
|| option_debug
) {
410 if (left_right
== LEFT
)
411 sm_msg("checking implications: (%s %s %s)",
412 sm
->name
, show_special(comparison
), show_rl(rl
));
414 sm_msg("checking implications: (%s %s %s)",
415 show_rl(rl
), show_special(comparison
), sm
->name
);
418 separate_pools(sm
, comparison
, rl
, left_right
, &true_stack
, &false_stack
, NULL
);
420 DIMPLIED("filtering true stack.\n");
421 *true_states
= filter_stack(sm
, pre_stree
, false_stack
, true_stack
);
422 DIMPLIED("filtering false stack.\n");
423 *false_states
= filter_stack(sm
, pre_stree
, true_stack
, false_stack
);
424 free_stree_stack(&true_stack
);
425 free_stree_stack(&false_stack
);
426 if (option_debug_implied
|| option_debug
) {
427 printf("These are the implied states for the true path:\n");
428 __print_stree(*true_states
);
429 printf("These are the implied states for the false path:\n");
430 __print_stree(*false_states
);
433 gettimeofday(&time_after
, NULL
);
434 if (time_after
.tv_sec
- time_before
.tv_sec
> 7)
435 __bail_on_rest_of_function
= 1;
438 static struct expression
*get_left_most_expr(struct expression
*expr
)
440 expr
= strip_expr(expr
);
441 if (expr
->type
== EXPR_ASSIGNMENT
)
442 return get_left_most_expr(expr
->left
);
446 static int is_merged_expr(struct expression
*expr
)
451 if (get_value(expr
, &dummy
))
453 sm
= get_sm_state_expr(SMATCH_EXTRA
, expr
);
461 static void delete_equiv_stree(struct stree
**stree
, const char *name
, struct symbol
*sym
)
463 struct smatch_state
*state
;
464 struct relation
*rel
;
466 state
= get_state(SMATCH_EXTRA
, name
, sym
);
467 if (!estate_related(state
)) {
468 delete_state_stree(stree
, SMATCH_EXTRA
, name
, sym
);
472 FOR_EACH_PTR(estate_related(state
), rel
) {
473 delete_state_stree(stree
, SMATCH_EXTRA
, rel
->name
, rel
->sym
);
474 } END_FOR_EACH_PTR(rel
);
477 static void handle_comparison(struct expression
*expr
,
478 struct stree
**implied_true
,
479 struct stree
**implied_false
)
481 struct sm_state
*sm
= NULL
;
482 struct range_list
*rl
= NULL
;
483 struct expression
*left
;
484 struct expression
*right
;
487 left
= get_left_most_expr(expr
->left
);
488 right
= get_left_most_expr(expr
->right
);
490 if (is_merged_expr(left
)) {
492 sm
= get_sm_state_expr(SMATCH_EXTRA
, left
);
493 get_implied_rl(right
, &rl
);
494 } else if (is_merged_expr(right
)) {
496 sm
= get_sm_state_expr(SMATCH_EXTRA
, right
);
497 get_implied_rl(left
, &rl
);
505 separate_and_filter(sm
, expr
->op
, rl
, left_right
, __get_cur_stree(), implied_true
, implied_false
);
507 delete_equiv_stree(implied_true
, sm
->name
, sm
->sym
);
508 delete_equiv_stree(implied_false
, sm
->name
, sm
->sym
);
511 static void handle_zero_comparison(struct expression
*expr
,
512 struct stree
**implied_true
,
513 struct stree
**implied_false
)
519 if (expr
->type
== EXPR_POSTOP
)
520 expr
= strip_expr(expr
->unop
);
522 if (expr
->type
== EXPR_ASSIGNMENT
) {
523 /* most of the time ->pools will be empty here because we
524 just set the state, but if have assigned a conditional
525 function there are implications. */
529 name
= expr_to_var_sym(expr
, &sym
);
532 sm
= get_sm_state(SMATCH_EXTRA
, name
, sym
);
536 separate_and_filter(sm
, SPECIAL_NOTEQUAL
, tmp_range_list(0), LEFT
, __get_cur_stree(), implied_true
, implied_false
);
537 delete_equiv_stree(implied_true
, name
, sym
);
538 delete_equiv_stree(implied_false
, name
, sym
);
543 static int handled_by_implied_hook(struct expression
*expr
,
544 struct stree
**implied_true
,
545 struct stree
**implied_false
)
547 struct stree_stack
*true_stack
= NULL
;
548 struct stree_stack
*false_stack
= NULL
;
549 struct stree
*pre_stree
;
552 sm
= comparison_implication_hook(expr
, &true_stack
, &false_stack
);
554 sm
= stored_condition_implication_hook(expr
, &true_stack
, &false_stack
);
558 pre_stree
= clone_stree(__get_cur_stree());
560 *implied_true
= filter_stack(sm
, pre_stree
, false_stack
, true_stack
);
561 *implied_false
= filter_stack(sm
, pre_stree
, true_stack
, false_stack
);
563 free_stree(&pre_stree
);
564 free_stree_stack(&true_stack
);
565 free_stree_stack(&false_stack
);
570 static void get_tf_states(struct expression
*expr
,
571 struct stree
**implied_true
,
572 struct stree
**implied_false
)
574 if (handled_by_implied_hook(expr
, implied_true
, implied_false
))
577 if (expr
->type
== EXPR_COMPARE
)
578 handle_comparison(expr
, implied_true
, implied_false
);
580 handle_zero_comparison(expr
, implied_true
, implied_false
);
583 static struct stree
*saved_implied_true
;
584 static struct stree
*saved_implied_false
;
586 static void save_implications_hook(struct expression
*expr
)
588 get_tf_states(expr
, &saved_implied_true
, &saved_implied_false
);
591 static void set_implied_states(struct expression
*expr
)
595 FOR_EACH_SM(saved_implied_true
, sm
) {
596 if (!get_state_stree(saved_implied_false
, sm
->owner
, sm
->name
, sm
->sym
)) {
597 struct sm_state
*orig
;
599 orig
= get_sm_state(sm
->owner
, sm
->name
, sm
->sym
);
600 set_state_stree(&saved_implied_false
, sm
->owner
, sm
->name
, sm
->sym
, orig
->state
);
602 } END_FOR_EACH_SM(sm
);
604 FOR_EACH_SM(saved_implied_false
, sm
) {
605 if (!get_state_stree(saved_implied_true
, sm
->owner
, sm
->name
, sm
->sym
)) {
606 struct sm_state
*orig
;
608 orig
= get_sm_state(sm
->owner
, sm
->name
, sm
->sym
);
609 set_state_stree(&saved_implied_true
, sm
->owner
, sm
->name
, sm
->sym
, orig
->state
);
611 } END_FOR_EACH_SM(sm
);
613 FOR_EACH_SM(saved_implied_true
, sm
) {
614 __set_true_false_sm(sm
, NULL
);
615 } END_FOR_EACH_SM(sm
);
616 free_stree(&saved_implied_true
);
618 FOR_EACH_SM(saved_implied_false
, sm
) {
619 __set_true_false_sm(NULL
, sm
);
620 } END_FOR_EACH_SM(sm
);
621 free_stree(&saved_implied_false
);
624 struct range_list
*__get_implied_values(struct expression
*switch_expr
)
628 struct smatch_state
*state
;
629 struct range_list
*ret
= NULL
;
631 name
= expr_to_var_sym(switch_expr
, &sym
);
634 state
= get_state(SMATCH_EXTRA
, name
, sym
);
637 ret
= clone_rl(estate_rl(state
));
643 type
= get_type(switch_expr
);
644 ret
= alloc_rl(sval_type_min(type
), sval_type_max(type
));
649 struct stree
*__implied_case_stree(struct expression
*switch_expr
,
650 struct expression
*case_expr
,
651 struct expression
*case_to
,
652 struct range_list_stack
**remaining_cases
,
653 struct stree
**raw_stree
)
658 struct stree
*true_states
= NULL
;
659 struct stree
*false_states
= NULL
;
660 struct stree
*extra_states
= NULL
;
661 struct stree
*ret
= clone_stree(*raw_stree
);
663 struct range_list
*rl
= NULL
;
665 name
= expr_to_var_sym(switch_expr
, &sym
);
668 sm
= get_sm_state_stree(*raw_stree
, SMATCH_EXTRA
, name
, sym
);
670 if (get_value(case_to
, &end
) && get_value(case_expr
, &start
)) {
671 filter_top_rl(remaining_cases
, start
, end
);
672 add_range(&rl
, start
, end
);
673 } else if (get_value(case_expr
, &start
)) {
674 filter_top_rl(remaining_cases
, start
, start
);
675 add_range(&rl
, start
, start
);
677 rl
= clone_rl(top_rl(*remaining_cases
));
681 separate_and_filter(sm
, SPECIAL_EQUAL
, rl
, LEFT
, *raw_stree
, &true_states
, &false_states
);
683 __push_fake_cur_stree();
685 set_extra_nomod(name
, sym
, alloc_estate_rl(rl
));
686 extra_states
= __pop_fake_cur_stree();
687 overwrite_stree(extra_states
, &true_states
);
688 overwrite_stree(true_states
, &ret
);
689 free_stree(&extra_states
);
690 free_stree(&true_states
);
691 free_stree(&false_states
);
697 static void match_end_func(struct symbol
*sym
)
701 implied_debug_msg
= NULL
;
704 static int sm_state_in_slist(struct sm_state
*sm
, struct state_list
*slist
)
706 struct sm_state
*tmp
;
708 FOR_EACH_PTR(slist
, tmp
) {
711 } END_FOR_EACH_PTR(tmp
);
716 * The situation is we have a SMATCH_EXTRA state and we want to break it into
717 * each of the ->possible states and find the implications of each. The caller
718 * has to use __push_fake_cur_stree() to preserve the correct states so they
719 * can be restored later.
721 void overwrite_states_using_pool(struct sm_state
*sm
)
723 struct sm_state
*old
;
724 struct sm_state
*new;
729 FOR_EACH_SM(sm
->pool
, old
) {
730 new = get_sm_state(old
->owner
, old
->name
, old
->sym
);
731 if (!new) /* the variable went out of scope */
733 if (sm_state_in_slist(old
, new->possible
))
734 set_state(old
->owner
, old
->name
, old
->sym
, old
->state
);
735 } END_FOR_EACH_SM(old
);
738 void __extra_match_condition(struct expression
*expr
);
739 void __comparison_match_condition(struct expression
*expr
);
740 void __stored_condition(struct expression
*expr
);
741 void register_implications(int id
)
743 add_hook(&save_implications_hook
, CONDITION_HOOK
);
744 add_hook(&set_implied_states
, CONDITION_HOOK
);
745 add_hook(&__extra_match_condition
, CONDITION_HOOK
);
746 add_hook(&__comparison_match_condition
, CONDITION_HOOK
);
747 add_hook(&__stored_condition
, CONDITION_HOOK
);
748 add_hook(&match_end_func
, END_FUNC_HOOK
);