1 // Copyright (c) 2018 Google LLC. 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_VECTOR_DCE_H_ 16 #define SOURCE_OPT_VECTOR_DCE_H_ 17 18 #include <unordered_map> 19 #include <vector> 20 21 #include "source/opt/mem_pass.h" 22 #include "source/util/bit_vector.h" 23 24 namespace spvtools { 25 namespace opt { 26 27 class VectorDCE : public MemPass { 28 private: 29 using LiveComponentMap = std::unordered_map<uint32_t, utils::BitVector>; 30 31 // According to the SPEC the maximum size for a vector is 16. See the data 32 // rules in the universal validation rules (section 2.16.1). 33 enum { kMaxVectorSize = 16 }; 34 35 struct WorkListItem { WorkListItemWorkListItem36 WorkListItem() : instruction(nullptr), components(kMaxVectorSize) {} 37 38 Instruction* instruction; 39 utils::BitVector components; 40 }; 41 42 public: VectorDCE()43 VectorDCE() : all_components_live_(kMaxVectorSize) { 44 for (uint32_t i = 0; i < kMaxVectorSize; i++) { 45 all_components_live_.Set(i); 46 } 47 } 48 name()49 const char* name() const override { return "vector-dce"; } 50 Status Process() override; 51 GetPreservedAnalyses()52 IRContext::Analysis GetPreservedAnalyses() override { 53 return IRContext::kAnalysisDefUse | IRContext::kAnalysisCFG | 54 IRContext::kAnalysisInstrToBlockMapping | 55 IRContext::kAnalysisLoopAnalysis | IRContext::kAnalysisDecorations | 56 IRContext::kAnalysisDominatorAnalysis | IRContext::kAnalysisNameMap | 57 IRContext::kAnalysisConstants | IRContext::kAnalysisTypes; 58 } 59 60 private: 61 // Runs the vector dce pass on |function|. Returns true if |function| was 62 // modified. 63 bool VectorDCEFunction(Function* function); 64 65 // Identifies the live components of the vectors that are results of 66 // instructions in |function|. The results are stored in |live_components|. 67 void FindLiveComponents(Function* function, 68 LiveComponentMap* live_components); 69 70 // Rewrites instructions in |function| that are dead or partially dead. If an 71 // instruction does not have an entry in |live_components|, then it is not 72 // changed. Returns true if |function| was modified. 73 bool RewriteInstructions(Function* function, 74 const LiveComponentMap& live_components); 75 76 // Makrs all DebugValue instructions that use |composite| for their values as 77 // dead instructions by putting them into |dead_dbg_value|. 78 void MarkDebugValueUsesAsDead(Instruction* composite, 79 std::vector<Instruction*>* dead_dbg_value); 80 81 // Rewrites the OpCompositeInsert instruction |current_inst| to avoid 82 // unnecessary computes given that the only components of the result that are 83 // live are |live_components|. 84 // 85 // If the value being inserted is not live, then the result of |current_inst| 86 // is replaced by the composite input to |current_inst|. 87 // 88 // If the composite input to |current_inst| is not live, then it is replaced 89 // by and OpUndef in |current_inst|. 90 bool RewriteInsertInstruction(Instruction* current_inst, 91 const utils::BitVector& live_components, 92 std::vector<Instruction*>* dead_dbg_value); 93 94 // Returns true if the result of |inst| is a vector or a scalar. 95 bool HasVectorOrScalarResult(const Instruction* inst) const; 96 97 // Returns true if the result of |inst| is a scalar. 98 bool HasVectorResult(const Instruction* inst) const; 99 100 // Returns true if the result of |inst| is a vector. 101 bool HasScalarResult(const Instruction* inst) const; 102 103 // Adds |work_item| to |work_list| if it is not already live according to 104 // |live_components|. |live_components| is updated to indicate that 105 // |work_item| is now live. 106 void AddItemToWorkListIfNeeded(WorkListItem work_item, 107 LiveComponentMap* live_components, 108 std::vector<WorkListItem>* work_list); 109 110 // Marks the components |live_elements| of the uses in |current_inst| as live 111 // according to |live_components|. If they were not live before, then they are 112 // added to |work_list|. 113 void MarkUsesAsLive(Instruction* current_inst, 114 const utils::BitVector& live_elements, 115 LiveComponentMap* live_components, 116 std::vector<WorkListItem>* work_list); 117 118 // Marks the uses in the OpVectorShuffle instruction in |current_item| as live 119 // based on the live components in |current_item|. If anything becomes live 120 // they are added to |work_list| and |live_components| is updated 121 // accordingly. 122 void MarkVectorShuffleUsesAsLive(const WorkListItem& current_item, 123 VectorDCE::LiveComponentMap* live_components, 124 std::vector<WorkListItem>* work_list); 125 126 // Marks the uses in the OpCompositeInsert instruction in |current_item| as 127 // live based on the live components in |current_item|. If anything becomes 128 // live they are added to |work_list| and |live_components| is updated 129 // accordingly. 130 void MarkInsertUsesAsLive(const WorkListItem& current_item, 131 LiveComponentMap* live_components, 132 std::vector<WorkListItem>* work_list); 133 134 // Marks the uses in the OpCompositeExtract instruction |current_inst| as 135 // live. If anything becomes live they are added to |work_list| and 136 // |live_components| is updated accordingly. 137 void MarkExtractUseAsLive(const Instruction* current_inst, 138 const utils::BitVector& live_elements, 139 LiveComponentMap* live_components, 140 std::vector<WorkListItem>* work_list); 141 142 // Marks the uses in the OpCompositeConstruct instruction |current_inst| as 143 // live. If anything becomes live they are added to |work_list| and 144 // |live_components| is updated accordingly. 145 void MarkCompositeContructUsesAsLive(WorkListItem work_item, 146 LiveComponentMap* live_components, 147 std::vector<WorkListItem>* work_list); 148 149 // A BitVector that can always be used to say that all components of a vector 150 // are live. 151 utils::BitVector all_components_live_; 152 }; 153 154 } // namespace opt 155 } // namespace spvtools 156 157 #endif // SOURCE_OPT_VECTOR_DCE_H_ 158