Teach getZeroExtendExpr and getSignExtendExpr to use trip-count
[llvm/msp430.git] / lib / Transforms / Utils / CloneLoop.cpp
bloba0306ffa527232f2d7e8e1ca1d94c2aeeffe6374
1 //===- CloneLoop.cpp - Clone loop nest ------------------------------------===//
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 // This file implements the CloneLoop interface which makes a copy of a loop.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/Transforms/Utils/Cloning.h"
15 #include "llvm/BasicBlock.h"
16 #include "llvm/Analysis/LoopPass.h"
17 #include "llvm/Analysis/Dominators.h"
18 #include "llvm/ADT/DenseMap.h"
21 using namespace llvm;
23 /// CloneDominatorInfo - Clone basicblock's dominator tree and, if available,
24 /// dominance info. It is expected that basic block is already cloned.
25 static void CloneDominatorInfo(BasicBlock *BB,
26 DenseMap<const Value *, Value *> &ValueMap,
27 DominatorTree *DT,
28 DominanceFrontier *DF) {
30 assert (DT && "DominatorTree is not available");
31 DenseMap<const Value *, Value*>::iterator BI = ValueMap.find(BB);
32 assert (BI != ValueMap.end() && "BasicBlock clone is missing");
33 BasicBlock *NewBB = cast<BasicBlock>(BI->second);
35 // NewBB already got dominator info.
36 if (DT->getNode(NewBB))
37 return;
39 assert (DT->getNode(BB) && "BasicBlock does not have dominator info");
40 // Entry block is not expected here. Infinite loops are not to cloned.
41 assert (DT->getNode(BB)->getIDom() && "BasicBlock does not have immediate dominator");
42 BasicBlock *BBDom = DT->getNode(BB)->getIDom()->getBlock();
44 // NewBB's dominator is either BB's dominator or BB's dominator's clone.
45 BasicBlock *NewBBDom = BBDom;
46 DenseMap<const Value *, Value*>::iterator BBDomI = ValueMap.find(BBDom);
47 if (BBDomI != ValueMap.end()) {
48 NewBBDom = cast<BasicBlock>(BBDomI->second);
49 if (!DT->getNode(NewBBDom))
50 CloneDominatorInfo(BBDom, ValueMap, DT, DF);
52 DT->addNewBlock(NewBB, NewBBDom);
54 // Copy cloned dominance frontiner set
55 if (DF) {
56 DominanceFrontier::DomSetType NewDFSet;
57 DominanceFrontier::iterator DFI = DF->find(BB);
58 if ( DFI != DF->end()) {
59 DominanceFrontier::DomSetType S = DFI->second;
60 for (DominanceFrontier::DomSetType::iterator I = S.begin(), E = S.end();
61 I != E; ++I) {
62 BasicBlock *DB = *I;
63 DenseMap<const Value*, Value*>::iterator IDM = ValueMap.find(DB);
64 if (IDM != ValueMap.end())
65 NewDFSet.insert(cast<BasicBlock>(IDM->second));
66 else
67 NewDFSet.insert(DB);
70 DF->addBasicBlock(NewBB, NewDFSet);
74 /// CloneLoop - Clone Loop. Clone dominator info. Populate ValueMap
75 /// using old blocks to new blocks mapping.
76 Loop *llvm::CloneLoop(Loop *OrigL, LPPassManager *LPM, LoopInfo *LI,
77 DenseMap<const Value *, Value *> &ValueMap, Pass *P) {
79 DominatorTree *DT = NULL;
80 DominanceFrontier *DF = NULL;
81 if (P) {
82 DT = P->getAnalysisIfAvailable<DominatorTree>();
83 DF = P->getAnalysisIfAvailable<DominanceFrontier>();
86 SmallVector<BasicBlock *, 16> NewBlocks;
88 // Populate loop nest.
89 SmallVector<Loop *, 8> LoopNest;
90 LoopNest.push_back(OrigL);
93 Loop *NewParentLoop = NULL;
94 while (!LoopNest.empty()) {
95 Loop *L = LoopNest.back();
96 LoopNest.pop_back();
97 Loop *NewLoop = new Loop();
99 if (!NewParentLoop)
100 NewParentLoop = NewLoop;
102 LPM->insertLoop(NewLoop, L->getParentLoop());
104 // Clone Basic Blocks.
105 for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
106 I != E; ++I) {
107 BasicBlock *BB = *I;
108 BasicBlock *NewBB = CloneBasicBlock(BB, ValueMap, ".clone");
109 ValueMap[BB] = NewBB;
110 if (P)
111 LPM->cloneBasicBlockSimpleAnalysis(BB, NewBB, L);
112 NewLoop->addBasicBlockToLoop(NewBB, LI->getBase());
113 NewBlocks.push_back(NewBB);
116 // Clone dominator info.
117 if (DT)
118 for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
119 I != E; ++I) {
120 BasicBlock *BB = *I;
121 CloneDominatorInfo(BB, ValueMap, DT, DF);
124 // Process sub loops
125 for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
126 LoopNest.push_back(*I);
129 // Remap instructions to reference operands from ValueMap.
130 for(SmallVector<BasicBlock *, 16>::iterator NBItr = NewBlocks.begin(),
131 NBE = NewBlocks.end(); NBItr != NBE; ++NBItr) {
132 BasicBlock *NB = *NBItr;
133 for(BasicBlock::iterator BI = NB->begin(), BE = NB->end();
134 BI != BE; ++BI) {
135 Instruction *Insn = BI;
136 for (unsigned index = 0, num_ops = Insn->getNumOperands();
137 index != num_ops; ++index) {
138 Value *Op = Insn->getOperand(index);
139 DenseMap<const Value *, Value *>::iterator OpItr = ValueMap.find(Op);
140 if (OpItr != ValueMap.end())
141 Insn->setOperand(index, OpItr->second);
146 BasicBlock *Latch = OrigL->getLoopLatch();
147 Function *F = Latch->getParent();
148 F->getBasicBlockList().insert(OrigL->getHeader(),
149 NewBlocks.begin(), NewBlocks.end());
152 return NewParentLoop;