smatch_conditions.c

   1 /*
   2  * sparse/smatch_conditions.c
   3  *
   4  * Copyright (C) 2006,2008 Dan Carpenter.
   5  *
   6  *  Licensed under the Open Software License version 1.1
   7  *
   8  */
   9
  10 /*
  11  * The simplest type of condition is
  12  * if (a) { ...
  13  *
  14  * The next simplest kind of conditions is
  15  * if (a && b) { c;
  16  * In that case 'a' is true when we get to 'b' and both are true
  17  * when we get to c.
  18  *
  19  * Or's are a little more complicated.
  20  * if (a || b) { c;
  21  * We know 'a' is not true when we get to 'b' but it may be true
  22  * when we get to c.
  23  *
  24  * If we mix and's and or's that's even more complicated.
  25  * if (a && b && c || a && d) { d ;
  26  * 'a' is true when we get to 'b', 'c' and 'd'.
  27  * 'b' is true when we reach 'c' but otherwise we don't know.
  28  *
  29  * The other thing that complicates matters is if we negate
  30  * some if conditions.
  31  * if (!a) { ...
  32  * We pass the un-negated version to the client and flip the true
  33  * and false values internally.
  34  *
  35  * And negations can be part of a compound.
  36  * if (a && !(b || c)) { d;
  37  * In that situation we multiply the negative through to simplify
  38  * stuff so that we can remove the parens like this:
  39  * if (a && !b && !c) { d;
  40  *
  41  * One other thing is that:
  42  * if ((a) != 0){ ...
  43  * that's basically the same as testing for just 'a' so we simplify
  44  * it before passing it to the script.
  45  */
  46
  47 #include "smatch.h"
  48
  49 #define KERNEL
  50
  51 static void split_conditions(struct expression *expr);
  52
  53 static int is_logical_and(struct expression *expr)
  54 {
  55         if (expr->op == SPECIAL_LOGICAL_AND)
  56                 return 1;
  57         return 0;
  58 }
  59
  60 static int handle_zero_comparisons(struct expression *expr)
  61 {
  62         struct expression *tmp = NULL;
  63
  64         // if left is zero or right is zero
  65         if (is_zero(expr->left))
  66                 tmp = expr->right;
  67         else if (is_zero(expr->right))
  68                 tmp = expr->left;
  69         else
  70                 return 0;
  71
  72         // "if (foo != 0)" is the same as "if (foo)"
  73         if (expr->op == SPECIAL_NOTEQUAL) {
  74                 split_conditions(tmp);
  75                 return 1;
  76         }
  77
  78         // "if (foo == 0)" is the same as "if (!foo)"
  79         if (expr->op == SPECIAL_EQUAL) {
  80                 split_conditions(tmp);
  81                 __negate_cond_stacks();
  82                 return 1;
  83         }
  84
  85         return 0;
  86 }
  87
  88 /*
  89  * This function is for handling calls to likely/unlikely
  90  */
  91
  92 static int ignore_builtin_expect(struct expression *expr)
  93 {
  94         if (sym_name_is("__builtin_expect", expr->fn)) {
  95                 split_conditions(first_ptr_list((struct ptr_list *) expr->args));
  96                 return 1;
  97         }
  98         if (sym_name_is("__builtin_constant_p", expr->fn)) {
  99                 split_conditions(first_ptr_list((struct ptr_list *) expr->args));
 100                 return 1;
 101         }
 102         return 0;
 103 }
 104
 105 /*
 106  * handle_compound_stmt() is for: foo = ({blah; blah; blah; 1})
 107  */
 108
 109 static void handle_compound_stmt(struct statement *stmt)
 110 {
 111         struct expression *expr = NULL;
 112         struct statement *last;
 113         struct statement *s;
 114
 115         last = last_ptr_list((struct ptr_list *)stmt->stmts);
 116         if (last->type != STMT_EXPRESSION) {
 117                 last = NULL;
 118         } else {
 119                 expr = last->expression;
 120         }
 121         FOR_EACH_PTR(stmt->stmts, s) {
 122                 if (s != last)
 123                         __split_statements(s);
 124         } END_FOR_EACH_PTR(s);
 125         split_conditions(expr);
 126         return;
 127 }
 128
 129 static int handle_preop(struct expression *expr)
 130 {
 131         struct statement *stmt;
 132
 133         if (expr->op == '!') {
 134                 split_conditions(expr->unop);
 135                 __negate_cond_stacks();
 136                 return 1;
 137         }
 138         stmt = get_block_thing(expr);
 139         if (stmt) {
 140                 handle_compound_stmt(stmt);
 141                 return 1;
 142         }
 143         return 0;
 144 }
 145
 146 static void handle_logical(struct expression *expr)
 147 {
 148         /*
 149          * If we come to an "and" expr then:
 150          * We split the left side.
 151          * We keep all the current states.
 152          * We split the right side.
 153          * We keep all the states from both true sides.
 154          *
 155          * If it's an "or" expr then:
 156          * We save the current slist.
 157          * We split the left side.
 158          * We use the false states for the right side.
 159          * We split the right side.
 160          * We save all the states that are the same on both sides.
 161          */
 162
 163         split_conditions(expr->left);
 164
 165         if (!is_logical_and(expr))
 166                 __use_cond_false_states();
 167
 168         __save_pre_cond_states();
 169         __push_cond_stacks();
 170
 171         split_conditions(expr->right);
 172
 173         if (is_logical_and(expr)) {
 174                 __and_cond_states();
 175         } else {
 176                 __or_cond_states();
 177         }
 178
 179         __pop_pre_cond_states();
 180         __use_cond_true_states();
 181 }
 182
 183 static int handle_rostedt_if(struct expression *expr)
 184 {
 185         if (expr->type != EXPR_CALL)
 186                 return 0;
 187         if (!sym_name_is("__builtin_constant_p", expr->fn))
 188                 return 0;
 189         split_conditions(expr);
 190         return 1;
 191 }
 192
 193 static void handle_select(struct expression *expr)
 194 {
 195         /*
 196          * if ((aaa()?bbb():ccc())) { ...
 197          *
 198          * This is almost the same as:
 199          * if ((aaa() && bbb()) || (!aaa() && ccc())) { ...
 200          *
 201          * It's a bit complicated because we shouldn't pass aaa()
 202          * to the clients more than once.
 203          */
 204
 205         if (handle_rostedt_if(expr->conditional))
 206                 return;
 207
 208         split_conditions(expr->conditional);
 209
 210         __save_false_states_for_later();
 211
 212         if (implied_condition_true(expr->cond_true)) {
 213                 __split_expr(expr->cond_true);
 214         } else {
 215                 __push_cond_stacks();
 216                 split_conditions(expr->cond_true);
 217                 __and_cond_states();
 218         }
 219
 220         if (implied_condition_false(expr->cond_false)) {
 221                 __split_expr(expr->cond_false);
 222                 __pop_pre_cond_states();
 223                 return;
 224         }
 225
 226         __use_previously_stored_false_states();
 227
 228         __save_pre_cond_states();
 229         __push_cond_stacks();
 230         split_conditions(expr->cond_false);
 231         __or_cond_states();
 232         __pop_pre_cond_states();
 233
 234         __use_cond_true_states();
 235 }
 236
 237 static void split_conditions(struct expression *expr)
 238 {
 239
 240         sm_debug("%d in split_conditions type=%d\n", get_lineno(), expr->type);
 241
 242         expr = strip_expr(expr);
 243         if (!expr)
 244                 return;
 245
 246         switch(expr->type) {
 247         case EXPR_LOGICAL:
 248                 handle_logical(expr);
 249                 return;
 250         case EXPR_COMPARE:
 251                 if (handle_zero_comparisons(expr))
 252                         return;
 253                 break;
 254         case EXPR_CALL:
 255                 if (ignore_builtin_expect(expr))
 256                         return;
 257                 break;
 258         case EXPR_PREOP:
 259                 if (handle_preop(expr))
 260                         return;
 261                 break;
 262         case EXPR_CONDITIONAL:
 263         case EXPR_SELECT:
 264                 handle_select(expr);
 265                 return;
 266         }
 267
 268         __split_expr(expr);
 269         __pass_to_client(expr, CONDITION_HOOK);
 270 }
 271
 272 static int inside_condition;
 273 void __split_whole_condition(struct expression *expr)
 274 {
 275         sm_debug("%d in __split_whole_condition\n", get_lineno());
 276         inside_condition++;
 277         __save_pre_cond_states();
 278         __push_cond_stacks();
 279         if (expr)
 280                 split_conditions(expr);
 281         __use_cond_states();
 282         __pass_to_client(expr, WHOLE_CONDITION_HOOK);
 283         inside_condition--;
 284 }
 285
 286 int in_condition()
 287 {
 288         return inside_condition;
 289 }