Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  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. #define PSC_DEBUG 0
  28.  
  29. #if PSC_DEBUG
  30. #define PSC_DUMP(a) do { a } while (0)
  31. #else
  32. #define PSC_DUMP(a)
  33. #endif
  34.  
  35. #include "sb_bc.h"
  36. #include "sb_shader.h"
  37. #include "sb_pass.h"
  38. #include "sb_sched.h"
  39.  
  40. namespace r600_sb {
  41.  
  42. rp_kcache_tracker::rp_kcache_tracker(shader &sh) : rp(), uc(),
  43.                 // FIXME: for now we'll use "two const pairs" limit for r600, same as
  44.                 // for other chips, otherwise additional check in alu_group_tracker is
  45.                 // required to make sure that all 4 consts in the group fit into 2
  46.                 // kcache sets
  47.                 sel_count(2) {}
  48.  
  49. bool rp_kcache_tracker::try_reserve(sel_chan r) {
  50.         unsigned sel = kc_sel(r);
  51.  
  52.         for (unsigned i = 0; i < sel_count; ++i) {
  53.                 if (rp[i] == 0) {
  54.                         rp[i] = sel;
  55.                         ++uc[i];
  56.                         return true;
  57.                 }
  58.                 if (rp[i] == sel) {
  59.                         ++uc[i];
  60.                         return true;
  61.                 }
  62.         }
  63.         return false;
  64. }
  65.  
  66. bool rp_kcache_tracker::try_reserve(node* n) {
  67.         bool need_unreserve = false;
  68.         vvec::iterator I(n->src.begin()), E(n->src.end());
  69.  
  70.         for (; I != E; ++I) {
  71.                 value *v = *I;
  72.                 if (v->is_kcache()) {
  73.                         if (!try_reserve(v->select))
  74.                                 break;
  75.                         else
  76.                                 need_unreserve = true;
  77.                 }
  78.         }
  79.         if (I == E)
  80.                 return true;
  81.  
  82.         if (need_unreserve && I != n->src.begin()) {
  83.                 do {
  84.                         --I;
  85.                         value *v =*I;
  86.                         if (v->is_kcache())
  87.                                 unreserve(v->select);
  88.                 } while (I != n->src.begin());
  89.         }
  90.         return false;
  91. }
  92.  
  93. inline
  94. void rp_kcache_tracker::unreserve(node* n) {
  95.         vvec::iterator I(n->src.begin()), E(n->src.end());
  96.         for (; I != E; ++I) {
  97.                 value *v = *I;
  98.                 if (v->is_kcache())
  99.                         unreserve(v->select);
  100.         }
  101. }
  102.  
  103. void rp_kcache_tracker::unreserve(sel_chan r) {
  104.         unsigned sel = kc_sel(r);
  105.  
  106.         for (unsigned i = 0; i < sel_count; ++i)
  107.                 if (rp[i] == sel) {
  108.                         if (--uc[i] == 0)
  109.                                 rp[i] = 0;
  110.                         return;
  111.                 }
  112.         assert(0);
  113.         return;
  114. }
  115.  
  116. bool literal_tracker::try_reserve(alu_node* n) {
  117.         bool need_unreserve = false;
  118.  
  119.         vvec::iterator I(n->src.begin()), E(n->src.end());
  120.  
  121.         for (; I != E; ++I) {
  122.                 value *v = *I;
  123.                 if (v->is_literal()) {
  124.                         if (!try_reserve(v->literal_value))
  125.                                 break;
  126.                         else
  127.                                 need_unreserve = true;
  128.                 }
  129.         }
  130.         if (I == E)
  131.                 return true;
  132.  
  133.         if (need_unreserve && I != n->src.begin()) {
  134.                 do {
  135.                         --I;
  136.                         value *v =*I;
  137.                         if (v->is_literal())
  138.                                 unreserve(v->literal_value);
  139.                 } while (I != n->src.begin());
  140.         }
  141.         return false;
  142. }
  143.  
  144. void literal_tracker::unreserve(alu_node* n) {
  145.         unsigned nsrc = n->bc.op_ptr->src_count, i;
  146.  
  147.         for (i = 0; i < nsrc; ++i) {
  148.                 value *v = n->src[i];
  149.                 if (v->is_literal())
  150.                         unreserve(v->literal_value);
  151.         }
  152. }
  153.  
  154. bool literal_tracker::try_reserve(literal l) {
  155.  
  156.         PSC_DUMP( sblog << "literal reserve " << l.u << "  " << l.f << "\n"; );
  157.  
  158.         for (unsigned i = 0; i < MAX_ALU_LITERALS; ++i) {
  159.                 if (lt[i] == 0) {
  160.                         lt[i] = l;
  161.                         ++uc[i];
  162.                         PSC_DUMP( sblog << "  reserved new uc = " << uc[i] << "\n"; );
  163.                         return true;
  164.                 } else if (lt[i] == l) {
  165.                         ++uc[i];
  166.                         PSC_DUMP( sblog << "  reserved uc = " << uc[i] << "\n"; );
  167.                         return true;
  168.                 }
  169.         }
  170.         PSC_DUMP( sblog << "  failed to reserve literal\n"; );
  171.         return false;
  172. }
  173.  
  174. void literal_tracker::unreserve(literal l) {
  175.  
  176.         PSC_DUMP( sblog << "literal unreserve " << l.u << "  " << l.f << "\n"; );
  177.  
  178.         for (unsigned i = 0; i < MAX_ALU_LITERALS; ++i) {
  179.                 if (lt[i] == l) {
  180.                         if (--uc[i] == 0)
  181.                                 lt[i] = 0;
  182.                         return;
  183.                 }
  184.         }
  185.         assert(0);
  186.         return;
  187. }
  188.  
  189. static inline unsigned bs_cycle_vector(unsigned bs, unsigned src) {
  190.         static const unsigned swz[VEC_NUM][3] = {
  191.                 {0, 1, 2}, {0, 2, 1}, {1, 2, 0}, {1, 0, 2}, {2, 0, 1}, {2, 1, 0}
  192.         };
  193.         assert(bs < VEC_NUM && src < 3);
  194.         return swz[bs][src];
  195. }
  196.  
  197. static inline unsigned bs_cycle_scalar(unsigned bs, unsigned src) {
  198.         static const unsigned swz[SCL_NUM][3] = {
  199.                 {2, 1, 0}, {1, 2, 2}, {2, 1, 2}, {2, 2, 1}
  200.         };
  201.  
  202.         if (bs >= SCL_NUM || src >= 3) {
  203.                 // this prevents gcc warning "array subscript is above array bounds"
  204.                 // AFAICS we should never hit this path
  205.                 abort();
  206.         }
  207.         return swz[bs][src];
  208. }
  209.  
  210. static inline unsigned bs_cycle(bool trans, unsigned bs, unsigned src) {
  211.         return trans ? bs_cycle_scalar(bs, src) : bs_cycle_vector(bs, src);
  212. }
  213.  
  214. inline
  215. bool rp_gpr_tracker::try_reserve(unsigned cycle, unsigned sel, unsigned chan) {
  216.         ++sel;
  217.         if (rp[cycle][chan] == 0) {
  218.                 rp[cycle][chan] = sel;
  219.                 ++uc[cycle][chan];
  220.                 return true;
  221.         } else if (rp[cycle][chan] == sel) {
  222.                 ++uc[cycle][chan];
  223.                 return true;
  224.         }
  225.         return false;
  226. }
  227.  
  228. inline
  229. void rp_gpr_tracker::unreserve(alu_node* n) {
  230.         unsigned nsrc = n->bc.op_ptr->src_count, i;
  231.         unsigned trans = n->bc.slot == SLOT_TRANS;
  232.         unsigned bs = n->bc.bank_swizzle;
  233.         unsigned opt = !trans
  234.                         && n->bc.src[0].sel == n->bc.src[1].sel
  235.                         && n->bc.src[0].chan == n->bc.src[1].chan;
  236.  
  237.         for (i = 0; i < nsrc; ++i) {
  238.                 value *v = n->src[i];
  239.                 if (v->is_readonly())
  240.                         continue;
  241.                 if (i == 1 && opt)
  242.                         continue;
  243.                 unsigned cycle = bs_cycle(trans, bs, i);
  244.                 unreserve(cycle, n->bc.src[i].sel, n->bc.src[i].chan);
  245.         }
  246. }
  247.  
  248. inline
  249. void rp_gpr_tracker::unreserve(unsigned cycle, unsigned sel, unsigned chan) {
  250.         ++sel;
  251.         assert(rp[cycle][chan] == sel && uc[cycle][chan]);
  252.         if (--uc[cycle][chan] == 0)
  253.                 rp[cycle][chan] = 0;
  254. }
  255.  
  256. inline
  257. bool rp_gpr_tracker::try_reserve(alu_node* n) {
  258.         unsigned nsrc = n->bc.op_ptr->src_count, i;
  259.         unsigned trans = n->bc.slot == SLOT_TRANS;
  260.         unsigned bs = n->bc.bank_swizzle;
  261.         unsigned opt = !trans && nsrc >= 2 &&
  262.                         n->src[0] == n->src[1];
  263.  
  264.         bool need_unreserve = false;
  265.         unsigned const_count = 0, min_gpr_cycle = 3;
  266.  
  267.         for (i = 0; i < nsrc; ++i) {
  268.                 value *v = n->src[i];
  269.                 if (v->is_readonly() || v->is_undef()) {
  270.                         const_count++;
  271.                         if (trans && const_count == 3)
  272.                                 break;
  273.                 } else {
  274.                         if (i == 1 && opt)
  275.                                 continue;
  276.  
  277.                         unsigned cycle = bs_cycle(trans, bs, i);
  278.  
  279.                         if (trans && cycle < min_gpr_cycle)
  280.                                 min_gpr_cycle = cycle;
  281.  
  282.                         if (const_count && cycle < const_count && trans)
  283.                                 break;
  284.  
  285.                         if (!try_reserve(cycle, n->bc.src[i].sel, n->bc.src[i].chan))
  286.                                 break;
  287.                         else
  288.                                 need_unreserve = true;
  289.                 }
  290.         }
  291.  
  292.         if ((i == nsrc) && (min_gpr_cycle + 1 > const_count))
  293.                 return true;
  294.  
  295.         if (need_unreserve && i--) {
  296.                 do {
  297.                         value *v = n->src[i];
  298.                         if (!v->is_readonly() && !v->is_undef()) {
  299.                         if (i == 1 && opt)
  300.                                 continue;
  301.                         unreserve(bs_cycle(trans, bs, i), n->bc.src[i].sel,
  302.                                   n->bc.src[i].chan);
  303.                         }
  304.                 } while (i--);
  305.         }
  306.         return false;
  307. }
  308.  
  309. alu_group_tracker::alu_group_tracker(shader &sh)
  310.         : sh(sh), kc(sh),
  311.           gpr(), lt(), slots(),
  312.           max_slots(sh.get_ctx().is_cayman() ? 4 : 5),
  313.           has_mova(), uses_ar(), has_predset(), has_kill(),
  314.           updates_exec_mask(), chan_count(), interp_param(), next_id() {
  315.  
  316.         available_slots = sh.get_ctx().has_trans ? 0x1F : 0x0F;
  317. }
  318.  
  319. inline
  320. sel_chan alu_group_tracker::get_value_id(value* v) {
  321.         unsigned &id = vmap[v];
  322.         if (!id)
  323.                 id = ++next_id;
  324.         return sel_chan(id, v->get_final_chan());
  325. }
  326.  
  327. inline
  328. void alu_group_tracker::assign_slot(unsigned slot, alu_node* n) {
  329.         update_flags(n);
  330.         slots[slot] = n;
  331.         available_slots &= ~(1 << slot);
  332.  
  333.         unsigned param = n->interp_param();
  334.  
  335.         if (param) {
  336.                 assert(!interp_param || interp_param == param);
  337.                 interp_param = param;
  338.         }
  339. }
  340.  
  341.  
  342. void alu_group_tracker::discard_all_slots(container_node &removed_nodes) {
  343.         PSC_DUMP( sblog << "agt::discard_all_slots\n"; );
  344.         discard_slots(~available_slots & ((1 << max_slots) - 1), removed_nodes);
  345. }
  346.  
  347. void alu_group_tracker::discard_slots(unsigned slot_mask,
  348.                                     container_node &removed_nodes) {
  349.  
  350.         PSC_DUMP(
  351.                 sblog << "discard_slots : packed_ops : "
  352.                         << (unsigned)packed_ops.size() << "\n";
  353.         );
  354.  
  355.         for (node_vec::iterator N, I = packed_ops.begin();
  356.                         I != packed_ops.end(); I = N) {
  357.                 N = I; ++N;
  358.  
  359.                 alu_packed_node *n = static_cast<alu_packed_node*>(*I);
  360.                 unsigned pslots = n->get_slot_mask();
  361.  
  362.                 PSC_DUMP(
  363.                         sblog << "discard_slots : packed slot_mask : " << pslots << "\n";
  364.                 );
  365.  
  366.                 if (pslots & slot_mask) {
  367.  
  368.                         PSC_DUMP(
  369.                                 sblog << "discard_slots : discarding packed...\n";
  370.                         );
  371.  
  372.                         removed_nodes.push_back(n);
  373.                         slot_mask &= ~pslots;
  374.                         N = packed_ops.erase(I);
  375.                         available_slots |= pslots;
  376.                         for (unsigned k = 0; k < max_slots; ++k) {
  377.                                 if (pslots & (1 << k))
  378.                                         slots[k] = NULL;
  379.                         }
  380.                 }
  381.         }
  382.  
  383.         for (unsigned slot = 0; slot < max_slots; ++slot) {
  384.                 unsigned slot_bit = 1 << slot;
  385.  
  386.                 if (slot_mask & slot_bit) {
  387.                         assert(!(available_slots & slot_bit));
  388.                         assert(slots[slot]);
  389.  
  390.                         assert(!(slots[slot]->bc.slot_flags & AF_4SLOT));
  391.  
  392.                         PSC_DUMP(
  393.                                 sblog << "discarding slot " << slot << " : ";
  394.                                 dump::dump_op(slots[slot]);
  395.                                 sblog << "\n";
  396.                         );
  397.  
  398.                         removed_nodes.push_back(slots[slot]);
  399.                         slots[slot] = NULL;
  400.                         available_slots |= slot_bit;
  401.                 }
  402.         }
  403.  
  404.         alu_node *t = slots[4];
  405.         if (t && (t->bc.slot_flags & AF_V)) {
  406.                 unsigned chan = t->bc.dst_chan;
  407.                 if (!slots[chan]) {
  408.                         PSC_DUMP(
  409.                                 sblog << "moving ";
  410.                                 dump::dump_op(t);
  411.                                 sblog << " from trans slot to free slot " << chan << "\n";
  412.                         );
  413.  
  414.                         slots[chan] = t;
  415.                         slots[4] = NULL;
  416.                         t->bc.slot = chan;
  417.                 }
  418.         }
  419.  
  420.         reinit();
  421. }
  422.  
  423. alu_group_node* alu_group_tracker::emit() {
  424.  
  425.         alu_group_node *g = sh.create_alu_group();
  426.  
  427.         lt.init_group_literals(g);
  428.  
  429.         for (unsigned i = 0; i < max_slots; ++i) {
  430.                 alu_node *n = slots[i];
  431.                 if (n) {
  432.                         g->push_back(n);
  433.                 }
  434.         }
  435.         return g;
  436. }
  437.  
  438. bool alu_group_tracker::try_reserve(alu_node* n) {
  439.         unsigned nsrc = n->bc.op_ptr->src_count;
  440.         unsigned slot = n->bc.slot;
  441.         bool trans = slot == 4;
  442.  
  443.         if (slots[slot])
  444.                 return false;
  445.  
  446.         unsigned flags = n->bc.op_ptr->flags;
  447.  
  448.         unsigned param = n->interp_param();
  449.  
  450.         if (param && interp_param && interp_param != param)
  451.                 return false;
  452.  
  453.         if ((flags & AF_KILL) && has_predset)
  454.                 return false;
  455.         if ((flags & AF_ANY_PRED) && (has_kill || has_predset))
  456.                 return false;
  457.         if ((flags & AF_MOVA) && (has_mova || uses_ar))
  458.                 return false;
  459.  
  460.         if (n->uses_ar() && has_mova)
  461.                 return false;
  462.  
  463.         for (unsigned i = 0; i < nsrc; ++i) {
  464.  
  465.                 unsigned last_id = next_id;
  466.  
  467.                 value *v = n->src[i];
  468.                 if (!v->is_any_gpr() && !v->is_rel())
  469.                         continue;
  470.                 sel_chan vid = get_value_id(n->src[i]);
  471.  
  472.                 if (vid > last_id && chan_count[vid.chan()] == 3) {
  473.                         return false;
  474.                 }
  475.  
  476.                 n->bc.src[i].sel = vid.sel();
  477.                 n->bc.src[i].chan = vid.chan();
  478.         }
  479.  
  480.         if (!lt.try_reserve(n))
  481.                 return false;
  482.  
  483.         if (!kc.try_reserve(n)) {
  484.                 lt.unreserve(n);
  485.                 return false;
  486.         }
  487.  
  488.         unsigned fbs = n->forced_bank_swizzle();
  489.  
  490.         n->bc.bank_swizzle = 0;
  491.  
  492.         if (!trans & fbs)
  493.                 n->bc.bank_swizzle = VEC_210;
  494.  
  495.         if (gpr.try_reserve(n)) {
  496.                 assign_slot(slot, n);
  497.                 return true;
  498.         }
  499.  
  500.         if (!fbs) {
  501.                 unsigned swz_num = trans ? SCL_NUM : VEC_NUM;
  502.                 for (unsigned bs = 0; bs < swz_num; ++bs) {
  503.                         n->bc.bank_swizzle = bs;
  504.                         if (gpr.try_reserve(n)) {
  505.                                 assign_slot(slot, n);
  506.                                 return true;
  507.                         }
  508.                 }
  509.         }
  510.  
  511.         gpr.reset();
  512.  
  513.         slots[slot] = n;
  514.         unsigned forced_swz_slots = 0;
  515.         int first_slot = ~0, first_nf = ~0, last_slot = ~0;
  516.         unsigned save_bs[5];
  517.  
  518.         for (unsigned i = 0; i < max_slots; ++i) {
  519.                 alu_node *a = slots[i];
  520.                 if (a) {
  521.                         if (first_slot == ~0)
  522.                                 first_slot = i;
  523.                         last_slot = i;
  524.                         save_bs[i] = a->bc.bank_swizzle;
  525.                         if (a->forced_bank_swizzle()) {
  526.                                 assert(i != SLOT_TRANS);
  527.                                 forced_swz_slots |= (1 << i);
  528.                                 a->bc.bank_swizzle = VEC_210;
  529.                                 if (!gpr.try_reserve(a))
  530.                                         assert(!"internal reservation error");
  531.                         } else {
  532.                                 if (first_nf == ~0)
  533.                                         first_nf = i;
  534.  
  535.                                 a->bc.bank_swizzle = 0;
  536.                         }
  537.                 }
  538.         }
  539.  
  540.         if (first_nf == ~0) {
  541.                 assign_slot(slot, n);
  542.                 return true;
  543.         }
  544.  
  545.         assert(first_slot != ~0 && last_slot != ~0);
  546.  
  547.         // silence "array subscript is above array bounds" with gcc 4.8
  548.         if (last_slot >= 5)
  549.                 abort();
  550.  
  551.         int i = first_nf;
  552.         alu_node *a = slots[i];
  553.         bool backtrack = false;
  554.  
  555.         while (1) {
  556.  
  557.                 PSC_DUMP(
  558.                         sblog << " bs: trying s" << i << " bs:" << a->bc.bank_swizzle
  559.                                 << " bt:" << backtrack << "\n";
  560.                 );
  561.  
  562.                 if (!backtrack && gpr.try_reserve(a)) {
  563.                         PSC_DUMP(
  564.                                 sblog << " bs: reserved s" << i << " bs:" << a->bc.bank_swizzle
  565.                                         << "\n";
  566.                         );
  567.  
  568.                         while ((++i <= last_slot) && !slots[i]);
  569.                         if (i <= last_slot)
  570.                                 a = slots[i];
  571.                         else
  572.                                 break;
  573.                 } else {
  574.                         bool itrans = i == SLOT_TRANS;
  575.                         unsigned max_swz = itrans ? SCL_221 : VEC_210;
  576.  
  577.                         if (a->bc.bank_swizzle < max_swz) {
  578.                                 ++a->bc.bank_swizzle;
  579.  
  580.                                 PSC_DUMP(
  581.                                         sblog << " bs: inc s" << i << " bs:" << a->bc.bank_swizzle
  582.                                                 << "\n";
  583.                                 );
  584.  
  585.                         } else {
  586.  
  587.                                 a->bc.bank_swizzle = 0;
  588.                                 while ((--i >= first_nf) && !slots[i]);
  589.                                 if (i < first_nf)
  590.                                         break;
  591.                                 a = slots[i];
  592.                                 PSC_DUMP(
  593.                                         sblog << " bs: unreserve s" << i << " bs:" << a->bc.bank_swizzle
  594.                                                 << "\n";
  595.                                 );
  596.                                 gpr.unreserve(a);
  597.                                 backtrack = true;
  598.  
  599.                                 continue;
  600.                         }
  601.                 }
  602.                 backtrack = false;
  603.         }
  604.  
  605.         if (i == last_slot + 1) {
  606.                 assign_slot(slot, n);
  607.                 return true;
  608.         }
  609.  
  610.         // reservation failed, restore previous state
  611.         slots[slot] = NULL;
  612.         gpr.reset();
  613.         for (unsigned i = 0; i < max_slots; ++i) {
  614.                 alu_node *a = slots[i];
  615.                 if (a) {
  616.                         a->bc.bank_swizzle = save_bs[i];
  617.                         bool b = gpr.try_reserve(a);
  618.                         assert(b);
  619.                 }
  620.         }
  621.  
  622.         kc.unreserve(n);
  623.         lt.unreserve(n);
  624.         return false;
  625. }
  626.  
  627. bool alu_group_tracker::try_reserve(alu_packed_node* p) {
  628.         bool need_unreserve = false;
  629.         node_iterator I(p->begin()), E(p->end());
  630.  
  631.         for (; I != E; ++I) {
  632.                 alu_node *n = static_cast<alu_node*>(*I);
  633.                 if (!try_reserve(n))
  634.                         break;
  635.                 else
  636.                         need_unreserve = true;
  637.         }
  638.  
  639.         if (I == E)  {
  640.                 packed_ops.push_back(p);
  641.                 return true;
  642.         }
  643.  
  644.         if (need_unreserve) {
  645.                 while (--I != E) {
  646.                         alu_node *n = static_cast<alu_node*>(*I);
  647.                         slots[n->bc.slot] = NULL;
  648.                 }
  649.                 reinit();
  650.         }
  651.         return false;
  652. }
  653.  
  654. void alu_group_tracker::reinit() {
  655.         alu_node * s[5];
  656.         memcpy(s, slots, sizeof(slots));
  657.  
  658.         reset(true);
  659.  
  660.         for (int i = max_slots - 1; i >= 0; --i) {
  661.                 if (s[i] && !try_reserve(s[i])) {
  662.                         sblog << "alu_group_tracker: reinit error on slot " << i <<  "\n";
  663.                         for (unsigned i = 0; i < max_slots; ++i) {
  664.                                 sblog << "  slot " << i << " : ";
  665.                                 if (s[i])
  666.                                         dump::dump_op(s[i]);
  667.  
  668.                                 sblog << "\n";
  669.                         }
  670.                         assert(!"alu_group_tracker: reinit error");
  671.                 }
  672.         }
  673. }
  674.  
  675. void alu_group_tracker::reset(bool keep_packed) {
  676.         kc.reset();
  677.         gpr.reset();
  678.         lt.reset();
  679.         memset(slots, 0, sizeof(slots));
  680.         vmap.clear();
  681.         next_id = 0;
  682.         has_mova = false;
  683.         uses_ar = false;
  684.         has_predset = false;
  685.         has_kill = false;
  686.         updates_exec_mask = false;
  687.         available_slots = sh.get_ctx().has_trans ? 0x1F : 0x0F;
  688.         interp_param = 0;
  689.  
  690.         chan_count[0] = 0;
  691.         chan_count[1] = 0;
  692.         chan_count[2] = 0;
  693.         chan_count[3] = 0;
  694.  
  695.         if (!keep_packed)
  696.                 packed_ops.clear();
  697. }
  698.  
  699. void alu_group_tracker::update_flags(alu_node* n) {
  700.         unsigned flags = n->bc.op_ptr->flags;
  701.         has_kill |= (flags & AF_KILL);
  702.         has_mova |= (flags & AF_MOVA);
  703.         has_predset |= (flags & AF_ANY_PRED);
  704.         uses_ar |= n->uses_ar();
  705.  
  706.         if (flags & AF_ANY_PRED) {
  707.                 if (n->dst[2] != NULL)
  708.                         updates_exec_mask = true;
  709.         }
  710. }
  711.  
  712. int post_scheduler::run() {
  713.         run_on(sh.root);
  714.         return 0;
  715. }
  716.  
  717. void post_scheduler::run_on(container_node* n) {
  718.  
  719.         for (node_riterator I = n->rbegin(), E = n->rend(); I != E; ++I) {
  720.                 if (I->is_container()) {
  721.                         if (I->subtype == NST_BB) {
  722.                                 bb_node* bb = static_cast<bb_node*>(*I);
  723.                                 schedule_bb(bb);
  724.                         } else {
  725.                                 run_on(static_cast<container_node*>(*I));
  726.                         }
  727.                 }
  728.         }
  729. }
  730.  
  731. void post_scheduler::init_uc_val(container_node *c, value *v) {
  732.         node *d = v->any_def();
  733.         if (d && d->parent == c)
  734.                 ++ucm[d];
  735. }
  736.  
  737. void post_scheduler::init_uc_vec(container_node *c, vvec &vv, bool src) {
  738.         for (vvec::iterator I = vv.begin(), E = vv.end(); I != E; ++I) {
  739.                 value *v = *I;
  740.                 if (!v || v->is_readonly())
  741.                         continue;
  742.  
  743.                 if (v->is_rel()) {
  744.                         init_uc_val(c, v->rel);
  745.                         init_uc_vec(c, v->muse, true);
  746.                 } if (src) {
  747.                         init_uc_val(c, v);
  748.                 }
  749.         }
  750. }
  751.  
  752. unsigned post_scheduler::init_ucm(container_node *c, node *n) {
  753.         init_uc_vec(c, n->src, true);
  754.         init_uc_vec(c, n->dst, false);
  755.  
  756.         uc_map::iterator F = ucm.find(n);
  757.         return F == ucm.end() ? 0 : F->second;
  758. }
  759.  
  760. void post_scheduler::schedule_bb(bb_node* bb) {
  761.         PSC_DUMP(
  762.                 sblog << "scheduling BB " << bb->id << "\n";
  763.                 if (!pending.empty())
  764.                         dump::dump_op_list(&pending);
  765.         );
  766.  
  767.         assert(pending.empty());
  768.         assert(bb_pending.empty());
  769.         assert(ready.empty());
  770.  
  771.         bb_pending.append_from(bb);
  772.         cur_bb = bb;
  773.  
  774.         node *n;
  775.  
  776.         while ((n = bb_pending.back())) {
  777.  
  778.                 PSC_DUMP(
  779.                         sblog << "post_sched_bb ";
  780.                         dump::dump_op(n);
  781.                         sblog << "\n";
  782.                 );
  783.  
  784.                 if (n->subtype == NST_ALU_CLAUSE) {
  785.                         n->remove();
  786.                         process_alu(static_cast<container_node*>(n));
  787.                         continue;
  788.                 }
  789.  
  790.                 n->remove();
  791.                 bb->push_front(n);
  792.         }
  793.  
  794.         this->cur_bb = NULL;
  795. }
  796.  
  797. void post_scheduler::init_regmap() {
  798.  
  799.         regmap.clear();
  800.  
  801.         PSC_DUMP(
  802.                 sblog << "init_regmap: live: ";
  803.                 dump::dump_set(sh, live);
  804.                 sblog << "\n";
  805.         );
  806.  
  807.         for (val_set::iterator I = live.begin(sh), E = live.end(sh); I != E; ++I) {
  808.                 value *v = *I;
  809.                 assert(v);
  810.                 if (!v->is_sgpr() || !v->is_prealloc())
  811.                         continue;
  812.  
  813.                 sel_chan r = v->gpr;
  814.  
  815.                 PSC_DUMP(
  816.                         sblog << "init_regmap:  " << r << " <= ";
  817.                         dump::dump_val(v);
  818.                         sblog << "\n";
  819.                 );
  820.  
  821.                 assert(r);
  822.                 regmap[r] = v;
  823.         }
  824. }
  825.  
  826. void post_scheduler::process_alu(container_node *c) {
  827.  
  828.         if (c->empty())
  829.                 return;
  830.  
  831.         ucm.clear();
  832.         alu.reset();
  833.  
  834.         live = c->live_after;
  835.  
  836.         init_globals(c->live_after, true);
  837.         init_globals(c->live_before, true);
  838.  
  839.         init_regmap();
  840.  
  841.         update_local_interferences();
  842.  
  843.         for (node_riterator N, I = c->rbegin(), E = c->rend(); I != E; I = N) {
  844.                 N = I;
  845.                 ++N;
  846.  
  847.                 node *n = *I;
  848.                 unsigned uc = init_ucm(c, n);
  849.  
  850.                 PSC_DUMP(
  851.                         sblog << "process_alu uc=" << uc << "  ";
  852.                         dump::dump_op(n);
  853.                         sblog << "  ";
  854.                 );
  855.  
  856.                 if (uc) {
  857.                         n->remove();
  858.                         pending.push_back(n);
  859.                         PSC_DUMP( sblog << "pending\n"; );
  860.                 } else {
  861.                         release_op(n);
  862.                 }
  863.         }
  864.  
  865.         schedule_alu(c);
  866. }
  867.  
  868. void post_scheduler::update_local_interferences() {
  869.  
  870.         PSC_DUMP(
  871.                 sblog << "update_local_interferences : ";
  872.                 dump::dump_set(sh, live);
  873.                 sblog << "\n";
  874.         );
  875.  
  876.  
  877.         for (val_set::iterator I = live.begin(sh), E = live.end(sh); I != E; ++I) {
  878.                 value *v = *I;
  879.                 if (v->is_prealloc())
  880.                         continue;
  881.  
  882.                 v->interferences.add_set(live);
  883.         }
  884. }
  885.  
  886. void post_scheduler::update_live_src_vec(vvec &vv, val_set *born, bool src) {
  887.         for (vvec::iterator I = vv.begin(), E = vv.end(); I != E; ++I) {
  888.                 value *v = *I;
  889.  
  890.                 if (!v)
  891.                         continue;
  892.  
  893.                 if (src && v->is_any_gpr()) {
  894.                         if (live.add_val(v)) {
  895.                                 if (!v->is_prealloc()) {
  896.                                         if (!cleared_interf.contains(v)) {
  897.                                                 PSC_DUMP(
  898.                                                         sblog << "clearing interferences for " << *v << "\n";
  899.                                                 );
  900.                                                 v->interferences.clear();
  901.                                                 cleared_interf.add_val(v);
  902.                                         }
  903.                                 }
  904.                                 if (born)
  905.                                         born->add_val(v);
  906.                         }
  907.                 } else if (v->is_rel()) {
  908.                         if (!v->rel->is_any_gpr())
  909.                                 live.add_val(v->rel);
  910.                         update_live_src_vec(v->muse, born, true);
  911.                 }
  912.         }
  913. }
  914.  
  915. void post_scheduler::update_live_dst_vec(vvec &vv) {
  916.         for (vvec::iterator I = vv.begin(), E = vv.end(); I != E; ++I) {
  917.                 value *v = *I;
  918.                 if (!v)
  919.                         continue;
  920.  
  921.                 if (v->is_rel()) {
  922.                         update_live_dst_vec(v->mdef);
  923.                 } else if (v->is_any_gpr()) {
  924.                         if (!live.remove_val(v)) {
  925.                                 PSC_DUMP(
  926.                                                 sblog << "failed to remove ";
  927.                                 dump::dump_val(v);
  928.                                 sblog << " from live : ";
  929.                                 dump::dump_set(sh, live);
  930.                                 sblog << "\n";
  931.                                 );
  932.                         }
  933.                 }
  934.         }
  935. }
  936.  
  937. void post_scheduler::update_live(node *n, val_set *born) {
  938.         update_live_dst_vec(n->dst);
  939.         update_live_src_vec(n->src, born, true);
  940.         update_live_src_vec(n->dst, born, false);
  941. }
  942.  
  943. void post_scheduler::process_group() {
  944.         alu_group_tracker &rt = alu.grp();
  945.  
  946.         val_set vals_born;
  947.  
  948.         recolor_locals();
  949.  
  950.         PSC_DUMP(
  951.                 sblog << "process_group: live_before : ";
  952.                 dump::dump_set(sh, live);
  953.                 sblog << "\n";
  954.         );
  955.  
  956.         for (unsigned s = 0; s < ctx.num_slots; ++s) {
  957.                 alu_node *n = rt.slot(s);
  958.                 if (!n)
  959.                         continue;
  960.  
  961.                 update_live(n, &vals_born);
  962.         }
  963.  
  964.         PSC_DUMP(
  965.                 sblog << "process_group: live_after : ";
  966.                 dump::dump_set(sh, live);
  967.                 sblog << "\n";
  968.         );
  969.  
  970.         update_local_interferences();
  971.  
  972.         for (unsigned i = 0; i < 5; ++i) {
  973.                 node *n = rt.slot(i);
  974.                 if (n && !n->is_mova()) {
  975.                         release_src_values(n);
  976.                 }
  977.         }
  978. }
  979.  
  980. void post_scheduler::init_globals(val_set &s, bool prealloc) {
  981.  
  982.         PSC_DUMP(
  983.                 sblog << "init_globals: ";
  984.                 dump::dump_set(sh, s);
  985.                 sblog << "\n";
  986.         );
  987.  
  988.         for (val_set::iterator I = s.begin(sh), E = s.end(sh); I != E; ++I) {
  989.                 value *v = *I;
  990.                 if (v->is_sgpr() && !v->is_global()) {
  991.                         v->set_global();
  992.  
  993.                         if (prealloc && v->is_fixed()) {
  994.                                 v->set_prealloc();
  995.                         }
  996.                 }
  997.         }
  998. }
  999.  
  1000. void post_scheduler::emit_clause() {
  1001.  
  1002.         if (alu.current_ar) {
  1003.                 emit_load_ar();
  1004.                 process_group();
  1005.                 alu.emit_group();
  1006.         }
  1007.  
  1008.         alu.emit_clause(cur_bb);
  1009. }
  1010.  
  1011. void post_scheduler::schedule_alu(container_node *c) {
  1012.  
  1013.         assert(!ready.empty() || !ready_copies.empty());
  1014.  
  1015.         while (1) {
  1016.  
  1017.                 prev_regmap = regmap;
  1018.  
  1019.                 if (!prepare_alu_group()) {
  1020.                         if (alu.current_ar) {
  1021.                                 emit_load_ar();
  1022.                                 continue;
  1023.                         } else
  1024.                                 break;
  1025.                 }
  1026.  
  1027.                 if (!alu.check_clause_limits()) {
  1028.                         regmap = prev_regmap;
  1029.                         emit_clause();
  1030.                         init_globals(live, false);
  1031.                         continue;
  1032.                 }
  1033.  
  1034.                 process_group();
  1035.                 alu.emit_group();
  1036.         };
  1037.  
  1038.         if (!alu.is_empty()) {
  1039.                 emit_clause();
  1040.         }
  1041.  
  1042.         if (!ready.empty()) {
  1043.                 sblog << "##post_scheduler: unscheduled ready instructions :";
  1044.                 dump::dump_op_list(&ready);
  1045.                 assert(!"unscheduled ready instructions");
  1046.         }
  1047.  
  1048.         if (!pending.empty()) {
  1049.                 sblog << "##post_scheduler: unscheduled pending instructions :";
  1050.                 dump::dump_op_list(&pending);
  1051.                 assert(!"unscheduled pending instructions");
  1052.         }
  1053. }
  1054.  
  1055. void post_scheduler::add_interferences(value *v, sb_bitset &rb, val_set &vs) {
  1056.         unsigned chan = v->gpr.chan();
  1057.  
  1058.         for (val_set::iterator I = vs.begin(sh), E = vs.end(sh);
  1059.                         I != E; ++I) {
  1060.                 value *vi = *I;
  1061.                 sel_chan gpr = vi->get_final_gpr();
  1062.  
  1063.                 if (vi->is_any_gpr() && gpr && vi != v &&
  1064.                                 (!v->chunk || v->chunk != vi->chunk) &&
  1065.                                 vi->is_fixed() && gpr.chan() == chan) {
  1066.  
  1067.                         unsigned r = gpr.sel();
  1068.  
  1069.                         PSC_DUMP(
  1070.                                 sblog << "\tadd_interferences: " << *vi << "\n";
  1071.                         );
  1072.  
  1073.                         if (rb.size() <= r)
  1074.                                 rb.resize(r + 32);
  1075.                         rb.set(r);
  1076.                 }
  1077.         }
  1078. }
  1079.  
  1080. void post_scheduler::set_color_local_val(value *v, sel_chan color) {
  1081.         v->gpr = color;
  1082.  
  1083.         PSC_DUMP(
  1084.                 sblog << "     recolored: ";
  1085.                 dump::dump_val(v);
  1086.                 sblog << "\n";
  1087.         );
  1088. }
  1089.  
  1090. void post_scheduler::set_color_local(value *v, sel_chan color) {
  1091.         if (v->chunk) {
  1092.                 vvec &vv = v->chunk->values;
  1093.                 for (vvec::iterator I = vv.begin(), E = vv.end(); I != E; ++I) {
  1094.                         value *v2 =*I;
  1095.                         set_color_local_val(v2, color);
  1096.                 }
  1097.                 v->chunk->fix();
  1098.         } else {
  1099.                 set_color_local_val(v, color);
  1100.                 v->fix();
  1101.         }
  1102. }
  1103.  
  1104. bool post_scheduler::recolor_local(value *v) {
  1105.  
  1106.         sb_bitset rb;
  1107.  
  1108.         assert(v->is_sgpr());
  1109.         assert(!v->is_prealloc());
  1110.         assert(v->gpr);
  1111.  
  1112.         unsigned chan = v->gpr.chan();
  1113.  
  1114.         PSC_DUMP(
  1115.                 sblog << "recolor_local: ";
  1116.                 dump::dump_val(v);
  1117.                 sblog << "   interferences: ";
  1118.                 dump::dump_set(sh, v->interferences);
  1119.                 sblog << "\n";
  1120.                 if (v->chunk) {
  1121.                         sblog << "     in chunk: ";
  1122.                         coalescer::dump_chunk(v->chunk);
  1123.                         sblog << "\n";
  1124.                 }
  1125.         );
  1126.  
  1127.         if (v->chunk) {
  1128.                 for (vvec::iterator I = v->chunk->values.begin(),
  1129.                                 E = v->chunk->values.end(); I != E; ++I) {
  1130.                         value *v2 = *I;
  1131.  
  1132.                         PSC_DUMP( sblog << "   add_interferences for " << *v2 << " :\n"; );
  1133.  
  1134.                         add_interferences(v, rb, v2->interferences);
  1135.                 }
  1136.         } else {
  1137.                 add_interferences(v, rb, v->interferences);
  1138.         }
  1139.  
  1140.         PSC_DUMP(
  1141.                 unsigned sz = rb.size();
  1142.                 sblog << "registers bits: " << sz;
  1143.                 for (unsigned r = 0; r < sz; ++r) {
  1144.                         if ((r & 7) == 0)
  1145.                                 sblog << "\n  " << r << "   ";
  1146.                         sblog << (rb.get(r) ? 1 : 0);
  1147.                 }
  1148.         );
  1149.  
  1150.         bool no_temp_gprs = v->is_global();
  1151.         unsigned rs, re, pass = no_temp_gprs ? 1 : 0;
  1152.  
  1153.         while (pass < 2) {
  1154.  
  1155.                 if (pass == 0) {
  1156.                         rs = sh.first_temp_gpr();
  1157.                         re = MAX_GPR;
  1158.                 } else {
  1159.                         rs = 0;
  1160.                         re = sh.num_nontemp_gpr();
  1161.                 }
  1162.  
  1163.                 for (unsigned reg = rs; reg < re; ++reg) {
  1164.                         if (reg >= rb.size() || !rb.get(reg)) {
  1165.                                 // color found
  1166.                                 set_color_local(v, sel_chan(reg, chan));
  1167.                                 return true;
  1168.                         }
  1169.                 }
  1170.                 ++pass;
  1171.         }
  1172.  
  1173.         assert(!"recolor_local failed");
  1174.         return true;
  1175. }
  1176.  
  1177. void post_scheduler::emit_load_ar() {
  1178.  
  1179.         regmap = prev_regmap;
  1180.         alu.discard_current_group();
  1181.  
  1182.         alu_group_tracker &rt = alu.grp();
  1183.         alu_node *a = alu.create_ar_load();
  1184.  
  1185.         if (!rt.try_reserve(a)) {
  1186.                 sblog << "can't emit AR load : ";
  1187.                 dump::dump_op(a);
  1188.                 sblog << "\n";
  1189.         }
  1190.  
  1191.         alu.current_ar = 0;
  1192. }
  1193.  
  1194. bool post_scheduler::unmap_dst_val(value *d) {
  1195.  
  1196.         if (d == alu.current_ar) {
  1197.                 emit_load_ar();
  1198.                 return false;
  1199.         }
  1200.  
  1201.         if (d->is_prealloc()) {
  1202.                 sel_chan gpr = d->get_final_gpr();
  1203.                 rv_map::iterator F = regmap.find(gpr);
  1204.                 value *c = NULL;
  1205.                 if (F != regmap.end())
  1206.                         c = F->second;
  1207.  
  1208.                 if (c && c!=d && (!c->chunk || c->chunk != d->chunk)) {
  1209.                         PSC_DUMP(
  1210.                                 sblog << "dst value conflict : ";
  1211.                                 dump::dump_val(d);
  1212.                                 sblog << "   regmap contains ";
  1213.                                 dump::dump_val(c);
  1214.                                 sblog << "\n";
  1215.                         );
  1216.                         assert(!"scheduler error");
  1217.                         return false;
  1218.                 } else if (c) {
  1219.                         regmap.erase(F);
  1220.                 }
  1221.         }
  1222.         return true;
  1223. }
  1224.  
  1225. bool post_scheduler::unmap_dst(alu_node *n) {
  1226.         value *d = n->dst.empty() ? NULL : n->dst[0];
  1227.  
  1228.         if (!d)
  1229.                 return true;
  1230.  
  1231.         if (!d->is_rel()) {
  1232.                 if (d && d->is_any_reg()) {
  1233.  
  1234.                         if (d->is_AR()) {
  1235.                                 if (alu.current_ar != d) {
  1236.                                         sblog << "loading wrong ar value\n";
  1237.                                         assert(0);
  1238.                                 } else {
  1239.                                         alu.current_ar = NULL;
  1240.                                 }
  1241.  
  1242.                         } else if (d->is_any_gpr()) {
  1243.                                 if (!unmap_dst_val(d))
  1244.                                         return false;
  1245.                         }
  1246.                 }
  1247.         } else {
  1248.                 for (vvec::iterator I = d->mdef.begin(), E = d->mdef.end();
  1249.                                 I != E; ++I) {
  1250.                         d = *I;
  1251.                         if (!d)
  1252.                                 continue;
  1253.  
  1254.                         assert(d->is_any_gpr());
  1255.  
  1256.                         if (!unmap_dst_val(d))
  1257.                                 return false;
  1258.                 }
  1259.         }
  1260.         return true;
  1261. }
  1262.  
  1263. bool post_scheduler::map_src_val(value *v) {
  1264.  
  1265.         if (!v->is_prealloc())
  1266.                 return true;
  1267.  
  1268.         sel_chan gpr = v->get_final_gpr();
  1269.         rv_map::iterator F = regmap.find(gpr);
  1270.         value *c = NULL;
  1271.         if (F != regmap.end()) {
  1272.                 c = F->second;
  1273.                 if (!v->v_equal(c)) {
  1274.                         PSC_DUMP(
  1275.                                 sblog << "can't map src value ";
  1276.                                 dump::dump_val(v);
  1277.                                 sblog << ", regmap contains ";
  1278.                                 dump::dump_val(c);
  1279.                                 sblog << "\n";
  1280.                         );
  1281.                         return false;
  1282.                 }
  1283.         } else {
  1284.                 regmap.insert(std::make_pair(gpr, v));
  1285.         }
  1286.         return true;
  1287. }
  1288.  
  1289. bool post_scheduler::map_src_vec(vvec &vv, bool src) {
  1290.         for (vvec::iterator I = vv.begin(), E = vv.end(); I != E; ++I) {
  1291.                 value *v = *I;
  1292.                 if (!v)
  1293.                         continue;
  1294.  
  1295.                 if ((!v->is_any_gpr() || !v->is_fixed()) && !v->is_rel())
  1296.                         continue;
  1297.  
  1298.                 if (v->is_rel()) {
  1299.                         value *rel = v->rel;
  1300.                         assert(rel);
  1301.  
  1302.                         if (!rel->is_const()) {
  1303.                                 if (!map_src_vec(v->muse, true))
  1304.                                         return false;
  1305.  
  1306.                                 if (rel != alu.current_ar) {
  1307.                                         if (alu.current_ar) {
  1308.                                                 PSC_DUMP(
  1309.                                                         sblog << "  current_AR is " << *alu.current_ar
  1310.                                                                 << "  trying to use " << *rel << "\n";
  1311.                                                 );
  1312.                                                 return false;
  1313.                                         }
  1314.  
  1315.                                         alu.current_ar = rel;
  1316.  
  1317.                                         PSC_DUMP(
  1318.                                                 sblog << "  new current_AR assigned: " << *alu.current_ar
  1319.                                                         << "\n";
  1320.                                         );
  1321.                                 }
  1322.                         }
  1323.  
  1324.                 } else if (src) {
  1325.                         if (!map_src_val(v)) {
  1326.                                 return false;
  1327.                         }
  1328.                 }
  1329.         }
  1330.         return true;
  1331. }
  1332.  
  1333. bool post_scheduler::map_src(alu_node *n) {
  1334.         if (!map_src_vec(n->dst, false))
  1335.                 return false;
  1336.  
  1337.         if (!map_src_vec(n->src, true))
  1338.                 return false;
  1339.  
  1340.         return true;
  1341. }
  1342.  
  1343. void post_scheduler::dump_regmap() {
  1344.  
  1345.         sblog << "# REGMAP :\n";
  1346.  
  1347.         for(rv_map::iterator I = regmap.begin(), E = regmap.end(); I != E; ++I) {
  1348.                 sblog << "  # " << I->first << " => " << *(I->second) << "\n";
  1349.         }
  1350.  
  1351.         if (alu.current_ar)
  1352.                 sblog << "    current_AR: " << *alu.current_ar << "\n";
  1353.         if (alu.current_pr)
  1354.                 sblog << "    current_PR: " << *alu.current_pr << "\n";
  1355. }
  1356.  
  1357. void post_scheduler::recolor_locals() {
  1358.         alu_group_tracker &rt = alu.grp();
  1359.  
  1360.         for (unsigned s = 0; s < ctx.num_slots; ++s) {
  1361.                 alu_node *n = rt.slot(s);
  1362.                 if (n) {
  1363.                         value *d = n->dst[0];
  1364.                         if (d && d->is_sgpr() && !d->is_prealloc()) {
  1365.                                 recolor_local(d);
  1366.                         }
  1367.                 }
  1368.         }
  1369. }
  1370.  
  1371. // returns true if there are interferences
  1372. bool post_scheduler::check_interferences() {
  1373.  
  1374.         alu_group_tracker &rt = alu.grp();
  1375.  
  1376.         unsigned interf_slots;
  1377.  
  1378.         bool discarded = false;
  1379.  
  1380.         PSC_DUMP(
  1381.                         sblog << "check_interferences: before: \n";
  1382.         dump_regmap();
  1383.         );
  1384.  
  1385.         do {
  1386.  
  1387.                 interf_slots = 0;
  1388.  
  1389.                 for (unsigned s = 0; s < ctx.num_slots; ++s) {
  1390.                         alu_node *n = rt.slot(s);
  1391.                         if (n) {
  1392.                                 if (!unmap_dst(n)) {
  1393.                                         return true;
  1394.                                 }
  1395.                         }
  1396.                 }
  1397.  
  1398.                 for (unsigned s = 0; s < ctx.num_slots; ++s) {
  1399.                         alu_node *n = rt.slot(s);
  1400.                         if (n) {
  1401.                                 if (!map_src(n)) {
  1402.                                         interf_slots |= (1 << s);
  1403.                                 }
  1404.                         }
  1405.                 }
  1406.  
  1407.                 PSC_DUMP(
  1408.                                 for (unsigned i = 0; i < 5; ++i) {
  1409.                                         if (interf_slots & (1 << i)) {
  1410.                                                 sblog << "!!!!!! interf slot: " << i << "  : ";
  1411.                                                 dump::dump_op(rt.slot(i));
  1412.                                                 sblog << "\n";
  1413.                                         }
  1414.                                 }
  1415.                 );
  1416.  
  1417.                 if (!interf_slots)
  1418.                         break;
  1419.  
  1420.                 PSC_DUMP( sblog << "ci: discarding slots " << interf_slots << "\n"; );
  1421.  
  1422.                 rt.discard_slots(interf_slots, alu.conflict_nodes);
  1423.                 regmap = prev_regmap;
  1424.                 discarded = true;
  1425.  
  1426.         } while(1);
  1427.  
  1428.         PSC_DUMP(
  1429.                 sblog << "check_interferences: after: \n";
  1430.                 dump_regmap();
  1431.         );
  1432.  
  1433.         return discarded;
  1434. }
  1435.  
  1436. // add instruction(s) (alu_node or contents of alu_packed_node) to current group
  1437. // returns the number of added instructions on success
  1438. unsigned post_scheduler::try_add_instruction(node *n) {
  1439.  
  1440.         alu_group_tracker &rt = alu.grp();
  1441.  
  1442.         unsigned avail_slots = rt.avail_slots();
  1443.  
  1444.         if (n->is_alu_packed()) {
  1445.                 alu_packed_node *p = static_cast<alu_packed_node*>(n);
  1446.                 unsigned slots = p->get_slot_mask();
  1447.                 unsigned cnt = __builtin_popcount(slots);
  1448.  
  1449.                 if ((slots & avail_slots) != slots) {
  1450.                         PSC_DUMP( sblog << "   no slots \n"; );
  1451.                         return 0;
  1452.                 }
  1453.  
  1454.                 p->update_packed_items(ctx);
  1455.  
  1456.                 if (!rt.try_reserve(p)) {
  1457.                         PSC_DUMP( sblog << "   reservation failed \n"; );
  1458.                         return 0;
  1459.                 }
  1460.  
  1461.                 p->remove();
  1462.                 return cnt;
  1463.  
  1464.         } else {
  1465.                 alu_node *a = static_cast<alu_node*>(n);
  1466.                 value *d = a->dst.empty() ? NULL : a->dst[0];
  1467.  
  1468.                 if (d && d->is_special_reg()) {
  1469.                         assert((a->bc.op_ptr->flags & AF_MOVA) || d->is_geometry_emit());
  1470.                         d = NULL;
  1471.                 }
  1472.  
  1473.                 unsigned allowed_slots = ctx.alu_slots_mask(a->bc.op_ptr);
  1474.                 unsigned slot;
  1475.  
  1476.                 allowed_slots &= avail_slots;
  1477.  
  1478.                 if (!allowed_slots)
  1479.                         return 0;
  1480.  
  1481.                 if (d) {
  1482.                         slot = d->get_final_chan();
  1483.                         a->bc.dst_chan = slot;
  1484.                         allowed_slots &= (1 << slot) | 0x10;
  1485.                 } else {
  1486.                         if (a->bc.op_ptr->flags & AF_MOVA) {
  1487.                                 if (a->bc.slot_flags & AF_V)
  1488.                                         allowed_slots &= (1 << SLOT_X);
  1489.                                 else
  1490.                                         allowed_slots &= (1 << SLOT_TRANS);
  1491.                         }
  1492.                 }
  1493.  
  1494.                 // FIXME workaround for some problems with MULADD in trans slot on r700,
  1495.                 // (is it really needed on r600?)
  1496.                 if ((a->bc.op == ALU_OP3_MULADD || a->bc.op == ALU_OP3_MULADD_IEEE) &&
  1497.                                 !ctx.is_egcm()) {
  1498.                         allowed_slots &= 0x0F;
  1499.                 }
  1500.  
  1501.                 if (!allowed_slots) {
  1502.                         PSC_DUMP( sblog << "   no suitable slots\n"; );
  1503.                         return 0;
  1504.                 }
  1505.  
  1506.                 slot = __builtin_ctz(allowed_slots);
  1507.                 a->bc.slot = slot;
  1508.  
  1509.                 PSC_DUMP( sblog << "slot: " << slot << "\n"; );
  1510.  
  1511.                 if (!rt.try_reserve(a)) {
  1512.                         PSC_DUMP( sblog << "   reservation failed\n"; );
  1513.                         return 0;
  1514.                 }
  1515.  
  1516.                 a->remove();
  1517.                 return 1;
  1518.         }
  1519. }
  1520.  
  1521. bool post_scheduler::check_copy(node *n) {
  1522.         if (!n->is_copy_mov())
  1523.                 return false;
  1524.  
  1525.         value *s = n->src[0];
  1526.         value *d = n->dst[0];
  1527.  
  1528.         if (!s->is_sgpr() || !d->is_sgpr())
  1529.                 return false;
  1530.  
  1531.         if (!s->is_prealloc()) {
  1532.                 recolor_local(s);
  1533.  
  1534.                 if (!s->chunk || s->chunk != d->chunk)
  1535.                         return false;
  1536.         }
  1537.  
  1538.         if (s->gpr == d->gpr) {
  1539.  
  1540.                 PSC_DUMP(
  1541.                         sblog << "check_copy: ";
  1542.                         dump::dump_op(n);
  1543.                         sblog << "\n";
  1544.                 );
  1545.  
  1546.                 rv_map::iterator F = regmap.find(d->gpr);
  1547.                 bool gpr_free = (F == regmap.end());
  1548.  
  1549.                 if (d->is_prealloc()) {
  1550.                         if (gpr_free) {
  1551.                                 PSC_DUMP( sblog << "    copy not ready...\n";);
  1552.                                 return true;
  1553.                         }
  1554.  
  1555.                         value *rv = F->second;
  1556.                         if (rv != d && (!rv->chunk || rv->chunk != d->chunk)) {
  1557.                                 PSC_DUMP( sblog << "    copy not ready(2)...\n";);
  1558.                                 return true;
  1559.                         }
  1560.  
  1561.                         unmap_dst(static_cast<alu_node*>(n));
  1562.                 }
  1563.  
  1564.                 if (s->is_prealloc() && !map_src_val(s))
  1565.                         return true;
  1566.  
  1567.                 update_live(n, NULL);
  1568.  
  1569.                 release_src_values(n);
  1570.                 n->remove();
  1571.                 PSC_DUMP( sblog << "    copy coalesced...\n";);
  1572.                 return true;
  1573.         }
  1574.         return false;
  1575. }
  1576.  
  1577. void post_scheduler::dump_group(alu_group_tracker &rt) {
  1578.         for (unsigned i = 0; i < 5; ++i) {
  1579.                 node *n = rt.slot(i);
  1580.                 if (n) {
  1581.                         sblog << "slot " << i << " : ";
  1582.                         dump::dump_op(n);
  1583.                         sblog << "\n";
  1584.                 }
  1585.         }
  1586. }
  1587.  
  1588. void post_scheduler::process_ready_copies() {
  1589.  
  1590.         node *last;
  1591.  
  1592.         do {
  1593.                 last = ready_copies.back();
  1594.  
  1595.                 for (node_iterator N, I = ready_copies.begin(), E = ready_copies.end();
  1596.                                 I != E; I = N) {
  1597.                         N = I; ++N;
  1598.  
  1599.                         node *n = *I;
  1600.  
  1601.                         if (!check_copy(n)) {
  1602.                                 n->remove();
  1603.                                 ready.push_back(n);
  1604.                         }
  1605.                 }
  1606.         } while (last != ready_copies.back());
  1607.  
  1608.         update_local_interferences();
  1609. }
  1610.  
  1611.  
  1612. bool post_scheduler::prepare_alu_group() {
  1613.  
  1614.         alu_group_tracker &rt = alu.grp();
  1615.  
  1616.         unsigned i1 = 0;
  1617.  
  1618.         PSC_DUMP(
  1619.                 sblog << "prepare_alu_group: starting...\n";
  1620.                 dump_group(rt);
  1621.         );
  1622.  
  1623.         ready.append_from(&alu.conflict_nodes);
  1624.  
  1625.         // FIXME rework this loop
  1626.  
  1627.         do {
  1628.  
  1629.                 process_ready_copies();
  1630.  
  1631.                 ++i1;
  1632.  
  1633.                 for (node_iterator N, I = ready.begin(), E = ready.end(); I != E;
  1634.                                 I = N) {
  1635.                         N = I; ++N;
  1636.                         node *n = *I;
  1637.  
  1638.                         PSC_DUMP(
  1639.                                 sblog << "p_a_g: ";
  1640.                                 dump::dump_op(n);
  1641.                                 sblog << "\n";
  1642.                         );
  1643.  
  1644.  
  1645.                         unsigned cnt = try_add_instruction(n);
  1646.  
  1647.                         if (!cnt)
  1648.                                 continue;
  1649.  
  1650.                         PSC_DUMP(
  1651.                                 sblog << "current group:\n";
  1652.                                 dump_group(rt);
  1653.                         );
  1654.  
  1655.                         if (rt.inst_count() == ctx.num_slots) {
  1656.                                 PSC_DUMP( sblog << " all slots used\n"; );
  1657.                                 break;
  1658.                         }
  1659.                 }
  1660.  
  1661.                 if (!check_interferences())
  1662.                         break;
  1663.  
  1664.                 // don't try to add more instructions to the group with mova if this
  1665.                 // can lead to breaking clause slot count limit - we don't want mova to
  1666.                 // end up in the end of the new clause instead of beginning of the
  1667.                 // current clause.
  1668.                 if (rt.has_ar_load() && alu.total_slots() > 121)
  1669.                         break;
  1670.  
  1671.                 if (rt.inst_count() && i1 > 50)
  1672.                         break;
  1673.  
  1674.                 regmap = prev_regmap;
  1675.  
  1676.         } while (1);
  1677.  
  1678.         PSC_DUMP(
  1679.                 sblog << " prepare_alu_group done, " << rt.inst_count()
  1680.                   << " slot(s) \n";
  1681.  
  1682.                 sblog << "$$$$$$$$PAG i1=" << i1
  1683.                                 << "  ready " << ready.count()
  1684.                                 << "  pending " << pending.count()
  1685.                                 << "  conflicting " << alu.conflict_nodes.count()
  1686.                                 <<"\n";
  1687.  
  1688.         );
  1689.  
  1690.         return rt.inst_count();
  1691. }
  1692.  
  1693. void post_scheduler::release_src_values(node* n) {
  1694.         release_src_vec(n->src, true);
  1695.         release_src_vec(n->dst, false);
  1696. }
  1697.  
  1698. void post_scheduler::release_op(node *n) {
  1699.         PSC_DUMP(
  1700.                 sblog << "release_op ";
  1701.                 dump::dump_op(n);
  1702.                 sblog << "\n";
  1703.         );
  1704.  
  1705.         n->remove();
  1706.  
  1707.         if (n->is_copy_mov()) {
  1708.                 ready_copies.push_back(n);
  1709.         } else if (n->is_mova() || n->is_pred_set()) {
  1710.                 ready.push_front(n);
  1711.         } else {
  1712.                 ready.push_back(n);
  1713.         }
  1714. }
  1715.  
  1716. void post_scheduler::release_src_val(value *v) {
  1717.         node *d = v->any_def();
  1718.         if (d) {
  1719.                 if (!--ucm[d])
  1720.                         release_op(d);
  1721.         }
  1722. }
  1723.  
  1724. void post_scheduler::release_src_vec(vvec& vv, bool src) {
  1725.  
  1726.         for (vvec::iterator I = vv.begin(), E = vv.end(); I != E; ++I) {
  1727.                 value *v = *I;
  1728.                 if (!v || v->is_readonly())
  1729.                         continue;
  1730.  
  1731.                 if (v->is_rel()) {
  1732.                         release_src_val(v->rel);
  1733.                         release_src_vec(v->muse, true);
  1734.  
  1735.                 } else if (src) {
  1736.                         release_src_val(v);
  1737.                 }
  1738.         }
  1739. }
  1740.  
  1741. void literal_tracker::reset() {
  1742.         memset(lt, 0, sizeof(lt));
  1743.         memset(uc, 0, sizeof(uc));
  1744. }
  1745.  
  1746. void rp_gpr_tracker::reset() {
  1747.         memset(rp, 0, sizeof(rp));
  1748.         memset(uc, 0, sizeof(uc));
  1749. }
  1750.  
  1751. void rp_kcache_tracker::reset() {
  1752.         memset(rp, 0, sizeof(rp));
  1753.         memset(uc, 0, sizeof(uc));
  1754. }
  1755.  
  1756. void alu_kcache_tracker::reset() {
  1757.         memset(kc, 0, sizeof(kc));
  1758.         lines.clear();
  1759. }
  1760.  
  1761. void alu_clause_tracker::reset() {
  1762.         group = 0;
  1763.         slot_count = 0;
  1764.         grp0.reset();
  1765.         grp1.reset();
  1766. }
  1767.  
  1768. alu_clause_tracker::alu_clause_tracker(shader &sh)
  1769.         : sh(sh), kt(sh.get_ctx().hw_class), slot_count(),
  1770.           grp0(sh), grp1(sh),
  1771.           group(), clause(),
  1772.           push_exec_mask(),
  1773.           current_ar(), current_pr() {}
  1774.  
  1775. void alu_clause_tracker::emit_group() {
  1776.  
  1777.         assert(grp().inst_count());
  1778.  
  1779.         alu_group_node *g = grp().emit();
  1780.  
  1781.         if (grp().has_update_exec_mask()) {
  1782.                 assert(!push_exec_mask);
  1783.                 push_exec_mask = true;
  1784.         }
  1785.  
  1786.         assert(g);
  1787.  
  1788.         if (!clause) {
  1789.                 clause = sh.create_clause(NST_ALU_CLAUSE);
  1790.         }
  1791.  
  1792.         clause->push_front(g);
  1793.  
  1794.         slot_count += grp().slot_count();
  1795.  
  1796.         new_group();
  1797.  
  1798.         PSC_DUMP( sblog << "   #### group emitted\n"; );
  1799. }
  1800.  
  1801. void alu_clause_tracker::emit_clause(container_node *c) {
  1802.         assert(clause);
  1803.  
  1804.         kt.init_clause(clause->bc);
  1805.  
  1806.         assert(!current_ar);
  1807.         assert(!current_pr);
  1808.  
  1809.         if (push_exec_mask)
  1810.                 clause->bc.set_op(CF_OP_ALU_PUSH_BEFORE);
  1811.  
  1812.         c->push_front(clause);
  1813.  
  1814.         clause = NULL;
  1815.         push_exec_mask = false;
  1816.         slot_count = 0;
  1817.         kt.reset();
  1818.  
  1819.         PSC_DUMP( sblog << "######### ALU clause emitted\n"; );
  1820. }
  1821.  
  1822. bool alu_clause_tracker::check_clause_limits() {
  1823.  
  1824.         alu_group_tracker &gt = grp();
  1825.  
  1826.         unsigned slots = gt.slot_count();
  1827.  
  1828.         // reserving slots to load AR and PR values
  1829.         unsigned reserve_slots = (current_ar ? 1 : 0) + (current_pr ? 1 : 0);
  1830.  
  1831.         if (slot_count + slots > MAX_ALU_SLOTS - reserve_slots)
  1832.                 return false;
  1833.  
  1834.         if (!kt.try_reserve(gt))
  1835.                 return false;
  1836.  
  1837.         return true;
  1838. }
  1839.  
  1840. void alu_clause_tracker::new_group() {
  1841.         group = !group;
  1842.         grp().reset();
  1843. }
  1844.  
  1845. bool alu_clause_tracker::is_empty() {
  1846.         return clause == NULL;
  1847. }
  1848.  
  1849. void literal_tracker::init_group_literals(alu_group_node* g) {
  1850.  
  1851.         g->literals.clear();
  1852.         for (unsigned i = 0; i < 4; ++i) {
  1853.                 if (!lt[i])
  1854.                         break;
  1855.  
  1856.                 g->literals.push_back(lt[i]);
  1857.  
  1858.                 PSC_DUMP(
  1859.                         sblog << "literal emitted: " << lt[i].f;
  1860.                         sblog.print_zw_hex(lt[i].u, 8);
  1861.                         sblog << "   " << lt[i].i << "\n";
  1862.                 );
  1863.         }
  1864. }
  1865.  
  1866. bool alu_kcache_tracker::try_reserve(alu_group_tracker& gt) {
  1867.         rp_kcache_tracker &kt = gt.kcache();
  1868.  
  1869.         if (!kt.num_sels())
  1870.                 return true;
  1871.  
  1872.         sb_set<unsigned> group_lines;
  1873.  
  1874.         unsigned nl = kt.get_lines(group_lines);
  1875.         assert(nl);
  1876.  
  1877.         sb_set<unsigned> clause_lines(lines);
  1878.         lines.add_set(group_lines);
  1879.  
  1880.         if (clause_lines.size() == lines.size())
  1881.                 return true;
  1882.  
  1883.         if (update_kc())
  1884.                 return true;
  1885.  
  1886.         lines = clause_lines;
  1887.  
  1888.         return false;
  1889. }
  1890.  
  1891. unsigned rp_kcache_tracker::get_lines(kc_lines& lines) {
  1892.         unsigned cnt = 0;
  1893.  
  1894.         for (unsigned i = 0; i < sel_count; ++i) {
  1895.                 unsigned line = rp[i];
  1896.  
  1897.                 if (!line)
  1898.                         return cnt;
  1899.  
  1900.                 --line;
  1901.                 line = (sel_count == 2) ? line >> 5 : line >> 6;
  1902.  
  1903.                 if (lines.insert(line).second)
  1904.                         ++cnt;
  1905.         }
  1906.         return cnt;
  1907. }
  1908.  
  1909. bool alu_kcache_tracker::update_kc() {
  1910.         unsigned c = 0;
  1911.  
  1912.         bc_kcache old_kc[4];
  1913.         memcpy(old_kc, kc, sizeof(kc));
  1914.  
  1915.         for (kc_lines::iterator I = lines.begin(), E = lines.end(); I != E; ++I) {
  1916.                 unsigned line = *I;
  1917.                 unsigned bank = line >> 8;
  1918.  
  1919.                 line &= 0xFF;
  1920.  
  1921.                 if (c && (bank == kc[c-1].bank) && (kc[c-1].addr + 1 == line))
  1922.                         ++kc[c-1].mode;
  1923.                 else {
  1924.                         if (c == max_kcs) {
  1925.                                 memcpy(kc, old_kc, sizeof(kc));
  1926.                                 return false;
  1927.                         }
  1928.  
  1929.                         kc[c].mode = KC_LOCK_1;
  1930.  
  1931.                         kc[c].bank = bank;
  1932.                         kc[c].addr = line;
  1933.                         ++c;
  1934.                 }
  1935.         }
  1936.         return true;
  1937. }
  1938.  
  1939. alu_node* alu_clause_tracker::create_ar_load() {
  1940.         alu_node *a = sh.create_alu();
  1941.  
  1942.         // FIXME use MOVA_GPR on R6xx
  1943.  
  1944.         if (sh.get_ctx().uses_mova_gpr) {
  1945.                 a->bc.set_op(ALU_OP1_MOVA_GPR_INT);
  1946.                 a->bc.slot = SLOT_TRANS;
  1947.         } else {
  1948.                 a->bc.set_op(ALU_OP1_MOVA_INT);
  1949.                 a->bc.slot = SLOT_X;
  1950.         }
  1951.  
  1952.         a->dst.resize(1);
  1953.         a->src.push_back(current_ar);
  1954.  
  1955.         PSC_DUMP(
  1956.                 sblog << "created AR load: ";
  1957.                 dump::dump_op(a);
  1958.                 sblog << "\n";
  1959.         );
  1960.  
  1961.         return a;
  1962. }
  1963.  
  1964. void alu_clause_tracker::discard_current_group() {
  1965.         PSC_DUMP( sblog << "act::discard_current_group\n"; );
  1966.         grp().discard_all_slots(conflict_nodes);
  1967. }
  1968.  
  1969. void rp_gpr_tracker::dump() {
  1970.         sblog << "=== gpr_tracker dump:\n";
  1971.         for (int c = 0; c < 3; ++c) {
  1972.                 sblog << "cycle " << c << "      ";
  1973.                 for (int h = 0; h < 4; ++h) {
  1974.                         sblog << rp[c][h] << ":" << uc[c][h] << "   ";
  1975.                 }
  1976.                 sblog << "\n";
  1977.         }
  1978. }
  1979.  
  1980. } // namespace r600_sb
  1981.