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