Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  1. /*
  2.  * Copyright © 2014 Broadcom
  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.  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
  8.  * and/or sell copies of the Software, and to permit persons to whom the
  9.  * 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 NONINFRINGEMENT.  IN NO EVENT SHALL
  18.  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19.  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  20.  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
  21.  * IN THE SOFTWARE.
  22.  */
  23.  
  24. /**
  25.  * @file vc4_opt_cse.c
  26.  *
  27.  * Implements CSE for QIR without control flow.
  28.  *
  29.  * For each operation that writes a destination (and isn't just a MOV), put it
  30.  * in the hash table of all instructions that do so.  When faced with another
  31.  * one, look it up in the hash table by its opcode and operands.  If there's
  32.  * an entry in the table, then just reuse the entry's destination as the
  33.  * source of a MOV instead of reproducing the computation.  That MOV will then
  34.  * get cleaned up by copy propagation.
  35.  */
  36.  
  37. #include "vc4_qir.h"
  38.  
  39. #include "util/hash_table.h"
  40. #include "util/ralloc.h"
  41.  
  42. static bool debug;
  43.  
  44. struct inst_key {
  45.         enum qop op;
  46.         struct qreg src[4];
  47.         /**
  48.          * If the instruction depends on the flags, how many SFs have been
  49.          * seen before this instruction, or if it depends on r4, how many r4
  50.          * writes have been seen.
  51.          */
  52.         uint32_t implicit_arg_update_count;
  53. };
  54.  
  55. static bool
  56. inst_key_equals(const void *a, const void *b)
  57. {
  58.         const struct inst_key *key_a = a;
  59.         const struct inst_key *key_b = b;
  60.  
  61.         return memcmp(key_a, key_b, sizeof(*key_a)) == 0;
  62. }
  63.  
  64. static struct qinst *
  65. vc4_find_cse(struct vc4_compile *c, struct hash_table *ht,
  66.              struct qinst *inst, uint32_t sf_count,
  67.              uint32_t r4_count)
  68. {
  69.         if (inst->dst.file != QFILE_TEMP ||
  70.             inst->op == QOP_MOV ||
  71.             qir_get_op_nsrc(inst->op) > 4) {
  72.                 return NULL;
  73.         }
  74.  
  75.         struct inst_key key;
  76.         memset(&key, 0, sizeof(key));
  77.         key.op = inst->op;
  78.         memcpy(key.src, inst->src,
  79.                qir_get_op_nsrc(inst->op) * sizeof(key.src[0]));
  80.         if (qir_depends_on_flags(inst))
  81.                 key.implicit_arg_update_count = sf_count;
  82.         if (qir_reads_r4(inst))
  83.                 key.implicit_arg_update_count = r4_count;
  84.  
  85.         uint32_t hash = _mesa_hash_data(&key, sizeof(key));
  86.         struct hash_entry *entry =
  87.                 _mesa_hash_table_search_pre_hashed(ht, hash, &key);
  88.  
  89.         if (entry) {
  90.                 if (debug) {
  91.                         fprintf(stderr, "CSE found match:\n");
  92.  
  93.                         fprintf(stderr, "  Original inst: ");
  94.                         qir_dump_inst(c, entry->data);
  95.                         fprintf(stderr, "\n");
  96.  
  97.                         fprintf(stderr, "  Our inst:      ");
  98.                         qir_dump_inst(c, inst);
  99.                         fprintf(stderr, "\n");
  100.                 }
  101.  
  102.                 return entry->data;
  103.         }
  104.  
  105.         struct inst_key *alloc_key = ralloc(ht, struct inst_key);
  106.         if (!alloc_key)
  107.                 return NULL;
  108.         memcpy(alloc_key, &key, sizeof(*alloc_key));
  109.         _mesa_hash_table_insert_pre_hashed(ht, hash, alloc_key, inst);
  110.  
  111.         if (debug) {
  112.                 fprintf(stderr, "Added to CSE HT: ");
  113.                 qir_dump_inst(c, inst);
  114.                 fprintf(stderr, "\n");
  115.         }
  116.  
  117.         return NULL;
  118. }
  119.  
  120. bool
  121. qir_opt_cse(struct vc4_compile *c)
  122. {
  123.         bool progress = false;
  124.         struct simple_node *node, *t;
  125.         uint32_t sf_count = 0, r4_count = 0;
  126.  
  127.         struct hash_table *ht = _mesa_hash_table_create(NULL, NULL,
  128.                                                         inst_key_equals);
  129.         if (!ht)
  130.                 return false;
  131.  
  132.         foreach_s(node, t, &c->instructions) {
  133.                 struct qinst *inst = (struct qinst *)node;
  134.  
  135.                 if (qir_has_side_effects(c, inst) ||
  136.                     qir_has_side_effect_reads(c, inst)) {
  137.                         continue;
  138.                 }
  139.  
  140.                 if (inst->sf) {
  141.                         sf_count++;
  142.                 } else {
  143.                         struct qinst *cse = vc4_find_cse(c, ht, inst,
  144.                                                          sf_count, r4_count);
  145.                         if (cse) {
  146.                                 inst->src[0] = cse->dst;
  147.                                 for (int i = 1; i < qir_get_op_nsrc(inst->op);
  148.                                      i++)
  149.                                         inst->src[i] = c->undef;
  150.                                 inst->op = QOP_MOV;
  151.                                 progress = true;
  152.  
  153.                                 if (debug) {
  154.                                         fprintf(stderr, "  Turned into:   ");
  155.                                         qir_dump_inst(c, inst);
  156.                                         fprintf(stderr, "\n");
  157.                                 }
  158.                         }
  159.                 }
  160.  
  161.                 if (qir_writes_r4(inst))
  162.                         r4_count++;
  163.         }
  164.  
  165.         ralloc_free(ht);
  166.  
  167.         return progress;
  168. }
  169.