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
16 */
17
18 #include "symbol.h"
19 #include "smatch.h"
20 #include "smatch_slist.h"
21 #include "smatch_extra.h"
22
23 static bool get_rl_sval(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *sval_res);
24 static bool get_rl_internal(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res);
25 static bool handle_variable(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval);
26 static struct range_list *(*custom_handle_variable)(struct expression *expr);
27
28 static bool get_implied_value_internal(struct expression *expr, int *recurse_cnt, sval_t *res_sval);
29 static int get_absolute_rl_internal(struct expression *expr, struct range_list **rl, int *recurse_cnt);
30
31 static sval_t zero = {.type = &int_ctype, {.value = 0} };
32 static sval_t one = {.type = &int_ctype, {.value = 1} };
33
34 struct range_list *rl_zero(void)
35 {
36 static struct range_list *zero_perm;
37
38 if (!zero_perm)
39 zero_perm = clone_rl_permanent(alloc_rl(zero, zero));
40 return zero_perm;
41 }
42
43 struct range_list *rl_one(void)
44 {
45 static struct range_list *one_perm;
46
47 if (!one_perm)
48 one_perm = clone_rl_permanent(alloc_rl(one, one));
49
50 return one_perm;
51 }
52
53 enum {
839 int final_pass_orig = final_pass;
840
841 cond_true = expr->cond_true;
842 if (!cond_true)
843 cond_true = expr->conditional;
844
845 if (known_condition_true(expr->conditional))
846 return get_rl_sval(cond_true, implied, recurse_cnt, res, res_sval);
847 if (known_condition_false(expr->conditional))
848 return get_rl_sval(expr->cond_false, implied, recurse_cnt, res, res_sval);
849
850 if (implied == RL_EXACT)
851 return false;
852
853 if (implied_condition_true(expr->conditional))
854 return get_rl_sval(cond_true, implied, recurse_cnt, res, res_sval);
855 if (implied_condition_false(expr->conditional))
856 return get_rl_sval(expr->cond_false, implied, recurse_cnt, res, res_sval);
857
858 /* this becomes a problem with deeply nested conditional statements */
859 if (low_on_memory())
860 return false;
861
862 type = get_type(expr);
863
864 __push_fake_cur_stree();
865 final_pass = 0;
866 __split_whole_condition(expr->conditional);
867 true_rl = NULL;
868 get_rl_internal(cond_true, implied, recurse_cnt, &true_rl);
869 __push_true_states();
870 __use_false_states();
871 false_rl = NULL;
872 get_rl_internal(expr->cond_false, implied, recurse_cnt, &false_rl);
873 __merge_true_states();
874 __free_fake_cur_stree();
875 final_pass = final_pass_orig;
876
877 if (!true_rl || !false_rl)
878 return false;
879 true_rl = cast_rl(type, true_rl);
930 sym = expr->symbol;
931 if (!(sym->ctype.modifiers & MOD_CONST))
932 return 0;
933 if (get_value(sym->initializer, &right)) {
934 *sval = sval_cast(get_type(expr), right);
935 return 1;
936 }
937 return 0;
938 }
939
940 struct range_list *var_to_absolute_rl(struct expression *expr)
941 {
942 struct smatch_state *state;
943 struct range_list *rl;
944
945 state = get_extra_state(expr);
946 if (!state || is_whole_rl(estate_rl(state))) {
947 state = get_real_absolute_state(expr);
948 if (state && state->data && !estate_is_whole(state))
949 return clone_rl(estate_rl(state));
950 if (get_local_rl(expr, &rl) && !is_whole_rl(rl))
951 return rl;
952 if (get_mtag_rl(expr, &rl))
953 return rl;
954 if (get_db_type_rl(expr, &rl) && !is_whole_rl(rl))
955 return rl;
956 return alloc_whole_rl(get_type(expr));
957 }
958 /* err on the side of saying things are possible */
959 if (!estate_rl(state))
960 return alloc_whole_rl(get_type(expr));
961 return clone_rl(estate_rl(state));
962 }
963
964 static bool handle_variable(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
965 {
966 struct smatch_state *state;
967 struct range_list *rl;
968 sval_t sval, min, max;
969 struct symbol *type;
970
971 if (get_const_value(expr, &sval)) {
991 *res_sval = sval;
992 return true;
993 }
994
995 type = get_type(expr);
996 if (type &&
997 (type->type == SYM_ARRAY ||
998 type->type == SYM_FN))
999 return handle_address(expr, implied, recurse_cnt, res, res_sval);
1000
1001 /* FIXME: call rl_to_sval() on the results */
1002
1003 switch (implied) {
1004 case RL_HARD:
1005 case RL_IMPLIED:
1006 case RL_ABSOLUTE:
1007 state = get_extra_state(expr);
1008 if (!state) {
1009 if (implied == RL_HARD)
1010 return false;
1011 if (get_local_rl(expr, res))
1012 return true;
1013 if (get_mtag_rl(expr, res))
1014 return true;
1015 if (get_db_type_rl(expr, res))
1016 return true;
1017 if (is_array(expr) && get_array_rl(expr, res))
1018 return true;
1019 return false;
1020 }
1021 if (implied == RL_HARD && !estate_has_hard_max(state))
1022 return false;
1023 *res = clone_rl(estate_rl(state));
1024 return true;
1025 case RL_REAL_ABSOLUTE: {
1026 struct smatch_state *abs_state;
1027
1028 state = get_extra_state(expr);
1029 abs_state = get_real_absolute_state(expr);
1030
1031 if (estate_rl(state) && estate_rl(abs_state)) {
1032 *res = clone_rl(rl_intersection(estate_rl(state),
1043 * extra state if there is one. We don't bother keeping
1044 * the abs state in sync all the time because we know it
1045 * will be filtered later.
1046 *
1047 * It's not totally obvious to me how they should be
1048 * handled. Perhaps we should take the whole rl and
1049 * filter by the imaginary states. Perhaps we should
1050 * just go with the empty state.
1051 *
1052 * Anyway what we currently do is return NULL here and
1053 * that gets translated into the whole range in
1054 * get_real_absolute_rl().
1055 *
1056 */
1057 return false;
1058 } else if (estate_rl(abs_state)) {
1059 *res = clone_rl(estate_rl(abs_state));
1060 return true;
1061 }
1062
1063 if (get_local_rl(expr, res))
1064 return true;
1065 if (get_mtag_rl(expr, res))
1066 return true;
1067 if (get_db_type_rl(expr, res))
1068 return true;
1069 if (is_array(expr) && get_array_rl(expr, res))
1070 return true;
1071 return false;
1072 }
1073 case RL_FUZZY:
1074 if (!get_fuzzy_min_helper(expr, &min))
1075 min = sval_type_min(get_type(expr));
1076 if (!get_fuzzy_max_helper(expr, &max))
1077 return false;
1078 /* fuzzy ranges are often inverted */
1079 if (sval_cmp(min, max) > 0) {
1080 sval = min;
1081 min = max;
1082 max = sval;
1083 }
1084 *res = alloc_rl(min, max);
1499 return false;
1500
1501 if (sval.type)
1502 *res = alloc_rl(sval, sval);
1503 else
1504 *res = rl;
1505 return true;
1506 }
1507
1508 struct {
1509 struct expression *expr;
1510 sval_t sval;
1511 } cached_results[24];
1512 static int cache_idx;
1513
1514 void clear_math_cache(void)
1515 {
1516 memset(cached_results, 0, sizeof(cached_results));
1517 }
1518
1519 /*
1520 * Don't cache EXPR_VALUE because values are fast already.
1521 *
1522 */
1523 static bool get_value_literal(struct expression *expr, sval_t *res_sval)
1524 {
1525 struct expression *tmp;
1526 int recurse_cnt = 0;
1527
1528 tmp = strip_expr(expr);
1529 if (!tmp || tmp->type != EXPR_VALUE)
1530 return false;
1531
1532 return get_rl_sval(expr, RL_EXACT, &recurse_cnt, NULL, res_sval);
1533 }
1534
1535 /* returns 1 if it can get a value literal or else returns 0 */
1536 int get_value(struct expression *expr, sval_t *res_sval)
1537 {
1538 struct range_list *(*orig_custom_fn)(struct expression *expr);
1743 type = &llong_ctype;
1744 rl = NULL;
1745 get_rl_helper(expr, RL_REAL_ABSOLUTE, &rl);
1746 if (rl)
1747 *sval = rl_max(rl);
1748 else
1749 *sval = sval_type_max(type);
1750
1751 if (sval_cmp(sval_type_max(type), *sval) < 0)
1752 *sval = sval_type_max(type);
1753 return 1;
1754 }
1755
1756 int known_condition_true(struct expression *expr)
1757 {
1758 sval_t tmp;
1759
1760 if (!expr)
1761 return 0;
1762
1763 if (get_value(expr, &tmp) && tmp.value)
1764 return 1;
1765
1766 return 0;
1767 }
1768
1769 int known_condition_false(struct expression *expr)
1770 {
1771 if (!expr)
1772 return 0;
1773
1774 if (is_zero(expr))
1775 return 1;
1776
1777 return 0;
1778 }
1779
1780 int implied_condition_true(struct expression *expr)
1781 {
1782 sval_t tmp;
1783
1784 if (!expr)
1785 return 0;
1786
1787 if (known_condition_true(expr))
1788 return 1;
1789 if (get_implied_value(expr, &tmp) && tmp.value)
1790 return 1;
1791
1792 if (expr->type == EXPR_POSTOP)
1793 return implied_condition_true(expr->unop);
1794
1795 if (expr->type == EXPR_PREOP && expr->op == SPECIAL_DECREMENT)
1796 return implied_not_equal(expr->unop, 1);
|
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
16 */
17
18 #include "symbol.h"
19 #include "smatch.h"
20 #include "smatch_slist.h"
21 #include "smatch_extra.h"
22
23 static bool get_rl_sval(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *sval_res);
24 static bool get_rl_internal(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res);
25 static bool handle_variable(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval);
26 static struct range_list *(*custom_handle_variable)(struct expression *expr);
27
28 static bool get_implied_value_internal(struct expression *expr, int *recurse_cnt, sval_t *res_sval);
29 static int get_absolute_rl_internal(struct expression *expr, struct range_list **rl, int *recurse_cnt);
30
31 static sval_t zero = {.type = &int_ctype, {.value = 0} };
32 static sval_t one = {.type = &int_ctype, {.value = 1} };
33
34 static int fast_math_only;
35
36 struct range_list *rl_zero(void)
37 {
38 static struct range_list *zero_perm;
39
40 if (!zero_perm)
41 zero_perm = clone_rl_permanent(alloc_rl(zero, zero));
42 return zero_perm;
43 }
44
45 struct range_list *rl_one(void)
46 {
47 static struct range_list *one_perm;
48
49 if (!one_perm)
50 one_perm = clone_rl_permanent(alloc_rl(one, one));
51
52 return one_perm;
53 }
54
55 enum {
841 int final_pass_orig = final_pass;
842
843 cond_true = expr->cond_true;
844 if (!cond_true)
845 cond_true = expr->conditional;
846
847 if (known_condition_true(expr->conditional))
848 return get_rl_sval(cond_true, implied, recurse_cnt, res, res_sval);
849 if (known_condition_false(expr->conditional))
850 return get_rl_sval(expr->cond_false, implied, recurse_cnt, res, res_sval);
851
852 if (implied == RL_EXACT)
853 return false;
854
855 if (implied_condition_true(expr->conditional))
856 return get_rl_sval(cond_true, implied, recurse_cnt, res, res_sval);
857 if (implied_condition_false(expr->conditional))
858 return get_rl_sval(expr->cond_false, implied, recurse_cnt, res, res_sval);
859
860 /* this becomes a problem with deeply nested conditional statements */
861 if (fast_math_only || low_on_memory())
862 return false;
863
864 type = get_type(expr);
865
866 __push_fake_cur_stree();
867 final_pass = 0;
868 __split_whole_condition(expr->conditional);
869 true_rl = NULL;
870 get_rl_internal(cond_true, implied, recurse_cnt, &true_rl);
871 __push_true_states();
872 __use_false_states();
873 false_rl = NULL;
874 get_rl_internal(expr->cond_false, implied, recurse_cnt, &false_rl);
875 __merge_true_states();
876 __free_fake_cur_stree();
877 final_pass = final_pass_orig;
878
879 if (!true_rl || !false_rl)
880 return false;
881 true_rl = cast_rl(type, true_rl);
932 sym = expr->symbol;
933 if (!(sym->ctype.modifiers & MOD_CONST))
934 return 0;
935 if (get_value(sym->initializer, &right)) {
936 *sval = sval_cast(get_type(expr), right);
937 return 1;
938 }
939 return 0;
940 }
941
942 struct range_list *var_to_absolute_rl(struct expression *expr)
943 {
944 struct smatch_state *state;
945 struct range_list *rl;
946
947 state = get_extra_state(expr);
948 if (!state || is_whole_rl(estate_rl(state))) {
949 state = get_real_absolute_state(expr);
950 if (state && state->data && !estate_is_whole(state))
951 return clone_rl(estate_rl(state));
952 if (get_mtag_rl(expr, &rl))
953 return rl;
954 if (get_db_type_rl(expr, &rl) && !is_whole_rl(rl))
955 return rl;
956 return alloc_whole_rl(get_type(expr));
957 }
958 /* err on the side of saying things are possible */
959 if (!estate_rl(state))
960 return alloc_whole_rl(get_type(expr));
961 return clone_rl(estate_rl(state));
962 }
963
964 static bool handle_variable(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
965 {
966 struct smatch_state *state;
967 struct range_list *rl;
968 sval_t sval, min, max;
969 struct symbol *type;
970
971 if (get_const_value(expr, &sval)) {
991 *res_sval = sval;
992 return true;
993 }
994
995 type = get_type(expr);
996 if (type &&
997 (type->type == SYM_ARRAY ||
998 type->type == SYM_FN))
999 return handle_address(expr, implied, recurse_cnt, res, res_sval);
1000
1001 /* FIXME: call rl_to_sval() on the results */
1002
1003 switch (implied) {
1004 case RL_HARD:
1005 case RL_IMPLIED:
1006 case RL_ABSOLUTE:
1007 state = get_extra_state(expr);
1008 if (!state) {
1009 if (implied == RL_HARD)
1010 return false;
1011 if (get_mtag_rl(expr, res))
1012 return true;
1013 if (get_db_type_rl(expr, res))
1014 return true;
1015 if (is_array(expr) && get_array_rl(expr, res))
1016 return true;
1017 return false;
1018 }
1019 if (implied == RL_HARD && !estate_has_hard_max(state))
1020 return false;
1021 *res = clone_rl(estate_rl(state));
1022 return true;
1023 case RL_REAL_ABSOLUTE: {
1024 struct smatch_state *abs_state;
1025
1026 state = get_extra_state(expr);
1027 abs_state = get_real_absolute_state(expr);
1028
1029 if (estate_rl(state) && estate_rl(abs_state)) {
1030 *res = clone_rl(rl_intersection(estate_rl(state),
1041 * extra state if there is one. We don't bother keeping
1042 * the abs state in sync all the time because we know it
1043 * will be filtered later.
1044 *
1045 * It's not totally obvious to me how they should be
1046 * handled. Perhaps we should take the whole rl and
1047 * filter by the imaginary states. Perhaps we should
1048 * just go with the empty state.
1049 *
1050 * Anyway what we currently do is return NULL here and
1051 * that gets translated into the whole range in
1052 * get_real_absolute_rl().
1053 *
1054 */
1055 return false;
1056 } else if (estate_rl(abs_state)) {
1057 *res = clone_rl(estate_rl(abs_state));
1058 return true;
1059 }
1060
1061 if (get_mtag_rl(expr, res))
1062 return true;
1063 if (get_db_type_rl(expr, res))
1064 return true;
1065 if (is_array(expr) && get_array_rl(expr, res))
1066 return true;
1067 return false;
1068 }
1069 case RL_FUZZY:
1070 if (!get_fuzzy_min_helper(expr, &min))
1071 min = sval_type_min(get_type(expr));
1072 if (!get_fuzzy_max_helper(expr, &max))
1073 return false;
1074 /* fuzzy ranges are often inverted */
1075 if (sval_cmp(min, max) > 0) {
1076 sval = min;
1077 min = max;
1078 max = sval;
1079 }
1080 *res = alloc_rl(min, max);
1495 return false;
1496
1497 if (sval.type)
1498 *res = alloc_rl(sval, sval);
1499 else
1500 *res = rl;
1501 return true;
1502 }
1503
1504 struct {
1505 struct expression *expr;
1506 sval_t sval;
1507 } cached_results[24];
1508 static int cache_idx;
1509
1510 void clear_math_cache(void)
1511 {
1512 memset(cached_results, 0, sizeof(cached_results));
1513 }
1514
1515 void set_fast_math_only(void)
1516 {
1517 fast_math_only++;
1518 }
1519
1520 void clear_fast_math_only(void)
1521 {
1522 fast_math_only--;
1523 }
1524
1525 /*
1526 * Don't cache EXPR_VALUE because values are fast already.
1527 *
1528 */
1529 static bool get_value_literal(struct expression *expr, sval_t *res_sval)
1530 {
1531 struct expression *tmp;
1532 int recurse_cnt = 0;
1533
1534 tmp = strip_expr(expr);
1535 if (!tmp || tmp->type != EXPR_VALUE)
1536 return false;
1537
1538 return get_rl_sval(expr, RL_EXACT, &recurse_cnt, NULL, res_sval);
1539 }
1540
1541 /* returns 1 if it can get a value literal or else returns 0 */
1542 int get_value(struct expression *expr, sval_t *res_sval)
1543 {
1544 struct range_list *(*orig_custom_fn)(struct expression *expr);
1749 type = &llong_ctype;
1750 rl = NULL;
1751 get_rl_helper(expr, RL_REAL_ABSOLUTE, &rl);
1752 if (rl)
1753 *sval = rl_max(rl);
1754 else
1755 *sval = sval_type_max(type);
1756
1757 if (sval_cmp(sval_type_max(type), *sval) < 0)
1758 *sval = sval_type_max(type);
1759 return 1;
1760 }
1761
1762 int known_condition_true(struct expression *expr)
1763 {
1764 sval_t tmp;
1765
1766 if (!expr)
1767 return 0;
1768
1769 if (__inline_fn && get_param_num(expr) >= 0) {
1770 if (get_implied_value(expr, &tmp) && tmp.value)
1771 return 1;
1772 return 0;
1773 }
1774
1775 if (get_value(expr, &tmp) && tmp.value)
1776 return 1;
1777
1778 return 0;
1779 }
1780
1781 int known_condition_false(struct expression *expr)
1782 {
1783 sval_t tmp;
1784
1785 if (!expr)
1786 return 0;
1787
1788 if (__inline_fn && get_param_num(expr) >= 0) {
1789 if (get_implied_value(expr, &tmp) && tmp.value == 0)
1790 return 1;
1791 return 0;
1792 }
1793
1794 if (expr_is_zero(expr))
1795 return 1;
1796
1797 return 0;
1798 }
1799
1800 int implied_condition_true(struct expression *expr)
1801 {
1802 sval_t tmp;
1803
1804 if (!expr)
1805 return 0;
1806
1807 if (known_condition_true(expr))
1808 return 1;
1809 if (get_implied_value(expr, &tmp) && tmp.value)
1810 return 1;
1811
1812 if (expr->type == EXPR_POSTOP)
1813 return implied_condition_true(expr->unop);
1814
1815 if (expr->type == EXPR_PREOP && expr->op == SPECIAL_DECREMENT)
1816 return implied_not_equal(expr->unop, 1);
|