11f5207b7SJohn Levon /*
21f5207b7SJohn Levon * Copyright (C) 2006,2008 Dan Carpenter.
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 simplest type of condition is
201f5207b7SJohn Levon * if (a) { ...
211f5207b7SJohn Levon *
221f5207b7SJohn Levon * The next simplest kind of conditions is
231f5207b7SJohn Levon * if (a && b) { c;
241f5207b7SJohn Levon * In that case 'a' is true when we get to 'b' and both are true
251f5207b7SJohn Levon * when we get to c.
261f5207b7SJohn Levon *
271f5207b7SJohn Levon * Or's are a little more complicated.
281f5207b7SJohn Levon * if (a || b) { c;
291f5207b7SJohn Levon * We know 'a' is not true when we get to 'b' but it may be true
301f5207b7SJohn Levon * when we get to c.
311f5207b7SJohn Levon *
321f5207b7SJohn Levon * If we mix and's and or's that's even more complicated.
331f5207b7SJohn Levon * if (a && b && c || a && d) { d ;
341f5207b7SJohn Levon * 'a' is true when we evaluate 'b', and 'd'.
351f5207b7SJohn Levon * 'b' is true when we evaluate 'c' but otherwise we don't.
361f5207b7SJohn Levon *
371f5207b7SJohn Levon * The other thing that complicates matters is if we negate
381f5207b7SJohn Levon * some if conditions.
391f5207b7SJohn Levon * if (!a) { ...
401f5207b7SJohn Levon * Smatch has passes the un-negated version to the client and flip
411f5207b7SJohn Levon * the true and false values internally. This makes it easier
421f5207b7SJohn Levon * to write checks.
431f5207b7SJohn Levon *
441f5207b7SJohn Levon * And negations can be part of a compound.
451f5207b7SJohn Levon * if (a && !(b || c)) { d;
461f5207b7SJohn Levon * In that situation we multiply the negative through to simplify
471f5207b7SJohn Levon * stuff so that we can remove the parens like this:
481f5207b7SJohn Levon * if (a && !b && !c) { d;
491f5207b7SJohn Levon *
501f5207b7SJohn Levon * One other thing is that:
511f5207b7SJohn Levon * if ((a) != 0){ ...
521f5207b7SJohn Levon * that's basically the same as testing for just 'a' and we simplify
531f5207b7SJohn Levon * comparisons with zero before passing it to the script.
541f5207b7SJohn Levon *
551f5207b7SJohn Levon */
561f5207b7SJohn Levon
571f5207b7SJohn Levon #include "smatch.h"
581f5207b7SJohn Levon #include "smatch_slist.h"
591f5207b7SJohn Levon #include "smatch_extra.h"
601f5207b7SJohn Levon #include "smatch_expression_stacks.h"
611f5207b7SJohn Levon
621f5207b7SJohn Levon extern int __expr_stmt_count;
631f5207b7SJohn Levon
641f5207b7SJohn Levon struct expression_list *big_condition_stack;
651f5207b7SJohn Levon
661f5207b7SJohn Levon static void split_conditions(struct expression *expr);
671f5207b7SJohn Levon
is_logical_and(struct expression * expr)681f5207b7SJohn Levon static int is_logical_and(struct expression *expr)
691f5207b7SJohn Levon {
701f5207b7SJohn Levon if (expr->op == SPECIAL_LOGICAL_AND)
711f5207b7SJohn Levon return 1;
721f5207b7SJohn Levon return 0;
731f5207b7SJohn Levon }
741f5207b7SJohn Levon
handle_zero_comparisons(struct expression * expr)751f5207b7SJohn Levon static int handle_zero_comparisons(struct expression *expr)
761f5207b7SJohn Levon {
771f5207b7SJohn Levon struct expression *tmp = NULL;
781f5207b7SJohn Levon struct expression *zero;
791f5207b7SJohn Levon
801f5207b7SJohn Levon // if left is zero or right is zero
81*c85f09ccSJohn Levon if (expr_is_zero(expr->left)) {
821f5207b7SJohn Levon zero = strip_expr(expr->left);
831f5207b7SJohn Levon if (zero->type != EXPR_VALUE)
841f5207b7SJohn Levon __split_expr(expr->left);
851f5207b7SJohn Levon tmp = expr->right;
86*c85f09ccSJohn Levon } else if (expr_is_zero(expr->right)) {
871f5207b7SJohn Levon zero = strip_expr(expr->left);
881f5207b7SJohn Levon if (zero->type != EXPR_VALUE)
891f5207b7SJohn Levon __split_expr(expr->right);
901f5207b7SJohn Levon tmp = expr->left;
911f5207b7SJohn Levon } else {
921f5207b7SJohn Levon return 0;
931f5207b7SJohn Levon }
941f5207b7SJohn Levon
951f5207b7SJohn Levon // "if (foo != 0)" is the same as "if (foo)"
961f5207b7SJohn Levon if (expr->op == SPECIAL_NOTEQUAL) {
971f5207b7SJohn Levon split_conditions(tmp);
981f5207b7SJohn Levon return 1;
991f5207b7SJohn Levon }
1001f5207b7SJohn Levon
1011f5207b7SJohn Levon // "if (foo == 0)" is the same as "if (!foo)"
1021f5207b7SJohn Levon if (expr->op == SPECIAL_EQUAL) {
1031f5207b7SJohn Levon split_conditions(tmp);
1041f5207b7SJohn Levon __negate_cond_stacks();
1051f5207b7SJohn Levon return 1;
1061f5207b7SJohn Levon }
1071f5207b7SJohn Levon
1081f5207b7SJohn Levon return 0;
1091f5207b7SJohn Levon }
1101f5207b7SJohn Levon
1111f5207b7SJohn Levon /*
1121f5207b7SJohn Levon * This function is for handling calls to likely/unlikely
1131f5207b7SJohn Levon */
1141f5207b7SJohn Levon
ignore_builtin_expect(struct expression * expr)1151f5207b7SJohn Levon static int ignore_builtin_expect(struct expression *expr)
1161f5207b7SJohn Levon {
1171f5207b7SJohn Levon if (sym_name_is("__builtin_expect", expr->fn)) {
1181f5207b7SJohn Levon split_conditions(first_ptr_list((struct ptr_list *) expr->args));
1191f5207b7SJohn Levon return 1;
1201f5207b7SJohn Levon }
1211f5207b7SJohn Levon return 0;
1221f5207b7SJohn Levon }
1231f5207b7SJohn Levon
1241f5207b7SJohn Levon /*
1251f5207b7SJohn Levon * handle_compound_stmt() is for: foo = ({blah; blah; blah; 1})
1261f5207b7SJohn Levon */
1271f5207b7SJohn Levon
handle_compound_stmt(struct statement * stmt)1281f5207b7SJohn Levon static void handle_compound_stmt(struct statement *stmt)
1291f5207b7SJohn Levon {
1301f5207b7SJohn Levon struct expression *expr = NULL;
1311f5207b7SJohn Levon struct statement *last;
1321f5207b7SJohn Levon struct statement *s;
1331f5207b7SJohn Levon
1341f5207b7SJohn Levon last = last_ptr_list((struct ptr_list *)stmt->stmts);
1351f5207b7SJohn Levon if (last->type == STMT_LABEL) {
1361f5207b7SJohn Levon if (last->label_statement &&
1371f5207b7SJohn Levon last->label_statement->type == STMT_EXPRESSION)
1381f5207b7SJohn Levon expr = last->label_statement->expression;
1391f5207b7SJohn Levon else
1401f5207b7SJohn Levon last = NULL;
1411f5207b7SJohn Levon } else if (last->type != STMT_EXPRESSION) {
1421f5207b7SJohn Levon last = NULL;
1431f5207b7SJohn Levon } else {
1441f5207b7SJohn Levon expr = last->expression;
1451f5207b7SJohn Levon }
1461f5207b7SJohn Levon
1471f5207b7SJohn Levon FOR_EACH_PTR(stmt->stmts, s) {
1481f5207b7SJohn Levon if (s != last)
1491f5207b7SJohn Levon __split_stmt(s);
1501f5207b7SJohn Levon } END_FOR_EACH_PTR(s);
1511f5207b7SJohn Levon if (last && last->type == STMT_LABEL)
1521f5207b7SJohn Levon __split_label_stmt(last);
1531f5207b7SJohn Levon split_conditions(expr);
1541f5207b7SJohn Levon }
1551f5207b7SJohn Levon
handle_preop(struct expression * expr)1561f5207b7SJohn Levon static int handle_preop(struct expression *expr)
1571f5207b7SJohn Levon {
1581f5207b7SJohn Levon struct statement *stmt;
1591f5207b7SJohn Levon
1601f5207b7SJohn Levon if (expr->op == '!') {
1611f5207b7SJohn Levon split_conditions(expr->unop);
1621f5207b7SJohn Levon __negate_cond_stacks();
1631f5207b7SJohn Levon return 1;
1641f5207b7SJohn Levon }
1651f5207b7SJohn Levon stmt = get_expression_statement(expr);
1661f5207b7SJohn Levon if (stmt) {
1671f5207b7SJohn Levon handle_compound_stmt(stmt);
1681f5207b7SJohn Levon return 1;
1691f5207b7SJohn Levon }
1701f5207b7SJohn Levon return 0;
1711f5207b7SJohn Levon }
1721f5207b7SJohn Levon
handle_logical(struct expression * expr)1731f5207b7SJohn Levon static void handle_logical(struct expression *expr)
1741f5207b7SJohn Levon {
1751f5207b7SJohn Levon /*
1761f5207b7SJohn Levon * If we come to an "and" expr then:
1771f5207b7SJohn Levon * We split the left side.
1781f5207b7SJohn Levon * We keep all the current states.
1791f5207b7SJohn Levon * We split the right side.
1801f5207b7SJohn Levon * We keep all the states from both true sides.
1811f5207b7SJohn Levon *
1821f5207b7SJohn Levon * If it's an "or" expr then:
1831f5207b7SJohn Levon * We save the current slist.
1841f5207b7SJohn Levon * We split the left side.
1851f5207b7SJohn Levon * We use the false states for the right side.
1861f5207b7SJohn Levon * We split the right side.
1871f5207b7SJohn Levon * We save all the states that are the same on both sides.
1881f5207b7SJohn Levon */
1891f5207b7SJohn Levon
1901f5207b7SJohn Levon split_conditions(expr->left);
1911f5207b7SJohn Levon
1921f5207b7SJohn Levon if (is_logical_and(expr))
1931f5207b7SJohn Levon __use_cond_true_states();
1941f5207b7SJohn Levon else
1951f5207b7SJohn Levon __use_cond_false_states();
1961f5207b7SJohn Levon
1971f5207b7SJohn Levon __push_cond_stacks();
1981f5207b7SJohn Levon
1991f5207b7SJohn Levon __save_pre_cond_states();
2001f5207b7SJohn Levon split_conditions(expr->right);
2011f5207b7SJohn Levon __discard_pre_cond_states();
2021f5207b7SJohn Levon
2031f5207b7SJohn Levon if (is_logical_and(expr))
2041f5207b7SJohn Levon __and_cond_states();
2051f5207b7SJohn Levon else
2061f5207b7SJohn Levon __or_cond_states();
2071f5207b7SJohn Levon
2081f5207b7SJohn Levon __use_cond_true_states();
2091f5207b7SJohn Levon }
2101f5207b7SJohn Levon
combine_strees(struct stree * orig,struct stree * fake,struct stree * new)2111f5207b7SJohn Levon static struct stree *combine_strees(struct stree *orig, struct stree *fake, struct stree *new)
2121f5207b7SJohn Levon {
2131f5207b7SJohn Levon struct stree *ret = NULL;
2141f5207b7SJohn Levon
2151f5207b7SJohn Levon overwrite_stree(orig, &ret);
2161f5207b7SJohn Levon overwrite_stree(fake, &ret);
2171f5207b7SJohn Levon overwrite_stree(new, &ret);
2181f5207b7SJohn Levon free_stree(&new);
2191f5207b7SJohn Levon
2201f5207b7SJohn Levon return ret;
2211f5207b7SJohn Levon }
2221f5207b7SJohn Levon
2231f5207b7SJohn Levon /*
2241f5207b7SJohn Levon * handle_select()
2251f5207b7SJohn Levon * if ((aaa()?bbb():ccc())) { ...
2261f5207b7SJohn Levon *
2271f5207b7SJohn Levon * This is almost the same as:
2281f5207b7SJohn Levon * if ((aaa() && bbb()) || (!aaa() && ccc())) { ...
2291f5207b7SJohn Levon *
2301f5207b7SJohn Levon * It's a bit complicated because we shouldn't pass aaa()
2311f5207b7SJohn Levon * to the clients more than once.
2321f5207b7SJohn Levon */
2331f5207b7SJohn Levon
handle_select(struct expression * expr)2341f5207b7SJohn Levon static void handle_select(struct expression *expr)
2351f5207b7SJohn Levon {
2361f5207b7SJohn Levon struct stree *a_T = NULL;
2371f5207b7SJohn Levon struct stree *a_F = NULL;
2381f5207b7SJohn Levon struct stree *a_T_b_T = NULL;
2391f5207b7SJohn Levon struct stree *a_T_b_F = NULL;
2401f5207b7SJohn Levon struct stree *a_T_b_fake = NULL;
2411f5207b7SJohn Levon struct stree *a_F_c_T = NULL;
2421f5207b7SJohn Levon struct stree *a_F_c_F = NULL;
2431f5207b7SJohn Levon struct stree *a_F_c_fake = NULL;
2441f5207b7SJohn Levon struct stree *tmp;
2451f5207b7SJohn Levon struct sm_state *sm;
2461f5207b7SJohn Levon
2471f5207b7SJohn Levon /*
2481f5207b7SJohn Levon * Imagine we have this: if (a ? b : c) { ...
2491f5207b7SJohn Levon *
2501f5207b7SJohn Levon * The condition is true if "a" is true and "b" is true or
2511f5207b7SJohn Levon * "a" is false and "c" is true. It's false if "a" is true
2521f5207b7SJohn Levon * and "b" is false or "a" is false and "c" is false.
2531f5207b7SJohn Levon *
2541f5207b7SJohn Levon * The variable name "a_T_b_T" stands for "a true b true" etc.
2551f5207b7SJohn Levon *
2561f5207b7SJohn Levon * But if we know "b" is true then we can simpilify things.
2571f5207b7SJohn Levon * The condition is true if "a" is true or if "a" is false and
2581f5207b7SJohn Levon * "c" is true. The only way the condition can be false is if
2591f5207b7SJohn Levon * "a" is false and "c" is false.
2601f5207b7SJohn Levon *
2611f5207b7SJohn Levon * The remaining thing is the "a_T_b_fake". When we simplify
2621f5207b7SJohn Levon * the equations we have to take into consideration that other
2631f5207b7SJohn Levon * states may have changed that don't play into the true false
2641f5207b7SJohn Levon * equation. Take the following example:
2651f5207b7SJohn Levon * if ({
2661f5207b7SJohn Levon * (flags) = __raw_local_irq_save();
2671f5207b7SJohn Levon * _spin_trylock(lock) ? 1 :
2681f5207b7SJohn Levon * ({ raw_local_irq_restore(flags); 0; });
2691f5207b7SJohn Levon * })
2701f5207b7SJohn Levon * Smatch has to record that the irq flags were restored on the
2711f5207b7SJohn Levon * false path.
2721f5207b7SJohn Levon *
2731f5207b7SJohn Levon */
2741f5207b7SJohn Levon
2751f5207b7SJohn Levon __save_pre_cond_states();
2761f5207b7SJohn Levon
2771f5207b7SJohn Levon split_conditions(expr->conditional);
2781f5207b7SJohn Levon
2791f5207b7SJohn Levon a_T = __copy_cond_true_states();
2801f5207b7SJohn Levon a_F = __copy_cond_false_states();
2811f5207b7SJohn Levon
2821f5207b7SJohn Levon __use_cond_true_states();
2831f5207b7SJohn Levon
2841f5207b7SJohn Levon __push_cond_stacks();
2851f5207b7SJohn Levon __push_fake_cur_stree();
2861f5207b7SJohn Levon split_conditions(expr->cond_true);
2871f5207b7SJohn Levon __process_post_op_stack();
2881f5207b7SJohn Levon a_T_b_fake = __pop_fake_cur_stree();
2891f5207b7SJohn Levon a_T_b_T = combine_strees(a_T, a_T_b_fake, __pop_cond_true_stack());
2901f5207b7SJohn Levon a_T_b_F = combine_strees(a_T, a_T_b_fake, __pop_cond_false_stack());
2911f5207b7SJohn Levon
2921f5207b7SJohn Levon __use_cond_false_states();
2931f5207b7SJohn Levon
2941f5207b7SJohn Levon __push_cond_stacks();
2951f5207b7SJohn Levon __push_fake_cur_stree();
2961f5207b7SJohn Levon split_conditions(expr->cond_false);
2971f5207b7SJohn Levon a_F_c_fake = __pop_fake_cur_stree();
2981f5207b7SJohn Levon a_F_c_T = combine_strees(a_F, a_F_c_fake, __pop_cond_true_stack());
2991f5207b7SJohn Levon a_F_c_F = combine_strees(a_F, a_F_c_fake, __pop_cond_false_stack());
3001f5207b7SJohn Levon
3011f5207b7SJohn Levon /* We have to restore the pre condition states so that
3021f5207b7SJohn Levon implied_condition_true() will use the right cur_stree */
3031f5207b7SJohn Levon __use_pre_cond_states();
3041f5207b7SJohn Levon
3051f5207b7SJohn Levon if (implied_condition_true(expr->cond_true)) {
3061f5207b7SJohn Levon free_stree(&a_T_b_T);
3071f5207b7SJohn Levon free_stree(&a_T_b_F);
3081f5207b7SJohn Levon a_T_b_T = clone_stree(a_T);
3091f5207b7SJohn Levon overwrite_stree(a_T_b_fake, &a_T_b_T);
3101f5207b7SJohn Levon }
3111f5207b7SJohn Levon if (implied_condition_false(expr->cond_true)) {
3121f5207b7SJohn Levon free_stree(&a_T_b_T);
3131f5207b7SJohn Levon free_stree(&a_T_b_F);
3141f5207b7SJohn Levon a_T_b_F = clone_stree(a_T);
3151f5207b7SJohn Levon overwrite_stree(a_T_b_fake, &a_T_b_F);
3161f5207b7SJohn Levon }
3171f5207b7SJohn Levon if (implied_condition_true(expr->cond_false)) {
3181f5207b7SJohn Levon free_stree(&a_F_c_T);
3191f5207b7SJohn Levon free_stree(&a_F_c_F);
3201f5207b7SJohn Levon a_F_c_T = clone_stree(a_F);
3211f5207b7SJohn Levon overwrite_stree(a_F_c_fake, &a_F_c_T);
3221f5207b7SJohn Levon }
3231f5207b7SJohn Levon if (implied_condition_false(expr->cond_false)) {
3241f5207b7SJohn Levon free_stree(&a_F_c_T);
3251f5207b7SJohn Levon free_stree(&a_F_c_F);
3261f5207b7SJohn Levon a_F_c_F = clone_stree(a_F);
3271f5207b7SJohn Levon overwrite_stree(a_F_c_fake, &a_F_c_F);
3281f5207b7SJohn Levon }
3291f5207b7SJohn Levon
3301f5207b7SJohn Levon merge_stree(&a_T_b_T, a_F_c_T);
3311f5207b7SJohn Levon merge_stree(&a_T_b_F, a_F_c_F);
3321f5207b7SJohn Levon
3331f5207b7SJohn Levon tmp = __pop_cond_true_stack();
3341f5207b7SJohn Levon free_stree(&tmp);
3351f5207b7SJohn Levon tmp = __pop_cond_false_stack();
3361f5207b7SJohn Levon free_stree(&tmp);
3371f5207b7SJohn Levon
3381f5207b7SJohn Levon __push_cond_stacks();
3391f5207b7SJohn Levon FOR_EACH_SM(a_T_b_T, sm) {
3401f5207b7SJohn Levon __set_true_false_sm(sm, NULL);
3411f5207b7SJohn Levon } END_FOR_EACH_SM(sm);
3421f5207b7SJohn Levon FOR_EACH_SM(a_T_b_F, sm) {
3431f5207b7SJohn Levon __set_true_false_sm(NULL, sm);
3441f5207b7SJohn Levon } END_FOR_EACH_SM(sm);
3451f5207b7SJohn Levon __free_set_states();
3461f5207b7SJohn Levon
3471f5207b7SJohn Levon free_stree(&a_T_b_fake);
3481f5207b7SJohn Levon free_stree(&a_F_c_fake);
3491f5207b7SJohn Levon free_stree(&a_F_c_T);
3501f5207b7SJohn Levon free_stree(&a_F_c_F);
3511f5207b7SJohn Levon free_stree(&a_T_b_T);
3521f5207b7SJohn Levon free_stree(&a_T_b_F);
3531f5207b7SJohn Levon free_stree(&a_T);
3541f5207b7SJohn Levon free_stree(&a_F);
3551f5207b7SJohn Levon }
3561f5207b7SJohn Levon
handle_comma(struct expression * expr)3571f5207b7SJohn Levon static void handle_comma(struct expression *expr)
3581f5207b7SJohn Levon {
3591f5207b7SJohn Levon __split_expr(expr->left);
3601f5207b7SJohn Levon split_conditions(expr->right);
3611f5207b7SJohn Levon }
3621f5207b7SJohn Levon
make_op_unsigned(int op)3631f5207b7SJohn Levon static int make_op_unsigned(int op)
3641f5207b7SJohn Levon {
3651f5207b7SJohn Levon switch (op) {
3661f5207b7SJohn Levon case '<':
3671f5207b7SJohn Levon return SPECIAL_UNSIGNED_LT;
3681f5207b7SJohn Levon case SPECIAL_LTE:
3691f5207b7SJohn Levon return SPECIAL_UNSIGNED_LTE;
3701f5207b7SJohn Levon case '>':
3711f5207b7SJohn Levon return SPECIAL_UNSIGNED_GT;
3721f5207b7SJohn Levon case SPECIAL_GTE:
3731f5207b7SJohn Levon return SPECIAL_UNSIGNED_GTE;
3741f5207b7SJohn Levon }
3751f5207b7SJohn Levon return op;
3761f5207b7SJohn Levon }
3771f5207b7SJohn Levon
hackup_unsigned_compares(struct expression * expr)3781f5207b7SJohn Levon static void hackup_unsigned_compares(struct expression *expr)
3791f5207b7SJohn Levon {
3801f5207b7SJohn Levon if (expr->type != EXPR_COMPARE)
3811f5207b7SJohn Levon return;
3821f5207b7SJohn Levon
3831f5207b7SJohn Levon if (type_unsigned(get_type(expr)))
3841f5207b7SJohn Levon expr->op = make_op_unsigned(expr->op);
3851f5207b7SJohn Levon }
3861f5207b7SJohn Levon
do_condition(struct expression * expr)3871f5207b7SJohn Levon static void do_condition(struct expression *expr)
3881f5207b7SJohn Levon {
3891f5207b7SJohn Levon __fold_in_set_states();
3901f5207b7SJohn Levon __push_fake_cur_stree();
3911f5207b7SJohn Levon __pass_to_client(expr, CONDITION_HOOK);
3921f5207b7SJohn Levon __fold_in_set_states();
3931f5207b7SJohn Levon }
3941f5207b7SJohn Levon
split_conditions(struct expression * expr)3951f5207b7SJohn Levon static void split_conditions(struct expression *expr)
3961f5207b7SJohn Levon {
3971f5207b7SJohn Levon if (option_debug) {
3981f5207b7SJohn Levon char *cond = expr_to_str(expr);
3991f5207b7SJohn Levon
4001f5207b7SJohn Levon sm_msg("%d in split_conditions (%s)", get_lineno(), cond);
4011f5207b7SJohn Levon free_string(cond);
4021f5207b7SJohn Levon }
4031f5207b7SJohn Levon
4041f5207b7SJohn Levon expr = strip_expr_set_parent(expr);
4051f5207b7SJohn Levon if (!expr) {
4061f5207b7SJohn Levon __fold_in_set_states();
4071f5207b7SJohn Levon return;
4081f5207b7SJohn Levon }
4091f5207b7SJohn Levon
4101f5207b7SJohn Levon /*
4111f5207b7SJohn Levon * On fast paths (and also I guess some people think it's cool) people
4121f5207b7SJohn Levon * sometimes use | instead of ||. It works the same basically except
4131f5207b7SJohn Levon * that || implies a memory barrier between conditions. The easiest way
4141f5207b7SJohn Levon * to handle it is by pretending that | also has a barrier and re-using
4151f5207b7SJohn Levon * all the normal condition code. This potentially hides some bugs, but
4161f5207b7SJohn Levon * people who write code like this should just be careful or they
4171f5207b7SJohn Levon * deserve bugs.
4181f5207b7SJohn Levon *
4191f5207b7SJohn Levon * We could potentially treat boolean bitwise & this way but that seems
4201f5207b7SJohn Levon * too complicated to deal with.
4211f5207b7SJohn Levon */
4221f5207b7SJohn Levon if (expr->type == EXPR_BINOP && expr->op == '|') {
423efe51d0cSJohn Levon expr_set_parent_expr(expr->left, expr);
424efe51d0cSJohn Levon expr_set_parent_expr(expr->right, expr);
4251f5207b7SJohn Levon handle_logical(expr);
4261f5207b7SJohn Levon return;
4271f5207b7SJohn Levon }
4281f5207b7SJohn Levon
4291f5207b7SJohn Levon switch (expr->type) {
4301f5207b7SJohn Levon case EXPR_LOGICAL:
4311f5207b7SJohn Levon expr_set_parent_expr(expr->left, expr);
4321f5207b7SJohn Levon expr_set_parent_expr(expr->right, expr);
4331f5207b7SJohn Levon __pass_to_client(expr, LOGIC_HOOK);
4341f5207b7SJohn Levon handle_logical(expr);
4351f5207b7SJohn Levon return;
4361f5207b7SJohn Levon case EXPR_COMPARE:
4371f5207b7SJohn Levon expr_set_parent_expr(expr->left, expr);
4381f5207b7SJohn Levon expr_set_parent_expr(expr->right, expr);
4391f5207b7SJohn Levon hackup_unsigned_compares(expr);
4401f5207b7SJohn Levon if (handle_zero_comparisons(expr))
4411f5207b7SJohn Levon return;
4421f5207b7SJohn Levon break;
4431f5207b7SJohn Levon case EXPR_CALL:
4441f5207b7SJohn Levon if (ignore_builtin_expect(expr))
4451f5207b7SJohn Levon return;
4461f5207b7SJohn Levon break;
4471f5207b7SJohn Levon case EXPR_PREOP:
4481f5207b7SJohn Levon expr_set_parent_expr(expr->unop, expr);
4491f5207b7SJohn Levon if (handle_preop(expr))
4501f5207b7SJohn Levon return;
4511f5207b7SJohn Levon break;
4521f5207b7SJohn Levon case EXPR_CONDITIONAL:
4531f5207b7SJohn Levon case EXPR_SELECT:
4541f5207b7SJohn Levon expr_set_parent_expr(expr->conditional, expr);
4551f5207b7SJohn Levon expr_set_parent_expr(expr->cond_true, expr);
4561f5207b7SJohn Levon expr_set_parent_expr(expr->cond_false, expr);
4571f5207b7SJohn Levon handle_select(expr);
4581f5207b7SJohn Levon return;
4591f5207b7SJohn Levon case EXPR_COMMA:
4601f5207b7SJohn Levon expr_set_parent_expr(expr->left, expr);
4611f5207b7SJohn Levon expr_set_parent_expr(expr->right, expr);
4621f5207b7SJohn Levon handle_comma(expr);
4631f5207b7SJohn Levon return;
4641f5207b7SJohn Levon }
4651f5207b7SJohn Levon
4661f5207b7SJohn Levon /* fixme: this should be in smatch_flow.c
4671f5207b7SJohn Levon but because of the funny stuff we do with conditions
4681f5207b7SJohn Levon it's awkward to put it there. We would need to
4691f5207b7SJohn Levon call CONDITION_HOOK in smatch_flow as well.
4701f5207b7SJohn Levon */
4711f5207b7SJohn Levon push_expression(&big_expression_stack, expr);
4721f5207b7SJohn Levon push_expression(&big_condition_stack, expr);
4731f5207b7SJohn Levon
4741f5207b7SJohn Levon if (expr->type == EXPR_COMPARE) {
4751f5207b7SJohn Levon if (expr->left->type != EXPR_POSTOP)
4761f5207b7SJohn Levon __split_expr(expr->left);
4771f5207b7SJohn Levon if (expr->right->type != EXPR_POSTOP)
4781f5207b7SJohn Levon __split_expr(expr->right);
4791f5207b7SJohn Levon } else if (expr->type != EXPR_POSTOP) {
4801f5207b7SJohn Levon __split_expr(expr);
4811f5207b7SJohn Levon }
4821f5207b7SJohn Levon do_condition(expr);
4831f5207b7SJohn Levon if (expr->type == EXPR_COMPARE) {
4841f5207b7SJohn Levon if (expr->left->type == EXPR_POSTOP)
4851f5207b7SJohn Levon __split_expr(expr->left);
4861f5207b7SJohn Levon if (expr->right->type == EXPR_POSTOP)
4871f5207b7SJohn Levon __split_expr(expr->right);
4881f5207b7SJohn Levon } else if (expr->type == EXPR_POSTOP) {
4891f5207b7SJohn Levon __split_expr(expr);
4901f5207b7SJohn Levon }
4911f5207b7SJohn Levon __push_fake_cur_stree();
4921f5207b7SJohn Levon __process_post_op_stack();
4931f5207b7SJohn Levon __fold_in_set_states();
4941f5207b7SJohn Levon pop_expression(&big_condition_stack);
4951f5207b7SJohn Levon pop_expression(&big_expression_stack);
4961f5207b7SJohn Levon }
4971f5207b7SJohn Levon
4981f5207b7SJohn Levon static int inside_condition;
__split_whole_condition(struct expression * expr)4991f5207b7SJohn Levon void __split_whole_condition(struct expression *expr)
5001f5207b7SJohn Levon {
5011f5207b7SJohn Levon sm_debug("%d in __split_whole_condition\n", get_lineno());
5021f5207b7SJohn Levon inside_condition++;
5031f5207b7SJohn Levon __save_pre_cond_states();
5041f5207b7SJohn Levon __push_cond_stacks();
5051f5207b7SJohn Levon /* it's a hack, but it's sometimes handy to have this stuff
5061f5207b7SJohn Levon on the big_expression_stack. */
5071f5207b7SJohn Levon push_expression(&big_expression_stack, expr);
5081f5207b7SJohn Levon split_conditions(expr);
5091f5207b7SJohn Levon __use_cond_states();
5101f5207b7SJohn Levon __pass_to_client(expr, WHOLE_CONDITION_HOOK);
5111f5207b7SJohn Levon pop_expression(&big_expression_stack);
5121f5207b7SJohn Levon inside_condition--;
5131f5207b7SJohn Levon sm_debug("%d done __split_whole_condition\n", get_lineno());
5141f5207b7SJohn Levon }
5151f5207b7SJohn Levon
__handle_logic(struct expression * expr)5161f5207b7SJohn Levon void __handle_logic(struct expression *expr)
5171f5207b7SJohn Levon {
5181f5207b7SJohn Levon sm_debug("%d in __handle_logic\n", get_lineno());
5191f5207b7SJohn Levon inside_condition++;
5201f5207b7SJohn Levon __save_pre_cond_states();
5211f5207b7SJohn Levon __push_cond_stacks();
5221f5207b7SJohn Levon /* it's a hack, but it's sometimes handy to have this stuff
5231f5207b7SJohn Levon on the big_expression_stack. */
5241f5207b7SJohn Levon push_expression(&big_expression_stack, expr);
5251f5207b7SJohn Levon if (expr)
5261f5207b7SJohn Levon split_conditions(expr);
5271f5207b7SJohn Levon __use_cond_states();
5281f5207b7SJohn Levon __pass_to_client(expr, WHOLE_CONDITION_HOOK);
5291f5207b7SJohn Levon pop_expression(&big_expression_stack);
5301f5207b7SJohn Levon __merge_false_states();
5311f5207b7SJohn Levon inside_condition--;
5321f5207b7SJohn Levon sm_debug("%d done __handle_logic\n", get_lineno());
5331f5207b7SJohn Levon }
5341f5207b7SJohn Levon
is_condition(struct expression * expr)5351f5207b7SJohn Levon int is_condition(struct expression *expr)
5361f5207b7SJohn Levon {
5371f5207b7SJohn Levon
5381f5207b7SJohn Levon expr = strip_expr(expr);
5391f5207b7SJohn Levon if (!expr)
5401f5207b7SJohn Levon return 0;
5411f5207b7SJohn Levon
5421f5207b7SJohn Levon switch (expr->type) {
5431f5207b7SJohn Levon case EXPR_LOGICAL:
5441f5207b7SJohn Levon case EXPR_COMPARE:
5451f5207b7SJohn Levon return 1;
5461f5207b7SJohn Levon case EXPR_PREOP:
5471f5207b7SJohn Levon if (expr->op == '!')
5481f5207b7SJohn Levon return 1;
5491f5207b7SJohn Levon }
5501f5207b7SJohn Levon return 0;
5511f5207b7SJohn Levon }
5521f5207b7SJohn Levon
__handle_condition_assigns(struct expression * expr)5531f5207b7SJohn Levon int __handle_condition_assigns(struct expression *expr)
5541f5207b7SJohn Levon {
5551f5207b7SJohn Levon struct expression *right;
5561f5207b7SJohn Levon struct stree *true_stree, *false_stree, *fake_stree;
5571f5207b7SJohn Levon struct sm_state *sm;
5581f5207b7SJohn Levon
5591f5207b7SJohn Levon if (expr->op != '=')
5601f5207b7SJohn Levon return 0;
5611f5207b7SJohn Levon right = strip_expr(expr->right);
5621f5207b7SJohn Levon if (!is_condition(expr->right))
5631f5207b7SJohn Levon return 0;
5641f5207b7SJohn Levon
5651f5207b7SJohn Levon sm_debug("%d in __handle_condition_assigns\n", get_lineno());
5661f5207b7SJohn Levon inside_condition++;
5671f5207b7SJohn Levon __save_pre_cond_states();
5681f5207b7SJohn Levon __push_cond_stacks();
5691f5207b7SJohn Levon /* it's a hack, but it's sometimes handy to have this stuff
5701f5207b7SJohn Levon on the big_expression_stack. */
5711f5207b7SJohn Levon push_expression(&big_expression_stack, right);
5721f5207b7SJohn Levon split_conditions(right);
5731f5207b7SJohn Levon true_stree = __get_true_states();
5741f5207b7SJohn Levon false_stree = __get_false_states();
5751f5207b7SJohn Levon __use_cond_states();
5761f5207b7SJohn Levon __push_fake_cur_stree();
5771f5207b7SJohn Levon set_extra_expr_mod(expr->left, alloc_estate_sval(sval_type_val(get_type(expr->left), 1)));
5781f5207b7SJohn Levon __pass_to_client(right, WHOLE_CONDITION_HOOK);
5791f5207b7SJohn Levon
5801f5207b7SJohn Levon fake_stree = __pop_fake_cur_stree();
5811f5207b7SJohn Levon FOR_EACH_SM(fake_stree, sm) {
5821f5207b7SJohn Levon overwrite_sm_state_stree(&true_stree, sm);
5831f5207b7SJohn Levon } END_FOR_EACH_SM(sm);
5841f5207b7SJohn Levon free_stree(&fake_stree);
5851f5207b7SJohn Levon
5861f5207b7SJohn Levon pop_expression(&big_expression_stack);
5871f5207b7SJohn Levon inside_condition--;
5881f5207b7SJohn Levon
5891f5207b7SJohn Levon __push_true_states();
5901f5207b7SJohn Levon
5911f5207b7SJohn Levon __use_false_states();
5921f5207b7SJohn Levon __push_fake_cur_stree();
5931f5207b7SJohn Levon set_extra_expr_mod(expr->left, alloc_estate_sval(sval_type_val(get_type(expr->left), 0)));
5941f5207b7SJohn Levon
5951f5207b7SJohn Levon fake_stree = __pop_fake_cur_stree();
5961f5207b7SJohn Levon FOR_EACH_SM(fake_stree, sm) {
5971f5207b7SJohn Levon overwrite_sm_state_stree(&false_stree, sm);
5981f5207b7SJohn Levon } END_FOR_EACH_SM(sm);
5991f5207b7SJohn Levon free_stree(&fake_stree);
6001f5207b7SJohn Levon
6011f5207b7SJohn Levon __merge_true_states();
6021f5207b7SJohn Levon merge_fake_stree(&true_stree, false_stree);
6031f5207b7SJohn Levon free_stree(&false_stree);
6041f5207b7SJohn Levon FOR_EACH_SM(true_stree, sm) {
6051f5207b7SJohn Levon __set_sm(sm);
6061f5207b7SJohn Levon } END_FOR_EACH_SM(sm);
6071f5207b7SJohn Levon
6081f5207b7SJohn Levon __pass_to_client(expr, ASSIGNMENT_HOOK);
6091f5207b7SJohn Levon sm_debug("%d done __handle_condition_assigns\n", get_lineno());
6101f5207b7SJohn Levon return 1;
6111f5207b7SJohn Levon }
6121f5207b7SJohn Levon
is_select_assign(struct expression * expr)6131f5207b7SJohn Levon static int is_select_assign(struct expression *expr)
6141f5207b7SJohn Levon {
6151f5207b7SJohn Levon struct expression *right;
6161f5207b7SJohn Levon
6171f5207b7SJohn Levon if (expr->op != '=')
6181f5207b7SJohn Levon return 0;
6191f5207b7SJohn Levon right = strip_expr(expr->right);
6201f5207b7SJohn Levon if (right->type == EXPR_CONDITIONAL)
6211f5207b7SJohn Levon return 1;
6221f5207b7SJohn Levon if (right->type == EXPR_SELECT)
6231f5207b7SJohn Levon return 1;
6241f5207b7SJohn Levon return 0;
6251f5207b7SJohn Levon }
6261f5207b7SJohn Levon
__handle_select_assigns(struct expression * expr)6271f5207b7SJohn Levon int __handle_select_assigns(struct expression *expr)
6281f5207b7SJohn Levon {
6291f5207b7SJohn Levon struct expression *right;
6301f5207b7SJohn Levon struct stree *final_states = NULL;
6311f5207b7SJohn Levon struct sm_state *sm;
6321f5207b7SJohn Levon int is_true;
6331f5207b7SJohn Levon int is_false;
6341f5207b7SJohn Levon
6351f5207b7SJohn Levon if (!is_select_assign(expr))
6361f5207b7SJohn Levon return 0;
6371f5207b7SJohn Levon sm_debug("%d in __handle_ternary_assigns\n", get_lineno());
6381f5207b7SJohn Levon right = strip_expr(expr->right);
6391f5207b7SJohn Levon __pass_to_client(right, SELECT_HOOK);
6401f5207b7SJohn Levon
6411f5207b7SJohn Levon is_true = implied_condition_true(right->conditional);
6421f5207b7SJohn Levon is_false = implied_condition_false(right->conditional);
6431f5207b7SJohn Levon
6441f5207b7SJohn Levon /* hah hah. the ultra fake out */
6451f5207b7SJohn Levon __save_pre_cond_states();
6461f5207b7SJohn Levon __split_whole_condition(right->conditional);
6471f5207b7SJohn Levon
6481f5207b7SJohn Levon if (!is_false) {
6491f5207b7SJohn Levon struct expression *fake_expr;
6501f5207b7SJohn Levon
6511f5207b7SJohn Levon if (right->cond_true)
6521f5207b7SJohn Levon fake_expr = assign_expression(expr->left, expr->op, right->cond_true);
6531f5207b7SJohn Levon else
6541f5207b7SJohn Levon fake_expr = assign_expression(expr->left, expr->op, right->conditional);
6551f5207b7SJohn Levon __split_expr(fake_expr);
6561f5207b7SJohn Levon final_states = clone_stree(__get_cur_stree());
6571f5207b7SJohn Levon }
6581f5207b7SJohn Levon
6591f5207b7SJohn Levon __use_false_states();
6601f5207b7SJohn Levon if (!is_true) {
6611f5207b7SJohn Levon struct expression *fake_expr;
6621f5207b7SJohn Levon
6631f5207b7SJohn Levon fake_expr = assign_expression(expr->left, expr->op, right->cond_false);
6641f5207b7SJohn Levon __split_expr(fake_expr);
6651f5207b7SJohn Levon merge_stree(&final_states, __get_cur_stree());
6661f5207b7SJohn Levon }
6671f5207b7SJohn Levon
6681f5207b7SJohn Levon __use_pre_cond_states();
6691f5207b7SJohn Levon
6701f5207b7SJohn Levon FOR_EACH_SM(final_states, sm) {
6711f5207b7SJohn Levon __set_sm(sm);
6721f5207b7SJohn Levon } END_FOR_EACH_SM(sm);
6731f5207b7SJohn Levon
6741f5207b7SJohn Levon free_stree(&final_states);
6751f5207b7SJohn Levon
6761f5207b7SJohn Levon sm_debug("%d done __handle_ternary_assigns\n", get_lineno());
6771f5207b7SJohn Levon
6781f5207b7SJohn Levon return 1;
6791f5207b7SJohn Levon }
6801f5207b7SJohn Levon
split_then_return_last(struct statement * stmt)6811f5207b7SJohn Levon static struct statement *split_then_return_last(struct statement *stmt)
6821f5207b7SJohn Levon {
6831f5207b7SJohn Levon struct statement *tmp;
6841f5207b7SJohn Levon struct statement *last_stmt;
6851f5207b7SJohn Levon
6861f5207b7SJohn Levon last_stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
6871f5207b7SJohn Levon if (!last_stmt)
6881f5207b7SJohn Levon return NULL;
6891f5207b7SJohn Levon
6901f5207b7SJohn Levon __push_scope_hooks();
6911f5207b7SJohn Levon FOR_EACH_PTR(stmt->stmts, tmp) {
6921f5207b7SJohn Levon if (tmp == last_stmt) {
6931f5207b7SJohn Levon if (tmp->type == STMT_LABEL) {
6941f5207b7SJohn Levon __split_label_stmt(tmp);
6951f5207b7SJohn Levon return tmp->label_statement;
6961f5207b7SJohn Levon }
6971f5207b7SJohn Levon return last_stmt;
6981f5207b7SJohn Levon }
6991f5207b7SJohn Levon __split_stmt(tmp);
7001f5207b7SJohn Levon } END_FOR_EACH_PTR(tmp);
7011f5207b7SJohn Levon return NULL;
7021f5207b7SJohn Levon }
7031f5207b7SJohn Levon
__handle_expr_statement_assigns(struct expression * expr)7041f5207b7SJohn Levon int __handle_expr_statement_assigns(struct expression *expr)
7051f5207b7SJohn Levon {
7061f5207b7SJohn Levon struct expression *right;
7071f5207b7SJohn Levon struct statement *stmt;
7081f5207b7SJohn Levon
7091f5207b7SJohn Levon right = expr->right;
7101f5207b7SJohn Levon if (right->type == EXPR_PREOP && right->op == '(')
7111f5207b7SJohn Levon right = right->unop;
7121f5207b7SJohn Levon if (right->type != EXPR_STATEMENT)
7131f5207b7SJohn Levon return 0;
7141f5207b7SJohn Levon
7151f5207b7SJohn Levon __expr_stmt_count++;
7161f5207b7SJohn Levon stmt = right->statement;
7171f5207b7SJohn Levon if (stmt->type == STMT_COMPOUND) {
7181f5207b7SJohn Levon struct statement *last_stmt;
7191f5207b7SJohn Levon struct expression *fake_assign;
7201f5207b7SJohn Levon struct expression fake_expr_stmt = { .smatch_flags = Fake, };
7211f5207b7SJohn Levon
7221f5207b7SJohn Levon last_stmt = split_then_return_last(stmt);
7231f5207b7SJohn Levon if (!last_stmt) {
7241f5207b7SJohn Levon __expr_stmt_count--;
7251f5207b7SJohn Levon return 0;
7261f5207b7SJohn Levon }
7271f5207b7SJohn Levon
7281f5207b7SJohn Levon fake_expr_stmt.pos = last_stmt->pos;
7291f5207b7SJohn Levon fake_expr_stmt.type = EXPR_STATEMENT;
7301f5207b7SJohn Levon fake_expr_stmt.op = 0;
7311f5207b7SJohn Levon fake_expr_stmt.statement = last_stmt;
7321f5207b7SJohn Levon
7331f5207b7SJohn Levon fake_assign = assign_expression(expr->left, expr->op, &fake_expr_stmt);
7341f5207b7SJohn Levon __split_expr(fake_assign);
7351f5207b7SJohn Levon
7361f5207b7SJohn Levon __pass_to_client(stmt, STMT_HOOK_AFTER);
7371f5207b7SJohn Levon __call_scope_hooks();
7381f5207b7SJohn Levon } else if (stmt->type == STMT_EXPRESSION) {
7391f5207b7SJohn Levon struct expression *fake_assign;
7401f5207b7SJohn Levon
7411f5207b7SJohn Levon fake_assign = assign_expression(expr->left, expr->op, stmt->expression);
7421f5207b7SJohn Levon __split_expr(fake_assign);
7431f5207b7SJohn Levon
7441f5207b7SJohn Levon } else {
7451f5207b7SJohn Levon __split_stmt(stmt);
7461f5207b7SJohn Levon }
7471f5207b7SJohn Levon __expr_stmt_count--;
7481f5207b7SJohn Levon return 1;
7491f5207b7SJohn Levon }
7501f5207b7SJohn Levon
in_condition(void)7511f5207b7SJohn Levon int in_condition(void)
7521f5207b7SJohn Levon {
7531f5207b7SJohn Levon return inside_condition;
7541f5207b7SJohn Levon }
755