src/amd/compiler/aco_dead_code_analysis.cpp

   1 /*
   2  * Copyright © 2019 Valve 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
  25 #include "aco_ir.h"
  26
  27 #include <algorithm>
  28
  29 /*
  30  * Implements an analysis pass to determine the number of uses
  31  * for each SSA-definition.
  32  */
  33
  34 namespace aco {
  35 namespace {
  36
  37 struct dce_ctx {
  38    int current_block;
  39    std::vector<uint16_t> uses;
  40    std::vector<std::vector<bool>> live;
  41
  42    dce_ctx(Program* program) : current_block(program->blocks.size() - 1), uses(program->peekAllocationId())
  43    {
  44       live.reserve(program->blocks.size());
  45       for (Block& block : program->blocks)
  46          live.emplace_back(block.instructions.size());
  47    }
  48 };
  49
  50 void process_block(dce_ctx& ctx, Block& block)
  51 {
  52    std::vector<bool>& live = ctx.live[block.index];
  53    assert(live.size() == block.instructions.size());
  54    bool process_predecessors = false;
  55    for (int idx = block.instructions.size() - 1; idx >= 0; idx--) {
  56       if (live[idx])
  57          continue;
  58
  59       aco_ptr<Instruction>& instr = block.instructions[idx];
  60       if (!is_dead(ctx.uses, instr.get())) {
  61          for (const Operand& op : instr->operands) {
  62             if (op.isTemp()) {
  63                if (ctx.uses[op.tempId()] == 0)
  64                   process_predecessors = true;
  65                ctx.uses[op.tempId()]++;
  66             }
  67          }
  68          live[idx] = true;
  69       }
  70    }
  71
  72    if (process_predecessors) {
  73       for (unsigned pred_idx : block.linear_preds)
  74          ctx.current_block = std::max(ctx.current_block, (int) pred_idx);
  75    }
  76 }
  77
  78 } /* end namespace */
  79
  80 bool is_dead(const std::vector<uint16_t>& uses, Instruction *instr)
  81 {
  82    if (instr->definitions.empty() || instr->format == Format::PSEUDO_BRANCH)
  83       return false;
  84    if (std::any_of(instr->definitions.begin(), instr->definitions.end(),
  85           [&uses] (const Definition& def) { return uses[def.tempId()];}))
  86       return false;
  87    return !(get_sync_info(instr).semantics & (semantic_volatile | semantic_acqrel));
  88 }
  89
  90 std::vector<uint16_t> dead_code_analysis(Program *program) {
  91
  92    dce_ctx ctx(program);
  93
  94    while (ctx.current_block >= 0) {
  95       unsigned next_block = ctx.current_block--;
  96       process_block(ctx, program->blocks[next_block]);
  97    }
  98
  99    /* add one use to exec to prevent startpgm from being removed */
 100    aco_ptr<Instruction>& startpgm = program->blocks[0].instructions[0];
 101    assert(startpgm->opcode == aco_opcode::p_startpgm);
 102    ctx.uses[startpgm->definitions.back().tempId()]++;
 103
 104    return ctx.uses;
 105 }
 106
 107 }
 108