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