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/decoration_manager.h" 28 #include "source/opt/module.h" 29 #include "source/opt/pass.h" 30 31 namespace spvtools { 32 namespace opt { 33 34 // See optimizer.hpp for documentation. 35 class InlinePass : public Pass { 36 using cbb_ptr = const BasicBlock*; 37 38 public: 39 virtual ~InlinePass() = default; 40 41 protected: 42 InlinePass(); 43 44 // Add pointer to type to module and return resultId. 45 uint32_t AddPointerToType(uint32_t type_id, SpvStorageClass storage_class); 46 47 // Add unconditional branch to labelId to end of block block_ptr. 48 void AddBranch(uint32_t labelId, std::unique_ptr<BasicBlock>* block_ptr); 49 50 // Add conditional branch to end of block |block_ptr|. 51 void AddBranchCond(uint32_t cond_id, uint32_t true_id, uint32_t false_id, 52 std::unique_ptr<BasicBlock>* block_ptr); 53 54 // Add unconditional branch to labelId to end of block block_ptr. 55 void AddLoopMerge(uint32_t merge_id, uint32_t continue_id, 56 std::unique_ptr<BasicBlock>* block_ptr); 57 58 // Add store of valId to ptrId to end of block block_ptr. 59 void AddStore(uint32_t ptrId, uint32_t valId, 60 std::unique_ptr<BasicBlock>* block_ptr); 61 62 // Add load of ptrId into resultId to end of block block_ptr. 63 void AddLoad(uint32_t typeId, uint32_t resultId, uint32_t ptrId, 64 std::unique_ptr<BasicBlock>* block_ptr); 65 66 // Return new label. 67 std::unique_ptr<Instruction> NewLabel(uint32_t label_id); 68 69 // Returns the id for the boolean false value. Looks in the module first 70 // and creates it if not found. Remembers it for future calls. 71 uint32_t GetFalseId(); 72 73 // Map callee params to caller args 74 void MapParams(Function* calleeFn, BasicBlock::iterator call_inst_itr, 75 std::unordered_map<uint32_t, uint32_t>* callee2caller); 76 77 // Clone and map callee locals 78 void CloneAndMapLocals(Function* calleeFn, 79 std::vector<std::unique_ptr<Instruction>>* new_vars, 80 std::unordered_map<uint32_t, uint32_t>* callee2caller); 81 82 // Create return variable for callee clone code if needed. Return id 83 // if created, otherwise 0. 84 uint32_t CreateReturnVar(Function* calleeFn, 85 std::vector<std::unique_ptr<Instruction>>* new_vars); 86 87 // Return true if instruction must be in the same block that its result 88 // is used. 89 bool IsSameBlockOp(const Instruction* inst) const; 90 91 // Clone operands which must be in same block as consumer instructions. 92 // Look in preCallSB for instructions that need cloning. Look in 93 // postCallSB for instructions already cloned. Add cloned instruction 94 // to postCallSB. 95 void CloneSameBlockOps(std::unique_ptr<Instruction>* inst, 96 std::unordered_map<uint32_t, uint32_t>* postCallSB, 97 std::unordered_map<uint32_t, Instruction*>* preCallSB, 98 std::unique_ptr<BasicBlock>* block_ptr); 99 100 // Return in new_blocks the result of inlining the call at call_inst_itr 101 // within its block at call_block_itr. The block at call_block_itr can 102 // just be replaced with the blocks in new_blocks. Any additional branches 103 // are avoided. Debug instructions are cloned along with their callee 104 // instructions. Early returns are replaced by a store to a local return 105 // variable and a branch to a (created) exit block where the local variable 106 // is returned. Formal parameters are trivially mapped to their actual 107 // parameters. Note that the first block in new_blocks retains the label 108 // of the original calling block. Also note that if an exit block is 109 // created, it is the last block of new_blocks. 110 // 111 // Also return in new_vars additional OpVariable instructions required by 112 // and to be inserted into the caller function after the block at 113 // call_block_itr is replaced with new_blocks. 114 void GenInlineCode(std::vector<std::unique_ptr<BasicBlock>>* new_blocks, 115 std::vector<std::unique_ptr<Instruction>>* new_vars, 116 BasicBlock::iterator call_inst_itr, 117 UptrVectorIterator<BasicBlock> call_block_itr); 118 119 // Return true if |inst| is a function call that can be inlined. 120 bool IsInlinableFunctionCall(const Instruction* inst); 121 122 // Return true if |func| does not have a return that is 123 // nested in a structured if, switch or loop. 124 bool HasNoReturnInStructuredConstruct(Function* func); 125 126 // Return true if |func| has no return in a loop. The current analysis 127 // requires structured control flow, so return false if control flow not 128 // structured ie. module is not a shader. 129 bool HasNoReturnInLoop(Function* func); 130 131 // Find all functions with multiple returns and no returns in loops 132 void AnalyzeReturns(Function* func); 133 134 // Return true if |func| is a function that can be inlined. 135 bool IsInlinableFunction(Function* func); 136 137 // Update phis in succeeding blocks to point to new last block 138 void UpdateSucceedingPhis( 139 std::vector<std::unique_ptr<BasicBlock>>& new_blocks); 140 141 // Initialize state for optimization of |module| 142 void InitializeInline(); 143 144 // Map from function's result id to function. 145 std::unordered_map<uint32_t, Function*> id2function_; 146 147 // Map from block's label id to block. TODO(dnovillo): This is superfluous wrt 148 // CFG. It has functionality not present in CFG. Consolidate. 149 std::unordered_map<uint32_t, BasicBlock*> id2block_; 150 151 // Set of ids of functions with early return. 152 std::set<uint32_t> early_return_funcs_; 153 154 // Set of ids of functions with no returns in loop 155 std::set<uint32_t> no_return_in_loop_; 156 157 // Set of ids of inlinable functions 158 std::set<uint32_t> inlinable_; 159 160 // result id for OpConstantFalse 161 uint32_t false_id_; 162 }; 163 164 } // namespace opt 165 } // namespace spvtools 166 167 #endif // SOURCE_OPT_INLINE_PASS_H_ 168
