AMDILCFGStructurizer.cpp revision a75c6163e605f35b14f26930dd9227e4f337ec9e 
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//==-----------------------------------------------------------------------===//
9
10#define DEBUG_TYPE "structcfg"
11#ifdef DEBUG
12#define DEBUGME (DebugFlag && isCurrentDebugType(DEBUG_TYPE))
13#else
14#define DEBUGME 0
15#endif
16
17#include "AMDILCompilerErrors.h"
18#include "AMDILMachineFunctionInfo.h"
19#include "AMDILTargetMachine.h"
20#include "AMDILUtilityFunctions.h"
21#include "llvm/ADT/SCCIterator.h"
22#include "llvm/ADT/SmallVector.h"
23#include "llvm/ADT/Statistic.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/MachineJumpTableInfo.h"
29#include "llvm/CodeGen/MachineLoopInfo.h"
30#include "llvm/CodeGen/MachineRegisterInfo.h"
31
32#define FirstNonDebugInstr(A) A->begin()
33using namespace llvm;
34
35// bixia TODO: move this out to analysis lib. Make this work for both target
36// AMDIL and CBackend.
37// TODO: move-begin.
38
39//===----------------------------------------------------------------------===//
40//
41// Statistics for CFGStructurizer.
42//
43//===----------------------------------------------------------------------===//
44
45STATISTIC(numSerialPatternMatch,    "CFGStructurizer number of serial pattern "
46    "matched");
47STATISTIC(numIfPatternMatch,        "CFGStructurizer number of if pattern "
48    "matched");
49STATISTIC(numLoopbreakPatternMatch, "CFGStructurizer number of loop-break "
50    "pattern matched");
51STATISTIC(numLoopcontPatternMatch,  "CFGStructurizer number of loop-continue "
52    "pattern matched");
53STATISTIC(numLoopPatternMatch,      "CFGStructurizer number of loop pattern "
54    "matched");
55STATISTIC(numClonedBlock,           "CFGStructurizer cloned blocks");
56STATISTIC(numClonedInstr,           "CFGStructurizer cloned instructions");
57
58//===----------------------------------------------------------------------===//
59//
60// Miscellaneous utility for CFGStructurizer.
61//
62//===----------------------------------------------------------------------===//
63namespace llvmCFGStruct
64{
65#define SHOWNEWINSTR(i) \
66  if (DEBUGME) errs() << "New instr: " << *i << "\n"
67
68#define SHOWNEWBLK(b, msg) \
69if (DEBUGME) { \
70  errs() << msg << "BB" << b->getNumber() << "size " << b->size(); \
71  errs() << "\n"; \
72}
73
74#define SHOWBLK_DETAIL(b, msg) \
75if (DEBUGME) { \
76  if (b) { \
77  errs() << msg << "BB" << b->getNumber() << "size " << b->size(); \
78  b->print(errs()); \
79  errs() << "\n"; \
80  } \
81}
82
83#define INVALIDSCCNUM -1
84#define INVALIDREGNUM 0
85
86template<class LoopinfoT>
87void PrintLoopinfo(const LoopinfoT &LoopInfo, llvm::raw_ostream &OS) {
88  for (typename LoopinfoT::iterator iter = LoopInfo.begin(),
89       iterEnd = LoopInfo.end();
90       iter != iterEnd; ++iter) {
91    (*iter)->print(OS, 0);
92  }
93}
94
95template<class NodeT>
96void ReverseVector(SmallVector<NodeT *, DEFAULT_VEC_SLOTS> &Src) {
97  size_t sz = Src.size();
98  for (size_t i = 0; i < sz/2; ++i) {
99    NodeT *t = Src[i];
100    Src[i] = Src[sz - i - 1];
101    Src[sz - i - 1] = t;
102  }
103}
104
105} //end namespace llvmCFGStruct
106
107
108//===----------------------------------------------------------------------===//
109//
110// MachinePostDominatorTree
111//
112//===----------------------------------------------------------------------===//
113
114#include "AMDILCompilerErrors.h"
115#include "AMDILMachineFunctionInfo.h"
116#include "AMDILTargetMachine.h"
117#include "AMDILUtilityFunctions.h"
118#include "llvm/ADT/SCCIterator.h"
119#include "llvm/ADT/SmallVector.h"
120#include "llvm/ADT/Statistic.h"
121#include "llvm/Analysis/DominatorInternals.h"
122#include "llvm/Analysis/Dominators.h"
123#include "llvm/CodeGen/MachineDominators.h"
124#include "llvm/CodeGen/MachineDominators.h"
125#include "llvm/CodeGen/MachineFunction.h"
126#include "llvm/CodeGen/MachineFunctionAnalysis.h"
127#include "llvm/CodeGen/MachineFunctionPass.h"
128#include "llvm/CodeGen/MachineFunctionPass.h"
129#include "llvm/CodeGen/MachineJumpTableInfo.h"
130#include "llvm/CodeGen/MachineLoopInfo.h"
131#include "llvm/CodeGen/MachineRegisterInfo.h"
132
133namespace llvm {
134
135/// PostDominatorTree Class - Concrete subclass of DominatorTree that is used
136/// to compute the a post-dominator tree.
137///
138struct MachinePostDominatorTree : public MachineFunctionPass {
139  static char ID; // Pass identification, replacement for typeid
140  DominatorTreeBase<MachineBasicBlock> *DT;
141  MachinePostDominatorTree() : MachineFunctionPass(ID)
142  {
143    DT = new DominatorTreeBase<MachineBasicBlock>(true); //true indicate
144    // postdominator
145  }
146
147  ~MachinePostDominatorTree();
148
149  virtual bool runOnMachineFunction(MachineFunction &MF);
150
151  virtual void getAnalysisUsage(AnalysisUsage &AU) const {
152    AU.setPreservesAll();
153    MachineFunctionPass::getAnalysisUsage(AU);
154  }
155
156  inline const std::vector<MachineBasicBlock *> &getRoots() const {
157    return DT->getRoots();
158  }
159
160  inline MachineDomTreeNode *getRootNode() const {
161    return DT->getRootNode();
162  }
163
164  inline MachineDomTreeNode *operator[](MachineBasicBlock *BB) const {
165    return DT->getNode(BB);
166  }
167
168  inline MachineDomTreeNode *getNode(MachineBasicBlock *BB) const {
169    return DT->getNode(BB);
170  }
171
172  inline bool dominates(MachineDomTreeNode *A, MachineDomTreeNode *B) const {
173    return DT->dominates(A, B);
174  }
175
176  inline bool dominates(MachineBasicBlock *A, MachineBasicBlock *B) const {
177    return DT->dominates(A, B);
178  }
179
180  inline bool
181  properlyDominates(const MachineDomTreeNode *A, MachineDomTreeNode *B) const {
182    return DT->properlyDominates(A, B);
183  }
184
185  inline bool
186  properlyDominates(MachineBasicBlock *A, MachineBasicBlock *B) const {
187    return DT->properlyDominates(A, B);
188  }
189
190  inline MachineBasicBlock *
191  findNearestCommonDominator(MachineBasicBlock *A, MachineBasicBlock *B) {
192    return DT->findNearestCommonDominator(A, B);
193  }
194
195  virtual void print(llvm::raw_ostream &OS, const Module *M = 0) const {
196    DT->print(OS);
197  }
198};
199} //end of namespace llvm
200
201char MachinePostDominatorTree::ID = 0;
202static RegisterPass<MachinePostDominatorTree>
203machinePostDominatorTreePass("machinepostdomtree",
204                             "MachinePostDominator Tree Construction",
205                             true, true);
206
207//const PassInfo *const llvm::MachinePostDominatorsID
208//= &machinePostDominatorTreePass;
209
210bool MachinePostDominatorTree::runOnMachineFunction(MachineFunction &F) {
211  DT->recalculate(F);
212  //DEBUG(DT->dump());
213  return false;
214}
215
216MachinePostDominatorTree::~MachinePostDominatorTree() {
217  delete DT;
218}
219
220//===----------------------------------------------------------------------===//
221//
222// supporting data structure for CFGStructurizer
223//
224//===----------------------------------------------------------------------===//
225
226namespace llvmCFGStruct
227{
228template<class PassT>
229struct CFGStructTraits {
230};
231
232template <class InstrT>
233class BlockInformation {
234public:
235  bool isRetired;
236  int  sccNum;
237  //SmallVector<InstrT*, DEFAULT_VEC_SLOTS> succInstr;
238  //Instructions defining the corresponding successor.
239  BlockInformation() : isRetired(false), sccNum(INVALIDSCCNUM) {}
240};
241
242template <class BlockT, class InstrT, class RegiT>
243class LandInformation {
244public:
245  BlockT *landBlk;
246  std::set<RegiT> breakInitRegs;  //Registers that need to "reg = 0", before
247                                  //WHILELOOP(thisloop) init before entering
248                                  //thisloop.
249  std::set<RegiT> contInitRegs;   //Registers that need to "reg = 0", after
250                                  //WHILELOOP(thisloop) init after entering
251                                  //thisloop.
252  std::set<RegiT> endbranchInitRegs; //Init before entering this loop, at loop
253                                     //land block, branch cond on this reg.
254  std::set<RegiT> breakOnRegs;       //registers that need to "if (reg) break
255                                     //endif" after ENDLOOP(thisloop) break
256                                     //outerLoopOf(thisLoop).
257  std::set<RegiT> contOnRegs;       //registers that need to "if (reg) continue
258                                    //endif" after ENDLOOP(thisloop) continue on
259                                    //outerLoopOf(thisLoop).
260  LandInformation() : landBlk(NULL) {}
261};
262
263} //end of namespace llvmCFGStruct
264
265//===----------------------------------------------------------------------===//
266//
267// CFGStructurizer
268//
269//===----------------------------------------------------------------------===//
270
271namespace llvmCFGStruct
272{
273// bixia TODO: port it to BasicBlock, not just MachineBasicBlock.
274template<class PassT>
275class  CFGStructurizer
276{
277public:
278  typedef enum {
279    Not_SinglePath = 0,
280    SinglePath_InPath = 1,
281    SinglePath_NotInPath = 2
282  } PathToKind;
283
284public:
285  typedef typename PassT::InstructionType         InstrT;
286  typedef typename PassT::FunctionType            FuncT;
287  typedef typename PassT::DominatortreeType       DomTreeT;
288  typedef typename PassT::PostDominatortreeType   PostDomTreeT;
289  typedef typename PassT::DomTreeNodeType         DomTreeNodeT;
290  typedef typename PassT::LoopinfoType            LoopInfoT;
291
292  typedef GraphTraits<FuncT *>                    FuncGTraits;
293  //typedef FuncGTraits::nodes_iterator BlockIterator;
294  typedef typename FuncT::iterator                BlockIterator;
295
296  typedef typename FuncGTraits::NodeType          BlockT;
297  typedef GraphTraits<BlockT *>                   BlockGTraits;
298  typedef GraphTraits<Inverse<BlockT *> >         InvBlockGTraits;
299  //typedef BlockGTraits::succ_iterator InstructionIterator;
300  typedef typename BlockT::iterator               InstrIterator;
301
302  typedef CFGStructTraits<PassT>                  CFGTraits;
303  typedef BlockInformation<InstrT>                BlockInfo;
304  typedef std::map<BlockT *, BlockInfo *>         BlockInfoMap;
305
306  typedef int                                     RegiT;
307  typedef typename PassT::LoopType                LoopT;
308  typedef LandInformation<BlockT, InstrT, RegiT>  LoopLandInfo;
309        typedef std::map<LoopT *, LoopLandInfo *> LoopLandInfoMap;
310        //landing info for loop break
311  typedef SmallVector<BlockT *, 32>               BlockTSmallerVector;
312
313public:
314  CFGStructurizer();
315  ~CFGStructurizer();
316
317  /// Perform the CFG structurization
318  bool run(FuncT &Func, PassT &Pass);
319
320  /// Perform the CFG preparation
321  bool prepare(FuncT &Func, PassT &Pass);
322
323private:
324  void   orderBlocks();
325  void   printOrderedBlocks(llvm::raw_ostream &OS);
326  int patternMatch(BlockT *CurBlock);
327  int patternMatchGroup(BlockT *CurBlock);
328
329  int serialPatternMatch(BlockT *CurBlock);
330  int ifPatternMatch(BlockT *CurBlock);
331  int switchPatternMatch(BlockT *CurBlock);
332  int loopendPatternMatch(BlockT *CurBlock);
333  int loopPatternMatch(BlockT *CurBlock);
334
335  int loopbreakPatternMatch(LoopT *LoopRep, BlockT *LoopHeader);
336  int loopcontPatternMatch(LoopT *LoopRep, BlockT *LoopHeader);
337  //int loopWithoutBreak(BlockT *);
338
339  void handleLoopbreak (BlockT *ExitingBlock, LoopT *ExitingLoop,
340                        BlockT *ExitBlock, LoopT *exitLoop, BlockT *landBlock);
341  void handleLoopcontBlock(BlockT *ContingBlock, LoopT *contingLoop,
342                           BlockT *ContBlock, LoopT *contLoop);
343  bool isSameloopDetachedContbreak(BlockT *Src1Block, BlockT *Src2Block);
344  int handleJumpintoIf(BlockT *HeadBlock, BlockT *TrueBlock,
345                       BlockT *FalseBlock);
346  int handleJumpintoIfImp(BlockT *HeadBlock, BlockT *TrueBlock,
347                          BlockT *FalseBlock);
348  int improveSimpleJumpintoIf(BlockT *HeadBlock, BlockT *TrueBlock,
349                              BlockT *FalseBlock, BlockT **LandBlockPtr);
350  void showImproveSimpleJumpintoIf(BlockT *HeadBlock, BlockT *TrueBlock,
351                                   BlockT *FalseBlock, BlockT *LandBlock,
352                                   bool Detail = false);
353  PathToKind singlePathTo(BlockT *SrcBlock, BlockT *DstBlock,
354                          bool AllowSideEntry = true);
355  BlockT *singlePathEnd(BlockT *srcBlock, BlockT *DstBlock,
356                        bool AllowSideEntry = true);
357  int cloneOnSideEntryTo(BlockT *PreBlock, BlockT *SrcBlock, BlockT *DstBlock);
358  void mergeSerialBlock(BlockT *DstBlock, BlockT *srcBlock);
359
360  void mergeIfthenelseBlock(InstrT *BranchInstr, BlockT *CurBlock,
361                            BlockT *TrueBlock, BlockT *FalseBlock,
362                            BlockT *LandBlock);
363  void mergeLooplandBlock(BlockT *DstBlock, LoopLandInfo *LoopLand);
364  void mergeLoopbreakBlock(BlockT *ExitingBlock, BlockT *ExitBlock,
365                           BlockT *ExitLandBlock, RegiT SetReg);
366  void settleLoopcontBlock(BlockT *ContingBlock, BlockT *ContBlock,
367                           RegiT SetReg);
368  BlockT *relocateLoopcontBlock(LoopT *ParentLoopRep, LoopT *LoopRep,
369                                std::set<BlockT*> &ExitBlockSet,
370                                BlockT *ExitLandBlk);
371  BlockT *addLoopEndbranchBlock(LoopT *LoopRep,
372                                BlockTSmallerVector &ExitingBlocks,
373                                BlockTSmallerVector &ExitBlocks);
374  BlockT *normalizeInfiniteLoopExit(LoopT *LoopRep);
375  void removeUnconditionalBranch(BlockT *SrcBlock);
376  void removeRedundantConditionalBranch(BlockT *SrcBlock);
377  void addDummyExitBlock(SmallVector<BlockT *, DEFAULT_VEC_SLOTS> &RetBlocks);
378
379  void removeSuccessor(BlockT *SrcBlock);
380  BlockT *cloneBlockForPredecessor(BlockT *CurBlock, BlockT *PredBlock);
381  BlockT *exitingBlock2ExitBlock (LoopT *LoopRep, BlockT *exitingBlock);
382
383  void migrateInstruction(BlockT *SrcBlock, BlockT *DstBlock,
384                          InstrIterator InsertPos);
385
386  void recordSccnum(BlockT *SrcBlock, int SCCNum);
387  int getSCCNum(BlockT *srcBlk);
388
389  void retireBlock(BlockT *DstBlock, BlockT *SrcBlock);
390  bool isRetiredBlock(BlockT *SrcBlock);
391  bool isActiveLoophead(BlockT *CurBlock);
392  bool needMigrateBlock(BlockT *Block);
393
394  BlockT *recordLoopLandBlock(LoopT *LoopRep, BlockT *LandBlock,
395                              BlockTSmallerVector &exitBlocks,
396                              std::set<BlockT*> &ExitBlockSet);
397  void setLoopLandBlock(LoopT *LoopRep, BlockT *Block = NULL);
398  BlockT *getLoopLandBlock(LoopT *LoopRep);
399  LoopLandInfo *getLoopLandInfo(LoopT *LoopRep);
400
401  void addLoopBreakOnReg(LoopT *LoopRep, RegiT RegNum);
402  void addLoopContOnReg(LoopT *LoopRep, RegiT RegNum);
403  void addLoopBreakInitReg(LoopT *LoopRep, RegiT RegNum);
404  void addLoopContInitReg(LoopT *LoopRep, RegiT RegNum);
405  void addLoopEndbranchInitReg(LoopT *LoopRep, RegiT RegNum);
406
407  bool hasBackEdge(BlockT *curBlock);
408  unsigned getLoopDepth  (LoopT *LoopRep);
409  int countActiveBlock(
410    typename SmallVector<BlockT *, DEFAULT_VEC_SLOTS>::const_iterator IterStart,
411    typename SmallVector<BlockT *, DEFAULT_VEC_SLOTS>::const_iterator IterEnd);
412    BlockT *findNearestCommonPostDom(std::set<BlockT *>&);
413  BlockT *findNearestCommonPostDom(BlockT *Block1, BlockT *Block2);
414
415private:
416  DomTreeT *domTree;
417  PostDomTreeT *postDomTree;
418  LoopInfoT *loopInfo;
419  PassT *passRep;
420  FuncT *funcRep;
421
422  BlockInfoMap blockInfoMap;
423  LoopLandInfoMap loopLandInfoMap;
424  SmallVector<BlockT *, DEFAULT_VEC_SLOTS> orderedBlks;
425
426};  //template class CFGStructurizer
427
428template<class PassT> CFGStructurizer<PassT>::CFGStructurizer()
429  : domTree(NULL), postDomTree(NULL), loopInfo(NULL) {
430}
431
432template<class PassT> CFGStructurizer<PassT>::~CFGStructurizer() {
433  for (typename BlockInfoMap::iterator I = blockInfoMap.begin(),
434       E = blockInfoMap.end(); I != E; ++I) {
435    delete I->second;
436  }
437}
438
439template<class PassT>
440bool CFGStructurizer<PassT>::prepare(FuncT &func, PassT &pass) {
441  passRep = &pass;
442  funcRep = &func;
443
444  bool changed = false;
445  //func.RenumberBlocks();
446
447  //to do, if not reducible flow graph, make it so ???
448
449  if (DEBUGME) {
450        errs() << "AMDILCFGStructurizer::prepare\n";
451    //func.viewCFG();
452    //func.viewCFGOnly();
453    //func.dump();
454  }
455
456  //FIXME: gcc complains on this.
457  //domTree = &pass.getAnalysis<DomTreeT>();
458      //domTree = CFGTraits::getDominatorTree(pass);
459      //if (DEBUGME) {
460      //    domTree->print(errs());
461    //}
462
463  //FIXME: gcc complains on this.
464  //domTree = &pass.getAnalysis<DomTreeT>();
465      //postDomTree = CFGTraits::getPostDominatorTree(pass);
466      //if (DEBUGME) {
467      //   postDomTree->print(errs());
468    //}
469
470  //FIXME: gcc complains on this.
471  //loopInfo = &pass.getAnalysis<LoopInfoT>();
472  loopInfo = CFGTraits::getLoopInfo(pass);
473  if (DEBUGME) {
474    errs() << "LoopInfo:\n";
475    PrintLoopinfo(*loopInfo, errs());
476  }
477
478  orderBlocks();
479  if (DEBUGME) {
480    errs() << "Ordered blocks:\n";
481    printOrderedBlocks(errs());
482  }
483
484  SmallVector<BlockT *, DEFAULT_VEC_SLOTS> retBlks;
485
486  for (typename LoopInfoT::iterator iter = loopInfo->begin(),
487       iterEnd = loopInfo->end();
488       iter != iterEnd; ++iter) {
489    LoopT* loopRep = (*iter);
490    BlockTSmallerVector exitingBlks;
491    loopRep->getExitingBlocks(exitingBlks);
492
493    if (exitingBlks.size() == 0) {
494      BlockT* dummyExitBlk = normalizeInfiniteLoopExit(loopRep);
495      if (dummyExitBlk != NULL)
496        retBlks.push_back(dummyExitBlk);
497    }
498  }
499
500  // Remove unconditional branch instr.
501  // Add dummy exit block iff there are multiple returns.
502
503  for (typename SmallVector<BlockT *, DEFAULT_VEC_SLOTS>::const_iterator
504       iterBlk = orderedBlks.begin(), iterEndBlk = orderedBlks.end();
505       iterBlk != iterEndBlk;
506       ++iterBlk) {
507    BlockT *curBlk = *iterBlk;
508    removeUnconditionalBranch(curBlk);
509    removeRedundantConditionalBranch(curBlk);
510    if (CFGTraits::isReturnBlock(curBlk)) {
511      retBlks.push_back(curBlk);
512    }
513    assert(curBlk->succ_size() <= 2);
514    //assert(curBlk->size() > 0);
515    //removeEmptyBlock(curBlk) ??
516  } //for
517
518  if (retBlks.size() >= 2) {
519    addDummyExitBlock(retBlks);
520    changed = true;
521  }
522
523  return changed;
524} //CFGStructurizer::prepare
525
526template<class PassT>
527bool CFGStructurizer<PassT>::run(FuncT &func, PassT &pass) {
528  passRep = &pass;
529  funcRep = &func;
530
531  //func.RenumberBlocks();
532
533  //Assume reducible CFG...
534  if (DEBUGME) {
535    errs() << "AMDILCFGStructurizer::run\n";
536    //errs() << func.getFunction()->getNameStr() << "\n";
537    func.viewCFG();
538    //func.viewCFGOnly();
539    //func.dump();
540  }
541
542#if 1
543  //FIXME: gcc complains on this.
544  //domTree = &pass.getAnalysis<DomTreeT>();
545  domTree = CFGTraits::getDominatorTree(pass);
546  if (DEBUGME) {
547    domTree->print(errs(), (const llvm::Module*)0);
548  }
549#endif
550
551  //FIXME: gcc complains on this.
552  //domTree = &pass.getAnalysis<DomTreeT>();
553  postDomTree = CFGTraits::getPostDominatorTree(pass);
554  if (DEBUGME) {
555    postDomTree->print(errs());
556  }
557
558  //FIXME: gcc complains on this.
559  //loopInfo = &pass.getAnalysis<LoopInfoT>();
560  loopInfo = CFGTraits::getLoopInfo(pass);
561  if (DEBUGME) {
562    errs() << "LoopInfo:\n";
563    PrintLoopinfo(*loopInfo, errs());
564  }
565
566  orderBlocks();
567//#define STRESSTEST
568#ifdef STRESSTEST
569  //Use the worse block ordering to test the algorithm.
570  ReverseVector(orderedBlks);
571#endif
572
573  if (DEBUGME) {
574    errs() << "Ordered blocks:\n";
575    printOrderedBlocks(errs());
576  }
577  int numIter = 0;
578  bool finish = false;
579  BlockT *curBlk;
580  bool makeProgress = false;
581  int numRemainedBlk = countActiveBlock(orderedBlks.begin(),
582                                        orderedBlks.end());
583
584  do {
585    ++numIter;
586    if (DEBUGME) {
587      errs() << "numIter = " << numIter
588             << ", numRemaintedBlk = " << numRemainedBlk << "\n";
589    }
590
591    typename SmallVector<BlockT *, DEFAULT_VEC_SLOTS>::const_iterator
592      iterBlk = orderedBlks.begin();
593    typename SmallVector<BlockT *, DEFAULT_VEC_SLOTS>::const_iterator
594      iterBlkEnd = orderedBlks.end();
595
596    typename SmallVector<BlockT *, DEFAULT_VEC_SLOTS>::const_iterator
597      sccBeginIter = iterBlk;
598    BlockT *sccBeginBlk = NULL;
599    int sccNumBlk = 0;  // The number of active blocks, init to a
600                        // maximum possible number.
601    int sccNumIter;     // Number of iteration in this SCC.
602
603    while (iterBlk != iterBlkEnd) {
604      curBlk = *iterBlk;
605
606      if (sccBeginBlk == NULL) {
607        sccBeginIter = iterBlk;
608        sccBeginBlk = curBlk;
609        sccNumIter = 0;
610        sccNumBlk = numRemainedBlk; // Init to maximum possible number.
611        if (DEBUGME) {
612              errs() << "start processing SCC" << getSCCNum(sccBeginBlk);
613              errs() << "\n";
614        }
615      }
616
617      if (!isRetiredBlock(curBlk)) {
618        patternMatch(curBlk);
619      }
620
621      ++iterBlk;
622
623      bool contNextScc = true;
624      if (iterBlk == iterBlkEnd
625          || getSCCNum(sccBeginBlk) != getSCCNum(*iterBlk)) {
626        // Just finish one scc.
627        ++sccNumIter;
628        int sccRemainedNumBlk = countActiveBlock(sccBeginIter, iterBlk);
629        if (sccRemainedNumBlk != 1 && sccRemainedNumBlk >= sccNumBlk) {
630          if (DEBUGME) {
631            errs() << "Can't reduce SCC " << getSCCNum(curBlk)
632                   << ", sccNumIter = " << sccNumIter;
633            errs() << "doesn't make any progress\n";
634          }
635          contNextScc = true;
636        } else if (sccRemainedNumBlk != 1 && sccRemainedNumBlk < sccNumBlk) {
637          sccNumBlk = sccRemainedNumBlk;
638          iterBlk = sccBeginIter;
639          contNextScc = false;
640          if (DEBUGME) {
641            errs() << "repeat processing SCC" << getSCCNum(curBlk)
642                   << "sccNumIter = " << sccNumIter << "\n";
643            func.viewCFG();
644            //func.viewCFGOnly();
645          }
646        } else {
647          // Finish the current scc.
648          contNextScc = true;
649        }
650      } else {
651        // Continue on next component in the current scc.
652        contNextScc = false;
653      }
654
655      if (contNextScc) {
656        sccBeginBlk = NULL;
657      }
658    } //while, "one iteration" over the function.
659
660    BlockT *entryBlk = FuncGTraits::nodes_begin(&func);
661    if (entryBlk->succ_size() == 0) {
662      finish = true;
663      if (DEBUGME) {
664        errs() << "Reduce to one block\n";
665      }
666    } else {
667      int newnumRemainedBlk
668        = countActiveBlock(orderedBlks.begin(), orderedBlks.end());
669      // consider cloned blocks ??
670      if (newnumRemainedBlk == 1 || newnumRemainedBlk < numRemainedBlk) {
671        makeProgress = true;
672        numRemainedBlk = newnumRemainedBlk;
673      } else {
674        makeProgress = false;
675        if (DEBUGME) {
676          errs() << "No progress\n";
677        }
678      }
679    }
680  } while (!finish && makeProgress);
681
682  // Misc wrap up to maintain the consistency of the Function representation.
683  CFGTraits::wrapup(FuncGTraits::nodes_begin(&func));
684
685  // Detach retired Block, release memory.
686  for (typename BlockInfoMap::iterator iterMap = blockInfoMap.begin(),
687       iterEndMap = blockInfoMap.end(); iterMap != iterEndMap; ++iterMap) {
688    if ((*iterMap).second && (*iterMap).second->isRetired) {
689      assert(((*iterMap).first)->getNumber() != -1);
690      if (DEBUGME) {
691        errs() << "Erase BB" << ((*iterMap).first)->getNumber() << "\n";
692      }
693      (*iterMap).first->eraseFromParent();  //Remove from the parent Function.
694    }
695    delete (*iterMap).second;
696  }
697  blockInfoMap.clear();
698
699  // clear loopLandInfoMap
700  for (typename LoopLandInfoMap::iterator iterMap = loopLandInfoMap.begin(),
701       iterEndMap = loopLandInfoMap.end(); iterMap != iterEndMap; ++iterMap) {
702    delete (*iterMap).second;
703  }
704  loopLandInfoMap.clear();
705
706  if (DEBUGME) {
707    func.viewCFG();
708    //func.dump();
709  }
710
711  if (!finish) {
712    MachineFunction *MF = &func;
713    AMDILMachineFunctionInfo *mMFI =
714      MF->getInfo<AMDILMachineFunctionInfo>();
715    mMFI->addErrorMsg(amd::CompilerErrorMessage[IRREDUCIBLE_CF]);
716  }
717
718  return true;
719} //CFGStructurizer::run
720
721/// Print the ordered Blocks.
722///
723template<class PassT>
724void CFGStructurizer<PassT>::printOrderedBlocks(llvm::raw_ostream &os) {
725  size_t i = 0;
726  for (typename SmallVector<BlockT *, DEFAULT_VEC_SLOTS>::const_iterator
727      iterBlk = orderedBlks.begin(), iterBlkEnd = orderedBlks.end();
728       iterBlk != iterBlkEnd;
729       ++iterBlk, ++i) {
730    os << "BB" << (*iterBlk)->getNumber();
731    os << "(" << getSCCNum(*iterBlk) << "," << (*iterBlk)->size() << ")";
732    if (i != 0 && i % 10 == 0) {
733      os << "\n";
734    } else {
735      os << " ";
736    }
737  }
738} //printOrderedBlocks
739
740/// Compute the reversed DFS post order of Blocks
741///
742template<class PassT> void CFGStructurizer<PassT>::orderBlocks() {
743  int sccNum = 0;
744  BlockT *bb;
745  for (scc_iterator<FuncT *> sccIter = scc_begin(funcRep),
746       sccEnd = scc_end(funcRep); sccIter != sccEnd; ++sccIter, ++sccNum) {
747    std::vector<BlockT *> &sccNext = *sccIter;
748    for (typename std::vector<BlockT *>::const_iterator
749         blockIter = sccNext.begin(), blockEnd = sccNext.end();
750         blockIter != blockEnd; ++blockIter) {
751      bb = *blockIter;
752      orderedBlks.push_back(bb);
753      recordSccnum(bb, sccNum);
754    }
755  }
756
757  //walk through all the block in func to check for unreachable
758  for (BlockIterator blockIter1 = FuncGTraits::nodes_begin(funcRep),
759       blockEnd1 = FuncGTraits::nodes_end(funcRep);
760       blockIter1 != blockEnd1; ++blockIter1) {
761    BlockT *bb = &(*blockIter1);
762    sccNum = getSCCNum(bb);
763    if (sccNum == INVALIDSCCNUM) {
764      errs() << "unreachable block BB" << bb->getNumber() << "\n";
765    }
766  } //end of for
767} //orderBlocks
768
769template<class PassT> int CFGStructurizer<PassT>::patternMatch(BlockT *curBlk) {
770  int numMatch = 0;
771  int curMatch;
772
773  if (DEBUGME) {
774        errs() << "Begin patternMatch BB" << curBlk->getNumber() << "\n";
775  }
776
777  while ((curMatch = patternMatchGroup(curBlk)) > 0) {
778    numMatch += curMatch;
779  }
780
781  if (DEBUGME) {
782        errs() << "End patternMatch BB" << curBlk->getNumber()
783      << ", numMatch = " << numMatch << "\n";
784  }
785
786  return numMatch;
787} //patternMatch
788
789template<class PassT>
790int CFGStructurizer<PassT>::patternMatchGroup(BlockT *curBlk) {
791  int numMatch = 0;
792  numMatch += serialPatternMatch(curBlk);
793  numMatch += ifPatternMatch(curBlk);
794  //numMatch += switchPatternMatch(curBlk);
795  numMatch += loopendPatternMatch(curBlk);
796  numMatch += loopPatternMatch(curBlk);
797  return numMatch;
798}//patternMatchGroup
799
800template<class PassT>
801int CFGStructurizer<PassT>::serialPatternMatch(BlockT *curBlk) {
802  if (curBlk->succ_size() != 1) {
803    return 0;
804  }
805
806  BlockT *childBlk = *curBlk->succ_begin();
807  if (childBlk->pred_size() != 1 || isActiveLoophead(childBlk)) {
808    return 0;
809  }
810
811  mergeSerialBlock(curBlk, childBlk);
812  ++numSerialPatternMatch;
813  return 1;
814} //serialPatternMatch
815
816template<class PassT>
817int CFGStructurizer<PassT>::ifPatternMatch(BlockT *curBlk) {
818  //two edges
819  if (curBlk->succ_size() != 2) {
820    return 0;
821  }
822
823  if (hasBackEdge(curBlk)) {
824    return 0;
825  }
826
827  InstrT *branchInstr = CFGTraits::getNormalBlockBranchInstr(curBlk);
828  if (branchInstr == NULL) {
829    return 0;
830  }
831
832  assert(CFGTraits::isCondBranch(branchInstr));
833
834  BlockT *trueBlk = CFGTraits::getTrueBranch(branchInstr);
835  BlockT *falseBlk = CFGTraits::getFalseBranch(curBlk, branchInstr);
836  BlockT *landBlk;
837  int cloned = 0;
838
839  // TODO: Simplify
840  if (trueBlk->succ_size() == 1 && falseBlk->succ_size() == 1
841    && *trueBlk->succ_begin() == *falseBlk->succ_begin()) {
842    landBlk = *trueBlk->succ_begin();
843  } else if (trueBlk->succ_size() == 0 && falseBlk->succ_size() == 0) {
844    landBlk = NULL;
845  } else if (trueBlk->succ_size() == 1 && *trueBlk->succ_begin() == falseBlk) {
846    landBlk = falseBlk;
847    falseBlk = NULL;
848  } else if (falseBlk->succ_size() == 1
849             && *falseBlk->succ_begin() == trueBlk) {
850    landBlk = trueBlk;
851    trueBlk = NULL;
852  } else if (falseBlk->succ_size() == 1
853             && isSameloopDetachedContbreak(trueBlk, falseBlk)) {
854    landBlk = *falseBlk->succ_begin();
855  } else if (trueBlk->succ_size() == 1
856    && isSameloopDetachedContbreak(falseBlk, trueBlk)) {
857    landBlk = *trueBlk->succ_begin();
858  } else {
859    return handleJumpintoIf(curBlk, trueBlk, falseBlk);
860  }
861
862  // improveSimpleJumpinfoIf can handle the case where landBlk == NULL but the
863  // new BB created for landBlk==NULL may introduce new challenge to the
864  // reduction process.
865  if (landBlk != NULL &&
866      ((trueBlk && trueBlk->pred_size() > 1)
867      || (falseBlk && falseBlk->pred_size() > 1))) {
868     cloned += improveSimpleJumpintoIf(curBlk, trueBlk, falseBlk, &landBlk);
869  }
870
871  if (trueBlk && trueBlk->pred_size() > 1) {
872    trueBlk = cloneBlockForPredecessor(trueBlk, curBlk);
873    ++cloned;
874  }
875
876  if (falseBlk && falseBlk->pred_size() > 1) {
877    falseBlk = cloneBlockForPredecessor(falseBlk, curBlk);
878    ++cloned;
879  }
880
881  mergeIfthenelseBlock(branchInstr, curBlk, trueBlk, falseBlk, landBlk);
882
883  ++numIfPatternMatch;
884
885  numClonedBlock += cloned;
886
887  return 1 + cloned;
888} //ifPatternMatch
889
890template<class PassT>
891int CFGStructurizer<PassT>::switchPatternMatch(BlockT *curBlk) {
892  return 0;
893} //switchPatternMatch
894
895template<class PassT>
896int CFGStructurizer<PassT>::loopendPatternMatch(BlockT *curBlk) {
897  LoopT *loopRep = loopInfo->getLoopFor(curBlk);
898  typename std::vector<LoopT *> nestedLoops;
899  while (loopRep) {
900    nestedLoops.push_back(loopRep);
901    loopRep = loopRep->getParentLoop();
902  }
903
904  if (nestedLoops.size() == 0) {
905    return 0;
906  }
907
908  // Process nested loop outside->inside, so "continue" to a outside loop won't
909  // be mistaken as "break" of the current loop.
910  int num = 0;
911  for (typename std::vector<LoopT *>::reverse_iterator
912       iter = nestedLoops.rbegin(), iterEnd = nestedLoops.rend();
913       iter != iterEnd; ++iter) {
914    loopRep = *iter;
915
916    if (getLoopLandBlock(loopRep) != NULL) {
917      continue;
918    }
919
920    BlockT *loopHeader = loopRep->getHeader();
921
922    int numBreak = loopbreakPatternMatch(loopRep, loopHeader);
923
924    if (numBreak == -1) {
925      break;
926    }
927
928    int numCont = loopcontPatternMatch(loopRep, loopHeader);
929    num += numBreak + numCont;
930  }
931
932  return num;
933} //loopendPatternMatch
934
935template<class PassT>
936int CFGStructurizer<PassT>::loopPatternMatch(BlockT *curBlk) {
937  if (curBlk->succ_size() != 0) {
938    return 0;
939  }
940
941  int numLoop = 0;
942  LoopT *loopRep = loopInfo->getLoopFor(curBlk);
943  while (loopRep && loopRep->getHeader() == curBlk) {
944    LoopLandInfo *loopLand = getLoopLandInfo(loopRep);
945    if (loopLand) {
946      BlockT *landBlk = loopLand->landBlk;
947      assert(landBlk);
948      if (!isRetiredBlock(landBlk)) {
949        mergeLooplandBlock(curBlk, loopLand);
950        ++numLoop;
951      }
952    }
953    loopRep = loopRep->getParentLoop();
954  }
955
956  numLoopPatternMatch += numLoop;
957
958  return numLoop;
959} //loopPatternMatch
960
961template<class PassT>
962int CFGStructurizer<PassT>::loopbreakPatternMatch(LoopT *loopRep,
963                                                  BlockT *loopHeader) {
964  BlockTSmallerVector exitingBlks;
965  loopRep->getExitingBlocks(exitingBlks);
966
967  if (DEBUGME) {
968    errs() << "Loop has " << exitingBlks.size() << " exiting blocks\n";
969  }
970
971  if (exitingBlks.size() == 0) {
972    setLoopLandBlock(loopRep);
973    return 0;
974  }
975
976  // Compute the corresponding exitBlks and exit block set.
977  BlockTSmallerVector exitBlks;
978  std::set<BlockT *> exitBlkSet;
979  for (typename BlockTSmallerVector::const_iterator iter = exitingBlks.begin(),
980       iterEnd = exitingBlks.end(); iter != iterEnd; ++iter) {
981    BlockT *exitingBlk = *iter;
982    BlockT *exitBlk = exitingBlock2ExitBlock(loopRep, exitingBlk);
983    exitBlks.push_back(exitBlk);
984    exitBlkSet.insert(exitBlk);  //non-duplicate insert
985  }
986
987  assert(exitBlkSet.size() > 0);
988  assert(exitBlks.size() == exitingBlks.size());
989
990  if (DEBUGME) {
991    errs() << "Loop has " << exitBlkSet.size() << " exit blocks\n";
992  }
993
994  // Find exitLandBlk.
995  BlockT *exitLandBlk = NULL;
996  int numCloned = 0;
997  int numSerial = 0;
998
999  if (exitBlkSet.size() == 1)
1000  {
1001    exitLandBlk = *exitBlkSet.begin();
1002  } else {
1003    exitLandBlk = findNearestCommonPostDom(exitBlkSet);
1004
1005    if (exitLandBlk == NULL) {
1006      return -1;
1007    }
1008
1009    bool allInPath = true;
1010    bool allNotInPath = true;
1011    for (typename std::set<BlockT*>::const_iterator
1012         iter = exitBlkSet.begin(),
1013         iterEnd = exitBlkSet.end();
1014         iter != iterEnd; ++iter) {
1015      BlockT *exitBlk = *iter;
1016
1017      PathToKind pathKind = singlePathTo(exitBlk, exitLandBlk, true);
1018      if (DEBUGME) {
1019        errs() << "BB" << exitBlk->getNumber()
1020               << " to BB" << exitLandBlk->getNumber() << " PathToKind="
1021               << pathKind << "\n";
1022      }
1023
1024      allInPath = allInPath && (pathKind == SinglePath_InPath);
1025      allNotInPath = allNotInPath && (pathKind == SinglePath_NotInPath);
1026
1027      if (!allInPath && !allNotInPath) {
1028        if (DEBUGME) {
1029              errs() << "singlePath check fail\n";
1030        }
1031        return -1;
1032      }
1033    } // check all exit blocks
1034
1035    if (allNotInPath) {
1036#if 1
1037
1038      // TODO: Simplify, maybe separate function?
1039      //funcRep->viewCFG();
1040      LoopT *parentLoopRep = loopRep->getParentLoop();
1041      BlockT *parentLoopHeader = NULL;
1042      if (parentLoopRep)
1043        parentLoopHeader = parentLoopRep->getHeader();
1044
1045      if (exitLandBlk == parentLoopHeader &&
1046          (exitLandBlk = relocateLoopcontBlock(parentLoopRep,
1047                                               loopRep,
1048                                               exitBlkSet,
1049                                               exitLandBlk)) != NULL) {
1050        if (DEBUGME) {
1051          errs() << "relocateLoopcontBlock success\n";
1052        }
1053      } else if ((exitLandBlk = addLoopEndbranchBlock(loopRep,
1054                                                      exitingBlks,
1055                                                      exitBlks)) != NULL) {
1056        if (DEBUGME) {
1057          errs() << "insertEndbranchBlock success\n";
1058        }
1059      } else {
1060        if (DEBUGME) {
1061          errs() << "loop exit fail\n";
1062        }
1063        return -1;
1064      }
1065#else
1066      return -1;
1067#endif
1068    }
1069
1070    // Handle side entry to exit path.
1071    exitBlks.clear();
1072    exitBlkSet.clear();
1073    for (typename BlockTSmallerVector::iterator iterExiting =
1074           exitingBlks.begin(),
1075         iterExitingEnd = exitingBlks.end();
1076         iterExiting != iterExitingEnd; ++iterExiting) {
1077      BlockT *exitingBlk = *iterExiting;
1078      BlockT *exitBlk = exitingBlock2ExitBlock(loopRep, exitingBlk);
1079      BlockT *newExitBlk = exitBlk;
1080
1081      if (exitBlk != exitLandBlk && exitBlk->pred_size() > 1) {
1082        newExitBlk = cloneBlockForPredecessor(exitBlk, exitingBlk);
1083        ++numCloned;
1084      }
1085
1086      numCloned += cloneOnSideEntryTo(exitingBlk, newExitBlk, exitLandBlk);
1087
1088      exitBlks.push_back(newExitBlk);
1089      exitBlkSet.insert(newExitBlk);
1090    }
1091
1092    for (typename BlockTSmallerVector::iterator iterExit = exitBlks.begin(),
1093         iterExitEnd = exitBlks.end();
1094         iterExit != iterExitEnd; ++iterExit) {
1095      BlockT *exitBlk = *iterExit;
1096      numSerial += serialPatternMatch(exitBlk);
1097    }
1098
1099    for (typename BlockTSmallerVector::iterator iterExit = exitBlks.begin(),
1100         iterExitEnd = exitBlks.end();
1101         iterExit != iterExitEnd; ++iterExit) {
1102      BlockT *exitBlk = *iterExit;
1103      if (exitBlk->pred_size() > 1) {
1104        if (exitBlk != exitLandBlk) {
1105          return -1;
1106        }
1107      } else {
1108        if (exitBlk != exitLandBlk &&
1109            (exitBlk->succ_size() != 1 ||
1110            *exitBlk->succ_begin() != exitLandBlk)) {
1111          return -1;
1112        }
1113      }
1114    }
1115  } // else
1116
1117  // LoopT *exitLandLoop = loopInfo->getLoopFor(exitLandBlk);
1118  exitLandBlk = recordLoopLandBlock(loopRep, exitLandBlk, exitBlks, exitBlkSet);
1119
1120  // Fold break into the breaking block. Leverage across level breaks.
1121  assert(exitingBlks.size() == exitBlks.size());
1122  for (typename BlockTSmallerVector::const_iterator iterExit = exitBlks.begin(),
1123       iterExiting = exitingBlks.begin(), iterExitEnd = exitBlks.end();
1124       iterExit != iterExitEnd; ++iterExit, ++iterExiting) {
1125    BlockT *exitBlk = *iterExit;
1126    BlockT *exitingBlk = *iterExiting;
1127    assert(exitBlk->pred_size() == 1 || exitBlk == exitLandBlk);
1128    LoopT *exitingLoop = loopInfo->getLoopFor(exitingBlk);
1129    handleLoopbreak(exitingBlk, exitingLoop, exitBlk, loopRep, exitLandBlk);
1130  }
1131
1132  int numBreak = static_cast<int>(exitingBlks.size());
1133  numLoopbreakPatternMatch += numBreak;
1134  numClonedBlock += numCloned;
1135  return numBreak + numSerial + numCloned;
1136} //loopbreakPatternMatch
1137
1138template<class PassT>
1139int CFGStructurizer<PassT>::loopcontPatternMatch(LoopT *loopRep,
1140                                                 BlockT *loopHeader) {
1141  int numCont = 0;
1142  SmallVector<BlockT *, DEFAULT_VEC_SLOTS> contBlk;
1143  for (typename InvBlockGTraits::ChildIteratorType iter =
1144       InvBlockGTraits::child_begin(loopHeader),
1145       iterEnd = InvBlockGTraits::child_end(loopHeader);
1146       iter != iterEnd; ++iter) {
1147    BlockT *curBlk = *iter;
1148    if (loopRep->contains(curBlk)) {
1149      handleLoopcontBlock(curBlk, loopInfo->getLoopFor(curBlk),
1150                          loopHeader, loopRep);
1151      contBlk.push_back(curBlk);
1152      ++numCont;
1153    }
1154  }
1155
1156  for (typename SmallVector<BlockT *, DEFAULT_VEC_SLOTS>::iterator
1157       iter = contBlk.begin(), iterEnd = contBlk.end();
1158       iter != iterEnd; ++iter) {
1159    (*iter)->removeSuccessor(loopHeader);
1160  }
1161
1162  numLoopcontPatternMatch += numCont;
1163
1164  return numCont;
1165} //loopcontPatternMatch
1166
1167
1168template<class PassT>
1169bool CFGStructurizer<PassT>::isSameloopDetachedContbreak(BlockT *src1Blk,
1170                                                         BlockT *src2Blk) {
1171  // return true iff src1Blk->succ_size() == 0 && src1Blk and src2Blk are in the
1172  // same loop with LoopLandInfo without explicitly keeping track of
1173  // loopContBlks and loopBreakBlks, this is a method to get the information.
1174  //
1175  if (src1Blk->succ_size() == 0) {
1176    LoopT *loopRep = loopInfo->getLoopFor(src1Blk);
1177    if (loopRep != NULL && loopRep == loopInfo->getLoopFor(src2Blk)) {
1178      LoopLandInfo *&theEntry = loopLandInfoMap[loopRep];
1179      if (theEntry != NULL) {
1180        if (DEBUGME) {
1181          errs() << "isLoopContBreakBlock yes src1 = BB"
1182                 << src1Blk->getNumber()
1183                 << " src2 = BB" << src2Blk->getNumber() << "\n";
1184        }
1185        return true;
1186      }
1187    }
1188  }
1189  return false;
1190}  //isSameloopDetachedContbreak
1191
1192template<class PassT>
1193int CFGStructurizer<PassT>::handleJumpintoIf(BlockT *headBlk,
1194                                             BlockT *trueBlk,
1195                                             BlockT *falseBlk) {
1196  int num = handleJumpintoIfImp(headBlk, trueBlk, falseBlk);
1197  if (num == 0) {
1198    if (DEBUGME) {
1199      errs() << "handleJumpintoIf swap trueBlk and FalseBlk" << "\n";
1200    }
1201    num = handleJumpintoIfImp(headBlk, falseBlk, trueBlk);
1202  }
1203  return num;
1204}
1205
1206template<class PassT>
1207int CFGStructurizer<PassT>::handleJumpintoIfImp(BlockT *headBlk,
1208                                                BlockT *trueBlk,
1209                                                BlockT *falseBlk) {
1210  int num = 0;
1211  BlockT *downBlk;
1212
1213  //trueBlk could be the common post dominator
1214  downBlk = trueBlk;
1215
1216  if (DEBUGME) {
1217    errs() << "handleJumpintoIfImp head = BB" << headBlk->getNumber()
1218           << " true = BB" << trueBlk->getNumber()
1219           << ", numSucc=" << trueBlk->succ_size()
1220           << " false = BB" << falseBlk->getNumber() << "\n";
1221  }
1222
1223  while (downBlk) {
1224    if (DEBUGME) {
1225      errs() << "check down = BB" << downBlk->getNumber();
1226    }
1227
1228    if (//postDomTree->dominates(downBlk, falseBlk) &&
1229        singlePathTo(falseBlk, downBlk) == SinglePath_InPath) {
1230      if (DEBUGME) {
1231        errs() << " working\n";
1232      }
1233
1234      num += cloneOnSideEntryTo(headBlk, trueBlk, downBlk);
1235      num += cloneOnSideEntryTo(headBlk, falseBlk, downBlk);
1236
1237      numClonedBlock += num;
1238      num += serialPatternMatch(*headBlk->succ_begin());
1239      num += serialPatternMatch(*(++headBlk->succ_begin()));
1240      num += ifPatternMatch(headBlk);
1241      assert(num > 0); //
1242
1243      break;
1244    }
1245    if (DEBUGME) {
1246      errs() << " not working\n";
1247    }
1248    downBlk = (downBlk->succ_size() == 1) ? (*downBlk->succ_begin()) : NULL;
1249  } // walk down the postDomTree
1250
1251  return num;
1252} //handleJumpintoIf
1253
1254template<class PassT>
1255void CFGStructurizer<PassT>::showImproveSimpleJumpintoIf(BlockT *headBlk,
1256                                                         BlockT *trueBlk,
1257                                                         BlockT *falseBlk,
1258                                                         BlockT *landBlk,
1259                                                         bool detail) {
1260  errs() << "head = BB" << headBlk->getNumber()
1261         << " size = " << headBlk->size();
1262  if (detail) {
1263    errs() << "\n";
1264    headBlk->print(errs());
1265    errs() << "\n";
1266  }
1267
1268  if (trueBlk) {
1269    errs() << ", true = BB" << trueBlk->getNumber() << " size = "
1270           << trueBlk->size() << " numPred = " << trueBlk->pred_size();
1271    if (detail) {
1272      errs() << "\n";
1273      trueBlk->print(errs());
1274      errs() << "\n";
1275    }
1276  }
1277  if (falseBlk) {
1278    errs() << ", false = BB" << falseBlk->getNumber() << " size = "
1279           << falseBlk->size() << " numPred = " << falseBlk->pred_size();
1280    if (detail) {
1281      errs() << "\n";
1282      falseBlk->print(errs());
1283      errs() << "\n";
1284    }
1285  }
1286  if (landBlk) {
1287    errs() << ", land = BB" << landBlk->getNumber() << " size = "
1288           << landBlk->size() << " numPred = " << landBlk->pred_size();
1289    if (detail) {
1290      errs() << "\n";
1291      landBlk->print(errs());
1292      errs() << "\n";
1293    }
1294  }
1295
1296    errs() << "\n";
1297} //showImproveSimpleJumpintoIf
1298
1299template<class PassT>
1300int CFGStructurizer<PassT>::improveSimpleJumpintoIf(BlockT *headBlk,
1301                                                    BlockT *trueBlk,
1302                                                    BlockT *falseBlk,
1303                                                    BlockT **plandBlk) {
1304  bool migrateTrue = false;
1305  bool migrateFalse = false;
1306
1307  BlockT *landBlk = *plandBlk;
1308
1309  assert((trueBlk == NULL || trueBlk->succ_size() <= 1)
1310         && (falseBlk == NULL || falseBlk->succ_size() <= 1));
1311
1312  if (trueBlk == falseBlk) {
1313    return 0;
1314  }
1315
1316#if 0
1317  if (DEBUGME) {
1318    errs() << "improveSimpleJumpintoIf: ";
1319    showImproveSimpleJumpintoIf(headBlk, trueBlk, falseBlk, landBlk, 0);
1320  }
1321#endif
1322
1323  // unsigned landPredSize = landBlk ? landBlk->pred_size() : 0;
1324  // May consider the # landBlk->pred_size() as it represents the number of
1325  // assignment initReg = .. needed to insert.
1326  migrateTrue = needMigrateBlock(trueBlk);
1327  migrateFalse = needMigrateBlock(falseBlk);
1328
1329  if (!migrateTrue && !migrateFalse) {
1330    return 0;
1331  }
1332
1333  // If we need to migrate either trueBlk and falseBlk, migrate the rest that
1334  // have more than one predecessors.  without doing this, its predecessor
1335  // rather than headBlk will have undefined value in initReg.
1336  if (!migrateTrue && trueBlk && trueBlk->pred_size() > 1) {
1337    migrateTrue = true;
1338  }
1339  if (!migrateFalse && falseBlk && falseBlk->pred_size() > 1) {
1340    migrateFalse = true;
1341  }
1342
1343  if (DEBUGME) {
1344    errs() << "before improveSimpleJumpintoIf: ";
1345    showImproveSimpleJumpintoIf(headBlk, trueBlk, falseBlk, landBlk, 0);
1346    //showImproveSimpleJumpintoIf(headBlk, trueBlk, falseBlk, landBlk, 1);
1347  }
1348
1349  // org: headBlk => if () {trueBlk} else {falseBlk} => landBlk
1350  //
1351  // new: headBlk => if () {initReg = 1; org trueBlk branch} else
1352  //      {initReg = 0; org falseBlk branch }
1353  //      => landBlk => if (initReg) {org trueBlk} else {org falseBlk}
1354  //      => org landBlk
1355  //      if landBlk->pred_size() > 2, put the about if-else inside
1356  //      if (initReg !=2) {...}
1357  //
1358  // add initReg = initVal to headBlk
1359  unsigned initReg =
1360    funcRep->getRegInfo().createVirtualRegister(&AMDIL::GPRI32RegClass);
1361  if (!migrateTrue || !migrateFalse) {
1362    int initVal = migrateTrue ? 0 : 1;
1363    CFGTraits::insertAssignInstrBefore(headBlk, passRep, initReg, initVal);
1364  }
1365
1366  int numNewBlk = 0;
1367
1368  if (landBlk == NULL) {
1369    landBlk = funcRep->CreateMachineBasicBlock();
1370    funcRep->push_back(landBlk);  //insert to function
1371
1372    if (trueBlk) {
1373      trueBlk->addSuccessor(landBlk);
1374    } else {
1375      headBlk->addSuccessor(landBlk);
1376    }
1377
1378    if (falseBlk) {
1379      falseBlk->addSuccessor(landBlk);
1380    } else {
1381      headBlk->addSuccessor(landBlk);
1382    }
1383
1384    numNewBlk ++;
1385  }
1386
1387  bool landBlkHasOtherPred = (landBlk->pred_size() > 2);
1388
1389  //insert AMDIL::ENDIF to avoid special case "input landBlk == NULL"
1390  typename BlockT::iterator insertPos =
1391    CFGTraits::getInstrPos
1392    (landBlk, CFGTraits::insertInstrBefore(landBlk, AMDIL::ENDIF, passRep));
1393
1394  if (landBlkHasOtherPred) {
1395    unsigned immReg =
1396      funcRep->getRegInfo().createVirtualRegister(&AMDIL::GPRI32RegClass);
1397    CFGTraits::insertAssignInstrBefore(insertPos, passRep, immReg, 2);
1398    unsigned cmpResReg =
1399      funcRep->getRegInfo().createVirtualRegister(&AMDIL::GPRI32RegClass);
1400
1401    CFGTraits::insertCompareInstrBefore(landBlk, insertPos, passRep, cmpResReg,
1402                                        initReg, immReg);
1403    CFGTraits::insertCondBranchBefore(landBlk, insertPos,
1404                                      AMDIL::IF_LOGICALZ_i32, passRep,
1405                                      cmpResReg, DebugLoc());
1406  }
1407
1408  CFGTraits::insertCondBranchBefore(landBlk, insertPos, AMDIL::IF_LOGICALNZ_i32,
1409                                    passRep, initReg, DebugLoc());
1410
1411  if (migrateTrue) {
1412    migrateInstruction(trueBlk, landBlk, insertPos);
1413    // need to uncondionally insert the assignment to ensure a path from its
1414    // predecessor rather than headBlk has valid value in initReg if
1415    // (initVal != 1).
1416    CFGTraits::insertAssignInstrBefore(trueBlk, passRep, initReg, 1);
1417  }
1418  CFGTraits::insertInstrBefore(insertPos, AMDIL::ELSE, passRep);
1419
1420  if (migrateFalse) {
1421    migrateInstruction(falseBlk, landBlk, insertPos);
1422    // need to uncondionally insert the assignment to ensure a path from its
1423    // predecessor rather than headBlk has valid value in initReg if
1424    // (initVal != 0)
1425    CFGTraits::insertAssignInstrBefore(falseBlk, passRep, initReg, 0);
1426  }
1427  //CFGTraits::insertInstrBefore(insertPos, AMDIL::ENDIF, passRep);
1428
1429  if (landBlkHasOtherPred) {
1430    // add endif
1431    CFGTraits::insertInstrBefore(insertPos, AMDIL::ENDIF, passRep);
1432
1433    // put initReg = 2 to other predecessors of landBlk
1434    for (typename BlockT::pred_iterator predIter = landBlk->pred_begin(),
1435         predIterEnd = landBlk->pred_end(); predIter != predIterEnd;
1436         ++predIter) {
1437      BlockT *curBlk = *predIter;
1438      if (curBlk != trueBlk && curBlk != falseBlk) {
1439        CFGTraits::insertAssignInstrBefore(curBlk, passRep, initReg, 2);
1440      }
1441    } //for
1442  }
1443  if (DEBUGME) {
1444    errs() << "result from improveSimpleJumpintoIf: ";
1445    showImproveSimpleJumpintoIf(headBlk, trueBlk, falseBlk, landBlk, 0);
1446    //showImproveSimpleJumpintoIf(headBlk, trueBlk, falseBlk, landBlk, 1);
1447  }
1448
1449  // update landBlk
1450  *plandBlk = landBlk;
1451
1452  return numNewBlk;
1453} //improveSimpleJumpintoIf
1454
1455template<class PassT>
1456void CFGStructurizer<PassT>::handleLoopbreak(BlockT *exitingBlk,
1457                                              LoopT *exitingLoop,
1458                                             BlockT *exitBlk,
1459                                              LoopT *exitLoop,
1460                                             BlockT *landBlk) {
1461  if (DEBUGME) {
1462    errs() << "Trying to break loop-depth = " << getLoopDepth(exitLoop)
1463           << " from loop-depth = " << getLoopDepth(exitingLoop) << "\n";
1464  }
1465
1466  RegiT initReg = INVALIDREGNUM;
1467  if (exitingLoop != exitLoop) {
1468    initReg = static_cast<int>
1469      (funcRep->getRegInfo().createVirtualRegister(&AMDIL::GPRI32RegClass));
1470    assert(initReg != INVALIDREGNUM);
1471    addLoopBreakInitReg(exitLoop, initReg);
1472    while (exitingLoop != exitLoop && exitingLoop) {
1473      addLoopBreakOnReg(exitingLoop, initReg);
1474      exitingLoop = exitingLoop->getParentLoop();
1475    }
1476    assert(exitingLoop == exitLoop);
1477  }
1478
1479  mergeLoopbreakBlock(exitingBlk, exitBlk, landBlk, initReg);
1480
1481} //handleLoopbreak
1482
1483template<class PassT>
1484void CFGStructurizer<PassT>::handleLoopcontBlock(BlockT *contingBlk,
1485                                                  LoopT *contingLoop,
1486                                                 BlockT *contBlk,
1487                                                  LoopT *contLoop) {
1488  if (DEBUGME) {
1489    errs() << "loopcontPattern cont = BB" << contingBlk->getNumber()
1490           << " header = BB" << contBlk->getNumber() << "\n";
1491
1492    errs() << "Trying to continue loop-depth = "
1493           << getLoopDepth(contLoop)
1494           << " from loop-depth = " << getLoopDepth(contingLoop) << "\n";
1495  }
1496
1497  RegiT initReg = INVALIDREGNUM;
1498  if (contingLoop != contLoop) {
1499    initReg = static_cast<int>
1500      (funcRep->getRegInfo().createVirtualRegister(&AMDIL::GPRI32RegClass));
1501    assert(initReg != INVALIDREGNUM);
1502    addLoopContInitReg(contLoop, initReg);
1503    while (contingLoop && contingLoop->getParentLoop() != contLoop) {
1504      addLoopBreakOnReg(contingLoop, initReg);  //not addLoopContOnReg
1505      contingLoop = contingLoop->getParentLoop();
1506    }
1507    assert(contingLoop && contingLoop->getParentLoop() == contLoop);
1508    addLoopContOnReg(contingLoop, initReg);
1509  }
1510
1511  settleLoopcontBlock(contingBlk, contBlk, initReg);
1512  //contingBlk->removeSuccessor(loopHeader);
1513} //handleLoopcontBlock
1514
1515template<class PassT>
1516void CFGStructurizer<PassT>::mergeSerialBlock(BlockT *dstBlk, BlockT *srcBlk) {
1517  if (DEBUGME) {
1518    errs() << "serialPattern BB" << dstBlk->getNumber()
1519           << " <= BB" << srcBlk->getNumber() << "\n";
1520  }
1521  //removeUnconditionalBranch(dstBlk);
1522  dstBlk->splice(dstBlk->end(), srcBlk, FirstNonDebugInstr(srcBlk), srcBlk->end());
1523
1524  dstBlk->removeSuccessor(srcBlk);
1525  CFGTraits::cloneSuccessorList(dstBlk, srcBlk);
1526
1527  removeSuccessor(srcBlk);
1528  retireBlock(dstBlk, srcBlk);
1529} //mergeSerialBlock
1530
1531template<class PassT>
1532void CFGStructurizer<PassT>::mergeIfthenelseBlock(InstrT *branchInstr,
1533                                                  BlockT *curBlk,
1534                                                  BlockT *trueBlk,
1535                                                  BlockT *falseBlk,
1536                                                  BlockT *landBlk) {
1537  if (DEBUGME) {
1538    errs() << "ifPattern BB" << curBlk->getNumber();
1539    errs() << "{  ";
1540    if (trueBlk) {
1541      errs() << "BB" << trueBlk->getNumber();
1542    }
1543    errs() << "  } else ";
1544    errs() << "{  ";
1545    if (falseBlk) {
1546      errs() << "BB" << falseBlk->getNumber();
1547    }
1548    errs() << "  }\n ";
1549    errs() << "landBlock: ";
1550    if (landBlk == NULL) {
1551      errs() << "NULL";
1552    } else {
1553      errs() << "BB" << landBlk->getNumber();
1554    }
1555    errs() << "\n";
1556  }
1557
1558  int oldOpcode = branchInstr->getOpcode();
1559  DebugLoc branchDL = branchInstr->getDebugLoc();
1560
1561//    transform to
1562//    if cond
1563//       trueBlk
1564//    else
1565//       falseBlk
1566//    endif
1567//    landBlk
1568
1569  typename BlockT::iterator branchInstrPos =
1570    CFGTraits::getInstrPos(curBlk, branchInstr);
1571  CFGTraits::insertCondBranchBefore(branchInstrPos,
1572                                    CFGTraits::getBranchNzeroOpcode(oldOpcode),
1573                                    passRep,
1574									branchDL);
1575
1576  if (trueBlk) {
1577    curBlk->splice(branchInstrPos, trueBlk, FirstNonDebugInstr(trueBlk), trueBlk->end());
1578    curBlk->removeSuccessor(trueBlk);
1579    if (landBlk && trueBlk->succ_size()!=0) {
1580      trueBlk->removeSuccessor(landBlk);
1581    }
1582    retireBlock(curBlk, trueBlk);
1583  }
1584  CFGTraits::insertInstrBefore(branchInstrPos, AMDIL::ELSE, passRep);
1585
1586  if (falseBlk) {
1587    curBlk->splice(branchInstrPos, falseBlk, FirstNonDebugInstr(falseBlk),
1588                   falseBlk->end());
1589    curBlk->removeSuccessor(falseBlk);
1590    if (landBlk && falseBlk->succ_size() != 0) {
1591      falseBlk->removeSuccessor(landBlk);
1592    }
1593    retireBlock(curBlk, falseBlk);
1594  }
1595  CFGTraits::insertInstrBefore(branchInstrPos, AMDIL::ENDIF, passRep);
1596
1597  //curBlk->remove(branchInstrPos);
1598  branchInstr->eraseFromParent();
1599
1600  if (landBlk && trueBlk && falseBlk) {
1601    curBlk->addSuccessor(landBlk);
1602  }
1603
1604} //mergeIfthenelseBlock
1605
1606template<class PassT>
1607void CFGStructurizer<PassT>::mergeLooplandBlock(BlockT *dstBlk,
1608                                                LoopLandInfo *loopLand) {
1609  BlockT *landBlk = loopLand->landBlk;
1610
1611  if (DEBUGME) {
1612    errs() << "loopPattern header = BB" << dstBlk->getNumber()
1613           << " land = BB" << landBlk->getNumber() << "\n";
1614  }
1615
1616  // Loop contInitRegs are init at the beginning of the loop.
1617  for (typename std::set<RegiT>::const_iterator iter =
1618         loopLand->contInitRegs.begin(),
1619       iterEnd = loopLand->contInitRegs.end(); iter != iterEnd; ++iter) {
1620    CFGTraits::insertAssignInstrBefore(dstBlk, passRep, *iter, 0);
1621  }
1622
1623  /* we last inserterd the DebugLoc in the
1624   * BREAK_LOGICALZ_i32 or AMDIL::BREAK_LOGICALNZ statement in the current dstBlk.
1625   * search for the DebugLoc in the that statement.
1626   * if not found, we have to insert the empty/default DebugLoc */
1627  InstrT *loopBreakInstr = CFGTraits::getLoopBreakInstr(dstBlk);
1628  DebugLoc DLBreak = (loopBreakInstr) ? loopBreakInstr->getDebugLoc() : DebugLoc();
1629
1630  CFGTraits::insertInstrBefore(dstBlk, AMDIL::WHILELOOP, passRep, DLBreak);
1631  // Loop breakInitRegs are init before entering the loop.
1632  for (typename std::set<RegiT>::const_iterator iter =
1633         loopLand->breakInitRegs.begin(),
1634       iterEnd = loopLand->breakInitRegs.end(); iter != iterEnd; ++iter)
1635  {
1636    CFGTraits::insertAssignInstrBefore(dstBlk, passRep, *iter, 0);
1637  }
1638  // Loop endbranchInitRegs are init before entering the loop.
1639  for (typename std::set<RegiT>::const_iterator iter =
1640         loopLand->endbranchInitRegs.begin(),
1641       iterEnd = loopLand->endbranchInitRegs.end(); iter != iterEnd; ++iter) {
1642    CFGTraits::insertAssignInstrBefore(dstBlk, passRep, *iter, 0);
1643  }
1644
1645  /* we last inserterd the DebugLoc in the continue statement in the current dstBlk
1646   * search for the DebugLoc in the continue statement.
1647   * if not found, we have to insert the empty/default DebugLoc */
1648  InstrT *continueInstr = CFGTraits::getContinueInstr(dstBlk);
1649  DebugLoc DLContinue = (continueInstr) ? continueInstr->getDebugLoc() : DebugLoc();
1650
1651  CFGTraits::insertInstrEnd(dstBlk, AMDIL::ENDLOOP, passRep, DLContinue);
1652  // Loop breakOnRegs are check after the ENDLOOP: break the loop outside this
1653  // loop.
1654  for (typename std::set<RegiT>::const_iterator iter =
1655         loopLand->breakOnRegs.begin(),
1656       iterEnd = loopLand->breakOnRegs.end(); iter != iterEnd; ++iter) {
1657    CFGTraits::insertCondBranchEnd(dstBlk, AMDIL::BREAK_LOGICALNZ_i32, passRep,
1658                                   *iter);
1659  }
1660
1661  // Loop contOnRegs are check after the ENDLOOP: cont the loop outside this
1662  // loop.
1663  for (std::set<RegiT>::const_iterator iter = loopLand->contOnRegs.begin(),
1664       iterEnd = loopLand->contOnRegs.end(); iter != iterEnd; ++iter) {
1665    CFGTraits::insertCondBranchEnd(dstBlk, AMDIL::CONTINUE_LOGICALNZ_i32,
1666                                   passRep, *iter);
1667  }
1668
1669  dstBlk->splice(dstBlk->end(), landBlk, landBlk->begin(), landBlk->end());
1670
1671  for (typename BlockT::succ_iterator iter = landBlk->succ_begin(),
1672       iterEnd = landBlk->succ_end(); iter != iterEnd; ++iter) {
1673    dstBlk->addSuccessor(*iter);  // *iter's predecessor is also taken care of.
1674  }
1675
1676  removeSuccessor(landBlk);
1677  retireBlock(dstBlk, landBlk);
1678} //mergeLooplandBlock
1679
1680template<class PassT>
1681void CFGStructurizer<PassT>::mergeLoopbreakBlock(BlockT *exitingBlk,
1682                                                 BlockT *exitBlk,
1683                                                 BlockT *exitLandBlk,
1684                                                 RegiT  setReg) {
1685  if (DEBUGME) {
1686    errs() << "loopbreakPattern exiting = BB" << exitingBlk->getNumber()
1687           << " exit = BB" << exitBlk->getNumber()
1688           << " land = BB" << exitLandBlk->getNumber() << "\n";
1689  }
1690
1691  InstrT *branchInstr = CFGTraits::getLoopendBlockBranchInstr(exitingBlk);
1692  assert(branchInstr && CFGTraits::isCondBranch(branchInstr));
1693
1694  DebugLoc DL = branchInstr->getDebugLoc();
1695
1696  BlockT *trueBranch = CFGTraits::getTrueBranch(branchInstr);
1697  int oldOpcode = branchInstr->getOpcode();
1698
1699  //    transform exitingBlk to
1700  //    if ( ) {
1701  //       exitBlk (if exitBlk != exitLandBlk)
1702  //       setReg = 1
1703  //       break
1704  //    }endif
1705  //    successor = {orgSuccessor(exitingBlk) - exitBlk}
1706
1707  typename BlockT::iterator branchInstrPos =
1708    CFGTraits::getInstrPos(exitingBlk, branchInstr);
1709
1710  if (exitBlk == exitLandBlk && setReg == INVALIDREGNUM) {
1711    //break_logical
1712    int newOpcode =
1713    (trueBranch == exitBlk) ? CFGTraits::getBreakNzeroOpcode(oldOpcode)
1714                            : CFGTraits::getBreakZeroOpcode(oldOpcode);
1715    CFGTraits::insertCondBranchBefore(branchInstrPos, newOpcode, passRep, DL);
1716  } else {
1717    int newOpcode =
1718    (trueBranch == exitBlk) ? CFGTraits::getBranchNzeroOpcode(oldOpcode)
1719                            : CFGTraits::getBranchZeroOpcode(oldOpcode);
1720    CFGTraits::insertCondBranchBefore(branchInstrPos, newOpcode, passRep, DL);
1721    if (exitBlk != exitLandBlk) {
1722      //splice is insert-before ...
1723      exitingBlk->splice(branchInstrPos, exitBlk, exitBlk->begin(),
1724                         exitBlk->end());
1725    }
1726    if (setReg != INVALIDREGNUM) {
1727      CFGTraits::insertAssignInstrBefore(branchInstrPos, passRep, setReg, 1);
1728    }
1729    CFGTraits::insertInstrBefore(branchInstrPos, AMDIL::BREAK, passRep);
1730    CFGTraits::insertInstrBefore(branchInstrPos, AMDIL::ENDIF, passRep);
1731  } //if_logical
1732
1733  //now branchInst can be erase safely
1734  //exitingBlk->eraseFromParent(branchInstr);
1735  branchInstr->eraseFromParent();
1736
1737  //now take care of successors, retire blocks
1738  exitingBlk->removeSuccessor(exitBlk);
1739  if (exitBlk != exitLandBlk) {
1740    //splice is insert-before ...
1741    exitBlk->removeSuccessor(exitLandBlk);
1742    retireBlock(exitingBlk, exitBlk);
1743  }
1744
1745} //mergeLoopbreakBlock
1746
1747template<class PassT>
1748void CFGStructurizer<PassT>::settleLoopcontBlock(BlockT *contingBlk,
1749                                                 BlockT *contBlk,
1750                                                 RegiT   setReg) {
1751  if (DEBUGME) {
1752    errs() << "settleLoopcontBlock conting = BB"
1753           << contingBlk->getNumber()
1754           << ", cont = BB" << contBlk->getNumber() << "\n";
1755  }
1756
1757  InstrT *branchInstr = CFGTraits::getLoopendBlockBranchInstr(contingBlk);
1758  if (branchInstr) {
1759    assert(CFGTraits::isCondBranch(branchInstr));
1760    typename BlockT::iterator branchInstrPos =
1761      CFGTraits::getInstrPos(contingBlk, branchInstr);
1762    BlockT *trueBranch = CFGTraits::getTrueBranch(branchInstr);
1763    int oldOpcode = branchInstr->getOpcode();
1764	DebugLoc DL = branchInstr->getDebugLoc();
1765
1766    //    transform contingBlk to
1767    //     if () {
1768    //          move instr after branchInstr
1769    //          continue
1770    //        or
1771    //          setReg = 1
1772    //          break
1773    //     }endif
1774    //     successor = {orgSuccessor(contingBlk) - loopHeader}
1775
1776    bool useContinueLogical =
1777      (setReg == INVALIDREGNUM && (&*contingBlk->rbegin()) == branchInstr);
1778
1779    if (useContinueLogical == false)
1780    {
1781      int branchOpcode =
1782        trueBranch == contBlk ? CFGTraits::getBranchNzeroOpcode(oldOpcode)
1783                              : CFGTraits::getBranchZeroOpcode(oldOpcode);
1784
1785      CFGTraits::insertCondBranchBefore(branchInstrPos, branchOpcode, passRep, DL);
1786
1787      if (setReg != INVALIDREGNUM) {
1788        CFGTraits::insertAssignInstrBefore(branchInstrPos, passRep, setReg, 1);
1789        // insertEnd to ensure phi-moves, if exist, go before the continue-instr.
1790        CFGTraits::insertInstrEnd(contingBlk, AMDIL::BREAK, passRep, DL);
1791      } else {
1792        // insertEnd to ensure phi-moves, if exist, go before the continue-instr.
1793        CFGTraits::insertInstrEnd(contingBlk, AMDIL::CONTINUE, passRep, DL);
1794      }
1795
1796      CFGTraits::insertInstrEnd(contingBlk, AMDIL::ENDIF, passRep, DL);
1797    } else {
1798      int branchOpcode =
1799        trueBranch == contBlk ? CFGTraits::getContinueNzeroOpcode(oldOpcode)
1800                              : CFGTraits::getContinueZeroOpcode(oldOpcode);
1801
1802      CFGTraits::insertCondBranchBefore(branchInstrPos, branchOpcode, passRep, DL);
1803    }
1804
1805    //contingBlk->eraseFromParent(branchInstr);
1806    branchInstr->eraseFromParent();
1807  } else {
1808    /* if we've arrived here then we've already erased the branch instruction
1809	 * travel back up the basic block to see the last reference of our debug location
1810	 * we've just inserted that reference here so it should be representative */
1811    if (setReg != INVALIDREGNUM) {
1812      CFGTraits::insertAssignInstrBefore(contingBlk, passRep, setReg, 1);
1813      // insertEnd to ensure phi-moves, if exist, go before the continue-instr.
1814      CFGTraits::insertInstrEnd(contingBlk, AMDIL::BREAK, passRep, CFGTraits::getLastDebugLocInBB(contingBlk));
1815    } else {
1816      // insertEnd to ensure phi-moves, if exist, go before the continue-instr.
1817      CFGTraits::insertInstrEnd(contingBlk, AMDIL::CONTINUE, passRep, CFGTraits::getLastDebugLocInBB(contingBlk));
1818    }
1819  } //else
1820
1821} //settleLoopcontBlock
1822
1823// BBs in exitBlkSet are determined as in break-path for loopRep,
1824// before we can put code for BBs as inside loop-body for loopRep
1825// check whether those BBs are determined as cont-BB for parentLoopRep
1826// earlier.
1827// If so, generate a new BB newBlk
1828//    (1) set newBlk common successor of BBs in exitBlkSet
1829//    (2) change the continue-instr in BBs in exitBlkSet to break-instr
1830//    (3) generate continue-instr in newBlk
1831//
1832template<class PassT>
1833typename CFGStructurizer<PassT>::BlockT *
1834CFGStructurizer<PassT>::relocateLoopcontBlock(LoopT *parentLoopRep,
1835                                              LoopT *loopRep,
1836                                              std::set<BlockT *> &exitBlkSet,
1837                                              BlockT *exitLandBlk) {
1838  std::set<BlockT *> endBlkSet;
1839
1840//  BlockT *parentLoopHead = parentLoopRep->getHeader();
1841
1842
1843  for (typename std::set<BlockT *>::const_iterator iter = exitBlkSet.begin(),
1844       iterEnd = exitBlkSet.end();
1845       iter != iterEnd; ++iter) {
1846    BlockT *exitBlk = *iter;
1847    BlockT *endBlk = singlePathEnd(exitBlk, exitLandBlk);
1848
1849    if (endBlk == NULL || CFGTraits::getContinueInstr(endBlk) == NULL)
1850      return NULL;
1851
1852    endBlkSet.insert(endBlk);
1853  }
1854
1855  BlockT *newBlk = funcRep->CreateMachineBasicBlock();
1856  funcRep->push_back(newBlk);  //insert to function
1857  CFGTraits::insertInstrEnd(newBlk, AMDIL::CONTINUE, passRep);
1858  SHOWNEWBLK(newBlk, "New continue block: ");
1859
1860  for (typename std::set<BlockT*>::const_iterator iter = endBlkSet.begin(),
1861       iterEnd = endBlkSet.end();
1862       iter != iterEnd; ++iter) {
1863      BlockT *endBlk = *iter;
1864      InstrT *contInstr = CFGTraits::getContinueInstr(endBlk);
1865      if (contInstr) {
1866        contInstr->eraseFromParent();
1867      }
1868      endBlk->addSuccessor(newBlk);
1869      if (DEBUGME) {
1870        errs() << "Add new continue Block to BB"
1871               << endBlk->getNumber() << " successors\n";
1872      }
1873  }
1874
1875  return newBlk;
1876} //relocateLoopcontBlock
1877
1878
1879// LoopEndbranchBlock is a BB created by the CFGStructurizer to use as
1880// LoopLandBlock. This BB branch on the loop endBranchInit register to the
1881// pathes corresponding to the loop exiting branches.
1882
1883template<class PassT>
1884typename CFGStructurizer<PassT>::BlockT *
1885CFGStructurizer<PassT>::addLoopEndbranchBlock(LoopT *loopRep,
1886                                              BlockTSmallerVector &exitingBlks,
1887                                              BlockTSmallerVector &exitBlks) {
1888  const TargetInstrInfo *tii = passRep->getTargetInstrInfo();
1889
1890  RegiT endBranchReg = static_cast<int>
1891    (funcRep->getRegInfo().createVirtualRegister(&AMDIL::GPRI32RegClass));
1892  assert(endBranchReg >= 0);
1893
1894  // reg = 0 before entering the loop
1895  addLoopEndbranchInitReg(loopRep, endBranchReg);
1896
1897  uint32_t numBlks = static_cast<uint32_t>(exitingBlks.size());
1898  assert(numBlks >=2 && numBlks == exitBlks.size());
1899
1900  BlockT *preExitingBlk = exitingBlks[0];
1901  BlockT *preExitBlk = exitBlks[0];
1902  BlockT *preBranchBlk = funcRep->CreateMachineBasicBlock();
1903  funcRep->push_back(preBranchBlk);  //insert to function
1904  SHOWNEWBLK(preBranchBlk, "New loopEndbranch block: ");
1905
1906  BlockT *newLandBlk = preBranchBlk;
1907
1908      CFGTraits::replaceInstrUseOfBlockWith(preExitingBlk, preExitBlk,
1909        newLandBlk);
1910  preExitingBlk->removeSuccessor(preExitBlk);
1911  preExitingBlk->addSuccessor(newLandBlk);
1912
1913  //it is redundant to add reg = 0 to exitingBlks[0]
1914
1915  // For 1..n th exiting path (the last iteration handles two pathes) create the
1916  // branch to the previous path and the current path.
1917  for (uint32_t i = 1; i < numBlks; ++i) {
1918    BlockT *curExitingBlk = exitingBlks[i];
1919    BlockT *curExitBlk = exitBlks[i];
1920    BlockT *curBranchBlk;
1921
1922    if (i == numBlks - 1) {
1923      curBranchBlk = curExitBlk;
1924    } else {
1925      curBranchBlk = funcRep->CreateMachineBasicBlock();
1926      funcRep->push_back(curBranchBlk);  //insert to function
1927      SHOWNEWBLK(curBranchBlk, "New loopEndbranch block: ");
1928    }
1929
1930    // Add reg = i to exitingBlks[i].
1931    CFGTraits::insertAssignInstrBefore(curExitingBlk, passRep,
1932                                       endBranchReg, i);
1933
1934    // Remove the edge (exitingBlks[i] exitBlks[i]) add new edge
1935    // (exitingBlks[i], newLandBlk).
1936    CFGTraits::replaceInstrUseOfBlockWith(curExitingBlk, curExitBlk,
1937                                          newLandBlk);
1938    curExitingBlk->removeSuccessor(curExitBlk);
1939    curExitingBlk->addSuccessor(newLandBlk);
1940
1941    // add to preBranchBlk the branch instruction:
1942    // if (endBranchReg == preVal)
1943    //    preExitBlk
1944    // else
1945    //    curBranchBlk
1946    //
1947    // preValReg = i - 1
1948
1949  DebugLoc DL;
1950  RegiT preValReg = static_cast<int>
1951    (funcRep->getRegInfo().createVirtualRegister(&AMDIL::GPRI32RegClass));
1952  BuildMI(preBranchBlk, DL, tii->get(AMDIL::LOADCONST_i32), preValReg)
1953    .addImm(i - 1); //preVal
1954
1955  // condResReg = (endBranchReg == preValReg)
1956    RegiT condResReg = static_cast<int>
1957      (funcRep->getRegInfo().createVirtualRegister(&AMDIL::GPRI32RegClass));
1958    BuildMI(preBranchBlk, DL, tii->get(AMDIL::IEQ), condResReg)
1959      .addReg(endBranchReg).addReg(preValReg);
1960
1961    BuildMI(preBranchBlk, DL, tii->get(AMDIL::BRANCH_COND_i32))
1962      .addMBB(preExitBlk).addReg(condResReg);
1963
1964    preBranchBlk->addSuccessor(preExitBlk);
1965    preBranchBlk->addSuccessor(curBranchBlk);
1966
1967    // Update preExitingBlk, preExitBlk, preBranchBlk.
1968    preExitingBlk = curExitingBlk;
1969    preExitBlk = curExitBlk;
1970    preBranchBlk = curBranchBlk;
1971
1972  }  //end for 1 .. n blocks
1973
1974  return newLandBlk;
1975} //addLoopEndbranchBlock
1976
1977template<class PassT>
1978typename CFGStructurizer<PassT>::PathToKind
1979CFGStructurizer<PassT>::singlePathTo(BlockT *srcBlk, BlockT *dstBlk,
1980                                     bool allowSideEntry) {
1981  assert(dstBlk);
1982
1983  if (srcBlk == dstBlk) {
1984    return SinglePath_InPath;
1985  }
1986
1987  while (srcBlk && srcBlk->succ_size() == 1) {
1988    srcBlk = *srcBlk->succ_begin();
1989    if (srcBlk == dstBlk) {
1990      return SinglePath_InPath;
1991    }
1992
1993    if (!allowSideEntry && srcBlk->pred_size() > 1) {
1994      return Not_SinglePath;
1995    }
1996  }
1997
1998  if (srcBlk && srcBlk->succ_size()==0) {
1999    return SinglePath_NotInPath;
2000  }
2001
2002  return Not_SinglePath;
2003} //singlePathTo
2004
2005// If there is a single path from srcBlk to dstBlk, return the last block before
2006// dstBlk If there is a single path from srcBlk->end without dstBlk, return the
2007// last block in the path Otherwise, return NULL
2008template<class PassT>
2009typename CFGStructurizer<PassT>::BlockT *
2010CFGStructurizer<PassT>::singlePathEnd(BlockT *srcBlk, BlockT *dstBlk,
2011                                      bool allowSideEntry) {
2012  assert(dstBlk);
2013
2014  if (srcBlk == dstBlk) {
2015    return srcBlk;
2016  }
2017
2018  if (srcBlk->succ_size() == 0) {
2019    return srcBlk;
2020  }
2021
2022  while (srcBlk && srcBlk->succ_size() == 1) {
2023    BlockT *preBlk = srcBlk;
2024
2025    srcBlk = *srcBlk->succ_begin();
2026    if (srcBlk == NULL) {
2027      return preBlk;
2028    }
2029
2030    if (!allowSideEntry && srcBlk->pred_size() > 1) {
2031      return NULL;
2032    }
2033  }
2034
2035  if (srcBlk && srcBlk->succ_size()==0) {
2036    return srcBlk;
2037  }
2038
2039  return NULL;
2040
2041} //singlePathEnd
2042
2043template<class PassT>
2044int CFGStructurizer<PassT>::cloneOnSideEntryTo(BlockT *preBlk, BlockT *srcBlk,
2045                                               BlockT *dstBlk) {
2046  int cloned = 0;
2047  assert(preBlk->isSuccessor(srcBlk));
2048  while (srcBlk && srcBlk != dstBlk) {
2049    assert(srcBlk->succ_size() == 1);
2050    if (srcBlk->pred_size() > 1) {
2051      srcBlk = cloneBlockForPredecessor(srcBlk, preBlk);
2052      ++cloned;
2053    }
2054
2055    preBlk = srcBlk;
2056    srcBlk = *srcBlk->succ_begin();
2057  }
2058
2059  return cloned;
2060} //cloneOnSideEntryTo
2061
2062template<class PassT>
2063typename CFGStructurizer<PassT>::BlockT *
2064CFGStructurizer<PassT>::cloneBlockForPredecessor(BlockT *curBlk,
2065                                                 BlockT *predBlk) {
2066  assert(predBlk->isSuccessor(curBlk) &&
2067         "succBlk is not a prececessor of curBlk");
2068
2069  BlockT *cloneBlk = CFGTraits::clone(curBlk);  //clone instructions
2070  CFGTraits::replaceInstrUseOfBlockWith(predBlk, curBlk, cloneBlk);
2071  //srcBlk, oldBlk, newBlk
2072
2073  predBlk->removeSuccessor(curBlk);
2074  predBlk->addSuccessor(cloneBlk);
2075
2076  // add all successor to cloneBlk
2077  CFGTraits::cloneSuccessorList(cloneBlk, curBlk);
2078
2079  numClonedInstr += curBlk->size();
2080
2081  if (DEBUGME) {
2082    errs() << "Cloned block: " << "BB"
2083           << curBlk->getNumber() << "size " << curBlk->size() << "\n";
2084  }
2085
2086  SHOWNEWBLK(cloneBlk, "result of Cloned block: ");
2087
2088  return cloneBlk;
2089} //cloneBlockForPredecessor
2090
2091template<class PassT>
2092typename CFGStructurizer<PassT>::BlockT *
2093CFGStructurizer<PassT>::exitingBlock2ExitBlock(LoopT *loopRep,
2094                                               BlockT *exitingBlk) {
2095  BlockT *exitBlk = NULL;
2096
2097  for (typename BlockT::succ_iterator iterSucc = exitingBlk->succ_begin(),
2098       iterSuccEnd = exitingBlk->succ_end();
2099       iterSucc != iterSuccEnd; ++iterSucc) {
2100    BlockT *curBlk = *iterSucc;
2101    if (!loopRep->contains(curBlk)) {
2102      assert(exitBlk == NULL);
2103      exitBlk = curBlk;
2104    }
2105  }
2106
2107  assert(exitBlk != NULL);
2108
2109  return exitBlk;
2110} //exitingBlock2ExitBlock
2111
2112template<class PassT>
2113void CFGStructurizer<PassT>::migrateInstruction(BlockT *srcBlk,
2114                                                BlockT *dstBlk,
2115                                                InstrIterator insertPos) {
2116  InstrIterator spliceEnd;
2117  //look for the input branchinstr, not the AMDIL branchinstr
2118  InstrT *branchInstr = CFGTraits::getNormalBlockBranchInstr(srcBlk);
2119  if (branchInstr == NULL) {
2120    if (DEBUGME) {
2121      errs() << "migrateInstruction don't see branch instr\n" ;
2122    }
2123    spliceEnd = srcBlk->end();
2124  } else {
2125    if (DEBUGME) {
2126      errs() << "migrateInstruction see branch instr\n" ;
2127      branchInstr->dump();
2128    }
2129    spliceEnd = CFGTraits::getInstrPos(srcBlk, branchInstr);
2130  }
2131  if (DEBUGME) {
2132    errs() << "migrateInstruction before splice dstSize = " << dstBlk->size()
2133      << "srcSize = " << srcBlk->size() << "\n";
2134  }
2135
2136  //splice insert before insertPos
2137  dstBlk->splice(insertPos, srcBlk, srcBlk->begin(), spliceEnd);
2138
2139  if (DEBUGME) {
2140    errs() << "migrateInstruction after splice dstSize = " << dstBlk->size()
2141      << "srcSize = " << srcBlk->size() << "\n";
2142  }
2143} //migrateInstruction
2144
2145// normalizeInfiniteLoopExit change
2146//   B1:
2147//        uncond_br LoopHeader
2148//
2149// to
2150//   B1:
2151//        cond_br 1 LoopHeader dummyExit
2152// and return the newly added dummy exit block
2153//
2154template<class PassT>
2155typename CFGStructurizer<PassT>::BlockT *
2156CFGStructurizer<PassT>::normalizeInfiniteLoopExit(LoopT* LoopRep) {
2157  BlockT *loopHeader;
2158  BlockT *loopLatch;
2159  loopHeader = LoopRep->getHeader();
2160  loopLatch = LoopRep->getLoopLatch();
2161  BlockT *dummyExitBlk = NULL;
2162  if (loopHeader!=NULL && loopLatch!=NULL) {
2163    InstrT *branchInstr = CFGTraits::getLoopendBlockBranchInstr(loopLatch);
2164    if (branchInstr!=NULL && CFGTraits::isUncondBranch(branchInstr)) {
2165      dummyExitBlk = funcRep->CreateMachineBasicBlock();
2166      funcRep->push_back(dummyExitBlk);  //insert to function
2167      SHOWNEWBLK(dummyExitBlk, "DummyExitBlock to normalize infiniteLoop: ");
2168
2169      if (DEBUGME) errs() << "Old branch instr: " << *branchInstr << "\n";
2170
2171      typename BlockT::iterator insertPos =
2172        CFGTraits::getInstrPos(loopLatch, branchInstr);
2173      unsigned immReg =
2174        funcRep->getRegInfo().createVirtualRegister(&AMDIL::GPRI32RegClass);
2175      CFGTraits::insertAssignInstrBefore(insertPos, passRep, immReg, 1);
2176      InstrT *newInstr =
2177        CFGTraits::insertInstrBefore(insertPos, AMDIL::BRANCH_COND_i32, passRep);
2178      MachineInstrBuilder(newInstr).addMBB(loopHeader).addReg(immReg, false);
2179
2180      SHOWNEWINSTR(newInstr);
2181
2182      branchInstr->eraseFromParent();
2183      loopLatch->addSuccessor(dummyExitBlk);
2184    }
2185  }
2186
2187  return dummyExitBlk;
2188} //normalizeInfiniteLoopExit
2189
2190template<class PassT>
2191void CFGStructurizer<PassT>::removeUnconditionalBranch(BlockT *srcBlk) {
2192  InstrT *branchInstr;
2193
2194  // I saw two unconditional branch in one basic block in example
2195  // test_fc_do_while_or.c need to fix the upstream on this to remove the loop.
2196  while ((branchInstr = CFGTraits::getLoopendBlockBranchInstr(srcBlk))
2197          && CFGTraits::isUncondBranch(branchInstr)) {
2198    if (DEBUGME) {
2199          errs() << "Removing unconditional branch instruction" ;
2200      branchInstr->dump();
2201    }
2202    branchInstr->eraseFromParent();
2203  }
2204} //removeUnconditionalBranch
2205
2206template<class PassT>
2207void CFGStructurizer<PassT>::removeRedundantConditionalBranch(BlockT *srcBlk) {
2208  if (srcBlk->succ_size() == 2) {
2209    BlockT *blk1 = *srcBlk->succ_begin();
2210    BlockT *blk2 = *(++srcBlk->succ_begin());
2211
2212    if (blk1 == blk2) {
2213      InstrT *branchInstr = CFGTraits::getNormalBlockBranchInstr(srcBlk);
2214      assert(branchInstr && CFGTraits::isCondBranch(branchInstr));
2215      if (DEBUGME) {
2216        errs() << "Removing unneeded conditional branch instruction" ;
2217        branchInstr->dump();
2218      }
2219      branchInstr->eraseFromParent();
2220      SHOWNEWBLK(blk1, "Removing redundant successor");
2221      srcBlk->removeSuccessor(blk1);
2222    }
2223  }
2224} //removeRedundantConditionalBranch
2225
2226template<class PassT>
2227void CFGStructurizer<PassT>::addDummyExitBlock(SmallVector<BlockT*,
2228                                               DEFAULT_VEC_SLOTS> &retBlks) {
2229  BlockT *dummyExitBlk = funcRep->CreateMachineBasicBlock();
2230  funcRep->push_back(dummyExitBlk);  //insert to function
2231  CFGTraits::insertInstrEnd(dummyExitBlk, AMDIL::RETURN, passRep);
2232
2233  for (typename SmallVector<BlockT *, DEFAULT_VEC_SLOTS>::iterator iter =
2234         retBlks.begin(),
2235       iterEnd = retBlks.end(); iter != iterEnd; ++iter) {
2236    BlockT *curBlk = *iter;
2237    InstrT *curInstr = CFGTraits::getReturnInstr(curBlk);
2238    if (curInstr) {
2239      curInstr->eraseFromParent();
2240    }
2241#if 0
2242    if (curBlk->size()==0 && curBlk->pred_size() == 1) {
2243      if (DEBUGME) {
2244        errs() << "Replace empty block BB" <<  curBlk->getNumber()
2245          << " with dummyExitBlock\n";
2246      }
2247      BlockT *predb = *curBlk->pred_begin();
2248      predb->removeSuccessor(curBlk);
2249      curBlk = predb;
2250    } //handle empty curBlk
2251#endif
2252    curBlk->addSuccessor(dummyExitBlk);
2253    if (DEBUGME) {
2254      errs() << "Add dummyExitBlock to BB" << curBlk->getNumber()
2255             << " successors\n";
2256    }
2257  } //for
2258
2259  SHOWNEWBLK(dummyExitBlk, "DummyExitBlock: ");
2260} //addDummyExitBlock
2261
2262template<class PassT>
2263void CFGStructurizer<PassT>::removeSuccessor(BlockT *srcBlk) {
2264  while (srcBlk->succ_size()) {
2265    srcBlk->removeSuccessor(*srcBlk->succ_begin());
2266  }
2267}
2268
2269template<class PassT>
2270void CFGStructurizer<PassT>::recordSccnum(BlockT *srcBlk, int sccNum) {
2271  BlockInfo *&srcBlkInfo = blockInfoMap[srcBlk];
2272
2273  if (srcBlkInfo == NULL) {
2274    srcBlkInfo = new BlockInfo();
2275  }
2276
2277  srcBlkInfo->sccNum = sccNum;
2278}
2279
2280template<class PassT>
2281int CFGStructurizer<PassT>::getSCCNum(BlockT *srcBlk) {
2282  BlockInfo *srcBlkInfo = blockInfoMap[srcBlk];
2283  return srcBlkInfo ? srcBlkInfo->sccNum : INVALIDSCCNUM;
2284}
2285
2286template<class PassT>
2287void CFGStructurizer<PassT>::retireBlock(BlockT *dstBlk, BlockT *srcBlk) {
2288  if (DEBUGME) {
2289        errs() << "Retiring BB" << srcBlk->getNumber() << "\n";
2290  }
2291
2292  BlockInfo *&srcBlkInfo = blockInfoMap[srcBlk];
2293
2294  if (srcBlkInfo == NULL) {
2295    srcBlkInfo = new BlockInfo();
2296  }
2297
2298  srcBlkInfo->isRetired = true;
2299  //int i = srcBlk->succ_size();
2300  //int j = srcBlk->pred_size();
2301  assert(srcBlk->succ_size() == 0 && srcBlk->pred_size() == 0
2302         && "can't retire block yet");
2303}
2304
2305template<class PassT>
2306bool CFGStructurizer<PassT>::isRetiredBlock(BlockT *srcBlk) {
2307  BlockInfo *srcBlkInfo = blockInfoMap[srcBlk];
2308  return (srcBlkInfo && srcBlkInfo->isRetired);
2309}
2310
2311template<class PassT>
2312bool CFGStructurizer<PassT>::isActiveLoophead(BlockT *curBlk) {
2313  LoopT *loopRep = loopInfo->getLoopFor(curBlk);
2314  while (loopRep && loopRep->getHeader() == curBlk) {
2315    LoopLandInfo *loopLand = getLoopLandInfo(loopRep);
2316
2317    if(loopLand == NULL)
2318      return true;
2319
2320    BlockT *landBlk = loopLand->landBlk;
2321    assert(landBlk);
2322    if (!isRetiredBlock(landBlk)) {
2323      return true;
2324    }
2325
2326    loopRep = loopRep->getParentLoop();
2327  }
2328
2329  return false;
2330} //isActiveLoophead
2331
2332template<class PassT>
2333bool CFGStructurizer<PassT>::needMigrateBlock(BlockT *blk) {
2334  const unsigned blockSizeThreshold = 30;
2335  const unsigned cloneInstrThreshold = 100;
2336
2337  bool multiplePreds = blk && (blk->pred_size() > 1);
2338
2339  if(!multiplePreds)
2340    return false;
2341
2342  unsigned blkSize = blk->size();
2343  return ((blkSize > blockSizeThreshold)
2344          && (blkSize * (blk->pred_size() - 1) > cloneInstrThreshold));
2345} //needMigrateBlock
2346
2347template<class PassT>
2348typename CFGStructurizer<PassT>::BlockT *
2349CFGStructurizer<PassT>::recordLoopLandBlock(LoopT *loopRep, BlockT *landBlk,
2350                                            BlockTSmallerVector &exitBlks,
2351                                            std::set<BlockT *> &exitBlkSet) {
2352  SmallVector<BlockT *, DEFAULT_VEC_SLOTS> inpathBlks;  //in exit path blocks
2353
2354  for (typename BlockT::pred_iterator predIter = landBlk->pred_begin(),
2355       predIterEnd = landBlk->pred_end();
2356       predIter != predIterEnd; ++predIter) {
2357    BlockT *curBlk = *predIter;
2358    if (loopRep->contains(curBlk) || exitBlkSet.count(curBlk)) {
2359      inpathBlks.push_back(curBlk);
2360    }
2361  } //for
2362
2363  //if landBlk has predecessors that are not in the given loop,
2364  //create a new block
2365  BlockT *newLandBlk = landBlk;
2366  if (inpathBlks.size() != landBlk->pred_size()) {
2367    newLandBlk = funcRep->CreateMachineBasicBlock();
2368    funcRep->push_back(newLandBlk);  //insert to function
2369    newLandBlk->addSuccessor(landBlk);
2370    for (typename SmallVector<BlockT*, DEFAULT_VEC_SLOTS>::iterator iter =
2371         inpathBlks.begin(),
2372         iterEnd = inpathBlks.end(); iter != iterEnd; ++iter) {
2373      BlockT *curBlk = *iter;
2374      CFGTraits::replaceInstrUseOfBlockWith(curBlk, landBlk, newLandBlk);
2375      //srcBlk, oldBlk, newBlk
2376      curBlk->removeSuccessor(landBlk);
2377      curBlk->addSuccessor(newLandBlk);
2378    }
2379    for (size_t i = 0, tot = exitBlks.size(); i < tot; ++i) {
2380      if (exitBlks[i] == landBlk) {
2381        exitBlks[i] = newLandBlk;
2382      }
2383    }
2384    SHOWNEWBLK(newLandBlk, "NewLandingBlock: ");
2385  }
2386
2387  setLoopLandBlock(loopRep, newLandBlk);
2388
2389  return newLandBlk;
2390} // recordLoopbreakLand
2391
2392template<class PassT>
2393void CFGStructurizer<PassT>::setLoopLandBlock(LoopT *loopRep, BlockT *blk) {
2394  LoopLandInfo *&theEntry = loopLandInfoMap[loopRep];
2395
2396  if (theEntry == NULL) {
2397    theEntry = new LoopLandInfo();
2398  }
2399  assert(theEntry->landBlk == NULL);
2400
2401  if (blk == NULL) {
2402    blk = funcRep->CreateMachineBasicBlock();
2403    funcRep->push_back(blk);  //insert to function
2404    SHOWNEWBLK(blk, "DummyLandingBlock for loop without break: ");
2405  }
2406
2407  theEntry->landBlk = blk;
2408
2409  if (DEBUGME) {
2410    errs() << "setLoopLandBlock loop-header = BB"
2411           << loopRep->getHeader()->getNumber()
2412           << "  landing-block = BB" << blk->getNumber() << "\n";
2413  }
2414} // setLoopLandBlock
2415
2416template<class PassT>
2417void CFGStructurizer<PassT>::addLoopBreakOnReg(LoopT *loopRep, RegiT regNum) {
2418  LoopLandInfo *&theEntry = loopLandInfoMap[loopRep];
2419
2420  if (theEntry == NULL) {
2421    theEntry = new LoopLandInfo();
2422  }
2423
2424  theEntry->breakOnRegs.insert(regNum);
2425
2426  if (DEBUGME) {
2427    errs() << "addLoopBreakOnReg loop-header = BB"
2428           << loopRep->getHeader()->getNumber()
2429           << "  regNum = " << regNum << "\n";
2430  }
2431} // addLoopBreakOnReg
2432
2433template<class PassT>
2434void CFGStructurizer<PassT>::addLoopContOnReg(LoopT *loopRep, RegiT regNum) {
2435  LoopLandInfo *&theEntry = loopLandInfoMap[loopRep];
2436
2437  if (theEntry == NULL) {
2438    theEntry = new LoopLandInfo();
2439  }
2440  theEntry->contOnRegs.insert(regNum);
2441
2442  if (DEBUGME) {
2443    errs() << "addLoopContOnReg loop-header = BB"
2444           << loopRep->getHeader()->getNumber()
2445           << "  regNum = " << regNum << "\n";
2446  }
2447} // addLoopContOnReg
2448
2449template<class PassT>
2450void CFGStructurizer<PassT>::addLoopBreakInitReg(LoopT *loopRep, RegiT regNum) {
2451  LoopLandInfo *&theEntry = loopLandInfoMap[loopRep];
2452
2453  if (theEntry == NULL) {
2454    theEntry = new LoopLandInfo();
2455  }
2456  theEntry->breakInitRegs.insert(regNum);
2457
2458  if (DEBUGME) {
2459    errs() << "addLoopBreakInitReg loop-header = BB"
2460           << loopRep->getHeader()->getNumber()
2461           << "  regNum = " << regNum << "\n";
2462  }
2463} // addLoopBreakInitReg
2464
2465template<class PassT>
2466void CFGStructurizer<PassT>::addLoopContInitReg(LoopT *loopRep, RegiT regNum) {
2467  LoopLandInfo *&theEntry = loopLandInfoMap[loopRep];
2468
2469  if (theEntry == NULL) {
2470    theEntry = new LoopLandInfo();
2471  }
2472  theEntry->contInitRegs.insert(regNum);
2473
2474  if (DEBUGME) {
2475    errs() << "addLoopContInitReg loop-header = BB"
2476           << loopRep->getHeader()->getNumber()
2477           << "  regNum = " << regNum << "\n";
2478  }
2479} // addLoopContInitReg
2480
2481template<class PassT>
2482void CFGStructurizer<PassT>::addLoopEndbranchInitReg(LoopT *loopRep,
2483                                                     RegiT regNum) {
2484  LoopLandInfo *&theEntry = loopLandInfoMap[loopRep];
2485
2486  if (theEntry == NULL) {
2487    theEntry = new LoopLandInfo();
2488  }
2489  theEntry->endbranchInitRegs.insert(regNum);
2490
2491  if (DEBUGME)
2492  {
2493        errs() << "addLoopEndbranchInitReg loop-header = BB"
2494      << loopRep->getHeader()->getNumber()
2495      << "  regNum = " << regNum << "\n";
2496  }
2497} // addLoopEndbranchInitReg
2498
2499template<class PassT>
2500typename CFGStructurizer<PassT>::LoopLandInfo *
2501CFGStructurizer<PassT>::getLoopLandInfo(LoopT *loopRep) {
2502  LoopLandInfo *&theEntry = loopLandInfoMap[loopRep];
2503
2504  return theEntry;
2505} // getLoopLandInfo
2506
2507template<class PassT>
2508typename CFGStructurizer<PassT>::BlockT *
2509CFGStructurizer<PassT>::getLoopLandBlock(LoopT *loopRep) {
2510  LoopLandInfo *&theEntry = loopLandInfoMap[loopRep];
2511
2512  return theEntry ? theEntry->landBlk : NULL;
2513} // getLoopLandBlock
2514
2515
2516template<class PassT>
2517bool CFGStructurizer<PassT>::hasBackEdge(BlockT *curBlk) {
2518  LoopT *loopRep = loopInfo->getLoopFor(curBlk);
2519  if (loopRep == NULL)
2520    return false;
2521
2522  BlockT *loopHeader = loopRep->getHeader();
2523
2524  return curBlk->isSuccessor(loopHeader);
2525
2526} //hasBackEdge
2527
2528template<class PassT>
2529unsigned CFGStructurizer<PassT>::getLoopDepth(LoopT *loopRep) {
2530  return loopRep ? loopRep->getLoopDepth() : 0;
2531} //getLoopDepth
2532
2533template<class PassT>
2534int CFGStructurizer<PassT>::countActiveBlock
2535(typename SmallVector<BlockT*, DEFAULT_VEC_SLOTS>::const_iterator iterStart,
2536 typename SmallVector<BlockT*, DEFAULT_VEC_SLOTS>::const_iterator iterEnd) {
2537  int count = 0;
2538  while (iterStart != iterEnd) {
2539    if (!isRetiredBlock(*iterStart)) {
2540      ++count;
2541    }
2542    ++iterStart;
2543  }
2544
2545  return count;
2546} //countActiveBlock
2547
2548// This is work around solution for findNearestCommonDominator not avaiable to
2549// post dom a proper fix should go to Dominators.h.
2550
2551template<class PassT>
2552typename CFGStructurizer<PassT>::BlockT*
2553CFGStructurizer<PassT>::findNearestCommonPostDom(BlockT *blk1, BlockT *blk2) {
2554
2555  if (postDomTree->dominates(blk1, blk2)) {
2556    return blk1;
2557  }
2558  if (postDomTree->dominates(blk2, blk1)) {
2559    return blk2;
2560  }
2561
2562  DomTreeNodeT *node1 = postDomTree->getNode(blk1);
2563  DomTreeNodeT *node2 = postDomTree->getNode(blk2);
2564
2565  // Handle newly cloned node.
2566  if (node1 == NULL && blk1->succ_size() == 1) {
2567    return findNearestCommonPostDom(*blk1->succ_begin(), blk2);
2568  }
2569  if (node2 == NULL && blk2->succ_size() == 1) {
2570    return findNearestCommonPostDom(blk1, *blk2->succ_begin());
2571  }
2572
2573  if (node1 == NULL || node2 == NULL) {
2574    return NULL;
2575  }
2576
2577  node1 = node1->getIDom();
2578  while (node1) {
2579    if (postDomTree->dominates(node1, node2)) {
2580      return node1->getBlock();
2581    }
2582    node1 = node1->getIDom();
2583  }
2584
2585  return NULL;
2586}
2587
2588template<class PassT>
2589typename CFGStructurizer<PassT>::BlockT *
2590CFGStructurizer<PassT>::findNearestCommonPostDom
2591(typename std::set<BlockT *> &blks) {
2592  BlockT *commonDom;
2593  typename std::set<BlockT *>::const_iterator iter = blks.begin();
2594  typename std::set<BlockT *>::const_iterator iterEnd = blks.end();
2595  for (commonDom = *iter; iter != iterEnd && commonDom != NULL; ++iter) {
2596    BlockT *curBlk = *iter;
2597    if (curBlk != commonDom) {
2598      commonDom = findNearestCommonPostDom(curBlk, commonDom);
2599    }
2600  }
2601
2602  if (DEBUGME) {
2603    errs() << "Common post dominator for exit blocks is ";
2604    if (commonDom) {
2605          errs() << "BB" << commonDom->getNumber() << "\n";
2606    } else {
2607      errs() << "NULL\n";
2608    }
2609  }
2610
2611  return commonDom;
2612} //findNearestCommonPostDom
2613
2614} //end namespace llvm
2615
2616//todo: move-end
2617
2618
2619//===----------------------------------------------------------------------===//
2620//
2621// CFGStructurizer for AMDIL
2622//
2623//===----------------------------------------------------------------------===//
2624
2625
2626using namespace llvmCFGStruct;
2627
2628namespace llvm
2629{
2630class AMDILCFGStructurizer : public MachineFunctionPass
2631{
2632public:
2633  typedef MachineInstr              InstructionType;
2634  typedef MachineFunction           FunctionType;
2635  typedef MachineBasicBlock         BlockType;
2636  typedef MachineLoopInfo           LoopinfoType;
2637  typedef MachineDominatorTree      DominatortreeType;
2638  typedef MachinePostDominatorTree  PostDominatortreeType;
2639  typedef MachineDomTreeNode        DomTreeNodeType;
2640  typedef MachineLoop               LoopType;
2641//private:
2642  TargetMachine &TM;
2643  const TargetInstrInfo *TII;
2644
2645//public:
2646//  static char ID;
2647
2648public:
2649  AMDILCFGStructurizer(char &pid, TargetMachine &tm AMDIL_OPT_LEVEL_DECL);
2650  const TargetInstrInfo *getTargetInstrInfo() const;
2651  //bool runOnMachineFunction(MachineFunction &F);
2652
2653private:
2654
2655};   //end of class AMDILCFGStructurizer
2656
2657//char AMDILCFGStructurizer::ID = 0;
2658} //end of namespace llvm
2659AMDILCFGStructurizer::AMDILCFGStructurizer(char &pid, TargetMachine &tm
2660                                           AMDIL_OPT_LEVEL_DECL)
2661: MachineFunctionPass(pid), TM(tm), TII(tm.getInstrInfo()) {
2662}
2663
2664const TargetInstrInfo *AMDILCFGStructurizer::getTargetInstrInfo() const {
2665  return TII;
2666}
2667//===----------------------------------------------------------------------===//
2668//
2669// CFGPrepare
2670//
2671//===----------------------------------------------------------------------===//
2672
2673
2674using namespace llvmCFGStruct;
2675
2676namespace llvm
2677{
2678class AMDILCFGPrepare : public AMDILCFGStructurizer
2679{
2680public:
2681  static char ID;
2682
2683public:
2684  AMDILCFGPrepare(TargetMachine &tm AMDIL_OPT_LEVEL_DECL);
2685
2686  virtual const char *getPassName() const;
2687  virtual void getAnalysisUsage(AnalysisUsage &AU) const;
2688
2689  bool runOnMachineFunction(MachineFunction &F);
2690
2691private:
2692
2693};   //end of class AMDILCFGPrepare
2694
2695char AMDILCFGPrepare::ID = 0;
2696} //end of namespace llvm
2697
2698AMDILCFGPrepare::AMDILCFGPrepare(TargetMachine &tm AMDIL_OPT_LEVEL_DECL)
2699  : AMDILCFGStructurizer(ID, tm  AMDIL_OPT_LEVEL_VAR)
2700{
2701}
2702const char *AMDILCFGPrepare::getPassName() const {
2703  return "AMD IL Control Flow Graph Preparation Pass";
2704}
2705
2706void AMDILCFGPrepare::getAnalysisUsage(AnalysisUsage &AU) const {
2707  AU.addPreserved<MachineFunctionAnalysis>();
2708  AU.addRequired<MachineFunctionAnalysis>();
2709  AU.addRequired<MachineDominatorTree>();
2710  AU.addRequired<MachinePostDominatorTree>();
2711  AU.addRequired<MachineLoopInfo>();
2712}
2713
2714//===----------------------------------------------------------------------===//
2715//
2716// CFGPerform
2717//
2718//===----------------------------------------------------------------------===//
2719
2720
2721using namespace llvmCFGStruct;
2722
2723namespace llvm
2724{
2725class AMDILCFGPerform : public AMDILCFGStructurizer
2726{
2727public:
2728  static char ID;
2729
2730public:
2731  AMDILCFGPerform(TargetMachine &tm AMDIL_OPT_LEVEL_DECL);
2732  virtual const char *getPassName() const;
2733  virtual void getAnalysisUsage(AnalysisUsage &AU) const;
2734  bool runOnMachineFunction(MachineFunction &F);
2735
2736private:
2737
2738};   //end of class AMDILCFGPerform
2739
2740char AMDILCFGPerform::ID = 0;
2741} //end of namespace llvm
2742
2743  AMDILCFGPerform::AMDILCFGPerform(TargetMachine &tm AMDIL_OPT_LEVEL_DECL)
2744: AMDILCFGStructurizer(ID, tm AMDIL_OPT_LEVEL_VAR)
2745{
2746}
2747
2748const char *AMDILCFGPerform::getPassName() const {
2749  return "AMD IL Control Flow Graph structurizer Pass";
2750}
2751
2752void AMDILCFGPerform::getAnalysisUsage(AnalysisUsage &AU) const {
2753  AU.addPreserved<MachineFunctionAnalysis>();
2754  AU.addRequired<MachineFunctionAnalysis>();
2755  AU.addRequired<MachineDominatorTree>();
2756  AU.addRequired<MachinePostDominatorTree>();
2757  AU.addRequired<MachineLoopInfo>();
2758}
2759
2760//===----------------------------------------------------------------------===//
2761//
2762// CFGStructTraits<AMDILCFGStructurizer>
2763//
2764//===----------------------------------------------------------------------===//
2765
2766namespace llvmCFGStruct
2767{
2768// this class is tailor to the AMDIL backend
2769template<>
2770struct CFGStructTraits<AMDILCFGStructurizer>
2771{
2772  typedef int RegiT;
2773
2774  static int getBreakNzeroOpcode(int oldOpcode) {
2775    switch(oldOpcode) {
2776      ExpandCaseToAllScalarReturn(AMDIL::BRANCH_COND, AMDIL::BREAK_LOGICALNZ);
2777    default:
2778      assert(0 && "internal error");
2779    };
2780    return -1;
2781  }
2782
2783  static int getBreakZeroOpcode(int oldOpcode) {
2784    switch(oldOpcode) {
2785      ExpandCaseToAllScalarReturn(AMDIL::BRANCH_COND, AMDIL::BREAK_LOGICALZ);
2786    default:
2787      assert(0 && "internal error");
2788    };
2789    return -1;
2790  }
2791
2792  static int getBranchNzeroOpcode(int oldOpcode) {
2793    switch(oldOpcode) {
2794      ExpandCaseToAllScalarReturn(AMDIL::BRANCH_COND, AMDIL::IF_LOGICALNZ);
2795    default:
2796      assert(0 && "internal error");
2797    };
2798    return -1;
2799  }
2800
2801  static int getBranchZeroOpcode(int oldOpcode) {
2802    switch(oldOpcode) {
2803      ExpandCaseToAllScalarReturn(AMDIL::BRANCH_COND, AMDIL::IF_LOGICALZ);
2804    default:
2805      assert(0 && "internal error");
2806    };
2807    return -1;
2808  }
2809
2810  static int getContinueNzeroOpcode(int oldOpcode)
2811  {
2812    switch(oldOpcode) {
2813      ExpandCaseToAllScalarReturn(AMDIL::BRANCH_COND, AMDIL::CONTINUE_LOGICALNZ);
2814      default:
2815        assert(0 && "internal error");
2816    };
2817    return -1;
2818  }
2819
2820  static int getContinueZeroOpcode(int oldOpcode) {
2821    switch(oldOpcode) {
2822      ExpandCaseToAllScalarReturn(AMDIL::BRANCH_COND, AMDIL::CONTINUE_LOGICALZ);
2823    default:
2824      assert(0 && "internal error");
2825    };
2826    return -1;
2827  }
2828
2829// the explicitly represented branch target is the true branch target
2830#define getExplicitBranch getTrueBranch
2831#define setExplicitBranch setTrueBranch
2832
2833  static MachineBasicBlock *getTrueBranch(MachineInstr *instr) {
2834    return instr->getOperand(0).getMBB();
2835  }
2836
2837  static void setTrueBranch(MachineInstr *instr, MachineBasicBlock *blk) {
2838    instr->getOperand(0).setMBB(blk);
2839  }
2840
2841  static MachineBasicBlock *
2842  getFalseBranch(MachineBasicBlock *blk, MachineInstr *instr) {
2843    assert(blk->succ_size() == 2);
2844    MachineBasicBlock *trueBranch = getTrueBranch(instr);
2845    MachineBasicBlock::succ_iterator iter = blk->succ_begin();
2846    MachineBasicBlock::succ_iterator iterNext = iter;
2847    ++iterNext;
2848
2849    return (*iter == trueBranch) ? *iterNext : *iter;
2850  }
2851
2852  static bool isCondBranch(MachineInstr *instr) {
2853    switch (instr->getOpcode()) {
2854      ExpandCaseToAllScalarTypes(AMDIL::BRANCH_COND);
2855      break;
2856    default:
2857      return false;
2858    }
2859    return true;
2860  }
2861
2862  static bool isUncondBranch(MachineInstr *instr) {
2863    switch (instr->getOpcode()) {
2864    case AMDIL::BRANCH:
2865      break;
2866    default:
2867      return false;
2868    }
2869    return true;
2870  }
2871
2872  static bool isPhimove(MachineInstr *instr) {
2873    switch (instr->getOpcode()) {
2874      ExpandCaseToAllTypes(AMDIL::MOVE);
2875      break;
2876    default:
2877      return false;
2878    }
2879    return true;
2880  }
2881
2882  static DebugLoc getLastDebugLocInBB(MachineBasicBlock *blk) {
2883    //get DebugLoc from the first MachineBasicBlock instruction with debug info
2884    DebugLoc DL;
2885	for (MachineBasicBlock::iterator iter = blk->begin(); iter != blk->end(); ++iter) {
2886	  MachineInstr *instr = &(*iter);
2887	  if (instr->getDebugLoc().isUnknown() == false) {
2888	    DL = instr->getDebugLoc();
2889	  }
2890    }
2891    return DL;
2892  }
2893
2894  static MachineInstr *getNormalBlockBranchInstr(MachineBasicBlock *blk) {
2895    MachineBasicBlock::reverse_iterator iter = blk->rbegin();
2896    MachineInstr *instr = &*iter;
2897    if (instr && (isCondBranch(instr) || isUncondBranch(instr))) {
2898      return instr;
2899    }
2900    return NULL;
2901  }
2902
2903  // The correct naming for this is getPossibleLoopendBlockBranchInstr.
2904  //
2905  // BB with backward-edge could have move instructions after the branch
2906  // instruction.  Such move instruction "belong to" the loop backward-edge.
2907  //
2908  static MachineInstr *getLoopendBlockBranchInstr(MachineBasicBlock *blk) {
2909    for (MachineBasicBlock::reverse_iterator iter = blk->rbegin(),
2910         iterEnd = blk->rend(); iter != iterEnd; ++iter) {
2911      // FIXME: Simplify
2912      MachineInstr *instr = &*iter;
2913      if (instr) {
2914        if (isCondBranch(instr) || isUncondBranch(instr)) {
2915          return instr;
2916        } else if (!isPhimove(instr)) {
2917          break;
2918        }
2919      }
2920    }
2921    return NULL;
2922  }
2923
2924  static MachineInstr *getReturnInstr(MachineBasicBlock *blk) {
2925    MachineBasicBlock::reverse_iterator iter = blk->rbegin();
2926    if (iter != blk->rend()) {
2927      MachineInstr *instr = &(*iter);
2928      if (instr->getOpcode() == AMDIL::RETURN) {
2929        return instr;
2930      }
2931    }
2932    return NULL;
2933  }
2934
2935  static MachineInstr *getContinueInstr(MachineBasicBlock *blk) {
2936    MachineBasicBlock::reverse_iterator iter = blk->rbegin();
2937    if (iter != blk->rend()) {
2938      MachineInstr *instr = &(*iter);
2939      if (instr->getOpcode() == AMDIL::CONTINUE) {
2940        return instr;
2941      }
2942    }
2943    return NULL;
2944  }
2945
2946  static MachineInstr *getLoopBreakInstr(MachineBasicBlock *blk) {
2947    for (MachineBasicBlock::iterator iter = blk->begin(); (iter != blk->end()); ++iter) {
2948      MachineInstr *instr = &(*iter);
2949      if ((instr->getOpcode() == AMDIL::BREAK_LOGICALNZ_i32) || (instr->getOpcode() == AMDIL::BREAK_LOGICALZ_i32)) {
2950        return instr;
2951      }
2952    }
2953    return NULL;
2954  }
2955
2956  static bool isReturnBlock(MachineBasicBlock *blk) {
2957    MachineInstr *instr = getReturnInstr(blk);
2958    bool isReturn = (blk->succ_size() == 0);
2959    if (instr) {
2960      assert(isReturn);
2961    } else if (isReturn) {
2962      if (DEBUGME) {
2963        errs() << "BB" << blk->getNumber()
2964               <<" is return block without RETURN instr\n";
2965      }
2966    }
2967
2968    return  isReturn;
2969  }
2970
2971  static MachineBasicBlock::iterator
2972  getInstrPos(MachineBasicBlock *blk, MachineInstr *instr) {
2973    assert(instr->getParent() == blk && "instruction doesn't belong to block");
2974    MachineBasicBlock::iterator iter = blk->begin();
2975    MachineBasicBlock::iterator iterEnd = blk->end();
2976    while (&(*iter) != instr && iter != iterEnd) {
2977      ++iter;
2978    }
2979
2980    assert(iter != iterEnd);
2981    return iter;
2982  }//getInstrPos
2983
2984  static MachineInstr *insertInstrBefore(MachineBasicBlock *blk, int newOpcode,
2985                                         AMDILCFGStructurizer *passRep) {
2986    return insertInstrBefore(blk,newOpcode,passRep,DebugLoc());
2987  } //insertInstrBefore
2988
2989  static MachineInstr *insertInstrBefore(MachineBasicBlock *blk, int newOpcode,
2990                                         AMDILCFGStructurizer *passRep, DebugLoc DL) {
2991    const TargetInstrInfo *tii = passRep->getTargetInstrInfo();
2992    MachineInstr *newInstr =
2993      blk->getParent()->CreateMachineInstr(tii->get(newOpcode), DL);
2994
2995    MachineBasicBlock::iterator res;
2996    if (blk->begin() != blk->end()) {
2997      blk->insert(blk->begin(), newInstr);
2998    } else {
2999      blk->push_back(newInstr);
3000    }
3001
3002    SHOWNEWINSTR(newInstr);
3003
3004    return newInstr;
3005  } //insertInstrBefore
3006
3007  static void insertInstrEnd(MachineBasicBlock *blk, int newOpcode,
3008                             AMDILCFGStructurizer *passRep) {
3009    insertInstrEnd(blk,newOpcode,passRep,DebugLoc());
3010  } //insertInstrEnd
3011
3012  static void insertInstrEnd(MachineBasicBlock *blk, int newOpcode,
3013                             AMDILCFGStructurizer *passRep, DebugLoc DL) {
3014    const TargetInstrInfo *tii = passRep->getTargetInstrInfo();
3015   MachineInstr *newInstr = blk->getParent()
3016      ->CreateMachineInstr(tii->get(newOpcode), DL);
3017
3018    blk->push_back(newInstr);
3019    //assume the instruction doesn't take any reg operand ...
3020
3021    SHOWNEWINSTR(newInstr);
3022  } //insertInstrEnd
3023
3024  static MachineInstr *insertInstrBefore(MachineBasicBlock::iterator instrPos,
3025                                         int newOpcode,
3026                                         AMDILCFGStructurizer *passRep) {
3027    MachineInstr *oldInstr = &(*instrPos);
3028    const TargetInstrInfo *tii = passRep->getTargetInstrInfo();
3029    MachineBasicBlock *blk = oldInstr->getParent();
3030    MachineInstr *newInstr =
3031      blk->getParent()->CreateMachineInstr(tii->get(newOpcode),
3032                                           DebugLoc());
3033
3034    blk->insert(instrPos, newInstr);
3035    //assume the instruction doesn't take any reg operand ...
3036
3037    SHOWNEWINSTR(newInstr);
3038    return newInstr;
3039  } //insertInstrBefore
3040
3041  static void insertCondBranchBefore(MachineBasicBlock::iterator instrPos,
3042                                     int newOpcode,
3043                                     AMDILCFGStructurizer *passRep,
3044									 DebugLoc DL) {
3045    MachineInstr *oldInstr = &(*instrPos);
3046    const TargetInstrInfo *tii = passRep->getTargetInstrInfo();
3047    MachineBasicBlock *blk = oldInstr->getParent();
3048    MachineInstr *newInstr =
3049      blk->getParent()->CreateMachineInstr(tii->get(newOpcode),
3050                                           DL);
3051
3052    blk->insert(instrPos, newInstr);
3053    MachineInstrBuilder(newInstr).addReg(oldInstr->getOperand(1).getReg(),
3054                                         false);
3055
3056    SHOWNEWINSTR(newInstr);
3057    //erase later oldInstr->eraseFromParent();
3058  } //insertCondBranchBefore
3059
3060  static void insertCondBranchBefore(MachineBasicBlock *blk,
3061                                     MachineBasicBlock::iterator insertPos,
3062                                     int newOpcode,
3063                                     AMDILCFGStructurizer *passRep,
3064                                     RegiT regNum,
3065									 DebugLoc DL) {
3066    const TargetInstrInfo *tii = passRep->getTargetInstrInfo();
3067
3068    MachineInstr *newInstr =
3069      blk->getParent()->CreateMachineInstr(tii->get(newOpcode), DL);
3070
3071    //insert before
3072    blk->insert(insertPos, newInstr);
3073    MachineInstrBuilder(newInstr).addReg(regNum, false);
3074
3075    SHOWNEWINSTR(newInstr);
3076  } //insertCondBranchBefore
3077
3078  static void insertCondBranchEnd(MachineBasicBlock *blk,
3079                                  int newOpcode,
3080                                  AMDILCFGStructurizer *passRep,
3081                                  RegiT regNum) {
3082    const TargetInstrInfo *tii = passRep->getTargetInstrInfo();
3083    MachineInstr *newInstr =
3084      blk->getParent()->CreateMachineInstr(tii->get(newOpcode), DebugLoc());
3085
3086    blk->push_back(newInstr);
3087    MachineInstrBuilder(newInstr).addReg(regNum, false);
3088
3089    SHOWNEWINSTR(newInstr);
3090  } //insertCondBranchEnd
3091
3092
3093  static void insertAssignInstrBefore(MachineBasicBlock::iterator instrPos,
3094                                      AMDILCFGStructurizer *passRep,
3095                                      RegiT regNum, int regVal) {
3096    MachineInstr *oldInstr = &(*instrPos);
3097    const TargetInstrInfo *tii = passRep->getTargetInstrInfo();
3098    MachineBasicBlock *blk = oldInstr->getParent();
3099    MachineInstr *newInstr =
3100      blk->getParent()->CreateMachineInstr(tii->get(AMDIL::LOADCONST_i32),
3101                                           DebugLoc());
3102    MachineInstrBuilder(newInstr).addReg(regNum, RegState::Define); //set target
3103    MachineInstrBuilder(newInstr).addImm(regVal); //set src value
3104
3105    blk->insert(instrPos, newInstr);
3106
3107    SHOWNEWINSTR(newInstr);
3108  } //insertAssignInstrBefore
3109
3110  static void insertAssignInstrBefore(MachineBasicBlock *blk,
3111                                      AMDILCFGStructurizer *passRep,
3112                                      RegiT regNum, int regVal) {
3113    const TargetInstrInfo *tii = passRep->getTargetInstrInfo();
3114
3115    MachineInstr *newInstr =
3116      blk->getParent()->CreateMachineInstr(tii->get(AMDIL::LOADCONST_i32),
3117                                           DebugLoc());
3118    MachineInstrBuilder(newInstr).addReg(regNum, RegState::Define); //set target
3119    MachineInstrBuilder(newInstr).addImm(regVal); //set src value
3120
3121    if (blk->begin() != blk->end()) {
3122      blk->insert(blk->begin(), newInstr);
3123    } else {
3124      blk->push_back(newInstr);
3125    }
3126
3127    SHOWNEWINSTR(newInstr);
3128
3129  } //insertInstrBefore
3130
3131  static void insertCompareInstrBefore(MachineBasicBlock *blk,
3132                                       MachineBasicBlock::iterator instrPos,
3133                                       AMDILCFGStructurizer *passRep,
3134                                       RegiT dstReg, RegiT src1Reg,
3135                                       RegiT src2Reg) {
3136    const TargetInstrInfo *tii = passRep->getTargetInstrInfo();
3137    MachineInstr *newInstr =
3138      blk->getParent()->CreateMachineInstr(tii->get(AMDIL::IEQ), DebugLoc());
3139
3140    MachineInstrBuilder(newInstr).addReg(dstReg, RegState::Define); //set target
3141    MachineInstrBuilder(newInstr).addReg(src1Reg); //set src value
3142    MachineInstrBuilder(newInstr).addReg(src2Reg); //set src value
3143
3144    blk->insert(instrPos, newInstr);
3145    SHOWNEWINSTR(newInstr);
3146
3147  } //insertCompareInstrBefore
3148
3149  static void cloneSuccessorList(MachineBasicBlock *dstBlk,
3150                                 MachineBasicBlock *srcBlk) {
3151    for (MachineBasicBlock::succ_iterator iter = srcBlk->succ_begin(),
3152         iterEnd = srcBlk->succ_end(); iter != iterEnd; ++iter) {
3153      dstBlk->addSuccessor(*iter);  // *iter's predecessor is also taken care of
3154    }
3155  } //cloneSuccessorList
3156
3157  static MachineBasicBlock *clone(MachineBasicBlock *srcBlk) {
3158    MachineFunction *func = srcBlk->getParent();
3159    MachineBasicBlock *newBlk = func->CreateMachineBasicBlock();
3160    func->push_back(newBlk);  //insert to function
3161    //newBlk->setNumber(srcBlk->getNumber());
3162    for (MachineBasicBlock::iterator iter = srcBlk->begin(),
3163         iterEnd = srcBlk->end();
3164         iter != iterEnd; ++iter) {
3165      MachineInstr *instr = func->CloneMachineInstr(iter);
3166      // This is a workaround for LLVM bugzilla 8420 because CloneMachineInstr
3167      // does not clone the AsmPrinterFlags.
3168      instr->setAsmPrinterFlag(
3169         (llvm::MachineInstr::CommentFlag)iter->getAsmPrinterFlags());
3170      newBlk->push_back(instr);
3171    }
3172    return newBlk;
3173  }
3174
3175  //MachineBasicBlock::ReplaceUsesOfBlockWith doesn't serve the purpose because
3176  //the AMDIL instruction is not recognized as terminator fix this and retire
3177  //this routine
3178  static void replaceInstrUseOfBlockWith(MachineBasicBlock *srcBlk,
3179                                         MachineBasicBlock *oldBlk,
3180                                         MachineBasicBlock *newBlk) {
3181    MachineInstr *branchInstr = getLoopendBlockBranchInstr(srcBlk);
3182    if (branchInstr && isCondBranch(branchInstr) &&
3183        getExplicitBranch(branchInstr) == oldBlk) {
3184      setExplicitBranch(branchInstr, newBlk);
3185    }
3186  }
3187
3188  static void wrapup(MachineBasicBlock *entryBlk) {
3189    assert((!entryBlk->getParent()->getJumpTableInfo()
3190            || entryBlk->getParent()->getJumpTableInfo()->isEmpty())
3191           && "found a jump table");
3192
3193     //collect continue right before endloop
3194     SmallVector<MachineInstr *, DEFAULT_VEC_SLOTS> contInstr;
3195     MachineBasicBlock::iterator pre = entryBlk->begin();
3196     MachineBasicBlock::iterator iterEnd = entryBlk->end();
3197     MachineBasicBlock::iterator iter = pre;
3198     while (iter != iterEnd) {
3199       if (pre->getOpcode() == AMDIL::CONTINUE
3200           && iter->getOpcode() == AMDIL::ENDLOOP) {
3201         contInstr.push_back(pre);
3202       }
3203       pre = iter;
3204       ++iter;
3205     } //end while
3206
3207     //delete continue right before endloop
3208     for (unsigned i = 0; i < contInstr.size(); ++i) {
3209        contInstr[i]->eraseFromParent();
3210     }
3211
3212     // TODO to fix up jump table so later phase won't be confused.  if
3213     // (jumpTableInfo->isEmpty() == false) { need to clean the jump table, but
3214     // there isn't such an interface yet.  alternatively, replace all the other
3215     // blocks in the jump table with the entryBlk //}
3216
3217  } //wrapup
3218
3219  static MachineDominatorTree *getDominatorTree(AMDILCFGStructurizer &pass) {
3220    return &pass.getAnalysis<MachineDominatorTree>();
3221  }
3222
3223  static MachinePostDominatorTree*
3224  getPostDominatorTree(AMDILCFGStructurizer &pass) {
3225    return &pass.getAnalysis<MachinePostDominatorTree>();
3226  }
3227
3228  static MachineLoopInfo *getLoopInfo(AMDILCFGStructurizer &pass) {
3229    return &pass.getAnalysis<MachineLoopInfo>();
3230  }
3231}; // template class CFGStructTraits
3232} //end of namespace llvm
3233
3234// createAMDILCFGPreparationPass- Returns a pass
3235FunctionPass *llvm::createAMDILCFGPreparationPass(TargetMachine &tm
3236                                                  AMDIL_OPT_LEVEL_DECL) {
3237  return new AMDILCFGPrepare(tm  AMDIL_OPT_LEVEL_VAR);
3238}
3239
3240bool AMDILCFGPrepare::runOnMachineFunction(MachineFunction &func) {
3241  return llvmCFGStruct::CFGStructurizer<AMDILCFGStructurizer>().prepare(func,
3242                                                                        *this);
3243}
3244
3245// createAMDILCFGStructurizerPass- Returns a pass
3246FunctionPass *llvm::createAMDILCFGStructurizerPass(TargetMachine &tm
3247                                                   AMDIL_OPT_LEVEL_DECL) {
3248  return new AMDILCFGPerform(tm  AMDIL_OPT_LEVEL_VAR);
3249}
3250
3251bool AMDILCFGPerform::runOnMachineFunction(MachineFunction &func) {
3252  return llvmCFGStruct::CFGStructurizer<AMDILCFGStructurizer>().run(func,
3253                                                                    *this);
3254}
3255
3256//end of file newline goes below
3257
3258