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