Debian Codegraph @

third_party/spirv-tools/source/opt/inline_pass.h

raw
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_