1 //===- AMDGPUMachineCFGStructurizer.cpp - Machine code if conversion pass. ===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file implements the machine instruction level CFG structurizer pass. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #include "AMDGPU.h" 14 #include "AMDGPUSubtarget.h" 15 #include "SIInstrInfo.h" 16 #include "llvm/ADT/ArrayRef.h" 17 #include "llvm/ADT/DenseMap.h" 18 #include "llvm/ADT/DenseSet.h" 19 #include "llvm/ADT/PostOrderIterator.h" 20 #include "llvm/ADT/SetVector.h" 21 #include "llvm/ADT/SmallPtrSet.h" 22 #include "llvm/ADT/SmallVector.h" 23 #include "llvm/CodeGen/MachineBasicBlock.h" 24 #include "llvm/CodeGen/MachineFunction.h" 25 #include "llvm/CodeGen/MachineFunctionPass.h" 26 #include "llvm/CodeGen/MachineInstr.h" 27 #include "llvm/CodeGen/MachineInstrBuilder.h" 28 #include "llvm/CodeGen/MachineOperand.h" 29 #include "llvm/CodeGen/MachineRegionInfo.h" 30 #include "llvm/CodeGen/MachineRegisterInfo.h" 31 #include "llvm/CodeGen/TargetOpcodes.h" 32 #include "llvm/CodeGen/TargetRegisterInfo.h" 33 #include "llvm/Config/llvm-config.h" 34 #include "llvm/IR/DebugLoc.h" 35 #include "llvm/Pass.h" 36 #include "llvm/Support/Compiler.h" 37 #include "llvm/Support/Debug.h" 38 #include "llvm/Support/ErrorHandling.h" 39 #include "llvm/Support/raw_ostream.h" 40 #include <cassert> 41 #include <tuple> 42 #include <utility> 43 44 using namespace llvm; 45 46 #define DEBUG_TYPE "amdgpucfgstructurizer" 47 48 namespace { 49 50 class PHILinearizeDestIterator; 51 52 class PHILinearize { 53 friend class PHILinearizeDestIterator; 54 55 public: 56 using PHISourceT = std::pair<unsigned, MachineBasicBlock *>; 57 58 private: 59 using PHISourcesT = DenseSet<PHISourceT>; 60 using PHIInfoElementT = struct { 61 unsigned DestReg; 62 DebugLoc DL; 63 PHISourcesT Sources; 64 }; 65 using PHIInfoT = SmallPtrSet<PHIInfoElementT *, 2>; 66 PHIInfoT PHIInfo; 67 68 static unsigned phiInfoElementGetDest(PHIInfoElementT *Info); 69 static void phiInfoElementSetDef(PHIInfoElementT *Info, unsigned NewDef); 70 static PHISourcesT &phiInfoElementGetSources(PHIInfoElementT *Info); 71 static void phiInfoElementAddSource(PHIInfoElementT *Info, unsigned SourceReg, 72 MachineBasicBlock *SourceMBB); 73 static void phiInfoElementRemoveSource(PHIInfoElementT *Info, 74 unsigned SourceReg, 75 MachineBasicBlock *SourceMBB); 76 PHIInfoElementT *findPHIInfoElement(unsigned DestReg); 77 PHIInfoElementT *findPHIInfoElementFromSource(unsigned SourceReg, 78 MachineBasicBlock *SourceMBB); 79 80 public: 81 bool findSourcesFromMBB(MachineBasicBlock *SourceMBB, 82 SmallVector<unsigned, 4> &Sources); 83 void addDest(unsigned DestReg, const DebugLoc &DL); 84 void replaceDef(unsigned OldDestReg, unsigned NewDestReg); 85 void deleteDef(unsigned DestReg); 86 void addSource(unsigned DestReg, unsigned SourceReg, 87 MachineBasicBlock *SourceMBB); 88 void removeSource(unsigned DestReg, unsigned SourceReg, 89 MachineBasicBlock *SourceMBB = nullptr); 90 bool findDest(unsigned SourceReg, MachineBasicBlock *SourceMBB, 91 unsigned &DestReg); 92 bool isSource(unsigned Reg, MachineBasicBlock *SourceMBB = nullptr); 93 unsigned getNumSources(unsigned DestReg); 94 void dump(MachineRegisterInfo *MRI); 95 void clear(); 96 97 using source_iterator = PHISourcesT::iterator; 98 using dest_iterator = PHILinearizeDestIterator; 99 100 dest_iterator dests_begin(); 101 dest_iterator dests_end(); 102 103 source_iterator sources_begin(unsigned Reg); 104 source_iterator sources_end(unsigned Reg); 105 }; 106 107 class PHILinearizeDestIterator { 108 private: 109 PHILinearize::PHIInfoT::iterator Iter; 110 111 public: 112 PHILinearizeDestIterator(PHILinearize::PHIInfoT::iterator I) : Iter(I) {} 113 114 unsigned operator*() { return PHILinearize::phiInfoElementGetDest(*Iter); } 115 PHILinearizeDestIterator &operator++() { 116 ++Iter; 117 return *this; 118 } 119 bool operator==(const PHILinearizeDestIterator &I) const { 120 return I.Iter == Iter; 121 } 122 bool operator!=(const PHILinearizeDestIterator &I) const { 123 return I.Iter != Iter; 124 } 125 }; 126 127 } // end anonymous namespace 128 129 unsigned PHILinearize::phiInfoElementGetDest(PHIInfoElementT *Info) { 130 return Info->DestReg; 131 } 132 133 void PHILinearize::phiInfoElementSetDef(PHIInfoElementT *Info, 134 unsigned NewDef) { 135 Info->DestReg = NewDef; 136 } 137 138 PHILinearize::PHISourcesT & 139 PHILinearize::phiInfoElementGetSources(PHIInfoElementT *Info) { 140 return Info->Sources; 141 } 142 143 void PHILinearize::phiInfoElementAddSource(PHIInfoElementT *Info, 144 unsigned SourceReg, 145 MachineBasicBlock *SourceMBB) { 146 // Assertion ensures we don't use the same SourceMBB for the 147 // sources, because we cannot have different registers with 148 // identical predecessors, but we can have the same register for 149 // multiple predecessors. 150 #if !defined(NDEBUG) 151 for (auto SI : phiInfoElementGetSources(Info)) { 152 assert((SI.second != SourceMBB || SourceReg == SI.first)); 153 } 154 #endif 155 156 phiInfoElementGetSources(Info).insert(PHISourceT(SourceReg, SourceMBB)); 157 } 158 159 void PHILinearize::phiInfoElementRemoveSource(PHIInfoElementT *Info, 160 unsigned SourceReg, 161 MachineBasicBlock *SourceMBB) { 162 auto &Sources = phiInfoElementGetSources(Info); 163 SmallVector<PHISourceT, 4> ElimiatedSources; 164 for (auto SI : Sources) { 165 if (SI.first == SourceReg && 166 (SI.second == nullptr || SI.second == SourceMBB)) { 167 ElimiatedSources.push_back(PHISourceT(SI.first, SI.second)); 168 } 169 } 170 171 for (auto &Source : ElimiatedSources) { 172 Sources.erase(Source); 173 } 174 } 175 176 PHILinearize::PHIInfoElementT * 177 PHILinearize::findPHIInfoElement(unsigned DestReg) { 178 for (auto I : PHIInfo) { 179 if (phiInfoElementGetDest(I) == DestReg) { 180 return I; 181 } 182 } 183 return nullptr; 184 } 185 186 PHILinearize::PHIInfoElementT * 187 PHILinearize::findPHIInfoElementFromSource(unsigned SourceReg, 188 MachineBasicBlock *SourceMBB) { 189 for (auto I : PHIInfo) { 190 for (auto SI : phiInfoElementGetSources(I)) { 191 if (SI.first == SourceReg && 192 (SI.second == nullptr || SI.second == SourceMBB)) { 193 return I; 194 } 195 } 196 } 197 return nullptr; 198 } 199 200 bool PHILinearize::findSourcesFromMBB(MachineBasicBlock *SourceMBB, 201 SmallVector<unsigned, 4> &Sources) { 202 bool FoundSource = false; 203 for (auto I : PHIInfo) { 204 for (auto SI : phiInfoElementGetSources(I)) { 205 if (SI.second == SourceMBB) { 206 FoundSource = true; 207 Sources.push_back(SI.first); 208 } 209 } 210 } 211 return FoundSource; 212 } 213 214 void PHILinearize::addDest(unsigned DestReg, const DebugLoc &DL) { 215 assert(findPHIInfoElement(DestReg) == nullptr && "Dest already exsists"); 216 PHISourcesT EmptySet; 217 PHIInfoElementT *NewElement = new PHIInfoElementT(); 218 NewElement->DestReg = DestReg; 219 NewElement->DL = DL; 220 NewElement->Sources = EmptySet; 221 PHIInfo.insert(NewElement); 222 } 223 224 void PHILinearize::replaceDef(unsigned OldDestReg, unsigned NewDestReg) { 225 phiInfoElementSetDef(findPHIInfoElement(OldDestReg), NewDestReg); 226 } 227 228 void PHILinearize::deleteDef(unsigned DestReg) { 229 PHIInfoElementT *InfoElement = findPHIInfoElement(DestReg); 230 PHIInfo.erase(InfoElement); 231 delete InfoElement; 232 } 233 234 void PHILinearize::addSource(unsigned DestReg, unsigned SourceReg, 235 MachineBasicBlock *SourceMBB) { 236 phiInfoElementAddSource(findPHIInfoElement(DestReg), SourceReg, SourceMBB); 237 } 238 239 void PHILinearize::removeSource(unsigned DestReg, unsigned SourceReg, 240 MachineBasicBlock *SourceMBB) { 241 phiInfoElementRemoveSource(findPHIInfoElement(DestReg), SourceReg, SourceMBB); 242 } 243 244 bool PHILinearize::findDest(unsigned SourceReg, MachineBasicBlock *SourceMBB, 245 unsigned &DestReg) { 246 PHIInfoElementT *InfoElement = 247 findPHIInfoElementFromSource(SourceReg, SourceMBB); 248 if (InfoElement != nullptr) { 249 DestReg = phiInfoElementGetDest(InfoElement); 250 return true; 251 } 252 return false; 253 } 254 255 bool PHILinearize::isSource(unsigned Reg, MachineBasicBlock *SourceMBB) { 256 unsigned DestReg; 257 return findDest(Reg, SourceMBB, DestReg); 258 } 259 260 unsigned PHILinearize::getNumSources(unsigned DestReg) { 261 return phiInfoElementGetSources(findPHIInfoElement(DestReg)).size(); 262 } 263 264 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 265 LLVM_DUMP_METHOD void PHILinearize::dump(MachineRegisterInfo *MRI) { 266 const TargetRegisterInfo *TRI = MRI->getTargetRegisterInfo(); 267 dbgs() << "=PHIInfo Start=\n"; 268 for (auto PII : this->PHIInfo) { 269 PHIInfoElementT &Element = *PII; 270 dbgs() << "Dest: " << printReg(Element.DestReg, TRI) 271 << " Sources: {"; 272 for (auto &SI : Element.Sources) { 273 dbgs() << printReg(SI.first, TRI) << '(' << printMBBReference(*SI.second) 274 << "),"; 275 } 276 dbgs() << "}\n"; 277 } 278 dbgs() << "=PHIInfo End=\n"; 279 } 280 #endif 281 282 void PHILinearize::clear() { PHIInfo = PHIInfoT(); } 283 284 PHILinearize::dest_iterator PHILinearize::dests_begin() { 285 return PHILinearizeDestIterator(PHIInfo.begin()); 286 } 287 288 PHILinearize::dest_iterator PHILinearize::dests_end() { 289 return PHILinearizeDestIterator(PHIInfo.end()); 290 } 291 292 PHILinearize::source_iterator PHILinearize::sources_begin(unsigned Reg) { 293 auto InfoElement = findPHIInfoElement(Reg); 294 return phiInfoElementGetSources(InfoElement).begin(); 295 } 296 297 PHILinearize::source_iterator PHILinearize::sources_end(unsigned Reg) { 298 auto InfoElement = findPHIInfoElement(Reg); 299 return phiInfoElementGetSources(InfoElement).end(); 300 } 301 302 static unsigned getPHINumInputs(MachineInstr &PHI) { 303 assert(PHI.isPHI()); 304 return (PHI.getNumOperands() - 1) / 2; 305 } 306 307 static MachineBasicBlock *getPHIPred(MachineInstr &PHI, unsigned Index) { 308 assert(PHI.isPHI()); 309 return PHI.getOperand(Index * 2 + 2).getMBB(); 310 } 311 312 static void setPhiPred(MachineInstr &PHI, unsigned Index, 313 MachineBasicBlock *NewPred) { 314 PHI.getOperand(Index * 2 + 2).setMBB(NewPred); 315 } 316 317 static unsigned getPHISourceReg(MachineInstr &PHI, unsigned Index) { 318 assert(PHI.isPHI()); 319 return PHI.getOperand(Index * 2 + 1).getReg(); 320 } 321 322 static unsigned getPHIDestReg(MachineInstr &PHI) { 323 assert(PHI.isPHI()); 324 return PHI.getOperand(0).getReg(); 325 } 326 327 namespace { 328 329 class RegionMRT; 330 class MBBMRT; 331 332 class LinearizedRegion { 333 protected: 334 MachineBasicBlock *Entry; 335 // The exit block is part of the region, and is the last 336 // merge block before exiting the region. 337 MachineBasicBlock *Exit; 338 DenseSet<unsigned> LiveOuts; 339 SmallPtrSet<MachineBasicBlock *, 1> MBBs; 340 bool HasLoop; 341 LinearizedRegion *Parent; 342 RegionMRT *RMRT; 343 344 void storeLiveOutReg(MachineBasicBlock *MBB, unsigned Reg, 345 MachineInstr *DefInstr, const MachineRegisterInfo *MRI, 346 const TargetRegisterInfo *TRI, PHILinearize &PHIInfo); 347 348 void storeLiveOutRegRegion(RegionMRT *Region, unsigned Reg, 349 MachineInstr *DefInstr, 350 const MachineRegisterInfo *MRI, 351 const TargetRegisterInfo *TRI, 352 PHILinearize &PHIInfo); 353 354 void storeMBBLiveOuts(MachineBasicBlock *MBB, const MachineRegisterInfo *MRI, 355 const TargetRegisterInfo *TRI, PHILinearize &PHIInfo, 356 RegionMRT *TopRegion); 357 358 void storeLiveOuts(MachineBasicBlock *MBB, const MachineRegisterInfo *MRI, 359 const TargetRegisterInfo *TRI, PHILinearize &PHIInfo); 360 361 void storeLiveOuts(RegionMRT *Region, const MachineRegisterInfo *MRI, 362 const TargetRegisterInfo *TRI, PHILinearize &PHIInfo, 363 RegionMRT *TopRegion = nullptr); 364 365 public: 366 LinearizedRegion(); 367 LinearizedRegion(MachineBasicBlock *MBB, const MachineRegisterInfo *MRI, 368 const TargetRegisterInfo *TRI, PHILinearize &PHIInfo); 369 ~LinearizedRegion() = default; 370 371 void setRegionMRT(RegionMRT *Region) { RMRT = Region; } 372 373 RegionMRT *getRegionMRT() { return RMRT; } 374 375 void setParent(LinearizedRegion *P) { Parent = P; } 376 377 LinearizedRegion *getParent() { return Parent; } 378 379 void print(raw_ostream &OS, const TargetRegisterInfo *TRI = nullptr); 380 381 void setBBSelectRegIn(unsigned Reg); 382 383 unsigned getBBSelectRegIn(); 384 385 void setBBSelectRegOut(unsigned Reg, bool IsLiveOut); 386 387 unsigned getBBSelectRegOut(); 388 389 void setHasLoop(bool Value); 390 391 bool getHasLoop(); 392 393 void addLiveOut(unsigned VReg); 394 395 void removeLiveOut(unsigned Reg); 396 397 void replaceLiveOut(unsigned OldReg, unsigned NewReg); 398 399 void replaceRegister(unsigned Register, unsigned NewRegister, 400 MachineRegisterInfo *MRI, bool ReplaceInside, 401 bool ReplaceOutside, bool IncludeLoopPHIs); 402 403 void replaceRegisterInsideRegion(unsigned Register, unsigned NewRegister, 404 bool IncludeLoopPHIs, 405 MachineRegisterInfo *MRI); 406 407 void replaceRegisterOutsideRegion(unsigned Register, unsigned NewRegister, 408 bool IncludeLoopPHIs, 409 MachineRegisterInfo *MRI); 410 411 DenseSet<unsigned> *getLiveOuts(); 412 413 void setEntry(MachineBasicBlock *NewEntry); 414 415 MachineBasicBlock *getEntry(); 416 417 void setExit(MachineBasicBlock *NewExit); 418 419 MachineBasicBlock *getExit(); 420 421 void addMBB(MachineBasicBlock *MBB); 422 423 void addMBBs(LinearizedRegion *InnerRegion); 424 425 bool contains(MachineBasicBlock *MBB); 426 427 bool isLiveOut(unsigned Reg); 428 429 bool hasNoDef(unsigned Reg, MachineRegisterInfo *MRI); 430 431 void removeFalseRegisterKills(MachineRegisterInfo *MRI); 432 433 void initLiveOut(RegionMRT *Region, const MachineRegisterInfo *MRI, 434 const TargetRegisterInfo *TRI, PHILinearize &PHIInfo); 435 }; 436 437 class MRT { 438 protected: 439 RegionMRT *Parent; 440 unsigned BBSelectRegIn; 441 unsigned BBSelectRegOut; 442 443 public: 444 virtual ~MRT() = default; 445 446 unsigned getBBSelectRegIn() { return BBSelectRegIn; } 447 448 unsigned getBBSelectRegOut() { return BBSelectRegOut; } 449 450 void setBBSelectRegIn(unsigned Reg) { BBSelectRegIn = Reg; } 451 452 void setBBSelectRegOut(unsigned Reg) { BBSelectRegOut = Reg; } 453 454 virtual RegionMRT *getRegionMRT() { return nullptr; } 455 456 virtual MBBMRT *getMBBMRT() { return nullptr; } 457 458 bool isRegion() { return getRegionMRT() != nullptr; } 459 460 bool isMBB() { return getMBBMRT() != nullptr; } 461 462 bool isRoot() { return Parent == nullptr; } 463 464 void setParent(RegionMRT *Region) { Parent = Region; } 465 466 RegionMRT *getParent() { return Parent; } 467 468 static MachineBasicBlock * 469 initializeMRT(MachineFunction &MF, const MachineRegionInfo *RegionInfo, 470 DenseMap<MachineRegion *, RegionMRT *> &RegionMap); 471 472 static RegionMRT *buildMRT(MachineFunction &MF, 473 const MachineRegionInfo *RegionInfo, 474 const SIInstrInfo *TII, 475 MachineRegisterInfo *MRI); 476 477 virtual void dump(const TargetRegisterInfo *TRI, int depth = 0) = 0; 478 479 void dumpDepth(int depth) { 480 for (int i = depth; i > 0; --i) { 481 dbgs() << " "; 482 } 483 } 484 }; 485 486 class MBBMRT : public MRT { 487 MachineBasicBlock *MBB; 488 489 public: 490 MBBMRT(MachineBasicBlock *BB) : MBB(BB) { 491 setParent(nullptr); 492 setBBSelectRegOut(0); 493 setBBSelectRegIn(0); 494 } 495 496 MBBMRT *getMBBMRT() override { return this; } 497 498 MachineBasicBlock *getMBB() { return MBB; } 499 500 void dump(const TargetRegisterInfo *TRI, int depth = 0) override { 501 dumpDepth(depth); 502 dbgs() << "MBB: " << getMBB()->getNumber(); 503 dbgs() << " In: " << printReg(getBBSelectRegIn(), TRI); 504 dbgs() << ", Out: " << printReg(getBBSelectRegOut(), TRI) << "\n"; 505 } 506 }; 507 508 class RegionMRT : public MRT { 509 protected: 510 MachineRegion *Region; 511 LinearizedRegion *LRegion = nullptr; 512 MachineBasicBlock *Succ = nullptr; 513 SetVector<MRT *> Children; 514 515 public: 516 RegionMRT(MachineRegion *MachineRegion) : Region(MachineRegion) { 517 setParent(nullptr); 518 setBBSelectRegOut(0); 519 setBBSelectRegIn(0); 520 } 521 522 ~RegionMRT() override { 523 if (LRegion) { 524 delete LRegion; 525 } 526 527 for (auto CI : Children) { 528 delete &(*CI); 529 } 530 } 531 532 RegionMRT *getRegionMRT() override { return this; } 533 534 void setLinearizedRegion(LinearizedRegion *LinearizeRegion) { 535 LRegion = LinearizeRegion; 536 } 537 538 LinearizedRegion *getLinearizedRegion() { return LRegion; } 539 540 MachineRegion *getMachineRegion() { return Region; } 541 542 unsigned getInnerOutputRegister() { 543 return (*(Children.begin()))->getBBSelectRegOut(); 544 } 545 546 void addChild(MRT *Tree) { Children.insert(Tree); } 547 548 SetVector<MRT *> *getChildren() { return &Children; } 549 550 void dump(const TargetRegisterInfo *TRI, int depth = 0) override { 551 dumpDepth(depth); 552 dbgs() << "Region: " << (void *)Region; 553 dbgs() << " In: " << printReg(getBBSelectRegIn(), TRI); 554 dbgs() << ", Out: " << printReg(getBBSelectRegOut(), TRI) << "\n"; 555 556 dumpDepth(depth); 557 if (getSucc()) 558 dbgs() << "Succ: " << getSucc()->getNumber() << "\n"; 559 else 560 dbgs() << "Succ: none \n"; 561 for (auto MRTI : Children) { 562 MRTI->dump(TRI, depth + 1); 563 } 564 } 565 566 MRT *getEntryTree() { return Children.back(); } 567 568 MRT *getExitTree() { return Children.front(); } 569 570 MachineBasicBlock *getEntry() { 571 MRT *Tree = Children.back(); 572 return (Tree->isRegion()) ? Tree->getRegionMRT()->getEntry() 573 : Tree->getMBBMRT()->getMBB(); 574 } 575 576 MachineBasicBlock *getExit() { 577 MRT *Tree = Children.front(); 578 return (Tree->isRegion()) ? Tree->getRegionMRT()->getExit() 579 : Tree->getMBBMRT()->getMBB(); 580 } 581 582 void setSucc(MachineBasicBlock *MBB) { Succ = MBB; } 583 584 MachineBasicBlock *getSucc() { return Succ; } 585 586 bool contains(MachineBasicBlock *MBB) { 587 for (auto CI : Children) { 588 if (CI->isMBB()) { 589 if (MBB == CI->getMBBMRT()->getMBB()) { 590 return true; 591 } 592 } else { 593 if (CI->getRegionMRT()->contains(MBB)) { 594 return true; 595 } else if (CI->getRegionMRT()->getLinearizedRegion() != nullptr && 596 CI->getRegionMRT()->getLinearizedRegion()->contains(MBB)) { 597 return true; 598 } 599 } 600 } 601 return false; 602 } 603 604 void replaceLiveOutReg(unsigned Register, unsigned NewRegister) { 605 LinearizedRegion *LRegion = getLinearizedRegion(); 606 LRegion->replaceLiveOut(Register, NewRegister); 607 for (auto &CI : Children) { 608 if (CI->isRegion()) { 609 CI->getRegionMRT()->replaceLiveOutReg(Register, NewRegister); 610 } 611 } 612 } 613 }; 614 615 } // end anonymous namespace 616 617 static unsigned createBBSelectReg(const SIInstrInfo *TII, 618 MachineRegisterInfo *MRI) { 619 return MRI->createVirtualRegister(TII->getPreferredSelectRegClass(32)); 620 } 621 622 MachineBasicBlock * 623 MRT::initializeMRT(MachineFunction &MF, const MachineRegionInfo *RegionInfo, 624 DenseMap<MachineRegion *, RegionMRT *> &RegionMap) { 625 for (auto &MFI : MF) { 626 MachineBasicBlock *ExitMBB = &MFI; 627 if (ExitMBB->succ_size() == 0) { 628 return ExitMBB; 629 } 630 } 631 llvm_unreachable("CFG has no exit block"); 632 return nullptr; 633 } 634 635 RegionMRT *MRT::buildMRT(MachineFunction &MF, 636 const MachineRegionInfo *RegionInfo, 637 const SIInstrInfo *TII, MachineRegisterInfo *MRI) { 638 SmallPtrSet<MachineRegion *, 4> PlacedRegions; 639 DenseMap<MachineRegion *, RegionMRT *> RegionMap; 640 MachineRegion *TopLevelRegion = RegionInfo->getTopLevelRegion(); 641 RegionMRT *Result = new RegionMRT(TopLevelRegion); 642 RegionMap[TopLevelRegion] = Result; 643 644 // Insert the exit block first, we need it to be the merge node 645 // for the top level region. 646 MachineBasicBlock *Exit = initializeMRT(MF, RegionInfo, RegionMap); 647 648 unsigned BBSelectRegIn = createBBSelectReg(TII, MRI); 649 MBBMRT *ExitMRT = new MBBMRT(Exit); 650 RegionMap[RegionInfo->getRegionFor(Exit)]->addChild(ExitMRT); 651 ExitMRT->setBBSelectRegIn(BBSelectRegIn); 652 653 for (auto MBBI : post_order(&(MF.front()))) { 654 MachineBasicBlock *MBB = &(*MBBI); 655 656 // Skip Exit since we already added it 657 if (MBB == Exit) { 658 continue; 659 } 660 661 LLVM_DEBUG(dbgs() << "Visiting " << printMBBReference(*MBB) << "\n"); 662 MBBMRT *NewMBB = new MBBMRT(MBB); 663 MachineRegion *Region = RegionInfo->getRegionFor(MBB); 664 665 // Ensure we have the MRT region 666 if (RegionMap.count(Region) == 0) { 667 RegionMRT *NewMRTRegion = new RegionMRT(Region); 668 RegionMap[Region] = NewMRTRegion; 669 670 // Ensure all parents are in the RegionMap 671 MachineRegion *Parent = Region->getParent(); 672 while (RegionMap.count(Parent) == 0) { 673 RegionMRT *NewMRTParent = new RegionMRT(Parent); 674 NewMRTParent->addChild(NewMRTRegion); 675 NewMRTRegion->setParent(NewMRTParent); 676 RegionMap[Parent] = NewMRTParent; 677 NewMRTRegion = NewMRTParent; 678 Parent = Parent->getParent(); 679 } 680 RegionMap[Parent]->addChild(NewMRTRegion); 681 NewMRTRegion->setParent(RegionMap[Parent]); 682 } 683 684 // Add MBB to Region MRT 685 RegionMap[Region]->addChild(NewMBB); 686 NewMBB->setParent(RegionMap[Region]); 687 RegionMap[Region]->setSucc(Region->getExit()); 688 } 689 return Result; 690 } 691 692 void LinearizedRegion::storeLiveOutReg(MachineBasicBlock *MBB, unsigned Reg, 693 MachineInstr *DefInstr, 694 const MachineRegisterInfo *MRI, 695 const TargetRegisterInfo *TRI, 696 PHILinearize &PHIInfo) { 697 if (TRI->isVirtualRegister(Reg)) { 698 LLVM_DEBUG(dbgs() << "Considering Register: " << printReg(Reg, TRI) 699 << "\n"); 700 // If this is a source register to a PHI we are chaining, it 701 // must be live out. 702 if (PHIInfo.isSource(Reg)) { 703 LLVM_DEBUG(dbgs() << "Add LiveOut (PHI): " << printReg(Reg, TRI) << "\n"); 704 addLiveOut(Reg); 705 } else { 706 // If this is live out of the MBB 707 for (auto &UI : MRI->use_operands(Reg)) { 708 if (UI.getParent()->getParent() != MBB) { 709 LLVM_DEBUG(dbgs() << "Add LiveOut (MBB " << printMBBReference(*MBB) 710 << "): " << printReg(Reg, TRI) << "\n"); 711 addLiveOut(Reg); 712 } else { 713 // If the use is in the same MBB we have to make sure 714 // it is after the def, otherwise it is live out in a loop 715 MachineInstr *UseInstr = UI.getParent(); 716 for (MachineBasicBlock::instr_iterator 717 MII = UseInstr->getIterator(), 718 MIE = UseInstr->getParent()->instr_end(); 719 MII != MIE; ++MII) { 720 if ((&(*MII)) == DefInstr) { 721 LLVM_DEBUG(dbgs() << "Add LiveOut (Loop): " << printReg(Reg, TRI) 722 << "\n"); 723 addLiveOut(Reg); 724 } 725 } 726 } 727 } 728 } 729 } 730 } 731 732 void LinearizedRegion::storeLiveOutRegRegion(RegionMRT *Region, unsigned Reg, 733 MachineInstr *DefInstr, 734 const MachineRegisterInfo *MRI, 735 const TargetRegisterInfo *TRI, 736 PHILinearize &PHIInfo) { 737 if (TRI->isVirtualRegister(Reg)) { 738 LLVM_DEBUG(dbgs() << "Considering Register: " << printReg(Reg, TRI) 739 << "\n"); 740 for (auto &UI : MRI->use_operands(Reg)) { 741 if (!Region->contains(UI.getParent()->getParent())) { 742 LLVM_DEBUG(dbgs() << "Add LiveOut (Region " << (void *)Region 743 << "): " << printReg(Reg, TRI) << "\n"); 744 addLiveOut(Reg); 745 } 746 } 747 } 748 } 749 750 void LinearizedRegion::storeLiveOuts(MachineBasicBlock *MBB, 751 const MachineRegisterInfo *MRI, 752 const TargetRegisterInfo *TRI, 753 PHILinearize &PHIInfo) { 754 LLVM_DEBUG(dbgs() << "-Store Live Outs Begin (" << printMBBReference(*MBB) 755 << ")-\n"); 756 for (auto &II : *MBB) { 757 for (auto &RI : II.defs()) { 758 storeLiveOutReg(MBB, RI.getReg(), RI.getParent(), MRI, TRI, PHIInfo); 759 } 760 for (auto &IRI : II.implicit_operands()) { 761 if (IRI.isDef()) { 762 storeLiveOutReg(MBB, IRI.getReg(), IRI.getParent(), MRI, TRI, PHIInfo); 763 } 764 } 765 } 766 767 // If we have a successor with a PHI, source coming from this MBB we have to 768 // add the register as live out 769 for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(), 770 E = MBB->succ_end(); 771 SI != E; ++SI) { 772 for (auto &II : *(*SI)) { 773 if (II.isPHI()) { 774 MachineInstr &PHI = II; 775 int numPreds = getPHINumInputs(PHI); 776 for (int i = 0; i < numPreds; ++i) { 777 if (getPHIPred(PHI, i) == MBB) { 778 unsigned PHIReg = getPHISourceReg(PHI, i); 779 LLVM_DEBUG(dbgs() 780 << "Add LiveOut (PhiSource " << printMBBReference(*MBB) 781 << " -> " << printMBBReference(*(*SI)) 782 << "): " << printReg(PHIReg, TRI) << "\n"); 783 addLiveOut(PHIReg); 784 } 785 } 786 } 787 } 788 } 789 790 LLVM_DEBUG(dbgs() << "-Store Live Outs Endn-\n"); 791 } 792 793 void LinearizedRegion::storeMBBLiveOuts(MachineBasicBlock *MBB, 794 const MachineRegisterInfo *MRI, 795 const TargetRegisterInfo *TRI, 796 PHILinearize &PHIInfo, 797 RegionMRT *TopRegion) { 798 for (auto &II : *MBB) { 799 for (auto &RI : II.defs()) { 800 storeLiveOutRegRegion(TopRegion, RI.getReg(), RI.getParent(), MRI, TRI, 801 PHIInfo); 802 } 803 for (auto &IRI : II.implicit_operands()) { 804 if (IRI.isDef()) { 805 storeLiveOutRegRegion(TopRegion, IRI.getReg(), IRI.getParent(), MRI, 806 TRI, PHIInfo); 807 } 808 } 809 } 810 } 811 812 void LinearizedRegion::storeLiveOuts(RegionMRT *Region, 813 const MachineRegisterInfo *MRI, 814 const TargetRegisterInfo *TRI, 815 PHILinearize &PHIInfo, 816 RegionMRT *CurrentTopRegion) { 817 MachineBasicBlock *Exit = Region->getSucc(); 818 819 RegionMRT *TopRegion = 820 CurrentTopRegion == nullptr ? Region : CurrentTopRegion; 821 822 // Check if exit is end of function, if so, no live outs. 823 if (Exit == nullptr) 824 return; 825 826 auto Children = Region->getChildren(); 827 for (auto CI : *Children) { 828 if (CI->isMBB()) { 829 auto MBB = CI->getMBBMRT()->getMBB(); 830 storeMBBLiveOuts(MBB, MRI, TRI, PHIInfo, TopRegion); 831 } else { 832 LinearizedRegion *SubRegion = CI->getRegionMRT()->getLinearizedRegion(); 833 // We should be limited to only store registers that are live out from the 834 // lineaized region 835 for (auto MBBI : SubRegion->MBBs) { 836 storeMBBLiveOuts(MBBI, MRI, TRI, PHIInfo, TopRegion); 837 } 838 } 839 } 840 841 if (CurrentTopRegion == nullptr) { 842 auto Succ = Region->getSucc(); 843 for (auto &II : *Succ) { 844 if (II.isPHI()) { 845 MachineInstr &PHI = II; 846 int numPreds = getPHINumInputs(PHI); 847 for (int i = 0; i < numPreds; ++i) { 848 if (Region->contains(getPHIPred(PHI, i))) { 849 unsigned PHIReg = getPHISourceReg(PHI, i); 850 LLVM_DEBUG(dbgs() << "Add Region LiveOut (" << (void *)Region 851 << "): " << printReg(PHIReg, TRI) << "\n"); 852 addLiveOut(PHIReg); 853 } 854 } 855 } 856 } 857 } 858 } 859 860 #ifndef NDEBUG 861 void LinearizedRegion::print(raw_ostream &OS, const TargetRegisterInfo *TRI) { 862 OS << "Linearized Region {"; 863 bool IsFirst = true; 864 for (const auto &MBB : MBBs) { 865 if (IsFirst) { 866 IsFirst = false; 867 } else { 868 OS << " ,"; 869 } 870 OS << MBB->getNumber(); 871 } 872 OS << "} (" << Entry->getNumber() << ", " 873 << (Exit == nullptr ? -1 : Exit->getNumber()) 874 << "): In:" << printReg(getBBSelectRegIn(), TRI) 875 << " Out:" << printReg(getBBSelectRegOut(), TRI) << " {"; 876 for (auto &LI : LiveOuts) { 877 OS << printReg(LI, TRI) << " "; 878 } 879 OS << "} \n"; 880 } 881 #endif 882 883 unsigned LinearizedRegion::getBBSelectRegIn() { 884 return getRegionMRT()->getBBSelectRegIn(); 885 } 886 887 unsigned LinearizedRegion::getBBSelectRegOut() { 888 return getRegionMRT()->getBBSelectRegOut(); 889 } 890 891 void LinearizedRegion::setHasLoop(bool Value) { HasLoop = Value; } 892 893 bool LinearizedRegion::getHasLoop() { return HasLoop; } 894 895 void LinearizedRegion::addLiveOut(unsigned VReg) { LiveOuts.insert(VReg); } 896 897 void LinearizedRegion::removeLiveOut(unsigned Reg) { 898 if (isLiveOut(Reg)) 899 LiveOuts.erase(Reg); 900 } 901 902 void LinearizedRegion::replaceLiveOut(unsigned OldReg, unsigned NewReg) { 903 if (isLiveOut(OldReg)) { 904 removeLiveOut(OldReg); 905 addLiveOut(NewReg); 906 } 907 } 908 909 void LinearizedRegion::replaceRegister(unsigned Register, unsigned NewRegister, 910 MachineRegisterInfo *MRI, 911 bool ReplaceInside, bool ReplaceOutside, 912 bool IncludeLoopPHI) { 913 assert(Register != NewRegister && "Cannot replace a reg with itself"); 914 915 LLVM_DEBUG( 916 dbgs() << "Pepareing to replace register (region): " 917 << printReg(Register, MRI->getTargetRegisterInfo()) << " with " 918 << printReg(NewRegister, MRI->getTargetRegisterInfo()) << "\n"); 919 920 // If we are replacing outside, we also need to update the LiveOuts 921 if (ReplaceOutside && 922 (isLiveOut(Register) || this->getParent()->isLiveOut(Register))) { 923 LinearizedRegion *Current = this; 924 while (Current != nullptr && Current->getEntry() != nullptr) { 925 LLVM_DEBUG(dbgs() << "Region before register replace\n"); 926 LLVM_DEBUG(Current->print(dbgs(), MRI->getTargetRegisterInfo())); 927 Current->replaceLiveOut(Register, NewRegister); 928 LLVM_DEBUG(dbgs() << "Region after register replace\n"); 929 LLVM_DEBUG(Current->print(dbgs(), MRI->getTargetRegisterInfo())); 930 Current = Current->getParent(); 931 } 932 } 933 934 for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(Register), 935 E = MRI->reg_end(); 936 I != E;) { 937 MachineOperand &O = *I; 938 ++I; 939 940 // We don't rewrite defs. 941 if (O.isDef()) 942 continue; 943 944 bool IsInside = contains(O.getParent()->getParent()); 945 bool IsLoopPHI = IsInside && (O.getParent()->isPHI() && 946 O.getParent()->getParent() == getEntry()); 947 bool ShouldReplace = (IsInside && ReplaceInside) || 948 (!IsInside && ReplaceOutside) || 949 (IncludeLoopPHI && IsLoopPHI); 950 if (ShouldReplace) { 951 952 if (TargetRegisterInfo::isPhysicalRegister(NewRegister)) { 953 LLVM_DEBUG(dbgs() << "Trying to substitute physical register: " 954 << printReg(NewRegister, MRI->getTargetRegisterInfo()) 955 << "\n"); 956 llvm_unreachable("Cannot substitute physical registers"); 957 } else { 958 LLVM_DEBUG(dbgs() << "Replacing register (region): " 959 << printReg(Register, MRI->getTargetRegisterInfo()) 960 << " with " 961 << printReg(NewRegister, MRI->getTargetRegisterInfo()) 962 << "\n"); 963 O.setReg(NewRegister); 964 } 965 } 966 } 967 } 968 969 void LinearizedRegion::replaceRegisterInsideRegion(unsigned Register, 970 unsigned NewRegister, 971 bool IncludeLoopPHIs, 972 MachineRegisterInfo *MRI) { 973 replaceRegister(Register, NewRegister, MRI, true, false, IncludeLoopPHIs); 974 } 975 976 void LinearizedRegion::replaceRegisterOutsideRegion(unsigned Register, 977 unsigned NewRegister, 978 bool IncludeLoopPHIs, 979 MachineRegisterInfo *MRI) { 980 replaceRegister(Register, NewRegister, MRI, false, true, IncludeLoopPHIs); 981 } 982 983 DenseSet<unsigned> *LinearizedRegion::getLiveOuts() { return &LiveOuts; } 984 985 void LinearizedRegion::setEntry(MachineBasicBlock *NewEntry) { 986 Entry = NewEntry; 987 } 988 989 MachineBasicBlock *LinearizedRegion::getEntry() { return Entry; } 990 991 void LinearizedRegion::setExit(MachineBasicBlock *NewExit) { Exit = NewExit; } 992 993 MachineBasicBlock *LinearizedRegion::getExit() { return Exit; } 994 995 void LinearizedRegion::addMBB(MachineBasicBlock *MBB) { MBBs.insert(MBB); } 996 997 void LinearizedRegion::addMBBs(LinearizedRegion *InnerRegion) { 998 for (const auto &MBB : InnerRegion->MBBs) { 999 addMBB(MBB); 1000 } 1001 } 1002 1003 bool LinearizedRegion::contains(MachineBasicBlock *MBB) { 1004 return MBBs.count(MBB) == 1; 1005 } 1006 1007 bool LinearizedRegion::isLiveOut(unsigned Reg) { 1008 return LiveOuts.count(Reg) == 1; 1009 } 1010 1011 bool LinearizedRegion::hasNoDef(unsigned Reg, MachineRegisterInfo *MRI) { 1012 return MRI->def_begin(Reg) == MRI->def_end(); 1013 } 1014 1015 // After the code has been structurized, what was flagged as kills 1016 // before are no longer register kills. 1017 void LinearizedRegion::removeFalseRegisterKills(MachineRegisterInfo *MRI) { 1018 const TargetRegisterInfo *TRI = MRI->getTargetRegisterInfo(); 1019 for (auto MBBI : MBBs) { 1020 MachineBasicBlock *MBB = MBBI; 1021 for (auto &II : *MBB) { 1022 for (auto &RI : II.uses()) { 1023 if (RI.isReg()) { 1024 unsigned Reg = RI.getReg(); 1025 if (TRI->isVirtualRegister(Reg)) { 1026 if (hasNoDef(Reg, MRI)) 1027 continue; 1028 if (!MRI->hasOneDef(Reg)) { 1029 LLVM_DEBUG(this->getEntry()->getParent()->dump()); 1030 LLVM_DEBUG(dbgs() << printReg(Reg, TRI) << "\n"); 1031 } 1032 1033 if (MRI->def_begin(Reg) == MRI->def_end()) { 1034 LLVM_DEBUG(dbgs() << "Register " 1035 << printReg(Reg, MRI->getTargetRegisterInfo()) 1036 << " has NO defs\n"); 1037 } else if (!MRI->hasOneDef(Reg)) { 1038 LLVM_DEBUG(dbgs() << "Register " 1039 << printReg(Reg, MRI->getTargetRegisterInfo()) 1040 << " has multiple defs\n"); 1041 } 1042 1043 assert(MRI->hasOneDef(Reg) && "Register has multiple definitions"); 1044 MachineOperand *Def = &(*(MRI->def_begin(Reg))); 1045 MachineOperand *UseOperand = &(RI); 1046 bool UseIsOutsideDefMBB = Def->getParent()->getParent() != MBB; 1047 if (UseIsOutsideDefMBB && UseOperand->isKill()) { 1048 LLVM_DEBUG(dbgs() << "Removing kill flag on register: " 1049 << printReg(Reg, TRI) << "\n"); 1050 UseOperand->setIsKill(false); 1051 } 1052 } 1053 } 1054 } 1055 } 1056 } 1057 } 1058 1059 void LinearizedRegion::initLiveOut(RegionMRT *Region, 1060 const MachineRegisterInfo *MRI, 1061 const TargetRegisterInfo *TRI, 1062 PHILinearize &PHIInfo) { 1063 storeLiveOuts(Region, MRI, TRI, PHIInfo); 1064 } 1065 1066 LinearizedRegion::LinearizedRegion(MachineBasicBlock *MBB, 1067 const MachineRegisterInfo *MRI, 1068 const TargetRegisterInfo *TRI, 1069 PHILinearize &PHIInfo) { 1070 setEntry(MBB); 1071 setExit(MBB); 1072 storeLiveOuts(MBB, MRI, TRI, PHIInfo); 1073 MBBs.insert(MBB); 1074 Parent = nullptr; 1075 } 1076 1077 LinearizedRegion::LinearizedRegion() { 1078 setEntry(nullptr); 1079 setExit(nullptr); 1080 Parent = nullptr; 1081 } 1082 1083 namespace { 1084 1085 class AMDGPUMachineCFGStructurizer : public MachineFunctionPass { 1086 private: 1087 const MachineRegionInfo *Regions; 1088 const SIInstrInfo *TII; 1089 const TargetRegisterInfo *TRI; 1090 MachineRegisterInfo *MRI; 1091 unsigned BBSelectRegister; 1092 PHILinearize PHIInfo; 1093 DenseMap<MachineBasicBlock *, MachineBasicBlock *> FallthroughMap; 1094 RegionMRT *RMRT; 1095 1096 void getPHIRegionIndices(RegionMRT *Region, MachineInstr &PHI, 1097 SmallVector<unsigned, 2> &RegionIndices); 1098 void getPHIRegionIndices(LinearizedRegion *Region, MachineInstr &PHI, 1099 SmallVector<unsigned, 2> &RegionIndices); 1100 void getPHINonRegionIndices(LinearizedRegion *Region, MachineInstr &PHI, 1101 SmallVector<unsigned, 2> &PHINonRegionIndices); 1102 1103 void storePHILinearizationInfoDest( 1104 unsigned LDestReg, MachineInstr &PHI, 1105 SmallVector<unsigned, 2> *RegionIndices = nullptr); 1106 1107 unsigned storePHILinearizationInfo(MachineInstr &PHI, 1108 SmallVector<unsigned, 2> *RegionIndices); 1109 1110 void extractKilledPHIs(MachineBasicBlock *MBB); 1111 1112 bool shrinkPHI(MachineInstr &PHI, SmallVector<unsigned, 2> &PHIIndices, 1113 unsigned *ReplaceReg); 1114 1115 bool shrinkPHI(MachineInstr &PHI, unsigned CombinedSourceReg, 1116 MachineBasicBlock *SourceMBB, 1117 SmallVector<unsigned, 2> &PHIIndices, unsigned *ReplaceReg); 1118 1119 void replacePHI(MachineInstr &PHI, unsigned CombinedSourceReg, 1120 MachineBasicBlock *LastMerge, 1121 SmallVector<unsigned, 2> &PHIRegionIndices); 1122 void replaceEntryPHI(MachineInstr &PHI, unsigned CombinedSourceReg, 1123 MachineBasicBlock *IfMBB, 1124 SmallVector<unsigned, 2> &PHIRegionIndices); 1125 void replaceLiveOutRegs(MachineInstr &PHI, 1126 SmallVector<unsigned, 2> &PHIRegionIndices, 1127 unsigned CombinedSourceReg, 1128 LinearizedRegion *LRegion); 1129 void rewriteRegionExitPHI(RegionMRT *Region, MachineBasicBlock *LastMerge, 1130 MachineInstr &PHI, LinearizedRegion *LRegion); 1131 1132 void rewriteRegionExitPHIs(RegionMRT *Region, MachineBasicBlock *LastMerge, 1133 LinearizedRegion *LRegion); 1134 void rewriteRegionEntryPHI(LinearizedRegion *Region, MachineBasicBlock *IfMBB, 1135 MachineInstr &PHI); 1136 void rewriteRegionEntryPHIs(LinearizedRegion *Region, 1137 MachineBasicBlock *IfMBB); 1138 1139 bool regionIsSimpleIf(RegionMRT *Region); 1140 1141 void transformSimpleIfRegion(RegionMRT *Region); 1142 1143 void eliminateDeadBranchOperands(MachineBasicBlock::instr_iterator &II); 1144 1145 void insertUnconditionalBranch(MachineBasicBlock *MBB, 1146 MachineBasicBlock *Dest, 1147 const DebugLoc &DL = DebugLoc()); 1148 1149 MachineBasicBlock *createLinearizedExitBlock(RegionMRT *Region); 1150 1151 void insertMergePHI(MachineBasicBlock *IfBB, MachineBasicBlock *CodeBB, 1152 MachineBasicBlock *MergeBB, unsigned DestRegister, 1153 unsigned IfSourceRegister, unsigned CodeSourceRegister, 1154 bool IsUndefIfSource = false); 1155 1156 MachineBasicBlock *createIfBlock(MachineBasicBlock *MergeBB, 1157 MachineBasicBlock *CodeBBStart, 1158 MachineBasicBlock *CodeBBEnd, 1159 MachineBasicBlock *SelectBB, unsigned IfReg, 1160 bool InheritPreds); 1161 1162 void prunePHIInfo(MachineBasicBlock *MBB); 1163 void createEntryPHI(LinearizedRegion *CurrentRegion, unsigned DestReg); 1164 1165 void createEntryPHIs(LinearizedRegion *CurrentRegion); 1166 void resolvePHIInfos(MachineBasicBlock *FunctionEntry); 1167 1168 void replaceRegisterWith(unsigned Register, unsigned NewRegister); 1169 1170 MachineBasicBlock *createIfRegion(MachineBasicBlock *MergeBB, 1171 MachineBasicBlock *CodeBB, 1172 LinearizedRegion *LRegion, 1173 unsigned BBSelectRegIn, 1174 unsigned BBSelectRegOut); 1175 1176 MachineBasicBlock * 1177 createIfRegion(MachineBasicBlock *MergeMBB, LinearizedRegion *InnerRegion, 1178 LinearizedRegion *CurrentRegion, MachineBasicBlock *SelectBB, 1179 unsigned BBSelectRegIn, unsigned BBSelectRegOut); 1180 void ensureCondIsNotKilled(SmallVector<MachineOperand, 1> Cond); 1181 1182 void rewriteCodeBBTerminator(MachineBasicBlock *CodeBB, 1183 MachineBasicBlock *MergeBB, 1184 unsigned BBSelectReg); 1185 1186 MachineInstr *getDefInstr(unsigned Reg); 1187 void insertChainedPHI(MachineBasicBlock *IfBB, MachineBasicBlock *CodeBB, 1188 MachineBasicBlock *MergeBB, 1189 LinearizedRegion *InnerRegion, unsigned DestReg, 1190 unsigned SourceReg); 1191 bool containsDef(MachineBasicBlock *MBB, LinearizedRegion *InnerRegion, 1192 unsigned Register); 1193 void rewriteLiveOutRegs(MachineBasicBlock *IfBB, MachineBasicBlock *CodeBB, 1194 MachineBasicBlock *MergeBB, 1195 LinearizedRegion *InnerRegion, 1196 LinearizedRegion *LRegion); 1197 1198 void splitLoopPHI(MachineInstr &PHI, MachineBasicBlock *Entry, 1199 MachineBasicBlock *EntrySucc, LinearizedRegion *LRegion); 1200 void splitLoopPHIs(MachineBasicBlock *Entry, MachineBasicBlock *EntrySucc, 1201 LinearizedRegion *LRegion); 1202 1203 MachineBasicBlock *splitExit(LinearizedRegion *LRegion); 1204 1205 MachineBasicBlock *splitEntry(LinearizedRegion *LRegion); 1206 1207 LinearizedRegion *initLinearizedRegion(RegionMRT *Region); 1208 1209 bool structurizeComplexRegion(RegionMRT *Region); 1210 1211 bool structurizeRegion(RegionMRT *Region); 1212 1213 bool structurizeRegions(RegionMRT *Region, bool isTopRegion); 1214 1215 public: 1216 static char ID; 1217 1218 AMDGPUMachineCFGStructurizer() : MachineFunctionPass(ID) { 1219 initializeAMDGPUMachineCFGStructurizerPass(*PassRegistry::getPassRegistry()); 1220 } 1221 1222 void getAnalysisUsage(AnalysisUsage &AU) const override { 1223 AU.addRequired<MachineRegionInfoPass>(); 1224 MachineFunctionPass::getAnalysisUsage(AU); 1225 } 1226 1227 void initFallthroughMap(MachineFunction &MF); 1228 1229 void createLinearizedRegion(RegionMRT *Region, unsigned SelectOut); 1230 1231 unsigned initializeSelectRegisters(MRT *MRT, unsigned ExistingExitReg, 1232 MachineRegisterInfo *MRI, 1233 const SIInstrInfo *TII); 1234 1235 void setRegionMRT(RegionMRT *RegionTree) { RMRT = RegionTree; } 1236 1237 RegionMRT *getRegionMRT() { return RMRT; } 1238 1239 bool runOnMachineFunction(MachineFunction &MF) override; 1240 }; 1241 1242 } // end anonymous namespace 1243 1244 char AMDGPUMachineCFGStructurizer::ID = 0; 1245 1246 bool AMDGPUMachineCFGStructurizer::regionIsSimpleIf(RegionMRT *Region) { 1247 MachineBasicBlock *Entry = Region->getEntry(); 1248 MachineBasicBlock *Succ = Region->getSucc(); 1249 bool FoundBypass = false; 1250 bool FoundIf = false; 1251 1252 if (Entry->succ_size() != 2) { 1253 return false; 1254 } 1255 1256 for (MachineBasicBlock::const_succ_iterator SI = Entry->succ_begin(), 1257 E = Entry->succ_end(); 1258 SI != E; ++SI) { 1259 MachineBasicBlock *Current = *SI; 1260 1261 if (Current == Succ) { 1262 FoundBypass = true; 1263 } else if ((Current->succ_size() == 1) && 1264 *(Current->succ_begin()) == Succ) { 1265 FoundIf = true; 1266 } 1267 } 1268 1269 return FoundIf && FoundBypass; 1270 } 1271 1272 void AMDGPUMachineCFGStructurizer::transformSimpleIfRegion(RegionMRT *Region) { 1273 MachineBasicBlock *Entry = Region->getEntry(); 1274 MachineBasicBlock *Exit = Region->getExit(); 1275 TII->convertNonUniformIfRegion(Entry, Exit); 1276 } 1277 1278 static void fixMBBTerminator(MachineBasicBlock *MBB) { 1279 if (MBB->succ_size() == 1) { 1280 auto *Succ = *(MBB->succ_begin()); 1281 for (auto &TI : MBB->terminators()) { 1282 for (auto &UI : TI.uses()) { 1283 if (UI.isMBB() && UI.getMBB() != Succ) { 1284 UI.setMBB(Succ); 1285 } 1286 } 1287 } 1288 } 1289 } 1290 1291 static void fixRegionTerminator(RegionMRT *Region) { 1292 MachineBasicBlock *InternalSucc = nullptr; 1293 MachineBasicBlock *ExternalSucc = nullptr; 1294 LinearizedRegion *LRegion = Region->getLinearizedRegion(); 1295 auto Exit = LRegion->getExit(); 1296 1297 SmallPtrSet<MachineBasicBlock *, 2> Successors; 1298 for (MachineBasicBlock::const_succ_iterator SI = Exit->succ_begin(), 1299 SE = Exit->succ_end(); 1300 SI != SE; ++SI) { 1301 MachineBasicBlock *Succ = *SI; 1302 if (LRegion->contains(Succ)) { 1303 // Do not allow re-assign 1304 assert(InternalSucc == nullptr); 1305 InternalSucc = Succ; 1306 } else { 1307 // Do not allow re-assign 1308 assert(ExternalSucc == nullptr); 1309 ExternalSucc = Succ; 1310 } 1311 } 1312 1313 for (auto &TI : Exit->terminators()) { 1314 for (auto &UI : TI.uses()) { 1315 if (UI.isMBB()) { 1316 auto Target = UI.getMBB(); 1317 if (Target != InternalSucc && Target != ExternalSucc) { 1318 UI.setMBB(ExternalSucc); 1319 } 1320 } 1321 } 1322 } 1323 } 1324 1325 // If a region region is just a sequence of regions (and the exit 1326 // block in the case of the top level region), we can simply skip 1327 // linearizing it, because it is already linear 1328 bool regionIsSequence(RegionMRT *Region) { 1329 auto Children = Region->getChildren(); 1330 for (auto CI : *Children) { 1331 if (!CI->isRegion()) { 1332 if (CI->getMBBMRT()->getMBB()->succ_size() > 1) { 1333 return false; 1334 } 1335 } 1336 } 1337 return true; 1338 } 1339 1340 void fixupRegionExits(RegionMRT *Region) { 1341 auto Children = Region->getChildren(); 1342 for (auto CI : *Children) { 1343 if (!CI->isRegion()) { 1344 fixMBBTerminator(CI->getMBBMRT()->getMBB()); 1345 } else { 1346 fixRegionTerminator(CI->getRegionMRT()); 1347 } 1348 } 1349 } 1350 1351 void AMDGPUMachineCFGStructurizer::getPHIRegionIndices( 1352 RegionMRT *Region, MachineInstr &PHI, 1353 SmallVector<unsigned, 2> &PHIRegionIndices) { 1354 unsigned NumInputs = getPHINumInputs(PHI); 1355 for (unsigned i = 0; i < NumInputs; ++i) { 1356 MachineBasicBlock *Pred = getPHIPred(PHI, i); 1357 if (Region->contains(Pred)) { 1358 PHIRegionIndices.push_back(i); 1359 } 1360 } 1361 } 1362 1363 void AMDGPUMachineCFGStructurizer::getPHIRegionIndices( 1364 LinearizedRegion *Region, MachineInstr &PHI, 1365 SmallVector<unsigned, 2> &PHIRegionIndices) { 1366 unsigned NumInputs = getPHINumInputs(PHI); 1367 for (unsigned i = 0; i < NumInputs; ++i) { 1368 MachineBasicBlock *Pred = getPHIPred(PHI, i); 1369 if (Region->contains(Pred)) { 1370 PHIRegionIndices.push_back(i); 1371 } 1372 } 1373 } 1374 1375 void AMDGPUMachineCFGStructurizer::getPHINonRegionIndices( 1376 LinearizedRegion *Region, MachineInstr &PHI, 1377 SmallVector<unsigned, 2> &PHINonRegionIndices) { 1378 unsigned NumInputs = getPHINumInputs(PHI); 1379 for (unsigned i = 0; i < NumInputs; ++i) { 1380 MachineBasicBlock *Pred = getPHIPred(PHI, i); 1381 if (!Region->contains(Pred)) { 1382 PHINonRegionIndices.push_back(i); 1383 } 1384 } 1385 } 1386 1387 void AMDGPUMachineCFGStructurizer::storePHILinearizationInfoDest( 1388 unsigned LDestReg, MachineInstr &PHI, 1389 SmallVector<unsigned, 2> *RegionIndices) { 1390 if (RegionIndices) { 1391 for (auto i : *RegionIndices) { 1392 PHIInfo.addSource(LDestReg, getPHISourceReg(PHI, i), getPHIPred(PHI, i)); 1393 } 1394 } else { 1395 unsigned NumInputs = getPHINumInputs(PHI); 1396 for (unsigned i = 0; i < NumInputs; ++i) { 1397 PHIInfo.addSource(LDestReg, getPHISourceReg(PHI, i), getPHIPred(PHI, i)); 1398 } 1399 } 1400 } 1401 1402 unsigned AMDGPUMachineCFGStructurizer::storePHILinearizationInfo( 1403 MachineInstr &PHI, SmallVector<unsigned, 2> *RegionIndices) { 1404 unsigned DestReg = getPHIDestReg(PHI); 1405 unsigned LinearizeDestReg = 1406 MRI->createVirtualRegister(MRI->getRegClass(DestReg)); 1407 PHIInfo.addDest(LinearizeDestReg, PHI.getDebugLoc()); 1408 storePHILinearizationInfoDest(LinearizeDestReg, PHI, RegionIndices); 1409 return LinearizeDestReg; 1410 } 1411 1412 void AMDGPUMachineCFGStructurizer::extractKilledPHIs(MachineBasicBlock *MBB) { 1413 // We need to create a new chain for the killed phi, but there is no 1414 // need to do the renaming outside or inside the block. 1415 SmallPtrSet<MachineInstr *, 2> PHIs; 1416 for (MachineBasicBlock::instr_iterator I = MBB->instr_begin(), 1417 E = MBB->instr_end(); 1418 I != E; ++I) { 1419 MachineInstr &Instr = *I; 1420 if (Instr.isPHI()) { 1421 unsigned PHIDestReg = getPHIDestReg(Instr); 1422 LLVM_DEBUG(dbgs() << "Extractking killed phi:\n"); 1423 LLVM_DEBUG(Instr.dump()); 1424 PHIs.insert(&Instr); 1425 PHIInfo.addDest(PHIDestReg, Instr.getDebugLoc()); 1426 storePHILinearizationInfoDest(PHIDestReg, Instr); 1427 } 1428 } 1429 1430 for (auto PI : PHIs) { 1431 PI->eraseFromParent(); 1432 } 1433 } 1434 1435 static bool isPHIRegionIndex(SmallVector<unsigned, 2> PHIRegionIndices, 1436 unsigned Index) { 1437 for (auto i : PHIRegionIndices) { 1438 if (i == Index) 1439 return true; 1440 } 1441 return false; 1442 } 1443 1444 bool AMDGPUMachineCFGStructurizer::shrinkPHI(MachineInstr &PHI, 1445 SmallVector<unsigned, 2> &PHIIndices, 1446 unsigned *ReplaceReg) { 1447 return shrinkPHI(PHI, 0, nullptr, PHIIndices, ReplaceReg); 1448 } 1449 1450 bool AMDGPUMachineCFGStructurizer::shrinkPHI(MachineInstr &PHI, 1451 unsigned CombinedSourceReg, 1452 MachineBasicBlock *SourceMBB, 1453 SmallVector<unsigned, 2> &PHIIndices, 1454 unsigned *ReplaceReg) { 1455 LLVM_DEBUG(dbgs() << "Shrink PHI: "); 1456 LLVM_DEBUG(PHI.dump()); 1457 LLVM_DEBUG(dbgs() << " to " << printReg(getPHIDestReg(PHI), TRI) 1458 << " = PHI("); 1459 1460 bool Replaced = false; 1461 unsigned NumInputs = getPHINumInputs(PHI); 1462 int SingleExternalEntryIndex = -1; 1463 for (unsigned i = 0; i < NumInputs; ++i) { 1464 if (!isPHIRegionIndex(PHIIndices, i)) { 1465 if (SingleExternalEntryIndex == -1) { 1466 // Single entry 1467 SingleExternalEntryIndex = i; 1468 } else { 1469 // Multiple entries 1470 SingleExternalEntryIndex = -2; 1471 } 1472 } 1473 } 1474 1475 if (SingleExternalEntryIndex > -1) { 1476 *ReplaceReg = getPHISourceReg(PHI, SingleExternalEntryIndex); 1477 // We should not rewrite the code, we should only pick up the single value 1478 // that represents the shrunk PHI. 1479 Replaced = true; 1480 } else { 1481 MachineBasicBlock *MBB = PHI.getParent(); 1482 MachineInstrBuilder MIB = 1483 BuildMI(*MBB, PHI, PHI.getDebugLoc(), TII->get(TargetOpcode::PHI), 1484 getPHIDestReg(PHI)); 1485 if (SourceMBB) { 1486 MIB.addReg(CombinedSourceReg); 1487 MIB.addMBB(SourceMBB); 1488 LLVM_DEBUG(dbgs() << printReg(CombinedSourceReg, TRI) << ", " 1489 << printMBBReference(*SourceMBB)); 1490 } 1491 1492 for (unsigned i = 0; i < NumInputs; ++i) { 1493 if (isPHIRegionIndex(PHIIndices, i)) { 1494 continue; 1495 } 1496 unsigned SourceReg = getPHISourceReg(PHI, i); 1497 MachineBasicBlock *SourcePred = getPHIPred(PHI, i); 1498 MIB.addReg(SourceReg); 1499 MIB.addMBB(SourcePred); 1500 LLVM_DEBUG(dbgs() << printReg(SourceReg, TRI) << ", " 1501 << printMBBReference(*SourcePred)); 1502 } 1503 LLVM_DEBUG(dbgs() << ")\n"); 1504 } 1505 PHI.eraseFromParent(); 1506 return Replaced; 1507 } 1508 1509 void AMDGPUMachineCFGStructurizer::replacePHI( 1510 MachineInstr &PHI, unsigned CombinedSourceReg, MachineBasicBlock *LastMerge, 1511 SmallVector<unsigned, 2> &PHIRegionIndices) { 1512 LLVM_DEBUG(dbgs() << "Replace PHI: "); 1513 LLVM_DEBUG(PHI.dump()); 1514 LLVM_DEBUG(dbgs() << " with " << printReg(getPHIDestReg(PHI), TRI) 1515 << " = PHI("); 1516 1517 bool HasExternalEdge = false; 1518 unsigned NumInputs = getPHINumInputs(PHI); 1519 for (unsigned i = 0; i < NumInputs; ++i) { 1520 if (!isPHIRegionIndex(PHIRegionIndices, i)) { 1521 HasExternalEdge = true; 1522 } 1523 } 1524 1525 if (HasExternalEdge) { 1526 MachineBasicBlock *MBB = PHI.getParent(); 1527 MachineInstrBuilder MIB = 1528 BuildMI(*MBB, PHI, PHI.getDebugLoc(), TII->get(TargetOpcode::PHI), 1529 getPHIDestReg(PHI)); 1530 MIB.addReg(CombinedSourceReg); 1531 MIB.addMBB(LastMerge); 1532 LLVM_DEBUG(dbgs() << printReg(CombinedSourceReg, TRI) << ", " 1533 << printMBBReference(*LastMerge)); 1534 for (unsigned i = 0; i < NumInputs; ++i) { 1535 if (isPHIRegionIndex(PHIRegionIndices, i)) { 1536 continue; 1537 } 1538 unsigned SourceReg = getPHISourceReg(PHI, i); 1539 MachineBasicBlock *SourcePred = getPHIPred(PHI, i); 1540 MIB.addReg(SourceReg); 1541 MIB.addMBB(SourcePred); 1542 LLVM_DEBUG(dbgs() << printReg(SourceReg, TRI) << ", " 1543 << printMBBReference(*SourcePred)); 1544 } 1545 LLVM_DEBUG(dbgs() << ")\n"); 1546 } else { 1547 replaceRegisterWith(getPHIDestReg(PHI), CombinedSourceReg); 1548 } 1549 PHI.eraseFromParent(); 1550 } 1551 1552 void AMDGPUMachineCFGStructurizer::replaceEntryPHI( 1553 MachineInstr &PHI, unsigned CombinedSourceReg, MachineBasicBlock *IfMBB, 1554 SmallVector<unsigned, 2> &PHIRegionIndices) { 1555 LLVM_DEBUG(dbgs() << "Replace entry PHI: "); 1556 LLVM_DEBUG(PHI.dump()); 1557 LLVM_DEBUG(dbgs() << " with "); 1558 1559 unsigned NumInputs = getPHINumInputs(PHI); 1560 unsigned NumNonRegionInputs = NumInputs; 1561 for (unsigned i = 0; i < NumInputs; ++i) { 1562 if (isPHIRegionIndex(PHIRegionIndices, i)) { 1563 NumNonRegionInputs--; 1564 } 1565 } 1566 1567 if (NumNonRegionInputs == 0) { 1568 auto DestReg = getPHIDestReg(PHI); 1569 replaceRegisterWith(DestReg, CombinedSourceReg); 1570 LLVM_DEBUG(dbgs() << " register " << printReg(CombinedSourceReg, TRI) 1571 << "\n"); 1572 PHI.eraseFromParent(); 1573 } else { 1574 LLVM_DEBUG(dbgs() << printReg(getPHIDestReg(PHI), TRI) << " = PHI("); 1575 MachineBasicBlock *MBB = PHI.getParent(); 1576 MachineInstrBuilder MIB = 1577 BuildMI(*MBB, PHI, PHI.getDebugLoc(), TII->get(TargetOpcode::PHI), 1578 getPHIDestReg(PHI)); 1579 MIB.addReg(CombinedSourceReg); 1580 MIB.addMBB(IfMBB); 1581 LLVM_DEBUG(dbgs() << printReg(CombinedSourceReg, TRI) << ", " 1582 << printMBBReference(*IfMBB)); 1583 unsigned NumInputs = getPHINumInputs(PHI); 1584 for (unsigned i = 0; i < NumInputs; ++i) { 1585 if (isPHIRegionIndex(PHIRegionIndices, i)) { 1586 continue; 1587 } 1588 unsigned SourceReg = getPHISourceReg(PHI, i); 1589 MachineBasicBlock *SourcePred = getPHIPred(PHI, i); 1590 MIB.addReg(SourceReg); 1591 MIB.addMBB(SourcePred); 1592 LLVM_DEBUG(dbgs() << printReg(SourceReg, TRI) << ", " 1593 << printMBBReference(*SourcePred)); 1594 } 1595 LLVM_DEBUG(dbgs() << ")\n"); 1596 PHI.eraseFromParent(); 1597 } 1598 } 1599 1600 void AMDGPUMachineCFGStructurizer::replaceLiveOutRegs( 1601 MachineInstr &PHI, SmallVector<unsigned, 2> &PHIRegionIndices, 1602 unsigned CombinedSourceReg, LinearizedRegion *LRegion) { 1603 bool WasLiveOut = false; 1604 for (auto PII : PHIRegionIndices) { 1605 unsigned Reg = getPHISourceReg(PHI, PII); 1606 if (LRegion->isLiveOut(Reg)) { 1607 bool IsDead = true; 1608 1609 // Check if register is live out of the basic block 1610 MachineBasicBlock *DefMBB = getDefInstr(Reg)->getParent(); 1611 for (auto UI = MRI->use_begin(Reg), E = MRI->use_end(); UI != E; ++UI) { 1612 if ((*UI).getParent()->getParent() != DefMBB) { 1613 IsDead = false; 1614 } 1615 } 1616 1617 LLVM_DEBUG(dbgs() << "Register " << printReg(Reg, TRI) << " is " 1618 << (IsDead ? "dead" : "alive") 1619 << " after PHI replace\n"); 1620 if (IsDead) { 1621 LRegion->removeLiveOut(Reg); 1622 } 1623 WasLiveOut = true; 1624 } 1625 } 1626 1627 if (WasLiveOut) 1628 LRegion->addLiveOut(CombinedSourceReg); 1629 } 1630 1631 void AMDGPUMachineCFGStructurizer::rewriteRegionExitPHI(RegionMRT *Region, 1632 MachineBasicBlock *LastMerge, 1633 MachineInstr &PHI, 1634 LinearizedRegion *LRegion) { 1635 SmallVector<unsigned, 2> PHIRegionIndices; 1636 getPHIRegionIndices(Region, PHI, PHIRegionIndices); 1637 unsigned LinearizedSourceReg = 1638 storePHILinearizationInfo(PHI, &PHIRegionIndices); 1639 1640 replacePHI(PHI, LinearizedSourceReg, LastMerge, PHIRegionIndices); 1641 replaceLiveOutRegs(PHI, PHIRegionIndices, LinearizedSourceReg, LRegion); 1642 } 1643 1644 void AMDGPUMachineCFGStructurizer::rewriteRegionEntryPHI(LinearizedRegion *Region, 1645 MachineBasicBlock *IfMBB, 1646 MachineInstr &PHI) { 1647 SmallVector<unsigned, 2> PHINonRegionIndices; 1648 getPHINonRegionIndices(Region, PHI, PHINonRegionIndices); 1649 unsigned LinearizedSourceReg = 1650 storePHILinearizationInfo(PHI, &PHINonRegionIndices); 1651 replaceEntryPHI(PHI, LinearizedSourceReg, IfMBB, PHINonRegionIndices); 1652 } 1653 1654 static void collectPHIs(MachineBasicBlock *MBB, 1655 SmallVector<MachineInstr *, 2> &PHIs) { 1656 for (auto &BBI : *MBB) { 1657 if (BBI.isPHI()) { 1658 PHIs.push_back(&BBI); 1659 } 1660 } 1661 } 1662 1663 void AMDGPUMachineCFGStructurizer::rewriteRegionExitPHIs(RegionMRT *Region, 1664 MachineBasicBlock *LastMerge, 1665 LinearizedRegion *LRegion) { 1666 SmallVector<MachineInstr *, 2> PHIs; 1667 auto Exit = Region->getSucc(); 1668 if (Exit == nullptr) 1669 return; 1670 1671 collectPHIs(Exit, PHIs); 1672 1673 for (auto PHII : PHIs) { 1674 rewriteRegionExitPHI(Region, LastMerge, *PHII, LRegion); 1675 } 1676 } 1677 1678 void AMDGPUMachineCFGStructurizer::rewriteRegionEntryPHIs(LinearizedRegion *Region, 1679 MachineBasicBlock *IfMBB) { 1680 SmallVector<MachineInstr *, 2> PHIs; 1681 auto Entry = Region->getEntry(); 1682 1683 collectPHIs(Entry, PHIs); 1684 1685 for (auto PHII : PHIs) { 1686 rewriteRegionEntryPHI(Region, IfMBB, *PHII); 1687 } 1688 } 1689 1690 void AMDGPUMachineCFGStructurizer::insertUnconditionalBranch(MachineBasicBlock *MBB, 1691 MachineBasicBlock *Dest, 1692 const DebugLoc &DL) { 1693 LLVM_DEBUG(dbgs() << "Inserting unconditional branch: " << MBB->getNumber() 1694 << " -> " << Dest->getNumber() << "\n"); 1695 MachineBasicBlock::instr_iterator Terminator = MBB->getFirstInstrTerminator(); 1696 bool HasTerminator = Terminator != MBB->instr_end(); 1697 if (HasTerminator) { 1698 TII->ReplaceTailWithBranchTo(Terminator, Dest); 1699 } 1700 if (++MachineFunction::iterator(MBB) != MachineFunction::iterator(Dest)) { 1701 TII->insertUnconditionalBranch(*MBB, Dest, DL); 1702 } 1703 } 1704 1705 static MachineBasicBlock *getSingleExitNode(MachineFunction &MF) { 1706 MachineBasicBlock *result = nullptr; 1707 for (auto &MFI : MF) { 1708 if (MFI.succ_size() == 0) { 1709 if (result == nullptr) { 1710 result = &MFI; 1711 } else { 1712 return nullptr; 1713 } 1714 } 1715 } 1716 1717 return result; 1718 } 1719 1720 static bool hasOneExitNode(MachineFunction &MF) { 1721 return getSingleExitNode(MF) != nullptr; 1722 } 1723 1724 MachineBasicBlock * 1725 AMDGPUMachineCFGStructurizer::createLinearizedExitBlock(RegionMRT *Region) { 1726 auto Exit = Region->getSucc(); 1727 1728 // If the exit is the end of the function, we just use the existing 1729 MachineFunction *MF = Region->getEntry()->getParent(); 1730 if (Exit == nullptr && hasOneExitNode(*MF)) { 1731 return &(*(--(Region->getEntry()->getParent()->end()))); 1732 } 1733 1734 MachineBasicBlock *LastMerge = MF->CreateMachineBasicBlock(); 1735 if (Exit == nullptr) { 1736 MachineFunction::iterator ExitIter = MF->end(); 1737 MF->insert(ExitIter, LastMerge); 1738 } else { 1739 MachineFunction::iterator ExitIter = Exit->getIterator(); 1740 MF->insert(ExitIter, LastMerge); 1741 LastMerge->addSuccessor(Exit); 1742 insertUnconditionalBranch(LastMerge, Exit); 1743 LLVM_DEBUG(dbgs() << "Created exit block: " << LastMerge->getNumber() 1744 << "\n"); 1745 } 1746 return LastMerge; 1747 } 1748 1749 void AMDGPUMachineCFGStructurizer::insertMergePHI(MachineBasicBlock *IfBB, 1750 MachineBasicBlock *CodeBB, 1751 MachineBasicBlock *MergeBB, 1752 unsigned DestRegister, 1753 unsigned IfSourceRegister, 1754 unsigned CodeSourceRegister, 1755 bool IsUndefIfSource) { 1756 // If this is the function exit block, we don't need a phi. 1757 if (MergeBB->succ_begin() == MergeBB->succ_end()) { 1758 return; 1759 } 1760 LLVM_DEBUG(dbgs() << "Merge PHI (" << printMBBReference(*MergeBB) 1761 << "): " << printReg(DestRegister, TRI) << " = PHI(" 1762 << printReg(IfSourceRegister, TRI) << ", " 1763 << printMBBReference(*IfBB) 1764 << printReg(CodeSourceRegister, TRI) << ", " 1765 << printMBBReference(*CodeBB) << ")\n"); 1766 const DebugLoc &DL = MergeBB->findDebugLoc(MergeBB->begin()); 1767 MachineInstrBuilder MIB = BuildMI(*MergeBB, MergeBB->instr_begin(), DL, 1768 TII->get(TargetOpcode::PHI), DestRegister); 1769 if (IsUndefIfSource && false) { 1770 MIB.addReg(IfSourceRegister, RegState::Undef); 1771 } else { 1772 MIB.addReg(IfSourceRegister); 1773 } 1774 MIB.addMBB(IfBB); 1775 MIB.addReg(CodeSourceRegister); 1776 MIB.addMBB(CodeBB); 1777 } 1778 1779 static void removeExternalCFGSuccessors(MachineBasicBlock *MBB) { 1780 for (MachineBasicBlock::succ_iterator PI = MBB->succ_begin(), 1781 E = MBB->succ_end(); 1782 PI != E; ++PI) { 1783 if ((*PI) != MBB) { 1784 (MBB)->removeSuccessor(*PI); 1785 } 1786 } 1787 } 1788 1789 static void removeExternalCFGEdges(MachineBasicBlock *StartMBB, 1790 MachineBasicBlock *EndMBB) { 1791 1792 // We have to check against the StartMBB successor becasuse a 1793 // structurized region with a loop will have the entry block split, 1794 // and the backedge will go to the entry successor. 1795 DenseSet<std::pair<MachineBasicBlock *, MachineBasicBlock *>> Succs; 1796 unsigned SuccSize = StartMBB->succ_size(); 1797 if (SuccSize > 0) { 1798 MachineBasicBlock *StartMBBSucc = *(StartMBB->succ_begin()); 1799 for (MachineBasicBlock::succ_iterator PI = EndMBB->succ_begin(), 1800 E = EndMBB->succ_end(); 1801 PI != E; ++PI) { 1802 // Either we have a back-edge to the entry block, or a back-edge to the 1803 // successor of the entry block since the block may be split. 1804 if ((*PI) != StartMBB && 1805 !((*PI) == StartMBBSucc && StartMBB != EndMBB && SuccSize == 1)) { 1806 Succs.insert( 1807 std::pair<MachineBasicBlock *, MachineBasicBlock *>(EndMBB, *PI)); 1808 } 1809 } 1810 } 1811 1812 for (MachineBasicBlock::pred_iterator PI = StartMBB->pred_begin(), 1813 E = StartMBB->pred_end(); 1814 PI != E; ++PI) { 1815 if ((*PI) != EndMBB) { 1816 Succs.insert( 1817 std::pair<MachineBasicBlock *, MachineBasicBlock *>(*PI, StartMBB)); 1818 } 1819 } 1820 1821 for (auto SI : Succs) { 1822 std::pair<MachineBasicBlock *, MachineBasicBlock *> Edge = SI; 1823 LLVM_DEBUG(dbgs() << "Removing edge: " << printMBBReference(*Edge.first) 1824 << " -> " << printMBBReference(*Edge.second) << "\n"); 1825 Edge.first->removeSuccessor(Edge.second); 1826 } 1827 } 1828 1829 MachineBasicBlock *AMDGPUMachineCFGStructurizer::createIfBlock( 1830 MachineBasicBlock *MergeBB, MachineBasicBlock *CodeBBStart, 1831 MachineBasicBlock *CodeBBEnd, MachineBasicBlock *SelectBB, unsigned IfReg, 1832 bool InheritPreds) { 1833 MachineFunction *MF = MergeBB->getParent(); 1834 MachineBasicBlock *IfBB = MF->CreateMachineBasicBlock(); 1835 1836 if (InheritPreds) { 1837 for (MachineBasicBlock::pred_iterator PI = CodeBBStart->pred_begin(), 1838 E = CodeBBStart->pred_end(); 1839 PI != E; ++PI) { 1840 if ((*PI) != CodeBBEnd) { 1841 MachineBasicBlock *Pred = (*PI); 1842 Pred->addSuccessor(IfBB); 1843 } 1844 } 1845 } 1846 1847 removeExternalCFGEdges(CodeBBStart, CodeBBEnd); 1848 1849 auto CodeBBStartI = CodeBBStart->getIterator(); 1850 auto CodeBBEndI = CodeBBEnd->getIterator(); 1851 auto MergeIter = MergeBB->getIterator(); 1852 MF->insert(MergeIter, IfBB); 1853 MF->splice(MergeIter, CodeBBStartI, ++CodeBBEndI); 1854 IfBB->addSuccessor(MergeBB); 1855 IfBB->addSuccessor(CodeBBStart); 1856 1857 LLVM_DEBUG(dbgs() << "Created If block: " << IfBB->getNumber() << "\n"); 1858 // Ensure that the MergeBB is a successor of the CodeEndBB. 1859 if (!CodeBBEnd->isSuccessor(MergeBB)) 1860 CodeBBEnd->addSuccessor(MergeBB); 1861 1862 LLVM_DEBUG(dbgs() << "Moved " << printMBBReference(*CodeBBStart) 1863 << " through " << printMBBReference(*CodeBBEnd) << "\n"); 1864 1865 // If we have a single predecessor we can find a reasonable debug location 1866 MachineBasicBlock *SinglePred = 1867 CodeBBStart->pred_size() == 1 ? *(CodeBBStart->pred_begin()) : nullptr; 1868 const DebugLoc &DL = SinglePred 1869 ? SinglePred->findDebugLoc(SinglePred->getFirstTerminator()) 1870 : DebugLoc(); 1871 1872 unsigned Reg = 1873 TII->insertEQ(IfBB, IfBB->begin(), DL, IfReg, 1874 SelectBB->getNumber() /* CodeBBStart->getNumber() */); 1875 if (&(*(IfBB->getParent()->begin())) == IfBB) { 1876 TII->materializeImmediate(*IfBB, IfBB->begin(), DL, IfReg, 1877 CodeBBStart->getNumber()); 1878 } 1879 MachineOperand RegOp = MachineOperand::CreateReg(Reg, false, false, true); 1880 ArrayRef<MachineOperand> Cond(RegOp); 1881 TII->insertBranch(*IfBB, MergeBB, CodeBBStart, Cond, DL); 1882 1883 return IfBB; 1884 } 1885 1886 void AMDGPUMachineCFGStructurizer::ensureCondIsNotKilled( 1887 SmallVector<MachineOperand, 1> Cond) { 1888 if (Cond.size() != 1) 1889 return; 1890 if (!Cond[0].isReg()) 1891 return; 1892 1893 unsigned CondReg = Cond[0].getReg(); 1894 for (auto UI = MRI->use_begin(CondReg), E = MRI->use_end(); UI != E; ++UI) { 1895 (*UI).setIsKill(false); 1896 } 1897 } 1898 1899 void AMDGPUMachineCFGStructurizer::rewriteCodeBBTerminator(MachineBasicBlock *CodeBB, 1900 MachineBasicBlock *MergeBB, 1901 unsigned BBSelectReg) { 1902 MachineBasicBlock *TrueBB = nullptr; 1903 MachineBasicBlock *FalseBB = nullptr; 1904 SmallVector<MachineOperand, 1> Cond; 1905 MachineBasicBlock *FallthroughBB = FallthroughMap[CodeBB]; 1906 TII->analyzeBranch(*CodeBB, TrueBB, FalseBB, Cond); 1907 1908 const DebugLoc &DL = CodeBB->findDebugLoc(CodeBB->getFirstTerminator()); 1909 1910 if (FalseBB == nullptr && TrueBB == nullptr && FallthroughBB == nullptr) { 1911 // This is an exit block, hence no successors. We will assign the 1912 // bb select register to the entry block. 1913 TII->materializeImmediate(*CodeBB, CodeBB->getFirstTerminator(), DL, 1914 BBSelectReg, 1915 CodeBB->getParent()->begin()->getNumber()); 1916 insertUnconditionalBranch(CodeBB, MergeBB, DL); 1917 return; 1918 } 1919 1920 if (FalseBB == nullptr && TrueBB == nullptr) { 1921 TrueBB = FallthroughBB; 1922 } else if (TrueBB != nullptr) { 1923 FalseBB = 1924 (FallthroughBB && (FallthroughBB != TrueBB)) ? FallthroughBB : FalseBB; 1925 } 1926 1927 if ((TrueBB != nullptr && FalseBB == nullptr) || (TrueBB == FalseBB)) { 1928 TII->materializeImmediate(*CodeBB, CodeBB->getFirstTerminator(), DL, 1929 BBSelectReg, TrueBB->getNumber()); 1930 } else { 1931 const TargetRegisterClass *RegClass = MRI->getRegClass(BBSelectReg); 1932 unsigned TrueBBReg = MRI->createVirtualRegister(RegClass); 1933 unsigned FalseBBReg = MRI->createVirtualRegister(RegClass); 1934 TII->materializeImmediate(*CodeBB, CodeBB->getFirstTerminator(), DL, 1935 TrueBBReg, TrueBB->getNumber()); 1936 TII->materializeImmediate(*CodeBB, CodeBB->getFirstTerminator(), DL, 1937 FalseBBReg, FalseBB->getNumber()); 1938 ensureCondIsNotKilled(Cond); 1939 TII->insertVectorSelect(*CodeBB, CodeBB->getFirstTerminator(), DL, 1940 BBSelectReg, Cond, TrueBBReg, FalseBBReg); 1941 } 1942 1943 insertUnconditionalBranch(CodeBB, MergeBB, DL); 1944 } 1945 1946 MachineInstr *AMDGPUMachineCFGStructurizer::getDefInstr(unsigned Reg) { 1947 if (MRI->def_begin(Reg) == MRI->def_end()) { 1948 LLVM_DEBUG(dbgs() << "Register " 1949 << printReg(Reg, MRI->getTargetRegisterInfo()) 1950 << " has NO defs\n"); 1951 } else if (!MRI->hasOneDef(Reg)) { 1952 LLVM_DEBUG(dbgs() << "Register " 1953 << printReg(Reg, MRI->getTargetRegisterInfo()) 1954 << " has multiple defs\n"); 1955 LLVM_DEBUG(dbgs() << "DEFS BEGIN:\n"); 1956 for (auto DI = MRI->def_begin(Reg), DE = MRI->def_end(); DI != DE; ++DI) { 1957 LLVM_DEBUG(DI->getParent()->dump()); 1958 } 1959 LLVM_DEBUG(dbgs() << "DEFS END\n"); 1960 } 1961 1962 assert(MRI->hasOneDef(Reg) && "Register has multiple definitions"); 1963 return (*(MRI->def_begin(Reg))).getParent(); 1964 } 1965 1966 void AMDGPUMachineCFGStructurizer::insertChainedPHI(MachineBasicBlock *IfBB, 1967 MachineBasicBlock *CodeBB, 1968 MachineBasicBlock *MergeBB, 1969 LinearizedRegion *InnerRegion, 1970 unsigned DestReg, 1971 unsigned SourceReg) { 1972 // In this function we know we are part of a chain already, so we need 1973 // to add the registers to the existing chain, and rename the register 1974 // inside the region. 1975 bool IsSingleBB = InnerRegion->getEntry() == InnerRegion->getExit(); 1976 MachineInstr *DefInstr = getDefInstr(SourceReg); 1977 if (DefInstr->isPHI() && DefInstr->getParent() == CodeBB && IsSingleBB) { 1978 // Handle the case where the def is a PHI-def inside a basic 1979 // block, then we only need to do renaming. Special care needs to 1980 // be taken if the PHI-def is part of an existing chain, or if a 1981 // new one needs to be created. 1982 InnerRegion->replaceRegisterInsideRegion(SourceReg, DestReg, true, MRI); 1983 1984 // We collect all PHI Information, and if we are at the region entry, 1985 // all PHIs will be removed, and then re-introduced if needed. 1986 storePHILinearizationInfoDest(DestReg, *DefInstr); 1987 // We have picked up all the information we need now and can remove 1988 // the PHI 1989 PHIInfo.removeSource(DestReg, SourceReg, CodeBB); 1990 DefInstr->eraseFromParent(); 1991 } else { 1992 // If this is not a phi-def, or it is a phi-def but from a linearized region 1993 if (IsSingleBB && DefInstr->getParent() == InnerRegion->getEntry()) { 1994 // If this is a single BB and the definition is in this block we 1995 // need to replace any uses outside the region. 1996 InnerRegion->replaceRegisterOutsideRegion(SourceReg, DestReg, false, MRI); 1997 } 1998 const TargetRegisterClass *RegClass = MRI->getRegClass(DestReg); 1999 unsigned NextDestReg = MRI->createVirtualRegister(RegClass); 2000 bool IsLastDef = PHIInfo.getNumSources(DestReg) == 1; 2001 LLVM_DEBUG(dbgs() << "Insert Chained PHI\n"); 2002 insertMergePHI(IfBB, InnerRegion->getExit(), MergeBB, DestReg, NextDestReg, 2003 SourceReg, IsLastDef); 2004 2005 PHIInfo.removeSource(DestReg, SourceReg, CodeBB); 2006 if (IsLastDef) { 2007 const DebugLoc &DL = IfBB->findDebugLoc(IfBB->getFirstTerminator()); 2008 TII->materializeImmediate(*IfBB, IfBB->getFirstTerminator(), DL, 2009 NextDestReg, 0); 2010 PHIInfo.deleteDef(DestReg); 2011 } else { 2012 PHIInfo.replaceDef(DestReg, NextDestReg); 2013 } 2014 } 2015 } 2016 2017 bool AMDGPUMachineCFGStructurizer::containsDef(MachineBasicBlock *MBB, 2018 LinearizedRegion *InnerRegion, 2019 unsigned Register) { 2020 return getDefInstr(Register)->getParent() == MBB || 2021 InnerRegion->contains(getDefInstr(Register)->getParent()); 2022 } 2023 2024 void AMDGPUMachineCFGStructurizer::rewriteLiveOutRegs(MachineBasicBlock *IfBB, 2025 MachineBasicBlock *CodeBB, 2026 MachineBasicBlock *MergeBB, 2027 LinearizedRegion *InnerRegion, 2028 LinearizedRegion *LRegion) { 2029 DenseSet<unsigned> *LiveOuts = InnerRegion->getLiveOuts(); 2030 SmallVector<unsigned, 4> OldLiveOuts; 2031 bool IsSingleBB = InnerRegion->getEntry() == InnerRegion->getExit(); 2032 for (auto OLI : *LiveOuts) { 2033 OldLiveOuts.push_back(OLI); 2034 } 2035 2036 for (auto LI : OldLiveOuts) { 2037 LLVM_DEBUG(dbgs() << "LiveOut: " << printReg(LI, TRI)); 2038 if (!containsDef(CodeBB, InnerRegion, LI) || 2039 (!IsSingleBB && (getDefInstr(LI)->getParent() == LRegion->getExit()))) { 2040 // If the register simly lives through the CodeBB, we don't have 2041 // to rewrite anything since the register is not defined in this 2042 // part of the code. 2043 LLVM_DEBUG(dbgs() << "- through"); 2044 continue; 2045 } 2046 LLVM_DEBUG(dbgs() << "\n"); 2047 unsigned Reg = LI; 2048 if (/*!PHIInfo.isSource(Reg) &&*/ Reg != InnerRegion->getBBSelectRegOut()) { 2049 // If the register is live out, we do want to create a phi, 2050 // unless it is from the Exit block, becasuse in that case there 2051 // is already a PHI, and no need to create a new one. 2052 2053 // If the register is just a live out def and not part of a phi 2054 // chain, we need to create a PHI node to handle the if region, 2055 // and replace all uses outside of the region with the new dest 2056 // register, unless it is the outgoing BB select register. We have 2057 // already creaed phi nodes for these. 2058 const TargetRegisterClass *RegClass = MRI->getRegClass(Reg); 2059 unsigned PHIDestReg = MRI->createVirtualRegister(RegClass); 2060 unsigned IfSourceReg = MRI->createVirtualRegister(RegClass); 2061 // Create initializer, this value is never used, but is needed 2062 // to satisfy SSA. 2063 LLVM_DEBUG(dbgs() << "Initializer for reg: " << printReg(Reg) << "\n"); 2064 TII->materializeImmediate(*IfBB, IfBB->getFirstTerminator(), DebugLoc(), 2065 IfSourceReg, 0); 2066 2067 InnerRegion->replaceRegisterOutsideRegion(Reg, PHIDestReg, true, MRI); 2068 LLVM_DEBUG(dbgs() << "Insert Non-Chained Live out PHI\n"); 2069 insertMergePHI(IfBB, InnerRegion->getExit(), MergeBB, PHIDestReg, 2070 IfSourceReg, Reg, true); 2071 } 2072 } 2073 2074 // Handle the chained definitions in PHIInfo, checking if this basic block 2075 // is a source block for a definition. 2076 SmallVector<unsigned, 4> Sources; 2077 if (PHIInfo.findSourcesFromMBB(CodeBB, Sources)) { 2078 LLVM_DEBUG(dbgs() << "Inserting PHI Live Out from " 2079 << printMBBReference(*CodeBB) << "\n"); 2080 for (auto SI : Sources) { 2081 unsigned DestReg; 2082 PHIInfo.findDest(SI, CodeBB, DestReg); 2083 insertChainedPHI(IfBB, CodeBB, MergeBB, InnerRegion, DestReg, SI); 2084 } 2085 LLVM_DEBUG(dbgs() << "Insertion done.\n"); 2086 } 2087 2088 LLVM_DEBUG(PHIInfo.dump(MRI)); 2089 } 2090 2091 void AMDGPUMachineCFGStructurizer::prunePHIInfo(MachineBasicBlock *MBB) { 2092 LLVM_DEBUG(dbgs() << "Before PHI Prune\n"); 2093 LLVM_DEBUG(PHIInfo.dump(MRI)); 2094 SmallVector<std::tuple<unsigned, unsigned, MachineBasicBlock *>, 4> 2095 ElimiatedSources; 2096 for (auto DRI = PHIInfo.dests_begin(), DE = PHIInfo.dests_end(); DRI != DE; 2097 ++DRI) { 2098 2099 unsigned DestReg = *DRI; 2100 auto SE = PHIInfo.sources_end(DestReg); 2101 2102 bool MBBContainsPHISource = false; 2103 // Check if there is a PHI source in this MBB 2104 for (auto SRI = PHIInfo.sources_begin(DestReg); SRI != SE; ++SRI) { 2105 unsigned SourceReg = (*SRI).first; 2106 MachineOperand *Def = &(*(MRI->def_begin(SourceReg))); 2107 if (Def->getParent()->getParent() == MBB) { 2108 MBBContainsPHISource = true; 2109 } 2110 } 2111 2112 // If so, all other sources are useless since we know this block 2113 // is always executed when the region is executed. 2114 if (MBBContainsPHISource) { 2115 for (auto SRI = PHIInfo.sources_begin(DestReg); SRI != SE; ++SRI) { 2116 PHILinearize::PHISourceT Source = *SRI; 2117 unsigned SourceReg = Source.first; 2118 MachineBasicBlock *SourceMBB = Source.second; 2119 MachineOperand *Def = &(*(MRI->def_begin(SourceReg))); 2120 if (Def->getParent()->getParent() != MBB) { 2121 ElimiatedSources.push_back( 2122 std::make_tuple(DestReg, SourceReg, SourceMBB)); 2123 } 2124 } 2125 } 2126 } 2127 2128 // Remove the PHI sources that are in the given MBB 2129 for (auto &SourceInfo : ElimiatedSources) { 2130 PHIInfo.removeSource(std::get<0>(SourceInfo), std::get<1>(SourceInfo), 2131 std::get<2>(SourceInfo)); 2132 } 2133 LLVM_DEBUG(dbgs() << "After PHI Prune\n"); 2134 LLVM_DEBUG(PHIInfo.dump(MRI)); 2135 } 2136 2137 void AMDGPUMachineCFGStructurizer::createEntryPHI(LinearizedRegion *CurrentRegion, 2138 unsigned DestReg) { 2139 MachineBasicBlock *Entry = CurrentRegion->getEntry(); 2140 MachineBasicBlock *Exit = CurrentRegion->getExit(); 2141 2142 LLVM_DEBUG(dbgs() << "RegionExit: " << Exit->getNumber() << " Pred: " 2143 << (*(Entry->pred_begin()))->getNumber() << "\n"); 2144 2145 int NumSources = 0; 2146 auto SE = PHIInfo.sources_end(DestReg); 2147 2148 for (auto SRI = PHIInfo.sources_begin(DestReg); SRI != SE; ++SRI) { 2149 NumSources++; 2150 } 2151 2152 if (NumSources == 1) { 2153 auto SRI = PHIInfo.sources_begin(DestReg); 2154 unsigned SourceReg = (*SRI).first; 2155 replaceRegisterWith(DestReg, SourceReg); 2156 } else { 2157 const DebugLoc &DL = Entry->findDebugLoc(Entry->begin()); 2158 MachineInstrBuilder MIB = BuildMI(*Entry, Entry->instr_begin(), DL, 2159 TII->get(TargetOpcode::PHI), DestReg); 2160 LLVM_DEBUG(dbgs() << "Entry PHI " << printReg(DestReg, TRI) << " = PHI("); 2161 2162 unsigned CurrentBackedgeReg = 0; 2163 2164 for (auto SRI = PHIInfo.sources_begin(DestReg); SRI != SE; ++SRI) { 2165 unsigned SourceReg = (*SRI).first; 2166 2167 if (CurrentRegion->contains((*SRI).second)) { 2168 if (CurrentBackedgeReg == 0) { 2169 CurrentBackedgeReg = SourceReg; 2170 } else { 2171 MachineInstr *PHIDefInstr = getDefInstr(SourceReg); 2172 MachineBasicBlock *PHIDefMBB = PHIDefInstr->getParent(); 2173 const TargetRegisterClass *RegClass = 2174 MRI->getRegClass(CurrentBackedgeReg); 2175 unsigned NewBackedgeReg = MRI->createVirtualRegister(RegClass); 2176 MachineInstrBuilder BackedgePHI = 2177 BuildMI(*PHIDefMBB, PHIDefMBB->instr_begin(), DL, 2178 TII->get(TargetOpcode::PHI), NewBackedgeReg); 2179 BackedgePHI.addReg(CurrentBackedgeReg); 2180 BackedgePHI.addMBB(getPHIPred(*PHIDefInstr, 0)); 2181 BackedgePHI.addReg(getPHISourceReg(*PHIDefInstr, 1)); 2182 BackedgePHI.addMBB((*SRI).second); 2183 CurrentBackedgeReg = NewBackedgeReg; 2184 LLVM_DEBUG(dbgs() 2185 << "Inserting backedge PHI: " 2186 << printReg(NewBackedgeReg, TRI) << " = PHI(" 2187 << printReg(CurrentBackedgeReg, TRI) << ", " 2188 << printMBBReference(*getPHIPred(*PHIDefInstr, 0)) << ", " 2189 << printReg(getPHISourceReg(*PHIDefInstr, 1), TRI) << ", " 2190 << printMBBReference(*(*SRI).second)); 2191 } 2192 } else { 2193 MIB.addReg(SourceReg); 2194 MIB.addMBB((*SRI).second); 2195 LLVM_DEBUG(dbgs() << printReg(SourceReg, TRI) << ", " 2196 << printMBBReference(*(*SRI).second) << ", "); 2197 } 2198 } 2199 2200 // Add the final backedge register source to the entry phi 2201 if (CurrentBackedgeReg != 0) { 2202 MIB.addReg(CurrentBackedgeReg); 2203 MIB.addMBB(Exit); 2204 LLVM_DEBUG(dbgs() << printReg(CurrentBackedgeReg, TRI) << ", " 2205 << printMBBReference(*Exit) << ")\n"); 2206 } else { 2207 LLVM_DEBUG(dbgs() << ")\n"); 2208 } 2209 } 2210 } 2211 2212 void AMDGPUMachineCFGStructurizer::createEntryPHIs(LinearizedRegion *CurrentRegion) { 2213 LLVM_DEBUG(PHIInfo.dump(MRI)); 2214 2215 for (auto DRI = PHIInfo.dests_begin(), DE = PHIInfo.dests_end(); DRI != DE; 2216 ++DRI) { 2217 2218 unsigned DestReg = *DRI; 2219 createEntryPHI(CurrentRegion, DestReg); 2220 } 2221 PHIInfo.clear(); 2222 } 2223 2224 void AMDGPUMachineCFGStructurizer::replaceRegisterWith(unsigned Register, 2225 unsigned NewRegister) { 2226 assert(Register != NewRegister && "Cannot replace a reg with itself"); 2227 2228 for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(Register), 2229 E = MRI->reg_end(); 2230 I != E;) { 2231 MachineOperand &O = *I; 2232 ++I; 2233 if (TargetRegisterInfo::isPhysicalRegister(NewRegister)) { 2234 LLVM_DEBUG(dbgs() << "Trying to substitute physical register: " 2235 << printReg(NewRegister, MRI->getTargetRegisterInfo()) 2236 << "\n"); 2237 llvm_unreachable("Cannot substitute physical registers"); 2238 // We don't handle physical registers, but if we need to 2239 // in the future This is how we do it: 2240 // O.substPhysReg(NewRegister, *TRI); 2241 } else { 2242 LLVM_DEBUG(dbgs() << "Replacing register: " 2243 << printReg(Register, MRI->getTargetRegisterInfo()) 2244 << " with " 2245 << printReg(NewRegister, MRI->getTargetRegisterInfo()) 2246 << "\n"); 2247 O.setReg(NewRegister); 2248 } 2249 } 2250 PHIInfo.deleteDef(Register); 2251 2252 getRegionMRT()->replaceLiveOutReg(Register, NewRegister); 2253 2254 LLVM_DEBUG(PHIInfo.dump(MRI)); 2255 } 2256 2257 void AMDGPUMachineCFGStructurizer::resolvePHIInfos(MachineBasicBlock *FunctionEntry) { 2258 LLVM_DEBUG(dbgs() << "Resolve PHI Infos\n"); 2259 LLVM_DEBUG(PHIInfo.dump(MRI)); 2260 for (auto DRI = PHIInfo.dests_begin(), DE = PHIInfo.dests_end(); DRI != DE; 2261 ++DRI) { 2262 unsigned DestReg = *DRI; 2263 LLVM_DEBUG(dbgs() << "DestReg: " << printReg(DestReg, TRI) << "\n"); 2264 auto SRI = PHIInfo.sources_begin(DestReg); 2265 unsigned SourceReg = (*SRI).first; 2266 LLVM_DEBUG(dbgs() << "DestReg: " << printReg(DestReg, TRI) 2267 << " SourceReg: " << printReg(SourceReg, TRI) << "\n"); 2268 2269 assert(PHIInfo.sources_end(DestReg) == ++SRI && 2270 "More than one phi source in entry node"); 2271 replaceRegisterWith(DestReg, SourceReg); 2272 } 2273 } 2274 2275 static bool isFunctionEntryBlock(MachineBasicBlock *MBB) { 2276 return ((&(*(MBB->getParent()->begin()))) == MBB); 2277 } 2278 2279 MachineBasicBlock *AMDGPUMachineCFGStructurizer::createIfRegion( 2280 MachineBasicBlock *MergeBB, MachineBasicBlock *CodeBB, 2281 LinearizedRegion *CurrentRegion, unsigned BBSelectRegIn, 2282 unsigned BBSelectRegOut) { 2283 if (isFunctionEntryBlock(CodeBB) && !CurrentRegion->getHasLoop()) { 2284 // Handle non-loop function entry block. 2285 // We need to allow loops to the entry block and then 2286 rewriteCodeBBTerminator(CodeBB, MergeBB, BBSelectRegOut); 2287 resolvePHIInfos(CodeBB); 2288 removeExternalCFGSuccessors(CodeBB); 2289 CodeBB->addSuccessor(MergeBB); 2290 CurrentRegion->addMBB(CodeBB); 2291 return nullptr; 2292 } 2293 if (CurrentRegion->getEntry() == CodeBB && !CurrentRegion->getHasLoop()) { 2294 // Handle non-loop region entry block. 2295 MachineFunction *MF = MergeBB->getParent(); 2296 auto MergeIter = MergeBB->getIterator(); 2297 auto CodeBBStartIter = CodeBB->getIterator(); 2298 auto CodeBBEndIter = ++(CodeBB->getIterator()); 2299 if (CodeBBEndIter != MergeIter) { 2300 MF->splice(MergeIter, CodeBBStartIter, CodeBBEndIter); 2301 } 2302 rewriteCodeBBTerminator(CodeBB, MergeBB, BBSelectRegOut); 2303 prunePHIInfo(CodeBB); 2304 createEntryPHIs(CurrentRegion); 2305 removeExternalCFGSuccessors(CodeBB); 2306 CodeBB->addSuccessor(MergeBB); 2307 CurrentRegion->addMBB(CodeBB); 2308 return nullptr; 2309 } else { 2310 // Handle internal block. 2311 const TargetRegisterClass *RegClass = MRI->getRegClass(BBSelectRegIn); 2312 unsigned CodeBBSelectReg = MRI->createVirtualRegister(RegClass); 2313 rewriteCodeBBTerminator(CodeBB, MergeBB, CodeBBSelectReg); 2314 bool IsRegionEntryBB = CurrentRegion->getEntry() == CodeBB; 2315 MachineBasicBlock *IfBB = createIfBlock(MergeBB, CodeBB, CodeBB, CodeBB, 2316 BBSelectRegIn, IsRegionEntryBB); 2317 CurrentRegion->addMBB(IfBB); 2318 // If this is the entry block we need to make the If block the new 2319 // linearized region entry. 2320 if (IsRegionEntryBB) { 2321 CurrentRegion->setEntry(IfBB); 2322 2323 if (CurrentRegion->getHasLoop()) { 2324 MachineBasicBlock *RegionExit = CurrentRegion->getExit(); 2325 MachineBasicBlock *ETrueBB = nullptr; 2326 MachineBasicBlock *EFalseBB = nullptr; 2327 SmallVector<MachineOperand, 1> ECond; 2328 2329 const DebugLoc &DL = DebugLoc(); 2330 TII->analyzeBranch(*RegionExit, ETrueBB, EFalseBB, ECond); 2331 TII->removeBranch(*RegionExit); 2332 2333 // We need to create a backedge if there is a loop 2334 unsigned Reg = TII->insertNE( 2335 RegionExit, RegionExit->instr_end(), DL, 2336 CurrentRegion->getRegionMRT()->getInnerOutputRegister(), 2337 CurrentRegion->getRegionMRT()->getEntry()->getNumber()); 2338 MachineOperand RegOp = 2339 MachineOperand::CreateReg(Reg, false, false, true); 2340 ArrayRef<MachineOperand> Cond(RegOp); 2341 LLVM_DEBUG(dbgs() << "RegionExitReg: "); 2342 LLVM_DEBUG(Cond[0].print(dbgs(), TRI)); 2343 LLVM_DEBUG(dbgs() << "\n"); 2344 TII->insertBranch(*RegionExit, CurrentRegion->getEntry(), RegionExit, 2345 Cond, DebugLoc()); 2346 RegionExit->addSuccessor(CurrentRegion->getEntry()); 2347 } 2348 } 2349 CurrentRegion->addMBB(CodeBB); 2350 LinearizedRegion InnerRegion(CodeBB, MRI, TRI, PHIInfo); 2351 2352 InnerRegion.setParent(CurrentRegion); 2353 LLVM_DEBUG(dbgs() << "Insert BB Select PHI (BB)\n"); 2354 insertMergePHI(IfBB, CodeBB, MergeBB, BBSelectRegOut, BBSelectRegIn, 2355 CodeBBSelectReg); 2356 InnerRegion.addMBB(MergeBB); 2357 2358 LLVM_DEBUG(InnerRegion.print(dbgs(), TRI)); 2359 rewriteLiveOutRegs(IfBB, CodeBB, MergeBB, &InnerRegion, CurrentRegion); 2360 extractKilledPHIs(CodeBB); 2361 if (IsRegionEntryBB) { 2362 createEntryPHIs(CurrentRegion); 2363 } 2364 return IfBB; 2365 } 2366 } 2367 2368 MachineBasicBlock *AMDGPUMachineCFGStructurizer::createIfRegion( 2369 MachineBasicBlock *MergeBB, LinearizedRegion *InnerRegion, 2370 LinearizedRegion *CurrentRegion, MachineBasicBlock *SelectBB, 2371 unsigned BBSelectRegIn, unsigned BBSelectRegOut) { 2372 unsigned CodeBBSelectReg = 2373 InnerRegion->getRegionMRT()->getInnerOutputRegister(); 2374 MachineBasicBlock *CodeEntryBB = InnerRegion->getEntry(); 2375 MachineBasicBlock *CodeExitBB = InnerRegion->getExit(); 2376 MachineBasicBlock *IfBB = createIfBlock(MergeBB, CodeEntryBB, CodeExitBB, 2377 SelectBB, BBSelectRegIn, true); 2378 CurrentRegion->addMBB(IfBB); 2379 bool isEntry = CurrentRegion->getEntry() == InnerRegion->getEntry(); 2380 if (isEntry) { 2381 2382 if (CurrentRegion->getHasLoop()) { 2383 MachineBasicBlock *RegionExit = CurrentRegion->getExit(); 2384 MachineBasicBlock *ETrueBB = nullptr; 2385 MachineBasicBlock *EFalseBB = nullptr; 2386 SmallVector<MachineOperand, 1> ECond; 2387 2388 const DebugLoc &DL = DebugLoc(); 2389 TII->analyzeBranch(*RegionExit, ETrueBB, EFalseBB, ECond); 2390 TII->removeBranch(*RegionExit); 2391 2392 // We need to create a backedge if there is a loop 2393 unsigned Reg = 2394 TII->insertNE(RegionExit, RegionExit->instr_end(), DL, 2395 CurrentRegion->getRegionMRT()->getInnerOutputRegister(), 2396 CurrentRegion->getRegionMRT()->getEntry()->getNumber()); 2397 MachineOperand RegOp = MachineOperand::CreateReg(Reg, false, false, true); 2398 ArrayRef<MachineOperand> Cond(RegOp); 2399 LLVM_DEBUG(dbgs() << "RegionExitReg: "); 2400 LLVM_DEBUG(Cond[0].print(dbgs(), TRI)); 2401 LLVM_DEBUG(dbgs() << "\n"); 2402 TII->insertBranch(*RegionExit, CurrentRegion->getEntry(), RegionExit, 2403 Cond, DebugLoc()); 2404 RegionExit->addSuccessor(IfBB); 2405 } 2406 } 2407 CurrentRegion->addMBBs(InnerRegion); 2408 LLVM_DEBUG(dbgs() << "Insert BB Select PHI (region)\n"); 2409 insertMergePHI(IfBB, CodeExitBB, MergeBB, BBSelectRegOut, BBSelectRegIn, 2410 CodeBBSelectReg); 2411 2412 rewriteLiveOutRegs(IfBB, /* CodeEntryBB */ CodeExitBB, MergeBB, InnerRegion, 2413 CurrentRegion); 2414 2415 rewriteRegionEntryPHIs(InnerRegion, IfBB); 2416 2417 if (isEntry) { 2418 CurrentRegion->setEntry(IfBB); 2419 } 2420 2421 if (isEntry) { 2422 createEntryPHIs(CurrentRegion); 2423 } 2424 2425 return IfBB; 2426 } 2427 2428 void AMDGPUMachineCFGStructurizer::splitLoopPHI(MachineInstr &PHI, 2429 MachineBasicBlock *Entry, 2430 MachineBasicBlock *EntrySucc, 2431 LinearizedRegion *LRegion) { 2432 SmallVector<unsigned, 2> PHIRegionIndices; 2433 getPHIRegionIndices(LRegion, PHI, PHIRegionIndices); 2434 2435 assert(PHIRegionIndices.size() == 1); 2436 2437 unsigned RegionIndex = PHIRegionIndices[0]; 2438 unsigned RegionSourceReg = getPHISourceReg(PHI, RegionIndex); 2439 MachineBasicBlock *RegionSourceMBB = getPHIPred(PHI, RegionIndex); 2440 unsigned PHIDest = getPHIDestReg(PHI); 2441 unsigned PHISource = PHIDest; 2442 unsigned ReplaceReg; 2443 2444 if (shrinkPHI(PHI, PHIRegionIndices, &ReplaceReg)) { 2445 PHISource = ReplaceReg; 2446 } 2447 2448 const TargetRegisterClass *RegClass = MRI->getRegClass(PHIDest); 2449 unsigned NewDestReg = MRI->createVirtualRegister(RegClass); 2450 LRegion->replaceRegisterInsideRegion(PHIDest, NewDestReg, false, MRI); 2451 MachineInstrBuilder MIB = 2452 BuildMI(*EntrySucc, EntrySucc->instr_begin(), PHI.getDebugLoc(), 2453 TII->get(TargetOpcode::PHI), NewDestReg); 2454 LLVM_DEBUG(dbgs() << "Split Entry PHI " << printReg(NewDestReg, TRI) 2455 << " = PHI("); 2456 MIB.addReg(PHISource); 2457 MIB.addMBB(Entry); 2458 LLVM_DEBUG(dbgs() << printReg(PHISource, TRI) << ", " 2459 << printMBBReference(*Entry)); 2460 MIB.addReg(RegionSourceReg); 2461 MIB.addMBB(RegionSourceMBB); 2462 LLVM_DEBUG(dbgs() << " ," << printReg(RegionSourceReg, TRI) << ", " 2463 << printMBBReference(*RegionSourceMBB) << ")\n"); 2464 } 2465 2466 void AMDGPUMachineCFGStructurizer::splitLoopPHIs(MachineBasicBlock *Entry, 2467 MachineBasicBlock *EntrySucc, 2468 LinearizedRegion *LRegion) { 2469 SmallVector<MachineInstr *, 2> PHIs; 2470 collectPHIs(Entry, PHIs); 2471 2472 for (auto PHII : PHIs) { 2473 splitLoopPHI(*PHII, Entry, EntrySucc, LRegion); 2474 } 2475 } 2476 2477 // Split the exit block so that we can insert a end control flow 2478 MachineBasicBlock * 2479 AMDGPUMachineCFGStructurizer::splitExit(LinearizedRegion *LRegion) { 2480 auto MRTRegion = LRegion->getRegionMRT(); 2481 auto Exit = LRegion->getExit(); 2482 auto MF = Exit->getParent(); 2483 auto Succ = MRTRegion->getSucc(); 2484 2485 auto NewExit = MF->CreateMachineBasicBlock(); 2486 auto AfterExitIter = Exit->getIterator(); 2487 AfterExitIter++; 2488 MF->insert(AfterExitIter, NewExit); 2489 Exit->removeSuccessor(Succ); 2490 Exit->addSuccessor(NewExit); 2491 NewExit->addSuccessor(Succ); 2492 insertUnconditionalBranch(NewExit, Succ); 2493 LRegion->addMBB(NewExit); 2494 LRegion->setExit(NewExit); 2495 2496 LLVM_DEBUG(dbgs() << "Created new exit block: " << NewExit->getNumber() 2497 << "\n"); 2498 2499 // Replace any PHI Predecessors in the successor with NewExit 2500 for (auto &II : *Succ) { 2501 MachineInstr &Instr = II; 2502 2503 // If we are past the PHI instructions we are done 2504 if (!Instr.isPHI()) 2505 break; 2506 2507 int numPreds = getPHINumInputs(Instr); 2508 for (int i = 0; i < numPreds; ++i) { 2509 auto Pred = getPHIPred(Instr, i); 2510 if (Pred == Exit) { 2511 setPhiPred(Instr, i, NewExit); 2512 } 2513 } 2514 } 2515 2516 return NewExit; 2517 } 2518 2519 static MachineBasicBlock *split(MachineBasicBlock::iterator I) { 2520 // Create the fall-through block. 2521 MachineBasicBlock *MBB = (*I).getParent(); 2522 MachineFunction *MF = MBB->getParent(); 2523 MachineBasicBlock *SuccMBB = MF->CreateMachineBasicBlock(); 2524 auto MBBIter = ++(MBB->getIterator()); 2525 MF->insert(MBBIter, SuccMBB); 2526 SuccMBB->transferSuccessorsAndUpdatePHIs(MBB); 2527 MBB->addSuccessor(SuccMBB); 2528 2529 // Splice the code over. 2530 SuccMBB->splice(SuccMBB->end(), MBB, I, MBB->end()); 2531 2532 return SuccMBB; 2533 } 2534 2535 // Split the entry block separating PHI-nodes and the rest of the code 2536 // This is needed to insert an initializer for the bb select register 2537 // inloop regions. 2538 2539 MachineBasicBlock * 2540 AMDGPUMachineCFGStructurizer::splitEntry(LinearizedRegion *LRegion) { 2541 MachineBasicBlock *Entry = LRegion->getEntry(); 2542 MachineBasicBlock *EntrySucc = split(Entry->getFirstNonPHI()); 2543 MachineBasicBlock *Exit = LRegion->getExit(); 2544 2545 LLVM_DEBUG(dbgs() << "Split " << printMBBReference(*Entry) << " to " 2546 << printMBBReference(*Entry) << " -> " 2547 << printMBBReference(*EntrySucc) << "\n"); 2548 LRegion->addMBB(EntrySucc); 2549 2550 // Make the backedge go to Entry Succ 2551 if (Exit->isSuccessor(Entry)) { 2552 Exit->removeSuccessor(Entry); 2553 } 2554 Exit->addSuccessor(EntrySucc); 2555 MachineInstr &Branch = *(Exit->instr_rbegin()); 2556 for (auto &UI : Branch.uses()) { 2557 if (UI.isMBB() && UI.getMBB() == Entry) { 2558 UI.setMBB(EntrySucc); 2559 } 2560 } 2561 2562 splitLoopPHIs(Entry, EntrySucc, LRegion); 2563 2564 return EntrySucc; 2565 } 2566 2567 LinearizedRegion * 2568 AMDGPUMachineCFGStructurizer::initLinearizedRegion(RegionMRT *Region) { 2569 LinearizedRegion *LRegion = Region->getLinearizedRegion(); 2570 LRegion->initLiveOut(Region, MRI, TRI, PHIInfo); 2571 LRegion->setEntry(Region->getEntry()); 2572 return LRegion; 2573 } 2574 2575 static void removeOldExitPreds(RegionMRT *Region) { 2576 MachineBasicBlock *Exit = Region->getSucc(); 2577 if (Exit == nullptr) { 2578 return; 2579 } 2580 for (MachineBasicBlock::pred_iterator PI = Exit->pred_begin(), 2581 E = Exit->pred_end(); 2582 PI != E; ++PI) { 2583 if (Region->contains(*PI)) { 2584 (*PI)->removeSuccessor(Exit); 2585 } 2586 } 2587 } 2588 2589 static bool mbbHasBackEdge(MachineBasicBlock *MBB, 2590 SmallPtrSet<MachineBasicBlock *, 8> &MBBs) { 2591 for (auto SI = MBB->succ_begin(), SE = MBB->succ_end(); SI != SE; ++SI) { 2592 if (MBBs.count(*SI) != 0) { 2593 return true; 2594 } 2595 } 2596 return false; 2597 } 2598 2599 static bool containsNewBackedge(MRT *Tree, 2600 SmallPtrSet<MachineBasicBlock *, 8> &MBBs) { 2601 // Need to traverse this in reverse since it is in post order. 2602 if (Tree == nullptr) 2603 return false; 2604 2605 if (Tree->isMBB()) { 2606 MachineBasicBlock *MBB = Tree->getMBBMRT()->getMBB(); 2607 MBBs.insert(MBB); 2608 if (mbbHasBackEdge(MBB, MBBs)) { 2609 return true; 2610 } 2611 } else { 2612 RegionMRT *Region = Tree->getRegionMRT(); 2613 SetVector<MRT *> *Children = Region->getChildren(); 2614 for (auto CI = Children->rbegin(), CE = Children->rend(); CI != CE; ++CI) { 2615 if (containsNewBackedge(*CI, MBBs)) 2616 return true; 2617 } 2618 } 2619 return false; 2620 } 2621 2622 static bool containsNewBackedge(RegionMRT *Region) { 2623 SmallPtrSet<MachineBasicBlock *, 8> MBBs; 2624 return containsNewBackedge(Region, MBBs); 2625 } 2626 2627 bool AMDGPUMachineCFGStructurizer::structurizeComplexRegion(RegionMRT *Region) { 2628 auto *LRegion = initLinearizedRegion(Region); 2629 LRegion->setHasLoop(containsNewBackedge(Region)); 2630 MachineBasicBlock *LastMerge = createLinearizedExitBlock(Region); 2631 MachineBasicBlock *CurrentMerge = LastMerge; 2632 LRegion->addMBB(LastMerge); 2633 LRegion->setExit(LastMerge); 2634 2635 rewriteRegionExitPHIs(Region, LastMerge, LRegion); 2636 removeOldExitPreds(Region); 2637 2638 LLVM_DEBUG(PHIInfo.dump(MRI)); 2639 2640 SetVector<MRT *> *Children = Region->getChildren(); 2641 LLVM_DEBUG(dbgs() << "===========If Region Start===============\n"); 2642 if (LRegion->getHasLoop()) { 2643 LLVM_DEBUG(dbgs() << "Has Backedge: Yes\n"); 2644 } else { 2645 LLVM_DEBUG(dbgs() << "Has Backedge: No\n"); 2646 } 2647 2648 unsigned BBSelectRegIn; 2649 unsigned BBSelectRegOut; 2650 for (auto CI = Children->begin(), CE = Children->end(); CI != CE; ++CI) { 2651 LLVM_DEBUG(dbgs() << "CurrentRegion: \n"); 2652 LLVM_DEBUG(LRegion->print(dbgs(), TRI)); 2653 2654 auto CNI = CI; 2655 ++CNI; 2656 2657 MRT *Child = (*CI); 2658 2659 if (Child->isRegion()) { 2660 2661 LinearizedRegion *InnerLRegion = 2662 Child->getRegionMRT()->getLinearizedRegion(); 2663 // We found the block is the exit of an inner region, we need 2664 // to put it in the current linearized region. 2665 2666 LLVM_DEBUG(dbgs() << "Linearizing region: "); 2667 LLVM_DEBUG(InnerLRegion->print(dbgs(), TRI)); 2668 LLVM_DEBUG(dbgs() << "\n"); 2669 2670 MachineBasicBlock *InnerEntry = InnerLRegion->getEntry(); 2671 if ((&(*(InnerEntry->getParent()->begin()))) == InnerEntry) { 2672 // Entry has already been linearized, no need to do this region. 2673 unsigned OuterSelect = InnerLRegion->getBBSelectRegOut(); 2674 unsigned InnerSelectReg = 2675 InnerLRegion->getRegionMRT()->getInnerOutputRegister(); 2676 replaceRegisterWith(InnerSelectReg, OuterSelect), 2677 resolvePHIInfos(InnerEntry); 2678 if (!InnerLRegion->getExit()->isSuccessor(CurrentMerge)) 2679 InnerLRegion->getExit()->addSuccessor(CurrentMerge); 2680 continue; 2681 } 2682 2683 BBSelectRegOut = Child->getBBSelectRegOut(); 2684 BBSelectRegIn = Child->getBBSelectRegIn(); 2685 2686 LLVM_DEBUG(dbgs() << "BBSelectRegIn: " << printReg(BBSelectRegIn, TRI) 2687 << "\n"); 2688 LLVM_DEBUG(dbgs() << "BBSelectRegOut: " << printReg(BBSelectRegOut, TRI) 2689 << "\n"); 2690 2691 MachineBasicBlock *IfEnd = CurrentMerge; 2692 CurrentMerge = createIfRegion(CurrentMerge, InnerLRegion, LRegion, 2693 Child->getRegionMRT()->getEntry(), 2694 BBSelectRegIn, BBSelectRegOut); 2695 TII->convertNonUniformIfRegion(CurrentMerge, IfEnd); 2696 } else { 2697 MachineBasicBlock *MBB = Child->getMBBMRT()->getMBB(); 2698 LLVM_DEBUG(dbgs() << "Linearizing block: " << MBB->getNumber() << "\n"); 2699 2700 if (MBB == getSingleExitNode(*(MBB->getParent()))) { 2701 // If this is the exit block then we need to skip to the next. 2702 // The "in" register will be transferred to "out" in the next 2703 // iteration. 2704 continue; 2705 } 2706 2707 BBSelectRegOut = Child->getBBSelectRegOut(); 2708 BBSelectRegIn = Child->getBBSelectRegIn(); 2709 2710 LLVM_DEBUG(dbgs() << "BBSelectRegIn: " << printReg(BBSelectRegIn, TRI) 2711 << "\n"); 2712 LLVM_DEBUG(dbgs() << "BBSelectRegOut: " << printReg(BBSelectRegOut, TRI) 2713 << "\n"); 2714 2715 MachineBasicBlock *IfEnd = CurrentMerge; 2716 // This is a basic block that is not part of an inner region, we 2717 // need to put it in the current linearized region. 2718 CurrentMerge = createIfRegion(CurrentMerge, MBB, LRegion, BBSelectRegIn, 2719 BBSelectRegOut); 2720 if (CurrentMerge) { 2721 TII->convertNonUniformIfRegion(CurrentMerge, IfEnd); 2722 } 2723 2724 LLVM_DEBUG(PHIInfo.dump(MRI)); 2725 } 2726 } 2727 2728 LRegion->removeFalseRegisterKills(MRI); 2729 2730 if (LRegion->getHasLoop()) { 2731 MachineBasicBlock *NewSucc = splitEntry(LRegion); 2732 if (isFunctionEntryBlock(LRegion->getEntry())) { 2733 resolvePHIInfos(LRegion->getEntry()); 2734 } 2735 const DebugLoc &DL = NewSucc->findDebugLoc(NewSucc->getFirstNonPHI()); 2736 unsigned InReg = LRegion->getBBSelectRegIn(); 2737 unsigned InnerSelectReg = 2738 MRI->createVirtualRegister(MRI->getRegClass(InReg)); 2739 unsigned NewInReg = MRI->createVirtualRegister(MRI->getRegClass(InReg)); 2740 TII->materializeImmediate(*(LRegion->getEntry()), 2741 LRegion->getEntry()->getFirstTerminator(), DL, 2742 NewInReg, Region->getEntry()->getNumber()); 2743 // Need to be careful about updating the registers inside the region. 2744 LRegion->replaceRegisterInsideRegion(InReg, InnerSelectReg, false, MRI); 2745 LLVM_DEBUG(dbgs() << "Loop BBSelect Merge PHI:\n"); 2746 insertMergePHI(LRegion->getEntry(), LRegion->getExit(), NewSucc, 2747 InnerSelectReg, NewInReg, 2748 LRegion->getRegionMRT()->getInnerOutputRegister()); 2749 splitExit(LRegion); 2750 TII->convertNonUniformLoopRegion(NewSucc, LastMerge); 2751 } 2752 2753 if (Region->isRoot()) { 2754 TII->insertReturn(*LastMerge); 2755 } 2756 2757 LLVM_DEBUG(Region->getEntry()->getParent()->dump()); 2758 LLVM_DEBUG(LRegion->print(dbgs(), TRI)); 2759 LLVM_DEBUG(PHIInfo.dump(MRI)); 2760 2761 LLVM_DEBUG(dbgs() << "===========If Region End===============\n"); 2762 2763 Region->setLinearizedRegion(LRegion); 2764 return true; 2765 } 2766 2767 bool AMDGPUMachineCFGStructurizer::structurizeRegion(RegionMRT *Region) { 2768 if (false && regionIsSimpleIf(Region)) { 2769 transformSimpleIfRegion(Region); 2770 return true; 2771 } else if (regionIsSequence(Region)) { 2772 fixupRegionExits(Region); 2773 return false; 2774 } else { 2775 structurizeComplexRegion(Region); 2776 } 2777 return false; 2778 } 2779 2780 static int structurize_once = 0; 2781 2782 bool AMDGPUMachineCFGStructurizer::structurizeRegions(RegionMRT *Region, 2783 bool isTopRegion) { 2784 bool Changed = false; 2785 2786 auto Children = Region->getChildren(); 2787 for (auto CI : *Children) { 2788 if (CI->isRegion()) { 2789 Changed |= structurizeRegions(CI->getRegionMRT(), false); 2790 } 2791 } 2792 2793 if (structurize_once < 2 || true) { 2794 Changed |= structurizeRegion(Region); 2795 structurize_once++; 2796 } 2797 return Changed; 2798 } 2799 2800 void AMDGPUMachineCFGStructurizer::initFallthroughMap(MachineFunction &MF) { 2801 LLVM_DEBUG(dbgs() << "Fallthrough Map:\n"); 2802 for (auto &MBBI : MF) { 2803 MachineBasicBlock *MBB = MBBI.getFallThrough(); 2804 if (MBB != nullptr) { 2805 LLVM_DEBUG(dbgs() << "Fallthrough: " << MBBI.getNumber() << " -> " 2806 << MBB->getNumber() << "\n"); 2807 } 2808 FallthroughMap[&MBBI] = MBB; 2809 } 2810 } 2811 2812 void AMDGPUMachineCFGStructurizer::createLinearizedRegion(RegionMRT *Region, 2813 unsigned SelectOut) { 2814 LinearizedRegion *LRegion = new LinearizedRegion(); 2815 if (SelectOut) { 2816 LRegion->addLiveOut(SelectOut); 2817 LLVM_DEBUG(dbgs() << "Add LiveOut (BBSelect): " << printReg(SelectOut, TRI) 2818 << "\n"); 2819 } 2820 LRegion->setRegionMRT(Region); 2821 Region->setLinearizedRegion(LRegion); 2822 LRegion->setParent(Region->getParent() 2823 ? Region->getParent()->getLinearizedRegion() 2824 : nullptr); 2825 } 2826 2827 unsigned 2828 AMDGPUMachineCFGStructurizer::initializeSelectRegisters(MRT *MRT, unsigned SelectOut, 2829 MachineRegisterInfo *MRI, 2830 const SIInstrInfo *TII) { 2831 if (MRT->isRegion()) { 2832 RegionMRT *Region = MRT->getRegionMRT(); 2833 Region->setBBSelectRegOut(SelectOut); 2834 unsigned InnerSelectOut = createBBSelectReg(TII, MRI); 2835 2836 // Fixme: Move linearization creation to the original spot 2837 createLinearizedRegion(Region, SelectOut); 2838 2839 for (auto CI = Region->getChildren()->begin(), 2840 CE = Region->getChildren()->end(); 2841 CI != CE; ++CI) { 2842 InnerSelectOut = 2843 initializeSelectRegisters((*CI), InnerSelectOut, MRI, TII); 2844 } 2845 MRT->setBBSelectRegIn(InnerSelectOut); 2846 return InnerSelectOut; 2847 } else { 2848 MRT->setBBSelectRegOut(SelectOut); 2849 unsigned NewSelectIn = createBBSelectReg(TII, MRI); 2850 MRT->setBBSelectRegIn(NewSelectIn); 2851 return NewSelectIn; 2852 } 2853 } 2854 2855 static void checkRegOnlyPHIInputs(MachineFunction &MF) { 2856 for (auto &MBBI : MF) { 2857 for (MachineBasicBlock::instr_iterator I = MBBI.instr_begin(), 2858 E = MBBI.instr_end(); 2859 I != E; ++I) { 2860 MachineInstr &Instr = *I; 2861 if (Instr.isPHI()) { 2862 int numPreds = getPHINumInputs(Instr); 2863 for (int i = 0; i < numPreds; ++i) { 2864 assert(Instr.getOperand(i * 2 + 1).isReg() && 2865 "PHI Operand not a register"); 2866 } 2867 } 2868 } 2869 } 2870 } 2871 2872 bool AMDGPUMachineCFGStructurizer::runOnMachineFunction(MachineFunction &MF) { 2873 const GCNSubtarget &ST = MF.getSubtarget<GCNSubtarget>(); 2874 const SIInstrInfo *TII = ST.getInstrInfo(); 2875 TRI = ST.getRegisterInfo(); 2876 MRI = &(MF.getRegInfo()); 2877 initFallthroughMap(MF); 2878 2879 checkRegOnlyPHIInputs(MF); 2880 LLVM_DEBUG(dbgs() << "----STRUCTURIZER START----\n"); 2881 LLVM_DEBUG(MF.dump()); 2882 2883 Regions = &(getAnalysis<MachineRegionInfoPass>().getRegionInfo()); 2884 LLVM_DEBUG(Regions->dump()); 2885 2886 RegionMRT *RTree = MRT::buildMRT(MF, Regions, TII, MRI); 2887 setRegionMRT(RTree); 2888 initializeSelectRegisters(RTree, 0, MRI, TII); 2889 LLVM_DEBUG(RTree->dump(TRI)); 2890 bool result = structurizeRegions(RTree, true); 2891 delete RTree; 2892 LLVM_DEBUG(dbgs() << "----STRUCTURIZER END----\n"); 2893 initFallthroughMap(MF); 2894 return result; 2895 } 2896 2897 char AMDGPUMachineCFGStructurizerID = AMDGPUMachineCFGStructurizer::ID; 2898 2899 INITIALIZE_PASS_BEGIN(AMDGPUMachineCFGStructurizer, "amdgpu-machine-cfg-structurizer", 2900 "AMDGPU Machine CFG Structurizer", false, false) 2901 INITIALIZE_PASS_DEPENDENCY(MachineRegionInfoPass) 2902 INITIALIZE_PASS_END(AMDGPUMachineCFGStructurizer, "amdgpu-machine-cfg-structurizer", 2903 "AMDGPU Machine CFG Structurizer", false, false) 2904 2905 FunctionPass *llvm::createAMDGPUMachineCFGStructurizerPass() { 2906 return new AMDGPUMachineCFGStructurizer(); 2907 } 2908