1 // Copyright (c) 2017 The Khronos Group Inc. 2 // Copyright (c) 2017 Valve Corporation 3 // Copyright (c) 2017 LunarG Inc. 4 // 5 // Licensed under the Apache License, Version 2.0 (the "License"); 6 // you may not use this file except in compliance with the License. 7 // You may obtain a copy of the License at 8 // 9 // http://www.apache.org/licenses/LICENSE-2.0 10 // 11 // Unless required by applicable law or agreed to in writing, software 12 // distributed under the License is distributed on an "AS IS" BASIS, 13 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 // See the License for the specific language governing permissions and 15 // limitations under the License. 16 17 #ifndef LIBSPIRV_OPT_INLINE_PASS_H_ 18 #define LIBSPIRV_OPT_INLINE_PASS_H_ 19 20 #include <algorithm> 21 #include <memory> 22 #include <unordered_map> 23 #include <vector> 24 #include <list> 25 26 #include "def_use_manager.h" 27 #include "module.h" 28 #include "pass.h" 29 30 namespace spvtools { 31 namespace opt { 32 33 // See optimizer.hpp for documentation. 34 class InlinePass : public Pass { 35 36 using cbb_ptr = const ir::BasicBlock*; 37 38 public: 39 using GetBlocksFunction = 40 std::function<std::vector<ir::BasicBlock*>*(const ir::BasicBlock*)>; 41 42 InlinePass(); 43 virtual ~InlinePass() = default; 44 45 protected: 46 // Return the next available Id and increment it. 47 inline uint32_t TakeNextId() { return next_id_++; } 48 49 // Write the next available Id back to the module. 50 inline void FinalizeNextId(ir::Module* module) { 51 module->SetIdBound(next_id_); 52 } 53 54 // Find pointer to type and storage in module, return its resultId, 55 // 0 if not found. TODO(greg-lunarg): Move this into type manager. 56 uint32_t FindPointerToType(uint32_t type_id, SpvStorageClass storage_class); 57 58 // Add pointer to type to module and return resultId. 59 uint32_t AddPointerToType(uint32_t type_id, SpvStorageClass storage_class); 60 61 // Add unconditional branch to labelId to end of block block_ptr. 62 void AddBranch(uint32_t labelId, std::unique_ptr<ir::BasicBlock>* block_ptr); 63 64 // Add conditional branch to end of block |block_ptr|. 65 void AddBranchCond(uint32_t cond_id, uint32_t true_id, 66 uint32_t false_id, std::unique_ptr<ir::BasicBlock>* block_ptr); 67 68 // Add unconditional branch to labelId to end of block block_ptr. 69 void AddLoopMerge(uint32_t merge_id, uint32_t continue_id, 70 std::unique_ptr<ir::BasicBlock>* block_ptr); 71 72 // Add store of valId to ptrId to end of block block_ptr. 73 void AddStore(uint32_t ptrId, uint32_t valId, 74 std::unique_ptr<ir::BasicBlock>* block_ptr); 75 76 // Add load of ptrId into resultId to end of block block_ptr. 77 void AddLoad(uint32_t typeId, uint32_t resultId, uint32_t ptrId, 78 std::unique_ptr<ir::BasicBlock>* block_ptr); 79 80 // Return new label. 81 std::unique_ptr<ir::Instruction> NewLabel(uint32_t label_id); 82 83 // Returns the id for the boolean false value. Looks in the module first 84 // and creates it if not found. Remembers it for future calls. 85 uint32_t GetFalseId(); 86 87 // Map callee params to caller args 88 void MapParams(ir::Function* calleeFn, 89 ir::UptrVectorIterator<ir::Instruction> call_inst_itr, 90 std::unordered_map<uint32_t, uint32_t>* callee2caller); 91 92 // Clone and map callee locals 93 void CloneAndMapLocals( 94 ir::Function* calleeFn, 95 std::vector<std::unique_ptr<ir::Instruction>>* new_vars, 96 std::unordered_map<uint32_t, uint32_t>* callee2caller); 97 98 // Create return variable for callee clone code if needed. Return id 99 // if created, otherwise 0. 100 uint32_t CreateReturnVar( 101 ir::Function* calleeFn, 102 std::vector<std::unique_ptr<ir::Instruction>>* new_vars); 103 104 // Return true if instruction must be in the same block that its result 105 // is used. 106 bool IsSameBlockOp(const ir::Instruction* inst) const; 107 108 // Clone operands which must be in same block as consumer instructions. 109 // Look in preCallSB for instructions that need cloning. Look in 110 // postCallSB for instructions already cloned. Add cloned instruction 111 // to postCallSB. 112 void CloneSameBlockOps( 113 std::unique_ptr<ir::Instruction>* inst, 114 std::unordered_map<uint32_t, uint32_t>* postCallSB, 115 std::unordered_map<uint32_t, ir::Instruction*>* preCallSB, 116 std::unique_ptr<ir::BasicBlock>* block_ptr); 117 118 // Return in new_blocks the result of inlining the call at call_inst_itr 119 // within its block at call_block_itr. The block at call_block_itr can 120 // just be replaced with the blocks in new_blocks. Any additional branches 121 // are avoided. Debug instructions are cloned along with their callee 122 // instructions. Early returns are replaced by a store to a local return 123 // variable and a branch to a (created) exit block where the local variable 124 // is returned. Formal parameters are trivially mapped to their actual 125 // parameters. Note that the first block in new_blocks retains the label 126 // of the original calling block. Also note that if an exit block is 127 // created, it is the last block of new_blocks. 128 // 129 // Also return in new_vars additional OpVariable instructions required by 130 // and to be inserted into the caller function after the block at 131 // call_block_itr is replaced with new_blocks. 132 void GenInlineCode(std::vector<std::unique_ptr<ir::BasicBlock>>* new_blocks, 133 std::vector<std::unique_ptr<ir::Instruction>>* new_vars, 134 ir::UptrVectorIterator<ir::Instruction> call_inst_itr, 135 ir::UptrVectorIterator<ir::BasicBlock> call_block_itr); 136 137 // Return true if |inst| is a function call that can be inlined. 138 bool IsInlinableFunctionCall(const ir::Instruction* inst); 139 140 // Returns the id of the merge block declared by a merge instruction in 141 // this block, if any. If none, returns zero. 142 uint32_t MergeBlockIdIfAny(const ir::BasicBlock& blk); 143 144 // Compute structured successors for function |func|. 145 // A block's structured successors are the blocks it branches to 146 // together with its declared merge block if it has one. 147 // When order matters, the merge block always appears first. 148 // This assures correct depth first search in the presence of early 149 // returns and kills. If the successor vector contain duplicates 150 // if the merge block, they are safely ignored by DFS. 151 void ComputeStructuredSuccessors(ir::Function* func); 152 153 // Return function to return ordered structure successors for a given block 154 // Assumes ComputeStructuredSuccessors() has been called. 155 GetBlocksFunction StructuredSuccessorsFunction(); 156 157 // Return true if |func| has multiple returns 158 bool HasMultipleReturns(ir::Function* func); 159 160 // Return true if |func| has no return in a loop. The current analysis 161 // requires structured control flow, so return false if control flow not 162 // structured ie. module is not a shader. 163 bool HasNoReturnInLoop(ir::Function* func); 164 165 // Find all functions with multiple returns and no returns in loops 166 void AnalyzeReturns(ir::Function* func); 167 168 // Return true if |func| is a function that can be inlined. 169 bool IsInlinableFunction(ir::Function* func); 170 171 // Update phis in succeeding blocks to point to new last block 172 void UpdateSucceedingPhis( 173 std::vector<std::unique_ptr<ir::BasicBlock>>& new_blocks); 174 175 // Initialize state for optimization of |module| 176 void InitializeInline(ir::Module* module); 177 178 // Module being processed by this pass 179 ir::Module* module_; 180 181 // Def/Use database 182 std::unique_ptr<analysis::DefUseManager> def_use_mgr_; 183 184 // Map from function's result id to function. 185 std::unordered_map<uint32_t, ir::Function*> id2function_; 186 187 // Map from block's label id to block. 188 std::unordered_map<uint32_t, ir::BasicBlock*> id2block_; 189 190 // Set of ids of functions with multiple returns. 191 std::set<uint32_t> multi_return_funcs_; 192 193 // Set of ids of functions with no returns in loop 194 std::set<uint32_t> no_return_in_loop_; 195 196 // Set of ids of inlinable functions 197 std::set<uint32_t> inlinable_; 198 199 // Map from block to its structured successor blocks. See 200 // ComputeStructuredSuccessors() for definition. 201 std::unordered_map<const ir::BasicBlock*, std::vector<ir::BasicBlock*>> 202 block2structured_succs_; 203 204 // result id for OpConstantFalse 205 uint32_t false_id_; 206 207 // Next unused ID 208 uint32_t next_id_; 209 }; 210 211 } // namespace opt 212 } // namespace spvtools 213 214 #endif // LIBSPIRV_OPT_INLINE_PASS_H_ 215
