src/gallium/drivers/r600/sb/sb_ir.h

   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 #ifndef R600_SB_IR_H_
  28 #define R600_SB_IR_H_
  29
  30 #include <algorithm>
  31 #include <stdint.h>
  32 #include <vector>
  33 #include <set>
  34 #include <algorithm>
  35
  36 #include "sb_bc.h"
  37
  38 namespace r600_sb {
  39
  40 enum special_regs {
  41         SV_ALU_PRED = 128,
  42         SV_EXEC_MASK,
  43         SV_AR_INDEX,
  44         SV_VALID_MASK,
  45         SV_GEOMETRY_EMIT
  46 };
  47
  48 class node;
  49 class value;
  50 class shader;
  51
  52 struct sel_chan
  53 {
  54         unsigned id;
  55
  56         sel_chan(unsigned id = 0) : id(id) {}
  57         sel_chan(unsigned sel, unsigned chan) : id(((sel << 2) | chan) + 1) {}
  58
  59         unsigned sel() const { return sel(id); }
  60         unsigned chan() const {return chan(id); }
  61         operator unsigned() const {return id;}
  62
  63         static unsigned sel(unsigned idx) { return (idx-1) >> 2; }
  64         static unsigned chan(unsigned idx) { return (idx-1) & 3; }
  65 };
  66
  67 inline sb_ostream& operator <<(sb_ostream& o, sel_chan r) {
  68         static const char * ch = "xyzw";
  69         o << r.sel() << "." << ch[r.chan()];
  70         return o;
  71 }
  72
  73 typedef std::vector<value*>  vvec;
  74
  75 class sb_pool {
  76 protected:
  77         static const unsigned SB_POOL_ALIGN = 8;
  78         static const unsigned SB_POOL_DEFAULT_BLOCK_SIZE = (1 << 16);
  79
  80         typedef std::vector<void*> block_vector;
  81
  82         unsigned block_size;
  83         block_vector blocks;
  84         unsigned total_size;
  85
  86 public:
  87         sb_pool(unsigned block_size = SB_POOL_DEFAULT_BLOCK_SIZE)
  88                 : block_size(block_size), blocks(), total_size() {}
  89
  90         virtual ~sb_pool() { free_all(); }
  91
  92         void* allocate(unsigned sz);
  93
  94 protected:
  95         void free_all();
  96 };
  97
  98 template <typename V, typename Comp = std::less<V> >
  99 class sb_set {
 100         typedef std::vector<V> data_vector;
 101         data_vector vec;
 102 public:
 103
 104         typedef typename data_vector::iterator iterator;
 105         typedef typename data_vector::const_iterator const_iterator;
 106
 107         sb_set() : vec() {}
 108         ~sb_set() {  }
 109
 110         iterator begin() { return vec.begin(); }
 111         iterator end() { return vec.end(); }
 112         const_iterator begin() const { return vec.begin(); }
 113         const_iterator end() const { return vec.end(); }
 114
 115         void add_set(const sb_set& s) {
 116                 data_vector t;
 117                 t.reserve(vec.size() + s.vec.size());
 118                 std::set_union(vec.begin(), vec.end(), s.vec.begin(), s.vec.end(),
 119                           std::inserter(t, t.begin()), Comp());
 120                 vec.swap(t);
 121         }
 122
 123         iterator lower_bound(const V& v) {
 124                 return std::lower_bound(vec.begin(), vec.end(), v, Comp());
 125         }
 126
 127         std::pair<iterator, bool> insert(const V& v) {
 128                 iterator P = lower_bound(v);
 129                 if (P != vec.end() && is_equal(*P, v))
 130                         return std::make_pair(P, false);
 131                 return std::make_pair(vec.insert(P, v), true);
 132         }
 133
 134         unsigned erase(const V&  v) {
 135                 iterator P = lower_bound(v);
 136                 if (P == vec.end() || !is_equal(*P, v))
 137                         return 0;
 138                 vec.erase(P);
 139                 return 1;
 140         }
 141
 142         void clear() { vec.clear(); }
 143
 144         bool empty() { return vec.empty(); }
 145
 146         bool is_equal(const V& v1, const V& v2) {
 147                 return !Comp()(v1, v2) && !Comp()(v2, v1);
 148         }
 149
 150         iterator find(const V& v) {
 151                 iterator P = lower_bound(v);
 152                 return (P != vec.end() && is_equal(*P, v)) ? P : vec.end();
 153         }
 154
 155         unsigned size() { return vec.size(); }
 156         void erase(iterator I) { vec.erase(I); }
 157 };
 158
 159 template <typename K, typename V, typename KComp = std::less<K> >
 160 class sb_map {
 161         typedef std::pair<K, V> datatype;
 162
 163         struct Comp {
 164                 bool operator()(const datatype &v1, const datatype &v2) {
 165                         return KComp()(v1.first, v2.first);
 166                 }
 167         };
 168
 169         typedef sb_set<datatype, Comp> dataset;
 170
 171         dataset set;
 172
 173 public:
 174
 175         sb_map() : set() {}
 176
 177         typedef typename dataset::iterator iterator;
 178
 179         iterator begin() { return set.begin(); }
 180         iterator end() { return set.end(); }
 181
 182         void clear() { set.clear(); }
 183
 184         V& operator[](const K& key) {
 185                 datatype P = std::make_pair(key, V());
 186                 iterator F = set.find(P);
 187                 if (F == set.end()) {
 188                         return (*(set.insert(P).first)).second;
 189                 } else {
 190                         return (*F).second;
 191                 }
 192         }
 193
 194         std::pair<iterator, bool> insert(const datatype& d) {
 195                 return set.insert(d);
 196         }
 197
 198         iterator find(const K& key) {
 199                 return set.find(std::make_pair(key, V()));
 200         }
 201
 202         unsigned erase(const K& key) {
 203                 return set.erase(std::make_pair(key, V()));
 204         }
 205
 206         void erase(iterator I) {
 207                 set.erase(I);
 208         }
 209 };
 210
 211 class sb_bitset {
 212         typedef uint32_t basetype;
 213         static const unsigned bt_bits = sizeof(basetype) << 3;
 214         std::vector<basetype> data;
 215         unsigned bit_size;
 216
 217 public:
 218
 219         sb_bitset() : data(), bit_size() {}
 220
 221         bool get(unsigned id);
 222         void set(unsigned id, bool bit = true);
 223         bool set_chk(unsigned id, bool bit = true);
 224
 225         void clear();
 226         void resize(unsigned size);
 227
 228         unsigned size() { return bit_size; }
 229
 230         unsigned find_bit(unsigned start = 0);
 231
 232         void swap(sb_bitset & bs2);
 233
 234         bool operator==(const sb_bitset &bs2);
 235         bool operator!=(const sb_bitset &bs2) { return !(*this == bs2); }
 236
 237         sb_bitset& operator|=(const sb_bitset &bs2) {
 238                 if (bit_size < bs2.bit_size) {
 239                         resize(bs2.bit_size);
 240                 }
 241
 242                 for (unsigned i = 0, c = std::min(data.size(), bs2.data.size()); i < c;
 243                                 ++i) {
 244                         data[i] |= bs2.data[i];
 245                 }
 246                 return *this;
 247         }
 248
 249         sb_bitset& operator&=(const sb_bitset &bs2);
 250         sb_bitset& mask(const sb_bitset &bs2);
 251
 252         friend sb_bitset operator|(const sb_bitset &b1, const sb_bitset &b2) {
 253                         sb_bitset nbs(b1);
 254                         nbs |= b2;
 255                         return nbs;
 256         }
 257 };
 258
 259 class value;
 260
 261 enum value_kind {
 262         VLK_REG,
 263         VLK_REL_REG,
 264         VLK_SPECIAL_REG,
 265         VLK_TEMP,
 266
 267         VLK_CONST,
 268         VLK_KCACHE,
 269         VLK_PARAM,
 270         VLK_SPECIAL_CONST,
 271
 272         VLK_UNDEF
 273 };
 274
 275
 276
 277 class sb_value_pool : protected sb_pool {
 278         unsigned aligned_elt_size;
 279
 280 public:
 281         sb_value_pool(unsigned elt_size, unsigned block_elts = 256)
 282                 : sb_pool(block_elts * (aligned_elt_size = ((elt_size +
 283                                 SB_POOL_ALIGN - 1) & ~(SB_POOL_ALIGN - 1)))) {}
 284
 285         virtual ~sb_value_pool() { delete_all(); }
 286
 287         value* create(value_kind k, sel_chan regid, unsigned ver);
 288
 289         value* operator[](unsigned id) {
 290                 unsigned offset = id * aligned_elt_size;
 291                 unsigned block_id;
 292                 if (offset < block_size) {
 293                         block_id = 0;
 294                 } else {
 295                         block_id = offset / block_size;
 296                         offset = offset % block_size;
 297                 }
 298                 return (value*)((char*)blocks[block_id] + offset);
 299         }
 300
 301         unsigned size() { return total_size / aligned_elt_size; }
 302
 303 protected:
 304         void delete_all();
 305 };
 306
 307
 308
 309
 310
 311 class sb_value_set {
 312
 313         sb_bitset bs;
 314
 315 public:
 316         sb_value_set() : bs() {}
 317
 318         class iterator {
 319                 sb_value_pool &vp;
 320                 sb_value_set *s;
 321                 unsigned nb;
 322         public:
 323                 iterator(shader &sh, sb_value_set *s, unsigned nb = 0);
 324
 325
 326                 iterator& operator++() {
 327                         if (nb + 1 < s->bs.size())
 328                                 nb = s->bs.find_bit(nb + 1);
 329                         else
 330                                 nb = s->bs.size();
 331                         return *this;
 332                 }
 333                 bool operator !=(const iterator &i) {
 334                         return s != i.s || nb != i.nb;
 335                 }
 336                 bool operator ==(const iterator &i) { return !(*this != i); }
 337                 value* operator *() {
 338                          return vp[nb];
 339                 }
 340
 341
 342         };
 343
 344         iterator begin(shader &sh) {
 345                 return iterator(sh, this, bs.size() ? bs.find_bit(0) : 0);
 346         }
 347         iterator end(shader &sh) { return iterator(sh, this, bs.size()); }
 348
 349         bool add_set_checked(sb_value_set & s2);
 350
 351         void add_set(sb_value_set & s2)  {
 352                 if (bs.size() < s2.bs.size())
 353                         bs.resize(s2.bs.size());
 354                 bs |= s2.bs;
 355         }
 356
 357         void remove_set(sb_value_set & s2);
 358
 359         bool add_vec(vvec &vv);
 360
 361         bool add_val(value *v);
 362         bool contains(value *v);
 363
 364         bool remove_val(value *v);
 365
 366         bool remove_vec(vvec &vv);
 367
 368         void clear();
 369
 370         bool empty();
 371 };
 372
 373 typedef sb_value_set val_set;
 374
 375 struct gpr_array {
 376         sel_chan base_gpr; // original gpr
 377         sel_chan gpr; // assigned by regalloc
 378         unsigned array_size;
 379
 380         gpr_array(sel_chan base_gpr, unsigned array_size) : base_gpr(base_gpr),
 381                         array_size(array_size) {}
 382
 383         unsigned hash() { return (base_gpr << 10) * array_size; }
 384
 385         val_set interferences;
 386         vvec refs;
 387
 388         bool is_dead();
 389
 390 };
 391
 392 typedef std::vector<gpr_array*> regarray_vec;
 393
 394 enum value_flags {
 395         VLF_UNDEF = (1 << 0),
 396         VLF_READONLY = (1 << 1),
 397         VLF_DEAD = (1 << 2),
 398
 399         VLF_PIN_REG = (1 << 3),
 400         VLF_PIN_CHAN = (1 << 4),
 401
 402         // opposite to alu clause local value - goes through alu clause boundary
 403         // (can't use temp gpr, can't recolor in the alu scheduler, etc)
 404         VLF_GLOBAL = (1 << 5),
 405         VLF_FIXED = (1 << 6),
 406         VLF_PVPS = (1 << 7),
 407
 408         VLF_PREALLOC = (1 << 8)
 409 };
 410
 411 inline value_flags operator |(value_flags l, value_flags r) {
 412         return (value_flags)((unsigned)l|(unsigned)r);
 413 }
 414 inline value_flags operator &(value_flags l, value_flags r) {
 415         return (value_flags)((unsigned)l&(unsigned)r);
 416 }
 417 inline value_flags operator ~(value_flags l) {
 418         return (value_flags)(~(unsigned)l);
 419 }
 420 inline value_flags& operator |=(value_flags &l, value_flags r) {
 421         l = l | r;
 422         return l;
 423 }
 424 inline value_flags& operator &=(value_flags &l, value_flags r) {
 425         l = l & r;
 426         return l;
 427 }
 428
 429 struct value;
 430
 431 sb_ostream& operator << (sb_ostream &o, value &v);
 432
 433 typedef uint32_t value_hash;
 434
 435 enum use_kind {
 436         UK_SRC,
 437         UK_SRC_REL,
 438         UK_DST_REL,
 439         UK_MAYDEF,
 440         UK_MAYUSE,
 441         UK_PRED,
 442         UK_COND
 443 };
 444
 445 struct use_info {
 446         use_info *next;
 447         node *op;
 448         use_kind kind;
 449         int arg;
 450
 451         use_info(node *n, use_kind kind, int arg, use_info* next)
 452                 : next(next), op(n), kind(kind), arg(arg) {}
 453 };
 454
 455 enum constraint_kind {
 456         CK_SAME_REG,
 457         CK_PACKED_BS,
 458         CK_PHI
 459 };
 460
 461 class shader;
 462 class sb_value_pool;
 463 class ra_chunk;
 464 class ra_constraint;
 465
 466 class value {
 467 protected:
 468         value(unsigned sh_id, value_kind k, sel_chan select, unsigned ver = 0)
 469                 : kind(k), flags(),
 470                         rel(), array(),
 471                         version(ver), select(select), pin_gpr(select), gpr(),
 472                         gvn_source(), ghash(),
 473                         def(), adef(), uses(), constraint(), chunk(),
 474                         literal_value(), uid(sh_id) {}
 475
 476         ~value() { delete_uses(); }
 477
 478         friend class sb_value_pool;
 479 public:
 480         value_kind kind;
 481         value_flags flags;
 482
 483         vvec mdef;
 484         vvec muse;
 485         value *rel;
 486         gpr_array *array;
 487
 488         unsigned version;
 489
 490         sel_chan select;
 491         sel_chan pin_gpr;
 492         sel_chan gpr;
 493
 494         value *gvn_source;
 495         value_hash ghash;
 496
 497         node *def, *adef;
 498         use_info *uses;
 499
 500         ra_constraint *constraint;
 501         ra_chunk *chunk;
 502
 503         literal literal_value;
 504
 505         bool is_const() { return kind == VLK_CONST || kind == VLK_UNDEF; }
 506
 507         bool is_AR() {
 508                 return is_special_reg() && select == sel_chan(SV_AR_INDEX, 0);
 509         }
 510         bool is_geometry_emit() {
 511                 return is_special_reg() && select == sel_chan(SV_GEOMETRY_EMIT, 0);
 512         }
 513
 514         node* any_def() {
 515                 assert(!(def && adef));
 516                 return def ? def : adef;
 517         }
 518
 519         value* gvalue() {
 520                 value *v = this;
 521                 while (v->gvn_source && v != v->gvn_source)
 522                         // FIXME we really shouldn't have such chains
 523                         v = v->gvn_source;
 524                 return v;
 525         }
 526
 527         bool is_float_0_or_1() {
 528                 value *v = gvalue();
 529                 return v->is_const() && (v->literal_value == literal(0)
 530                                                 || v->literal_value == literal(1.0f));
 531         }
 532
 533         bool is_undef() { return gvalue()->kind == VLK_UNDEF; }
 534
 535         bool is_any_gpr() {
 536                 return (kind == VLK_REG || kind == VLK_TEMP);
 537         }
 538
 539         bool is_agpr() {
 540                 return array && is_any_gpr();
 541         }
 542
 543         // scalar gpr, as opposed to element of gpr array
 544         bool is_sgpr() {
 545                 return !array && is_any_gpr();
 546         }
 547
 548         bool is_special_reg() { return kind == VLK_SPECIAL_REG; }
 549         bool is_any_reg() { return is_any_gpr() || is_special_reg(); }
 550         bool is_kcache() { return kind == VLK_KCACHE; }
 551         bool is_rel() { return kind == VLK_REL_REG; }
 552         bool is_readonly() { return flags & VLF_READONLY; }
 553
 554         bool is_chan_pinned() { return flags & VLF_PIN_CHAN; }
 555         bool is_reg_pinned() { return flags & VLF_PIN_REG; }
 556
 557         bool is_global();
 558         void set_global();
 559         void set_prealloc();
 560
 561         bool is_prealloc();
 562
 563         bool is_fixed();
 564         void fix();
 565
 566         bool is_dead() { return flags & VLF_DEAD; }
 567
 568         literal & get_const_value() {
 569                 value *v = gvalue();
 570                 assert(v->is_const());
 571                 return v->literal_value;
 572         }
 573
 574         // true if needs to be encoded as literal in alu
 575         bool is_literal() {
 576                 return is_const()
 577                                 && literal_value != literal(0)
 578                                 && literal_value != literal(1)
 579                                 && literal_value != literal(-1)
 580                                 && literal_value != literal(0.5)
 581                                 && literal_value != literal(1.0);
 582         }
 583
 584         void add_use(node *n, use_kind kind, int arg);
 585
 586         value_hash hash();
 587         value_hash rel_hash();
 588
 589         void assign_source(value *v) {
 590                 assert(!gvn_source || gvn_source == this);
 591                 gvn_source = v->gvalue();
 592         }
 593
 594         bool v_equal(value *v) { return gvalue() == v->gvalue(); }
 595
 596         unsigned use_count();
 597         void delete_uses();
 598
 599         sel_chan get_final_gpr() {
 600                 if (array && array->gpr) {
 601                         int reg_offset = select.sel() - array->base_gpr.sel();
 602                         if (rel && rel->is_const())
 603                                 reg_offset += rel->get_const_value().i;
 604                         return array->gpr + (reg_offset << 2);
 605                 } else {
 606                         return gpr;
 607                 }
 608         }
 609
 610         unsigned get_final_chan() {
 611                 if (array) {
 612                         assert(array->gpr);
 613                         return array->gpr.chan();
 614                 } else {
 615                         assert(gpr);
 616                         return gpr.chan();
 617                 }
 618         }
 619
 620         val_set interferences;
 621         unsigned uid;
 622 };
 623
 624 class expr_handler;
 625
 626 class value_table {
 627         typedef std::vector<value*> vt_item;
 628         typedef std::vector<vt_item> vt_table;
 629
 630         expr_handler &ex;
 631
 632         unsigned size_bits;
 633         unsigned size;
 634         unsigned size_mask;
 635
 636         vt_table hashtable;
 637
 638         unsigned cnt;
 639
 640 public:
 641
 642         value_table(expr_handler &ex, unsigned size_bits = 10)
 643                 : ex(ex), size_bits(size_bits), size(1u << size_bits),
 644                   size_mask(size - 1), hashtable(size), cnt() {}
 645
 646         ~value_table() {}
 647
 648         void add_value(value* v);
 649
 650         bool expr_equal(value* l, value* r);
 651
 652         unsigned count() { return cnt; }
 653
 654         void get_values(vvec & v);
 655 };
 656
 657 class sb_context;
 658
 659 enum node_type {
 660         NT_UNKNOWN,
 661         NT_LIST,
 662         NT_OP,
 663         NT_REGION,
 664         NT_REPEAT,
 665         NT_DEPART,
 666         NT_IF,
 667 };
 668
 669 enum node_subtype {
 670         NST_UNKNOWN,
 671         NST_LIST,
 672         NST_ALU_GROUP,
 673         NST_ALU_CLAUSE,
 674         NST_ALU_INST,
 675         NST_ALU_PACKED_INST,
 676         NST_CF_INST,
 677         NST_FETCH_INST,
 678         NST_TEX_CLAUSE,
 679         NST_VTX_CLAUSE,
 680
 681         NST_BB,
 682
 683         NST_PHI,
 684         NST_PSI,
 685         NST_COPY,
 686
 687         NST_LOOP_PHI_CONTAINER,
 688         NST_LOOP_CONTINUE,
 689         NST_LOOP_BREAK
 690 };
 691
 692 enum node_flags {
 693         NF_EMPTY = 0,
 694         NF_DEAD = (1 << 0),
 695         NF_REG_CONSTRAINT = (1 << 1),
 696         NF_CHAN_CONSTRAINT = (1 << 2),
 697         NF_ALU_4SLOT = (1 << 3),
 698         NF_CONTAINER = (1 << 4),
 699
 700         NF_COPY_MOV = (1 << 5),
 701
 702         NF_DONT_KILL = (1 << 6),
 703         NF_DONT_HOIST = (1 << 7),
 704         NF_DONT_MOVE = (1 << 8),
 705
 706         // for KILLxx - we want to schedule them as early as possible
 707         NF_SCHEDULE_EARLY = (1 << 9),
 708
 709         // for ALU_PUSH_BEFORE - when set, replace with PUSH + ALU
 710         NF_ALU_STACK_WORKAROUND = (1 << 10)
 711 };
 712
 713 inline node_flags operator |(node_flags l, node_flags r) {
 714         return (node_flags)((unsigned)l|(unsigned)r);
 715 }
 716 inline node_flags& operator |=(node_flags &l, node_flags r) {
 717         l = l | r;
 718         return l;
 719 }
 720
 721 inline node_flags& operator &=(node_flags &l, node_flags r) {
 722         l = (node_flags)((unsigned)l & (unsigned)r);
 723         return l;
 724 }
 725
 726 inline node_flags operator ~(node_flags r) {
 727         return (node_flags)~(unsigned)r;
 728 }
 729
 730 struct node_stats {
 731         unsigned alu_count;
 732         unsigned alu_kill_count;
 733         unsigned alu_copy_mov_count;
 734         unsigned cf_count;
 735         unsigned fetch_count;
 736         unsigned region_count;
 737         unsigned loop_count;
 738         unsigned phi_count;
 739         unsigned loop_phi_count;
 740         unsigned depart_count;
 741         unsigned repeat_count;
 742         unsigned if_count;
 743
 744         node_stats() : alu_count(), alu_kill_count(), alu_copy_mov_count(),
 745                         cf_count(), fetch_count(), region_count(),
 746                         loop_count(), phi_count(), loop_phi_count(), depart_count(),
 747                         repeat_count(), if_count() {}
 748
 749         void dump();
 750 };
 751
 752 class shader;
 753
 754 class vpass;
 755
 756 class container_node;
 757 class region_node;
 758
 759 class node {
 760
 761 protected:
 762         node(node_type nt, node_subtype nst, node_flags flags = NF_EMPTY)
 763         : prev(), next(), parent(),
 764           type(nt), subtype(nst), flags(flags),
 765           pred(), dst(), src() {}
 766
 767         virtual ~node() {};
 768
 769 public:
 770         node *prev, *next;
 771         container_node *parent;
 772
 773         node_type type;
 774         node_subtype subtype;
 775         node_flags flags;
 776
 777         value *pred;
 778
 779         vvec dst;
 780         vvec src;
 781
 782         virtual bool is_valid() { return true; }
 783         virtual bool accept(vpass &p, bool enter);
 784
 785         void insert_before(node *n);
 786         void insert_after(node *n);
 787         void replace_with(node *n);
 788         void remove();
 789
 790         virtual value_hash hash();
 791         value_hash hash_src();
 792
 793         virtual bool fold_dispatch(expr_handler *ex);
 794
 795         bool is_container() { return flags & NF_CONTAINER; }
 796
 797         bool is_alu_packed() { return subtype == NST_ALU_PACKED_INST; }
 798         bool is_alu_inst() { return subtype == NST_ALU_INST; }
 799         bool is_alu_group() { return subtype == NST_ALU_GROUP; }
 800         bool is_alu_clause() { return subtype == NST_ALU_CLAUSE; }
 801
 802         bool is_fetch_clause() {
 803                 return subtype == NST_TEX_CLAUSE || subtype == NST_VTX_CLAUSE;
 804         }
 805
 806         bool is_copy() { return subtype == NST_COPY; }
 807         bool is_copy_mov() { return flags & NF_COPY_MOV; }
 808         bool is_any_alu() { return is_alu_inst() || is_alu_packed() || is_copy(); }
 809
 810         bool is_fetch_inst() { return subtype == NST_FETCH_INST; }
 811         bool is_cf_inst() { return subtype == NST_CF_INST; }
 812
 813         bool is_region() { return type == NT_REGION; }
 814         bool is_depart() { return type == NT_DEPART; }
 815         bool is_repeat() { return type == NT_REPEAT; }
 816         bool is_if() { return type == NT_IF; }
 817         bool is_bb() { return subtype == NST_BB; }
 818
 819         bool is_phi() { return subtype == NST_PHI; }
 820
 821         bool is_dead() { return flags & NF_DEAD; }
 822
 823         bool is_cf_op(unsigned op);
 824         bool is_alu_op(unsigned op);
 825         bool is_fetch_op(unsigned op);
 826
 827         unsigned cf_op_flags();
 828         unsigned alu_op_flags();
 829         unsigned alu_op_slot_flags();
 830         unsigned fetch_op_flags();
 831
 832         bool is_mova();
 833         bool is_pred_set();
 834
 835         bool vec_uses_ar(vvec &vv) {
 836                 for (vvec::iterator I = vv.begin(), E = vv.end(); I != E; ++I) {
 837                         value *v = *I;
 838                         if (v && v->rel && !v->rel->is_const())
 839                                 return true;
 840                 }
 841                 return false;
 842         }
 843
 844         bool uses_ar() {
 845                 return vec_uses_ar(dst) || vec_uses_ar(src);
 846         }
 847
 848
 849         region_node* get_parent_region();
 850
 851         friend class shader;
 852 };
 853
 854 class container_node : public node {
 855 public:
 856
 857         container_node(node_type nt = NT_LIST, node_subtype nst = NST_LIST,
 858                        node_flags flags = NF_EMPTY)
 859         : node(nt, nst, flags | NF_CONTAINER), first(), last(),
 860           live_after(), live_before() {}
 861
 862         // child items list
 863         node *first, *last;
 864
 865         val_set live_after;
 866         val_set live_before;
 867
 868         class iterator {
 869                 node *p;
 870         public:
 871                 iterator(node *pp = NULL) : p(pp) {}
 872                 iterator & operator ++() { p = p->next; return *this;}
 873                 iterator & operator --() { p = p->prev; return *this;}
 874                 node* operator *() { return p; }
 875                 node* operator ->() { return p; }
 876                 const iterator advance(int n) {
 877                         if (!n) return *this;
 878                         iterator I(p);
 879                         if (n > 0) while (n--) ++I;
 880                         else while (n++) --I;
 881                         return I;
 882                 }
 883                 const iterator operator +(int n) { return advance(n); }
 884                 const iterator operator -(int n) { return advance(-n); }
 885                 bool operator !=(const iterator &i) { return p != i.p; }
 886                 bool operator ==(const iterator &i) { return p == i.p; }
 887         };
 888
 889         class riterator {
 890                 iterator i;
 891         public:
 892                 riterator(node *p = NULL) : i(p) {}
 893                 riterator & operator ++() { --i; return *this;}
 894                 riterator & operator --() { ++i; return *this;}
 895                 node* operator *() { return *i; }
 896                 node* operator ->() { return *i; }
 897                 bool operator !=(const riterator &r) { return i != r.i; }
 898                 bool operator ==(const riterator &r) { return i == r.i; }
 899         };
 900
 901         iterator begin() { return first; }
 902         iterator end() { return NULL; }
 903         riterator rbegin() { return last; }
 904         riterator rend() { return NULL; }
 905
 906         bool empty() { assert(first != NULL || first == last); return !first; }
 907         unsigned count();
 908
 909         // used with node containers that represent shceduling queues
 910         // ignores copies and takes into account alu_packed_node items
 911         unsigned real_alu_count();
 912
 913         void push_back(node *n);
 914         void push_front(node *n);
 915
 916         void insert_node_before(node *s, node *n);
 917         void insert_node_after(node *s, node *n);
 918
 919         void append_from(container_node *c);
 920
 921         // remove range [b..e) from some container and assign to this container
 922         void move(iterator b, iterator e);
 923
 924         void expand();
 925         void expand(container_node *n);
 926         void remove_node(node *n);
 927
 928         node *cut(iterator b, iterator e);
 929
 930         void clear() { first = last = NULL; }
 931
 932         virtual bool is_valid() { return true; }
 933         virtual bool accept(vpass &p, bool enter);
 934         virtual bool fold_dispatch(expr_handler *ex);
 935
 936         node* front() { return first; }
 937         node* back() { return last; }
 938
 939         void collect_stats(node_stats &s);
 940
 941         friend class shader;
 942
 943
 944 };
 945
 946 typedef container_node::iterator node_iterator;
 947 typedef container_node::riterator node_riterator;
 948
 949 class alu_group_node : public container_node {
 950 protected:
 951         alu_group_node() : container_node(NT_LIST, NST_ALU_GROUP), literals() {}
 952 public:
 953
 954         std::vector<literal> literals;
 955
 956         virtual bool is_valid() { return subtype == NST_ALU_GROUP; }
 957         virtual bool accept(vpass &p, bool enter);
 958
 959
 960         unsigned literal_chan(literal l) {
 961                 std::vector<literal>::iterator F =
 962                                 std::find(literals.begin(), literals.end(), l);
 963                 assert(F != literals.end());
 964                 return F - literals.begin();
 965         }
 966
 967         friend class shader;
 968 };
 969
 970 class cf_node : public container_node {
 971 protected:
 972         cf_node() : container_node(NT_OP, NST_CF_INST), jump_target(),
 973                 jump_after_target() { memset(&bc, 0, sizeof(bc_cf)); };
 974 public:
 975         bc_cf bc;
 976
 977         cf_node *jump_target;
 978         bool jump_after_target;
 979
 980         virtual bool is_valid() { return subtype == NST_CF_INST; }
 981         virtual bool accept(vpass &p, bool enter);
 982         virtual bool fold_dispatch(expr_handler *ex);
 983
 984         void jump(cf_node *c) { jump_target = c; jump_after_target = false; }
 985         void jump_after(cf_node *c) { jump_target = c; jump_after_target = true; }
 986
 987         friend class shader;
 988 };
 989
 990 class alu_node : public node {
 991 protected:
 992         alu_node() : node(NT_OP, NST_ALU_INST) { memset(&bc, 0, sizeof(bc_alu)); };
 993 public:
 994         bc_alu bc;
 995
 996         virtual bool is_valid() { return subtype == NST_ALU_INST; }
 997         virtual bool accept(vpass &p, bool enter);
 998         virtual bool fold_dispatch(expr_handler *ex);
 999
1000         unsigned forced_bank_swizzle() {
1001                 return ((bc.op_ptr->flags & AF_INTERP) && (bc.slot_flags == AF_4V)) ?
1002                                 VEC_210 : 0;
1003         }
1004
1005         // return param index + 1 if instruction references interpolation param,
1006         // otherwise 0
1007         unsigned interp_param();
1008
1009         alu_group_node *get_alu_group_node();
1010
1011         friend class shader;
1012 };
1013
1014 // for multi-slot instrs - DOT/INTERP/... (maybe useful for 64bit pairs later)
1015 class alu_packed_node : public container_node {
1016 protected:
1017         alu_packed_node() : container_node(NT_OP, NST_ALU_PACKED_INST) {}
1018 public:
1019
1020         const alu_op_info* op_ptr() {
1021                 return static_cast<alu_node*>(first)->bc.op_ptr;
1022         }
1023         unsigned op() { return static_cast<alu_node*>(first)->bc.op; }
1024         void init_args(bool repl);
1025
1026         virtual bool is_valid() { return subtype == NST_ALU_PACKED_INST; }
1027         virtual bool accept(vpass &p, bool enter);
1028         virtual bool fold_dispatch(expr_handler *ex);
1029
1030         unsigned get_slot_mask();
1031         void update_packed_items(sb_context &ctx);
1032
1033         friend class shader;
1034 };
1035
1036 class fetch_node : public node {
1037 protected:
1038         fetch_node() : node(NT_OP, NST_FETCH_INST) { memset(&bc, 0, sizeof(bc_fetch)); };
1039 public:
1040         bc_fetch bc;
1041
1042         virtual bool is_valid() { return subtype == NST_FETCH_INST; }
1043         virtual bool accept(vpass &p, bool enter);
1044         virtual bool fold_dispatch(expr_handler *ex);
1045
1046         bool uses_grad() { return bc.op_ptr->flags & FF_USEGRAD; }
1047
1048         friend class shader;
1049 };
1050
1051 class region_node;
1052
1053 class repeat_node : public container_node {
1054 protected:
1055         repeat_node(region_node *target, unsigned id)
1056         : container_node(NT_REPEAT, NST_LIST), target(target), rep_id(id) {}
1057 public:
1058         region_node *target;
1059         unsigned rep_id;
1060
1061         virtual bool accept(vpass &p, bool enter);
1062
1063         friend class shader;
1064 };
1065
1066 class depart_node : public container_node {
1067 protected:
1068         depart_node(region_node *target, unsigned id)
1069         : container_node(NT_DEPART, NST_LIST), target(target), dep_id(id) {}
1070 public:
1071         region_node *target;
1072         unsigned dep_id;
1073
1074         virtual bool accept(vpass &p, bool enter);
1075
1076         friend class shader;
1077 };
1078
1079 class if_node : public container_node {
1080 protected:
1081         if_node() : container_node(NT_IF, NST_LIST), cond() {};
1082 public:
1083         value *cond; // glued to pseudo output (dst[2]) of the PRED_SETxxx
1084
1085         virtual bool accept(vpass &p, bool enter);
1086
1087         friend class shader;
1088 };
1089
1090 typedef std::vector<depart_node*> depart_vec;
1091 typedef std::vector<repeat_node*> repeat_vec;
1092
1093 class region_node : public container_node {
1094 protected:
1095         region_node(unsigned id) : container_node(NT_REGION, NST_LIST), region_id(id),
1096                         loop_phi(), phi(), vars_defined(), departs(), repeats(), src_loop()
1097                         {}
1098 public:
1099         unsigned region_id;
1100
1101         container_node *loop_phi;
1102         container_node *phi;
1103
1104         val_set vars_defined;
1105
1106         depart_vec departs;
1107         repeat_vec repeats;
1108
1109         // true if region was created for loop in the parser, sometimes repeat_node
1110         // may be optimized away so we need to remember this information
1111         bool src_loop;
1112
1113         virtual bool accept(vpass &p, bool enter);
1114
1115         unsigned dep_count() { return departs.size(); }
1116         unsigned rep_count() { return repeats.size() + 1; }
1117
1118         bool is_loop() { return src_loop || !repeats.empty(); }
1119
1120         container_node* get_entry_code_location() {
1121                 node *p = first;
1122                 while (p && (p->is_depart() || p->is_repeat()))
1123                         p = static_cast<container_node*>(p)->first;
1124
1125                 container_node *c = static_cast<container_node*>(p);
1126                 if (c->is_bb())
1127                         return c;
1128                 else
1129                         return c->parent;
1130         }
1131
1132         void expand_depart(depart_node *d);
1133         void expand_repeat(repeat_node *r);
1134
1135         friend class shader;
1136 };
1137
1138 class bb_node : public container_node {
1139 protected:
1140         bb_node(unsigned id, unsigned loop_level)
1141                 : container_node(NT_LIST, NST_BB), id(id), loop_level(loop_level) {}
1142 public:
1143         unsigned id;
1144         unsigned loop_level;
1145
1146         virtual bool accept(vpass &p, bool enter);
1147
1148         friend class shader;
1149 };
1150
1151
1152 typedef std::vector<region_node*> regions_vec;
1153 typedef std::vector<bb_node*> bbs_vec;
1154 typedef std::list<node*> sched_queue;
1155 typedef sched_queue::iterator sq_iterator;
1156 typedef std::vector<node*> node_vec;
1157 typedef std::list<node*> node_list;
1158 typedef std::set<node*> node_set;
1159
1160
1161
1162 } // namespace r600_sb
1163
1164 #endif /* R600_SB_IR_H_ */