xref: /third_party/ltp/tools/sparse/sparse-src/ssa.c (revision f08c3bdf) 
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?
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		// (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
77static void kill_store(struct instruction *insn)
78{
79	remove_use(&insn->src);
80	remove_use(&insn->target);
81	insn->bb = NULL;
82}
83
84static 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
95static 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?
130static 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
207external_visibility:
208	if (mod & (MOD_NONLOCAL | MOD_STATIC))
209		return;
210	kill_dead_stores(ep, addr, !mod);
211}
212
213static 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
223static struct instruction_list *phis_all;
224static struct instruction_list *phis_used;
225static struct instruction_list *stores;
226
227static 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
244static 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
290static 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
304static 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
319static 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
341static 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
360static 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
372void 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