• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
38 namespace r600_sb {
39 
visit(container_node & n,bool enter)40 bool 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 
visit(bb_node & n,bool enter)51 bool 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 
visit(alu_group_node & n,bool enter)60 bool liveness::visit(alu_group_node& n, bool enter) {
61 	if (enter) {
62 	} else {
63 	}
64 	return true;
65 }
66 
visit(cf_node & n,bool enter)67 bool 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 
visit(alu_node & n,bool enter)82 bool 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 
visit(alu_packed_node & n,bool enter)91 bool 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 
visit(fetch_node & n,bool enter)101 bool 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 
visit(region_node & n,bool enter)110 bool 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 
visit(repeat_node & n,bool enter)151 bool 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 
visit(depart_node & n,bool enter)160 bool 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 
visit(if_node & n,bool enter)170 bool 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 
update_interferences()183 void 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 
remove_val(value * v)219 bool 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 
process_maydef(value * v)228 bool 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 
remove_vec(vvec & vv)251 bool 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 
visit(node & n,bool enter)266 bool r600_sb::liveness::visit(node& n, bool enter) {
267 	if (enter) {
268 		update_interferences();
269 		process_op(n);
270 	}
271 	return false;
272 }
273 
process_outs(node & n)274 bool liveness::process_outs(node& n) {
275 	bool alive = remove_vec(n.dst);
276 	if (alive)
277 		live_changed = true;
278 	return alive;
279 }
280 
add_vec(vvec & vv,bool src)281 bool 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 
process_ins(node & n)301 void 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 
process_op(node & n)317 void 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 
init()345 int 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 
update_src_vec(vvec & vv,bool src)359 void 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 
process_phi_outs(container_node * phi)375 void 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 
process_phi_branch(container_node * phi,unsigned id)388 void 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