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?
18static 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
74static 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
89static void kill_store(struct instruction *insn)
90{
91	remove_use(&insn->src);
92	remove_use(&insn->target);
93	insn->bb = NULL;
94}
95
96static 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
124static 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
164static 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?
169static 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
251external_visibility:
252	if (mod & (MOD_NONLOCAL | MOD_STATIC))
253		return;
254	kill_dead_stores(ep, addr, !mod);
255}
256
257static 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
267static struct instruction_list *phis_all;
268static struct instruction_list *phis_used;
269
270static 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
307static 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
321static 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
336static 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
357static 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
376void 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}
403