Debian Codegraph @

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

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 #include "source/opt/inline_pass.h"
18
19 #include <unordered_set>
20 #include <utility>
21
22 #include "source/cfa.h"
23 #include "source/opt/reflect.h"
24 #include "source/util/make_unique.h"
25
26 // Indices of operands in SPIR-V instructions
27
28 static const int kSpvFunctionCallFunctionId = 2;
29 static const int kSpvFunctionCallArgumentId = 3;
30 static const int kSpvReturnValueId = 0;
31
32 namespace spvtools {
33 namespace opt {
34
35 uint32_t InlinePass::AddPointerToType(uint32_t type_id,
36 SpvStorageClass storage_class) {
37 uint32_t resultId = context()->TakeNextId();
38 if (resultId == 0) {
39 return resultId;
40 }
41
42 std::unique_ptr<Instruction> type_inst(
43 new Instruction(context(), SpvOpTypePointer, 0, resultId,
44 {{spv_operand_type_t::SPV_OPERAND_TYPE_STORAGE_CLASS,
45 {uint32_t(storage_class)}},
46 {spv_operand_type_t::SPV_OPERAND_TYPE_ID, {type_id}}}));
47 context()->AddType(std::move(type_inst));
48 analysis::Type* pointeeTy;
49 std::unique_ptr<analysis::Pointer> pointerTy;
50 std::tie(pointeeTy, pointerTy) =
51 context()->get_type_mgr()->GetTypeAndPointerType(type_id,
52 SpvStorageClassFunction);
53 context()->get_type_mgr()->RegisterType(resultId, *pointerTy);
54 return resultId;
55 }
56
57 void InlinePass::AddBranch(uint32_t label_id,
58 std::unique_ptr<BasicBlock>* block_ptr) {
59 std::unique_ptr<Instruction> newBranch(
60 new Instruction(context(), SpvOpBranch, 0, 0,
61 {{spv_operand_type_t::SPV_OPERAND_TYPE_ID, {label_id}}}));
62 (*block_ptr)->AddInstruction(std::move(newBranch));
63 }
64
65 void InlinePass::AddBranchCond(uint32_t cond_id, uint32_t true_id,
66 uint32_t false_id,
67 std::unique_ptr<BasicBlock>* block_ptr) {
68 std::unique_ptr<Instruction> newBranch(
69 new Instruction(context(), SpvOpBranchConditional, 0, 0,
70 {{spv_operand_type_t::SPV_OPERAND_TYPE_ID, {cond_id}},
71 {spv_operand_type_t::SPV_OPERAND_TYPE_ID, {true_id}},
72 {spv_operand_type_t::SPV_OPERAND_TYPE_ID, {false_id}}}));
73 (*block_ptr)->AddInstruction(std::move(newBranch));
74 }
75
76 void InlinePass::AddLoopMerge(uint32_t merge_id, uint32_t continue_id,
77 std::unique_ptr<BasicBlock>* block_ptr) {
78 std::unique_ptr<Instruction> newLoopMerge(new Instruction(
79 context(), SpvOpLoopMerge, 0, 0,
80 {{spv_operand_type_t::SPV_OPERAND_TYPE_ID, {merge_id}},
81 {spv_operand_type_t::SPV_OPERAND_TYPE_ID, {continue_id}},
82 {spv_operand_type_t::SPV_OPERAND_TYPE_LOOP_CONTROL, {0}}}));
83 (*block_ptr)->AddInstruction(std::move(newLoopMerge));
84 }
85
86 void InlinePass::AddStore(uint32_t ptr_id, uint32_t val_id,
87 std::unique_ptr<BasicBlock>* block_ptr,
88 const Instruction* line_inst,
89 const DebugScope& dbg_scope) {
90 std::unique_ptr<Instruction> newStore(
91 new Instruction(context(), SpvOpStore, 0, 0,
92 {{spv_operand_type_t::SPV_OPERAND_TYPE_ID, {ptr_id}},
93 {spv_operand_type_t::SPV_OPERAND_TYPE_ID, {val_id}}}));
94 if (line_inst != nullptr) {
95 newStore->dbg_line_insts().push_back(*line_inst);
96 }
97 newStore->SetDebugScope(dbg_scope);
98 (*block_ptr)->AddInstruction(std::move(newStore));
99 }
100
101 void InlinePass::AddLoad(uint32_t type_id, uint32_t resultId, uint32_t ptr_id,
102 std::unique_ptr<BasicBlock>* block_ptr,
103 const Instruction* line_inst,
104 const DebugScope& dbg_scope) {
105 std::unique_ptr<Instruction> newLoad(
106 new Instruction(context(), SpvOpLoad, type_id, resultId,
107 {{spv_operand_type_t::SPV_OPERAND_TYPE_ID, {ptr_id}}}));
108 if (line_inst != nullptr) {
109 newLoad->dbg_line_insts().push_back(*line_inst);
110 }
111 newLoad->SetDebugScope(dbg_scope);
112 (*block_ptr)->AddInstruction(std::move(newLoad));
113 }
114
115 std::unique_ptr<Instruction> InlinePass::NewLabel(uint32_t label_id) {
116 std::unique_ptr<Instruction> newLabel(
117 new Instruction(context(), SpvOpLabel, 0, label_id, {}));
118 return newLabel;
119 }
120
121 uint32_t InlinePass::GetFalseId() {
122 if (false_id_ != 0) return false_id_;
123 false_id_ = get_module()->GetGlobalValue(SpvOpConstantFalse);
124 if (false_id_ != 0) return false_id_;
125 uint32_t boolId = get_module()->GetGlobalValue(SpvOpTypeBool);
126 if (boolId == 0) {
127 boolId = context()->TakeNextId();
128 if (boolId == 0) {
129 return 0;
130 }
131 get_module()->AddGlobalValue(SpvOpTypeBool, boolId, 0);
132 }
133 false_id_ = context()->TakeNextId();
134 if (false_id_ == 0) {
135 return 0;
136 }
137 get_module()->AddGlobalValue(SpvOpConstantFalse, false_id_, boolId);
138 return false_id_;
139 }
140
141 void InlinePass::MapParams(
142 Function* calleeFn, BasicBlock::iterator call_inst_itr,
143 std::unordered_map<uint32_t, uint32_t>* callee2caller) {
144 int param_idx = 0;
145 calleeFn->ForEachParam(
146 [&call_inst_itr, &param_idx, &callee2caller](const Instruction* cpi) {
147 const uint32_t pid = cpi->result_id();
148 (*callee2caller)[pid] = call_inst_itr->GetSingleWordOperand(
149 kSpvFunctionCallArgumentId + param_idx);
150 ++param_idx;
151 });
152 }
153
154 bool InlinePass::CloneAndMapLocals(
155 Function* calleeFn, std::vector<std::unique_ptr<Instruction>>* new_vars,
156 std::unordered_map<uint32_t, uint32_t>* callee2caller,
157 analysis::DebugInlinedAtContext* inlined_at_ctx) {
158 auto callee_block_itr = calleeFn->begin();
159 auto callee_var_itr = callee_block_itr->begin();
160 while (callee_var_itr->opcode() == SpvOp::SpvOpVariable ||
161 callee_var_itr->GetOpenCL100DebugOpcode() ==
162 OpenCLDebugInfo100DebugDeclare) {
163 if (callee_var_itr->opcode() != SpvOp::SpvOpVariable) {
164 ++callee_var_itr;
165 continue;
166 }
167
168 std::unique_ptr<Instruction> var_inst(callee_var_itr->Clone(context()));
169 uint32_t newId = context()->TakeNextId();
170 if (newId == 0) {
171 return false;
172 }
173 get_decoration_mgr()->CloneDecorations(callee_var_itr->result_id(), newId);
174 var_inst->SetResultId(newId);
175 var_inst->UpdateDebugInlinedAt(
176 context()->get_debug_info_mgr()->BuildDebugInlinedAtChain(
177 callee_var_itr->GetDebugInlinedAt(), inlined_at_ctx));
178 (*callee2caller)[callee_var_itr->result_id()] = newId;
179 new_vars->push_back(std::move(var_inst));
180 ++callee_var_itr;
181 }
182 return true;
183 }
184
185 uint32_t InlinePass::CreateReturnVar(
186 Function* calleeFn, std::vector<std::unique_ptr<Instruction>>* new_vars) {
187 uint32_t returnVarId = 0;
188 const uint32_t calleeTypeId = calleeFn->type_id();
189 analysis::TypeManager* type_mgr = context()->get_type_mgr();
190 assert(type_mgr->GetType(calleeTypeId)->AsVoid() == nullptr &&
191 "Cannot create a return variable of type void.");
192 // Find or create ptr to callee return type.
193 uint32_t returnVarTypeId =
194 type_mgr->FindPointerToType(calleeTypeId, SpvStorageClassFunction);
195
196 if (returnVarTypeId == 0) {
197 returnVarTypeId = AddPointerToType(calleeTypeId, SpvStorageClassFunction);
198 if (returnVarTypeId == 0) {
199 return 0;
200 }
201 }
202
203 // Add return var to new function scope variables.
204 returnVarId = context()->TakeNextId();
205 if (returnVarId == 0) {
206 return 0;
207 }
208
209 std::unique_ptr<Instruction> var_inst(
210 new Instruction(context(), SpvOpVariable, returnVarTypeId, returnVarId,
211 {{spv_operand_type_t::SPV_OPERAND_TYPE_STORAGE_CLASS,
212 {SpvStorageClassFunction}}}));
213 new_vars->push_back(std::move(var_inst));
214 get_decoration_mgr()->CloneDecorations(calleeFn->result_id(), returnVarId);
215 return returnVarId;
216 }
217
218 bool InlinePass::IsSameBlockOp(const Instruction* inst) const {
219 return inst->opcode() == SpvOpSampledImage || inst->opcode() == SpvOpImage;
220 }
221
222 bool InlinePass::CloneSameBlockOps(
223 std::unique_ptr<Instruction>* inst,
224 std::unordered_map<uint32_t, uint32_t>* postCallSB,
225 std::unordered_map<uint32_t, Instruction*>* preCallSB,
226 std::unique_ptr<BasicBlock>* block_ptr) {
227 return (*inst)->WhileEachInId([&postCallSB, &preCallSB, &block_ptr,
228 this](uint32_t* iid) {
229 const auto mapItr = (*postCallSB).find(*iid);
230 if (mapItr == (*postCallSB).end()) {
231 const auto mapItr2 = (*preCallSB).find(*iid);
232 if (mapItr2 != (*preCallSB).end()) {
233 // Clone pre-call same-block ops, map result id.
234 const Instruction* inInst = mapItr2->second;
235 std::unique_ptr<Instruction> sb_inst(inInst->Clone(context()));
236 if (!CloneSameBlockOps(&sb_inst, postCallSB, preCallSB, block_ptr)) {
237 return false;
238 }
239
240 const uint32_t rid = sb_inst->result_id();
241 const uint32_t nid = context()->TakeNextId();
242 if (nid == 0) {
243 return false;
244 }
245 get_decoration_mgr()->CloneDecorations(rid, nid);
246 sb_inst->SetResultId(nid);
247 (*postCallSB)[rid] = nid;
248 *iid = nid;
249 (*block_ptr)->AddInstruction(std::move(sb_inst));
250 }
251 } else {
252 // Reset same-block op operand.
253 *iid = mapItr->second;
254 }
255 return true;
256 });
257 }
258
259 void InlinePass::MoveInstsBeforeEntryBlock(
260 std::unordered_map<uint32_t, Instruction*>* preCallSB,
261 BasicBlock* new_blk_ptr, BasicBlock::iterator call_inst_itr,
262 UptrVectorIterator<BasicBlock> call_block_itr) {
263 for (auto cii = call_block_itr->begin(); cii != call_inst_itr;
264 cii = call_block_itr->begin()) {
265 Instruction* inst = &*cii;
266 inst->RemoveFromList();
267 std::unique_ptr<Instruction> cp_inst(inst);
268 // Remember same-block ops for possible regeneration.
269 if (IsSameBlockOp(&*cp_inst)) {
270 auto* sb_inst_ptr = cp_inst.get();
271 (*preCallSB)[cp_inst->result_id()] = sb_inst_ptr;
272 }
273 new_blk_ptr->AddInstruction(std::move(cp_inst));
274 }
275 }
276
277 std::unique_ptr<BasicBlock> InlinePass::AddGuardBlock(
278 std::vector<std::unique_ptr<BasicBlock>>* new_blocks,
279 std::unordered_map<uint32_t, uint32_t>* callee2caller,
280 std::unique_ptr<BasicBlock> new_blk_ptr, uint32_t entry_blk_label_id) {
281 const auto guard_block_id = context()->TakeNextId();
282 if (guard_block_id == 0) {
283 return nullptr;
284 }
285 AddBranch(guard_block_id, &new_blk_ptr);
286 new_blocks->push_back(std::move(new_blk_ptr));
287 // Start the next block.
288 new_blk_ptr = MakeUnique<BasicBlock>(NewLabel(guard_block_id));
289 // Reset the mapping of the callee's entry block to point to
290 // the guard block. Do this so we can fix up phis later on to
291 // satisfy dominance.
292 (*callee2caller)[entry_blk_label_id] = guard_block_id;
293 return new_blk_ptr;
294 }
295
296 InstructionList::iterator InlinePass::AddStoresForVariableInitializers(
297 const std::unordered_map<uint32_t, uint32_t>& callee2caller,
298 analysis::DebugInlinedAtContext* inlined_at_ctx,
299 std::unique_ptr<BasicBlock>* new_blk_ptr,
300 UptrVectorIterator<BasicBlock> callee_first_block_itr) {
301 auto callee_itr = callee_first_block_itr->begin();
302 while (callee_itr->opcode() == SpvOp::SpvOpVariable ||
303 callee_itr->GetOpenCL100DebugOpcode() ==
304 OpenCLDebugInfo100DebugDeclare) {
305 if (callee_itr->opcode() == SpvOp::SpvOpVariable &&
306 callee_itr->NumInOperands() == 2) {
307 assert(callee2caller.count(callee_itr->result_id()) &&
308 "Expected the variable to have already been mapped.");
309 uint32_t new_var_id = callee2caller.at(callee_itr->result_id());
310
311 // The initializer must be a constant or global value. No mapped
312 // should be used.
313 uint32_t val_id = callee_itr->GetSingleWordInOperand(1);
314 AddStore(new_var_id, val_id, new_blk_ptr, callee_itr->dbg_line_inst(),
315 context()->get_debug_info_mgr()->BuildDebugScope(
316 callee_itr->GetDebugScope(), inlined_at_ctx));
317 }
318 if (callee_itr->GetOpenCL100DebugOpcode() ==
319 OpenCLDebugInfo100DebugDeclare) {
320 InlineSingleInstruction(
321 callee2caller, new_blk_ptr->get(), &*callee_itr,
322 context()->get_debug_info_mgr()->BuildDebugInlinedAtChain(
323 callee_itr->GetDebugScope().GetInlinedAt(), inlined_at_ctx));
324 }
325 ++callee_itr;
326 }
327 return callee_itr;
328 }
329
330 bool InlinePass::InlineSingleInstruction(
331 const std::unordered_map<uint32_t, uint32_t>& callee2caller,
332 BasicBlock* new_blk_ptr, const Instruction* inst, uint32_t dbg_inlined_at) {
333 // If we have return, it must be at the end of the callee. We will handle
334 // it at the end.
335 if (inst->opcode() == SpvOpReturnValue || inst->opcode() == SpvOpReturn)
336 return true;
337
338 // Copy callee instruction and remap all input Ids.
339 std::unique_ptr<Instruction> cp_inst(inst->Clone(context()));
340 cp_inst->ForEachInId([&callee2caller](uint32_t* iid) {
341 const auto mapItr = callee2caller.find(*iid);
342 if (mapItr != callee2caller.end()) {
343 *iid = mapItr->second;
344 }
345 });
346
347 // If result id is non-zero, remap it.
348 const uint32_t rid = cp_inst->result_id();
349 if (rid != 0) {
350 const auto mapItr = callee2caller.find(rid);
351 if (mapItr == callee2caller.end()) {
352 return false;
353 }
354 uint32_t nid = mapItr->second;
355 cp_inst->SetResultId(nid);
356 get_decoration_mgr()->CloneDecorations(rid, nid);
357 }
358
359 cp_inst->UpdateDebugInlinedAt(dbg_inlined_at);
360 new_blk_ptr->AddInstruction(std::move(cp_inst));
361 return true;
362 }
363
364 std::unique_ptr<BasicBlock> InlinePass::InlineReturn(
365 const std::unordered_map<uint32_t, uint32_t>& callee2caller,
366 std::vector<std::unique_ptr<BasicBlock>>* new_blocks,
367 std::unique_ptr<BasicBlock> new_blk_ptr,
368 analysis::DebugInlinedAtContext* inlined_at_ctx, Function* calleeFn,
369 const Instruction* inst, uint32_t returnVarId) {
370 // Store return value to return variable.
371 if (inst->opcode() == SpvOpReturnValue) {
372 assert(returnVarId != 0);
373 uint32_t valId = inst->GetInOperand(kSpvReturnValueId).words[0];
374 const auto mapItr = callee2caller.find(valId);
375 if (mapItr != callee2caller.end()) {
376 valId = mapItr->second;
377 }
378 AddStore(returnVarId, valId, &new_blk_ptr, inst->dbg_line_inst(),
379 context()->get_debug_info_mgr()->BuildDebugScope(
380 inst->GetDebugScope(), inlined_at_ctx));
381 }
382
383 uint32_t returnLabelId = 0;
384 for (auto callee_block_itr = calleeFn->begin();
385 callee_block_itr != calleeFn->end(); ++callee_block_itr) {
386 if (callee_block_itr->tail()->opcode() == SpvOpUnreachable ||
387 callee_block_itr->tail()->opcode() == SpvOpKill ||
388 callee_block_itr->tail()->opcode() == SpvOpTerminateInvocation) {
389 returnLabelId = context()->TakeNextId();
390 break;
391 }
392 }
393 if (returnLabelId == 0) return new_blk_ptr;
394
395 if (inst->opcode() == SpvOpReturn || inst->opcode() == SpvOpReturnValue)
396 AddBranch(returnLabelId, &new_blk_ptr);
397 new_blocks->push_back(std::move(new_blk_ptr));
398 return MakeUnique<BasicBlock>(NewLabel(returnLabelId));
399 }
400
401 bool InlinePass::InlineEntryBlock(
402 const std::unordered_map<uint32_t, uint32_t>& callee2caller,
403 std::unique_ptr<BasicBlock>* new_blk_ptr,
404 UptrVectorIterator<BasicBlock> callee_first_block,
405 analysis::DebugInlinedAtContext* inlined_at_ctx) {
406 auto callee_inst_itr = AddStoresForVariableInitializers(
407 callee2caller, inlined_at_ctx, new_blk_ptr, callee_first_block);
408
409 while (callee_inst_itr != callee_first_block->end()) {
410 if (!InlineSingleInstruction(
411 callee2caller, new_blk_ptr->get(), &*callee_inst_itr,
412 context()->get_debug_info_mgr()->BuildDebugInlinedAtChain(
413 callee_inst_itr->GetDebugScope().GetInlinedAt(),
414 inlined_at_ctx))) {
415 return false;
416 }
417 ++callee_inst_itr;
418 }
419 return true;
420 }
421
422 std::unique_ptr<BasicBlock> InlinePass::InlineBasicBlocks(
423 std::vector<std::unique_ptr<BasicBlock>>* new_blocks,
424 const std::unordered_map<uint32_t, uint32_t>& callee2caller,
425 std::unique_ptr<BasicBlock> new_blk_ptr,
426 analysis::DebugInlinedAtContext* inlined_at_ctx, Function* calleeFn) {
427 auto callee_block_itr = calleeFn->begin();
428 ++callee_block_itr;
429
430 while (callee_block_itr != calleeFn->end()) {
431 new_blocks->push_back(std::move(new_blk_ptr));
432 const auto mapItr =
433 callee2caller.find(callee_block_itr->GetLabelInst()->result_id());
434 if (mapItr == callee2caller.end()) return nullptr;
435 new_blk_ptr = MakeUnique<BasicBlock>(NewLabel(mapItr->second));
436
437 auto tail_inst_itr = callee_block_itr->end();
438 for (auto inst_itr = callee_block_itr->begin(); inst_itr != tail_inst_itr;
439 ++inst_itr) {
440 if (!InlineSingleInstruction(
441 callee2caller, new_blk_ptr.get(), &*inst_itr,
442 context()->get_debug_info_mgr()->BuildDebugInlinedAtChain(
443 inst_itr->GetDebugScope().GetInlinedAt(), inlined_at_ctx))) {
444 return nullptr;
445 }
446 }
447
448 ++callee_block_itr;
449 }
450 return new_blk_ptr;
451 }
452
453 bool InlinePass::MoveCallerInstsAfterFunctionCall(
454 std::unordered_map<uint32_t, Instruction*>* preCallSB,
455 std::unordered_map<uint32_t, uint32_t>* postCallSB,
456 std::unique_ptr<BasicBlock>* new_blk_ptr,
457 BasicBlock::iterator call_inst_itr, bool multiBlocks) {
458 // Copy remaining instructions from caller block.
459 for (Instruction* inst = call_inst_itr->NextNode(); inst;
460 inst = call_inst_itr->NextNode()) {
461 inst->RemoveFromList();
462 std::unique_ptr<Instruction> cp_inst(inst);
463 // If multiple blocks generated, regenerate any same-block
464 // instruction that has not been seen in this last block.
465 if (multiBlocks) {
466 if (!CloneSameBlockOps(&cp_inst, postCallSB, preCallSB, new_blk_ptr)) {
467 return false;
468 }
469
470 // Remember same-block ops in this block.
471 if (IsSameBlockOp(&*cp_inst)) {
472 const uint32_t rid = cp_inst->result_id();
473 (*postCallSB)[rid] = rid;
474 }
475 }
476 new_blk_ptr->get()->AddInstruction(std::move(cp_inst));
477 }
478
479 return true;
480 }
481
482 void InlinePass::MoveLoopMergeInstToFirstBlock(
483 std::vector<std::unique_ptr<BasicBlock>>* new_blocks) {
484 // Move the OpLoopMerge from the last block back to the first, where
485 // it belongs.
486 auto& first = new_blocks->front();
487 auto& last = new_blocks->back();
488 assert(first != last);
489
490 // Insert a modified copy of the loop merge into the first block.
491 auto loop_merge_itr = last->tail();
492 --loop_merge_itr;
493 assert(loop_merge_itr->opcode() == SpvOpLoopMerge);
494 std::unique_ptr<Instruction> cp_inst(loop_merge_itr->Clone(context()));
495 first->tail().InsertBefore(std::move(cp_inst));
496
497 // Remove the loop merge from the last block.
498 loop_merge_itr->RemoveFromList();
499 delete &*loop_merge_itr;
500 }
501
502 bool InlinePass::GenInlineCode(
503 std::vector<std::unique_ptr<BasicBlock>>* new_blocks,
504 std::vector<std::unique_ptr<Instruction>>* new_vars,
505 BasicBlock::iterator call_inst_itr,
506 UptrVectorIterator<BasicBlock> call_block_itr) {
507 // Map from all ids in the callee to their equivalent id in the caller
508 // as callee instructions are copied into caller.
509 std::unordered_map<uint32_t, uint32_t> callee2caller;
510 // Pre-call same-block insts
511 std::unordered_map<uint32_t, Instruction*> preCallSB;
512 // Post-call same-block op ids
513 std::unordered_map<uint32_t, uint32_t> postCallSB;
514
515 analysis::DebugInlinedAtContext inlined_at_ctx(&*call_inst_itr);
516
517 // Invalidate the def-use chains. They are not kept up to date while
518 // inlining. However, certain calls try to keep them up-to-date if they are
519 // valid. These operations can fail.
520 context()->InvalidateAnalyses(IRContext::kAnalysisDefUse);
521
522 // If the caller is a loop header and the callee has multiple blocks, then the
523 // normal inlining logic will place the OpLoopMerge in the last of several
524 // blocks in the loop. Instead, it should be placed at the end of the first
525 // block. We'll wait to move the OpLoopMerge until the end of the regular
526 // inlining logic, and only if necessary.
527 bool caller_is_loop_header = call_block_itr->GetLoopMergeInst() != nullptr;
528
529 // Single-trip loop continue block
530 std::unique_ptr<BasicBlock> single_trip_loop_cont_blk;
531
532 Function* calleeFn = id2function_[call_inst_itr->GetSingleWordOperand(
533 kSpvFunctionCallFunctionId)];
534
535 // Map parameters to actual arguments.
536 MapParams(calleeFn, call_inst_itr, &callee2caller);
537
538 // Define caller local variables for all callee variables and create map to
539 // them.
540 if (!CloneAndMapLocals(calleeFn, new_vars, &callee2caller, &inlined_at_ctx)) {
541 return false;
542 }
543
544 // First block needs to use label of original block
545 // but map callee label in case of phi reference.
546 uint32_t entry_blk_label_id = calleeFn->begin()->GetLabelInst()->result_id();
547 callee2caller[entry_blk_label_id] = call_block_itr->id();
548 std::unique_ptr<BasicBlock> new_blk_ptr =
549 MakeUnique<BasicBlock>(NewLabel(call_block_itr->id()));
550
551 // Move instructions of original caller block up to call instruction.
552 MoveInstsBeforeEntryBlock(&preCallSB, new_blk_ptr.get(), call_inst_itr,
553 call_block_itr);
554
555 if (caller_is_loop_header &&
556 (*(calleeFn->begin())).GetMergeInst() != nullptr) {
557 // We can't place both the caller's merge instruction and
558 // another merge instruction in the same block. So split the
559 // calling block. Insert an unconditional branch to a new guard
560 // block. Later, once we know the ID of the last block, we
561 // will move the caller's OpLoopMerge from the last generated
562 // block into the first block. We also wait to avoid
563 // invalidating various iterators.
564 new_blk_ptr = AddGuardBlock(new_blocks, &callee2caller,
565 std::move(new_blk_ptr), entry_blk_label_id);
566 if (new_blk_ptr == nullptr) return false;
567 }
568
569 // Create return var if needed.
570 const uint32_t calleeTypeId = calleeFn->type_id();
571 uint32_t returnVarId = 0;
572 analysis::Type* calleeType = context()->get_type_mgr()->GetType(calleeTypeId);
573 if (calleeType->AsVoid() == nullptr) {
574 returnVarId = CreateReturnVar(calleeFn, new_vars);
575 if (returnVarId == 0) {
576 return false;
577 }
578 }
579
580 calleeFn->WhileEachInst([&callee2caller, this](const Instruction* cpi) {
581 // Create set of callee result ids. Used to detect forward references
582 const uint32_t rid = cpi->result_id();
583 if (rid != 0 && callee2caller.find(rid) == callee2caller.end()) {
584 const uint32_t nid = context()->TakeNextId();
585 if (nid == 0) return false;
586 callee2caller[rid] = nid;
587 }
588 return true;
589 });
590
591 // Inline DebugClare instructions in the callee's header.
592 calleeFn->ForEachDebugInstructionsInHeader(
593 [&new_blk_ptr, &callee2caller, &inlined_at_ctx, this](Instruction* inst) {
594 InlineSingleInstruction(
595 callee2caller, new_blk_ptr.get(), inst,
596 context()->get_debug_info_mgr()->BuildDebugInlinedAtChain(
597 inst->GetDebugScope().GetInlinedAt(), &inlined_at_ctx));
598 });
599
600 // Inline the entry block of the callee function.
601 if (!InlineEntryBlock(callee2caller, &new_blk_ptr, calleeFn->begin(),
602 &inlined_at_ctx)) {
603 return false;
604 }
605
606 // Inline blocks of the callee function other than the entry block.
607 new_blk_ptr =
608 InlineBasicBlocks(new_blocks, callee2caller, std::move(new_blk_ptr),
609 &inlined_at_ctx, calleeFn);
610 if (new_blk_ptr == nullptr) return false;
611
612 new_blk_ptr = InlineReturn(callee2caller, new_blocks, std::move(new_blk_ptr),
613 &inlined_at_ctx, calleeFn,
614 &*(calleeFn->tail()->tail()), returnVarId);
615
616 // Load return value into result id of call, if it exists.
617 if (returnVarId != 0) {
618 const uint32_t resId = call_inst_itr->result_id();
619 assert(resId != 0);
620 AddLoad(calleeTypeId, resId, returnVarId, &new_blk_ptr,
621 call_inst_itr->dbg_line_inst(), call_inst_itr->GetDebugScope());
622 } else {
623 // Even though it is very unlikely, it is possible that the result id of
624 // the void-function call is used, so we need to generate an instruction
625 // with that result id.
626 std::unique_ptr<Instruction> undef_inst(
627 new Instruction(context(), SpvOpUndef, call_inst_itr->type_id(),
628 call_inst_itr->result_id(), {}));
629 context()->AddGlobalValue(std::move(undef_inst));
630 }
631
632 // Move instructions of original caller block after call instruction.
633 if (!MoveCallerInstsAfterFunctionCall(&preCallSB, &postCallSB, &new_blk_ptr,
634 call_inst_itr,
635 calleeFn->begin() != calleeFn->end()))
636 return false;
637
638 // Finalize inline code.
639 new_blocks->push_back(std::move(new_blk_ptr));
640
641 if (caller_is_loop_header && (new_blocks->size() > 1))
642 MoveLoopMergeInstToFirstBlock(new_blocks);
643
644 // Update block map given replacement blocks.
645 for (auto& blk : *new_blocks) {
646 id2block_[blk->id()] = &*blk;
647 }
648 return true;
649 }
650
651 bool InlinePass::IsInlinableFunctionCall(const Instruction* inst) {
652 if (inst->opcode() != SpvOp::SpvOpFunctionCall) return false;
653 const uint32_t calleeFnId =
654 inst->GetSingleWordOperand(kSpvFunctionCallFunctionId);
655 const auto ci = inlinable_.find(calleeFnId);
656 if (ci == inlinable_.cend()) return false;
657
658 if (early_return_funcs_.find(calleeFnId) != early_return_funcs_.end()) {
659 // We rely on the merge-return pass to handle the early return case
660 // in advance.
661 std::string message =
662 "The function '" + id2function_[calleeFnId]->DefInst().PrettyPrint() +
663 "' could not be inlined because the return instruction "
664 "is not at the end of the function. This could be fixed by "
665 "running merge-return before inlining.";
666 consumer()(SPV_MSG_WARNING, "", {0, 0, 0}, message.c_str());
667 return false;
668 }
669
670 return true;
671 }
672
673 void InlinePass::UpdateSucceedingPhis(
674 std::vector<std::unique_ptr<BasicBlock>>& new_blocks) {
675 const auto firstBlk = new_blocks.begin();
676 const auto lastBlk = new_blocks.end() - 1;
677 const uint32_t firstId = (*firstBlk)->id();
678 const uint32_t lastId = (*lastBlk)->id();
679 const BasicBlock& const_last_block = *lastBlk->get();
680 const_last_block.ForEachSuccessorLabel(
681 [&firstId, &lastId, this](const uint32_t succ) {
682 BasicBlock* sbp = this->id2block_[succ];
683 sbp->ForEachPhiInst([&firstId, &lastId](Instruction* phi) {
684 phi->ForEachInId([&firstId, &lastId](uint32_t* id) {
685 if (*id == firstId) *id = lastId;
686 });
687 });
688 });
689 }
690
691 bool InlinePass::HasNoReturnInLoop(Function* func) {
692 // If control not structured, do not do loop/return analysis
693 // TODO: Analyze returns in non-structured control flow
694 if (!context()->get_feature_mgr()->HasCapability(SpvCapabilityShader))
695 return false;
696 const auto structured_analysis = context()->GetStructuredCFGAnalysis();
697 // Search for returns in structured construct.
698 bool return_in_loop = false;
699 for (auto& blk : *func) {
700 auto terminal_ii = blk.cend();
701 --terminal_ii;
702 if (spvOpcodeIsReturn(terminal_ii->opcode()) &&
703 structured_analysis->ContainingLoop(blk.id()) != 0) {
704 return_in_loop = true;
705 break;
706 }
707 }
708 return !return_in_loop;
709 }
710
711 void InlinePass::AnalyzeReturns(Function* func) {
712 // Analyze functions without a return in loop.
713 if (HasNoReturnInLoop(func)) {
714 no_return_in_loop_.insert(func->result_id());
715 }
716 // Analyze functions with a return before its tail basic block.
717 for (auto& blk : *func) {
718 auto terminal_ii = blk.cend();
719 --terminal_ii;
720 if (spvOpcodeIsReturn(terminal_ii->opcode()) && &blk != func->tail()) {
721 early_return_funcs_.insert(func->result_id());
722 break;
723 }
724 }
725 }
726
727 bool InlinePass::IsInlinableFunction(Function* func) {
728 // We can only inline a function if it has blocks.
729 if (func->cbegin() == func->cend()) return false;
730
731 // Do not inline functions with DontInline flag.
732 if (func->control_mask() & SpvFunctionControlDontInlineMask) {
733 return false;
734 }
735
736 // Do not inline functions with returns in loops. Currently early return
737 // functions are inlined by wrapping them in a one trip loop and implementing
738 // the returns as a branch to the loop's merge block. However, this can only
739 // done validly if the return was not in a loop in the original function.
740 // Also remember functions with multiple (early) returns.
741 AnalyzeReturns(func);
742 if (no_return_in_loop_.find(func->result_id()) == no_return_in_loop_.cend()) {
743 return false;
744 }
745
746 if (func->IsRecursive()) {
747 return false;
748 }
749
750 // Do not inline functions with an OpKill if they are called from a continue
751 // construct. If it is inlined into a continue construct it will generate
752 // invalid code.
753 bool func_is_called_from_continue =
754 funcs_called_from_continue_.count(func->result_id()) != 0;
755
756 if (func_is_called_from_continue && ContainsKillOrTerminateInvocation(func)) {
757 return false;
758 }
759
760 return true;
761 }
762
763 bool InlinePass::ContainsKillOrTerminateInvocation(Function* func) const {
764 return !func->WhileEachInst([](Instruction* inst) {
765 const auto opcode = inst->opcode();
766 return (opcode != SpvOpKill) && (opcode != SpvOpTerminateInvocation);
767 });
768 }
769
770 void InlinePass::InitializeInline() {
771 false_id_ = 0;
772
773 // clear collections
774 id2function_.clear();
775 id2block_.clear();
776 inlinable_.clear();
777 no_return_in_loop_.clear();
778 early_return_funcs_.clear();
779 funcs_called_from_continue_ =
780 context()->GetStructuredCFGAnalysis()->FindFuncsCalledFromContinue();
781
782 for (auto& fn : *get_module()) {
783 // Initialize function and block maps.
784 id2function_[fn.result_id()] = &fn;
785 for (auto& blk : fn) {
786 id2block_[blk.id()] = &blk;
787 }
788 // Compute inlinability
789 if (IsInlinableFunction(&fn)) inlinable_.insert(fn.result_id());
790 }
791 }
792
793 InlinePass::InlinePass() {}
794
795 } // namespace opt
796 } // namespace spvtools