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
23namespace spvtools {
24namespace opt {
25
26// Remove unused members from structures. The remaining members will remain at
27// the same offset.
28class EliminateDeadMembersPass : public MemPass {
29 public:
30 const char* name() const override { return "eliminate-dead-members"; }
31 Status Process() override;
32
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