Home | History | Annotate | Download | only in opt 
      1 // Copyright (c) 2016 Google Inc.
      2 //
      3 // Licensed under the Apache License, Version 2.0 (the "License");
      4 // you may not use this file except in compliance with the License.
      5 // You may obtain a copy of the License at
      6 //
      7 //     http://www.apache.org/licenses/LICENSE-2.0
      8 //
      9 // Unless required by applicable law or agreed to in writing, software
     10 // distributed under the License is distributed on an "AS IS" BASIS,
     11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     12 // See the License for the specific language governing permissions and
     13 // limitations under the License.
     14 
     15 #include "source/opt/eliminate_dead_constant_pass.h"
     16 
     17 #include <algorithm>
     18 #include <unordered_map>
     19 #include <unordered_set>
     20 #include <vector>
     21 
     22 #include "source/opt/def_use_manager.h"
     23 #include "source/opt/ir_context.h"
     24 #include "source/opt/log.h"
     25 #include "source/opt/reflect.h"
     26 
     27 namespace spvtools {
     28 namespace opt {
     29 
     30 Pass::Status EliminateDeadConstantPass::Process() {
     31   std::unordered_set<Instruction*> working_list;
     32   // Traverse all the instructions to get the initial set of dead constants as
     33   // working list and count number of real uses for constants. Uses in
     34   // annotation instructions do not count.
     35   std::unordered_map<Instruction*, size_t> use_counts;
     36   std::vector<Instruction*> constants = context()->GetConstants();
     37   for (auto* c : constants) {
     38     uint32_t const_id = c->result_id();
     39     size_t count = 0;
     40     context()->get_def_use_mgr()->ForEachUse(
     41         const_id, [&count](Instruction* user, uint32_t index) {
     42           (void)index;
     43           SpvOp op = user->opcode();
     44           if (!(IsAnnotationInst(op) || IsDebug1Inst(op) || IsDebug2Inst(op) ||
     45                 IsDebug3Inst(op))) {
     46             ++count;
     47           }
     48         });
     49     use_counts[c] = count;
     50     if (!count) {
     51       working_list.insert(c);
     52     }
     53   }
     54 
     55   // Start from the constants with 0 uses, back trace through the def-use chain
     56   // to find all dead constants.
     57   std::unordered_set<Instruction*> dead_consts;
     58   while (!working_list.empty()) {
     59     Instruction* inst = *working_list.begin();
     60     // Back propagate if the instruction contains IDs in its operands.
     61     switch (inst->opcode()) {
     62       case SpvOp::SpvOpConstantComposite:
     63       case SpvOp::SpvOpSpecConstantComposite:
     64       case SpvOp::SpvOpSpecConstantOp:
     65         for (uint32_t i = 0; i < inst->NumInOperands(); i++) {
     66           // SpecConstantOp instruction contains 'opcode' as its operand. Need
     67           // to exclude such operands when decreasing uses.
     68           if (inst->GetInOperand(i).type != SPV_OPERAND_TYPE_ID) {
     69             continue;
     70           }
     71           uint32_t operand_id = inst->GetSingleWordInOperand(i);
     72           Instruction* def_inst =
     73               context()->get_def_use_mgr()->GetDef(operand_id);
     74           // If the use_count does not have any count for the def_inst,
     75           // def_inst must not be a constant, and should be ignored here.
     76           if (!use_counts.count(def_inst)) {
     77             continue;
     78           }
     79           // The number of uses should never be less then 0, so it can not be
     80           // less than 1 before it decreases.
     81           SPIRV_ASSERT(consumer(), use_counts[def_inst] > 0);
     82           --use_counts[def_inst];
     83           if (!use_counts[def_inst]) {
     84             working_list.insert(def_inst);
     85           }
     86         }
     87         break;
     88       default:
     89         break;
     90     }
     91     dead_consts.insert(inst);
     92     working_list.erase(inst);
     93   }
     94 
     95   // Turn all dead instructions and uses of them to nop
     96   for (auto* dc : dead_consts) {
     97     context()->KillDef(dc->result_id());
     98   }
     99   return dead_consts.empty() ? Status::SuccessWithoutChange
    100                              : Status::SuccessWithChange;
    101 }
    102 
    103 }  // namespace opt
    104 }  // namespace spvtools
    105