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