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 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 ->pool. An sm_state only has one ->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
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 * add_pool() adds a slist to *pools. If the slist has already been
106 * added earlier then it doesn't get added a second time.
108 static void add_pool(struct state_list_stack
**pools
, struct state_list
*new)
110 struct state_list
*tmp
;
112 FOR_EACH_PTR(*pools
, tmp
) {
115 else if (tmp
== new) {
118 INSERT_CURRENT(new, tmp
);
121 } END_FOR_EACH_PTR(tmp
);
122 add_ptr_list(pools
, new);
126 * If 'foo' == 99 add it that pool to the true pools. If it's false, add it to
127 * the false pools. If we're not sure, then we don't add it to either.
129 static void do_compare(struct sm_state
*sm_state
, int comparison
, struct range_list
*vals
,
131 struct state_list_stack
**true_stack
,
132 struct state_list_stack
**false_stack
)
141 if (is_implied(sm_state
)) {
142 s
= get_sm_state_slist(sm_state
->pool
,
143 sm_state
->owner
, sm_state
->name
,
150 if (option_debug_implied
|| option_debug
)
151 sm_msg("%s from %d, has borrowed implications.",
152 sm_state
->name
, sm_state
->line
);
157 istrue
= !possibly_false_range_lists(estate_ranges(s
->state
), comparison
, vals
);
158 isfalse
= !possibly_true_range_lists(estate_ranges(s
->state
), comparison
, vals
);
160 istrue
= !possibly_false_range_lists(vals
, comparison
, estate_ranges(s
->state
));
161 isfalse
= !possibly_true_range_lists(vals
, comparison
, estate_ranges(s
->state
));
164 print_debug_tf(s
, istrue
, isfalse
);
167 add_pool(true_stack
, s
->pool
);
170 add_pool(false_stack
, s
->pool
);
173 static int pool_in_pools(struct state_list
*pool
,
174 struct state_list_stack
*pools
)
176 struct state_list
*tmp
;
178 FOR_EACH_PTR(pools
, tmp
) {
183 } END_FOR_EACH_PTR(tmp
);
187 static int is_checked(struct state_list
*checked
, struct sm_state
*sm
)
189 struct sm_state
*tmp
;
191 FOR_EACH_PTR(checked
, tmp
) {
194 } END_FOR_EACH_PTR(tmp
);
200 * Example code: if (foo == 99) {
202 * Say 'foo' is a merged state that has many possible values. It is the combination
203 * of merges. separate_pools() iterates through the pools recursively and calls
204 * do_compare() for each time 'foo' was set.
206 static void separate_pools(struct sm_state
*sm_state
, int comparison
, struct range_list
*vals
,
208 struct state_list_stack
**true_stack
,
209 struct state_list_stack
**false_stack
,
210 struct state_list
**checked
)
212 int free_checked
= 0;
213 struct state_list
*checked_states
= NULL
;
219 Sometimes the implications are just too big to deal with
220 so we bail. Theoretically, bailing out here can cause more false
221 positives but won't hide actual bugs.
223 if (sm_state
->nr_children
> 4000) {
225 (char *) "debug: seperate_pools: nr_children over 4000.";
229 if (checked
== NULL
) {
230 checked
= &checked_states
;
233 if (is_checked(*checked
, sm_state
))
235 add_ptr_list(checked
, sm_state
);
237 do_compare(sm_state
, comparison
, vals
, lr
, true_stack
, false_stack
);
239 separate_pools(sm_state
->left
, comparison
, vals
, lr
, true_stack
, false_stack
, checked
);
240 separate_pools(sm_state
->right
, comparison
, vals
, lr
, true_stack
, false_stack
, checked
);
245 struct sm_state
*remove_pools(struct sm_state
*sm
,
246 struct state_list_stack
*pools
, int *modified
)
248 struct sm_state
*ret
= NULL
;
249 struct sm_state
*left
;
250 struct sm_state
*right
;
256 if (sm
->nr_children
> 4000) {
258 (char *) "debug: remove_pools: nr_children over 4000";
262 if (pool_in_pools(sm
->pool
, pools
)) {
263 DIMPLIED("removed %s from %d\n", show_sm(sm
), sm
->line
);
268 if (!is_merged(sm
)) {
269 DIMPLIED("kept %s from %d\n", show_sm(sm
), sm
->line
);
273 DIMPLIED("checking %s from %d\n", show_sm(sm
), sm
->line
);
274 left
= remove_pools(sm
->left
, pools
, &removed
);
275 right
= remove_pools(sm
->right
, pools
, &removed
);
277 DIMPLIED("kept %s from %d\n", show_sm(sm
), sm
->line
);
281 if (!left
&& !right
) {
282 DIMPLIED("removed %s from %d <none>\n", show_sm(sm
), sm
->line
);
287 ret
= clone_sm(right
);
291 ret
->pool
= sm
->pool
;
293 ret
= clone_sm(left
);
297 ret
->pool
= sm
->pool
;
299 ret
= merge_sm_states(left
, right
);
300 ret
->pool
= sm
->pool
;
303 DIMPLIED("partial %s => ", show_sm(sm
));
304 DIMPLIED("%s from %d\n", show_sm(ret
), sm
->line
);
308 static struct state_list
*filter_stack(struct state_list
*pre_list
,
309 struct state_list_stack
*stack
)
311 struct state_list
*ret
= NULL
;
312 struct sm_state
*tmp
;
313 struct sm_state
*filtered_sm
;
319 FOR_EACH_PTR(pre_list
, tmp
) {
321 filtered_sm
= remove_pools(tmp
, stack
, &modified
);
322 if (filtered_sm
&& modified
) {
323 filtered_sm
->name
= tmp
->name
;
324 filtered_sm
->sym
= tmp
->sym
;
325 add_ptr_list(&ret
, filtered_sm
);
330 } END_FOR_EACH_PTR(tmp
);
334 static void separate_and_filter(struct sm_state
*sm_state
, int comparison
, struct range_list
*vals
,
336 struct state_list
*pre_list
,
337 struct state_list
**true_states
,
338 struct state_list
**false_states
)
340 struct state_list_stack
*true_stack
= NULL
;
341 struct state_list_stack
*false_stack
= NULL
;
342 struct timeval time_before
;
343 struct timeval time_after
;
345 gettimeofday(&time_before
, NULL
);
347 if (!is_merged(sm_state
)) {
348 DIMPLIED("%d '%s' is not merged.\n", get_lineno(), sm_state
->name
);
352 if (option_debug_implied
|| option_debug
) {
354 sm_msg("checking implications: (%s %s %s)",
355 sm_state
->name
, show_special(comparison
), show_ranges(vals
));
357 sm_msg("checking implications: (%s %s %s)",
358 show_ranges(vals
), show_special(comparison
), sm_state
->name
);
361 separate_pools(sm_state
, comparison
, vals
, lr
, &true_stack
, &false_stack
, NULL
);
363 DIMPLIED("filtering true stack.\n");
364 *true_states
= filter_stack(pre_list
, false_stack
);
365 DIMPLIED("filtering false stack.\n");
366 *false_states
= filter_stack(pre_list
, true_stack
);
367 free_stack(&true_stack
);
368 free_stack(&false_stack
);
369 if (option_debug_implied
|| option_debug
) {
370 printf("These are the implied states for the true path:\n");
371 __print_slist(*true_states
);
372 printf("These are the implied states for the false path:\n");
373 __print_slist(*false_states
);
376 gettimeofday(&time_after
, NULL
);
377 if (time_after
.tv_sec
- time_before
.tv_sec
> 7)
378 __bail_on_rest_of_function
= 1;
381 static struct expression
*get_left_most_expr(struct expression
*expr
)
383 expr
= strip_expr(expr
);
384 if (expr
->type
== EXPR_ASSIGNMENT
)
385 return get_left_most_expr(expr
->left
);
389 static int is_merged_expr(struct expression
*expr
)
394 if (get_value(expr
, &dummy
))
396 sm
= get_sm_state_expr(SMATCH_EXTRA
, expr
);
404 static void delete_equiv_slist(struct state_list
**slist
, const char *name
, struct symbol
*sym
)
406 struct smatch_state
*state
;
407 struct relation
*rel
;
409 state
= get_state(SMATCH_EXTRA
, name
, sym
);
410 if (!estate_related(state
)) {
411 delete_state_slist(slist
, SMATCH_EXTRA
, name
, sym
);
415 FOR_EACH_PTR(estate_related(state
), rel
) {
416 delete_state_slist(slist
, SMATCH_EXTRA
, rel
->name
, rel
->sym
);
417 } END_FOR_EACH_PTR(rel
);
420 static void handle_comparison(struct expression
*expr
,
421 struct state_list
**implied_true
,
422 struct state_list
**implied_false
)
424 struct sm_state
*sm
= NULL
;
425 struct range_list
*ranges
= NULL
;
426 struct expression
*left
;
427 struct expression
*right
;
430 left
= get_left_most_expr(expr
->left
);
431 right
= get_left_most_expr(expr
->right
);
433 if (is_merged_expr(left
)) {
435 sm
= get_sm_state_expr(SMATCH_EXTRA
, left
);
436 get_implied_range_list(right
, &ranges
);
437 } else if (is_merged_expr(right
)) {
439 sm
= get_sm_state_expr(SMATCH_EXTRA
, right
);
440 get_implied_range_list(left
, &ranges
);
443 if (!ranges
|| !sm
) {
444 free_range_list(&ranges
);
448 separate_and_filter(sm
, expr
->op
, ranges
, lr
, __get_cur_slist(), implied_true
, implied_false
);
449 free_range_list(&ranges
);
450 delete_equiv_slist(implied_true
, sm
->name
, sm
->sym
);
451 delete_equiv_slist(implied_false
, sm
->name
, sm
->sym
);
454 static void handle_zero_comparison(struct expression
*expr
,
455 struct state_list
**implied_true
,
456 struct state_list
**implied_false
)
462 if (expr
->type
== EXPR_POSTOP
)
463 expr
= strip_expr(expr
->unop
);
465 if (expr
->type
== EXPR_ASSIGNMENT
) {
466 /* most of the time ->pools will be empty here because we
467 just set the state, but if have assigned a conditional
468 function there are implications. */
472 name
= get_variable_from_expr(expr
, &sym
);
475 sm
= get_sm_state(SMATCH_EXTRA
, name
, sym
);
479 separate_and_filter(sm
, SPECIAL_NOTEQUAL
, tmp_range_list(0), LEFT
, __get_cur_slist(), implied_true
, implied_false
);
480 delete_equiv_slist(implied_true
, name
, sym
);
481 delete_equiv_slist(implied_false
, name
, sym
);
486 static void get_tf_states(struct expression
*expr
,
487 struct state_list
**implied_true
,
488 struct state_list
**implied_false
)
490 if (expr
->type
== EXPR_COMPARE
)
491 handle_comparison(expr
, implied_true
, implied_false
);
493 handle_zero_comparison(expr
, implied_true
, implied_false
);
496 static void implied_states_hook(struct expression
*expr
)
499 struct state_list
*implied_true
= NULL
;
500 struct state_list
*implied_false
= NULL
;
502 if (option_no_implied
)
505 get_tf_states(expr
, &implied_true
, &implied_false
);
507 FOR_EACH_PTR(implied_true
, sm
) {
508 __set_true_false_sm(sm
, NULL
);
509 } END_FOR_EACH_PTR(sm
);
510 free_slist(&implied_true
);
512 FOR_EACH_PTR(implied_false
, sm
) {
513 __set_true_false_sm(NULL
, sm
);
514 } END_FOR_EACH_PTR(sm
);
515 free_slist(&implied_false
);
518 struct range_list
*__get_implied_values(struct expression
*switch_expr
)
522 struct smatch_state
*state
;
523 struct range_list
*ret
= NULL
;
525 name
= get_variable_from_expr(switch_expr
, &sym
);
528 state
= get_state(SMATCH_EXTRA
, name
, sym
);
531 ret
= clone_range_list(estate_ranges(state
));
535 add_range(&ret
, whole_range
.min
, whole_range
.max
);
539 struct state_list
*__implied_case_slist(struct expression
*switch_expr
,
540 struct expression
*case_expr
,
541 struct range_list_stack
**remaining_cases
,
542 struct state_list
**raw_slist
)
547 struct sm_state
*true_sm
;
548 struct state_list
*true_states
= NULL
;
549 struct state_list
*false_states
= NULL
;
550 struct state_list
*ret
= clone_slist(*raw_slist
);
552 struct range_list
*vals
= NULL
;
554 name
= get_variable_from_expr(switch_expr
, &sym
);
557 sm
= get_sm_state_slist(*raw_slist
, SMATCH_EXTRA
, name
, sym
);
559 vals
= top_range_list(*remaining_cases
);
561 if (!get_value(case_expr
, &val
))
564 filter_top_range_list(remaining_cases
, val
);
565 add_range(&vals
, val
, val
);
568 separate_and_filter(sm
, SPECIAL_EQUAL
, vals
, LEFT
, *raw_slist
, &true_states
, &false_states
);
570 true_sm
= get_sm_state_slist(true_states
, SMATCH_EXTRA
, name
, sym
);
572 set_state_slist(&true_states
, SMATCH_EXTRA
, name
, sym
, alloc_estate_range_list(vals
));
573 overwrite_slist(true_states
, &ret
);
574 free_slist(&true_states
);
575 free_slist(&false_states
);
581 static void match_end_func(struct symbol
*sym
)
583 implied_debug_msg
= NULL
;
587 * get_implications() can be called by check_ scripts.
589 void get_implications(char *name
, struct symbol
*sym
, int comparison
, long long num
,
590 struct state_list
**true_states
,
591 struct state_list
**false_states
)
595 sm
= get_sm_state(SMATCH_EXTRA
, name
, sym
);
598 if (slist_has_state(sm
->possible
, &undefined
))
600 separate_and_filter(sm
, comparison
, tmp_range_list(num
), LEFT
, __get_cur_slist(), true_states
, false_states
);
603 void __extra_match_condition(struct expression
*expr
);
604 void register_implications(int id
)
606 add_hook(&implied_states_hook
, CONDITION_HOOK
);
607 add_hook(&__extra_match_condition
, CONDITION_HOOK
);
608 add_hook(&match_end_func
, END_FUNC_HOOK
);