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 #include "smatch.h"
  11
  12 #define KERNEL
  13
  14 int __negate = 0;
  15 int __ors = 0;
  16 int __ands = 0;
  17
  18 static void split_conditions(struct expression *expr);
  19
  20 static int is_logical_and(struct expression *expr)
  21 {
  22         /* If you have if (!(a && b)) smatch translates that to
  23          * if (!a || !b).  Logically those are the same.
  24          */
  25
  26         if ((!__negate && expr->op == SPECIAL_LOGICAL_AND) ||
  27             (__negate && expr->op == SPECIAL_LOGICAL_OR))
  28                 return 1;
  29         return 0;
  30 }
  31
  32 static int is_logical_or(struct expression *expr)
  33 {
  34         if ((!__negate && expr->op == SPECIAL_LOGICAL_OR) ||
  35              (__negate && expr->op == SPECIAL_LOGICAL_AND))
  36                 return 1;
  37         return 0;
  38 }
  39
  40 static void inc_ands_ors(struct expression *expr)
  41 {
  42         if (is_logical_and(expr))
  43                 __ands++;
  44         else if (is_logical_or(expr))
  45                 __ors++;
  46 }
  47
  48 static void dec_ands_ors(struct expression *expr)
  49 {
  50         if (is_logical_and(expr))
  51                 __ands--;
  52         else if (is_logical_or(expr))
  53                 __ors--;
  54 }
  55
  56 static void special_kernel_macros(struct expression *expr)
  57 {
  58 #ifdef KERNEL
  59         struct expression *tmp;
  60
  61         tmp = first_ptr_list((struct ptr_list *) expr->args);
  62         if (tmp->op == '!' && tmp->unop->op == '!'
  63             && tmp->unop->unop->op == '(') {
  64                 split_conditions(tmp->unop->unop->unop);
  65         } else {
  66                 __pass_to_client(expr, CONDITION_HOOK);
  67                 __split_expr(expr);
  68                 return;
  69         }
  70
  71 #endif
  72 }
  73
  74 static int is_zero(struct expression *expr)
  75 {
  76         if (expr->type == EXPR_VALUE && expr->value == 0)
  77                 return 1;
  78         if (expr->op == '(')
  79                 return is_zero(expr->unop);
  80         if (expr->type == EXPR_CAST)
  81                 return is_zero(expr->cast_expression);
  82         return 0;
  83 }
  84
  85 static int handle_zero_comparisons(struct expression *expr)
  86 {
  87         struct expression *tmp = NULL;
  88
  89         // if left is zero or right is zero
  90         if (is_zero(expr->left))
  91                 tmp = expr->right;
  92         else if (is_zero(expr->right))
  93                 tmp = expr->left;
  94         else
  95                 return 0;
  96
  97         // "if (foo != 0)" is the same as "if (foo)"
  98         if (expr->op == SPECIAL_NOTEQUAL) {
  99                 split_conditions(tmp);
 100                 return 1;
 101         }
 102
 103         // "if (foo == 0)" is the same as "if (!foo)"
 104         if (expr->op == SPECIAL_EQUAL) {
 105                 __negate = (__negate +  1)%2;
 106                 split_conditions(tmp);
 107                 __negate = (__negate +  1)%2;
 108                 return 1;
 109         }
 110
 111         return 0;
 112 }
 113
 114 static void split_conditions(struct expression *expr)
 115 {
 116         /*
 117          * If you have if ((a || a = foo()), we know a is
 118          * non-null on the true state because 'a' is checked in both and
 119          * groups.  __ors_reached helps with that.  Unfortunately
 120          * smatch doesn't handle stuff like if (a && a = foo())
 121          * because it never occured to me that people would do that...
 122          */
 123
 124         static int __ors_reached;
 125
 126         SM_DEBUG("%d in split_conditions type=%d\n", get_lineno(), expr->type);
 127
 128         if (expr->type == EXPR_COMPARE)
 129                 if (handle_zero_comparisons(expr))
 130                         return;
 131
 132         if (expr->type == EXPR_LOGICAL) {
 133                 unsigned int path_orig;
 134
 135                 inc_ands_ors(expr);
 136                 path_orig = __split_path_id();
 137                 __split_false_states_mini();
 138
 139                 split_conditions(expr->left);
 140
 141                 if (is_logical_and(expr)) {
 142                         __split_path_id();
 143                         __pop_false_states_mini();
 144                         split_conditions(expr->right);
 145                 } else if (is_logical_or(expr)) {
 146                         if (!__ors_reached) {
 147                                 __ors_reached = 1;
 148                                 __first_and_clump();
 149                         } else {
 150                                 __merge_and_clump();
 151                         }
 152                         __split_path_id();
 153                         __use_false_states_mini();
 154                         split_conditions(expr->right);
 155                 }
 156                 dec_ands_ors(expr);
 157
 158                 if (__ands + __ors == 0) {
 159                         __merge_and_clump();
 160                         __use_and_clumps();
 161                         __ors_reached = 0;
 162                 }
 163
 164                 __restore_path_id(path_orig);
 165                 return;
 166         } else if (expr->type == EXPR_PREOP && expr->op == '!') {
 167                 __negate = (__negate +  1)%2;
 168                 split_conditions(expr->unop);
 169                 __negate = (__negate +  1)%2;
 170                 return;
 171         } else if (expr->type == EXPR_PREOP && expr->op == '(') {
 172                 split_conditions(expr->unop);
 173         } else if (expr->type == EXPR_CALL) {
 174
 175                 if (expr->fn->type != EXPR_SYMBOL ||
 176                     strcmp("__builtin_expect", expr->fn->symbol_name->name)) {
 177                         __pass_to_client(expr, CONDITION_HOOK);
 178                         __split_expr(expr);
 179                         return;
 180                 }
 181                 special_kernel_macros(expr);
 182         } else {
 183                 __pass_to_client(expr, CONDITION_HOOK);
 184                 __split_expr(expr);
 185         }
 186 }
 187
 188 void __split_whole_condition(struct expression *expr)
 189 {
 190
 191         split_conditions(expr);
 192         SM_DEBUG("%d __ands = %d __ors = %d __negate = %d\n", get_lineno(),
 193                  __ands, __ors, __negate);
 194 }