1 //===- Cloning.cpp - Unit tests for the Cloner ----------------------------===//
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 #include "llvm/Transforms/Utils/Cloning.h"
10 #include "llvm/ADT/STLExtras.h"
11 #include "llvm/ADT/SmallPtrSet.h"
12 #include "llvm/Analysis/AliasAnalysis.h"
13 #include "llvm/Analysis/DomTreeUpdater.h"
14 #include "llvm/Analysis/LoopInfo.h"
15 #include "llvm/AsmParser/Parser.h"
16 #include "llvm/IR/Argument.h"
17 #include "llvm/IR/Constant.h"
18 #include "llvm/IR/DIBuilder.h"
19 #include "llvm/IR/DebugInfo.h"
20 #include "llvm/IR/Function.h"
21 #include "llvm/IR/IRBuilder.h"
22 #include "llvm/IR/InstIterator.h"
23 #include "llvm/IR/Instructions.h"
24 #include "llvm/IR/IntrinsicInst.h"
25 #include "llvm/IR/LLVMContext.h"
26 #include "llvm/IR/Module.h"
27 #include "llvm/IR/Verifier.h"
28 #include "llvm/Support/SourceMgr.h"
29 #include "gtest/gtest.h"
30 
31 using namespace llvm;
32 
33 namespace {
34 
35 class CloneInstruction : public ::testing::Test {
36 protected:
37   void SetUp() override { V = nullptr; }
38 
39   template <typename T>
40   T *clone(T *V1) {
41     Value *V2 = V1->clone();
42     Orig.insert(V1);
43     Clones.insert(V2);
44     return cast<T>(V2);
45   }
46 
47   void eraseClones() {
48     for (Value *V : Clones)
49       V->deleteValue();
50     Clones.clear();
51   }
52 
53   void TearDown() override {
54     eraseClones();
55     for (Value *V : Orig)
56       V->deleteValue();
57     Orig.clear();
58     if (V)
59       V->deleteValue();
60   }
61 
62   SmallPtrSet<Value *, 4> Orig;   // Erase on exit
63   SmallPtrSet<Value *, 4> Clones; // Erase in eraseClones
64 
65   LLVMContext context;
66   Value *V;
67 };
68 
69 TEST_F(CloneInstruction, OverflowBits) {
70   V = new Argument(Type::getInt32Ty(context));
71 
72   BinaryOperator *Add = BinaryOperator::Create(Instruction::Add, V, V);
73   BinaryOperator *Sub = BinaryOperator::Create(Instruction::Sub, V, V);
74   BinaryOperator *Mul = BinaryOperator::Create(Instruction::Mul, V, V);
75 
76   BinaryOperator *AddClone = this->clone(Add);
77   BinaryOperator *SubClone = this->clone(Sub);
78   BinaryOperator *MulClone = this->clone(Mul);
79 
80   EXPECT_FALSE(AddClone->hasNoUnsignedWrap());
81   EXPECT_FALSE(AddClone->hasNoSignedWrap());
82   EXPECT_FALSE(SubClone->hasNoUnsignedWrap());
83   EXPECT_FALSE(SubClone->hasNoSignedWrap());
84   EXPECT_FALSE(MulClone->hasNoUnsignedWrap());
85   EXPECT_FALSE(MulClone->hasNoSignedWrap());
86 
87   eraseClones();
88 
89   Add->setHasNoUnsignedWrap();
90   Sub->setHasNoUnsignedWrap();
91   Mul->setHasNoUnsignedWrap();
92 
93   AddClone = this->clone(Add);
94   SubClone = this->clone(Sub);
95   MulClone = this->clone(Mul);
96 
97   EXPECT_TRUE(AddClone->hasNoUnsignedWrap());
98   EXPECT_FALSE(AddClone->hasNoSignedWrap());
99   EXPECT_TRUE(SubClone->hasNoUnsignedWrap());
100   EXPECT_FALSE(SubClone->hasNoSignedWrap());
101   EXPECT_TRUE(MulClone->hasNoUnsignedWrap());
102   EXPECT_FALSE(MulClone->hasNoSignedWrap());
103 
104   eraseClones();
105 
106   Add->setHasNoSignedWrap();
107   Sub->setHasNoSignedWrap();
108   Mul->setHasNoSignedWrap();
109 
110   AddClone = this->clone(Add);
111   SubClone = this->clone(Sub);
112   MulClone = this->clone(Mul);
113 
114   EXPECT_TRUE(AddClone->hasNoUnsignedWrap());
115   EXPECT_TRUE(AddClone->hasNoSignedWrap());
116   EXPECT_TRUE(SubClone->hasNoUnsignedWrap());
117   EXPECT_TRUE(SubClone->hasNoSignedWrap());
118   EXPECT_TRUE(MulClone->hasNoUnsignedWrap());
119   EXPECT_TRUE(MulClone->hasNoSignedWrap());
120 
121   eraseClones();
122 
123   Add->setHasNoUnsignedWrap(false);
124   Sub->setHasNoUnsignedWrap(false);
125   Mul->setHasNoUnsignedWrap(false);
126 
127   AddClone = this->clone(Add);
128   SubClone = this->clone(Sub);
129   MulClone = this->clone(Mul);
130 
131   EXPECT_FALSE(AddClone->hasNoUnsignedWrap());
132   EXPECT_TRUE(AddClone->hasNoSignedWrap());
133   EXPECT_FALSE(SubClone->hasNoUnsignedWrap());
134   EXPECT_TRUE(SubClone->hasNoSignedWrap());
135   EXPECT_FALSE(MulClone->hasNoUnsignedWrap());
136   EXPECT_TRUE(MulClone->hasNoSignedWrap());
137 }
138 
139 TEST_F(CloneInstruction, Inbounds) {
140   V = new Argument(Type::getInt32PtrTy(context));
141 
142   Constant *Z = Constant::getNullValue(Type::getInt32Ty(context));
143   std::vector<Value *> ops;
144   ops.push_back(Z);
145   GetElementPtrInst *GEP =
146       GetElementPtrInst::Create(Type::getInt32Ty(context), V, ops);
147   EXPECT_FALSE(this->clone(GEP)->isInBounds());
148 
149   GEP->setIsInBounds();
150   EXPECT_TRUE(this->clone(GEP)->isInBounds());
151 }
152 
153 TEST_F(CloneInstruction, Exact) {
154   V = new Argument(Type::getInt32Ty(context));
155 
156   BinaryOperator *SDiv = BinaryOperator::Create(Instruction::SDiv, V, V);
157   EXPECT_FALSE(this->clone(SDiv)->isExact());
158 
159   SDiv->setIsExact(true);
160   EXPECT_TRUE(this->clone(SDiv)->isExact());
161 }
162 
163 TEST_F(CloneInstruction, Attributes) {
164   Type *ArgTy1[] = { Type::getInt32PtrTy(context) };
165   FunctionType *FT1 =  FunctionType::get(Type::getVoidTy(context), ArgTy1, false);
166 
167   Function *F1 = Function::Create(FT1, Function::ExternalLinkage);
168   BasicBlock *BB = BasicBlock::Create(context, "", F1);
169   IRBuilder<> Builder(BB);
170   Builder.CreateRetVoid();
171 
172   Function *F2 = Function::Create(FT1, Function::ExternalLinkage);
173 
174   Argument *A = &*F1->arg_begin();
175   A->addAttr(Attribute::NoCapture);
176 
177   SmallVector<ReturnInst*, 4> Returns;
178   ValueToValueMapTy VMap;
179   VMap[A] = UndefValue::get(A->getType());
180 
181   CloneFunctionInto(F2, F1, VMap, CloneFunctionChangeType::LocalChangesOnly,
182                     Returns);
183   EXPECT_FALSE(F2->arg_begin()->hasNoCaptureAttr());
184 
185   delete F1;
186   delete F2;
187 }
188 
189 TEST_F(CloneInstruction, CallingConvention) {
190   Type *ArgTy1[] = { Type::getInt32PtrTy(context) };
191   FunctionType *FT1 =  FunctionType::get(Type::getVoidTy(context), ArgTy1, false);
192 
193   Function *F1 = Function::Create(FT1, Function::ExternalLinkage);
194   F1->setCallingConv(CallingConv::Cold);
195   BasicBlock *BB = BasicBlock::Create(context, "", F1);
196   IRBuilder<> Builder(BB);
197   Builder.CreateRetVoid();
198 
199   Function *F2 = Function::Create(FT1, Function::ExternalLinkage);
200 
201   SmallVector<ReturnInst*, 4> Returns;
202   ValueToValueMapTy VMap;
203   VMap[&*F1->arg_begin()] = &*F2->arg_begin();
204 
205   CloneFunctionInto(F2, F1, VMap, CloneFunctionChangeType::LocalChangesOnly,
206                     Returns);
207   EXPECT_EQ(CallingConv::Cold, F2->getCallingConv());
208 
209   delete F1;
210   delete F2;
211 }
212 
213 TEST_F(CloneInstruction, DuplicateInstructionsToSplit) {
214   Type *ArgTy1[] = {Type::getInt32PtrTy(context)};
215   FunctionType *FT = FunctionType::get(Type::getVoidTy(context), ArgTy1, false);
216   V = new Argument(Type::getInt32Ty(context));
217 
218   Function *F = Function::Create(FT, Function::ExternalLinkage);
219 
220   BasicBlock *BB1 = BasicBlock::Create(context, "", F);
221   IRBuilder<> Builder1(BB1);
222 
223   BasicBlock *BB2 = BasicBlock::Create(context, "", F);
224   IRBuilder<> Builder2(BB2);
225 
226   Builder1.CreateBr(BB2);
227 
228   Instruction *AddInst = cast<Instruction>(Builder2.CreateAdd(V, V));
229   Instruction *MulInst = cast<Instruction>(Builder2.CreateMul(AddInst, V));
230   Instruction *SubInst = cast<Instruction>(Builder2.CreateSub(MulInst, V));
231   Builder2.CreateRetVoid();
232 
233   // Dummy DTU.
234   ValueToValueMapTy Mapping;
235   DomTreeUpdater DTU(DomTreeUpdater::UpdateStrategy::Lazy);
236   auto Split =
237       DuplicateInstructionsInSplitBetween(BB2, BB1, SubInst, Mapping, DTU);
238 
239   EXPECT_TRUE(Split);
240   EXPECT_EQ(Mapping.size(), 2u);
241   EXPECT_TRUE(Mapping.find(AddInst) != Mapping.end());
242   EXPECT_TRUE(Mapping.find(MulInst) != Mapping.end());
243 
244   auto AddSplit = dyn_cast<Instruction>(Mapping[AddInst]);
245   EXPECT_TRUE(AddSplit);
246   EXPECT_EQ(AddSplit->getOperand(0), V);
247   EXPECT_EQ(AddSplit->getOperand(1), V);
248   EXPECT_EQ(AddSplit->getParent(), Split);
249 
250   auto MulSplit = dyn_cast<Instruction>(Mapping[MulInst]);
251   EXPECT_TRUE(MulSplit);
252   EXPECT_EQ(MulSplit->getOperand(0), AddSplit);
253   EXPECT_EQ(MulSplit->getOperand(1), V);
254   EXPECT_EQ(MulSplit->getParent(), Split);
255 
256   EXPECT_EQ(AddSplit->getNextNode(), MulSplit);
257   EXPECT_EQ(MulSplit->getNextNode(), Split->getTerminator());
258 
259   delete F;
260 }
261 
262 TEST_F(CloneInstruction, DuplicateInstructionsToSplitBlocksEq1) {
263   Type *ArgTy1[] = {Type::getInt32PtrTy(context)};
264   FunctionType *FT = FunctionType::get(Type::getVoidTy(context), ArgTy1, false);
265   V = new Argument(Type::getInt32Ty(context));
266 
267   Function *F = Function::Create(FT, Function::ExternalLinkage);
268 
269   BasicBlock *BB1 = BasicBlock::Create(context, "", F);
270   IRBuilder<> Builder1(BB1);
271 
272   BasicBlock *BB2 = BasicBlock::Create(context, "", F);
273   IRBuilder<> Builder2(BB2);
274 
275   Builder1.CreateBr(BB2);
276 
277   Instruction *AddInst = cast<Instruction>(Builder2.CreateAdd(V, V));
278   Instruction *MulInst = cast<Instruction>(Builder2.CreateMul(AddInst, V));
279   Instruction *SubInst = cast<Instruction>(Builder2.CreateSub(MulInst, V));
280   Builder2.CreateBr(BB2);
281 
282   // Dummy DTU.
283   DomTreeUpdater DTU(DomTreeUpdater::UpdateStrategy::Lazy);
284   ValueToValueMapTy Mapping;
285   auto Split = DuplicateInstructionsInSplitBetween(
286       BB2, BB2, BB2->getTerminator(), Mapping, DTU);
287 
288   EXPECT_TRUE(Split);
289   EXPECT_EQ(Mapping.size(), 3u);
290   EXPECT_TRUE(Mapping.find(AddInst) != Mapping.end());
291   EXPECT_TRUE(Mapping.find(MulInst) != Mapping.end());
292   EXPECT_TRUE(Mapping.find(SubInst) != Mapping.end());
293 
294   auto AddSplit = dyn_cast<Instruction>(Mapping[AddInst]);
295   EXPECT_TRUE(AddSplit);
296   EXPECT_EQ(AddSplit->getOperand(0), V);
297   EXPECT_EQ(AddSplit->getOperand(1), V);
298   EXPECT_EQ(AddSplit->getParent(), Split);
299 
300   auto MulSplit = dyn_cast<Instruction>(Mapping[MulInst]);
301   EXPECT_TRUE(MulSplit);
302   EXPECT_EQ(MulSplit->getOperand(0), AddSplit);
303   EXPECT_EQ(MulSplit->getOperand(1), V);
304   EXPECT_EQ(MulSplit->getParent(), Split);
305 
306   auto SubSplit = dyn_cast<Instruction>(Mapping[SubInst]);
307   EXPECT_EQ(MulSplit->getNextNode(), SubSplit);
308   EXPECT_EQ(SubSplit->getNextNode(), Split->getTerminator());
309   EXPECT_EQ(Split->getSingleSuccessor(), BB2);
310   EXPECT_EQ(BB2->getSingleSuccessor(), Split);
311 
312   delete F;
313 }
314 
315 TEST_F(CloneInstruction, DuplicateInstructionsToSplitBlocksEq2) {
316   Type *ArgTy1[] = {Type::getInt32PtrTy(context)};
317   FunctionType *FT = FunctionType::get(Type::getVoidTy(context), ArgTy1, false);
318   V = new Argument(Type::getInt32Ty(context));
319 
320   Function *F = Function::Create(FT, Function::ExternalLinkage);
321 
322   BasicBlock *BB1 = BasicBlock::Create(context, "", F);
323   IRBuilder<> Builder1(BB1);
324 
325   BasicBlock *BB2 = BasicBlock::Create(context, "", F);
326   IRBuilder<> Builder2(BB2);
327 
328   Builder1.CreateBr(BB2);
329 
330   Instruction *AddInst = cast<Instruction>(Builder2.CreateAdd(V, V));
331   Instruction *MulInst = cast<Instruction>(Builder2.CreateMul(AddInst, V));
332   Instruction *SubInst = cast<Instruction>(Builder2.CreateSub(MulInst, V));
333   Builder2.CreateBr(BB2);
334 
335   // Dummy DTU.
336   DomTreeUpdater DTU(DomTreeUpdater::UpdateStrategy::Lazy);
337   ValueToValueMapTy Mapping;
338   auto Split =
339       DuplicateInstructionsInSplitBetween(BB2, BB2, SubInst, Mapping, DTU);
340 
341   EXPECT_TRUE(Split);
342   EXPECT_EQ(Mapping.size(), 2u);
343   EXPECT_TRUE(Mapping.find(AddInst) != Mapping.end());
344   EXPECT_TRUE(Mapping.find(MulInst) != Mapping.end());
345 
346   auto AddSplit = dyn_cast<Instruction>(Mapping[AddInst]);
347   EXPECT_TRUE(AddSplit);
348   EXPECT_EQ(AddSplit->getOperand(0), V);
349   EXPECT_EQ(AddSplit->getOperand(1), V);
350   EXPECT_EQ(AddSplit->getParent(), Split);
351 
352   auto MulSplit = dyn_cast<Instruction>(Mapping[MulInst]);
353   EXPECT_TRUE(MulSplit);
354   EXPECT_EQ(MulSplit->getOperand(0), AddSplit);
355   EXPECT_EQ(MulSplit->getOperand(1), V);
356   EXPECT_EQ(MulSplit->getParent(), Split);
357   EXPECT_EQ(MulSplit->getNextNode(), Split->getTerminator());
358   EXPECT_EQ(Split->getSingleSuccessor(), BB2);
359   EXPECT_EQ(BB2->getSingleSuccessor(), Split);
360 
361   delete F;
362 }
363 
364 static void runWithLoopInfoAndDominatorTree(
365     Module &M, StringRef FuncName,
366     function_ref<void(Function &F, LoopInfo &LI, DominatorTree &DT)> Test) {
367   auto *F = M.getFunction(FuncName);
368   ASSERT_NE(F, nullptr) << "Could not find " << FuncName;
369 
370   DominatorTree DT(*F);
371   LoopInfo LI(DT);
372 
373   Test(*F, LI, DT);
374 }
375 
376 static std::unique_ptr<Module> parseIR(LLVMContext &C, const char *IR) {
377   SMDiagnostic Err;
378   std::unique_ptr<Module> Mod = parseAssemblyString(IR, Err, C);
379   if (!Mod)
380     Err.print("CloneLoop", errs());
381   return Mod;
382 }
383 
384 TEST(CloneLoop, CloneLoopNest) {
385   // Parse the module.
386   LLVMContext Context;
387 
388   std::unique_ptr<Module> M = parseIR(
389     Context,
390     R"(define void @foo(i32* %A, i32 %ub) {
391 entry:
392   %guardcmp = icmp slt i32 0, %ub
393   br i1 %guardcmp, label %for.outer.preheader, label %for.end
394 for.outer.preheader:
395   br label %for.outer
396 for.outer:
397   %j = phi i32 [ 0, %for.outer.preheader ], [ %inc.outer, %for.outer.latch ]
398   br i1 %guardcmp, label %for.inner.preheader, label %for.outer.latch
399 for.inner.preheader:
400   br label %for.inner
401 for.inner:
402   %i = phi i32 [ 0, %for.inner.preheader ], [ %inc, %for.inner ]
403   %idxprom = sext i32 %i to i64
404   %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom
405   store i32 %i, i32* %arrayidx, align 4
406   %inc = add nsw i32 %i, 1
407   %cmp = icmp slt i32 %inc, %ub
408   br i1 %cmp, label %for.inner, label %for.inner.exit
409 for.inner.exit:
410   br label %for.outer.latch
411 for.outer.latch:
412   %inc.outer = add nsw i32 %j, 1
413   %cmp.outer = icmp slt i32 %inc.outer, %ub
414   br i1 %cmp.outer, label %for.outer, label %for.outer.exit
415 for.outer.exit:
416   br label %for.end
417 for.end:
418   ret void
419 })"
420     );
421 
422   runWithLoopInfoAndDominatorTree(
423       *M, "foo", [&](Function &F, LoopInfo &LI, DominatorTree &DT) {
424         Function::iterator FI = F.begin();
425         // First basic block is entry - skip it.
426         BasicBlock *Preheader = &*(++FI);
427         BasicBlock *Header = &*(++FI);
428         assert(Header->getName() == "for.outer");
429         Loop *L = LI.getLoopFor(Header);
430         EXPECT_NE(L, nullptr);
431         EXPECT_EQ(Header, L->getHeader());
432         EXPECT_EQ(Preheader, L->getLoopPreheader());
433 
434         ValueToValueMapTy VMap;
435         SmallVector<BasicBlock *, 4> ClonedLoopBlocks;
436         Loop *NewLoop = cloneLoopWithPreheader(Preheader, Preheader, L, VMap,
437                                                "", &LI, &DT, ClonedLoopBlocks);
438         EXPECT_NE(NewLoop, nullptr);
439         EXPECT_EQ(NewLoop->getSubLoops().size(), 1u);
440         Loop::block_iterator BI = NewLoop->block_begin();
441         EXPECT_TRUE((*BI)->getName().startswith("for.outer"));
442         EXPECT_TRUE((*(++BI))->getName().startswith("for.inner.preheader"));
443         EXPECT_TRUE((*(++BI))->getName().startswith("for.inner"));
444         EXPECT_TRUE((*(++BI))->getName().startswith("for.inner.exit"));
445         EXPECT_TRUE((*(++BI))->getName().startswith("for.outer.latch"));
446       });
447 }
448 
449 class CloneFunc : public ::testing::Test {
450 protected:
451   void SetUp() override {
452     SetupModule();
453     CreateOldFunc();
454     CreateNewFunc();
455     SetupFinder();
456   }
457 
458   void TearDown() override { delete Finder; }
459 
460   void SetupModule() {
461     M = new Module("", C);
462   }
463 
464   void CreateOldFunc() {
465     FunctionType* FuncType = FunctionType::get(Type::getVoidTy(C), false);
466     OldFunc = Function::Create(FuncType, GlobalValue::PrivateLinkage, "f", M);
467     CreateOldFunctionBodyAndDI();
468   }
469 
470   void CreateOldFunctionBodyAndDI() {
471     DIBuilder DBuilder(*M);
472     IRBuilder<> IBuilder(C);
473 
474     // Function DI
475     auto *File = DBuilder.createFile("filename.c", "/file/dir/");
476     DITypeRefArray ParamTypes = DBuilder.getOrCreateTypeArray(None);
477     DISubroutineType *FuncType =
478         DBuilder.createSubroutineType(ParamTypes);
479     auto *CU = DBuilder.createCompileUnit(dwarf::DW_LANG_C99,
480                                           DBuilder.createFile("filename.c",
481                                                               "/file/dir"),
482                                           "CloneFunc", false, "", 0);
483 
484     auto *Subprogram = DBuilder.createFunction(
485         CU, "f", "f", File, 4, FuncType, 3, DINode::FlagZero,
486         DISubprogram::SPFlagLocalToUnit | DISubprogram::SPFlagDefinition);
487     OldFunc->setSubprogram(Subprogram);
488 
489     // Function body
490     BasicBlock* Entry = BasicBlock::Create(C, "", OldFunc);
491     IBuilder.SetInsertPoint(Entry);
492     DebugLoc Loc = DILocation::get(Subprogram->getContext(), 3, 2, Subprogram);
493     IBuilder.SetCurrentDebugLocation(Loc);
494     AllocaInst* Alloca = IBuilder.CreateAlloca(IntegerType::getInt32Ty(C));
495     IBuilder.SetCurrentDebugLocation(
496         DILocation::get(Subprogram->getContext(), 4, 2, Subprogram));
497     Value* AllocaContent = IBuilder.getInt32(1);
498     Instruction* Store = IBuilder.CreateStore(AllocaContent, Alloca);
499     IBuilder.SetCurrentDebugLocation(
500         DILocation::get(Subprogram->getContext(), 5, 2, Subprogram));
501 
502     // Create a local variable around the alloca
503     auto *IntType = DBuilder.createBasicType("int", 32, dwarf::DW_ATE_signed);
504     auto *E = DBuilder.createExpression();
505     auto *Variable =
506         DBuilder.createAutoVariable(Subprogram, "x", File, 5, IntType, true);
507     auto *DL = DILocation::get(Subprogram->getContext(), 5, 0, Subprogram);
508     DBuilder.insertDeclare(Alloca, Variable, E, DL, Store);
509     DBuilder.insertDbgValueIntrinsic(AllocaContent, Variable, E, DL, Entry);
510     // Also create an inlined variable.
511     // Create a distinct struct type that we should not duplicate during
512     // cloning).
513     auto *StructType = DICompositeType::getDistinct(
514         C, dwarf::DW_TAG_structure_type, "some_struct", nullptr, 0, nullptr,
515         nullptr, 32, 32, 0, DINode::FlagZero, nullptr, 0, nullptr, nullptr);
516     auto *InlinedSP = DBuilder.createFunction(
517         CU, "inlined", "inlined", File, 8, FuncType, 9, DINode::FlagZero,
518         DISubprogram::SPFlagLocalToUnit | DISubprogram::SPFlagDefinition);
519     auto *InlinedVar =
520         DBuilder.createAutoVariable(InlinedSP, "inlined", File, 5, StructType, true);
521     auto *Scope = DBuilder.createLexicalBlock(
522         DBuilder.createLexicalBlockFile(InlinedSP, File), File, 1, 1);
523     auto InlinedDL = DILocation::get(
524         Subprogram->getContext(), 9, 4, Scope,
525         DILocation::get(Subprogram->getContext(), 5, 2, Subprogram));
526     IBuilder.SetCurrentDebugLocation(InlinedDL);
527     DBuilder.insertDeclare(Alloca, InlinedVar, E, InlinedDL, Store);
528     IBuilder.CreateStore(IBuilder.getInt32(2), Alloca);
529     // Finalize the debug info.
530     DBuilder.finalize();
531     IBuilder.CreateRetVoid();
532 
533     // Create another, empty, compile unit.
534     DIBuilder DBuilder2(*M);
535     DBuilder2.createCompileUnit(dwarf::DW_LANG_C99,
536                                 DBuilder.createFile("extra.c", "/file/dir"),
537                                 "CloneFunc", false, "", 0);
538     DBuilder2.finalize();
539   }
540 
541   void CreateNewFunc() {
542     ValueToValueMapTy VMap;
543     NewFunc = CloneFunction(OldFunc, VMap, nullptr);
544   }
545 
546   void SetupFinder() {
547     Finder = new DebugInfoFinder();
548     Finder->processModule(*M);
549   }
550 
551   LLVMContext C;
552   Function* OldFunc;
553   Function* NewFunc;
554   Module* M;
555   DebugInfoFinder* Finder;
556 };
557 
558 // Test that a new, distinct function was created.
559 TEST_F(CloneFunc, NewFunctionCreated) {
560   EXPECT_NE(OldFunc, NewFunc);
561 }
562 
563 // Test that a new subprogram entry was added and is pointing to the new
564 // function, while the original subprogram still points to the old one.
565 TEST_F(CloneFunc, Subprogram) {
566   EXPECT_FALSE(verifyModule(*M, &errs()));
567   EXPECT_EQ(3U, Finder->subprogram_count());
568   EXPECT_NE(NewFunc->getSubprogram(), OldFunc->getSubprogram());
569 }
570 
571 // Test that instructions in the old function still belong to it in the
572 // metadata, while instruction in the new function belong to the new one.
573 TEST_F(CloneFunc, InstructionOwnership) {
574   EXPECT_FALSE(verifyModule(*M));
575 
576   inst_iterator OldIter = inst_begin(OldFunc);
577   inst_iterator OldEnd = inst_end(OldFunc);
578   inst_iterator NewIter = inst_begin(NewFunc);
579   inst_iterator NewEnd = inst_end(NewFunc);
580   while (OldIter != OldEnd && NewIter != NewEnd) {
581     Instruction& OldI = *OldIter;
582     Instruction& NewI = *NewIter;
583     EXPECT_NE(&OldI, &NewI);
584 
585     EXPECT_EQ(OldI.hasMetadata(), NewI.hasMetadata());
586     if (OldI.hasMetadata()) {
587       const DebugLoc& OldDL = OldI.getDebugLoc();
588       const DebugLoc& NewDL = NewI.getDebugLoc();
589 
590       // Verify that the debug location data is the same
591       EXPECT_EQ(OldDL.getLine(), NewDL.getLine());
592       EXPECT_EQ(OldDL.getCol(), NewDL.getCol());
593 
594       // But that they belong to different functions
595       auto *OldSubprogram = cast<DISubprogram>(OldDL.getInlinedAtScope());
596       auto *NewSubprogram = cast<DISubprogram>(NewDL.getInlinedAtScope());
597       EXPECT_EQ(OldFunc->getSubprogram(), OldSubprogram);
598       EXPECT_EQ(NewFunc->getSubprogram(), NewSubprogram);
599     }
600 
601     ++OldIter;
602     ++NewIter;
603   }
604   EXPECT_EQ(OldEnd, OldIter);
605   EXPECT_EQ(NewEnd, NewIter);
606 }
607 
608 // Test that the arguments for debug intrinsics in the new function were
609 // properly cloned
610 TEST_F(CloneFunc, DebugIntrinsics) {
611   EXPECT_FALSE(verifyModule(*M));
612 
613   inst_iterator OldIter = inst_begin(OldFunc);
614   inst_iterator OldEnd = inst_end(OldFunc);
615   inst_iterator NewIter = inst_begin(NewFunc);
616   inst_iterator NewEnd = inst_end(NewFunc);
617   while (OldIter != OldEnd && NewIter != NewEnd) {
618     Instruction& OldI = *OldIter;
619     Instruction& NewI = *NewIter;
620     if (DbgDeclareInst* OldIntrin = dyn_cast<DbgDeclareInst>(&OldI)) {
621       DbgDeclareInst* NewIntrin = dyn_cast<DbgDeclareInst>(&NewI);
622       EXPECT_TRUE(NewIntrin);
623 
624       // Old address must belong to the old function
625       EXPECT_EQ(OldFunc, cast<AllocaInst>(OldIntrin->getAddress())->
626                          getParent()->getParent());
627       // New address must belong to the new function
628       EXPECT_EQ(NewFunc, cast<AllocaInst>(NewIntrin->getAddress())->
629                          getParent()->getParent());
630 
631       if (OldIntrin->getDebugLoc()->getInlinedAt()) {
632         // Inlined variable should refer to the same DILocalVariable as in the
633         // Old Function
634         EXPECT_EQ(OldIntrin->getVariable(), NewIntrin->getVariable());
635       } else {
636         // Old variable must belong to the old function.
637         EXPECT_EQ(OldFunc->getSubprogram(),
638                   cast<DISubprogram>(OldIntrin->getVariable()->getScope()));
639         // New variable must belong to the new function.
640         EXPECT_EQ(NewFunc->getSubprogram(),
641                   cast<DISubprogram>(NewIntrin->getVariable()->getScope()));
642       }
643     } else if (DbgValueInst* OldIntrin = dyn_cast<DbgValueInst>(&OldI)) {
644       DbgValueInst* NewIntrin = dyn_cast<DbgValueInst>(&NewI);
645       EXPECT_TRUE(NewIntrin);
646 
647       if (!OldIntrin->getDebugLoc()->getInlinedAt()) {
648         // Old variable must belong to the old function.
649         EXPECT_EQ(OldFunc->getSubprogram(),
650                   cast<DISubprogram>(OldIntrin->getVariable()->getScope()));
651         // New variable must belong to the new function.
652         EXPECT_EQ(NewFunc->getSubprogram(),
653                   cast<DISubprogram>(NewIntrin->getVariable()->getScope()));
654       }
655     }
656 
657     ++OldIter;
658     ++NewIter;
659   }
660 }
661 
662 static int GetDICompileUnitCount(const Module& M) {
663   if (const auto* LLVM_DBG_CU = M.getNamedMetadata("llvm.dbg.cu")) {
664     return LLVM_DBG_CU->getNumOperands();
665   }
666   return 0;
667 }
668 
669 static bool haveCompileUnitsInCommon(const Module &LHS, const Module &RHS) {
670   const NamedMDNode *LHSCUs = LHS.getNamedMetadata("llvm.dbg.cu");
671   if (!LHSCUs)
672     return false;
673 
674   const NamedMDNode *RHSCUs = RHS.getNamedMetadata("llvm.dbg.cu");
675   if (!RHSCUs)
676     return false;
677 
678   SmallPtrSet<const MDNode *, 8> Found;
679   for (int I = 0, E = LHSCUs->getNumOperands(); I != E; ++I)
680     if (const MDNode *N = LHSCUs->getOperand(I))
681       Found.insert(N);
682 
683   for (int I = 0, E = RHSCUs->getNumOperands(); I != E; ++I)
684     if (const MDNode *N = RHSCUs->getOperand(I))
685       if (Found.count(N))
686         return true;
687 
688   return false;
689 }
690 
691 TEST(CloneFunction, CloneEmptyFunction) {
692   StringRef ImplAssembly = R"(
693     define void @foo() {
694       ret void
695     }
696     declare void @bar()
697   )";
698 
699   LLVMContext Context;
700   SMDiagnostic Error;
701 
702   auto ImplModule = parseAssemblyString(ImplAssembly, Error, Context);
703   EXPECT_TRUE(ImplModule != nullptr);
704   auto *ImplFunction = ImplModule->getFunction("foo");
705   EXPECT_TRUE(ImplFunction != nullptr);
706   auto *DeclFunction = ImplModule->getFunction("bar");
707   EXPECT_TRUE(DeclFunction != nullptr);
708 
709   ValueToValueMapTy VMap;
710   SmallVector<ReturnInst *, 8> Returns;
711   ClonedCodeInfo CCI;
712   CloneFunctionInto(ImplFunction, DeclFunction, VMap,
713                     CloneFunctionChangeType::GlobalChanges, Returns, "", &CCI);
714 
715   EXPECT_FALSE(verifyModule(*ImplModule, &errs()));
716   EXPECT_FALSE(CCI.ContainsCalls);
717   EXPECT_FALSE(CCI.ContainsDynamicAllocas);
718 }
719 
720 TEST(CloneFunction, CloneFunctionWithInalloca) {
721   StringRef ImplAssembly = R"(
722     declare void @a(i32* inalloca(i32))
723     define void @foo() {
724       %a = alloca inalloca i32
725       call void @a(i32* inalloca(i32) %a)
726       ret void
727     }
728     declare void @bar()
729   )";
730 
731   LLVMContext Context;
732   SMDiagnostic Error;
733 
734   auto ImplModule = parseAssemblyString(ImplAssembly, Error, Context);
735   EXPECT_TRUE(ImplModule != nullptr);
736   auto *ImplFunction = ImplModule->getFunction("foo");
737   EXPECT_TRUE(ImplFunction != nullptr);
738   auto *DeclFunction = ImplModule->getFunction("bar");
739   EXPECT_TRUE(DeclFunction != nullptr);
740 
741   ValueToValueMapTy VMap;
742   SmallVector<ReturnInst *, 8> Returns;
743   ClonedCodeInfo CCI;
744   CloneFunctionInto(DeclFunction, ImplFunction, VMap,
745                     CloneFunctionChangeType::GlobalChanges, Returns, "", &CCI);
746 
747   EXPECT_FALSE(verifyModule(*ImplModule, &errs()));
748   EXPECT_TRUE(CCI.ContainsCalls);
749   EXPECT_TRUE(CCI.ContainsDynamicAllocas);
750 }
751 
752 TEST(CloneFunction, CloneFunctionWithSubprograms) {
753   // Tests that the debug info is duplicated correctly when a DISubprogram
754   // happens to be one of the operands of the DISubprogram that is being cloned.
755   // In general, operands of "test" that are distinct should be duplicated,
756   // but in this case "my_operator" should not be duplicated. If it is
757   // duplicated, the metadata in the llvm.dbg.declare could end up with
758   // different duplicates.
759   StringRef ImplAssembly = R"(
760     declare void @llvm.dbg.declare(metadata, metadata, metadata)
761 
762     define void @test() !dbg !5 {
763       call void @llvm.dbg.declare(metadata i8* undef, metadata !4, metadata !DIExpression()), !dbg !6
764       ret void
765     }
766 
767     declare void @cloned()
768 
769     !llvm.dbg.cu = !{!0}
770     !llvm.module.flags = !{!2}
771     !0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1)
772     !1 = !DIFile(filename: "test.cpp",  directory: "")
773     !2 = !{i32 1, !"Debug Info Version", i32 3}
774     !3 = distinct !DISubprogram(name: "my_operator", scope: !1, unit: !0, retainedNodes: !{!4})
775     !4 = !DILocalVariable(name: "awaitables", scope: !3)
776     !5 = distinct !DISubprogram(name: "test", scope: !3, unit: !0)
777     !6 = !DILocation(line: 55, column: 15, scope: !3, inlinedAt: !7)
778     !7 = distinct !DILocation(line: 73, column: 14, scope: !5)
779   )";
780 
781   LLVMContext Context;
782   SMDiagnostic Error;
783 
784   auto ImplModule = parseAssemblyString(ImplAssembly, Error, Context);
785   EXPECT_TRUE(ImplModule != nullptr);
786   auto *OldFunc = ImplModule->getFunction("test");
787   EXPECT_TRUE(OldFunc != nullptr);
788   auto *NewFunc = ImplModule->getFunction("cloned");
789   EXPECT_TRUE(NewFunc != nullptr);
790 
791   ValueToValueMapTy VMap;
792   SmallVector<ReturnInst *, 8> Returns;
793   ClonedCodeInfo CCI;
794   CloneFunctionInto(NewFunc, OldFunc, VMap,
795                     CloneFunctionChangeType::GlobalChanges, Returns, "", &CCI);
796 
797   // This fails if the scopes in the llvm.dbg.declare variable and location
798   // aren't the same.
799   EXPECT_FALSE(verifyModule(*ImplModule, &errs()));
800 }
801 
802 TEST(CloneFunction, CloneFunctionToDifferentModule) {
803   StringRef ImplAssembly = R"(
804     define void @foo() {
805       ret void, !dbg !5
806     }
807 
808     !llvm.module.flags = !{!0}
809     !llvm.dbg.cu = !{!2, !6}
810     !0 = !{i32 1, !"Debug Info Version", i32 3}
811     !1 = distinct !DISubprogram(unit: !2)
812     !2 = distinct !DICompileUnit(language: DW_LANG_C99, file: !3)
813     !3 = !DIFile(filename: "foo.c", directory: "/tmp")
814     !4 = distinct !DISubprogram(unit: !2)
815     !5 = !DILocation(line: 4, scope: !1)
816     !6 = distinct !DICompileUnit(language: DW_LANG_C99, file: !3)
817   )";
818   StringRef DeclAssembly = R"(
819     declare void @foo()
820   )";
821 
822   LLVMContext Context;
823   SMDiagnostic Error;
824 
825   auto ImplModule = parseAssemblyString(ImplAssembly, Error, Context);
826   EXPECT_TRUE(ImplModule != nullptr);
827   // DICompileUnits: !2, !6. Only !2 is reachable from @foo().
828   EXPECT_TRUE(GetDICompileUnitCount(*ImplModule) == 2);
829   auto* ImplFunction = ImplModule->getFunction("foo");
830   EXPECT_TRUE(ImplFunction != nullptr);
831 
832   auto DeclModule = parseAssemblyString(DeclAssembly, Error, Context);
833   EXPECT_TRUE(DeclModule != nullptr);
834   // No DICompileUnits defined here.
835   EXPECT_TRUE(GetDICompileUnitCount(*DeclModule) == 0);
836   auto* DeclFunction = DeclModule->getFunction("foo");
837   EXPECT_TRUE(DeclFunction != nullptr);
838 
839   ValueToValueMapTy VMap;
840   VMap[ImplFunction] = DeclFunction;
841   // No args to map
842   SmallVector<ReturnInst*, 8> Returns;
843   CloneFunctionInto(DeclFunction, ImplFunction, VMap,
844                     CloneFunctionChangeType::DifferentModule, Returns);
845 
846   EXPECT_FALSE(verifyModule(*ImplModule, &errs()));
847   EXPECT_FALSE(verifyModule(*DeclModule, &errs()));
848   // DICompileUnit !2 shall be cloned into DeclModule.
849   EXPECT_TRUE(GetDICompileUnitCount(*DeclModule) == 1);
850   EXPECT_FALSE(haveCompileUnitsInCommon(*ImplModule, *DeclModule));
851 }
852 
853 class CloneModule : public ::testing::Test {
854 protected:
855   void SetUp() override {
856     SetupModule();
857     CreateOldModule();
858     CreateNewModule();
859   }
860 
861   void SetupModule() { OldM = new Module("", C); }
862 
863   void CreateOldModule() {
864     auto *CD = OldM->getOrInsertComdat("comdat");
865     CD->setSelectionKind(Comdat::ExactMatch);
866 
867     auto GV = new GlobalVariable(
868         *OldM, Type::getInt32Ty(C), false, GlobalValue::ExternalLinkage,
869         ConstantInt::get(Type::getInt32Ty(C), 1), "gv");
870     GV->addMetadata(LLVMContext::MD_type, *MDNode::get(C, {}));
871     GV->setComdat(CD);
872 
873     {
874       // Add an empty compile unit first that isn't otherwise referenced, to
875       // confirm that compile units get cloned in the correct order.
876       DIBuilder EmptyBuilder(*OldM);
877       auto *File = EmptyBuilder.createFile("empty.c", "/file/dir/");
878       (void)EmptyBuilder.createCompileUnit(dwarf::DW_LANG_C99, File,
879                                            "EmptyUnit", false, "", 0);
880       EmptyBuilder.finalize();
881     }
882 
883     DIBuilder DBuilder(*OldM);
884     IRBuilder<> IBuilder(C);
885 
886     auto *FuncType = FunctionType::get(Type::getVoidTy(C), false);
887     auto *PersFn = Function::Create(FuncType, GlobalValue::ExternalLinkage,
888                                     "persfn", OldM);
889     auto *F =
890         Function::Create(FuncType, GlobalValue::PrivateLinkage, "f", OldM);
891     F->setPersonalityFn(PersFn);
892     F->setComdat(CD);
893 
894     // Create debug info
895     auto *File = DBuilder.createFile("filename.c", "/file/dir/");
896     DITypeRefArray ParamTypes = DBuilder.getOrCreateTypeArray(None);
897     DISubroutineType *DFuncType = DBuilder.createSubroutineType(ParamTypes);
898     auto *CU = DBuilder.createCompileUnit(dwarf::DW_LANG_C99,
899                                           DBuilder.createFile("filename.c",
900                                                               "/file/dir"),
901                                           "CloneModule", false, "", 0);
902     // Function DI
903     auto *Subprogram = DBuilder.createFunction(
904         CU, "f", "f", File, 4, DFuncType, 3, DINode::FlagZero,
905         DISubprogram::SPFlagLocalToUnit | DISubprogram::SPFlagDefinition);
906     F->setSubprogram(Subprogram);
907 
908     // Create and assign DIGlobalVariableExpression to gv
909     auto GVExpression = DBuilder.createGlobalVariableExpression(
910         Subprogram, "gv", "gv", File, 1, DBuilder.createNullPtrType(), false);
911     GV->addDebugInfo(GVExpression);
912 
913     // DIGlobalVariableExpression not attached to any global variable
914     auto Expr = DBuilder.createExpression(
915         ArrayRef<uint64_t>{dwarf::DW_OP_constu, 42U, dwarf::DW_OP_stack_value});
916 
917     DBuilder.createGlobalVariableExpression(
918         Subprogram, "unattached", "unattached", File, 1,
919         DBuilder.createNullPtrType(), false, true, Expr);
920 
921     auto *Entry = BasicBlock::Create(C, "", F);
922     IBuilder.SetInsertPoint(Entry);
923     IBuilder.CreateRetVoid();
924 
925     auto *G =
926         Function::Create(FuncType, GlobalValue::ExternalLinkage, "g", OldM);
927     G->addMetadata(LLVMContext::MD_type, *MDNode::get(C, {}));
928 
929     // Finalize the debug info
930     DBuilder.finalize();
931   }
932 
933   void CreateNewModule() { NewM = llvm::CloneModule(*OldM).release(); }
934 
935   LLVMContext C;
936   Module *OldM;
937   Module *NewM;
938 };
939 
940 TEST_F(CloneModule, Verify) {
941   // Confirm the old module is (still) valid.
942   EXPECT_FALSE(verifyModule(*OldM, &errs()));
943 
944   // Check the new module.
945   EXPECT_FALSE(verifyModule(*NewM, &errs()));
946 }
947 
948 TEST_F(CloneModule, OldModuleUnchanged) {
949   DebugInfoFinder Finder;
950   Finder.processModule(*OldM);
951   EXPECT_EQ(1U, Finder.subprogram_count());
952 }
953 
954 TEST_F(CloneModule, Subprogram) {
955   Function *NewF = NewM->getFunction("f");
956   DISubprogram *SP = NewF->getSubprogram();
957   EXPECT_TRUE(SP != nullptr);
958   EXPECT_EQ(SP->getName(), "f");
959   EXPECT_EQ(SP->getFile()->getFilename(), "filename.c");
960   EXPECT_EQ(SP->getLine(), (unsigned)4);
961 }
962 
963 TEST_F(CloneModule, FunctionDeclarationMetadata) {
964   Function *NewF = NewM->getFunction("g");
965   EXPECT_NE(nullptr, NewF->getMetadata(LLVMContext::MD_type));
966 }
967 
968 TEST_F(CloneModule, GlobalMetadata) {
969   GlobalVariable *NewGV = NewM->getGlobalVariable("gv");
970   EXPECT_NE(nullptr, NewGV->getMetadata(LLVMContext::MD_type));
971 }
972 
973 TEST_F(CloneModule, GlobalDebugInfo) {
974   GlobalVariable *NewGV = NewM->getGlobalVariable("gv");
975   EXPECT_TRUE(NewGV != nullptr);
976 
977   // Find debug info expression assigned to global
978   SmallVector<DIGlobalVariableExpression *, 1> GVs;
979   NewGV->getDebugInfo(GVs);
980   EXPECT_EQ(GVs.size(), 1U);
981 
982   DIGlobalVariableExpression *GVExpr = GVs[0];
983   DIGlobalVariable *GV = GVExpr->getVariable();
984   EXPECT_TRUE(GV != nullptr);
985 
986   EXPECT_EQ(GV->getName(), "gv");
987   EXPECT_EQ(GV->getLine(), 1U);
988 
989   // Assert that the scope of the debug info attached to
990   // global variable matches the cloned function.
991   DISubprogram *SP = NewM->getFunction("f")->getSubprogram();
992   EXPECT_TRUE(SP != nullptr);
993   EXPECT_EQ(GV->getScope(), SP);
994 }
995 
996 TEST_F(CloneModule, CompileUnit) {
997   // Find DICompileUnit listed in llvm.dbg.cu
998   auto *NMD = NewM->getNamedMetadata("llvm.dbg.cu");
999   EXPECT_TRUE(NMD != nullptr);
1000   EXPECT_EQ(NMD->getNumOperands(), 2U);
1001   EXPECT_FALSE(haveCompileUnitsInCommon(*OldM, *NewM));
1002 
1003   // Check that the empty CU is first, even though it's not referenced except
1004   // from named metadata.
1005   DICompileUnit *EmptyCU = dyn_cast<llvm::DICompileUnit>(NMD->getOperand(0));
1006   EXPECT_TRUE(EmptyCU != nullptr);
1007   EXPECT_EQ("EmptyUnit", EmptyCU->getProducer());
1008 
1009   // Get the interesting CU.
1010   DICompileUnit *CU = dyn_cast<llvm::DICompileUnit>(NMD->getOperand(1));
1011   EXPECT_TRUE(CU != nullptr);
1012   EXPECT_EQ("CloneModule", CU->getProducer());
1013 
1014   // Assert this CU is consistent with the cloned function debug info
1015   DISubprogram *SP = NewM->getFunction("f")->getSubprogram();
1016   EXPECT_TRUE(SP != nullptr);
1017   EXPECT_EQ(SP->getUnit(), CU);
1018 
1019   // Check globals listed in CU have the correct scope
1020   DIGlobalVariableExpressionArray GlobalArray = CU->getGlobalVariables();
1021   EXPECT_EQ(GlobalArray.size(), 2U);
1022   for (DIGlobalVariableExpression *GVExpr : GlobalArray) {
1023     DIGlobalVariable *GV = GVExpr->getVariable();
1024     EXPECT_EQ(GV->getScope(), SP);
1025   }
1026 }
1027 
1028 TEST_F(CloneModule, Comdat) {
1029   GlobalVariable *NewGV = NewM->getGlobalVariable("gv");
1030   auto *CD = NewGV->getComdat();
1031   ASSERT_NE(nullptr, CD);
1032   EXPECT_EQ("comdat", CD->getName());
1033   EXPECT_EQ(Comdat::ExactMatch, CD->getSelectionKind());
1034 
1035   Function *NewF = NewM->getFunction("f");
1036   EXPECT_EQ(CD, NewF->getComdat());
1037 }
1038 }
1039