llvm/unittests/Transforms/Utils/LocalTest.cpp

   1 //===- Local.cpp - Unit tests for Local -----------------------------------===//
   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/Local.h"
  10 #include "llvm/Analysis/DomTreeUpdater.h"
  11 #include "llvm/Analysis/InstructionSimplify.h"
  12 #include "llvm/Analysis/PostDominators.h"
  13 #include "llvm/Analysis/TargetTransformInfo.h"
  14 #include "llvm/AsmParser/Parser.h"
  15 #include "llvm/IR/BasicBlock.h"
  16 #include "llvm/IR/DIBuilder.h"
  17 #include "llvm/IR/DebugInfo.h"
  18 #include "llvm/IR/IRBuilder.h"
  19 #include "llvm/IR/Instructions.h"
  20 #include "llvm/IR/IntrinsicInst.h"
  21 #include "llvm/IR/LLVMContext.h"
  22 #include "llvm/IR/Verifier.h"
  23 #include "llvm/Support/SourceMgr.h"
  24 #include "gtest/gtest.h"
  25
  26 using namespace llvm;
  27
  28 TEST(Local, RecursivelyDeleteDeadPHINodes) {
  29   LLVMContext C;
  30
  31   IRBuilder<> builder(C);
  32
  33   // Make blocks
  34   BasicBlock *bb0 = BasicBlock::Create(C);
  35   BasicBlock *bb1 = BasicBlock::Create(C);
  36
  37   builder.SetInsertPoint(bb0);
  38   PHINode    *phi = builder.CreatePHI(Type::getInt32Ty(C), 2);
  39   BranchInst *br0 = builder.CreateCondBr(builder.getTrue(), bb0, bb1);
  40
  41   builder.SetInsertPoint(bb1);
  42   BranchInst *br1 = builder.CreateBr(bb0);
  43
  44   phi->addIncoming(phi, bb0);
  45   phi->addIncoming(phi, bb1);
  46
  47   // The PHI will be removed
  48   EXPECT_TRUE(RecursivelyDeleteDeadPHINode(phi));
  49
  50   // Make sure the blocks only contain the branches
  51   EXPECT_EQ(&bb0->front(), br0);
  52   EXPECT_EQ(&bb1->front(), br1);
  53
  54   builder.SetInsertPoint(bb0);
  55   phi = builder.CreatePHI(Type::getInt32Ty(C), 0);
  56
  57   EXPECT_TRUE(RecursivelyDeleteDeadPHINode(phi));
  58
  59   builder.SetInsertPoint(bb0);
  60   phi = builder.CreatePHI(Type::getInt32Ty(C), 0);
  61   builder.CreateAdd(phi, phi);
  62
  63   EXPECT_TRUE(RecursivelyDeleteDeadPHINode(phi));
  64
  65   bb0->dropAllReferences();
  66   bb1->dropAllReferences();
  67   delete bb0;
  68   delete bb1;
  69 }
  70
  71 TEST(Local, RemoveDuplicatePHINodes) {
  72   LLVMContext C;
  73   IRBuilder<> B(C);
  74
  75   std::unique_ptr<Function> F(
  76       Function::Create(FunctionType::get(B.getVoidTy(), false),
  77                        GlobalValue::ExternalLinkage, "F"));
  78   BasicBlock *Entry(BasicBlock::Create(C, "", F.get()));
  79   BasicBlock *BB(BasicBlock::Create(C, "", F.get()));
  80   BranchInst::Create(BB, Entry);
  81
  82   B.SetInsertPoint(BB);
  83
  84   AssertingVH<PHINode> P1 = B.CreatePHI(Type::getInt32Ty(C), 2);
  85   P1->addIncoming(B.getInt32(42), Entry);
  86
  87   PHINode *P2 = B.CreatePHI(Type::getInt32Ty(C), 2);
  88   P2->addIncoming(B.getInt32(42), Entry);
  89
  90   AssertingVH<PHINode> P3 = B.CreatePHI(Type::getInt32Ty(C), 2);
  91   P3->addIncoming(B.getInt32(42), Entry);
  92   P3->addIncoming(B.getInt32(23), BB);
  93
  94   PHINode *P4 = B.CreatePHI(Type::getInt32Ty(C), 2);
  95   P4->addIncoming(B.getInt32(42), Entry);
  96   P4->addIncoming(B.getInt32(23), BB);
  97
  98   P1->addIncoming(P3, BB);
  99   P2->addIncoming(P4, BB);
 100   BranchInst::Create(BB, BB);
 101
 102   // Verify that we can eliminate PHIs that become duplicates after chaning PHIs
 103   // downstream.
 104   EXPECT_TRUE(EliminateDuplicatePHINodes(BB));
 105   EXPECT_EQ(3U, BB->size());
 106 }
 107
 108 static std::unique_ptr<Module> parseIR(LLVMContext &C, const char *IR) {
 109   SMDiagnostic Err;
 110   std::unique_ptr<Module> Mod = parseAssemblyString(IR, Err, C);
 111   if (!Mod)
 112     Err.print("UtilsTests", errs());
 113   return Mod;
 114 }
 115
 116 TEST(Local, ReplaceDbgDeclare) {
 117   LLVMContext C;
 118
 119   // Original C source to get debug info for a local variable:
 120   // void f() { int x; }
 121   std::unique_ptr<Module> M = parseIR(C,
 122                                       R"(
 123       define void @f() !dbg !8 {
 124       entry:
 125         %x = alloca i32, align 4
 126         call void @llvm.dbg.declare(metadata i32* %x, metadata !11, metadata !DIExpression()), !dbg !13
 127         call void @llvm.dbg.declare(metadata i32* %x, metadata !11, metadata !DIExpression()), !dbg !13
 128         ret void, !dbg !14
 129       }
 130       declare void @llvm.dbg.declare(metadata, metadata, metadata)
 131       !llvm.dbg.cu = !{!0}
 132       !llvm.module.flags = !{!3, !4}
 133       !0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang version 6.0.0", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !2)
 134       !1 = !DIFile(filename: "t2.c", directory: "foo")
 135       !2 = !{}
 136       !3 = !{i32 2, !"Dwarf Version", i32 4}
 137       !4 = !{i32 2, !"Debug Info Version", i32 3}
 138       !8 = distinct !DISubprogram(name: "f", scope: !1, file: !1, line: 1, type: !9, isLocal: false, isDefinition: true, scopeLine: 1, isOptimized: false, unit: !0, retainedNodes: !2)
 139       !9 = !DISubroutineType(types: !10)
 140       !10 = !{null}
 141       !11 = !DILocalVariable(name: "x", scope: !8, file: !1, line: 2, type: !12)
 142       !12 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
 143       !13 = !DILocation(line: 2, column: 7, scope: !8)
 144       !14 = !DILocation(line: 3, column: 1, scope: !8)
 145       )");
 146   auto *GV = M->getNamedValue("f");
 147   ASSERT_TRUE(GV);
 148   auto *F = dyn_cast<Function>(GV);
 149   ASSERT_TRUE(F);
 150   Instruction *Inst = &F->front().front();
 151   auto *AI = dyn_cast<AllocaInst>(Inst);
 152   ASSERT_TRUE(AI);
 153   Inst = Inst->getNextNode()->getNextNode();
 154   ASSERT_TRUE(Inst);
 155   auto *DII = dyn_cast<DbgDeclareInst>(Inst);
 156   ASSERT_TRUE(DII);
 157   Value *NewBase = Constant::getNullValue(PointerType::getUnqual(C));
 158   DIBuilder DIB(*M);
 159   replaceDbgDeclare(AI, NewBase, DIB, DIExpression::ApplyOffset, 0);
 160
 161   // There should be exactly two dbg.declares.
 162   int Declares = 0;
 163   for (const Instruction &I : F->front())
 164     if (isa<DbgDeclareInst>(I))
 165       Declares++;
 166   EXPECT_EQ(2, Declares);
 167 }
 168
 169 /// Build the dominator tree for the function and run the Test.
 170 static void runWithDomTree(
 171     Module &M, StringRef FuncName,
 172     function_ref<void(Function &F, DominatorTree *DT)> Test) {
 173   auto *F = M.getFunction(FuncName);
 174   ASSERT_NE(F, nullptr) << "Could not find " << FuncName;
 175   // Compute the dominator tree for the function.
 176   DominatorTree DT(*F);
 177   Test(*F, &DT);
 178 }
 179
 180 TEST(Local, MergeBasicBlockIntoOnlyPred) {
 181   LLVMContext C;
 182   std::unique_ptr<Module> M;
 183   auto resetIR = [&]() {
 184     M = parseIR(C,
 185                 R"(
 186       define i32 @f(i8* %str) {
 187       entry:
 188         br label %bb2.i
 189       bb2.i:                                            ; preds = %bb4.i, %entry
 190         br i1 false, label %bb4.i, label %base2flt.exit204
 191       bb4.i:                                            ; preds = %bb2.i
 192         br i1 false, label %base2flt.exit204, label %bb2.i
 193       bb10.i196.bb7.i197_crit_edge:                     ; No predecessors!
 194         br label %bb7.i197
 195       bb7.i197:                                         ; preds = %bb10.i196.bb7.i197_crit_edge
 196         %.reg2mem.0 = phi i32 [ %.reg2mem.0, %bb10.i196.bb7.i197_crit_edge ]
 197         br i1 undef, label %base2flt.exit204, label %base2flt.exit204
 198       base2flt.exit204:                                 ; preds = %bb7.i197, %bb7.i197, %bb2.i, %bb4.i
 199         ret i32 0
 200       }
 201       )");
 202   };
 203
 204   auto resetIRReplaceEntry = [&]() {
 205     M = parseIR(C,
 206                 R"(
 207       define i32 @f() {
 208       entry:
 209         br label %bb2.i
 210       bb2.i:                                            ; preds = %entry
 211         ret i32 0
 212       }
 213       )");
 214   };
 215
 216   auto Test = [&](Function &F, DomTreeUpdater &DTU) {
 217     for (Function::iterator I = F.begin(), E = F.end(); I != E;) {
 218       BasicBlock *BB = &*I++;
 219       BasicBlock *SinglePred = BB->getSinglePredecessor();
 220       if (!SinglePred || SinglePred == BB || BB->hasAddressTaken())
 221         continue;
 222       BranchInst *Term = dyn_cast<BranchInst>(SinglePred->getTerminator());
 223       if (Term && !Term->isConditional())
 224         MergeBasicBlockIntoOnlyPred(BB, &DTU);
 225     }
 226     if (DTU.hasDomTree()) {
 227       EXPECT_TRUE(DTU.getDomTree().verify());
 228     }
 229     if (DTU.hasPostDomTree()) {
 230       EXPECT_TRUE(DTU.getPostDomTree().verify());
 231     }
 232   };
 233
 234   // Test MergeBasicBlockIntoOnlyPred working under Eager UpdateStrategy with
 235   // both DT and PDT.
 236   resetIR();
 237   runWithDomTree(*M, "f", [&](Function &F, DominatorTree *DT) {
 238     PostDominatorTree PDT = PostDominatorTree(F);
 239     DomTreeUpdater DTU(*DT, PDT, DomTreeUpdater::UpdateStrategy::Eager);
 240     Test(F, DTU);
 241   });
 242
 243   // Test MergeBasicBlockIntoOnlyPred working under Eager UpdateStrategy with
 244   // DT.
 245   resetIR();
 246   runWithDomTree(*M, "f", [&](Function &F, DominatorTree *DT) {
 247     DomTreeUpdater DTU(*DT, DomTreeUpdater::UpdateStrategy::Eager);
 248     Test(F, DTU);
 249   });
 250
 251   // Test MergeBasicBlockIntoOnlyPred working under Eager UpdateStrategy with
 252   // PDT.
 253   resetIR();
 254   runWithDomTree(*M, "f", [&](Function &F, DominatorTree *DT) {
 255     PostDominatorTree PDT = PostDominatorTree(F);
 256     DomTreeUpdater DTU(PDT, DomTreeUpdater::UpdateStrategy::Eager);
 257     Test(F, DTU);
 258   });
 259
 260   // Test MergeBasicBlockIntoOnlyPred working under Lazy UpdateStrategy with
 261   // both DT and PDT.
 262   resetIR();
 263   runWithDomTree(*M, "f", [&](Function &F, DominatorTree *DT) {
 264     PostDominatorTree PDT = PostDominatorTree(F);
 265     DomTreeUpdater DTU(*DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy);
 266     Test(F, DTU);
 267   });
 268
 269   // Test MergeBasicBlockIntoOnlyPred working under Lazy UpdateStrategy with
 270   // PDT.
 271   resetIR();
 272   runWithDomTree(*M, "f", [&](Function &F, DominatorTree *DT) {
 273     PostDominatorTree PDT = PostDominatorTree(F);
 274     DomTreeUpdater DTU(PDT, DomTreeUpdater::UpdateStrategy::Lazy);
 275     Test(F, DTU);
 276   });
 277
 278   // Test MergeBasicBlockIntoOnlyPred working under Lazy UpdateStrategy with DT.
 279   resetIR();
 280   runWithDomTree(*M, "f", [&](Function &F, DominatorTree *DT) {
 281     DomTreeUpdater DTU(*DT, DomTreeUpdater::UpdateStrategy::Lazy);
 282     Test(F, DTU);
 283   });
 284
 285   // Test MergeBasicBlockIntoOnlyPred working under Eager UpdateStrategy with
 286   // both DT and PDT.
 287   resetIRReplaceEntry();
 288   runWithDomTree(*M, "f", [&](Function &F, DominatorTree *DT) {
 289     PostDominatorTree PDT = PostDominatorTree(F);
 290     DomTreeUpdater DTU(*DT, PDT, DomTreeUpdater::UpdateStrategy::Eager);
 291     Test(F, DTU);
 292   });
 293
 294   // Test MergeBasicBlockIntoOnlyPred working under Eager UpdateStrategy with
 295   // DT.
 296   resetIRReplaceEntry();
 297   runWithDomTree(*M, "f", [&](Function &F, DominatorTree *DT) {
 298     DomTreeUpdater DTU(*DT, DomTreeUpdater::UpdateStrategy::Eager);
 299     Test(F, DTU);
 300   });
 301
 302   // Test MergeBasicBlockIntoOnlyPred working under Eager UpdateStrategy with
 303   // PDT.
 304   resetIRReplaceEntry();
 305   runWithDomTree(*M, "f", [&](Function &F, DominatorTree *DT) {
 306     PostDominatorTree PDT = PostDominatorTree(F);
 307     DomTreeUpdater DTU(PDT, DomTreeUpdater::UpdateStrategy::Eager);
 308     Test(F, DTU);
 309   });
 310
 311   // Test MergeBasicBlockIntoOnlyPred working under Lazy UpdateStrategy with
 312   // both DT and PDT.
 313   resetIRReplaceEntry();
 314   runWithDomTree(*M, "f", [&](Function &F, DominatorTree *DT) {
 315     PostDominatorTree PDT = PostDominatorTree(F);
 316     DomTreeUpdater DTU(*DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy);
 317     Test(F, DTU);
 318   });
 319
 320   // Test MergeBasicBlockIntoOnlyPred working under Lazy UpdateStrategy with
 321   // PDT.
 322   resetIRReplaceEntry();
 323   runWithDomTree(*M, "f", [&](Function &F, DominatorTree *DT) {
 324     PostDominatorTree PDT = PostDominatorTree(F);
 325     DomTreeUpdater DTU(PDT, DomTreeUpdater::UpdateStrategy::Lazy);
 326     Test(F, DTU);
 327   });
 328
 329   // Test MergeBasicBlockIntoOnlyPred working under Lazy UpdateStrategy with DT.
 330   resetIRReplaceEntry();
 331   runWithDomTree(*M, "f", [&](Function &F, DominatorTree *DT) {
 332     DomTreeUpdater DTU(*DT, DomTreeUpdater::UpdateStrategy::Lazy);
 333     Test(F, DTU);
 334   });
 335 }
 336
 337 TEST(Local, ConstantFoldTerminator) {
 338   LLVMContext C;
 339
 340   std::unique_ptr<Module> M = parseIR(C,
 341                                       R"(
 342       define void @br_same_dest() {
 343       entry:
 344         br i1 false, label %bb0, label %bb0
 345       bb0:
 346         ret void
 347       }
 348
 349       define void @br_different_dest() {
 350       entry:
 351         br i1 true, label %bb0, label %bb1
 352       bb0:
 353         br label %exit
 354       bb1:
 355         br label %exit
 356       exit:
 357         ret void
 358       }
 359
 360       define void @switch_2_different_dest() {
 361       entry:
 362         switch i32 0, label %default [ i32 0, label %bb0 ]
 363       default:
 364         ret void
 365       bb0:
 366         ret void
 367       }
 368       define void @switch_2_different_dest_default() {
 369       entry:
 370         switch i32 1, label %default [ i32 0, label %bb0 ]
 371       default:
 372         ret void
 373       bb0:
 374         ret void
 375       }
 376       define void @switch_3_different_dest() {
 377       entry:
 378         switch i32 0, label %default [ i32 0, label %bb0
 379                                        i32 1, label %bb1 ]
 380       default:
 381         ret void
 382       bb0:
 383         ret void
 384       bb1:
 385         ret void
 386       }
 387
 388       define void @switch_variable_2_default_dest(i32 %arg) {
 389       entry:
 390         switch i32 %arg, label %default [ i32 0, label %default ]
 391       default:
 392         ret void
 393       }
 394
 395       define void @switch_constant_2_default_dest() {
 396       entry:
 397         switch i32 1, label %default [ i32 0, label %default ]
 398       default:
 399         ret void
 400       }
 401
 402       define void @switch_constant_3_repeated_dest() {
 403       entry:
 404         switch i32 0, label %default [ i32 0, label %bb0
 405                                        i32 1, label %bb0 ]
 406        bb0:
 407          ret void
 408       default:
 409         ret void
 410       }
 411
 412       define void @indirectbr() {
 413       entry:
 414         indirectbr i8* blockaddress(@indirectbr, %bb0), [label %bb0, label %bb1]
 415       bb0:
 416         ret void
 417       bb1:
 418         ret void
 419       }
 420
 421       define void @indirectbr_repeated() {
 422       entry:
 423         indirectbr i8* blockaddress(@indirectbr_repeated, %bb0), [label %bb0, label %bb0]
 424       bb0:
 425         ret void
 426       }
 427
 428       define void @indirectbr_unreachable() {
 429       entry:
 430         indirectbr i8* blockaddress(@indirectbr_unreachable, %bb0), [label %bb1]
 431       bb0:
 432         ret void
 433       bb1:
 434         ret void
 435       }
 436         )");
 437
 438   auto CFAllTerminatorsEager = [&](Function &F, DominatorTree *DT) {
 439     PostDominatorTree PDT = PostDominatorTree(F);
 440     DomTreeUpdater DTU(*DT, PDT, DomTreeUpdater::UpdateStrategy::Eager);
 441     for (Function::iterator I = F.begin(), E = F.end(); I != E;) {
 442       BasicBlock *BB = &*I++;
 443       ConstantFoldTerminator(BB, true, nullptr, &DTU);
 444     }
 445
 446     EXPECT_TRUE(DTU.getDomTree().verify());
 447     EXPECT_TRUE(DTU.getPostDomTree().verify());
 448   };
 449
 450   auto CFAllTerminatorsLazy = [&](Function &F, DominatorTree *DT) {
 451     PostDominatorTree PDT = PostDominatorTree(F);
 452     DomTreeUpdater DTU(*DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy);
 453     for (Function::iterator I = F.begin(), E = F.end(); I != E;) {
 454       BasicBlock *BB = &*I++;
 455       ConstantFoldTerminator(BB, true, nullptr, &DTU);
 456     }
 457
 458     EXPECT_TRUE(DTU.getDomTree().verify());
 459     EXPECT_TRUE(DTU.getPostDomTree().verify());
 460   };
 461
 462   // Test ConstantFoldTerminator under Eager UpdateStrategy.
 463   runWithDomTree(*M, "br_same_dest", CFAllTerminatorsEager);
 464   runWithDomTree(*M, "br_different_dest", CFAllTerminatorsEager);
 465   runWithDomTree(*M, "switch_2_different_dest", CFAllTerminatorsEager);
 466   runWithDomTree(*M, "switch_2_different_dest_default", CFAllTerminatorsEager);
 467   runWithDomTree(*M, "switch_3_different_dest", CFAllTerminatorsEager);
 468   runWithDomTree(*M, "switch_variable_2_default_dest", CFAllTerminatorsEager);
 469   runWithDomTree(*M, "switch_constant_2_default_dest", CFAllTerminatorsEager);
 470   runWithDomTree(*M, "switch_constant_3_repeated_dest", CFAllTerminatorsEager);
 471   runWithDomTree(*M, "indirectbr", CFAllTerminatorsEager);
 472   runWithDomTree(*M, "indirectbr_repeated", CFAllTerminatorsEager);
 473   runWithDomTree(*M, "indirectbr_unreachable", CFAllTerminatorsEager);
 474
 475   // Test ConstantFoldTerminator under Lazy UpdateStrategy.
 476   runWithDomTree(*M, "br_same_dest", CFAllTerminatorsLazy);
 477   runWithDomTree(*M, "br_different_dest", CFAllTerminatorsLazy);
 478   runWithDomTree(*M, "switch_2_different_dest", CFAllTerminatorsLazy);
 479   runWithDomTree(*M, "switch_2_different_dest_default", CFAllTerminatorsLazy);
 480   runWithDomTree(*M, "switch_3_different_dest", CFAllTerminatorsLazy);
 481   runWithDomTree(*M, "switch_variable_2_default_dest", CFAllTerminatorsLazy);
 482   runWithDomTree(*M, "switch_constant_2_default_dest", CFAllTerminatorsLazy);
 483   runWithDomTree(*M, "switch_constant_3_repeated_dest", CFAllTerminatorsLazy);
 484   runWithDomTree(*M, "indirectbr", CFAllTerminatorsLazy);
 485   runWithDomTree(*M, "indirectbr_repeated", CFAllTerminatorsLazy);
 486   runWithDomTree(*M, "indirectbr_unreachable", CFAllTerminatorsLazy);
 487 }
 488
 489 struct SalvageDebugInfoTest : ::testing::Test {
 490   LLVMContext C;
 491   std::unique_ptr<Module> M;
 492   Function *F = nullptr;
 493
 494   void SetUp() override {
 495     M = parseIR(C,
 496                 R"(
 497       define void @f() !dbg !8 {
 498       entry:
 499         %x = add i32 0, 1
 500         %y = add i32 %x, 2
 501         call void @llvm.dbg.value(metadata i32 %x, metadata !11, metadata !DIExpression()), !dbg !13
 502         call void @llvm.dbg.value(metadata i32 %y, metadata !11, metadata !DIExpression()), !dbg !13
 503         ret void, !dbg !14
 504       }
 505       declare void @llvm.dbg.value(metadata, metadata, metadata)
 506       !llvm.dbg.cu = !{!0}
 507       !llvm.module.flags = !{!3, !4}
 508       !0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang version 6.0.0", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !2)
 509       !1 = !DIFile(filename: "t2.c", directory: "foo")
 510       !2 = !{}
 511       !3 = !{i32 2, !"Dwarf Version", i32 4}
 512       !4 = !{i32 2, !"Debug Info Version", i32 3}
 513       !8 = distinct !DISubprogram(name: "f", scope: !1, file: !1, line: 1, type: !9, isLocal: false, isDefinition: true, scopeLine: 1, isOptimized: false, unit: !0, retainedNodes: !2)
 514       !9 = !DISubroutineType(types: !10)
 515       !10 = !{null}
 516       !11 = !DILocalVariable(name: "x", scope: !8, file: !1, line: 2, type: !12)
 517       !12 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
 518       !13 = !DILocation(line: 2, column: 7, scope: !8)
 519       !14 = !DILocation(line: 3, column: 1, scope: !8)
 520       )");
 521
 522     auto *GV = M->getNamedValue("f");
 523     ASSERT_TRUE(GV);
 524     F = dyn_cast<Function>(GV);
 525     ASSERT_TRUE(F);
 526   }
 527
 528   bool doesDebugValueDescribeX(const DbgValueInst &DI) {
 529     if (DI.getNumVariableLocationOps() != 1u)
 530       return false;
 531     const auto &CI = *cast<ConstantInt>(DI.getValue(0));
 532     if (CI.isZero())
 533       return DI.getExpression()->getElements().equals(
 534           {dwarf::DW_OP_plus_uconst, 1, dwarf::DW_OP_stack_value});
 535     else if (CI.isOneValue())
 536       return DI.getExpression()->getElements().empty();
 537     return false;
 538   }
 539
 540   bool doesDebugValueDescribeY(const DbgValueInst &DI) {
 541     if (DI.getNumVariableLocationOps() != 1u)
 542       return false;
 543     const auto &CI = *cast<ConstantInt>(DI.getVariableLocationOp(0));
 544     if (CI.isZero())
 545       return DI.getExpression()->getElements().equals(
 546           {dwarf::DW_OP_plus_uconst, 1, dwarf::DW_OP_plus_uconst, 2,
 547            dwarf::DW_OP_stack_value});
 548     else if (CI.isOneValue())
 549       return DI.getExpression()->getElements().equals(
 550           {dwarf::DW_OP_plus_uconst, 2, dwarf::DW_OP_stack_value});
 551     return false;
 552   }
 553
 554   void verifyDebugValuesAreSalvaged() {
 555     // Check that the debug values for %x and %y are preserved.
 556     bool FoundX = false;
 557     bool FoundY = false;
 558     for (const Instruction &I : F->front()) {
 559       auto DI = dyn_cast<DbgValueInst>(&I);
 560       if (!DI) {
 561         // The function should only contain debug values and a terminator.
 562         ASSERT_TRUE(I.isTerminator());
 563         continue;
 564       }
 565       EXPECT_EQ(DI->getVariable()->getName(), "x");
 566       FoundX |= doesDebugValueDescribeX(*DI);
 567       FoundY |= doesDebugValueDescribeY(*DI);
 568     }
 569     ASSERT_TRUE(FoundX);
 570     ASSERT_TRUE(FoundY);
 571   }
 572 };
 573
 574 TEST_F(SalvageDebugInfoTest, RecursiveInstDeletion) {
 575   Instruction *Inst = &F->front().front();
 576   Inst = Inst->getNextNode(); // Get %y = add ...
 577   ASSERT_TRUE(Inst);
 578   bool Deleted = RecursivelyDeleteTriviallyDeadInstructions(Inst);
 579   ASSERT_TRUE(Deleted);
 580   verifyDebugValuesAreSalvaged();
 581 }
 582
 583 TEST_F(SalvageDebugInfoTest, RecursiveBlockSimplification) {
 584   BasicBlock *BB = &F->front();
 585   ASSERT_TRUE(BB);
 586   bool Deleted = SimplifyInstructionsInBlock(BB);
 587   ASSERT_TRUE(Deleted);
 588   verifyDebugValuesAreSalvaged();
 589 }
 590
 591 TEST(Local, wouldInstructionBeTriviallyDead) {
 592   LLVMContext Ctx;
 593   std::unique_ptr<Module> M = parseIR(Ctx,
 594                                       R"(
 595     define dso_local void @fun() local_unnamed_addr #0 !dbg !9 {
 596     entry:
 597       call void @llvm.dbg.declare(metadata !{}, metadata !13, metadata !DIExpression()), !dbg !16
 598       ret void, !dbg !16
 599     }
 600
 601     declare void @llvm.dbg.declare(metadata, metadata, metadata)
 602
 603     !llvm.dbg.cu = !{!0}
 604     !llvm.module.flags = !{!2, !3}
 605     !llvm.ident = !{!8}
 606
 607     !0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang version 16.0.0", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, splitDebugInlining: false, nameTableKind: None)
 608     !1 = !DIFile(filename: "test.c", directory: "/")
 609     !2 = !{i32 7, !"Dwarf Version", i32 5}
 610     !3 = !{i32 2, !"Debug Info Version", i32 3}
 611     !8 = !{!"clang version 16.0.0"}
 612     !9 = distinct !DISubprogram(name: "fun", scope: !1, file: !1, line: 1, type: !10, scopeLine: 1, flags: DIFlagAllCallsDescribed, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !12)
 613     !10 = !DISubroutineType(types: !11)
 614     !11 = !{null}
 615     !12 = !{!13}
 616     !13 = !DILocalVariable(name: "a", scope: !9, file: !1, line: 1, type: !14)
 617     !14 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
 618     !16 = !DILocation(line: 1, column: 21, scope: !9)
 619     )");
 620   bool BrokenDebugInfo = true;
 621   verifyModule(*M, &errs(), &BrokenDebugInfo);
 622   ASSERT_FALSE(BrokenDebugInfo);
 623
 624   // Get the dbg.declare.
 625   Function &F = *cast<Function>(M->getNamedValue("fun"));
 626   Instruction *DbgDeclare = &F.front().front();
 627   ASSERT_TRUE(isa<DbgDeclareInst>(DbgDeclare));
 628   // Debug intrinsics with empty metadata arguments are not dead.
 629   EXPECT_FALSE(wouldInstructionBeTriviallyDead(DbgDeclare));
 630 }
 631
 632 TEST(Local, ChangeToUnreachable) {
 633   LLVMContext Ctx;
 634
 635   std::unique_ptr<Module> M = parseIR(Ctx,
 636                                       R"(
 637     define internal void @foo() !dbg !6 {
 638     entry:
 639       ret void, !dbg !8
 640     }
 641
 642     !llvm.dbg.cu = !{!0}
 643     !llvm.debugify = !{!3, !4}
 644     !llvm.module.flags = !{!5}
 645
 646     !0 = distinct !DICompileUnit(language: DW_LANG_C, file: !1, producer: "debugify", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2)
 647     !1 = !DIFile(filename: "test.ll", directory: "/")
 648     !2 = !{}
 649     !3 = !{i32 1}
 650     !4 = !{i32 0}
 651     !5 = !{i32 2, !"Debug Info Version", i32 3}
 652     !6 = distinct !DISubprogram(name: "foo", linkageName: "foo", scope: null, file: !1, line: 1, type: !7, isLocal: true, isDefinition: true, scopeLine: 1, isOptimized: true, unit: !0, retainedNodes: !2)
 653     !7 = !DISubroutineType(types: !2)
 654     !8 = !DILocation(line: 1, column: 1, scope: !6)
 655   )");
 656
 657   bool BrokenDebugInfo = true;
 658   verifyModule(*M, &errs(), &BrokenDebugInfo);
 659   ASSERT_FALSE(BrokenDebugInfo);
 660
 661   Function &F = *cast<Function>(M->getNamedValue("foo"));
 662
 663   BasicBlock &BB = F.front();
 664   Instruction &A = BB.front();
 665   DebugLoc DLA = A.getDebugLoc();
 666
 667   ASSERT_TRUE(isa<ReturnInst>(&A));
 668   // One instruction should be affected.
 669   EXPECT_EQ(changeToUnreachable(&A), 1U);
 670
 671   Instruction &B = BB.front();
 672
 673   // There should be an uncreachable instruction.
 674   ASSERT_TRUE(isa<UnreachableInst>(&B));
 675
 676   DebugLoc DLB = B.getDebugLoc();
 677   EXPECT_EQ(DLA, DLB);
 678 }
 679
 680 TEST(Local, FindDbgUsers) {
 681   LLVMContext Ctx;
 682   std::unique_ptr<Module> M = parseIR(Ctx,
 683                                       R"(
 684   define dso_local void @fun(ptr %a) #0 !dbg !11 {
 685   entry:
 686     call void @llvm.dbg.assign(metadata ptr %a, metadata !16, metadata !DIExpression(), metadata !15, metadata ptr %a, metadata !DIExpression()), !dbg !19
 687     ret void
 688   }
 689
 690   declare void @llvm.dbg.assign(metadata, metadata, metadata, metadata, metadata, metadata)
 691
 692   !llvm.dbg.cu = !{!0}
 693   !llvm.module.flags = !{!2, !3, !9}
 694   !llvm.ident = !{!10}
 695
 696   !0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus_14, file: !1, producer: "clang version 17.0.0", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, splitDebugInlining: false, nameTableKind: None)
 697   !1 = !DIFile(filename: "test.cpp", directory: "/")
 698   !2 = !{i32 7, !"Dwarf Version", i32 5}
 699   !3 = !{i32 2, !"Debug Info Version", i32 3}
 700   !4 = !{i32 1, !"wchar_size", i32 4}
 701   !9 = !{i32 7, !"debug-info-assignment-tracking", i1 true}
 702   !10 = !{!"clang version 17.0.0"}
 703   !11 = distinct !DISubprogram(name: "fun", linkageName: "fun", scope: !1, file: !1, line: 1, type: !12, scopeLine: 1, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition, unit: !0, retainedNodes: !14)
 704   !12 = !DISubroutineType(types: !13)
 705   !13 = !{null}
 706   !14 = !{}
 707   !15 = distinct !DIAssignID()
 708   !16 = !DILocalVariable(name: "x", scope: !11, file: !1, line: 2, type: !17)
 709   !17 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !18, size: 64)
 710   !18 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
 711   !19 = !DILocation(line: 0, scope: !11)
 712   )");
 713
 714   bool BrokenDebugInfo = true;
 715   verifyModule(*M, &errs(), &BrokenDebugInfo);
 716   ASSERT_FALSE(BrokenDebugInfo);
 717
 718   Function &Fun = *cast<Function>(M->getNamedValue("fun"));
 719   Value *Arg = Fun.getArg(0);
 720
 721   SmallVector<DbgVariableIntrinsic *> Users;
 722   // Arg (%a) is used twice by a single dbg.assign. Check findDbgUsers returns
 723   // only 1 pointer to it rather than 2.
 724   findDbgUsers(Users, Arg);
 725   EXPECT_EQ(Users.size(), 1u);
 726
 727   SmallVector<DbgValueInst *> Vals;
 728   // Arg (%a) is used twice by a single dbg.assign. Check findDbgValues returns
 729   // only 1 pointer to it rather than 2.
 730   findDbgValues(Vals, Arg);
 731   EXPECT_EQ(Vals.size(), 1u);
 732 }
 733
 734 TEST(Local, ReplaceAllDbgUsesWith) {
 735   using namespace llvm::dwarf;
 736
 737   LLVMContext Ctx;
 738
 739   // Note: The datalayout simulates Darwin/x86_64.
 740   std::unique_ptr<Module> M = parseIR(Ctx,
 741                                       R"(
 742     target datalayout = "e-m:o-i63:64-f80:128-n8:16:32:64-S128"
 743
 744     declare i32 @escape(i32)
 745
 746     define void @f() !dbg !6 {
 747     entry:
 748       %a = add i32 0, 1, !dbg !15
 749       call void @llvm.dbg.value(metadata i32 %a, metadata !9, metadata !DIExpression()), !dbg !15
 750
 751       %b = add i64 0, 1, !dbg !16
 752       call void @llvm.dbg.value(metadata i64 %b, metadata !11, metadata !DIExpression()), !dbg !16
 753       call void @llvm.dbg.value(metadata i64 %b, metadata !11, metadata !DIExpression(DW_OP_lit0, DW_OP_mul)), !dbg !16
 754       call void @llvm.dbg.value(metadata i64 %b, metadata !11, metadata !DIExpression(DW_OP_lit0, DW_OP_mul, DW_OP_stack_value)), !dbg !16
 755       call void @llvm.dbg.value(metadata i64 %b, metadata !11, metadata !DIExpression(DW_OP_LLVM_fragment, 0, 8)), !dbg !16
 756       call void @llvm.dbg.value(metadata i64 %b, metadata !11, metadata !DIExpression(DW_OP_lit0, DW_OP_mul, DW_OP_LLVM_fragment, 0, 8)), !dbg !16
 757       call void @llvm.dbg.value(metadata i64 %b, metadata !11, metadata !DIExpression(DW_OP_lit0, DW_OP_mul, DW_OP_stack_value, DW_OP_LLVM_fragment, 0, 8)), !dbg !16
 758
 759       %c = inttoptr i64 0 to i64*, !dbg !17
 760       call void @llvm.dbg.declare(metadata i64* %c, metadata !13, metadata !DIExpression()), !dbg !17
 761
 762       %d = inttoptr i64 0 to i32*, !dbg !18
 763       call void @llvm.dbg.declare(metadata i32* %d, metadata !20, metadata !DIExpression()), !dbg !18
 764
 765       %e = add <2 x i16> zeroinitializer, zeroinitializer
 766       call void @llvm.dbg.value(metadata <2 x i16> %e, metadata !14, metadata !DIExpression()), !dbg !18
 767
 768       %f = call i32 @escape(i32 0)
 769       call void @llvm.dbg.value(metadata i32 %f, metadata !9, metadata !DIExpression()), !dbg !15
 770
 771       %barrier = call i32 @escape(i32 0)
 772
 773       %g = call i32 @escape(i32 %f)
 774       call void @llvm.dbg.value(metadata i32 %g, metadata !9, metadata !DIExpression()), !dbg !15
 775
 776       ret void, !dbg !19
 777     }
 778
 779     declare void @llvm.dbg.declare(metadata, metadata, metadata)
 780     declare void @llvm.dbg.value(metadata, metadata, metadata)
 781
 782     !llvm.dbg.cu = !{!0}
 783     !llvm.module.flags = !{!5}
 784
 785     !0 = distinct !DICompileUnit(language: DW_LANG_C, file: !1, producer: "debugify", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2)
 786     !1 = !DIFile(filename: "/Users/vsk/Desktop/foo.ll", directory: "/")
 787     !2 = !{}
 788     !5 = !{i32 2, !"Debug Info Version", i32 3}
 789     !6 = distinct !DISubprogram(name: "f", linkageName: "f", scope: null, file: !1, line: 1, type: !7, isLocal: false, isDefinition: true, scopeLine: 1, isOptimized: true, unit: !0, retainedNodes: !8)
 790     !7 = !DISubroutineType(types: !2)
 791     !8 = !{!9, !11, !13, !14}
 792     !9 = !DILocalVariable(name: "1", scope: !6, file: !1, line: 1, type: !10)
 793     !10 = !DIBasicType(name: "ty32", size: 32, encoding: DW_ATE_signed)
 794     !11 = !DILocalVariable(name: "2", scope: !6, file: !1, line: 2, type: !12)
 795     !12 = !DIBasicType(name: "ty64", size: 64, encoding: DW_ATE_signed)
 796     !13 = !DILocalVariable(name: "3", scope: !6, file: !1, line: 3, type: !12)
 797     !14 = !DILocalVariable(name: "4", scope: !6, file: !1, line: 4, type: !10)
 798     !15 = !DILocation(line: 1, column: 1, scope: !6)
 799     !16 = !DILocation(line: 2, column: 1, scope: !6)
 800     !17 = !DILocation(line: 3, column: 1, scope: !6)
 801     !18 = !DILocation(line: 4, column: 1, scope: !6)
 802     !19 = !DILocation(line: 5, column: 1, scope: !6)
 803     !20 = !DILocalVariable(name: "5", scope: !6, file: !1, line: 5, type: !10)
 804   )");
 805
 806   bool BrokenDebugInfo = true;
 807   verifyModule(*M, &errs(), &BrokenDebugInfo);
 808   ASSERT_FALSE(BrokenDebugInfo);
 809
 810   Function &F = *cast<Function>(M->getNamedValue("f"));
 811   DominatorTree DT{F};
 812
 813   BasicBlock &BB = F.front();
 814   Instruction &A = BB.front();
 815   Instruction &B = *A.getNextNonDebugInstruction();
 816   Instruction &C = *B.getNextNonDebugInstruction();
 817   Instruction &D = *C.getNextNonDebugInstruction();
 818   Instruction &E = *D.getNextNonDebugInstruction();
 819   Instruction &F_ = *E.getNextNonDebugInstruction();
 820   Instruction &Barrier = *F_.getNextNonDebugInstruction();
 821   Instruction &G = *Barrier.getNextNonDebugInstruction();
 822
 823   // Simulate i32 <-> i64* conversion. Expect no updates: the datalayout says
 824   // pointers are 64 bits, so the conversion would be lossy.
 825   EXPECT_FALSE(replaceAllDbgUsesWith(A, C, C, DT));
 826   EXPECT_FALSE(replaceAllDbgUsesWith(C, A, A, DT));
 827
 828   // Simulate i32 <-> <2 x i16> conversion. This is unsupported.
 829   EXPECT_FALSE(replaceAllDbgUsesWith(E, A, A, DT));
 830   EXPECT_FALSE(replaceAllDbgUsesWith(A, E, E, DT));
 831
 832   // Simulate i32* <-> i64* conversion.
 833   EXPECT_TRUE(replaceAllDbgUsesWith(D, C, C, DT));
 834
 835   SmallVector<DbgVariableIntrinsic *, 2> CDbgVals;
 836   findDbgUsers(CDbgVals, &C);
 837   EXPECT_EQ(2U, CDbgVals.size());
 838   EXPECT_TRUE(all_of(CDbgVals, [](DbgVariableIntrinsic *DII) {
 839     return isa<DbgDeclareInst>(DII);
 840   }));
 841
 842   EXPECT_TRUE(replaceAllDbgUsesWith(C, D, D, DT));
 843
 844   SmallVector<DbgVariableIntrinsic *, 2> DDbgVals;
 845   findDbgUsers(DDbgVals, &D);
 846   EXPECT_EQ(2U, DDbgVals.size());
 847   EXPECT_TRUE(all_of(DDbgVals, [](DbgVariableIntrinsic *DII) {
 848     return isa<DbgDeclareInst>(DII);
 849   }));
 850
 851   // Introduce a use-before-def. Check that the dbg.value for %a is salvaged.
 852   EXPECT_TRUE(replaceAllDbgUsesWith(A, F_, F_, DT));
 853
 854   auto *ADbgVal = cast<DbgValueInst>(A.getNextNode());
 855   EXPECT_EQ(ADbgVal->getNumVariableLocationOps(), 1u);
 856   EXPECT_EQ(ConstantInt::get(A.getType(), 0), ADbgVal->getVariableLocationOp(0));
 857
 858   // Introduce a use-before-def. Check that the dbg.values for %f become undef.
 859   EXPECT_TRUE(replaceAllDbgUsesWith(F_, G, G, DT));
 860
 861   auto *FDbgVal = cast<DbgValueInst>(F_.getNextNode());
 862   EXPECT_EQ(FDbgVal->getNumVariableLocationOps(), 1u);
 863   EXPECT_TRUE(FDbgVal->isKillLocation());
 864
 865   SmallVector<DbgValueInst *, 1> FDbgVals;
 866   findDbgValues(FDbgVals, &F_);
 867   EXPECT_EQ(0U, FDbgVals.size());
 868
 869   // Simulate i32 -> i64 conversion to test sign-extension. Here are some
 870   // interesting cases to handle:
 871   //  1) debug user has empty DIExpression
 872   //  2) debug user has non-empty, non-stack-value'd DIExpression
 873   //  3) debug user has non-empty, stack-value'd DIExpression
 874   //  4-6) like (1-3), but with a fragment
 875   EXPECT_TRUE(replaceAllDbgUsesWith(B, A, A, DT));
 876
 877   SmallVector<DbgValueInst *, 8> ADbgVals;
 878   findDbgValues(ADbgVals, &A);
 879   EXPECT_EQ(6U, ADbgVals.size());
 880
 881   // Check that %a has a dbg.value with a DIExpression matching \p Ops.
 882   auto hasADbgVal = [&](ArrayRef<uint64_t> Ops) {
 883     return any_of(ADbgVals, [&](DbgValueInst *DVI) {
 884       assert(DVI->getVariable()->getName() == "2");
 885       return DVI->getExpression()->getElements() == Ops;
 886     });
 887   };
 888
 889   // Case 1: The original expr is empty, so no deref is needed.
 890   EXPECT_TRUE(hasADbgVal({DW_OP_LLVM_convert, 32, DW_ATE_signed,
 891                          DW_OP_LLVM_convert, 64, DW_ATE_signed,
 892                          DW_OP_stack_value}));
 893
 894   // Case 2: Perform an address calculation with the original expr, deref it,
 895   // then sign-extend the result.
 896   EXPECT_TRUE(hasADbgVal({DW_OP_lit0, DW_OP_mul, DW_OP_deref,
 897                          DW_OP_LLVM_convert, 32, DW_ATE_signed,
 898                          DW_OP_LLVM_convert, 64, DW_ATE_signed,
 899                          DW_OP_stack_value}));
 900
 901   // Case 3: Insert the sign-extension logic before the DW_OP_stack_value.
 902   EXPECT_TRUE(hasADbgVal({DW_OP_lit0, DW_OP_mul, DW_OP_LLVM_convert, 32,
 903                          DW_ATE_signed, DW_OP_LLVM_convert, 64, DW_ATE_signed,
 904                          DW_OP_stack_value}));
 905
 906   // Cases 4-6: Just like cases 1-3, but preserve the fragment at the end.
 907   EXPECT_TRUE(hasADbgVal({DW_OP_LLVM_convert, 32, DW_ATE_signed,
 908                          DW_OP_LLVM_convert, 64, DW_ATE_signed,
 909                          DW_OP_stack_value, DW_OP_LLVM_fragment, 0, 8}));
 910
 911   EXPECT_TRUE(hasADbgVal({DW_OP_lit0, DW_OP_mul, DW_OP_deref,
 912                          DW_OP_LLVM_convert, 32, DW_ATE_signed,
 913                          DW_OP_LLVM_convert, 64, DW_ATE_signed,
 914                          DW_OP_stack_value, DW_OP_LLVM_fragment, 0, 8}));
 915
 916   EXPECT_TRUE(hasADbgVal({DW_OP_lit0, DW_OP_mul, DW_OP_LLVM_convert, 32,
 917                          DW_ATE_signed, DW_OP_LLVM_convert, 64, DW_ATE_signed,
 918                          DW_OP_stack_value, DW_OP_LLVM_fragment, 0, 8}));
 919
 920   verifyModule(*M, &errs(), &BrokenDebugInfo);
 921   ASSERT_FALSE(BrokenDebugInfo);
 922 }
 923
 924 TEST(Local, RemoveUnreachableBlocks) {
 925   LLVMContext C;
 926
 927   std::unique_ptr<Module> M = parseIR(C,
 928                                       R"(
 929       define void @br_simple() {
 930       entry:
 931         br label %bb0
 932       bb0:
 933         ret void
 934       bb1:
 935         ret void
 936       }
 937
 938       define void @br_self_loop() {
 939       entry:
 940         br label %bb0
 941       bb0:
 942         br i1 true, label %bb1, label %bb0
 943       bb1:
 944         br i1 true, label %bb0, label %bb2
 945       bb2:
 946         br label %bb2
 947       }
 948
 949       define void @br_constant() {
 950       entry:
 951         br label %bb0
 952       bb0:
 953         br i1 true, label %bb1, label %bb2
 954       bb1:
 955         br i1 true, label %bb0, label %bb2
 956       bb2:
 957         br label %bb2
 958       }
 959
 960       define void @br_loop() {
 961       entry:
 962         br label %bb0
 963       bb0:
 964         br label %bb0
 965       bb1:
 966         br label %bb2
 967       bb2:
 968         br label %bb1
 969       }
 970
 971       declare i32 @__gxx_personality_v0(...)
 972
 973       define void @invoke_terminator() personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*) {
 974       entry:
 975         br i1 undef, label %invoke.block, label %exit
 976
 977       invoke.block:
 978         %cond = invoke zeroext i1 @invokable()
 979                 to label %continue.block unwind label %lpad.block
 980
 981       continue.block:
 982         br i1 %cond, label %if.then, label %if.end
 983
 984       if.then:
 985         unreachable
 986
 987       if.end:
 988         unreachable
 989
 990       lpad.block:
 991         %lp = landingpad { i8*, i32 }
 992                 catch i8* null
 993         br label %exit
 994
 995       exit:
 996         ret void
 997       }
 998
 999       declare i1 @invokable()
1000       )");
1001
1002   auto runEager = [&](Function &F, DominatorTree *DT) {
1003     PostDominatorTree PDT = PostDominatorTree(F);
1004     DomTreeUpdater DTU(*DT, PDT, DomTreeUpdater::UpdateStrategy::Eager);
1005     removeUnreachableBlocks(F, &DTU);
1006     EXPECT_TRUE(DTU.getDomTree().verify());
1007     EXPECT_TRUE(DTU.getPostDomTree().verify());
1008   };
1009
1010   auto runLazy = [&](Function &F, DominatorTree *DT) {
1011     PostDominatorTree PDT = PostDominatorTree(F);
1012     DomTreeUpdater DTU(*DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy);
1013     removeUnreachableBlocks(F, &DTU);
1014     EXPECT_TRUE(DTU.getDomTree().verify());
1015     EXPECT_TRUE(DTU.getPostDomTree().verify());
1016   };
1017
1018   // Test removeUnreachableBlocks under Eager UpdateStrategy.
1019   runWithDomTree(*M, "br_simple", runEager);
1020   runWithDomTree(*M, "br_self_loop", runEager);
1021   runWithDomTree(*M, "br_constant", runEager);
1022   runWithDomTree(*M, "br_loop", runEager);
1023   runWithDomTree(*M, "invoke_terminator", runEager);
1024
1025   // Test removeUnreachableBlocks under Lazy UpdateStrategy.
1026   runWithDomTree(*M, "br_simple", runLazy);
1027   runWithDomTree(*M, "br_self_loop", runLazy);
1028   runWithDomTree(*M, "br_constant", runLazy);
1029   runWithDomTree(*M, "br_loop", runLazy);
1030   runWithDomTree(*M, "invoke_terminator", runLazy);
1031
1032   M = parseIR(C,
1033               R"(
1034       define void @f() {
1035       entry:
1036         ret void
1037       bb0:
1038         ret void
1039       }
1040         )");
1041
1042   auto checkRUBlocksRetVal = [&](Function &F, DominatorTree *DT) {
1043     DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
1044     EXPECT_TRUE(removeUnreachableBlocks(F, &DTU));
1045     EXPECT_FALSE(removeUnreachableBlocks(F, &DTU));
1046     EXPECT_TRUE(DTU.getDomTree().verify());
1047   };
1048
1049   runWithDomTree(*M, "f", checkRUBlocksRetVal);
1050 }
1051
1052 TEST(Local, SimplifyCFGWithNullAC) {
1053   LLVMContext Ctx;
1054
1055   std::unique_ptr<Module> M = parseIR(Ctx, R"(
1056     declare void @true_path()
1057     declare void @false_path()
1058     declare void @llvm.assume(i1 %cond);
1059
1060     define i32 @foo(i1, i32) {
1061     entry:
1062       %cmp = icmp sgt i32 %1, 0
1063       br i1 %cmp, label %if.bb1, label %then.bb1
1064     if.bb1:
1065       call void @true_path()
1066       br label %test.bb
1067     then.bb1:
1068       call void @false_path()
1069       br label %test.bb
1070     test.bb:
1071       %phi = phi i1 [1, %if.bb1], [%0, %then.bb1]
1072       call void @llvm.assume(i1 %0)
1073       br i1 %phi, label %if.bb2, label %then.bb2
1074     if.bb2:
1075       ret i32 %1
1076     then.bb2:
1077       ret i32 0
1078     }
1079   )");
1080
1081   Function &F = *cast<Function>(M->getNamedValue("foo"));
1082   TargetTransformInfo TTI(M->getDataLayout());
1083
1084   SimplifyCFGOptions Options{};
1085   Options.setAssumptionCache(nullptr);
1086
1087   // Obtain BasicBlock of interest to this test, %test.bb.
1088   BasicBlock *TestBB = nullptr;
1089   for (BasicBlock &BB : F) {
1090     if (BB.getName().equals("test.bb")) {
1091       TestBB = &BB;
1092       break;
1093     }
1094   }
1095   ASSERT_TRUE(TestBB);
1096
1097   DominatorTree DT(F);
1098   DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
1099
1100   // %test.bb is expected to be simplified by FoldCondBranchOnPHI.
1101   EXPECT_TRUE(simplifyCFG(TestBB, TTI,
1102                           RequireAndPreserveDomTree ? &DTU : nullptr, Options));
1103 }
1104
1105 TEST(Local, CanReplaceOperandWithVariable) {
1106   LLVMContext Ctx;
1107   Module M("test_module", Ctx);
1108   IRBuilder<> B(Ctx);
1109
1110   FunctionType *FnType =
1111     FunctionType::get(Type::getVoidTy(Ctx), {}, false);
1112
1113   FunctionType *VarArgFnType =
1114     FunctionType::get(Type::getVoidTy(Ctx), {B.getInt32Ty()}, true);
1115
1116   Function *TestBody = Function::Create(FnType, GlobalValue::ExternalLinkage,
1117                                         0, "", &M);
1118
1119   BasicBlock *BB0 = BasicBlock::Create(Ctx, "", TestBody);
1120   B.SetInsertPoint(BB0);
1121
1122   FunctionCallee Intrin = M.getOrInsertFunction("llvm.foo", FnType);
1123   FunctionCallee Func = M.getOrInsertFunction("foo", FnType);
1124   FunctionCallee VarArgFunc
1125     = M.getOrInsertFunction("foo.vararg", VarArgFnType);
1126   FunctionCallee VarArgIntrin
1127     = M.getOrInsertFunction("llvm.foo.vararg", VarArgFnType);
1128
1129   auto *CallToIntrin = B.CreateCall(Intrin);
1130   auto *CallToFunc = B.CreateCall(Func);
1131
1132   // Test if it's valid to replace the callee operand.
1133   EXPECT_FALSE(canReplaceOperandWithVariable(CallToIntrin, 0));
1134   EXPECT_TRUE(canReplaceOperandWithVariable(CallToFunc, 0));
1135
1136   // That it's invalid to replace an argument in the variadic argument list for
1137   // an intrinsic, but OK for a normal function.
1138   auto *CallToVarArgFunc = B.CreateCall(
1139     VarArgFunc, {B.getInt32(0), B.getInt32(1), B.getInt32(2)});
1140   EXPECT_TRUE(canReplaceOperandWithVariable(CallToVarArgFunc, 0));
1141   EXPECT_TRUE(canReplaceOperandWithVariable(CallToVarArgFunc, 1));
1142   EXPECT_TRUE(canReplaceOperandWithVariable(CallToVarArgFunc, 2));
1143   EXPECT_TRUE(canReplaceOperandWithVariable(CallToVarArgFunc, 3));
1144
1145   auto *CallToVarArgIntrin = B.CreateCall(
1146     VarArgIntrin, {B.getInt32(0), B.getInt32(1), B.getInt32(2)});
1147   EXPECT_TRUE(canReplaceOperandWithVariable(CallToVarArgIntrin, 0));
1148   EXPECT_FALSE(canReplaceOperandWithVariable(CallToVarArgIntrin, 1));
1149   EXPECT_FALSE(canReplaceOperandWithVariable(CallToVarArgIntrin, 2));
1150   EXPECT_FALSE(canReplaceOperandWithVariable(CallToVarArgIntrin, 3));
1151
1152   // Test that it's invalid to replace gcroot operands, even though it can't use
1153   // immarg.
1154   Type *PtrPtr = B.getPtrTy(0);
1155   Value *Alloca = B.CreateAlloca(PtrPtr, (unsigned)0);
1156   CallInst *GCRoot = B.CreateIntrinsic(Intrinsic::gcroot, {},
1157     {Alloca, Constant::getNullValue(PtrPtr)});
1158   EXPECT_TRUE(canReplaceOperandWithVariable(GCRoot, 0)); // Alloca
1159   EXPECT_FALSE(canReplaceOperandWithVariable(GCRoot, 1));
1160   EXPECT_FALSE(canReplaceOperandWithVariable(GCRoot, 2));
1161
1162   BB0->dropAllReferences();
1163 }
1164
1165 TEST(Local, ExpressionForConstant) {
1166   LLVMContext Context;
1167   Module M("test_module", Context);
1168   DIBuilder DIB(M);
1169   DIExpression *Expr = nullptr;
1170
1171   auto createExpression = [&](Constant *C, Type *Ty) -> DIExpression * {
1172     EXPECT_NE(C, nullptr);
1173     EXPECT_NE(Ty, nullptr);
1174     EXPECT_EQ(C->getType(), Ty);
1175     std::unique_ptr<GlobalVariable> GV = std::make_unique<GlobalVariable>(
1176         Ty, false, GlobalValue::ExternalLinkage, C, "GV");
1177     EXPECT_NE(GV, nullptr);
1178
1179     DIExpression *Expr = getExpressionForConstant(DIB, *GV->getInitializer(),
1180                                                   *GV->getValueType());
1181     if (Expr) {
1182       EXPECT_EQ(Expr->getNumElements(), 3u);
1183       EXPECT_EQ(Expr->getElement(0), dwarf::DW_OP_constu);
1184       EXPECT_EQ(Expr->getElement(2), dwarf::DW_OP_stack_value);
1185     }
1186     return Expr;
1187   };
1188
1189   // Integer.
1190   IntegerType *Int1Ty = Type::getInt1Ty(Context);
1191   Expr = createExpression(ConstantInt::getTrue(Context), Int1Ty);
1192   EXPECT_NE(Expr, nullptr);
1193   EXPECT_EQ(Expr->getElement(1), 18446744073709551615U);
1194
1195   Expr = createExpression(ConstantInt::getFalse(Context), Int1Ty);
1196   EXPECT_NE(Expr, nullptr);
1197   EXPECT_EQ(Expr->getElement(1), 0U);
1198
1199   IntegerType *Int8Ty = Type::getInt8Ty(Context);
1200   Expr = createExpression(ConstantInt::get(Int8Ty, 100), Int8Ty);
1201   EXPECT_NE(Expr, nullptr);
1202   EXPECT_EQ(Expr->getElement(1), 100U);
1203
1204   IntegerType *Int16Ty = Type::getInt16Ty(Context);
1205   Expr = createExpression(ConstantInt::getSigned(Int16Ty, -50), Int16Ty);
1206   EXPECT_NE(Expr, nullptr);
1207   EXPECT_EQ(Expr->getElement(1), -50ULL);
1208
1209   IntegerType *Int32Ty = Type::getInt32Ty(Context);
1210   Expr = createExpression(ConstantInt::get(Int32Ty, 0x7FFFFFFF), Int32Ty);
1211   EXPECT_NE(Expr, nullptr);
1212   EXPECT_EQ(Expr->getElement(1), 0x7FFFFFFFU);
1213
1214   IntegerType *Int64Ty = Type::getInt64Ty(Context);
1215   Expr =
1216       createExpression(ConstantInt::get(Int64Ty, 0x7FFFFFFFFFFFFFFF), Int64Ty);
1217   EXPECT_NE(Expr, nullptr);
1218   EXPECT_EQ(Expr->getElement(1), 0x7FFFFFFFFFFFFFFFU);
1219
1220   IntegerType *Int128Ty = Type::getInt128Ty(Context);
1221   Expr = createExpression(ConstantInt::get(Int128Ty, 0x7FFFFFFFFFFFFFFF),
1222                           Int128Ty);
1223   EXPECT_NE(Expr, nullptr);
1224   EXPECT_EQ(Expr->getElement(1), 0x7FFFFFFFFFFFFFFFU);
1225
1226   GlobalVariable *String =
1227       IRBuilder<>(Context).CreateGlobalString("hello", "hello", 0, &M);
1228   Expr = createExpression(ConstantExpr::getPtrToInt(String, Int32Ty), Int32Ty);
1229   EXPECT_EQ(Expr, nullptr);
1230
1231   // Float.
1232   Type *FloatTy = Type::getFloatTy(Context);
1233   Expr = createExpression(ConstantFP::get(FloatTy, 5.55), FloatTy);
1234   EXPECT_NE(Expr, nullptr);
1235   EXPECT_EQ(Expr->getElement(1), 1085381018U);
1236
1237   // Double.
1238   Type *DoubleTy = Type::getDoubleTy(Context);
1239   Expr = createExpression(ConstantFP::get(DoubleTy, -5.55), DoubleTy);
1240   EXPECT_NE(Expr, nullptr);
1241   EXPECT_EQ(Expr->getElement(1), 13841306799765140275U);
1242
1243   // Pointer.
1244   PointerType *PtrTy = PointerType::get(Context, 0);
1245   Expr = createExpression(ConstantPointerNull::get(PtrTy), PtrTy);
1246   EXPECT_NE(Expr, nullptr);
1247   EXPECT_EQ(Expr->getElement(1), 0U);
1248
1249   ConstantInt *K1 = ConstantInt::get(Type::getInt32Ty(Context), 1234);
1250   Expr = createExpression(ConstantExpr::getIntToPtr(K1, PtrTy), PtrTy);
1251   EXPECT_NE(Expr, nullptr);
1252   EXPECT_EQ(Expr->getElement(1), 1234U);
1253
1254   ConstantInt *K2 = ConstantInt::get(Type::getInt64Ty(Context), 5678);
1255   Expr = createExpression(ConstantExpr::getIntToPtr(K2, PtrTy), PtrTy);
1256   EXPECT_NE(Expr, nullptr);
1257   EXPECT_EQ(Expr->getElement(1), 5678U);
1258
1259   // Others.
1260   Type *HalfTy = Type::getHalfTy(Context);
1261   Expr = createExpression(ConstantFP::get(HalfTy, 32), HalfTy);
1262   EXPECT_EQ(Expr, nullptr);
1263
1264   Type *BFloatTy = Type::getBFloatTy(Context);
1265   Expr = createExpression(ConstantFP::get(BFloatTy, 32), BFloatTy);
1266   EXPECT_EQ(Expr, nullptr);
1267
1268   Type *FP128Ty = Type::getFP128Ty(Context);
1269   Expr = createExpression(ConstantFP::get(FP128Ty, 32), FP128Ty);
1270   EXPECT_EQ(Expr, nullptr);
1271
1272   Type *X86_FP80Ty = Type::getX86_FP80Ty(Context);
1273   Expr = createExpression(ConstantFP::get(X86_FP80Ty, 32), X86_FP80Ty);
1274   EXPECT_EQ(Expr, nullptr);
1275
1276   Type *PPC_FP128Ty = Type::getPPC_FP128Ty(Context);
1277   Expr = createExpression(ConstantFP::get(PPC_FP128Ty, 32), PPC_FP128Ty);
1278   EXPECT_EQ(Expr, nullptr);
1279 }