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