1 // Copyright (c) 2018 Google LLC. 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 #include "source/opt/register_pressure.h" 16 17 #include <algorithm> 18 #include <iterator> 19 20 #include "source/opt/cfg.h" 21 #include "source/opt/def_use_manager.h" 22 #include "source/opt/dominator_tree.h" 23 #include "source/opt/function.h" 24 #include "source/opt/ir_context.h" 25 #include "source/opt/iterator.h" 26 27 namespace spvtools { 28 namespace opt { 29 30 namespace { 31 // Predicate for the FilterIterator to only consider instructions that are not 32 // phi instructions defined in the basic block |bb|. 33 class ExcludePhiDefinedInBlock { 34 public: 35 ExcludePhiDefinedInBlock(IRContext* context, const BasicBlock* bb) 36 : context_(context), bb_(bb) {} 37 38 bool operator()(Instruction* insn) const { 39 return !(insn->opcode() == SpvOpPhi && 40 context_->get_instr_block(insn) == bb_); 41 } 42 43 private: 44 IRContext* context_; 45 const BasicBlock* bb_; 46 }; 47 48 // Returns true if |insn| generates a SSA register that is likely to require a 49 // physical register. 50 bool CreatesRegisterUsage(Instruction* insn) { 51 if (!insn->HasResultId()) return false; 52 if (insn->opcode() == SpvOpUndef) return false; 53 if (IsConstantInst(insn->opcode())) return false; 54 if (insn->opcode() == SpvOpLabel) return false; 55 return true; 56 } 57 58 // Compute the register liveness for each basic block of a function. This also 59 // fill-up some information about the pick register usage and a break down of 60 // register usage. This implements: "A non-iterative data-flow algorithm for 61 // computing liveness sets in strict ssa programs" from Boissinot et al. 62 class ComputeRegisterLiveness { 63 public: 64 ComputeRegisterLiveness(RegisterLiveness* reg_pressure, Function* f) 65 : reg_pressure_(reg_pressure), 66 context_(reg_pressure->GetContext()), 67 function_(f), 68 cfg_(*reg_pressure->GetContext()->cfg()), 69 def_use_manager_(*reg_pressure->GetContext()->get_def_use_mgr()), 70 dom_tree_( 71 reg_pressure->GetContext()->GetDominatorAnalysis(f)->GetDomTree()), 72 loop_desc_(*reg_pressure->GetContext()->GetLoopDescriptor(f)) {} 73 74 // Computes the register liveness for |function_| and then estimate the 75 // register usage. The liveness algorithm works in 2 steps: 76 // - First, compute the liveness for each basic blocks, but will ignore any 77 // back-edge; 78 // - Second, walk loop forest to propagate registers crossing back-edges 79 // (add iterative values into the liveness set). 80 void Compute() { 81 cfg_.ForEachBlockInPostOrder(&*function_->begin(), [this](BasicBlock* bb) { 82 ComputePartialLiveness(bb); 83 }); 84 DoLoopLivenessUnification(); 85 EvaluateRegisterRequirements(); 86 } 87 88 private: 89 // Registers all SSA register used by successors of |bb| in their phi 90 // instructions. 91 void ComputePhiUses(const BasicBlock& bb, 92 RegisterLiveness::RegionRegisterLiveness::LiveSet* live) { 93 uint32_t bb_id = bb.id(); 94 bb.ForEachSuccessorLabel([live, bb_id, this](uint32_t sid) { 95 BasicBlock* succ_bb = cfg_.block(sid); 96 succ_bb->ForEachPhiInst([live, bb_id, this](const Instruction* phi) { 97 for (uint32_t i = 0; i < phi->NumInOperands(); i += 2) { 98 if (phi->GetSingleWordInOperand(i + 1) == bb_id) { 99 Instruction* insn_op = 100 def_use_manager_.GetDef(phi->GetSingleWordInOperand(i)); 101 if (CreatesRegisterUsage(insn_op)) { 102 live->insert(insn_op); 103 break; 104 } 105 } 106 } 107 }); 108 }); 109 } 110 111 // Computes register liveness for each basic blocks but ignores all 112 // back-edges. 113 void ComputePartialLiveness(BasicBlock* bb) { 114 assert(reg_pressure_->Get(bb) == nullptr && 115 "Basic block already processed"); 116 117 RegisterLiveness::RegionRegisterLiveness* live_inout = 118 reg_pressure_->GetOrInsert(bb->id()); 119 ComputePhiUses(*bb, &live_inout->live_out_); 120 121 const BasicBlock* cbb = bb; 122 cbb->ForEachSuccessorLabel([&live_inout, bb, this](uint32_t sid) { 123 // Skip back edges. 124 if (dom_tree_.Dominates(sid, bb->id())) { 125 return; 126 } 127 128 BasicBlock* succ_bb = cfg_.block(sid); 129 RegisterLiveness::RegionRegisterLiveness* succ_live_inout = 130 reg_pressure_->Get(succ_bb); 131 assert(succ_live_inout && 132 "Successor liveness analysis was not performed"); 133 134 ExcludePhiDefinedInBlock predicate(context_, succ_bb); 135 auto filter = 136 MakeFilterIteratorRange(succ_live_inout->live_in_.begin(), 137 succ_live_inout->live_in_.end(), predicate); 138 live_inout->live_out_.insert(filter.begin(), filter.end()); 139 }); 140 141 live_inout->live_in_ = live_inout->live_out_; 142 for (Instruction& insn : make_range(bb->rbegin(), bb->rend())) { 143 if (insn.opcode() == SpvOpPhi) { 144 live_inout->live_in_.insert(&insn); 145 break; 146 } 147 live_inout->live_in_.erase(&insn); 148 insn.ForEachInId([live_inout, this](uint32_t* id) { 149 Instruction* insn_op = def_use_manager_.GetDef(*id); 150 if (CreatesRegisterUsage(insn_op)) { 151 live_inout->live_in_.insert(insn_op); 152 } 153 }); 154 } 155 } 156 157 // Propagates the register liveness information of each loop iterators. 158 void DoLoopLivenessUnification() { 159 for (const Loop* loop : *loop_desc_.GetDummyRootLoop()) { 160 DoLoopLivenessUnification(*loop); 161 } 162 } 163 164 // Propagates the register liveness information of loop iterators trough-out 165 // the loop body. 166 void DoLoopLivenessUnification(const Loop& loop) { 167 auto blocks_in_loop = MakeFilterIteratorRange( 168 loop.GetBlocks().begin(), loop.GetBlocks().end(), 169 [&loop, this](uint32_t bb_id) { 170 return bb_id != loop.GetHeaderBlock()->id() && 171 loop_desc_[bb_id] == &loop; 172 }); 173 174 RegisterLiveness::RegionRegisterLiveness* header_live_inout = 175 reg_pressure_->Get(loop.GetHeaderBlock()); 176 assert(header_live_inout && 177 "Liveness analysis was not performed for the current block"); 178 179 ExcludePhiDefinedInBlock predicate(context_, loop.GetHeaderBlock()); 180 auto live_loop = 181 MakeFilterIteratorRange(header_live_inout->live_in_.begin(), 182 header_live_inout->live_in_.end(), predicate); 183 184 for (uint32_t bb_id : blocks_in_loop) { 185 BasicBlock* bb = cfg_.block(bb_id); 186 187 RegisterLiveness::RegionRegisterLiveness* live_inout = 188 reg_pressure_->Get(bb); 189 live_inout->live_in_.insert(live_loop.begin(), live_loop.end()); 190 live_inout->live_out_.insert(live_loop.begin(), live_loop.end()); 191 } 192 193 for (const Loop* inner_loop : loop) { 194 RegisterLiveness::RegionRegisterLiveness* live_inout = 195 reg_pressure_->Get(inner_loop->GetHeaderBlock()); 196 live_inout->live_in_.insert(live_loop.begin(), live_loop.end()); 197 live_inout->live_out_.insert(live_loop.begin(), live_loop.end()); 198 199 DoLoopLivenessUnification(*inner_loop); 200 } 201 } 202 203 // Get the number of required registers for this each basic block. 204 void EvaluateRegisterRequirements() { 205 for (BasicBlock& bb : *function_) { 206 RegisterLiveness::RegionRegisterLiveness* live_inout = 207 reg_pressure_->Get(bb.id()); 208 assert(live_inout != nullptr && "Basic block not processed"); 209 210 size_t reg_count = live_inout->live_out_.size(); 211 for (Instruction* insn : live_inout->live_out_) { 212 live_inout->AddRegisterClass(insn); 213 } 214 live_inout->used_registers_ = reg_count; 215 216 std::unordered_set<uint32_t> die_in_block; 217 for (Instruction& insn : make_range(bb.rbegin(), bb.rend())) { 218 // If it is a phi instruction, the register pressure will not change 219 // anymore. 220 if (insn.opcode() == SpvOpPhi) { 221 break; 222 } 223 224 insn.ForEachInId( 225 [live_inout, &die_in_block, ®_count, this](uint32_t* id) { 226 Instruction* op_insn = def_use_manager_.GetDef(*id); 227 if (!CreatesRegisterUsage(op_insn) || 228 live_inout->live_out_.count(op_insn)) { 229 // already taken into account. 230 return; 231 } 232 if (!die_in_block.count(*id)) { 233 live_inout->AddRegisterClass(def_use_manager_.GetDef(*id)); 234 reg_count++; 235 die_in_block.insert(*id); 236 } 237 }); 238 live_inout->used_registers_ = 239 std::max(live_inout->used_registers_, reg_count); 240 if (CreatesRegisterUsage(&insn)) { 241 reg_count--; 242 } 243 } 244 } 245 } 246 247 RegisterLiveness* reg_pressure_; 248 IRContext* context_; 249 Function* function_; 250 CFG& cfg_; 251 analysis::DefUseManager& def_use_manager_; 252 DominatorTree& dom_tree_; 253 LoopDescriptor& loop_desc_; 254 }; 255 } // namespace 256 257 // Get the number of required registers for each basic block. 258 void RegisterLiveness::RegionRegisterLiveness::AddRegisterClass( 259 Instruction* insn) { 260 assert(CreatesRegisterUsage(insn) && "Instruction does not use a register"); 261 analysis::Type* type = 262 insn->context()->get_type_mgr()->GetType(insn->type_id()); 263 264 RegisterLiveness::RegisterClass reg_class{type, false}; 265 266 insn->context()->get_decoration_mgr()->WhileEachDecoration( 267 insn->result_id(), SpvDecorationUniform, 268 [®_class](const Instruction&) { 269 reg_class.is_uniform_ = true; 270 return false; 271 }); 272 273 AddRegisterClass(reg_class); 274 } 275 276 void RegisterLiveness::Analyze(Function* f) { 277 block_pressure_.clear(); 278 ComputeRegisterLiveness(this, f).Compute(); 279 } 280 281 void RegisterLiveness::ComputeLoopRegisterPressure( 282 const Loop& loop, RegionRegisterLiveness* loop_reg_pressure) const { 283 loop_reg_pressure->Clear(); 284 285 const RegionRegisterLiveness* header_live_inout = Get(loop.GetHeaderBlock()); 286 loop_reg_pressure->live_in_ = header_live_inout->live_in_; 287 288 std::unordered_set<uint32_t> exit_blocks; 289 loop.GetExitBlocks(&exit_blocks); 290 291 for (uint32_t bb_id : exit_blocks) { 292 const RegionRegisterLiveness* live_inout = Get(bb_id); 293 loop_reg_pressure->live_out_.insert(live_inout->live_in_.begin(), 294 live_inout->live_in_.end()); 295 } 296 297 std::unordered_set<uint32_t> seen_insn; 298 for (Instruction* insn : loop_reg_pressure->live_out_) { 299 loop_reg_pressure->AddRegisterClass(insn); 300 seen_insn.insert(insn->result_id()); 301 } 302 for (Instruction* insn : loop_reg_pressure->live_in_) { 303 if (!seen_insn.count(insn->result_id())) { 304 continue; 305 } 306 loop_reg_pressure->AddRegisterClass(insn); 307 seen_insn.insert(insn->result_id()); 308 } 309 310 loop_reg_pressure->used_registers_ = 0; 311 312 for (uint32_t bb_id : loop.GetBlocks()) { 313 BasicBlock* bb = context_->cfg()->block(bb_id); 314 315 const RegionRegisterLiveness* live_inout = Get(bb_id); 316 assert(live_inout != nullptr && "Basic block not processed"); 317 loop_reg_pressure->used_registers_ = std::max( 318 loop_reg_pressure->used_registers_, live_inout->used_registers_); 319 320 for (Instruction& insn : *bb) { 321 if (insn.opcode() == SpvOpPhi || !CreatesRegisterUsage(&insn) || 322 seen_insn.count(insn.result_id())) { 323 continue; 324 } 325 loop_reg_pressure->AddRegisterClass(&insn); 326 } 327 } 328 } 329 330 void RegisterLiveness::SimulateFusion( 331 const Loop& l1, const Loop& l2, RegionRegisterLiveness* sim_result) const { 332 sim_result->Clear(); 333 334 // Compute the live-in state: 335 // sim_result.live_in = l1.live_in U l2.live_in 336 // This assumes that |l1| does not generated register that is live-out for 337 // |l1|. 338 const RegionRegisterLiveness* l1_header_live_inout = Get(l1.GetHeaderBlock()); 339 sim_result->live_in_ = l1_header_live_inout->live_in_; 340 341 const RegionRegisterLiveness* l2_header_live_inout = Get(l2.GetHeaderBlock()); 342 sim_result->live_in_.insert(l2_header_live_inout->live_in_.begin(), 343 l2_header_live_inout->live_in_.end()); 344 345 // The live-out set of the fused loop is the l2 live-out set. 346 std::unordered_set<uint32_t> exit_blocks; 347 l2.GetExitBlocks(&exit_blocks); 348 349 for (uint32_t bb_id : exit_blocks) { 350 const RegionRegisterLiveness* live_inout = Get(bb_id); 351 sim_result->live_out_.insert(live_inout->live_in_.begin(), 352 live_inout->live_in_.end()); 353 } 354 355 // Compute the register usage information. 356 std::unordered_set<uint32_t> seen_insn; 357 for (Instruction* insn : sim_result->live_out_) { 358 sim_result->AddRegisterClass(insn); 359 seen_insn.insert(insn->result_id()); 360 } 361 for (Instruction* insn : sim_result->live_in_) { 362 if (!seen_insn.count(insn->result_id())) { 363 continue; 364 } 365 sim_result->AddRegisterClass(insn); 366 seen_insn.insert(insn->result_id()); 367 } 368 369 sim_result->used_registers_ = 0; 370 371 // The loop fusion is injecting the l1 before the l2, the latch of l1 will be 372 // connected to the header of l2. 373 // To compute the register usage, we inject the loop live-in (union of l1 and 374 // l2 live-in header blocks) into the the live in/out of each basic block of 375 // l1 to get the peak register usage. We then repeat the operation to for l2 376 // basic blocks but in this case we inject the live-out of the latch of l1. 377 auto live_loop = MakeFilterIteratorRange( 378 sim_result->live_in_.begin(), sim_result->live_in_.end(), 379 [&l1, &l2](Instruction* insn) { 380 BasicBlock* bb = insn->context()->get_instr_block(insn); 381 return insn->HasResultId() && 382 !(insn->opcode() == SpvOpPhi && 383 (bb == l1.GetHeaderBlock() || bb == l2.GetHeaderBlock())); 384 }); 385 386 for (uint32_t bb_id : l1.GetBlocks()) { 387 BasicBlock* bb = context_->cfg()->block(bb_id); 388 389 const RegionRegisterLiveness* live_inout_info = Get(bb_id); 390 assert(live_inout_info != nullptr && "Basic block not processed"); 391 RegionRegisterLiveness::LiveSet live_out = live_inout_info->live_out_; 392 live_out.insert(live_loop.begin(), live_loop.end()); 393 sim_result->used_registers_ = 394 std::max(sim_result->used_registers_, 395 live_inout_info->used_registers_ + live_out.size() - 396 live_inout_info->live_out_.size()); 397 398 for (Instruction& insn : *bb) { 399 if (insn.opcode() == SpvOpPhi || !CreatesRegisterUsage(&insn) || 400 seen_insn.count(insn.result_id())) { 401 continue; 402 } 403 sim_result->AddRegisterClass(&insn); 404 } 405 } 406 407 const RegionRegisterLiveness* l1_latch_live_inout_info = 408 Get(l1.GetLatchBlock()->id()); 409 assert(l1_latch_live_inout_info != nullptr && "Basic block not processed"); 410 RegionRegisterLiveness::LiveSet l1_latch_live_out = 411 l1_latch_live_inout_info->live_out_; 412 l1_latch_live_out.insert(live_loop.begin(), live_loop.end()); 413 414 auto live_loop_l2 = 415 make_range(l1_latch_live_out.begin(), l1_latch_live_out.end()); 416 417 for (uint32_t bb_id : l2.GetBlocks()) { 418 BasicBlock* bb = context_->cfg()->block(bb_id); 419 420 const RegionRegisterLiveness* live_inout_info = Get(bb_id); 421 assert(live_inout_info != nullptr && "Basic block not processed"); 422 RegionRegisterLiveness::LiveSet live_out = live_inout_info->live_out_; 423 live_out.insert(live_loop_l2.begin(), live_loop_l2.end()); 424 sim_result->used_registers_ = 425 std::max(sim_result->used_registers_, 426 live_inout_info->used_registers_ + live_out.size() - 427 live_inout_info->live_out_.size()); 428 429 for (Instruction& insn : *bb) { 430 if (insn.opcode() == SpvOpPhi || !CreatesRegisterUsage(&insn) || 431 seen_insn.count(insn.result_id())) { 432 continue; 433 } 434 sim_result->AddRegisterClass(&insn); 435 } 436 } 437 } 438 439 void RegisterLiveness::SimulateFission( 440 const Loop& loop, const std::unordered_set<Instruction*>& moved_inst, 441 const std::unordered_set<Instruction*>& copied_inst, 442 RegionRegisterLiveness* l1_sim_result, 443 RegionRegisterLiveness* l2_sim_result) const { 444 l1_sim_result->Clear(); 445 l2_sim_result->Clear(); 446 447 // Filter predicates: consider instructions that only belong to the first and 448 // second loop. 449 auto belong_to_loop1 = [&moved_inst, &copied_inst, &loop](Instruction* insn) { 450 return moved_inst.count(insn) || copied_inst.count(insn) || 451 !loop.IsInsideLoop(insn); 452 }; 453 auto belong_to_loop2 = [&moved_inst](Instruction* insn) { 454 return !moved_inst.count(insn); 455 }; 456 457 const RegionRegisterLiveness* header_live_inout = Get(loop.GetHeaderBlock()); 458 // l1 live-in 459 { 460 auto live_loop = MakeFilterIteratorRange( 461 header_live_inout->live_in_.begin(), header_live_inout->live_in_.end(), 462 belong_to_loop1); 463 l1_sim_result->live_in_.insert(live_loop.begin(), live_loop.end()); 464 } 465 // l2 live-in 466 { 467 auto live_loop = MakeFilterIteratorRange( 468 header_live_inout->live_in_.begin(), header_live_inout->live_in_.end(), 469 belong_to_loop2); 470 l2_sim_result->live_in_.insert(live_loop.begin(), live_loop.end()); 471 } 472 473 std::unordered_set<uint32_t> exit_blocks; 474 loop.GetExitBlocks(&exit_blocks); 475 476 // l2 live-out. 477 for (uint32_t bb_id : exit_blocks) { 478 const RegionRegisterLiveness* live_inout = Get(bb_id); 479 l2_sim_result->live_out_.insert(live_inout->live_in_.begin(), 480 live_inout->live_in_.end()); 481 } 482 // l1 live-out. 483 { 484 auto live_out = MakeFilterIteratorRange(l2_sim_result->live_out_.begin(), 485 l2_sim_result->live_out_.end(), 486 belong_to_loop1); 487 l1_sim_result->live_out_.insert(live_out.begin(), live_out.end()); 488 } 489 { 490 auto live_out = 491 MakeFilterIteratorRange(l2_sim_result->live_in_.begin(), 492 l2_sim_result->live_in_.end(), belong_to_loop1); 493 l1_sim_result->live_out_.insert(live_out.begin(), live_out.end()); 494 } 495 // Lives out of l1 are live out of l2 so are live in of l2 as well. 496 l2_sim_result->live_in_.insert(l1_sim_result->live_out_.begin(), 497 l1_sim_result->live_out_.end()); 498 499 for (Instruction* insn : l1_sim_result->live_in_) { 500 l1_sim_result->AddRegisterClass(insn); 501 } 502 for (Instruction* insn : l2_sim_result->live_in_) { 503 l2_sim_result->AddRegisterClass(insn); 504 } 505 506 l1_sim_result->used_registers_ = 0; 507 l2_sim_result->used_registers_ = 0; 508 509 for (uint32_t bb_id : loop.GetBlocks()) { 510 BasicBlock* bb = context_->cfg()->block(bb_id); 511 512 const RegisterLiveness::RegionRegisterLiveness* live_inout = Get(bb_id); 513 assert(live_inout != nullptr && "Basic block not processed"); 514 auto l1_block_live_out = 515 MakeFilterIteratorRange(live_inout->live_out_.begin(), 516 live_inout->live_out_.end(), belong_to_loop1); 517 auto l2_block_live_out = 518 MakeFilterIteratorRange(live_inout->live_out_.begin(), 519 live_inout->live_out_.end(), belong_to_loop2); 520 521 size_t l1_reg_count = 522 std::distance(l1_block_live_out.begin(), l1_block_live_out.end()); 523 size_t l2_reg_count = 524 std::distance(l2_block_live_out.begin(), l2_block_live_out.end()); 525 526 std::unordered_set<uint32_t> die_in_block; 527 for (Instruction& insn : make_range(bb->rbegin(), bb->rend())) { 528 if (insn.opcode() == SpvOpPhi) { 529 break; 530 } 531 532 bool does_belong_to_loop1 = belong_to_loop1(&insn); 533 bool does_belong_to_loop2 = belong_to_loop2(&insn); 534 insn.ForEachInId([live_inout, &die_in_block, &l1_reg_count, &l2_reg_count, 535 does_belong_to_loop1, does_belong_to_loop2, 536 this](uint32_t* id) { 537 Instruction* op_insn = context_->get_def_use_mgr()->GetDef(*id); 538 if (!CreatesRegisterUsage(op_insn) || 539 live_inout->live_out_.count(op_insn)) { 540 // already taken into account. 541 return; 542 } 543 if (!die_in_block.count(*id)) { 544 if (does_belong_to_loop1) { 545 l1_reg_count++; 546 } 547 if (does_belong_to_loop2) { 548 l2_reg_count++; 549 } 550 die_in_block.insert(*id); 551 } 552 }); 553 l1_sim_result->used_registers_ = 554 std::max(l1_sim_result->used_registers_, l1_reg_count); 555 l2_sim_result->used_registers_ = 556 std::max(l2_sim_result->used_registers_, l2_reg_count); 557 if (CreatesRegisterUsage(&insn)) { 558 if (does_belong_to_loop1) { 559 if (!l1_sim_result->live_in_.count(&insn)) { 560 l1_sim_result->AddRegisterClass(&insn); 561 } 562 l1_reg_count--; 563 } 564 if (does_belong_to_loop2) { 565 if (!l2_sim_result->live_in_.count(&insn)) { 566 l2_sim_result->AddRegisterClass(&insn); 567 } 568 l2_reg_count--; 569 } 570 } 571 } 572 } 573 } 574 575 } // namespace opt 576 } // namespace spvtools 577