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