Coverage Report

Created: 2025-06-13 06:49

/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_