2 * Copyright (C) 2021 Oracle.
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.
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.
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
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.
23 * Anyway, the point is that say we have code like:
28 * ret = something else;
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 =.
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.
46 #include "smatch_extra.h"
47 #include "smatch_slist.h"
51 static unsigned long ssa_id
= 1;
53 char *ssa_name(const char *name
)
58 ret
= alloc_sname(name
);
65 static bool is_inc_dec(struct expression
*expr
)
69 if (expr
->type
!= EXPR_PREOP
&& expr
->type
!= EXPR_POSTOP
)
71 if (expr
->op
!= SPECIAL_INCREMENT
&& expr
->op
!= SPECIAL_DECREMENT
)
76 static void set_undefined(struct sm_state
*sm
, struct expression
*mod_expr
)
78 if (!is_inc_dec(mod_expr
))
81 set_state(my_id
, sm
->name
, sm
->sym
, &undefined
);
84 static struct smatch_state
*alloc_ssa_new(const char *name
)
86 struct smatch_state
*state
;
89 state
= __alloc_smatch_state(0);
90 snprintf(buf
, sizeof(buf
), "%s:%ld", name
, ssa_id
);
91 state
->name
= alloc_sname(buf
);
98 static struct smatch_state
*alloc_ssa_copy(struct sm_state
*sm
)
100 struct smatch_state
*state
;
102 state
= __alloc_smatch_state(0);
103 state
->name
= alloc_sname(sm
->state
->name
);
107 static bool whatever_close_enough(struct expression
*left
, struct expression
*right
)
109 struct symbol
*left_type
, *right_type
;
111 left_type
= get_type(left
);
112 right_type
= get_type(right
);
114 if (type_bits(right_type
) == 64) {
115 if (type_bits(left_type
) == 64)
120 if (type_bits(right_type
) == 32) {
121 if (type_bits(left_type
) == 64 || type_bits(left_type
) == 32)
129 static void match_assign(struct expression
*expr
)
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
;
136 if (__in_fake_assign
)
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
))
147 left_name
= expr_to_var_sym(expr
->left
, &left_sym
);
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.
158 * So check if the left side already has a state and return if it does.
160 left_state
= get_state(my_id
, left_name
, left_sym
);
164 right_name
= expr_to_var_sym(expr
->right
, &right_sym
);
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
));
172 /* This can happen in unreachable code or outside of functions I gess */
177 * Cloning is only really necessary for &merged states but it's better
178 * to only have one code path where possible.
181 clone
= clone_sm(orig
);
182 clone
->state
= alloc_ssa_copy(orig
);
183 clone
->name
= alloc_sname(left_name
);
184 clone
->sym
= left_sym
;
188 free_string(left_name
);
189 free_string(right_name
);
192 void set_ssa_state(int owner
, const char *name
, struct symbol
*sym
,
193 struct smatch_state
*state
)
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
));
205 if (sm
->state
== &merged
) {
207 sm
->state
= alloc_ssa_new(name
);
208 add_possible_sm(sm
, sm
);
213 set_state(owner
, sm
->state
->name
, NULL
, state
);
216 void update_ssa_state(int owner
, const char *name
, struct symbol
*sym
,
217 struct smatch_state
*state
)
219 set_state(owner
, name
, NULL
, state
);
222 void set_ssa_state_expr(int owner
, struct expression
*expr
,
223 struct smatch_state
*state
)
228 name
= expr_to_var_sym(expr
, &sym
);
231 set_ssa_state(owner
, name
, sym
, state
);
235 struct sm_state
*get_ssa_sm_state(int owner
, const char *name
, struct symbol
*sym
)
237 struct sm_state
*sm
, *ret
, *tmp
;
239 // TODO: what about if it is merged because one state is &alloc and the
240 // other state is NULL/uninitialized
242 sm
= get_sm_state(my_id
, name
, sym
);
243 if (!sm
|| sm
->state
== &undefined
)
246 ret
= get_sm_state(owner
, sm
->state
->name
, NULL
);
250 FOR_EACH_PTR(sm
->possible
, tmp
) {
252 tmp
->state
== &merged
||
253 tmp
->state
== &undefined
)
255 ret
= get_sm_state(owner
, tmp
->state
->name
, NULL
);
258 } END_FOR_EACH_PTR(tmp
);
263 struct sm_state
*get_ssa_sm_state_expr(int owner
, struct expression
*expr
)
265 struct sm_state
*ret
;
269 name
= expr_to_var_sym(expr
, &sym
);
272 ret
= get_ssa_sm_state(owner
, name
, sym
);
277 struct smatch_state
*get_ssa_state(int owner
, const char *name
, struct symbol
*sym
)
281 sm
= get_ssa_sm_state(my_id
, name
, sym
);
287 struct smatch_state
*get_ssa_state_expr(int owner
, struct expression
*expr
)
291 sm
= get_ssa_sm_state_expr(my_id
, expr
);
297 void register_ssa(int id
)
301 set_dynamic_states(my_id
);
302 add_hook(&match_assign
, ASSIGNMENT_HOOK_AFTER
);
303 add_modification_hook(my_id
, &set_undefined
);