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