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:
ValueNumberTable(IRContext * ctx)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 
context()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.
TakeNextValueNumber()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_
92