1 //===- R600MachineCFGStructurizer.cpp - CFG Structurizer ------------------===// 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 #include "MCTargetDesc/R600MCTargetDesc.h" 10 #include "R600.h" 11 #include "R600RegisterInfo.h" 12 #include "R600Subtarget.h" 13 #include "llvm/ADT/DepthFirstIterator.h" 14 #include "llvm/ADT/SCCIterator.h" 15 #include "llvm/ADT/Statistic.h" 16 #include "llvm/CodeGen/MachineFunction.h" 17 #include "llvm/CodeGen/MachineFunctionPass.h" 18 #include "llvm/CodeGen/MachineJumpTableInfo.h" 19 #include "llvm/CodeGen/MachineLoopInfo.h" 20 #include "llvm/CodeGen/MachinePostDominators.h" 21 #include "llvm/InitializePasses.h" 22 23 using namespace llvm; 24 25 #define DEBUG_TYPE "structcfg" 26 27 #define DEFAULT_VEC_SLOTS 8 28 29 // TODO: move-begin. 30 31 //===----------------------------------------------------------------------===// 32 // 33 // Statistics for CFGStructurizer. 34 // 35 //===----------------------------------------------------------------------===// 36 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"); 43 44 namespace llvm { 45 46 void initializeR600MachineCFGStructurizerPass(PassRegistry &); 47 48 } // end namespace llvm 49 50 namespace { 51 52 //===----------------------------------------------------------------------===// 53 // 54 // Miscellaneous utility for CFGStructurizer. 55 // 56 //===----------------------------------------------------------------------===// 57 58 #define SHOWNEWINSTR(i) LLVM_DEBUG(dbgs() << "New instr: " << *i << "\n"); 59 60 #define SHOWNEWBLK(b, msg) \ 61 LLVM_DEBUG(dbgs() << msg << "BB" << b->getNumber() << "size " << b->size(); \ 62 dbgs() << "\n";); 63 64 #define SHOWBLK_DETAIL(b, msg) \ 65 LLVM_DEBUG(if (b) { \ 66 dbgs() << msg << "BB" << b->getNumber() << "size " << b->size(); \ 67 b->print(dbgs()); \ 68 dbgs() << "\n"; \ 69 }); 70 71 #define INVALIDSCCNUM -1 72 73 //===----------------------------------------------------------------------===// 74 // 75 // supporting data structure for CFGStructurizer 76 // 77 //===----------------------------------------------------------------------===// 78 79 class BlockInformation { 80 public: 81 bool IsRetired = false; 82 int SccNum = INVALIDSCCNUM; 83 84 BlockInformation() = default; 85 }; 86 87 //===----------------------------------------------------------------------===// 88 // 89 // CFGStructurizer 90 // 91 //===----------------------------------------------------------------------===// 92 93 class R600MachineCFGStructurizer : public MachineFunctionPass { 94 public: 95 using MBBVector = SmallVector<MachineBasicBlock *, 32>; 96 using MBBInfoMap = std::map<MachineBasicBlock *, BlockInformation *>; 97 using LoopLandInfoMap = std::map<MachineLoop *, MachineBasicBlock *>; 98 99 enum PathToKind { 100 Not_SinglePath = 0, 101 SinglePath_InPath = 1, 102 SinglePath_NotInPath = 2 103 }; 104 105 static char ID; 106 107 R600MachineCFGStructurizer() : MachineFunctionPass(ID) { 108 initializeR600MachineCFGStructurizerPass(*PassRegistry::getPassRegistry()); 109 } 110 111 StringRef getPassName() const override { 112 return "AMDGPU Control Flow Graph structurizer Pass"; 113 } 114 115 void getAnalysisUsage(AnalysisUsage &AU) const override { 116 AU.addRequired<MachineDominatorTree>(); 117 AU.addRequired<MachinePostDominatorTree>(); 118 AU.addRequired<MachineLoopInfo>(); 119 MachineFunctionPass::getAnalysisUsage(AU); 120 } 121 122 /// Perform the CFG structurization 123 bool run(); 124 125 /// Perform the CFG preparation 126 /// This step will remove every unconditionnal/dead jump instructions and make 127 /// sure all loops have an exit block 128 bool prepare(); 129 130 bool runOnMachineFunction(MachineFunction &MF) override { 131 // FIXME: This pass causes verification failures. 132 MF.getProperties().set( 133 MachineFunctionProperties::Property::FailsVerification); 134 135 TII = MF.getSubtarget<R600Subtarget>().getInstrInfo(); 136 TRI = &TII->getRegisterInfo(); 137 LLVM_DEBUG(MF.dump();); 138 OrderedBlks.clear(); 139 Visited.clear(); 140 FuncRep = &MF; 141 MLI = &getAnalysis<MachineLoopInfo>(); 142 LLVM_DEBUG(dbgs() << "LoopInfo:\n"; PrintLoopinfo(*MLI);); 143 MDT = &getAnalysis<MachineDominatorTree>(); 144 LLVM_DEBUG(MDT->print(dbgs(), (const Module *)nullptr);); 145 PDT = &getAnalysis<MachinePostDominatorTree>(); 146 LLVM_DEBUG(PDT->print(dbgs());); 147 prepare(); 148 run(); 149 LLVM_DEBUG(MF.dump();); 150 return true; 151 } 152 153 protected: 154 MachineDominatorTree *MDT; 155 MachinePostDominatorTree *PDT; 156 MachineLoopInfo *MLI; 157 const R600InstrInfo *TII = nullptr; 158 const R600RegisterInfo *TRI = nullptr; 159 160 // PRINT FUNCTIONS 161 /// Print the ordered Blocks. 162 void printOrderedBlocks() const { 163 size_t i = 0; 164 for (MBBVector::const_iterator iterBlk = OrderedBlks.begin(), 165 iterBlkEnd = OrderedBlks.end(); iterBlk != iterBlkEnd; ++iterBlk, ++i) { 166 dbgs() << "BB" << (*iterBlk)->getNumber(); 167 dbgs() << "(" << getSCCNum(*iterBlk) << "," << (*iterBlk)->size() << ")"; 168 if (i != 0 && i % 10 == 0) { 169 dbgs() << "\n"; 170 } else { 171 dbgs() << " "; 172 } 173 } 174 } 175 176 static void PrintLoopinfo(const MachineLoopInfo &LoopInfo) { 177 for (const MachineLoop *L : LoopInfo) 178 L->print(dbgs()); 179 } 180 181 // UTILITY FUNCTIONS 182 int getSCCNum(MachineBasicBlock *MBB) const; 183 MachineBasicBlock *getLoopLandInfo(MachineLoop *LoopRep) const; 184 bool hasBackEdge(MachineBasicBlock *MBB) const; 185 bool isRetiredBlock(MachineBasicBlock *MBB) const; 186 bool isActiveLoophead(MachineBasicBlock *MBB) const; 187 PathToKind singlePathTo(MachineBasicBlock *SrcMBB, MachineBasicBlock *DstMBB, 188 bool AllowSideEntry = true) const; 189 int countActiveBlock(MBBVector::const_iterator It, 190 MBBVector::const_iterator E) const; 191 bool needMigrateBlock(MachineBasicBlock *MBB) const; 192 193 // Utility Functions 194 void reversePredicateSetter(MachineBasicBlock::iterator I, 195 MachineBasicBlock &MBB); 196 /// Compute the reversed DFS post order of Blocks 197 void orderBlocks(MachineFunction *MF); 198 199 // Function originally from CFGStructTraits 200 void insertInstrEnd(MachineBasicBlock *MBB, int NewOpcode, 201 const DebugLoc &DL = DebugLoc()); 202 MachineInstr *insertInstrBefore(MachineBasicBlock *MBB, int NewOpcode, 203 const DebugLoc &DL = DebugLoc()); 204 MachineInstr *insertInstrBefore(MachineBasicBlock::iterator I, int NewOpcode); 205 void insertCondBranchBefore(MachineBasicBlock::iterator I, int NewOpcode, 206 const DebugLoc &DL); 207 void insertCondBranchBefore(MachineBasicBlock *MBB, 208 MachineBasicBlock::iterator I, int NewOpcode, 209 int RegNum, const DebugLoc &DL); 210 211 static int getBranchNzeroOpcode(int OldOpcode); 212 static int getBranchZeroOpcode(int OldOpcode); 213 static int getContinueNzeroOpcode(int OldOpcode); 214 static int getContinueZeroOpcode(int OldOpcode); 215 static MachineBasicBlock *getTrueBranch(MachineInstr *MI); 216 static void setTrueBranch(MachineInstr *MI, MachineBasicBlock *MBB); 217 static MachineBasicBlock *getFalseBranch(MachineBasicBlock *MBB, 218 MachineInstr *MI); 219 static bool isCondBranch(MachineInstr *MI); 220 static bool isUncondBranch(MachineInstr *MI); 221 static DebugLoc getLastDebugLocInBB(MachineBasicBlock *MBB); 222 static MachineInstr *getNormalBlockBranchInstr(MachineBasicBlock *MBB); 223 224 /// The correct naming for this is getPossibleLoopendBlockBranchInstr. 225 /// 226 /// BB with backward-edge could have move instructions after the branch 227 /// instruction. Such move instruction "belong to" the loop backward-edge. 228 MachineInstr *getLoopendBlockBranchInstr(MachineBasicBlock *MBB); 229 230 static MachineInstr *getReturnInstr(MachineBasicBlock *MBB); 231 static bool isReturnBlock(MachineBasicBlock *MBB); 232 static void cloneSuccessorList(MachineBasicBlock *DstMBB, 233 MachineBasicBlock *SrcMBB); 234 static MachineBasicBlock *clone(MachineBasicBlock *MBB); 235 236 /// MachineBasicBlock::ReplaceUsesOfBlockWith doesn't serve the purpose 237 /// because the AMDGPU instruction is not recognized as terminator fix this 238 /// and retire this routine 239 void replaceInstrUseOfBlockWith(MachineBasicBlock *SrcMBB, 240 MachineBasicBlock *OldMBB, MachineBasicBlock *NewBlk); 241 242 static void wrapup(MachineBasicBlock *MBB); 243 244 int patternMatch(MachineBasicBlock *MBB); 245 int patternMatchGroup(MachineBasicBlock *MBB); 246 int serialPatternMatch(MachineBasicBlock *MBB); 247 int ifPatternMatch(MachineBasicBlock *MBB); 248 int loopendPatternMatch(); 249 int mergeLoop(MachineLoop *LoopRep); 250 251 /// return true iff src1Blk->succ_empty() && src1Blk and src2Blk are in 252 /// the same loop with LoopLandInfo without explicitly keeping track of 253 /// loopContBlks and loopBreakBlks, this is a method to get the information. 254 bool isSameloopDetachedContbreak(MachineBasicBlock *Src1MBB, 255 MachineBasicBlock *Src2MBB); 256 int handleJumpintoIf(MachineBasicBlock *HeadMBB, 257 MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB); 258 int handleJumpintoIfImp(MachineBasicBlock *HeadMBB, 259 MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB); 260 int improveSimpleJumpintoIf(MachineBasicBlock *HeadMBB, 261 MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB, 262 MachineBasicBlock **LandMBBPtr); 263 void showImproveSimpleJumpintoIf(MachineBasicBlock *HeadMBB, 264 MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB, 265 MachineBasicBlock *LandMBB, bool Detail = false); 266 int cloneOnSideEntryTo(MachineBasicBlock *PreMBB, 267 MachineBasicBlock *SrcMBB, MachineBasicBlock *DstMBB); 268 void mergeSerialBlock(MachineBasicBlock *DstMBB, 269 MachineBasicBlock *SrcMBB); 270 271 void mergeIfthenelseBlock(MachineInstr *BranchMI, 272 MachineBasicBlock *MBB, MachineBasicBlock *TrueMBB, 273 MachineBasicBlock *FalseMBB, MachineBasicBlock *LandMBB); 274 void mergeLooplandBlock(MachineBasicBlock *DstMBB, 275 MachineBasicBlock *LandMBB); 276 void mergeLoopbreakBlock(MachineBasicBlock *ExitingMBB, 277 MachineBasicBlock *LandMBB); 278 void settleLoopcontBlock(MachineBasicBlock *ContingMBB, 279 MachineBasicBlock *ContMBB); 280 281 /// normalizeInfiniteLoopExit change 282 /// B1: 283 /// uncond_br LoopHeader 284 /// 285 /// to 286 /// B1: 287 /// cond_br 1 LoopHeader dummyExit 288 /// and return the newly added dummy exit block 289 MachineBasicBlock *normalizeInfiniteLoopExit(MachineLoop *LoopRep); 290 void removeUnconditionalBranch(MachineBasicBlock *MBB); 291 292 /// Remove duplicate branches instructions in a block. 293 /// For instance 294 /// B0: 295 /// cond_br X B1 B2 296 /// cond_br X B1 B2 297 /// is transformed to 298 /// B0: 299 /// cond_br X B1 B2 300 void removeRedundantConditionalBranch(MachineBasicBlock *MBB); 301 302 void addDummyExitBlock(SmallVectorImpl<MachineBasicBlock *> &RetMBB); 303 void removeSuccessor(MachineBasicBlock *MBB); 304 MachineBasicBlock *cloneBlockForPredecessor(MachineBasicBlock *MBB, 305 MachineBasicBlock *PredMBB); 306 void migrateInstruction(MachineBasicBlock *SrcMBB, 307 MachineBasicBlock *DstMBB, MachineBasicBlock::iterator I); 308 void recordSccnum(MachineBasicBlock *MBB, int SCCNum); 309 void retireBlock(MachineBasicBlock *MBB); 310 311 private: 312 MBBInfoMap BlockInfoMap; 313 LoopLandInfoMap LLInfoMap; 314 std::map<MachineLoop *, bool> Visited; 315 MachineFunction *FuncRep; 316 SmallVector<MachineBasicBlock *, DEFAULT_VEC_SLOTS> OrderedBlks; 317 }; 318 319 } // end anonymous namespace 320 321 char R600MachineCFGStructurizer::ID = 0; 322 323 int R600MachineCFGStructurizer::getSCCNum(MachineBasicBlock *MBB) const { 324 MBBInfoMap::const_iterator It = BlockInfoMap.find(MBB); 325 if (It == BlockInfoMap.end()) 326 return INVALIDSCCNUM; 327 return (*It).second->SccNum; 328 } 329 330 MachineBasicBlock *R600MachineCFGStructurizer::getLoopLandInfo(MachineLoop *LoopRep) 331 const { 332 LoopLandInfoMap::const_iterator It = LLInfoMap.find(LoopRep); 333 if (It == LLInfoMap.end()) 334 return nullptr; 335 return (*It).second; 336 } 337 338 bool R600MachineCFGStructurizer::hasBackEdge(MachineBasicBlock *MBB) const { 339 MachineLoop *LoopRep = MLI->getLoopFor(MBB); 340 if (!LoopRep) 341 return false; 342 MachineBasicBlock *LoopHeader = LoopRep->getHeader(); 343 return MBB->isSuccessor(LoopHeader); 344 } 345 346 bool R600MachineCFGStructurizer::isRetiredBlock(MachineBasicBlock *MBB) const { 347 MBBInfoMap::const_iterator It = BlockInfoMap.find(MBB); 348 if (It == BlockInfoMap.end()) 349 return false; 350 return (*It).second->IsRetired; 351 } 352 353 bool R600MachineCFGStructurizer::isActiveLoophead(MachineBasicBlock *MBB) const { 354 MachineLoop *LoopRep = MLI->getLoopFor(MBB); 355 while (LoopRep && LoopRep->getHeader() == MBB) { 356 MachineBasicBlock *LoopLand = getLoopLandInfo(LoopRep); 357 if(!LoopLand) 358 return true; 359 if (!isRetiredBlock(LoopLand)) 360 return true; 361 LoopRep = LoopRep->getParentLoop(); 362 } 363 return false; 364 } 365 366 R600MachineCFGStructurizer::PathToKind R600MachineCFGStructurizer::singlePathTo( 367 MachineBasicBlock *SrcMBB, MachineBasicBlock *DstMBB, 368 bool AllowSideEntry) const { 369 assert(DstMBB); 370 if (SrcMBB == DstMBB) 371 return SinglePath_InPath; 372 while (SrcMBB && SrcMBB->succ_size() == 1) { 373 SrcMBB = *SrcMBB->succ_begin(); 374 if (SrcMBB == DstMBB) 375 return SinglePath_InPath; 376 if (!AllowSideEntry && SrcMBB->pred_size() > 1) 377 return Not_SinglePath; 378 } 379 if (SrcMBB && SrcMBB->succ_size()==0) 380 return SinglePath_NotInPath; 381 return Not_SinglePath; 382 } 383 384 int R600MachineCFGStructurizer::countActiveBlock(MBBVector::const_iterator It, 385 MBBVector::const_iterator E) const { 386 int Count = 0; 387 while (It != E) { 388 if (!isRetiredBlock(*It)) 389 ++Count; 390 ++It; 391 } 392 return Count; 393 } 394 395 bool R600MachineCFGStructurizer::needMigrateBlock(MachineBasicBlock *MBB) const { 396 unsigned BlockSizeThreshold = 30; 397 unsigned CloneInstrThreshold = 100; 398 bool MultiplePreds = MBB && (MBB->pred_size() > 1); 399 400 if(!MultiplePreds) 401 return false; 402 unsigned BlkSize = MBB->size(); 403 return ((BlkSize > BlockSizeThreshold) && 404 (BlkSize * (MBB->pred_size() - 1) > CloneInstrThreshold)); 405 } 406 407 void R600MachineCFGStructurizer::reversePredicateSetter( 408 MachineBasicBlock::iterator I, MachineBasicBlock &MBB) { 409 assert(I.isValid() && "Expected valid iterator"); 410 for (;; --I) { 411 if (I == MBB.end()) 412 continue; 413 if (I->getOpcode() == R600::PRED_X) { 414 switch (I->getOperand(2).getImm()) { 415 case R600::PRED_SETE_INT: 416 I->getOperand(2).setImm(R600::PRED_SETNE_INT); 417 return; 418 case R600::PRED_SETNE_INT: 419 I->getOperand(2).setImm(R600::PRED_SETE_INT); 420 return; 421 case R600::PRED_SETE: 422 I->getOperand(2).setImm(R600::PRED_SETNE); 423 return; 424 case R600::PRED_SETNE: 425 I->getOperand(2).setImm(R600::PRED_SETE); 426 return; 427 default: 428 llvm_unreachable("PRED_X Opcode invalid!"); 429 } 430 } 431 } 432 } 433 434 void R600MachineCFGStructurizer::insertInstrEnd(MachineBasicBlock *MBB, 435 int NewOpcode, const DebugLoc &DL) { 436 MachineInstr *MI = 437 MBB->getParent()->CreateMachineInstr(TII->get(NewOpcode), DL); 438 MBB->push_back(MI); 439 //assume the instruction doesn't take any reg operand ... 440 SHOWNEWINSTR(MI); 441 } 442 443 MachineInstr *R600MachineCFGStructurizer::insertInstrBefore(MachineBasicBlock *MBB, 444 int NewOpcode, 445 const DebugLoc &DL) { 446 MachineInstr *MI = 447 MBB->getParent()->CreateMachineInstr(TII->get(NewOpcode), DL); 448 if (!MBB->empty()) 449 MBB->insert(MBB->begin(), MI); 450 else 451 MBB->push_back(MI); 452 SHOWNEWINSTR(MI); 453 return MI; 454 } 455 456 MachineInstr *R600MachineCFGStructurizer::insertInstrBefore( 457 MachineBasicBlock::iterator I, int NewOpcode) { 458 MachineInstr *OldMI = &(*I); 459 MachineBasicBlock *MBB = OldMI->getParent(); 460 MachineInstr *NewMBB = 461 MBB->getParent()->CreateMachineInstr(TII->get(NewOpcode), DebugLoc()); 462 MBB->insert(I, NewMBB); 463 //assume the instruction doesn't take any reg operand ... 464 SHOWNEWINSTR(NewMBB); 465 return NewMBB; 466 } 467 468 void R600MachineCFGStructurizer::insertCondBranchBefore( 469 MachineBasicBlock::iterator I, int NewOpcode, const DebugLoc &DL) { 470 MachineInstr *OldMI = &(*I); 471 MachineBasicBlock *MBB = OldMI->getParent(); 472 MachineFunction *MF = MBB->getParent(); 473 MachineInstr *NewMI = MF->CreateMachineInstr(TII->get(NewOpcode), DL); 474 MBB->insert(I, NewMI); 475 MachineInstrBuilder MIB(*MF, NewMI); 476 MIB.addReg(OldMI->getOperand(1).getReg(), false); 477 SHOWNEWINSTR(NewMI); 478 //erase later oldInstr->eraseFromParent(); 479 } 480 481 void R600MachineCFGStructurizer::insertCondBranchBefore( 482 MachineBasicBlock *blk, MachineBasicBlock::iterator I, int NewOpcode, 483 int RegNum, const DebugLoc &DL) { 484 MachineFunction *MF = blk->getParent(); 485 MachineInstr *NewInstr = MF->CreateMachineInstr(TII->get(NewOpcode), DL); 486 //insert before 487 blk->insert(I, NewInstr); 488 MachineInstrBuilder(*MF, NewInstr).addReg(RegNum, false); 489 SHOWNEWINSTR(NewInstr); 490 } 491 492 int R600MachineCFGStructurizer::getBranchNzeroOpcode(int OldOpcode) { 493 switch(OldOpcode) { 494 case R600::JUMP_COND: 495 case R600::JUMP: return R600::IF_PREDICATE_SET; 496 case R600::BRANCH_COND_i32: 497 case R600::BRANCH_COND_f32: return R600::IF_LOGICALNZ_f32; 498 default: llvm_unreachable("internal error"); 499 } 500 return -1; 501 } 502 503 int R600MachineCFGStructurizer::getBranchZeroOpcode(int OldOpcode) { 504 switch(OldOpcode) { 505 case R600::JUMP_COND: 506 case R600::JUMP: return R600::IF_PREDICATE_SET; 507 case R600::BRANCH_COND_i32: 508 case R600::BRANCH_COND_f32: return R600::IF_LOGICALZ_f32; 509 default: llvm_unreachable("internal error"); 510 } 511 return -1; 512 } 513 514 int R600MachineCFGStructurizer::getContinueNzeroOpcode(int OldOpcode) { 515 switch(OldOpcode) { 516 case R600::JUMP_COND: 517 case R600::JUMP: return R600::CONTINUE_LOGICALNZ_i32; 518 default: llvm_unreachable("internal error"); 519 } 520 return -1; 521 } 522 523 int R600MachineCFGStructurizer::getContinueZeroOpcode(int OldOpcode) { 524 switch(OldOpcode) { 525 case R600::JUMP_COND: 526 case R600::JUMP: return R600::CONTINUE_LOGICALZ_i32; 527 default: llvm_unreachable("internal error"); 528 } 529 return -1; 530 } 531 532 MachineBasicBlock *R600MachineCFGStructurizer::getTrueBranch(MachineInstr *MI) { 533 return MI->getOperand(0).getMBB(); 534 } 535 536 void R600MachineCFGStructurizer::setTrueBranch(MachineInstr *MI, 537 MachineBasicBlock *MBB) { 538 MI->getOperand(0).setMBB(MBB); 539 } 540 541 MachineBasicBlock * 542 R600MachineCFGStructurizer::getFalseBranch(MachineBasicBlock *MBB, 543 MachineInstr *MI) { 544 assert(MBB->succ_size() == 2); 545 MachineBasicBlock *TrueBranch = getTrueBranch(MI); 546 MachineBasicBlock::succ_iterator It = MBB->succ_begin(); 547 MachineBasicBlock::succ_iterator Next = It; 548 ++Next; 549 return (*It == TrueBranch) ? *Next : *It; 550 } 551 552 bool R600MachineCFGStructurizer::isCondBranch(MachineInstr *MI) { 553 switch (MI->getOpcode()) { 554 case R600::JUMP_COND: 555 case R600::BRANCH_COND_i32: 556 case R600::BRANCH_COND_f32: return true; 557 default: 558 return false; 559 } 560 return false; 561 } 562 563 bool R600MachineCFGStructurizer::isUncondBranch(MachineInstr *MI) { 564 switch (MI->getOpcode()) { 565 case R600::JUMP: 566 case R600::BRANCH: 567 return true; 568 default: 569 return false; 570 } 571 return false; 572 } 573 574 DebugLoc R600MachineCFGStructurizer::getLastDebugLocInBB(MachineBasicBlock *MBB) { 575 //get DebugLoc from the first MachineBasicBlock instruction with debug info 576 DebugLoc DL; 577 for (MachineInstr &MI : *MBB) 578 if (MI.getDebugLoc()) 579 DL = MI.getDebugLoc(); 580 return DL; 581 } 582 583 MachineInstr *R600MachineCFGStructurizer::getNormalBlockBranchInstr( 584 MachineBasicBlock *MBB) { 585 MachineBasicBlock::reverse_iterator It = MBB->rbegin(); 586 MachineInstr *MI = &*It; 587 if (MI && (isCondBranch(MI) || isUncondBranch(MI))) 588 return MI; 589 return nullptr; 590 } 591 592 MachineInstr *R600MachineCFGStructurizer::getLoopendBlockBranchInstr( 593 MachineBasicBlock *MBB) { 594 for (MachineBasicBlock::reverse_iterator It = MBB->rbegin(), E = MBB->rend(); 595 It != E; ++It) { 596 // FIXME: Simplify 597 MachineInstr *MI = &*It; 598 if (MI) { 599 if (isCondBranch(MI) || isUncondBranch(MI)) 600 return MI; 601 else if (!TII->isMov(MI->getOpcode())) 602 break; 603 } 604 } 605 return nullptr; 606 } 607 608 MachineInstr *R600MachineCFGStructurizer::getReturnInstr(MachineBasicBlock *MBB) { 609 MachineBasicBlock::reverse_iterator It = MBB->rbegin(); 610 if (It != MBB->rend()) { 611 MachineInstr *instr = &(*It); 612 if (instr->getOpcode() == R600::RETURN) 613 return instr; 614 } 615 return nullptr; 616 } 617 618 bool R600MachineCFGStructurizer::isReturnBlock(MachineBasicBlock *MBB) { 619 MachineInstr *MI = getReturnInstr(MBB); 620 bool IsReturn = MBB->succ_empty(); 621 if (MI) 622 assert(IsReturn); 623 else if (IsReturn) 624 LLVM_DEBUG(dbgs() << "BB" << MBB->getNumber() 625 << " is return block without RETURN instr\n";); 626 return IsReturn; 627 } 628 629 void R600MachineCFGStructurizer::cloneSuccessorList(MachineBasicBlock *DstMBB, 630 MachineBasicBlock *SrcMBB) { 631 for (MachineBasicBlock *Succ : SrcMBB->successors()) 632 DstMBB->addSuccessor(Succ); // *iter's predecessor is also taken care of 633 } 634 635 MachineBasicBlock *R600MachineCFGStructurizer::clone(MachineBasicBlock *MBB) { 636 MachineFunction *Func = MBB->getParent(); 637 MachineBasicBlock *NewMBB = Func->CreateMachineBasicBlock(); 638 Func->push_back(NewMBB); //insert to function 639 for (const MachineInstr &It : *MBB) 640 NewMBB->push_back(Func->CloneMachineInstr(&It)); 641 return NewMBB; 642 } 643 644 void R600MachineCFGStructurizer::replaceInstrUseOfBlockWith( 645 MachineBasicBlock *SrcMBB, MachineBasicBlock *OldMBB, 646 MachineBasicBlock *NewBlk) { 647 MachineInstr *BranchMI = getLoopendBlockBranchInstr(SrcMBB); 648 if (BranchMI && isCondBranch(BranchMI) && 649 getTrueBranch(BranchMI) == OldMBB) 650 setTrueBranch(BranchMI, NewBlk); 651 } 652 653 void R600MachineCFGStructurizer::wrapup(MachineBasicBlock *MBB) { 654 assert((!MBB->getParent()->getJumpTableInfo() 655 || MBB->getParent()->getJumpTableInfo()->isEmpty()) 656 && "found a jump table"); 657 658 //collect continue right before endloop 659 SmallVector<MachineInstr *, DEFAULT_VEC_SLOTS> ContInstr; 660 MachineBasicBlock::iterator Pre = MBB->begin(); 661 MachineBasicBlock::iterator E = MBB->end(); 662 MachineBasicBlock::iterator It = Pre; 663 while (It != E) { 664 if (Pre->getOpcode() == R600::CONTINUE 665 && It->getOpcode() == R600::ENDLOOP) 666 ContInstr.push_back(&*Pre); 667 Pre = It; 668 ++It; 669 } 670 671 //delete continue right before endloop 672 for (unsigned i = 0; i < ContInstr.size(); ++i) 673 ContInstr[i]->eraseFromParent(); 674 675 // TODO to fix up jump table so later phase won't be confused. if 676 // (jumpTableInfo->isEmpty() == false) { need to clean the jump table, but 677 // there isn't such an interface yet. alternatively, replace all the other 678 // blocks in the jump table with the entryBlk //} 679 } 680 681 bool R600MachineCFGStructurizer::prepare() { 682 bool Changed = false; 683 684 //FIXME: if not reducible flow graph, make it so ??? 685 686 LLVM_DEBUG(dbgs() << "R600MachineCFGStructurizer::prepare\n";); 687 688 orderBlocks(FuncRep); 689 690 SmallVector<MachineBasicBlock *, DEFAULT_VEC_SLOTS> RetBlks; 691 692 // Add an ExitBlk to loop that don't have one 693 for (MachineLoop *LoopRep : *MLI) { 694 MBBVector ExitingMBBs; 695 LoopRep->getExitingBlocks(ExitingMBBs); 696 697 if (ExitingMBBs.size() == 0) { 698 MachineBasicBlock* DummyExitBlk = normalizeInfiniteLoopExit(LoopRep); 699 if (DummyExitBlk) 700 RetBlks.push_back(DummyExitBlk); 701 } 702 } 703 704 // Remove unconditional branch instr. 705 // Add dummy exit block iff there are multiple returns. 706 for (MachineBasicBlock *MBB : OrderedBlks) { 707 removeUnconditionalBranch(MBB); 708 removeRedundantConditionalBranch(MBB); 709 if (isReturnBlock(MBB)) { 710 RetBlks.push_back(MBB); 711 } 712 assert(MBB->succ_size() <= 2); 713 } 714 715 if (RetBlks.size() >= 2) { 716 addDummyExitBlock(RetBlks); 717 Changed = true; 718 } 719 720 return Changed; 721 } 722 723 bool R600MachineCFGStructurizer::run() { 724 //Assume reducible CFG... 725 LLVM_DEBUG(dbgs() << "R600MachineCFGStructurizer::run\n"); 726 727 #ifdef STRESSTEST 728 //Use the worse block ordering to test the algorithm. 729 ReverseVector(orderedBlks); 730 #endif 731 732 LLVM_DEBUG(dbgs() << "Ordered blocks:\n"; printOrderedBlocks();); 733 int NumIter = 0; 734 bool Finish = false; 735 MachineBasicBlock *MBB; 736 bool MakeProgress = false; 737 int NumRemainedBlk = countActiveBlock(OrderedBlks.begin(), 738 OrderedBlks.end()); 739 740 do { 741 ++NumIter; 742 LLVM_DEBUG(dbgs() << "numIter = " << NumIter 743 << ", numRemaintedBlk = " << NumRemainedBlk << "\n";); 744 745 SmallVectorImpl<MachineBasicBlock *>::const_iterator It = 746 OrderedBlks.begin(); 747 SmallVectorImpl<MachineBasicBlock *>::const_iterator E = 748 OrderedBlks.end(); 749 750 SmallVectorImpl<MachineBasicBlock *>::const_iterator SccBeginIter = 751 It; 752 MachineBasicBlock *SccBeginMBB = nullptr; 753 int SccNumBlk = 0; // The number of active blocks, init to a 754 // maximum possible number. 755 int SccNumIter; // Number of iteration in this SCC. 756 757 while (It != E) { 758 MBB = *It; 759 760 if (!SccBeginMBB) { 761 SccBeginIter = It; 762 SccBeginMBB = MBB; 763 SccNumIter = 0; 764 SccNumBlk = NumRemainedBlk; // Init to maximum possible number. 765 LLVM_DEBUG(dbgs() << "start processing SCC" << getSCCNum(SccBeginMBB); 766 dbgs() << "\n";); 767 } 768 769 if (!isRetiredBlock(MBB)) 770 patternMatch(MBB); 771 772 ++It; 773 774 bool ContNextScc = true; 775 if (It == E 776 || getSCCNum(SccBeginMBB) != getSCCNum(*It)) { 777 // Just finish one scc. 778 ++SccNumIter; 779 int sccRemainedNumBlk = countActiveBlock(SccBeginIter, It); 780 if (sccRemainedNumBlk != 1 && sccRemainedNumBlk >= SccNumBlk) { 781 LLVM_DEBUG(dbgs() << "Can't reduce SCC " << getSCCNum(MBB) 782 << ", sccNumIter = " << SccNumIter; 783 dbgs() << "doesn't make any progress\n";); 784 ContNextScc = true; 785 } else if (sccRemainedNumBlk != 1 && sccRemainedNumBlk < SccNumBlk) { 786 SccNumBlk = sccRemainedNumBlk; 787 It = SccBeginIter; 788 ContNextScc = false; 789 LLVM_DEBUG(dbgs() << "repeat processing SCC" << getSCCNum(MBB) 790 << "sccNumIter = " << SccNumIter << '\n';); 791 } else { 792 // Finish the current scc. 793 ContNextScc = true; 794 } 795 } else { 796 // Continue on next component in the current scc. 797 ContNextScc = false; 798 } 799 800 if (ContNextScc) 801 SccBeginMBB = nullptr; 802 } //while, "one iteration" over the function. 803 804 MachineBasicBlock *EntryMBB = 805 *GraphTraits<MachineFunction *>::nodes_begin(FuncRep); 806 if (EntryMBB->succ_empty()) { 807 Finish = true; 808 LLVM_DEBUG(dbgs() << "Reduce to one block\n";); 809 } else { 810 int NewnumRemainedBlk 811 = countActiveBlock(OrderedBlks.begin(), OrderedBlks.end()); 812 // consider cloned blocks ?? 813 if (NewnumRemainedBlk == 1 || NewnumRemainedBlk < NumRemainedBlk) { 814 MakeProgress = true; 815 NumRemainedBlk = NewnumRemainedBlk; 816 } else { 817 MakeProgress = false; 818 LLVM_DEBUG(dbgs() << "No progress\n";); 819 } 820 } 821 } while (!Finish && MakeProgress); 822 823 // Misc wrap up to maintain the consistency of the Function representation. 824 wrapup(*GraphTraits<MachineFunction *>::nodes_begin(FuncRep)); 825 826 // Detach retired Block, release memory. 827 for (auto &It : BlockInfoMap) { 828 if (It.second && It.second->IsRetired) { 829 assert((It.first)->getNumber() != -1); 830 LLVM_DEBUG(dbgs() << "Erase BB" << (It.first)->getNumber() << "\n";); 831 It.first->eraseFromParent(); // Remove from the parent Function. 832 } 833 delete It.second; 834 } 835 BlockInfoMap.clear(); 836 LLInfoMap.clear(); 837 838 if (!Finish) { 839 LLVM_DEBUG(FuncRep->viewCFG()); 840 report_fatal_error("IRREDUCIBLE_CFG"); 841 } 842 843 return true; 844 } 845 846 void R600MachineCFGStructurizer::orderBlocks(MachineFunction *MF) { 847 int SccNum = 0; 848 for (scc_iterator<MachineFunction *> It = scc_begin(MF); !It.isAtEnd(); 849 ++It, ++SccNum) { 850 const std::vector<MachineBasicBlock *> &SccNext = *It; 851 for (MachineBasicBlock *MBB : SccNext) { 852 OrderedBlks.push_back(MBB); 853 recordSccnum(MBB, SccNum); 854 } 855 } 856 857 // walk through all the block in func to check for unreachable 858 for (auto *MBB : nodes(MF)) { 859 SccNum = getSCCNum(MBB); 860 if (SccNum == INVALIDSCCNUM) 861 dbgs() << "unreachable block BB" << MBB->getNumber() << "\n"; 862 } 863 } 864 865 int R600MachineCFGStructurizer::patternMatch(MachineBasicBlock *MBB) { 866 int NumMatch = 0; 867 int CurMatch; 868 869 LLVM_DEBUG(dbgs() << "Begin patternMatch BB" << MBB->getNumber() << "\n";); 870 871 while ((CurMatch = patternMatchGroup(MBB)) > 0) 872 NumMatch += CurMatch; 873 874 LLVM_DEBUG(dbgs() << "End patternMatch BB" << MBB->getNumber() 875 << ", numMatch = " << NumMatch << "\n";); 876 877 return NumMatch; 878 } 879 880 int R600MachineCFGStructurizer::patternMatchGroup(MachineBasicBlock *MBB) { 881 int NumMatch = 0; 882 NumMatch += loopendPatternMatch(); 883 NumMatch += serialPatternMatch(MBB); 884 NumMatch += ifPatternMatch(MBB); 885 return NumMatch; 886 } 887 888 int R600MachineCFGStructurizer::serialPatternMatch(MachineBasicBlock *MBB) { 889 if (MBB->succ_size() != 1) 890 return 0; 891 892 MachineBasicBlock *childBlk = *MBB->succ_begin(); 893 if (childBlk->pred_size() != 1 || isActiveLoophead(childBlk)) 894 return 0; 895 896 mergeSerialBlock(MBB, childBlk); 897 ++numSerialPatternMatch; 898 return 1; 899 } 900 901 int R600MachineCFGStructurizer::ifPatternMatch(MachineBasicBlock *MBB) { 902 //two edges 903 if (MBB->succ_size() != 2) 904 return 0; 905 if (hasBackEdge(MBB)) 906 return 0; 907 MachineInstr *BranchMI = getNormalBlockBranchInstr(MBB); 908 if (!BranchMI) 909 return 0; 910 911 assert(isCondBranch(BranchMI)); 912 int NumMatch = 0; 913 914 MachineBasicBlock *TrueMBB = getTrueBranch(BranchMI); 915 NumMatch += serialPatternMatch(TrueMBB); 916 NumMatch += ifPatternMatch(TrueMBB); 917 MachineBasicBlock *FalseMBB = getFalseBranch(MBB, BranchMI); 918 NumMatch += serialPatternMatch(FalseMBB); 919 NumMatch += ifPatternMatch(FalseMBB); 920 MachineBasicBlock *LandBlk; 921 int Cloned = 0; 922 923 assert (!TrueMBB->succ_empty() || !FalseMBB->succ_empty()); 924 // TODO: Simplify 925 if (TrueMBB->succ_size() == 1 && FalseMBB->succ_size() == 1 926 && *TrueMBB->succ_begin() == *FalseMBB->succ_begin()) { 927 // Diamond pattern 928 LandBlk = *TrueMBB->succ_begin(); 929 } else if (TrueMBB->succ_size() == 1 && *TrueMBB->succ_begin() == FalseMBB) { 930 // Triangle pattern, false is empty 931 LandBlk = FalseMBB; 932 FalseMBB = nullptr; 933 } else if (FalseMBB->succ_size() == 1 934 && *FalseMBB->succ_begin() == TrueMBB) { 935 // Triangle pattern, true is empty 936 // We reverse the predicate to make a triangle, empty false pattern; 937 std::swap(TrueMBB, FalseMBB); 938 reversePredicateSetter(MBB->end(), *MBB); 939 LandBlk = FalseMBB; 940 FalseMBB = nullptr; 941 } else if (FalseMBB->succ_size() == 1 942 && isSameloopDetachedContbreak(TrueMBB, FalseMBB)) { 943 LandBlk = *FalseMBB->succ_begin(); 944 } else if (TrueMBB->succ_size() == 1 945 && isSameloopDetachedContbreak(FalseMBB, TrueMBB)) { 946 LandBlk = *TrueMBB->succ_begin(); 947 } else { 948 return NumMatch + handleJumpintoIf(MBB, TrueMBB, FalseMBB); 949 } 950 951 // improveSimpleJumpinfoIf can handle the case where landBlk == NULL but the 952 // new BB created for landBlk==NULL may introduce new challenge to the 953 // reduction process. 954 if (LandBlk && 955 ((TrueMBB && TrueMBB->pred_size() > 1) 956 || (FalseMBB && FalseMBB->pred_size() > 1))) { 957 Cloned += improveSimpleJumpintoIf(MBB, TrueMBB, FalseMBB, &LandBlk); 958 } 959 960 if (TrueMBB && TrueMBB->pred_size() > 1) { 961 TrueMBB = cloneBlockForPredecessor(TrueMBB, MBB); 962 ++Cloned; 963 } 964 965 if (FalseMBB && FalseMBB->pred_size() > 1) { 966 FalseMBB = cloneBlockForPredecessor(FalseMBB, MBB); 967 ++Cloned; 968 } 969 970 mergeIfthenelseBlock(BranchMI, MBB, TrueMBB, FalseMBB, LandBlk); 971 972 ++numIfPatternMatch; 973 974 numClonedBlock += Cloned; 975 976 return 1 + Cloned + NumMatch; 977 } 978 979 int R600MachineCFGStructurizer::loopendPatternMatch() { 980 std::deque<MachineLoop *> NestedLoops; 981 for (auto &It: *MLI) 982 for (MachineLoop *ML : depth_first(It)) 983 NestedLoops.push_front(ML); 984 985 if (NestedLoops.empty()) 986 return 0; 987 988 // Process nested loop outside->inside (we did push_front), 989 // so "continue" to a outside loop won't be mistaken as "break" 990 // of the current loop. 991 int Num = 0; 992 for (MachineLoop *ExaminedLoop : NestedLoops) { 993 if (ExaminedLoop->getNumBlocks() == 0 || Visited[ExaminedLoop]) 994 continue; 995 LLVM_DEBUG(dbgs() << "Processing:\n"; ExaminedLoop->dump();); 996 int NumBreak = mergeLoop(ExaminedLoop); 997 if (NumBreak == -1) 998 break; 999 Num += NumBreak; 1000 } 1001 return Num; 1002 } 1003 1004 int R600MachineCFGStructurizer::mergeLoop(MachineLoop *LoopRep) { 1005 MachineBasicBlock *LoopHeader = LoopRep->getHeader(); 1006 MBBVector ExitingMBBs; 1007 LoopRep->getExitingBlocks(ExitingMBBs); 1008 assert(!ExitingMBBs.empty() && "Infinite Loop not supported"); 1009 LLVM_DEBUG(dbgs() << "Loop has " << ExitingMBBs.size() 1010 << " exiting blocks\n";); 1011 // We assume a single ExitBlk 1012 MBBVector ExitBlks; 1013 LoopRep->getExitBlocks(ExitBlks); 1014 SmallPtrSet<MachineBasicBlock *, 2> ExitBlkSet; 1015 for (unsigned i = 0, e = ExitBlks.size(); i < e; ++i) 1016 ExitBlkSet.insert(ExitBlks[i]); 1017 assert(ExitBlkSet.size() == 1); 1018 MachineBasicBlock *ExitBlk = *ExitBlks.begin(); 1019 assert(ExitBlk && "Loop has several exit block"); 1020 MBBVector LatchBlks; 1021 for (auto *LB : inverse_children<MachineBasicBlock*>(LoopHeader)) 1022 if (LoopRep->contains(LB)) 1023 LatchBlks.push_back(LB); 1024 1025 for (unsigned i = 0, e = ExitingMBBs.size(); i < e; ++i) 1026 mergeLoopbreakBlock(ExitingMBBs[i], ExitBlk); 1027 for (unsigned i = 0, e = LatchBlks.size(); i < e; ++i) 1028 settleLoopcontBlock(LatchBlks[i], LoopHeader); 1029 int Match = 0; 1030 do { 1031 Match = 0; 1032 Match += serialPatternMatch(LoopHeader); 1033 Match += ifPatternMatch(LoopHeader); 1034 } while (Match > 0); 1035 mergeLooplandBlock(LoopHeader, ExitBlk); 1036 MachineLoop *ParentLoop = LoopRep->getParentLoop(); 1037 if (ParentLoop) 1038 MLI->changeLoopFor(LoopHeader, ParentLoop); 1039 else 1040 MLI->removeBlock(LoopHeader); 1041 Visited[LoopRep] = true; 1042 return 1; 1043 } 1044 1045 bool R600MachineCFGStructurizer::isSameloopDetachedContbreak( 1046 MachineBasicBlock *Src1MBB, MachineBasicBlock *Src2MBB) { 1047 if (Src1MBB->succ_empty()) { 1048 MachineLoop *LoopRep = MLI->getLoopFor(Src1MBB); 1049 if (LoopRep&& LoopRep == MLI->getLoopFor(Src2MBB)) { 1050 MachineBasicBlock *&TheEntry = LLInfoMap[LoopRep]; 1051 if (TheEntry) { 1052 LLVM_DEBUG(dbgs() << "isLoopContBreakBlock yes src1 = BB" 1053 << Src1MBB->getNumber() << " src2 = BB" 1054 << Src2MBB->getNumber() << "\n";); 1055 return true; 1056 } 1057 } 1058 } 1059 return false; 1060 } 1061 1062 int R600MachineCFGStructurizer::handleJumpintoIf(MachineBasicBlock *HeadMBB, 1063 MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB) { 1064 int Num = handleJumpintoIfImp(HeadMBB, TrueMBB, FalseMBB); 1065 if (Num == 0) { 1066 LLVM_DEBUG(dbgs() << "handleJumpintoIf swap trueBlk and FalseBlk" 1067 << "\n";); 1068 Num = handleJumpintoIfImp(HeadMBB, FalseMBB, TrueMBB); 1069 } 1070 return Num; 1071 } 1072 1073 int R600MachineCFGStructurizer::handleJumpintoIfImp(MachineBasicBlock *HeadMBB, 1074 MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB) { 1075 int Num = 0; 1076 MachineBasicBlock *DownBlk; 1077 1078 //trueBlk could be the common post dominator 1079 DownBlk = TrueMBB; 1080 1081 LLVM_DEBUG(dbgs() << "handleJumpintoIfImp head = BB" << HeadMBB->getNumber() 1082 << " true = BB" << TrueMBB->getNumber() 1083 << ", numSucc=" << TrueMBB->succ_size() << " false = BB" 1084 << FalseMBB->getNumber() << "\n";); 1085 1086 while (DownBlk) { 1087 LLVM_DEBUG(dbgs() << "check down = BB" << DownBlk->getNumber();); 1088 1089 if (singlePathTo(FalseMBB, DownBlk) == SinglePath_InPath) { 1090 LLVM_DEBUG(dbgs() << " working\n";); 1091 1092 Num += cloneOnSideEntryTo(HeadMBB, TrueMBB, DownBlk); 1093 Num += cloneOnSideEntryTo(HeadMBB, FalseMBB, DownBlk); 1094 1095 numClonedBlock += Num; 1096 Num += serialPatternMatch(*HeadMBB->succ_begin()); 1097 Num += serialPatternMatch(*std::next(HeadMBB->succ_begin())); 1098 Num += ifPatternMatch(HeadMBB); 1099 assert(Num > 0); 1100 1101 break; 1102 } 1103 LLVM_DEBUG(dbgs() << " not working\n";); 1104 DownBlk = (DownBlk->succ_size() == 1) ? (*DownBlk->succ_begin()) : nullptr; 1105 } // walk down the postDomTree 1106 1107 return Num; 1108 } 1109 1110 #ifndef NDEBUG 1111 void R600MachineCFGStructurizer::showImproveSimpleJumpintoIf( 1112 MachineBasicBlock *HeadMBB, MachineBasicBlock *TrueMBB, 1113 MachineBasicBlock *FalseMBB, MachineBasicBlock *LandMBB, bool Detail) { 1114 dbgs() << "head = BB" << HeadMBB->getNumber() 1115 << " size = " << HeadMBB->size(); 1116 if (Detail) { 1117 dbgs() << "\n"; 1118 HeadMBB->print(dbgs()); 1119 dbgs() << "\n"; 1120 } 1121 1122 if (TrueMBB) { 1123 dbgs() << ", true = BB" << TrueMBB->getNumber() << " size = " 1124 << TrueMBB->size() << " numPred = " << TrueMBB->pred_size(); 1125 if (Detail) { 1126 dbgs() << "\n"; 1127 TrueMBB->print(dbgs()); 1128 dbgs() << "\n"; 1129 } 1130 } 1131 if (FalseMBB) { 1132 dbgs() << ", false = BB" << FalseMBB->getNumber() << " size = " 1133 << FalseMBB->size() << " numPred = " << FalseMBB->pred_size(); 1134 if (Detail) { 1135 dbgs() << "\n"; 1136 FalseMBB->print(dbgs()); 1137 dbgs() << "\n"; 1138 } 1139 } 1140 if (LandMBB) { 1141 dbgs() << ", land = BB" << LandMBB->getNumber() << " size = " 1142 << LandMBB->size() << " numPred = " << LandMBB->pred_size(); 1143 if (Detail) { 1144 dbgs() << "\n"; 1145 LandMBB->print(dbgs()); 1146 dbgs() << "\n"; 1147 } 1148 } 1149 1150 dbgs() << "\n"; 1151 } 1152 #endif 1153 1154 int R600MachineCFGStructurizer::improveSimpleJumpintoIf(MachineBasicBlock *HeadMBB, 1155 MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB, 1156 MachineBasicBlock **LandMBBPtr) { 1157 bool MigrateTrue = false; 1158 bool MigrateFalse = false; 1159 1160 MachineBasicBlock *LandBlk = *LandMBBPtr; 1161 1162 assert((!TrueMBB || TrueMBB->succ_size() <= 1) 1163 && (!FalseMBB || FalseMBB->succ_size() <= 1)); 1164 1165 if (TrueMBB == FalseMBB) 1166 return 0; 1167 1168 MigrateTrue = needMigrateBlock(TrueMBB); 1169 MigrateFalse = needMigrateBlock(FalseMBB); 1170 1171 if (!MigrateTrue && !MigrateFalse) 1172 return 0; 1173 1174 // If we need to migrate either trueBlk and falseBlk, migrate the rest that 1175 // have more than one predecessors. without doing this, its predecessor 1176 // rather than headBlk will have undefined value in initReg. 1177 if (!MigrateTrue && TrueMBB && TrueMBB->pred_size() > 1) 1178 MigrateTrue = true; 1179 if (!MigrateFalse && FalseMBB && FalseMBB->pred_size() > 1) 1180 MigrateFalse = true; 1181 1182 LLVM_DEBUG( 1183 dbgs() << "before improveSimpleJumpintoIf: "; 1184 showImproveSimpleJumpintoIf(HeadMBB, TrueMBB, FalseMBB, LandBlk, 0);); 1185 1186 // org: headBlk => if () {trueBlk} else {falseBlk} => landBlk 1187 // 1188 // new: headBlk => if () {initReg = 1; org trueBlk branch} else 1189 // {initReg = 0; org falseBlk branch } 1190 // => landBlk => if (initReg) {org trueBlk} else {org falseBlk} 1191 // => org landBlk 1192 // if landBlk->pred_size() > 2, put the about if-else inside 1193 // if (initReg !=2) {...} 1194 // 1195 // add initReg = initVal to headBlk 1196 1197 const TargetRegisterClass * I32RC = TRI->getCFGStructurizerRegClass(MVT::i32); 1198 if (!MigrateTrue || !MigrateFalse) { 1199 // XXX: We have an opportunity here to optimize the "branch into if" case 1200 // here. Branch into if looks like this: 1201 // entry 1202 // / | 1203 // diamond_head branch_from 1204 // / \ | 1205 // diamond_false diamond_true 1206 // \ / 1207 // done 1208 // 1209 // The diamond_head block begins the "if" and the diamond_true block 1210 // is the block being "branched into". 1211 // 1212 // If MigrateTrue is true, then TrueBB is the block being "branched into" 1213 // and if MigrateFalse is true, then FalseBB is the block being 1214 // "branched into" 1215 // 1216 // Here is the pseudo code for how I think the optimization should work: 1217 // 1. Insert MOV GPR0, 0 before the branch instruction in diamond_head. 1218 // 2. Insert MOV GPR0, 1 before the branch instruction in branch_from. 1219 // 3. Move the branch instruction from diamond_head into its own basic 1220 // block (new_block). 1221 // 4. Add an unconditional branch from diamond_head to new_block 1222 // 5. Replace the branch instruction in branch_from with an unconditional 1223 // branch to new_block. If branch_from has multiple predecessors, then 1224 // we need to replace the True/False block in the branch 1225 // instruction instead of replacing it. 1226 // 6. Change the condition of the branch instruction in new_block from 1227 // COND to (COND || GPR0) 1228 // 1229 // In order insert these MOV instruction, we will need to use the 1230 // RegisterScavenger. Usually liveness stops being tracked during 1231 // the late machine optimization passes, however if we implement 1232 // bool TargetRegisterInfo::requiresRegisterScavenging( 1233 // const MachineFunction &MF) 1234 // and have it return true, liveness will be tracked correctly 1235 // by generic optimization passes. We will also need to make sure that 1236 // all of our target-specific passes that run after regalloc and before 1237 // the CFGStructurizer track liveness and we will need to modify this pass 1238 // to correctly track liveness. 1239 // 1240 // After the above changes, the new CFG should look like this: 1241 // entry 1242 // / | 1243 // diamond_head branch_from 1244 // \ / 1245 // new_block 1246 // / | 1247 // diamond_false diamond_true 1248 // \ / 1249 // done 1250 // 1251 // Without this optimization, we are forced to duplicate the diamond_true 1252 // block and we will end up with a CFG like this: 1253 // 1254 // entry 1255 // / | 1256 // diamond_head branch_from 1257 // / \ | 1258 // diamond_false diamond_true diamond_true (duplicate) 1259 // \ / | 1260 // done --------------------| 1261 // 1262 // Duplicating diamond_true can be very costly especially if it has a 1263 // lot of instructions. 1264 return 0; 1265 } 1266 1267 int NumNewBlk = 0; 1268 1269 bool LandBlkHasOtherPred = (LandBlk->pred_size() > 2); 1270 1271 //insert R600::ENDIF to avoid special case "input landBlk == NULL" 1272 MachineBasicBlock::iterator I = insertInstrBefore(LandBlk, R600::ENDIF); 1273 1274 if (LandBlkHasOtherPred) { 1275 report_fatal_error("Extra register needed to handle CFG"); 1276 Register CmpResReg = 1277 HeadMBB->getParent()->getRegInfo().createVirtualRegister(I32RC); 1278 report_fatal_error("Extra compare instruction needed to handle CFG"); 1279 insertCondBranchBefore(LandBlk, I, R600::IF_PREDICATE_SET, 1280 CmpResReg, DebugLoc()); 1281 } 1282 1283 // XXX: We are running this after RA, so creating virtual registers will 1284 // cause an assertion failure in the PostRA scheduling pass. 1285 Register InitReg = 1286 HeadMBB->getParent()->getRegInfo().createVirtualRegister(I32RC); 1287 insertCondBranchBefore(LandBlk, I, R600::IF_PREDICATE_SET, InitReg, 1288 DebugLoc()); 1289 1290 if (MigrateTrue) { 1291 migrateInstruction(TrueMBB, LandBlk, I); 1292 // need to uncondionally insert the assignment to ensure a path from its 1293 // predecessor rather than headBlk has valid value in initReg if 1294 // (initVal != 1). 1295 report_fatal_error("Extra register needed to handle CFG"); 1296 } 1297 insertInstrBefore(I, R600::ELSE); 1298 1299 if (MigrateFalse) { 1300 migrateInstruction(FalseMBB, LandBlk, I); 1301 // need to uncondionally insert the assignment to ensure a path from its 1302 // predecessor rather than headBlk has valid value in initReg if 1303 // (initVal != 0) 1304 report_fatal_error("Extra register needed to handle CFG"); 1305 } 1306 1307 if (LandBlkHasOtherPred) { 1308 // add endif 1309 insertInstrBefore(I, R600::ENDIF); 1310 1311 // put initReg = 2 to other predecessors of landBlk 1312 for (MachineBasicBlock *MBB : LandBlk->predecessors()) 1313 if (MBB != TrueMBB && MBB != FalseMBB) 1314 report_fatal_error("Extra register needed to handle CFG"); 1315 } 1316 LLVM_DEBUG( 1317 dbgs() << "result from improveSimpleJumpintoIf: "; 1318 showImproveSimpleJumpintoIf(HeadMBB, TrueMBB, FalseMBB, LandBlk, 0);); 1319 1320 // update landBlk 1321 *LandMBBPtr = LandBlk; 1322 1323 return NumNewBlk; 1324 } 1325 1326 void R600MachineCFGStructurizer::mergeSerialBlock(MachineBasicBlock *DstMBB, 1327 MachineBasicBlock *SrcMBB) { 1328 LLVM_DEBUG(dbgs() << "serialPattern BB" << DstMBB->getNumber() << " <= BB" 1329 << SrcMBB->getNumber() << "\n";); 1330 DstMBB->splice(DstMBB->end(), SrcMBB, SrcMBB->begin(), SrcMBB->end()); 1331 1332 DstMBB->removeSuccessor(SrcMBB, true); 1333 cloneSuccessorList(DstMBB, SrcMBB); 1334 1335 removeSuccessor(SrcMBB); 1336 MLI->removeBlock(SrcMBB); 1337 retireBlock(SrcMBB); 1338 } 1339 1340 void R600MachineCFGStructurizer::mergeIfthenelseBlock(MachineInstr *BranchMI, 1341 MachineBasicBlock *MBB, MachineBasicBlock *TrueMBB, 1342 MachineBasicBlock *FalseMBB, MachineBasicBlock *LandMBB) { 1343 assert (TrueMBB); 1344 LLVM_DEBUG(dbgs() << "ifPattern BB" << MBB->getNumber(); dbgs() << "{ "; 1345 if (TrueMBB) { dbgs() << "BB" << TrueMBB->getNumber(); } dbgs() 1346 << " } else "; 1347 dbgs() << "{ "; if (FalseMBB) { 1348 dbgs() << "BB" << FalseMBB->getNumber(); 1349 } dbgs() << " }\n "; 1350 dbgs() << "landBlock: "; if (!LandMBB) { dbgs() << "NULL"; } else { 1351 dbgs() << "BB" << LandMBB->getNumber(); 1352 } dbgs() << "\n";); 1353 1354 int OldOpcode = BranchMI->getOpcode(); 1355 DebugLoc BranchDL = BranchMI->getDebugLoc(); 1356 1357 // transform to 1358 // if cond 1359 // trueBlk 1360 // else 1361 // falseBlk 1362 // endif 1363 // landBlk 1364 1365 MachineBasicBlock::iterator I = BranchMI; 1366 insertCondBranchBefore(I, getBranchNzeroOpcode(OldOpcode), 1367 BranchDL); 1368 1369 if (TrueMBB) { 1370 MBB->splice(I, TrueMBB, TrueMBB->begin(), TrueMBB->end()); 1371 MBB->removeSuccessor(TrueMBB, true); 1372 if (LandMBB && TrueMBB->succ_size()!=0) 1373 TrueMBB->removeSuccessor(LandMBB, true); 1374 retireBlock(TrueMBB); 1375 MLI->removeBlock(TrueMBB); 1376 } 1377 1378 if (FalseMBB) { 1379 insertInstrBefore(I, R600::ELSE); 1380 MBB->splice(I, FalseMBB, FalseMBB->begin(), 1381 FalseMBB->end()); 1382 MBB->removeSuccessor(FalseMBB, true); 1383 if (LandMBB && !FalseMBB->succ_empty()) 1384 FalseMBB->removeSuccessor(LandMBB, true); 1385 retireBlock(FalseMBB); 1386 MLI->removeBlock(FalseMBB); 1387 } 1388 insertInstrBefore(I, R600::ENDIF); 1389 1390 BranchMI->eraseFromParent(); 1391 1392 if (LandMBB && TrueMBB && FalseMBB) 1393 MBB->addSuccessor(LandMBB); 1394 } 1395 1396 void R600MachineCFGStructurizer::mergeLooplandBlock(MachineBasicBlock *DstBlk, 1397 MachineBasicBlock *LandMBB) { 1398 LLVM_DEBUG(dbgs() << "loopPattern header = BB" << DstBlk->getNumber() 1399 << " land = BB" << LandMBB->getNumber() << "\n";); 1400 1401 insertInstrBefore(DstBlk, R600::WHILELOOP, DebugLoc()); 1402 insertInstrEnd(DstBlk, R600::ENDLOOP, DebugLoc()); 1403 DstBlk->replaceSuccessor(DstBlk, LandMBB); 1404 } 1405 1406 void R600MachineCFGStructurizer::mergeLoopbreakBlock(MachineBasicBlock *ExitingMBB, 1407 MachineBasicBlock *LandMBB) { 1408 LLVM_DEBUG(dbgs() << "loopbreakPattern exiting = BB" 1409 << ExitingMBB->getNumber() << " land = BB" 1410 << LandMBB->getNumber() << "\n";); 1411 MachineInstr *BranchMI = getLoopendBlockBranchInstr(ExitingMBB); 1412 assert(BranchMI && isCondBranch(BranchMI)); 1413 DebugLoc DL = BranchMI->getDebugLoc(); 1414 MachineBasicBlock *TrueBranch = getTrueBranch(BranchMI); 1415 MachineBasicBlock::iterator I = BranchMI; 1416 if (TrueBranch != LandMBB) 1417 reversePredicateSetter(I, *I->getParent()); 1418 insertCondBranchBefore(ExitingMBB, I, R600::IF_PREDICATE_SET, R600::PREDICATE_BIT, DL); 1419 insertInstrBefore(I, R600::BREAK); 1420 insertInstrBefore(I, R600::ENDIF); 1421 //now branchInst can be erase safely 1422 BranchMI->eraseFromParent(); 1423 //now take care of successors, retire blocks 1424 ExitingMBB->removeSuccessor(LandMBB, true); 1425 } 1426 1427 void R600MachineCFGStructurizer::settleLoopcontBlock(MachineBasicBlock *ContingMBB, 1428 MachineBasicBlock *ContMBB) { 1429 LLVM_DEBUG(dbgs() << "settleLoopcontBlock conting = BB" 1430 << ContingMBB->getNumber() << ", cont = BB" 1431 << ContMBB->getNumber() << "\n";); 1432 1433 MachineInstr *MI = getLoopendBlockBranchInstr(ContingMBB); 1434 if (MI) { 1435 assert(isCondBranch(MI)); 1436 MachineBasicBlock::iterator I = MI; 1437 MachineBasicBlock *TrueBranch = getTrueBranch(MI); 1438 int OldOpcode = MI->getOpcode(); 1439 DebugLoc DL = MI->getDebugLoc(); 1440 1441 bool UseContinueLogical = ((&*ContingMBB->rbegin()) == MI); 1442 1443 if (!UseContinueLogical) { 1444 int BranchOpcode = 1445 TrueBranch == ContMBB ? getBranchNzeroOpcode(OldOpcode) : 1446 getBranchZeroOpcode(OldOpcode); 1447 insertCondBranchBefore(I, BranchOpcode, DL); 1448 // insertEnd to ensure phi-moves, if exist, go before the continue-instr. 1449 insertInstrEnd(ContingMBB, R600::CONTINUE, DL); 1450 insertInstrEnd(ContingMBB, R600::ENDIF, DL); 1451 } else { 1452 int BranchOpcode = 1453 TrueBranch == ContMBB ? getContinueNzeroOpcode(OldOpcode) : 1454 getContinueZeroOpcode(OldOpcode); 1455 insertCondBranchBefore(I, BranchOpcode, DL); 1456 } 1457 1458 MI->eraseFromParent(); 1459 } else { 1460 // if we've arrived here then we've already erased the branch instruction 1461 // travel back up the basic block to see the last reference of our debug 1462 // location we've just inserted that reference here so it should be 1463 // representative insertEnd to ensure phi-moves, if exist, go before the 1464 // continue-instr. 1465 insertInstrEnd(ContingMBB, R600::CONTINUE, 1466 getLastDebugLocInBB(ContingMBB)); 1467 } 1468 } 1469 1470 int R600MachineCFGStructurizer::cloneOnSideEntryTo(MachineBasicBlock *PreMBB, 1471 MachineBasicBlock *SrcMBB, MachineBasicBlock *DstMBB) { 1472 int Cloned = 0; 1473 assert(PreMBB->isSuccessor(SrcMBB)); 1474 while (SrcMBB && SrcMBB != DstMBB) { 1475 assert(SrcMBB->succ_size() == 1); 1476 if (SrcMBB->pred_size() > 1) { 1477 SrcMBB = cloneBlockForPredecessor(SrcMBB, PreMBB); 1478 ++Cloned; 1479 } 1480 1481 PreMBB = SrcMBB; 1482 SrcMBB = *SrcMBB->succ_begin(); 1483 } 1484 1485 return Cloned; 1486 } 1487 1488 MachineBasicBlock * 1489 R600MachineCFGStructurizer::cloneBlockForPredecessor(MachineBasicBlock *MBB, 1490 MachineBasicBlock *PredMBB) { 1491 assert(PredMBB->isSuccessor(MBB) && "succBlk is not a predecessor of curBlk"); 1492 1493 MachineBasicBlock *CloneMBB = clone(MBB); //clone instructions 1494 replaceInstrUseOfBlockWith(PredMBB, MBB, CloneMBB); 1495 //srcBlk, oldBlk, newBlk 1496 1497 PredMBB->replaceSuccessor(MBB, CloneMBB); 1498 1499 // add all successor to cloneBlk 1500 cloneSuccessorList(CloneMBB, MBB); 1501 1502 numClonedInstr += MBB->size(); 1503 1504 LLVM_DEBUG(dbgs() << "Cloned block: " 1505 << "BB" << MBB->getNumber() << "size " << MBB->size() 1506 << "\n";); 1507 1508 SHOWNEWBLK(CloneMBB, "result of Cloned block: "); 1509 1510 return CloneMBB; 1511 } 1512 1513 void R600MachineCFGStructurizer::migrateInstruction(MachineBasicBlock *SrcMBB, 1514 MachineBasicBlock *DstMBB, MachineBasicBlock::iterator I) { 1515 MachineBasicBlock::iterator SpliceEnd; 1516 //look for the input branchinstr, not the AMDGPU branchinstr 1517 MachineInstr *BranchMI = getNormalBlockBranchInstr(SrcMBB); 1518 if (!BranchMI) { 1519 LLVM_DEBUG(dbgs() << "migrateInstruction don't see branch instr\n";); 1520 SpliceEnd = SrcMBB->end(); 1521 } else { 1522 LLVM_DEBUG(dbgs() << "migrateInstruction see branch instr: " << *BranchMI); 1523 SpliceEnd = BranchMI; 1524 } 1525 LLVM_DEBUG(dbgs() << "migrateInstruction before splice dstSize = " 1526 << DstMBB->size() << "srcSize = " << SrcMBB->size() 1527 << "\n";); 1528 1529 //splice insert before insertPos 1530 DstMBB->splice(I, SrcMBB, SrcMBB->begin(), SpliceEnd); 1531 1532 LLVM_DEBUG(dbgs() << "migrateInstruction after splice dstSize = " 1533 << DstMBB->size() << "srcSize = " << SrcMBB->size() 1534 << '\n';); 1535 } 1536 1537 MachineBasicBlock * 1538 R600MachineCFGStructurizer::normalizeInfiniteLoopExit(MachineLoop* LoopRep) { 1539 MachineBasicBlock *LoopHeader = LoopRep->getHeader(); 1540 MachineBasicBlock *LoopLatch = LoopRep->getLoopLatch(); 1541 1542 if (!LoopHeader || !LoopLatch) 1543 return nullptr; 1544 MachineInstr *BranchMI = getLoopendBlockBranchInstr(LoopLatch); 1545 // Is LoopRep an infinite loop ? 1546 if (!BranchMI || !isUncondBranch(BranchMI)) 1547 return nullptr; 1548 1549 MachineBasicBlock *DummyExitBlk = FuncRep->CreateMachineBasicBlock(); 1550 FuncRep->push_back(DummyExitBlk); //insert to function 1551 SHOWNEWBLK(DummyExitBlk, "DummyExitBlock to normalize infiniteLoop: "); 1552 LLVM_DEBUG(dbgs() << "Old branch instr: " << *BranchMI << "\n";); 1553 LLVMContext &Ctx = LoopHeader->getParent()->getFunction().getContext(); 1554 Ctx.emitError("Extra register needed to handle CFG"); 1555 return nullptr; 1556 } 1557 1558 void R600MachineCFGStructurizer::removeUnconditionalBranch(MachineBasicBlock *MBB) { 1559 MachineInstr *BranchMI; 1560 1561 // I saw two unconditional branch in one basic block in example 1562 // test_fc_do_while_or.c need to fix the upstream on this to remove the loop. 1563 while ((BranchMI = getLoopendBlockBranchInstr(MBB)) 1564 && isUncondBranch(BranchMI)) { 1565 LLVM_DEBUG(dbgs() << "Removing uncond branch instr: " << *BranchMI); 1566 BranchMI->eraseFromParent(); 1567 } 1568 } 1569 1570 void R600MachineCFGStructurizer::removeRedundantConditionalBranch( 1571 MachineBasicBlock *MBB) { 1572 if (MBB->succ_size() != 2) 1573 return; 1574 MachineBasicBlock *MBB1 = *MBB->succ_begin(); 1575 MachineBasicBlock *MBB2 = *std::next(MBB->succ_begin()); 1576 if (MBB1 != MBB2) 1577 return; 1578 1579 MachineInstr *BranchMI = getNormalBlockBranchInstr(MBB); 1580 assert(BranchMI && isCondBranch(BranchMI)); 1581 LLVM_DEBUG(dbgs() << "Removing unneeded cond branch instr: " << *BranchMI); 1582 BranchMI->eraseFromParent(); 1583 SHOWNEWBLK(MBB1, "Removing redundant successor"); 1584 MBB->removeSuccessor(MBB1, true); 1585 } 1586 1587 void R600MachineCFGStructurizer::addDummyExitBlock( 1588 SmallVectorImpl<MachineBasicBlock*> &RetMBB) { 1589 MachineBasicBlock *DummyExitBlk = FuncRep->CreateMachineBasicBlock(); 1590 FuncRep->push_back(DummyExitBlk); //insert to function 1591 insertInstrEnd(DummyExitBlk, R600::RETURN); 1592 1593 for (MachineBasicBlock *MBB : RetMBB) { 1594 if (MachineInstr *MI = getReturnInstr(MBB)) 1595 MI->eraseFromParent(); 1596 MBB->addSuccessor(DummyExitBlk); 1597 LLVM_DEBUG(dbgs() << "Add dummyExitBlock to BB" << MBB->getNumber() 1598 << " successors\n";); 1599 } 1600 SHOWNEWBLK(DummyExitBlk, "DummyExitBlock: "); 1601 } 1602 1603 void R600MachineCFGStructurizer::removeSuccessor(MachineBasicBlock *MBB) { 1604 while (MBB->succ_size()) 1605 MBB->removeSuccessor(*MBB->succ_begin()); 1606 } 1607 1608 void R600MachineCFGStructurizer::recordSccnum(MachineBasicBlock *MBB, 1609 int SccNum) { 1610 BlockInformation *&srcBlkInfo = BlockInfoMap[MBB]; 1611 if (!srcBlkInfo) 1612 srcBlkInfo = new BlockInformation(); 1613 srcBlkInfo->SccNum = SccNum; 1614 } 1615 1616 void R600MachineCFGStructurizer::retireBlock(MachineBasicBlock *MBB) { 1617 LLVM_DEBUG(dbgs() << "Retiring BB" << MBB->getNumber() << "\n";); 1618 1619 BlockInformation *&SrcBlkInfo = BlockInfoMap[MBB]; 1620 1621 if (!SrcBlkInfo) 1622 SrcBlkInfo = new BlockInformation(); 1623 1624 SrcBlkInfo->IsRetired = true; 1625 assert(MBB->succ_empty() && MBB->pred_empty() && "can't retire block yet"); 1626 } 1627 1628 INITIALIZE_PASS_BEGIN(R600MachineCFGStructurizer, "amdgpustructurizer", 1629 "AMDGPU CFG Structurizer", false, false) 1630 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 1631 INITIALIZE_PASS_DEPENDENCY(MachinePostDominatorTree) 1632 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 1633 INITIALIZE_PASS_END(R600MachineCFGStructurizer, "amdgpustructurizer", 1634 "AMDGPU CFG Structurizer", false, false) 1635 1636 FunctionPass *llvm::createR600MachineCFGStructurizerPass() { 1637 return new R600MachineCFGStructurizer(); 1638 } 1639