LLVM API Documentation
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