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_pools
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_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.
53 #include "smatch_slist.h"
54 #include "smatch_extra.h"
56 int debug_implied_states
= 0;
57 int option_no_implied
= 0;
59 static int pool_in_pools(struct state_list
*pool
,
60 struct state_list_stack
*pools
)
62 struct state_list
*tmp
;
64 FOR_EACH_PTR(pools
, tmp
) {
69 } END_FOR_EACH_PTR(tmp
);
73 struct sm_state
*remove_my_pools(struct sm_state
*sm
,
74 struct state_list_stack
*pools
, int *modified
)
76 struct sm_state
*ret
= NULL
;
77 struct sm_state
*left
;
78 struct sm_state
*right
;
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
);
92 DIMPLIED("kept %s = %s from %d\n", sm
->name
, show_state(sm
->state
),
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
);
101 DIMPLIED("kept %s = %s from %d\n", sm
->name
, show_state(sm
->state
), sm
->line
);
105 if (!left
&& !right
) {
106 DIMPLIED("removed %s = %s from %d\n", sm
->name
, show_state(sm
->state
), sm
->line
);
111 ret
= clone_state(right
);
113 ret
->pre_right
= right
;
114 ret
->pre_left
= NULL
;
115 ret
->my_pool
= sm
->my_pool
;
117 ret
= clone_state(left
);
119 ret
->pre_left
= left
;
120 ret
->pre_right
= NULL
;
121 ret
->my_pool
= sm
->my_pool
;
123 ret
= merge_sm_states(left
, right
);
124 ret
->my_pool
= sm
->my_pool
;
126 DIMPLIED("partial %s = %s from %d\n", sm
->name
, show_state(sm
->state
), sm
->line
);
130 static struct state_list
*filter_stack(struct state_list
*pre_list
,
131 struct state_list_stack
*stack
)
133 struct state_list
*ret
= NULL
;
134 struct sm_state
*tmp
;
135 struct sm_state
*filtered_state
;
142 FOR_EACH_PTR(pre_list
, tmp
) {
144 filtered_state
= remove_my_pools(tmp
, stack
, &modified
);
145 if (filtered_state
&& modified
) {
146 add_ptr_list(&ret
, filtered_state
);
147 if ((counter
++)%10 && out_of_memory())
151 } END_FOR_EACH_PTR(tmp
);
155 static int is_checked(struct state_list
*checked
, struct sm_state
*sm
)
157 struct sm_state
*tmp
;
159 FOR_EACH_PTR(checked
, tmp
) {
162 } END_FOR_EACH_PTR(tmp
);
166 static void separate_pools(struct sm_state
*sm_state
, int comparison
, int num
,
168 struct state_list_stack
**true_stack
,
169 struct state_list_stack
**false_stack
,
170 struct state_list
**checked
)
174 int free_checked
= 0;
175 struct state_list
*checked_states
= NULL
;
181 if (checked
== NULL
) {
183 checked
= &checked_states
;
186 if (is_checked(*checked
, sm_state
)) {
189 add_ptr_list(checked
, sm_state
);
191 if (stopper
++ >= 500) {
192 smatch_msg("internal error: too much recursion going on here");
196 if (sm_state
->my_pool
) {
197 s
= get_sm_state_slist(sm_state
->my_pool
, sm_state
->name
, sm_state
->owner
,
200 istrue
= !possibly_false(comparison
,
201 (struct data_info
*)s
->state
->data
, num
,
203 isfalse
= !possibly_true(comparison
,
204 (struct data_info
*)s
->state
->data
,
207 if (debug_implied_states
|| debug_states
) {
208 if (istrue
&& isfalse
) {
209 printf("'%s = %s' from %d does not exist.\n",
210 s
->name
, show_state(s
->state
),
213 printf("'%s = %s' from %d is true.\n",
214 s
->name
, show_state(s
->state
),
216 } else if (isfalse
) {
217 printf("'%s = %s' from %d is false.\n",
218 s
->name
, show_state(s
->state
),
221 printf("'%s = %s' from %d could be true or "
223 show_state(s
->state
), s
->line
);
227 add_pool(true_stack
, s
->my_pool
);
230 add_pool(false_stack
, s
->my_pool
);
233 separate_pools(sm_state
->pre_left
, comparison
, num
, left
, true_stack
, false_stack
, checked
);
234 separate_pools(sm_state
->pre_right
, comparison
, num
, left
, true_stack
, false_stack
, checked
);
239 static void get_eq_neq(struct sm_state
*sm_state
, int comparison
, int num
,
241 struct state_list
*pre_list
,
242 struct state_list
**true_states
,
243 struct state_list
**false_states
)
245 struct state_list_stack
*true_stack
= NULL
;
246 struct state_list_stack
*false_stack
= NULL
;
248 if (debug_implied_states
|| debug_states
) {
250 smatch_msg("checking implications: (%s %s %d)",
251 sm_state
->name
, show_special(comparison
), num
);
253 smatch_msg("checking implications: (%d %s %s)",
254 num
, show_special(comparison
), sm_state
->name
);
257 separate_pools(sm_state
, comparison
, num
, left
, &true_stack
, &false_stack
, NULL
);
259 DIMPLIED("filtering true stack.\n");
260 *true_states
= filter_stack(pre_list
, false_stack
);
261 DIMPLIED("filtering false stack.\n");
262 *false_states
= filter_stack(pre_list
, true_stack
);
263 free_stack(&true_stack
);
264 free_stack(&false_stack
);
265 if (debug_implied_states
|| debug_states
) {
266 printf("These are the implied states for the true path:\n");
267 __print_slist(*true_states
);
268 printf("These are the implied states for the false path:\n");
269 __print_slist(*false_states
);
273 static char *get_implication_variable(struct expression
*expr
, struct symbol
**symp
)
275 expr
= strip_expr(expr
);
276 if (expr
->type
== EXPR_ASSIGNMENT
)
277 return get_implication_variable(expr
->left
, symp
);
278 return get_variable_from_expr(expr
, symp
);
281 static void handle_comparison(struct expression
*expr
,
282 struct state_list
**implied_true
,
283 struct state_list
**implied_false
)
287 struct sm_state
*state
;
291 value
= get_value(expr
->left
);
292 if (value
== UNDEFINED
) {
293 value
= get_value(expr
->right
);
294 if (value
== UNDEFINED
)
299 name
= get_implication_variable(expr
->left
, &sym
);
301 name
= get_implication_variable(expr
->right
, &sym
);
304 state
= get_sm_state(name
, SMATCH_EXTRA
, sym
);
307 if (!is_merged(state
)) {
308 DIMPLIED("%d '%s' is not merged.\n", get_lineno(), state
->name
);
311 get_eq_neq(state
, expr
->op
, value
, left
, __get_cur_slist(), implied_true
, implied_false
);
312 delete_state_slist(implied_true
, name
, SMATCH_EXTRA
, sym
);
313 delete_state_slist(implied_false
, name
, SMATCH_EXTRA
, sym
);
318 static void get_tf_states(struct expression
*expr
,
319 struct state_list
**implied_true
,
320 struct state_list
**implied_false
)
324 struct sm_state
*state
;
326 if (expr
->type
== EXPR_COMPARE
) {
327 handle_comparison(expr
, implied_true
, implied_false
);
330 if (expr
->type
== EXPR_ASSIGNMENT
) {
331 /* most of the time ->my_pools will be empty here because we
332 just set the state, but if have assigned a conditional
333 function there are implications. */
337 name
= get_variable_from_expr(expr
, &sym
);
340 state
= get_sm_state(name
, SMATCH_EXTRA
, sym
);
343 if (!is_merged(state
)) {
344 DIMPLIED("%d '%s' has no pools.\n", get_lineno(), state
->name
);
347 get_eq_neq(state
, SPECIAL_NOTEQUAL
, 0, 1, __get_cur_slist(), implied_true
, implied_false
);
348 delete_state_slist(implied_true
, name
, SMATCH_EXTRA
, sym
);
349 delete_state_slist(implied_false
, name
, SMATCH_EXTRA
, sym
);
354 static void implied_states_hook(struct expression
*expr
)
356 struct sm_state
*state
;
357 struct state_list
*implied_true
= NULL
;
358 struct state_list
*implied_false
= NULL
;
360 if (option_no_implied
)
363 get_tf_states(expr
, &implied_true
, &implied_false
);
365 FOR_EACH_PTR(implied_true
, state
) {
366 __set_true_false_sm(state
, NULL
);
367 } END_FOR_EACH_PTR(state
);
368 free_slist(&implied_true
);
370 FOR_EACH_PTR(implied_false
, state
) {
371 __set_true_false_sm(NULL
, state
);
372 } END_FOR_EACH_PTR(state
);
373 free_slist(&implied_false
);
376 void get_implications(char *name
, struct symbol
*sym
, int comparison
, int num
,
377 struct state_list
**true_states
,
378 struct state_list
**false_states
)
382 sm
= get_sm_state(name
, SMATCH_EXTRA
, sym
);
385 if (slist_has_state(sm
->possible
, &undefined
))
387 get_eq_neq(sm
, comparison
, num
, 1, __get_cur_slist(), true_states
, false_states
);
390 struct state_list
*__implied_case_slist(struct expression
*switch_expr
,
391 struct expression
*case_expr
,
392 struct state_list
**raw_slist
)
397 struct sm_state
*true_sm
;
398 struct sm_state
*false_sm
;
399 struct state_list
*true_states
= NULL
;
400 struct state_list
*false_states
= NULL
;
401 struct state_list
*ret
= clone_slist(*raw_slist
);
406 name
= get_variable_from_expr(switch_expr
, &sym
);
409 sm
= get_sm_state_slist(*raw_slist
, name
, SMATCH_EXTRA
, sym
);
410 val
= get_value(case_expr
);
411 if (val
== UNDEFINED
)
414 get_eq_neq(sm
, SPECIAL_EQUAL
, val
, 1, *raw_slist
, &true_states
, &false_states
);
417 true_sm
= get_sm_state_slist(true_states
, name
, SMATCH_EXTRA
, sym
);
419 set_state_slist(&true_states
, name
, SMATCH_EXTRA
, sym
, alloc_extra_state(val
));
420 false_sm
= get_sm_state_slist(false_states
, name
, SMATCH_EXTRA
, sym
);
422 set_state_slist(&false_states
, name
, SMATCH_EXTRA
, sym
, add_filter(sm
?sm
->state
:NULL
, val
));
423 overwrite_slist(false_states
, raw_slist
);
424 overwrite_slist(true_states
, &ret
);
425 free_slist(&true_states
);
426 free_slist(&false_states
);
432 void __extra_match_condition(struct expression
*expr
);
433 void register_implications(int id
)
435 add_hook(&implied_states_hook
, CONDITION_HOOK
);
436 add_hook(&__extra_match_condition
, CONDITION_HOOK
);