lib/Transforms/Utils/CloneTrace.cpp

   1 //===- CloneTrace.cpp - Clone a trace ---------===//
   2 //
   3 // This file implements the CloneTrace interface, which is used
   4 // when writing runtime optimizations. It takes a vector of basic blocks
   5 // removes internal phi nodes, clones the basic blocks, and returns the new
   6 // vector of basic blocks.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include "llvm/Instruction.h"
  11 #include "llvm/BasicBlock.h"
  12 #include "llvm/iPHINode.h"
  13 #include "llvm/Function.h"
  14 #include "llvm/Transforms/Utils/Cloning.h"
  15 #include <map>
  16
  17
  18 //Clones the trace (a vector of basic blocks)
  19 std::vector<BasicBlock *> CloneTrace(std::vector<BasicBlock*> &origTrace) {
  20
  21   std::vector<BasicBlock *> clonedTrace;
  22   std::map<const Value*, Value*> ValueMap;
  23
  24   //First, loop over all the Basic Blocks in the trace and copy
  25   //them using CloneBasicBlock. Also fix the phi nodes during
  26   //this loop. To fix the phi nodes, we delete incoming branches
  27   //that are not in the trace.
  28   for(std::vector<BasicBlock *>::const_iterator T = origTrace.begin(),
  29         End = origTrace.end(); T != End; ++T) {
  30
  31     //Clone Basic Block
  32     BasicBlock *clonedBlock = CloneBasicBlock(*T, ValueMap);
  33
  34     //Add it to our new trace
  35     clonedTrace.push_back(clonedBlock);
  36
  37     //Add this new mapping to our Value Map
  38     ValueMap[*T] = clonedBlock;
  39
  40     //Add this cloned BB to the old BB's function
  41     (*T)->getParent()->getBasicBlockList().push_back(clonedBlock);
  42
  43     //Loop over the phi instructions and delete operands
  44     //that are from blocks not in the trace
  45     //only do this if we are NOT the first block
  46     if(T != origTrace.begin()) {
  47       for (BasicBlock::iterator I = clonedBlock->begin();
  48            PHINode *PN = dyn_cast<PHINode>(I); ++I) {
  49         //get incoming value for the previous BB
  50         Value *V = PN->getIncomingValueForBlock(*(T-1));
  51         assert(V && "No incoming value from a BasicBlock in our trace!");
  52
  53         //remap our phi node to point to incoming value
  54         ValueMap[*&I] = V;
  55
  56         //remove phi node
  57         clonedBlock->getInstList().erase(PN);
  58       }
  59     }
  60   }
  61
  62   //Second loop to do the remapping
  63   for(std::vector<BasicBlock *>::const_iterator BB = clonedTrace.begin(),
  64         BE = clonedTrace.end(); BB != BE; ++BB) {
  65     for(BasicBlock::iterator I = (*BB)->begin(); I != (*BB)->end(); ++I) {
  66
  67       //Loop over all the operands of the instruction
  68       for(unsigned op=0, E = I->getNumOperands(); op != E; ++op) {
  69         const Value *Op = I->getOperand(op);
  70
  71         //Get it out of the value map
  72         Value *V = ValueMap[Op];
  73
  74         //If not in the value map, then its outside our trace so ignore
  75         if(V != 0)
  76           I->setOperand(op,V);
  77       }
  78     }
  79   }
  80
  81   //return new vector of basic blocks
  82   return clonedTrace;
  83 }