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/Instructions.h" |
27 | #include "llvm/IR/IntrinsicInst.h" |
28 | #include "llvm/IR/LLVMContext.h" |
29 | #include "llvm/IR/MDBuilder.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 | #include <optional> |
38 | using namespace llvm; |
39 | |
40 | #define DEBUG_TYPE "clone-function" |
41 | |
42 | /// See comments in Cloning.h. |
43 | BasicBlock *llvm::CloneBasicBlock(const BasicBlock *BB, ValueToValueMapTy &VMap, |
44 | const Twine &NameSuffix, Function *F, |
45 | ClonedCodeInfo *CodeInfo, |
46 | DebugInfoFinder *DIFinder) { |
47 | BasicBlock *NewBB = BasicBlock::Create(Context&: BB->getContext(), Name: "" , Parent: F); |
48 | NewBB->IsNewDbgInfoFormat = BB->IsNewDbgInfoFormat; |
49 | if (BB->hasName()) |
50 | NewBB->setName(BB->getName() + NameSuffix); |
51 | |
52 | bool hasCalls = false, hasDynamicAllocas = false, hasMemProfMetadata = false; |
53 | Module *TheModule = F ? F->getParent() : nullptr; |
54 | |
55 | // Loop over all instructions, and copy them over. |
56 | for (const Instruction &I : *BB) { |
57 | if (DIFinder && TheModule) |
58 | DIFinder->processInstruction(M: *TheModule, I); |
59 | |
60 | Instruction *NewInst = I.clone(); |
61 | if (I.hasName()) |
62 | NewInst->setName(I.getName() + NameSuffix); |
63 | |
64 | NewInst->insertBefore(BB&: *NewBB, InsertPos: NewBB->end()); |
65 | NewInst->cloneDebugInfoFrom(From: &I); |
66 | |
67 | VMap[&I] = NewInst; // Add instruction map to value. |
68 | |
69 | if (isa<CallInst>(Val: I) && !I.isDebugOrPseudoInst()) { |
70 | hasCalls = true; |
71 | hasMemProfMetadata |= I.hasMetadata(KindID: LLVMContext::MD_memprof); |
72 | } |
73 | if (const AllocaInst *AI = dyn_cast<AllocaInst>(Val: &I)) { |
74 | if (!AI->isStaticAlloca()) { |
75 | hasDynamicAllocas = true; |
76 | } |
77 | } |
78 | } |
79 | |
80 | if (CodeInfo) { |
81 | CodeInfo->ContainsCalls |= hasCalls; |
82 | CodeInfo->ContainsMemProfMetadata |= hasMemProfMetadata; |
83 | CodeInfo->ContainsDynamicAllocas |= hasDynamicAllocas; |
84 | } |
85 | return NewBB; |
86 | } |
87 | |
88 | // Clone OldFunc into NewFunc, transforming the old arguments into references to |
89 | // VMap values. |
90 | // |
91 | void llvm::CloneFunctionInto(Function *NewFunc, const Function *OldFunc, |
92 | ValueToValueMapTy &VMap, |
93 | CloneFunctionChangeType Changes, |
94 | SmallVectorImpl<ReturnInst *> &Returns, |
95 | const char *NameSuffix, ClonedCodeInfo *CodeInfo, |
96 | ValueMapTypeRemapper *TypeMapper, |
97 | ValueMaterializer *Materializer) { |
98 | NewFunc->setIsNewDbgInfoFormat(OldFunc->IsNewDbgInfoFormat); |
99 | assert(NameSuffix && "NameSuffix cannot be null!" ); |
100 | |
101 | #ifndef NDEBUG |
102 | for (const Argument &I : OldFunc->args()) |
103 | assert(VMap.count(&I) && "No mapping from source argument specified!" ); |
104 | #endif |
105 | |
106 | bool ModuleLevelChanges = Changes > CloneFunctionChangeType::LocalChangesOnly; |
107 | |
108 | // Copy all attributes other than those stored in the AttributeList. We need |
109 | // to remap the parameter indices of the AttributeList. |
110 | AttributeList NewAttrs = NewFunc->getAttributes(); |
111 | NewFunc->copyAttributesFrom(Src: OldFunc); |
112 | NewFunc->setAttributes(NewAttrs); |
113 | |
114 | const RemapFlags FuncGlobalRefFlags = |
115 | ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges; |
116 | |
117 | // Fix up the personality function that got copied over. |
118 | if (OldFunc->hasPersonalityFn()) |
119 | NewFunc->setPersonalityFn(MapValue(V: OldFunc->getPersonalityFn(), VM&: VMap, |
120 | Flags: FuncGlobalRefFlags, TypeMapper, |
121 | Materializer)); |
122 | |
123 | if (OldFunc->hasPrefixData()) { |
124 | NewFunc->setPrefixData(MapValue(V: OldFunc->getPrefixData(), VM&: VMap, |
125 | Flags: FuncGlobalRefFlags, TypeMapper, |
126 | Materializer)); |
127 | } |
128 | |
129 | if (OldFunc->hasPrologueData()) { |
130 | NewFunc->setPrologueData(MapValue(V: OldFunc->getPrologueData(), VM&: VMap, |
131 | Flags: FuncGlobalRefFlags, TypeMapper, |
132 | Materializer)); |
133 | } |
134 | |
135 | SmallVector<AttributeSet, 4> NewArgAttrs(NewFunc->arg_size()); |
136 | AttributeList OldAttrs = OldFunc->getAttributes(); |
137 | |
138 | // Clone any argument attributes that are present in the VMap. |
139 | for (const Argument &OldArg : OldFunc->args()) { |
140 | if (Argument *NewArg = dyn_cast<Argument>(Val&: VMap[&OldArg])) { |
141 | NewArgAttrs[NewArg->getArgNo()] = |
142 | OldAttrs.getParamAttrs(ArgNo: OldArg.getArgNo()); |
143 | } |
144 | } |
145 | |
146 | NewFunc->setAttributes( |
147 | AttributeList::get(C&: NewFunc->getContext(), FnAttrs: OldAttrs.getFnAttrs(), |
148 | RetAttrs: OldAttrs.getRetAttrs(), ArgAttrs: NewArgAttrs)); |
149 | |
150 | // Everything else beyond this point deals with function instructions, |
151 | // so if we are dealing with a function declaration, we're done. |
152 | if (OldFunc->isDeclaration()) |
153 | return; |
154 | |
155 | // When we remap instructions within the same module, we want to avoid |
156 | // duplicating inlined DISubprograms, so record all subprograms we find as we |
157 | // duplicate instructions and then freeze them in the MD map. We also record |
158 | // information about dbg.value and dbg.declare to avoid duplicating the |
159 | // types. |
160 | std::optional<DebugInfoFinder> DIFinder; |
161 | |
162 | // Track the subprogram attachment that needs to be cloned to fine-tune the |
163 | // mapping within the same module. |
164 | DISubprogram *SPClonedWithinModule = nullptr; |
165 | if (Changes < CloneFunctionChangeType::DifferentModule) { |
166 | assert((NewFunc->getParent() == nullptr || |
167 | NewFunc->getParent() == OldFunc->getParent()) && |
168 | "Expected NewFunc to have the same parent, or no parent" ); |
169 | |
170 | // Need to find subprograms, types, and compile units. |
171 | DIFinder.emplace(); |
172 | |
173 | SPClonedWithinModule = OldFunc->getSubprogram(); |
174 | if (SPClonedWithinModule) |
175 | DIFinder->processSubprogram(SP: SPClonedWithinModule); |
176 | } else { |
177 | assert((NewFunc->getParent() == nullptr || |
178 | NewFunc->getParent() != OldFunc->getParent()) && |
179 | "Expected NewFunc to have different parents, or no parent" ); |
180 | |
181 | if (Changes == CloneFunctionChangeType::DifferentModule) { |
182 | assert(NewFunc->getParent() && |
183 | "Need parent of new function to maintain debug info invariants" ); |
184 | |
185 | // Need to find all the compile units. |
186 | DIFinder.emplace(); |
187 | } |
188 | } |
189 | |
190 | // Loop over all of the basic blocks in the function, cloning them as |
191 | // appropriate. Note that we save BE this way in order to handle cloning of |
192 | // recursive functions into themselves. |
193 | for (const BasicBlock &BB : *OldFunc) { |
194 | |
195 | // Create a new basic block and copy instructions into it! |
196 | BasicBlock *CBB = CloneBasicBlock(BB: &BB, VMap, NameSuffix, F: NewFunc, CodeInfo, |
197 | DIFinder: DIFinder ? &*DIFinder : nullptr); |
198 | |
199 | // Add basic block mapping. |
200 | VMap[&BB] = CBB; |
201 | |
202 | // It is only legal to clone a function if a block address within that |
203 | // function is never referenced outside of the function. Given that, we |
204 | // want to map block addresses from the old function to block addresses in |
205 | // the clone. (This is different from the generic ValueMapper |
206 | // implementation, which generates an invalid blockaddress when |
207 | // cloning a function.) |
208 | if (BB.hasAddressTaken()) { |
209 | Constant *OldBBAddr = BlockAddress::get(F: const_cast<Function *>(OldFunc), |
210 | BB: const_cast<BasicBlock *>(&BB)); |
211 | VMap[OldBBAddr] = BlockAddress::get(F: NewFunc, BB: CBB); |
212 | } |
213 | |
214 | // Note return instructions for the caller. |
215 | if (ReturnInst *RI = dyn_cast<ReturnInst>(Val: CBB->getTerminator())) |
216 | Returns.push_back(Elt: RI); |
217 | } |
218 | |
219 | if (Changes < CloneFunctionChangeType::DifferentModule && |
220 | DIFinder->subprogram_count() > 0) { |
221 | // Turn on module-level changes, since we need to clone (some of) the |
222 | // debug info metadata. |
223 | // |
224 | // FIXME: Metadata effectively owned by a function should be made |
225 | // local, and only that local metadata should be cloned. |
226 | ModuleLevelChanges = true; |
227 | |
228 | auto mapToSelfIfNew = [&VMap](MDNode *N) { |
229 | // Avoid clobbering an existing mapping. |
230 | (void)VMap.MD().try_emplace(Key: N, Args&: N); |
231 | }; |
232 | |
233 | // Avoid cloning types, compile units, and (other) subprograms. |
234 | SmallPtrSet<const DISubprogram *, 16> MappedToSelfSPs; |
235 | for (DISubprogram *ISP : DIFinder->subprograms()) { |
236 | if (ISP != SPClonedWithinModule) { |
237 | mapToSelfIfNew(ISP); |
238 | MappedToSelfSPs.insert(Ptr: ISP); |
239 | } |
240 | } |
241 | |
242 | // If a subprogram isn't going to be cloned skip its lexical blocks as well. |
243 | for (DIScope *S : DIFinder->scopes()) { |
244 | auto *LScope = dyn_cast<DILocalScope>(Val: S); |
245 | if (LScope && MappedToSelfSPs.count(Ptr: LScope->getSubprogram())) |
246 | mapToSelfIfNew(S); |
247 | } |
248 | |
249 | for (DICompileUnit *CU : DIFinder->compile_units()) |
250 | mapToSelfIfNew(CU); |
251 | |
252 | for (DIType *Type : DIFinder->types()) |
253 | mapToSelfIfNew(Type); |
254 | } else { |
255 | assert(!SPClonedWithinModule && |
256 | "Subprogram should be in DIFinder->subprogram_count()..." ); |
257 | } |
258 | |
259 | const auto RemapFlag = ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges; |
260 | // Duplicate the metadata that is attached to the cloned function. |
261 | // Subprograms/CUs/types that were already mapped to themselves won't be |
262 | // duplicated. |
263 | SmallVector<std::pair<unsigned, MDNode *>, 1> MDs; |
264 | OldFunc->getAllMetadata(MDs); |
265 | for (auto MD : MDs) { |
266 | NewFunc->addMetadata(KindID: MD.first, MD&: *MapMetadata(MD: MD.second, VM&: VMap, Flags: RemapFlag, |
267 | TypeMapper, Materializer)); |
268 | } |
269 | |
270 | // Loop over all of the instructions in the new function, fixing up operand |
271 | // references as we go. This uses VMap to do all the hard work. |
272 | for (Function::iterator |
273 | BB = cast<BasicBlock>(Val&: VMap[&OldFunc->front()])->getIterator(), |
274 | BE = NewFunc->end(); |
275 | BB != BE; ++BB) |
276 | // Loop over all instructions, fixing each one as we find it, and any |
277 | // attached debug-info records. |
278 | for (Instruction &II : *BB) { |
279 | RemapInstruction(I: &II, VM&: VMap, Flags: RemapFlag, TypeMapper, Materializer); |
280 | RemapDbgVariableRecordRange(M: II.getModule(), Range: II.getDbgRecordRange(), VM&: VMap, |
281 | Flags: RemapFlag, TypeMapper, Materializer); |
282 | } |
283 | |
284 | // Only update !llvm.dbg.cu for DifferentModule (not CloneModule). In the |
285 | // same module, the compile unit will already be listed (or not). When |
286 | // cloning a module, CloneModule() will handle creating the named metadata. |
287 | if (Changes != CloneFunctionChangeType::DifferentModule) |
288 | return; |
289 | |
290 | // Update !llvm.dbg.cu with compile units added to the new module if this |
291 | // function is being cloned in isolation. |
292 | // |
293 | // FIXME: This is making global / module-level changes, which doesn't seem |
294 | // like the right encapsulation Consider dropping the requirement to update |
295 | // !llvm.dbg.cu (either obsoleting the node, or restricting it to |
296 | // non-discardable compile units) instead of discovering compile units by |
297 | // visiting the metadata attached to global values, which would allow this |
298 | // code to be deleted. Alternatively, perhaps give responsibility for this |
299 | // update to CloneFunctionInto's callers. |
300 | auto *NewModule = NewFunc->getParent(); |
301 | auto *NMD = NewModule->getOrInsertNamedMetadata(Name: "llvm.dbg.cu" ); |
302 | // Avoid multiple insertions of the same DICompileUnit to NMD. |
303 | SmallPtrSet<const void *, 8> Visited; |
304 | for (auto *Operand : NMD->operands()) |
305 | Visited.insert(Ptr: Operand); |
306 | for (auto *Unit : DIFinder->compile_units()) { |
307 | MDNode *MappedUnit = |
308 | MapMetadata(MD: Unit, VM&: VMap, Flags: RF_None, TypeMapper, Materializer); |
309 | if (Visited.insert(Ptr: MappedUnit).second) |
310 | NMD->addOperand(M: MappedUnit); |
311 | } |
312 | } |
313 | |
314 | /// Return a copy of the specified function and add it to that function's |
315 | /// module. Also, any references specified in the VMap are changed to refer to |
316 | /// their mapped value instead of the original one. If any of the arguments to |
317 | /// the function are in the VMap, the arguments are deleted from the resultant |
318 | /// function. The VMap is updated to include mappings from all of the |
319 | /// instructions and basicblocks in the function from their old to new values. |
320 | /// |
321 | Function *llvm::CloneFunction(Function *F, ValueToValueMapTy &VMap, |
322 | ClonedCodeInfo *CodeInfo) { |
323 | std::vector<Type *> ArgTypes; |
324 | |
325 | // The user might be deleting arguments to the function by specifying them in |
326 | // the VMap. If so, we need to not add the arguments to the arg ty vector |
327 | // |
328 | for (const Argument &I : F->args()) |
329 | if (VMap.count(Val: &I) == 0) // Haven't mapped the argument to anything yet? |
330 | ArgTypes.push_back(x: I.getType()); |
331 | |
332 | // Create a new function type... |
333 | FunctionType *FTy = |
334 | FunctionType::get(Result: F->getFunctionType()->getReturnType(), Params: ArgTypes, |
335 | isVarArg: F->getFunctionType()->isVarArg()); |
336 | |
337 | // Create the new function... |
338 | Function *NewF = Function::Create(Ty: FTy, Linkage: F->getLinkage(), AddrSpace: F->getAddressSpace(), |
339 | N: F->getName(), M: F->getParent()); |
340 | NewF->setIsNewDbgInfoFormat(F->IsNewDbgInfoFormat); |
341 | |
342 | // Loop over the arguments, copying the names of the mapped arguments over... |
343 | Function::arg_iterator DestI = NewF->arg_begin(); |
344 | for (const Argument &I : F->args()) |
345 | if (VMap.count(Val: &I) == 0) { // Is this argument preserved? |
346 | DestI->setName(I.getName()); // Copy the name over... |
347 | VMap[&I] = &*DestI++; // Add mapping to VMap |
348 | } |
349 | |
350 | SmallVector<ReturnInst *, 8> Returns; // Ignore returns cloned. |
351 | CloneFunctionInto(NewFunc: NewF, OldFunc: F, VMap, Changes: CloneFunctionChangeType::LocalChangesOnly, |
352 | Returns, NameSuffix: "" , CodeInfo); |
353 | |
354 | return NewF; |
355 | } |
356 | |
357 | namespace { |
358 | /// This is a private class used to implement CloneAndPruneFunctionInto. |
359 | struct PruningFunctionCloner { |
360 | Function *NewFunc; |
361 | const Function *OldFunc; |
362 | ValueToValueMapTy &VMap; |
363 | bool ModuleLevelChanges; |
364 | const char *NameSuffix; |
365 | ClonedCodeInfo *CodeInfo; |
366 | bool HostFuncIsStrictFP; |
367 | |
368 | Instruction *cloneInstruction(BasicBlock::const_iterator II); |
369 | |
370 | public: |
371 | PruningFunctionCloner(Function *newFunc, const Function *oldFunc, |
372 | ValueToValueMapTy &valueMap, bool moduleLevelChanges, |
373 | const char *nameSuffix, ClonedCodeInfo *codeInfo) |
374 | : NewFunc(newFunc), OldFunc(oldFunc), VMap(valueMap), |
375 | ModuleLevelChanges(moduleLevelChanges), NameSuffix(nameSuffix), |
376 | CodeInfo(codeInfo) { |
377 | HostFuncIsStrictFP = |
378 | newFunc->getAttributes().hasFnAttr(Attribute::StrictFP); |
379 | } |
380 | |
381 | /// The specified block is found to be reachable, clone it and |
382 | /// anything that it can reach. |
383 | void CloneBlock(const BasicBlock *BB, BasicBlock::const_iterator StartingInst, |
384 | std::vector<const BasicBlock *> &ToClone); |
385 | }; |
386 | } // namespace |
387 | |
388 | static bool hasRoundingModeOperand(Intrinsic::ID CIID) { |
389 | switch (CIID) { |
390 | #define INSTRUCTION(NAME, NARG, ROUND_MODE, INTRINSIC) \ |
391 | case Intrinsic::INTRINSIC: \ |
392 | return ROUND_MODE == 1; |
393 | #define FUNCTION INSTRUCTION |
394 | #include "llvm/IR/ConstrainedOps.def" |
395 | default: |
396 | llvm_unreachable("Unexpected constrained intrinsic id" ); |
397 | } |
398 | } |
399 | |
400 | Instruction * |
401 | PruningFunctionCloner::cloneInstruction(BasicBlock::const_iterator II) { |
402 | const Instruction &OldInst = *II; |
403 | Instruction *NewInst = nullptr; |
404 | if (HostFuncIsStrictFP) { |
405 | Intrinsic::ID CIID = getConstrainedIntrinsicID(Instr: OldInst); |
406 | if (CIID != Intrinsic::not_intrinsic) { |
407 | // Instead of cloning the instruction, a call to constrained intrinsic |
408 | // should be created. |
409 | // Assume the first arguments of constrained intrinsics are the same as |
410 | // the operands of original instruction. |
411 | |
412 | // Determine overloaded types of the intrinsic. |
413 | SmallVector<Type *, 2> TParams; |
414 | SmallVector<Intrinsic::IITDescriptor, 8> Descriptor; |
415 | getIntrinsicInfoTableEntries(id: CIID, T&: Descriptor); |
416 | for (unsigned I = 0, E = Descriptor.size(); I != E; ++I) { |
417 | Intrinsic::IITDescriptor Operand = Descriptor[I]; |
418 | switch (Operand.Kind) { |
419 | case Intrinsic::IITDescriptor::Argument: |
420 | if (Operand.getArgumentKind() != |
421 | Intrinsic::IITDescriptor::AK_MatchType) { |
422 | if (I == 0) |
423 | TParams.push_back(Elt: OldInst.getType()); |
424 | else |
425 | TParams.push_back(Elt: OldInst.getOperand(i: I - 1)->getType()); |
426 | } |
427 | break; |
428 | case Intrinsic::IITDescriptor::SameVecWidthArgument: |
429 | ++I; |
430 | break; |
431 | default: |
432 | break; |
433 | } |
434 | } |
435 | |
436 | // Create intrinsic call. |
437 | LLVMContext &Ctx = NewFunc->getContext(); |
438 | Function *IFn = |
439 | Intrinsic::getDeclaration(M: NewFunc->getParent(), id: CIID, Tys: TParams); |
440 | SmallVector<Value *, 4> Args; |
441 | unsigned NumOperands = OldInst.getNumOperands(); |
442 | if (isa<CallInst>(Val: OldInst)) |
443 | --NumOperands; |
444 | for (unsigned I = 0; I < NumOperands; ++I) { |
445 | Value *Op = OldInst.getOperand(i: I); |
446 | Args.push_back(Elt: Op); |
447 | } |
448 | if (const auto *CmpI = dyn_cast<FCmpInst>(Val: &OldInst)) { |
449 | FCmpInst::Predicate Pred = CmpI->getPredicate(); |
450 | StringRef PredName = FCmpInst::getPredicateName(P: Pred); |
451 | Args.push_back(Elt: MetadataAsValue::get(Context&: Ctx, MD: MDString::get(Context&: Ctx, Str: PredName))); |
452 | } |
453 | |
454 | // The last arguments of a constrained intrinsic are metadata that |
455 | // represent rounding mode (absents in some intrinsics) and exception |
456 | // behavior. The inlined function uses default settings. |
457 | if (hasRoundingModeOperand(CIID)) |
458 | Args.push_back( |
459 | Elt: MetadataAsValue::get(Context&: Ctx, MD: MDString::get(Context&: Ctx, Str: "round.tonearest" ))); |
460 | Args.push_back( |
461 | Elt: MetadataAsValue::get(Context&: Ctx, MD: MDString::get(Context&: Ctx, Str: "fpexcept.ignore" ))); |
462 | |
463 | NewInst = CallInst::Create(Func: IFn, Args, NameStr: OldInst.getName() + ".strict" ); |
464 | } |
465 | } |
466 | if (!NewInst) |
467 | NewInst = II->clone(); |
468 | return NewInst; |
469 | } |
470 | |
471 | /// The specified block is found to be reachable, clone it and |
472 | /// anything that it can reach. |
473 | void PruningFunctionCloner::CloneBlock( |
474 | const BasicBlock *BB, BasicBlock::const_iterator StartingInst, |
475 | std::vector<const BasicBlock *> &ToClone) { |
476 | WeakTrackingVH &BBEntry = VMap[BB]; |
477 | |
478 | // Have we already cloned this block? |
479 | if (BBEntry) |
480 | return; |
481 | |
482 | // Nope, clone it now. |
483 | BasicBlock *NewBB; |
484 | Twine NewName(BB->hasName() ? Twine(BB->getName()) + NameSuffix : "" ); |
485 | BBEntry = NewBB = BasicBlock::Create(Context&: BB->getContext(), Name: NewName, Parent: NewFunc); |
486 | NewBB->IsNewDbgInfoFormat = BB->IsNewDbgInfoFormat; |
487 | |
488 | // It is only legal to clone a function if a block address within that |
489 | // function is never referenced outside of the function. Given that, we |
490 | // want to map block addresses from the old function to block addresses in |
491 | // the clone. (This is different from the generic ValueMapper |
492 | // implementation, which generates an invalid blockaddress when |
493 | // cloning a function.) |
494 | // |
495 | // Note that we don't need to fix the mapping for unreachable blocks; |
496 | // the default mapping there is safe. |
497 | if (BB->hasAddressTaken()) { |
498 | Constant *OldBBAddr = BlockAddress::get(F: const_cast<Function *>(OldFunc), |
499 | BB: const_cast<BasicBlock *>(BB)); |
500 | VMap[OldBBAddr] = BlockAddress::get(F: NewFunc, BB: NewBB); |
501 | } |
502 | |
503 | bool hasCalls = false, hasDynamicAllocas = false, hasStaticAllocas = false; |
504 | bool hasMemProfMetadata = false; |
505 | |
506 | // Keep a cursor pointing at the last place we cloned debug-info records from. |
507 | BasicBlock::const_iterator DbgCursor = StartingInst; |
508 | auto CloneDbgRecordsToHere = |
509 | [NewBB, &DbgCursor](Instruction *NewInst, BasicBlock::const_iterator II) { |
510 | if (!NewBB->IsNewDbgInfoFormat) |
511 | return; |
512 | |
513 | // Clone debug-info records onto this instruction. Iterate through any |
514 | // source-instructions we've cloned and then subsequently optimised |
515 | // away, so that their debug-info doesn't go missing. |
516 | for (; DbgCursor != II; ++DbgCursor) |
517 | NewInst->cloneDebugInfoFrom(From: &*DbgCursor, FromHere: std::nullopt, InsertAtHead: false); |
518 | NewInst->cloneDebugInfoFrom(From: &*II); |
519 | DbgCursor = std::next(x: II); |
520 | }; |
521 | |
522 | // Loop over all instructions, and copy them over, DCE'ing as we go. This |
523 | // loop doesn't include the terminator. |
524 | for (BasicBlock::const_iterator II = StartingInst, IE = --BB->end(); II != IE; |
525 | ++II) { |
526 | |
527 | Instruction *NewInst = cloneInstruction(II); |
528 | NewInst->insertInto(ParentBB: NewBB, It: NewBB->end()); |
529 | |
530 | if (HostFuncIsStrictFP) { |
531 | // All function calls in the inlined function must get 'strictfp' |
532 | // attribute to prevent undesirable optimizations. |
533 | if (auto *Call = dyn_cast<CallInst>(Val: NewInst)) |
534 | Call->addFnAttr(Attribute::StrictFP); |
535 | } |
536 | |
537 | // Eagerly remap operands to the newly cloned instruction, except for PHI |
538 | // nodes for which we defer processing until we update the CFG. Also defer |
539 | // debug intrinsic processing because they may contain use-before-defs. |
540 | if (!isa<PHINode>(Val: NewInst) && !isa<DbgVariableIntrinsic>(Val: NewInst)) { |
541 | RemapInstruction(I: NewInst, VM&: VMap, |
542 | Flags: ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges); |
543 | |
544 | // Eagerly constant fold the newly cloned instruction. If successful, add |
545 | // a mapping to the new value. Non-constant operands may be incomplete at |
546 | // this stage, thus instruction simplification is performed after |
547 | // processing phi-nodes. |
548 | if (Value *V = ConstantFoldInstruction( |
549 | I: NewInst, DL: BB->getModule()->getDataLayout())) { |
550 | if (isInstructionTriviallyDead(I: NewInst)) { |
551 | VMap[&*II] = V; |
552 | NewInst->eraseFromParent(); |
553 | continue; |
554 | } |
555 | } |
556 | } |
557 | |
558 | if (II->hasName()) |
559 | NewInst->setName(II->getName() + NameSuffix); |
560 | VMap[&*II] = NewInst; // Add instruction map to value. |
561 | if (isa<CallInst>(Val: II) && !II->isDebugOrPseudoInst()) { |
562 | hasCalls = true; |
563 | hasMemProfMetadata |= II->hasMetadata(KindID: LLVMContext::MD_memprof); |
564 | } |
565 | |
566 | CloneDbgRecordsToHere(NewInst, II); |
567 | |
568 | if (CodeInfo) { |
569 | CodeInfo->OrigVMap[&*II] = NewInst; |
570 | if (auto *CB = dyn_cast<CallBase>(Val: &*II)) |
571 | if (CB->hasOperandBundles()) |
572 | CodeInfo->OperandBundleCallSites.push_back(x: NewInst); |
573 | } |
574 | |
575 | if (const AllocaInst *AI = dyn_cast<AllocaInst>(Val&: II)) { |
576 | if (isa<ConstantInt>(Val: AI->getArraySize())) |
577 | hasStaticAllocas = true; |
578 | else |
579 | hasDynamicAllocas = true; |
580 | } |
581 | } |
582 | |
583 | // Finally, clone over the terminator. |
584 | const Instruction *OldTI = BB->getTerminator(); |
585 | bool TerminatorDone = false; |
586 | if (const BranchInst *BI = dyn_cast<BranchInst>(Val: OldTI)) { |
587 | if (BI->isConditional()) { |
588 | // If the condition was a known constant in the callee... |
589 | ConstantInt *Cond = dyn_cast<ConstantInt>(Val: BI->getCondition()); |
590 | // Or is a known constant in the caller... |
591 | if (!Cond) { |
592 | Value *V = VMap.lookup(Val: BI->getCondition()); |
593 | Cond = dyn_cast_or_null<ConstantInt>(Val: V); |
594 | } |
595 | |
596 | // Constant fold to uncond branch! |
597 | if (Cond) { |
598 | BasicBlock *Dest = BI->getSuccessor(i: !Cond->getZExtValue()); |
599 | VMap[OldTI] = BranchInst::Create(IfTrue: Dest, InsertAtEnd: NewBB); |
600 | ToClone.push_back(x: Dest); |
601 | TerminatorDone = true; |
602 | } |
603 | } |
604 | } else if (const SwitchInst *SI = dyn_cast<SwitchInst>(Val: OldTI)) { |
605 | // If switching on a value known constant in the caller. |
606 | ConstantInt *Cond = dyn_cast<ConstantInt>(Val: SI->getCondition()); |
607 | if (!Cond) { // Or known constant after constant prop in the callee... |
608 | Value *V = VMap.lookup(Val: SI->getCondition()); |
609 | Cond = dyn_cast_or_null<ConstantInt>(Val: V); |
610 | } |
611 | if (Cond) { // Constant fold to uncond branch! |
612 | SwitchInst::ConstCaseHandle Case = *SI->findCaseValue(C: Cond); |
613 | BasicBlock *Dest = const_cast<BasicBlock *>(Case.getCaseSuccessor()); |
614 | VMap[OldTI] = BranchInst::Create(IfTrue: Dest, InsertAtEnd: NewBB); |
615 | ToClone.push_back(x: Dest); |
616 | TerminatorDone = true; |
617 | } |
618 | } |
619 | |
620 | if (!TerminatorDone) { |
621 | Instruction *NewInst = OldTI->clone(); |
622 | if (OldTI->hasName()) |
623 | NewInst->setName(OldTI->getName() + NameSuffix); |
624 | NewInst->insertInto(ParentBB: NewBB, It: NewBB->end()); |
625 | |
626 | CloneDbgRecordsToHere(NewInst, OldTI->getIterator()); |
627 | |
628 | VMap[OldTI] = NewInst; // Add instruction map to value. |
629 | |
630 | if (CodeInfo) { |
631 | CodeInfo->OrigVMap[OldTI] = NewInst; |
632 | if (auto *CB = dyn_cast<CallBase>(Val: OldTI)) |
633 | if (CB->hasOperandBundles()) |
634 | CodeInfo->OperandBundleCallSites.push_back(x: NewInst); |
635 | } |
636 | |
637 | // Recursively clone any reachable successor blocks. |
638 | append_range(C&: ToClone, R: successors(I: BB->getTerminator())); |
639 | } else { |
640 | // If we didn't create a new terminator, clone DbgVariableRecords from the |
641 | // old terminator onto the new terminator. |
642 | Instruction *NewInst = NewBB->getTerminator(); |
643 | assert(NewInst); |
644 | |
645 | CloneDbgRecordsToHere(NewInst, OldTI->getIterator()); |
646 | } |
647 | |
648 | if (CodeInfo) { |
649 | CodeInfo->ContainsCalls |= hasCalls; |
650 | CodeInfo->ContainsMemProfMetadata |= hasMemProfMetadata; |
651 | CodeInfo->ContainsDynamicAllocas |= hasDynamicAllocas; |
652 | CodeInfo->ContainsDynamicAllocas |= |
653 | hasStaticAllocas && BB != &BB->getParent()->front(); |
654 | } |
655 | } |
656 | |
657 | /// This works like CloneAndPruneFunctionInto, except that it does not clone the |
658 | /// entire function. Instead it starts at an instruction provided by the caller |
659 | /// and copies (and prunes) only the code reachable from that instruction. |
660 | void llvm::CloneAndPruneIntoFromInst(Function *NewFunc, const Function *OldFunc, |
661 | const Instruction *StartingInst, |
662 | ValueToValueMapTy &VMap, |
663 | bool ModuleLevelChanges, |
664 | SmallVectorImpl<ReturnInst *> &Returns, |
665 | const char *NameSuffix, |
666 | ClonedCodeInfo *CodeInfo) { |
667 | assert(NameSuffix && "NameSuffix cannot be null!" ); |
668 | |
669 | ValueMapTypeRemapper *TypeMapper = nullptr; |
670 | ValueMaterializer *Materializer = nullptr; |
671 | |
672 | #ifndef NDEBUG |
673 | // If the cloning starts at the beginning of the function, verify that |
674 | // the function arguments are mapped. |
675 | if (!StartingInst) |
676 | for (const Argument &II : OldFunc->args()) |
677 | assert(VMap.count(&II) && "No mapping from source argument specified!" ); |
678 | #endif |
679 | |
680 | PruningFunctionCloner PFC(NewFunc, OldFunc, VMap, ModuleLevelChanges, |
681 | NameSuffix, CodeInfo); |
682 | const BasicBlock *StartingBB; |
683 | if (StartingInst) |
684 | StartingBB = StartingInst->getParent(); |
685 | else { |
686 | StartingBB = &OldFunc->getEntryBlock(); |
687 | StartingInst = &StartingBB->front(); |
688 | } |
689 | |
690 | // Collect debug intrinsics for remapping later. |
691 | SmallVector<const DbgVariableIntrinsic *, 8> DbgIntrinsics; |
692 | for (const auto &BB : *OldFunc) { |
693 | for (const auto &I : BB) { |
694 | if (const auto *DVI = dyn_cast<DbgVariableIntrinsic>(Val: &I)) |
695 | DbgIntrinsics.push_back(Elt: DVI); |
696 | } |
697 | } |
698 | |
699 | // Clone the entry block, and anything recursively reachable from it. |
700 | std::vector<const BasicBlock *> CloneWorklist; |
701 | PFC.CloneBlock(BB: StartingBB, StartingInst: StartingInst->getIterator(), ToClone&: CloneWorklist); |
702 | while (!CloneWorklist.empty()) { |
703 | const BasicBlock *BB = CloneWorklist.back(); |
704 | CloneWorklist.pop_back(); |
705 | PFC.CloneBlock(BB, StartingInst: BB->begin(), ToClone&: CloneWorklist); |
706 | } |
707 | |
708 | // Loop over all of the basic blocks in the old function. If the block was |
709 | // reachable, we have cloned it and the old block is now in the value map: |
710 | // insert it into the new function in the right order. If not, ignore it. |
711 | // |
712 | // Defer PHI resolution until rest of function is resolved. |
713 | SmallVector<const PHINode *, 16> PHIToResolve; |
714 | for (const BasicBlock &BI : *OldFunc) { |
715 | Value *V = VMap.lookup(Val: &BI); |
716 | BasicBlock *NewBB = cast_or_null<BasicBlock>(Val: V); |
717 | if (!NewBB) |
718 | continue; // Dead block. |
719 | |
720 | // Move the new block to preserve the order in the original function. |
721 | NewBB->moveBefore(MovePos: NewFunc->end()); |
722 | |
723 | // Handle PHI nodes specially, as we have to remove references to dead |
724 | // blocks. |
725 | for (const PHINode &PN : BI.phis()) { |
726 | // PHI nodes may have been remapped to non-PHI nodes by the caller or |
727 | // during the cloning process. |
728 | if (isa<PHINode>(Val: VMap[&PN])) |
729 | PHIToResolve.push_back(Elt: &PN); |
730 | else |
731 | break; |
732 | } |
733 | |
734 | // Finally, remap the terminator instructions, as those can't be remapped |
735 | // until all BBs are mapped. |
736 | RemapInstruction(I: NewBB->getTerminator(), VM&: VMap, |
737 | Flags: ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges, |
738 | TypeMapper, Materializer); |
739 | } |
740 | |
741 | // Defer PHI resolution until rest of function is resolved, PHI resolution |
742 | // requires the CFG to be up-to-date. |
743 | for (unsigned phino = 0, e = PHIToResolve.size(); phino != e;) { |
744 | const PHINode *OPN = PHIToResolve[phino]; |
745 | unsigned NumPreds = OPN->getNumIncomingValues(); |
746 | const BasicBlock *OldBB = OPN->getParent(); |
747 | BasicBlock *NewBB = cast<BasicBlock>(Val&: VMap[OldBB]); |
748 | |
749 | // Map operands for blocks that are live and remove operands for blocks |
750 | // that are dead. |
751 | for (; phino != PHIToResolve.size() && |
752 | PHIToResolve[phino]->getParent() == OldBB; |
753 | ++phino) { |
754 | OPN = PHIToResolve[phino]; |
755 | PHINode *PN = cast<PHINode>(Val&: VMap[OPN]); |
756 | for (unsigned pred = 0, e = NumPreds; pred != e; ++pred) { |
757 | Value *V = VMap.lookup(Val: PN->getIncomingBlock(i: pred)); |
758 | if (BasicBlock *MappedBlock = cast_or_null<BasicBlock>(Val: V)) { |
759 | Value *InVal = |
760 | MapValue(V: PN->getIncomingValue(i: pred), VM&: VMap, |
761 | Flags: ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges); |
762 | assert(InVal && "Unknown input value?" ); |
763 | PN->setIncomingValue(i: pred, V: InVal); |
764 | PN->setIncomingBlock(i: pred, BB: MappedBlock); |
765 | } else { |
766 | PN->removeIncomingValue(Idx: pred, DeletePHIIfEmpty: false); |
767 | --pred; // Revisit the next entry. |
768 | --e; |
769 | } |
770 | } |
771 | } |
772 | |
773 | // The loop above has removed PHI entries for those blocks that are dead |
774 | // and has updated others. However, if a block is live (i.e. copied over) |
775 | // but its terminator has been changed to not go to this block, then our |
776 | // phi nodes will have invalid entries. Update the PHI nodes in this |
777 | // case. |
778 | PHINode *PN = cast<PHINode>(Val: NewBB->begin()); |
779 | NumPreds = pred_size(BB: NewBB); |
780 | if (NumPreds != PN->getNumIncomingValues()) { |
781 | assert(NumPreds < PN->getNumIncomingValues()); |
782 | // Count how many times each predecessor comes to this block. |
783 | std::map<BasicBlock *, unsigned> PredCount; |
784 | for (BasicBlock *Pred : predecessors(BB: NewBB)) |
785 | --PredCount[Pred]; |
786 | |
787 | // Figure out how many entries to remove from each PHI. |
788 | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) |
789 | ++PredCount[PN->getIncomingBlock(i)]; |
790 | |
791 | // At this point, the excess predecessor entries are positive in the |
792 | // map. Loop over all of the PHIs and remove excess predecessor |
793 | // entries. |
794 | BasicBlock::iterator I = NewBB->begin(); |
795 | for (; (PN = dyn_cast<PHINode>(Val&: I)); ++I) { |
796 | for (const auto &PCI : PredCount) { |
797 | BasicBlock *Pred = PCI.first; |
798 | for (unsigned NumToRemove = PCI.second; NumToRemove; --NumToRemove) |
799 | PN->removeIncomingValue(BB: Pred, DeletePHIIfEmpty: false); |
800 | } |
801 | } |
802 | } |
803 | |
804 | // If the loops above have made these phi nodes have 0 or 1 operand, |
805 | // replace them with poison or the input value. We must do this for |
806 | // correctness, because 0-operand phis are not valid. |
807 | PN = cast<PHINode>(Val: NewBB->begin()); |
808 | if (PN->getNumIncomingValues() == 0) { |
809 | BasicBlock::iterator I = NewBB->begin(); |
810 | BasicBlock::const_iterator OldI = OldBB->begin(); |
811 | while ((PN = dyn_cast<PHINode>(Val: I++))) { |
812 | Value *NV = PoisonValue::get(T: PN->getType()); |
813 | PN->replaceAllUsesWith(V: NV); |
814 | assert(VMap[&*OldI] == PN && "VMap mismatch" ); |
815 | VMap[&*OldI] = NV; |
816 | PN->eraseFromParent(); |
817 | ++OldI; |
818 | } |
819 | } |
820 | } |
821 | |
822 | // As phi-nodes have been now remapped, allow incremental simplification of |
823 | // newly-cloned instructions. |
824 | const DataLayout &DL = NewFunc->getParent()->getDataLayout(); |
825 | for (const auto &BB : *OldFunc) { |
826 | for (const auto &I : BB) { |
827 | auto *NewI = dyn_cast_or_null<Instruction>(Val: VMap.lookup(Val: &I)); |
828 | if (!NewI) |
829 | continue; |
830 | |
831 | // Skip over non-intrinsic callsites, we don't want to remove any nodes |
832 | // from the CGSCC. |
833 | CallBase *CB = dyn_cast<CallBase>(Val: NewI); |
834 | if (CB && CB->getCalledFunction() && |
835 | !CB->getCalledFunction()->isIntrinsic()) |
836 | continue; |
837 | |
838 | if (Value *V = simplifyInstruction(I: NewI, Q: DL)) { |
839 | NewI->replaceAllUsesWith(V); |
840 | |
841 | if (isInstructionTriviallyDead(I: NewI)) { |
842 | NewI->eraseFromParent(); |
843 | } else { |
844 | // Did not erase it? Restore the new instruction into VMap previously |
845 | // dropped by `ValueIsRAUWd`. |
846 | VMap[&I] = NewI; |
847 | } |
848 | } |
849 | } |
850 | } |
851 | |
852 | // Remap debug intrinsic operands now that all values have been mapped. |
853 | // Doing this now (late) preserves use-before-defs in debug intrinsics. If |
854 | // we didn't do this, ValueAsMetadata(use-before-def) operands would be |
855 | // replaced by empty metadata. This would signal later cleanup passes to |
856 | // remove the debug intrinsics, potentially causing incorrect locations. |
857 | for (const auto *DVI : DbgIntrinsics) { |
858 | if (DbgVariableIntrinsic *NewDVI = |
859 | cast_or_null<DbgVariableIntrinsic>(Val: VMap.lookup(Val: DVI))) |
860 | RemapInstruction(I: NewDVI, VM&: VMap, |
861 | Flags: ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges, |
862 | TypeMapper, Materializer); |
863 | } |
864 | |
865 | // Do the same for DbgVariableRecords, touching all the instructions in the |
866 | // cloned range of blocks. |
867 | Function::iterator Begin = cast<BasicBlock>(Val&: VMap[StartingBB])->getIterator(); |
868 | for (BasicBlock &BB : make_range(x: Begin, y: NewFunc->end())) { |
869 | for (Instruction &I : BB) { |
870 | RemapDbgVariableRecordRange(M: I.getModule(), Range: I.getDbgRecordRange(), VM&: VMap, |
871 | Flags: ModuleLevelChanges ? RF_None |
872 | : RF_NoModuleLevelChanges, |
873 | TypeMapper, Materializer); |
874 | } |
875 | } |
876 | |
877 | // Simplify conditional branches and switches with a constant operand. We try |
878 | // to prune these out when cloning, but if the simplification required |
879 | // looking through PHI nodes, those are only available after forming the full |
880 | // basic block. That may leave some here, and we still want to prune the dead |
881 | // code as early as possible. |
882 | for (BasicBlock &BB : make_range(x: Begin, y: NewFunc->end())) |
883 | ConstantFoldTerminator(BB: &BB); |
884 | |
885 | // Some blocks may have become unreachable as a result. Find and delete them. |
886 | { |
887 | SmallPtrSet<BasicBlock *, 16> ReachableBlocks; |
888 | SmallVector<BasicBlock *, 16> Worklist; |
889 | Worklist.push_back(Elt: &*Begin); |
890 | while (!Worklist.empty()) { |
891 | BasicBlock *BB = Worklist.pop_back_val(); |
892 | if (ReachableBlocks.insert(Ptr: BB).second) |
893 | append_range(C&: Worklist, R: successors(BB)); |
894 | } |
895 | |
896 | SmallVector<BasicBlock *, 16> UnreachableBlocks; |
897 | for (BasicBlock &BB : make_range(x: Begin, y: NewFunc->end())) |
898 | if (!ReachableBlocks.contains(Ptr: &BB)) |
899 | UnreachableBlocks.push_back(Elt: &BB); |
900 | DeleteDeadBlocks(BBs: UnreachableBlocks); |
901 | } |
902 | |
903 | // Now that the inlined function body has been fully constructed, go through |
904 | // and zap unconditional fall-through branches. This happens all the time when |
905 | // specializing code: code specialization turns conditional branches into |
906 | // uncond branches, and this code folds them. |
907 | Function::iterator I = Begin; |
908 | while (I != NewFunc->end()) { |
909 | BranchInst *BI = dyn_cast<BranchInst>(Val: I->getTerminator()); |
910 | if (!BI || BI->isConditional()) { |
911 | ++I; |
912 | continue; |
913 | } |
914 | |
915 | BasicBlock *Dest = BI->getSuccessor(i: 0); |
916 | if (!Dest->getSinglePredecessor()) { |
917 | ++I; |
918 | continue; |
919 | } |
920 | |
921 | // We shouldn't be able to get single-entry PHI nodes here, as instsimplify |
922 | // above should have zapped all of them.. |
923 | assert(!isa<PHINode>(Dest->begin())); |
924 | |
925 | // We know all single-entry PHI nodes in the inlined function have been |
926 | // removed, so we just need to splice the blocks. |
927 | BI->eraseFromParent(); |
928 | |
929 | // Make all PHI nodes that referred to Dest now refer to I as their source. |
930 | Dest->replaceAllUsesWith(V: &*I); |
931 | |
932 | // Move all the instructions in the succ to the pred. |
933 | I->splice(ToIt: I->end(), FromBB: Dest); |
934 | |
935 | // Remove the dest block. |
936 | Dest->eraseFromParent(); |
937 | |
938 | // Do not increment I, iteratively merge all things this block branches to. |
939 | } |
940 | |
941 | // Make a final pass over the basic blocks from the old function to gather |
942 | // any return instructions which survived folding. We have to do this here |
943 | // because we can iteratively remove and merge returns above. |
944 | for (Function::iterator I = cast<BasicBlock>(Val&: VMap[StartingBB])->getIterator(), |
945 | E = NewFunc->end(); |
946 | I != E; ++I) |
947 | if (ReturnInst *RI = dyn_cast<ReturnInst>(Val: I->getTerminator())) |
948 | Returns.push_back(Elt: RI); |
949 | } |
950 | |
951 | /// This works exactly like CloneFunctionInto, |
952 | /// except that it does some simple constant prop and DCE on the fly. The |
953 | /// effect of this is to copy significantly less code in cases where (for |
954 | /// example) a function call with constant arguments is inlined, and those |
955 | /// constant arguments cause a significant amount of code in the callee to be |
956 | /// dead. Since this doesn't produce an exact copy of the input, it can't be |
957 | /// used for things like CloneFunction or CloneModule. |
958 | void llvm::CloneAndPruneFunctionInto( |
959 | Function *NewFunc, const Function *OldFunc, ValueToValueMapTy &VMap, |
960 | bool ModuleLevelChanges, SmallVectorImpl<ReturnInst *> &Returns, |
961 | const char *NameSuffix, ClonedCodeInfo *CodeInfo) { |
962 | CloneAndPruneIntoFromInst(NewFunc, OldFunc, StartingInst: &OldFunc->front().front(), VMap, |
963 | ModuleLevelChanges, Returns, NameSuffix, CodeInfo); |
964 | } |
965 | |
966 | /// Remaps instructions in \p Blocks using the mapping in \p VMap. |
967 | void llvm::remapInstructionsInBlocks(ArrayRef<BasicBlock *> Blocks, |
968 | ValueToValueMapTy &VMap) { |
969 | // Rewrite the code to refer to itself. |
970 | for (auto *BB : Blocks) { |
971 | for (auto &Inst : *BB) { |
972 | RemapDbgVariableRecordRange( |
973 | M: Inst.getModule(), Range: Inst.getDbgRecordRange(), VM&: VMap, |
974 | Flags: RF_NoModuleLevelChanges | RF_IgnoreMissingLocals); |
975 | RemapInstruction(I: &Inst, VM&: VMap, |
976 | Flags: RF_NoModuleLevelChanges | RF_IgnoreMissingLocals); |
977 | } |
978 | } |
979 | } |
980 | |
981 | /// Clones a loop \p OrigLoop. Returns the loop and the blocks in \p |
982 | /// Blocks. |
983 | /// |
984 | /// Updates LoopInfo and DominatorTree assuming the loop is dominated by block |
985 | /// \p LoopDomBB. Insert the new blocks before block specified in \p Before. |
986 | Loop *llvm::(BasicBlock *Before, BasicBlock *LoopDomBB, |
987 | Loop *OrigLoop, ValueToValueMapTy &VMap, |
988 | const Twine &NameSuffix, LoopInfo *LI, |
989 | DominatorTree *DT, |
990 | SmallVectorImpl<BasicBlock *> &Blocks) { |
991 | Function *F = OrigLoop->getHeader()->getParent(); |
992 | Loop *ParentLoop = OrigLoop->getParentLoop(); |
993 | DenseMap<Loop *, Loop *> LMap; |
994 | |
995 | Loop *NewLoop = LI->AllocateLoop(); |
996 | LMap[OrigLoop] = NewLoop; |
997 | if (ParentLoop) |
998 | ParentLoop->addChildLoop(NewChild: NewLoop); |
999 | else |
1000 | LI->addTopLevelLoop(New: NewLoop); |
1001 | |
1002 | BasicBlock *OrigPH = OrigLoop->getLoopPreheader(); |
1003 | assert(OrigPH && "No preheader" ); |
1004 | BasicBlock *NewPH = CloneBasicBlock(BB: OrigPH, VMap, NameSuffix, F); |
1005 | // To rename the loop PHIs. |
1006 | VMap[OrigPH] = NewPH; |
1007 | Blocks.push_back(Elt: NewPH); |
1008 | |
1009 | // Update LoopInfo. |
1010 | if (ParentLoop) |
1011 | ParentLoop->addBasicBlockToLoop(NewBB: NewPH, LI&: *LI); |
1012 | |
1013 | // Update DominatorTree. |
1014 | DT->addNewBlock(BB: NewPH, DomBB: LoopDomBB); |
1015 | |
1016 | for (Loop *CurLoop : OrigLoop->getLoopsInPreorder()) { |
1017 | Loop *&NewLoop = LMap[CurLoop]; |
1018 | if (!NewLoop) { |
1019 | NewLoop = LI->AllocateLoop(); |
1020 | |
1021 | // Establish the parent/child relationship. |
1022 | Loop *OrigParent = CurLoop->getParentLoop(); |
1023 | assert(OrigParent && "Could not find the original parent loop" ); |
1024 | Loop *NewParentLoop = LMap[OrigParent]; |
1025 | assert(NewParentLoop && "Could not find the new parent loop" ); |
1026 | |
1027 | NewParentLoop->addChildLoop(NewChild: NewLoop); |
1028 | } |
1029 | } |
1030 | |
1031 | for (BasicBlock *BB : OrigLoop->getBlocks()) { |
1032 | Loop *CurLoop = LI->getLoopFor(BB); |
1033 | Loop *&NewLoop = LMap[CurLoop]; |
1034 | assert(NewLoop && "Expecting new loop to be allocated" ); |
1035 | |
1036 | BasicBlock *NewBB = CloneBasicBlock(BB, VMap, NameSuffix, F); |
1037 | VMap[BB] = NewBB; |
1038 | |
1039 | // Update LoopInfo. |
1040 | NewLoop->addBasicBlockToLoop(NewBB, LI&: *LI); |
1041 | |
1042 | // Add DominatorTree node. After seeing all blocks, update to correct |
1043 | // IDom. |
1044 | DT->addNewBlock(BB: NewBB, DomBB: NewPH); |
1045 | |
1046 | Blocks.push_back(Elt: NewBB); |
1047 | } |
1048 | |
1049 | for (BasicBlock *BB : OrigLoop->getBlocks()) { |
1050 | // Update loop headers. |
1051 | Loop *CurLoop = LI->getLoopFor(BB); |
1052 | if (BB == CurLoop->getHeader()) |
1053 | LMap[CurLoop]->moveToHeader(BB: cast<BasicBlock>(Val&: VMap[BB])); |
1054 | |
1055 | // Update DominatorTree. |
1056 | BasicBlock *IDomBB = DT->getNode(BB)->getIDom()->getBlock(); |
1057 | DT->changeImmediateDominator(BB: cast<BasicBlock>(Val&: VMap[BB]), |
1058 | NewBB: cast<BasicBlock>(Val&: VMap[IDomBB])); |
1059 | } |
1060 | |
1061 | // Move them physically from the end of the block list. |
1062 | F->splice(ToIt: Before->getIterator(), FromF: F, FromIt: NewPH->getIterator()); |
1063 | F->splice(ToIt: Before->getIterator(), FromF: F, FromBeginIt: NewLoop->getHeader()->getIterator(), |
1064 | FromEndIt: F->end()); |
1065 | |
1066 | return NewLoop; |
1067 | } |
1068 | |
1069 | /// Duplicate non-Phi instructions from the beginning of block up to |
1070 | /// StopAt instruction into a split block between BB and its predecessor. |
1071 | BasicBlock *llvm::DuplicateInstructionsInSplitBetween( |
1072 | BasicBlock *BB, BasicBlock *PredBB, Instruction *StopAt, |
1073 | ValueToValueMapTy &ValueMapping, DomTreeUpdater &DTU) { |
1074 | |
1075 | assert(count(successors(PredBB), BB) == 1 && |
1076 | "There must be a single edge between PredBB and BB!" ); |
1077 | // We are going to have to map operands from the original BB block to the new |
1078 | // copy of the block 'NewBB'. If there are PHI nodes in BB, evaluate them to |
1079 | // account for entry from PredBB. |
1080 | BasicBlock::iterator BI = BB->begin(); |
1081 | for (; PHINode *PN = dyn_cast<PHINode>(Val&: BI); ++BI) |
1082 | ValueMapping[PN] = PN->getIncomingValueForBlock(BB: PredBB); |
1083 | |
1084 | BasicBlock *NewBB = SplitEdge(From: PredBB, To: BB); |
1085 | NewBB->setName(PredBB->getName() + ".split" ); |
1086 | Instruction *NewTerm = NewBB->getTerminator(); |
1087 | |
1088 | // FIXME: SplitEdge does not yet take a DTU, so we include the split edge |
1089 | // in the update set here. |
1090 | DTU.applyUpdates(Updates: {{DominatorTree::Delete, PredBB, BB}, |
1091 | {DominatorTree::Insert, PredBB, NewBB}, |
1092 | {DominatorTree::Insert, NewBB, BB}}); |
1093 | |
1094 | // Clone the non-phi instructions of BB into NewBB, keeping track of the |
1095 | // mapping and using it to remap operands in the cloned instructions. |
1096 | // Stop once we see the terminator too. This covers the case where BB's |
1097 | // terminator gets replaced and StopAt == BB's terminator. |
1098 | for (; StopAt != &*BI && BB->getTerminator() != &*BI; ++BI) { |
1099 | Instruction *New = BI->clone(); |
1100 | New->setName(BI->getName()); |
1101 | New->insertBefore(InsertPos: NewTerm); |
1102 | New->cloneDebugInfoFrom(From: &*BI); |
1103 | ValueMapping[&*BI] = New; |
1104 | |
1105 | // Remap operands to patch up intra-block references. |
1106 | for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i) |
1107 | if (Instruction *Inst = dyn_cast<Instruction>(Val: New->getOperand(i))) { |
1108 | auto I = ValueMapping.find(Val: Inst); |
1109 | if (I != ValueMapping.end()) |
1110 | New->setOperand(i, Val: I->second); |
1111 | } |
1112 | } |
1113 | |
1114 | return NewBB; |
1115 | } |
1116 | |
1117 | void llvm::cloneNoAliasScopes(ArrayRef<MDNode *> NoAliasDeclScopes, |
1118 | DenseMap<MDNode *, MDNode *> &ClonedScopes, |
1119 | StringRef Ext, LLVMContext &Context) { |
1120 | MDBuilder MDB(Context); |
1121 | |
1122 | for (auto *ScopeList : NoAliasDeclScopes) { |
1123 | for (const auto &MDOperand : ScopeList->operands()) { |
1124 | if (MDNode *MD = dyn_cast<MDNode>(Val: MDOperand)) { |
1125 | AliasScopeNode SNANode(MD); |
1126 | |
1127 | std::string Name; |
1128 | auto ScopeName = SNANode.getName(); |
1129 | if (!ScopeName.empty()) |
1130 | Name = (Twine(ScopeName) + ":" + Ext).str(); |
1131 | else |
1132 | Name = std::string(Ext); |
1133 | |
1134 | MDNode *NewScope = MDB.createAnonymousAliasScope( |
1135 | Domain: const_cast<MDNode *>(SNANode.getDomain()), Name); |
1136 | ClonedScopes.insert(KV: std::make_pair(x&: MD, y&: NewScope)); |
1137 | } |
1138 | } |
1139 | } |
1140 | } |
1141 | |
1142 | void llvm::adaptNoAliasScopes(Instruction *I, |
1143 | const DenseMap<MDNode *, MDNode *> &ClonedScopes, |
1144 | LLVMContext &Context) { |
1145 | auto CloneScopeList = [&](const MDNode *ScopeList) -> MDNode * { |
1146 | bool NeedsReplacement = false; |
1147 | SmallVector<Metadata *, 8> NewScopeList; |
1148 | for (const auto &MDOp : ScopeList->operands()) { |
1149 | if (MDNode *MD = dyn_cast<MDNode>(Val: MDOp)) { |
1150 | if (auto *NewMD = ClonedScopes.lookup(Val: MD)) { |
1151 | NewScopeList.push_back(Elt: NewMD); |
1152 | NeedsReplacement = true; |
1153 | continue; |
1154 | } |
1155 | NewScopeList.push_back(Elt: MD); |
1156 | } |
1157 | } |
1158 | if (NeedsReplacement) |
1159 | return MDNode::get(Context, MDs: NewScopeList); |
1160 | return nullptr; |
1161 | }; |
1162 | |
1163 | if (auto *Decl = dyn_cast<NoAliasScopeDeclInst>(Val: I)) |
1164 | if (auto *NewScopeList = CloneScopeList(Decl->getScopeList())) |
1165 | Decl->setScopeList(NewScopeList); |
1166 | |
1167 | auto replaceWhenNeeded = [&](unsigned MD_ID) { |
1168 | if (const MDNode *CSNoAlias = I->getMetadata(KindID: MD_ID)) |
1169 | if (auto *NewScopeList = CloneScopeList(CSNoAlias)) |
1170 | I->setMetadata(KindID: MD_ID, Node: NewScopeList); |
1171 | }; |
1172 | replaceWhenNeeded(LLVMContext::MD_noalias); |
1173 | replaceWhenNeeded(LLVMContext::MD_alias_scope); |
1174 | } |
1175 | |
1176 | void llvm::cloneAndAdaptNoAliasScopes(ArrayRef<MDNode *> NoAliasDeclScopes, |
1177 | ArrayRef<BasicBlock *> NewBlocks, |
1178 | LLVMContext &Context, StringRef Ext) { |
1179 | if (NoAliasDeclScopes.empty()) |
1180 | return; |
1181 | |
1182 | DenseMap<MDNode *, MDNode *> ClonedScopes; |
1183 | LLVM_DEBUG(dbgs() << "cloneAndAdaptNoAliasScopes: cloning " |
1184 | << NoAliasDeclScopes.size() << " node(s)\n" ); |
1185 | |
1186 | cloneNoAliasScopes(NoAliasDeclScopes, ClonedScopes, Ext, Context); |
1187 | // Identify instructions using metadata that needs adaptation |
1188 | for (BasicBlock *NewBlock : NewBlocks) |
1189 | for (Instruction &I : *NewBlock) |
1190 | adaptNoAliasScopes(I: &I, ClonedScopes, Context); |
1191 | } |
1192 | |
1193 | void llvm::cloneAndAdaptNoAliasScopes(ArrayRef<MDNode *> NoAliasDeclScopes, |
1194 | Instruction *IStart, Instruction *IEnd, |
1195 | LLVMContext &Context, StringRef Ext) { |
1196 | if (NoAliasDeclScopes.empty()) |
1197 | return; |
1198 | |
1199 | DenseMap<MDNode *, MDNode *> ClonedScopes; |
1200 | LLVM_DEBUG(dbgs() << "cloneAndAdaptNoAliasScopes: cloning " |
1201 | << NoAliasDeclScopes.size() << " node(s)\n" ); |
1202 | |
1203 | cloneNoAliasScopes(NoAliasDeclScopes, ClonedScopes, Ext, Context); |
1204 | // Identify instructions using metadata that needs adaptation |
1205 | assert(IStart->getParent() == IEnd->getParent() && "different basic block ?" ); |
1206 | auto ItStart = IStart->getIterator(); |
1207 | auto ItEnd = IEnd->getIterator(); |
1208 | ++ItEnd; // IEnd is included, increment ItEnd to get the end of the range |
1209 | for (auto &I : llvm::make_range(x: ItStart, y: ItEnd)) |
1210 | adaptNoAliasScopes(I: &I, ClonedScopes, Context); |
1211 | } |
1212 | |
1213 | void llvm::identifyNoAliasScopesToClone( |
1214 | ArrayRef<BasicBlock *> BBs, SmallVectorImpl<MDNode *> &NoAliasDeclScopes) { |
1215 | for (BasicBlock *BB : BBs) |
1216 | for (Instruction &I : *BB) |
1217 | if (auto *Decl = dyn_cast<NoAliasScopeDeclInst>(Val: &I)) |
1218 | NoAliasDeclScopes.push_back(Elt: Decl->getScopeList()); |
1219 | } |
1220 | |
1221 | void llvm::identifyNoAliasScopesToClone( |
1222 | BasicBlock::iterator Start, BasicBlock::iterator End, |
1223 | SmallVectorImpl<MDNode *> &NoAliasDeclScopes) { |
1224 | for (Instruction &I : make_range(x: Start, y: End)) |
1225 | if (auto *Decl = dyn_cast<NoAliasScopeDeclInst>(Val: &I)) |
1226 | NoAliasDeclScopes.push_back(Elt: Decl->getScopeList()); |
1227 | } |
1228 | |