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
16static 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
31static 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
46static 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
140static int liveness_changed;
141
142static 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
150static inline int trackable_pseudo(pseudo_t pseudo)
151{
152	return pseudo && (pseudo->type == PSEUDO_REG || pseudo->type == PSEUDO_ARG);
153}
154
155static 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
164static void insn_defines(struct basic_block *bb, pseudo_t pseudo)
165{
166	assert(trackable_pseudo(pseudo));
167	add_pseudo(&bb->defines, pseudo);
168}
169
170static 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 */
188void 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 */
202void 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);
235is_used:
236		;
237		} END_FOR_EACH_PTR(def);
238		PACK_PTR_LIST(&bb->defines);
239	} END_FOR_EACH_PTR(bb);
240}
241
242static 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
250static 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
263static 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
272static struct pseudo_list **live_list;
273static struct pseudo_list *dead_list;
274
275static void death_def(struct basic_block *bb, pseudo_t pseudo)
276{
277}
278
279static 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
287static 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
319void 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