1 // Copyright (c) 2017 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 #ifndef SOURCE_OPT_LOCAL_REDUNDANCY_ELIMINATION_H_ 16 #define SOURCE_OPT_LOCAL_REDUNDANCY_ELIMINATION_H_ 17 18 #include <map> 19 20 #include "source/opt/ir_context.h" 21 #include "source/opt/pass.h" 22 #include "source/opt/value_number_table.h" 23 24 namespace spvtools { 25 namespace opt { 26 27 // This pass implements local redundancy elimination. Its goal is to reduce the 28 // number of times the same value is computed. It works on each basic block 29 // independently, ie local. For each instruction in a basic block, it gets the 30 // value number for the result id, |id|, of the instruction. If that value 31 // number has already been computed in the basic block, it tries to replace the 32 // uses of |id| by the id that already contains the same value. Then the 33 // current instruction is deleted. 34 class LocalRedundancyEliminationPass : public Pass { 35 public: name()36 const char* name() const override { return "local-redundancy-elimination"; } 37 Status Process() override; 38 GetPreservedAnalyses()39 IRContext::Analysis GetPreservedAnalyses() override { 40 return IRContext::kAnalysisDefUse | 41 IRContext::kAnalysisInstrToBlockMapping | 42 IRContext::kAnalysisDecorations | IRContext::kAnalysisCombinators | 43 IRContext::kAnalysisCFG | IRContext::kAnalysisDominatorAnalysis | 44 IRContext::kAnalysisNameMap | IRContext::kAnalysisConstants | 45 IRContext::kAnalysisTypes; 46 } 47 48 protected: 49 // Deletes instructions in |block| whose value is in |value_to_ids| or is 50 // computed earlier in |block|. 51 // 52 // |vnTable| must have computed a value number for every result id defined 53 // in |bb|. 54 // 55 // |value_to_ids| is a map from value number to ids. If {vn, id} is in 56 // |value_to_ids| then vn is the value number of id, and the definition of id 57 // dominates |bb|. 58 // 59 // Returns true if the module is changed. 60 bool EliminateRedundanciesInBB(BasicBlock* block, 61 const ValueNumberTable& vnTable, 62 std::map<uint32_t, uint32_t>* value_to_ids); 63 }; 64 65 } // namespace opt 66 } // namespace spvtools 67 68 #endif // SOURCE_OPT_LOCAL_REDUNDANCY_ELIMINATION_H_ 69