Tanya Lattner | 658c5bc | 2003-05-31 20:01:37 +0000 | [diff] [blame] | 1 | //===- CloneTrace.cpp - Clone a trace -------------------------------------===// |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 2 | // |
John Criswell | b576c94 | 2003-10-20 19:43:21 +0000 | [diff] [blame] | 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. |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 7 | // |
John Criswell | b576c94 | 2003-10-20 19:43:21 +0000 | [diff] [blame] | 8 | //===----------------------------------------------------------------------===// |
Tanya Lattner | 6074d2f | 2003-05-30 15:50:18 +0000 | [diff] [blame] | 9 | // |
Chris Lattner | 23b4c68 | 2004-02-04 01:19:43 +0000 | [diff] [blame] | 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. |
Tanya Lattner | 6074d2f | 2003-05-30 15:50:18 +0000 | [diff] [blame] | 15 | // |
| 16 | //===----------------------------------------------------------------------===// |
| 17 | |
Brian Gaeke | c58a7f4 | 2004-05-19 09:08:14 +0000 | [diff] [blame] | 18 | #include "llvm/Analysis/Trace.h" |
Tanya Lattner | 658c5bc | 2003-05-31 20:01:37 +0000 | [diff] [blame] | 19 | #include "llvm/Transforms/Utils/Cloning.h" |
Misha Brukman | 47b14a4 | 2004-07-29 17:30:56 +0000 | [diff] [blame] | 20 | #include "llvm/Instructions.h" |
Tanya Lattner | 6074d2f | 2003-05-30 15:50:18 +0000 | [diff] [blame] | 21 | #include "llvm/Function.h" |
Brian Gaeke | c58a7f4 | 2004-05-19 09:08:14 +0000 | [diff] [blame] | 22 | #include "ValueMapper.h" |
Chris Lattner | f7703df | 2004-01-09 06:12:26 +0000 | [diff] [blame] | 23 | using namespace llvm; |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 24 | |
Tanya Lattner | 6074d2f | 2003-05-30 15:50:18 +0000 | [diff] [blame] | 25 | //Clones the trace (a vector of basic blocks) |
Chris Lattner | f7703df | 2004-01-09 06:12:26 +0000 | [diff] [blame] | 26 | std::vector<BasicBlock *> |
| 27 | llvm::CloneTrace(const std::vector<BasicBlock*> &origTrace) { |
Tanya Lattner | 6074d2f | 2003-05-30 15:50:18 +0000 | [diff] [blame] | 28 | std::vector<BasicBlock *> clonedTrace; |
| 29 | std::map<const Value*, Value*> ValueMap; |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 30 | |
Tanya Lattner | 6074d2f | 2003-05-30 15:50:18 +0000 | [diff] [blame] | 31 | //First, loop over all the Basic Blocks in the trace and copy |
| 32 | //them using CloneBasicBlock. Also fix the phi nodes during |
| 33 | //this loop. To fix the phi nodes, we delete incoming branches |
| 34 | //that are not in the trace. |
| 35 | for(std::vector<BasicBlock *>::const_iterator T = origTrace.begin(), |
Jeff Cohen | 9d80930 | 2005-04-23 21:38:35 +0000 | [diff] [blame^] | 36 | End = origTrace.end(); T != End; ++T) { |
Tanya Lattner | 6074d2f | 2003-05-30 15:50:18 +0000 | [diff] [blame] | 37 | |
| 38 | //Clone Basic Block |
Chris Lattner | 23b4c68 | 2004-02-04 01:19:43 +0000 | [diff] [blame] | 39 | BasicBlock *clonedBlock = |
| 40 | CloneBasicBlock(*T, ValueMap, ".tr", (*T)->getParent()); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 41 | |
Tanya Lattner | 6074d2f | 2003-05-30 15:50:18 +0000 | [diff] [blame] | 42 | //Add it to our new trace |
| 43 | clonedTrace.push_back(clonedBlock); |
| 44 | |
| 45 | //Add this new mapping to our Value Map |
| 46 | ValueMap[*T] = clonedBlock; |
| 47 | |
Tanya Lattner | 6074d2f | 2003-05-30 15:50:18 +0000 | [diff] [blame] | 48 | //Loop over the phi instructions and delete operands |
| 49 | //that are from blocks not in the trace |
| 50 | //only do this if we are NOT the first block |
| 51 | if(T != origTrace.begin()) { |
| 52 | for (BasicBlock::iterator I = clonedBlock->begin(); |
Reid Spencer | 2da5c3d | 2004-09-15 17:06:42 +0000 | [diff] [blame] | 53 | isa<PHINode>(I); ++I) { |
| 54 | PHINode *PN = cast<PHINode>(I); |
| 55 | //get incoming value for the previous BB |
| 56 | Value *V = PN->getIncomingValueForBlock(*(T-1)); |
| 57 | assert(V && "No incoming value from a BasicBlock in our trace!"); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 58 | |
Reid Spencer | 2da5c3d | 2004-09-15 17:06:42 +0000 | [diff] [blame] | 59 | //remap our phi node to point to incoming value |
| 60 | ValueMap[*&I] = V; |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 61 | |
Reid Spencer | 2da5c3d | 2004-09-15 17:06:42 +0000 | [diff] [blame] | 62 | //remove phi node |
| 63 | clonedBlock->getInstList().erase(PN); |
Tanya Lattner | 6074d2f | 2003-05-30 15:50:18 +0000 | [diff] [blame] | 64 | } |
| 65 | } |
| 66 | } |
| 67 | |
| 68 | //Second loop to do the remapping |
| 69 | for(std::vector<BasicBlock *>::const_iterator BB = clonedTrace.begin(), |
Jeff Cohen | 9d80930 | 2005-04-23 21:38:35 +0000 | [diff] [blame^] | 70 | BE = clonedTrace.end(); BB != BE; ++BB) { |
Tanya Lattner | 6074d2f | 2003-05-30 15:50:18 +0000 | [diff] [blame] | 71 | for(BasicBlock::iterator I = (*BB)->begin(); I != (*BB)->end(); ++I) { |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 72 | |
Tanya Lattner | 6074d2f | 2003-05-30 15:50:18 +0000 | [diff] [blame] | 73 | //Loop over all the operands of the instruction |
| 74 | for(unsigned op=0, E = I->getNumOperands(); op != E; ++op) { |
Jeff Cohen | 9d80930 | 2005-04-23 21:38:35 +0000 | [diff] [blame^] | 75 | const Value *Op = I->getOperand(op); |
Tanya Lattner | 6074d2f | 2003-05-30 15:50:18 +0000 | [diff] [blame] | 76 | |
Jeff Cohen | 9d80930 | 2005-04-23 21:38:35 +0000 | [diff] [blame^] | 77 | //Get it out of the value map |
| 78 | Value *V = ValueMap[Op]; |
| 79 | |
| 80 | //If not in the value map, then its outside our trace so ignore |
| 81 | if(V != 0) |
| 82 | I->setOperand(op,V); |
Tanya Lattner | 6074d2f | 2003-05-30 15:50:18 +0000 | [diff] [blame] | 83 | } |
| 84 | } |
| 85 | } |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 86 | |
Tanya Lattner | 6074d2f | 2003-05-30 15:50:18 +0000 | [diff] [blame] | 87 | //return new vector of basic blocks |
| 88 | return clonedTrace; |
| 89 | } |
Brian Gaeke | c58a7f4 | 2004-05-19 09:08:14 +0000 | [diff] [blame] | 90 | |
| 91 | /// CloneTraceInto - Clone T into NewFunc. Original<->clone mapping is |
| 92 | /// saved in ValueMap. |
| 93 | /// |
| 94 | void llvm::CloneTraceInto(Function *NewFunc, Trace &T, |
| 95 | std::map<const Value*, Value*> &ValueMap, |
| 96 | const char *NameSuffix) { |
| 97 | assert(NameSuffix && "NameSuffix cannot be null!"); |
| 98 | |
| 99 | // Loop over all of the basic blocks in the trace, cloning them as |
| 100 | // appropriate. |
| 101 | // |
| 102 | for (Trace::const_iterator BI = T.begin(), BE = T.end(); BI != BE; ++BI) { |
| 103 | const BasicBlock *BB = *BI; |
| 104 | |
| 105 | // Create a new basic block and copy instructions into it! |
| 106 | BasicBlock *CBB = CloneBasicBlock(BB, ValueMap, NameSuffix, NewFunc); |
| 107 | ValueMap[BB] = CBB; // Add basic block mapping. |
| 108 | } |
| 109 | |
| 110 | // Loop over all of the instructions in the new function, fixing up operand |
| 111 | // references as we go. This uses ValueMap to do all the hard work. |
| 112 | // |
| 113 | for (Function::iterator BB = |
| 114 | cast<BasicBlock>(ValueMap[T.getEntryBasicBlock()]), |
| 115 | BE = NewFunc->end(); BB != BE; ++BB) |
| 116 | // Loop over all instructions, fixing each one as we find it... |
| 117 | for (BasicBlock::iterator II = BB->begin(); II != BB->end(); ++II) |
| 118 | RemapInstruction(II, ValueMap); |
| 119 | } |
| 120 | |