From 4eff961d813a5a087ece3bf0a728a23f50337a2a Mon Sep 17 00:00:00 2001 From: Dan Carpenter Date: Sat, 21 Mar 2009 14:19:27 +0300 Subject: [PATCH] core: improve anding condition handling. The handling of merged states was obviously wrong before and so this is an improvement. It's a bit tricky because sometimes mutually exclusive states are legit. if (!foo && !(foo = kmalloc())) { Sometimes when it complains about mutually exclusive states that really does mean a condition is always false. We set a lot of states all the time because of implications. I may remove the "mutually exclusive" print statement again. Signed-off-by: Dan Carpenter --- smatch_implied.c | 39 +++++++++----------- smatch_slist.c | 108 ++++++++++++++++++++++++++++++++++++++++++++----------- 2 files changed, 104 insertions(+), 43 deletions(-) diff --git a/smatch_implied.c b/smatch_implied.c index 90bcc4a8..9ccac41a 100644 --- a/smatch_implied.c +++ b/smatch_implied.c @@ -209,15 +209,22 @@ static struct state_list *filter_stack(struct state_list_stack *stack) return ret; } +static int is_true(int comparison, int num, int var, int left) +{ + if (left) + return true_comparison(var, comparison, num); + else + return true_comparison(num, comparison, var); +} + static void get_eq_neq(struct sm_state *sm_state, int comparison, int num, int left, struct state_list **true_states, struct state_list **false_states) { struct state_list *list; - struct smatch_state *s; + struct sm_state *s; struct state_list_stack *true_stack = NULL; struct state_list_stack *false_stack = NULL; - int tf; if (left) DIMPLIED("checking implications: (%s %s %d)\n", sm_state->name, @@ -227,32 +234,20 @@ static void get_eq_neq(struct sm_state *sm_state, int comparison, int num, show_special(comparison), sm_state->name); FOR_EACH_PTR(sm_state->my_pools, list) { - s = get_state_slist(list, sm_state->name, sm_state->owner, + s = get_sm_state_slist(list, sm_state->name, sm_state->owner, sm_state->sym); - if (s == &merged) { - free_stack(&true_stack); - free_stack(&false_stack); - DIMPLIED("'%s' is merged.\n", sm_state->name); - return; - } - if (s == &undefined) { - DIMPLIED("'%s' from %d is undefined.\n", - sm_state->name, sm_state->line); - push_slist(&true_stack, list); + if (s->state == &undefined || s->state == &merged) { + DIMPLIED("'%s' from %d is %s.\n", s->name, s->line, + show_state(s->state)); push_slist(&false_stack, list); + push_slist(&true_stack, list); continue; } - if (left) - tf = true_comparison(*(int *)s->data, comparison, num); - else - tf = true_comparison(num, comparison, *(int *)s->data); - if (tf) { - DIMPLIED("'%s' from %d is true.\n", sm_state->name, - sm_state->line); + if (is_true(comparison, num, *(int *)s->state->data, left)) { + DIMPLIED("'%s' from %d is true.\n", s->name, s->line); push_slist(&true_stack, list); } else { - DIMPLIED("'%s' from %d is false.\n", sm_state->name, - sm_state->line); + DIMPLIED("'%s' from %d is false.\n", s->name, s->line); push_slist(&false_stack, list); } } END_FOR_EACH_PTR(list); diff --git a/smatch_slist.c b/smatch_slist.c index 4909014d..2fa20073 100644 --- a/smatch_slist.c +++ b/smatch_slist.c @@ -527,21 +527,34 @@ void set_state_stack(struct state_list_stack **stack, const char *name, } /* - * get_state_stack() gets the state for the top slist on the stack. + * get_sm_state_stack() gets the state for the top slist on the stack. */ -struct smatch_state *get_state_stack(struct state_list_stack *stack, - const char *name, int owner, - struct symbol *sym) +struct sm_state *get_sm_state_stack(struct state_list_stack *stack, + const char *name, int owner, + struct symbol *sym) { struct state_list *slist; - struct smatch_state *ret; + struct sm_state *ret; slist = pop_slist(&stack); - ret = get_state_slist(slist, name, owner, sym); + ret = get_sm_state_slist(slist, name, owner, sym); push_slist(&stack, slist); return ret; } + +struct smatch_state *get_state_stack(struct state_list_stack *stack, + const char *name, int owner, + struct symbol *sym) +{ + struct sm_state *state; + + state = get_sm_state_stack(stack, name, owner, sym); + if (state) + return state->state; + return NULL; +} + static void register_implied_pool(struct state_list *pool) { struct sm_state *sm; @@ -653,6 +666,64 @@ void merge_slist(struct state_list **to, struct state_list *slist) *to = results; } +static struct sm_state *find_intersection(struct sm_state *one, + struct sm_state *two) +{ + struct state_list *tmp1, *tmp2; + struct state_list_stack *stack = NULL; + struct sm_state *tmp_state; + struct sm_state *ret; + + if (!one) + return two; + if (one->state != &merged) { + if (one->state == two->state) + return one; + if (two->state != &merged) { + smatch_msg("mutually exclusive 'and' conditions states " + "'%s': %s + %s", one->name, + show_state(one->state), + show_state(two->state)); + return two; + } + } + + PREPARE_PTR_LIST(one->my_pools, tmp1); + PREPARE_PTR_LIST(two->my_pools, tmp2); + for (;;) { + if (!tmp1 && !tmp2) + break; + if (!tmp2 || (tmp1 && tmp1 < tmp2)) { + NEXT_PTR_LIST(tmp1); + } else if (tmp1 == tmp2) { + push_slist(&stack, tmp1); + NEXT_PTR_LIST(tmp1); + NEXT_PTR_LIST(tmp2); + } else { + NEXT_PTR_LIST(tmp2); + } + } + FINISH_PTR_LIST(tmp2); + FINISH_PTR_LIST(tmp1); + + if (!stack) { + smatch_msg("mutually eXclusive 'and' conditions states " + "'%s': %s + %s", one->name, show_state(one->state), + show_state(two->state)); + return two; + } + + ret = alloc_state(one->name, one->owner, one->sym, &merged); + FOR_EACH_PTR(stack, tmp1) { + tmp_state = get_sm_state_slist(tmp1, one->name, one->owner, + one->sym); + add_possible(ret, tmp_state); + } END_FOR_EACH_PTR(tmp1); + ret->my_pools = stack; + ret->all_pools = clone_stack(stack); + return ret; +} + /* * and_slist_stack() is basically the same as popping the top two slists, * overwriting the one with the other and pushing it back on the stack. @@ -663,22 +734,17 @@ void merge_slist(struct state_list **to, struct state_list *slist) void and_slist_stack(struct state_list_stack **slist_stack) { struct sm_state *tmp; - struct smatch_state *tmp_state; - struct state_list *tmp_slist = pop_slist(slist_stack); - - FOR_EACH_PTR(tmp_slist, tmp) { - tmp_state = get_state_stack(*slist_stack, tmp->name, - tmp->owner, tmp->sym); - if (tmp_state && tmp_state != tmp->state) { - SM_DEBUG("mutually exclusive 'and' conditions states " - "'%s': %s + %s", - tmp->name, show_state(tmp_state), - show_state(tmp->state)); - } - set_state_stack(slist_stack, tmp->name, tmp->owner, tmp->sym, - tmp->state); + struct sm_state *left_state; + struct sm_state *res; + struct state_list *right_slist = pop_slist(slist_stack); + + FOR_EACH_PTR(right_slist, tmp) { + left_state = get_sm_state_stack(*slist_stack, tmp->name, + tmp->owner, tmp->sym); + res = find_intersection(left_state, tmp); + overwrite_sm_state_stack(slist_stack, res); } END_FOR_EACH_PTR(tmp); - free_slist(&tmp_slist); + free_slist(&right_slist); } /* -- 2.11.4.GIT