contrib/llvm/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp

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