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 pools_overlap(struct state_list_stack
*pools1
,
60 struct state_list_stack
*pools2
)
62 struct state_list
*one
;
63 struct state_list
*two
;
65 PREPARE_PTR_LIST(pools1
, one
);
66 PREPARE_PTR_LIST(pools2
, two
);
73 } else if (one
== two
) {
84 struct sm_state
*remove_my_pools(struct sm_state
*sm
,
85 struct state_list_stack
*pools
, int *modified
)
87 struct sm_state
*ret
= NULL
;
89 struct sm_state
*tmp_keep
;
90 struct state_list
*keep
= NULL
;
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
);
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
);
107 add_ptr_list(&keep
, tmp_keep
);
108 } END_FOR_EACH_PTR(pre
);
110 DIMPLIED("kept %s = %s from %d\n", sm
->name
, show_state(sm
->state
), sm
->line
);
115 DIMPLIED("removed %s = %s from %d\n", sm
->name
, show_state(sm
->state
), sm
->line
);
119 FOR_EACH_PTR(keep
, tmp_keep
) {
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
);
129 DIMPLIED("kept %s = %s from %d\n", sm
->name
, show_state(sm
->state
),
134 static struct state_list
*filter_stack(struct state_list
*pre_list
,
135 struct state_list_stack
*stack
)
137 struct state_list
*ret
= NULL
;
138 struct sm_state
*tmp
;
139 struct sm_state
*filtered_state
;
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
);
153 static void separate_pools(struct sm_state
*sm_state
, int comparison
, int num
,
155 struct state_list_stack
**true_stack
,
156 struct state_list_stack
**false_stack
)
158 struct state_list
*list
;
162 FOR_EACH_PTR(sm_state
->my_pools
, list
) {
163 s
= get_sm_state_slist(list
, sm_state
->name
, sm_state
->owner
,
165 istrue
= !possibly_false(comparison
,
166 (struct data_info
*)s
->state
->data
, num
,
168 isfalse
= !possibly_true(comparison
,
169 (struct data_info
*)s
->state
->data
,
171 if (debug_implied_states
|| debug_states
) {
172 if (istrue
&& isfalse
) {
173 printf("'%s = %s' from %d does not exist.\n",
174 s
->name
, show_state(s
->state
),
177 printf("'%s = %s' from %d is true. %p\n",
178 s
->name
, show_state(s
->state
),
180 } else if (isfalse
) {
181 printf("'%s = %s' from %d is false. %p\n",
182 s
->name
, show_state(s
->state
),
185 printf("'%s = %s' from %d could be true or "
187 show_state(s
->state
), s
->line
);
191 add_pool(true_stack
, list
);
194 add_pool(false_stack
, list
);
196 } END_FOR_EACH_PTR(list
);
197 FOR_EACH_PTR(sm_state
->pre_merge
, s
) {
198 separate_pools(s
, comparison
, num
, left
, true_stack
, false_stack
);
199 } END_FOR_EACH_PTR(s
);
202 static void get_eq_neq(struct sm_state
*sm_state
, int comparison
, int num
,
204 struct state_list
*pre_list
,
205 struct state_list
**true_states
,
206 struct state_list
**false_states
)
208 struct state_list_stack
*true_stack
= NULL
;
209 struct state_list_stack
*false_stack
= NULL
;
211 if (debug_implied_states
|| debug_states
) {
213 smatch_msg("checking implications: (%s %s %d)",
214 sm_state
->name
, show_special(comparison
), num
);
216 smatch_msg("checking implications: (%d %s %s)",
217 num
, show_special(comparison
), sm_state
->name
);
220 separate_pools(sm_state
, comparison
, num
, left
, &true_stack
, &false_stack
);
222 DIMPLIED("filtering true stack.\n");
223 *true_states
= filter_stack(pre_list
, false_stack
);
224 DIMPLIED("filtering false stack.\n");
225 *false_states
= filter_stack(pre_list
, true_stack
);
226 free_stack(&true_stack
);
227 free_stack(&false_stack
);
228 if (debug_implied_states
|| debug_states
) {
229 printf("These are the implied states for the true path:\n");
230 __print_slist(*true_states
);
231 printf("These are the implied states for the false path:\n");
232 __print_slist(*false_states
);
236 static char *get_implication_variable(struct expression
*expr
, struct symbol
**symp
)
238 expr
= strip_expr(expr
);
239 if (expr
->type
== EXPR_ASSIGNMENT
)
240 return get_implication_variable(expr
->left
, symp
);
241 return get_variable_from_expr(expr
, symp
);
244 static void handle_comparison(struct expression
*expr
,
245 struct state_list
**implied_true
,
246 struct state_list
**implied_false
)
250 struct sm_state
*state
;
254 value
= get_value(expr
->left
);
255 if (value
== UNDEFINED
) {
256 value
= get_value(expr
->right
);
257 if (value
== UNDEFINED
)
262 name
= get_implication_variable(expr
->left
, &sym
);
264 name
= get_implication_variable(expr
->right
, &sym
);
267 state
= get_sm_state(name
, SMATCH_EXTRA
, sym
);
270 if (!is_merged(state
)) {
271 DIMPLIED("%d '%s' is not merged.\n", get_lineno(), state
->name
);
274 get_eq_neq(state
, expr
->op
, value
, left
, __get_cur_slist(), implied_true
, implied_false
);
275 delete_state_slist(implied_true
, name
, SMATCH_EXTRA
, sym
);
276 delete_state_slist(implied_false
, name
, SMATCH_EXTRA
, sym
);
281 static void get_tf_states(struct expression
*expr
,
282 struct state_list
**implied_true
,
283 struct state_list
**implied_false
)
287 struct sm_state
*state
;
289 if (expr
->type
== EXPR_COMPARE
) {
290 handle_comparison(expr
, implied_true
, implied_false
);
293 if (expr
->type
== EXPR_ASSIGNMENT
) {
294 /* most of the time ->my_pools will be empty here because we
295 just set the state, but if have assigned a conditional
296 function there are implications. */
300 name
= get_variable_from_expr(expr
, &sym
);
303 state
= get_sm_state(name
, SMATCH_EXTRA
, sym
);
306 if (!is_merged(state
)) {
307 DIMPLIED("%d '%s' has no pools.\n", get_lineno(), state
->name
);
310 get_eq_neq(state
, SPECIAL_NOTEQUAL
, 0, 1, __get_cur_slist(), implied_true
, implied_false
);
311 delete_state_slist(implied_true
, name
, SMATCH_EXTRA
, sym
);
312 delete_state_slist(implied_false
, name
, SMATCH_EXTRA
, sym
);
317 static void implied_states_hook(struct expression
*expr
)
319 struct sm_state
*state
;
320 struct sm_state
*clone
;
321 struct state_list
*implied_true
= NULL
;
322 struct state_list
*implied_false
= NULL
;
324 if (option_no_implied
)
327 get_tf_states(expr
, &implied_true
, &implied_false
);
329 FOR_EACH_PTR(implied_true
, state
) {
330 clone
= clone_state(state
);
331 __set_true_false_sm(clone
, NULL
);
332 } END_FOR_EACH_PTR(state
);
333 free_slist(&implied_true
);
335 FOR_EACH_PTR(implied_false
, state
) {
336 clone
= clone_state(state
);
337 __set_true_false_sm(NULL
, clone
);
338 } END_FOR_EACH_PTR(state
);
339 free_slist(&implied_false
);
342 void get_implications(char *name
, struct symbol
*sym
, int comparison
, int num
,
343 struct state_list
**true_states
,
344 struct state_list
**false_states
)
348 sm
= get_sm_state(name
, SMATCH_EXTRA
, sym
);
351 if (slist_has_state(sm
->possible
, &undefined
))
353 get_eq_neq(sm
, comparison
, num
, 1, __get_cur_slist(), true_states
, false_states
);
356 struct state_list
*__implied_case_slist(struct expression
*switch_expr
,
357 struct expression
*case_expr
,
358 struct state_list
**raw_slist
)
363 struct sm_state
*true_sm
;
364 struct sm_state
*false_sm
;
365 struct state_list
*true_states
= NULL
;
366 struct state_list
*false_states
= NULL
;
367 struct state_list
*ret
= clone_slist(*raw_slist
);
372 name
= get_variable_from_expr(switch_expr
, &sym
);
375 sm
= get_sm_state_slist(*raw_slist
, name
, SMATCH_EXTRA
, sym
);
376 val
= get_value(case_expr
);
377 if (val
== UNDEFINED
)
380 get_eq_neq(sm
, SPECIAL_EQUAL
, val
, 1, *raw_slist
, &true_states
, &false_states
);
383 true_sm
= get_sm_state_slist(true_states
, name
, SMATCH_EXTRA
, sym
);
385 set_state_slist(&true_states
, name
, SMATCH_EXTRA
, sym
, alloc_extra_state(val
));
386 false_sm
= get_sm_state_slist(false_states
, name
, SMATCH_EXTRA
, sym
);
388 set_state_slist(&false_states
, name
, SMATCH_EXTRA
, sym
, add_filter(sm
?sm
->state
:NULL
, val
));
389 overwrite_slist(false_states
, raw_slist
);
390 overwrite_slist(true_states
, &ret
);
391 free_slist(&true_states
);
392 free_slist(&false_states
);
398 void __extra_match_condition(struct expression
*expr
);
399 void register_implications(int id
)
401 add_hook(&implied_states_hook
, CONDITION_HOOK
);
402 add_hook(&__extra_match_condition
, CONDITION_HOOK
);