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