/src/spirv-tools/source/opt/local_redundancy_elimination.h
Line | Count | Source (jump to first uncovered line) |
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: |
36 | 0 | const char* name() const override { return "local-redundancy-elimination"; } |
37 | | Status Process() override; |
38 | | |
39 | 2.05k | IRContext::Analysis GetPreservedAnalyses() override { |
40 | 2.05k | return IRContext::kAnalysisDefUse | |
41 | 2.05k | IRContext::kAnalysisInstrToBlockMapping | |
42 | 2.05k | IRContext::kAnalysisDecorations | IRContext::kAnalysisCombinators | |
43 | 2.05k | IRContext::kAnalysisCFG | IRContext::kAnalysisDominatorAnalysis | |
44 | 2.05k | IRContext::kAnalysisNameMap | IRContext::kAnalysisConstants | |
45 | 2.05k | IRContext::kAnalysisTypes; |
46 | 2.05k | } |
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_ |