Debian Codegraph @

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

raw
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_VALUE_NUMBER_TABLE_H_
16 #define SOURCE_OPT_VALUE_NUMBER_TABLE_H_
17
18 #include <cstdint>
19 #include <unordered_map>
20
21 #include "source/opt/instruction.h"
22
23 namespace spvtools {
24 namespace opt {
25
26 class IRContext;
27
28 // Returns true if the two instructions compute the same value. Used by the
29 // value number table to compare two instructions.
30 class ComputeSameValue {
31 public:
32 bool operator()(const Instruction& lhs, const Instruction& rhs) const;
33 };
34
35 // The hash function used in the value number table.
36 class ValueTableHash {
37 public:
38 std::size_t operator()(const Instruction& inst) const;
39 };
40
41 // This class implements the value number analysis. It is using a hash-based
42 // approach to value numbering. It is essentially doing dominator-tree value
43 // numbering described in
44 //
45 // Preston Briggs, Keith D. Cooper, and L. Taylor Simpson. 1997. Value
46 // numbering. Softw. Pract. Exper. 27, 6 (June 1997), 701-724.
47 // https://www.cs.rice.edu/~keith/Promo/CRPC-TR94517.pdf.gz
48 //
49 // The main difference is that because we do not perform redundancy elimination
50 // as we build the value number table, we do not have to deal with cleaning up
51 // the scope.
52 class ValueNumberTable {
53 public:
54 ValueNumberTable(IRContext* ctx) : context_(ctx), next_value_number_(1) {
55 BuildDominatorTreeValueNumberTable();
56 }
57
58 // Returns the value number of the value computed by |inst|. |inst| must have
59 // a result id that will hold the computed value. If no value number has been
60 // assigned to the result id, then the return value is 0.
61 uint32_t GetValueNumber(Instruction* inst) const;
62
63 // Returns the value number of the value contain in |id|. Returns 0 if it
64 // has not been assigned a value number.
65 uint32_t GetValueNumber(uint32_t id) const;
66
67 IRContext* context() const { return context_; }
68
69 private:
70 // Assigns a value number to every result id in the module.
71 void BuildDominatorTreeValueNumberTable();
72
73 // Returns the new value number.
74 uint32_t TakeNextValueNumber() { return next_value_number_++; }
75
76 // Assigns a new value number to the result of |inst| if it does not already
77 // have one. Return the value number for |inst|. |inst| must have a result
78 // id.
79 uint32_t AssignValueNumber(Instruction* inst);
80
81 std::unordered_map<Instruction, uint32_t, ValueTableHash, ComputeSameValue>
82 instruction_to_value_;
83 std::unordered_map<uint32_t, uint32_t> id_to_value_;
84 IRContext* context_;
85 uint32_t next_value_number_;
86 };
87
88 } // namespace opt
89 } // namespace spvtools
90
91 #endif // SOURCE_OPT_VALUE_NUMBER_TABLE_H_