Debian Codegraph @

third_party/spirv-tools/source/opt/vector_dce.h

raw
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 {
36 WorkListItem() : instruction(nullptr), components(kMaxVectorSize) {}
37
38 Instruction* instruction;
39 utils::BitVector components;
40 };
41
42 public:
43 VectorDCE() : all_components_live_(kMaxVectorSize) {
44 for (uint32_t i = 0; i < kMaxVectorSize; i++) {
45 all_components_live_.Set(i);
46 }
47 }
48
49 const char* name() const override { return "vector-dce"; }
50 Status Process() override;
51
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_