41 * When it comes to the if (foo == 99) the smatch implied hook
42 * looks for all the pools where foo was not 99. It makes a list
43 * of those.
44 *
45 * Then for bar (and all the other states) it says, ok bar is a
46 * merged state that came from these previous states. We'll
47 * chop out all the states where it came from a pool where
48 * foo != 99 and merge it all back together.
49 *
50 * That is the implied state of bar.
51 *
52 * merge_slist() sets up ->pool. An sm_state only has one ->pool and
53 * that is the pool where it was first set. The my pool gets set when
54 * code paths merge. States that have been set since the last merge do
55 * not have a ->pool.
56 * merge_sm_state() sets ->left and ->right. (These are the states which were
57 * merged to form the current state.)
58 * a pool: a pool is an slist that has been merged with another slist.
59 */
60
61 #include <sys/time.h>
62 #include <time.h>
63 #include "smatch.h"
64 #include "smatch_slist.h"
65 #include "smatch_extra.h"
66
67 char *implied_debug_msg;
68
69 bool implications_off;
70
71 #define implied_debug 0
72 #define DIMPLIED(msg...) do { if (implied_debug) printf(msg); } while (0)
73
74 /*
75 * tmp_range_list():
76 * It messes things up to free range list allocations. This helper fuction
77 * lets us reuse memory instead of doing new allocations.
78 */
79 static struct range_list *tmp_range_list(struct symbol *type, long long num)
80 {
81 static struct range_list *my_list = NULL;
82 static struct data_range *my_range;
83
84 __free_ptr_list((struct ptr_list **)&my_list);
85 my_range = alloc_range(ll_to_sval(num), ll_to_sval(num));
86 add_ptr_list(&my_list, my_range);
87 return my_list;
88 }
89
90 static void print_debug_tf(struct sm_state *sm, int istrue, int isfalse)
91 {
92 if (!implied_debug && !option_debug)
93 return;
281 return 0;
282 }
283
284 /*
285 * separate_pools():
286 * Example code: if (foo == 99) {
287 *
288 * Say 'foo' is a merged state that has many possible values. It is the combination
289 * of merges. separate_pools() iterates through the pools recursively and calls
290 * do_compare() for each time 'foo' was set.
291 */
292 static void __separate_pools(struct sm_state *sm, int comparison, struct range_list *rl,
293 struct state_list **true_stack,
294 struct state_list **maybe_stack,
295 struct state_list **false_stack,
296 struct state_list **checked, int *mixed, struct sm_state *gate_sm,
297 struct timeval *start_time)
298 {
299 int free_checked = 0;
300 struct state_list *checked_states = NULL;
301 struct timeval now;
302
303 if (!sm)
304 return;
305
306 gettimeofday(&now, NULL);
307 if (now.tv_usec - start_time->tv_usec > 1000000) {
308 if (implied_debug) {
309 sm_msg("debug: %s: implications taking too long. (%s %s %s)",
310 __func__, sm->state->name, show_special(comparison), show_rl(rl));
311 }
312 if (mixed)
313 *mixed = 1;
314 }
315
316 if (checked == NULL) {
317 checked = &checked_states;
318 free_checked = 1;
319 }
320 if (is_checked(*checked, sm))
321 return;
322 add_ptr_list(checked, sm);
323
324 do_compare(sm, comparison, rl, true_stack, maybe_stack, false_stack, mixed, gate_sm);
325
326 __separate_pools(sm->left, comparison, rl, true_stack, maybe_stack, false_stack, checked, mixed, gate_sm, start_time);
327 __separate_pools(sm->right, comparison, rl, true_stack, maybe_stack, false_stack, checked, mixed, gate_sm, start_time);
434 }
435
436 /*
437 * NOTE: If a state is in both the keep stack and the remove stack then that is
438 * a bug. Only add states which are definitely true or definitely false. If
439 * you have a leaf state that could be both true and false, then create a fake
440 * split history where one side is true and one side is false. Otherwise, if
441 * you can't do that, then don't add it to either list.
442 */
443 #define RECURSE_LIMIT 300
444 struct sm_state *filter_pools(struct sm_state *sm,
445 const struct state_list *remove_stack,
446 const struct state_list *keep_stack,
447 int *modified, int *recurse_cnt,
448 struct timeval *start, int *skip, int *bail)
449 {
450 struct sm_state *ret = NULL;
451 struct sm_state *left;
452 struct sm_state *right;
453 int removed = 0;
454 struct timeval now;
455
456 if (!sm)
457 return NULL;
458 if (*bail)
459 return NULL;
460 gettimeofday(&now, NULL);
461 if (now.tv_usec - start->tv_usec > 3000000) {
462 DIMPLIED("%s: implications taking too long: %s\n", __func__, sm_state_info(sm));
463 *bail = 1;
464 return NULL;
465 }
466 if ((*recurse_cnt)++ > RECURSE_LIMIT) {
467 DIMPLIED("%s: recursed too far: %s\n", __func__, sm_state_info(sm));
468 *skip = 1;
469 return NULL;
470 }
471
472 if (pool_in_pools(sm->pool, remove_stack)) {
473 DIMPLIED("%s: remove: %s\n", __func__, sm_state_info(sm));
474 *modified = 1;
475 return NULL;
476 }
477
478 if (!is_merged(sm) || pool_in_pools(sm->pool, keep_stack) || sm_in_keep_leafs(sm, keep_stack)) {
479 DIMPLIED("%s: keep %s (%s, %s, %s): %s\n", __func__, sm->state->name,
480 is_merged(sm) ? "merged" : "not merged",
481 pool_in_pools(sm->pool, keep_stack) ? "not in keep pools" : "in keep pools",
582 int sec;
583
584 gettimeofday(&time_before, NULL);
585
586 DIMPLIED("checking implications: (%s (%s) %s %s)\n",
587 sm->name, sm->state->name, show_special(comparison), show_rl(rl));
588
589 if (!is_merged(sm)) {
590 DIMPLIED("%d '%s' from line %d is not merged.\n", get_lineno(), sm->name, sm->line);
591 return;
592 }
593
594 separate_pools(sm, comparison, rl, &true_stack, &false_stack, NULL, mixed);
595
596 DIMPLIED("filtering true stack.\n");
597 *true_states = filter_stack(sm, pre_stree, false_stack, true_stack);
598 DIMPLIED("filtering false stack.\n");
599 *false_states = filter_stack(sm, pre_stree, true_stack, false_stack);
600 free_slist(&true_stack);
601 free_slist(&false_stack);
602 if (implied_debug) {
603 printf("These are the implied states for the true path: (%s (%s) %s %s)\n",
604 sm->name, sm->state->name, show_special(comparison), show_rl(rl));
605 __print_stree(*true_states);
606 printf("These are the implied states for the false path: (%s (%s) %s %s)\n",
607 sm->name, sm->state->name, show_special(comparison), show_rl(rl));
608 __print_stree(*false_states);
609 }
610
611 gettimeofday(&time_after, NULL);
612 sec = time_after.tv_sec - time_before.tv_sec;
613 if (option_timeout && sec > option_timeout) {
614 sm_perror("Function too hairy. Ignoring implications after %d seconds.", sec);
615 }
616 }
617
618 static struct expression *get_last_expr(struct statement *stmt)
619 {
620 struct statement *last;
621
622 last = last_ptr_list((struct ptr_list *)stmt->stmts);
623 if (last->type == STMT_EXPRESSION)
624 return last->expression;
625
626 if (last->type == STMT_LABEL) {
627 if (last->label_statement &&
628 last->label_statement->type == STMT_EXPRESSION)
629 return last->label_statement->expression;
780 sm = comparison_implication_hook(expr, &true_stack, &false_stack);
781 if (!sm)
782 return 0;
783
784 pre_stree = clone_stree(__get_cur_stree());
785
786 *implied_true = filter_stack(sm, pre_stree, false_stack, true_stack);
787 *implied_false = filter_stack(sm, pre_stree, true_stack, false_stack);
788
789 free_stree(&pre_stree);
790 free_slist(&true_stack);
791 free_slist(&false_stack);
792
793 return 1;
794 }
795
796 static int handled_by_extra_states(struct expression *expr,
797 struct stree **implied_true,
798 struct stree **implied_false)
799 {
800 if (expr->type == EXPR_COMPARE)
801 return handle_comparison(expr, implied_true, implied_false);
802 else
803 return handle_zero_comparison(expr, implied_true, implied_false);
804 }
805
806 static int handled_by_stored_conditions(struct expression *expr,
807 struct stree **implied_true,
808 struct stree **implied_false)
809 {
810 struct state_list *true_stack = NULL;
811 struct state_list *false_stack = NULL;
812 struct stree *pre_stree;
813 struct sm_state *sm;
814
815 sm = stored_condition_implication_hook(expr, &true_stack, &false_stack);
816 if (!sm)
817 return 0;
818
819 pre_stree = clone_stree(__get_cur_stree());
866 if (handled_by_extra_states(expr, implied_true, implied_false)) {
867 separate_extra_states(implied_true, implied_false);
868 return;
869 }
870
871 if (handled_by_stored_conditions(expr, implied_true, implied_false))
872 return;
873 }
874
875 static void save_implications_hook(struct expression *expr)
876 {
877 if (going_too_slow())
878 return;
879 get_tf_states(expr, &saved_implied_true, &saved_implied_false);
880 }
881
882 static void set_implied_states(struct expression *expr)
883 {
884 struct sm_state *sm;
885
886 FOR_EACH_SM(saved_implied_true, sm) {
887 __set_true_false_sm(sm, NULL);
888 } END_FOR_EACH_SM(sm);
889 free_stree(&saved_implied_true);
890
891 FOR_EACH_SM(saved_implied_false, sm) {
892 __set_true_false_sm(NULL, sm);
893 } END_FOR_EACH_SM(sm);
894 free_stree(&saved_implied_false);
895 }
896
897 static void set_extra_implied_states(struct expression *expr)
898 {
899 saved_implied_true = extra_saved_implied_true;
900 saved_implied_false = extra_saved_implied_false;
901 extra_saved_implied_true = NULL;
902 extra_saved_implied_false = NULL;
903 set_implied_states(NULL);
904 }
905
|
41 * When it comes to the if (foo == 99) the smatch implied hook
42 * looks for all the pools where foo was not 99. It makes a list
43 * of those.
44 *
45 * Then for bar (and all the other states) it says, ok bar is a
46 * merged state that came from these previous states. We'll
47 * chop out all the states where it came from a pool where
48 * foo != 99 and merge it all back together.
49 *
50 * That is the implied state of bar.
51 *
52 * merge_slist() sets up ->pool. An sm_state only has one ->pool and
53 * that is the pool where it was first set. The my pool gets set when
54 * code paths merge. States that have been set since the last merge do
55 * not have a ->pool.
56 * merge_sm_state() sets ->left and ->right. (These are the states which were
57 * merged to form the current state.)
58 * a pool: a pool is an slist that has been merged with another slist.
59 */
60
61 #include <time.h>
62 #include "smatch.h"
63 #include "smatch_slist.h"
64 #include "smatch_extra.h"
65
66 char *implied_debug_msg;
67
68 bool implications_off;
69
70 #define implied_debug 0
71 #define DIMPLIED(msg...) do { if (implied_debug) printf(msg); } while (0)
72
73 bool debug_implied(void)
74 {
75 return implied_debug;
76 }
77
78 /*
79 * tmp_range_list():
80 * It messes things up to free range list allocations. This helper fuction
81 * lets us reuse memory instead of doing new allocations.
82 */
83 static struct range_list *tmp_range_list(struct symbol *type, long long num)
84 {
85 static struct range_list *my_list = NULL;
86 static struct data_range *my_range;
87
88 __free_ptr_list((struct ptr_list **)&my_list);
89 my_range = alloc_range(ll_to_sval(num), ll_to_sval(num));
90 add_ptr_list(&my_list, my_range);
91 return my_list;
92 }
93
94 static void print_debug_tf(struct sm_state *sm, int istrue, int isfalse)
95 {
96 if (!implied_debug && !option_debug)
97 return;
285 return 0;
286 }
287
288 /*
289 * separate_pools():
290 * Example code: if (foo == 99) {
291 *
292 * Say 'foo' is a merged state that has many possible values. It is the combination
293 * of merges. separate_pools() iterates through the pools recursively and calls
294 * do_compare() for each time 'foo' was set.
295 */
296 static void __separate_pools(struct sm_state *sm, int comparison, struct range_list *rl,
297 struct state_list **true_stack,
298 struct state_list **maybe_stack,
299 struct state_list **false_stack,
300 struct state_list **checked, int *mixed, struct sm_state *gate_sm,
301 struct timeval *start_time)
302 {
303 int free_checked = 0;
304 struct state_list *checked_states = NULL;
305 struct timeval now, diff;
306
307 if (!sm)
308 return;
309
310 gettimeofday(&now, NULL);
311 timersub(&now, start_time, &diff);
312 if (diff.tv_sec >= 1) {
313 if (implied_debug) {
314 sm_msg("debug: %s: implications taking too long. (%s %s %s)",
315 __func__, sm->state->name, show_special(comparison), show_rl(rl));
316 }
317 if (mixed)
318 *mixed = 1;
319 }
320
321 if (checked == NULL) {
322 checked = &checked_states;
323 free_checked = 1;
324 }
325 if (is_checked(*checked, sm))
326 return;
327 add_ptr_list(checked, sm);
328
329 do_compare(sm, comparison, rl, true_stack, maybe_stack, false_stack, mixed, gate_sm);
330
331 __separate_pools(sm->left, comparison, rl, true_stack, maybe_stack, false_stack, checked, mixed, gate_sm, start_time);
332 __separate_pools(sm->right, comparison, rl, true_stack, maybe_stack, false_stack, checked, mixed, gate_sm, start_time);
439 }
440
441 /*
442 * NOTE: If a state is in both the keep stack and the remove stack then that is
443 * a bug. Only add states which are definitely true or definitely false. If
444 * you have a leaf state that could be both true and false, then create a fake
445 * split history where one side is true and one side is false. Otherwise, if
446 * you can't do that, then don't add it to either list.
447 */
448 #define RECURSE_LIMIT 300
449 struct sm_state *filter_pools(struct sm_state *sm,
450 const struct state_list *remove_stack,
451 const struct state_list *keep_stack,
452 int *modified, int *recurse_cnt,
453 struct timeval *start, int *skip, int *bail)
454 {
455 struct sm_state *ret = NULL;
456 struct sm_state *left;
457 struct sm_state *right;
458 int removed = 0;
459 struct timeval now, diff;
460
461 if (!sm)
462 return NULL;
463 if (*bail)
464 return NULL;
465 gettimeofday(&now, NULL);
466 timersub(&now, start, &diff);
467 if (diff.tv_sec >= 3) {
468 DIMPLIED("%s: implications taking too long: %s\n", __func__, sm_state_info(sm));
469 *bail = 1;
470 return NULL;
471 }
472 if ((*recurse_cnt)++ > RECURSE_LIMIT) {
473 DIMPLIED("%s: recursed too far: %s\n", __func__, sm_state_info(sm));
474 *skip = 1;
475 return NULL;
476 }
477
478 if (pool_in_pools(sm->pool, remove_stack)) {
479 DIMPLIED("%s: remove: %s\n", __func__, sm_state_info(sm));
480 *modified = 1;
481 return NULL;
482 }
483
484 if (!is_merged(sm) || pool_in_pools(sm->pool, keep_stack) || sm_in_keep_leafs(sm, keep_stack)) {
485 DIMPLIED("%s: keep %s (%s, %s, %s): %s\n", __func__, sm->state->name,
486 is_merged(sm) ? "merged" : "not merged",
487 pool_in_pools(sm->pool, keep_stack) ? "not in keep pools" : "in keep pools",
588 int sec;
589
590 gettimeofday(&time_before, NULL);
591
592 DIMPLIED("checking implications: (%s (%s) %s %s)\n",
593 sm->name, sm->state->name, show_special(comparison), show_rl(rl));
594
595 if (!is_merged(sm)) {
596 DIMPLIED("%d '%s' from line %d is not merged.\n", get_lineno(), sm->name, sm->line);
597 return;
598 }
599
600 separate_pools(sm, comparison, rl, &true_stack, &false_stack, NULL, mixed);
601
602 DIMPLIED("filtering true stack.\n");
603 *true_states = filter_stack(sm, pre_stree, false_stack, true_stack);
604 DIMPLIED("filtering false stack.\n");
605 *false_states = filter_stack(sm, pre_stree, true_stack, false_stack);
606 free_slist(&true_stack);
607 free_slist(&false_stack);
608
609 gettimeofday(&time_after, NULL);
610 sec = time_after.tv_sec - time_before.tv_sec;
611 if (option_timeout && sec > option_timeout) {
612 sm_perror("Function too hairy. Ignoring implications after %d seconds.", sec);
613 }
614 }
615
616 static struct expression *get_last_expr(struct statement *stmt)
617 {
618 struct statement *last;
619
620 last = last_ptr_list((struct ptr_list *)stmt->stmts);
621 if (last->type == STMT_EXPRESSION)
622 return last->expression;
623
624 if (last->type == STMT_LABEL) {
625 if (last->label_statement &&
626 last->label_statement->type == STMT_EXPRESSION)
627 return last->label_statement->expression;
778 sm = comparison_implication_hook(expr, &true_stack, &false_stack);
779 if (!sm)
780 return 0;
781
782 pre_stree = clone_stree(__get_cur_stree());
783
784 *implied_true = filter_stack(sm, pre_stree, false_stack, true_stack);
785 *implied_false = filter_stack(sm, pre_stree, true_stack, false_stack);
786
787 free_stree(&pre_stree);
788 free_slist(&true_stack);
789 free_slist(&false_stack);
790
791 return 1;
792 }
793
794 static int handled_by_extra_states(struct expression *expr,
795 struct stree **implied_true,
796 struct stree **implied_false)
797 {
798 sval_t sval;
799
800 /* If the expression is known then it has no implications. */
801 if (get_implied_value(expr, &sval))
802 return true;
803
804 if (expr->type == EXPR_COMPARE)
805 return handle_comparison(expr, implied_true, implied_false);
806 else
807 return handle_zero_comparison(expr, implied_true, implied_false);
808 }
809
810 static int handled_by_stored_conditions(struct expression *expr,
811 struct stree **implied_true,
812 struct stree **implied_false)
813 {
814 struct state_list *true_stack = NULL;
815 struct state_list *false_stack = NULL;
816 struct stree *pre_stree;
817 struct sm_state *sm;
818
819 sm = stored_condition_implication_hook(expr, &true_stack, &false_stack);
820 if (!sm)
821 return 0;
822
823 pre_stree = clone_stree(__get_cur_stree());
870 if (handled_by_extra_states(expr, implied_true, implied_false)) {
871 separate_extra_states(implied_true, implied_false);
872 return;
873 }
874
875 if (handled_by_stored_conditions(expr, implied_true, implied_false))
876 return;
877 }
878
879 static void save_implications_hook(struct expression *expr)
880 {
881 if (going_too_slow())
882 return;
883 get_tf_states(expr, &saved_implied_true, &saved_implied_false);
884 }
885
886 static void set_implied_states(struct expression *expr)
887 {
888 struct sm_state *sm;
889
890 if (implied_debug &&
891 (expr || saved_implied_true || saved_implied_false)) {
892 char *name;
893
894 name = expr_to_str(expr);
895 printf("These are the implied states for the true path: (%s)\n", name);
896 __print_stree(saved_implied_true);
897 printf("These are the implied states for the false path: (%s)\n", name);
898 __print_stree(saved_implied_false);
899 free_string(name);
900 }
901
902 FOR_EACH_SM(saved_implied_true, sm) {
903 __set_true_false_sm(sm, NULL);
904 } END_FOR_EACH_SM(sm);
905 free_stree(&saved_implied_true);
906
907 FOR_EACH_SM(saved_implied_false, sm) {
908 __set_true_false_sm(NULL, sm);
909 } END_FOR_EACH_SM(sm);
910 free_stree(&saved_implied_false);
911 }
912
913 static void set_extra_implied_states(struct expression *expr)
914 {
915 saved_implied_true = extra_saved_implied_true;
916 saved_implied_false = extra_saved_implied_false;
917 extra_saved_implied_true = NULL;
918 extra_saved_implied_false = NULL;
919 set_implied_states(NULL);
920 }
921
|