R600MachineCFGStructurizer.cpp Source File (original) (raw)

23using namespace llvm;

25#define DEBUG_TYPE "structcfg"

37 STATISTIC(numSerialPatternMatch, "CFGStructurizer number of serial pattern "

38 "matched");

39 STATISTIC(numIfPatternMatch, "CFGStructurizer number of if pattern "

40 "matched");

41 STATISTIC(numClonedBlock, "CFGStructurizer cloned blocks");

42 STATISTIC(numClonedInstr, "CFGStructurizer cloned instructions");

44namespace {

52#define SHOWNEWINSTR(i) LLVM_DEBUG(dbgs() << "New instr: " << *i << "\n");

54#define SHOWNEWBLK(b, msg) \

55 LLVM_DEBUG(dbgs() << msg << "BB" << b->getNumber() << "size " << b->size(); \

56 dbgs() << "\n";);

58#define SHOWBLK_DETAIL(b, msg) \

59 LLVM_DEBUG(if (b) { \

60 dbgs() << msg << "BB" << b->getNumber() << "size " << b->size(); \

61 b->print(dbgs()); \

62 dbgs() << "\n"; \

63 });

65#define INVALIDSCCNUM -1

73class BlockInformation {

74public:

75 bool IsRetired = false;

78 BlockInformation() = default;

79};

88public:

89 using MBBVector = SmallVector<MachineBasicBlock *, 32>;

90 using MBBInfoMap = std::map<MachineBasicBlock *, BlockInformation *>;

91 using LoopLandInfoMap = std::map<MachineLoop *, MachineBasicBlock *>;

93 enum PathToKind {

94 Not_SinglePath = 0,

95 SinglePath_InPath = 1,

96 SinglePath_NotInPath = 2

97 };

99 static char ID;

100

101 R600MachineCFGStructurizer() : MachineFunctionPass(ID) {}

102

103 StringRef getPassName() const override {

104 return "AMDGPU Control Flow Graph structurizer Pass";

105 }

106

107 void getAnalysisUsage(AnalysisUsage &AU) const override {

108 AU.addRequired();

109 AU.addRequired();

110 AU.addRequired();

112 }

113

114

115 bool run();

116

117

118

119

121

122 bool runOnMachineFunction(MachineFunction &MF) override {

123

125

126 TII = MF.getSubtarget().getInstrInfo();

127 TRI = &TII->getRegisterInfo();

129 OrderedBlks.clear();

130 Visited.clear();

131 FuncRep = &MF;

132 MLI = &getAnalysis().getLI();

133 LLVM_DEBUG(dbgs() << "LoopInfo:\n"; PrintLoopinfo(*MLI););

134 MDT = &getAnalysis().getDomTree();

136 PDT = &getAnalysis().getPostDomTree();

141 return true;

142 }

143

144protected:

145 MachineDominatorTree *MDT;

146 MachinePostDominatorTree *PDT;

147 MachineLoopInfo *MLI;

148 const R600InstrInfo *TII = nullptr;

149 const R600RegisterInfo *TRI = nullptr;

150

151

152

153 void printOrderedBlocks() const {

154 size_t i = 0;

156 iterBlkEnd = OrderedBlks.end(); iterBlk != iterBlkEnd; ++iterBlk, ++i) {

157 dbgs() << "BB" << (*iterBlk)->getNumber();

158 dbgs() << "(" << getSCCNum(*iterBlk) << "," << (*iterBlk)->size() << ")";

159 if (i != 0 && i % 10 == 0) {

160 dbgs() << "\n";

161 } else {

162 dbgs() << " ";

163 }

164 }

165 }

166

167 static void PrintLoopinfo(const MachineLoopInfo &LoopInfo) {

168 for (const MachineLoop *L : LoopInfo)

169 L->print(dbgs());

170 }

171

172

173 int getSCCNum(MachineBasicBlock *MBB) const;

174 MachineBasicBlock *getLoopLandInfo(MachineLoop *LoopRep) const;

175 bool hasBackEdge(MachineBasicBlock *MBB) const;

176 bool isRetiredBlock(MachineBasicBlock *MBB) const;

177 bool isActiveLoophead(MachineBasicBlock *MBB) const;

178 PathToKind singlePathTo(MachineBasicBlock *SrcMBB, MachineBasicBlock *DstMBB,

179 bool AllowSideEntry = true) const;

182 bool needMigrateBlock(MachineBasicBlock *MBB) const;

183

184

186 MachineBasicBlock &MBB);

187

188 void orderBlocks(MachineFunction *MF);

189

190

