lib/Transforms/Utils/CloneLoop.cpp

//===- CloneLoop.cpp - Clone loop nest ------------------------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file was developed by Devang Patel and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements the CloneLoop interface which makes a copy of a loop.
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/BasicBlock.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/ADT/DenseMap.h"


using namespace llvm;

/// CloneDominatorInfo - Clone basicblock's dominator tree and, if available,
/// dominance info. It is expected that basic block is already cloned.
static void CloneDominatorInfo(BasicBlock *BB, 
                               DenseMap<const Value *, Value *> &ValueMap,
                               DominatorTree *DT,
                               DominanceFrontier *DF) {

  assert (DT && "DominatorTree is not available");
  DenseMap<const Value *, Value*>::iterator BI = ValueMap.find(BB);
  assert (BI != ValueMap.end() && "BasicBlock clone is missing");
  BasicBlock *NewBB = cast<BasicBlock>(BI->second);

  // NewBB already got dominator info.
  if (DT->getNode(NewBB))
    return;

  assert (DT->getNode(BB) && "BasicBlock does not have dominator info");
  // Entry block is not expected here. Infinite loops are not to cloned.
  assert (DT->getNode(BB)->getIDom() && "BasicBlock does not have immediate dominator");
  BasicBlock *BBDom = DT->getNode(BB)->getIDom()->getBlock();

  // NewBB's dominator is either BB's dominator or BB's dominator's clone.
  BasicBlock *NewBBDom = BBDom;
  DenseMap<const Value *, Value*>::iterator BBDomI = ValueMap.find(BBDom);
  if (BBDomI != ValueMap.end()) {
    NewBBDom = cast<BasicBlock>(BBDomI->second);
    if (!DT->getNode(NewBBDom))
      CloneDominatorInfo(BBDom, ValueMap, DT, DF);
  }
  DT->addNewBlock(NewBB, NewBBDom);

  // Copy cloned dominance frontiner set
  if (DF) {
    DominanceFrontier::DomSetType NewDFSet;
    DominanceFrontier::iterator DFI = DF->find(BB);
    if ( DFI != DF->end()) {
      DominanceFrontier::DomSetType S = DFI->second;
        for (DominanceFrontier::DomSetType::iterator I = S.begin(), E = S.end();
             I != E; ++I) {
          BasicBlock *DB = *I;
          DenseMap<const Value*, Value*>::iterator IDM = ValueMap.find(DB);
          if (IDM != ValueMap.end())
            NewDFSet.insert(cast<BasicBlock>(IDM->second));
          else
            NewDFSet.insert(DB);
        }
    }
    DF->addBasicBlock(NewBB, NewDFSet);
  }
}

/// CloneLoop - Clone Loop. Clone dominator info. Populate ValueMap
/// using old blocks to new blocks mapping.
Loop *llvm::CloneLoop(Loop *OrigL, LPPassManager  *LPM, LoopInfo *LI,
                      DenseMap<const Value *, Value *> &ValueMap, Pass *P) {
  
  DominatorTree *DT = NULL;
  DominanceFrontier *DF = NULL;
  if (P) {
    DT = P->getAnalysisToUpdate<DominatorTree>();
    DF = P->getAnalysisToUpdate<DominanceFrontier>();
  }

  SmallVector<BasicBlock *, 16> NewBlocks;
  SmallVector<std::pair<Loop *, Loop::iterator>, 8> LoopNest;
  LoopNest.push_back(std::make_pair(OrigL, OrigL->begin()));
  
  Loop *NewLoop = NULL;
  while (!LoopNest.empty()) {
    Loop *L = LoopNest.back().first;
    Loop::iterator SubLoop = LoopNest.back().second;
    
    // Handle sub loops.
    if (SubLoop != L->end()) {
      Loop *SL  = *SubLoop;
      LoopNest.push_back(std::make_pair(SL, SL->begin()));
    } 

    LoopNest.pop_back();
    NewLoop = new Loop();
    LPM->insertLoop(NewLoop, L->getParentLoop());

    // Clone Basic Blocks.
    for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
         I != E; ++I) {
      BasicBlock *BB = *I;
      BasicBlock *NewBB = CloneBasicBlock(BB, ValueMap, ".clone");
      ValueMap[BB] = NewBB;
      if (P)
        LPM->cloneBasicBlockSimpleAnalysis(BB, NewBB, L);
      NewLoop->addBasicBlockToLoop(NewBB, *LI);
      NewBlocks.push_back(NewBB);
    }

    // Clone dominator info.
    if (DT)
      for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
           I != E; ++I) {
        BasicBlock *BB = *I;
        CloneDominatorInfo(BB, ValueMap, DT, DF);
      }

  }

  // Remap instructions to reference operands from ValueMap.
  for(SmallVector<BasicBlock *, 16>::iterator NBItr = NewBlocks.begin(), 
        NBE = NewBlocks.end();  NBItr != NBE; ++NBItr) {
    BasicBlock *NB = *NBItr;
    for(BasicBlock::iterator BI = NB->begin(), BE = NB->end(); 
        BI != BE; ++BI) {
      Instruction *Insn = BI;
      for (unsigned index = 0, num_ops = Insn->getNumOperands(); 
           index != num_ops; ++index) {
        Value *Op = Insn->getOperand(index);
        DenseMap<const Value *, Value *>::iterator OpItr = ValueMap.find(Op);
        if (OpItr != ValueMap.end())
          Insn->setOperand(index, OpItr->second);
      }
    }
  }

  BasicBlock *Latch = OrigL->getLoopLatch();
  Function *F = Latch->getParent();
  F->getBasicBlockList().insert(Latch, NewBlocks.begin(), NewBlocks.end());

  return NewLoop;
}