src/gallium/drivers/vc4/vc4_opt_cse.c

   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 QOP_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(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(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         struct qinst *last_sf = NULL;
 126         uint32_t sf_count = 0, r4_count = 0;
 127
 128         struct hash_table *ht = _mesa_hash_table_create(NULL, 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                         if (inst->op == QOP_TLB_DISCARD_SETUP)
 137                                 last_sf = NULL;
 138                         continue;
 139                 }
 140
 141                 if (inst->op == QOP_SF) {
 142                         if (last_sf &&
 143                             qir_reg_equals(last_sf->src[0], inst->src[0])) {
 144                                 if (debug) {
 145                                         fprintf(stderr,
 146                                                 "Removing redundant SF: ");
 147                                         qir_dump_inst(c, inst);
 148                                         fprintf(stderr, "\n");
 149                                 }
 150                                 qir_remove_instruction(inst);
 151                                 progress = true;
 152                                 continue;
 153                         } else {
 154                                 last_sf = inst;
 155                                 sf_count++;
 156                         }
 157                 } else {
 158                         struct qinst *cse = vc4_find_cse(c, ht, inst,
 159                                                          sf_count, r4_count);
 160                         if (cse) {
 161                                 inst->src[0] = cse->dst;
 162                                 for (int i = 1; i < qir_get_op_nsrc(inst->op);
 163                                      i++)
 164                                         inst->src[i] = c->undef;
 165                                 inst->op = QOP_MOV;
 166                                 progress = true;
 167
 168                                 if (debug) {
 169                                         fprintf(stderr, "  Turned into:   ");
 170                                         qir_dump_inst(c, inst);
 171                                         fprintf(stderr, "\n");
 172                                 }
 173                         }
 174                 }
 175
 176                 if (qir_writes_r4(inst))
 177                         r4_count++;
 178         }
 179
 180         ralloc_free(ht);
 181
 182         return progress;
 183 }