191 void insertInstrEnd(MachineBasicBlock *MBB, int NewOpcode,

193 MachineInstr *insertInstrBefore(MachineBasicBlock *MBB, int NewOpcode,

198 void insertCondBranchBefore(MachineBasicBlock *MBB,

201

202 static int getBranchNzeroOpcode(int OldOpcode);

203 static int getBranchZeroOpcode(int OldOpcode);

204 static int getContinueNzeroOpcode(int OldOpcode);

205 static int getContinueZeroOpcode(int OldOpcode);

206 static MachineBasicBlock *getTrueBranch(MachineInstr *MI);

207 static void setTrueBranch(MachineInstr *MI, MachineBasicBlock *MBB);

208 static MachineBasicBlock *getFalseBranch(MachineBasicBlock *MBB,

209 MachineInstr *MI);

210 static bool isCondBranch(MachineInstr *MI);

211 static bool isUncondBranch(MachineInstr *MI);

212 static DebugLoc getLastDebugLocInBB(MachineBasicBlock *MBB);

213 static MachineInstr *getNormalBlockBranchInstr(MachineBasicBlock *MBB);

214

215

216

217

218

219 MachineInstr *getLoopendBlockBranchInstr(MachineBasicBlock *MBB);

220

221 static MachineInstr *getReturnInstr(MachineBasicBlock *MBB);

222 static bool isReturnBlock(MachineBasicBlock *MBB);

223 static void cloneSuccessorList(MachineBasicBlock *DstMBB,

224 MachineBasicBlock *SrcMBB);

225 static MachineBasicBlock *clone(MachineBasicBlock *MBB);

226

227

228

229

230 void replaceInstrUseOfBlockWith(MachineBasicBlock *SrcMBB,

231 MachineBasicBlock *OldMBB, MachineBasicBlock *NewBlk);

232

233 static void wrapup(MachineBasicBlock *MBB);

234

235 int patternMatch(MachineBasicBlock *MBB);

236 int patternMatchGroup(MachineBasicBlock *MBB);

237 int serialPatternMatch(MachineBasicBlock *MBB);

238 int ifPatternMatch(MachineBasicBlock *MBB);

239 int loopendPatternMatch();

240 int mergeLoop(MachineLoop *LoopRep);

241

242

243

244

245 bool isSameloopDetachedContbreak(MachineBasicBlock *Src1MBB,

246 MachineBasicBlock *Src2MBB);

247 int handleJumpintoIf(MachineBasicBlock *HeadMBB,

248 MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB);

249 int handleJumpintoIfImp(MachineBasicBlock *HeadMBB,

250 MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB);

251 int improveSimpleJumpintoIf(MachineBasicBlock *HeadMBB,

252 MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB,

253 MachineBasicBlock **LandMBBPtr);

254 void showImproveSimpleJumpintoIf(MachineBasicBlock *HeadMBB,

255 MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB,

256 MachineBasicBlock *LandMBB, bool Detail = false);

257 int cloneOnSideEntryTo(MachineBasicBlock *PreMBB,

258 MachineBasicBlock *SrcMBB, MachineBasicBlock *DstMBB);

259 void mergeSerialBlock(MachineBasicBlock *DstMBB,

260 MachineBasicBlock *SrcMBB);

261

262 void mergeIfthenelseBlock(MachineInstr *BranchMI,

263 MachineBasicBlock *MBB, MachineBasicBlock *TrueMBB,

264 MachineBasicBlock *FalseMBB, MachineBasicBlock *LandMBB);

265 void mergeLooplandBlock(MachineBasicBlock *DstMBB,

266 MachineBasicBlock *LandMBB);

267 void mergeLoopbreakBlock(MachineBasicBlock *ExitingMBB,

268 MachineBasicBlock *LandMBB);

269 void settleLoopcontBlock(MachineBasicBlock *ContingMBB,

270 MachineBasicBlock *ContMBB);

271

272

273

274

275

276

277

278

279

280 MachineBasicBlock *normalizeInfiniteLoopExit(MachineLoop *LoopRep);

281 void removeUnconditionalBranch(MachineBasicBlock *MBB);

282

283

284

285

286

287

288

289

290

291 void removeRedundantConditionalBranch(MachineBasicBlock *MBB);

292

293 void addDummyExitBlock(SmallVectorImpl<MachineBasicBlock *> &RetMBB);

294 void removeSuccessor(MachineBasicBlock *MBB);

295 MachineBasicBlock *cloneBlockForPredecessor(MachineBasicBlock *MBB,

296 MachineBasicBlock *PredMBB);

297 void migrateInstruction(MachineBasicBlock *SrcMBB,

299 void recordSccnum(MachineBasicBlock *MBB, int SCCNum);

300 void retireBlock(MachineBasicBlock *MBB);

301

302private:

303 MBBInfoMap BlockInfoMap;

304 LoopLandInfoMap LLInfoMap;

305 std::map<MachineLoop *, bool> Visited;

306 MachineFunction *FuncRep;

308};

309

310}

311

312char R600MachineCFGStructurizer::ID = 0;

313

315 MBBInfoMap::const_iterator It = BlockInfoMap.find(MBB);

316 if (It == BlockInfoMap.end())

318 return (*It).second->SccNum;

319}

320

321MachineBasicBlock *R600MachineCFGStructurizer::getLoopLandInfo(MachineLoop *LoopRep)

322 const {

323 LoopLandInfoMap::const_iterator It = LLInfoMap.find(LoopRep);

324 if (It == LLInfoMap.end())

325 return nullptr;

326 return (*It).second;

327}

328

329bool R600MachineCFGStructurizer::hasBackEdge(MachineBasicBlock *MBB) const {

331 if (!LoopRep)

332 return false;

333 MachineBasicBlock *LoopHeader = LoopRep->getHeader();

335}

336

337bool R600MachineCFGStructurizer::isRetiredBlock(MachineBasicBlock *MBB) const {

338 MBBInfoMap::const_iterator It = BlockInfoMap.find(MBB);

339 if (It == BlockInfoMap.end())

340 return false;

341 return (*It).second->IsRetired;

342}

343

344bool R600MachineCFGStructurizer::isActiveLoophead(MachineBasicBlock *MBB) const {

346 while (LoopRep && LoopRep->getHeader() == MBB) {

347 MachineBasicBlock *LoopLand = getLoopLandInfo(LoopRep);

348 if(!LoopLand)

349 return true;

350 if (!isRetiredBlock(LoopLand))

351 return true;

353 }

354 return false;

355}

356

357R600MachineCFGStructurizer::PathToKind R600MachineCFGStructurizer::singlePathTo(

358 MachineBasicBlock *SrcMBB, MachineBasicBlock *DstMBB,

359 bool AllowSideEntry) const {

361 if (SrcMBB == DstMBB)

362 return SinglePath_InPath;

363 while (SrcMBB && SrcMBB->succ_size() == 1) {

365 if (SrcMBB == DstMBB)

366 return SinglePath_InPath;

367 if (!AllowSideEntry && SrcMBB->pred_size() > 1)

368 return Not_SinglePath;

369 }

370 if (SrcMBB && SrcMBB->succ_size()==0)

371 return SinglePath_NotInPath;

372 return Not_SinglePath;

373}

374

378 while (It != E) {

379 if (!isRetiredBlock(*It))

381 ++It;

382 }

384}

385

386bool R600MachineCFGStructurizer::needMigrateBlock(MachineBasicBlock *MBB) const {

387 unsigned BlockSizeThreshold = 30;

388 unsigned CloneInstrThreshold = 100;

390

391 if(!MultiplePreds)

392 return false;

393 unsigned BlkSize = MBB->size();

394 return ((BlkSize > BlockSizeThreshold) &&

395 (BlkSize * (MBB->pred_size() - 1) > CloneInstrThreshold));

396}

397

398void R600MachineCFGStructurizer::reversePredicateSetter(

400 assert(I.isValid() && "Expected valid iterator");

401 for (;; --I) {

403 continue;

404 if (I->getOpcode() == R600::PRED_X) {

405 switch (I->getOperand(2).getImm()) {

406 case R600::PRED_SETE_INT:

407 I->getOperand(2).setImm(R600::PRED_SETNE_INT);

408 return;

409 case R600::PRED_SETNE_INT:

410 I->getOperand(2).setImm(R600::PRED_SETE_INT);

411 return;

412 case R600::PRED_SETE:

413 I->getOperand(2).setImm(R600::PRED_SETNE);

414 return;

415 case R600::PRED_SETNE:

416 I->getOperand(2).setImm(R600::PRED_SETE);

417 return;

418 default:

420 }

421 }

422 }

423}

424

425void R600MachineCFGStructurizer::insertInstrEnd(MachineBasicBlock *MBB,

427 MachineInstr *MI =

430

432}

433

434MachineInstr *R600MachineCFGStructurizer::insertInstrBefore(MachineBasicBlock *MBB,

435 int NewOpcode,

437 MachineInstr *MI =

441 else

444 return MI;

445}

446

447MachineInstr *R600MachineCFGStructurizer::insertInstrBefore(

449 MachineInstr *OldMI = &(*I);

451 MachineInstr *NewMBB =

454

456 return NewMBB;

457}

458

459void R600MachineCFGStructurizer::insertCondBranchBefore(

461 MachineInstr *OldMI = &(*I);

464 MachineInstr *NewMI = MF->CreateMachineInstr(TII->get(NewOpcode), DL);

466 MachineInstrBuilder MIB(*MF, NewMI);

469

470}

471

472void R600MachineCFGStructurizer::insertCondBranchBefore(

475 MachineFunction *MF = blk->getParent();

476 MachineInstr *NewInstr = MF->CreateMachineInstr(TII->get(NewOpcode), DL);

477

478 blk->insert(I, NewInstr);

479 MachineInstrBuilder(*MF, NewInstr).addReg(RegNum, false);

481}

