LLVM API Documentation

CloneTrace.cpp

Go to the documentation of this file.
00001 //===- CloneTrace.cpp - Clone a trace -------------------------------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements the CloneTrace interface, which is used when writing
00011 // runtime optimizations. It takes a vector of basic blocks clones the basic
00012 // blocks, removes internal phi nodes, adds it to the same function as the
00013 // original (although there is no jump to it) and returns the new vector of
00014 // basic blocks.
00015 //
00016 //===----------------------------------------------------------------------===//
00017 
00018 #include "llvm/Analysis/Trace.h"
00019 #include "llvm/Transforms/Utils/Cloning.h"
00020 #include "llvm/Instructions.h"
00021 #include "llvm/Function.h"
00022 #include "ValueMapper.h"
00023 using namespace llvm;
00024 
00025 //Clones the trace (a vector of basic blocks)
00026 std::vector<BasicBlock *>
00027 llvm::CloneTrace(const std::vector<BasicBlock*> &origTrace) {
00028   std::vector<BasicBlock *> clonedTrace;
00029   std::map<const Value*, Value*> ValueMap;
00030 
00031   //First, loop over all the Basic Blocks in the trace and copy
00032   //them using CloneBasicBlock. Also fix the phi nodes during
00033   //this loop. To fix the phi nodes, we delete incoming branches
00034   //that are not in the trace.
00035   for(std::vector<BasicBlock *>::const_iterator T = origTrace.begin(),
00036     End = origTrace.end(); T != End; ++T) {
00037 
00038     //Clone Basic Block
00039     BasicBlock *clonedBlock =
00040       CloneBasicBlock(*T, ValueMap, ".tr", (*T)->getParent());
00041 
00042     //Add it to our new trace
00043     clonedTrace.push_back(clonedBlock);
00044 
00045     //Add this new mapping to our Value Map
00046     ValueMap[*T] = clonedBlock;
00047 
00048     //Loop over the phi instructions and delete operands
00049     //that are from blocks not in the trace
00050     //only do this if we are NOT the first block
00051     if(T != origTrace.begin()) {
00052       for (BasicBlock::iterator I = clonedBlock->begin();
00053            isa<PHINode>(I); ++I) {
00054         PHINode *PN = cast<PHINode>(I);
00055         //get incoming value for the previous BB
00056         Value *V = PN->getIncomingValueForBlock(*(T-1));
00057         assert(V && "No incoming value from a BasicBlock in our trace!");
00058 
00059         //remap our phi node to point to incoming value
00060         ValueMap[*&I] = V;
00061 
00062         //remove phi node
00063         clonedBlock->getInstList().erase(PN);
00064       }
00065     }
00066   }
00067 
00068   //Second loop to do the remapping
00069   for(std::vector<BasicBlock *>::const_iterator BB = clonedTrace.begin(),
00070     BE = clonedTrace.end(); BB != BE; ++BB) {
00071     for(BasicBlock::iterator I = (*BB)->begin(); I != (*BB)->end(); ++I) {
00072 
00073       //Loop over all the operands of the instruction
00074       for(unsigned op=0, E = I->getNumOperands(); op != E; ++op) {
00075     const Value *Op = I->getOperand(op);
00076 
00077     //Get it out of the value map
00078     Value *V = ValueMap[Op];
00079 
00080     //If not in the value map, then its outside our trace so ignore
00081     if(V != 0)
00082       I->setOperand(op,V);
00083       }
00084     }
00085   }
00086 
00087   //return new vector of basic blocks
00088   return clonedTrace;
00089 }
00090 
00091 /// CloneTraceInto - Clone T into NewFunc. Original<->clone mapping is
00092 /// saved in ValueMap.
00093 ///
00094 void llvm::CloneTraceInto(Function *NewFunc, Trace &T,
00095                           std::map<const Value*, Value*> &ValueMap,
00096                           const char *NameSuffix) {
00097   assert(NameSuffix && "NameSuffix cannot be null!");
00098 
00099   // Loop over all of the basic blocks in the trace, cloning them as
00100   // appropriate.
00101   //
00102   for (Trace::const_iterator BI = T.begin(), BE = T.end(); BI != BE; ++BI) {
00103     const BasicBlock *BB = *BI;
00104 
00105     // Create a new basic block and copy instructions into it!
00106     BasicBlock *CBB = CloneBasicBlock(BB, ValueMap, NameSuffix, NewFunc);
00107     ValueMap[BB] = CBB;                       // Add basic block mapping.
00108   }
00109 
00110   // Loop over all of the instructions in the new function, fixing up operand
00111   // references as we go.  This uses ValueMap to do all the hard work.
00112   //
00113   for (Function::iterator BB =
00114          cast<BasicBlock>(ValueMap[T.getEntryBasicBlock()]),
00115          BE = NewFunc->end(); BB != BE; ++BB)
00116     // Loop over all instructions, fixing each one as we find it...
00117     for (BasicBlock::iterator II = BB->begin(); II != BB->end(); ++II)
00118       RemapInstruction(II, ValueMap);
00119 }
00120