lib/Transforms/Utils/CloneLoop.cpp

   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.
  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
  19
  20 using namespace llvm;
  21
  22 /// CloneDominatorInfo - Clone a basic block's dominator tree. It is expected
  23 /// that the basic block is already cloned.
  24 static void CloneDominatorInfo(BasicBlock *BB,
  25                                ValueToValueMapTy &VMap,
  26                                DominatorTree *DT) {
  27
  28   assert (DT && "DominatorTree is not available");
  29   ValueToValueMapTy::iterator BI = VMap.find(BB);
  30   assert (BI != VMap.end() && "BasicBlock clone is missing");
  31   BasicBlock *NewBB = cast<BasicBlock>(BI->second);
  32
  33   // NewBB already got dominator info.
  34   if (DT->getNode(NewBB))
  35     return;
  36
  37   assert (DT->getNode(BB) && "BasicBlock does not have dominator info");
  38   // Entry block is not expected here. Infinite loops are not to cloned.
  39   assert (DT->getNode(BB)->getIDom() && "BasicBlock does not have immediate dominator");
  40   BasicBlock *BBDom = DT->getNode(BB)->getIDom()->getBlock();
  41
  42   // NewBB's dominator is either BB's dominator or BB's dominator's clone.
  43   BasicBlock *NewBBDom = BBDom;
  44   ValueToValueMapTy::iterator BBDomI = VMap.find(BBDom);
  45   if (BBDomI != VMap.end()) {
  46     NewBBDom = cast<BasicBlock>(BBDomI->second);
  47     if (!DT->getNode(NewBBDom))
  48       CloneDominatorInfo(BBDom, VMap, DT);
  49   }
  50   DT->addNewBlock(NewBB, NewBBDom);
  51 }
  52
  53 /// CloneLoop - Clone Loop. Clone dominator info. Populate VMap
  54 /// using old blocks to new blocks mapping.
  55 Loop *llvm::CloneLoop(Loop *OrigL, LPPassManager  *LPM, LoopInfo *LI,
  56                       ValueToValueMapTy &VMap, Pass *P) {
  57
  58   DominatorTree *DT = NULL;
  59   if (P)
  60     DT = P->getAnalysisIfAvailable<DominatorTree>();
  61
  62   SmallVector<BasicBlock *, 16> NewBlocks;
  63
  64   // Populate loop nest.
  65   SmallVector<Loop *, 8> LoopNest;
  66   LoopNest.push_back(OrigL);
  67
  68
  69   Loop *NewParentLoop = NULL;
  70   do {
  71     Loop *L = LoopNest.pop_back_val();
  72     Loop *NewLoop = new Loop();
  73
  74     if (!NewParentLoop)
  75       NewParentLoop = NewLoop;
  76
  77     LPM->insertLoop(NewLoop, L->getParentLoop());
  78
  79     // Clone Basic Blocks.
  80     for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
  81          I != E; ++I) {
  82       BasicBlock *BB = *I;
  83       BasicBlock *NewBB = CloneBasicBlock(BB, VMap, ".clone");
  84       VMap[BB] = NewBB;
  85       if (P)
  86         LPM->cloneBasicBlockSimpleAnalysis(BB, NewBB, L);
  87       NewLoop->addBasicBlockToLoop(NewBB, LI->getBase());
  88       NewBlocks.push_back(NewBB);
  89     }
  90
  91     // Clone dominator info.
  92     if (DT)
  93       for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
  94            I != E; ++I) {
  95         BasicBlock *BB = *I;
  96         CloneDominatorInfo(BB, VMap, DT);
  97       }
  98
  99     // Process sub loops
 100     for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
 101       LoopNest.push_back(*I);
 102   } while (!LoopNest.empty());
 103
 104   // Remap instructions to reference operands from VMap.
 105   for(SmallVector<BasicBlock *, 16>::iterator NBItr = NewBlocks.begin(),
 106         NBE = NewBlocks.end();  NBItr != NBE; ++NBItr) {
 107     BasicBlock *NB = *NBItr;
 108     for(BasicBlock::iterator BI = NB->begin(), BE = NB->end();
 109         BI != BE; ++BI) {
 110       Instruction *Insn = BI;
 111       for (unsigned index = 0, num_ops = Insn->getNumOperands();
 112            index != num_ops; ++index) {
 113         Value *Op = Insn->getOperand(index);
 114         ValueToValueMapTy::iterator OpItr = VMap.find(Op);
 115         if (OpItr != VMap.end())
 116           Insn->setOperand(index, OpItr->second);
 117       }
 118     }
 119   }
 120
 121   BasicBlock *Latch = OrigL->getLoopLatch();
 122   Function *F = Latch->getParent();
 123   F->getBasicBlockList().insert(OrigL->getHeader(),
 124                                 NewBlocks.begin(), NewBlocks.end());
 125
 126
 127   return NewParentLoop;
 128 }