482

483int R600MachineCFGStructurizer::getBranchNzeroOpcode(int OldOpcode) {

484 switch(OldOpcode) {

485 case R600::JUMP_COND:

486 case R600::JUMP: return R600::IF_PREDICATE_SET;

487 case R600::BRANCH_COND_i32:

488 case R600::BRANCH_COND_f32: return R600::IF_LOGICALNZ_f32;

490 }

491 return -1;

492}

493

494int R600MachineCFGStructurizer::getBranchZeroOpcode(int OldOpcode) {

495 switch(OldOpcode) {

496 case R600::JUMP_COND:

497 case R600::JUMP: return R600::IF_PREDICATE_SET;

498 case R600::BRANCH_COND_i32:

499 case R600::BRANCH_COND_f32: return R600::IF_LOGICALZ_f32;

501 }

502 return -1;

503}

504

505int R600MachineCFGStructurizer::getContinueNzeroOpcode(int OldOpcode) {

506 switch(OldOpcode) {

507 case R600::JUMP_COND:

508 case R600::JUMP: return R600::CONTINUE_LOGICALNZ_i32;

510 }

511 return -1;

512}

513

514int R600MachineCFGStructurizer::getContinueZeroOpcode(int OldOpcode) {

515 switch(OldOpcode) {

516 case R600::JUMP_COND:

517 case R600::JUMP: return R600::CONTINUE_LOGICALZ_i32;

519 }

520 return -1;

521}

522

523MachineBasicBlock *R600MachineCFGStructurizer::getTrueBranch(MachineInstr *MI) {

524 return MI->getOperand(0).getMBB();

525}

526

527void R600MachineCFGStructurizer::setTrueBranch(MachineInstr *MI,

528 MachineBasicBlock *MBB) {

529 MI->getOperand(0).setMBB(MBB);

530}

531

532MachineBasicBlock *

533R600MachineCFGStructurizer::getFalseBranch(MachineBasicBlock *MBB,

534 MachineInstr *MI) {

536 MachineBasicBlock *TrueBranch = getTrueBranch(MI);

540 return (*It == TrueBranch) ? *Next : *It;

541}

542

543bool R600MachineCFGStructurizer::isCondBranch(MachineInstr *MI) {

544 switch (MI->getOpcode()) {

545 case R600::JUMP_COND:

546 case R600::BRANCH_COND_i32:

547 case R600::BRANCH_COND_f32: return true;

548 default:

549 return false;

550 }

551 return false;

552}

553

554bool R600MachineCFGStructurizer::isUncondBranch(MachineInstr *MI) {

555 switch (MI->getOpcode()) {

556 case R600::JUMP:

557 case R600::BRANCH:

558 return true;

559 default:

560 return false;

561 }

562 return false;

563}

564

565DebugLoc R600MachineCFGStructurizer::getLastDebugLocInBB(MachineBasicBlock *MBB) {

566

568 for (MachineInstr &MI : *MBB)

569 if (MI.getDebugLoc())

570 DL = MI.getDebugLoc();

571 return DL;

572}

573

574MachineInstr *R600MachineCFGStructurizer::getNormalBlockBranchInstr(

575 MachineBasicBlock *MBB) {

577 MachineInstr *MI = &*It;

578 if (MI && (isCondBranch(MI) || isUncondBranch(MI)))

579 return MI;

580 return nullptr;

581}

582

583MachineInstr *R600MachineCFGStructurizer::getLoopendBlockBranchInstr(

584 MachineBasicBlock *MBB) {

586 It != E; ++It) {

587

588 MachineInstr *MI = &*It;

589 if (MI) {

590 if (isCondBranch(MI) || isUncondBranch(MI))

591 return MI;

592 if ( TII ->isMov(MI->getOpcode()))

593 break;

594 }

595 }

596 return nullptr;

597}

598

599MachineInstr *R600MachineCFGStructurizer::getReturnInstr(MachineBasicBlock *MBB) {

602 MachineInstr *instr = &(*It);

603 if (instr->getOpcode() == R600::RETURN)

605 }

606 return nullptr;

607}

608

609bool R600MachineCFGStructurizer::isReturnBlock(MachineBasicBlock *MBB) {

610 MachineInstr *MI = getReturnInstr(MBB);

612 if (MI)

614 else if (IsReturn)

616 << " is return block without RETURN instr\n";);

617 return IsReturn;

618}

619

620void R600MachineCFGStructurizer::cloneSuccessorList(MachineBasicBlock *DstMBB,

621 MachineBasicBlock *SrcMBB) {

622 for (MachineBasicBlock *Succ : SrcMBB->successors())

623 DstMBB->addSuccessor(Succ);

624}

625

626MachineBasicBlock *R600MachineCFGStructurizer::clone(MachineBasicBlock *MBB) {

628 MachineBasicBlock *NewMBB = Func->CreateMachineBasicBlock();

629 Func->push_back(NewMBB);

630 for (const MachineInstr &It : *MBB)

632 return NewMBB;

633}

634

635void R600MachineCFGStructurizer::replaceInstrUseOfBlockWith(

636 MachineBasicBlock *SrcMBB, MachineBasicBlock *OldMBB,

637 MachineBasicBlock *NewBlk) {

638 MachineInstr *BranchMI = getLoopendBlockBranchInstr(SrcMBB);

639 if (BranchMI && isCondBranch(BranchMI) &&

640 getTrueBranch(BranchMI) == OldMBB)

641 setTrueBranch(BranchMI, NewBlk);

642}

643

644void R600MachineCFGStructurizer::wrapup(MachineBasicBlock *MBB) {

647 && "found a jump table");

648

649

654 while (It != E) {

655 if (Pre->getOpcode() == R600::CONTINUE

656 && It->getOpcode() == R600::ENDLOOP)

658 Pre = It;

659 ++It;

660 }

661

662

663 for (auto *MI : ContInstr)

664 MI->eraseFromParent();

665

666

667

668

669

670}

671

672bool R600MachineCFGStructurizer::prepare() {

674

675

676

677 LLVM_DEBUG(dbgs() << "R600MachineCFGStructurizer::prepare\n";);

678

679 orderBlocks(FuncRep);

680

682

683

684 for (MachineLoop *LoopRep : *MLI) {

687

688 if (ExitingMBBs.size() == 0) {

689 MachineBasicBlock* DummyExitBlk = normalizeInfiniteLoopExit(LoopRep);

690 if (DummyExitBlk)

692 }

693 }

694

695

696

697 for (MachineBasicBlock *MBB : OrderedBlks) {

698 removeUnconditionalBranch(MBB);

699 removeRedundantConditionalBranch(MBB);

700 if (isReturnBlock(MBB)) {

702 }

704 }

705

706 if (RetBlks.size() >= 2) {

707 addDummyExitBlock(RetBlks);

709 }

710

712}

713

