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     // We reverse the predicate to make a triangle, empty false pattern;
1043     std::swap(TrueMBB, FalseMBB);
1044     reversePredicateSetter(MBB->end());
1045     LandBlk = FalseMBB;
1046     FalseMBB = NULL;
1047   } else if (FalseMBB->succ_size() == 1
1048              && isSameloopDetachedContbreak(TrueMBB, FalseMBB)) {
1049     LandBlk = *FalseMBB->succ_begin();
1050   } else if (TrueMBB->succ_size() == 1
1051     && isSameloopDetachedContbreak(FalseMBB, TrueMBB)) {
1052     LandBlk = *TrueMBB->succ_begin();
1053   } else {
1054     return handleJumpintoIf(MBB, TrueMBB, FalseMBB);
1055   }
1056
1057   // improveSimpleJumpinfoIf can handle the case where landBlk == NULL but the
1058   // new BB created for landBlk==NULL may introduce new challenge to the
1059   // reduction process.
1060   if (LandBlk &&
1061       ((TrueMBB && TrueMBB->pred_size() > 1)
1062       || (FalseMBB && FalseMBB->pred_size() > 1))) {
1063      Cloned += improveSimpleJumpintoIf(MBB, TrueMBB, FalseMBB, &LandBlk);
1064   }
1065
1066   if (TrueMBB && TrueMBB->pred_size() > 1) {
1067     TrueMBB = cloneBlockForPredecessor(TrueMBB, MBB);
1068     ++Cloned;
1069   }
1070
1071   if (FalseMBB && FalseMBB->pred_size() > 1) {
1072     FalseMBB = cloneBlockForPredecessor(FalseMBB, MBB);
1073     ++Cloned;
1074   }
1075
1076   mergeIfthenelseBlock(BranchMI, MBB, TrueMBB, FalseMBB, LandBlk);
1077
1078   ++numIfPatternMatch;
1079
1080   numClonedBlock += Cloned;
1081
1082   return 1 + Cloned;
1083 }
1084
1085 int AMDGPUCFGStructurizer::loopendPatternMatch() {
1086   std::vector<MachineLoop *> NestedLoops;
1087   for (MachineLoopInfo::iterator It = MLI->begin(), E = MLI->end();
1088       It != E; ++It) {
1089     df_iterator<MachineLoop *> LpIt = df_begin(*It),
1090         LpE = df_end(*It);
1091     for (; LpIt != LpE; ++LpIt)
1092       NestedLoops.push_back(*LpIt);
1093   }
1094   if (NestedLoops.size() == 0)
1095     return 0;
1096
1097   // Process nested loop outside->inside, so "continue" to a outside loop won't
1098   // be mistaken as "break" of the current loop.
1099   int Num = 0;
1100   for (std::vector<MachineLoop *>::reverse_iterator It = NestedLoops.rbegin(),
1101       E = NestedLoops.rend(); It != E; ++It) {
1102     MachineLoop *ExaminedLoop = *It;
1103     if (ExaminedLoop->getNumBlocks() == 0 || Visited[ExaminedLoop])
1104       continue;
1105     DEBUG(dbgs() << "Processing:\n"; ExaminedLoop->dump(););
1106     int NumBreak = mergeLoop(ExaminedLoop);
1107     if (NumBreak == -1)
1108       break;
1109     Num += NumBreak;
1110   }
1111   return Num;
1112 }
1113
1114 int AMDGPUCFGStructurizer::mergeLoop(MachineLoop *LoopRep) {
1115   MachineBasicBlock *LoopHeader = LoopRep->getHeader();
1116   MBBVector ExitingMBBs;
1117   LoopRep->getExitingBlocks(ExitingMBBs);
1118   assert(!ExitingMBBs.empty() && "Infinite Loop not supported");
1119   DEBUG(dbgs() << "Loop has " << ExitingMBBs.size() << " exiting blocks\n";);
1120   // We assume a single ExitBlk
1121   MBBVector ExitBlks;
1122   LoopRep->getExitBlocks(ExitBlks);
1123   SmallPtrSet<MachineBasicBlock *, 2> ExitBlkSet;
1124   for (unsigned i = 0, e = ExitBlks.size(); i < e; ++i)
1125     ExitBlkSet.insert(ExitBlks[i]);
1126   assert(ExitBlkSet.size() == 1);
1127   MachineBasicBlock *ExitBlk = *ExitBlks.begin();
1128   assert(ExitBlk && "Loop has several exit block");
1129   MBBVector LatchBlks;
1130   typedef GraphTraits<Inverse<MachineBasicBlock*> > InvMBBTraits;
1131   InvMBBTraits::ChildIteratorType PI = InvMBBTraits::child_begin(LoopHeader),
1132       PE = InvMBBTraits::child_end(LoopHeader);
1133   for (; PI != PE; PI++) {
1134     if (LoopRep->contains(*PI))
1135       LatchBlks.push_back(*PI);
1136   }
1137
1138   for (unsigned i = 0, e = ExitingMBBs.size(); i < e; ++i)
1139     mergeLoopbreakBlock(ExitingMBBs[i], ExitBlk);
1140   for (unsigned i = 0, e = LatchBlks.size(); i < e; ++i)
1141     settleLoopcontBlock(LatchBlks[i], LoopHeader);
1142   int Match = 0;
1143   do {
1144     Match = 0;
1145     Match += serialPatternMatch(LoopHeader);
1146     Match += ifPatternMatch(LoopHeader);
1147   } while (Match > 0);
1148   mergeLooplandBlock(LoopHeader, ExitBlk);
1149   MachineLoop *ParentLoop = LoopRep->getParentLoop();
1150   if (ParentLoop)
1151     MLI->changeLoopFor(LoopHeader, ParentLoop);
1152   else
1153     MLI->removeBlock(LoopHeader);
1154   Visited[LoopRep] = true;
1155   return 1;
1156 }
1157
1158 int AMDGPUCFGStructurizer::loopcontPatternMatch(MachineLoop *LoopRep,
1159     MachineBasicBlock *LoopHeader) {
1160   int NumCont = 0;
1161   SmallVector<MachineBasicBlock *, DEFAULT_VEC_SLOTS> ContMBB;
1162   typedef GraphTraits<Inverse<MachineBasicBlock *> > GTIM;
1163   GTIM::ChildIteratorType It = GTIM::child_begin(LoopHeader),
1164       E = GTIM::child_end(LoopHeader);
1165   for (; It != E; ++It) {
1166     MachineBasicBlock *MBB = *It;
1167     if (LoopRep->contains(MBB)) {
1168       handleLoopcontBlock(MBB, MLI->getLoopFor(MBB),
1169                           LoopHeader, LoopRep);
1170       ContMBB.push_back(MBB);
1171       ++NumCont;
1172     }
1173   }
1174
1175   for (SmallVectorImpl<MachineBasicBlock *>::iterator It = ContMBB.begin(),
1176       E = ContMBB.end(); It != E; ++It) {
1177     (*It)->removeSuccessor(LoopHeader);
1178   }
1179
1180   numLoopcontPatternMatch += NumCont;
1181
1182   return NumCont;
1183 }
1184
1185
1186 bool AMDGPUCFGStructurizer::isSameloopDetachedContbreak(
1187     MachineBasicBlock *Src1MBB, MachineBasicBlock *Src2MBB) {
1188   if (Src1MBB->succ_size() == 0) {
1189     MachineLoop *LoopRep = MLI->getLoopFor(Src1MBB);
1190     if (LoopRep&& LoopRep == MLI->getLoopFor(Src2MBB)) {
1191       MachineBasicBlock *&TheEntry = LLInfoMap[LoopRep];
1192       if (TheEntry) {
1193         DEBUG(
1194           dbgs() << "isLoopContBreakBlock yes src1 = BB"
1195                  << Src1MBB->getNumber()
1196                  << " src2 = BB" << Src2MBB->getNumber() << "\n";
1197         );
1198         return true;
1199       }
1200     }
1201   }
1202   return false;
1203 }
1204
1205 int AMDGPUCFGStructurizer::handleJumpintoIf(MachineBasicBlock *HeadMBB,
1206     MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB) {
1207   int Num = handleJumpintoIfImp(HeadMBB, TrueMBB, FalseMBB);
1208   if (Num == 0) {
1209     DEBUG(
1210       dbgs() << "handleJumpintoIf swap trueBlk and FalseBlk" << "\n";
1211     );
1212     Num = handleJumpintoIfImp(HeadMBB, FalseMBB, TrueMBB);
1213   }
1214   return Num;
1215 }
1216
1217 int AMDGPUCFGStructurizer::handleJumpintoIfImp(MachineBasicBlock *HeadMBB,
1218     MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB) {
1219   int Num = 0;
1220   MachineBasicBlock *DownBlk;
1221
1222   //trueBlk could be the common post dominator
1223   DownBlk = TrueMBB;
1224
1225   DEBUG(
1226     dbgs() << "handleJumpintoIfImp head = BB" << HeadMBB->getNumber()
1227            << " true = BB" << TrueMBB->getNumber()
1228            << ", numSucc=" << TrueMBB->succ_size()
1229            << " false = BB" << FalseMBB->getNumber() << "\n";
1230   );
1231
1232   while (DownBlk) {
1233     DEBUG(
1234       dbgs() << "check down = BB" << DownBlk->getNumber();
1235     );
1236
1237     if (singlePathTo(FalseMBB, DownBlk) == SinglePath_InPath) {
1238       DEBUG(
1239         dbgs() << " working\n";
1240       );
1241
1242       Num += cloneOnSideEntryTo(HeadMBB, TrueMBB, DownBlk);
1243       Num += cloneOnSideEntryTo(HeadMBB, FalseMBB, DownBlk);
1244
1245       numClonedBlock += Num;
1246       Num += serialPatternMatch(*HeadMBB->succ_begin());
1247       Num += serialPatternMatch(*(++HeadMBB->succ_begin()));
1248       Num += ifPatternMatch(HeadMBB);
1249       assert(Num > 0);
1250
1251       break;
1252     }
1253     DEBUG(
1254       dbgs() << " not working\n";
1255     );
1256     DownBlk = (DownBlk->succ_size() == 1) ? (*DownBlk->succ_begin()) : NULL;
1257   } // walk down the postDomTree
1258
1259   return Num;
1260 }
1261
1262 void AMDGPUCFGStructurizer::showImproveSimpleJumpintoIf(
1263     MachineBasicBlock *HeadMBB, MachineBasicBlock *TrueMBB,
1264     MachineBasicBlock *FalseMBB, MachineBasicBlock *LandMBB, bool Detail) {
1265   dbgs() << "head = BB" << HeadMBB->getNumber()
1266          << " size = " << HeadMBB->size();
1267   if (Detail) {
1268     dbgs() << "\n";
1269     HeadMBB->print(dbgs());
1270     dbgs() << "\n";
1271   }
1272
1273   if (TrueMBB) {
1274     dbgs() << ", true = BB" << TrueMBB->getNumber() << " size = "
1275            << TrueMBB->size() << " numPred = " << TrueMBB->pred_size();
1276     if (Detail) {
1277       dbgs() << "\n";
1278       TrueMBB->print(dbgs());
1279       dbgs() << "\n";
1280     }
1281   }
1282   if (FalseMBB) {
1283     dbgs() << ", false = BB" << FalseMBB->getNumber() << " size = "
1284            << FalseMBB->size() << " numPred = " << FalseMBB->pred_size();
1285     if (Detail) {
1286       dbgs() << "\n";
1287       FalseMBB->print(dbgs());
1288       dbgs() << "\n";
1289     }
1290   }
1291   if (LandMBB) {
1292     dbgs() << ", land = BB" << LandMBB->getNumber() << " size = "
1293            << LandMBB->size() << " numPred = " << LandMBB->pred_size();
1294     if (Detail) {
1295       dbgs() << "\n";
1296       LandMBB->print(dbgs());
1297       dbgs() << "\n";
1298     }
1299   }
1300
1301     dbgs() << "\n";
1302 }
1303
1304 int AMDGPUCFGStructurizer::improveSimpleJumpintoIf(MachineBasicBlock *HeadMBB,
1305     MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB,
1306     MachineBasicBlock **LandMBBPtr) {
1307   bool MigrateTrue = false;
1308   bool MigrateFalse = false;
1309
1310   MachineBasicBlock *LandBlk = *LandMBBPtr;
1311
1312   assert((!TrueMBB || TrueMBB->succ_size() <= 1)
1313          && (!FalseMBB || FalseMBB->succ_size() <= 1));
1314
1315   if (TrueMBB == FalseMBB)
1316     return 0;
1317
1318   MigrateTrue = needMigrateBlock(TrueMBB);
1319   MigrateFalse = needMigrateBlock(FalseMBB);
1320
1321   if (!MigrateTrue && !MigrateFalse)
1322     return 0;
1323
1324   // If we need to migrate either trueBlk and falseBlk, migrate the rest that
1325   // have more than one predecessors.  without doing this, its predecessor
1326   // rather than headBlk will have undefined value in initReg.
1327   if (!MigrateTrue && TrueMBB && TrueMBB->pred_size() > 1)
1328     MigrateTrue = true;
1329   if (!MigrateFalse && FalseMBB && FalseMBB->pred_size() > 1)
1330     MigrateFalse = true;
1331
1332   DEBUG(
1333     dbgs() << "before improveSimpleJumpintoIf: ";
1334     showImproveSimpleJumpintoIf(HeadMBB, TrueMBB, FalseMBB, LandBlk, 0);
1335   );
1336
1337   // org: headBlk => if () {trueBlk} else {falseBlk} => landBlk
1338   //
1339   // new: headBlk => if () {initReg = 1; org trueBlk branch} else
1340   //      {initReg = 0; org falseBlk branch }
1341   //      => landBlk => if (initReg) {org trueBlk} else {org falseBlk}
1342   //      => org landBlk
1343   //      if landBlk->pred_size() > 2, put the about if-else inside
1344   //      if (initReg !=2) {...}
1345   //
1346   // add initReg = initVal to headBlk
1347
1348   const TargetRegisterClass * I32RC = TRI->getCFGStructurizerRegClass(MVT::i32);
1349   unsigned InitReg =
1350     HeadMBB->getParent()->getRegInfo().createVirtualRegister(I32RC);
1351   if (!MigrateTrue || !MigrateFalse)
1352     llvm_unreachable("Extra register needed to handle CFG");
1353
1354   int NumNewBlk = 0;
1355
1356   if (!LandBlk) {
1357     LandBlk = HeadMBB->getParent()->CreateMachineBasicBlock();
1358     HeadMBB->getParent()->push_back(LandBlk);  //insert to function
1359
1360     if (TrueMBB) {
1361       TrueMBB->addSuccessor(LandBlk);
1362     } else {
1363       HeadMBB->addSuccessor(LandBlk);
1364     }
1365
1366     if (FalseMBB) {
1367       FalseMBB->addSuccessor(LandBlk);
1368     } else {
1369       HeadMBB->addSuccessor(LandBlk);
1370     }
1371
1372     NumNewBlk ++;
1373   }
1374
1375   bool LandBlkHasOtherPred = (LandBlk->pred_size() > 2);
1376
1377   //insert AMDGPU::ENDIF to avoid special case "input landBlk == NULL"
1378   MachineBasicBlock::iterator I = insertInstrBefore(LandBlk, AMDGPU::ENDIF);
1379
1380   if (LandBlkHasOtherPred) {
1381     llvm_unreachable("Extra register needed to handle CFG");
1382     unsigned CmpResReg =
1383       HeadMBB->getParent()->getRegInfo().createVirtualRegister(I32RC);
1384     llvm_unreachable("Extra compare instruction needed to handle CFG");
1385     insertCondBranchBefore(LandBlk, I, AMDGPU::IF_PREDICATE_SET,
1386         CmpResReg, DebugLoc());
1387   }
1388
1389   insertCondBranchBefore(LandBlk, I, AMDGPU::IF_PREDICATE_SET, InitReg,
1390       DebugLoc());
1391
1392   if (MigrateTrue) {
1393     migrateInstruction(TrueMBB, LandBlk, I);
1394     // need to uncondionally insert the assignment to ensure a path from its
1395     // predecessor rather than headBlk has valid value in initReg if
1396     // (initVal != 1).
1397     llvm_unreachable("Extra register needed to handle CFG");
1398   }
1399   insertInstrBefore(I, AMDGPU::ELSE);
1400
1401   if (MigrateFalse) {
1402     migrateInstruction(FalseMBB, LandBlk, I);
1403     // need to uncondionally insert the assignment to ensure a path from its
1404     // predecessor rather than headBlk has valid value in initReg if
1405     // (initVal != 0)
1406     llvm_unreachable("Extra register needed to handle CFG");
1407   }
1408
1409   if (LandBlkHasOtherPred) {
1410     // add endif
1411     insertInstrBefore(I, AMDGPU::ENDIF);
1412
1413     // put initReg = 2 to other predecessors of landBlk
1414     for (MachineBasicBlock::pred_iterator PI = LandBlk->pred_begin(),
1415          PE = LandBlk->pred_end(); PI != PE; ++PI) {
1416       MachineBasicBlock *MBB = *PI;
1417       if (MBB != TrueMBB && MBB != FalseMBB)
1418         llvm_unreachable("Extra register needed to handle CFG");
1419     }
1420   }
1421   DEBUG(
1422     dbgs() << "result from improveSimpleJumpintoIf: ";
1423     showImproveSimpleJumpintoIf(HeadMBB, TrueMBB, FalseMBB, LandBlk, 0);
1424   );
1425
1426   // update landBlk
1427   *LandMBBPtr = LandBlk;
1428
1429   return NumNewBlk;
1430 }
1431
1432 void AMDGPUCFGStructurizer::handleLoopcontBlock(MachineBasicBlock *ContingMBB,
1433     MachineLoop *ContingLoop, MachineBasicBlock *ContMBB,
1434     MachineLoop *ContLoop) {
1435   DEBUG(dbgs() << "loopcontPattern cont = BB" << ContingMBB->getNumber()
1436                << " header = BB" << ContMBB->getNumber() << "\n";
1437         dbgs() << "Trying to continue loop-depth = "
1438                << getLoopDepth(ContLoop)
1439                << " from loop-depth = " << getLoopDepth(ContingLoop) << "\n";);
1440   settleLoopcontBlock(ContingMBB, ContMBB);
1441 }
1442
1443 void AMDGPUCFGStructurizer::mergeSerialBlock(MachineBasicBlock *DstMBB,
1444     MachineBasicBlock *SrcMBB) {
1445   DEBUG(
1446     dbgs() << "serialPattern BB" << DstMBB->getNumber()
1447            << " <= BB" << SrcMBB->getNumber() << "\n";
1448   );
1449   DstMBB->splice(DstMBB->end(), SrcMBB, SrcMBB->begin(), SrcMBB->end());
1450
1451   DstMBB->removeSuccessor(SrcMBB);
1452   cloneSuccessorList(DstMBB, SrcMBB);
1453
1454   removeSuccessor(SrcMBB);
1455   MLI->removeBlock(SrcMBB);
1456   retireBlock(SrcMBB);
1457 }
1458
1459 void AMDGPUCFGStructurizer::mergeIfthenelseBlock(MachineInstr *BranchMI,
1460     MachineBasicBlock *MBB, MachineBasicBlock *TrueMBB,
1461     MachineBasicBlock *FalseMBB, MachineBasicBlock *LandMBB) {
1462   assert (TrueMBB);
1463   DEBUG(
1464     dbgs() << "ifPattern BB" << MBB->getNumber();
1465     dbgs() << "{  ";
1466     if (TrueMBB) {
1467       dbgs() << "BB" << TrueMBB->getNumber();
1468     }
1469     dbgs() << "  } else ";
1470     dbgs() << "{  ";
1471     if (FalseMBB) {
1472       dbgs() << "BB" << FalseMBB->getNumber();
1473     }
1474     dbgs() << "  }\n ";
1475     dbgs() << "landBlock: ";
1476     if (!LandMBB) {
1477       dbgs() << "NULL";
1478     } else {
1479       dbgs() << "BB" << LandMBB->getNumber();
1480     }
1481     dbgs() << "\n";
1482   );
1483
1484   int OldOpcode = BranchMI->getOpcode();
1485   DebugLoc BranchDL = BranchMI->getDebugLoc();
1486
1487 //    transform to
1488 //    if cond
1489 //       trueBlk
1490 //    else
1491 //       falseBlk
1492 //    endif
1493 //    landBlk
1494
1495   MachineBasicBlock::iterator I = BranchMI;
1496   insertCondBranchBefore(I, getBranchNzeroOpcode(OldOpcode),
1497       BranchDL);
1498
1499   if (TrueMBB) {
1500     MBB->splice(I, TrueMBB, TrueMBB->begin(), TrueMBB->end());
1501     MBB->removeSuccessor(TrueMBB);
1502     if (LandMBB && TrueMBB->succ_size()!=0)
1503       TrueMBB->removeSuccessor(LandMBB);
1504     retireBlock(TrueMBB);
1505     MLI->removeBlock(TrueMBB);
1506   }
1507
1508   if (FalseMBB) {
1509     insertInstrBefore(I, AMDGPU::ELSE);
1510     MBB->splice(I, FalseMBB, FalseMBB->begin(),
1511                    FalseMBB->end());
1512     MBB->removeSuccessor(FalseMBB);
1513     if (LandMBB && FalseMBB->succ_size() != 0)
1514       FalseMBB->removeSuccessor(LandMBB);
1515     retireBlock(FalseMBB);
1516     MLI->removeBlock(FalseMBB);
1517   }
1518   insertInstrBefore(I, AMDGPU::ENDIF);
1519
1520   BranchMI->eraseFromParent();
1521
1522   if (LandMBB && TrueMBB && FalseMBB)
1523     MBB->addSuccessor(LandMBB);
1524
1525 }
1526
1527 void AMDGPUCFGStructurizer::mergeLooplandBlock(MachineBasicBlock *DstBlk,
1528     MachineBasicBlock *LandMBB) {
1529   DEBUG(dbgs() << "loopPattern header = BB" << DstBlk->getNumber()
1530                << " land = BB" << LandMBB->getNumber() << "\n";);
1531
1532   /* we last inserterd the DebugLoc in the
1533    * BREAK_LOGICALZ_i32 or AMDGPU::BREAK_LOGICALNZ statement in the current
1534    * dstBlk.
1535    * search for the DebugLoc in the that statement.
1536    * if not found, we have to insert the empty/default DebugLoc */
1537   MachineInstr *LoopBreakInstr = getLoopBreakInstr(DstBlk);
1538   DebugLoc DLBreak = (LoopBreakInstr) ? LoopBreakInstr->getDebugLoc() :
1539       DebugLoc();
1540
1541   insertInstrBefore(DstBlk, AMDGPU::WHILELOOP, DLBreak);
1542
1543   /* we last inserterd the DebugLoc in the continue statement in the current
1544    * dstBlk.
1545    * search for the DebugLoc in the continue statement.
1546    * if not found, we have to insert the empty/default DebugLoc */
1547   MachineInstr *ContinueInstr = getContinueInstr(DstBlk);
1548   DebugLoc DLContinue = (ContinueInstr) ? ContinueInstr->getDebugLoc() :
1549       DebugLoc();
1550
1551   insertInstrEnd(DstBlk, AMDGPU::ENDLOOP, DLContinue);
1552   DstBlk->addSuccessor(LandMBB);
1553   DstBlk->removeSuccessor(DstBlk);
1554 }
1555
1556
1557 void AMDGPUCFGStructurizer::mergeLoopbreakBlock(MachineBasicBlock *ExitingMBB,
1558     MachineBasicBlock *LandMBB) {
1559   DEBUG(dbgs() << "loopbreakPattern exiting = BB" << ExitingMBB->getNumber()
1560                << " land = BB" << LandMBB->getNumber() << "\n";);
1561   MachineInstr *BranchMI = getLoopendBlockBranchInstr(ExitingMBB);
1562   assert(BranchMI && isCondBranch(BranchMI));
1563   DebugLoc DL = BranchMI->getDebugLoc();
1564   MachineBasicBlock *TrueBranch = getTrueBranch(BranchMI);
1565   MachineBasicBlock::iterator I = BranchMI;
1566   if (TrueBranch != LandMBB)
1567     reversePredicateSetter(I);
1568   insertCondBranchBefore(I, AMDGPU::PREDICATED_BREAK, DL);
1569   //now branchInst can be erase safely
1570   BranchMI->eraseFromParent();
1571   //now take care of successors, retire blocks
1572   ExitingMBB->removeSuccessor(LandMBB);
1573 }
1574
1575 void AMDGPUCFGStructurizer::settleLoopcontBlock(MachineBasicBlock *ContingMBB,
1576     MachineBasicBlock *ContMBB) {
1577   DEBUG(dbgs() << "settleLoopcontBlock conting = BB"
1578                << ContingMBB->getNumber()
1579                << ", cont = BB" << ContMBB->getNumber() << "\n";);
1580
1581   MachineInstr *MI = getLoopendBlockBranchInstr(ContingMBB);
1582   if (MI) {
1583     assert(isCondBranch(MI));
1584     MachineBasicBlock::iterator I = MI;
1585     MachineBasicBlock *TrueBranch = getTrueBranch(MI);
1586     int OldOpcode = MI->getOpcode();
1587     DebugLoc DL = MI->getDebugLoc();
1588
1589     bool UseContinueLogical = ((&*ContingMBB->rbegin()) == MI);
1590
1591     if (UseContinueLogical == false) {
1592       int BranchOpcode =
1593           TrueBranch == ContMBB ? getBranchNzeroOpcode(OldOpcode) :
1594           getBranchZeroOpcode(OldOpcode);
1595       insertCondBranchBefore(I, BranchOpcode, DL);
1596       // insertEnd to ensure phi-moves, if exist, go before the continue-instr.
1597       insertInstrEnd(ContingMBB, AMDGPU::CONTINUE, DL);
1598       insertInstrEnd(ContingMBB, AMDGPU::ENDIF, DL);
1599     } else {
1600       int BranchOpcode =
1601           TrueBranch == ContMBB ? getContinueNzeroOpcode(OldOpcode) :
1602           getContinueZeroOpcode(OldOpcode);
1603       insertCondBranchBefore(I, BranchOpcode, DL);
1604     }
1605
1606     MI->eraseFromParent();
1607   } else {
1608     // if we've arrived here then we've already erased the branch instruction
1609     // travel back up the basic block to see the last reference of our debug
1610     // location we've just inserted that reference here so it should be
1611     // representative insertEnd to ensure phi-moves, if exist, go before the
1612     // continue-instr.
1613     insertInstrEnd(ContingMBB, AMDGPU::CONTINUE,
1614         getLastDebugLocInBB(ContingMBB));
1615   }
1616 }
1617
1618 int AMDGPUCFGStructurizer::cloneOnSideEntryTo(MachineBasicBlock *PreMBB,
1619     MachineBasicBlock *SrcMBB, MachineBasicBlock *DstMBB) {
1620   int Cloned = 0;
1621   assert(PreMBB->isSuccessor(SrcMBB));
1622   while (SrcMBB && SrcMBB != DstMBB) {
1623     assert(SrcMBB->succ_size() == 1);
1624     if (SrcMBB->pred_size() > 1) {
1625       SrcMBB = cloneBlockForPredecessor(SrcMBB, PreMBB);
1626       ++Cloned;
1627     }
1628
1629     PreMBB = SrcMBB;
1630     SrcMBB = *SrcMBB->succ_begin();
1631   }
1632
1633   return Cloned;
1634 }
1635
1636 MachineBasicBlock *
1637 AMDGPUCFGStructurizer::cloneBlockForPredecessor(MachineBasicBlock *MBB,
1638     MachineBasicBlock *PredMBB) {
1639   assert(PredMBB->isSuccessor(MBB) &&
1640          "succBlk is not a prececessor of curBlk");
1641
1642   MachineBasicBlock *CloneMBB = clone(MBB);  //clone instructions
1643   replaceInstrUseOfBlockWith(PredMBB, MBB, CloneMBB);
1644   //srcBlk, oldBlk, newBlk
1645
1646   PredMBB->removeSuccessor(MBB);
1647   PredMBB->addSuccessor(CloneMBB);
1648
1649   // add all successor to cloneBlk
1650   cloneSuccessorList(CloneMBB, MBB);
1651
1652   numClonedInstr += MBB->size();
1653
1654   DEBUG(
1655     dbgs() << "Cloned block: " << "BB"
1656            << MBB->getNumber() << "size " << MBB->size() << "\n";
1657   );
1658
1659   SHOWNEWBLK(CloneMBB, "result of Cloned block: ");
1660
1661   return CloneMBB;
1662 }
1663
1664 void AMDGPUCFGStructurizer::migrateInstruction(MachineBasicBlock *SrcMBB,
1665     MachineBasicBlock *DstMBB, MachineBasicBlock::iterator I) {
1666   MachineBasicBlock::iterator SpliceEnd;
1667   //look for the input branchinstr, not the AMDGPU branchinstr
1668   MachineInstr *BranchMI = getNormalBlockBranchInstr(SrcMBB);
1669   if (!BranchMI) {
1670     DEBUG(
1671       dbgs() << "migrateInstruction don't see branch instr\n" ;
1672     );
1673     SpliceEnd = SrcMBB->end();
1674   } else {
1675     DEBUG(
1676       dbgs() << "migrateInstruction see branch instr\n" ;
1677       BranchMI->dump();
1678     );
1679     SpliceEnd = BranchMI;
1680   }
1681   DEBUG(
1682     dbgs() << "migrateInstruction before splice dstSize = " << DstMBB->size()
1683       << "srcSize = " << SrcMBB->size() << "\n";
1684   );
1685
1686   //splice insert before insertPos
1687   DstMBB->splice(I, SrcMBB, SrcMBB->begin(), SpliceEnd);
1688
1689   DEBUG(
1690     dbgs() << "migrateInstruction after splice dstSize = " << DstMBB->size()
1691       << "srcSize = " << SrcMBB->size() << "\n";
1692   );
1693 }
1694
1695 MachineBasicBlock *
1696 AMDGPUCFGStructurizer::normalizeInfiniteLoopExit(MachineLoop* LoopRep) {
1697   MachineBasicBlock *LoopHeader = LoopRep->getHeader();
1698   MachineBasicBlock *LoopLatch = LoopRep->getLoopLatch();
1699   const TargetRegisterClass * I32RC = TRI->getCFGStructurizerRegClass(MVT::i32);
1700
1701   if (!LoopHeader || !LoopLatch)
1702     return NULL;
1703   MachineInstr *BranchMI = getLoopendBlockBranchInstr(LoopLatch);
1704   // Is LoopRep an infinite loop ?
1705   if (!BranchMI || !isUncondBranch(BranchMI))
1706     return NULL;
1707
1708   MachineBasicBlock *DummyExitBlk = FuncRep->CreateMachineBasicBlock();
1709   FuncRep->push_back(DummyExitBlk);  //insert to function
1710   SHOWNEWBLK(DummyExitBlk, "DummyExitBlock to normalize infiniteLoop: ");
1711   DEBUG(dbgs() << "Old branch instr: " << *BranchMI << "\n";);
1712   MachineBasicBlock::iterator I = BranchMI;
1713   unsigned ImmReg = FuncRep->getRegInfo().createVirtualRegister(I32RC);
1714   llvm_unreachable("Extra register needed to handle CFG");
1715   MachineInstr *NewMI = insertInstrBefore(I, AMDGPU::BRANCH_COND_i32);
1716   MachineInstrBuilder MIB(*FuncRep, NewMI);
1717   MIB.addMBB(LoopHeader);
1718   MIB.addReg(ImmReg, false);
1719   SHOWNEWINSTR(NewMI);
1720   BranchMI->eraseFromParent();
1721   LoopLatch->addSuccessor(DummyExitBlk);
1722
1723   return DummyExitBlk;
1724 }
1725
1726 void AMDGPUCFGStructurizer::removeUnconditionalBranch(MachineBasicBlock *MBB) {
1727   MachineInstr *BranchMI;
1728
1729   // I saw two unconditional branch in one basic block in example
1730   // test_fc_do_while_or.c need to fix the upstream on this to remove the loop.
1731   while ((BranchMI = getLoopendBlockBranchInstr(MBB))
1732           && isUncondBranch(BranchMI)) {
1733     DEBUG(dbgs() << "Removing uncond branch instr"; BranchMI->dump(););
1734     BranchMI->eraseFromParent();
1735   }
1736 }
1737
1738 void AMDGPUCFGStructurizer::removeRedundantConditionalBranch(
1739     MachineBasicBlock *MBB) {
1740   if (MBB->succ_size() != 2)
1741     return;
1742   MachineBasicBlock *MBB1 = *MBB->succ_begin();
1743   MachineBasicBlock *MBB2 = *(++MBB->succ_begin());
1744   if (MBB1 != MBB2)
1745     return;
1746
1747   MachineInstr *BranchMI = getNormalBlockBranchInstr(MBB);
1748   assert(BranchMI && isCondBranch(BranchMI));
1749   DEBUG(dbgs() << "Removing unneeded cond branch instr"; BranchMI->dump(););
1750   BranchMI->eraseFromParent();
1751   SHOWNEWBLK(MBB1, "Removing redundant successor");
1752   MBB->removeSuccessor(MBB1);
1753 }
1754
1755 void AMDGPUCFGStructurizer::addDummyExitBlock(
1756     SmallVectorImpl<MachineBasicBlock*> &RetMBB) {
1757   MachineBasicBlock *DummyExitBlk = FuncRep->CreateMachineBasicBlock();
1758   FuncRep->push_back(DummyExitBlk);  //insert to function
1759   insertInstrEnd(DummyExitBlk, AMDGPU::RETURN);
1760
1761   for (SmallVectorImpl<MachineBasicBlock *>::iterator It = RetMBB.begin(),
1762        E = RetMBB.end(); It != E; ++It) {
1763     MachineBasicBlock *MBB = *It;
1764     MachineInstr *MI = getReturnInstr(MBB);
1765     if (MI)
1766       MI->eraseFromParent();
1767     MBB->addSuccessor(DummyExitBlk);
1768     DEBUG(
1769       dbgs() << "Add dummyExitBlock to BB" << MBB->getNumber()
1770              << " successors\n";
1771     );
1772   }
1773   SHOWNEWBLK(DummyExitBlk, "DummyExitBlock: ");
1774 }
1775
1776 void AMDGPUCFGStructurizer::removeSuccessor(MachineBasicBlock *MBB) {
1777   while (MBB->succ_size())
1778     MBB->removeSuccessor(*MBB->succ_begin());
1779 }
1780
1781 void AMDGPUCFGStructurizer::recordSccnum(MachineBasicBlock *MBB,
1782     int SccNum) {
1783   BlockInformation *&srcBlkInfo = BlockInfoMap[MBB];
1784   if (!srcBlkInfo)
1785     srcBlkInfo = new BlockInformation();
1786   srcBlkInfo->SccNum = SccNum;
1787 }
1788
1789 void AMDGPUCFGStructurizer::retireBlock(MachineBasicBlock *MBB) {
1790   DEBUG(
1791         dbgs() << "Retiring BB" << MBB->getNumber() << "\n";
1792   );
1793
1794   BlockInformation *&SrcBlkInfo = BlockInfoMap[MBB];
1795
1796   if (!SrcBlkInfo)
1797     SrcBlkInfo = new BlockInformation();
1798
1799   SrcBlkInfo->IsRetired = true;
1800   assert(MBB->succ_size() == 0 && MBB->pred_size() == 0
1801          && "can't retire block yet");
1802 }
1803
1804 void AMDGPUCFGStructurizer::setLoopLandBlock(MachineLoop *loopRep,
1805     MachineBasicBlock *MBB) {
1806   MachineBasicBlock *&TheEntry = LLInfoMap[loopRep];
1807   if (!MBB) {
1808     MBB = FuncRep->CreateMachineBasicBlock();
1809     FuncRep->push_back(MBB);  //insert to function
1810     SHOWNEWBLK(MBB, "DummyLandingBlock for loop without break: ");
1811   }
1812   TheEntry = MBB;
1813   DEBUG(
1814     dbgs() << "setLoopLandBlock loop-header = BB"
1815            << loopRep->getHeader()->getNumber()
1816            << "  landing-block = BB" << MBB->getNumber() << "\n";
1817   );
1818 }
1819
1820 MachineBasicBlock *
1821 AMDGPUCFGStructurizer::findNearestCommonPostDom(MachineBasicBlock *MBB1,
1822     MachineBasicBlock *MBB2) {
1823
1824   if (PDT->dominates(MBB1, MBB2))
1825     return MBB1;
1826   if (PDT->dominates(MBB2, MBB1))
1827     return MBB2;
1828
1829   MachineDomTreeNode *Node1 = PDT->getNode(MBB1);
1830   MachineDomTreeNode *Node2 = PDT->getNode(MBB2);
1831
1832   // Handle newly cloned node.
1833   if (!Node1 && MBB1->succ_size() == 1)
1834     return findNearestCommonPostDom(*MBB1->succ_begin(), MBB2);
1835   if (!Node2 && MBB2->succ_size() == 1)
1836     return findNearestCommonPostDom(MBB1, *MBB2->succ_begin());
1837
1838   if (!Node1 || !Node2)
1839     return NULL;
1840
1841   Node1 = Node1->getIDom();
1842   while (Node1) {
1843     if (PDT->dominates(Node1, Node2))
1844       return Node1->getBlock();
1845     Node1 = Node1->getIDom();
1846   }
1847
1848   return NULL;
1849 }
1850
1851 MachineBasicBlock *
1852 AMDGPUCFGStructurizer::findNearestCommonPostDom(
1853     std::set<MachineBasicBlock *> &MBBs) {
1854   MachineBasicBlock *CommonDom;
1855   std::set<MachineBasicBlock *>::const_iterator It = MBBs.begin();
1856   std::set<MachineBasicBlock *>::const_iterator E = MBBs.end();
1857   for (CommonDom = *It; It != E && CommonDom; ++It) {
1858     MachineBasicBlock *MBB = *It;
1859     if (MBB != CommonDom)
1860       CommonDom = findNearestCommonPostDom(MBB, CommonDom);
1861   }
1862
1863   DEBUG(
1864     dbgs() << "Common post dominator for exit blocks is ";
1865     if (CommonDom)
1866           dbgs() << "BB" << CommonDom->getNumber() << "\n";
1867     else
1868       dbgs() << "NULL\n";
1869   );
1870
1871   return CommonDom;
1872 }
1873
1874 char AMDGPUCFGStructurizer::ID = 0;
1875
1876 } // end anonymous namespace
1877
1878
1879 FunctionPass *llvm::createAMDGPUCFGStructurizerPass(TargetMachine &tm) {
1880   return new AMDGPUCFGStructurizer(tm);
1881 }