smatch_ssa.c

   1 /*
   2  * Copyright (C) 2021 Oracle.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License
   6  * as published by the Free Software Foundation; either version 2
   7  * of the License, or (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
  16  */
  17
  18 /*
  19  * The truth is I don't know very much about compilers.  I've heard about
  20  * Single Static Assignment and it seems like a useful feature but it's also
  21  * possible I have misunderstood the whole thing.
  22  *
  23  * Anyway, the point is that say we have code like:
  24  * ret = alloc();
  25  * if (ret < 0)
  26  *      return ret;
  27  * p->foo = ret;
  28  * ret = something else;
  29  *
  30  * So the problem here is "p->foo" and "ret" are equivalent at first but then
  31  * not at the end.  We don't really care if "p->foo" is freed or "ret" is freed,
  32  * we care if the value which was initially stored in "ret" is freed.  This is
  33  * different from equiv because "ret" and "p->foo" are not equiv at the end.
  34  * The SSA module doesn't deal with == only with =.
  35  *
  36  * Using this is a bit different and more complicated than I would like.  If
  37  * there is a new state then call set_ssa_state().  When you're getting the
  38  * state it's probably easiest to always use get_ssa_sm_state() because
  39  * afterwards you will need to call update_ssa_state(my_id, sm->name, sm->sym,
  40  * &state); to change the state.  If you call set_ssa_state() that basically
  41  * works too but it's slower because it adds a layer of indirection.
  42  *
  43  */
  44
  45 #include "smatch.h"
  46 #include "smatch_extra.h"
  47 #include "smatch_slist.h"
  48
  49 static int my_id;
  50
  51 static unsigned long ssa_id = 1;
  52
  53 char *ssa_name(const char *name)
  54 {
  55         char *ret;
  56         char *p;
  57
  58         ret = alloc_sname(name);
  59         p = strchr(ret, ':');
  60         if (p)
  61                 *p = '\0';
  62         return ret;
  63 }
  64
  65 static bool is_inc_dec(struct expression *expr)
  66 {
  67         if (!expr)
  68                 return false;
  69         if (expr->type != EXPR_PREOP && expr->type != EXPR_POSTOP)
  70                 return false;
  71         if (expr->op != SPECIAL_INCREMENT && expr->op != SPECIAL_DECREMENT)
  72                 return false;
  73         return true;
  74 }
  75
  76 static void set_undefined(struct sm_state *sm, struct expression *mod_expr)
  77 {
  78         if (!is_inc_dec(mod_expr))
  79                 return;
  80
  81         set_state(my_id, sm->name, sm->sym, &undefined);
  82 }
  83
  84 static struct smatch_state *alloc_ssa_new(const char *name)
  85 {
  86         struct smatch_state *state;
  87         char buf[64];
  88
  89         state = __alloc_smatch_state(0);
  90         snprintf(buf, sizeof(buf), "%s:%ld", name, ssa_id);
  91         state->name = alloc_sname(buf);
  92
  93         ssa_id++;
  94
  95         return state;
  96 }
  97
  98 static struct smatch_state *alloc_ssa_copy(struct sm_state *sm)
  99 {
 100         struct smatch_state *state;
 101
 102         state = __alloc_smatch_state(0);
 103         state->name = alloc_sname(sm->state->name);
 104         return state;
 105 }
 106
 107 static bool whatever_close_enough(struct expression *left, struct expression *right)
 108 {
 109         struct symbol *left_type, *right_type;
 110
 111         left_type = get_type(left);
 112         right_type = get_type(right);
 113
 114         if (type_bits(right_type) == 64) {
 115                 if (type_bits(left_type) == 64)
 116                         return true;
 117                 return false;
 118         }
 119
 120         if (type_bits(right_type) == 32) {
 121                 if (type_bits(left_type) == 64 || type_bits(left_type) == 32)
 122                         return true;
 123                 return false;
 124         }
 125
 126         return false;
 127 }
 128
 129 static void match_assign(struct expression *expr)
 130 {
 131         struct smatch_state *left_state;
 132         struct sm_state *orig, *clone;
 133         struct symbol *left_sym, *right_sym;
 134         char *left_name = NULL, *right_name = NULL;
 135
 136         if (__in_fake_assign)
 137                 return;
 138
 139         if (expr->op != '=')
 140                 return;
 141
 142         /* The whatever function is more likely to return true #Faster */
 143         if (!whatever_close_enough(expr->left, expr->right) &&
 144             !values_fit_type(expr->left, expr->right))
 145                 return;
 146
 147         left_name = expr_to_var_sym(expr->left, &left_sym);
 148         if (!left_name)
 149                 goto free;
 150
 151         /*
 152          * The ordering of this is really nasty.  The issue here is that we
 153          * have: "dev = of_node_get(node);".  The of_node_get() function returns
 154          * "node".  But it's also an increment so we parse the
 155          * "dev = of_node_get()" get's parsed, then the fake parameter
 156          * assignment gets parsed and overwrites the first assignment.
 157          *
 158          * So check if the left side already has a state and return if it does.
 159          */
 160         left_state = get_state(my_id, left_name, left_sym);
 161         if (left_state)
 162                 goto free;
 163
 164         right_name = expr_to_var_sym(expr->right, &right_sym);
 165         if (!right_name)
 166                 goto free;
 167
 168         orig = get_sm_state(my_id, right_name, right_sym);
 169         if (!orig || orig->state == &undefined)
 170                 orig = set_state(my_id, right_name, right_sym, alloc_ssa_new(right_name));
 171
 172         /* This can happen in unreachable code or outside of functions I gess */
 173         if (!orig)
 174                 return;
 175
 176         /*
 177          * Cloning is only really necessary for &merged states but it's better
 178          * to only have one code path where possible.
 179          *
 180          */
 181         clone        = clone_sm(orig);
 182         clone->state = alloc_ssa_copy(orig);
 183         clone->name  = alloc_sname(left_name);
 184         clone->sym   = left_sym;
 185         __set_sm(clone);
 186
 187 free:
 188         free_string(left_name);
 189         free_string(right_name);
 190 }
 191
 192 void set_ssa_state(int owner, const char *name, struct symbol *sym,
 193                struct smatch_state *state)
 194 {
 195         struct sm_state *sm;
 196
 197         if (!name)
 198                 return;
 199
 200         sm = get_sm_state(my_id, name, sym);
 201         if (!sm || sm->state == &undefined)
 202                 sm = set_state(my_id, name, sym, alloc_ssa_new(name));
 203         if (!sm)
 204                 return;
 205         if (sm->state == &merged) {
 206                 sm = clone_sm(sm);
 207                 sm->state = alloc_ssa_new(name);
 208                 add_possible_sm(sm, sm);
 209                 __set_sm(sm);
 210         }
 211         if (!sm)
 212                 return;
 213         set_state(owner, sm->state->name, NULL, state);
 214 }
 215
 216 void update_ssa_state(int owner, const char *name, struct symbol *sym,
 217                       struct smatch_state *state)
 218 {
 219         set_state(owner, name, NULL, state);
 220 }
 221
 222 void set_ssa_state_expr(int owner, struct expression *expr,
 223                 struct smatch_state *state)
 224 {
 225         struct symbol *sym;
 226         char *name;
 227
 228         name = expr_to_var_sym(expr, &sym);
 229         if (!name)
 230                 return;
 231         set_ssa_state(owner, name, sym, state);
 232         free_string(name);
 233 }
 234
 235 struct sm_state *get_ssa_sm_state(int owner, const char *name, struct symbol *sym)
 236 {
 237         struct sm_state *sm, *ret, *tmp;
 238
 239         // TODO: what about if it is merged because one state is &alloc and the
 240         //       other state is NULL/uninitialized
 241
 242         sm = get_sm_state(my_id, name, sym);
 243         if (!sm || sm->state == &undefined)
 244                 return NULL;
 245
 246         ret = get_sm_state(owner, sm->state->name, NULL);
 247         if (ret)
 248                 return ret;
 249
 250         FOR_EACH_PTR(sm->possible, tmp) {
 251                 if (tmp == sm ||
 252                     tmp->state == &merged ||
 253                     tmp->state == &undefined)
 254                         continue;
 255                 ret = get_sm_state(owner, tmp->state->name, NULL);
 256                 if (ret)
 257                         return ret;
 258         } END_FOR_EACH_PTR(tmp);
 259
 260         return NULL;
 261 }
 262
 263 struct sm_state *get_ssa_sm_state_expr(int owner, struct expression *expr)
 264 {
 265         struct sm_state *ret;
 266         struct symbol *sym;
 267         char *name;
 268
 269         name = expr_to_var_sym(expr, &sym);
 270         if (!name)
 271                 return NULL;
 272         ret = get_ssa_sm_state(owner, name, sym);
 273         free_string(name);
 274         return ret;
 275 }
 276
 277 struct smatch_state *get_ssa_state(int owner, const char *name, struct symbol *sym)
 278 {
 279         struct sm_state *sm;
 280
 281         sm = get_ssa_sm_state(my_id, name, sym);
 282         if (!sm)
 283                 return NULL;
 284         return sm->state;
 285 }
 286
 287 struct smatch_state *get_ssa_state_expr(int owner, struct expression *expr)
 288 {
 289         struct sm_state *sm;
 290
 291         sm = get_ssa_sm_state_expr(my_id, expr);
 292         if (!sm)
 293                 return NULL;
 294         return sm->state;
 295 }
 296
 297 void register_ssa(int id)
 298 {
 299         my_id = id;
 300
 301         set_dynamic_states(my_id);
 302         add_hook(&match_assign, ASSIGNMENT_HOOK_AFTER);
 303         add_modification_hook(my_id, &set_undefined);
 304 }
 305