714bool R600MachineCFGStructurizer::run() {

715

716 LLVM_DEBUG(dbgs() << "R600MachineCFGStructurizer::run\n");

717

718#ifdef STRESSTEST

719

720 ReverseVector(orderedBlks);

721#endif

722

723 LLVM_DEBUG(dbgs() << "Ordered blocks:\n"; printOrderedBlocks(););

724 int NumIter = 0;

725 bool Finish = false;

726 MachineBasicBlock *MBB;

727 bool MakeProgress = false;

728 int NumRemainedBlk = countActiveBlock(OrderedBlks.begin(),

729 OrderedBlks.end());

730

731 do {

732 ++NumIter;

734 << ", numRemaintedBlk = " << NumRemainedBlk << "\n";);

735 (void)NumIter;

736

738 OrderedBlks.begin();

740 OrderedBlks.end();

741

743 It;

744 MachineBasicBlock *SccBeginMBB = nullptr;

745 int SccNumBlk = 0;

746

747 int SccNumIter;

748

749 while (It != E) {

750 MBB = *It;

751

752 if (!SccBeginMBB) {

753 SccBeginIter = It;

754 SccBeginMBB = MBB;

755 SccNumIter = 0;

756 SccNumBlk = NumRemainedBlk;

757 LLVM_DEBUG(dbgs() << "start processing SCC" << getSCCNum(SccBeginMBB);

758 dbgs() << "\n";);

759 }

760

761 if (!isRetiredBlock(MBB))

762 patternMatch(MBB);

763

764 ++It;

765

766 bool ContNextScc = true;

767 if (It == E

768 || getSCCNum(SccBeginMBB) != getSCCNum(*It)) {

769

770 ++SccNumIter;

771 int sccRemainedNumBlk = countActiveBlock(SccBeginIter, It);

772 if (sccRemainedNumBlk != 1 && sccRemainedNumBlk >= SccNumBlk) {

774 << ", sccNumIter = " << SccNumIter;

775 dbgs() << "doesn't make any progress\n";);

776 (void)SccNumIter;

777 ContNextScc = true;

778 } else if (sccRemainedNumBlk != 1 && sccRemainedNumBlk < SccNumBlk) {

779 SccNumBlk = sccRemainedNumBlk;

780 It = SccBeginIter;

781 ContNextScc = false;

783 << "sccNumIter = " << SccNumIter << '\n';);

784 } else {

785

786 ContNextScc = true;

787 }

788 } else {

789

790 ContNextScc = false;

791 }

792

793 if (ContNextScc)

794 SccBeginMBB = nullptr;

795 }

796

797 MachineBasicBlock *EntryMBB =

800 Finish = true;

802 } else {

803 int NewnumRemainedBlk

804 = countActiveBlock(OrderedBlks.begin(), OrderedBlks.end());

805

806 if (NewnumRemainedBlk == 1 || NewnumRemainedBlk < NumRemainedBlk) {

807 MakeProgress = true;

808 NumRemainedBlk = NewnumRemainedBlk;

809 } else {

810 MakeProgress = false;

812 }

813 }

814 } while (!Finish && MakeProgress);

815

816

818

819

820 for (auto &It : BlockInfoMap) {

821 if (It.second && It.second->IsRetired) {

822 assert((It.first)->getNumber() != -1);

823 LLVM_DEBUG(dbgs() << "Erase BB" << (It.first)->getNumber() << "\n";);

824 It.first->eraseFromParent();

825 }

826 delete It.second;

827 }

828 BlockInfoMap.clear();

829 LLInfoMap.clear();

830

831 if (!Finish) {

834 }

835

836 return true;

837}

838

839void R600MachineCFGStructurizer::orderBlocks(MachineFunction *MF) {

840 int SccNum = 0;

841 for (scc_iterator<MachineFunction *> It = scc_begin(MF); !It.isAtEnd();

842 ++It, ++SccNum) {

843 const std::vector<MachineBasicBlock *> &SccNext = *It;

844 for (MachineBasicBlock *MBB : SccNext) {

845 OrderedBlks.push_back(MBB);

846 recordSccnum(MBB, SccNum);

847 }

848 }

849

850

851 for (auto *MBB : nodes(MF)) {

852 SccNum = getSCCNum(MBB);

854 dbgs() << "unreachable block BB" << MBB->getNumber() << "\n";

855 }

856}

857

858int R600MachineCFGStructurizer::patternMatch(MachineBasicBlock *MBB) {

859 int NumMatch = 0;

860 int CurMatch;

861

863

864 while ((CurMatch = patternMatchGroup(MBB)) > 0)

865 NumMatch += CurMatch;

866

868 << ", numMatch = " << NumMatch << "\n";);

869

870 return NumMatch;

871}

872

873int R600MachineCFGStructurizer::patternMatchGroup(MachineBasicBlock *MBB) {

874 int NumMatch = 0;

875 NumMatch += loopendPatternMatch();

876 NumMatch += serialPatternMatch(MBB);

877 NumMatch += ifPatternMatch(MBB);

878 return NumMatch;

879}

880

881int R600MachineCFGStructurizer::serialPatternMatch(MachineBasicBlock *MBB) {

883 return 0;

884

885 MachineBasicBlock *childBlk = *MBB->succ_begin();

886 if (childBlk->pred_size() != 1 || isActiveLoophead(childBlk))

887 return 0;

888

889 mergeSerialBlock(MBB, childBlk);

890 ++numSerialPatternMatch;

891 return 1;

892}

893

894int R600MachineCFGStructurizer::ifPatternMatch(MachineBasicBlock *MBB) {

895

897 return 0;

898 if (hasBackEdge(MBB))

899 return 0;

900 MachineInstr *BranchMI = getNormalBlockBranchInstr(MBB);

901 if (!BranchMI)

902 return 0;

903

904 assert(isCondBranch(BranchMI));

905 int NumMatch = 0;

906

907 MachineBasicBlock *TrueMBB = getTrueBranch(BranchMI);

908 NumMatch += serialPatternMatch(TrueMBB);

909 NumMatch += ifPatternMatch(TrueMBB);

910 MachineBasicBlock *FalseMBB = getFalseBranch(MBB, BranchMI);

911 NumMatch += serialPatternMatch(FalseMBB);

912 NumMatch += ifPatternMatch(FalseMBB);

913 MachineBasicBlock *LandBlk;

914 int Cloned = 0;

915

917

920

922 } else if (TrueMBB->succ_size() == 1 && *TrueMBB->succ_begin() == FalseMBB) {

923

924 LandBlk = FalseMBB;

925 FalseMBB = nullptr;

926 } else if (FalseMBB->succ_size() == 1

927 && *FalseMBB->succ_begin() == TrueMBB) {

928

929

931 reversePredicateSetter(MBB->end(), *MBB);

932 LandBlk = FalseMBB;

933 FalseMBB = nullptr;

934 } else if (FalseMBB->succ_size() == 1

935 && isSameloopDetachedContbreak(TrueMBB, FalseMBB)) {

937 } else if (TrueMBB->succ_size() == 1

938 && isSameloopDetachedContbreak(FalseMBB, TrueMBB)) {

940 } else {

941 return NumMatch + handleJumpintoIf(MBB, TrueMBB, FalseMBB);

942 }

943

944

945

946

947 if (LandBlk &&

948 ((TrueMBB && TrueMBB->pred_size() > 1)

949 || (FalseMBB && FalseMBB->pred_size() > 1))) {

950 Cloned += improveSimpleJumpintoIf(MBB, TrueMBB, FalseMBB, &LandBlk);

951 }

