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