2 * sparse/smatch_implied.c
4 * Copyright (C) 2008 Dan Carpenter.
6 * Licensed under the Open Software License version 1.1
11 * Imagine we have this code:
18 * if (foo == 99) // <-- point #2
19 * bar->baz; // <-- point #3
22 * At point #3 bar is non null and can be dereferenced.
24 * It's smatch_implied.c which sets bar to non null at point #2.
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_pool
29 * list to show the other states which were there when foo == 99.
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
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.
40 * That is the implied state of bar.
42 * merge_slist() sets up ->my_pool. An sm_state only has one ->my_pool and
43 * that is the pool where it was first set. The my pool gets set when
44 * code paths merge. States that have been set since the last merge do
45 * not have a ->my_pool.
46 * merge_sm_state() sets ->left and ->right. (These are the states which were
47 * merged to form the current state.)
48 * a pool: a pool is an slist that has been merged with another slist.
54 #include "smatch_slist.h"
55 #include "smatch_extra.h"
57 char *implied_debug_msg
;
58 #define DIMPLIED(msg...) do { if (option_debug_implied) printf(msg); } while (0)
60 int option_debug_implied
= 0;
61 int option_no_implied
= 0;
68 * It messes things up to free range list allocations. This helper fuction
69 * lets us reuse memory instead of doing new allocations.
71 static struct range_list
*tmp_range_list(long long num
)
73 static struct range_list
*my_list
= NULL
;
74 static struct data_range
*my_range
;
76 __free_ptr_list((struct ptr_list
**)&my_list
);
77 my_range
= alloc_range(num
, num
);
80 add_ptr_list(&my_list
, my_range
);
84 static void print_debug_tf(struct sm_state
*s
, int istrue
, int isfalse
)
86 if (!option_debug_implied
&& !option_debug
)
89 if (istrue
&& isfalse
) {
90 printf("'%s = %s' from %d does not exist.\n", s
->name
,
91 show_state(s
->state
), s
->line
);
93 printf("'%s = %s' from %d is true.\n", s
->name
, show_state(s
->state
),
96 printf("'%s = %s' from %d is false.\n", s
->name
, show_state(s
->state
),
99 printf("'%s = %s' from %d could be true or false.\n", s
->name
,
100 show_state(s
->state
), s
->line
);
105 * If 'foo' == 99 add it that pool to the true pools. If it's false, add it to
106 * the false pools. If we're not sure, then we don't add it to either.
108 static void do_compare(struct sm_state
*sm_state
, int comparison
, struct range_list
*vals
,
110 struct state_list_stack
**true_stack
,
111 struct state_list_stack
**false_stack
)
117 if (!sm_state
->my_pool
)
120 if (is_implied(sm_state
)) {
121 s
= get_sm_state_slist(sm_state
->my_pool
,
122 sm_state
->owner
, sm_state
->name
,
129 if (option_debug_implied
|| option_debug
)
130 sm_msg("%s from %d, has borrowed implications.",
131 sm_state
->name
, sm_state
->line
);
136 istrue
= !possibly_false_range_lists(estate_ranges(s
->state
), comparison
, vals
);
137 isfalse
= !possibly_true_range_lists(estate_ranges(s
->state
), comparison
, vals
);
139 istrue
= !possibly_false_range_lists(vals
, comparison
, estate_ranges(s
->state
));
140 isfalse
= !possibly_true_range_lists(vals
, comparison
, estate_ranges(s
->state
));
143 print_debug_tf(s
, istrue
, isfalse
);
146 add_pool(true_stack
, s
->my_pool
);
149 add_pool(false_stack
, s
->my_pool
);
152 static int pool_in_pools(struct state_list
*pool
,
153 struct state_list_stack
*pools
)
155 struct state_list
*tmp
;
157 FOR_EACH_PTR(pools
, tmp
) {
162 } END_FOR_EACH_PTR(tmp
);
166 static int is_checked(struct state_list
*checked
, struct sm_state
*sm
)
168 struct sm_state
*tmp
;
170 FOR_EACH_PTR(checked
, tmp
) {
173 } END_FOR_EACH_PTR(tmp
);
179 * Example code: if (foo == 99) {
181 * Say 'foo' is a merged state that has many possible values. It is the combination
182 * of merges. separate_pools() iterates through the pools recursively and calls
183 * do_compare() for each time 'foo' was set.
185 static void separate_pools(struct sm_state
*sm_state
, int comparison
, struct range_list
*vals
,
187 struct state_list_stack
**true_stack
,
188 struct state_list_stack
**false_stack
,
189 struct state_list
**checked
)
191 int free_checked
= 0;
192 struct state_list
*checked_states
= NULL
;
198 Sometimes the implications are just too big to deal with
199 so we bail. Theoretically, bailing out here can cause more false
200 positives but won't hide actual bugs.
202 if (sm_state
->nr_children
> 4000) {
204 (char *) "debug: seperate_pools: nr_children over 4000.";
208 if (checked
== NULL
) {
209 checked
= &checked_states
;
212 if (is_checked(*checked
, sm_state
))
214 add_ptr_list(checked
, sm_state
);
216 do_compare(sm_state
, comparison
, vals
, lr
, true_stack
, false_stack
);
218 separate_pools(sm_state
->left
, comparison
, vals
, lr
, true_stack
, false_stack
, checked
);
219 separate_pools(sm_state
->right
, comparison
, vals
, lr
, true_stack
, false_stack
, checked
);
224 struct sm_state
*remove_my_pools(struct sm_state
*sm
,
225 struct state_list_stack
*pools
, int *modified
)
227 struct sm_state
*ret
= NULL
;
228 struct sm_state
*left
;
229 struct sm_state
*right
;
235 if (sm
->nr_children
> 4000) {
237 (char *) "debug: remove_my_pools: nr_children over 4000";
241 if (pool_in_pools(sm
->my_pool
, pools
)) {
242 DIMPLIED("removed %s = %s from %d\n", sm
->name
,
243 show_state(sm
->state
), sm
->line
);
248 if (!is_merged(sm
)) {
249 DIMPLIED("kept %s = %s from %d\n", sm
->name
, show_state(sm
->state
),
254 DIMPLIED("checking %s = %s from %d\n", sm
->name
, show_state(sm
->state
), sm
->line
);
255 left
= remove_my_pools(sm
->left
, pools
, &removed
);
256 right
= remove_my_pools(sm
->right
, pools
, &removed
);
258 DIMPLIED("kept %s = %s from %d\n", sm
->name
, show_state(sm
->state
), sm
->line
);
262 if (!left
&& !right
) {
263 DIMPLIED("removed %s = %s from %d\n", sm
->name
, show_state(sm
->state
), sm
->line
);
268 ret
= clone_sm(right
);
272 ret
->my_pool
= sm
->my_pool
;
274 ret
= clone_sm(left
);
278 ret
->my_pool
= sm
->my_pool
;
280 ret
= merge_sm_states(left
, right
);
281 ret
->my_pool
= sm
->my_pool
;
284 DIMPLIED("partial %s = %s from %d\n", sm
->name
, show_state(sm
->state
), sm
->line
);
288 static struct state_list
*filter_stack(struct state_list
*pre_list
,
289 struct state_list_stack
*stack
)
291 struct state_list
*ret
= NULL
;
292 struct sm_state
*tmp
;
293 struct sm_state
*filtered_sm
;
299 FOR_EACH_PTR(pre_list
, tmp
) {
301 filtered_sm
= remove_my_pools(tmp
, stack
, &modified
);
302 if (filtered_sm
&& modified
) {
303 filtered_sm
->name
= tmp
->name
;
304 filtered_sm
->sym
= tmp
->sym
;
305 add_ptr_list(&ret
, filtered_sm
);
310 } END_FOR_EACH_PTR(tmp
);
314 static void separate_and_filter(struct sm_state
*sm_state
, int comparison
, struct range_list
*vals
,
316 struct state_list
*pre_list
,
317 struct state_list
**true_states
,
318 struct state_list
**false_states
)
320 struct state_list_stack
*true_stack
= NULL
;
321 struct state_list_stack
*false_stack
= NULL
;
322 struct timeval time_before
;
323 struct timeval time_after
;
325 gettimeofday(&time_before
, NULL
);
327 if (!is_merged(sm_state
)) {
328 DIMPLIED("%d '%s' is not merged.\n", get_lineno(), sm_state
->name
);
332 if (option_debug_implied
|| option_debug
) {
334 sm_msg("checking implications: (%s %s %s)",
335 sm_state
->name
, show_special(comparison
), show_ranges(vals
));
337 sm_msg("checking implications: (%s %s %s)",
338 show_ranges(vals
), show_special(comparison
), sm_state
->name
);
341 separate_pools(sm_state
, comparison
, vals
, lr
, &true_stack
, &false_stack
, NULL
);
343 DIMPLIED("filtering true stack.\n");
344 *true_states
= filter_stack(pre_list
, false_stack
);
345 DIMPLIED("filtering false stack.\n");
346 *false_states
= filter_stack(pre_list
, true_stack
);
347 free_stack(&true_stack
);
348 free_stack(&false_stack
);
349 if (option_debug_implied
|| option_debug
) {
350 printf("These are the implied states for the true path:\n");
351 __print_slist(*true_states
);
352 printf("These are the implied states for the false path:\n");
353 __print_slist(*false_states
);
356 gettimeofday(&time_after
, NULL
);
357 if (time_after
.tv_sec
- time_before
.tv_sec
> 7)
358 __bail_on_rest_of_function
= 1;
361 static struct expression
*get_left_most_expr(struct expression
*expr
)
363 expr
= strip_expr(expr
);
364 if (expr
->type
== EXPR_ASSIGNMENT
)
365 return get_left_most_expr(expr
->left
);
369 static int is_merged_expr(struct expression
*expr
)
374 if (get_value(expr
, &dummy
))
376 sm
= get_sm_state_expr(SMATCH_EXTRA
, expr
);
384 static void delete_equiv_slist(struct state_list
**slist
, const char *name
, struct symbol
*sym
)
386 struct smatch_state
*state
;
387 struct relation
*rel
;
389 state
= get_state(SMATCH_EXTRA
, name
, sym
);
390 if (!estate_related(state
)) {
391 delete_state_slist(slist
, SMATCH_EXTRA
, name
, sym
);
395 FOR_EACH_PTR(estate_related(state
), rel
) {
396 delete_state_slist(slist
, SMATCH_EXTRA
, rel
->name
, rel
->sym
);
397 } END_FOR_EACH_PTR(rel
);
400 static void handle_comparison(struct expression
*expr
,
401 struct state_list
**implied_true
,
402 struct state_list
**implied_false
)
404 struct sm_state
*sm
= NULL
;
405 struct range_list
*ranges
= NULL
;
406 struct expression
*left
;
407 struct expression
*right
;
410 left
= get_left_most_expr(expr
->left
);
411 right
= get_left_most_expr(expr
->right
);
413 if (is_merged_expr(left
)) {
415 sm
= get_sm_state_expr(SMATCH_EXTRA
, left
);
416 get_implied_range_list(right
, &ranges
);
417 } else if (is_merged_expr(right
)) {
419 sm
= get_sm_state_expr(SMATCH_EXTRA
, right
);
420 get_implied_range_list(left
, &ranges
);
423 if (!ranges
|| !sm
) {
424 free_range_list(&ranges
);
428 separate_and_filter(sm
, expr
->op
, ranges
, lr
, __get_cur_slist(), implied_true
, implied_false
);
429 free_range_list(&ranges
);
430 delete_equiv_slist(implied_true
, sm
->name
, sm
->sym
);
431 delete_equiv_slist(implied_false
, sm
->name
, sm
->sym
);
434 static void handle_zero_comparison(struct expression
*expr
,
435 struct state_list
**implied_true
,
436 struct state_list
**implied_false
)
442 if (expr
->type
== EXPR_POSTOP
)
443 expr
= strip_expr(expr
->unop
);
445 if (expr
->type
== EXPR_ASSIGNMENT
) {
446 /* most of the time ->my_pools will be empty here because we
447 just set the state, but if have assigned a conditional
448 function there are implications. */
452 name
= get_variable_from_expr(expr
, &sym
);
455 sm
= get_sm_state(SMATCH_EXTRA
, name
, sym
);
459 separate_and_filter(sm
, SPECIAL_NOTEQUAL
, tmp_range_list(0), LEFT
, __get_cur_slist(), implied_true
, implied_false
);
460 delete_equiv_slist(implied_true
, name
, sym
);
461 delete_equiv_slist(implied_false
, name
, sym
);
466 static void get_tf_states(struct expression
*expr
,
467 struct state_list
**implied_true
,
468 struct state_list
**implied_false
)
470 if (expr
->type
== EXPR_COMPARE
)
471 handle_comparison(expr
, implied_true
, implied_false
);
473 handle_zero_comparison(expr
, implied_true
, implied_false
);
476 static void implied_states_hook(struct expression
*expr
)
479 struct state_list
*implied_true
= NULL
;
480 struct state_list
*implied_false
= NULL
;
482 if (option_no_implied
)
485 get_tf_states(expr
, &implied_true
, &implied_false
);
487 FOR_EACH_PTR(implied_true
, sm
) {
488 __set_true_false_sm(sm
, NULL
);
489 } END_FOR_EACH_PTR(sm
);
490 free_slist(&implied_true
);
492 FOR_EACH_PTR(implied_false
, sm
) {
493 __set_true_false_sm(NULL
, sm
);
494 } END_FOR_EACH_PTR(sm
);
495 free_slist(&implied_false
);
498 struct range_list
*__get_implied_values(struct expression
*switch_expr
)
502 struct smatch_state
*state
;
503 struct range_list
*ret
= NULL
;
505 name
= get_variable_from_expr(switch_expr
, &sym
);
508 state
= get_state(SMATCH_EXTRA
, name
, sym
);
511 ret
= clone_range_list(estate_ranges(state
));
515 add_range(&ret
, whole_range
.min
, whole_range
.max
);
519 struct state_list
*__implied_case_slist(struct expression
*switch_expr
,
520 struct expression
*case_expr
,
521 struct range_list_stack
**remaining_cases
,
522 struct state_list
**raw_slist
)
527 struct sm_state
*true_sm
;
528 struct state_list
*true_states
= NULL
;
529 struct state_list
*false_states
= NULL
;
530 struct state_list
*ret
= clone_slist(*raw_slist
);
532 struct range_list
*vals
= NULL
;
534 name
= get_variable_from_expr(switch_expr
, &sym
);
537 sm
= get_sm_state_slist(*raw_slist
, SMATCH_EXTRA
, name
, sym
);
539 vals
= top_range_list(*remaining_cases
);
541 if (!get_value(case_expr
, &val
))
544 filter_top_range_list(remaining_cases
, val
);
545 add_range(&vals
, val
, val
);
548 separate_and_filter(sm
, SPECIAL_EQUAL
, vals
, LEFT
, *raw_slist
, &true_states
, &false_states
);
550 true_sm
= get_sm_state_slist(true_states
, SMATCH_EXTRA
, name
, sym
);
552 set_state_slist(&true_states
, SMATCH_EXTRA
, name
, sym
, alloc_estate_range_list(vals
));
553 overwrite_slist(true_states
, &ret
);
554 free_slist(&true_states
);
555 free_slist(&false_states
);
561 static void match_end_func(struct symbol
*sym
)
563 implied_debug_msg
= NULL
;
567 * get_implications() can be called by check_ scripts.
569 void get_implications(char *name
, struct symbol
*sym
, int comparison
, long long num
,
570 struct state_list
**true_states
,
571 struct state_list
**false_states
)
575 sm
= get_sm_state(SMATCH_EXTRA
, name
, sym
);
578 if (slist_has_state(sm
->possible
, &undefined
))
580 separate_and_filter(sm
, comparison
, tmp_range_list(num
), LEFT
, __get_cur_slist(), true_states
, false_states
);
583 void __extra_match_condition(struct expression
*expr
);
584 void register_implications(int id
)
586 add_hook(&implied_states_hook
, CONDITION_HOOK
);
587 add_hook(&__extra_match_condition
, CONDITION_HOOK
);
588 add_hook(&match_end_func
, END_FUNC_HOOK
);