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 void set_undefined(struct sm_state
*sm
, struct expression
*mod_expr
)
67 /* this should be called early before any checks have run */
68 set_state(my_id
, sm
->name
, sm
->sym
, &undefined
);
71 static struct smatch_state
*alloc_ssa_new(const char *name
)
73 struct smatch_state
*state
;
76 state
= __alloc_smatch_state(0);
77 snprintf(buf
, sizeof(buf
), "%s:%ld", name
, ssa_id
);
78 state
->name
= alloc_sname(buf
);
85 static struct smatch_state
*alloc_ssa_copy(struct sm_state
*sm
)
87 struct smatch_state
*state
;
89 if (sm
->state
== &undefined
|| sm
->state
== &merged
)
92 state
= __alloc_smatch_state(0);
93 state
->name
= alloc_sname(sm
->state
->name
);
97 static bool whatever_close_enough(struct expression
*left
, struct expression
*right
)
99 struct symbol
*left_type
, *right_type
;
101 left_type
= get_type(left
);
102 right_type
= get_type(right
);
104 if (type_bits(right_type
) == 64) {
105 if (type_bits(left_type
) == 64)
110 if (type_bits(right_type
) == 32) {
111 if (type_bits(left_type
) == 64 || type_bits(left_type
) == 32)
119 static void match_assign(struct expression
*expr
)
121 struct smatch_state
*left_state
;
122 struct sm_state
*orig
, *clone
;
123 struct symbol
*left_sym
, *right_sym
;
124 char *left_name
= NULL
, *right_name
= NULL
;
126 if (__in_fake_assign
)
132 /* The whatever function is more likely to return true #Faster */
133 if (!whatever_close_enough(expr
->left
, expr
->right
) &&
134 !values_fit_type(expr
->left
, expr
->right
))
137 left_name
= expr_to_var_sym(expr
->left
, &left_sym
);
142 * The ordering of this is really tricky. The issue here is that we
143 * have: "dev = of_node_get(node);". The first thing that happens is
144 * the modified hook sets "dev" to undefined. Then the check for
145 * tracking of_node_get/put() allocates an ssa state for "dev". So if
146 * it's set here we can just return. Otherwise track the SSA state.
148 left_state
= get_state(my_id
, left_name
, left_sym
);
149 if (left_state
&& left_state
!= &undefined
)
152 right_name
= expr_to_var_sym(expr
->right
, &right_sym
);
156 orig
= get_sm_state(my_id
, right_name
, right_sym
);
157 if (!orig
|| orig
->state
== &undefined
)
158 orig
= set_state(my_id
, right_name
, right_sym
, alloc_ssa_new(right_name
));
160 /* This can happen in unreachable code or outside of functions I gess */
165 * Cloning is only really necessary for &merged states but it's better
166 * to only have one code path where possible.
169 clone
= clone_sm(orig
);
170 clone
->state
= alloc_ssa_copy(orig
);
171 clone
->name
= alloc_sname(left_name
);
172 clone
->sym
= left_sym
;
176 free_string(left_name
);
177 free_string(right_name
);
180 void set_ssa_state(int owner
, const char *name
, struct symbol
*sym
,
181 struct smatch_state
*state
)
188 sm
= get_sm_state(my_id
, name
, sym
);
189 if (!sm
|| sm
->state
== &undefined
)
190 sm
= set_state(my_id
, name
, sym
, alloc_ssa_new(name
));
193 if (sm
->state
== &merged
) {
195 sm
->state
= alloc_ssa_new(name
);
196 add_possible_sm(sm
, sm
);
201 set_state(owner
, sm
->state
->name
, NULL
, state
);
204 void update_ssa_state(int owner
, const char *name
, struct symbol
*sym
,
205 struct smatch_state
*state
)
207 set_state(owner
, name
, NULL
, state
);
210 void set_ssa_state_expr(int owner
, struct expression
*expr
,
211 struct smatch_state
*state
)
216 name
= expr_to_var_sym(expr
, &sym
);
219 set_ssa_state(owner
, name
, sym
, state
);
223 struct sm_state
*get_ssa_sm_state(int owner
, const char *name
, struct symbol
*sym
)
225 struct sm_state
*sm
, *ret
, *tmp
;
227 // TODO: what about if it is merged because one state is &alloc and the
228 // other state is NULL/uninitialized
230 sm
= get_sm_state(my_id
, name
, sym
);
231 if (!sm
|| sm
->state
== &undefined
)
234 ret
= get_sm_state(owner
, sm
->state
->name
, NULL
);
238 FOR_EACH_PTR(sm
->possible
, tmp
) {
240 tmp
->state
== &merged
||
241 tmp
->state
== &undefined
)
243 ret
= get_sm_state(owner
, tmp
->state
->name
, NULL
);
246 } END_FOR_EACH_PTR(tmp
);
252 * This function uses the SSA infrastructure instead of smatch_assigned.c
253 * to set all the other names of a variable.
256 void ssa_set_all_states(int owner
, const char *name
, struct symbol
*sym
, struct smatch_state
*state
)
258 struct sm_state
*sm
, *tmp
;
260 set_state(owner
, name
, sym
, state
);
262 sm
= get_sm_state(my_id
, name
, sym
);
263 if (!sm
|| sm
->state
== &undefined
|| sm
->state
== &merged
)
266 FOR_EACH_MY_SM(my_id
, __get_cur_stree(), tmp
) {
267 if (strcmp(tmp
->state
->name
, sm
->state
->name
) != 0)
269 set_state(owner
, tmp
->name
, tmp
->sym
, state
);
270 } END_FOR_EACH_SM(tmp
);
273 void ssa_set_all_states_expr(int owner
, struct expression
*expr
, struct smatch_state
*state
)
278 name
= expr_to_var_sym(expr
, &sym
);
281 ssa_set_all_states(owner
, name
, sym
, state
);
285 struct sm_state
*get_ssa_sm_state_expr(int owner
, struct expression
*expr
)
287 struct sm_state
*ret
;
291 name
= expr_to_var_sym(expr
, &sym
);
294 ret
= get_ssa_sm_state(owner
, name
, sym
);
299 struct smatch_state
*get_ssa_state(int owner
, const char *name
, struct symbol
*sym
)
303 sm
= get_ssa_sm_state(my_id
, name
, sym
);
309 struct smatch_state
*get_ssa_state_expr(int owner
, struct expression
*expr
)
313 sm
= get_ssa_sm_state_expr(my_id
, expr
);
319 void register_ssa(int id
)
323 set_dynamic_states(my_id
);
324 add_hook(&match_assign
, ASSIGNMENT_HOOK_AFTER
);
325 add_modification_hook(my_id
, &set_undefined
);