xref: /illumos-gate/usr/src/tools/smatch/src/liveness.c (revision c85f09cc92abd00c84e58ec9f0f5d942906cb713)
1 /*
2  * Register - track pseudo usage, maybe eventually try to do register
3  * allocation.
4  *
5  * Copyright (C) 2004 Linus Torvalds
6  */
7 
8 #include <assert.h>
9 
10 #include "liveness.h"
11 #include "parse.h"
12 #include "expression.h"
13 #include "linearize.h"
14 #include "flow.h"
15 
phi_defines(struct instruction * phi_node,pseudo_t target,void (* defines)(struct basic_block *,pseudo_t))16 static void phi_defines(struct instruction * phi_node, pseudo_t target,
17 	void (*defines)(struct basic_block *, pseudo_t))
18 {
19 	pseudo_t phi;
20 	FOR_EACH_PTR(phi_node->phi_list, phi) {
21 		struct instruction *def;
22 		if (phi == VOID)
23 			continue;
24 		def = phi->def;
25 		if (!def || !def->bb)
26 			continue;
27 		defines(def->bb, target);
28 	} END_FOR_EACH_PTR(phi);
29 }
30 
asm_liveness(struct basic_block * bb,struct instruction * insn,void (* def)(struct basic_block *,pseudo_t),void (* use)(struct basic_block *,pseudo_t))31 static void asm_liveness(struct basic_block *bb, struct instruction *insn,
32 	void (*def)(struct basic_block *, pseudo_t),
33 	void (*use)(struct basic_block *, pseudo_t))
34 {
35 	struct asm_constraint *entry;
36 
37 	FOR_EACH_PTR(insn->asm_rules->inputs, entry) {
38 		use(bb, entry->pseudo);
39 	} END_FOR_EACH_PTR(entry);
40 
41 	FOR_EACH_PTR(insn->asm_rules->outputs, entry) {
42 		def(bb, entry->pseudo);
43 	} END_FOR_EACH_PTR(entry);
44 }
45 
track_instruction_usage(struct basic_block * bb,struct instruction * insn,void (* def)(struct basic_block *,pseudo_t),void (* use)(struct basic_block *,pseudo_t))46 static void track_instruction_usage(struct basic_block *bb, struct instruction *insn,
47 	void (*def)(struct basic_block *, pseudo_t),
48 	void (*use)(struct basic_block *, pseudo_t))
49 {
50 	pseudo_t pseudo;
51 
52 	#define USES(x)		use(bb, insn->x)
53 	#define DEFINES(x)	def(bb, insn->x)
54 
55 	switch (insn->opcode) {
56 	case OP_RET:
57 	case OP_COMPUTEDGOTO:
58 		USES(src);
59 		break;
60 
61 	case OP_CBR:
62 	case OP_SWITCH:
63 		USES(cond);
64 		break;
65 
66 	/* Binary */
67 	case OP_BINARY ... OP_BINARY_END:
68 	case OP_FPCMP ... OP_FPCMP_END:
69 	case OP_BINCMP ... OP_BINCMP_END:
70 		USES(src1); USES(src2); DEFINES(target);
71 		break;
72 
73 	/* Uni */
74 	case OP_UNOP ... OP_UNOP_END:
75 	case OP_SYMADDR:
76 		USES(src1); DEFINES(target);
77 		break;
78 
79 	case OP_SEL:
80 		USES(src1); USES(src2); USES(src3); DEFINES(target);
81 		break;
82 
83 	/* Memory */
84 	case OP_LOAD:
85 		USES(src); DEFINES(target);
86 		break;
87 
88 	case OP_STORE:
89 		USES(src); USES(target);
90 		break;
91 
92 	case OP_SETVAL:
93 	case OP_SETFVAL:
94 		DEFINES(target);
95 		break;
96 
97 	/* Other */
98 	case OP_PHI:
99 		/* Phi-nodes are "backwards" nodes. Their def doesn't matter */
100 		phi_defines(insn, insn->target, def);
101 		break;
102 
103 	case OP_PHISOURCE:
104 		/*
105 		 * We don't care about the phi-source define, they get set
106 		 * up and expanded by the OP_PHI
107 		 */
108 		USES(phi_src);
109 		break;
110 
111 	case OP_CALL:
112 		USES(func);
113 		if (insn->target != VOID)
114 			DEFINES(target);
115 		FOR_EACH_PTR(insn->arguments, pseudo) {
116 			use(bb, pseudo);
117 		} END_FOR_EACH_PTR(pseudo);
118 		break;
119 
120 	case OP_SLICE:
121 		USES(base); DEFINES(target);
122 		break;
123 
124 	case OP_ASM:
125 		asm_liveness(bb, insn, def, use);
126 		break;
127 
128 	case OP_RANGE:
129 		USES(src1); USES(src2); USES(src3);
130 		break;
131 
132 	case OP_BADOP:
133 	case OP_NOP:
134 	case OP_CONTEXT:
135 		break;
136 	}
137 }
138 
139 
140 static int liveness_changed;
141 
add_pseudo_exclusive(struct pseudo_list ** list,pseudo_t pseudo)142 static void add_pseudo_exclusive(struct pseudo_list **list, pseudo_t pseudo)
143 {
144 	if (!pseudo_in_list(*list, pseudo)) {
145 		liveness_changed = 1;
146 		add_pseudo(list, pseudo);
147 	}
148 }
149 
trackable_pseudo(pseudo_t pseudo)150 static inline int trackable_pseudo(pseudo_t pseudo)
151 {
152 	return pseudo && (pseudo->type == PSEUDO_REG || pseudo->type == PSEUDO_ARG);
153 }
154 
insn_uses(struct basic_block * bb,pseudo_t pseudo)155 static void insn_uses(struct basic_block *bb, pseudo_t pseudo)
156 {
157 	if (trackable_pseudo(pseudo)) {
158 		struct instruction *def = pseudo->def;
159 		if (pseudo->type != PSEUDO_REG || def->bb != bb || def->opcode == OP_PHI)
160 			add_pseudo_exclusive(&bb->needs, pseudo);
161 	}
162 }
163 
insn_defines(struct basic_block * bb,pseudo_t pseudo)164 static void insn_defines(struct basic_block *bb, pseudo_t pseudo)
165 {
166 	assert(trackable_pseudo(pseudo));
167 	add_pseudo(&bb->defines, pseudo);
168 }
169 
track_bb_liveness(struct basic_block * bb)170 static void track_bb_liveness(struct basic_block *bb)
171 {
172 	pseudo_t needs;
173 
174 	FOR_EACH_PTR(bb->needs, needs) {
175 		struct basic_block *parent;
176 		FOR_EACH_PTR(bb->parents, parent) {
177 			if (!pseudo_in_list(parent->defines, needs)) {
178 				add_pseudo_exclusive(&parent->needs, needs);
179 			}
180 		} END_FOR_EACH_PTR(parent);
181 	} END_FOR_EACH_PTR(needs);
182 }
183 
184 /*
185  * We need to clear the liveness information if we
186  * are going to re-run it.
187  */
clear_liveness(struct entrypoint * ep)188 void clear_liveness(struct entrypoint *ep)
189 {
190 	struct basic_block *bb;
191 
192 	FOR_EACH_PTR(ep->bbs, bb) {
193 		free_ptr_list(&bb->needs);
194 		free_ptr_list(&bb->defines);
195 	} END_FOR_EACH_PTR(bb);
196 }
197 
198 /*
199  * Track inter-bb pseudo liveness. The intra-bb case
200  * is purely local information.
201  */
track_pseudo_liveness(struct entrypoint * ep)202 void track_pseudo_liveness(struct entrypoint *ep)
203 {
204 	struct basic_block *bb;
205 
206 	/* Add all the bb pseudo usage */
207 	FOR_EACH_PTR(ep->bbs, bb) {
208 		struct instruction *insn;
209 		FOR_EACH_PTR(bb->insns, insn) {
210 			if (!insn->bb)
211 				continue;
212 			assert(insn->bb == bb);
213 			track_instruction_usage(bb, insn, insn_defines, insn_uses);
214 		} END_FOR_EACH_PTR(insn);
215 	} END_FOR_EACH_PTR(bb);
216 
217 	/* Calculate liveness.. */
218 	do {
219 		liveness_changed = 0;
220 		FOR_EACH_PTR_REVERSE(ep->bbs, bb) {
221 			track_bb_liveness(bb);
222 		} END_FOR_EACH_PTR_REVERSE(bb);
223 	} while (liveness_changed);
224 
225 	/* Remove the pseudos from the "defines" list that are used internally */
226 	FOR_EACH_PTR(ep->bbs, bb) {
227 		pseudo_t def;
228 		FOR_EACH_PTR(bb->defines, def) {
229 			struct basic_block *child;
230 			FOR_EACH_PTR(bb->children, child) {
231 				if (pseudo_in_list(child->needs, def))
232 					goto is_used;
233 			} END_FOR_EACH_PTR(child);
234 			DELETE_CURRENT_PTR(def);
235 is_used:
236 		;
237 		} END_FOR_EACH_PTR(def);
238 		PACK_PTR_LIST(&bb->defines);
239 	} END_FOR_EACH_PTR(bb);
240 }
241 
merge_pseudo_list(struct pseudo_list * src,struct pseudo_list ** dest)242 static void merge_pseudo_list(struct pseudo_list *src, struct pseudo_list **dest)
243 {
244 	pseudo_t pseudo;
245 	FOR_EACH_PTR(src, pseudo) {
246 		add_pseudo_exclusive(dest, pseudo);
247 	} END_FOR_EACH_PTR(pseudo);
248 }
249 
track_phi_uses(struct instruction * insn)250 static void track_phi_uses(struct instruction *insn)
251 {
252 	pseudo_t phi;
253 	FOR_EACH_PTR(insn->phi_list, phi) {
254 		struct instruction *def;
255 		if (phi == VOID || !phi->def)
256 			continue;
257 		def = phi->def;
258 		assert(def->opcode == OP_PHISOURCE);
259 		add_ptr_list(&def->phi_users, insn);
260 	} END_FOR_EACH_PTR(phi);
261 }
262 
track_bb_phi_uses(struct basic_block * bb)263 static void track_bb_phi_uses(struct basic_block *bb)
264 {
265 	struct instruction *insn;
266 	FOR_EACH_PTR(bb->insns, insn) {
267 		if (insn->bb && insn->opcode == OP_PHI)
268 			track_phi_uses(insn);
269 	} END_FOR_EACH_PTR(insn);
270 }
271 
272 static struct pseudo_list **live_list;
273 static struct pseudo_list *dead_list;
274 
death_def(struct basic_block * bb,pseudo_t pseudo)275 static void death_def(struct basic_block *bb, pseudo_t pseudo)
276 {
277 }
278 
death_use(struct basic_block * bb,pseudo_t pseudo)279 static void death_use(struct basic_block *bb, pseudo_t pseudo)
280 {
281 	if (trackable_pseudo(pseudo) && !pseudo_in_list(*live_list, pseudo)) {
282 		add_pseudo(&dead_list, pseudo);
283 		add_pseudo(live_list, pseudo);
284 	}
285 }
286 
track_pseudo_death_bb(struct basic_block * bb)287 static void track_pseudo_death_bb(struct basic_block *bb)
288 {
289 	struct pseudo_list *live = NULL;
290 	struct basic_block *child;
291 	struct instruction *insn;
292 
293 	FOR_EACH_PTR(bb->children, child) {
294 		merge_pseudo_list(child->needs, &live);
295 	} END_FOR_EACH_PTR(child);
296 
297 	live_list = &live;
298 	FOR_EACH_PTR_REVERSE(bb->insns, insn) {
299 		if (!insn->bb)
300 			continue;
301 
302 		dead_list = NULL;
303 		track_instruction_usage(bb, insn, death_def, death_use);
304 		if (dead_list) {
305 			pseudo_t dead;
306 			FOR_EACH_PTR(dead_list, dead) {
307 				struct instruction *deathnote = __alloc_instruction(0);
308 				deathnote->bb = bb;
309 				deathnote->opcode = OP_DEATHNOTE;
310 				deathnote->target = dead;
311 				INSERT_CURRENT(deathnote, insn);
312 			} END_FOR_EACH_PTR(dead);
313 			free_ptr_list(&dead_list);
314 		}
315 	} END_FOR_EACH_PTR_REVERSE(insn);
316 	free_ptr_list(&live);
317 }
318 
track_pseudo_death(struct entrypoint * ep)319 void track_pseudo_death(struct entrypoint *ep)
320 {
321 	struct basic_block *bb;
322 
323 	FOR_EACH_PTR(ep->bbs, bb) {
324 		track_bb_phi_uses(bb);
325 	} END_FOR_EACH_PTR(bb);
326 
327 	FOR_EACH_PTR(ep->bbs, bb) {
328 		track_pseudo_death_bb(bb);
329 	} END_FOR_EACH_PTR(bb);
330 }
331