1 // Copyright (c) 2021 Google LLC 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_REPLACE_DESC_VAR_INDEX_ACCESS_H_ 16 #define SOURCE_OPT_REPLACE_DESC_VAR_INDEX_ACCESS_H_ 17 18 #include <cstdio> 19 #include <memory> 20 #include <queue> 21 #include <unordered_map> 22 #include <unordered_set> 23 #include <vector> 24 25 #include "source/opt/function.h" 26 #include "source/opt/pass.h" 27 #include "source/opt/type_manager.h" 28 29 namespace spvtools { 30 namespace opt { 31 32 // See optimizer.hpp for documentation. 33 class ReplaceDescArrayAccessUsingVarIndex : public Pass { 34 public: ReplaceDescArrayAccessUsingVarIndex()35 ReplaceDescArrayAccessUsingVarIndex() {} 36 name()37 const char* name() const override { 38 return "replace-desc-array-access-using-var-index"; 39 } 40 41 Status Process() override; 42 GetPreservedAnalyses()43 IRContext::Analysis GetPreservedAnalyses() override { 44 return IRContext::kAnalysisDefUse | 45 IRContext::kAnalysisInstrToBlockMapping | 46 IRContext::kAnalysisConstants | IRContext::kAnalysisTypes; 47 } 48 49 private: 50 // Replaces all accesses to |var| using variable indices with constant 51 // elements of the array |var|. Creates switch-case statements to determine 52 // the value of the variable index for all the possible cases. Returns 53 // whether replacement is done or not. 54 bool ReplaceVariableAccessesWithConstantElements(Instruction* var) const; 55 56 // Replaces the OpAccessChain or OpInBoundsAccessChain instruction |use| that 57 // uses the descriptor variable |var| with the OpAccessChain or 58 // OpInBoundsAccessChain instruction with a constant Indexes operand. 59 void ReplaceAccessChain(Instruction* var, Instruction* use) const; 60 61 // Updates the first Indexes operand of the OpAccessChain or 62 // OpInBoundsAccessChain instruction |access_chain| to let it use a constant 63 // index |const_element_idx|. 64 void UseConstIndexForAccessChain(Instruction* access_chain, 65 uint32_t const_element_idx) const; 66 67 // Replaces users of the OpAccessChain or OpInBoundsAccessChain instruction 68 // |access_chain| that accesses an array descriptor variable using variable 69 // indices with constant elements. |number_of_elements| is the number 70 // of array elements. 71 void ReplaceUsersOfAccessChain(Instruction* access_chain, 72 uint32_t number_of_elements) const; 73 74 // Puts all the recursive users of |access_chain| with concrete result types 75 // or the ones without result it in |final_users|. 76 void CollectRecursiveUsersWithConcreteType( 77 Instruction* access_chain, std::vector<Instruction*>* final_users) const; 78 79 // Recursively collects the operands of |user| (and operands of the operands) 80 // whose result types are images/samplers (or pointers/arrays/ structs of 81 // them) and access chains instructions and returns them. The returned 82 // collection includes |user|. 83 std::deque<Instruction*> CollectRequiredImageAndAccessInsts( 84 Instruction* user) const; 85 86 // Returns whether result type of |inst| is an image/sampler/pointer of image 87 // or sampler or not. 88 bool HasImageOrImagePtrType(const Instruction* inst) const; 89 90 // Returns whether |type_inst| is an image/sampler or pointer/array/struct of 91 // image or sampler or not. 92 bool IsImageOrImagePtrType(const Instruction* type_inst) const; 93 94 // Returns whether the type with |type_id| is a concrete type or not. 95 bool IsConcreteType(uint32_t type_id) const; 96 97 // Replaces the non-uniform access to a descriptor variable 98 // |access_chain_final_user| with OpSwitch instruction and case blocks. Each 99 // case block will contain a clone of |access_chain| and clones of 100 // |non_uniform_accesses_to_clone| that are recursively used by 101 // |access_chain_final_user|. The clone of |access_chain| (or 102 // OpInBoundsAccessChain) will have a constant index for its first index. The 103 // OpSwitch instruction will have the cases for the variable index of 104 // |access_chain| from 0 to |number_of_elements| - 1. 105 void ReplaceNonUniformAccessWithSwitchCase( 106 Instruction* access_chain_final_user, Instruction* access_chain, 107 uint32_t number_of_elements, 108 const std::deque<Instruction*>& non_uniform_accesses_to_clone) const; 109 110 // Creates and returns a new basic block that contains all instructions of 111 // |block| after |separation_begin_inst|. The new basic block is added to the 112 // function in this method. 113 BasicBlock* SeparateInstructionsIntoNewBlock( 114 BasicBlock* block, Instruction* separation_begin_inst) const; 115 116 // Creates and returns a new block. 117 BasicBlock* CreateNewBlock() const; 118 119 // Returns the first operand id of the OpAccessChain or OpInBoundsAccessChain 120 // instruction |access_chain|. 121 uint32_t GetFirstIndexOfAccessChain(Instruction* access_chain) const; 122 123 // Adds a clone of the OpAccessChain or OpInBoundsAccessChain instruction 124 // |access_chain| to |case_block|. The clone of |access_chain| will use 125 // |const_element_idx| for its first index. |old_ids_to_new_ids| keeps the 126 // mapping from the result id of |access_chain| to the result of its clone. 127 void AddConstElementAccessToCaseBlock( 128 BasicBlock* case_block, Instruction* access_chain, 129 uint32_t const_element_idx, 130 std::unordered_map<uint32_t, uint32_t>* old_ids_to_new_ids) const; 131 132 // Clones all instructions in |insts_to_be_cloned| and put them to |block|. 133 // |old_ids_to_new_ids| keeps the mapping from the result id of each 134 // instruction of |insts_to_be_cloned| to the result of their clones. 135 void CloneInstsToBlock( 136 BasicBlock* block, Instruction* inst_to_skip_cloning, 137 const std::deque<Instruction*>& insts_to_be_cloned, 138 std::unordered_map<uint32_t, uint32_t>* old_ids_to_new_ids) const; 139 140 // Adds OpBranch to |branch_destination| at the end of |parent_block|. 141 void AddBranchToBlock(BasicBlock* parent_block, 142 uint32_t branch_destination) const; 143 144 // Replaces in-operands of all instructions in the basic block |block| using 145 // |old_ids_to_new_ids|. It conducts the replacement only if the in-operand 146 // id is a key of |old_ids_to_new_ids|. 147 void UseNewIdsInBlock( 148 BasicBlock* block, 149 const std::unordered_map<uint32_t, uint32_t>& old_ids_to_new_ids) const; 150 151 // Creates a case block for |element_index| case. It adds clones of 152 // |insts_to_be_cloned| and a clone of |access_chain| with |element_index| as 153 // its first index. The termination instruction of the created case block will 154 // be a branch to |branch_target_id|. Puts old ids to new ids map for the 155 // cloned instructions in |old_ids_to_new_ids|. 156 BasicBlock* CreateCaseBlock( 157 Instruction* access_chain, uint32_t element_index, 158 const std::deque<Instruction*>& insts_to_be_cloned, 159 uint32_t branch_target_id, 160 std::unordered_map<uint32_t, uint32_t>* old_ids_to_new_ids) const; 161 162 // Creates a default block for switch-case statement that has only a single 163 // instruction OpBranch whose target is a basic block with |merge_block_id|. 164 // If |null_const_for_phi_is_needed| is true, gets or creates a default null 165 // constant value for a phi instruction whose operands are |phi_operands| and 166 // puts it in |phi_operands|. 167 BasicBlock* CreateDefaultBlock(bool null_const_for_phi_is_needed, 168 std::vector<uint32_t>* phi_operands, 169 uint32_t merge_block_id) const; 170 171 // Creates and adds an OpSwitch used for the selection of OpAccessChain whose 172 // first Indexes operand is |access_chain_index_var_id|. The OpSwitch will be 173 // added at the end of |parent_block|. It will jump to |default_id| for the 174 // default case and jumps to one of case blocks whose ids are |case_block_ids| 175 // if |access_chain_index_var_id| matches the case number. |merge_id| is the 176 // merge block id. 177 void AddSwitchForAccessChain( 178 BasicBlock* parent_block, uint32_t access_chain_index_var_id, 179 uint32_t default_id, uint32_t merge_id, 180 const std::vector<uint32_t>& case_block_ids) const; 181 182 // Creates a phi instruction with |phi_operands| as values and 183 // |case_block_ids| and |default_block_id| as incoming blocks. The size of 184 // |phi_operands| must be exactly 1 larger than the size of |case_block_ids|. 185 // The last element of |phi_operands| will be used for |default_block_id|. It 186 // adds the phi instruction to the beginning of |parent_block|. 187 uint32_t CreatePhiInstruction(BasicBlock* parent_block, 188 const std::vector<uint32_t>& phi_operands, 189 const std::vector<uint32_t>& case_block_ids, 190 uint32_t default_block_id) const; 191 192 // Replaces the incoming block operand of OpPhi instructions with 193 // |new_incoming_block_id| if the incoming block operand is 194 // |old_incoming_block_id|. 195 void ReplacePhiIncomingBlock(uint32_t old_incoming_block_id, 196 uint32_t new_incoming_block_id) const; 197 198 // Create an OpConstantNull instruction whose result type id is |type_id|. 199 Instruction* GetConstNull(uint32_t type_id) const; 200 }; 201 202 } // namespace opt 203 } // namespace spvtools 204 205 #endif // SOURCE_OPT_REPLACE_DESC_VAR_INDEX_ACCESS_H_ 206