src/mesa/drivers/dri/i965/brw_fs_copy_propagation.cpp

   1 /*
   2  * Copyright © 2012 Intel Corporation
   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 /** @file brw_fs_copy_propagation.cpp
  25  *
  26  * Support for global copy propagation in two passes: A local pass that does
  27  * intra-block copy (and constant) propagation, and a global pass that uses
  28  * dataflow analysis on the copies available at the end of each block to re-do
  29  * local copy propagation with more copies available.
  30  *
  31  * See Muchnik's Advanced Compiler Design and Implementation, section
  32  * 12.5 (p356).
  33  */
  34
  35 #define ACP_HASH_SIZE 16
  36
  37 #include "brw_fs.h"
  38 #include "brw_cfg.h"
  39
  40 namespace { /* avoid conflict with opt_copy_propagation_elements */
  41 struct acp_entry : public exec_node {
  42    fs_reg dst;
  43    fs_reg src;
  44 };
  45
  46 struct block_data {
  47    /**
  48     * Which entries in the fs_copy_prop_dataflow acp table are live at the
  49     * start of this block.  This is the useful output of the analysis, since
  50     * it lets us plug those into the local copy propagation on the second
  51     * pass.
  52     */
  53    bool *livein;
  54
  55    /**
  56     * Which entries in the fs_copy_prop_dataflow acp table are live at the end
  57     * of this block.  This is done in initial setup from the per-block acps
  58     * returned by the first local copy prop pass.
  59     */
  60    bool *liveout;
  61
  62    /**
  63     * Which entries in the fs_copy_prop_dataflow acp table are killed over the
  64     * course of this block.
  65     */
  66    bool *kill;
  67 };
  68
  69 class fs_copy_prop_dataflow
  70 {
  71 public:
  72    fs_copy_prop_dataflow(void *mem_ctx, cfg_t *cfg,
  73                          exec_list *out_acp[ACP_HASH_SIZE]);
  74
  75    void setup_kills();
  76    void run();
  77
  78    void *mem_ctx;
  79    cfg_t *cfg;
  80
  81    acp_entry **acp;
  82    int num_acp;
  83
  84   struct block_data *bd;
  85 };
  86 } /* anonymous namespace */
  87
  88 fs_copy_prop_dataflow::fs_copy_prop_dataflow(void *mem_ctx, cfg_t *cfg,
  89                                              exec_list *out_acp[ACP_HASH_SIZE])
  90    : mem_ctx(mem_ctx), cfg(cfg)
  91 {
  92    bd = rzalloc_array(mem_ctx, struct block_data, cfg->num_blocks);
  93
  94    num_acp = 0;
  95    for (int b = 0; b < cfg->num_blocks; b++) {
  96       for (int i = 0; i < ACP_HASH_SIZE; i++) {
  97          foreach_list(entry_node, &out_acp[b][i]) {
  98             num_acp++;
  99          }
 100       }
 101    }
 102
 103    acp = rzalloc_array(mem_ctx, struct acp_entry *, num_acp);
 104
 105    int next_acp = 0;
 106    for (int b = 0; b < cfg->num_blocks; b++) {
 107       bd[b].livein = rzalloc_array(bd, bool, num_acp);
 108       bd[b].liveout = rzalloc_array(bd, bool, num_acp);
 109       bd[b].kill = rzalloc_array(bd, bool, num_acp);
 110
 111       for (int i = 0; i < ACP_HASH_SIZE; i++) {
 112          foreach_list(entry_node, &out_acp[b][i]) {
 113             acp_entry *entry = (acp_entry *)entry_node;
 114
 115             acp[next_acp] = entry;
 116             bd[b].liveout[next_acp] = true;
 117             next_acp++;
 118          }
 119       }
 120    }
 121
 122    assert(next_acp == num_acp);
 123
 124    setup_kills();
 125    run();
 126 }
 127
 128 /**
 129  * Walk the set of instructions in the block, marking which entries in the acp
 130  * are killed by the block.
 131  */
 132 void
 133 fs_copy_prop_dataflow::setup_kills()
 134 {
 135    for (int b = 0; b < cfg->num_blocks; b++) {
 136       bblock_t *block = cfg->blocks[b];
 137
 138       for (fs_inst *inst = (fs_inst *)block->start;
 139            inst != block->end->next;
 140            inst = (fs_inst *)inst->next) {
 141          if (inst->dst.file != GRF)
 142             continue;
 143
 144          for (int i = 0; i < num_acp; i++) {
 145             if (inst->overwrites_reg(acp[i]->dst) ||
 146                 inst->overwrites_reg(acp[i]->src)) {
 147                bd[b].kill[i] = true;
 148             }
 149          }
 150       }
 151    }
 152 }
 153
 154 /**
 155  * Walk the set of instructions in the block, marking which entries in the acp
 156  * are killed by the block.
 157  */
 158 void
 159 fs_copy_prop_dataflow::run()
 160 {
 161    bool cont = true;
 162
 163    while (cont) {
 164       cont = false;
 165
 166       for (int b = 0; b < cfg->num_blocks; b++) {
 167          for (int i = 0; i < num_acp; i++) {
 168             if (!bd[b].liveout[i]) {
 169                /* Update liveout */
 170                if (bd[b].livein[i] && !bd[b].kill[i]) {
 171                   bd[b].liveout[i] = true;
 172                   cont = true;
 173                }
 174             }
 175
 176             if (!bd[b].livein[i]) {
 177                /* Update livein: if it's live at the end of all parents, it's
 178                 * live at our start.
 179                 */
 180                bool add = true;
 181                foreach_list(block_node, &cfg->blocks[b]->parents) {
 182                   bblock_link *link = (bblock_link *)block_node;
 183                   bblock_t *block = link->block;
 184                   if (!bd[block->block_num].liveout[i]) {
 185                      add = false;
 186                      break;
 187                   }
 188                }
 189                if (add) {
 190                   bd[b].livein[i] = true;
 191                   cont = true;
 192                }
 193             }
 194          }
 195       }
 196    }
 197 }
 198
 199 bool
 200 fs_visitor::try_copy_propagate(fs_inst *inst, int arg, acp_entry *entry)
 201 {
 202    if (entry->src.file == IMM)
 203       return false;
 204
 205    if (inst->src[arg].file != entry->dst.file ||
 206        inst->src[arg].reg != entry->dst.reg ||
 207        inst->src[arg].reg_offset != entry->dst.reg_offset) {
 208       return false;
 209    }
 210
 211    /* See resolve_ud_negate() and comment in brw_fs_emit.cpp. */
 212    if (inst->conditional_mod &&
 213        inst->src[arg].type == BRW_REGISTER_TYPE_UD &&
 214        entry->src.negate)
 215       return false;
 216
 217    bool has_source_modifiers = entry->src.abs || entry->src.negate;
 218
 219    if ((has_source_modifiers || entry->src.file == UNIFORM ||
 220         entry->src.smear != -1) && !can_do_source_mods(inst))
 221       return false;
 222
 223    inst->src[arg].file = entry->src.file;
 224    inst->src[arg].reg = entry->src.reg;
 225    inst->src[arg].reg_offset = entry->src.reg_offset;
 226    if (entry->src.smear != -1)
 227       inst->src[arg].smear = entry->src.smear;
 228
 229    if (!inst->src[arg].abs) {
 230       inst->src[arg].abs = entry->src.abs;
 231       inst->src[arg].negate ^= entry->src.negate;
 232    }
 233
 234    return true;
 235 }
 236
 237
 238 bool
 239 fs_visitor::try_constant_propagate(fs_inst *inst, acp_entry *entry)
 240 {
 241    bool progress = false;
 242
 243    if (entry->src.file != IMM)
 244       return false;
 245
 246    for (int i = 2; i >= 0; i--) {
 247       if (inst->src[i].file != entry->dst.file ||
 248           inst->src[i].reg != entry->dst.reg ||
 249           inst->src[i].reg_offset != entry->dst.reg_offset)
 250          continue;
 251
 252       /* Don't bother with cases that should have been taken care of by the
 253        * GLSL compiler's constant folding pass.
 254        */
 255       if (inst->src[i].negate || inst->src[i].abs)
 256          continue;
 257
 258       switch (inst->opcode) {
 259       case BRW_OPCODE_MOV:
 260          inst->src[i] = entry->src;
 261          progress = true;
 262          break;
 263
 264       case BRW_OPCODE_MUL:
 265       case BRW_OPCODE_ADD:
 266          if (i == 1) {
 267             inst->src[i] = entry->src;
 268             progress = true;
 269          } else if (i == 0 && inst->src[1].file != IMM) {
 270             /* Fit this constant in by commuting the operands.
 271              * Exception: we can't do this for 32-bit integer MUL
 272              * because it's asymmetric.
 273              */
 274             if (inst->opcode == BRW_OPCODE_MUL &&
 275                 (inst->src[1].type == BRW_REGISTER_TYPE_D ||
 276                  inst->src[1].type == BRW_REGISTER_TYPE_UD))
 277                break;
 278             inst->src[0] = inst->src[1];
 279             inst->src[1] = entry->src;
 280             progress = true;
 281          }
 282          break;
 283
 284       case BRW_OPCODE_CMP:
 285       case BRW_OPCODE_IF:
 286          if (i == 1) {
 287             inst->src[i] = entry->src;
 288             progress = true;
 289          } else if (i == 0 && inst->src[1].file != IMM) {
 290             uint32_t new_cmod;
 291
 292             new_cmod = brw_swap_cmod(inst->conditional_mod);
 293             if (new_cmod != ~0u) {
 294                /* Fit this constant in by swapping the operands and
 295                 * flipping the test
 296                 */
 297                inst->src[0] = inst->src[1];
 298                inst->src[1] = entry->src;
 299                inst->conditional_mod = new_cmod;
 300                progress = true;
 301             }
 302          }
 303          break;
 304
 305       case BRW_OPCODE_SEL:
 306          if (i == 1) {
 307             inst->src[i] = entry->src;
 308             progress = true;
 309          } else if (i == 0 && inst->src[1].file != IMM) {
 310             inst->src[0] = inst->src[1];
 311             inst->src[1] = entry->src;
 312
 313             /* If this was predicated, flipping operands means
 314              * we also need to flip the predicate.
 315              */
 316             if (inst->conditional_mod == BRW_CONDITIONAL_NONE) {
 317                inst->predicate_inverse =
 318                   !inst->predicate_inverse;
 319             }
 320             progress = true;
 321          }
 322          break;
 323
 324       case SHADER_OPCODE_RCP:
 325          /* The hardware doesn't do math on immediate values
 326           * (because why are you doing that, seriously?), but
 327           * the correct answer is to just constant fold it
 328           * anyway.
 329           */
 330          assert(i == 0);
 331          if (inst->src[0].imm.f != 0.0f) {
 332             inst->opcode = BRW_OPCODE_MOV;
 333             inst->src[0] = entry->src;
 334             inst->src[0].imm.f = 1.0f / inst->src[0].imm.f;
 335             progress = true;
 336          }
 337          break;
 338
 339       case FS_OPCODE_UNIFORM_PULL_CONSTANT_LOAD:
 340          inst->src[i] = entry->src;
 341          progress = true;
 342          break;
 343
 344       default:
 345          break;
 346       }
 347    }
 348
 349    return progress;
 350 }
 351 /* Walks a basic block and does copy propagation on it using the acp
 352  * list.
 353  */
 354 bool
 355 fs_visitor::opt_copy_propagate_local(void *mem_ctx, bblock_t *block,
 356                                      exec_list *acp)
 357 {
 358    bool progress = false;
 359
 360    for (fs_inst *inst = (fs_inst *)block->start;
 361         inst != block->end->next;
 362         inst = (fs_inst *)inst->next) {
 363
 364       /* Try propagating into this instruction. */
 365       for (int i = 0; i < 3; i++) {
 366          if (inst->src[i].file != GRF)
 367             continue;
 368
 369          foreach_list(entry_node, &acp[inst->src[i].reg % ACP_HASH_SIZE]) {
 370             acp_entry *entry = (acp_entry *)entry_node;
 371
 372             if (try_constant_propagate(inst, entry))
 373                progress = true;
 374
 375             if (try_copy_propagate(inst, i, entry))
 376                progress = true;
 377          }
 378       }
 379
 380       /* kill the destination from the ACP */
 381       if (inst->dst.file == GRF) {
 382          foreach_list_safe(entry_node, &acp[inst->dst.reg % ACP_HASH_SIZE]) {
 383             acp_entry *entry = (acp_entry *)entry_node;
 384
 385             if (inst->overwrites_reg(entry->dst)) {
 386                entry->remove();
 387             }
 388          }
 389
 390          /* Oops, we only have the chaining hash based on the destination, not
 391           * the source, so walk across the entire table.
 392           */
 393          for (int i = 0; i < ACP_HASH_SIZE; i++) {
 394             foreach_list_safe(entry_node, &acp[i]) {
 395                acp_entry *entry = (acp_entry *)entry_node;
 396                if (inst->overwrites_reg(entry->src))
 397                   entry->remove();
 398             }
 399          }
 400       }
 401
 402       /* If this instruction's source could potentially be folded into the
 403        * operand of another instruction, add it to the ACP.
 404        */
 405       if (inst->opcode == BRW_OPCODE_MOV &&
 406           inst->dst.file == GRF &&
 407           ((inst->src[0].file == GRF &&
 408             (inst->src[0].reg != inst->dst.reg ||
 409              inst->src[0].reg_offset != inst->dst.reg_offset)) ||
 410            inst->src[0].file == UNIFORM ||
 411            inst->src[0].file == IMM) &&
 412           inst->src[0].type == inst->dst.type &&
 413           !inst->saturate &&
 414           !inst->predicate &&
 415           !inst->force_uncompressed &&
 416           !inst->force_sechalf) {
 417          acp_entry *entry = ralloc(mem_ctx, acp_entry);
 418          entry->dst = inst->dst;
 419          entry->src = inst->src[0];
 420          acp[entry->dst.reg % ACP_HASH_SIZE].push_tail(entry);
 421       }
 422    }
 423
 424    return progress;
 425 }
 426
 427 bool
 428 fs_visitor::opt_copy_propagate()
 429 {
 430    bool progress = false;
 431    void *mem_ctx = ralloc_context(this->mem_ctx);
 432    cfg_t cfg(this);
 433    exec_list *out_acp[cfg.num_blocks];
 434    for (int i = 0; i < cfg.num_blocks; i++)
 435       out_acp[i] = new exec_list [ACP_HASH_SIZE];
 436
 437    /* First, walk through each block doing local copy propagation and getting
 438     * the set of copies available at the end of the block.
 439     */
 440    for (int b = 0; b < cfg.num_blocks; b++) {
 441       bblock_t *block = cfg.blocks[b];
 442
 443       progress = opt_copy_propagate_local(mem_ctx, block,
 444                                           out_acp[b]) || progress;
 445    }
 446
 447    /* Do dataflow analysis for those available copies. */
 448    fs_copy_prop_dataflow dataflow(mem_ctx, &cfg, out_acp);
 449
 450    /* Next, re-run local copy propagation, this time with the set of copies
 451     * provided by the dataflow analysis available at the start of a block.
 452     */
 453    for (int b = 0; b < cfg.num_blocks; b++) {
 454       bblock_t *block = cfg.blocks[b];
 455       exec_list in_acp[ACP_HASH_SIZE];
 456
 457       for (int i = 0; i < dataflow.num_acp; i++) {
 458          if (dataflow.bd[b].livein[i]) {
 459             struct acp_entry *entry = dataflow.acp[i];
 460             in_acp[entry->dst.reg % ACP_HASH_SIZE].push_tail(entry);
 461          }
 462       }
 463
 464       progress = opt_copy_propagate_local(mem_ctx, block, in_acp) || progress;
 465    }
 466
 467    for (int i = 0; i < cfg.num_blocks; i++)
 468       delete [] out_acp[i];
 469    ralloc_free(mem_ctx);
 470
 471    if (progress)
 472       live_intervals_valid = false;
 473
 474    return progress;
 475 }