lib/Transforms/Utils/CloneTrace.cpp

   1 //===- CloneTrace.cpp - Clone a trace -------------------------------------===//
   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 CloneTrace interface, which is used when writing
  11 // runtime optimizations. It takes a vector of basic blocks clones the basic
  12 // blocks, removes internal phi nodes, adds it to the same function as the
  13 // original (although there is no jump to it) and returns the new vector of
  14 // basic blocks.
  15 //
  16 //===----------------------------------------------------------------------===//
  17
  18 #include "llvm/Analysis/Trace.h"
  19 #include "llvm/Transforms/Utils/Cloning.h"
  20 #include "llvm/Instructions.h"
  21 #include "llvm/Function.h"
  22 #include "llvm/Transforms/Utils/ValueMapper.h"
  23 using namespace llvm;
  24
  25 //Clones the trace (a vector of basic blocks)
  26 std::vector<BasicBlock *>
  27 llvm::CloneTrace(const std::vector<BasicBlock*> &origTrace) {
  28   std::vector<BasicBlock *> clonedTrace;
  29   DenseMap<const Value*, Value*> ValueMap;
  30
  31   //First, loop over all the Basic Blocks in the trace and copy
  32   //them using CloneBasicBlock. Also fix the phi nodes during
  33   //this loop. To fix the phi nodes, we delete incoming branches
  34   //that are not in the trace.
  35   for (std::vector<BasicBlock *>::const_iterator T = origTrace.begin(),
  36     End = origTrace.end(); T != End; ++T) {
  37
  38     //Clone Basic Block
  39     BasicBlock *clonedBlock =
  40       CloneBasicBlock(*T, ValueMap, ".tr", (*T)->getParent());
  41
  42     //Add it to our new trace
  43     clonedTrace.push_back(clonedBlock);
  44
  45     //Add this new mapping to our Value Map
  46     ValueMap[*T] = clonedBlock;
  47
  48     //Loop over the phi instructions and delete operands
  49     //that are from blocks not in the trace
  50     //only do this if we are NOT the first block
  51     if (T != origTrace.begin()) {
  52       for (BasicBlock::iterator I = clonedBlock->begin();
  53            isa<PHINode>(I); ++I) {
  54         PHINode *PN = cast<PHINode>(I);
  55         //get incoming value for the previous BB
  56         Value *V = PN->getIncomingValueForBlock(*(T-1));
  57         assert(V && "No incoming value from a BasicBlock in our trace!");
  58
  59         //remap our phi node to point to incoming value
  60         ValueMap[*&I] = V;
  61
  62         //remove phi node
  63         clonedBlock->getInstList().erase(PN);
  64       }
  65     }
  66   }
  67
  68   //Second loop to do the remapping
  69   for (std::vector<BasicBlock *>::const_iterator BB = clonedTrace.begin(),
  70     BE = clonedTrace.end(); BB != BE; ++BB) {
  71
  72     //Remap the unwind destination
  73     if (BasicBlock *UnwindDest = (*BB)->getUnwindDest())
  74       (*BB)->setUnwindDest(cast<BasicBlock>(ValueMap[UnwindDest]));
  75
  76     for (BasicBlock::iterator I = (*BB)->begin(); I != (*BB)->end(); ++I) {
  77       //Loop over all the operands of the instruction
  78       for (unsigned op=0, E = I->getNumOperands(); op != E; ++op) {
  79         const Value *Op = I->getOperand(op);
  80
  81         //Get it out of the value map
  82         Value *V = ValueMap[Op];
  83
  84         //If not in the value map, then its outside our trace so ignore
  85         if (V != 0)
  86           I->setOperand(op,V);
  87       }
  88     }
  89   }
  90
  91   //return new vector of basic blocks
  92   return clonedTrace;
  93 }
  94
  95 /// CloneTraceInto - Clone T into NewFunc. Original<->clone mapping is
  96 /// saved in ValueMap.
  97 ///
  98 void llvm::CloneTraceInto(Function *NewFunc, Trace &T,
  99                           DenseMap<const Value*, Value*> &ValueMap,
 100                           const char *NameSuffix) {
 101   assert(NameSuffix && "NameSuffix cannot be null!");
 102
 103   // Loop over all of the basic blocks in the trace, cloning them as
 104   // appropriate.
 105   //
 106   for (Trace::const_iterator BI = T.begin(), BE = T.end(); BI != BE; ++BI) {
 107     const BasicBlock *BB = *BI;
 108
 109     // Create a new basic block and copy instructions into it!
 110     BasicBlock *CBB = CloneBasicBlock(BB, ValueMap, NameSuffix, NewFunc);
 111     ValueMap[BB] = CBB;                       // Add basic block mapping.
 112   }
 113
 114   // Loop over all of the instructions in the new function, fixing up operand
 115   // references as we go.  This uses ValueMap to do all the hard work.
 116   //
 117   for (Function::iterator BB =
 118          cast<BasicBlock>(ValueMap[T.getEntryBasicBlock()]),
 119          BE = NewFunc->end(); BB != BE; ++BB)
 120     // Loop over all instructions, fixing each one as we find it...
 121     for (BasicBlock::iterator II = BB->begin(); II != BB->end(); ++II)
 122       RemapInstruction(II, ValueMap);
 123 }
 124