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 #ifndef LIBSPIRV_OPT_DEF_USE_MANAGER_H_ 16 #define LIBSPIRV_OPT_DEF_USE_MANAGER_H_ 17 18 #include <list> 19 #include <unordered_map> 20 #include <vector> 21 22 #include "instruction.h" 23 #include "module.h" 24 #include "spirv-tools/libspirv.hpp" 25 26 namespace spvtools { 27 namespace opt { 28 namespace analysis { 29 30 // Class for representing a use of id. Note that: 31 // * Result type id is a use. 32 // * Ids referenced in OpSectionMerge & OpLoopMerge are considered as use. 33 // * Ids referenced in OpPhi's in operands are considered as use. 34 struct Use { 35 ir::Instruction* inst; // Instruction using the id. 36 uint32_t operand_index; // logical operand index of the id use. This can be 37 // the index of result type id. 38 }; 39 40 using UseList = std::list<Use>; 41 42 // A class for analyzing and managing defs and uses in an ir::Module. 43 class DefUseManager { 44 public: 45 using IdToDefMap = std::unordered_map<uint32_t, ir::Instruction*>; 46 using IdToUsesMap = std::unordered_map<uint32_t, UseList>; 47 48 // Constructs a def-use manager from the given |module|. All internal messages 49 // will be communicated to the outside via the given message |consumer|. This 50 // instance only keeps a reference to the |consumer|, so the |consumer| should 51 // outlive this instance. 52 DefUseManager(const MessageConsumer& consumer, ir::Module* module) 53 : consumer_(consumer) { 54 AnalyzeDefUse(module); 55 } 56 57 DefUseManager(const DefUseManager&) = delete; 58 DefUseManager(DefUseManager&&) = delete; 59 DefUseManager& operator=(const DefUseManager&) = delete; 60 DefUseManager& operator=(DefUseManager&&) = delete; 61 62 // Analyzes the defs in the given |inst|. 63 void AnalyzeInstDef(ir::Instruction* inst); 64 65 // Analyzes the uses in the given |inst|. 66 void AnalyzeInstUse(ir::Instruction* inst); 67 68 // Analyzes the defs and uses in the given |inst|. 69 void AnalyzeInstDefUse(ir::Instruction* inst); 70 71 // Returns the def instruction for the given |id|. If there is no instruction 72 // defining |id|, returns nullptr. 73 ir::Instruction* GetDef(uint32_t id); 74 // Returns the use instructions for the given |id|. If there is no uses of 75 // |id|, returns nullptr. 76 UseList* GetUses(uint32_t id); 77 const UseList* GetUses(uint32_t id) const; 78 // Returns the annotation instrunctions which are a direct use of the given 79 // |id|. This means when the decorations are applied through decoration 80 // group(s), this function will just return the OpGroupDecorate 81 // instrcution(s) which refer to the given id as an operand. The OpDecorate 82 // instructions which decorate the decoration group will not be returned. 83 std::vector<ir::Instruction*> GetAnnotations(uint32_t id) const; 84 85 // Returns the map from ids to their def instructions. 86 const IdToDefMap& id_to_defs() const { return id_to_def_; } 87 // Returns the map from ids to their uses in instructions. 88 const IdToUsesMap& id_to_uses() const { return id_to_uses_; } 89 90 // Turns the instruction defining the given |id| into a Nop. Returns true on 91 // success, false if the given |id| is not defined at all. This method also 92 // erases both the uses of |id| and the information of this |id|-generating 93 // instruction's uses of its operands. 94 bool KillDef(uint32_t id); 95 // Turns the given instruction |inst| to a Nop. This method erases the 96 // information of the given instruction's uses of its operands. If |inst| 97 // defines an result id, the uses of the result id will also be erased. 98 void KillInst(ir::Instruction* inst); 99 // Replaces all uses of |before| id with |after| id. Returns true if any 100 // replacement happens. This method does not kill the definition of the 101 // |before| id. If |after| is the same as |before|, does nothing and returns 102 // false. 103 bool ReplaceAllUsesWith(uint32_t before, uint32_t after); 104 105 private: 106 using InstToUsedIdsMap = 107 std::unordered_map<const ir::Instruction*, std::vector<uint32_t>>; 108 109 // Analyzes the defs and uses in the given |module| and populates data 110 // structures in this class. Does nothing if |module| is nullptr. 111 void AnalyzeDefUse(ir::Module* module); 112 113 // Clear the internal def-use record of the given instruction |inst|. This 114 // method will update the use information of the operand ids of |inst|. The 115 // record: |inst| uses an |id|, will be removed from the use records of |id|. 116 // If |inst| defines an result id, the use record of this result id will also 117 // be removed. Does nothing if |inst| was not analyzed before. 118 void ClearInst(ir::Instruction* inst); 119 120 // Erases the records that a given instruction uses its operand ids. 121 void EraseUseRecordsOfOperandIds(const ir::Instruction* inst); 122 123 const MessageConsumer& consumer_; // Message consumer. 124 IdToDefMap id_to_def_; // Mapping from ids to their definitions 125 IdToUsesMap id_to_uses_; // Mapping from ids to their uses 126 // Mapping from instructions to the ids used in the instructions generating 127 // the result ids. 128 InstToUsedIdsMap inst_to_used_ids_; 129 }; 130 131 } // namespace analysis 132 } // namespace opt 133 } // namespace spvtools 134 135 #endif // LIBSPIRV_OPT_DEF_USE_MANAGER_H_ 136