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 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                                ValueToValueMapTy &VMap,
  26                                DominatorTree *DT,
  27                                DominanceFrontier *DF) {
  28
  29   assert (DT && "DominatorTree is not available");
  30   ValueToValueMapTy::iterator BI = VMap.find(BB);
  31   assert (BI != VMap.end() && "BasicBlock clone is missing");
  32   BasicBlock *NewBB = cast<BasicBlock>(BI->second);
  33
  34   // NewBB already got dominator info.
  35   if (DT->getNode(NewBB))
  36     return;
  37
  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();
  42
  43   // NewBB's dominator is either BB's dominator or BB's dominator's clone.
  44   BasicBlock *NewBBDom = BBDom;
  45   ValueToValueMapTy::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);
  50   }
  51   DT->addNewBlock(NewBB, NewBBDom);
  52
  53   // Copy cloned dominance frontiner set
  54   if (DF) {
  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();
  60              I != E; ++I) {
  61           BasicBlock *DB = *I;
  62           ValueToValueMapTy::iterator IDM = VMap.find(DB);
  63           if (IDM != VMap.end())
  64             NewDFSet.insert(cast<BasicBlock>(IDM->second));
  65           else
  66             NewDFSet.insert(DB);
  67         }
  68     }
  69     DF->addBasicBlock(NewBB, NewDFSet);
  70   }
  71 }
  72
  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                       ValueToValueMapTy &VMap, Pass *P) {
  77
  78   DominatorTree *DT = NULL;
  79   DominanceFrontier *DF = NULL;
  80   if (P) {
  81     DT = P->getAnalysisIfAvailable<DominatorTree>();
  82     DF = P->getAnalysisIfAvailable<DominanceFrontier>();
  83   }
  84
  85   SmallVector<BasicBlock *, 16> NewBlocks;
  86
  87   // Populate loop nest.
  88   SmallVector<Loop *, 8> LoopNest;
  89   LoopNest.push_back(OrigL);
  90
  91
  92   Loop *NewParentLoop = NULL;
  93   do {
  94     Loop *L = LoopNest.pop_back_val();
  95     Loop *NewLoop = new Loop();
  96
  97     if (!NewParentLoop)
  98       NewParentLoop = NewLoop;
  99
 100     LPM->insertLoop(NewLoop, L->getParentLoop());
 101
 102     // Clone Basic Blocks.
 103     for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
 104          I != E; ++I) {
 105       BasicBlock *BB = *I;
 106       BasicBlock *NewBB = CloneBasicBlock(BB, VMap, ".clone");
 107       VMap[BB] = NewBB;
 108       if (P)
 109         LPM->cloneBasicBlockSimpleAnalysis(BB, NewBB, L);
 110       NewLoop->addBasicBlockToLoop(NewBB, LI->getBase());
 111       NewBlocks.push_back(NewBB);
 112     }
 113
 114     // Clone dominator info.
 115     if (DT)
 116       for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
 117            I != E; ++I) {
 118         BasicBlock *BB = *I;
 119         CloneDominatorInfo(BB, VMap, DT, DF);
 120       }
 121
 122     // Process sub loops
 123     for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
 124       LoopNest.push_back(*I);
 125   } while (!LoopNest.empty());
 126
 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();
 132         BI != BE; ++BI) {
 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         ValueToValueMapTy::iterator OpItr = VMap.find(Op);
 138         if (OpItr != VMap.end())
 139           Insn->setOperand(index, OpItr->second);
 140       }
 141     }
 142   }
 143
 144   BasicBlock *Latch = OrigL->getLoopLatch();
 145   Function *F = Latch->getParent();
 146   F->getBasicBlockList().insert(OrigL->getHeader(),
 147                                 NewBlocks.begin(), NewBlocks.end());
 148
 149
 150   return NewParentLoop;
 151 }