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