1 // Copyright (c) 2016 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 #include "unify_const_pass.h" 16 17 #include <unordered_map> 18 #include <utility> 19 20 #include "def_use_manager.h" 21 #include "make_unique.h" 22 23 namespace spvtools { 24 namespace opt { 25 26 namespace { 27 28 // The trie that stores a bunch of result ids and, for a given instruction, 29 // searches the result id that has been defined with the same opcode, type and 30 // operands. 31 class ResultIdTrie { 32 public: 33 ResultIdTrie() : root_(new Node) {} 34 35 // For a given instruction, extracts its opcode, type id and operand words 36 // as an array of keys, looks up the trie to find a result id which is stored 37 // with the same opcode, type id and operand words. If none of such result id 38 // is found, creates a trie node with those keys, stores the instruction's 39 // result id and returns that result id. If an existing result id is found, 40 // returns the existing result id. 41 uint32_t LookupEquivalentResultFor(const ir::Instruction& inst) { 42 auto keys = GetLookUpKeys(inst); 43 auto* node = root_.get(); 44 for (uint32_t key : keys) { 45 node = node->GetOrCreateTrieNodeFor(key); 46 } 47 if (node->result_id() == 0) { 48 node->SetResultId(inst.result_id()); 49 } 50 return node->result_id(); 51 } 52 53 private: 54 // The trie node to store result ids. 55 class Node { 56 public: 57 using TrieNodeMap = std::unordered_map<uint32_t, std::unique_ptr<Node>>; 58 59 Node() : result_id_(0), next_() {} 60 uint32_t result_id() const { return result_id_; } 61 62 // Sets the result id stored in this node. 63 void SetResultId(uint32_t id) { result_id_ = id; } 64 65 // Searches for the child trie node with the given key. If the node is 66 // found, returns that node. Otherwise creates an empty child node with 67 // that key and returns that newly created node. 68 Node* GetOrCreateTrieNodeFor(uint32_t key) { 69 auto iter = next_.find(key); 70 if (iter == next_.end()) { 71 // insert a new node and return the node. 72 return next_.insert(std::make_pair(key, MakeUnique<Node>())) 73 .first->second.get(); 74 } 75 return iter->second.get(); 76 } 77 78 private: 79 // The result id stored in this node. 0 means this node is empty. 80 uint32_t result_id_; 81 // The mapping from the keys to the child nodes of this node. 82 TrieNodeMap next_; 83 }; 84 85 // Returns a vector of the opcode followed by the words in the raw SPIR-V 86 // instruction encoding but without the result id. 87 std::vector<uint32_t> GetLookUpKeys(const ir::Instruction& inst) { 88 std::vector<uint32_t> keys; 89 // Need to use the opcode, otherwise there might be a conflict with the 90 // following case when <op>'s binary value equals xx's id: 91 // OpSpecConstantOp tt <op> yy zz 92 // OpSpecConstantComposite tt xx yy zz; 93 keys.push_back(static_cast<uint32_t>(inst.opcode())); 94 for (const auto& operand : inst) { 95 if (operand.type == SPV_OPERAND_TYPE_RESULT_ID) continue; 96 keys.insert(keys.end(), operand.words.cbegin(), operand.words.cend()); 97 } 98 return keys; 99 } 100 101 std::unique_ptr<Node> root_; // The root node of the trie. 102 }; 103 } // anonymous namespace 104 105 Pass::Status UnifyConstantPass::Process(ir::Module* module) { 106 bool modified = false; 107 ResultIdTrie defined_constants; 108 analysis::DefUseManager def_use_mgr(consumer(), module); 109 110 for (ir::Instruction& inst : module->types_values()) { 111 // Do not handle the instruction when there are decorations upon the result 112 // id. 113 if (def_use_mgr.GetAnnotations(inst.result_id()).size() != 0) { 114 continue; 115 } 116 117 // The overall algorithm is to store the result ids of all the eligible 118 // constants encountered so far in a trie. For a constant defining 119 // instruction under consideration, use its opcode, result type id and 120 // words in operands as an array of keys to lookup the trie. If a result id 121 // can be found for that array of keys, a constant with exactly the same 122 // value must has been defined before, the constant under processing 123 // should be replaced by the constant previously defined. If no such result 124 // id can be found for that array of keys, this must be the first time a 125 // constant with its value be defined, we then create a new trie node to 126 // store the result id with the keys. When replacing a duplicated constant 127 // with a previously defined constant, all the uses of the duplicated 128 // constant, which must be placed after the duplicated constant defining 129 // instruction, will be updated. This way, the descendants of the 130 // previously defined constant and the duplicated constant will both refer 131 // to the previously defined constant. So that the operand ids which are 132 // used in key arrays will be the ids of the unified constants, when 133 // processing is up to a descendant. This makes comparing the key array 134 // always valid for judging duplication. 135 switch (inst.opcode()) { 136 case SpvOp::SpvOpConstantTrue: 137 case SpvOp::SpvOpConstantFalse: 138 case SpvOp::SpvOpConstant: 139 case SpvOp::SpvOpConstantNull: 140 case SpvOp::SpvOpConstantSampler: 141 case SpvOp::SpvOpConstantComposite: 142 // Only spec constants defined with OpSpecConstantOp and 143 // OpSpecConstantComposite should be processed in this pass. Spec 144 // constants defined with OpSpecConstant{|True|False} are decorated with 145 // 'SpecId' decoration and all of them should be treated as unique. 146 // 'SpecId' is not applicable to SpecConstants defined with 147 // OpSpecConstant{Op|Composite}, their values are not necessary to be 148 // unique. When all the operands/compoents are the same between two 149 // OpSpecConstant{Op|Composite} results, their result values must be the 150 // same so are unifiable. 151 case SpvOp::SpvOpSpecConstantOp: 152 case SpvOp::SpvOpSpecConstantComposite: { 153 uint32_t id = defined_constants.LookupEquivalentResultFor(inst); 154 if (id != inst.result_id()) { 155 // The constant is a duplicated one, use the cached constant to 156 // replace the uses of this duplicated one, then turn it to nop. 157 def_use_mgr.ReplaceAllUsesWith(inst.result_id(), id); 158 def_use_mgr.KillInst(&inst); 159 modified = true; 160 } 161 break; 162 } 163 default: 164 break; 165 } 166 } 167 return modified ? Status::SuccessWithChange : Status::SuccessWithoutChange; 168 } 169 170 } // opt 171 } // namespace spvtools 172