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 <stack>
28#include <map>
29
30#include "sb_shader.h"
31#include "sb_pass.h"
32
33namespace r600_sb {
34
35container_node* ssa_prepare::create_phi_nodes(int count) {
36	container_node *p = sh.create_container();
37	val_set &vars = cur_set();
38	node *nn;
39
40	for (val_set::iterator I = vars.begin(sh), E = vars.end(sh); I != E; ++I) {
41		nn = sh.create_node(NT_OP, NST_PHI);
42		nn->dst.assign(1, *I);
43		nn->src.assign(count, *I);
44		p->push_back(nn);
45	}
46	return p;
47}
48
49void ssa_prepare::add_defs(node &n) {
50	val_set &s = cur_set();
51	for (vvec::iterator I = n.dst.begin(), E = n.dst.end(); I != E; ++I) {
52		value *v = *I;
53		if (!v)
54			continue;
55
56		if (v->is_rel()) {
57			s.add_vec(v->mdef);
58		} else
59			s.add_val(v);
60	}
61}
62
63bool ssa_prepare::visit(cf_node& n, bool enter) {
64	if (enter) {
65		push_stk();
66	} else {
67		add_defs(n);
68		pop_stk();
69	}
70	return true;
71}
72
73bool ssa_prepare::visit(alu_node& n, bool enter) {
74	if (enter) {
75	} else {
76		add_defs(n);
77	}
78	return true;
79}
80
81bool ssa_prepare::visit(fetch_node& n, bool enter) {
82	if (enter) {
83	} else {
84		add_defs(n);
85	}
86	return true;
87}
88
89bool ssa_prepare::visit(region_node& n, bool enter) {
90	if (enter) {
91
92		push_stk();
93	} else {
94		cur_set().add_set(n.vars_defined);
95		if (n.dep_count() > 0)
96			n.phi = create_phi_nodes(n.dep_count());
97		if (n.rep_count() > 1) {
98			n.loop_phi = create_phi_nodes(n.rep_count());
99			n.loop_phi->subtype = NST_LOOP_PHI_CONTAINER;
100		}
101		n.vars_defined.clear();
102		pop_stk();
103	}
104	return true;
105}
106
107bool ssa_prepare::visit(repeat_node& n, bool enter) {
108	if (enter) {
109		push_stk();
110	} else {
111		assert(n.target);
112		n.target->vars_defined.add_set(cur_set());
113		cur_set().clear();
114		pop_stk();
115	}
116	return true;
117}
118
119bool ssa_prepare::visit(depart_node& n, bool enter) {
120	if (enter) {
121		push_stk();
122	} else {
123		assert(n.target);
124		n.target->vars_defined.add_set(cur_set());
125		cur_set().clear();
126		pop_stk();
127	}
128	return true;
129}
130
131// ===============================
132
133int ssa_rename::init() {
134	rename_stack.push(def_map());
135	rename_lds_oq_stack.push(def_map());
136	rename_lds_rw_stack.push(def_map());
137	return 0;
138}
139
140bool ssa_rename::visit(alu_group_node& n, bool enter) {
141	// taking into account parallel execution of the alu group
142	if (enter) {
143		for (node_iterator I = n.begin(), E = n.end(); I != E; ++I) {
144			I->accept(*this, true);
145		}
146	} else {
147		for (node_iterator I = n.begin(), E = n.end(); I != E; ++I) {
148			I->accept(*this, false);
149		}
150	}
151	return false;
152}
153
154bool ssa_rename::visit(cf_node& n, bool enter) {
155	if (enter) {
156		rename_src(&n);
157	} else {
158		rename_dst(&n);
159	}
160	return true;
161}
162
163bool ssa_rename::visit(alu_node& n, bool enter) {
164	if (enter) {
165		rename_src(&n);
166	} else {
167
168		node *psi = NULL;
169
170		if (n.pred && n.dst[0]) {
171
172			value *d = n.dst[0];
173			unsigned index = get_index(rename_stack.top(), d);
174			value *p = sh.get_value_version(d, index);
175
176			psi = sh.create_node(NT_OP, NST_PSI);
177
178			container_node *parent;
179			if (n.parent->subtype == NST_ALU_GROUP)
180				parent = n.parent;
181			else {
182				assert (n.parent->parent->subtype == NST_ALU_GROUP);
183				parent = n.parent->parent;
184			}
185			parent->insert_after(psi);
186
187			assert(n.bc.pred_sel);
188
189			psi->src.resize(6);
190			psi->src[2] = p;
191			psi->src[3] = n.pred;
192			psi->src[4] = sh.get_pred_sel(n.bc.pred_sel - PRED_SEL_0);
193			psi->src[5] = d;
194			psi->dst.push_back(d);
195		}
196
197		rename_dst(&n);
198
199		if (psi) {
200			rename_src(psi);
201			rename_dst(psi);
202		}
203
204		if (!n.dst.empty() && n.dst[0]) {
205			// FIXME probably use separate pass for such things
206			if ((n.bc.op_ptr->flags & AF_INTERP) || n.bc.op == ALU_OP2_CUBE)
207				n.dst[0]->flags |= VLF_PIN_CHAN;
208		}
209	}
210	return true;
211}
212
213bool ssa_rename::visit(alu_packed_node& n, bool enter) {
214	if (enter) {
215		for (node_iterator I = n.begin(), E = n.end(); I != E; ++I) {
216			I->accept(*this, true);
217		}
218	} else {
219		for (node_iterator I = n.begin(), E = n.end(); I != E; ++I) {
220			I->accept(*this, false);
221		}
222
223		bool repl = (n.op_ptr()->flags & AF_REPL) ||
224				(ctx.is_cayman() && (n.first->alu_op_slot_flags() & AF_S));
225
226		n.init_args(repl);
227	}
228	return false;
229}
230
231bool ssa_rename::visit(fetch_node& n, bool enter) {
232	if (enter) {
233		rename_src(&n);
234		rename_dst(&n);
235	} else {
236	}
237	return true;
238}
239
240bool ssa_rename::visit(region_node& n, bool enter) {
241	if (enter) {
242		if (n.loop_phi)
243			rename_phi_args(n.loop_phi, 0, true);
244	} else {
245		if (n.phi)
246			rename_phi_args(n.phi, ~0u, true);
247	}
248	return true;
249}
250
251bool ssa_rename::visit(repeat_node& n, bool enter) {
252	if (enter) {
253		push(n.target->loop_phi);
254	} else {
255		if (n.target->loop_phi)
256			rename_phi_args(n.target->loop_phi, n.rep_id, false);
257		pop();
258	}
259	return true;
260}
261
262bool ssa_rename::visit(depart_node& n, bool enter) {
263	if (enter) {
264		push(n.target->phi);
265	} else {
266		if (n.target->phi)
267			rename_phi_args(n.target->phi, n.dep_id, false);
268		pop();
269	}
270	return true;
271}
272
273bool ssa_rename::visit(if_node& n, bool enter) {
274	if (enter) {
275	} else {
276		n.cond = rename_use(&n, n.cond);
277	}
278	return true;
279}
280
281void ssa_rename::push(node* phi) {
282	rename_stack.push(rename_stack.top());
283}
284
285void ssa_rename::pop() {
286	rename_stack.pop();
287}
288
289value* ssa_rename::rename_use(node *n, value* v) {
290	if (v->version)
291		return v;
292	unsigned index;
293	if (v->is_lds_access()) {
294		index = get_index(rename_lds_rw_stack.top(), v);
295	} else if (v->is_lds_oq()) {
296		index = new_index(lds_oq_count, v);
297		set_index(rename_lds_oq_stack.top(), v, index);
298	} else {
299		index = get_index(rename_stack.top(), v);
300	}
301
302	v = sh.get_value_version(v, index);
303
304	// if (alu) instruction is predicated and source arg comes from psi node
305	// (that is, from another predicated instruction through its psi node),
306	// we can try to select the corresponding source value directly
307	if (n->pred && v->def && v->def->subtype == NST_PSI) {
308		assert(n->subtype == NST_ALU_INST);
309		alu_node *an = static_cast<alu_node*>(n);
310		node *pn = v->def;
311		// FIXME make it more generic ???
312		if (pn->src.size() == 6) {
313			if (pn->src[3] == n->pred) {
314				value* ps = sh.get_pred_sel(an->bc.pred_sel - PRED_SEL_0);
315				if (pn->src[4] == ps)
316					return pn->src[5];
317				else
318					return pn->src[2];
319			}
320		}
321	}
322	return v;
323}
324
325value* ssa_rename::rename_def(node *n, value* v) {
326	unsigned index;
327
328	if (v->is_lds_access()) {
329		index = new_index(lds_rw_count, v);
330		set_index(rename_lds_rw_stack.top(), v, index);
331	} else {
332		index = new_index(def_count, v);
333		set_index(rename_stack.top(), v, index);
334	}
335	value *r = sh.get_value_version(v, index);
336	return r;
337}
338
339void ssa_rename::rename_src_vec(node *n, vvec &vv, bool src) {
340	for(vvec::iterator I = vv.begin(), E = vv.end(); I != E; ++I) {
341		value* &v = *I;
342		if (!v || v->is_readonly())
343			continue;
344
345		if (v->is_rel()) {
346			if (!v->rel->is_readonly())
347				v->rel = rename_use(n, v->rel);
348			rename_src_vec(n, v->muse, true);
349		} else if (src)
350			v = rename_use(n, v);
351	}
352}
353
354void ssa_rename::rename_src(node* n) {
355	if (n->pred)
356		n->pred = rename_use(n, n->pred);
357
358	rename_src_vec(n, n->src, true);
359	rename_src_vec(n, n->dst, false);
360
361}
362
363void ssa_rename::rename_dst_vec(node *n, vvec &vv, bool set_def) {
364
365	for(vvec::iterator I = vv.begin(), E = vv.end(); I != E; ++I) {
366		value* &v = *I;
367		if (!v)
368			continue;
369
370		if (v->is_rel()) {
371			rename_dst_vec(n, v->mdef, false);
372		} else {
373			v = rename_def(n, v);
374			if (set_def)
375				v->def = n;
376		}
377	}
378}
379
380void ssa_rename::rename_dst(node* n) {
381	rename_dst_vec(n, n->dst, true);
382}
383
384unsigned ssa_rename::get_index(def_map& m, value* v) {
385	def_map::iterator I = m.find(v);
386	if (I != m.end())
387		return I->second;
388	return 0;
389}
390
391void ssa_rename::set_index(def_map& m, value* v, unsigned index) {
392	std::pair<def_map::iterator,bool>  r = m.insert(std::make_pair(v, index));
393	if (!r.second)
394		r.first->second = index;
395}
396
397unsigned ssa_rename::new_index(def_map& m, value* v) {
398	unsigned index = 1;
399	def_map::iterator I = m.find(v);
400	if (I != m.end())
401		index = ++I->second;
402	else
403		m.insert(std::make_pair(v, index));
404	return index;
405}
406
407bool ssa_rename::visit(node& n, bool enter) {
408	if (enter) {
409		assert(n.subtype == NST_PSI);
410		rename_src(&n);
411		rename_dst(&n);
412	}
413	return false;
414}
415
416bool ssa_rename::visit(container_node& n, bool enter) {
417	if (enter) {
418	} else {
419		// should be root container node
420		assert(n.parent == NULL);
421		rename_src_vec(&n, n.src, true);
422	}
423	return true;
424}
425
426void ssa_rename::rename_phi_args(container_node* phi, unsigned op, bool def) {
427	for (node_iterator I = phi->begin(), E = phi->end(); I != E; ++I) {
428		node *o = *I;
429		if (op != ~0u)
430			o->src[op] = rename_use(o, o->src[op]);
431		if (def) {
432			o->dst[0] = rename_def(o, o->dst[0]);
433			o->dst[0]->def = o;
434		}
435	}
436}
437
438} // namespace r600_sb
439