smatch.h: introduce sm_pedantic()
[smatch.git] / ssa.c
blob4c86c55c2ec158052fd73d9febdc7e109854dda6
1 // SPDX-License-Identifier: MIT
2 //
3 // SSA conversion
4 // Copyright (C) 2005 Luc Van Oostenryck
5 //
7 #include <assert.h>
8 #include "ssa.h"
9 #include "lib.h"
10 #include "sset.h"
11 #include "dominate.h"
12 #include "flowgraph.h"
13 #include "linearize.h"
14 #include "simplify.h"
15 #include "flow.h"
18 // Is it possible and desirable for this to be promoted to a pseudo?
19 static inline bool is_promotable(struct symbol *type)
21 struct symbol *member;
22 int bf_seen;
23 int nbr;
25 if (type->type == SYM_NODE)
26 type = type->ctype.base_type;
27 switch (type->type) {
28 case SYM_ENUM:
29 case SYM_BITFIELD:
30 case SYM_PTR:
31 case SYM_RESTRICT: // OK, always integer types
32 return 1;
33 case SYM_STRUCT:
34 // we allow a single scalar field
35 // but a run of bitfields count for 1
36 nbr = 0;
37 bf_seen = 0;
38 FOR_EACH_PTR(type->symbol_list, member) {
39 if (is_bitfield_type(member)) {
40 if (bf_seen)
41 continue;
42 bf_seen = 1;
43 } else {
44 bf_seen = 0;
46 if (!is_scalar_type(member))
47 return 0;
48 if (nbr++)
49 return 0;
50 } END_FOR_EACH_PTR(member);
51 if (bf_seen && (type->bit_size > long_ctype.bit_size))
52 return 0;
53 return 1;
54 case SYM_UNION:
55 // FIXME: should be like struct but has problem
56 // when used with/for type cohercion
57 // -----> OK if only same sized integral types
58 FOR_EACH_PTR(type->symbol_list, member) {
59 if (member->bit_size != type->bit_size)
60 return 0;
61 if (!is_integral_type(member))
62 return 0;
63 } END_FOR_EACH_PTR(member);
64 return 1;
65 default:
66 break;
68 if (type->ctype.base_type == &int_type)
69 return 1;
70 if (type->ctype.base_type == &fp_type)
71 return 1;
72 return 0;
75 static bool insn_before(struct instruction *a, struct instruction *b)
77 struct basic_block *bb = a->bb;
78 struct instruction *insn;
80 assert(b->bb == bb);
81 FOR_EACH_PTR(bb->insns, insn) {
82 if (insn == a)
83 return true;
84 if (insn == b)
85 return false;
86 } END_FOR_EACH_PTR(insn);
87 assert(0);
90 static void kill_store(struct instruction *insn)
92 remove_use(&insn->src);
93 remove_use(&insn->target);
94 insn->bb = NULL;
97 static void rewrite_local_var(struct basic_block *bb, pseudo_t addr, int nbr_stores, int nbr_uses)
99 struct instruction *insn;
100 pseudo_t val = NULL;
102 if (!bb)
103 return;
105 FOR_EACH_PTR(bb->insns, insn) {
107 if (!insn->bb || insn->src != addr)
108 continue;
109 switch (insn->opcode) {
110 case OP_LOAD:
111 if (!val)
112 val = undef_pseudo();
113 replace_with_pseudo(insn, val);
114 break;
115 case OP_STORE:
116 val = insn->target;
117 // can't use kill_instruction() unless
118 // we add a fake user to val
119 kill_store(insn);
120 break;
122 } END_FOR_EACH_PTR(insn);
125 static bool rewrite_single_store(struct instruction *store)
127 pseudo_t addr = store->src;
128 struct pseudo_user *pu;
130 FOR_EACH_PTR(addr->users, pu) {
131 struct instruction *insn = pu->insn;
133 if (insn->opcode != OP_LOAD)
134 continue;
136 // Let's try to replace the value of the load
137 // by the value from the store. This is only valid
138 // if the store dominate the load.
140 if (insn->bb == store->bb) {
141 // the load and the store are in the same BB
142 // we can convert if the load is after the store.
143 if (!insn_before(store, insn))
144 continue;
145 } else if (!domtree_dominates(store->bb, insn->bb)) {
146 // we can't convert this load
147 continue;
150 // OK, we can rewrite this load
152 // undefs ?
154 replace_with_pseudo(insn, store->target);
155 } END_FOR_EACH_PTR(pu);
157 // is there some unconverted loads?
158 if (pseudo_user_list_size(addr->users) > 1)
159 return false;
161 kill_store(store);
162 return true;
165 static struct sset *processed;
167 // we would like to know:
168 // is there one or more stores?
169 // are all loads & stores local/done in a single block?
170 static void ssa_convert_one_var(struct entrypoint *ep, struct symbol *var)
172 struct basic_block_list *alpha = NULL;
173 struct basic_block_list *idf = NULL;
174 struct basic_block *samebb = NULL;
175 struct instruction *store = NULL;
176 struct basic_block *bb;
177 struct pseudo_user *pu;
178 unsigned long mod = var->ctype.modifiers;
179 bool local = true;
180 int nbr_stores = 0;
181 int nbr_uses = 0;
182 pseudo_t addr;
184 /* Never used as a symbol? */
185 addr = var->pseudo;
186 if (!addr)
187 return;
189 /* We don't do coverage analysis of volatiles.. */
190 if (mod & MOD_VOLATILE)
191 return;
193 /* ..and symbols with external visibility need more care */
194 mod &= (MOD_NONLOCAL | MOD_STATIC | MOD_ADDRESSABLE);
195 if (mod)
196 goto external_visibility;
198 if (!is_promotable(var))
199 return;
201 // 1) insert in the worklist all BBs that may modify var
202 sset_reset(processed);
203 FOR_EACH_PTR(addr->users, pu) {
204 struct instruction *insn = pu->insn;
205 struct basic_block *bb = insn->bb;
207 switch (insn->opcode) {
208 case OP_STORE:
209 nbr_stores++;
210 store = insn;
211 if (!sset_testset(processed, bb->nr))
212 add_bb(&alpha, bb);
213 /* fall through */
214 case OP_LOAD:
215 if (local) {
216 if (!samebb)
217 samebb = bb;
218 else if (samebb != bb)
219 local = false;
221 nbr_uses++;
222 break;
223 case OP_SYMADDR:
224 mod |= MOD_ADDRESSABLE;
225 goto external_visibility;
226 default:
227 warning(var->pos, "symbol '%s' pseudo used in unexpected way",
228 show_ident(var->ident));
230 } END_FOR_EACH_PTR(pu);
232 if (nbr_stores == 1) {
233 if (rewrite_single_store(store))
234 return;
237 // if all uses are local to a single block
238 // they can easily be rewritten and doesn't need phi-nodes
239 // FIXME: could be done for extended BB too
240 if (local) {
241 rewrite_local_var(samebb, addr, nbr_stores, nbr_uses);
242 return;
245 idf_compute(ep, &idf, alpha);
246 FOR_EACH_PTR(idf, bb) {
247 struct instruction *node = insert_phi_node(bb, var);
248 node->phi_var = var->pseudo;
249 } END_FOR_EACH_PTR(bb);
250 var->torename = 1;
252 external_visibility:
253 if (mod & (MOD_NONLOCAL | MOD_STATIC))
254 return;
255 kill_dead_stores(ep, addr, !mod);
258 static pseudo_t lookup_var(struct basic_block *bb, struct symbol *var)
260 do {
261 pseudo_t val = phi_map_lookup(bb->phi_map, var);
262 if (val)
263 return val;
264 } while ((bb = bb->idom));
265 return undef_pseudo();
268 static struct instruction_list *phis_all;
269 static struct instruction_list *phis_used;
271 static void ssa_rename_insn(struct basic_block *bb, struct instruction *insn)
273 struct symbol *var;
274 pseudo_t addr;
275 pseudo_t val;
277 switch (insn->opcode) {
278 case OP_STORE:
279 addr = insn->src;
280 if (addr->type != PSEUDO_SYM)
281 break;
282 var = addr->sym;
283 if (!var || !var->torename)
284 break;
285 phi_map_update(&bb->phi_map, var, insn->target);
286 kill_store(insn);
287 break;
288 case OP_LOAD:
289 addr = insn->src;
290 if (addr->type != PSEUDO_SYM)
291 break;
292 var = addr->sym;
293 if (!var || !var->torename)
294 break;
295 val = lookup_var(bb, var);
296 replace_with_pseudo(insn, val);
297 break;
298 case OP_PHI:
299 var = insn->type;
300 if (!var || !var->torename)
301 break;
302 phi_map_update(&bb->phi_map, var, insn->target);
303 add_instruction(&phis_all, insn);
304 break;
308 static void ssa_rename_insns(struct entrypoint *ep)
310 struct basic_block *bb;
312 FOR_EACH_PTR(ep->bbs, bb) {
313 struct instruction *insn;
314 FOR_EACH_PTR(bb->insns, insn) {
315 if (!insn->bb)
316 continue;
317 ssa_rename_insn(bb, insn);
318 } END_FOR_EACH_PTR(insn);
319 } END_FOR_EACH_PTR(bb);
322 static void mark_phi_used(pseudo_t val)
324 struct instruction *node;
326 if (val->type != PSEUDO_REG)
327 return;
328 node = val->def;
329 if (node->opcode != OP_PHI)
330 return;
331 if (node->used)
332 return;
333 node->used = 1;
334 add_instruction(&phis_used, node);
337 static void ssa_rename_phi(struct instruction *insn)
339 struct basic_block *par;
340 struct symbol *var;
342 if (!insn->phi_var)
343 return;
344 var = insn->phi_var->sym;
345 if (!var->torename)
346 return;
347 FOR_EACH_PTR(insn->bb->parents, par) {
348 struct instruction *term = delete_last_instruction(&par->insns);
349 pseudo_t val = lookup_var(par, var);
350 pseudo_t phi = alloc_phi(par, val, var);
351 phi->ident = var->ident;
352 add_instruction(&par->insns, term);
353 use_pseudo(insn, phi, add_pseudo(&insn->phi_list, phi));
354 mark_phi_used(val);
355 } END_FOR_EACH_PTR(par);
358 static void ssa_rename_phis(struct entrypoint *ep)
360 struct instruction *phi;
362 phis_used = NULL;
363 FOR_EACH_PTR(phis_all, phi) {
364 if (has_users(phi->target)) {
365 phi->used = 1;
366 add_instruction(&phis_used, phi);
368 } END_FOR_EACH_PTR(phi);
370 FOR_EACH_PTR(phis_used, phi) {
371 if (!phi->bb)
372 continue;
373 ssa_rename_phi(phi);
374 } END_FOR_EACH_PTR(phi);
377 void ssa_convert(struct entrypoint *ep)
379 struct basic_block *bb;
380 pseudo_t pseudo;
381 int first, last;
383 // calculate the number of BBs
384 first = ep->entry->bb->nr;
385 last = first;
386 FOR_EACH_PTR(ep->bbs, bb) {
387 int nr = bb->nr;
388 if (nr > last)
389 last = nr;
390 bb->phi_map = NULL;
391 } END_FOR_EACH_PTR(bb);
393 processed = sset_init(first, last);
395 // try to promote memory accesses to pseudos
396 FOR_EACH_PTR(ep->accesses, pseudo) {
397 ssa_convert_one_var(ep, pseudo->sym);
398 } END_FOR_EACH_PTR(pseudo);
400 // rename the converted accesses
401 phis_all = phis_used = NULL;
402 ssa_rename_insns(ep);
403 ssa_rename_phis(ep);