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