11f5207b7SJohn Levon /* 21f5207b7SJohn Levon * Copyright (C) 2012 Oracle. 31f5207b7SJohn Levon * 41f5207b7SJohn Levon * This program is free software; you can redistribute it and/or 51f5207b7SJohn Levon * modify it under the terms of the GNU General Public License 61f5207b7SJohn Levon * as published by the Free Software Foundation; either version 2 71f5207b7SJohn Levon * of the License, or (at your option) any later version. 81f5207b7SJohn Levon * 91f5207b7SJohn Levon * This program is distributed in the hope that it will be useful, 101f5207b7SJohn Levon * but WITHOUT ANY WARRANTY; without even the implied warranty of 111f5207b7SJohn Levon * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 121f5207b7SJohn Levon * GNU General Public License for more details. 131f5207b7SJohn Levon * 141f5207b7SJohn Levon * You should have received a copy of the GNU General Public License 151f5207b7SJohn Levon * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt 161f5207b7SJohn Levon */ 171f5207b7SJohn Levon 181f5207b7SJohn Levon /* 191f5207b7SJohn Levon * The point here is to store the relationships between two variables. 201f5207b7SJohn Levon * Ie: y > x. 211f5207b7SJohn Levon * To do that we create a state with the two variables in alphabetical order: 221f5207b7SJohn Levon * ->name = "x vs y" and the state would be "<". On the false path the state 231f5207b7SJohn Levon * would be ">=". 241f5207b7SJohn Levon * 251f5207b7SJohn Levon * Part of the trick of it is that if x or y is modified then we need to reset 261f5207b7SJohn Levon * the state. We need to keep a list of all the states which depend on x and 271f5207b7SJohn Levon * all the states which depend on y. The link_id code handles this. 281f5207b7SJohn Levon * 291f5207b7SJohn Levon */ 301f5207b7SJohn Levon 311f5207b7SJohn Levon #include "smatch.h" 321f5207b7SJohn Levon #include "smatch_extra.h" 331f5207b7SJohn Levon #include "smatch_slist.h" 341f5207b7SJohn Levon 351f5207b7SJohn Levon static int compare_id; 361f5207b7SJohn Levon static int link_id; 371f5207b7SJohn Levon static int inc_dec_id; 381f5207b7SJohn Levon static int inc_dec_link_id; 391f5207b7SJohn Levon 401f5207b7SJohn Levon static void add_comparison(struct expression *left, int comparison, struct expression *right); 411f5207b7SJohn Levon 421f5207b7SJohn Levon /* for handling for loops */ 431f5207b7SJohn Levon STATE(start); 441f5207b7SJohn Levon STATE(incremented); 451f5207b7SJohn Levon 461f5207b7SJohn Levon ALLOCATOR(compare_data, "compare data"); 471f5207b7SJohn Levon 481f5207b7SJohn Levon static struct symbol *vsl_to_sym(struct var_sym_list *vsl) 491f5207b7SJohn Levon { 501f5207b7SJohn Levon struct var_sym *vs; 511f5207b7SJohn Levon 521f5207b7SJohn Levon if (!vsl) 531f5207b7SJohn Levon return NULL; 541f5207b7SJohn Levon if (ptr_list_size((struct ptr_list *)vsl) != 1) 551f5207b7SJohn Levon return NULL; 561f5207b7SJohn Levon vs = first_ptr_list((struct ptr_list *)vsl); 571f5207b7SJohn Levon return vs->sym; 581f5207b7SJohn Levon } 591f5207b7SJohn Levon 601f5207b7SJohn Levon struct smatch_state *alloc_compare_state( 611f5207b7SJohn Levon struct expression *left, 621f5207b7SJohn Levon const char *left_var, struct var_sym_list *left_vsl, 631f5207b7SJohn Levon int comparison, 641f5207b7SJohn Levon struct expression *right, 651f5207b7SJohn Levon const char *right_var, struct var_sym_list *right_vsl) 661f5207b7SJohn Levon { 671f5207b7SJohn Levon struct smatch_state *state; 681f5207b7SJohn Levon struct compare_data *data; 691f5207b7SJohn Levon 701f5207b7SJohn Levon state = __alloc_smatch_state(0); 711f5207b7SJohn Levon state->name = alloc_sname(show_special(comparison)); 721f5207b7SJohn Levon data = __alloc_compare_data(0); 731f5207b7SJohn Levon data->left = left; 741f5207b7SJohn Levon data->left_var = alloc_sname(left_var); 751f5207b7SJohn Levon data->left_vsl = clone_var_sym_list(left_vsl); 761f5207b7SJohn Levon data->comparison = comparison; 771f5207b7SJohn Levon data->right = right; 781f5207b7SJohn Levon data->right_var = alloc_sname(right_var); 791f5207b7SJohn Levon data->right_vsl = clone_var_sym_list(right_vsl); 801f5207b7SJohn Levon state->data = data; 811f5207b7SJohn Levon return state; 821f5207b7SJohn Levon } 831f5207b7SJohn Levon 841f5207b7SJohn Levon int state_to_comparison(struct smatch_state *state) 851f5207b7SJohn Levon { 861f5207b7SJohn Levon if (!state || !state->data) 871f5207b7SJohn Levon return 0; 881f5207b7SJohn Levon return ((struct compare_data *)state->data)->comparison; 891f5207b7SJohn Levon } 901f5207b7SJohn Levon 911f5207b7SJohn Levon /* 921f5207b7SJohn Levon * flip_comparison() reverses the op left and right. So "x >= y" becomes "y <= x". 931f5207b7SJohn Levon */ 941f5207b7SJohn Levon int flip_comparison(int op) 951f5207b7SJohn Levon { 961f5207b7SJohn Levon switch (op) { 971f5207b7SJohn Levon case 0: 981f5207b7SJohn Levon return 0; 991f5207b7SJohn Levon case '<': 1001f5207b7SJohn Levon return '>'; 1011f5207b7SJohn Levon case SPECIAL_UNSIGNED_LT: 1021f5207b7SJohn Levon return SPECIAL_UNSIGNED_GT; 1031f5207b7SJohn Levon case SPECIAL_LTE: 1041f5207b7SJohn Levon return SPECIAL_GTE; 1051f5207b7SJohn Levon case SPECIAL_UNSIGNED_LTE: 1061f5207b7SJohn Levon return SPECIAL_UNSIGNED_GTE; 1071f5207b7SJohn Levon case SPECIAL_EQUAL: 1081f5207b7SJohn Levon return SPECIAL_EQUAL; 1091f5207b7SJohn Levon case SPECIAL_NOTEQUAL: 1101f5207b7SJohn Levon return SPECIAL_NOTEQUAL; 1111f5207b7SJohn Levon case SPECIAL_GTE: 1121f5207b7SJohn Levon return SPECIAL_LTE; 1131f5207b7SJohn Levon case SPECIAL_UNSIGNED_GTE: 1141f5207b7SJohn Levon return SPECIAL_UNSIGNED_LTE; 1151f5207b7SJohn Levon case '>': 1161f5207b7SJohn Levon return '<'; 1171f5207b7SJohn Levon case SPECIAL_UNSIGNED_GT: 1181f5207b7SJohn Levon return SPECIAL_UNSIGNED_LT; 1191f5207b7SJohn Levon default: 1201f5207b7SJohn Levon sm_perror("unhandled comparison %d", op); 1211f5207b7SJohn Levon return op; 1221f5207b7SJohn Levon } 1231f5207b7SJohn Levon } 1241f5207b7SJohn Levon 1251f5207b7SJohn Levon int negate_comparison(int op) 1261f5207b7SJohn Levon { 1271f5207b7SJohn Levon switch (op) { 1281f5207b7SJohn Levon case 0: 1291f5207b7SJohn Levon return 0; 1301f5207b7SJohn Levon case '<': 1311f5207b7SJohn Levon return SPECIAL_GTE; 1321f5207b7SJohn Levon case SPECIAL_UNSIGNED_LT: 1331f5207b7SJohn Levon return SPECIAL_UNSIGNED_GTE; 1341f5207b7SJohn Levon case SPECIAL_LTE: 1351f5207b7SJohn Levon return '>'; 1361f5207b7SJohn Levon case SPECIAL_UNSIGNED_LTE: 1371f5207b7SJohn Levon return SPECIAL_UNSIGNED_GT; 1381f5207b7SJohn Levon case SPECIAL_EQUAL: 1391f5207b7SJohn Levon return SPECIAL_NOTEQUAL; 1401f5207b7SJohn Levon case SPECIAL_NOTEQUAL: 1411f5207b7SJohn Levon return SPECIAL_EQUAL; 1421f5207b7SJohn Levon case SPECIAL_GTE: 1431f5207b7SJohn Levon return '<'; 1441f5207b7SJohn Levon case SPECIAL_UNSIGNED_GTE: 1451f5207b7SJohn Levon return SPECIAL_UNSIGNED_LT; 1461f5207b7SJohn Levon case '>': 1471f5207b7SJohn Levon return SPECIAL_LTE; 1481f5207b7SJohn Levon case SPECIAL_UNSIGNED_GT: 1491f5207b7SJohn Levon return SPECIAL_UNSIGNED_LTE; 1501f5207b7SJohn Levon default: 1511f5207b7SJohn Levon sm_perror("unhandled comparison %d", op); 1521f5207b7SJohn Levon return op; 1531f5207b7SJohn Levon } 1541f5207b7SJohn Levon } 1551f5207b7SJohn Levon 1561f5207b7SJohn Levon static int rl_comparison(struct range_list *left_rl, struct range_list *right_rl) 1571f5207b7SJohn Levon { 1581f5207b7SJohn Levon sval_t left_min, left_max, right_min, right_max; 1591f5207b7SJohn Levon struct symbol *type = &int_ctype; 1601f5207b7SJohn Levon 1611f5207b7SJohn Levon if (!left_rl || !right_rl) 1621f5207b7SJohn Levon return 0; 1631f5207b7SJohn Levon 1641f5207b7SJohn Levon if (type_positive_bits(rl_type(left_rl)) > type_positive_bits(type)) 1651f5207b7SJohn Levon type = rl_type(left_rl); 1661f5207b7SJohn Levon if (type_positive_bits(rl_type(right_rl)) > type_positive_bits(type)) 1671f5207b7SJohn Levon type = rl_type(right_rl); 1681f5207b7SJohn Levon 1691f5207b7SJohn Levon left_rl = cast_rl(type, left_rl); 1701f5207b7SJohn Levon right_rl = cast_rl(type, right_rl); 1711f5207b7SJohn Levon 1721f5207b7SJohn Levon left_min = rl_min(left_rl); 1731f5207b7SJohn Levon left_max = rl_max(left_rl); 1741f5207b7SJohn Levon right_min = rl_min(right_rl); 1751f5207b7SJohn Levon right_max = rl_max(right_rl); 1761f5207b7SJohn Levon 1771f5207b7SJohn Levon if (left_min.value == left_max.value && 1781f5207b7SJohn Levon right_min.value == right_max.value && 1791f5207b7SJohn Levon left_min.value == right_min.value) 1801f5207b7SJohn Levon return SPECIAL_EQUAL; 1811f5207b7SJohn Levon 1821f5207b7SJohn Levon if (sval_cmp(left_max, right_min) < 0) 1831f5207b7SJohn Levon return '<'; 1841f5207b7SJohn Levon if (sval_cmp(left_max, right_min) == 0) 1851f5207b7SJohn Levon return SPECIAL_LTE; 1861f5207b7SJohn Levon if (sval_cmp(left_min, right_max) > 0) 1871f5207b7SJohn Levon return '>'; 1881f5207b7SJohn Levon if (sval_cmp(left_min, right_max) == 0) 1891f5207b7SJohn Levon return SPECIAL_GTE; 1901f5207b7SJohn Levon 1911f5207b7SJohn Levon return 0; 1921f5207b7SJohn Levon } 1931f5207b7SJohn Levon 1941f5207b7SJohn Levon static int comparison_from_extra(struct expression *a, struct expression *b) 1951f5207b7SJohn Levon { 1961f5207b7SJohn Levon struct range_list *left, *right; 1971f5207b7SJohn Levon 1981f5207b7SJohn Levon if (!get_implied_rl(a, &left)) 1991f5207b7SJohn Levon return 0; 2001f5207b7SJohn Levon if (!get_implied_rl(b, &right)) 2011f5207b7SJohn Levon return 0; 2021f5207b7SJohn Levon 2031f5207b7SJohn Levon return rl_comparison(left, right); 2041f5207b7SJohn Levon } 2051f5207b7SJohn Levon 2061f5207b7SJohn Levon static struct range_list *get_orig_rl(struct var_sym_list *vsl) 2071f5207b7SJohn Levon { 2081f5207b7SJohn Levon struct symbol *sym; 2091f5207b7SJohn Levon struct smatch_state *state; 2101f5207b7SJohn Levon 2111f5207b7SJohn Levon if (!vsl) 2121f5207b7SJohn Levon return NULL; 2131f5207b7SJohn Levon sym = vsl_to_sym(vsl); 2141f5207b7SJohn Levon if (!sym || !sym->ident) 2151f5207b7SJohn Levon return NULL; 2161f5207b7SJohn Levon state = get_orig_estate(sym->ident->name, sym); 2171f5207b7SJohn Levon return estate_rl(state); 2181f5207b7SJohn Levon } 2191f5207b7SJohn Levon 2201f5207b7SJohn Levon static struct smatch_state *unmatched_comparison(struct sm_state *sm) 2211f5207b7SJohn Levon { 2221f5207b7SJohn Levon struct compare_data *data = sm->state->data; 2231f5207b7SJohn Levon struct range_list *left_rl, *right_rl; 2241f5207b7SJohn Levon int op; 2251f5207b7SJohn Levon 2261f5207b7SJohn Levon if (!data) 2271f5207b7SJohn Levon return &undefined; 2281f5207b7SJohn Levon 2291f5207b7SJohn Levon if (strstr(data->left_var, " orig")) 2301f5207b7SJohn Levon left_rl = get_orig_rl(data->left_vsl); 2311f5207b7SJohn Levon else if (!get_implied_rl_var_sym(data->left_var, vsl_to_sym(data->left_vsl), &left_rl)) 2321f5207b7SJohn Levon return &undefined; 2331f5207b7SJohn Levon 2341f5207b7SJohn Levon if (strstr(data->right_var, " orig")) 2351f5207b7SJohn Levon right_rl = get_orig_rl(data->right_vsl); 2361f5207b7SJohn Levon else if (!get_implied_rl_var_sym(data->right_var, vsl_to_sym(data->right_vsl), &right_rl)) 2371f5207b7SJohn Levon return &undefined; 2381f5207b7SJohn Levon 2391f5207b7SJohn Levon op = rl_comparison(left_rl, right_rl); 2401f5207b7SJohn Levon if (op) 2411f5207b7SJohn Levon return alloc_compare_state( 2421f5207b7SJohn Levon data->left, data->left_var, data->left_vsl, 2431f5207b7SJohn Levon op, 2441f5207b7SJohn Levon data->right, data->right_var, data->right_vsl); 2451f5207b7SJohn Levon 2461f5207b7SJohn Levon return &undefined; 2471f5207b7SJohn Levon } 2481f5207b7SJohn Levon 2491f5207b7SJohn Levon /* remove_unsigned_from_comparison() is obviously a hack. */ 2501f5207b7SJohn Levon int remove_unsigned_from_comparison(int op) 2511f5207b7SJohn Levon { 2521f5207b7SJohn Levon switch (op) { 2531f5207b7SJohn Levon case SPECIAL_UNSIGNED_LT: 2541f5207b7SJohn Levon return '<'; 2551f5207b7SJohn Levon case SPECIAL_UNSIGNED_LTE: 2561f5207b7SJohn Levon return SPECIAL_LTE; 2571f5207b7SJohn Levon case SPECIAL_UNSIGNED_GTE: 2581f5207b7SJohn Levon return SPECIAL_GTE; 2591f5207b7SJohn Levon case SPECIAL_UNSIGNED_GT: 2601f5207b7SJohn Levon return '>'; 2611f5207b7SJohn Levon default: 2621f5207b7SJohn Levon return op; 2631f5207b7SJohn Levon } 2641f5207b7SJohn Levon } 2651f5207b7SJohn Levon 2661f5207b7SJohn Levon /* 2671f5207b7SJohn Levon * This is for when you merge states "a < b" and "a == b", the result is that 2681f5207b7SJohn Levon * we can say for sure, "a <= b" after the merge. 2691f5207b7SJohn Levon */ 2701f5207b7SJohn Levon int merge_comparisons(int one, int two) 2711f5207b7SJohn Levon { 2721f5207b7SJohn Levon int LT, EQ, GT; 2731f5207b7SJohn Levon 2741f5207b7SJohn Levon if (!one || !two) 2751f5207b7SJohn Levon return 0; 2761f5207b7SJohn Levon 2771f5207b7SJohn Levon one = remove_unsigned_from_comparison(one); 2781f5207b7SJohn Levon two = remove_unsigned_from_comparison(two); 2791f5207b7SJohn Levon 2801f5207b7SJohn Levon if (one == two) 2811f5207b7SJohn Levon return one; 2821f5207b7SJohn Levon 2831f5207b7SJohn Levon LT = EQ = GT = 0; 2841f5207b7SJohn Levon 2851f5207b7SJohn Levon switch (one) { 2861f5207b7SJohn Levon case '<': 2871f5207b7SJohn Levon LT = 1; 2881f5207b7SJohn Levon break; 2891f5207b7SJohn Levon case SPECIAL_LTE: 2901f5207b7SJohn Levon LT = 1; 2911f5207b7SJohn Levon EQ = 1; 2921f5207b7SJohn Levon break; 2931f5207b7SJohn Levon case SPECIAL_EQUAL: 2941f5207b7SJohn Levon EQ = 1; 2951f5207b7SJohn Levon break; 2961f5207b7SJohn Levon case SPECIAL_GTE: 2971f5207b7SJohn Levon GT = 1; 2981f5207b7SJohn Levon EQ = 1; 2991f5207b7SJohn Levon break; 3001f5207b7SJohn Levon case '>': 3011f5207b7SJohn Levon GT = 1; 3021f5207b7SJohn Levon } 3031f5207b7SJohn Levon 3041f5207b7SJohn Levon switch (two) { 3051f5207b7SJohn Levon case '<': 3061f5207b7SJohn Levon LT = 1; 3071f5207b7SJohn Levon break; 3081f5207b7SJohn Levon case SPECIAL_LTE: 3091f5207b7SJohn Levon LT = 1; 3101f5207b7SJohn Levon EQ = 1; 3111f5207b7SJohn Levon break; 3121f5207b7SJohn Levon case SPECIAL_EQUAL: 3131f5207b7SJohn Levon EQ = 1; 3141f5207b7SJohn Levon break; 3151f5207b7SJohn Levon case SPECIAL_GTE: 3161f5207b7SJohn Levon GT = 1; 3171f5207b7SJohn Levon EQ = 1; 3181f5207b7SJohn Levon break; 3191f5207b7SJohn Levon case '>': 3201f5207b7SJohn Levon GT = 1; 3211f5207b7SJohn Levon } 3221f5207b7SJohn Levon 3231f5207b7SJohn Levon if (LT && EQ && GT) 3241f5207b7SJohn Levon return 0; 3251f5207b7SJohn Levon if (LT && EQ) 3261f5207b7SJohn Levon return SPECIAL_LTE; 3271f5207b7SJohn Levon if (LT && GT) 3281f5207b7SJohn Levon return SPECIAL_NOTEQUAL; 3291f5207b7SJohn Levon if (LT) 3301f5207b7SJohn Levon return '<'; 3311f5207b7SJohn Levon if (EQ && GT) 3321f5207b7SJohn Levon return SPECIAL_GTE; 3331f5207b7SJohn Levon if (GT) 3341f5207b7SJohn Levon return '>'; 3351f5207b7SJohn Levon return 0; 3361f5207b7SJohn Levon } 3371f5207b7SJohn Levon 3381f5207b7SJohn Levon /* 3391f5207b7SJohn Levon * This is for if you have "a < b" and "b <= c". Or in other words, 3401f5207b7SJohn Levon * "a < b <= c". You would call this like get_combined_comparison('<', '<='). 3411f5207b7SJohn Levon * The return comparison would be '<'. 3421f5207b7SJohn Levon * 3431f5207b7SJohn Levon * This function is different from merge_comparisons(), for example: 3441f5207b7SJohn Levon * merge_comparison('<', '==') returns '<=' 3451f5207b7SJohn Levon * get_combined_comparison('<', '==') returns '<' 3461f5207b7SJohn Levon */ 3471f5207b7SJohn Levon int combine_comparisons(int left_compare, int right_compare) 3481f5207b7SJohn Levon { 3491f5207b7SJohn Levon int LT, EQ, GT; 3501f5207b7SJohn Levon 3511f5207b7SJohn Levon left_compare = remove_unsigned_from_comparison(left_compare); 3521f5207b7SJohn Levon right_compare = remove_unsigned_from_comparison(right_compare); 3531f5207b7SJohn Levon 3541f5207b7SJohn Levon LT = EQ = GT = 0; 3551f5207b7SJohn Levon 3561f5207b7SJohn Levon switch (left_compare) { 3571f5207b7SJohn Levon case '<': 3581f5207b7SJohn Levon LT++; 3591f5207b7SJohn Levon break; 3601f5207b7SJohn Levon case SPECIAL_LTE: 3611f5207b7SJohn Levon LT++; 3621f5207b7SJohn Levon EQ++; 3631f5207b7SJohn Levon break; 3641f5207b7SJohn Levon case SPECIAL_EQUAL: 3651f5207b7SJohn Levon return right_compare; 3661f5207b7SJohn Levon case SPECIAL_GTE: 3671f5207b7SJohn Levon GT++; 3681f5207b7SJohn Levon EQ++; 3691f5207b7SJohn Levon break; 3701f5207b7SJohn Levon case '>': 3711f5207b7SJohn Levon GT++; 3721f5207b7SJohn Levon } 3731f5207b7SJohn Levon 3741f5207b7SJohn Levon switch (right_compare) { 3751f5207b7SJohn Levon case '<': 3761f5207b7SJohn Levon LT++; 3771f5207b7SJohn Levon break; 3781f5207b7SJohn Levon case SPECIAL_LTE: 3791f5207b7SJohn Levon LT++; 3801f5207b7SJohn Levon EQ++; 3811f5207b7SJohn Levon break; 3821f5207b7SJohn Levon case SPECIAL_EQUAL: 3831f5207b7SJohn Levon return left_compare; 3841f5207b7SJohn Levon case SPECIAL_GTE: 3851f5207b7SJohn Levon GT++; 3861f5207b7SJohn Levon EQ++; 3871f5207b7SJohn Levon break; 3881f5207b7SJohn Levon case '>': 3891f5207b7SJohn Levon GT++; 3901f5207b7SJohn Levon } 3911f5207b7SJohn Levon 3921f5207b7SJohn Levon if (LT == 2) { 3931f5207b7SJohn Levon if (EQ == 2) 3941f5207b7SJohn Levon return SPECIAL_LTE; 3951f5207b7SJohn Levon return '<'; 3961f5207b7SJohn Levon } 3971f5207b7SJohn Levon 3981f5207b7SJohn Levon if (GT == 2) { 3991f5207b7SJohn Levon if (EQ == 2) 4001f5207b7SJohn Levon return SPECIAL_GTE; 4011f5207b7SJohn Levon return '>'; 4021f5207b7SJohn Levon } 4031f5207b7SJohn Levon return 0; 4041f5207b7SJohn Levon } 4051f5207b7SJohn Levon 4061f5207b7SJohn Levon int filter_comparison(int orig, int op) 4071f5207b7SJohn Levon { 4081f5207b7SJohn Levon if (orig == op) 4091f5207b7SJohn Levon return orig; 4101f5207b7SJohn Levon 4111f5207b7SJohn Levon orig = remove_unsigned_from_comparison(orig); 4121f5207b7SJohn Levon op = remove_unsigned_from_comparison(op); 4131f5207b7SJohn Levon 4141f5207b7SJohn Levon switch (orig) { 4151f5207b7SJohn Levon case 0: 4161f5207b7SJohn Levon return op; 4171f5207b7SJohn Levon case '<': 4181f5207b7SJohn Levon switch (op) { 4191f5207b7SJohn Levon case '<': 4201f5207b7SJohn Levon case SPECIAL_LTE: 4211f5207b7SJohn Levon case SPECIAL_NOTEQUAL: 4221f5207b7SJohn Levon return '<'; 4231f5207b7SJohn Levon } 4241f5207b7SJohn Levon return 0; 4251f5207b7SJohn Levon case SPECIAL_LTE: 4261f5207b7SJohn Levon switch (op) { 4271f5207b7SJohn Levon case '<': 4281f5207b7SJohn Levon case SPECIAL_LTE: 4291f5207b7SJohn Levon case SPECIAL_EQUAL: 4301f5207b7SJohn Levon return op; 4311f5207b7SJohn Levon case SPECIAL_NOTEQUAL: 4321f5207b7SJohn Levon return '<'; 4331f5207b7SJohn Levon } 4341f5207b7SJohn Levon return 0; 4351f5207b7SJohn Levon case SPECIAL_EQUAL: 4361f5207b7SJohn Levon switch (op) { 4371f5207b7SJohn Levon case SPECIAL_LTE: 4381f5207b7SJohn Levon case SPECIAL_EQUAL: 4391f5207b7SJohn Levon case SPECIAL_GTE: 4401f5207b7SJohn Levon case SPECIAL_UNSIGNED_LTE: 4411f5207b7SJohn Levon case SPECIAL_UNSIGNED_GTE: 4421f5207b7SJohn Levon return SPECIAL_EQUAL; 4431f5207b7SJohn Levon } 4441f5207b7SJohn Levon return 0; 4451f5207b7SJohn Levon case SPECIAL_NOTEQUAL: 4461f5207b7SJohn Levon switch (op) { 4471f5207b7SJohn Levon case '<': 4481f5207b7SJohn Levon case SPECIAL_LTE: 4491f5207b7SJohn Levon return '<'; 4501f5207b7SJohn Levon case SPECIAL_UNSIGNED_LT: 4511f5207b7SJohn Levon case SPECIAL_UNSIGNED_LTE: 4521f5207b7SJohn Levon return SPECIAL_UNSIGNED_LT; 4531f5207b7SJohn Levon case SPECIAL_NOTEQUAL: 4541f5207b7SJohn Levon return op; 4551f5207b7SJohn Levon case '>': 4561f5207b7SJohn Levon case SPECIAL_GTE: 4571f5207b7SJohn Levon return '>'; 4581f5207b7SJohn Levon case SPECIAL_UNSIGNED_GT: 4591f5207b7SJohn Levon case SPECIAL_UNSIGNED_GTE: 4601f5207b7SJohn Levon return SPECIAL_UNSIGNED_GT; 4611f5207b7SJohn Levon } 4621f5207b7SJohn Levon return 0; 4631f5207b7SJohn Levon case SPECIAL_GTE: 4641f5207b7SJohn Levon switch (op) { 4651f5207b7SJohn Levon case SPECIAL_LTE: 4661f5207b7SJohn Levon return SPECIAL_EQUAL; 4671f5207b7SJohn Levon case '>': 4681f5207b7SJohn Levon case SPECIAL_GTE: 4691f5207b7SJohn Levon case SPECIAL_EQUAL: 4701f5207b7SJohn Levon return op; 4711f5207b7SJohn Levon case SPECIAL_NOTEQUAL: 4721f5207b7SJohn Levon return '>'; 4731f5207b7SJohn Levon } 4741f5207b7SJohn Levon return 0; 4751f5207b7SJohn Levon case '>': 4761f5207b7SJohn Levon switch (op) { 4771f5207b7SJohn Levon case '>': 4781f5207b7SJohn Levon case SPECIAL_GTE: 4791f5207b7SJohn Levon case SPECIAL_NOTEQUAL: 4801f5207b7SJohn Levon return '>'; 4811f5207b7SJohn Levon } 4821f5207b7SJohn Levon return 0; 4831f5207b7SJohn Levon case SPECIAL_UNSIGNED_LT: 4841f5207b7SJohn Levon switch (op) { 4851f5207b7SJohn Levon case SPECIAL_UNSIGNED_LT: 4861f5207b7SJohn Levon case SPECIAL_UNSIGNED_LTE: 4871f5207b7SJohn Levon case SPECIAL_NOTEQUAL: 4881f5207b7SJohn Levon return SPECIAL_UNSIGNED_LT; 4891f5207b7SJohn Levon } 4901f5207b7SJohn Levon return 0; 4911f5207b7SJohn Levon case SPECIAL_UNSIGNED_LTE: 4921f5207b7SJohn Levon switch (op) { 4931f5207b7SJohn Levon case SPECIAL_UNSIGNED_LT: 4941f5207b7SJohn Levon case SPECIAL_UNSIGNED_LTE: 4951f5207b7SJohn Levon case SPECIAL_EQUAL: 4961f5207b7SJohn Levon return op; 4971f5207b7SJohn Levon case SPECIAL_NOTEQUAL: 4981f5207b7SJohn Levon return SPECIAL_UNSIGNED_LT; 4991f5207b7SJohn Levon case SPECIAL_UNSIGNED_GTE: 5001f5207b7SJohn Levon return SPECIAL_EQUAL; 5011f5207b7SJohn Levon } 5021f5207b7SJohn Levon return 0; 5031f5207b7SJohn Levon case SPECIAL_UNSIGNED_GTE: 5041f5207b7SJohn Levon switch (op) { 5051f5207b7SJohn Levon case SPECIAL_UNSIGNED_LTE: 5061f5207b7SJohn Levon return SPECIAL_EQUAL; 5071f5207b7SJohn Levon case SPECIAL_NOTEQUAL: 5081f5207b7SJohn Levon return SPECIAL_UNSIGNED_GT; 5091f5207b7SJohn Levon case SPECIAL_EQUAL: 5101f5207b7SJohn Levon case SPECIAL_UNSIGNED_GTE: 5111f5207b7SJohn Levon case SPECIAL_UNSIGNED_GT: 5121f5207b7SJohn Levon return op; 5131f5207b7SJohn Levon } 5141f5207b7SJohn Levon return 0; 5151f5207b7SJohn Levon case SPECIAL_UNSIGNED_GT: 5161f5207b7SJohn Levon switch (op) { 5171f5207b7SJohn Levon case SPECIAL_UNSIGNED_GT: 5181f5207b7SJohn Levon case SPECIAL_UNSIGNED_GTE: 5191f5207b7SJohn Levon case SPECIAL_NOTEQUAL: 5201f5207b7SJohn Levon return SPECIAL_UNSIGNED_GT; 5211f5207b7SJohn Levon } 5221f5207b7SJohn Levon return 0; 5231f5207b7SJohn Levon } 5241f5207b7SJohn Levon return 0; 5251f5207b7SJohn Levon } 5261f5207b7SJohn Levon 5271f5207b7SJohn Levon static void pre_merge_hook(struct sm_state *sm) 5281f5207b7SJohn Levon { 5291f5207b7SJohn Levon struct compare_data *data = sm->state->data; 5301f5207b7SJohn Levon int other; 5311f5207b7SJohn Levon 5321f5207b7SJohn Levon if (!data) 5331f5207b7SJohn Levon return; 5341f5207b7SJohn Levon other = get_comparison(data->left, data->right); 5351f5207b7SJohn Levon if (!other) 5361f5207b7SJohn Levon return; 5371f5207b7SJohn Levon 5381f5207b7SJohn Levon set_state(compare_id, sm->name, NULL, 5391f5207b7SJohn Levon alloc_compare_state(data->left, data->left_var, data->left_vsl, 5401f5207b7SJohn Levon other, 5411f5207b7SJohn Levon data->right, data->right_var, data->right_vsl)); 5421f5207b7SJohn Levon } 5431f5207b7SJohn Levon 5441f5207b7SJohn Levon struct smatch_state *merge_compare_states(struct smatch_state *s1, struct smatch_state *s2) 5451f5207b7SJohn Levon { 5461f5207b7SJohn Levon struct compare_data *data = s1->data; 5471f5207b7SJohn Levon int op; 5481f5207b7SJohn Levon 5491f5207b7SJohn Levon op = merge_comparisons(state_to_comparison(s1), state_to_comparison(s2)); 5501f5207b7SJohn Levon if (op) 5511f5207b7SJohn Levon return alloc_compare_state( 5521f5207b7SJohn Levon data->left, data->left_var, data->left_vsl, 5531f5207b7SJohn Levon op, 5541f5207b7SJohn Levon data->right, data->right_var, data->right_vsl); 5551f5207b7SJohn Levon return &undefined; 5561f5207b7SJohn Levon } 5571f5207b7SJohn Levon 5581f5207b7SJohn Levon static struct smatch_state *alloc_link_state(struct string_list *links) 5591f5207b7SJohn Levon { 5601f5207b7SJohn Levon struct smatch_state *state; 5611f5207b7SJohn Levon static char buf[256]; 5621f5207b7SJohn Levon char *tmp; 5631f5207b7SJohn Levon int i; 5641f5207b7SJohn Levon 5651f5207b7SJohn Levon state = __alloc_smatch_state(0); 5661f5207b7SJohn Levon 5671f5207b7SJohn Levon i = 0; 5681f5207b7SJohn Levon FOR_EACH_PTR(links, tmp) { 5691f5207b7SJohn Levon if (!i++) { 5701f5207b7SJohn Levon snprintf(buf, sizeof(buf), "%s", tmp); 5711f5207b7SJohn Levon } else { 5721f5207b7SJohn Levon append(buf, ", ", sizeof(buf)); 5731f5207b7SJohn Levon append(buf, tmp, sizeof(buf)); 5741f5207b7SJohn Levon } 5751f5207b7SJohn Levon } END_FOR_EACH_PTR(tmp); 5761f5207b7SJohn Levon 5771f5207b7SJohn Levon state->name = alloc_sname(buf); 5781f5207b7SJohn Levon state->data = links; 5791f5207b7SJohn Levon return state; 5801f5207b7SJohn Levon } 5811f5207b7SJohn Levon 5821f5207b7SJohn Levon static void save_start_states(struct statement *stmt) 5831f5207b7SJohn Levon { 5841f5207b7SJohn Levon struct symbol *param; 5851f5207b7SJohn Levon char orig[64]; 5861f5207b7SJohn Levon char state_name[128]; 5871f5207b7SJohn Levon struct smatch_state *state; 5881f5207b7SJohn Levon struct string_list *links; 5891f5207b7SJohn Levon char *link; 5901f5207b7SJohn Levon 5911f5207b7SJohn Levon FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) { 5921f5207b7SJohn Levon struct var_sym_list *left_vsl = NULL; 5931f5207b7SJohn Levon struct var_sym_list *right_vsl = NULL; 5941f5207b7SJohn Levon 5951f5207b7SJohn Levon if (!param->ident) 5961f5207b7SJohn Levon continue; 5971f5207b7SJohn Levon snprintf(orig, sizeof(orig), "%s orig", param->ident->name); 5981f5207b7SJohn Levon snprintf(state_name, sizeof(state_name), "%s vs %s", param->ident->name, orig); 5991f5207b7SJohn Levon add_var_sym(&left_vsl, param->ident->name, param); 6001f5207b7SJohn Levon add_var_sym(&right_vsl, orig, param); 6011f5207b7SJohn Levon state = alloc_compare_state( 6021f5207b7SJohn Levon NULL, param->ident->name, left_vsl, 6031f5207b7SJohn Levon SPECIAL_EQUAL, 6041f5207b7SJohn Levon NULL, alloc_sname(orig), right_vsl); 6051f5207b7SJohn Levon set_state(compare_id, state_name, NULL, state); 6061f5207b7SJohn Levon 6071f5207b7SJohn Levon link = alloc_sname(state_name); 6081f5207b7SJohn Levon links = NULL; 6091f5207b7SJohn Levon insert_string(&links, link); 6101f5207b7SJohn Levon state = alloc_link_state(links); 6111f5207b7SJohn Levon set_state(link_id, param->ident->name, param, state); 6121f5207b7SJohn Levon } END_FOR_EACH_PTR(param); 6131f5207b7SJohn Levon } 6141f5207b7SJohn Levon 6151f5207b7SJohn Levon static struct smatch_state *merge_links(struct smatch_state *s1, struct smatch_state *s2) 6161f5207b7SJohn Levon { 6171f5207b7SJohn Levon struct smatch_state *ret; 6181f5207b7SJohn Levon struct string_list *links; 6191f5207b7SJohn Levon 6201f5207b7SJohn Levon links = combine_string_lists(s1->data, s2->data); 6211f5207b7SJohn Levon ret = alloc_link_state(links); 6221f5207b7SJohn Levon return ret; 6231f5207b7SJohn Levon } 6241f5207b7SJohn Levon 6251f5207b7SJohn Levon static void save_link_var_sym(const char *var, struct symbol *sym, const char *link) 6261f5207b7SJohn Levon { 6271f5207b7SJohn Levon struct smatch_state *old_state, *new_state; 6281f5207b7SJohn Levon struct string_list *links; 6291f5207b7SJohn Levon char *new; 6301f5207b7SJohn Levon 6311f5207b7SJohn Levon old_state = get_state(link_id, var, sym); 6321f5207b7SJohn Levon if (old_state) 6331f5207b7SJohn Levon links = clone_str_list(old_state->data); 6341f5207b7SJohn Levon else 6351f5207b7SJohn Levon links = NULL; 6361f5207b7SJohn Levon 6371f5207b7SJohn Levon new = alloc_sname(link); 6381f5207b7SJohn Levon insert_string(&links, new); 6391f5207b7SJohn Levon 6401f5207b7SJohn Levon new_state = alloc_link_state(links); 6411f5207b7SJohn Levon set_state(link_id, var, sym, new_state); 6421f5207b7SJohn Levon } 6431f5207b7SJohn Levon 644*efe51d0cSJohn Levon static void match_inc(struct sm_state *sm, bool preserve) 6451f5207b7SJohn Levon { 6461f5207b7SJohn Levon struct string_list *links; 6471f5207b7SJohn Levon struct smatch_state *state, *new; 6481f5207b7SJohn Levon struct compare_data *data; 6491f5207b7SJohn Levon char *tmp; 6501f5207b7SJohn Levon int flip; 6511f5207b7SJohn Levon int op; 6521f5207b7SJohn Levon 6531f5207b7SJohn Levon links = sm->state->data; 6541f5207b7SJohn Levon 6551f5207b7SJohn Levon FOR_EACH_PTR(links, tmp) { 6561f5207b7SJohn Levon state = get_state(compare_id, tmp, NULL); 6571f5207b7SJohn Levon if (!state) 6581f5207b7SJohn Levon continue; 6591f5207b7SJohn Levon data = state->data; 6601f5207b7SJohn Levon if (!data) 6611f5207b7SJohn Levon continue; 6621f5207b7SJohn Levon 6631f5207b7SJohn Levon flip = 0; 6641f5207b7SJohn Levon if (strncmp(sm->name, tmp, strlen(sm->name)) != 0 || 6651f5207b7SJohn Levon tmp[strlen(sm->name)] != ' ') 6661f5207b7SJohn Levon flip = 1; 6671f5207b7SJohn Levon 6681f5207b7SJohn Levon op = state_to_comparison(state); 6691f5207b7SJohn Levon 6701f5207b7SJohn Levon switch (flip ? flip_comparison(op) : op) { 6711f5207b7SJohn Levon case SPECIAL_EQUAL: 6721f5207b7SJohn Levon case SPECIAL_GTE: 6731f5207b7SJohn Levon case SPECIAL_UNSIGNED_GTE: 6741f5207b7SJohn Levon case '>': 6751f5207b7SJohn Levon case SPECIAL_UNSIGNED_GT: 676*efe51d0cSJohn Levon if (preserve) 677*efe51d0cSJohn Levon break; 6781f5207b7SJohn Levon new = alloc_compare_state( 6791f5207b7SJohn Levon data->left, data->left_var, data->left_vsl, 6801f5207b7SJohn Levon flip ? '<' : '>', 6811f5207b7SJohn Levon data->right, data->right_var, data->right_vsl); 6821f5207b7SJohn Levon set_state(compare_id, tmp, NULL, new); 6831f5207b7SJohn Levon break; 6841f5207b7SJohn Levon case '<': 6851f5207b7SJohn Levon case SPECIAL_UNSIGNED_LT: 6861f5207b7SJohn Levon new = alloc_compare_state( 6871f5207b7SJohn Levon data->left, data->left_var, data->left_vsl, 6881f5207b7SJohn Levon flip ? SPECIAL_GTE : SPECIAL_LTE, 6891f5207b7SJohn Levon data->right, data->right_var, data->right_vsl); 6901f5207b7SJohn Levon set_state(compare_id, tmp, NULL, new); 6911f5207b7SJohn Levon break; 6921f5207b7SJohn Levon default: 6931f5207b7SJohn Levon set_state(compare_id, tmp, NULL, &undefined); 6941f5207b7SJohn Levon } 6951f5207b7SJohn Levon } END_FOR_EACH_PTR(tmp); 6961f5207b7SJohn Levon } 6971f5207b7SJohn Levon 698*efe51d0cSJohn Levon static void match_dec(struct sm_state *sm, bool preserve) 6991f5207b7SJohn Levon { 7001f5207b7SJohn Levon struct string_list *links; 7011f5207b7SJohn Levon struct smatch_state *state; 7021f5207b7SJohn Levon char *tmp; 7031f5207b7SJohn Levon 7041f5207b7SJohn Levon links = sm->state->data; 7051f5207b7SJohn Levon 7061f5207b7SJohn Levon FOR_EACH_PTR(links, tmp) { 7071f5207b7SJohn Levon state = get_state(compare_id, tmp, NULL); 7081f5207b7SJohn Levon 7091f5207b7SJohn Levon switch (state_to_comparison(state)) { 7101f5207b7SJohn Levon case SPECIAL_EQUAL: 7111f5207b7SJohn Levon case SPECIAL_LTE: 7121f5207b7SJohn Levon case SPECIAL_UNSIGNED_LTE: 7131f5207b7SJohn Levon case '<': 7141f5207b7SJohn Levon case SPECIAL_UNSIGNED_LT: { 7151f5207b7SJohn Levon struct compare_data *data = state->data; 7161f5207b7SJohn Levon struct smatch_state *new; 7171f5207b7SJohn Levon 718*efe51d0cSJohn Levon if (preserve) 719*efe51d0cSJohn Levon break; 720*efe51d0cSJohn Levon 7211f5207b7SJohn Levon new = alloc_compare_state( 7221f5207b7SJohn Levon data->left, data->left_var, data->left_vsl, 7231f5207b7SJohn Levon '<', 7241f5207b7SJohn Levon data->right, data->right_var, data->right_vsl); 7251f5207b7SJohn Levon set_state(compare_id, tmp, NULL, new); 7261f5207b7SJohn Levon break; 7271f5207b7SJohn Levon } 7281f5207b7SJohn Levon default: 7291f5207b7SJohn Levon set_state(compare_id, tmp, NULL, &undefined); 7301f5207b7SJohn Levon } 7311f5207b7SJohn Levon } END_FOR_EACH_PTR(tmp); 7321f5207b7SJohn Levon } 7331f5207b7SJohn Levon 734*efe51d0cSJohn Levon static void reset_sm(struct sm_state *sm) 735*efe51d0cSJohn Levon { 736*efe51d0cSJohn Levon struct string_list *links; 737*efe51d0cSJohn Levon char *tmp; 738*efe51d0cSJohn Levon 739*efe51d0cSJohn Levon links = sm->state->data; 740*efe51d0cSJohn Levon 741*efe51d0cSJohn Levon FOR_EACH_PTR(links, tmp) { 742*efe51d0cSJohn Levon set_state(compare_id, tmp, NULL, &undefined); 743*efe51d0cSJohn Levon } END_FOR_EACH_PTR(tmp); 744*efe51d0cSJohn Levon set_state(link_id, sm->name, sm->sym, &undefined); 745*efe51d0cSJohn Levon } 746*efe51d0cSJohn Levon 747*efe51d0cSJohn Levon static bool match_add_sub_assign(struct sm_state *sm, struct expression *expr) 748*efe51d0cSJohn Levon { 749*efe51d0cSJohn Levon struct range_list *rl; 750*efe51d0cSJohn Levon sval_t zero = { .type = &int_ctype }; 751*efe51d0cSJohn Levon 752*efe51d0cSJohn Levon if (!expr || expr->type != EXPR_ASSIGNMENT) 753*efe51d0cSJohn Levon return false; 754*efe51d0cSJohn Levon if (expr->op != SPECIAL_ADD_ASSIGN && expr->op != SPECIAL_SUB_ASSIGN) 755*efe51d0cSJohn Levon return false; 756*efe51d0cSJohn Levon 757*efe51d0cSJohn Levon get_absolute_rl(expr->right, &rl); 758*efe51d0cSJohn Levon if (sval_is_negative(rl_min(rl))) { 759*efe51d0cSJohn Levon reset_sm(sm); 760*efe51d0cSJohn Levon return false; 761*efe51d0cSJohn Levon } 762*efe51d0cSJohn Levon 763*efe51d0cSJohn Levon if (expr->op == SPECIAL_ADD_ASSIGN) 764*efe51d0cSJohn Levon match_inc(sm, rl_has_sval(rl, zero)); 765*efe51d0cSJohn Levon else 766*efe51d0cSJohn Levon match_dec(sm, rl_has_sval(rl, zero)); 767*efe51d0cSJohn Levon return true; 768*efe51d0cSJohn Levon } 769*efe51d0cSJohn Levon 7701f5207b7SJohn Levon static void match_inc_dec(struct sm_state *sm, struct expression *mod_expr) 7711f5207b7SJohn Levon { 7721f5207b7SJohn Levon /* 7731f5207b7SJohn Levon * if (foo > bar) then ++foo is also > bar. 7741f5207b7SJohn Levon */ 7751f5207b7SJohn Levon if (!mod_expr) 7761f5207b7SJohn Levon return; 777*efe51d0cSJohn Levon if (match_add_sub_assign(sm, mod_expr)) 778*efe51d0cSJohn Levon return; 7791f5207b7SJohn Levon if (mod_expr->type != EXPR_PREOP && mod_expr->type != EXPR_POSTOP) 7801f5207b7SJohn Levon return; 7811f5207b7SJohn Levon 7821f5207b7SJohn Levon if (mod_expr->op == SPECIAL_INCREMENT) 783*efe51d0cSJohn Levon match_inc(sm, false); 7841f5207b7SJohn Levon else if (mod_expr->op == SPECIAL_DECREMENT) 785*efe51d0cSJohn Levon match_dec(sm, false); 7861f5207b7SJohn Levon } 7871f5207b7SJohn Levon 7881f5207b7SJohn Levon static int is_self_assign(struct expression *expr) 7891f5207b7SJohn Levon { 7901f5207b7SJohn Levon if (!expr || expr->type != EXPR_ASSIGNMENT || expr->op != '=') 7911f5207b7SJohn Levon return 0; 7921f5207b7SJohn Levon return expr_equiv(expr->left, expr->right); 7931f5207b7SJohn Levon } 7941f5207b7SJohn Levon 7951f5207b7SJohn Levon static void match_modify(struct sm_state *sm, struct expression *mod_expr) 7961f5207b7SJohn Levon { 7971f5207b7SJohn Levon if (mod_expr && is_self_assign(mod_expr)) 7981f5207b7SJohn Levon return; 7991f5207b7SJohn Levon 8001f5207b7SJohn Levon /* handled by match_inc_dec() */ 8011f5207b7SJohn Levon if (mod_expr && 8021f5207b7SJohn Levon ((mod_expr->type == EXPR_PREOP || mod_expr->type == EXPR_POSTOP) && 8031f5207b7SJohn Levon (mod_expr->op == SPECIAL_INCREMENT || mod_expr->op == SPECIAL_DECREMENT))) 8041f5207b7SJohn Levon return; 805*efe51d0cSJohn Levon if (mod_expr && mod_expr->type == EXPR_ASSIGNMENT && 806*efe51d0cSJohn Levon (mod_expr->op == SPECIAL_ADD_ASSIGN || mod_expr->op == SPECIAL_SUB_ASSIGN)) 807*efe51d0cSJohn Levon return; 8081f5207b7SJohn Levon 809*efe51d0cSJohn Levon reset_sm(sm); 8101f5207b7SJohn Levon } 8111f5207b7SJohn Levon 8121f5207b7SJohn Levon static void match_preop(struct expression *expr) 8131f5207b7SJohn Levon { 8141f5207b7SJohn Levon struct expression *parent; 8151f5207b7SJohn Levon struct range_list *left, *right; 8161f5207b7SJohn Levon int op; 8171f5207b7SJohn Levon 8181f5207b7SJohn Levon /* 8191f5207b7SJohn Levon * This is an important special case. Say you have: 8201f5207b7SJohn Levon * 8211f5207b7SJohn Levon * if (++j == limit) 8221f5207b7SJohn Levon * 8231f5207b7SJohn Levon * Assume that we know the range of limit is higher than the start 8241f5207b7SJohn Levon * value for "j". Then the first thing that we process is the ++j. We 8251f5207b7SJohn Levon * have not comparison states set up so it doesn't get caught by the 8261f5207b7SJohn Levon * modification hook. But it does get caught by smatch_extra which sets 8271f5207b7SJohn Levon * j to unknown then we parse the "j == limit" and sets false to != but 8281f5207b7SJohn Levon * really we want false to be <. 8291f5207b7SJohn Levon * 8301f5207b7SJohn Levon * So what we do is we set j < limit here, then the match_modify catches 8311f5207b7SJohn Levon * it and we do a match_inc_dec(). 8321f5207b7SJohn Levon * 8331f5207b7SJohn Levon */ 8341f5207b7SJohn Levon 8351f5207b7SJohn Levon if (expr->type != EXPR_PREOP || 8361f5207b7SJohn Levon (expr->op != SPECIAL_INCREMENT && expr->op != SPECIAL_DECREMENT)) 8371f5207b7SJohn Levon return; 8381f5207b7SJohn Levon 8391f5207b7SJohn Levon parent = expr_get_parent_expr(expr); 8401f5207b7SJohn Levon if (!parent) 8411f5207b7SJohn Levon return; 8421f5207b7SJohn Levon if (parent->type != EXPR_COMPARE || parent->op != SPECIAL_EQUAL) 8431f5207b7SJohn Levon return; 8441f5207b7SJohn Levon if (parent->left != expr) 8451f5207b7SJohn Levon return; 8461f5207b7SJohn Levon 8471f5207b7SJohn Levon if (!get_implied_rl(expr->unop, &left) || 8481f5207b7SJohn Levon !get_implied_rl(parent->right, &right)) 8491f5207b7SJohn Levon return; 8501f5207b7SJohn Levon 8511f5207b7SJohn Levon op = rl_comparison(left, right); 8521f5207b7SJohn Levon if (!op) 8531f5207b7SJohn Levon return; 8541f5207b7SJohn Levon 8551f5207b7SJohn Levon add_comparison(expr->unop, op, parent->right); 8561f5207b7SJohn Levon } 8571f5207b7SJohn Levon 8581f5207b7SJohn Levon static char *chunk_to_var_sym(struct expression *expr, struct symbol **sym) 8591f5207b7SJohn Levon { 8601f5207b7SJohn Levon expr = strip_expr(expr); 8611f5207b7SJohn Levon if (!expr) 8621f5207b7SJohn Levon return NULL; 8631f5207b7SJohn Levon if (sym) 8641f5207b7SJohn Levon *sym = NULL; 8651f5207b7SJohn Levon 8661f5207b7SJohn Levon if (expr->type == EXPR_PREOP && 8671f5207b7SJohn Levon (expr->op == SPECIAL_INCREMENT || 8681f5207b7SJohn Levon expr->op == SPECIAL_DECREMENT)) 8691f5207b7SJohn Levon expr = strip_expr(expr->unop); 8701f5207b7SJohn Levon 8711f5207b7SJohn Levon if (expr->type == EXPR_CALL) { 8721f5207b7SJohn Levon char buf[64]; 8731f5207b7SJohn Levon 8741f5207b7SJohn Levon snprintf(buf, sizeof(buf), "return %p", expr); 8751f5207b7SJohn Levon return alloc_string(buf); 8761f5207b7SJohn Levon } 8771f5207b7SJohn Levon 8781f5207b7SJohn Levon return expr_to_chunk_sym_vsl(expr, sym, NULL); 8791f5207b7SJohn Levon } 8801f5207b7SJohn Levon 8811f5207b7SJohn Levon static char *chunk_to_var(struct expression *expr) 8821f5207b7SJohn Levon { 8831f5207b7SJohn Levon return chunk_to_var_sym(expr, NULL); 8841f5207b7SJohn Levon } 8851f5207b7SJohn Levon 8861f5207b7SJohn Levon static struct smatch_state *get_state_chunk(int owner, struct expression *expr) 8871f5207b7SJohn Levon { 8881f5207b7SJohn Levon char *name; 8891f5207b7SJohn Levon struct symbol *sym; 8901f5207b7SJohn Levon struct smatch_state *ret; 8911f5207b7SJohn Levon 8921f5207b7SJohn Levon name = chunk_to_var_sym(expr, &sym); 8931f5207b7SJohn Levon if (!name) 8941f5207b7SJohn Levon return NULL; 8951f5207b7SJohn Levon 8961f5207b7SJohn Levon ret = get_state(owner, name, sym); 8971f5207b7SJohn Levon free_string(name); 8981f5207b7SJohn Levon return ret; 8991f5207b7SJohn Levon } 9001f5207b7SJohn Levon 9011f5207b7SJohn Levon static void save_link(struct expression *expr, char *link) 9021f5207b7SJohn Levon { 9031f5207b7SJohn Levon char *var; 9041f5207b7SJohn Levon struct symbol *sym; 9051f5207b7SJohn Levon 9061f5207b7SJohn Levon expr = strip_expr(expr); 9071f5207b7SJohn Levon if (expr->type == EXPR_BINOP) { 9081f5207b7SJohn Levon char *chunk; 9091f5207b7SJohn Levon 9101f5207b7SJohn Levon chunk = chunk_to_var(expr); 9111f5207b7SJohn Levon if (!chunk) 9121f5207b7SJohn Levon return; 9131f5207b7SJohn Levon 9141f5207b7SJohn Levon save_link(expr->left, link); 9151f5207b7SJohn Levon save_link(expr->right, link); 9161f5207b7SJohn Levon save_link_var_sym(chunk, NULL, link); 9171f5207b7SJohn Levon return; 9181f5207b7SJohn Levon } 9191f5207b7SJohn Levon 9201f5207b7SJohn Levon var = chunk_to_var_sym(expr, &sym); 9211f5207b7SJohn Levon if (!var) 9221f5207b7SJohn Levon return; 9231f5207b7SJohn Levon 9241f5207b7SJohn Levon save_link_var_sym(var, sym, link); 9251f5207b7SJohn Levon free_string(var); 9261f5207b7SJohn Levon } 9271f5207b7SJohn Levon 9281f5207b7SJohn Levon static int get_orig_comparison(struct stree *pre_stree, const char *left, const char *right) 9291f5207b7SJohn Levon { 9301f5207b7SJohn Levon struct smatch_state *state; 9311f5207b7SJohn Levon struct compare_data *data; 9321f5207b7SJohn Levon int flip = 0; 9331f5207b7SJohn Levon char state_name[256]; 9341f5207b7SJohn Levon 9351f5207b7SJohn Levon if (strcmp(left, right) > 0) { 9361f5207b7SJohn Levon const char *tmp = right; 9371f5207b7SJohn Levon 9381f5207b7SJohn Levon flip = 1; 9391f5207b7SJohn Levon right = left; 9401f5207b7SJohn Levon left = tmp; 9411f5207b7SJohn Levon } 9421f5207b7SJohn Levon 9431f5207b7SJohn Levon snprintf(state_name, sizeof(state_name), "%s vs %s", left, right); 9441f5207b7SJohn Levon state = get_state_stree(pre_stree, compare_id, state_name, NULL); 9451f5207b7SJohn Levon if (!state || !state->data) 9461f5207b7SJohn Levon return 0; 9471f5207b7SJohn Levon data = state->data; 9481f5207b7SJohn Levon if (flip) 9491f5207b7SJohn Levon return flip_comparison(data->comparison); 9501f5207b7SJohn Levon return data->comparison; 9511f5207b7SJohn Levon 9521f5207b7SJohn Levon } 9531f5207b7SJohn Levon 9541f5207b7SJohn Levon static int have_common_var_sym(struct var_sym_list *left_vsl, struct var_sym_list *right_vsl) 9551f5207b7SJohn Levon { 9561f5207b7SJohn Levon struct var_sym *tmp; 9571f5207b7SJohn Levon 9581f5207b7SJohn Levon FOR_EACH_PTR(left_vsl, tmp) { 9591f5207b7SJohn Levon if (in_var_sym_list(right_vsl, tmp->var, tmp->sym)) 9601f5207b7SJohn Levon return 1; 9611f5207b7SJohn Levon } END_FOR_EACH_PTR(tmp); 9621f5207b7SJohn Levon 9631f5207b7SJohn Levon return 0; 9641f5207b7SJohn Levon } 9651f5207b7SJohn Levon 9661f5207b7SJohn Levon /* 9671f5207b7SJohn Levon * The idea here is that we take a comparison "a < b" and then we look at all 9681f5207b7SJohn Levon * the things which "b" is compared against "b < c" and we say that that implies 9691f5207b7SJohn Levon * a relationship "a < c". 9701f5207b7SJohn Levon * 9711f5207b7SJohn Levon * The names here about because the comparisons are organized like this 9721f5207b7SJohn Levon * "a < b < c". 9731f5207b7SJohn Levon * 9741f5207b7SJohn Levon */ 9751f5207b7SJohn Levon static void update_tf_links(struct stree *pre_stree, 9761f5207b7SJohn Levon struct expression *left_expr, 9771f5207b7SJohn Levon const char *left_var, struct var_sym_list *left_vsl, 9781f5207b7SJohn Levon int left_comparison, int left_false_comparison, 9791f5207b7SJohn Levon const char *mid_var, struct var_sym_list *mid_vsl, 9801f5207b7SJohn Levon struct string_list *links) 9811f5207b7SJohn Levon { 9821f5207b7SJohn Levon struct smatch_state *state; 9831f5207b7SJohn Levon struct smatch_state *true_state, *false_state; 9841f5207b7SJohn Levon struct compare_data *data; 9851f5207b7SJohn Levon struct expression *right_expr; 9861f5207b7SJohn Levon const char *right_var; 9871f5207b7SJohn Levon struct var_sym_list *right_vsl; 9881f5207b7SJohn Levon int orig_comparison; 9891f5207b7SJohn Levon int right_comparison; 9901f5207b7SJohn Levon int true_comparison; 9911f5207b7SJohn Levon int false_comparison; 9921f5207b7SJohn Levon char *tmp; 9931f5207b7SJohn Levon char state_name[256]; 9941f5207b7SJohn Levon struct var_sym *vs; 9951f5207b7SJohn Levon 9961f5207b7SJohn Levon FOR_EACH_PTR(links, tmp) { 9971f5207b7SJohn Levon state = get_state_stree(pre_stree, compare_id, tmp, NULL); 9981f5207b7SJohn Levon if (!state || !state->data) 9991f5207b7SJohn Levon continue; 10001f5207b7SJohn Levon data = state->data; 10011f5207b7SJohn Levon right_comparison = data->comparison; 10021f5207b7SJohn Levon right_expr = data->right; 10031f5207b7SJohn Levon right_var = data->right_var; 10041f5207b7SJohn Levon right_vsl = data->right_vsl; 10051f5207b7SJohn Levon if (strcmp(mid_var, right_var) == 0) { 10061f5207b7SJohn Levon right_expr = data->left; 10071f5207b7SJohn Levon right_var = data->left_var; 10081f5207b7SJohn Levon right_vsl = data->left_vsl; 10091f5207b7SJohn Levon right_comparison = flip_comparison(right_comparison); 10101f5207b7SJohn Levon } 10111f5207b7SJohn Levon if (have_common_var_sym(left_vsl, right_vsl)) 10121f5207b7SJohn Levon continue; 10131f5207b7SJohn Levon 10141f5207b7SJohn Levon orig_comparison = get_orig_comparison(pre_stree, left_var, right_var); 10151f5207b7SJohn Levon 10161f5207b7SJohn Levon true_comparison = combine_comparisons(left_comparison, right_comparison); 10171f5207b7SJohn Levon false_comparison = combine_comparisons(left_false_comparison, right_comparison); 10181f5207b7SJohn Levon 10191f5207b7SJohn Levon true_comparison = filter_comparison(orig_comparison, true_comparison); 10201f5207b7SJohn Levon false_comparison = filter_comparison(orig_comparison, false_comparison); 10211f5207b7SJohn Levon 10221f5207b7SJohn Levon if (strcmp(left_var, right_var) > 0) { 10231f5207b7SJohn Levon struct expression *tmp_expr = left_expr; 10241f5207b7SJohn Levon const char *tmp_var = left_var; 10251f5207b7SJohn Levon struct var_sym_list *tmp_vsl = left_vsl; 10261f5207b7SJohn Levon 10271f5207b7SJohn Levon left_expr = right_expr; 10281f5207b7SJohn Levon left_var = right_var; 10291f5207b7SJohn Levon left_vsl = right_vsl; 10301f5207b7SJohn Levon right_expr = tmp_expr; 10311f5207b7SJohn Levon right_var = tmp_var; 10321f5207b7SJohn Levon right_vsl = tmp_vsl; 10331f5207b7SJohn Levon true_comparison = flip_comparison(true_comparison); 10341f5207b7SJohn Levon false_comparison = flip_comparison(false_comparison); 10351f5207b7SJohn Levon } 10361f5207b7SJohn Levon 10371f5207b7SJohn Levon if (!true_comparison && !false_comparison) 10381f5207b7SJohn Levon continue; 10391f5207b7SJohn Levon 10401f5207b7SJohn Levon if (true_comparison) 10411f5207b7SJohn Levon true_state = alloc_compare_state( 10421f5207b7SJohn Levon left_expr, left_var, left_vsl, 10431f5207b7SJohn Levon true_comparison, 10441f5207b7SJohn Levon right_expr, right_var, right_vsl); 10451f5207b7SJohn Levon else 10461f5207b7SJohn Levon true_state = NULL; 10471f5207b7SJohn Levon if (false_comparison) 10481f5207b7SJohn Levon false_state = alloc_compare_state( 10491f5207b7SJohn Levon left_expr, left_var, left_vsl, 10501f5207b7SJohn Levon false_comparison, 10511f5207b7SJohn Levon right_expr, right_var, right_vsl); 10521f5207b7SJohn Levon else 10531f5207b7SJohn Levon false_state = NULL; 10541f5207b7SJohn Levon 10551f5207b7SJohn Levon snprintf(state_name, sizeof(state_name), "%s vs %s", left_var, right_var); 10561f5207b7SJohn Levon set_true_false_states(compare_id, state_name, NULL, true_state, false_state); 10571f5207b7SJohn Levon FOR_EACH_PTR(left_vsl, vs) { 10581f5207b7SJohn Levon save_link_var_sym(vs->var, vs->sym, state_name); 10591f5207b7SJohn Levon } END_FOR_EACH_PTR(vs); 10601f5207b7SJohn Levon FOR_EACH_PTR(right_vsl, vs) { 10611f5207b7SJohn Levon save_link_var_sym(vs->var, vs->sym, state_name); 10621f5207b7SJohn Levon } END_FOR_EACH_PTR(vs); 10631f5207b7SJohn Levon if (!vsl_to_sym(left_vsl)) 10641f5207b7SJohn Levon save_link_var_sym(left_var, NULL, state_name); 10651f5207b7SJohn Levon if (!vsl_to_sym(right_vsl)) 10661f5207b7SJohn Levon save_link_var_sym(right_var, NULL, state_name); 10671f5207b7SJohn Levon } END_FOR_EACH_PTR(tmp); 10681f5207b7SJohn Levon } 10691f5207b7SJohn Levon 10701f5207b7SJohn Levon static void update_tf_data(struct stree *pre_stree, 10711f5207b7SJohn Levon struct expression *left_expr, 10721f5207b7SJohn Levon const char *left_name, struct var_sym_list *left_vsl, 10731f5207b7SJohn Levon struct expression *right_expr, 10741f5207b7SJohn Levon const char *right_name, struct var_sym_list *right_vsl, 10751f5207b7SJohn Levon int true_comparison, int false_comparison) 10761f5207b7SJohn Levon { 10771f5207b7SJohn Levon struct smatch_state *state; 10781f5207b7SJohn Levon 10791f5207b7SJohn Levon state = get_state_stree(pre_stree, link_id, right_name, vsl_to_sym(right_vsl)); 10801f5207b7SJohn Levon if (state) 10811f5207b7SJohn Levon update_tf_links(pre_stree, left_expr, left_name, left_vsl, true_comparison, false_comparison, right_name, right_vsl, state->data); 10821f5207b7SJohn Levon 10831f5207b7SJohn Levon state = get_state_stree(pre_stree, link_id, left_name, vsl_to_sym(left_vsl)); 10841f5207b7SJohn Levon if (state) 10851f5207b7SJohn Levon update_tf_links(pre_stree, right_expr, right_name, right_vsl, flip_comparison(true_comparison), flip_comparison(false_comparison), left_name, left_vsl, state->data); 10861f5207b7SJohn Levon } 10871f5207b7SJohn Levon 10881f5207b7SJohn Levon static void iter_modify(struct sm_state *sm, struct expression *mod_expr) 10891f5207b7SJohn Levon { 10901f5207b7SJohn Levon if (sm->state != &start || 10911f5207b7SJohn Levon !mod_expr || 10921f5207b7SJohn Levon (mod_expr->type != EXPR_PREOP && mod_expr->type != EXPR_POSTOP) || 10931f5207b7SJohn Levon mod_expr->op != SPECIAL_INCREMENT) 10941f5207b7SJohn Levon set_state(inc_dec_id, sm->name, sm->sym, &undefined); 10951f5207b7SJohn Levon else 10961f5207b7SJohn Levon set_state(inc_dec_id, sm->name, sm->sym, &incremented); 10971f5207b7SJohn Levon } 10981f5207b7SJohn Levon 10991f5207b7SJohn Levon static void handle_for_loops(struct expression *expr, char *state_name, struct smatch_state *false_state) 11001f5207b7SJohn Levon { 11011f5207b7SJohn Levon sval_t sval; 11021f5207b7SJohn Levon char *iter_name, *cap_name; 11031f5207b7SJohn Levon struct symbol *iter_sym, *cap_sym; 11041f5207b7SJohn Levon struct compare_data *data; 11051f5207b7SJohn Levon 11061f5207b7SJohn Levon if (expr->op != '<' && expr->op != SPECIAL_UNSIGNED_LT) 11071f5207b7SJohn Levon return; 11081f5207b7SJohn Levon 11091f5207b7SJohn Levon if (!__cur_stmt || !__prev_stmt) 11101f5207b7SJohn Levon return; 11111f5207b7SJohn Levon if (__cur_stmt->type != STMT_ITERATOR) 11121f5207b7SJohn Levon return; 11131f5207b7SJohn Levon if (__cur_stmt->iterator_pre_condition != expr) 11141f5207b7SJohn Levon return; 11151f5207b7SJohn Levon 11161f5207b7SJohn Levon /* literals are handled in smatch_extra.c */ 11171f5207b7SJohn Levon if (get_value(expr->right, &sval)) 11181f5207b7SJohn Levon return; 11191f5207b7SJohn Levon 11201f5207b7SJohn Levon /* First time checking the condition */ 11211f5207b7SJohn Levon if (__prev_stmt == __cur_stmt->iterator_pre_statement) { 11221f5207b7SJohn Levon if (!get_implied_value(expr->left, &sval) || 11231f5207b7SJohn Levon sval.value != 0) 11241f5207b7SJohn Levon return; 11251f5207b7SJohn Levon 11261f5207b7SJohn Levon iter_name = expr_to_var_sym(expr->left, &iter_sym); 11271f5207b7SJohn Levon cap_name = expr_to_var_sym(expr->right, &cap_sym); 11281f5207b7SJohn Levon if (!iter_name || !cap_name || !iter_sym || !cap_sym) { 11291f5207b7SJohn Levon free_string(iter_name); 11301f5207b7SJohn Levon free_string(cap_name); 11311f5207b7SJohn Levon return; 11321f5207b7SJohn Levon } 11331f5207b7SJohn Levon 11341f5207b7SJohn Levon set_state(inc_dec_id, iter_name, iter_sym, &start); 11351f5207b7SJohn Levon store_link(inc_dec_link_id, cap_name, cap_sym, iter_name, iter_sym); 11361f5207b7SJohn Levon 11371f5207b7SJohn Levon free_string(iter_name); 11381f5207b7SJohn Levon free_string(cap_name); 11391f5207b7SJohn Levon return; 11401f5207b7SJohn Levon } 11411f5207b7SJohn Levon 11421f5207b7SJohn Levon /* Second time checking the condtion */ 11431f5207b7SJohn Levon if (__prev_stmt != __cur_stmt->iterator_post_statement) 11441f5207b7SJohn Levon return; 11451f5207b7SJohn Levon 11461f5207b7SJohn Levon if (get_state_chunk(inc_dec_id, expr->left) != &incremented) 11471f5207b7SJohn Levon return; 11481f5207b7SJohn Levon 11491f5207b7SJohn Levon data = false_state->data; 11501f5207b7SJohn Levon false_state = alloc_compare_state( 11511f5207b7SJohn Levon data->left, data->left_var, data->left_vsl, 11521f5207b7SJohn Levon SPECIAL_EQUAL, 11531f5207b7SJohn Levon data->right, data->right_var, data->right_vsl); 11541f5207b7SJohn Levon 11551f5207b7SJohn Levon set_true_false_states(compare_id, state_name, NULL, NULL, false_state); 11561f5207b7SJohn Levon } 11571f5207b7SJohn Levon 11581f5207b7SJohn Levon static int is_plus_one(struct expression *expr) 11591f5207b7SJohn Levon { 11601f5207b7SJohn Levon sval_t sval; 11611f5207b7SJohn Levon 11621f5207b7SJohn Levon if (expr->type != EXPR_BINOP || expr->op != '+') 11631f5207b7SJohn Levon return 0; 11641f5207b7SJohn Levon if (!get_implied_value(expr->right, &sval) || sval.value != 1) 11651f5207b7SJohn Levon return 0; 11661f5207b7SJohn Levon return 1; 11671f5207b7SJohn Levon } 11681f5207b7SJohn Levon 11691f5207b7SJohn Levon static int is_minus_one(struct expression *expr) 11701f5207b7SJohn Levon { 11711f5207b7SJohn Levon sval_t sval; 11721f5207b7SJohn Levon 11731f5207b7SJohn Levon if (expr->type != EXPR_BINOP || expr->op != '-') 11741f5207b7SJohn Levon return 0; 11751f5207b7SJohn Levon if (!get_implied_value(expr->right, &sval) || sval.value != 1) 11761f5207b7SJohn Levon return 0; 11771f5207b7SJohn Levon return 1; 11781f5207b7SJohn Levon } 11791f5207b7SJohn Levon 11801f5207b7SJohn Levon static void move_plus_to_minus_helper(struct expression **left_p, struct expression **right_p) 11811f5207b7SJohn Levon { 11821f5207b7SJohn Levon struct expression *left = *left_p; 11831f5207b7SJohn Levon struct expression *right = *right_p; 11841f5207b7SJohn Levon 11851f5207b7SJohn Levon /* 11861f5207b7SJohn Levon * These two are basically equivalent: "foo + 1 != bar" and 11871f5207b7SJohn Levon * "foo != bar - 1". There are issues with signedness and integer 11881f5207b7SJohn Levon * overflows. There are also issues with type as well. But let's 11891f5207b7SJohn Levon * pretend we can ignore all that stuff for now. 11901f5207b7SJohn Levon * 11911f5207b7SJohn Levon */ 11921f5207b7SJohn Levon 11931f5207b7SJohn Levon if (!is_plus_one(left)) 11941f5207b7SJohn Levon return; 11951f5207b7SJohn Levon 11961f5207b7SJohn Levon *left_p = left->left; 11971f5207b7SJohn Levon *right_p = binop_expression(right, '-', left->right); 11981f5207b7SJohn Levon } 11991f5207b7SJohn Levon 12001f5207b7SJohn Levon static void move_plus_to_minus(struct expression **left_p, struct expression **right_p) 12011f5207b7SJohn Levon { 12021f5207b7SJohn Levon if (is_plus_one(*left_p) && is_plus_one(*right_p)) 12031f5207b7SJohn Levon return; 12041f5207b7SJohn Levon 12051f5207b7SJohn Levon move_plus_to_minus_helper(left_p, right_p); 12061f5207b7SJohn Levon move_plus_to_minus_helper(right_p, left_p); 12071f5207b7SJohn Levon } 12081f5207b7SJohn Levon 12091f5207b7SJohn Levon static void handle_comparison(struct expression *left_expr, int op, struct expression *right_expr, char **_state_name, struct smatch_state **_false_state) 12101f5207b7SJohn Levon { 12111f5207b7SJohn Levon char *left = NULL; 12121f5207b7SJohn Levon char *right = NULL; 12131f5207b7SJohn Levon struct symbol *left_sym, *right_sym; 12141f5207b7SJohn Levon struct var_sym_list *left_vsl = NULL; 12151f5207b7SJohn Levon struct var_sym_list *right_vsl = NULL; 12161f5207b7SJohn Levon int false_op; 12171f5207b7SJohn Levon int orig_comparison; 12181f5207b7SJohn Levon struct smatch_state *true_state, *false_state; 12191f5207b7SJohn Levon static char state_name[256]; 12201f5207b7SJohn Levon struct stree *pre_stree; 12211f5207b7SJohn Levon sval_t sval; 12221f5207b7SJohn Levon 12231f5207b7SJohn Levon if (!left_expr || !right_expr) 12241f5207b7SJohn Levon return; 12251f5207b7SJohn Levon 12261f5207b7SJohn Levon left_expr = strip_parens(left_expr); 12271f5207b7SJohn Levon right_expr = strip_parens(right_expr); 12281f5207b7SJohn Levon 12291f5207b7SJohn Levon while (left_expr->type == EXPR_ASSIGNMENT) 12301f5207b7SJohn Levon left_expr = strip_parens(left_expr->left); 12311f5207b7SJohn Levon while (right_expr->type == EXPR_ASSIGNMENT) 12321f5207b7SJohn Levon right_expr = strip_parens(right_expr->left); 12331f5207b7SJohn Levon 12341f5207b7SJohn Levon false_op = negate_comparison(op); 12351f5207b7SJohn Levon 12361f5207b7SJohn Levon move_plus_to_minus(&left_expr, &right_expr); 12371f5207b7SJohn Levon 12381f5207b7SJohn Levon if (op == SPECIAL_UNSIGNED_LT && 12391f5207b7SJohn Levon get_implied_value(left_expr, &sval) && 12401f5207b7SJohn Levon sval.value == 0) 12411f5207b7SJohn Levon false_op = SPECIAL_EQUAL; 12421f5207b7SJohn Levon 12431f5207b7SJohn Levon if (op == SPECIAL_UNSIGNED_GT && 12441f5207b7SJohn Levon get_implied_value(right_expr, &sval) && 12451f5207b7SJohn Levon sval.value == 0) 12461f5207b7SJohn Levon false_op = SPECIAL_EQUAL; 12471f5207b7SJohn Levon 12481f5207b7SJohn Levon left = chunk_to_var_sym(left_expr, &left_sym); 12491f5207b7SJohn Levon if (!left) 12501f5207b7SJohn Levon goto free; 12511f5207b7SJohn Levon if (left_sym) 12521f5207b7SJohn Levon add_var_sym(&left_vsl, left, left_sym); 12531f5207b7SJohn Levon else 12541f5207b7SJohn Levon left_vsl = expr_to_vsl(left_expr); 12551f5207b7SJohn Levon right = chunk_to_var_sym(right_expr, &right_sym); 12561f5207b7SJohn Levon if (!right) 12571f5207b7SJohn Levon goto free; 12581f5207b7SJohn Levon if (right_sym) 12591f5207b7SJohn Levon add_var_sym(&right_vsl, right, right_sym); 12601f5207b7SJohn Levon else 12611f5207b7SJohn Levon right_vsl = expr_to_vsl(right_expr); 12621f5207b7SJohn Levon 12631f5207b7SJohn Levon if (strcmp(left, right) > 0) { 12641f5207b7SJohn Levon char *tmp_name = left; 12651f5207b7SJohn Levon struct var_sym_list *tmp_vsl = left_vsl; 12661f5207b7SJohn Levon struct expression *tmp_expr = left_expr; 12671f5207b7SJohn Levon 12681f5207b7SJohn Levon left = right; 12691f5207b7SJohn Levon left_vsl = right_vsl; 12701f5207b7SJohn Levon left_expr = right_expr; 12711f5207b7SJohn Levon right = tmp_name; 12721f5207b7SJohn Levon right_vsl = tmp_vsl; 12731f5207b7SJohn Levon right_expr = tmp_expr; 12741f5207b7SJohn Levon op = flip_comparison(op); 12751f5207b7SJohn Levon false_op = flip_comparison(false_op); 12761f5207b7SJohn Levon } 12771f5207b7SJohn Levon 12781f5207b7SJohn Levon orig_comparison = get_comparison(left_expr, right_expr); 12791f5207b7SJohn Levon op = filter_comparison(orig_comparison, op); 12801f5207b7SJohn Levon false_op = filter_comparison(orig_comparison, false_op); 12811f5207b7SJohn Levon 12821f5207b7SJohn Levon snprintf(state_name, sizeof(state_name), "%s vs %s", left, right); 12831f5207b7SJohn Levon true_state = alloc_compare_state( 12841f5207b7SJohn Levon left_expr, left, left_vsl, 12851f5207b7SJohn Levon op, 12861f5207b7SJohn Levon right_expr, right, right_vsl); 12871f5207b7SJohn Levon false_state = alloc_compare_state( 12881f5207b7SJohn Levon left_expr, left, left_vsl, 12891f5207b7SJohn Levon false_op, 12901f5207b7SJohn Levon right_expr, right, right_vsl); 12911f5207b7SJohn Levon 12921f5207b7SJohn Levon pre_stree = clone_stree(__get_cur_stree()); 12931f5207b7SJohn Levon update_tf_data(pre_stree, left_expr, left, left_vsl, right_expr, right, right_vsl, op, false_op); 12941f5207b7SJohn Levon free_stree(&pre_stree); 12951f5207b7SJohn Levon 12961f5207b7SJohn Levon set_true_false_states(compare_id, state_name, NULL, true_state, false_state); 12971f5207b7SJohn Levon __compare_param_limit_hook(left_expr, right_expr, state_name, true_state, false_state); 12981f5207b7SJohn Levon save_link(left_expr, state_name); 12991f5207b7SJohn Levon save_link(right_expr, state_name); 13001f5207b7SJohn Levon 13011f5207b7SJohn Levon if (_false_state) 13021f5207b7SJohn Levon *_false_state = false_state; 13031f5207b7SJohn Levon if (_state_name) 13041f5207b7SJohn Levon *_state_name = state_name; 13051f5207b7SJohn Levon free: 13061f5207b7SJohn Levon free_string(left); 13071f5207b7SJohn Levon free_string(right); 13081f5207b7SJohn Levon } 13091f5207b7SJohn Levon 13101f5207b7SJohn Levon void __comparison_match_condition(struct expression *expr) 13111f5207b7SJohn Levon { 13121f5207b7SJohn Levon struct expression *left, *right, *new_left, *new_right, *tmp; 13131f5207b7SJohn Levon struct smatch_state *false_state = NULL; 13141f5207b7SJohn Levon char *state_name = NULL; 13151f5207b7SJohn Levon int redo, count; 13161f5207b7SJohn Levon 13171f5207b7SJohn Levon if (expr->type != EXPR_COMPARE) 13181f5207b7SJohn Levon return; 13191f5207b7SJohn Levon 13201f5207b7SJohn Levon handle_comparison(expr->left, expr->op, expr->right, &state_name, &false_state); 13211f5207b7SJohn Levon if (false_state && state_name) 13221f5207b7SJohn Levon handle_for_loops(expr, state_name, false_state); 13231f5207b7SJohn Levon 13241f5207b7SJohn Levon left = strip_parens(expr->left); 13251f5207b7SJohn Levon right = strip_parens(expr->right); 13261f5207b7SJohn Levon 13271f5207b7SJohn Levon if (left->type == EXPR_BINOP && left->op == '+') { 13281f5207b7SJohn Levon new_left = left->left; 13291f5207b7SJohn Levon new_right = binop_expression(right, '-', left->right); 13301f5207b7SJohn Levon handle_comparison(new_left, expr->op, new_right, NULL, NULL); 13311f5207b7SJohn Levon 13321f5207b7SJohn Levon new_left = left->right; 13331f5207b7SJohn Levon new_right = binop_expression(right, '-', left->left); 13341f5207b7SJohn Levon handle_comparison(new_left, expr->op, new_right, NULL, NULL); 13351f5207b7SJohn Levon } 13361f5207b7SJohn Levon 13371f5207b7SJohn Levon 13381f5207b7SJohn Levon redo = 0; 13391f5207b7SJohn Levon left = strip_parens(expr->left); 13401f5207b7SJohn Levon right = strip_parens(expr->right); 13411f5207b7SJohn Levon if (get_last_expr_from_expression_stmt(expr->left)) { 13421f5207b7SJohn Levon left = get_last_expr_from_expression_stmt(expr->left); 13431f5207b7SJohn Levon redo = 1; 13441f5207b7SJohn Levon } 13451f5207b7SJohn Levon if (get_last_expr_from_expression_stmt(expr->right)) { 13461f5207b7SJohn Levon right = get_last_expr_from_expression_stmt(expr->right); 13471f5207b7SJohn Levon redo = 1; 13481f5207b7SJohn Levon } 13491f5207b7SJohn Levon 13501f5207b7SJohn Levon if (!redo) 13511f5207b7SJohn Levon return; 13521f5207b7SJohn Levon 13531f5207b7SJohn Levon count = 0; 13541f5207b7SJohn Levon while ((tmp = get_assigned_expr(left))) { 13551f5207b7SJohn Levon if (count++ > 3) 13561f5207b7SJohn Levon break; 13571f5207b7SJohn Levon left = strip_expr(tmp); 13581f5207b7SJohn Levon } 13591f5207b7SJohn Levon count = 0; 13601f5207b7SJohn Levon while ((tmp = get_assigned_expr(right))) { 13611f5207b7SJohn Levon if (count++ > 3) 13621f5207b7SJohn Levon break; 13631f5207b7SJohn Levon right = strip_expr(tmp); 13641f5207b7SJohn Levon } 13651f5207b7SJohn Levon 13661f5207b7SJohn Levon handle_comparison(left, expr->op, right, NULL, NULL); 13671f5207b7SJohn Levon } 13681f5207b7SJohn Levon 13691f5207b7SJohn Levon static void add_comparison_var_sym( 13701f5207b7SJohn Levon struct expression *left_expr, 13711f5207b7SJohn Levon const char *left_name, struct var_sym_list *left_vsl, 13721f5207b7SJohn Levon int comparison, 13731f5207b7SJohn Levon struct expression *right_expr, 13741f5207b7SJohn Levon const char *right_name, struct var_sym_list *right_vsl) 13751f5207b7SJohn Levon { 13761f5207b7SJohn Levon struct smatch_state *state; 13771f5207b7SJohn Levon struct var_sym *vs; 13781f5207b7SJohn Levon char state_name[256]; 13791f5207b7SJohn Levon 13801f5207b7SJohn Levon if (strcmp(left_name, right_name) > 0) { 13811f5207b7SJohn Levon struct expression *tmp_expr = left_expr; 13821f5207b7SJohn Levon const char *tmp_name = left_name; 13831f5207b7SJohn Levon struct var_sym_list *tmp_vsl = left_vsl; 13841f5207b7SJohn Levon 13851f5207b7SJohn Levon left_expr = right_expr; 13861f5207b7SJohn Levon left_name = right_name; 13871f5207b7SJohn Levon left_vsl = right_vsl; 13881f5207b7SJohn Levon right_expr = tmp_expr; 13891f5207b7SJohn Levon right_name = tmp_name; 13901f5207b7SJohn Levon right_vsl = tmp_vsl; 13911f5207b7SJohn Levon comparison = flip_comparison(comparison); 13921f5207b7SJohn Levon } 13931f5207b7SJohn Levon snprintf(state_name, sizeof(state_name), "%s vs %s", left_name, right_name); 13941f5207b7SJohn Levon state = alloc_compare_state( 13951f5207b7SJohn Levon left_expr, left_name, left_vsl, 13961f5207b7SJohn Levon comparison, 13971f5207b7SJohn Levon right_expr, right_name, right_vsl); 13981f5207b7SJohn Levon 13991f5207b7SJohn Levon set_state(compare_id, state_name, NULL, state); 14001f5207b7SJohn Levon 14011f5207b7SJohn Levon FOR_EACH_PTR(left_vsl, vs) { 14021f5207b7SJohn Levon save_link_var_sym(vs->var, vs->sym, state_name); 14031f5207b7SJohn Levon } END_FOR_EACH_PTR(vs); 14041f5207b7SJohn Levon FOR_EACH_PTR(right_vsl, vs) { 14051f5207b7SJohn Levon save_link_var_sym(vs->var, vs->sym, state_name); 14061f5207b7SJohn Levon } END_FOR_EACH_PTR(vs); 14071f5207b7SJohn Levon } 14081f5207b7SJohn Levon 14091f5207b7SJohn Levon static void add_comparison(struct expression *left, int comparison, struct expression *right) 14101f5207b7SJohn Levon { 14111f5207b7SJohn Levon char *left_name = NULL; 14121f5207b7SJohn Levon char *right_name = NULL; 14131f5207b7SJohn Levon struct symbol *left_sym, *right_sym; 14141f5207b7SJohn Levon struct var_sym_list *left_vsl, *right_vsl; 14151f5207b7SJohn Levon struct smatch_state *state; 14161f5207b7SJohn Levon char state_name[256]; 14171f5207b7SJohn Levon 14181f5207b7SJohn Levon left_name = chunk_to_var_sym(left, &left_sym); 14191f5207b7SJohn Levon if (!left_name) 14201f5207b7SJohn Levon goto free; 14211f5207b7SJohn Levon left_vsl = expr_to_vsl(left); 14221f5207b7SJohn Levon right_name = chunk_to_var_sym(right, &right_sym); 14231f5207b7SJohn Levon if (!right_name) 14241f5207b7SJohn Levon goto free; 14251f5207b7SJohn Levon right_vsl = expr_to_vsl(right); 14261f5207b7SJohn Levon 14271f5207b7SJohn Levon if (strcmp(left_name, right_name) > 0) { 14281f5207b7SJohn Levon struct expression *tmp_expr = left; 14291f5207b7SJohn Levon struct symbol *tmp_sym = left_sym; 14301f5207b7SJohn Levon char *tmp_name = left_name; 14311f5207b7SJohn Levon struct var_sym_list *tmp_vsl = left_vsl; 14321f5207b7SJohn Levon 14331f5207b7SJohn Levon left = right; 14341f5207b7SJohn Levon left_name = right_name; 14351f5207b7SJohn Levon left_sym = right_sym; 14361f5207b7SJohn Levon left_vsl = right_vsl; 14371f5207b7SJohn Levon right = tmp_expr; 14381f5207b7SJohn Levon right_name = tmp_name; 14391f5207b7SJohn Levon right_sym = tmp_sym; 14401f5207b7SJohn Levon right_vsl = tmp_vsl; 14411f5207b7SJohn Levon comparison = flip_comparison(comparison); 14421f5207b7SJohn Levon } 14431f5207b7SJohn Levon snprintf(state_name, sizeof(state_name), "%s vs %s", left_name, right_name); 14441f5207b7SJohn Levon state = alloc_compare_state( 14451f5207b7SJohn Levon left, left_name, left_vsl, 14461f5207b7SJohn Levon comparison, 14471f5207b7SJohn Levon right, right_name, right_vsl); 14481f5207b7SJohn Levon 14491f5207b7SJohn Levon set_state(compare_id, state_name, NULL, state); 14501f5207b7SJohn Levon save_link(left, state_name); 14511f5207b7SJohn Levon save_link(right, state_name); 14521f5207b7SJohn Levon 14531f5207b7SJohn Levon free: 14541f5207b7SJohn Levon free_string(left_name); 14551f5207b7SJohn Levon free_string(right_name); 14561f5207b7SJohn Levon } 14571f5207b7SJohn Levon 14581f5207b7SJohn Levon static void match_assign_add(struct expression *expr) 14591f5207b7SJohn Levon { 14601f5207b7SJohn Levon struct expression *right; 14611f5207b7SJohn Levon struct expression *r_left, *r_right; 14621f5207b7SJohn Levon sval_t left_tmp, right_tmp; 14631f5207b7SJohn Levon 14641f5207b7SJohn Levon right = strip_expr(expr->right); 14651f5207b7SJohn Levon r_left = strip_expr(right->left); 14661f5207b7SJohn Levon r_right = strip_expr(right->right); 14671f5207b7SJohn Levon 14681f5207b7SJohn Levon get_absolute_min(r_left, &left_tmp); 14691f5207b7SJohn Levon get_absolute_min(r_right, &right_tmp); 14701f5207b7SJohn Levon 14711f5207b7SJohn Levon if (left_tmp.value > 0) 14721f5207b7SJohn Levon add_comparison(expr->left, '>', r_right); 14731f5207b7SJohn Levon else if (left_tmp.value == 0) 14741f5207b7SJohn Levon add_comparison(expr->left, SPECIAL_GTE, r_right); 14751f5207b7SJohn Levon 14761f5207b7SJohn Levon if (right_tmp.value > 0) 14771f5207b7SJohn Levon add_comparison(expr->left, '>', r_left); 14781f5207b7SJohn Levon else if (right_tmp.value == 0) 14791f5207b7SJohn Levon add_comparison(expr->left, SPECIAL_GTE, r_left); 14801f5207b7SJohn Levon } 14811f5207b7SJohn Levon 14821f5207b7SJohn Levon static void match_assign_sub(struct expression *expr) 14831f5207b7SJohn Levon { 14841f5207b7SJohn Levon struct expression *right; 14851f5207b7SJohn Levon struct expression *r_left, *r_right; 14861f5207b7SJohn Levon int comparison; 14871f5207b7SJohn Levon sval_t min; 14881f5207b7SJohn Levon 14891f5207b7SJohn Levon right = strip_expr(expr->right); 14901f5207b7SJohn Levon r_left = strip_expr(right->left); 14911f5207b7SJohn Levon r_right = strip_expr(right->right); 14921f5207b7SJohn Levon 14931f5207b7SJohn Levon if (get_absolute_min(r_right, &min) && sval_is_negative(min)) 14941f5207b7SJohn Levon return; 14951f5207b7SJohn Levon 14961f5207b7SJohn Levon comparison = get_comparison(r_left, r_right); 14971f5207b7SJohn Levon 14981f5207b7SJohn Levon switch (comparison) { 14991f5207b7SJohn Levon case '>': 15001f5207b7SJohn Levon case SPECIAL_GTE: 15011f5207b7SJohn Levon if (implied_not_equal(r_right, 0)) 15021f5207b7SJohn Levon add_comparison(expr->left, '>', r_left); 15031f5207b7SJohn Levon else 15041f5207b7SJohn Levon add_comparison(expr->left, SPECIAL_GTE, r_left); 15051f5207b7SJohn Levon return; 15061f5207b7SJohn Levon } 15071f5207b7SJohn Levon } 15081f5207b7SJohn Levon 15091f5207b7SJohn Levon static void match_assign_divide(struct expression *expr) 15101f5207b7SJohn Levon { 15111f5207b7SJohn Levon struct expression *right; 15121f5207b7SJohn Levon struct expression *r_left, *r_right; 15131f5207b7SJohn Levon sval_t min; 15141f5207b7SJohn Levon 15151f5207b7SJohn Levon right = strip_expr(expr->right); 15161f5207b7SJohn Levon r_left = strip_expr(right->left); 15171f5207b7SJohn Levon r_right = strip_expr(right->right); 15181f5207b7SJohn Levon if (!get_implied_min(r_right, &min) || min.value <= 1) 15191f5207b7SJohn Levon return; 15201f5207b7SJohn Levon 15211f5207b7SJohn Levon add_comparison(expr->left, '<', r_left); 15221f5207b7SJohn Levon } 15231f5207b7SJohn Levon 15241f5207b7SJohn Levon static void match_binop_assign(struct expression *expr) 15251f5207b7SJohn Levon { 15261f5207b7SJohn Levon struct expression *right; 15271f5207b7SJohn Levon 15281f5207b7SJohn Levon right = strip_expr(expr->right); 15291f5207b7SJohn Levon if (right->op == '+') 15301f5207b7SJohn Levon match_assign_add(expr); 15311f5207b7SJohn Levon if (right->op == '-') 15321f5207b7SJohn Levon match_assign_sub(expr); 15331f5207b7SJohn Levon if (right->op == '/') 15341f5207b7SJohn Levon match_assign_divide(expr); 15351f5207b7SJohn Levon } 15361f5207b7SJohn Levon 15371f5207b7SJohn Levon static void copy_comparisons(struct expression *left, struct expression *right) 15381f5207b7SJohn Levon { 15391f5207b7SJohn Levon struct string_list *links; 15401f5207b7SJohn Levon struct smatch_state *state; 15411f5207b7SJohn Levon struct compare_data *data; 15421f5207b7SJohn Levon struct symbol *left_sym, *right_sym; 15431f5207b7SJohn Levon char *left_var = NULL; 15441f5207b7SJohn Levon char *right_var = NULL; 15451f5207b7SJohn Levon struct var_sym_list *left_vsl; 15461f5207b7SJohn Levon struct expression *expr; 15471f5207b7SJohn Levon const char *var; 15481f5207b7SJohn Levon struct var_sym_list *vsl; 15491f5207b7SJohn Levon int comparison; 15501f5207b7SJohn Levon char *tmp; 15511f5207b7SJohn Levon 15521f5207b7SJohn Levon left_var = chunk_to_var_sym(left, &left_sym); 15531f5207b7SJohn Levon if (!left_var) 15541f5207b7SJohn Levon goto done; 15551f5207b7SJohn Levon left_vsl = expr_to_vsl(left); 15561f5207b7SJohn Levon right_var = chunk_to_var_sym(right, &right_sym); 15571f5207b7SJohn Levon if (!right_var) 15581f5207b7SJohn Levon goto done; 15591f5207b7SJohn Levon 15601f5207b7SJohn Levon state = get_state(link_id, right_var, right_sym); 15611f5207b7SJohn Levon if (!state) 15621f5207b7SJohn Levon return; 15631f5207b7SJohn Levon links = state->data; 15641f5207b7SJohn Levon 15651f5207b7SJohn Levon FOR_EACH_PTR(links, tmp) { 15661f5207b7SJohn Levon state = get_state(compare_id, tmp, NULL); 15671f5207b7SJohn Levon if (!state || !state->data) 15681f5207b7SJohn Levon continue; 15691f5207b7SJohn Levon data = state->data; 15701f5207b7SJohn Levon comparison = data->comparison; 15711f5207b7SJohn Levon expr = data->right; 15721f5207b7SJohn Levon var = data->right_var; 15731f5207b7SJohn Levon vsl = data->right_vsl; 15741f5207b7SJohn Levon if (strcmp(var, right_var) == 0) { 15751f5207b7SJohn Levon expr = data->left; 15761f5207b7SJohn Levon var = data->left_var; 15771f5207b7SJohn Levon vsl = data->left_vsl; 15781f5207b7SJohn Levon comparison = flip_comparison(comparison); 15791f5207b7SJohn Levon } 15801f5207b7SJohn Levon /* n = copy_from_user(dest, src, n); leads to n <= n which is nonsense */ 15811f5207b7SJohn Levon if (strcmp(left_var, var) == 0) 15821f5207b7SJohn Levon continue; 15831f5207b7SJohn Levon add_comparison_var_sym(left, left_var, left_vsl, comparison, expr, var, vsl); 15841f5207b7SJohn Levon } END_FOR_EACH_PTR(tmp); 15851f5207b7SJohn Levon 15861f5207b7SJohn Levon done: 15871f5207b7SJohn Levon free_string(right_var); 15881f5207b7SJohn Levon } 15891f5207b7SJohn Levon 15901f5207b7SJohn Levon static void match_assign(struct expression *expr) 15911f5207b7SJohn Levon { 15921f5207b7SJohn Levon struct expression *right; 15931f5207b7SJohn Levon 15941f5207b7SJohn Levon if (expr->op != '=') 15951f5207b7SJohn Levon return; 15961f5207b7SJohn Levon if (__in_fake_assign || outside_of_function()) 15971f5207b7SJohn Levon return; 15981f5207b7SJohn Levon 15991f5207b7SJohn Levon if (is_struct(expr->left)) 16001f5207b7SJohn Levon return; 16011f5207b7SJohn Levon 16021f5207b7SJohn Levon if (is_self_assign(expr)) 16031f5207b7SJohn Levon return; 16041f5207b7SJohn Levon 16051f5207b7SJohn Levon copy_comparisons(expr->left, expr->right); 16061f5207b7SJohn Levon add_comparison(expr->left, SPECIAL_EQUAL, expr->right); 16071f5207b7SJohn Levon 16081f5207b7SJohn Levon right = strip_expr(expr->right); 16091f5207b7SJohn Levon if (right->type == EXPR_BINOP) 16101f5207b7SJohn Levon match_binop_assign(expr); 16111f5207b7SJohn Levon } 16121f5207b7SJohn Levon 16131f5207b7SJohn Levon int get_comparison_strings(const char *one, const char *two) 16141f5207b7SJohn Levon { 16151f5207b7SJohn Levon char buf[256]; 16161f5207b7SJohn Levon struct smatch_state *state; 16171f5207b7SJohn Levon int invert = 0; 16181f5207b7SJohn Levon int ret = 0; 16191f5207b7SJohn Levon 16201f5207b7SJohn Levon if (!one || !two) 16211f5207b7SJohn Levon return 0; 16221f5207b7SJohn Levon 16231f5207b7SJohn Levon if (strcmp(one, two) == 0) 16241f5207b7SJohn Levon return SPECIAL_EQUAL; 16251f5207b7SJohn Levon 16261f5207b7SJohn Levon if (strcmp(one, two) > 0) { 16271f5207b7SJohn Levon const char *tmp = one; 16281f5207b7SJohn Levon 16291f5207b7SJohn Levon one = two; 16301f5207b7SJohn Levon two = tmp; 16311f5207b7SJohn Levon invert = 1; 16321f5207b7SJohn Levon } 16331f5207b7SJohn Levon 16341f5207b7SJohn Levon snprintf(buf, sizeof(buf), "%s vs %s", one, two); 16351f5207b7SJohn Levon state = get_state(compare_id, buf, NULL); 16361f5207b7SJohn Levon if (state) 16371f5207b7SJohn Levon ret = state_to_comparison(state); 16381f5207b7SJohn Levon 16391f5207b7SJohn Levon if (invert) 16401f5207b7SJohn Levon ret = flip_comparison(ret); 16411f5207b7SJohn Levon 16421f5207b7SJohn Levon return ret; 16431f5207b7SJohn Levon } 16441f5207b7SJohn Levon 1645*efe51d0cSJohn Levon static int get_comparison_helper(struct expression *a, struct expression *b, bool use_extra) 16461f5207b7SJohn Levon { 16471f5207b7SJohn Levon char *one = NULL; 16481f5207b7SJohn Levon char *two = NULL; 16491f5207b7SJohn Levon int ret = 0; 16501f5207b7SJohn Levon 16511f5207b7SJohn Levon if (!a || !b) 16521f5207b7SJohn Levon return 0; 16531f5207b7SJohn Levon 16541f5207b7SJohn Levon a = strip_parens(a); 16551f5207b7SJohn Levon b = strip_parens(b); 16561f5207b7SJohn Levon 16571f5207b7SJohn Levon move_plus_to_minus(&a, &b); 16581f5207b7SJohn Levon 16591f5207b7SJohn Levon one = chunk_to_var(a); 16601f5207b7SJohn Levon if (!one) 16611f5207b7SJohn Levon goto free; 16621f5207b7SJohn Levon two = chunk_to_var(b); 16631f5207b7SJohn Levon if (!two) 16641f5207b7SJohn Levon goto free; 16651f5207b7SJohn Levon 16661f5207b7SJohn Levon ret = get_comparison_strings(one, two); 16671f5207b7SJohn Levon if (ret) 16681f5207b7SJohn Levon goto free; 16691f5207b7SJohn Levon 16701f5207b7SJohn Levon if (is_plus_one(a) || is_minus_one(a)) { 16711f5207b7SJohn Levon free_string(one); 16721f5207b7SJohn Levon one = chunk_to_var(a->left); 16731f5207b7SJohn Levon ret = get_comparison_strings(one, two); 16741f5207b7SJohn Levon } else if (is_plus_one(b) || is_minus_one(b)) { 16751f5207b7SJohn Levon free_string(two); 16761f5207b7SJohn Levon two = chunk_to_var(b->left); 16771f5207b7SJohn Levon ret = get_comparison_strings(one, two); 16781f5207b7SJohn Levon } 16791f5207b7SJohn Levon 16801f5207b7SJohn Levon if (!ret) 16811f5207b7SJohn Levon goto free; 16821f5207b7SJohn Levon 16831f5207b7SJohn Levon if ((is_plus_one(a) || is_minus_one(b)) && ret == '<') 16841f5207b7SJohn Levon ret = SPECIAL_LTE; 16851f5207b7SJohn Levon else if ((is_minus_one(a) || is_plus_one(b)) && ret == '>') 16861f5207b7SJohn Levon ret = SPECIAL_GTE; 16871f5207b7SJohn Levon else 16881f5207b7SJohn Levon ret = 0; 16891f5207b7SJohn Levon 16901f5207b7SJohn Levon free: 16911f5207b7SJohn Levon free_string(one); 16921f5207b7SJohn Levon free_string(two); 16931f5207b7SJohn Levon 1694*efe51d0cSJohn Levon if (!ret && use_extra) 16951f5207b7SJohn Levon return comparison_from_extra(a, b); 16961f5207b7SJohn Levon return ret; 16971f5207b7SJohn Levon } 16981f5207b7SJohn Levon 1699*efe51d0cSJohn Levon int get_comparison(struct expression *a, struct expression *b) 1700*efe51d0cSJohn Levon { 1701*efe51d0cSJohn Levon return get_comparison_helper(a, b, true); 1702*efe51d0cSJohn Levon } 1703*efe51d0cSJohn Levon 1704*efe51d0cSJohn Levon int get_comparison_no_extra(struct expression *a, struct expression *b) 1705*efe51d0cSJohn Levon { 1706*efe51d0cSJohn Levon return get_comparison_helper(a, b, false); 1707*efe51d0cSJohn Levon } 1708*efe51d0cSJohn Levon 17091f5207b7SJohn Levon int possible_comparison(struct expression *a, int comparison, struct expression *b) 17101f5207b7SJohn Levon { 17111f5207b7SJohn Levon char *one = NULL; 17121f5207b7SJohn Levon char *two = NULL; 17131f5207b7SJohn Levon int ret = 0; 17141f5207b7SJohn Levon char buf[256]; 17151f5207b7SJohn Levon struct sm_state *sm; 17161f5207b7SJohn Levon int saved; 17171f5207b7SJohn Levon 17181f5207b7SJohn Levon one = chunk_to_var(a); 17191f5207b7SJohn Levon if (!one) 17201f5207b7SJohn Levon goto free; 17211f5207b7SJohn Levon two = chunk_to_var(b); 17221f5207b7SJohn Levon if (!two) 17231f5207b7SJohn Levon goto free; 17241f5207b7SJohn Levon 17251f5207b7SJohn Levon 17261f5207b7SJohn Levon if (strcmp(one, two) == 0 && comparison == SPECIAL_EQUAL) { 17271f5207b7SJohn Levon ret = 1; 17281f5207b7SJohn Levon goto free; 17291f5207b7SJohn Levon } 17301f5207b7SJohn Levon 17311f5207b7SJohn Levon if (strcmp(one, two) > 0) { 17321f5207b7SJohn Levon char *tmp = one; 17331f5207b7SJohn Levon 17341f5207b7SJohn Levon one = two; 17351f5207b7SJohn Levon two = tmp; 17361f5207b7SJohn Levon comparison = flip_comparison(comparison); 17371f5207b7SJohn Levon } 17381f5207b7SJohn Levon 17391f5207b7SJohn Levon snprintf(buf, sizeof(buf), "%s vs %s", one, two); 17401f5207b7SJohn Levon sm = get_sm_state(compare_id, buf, NULL); 17411f5207b7SJohn Levon if (!sm) 17421f5207b7SJohn Levon goto free; 17431f5207b7SJohn Levon 17441f5207b7SJohn Levon FOR_EACH_PTR(sm->possible, sm) { 17451f5207b7SJohn Levon if (!sm->state->data) 17461f5207b7SJohn Levon continue; 17471f5207b7SJohn Levon saved = ((struct compare_data *)sm->state->data)->comparison; 17481f5207b7SJohn Levon if (saved == comparison) 17491f5207b7SJohn Levon ret = 1; 17501f5207b7SJohn Levon if (comparison == SPECIAL_EQUAL && 17511f5207b7SJohn Levon (saved == SPECIAL_LTE || 17521f5207b7SJohn Levon saved == SPECIAL_GTE || 17531f5207b7SJohn Levon saved == SPECIAL_UNSIGNED_LTE || 17541f5207b7SJohn Levon saved == SPECIAL_UNSIGNED_GTE)) 17551f5207b7SJohn Levon ret = 1; 17561f5207b7SJohn Levon if (ret == 1) 17571f5207b7SJohn Levon goto free; 17581f5207b7SJohn Levon } END_FOR_EACH_PTR(sm); 17591f5207b7SJohn Levon 17601f5207b7SJohn Levon return ret; 17611f5207b7SJohn Levon free: 17621f5207b7SJohn Levon free_string(one); 17631f5207b7SJohn Levon free_string(two); 17641f5207b7SJohn Levon return ret; 17651f5207b7SJohn Levon } 17661f5207b7SJohn Levon 17671f5207b7SJohn Levon struct state_list *get_all_comparisons(struct expression *expr) 17681f5207b7SJohn Levon { 17691f5207b7SJohn Levon struct smatch_state *state; 17701f5207b7SJohn Levon struct string_list *links; 17711f5207b7SJohn Levon struct state_list *ret = NULL; 17721f5207b7SJohn Levon struct sm_state *sm; 17731f5207b7SJohn Levon char *tmp; 17741f5207b7SJohn Levon 17751f5207b7SJohn Levon state = get_state_chunk(link_id, expr); 17761f5207b7SJohn Levon if (!state) 17771f5207b7SJohn Levon return NULL; 17781f5207b7SJohn Levon links = state->data; 17791f5207b7SJohn Levon 17801f5207b7SJohn Levon FOR_EACH_PTR(links, tmp) { 17811f5207b7SJohn Levon sm = get_sm_state(compare_id, tmp, NULL); 17821f5207b7SJohn Levon if (!sm) 17831f5207b7SJohn Levon continue; 17841f5207b7SJohn Levon // FIXME have to compare name with vsl 17851f5207b7SJohn Levon add_ptr_list(&ret, sm); 17861f5207b7SJohn Levon } END_FOR_EACH_PTR(tmp); 17871f5207b7SJohn Levon 17881f5207b7SJohn Levon return ret; 17891f5207b7SJohn Levon } 17901f5207b7SJohn Levon 17911f5207b7SJohn Levon struct state_list *get_all_possible_equal_comparisons(struct expression *expr) 17921f5207b7SJohn Levon { 17931f5207b7SJohn Levon struct smatch_state *state; 17941f5207b7SJohn Levon struct string_list *links; 17951f5207b7SJohn Levon struct state_list *ret = NULL; 17961f5207b7SJohn Levon struct sm_state *sm; 17971f5207b7SJohn Levon char *tmp; 17981f5207b7SJohn Levon 17991f5207b7SJohn Levon state = get_state_chunk(link_id, expr); 18001f5207b7SJohn Levon if (!state) 18011f5207b7SJohn Levon return NULL; 18021f5207b7SJohn Levon links = state->data; 18031f5207b7SJohn Levon 18041f5207b7SJohn Levon FOR_EACH_PTR(links, tmp) { 18051f5207b7SJohn Levon sm = get_sm_state(compare_id, tmp, NULL); 18061f5207b7SJohn Levon if (!sm) 18071f5207b7SJohn Levon continue; 18081f5207b7SJohn Levon if (!strchr(sm->state->name, '=')) 18091f5207b7SJohn Levon continue; 18101f5207b7SJohn Levon if (strcmp(sm->state->name, "!=") == 0) 18111f5207b7SJohn Levon continue; 18121f5207b7SJohn Levon add_ptr_list(&ret, sm); 18131f5207b7SJohn Levon } END_FOR_EACH_PTR(tmp); 18141f5207b7SJohn Levon 18151f5207b7SJohn Levon return ret; 18161f5207b7SJohn Levon } 18171f5207b7SJohn Levon 18181f5207b7SJohn Levon struct state_list *get_all_possible_not_equal_comparisons(struct expression *expr) 18191f5207b7SJohn Levon { 18201f5207b7SJohn Levon struct smatch_state *state; 18211f5207b7SJohn Levon struct string_list *links; 18221f5207b7SJohn Levon struct state_list *ret = NULL; 18231f5207b7SJohn Levon struct sm_state *sm; 18241f5207b7SJohn Levon struct sm_state *possible; 18251f5207b7SJohn Levon char *link; 18261f5207b7SJohn Levon 18271f5207b7SJohn Levon return NULL; 18281f5207b7SJohn Levon 18291f5207b7SJohn Levon state = get_state_chunk(link_id, expr); 18301f5207b7SJohn Levon if (!state) 18311f5207b7SJohn Levon return NULL; 18321f5207b7SJohn Levon links = state->data; 18331f5207b7SJohn Levon 18341f5207b7SJohn Levon FOR_EACH_PTR(links, link) { 18351f5207b7SJohn Levon sm = get_sm_state(compare_id, link, NULL); 18361f5207b7SJohn Levon if (!sm) 18371f5207b7SJohn Levon continue; 18381f5207b7SJohn Levon FOR_EACH_PTR(sm->possible, possible) { 18391f5207b7SJohn Levon if (strcmp(possible->state->name, "!=") != 0) 18401f5207b7SJohn Levon continue; 18411f5207b7SJohn Levon add_ptr_list(&ret, sm); 18421f5207b7SJohn Levon break; 18431f5207b7SJohn Levon } END_FOR_EACH_PTR(link); 18441f5207b7SJohn Levon } END_FOR_EACH_PTR(link); 18451f5207b7SJohn Levon 18461f5207b7SJohn Levon return ret; 18471f5207b7SJohn Levon } 18481f5207b7SJohn Levon 18491f5207b7SJohn Levon static void update_links_from_call(struct expression *left, 18501f5207b7SJohn Levon int left_compare, 18511f5207b7SJohn Levon struct expression *right) 18521f5207b7SJohn Levon { 18531f5207b7SJohn Levon struct string_list *links; 18541f5207b7SJohn Levon struct smatch_state *state; 18551f5207b7SJohn Levon struct compare_data *data; 18561f5207b7SJohn Levon struct symbol *left_sym, *right_sym; 18571f5207b7SJohn Levon char *left_var = NULL; 18581f5207b7SJohn Levon char *right_var = NULL; 18591f5207b7SJohn Levon struct var_sym_list *left_vsl; 18601f5207b7SJohn Levon struct expression *expr; 18611f5207b7SJohn Levon const char *var; 18621f5207b7SJohn Levon struct var_sym_list *vsl; 18631f5207b7SJohn Levon int comparison; 18641f5207b7SJohn Levon char *tmp; 18651f5207b7SJohn Levon 18661f5207b7SJohn Levon left_var = chunk_to_var_sym(left, &left_sym); 18671f5207b7SJohn Levon if (!left_var) 18681f5207b7SJohn Levon goto done; 18691f5207b7SJohn Levon left_vsl = expr_to_vsl(left); 18701f5207b7SJohn Levon right_var = chunk_to_var_sym(right, &right_sym); 18711f5207b7SJohn Levon if (!right_var) 18721f5207b7SJohn Levon goto done; 18731f5207b7SJohn Levon 18741f5207b7SJohn Levon state = get_state(link_id, right_var, right_sym); 18751f5207b7SJohn Levon if (!state) 18761f5207b7SJohn Levon return; 18771f5207b7SJohn Levon links = state->data; 18781f5207b7SJohn Levon 18791f5207b7SJohn Levon FOR_EACH_PTR(links, tmp) { 18801f5207b7SJohn Levon state = get_state(compare_id, tmp, NULL); 18811f5207b7SJohn Levon if (!state || !state->data) 18821f5207b7SJohn Levon continue; 18831f5207b7SJohn Levon data = state->data; 18841f5207b7SJohn Levon comparison = data->comparison; 18851f5207b7SJohn Levon expr = data->right; 18861f5207b7SJohn Levon var = data->right_var; 18871f5207b7SJohn Levon vsl = data->right_vsl; 18881f5207b7SJohn Levon if (strcmp(var, right_var) == 0) { 18891f5207b7SJohn Levon expr = data->left; 18901f5207b7SJohn Levon var = data->left_var; 18911f5207b7SJohn Levon vsl = data->left_vsl; 18921f5207b7SJohn Levon comparison = flip_comparison(comparison); 18931f5207b7SJohn Levon } 18941f5207b7SJohn Levon comparison = combine_comparisons(left_compare, comparison); 18951f5207b7SJohn Levon if (!comparison) 18961f5207b7SJohn Levon continue; 18971f5207b7SJohn Levon add_comparison_var_sym(left, left_var, left_vsl, comparison, expr, var, vsl); 18981f5207b7SJohn Levon } END_FOR_EACH_PTR(tmp); 18991f5207b7SJohn Levon 19001f5207b7SJohn Levon done: 19011f5207b7SJohn Levon free_string(right_var); 19021f5207b7SJohn Levon } 19031f5207b7SJohn Levon 19041f5207b7SJohn Levon void __add_return_comparison(struct expression *call, const char *range) 19051f5207b7SJohn Levon { 19061f5207b7SJohn Levon struct expression *arg; 19071f5207b7SJohn Levon int comparison; 19081f5207b7SJohn Levon char buf[4]; 19091f5207b7SJohn Levon 19101f5207b7SJohn Levon if (!str_to_comparison_arg(range, call, &comparison, &arg)) 19111f5207b7SJohn Levon return; 19121f5207b7SJohn Levon snprintf(buf, sizeof(buf), "%s", show_special(comparison)); 19131f5207b7SJohn Levon update_links_from_call(call, comparison, arg); 19141f5207b7SJohn Levon add_comparison(call, comparison, arg); 19151f5207b7SJohn Levon } 19161f5207b7SJohn Levon 19171f5207b7SJohn Levon void __add_comparison_info(struct expression *expr, struct expression *call, const char *range) 19181f5207b7SJohn Levon { 19191f5207b7SJohn Levon copy_comparisons(expr, call); 19201f5207b7SJohn Levon } 19211f5207b7SJohn Levon 19221f5207b7SJohn Levon static char *get_mask_comparison(struct expression *expr, int ignore) 19231f5207b7SJohn Levon { 19241f5207b7SJohn Levon struct expression *tmp, *right; 19251f5207b7SJohn Levon int count, param; 19261f5207b7SJohn Levon char buf[256]; 19271f5207b7SJohn Levon 19281f5207b7SJohn Levon /* The return value for "return foo & param;" is <= param */ 19291f5207b7SJohn Levon 19301f5207b7SJohn Levon count = 0; 19311f5207b7SJohn Levon while ((tmp = get_assigned_expr(expr))) { 19321f5207b7SJohn Levon expr = strip_expr(tmp); 19331f5207b7SJohn Levon if (count++ > 4) 19341f5207b7SJohn Levon break; 19351f5207b7SJohn Levon } 19361f5207b7SJohn Levon 19371f5207b7SJohn Levon if (expr->type != EXPR_BINOP || expr->op != '&') 19381f5207b7SJohn Levon return NULL; 19391f5207b7SJohn Levon 19401f5207b7SJohn Levon right = strip_expr(expr->right); 19411f5207b7SJohn Levon param = get_param_num(right); 19421f5207b7SJohn Levon if (param < 0 || param == ignore) 19431f5207b7SJohn Levon return NULL; 19441f5207b7SJohn Levon 19451f5207b7SJohn Levon snprintf(buf, sizeof(buf), "[<=$%d]", param); 19461f5207b7SJohn Levon return alloc_sname(buf); 19471f5207b7SJohn Levon } 19481f5207b7SJohn Levon 19491f5207b7SJohn Levon static char *range_comparison_to_param_helper(struct expression *expr, char starts_with, int ignore) 19501f5207b7SJohn Levon { 19511f5207b7SJohn Levon struct symbol *param; 19521f5207b7SJohn Levon char *var = NULL; 19531f5207b7SJohn Levon char buf[256]; 19541f5207b7SJohn Levon char *ret_str = NULL; 19551f5207b7SJohn Levon int compare; 19561f5207b7SJohn Levon int i; 19571f5207b7SJohn Levon 19581f5207b7SJohn Levon if (!expr) 19591f5207b7SJohn Levon return NULL; 19601f5207b7SJohn Levon 19611f5207b7SJohn Levon var = chunk_to_var(expr); 19621f5207b7SJohn Levon if (!var) 19631f5207b7SJohn Levon goto try_mask; 19641f5207b7SJohn Levon 19651f5207b7SJohn Levon i = -1; 19661f5207b7SJohn Levon FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) { 19671f5207b7SJohn Levon i++; 19681f5207b7SJohn Levon if (i == ignore) 19691f5207b7SJohn Levon continue; 19701f5207b7SJohn Levon if (!param->ident) 19711f5207b7SJohn Levon continue; 19721f5207b7SJohn Levon snprintf(buf, sizeof(buf), "%s orig", param->ident->name); 19731f5207b7SJohn Levon compare = get_comparison_strings(var, buf); 19741f5207b7SJohn Levon if (!compare) 19751f5207b7SJohn Levon continue; 19761f5207b7SJohn Levon if (show_special(compare)[0] != starts_with) 19771f5207b7SJohn Levon continue; 19781f5207b7SJohn Levon snprintf(buf, sizeof(buf), "[%s$%d]", show_special(compare), i); 19791f5207b7SJohn Levon ret_str = alloc_sname(buf); 19801f5207b7SJohn Levon break; 19811f5207b7SJohn Levon } END_FOR_EACH_PTR(param); 19821f5207b7SJohn Levon 19831f5207b7SJohn Levon free_string(var); 19841f5207b7SJohn Levon if (!ret_str) 19851f5207b7SJohn Levon goto try_mask; 19861f5207b7SJohn Levon 19871f5207b7SJohn Levon return ret_str; 19881f5207b7SJohn Levon 19891f5207b7SJohn Levon try_mask: 19901f5207b7SJohn Levon if (starts_with == '<') 19911f5207b7SJohn Levon ret_str = get_mask_comparison(expr, ignore); 19921f5207b7SJohn Levon return ret_str; 19931f5207b7SJohn Levon } 19941f5207b7SJohn Levon 19951f5207b7SJohn Levon char *name_sym_to_param_comparison(const char *name, struct symbol *sym) 19961f5207b7SJohn Levon { 19971f5207b7SJohn Levon struct symbol *param; 19981f5207b7SJohn Levon char buf[256]; 19991f5207b7SJohn Levon int compare; 20001f5207b7SJohn Levon int i; 20011f5207b7SJohn Levon 20021f5207b7SJohn Levon i = -1; 20031f5207b7SJohn Levon FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) { 20041f5207b7SJohn Levon i++; 20051f5207b7SJohn Levon if (!param->ident) 20061f5207b7SJohn Levon continue; 20071f5207b7SJohn Levon snprintf(buf, sizeof(buf), "%s orig", param->ident->name); 20081f5207b7SJohn Levon compare = get_comparison_strings(name, buf); 20091f5207b7SJohn Levon if (!compare) 20101f5207b7SJohn Levon continue; 20111f5207b7SJohn Levon snprintf(buf, sizeof(buf), "[%s$%d]", show_special(compare), i); 20121f5207b7SJohn Levon return alloc_sname(buf); 20131f5207b7SJohn Levon } END_FOR_EACH_PTR(param); 20141f5207b7SJohn Levon 20151f5207b7SJohn Levon return NULL; 20161f5207b7SJohn Levon } 20171f5207b7SJohn Levon 20181f5207b7SJohn Levon char *expr_equal_to_param(struct expression *expr, int ignore) 20191f5207b7SJohn Levon { 20201f5207b7SJohn Levon return range_comparison_to_param_helper(expr, '=', ignore); 20211f5207b7SJohn Levon } 20221f5207b7SJohn Levon 20231f5207b7SJohn Levon char *expr_lte_to_param(struct expression *expr, int ignore) 20241f5207b7SJohn Levon { 20251f5207b7SJohn Levon return range_comparison_to_param_helper(expr, '<', ignore); 20261f5207b7SJohn Levon } 20271f5207b7SJohn Levon 20281f5207b7SJohn Levon char *expr_param_comparison(struct expression *expr, int ignore) 20291f5207b7SJohn Levon { 20301f5207b7SJohn Levon struct symbol *param; 20311f5207b7SJohn Levon char *var = NULL; 20321f5207b7SJohn Levon char buf[256]; 20331f5207b7SJohn Levon char *ret_str = NULL; 20341f5207b7SJohn Levon int compare; 20351f5207b7SJohn Levon int i; 20361f5207b7SJohn Levon 20371f5207b7SJohn Levon var = chunk_to_var(expr); 20381f5207b7SJohn Levon if (!var) 20391f5207b7SJohn Levon goto free; 20401f5207b7SJohn Levon 20411f5207b7SJohn Levon i = -1; 20421f5207b7SJohn Levon FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) { 20431f5207b7SJohn Levon i++; 20441f5207b7SJohn Levon if (i == ignore) 20451f5207b7SJohn Levon continue; 20461f5207b7SJohn Levon if (!param->ident) 20471f5207b7SJohn Levon continue; 20481f5207b7SJohn Levon snprintf(buf, sizeof(buf), "%s orig", param->ident->name); 20491f5207b7SJohn Levon compare = get_comparison_strings(var, buf); 20501f5207b7SJohn Levon if (!compare) 20511f5207b7SJohn Levon continue; 20521f5207b7SJohn Levon snprintf(buf, sizeof(buf), "[%s$%d]", show_special(compare), i); 20531f5207b7SJohn Levon ret_str = alloc_sname(buf); 20541f5207b7SJohn Levon break; 20551f5207b7SJohn Levon } END_FOR_EACH_PTR(param); 20561f5207b7SJohn Levon 20571f5207b7SJohn Levon free: 20581f5207b7SJohn Levon free_string(var); 20591f5207b7SJohn Levon return ret_str; 20601f5207b7SJohn Levon } 20611f5207b7SJohn Levon 20621f5207b7SJohn Levon char *get_printed_param_name(struct expression *call, const char *param_name, struct symbol *param_sym) 20631f5207b7SJohn Levon { 20641f5207b7SJohn Levon struct expression *arg; 20651f5207b7SJohn Levon char *name; 20661f5207b7SJohn Levon struct symbol *sym; 20671f5207b7SJohn Levon static char buf[256]; 20681f5207b7SJohn Levon int len; 20691f5207b7SJohn Levon int i; 20701f5207b7SJohn Levon 20711f5207b7SJohn Levon i = -1; 20721f5207b7SJohn Levon FOR_EACH_PTR(call->args, arg) { 20731f5207b7SJohn Levon i++; 20741f5207b7SJohn Levon 20751f5207b7SJohn Levon name = expr_to_var_sym(arg, &sym); 20761f5207b7SJohn Levon if (!name || !sym) 20771f5207b7SJohn Levon continue; 20781f5207b7SJohn Levon if (sym != param_sym) 20791f5207b7SJohn Levon continue; 20801f5207b7SJohn Levon 20811f5207b7SJohn Levon len = strlen(name); 20821f5207b7SJohn Levon if (strncmp(name, param_name, len) != 0) 20831f5207b7SJohn Levon continue; 20841f5207b7SJohn Levon if (param_name[len] == '\0') { 20851f5207b7SJohn Levon snprintf(buf, sizeof(buf), "$%d", i); 20861f5207b7SJohn Levon return buf; 20871f5207b7SJohn Levon } 20881f5207b7SJohn Levon if (param_name[len] != '-') 20891f5207b7SJohn Levon continue; 20901f5207b7SJohn Levon snprintf(buf, sizeof(buf), "$%d%s", i, param_name + len); 20911f5207b7SJohn Levon return buf; 20921f5207b7SJohn Levon } END_FOR_EACH_PTR(arg); 20931f5207b7SJohn Levon 20941f5207b7SJohn Levon return NULL; 20951f5207b7SJohn Levon } 20961f5207b7SJohn Levon 20971f5207b7SJohn Levon static void match_call_info(struct expression *expr) 20981f5207b7SJohn Levon { 20991f5207b7SJohn Levon struct expression *arg; 21001f5207b7SJohn Levon struct smatch_state *state; 21011f5207b7SJohn Levon struct sm_state *sm; 21021f5207b7SJohn Levon struct compare_data *data; 21031f5207b7SJohn Levon int comparison; 21041f5207b7SJohn Levon struct string_list *links; 21051f5207b7SJohn Levon char *arg_name; 21061f5207b7SJohn Levon const char *right_name; 21071f5207b7SJohn Levon char *link; 21081f5207b7SJohn Levon char info_buf[256]; 21091f5207b7SJohn Levon int i; 21101f5207b7SJohn Levon 21111f5207b7SJohn Levon i = -1; 21121f5207b7SJohn Levon FOR_EACH_PTR(expr->args, arg) { 21131f5207b7SJohn Levon i++; 21141f5207b7SJohn Levon 21151f5207b7SJohn Levon state = get_state_chunk(link_id, arg); 21161f5207b7SJohn Levon if (!state) 21171f5207b7SJohn Levon continue; 21181f5207b7SJohn Levon 21191f5207b7SJohn Levon links = state->data; 21201f5207b7SJohn Levon FOR_EACH_PTR(links, link) { 21211f5207b7SJohn Levon struct var_sym_list *right_vsl; 21221f5207b7SJohn Levon struct var_sym *right_vs; 21231f5207b7SJohn Levon 21241f5207b7SJohn Levon 21251f5207b7SJohn Levon if (strstr(link, " orig")) 21261f5207b7SJohn Levon continue; 21271f5207b7SJohn Levon sm = get_sm_state(compare_id, link, NULL); 21281f5207b7SJohn Levon if (!sm) 21291f5207b7SJohn Levon continue; 21301f5207b7SJohn Levon data = sm->state->data; 21311f5207b7SJohn Levon if (!data || !data->comparison) 21321f5207b7SJohn Levon continue; 21331f5207b7SJohn Levon arg_name = expr_to_var(arg); 21341f5207b7SJohn Levon if (!arg_name) 21351f5207b7SJohn Levon continue; 21361f5207b7SJohn Levon 21371f5207b7SJohn Levon right_vsl = NULL; 21381f5207b7SJohn Levon if (strcmp(data->left_var, arg_name) == 0) { 21391f5207b7SJohn Levon comparison = data->comparison; 21401f5207b7SJohn Levon right_name = data->right_var; 21411f5207b7SJohn Levon right_vsl = data->right_vsl; 21421f5207b7SJohn Levon } else if (strcmp(data->right_var, arg_name) == 0) { 21431f5207b7SJohn Levon comparison = flip_comparison(data->comparison); 21441f5207b7SJohn Levon right_name = data->left_var; 21451f5207b7SJohn Levon right_vsl = data->left_vsl; 21461f5207b7SJohn Levon } 21471f5207b7SJohn Levon if (!right_vsl || ptr_list_size((struct ptr_list *)right_vsl) != 1) 21481f5207b7SJohn Levon goto free; 21491f5207b7SJohn Levon 21501f5207b7SJohn Levon right_vs = first_ptr_list((struct ptr_list *)right_vsl); 21511f5207b7SJohn Levon if (strcmp(right_vs->var, right_name) != 0) 21521f5207b7SJohn Levon goto free; 21531f5207b7SJohn Levon right_name = get_printed_param_name(expr, right_vs->var, right_vs->sym); 21541f5207b7SJohn Levon if (!right_name) 21551f5207b7SJohn Levon goto free; 21561f5207b7SJohn Levon snprintf(info_buf, sizeof(info_buf), "%s %s", show_special(comparison), right_name); 21571f5207b7SJohn Levon sql_insert_caller_info(expr, PARAM_COMPARE, i, "$", info_buf); 21581f5207b7SJohn Levon 21591f5207b7SJohn Levon free: 21601f5207b7SJohn Levon free_string(arg_name); 21611f5207b7SJohn Levon } END_FOR_EACH_PTR(link); 21621f5207b7SJohn Levon } END_FOR_EACH_PTR(arg); 21631f5207b7SJohn Levon } 21641f5207b7SJohn Levon 21651f5207b7SJohn Levon static void struct_member_callback(struct expression *call, int param, char *printed_name, struct sm_state *link_sm) 21661f5207b7SJohn Levon { 21671f5207b7SJohn Levon struct sm_state *compare_sm; 21681f5207b7SJohn Levon struct string_list *links; 21691f5207b7SJohn Levon char *link; 21701f5207b7SJohn Levon struct compare_data *data; 21711f5207b7SJohn Levon struct var_sym *left, *right; 21721f5207b7SJohn Levon static char info_buf[256]; 21731f5207b7SJohn Levon const char *right_name; 21741f5207b7SJohn Levon 21751f5207b7SJohn Levon if (strstr(printed_name, " orig")) 21761f5207b7SJohn Levon return; 21771f5207b7SJohn Levon 21781f5207b7SJohn Levon links = link_sm->state->data; 21791f5207b7SJohn Levon FOR_EACH_PTR(links, link) { 21801f5207b7SJohn Levon compare_sm = get_sm_state(compare_id, link, NULL); 21811f5207b7SJohn Levon if (!compare_sm) 21821f5207b7SJohn Levon continue; 21831f5207b7SJohn Levon data = compare_sm->state->data; 21841f5207b7SJohn Levon if (!data || !data->comparison) 21851f5207b7SJohn Levon continue; 21861f5207b7SJohn Levon 21871f5207b7SJohn Levon if (ptr_list_size((struct ptr_list *)data->left_vsl) != 1 || 21881f5207b7SJohn Levon ptr_list_size((struct ptr_list *)data->right_vsl) != 1) 21891f5207b7SJohn Levon continue; 21901f5207b7SJohn Levon left = first_ptr_list((struct ptr_list *)data->left_vsl); 21911f5207b7SJohn Levon right = first_ptr_list((struct ptr_list *)data->right_vsl); 21921f5207b7SJohn Levon if (left->sym == right->sym && 21931f5207b7SJohn Levon strcmp(left->var, right->var) == 0) 21941f5207b7SJohn Levon continue; 21951f5207b7SJohn Levon /* 21961f5207b7SJohn Levon * Both parameters link to this comparison so only 21971f5207b7SJohn Levon * record the first one. 21981f5207b7SJohn Levon */ 21991f5207b7SJohn Levon if (left->sym != link_sm->sym || 22001f5207b7SJohn Levon strcmp(left->var, link_sm->name) != 0) 22011f5207b7SJohn Levon continue; 22021f5207b7SJohn Levon 22031f5207b7SJohn Levon right_name = get_printed_param_name(call, right->var, right->sym); 22041f5207b7SJohn Levon if (!right_name) 22051f5207b7SJohn Levon continue; 22061f5207b7SJohn Levon snprintf(info_buf, sizeof(info_buf), "%s %s", show_special(data->comparison), right_name); 22071f5207b7SJohn Levon sql_insert_caller_info(call, PARAM_COMPARE, param, printed_name, info_buf); 22081f5207b7SJohn Levon } END_FOR_EACH_PTR(link); 22091f5207b7SJohn Levon } 22101f5207b7SJohn Levon 22111f5207b7SJohn Levon static void print_return_value_comparison(int return_id, char *return_ranges, struct expression *expr) 22121f5207b7SJohn Levon { 22131f5207b7SJohn Levon char *name; 22141f5207b7SJohn Levon const char *tmp_name; 22151f5207b7SJohn Levon struct symbol *sym; 22161f5207b7SJohn Levon int param; 22171f5207b7SJohn Levon char info_buf[256]; 22181f5207b7SJohn Levon 22191f5207b7SJohn Levon /* 22201f5207b7SJohn Levon * TODO: This only prints == comparisons. That's probably the most 22211f5207b7SJohn Levon * useful comparison because == max has lots of implications. But it 22221f5207b7SJohn Levon * would be good to capture the rest as well. 22231f5207b7SJohn Levon * 22241f5207b7SJohn Levon * This information is already in the DB but it's in the parameter math 22251f5207b7SJohn Levon * bits and it's awkward to use it. This is is the simpler, possibly 22261f5207b7SJohn Levon * cleaner way, but not necessarily the best, I don't know. 22271f5207b7SJohn Levon */ 22281f5207b7SJohn Levon 22291f5207b7SJohn Levon if (!expr) 22301f5207b7SJohn Levon return; 22311f5207b7SJohn Levon name = expr_to_var_sym(expr, &sym); 22321f5207b7SJohn Levon if (!name || !sym) 22331f5207b7SJohn Levon goto free; 22341f5207b7SJohn Levon 22351f5207b7SJohn Levon param = get_param_num_from_sym(sym); 22361f5207b7SJohn Levon if (param < 0) 22371f5207b7SJohn Levon goto free; 22381f5207b7SJohn Levon if (param_was_set_var_sym(name, sym)) 22391f5207b7SJohn Levon goto free; 22401f5207b7SJohn Levon 22411f5207b7SJohn Levon tmp_name = get_param_name_var_sym(name, sym); 22421f5207b7SJohn Levon if (!tmp_name) 22431f5207b7SJohn Levon goto free; 22441f5207b7SJohn Levon 22451f5207b7SJohn Levon snprintf(info_buf, sizeof(info_buf), "== $%d%s", param, tmp_name + 1); 22461f5207b7SJohn Levon sql_insert_return_states(return_id, return_ranges, 22471f5207b7SJohn Levon PARAM_COMPARE, -1, "$", info_buf); 22481f5207b7SJohn Levon free: 22491f5207b7SJohn Levon free_string(name); 22501f5207b7SJohn Levon } 22511f5207b7SJohn Levon 22521f5207b7SJohn Levon static void print_return_comparison(int return_id, char *return_ranges, struct expression *expr) 22531f5207b7SJohn Levon { 22541f5207b7SJohn Levon struct sm_state *tmp; 22551f5207b7SJohn Levon struct string_list *links; 22561f5207b7SJohn Levon char *link; 22571f5207b7SJohn Levon struct sm_state *sm; 22581f5207b7SJohn Levon struct compare_data *data; 22591f5207b7SJohn Levon struct var_sym *left, *right; 22601f5207b7SJohn Levon int left_param, right_param; 22611f5207b7SJohn Levon char left_buf[256]; 22621f5207b7SJohn Levon char right_buf[256]; 22631f5207b7SJohn Levon char info_buf[258]; 22641f5207b7SJohn Levon const char *tmp_name; 22651f5207b7SJohn Levon 22661f5207b7SJohn Levon print_return_value_comparison(return_id, return_ranges, expr); 22671f5207b7SJohn Levon 22681f5207b7SJohn Levon FOR_EACH_MY_SM(link_id, __get_cur_stree(), tmp) { 22691f5207b7SJohn Levon if (get_param_num_from_sym(tmp->sym) < 0) 22701f5207b7SJohn Levon continue; 22711f5207b7SJohn Levon links = tmp->state->data; 22721f5207b7SJohn Levon FOR_EACH_PTR(links, link) { 22731f5207b7SJohn Levon sm = get_sm_state(compare_id, link, NULL); 22741f5207b7SJohn Levon if (!sm) 22751f5207b7SJohn Levon continue; 22761f5207b7SJohn Levon data = sm->state->data; 22771f5207b7SJohn Levon if (!data || !data->comparison) 22781f5207b7SJohn Levon continue; 22791f5207b7SJohn Levon if (ptr_list_size((struct ptr_list *)data->left_vsl) != 1 || 22801f5207b7SJohn Levon ptr_list_size((struct ptr_list *)data->right_vsl) != 1) 22811f5207b7SJohn Levon continue; 22821f5207b7SJohn Levon left = first_ptr_list((struct ptr_list *)data->left_vsl); 22831f5207b7SJohn Levon right = first_ptr_list((struct ptr_list *)data->right_vsl); 22841f5207b7SJohn Levon if (left->sym == right->sym && 22851f5207b7SJohn Levon strcmp(left->var, right->var) == 0) 22861f5207b7SJohn Levon continue; 22871f5207b7SJohn Levon /* 22881f5207b7SJohn Levon * Both parameters link to this comparison so only 22891f5207b7SJohn Levon * record the first one. 22901f5207b7SJohn Levon */ 22911f5207b7SJohn Levon if (left->sym != tmp->sym || 22921f5207b7SJohn Levon strcmp(left->var, tmp->name) != 0) 22931f5207b7SJohn Levon continue; 22941f5207b7SJohn Levon 22951f5207b7SJohn Levon if (strstr(right->var, " orig")) 22961f5207b7SJohn Levon continue; 22971f5207b7SJohn Levon 22981f5207b7SJohn Levon left_param = get_param_num_from_sym(left->sym); 22991f5207b7SJohn Levon right_param = get_param_num_from_sym(right->sym); 23001f5207b7SJohn Levon if (left_param < 0 || right_param < 0) 23011f5207b7SJohn Levon continue; 23021f5207b7SJohn Levon 23031f5207b7SJohn Levon tmp_name = get_param_name_var_sym(left->var, left->sym); 23041f5207b7SJohn Levon if (!tmp_name) 23051f5207b7SJohn Levon continue; 23061f5207b7SJohn Levon snprintf(left_buf, sizeof(left_buf), "%s", tmp_name); 23071f5207b7SJohn Levon 23081f5207b7SJohn Levon tmp_name = get_param_name_var_sym(right->var, right->sym); 23091f5207b7SJohn Levon if (!tmp_name || tmp_name[0] != '$') 23101f5207b7SJohn Levon continue; 23111f5207b7SJohn Levon snprintf(right_buf, sizeof(right_buf), "$%d%s", right_param, tmp_name + 1); 23121f5207b7SJohn Levon 23131f5207b7SJohn Levon /* 23141f5207b7SJohn Levon * FIXME: this should reject $ type variables (as 23151f5207b7SJohn Levon * opposed to $->foo type). Those should come from 23161f5207b7SJohn Levon * smatch_param_compare_limit.c. 23171f5207b7SJohn Levon */ 23181f5207b7SJohn Levon 23191f5207b7SJohn Levon snprintf(info_buf, sizeof(info_buf), "%s %s", show_special(data->comparison), right_buf); 23201f5207b7SJohn Levon sql_insert_return_states(return_id, return_ranges, 23211f5207b7SJohn Levon PARAM_COMPARE, left_param, left_buf, info_buf); 23221f5207b7SJohn Levon } END_FOR_EACH_PTR(link); 23231f5207b7SJohn Levon 23241f5207b7SJohn Levon } END_FOR_EACH_SM(tmp); 23251f5207b7SJohn Levon } 23261f5207b7SJohn Levon 23271f5207b7SJohn Levon static int parse_comparison(char **value, int *op) 23281f5207b7SJohn Levon { 23291f5207b7SJohn Levon 23301f5207b7SJohn Levon *op = **value; 23311f5207b7SJohn Levon 23321f5207b7SJohn Levon switch (*op) { 23331f5207b7SJohn Levon case '<': 23341f5207b7SJohn Levon (*value)++; 23351f5207b7SJohn Levon if (**value == '=') { 23361f5207b7SJohn Levon (*value)++; 23371f5207b7SJohn Levon *op = SPECIAL_LTE; 23381f5207b7SJohn Levon } 23391f5207b7SJohn Levon break; 23401f5207b7SJohn Levon case '=': 23411f5207b7SJohn Levon (*value)++; 23421f5207b7SJohn Levon (*value)++; 23431f5207b7SJohn Levon *op = SPECIAL_EQUAL; 23441f5207b7SJohn Levon break; 23451f5207b7SJohn Levon case '!': 23461f5207b7SJohn Levon (*value)++; 23471f5207b7SJohn Levon (*value)++; 23481f5207b7SJohn Levon *op = SPECIAL_NOTEQUAL; 23491f5207b7SJohn Levon break; 23501f5207b7SJohn Levon case '>': 23511f5207b7SJohn Levon (*value)++; 23521f5207b7SJohn Levon if (**value == '=') { 23531f5207b7SJohn Levon (*value)++; 23541f5207b7SJohn Levon *op = SPECIAL_GTE; 23551f5207b7SJohn Levon } 23561f5207b7SJohn Levon break; 23571f5207b7SJohn Levon default: 23581f5207b7SJohn Levon return 0; 23591f5207b7SJohn Levon } 23601f5207b7SJohn Levon 23611f5207b7SJohn Levon if (**value != ' ') { 23621f5207b7SJohn Levon sm_perror("parsing comparison. %s", *value); 23631f5207b7SJohn Levon return 0; 23641f5207b7SJohn Levon } 23651f5207b7SJohn Levon 23661f5207b7SJohn Levon (*value)++; 23671f5207b7SJohn Levon return 1; 23681f5207b7SJohn Levon } 23691f5207b7SJohn Levon 23701f5207b7SJohn Levon static int split_op_param_key(char *value, int *op, int *param, char **key) 23711f5207b7SJohn Levon { 23721f5207b7SJohn Levon static char buf[256]; 23731f5207b7SJohn Levon char *p; 23741f5207b7SJohn Levon 23751f5207b7SJohn Levon if (!parse_comparison(&value, op)) 23761f5207b7SJohn Levon return 0; 23771f5207b7SJohn Levon 2378*efe51d0cSJohn Levon snprintf(buf, sizeof(buf), "%s", value); 23791f5207b7SJohn Levon 23801f5207b7SJohn Levon p = buf; 23811f5207b7SJohn Levon if (*p++ != '$') 23821f5207b7SJohn Levon return 0; 23831f5207b7SJohn Levon 23841f5207b7SJohn Levon *param = atoi(p); 23851f5207b7SJohn Levon if (*param < 0 || *param > 99) 23861f5207b7SJohn Levon return 0; 23871f5207b7SJohn Levon p++; 23881f5207b7SJohn Levon if (*param > 9) 23891f5207b7SJohn Levon p++; 23901f5207b7SJohn Levon p--; 23911f5207b7SJohn Levon *p = '$'; 23921f5207b7SJohn Levon *key = p; 23931f5207b7SJohn Levon 23941f5207b7SJohn Levon return 1; 23951f5207b7SJohn Levon } 23961f5207b7SJohn Levon 23971f5207b7SJohn Levon static void db_return_comparison(struct expression *expr, int left_param, char *key, char *value) 23981f5207b7SJohn Levon { 23991f5207b7SJohn Levon struct expression *left_arg, *right_arg; 24001f5207b7SJohn Levon char *left_name = NULL; 24011f5207b7SJohn Levon struct symbol *left_sym; 24021f5207b7SJohn Levon char *right_name = NULL; 24031f5207b7SJohn Levon struct symbol *right_sym; 24041f5207b7SJohn Levon int op; 24051f5207b7SJohn Levon int right_param; 24061f5207b7SJohn Levon char *right_key; 24071f5207b7SJohn Levon struct var_sym_list *left_vsl = NULL, *right_vsl = NULL; 24081f5207b7SJohn Levon 24091f5207b7SJohn Levon if (left_param == -1) { 24101f5207b7SJohn Levon if (expr->type != EXPR_ASSIGNMENT) 24111f5207b7SJohn Levon return; 24121f5207b7SJohn Levon left_arg = strip_expr(expr->left); 24131f5207b7SJohn Levon 24141f5207b7SJohn Levon while (expr->type == EXPR_ASSIGNMENT) 24151f5207b7SJohn Levon expr = strip_expr(expr->right); 24161f5207b7SJohn Levon if (expr->type != EXPR_CALL) 24171f5207b7SJohn Levon return; 24181f5207b7SJohn Levon } else { 24191f5207b7SJohn Levon while (expr->type == EXPR_ASSIGNMENT) 24201f5207b7SJohn Levon expr = strip_expr(expr->right); 24211f5207b7SJohn Levon if (expr->type != EXPR_CALL) 24221f5207b7SJohn Levon return; 24231f5207b7SJohn Levon 24241f5207b7SJohn Levon left_arg = get_argument_from_call_expr(expr->args, left_param); 24251f5207b7SJohn Levon if (!left_arg) 24261f5207b7SJohn Levon return; 24271f5207b7SJohn Levon } 24281f5207b7SJohn Levon 24291f5207b7SJohn Levon if (!split_op_param_key(value, &op, &right_param, &right_key)) 24301f5207b7SJohn Levon return; 24311f5207b7SJohn Levon 24321f5207b7SJohn Levon right_arg = get_argument_from_call_expr(expr->args, right_param); 24331f5207b7SJohn Levon if (!right_arg) 24341f5207b7SJohn Levon return; 24351f5207b7SJohn Levon 24361f5207b7SJohn Levon left_name = get_variable_from_key(left_arg, key, &left_sym); 24371f5207b7SJohn Levon if (!left_name || !left_sym) 24381f5207b7SJohn Levon goto free; 24391f5207b7SJohn Levon 24401f5207b7SJohn Levon right_name = get_variable_from_key(right_arg, right_key, &right_sym); 24411f5207b7SJohn Levon if (!right_name || !right_sym) 24421f5207b7SJohn Levon goto free; 24431f5207b7SJohn Levon 24441f5207b7SJohn Levon add_var_sym(&left_vsl, left_name, left_sym); 24451f5207b7SJohn Levon add_var_sym(&right_vsl, right_name, right_sym); 24461f5207b7SJohn Levon 24471f5207b7SJohn Levon add_comparison_var_sym(NULL, left_name, left_vsl, op, NULL, right_name, right_vsl); 24481f5207b7SJohn Levon 24491f5207b7SJohn Levon free: 24501f5207b7SJohn Levon free_string(left_name); 24511f5207b7SJohn Levon free_string(right_name); 24521f5207b7SJohn Levon } 24531f5207b7SJohn Levon 24541f5207b7SJohn Levon int param_compare_limit_is_impossible(struct expression *expr, int left_param, char *left_key, char *value) 24551f5207b7SJohn Levon { 24561f5207b7SJohn Levon struct smatch_state *state; 24571f5207b7SJohn Levon char *left_name = NULL; 24581f5207b7SJohn Levon char *right_name = NULL; 24591f5207b7SJohn Levon struct symbol *left_sym, *right_sym; 24601f5207b7SJohn Levon struct expression *left_arg, *right_arg; 24611f5207b7SJohn Levon int op, state_op; 24621f5207b7SJohn Levon int right_param; 24631f5207b7SJohn Levon char *right_key; 24641f5207b7SJohn Levon int ret = 0; 24651f5207b7SJohn Levon char buf[256]; 24661f5207b7SJohn Levon 24671f5207b7SJohn Levon while (expr->type == EXPR_ASSIGNMENT) 24681f5207b7SJohn Levon expr = strip_expr(expr->right); 24691f5207b7SJohn Levon if (expr->type != EXPR_CALL) 24701f5207b7SJohn Levon return 0; 24711f5207b7SJohn Levon 24721f5207b7SJohn Levon if (!split_op_param_key(value, &op, &right_param, &right_key)) 24731f5207b7SJohn Levon return 0; 24741f5207b7SJohn Levon 24751f5207b7SJohn Levon left_arg = get_argument_from_call_expr(expr->args, left_param); 24761f5207b7SJohn Levon if (!left_arg) 24771f5207b7SJohn Levon return 0; 24781f5207b7SJohn Levon 24791f5207b7SJohn Levon right_arg = get_argument_from_call_expr(expr->args, right_param); 24801f5207b7SJohn Levon if (!right_arg) 24811f5207b7SJohn Levon return 0; 24821f5207b7SJohn Levon 24831f5207b7SJohn Levon left_name = get_variable_from_key(left_arg, left_key, &left_sym); 24841f5207b7SJohn Levon right_name = get_variable_from_key(right_arg, right_key, &right_sym); 24851f5207b7SJohn Levon if (!left_name || !right_name) 24861f5207b7SJohn Levon goto free; 24871f5207b7SJohn Levon 24881f5207b7SJohn Levon snprintf(buf, sizeof(buf), "%s vs %s", left_name, right_name); 24891f5207b7SJohn Levon state = get_state(compare_id, buf, NULL); 24901f5207b7SJohn Levon if (!state) 24911f5207b7SJohn Levon goto free; 24921f5207b7SJohn Levon state_op = state_to_comparison(state); 24931f5207b7SJohn Levon if (!state_op) 24941f5207b7SJohn Levon goto free; 24951f5207b7SJohn Levon 24961f5207b7SJohn Levon if (!filter_comparison(remove_unsigned_from_comparison(state_op), op)) 24971f5207b7SJohn Levon ret = 1; 24981f5207b7SJohn Levon free: 24991f5207b7SJohn Levon free_string(left_name); 25001f5207b7SJohn Levon free_string(right_name); 25011f5207b7SJohn Levon return ret; 25021f5207b7SJohn Levon } 25031f5207b7SJohn Levon 25041f5207b7SJohn Levon int impossibly_high_comparison(struct expression *expr) 25051f5207b7SJohn Levon { 25061f5207b7SJohn Levon struct smatch_state *link_state; 25071f5207b7SJohn Levon struct sm_state *sm; 25081f5207b7SJohn Levon struct string_list *links; 25091f5207b7SJohn Levon char *link; 25101f5207b7SJohn Levon struct compare_data *data; 25111f5207b7SJohn Levon 25121f5207b7SJohn Levon link_state = get_state_expr(link_id, expr); 25131f5207b7SJohn Levon if (!link_state) { 25141f5207b7SJohn Levon if (expr->type == EXPR_BINOP && 25151f5207b7SJohn Levon (impossibly_high_comparison(expr->left) || 25161f5207b7SJohn Levon impossibly_high_comparison(expr->right))) 25171f5207b7SJohn Levon return 1; 25181f5207b7SJohn Levon return 0; 25191f5207b7SJohn Levon } 25201f5207b7SJohn Levon 25211f5207b7SJohn Levon links = link_state->data; 25221f5207b7SJohn Levon FOR_EACH_PTR(links, link) { 25231f5207b7SJohn Levon sm = get_sm_state(compare_id, link, NULL); 25241f5207b7SJohn Levon if (!sm) 25251f5207b7SJohn Levon continue; 25261f5207b7SJohn Levon data = sm->state->data; 25271f5207b7SJohn Levon if (!data) 25281f5207b7SJohn Levon continue; 25291f5207b7SJohn Levon if (!possibly_true(data->left, data->comparison, data->right)) 25301f5207b7SJohn Levon return 1; 25311f5207b7SJohn Levon } END_FOR_EACH_PTR(link); 25321f5207b7SJohn Levon 25331f5207b7SJohn Levon return 0; 25341f5207b7SJohn Levon } 25351f5207b7SJohn Levon 25361f5207b7SJohn Levon static void free_data(struct symbol *sym) 25371f5207b7SJohn Levon { 25381f5207b7SJohn Levon if (__inline_fn) 25391f5207b7SJohn Levon return; 25401f5207b7SJohn Levon clear_compare_data_alloc(); 25411f5207b7SJohn Levon } 25421f5207b7SJohn Levon 25431f5207b7SJohn Levon void register_comparison(int id) 25441f5207b7SJohn Levon { 25451f5207b7SJohn Levon compare_id = id; 2546*efe51d0cSJohn Levon set_dynamic_states(compare_id); 25471f5207b7SJohn Levon add_hook(&save_start_states, AFTER_DEF_HOOK); 25481f5207b7SJohn Levon add_unmatched_state_hook(compare_id, unmatched_comparison); 25491f5207b7SJohn Levon add_pre_merge_hook(compare_id, &pre_merge_hook); 25501f5207b7SJohn Levon add_merge_hook(compare_id, &merge_compare_states); 25511f5207b7SJohn Levon add_hook(&free_data, AFTER_FUNC_HOOK); 25521f5207b7SJohn Levon add_hook(&match_call_info, FUNCTION_CALL_HOOK); 25531f5207b7SJohn Levon add_split_return_callback(&print_return_comparison); 25541f5207b7SJohn Levon 25551f5207b7SJohn Levon select_return_states_hook(PARAM_COMPARE, &db_return_comparison); 25561f5207b7SJohn Levon add_hook(&match_preop, OP_HOOK); 25571f5207b7SJohn Levon } 25581f5207b7SJohn Levon 25591f5207b7SJohn Levon void register_comparison_late(int id) 25601f5207b7SJohn Levon { 25611f5207b7SJohn Levon add_hook(&match_assign, ASSIGNMENT_HOOK); 25621f5207b7SJohn Levon } 25631f5207b7SJohn Levon 25641f5207b7SJohn Levon void register_comparison_links(int id) 25651f5207b7SJohn Levon { 25661f5207b7SJohn Levon link_id = id; 2567*efe51d0cSJohn Levon db_ignore_states(link_id); 2568*efe51d0cSJohn Levon set_dynamic_states(link_id); 25691f5207b7SJohn Levon add_merge_hook(link_id, &merge_links); 25701f5207b7SJohn Levon add_modification_hook(link_id, &match_modify); 25711f5207b7SJohn Levon add_modification_hook_late(link_id, match_inc_dec); 25721f5207b7SJohn Levon 25731f5207b7SJohn Levon add_member_info_callback(link_id, struct_member_callback); 25741f5207b7SJohn Levon } 25751f5207b7SJohn Levon 25761f5207b7SJohn Levon void register_comparison_inc_dec(int id) 25771f5207b7SJohn Levon { 25781f5207b7SJohn Levon inc_dec_id = id; 25791f5207b7SJohn Levon add_modification_hook_late(inc_dec_id, &iter_modify); 25801f5207b7SJohn Levon } 25811f5207b7SJohn Levon 25821f5207b7SJohn Levon void register_comparison_inc_dec_links(int id) 25831f5207b7SJohn Levon { 25841f5207b7SJohn Levon inc_dec_link_id = id; 2585*efe51d0cSJohn Levon set_dynamic_states(inc_dec_link_id); 25861f5207b7SJohn Levon set_up_link_functions(inc_dec_id, inc_dec_link_id); 25871f5207b7SJohn Levon } 25881f5207b7SJohn Levon 25891f5207b7SJohn Levon static void filter_by_sm(struct sm_state *sm, int op, 25901f5207b7SJohn Levon struct state_list **true_stack, 25911f5207b7SJohn Levon struct state_list **false_stack) 25921f5207b7SJohn Levon { 25931f5207b7SJohn Levon struct compare_data *data; 25941f5207b7SJohn Levon int istrue = 0; 25951f5207b7SJohn Levon int isfalse = 0; 25961f5207b7SJohn Levon 25971f5207b7SJohn Levon if (!sm) 25981f5207b7SJohn Levon return; 25991f5207b7SJohn Levon data = sm->state->data; 26001f5207b7SJohn Levon if (!data) { 26011f5207b7SJohn Levon if (sm->merged) { 26021f5207b7SJohn Levon filter_by_sm(sm->left, op, true_stack, false_stack); 26031f5207b7SJohn Levon filter_by_sm(sm->right, op, true_stack, false_stack); 26041f5207b7SJohn Levon } 26051f5207b7SJohn Levon return; 26061f5207b7SJohn Levon } 26071f5207b7SJohn Levon 26081f5207b7SJohn Levon if (data->comparison && 26091f5207b7SJohn Levon data->comparison == filter_comparison(data->comparison, op)) 26101f5207b7SJohn Levon istrue = 1; 26111f5207b7SJohn Levon 26121f5207b7SJohn Levon if (data->comparison && 26131f5207b7SJohn Levon data->comparison == filter_comparison(data->comparison, negate_comparison(op))) 26141f5207b7SJohn Levon isfalse = 1; 26151f5207b7SJohn Levon 26161f5207b7SJohn Levon if (istrue) 26171f5207b7SJohn Levon add_ptr_list(true_stack, sm); 26181f5207b7SJohn Levon if (isfalse) 26191f5207b7SJohn Levon add_ptr_list(false_stack, sm); 26201f5207b7SJohn Levon 26211f5207b7SJohn Levon if (sm->merged) { 26221f5207b7SJohn Levon filter_by_sm(sm->left, op, true_stack, false_stack); 26231f5207b7SJohn Levon filter_by_sm(sm->right, op, true_stack, false_stack); 26241f5207b7SJohn Levon } 26251f5207b7SJohn Levon } 26261f5207b7SJohn Levon 26271f5207b7SJohn Levon struct sm_state *comparison_implication_hook(struct expression *expr, 26281f5207b7SJohn Levon struct state_list **true_stack, 26291f5207b7SJohn Levon struct state_list **false_stack) 26301f5207b7SJohn Levon { 26311f5207b7SJohn Levon struct sm_state *sm; 26321f5207b7SJohn Levon char *left, *right; 26331f5207b7SJohn Levon int op; 26341f5207b7SJohn Levon static char buf[256]; 26351f5207b7SJohn Levon 26361f5207b7SJohn Levon if (expr->type != EXPR_COMPARE) 26371f5207b7SJohn Levon return NULL; 26381f5207b7SJohn Levon 26391f5207b7SJohn Levon op = expr->op; 26401f5207b7SJohn Levon 26411f5207b7SJohn Levon left = expr_to_var(expr->left); 26421f5207b7SJohn Levon right = expr_to_var(expr->right); 26431f5207b7SJohn Levon if (!left || !right) { 26441f5207b7SJohn Levon free_string(left); 26451f5207b7SJohn Levon free_string(right); 26461f5207b7SJohn Levon return NULL; 26471f5207b7SJohn Levon } 26481f5207b7SJohn Levon 26491f5207b7SJohn Levon if (strcmp(left, right) > 0) { 26501f5207b7SJohn Levon char *tmp = left; 26511f5207b7SJohn Levon 26521f5207b7SJohn Levon left = right; 26531f5207b7SJohn Levon right = tmp; 26541f5207b7SJohn Levon op = flip_comparison(op); 26551f5207b7SJohn Levon } 26561f5207b7SJohn Levon 26571f5207b7SJohn Levon snprintf(buf, sizeof(buf), "%s vs %s", left, right); 26581f5207b7SJohn Levon sm = get_sm_state(compare_id, buf, NULL); 26591f5207b7SJohn Levon if (!sm) 26601f5207b7SJohn Levon return NULL; 26611f5207b7SJohn Levon if (!sm->merged) 26621f5207b7SJohn Levon return NULL; 26631f5207b7SJohn Levon 26641f5207b7SJohn Levon filter_by_sm(sm, op, true_stack, false_stack); 26651f5207b7SJohn Levon if (!*true_stack && !*false_stack) 26661f5207b7SJohn Levon return NULL; 26671f5207b7SJohn Levon 26681f5207b7SJohn Levon if (option_debug) 26691f5207b7SJohn Levon sm_msg("implications from comparison: (%s)", show_sm(sm)); 26701f5207b7SJohn Levon 26711f5207b7SJohn Levon return sm; 26721f5207b7SJohn Levon } 2673