1 //===- CloneLoop.cpp - Clone loop nest ------------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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"
22 /// CloneDominatorInfo - Clone basicblock's dominator tree and, if available,
23 /// dominance info. It is expected that basic block is already cloned.
24 static void CloneDominatorInfo(BasicBlock *BB,
25 ValueMap<const Value *, Value *> &VMap,
27 DominanceFrontier *DF) {
29 assert (DT && "DominatorTree is not available");
30 ValueMap<const Value *, Value*>::iterator BI = VMap.find(BB);
31 assert (BI != VMap.end() && "BasicBlock clone is missing");
32 BasicBlock *NewBB = cast<BasicBlock>(BI->second);
34 // NewBB already got dominator info.
35 if (DT->getNode(NewBB))
38 assert (DT->getNode(BB) && "BasicBlock does not have dominator info");
39 // Entry block is not expected here. Infinite loops are not to cloned.
40 assert (DT->getNode(BB)->getIDom() && "BasicBlock does not have immediate dominator");
41 BasicBlock *BBDom = DT->getNode(BB)->getIDom()->getBlock();
43 // NewBB's dominator is either BB's dominator or BB's dominator's clone.
44 BasicBlock *NewBBDom = BBDom;
45 ValueMap<const Value *, Value*>::iterator BBDomI = VMap.find(BBDom);
46 if (BBDomI != VMap.end()) {
47 NewBBDom = cast<BasicBlock>(BBDomI->second);
48 if (!DT->getNode(NewBBDom))
49 CloneDominatorInfo(BBDom, VMap, DT, DF);
51 DT->addNewBlock(NewBB, NewBBDom);
53 // Copy cloned dominance frontiner set
55 DominanceFrontier::DomSetType NewDFSet;
56 DominanceFrontier::iterator DFI = DF->find(BB);
57 if ( DFI != DF->end()) {
58 DominanceFrontier::DomSetType S = DFI->second;
59 for (DominanceFrontier::DomSetType::iterator I = S.begin(), E = S.end();
62 ValueMap<const Value*, Value*>::iterator IDM = VMap.find(DB);
63 if (IDM != VMap.end())
64 NewDFSet.insert(cast<BasicBlock>(IDM->second));
69 DF->addBasicBlock(NewBB, NewDFSet);
73 /// CloneLoop - Clone Loop. Clone dominator info. Populate VMap
74 /// using old blocks to new blocks mapping.
75 Loop *llvm::CloneLoop(Loop *OrigL, LPPassManager *LPM, LoopInfo *LI,
76 ValueMap<const Value *, Value *> &VMap, Pass *P) {
78 DominatorTree *DT = NULL;
79 DominanceFrontier *DF = NULL;
81 DT = P->getAnalysisIfAvailable<DominatorTree>();
82 DF = P->getAnalysisIfAvailable<DominanceFrontier>();
85 SmallVector<BasicBlock *, 16> NewBlocks;
87 // Populate loop nest.
88 SmallVector<Loop *, 8> LoopNest;
89 LoopNest.push_back(OrigL);
92 Loop *NewParentLoop = NULL;
94 Loop *L = LoopNest.pop_back_val();
95 Loop *NewLoop = new Loop();
98 NewParentLoop = NewLoop;
100 LPM->insertLoop(NewLoop, L->getParentLoop());
102 // Clone Basic Blocks.
103 for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
106 BasicBlock *NewBB = CloneBasicBlock(BB, VMap, ".clone");
109 LPM->cloneBasicBlockSimpleAnalysis(BB, NewBB, L);
110 NewLoop->addBasicBlockToLoop(NewBB, LI->getBase());
111 NewBlocks.push_back(NewBB);
114 // Clone dominator info.
116 for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
119 CloneDominatorInfo(BB, VMap, DT, DF);
123 for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
124 LoopNest.push_back(*I);
125 } while (!LoopNest.empty());
127 // Remap instructions to reference operands from VMap.
128 for(SmallVector<BasicBlock *, 16>::iterator NBItr = NewBlocks.begin(),
129 NBE = NewBlocks.end(); NBItr != NBE; ++NBItr) {
130 BasicBlock *NB = *NBItr;
131 for(BasicBlock::iterator BI = NB->begin(), BE = NB->end();
133 Instruction *Insn = BI;
134 for (unsigned index = 0, num_ops = Insn->getNumOperands();
135 index != num_ops; ++index) {
136 Value *Op = Insn->getOperand(index);
137 ValueMap<const Value *, Value *>::iterator OpItr = VMap.find(Op);
138 if (OpItr != VMap.end())
139 Insn->setOperand(index, OpItr->second);
144 BasicBlock *Latch = OrigL->getLoopLatch();
145 Function *F = Latch->getParent();
146 F->getBasicBlockList().insert(OrigL->getHeader(),
147 NewBlocks.begin(), NewBlocks.end());
150 return NewParentLoop;