952

953 if (TrueMBB && TrueMBB->pred_size() > 1) {

954 TrueMBB = cloneBlockForPredecessor(TrueMBB, MBB);

955 ++Cloned;

956 }

957

958 if (FalseMBB && FalseMBB->pred_size() > 1) {

959 FalseMBB = cloneBlockForPredecessor(FalseMBB, MBB);

960 ++Cloned;

961 }

962

963 mergeIfthenelseBlock(BranchMI, MBB, TrueMBB, FalseMBB, LandBlk);

964

965 ++numIfPatternMatch;

966

967 numClonedBlock += Cloned;

968

969 return 1 + Cloned + NumMatch;

970}

971

972int R600MachineCFGStructurizer::loopendPatternMatch() {

973 std::deque<MachineLoop *> NestedLoops;

974 for (auto &It: *MLI)

976 NestedLoops.push_front(ML);

977

978 if (NestedLoops.empty())

979 return 0;

980

981

982

983

984 int Num = 0;

985 for (MachineLoop *ExaminedLoop : NestedLoops) {

986 if (ExaminedLoop->getNumBlocks() == 0 || Visited[ExaminedLoop])

987 continue;

988 LLVM_DEBUG(dbgs() << "Processing:\n"; ExaminedLoop->dump(););

989 int NumBreak = mergeLoop(ExaminedLoop);

990 if (NumBreak == -1)

991 break;

992 Num += NumBreak;

993 }

994 return Num;

995}

996

997int R600MachineCFGStructurizer::mergeLoop(MachineLoop *LoopRep) {

998 MachineBasicBlock *LoopHeader = LoopRep->getHeader();

1001 assert(!ExitingMBBs.empty() && "Infinite Loop not supported");

1003 << " exiting blocks\n";);

1004

1007 SmallPtrSet<MachineBasicBlock *, 2> ExitBlkSet(llvm::from_range, ExitBlks);

1008 assert(ExitBlkSet.size() == 1);

1009 MachineBasicBlock *ExitBlk = *ExitBlks.begin();

1010 assert(ExitBlk && "Loop has several exit block");

1015

1016 for (MachineBasicBlock *MBB : ExitingMBBs)

1017 mergeLoopbreakBlock(MBB, ExitBlk);

1018 for (MachineBasicBlock *MBB : LatchBlks)

1019 settleLoopcontBlock(MBB, LoopHeader);

1020 int Match = 0;

1021 do {

1022 Match = 0;

1023 Match += serialPatternMatch(LoopHeader);

1024 Match += ifPatternMatch(LoopHeader);

1025 } while (Match > 0);

1026 mergeLooplandBlock(LoopHeader, ExitBlk);

1027 MachineLoop *ParentLoop = LoopRep->getParentLoop();

1028 if (ParentLoop)

1029 MLI->changeLoopFor(LoopHeader, ParentLoop);

1030 else

1031 MLI->removeBlock(LoopHeader);

1032 Visited[LoopRep] = true;

1033 return 1;

1034}

1035

1036bool R600MachineCFGStructurizer::isSameloopDetachedContbreak(

1037 MachineBasicBlock *Src1MBB, MachineBasicBlock *Src2MBB) {

1039 MachineLoop *LoopRep = MLI->getLoopFor(Src1MBB);

1040 if (LoopRep&& LoopRep == MLI->getLoopFor(Src2MBB)) {

1041 MachineBasicBlock *&TheEntry = LLInfoMap[LoopRep];

1042 if (TheEntry) {

1043 LLVM_DEBUG(dbgs() << "isLoopContBreakBlock yes src1 = BB"

1044 << Src1MBB->getNumber() << " src2 = BB"

1045 << Src2MBB->getNumber() << "\n";);

1046 return true;

1047 }

1048 }

1049 }

1050 return false;

1051}

1052

1053int R600MachineCFGStructurizer::handleJumpintoIf(MachineBasicBlock *HeadMBB,

1054 MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB) {

1055 int Num = handleJumpintoIfImp(HeadMBB, TrueMBB, FalseMBB);

1056 if (Num == 0) {

1057 LLVM_DEBUG(dbgs() << "handleJumpintoIf swap trueBlk and FalseBlk"

1058 << "\n";);

1059 Num = handleJumpintoIfImp(HeadMBB, FalseMBB, TrueMBB);

1060 }

1061 return Num;

1062}

1063

1064int R600MachineCFGStructurizer::handleJumpintoIfImp(MachineBasicBlock *HeadMBB,

1065 MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB) {

1066 int Num = 0;

1067 MachineBasicBlock *DownBlk;

1068

1069

1070 DownBlk = TrueMBB;

1071

1073 << " true = BB" << TrueMBB->getNumber()

1074 << ", numSucc=" << TrueMBB->succ_size() << " false = BB"

1075 << FalseMBB->getNumber() << "\n";);

1076

1077 while (DownBlk) {

1079

1080 if (singlePathTo(FalseMBB, DownBlk) == SinglePath_InPath) {

1082

1083 Num += cloneOnSideEntryTo(HeadMBB, TrueMBB, DownBlk);

1084 Num += cloneOnSideEntryTo(HeadMBB, FalseMBB, DownBlk);

1085

1086 numClonedBlock += Num;

1087 Num += serialPatternMatch(*HeadMBB->succ_begin());

1088 Num += serialPatternMatch(*std::next(HeadMBB->succ_begin()));

1089 Num += ifPatternMatch(HeadMBB);

1091

1092 break;

1093 }

1095 DownBlk = (DownBlk->succ_size() == 1) ? (*DownBlk->succ_begin()) : nullptr;

1096 }

1097

1098 return Num;

1099}

1100

1101#ifndef NDEBUG

1102void R600MachineCFGStructurizer::showImproveSimpleJumpintoIf(

1103 MachineBasicBlock *HeadMBB, MachineBasicBlock *TrueMBB,

1104 MachineBasicBlock *FalseMBB, MachineBasicBlock *LandMBB, bool Detail) {

1106 << " size = " << HeadMBB->size();

1107 if (Detail) {

1108 dbgs() << "\n";

1110 dbgs() << "\n";

1111 }

1112

1113 if (TrueMBB) {

1114 dbgs() << ", true = BB" << TrueMBB->getNumber() << " size = "

1115 << TrueMBB->size() << " numPred = " << TrueMBB->pred_size();

1116 if (Detail) {

1117 dbgs() << "\n";

1119 dbgs() << "\n";

1120 }

1121 }

1122 if (FalseMBB) {

1123 dbgs() << ", false = BB" << FalseMBB->getNumber() << " size = "

1124 << FalseMBB->size() << " numPred = " << FalseMBB->pred_size();

1125 if (Detail) {

1126 dbgs() << "\n";

1128 dbgs() << "\n";

1129 }

1130 }

1131 if (LandMBB) {

1132 dbgs() << ", land = BB" << LandMBB->getNumber() << " size = "

1133 << LandMBB->size() << " numPred = " << LandMBB->pred_size();

1134 if (Detail) {

1135 dbgs() << "\n";

1137 dbgs() << "\n";

1138 }

1139 }

1140

1141 dbgs() << "\n";

1142}

