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"
18 #include "llvm/ADT/DenseMap.h"
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
,
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
))
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
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();
63 DenseMap
<const Value
*, Value
*>::iterator IDM
= ValueMap
.find(DB
);
64 if (IDM
!= ValueMap
.end())
65 NewDFSet
.insert(cast
<BasicBlock
>(IDM
->second
));
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
;
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();
97 Loop
*NewLoop
= new Loop();
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();
108 BasicBlock
*NewBB
= CloneBasicBlock(BB
, ValueMap
, ".clone");
109 ValueMap
[BB
] = NewBB
;
111 LPM
->cloneBasicBlockSimpleAnalysis(BB
, NewBB
, L
);
112 NewLoop
->addBasicBlockToLoop(NewBB
, LI
->getBase());
113 NewBlocks
.push_back(NewBB
);
116 // Clone dominator info.
118 for (Loop::block_iterator I
= L
->block_begin(), E
= L
->block_end();
121 CloneDominatorInfo(BB
, ValueMap
, DT
, DF
);
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();
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
;