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 int __ors = 0;
  52 int __ands = 0;
  53
  54 static int negative = 0;
  55 int __negate()
  56 {
  57         return negative;
  58 }
  59
  60 static void split_conditions(struct expression *expr);
  61
  62 static int is_logical_and(struct expression *expr)
  63 {
  64         /* If you have if (!(a && b)) smatch translates that to
  65          * if (!a || !b).  Logically those are the same.
  66          */
  67
  68         if ((!__negate() && expr->op == SPECIAL_LOGICAL_AND) ||
  69             (__negate() && expr->op == SPECIAL_LOGICAL_OR))
  70                 return 1;
  71         return 0;
  72 }
  73
  74 static int is_logical_or(struct expression *expr)
  75 {
  76         if ((!__negate() && expr->op == SPECIAL_LOGICAL_OR) ||
  77              (__negate() && expr->op == SPECIAL_LOGICAL_AND))
  78                 return 1;
  79         return 0;
  80 }
  81
  82 static void inc_ands_ors(struct expression *expr)
  83 {
  84         if (is_logical_and(expr))
  85                 __ands++;
  86         else if (is_logical_or(expr))
  87                 __ors++;
  88 }
  89
  90 static void dec_ands_ors(struct expression *expr)
  91 {
  92         if (is_logical_and(expr))
  93                 __ands--;
  94         else if (is_logical_or(expr))
  95                 __ors--;
  96 }
  97
  98 static int is_zero(struct expression *expr)
  99 {
 100         if (expr->type == EXPR_VALUE && expr->value == 0)
 101                 return 1;
 102         if (expr->op == '(')
 103                 return is_zero(expr->unop);
 104         if (expr->type == EXPR_CAST)
 105                 return is_zero(expr->cast_expression);
 106         return 0;
 107 }
 108
 109 static int handle_zero_comparisons(struct expression *expr)
 110 {
 111         struct expression *tmp = NULL;
 112
 113         // if left is zero or right is zero
 114         if (is_zero(expr->left))
 115                 tmp = expr->right;
 116         else if (is_zero(expr->right))
 117                 tmp = expr->left;
 118         else
 119                 return 0;
 120
 121         // "if (foo != 0)" is the same as "if (foo)"
 122         if (expr->op == SPECIAL_NOTEQUAL) {
 123                 split_conditions(tmp);
 124                 return 1;
 125         }
 126
 127         // "if (foo == 0)" is the same as "if (!foo)"
 128         if (expr->op == SPECIAL_EQUAL) {
 129                 negative = (negative +  1)%2;
 130                 split_conditions(tmp);
 131                 negative = (negative +  1)%2;
 132                 return 1;
 133         }
 134
 135         return 0;
 136 }
 137
 138 /*
 139  * This function is for handling calls to likely/unlikely
 140  */
 141
 142 static int ignore_builtin_expect(struct expression *expr)
 143 {
 144         if (sym_name_is("__builtin_expect", expr->fn)) {
 145                 split_conditions(first_ptr_list((struct ptr_list *) expr->args));
 146                 return 1;
 147         }
 148         return 0;
 149 }
 150
 151 static int handle_preop(struct expression *expr)
 152 {
 153         if (expr->op == '!') {
 154                 negative = (negative +  1)%2;
 155                 split_conditions(expr->unop);
 156                 negative = (negative +  1)%2;
 157                 return 1;
 158         }
 159         if (expr->op == '(') {
 160                 split_conditions(expr->unop);
 161                 return 1;
 162         }
 163         return 0;
 164 }
 165
 166 static void handle_logical(struct expression *expr)
 167 {
 168         static int __ors_reached;
 169
 170         inc_ands_ors(expr);
 171         __split_false_states_mini();
 172
 173         split_conditions(expr->left);
 174
 175         if (is_logical_and(expr)) {
 176                 SM_DEBUG("%d and\n", get_lineno());
 177                 __pop_false_states_mini();
 178                 split_conditions(expr->right);
 179         } else if (is_logical_or(expr)) {
 180                 SM_DEBUG("%d or\n", get_lineno());
 181                 if (!__ors_reached) {
 182                         __ors_reached = 1;
 183                         __first_and_clump();
 184                 } else {
 185                         __merge_and_clump();
 186                 }
 187                 __use_false_states_mini();
 188                 split_conditions(expr->right);
 189         }
 190         dec_ands_ors(expr);
 191
 192         if (__ands + __ors == 0) {
 193                 __merge_and_clump();
 194                 __use_and_clumps();
 195                 __ors_reached = 0;
 196         }
 197 }
 198
 199 static void split_conditions(struct expression *expr)
 200 {
 201
 202         SM_DEBUG("%d in split_conditions type=%d\n", get_lineno(), expr->type);
 203
 204         switch(expr->type) {
 205         case EXPR_LOGICAL:
 206                 handle_logical(expr);
 207                 return;
 208         case EXPR_COMPARE:
 209                 if (handle_zero_comparisons(expr))
 210                         return;
 211                 break;
 212         case EXPR_CALL:
 213                 if (ignore_builtin_expect(expr))
 214                         return;
 215                 break;
 216         case EXPR_PREOP:
 217                 if (handle_preop(expr))
 218                         return;
 219                 break;
 220         }
 221
 222         __pass_to_client(expr, CONDITION_HOOK);
 223         __split_expr(expr);
 224 }
 225
 226 void __split_whole_condition(struct expression *expr)
 227 {
 228
 229         __pass_to_client(expr, WHOLE_CONDITION_HOOK);
 230         split_conditions(expr);
 231         SM_DEBUG("%d __ands = %d __ors = %d __negate() = %d\n", get_lineno(),
 232                  __ands, __ors, __negate());
 233 }