1143#endif

1144

1145int R600MachineCFGStructurizer::improveSimpleJumpintoIf(MachineBasicBlock *HeadMBB,

1146 MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB,

1147 MachineBasicBlock **LandMBBPtr) {

1148 bool MigrateTrue = false;

1149 bool MigrateFalse = false;

1150

1151 MachineBasicBlock *LandBlk = *LandMBBPtr;

1152

1154 && (!FalseMBB || FalseMBB->succ_size() <= 1));

1155

1156 if (TrueMBB == FalseMBB)

1157 return 0;

1158

1159 MigrateTrue = needMigrateBlock(TrueMBB);

1160 MigrateFalse = needMigrateBlock(FalseMBB);

1161

1162 if (!MigrateTrue && !MigrateFalse)

1163 return 0;

1164

1165

1166

1167

1168 if (!MigrateTrue && TrueMBB && TrueMBB->pred_size() > 1)

1169 MigrateTrue = true;

1170 if (!MigrateFalse && FalseMBB && FalseMBB->pred_size() > 1)

1171 MigrateFalse = true;

1172

1174 dbgs() << "before improveSimpleJumpintoIf: ";

1175 showImproveSimpleJumpintoIf(HeadMBB, TrueMBB, FalseMBB, LandBlk, 0););

1176

1177

1178

1179

1180

1181

1182

1183

1184

1185

1186

1187

1188 const TargetRegisterClass * I32RC = TRI->getCFGStructurizerRegClass(MVT::i32);

1189 if (!MigrateTrue || !MigrateFalse) {

1190

1191

1192

1193

1194

1195

1196

1197

1198

1199

1200

1201

1202

1203

1204

1205

1206

1207

1208

1209

1210

1211

1212

1213

1214

1215

1216

1217

1218

1219

1220

1221

1222

1223

1224

1225

1226

1227

1228

1229

1230

1231

1232

1233

1234

1235

1236

1237

1238

1239

1240

1241

1242

1243

1244

1245

1246

1247

1248

1249

1250

1251

1252

1253

1254

1255 return 0;

1256 }

1257

1258 int NumNewBlk = 0;

1259

1260 bool LandBlkHasOtherPred = (LandBlk->pred_size() > 2);

1261

1262

1264

1265 if (LandBlkHasOtherPred) {

1269 report_fatal_error("Extra compare instruction needed to handle CFG");

1270 insertCondBranchBefore(LandBlk, I, R600::IF_PREDICATE_SET,

1272 }

1273

1274

1275

1278 insertCondBranchBefore(LandBlk, I, R600::IF_PREDICATE_SET, InitReg,

1280

1281 if (MigrateTrue) {

1282 migrateInstruction(TrueMBB, LandBlk, I);

1283

1284

1285

1287 }

1288 insertInstrBefore(I, R600::ELSE);

1289

1290 if (MigrateFalse) {

1291 migrateInstruction(FalseMBB, LandBlk, I);

1292

1293

1294

1296 }

1297

1298 if (LandBlkHasOtherPred) {

1299

1300 insertInstrBefore(I, R600::ENDIF);

1301

1302

1304 if (MBB != TrueMBB && MBB != FalseMBB)

1306 }

1308 dbgs() << "result from improveSimpleJumpintoIf: ";

1309 showImproveSimpleJumpintoIf(HeadMBB, TrueMBB, FalseMBB, LandBlk, 0););

1310

1311

1312 *LandMBBPtr = LandBlk;

1313

1314 return NumNewBlk;

1315}

1316

1317void R600MachineCFGStructurizer::mergeSerialBlock(MachineBasicBlock *DstMBB,

1318 MachineBasicBlock *SrcMBB) {

1320 << SrcMBB->getNumber() << "\n";);

1321 DstMBB->splice(DstMBB->end(), SrcMBB, SrcMBB->begin(), SrcMBB->end());

1322

1324 cloneSuccessorList(DstMBB, SrcMBB);

1325

1326 removeSuccessor(SrcMBB);

1327 MLI->removeBlock(SrcMBB);

1328 retireBlock(SrcMBB);

1329}

1330

1331void R600MachineCFGStructurizer::mergeIfthenelseBlock(MachineInstr *BranchMI,

1332 MachineBasicBlock *MBB, MachineBasicBlock *TrueMBB,

1333 MachineBasicBlock *FalseMBB, MachineBasicBlock *LandMBB) {

1337 << " } else ";

1338 dbgs() << "{ "; if (FalseMBB) {

1340 } dbgs() << " }\n ";

1341 dbgs() << "landBlock: "; if (!LandMBB) { dbgs() << "NULL"; } else {

1343 } dbgs() << "\n";);

1344

1345 int OldOpcode = BranchMI->getOpcode();

1347

1348

1349

1350

1351

1352

1353

1354

1355

1357 insertCondBranchBefore(I, getBranchNzeroOpcode(OldOpcode),

1358 BranchDL);

1359

1360 if (TrueMBB) {

1363 if (LandMBB && TrueMBB->succ_size()!=0)

1365 retireBlock(TrueMBB);

1366 MLI->removeBlock(TrueMBB);

1367 }

1368

1369 if (FalseMBB) {

1370 insertInstrBefore(I, R600::ELSE);

1372 FalseMBB->end());

1374 if (LandMBB && !FalseMBB->succ_empty())

1376 retireBlock(FalseMBB);

1377 MLI->removeBlock(FalseMBB);

1378 }

1379 insertInstrBefore(I, R600::ENDIF);

1380

1382

1383 if (LandMBB && TrueMBB && FalseMBB)

1385}

1386

1387void R600MachineCFGStructurizer::mergeLooplandBlock(MachineBasicBlock *DstBlk,

1388 MachineBasicBlock *LandMBB) {

1390 << " land = BB" << LandMBB->getNumber() << "\n";);

1391

1392 insertInstrBefore(DstBlk, R600::WHILELOOP, DebugLoc());

1393 insertInstrEnd(DstBlk, R600::ENDLOOP, DebugLoc());

1395}

1396

1397void R600MachineCFGStructurizer::mergeLoopbreakBlock(MachineBasicBlock *ExitingMBB,

1398 MachineBasicBlock *LandMBB) {

1399 LLVM_DEBUG(dbgs() << "loopbreakPattern exiting = BB"

1400 << ExitingMBB->getNumber() << " land = BB"

1401 << LandMBB->getNumber() << "\n";);

1402 MachineInstr *BranchMI = getLoopendBlockBranchInstr(ExitingMBB);

1403 assert(BranchMI && isCondBranch(BranchMI));

1405 MachineBasicBlock *TrueBranch = getTrueBranch(BranchMI);

1407 if (TrueBranch != LandMBB)

1408 reversePredicateSetter(I, *I->getParent());

1409 insertCondBranchBefore(ExitingMBB, I, R600::IF_PREDICATE_SET, R600::PREDICATE_BIT, DL);

1410 insertInstrBefore(I, R600::BREAK);

1411 insertInstrBefore(I, R600::ENDIF);

1412

1414

1416}

1417

