Devang Patel | 4bc2a0b | 2007-08-10 17:59:47 +0000 | [diff] [blame] | 1 | //===- CloneLoop.cpp - Clone loop nest ------------------------------------===// |
| 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
Chris Lattner | 4ee451d | 2007-12-29 20:36:04 +0000 | [diff] [blame^] | 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
Devang Patel | 4bc2a0b | 2007-08-10 17:59:47 +0000 | [diff] [blame] | 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | // |
| 10 | // This file implements the CloneLoop interface which makes a copy of a loop. |
| 11 | // |
| 12 | //===----------------------------------------------------------------------===// |
| 13 | |
| 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" |
| 19 | |
| 20 | |
| 21 | using namespace llvm; |
| 22 | |
| 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) { |
| 29 | |
| 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); |
| 34 | |
| 35 | // NewBB already got dominator info. |
| 36 | if (DT->getNode(NewBB)) |
| 37 | return; |
| 38 | |
| 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(); |
| 43 | |
| 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); |
| 51 | } |
| 52 | DT->addNewBlock(NewBB, NewBBDom); |
| 53 | |
| 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); |
| 68 | } |
| 69 | } |
| 70 | DF->addBasicBlock(NewBB, NewDFSet); |
| 71 | } |
| 72 | } |
| 73 | |
| 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) { |
| 78 | |
| 79 | DominatorTree *DT = NULL; |
| 80 | DominanceFrontier *DF = NULL; |
| 81 | if (P) { |
| 82 | DT = P->getAnalysisToUpdate<DominatorTree>(); |
| 83 | DF = P->getAnalysisToUpdate<DominanceFrontier>(); |
| 84 | } |
| 85 | |
| 86 | SmallVector<BasicBlock *, 16> NewBlocks; |
Devang Patel | 4bc2a0b | 2007-08-10 17:59:47 +0000 | [diff] [blame] | 87 | |
Devang Patel | 4f5d78e | 2007-08-14 23:59:17 +0000 | [diff] [blame] | 88 | // Populate loop nest. |
| 89 | SmallVector<Loop *, 8> LoopNest; |
| 90 | LoopNest.push_back(OrigL); |
| 91 | |
| 92 | |
| 93 | Loop *NewParentLoop = NULL; |
| 94 | while (!LoopNest.empty()) { |
| 95 | Loop *L = LoopNest.back(); |
Devang Patel | 4bc2a0b | 2007-08-10 17:59:47 +0000 | [diff] [blame] | 96 | LoopNest.pop_back(); |
Devang Patel | 4f5d78e | 2007-08-14 23:59:17 +0000 | [diff] [blame] | 97 | Loop *NewLoop = new Loop(); |
| 98 | |
| 99 | if (!NewParentLoop) |
| 100 | NewParentLoop = NewLoop; |
| 101 | |
Devang Patel | 4bc2a0b | 2007-08-10 17:59:47 +0000 | [diff] [blame] | 102 | LPM->insertLoop(NewLoop, L->getParentLoop()); |
| 103 | |
| 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); |
Owen Anderson | d735ee8 | 2007-11-27 03:43:35 +0000 | [diff] [blame] | 112 | NewLoop->addBasicBlockToLoop(NewBB, LI->getBase()); |
Devang Patel | 4bc2a0b | 2007-08-10 17:59:47 +0000 | [diff] [blame] | 113 | NewBlocks.push_back(NewBB); |
| 114 | } |
| 115 | |
| 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); |
| 122 | } |
| 123 | |
Devang Patel | 4f5d78e | 2007-08-14 23:59:17 +0000 | [diff] [blame] | 124 | // Process sub loops |
| 125 | for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) |
| 126 | LoopNest.push_back(*I); |
Devang Patel | 4bc2a0b | 2007-08-10 17:59:47 +0000 | [diff] [blame] | 127 | } |
| 128 | |
| 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); |
| 142 | } |
| 143 | } |
| 144 | } |
| 145 | |
| 146 | BasicBlock *Latch = OrigL->getLoopLatch(); |
| 147 | Function *F = Latch->getParent(); |
Devang Patel | d24e599 | 2007-09-04 20:46:35 +0000 | [diff] [blame] | 148 | F->getBasicBlockList().insert(OrigL->getHeader(), |
| 149 | NewBlocks.begin(), NewBlocks.end()); |
| 150 | |
Devang Patel | 4bc2a0b | 2007-08-10 17:59:47 +0000 | [diff] [blame] | 151 | |
Devang Patel | 4f5d78e | 2007-08-14 23:59:17 +0000 | [diff] [blame] | 152 | return NewParentLoop; |
Devang Patel | 4bc2a0b | 2007-08-10 17:59:47 +0000 | [diff] [blame] | 153 | } |