10b57cec5SDimitry Andric //===- CloneFunction.cpp - Clone a function into another function ---------===//
20b57cec5SDimitry Andric //
30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information.
50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
60b57cec5SDimitry Andric //
70b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
80b57cec5SDimitry Andric //
90b57cec5SDimitry Andric // This file implements the CloneFunctionInto interface, which is used as the
100b57cec5SDimitry Andric // low-level function cloner. This is used by the CloneFunction and function
110b57cec5SDimitry Andric // inliner to do the dirty work of copying the body of a function around.
120b57cec5SDimitry Andric //
130b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
140b57cec5SDimitry Andric
150b57cec5SDimitry Andric #include "llvm/ADT/SetVector.h"
160b57cec5SDimitry Andric #include "llvm/ADT/SmallVector.h"
170b57cec5SDimitry Andric #include "llvm/Analysis/DomTreeUpdater.h"
180b57cec5SDimitry Andric #include "llvm/Analysis/InstructionSimplify.h"
190b57cec5SDimitry Andric #include "llvm/Analysis/LoopInfo.h"
200b57cec5SDimitry Andric #include "llvm/IR/CFG.h"
210b57cec5SDimitry Andric #include "llvm/IR/Constants.h"
220b57cec5SDimitry Andric #include "llvm/IR/DebugInfo.h"
230b57cec5SDimitry Andric #include "llvm/IR/DerivedTypes.h"
240b57cec5SDimitry Andric #include "llvm/IR/Function.h"
250b57cec5SDimitry Andric #include "llvm/IR/Instructions.h"
260b57cec5SDimitry Andric #include "llvm/IR/IntrinsicInst.h"
270b57cec5SDimitry Andric #include "llvm/IR/LLVMContext.h"
28e8d8bef9SDimitry Andric #include "llvm/IR/MDBuilder.h"
290b57cec5SDimitry Andric #include "llvm/IR/Metadata.h"
300b57cec5SDimitry Andric #include "llvm/IR/Module.h"
310b57cec5SDimitry Andric #include "llvm/Transforms/Utils/BasicBlockUtils.h"
320b57cec5SDimitry Andric #include "llvm/Transforms/Utils/Cloning.h"
330b57cec5SDimitry Andric #include "llvm/Transforms/Utils/Local.h"
340b57cec5SDimitry Andric #include "llvm/Transforms/Utils/ValueMapper.h"
350b57cec5SDimitry Andric #include <map>
36bdd1243dSDimitry Andric #include <optional>
370b57cec5SDimitry Andric using namespace llvm;
380b57cec5SDimitry Andric
39e8d8bef9SDimitry Andric #define DEBUG_TYPE "clone-function"
40e8d8bef9SDimitry Andric
410b57cec5SDimitry Andric /// See comments in Cloning.h.
CloneBasicBlock(const BasicBlock * BB,ValueToValueMapTy & VMap,const Twine & NameSuffix,Function * F,ClonedCodeInfo * CodeInfo,DebugInfoFinder * DIFinder)420b57cec5SDimitry Andric BasicBlock *llvm::CloneBasicBlock(const BasicBlock *BB, ValueToValueMapTy &VMap,
430b57cec5SDimitry Andric const Twine &NameSuffix, Function *F,
440b57cec5SDimitry Andric ClonedCodeInfo *CodeInfo,
450b57cec5SDimitry Andric DebugInfoFinder *DIFinder) {
460b57cec5SDimitry Andric BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), "", F);
475f757f3fSDimitry Andric NewBB->IsNewDbgInfoFormat = BB->IsNewDbgInfoFormat;
480b57cec5SDimitry Andric if (BB->hasName())
490b57cec5SDimitry Andric NewBB->setName(BB->getName() + NameSuffix);
500b57cec5SDimitry Andric
51bdd1243dSDimitry Andric bool hasCalls = false, hasDynamicAllocas = false, hasMemProfMetadata = false;
520b57cec5SDimitry Andric Module *TheModule = F ? F->getParent() : nullptr;
530b57cec5SDimitry Andric
540b57cec5SDimitry Andric // Loop over all instructions, and copy them over.
550b57cec5SDimitry Andric for (const Instruction &I : *BB) {
560b57cec5SDimitry Andric if (DIFinder && TheModule)
570b57cec5SDimitry Andric DIFinder->processInstruction(*TheModule, I);
580b57cec5SDimitry Andric
590b57cec5SDimitry Andric Instruction *NewInst = I.clone();
600b57cec5SDimitry Andric if (I.hasName())
610b57cec5SDimitry Andric NewInst->setName(I.getName() + NameSuffix);
625f757f3fSDimitry Andric
635f757f3fSDimitry Andric NewInst->insertBefore(*NewBB, NewBB->end());
645f757f3fSDimitry Andric NewInst->cloneDebugInfoFrom(&I);
655f757f3fSDimitry Andric
660b57cec5SDimitry Andric VMap[&I] = NewInst; // Add instruction map to value.
670b57cec5SDimitry Andric
68bdd1243dSDimitry Andric if (isa<CallInst>(I) && !I.isDebugOrPseudoInst()) {
69bdd1243dSDimitry Andric hasCalls = true;
70bdd1243dSDimitry Andric hasMemProfMetadata |= I.hasMetadata(LLVMContext::MD_memprof);
71bdd1243dSDimitry Andric }
720b57cec5SDimitry Andric if (const AllocaInst *AI = dyn_cast<AllocaInst>(&I)) {
735ffd83dbSDimitry Andric if (!AI->isStaticAlloca()) {
740b57cec5SDimitry Andric hasDynamicAllocas = true;
750b57cec5SDimitry Andric }
760b57cec5SDimitry Andric }
775ffd83dbSDimitry Andric }
780b57cec5SDimitry Andric
790b57cec5SDimitry Andric if (CodeInfo) {
800b57cec5SDimitry Andric CodeInfo->ContainsCalls |= hasCalls;
81bdd1243dSDimitry Andric CodeInfo->ContainsMemProfMetadata |= hasMemProfMetadata;
820b57cec5SDimitry Andric CodeInfo->ContainsDynamicAllocas |= hasDynamicAllocas;
830b57cec5SDimitry Andric }
840b57cec5SDimitry Andric return NewBB;
850b57cec5SDimitry Andric }
860b57cec5SDimitry Andric
870b57cec5SDimitry Andric // Clone OldFunc into NewFunc, transforming the old arguments into references to
880b57cec5SDimitry Andric // VMap values.
890b57cec5SDimitry Andric //
CloneFunctionInto(Function * NewFunc,const Function * OldFunc,ValueToValueMapTy & VMap,CloneFunctionChangeType Changes,SmallVectorImpl<ReturnInst * > & Returns,const char * NameSuffix,ClonedCodeInfo * CodeInfo,ValueMapTypeRemapper * TypeMapper,ValueMaterializer * Materializer)900b57cec5SDimitry Andric void llvm::CloneFunctionInto(Function *NewFunc, const Function *OldFunc,
910b57cec5SDimitry Andric ValueToValueMapTy &VMap,
92fe6060f1SDimitry Andric CloneFunctionChangeType Changes,
930b57cec5SDimitry Andric SmallVectorImpl<ReturnInst *> &Returns,
940b57cec5SDimitry Andric const char *NameSuffix, ClonedCodeInfo *CodeInfo,
950b57cec5SDimitry Andric ValueMapTypeRemapper *TypeMapper,
960b57cec5SDimitry Andric ValueMaterializer *Materializer) {
975f757f3fSDimitry Andric NewFunc->setIsNewDbgInfoFormat(OldFunc->IsNewDbgInfoFormat);
980b57cec5SDimitry Andric assert(NameSuffix && "NameSuffix cannot be null!");
990b57cec5SDimitry Andric
1000b57cec5SDimitry Andric #ifndef NDEBUG
1010b57cec5SDimitry Andric for (const Argument &I : OldFunc->args())
1020b57cec5SDimitry Andric assert(VMap.count(&I) && "No mapping from source argument specified!");
1030b57cec5SDimitry Andric #endif
1040b57cec5SDimitry Andric
105fe6060f1SDimitry Andric bool ModuleLevelChanges = Changes > CloneFunctionChangeType::LocalChangesOnly;
106fe6060f1SDimitry Andric
1070b57cec5SDimitry Andric // Copy all attributes other than those stored in the AttributeList. We need
1080b57cec5SDimitry Andric // to remap the parameter indices of the AttributeList.
1090b57cec5SDimitry Andric AttributeList NewAttrs = NewFunc->getAttributes();
1100b57cec5SDimitry Andric NewFunc->copyAttributesFrom(OldFunc);
1110b57cec5SDimitry Andric NewFunc->setAttributes(NewAttrs);
1120b57cec5SDimitry Andric
113bdd1243dSDimitry Andric const RemapFlags FuncGlobalRefFlags =
114bdd1243dSDimitry Andric ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges;
115bdd1243dSDimitry Andric
1160b57cec5SDimitry Andric // Fix up the personality function that got copied over.
1170b57cec5SDimitry Andric if (OldFunc->hasPersonalityFn())
118bdd1243dSDimitry Andric NewFunc->setPersonalityFn(MapValue(OldFunc->getPersonalityFn(), VMap,
119bdd1243dSDimitry Andric FuncGlobalRefFlags, TypeMapper,
120bdd1243dSDimitry Andric Materializer));
121bdd1243dSDimitry Andric
122bdd1243dSDimitry Andric if (OldFunc->hasPrefixData()) {
123bdd1243dSDimitry Andric NewFunc->setPrefixData(MapValue(OldFunc->getPrefixData(), VMap,
124bdd1243dSDimitry Andric FuncGlobalRefFlags, TypeMapper,
125bdd1243dSDimitry Andric Materializer));
126bdd1243dSDimitry Andric }
127bdd1243dSDimitry Andric
128bdd1243dSDimitry Andric if (OldFunc->hasPrologueData()) {
129bdd1243dSDimitry Andric NewFunc->setPrologueData(MapValue(OldFunc->getPrologueData(), VMap,
130bdd1243dSDimitry Andric FuncGlobalRefFlags, TypeMapper,
131bdd1243dSDimitry Andric Materializer));
132bdd1243dSDimitry Andric }
1330b57cec5SDimitry Andric
1340b57cec5SDimitry Andric SmallVector<AttributeSet, 4> NewArgAttrs(NewFunc->arg_size());
1350b57cec5SDimitry Andric AttributeList OldAttrs = OldFunc->getAttributes();
1360b57cec5SDimitry Andric
1370b57cec5SDimitry Andric // Clone any argument attributes that are present in the VMap.
1380b57cec5SDimitry Andric for (const Argument &OldArg : OldFunc->args()) {
1390b57cec5SDimitry Andric if (Argument *NewArg = dyn_cast<Argument>(VMap[&OldArg])) {
1400b57cec5SDimitry Andric NewArgAttrs[NewArg->getArgNo()] =
141349cc55cSDimitry Andric OldAttrs.getParamAttrs(OldArg.getArgNo());
1420b57cec5SDimitry Andric }
1430b57cec5SDimitry Andric }
1440b57cec5SDimitry Andric
1450b57cec5SDimitry Andric NewFunc->setAttributes(
146349cc55cSDimitry Andric AttributeList::get(NewFunc->getContext(), OldAttrs.getFnAttrs(),
147349cc55cSDimitry Andric OldAttrs.getRetAttrs(), NewArgAttrs));
1480b57cec5SDimitry Andric
149e8d8bef9SDimitry Andric // Everything else beyond this point deals with function instructions,
150e8d8bef9SDimitry Andric // so if we are dealing with a function declaration, we're done.
151e8d8bef9SDimitry Andric if (OldFunc->isDeclaration())
152e8d8bef9SDimitry Andric return;
1530b57cec5SDimitry Andric
154fe6060f1SDimitry Andric // When we remap instructions within the same module, we want to avoid
155fe6060f1SDimitry Andric // duplicating inlined DISubprograms, so record all subprograms we find as we
156fe6060f1SDimitry Andric // duplicate instructions and then freeze them in the MD map. We also record
157fe6060f1SDimitry Andric // information about dbg.value and dbg.declare to avoid duplicating the
158fe6060f1SDimitry Andric // types.
159bdd1243dSDimitry Andric std::optional<DebugInfoFinder> DIFinder;
160fe6060f1SDimitry Andric
161fe6060f1SDimitry Andric // Track the subprogram attachment that needs to be cloned to fine-tune the
162fe6060f1SDimitry Andric // mapping within the same module.
163fe6060f1SDimitry Andric DISubprogram *SPClonedWithinModule = nullptr;
164fe6060f1SDimitry Andric if (Changes < CloneFunctionChangeType::DifferentModule) {
165fe6060f1SDimitry Andric assert((NewFunc->getParent() == nullptr ||
166fe6060f1SDimitry Andric NewFunc->getParent() == OldFunc->getParent()) &&
167fe6060f1SDimitry Andric "Expected NewFunc to have the same parent, or no parent");
168fe6060f1SDimitry Andric
169fe6060f1SDimitry Andric // Need to find subprograms, types, and compile units.
170fe6060f1SDimitry Andric DIFinder.emplace();
171fe6060f1SDimitry Andric
172fe6060f1SDimitry Andric SPClonedWithinModule = OldFunc->getSubprogram();
173fe6060f1SDimitry Andric if (SPClonedWithinModule)
174fe6060f1SDimitry Andric DIFinder->processSubprogram(SPClonedWithinModule);
175fe6060f1SDimitry Andric } else {
176fe6060f1SDimitry Andric assert((NewFunc->getParent() == nullptr ||
177fe6060f1SDimitry Andric NewFunc->getParent() != OldFunc->getParent()) &&
178fe6060f1SDimitry Andric "Expected NewFunc to have different parents, or no parent");
179fe6060f1SDimitry Andric
180fe6060f1SDimitry Andric if (Changes == CloneFunctionChangeType::DifferentModule) {
181fe6060f1SDimitry Andric assert(NewFunc->getParent() &&
182fe6060f1SDimitry Andric "Need parent of new function to maintain debug info invariants");
183fe6060f1SDimitry Andric
184fe6060f1SDimitry Andric // Need to find all the compile units.
185fe6060f1SDimitry Andric DIFinder.emplace();
186fe6060f1SDimitry Andric }
187fe6060f1SDimitry Andric }
1880b57cec5SDimitry Andric
1890b57cec5SDimitry Andric // Loop over all of the basic blocks in the function, cloning them as
1900b57cec5SDimitry Andric // appropriate. Note that we save BE this way in order to handle cloning of
1910b57cec5SDimitry Andric // recursive functions into themselves.
192fe6060f1SDimitry Andric for (const BasicBlock &BB : *OldFunc) {
1930b57cec5SDimitry Andric
1940b57cec5SDimitry Andric // Create a new basic block and copy instructions into it!
1950b57cec5SDimitry Andric BasicBlock *CBB = CloneBasicBlock(&BB, VMap, NameSuffix, NewFunc, CodeInfo,
196fe6060f1SDimitry Andric DIFinder ? &*DIFinder : nullptr);
1970b57cec5SDimitry Andric
1980b57cec5SDimitry Andric // Add basic block mapping.
1990b57cec5SDimitry Andric VMap[&BB] = CBB;
2000b57cec5SDimitry Andric
2010b57cec5SDimitry Andric // It is only legal to clone a function if a block address within that
2020b57cec5SDimitry Andric // function is never referenced outside of the function. Given that, we
2030b57cec5SDimitry Andric // want to map block addresses from the old function to block addresses in
2040b57cec5SDimitry Andric // the clone. (This is different from the generic ValueMapper
2050b57cec5SDimitry Andric // implementation, which generates an invalid blockaddress when
2060b57cec5SDimitry Andric // cloning a function.)
2070b57cec5SDimitry Andric if (BB.hasAddressTaken()) {
2080b57cec5SDimitry Andric Constant *OldBBAddr = BlockAddress::get(const_cast<Function *>(OldFunc),
2090b57cec5SDimitry Andric const_cast<BasicBlock *>(&BB));
2100b57cec5SDimitry Andric VMap[OldBBAddr] = BlockAddress::get(NewFunc, CBB);
2110b57cec5SDimitry Andric }
2120b57cec5SDimitry Andric
2130b57cec5SDimitry Andric // Note return instructions for the caller.
2140b57cec5SDimitry Andric if (ReturnInst *RI = dyn_cast<ReturnInst>(CBB->getTerminator()))
2150b57cec5SDimitry Andric Returns.push_back(RI);
2160b57cec5SDimitry Andric }
2170b57cec5SDimitry Andric
218fe6060f1SDimitry Andric if (Changes < CloneFunctionChangeType::DifferentModule &&
219fe6060f1SDimitry Andric DIFinder->subprogram_count() > 0) {
220fe6060f1SDimitry Andric // Turn on module-level changes, since we need to clone (some of) the
221fe6060f1SDimitry Andric // debug info metadata.
222fe6060f1SDimitry Andric //
223fe6060f1SDimitry Andric // FIXME: Metadata effectively owned by a function should be made
224fe6060f1SDimitry Andric // local, and only that local metadata should be cloned.
225fe6060f1SDimitry Andric ModuleLevelChanges = true;
2260b57cec5SDimitry Andric
227fe6060f1SDimitry Andric auto mapToSelfIfNew = [&VMap](MDNode *N) {
228fe6060f1SDimitry Andric // Avoid clobbering an existing mapping.
229fe6060f1SDimitry Andric (void)VMap.MD().try_emplace(N, N);
230fe6060f1SDimitry Andric };
2310b57cec5SDimitry Andric
232fe6060f1SDimitry Andric // Avoid cloning types, compile units, and (other) subprograms.
233fcaf7f86SDimitry Andric SmallPtrSet<const DISubprogram *, 16> MappedToSelfSPs;
234fcaf7f86SDimitry Andric for (DISubprogram *ISP : DIFinder->subprograms()) {
235fcaf7f86SDimitry Andric if (ISP != SPClonedWithinModule) {
236fe6060f1SDimitry Andric mapToSelfIfNew(ISP);
237fcaf7f86SDimitry Andric MappedToSelfSPs.insert(ISP);
238fcaf7f86SDimitry Andric }
239fcaf7f86SDimitry Andric }
240fcaf7f86SDimitry Andric
241fcaf7f86SDimitry Andric // If a subprogram isn't going to be cloned skip its lexical blocks as well.
242fcaf7f86SDimitry Andric for (DIScope *S : DIFinder->scopes()) {
243fcaf7f86SDimitry Andric auto *LScope = dyn_cast<DILocalScope>(S);
244fcaf7f86SDimitry Andric if (LScope && MappedToSelfSPs.count(LScope->getSubprogram()))
245fcaf7f86SDimitry Andric mapToSelfIfNew(S);
246fcaf7f86SDimitry Andric }
2470b57cec5SDimitry Andric
248fe6060f1SDimitry Andric for (DICompileUnit *CU : DIFinder->compile_units())
249fe6060f1SDimitry Andric mapToSelfIfNew(CU);
250fe6060f1SDimitry Andric
251fe6060f1SDimitry Andric for (DIType *Type : DIFinder->types())
252fe6060f1SDimitry Andric mapToSelfIfNew(Type);
253fe6060f1SDimitry Andric } else {
254fe6060f1SDimitry Andric assert(!SPClonedWithinModule &&
255fe6060f1SDimitry Andric "Subprogram should be in DIFinder->subprogram_count()...");
256fe6060f1SDimitry Andric }
257fe6060f1SDimitry Andric
258fe6060f1SDimitry Andric const auto RemapFlag = ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges;
259e8d8bef9SDimitry Andric // Duplicate the metadata that is attached to the cloned function.
260e8d8bef9SDimitry Andric // Subprograms/CUs/types that were already mapped to themselves won't be
261e8d8bef9SDimitry Andric // duplicated.
262e8d8bef9SDimitry Andric SmallVector<std::pair<unsigned, MDNode *>, 1> MDs;
263e8d8bef9SDimitry Andric OldFunc->getAllMetadata(MDs);
264e8d8bef9SDimitry Andric for (auto MD : MDs) {
265fe6060f1SDimitry Andric NewFunc->addMetadata(MD.first, *MapMetadata(MD.second, VMap, RemapFlag,
266e8d8bef9SDimitry Andric TypeMapper, Materializer));
267e8d8bef9SDimitry Andric }
268e8d8bef9SDimitry Andric
269fe6060f1SDimitry Andric // Loop over all of the instructions in the new function, fixing up operand
2700b57cec5SDimitry Andric // references as we go. This uses VMap to do all the hard work.
271fe6060f1SDimitry Andric for (Function::iterator
272fe6060f1SDimitry Andric BB = cast<BasicBlock>(VMap[&OldFunc->front()])->getIterator(),
2730b57cec5SDimitry Andric BE = NewFunc->end();
2740b57cec5SDimitry Andric BB != BE; ++BB)
2755f757f3fSDimitry Andric // Loop over all instructions, fixing each one as we find it, and any
2765f757f3fSDimitry Andric // attached debug-info records.
2775f757f3fSDimitry Andric for (Instruction &II : *BB) {
278fe6060f1SDimitry Andric RemapInstruction(&II, VMap, RemapFlag, TypeMapper, Materializer);
2795f757f3fSDimitry Andric RemapDPValueRange(II.getModule(), II.getDbgValueRange(), VMap, RemapFlag,
2805f757f3fSDimitry Andric TypeMapper, Materializer);
2815f757f3fSDimitry Andric }
2828bcb0991SDimitry Andric
283fe6060f1SDimitry Andric // Only update !llvm.dbg.cu for DifferentModule (not CloneModule). In the
284fe6060f1SDimitry Andric // same module, the compile unit will already be listed (or not). When
285fe6060f1SDimitry Andric // cloning a module, CloneModule() will handle creating the named metadata.
286fe6060f1SDimitry Andric if (Changes != CloneFunctionChangeType::DifferentModule)
287fe6060f1SDimitry Andric return;
288fe6060f1SDimitry Andric
289fe6060f1SDimitry Andric // Update !llvm.dbg.cu with compile units added to the new module if this
290fe6060f1SDimitry Andric // function is being cloned in isolation.
291fe6060f1SDimitry Andric //
292fe6060f1SDimitry Andric // FIXME: This is making global / module-level changes, which doesn't seem
293fe6060f1SDimitry Andric // like the right encapsulation Consider dropping the requirement to update
294fe6060f1SDimitry Andric // !llvm.dbg.cu (either obsoleting the node, or restricting it to
295fe6060f1SDimitry Andric // non-discardable compile units) instead of discovering compile units by
296fe6060f1SDimitry Andric // visiting the metadata attached to global values, which would allow this
297fe6060f1SDimitry Andric // code to be deleted. Alternatively, perhaps give responsibility for this
298fe6060f1SDimitry Andric // update to CloneFunctionInto's callers.
2998bcb0991SDimitry Andric auto *NewModule = NewFunc->getParent();
3008bcb0991SDimitry Andric auto *NMD = NewModule->getOrInsertNamedMetadata("llvm.dbg.cu");
3018bcb0991SDimitry Andric // Avoid multiple insertions of the same DICompileUnit to NMD.
3028bcb0991SDimitry Andric SmallPtrSet<const void *, 8> Visited;
3038bcb0991SDimitry Andric for (auto *Operand : NMD->operands())
3048bcb0991SDimitry Andric Visited.insert(Operand);
305fe6060f1SDimitry Andric for (auto *Unit : DIFinder->compile_units()) {
306fe6060f1SDimitry Andric MDNode *MappedUnit =
307fe6060f1SDimitry Andric MapMetadata(Unit, VMap, RF_None, TypeMapper, Materializer);
308fe6060f1SDimitry Andric if (Visited.insert(MappedUnit).second)
309fe6060f1SDimitry Andric NMD->addOperand(MappedUnit);
3108bcb0991SDimitry Andric }
3110b57cec5SDimitry Andric }
3120b57cec5SDimitry Andric
3130b57cec5SDimitry Andric /// Return a copy of the specified function and add it to that function's
3140b57cec5SDimitry Andric /// module. Also, any references specified in the VMap are changed to refer to
3150b57cec5SDimitry Andric /// their mapped value instead of the original one. If any of the arguments to
3160b57cec5SDimitry Andric /// the function are in the VMap, the arguments are deleted from the resultant
3170b57cec5SDimitry Andric /// function. The VMap is updated to include mappings from all of the
3180b57cec5SDimitry Andric /// instructions and basicblocks in the function from their old to new values.
3190b57cec5SDimitry Andric ///
CloneFunction(Function * F,ValueToValueMapTy & VMap,ClonedCodeInfo * CodeInfo)3200b57cec5SDimitry Andric Function *llvm::CloneFunction(Function *F, ValueToValueMapTy &VMap,
3210b57cec5SDimitry Andric ClonedCodeInfo *CodeInfo) {
3220b57cec5SDimitry Andric std::vector<Type *> ArgTypes;
3230b57cec5SDimitry Andric
3240b57cec5SDimitry Andric // The user might be deleting arguments to the function by specifying them in
3250b57cec5SDimitry Andric // the VMap. If so, we need to not add the arguments to the arg ty vector
3260b57cec5SDimitry Andric //
3270b57cec5SDimitry Andric for (const Argument &I : F->args())
3280b57cec5SDimitry Andric if (VMap.count(&I) == 0) // Haven't mapped the argument to anything yet?
3290b57cec5SDimitry Andric ArgTypes.push_back(I.getType());
3300b57cec5SDimitry Andric
3310b57cec5SDimitry Andric // Create a new function type...
332fe6060f1SDimitry Andric FunctionType *FTy =
333fe6060f1SDimitry Andric FunctionType::get(F->getFunctionType()->getReturnType(), ArgTypes,
334fe6060f1SDimitry Andric F->getFunctionType()->isVarArg());
3350b57cec5SDimitry Andric
3360b57cec5SDimitry Andric // Create the new function...
3370b57cec5SDimitry Andric Function *NewF = Function::Create(FTy, F->getLinkage(), F->getAddressSpace(),
3380b57cec5SDimitry Andric F->getName(), F->getParent());
3395f757f3fSDimitry Andric NewF->setIsNewDbgInfoFormat(F->IsNewDbgInfoFormat);
3400b57cec5SDimitry Andric
3410b57cec5SDimitry Andric // Loop over the arguments, copying the names of the mapped arguments over...
3420b57cec5SDimitry Andric Function::arg_iterator DestI = NewF->arg_begin();
3430b57cec5SDimitry Andric for (const Argument &I : F->args())
3440b57cec5SDimitry Andric if (VMap.count(&I) == 0) { // Is this argument preserved?
3450b57cec5SDimitry Andric DestI->setName(I.getName()); // Copy the name over...
3460b57cec5SDimitry Andric VMap[&I] = &*DestI++; // Add mapping to VMap
3470b57cec5SDimitry Andric }
3480b57cec5SDimitry Andric
3490b57cec5SDimitry Andric SmallVector<ReturnInst *, 8> Returns; // Ignore returns cloned.
350fe6060f1SDimitry Andric CloneFunctionInto(NewF, F, VMap, CloneFunctionChangeType::LocalChangesOnly,
351fe6060f1SDimitry Andric Returns, "", CodeInfo);
3520b57cec5SDimitry Andric
3530b57cec5SDimitry Andric return NewF;
3540b57cec5SDimitry Andric }
3550b57cec5SDimitry Andric
3560b57cec5SDimitry Andric namespace {
3570b57cec5SDimitry Andric /// This is a private class used to implement CloneAndPruneFunctionInto.
3580b57cec5SDimitry Andric struct PruningFunctionCloner {
3590b57cec5SDimitry Andric Function *NewFunc;
3600b57cec5SDimitry Andric const Function *OldFunc;
3610b57cec5SDimitry Andric ValueToValueMapTy &VMap;
3620b57cec5SDimitry Andric bool ModuleLevelChanges;
3630b57cec5SDimitry Andric const char *NameSuffix;
3640b57cec5SDimitry Andric ClonedCodeInfo *CodeInfo;
36581ad6265SDimitry Andric bool HostFuncIsStrictFP;
36681ad6265SDimitry Andric
36781ad6265SDimitry Andric Instruction *cloneInstruction(BasicBlock::const_iterator II);
3680b57cec5SDimitry Andric
3690b57cec5SDimitry Andric public:
PruningFunctionCloner__anon9ac1642d0211::PruningFunctionCloner3700b57cec5SDimitry Andric PruningFunctionCloner(Function *newFunc, const Function *oldFunc,
3710b57cec5SDimitry Andric ValueToValueMapTy &valueMap, bool moduleLevelChanges,
3720b57cec5SDimitry Andric const char *nameSuffix, ClonedCodeInfo *codeInfo)
3730b57cec5SDimitry Andric : NewFunc(newFunc), OldFunc(oldFunc), VMap(valueMap),
3740b57cec5SDimitry Andric ModuleLevelChanges(moduleLevelChanges), NameSuffix(nameSuffix),
37581ad6265SDimitry Andric CodeInfo(codeInfo) {
37681ad6265SDimitry Andric HostFuncIsStrictFP =
37781ad6265SDimitry Andric newFunc->getAttributes().hasFnAttr(Attribute::StrictFP);
37881ad6265SDimitry Andric }
3790b57cec5SDimitry Andric
3800b57cec5SDimitry Andric /// The specified block is found to be reachable, clone it and
3810b57cec5SDimitry Andric /// anything that it can reach.
382fe6060f1SDimitry Andric void CloneBlock(const BasicBlock *BB, BasicBlock::const_iterator StartingInst,
3830b57cec5SDimitry Andric std::vector<const BasicBlock *> &ToClone);
3840b57cec5SDimitry Andric };
385fe6060f1SDimitry Andric } // namespace
3860b57cec5SDimitry Andric
hasRoundingModeOperand(Intrinsic::ID CIID)38781ad6265SDimitry Andric static bool hasRoundingModeOperand(Intrinsic::ID CIID) {
38881ad6265SDimitry Andric switch (CIID) {
38981ad6265SDimitry Andric #define INSTRUCTION(NAME, NARG, ROUND_MODE, INTRINSIC) \
39081ad6265SDimitry Andric case Intrinsic::INTRINSIC: \
39181ad6265SDimitry Andric return ROUND_MODE == 1;
39281ad6265SDimitry Andric #define FUNCTION INSTRUCTION
39381ad6265SDimitry Andric #include "llvm/IR/ConstrainedOps.def"
39481ad6265SDimitry Andric default:
39581ad6265SDimitry Andric llvm_unreachable("Unexpected constrained intrinsic id");
39681ad6265SDimitry Andric }
39781ad6265SDimitry Andric }
39881ad6265SDimitry Andric
39981ad6265SDimitry Andric Instruction *
cloneInstruction(BasicBlock::const_iterator II)40081ad6265SDimitry Andric PruningFunctionCloner::cloneInstruction(BasicBlock::const_iterator II) {
40181ad6265SDimitry Andric const Instruction &OldInst = *II;
40281ad6265SDimitry Andric Instruction *NewInst = nullptr;
40381ad6265SDimitry Andric if (HostFuncIsStrictFP) {
40481ad6265SDimitry Andric Intrinsic::ID CIID = getConstrainedIntrinsicID(OldInst);
40581ad6265SDimitry Andric if (CIID != Intrinsic::not_intrinsic) {
40681ad6265SDimitry Andric // Instead of cloning the instruction, a call to constrained intrinsic
40781ad6265SDimitry Andric // should be created.
40881ad6265SDimitry Andric // Assume the first arguments of constrained intrinsics are the same as
40981ad6265SDimitry Andric // the operands of original instruction.
41081ad6265SDimitry Andric
41181ad6265SDimitry Andric // Determine overloaded types of the intrinsic.
41281ad6265SDimitry Andric SmallVector<Type *, 2> TParams;
41381ad6265SDimitry Andric SmallVector<Intrinsic::IITDescriptor, 8> Descriptor;
41481ad6265SDimitry Andric getIntrinsicInfoTableEntries(CIID, Descriptor);
41581ad6265SDimitry Andric for (unsigned I = 0, E = Descriptor.size(); I != E; ++I) {
41681ad6265SDimitry Andric Intrinsic::IITDescriptor Operand = Descriptor[I];
41781ad6265SDimitry Andric switch (Operand.Kind) {
41881ad6265SDimitry Andric case Intrinsic::IITDescriptor::Argument:
41981ad6265SDimitry Andric if (Operand.getArgumentKind() !=
42081ad6265SDimitry Andric Intrinsic::IITDescriptor::AK_MatchType) {
42181ad6265SDimitry Andric if (I == 0)
42281ad6265SDimitry Andric TParams.push_back(OldInst.getType());
42381ad6265SDimitry Andric else
42481ad6265SDimitry Andric TParams.push_back(OldInst.getOperand(I - 1)->getType());
42581ad6265SDimitry Andric }
42681ad6265SDimitry Andric break;
42781ad6265SDimitry Andric case Intrinsic::IITDescriptor::SameVecWidthArgument:
42881ad6265SDimitry Andric ++I;
42981ad6265SDimitry Andric break;
43081ad6265SDimitry Andric default:
43181ad6265SDimitry Andric break;
43281ad6265SDimitry Andric }
43381ad6265SDimitry Andric }
43481ad6265SDimitry Andric
43581ad6265SDimitry Andric // Create intrinsic call.
43681ad6265SDimitry Andric LLVMContext &Ctx = NewFunc->getContext();
43781ad6265SDimitry Andric Function *IFn =
43881ad6265SDimitry Andric Intrinsic::getDeclaration(NewFunc->getParent(), CIID, TParams);
43981ad6265SDimitry Andric SmallVector<Value *, 4> Args;
44081ad6265SDimitry Andric unsigned NumOperands = OldInst.getNumOperands();
44181ad6265SDimitry Andric if (isa<CallInst>(OldInst))
44281ad6265SDimitry Andric --NumOperands;
44381ad6265SDimitry Andric for (unsigned I = 0; I < NumOperands; ++I) {
44481ad6265SDimitry Andric Value *Op = OldInst.getOperand(I);
44581ad6265SDimitry Andric Args.push_back(Op);
44681ad6265SDimitry Andric }
44781ad6265SDimitry Andric if (const auto *CmpI = dyn_cast<FCmpInst>(&OldInst)) {
44881ad6265SDimitry Andric FCmpInst::Predicate Pred = CmpI->getPredicate();
44981ad6265SDimitry Andric StringRef PredName = FCmpInst::getPredicateName(Pred);
45081ad6265SDimitry Andric Args.push_back(MetadataAsValue::get(Ctx, MDString::get(Ctx, PredName)));
45181ad6265SDimitry Andric }
45281ad6265SDimitry Andric
45381ad6265SDimitry Andric // The last arguments of a constrained intrinsic are metadata that
45481ad6265SDimitry Andric // represent rounding mode (absents in some intrinsics) and exception
45581ad6265SDimitry Andric // behavior. The inlined function uses default settings.
45681ad6265SDimitry Andric if (hasRoundingModeOperand(CIID))
45781ad6265SDimitry Andric Args.push_back(
45881ad6265SDimitry Andric MetadataAsValue::get(Ctx, MDString::get(Ctx, "round.tonearest")));
45981ad6265SDimitry Andric Args.push_back(
46081ad6265SDimitry Andric MetadataAsValue::get(Ctx, MDString::get(Ctx, "fpexcept.ignore")));
46181ad6265SDimitry Andric
46281ad6265SDimitry Andric NewInst = CallInst::Create(IFn, Args, OldInst.getName() + ".strict");
46381ad6265SDimitry Andric }
46481ad6265SDimitry Andric }
46581ad6265SDimitry Andric if (!NewInst)
46681ad6265SDimitry Andric NewInst = II->clone();
46781ad6265SDimitry Andric return NewInst;
46881ad6265SDimitry Andric }
46981ad6265SDimitry Andric
4700b57cec5SDimitry Andric /// The specified block is found to be reachable, clone it and
4710b57cec5SDimitry Andric /// anything that it can reach.
CloneBlock(const BasicBlock * BB,BasicBlock::const_iterator StartingInst,std::vector<const BasicBlock * > & ToClone)472fe6060f1SDimitry Andric void PruningFunctionCloner::CloneBlock(
473fe6060f1SDimitry Andric const BasicBlock *BB, BasicBlock::const_iterator StartingInst,
4740b57cec5SDimitry Andric std::vector<const BasicBlock *> &ToClone) {
4750b57cec5SDimitry Andric WeakTrackingVH &BBEntry = VMap[BB];
4760b57cec5SDimitry Andric
4770b57cec5SDimitry Andric // Have we already cloned this block?
478fe6060f1SDimitry Andric if (BBEntry)
479fe6060f1SDimitry Andric return;
4800b57cec5SDimitry Andric
4810b57cec5SDimitry Andric // Nope, clone it now.
4820b57cec5SDimitry Andric BasicBlock *NewBB;
48306c3fb27SDimitry Andric Twine NewName(BB->hasName() ? Twine(BB->getName()) + NameSuffix : "");
48406c3fb27SDimitry Andric BBEntry = NewBB = BasicBlock::Create(BB->getContext(), NewName, NewFunc);
4855f757f3fSDimitry Andric NewBB->IsNewDbgInfoFormat = BB->IsNewDbgInfoFormat;
4860b57cec5SDimitry Andric
4870b57cec5SDimitry Andric // It is only legal to clone a function if a block address within that
4880b57cec5SDimitry Andric // function is never referenced outside of the function. Given that, we
4890b57cec5SDimitry Andric // want to map block addresses from the old function to block addresses in
4900b57cec5SDimitry Andric // the clone. (This is different from the generic ValueMapper
4910b57cec5SDimitry Andric // implementation, which generates an invalid blockaddress when
4920b57cec5SDimitry Andric // cloning a function.)
4930b57cec5SDimitry Andric //
4940b57cec5SDimitry Andric // Note that we don't need to fix the mapping for unreachable blocks;
4950b57cec5SDimitry Andric // the default mapping there is safe.
4960b57cec5SDimitry Andric if (BB->hasAddressTaken()) {
4970b57cec5SDimitry Andric Constant *OldBBAddr = BlockAddress::get(const_cast<Function *>(OldFunc),
4980b57cec5SDimitry Andric const_cast<BasicBlock *>(BB));
4990b57cec5SDimitry Andric VMap[OldBBAddr] = BlockAddress::get(NewFunc, NewBB);
5000b57cec5SDimitry Andric }
5010b57cec5SDimitry Andric
5020b57cec5SDimitry Andric bool hasCalls = false, hasDynamicAllocas = false, hasStaticAllocas = false;
503bdd1243dSDimitry Andric bool hasMemProfMetadata = false;
5040b57cec5SDimitry Andric
5055f757f3fSDimitry Andric // Keep a cursor pointing at the last place we cloned debug-info records from.
5065f757f3fSDimitry Andric BasicBlock::const_iterator DbgCursor = StartingInst;
5075f757f3fSDimitry Andric auto CloneDbgRecordsToHere =
5085f757f3fSDimitry Andric [NewBB, &DbgCursor](Instruction *NewInst, BasicBlock::const_iterator II) {
5095f757f3fSDimitry Andric if (!NewBB->IsNewDbgInfoFormat)
5105f757f3fSDimitry Andric return;
5115f757f3fSDimitry Andric
5125f757f3fSDimitry Andric // Clone debug-info records onto this instruction. Iterate through any
5135f757f3fSDimitry Andric // source-instructions we've cloned and then subsequently optimised
5145f757f3fSDimitry Andric // away, so that their debug-info doesn't go missing.
5155f757f3fSDimitry Andric for (; DbgCursor != II; ++DbgCursor)
5165f757f3fSDimitry Andric NewInst->cloneDebugInfoFrom(&*DbgCursor, std::nullopt, false);
5175f757f3fSDimitry Andric NewInst->cloneDebugInfoFrom(&*II);
5185f757f3fSDimitry Andric DbgCursor = std::next(II);
5195f757f3fSDimitry Andric };
5205f757f3fSDimitry Andric
5210b57cec5SDimitry Andric // Loop over all instructions, and copy them over, DCE'ing as we go. This
5220b57cec5SDimitry Andric // loop doesn't include the terminator.
523fe6060f1SDimitry Andric for (BasicBlock::const_iterator II = StartingInst, IE = --BB->end(); II != IE;
524fe6060f1SDimitry Andric ++II) {
5250b57cec5SDimitry Andric
52681ad6265SDimitry Andric Instruction *NewInst = cloneInstruction(II);
52706c3fb27SDimitry Andric NewInst->insertInto(NewBB, NewBB->end());
52881ad6265SDimitry Andric
52981ad6265SDimitry Andric if (HostFuncIsStrictFP) {
53081ad6265SDimitry Andric // All function calls in the inlined function must get 'strictfp'
53181ad6265SDimitry Andric // attribute to prevent undesirable optimizations.
53281ad6265SDimitry Andric if (auto *Call = dyn_cast<CallInst>(NewInst))
53381ad6265SDimitry Andric Call->addFnAttr(Attribute::StrictFP);
53481ad6265SDimitry Andric }
5350b57cec5SDimitry Andric
5360b57cec5SDimitry Andric // Eagerly remap operands to the newly cloned instruction, except for PHI
537bdd1243dSDimitry Andric // nodes for which we defer processing until we update the CFG. Also defer
538bdd1243dSDimitry Andric // debug intrinsic processing because they may contain use-before-defs.
539bdd1243dSDimitry Andric if (!isa<PHINode>(NewInst) && !isa<DbgVariableIntrinsic>(NewInst)) {
5400b57cec5SDimitry Andric RemapInstruction(NewInst, VMap,
5410b57cec5SDimitry Andric ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges);
5420b57cec5SDimitry Andric
5430b57cec5SDimitry Andric // If we can simplify this instruction to some other value, simply add
5440b57cec5SDimitry Andric // a mapping to that value rather than inserting a new instruction into
5450b57cec5SDimitry Andric // the basic block.
5460b57cec5SDimitry Andric if (Value *V =
54781ad6265SDimitry Andric simplifyInstruction(NewInst, BB->getModule()->getDataLayout())) {
5480b57cec5SDimitry Andric // On the off-chance that this simplifies to an instruction in the old
5490b57cec5SDimitry Andric // function, map it back into the new function.
5500b57cec5SDimitry Andric if (NewFunc != OldFunc)
5510b57cec5SDimitry Andric if (Value *MappedV = VMap.lookup(V))
5520b57cec5SDimitry Andric V = MappedV;
5530b57cec5SDimitry Andric
5540b57cec5SDimitry Andric if (!NewInst->mayHaveSideEffects()) {
5550b57cec5SDimitry Andric VMap[&*II] = V;
55606c3fb27SDimitry Andric NewInst->eraseFromParent();
5570b57cec5SDimitry Andric continue;
5580b57cec5SDimitry Andric }
5590b57cec5SDimitry Andric }
5600b57cec5SDimitry Andric }
5610b57cec5SDimitry Andric
5620b57cec5SDimitry Andric if (II->hasName())
5630b57cec5SDimitry Andric NewInst->setName(II->getName() + NameSuffix);
5640b57cec5SDimitry Andric VMap[&*II] = NewInst; // Add instruction map to value.
565bdd1243dSDimitry Andric if (isa<CallInst>(II) && !II->isDebugOrPseudoInst()) {
566bdd1243dSDimitry Andric hasCalls = true;
567bdd1243dSDimitry Andric hasMemProfMetadata |= II->hasMetadata(LLVMContext::MD_memprof);
568bdd1243dSDimitry Andric }
5690b57cec5SDimitry Andric
5705f757f3fSDimitry Andric CloneDbgRecordsToHere(NewInst, II);
5715f757f3fSDimitry Andric
572fe6060f1SDimitry Andric if (CodeInfo) {
573fe6060f1SDimitry Andric CodeInfo->OrigVMap[&*II] = NewInst;
5745ffd83dbSDimitry Andric if (auto *CB = dyn_cast<CallBase>(&*II))
5755ffd83dbSDimitry Andric if (CB->hasOperandBundles())
5760b57cec5SDimitry Andric CodeInfo->OperandBundleCallSites.push_back(NewInst);
577fe6060f1SDimitry Andric }
5780b57cec5SDimitry Andric
5790b57cec5SDimitry Andric if (const AllocaInst *AI = dyn_cast<AllocaInst>(II)) {
5800b57cec5SDimitry Andric if (isa<ConstantInt>(AI->getArraySize()))
5810b57cec5SDimitry Andric hasStaticAllocas = true;
5820b57cec5SDimitry Andric else
5830b57cec5SDimitry Andric hasDynamicAllocas = true;
5840b57cec5SDimitry Andric }
5850b57cec5SDimitry Andric }
5860b57cec5SDimitry Andric
5870b57cec5SDimitry Andric // Finally, clone over the terminator.
5880b57cec5SDimitry Andric const Instruction *OldTI = BB->getTerminator();
5890b57cec5SDimitry Andric bool TerminatorDone = false;
5900b57cec5SDimitry Andric if (const BranchInst *BI = dyn_cast<BranchInst>(OldTI)) {
5910b57cec5SDimitry Andric if (BI->isConditional()) {
5920b57cec5SDimitry Andric // If the condition was a known constant in the callee...
5930b57cec5SDimitry Andric ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition());
5940b57cec5SDimitry Andric // Or is a known constant in the caller...
5950b57cec5SDimitry Andric if (!Cond) {
5960b57cec5SDimitry Andric Value *V = VMap.lookup(BI->getCondition());
5970b57cec5SDimitry Andric Cond = dyn_cast_or_null<ConstantInt>(V);
5980b57cec5SDimitry Andric }
5990b57cec5SDimitry Andric
6000b57cec5SDimitry Andric // Constant fold to uncond branch!
6010b57cec5SDimitry Andric if (Cond) {
6020b57cec5SDimitry Andric BasicBlock *Dest = BI->getSuccessor(!Cond->getZExtValue());
6030b57cec5SDimitry Andric VMap[OldTI] = BranchInst::Create(Dest, NewBB);
6040b57cec5SDimitry Andric ToClone.push_back(Dest);
6050b57cec5SDimitry Andric TerminatorDone = true;
6060b57cec5SDimitry Andric }
6070b57cec5SDimitry Andric }
6080b57cec5SDimitry Andric } else if (const SwitchInst *SI = dyn_cast<SwitchInst>(OldTI)) {
6090b57cec5SDimitry Andric // If switching on a value known constant in the caller.
6100b57cec5SDimitry Andric ConstantInt *Cond = dyn_cast<ConstantInt>(SI->getCondition());
6110b57cec5SDimitry Andric if (!Cond) { // Or known constant after constant prop in the callee...
6120b57cec5SDimitry Andric Value *V = VMap.lookup(SI->getCondition());
6130b57cec5SDimitry Andric Cond = dyn_cast_or_null<ConstantInt>(V);
6140b57cec5SDimitry Andric }
6150b57cec5SDimitry Andric if (Cond) { // Constant fold to uncond branch!
6160b57cec5SDimitry Andric SwitchInst::ConstCaseHandle Case = *SI->findCaseValue(Cond);
6170b57cec5SDimitry Andric BasicBlock *Dest = const_cast<BasicBlock *>(Case.getCaseSuccessor());
6180b57cec5SDimitry Andric VMap[OldTI] = BranchInst::Create(Dest, NewBB);
6190b57cec5SDimitry Andric ToClone.push_back(Dest);
6200b57cec5SDimitry Andric TerminatorDone = true;
6210b57cec5SDimitry Andric }
6220b57cec5SDimitry Andric }
6230b57cec5SDimitry Andric
6240b57cec5SDimitry Andric if (!TerminatorDone) {
6250b57cec5SDimitry Andric Instruction *NewInst = OldTI->clone();
6260b57cec5SDimitry Andric if (OldTI->hasName())
6270b57cec5SDimitry Andric NewInst->setName(OldTI->getName() + NameSuffix);
628bdd1243dSDimitry Andric NewInst->insertInto(NewBB, NewBB->end());
6295f757f3fSDimitry Andric
6305f757f3fSDimitry Andric CloneDbgRecordsToHere(NewInst, OldTI->getIterator());
6315f757f3fSDimitry Andric
6320b57cec5SDimitry Andric VMap[OldTI] = NewInst; // Add instruction map to value.
6330b57cec5SDimitry Andric
634fe6060f1SDimitry Andric if (CodeInfo) {
635fe6060f1SDimitry Andric CodeInfo->OrigVMap[OldTI] = NewInst;
6365ffd83dbSDimitry Andric if (auto *CB = dyn_cast<CallBase>(OldTI))
6375ffd83dbSDimitry Andric if (CB->hasOperandBundles())
6380b57cec5SDimitry Andric CodeInfo->OperandBundleCallSites.push_back(NewInst);
639fe6060f1SDimitry Andric }
6400b57cec5SDimitry Andric
6410b57cec5SDimitry Andric // Recursively clone any reachable successor blocks.
642e8d8bef9SDimitry Andric append_range(ToClone, successors(BB->getTerminator()));
6435f757f3fSDimitry Andric } else {
6445f757f3fSDimitry Andric // If we didn't create a new terminator, clone DPValues from the old
6455f757f3fSDimitry Andric // terminator onto the new terminator.
6465f757f3fSDimitry Andric Instruction *NewInst = NewBB->getTerminator();
6475f757f3fSDimitry Andric assert(NewInst);
6485f757f3fSDimitry Andric
6495f757f3fSDimitry Andric CloneDbgRecordsToHere(NewInst, OldTI->getIterator());
6500b57cec5SDimitry Andric }
6510b57cec5SDimitry Andric
6520b57cec5SDimitry Andric if (CodeInfo) {
6530b57cec5SDimitry Andric CodeInfo->ContainsCalls |= hasCalls;
654bdd1243dSDimitry Andric CodeInfo->ContainsMemProfMetadata |= hasMemProfMetadata;
6550b57cec5SDimitry Andric CodeInfo->ContainsDynamicAllocas |= hasDynamicAllocas;
656fe6060f1SDimitry Andric CodeInfo->ContainsDynamicAllocas |=
657fe6060f1SDimitry Andric hasStaticAllocas && BB != &BB->getParent()->front();
6580b57cec5SDimitry Andric }
6590b57cec5SDimitry Andric }
6600b57cec5SDimitry Andric
6610b57cec5SDimitry Andric /// This works like CloneAndPruneFunctionInto, except that it does not clone the
6620b57cec5SDimitry Andric /// entire function. Instead it starts at an instruction provided by the caller
6630b57cec5SDimitry Andric /// and copies (and prunes) only the code reachable from that instruction.
CloneAndPruneIntoFromInst(Function * NewFunc,const Function * OldFunc,const Instruction * StartingInst,ValueToValueMapTy & VMap,bool ModuleLevelChanges,SmallVectorImpl<ReturnInst * > & Returns,const char * NameSuffix,ClonedCodeInfo * CodeInfo)6640b57cec5SDimitry Andric void llvm::CloneAndPruneIntoFromInst(Function *NewFunc, const Function *OldFunc,
6650b57cec5SDimitry Andric const Instruction *StartingInst,
6660b57cec5SDimitry Andric ValueToValueMapTy &VMap,
6670b57cec5SDimitry Andric bool ModuleLevelChanges,
6680b57cec5SDimitry Andric SmallVectorImpl<ReturnInst *> &Returns,
6690b57cec5SDimitry Andric const char *NameSuffix,
6700b57cec5SDimitry Andric ClonedCodeInfo *CodeInfo) {
6710b57cec5SDimitry Andric assert(NameSuffix && "NameSuffix cannot be null!");
6720b57cec5SDimitry Andric
6730b57cec5SDimitry Andric ValueMapTypeRemapper *TypeMapper = nullptr;
6740b57cec5SDimitry Andric ValueMaterializer *Materializer = nullptr;
6750b57cec5SDimitry Andric
6760b57cec5SDimitry Andric #ifndef NDEBUG
6770b57cec5SDimitry Andric // If the cloning starts at the beginning of the function, verify that
6780b57cec5SDimitry Andric // the function arguments are mapped.
6790b57cec5SDimitry Andric if (!StartingInst)
6800b57cec5SDimitry Andric for (const Argument &II : OldFunc->args())
6810b57cec5SDimitry Andric assert(VMap.count(&II) && "No mapping from source argument specified!");
6820b57cec5SDimitry Andric #endif
6830b57cec5SDimitry Andric
6840b57cec5SDimitry Andric PruningFunctionCloner PFC(NewFunc, OldFunc, VMap, ModuleLevelChanges,
6850b57cec5SDimitry Andric NameSuffix, CodeInfo);
6860b57cec5SDimitry Andric const BasicBlock *StartingBB;
6870b57cec5SDimitry Andric if (StartingInst)
6880b57cec5SDimitry Andric StartingBB = StartingInst->getParent();
6890b57cec5SDimitry Andric else {
6900b57cec5SDimitry Andric StartingBB = &OldFunc->getEntryBlock();
6910b57cec5SDimitry Andric StartingInst = &StartingBB->front();
6920b57cec5SDimitry Andric }
6930b57cec5SDimitry Andric
694bdd1243dSDimitry Andric // Collect debug intrinsics for remapping later.
695bdd1243dSDimitry Andric SmallVector<const DbgVariableIntrinsic *, 8> DbgIntrinsics;
696bdd1243dSDimitry Andric for (const auto &BB : *OldFunc) {
697bdd1243dSDimitry Andric for (const auto &I : BB) {
698bdd1243dSDimitry Andric if (const auto *DVI = dyn_cast<DbgVariableIntrinsic>(&I))
699bdd1243dSDimitry Andric DbgIntrinsics.push_back(DVI);
700bdd1243dSDimitry Andric }
701bdd1243dSDimitry Andric }
702bdd1243dSDimitry Andric
7030b57cec5SDimitry Andric // Clone the entry block, and anything recursively reachable from it.
7040b57cec5SDimitry Andric std::vector<const BasicBlock *> CloneWorklist;
7050b57cec5SDimitry Andric PFC.CloneBlock(StartingBB, StartingInst->getIterator(), CloneWorklist);
7060b57cec5SDimitry Andric while (!CloneWorklist.empty()) {
7070b57cec5SDimitry Andric const BasicBlock *BB = CloneWorklist.back();
7080b57cec5SDimitry Andric CloneWorklist.pop_back();
7090b57cec5SDimitry Andric PFC.CloneBlock(BB, BB->begin(), CloneWorklist);
7100b57cec5SDimitry Andric }
7110b57cec5SDimitry Andric
7120b57cec5SDimitry Andric // Loop over all of the basic blocks in the old function. If the block was
7130b57cec5SDimitry Andric // reachable, we have cloned it and the old block is now in the value map:
7140b57cec5SDimitry Andric // insert it into the new function in the right order. If not, ignore it.
7150b57cec5SDimitry Andric //
7160b57cec5SDimitry Andric // Defer PHI resolution until rest of function is resolved.
7170b57cec5SDimitry Andric SmallVector<const PHINode *, 16> PHIToResolve;
7180b57cec5SDimitry Andric for (const BasicBlock &BI : *OldFunc) {
7190b57cec5SDimitry Andric Value *V = VMap.lookup(&BI);
7200b57cec5SDimitry Andric BasicBlock *NewBB = cast_or_null<BasicBlock>(V);
721fe6060f1SDimitry Andric if (!NewBB)
722fe6060f1SDimitry Andric continue; // Dead block.
7230b57cec5SDimitry Andric
72406c3fb27SDimitry Andric // Move the new block to preserve the order in the original function.
72506c3fb27SDimitry Andric NewBB->moveBefore(NewFunc->end());
7260b57cec5SDimitry Andric
7270b57cec5SDimitry Andric // Handle PHI nodes specially, as we have to remove references to dead
7280b57cec5SDimitry Andric // blocks.
7290b57cec5SDimitry Andric for (const PHINode &PN : BI.phis()) {
7300b57cec5SDimitry Andric // PHI nodes may have been remapped to non-PHI nodes by the caller or
7310b57cec5SDimitry Andric // during the cloning process.
7320b57cec5SDimitry Andric if (isa<PHINode>(VMap[&PN]))
7330b57cec5SDimitry Andric PHIToResolve.push_back(&PN);
7340b57cec5SDimitry Andric else
7350b57cec5SDimitry Andric break;
7360b57cec5SDimitry Andric }
7370b57cec5SDimitry Andric
7380b57cec5SDimitry Andric // Finally, remap the terminator instructions, as those can't be remapped
7390b57cec5SDimitry Andric // until all BBs are mapped.
7400b57cec5SDimitry Andric RemapInstruction(NewBB->getTerminator(), VMap,
7410b57cec5SDimitry Andric ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges,
7420b57cec5SDimitry Andric TypeMapper, Materializer);
7430b57cec5SDimitry Andric }
7440b57cec5SDimitry Andric
7450b57cec5SDimitry Andric // Defer PHI resolution until rest of function is resolved, PHI resolution
7460b57cec5SDimitry Andric // requires the CFG to be up-to-date.
7470b57cec5SDimitry Andric for (unsigned phino = 0, e = PHIToResolve.size(); phino != e;) {
7480b57cec5SDimitry Andric const PHINode *OPN = PHIToResolve[phino];
7490b57cec5SDimitry Andric unsigned NumPreds = OPN->getNumIncomingValues();
7500b57cec5SDimitry Andric const BasicBlock *OldBB = OPN->getParent();
7510b57cec5SDimitry Andric BasicBlock *NewBB = cast<BasicBlock>(VMap[OldBB]);
7520b57cec5SDimitry Andric
7530b57cec5SDimitry Andric // Map operands for blocks that are live and remove operands for blocks
7540b57cec5SDimitry Andric // that are dead.
7550b57cec5SDimitry Andric for (; phino != PHIToResolve.size() &&
756fe6060f1SDimitry Andric PHIToResolve[phino]->getParent() == OldBB;
757fe6060f1SDimitry Andric ++phino) {
7580b57cec5SDimitry Andric OPN = PHIToResolve[phino];
7590b57cec5SDimitry Andric PHINode *PN = cast<PHINode>(VMap[OPN]);
7600b57cec5SDimitry Andric for (unsigned pred = 0, e = NumPreds; pred != e; ++pred) {
7610b57cec5SDimitry Andric Value *V = VMap.lookup(PN->getIncomingBlock(pred));
7620b57cec5SDimitry Andric if (BasicBlock *MappedBlock = cast_or_null<BasicBlock>(V)) {
763fe6060f1SDimitry Andric Value *InVal =
764fe6060f1SDimitry Andric MapValue(PN->getIncomingValue(pred), VMap,
7650b57cec5SDimitry Andric ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges);
7660b57cec5SDimitry Andric assert(InVal && "Unknown input value?");
7670b57cec5SDimitry Andric PN->setIncomingValue(pred, InVal);
7680b57cec5SDimitry Andric PN->setIncomingBlock(pred, MappedBlock);
7690b57cec5SDimitry Andric } else {
7700b57cec5SDimitry Andric PN->removeIncomingValue(pred, false);
7710b57cec5SDimitry Andric --pred; // Revisit the next entry.
7720b57cec5SDimitry Andric --e;
7730b57cec5SDimitry Andric }
7740b57cec5SDimitry Andric }
7750b57cec5SDimitry Andric }
7760b57cec5SDimitry Andric
7770b57cec5SDimitry Andric // The loop above has removed PHI entries for those blocks that are dead
7780b57cec5SDimitry Andric // and has updated others. However, if a block is live (i.e. copied over)
7790b57cec5SDimitry Andric // but its terminator has been changed to not go to this block, then our
7800b57cec5SDimitry Andric // phi nodes will have invalid entries. Update the PHI nodes in this
7810b57cec5SDimitry Andric // case.
7820b57cec5SDimitry Andric PHINode *PN = cast<PHINode>(NewBB->begin());
7830b57cec5SDimitry Andric NumPreds = pred_size(NewBB);
7840b57cec5SDimitry Andric if (NumPreds != PN->getNumIncomingValues()) {
7850b57cec5SDimitry Andric assert(NumPreds < PN->getNumIncomingValues());
7860b57cec5SDimitry Andric // Count how many times each predecessor comes to this block.
7870b57cec5SDimitry Andric std::map<BasicBlock *, unsigned> PredCount;
788fe6060f1SDimitry Andric for (BasicBlock *Pred : predecessors(NewBB))
789fe6060f1SDimitry Andric --PredCount[Pred];
7900b57cec5SDimitry Andric
7910b57cec5SDimitry Andric // Figure out how many entries to remove from each PHI.
7920b57cec5SDimitry Andric for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
7930b57cec5SDimitry Andric ++PredCount[PN->getIncomingBlock(i)];
7940b57cec5SDimitry Andric
7950b57cec5SDimitry Andric // At this point, the excess predecessor entries are positive in the
7960b57cec5SDimitry Andric // map. Loop over all of the PHIs and remove excess predecessor
7970b57cec5SDimitry Andric // entries.
7980b57cec5SDimitry Andric BasicBlock::iterator I = NewBB->begin();
7990b57cec5SDimitry Andric for (; (PN = dyn_cast<PHINode>(I)); ++I) {
8000b57cec5SDimitry Andric for (const auto &PCI : PredCount) {
8010b57cec5SDimitry Andric BasicBlock *Pred = PCI.first;
8020b57cec5SDimitry Andric for (unsigned NumToRemove = PCI.second; NumToRemove; --NumToRemove)
8030b57cec5SDimitry Andric PN->removeIncomingValue(Pred, false);
8040b57cec5SDimitry Andric }
8050b57cec5SDimitry Andric }
8060b57cec5SDimitry Andric }
8070b57cec5SDimitry Andric
8080b57cec5SDimitry Andric // If the loops above have made these phi nodes have 0 or 1 operand,
809fcaf7f86SDimitry Andric // replace them with poison or the input value. We must do this for
8100b57cec5SDimitry Andric // correctness, because 0-operand phis are not valid.
8110b57cec5SDimitry Andric PN = cast<PHINode>(NewBB->begin());
8120b57cec5SDimitry Andric if (PN->getNumIncomingValues() == 0) {
8130b57cec5SDimitry Andric BasicBlock::iterator I = NewBB->begin();
8140b57cec5SDimitry Andric BasicBlock::const_iterator OldI = OldBB->begin();
8150b57cec5SDimitry Andric while ((PN = dyn_cast<PHINode>(I++))) {
816fcaf7f86SDimitry Andric Value *NV = PoisonValue::get(PN->getType());
8170b57cec5SDimitry Andric PN->replaceAllUsesWith(NV);
8180b57cec5SDimitry Andric assert(VMap[&*OldI] == PN && "VMap mismatch");
8190b57cec5SDimitry Andric VMap[&*OldI] = NV;
8200b57cec5SDimitry Andric PN->eraseFromParent();
8210b57cec5SDimitry Andric ++OldI;
8220b57cec5SDimitry Andric }
8230b57cec5SDimitry Andric }
8240b57cec5SDimitry Andric }
8250b57cec5SDimitry Andric
8260b57cec5SDimitry Andric // Make a second pass over the PHINodes now that all of them have been
8270b57cec5SDimitry Andric // remapped into the new function, simplifying the PHINode and performing any
8280b57cec5SDimitry Andric // recursive simplifications exposed. This will transparently update the
8290b57cec5SDimitry Andric // WeakTrackingVH in the VMap. Notably, we rely on that so that if we coalesce
8300b57cec5SDimitry Andric // two PHINodes, the iteration over the old PHIs remains valid, and the
8310b57cec5SDimitry Andric // mapping will just map us to the new node (which may not even be a PHI
8320b57cec5SDimitry Andric // node).
8330b57cec5SDimitry Andric const DataLayout &DL = NewFunc->getParent()->getDataLayout();
8340b57cec5SDimitry Andric SmallSetVector<const Value *, 8> Worklist;
8350b57cec5SDimitry Andric for (unsigned Idx = 0, Size = PHIToResolve.size(); Idx != Size; ++Idx)
8360b57cec5SDimitry Andric if (isa<PHINode>(VMap[PHIToResolve[Idx]]))
8370b57cec5SDimitry Andric Worklist.insert(PHIToResolve[Idx]);
8380b57cec5SDimitry Andric
8390b57cec5SDimitry Andric // Note that we must test the size on each iteration, the worklist can grow.
8400b57cec5SDimitry Andric for (unsigned Idx = 0; Idx != Worklist.size(); ++Idx) {
8410b57cec5SDimitry Andric const Value *OrigV = Worklist[Idx];
8420b57cec5SDimitry Andric auto *I = dyn_cast_or_null<Instruction>(VMap.lookup(OrigV));
8430b57cec5SDimitry Andric if (!I)
8440b57cec5SDimitry Andric continue;
8450b57cec5SDimitry Andric
8460b57cec5SDimitry Andric // Skip over non-intrinsic callsites, we don't want to remove any nodes from
8470b57cec5SDimitry Andric // the CGSCC.
8485ffd83dbSDimitry Andric CallBase *CB = dyn_cast<CallBase>(I);
8495ffd83dbSDimitry Andric if (CB && CB->getCalledFunction() &&
8505ffd83dbSDimitry Andric !CB->getCalledFunction()->isIntrinsic())
8510b57cec5SDimitry Andric continue;
8520b57cec5SDimitry Andric
8530b57cec5SDimitry Andric // See if this instruction simplifies.
85481ad6265SDimitry Andric Value *SimpleV = simplifyInstruction(I, DL);
8550b57cec5SDimitry Andric if (!SimpleV)
8560b57cec5SDimitry Andric continue;
8570b57cec5SDimitry Andric
8580b57cec5SDimitry Andric // Stash away all the uses of the old instruction so we can check them for
8590b57cec5SDimitry Andric // recursive simplifications after a RAUW. This is cheaper than checking all
8600b57cec5SDimitry Andric // uses of To on the recursive step in most cases.
8610b57cec5SDimitry Andric for (const User *U : OrigV->users())
8620b57cec5SDimitry Andric Worklist.insert(cast<Instruction>(U));
8630b57cec5SDimitry Andric
8640b57cec5SDimitry Andric // Replace the instruction with its simplified value.
8650b57cec5SDimitry Andric I->replaceAllUsesWith(SimpleV);
8660b57cec5SDimitry Andric
8670b57cec5SDimitry Andric // If the original instruction had no side effects, remove it.
8680b57cec5SDimitry Andric if (isInstructionTriviallyDead(I))
8690b57cec5SDimitry Andric I->eraseFromParent();
8700b57cec5SDimitry Andric else
8710b57cec5SDimitry Andric VMap[OrigV] = I;
8720b57cec5SDimitry Andric }
8730b57cec5SDimitry Andric
874bdd1243dSDimitry Andric // Remap debug intrinsic operands now that all values have been mapped.
875bdd1243dSDimitry Andric // Doing this now (late) preserves use-before-defs in debug intrinsics. If
876bdd1243dSDimitry Andric // we didn't do this, ValueAsMetadata(use-before-def) operands would be
877bdd1243dSDimitry Andric // replaced by empty metadata. This would signal later cleanup passes to
878bdd1243dSDimitry Andric // remove the debug intrinsics, potentially causing incorrect locations.
879bdd1243dSDimitry Andric for (const auto *DVI : DbgIntrinsics) {
880bdd1243dSDimitry Andric if (DbgVariableIntrinsic *NewDVI =
881bdd1243dSDimitry Andric cast_or_null<DbgVariableIntrinsic>(VMap.lookup(DVI)))
882bdd1243dSDimitry Andric RemapInstruction(NewDVI, VMap,
883bdd1243dSDimitry Andric ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges,
884bdd1243dSDimitry Andric TypeMapper, Materializer);
885bdd1243dSDimitry Andric }
886bdd1243dSDimitry Andric
8875f757f3fSDimitry Andric // Do the same for DPValues, touching all the instructions in the cloned
8885f757f3fSDimitry Andric // range of blocks.
8895f757f3fSDimitry Andric Function::iterator Begin = cast<BasicBlock>(VMap[StartingBB])->getIterator();
8905f757f3fSDimitry Andric for (BasicBlock &BB : make_range(Begin, NewFunc->end())) {
8915f757f3fSDimitry Andric for (Instruction &I : BB) {
8925f757f3fSDimitry Andric RemapDPValueRange(I.getModule(), I.getDbgValueRange(), VMap,
8935f757f3fSDimitry Andric ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges,
8945f757f3fSDimitry Andric TypeMapper, Materializer);
8955f757f3fSDimitry Andric }
8965f757f3fSDimitry Andric }
8975f757f3fSDimitry Andric
8981fd87a68SDimitry Andric // Simplify conditional branches and switches with a constant operand. We try
8991fd87a68SDimitry Andric // to prune these out when cloning, but if the simplification required
9001fd87a68SDimitry Andric // looking through PHI nodes, those are only available after forming the full
9011fd87a68SDimitry Andric // basic block. That may leave some here, and we still want to prune the dead
9021fd87a68SDimitry Andric // code as early as possible.
9031fd87a68SDimitry Andric for (BasicBlock &BB : make_range(Begin, NewFunc->end()))
9041fd87a68SDimitry Andric ConstantFoldTerminator(&BB);
9051fd87a68SDimitry Andric
9061fd87a68SDimitry Andric // Some blocks may have become unreachable as a result. Find and delete them.
9071fd87a68SDimitry Andric {
9081fd87a68SDimitry Andric SmallPtrSet<BasicBlock *, 16> ReachableBlocks;
9091fd87a68SDimitry Andric SmallVector<BasicBlock *, 16> Worklist;
9101fd87a68SDimitry Andric Worklist.push_back(&*Begin);
9111fd87a68SDimitry Andric while (!Worklist.empty()) {
9121fd87a68SDimitry Andric BasicBlock *BB = Worklist.pop_back_val();
9131fd87a68SDimitry Andric if (ReachableBlocks.insert(BB).second)
9141fd87a68SDimitry Andric append_range(Worklist, successors(BB));
9151fd87a68SDimitry Andric }
9161fd87a68SDimitry Andric
9171fd87a68SDimitry Andric SmallVector<BasicBlock *, 16> UnreachableBlocks;
9181fd87a68SDimitry Andric for (BasicBlock &BB : make_range(Begin, NewFunc->end()))
9191fd87a68SDimitry Andric if (!ReachableBlocks.contains(&BB))
9201fd87a68SDimitry Andric UnreachableBlocks.push_back(&BB);
9211fd87a68SDimitry Andric DeleteDeadBlocks(UnreachableBlocks);
9221fd87a68SDimitry Andric }
9231fd87a68SDimitry Andric
9240b57cec5SDimitry Andric // Now that the inlined function body has been fully constructed, go through
9250b57cec5SDimitry Andric // and zap unconditional fall-through branches. This happens all the time when
9260b57cec5SDimitry Andric // specializing code: code specialization turns conditional branches into
9270b57cec5SDimitry Andric // uncond branches, and this code folds them.
9280b57cec5SDimitry Andric Function::iterator I = Begin;
9290b57cec5SDimitry Andric while (I != NewFunc->end()) {
9300b57cec5SDimitry Andric BranchInst *BI = dyn_cast<BranchInst>(I->getTerminator());
931fe6060f1SDimitry Andric if (!BI || BI->isConditional()) {
932fe6060f1SDimitry Andric ++I;
933fe6060f1SDimitry Andric continue;
934fe6060f1SDimitry Andric }
9350b57cec5SDimitry Andric
9360b57cec5SDimitry Andric BasicBlock *Dest = BI->getSuccessor(0);
9370b57cec5SDimitry Andric if (!Dest->getSinglePredecessor()) {
938fe6060f1SDimitry Andric ++I;
939fe6060f1SDimitry Andric continue;
9400b57cec5SDimitry Andric }
9410b57cec5SDimitry Andric
9420b57cec5SDimitry Andric // We shouldn't be able to get single-entry PHI nodes here, as instsimplify
9430b57cec5SDimitry Andric // above should have zapped all of them..
9440b57cec5SDimitry Andric assert(!isa<PHINode>(Dest->begin()));
9450b57cec5SDimitry Andric
9460b57cec5SDimitry Andric // We know all single-entry PHI nodes in the inlined function have been
9470b57cec5SDimitry Andric // removed, so we just need to splice the blocks.
9480b57cec5SDimitry Andric BI->eraseFromParent();
9490b57cec5SDimitry Andric
9500b57cec5SDimitry Andric // Make all PHI nodes that referred to Dest now refer to I as their source.
9510b57cec5SDimitry Andric Dest->replaceAllUsesWith(&*I);
9520b57cec5SDimitry Andric
9530b57cec5SDimitry Andric // Move all the instructions in the succ to the pred.
954bdd1243dSDimitry Andric I->splice(I->end(), Dest);
9550b57cec5SDimitry Andric
9560b57cec5SDimitry Andric // Remove the dest block.
9570b57cec5SDimitry Andric Dest->eraseFromParent();
9580b57cec5SDimitry Andric
9590b57cec5SDimitry Andric // Do not increment I, iteratively merge all things this block branches to.
9600b57cec5SDimitry Andric }
9610b57cec5SDimitry Andric
9620b57cec5SDimitry Andric // Make a final pass over the basic blocks from the old function to gather
9630b57cec5SDimitry Andric // any return instructions which survived folding. We have to do this here
9640b57cec5SDimitry Andric // because we can iteratively remove and merge returns above.
9650b57cec5SDimitry Andric for (Function::iterator I = cast<BasicBlock>(VMap[StartingBB])->getIterator(),
9660b57cec5SDimitry Andric E = NewFunc->end();
9670b57cec5SDimitry Andric I != E; ++I)
9680b57cec5SDimitry Andric if (ReturnInst *RI = dyn_cast<ReturnInst>(I->getTerminator()))
9690b57cec5SDimitry Andric Returns.push_back(RI);
9700b57cec5SDimitry Andric }
9710b57cec5SDimitry Andric
9720b57cec5SDimitry Andric /// This works exactly like CloneFunctionInto,
9730b57cec5SDimitry Andric /// except that it does some simple constant prop and DCE on the fly. The
9740b57cec5SDimitry Andric /// effect of this is to copy significantly less code in cases where (for
9750b57cec5SDimitry Andric /// example) a function call with constant arguments is inlined, and those
9760b57cec5SDimitry Andric /// constant arguments cause a significant amount of code in the callee to be
9770b57cec5SDimitry Andric /// dead. Since this doesn't produce an exact copy of the input, it can't be
9780b57cec5SDimitry Andric /// used for things like CloneFunction or CloneModule.
CloneAndPruneFunctionInto(Function * NewFunc,const Function * OldFunc,ValueToValueMapTy & VMap,bool ModuleLevelChanges,SmallVectorImpl<ReturnInst * > & Returns,const char * NameSuffix,ClonedCodeInfo * CodeInfo)979fe6060f1SDimitry Andric void llvm::CloneAndPruneFunctionInto(
980fe6060f1SDimitry Andric Function *NewFunc, const Function *OldFunc, ValueToValueMapTy &VMap,
981fe6060f1SDimitry Andric bool ModuleLevelChanges, SmallVectorImpl<ReturnInst *> &Returns,
982fe6060f1SDimitry Andric const char *NameSuffix, ClonedCodeInfo *CodeInfo) {
9830b57cec5SDimitry Andric CloneAndPruneIntoFromInst(NewFunc, OldFunc, &OldFunc->front().front(), VMap,
9840b57cec5SDimitry Andric ModuleLevelChanges, Returns, NameSuffix, CodeInfo);
9850b57cec5SDimitry Andric }
9860b57cec5SDimitry Andric
9870b57cec5SDimitry Andric /// Remaps instructions in \p Blocks using the mapping in \p VMap.
remapInstructionsInBlocks(ArrayRef<BasicBlock * > Blocks,ValueToValueMapTy & VMap)98806c3fb27SDimitry Andric void llvm::remapInstructionsInBlocks(ArrayRef<BasicBlock *> Blocks,
98906c3fb27SDimitry Andric ValueToValueMapTy &VMap) {
9900b57cec5SDimitry Andric // Rewrite the code to refer to itself.
9915f757f3fSDimitry Andric for (auto *BB : Blocks) {
9925f757f3fSDimitry Andric for (auto &Inst : *BB) {
9935f757f3fSDimitry Andric RemapDPValueRange(Inst.getModule(), Inst.getDbgValueRange(), VMap,
9945f757f3fSDimitry Andric RF_NoModuleLevelChanges | RF_IgnoreMissingLocals);
9950b57cec5SDimitry Andric RemapInstruction(&Inst, VMap,
9960b57cec5SDimitry Andric RF_NoModuleLevelChanges | RF_IgnoreMissingLocals);
9970b57cec5SDimitry Andric }
9985f757f3fSDimitry Andric }
9995f757f3fSDimitry Andric }
10000b57cec5SDimitry Andric
10010b57cec5SDimitry Andric /// Clones a loop \p OrigLoop. Returns the loop and the blocks in \p
10020b57cec5SDimitry Andric /// Blocks.
10030b57cec5SDimitry Andric ///
10040b57cec5SDimitry Andric /// Updates LoopInfo and DominatorTree assuming the loop is dominated by block
10050b57cec5SDimitry Andric /// \p LoopDomBB. Insert the new blocks before block specified in \p Before.
cloneLoopWithPreheader(BasicBlock * Before,BasicBlock * LoopDomBB,Loop * OrigLoop,ValueToValueMapTy & VMap,const Twine & NameSuffix,LoopInfo * LI,DominatorTree * DT,SmallVectorImpl<BasicBlock * > & Blocks)10060b57cec5SDimitry Andric Loop *llvm::cloneLoopWithPreheader(BasicBlock *Before, BasicBlock *LoopDomBB,
10070b57cec5SDimitry Andric Loop *OrigLoop, ValueToValueMapTy &VMap,
10080b57cec5SDimitry Andric const Twine &NameSuffix, LoopInfo *LI,
10090b57cec5SDimitry Andric DominatorTree *DT,
10100b57cec5SDimitry Andric SmallVectorImpl<BasicBlock *> &Blocks) {
10110b57cec5SDimitry Andric Function *F = OrigLoop->getHeader()->getParent();
10120b57cec5SDimitry Andric Loop *ParentLoop = OrigLoop->getParentLoop();
10130b57cec5SDimitry Andric DenseMap<Loop *, Loop *> LMap;
10140b57cec5SDimitry Andric
10150b57cec5SDimitry Andric Loop *NewLoop = LI->AllocateLoop();
10160b57cec5SDimitry Andric LMap[OrigLoop] = NewLoop;
10170b57cec5SDimitry Andric if (ParentLoop)
10180b57cec5SDimitry Andric ParentLoop->addChildLoop(NewLoop);
10190b57cec5SDimitry Andric else
10200b57cec5SDimitry Andric LI->addTopLevelLoop(NewLoop);
10210b57cec5SDimitry Andric
10220b57cec5SDimitry Andric BasicBlock *OrigPH = OrigLoop->getLoopPreheader();
10230b57cec5SDimitry Andric assert(OrigPH && "No preheader");
10240b57cec5SDimitry Andric BasicBlock *NewPH = CloneBasicBlock(OrigPH, VMap, NameSuffix, F);
10250b57cec5SDimitry Andric // To rename the loop PHIs.
10260b57cec5SDimitry Andric VMap[OrigPH] = NewPH;
10270b57cec5SDimitry Andric Blocks.push_back(NewPH);
10280b57cec5SDimitry Andric
10290b57cec5SDimitry Andric // Update LoopInfo.
10300b57cec5SDimitry Andric if (ParentLoop)
10310b57cec5SDimitry Andric ParentLoop->addBasicBlockToLoop(NewPH, *LI);
10320b57cec5SDimitry Andric
10330b57cec5SDimitry Andric // Update DominatorTree.
10340b57cec5SDimitry Andric DT->addNewBlock(NewPH, LoopDomBB);
10350b57cec5SDimitry Andric
10360b57cec5SDimitry Andric for (Loop *CurLoop : OrigLoop->getLoopsInPreorder()) {
10370b57cec5SDimitry Andric Loop *&NewLoop = LMap[CurLoop];
10380b57cec5SDimitry Andric if (!NewLoop) {
10390b57cec5SDimitry Andric NewLoop = LI->AllocateLoop();
10400b57cec5SDimitry Andric
10410b57cec5SDimitry Andric // Establish the parent/child relationship.
10420b57cec5SDimitry Andric Loop *OrigParent = CurLoop->getParentLoop();
10430b57cec5SDimitry Andric assert(OrigParent && "Could not find the original parent loop");
10440b57cec5SDimitry Andric Loop *NewParentLoop = LMap[OrigParent];
10450b57cec5SDimitry Andric assert(NewParentLoop && "Could not find the new parent loop");
10460b57cec5SDimitry Andric
10470b57cec5SDimitry Andric NewParentLoop->addChildLoop(NewLoop);
10480b57cec5SDimitry Andric }
10490b57cec5SDimitry Andric }
10500b57cec5SDimitry Andric
10510b57cec5SDimitry Andric for (BasicBlock *BB : OrigLoop->getBlocks()) {
10520b57cec5SDimitry Andric Loop *CurLoop = LI->getLoopFor(BB);
10530b57cec5SDimitry Andric Loop *&NewLoop = LMap[CurLoop];
10540b57cec5SDimitry Andric assert(NewLoop && "Expecting new loop to be allocated");
10550b57cec5SDimitry Andric
10560b57cec5SDimitry Andric BasicBlock *NewBB = CloneBasicBlock(BB, VMap, NameSuffix, F);
10570b57cec5SDimitry Andric VMap[BB] = NewBB;
10580b57cec5SDimitry Andric
10590b57cec5SDimitry Andric // Update LoopInfo.
10600b57cec5SDimitry Andric NewLoop->addBasicBlockToLoop(NewBB, *LI);
10610b57cec5SDimitry Andric
10620b57cec5SDimitry Andric // Add DominatorTree node. After seeing all blocks, update to correct
10630b57cec5SDimitry Andric // IDom.
10640b57cec5SDimitry Andric DT->addNewBlock(NewBB, NewPH);
10650b57cec5SDimitry Andric
10660b57cec5SDimitry Andric Blocks.push_back(NewBB);
10670b57cec5SDimitry Andric }
10680b57cec5SDimitry Andric
10690b57cec5SDimitry Andric for (BasicBlock *BB : OrigLoop->getBlocks()) {
10705ffd83dbSDimitry Andric // Update loop headers.
10715ffd83dbSDimitry Andric Loop *CurLoop = LI->getLoopFor(BB);
10725ffd83dbSDimitry Andric if (BB == CurLoop->getHeader())
10735ffd83dbSDimitry Andric LMap[CurLoop]->moveToHeader(cast<BasicBlock>(VMap[BB]));
10745ffd83dbSDimitry Andric
10750b57cec5SDimitry Andric // Update DominatorTree.
10760b57cec5SDimitry Andric BasicBlock *IDomBB = DT->getNode(BB)->getIDom()->getBlock();
10770b57cec5SDimitry Andric DT->changeImmediateDominator(cast<BasicBlock>(VMap[BB]),
10780b57cec5SDimitry Andric cast<BasicBlock>(VMap[IDomBB]));
10790b57cec5SDimitry Andric }
10800b57cec5SDimitry Andric
10810b57cec5SDimitry Andric // Move them physically from the end of the block list.
1082bdd1243dSDimitry Andric F->splice(Before->getIterator(), F, NewPH->getIterator());
1083bdd1243dSDimitry Andric F->splice(Before->getIterator(), F, NewLoop->getHeader()->getIterator(),
1084bdd1243dSDimitry Andric F->end());
10850b57cec5SDimitry Andric
10860b57cec5SDimitry Andric return NewLoop;
10870b57cec5SDimitry Andric }
10880b57cec5SDimitry Andric
10890b57cec5SDimitry Andric /// Duplicate non-Phi instructions from the beginning of block up to
10900b57cec5SDimitry Andric /// StopAt instruction into a split block between BB and its predecessor.
DuplicateInstructionsInSplitBetween(BasicBlock * BB,BasicBlock * PredBB,Instruction * StopAt,ValueToValueMapTy & ValueMapping,DomTreeUpdater & DTU)10910b57cec5SDimitry Andric BasicBlock *llvm::DuplicateInstructionsInSplitBetween(
10920b57cec5SDimitry Andric BasicBlock *BB, BasicBlock *PredBB, Instruction *StopAt,
10930b57cec5SDimitry Andric ValueToValueMapTy &ValueMapping, DomTreeUpdater &DTU) {
10940b57cec5SDimitry Andric
10950b57cec5SDimitry Andric assert(count(successors(PredBB), BB) == 1 &&
10960b57cec5SDimitry Andric "There must be a single edge between PredBB and BB!");
10970b57cec5SDimitry Andric // We are going to have to map operands from the original BB block to the new
10980b57cec5SDimitry Andric // copy of the block 'NewBB'. If there are PHI nodes in BB, evaluate them to
10990b57cec5SDimitry Andric // account for entry from PredBB.
11000b57cec5SDimitry Andric BasicBlock::iterator BI = BB->begin();
11010b57cec5SDimitry Andric for (; PHINode *PN = dyn_cast<PHINode>(BI); ++BI)
11020b57cec5SDimitry Andric ValueMapping[PN] = PN->getIncomingValueForBlock(PredBB);
11030b57cec5SDimitry Andric
11040b57cec5SDimitry Andric BasicBlock *NewBB = SplitEdge(PredBB, BB);
11050b57cec5SDimitry Andric NewBB->setName(PredBB->getName() + ".split");
11060b57cec5SDimitry Andric Instruction *NewTerm = NewBB->getTerminator();
11070b57cec5SDimitry Andric
11080b57cec5SDimitry Andric // FIXME: SplitEdge does not yet take a DTU, so we include the split edge
11090b57cec5SDimitry Andric // in the update set here.
11100b57cec5SDimitry Andric DTU.applyUpdates({{DominatorTree::Delete, PredBB, BB},
11110b57cec5SDimitry Andric {DominatorTree::Insert, PredBB, NewBB},
11120b57cec5SDimitry Andric {DominatorTree::Insert, NewBB, BB}});
11130b57cec5SDimitry Andric
11140b57cec5SDimitry Andric // Clone the non-phi instructions of BB into NewBB, keeping track of the
11150b57cec5SDimitry Andric // mapping and using it to remap operands in the cloned instructions.
11160b57cec5SDimitry Andric // Stop once we see the terminator too. This covers the case where BB's
11170b57cec5SDimitry Andric // terminator gets replaced and StopAt == BB's terminator.
11180b57cec5SDimitry Andric for (; StopAt != &*BI && BB->getTerminator() != &*BI; ++BI) {
11190b57cec5SDimitry Andric Instruction *New = BI->clone();
11200b57cec5SDimitry Andric New->setName(BI->getName());
11210b57cec5SDimitry Andric New->insertBefore(NewTerm);
11225f757f3fSDimitry Andric New->cloneDebugInfoFrom(&*BI);
11230b57cec5SDimitry Andric ValueMapping[&*BI] = New;
11240b57cec5SDimitry Andric
11250b57cec5SDimitry Andric // Remap operands to patch up intra-block references.
11260b57cec5SDimitry Andric for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i)
11270b57cec5SDimitry Andric if (Instruction *Inst = dyn_cast<Instruction>(New->getOperand(i))) {
11280b57cec5SDimitry Andric auto I = ValueMapping.find(Inst);
11290b57cec5SDimitry Andric if (I != ValueMapping.end())
11300b57cec5SDimitry Andric New->setOperand(i, I->second);
11310b57cec5SDimitry Andric }
11320b57cec5SDimitry Andric }
11330b57cec5SDimitry Andric
11340b57cec5SDimitry Andric return NewBB;
11350b57cec5SDimitry Andric }
1136e8d8bef9SDimitry Andric
cloneNoAliasScopes(ArrayRef<MDNode * > NoAliasDeclScopes,DenseMap<MDNode *,MDNode * > & ClonedScopes,StringRef Ext,LLVMContext & Context)1137fe6060f1SDimitry Andric void llvm::cloneNoAliasScopes(ArrayRef<MDNode *> NoAliasDeclScopes,
1138e8d8bef9SDimitry Andric DenseMap<MDNode *, MDNode *> &ClonedScopes,
1139e8d8bef9SDimitry Andric StringRef Ext, LLVMContext &Context) {
1140e8d8bef9SDimitry Andric MDBuilder MDB(Context);
1141e8d8bef9SDimitry Andric
1142e8d8bef9SDimitry Andric for (auto *ScopeList : NoAliasDeclScopes) {
1143bdd1243dSDimitry Andric for (const auto &MDOperand : ScopeList->operands()) {
1144e8d8bef9SDimitry Andric if (MDNode *MD = dyn_cast<MDNode>(MDOperand)) {
1145e8d8bef9SDimitry Andric AliasScopeNode SNANode(MD);
1146e8d8bef9SDimitry Andric
1147e8d8bef9SDimitry Andric std::string Name;
1148e8d8bef9SDimitry Andric auto ScopeName = SNANode.getName();
1149e8d8bef9SDimitry Andric if (!ScopeName.empty())
1150e8d8bef9SDimitry Andric Name = (Twine(ScopeName) + ":" + Ext).str();
1151e8d8bef9SDimitry Andric else
1152e8d8bef9SDimitry Andric Name = std::string(Ext);
1153e8d8bef9SDimitry Andric
1154e8d8bef9SDimitry Andric MDNode *NewScope = MDB.createAnonymousAliasScope(
1155e8d8bef9SDimitry Andric const_cast<MDNode *>(SNANode.getDomain()), Name);
1156e8d8bef9SDimitry Andric ClonedScopes.insert(std::make_pair(MD, NewScope));
1157e8d8bef9SDimitry Andric }
1158e8d8bef9SDimitry Andric }
1159e8d8bef9SDimitry Andric }
1160e8d8bef9SDimitry Andric }
1161e8d8bef9SDimitry Andric
adaptNoAliasScopes(Instruction * I,const DenseMap<MDNode *,MDNode * > & ClonedScopes,LLVMContext & Context)1162fe6060f1SDimitry Andric void llvm::adaptNoAliasScopes(Instruction *I,
1163fe6060f1SDimitry Andric const DenseMap<MDNode *, MDNode *> &ClonedScopes,
1164e8d8bef9SDimitry Andric LLVMContext &Context) {
1165e8d8bef9SDimitry Andric auto CloneScopeList = [&](const MDNode *ScopeList) -> MDNode * {
1166e8d8bef9SDimitry Andric bool NeedsReplacement = false;
1167e8d8bef9SDimitry Andric SmallVector<Metadata *, 8> NewScopeList;
1168bdd1243dSDimitry Andric for (const auto &MDOp : ScopeList->operands()) {
1169e8d8bef9SDimitry Andric if (MDNode *MD = dyn_cast<MDNode>(MDOp)) {
1170e8d8bef9SDimitry Andric if (auto *NewMD = ClonedScopes.lookup(MD)) {
1171e8d8bef9SDimitry Andric NewScopeList.push_back(NewMD);
1172e8d8bef9SDimitry Andric NeedsReplacement = true;
1173e8d8bef9SDimitry Andric continue;
1174e8d8bef9SDimitry Andric }
1175e8d8bef9SDimitry Andric NewScopeList.push_back(MD);
1176e8d8bef9SDimitry Andric }
1177e8d8bef9SDimitry Andric }
1178e8d8bef9SDimitry Andric if (NeedsReplacement)
1179e8d8bef9SDimitry Andric return MDNode::get(Context, NewScopeList);
1180e8d8bef9SDimitry Andric return nullptr;
1181e8d8bef9SDimitry Andric };
1182e8d8bef9SDimitry Andric
1183e8d8bef9SDimitry Andric if (auto *Decl = dyn_cast<NoAliasScopeDeclInst>(I))
1184e8d8bef9SDimitry Andric if (auto *NewScopeList = CloneScopeList(Decl->getScopeList()))
1185e8d8bef9SDimitry Andric Decl->setScopeList(NewScopeList);
1186e8d8bef9SDimitry Andric
1187e8d8bef9SDimitry Andric auto replaceWhenNeeded = [&](unsigned MD_ID) {
1188e8d8bef9SDimitry Andric if (const MDNode *CSNoAlias = I->getMetadata(MD_ID))
1189e8d8bef9SDimitry Andric if (auto *NewScopeList = CloneScopeList(CSNoAlias))
1190e8d8bef9SDimitry Andric I->setMetadata(MD_ID, NewScopeList);
1191e8d8bef9SDimitry Andric };
1192e8d8bef9SDimitry Andric replaceWhenNeeded(LLVMContext::MD_noalias);
1193e8d8bef9SDimitry Andric replaceWhenNeeded(LLVMContext::MD_alias_scope);
1194e8d8bef9SDimitry Andric }
1195e8d8bef9SDimitry Andric
cloneAndAdaptNoAliasScopes(ArrayRef<MDNode * > NoAliasDeclScopes,ArrayRef<BasicBlock * > NewBlocks,LLVMContext & Context,StringRef Ext)1196fe6060f1SDimitry Andric void llvm::cloneAndAdaptNoAliasScopes(ArrayRef<MDNode *> NoAliasDeclScopes,
1197fe6060f1SDimitry Andric ArrayRef<BasicBlock *> NewBlocks,
1198fe6060f1SDimitry Andric LLVMContext &Context, StringRef Ext) {
1199e8d8bef9SDimitry Andric if (NoAliasDeclScopes.empty())
1200e8d8bef9SDimitry Andric return;
1201e8d8bef9SDimitry Andric
1202e8d8bef9SDimitry Andric DenseMap<MDNode *, MDNode *> ClonedScopes;
1203e8d8bef9SDimitry Andric LLVM_DEBUG(dbgs() << "cloneAndAdaptNoAliasScopes: cloning "
1204e8d8bef9SDimitry Andric << NoAliasDeclScopes.size() << " node(s)\n");
1205e8d8bef9SDimitry Andric
1206e8d8bef9SDimitry Andric cloneNoAliasScopes(NoAliasDeclScopes, ClonedScopes, Ext, Context);
1207e8d8bef9SDimitry Andric // Identify instructions using metadata that needs adaptation
1208e8d8bef9SDimitry Andric for (BasicBlock *NewBlock : NewBlocks)
1209e8d8bef9SDimitry Andric for (Instruction &I : *NewBlock)
1210e8d8bef9SDimitry Andric adaptNoAliasScopes(&I, ClonedScopes, Context);
1211e8d8bef9SDimitry Andric }
1212e8d8bef9SDimitry Andric
cloneAndAdaptNoAliasScopes(ArrayRef<MDNode * > NoAliasDeclScopes,Instruction * IStart,Instruction * IEnd,LLVMContext & Context,StringRef Ext)1213fe6060f1SDimitry Andric void llvm::cloneAndAdaptNoAliasScopes(ArrayRef<MDNode *> NoAliasDeclScopes,
1214fe6060f1SDimitry Andric Instruction *IStart, Instruction *IEnd,
1215fe6060f1SDimitry Andric LLVMContext &Context, StringRef Ext) {
1216e8d8bef9SDimitry Andric if (NoAliasDeclScopes.empty())
1217e8d8bef9SDimitry Andric return;
1218e8d8bef9SDimitry Andric
1219e8d8bef9SDimitry Andric DenseMap<MDNode *, MDNode *> ClonedScopes;
1220e8d8bef9SDimitry Andric LLVM_DEBUG(dbgs() << "cloneAndAdaptNoAliasScopes: cloning "
1221e8d8bef9SDimitry Andric << NoAliasDeclScopes.size() << " node(s)\n");
1222e8d8bef9SDimitry Andric
1223e8d8bef9SDimitry Andric cloneNoAliasScopes(NoAliasDeclScopes, ClonedScopes, Ext, Context);
1224e8d8bef9SDimitry Andric // Identify instructions using metadata that needs adaptation
1225e8d8bef9SDimitry Andric assert(IStart->getParent() == IEnd->getParent() && "different basic block ?");
1226e8d8bef9SDimitry Andric auto ItStart = IStart->getIterator();
1227e8d8bef9SDimitry Andric auto ItEnd = IEnd->getIterator();
1228e8d8bef9SDimitry Andric ++ItEnd; // IEnd is included, increment ItEnd to get the end of the range
1229e8d8bef9SDimitry Andric for (auto &I : llvm::make_range(ItStart, ItEnd))
1230e8d8bef9SDimitry Andric adaptNoAliasScopes(&I, ClonedScopes, Context);
1231e8d8bef9SDimitry Andric }
1232e8d8bef9SDimitry Andric
identifyNoAliasScopesToClone(ArrayRef<BasicBlock * > BBs,SmallVectorImpl<MDNode * > & NoAliasDeclScopes)1233e8d8bef9SDimitry Andric void llvm::identifyNoAliasScopesToClone(
1234e8d8bef9SDimitry Andric ArrayRef<BasicBlock *> BBs, SmallVectorImpl<MDNode *> &NoAliasDeclScopes) {
1235e8d8bef9SDimitry Andric for (BasicBlock *BB : BBs)
1236e8d8bef9SDimitry Andric for (Instruction &I : *BB)
1237e8d8bef9SDimitry Andric if (auto *Decl = dyn_cast<NoAliasScopeDeclInst>(&I))
1238e8d8bef9SDimitry Andric NoAliasDeclScopes.push_back(Decl->getScopeList());
1239e8d8bef9SDimitry Andric }
1240d409305fSDimitry Andric
identifyNoAliasScopesToClone(BasicBlock::iterator Start,BasicBlock::iterator End,SmallVectorImpl<MDNode * > & NoAliasDeclScopes)1241d409305fSDimitry Andric void llvm::identifyNoAliasScopesToClone(
1242d409305fSDimitry Andric BasicBlock::iterator Start, BasicBlock::iterator End,
1243d409305fSDimitry Andric SmallVectorImpl<MDNode *> &NoAliasDeclScopes) {
1244d409305fSDimitry Andric for (Instruction &I : make_range(Start, End))
1245d409305fSDimitry Andric if (auto *Decl = dyn_cast<NoAliasScopeDeclInst>(&I))
1246d409305fSDimitry Andric NoAliasDeclScopes.push_back(Decl->getScopeList());
1247d409305fSDimitry Andric }
1248