1418void R600MachineCFGStructurizer::settleLoopcontBlock(MachineBasicBlock *ContingMBB,

1419 MachineBasicBlock *ContMBB) {

1420 LLVM_DEBUG(dbgs() << "settleLoopcontBlock conting = BB"

1421 << ContingMBB->getNumber() << ", cont = BB"

1422 << ContMBB->getNumber() << "\n";);

1423

1424 MachineInstr *MI = getLoopendBlockBranchInstr(ContingMBB);

1425 if (MI) {

1428 MachineBasicBlock *TrueBranch = getTrueBranch(MI);

1429 int OldOpcode = MI->getOpcode();

1431

1432 bool UseContinueLogical = ((&*ContingMBB->rbegin()) == MI);

1433

1434 if (!UseContinueLogical) {

1435 int BranchOpcode =

1436 TrueBranch == ContMBB ? getBranchNzeroOpcode(OldOpcode) :

1437 getBranchZeroOpcode(OldOpcode);

1438 insertCondBranchBefore(I, BranchOpcode, DL);

1439

1440 insertInstrEnd(ContingMBB, R600::CONTINUE, DL);

1441 insertInstrEnd(ContingMBB, R600::ENDIF, DL);

1442 } else {

1443 int BranchOpcode =

1444 TrueBranch == ContMBB ? getContinueNzeroOpcode(OldOpcode) :

1445 getContinueZeroOpcode(OldOpcode);

1446 insertCondBranchBefore(I, BranchOpcode, DL);

1447 }

1448

1449 MI->eraseFromParent();

1450 } else {

1451

1452

1453

1454

1455

1456 insertInstrEnd(ContingMBB, R600::CONTINUE,

1457 getLastDebugLocInBB(ContingMBB));

1458 }

1459}

1460

1461int R600MachineCFGStructurizer::cloneOnSideEntryTo(MachineBasicBlock *PreMBB,

1462 MachineBasicBlock *SrcMBB, MachineBasicBlock *DstMBB) {

1463 int Cloned = 0;

1465 while (SrcMBB && SrcMBB != DstMBB) {

1468 SrcMBB = cloneBlockForPredecessor(SrcMBB, PreMBB);

1469 ++Cloned;

1470 }

1471

1472 PreMBB = SrcMBB;

1474 }

1475

1476 return Cloned;

1477}

1478

1479MachineBasicBlock *

1480R600MachineCFGStructurizer::cloneBlockForPredecessor(MachineBasicBlock *MBB,

1481 MachineBasicBlock *PredMBB) {

1482 assert(PredMBB->isSuccessor(MBB) && "succBlk is not a predecessor of curBlk");

1483

1484 MachineBasicBlock *CloneMBB = clone(MBB);

1485 replaceInstrUseOfBlockWith(PredMBB, MBB, CloneMBB);

1486

1487

1489

1490

1491 cloneSuccessorList(CloneMBB, MBB);

1492

1493 numClonedInstr += MBB->size();

1494

1497 << "\n";);

1498

1499 SHOWNEWBLK(CloneMBB, "result of Cloned block: ");

1500

1501 return CloneMBB;

1502}

1503

1504void R600MachineCFGStructurizer::migrateInstruction(MachineBasicBlock *SrcMBB,

1507

1508 MachineInstr *BranchMI = getNormalBlockBranchInstr(SrcMBB);

1509 if (!BranchMI) {

1510 LLVM_DEBUG(dbgs() << "migrateInstruction don't see branch instr\n";);

1511 SpliceEnd = SrcMBB->end();

1512 } else {

1513 LLVM_DEBUG(dbgs() << "migrateInstruction see branch instr: " << *BranchMI);

1514 SpliceEnd = BranchMI;

1515 }

1516 LLVM_DEBUG(dbgs() << "migrateInstruction before splice dstSize = "

1517 << DstMBB->size() << "srcSize = " << SrcMBB->size()

1518 << "\n";);

1519

1520

1521 DstMBB->splice(I, SrcMBB, SrcMBB->begin(), SpliceEnd);

1522

1523 LLVM_DEBUG(dbgs() << "migrateInstruction after splice dstSize = "

1524 << DstMBB->size() << "srcSize = " << SrcMBB->size()

1525 << '\n';);

1526}

1527

1528MachineBasicBlock *

1529R600MachineCFGStructurizer::normalizeInfiniteLoopExit(MachineLoop* LoopRep) {

1530 MachineBasicBlock *LoopHeader = LoopRep->getHeader();

1531 MachineBasicBlock *LoopLatch = LoopRep->getLoopLatch();

1532

1533 if (!LoopHeader || !LoopLatch)

1534 return nullptr;

1535 MachineInstr *BranchMI = getLoopendBlockBranchInstr(LoopLatch);

1536

1537 if (!BranchMI || !isUncondBranch(BranchMI))

1538 return nullptr;

1539

1541 FuncRep->push_back(DummyExitBlk);

1542 SHOWNEWBLK(DummyExitBlk, "DummyExitBlock to normalize infiniteLoop: ");

1543 LLVM_DEBUG(dbgs() << "Old branch instr: " << *BranchMI << "\n";);

1545 Ctx.emitError("Extra register needed to handle CFG");

1546 return nullptr;

1547}

1548

1549void R600MachineCFGStructurizer::removeUnconditionalBranch(MachineBasicBlock *MBB) {

1550 MachineInstr *BranchMI;

1551

1552

1553

1554 while ((BranchMI = getLoopendBlockBranchInstr(MBB))

1555 && isUncondBranch(BranchMI)) {

1556 LLVM_DEBUG(dbgs() << "Removing uncond branch instr: " << *BranchMI);

1558 }

1559}

1560

1561void R600MachineCFGStructurizer::removeRedundantConditionalBranch(

1562 MachineBasicBlock *MBB) {

1564 return;

1566 MachineBasicBlock *MBB2 = *std::next(MBB->succ_begin());

1567 if (MBB1 != MBB2)

1568 return;

1569

1570 MachineInstr *BranchMI = getNormalBlockBranchInstr(MBB);

1571 assert(BranchMI && isCondBranch(BranchMI));

1572 LLVM_DEBUG(dbgs() << "Removing unneeded cond branch instr: " << *BranchMI);

1574 SHOWNEWBLK(MBB1, "Removing redundant successor");

1576}

1577

1578void R600MachineCFGStructurizer::addDummyExitBlock(

1579 SmallVectorImpl<MachineBasicBlock*> &RetMBB) {

1581 FuncRep->push_back(DummyExitBlk);

1582 insertInstrEnd(DummyExitBlk, R600::RETURN);

1583

1584 for (MachineBasicBlock *MBB : RetMBB) {

1585 if (MachineInstr *MI = getReturnInstr(MBB))

1586 MI->eraseFromParent();

1589 << " successors\n";);

1590 }

1591 SHOWNEWBLK(DummyExitBlk, "DummyExitBlock: ");

1592}

1593

1594void R600MachineCFGStructurizer::removeSuccessor(MachineBasicBlock *MBB) {

1597}

1598

