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 = DebugLoc::get(3, 2, Subprogram);
490     IBuilder.SetCurrentDebugLocation(Loc);
491     AllocaInst* Alloca = IBuilder.CreateAlloca(IntegerType::getInt32Ty(C));
492     IBuilder.SetCurrentDebugLocation(DebugLoc::get(4, 2, Subprogram));
493     Value* AllocaContent = IBuilder.getInt32(1);
494     Instruction* Store = IBuilder.CreateStore(AllocaContent, Alloca);
495     IBuilder.SetCurrentDebugLocation(DebugLoc::get(5, 2, Subprogram));
496 
497     // Create a local variable around the alloca
498     auto *IntType = DBuilder.createBasicType("int", 32, dwarf::DW_ATE_signed);
499     auto *E = DBuilder.createExpression();
500     auto *Variable =
501         DBuilder.createAutoVariable(Subprogram, "x", File, 5, IntType, true);
502     auto *DL = DILocation::get(Subprogram->getContext(), 5, 0, Subprogram);
503     DBuilder.insertDeclare(Alloca, Variable, E, DL, Store);
504     DBuilder.insertDbgValueIntrinsic(AllocaContent, Variable, E, DL, Entry);
505     // Also create an inlined variable.
506     // Create a distinct struct type that we should not duplicate during
507     // cloning).
508     auto *StructType = DICompositeType::getDistinct(
509         C, dwarf::DW_TAG_structure_type, "some_struct", nullptr, 0, nullptr,
510         nullptr, 32, 32, 0, DINode::FlagZero, nullptr, 0, nullptr, nullptr);
511     auto *InlinedSP = DBuilder.createFunction(
512         CU, "inlined", "inlined", File, 8, FuncType, 9, DINode::FlagZero,
513         DISubprogram::SPFlagLocalToUnit | DISubprogram::SPFlagDefinition);
514     auto *InlinedVar =
515         DBuilder.createAutoVariable(InlinedSP, "inlined", File, 5, StructType, true);
516     auto *Scope = DBuilder.createLexicalBlock(
517         DBuilder.createLexicalBlockFile(InlinedSP, File), File, 1, 1);
518     auto InlinedDL =
519         DebugLoc::get(9, 4, Scope, DebugLoc::get(5, 2, Subprogram));
520     IBuilder.SetCurrentDebugLocation(InlinedDL);
521     DBuilder.insertDeclare(Alloca, InlinedVar, E, InlinedDL, Store);
522     IBuilder.CreateStore(IBuilder.getInt32(2), Alloca);
523     // Finalize the debug info.
524     DBuilder.finalize();
525     IBuilder.CreateRetVoid();
526 
527     // Create another, empty, compile unit.
528     DIBuilder DBuilder2(*M);
529     DBuilder2.createCompileUnit(dwarf::DW_LANG_C99,
530                                 DBuilder.createFile("extra.c", "/file/dir"),
531                                 "CloneFunc", false, "", 0);
532     DBuilder2.finalize();
533   }
534 
535   void CreateNewFunc() {
536     ValueToValueMapTy VMap;
537     NewFunc = CloneFunction(OldFunc, VMap, nullptr);
538   }
539 
540   void SetupFinder() {
541     Finder = new DebugInfoFinder();
542     Finder->processModule(*M);
543   }
544 
545   LLVMContext C;
546   Function* OldFunc;
547   Function* NewFunc;
548   Module* M;
549   DebugInfoFinder* Finder;
550 };
551 
552 // Test that a new, distinct function was created.
553 TEST_F(CloneFunc, NewFunctionCreated) {
554   EXPECT_NE(OldFunc, NewFunc);
555 }
556 
557 // Test that a new subprogram entry was added and is pointing to the new
558 // function, while the original subprogram still points to the old one.
559 TEST_F(CloneFunc, Subprogram) {
560   EXPECT_FALSE(verifyModule(*M, &errs()));
561   EXPECT_EQ(3U, Finder->subprogram_count());
562   EXPECT_NE(NewFunc->getSubprogram(), OldFunc->getSubprogram());
563 }
564 
565 // Test that instructions in the old function still belong to it in the
566 // metadata, while instruction in the new function belong to the new one.
567 TEST_F(CloneFunc, InstructionOwnership) {
568   EXPECT_FALSE(verifyModule(*M));
569 
570   inst_iterator OldIter = inst_begin(OldFunc);
571   inst_iterator OldEnd = inst_end(OldFunc);
572   inst_iterator NewIter = inst_begin(NewFunc);
573   inst_iterator NewEnd = inst_end(NewFunc);
574   while (OldIter != OldEnd && NewIter != NewEnd) {
575     Instruction& OldI = *OldIter;
576     Instruction& NewI = *NewIter;
577     EXPECT_NE(&OldI, &NewI);
578 
579     EXPECT_EQ(OldI.hasMetadata(), NewI.hasMetadata());
580     if (OldI.hasMetadata()) {
581       const DebugLoc& OldDL = OldI.getDebugLoc();
582       const DebugLoc& NewDL = NewI.getDebugLoc();
583 
584       // Verify that the debug location data is the same
585       EXPECT_EQ(OldDL.getLine(), NewDL.getLine());
586       EXPECT_EQ(OldDL.getCol(), NewDL.getCol());
587 
588       // But that they belong to different functions
589       auto *OldSubprogram = cast<DISubprogram>(OldDL.getInlinedAtScope());
590       auto *NewSubprogram = cast<DISubprogram>(NewDL.getInlinedAtScope());
591       EXPECT_EQ(OldFunc->getSubprogram(), OldSubprogram);
592       EXPECT_EQ(NewFunc->getSubprogram(), NewSubprogram);
593     }
594 
595     ++OldIter;
596     ++NewIter;
597   }
598   EXPECT_EQ(OldEnd, OldIter);
599   EXPECT_EQ(NewEnd, NewIter);
600 }
601 
602 // Test that the arguments for debug intrinsics in the new function were
603 // properly cloned
604 TEST_F(CloneFunc, DebugIntrinsics) {
605   EXPECT_FALSE(verifyModule(*M));
606 
607   inst_iterator OldIter = inst_begin(OldFunc);
608   inst_iterator OldEnd = inst_end(OldFunc);
609   inst_iterator NewIter = inst_begin(NewFunc);
610   inst_iterator NewEnd = inst_end(NewFunc);
611   while (OldIter != OldEnd && NewIter != NewEnd) {
612     Instruction& OldI = *OldIter;
613     Instruction& NewI = *NewIter;
614     if (DbgDeclareInst* OldIntrin = dyn_cast<DbgDeclareInst>(&OldI)) {
615       DbgDeclareInst* NewIntrin = dyn_cast<DbgDeclareInst>(&NewI);
616       EXPECT_TRUE(NewIntrin);
617 
618       // Old address must belong to the old function
619       EXPECT_EQ(OldFunc, cast<AllocaInst>(OldIntrin->getAddress())->
620                          getParent()->getParent());
621       // New address must belong to the new function
622       EXPECT_EQ(NewFunc, cast<AllocaInst>(NewIntrin->getAddress())->
623                          getParent()->getParent());
624 
625       if (OldIntrin->getDebugLoc()->getInlinedAt()) {
626         // Inlined variable should refer to the same DILocalVariable as in the
627         // Old Function
628         EXPECT_EQ(OldIntrin->getVariable(), NewIntrin->getVariable());
629       } else {
630         // Old variable must belong to the old function.
631         EXPECT_EQ(OldFunc->getSubprogram(),
632                   cast<DISubprogram>(OldIntrin->getVariable()->getScope()));
633         // New variable must belong to the new function.
634         EXPECT_EQ(NewFunc->getSubprogram(),
635                   cast<DISubprogram>(NewIntrin->getVariable()->getScope()));
636       }
637     } else if (DbgValueInst* OldIntrin = dyn_cast<DbgValueInst>(&OldI)) {
638       DbgValueInst* NewIntrin = dyn_cast<DbgValueInst>(&NewI);
639       EXPECT_TRUE(NewIntrin);
640 
641       if (!OldIntrin->getDebugLoc()->getInlinedAt()) {
642         // Old variable must belong to the old function.
643         EXPECT_EQ(OldFunc->getSubprogram(),
644                   cast<DISubprogram>(OldIntrin->getVariable()->getScope()));
645         // New variable must belong to the new function.
646         EXPECT_EQ(NewFunc->getSubprogram(),
647                   cast<DISubprogram>(NewIntrin->getVariable()->getScope()));
648       }
649     }
650 
651     ++OldIter;
652     ++NewIter;
653   }
654 }
655 
656 static int GetDICompileUnitCount(const Module& M) {
657   if (const auto* LLVM_DBG_CU = M.getNamedMetadata("llvm.dbg.cu")) {
658     return LLVM_DBG_CU->getNumOperands();
659   }
660   return 0;
661 }
662 
663 TEST(CloneFunction, CloneEmptyFunction) {
664   StringRef ImplAssembly = R"(
665     define void @foo() {
666       ret void
667     }
668     declare void @bar()
669   )";
670 
671   LLVMContext Context;
672   SMDiagnostic Error;
673 
674   auto ImplModule = parseAssemblyString(ImplAssembly, Error, Context);
675   EXPECT_TRUE(ImplModule != nullptr);
676   auto *ImplFunction = ImplModule->getFunction("foo");
677   EXPECT_TRUE(ImplFunction != nullptr);
678   auto *DeclFunction = ImplModule->getFunction("bar");
679   EXPECT_TRUE(DeclFunction != nullptr);
680 
681   ValueToValueMapTy VMap;
682   SmallVector<ReturnInst *, 8> Returns;
683   ClonedCodeInfo CCI;
684   CloneFunctionInto(DeclFunction, ImplFunction, VMap, true, Returns, "", &CCI);
685 
686   EXPECT_FALSE(verifyModule(*ImplModule, &errs()));
687   EXPECT_FALSE(CCI.ContainsCalls);
688   EXPECT_FALSE(CCI.ContainsDynamicAllocas);
689 }
690 
691 TEST(CloneFunction, CloneFunctionWithInalloca) {
692   StringRef ImplAssembly = R"(
693     declare void @a(i32* inalloca)
694     define void @foo() {
695       %a = alloca inalloca i32
696       call void @a(i32* inalloca %a)
697       ret void
698     }
699     declare void @bar()
700   )";
701 
702   LLVMContext Context;
703   SMDiagnostic Error;
704 
705   auto ImplModule = parseAssemblyString(ImplAssembly, Error, Context);
706   EXPECT_TRUE(ImplModule != nullptr);
707   auto *ImplFunction = ImplModule->getFunction("foo");
708   EXPECT_TRUE(ImplFunction != nullptr);
709   auto *DeclFunction = ImplModule->getFunction("bar");
710   EXPECT_TRUE(DeclFunction != nullptr);
711 
712   ValueToValueMapTy VMap;
713   SmallVector<ReturnInst *, 8> Returns;
714   ClonedCodeInfo CCI;
715   CloneFunctionInto(DeclFunction, ImplFunction, VMap, true, Returns, "", &CCI);
716 
717   EXPECT_FALSE(verifyModule(*ImplModule, &errs()));
718   EXPECT_TRUE(CCI.ContainsCalls);
719   EXPECT_TRUE(CCI.ContainsDynamicAllocas);
720 }
721 
722 TEST(CloneFunction, CloneFunctionToDifferentModule) {
723   StringRef ImplAssembly = R"(
724     define void @foo() {
725       ret void, !dbg !5
726     }
727 
728     !llvm.module.flags = !{!0}
729     !llvm.dbg.cu = !{!2, !6}
730     !0 = !{i32 1, !"Debug Info Version", i32 3}
731     !1 = distinct !DISubprogram(unit: !2)
732     !2 = distinct !DICompileUnit(language: DW_LANG_C99, file: !3)
733     !3 = !DIFile(filename: "foo.c", directory: "/tmp")
734     !4 = distinct !DISubprogram(unit: !2)
735     !5 = !DILocation(line: 4, scope: !1)
736     !6 = distinct !DICompileUnit(language: DW_LANG_C99, file: !3)
737   )";
738   StringRef DeclAssembly = R"(
739     declare void @foo()
740   )";
741 
742   LLVMContext Context;
743   SMDiagnostic Error;
744 
745   auto ImplModule = parseAssemblyString(ImplAssembly, Error, Context);
746   EXPECT_TRUE(ImplModule != nullptr);
747   // DICompileUnits: !2, !6. Only !2 is reachable from @foo().
748   EXPECT_TRUE(GetDICompileUnitCount(*ImplModule) == 2);
749   auto* ImplFunction = ImplModule->getFunction("foo");
750   EXPECT_TRUE(ImplFunction != nullptr);
751 
752   auto DeclModule = parseAssemblyString(DeclAssembly, Error, Context);
753   EXPECT_TRUE(DeclModule != nullptr);
754   // No DICompileUnits defined here.
755   EXPECT_TRUE(GetDICompileUnitCount(*DeclModule) == 0);
756   auto* DeclFunction = DeclModule->getFunction("foo");
757   EXPECT_TRUE(DeclFunction != nullptr);
758 
759   ValueToValueMapTy VMap;
760   VMap[ImplFunction] = DeclFunction;
761   // No args to map
762   SmallVector<ReturnInst*, 8> Returns;
763   CloneFunctionInto(DeclFunction, ImplFunction, VMap, true, Returns);
764 
765   EXPECT_FALSE(verifyModule(*ImplModule, &errs()));
766   EXPECT_FALSE(verifyModule(*DeclModule, &errs()));
767   // DICompileUnit !2 shall be inserted into DeclModule.
768   EXPECT_TRUE(GetDICompileUnitCount(*DeclModule) == 1);
769 }
770 
771 class CloneModule : public ::testing::Test {
772 protected:
773   void SetUp() override {
774     SetupModule();
775     CreateOldModule();
776     CreateNewModule();
777   }
778 
779   void SetupModule() { OldM = new Module("", C); }
780 
781   void CreateOldModule() {
782     auto *CD = OldM->getOrInsertComdat("comdat");
783     CD->setSelectionKind(Comdat::ExactMatch);
784 
785     auto GV = new GlobalVariable(
786         *OldM, Type::getInt32Ty(C), false, GlobalValue::ExternalLinkage,
787         ConstantInt::get(Type::getInt32Ty(C), 1), "gv");
788     GV->addMetadata(LLVMContext::MD_type, *MDNode::get(C, {}));
789     GV->setComdat(CD);
790 
791     DIBuilder DBuilder(*OldM);
792     IRBuilder<> IBuilder(C);
793 
794     auto *FuncType = FunctionType::get(Type::getVoidTy(C), false);
795     auto *PersFn = Function::Create(FuncType, GlobalValue::ExternalLinkage,
796                                     "persfn", OldM);
797     auto *F =
798         Function::Create(FuncType, GlobalValue::PrivateLinkage, "f", OldM);
799     F->setPersonalityFn(PersFn);
800     F->setComdat(CD);
801 
802     // Create debug info
803     auto *File = DBuilder.createFile("filename.c", "/file/dir/");
804     DITypeRefArray ParamTypes = DBuilder.getOrCreateTypeArray(None);
805     DISubroutineType *DFuncType = DBuilder.createSubroutineType(ParamTypes);
806     auto *CU = DBuilder.createCompileUnit(dwarf::DW_LANG_C99,
807                                           DBuilder.createFile("filename.c",
808                                                               "/file/dir"),
809                                           "CloneModule", false, "", 0);
810     // Function DI
811     auto *Subprogram = DBuilder.createFunction(
812         CU, "f", "f", File, 4, DFuncType, 3, DINode::FlagZero,
813         DISubprogram::SPFlagLocalToUnit | DISubprogram::SPFlagDefinition);
814     F->setSubprogram(Subprogram);
815 
816     // Create and assign DIGlobalVariableExpression to gv
817     auto GVExpression = DBuilder.createGlobalVariableExpression(
818         Subprogram, "gv", "gv", File, 1, DBuilder.createNullPtrType(), false);
819     GV->addDebugInfo(GVExpression);
820 
821     // DIGlobalVariableExpression not attached to any global variable
822     auto Expr = DBuilder.createExpression(
823         ArrayRef<uint64_t>{dwarf::DW_OP_constu, 42U, dwarf::DW_OP_stack_value});
824 
825     DBuilder.createGlobalVariableExpression(
826         Subprogram, "unattached", "unattached", File, 1,
827         DBuilder.createNullPtrType(), false, true, Expr);
828 
829     auto *Entry = BasicBlock::Create(C, "", F);
830     IBuilder.SetInsertPoint(Entry);
831     IBuilder.CreateRetVoid();
832 
833     // Finalize the debug info
834     DBuilder.finalize();
835   }
836 
837   void CreateNewModule() { NewM = llvm::CloneModule(*OldM).release(); }
838 
839   LLVMContext C;
840   Module *OldM;
841   Module *NewM;
842 };
843 
844 TEST_F(CloneModule, Verify) {
845   EXPECT_FALSE(verifyModule(*NewM));
846 }
847 
848 TEST_F(CloneModule, OldModuleUnchanged) {
849   DebugInfoFinder Finder;
850   Finder.processModule(*OldM);
851   EXPECT_EQ(1U, Finder.subprogram_count());
852 }
853 
854 TEST_F(CloneModule, Subprogram) {
855   Function *NewF = NewM->getFunction("f");
856   DISubprogram *SP = NewF->getSubprogram();
857   EXPECT_TRUE(SP != nullptr);
858   EXPECT_EQ(SP->getName(), "f");
859   EXPECT_EQ(SP->getFile()->getFilename(), "filename.c");
860   EXPECT_EQ(SP->getLine(), (unsigned)4);
861 }
862 
863 TEST_F(CloneModule, GlobalMetadata) {
864   GlobalVariable *NewGV = NewM->getGlobalVariable("gv");
865   EXPECT_NE(nullptr, NewGV->getMetadata(LLVMContext::MD_type));
866 }
867 
868 TEST_F(CloneModule, GlobalDebugInfo) {
869   GlobalVariable *NewGV = NewM->getGlobalVariable("gv");
870   EXPECT_TRUE(NewGV != nullptr);
871 
872   // Find debug info expression assigned to global
873   SmallVector<DIGlobalVariableExpression *, 1> GVs;
874   NewGV->getDebugInfo(GVs);
875   EXPECT_EQ(GVs.size(), 1U);
876 
877   DIGlobalVariableExpression *GVExpr = GVs[0];
878   DIGlobalVariable *GV = GVExpr->getVariable();
879   EXPECT_TRUE(GV != nullptr);
880 
881   EXPECT_EQ(GV->getName(), "gv");
882   EXPECT_EQ(GV->getLine(), 1U);
883 
884   // Assert that the scope of the debug info attached to
885   // global variable matches the cloned function.
886   DISubprogram *SP = NewM->getFunction("f")->getSubprogram();
887   EXPECT_TRUE(SP != nullptr);
888   EXPECT_EQ(GV->getScope(), SP);
889 }
890 
891 TEST_F(CloneModule, CompileUnit) {
892   // Find DICompileUnit listed in llvm.dbg.cu
893   auto *NMD = NewM->getNamedMetadata("llvm.dbg.cu");
894   EXPECT_TRUE(NMD != nullptr);
895   EXPECT_EQ(NMD->getNumOperands(), 1U);
896 
897   DICompileUnit *CU = dyn_cast<llvm::DICompileUnit>(NMD->getOperand(0));
898   EXPECT_TRUE(CU != nullptr);
899 
900   // Assert this CU is consistent with the cloned function debug info
901   DISubprogram *SP = NewM->getFunction("f")->getSubprogram();
902   EXPECT_TRUE(SP != nullptr);
903   EXPECT_EQ(SP->getUnit(), CU);
904 
905   // Check globals listed in CU have the correct scope
906   DIGlobalVariableExpressionArray GlobalArray = CU->getGlobalVariables();
907   EXPECT_EQ(GlobalArray.size(), 2U);
908   for (DIGlobalVariableExpression *GVExpr : GlobalArray) {
909     DIGlobalVariable *GV = GVExpr->getVariable();
910     EXPECT_EQ(GV->getScope(), SP);
911   }
912 }
913 
914 TEST_F(CloneModule, Comdat) {
915   GlobalVariable *NewGV = NewM->getGlobalVariable("gv");
916   auto *CD = NewGV->getComdat();
917   ASSERT_NE(nullptr, CD);
918   EXPECT_EQ("comdat", CD->getName());
919   EXPECT_EQ(Comdat::ExactMatch, CD->getSelectionKind());
920 
921   Function *NewF = NewM->getFunction("f");
922   EXPECT_EQ(CD, NewF->getComdat());
923 }
924 }
925