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