1599void R600MachineCFGStructurizer::recordSccnum(MachineBasicBlock *MBB,

1600 int SccNum) {

1601 BlockInformation *&srcBlkInfo = BlockInfoMap[MBB];

1602 if (!srcBlkInfo)

1603 srcBlkInfo = new BlockInformation();

1604 srcBlkInfo->SccNum = SccNum;

1605}

1606

1607void R600MachineCFGStructurizer::retireBlock(MachineBasicBlock *MBB) {

1609

1610 BlockInformation *&SrcBlkInfo = BlockInfoMap[MBB];

1611

1612 if (!SrcBlkInfo)

1613 SrcBlkInfo = new BlockInformation();

1614

1615 SrcBlkInfo->IsRetired = true;

1617}

1618

1620 "AMDGPU CFG Structurizer", false, false)

1626

1628 return new R600MachineCFGStructurizer();

1629}

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

Unify divergent function exit nodes

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")

This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.

const HexagonInstrInfo * TII

Promote Memory to Register

#define INITIALIZE_PASS_DEPENDENCY(depName)

#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)

#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)

SmallVector< MachineBasicBlock *, 4 > MBBVector

Provides R600 specific target descriptions.

#define SHOWNEWBLK(b, msg)

Definition R600MachineCFGStructurizer.cpp:54

#define SHOWNEWINSTR(i)

Definition R600MachineCFGStructurizer.cpp:52

@ DEFAULT_VEC_SLOTS

Definition R600MachineCFGStructurizer.cpp:27

#define INVALIDSCCNUM

Definition R600MachineCFGStructurizer.cpp:65

Interface definition for R600RegisterInfo.

AMDGPU R600 specific subclass of TargetSubtarget.

This builds on the llvm/ADT/GraphTraits.h file to find the strongly connected components (SCCs) of a ...

static uint32_t blk(uint32_t *Buf, int I)

This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...

#define STATISTIC(VARNAME, DESC)

AnalysisUsage & addRequired()

FunctionPass class - This class is used to implement most global optimizations.

LLVMContext & getContext() const

getContext - Return a reference to the LLVMContext associated with this function.

LLVM_ABI void emitError(const Instruction *I, const Twine &ErrorStr)

emitError - Emit an error message to the currently installed error handler with optional location inf...

bool contains(const LoopT *L) const

Return true if the specified loop is contained within in this loop.

BlockT * getLoopLatch() const

If there is a single latch block for this loop, return it.

void getExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const

Return all of the successor blocks of this loop.

void getExitingBlocks(SmallVectorImpl< BlockT * > &ExitingBlocks) const

Return all blocks inside the loop that have successors outside of the loop.

BlockT * getHeader() const

LoopT * getParentLoop() const

Return the parent loop if it exists or nullptr for top level loops.

LoopT * getLoopFor(const BlockT *BB) const

Return the inner most loop that BB lives in.

unsigned pred_size() const

LLVM_ABI void replaceSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New)

Replace successor OLD with NEW and update probability info.

LLVM_ABI instr_iterator insert(instr_iterator I, MachineInstr *M)

Insert MI into the instruction list before I, possibly inside a bundle.

int getNumber() const

MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...

void push_back(MachineInstr *MI)

succ_iterator succ_begin()

unsigned succ_size() const

LLVM_ABI void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob=BranchProbability::getUnknown())

Add Succ as a successor of this MachineBasicBlock.

SmallVectorImpl< MachineBasicBlock * >::iterator succ_iterator

LLVM_ABI void removeSuccessor(MachineBasicBlock *Succ, bool NormalizeSuccProbs=false)

Remove successor from the successors list of this MachineBasicBlock.

LLVM_ABI void print(raw_ostream &OS, const SlotIndexes *=nullptr, bool IsStandalone=true) const

MachineInstrBundleIterator< MachineInstr, true > reverse_iterator

const MachineFunction * getParent() const

Return the MachineFunction containing this basic block.

iterator_range< succ_iterator > successors()

reverse_iterator rbegin()

LLVM_ABI bool isSuccessor(const MachineBasicBlock *MBB) const

Return true if the specified MBB is a successor of this block.

iterator_range< pred_iterator > predecessors()

void splice(iterator Where, MachineBasicBlock *Other, iterator From)

Take an instruction from MBB 'Other' at the position From, and insert it into this MBB right before '...

MachineInstrBundleIterator< MachineInstr > iterator

Analysis pass which computes a MachineDominatorTree.

MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...

void getAnalysisUsage(AnalysisUsage &AU) const override

getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.

const TargetSubtargetInfo & getSubtarget() const

getSubtarget - Return the subtarget for which this machine code is being compiled.

void dump() const

dump - Print the current MachineFunction to cerr, useful for debugger use.

void push_back(MachineBasicBlock *MBB)

MachineRegisterInfo & getRegInfo()

getRegInfo - Return information about the registers currently in use.

Function & getFunction()

Return the LLVM function that this machine code represents.

void viewCFG() const

viewCFG - This function is meant for use from the debugger.

const MachineFunctionProperties & getProperties() const

Get the function properties.

const MachineJumpTableInfo * getJumpTableInfo() const

getJumpTableInfo - Return the jump table info object for the current function.

MachineBasicBlock * CreateMachineBasicBlock(const BasicBlock *BB=nullptr, std::optional< UniqueBBID > BBID=std::nullopt)

CreateMachineInstr - Allocate a new MachineInstr.

unsigned getOpcode() const

Returns the opcode of this MachineInstr.

const MachineBasicBlock * getParent() const

const DebugLoc & getDebugLoc() const

Returns the debug location id of this MachineInstr.

LLVM_ABI void eraseFromParent()

Unlink 'this' from the containing basic block and delete it.

const MachineOperand & getOperand(unsigned i) const

bool isEmpty() const

isEmpty - Return true if there are no jump tables.

getReg - Returns the register number.

LLVM_ABI Register createVirtualRegister(const TargetRegisterClass *RegClass, StringRef Name="")

createVirtualRegister - Create and return a new virtual register in the function with the specified r...

typename SuperClass::const_iterator const_iterator

void push_back(const T &Elt)

#define llvm_unreachable(msg)

Marks that the current location is not supposed to be reachable.

PointerTypeMap run(const Module &M)

Compute the PointerTypeMap for the module M.

NodeAddr< FuncNode * > Func

This is an optimization pass for GlobalISel generic memory operations.

constexpr from_range_t from_range

scc_iterator< T > scc_begin(const T &G)

Construct the begin iterator for a deduced graph type T.

LLVM_ABI raw_ostream & dbgs()

dbgs() - This returns a reference to a raw_ostream for debugging messages.

LLVM_ABI void report_fatal_error(Error Err, bool gen_crash_diag=true)

FunctionAddr VTableAddr Count

class LLVM_GSL_OWNER SmallVector

Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...

iterator_range< typename GraphTraits< Inverse< GraphType > >::ChildIteratorType > inverse_children(const typename GraphTraits< GraphType >::NodeRef &G)

FunctionAddr VTableAddr Next

iterator_range< df_iterator< T > > depth_first(const T &G)

FunctionPass * createR600MachineCFGStructurizerPass()

Definition R600MachineCFGStructurizer.cpp:1627

void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)

Implement std::swap in terms of BitVector swap.

static nodes_iterator nodes_begin(MachineFunction *F)