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 #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;
  87
  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();
  96     LoopNest.pop_back();
  97     Loop *NewLoop = new Loop();
  98
  99     if (!NewParentLoop)
 100       NewParentLoop = NewLoop;
 101
 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);
 112       NewLoop->addBasicBlockToLoop(NewBB, LI->getBase());
 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
 124     // Process sub loops
 125     for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
 126       LoopNest.push_back(*I);
 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();
 148   F->getBasicBlockList().insert(OrigL->getHeader(),
 149                                 NewBlocks.begin(), NewBlocks.end());
 150
 151
 152   return NewParentLoop;
 153 }