2 * Copyright (C) 2006 Dan Carpenter.
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License
6 * as published by the Free Software Foundation; either version 2
7 * of the License, or (at your option) any later version.
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
19 * You have a lists of states. kernel = locked, foo = NULL, ...
20 * When you hit an if {} else {} statement then you swap the list
21 * of states for a different list of states. The lists are stored
24 * At the beginning of this file there are list of the stacks that
25 * we use. Each function in this file does something to one of
28 * So the smatch_flow.c understands code but it doesn't understand states.
29 * smatch_flow calls functions in this file. This file calls functions
30 * in smatch_slist.c which just has boring generic plumbing for handling
31 * state lists. But really it's this file where all the magic happens.
37 #include "smatch_slist.h"
38 #include "smatch_extra.h"
40 struct smatch_state undefined
= { .name
= "undefined" };
41 struct smatch_state ghost
= { .name
= "ghost" };
42 struct smatch_state merged
= { .name
= "merged" };
43 struct smatch_state true_state
= { .name
= "true" };
44 struct smatch_state false_state
= { .name
= "false" };
46 static struct stree
*cur_stree
; /* current states */
47 static struct stree
*fast_overlay
;
49 static struct stree_stack
*true_stack
; /* states after a t/f branch */
50 static struct stree_stack
*false_stack
;
51 static struct stree_stack
*pre_cond_stack
; /* states before a t/f branch */
53 static struct stree_stack
*cond_true_stack
; /* states affected by a branch */
54 static struct stree_stack
*cond_false_stack
;
56 static struct stree_stack
*fake_cur_stree_stack
;
59 static struct stree_stack
*break_stack
;
60 static struct stree_stack
*fake_break_stack
;
61 static struct stree_stack
*switch_stack
;
62 static struct range_list_stack
*remaining_cases
;
63 static struct stree_stack
*default_stack
;
64 static struct stree_stack
*continue_stack
;
66 static struct named_stree_stack
*goto_stack
;
68 static struct ptr_list
*backup
;
72 void __print_cur_stree(void)
74 __print_stree(cur_stree
);
77 bool __print_states(const char *owner
)
85 FOR_EACH_SM(__get_cur_stree(), sm
) {
86 if (!strstr(check_name(sm
->owner
), owner
))
88 sm_msg("%s", show_sm(sm
));
90 } END_FOR_EACH_SM(sm
);
102 void __set_cur_stree_readonly(void)
107 void __set_cur_stree_writable(void)
112 DECLARE_PTR_LIST(check_tracker_list
, check_tracker_hook
*);
113 static struct check_tracker_list
**tracker_hooks
;
115 void add_check_tracker(const char *check_name
, check_tracker_hook
*fn
)
117 check_tracker_hook
**p
;
120 owner
= id_from_name(check_name
);
122 printf("check not found. '%s'\n", check_name
);
126 p
= malloc(sizeof(check_tracker_hook
*));
128 add_ptr_list(&tracker_hooks
[owner
], p
);
131 static void call_tracker_hooks(int owner
, const char *name
, struct symbol
*sym
, struct smatch_state
*state
)
133 struct check_tracker_list
*hooks
;
134 check_tracker_hook
**fn
;
136 if ((unsigned short)owner
== USHRT_MAX
)
139 hooks
= tracker_hooks
[owner
];
140 FOR_EACH_PTR(hooks
, fn
) {
141 (*fn
)(owner
, name
, sym
, state
);
142 } END_FOR_EACH_PTR(fn
);
145 void allocate_tracker_array(int num_checks
)
147 tracker_hooks
= malloc(num_checks
* sizeof(void *));
148 memset(tracker_hooks
, 0, num_checks
* sizeof(void *));
151 bool debug_on(const char *check_name
, const char *var
)
155 if (option_debug_check
&& strstr(check_name
, option_debug_check
))
157 if (option_debug_var
&& strcmp(var
, option_debug_var
) == 0)
162 struct sm_state
*set_state(int owner
, const char *name
, struct symbol
*sym
, struct smatch_state
*state
)
164 struct sm_state
*ret
;
170 sm_perror("cur_stree is read only.");
172 if (debug_on(check_name(owner
), name
)) {
173 struct smatch_state
*s
;
175 s
= __get_state(owner
, name
, sym
);
177 sm_msg("%s new [%s] '%s' %s", __func__
,
178 check_name(owner
), name
, show_state(state
));
180 sm_msg("%s change [%s] '%s' %s => %s",
181 __func__
, check_name(owner
), name
, show_state(s
),
185 call_tracker_hooks(owner
, name
, sym
, state
);
187 if (owner
!= -1 && unreachable())
190 if (fake_cur_stree_stack
)
191 set_state_stree_stack(&fake_cur_stree_stack
, owner
, name
, sym
, state
);
193 ret
= set_state_stree(&cur_stree
, owner
, name
, sym
, state
);
198 struct sm_state
*set_state_expr(int owner
, struct expression
*expr
, struct smatch_state
*state
)
202 struct sm_state
*ret
= NULL
;
204 expr
= strip_expr(expr
);
205 name
= expr_to_var_sym(expr
, &sym
);
208 ret
= set_state(owner
, name
, sym
, state
);
214 struct stree
*__swap_cur_stree(struct stree
*stree
)
216 struct stree
*orig
= cur_stree
;
222 void __push_fake_cur_stree(void)
224 push_stree(&fake_cur_stree_stack
, NULL
);
225 __save_pre_cond_states();
228 struct stree
*__pop_fake_cur_stree(void)
230 if (!fake_cur_stree_stack
)
231 sm_perror("popping too many fake cur strees.");
232 __use_pre_cond_states();
233 return pop_stree(&fake_cur_stree_stack
);
236 void __free_fake_cur_stree(void)
240 stree
= __pop_fake_cur_stree();
244 void __set_fake_cur_stree_fast(struct stree
*stree
)
247 sm_perror("cannot nest fast overlay");
250 fast_overlay
= stree
;
251 set_fast_math_only();
254 void __pop_fake_cur_stree_fast(void)
257 clear_fast_math_only();
260 void __merge_stree_into_cur(struct stree
*stree
)
263 struct sm_state
*orig
;
264 struct sm_state
*merged
;
266 FOR_EACH_SM(stree
, sm
) {
267 orig
= get_sm_state(sm
->owner
, sm
->name
, sm
->sym
);
269 merged
= merge_sm_states(orig
, sm
);
273 } END_FOR_EACH_SM(sm
);
276 void __set_sm(struct sm_state
*sm
)
279 sm_perror("cur_stree is read only.");
281 if (debug_on(check_name(sm
->owner
), sm
->name
)) {
282 struct smatch_state
*s
;
284 s
= __get_state(sm
->owner
, sm
->name
, sm
->sym
);
286 sm_msg("%s new %s", __func__
, show_sm(sm
));
288 sm_msg("%s change %s (was %s)", __func__
, show_sm(sm
),
295 if (fake_cur_stree_stack
)
296 overwrite_sm_state_stree_stack(&fake_cur_stree_stack
, sm
);
298 overwrite_sm_state_stree(&cur_stree
, sm
);
301 void __set_sm_cur_stree(struct sm_state
*sm
)
304 sm_perror("cur_stree is read only.");
306 if (debug_on(check_name(sm
->owner
), sm
->name
)) {
307 struct smatch_state
*s
;
309 s
= __get_state(sm
->owner
, sm
->name
, sm
->sym
);
311 sm_msg("%s new %s", __func__
, show_sm(sm
));
313 sm_msg("%s change %s (was %s)",
314 __func__
, show_sm(sm
), show_state(s
));
320 overwrite_sm_state_stree(&cur_stree
, sm
);
323 void __set_sm_fake_stree(struct sm_state
*sm
)
326 sm_perror("cur_stree is read only.");
328 if (debug_on(check_name(sm
->owner
), sm
->name
)) {
329 struct smatch_state
*s
;
331 s
= __get_state(sm
->owner
, sm
->name
, sm
->sym
);
333 sm_msg("%s new %s", __func__
, show_sm(sm
));
335 sm_msg("%s change %s (was %s)",
336 __func__
, show_sm(sm
), show_state(s
));
342 overwrite_sm_state_stree_stack(&fake_cur_stree_stack
, sm
);
346 typedef void (get_state_hook
)(int owner
, const char *name
, struct symbol
*sym
);
347 DECLARE_PTR_LIST(fn_list
, get_state_hook
*);
348 static struct fn_list
*get_state_hooks
;
350 void add_get_state_hook(get_state_hook
*fn
)
352 get_state_hook
**p
= malloc(sizeof(get_state_hook
*));
354 add_ptr_list(&get_state_hooks
, p
);
357 static void call_get_state_hooks(int owner
, const char *name
, struct symbol
*sym
)
359 static int recursion
;
366 FOR_EACH_PTR(get_state_hooks
, fn
) {
367 (*fn
)(owner
, name
, sym
);
368 } END_FOR_EACH_PTR(fn
);
373 bool has_states(int owner
)
375 if (owner
< 0 || owner
>= USHRT_MAX
)
379 return cur_stree
->has_states
[owner
];
382 struct smatch_state
*__get_state(int owner
, const char *name
, struct symbol
*sym
)
386 sm
= get_sm_state(owner
, name
, sym
);
392 struct smatch_state
*get_state(int owner
, const char *name
, struct symbol
*sym
)
394 call_get_state_hooks(owner
, name
, sym
);
396 return __get_state(owner
, name
, sym
);
399 struct smatch_state
*get_state_expr(int owner
, struct expression
*expr
)
401 struct expression
*fake_parent
;
404 struct smatch_state
*ret
= NULL
;
406 expr
= strip_expr(expr
);
407 name
= expr_to_var_sym(expr
, &sym
);
408 if ((!name
|| !sym
) && cur_func_sym
&& !cur_func_sym
->parsed
) {
409 fake_parent
= expr_get_fake_parent_expr(expr
);
412 name
= expr_to_var_sym(fake_parent
->left
, &sym
);
416 ret
= get_state(owner
, name
, sym
);
422 struct state_list
*get_possible_states(int owner
, const char *name
, struct symbol
*sym
)
424 struct sm_state
*sms
;
426 sms
= get_sm_state_stree(cur_stree
, owner
, name
, sym
);
428 return sms
->possible
;
432 struct state_list
*get_possible_states_expr(int owner
, struct expression
*expr
)
436 struct state_list
*ret
= NULL
;
438 expr
= strip_expr(expr
);
439 name
= expr_to_var_sym(expr
, &sym
);
442 ret
= get_possible_states(owner
, name
, sym
);
448 struct sm_state
*get_sm_state(int owner
, const char *name
, struct symbol
*sym
)
450 struct sm_state
*ret
;
452 ret
= get_sm_state_stree(fast_overlay
, owner
, name
, sym
);
456 return get_sm_state_stree(cur_stree
, owner
, name
, sym
);
459 struct sm_state
*get_sm_state_expr(int owner
, struct expression
*expr
)
463 struct sm_state
*ret
= NULL
;
465 expr
= strip_expr(expr
);
466 name
= expr_to_var_sym(expr
, &sym
);
469 ret
= get_sm_state(owner
, name
, sym
);
475 void delete_state(int owner
, const char *name
, struct symbol
*sym
)
477 delete_state_stree(&cur_stree
, owner
, name
, sym
);
478 if (cond_true_stack
) {
479 delete_state_stree_stack(&pre_cond_stack
, owner
, name
, sym
);
480 delete_state_stree_stack(&cond_true_stack
, owner
, name
, sym
);
481 delete_state_stree_stack(&cond_false_stack
, owner
, name
, sym
);
485 void delete_state_expr(int owner
, struct expression
*expr
)
490 expr
= strip_expr(expr
);
491 name
= expr_to_var_sym(expr
, &sym
);
494 delete_state(owner
, name
, sym
);
499 static void delete_all_states_stree_sym(struct stree
**stree
, struct symbol
*sym
)
501 struct state_list
*slist
= NULL
;
504 FOR_EACH_SM(*stree
, sm
) {
506 add_ptr_list(&slist
, sm
);
507 } END_FOR_EACH_SM(sm
);
509 FOR_EACH_PTR(slist
, sm
) {
510 delete_state_stree(stree
, sm
->owner
, sm
->name
, sm
->sym
);
511 } END_FOR_EACH_PTR(sm
);
516 static void delete_all_states_stree_stack_sym(struct stree_stack
**stack
, struct symbol
*sym
)
523 stree
= pop_stree(stack
);
524 delete_all_states_stree_sym(&stree
, sym
);
525 push_stree(stack
, stree
);
528 void __delete_all_states_sym(struct symbol
*sym
)
530 delete_all_states_stree_sym(&cur_stree
, sym
);
532 delete_all_states_stree_stack_sym(&true_stack
, sym
);
533 delete_all_states_stree_stack_sym(&true_stack
, sym
);
534 delete_all_states_stree_stack_sym(&false_stack
, sym
);
535 delete_all_states_stree_stack_sym(&pre_cond_stack
, sym
);
536 delete_all_states_stree_stack_sym(&cond_true_stack
, sym
);
537 delete_all_states_stree_stack_sym(&cond_false_stack
, sym
);
538 delete_all_states_stree_stack_sym(&fake_cur_stree_stack
, sym
);
539 delete_all_states_stree_stack_sym(&break_stack
, sym
);
540 delete_all_states_stree_stack_sym(&fake_break_stack
, sym
);
541 delete_all_states_stree_stack_sym(&switch_stack
, sym
);
542 delete_all_states_stree_stack_sym(&continue_stack
, sym
);
545 * deleting from the goto stack is problematic because we don't know
546 * if the label is in scope and also we need the value for --two-passes.
550 struct stree
*get_all_states_from_stree(int owner
, struct stree
*source
)
552 struct stree
*ret
= NULL
;
553 struct sm_state
*tmp
;
555 FOR_EACH_SM(source
, tmp
) {
556 if (tmp
->owner
== owner
)
557 avl_insert(&ret
, tmp
);
558 } END_FOR_EACH_SM(tmp
);
563 struct stree
*get_all_states_stree(int owner
)
565 return get_all_states_from_stree(owner
, cur_stree
);
568 struct stree
*__get_cur_stree(void)
573 int is_reachable(void)
580 void set_true_false_states(int owner
, const char *name
, struct symbol
*sym
,
581 struct smatch_state
*true_state
,
582 struct smatch_state
*false_state
)
585 sm_perror("cur_stree is read only.");
587 if (debug_on(check_name(owner
), name
)) {
588 struct smatch_state
*tmp
;
590 tmp
= __get_state(owner
, name
, sym
);
591 sm_msg("%s [%s] '%s'. Was %s. Now T:%s F:%s", __func__
,
592 check_name(owner
), name
, show_state(tmp
),
593 show_state(true_state
), show_state(false_state
));
599 if (!cond_false_stack
|| !cond_true_stack
) {
600 sm_perror("missing true/false stacks");
605 set_state_stree_stack(&cond_true_stack
, owner
, name
, sym
, true_state
);
607 set_state_stree_stack(&cond_false_stack
, owner
, name
, sym
, false_state
);
610 void set_true_false_states_expr(int owner
, struct expression
*expr
,
611 struct smatch_state
*true_state
,
612 struct smatch_state
*false_state
)
617 expr
= strip_expr(expr
);
618 name
= expr_to_var_sym(expr
, &sym
);
621 set_true_false_states(owner
, name
, sym
, true_state
, false_state
);
626 void __set_true_false_sm(struct sm_state
*true_sm
, struct sm_state
*false_sm
)
632 if (!true_sm
&& !false_sm
)
638 owner
= true_sm
? true_sm
->owner
: false_sm
->owner
;
639 name
= true_sm
? true_sm
->name
: false_sm
->name
;
640 sym
= true_sm
? true_sm
->sym
: false_sm
->sym
;
641 if (debug_on(check_name(owner
), name
)) {
642 struct smatch_state
*tmp
;
644 tmp
= __get_state(owner
, name
, sym
);
645 sm_msg("%s [%s] '%s'. Was %s. Now T:%s F:%s", __func__
,
646 check_name(owner
), name
, show_state(tmp
),
647 show_state(true_sm
? true_sm
->state
: NULL
),
648 show_state(false_sm
? false_sm
->state
: NULL
));
651 if (!cond_false_stack
|| !cond_true_stack
) {
652 sm_perror("missing true/false stacks");
657 overwrite_sm_state_stree_stack(&cond_true_stack
, true_sm
);
659 overwrite_sm_state_stree_stack(&cond_false_stack
, false_sm
);
662 void nullify_path(void)
664 if (fake_cur_stree_stack
) {
665 __free_fake_cur_stree();
666 __push_fake_cur_stree();
668 free_stree(&cur_stree
);
671 void __match_nullify_path_hook(const char *fn
, struct expression
*expr
,
678 * At the start of every function we mark the path
679 * as unnull. That way there is always at least one state
680 * in the cur_stree until nullify_path is called. This
681 * is used in merge_slist() for the first null check.
683 void __unnullify_path(void)
686 set_state(-1, "unnull_path", NULL
, &true_state
);
689 int __path_is_null(void)
696 static void check_stree_stack_free(struct stree_stack
**stack
)
699 sm_perror("stack not empty");
700 free_stack_and_strees(stack
);
704 void save_all_states(void)
706 __add_ptr_list(&backup
, cur_stree
);
709 __add_ptr_list(&backup
, true_stack
);
711 __add_ptr_list(&backup
, false_stack
);
713 __add_ptr_list(&backup
, pre_cond_stack
);
714 pre_cond_stack
= NULL
;
716 __add_ptr_list(&backup
, cond_true_stack
);
717 cond_true_stack
= NULL
;
718 __add_ptr_list(&backup
, cond_false_stack
);
719 cond_false_stack
= NULL
;
721 __add_ptr_list(&backup
, fake_cur_stree_stack
);
722 fake_cur_stree_stack
= NULL
;
724 __add_ptr_list(&backup
, break_stack
);
726 __add_ptr_list(&backup
, fake_break_stack
);
727 fake_break_stack
= NULL
;
729 __add_ptr_list(&backup
, switch_stack
);
731 __add_ptr_list(&backup
, remaining_cases
);
732 remaining_cases
= NULL
;
733 __add_ptr_list(&backup
, default_stack
);
734 default_stack
= NULL
;
735 __add_ptr_list(&backup
, continue_stack
);
736 continue_stack
= NULL
;
738 __add_ptr_list(&backup
, goto_stack
);
742 static void *pop_backup(void)
746 ret
= last_ptr_list(backup
);
747 delete_ptr_list_last(&backup
);
751 void restore_all_states(void)
753 goto_stack
= pop_backup();
755 continue_stack
= pop_backup();
756 default_stack
= pop_backup();
757 remaining_cases
= pop_backup();
758 switch_stack
= pop_backup();
759 fake_break_stack
= pop_backup();
760 break_stack
= pop_backup();
762 fake_cur_stree_stack
= pop_backup();
764 cond_false_stack
= pop_backup();
765 cond_true_stack
= pop_backup();
767 pre_cond_stack
= pop_backup();
768 false_stack
= pop_backup();
769 true_stack
= pop_backup();
771 cur_stree
= pop_backup();
774 void free_goto_stack(void)
776 struct named_stree
*named_stree
;
778 FOR_EACH_PTR(goto_stack
, named_stree
) {
779 free_stree(&named_stree
->stree
);
780 } END_FOR_EACH_PTR(named_stree
);
781 __free_ptr_list((struct ptr_list
**)&goto_stack
);
784 void clear_all_states(void)
787 check_stree_stack_free(&true_stack
);
788 check_stree_stack_free(&false_stack
);
789 check_stree_stack_free(&pre_cond_stack
);
790 check_stree_stack_free(&cond_true_stack
);
791 check_stree_stack_free(&cond_false_stack
);
792 check_stree_stack_free(&break_stack
);
793 check_stree_stack_free(&fake_break_stack
);
794 check_stree_stack_free(&switch_stack
);
795 check_stree_stack_free(&continue_stack
);
796 check_stree_stack_free(&fake_cur_stree_stack
);
800 free_every_single_sm_state();
801 free_tmp_expressions();
804 void __push_cond_stacks(void)
806 push_stree(&cond_true_stack
, NULL
);
807 push_stree(&cond_false_stack
, NULL
);
808 __push_fake_cur_stree();
811 void __fold_in_set_states(void)
813 struct stree
*new_states
;
816 new_states
= __pop_fake_cur_stree();
817 FOR_EACH_SM(new_states
, sm
) {
819 __set_true_false_sm(sm
, sm
);
820 } END_FOR_EACH_SM(sm
);
821 free_stree(&new_states
);
824 void __free_set_states(void)
826 struct stree
*new_states
;
828 new_states
= __pop_fake_cur_stree();
829 free_stree(&new_states
);
832 struct stree
*__copy_cond_true_states(void)
836 ret
= pop_stree(&cond_true_stack
);
837 push_stree(&cond_true_stack
, clone_stree(ret
));
841 struct stree
*__copy_cond_false_states(void)
845 ret
= pop_stree(&cond_false_stack
);
846 push_stree(&cond_false_stack
, clone_stree(ret
));
850 struct stree
*__pop_cond_true_stack(void)
852 return pop_stree(&cond_true_stack
);
855 struct stree
*__pop_cond_false_stack(void)
857 return pop_stree(&cond_false_stack
);
861 * This combines the pre cond states with either the true or false states.
863 * a = kmalloc() ; if (a !! foo(a)
864 * In the pre state a is possibly null. In the true state it is non null.
865 * In the false state it is null. Combine the pre and the false to get
866 * that when we call 'foo', 'a' is null.
868 static void __use_cond_stack(struct stree_stack
**stack
)
872 free_stree(&cur_stree
);
874 cur_stree
= pop_stree(&pre_cond_stack
);
875 push_stree(&pre_cond_stack
, clone_stree(cur_stree
));
877 stree
= pop_stree(stack
);
878 overwrite_stree(stree
, &cur_stree
);
879 push_stree(stack
, stree
);
882 void __use_pre_cond_states(void)
884 free_stree(&cur_stree
);
885 cur_stree
= pop_stree(&pre_cond_stack
);
888 void __use_cond_true_states(void)
890 __use_cond_stack(&cond_true_stack
);
893 void __use_cond_false_states(void)
895 __use_cond_stack(&cond_false_stack
);
898 void __negate_cond_stacks(void)
900 struct stree
*old_false
, *old_true
;
902 old_false
= pop_stree(&cond_false_stack
);
903 old_true
= pop_stree(&cond_true_stack
);
904 push_stree(&cond_false_stack
, old_true
);
905 push_stree(&cond_true_stack
, old_false
);
908 void __and_cond_states(void)
910 and_stree_stack(&cond_true_stack
);
911 or_stree_stack(&pre_cond_stack
, cur_stree
, &cond_false_stack
);
914 void __or_cond_states(void)
916 or_stree_stack(&pre_cond_stack
, cur_stree
, &cond_true_stack
);
917 and_stree_stack(&cond_false_stack
);
920 void __save_pre_cond_states(void)
922 push_stree(&pre_cond_stack
, clone_stree(cur_stree
));
925 void __discard_pre_cond_states(void)
929 tmp
= pop_stree(&pre_cond_stack
);
933 struct stree
*__get_true_states(void)
935 return clone_stree(top_stree(cond_true_stack
));
938 struct stree
*__get_false_states(void)
940 return clone_stree(top_stree(cond_false_stack
));
943 void __use_cond_states(void)
945 struct stree
*pre
, *pre_clone
, *true_states
, *false_states
;
947 pre
= pop_stree(&pre_cond_stack
);
948 pre_clone
= clone_stree(pre
);
950 true_states
= pop_stree(&cond_true_stack
);
951 overwrite_stree(true_states
, &pre
);
952 free_stree(&true_states
);
953 /* we use the true states right away */
954 free_stree(&cur_stree
);
957 false_states
= pop_stree(&cond_false_stack
);
958 overwrite_stree(false_states
, &pre_clone
);
959 free_stree(&false_states
);
960 push_stree(&false_stack
, pre_clone
);
963 void __push_true_states(void)
965 push_stree(&true_stack
, clone_stree(cur_stree
));
968 void __use_false_states(void)
970 free_stree(&cur_stree
);
971 cur_stree
= pop_stree(&false_stack
);
974 void __discard_false_states(void)
978 stree
= pop_stree(&false_stack
);
982 void __merge_false_states(void)
986 stree
= pop_stree(&false_stack
);
987 merge_stree(&cur_stree
, stree
);
992 * This function probably seemed common sensical when I wrote it but, oh wow,
993 * does it look subtle in retrospect. Say we set a state on one side of the if
994 * else path but not on the other, then what we should record in the fake stree
995 * is the merged state.
997 * This function relies on the fact that the we always set the cur_stree as well
998 * and we already have the infrastructure to merge things correctly into the
1001 * So instead of merging fake strees together which is probably a lot of work,
1002 * we just use it as a list of set states and look up the actual current values
1006 static void update_stree_with_merged(struct stree
**stree
)
1008 struct state_list
*slist
= NULL
;
1009 struct sm_state
*sm
, *new;
1011 FOR_EACH_SM(*stree
, sm
) {
1012 new = get_sm_state(sm
->owner
, sm
->name
, sm
->sym
);
1013 if (!new) /* This can happen if we go out of scope */
1015 add_ptr_list(&slist
, new);
1016 } END_FOR_EACH_SM(sm
);
1018 FOR_EACH_PTR(slist
, sm
) {
1019 overwrite_sm_state_stree(stree
, sm
);
1020 } END_FOR_EACH_PTR(sm
);
1025 static void update_fake_stree_with_merged(void)
1027 struct stree
*stree
;
1029 if (!fake_cur_stree_stack
)
1031 stree
= pop_stree(&fake_cur_stree_stack
);
1032 update_stree_with_merged(&stree
);
1033 push_stree(&fake_cur_stree_stack
, stree
);
1036 void __merge_true_states(void)
1038 struct stree
*stree
;
1040 stree
= pop_stree(&true_stack
);
1041 merge_stree(&cur_stree
, stree
);
1042 update_fake_stree_with_merged();
1046 void __push_continues(void)
1048 push_stree(&continue_stack
, NULL
);
1051 void __discard_continues(void)
1053 struct stree
*stree
;
1055 stree
= pop_stree(&continue_stack
);
1059 void __process_continues(void)
1061 struct stree
*stree
;
1063 stree
= pop_stree(&continue_stack
);
1065 stree
= clone_stree(cur_stree
);
1067 merge_stree(&stree
, cur_stree
);
1069 push_stree(&continue_stack
, stree
);
1072 void __merge_continues(void)
1074 struct stree
*stree
;
1076 stree
= pop_stree(&continue_stack
);
1077 merge_stree(&cur_stree
, stree
);
1081 void __push_breaks(void)
1083 push_stree(&break_stack
, NULL
);
1084 if (fake_cur_stree_stack
)
1085 push_stree(&fake_break_stack
, NULL
);
1088 void __process_breaks(void)
1090 struct stree
*stree
;
1092 stree
= pop_stree(&break_stack
);
1094 stree
= clone_stree(cur_stree
);
1096 merge_stree(&stree
, cur_stree
);
1097 push_stree(&break_stack
, stree
);
1099 if (!fake_cur_stree_stack
)
1102 stree
= pop_stree(&fake_break_stack
);
1104 stree
= clone_stree(top_stree(fake_cur_stree_stack
));
1106 merge_stree(&stree
, top_stree(fake_cur_stree_stack
));
1107 push_stree(&fake_break_stack
, stree
);
1110 int __has_breaks(void)
1112 struct stree
*stree
;
1115 stree
= pop_stree(&break_stack
);
1117 push_stree(&break_stack
, stree
);
1121 void __merge_breaks(void)
1123 struct stree
*stree
;
1124 struct sm_state
*sm
;
1126 stree
= pop_stree(&break_stack
);
1127 merge_stree(&cur_stree
, stree
);
1130 if (!fake_cur_stree_stack
)
1133 stree
= pop_stree(&fake_break_stack
);
1134 update_stree_with_merged(&stree
);
1135 FOR_EACH_SM(stree
, sm
) {
1136 overwrite_sm_state_stree_stack(&fake_cur_stree_stack
, sm
);
1137 } END_FOR_EACH_SM(sm
);
1141 void __use_breaks(void)
1143 struct stree
*stree
;
1144 struct sm_state
*sm
;
1146 free_stree(&cur_stree
);
1147 cur_stree
= pop_stree(&break_stack
);
1149 if (!fake_cur_stree_stack
)
1151 stree
= pop_stree(&fake_break_stack
);
1152 FOR_EACH_SM(stree
, sm
) {
1153 overwrite_sm_state_stree_stack(&fake_cur_stree_stack
, sm
);
1154 } END_FOR_EACH_SM(sm
);
1160 void __save_switch_states(struct expression
*switch_expr
)
1162 struct range_list
*rl
;
1164 get_absolute_rl(switch_expr
, &rl
);
1166 push_rl(&remaining_cases
, rl
);
1167 push_stree(&switch_stack
, clone_stree(cur_stree
));
1170 int have_remaining_cases(void)
1172 return !!top_rl(remaining_cases
);
1175 void __merge_switches(struct expression
*switch_expr
, struct range_list
*case_rl
)
1177 struct stree
*stree
;
1178 struct stree
*implied_stree
;
1180 stree
= pop_stree(&switch_stack
);
1183 * If the cur_stree was NULL before the start of the switch
1184 * statement then we don't want to unnullify it.
1187 push_stree(&switch_stack
, stree
);
1190 implied_stree
= __implied_case_stree(switch_expr
, case_rl
, &remaining_cases
, &stree
);
1191 merge_stree(&cur_stree
, implied_stree
);
1192 free_stree(&implied_stree
);
1193 push_stree(&switch_stack
, stree
);
1196 void __discard_switches(void)
1198 struct stree
*stree
;
1200 pop_rl(&remaining_cases
);
1201 stree
= pop_stree(&switch_stack
);
1205 void __push_default(void)
1207 push_stree(&default_stack
, NULL
);
1210 void __set_default(void)
1212 set_state_stree_stack(&default_stack
, 0, "has_default", NULL
, &true_state
);
1215 int __pop_default(void)
1217 struct stree
*stree
;
1219 stree
= pop_stree(&default_stack
);
1227 static struct named_stree
*alloc_named_stree(const char *name
, struct symbol
*sym
, struct stree
*stree
)
1229 struct named_stree
*named_stree
= __alloc_named_stree(0);
1231 named_stree
->name
= (char *)name
;
1232 named_stree
->stree
= stree
;
1233 named_stree
->sym
= sym
;
1237 void __save_gotos(const char *name
, struct symbol
*sym
)
1239 struct stree
**stree
;
1240 struct stree
*clone
;
1242 stree
= get_named_stree(goto_stack
, name
, sym
);
1244 merge_stree(stree
, cur_stree
);
1247 struct named_stree
*named_stree
;
1249 clone
= clone_stree(cur_stree
);
1250 named_stree
= alloc_named_stree(name
, sym
, clone
);
1251 add_ptr_list(&goto_stack
, named_stree
);
1255 void __merge_gotos(const char *name
, struct symbol
*sym
)
1257 struct stree
**stree
;
1259 stree
= get_named_stree(goto_stack
, name
, sym
);
1261 merge_stree(&cur_stree
, *stree
);
1264 void __discard_fake_states(struct expression
*call
)
1266 struct stree
*new = NULL
;
1267 struct sm_state
*sm
;
1271 if (__fake_state_cnt
== 0)
1275 * This is just a best effort type of thing. There could be
1276 * fake states in the true/false trees already. They might
1277 * eventually get cleared out too because we call after probably
1278 * 50% of function calls. But the point is that I don't want to
1279 * waste resources tracking them.
1281 FOR_EACH_SM(cur_stree
, sm
) {
1283 len
= snprintf(buf
, sizeof(buf
), "__fake_param_%p_", call
);
1284 if (strncmp(sm
->name
, buf
, len
) != 0)
1285 avl_insert(&new, sm
);
1288 if (strncmp(sm
->name
, "__fake_param_", 13) != 0)
1289 avl_insert(&new, sm
);
1290 } END_FOR_EACH_SM(sm
);
1292 free_stree(&cur_stree
);
1294 __fake_state_cnt
= 0;