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 SOURCE_OPT_INLINE_PASS_H_ 18 #define SOURCE_OPT_INLINE_PASS_H_ 19 20 #include <algorithm> 21 #include <list> 22 #include <memory> 23 #include <set> 24 #include <unordered_map> 25 #include <vector> 26 27 #include "source/opt/debug_info_manager.h" 28 #include "source/opt/decoration_manager.h" 29 #include "source/opt/module.h" 30 #include "source/opt/pass.h" 31 32 namespace spvtools { 33 namespace opt { 34 35 // See optimizer.hpp for documentation. 36 class InlinePass : public Pass { 37 using cbb_ptr = const BasicBlock*; 38 39 public: 40 virtual ~InlinePass() = default; 41 42 protected: 43 InlinePass(); 44 45 // Add pointer to type to module and return resultId. Returns 0 if the type 46 // could not be created. 47 uint32_t AddPointerToType(uint32_t type_id, SpvStorageClass storage_class); 48 49 // Add unconditional branch to labelId to end of block block_ptr. 50 void AddBranch(uint32_t labelId, std::unique_ptr<BasicBlock>* block_ptr); 51 52 // Add conditional branch to end of block |block_ptr|. 53 void AddBranchCond(uint32_t cond_id, uint32_t true_id, uint32_t false_id, 54 std::unique_ptr<BasicBlock>* block_ptr); 55 56 // Add unconditional branch to labelId to end of block block_ptr. 57 void AddLoopMerge(uint32_t merge_id, uint32_t continue_id, 58 std::unique_ptr<BasicBlock>* block_ptr); 59 60 // Add store of valId to ptrId to end of block block_ptr. 61 void AddStore(uint32_t ptrId, uint32_t valId, 62 std::unique_ptr<BasicBlock>* block_ptr, 63 const Instruction* line_inst, const DebugScope& dbg_scope); 64 65 // Add load of ptrId into resultId to end of block block_ptr. 66 void AddLoad(uint32_t typeId, uint32_t resultId, uint32_t ptrId, 67 std::unique_ptr<BasicBlock>* block_ptr, 68 const Instruction* line_inst, const DebugScope& dbg_scope); 69 70 // Return new label. 71 std::unique_ptr<Instruction> NewLabel(uint32_t label_id); 72 73 // Returns the id for the boolean false value. Looks in the module first 74 // and creates it if not found. Remembers it for future calls. Returns 0 if 75 // the value could not be created. 76 uint32_t GetFalseId(); 77 78 // Map callee params to caller args 79 void MapParams(Function* calleeFn, BasicBlock::iterator call_inst_itr, 80 std::unordered_map<uint32_t, uint32_t>* callee2caller); 81 82 // Clone and map callee locals. Return true if successful. 83 bool CloneAndMapLocals(Function* calleeFn, 84 std::vector<std::unique_ptr<Instruction>>* new_vars, 85 std::unordered_map<uint32_t, uint32_t>* callee2caller, 86 analysis::DebugInlinedAtContext* inlined_at_ctx); 87 88 // Create return variable for callee clone code. The return type of 89 // |calleeFn| must not be void. Returns the id of the return variable if 90 // created. Returns 0 if the return variable could not be created. 91 uint32_t CreateReturnVar(Function* calleeFn, 92 std::vector<std::unique_ptr<Instruction>>* new_vars); 93 94 // Return true if instruction must be in the same block that its result 95 // is used. 96 bool IsSameBlockOp(const Instruction* inst) const; 97 98 // Clone operands which must be in same block as consumer instructions. 99 // Look in preCallSB for instructions that need cloning. Look in 100 // postCallSB for instructions already cloned. Add cloned instruction 101 // to postCallSB. 102 bool CloneSameBlockOps(std::unique_ptr<Instruction>* inst, 103 std::unordered_map<uint32_t, uint32_t>* postCallSB, 104 std::unordered_map<uint32_t, Instruction*>* preCallSB, 105 std::unique_ptr<BasicBlock>* block_ptr); 106 107 // Return in new_blocks the result of inlining the call at call_inst_itr 108 // within its block at call_block_itr. The block at call_block_itr can 109 // just be replaced with the blocks in new_blocks. Any additional branches 110 // are avoided. Debug instructions are cloned along with their callee 111 // instructions. Early returns are replaced by a store to a local return 112 // variable and a branch to a (created) exit block where the local variable 113 // is returned. Formal parameters are trivially mapped to their actual 114 // parameters. Note that the first block in new_blocks retains the label 115 // of the original calling block. Also note that if an exit block is 116 // created, it is the last block of new_blocks. 117 // 118 // Also return in new_vars additional OpVariable instructions required by 119 // and to be inserted into the caller function after the block at 120 // call_block_itr is replaced with new_blocks. 121 // 122 // Returns true if successful. 123 bool GenInlineCode(std::vector<std::unique_ptr<BasicBlock>>* new_blocks, 124 std::vector<std::unique_ptr<Instruction>>* new_vars, 125 BasicBlock::iterator call_inst_itr, 126 UptrVectorIterator<BasicBlock> call_block_itr); 127 128 // Return true if |inst| is a function call that can be inlined. 129 bool IsInlinableFunctionCall(const Instruction* inst); 130 131 // Return true if |func| has no return in a loop. The current analysis 132 // requires structured control flow, so return false if control flow not 133 // structured ie. module is not a shader. 134 bool HasNoReturnInLoop(Function* func); 135 136 // Find all functions with multiple returns and no returns in loops 137 void AnalyzeReturns(Function* func); 138 139 // Return true if |func| is a function that can be inlined. 140 bool IsInlinableFunction(Function* func); 141 142 // Returns true if |func| contains an OpKill or OpTerminateInvocation 143 // instruction. 144 bool ContainsKillOrTerminateInvocation(Function* func) const; 145 146 // Update phis in succeeding blocks to point to new last block 147 void UpdateSucceedingPhis( 148 std::vector<std::unique_ptr<BasicBlock>>& new_blocks); 149 150 // Initialize state for optimization of |module| 151 void InitializeInline(); 152 153 // Map from function's result id to function. 154 std::unordered_map<uint32_t, Function*> id2function_; 155 156 // Map from block's label id to block. TODO(dnovillo): This is superfluous wrt 157 // CFG. It has functionality not present in CFG. Consolidate. 158 std::unordered_map<uint32_t, BasicBlock*> id2block_; 159 160 // Set of ids of functions with early return. 161 std::set<uint32_t> early_return_funcs_; 162 163 // Set of ids of functions with no returns in loop 164 std::set<uint32_t> no_return_in_loop_; 165 166 // Set of ids of inlinable functions 167 std::set<uint32_t> inlinable_; 168 169 // result id for OpConstantFalse 170 uint32_t false_id_; 171 172 // Set of functions that are originally called directly or indirectly from a 173 // continue construct. 174 std::unordered_set<uint32_t> funcs_called_from_continue_; 175 176 private: 177 // Moves instructions of the caller function up to the call instruction 178 // to |new_blk_ptr|. 179 void MoveInstsBeforeEntryBlock( 180 std::unordered_map<uint32_t, Instruction*>* preCallSB, 181 BasicBlock* new_blk_ptr, BasicBlock::iterator call_inst_itr, 182 UptrVectorIterator<BasicBlock> call_block_itr); 183 184 // Returns a new guard block after adding a branch to the end of 185 // |new_blocks|. 186 std::unique_ptr<BasicBlock> AddGuardBlock( 187 std::vector<std::unique_ptr<BasicBlock>>* new_blocks, 188 std::unordered_map<uint32_t, uint32_t>* callee2caller, 189 std::unique_ptr<BasicBlock> new_blk_ptr, uint32_t entry_blk_label_id); 190 191 // Add store instructions for initializers of variables. 192 InstructionList::iterator AddStoresForVariableInitializers( 193 const std::unordered_map<uint32_t, uint32_t>& callee2caller, 194 analysis::DebugInlinedAtContext* inlined_at_ctx, 195 std::unique_ptr<BasicBlock>* new_blk_ptr, 196 UptrVectorIterator<BasicBlock> callee_block_itr); 197 198 // Inlines a single instruction of the callee function. 199 bool InlineSingleInstruction( 200 const std::unordered_map<uint32_t, uint32_t>& callee2caller, 201 BasicBlock* new_blk_ptr, const Instruction* inst, 202 uint32_t dbg_inlined_at); 203 204 // Inlines the return instruction of the callee function. 205 std::unique_ptr<BasicBlock> InlineReturn( 206 const std::unordered_map<uint32_t, uint32_t>& callee2caller, 207 std::vector<std::unique_ptr<BasicBlock>>* new_blocks, 208 std::unique_ptr<BasicBlock> new_blk_ptr, 209 analysis::DebugInlinedAtContext* inlined_at_ctx, Function* calleeFn, 210 const Instruction* inst, uint32_t returnVarId); 211 212 // Inlines the entry block of the callee function. 213 bool InlineEntryBlock( 214 const std::unordered_map<uint32_t, uint32_t>& callee2caller, 215 std::unique_ptr<BasicBlock>* new_blk_ptr, 216 UptrVectorIterator<BasicBlock> callee_first_block, 217 analysis::DebugInlinedAtContext* inlined_at_ctx); 218 219 // Inlines basic blocks of the callee function other than the entry basic 220 // block. 221 std::unique_ptr<BasicBlock> InlineBasicBlocks( 222 std::vector<std::unique_ptr<BasicBlock>>* new_blocks, 223 const std::unordered_map<uint32_t, uint32_t>& callee2caller, 224 std::unique_ptr<BasicBlock> new_blk_ptr, 225 analysis::DebugInlinedAtContext* inlined_at_ctx, Function* calleeFn); 226 227 // Moves instructions of the caller function after the call instruction 228 // to |new_blk_ptr|. 229 bool MoveCallerInstsAfterFunctionCall( 230 std::unordered_map<uint32_t, Instruction*>* preCallSB, 231 std::unordered_map<uint32_t, uint32_t>* postCallSB, 232 std::unique_ptr<BasicBlock>* new_blk_ptr, 233 BasicBlock::iterator call_inst_itr, bool multiBlocks); 234 235 // Move the OpLoopMerge from the last block back to the first. 236 void MoveLoopMergeInstToFirstBlock( 237 std::vector<std::unique_ptr<BasicBlock>>* new_blocks); 238 }; 239 240 } // namespace opt 241 } // namespace spvtools 242 243 #endif // SOURCE_OPT_INLINE_PASS_H_ 244