]>
Commit | Line | Data |
---|---|---|
223e47cc LB |
1 | //===- CloneFunction.cpp - Clone a function into another function ---------===// |
2 | // | |
3 | // The LLVM Compiler Infrastructure | |
4 | // | |
5 | // This file is distributed under the University of Illinois Open Source | |
6 | // License. See LICENSE.TXT for details. | |
7 | // | |
8 | //===----------------------------------------------------------------------===// | |
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 | //===----------------------------------------------------------------------===// | |
15 | ||
16 | #include "llvm/Transforms/Utils/Cloning.h" | |
970d7e83 LB |
17 | #include "llvm/ADT/SmallVector.h" |
18 | #include "llvm/Analysis/ConstantFolding.h" | |
19 | #include "llvm/Analysis/InstructionSimplify.h" | |
1a4d82fc | 20 | #include "llvm/IR/CFG.h" |
970d7e83 | 21 | #include "llvm/IR/Constants.h" |
1a4d82fc | 22 | #include "llvm/IR/DebugInfo.h" |
970d7e83 LB |
23 | #include "llvm/IR/DerivedTypes.h" |
24 | #include "llvm/IR/Function.h" | |
25 | #include "llvm/IR/GlobalVariable.h" | |
26 | #include "llvm/IR/Instructions.h" | |
27 | #include "llvm/IR/IntrinsicInst.h" | |
28 | #include "llvm/IR/LLVMContext.h" | |
29 | #include "llvm/IR/Metadata.h" | |
1a4d82fc | 30 | #include "llvm/IR/Module.h" |
223e47cc LB |
31 | #include "llvm/Transforms/Utils/BasicBlockUtils.h" |
32 | #include "llvm/Transforms/Utils/Local.h" | |
33 | #include "llvm/Transforms/Utils/ValueMapper.h" | |
223e47cc LB |
34 | #include <map> |
35 | using namespace llvm; | |
36 | ||
37 | // CloneBasicBlock - See comments in Cloning.h | |
38 | BasicBlock *llvm::CloneBasicBlock(const BasicBlock *BB, | |
39 | ValueToValueMapTy &VMap, | |
40 | const Twine &NameSuffix, Function *F, | |
41 | ClonedCodeInfo *CodeInfo) { | |
42 | BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), "", F); | |
43 | if (BB->hasName()) NewBB->setName(BB->getName()+NameSuffix); | |
44 | ||
45 | bool hasCalls = false, hasDynamicAllocas = false, hasStaticAllocas = false; | |
46 | ||
47 | // Loop over all instructions, and copy them over. | |
48 | for (BasicBlock::const_iterator II = BB->begin(), IE = BB->end(); | |
49 | II != IE; ++II) { | |
50 | Instruction *NewInst = II->clone(); | |
51 | if (II->hasName()) | |
52 | NewInst->setName(II->getName()+NameSuffix); | |
53 | NewBB->getInstList().push_back(NewInst); | |
54 | VMap[II] = NewInst; // Add instruction map to value. | |
55 | ||
56 | hasCalls |= (isa<CallInst>(II) && !isa<DbgInfoIntrinsic>(II)); | |
57 | if (const AllocaInst *AI = dyn_cast<AllocaInst>(II)) { | |
58 | if (isa<ConstantInt>(AI->getArraySize())) | |
59 | hasStaticAllocas = true; | |
60 | else | |
61 | hasDynamicAllocas = true; | |
62 | } | |
63 | } | |
64 | ||
65 | if (CodeInfo) { | |
66 | CodeInfo->ContainsCalls |= hasCalls; | |
67 | CodeInfo->ContainsDynamicAllocas |= hasDynamicAllocas; | |
68 | CodeInfo->ContainsDynamicAllocas |= hasStaticAllocas && | |
69 | BB != &BB->getParent()->getEntryBlock(); | |
70 | } | |
71 | return NewBB; | |
72 | } | |
73 | ||
74 | // Clone OldFunc into NewFunc, transforming the old arguments into references to | |
75 | // VMap values. | |
76 | // | |
77 | void llvm::CloneFunctionInto(Function *NewFunc, const Function *OldFunc, | |
78 | ValueToValueMapTy &VMap, | |
79 | bool ModuleLevelChanges, | |
80 | SmallVectorImpl<ReturnInst*> &Returns, | |
81 | const char *NameSuffix, ClonedCodeInfo *CodeInfo, | |
1a4d82fc JJ |
82 | ValueMapTypeRemapper *TypeMapper, |
83 | ValueMaterializer *Materializer) { | |
223e47cc LB |
84 | assert(NameSuffix && "NameSuffix cannot be null!"); |
85 | ||
86 | #ifndef NDEBUG | |
87 | for (Function::const_arg_iterator I = OldFunc->arg_begin(), | |
88 | E = OldFunc->arg_end(); I != E; ++I) | |
89 | assert(VMap.count(I) && "No mapping from source argument specified!"); | |
90 | #endif | |
91 | ||
1a4d82fc JJ |
92 | // Copy all attributes other than those stored in the AttributeSet. We need |
93 | // to remap the parameter indices of the AttributeSet. | |
94 | AttributeSet NewAttrs = NewFunc->getAttributes(); | |
95 | NewFunc->copyAttributesFrom(OldFunc); | |
96 | NewFunc->setAttributes(NewAttrs); | |
97 | ||
98 | AttributeSet OldAttrs = OldFunc->getAttributes(); | |
99 | // Clone any argument attributes that are present in the VMap. | |
100 | for (const Argument &OldArg : OldFunc->args()) | |
101 | if (Argument *NewArg = dyn_cast<Argument>(VMap[&OldArg])) { | |
102 | AttributeSet attrs = | |
103 | OldAttrs.getParamAttributes(OldArg.getArgNo() + 1); | |
104 | if (attrs.getNumSlots() > 0) | |
105 | NewArg->addAttr(attrs); | |
106 | } | |
223e47cc | 107 | |
1a4d82fc JJ |
108 | NewFunc->setAttributes( |
109 | NewFunc->getAttributes() | |
110 | .addAttributes(NewFunc->getContext(), AttributeSet::ReturnIndex, | |
111 | OldAttrs.getRetAttributes()) | |
112 | .addAttributes(NewFunc->getContext(), AttributeSet::FunctionIndex, | |
113 | OldAttrs.getFnAttributes())); | |
223e47cc LB |
114 | |
115 | // Loop over all of the basic blocks in the function, cloning them as | |
116 | // appropriate. Note that we save BE this way in order to handle cloning of | |
117 | // recursive functions into themselves. | |
118 | // | |
119 | for (Function::const_iterator BI = OldFunc->begin(), BE = OldFunc->end(); | |
120 | BI != BE; ++BI) { | |
121 | const BasicBlock &BB = *BI; | |
122 | ||
123 | // Create a new basic block and copy instructions into it! | |
124 | BasicBlock *CBB = CloneBasicBlock(&BB, VMap, NameSuffix, NewFunc, CodeInfo); | |
125 | ||
126 | // Add basic block mapping. | |
127 | VMap[&BB] = CBB; | |
128 | ||
129 | // It is only legal to clone a function if a block address within that | |
130 | // function is never referenced outside of the function. Given that, we | |
131 | // want to map block addresses from the old function to block addresses in | |
132 | // the clone. (This is different from the generic ValueMapper | |
133 | // implementation, which generates an invalid blockaddress when | |
134 | // cloning a function.) | |
135 | if (BB.hasAddressTaken()) { | |
136 | Constant *OldBBAddr = BlockAddress::get(const_cast<Function*>(OldFunc), | |
137 | const_cast<BasicBlock*>(&BB)); | |
138 | VMap[OldBBAddr] = BlockAddress::get(NewFunc, CBB); | |
139 | } | |
140 | ||
141 | // Note return instructions for the caller. | |
142 | if (ReturnInst *RI = dyn_cast<ReturnInst>(CBB->getTerminator())) | |
143 | Returns.push_back(RI); | |
144 | } | |
145 | ||
146 | // Loop over all of the instructions in the function, fixing up operand | |
147 | // references as we go. This uses VMap to do all the hard work. | |
148 | for (Function::iterator BB = cast<BasicBlock>(VMap[OldFunc->begin()]), | |
149 | BE = NewFunc->end(); BB != BE; ++BB) | |
150 | // Loop over all instructions, fixing each one as we find it... | |
151 | for (BasicBlock::iterator II = BB->begin(); II != BB->end(); ++II) | |
152 | RemapInstruction(II, VMap, | |
153 | ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges, | |
1a4d82fc JJ |
154 | TypeMapper, Materializer); |
155 | } | |
156 | ||
157 | // Find the MDNode which corresponds to the DISubprogram data that described F. | |
158 | static MDNode* FindSubprogram(const Function *F, DebugInfoFinder &Finder) { | |
159 | for (DISubprogram Subprogram : Finder.subprograms()) { | |
160 | if (Subprogram.describes(F)) return Subprogram; | |
161 | } | |
162 | return nullptr; | |
163 | } | |
164 | ||
165 | // Add an operand to an existing MDNode. The new operand will be added at the | |
166 | // back of the operand list. | |
85aaf69f SL |
167 | static void AddOperand(DICompileUnit CU, DIArray SPs, Metadata *NewSP) { |
168 | SmallVector<Metadata *, 16> NewSPs; | |
169 | NewSPs.reserve(SPs->getNumOperands() + 1); | |
170 | for (unsigned I = 0, E = SPs->getNumOperands(); I != E; ++I) | |
171 | NewSPs.push_back(SPs->getOperand(I)); | |
172 | NewSPs.push_back(NewSP); | |
173 | CU.replaceSubprograms(DIArray(MDNode::get(CU->getContext(), NewSPs))); | |
1a4d82fc JJ |
174 | } |
175 | ||
176 | // Clone the module-level debug info associated with OldFunc. The cloned data | |
177 | // will point to NewFunc instead. | |
178 | static void CloneDebugInfoMetadata(Function *NewFunc, const Function *OldFunc, | |
179 | ValueToValueMapTy &VMap) { | |
180 | DebugInfoFinder Finder; | |
181 | Finder.processModule(*OldFunc->getParent()); | |
182 | ||
183 | const MDNode *OldSubprogramMDNode = FindSubprogram(OldFunc, Finder); | |
184 | if (!OldSubprogramMDNode) return; | |
185 | ||
186 | // Ensure that OldFunc appears in the map. | |
187 | // (if it's already there it must point to NewFunc anyway) | |
188 | VMap[OldFunc] = NewFunc; | |
85aaf69f | 189 | DISubprogram NewSubprogram(MapMetadata(OldSubprogramMDNode, VMap)); |
1a4d82fc JJ |
190 | |
191 | for (DICompileUnit CU : Finder.compile_units()) { | |
192 | DIArray Subprograms(CU.getSubprograms()); | |
193 | ||
194 | // If the compile unit's function list contains the old function, it should | |
195 | // also contain the new one. | |
196 | for (unsigned i = 0; i < Subprograms.getNumElements(); i++) { | |
197 | if ((MDNode*)Subprograms.getElement(i) == OldSubprogramMDNode) { | |
85aaf69f SL |
198 | AddOperand(CU, Subprograms, NewSubprogram); |
199 | break; | |
1a4d82fc JJ |
200 | } |
201 | } | |
202 | } | |
223e47cc LB |
203 | } |
204 | ||
205 | /// CloneFunction - Return a copy of the specified function, but without | |
206 | /// embedding the function into another module. Also, any references specified | |
207 | /// in the VMap are changed to refer to their mapped value instead of the | |
208 | /// original one. If any of the arguments to the function are in the VMap, | |
209 | /// the arguments are deleted from the resultant function. The VMap is | |
210 | /// updated to include mappings from all of the instructions and basicblocks in | |
211 | /// the function from their old to new values. | |
212 | /// | |
213 | Function *llvm::CloneFunction(const Function *F, ValueToValueMapTy &VMap, | |
214 | bool ModuleLevelChanges, | |
215 | ClonedCodeInfo *CodeInfo) { | |
216 | std::vector<Type*> ArgTypes; | |
217 | ||
218 | // The user might be deleting arguments to the function by specifying them in | |
219 | // the VMap. If so, we need to not add the arguments to the arg ty vector | |
220 | // | |
221 | for (Function::const_arg_iterator I = F->arg_begin(), E = F->arg_end(); | |
222 | I != E; ++I) | |
223 | if (VMap.count(I) == 0) // Haven't mapped the argument to anything yet? | |
224 | ArgTypes.push_back(I->getType()); | |
225 | ||
226 | // Create a new function type... | |
227 | FunctionType *FTy = FunctionType::get(F->getFunctionType()->getReturnType(), | |
228 | ArgTypes, F->getFunctionType()->isVarArg()); | |
229 | ||
230 | // Create the new function... | |
231 | Function *NewF = Function::Create(FTy, F->getLinkage(), F->getName()); | |
232 | ||
233 | // Loop over the arguments, copying the names of the mapped arguments over... | |
234 | Function::arg_iterator DestI = NewF->arg_begin(); | |
235 | for (Function::const_arg_iterator I = F->arg_begin(), E = F->arg_end(); | |
236 | I != E; ++I) | |
237 | if (VMap.count(I) == 0) { // Is this argument preserved? | |
238 | DestI->setName(I->getName()); // Copy the name over... | |
239 | VMap[I] = DestI++; // Add mapping to VMap | |
240 | } | |
241 | ||
1a4d82fc JJ |
242 | if (ModuleLevelChanges) |
243 | CloneDebugInfoMetadata(NewF, F, VMap); | |
244 | ||
223e47cc LB |
245 | SmallVector<ReturnInst*, 8> Returns; // Ignore returns cloned. |
246 | CloneFunctionInto(NewF, F, VMap, ModuleLevelChanges, Returns, "", CodeInfo); | |
247 | return NewF; | |
248 | } | |
249 | ||
250 | ||
251 | ||
252 | namespace { | |
253 | /// PruningFunctionCloner - This class is a private class used to implement | |
254 | /// the CloneAndPruneFunctionInto method. | |
255 | struct PruningFunctionCloner { | |
256 | Function *NewFunc; | |
257 | const Function *OldFunc; | |
258 | ValueToValueMapTy &VMap; | |
259 | bool ModuleLevelChanges; | |
260 | const char *NameSuffix; | |
261 | ClonedCodeInfo *CodeInfo; | |
1a4d82fc | 262 | const DataLayout *DL; |
223e47cc LB |
263 | public: |
264 | PruningFunctionCloner(Function *newFunc, const Function *oldFunc, | |
265 | ValueToValueMapTy &valueMap, | |
266 | bool moduleLevelChanges, | |
267 | const char *nameSuffix, | |
268 | ClonedCodeInfo *codeInfo, | |
1a4d82fc | 269 | const DataLayout *DL) |
223e47cc LB |
270 | : NewFunc(newFunc), OldFunc(oldFunc), |
271 | VMap(valueMap), ModuleLevelChanges(moduleLevelChanges), | |
1a4d82fc | 272 | NameSuffix(nameSuffix), CodeInfo(codeInfo), DL(DL) { |
223e47cc LB |
273 | } |
274 | ||
275 | /// CloneBlock - The specified block is found to be reachable, clone it and | |
276 | /// anything that it can reach. | |
277 | void CloneBlock(const BasicBlock *BB, | |
278 | std::vector<const BasicBlock*> &ToClone); | |
279 | }; | |
280 | } | |
281 | ||
282 | /// CloneBlock - The specified block is found to be reachable, clone it and | |
283 | /// anything that it can reach. | |
284 | void PruningFunctionCloner::CloneBlock(const BasicBlock *BB, | |
285 | std::vector<const BasicBlock*> &ToClone){ | |
286 | WeakVH &BBEntry = VMap[BB]; | |
287 | ||
288 | // Have we already cloned this block? | |
289 | if (BBEntry) return; | |
290 | ||
291 | // Nope, clone it now. | |
292 | BasicBlock *NewBB; | |
293 | BBEntry = NewBB = BasicBlock::Create(BB->getContext()); | |
294 | if (BB->hasName()) NewBB->setName(BB->getName()+NameSuffix); | |
295 | ||
296 | // It is only legal to clone a function if a block address within that | |
297 | // function is never referenced outside of the function. Given that, we | |
298 | // want to map block addresses from the old function to block addresses in | |
299 | // the clone. (This is different from the generic ValueMapper | |
300 | // implementation, which generates an invalid blockaddress when | |
301 | // cloning a function.) | |
302 | // | |
303 | // Note that we don't need to fix the mapping for unreachable blocks; | |
304 | // the default mapping there is safe. | |
305 | if (BB->hasAddressTaken()) { | |
306 | Constant *OldBBAddr = BlockAddress::get(const_cast<Function*>(OldFunc), | |
307 | const_cast<BasicBlock*>(BB)); | |
308 | VMap[OldBBAddr] = BlockAddress::get(NewFunc, NewBB); | |
309 | } | |
310 | ||
311 | ||
312 | bool hasCalls = false, hasDynamicAllocas = false, hasStaticAllocas = false; | |
313 | ||
314 | // Loop over all instructions, and copy them over, DCE'ing as we go. This | |
315 | // loop doesn't include the terminator. | |
316 | for (BasicBlock::const_iterator II = BB->begin(), IE = --BB->end(); | |
317 | II != IE; ++II) { | |
318 | Instruction *NewInst = II->clone(); | |
319 | ||
320 | // Eagerly remap operands to the newly cloned instruction, except for PHI | |
321 | // nodes for which we defer processing until we update the CFG. | |
322 | if (!isa<PHINode>(NewInst)) { | |
323 | RemapInstruction(NewInst, VMap, | |
324 | ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges); | |
325 | ||
326 | // If we can simplify this instruction to some other value, simply add | |
327 | // a mapping to that value rather than inserting a new instruction into | |
328 | // the basic block. | |
1a4d82fc | 329 | if (Value *V = SimplifyInstruction(NewInst, DL)) { |
223e47cc LB |
330 | // On the off-chance that this simplifies to an instruction in the old |
331 | // function, map it back into the new function. | |
332 | if (Value *MappedV = VMap.lookup(V)) | |
333 | V = MappedV; | |
334 | ||
335 | VMap[II] = V; | |
336 | delete NewInst; | |
337 | continue; | |
338 | } | |
339 | } | |
340 | ||
341 | if (II->hasName()) | |
342 | NewInst->setName(II->getName()+NameSuffix); | |
343 | VMap[II] = NewInst; // Add instruction map to value. | |
344 | NewBB->getInstList().push_back(NewInst); | |
345 | hasCalls |= (isa<CallInst>(II) && !isa<DbgInfoIntrinsic>(II)); | |
346 | if (const AllocaInst *AI = dyn_cast<AllocaInst>(II)) { | |
347 | if (isa<ConstantInt>(AI->getArraySize())) | |
348 | hasStaticAllocas = true; | |
349 | else | |
350 | hasDynamicAllocas = true; | |
351 | } | |
352 | } | |
353 | ||
354 | // Finally, clone over the terminator. | |
355 | const TerminatorInst *OldTI = BB->getTerminator(); | |
356 | bool TerminatorDone = false; | |
357 | if (const BranchInst *BI = dyn_cast<BranchInst>(OldTI)) { | |
358 | if (BI->isConditional()) { | |
359 | // If the condition was a known constant in the callee... | |
360 | ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition()); | |
361 | // Or is a known constant in the caller... | |
1a4d82fc | 362 | if (!Cond) { |
223e47cc LB |
363 | Value *V = VMap[BI->getCondition()]; |
364 | Cond = dyn_cast_or_null<ConstantInt>(V); | |
365 | } | |
366 | ||
367 | // Constant fold to uncond branch! | |
368 | if (Cond) { | |
369 | BasicBlock *Dest = BI->getSuccessor(!Cond->getZExtValue()); | |
370 | VMap[OldTI] = BranchInst::Create(Dest, NewBB); | |
371 | ToClone.push_back(Dest); | |
372 | TerminatorDone = true; | |
373 | } | |
374 | } | |
375 | } else if (const SwitchInst *SI = dyn_cast<SwitchInst>(OldTI)) { | |
376 | // If switching on a value known constant in the caller. | |
377 | ConstantInt *Cond = dyn_cast<ConstantInt>(SI->getCondition()); | |
1a4d82fc | 378 | if (!Cond) { // Or known constant after constant prop in the callee... |
223e47cc LB |
379 | Value *V = VMap[SI->getCondition()]; |
380 | Cond = dyn_cast_or_null<ConstantInt>(V); | |
381 | } | |
382 | if (Cond) { // Constant fold to uncond branch! | |
383 | SwitchInst::ConstCaseIt Case = SI->findCaseValue(Cond); | |
384 | BasicBlock *Dest = const_cast<BasicBlock*>(Case.getCaseSuccessor()); | |
385 | VMap[OldTI] = BranchInst::Create(Dest, NewBB); | |
386 | ToClone.push_back(Dest); | |
387 | TerminatorDone = true; | |
388 | } | |
389 | } | |
390 | ||
391 | if (!TerminatorDone) { | |
392 | Instruction *NewInst = OldTI->clone(); | |
393 | if (OldTI->hasName()) | |
394 | NewInst->setName(OldTI->getName()+NameSuffix); | |
395 | NewBB->getInstList().push_back(NewInst); | |
396 | VMap[OldTI] = NewInst; // Add instruction map to value. | |
397 | ||
398 | // Recursively clone any reachable successor blocks. | |
399 | const TerminatorInst *TI = BB->getTerminator(); | |
400 | for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) | |
401 | ToClone.push_back(TI->getSuccessor(i)); | |
402 | } | |
403 | ||
404 | if (CodeInfo) { | |
405 | CodeInfo->ContainsCalls |= hasCalls; | |
406 | CodeInfo->ContainsDynamicAllocas |= hasDynamicAllocas; | |
407 | CodeInfo->ContainsDynamicAllocas |= hasStaticAllocas && | |
408 | BB != &BB->getParent()->front(); | |
409 | } | |
410 | } | |
411 | ||
412 | /// CloneAndPruneFunctionInto - This works exactly like CloneFunctionInto, | |
413 | /// except that it does some simple constant prop and DCE on the fly. The | |
414 | /// effect of this is to copy significantly less code in cases where (for | |
415 | /// example) a function call with constant arguments is inlined, and those | |
416 | /// constant arguments cause a significant amount of code in the callee to be | |
417 | /// dead. Since this doesn't produce an exact copy of the input, it can't be | |
418 | /// used for things like CloneFunction or CloneModule. | |
419 | void llvm::CloneAndPruneFunctionInto(Function *NewFunc, const Function *OldFunc, | |
420 | ValueToValueMapTy &VMap, | |
421 | bool ModuleLevelChanges, | |
422 | SmallVectorImpl<ReturnInst*> &Returns, | |
423 | const char *NameSuffix, | |
424 | ClonedCodeInfo *CodeInfo, | |
1a4d82fc | 425 | const DataLayout *DL, |
223e47cc LB |
426 | Instruction *TheCall) { |
427 | assert(NameSuffix && "NameSuffix cannot be null!"); | |
428 | ||
429 | #ifndef NDEBUG | |
430 | for (Function::const_arg_iterator II = OldFunc->arg_begin(), | |
431 | E = OldFunc->arg_end(); II != E; ++II) | |
432 | assert(VMap.count(II) && "No mapping from source argument specified!"); | |
433 | #endif | |
434 | ||
435 | PruningFunctionCloner PFC(NewFunc, OldFunc, VMap, ModuleLevelChanges, | |
1a4d82fc | 436 | NameSuffix, CodeInfo, DL); |
223e47cc LB |
437 | |
438 | // Clone the entry block, and anything recursively reachable from it. | |
439 | std::vector<const BasicBlock*> CloneWorklist; | |
440 | CloneWorklist.push_back(&OldFunc->getEntryBlock()); | |
441 | while (!CloneWorklist.empty()) { | |
442 | const BasicBlock *BB = CloneWorklist.back(); | |
443 | CloneWorklist.pop_back(); | |
444 | PFC.CloneBlock(BB, CloneWorklist); | |
445 | } | |
446 | ||
447 | // Loop over all of the basic blocks in the old function. If the block was | |
448 | // reachable, we have cloned it and the old block is now in the value map: | |
449 | // insert it into the new function in the right order. If not, ignore it. | |
450 | // | |
451 | // Defer PHI resolution until rest of function is resolved. | |
452 | SmallVector<const PHINode*, 16> PHIToResolve; | |
453 | for (Function::const_iterator BI = OldFunc->begin(), BE = OldFunc->end(); | |
454 | BI != BE; ++BI) { | |
455 | Value *V = VMap[BI]; | |
456 | BasicBlock *NewBB = cast_or_null<BasicBlock>(V); | |
1a4d82fc | 457 | if (!NewBB) continue; // Dead block. |
223e47cc LB |
458 | |
459 | // Add the new block to the new function. | |
460 | NewFunc->getBasicBlockList().push_back(NewBB); | |
461 | ||
462 | // Handle PHI nodes specially, as we have to remove references to dead | |
463 | // blocks. | |
464 | for (BasicBlock::const_iterator I = BI->begin(), E = BI->end(); I != E; ++I) | |
465 | if (const PHINode *PN = dyn_cast<PHINode>(I)) | |
466 | PHIToResolve.push_back(PN); | |
467 | else | |
468 | break; | |
469 | ||
470 | // Finally, remap the terminator instructions, as those can't be remapped | |
471 | // until all BBs are mapped. | |
472 | RemapInstruction(NewBB->getTerminator(), VMap, | |
473 | ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges); | |
474 | } | |
475 | ||
476 | // Defer PHI resolution until rest of function is resolved, PHI resolution | |
477 | // requires the CFG to be up-to-date. | |
478 | for (unsigned phino = 0, e = PHIToResolve.size(); phino != e; ) { | |
479 | const PHINode *OPN = PHIToResolve[phino]; | |
480 | unsigned NumPreds = OPN->getNumIncomingValues(); | |
481 | const BasicBlock *OldBB = OPN->getParent(); | |
482 | BasicBlock *NewBB = cast<BasicBlock>(VMap[OldBB]); | |
483 | ||
484 | // Map operands for blocks that are live and remove operands for blocks | |
485 | // that are dead. | |
486 | for (; phino != PHIToResolve.size() && | |
487 | PHIToResolve[phino]->getParent() == OldBB; ++phino) { | |
488 | OPN = PHIToResolve[phino]; | |
489 | PHINode *PN = cast<PHINode>(VMap[OPN]); | |
490 | for (unsigned pred = 0, e = NumPreds; pred != e; ++pred) { | |
491 | Value *V = VMap[PN->getIncomingBlock(pred)]; | |
492 | if (BasicBlock *MappedBlock = cast_or_null<BasicBlock>(V)) { | |
493 | Value *InVal = MapValue(PN->getIncomingValue(pred), | |
494 | VMap, | |
495 | ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges); | |
496 | assert(InVal && "Unknown input value?"); | |
497 | PN->setIncomingValue(pred, InVal); | |
498 | PN->setIncomingBlock(pred, MappedBlock); | |
499 | } else { | |
500 | PN->removeIncomingValue(pred, false); | |
501 | --pred, --e; // Revisit the next entry. | |
502 | } | |
503 | } | |
504 | } | |
505 | ||
506 | // The loop above has removed PHI entries for those blocks that are dead | |
507 | // and has updated others. However, if a block is live (i.e. copied over) | |
508 | // but its terminator has been changed to not go to this block, then our | |
509 | // phi nodes will have invalid entries. Update the PHI nodes in this | |
510 | // case. | |
511 | PHINode *PN = cast<PHINode>(NewBB->begin()); | |
512 | NumPreds = std::distance(pred_begin(NewBB), pred_end(NewBB)); | |
513 | if (NumPreds != PN->getNumIncomingValues()) { | |
514 | assert(NumPreds < PN->getNumIncomingValues()); | |
515 | // Count how many times each predecessor comes to this block. | |
516 | std::map<BasicBlock*, unsigned> PredCount; | |
517 | for (pred_iterator PI = pred_begin(NewBB), E = pred_end(NewBB); | |
518 | PI != E; ++PI) | |
519 | --PredCount[*PI]; | |
520 | ||
521 | // Figure out how many entries to remove from each PHI. | |
522 | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) | |
523 | ++PredCount[PN->getIncomingBlock(i)]; | |
524 | ||
525 | // At this point, the excess predecessor entries are positive in the | |
526 | // map. Loop over all of the PHIs and remove excess predecessor | |
527 | // entries. | |
528 | BasicBlock::iterator I = NewBB->begin(); | |
529 | for (; (PN = dyn_cast<PHINode>(I)); ++I) { | |
530 | for (std::map<BasicBlock*, unsigned>::iterator PCI =PredCount.begin(), | |
531 | E = PredCount.end(); PCI != E; ++PCI) { | |
532 | BasicBlock *Pred = PCI->first; | |
533 | for (unsigned NumToRemove = PCI->second; NumToRemove; --NumToRemove) | |
534 | PN->removeIncomingValue(Pred, false); | |
535 | } | |
536 | } | |
537 | } | |
538 | ||
539 | // If the loops above have made these phi nodes have 0 or 1 operand, | |
540 | // replace them with undef or the input value. We must do this for | |
541 | // correctness, because 0-operand phis are not valid. | |
542 | PN = cast<PHINode>(NewBB->begin()); | |
543 | if (PN->getNumIncomingValues() == 0) { | |
544 | BasicBlock::iterator I = NewBB->begin(); | |
545 | BasicBlock::const_iterator OldI = OldBB->begin(); | |
546 | while ((PN = dyn_cast<PHINode>(I++))) { | |
547 | Value *NV = UndefValue::get(PN->getType()); | |
548 | PN->replaceAllUsesWith(NV); | |
549 | assert(VMap[OldI] == PN && "VMap mismatch"); | |
550 | VMap[OldI] = NV; | |
551 | PN->eraseFromParent(); | |
552 | ++OldI; | |
553 | } | |
554 | } | |
555 | } | |
556 | ||
557 | // Make a second pass over the PHINodes now that all of them have been | |
558 | // remapped into the new function, simplifying the PHINode and performing any | |
559 | // recursive simplifications exposed. This will transparently update the | |
560 | // WeakVH in the VMap. Notably, we rely on that so that if we coalesce | |
561 | // two PHINodes, the iteration over the old PHIs remains valid, and the | |
562 | // mapping will just map us to the new node (which may not even be a PHI | |
563 | // node). | |
564 | for (unsigned Idx = 0, Size = PHIToResolve.size(); Idx != Size; ++Idx) | |
565 | if (PHINode *PN = dyn_cast<PHINode>(VMap[PHIToResolve[Idx]])) | |
1a4d82fc | 566 | recursivelySimplifyInstruction(PN, DL); |
223e47cc LB |
567 | |
568 | // Now that the inlined function body has been fully constructed, go through | |
569 | // and zap unconditional fall-through branches. This happen all the time when | |
570 | // specializing code: code specialization turns conditional branches into | |
571 | // uncond branches, and this code folds them. | |
572 | Function::iterator Begin = cast<BasicBlock>(VMap[&OldFunc->getEntryBlock()]); | |
573 | Function::iterator I = Begin; | |
574 | while (I != NewFunc->end()) { | |
575 | // Check if this block has become dead during inlining or other | |
576 | // simplifications. Note that the first block will appear dead, as it has | |
577 | // not yet been wired up properly. | |
578 | if (I != Begin && (pred_begin(I) == pred_end(I) || | |
579 | I->getSinglePredecessor() == I)) { | |
580 | BasicBlock *DeadBB = I++; | |
581 | DeleteDeadBlock(DeadBB); | |
582 | continue; | |
583 | } | |
584 | ||
585 | // We need to simplify conditional branches and switches with a constant | |
586 | // operand. We try to prune these out when cloning, but if the | |
587 | // simplification required looking through PHI nodes, those are only | |
588 | // available after forming the full basic block. That may leave some here, | |
589 | // and we still want to prune the dead code as early as possible. | |
590 | ConstantFoldTerminator(I); | |
591 | ||
592 | BranchInst *BI = dyn_cast<BranchInst>(I->getTerminator()); | |
593 | if (!BI || BI->isConditional()) { ++I; continue; } | |
594 | ||
595 | BasicBlock *Dest = BI->getSuccessor(0); | |
596 | if (!Dest->getSinglePredecessor()) { | |
597 | ++I; continue; | |
598 | } | |
599 | ||
600 | // We shouldn't be able to get single-entry PHI nodes here, as instsimplify | |
601 | // above should have zapped all of them.. | |
602 | assert(!isa<PHINode>(Dest->begin())); | |
603 | ||
604 | // We know all single-entry PHI nodes in the inlined function have been | |
605 | // removed, so we just need to splice the blocks. | |
606 | BI->eraseFromParent(); | |
607 | ||
608 | // Make all PHI nodes that referred to Dest now refer to I as their source. | |
609 | Dest->replaceAllUsesWith(I); | |
610 | ||
611 | // Move all the instructions in the succ to the pred. | |
612 | I->getInstList().splice(I->end(), Dest->getInstList()); | |
613 | ||
614 | // Remove the dest block. | |
615 | Dest->eraseFromParent(); | |
616 | ||
617 | // Do not increment I, iteratively merge all things this block branches to. | |
618 | } | |
619 | ||
620 | // Make a final pass over the basic blocks from theh old function to gather | |
621 | // any return instructions which survived folding. We have to do this here | |
622 | // because we can iteratively remove and merge returns above. | |
623 | for (Function::iterator I = cast<BasicBlock>(VMap[&OldFunc->getEntryBlock()]), | |
624 | E = NewFunc->end(); | |
625 | I != E; ++I) | |
626 | if (ReturnInst *RI = dyn_cast<ReturnInst>(I->getTerminator())) | |
627 | Returns.push_back(RI); | |
628 | } |