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