1 // Copyright (c) 2019 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_ELIMINATE_DEAD_MEMBERS_PASS_H_ 16 #define SOURCE_OPT_ELIMINATE_DEAD_MEMBERS_PASS_H_ 17 18 #include "source/opt/def_use_manager.h" 19 #include "source/opt/function.h" 20 #include "source/opt/mem_pass.h" 21 #include "source/opt/module.h" 22 23 namespace spvtools { 24 namespace opt { 25 26 // Remove unused members from structures. The remaining members will remain at 27 // the same offset. 28 class EliminateDeadMembersPass : public MemPass { 29 public: name()30 const char* name() const override { return "eliminate-dead-members"; } 31 Status Process() override; 32 GetPreservedAnalyses()33 IRContext::Analysis GetPreservedAnalyses() override { 34 return IRContext::kAnalysisDefUse | 35 IRContext::kAnalysisInstrToBlockMapping | 36 IRContext::kAnalysisCombinators | IRContext::kAnalysisCFG | 37 IRContext::kAnalysisDominatorAnalysis | 38 IRContext::kAnalysisLoopAnalysis | 39 IRContext::kAnalysisScalarEvolution | 40 IRContext::kAnalysisRegisterPressure | 41 IRContext::kAnalysisValueNumberTable | 42 IRContext::kAnalysisStructuredCFG | 43 IRContext::kAnalysisBuiltinVarId | 44 IRContext::kAnalysisIdToFuncMapping; 45 } 46 47 private: 48 // Populate |used_members_| with the member of structures that are live in the 49 // current context. 50 void FindLiveMembers(); 51 52 // Add to |used_members_| the member of structures that are live in 53 // |function|. 54 void FindLiveMembers(const Function& function); 55 // Add to |used_members_| the member of structures that are live in |inst|. 56 void FindLiveMembers(const Instruction* inst); 57 58 // Add to |used_members_| the members that are live in the |OpStore| 59 // instruction |inst|. 60 void MarkMembersAsLiveForStore(const Instruction* inst); 61 62 // Add to |used_members_| the members that are live in the |OpCopyMemory*| 63 // instruction |inst|. 64 void MarkMembersAsLiveForCopyMemory(const Instruction* inst); 65 66 // Add to |used_members_| the members that are live in the 67 // |OpCompositeExtract| instruction |inst|. 68 void MarkMembersAsLiveForExtract(const Instruction* inst); 69 70 // Add to |used_members_| the members that are live in the |Op*AccessChain| 71 // instruction |inst|. 72 void MarkMembersAsLiveForAccessChain(const Instruction* inst); 73 74 // Add the member referenced by the OpArrayLength instruction |inst| to 75 // |uses_members_|. 76 void MarkMembersAsLiveForArrayLength(const Instruction* inst); 77 78 // Remove dead members from structs and updates any instructions that need to 79 // be updated as a consequence. Return true if something changed. 80 bool RemoveDeadMembers(); 81 82 // Update |inst|, which must be an |OpMemberName| or |OpMemberDecorate| 83 // instruction, so it references the correct member after the struct is 84 // updated. Return true if something changed. 85 bool UpdateOpMemberNameOrDecorate(Instruction* inst); 86 87 // Update |inst|, which must be an |OpGroupMemberDecorate| instruction, so it 88 // references the correct member after the struct is updated. Return true if 89 // something changed. 90 bool UpdateOpGroupMemberDecorate(Instruction* inst); 91 92 // Update the |OpTypeStruct| instruction |inst| my removing the members that 93 // are not live. Return true if something changed. 94 bool UpdateOpTypeStruct(Instruction* inst); 95 96 // Update the |OpConstantComposite| instruction |inst| to match the change 97 // made to the type that was being generated. Return true if something 98 // changed. 99 bool UpdateConstantComposite(Instruction* inst); 100 101 // Update the |Op*AccessChain| instruction |inst| to reference the correct 102 // members. All members referenced in the access chain must be live. This 103 // function must be called after the |OpTypeStruct| instruction for the type 104 // has been updated. Return true if something changed. 105 bool UpdateAccessChain(Instruction* inst); 106 107 // Update the |OpCompositeExtract| instruction |inst| to reference the correct 108 // members. All members referenced in the instruction must be live. This 109 // function must be called after the |OpTypeStruct| instruction for the type 110 // has been updated. Return true if something changed. 111 bool UpdateCompsiteExtract(Instruction* inst); 112 113 // Update the |OpCompositeInsert| instruction |inst| to reference the correct 114 // members. If the member being inserted is not live, then |inst| is killed. 115 // This function must be called after the |OpTypeStruct| instruction for the 116 // type has been updated. Return true if something changed. 117 bool UpdateCompositeInsert(Instruction* inst); 118 119 // Update the |OpArrayLength| instruction |inst| to reference the correct 120 // member. The member referenced in the instruction must be live. Return true 121 // if something changed. 122 bool UpdateOpArrayLength(Instruction* inst); 123 124 // Add all of the members of type |type_id| and members of any subtypes to 125 // |used_members_|. 126 void MarkTypeAsFullyUsed(uint32_t type_id); 127 128 // Add all of the members of the type of the operand |in_idx| in |inst| and 129 // members of any subtypes to |uses_members_|. 130 void MarkOperandTypeAsFullyUsed(const Instruction* inst, uint32_t in_idx); 131 132 // Return the index of the member that use to be the |member_idx|th member of 133 // |type_id|. If the member has been removed, |kRemovedMember| is returned. 134 uint32_t GetNewMemberIndex(uint32_t type_id, uint32_t member_idx); 135 136 // A map from a type id to a set of indices representing the members of the 137 // type that are used, and must be kept. 138 std::unordered_map<uint32_t, std::set<uint32_t>> used_members_; 139 void MarkStructOperandsAsFullyUsed(const Instruction* inst); 140 void MarkPointeeTypeAsFullUsed(uint32_t ptr_type_id); 141 }; 142 143 } // namespace opt 144 } // namespace spvtools 145 146 #endif // SOURCE_OPT_ELIMINATE_DEAD_MEMBERS_PASS_H_ 147