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