lib/Transforms/Utils/CloneTrace.cpp

   1 //===- CloneTrace.cpp - Clone a trace -------------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source 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/Transforms/Utils/Cloning.h"
  19 #include "llvm/iPHINode.h"
  20 #include "llvm/Function.h"
  21 using namespace llvm;
  22
  23 //Clones the trace (a vector of basic blocks)
  24 std::vector<BasicBlock *>
  25 llvm::CloneTrace(const std::vector<BasicBlock*> &origTrace) {
  26   std::vector<BasicBlock *> clonedTrace;
  27   std::map<const Value*, Value*> ValueMap;
  28
  29   //First, loop over all the Basic Blocks in the trace and copy
  30   //them using CloneBasicBlock. Also fix the phi nodes during
  31   //this loop. To fix the phi nodes, we delete incoming branches
  32   //that are not in the trace.
  33   for(std::vector<BasicBlock *>::const_iterator T = origTrace.begin(),
  34         End = origTrace.end(); T != End; ++T) {
  35
  36     //Clone Basic Block
  37     BasicBlock *clonedBlock =
  38       CloneBasicBlock(*T, ValueMap, ".tr", (*T)->getParent());
  39
  40     //Add it to our new trace
  41     clonedTrace.push_back(clonedBlock);
  42
  43     //Add this new mapping to our Value Map
  44     ValueMap[*T] = clonedBlock;
  45
  46     //Loop over the phi instructions and delete operands
  47     //that are from blocks not in the trace
  48     //only do this if we are NOT the first block
  49     if(T != origTrace.begin()) {
  50       for (BasicBlock::iterator I = clonedBlock->begin();
  51            PHINode *PN = dyn_cast<PHINode>(I); ++I) {
  52         //get incoming value for the previous BB
  53         Value *V = PN->getIncomingValueForBlock(*(T-1));
  54         assert(V && "No incoming value from a BasicBlock in our trace!");
  55
  56         //remap our phi node to point to incoming value
  57         ValueMap[*&I] = V;
  58
  59         //remove phi node
  60         clonedBlock->getInstList().erase(PN);
  61       }
  62     }
  63   }
  64
  65   //Second loop to do the remapping
  66   for(std::vector<BasicBlock *>::const_iterator BB = clonedTrace.begin(),
  67         BE = clonedTrace.end(); BB != BE; ++BB) {
  68     for(BasicBlock::iterator I = (*BB)->begin(); I != (*BB)->end(); ++I) {
  69
  70       //Loop over all the operands of the instruction
  71       for(unsigned op=0, E = I->getNumOperands(); op != E; ++op) {
  72         const Value *Op = I->getOperand(op);
  73
  74         //Get it out of the value map
  75         Value *V = ValueMap[Op];
  76
  77         //If not in the value map, then its outside our trace so ignore
  78         if(V != 0)
  79           I->setOperand(op,V);
  80       }
  81     }
  82   }
  83
  84   //return new vector of basic blocks
  85   return clonedTrace;
  86 }