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