introduce: smatch_data/kernel.no_inline_functions
[smatch.git] / smatch_equiv.c
blob4b8ca3f00fd7508458bd37ae8cfb63bd49889d1f
1 /*
2 * sparse/smatch_equiv.c
4 * Copyright (C) 2010 Dan Carpenter.
6 * Licensed under the Open Software License version 1.1
8 */
11 * smatch_equiv.c is for tracking how variables are the same
13 * if (a == b) {
14 * Or
15 * x = y;
17 * When a variable gets modified all the old relationships are
18 * deleted. remove_equiv(expr);
22 #include "smatch.h"
23 #include "smatch_slist.h"
24 #include "smatch_extra.h"
26 ALLOCATOR(relation, "related variables");
28 static struct relation *alloc_relation(const char *name, struct symbol *sym)
30 struct relation *tmp;
32 tmp = __alloc_relation(0);
33 tmp->name = alloc_string(name);
34 tmp->sym = sym;
35 return tmp;
38 struct related_list *clone_related_list(struct related_list *related)
40 struct relation *rel;
41 struct related_list *to_list = NULL;
43 FOR_EACH_PTR(related, rel) {
44 add_ptr_list(&to_list, rel);
45 } END_FOR_EACH_PTR(rel);
47 return to_list;
50 static int cmp_relation(struct relation *a, struct relation *b)
52 int ret;
54 if (a == b)
55 return 0;
57 if (a->sym > b->sym)
58 return -1;
59 if (a->sym < b->sym)
60 return 1;
62 ret = strcmp(a->name, b->name);
63 if (ret)
64 return ret;
66 return 0;
69 struct related_list *get_shared_relations(struct related_list *one,
70 struct related_list *two)
72 struct related_list *ret = NULL;
73 struct relation *one_rel;
74 struct relation *two_rel;
76 PREPARE_PTR_LIST(one, one_rel);
77 PREPARE_PTR_LIST(two, two_rel);
78 for (;;) {
79 if (!one_rel || !two_rel)
80 break;
81 if (cmp_relation(one_rel, two_rel) < 0) {
82 NEXT_PTR_LIST(one_rel);
83 } else if (cmp_relation(one_rel, two_rel) == 0) {
84 add_ptr_list(&ret, one_rel);
85 NEXT_PTR_LIST(one_rel);
86 NEXT_PTR_LIST(two_rel);
87 } else {
88 NEXT_PTR_LIST(two_rel);
91 FINISH_PTR_LIST(two_rel);
92 FINISH_PTR_LIST(one_rel);
94 return ret;
97 static void debug_addition(struct related_list *rlist, const char *name)
99 struct relation *tmp;
101 if (!option_debug_related)
102 return;
104 sm_prefix();
105 sm_printf("(");
106 FOR_EACH_PTR(rlist, tmp) {
107 sm_printf("%s ", tmp->name);
108 } END_FOR_EACH_PTR(tmp);
109 sm_printf(") <-- %s\n", name);
112 static void add_related(struct related_list **rlist, const char *name, struct symbol *sym)
114 struct relation *rel;
115 struct relation *new;
116 struct relation tmp = {
117 .name = (char *)name,
118 .sym = sym
121 debug_addition(*rlist, name);
123 FOR_EACH_PTR(*rlist, rel) {
124 if (cmp_relation(rel, &tmp) < 0)
125 continue;
126 if (cmp_relation(rel, &tmp) == 0)
127 return;
128 new = alloc_relation(name, sym);
129 INSERT_CURRENT(new, rel);
130 return;
131 } END_FOR_EACH_PTR(rel);
132 new = alloc_relation(name, sym);
133 add_ptr_list(rlist, new);
136 void del_related(struct smatch_state *state, const char *name, struct symbol *sym)
138 struct relation *tmp;
139 struct relation remove = {
140 .name = (char *)name,
141 .sym = sym,
144 FOR_EACH_PTR(estate_related(state), tmp) {
145 if (cmp_relation(tmp, &remove) < 0)
146 continue;
147 if (cmp_relation(tmp, &remove) == 0) {
148 DELETE_CURRENT_PTR(tmp);
149 return;
151 return;
152 } END_FOR_EACH_PTR(tmp);
155 static void del_equiv(struct smatch_state *state, const char *name, struct symbol *sym)
157 del_related(state, name, sym);
160 void remove_from_equiv(const char *name, struct symbol *sym)
162 struct sm_state *orig_sm;
163 struct relation *rel;
164 struct smatch_state *state;
165 struct related_list *to_update;
167 // FIXME equiv => related
168 orig_sm = get_sm_state(SMATCH_EXTRA, name, sym);
169 if (!orig_sm || !get_dinfo(orig_sm->state)->related)
170 return;
172 state = clone_estate(orig_sm->state);
173 del_equiv(state, name, sym);
174 to_update = get_dinfo(state)->related;
175 if (ptr_list_size((struct ptr_list *)get_dinfo(state)->related) == 1)
176 get_dinfo(state)->related = NULL;
178 FOR_EACH_PTR(to_update, rel) {
179 struct sm_state *new_sm;
181 new_sm = clone_sm(orig_sm);
182 new_sm->name = rel->name;
183 new_sm->sym = rel->sym;
184 new_sm->state = state;
185 __set_sm(new_sm);
186 } END_FOR_EACH_PTR(rel);
189 void remove_from_equiv_expr(struct expression *expr)
191 char *name;
192 struct symbol *sym;
194 name = expr_to_var_sym(expr, &sym);
195 if (!name || !sym)
196 goto free;
197 remove_from_equiv(name, sym);
198 free:
199 free_string(name);
202 void set_related(struct smatch_state *estate, struct related_list *rlist)
204 if (!estate_related(estate) && !rlist)
205 return;
206 get_dinfo(estate)->related = rlist;
210 * set_equiv() is only used for assignments where we set one variable
211 * equal to the other. a = b;. It's not used for if conditions where
212 * a == b.
214 void set_equiv(struct expression *left, struct expression *right)
216 struct sm_state *right_sm;
217 struct smatch_state *state;
218 struct relation *rel;
219 char *left_name;
220 struct symbol *left_sym;
221 struct related_list *rlist;
223 left_name = expr_to_var_sym(left, &left_sym);
224 if (!left_name || !left_sym)
225 goto free;
227 right_sm = get_sm_state_expr(SMATCH_EXTRA, right);
228 if (!right_sm)
229 right_sm = set_state_expr(SMATCH_EXTRA, right, alloc_estate_whole(get_type(right)));
230 if (!right_sm)
231 goto free;
233 remove_from_equiv(left_name, left_sym);
235 rlist = clone_related_list(estate_related(right_sm->state));
236 add_related(&rlist, right_sm->name, right_sm->sym);
237 add_related(&rlist, left_name, left_sym);
239 state = clone_estate(right_sm->state);
240 get_dinfo(state)->related = rlist;
242 call_extra_mod_hooks(left_name, left_sym, state);
244 FOR_EACH_PTR(rlist, rel) {
245 struct sm_state *new_sm;
247 new_sm = clone_sm(right_sm);
248 new_sm->name = rel->name;
249 new_sm->sym = rel->sym;
250 new_sm->state = state;
251 __set_sm(new_sm);
252 } END_FOR_EACH_PTR(rel);
253 free:
254 free_string(left_name);
257 void set_equiv_state_expr(int id, struct expression *expr, struct smatch_state *state)
259 struct relation *rel;
260 struct smatch_state *estate;
262 estate = get_state_expr(SMATCH_EXTRA, expr);
264 if (!estate)
265 return;
267 FOR_EACH_PTR(get_dinfo(estate)->related, rel) {
268 set_state(id, rel->name, rel->sym, state);
269 } END_FOR_EACH_PTR(rel);