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