Chris Lattner | 6c2e2e5 | 2002-11-19 22:04:49 +0000 | [diff] [blame] | 1 | //===- CloneFunction.cpp - Clone a function into another function ---------===// |
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 | //===----------------------------------------------------------------------===// |
Chris Lattner | 6c2e2e5 | 2002-11-19 22:04:49 +0000 | [diff] [blame] | 9 | // |
| 10 | // This file implements the CloneFunctionInto interface, which is used as the |
| 11 | // low-level function cloner. This is used by the CloneFunction and function |
| 12 | // inliner to do the dirty work of copying the body of a function around. |
| 13 | // |
| 14 | //===----------------------------------------------------------------------===// |
Chris Lattner | fa703a4 | 2002-03-29 19:03:54 +0000 | [diff] [blame] | 15 | |
Chris Lattner | 309f193 | 2002-11-19 20:59:41 +0000 | [diff] [blame] | 16 | #include "llvm/Transforms/Utils/Cloning.h" |
Chris Lattner | a4c29d2 | 2006-01-13 18:39:17 +0000 | [diff] [blame] | 17 | #include "llvm/Constants.h" |
Chris Lattner | 5a8932f | 2002-11-19 23:12:22 +0000 | [diff] [blame] | 18 | #include "llvm/DerivedTypes.h" |
Chris Lattner | a4c29d2 | 2006-01-13 18:39:17 +0000 | [diff] [blame] | 19 | #include "llvm/Instructions.h" |
Chris Lattner | fa703a4 | 2002-03-29 19:03:54 +0000 | [diff] [blame] | 20 | #include "llvm/Function.h" |
Chris Lattner | 35033ef | 2006-06-01 19:19:23 +0000 | [diff] [blame] | 21 | #include "llvm/Support/CFG.h" |
Reid Spencer | 9133fe2 | 2007-02-05 23:32:05 +0000 | [diff] [blame] | 22 | #include "llvm/Support/Compiler.h" |
Anton Korobeynikov | 344ef19 | 2007-11-09 12:27:04 +0000 | [diff] [blame] | 23 | #include "llvm/Transforms/Utils/ValueMapper.h" |
Chris Lattner | 79066fa | 2007-01-30 23:46:24 +0000 | [diff] [blame] | 24 | #include "llvm/Analysis/ConstantFolding.h" |
Chris Lattner | 9fa038d | 2007-01-30 23:13:49 +0000 | [diff] [blame] | 25 | #include "llvm/ADT/SmallVector.h" |
Chris Lattner | 5e665f5 | 2007-02-03 00:08:31 +0000 | [diff] [blame] | 26 | #include <map> |
Chris Lattner | f7703df | 2004-01-09 06:12:26 +0000 | [diff] [blame] | 27 | using namespace llvm; |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 28 | |
Chris Lattner | 17d145d | 2003-04-18 03:50:09 +0000 | [diff] [blame] | 29 | // CloneBasicBlock - See comments in Cloning.h |
Chris Lattner | f7703df | 2004-01-09 06:12:26 +0000 | [diff] [blame] | 30 | BasicBlock *llvm::CloneBasicBlock(const BasicBlock *BB, |
Chris Lattner | 5e665f5 | 2007-02-03 00:08:31 +0000 | [diff] [blame] | 31 | DenseMap<const Value*, Value*> &ValueMap, |
Chris Lattner | a4c29d2 | 2006-01-13 18:39:17 +0000 | [diff] [blame] | 32 | const char *NameSuffix, Function *F, |
| 33 | ClonedCodeInfo *CodeInfo) { |
Chris Lattner | 23b4c68 | 2004-02-04 01:19:43 +0000 | [diff] [blame] | 34 | BasicBlock *NewBB = new BasicBlock("", F); |
Chris Lattner | 17d145d | 2003-04-18 03:50:09 +0000 | [diff] [blame] | 35 | if (BB->hasName()) NewBB->setName(BB->getName()+NameSuffix); |
| 36 | |
Chris Lattner | a4c29d2 | 2006-01-13 18:39:17 +0000 | [diff] [blame] | 37 | bool hasCalls = false, hasDynamicAllocas = false, hasStaticAllocas = false; |
| 38 | |
| 39 | // Loop over all instructions, and copy them over. |
Chris Lattner | 17d145d | 2003-04-18 03:50:09 +0000 | [diff] [blame] | 40 | for (BasicBlock::const_iterator II = BB->begin(), IE = BB->end(); |
| 41 | II != IE; ++II) { |
| 42 | Instruction *NewInst = II->clone(); |
| 43 | if (II->hasName()) |
| 44 | NewInst->setName(II->getName()+NameSuffix); |
| 45 | NewBB->getInstList().push_back(NewInst); |
| 46 | ValueMap[II] = NewInst; // Add instruction map to value. |
Chris Lattner | a4c29d2 | 2006-01-13 18:39:17 +0000 | [diff] [blame] | 47 | |
| 48 | hasCalls |= isa<CallInst>(II); |
| 49 | if (const AllocaInst *AI = dyn_cast<AllocaInst>(II)) { |
| 50 | if (isa<ConstantInt>(AI->getArraySize())) |
| 51 | hasStaticAllocas = true; |
| 52 | else |
| 53 | hasDynamicAllocas = true; |
| 54 | } |
| 55 | } |
| 56 | |
| 57 | if (CodeInfo) { |
| 58 | CodeInfo->ContainsCalls |= hasCalls; |
| 59 | CodeInfo->ContainsUnwinds |= isa<UnwindInst>(BB->getTerminator()); |
| 60 | CodeInfo->ContainsDynamicAllocas |= hasDynamicAllocas; |
| 61 | CodeInfo->ContainsDynamicAllocas |= hasStaticAllocas && |
Dan Gohman | ecb7a77 | 2007-03-22 16:38:57 +0000 | [diff] [blame] | 62 | BB != &BB->getParent()->getEntryBlock(); |
Chris Lattner | 17d145d | 2003-04-18 03:50:09 +0000 | [diff] [blame] | 63 | } |
| 64 | return NewBB; |
| 65 | } |
| 66 | |
Chris Lattner | fa703a4 | 2002-03-29 19:03:54 +0000 | [diff] [blame] | 67 | // Clone OldFunc into NewFunc, transforming the old arguments into references to |
| 68 | // ArgMap values. |
| 69 | // |
Chris Lattner | f7703df | 2004-01-09 06:12:26 +0000 | [diff] [blame] | 70 | void llvm::CloneFunctionInto(Function *NewFunc, const Function *OldFunc, |
Chris Lattner | 5e665f5 | 2007-02-03 00:08:31 +0000 | [diff] [blame] | 71 | DenseMap<const Value*, Value*> &ValueMap, |
Chris Lattner | f7703df | 2004-01-09 06:12:26 +0000 | [diff] [blame] | 72 | std::vector<ReturnInst*> &Returns, |
Chris Lattner | a4c29d2 | 2006-01-13 18:39:17 +0000 | [diff] [blame] | 73 | const char *NameSuffix, ClonedCodeInfo *CodeInfo) { |
Chris Lattner | dcd8040 | 2002-11-19 21:54:07 +0000 | [diff] [blame] | 74 | assert(NameSuffix && "NameSuffix cannot be null!"); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 75 | |
Chris Lattner | d180155 | 2002-11-19 22:54:01 +0000 | [diff] [blame] | 76 | #ifndef NDEBUG |
Chris Lattner | a4c29d2 | 2006-01-13 18:39:17 +0000 | [diff] [blame] | 77 | for (Function::const_arg_iterator I = OldFunc->arg_begin(), |
| 78 | E = OldFunc->arg_end(); I != E; ++I) |
Chris Lattner | d180155 | 2002-11-19 22:54:01 +0000 | [diff] [blame] | 79 | assert(ValueMap.count(I) && "No mapping from source argument specified!"); |
| 80 | #endif |
Chris Lattner | fa703a4 | 2002-03-29 19:03:54 +0000 | [diff] [blame] | 81 | |
Duncan Sands | dc02467 | 2007-11-27 13:23:08 +0000 | [diff] [blame] | 82 | // Clone the parameter attributes |
| 83 | NewFunc->setParamAttrs(OldFunc->getParamAttrs()); |
| 84 | |
Chris Lattner | fa703a4 | 2002-03-29 19:03:54 +0000 | [diff] [blame] | 85 | // Loop over all of the basic blocks in the function, cloning them as |
Chris Lattner | dcd8040 | 2002-11-19 21:54:07 +0000 | [diff] [blame] | 86 | // appropriate. Note that we save BE this way in order to handle cloning of |
| 87 | // recursive functions into themselves. |
Chris Lattner | fa703a4 | 2002-03-29 19:03:54 +0000 | [diff] [blame] | 88 | // |
| 89 | for (Function::const_iterator BI = OldFunc->begin(), BE = OldFunc->end(); |
| 90 | BI != BE; ++BI) { |
Chris Lattner | 1896150 | 2002-06-25 16:12:52 +0000 | [diff] [blame] | 91 | const BasicBlock &BB = *BI; |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 92 | |
Chris Lattner | 17d145d | 2003-04-18 03:50:09 +0000 | [diff] [blame] | 93 | // Create a new basic block and copy instructions into it! |
Chris Lattner | a4c29d2 | 2006-01-13 18:39:17 +0000 | [diff] [blame] | 94 | BasicBlock *CBB = CloneBasicBlock(&BB, ValueMap, NameSuffix, NewFunc, |
| 95 | CodeInfo); |
Chris Lattner | 1896150 | 2002-06-25 16:12:52 +0000 | [diff] [blame] | 96 | ValueMap[&BB] = CBB; // Add basic block mapping. |
Chris Lattner | fa703a4 | 2002-03-29 19:03:54 +0000 | [diff] [blame] | 97 | |
Chris Lattner | dcd8040 | 2002-11-19 21:54:07 +0000 | [diff] [blame] | 98 | if (ReturnInst *RI = dyn_cast<ReturnInst>(CBB->getTerminator())) |
| 99 | Returns.push_back(RI); |
Chris Lattner | fa703a4 | 2002-03-29 19:03:54 +0000 | [diff] [blame] | 100 | } |
| 101 | |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 102 | // Loop over all of the instructions in the function, fixing up operand |
Chris Lattner | fa703a4 | 2002-03-29 19:03:54 +0000 | [diff] [blame] | 103 | // references as we go. This uses ValueMap to do all the hard work. |
| 104 | // |
Chris Lattner | a33ceaa | 2004-02-04 21:44:26 +0000 | [diff] [blame] | 105 | for (Function::iterator BB = cast<BasicBlock>(ValueMap[OldFunc->begin()]), |
| 106 | BE = NewFunc->end(); BB != BE; ++BB) |
Chris Lattner | fa703a4 | 2002-03-29 19:03:54 +0000 | [diff] [blame] | 107 | // Loop over all instructions, fixing each one as we find it... |
Chris Lattner | a33ceaa | 2004-02-04 21:44:26 +0000 | [diff] [blame] | 108 | for (BasicBlock::iterator II = BB->begin(); II != BB->end(); ++II) |
Chris Lattner | 1896150 | 2002-06-25 16:12:52 +0000 | [diff] [blame] | 109 | RemapInstruction(II, ValueMap); |
Chris Lattner | fa703a4 | 2002-03-29 19:03:54 +0000 | [diff] [blame] | 110 | } |
Chris Lattner | 5a8932f | 2002-11-19 23:12:22 +0000 | [diff] [blame] | 111 | |
| 112 | /// CloneFunction - Return a copy of the specified function, but without |
| 113 | /// embedding the function into another module. Also, any references specified |
| 114 | /// in the ValueMap are changed to refer to their mapped value instead of the |
| 115 | /// original one. If any of the arguments to the function are in the ValueMap, |
| 116 | /// the arguments are deleted from the resultant function. The ValueMap is |
| 117 | /// updated to include mappings from all of the instructions and basicblocks in |
| 118 | /// the function from their old to new values. |
| 119 | /// |
Chris Lattner | f7703df | 2004-01-09 06:12:26 +0000 | [diff] [blame] | 120 | Function *llvm::CloneFunction(const Function *F, |
Chris Lattner | 5e665f5 | 2007-02-03 00:08:31 +0000 | [diff] [blame] | 121 | DenseMap<const Value*, Value*> &ValueMap, |
Chris Lattner | a4c29d2 | 2006-01-13 18:39:17 +0000 | [diff] [blame] | 122 | ClonedCodeInfo *CodeInfo) { |
Chris Lattner | 5a8932f | 2002-11-19 23:12:22 +0000 | [diff] [blame] | 123 | std::vector<const Type*> ArgTypes; |
| 124 | |
| 125 | // The user might be deleting arguments to the function by specifying them in |
| 126 | // the ValueMap. If so, we need to not add the arguments to the arg ty vector |
| 127 | // |
Chris Lattner | a4c29d2 | 2006-01-13 18:39:17 +0000 | [diff] [blame] | 128 | for (Function::const_arg_iterator I = F->arg_begin(), E = F->arg_end(); |
| 129 | I != E; ++I) |
Chris Lattner | 5a8932f | 2002-11-19 23:12:22 +0000 | [diff] [blame] | 130 | if (ValueMap.count(I) == 0) // Haven't mapped the argument to anything yet? |
| 131 | ArgTypes.push_back(I->getType()); |
| 132 | |
| 133 | // Create a new function type... |
| 134 | FunctionType *FTy = FunctionType::get(F->getFunctionType()->getReturnType(), |
| 135 | ArgTypes, F->getFunctionType()->isVarArg()); |
| 136 | |
| 137 | // Create the new function... |
Chris Lattner | 4ad02e7 | 2003-04-16 20:28:45 +0000 | [diff] [blame] | 138 | Function *NewF = new Function(FTy, F->getLinkage(), F->getName()); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 139 | |
Chris Lattner | 5a8932f | 2002-11-19 23:12:22 +0000 | [diff] [blame] | 140 | // Loop over the arguments, copying the names of the mapped arguments over... |
Chris Lattner | e4d5c44 | 2005-03-15 04:54:21 +0000 | [diff] [blame] | 141 | Function::arg_iterator DestI = NewF->arg_begin(); |
Chris Lattner | a4c29d2 | 2006-01-13 18:39:17 +0000 | [diff] [blame] | 142 | for (Function::const_arg_iterator I = F->arg_begin(), E = F->arg_end(); |
| 143 | I != E; ++I) |
Chris Lattner | c09aab0 | 2002-11-20 18:32:31 +0000 | [diff] [blame] | 144 | if (ValueMap.count(I) == 0) { // Is this argument preserved? |
Chris Lattner | 5a8932f | 2002-11-19 23:12:22 +0000 | [diff] [blame] | 145 | DestI->setName(I->getName()); // Copy the name over... |
Chris Lattner | c09aab0 | 2002-11-20 18:32:31 +0000 | [diff] [blame] | 146 | ValueMap[I] = DestI++; // Add mapping to ValueMap |
Chris Lattner | 5a8932f | 2002-11-19 23:12:22 +0000 | [diff] [blame] | 147 | } |
| 148 | |
| 149 | std::vector<ReturnInst*> Returns; // Ignore returns cloned... |
Chris Lattner | a4c29d2 | 2006-01-13 18:39:17 +0000 | [diff] [blame] | 150 | CloneFunctionInto(NewF, F, ValueMap, Returns, "", CodeInfo); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 151 | return NewF; |
Chris Lattner | 5a8932f | 2002-11-19 23:12:22 +0000 | [diff] [blame] | 152 | } |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 153 | |
Chris Lattner | 83f03bf | 2006-05-27 01:22:24 +0000 | [diff] [blame] | 154 | |
| 155 | |
| 156 | namespace { |
| 157 | /// PruningFunctionCloner - This class is a private class used to implement |
| 158 | /// the CloneAndPruneFunctionInto method. |
Reid Spencer | 9133fe2 | 2007-02-05 23:32:05 +0000 | [diff] [blame] | 159 | struct VISIBILITY_HIDDEN PruningFunctionCloner { |
Chris Lattner | 83f03bf | 2006-05-27 01:22:24 +0000 | [diff] [blame] | 160 | Function *NewFunc; |
| 161 | const Function *OldFunc; |
Chris Lattner | 5e665f5 | 2007-02-03 00:08:31 +0000 | [diff] [blame] | 162 | DenseMap<const Value*, Value*> &ValueMap; |
Chris Lattner | 83f03bf | 2006-05-27 01:22:24 +0000 | [diff] [blame] | 163 | std::vector<ReturnInst*> &Returns; |
| 164 | const char *NameSuffix; |
| 165 | ClonedCodeInfo *CodeInfo; |
Chris Lattner | 1dfdf82 | 2007-01-30 23:22:39 +0000 | [diff] [blame] | 166 | const TargetData *TD; |
Chris Lattner | 83f03bf | 2006-05-27 01:22:24 +0000 | [diff] [blame] | 167 | |
| 168 | public: |
| 169 | PruningFunctionCloner(Function *newFunc, const Function *oldFunc, |
Chris Lattner | 5e665f5 | 2007-02-03 00:08:31 +0000 | [diff] [blame] | 170 | DenseMap<const Value*, Value*> &valueMap, |
Chris Lattner | 83f03bf | 2006-05-27 01:22:24 +0000 | [diff] [blame] | 171 | std::vector<ReturnInst*> &returns, |
| 172 | const char *nameSuffix, |
Chris Lattner | 1dfdf82 | 2007-01-30 23:22:39 +0000 | [diff] [blame] | 173 | ClonedCodeInfo *codeInfo, |
| 174 | const TargetData *td) |
Chris Lattner | 83f03bf | 2006-05-27 01:22:24 +0000 | [diff] [blame] | 175 | : NewFunc(newFunc), OldFunc(oldFunc), ValueMap(valueMap), Returns(returns), |
Chris Lattner | 1dfdf82 | 2007-01-30 23:22:39 +0000 | [diff] [blame] | 176 | NameSuffix(nameSuffix), CodeInfo(codeInfo), TD(td) { |
Chris Lattner | 83f03bf | 2006-05-27 01:22:24 +0000 | [diff] [blame] | 177 | } |
| 178 | |
| 179 | /// CloneBlock - The specified block is found to be reachable, clone it and |
| 180 | /// anything that it can reach. |
Chris Lattner | 67ef241 | 2007-03-02 03:11:20 +0000 | [diff] [blame] | 181 | void CloneBlock(const BasicBlock *BB, |
| 182 | std::vector<const BasicBlock*> &ToClone); |
Chris Lattner | 83f03bf | 2006-05-27 01:22:24 +0000 | [diff] [blame] | 183 | |
| 184 | public: |
| 185 | /// ConstantFoldMappedInstruction - Constant fold the specified instruction, |
| 186 | /// mapping its operands through ValueMap if they are available. |
| 187 | Constant *ConstantFoldMappedInstruction(const Instruction *I); |
| 188 | }; |
| 189 | } |
| 190 | |
| 191 | /// CloneBlock - The specified block is found to be reachable, clone it and |
| 192 | /// anything that it can reach. |
Chris Lattner | 67ef241 | 2007-03-02 03:11:20 +0000 | [diff] [blame] | 193 | void PruningFunctionCloner::CloneBlock(const BasicBlock *BB, |
| 194 | std::vector<const BasicBlock*> &ToClone){ |
Chris Lattner | 83f03bf | 2006-05-27 01:22:24 +0000 | [diff] [blame] | 195 | Value *&BBEntry = ValueMap[BB]; |
| 196 | |
| 197 | // Have we already cloned this block? |
| 198 | if (BBEntry) return; |
| 199 | |
| 200 | // Nope, clone it now. |
| 201 | BasicBlock *NewBB; |
| 202 | BBEntry = NewBB = new BasicBlock(); |
| 203 | if (BB->hasName()) NewBB->setName(BB->getName()+NameSuffix); |
| 204 | |
| 205 | bool hasCalls = false, hasDynamicAllocas = false, hasStaticAllocas = false; |
| 206 | |
| 207 | // Loop over all instructions, and copy them over, DCE'ing as we go. This |
| 208 | // loop doesn't include the terminator. |
Chris Lattner | 35033ef | 2006-06-01 19:19:23 +0000 | [diff] [blame] | 209 | for (BasicBlock::const_iterator II = BB->begin(), IE = --BB->end(); |
Chris Lattner | 83f03bf | 2006-05-27 01:22:24 +0000 | [diff] [blame] | 210 | II != IE; ++II) { |
| 211 | // If this instruction constant folds, don't bother cloning the instruction, |
| 212 | // instead, just add the constant to the value map. |
| 213 | if (Constant *C = ConstantFoldMappedInstruction(II)) { |
| 214 | ValueMap[II] = C; |
| 215 | continue; |
| 216 | } |
| 217 | |
| 218 | Instruction *NewInst = II->clone(); |
| 219 | if (II->hasName()) |
| 220 | NewInst->setName(II->getName()+NameSuffix); |
| 221 | NewBB->getInstList().push_back(NewInst); |
| 222 | ValueMap[II] = NewInst; // Add instruction map to value. |
| 223 | |
| 224 | hasCalls |= isa<CallInst>(II); |
| 225 | if (const AllocaInst *AI = dyn_cast<AllocaInst>(II)) { |
| 226 | if (isa<ConstantInt>(AI->getArraySize())) |
| 227 | hasStaticAllocas = true; |
| 228 | else |
| 229 | hasDynamicAllocas = true; |
| 230 | } |
| 231 | } |
| 232 | |
Chris Lattner | 35033ef | 2006-06-01 19:19:23 +0000 | [diff] [blame] | 233 | // Finally, clone over the terminator. |
| 234 | const TerminatorInst *OldTI = BB->getTerminator(); |
| 235 | bool TerminatorDone = false; |
| 236 | if (const BranchInst *BI = dyn_cast<BranchInst>(OldTI)) { |
| 237 | if (BI->isConditional()) { |
| 238 | // If the condition was a known constant in the callee... |
Zhou Sheng | 6b6b6ef | 2007-01-11 12:24:14 +0000 | [diff] [blame] | 239 | ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition()); |
| 240 | // Or is a known constant in the caller... |
| 241 | if (Cond == 0) |
| 242 | Cond = dyn_cast_or_null<ConstantInt>(ValueMap[BI->getCondition()]); |
| 243 | |
| 244 | // Constant fold to uncond branch! |
| 245 | if (Cond) { |
Reid Spencer | 579dca1 | 2007-01-12 04:24:46 +0000 | [diff] [blame] | 246 | BasicBlock *Dest = BI->getSuccessor(!Cond->getZExtValue()); |
Chris Lattner | 35033ef | 2006-06-01 19:19:23 +0000 | [diff] [blame] | 247 | ValueMap[OldTI] = new BranchInst(Dest, NewBB); |
Chris Lattner | 67ef241 | 2007-03-02 03:11:20 +0000 | [diff] [blame] | 248 | ToClone.push_back(Dest); |
Chris Lattner | 35033ef | 2006-06-01 19:19:23 +0000 | [diff] [blame] | 249 | TerminatorDone = true; |
| 250 | } |
| 251 | } |
| 252 | } else if (const SwitchInst *SI = dyn_cast<SwitchInst>(OldTI)) { |
| 253 | // If switching on a value known constant in the caller. |
| 254 | ConstantInt *Cond = dyn_cast<ConstantInt>(SI->getCondition()); |
| 255 | if (Cond == 0) // Or known constant after constant prop in the callee... |
| 256 | Cond = dyn_cast_or_null<ConstantInt>(ValueMap[SI->getCondition()]); |
| 257 | if (Cond) { // Constant fold to uncond branch! |
| 258 | BasicBlock *Dest = SI->getSuccessor(SI->findCaseValue(Cond)); |
| 259 | ValueMap[OldTI] = new BranchInst(Dest, NewBB); |
Chris Lattner | 67ef241 | 2007-03-02 03:11:20 +0000 | [diff] [blame] | 260 | ToClone.push_back(Dest); |
Chris Lattner | 35033ef | 2006-06-01 19:19:23 +0000 | [diff] [blame] | 261 | TerminatorDone = true; |
| 262 | } |
| 263 | } |
| 264 | |
| 265 | if (!TerminatorDone) { |
| 266 | Instruction *NewInst = OldTI->clone(); |
| 267 | if (OldTI->hasName()) |
| 268 | NewInst->setName(OldTI->getName()+NameSuffix); |
| 269 | NewBB->getInstList().push_back(NewInst); |
| 270 | ValueMap[OldTI] = NewInst; // Add instruction map to value. |
| 271 | |
| 272 | // Recursively clone any reachable successor blocks. |
| 273 | const TerminatorInst *TI = BB->getTerminator(); |
| 274 | for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) |
Chris Lattner | 67ef241 | 2007-03-02 03:11:20 +0000 | [diff] [blame] | 275 | ToClone.push_back(TI->getSuccessor(i)); |
Chris Lattner | 35033ef | 2006-06-01 19:19:23 +0000 | [diff] [blame] | 276 | } |
| 277 | |
Chris Lattner | 83f03bf | 2006-05-27 01:22:24 +0000 | [diff] [blame] | 278 | if (CodeInfo) { |
| 279 | CodeInfo->ContainsCalls |= hasCalls; |
Chris Lattner | 35033ef | 2006-06-01 19:19:23 +0000 | [diff] [blame] | 280 | CodeInfo->ContainsUnwinds |= isa<UnwindInst>(OldTI); |
Chris Lattner | 83f03bf | 2006-05-27 01:22:24 +0000 | [diff] [blame] | 281 | CodeInfo->ContainsDynamicAllocas |= hasDynamicAllocas; |
| 282 | CodeInfo->ContainsDynamicAllocas |= hasStaticAllocas && |
| 283 | BB != &BB->getParent()->front(); |
| 284 | } |
| 285 | |
| 286 | if (ReturnInst *RI = dyn_cast<ReturnInst>(NewBB->getTerminator())) |
| 287 | Returns.push_back(RI); |
Chris Lattner | 83f03bf | 2006-05-27 01:22:24 +0000 | [diff] [blame] | 288 | } |
| 289 | |
| 290 | /// ConstantFoldMappedInstruction - Constant fold the specified instruction, |
| 291 | /// mapping its operands through ValueMap if they are available. |
| 292 | Constant *PruningFunctionCloner:: |
| 293 | ConstantFoldMappedInstruction(const Instruction *I) { |
Chris Lattner | 9fa038d | 2007-01-30 23:13:49 +0000 | [diff] [blame] | 294 | SmallVector<Constant*, 8> Ops; |
Chris Lattner | 83f03bf | 2006-05-27 01:22:24 +0000 | [diff] [blame] | 295 | for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) |
| 296 | if (Constant *Op = dyn_cast_or_null<Constant>(MapValue(I->getOperand(i), |
| 297 | ValueMap))) |
| 298 | Ops.push_back(Op); |
| 299 | else |
| 300 | return 0; // All operands not constant! |
| 301 | |
Chris Lattner | f286f6f | 2007-12-10 22:53:04 +0000 | [diff] [blame] | 302 | |
| 303 | if (const CmpInst *CI = dyn_cast<CmpInst>(I)) |
| 304 | return ConstantFoldCompareInstOperands(CI->getPredicate(), |
| 305 | &Ops[0], Ops.size(), TD); |
| 306 | else |
| 307 | return ConstantFoldInstOperands(I->getOpcode(), I->getType(), |
| 308 | &Ops[0], Ops.size(), TD); |
Chris Lattner | 83f03bf | 2006-05-27 01:22:24 +0000 | [diff] [blame] | 309 | } |
| 310 | |
Chris Lattner | 83f03bf | 2006-05-27 01:22:24 +0000 | [diff] [blame] | 311 | /// CloneAndPruneFunctionInto - This works exactly like CloneFunctionInto, |
| 312 | /// except that it does some simple constant prop and DCE on the fly. The |
| 313 | /// effect of this is to copy significantly less code in cases where (for |
| 314 | /// example) a function call with constant arguments is inlined, and those |
| 315 | /// constant arguments cause a significant amount of code in the callee to be |
Duncan Sands | dc02467 | 2007-11-27 13:23:08 +0000 | [diff] [blame] | 316 | /// dead. Since this doesn't produce an exact copy of the input, it can't be |
Chris Lattner | 83f03bf | 2006-05-27 01:22:24 +0000 | [diff] [blame] | 317 | /// used for things like CloneFunction or CloneModule. |
| 318 | void llvm::CloneAndPruneFunctionInto(Function *NewFunc, const Function *OldFunc, |
Chris Lattner | 5e665f5 | 2007-02-03 00:08:31 +0000 | [diff] [blame] | 319 | DenseMap<const Value*, Value*> &ValueMap, |
Chris Lattner | 83f03bf | 2006-05-27 01:22:24 +0000 | [diff] [blame] | 320 | std::vector<ReturnInst*> &Returns, |
| 321 | const char *NameSuffix, |
Chris Lattner | 1dfdf82 | 2007-01-30 23:22:39 +0000 | [diff] [blame] | 322 | ClonedCodeInfo *CodeInfo, |
| 323 | const TargetData *TD) { |
Chris Lattner | 83f03bf | 2006-05-27 01:22:24 +0000 | [diff] [blame] | 324 | assert(NameSuffix && "NameSuffix cannot be null!"); |
| 325 | |
| 326 | #ifndef NDEBUG |
Jeff Cohen | d41b30d | 2006-11-05 19:31:28 +0000 | [diff] [blame] | 327 | for (Function::const_arg_iterator II = OldFunc->arg_begin(), |
| 328 | E = OldFunc->arg_end(); II != E; ++II) |
| 329 | assert(ValueMap.count(II) && "No mapping from source argument specified!"); |
Chris Lattner | 83f03bf | 2006-05-27 01:22:24 +0000 | [diff] [blame] | 330 | #endif |
| 331 | |
| 332 | PruningFunctionCloner PFC(NewFunc, OldFunc, ValueMap, Returns, |
Chris Lattner | 1dfdf82 | 2007-01-30 23:22:39 +0000 | [diff] [blame] | 333 | NameSuffix, CodeInfo, TD); |
Chris Lattner | 83f03bf | 2006-05-27 01:22:24 +0000 | [diff] [blame] | 334 | |
| 335 | // Clone the entry block, and anything recursively reachable from it. |
Chris Lattner | 67ef241 | 2007-03-02 03:11:20 +0000 | [diff] [blame] | 336 | std::vector<const BasicBlock*> CloneWorklist; |
| 337 | CloneWorklist.push_back(&OldFunc->getEntryBlock()); |
| 338 | while (!CloneWorklist.empty()) { |
| 339 | const BasicBlock *BB = CloneWorklist.back(); |
| 340 | CloneWorklist.pop_back(); |
| 341 | PFC.CloneBlock(BB, CloneWorklist); |
| 342 | } |
Chris Lattner | 83f03bf | 2006-05-27 01:22:24 +0000 | [diff] [blame] | 343 | |
| 344 | // Loop over all of the basic blocks in the old function. If the block was |
| 345 | // reachable, we have cloned it and the old block is now in the value map: |
| 346 | // insert it into the new function in the right order. If not, ignore it. |
| 347 | // |
Chris Lattner | 35033ef | 2006-06-01 19:19:23 +0000 | [diff] [blame] | 348 | // Defer PHI resolution until rest of function is resolved. |
| 349 | std::vector<const PHINode*> PHIToResolve; |
Chris Lattner | 83f03bf | 2006-05-27 01:22:24 +0000 | [diff] [blame] | 350 | for (Function::const_iterator BI = OldFunc->begin(), BE = OldFunc->end(); |
| 351 | BI != BE; ++BI) { |
| 352 | BasicBlock *NewBB = cast_or_null<BasicBlock>(ValueMap[BI]); |
| 353 | if (NewBB == 0) continue; // Dead block. |
Chris Lattner | 35033ef | 2006-06-01 19:19:23 +0000 | [diff] [blame] | 354 | |
Chris Lattner | 83f03bf | 2006-05-27 01:22:24 +0000 | [diff] [blame] | 355 | // Add the new block to the new function. |
| 356 | NewFunc->getBasicBlockList().push_back(NewBB); |
| 357 | |
| 358 | // Loop over all of the instructions in the block, fixing up operand |
| 359 | // references as we go. This uses ValueMap to do all the hard work. |
| 360 | // |
| 361 | BasicBlock::iterator I = NewBB->begin(); |
| 362 | |
| 363 | // Handle PHI nodes specially, as we have to remove references to dead |
| 364 | // blocks. |
| 365 | if (PHINode *PN = dyn_cast<PHINode>(I)) { |
Chris Lattner | 35033ef | 2006-06-01 19:19:23 +0000 | [diff] [blame] | 366 | // Skip over all PHI nodes, remembering them for later. |
| 367 | BasicBlock::const_iterator OldI = BI->begin(); |
| 368 | for (; (PN = dyn_cast<PHINode>(I)); ++I, ++OldI) |
| 369 | PHIToResolve.push_back(cast<PHINode>(OldI)); |
Chris Lattner | 83f03bf | 2006-05-27 01:22:24 +0000 | [diff] [blame] | 370 | } |
| 371 | |
| 372 | // Otherwise, remap the rest of the instructions normally. |
| 373 | for (; I != NewBB->end(); ++I) |
| 374 | RemapInstruction(I, ValueMap); |
| 375 | } |
Chris Lattner | 35033ef | 2006-06-01 19:19:23 +0000 | [diff] [blame] | 376 | |
| 377 | // Defer PHI resolution until rest of function is resolved, PHI resolution |
| 378 | // requires the CFG to be up-to-date. |
| 379 | for (unsigned phino = 0, e = PHIToResolve.size(); phino != e; ) { |
| 380 | const PHINode *OPN = PHIToResolve[phino]; |
Chris Lattner | 35033ef | 2006-06-01 19:19:23 +0000 | [diff] [blame] | 381 | unsigned NumPreds = OPN->getNumIncomingValues(); |
Chris Lattner | 35033ef | 2006-06-01 19:19:23 +0000 | [diff] [blame] | 382 | const BasicBlock *OldBB = OPN->getParent(); |
| 383 | BasicBlock *NewBB = cast<BasicBlock>(ValueMap[OldBB]); |
| 384 | |
| 385 | // Map operands for blocks that are live and remove operands for blocks |
| 386 | // that are dead. |
| 387 | for (; phino != PHIToResolve.size() && |
| 388 | PHIToResolve[phino]->getParent() == OldBB; ++phino) { |
| 389 | OPN = PHIToResolve[phino]; |
| 390 | PHINode *PN = cast<PHINode>(ValueMap[OPN]); |
| 391 | for (unsigned pred = 0, e = NumPreds; pred != e; ++pred) { |
| 392 | if (BasicBlock *MappedBlock = |
| 393 | cast_or_null<BasicBlock>(ValueMap[PN->getIncomingBlock(pred)])) { |
| 394 | Value *InVal = MapValue(PN->getIncomingValue(pred), ValueMap); |
| 395 | assert(InVal && "Unknown input value?"); |
| 396 | PN->setIncomingValue(pred, InVal); |
| 397 | PN->setIncomingBlock(pred, MappedBlock); |
| 398 | } else { |
| 399 | PN->removeIncomingValue(pred, false); |
| 400 | --pred, --e; // Revisit the next entry. |
| 401 | } |
| 402 | } |
| 403 | } |
| 404 | |
| 405 | // The loop above has removed PHI entries for those blocks that are dead |
| 406 | // and has updated others. However, if a block is live (i.e. copied over) |
| 407 | // but its terminator has been changed to not go to this block, then our |
| 408 | // phi nodes will have invalid entries. Update the PHI nodes in this |
| 409 | // case. |
| 410 | PHINode *PN = cast<PHINode>(NewBB->begin()); |
| 411 | NumPreds = std::distance(pred_begin(NewBB), pred_end(NewBB)); |
| 412 | if (NumPreds != PN->getNumIncomingValues()) { |
| 413 | assert(NumPreds < PN->getNumIncomingValues()); |
| 414 | // Count how many times each predecessor comes to this block. |
| 415 | std::map<BasicBlock*, unsigned> PredCount; |
| 416 | for (pred_iterator PI = pred_begin(NewBB), E = pred_end(NewBB); |
| 417 | PI != E; ++PI) |
| 418 | --PredCount[*PI]; |
| 419 | |
| 420 | // Figure out how many entries to remove from each PHI. |
| 421 | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) |
| 422 | ++PredCount[PN->getIncomingBlock(i)]; |
| 423 | |
| 424 | // At this point, the excess predecessor entries are positive in the |
| 425 | // map. Loop over all of the PHIs and remove excess predecessor |
| 426 | // entries. |
| 427 | BasicBlock::iterator I = NewBB->begin(); |
| 428 | for (; (PN = dyn_cast<PHINode>(I)); ++I) { |
| 429 | for (std::map<BasicBlock*, unsigned>::iterator PCI =PredCount.begin(), |
| 430 | E = PredCount.end(); PCI != E; ++PCI) { |
| 431 | BasicBlock *Pred = PCI->first; |
| 432 | for (unsigned NumToRemove = PCI->second; NumToRemove; --NumToRemove) |
| 433 | PN->removeIncomingValue(Pred, false); |
| 434 | } |
| 435 | } |
| 436 | } |
| 437 | |
| 438 | // If the loops above have made these phi nodes have 0 or 1 operand, |
| 439 | // replace them with undef or the input value. We must do this for |
| 440 | // correctness, because 0-operand phis are not valid. |
| 441 | PN = cast<PHINode>(NewBB->begin()); |
| 442 | if (PN->getNumIncomingValues() == 0) { |
| 443 | BasicBlock::iterator I = NewBB->begin(); |
| 444 | BasicBlock::const_iterator OldI = OldBB->begin(); |
| 445 | while ((PN = dyn_cast<PHINode>(I++))) { |
| 446 | Value *NV = UndefValue::get(PN->getType()); |
| 447 | PN->replaceAllUsesWith(NV); |
| 448 | assert(ValueMap[OldI] == PN && "ValueMap mismatch"); |
| 449 | ValueMap[OldI] = NV; |
| 450 | PN->eraseFromParent(); |
| 451 | ++OldI; |
| 452 | } |
Chris Lattner | 35033ef | 2006-06-01 19:19:23 +0000 | [diff] [blame] | 453 | } |
Chris Lattner | 8e8eda7 | 2007-02-01 18:48:38 +0000 | [diff] [blame] | 454 | // NOTE: We cannot eliminate single entry phi nodes here, because of |
| 455 | // ValueMap. Single entry phi nodes can have multiple ValueMap entries |
| 456 | // pointing at them. Thus, deleting one would require scanning the ValueMap |
| 457 | // to update any entries in it that would require that. This would be |
| 458 | // really slow. |
Chris Lattner | 35033ef | 2006-06-01 19:19:23 +0000 | [diff] [blame] | 459 | } |
Chris Lattner | a4646b6 | 2006-09-13 21:27:00 +0000 | [diff] [blame] | 460 | |
| 461 | // Now that the inlined function body has been fully constructed, go through |
| 462 | // and zap unconditional fall-through branches. This happen all the time when |
| 463 | // specializing code: code specialization turns conditional branches into |
| 464 | // uncond branches, and this code folds them. |
| 465 | Function::iterator I = cast<BasicBlock>(ValueMap[&OldFunc->getEntryBlock()]); |
| 466 | while (I != NewFunc->end()) { |
| 467 | BranchInst *BI = dyn_cast<BranchInst>(I->getTerminator()); |
| 468 | if (!BI || BI->isConditional()) { ++I; continue; } |
| 469 | |
Chris Lattner | 8e8eda7 | 2007-02-01 18:48:38 +0000 | [diff] [blame] | 470 | // Note that we can't eliminate uncond branches if the destination has |
| 471 | // single-entry PHI nodes. Eliminating the single-entry phi nodes would |
| 472 | // require scanning the ValueMap to update any entries that point to the phi |
| 473 | // node. |
Chris Lattner | a4646b6 | 2006-09-13 21:27:00 +0000 | [diff] [blame] | 474 | BasicBlock *Dest = BI->getSuccessor(0); |
Chris Lattner | 8e8eda7 | 2007-02-01 18:48:38 +0000 | [diff] [blame] | 475 | if (!Dest->getSinglePredecessor() || isa<PHINode>(Dest->begin())) { |
| 476 | ++I; continue; |
| 477 | } |
Chris Lattner | a4646b6 | 2006-09-13 21:27:00 +0000 | [diff] [blame] | 478 | |
| 479 | // We know all single-entry PHI nodes in the inlined function have been |
| 480 | // removed, so we just need to splice the blocks. |
| 481 | BI->eraseFromParent(); |
| 482 | |
| 483 | // Move all the instructions in the succ to the pred. |
| 484 | I->getInstList().splice(I->end(), Dest->getInstList()); |
| 485 | |
| 486 | // Make all PHI nodes that referred to Dest now refer to I as their source. |
| 487 | Dest->replaceAllUsesWith(I); |
| 488 | |
| 489 | // Remove the dest block. |
| 490 | Dest->eraseFromParent(); |
| 491 | |
| 492 | // Do not increment I, iteratively merge all things this block branches to. |
| 493 | } |
Chris Lattner | 83f03bf | 2006-05-27 01:22:24 +0000 | [diff] [blame] | 494 | } |