• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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