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