xref: /illumos-gate/usr/src/tools/smatch/src/ssa.c (revision c85f09cc92abd00c84e58ec9f0f5d942906cb713)
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?
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 		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 
insn_before(struct instruction * a,struct instruction * b)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 
kill_store(struct instruction * insn)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 
rewrite_local_var(struct basic_block * bb,pseudo_t addr,int nbr_stores,int nbr_uses)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 
rewrite_single_store(struct instruction * store)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?
ssa_convert_one_var(struct entrypoint * ep,struct symbol * var)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 
lookup_var(struct basic_block * bb,struct symbol * var)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 
ssa_rename_insn(struct basic_block * bb,struct instruction * insn)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 
ssa_rename_insns(struct entrypoint * ep)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 
mark_phi_used(pseudo_t val)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 
ssa_rename_phi(struct instruction * insn)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 
ssa_rename_phis(struct entrypoint * ep)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 
ssa_convert(struct entrypoint * ep)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 }
403