1 //===- CloneTrace.cpp - Clone a trace ---------===//
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.
8 //===----------------------------------------------------------------------===//
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"
18 //Clones the trace (a vector of basic blocks)
19 std::vector<BasicBlock *> CloneTrace(std::vector<BasicBlock*> &origTrace) {
21 std::vector<BasicBlock *> clonedTrace;
22 std::map<const Value*, Value*> ValueMap;
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) {
32 BasicBlock *clonedBlock = CloneBasicBlock(*T, ValueMap);
34 //Add it to our new trace
35 clonedTrace.push_back(clonedBlock);
37 //Add this new mapping to our Value Map
38 ValueMap[*T] = clonedBlock;
40 //Add this cloned BB to the old BB's function
41 (*T)->getParent()->getBasicBlockList().push_back(clonedBlock);
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!");
53 //remap our phi node to point to incoming value
57 clonedBlock->getInstList().erase(PN);
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) {
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);
71 //Get it out of the value map
72 Value *V = ValueMap[Op];
74 //If not in the value map, then its outside our trace so ignore
81 //return new vector of basic blocks