src/gallium/drivers/r600/sb/sb_liveness.cpp

   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
  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
  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
  60 bool liveness::visit(alu_group_node& n, bool enter) {
  61         if (enter) {
  62         } else {
  63         }
  64         return true;
  65 }
  66
  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
  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
  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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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