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
23namespace spvtools {
24namespace opt {
25
26class IRContext;
27
28// Returns true if the two instructions compute the same value. Used by the
29// value number table to compare two instructions.
30class 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.
36class 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.
52class 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_
92