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