1/*
2 * Copyright 2013 Vadim Girlin <vadimgirlin@gmail.com>
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining a
5 * copy of this software and associated documentation files (the "Software"),
6 * to deal in the Software without restriction, including without limitation
7 * on the rights to use, copy, modify, merge, publish, distribute, sub
8 * license, and/or sell copies of the Software, and to permit persons to whom
9 * the Software is furnished to do so, subject to the following conditions:
10 *
11 * The above copyright notice and this permission notice (including the next
12 * paragraph) shall be included in all copies or substantial portions of the
13 * Software.
14 *
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL
18 * THE AUTHOR(S) AND/OR THEIR SUPPLIERS BE LIABLE FOR ANY CLAIM,
19 * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
20 * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE
21 * USE OR OTHER DEALINGS IN THE SOFTWARE.
22 *
23 * Authors:
24 *      Vadim Girlin
25 */
26
27#include "sb_shader.h"
28#include "sb_pass.h"
29
30#define LIV_DEBUG 0
31
32#if LIV_DEBUG
33#define LIV_DUMP(a) do { a } while (0)
34#else
35#define LIV_DUMP(a)
36#endif
37
38namespace r600_sb {
39
40bool liveness::visit(container_node& n, bool enter) {
41	if (enter) {
42		n.live_after = live;
43		process_ins(n);
44	} else {
45		process_outs(n);
46		n.live_before = live;
47	}
48	return true;
49}
50
51bool liveness::visit(bb_node& n, bool enter) {
52	if (enter) {
53		n.live_after = live;
54	} else {
55		n.live_before = live;
56	}
57	return true;
58}
59
60bool liveness::visit(alu_group_node& n, bool enter) {
61	if (enter) {
62	} else {
63	}
64	return true;
65}
66
67bool liveness::visit(cf_node& n, bool enter) {
68	if (enter) {
69		if (n.bc.op == CF_OP_CF_END) {
70			n.flags |= NF_DEAD;
71			return false;
72		}
73		n.live_after = live;
74		update_interferences();
75		process_op(n);
76	} else {
77		n.live_before = live;
78	}
79	return true;
80}
81
82bool liveness::visit(alu_node& n, bool enter) {
83	if (enter) {
84		update_interferences();
85		process_op(n);
86	} else {
87	}
88	return false;
89}
90
91bool liveness::visit(alu_packed_node& n, bool enter) {
92	if (enter) {
93		update_interferences();
94		process_op(n);
95
96	} else {
97	}
98	return false;
99}
100
101bool liveness::visit(fetch_node& n, bool enter) {
102	if (enter) {
103		update_interferences();
104		process_op(n);
105	} else {
106	}
107	return true;
108}
109
110bool liveness::visit(region_node& n, bool enter) {
111	if (enter) {
112		val_set s = live;
113
114		update_interferences();
115
116		if (n.phi)
117			process_phi_outs(n.phi);
118
119		n.live_after = live;
120
121		live.clear();
122
123		if (n.loop_phi) {
124			n.live_before.clear();
125		}
126
127		assert(n.count() == 1);
128		run_on(*static_cast<container_node*>(*n.begin()));
129
130		// second pass for loops
131		if (n.loop_phi) {
132			process_phi_outs(n.loop_phi);
133			n.live_before = live;
134
135			run_on(*static_cast<container_node*>(*n.begin()));
136
137			update_interferences(); // FIXME is it required
138
139			process_phi_outs(n.loop_phi);
140			process_phi_branch(n.loop_phi, 0);
141		}
142
143		update_interferences(); // FIXME is it required
144
145		n.live_after = s;
146		n.live_before = live;
147	}
148	return false;
149}
150
151bool liveness::visit(repeat_node& n, bool enter) {
152	if (enter) {
153		live = n.target->live_before;
154		process_phi_branch(n.target->loop_phi, n.rep_id);
155	} else {
156	}
157	return true;
158}
159
160bool liveness::visit(depart_node& n, bool enter) {
161	if (enter) {
162		live = n.target->live_after;
163		if(n.target->phi)
164			process_phi_branch(n.target->phi, n.dep_id);
165	} else {
166	}
167	return true;
168}
169
170bool liveness::visit(if_node& n, bool enter) {
171	if (enter) {
172		assert(n.count() == 1);
173		n.live_after = live;
174
175		run_on(*static_cast<container_node*>(*n.begin()));
176
177		process_op(n);
178		live.add_set(n.live_after);
179	}
180	return false;
181}
182
183void liveness::update_interferences() {
184	if (!sh.compute_interferences)
185		return;
186
187	if (!live_changed)
188		return;
189
190	LIV_DUMP(
191		sblog << "interf ";
192		dump::dump_set(sh, live);
193		sblog << "\n";
194	);
195
196	val_set& s = live;
197	for(val_set::iterator I = s.begin(sh), E = s.end(sh); I != E; ++I) {
198		value *v = *I;
199		assert(v);
200
201		if (v->array) {
202			v->array->interferences.add_set(s);
203		}
204
205		v->interferences.add_set(s);
206		v->interferences.remove_val(v);
207
208		LIV_DUMP(
209			sblog << "interferences updated for ";
210			dump::dump_val(v);
211			sblog << " : ";
212			dump::dump_set(sh, v->interferences);
213			sblog << "\n";
214		);
215	}
216	live_changed = false;
217}
218
219bool liveness::remove_val(value *v) {
220	if (live.remove_val(v)) {
221		v->flags &= ~VLF_DEAD;
222		return true;
223	}
224	v->flags |= VLF_DEAD;
225	return false;
226}
227
228bool liveness::process_maydef(value *v) {
229	bool r = false;
230	vvec::iterator S(v->muse.begin());
231
232	for (vvec::iterator I = v->mdef.begin(), E = v->mdef.end(); I != E;
233			++I, ++S) {
234		value *&d = *I, *&u = *S;
235		if (!d) {
236			assert(!u);
237			continue;
238		}
239
240		bool alive = remove_val(d);
241		if (alive) {
242			r = true;
243		} else {
244			d = NULL;
245			u = NULL;
246		}
247	}
248	return r;
249}
250
251bool liveness::remove_vec(vvec &vv) {
252	bool r = false;
253	for (vvec::reverse_iterator I = vv.rbegin(), E = vv.rend(); I != E; ++I) {
254		value* &v = *I;
255		if (!v)
256			continue;
257
258		if (v->is_rel()) {
259			r |= process_maydef(v);
260		} else
261			r |= remove_val(v);
262	}
263	return r;
264}
265
266bool r600_sb::liveness::visit(node& n, bool enter) {
267	if (enter) {
268		update_interferences();
269		process_op(n);
270	}
271	return false;
272}
273
274bool liveness::process_outs(node& n) {
275	bool alive = remove_vec(n.dst);
276	if (alive)
277		live_changed = true;
278	return alive;
279}
280
281bool liveness::add_vec(vvec &vv, bool src) {
282	bool r = false;
283	for (vvec::iterator I = vv.begin(), E = vv.end(); I != E; ++I) {
284		value *v = *I;
285		if (!v || v->is_readonly())
286			continue;
287
288		if (v->is_rel()) {
289			r |= add_vec(v->muse, true);
290			if (v->rel->is_any_reg())
291				r |= live.add_val(v->rel);
292
293		} else if (src) {
294			r |= live.add_val(v);
295		}
296	}
297
298	return r;
299}
300
301void liveness::process_ins(node& n) {
302	if (!(n.flags & NF_DEAD)) {
303
304		live_changed |= add_vec(n.src, true);
305		live_changed |= add_vec(n.dst, false);
306
307		if (n.type == NT_IF) {
308			if_node &in = (if_node&)n;
309			if (in.cond)
310				live_changed |= live.add_val(in.cond);
311		}
312		if (n.pred)
313			live_changed |= live.add_val(n.pred);
314	}
315}
316
317void liveness::process_op(node& n) {
318
319	LIV_DUMP(
320		sblog << "process_op: ";
321		dump::dump_op(&n);
322		sblog << "\n";
323		sblog << "process_op: live_after:";
324		dump::dump_set(sh, live);
325		sblog << "\n";
326	);
327
328	if(!n.dst.empty() || n.is_cf_op(CF_OP_CALL_FS)) {
329		if (!process_outs(n)) {
330			if (!(n.flags & NF_DONT_KILL))
331				n.flags |= NF_DEAD;
332		} else {
333			n.flags &= ~NF_DEAD;
334		}
335	}
336	process_ins(n);
337
338	LIV_DUMP(
339		sblog << "process_op: live_before:";
340		dump::dump_set(sh, live);
341		sblog << "\n";
342	);
343}
344
345int liveness::init() {
346
347	if (sh.compute_interferences) {
348		gpr_array_vec &vv = sh.arrays();
349		for (gpr_array_vec::iterator I = vv.begin(), E = vv.end(); I != E;
350				++I) {
351			gpr_array *a = *I;
352			a->interferences.clear();
353		}
354	}
355
356	return 0;
357}
358
359void liveness::update_src_vec(vvec &vv, bool src) {
360	for (vvec::iterator I = vv.begin(), E = vv.end(); I != E; ++I) {
361		value *v = *I;
362
363		if (!v || !v->is_sgpr())
364			continue;
365
366		if (v->rel && v->rel->is_dead())
367			v->rel->flags &= ~VLF_DEAD;
368
369		if (src && v->is_dead()) {
370			v->flags &= ~VLF_DEAD;
371		}
372	}
373}
374
375void liveness::process_phi_outs(container_node *phi) {
376	for (node_iterator I = phi->begin(), E = phi->end(); I != E; ++I) {
377		node *n = *I;
378		if (!process_outs(*n)) {
379			n->flags |= NF_DEAD;
380		} else {
381			n->flags &= ~NF_DEAD;
382			update_src_vec(n->src, true);
383			update_src_vec(n->dst, false);
384		}
385	}
386}
387
388void liveness::process_phi_branch(container_node* phi, unsigned id) {
389	val_set &s = live;
390	for (node_iterator I = phi->begin(), E = phi->end(); I != E; ++I) {
391		node *n = *I;
392		if (n->is_dead())
393			continue;
394
395		value *v = n->src[id];
396
397		if (!v->is_readonly()) {
398			live_changed |= s.add_val(v);
399			v->flags &= ~VLF_DEAD;
400		}
401	}
402}
403
404} //namespace r600_sb
405