/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/Utils/CloneFunction.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===- CloneFunction.cpp - Clone a function into another function ---------===// |
2 | | // |
3 | | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | | // See https://llvm.org/LICENSE.txt for license information. |
5 | | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | | // |
7 | | //===----------------------------------------------------------------------===// |
8 | | // |
9 | | // This file implements the CloneFunctionInto interface, which is used as the |
10 | | // low-level function cloner. This is used by the CloneFunction and function |
11 | | // inliner to do the dirty work of copying the body of a function around. |
12 | | // |
13 | | //===----------------------------------------------------------------------===// |
14 | | |
15 | | #include "llvm/ADT/SetVector.h" |
16 | | #include "llvm/ADT/SmallVector.h" |
17 | | #include "llvm/Analysis/ConstantFolding.h" |
18 | | #include "llvm/Analysis/DomTreeUpdater.h" |
19 | | #include "llvm/Analysis/InstructionSimplify.h" |
20 | | #include "llvm/Analysis/LoopInfo.h" |
21 | | #include "llvm/IR/CFG.h" |
22 | | #include "llvm/IR/Constants.h" |
23 | | #include "llvm/IR/DebugInfo.h" |
24 | | #include "llvm/IR/DerivedTypes.h" |
25 | | #include "llvm/IR/Function.h" |
26 | | #include "llvm/IR/GlobalVariable.h" |
27 | | #include "llvm/IR/Instructions.h" |
28 | | #include "llvm/IR/IntrinsicInst.h" |
29 | | #include "llvm/IR/LLVMContext.h" |
30 | | #include "llvm/IR/Metadata.h" |
31 | | #include "llvm/IR/Module.h" |
32 | | #include "llvm/Transforms/Utils/BasicBlockUtils.h" |
33 | | #include "llvm/Transforms/Utils/Cloning.h" |
34 | | #include "llvm/Transforms/Utils/Local.h" |
35 | | #include "llvm/Transforms/Utils/ValueMapper.h" |
36 | | #include <map> |
37 | | using namespace llvm; |
38 | | |
39 | | /// See comments in Cloning.h. |
40 | | BasicBlock *llvm::CloneBasicBlock(const BasicBlock *BB, ValueToValueMapTy &VMap, |
41 | | const Twine &NameSuffix, Function *F, |
42 | | ClonedCodeInfo *CodeInfo, |
43 | 347k | DebugInfoFinder *DIFinder) { |
44 | 347k | DenseMap<const MDNode *, MDNode *> Cache; |
45 | 347k | BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), "", F); |
46 | 347k | if (BB->hasName()) |
47 | 144k | NewBB->setName(BB->getName() + NameSuffix); |
48 | 347k | |
49 | 347k | bool hasCalls = false, hasDynamicAllocas = false, hasStaticAllocas = false; |
50 | 347k | Module *TheModule = F ? F->getParent()67.6k : nullptr280k ; |
51 | 347k | |
52 | 347k | // Loop over all instructions, and copy them over. |
53 | 2.32M | for (const Instruction &I : *BB) { |
54 | 2.32M | if (DIFinder && TheModule5.40k ) |
55 | 5.40k | DIFinder->processInstruction(*TheModule, I); |
56 | 2.32M | |
57 | 2.32M | Instruction *NewInst = I.clone(); |
58 | 2.32M | if (I.hasName()) |
59 | 468k | NewInst->setName(I.getName() + NameSuffix); |
60 | 2.32M | NewBB->getInstList().push_back(NewInst); |
61 | 2.32M | VMap[&I] = NewInst; // Add instruction map to value. |
62 | 2.32M | |
63 | 2.32M | hasCalls |= (isa<CallInst>(I) && !isa<DbgInfoIntrinsic>(I)46.0k ); |
64 | 2.32M | if (const AllocaInst *AI = dyn_cast<AllocaInst>(&I)) { |
65 | 101 | if (isa<ConstantInt>(AI->getArraySize())) |
66 | 87 | hasStaticAllocas = true; |
67 | 14 | else |
68 | 14 | hasDynamicAllocas = true; |
69 | 101 | } |
70 | 2.32M | } |
71 | 347k | |
72 | 347k | if (CodeInfo) { |
73 | 0 | CodeInfo->ContainsCalls |= hasCalls; |
74 | 0 | CodeInfo->ContainsDynamicAllocas |= hasDynamicAllocas; |
75 | 0 | CodeInfo->ContainsDynamicAllocas |= hasStaticAllocas && |
76 | 0 | BB != &BB->getParent()->getEntryBlock(); |
77 | 0 | } |
78 | 347k | return NewBB; |
79 | 347k | } |
80 | | |
81 | | // Clone OldFunc into NewFunc, transforming the old arguments into references to |
82 | | // VMap values. |
83 | | // |
84 | | void llvm::CloneFunctionInto(Function *NewFunc, const Function *OldFunc, |
85 | | ValueToValueMapTy &VMap, |
86 | | bool ModuleLevelChanges, |
87 | | SmallVectorImpl<ReturnInst*> &Returns, |
88 | | const char *NameSuffix, ClonedCodeInfo *CodeInfo, |
89 | | ValueMapTypeRemapper *TypeMapper, |
90 | 519 | ValueMaterializer *Materializer) { |
91 | 519 | assert(NameSuffix && "NameSuffix cannot be null!"); |
92 | 519 | |
93 | | #ifndef NDEBUG |
94 | | for (const Argument &I : OldFunc->args()) |
95 | | assert(VMap.count(&I) && "No mapping from source argument specified!"); |
96 | | #endif |
97 | | |
98 | 519 | // Copy all attributes other than those stored in the AttributeList. We need |
99 | 519 | // to remap the parameter indices of the AttributeList. |
100 | 519 | AttributeList NewAttrs = NewFunc->getAttributes(); |
101 | 519 | NewFunc->copyAttributesFrom(OldFunc); |
102 | 519 | NewFunc->setAttributes(NewAttrs); |
103 | 519 | |
104 | 519 | // Fix up the personality function that got copied over. |
105 | 519 | if (OldFunc->hasPersonalityFn()) |
106 | 41 | NewFunc->setPersonalityFn( |
107 | 41 | MapValue(OldFunc->getPersonalityFn(), VMap, |
108 | 41 | ModuleLevelChanges ? RF_None35 : RF_NoModuleLevelChanges6 , |
109 | 41 | TypeMapper, Materializer)); |
110 | 519 | |
111 | 519 | SmallVector<AttributeSet, 4> NewArgAttrs(NewFunc->arg_size()); |
112 | 519 | AttributeList OldAttrs = OldFunc->getAttributes(); |
113 | 519 | |
114 | 519 | // Clone any argument attributes that are present in the VMap. |
115 | 519 | for (const Argument &OldArg : OldFunc->args()) { |
116 | 422 | if (Argument *NewArg = dyn_cast<Argument>(VMap[&OldArg])) { |
117 | 340 | NewArgAttrs[NewArg->getArgNo()] = |
118 | 340 | OldAttrs.getParamAttributes(OldArg.getArgNo()); |
119 | 340 | } |
120 | 422 | } |
121 | 519 | |
122 | 519 | NewFunc->setAttributes( |
123 | 519 | AttributeList::get(NewFunc->getContext(), OldAttrs.getFnAttributes(), |
124 | 519 | OldAttrs.getRetAttributes(), NewArgAttrs)); |
125 | 519 | |
126 | 519 | bool MustCloneSP = |
127 | 519 | OldFunc->getParent() && OldFunc->getParent() == NewFunc->getParent()517 ; |
128 | 519 | DISubprogram *SP = OldFunc->getSubprogram(); |
129 | 519 | if (SP) { |
130 | 54 | assert(!MustCloneSP || ModuleLevelChanges); |
131 | 54 | // Add mappings for some DebugInfo nodes that we don't want duplicated |
132 | 54 | // even if they're distinct. |
133 | 54 | auto &MD = VMap.MD(); |
134 | 54 | MD[SP->getUnit()].reset(SP->getUnit()); |
135 | 54 | MD[SP->getType()].reset(SP->getType()); |
136 | 54 | MD[SP->getFile()].reset(SP->getFile()); |
137 | 54 | // If we're not cloning into the same module, no need to clone the |
138 | 54 | // subprogram |
139 | 54 | if (!MustCloneSP) |
140 | 29 | MD[SP].reset(SP); |
141 | 54 | } |
142 | 519 | |
143 | 519 | SmallVector<std::pair<unsigned, MDNode *>, 1> MDs; |
144 | 519 | OldFunc->getAllMetadata(MDs); |
145 | 519 | for (auto MD : MDs) { |
146 | 63 | NewFunc->addMetadata( |
147 | 63 | MD.first, |
148 | 63 | *MapMetadata(MD.second, VMap, |
149 | 63 | ModuleLevelChanges ? RF_None54 : RF_NoModuleLevelChanges9 , |
150 | 63 | TypeMapper, Materializer)); |
151 | 63 | } |
152 | 519 | |
153 | 519 | // When we remap instructions, we want to avoid duplicating inlined |
154 | 519 | // DISubprograms, so record all subprograms we find as we duplicate |
155 | 519 | // instructions and then freeze them in the MD map. |
156 | 519 | // We also record information about dbg.value and dbg.declare to avoid |
157 | 519 | // duplicating the types. |
158 | 519 | DebugInfoFinder DIFinder; |
159 | 519 | |
160 | 519 | // Loop over all of the basic blocks in the function, cloning them as |
161 | 519 | // appropriate. Note that we save BE this way in order to handle cloning of |
162 | 519 | // recursive functions into themselves. |
163 | 519 | // |
164 | 519 | for (Function::const_iterator BI = OldFunc->begin(), BE = OldFunc->end(); |
165 | 3.22k | BI != BE; ++BI2.70k ) { |
166 | 2.70k | const BasicBlock &BB = *BI; |
167 | 2.70k | |
168 | 2.70k | // Create a new basic block and copy instructions into it! |
169 | 2.70k | BasicBlock *CBB = CloneBasicBlock(&BB, VMap, NameSuffix, NewFunc, CodeInfo, |
170 | 2.70k | ModuleLevelChanges ? &DIFinder2.27k : nullptr433 ); |
171 | 2.70k | |
172 | 2.70k | // Add basic block mapping. |
173 | 2.70k | VMap[&BB] = CBB; |
174 | 2.70k | |
175 | 2.70k | // It is only legal to clone a function if a block address within that |
176 | 2.70k | // function is never referenced outside of the function. Given that, we |
177 | 2.70k | // want to map block addresses from the old function to block addresses in |
178 | 2.70k | // the clone. (This is different from the generic ValueMapper |
179 | 2.70k | // implementation, which generates an invalid blockaddress when |
180 | 2.70k | // cloning a function.) |
181 | 2.70k | if (BB.hasAddressTaken()) { |
182 | 2 | Constant *OldBBAddr = BlockAddress::get(const_cast<Function*>(OldFunc), |
183 | 2 | const_cast<BasicBlock*>(&BB)); |
184 | 2 | VMap[OldBBAddr] = BlockAddress::get(NewFunc, CBB); |
185 | 2 | } |
186 | 2.70k | |
187 | 2.70k | // Note return instructions for the caller. |
188 | 2.70k | if (ReturnInst *RI = dyn_cast<ReturnInst>(CBB->getTerminator())) |
189 | 523 | Returns.push_back(RI); |
190 | 2.70k | } |
191 | 519 | |
192 | 519 | for (DISubprogram *ISP : DIFinder.subprograms()) |
193 | 64 | if (ISP != SP) |
194 | 40 | VMap.MD()[ISP].reset(ISP); |
195 | 519 | |
196 | 519 | for (DICompileUnit *CU : DIFinder.compile_units()) |
197 | 57 | VMap.MD()[CU].reset(CU); |
198 | 519 | |
199 | 519 | for (DIType *Type : DIFinder.types()) |
200 | 115 | VMap.MD()[Type].reset(Type); |
201 | 519 | |
202 | 519 | // Loop over all of the instructions in the function, fixing up operand |
203 | 519 | // references as we go. This uses VMap to do all the hard work. |
204 | 519 | for (Function::iterator BB = |
205 | 519 | cast<BasicBlock>(VMap[&OldFunc->front()])->getIterator(), |
206 | 519 | BE = NewFunc->end(); |
207 | 3.22k | BB != BE; ++BB2.70k ) |
208 | 2.70k | // Loop over all instructions, fixing each one as we find it... |
209 | 2.70k | for (Instruction &II : *BB) |
210 | 6.84k | RemapInstruction(&II, VMap, |
211 | 6.84k | ModuleLevelChanges ? RF_None5.40k : RF_NoModuleLevelChanges1.43k , |
212 | 6.84k | TypeMapper, Materializer); |
213 | 519 | } |
214 | | |
215 | | /// Return a copy of the specified function and add it to that function's |
216 | | /// module. Also, any references specified in the VMap are changed to refer to |
217 | | /// their mapped value instead of the original one. If any of the arguments to |
218 | | /// the function are in the VMap, the arguments are deleted from the resultant |
219 | | /// function. The VMap is updated to include mappings from all of the |
220 | | /// instructions and basicblocks in the function from their old to new values. |
221 | | /// |
222 | | Function *llvm::CloneFunction(Function *F, ValueToValueMapTy &VMap, |
223 | 136 | ClonedCodeInfo *CodeInfo) { |
224 | 136 | std::vector<Type*> ArgTypes; |
225 | 136 | |
226 | 136 | // The user might be deleting arguments to the function by specifying them in |
227 | 136 | // the VMap. If so, we need to not add the arguments to the arg ty vector |
228 | 136 | // |
229 | 136 | for (const Argument &I : F->args()) |
230 | 114 | if (VMap.count(&I) == 0) // Haven't mapped the argument to anything yet? |
231 | 114 | ArgTypes.push_back(I.getType()); |
232 | 136 | |
233 | 136 | // Create a new function type... |
234 | 136 | FunctionType *FTy = FunctionType::get(F->getFunctionType()->getReturnType(), |
235 | 136 | ArgTypes, F->getFunctionType()->isVarArg()); |
236 | 136 | |
237 | 136 | // Create the new function... |
238 | 136 | Function *NewF = Function::Create(FTy, F->getLinkage(), F->getAddressSpace(), |
239 | 136 | F->getName(), F->getParent()); |
240 | 136 | |
241 | 136 | // Loop over the arguments, copying the names of the mapped arguments over... |
242 | 136 | Function::arg_iterator DestI = NewF->arg_begin(); |
243 | 136 | for (const Argument & I : F->args()) |
244 | 114 | if (VMap.count(&I) == 0) { // Is this argument preserved? |
245 | 114 | DestI->setName(I.getName()); // Copy the name over... |
246 | 114 | VMap[&I] = &*DestI++; // Add mapping to VMap |
247 | 114 | } |
248 | 136 | |
249 | 136 | SmallVector<ReturnInst*, 8> Returns; // Ignore returns cloned. |
250 | 136 | CloneFunctionInto(NewF, F, VMap, F->getSubprogram() != nullptr, Returns, "", |
251 | 136 | CodeInfo); |
252 | 136 | |
253 | 136 | return NewF; |
254 | 136 | } |
255 | | |
256 | | |
257 | | |
258 | | namespace { |
259 | | /// This is a private class used to implement CloneAndPruneFunctionInto. |
260 | | struct PruningFunctionCloner { |
261 | | Function *NewFunc; |
262 | | const Function *OldFunc; |
263 | | ValueToValueMapTy &VMap; |
264 | | bool ModuleLevelChanges; |
265 | | const char *NameSuffix; |
266 | | ClonedCodeInfo *CodeInfo; |
267 | | |
268 | | public: |
269 | | PruningFunctionCloner(Function *newFunc, const Function *oldFunc, |
270 | | ValueToValueMapTy &valueMap, bool moduleLevelChanges, |
271 | | const char *nameSuffix, ClonedCodeInfo *codeInfo) |
272 | | : NewFunc(newFunc), OldFunc(oldFunc), VMap(valueMap), |
273 | | ModuleLevelChanges(moduleLevelChanges), NameSuffix(nameSuffix), |
274 | 541k | CodeInfo(codeInfo) {} |
275 | | |
276 | | /// The specified block is found to be reachable, clone it and |
277 | | /// anything that it can reach. |
278 | | void CloneBlock(const BasicBlock *BB, |
279 | | BasicBlock::const_iterator StartingInst, |
280 | | std::vector<const BasicBlock*> &ToClone); |
281 | | }; |
282 | | } |
283 | | |
284 | | /// The specified block is found to be reachable, clone it and |
285 | | /// anything that it can reach. |
286 | | void PruningFunctionCloner::CloneBlock(const BasicBlock *BB, |
287 | | BasicBlock::const_iterator StartingInst, |
288 | 1.55M | std::vector<const BasicBlock*> &ToClone){ |
289 | 1.55M | WeakTrackingVH &BBEntry = VMap[BB]; |
290 | 1.55M | |
291 | 1.55M | // Have we already cloned this block? |
292 | 1.55M | if (BBEntry) return336k ; |
293 | 1.21M | |
294 | 1.21M | // Nope, clone it now. |
295 | 1.21M | BasicBlock *NewBB; |
296 | 1.21M | BBEntry = NewBB = BasicBlock::Create(BB->getContext()); |
297 | 1.21M | if (BB->hasName()) NewBB->setName(BB->getName()+NameSuffix)34.4k ; |
298 | 1.21M | |
299 | 1.21M | // It is only legal to clone a function if a block address within that |
300 | 1.21M | // function is never referenced outside of the function. Given that, we |
301 | 1.21M | // want to map block addresses from the old function to block addresses in |
302 | 1.21M | // the clone. (This is different from the generic ValueMapper |
303 | 1.21M | // implementation, which generates an invalid blockaddress when |
304 | 1.21M | // cloning a function.) |
305 | 1.21M | // |
306 | 1.21M | // Note that we don't need to fix the mapping for unreachable blocks; |
307 | 1.21M | // the default mapping there is safe. |
308 | 1.21M | if (BB->hasAddressTaken()) { |
309 | 4 | Constant *OldBBAddr = BlockAddress::get(const_cast<Function*>(OldFunc), |
310 | 4 | const_cast<BasicBlock*>(BB)); |
311 | 4 | VMap[OldBBAddr] = BlockAddress::get(NewFunc, NewBB); |
312 | 4 | } |
313 | 1.21M | |
314 | 1.21M | bool hasCalls = false, hasDynamicAllocas = false, hasStaticAllocas = false; |
315 | 1.21M | |
316 | 1.21M | // Loop over all instructions, and copy them over, DCE'ing as we go. This |
317 | 1.21M | // loop doesn't include the terminator. |
318 | 1.21M | for (BasicBlock::const_iterator II = StartingInst, IE = --BB->end(); |
319 | 6.14M | II != IE; ++II4.92M ) { |
320 | 4.92M | |
321 | 4.92M | Instruction *NewInst = II->clone(); |
322 | 4.92M | |
323 | 4.92M | // Eagerly remap operands to the newly cloned instruction, except for PHI |
324 | 4.92M | // nodes for which we defer processing until we update the CFG. |
325 | 4.92M | if (!isa<PHINode>(NewInst)) { |
326 | 4.74M | RemapInstruction(NewInst, VMap, |
327 | 4.74M | ModuleLevelChanges ? RF_None0 : RF_NoModuleLevelChanges); |
328 | 4.74M | |
329 | 4.74M | // If we can simplify this instruction to some other value, simply add |
330 | 4.74M | // a mapping to that value rather than inserting a new instruction into |
331 | 4.74M | // the basic block. |
332 | 4.74M | if (Value *V = |
333 | 119k | SimplifyInstruction(NewInst, BB->getModule()->getDataLayout())) { |
334 | 119k | // On the off-chance that this simplifies to an instruction in the old |
335 | 119k | // function, map it back into the new function. |
336 | 119k | if (NewFunc != OldFunc) |
337 | 119k | if (Value *MappedV = VMap.lookup(V)) |
338 | 9.10k | V = MappedV; |
339 | 119k | |
340 | 119k | if (!NewInst->mayHaveSideEffects()) { |
341 | 119k | VMap[&*II] = V; |
342 | 119k | NewInst->deleteValue(); |
343 | 119k | continue; |
344 | 119k | } |
345 | 4.80M | } |
346 | 4.74M | } |
347 | 4.80M | |
348 | 4.80M | if (II->hasName()) |
349 | 149k | NewInst->setName(II->getName()+NameSuffix); |
350 | 4.80M | VMap[&*II] = NewInst; // Add instruction map to value. |
351 | 4.80M | NewBB->getInstList().push_back(NewInst); |
352 | 4.80M | hasCalls |= (isa<CallInst>(II) && !isa<DbgInfoIntrinsic>(II)419k ); |
353 | 4.80M | |
354 | 4.80M | if (CodeInfo) |
355 | 4.80M | if (auto CS = ImmutableCallSite(&*II)) |
356 | 419k | if (CS.hasOperandBundles()) |
357 | 51 | CodeInfo->OperandBundleCallSites.push_back(NewInst); |
358 | 4.80M | |
359 | 4.80M | if (const AllocaInst *AI = dyn_cast<AllocaInst>(II)) { |
360 | 103k | if (isa<ConstantInt>(AI->getArraySize())) |
361 | 103k | hasStaticAllocas = true; |
362 | 17 | else |
363 | 17 | hasDynamicAllocas = true; |
364 | 103k | } |
365 | 4.80M | } |
366 | 1.21M | |
367 | 1.21M | // Finally, clone over the terminator. |
368 | 1.21M | const Instruction *OldTI = BB->getTerminator(); |
369 | 1.21M | bool TerminatorDone = false; |
370 | 1.21M | if (const BranchInst *BI = dyn_cast<BranchInst>(OldTI)) { |
371 | 611k | if (BI->isConditional()) { |
372 | 363k | // If the condition was a known constant in the callee... |
373 | 363k | ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition()); |
374 | 363k | // Or is a known constant in the caller... |
375 | 363k | if (!Cond) { |
376 | 363k | Value *V = VMap.lookup(BI->getCondition()); |
377 | 363k | Cond = dyn_cast_or_null<ConstantInt>(V); |
378 | 363k | } |
379 | 363k | |
380 | 363k | // Constant fold to uncond branch! |
381 | 363k | if (Cond) { |
382 | 21.9k | BasicBlock *Dest = BI->getSuccessor(!Cond->getZExtValue()); |
383 | 21.9k | VMap[OldTI] = BranchInst::Create(Dest, NewBB); |
384 | 21.9k | ToClone.push_back(Dest); |
385 | 21.9k | TerminatorDone = true; |
386 | 21.9k | } |
387 | 363k | } |
388 | 611k | } else if (const SwitchInst *606k SI606k = dyn_cast<SwitchInst>(OldTI)) { |
389 | 19.8k | // If switching on a value known constant in the caller. |
390 | 19.8k | ConstantInt *Cond = dyn_cast<ConstantInt>(SI->getCondition()); |
391 | 19.8k | if (!Cond) { // Or known constant after constant prop in the callee... |
392 | 19.8k | Value *V = VMap.lookup(SI->getCondition()); |
393 | 19.8k | Cond = dyn_cast_or_null<ConstantInt>(V); |
394 | 19.8k | } |
395 | 19.8k | if (Cond) { // Constant fold to uncond branch! |
396 | 16.1k | SwitchInst::ConstCaseHandle Case = *SI->findCaseValue(Cond); |
397 | 16.1k | BasicBlock *Dest = const_cast<BasicBlock*>(Case.getCaseSuccessor()); |
398 | 16.1k | VMap[OldTI] = BranchInst::Create(Dest, NewBB); |
399 | 16.1k | ToClone.push_back(Dest); |
400 | 16.1k | TerminatorDone = true; |
401 | 16.1k | } |
402 | 19.8k | } |
403 | 1.21M | |
404 | 1.21M | if (!TerminatorDone) { |
405 | 1.17M | Instruction *NewInst = OldTI->clone(); |
406 | 1.17M | if (OldTI->hasName()) |
407 | 22 | NewInst->setName(OldTI->getName()+NameSuffix); |
408 | 1.17M | NewBB->getInstList().push_back(NewInst); |
409 | 1.17M | VMap[OldTI] = NewInst; // Add instruction map to value. |
410 | 1.17M | |
411 | 1.17M | if (CodeInfo) |
412 | 1.17M | if (auto CS = ImmutableCallSite(OldTI)) |
413 | 12.0k | if (CS.hasOperandBundles()) |
414 | 46 | CodeInfo->OperandBundleCallSites.push_back(NewInst); |
415 | 1.17M | |
416 | 1.17M | // Recursively clone any reachable successor blocks. |
417 | 1.17M | const Instruction *TI = BB->getTerminator(); |
418 | 1.17M | for (const BasicBlock *Succ : successors(TI)) |
419 | 975k | ToClone.push_back(Succ); |
420 | 1.17M | } |
421 | 1.21M | |
422 | 1.21M | if (CodeInfo) { |
423 | 1.21M | CodeInfo->ContainsCalls |= hasCalls; |
424 | 1.21M | CodeInfo->ContainsDynamicAllocas |= hasDynamicAllocas; |
425 | 1.21M | CodeInfo->ContainsDynamicAllocas |= hasStaticAllocas && |
426 | 1.21M | BB != &BB->getParent()->front()34.4k ; |
427 | 1.21M | } |
428 | 1.21M | } |
429 | | |
430 | | /// This works like CloneAndPruneFunctionInto, except that it does not clone the |
431 | | /// entire function. Instead it starts at an instruction provided by the caller |
432 | | /// and copies (and prunes) only the code reachable from that instruction. |
433 | | void llvm::CloneAndPruneIntoFromInst(Function *NewFunc, const Function *OldFunc, |
434 | | const Instruction *StartingInst, |
435 | | ValueToValueMapTy &VMap, |
436 | | bool ModuleLevelChanges, |
437 | | SmallVectorImpl<ReturnInst *> &Returns, |
438 | | const char *NameSuffix, |
439 | 541k | ClonedCodeInfo *CodeInfo) { |
440 | 541k | assert(NameSuffix && "NameSuffix cannot be null!"); |
441 | 541k | |
442 | 541k | ValueMapTypeRemapper *TypeMapper = nullptr; |
443 | 541k | ValueMaterializer *Materializer = nullptr; |
444 | 541k | |
445 | | #ifndef NDEBUG |
446 | | // If the cloning starts at the beginning of the function, verify that |
447 | | // the function arguments are mapped. |
448 | | if (!StartingInst) |
449 | | for (const Argument &II : OldFunc->args()) |
450 | | assert(VMap.count(&II) && "No mapping from source argument specified!"); |
451 | | #endif |
452 | | |
453 | 541k | PruningFunctionCloner PFC(NewFunc, OldFunc, VMap, ModuleLevelChanges, |
454 | 541k | NameSuffix, CodeInfo); |
455 | 541k | const BasicBlock *StartingBB; |
456 | 541k | if (StartingInst) |
457 | 541k | StartingBB = StartingInst->getParent(); |
458 | 1 | else { |
459 | 1 | StartingBB = &OldFunc->getEntryBlock(); |
460 | 1 | StartingInst = &StartingBB->front(); |
461 | 1 | } |
462 | 541k | |
463 | 541k | // Clone the entry block, and anything recursively reachable from it. |
464 | 541k | std::vector<const BasicBlock*> CloneWorklist; |
465 | 541k | PFC.CloneBlock(StartingBB, StartingInst->getIterator(), CloneWorklist); |
466 | 1.55M | while (!CloneWorklist.empty()) { |
467 | 1.01M | const BasicBlock *BB = CloneWorklist.back(); |
468 | 1.01M | CloneWorklist.pop_back(); |
469 | 1.01M | PFC.CloneBlock(BB, BB->begin(), CloneWorklist); |
470 | 1.01M | } |
471 | 541k | |
472 | 541k | // Loop over all of the basic blocks in the old function. If the block was |
473 | 541k | // reachable, we have cloned it and the old block is now in the value map: |
474 | 541k | // insert it into the new function in the right order. If not, ignore it. |
475 | 541k | // |
476 | 541k | // Defer PHI resolution until rest of function is resolved. |
477 | 541k | SmallVector<const PHINode*, 16> PHIToResolve; |
478 | 1.33M | for (const BasicBlock &BI : *OldFunc) { |
479 | 1.33M | Value *V = VMap.lookup(&BI); |
480 | 1.33M | BasicBlock *NewBB = cast_or_null<BasicBlock>(V); |
481 | 1.33M | if (!NewBB) continue118k ; // Dead block. |
482 | 1.21M | |
483 | 1.21M | // Add the new block to the new function. |
484 | 1.21M | NewFunc->getBasicBlockList().push_back(NewBB); |
485 | 1.21M | |
486 | 1.21M | // Handle PHI nodes specially, as we have to remove references to dead |
487 | 1.21M | // blocks. |
488 | 1.21M | for (const PHINode &PN : BI.phis()) { |
489 | 180k | // PHI nodes may have been remapped to non-PHI nodes by the caller or |
490 | 180k | // during the cloning process. |
491 | 180k | if (isa<PHINode>(VMap[&PN])) |
492 | 180k | PHIToResolve.push_back(&PN); |
493 | 0 | else |
494 | 0 | break; |
495 | 180k | } |
496 | 1.21M | |
497 | 1.21M | // Finally, remap the terminator instructions, as those can't be remapped |
498 | 1.21M | // until all BBs are mapped. |
499 | 1.21M | RemapInstruction(NewBB->getTerminator(), VMap, |
500 | 1.21M | ModuleLevelChanges ? RF_None0 : RF_NoModuleLevelChanges, |
501 | 1.21M | TypeMapper, Materializer); |
502 | 1.21M | } |
503 | 541k | |
504 | 541k | // Defer PHI resolution until rest of function is resolved, PHI resolution |
505 | 541k | // requires the CFG to be up-to-date. |
506 | 675k | for (unsigned phino = 0, e = PHIToResolve.size(); phino != e; ) { |
507 | 134k | const PHINode *OPN = PHIToResolve[phino]; |
508 | 134k | unsigned NumPreds = OPN->getNumIncomingValues(); |
509 | 134k | const BasicBlock *OldBB = OPN->getParent(); |
510 | 134k | BasicBlock *NewBB = cast<BasicBlock>(VMap[OldBB]); |
511 | 134k | |
512 | 134k | // Map operands for blocks that are live and remove operands for blocks |
513 | 134k | // that are dead. |
514 | 314k | for (; phino != PHIToResolve.size() && |
515 | 314k | PHIToResolve[phino]->getParent() == OldBB232k ; ++phino180k ) { |
516 | 180k | OPN = PHIToResolve[phino]; |
517 | 180k | PHINode *PN = cast<PHINode>(VMap[OPN]); |
518 | 628k | for (unsigned pred = 0, e = NumPreds; pred != e; ++pred447k ) { |
519 | 447k | Value *V = VMap.lookup(PN->getIncomingBlock(pred)); |
520 | 447k | if (BasicBlock *MappedBlock = cast_or_null<BasicBlock>(V)) { |
521 | 414k | Value *InVal = MapValue(PN->getIncomingValue(pred), |
522 | 414k | VMap, |
523 | 414k | ModuleLevelChanges ? RF_None0 : RF_NoModuleLevelChanges); |
524 | 414k | assert(InVal && "Unknown input value?"); |
525 | 414k | PN->setIncomingValue(pred, InVal); |
526 | 414k | PN->setIncomingBlock(pred, MappedBlock); |
527 | 414k | } else { |
528 | 33.4k | PN->removeIncomingValue(pred, false); |
529 | 33.4k | --pred; // Revisit the next entry. |
530 | 33.4k | --e; |
531 | 33.4k | } |
532 | 447k | } |
533 | 180k | } |
534 | 134k | |
535 | 134k | // The loop above has removed PHI entries for those blocks that are dead |
536 | 134k | // and has updated others. However, if a block is live (i.e. copied over) |
537 | 134k | // but its terminator has been changed to not go to this block, then our |
538 | 134k | // phi nodes will have invalid entries. Update the PHI nodes in this |
539 | 134k | // case. |
540 | 134k | PHINode *PN = cast<PHINode>(NewBB->begin()); |
541 | 134k | NumPreds = pred_size(NewBB); |
542 | 134k | if (NumPreds != PN->getNumIncomingValues()) { |
543 | 2.60k | assert(NumPreds < PN->getNumIncomingValues()); |
544 | 2.60k | // Count how many times each predecessor comes to this block. |
545 | 2.60k | std::map<BasicBlock*, unsigned> PredCount; |
546 | 2.60k | for (pred_iterator PI = pred_begin(NewBB), E = pred_end(NewBB); |
547 | 7.78k | PI != E; ++PI5.18k ) |
548 | 5.18k | --PredCount[*PI]; |
549 | 2.60k | |
550 | 2.60k | // Figure out how many entries to remove from each PHI. |
551 | 10.5k | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i7.96k ) |
552 | 7.96k | ++PredCount[PN->getIncomingBlock(i)]; |
553 | 2.60k | |
554 | 2.60k | // At this point, the excess predecessor entries are positive in the |
555 | 2.60k | // map. Loop over all of the PHIs and remove excess predecessor |
556 | 2.60k | // entries. |
557 | 2.60k | BasicBlock::iterator I = NewBB->begin(); |
558 | 5.33k | for (; (PN = dyn_cast<PHINode>(I)); ++I2.73k ) { |
559 | 8.46k | for (const auto &PCI : PredCount) { |
560 | 8.46k | BasicBlock *Pred = PCI.first; |
561 | 11.4k | for (unsigned NumToRemove = PCI.second; NumToRemove; --NumToRemove2.93k ) |
562 | 2.93k | PN->removeIncomingValue(Pred, false); |
563 | 8.46k | } |
564 | 2.73k | } |
565 | 2.60k | } |
566 | 134k | |
567 | 134k | // If the loops above have made these phi nodes have 0 or 1 operand, |
568 | 134k | // replace them with undef or the input value. We must do this for |
569 | 134k | // correctness, because 0-operand phis are not valid. |
570 | 134k | PN = cast<PHINode>(NewBB->begin()); |
571 | 134k | if (PN->getNumIncomingValues() == 0) { |
572 | 0 | BasicBlock::iterator I = NewBB->begin(); |
573 | 0 | BasicBlock::const_iterator OldI = OldBB->begin(); |
574 | 0 | while ((PN = dyn_cast<PHINode>(I++))) { |
575 | 0 | Value *NV = UndefValue::get(PN->getType()); |
576 | 0 | PN->replaceAllUsesWith(NV); |
577 | 0 | assert(VMap[&*OldI] == PN && "VMap mismatch"); |
578 | 0 | VMap[&*OldI] = NV; |
579 | 0 | PN->eraseFromParent(); |
580 | 0 | ++OldI; |
581 | 0 | } |
582 | 0 | } |
583 | 134k | } |
584 | 541k | |
585 | 541k | // Make a second pass over the PHINodes now that all of them have been |
586 | 541k | // remapped into the new function, simplifying the PHINode and performing any |
587 | 541k | // recursive simplifications exposed. This will transparently update the |
588 | 541k | // WeakTrackingVH in the VMap. Notably, we rely on that so that if we coalesce |
589 | 541k | // two PHINodes, the iteration over the old PHIs remains valid, and the |
590 | 541k | // mapping will just map us to the new node (which may not even be a PHI |
591 | 541k | // node). |
592 | 541k | const DataLayout &DL = NewFunc->getParent()->getDataLayout(); |
593 | 541k | SmallSetVector<const Value *, 8> Worklist; |
594 | 721k | for (unsigned Idx = 0, Size = PHIToResolve.size(); Idx != Size; ++Idx180k ) |
595 | 180k | if (isa<PHINode>(VMap[PHIToResolve[Idx]])) |
596 | 180k | Worklist.insert(PHIToResolve[Idx]); |
597 | 541k | |
598 | 541k | // Note that we must test the size on each iteration, the worklist can grow. |
599 | 727k | for (unsigned Idx = 0; Idx != Worklist.size(); ++Idx186k ) { |
600 | 186k | const Value *OrigV = Worklist[Idx]; |
601 | 186k | auto *I = dyn_cast_or_null<Instruction>(VMap.lookup(OrigV)); |
602 | 186k | if (!I) |
603 | 253 | continue; |
604 | 186k | |
605 | 186k | // Skip over non-intrinsic callsites, we don't want to remove any nodes from |
606 | 186k | // the CGSCC. |
607 | 186k | CallSite CS = CallSite(I); |
608 | 186k | if (CS && CS.getCalledFunction()185 && !CS.getCalledFunction()->isIntrinsic()143 ) |
609 | 120 | continue; |
610 | 186k | |
611 | 186k | // See if this instruction simplifies. |
612 | 186k | Value *SimpleV = SimplifyInstruction(I, DL); |
613 | 186k | if (!SimpleV) |
614 | 181k | continue; |
615 | 5.34k | |
616 | 5.34k | // Stash away all the uses of the old instruction so we can check them for |
617 | 5.34k | // recursive simplifications after a RAUW. This is cheaper than checking all |
618 | 5.34k | // uses of To on the recursive step in most cases. |
619 | 5.34k | for (const User *U : OrigV->users()) |
620 | 7.18k | Worklist.insert(cast<Instruction>(U)); |
621 | 5.34k | |
622 | 5.34k | // Replace the instruction with its simplified value. |
623 | 5.34k | I->replaceAllUsesWith(SimpleV); |
624 | 5.34k | |
625 | 5.34k | // If the original instruction had no side effects, remove it. |
626 | 5.34k | if (isInstructionTriviallyDead(I)) |
627 | 5.34k | I->eraseFromParent(); |
628 | 0 | else |
629 | 0 | VMap[OrigV] = I; |
630 | 5.34k | } |
631 | 541k | |
632 | 541k | // Now that the inlined function body has been fully constructed, go through |
633 | 541k | // and zap unconditional fall-through branches. This happens all the time when |
634 | 541k | // specializing code: code specialization turns conditional branches into |
635 | 541k | // uncond branches, and this code folds them. |
636 | 541k | Function::iterator Begin = cast<BasicBlock>(VMap[StartingBB])->getIterator(); |
637 | 541k | Function::iterator I = Begin; |
638 | 1.75M | while (I != NewFunc->end()) { |
639 | 1.21M | // We need to simplify conditional branches and switches with a constant |
640 | 1.21M | // operand. We try to prune these out when cloning, but if the |
641 | 1.21M | // simplification required looking through PHI nodes, those are only |
642 | 1.21M | // available after forming the full basic block. That may leave some here, |
643 | 1.21M | // and we still want to prune the dead code as early as possible. |
644 | 1.21M | // |
645 | 1.21M | // Do the folding before we check if the block is dead since we want code |
646 | 1.21M | // like |
647 | 1.21M | // bb: |
648 | 1.21M | // br i1 undef, label %bb, label %bb |
649 | 1.21M | // to be simplified to |
650 | 1.21M | // bb: |
651 | 1.21M | // br label %bb |
652 | 1.21M | // before we call I->getSinglePredecessor(). |
653 | 1.21M | ConstantFoldTerminator(&*I); |
654 | 1.21M | |
655 | 1.21M | // Check if this block has become dead during inlining or other |
656 | 1.21M | // simplifications. Note that the first block will appear dead, as it has |
657 | 1.21M | // not yet been wired up properly. |
658 | 1.21M | if (I != Begin && (637k pred_begin(&*I) == pred_end(&*I)637k || |
659 | 637k | I->getSinglePredecessor() == &*I637k )) { |
660 | 44 | BasicBlock *DeadBB = &*I++; |
661 | 44 | DeleteDeadBlock(DeadBB); |
662 | 44 | continue; |
663 | 44 | } |
664 | 1.21M | |
665 | 1.21M | BranchInst *BI = dyn_cast<BranchInst>(I->getTerminator()); |
666 | 1.21M | if (!BI || BI->isConditional()627k ) { ++I; continue; }932k |
667 | 285k | |
668 | 285k | BasicBlock *Dest = BI->getSuccessor(0); |
669 | 285k | if (!Dest->getSinglePredecessor()) { |
670 | 242k | ++I; continue; |
671 | 242k | } |
672 | 43.6k | |
673 | 43.6k | // We shouldn't be able to get single-entry PHI nodes here, as instsimplify |
674 | 43.6k | // above should have zapped all of them.. |
675 | 43.6k | assert(!isa<PHINode>(Dest->begin())); |
676 | 43.6k | |
677 | 43.6k | // We know all single-entry PHI nodes in the inlined function have been |
678 | 43.6k | // removed, so we just need to splice the blocks. |
679 | 43.6k | BI->eraseFromParent(); |
680 | 43.6k | |
681 | 43.6k | // Make all PHI nodes that referred to Dest now refer to I as their source. |
682 | 43.6k | Dest->replaceAllUsesWith(&*I); |
683 | 43.6k | |
684 | 43.6k | // Move all the instructions in the succ to the pred. |
685 | 43.6k | I->getInstList().splice(I->end(), Dest->getInstList()); |
686 | 43.6k | |
687 | 43.6k | // Remove the dest block. |
688 | 43.6k | Dest->eraseFromParent(); |
689 | 43.6k | |
690 | 43.6k | // Do not increment I, iteratively merge all things this block branches to. |
691 | 43.6k | } |
692 | 541k | |
693 | 541k | // Make a final pass over the basic blocks from the old function to gather |
694 | 541k | // any return instructions which survived folding. We have to do this here |
695 | 541k | // because we can iteratively remove and merge returns above. |
696 | 541k | for (Function::iterator I = cast<BasicBlock>(VMap[StartingBB])->getIterator(), |
697 | 541k | E = NewFunc->end(); |
698 | 1.71M | I != E; ++I1.17M ) |
699 | 1.17M | if (ReturnInst *RI = dyn_cast<ReturnInst>(I->getTerminator())) |
700 | 541k | Returns.push_back(RI); |
701 | 541k | } |
702 | | |
703 | | |
704 | | /// This works exactly like CloneFunctionInto, |
705 | | /// except that it does some simple constant prop and DCE on the fly. The |
706 | | /// effect of this is to copy significantly less code in cases where (for |
707 | | /// example) a function call with constant arguments is inlined, and those |
708 | | /// constant arguments cause a significant amount of code in the callee to be |
709 | | /// dead. Since this doesn't produce an exact copy of the input, it can't be |
710 | | /// used for things like CloneFunction or CloneModule. |
711 | | void llvm::CloneAndPruneFunctionInto(Function *NewFunc, const Function *OldFunc, |
712 | | ValueToValueMapTy &VMap, |
713 | | bool ModuleLevelChanges, |
714 | | SmallVectorImpl<ReturnInst*> &Returns, |
715 | | const char *NameSuffix, |
716 | | ClonedCodeInfo *CodeInfo, |
717 | 541k | Instruction *TheCall) { |
718 | 541k | CloneAndPruneIntoFromInst(NewFunc, OldFunc, &OldFunc->front().front(), VMap, |
719 | 541k | ModuleLevelChanges, Returns, NameSuffix, CodeInfo); |
720 | 541k | } |
721 | | |
722 | | /// Remaps instructions in \p Blocks using the mapping in \p VMap. |
723 | | void llvm::remapInstructionsInBlocks( |
724 | 227 | const SmallVectorImpl<BasicBlock *> &Blocks, ValueToValueMapTy &VMap) { |
725 | 227 | // Rewrite the code to refer to itself. |
726 | 227 | for (auto *BB : Blocks) |
727 | 948 | for (auto &Inst : *BB) |
728 | 6.40k | RemapInstruction(&Inst, VMap, |
729 | 6.40k | RF_NoModuleLevelChanges | RF_IgnoreMissingLocals); |
730 | 227 | } |
731 | | |
732 | | /// Clones a loop \p OrigLoop. Returns the loop and the blocks in \p |
733 | | /// Blocks. |
734 | | /// |
735 | | /// Updates LoopInfo and DominatorTree assuming the loop is dominated by block |
736 | | /// \p LoopDomBB. Insert the new blocks before block specified in \p Before. |
737 | | Loop *llvm::cloneLoopWithPreheader(BasicBlock *Before, BasicBlock *LoopDomBB, |
738 | | Loop *OrigLoop, ValueToValueMapTy &VMap, |
739 | | const Twine &NameSuffix, LoopInfo *LI, |
740 | | DominatorTree *DT, |
741 | 75 | SmallVectorImpl<BasicBlock *> &Blocks) { |
742 | 75 | Function *F = OrigLoop->getHeader()->getParent(); |
743 | 75 | Loop *ParentLoop = OrigLoop->getParentLoop(); |
744 | 75 | DenseMap<Loop *, Loop *> LMap; |
745 | 75 | |
746 | 75 | Loop *NewLoop = LI->AllocateLoop(); |
747 | 75 | LMap[OrigLoop] = NewLoop; |
748 | 75 | if (ParentLoop) |
749 | 7 | ParentLoop->addChildLoop(NewLoop); |
750 | 68 | else |
751 | 68 | LI->addTopLevelLoop(NewLoop); |
752 | 75 | |
753 | 75 | BasicBlock *OrigPH = OrigLoop->getLoopPreheader(); |
754 | 75 | assert(OrigPH && "No preheader"); |
755 | 75 | BasicBlock *NewPH = CloneBasicBlock(OrigPH, VMap, NameSuffix, F); |
756 | 75 | // To rename the loop PHIs. |
757 | 75 | VMap[OrigPH] = NewPH; |
758 | 75 | Blocks.push_back(NewPH); |
759 | 75 | |
760 | 75 | // Update LoopInfo. |
761 | 75 | if (ParentLoop) |
762 | 7 | ParentLoop->addBasicBlockToLoop(NewPH, *LI); |
763 | 75 | |
764 | 75 | // Update DominatorTree. |
765 | 75 | DT->addNewBlock(NewPH, LoopDomBB); |
766 | 75 | |
767 | 76 | for (Loop *CurLoop : OrigLoop->getLoopsInPreorder()) { |
768 | 76 | Loop *&NewLoop = LMap[CurLoop]; |
769 | 76 | if (!NewLoop) { |
770 | 1 | NewLoop = LI->AllocateLoop(); |
771 | 1 | |
772 | 1 | // Establish the parent/child relationship. |
773 | 1 | Loop *OrigParent = CurLoop->getParentLoop(); |
774 | 1 | assert(OrigParent && "Could not find the original parent loop"); |
775 | 1 | Loop *NewParentLoop = LMap[OrigParent]; |
776 | 1 | assert(NewParentLoop && "Could not find the new parent loop"); |
777 | 1 | |
778 | 1 | NewParentLoop->addChildLoop(NewLoop); |
779 | 1 | } |
780 | 76 | } |
781 | 75 | |
782 | 137 | for (BasicBlock *BB : OrigLoop->getBlocks()) { |
783 | 137 | Loop *CurLoop = LI->getLoopFor(BB); |
784 | 137 | Loop *&NewLoop = LMap[CurLoop]; |
785 | 137 | assert(NewLoop && "Expecting new loop to be allocated"); |
786 | 137 | |
787 | 137 | BasicBlock *NewBB = CloneBasicBlock(BB, VMap, NameSuffix, F); |
788 | 137 | VMap[BB] = NewBB; |
789 | 137 | |
790 | 137 | // Update LoopInfo. |
791 | 137 | NewLoop->addBasicBlockToLoop(NewBB, *LI); |
792 | 137 | if (BB == CurLoop->getHeader()) |
793 | 76 | NewLoop->moveToHeader(NewBB); |
794 | 137 | |
795 | 137 | // Add DominatorTree node. After seeing all blocks, update to correct |
796 | 137 | // IDom. |
797 | 137 | DT->addNewBlock(NewBB, NewPH); |
798 | 137 | |
799 | 137 | Blocks.push_back(NewBB); |
800 | 137 | } |
801 | 75 | |
802 | 137 | for (BasicBlock *BB : OrigLoop->getBlocks()) { |
803 | 137 | // Update DominatorTree. |
804 | 137 | BasicBlock *IDomBB = DT->getNode(BB)->getIDom()->getBlock(); |
805 | 137 | DT->changeImmediateDominator(cast<BasicBlock>(VMap[BB]), |
806 | 137 | cast<BasicBlock>(VMap[IDomBB])); |
807 | 137 | } |
808 | 75 | |
809 | 75 | // Move them physically from the end of the block list. |
810 | 75 | F->getBasicBlockList().splice(Before->getIterator(), F->getBasicBlockList(), |
811 | 75 | NewPH); |
812 | 75 | F->getBasicBlockList().splice(Before->getIterator(), F->getBasicBlockList(), |
813 | 75 | NewLoop->getHeader()->getIterator(), F->end()); |
814 | 75 | |
815 | 75 | return NewLoop; |
816 | 75 | } |
817 | | |
818 | | /// Duplicate non-Phi instructions from the beginning of block up to |
819 | | /// StopAt instruction into a split block between BB and its predecessor. |
820 | | BasicBlock *llvm::DuplicateInstructionsInSplitBetween( |
821 | | BasicBlock *BB, BasicBlock *PredBB, Instruction *StopAt, |
822 | 535 | ValueToValueMapTy &ValueMapping, DomTreeUpdater &DTU) { |
823 | 535 | |
824 | 535 | assert(count(successors(PredBB), BB) == 1 && |
825 | 535 | "There must be a single edge between PredBB and BB!"); |
826 | 535 | // We are going to have to map operands from the original BB block to the new |
827 | 535 | // copy of the block 'NewBB'. If there are PHI nodes in BB, evaluate them to |
828 | 535 | // account for entry from PredBB. |
829 | 535 | BasicBlock::iterator BI = BB->begin(); |
830 | 739 | for (; PHINode *PN = dyn_cast<PHINode>(BI); ++BI204 ) |
831 | 204 | ValueMapping[PN] = PN->getIncomingValueForBlock(PredBB); |
832 | 535 | |
833 | 535 | BasicBlock *NewBB = SplitEdge(PredBB, BB); |
834 | 535 | NewBB->setName(PredBB->getName() + ".split"); |
835 | 535 | Instruction *NewTerm = NewBB->getTerminator(); |
836 | 535 | |
837 | 535 | // FIXME: SplitEdge does not yet take a DTU, so we include the split edge |
838 | 535 | // in the update set here. |
839 | 535 | DTU.applyUpdates({{DominatorTree::Delete, PredBB, BB}, |
840 | 535 | {DominatorTree::Insert, PredBB, NewBB}, |
841 | 535 | {DominatorTree::Insert, NewBB, BB}}); |
842 | 535 | |
843 | 535 | // Clone the non-phi instructions of BB into NewBB, keeping track of the |
844 | 535 | // mapping and using it to remap operands in the cloned instructions. |
845 | 535 | // Stop once we see the terminator too. This covers the case where BB's |
846 | 535 | // terminator gets replaced and StopAt == BB's terminator. |
847 | 1.28k | for (; StopAt != &*BI && BB->getTerminator() != &*BI748 ; ++BI747 ) { |
848 | 747 | Instruction *New = BI->clone(); |
849 | 747 | New->setName(BI->getName()); |
850 | 747 | New->insertBefore(NewTerm); |
851 | 747 | ValueMapping[&*BI] = New; |
852 | 747 | |
853 | 747 | // Remap operands to patch up intra-block references. |
854 | 3.14k | for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i2.40k ) |
855 | 2.40k | if (Instruction *Inst = dyn_cast<Instruction>(New->getOperand(i))) { |
856 | 890 | auto I = ValueMapping.find(Inst); |
857 | 890 | if (I != ValueMapping.end()) |
858 | 340 | New->setOperand(i, I->second); |
859 | 890 | } |
860 | 747 | } |
861 | 535 | |
862 | 535 | return NewBB; |
863 | 535 | } |