llvm/unittests/CodeGen/MachineDomTreeUpdaterTest.cpp

   1 //===- MachineDomTreeUpdaterTest.cpp - MachineDomTreeUpdater unit tests ---===//
   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/CodeGen/MachineDomTreeUpdater.h"
  10 #include "llvm/Analysis/CGSCCPassManager.h"
  11 #include "llvm/Analysis/LoopAnalysisManager.h"
  12 #include "llvm/CodeGen/MIRParser/MIRParser.h"
  13 #include "llvm/CodeGen/MachineFunctionAnalysis.h"
  14 #include "llvm/CodeGen/MachineModuleInfo.h"
  15 #include "llvm/CodeGen/MachinePassManager.h"
  16 #include "llvm/CodeGen/MachinePostDominators.h"
  17 #include "llvm/CodeGen/SelectionDAG.h"
  18 #include "llvm/CodeGen/TargetLowering.h"
  19 #include "llvm/IR/Module.h"
  20 #include "llvm/MC/TargetRegistry.h"
  21 #include "llvm/Passes/PassBuilder.h"
  22 #include "llvm/Support/SourceMgr.h"
  23 #include "llvm/Support/TargetSelect.h"
  24 #include "llvm/Target/TargetMachine.h"
  25 #include "gtest/gtest.h"
  26
  27 using namespace llvm;
  28
  29 class MachineDomTreeUpdaterTest : public testing::Test {
  30 public:
  31   LLVMContext Context;
  32   std::unique_ptr<TargetMachine> TM;
  33   std::unique_ptr<Module> M;
  34   std::unique_ptr<MachineModuleInfo> MMI;
  35   std::unique_ptr<MIRParser> MIR;
  36
  37   LoopAnalysisManager LAM;
  38   MachineFunctionAnalysisManager MFAM;
  39   FunctionAnalysisManager FAM;
  40   CGSCCAnalysisManager CGAM;
  41   ModuleAnalysisManager MAM;
  42
  43   ModulePassManager MPM;
  44   FunctionPassManager FPM;
  45   MachineFunctionPassManager MFPM;
  46
  47   static void SetUpTestCase() {
  48     InitializeAllTargets();
  49     InitializeAllTargetMCs();
  50   }
  51
  52   void SetUp() override {
  53     Triple TargetTriple("x86_64-unknown-linux-gnu");
  54     std::string Error;
  55     const Target *T = TargetRegistry::lookupTarget("", TargetTriple, Error);
  56     if (!T)
  57       GTEST_SKIP();
  58     TargetOptions Options;
  59     TM = std::unique_ptr<TargetMachine>(
  60         T->createTargetMachine("X86", "", "", Options, std::nullopt));
  61     if (!TM)
  62       GTEST_SKIP();
  63     MMI = std::make_unique<MachineModuleInfo>(TM.get());
  64
  65     PassBuilder PB(TM.get());
  66     PB.registerModuleAnalyses(MAM);
  67     PB.registerCGSCCAnalyses(CGAM);
  68     PB.registerFunctionAnalyses(FAM);
  69     PB.registerLoopAnalyses(LAM);
  70     PB.registerMachineFunctionAnalyses(MFAM);
  71     PB.crossRegisterProxies(LAM, FAM, CGAM, MAM, &MFAM);
  72     MAM.registerPass([&] { return MachineModuleAnalysis(*MMI); });
  73   }
  74
  75   bool parseMIR(StringRef MIRCode) {
  76     SMDiagnostic Diagnostic;
  77     std::unique_ptr<MemoryBuffer> MBuffer = MemoryBuffer::getMemBuffer(MIRCode);
  78     MIR = createMIRParser(std::move(MBuffer), Context);
  79     if (!MIR)
  80       return false;
  81
  82     M = MIR->parseIRModule();
  83     M->setDataLayout(TM->createDataLayout());
  84
  85     if (MIR->parseMachineFunctions(*M, MAM)) {
  86       M.reset();
  87       return false;
  88     }
  89
  90     return true;
  91   }
  92 };
  93
  94 TEST_F(MachineDomTreeUpdaterTest, EagerUpdateBasicOperations) {
  95   StringRef MIRString = R"(
  96 --- |
  97   define i64 @f0(i64 %i, ptr %p) {
  98   bb0:
  99     store i64 %i, ptr %p, align 4
 100     switch i64 %i, label %bb1 [
 101       i64 1, label %bb2
 102       i64 2, label %bb3
 103     ]
 104   bb1:                                              ; preds = %bb0
 105     ret i64 1
 106   bb2:                                              ; preds = %bb0
 107     ret i64 2
 108   bb3:                                              ; preds = %bb0
 109     ret i64 3
 110   }
 111 ...
 112 ---
 113 name:            f0
 114 body:             |
 115   bb.0.bb0:
 116     successors: %bb.2, %bb.4
 117     liveins: $rdi, $rsi
 118
 119     %1:gr32 = COPY $rsi
 120     %0:gr64 = COPY $rdi
 121     MOV64mr %1, 1, $noreg, 0, $noreg, %0 :: (store (s64) into %ir.p)
 122     %2:gr64 = SUB64ri32 %0, 1, implicit-def $eflags
 123     JCC_1 %bb.2, 4, implicit $eflags
 124     JMP_1 %bb.4
 125
 126   bb.4.bb0:
 127     successors: %bb.3, %bb.1
 128
 129     %3:gr64 = SUB64ri32 %0, 2, implicit-def $eflags
 130     JCC_1 %bb.3, 4, implicit $eflags
 131     JMP_1 %bb.1
 132
 133   bb.1.bb1:
 134     %6:gr64 = MOV32ri64 1
 135     $rax = COPY %6
 136     RET 0, $rax
 137
 138   bb.2.bb2:
 139     %5:gr64 = MOV32ri64 2
 140     $rax = COPY %5
 141     RET 0, $rax
 142
 143   bb.3.bb3:
 144     %4:gr64 = MOV32ri64 3
 145     $rax = COPY %4
 146     RET 0, $rax
 147
 148 ...
 149 )";
 150
 151   ASSERT_TRUE(parseMIR(MIRString));
 152
 153   auto &MF =
 154       FAM.getResult<MachineFunctionAnalysis>(*M->getFunction("f0")).getMF();
 155
 156   MachineDominatorTree DT(MF);
 157   MachinePostDominatorTree PDT(MF);
 158   MachineDomTreeUpdater DTU(DT, PDT,
 159                             MachineDomTreeUpdater::UpdateStrategy::Eager);
 160
 161   ASSERT_TRUE(DTU.hasDomTree());
 162   ASSERT_TRUE(DTU.hasPostDomTree());
 163   ASSERT_TRUE(DTU.isEager());
 164   ASSERT_FALSE(DTU.isLazy());
 165   ASSERT_TRUE(DTU.getDomTree().verify());
 166   ASSERT_TRUE(DTU.getPostDomTree().verify());
 167   ASSERT_FALSE(DTU.hasPendingUpdates());
 168
 169   auto B = MF.begin();
 170   [[maybe_unused]] auto BB0 = B;
 171   auto BB1 = ++B;
 172   auto BB2 = ++B;
 173   [[maybe_unused]] auto BB3 = ++B;
 174   auto BB4 = ++B;
 175   EXPECT_EQ(BB1->succ_size(), 2u);
 176   ASSERT_TRUE(DT.dominates(&*BB1, &*BB2));
 177   ASSERT_TRUE(DT.dominates(&*BB1, &*BB4));
 178   BB1->removeSuccessor(&*BB4);
 179   DTU.deleteBB(&*BB4);
 180   EXPECT_EQ(BB1->succ_size(), 1u);
 181   ASSERT_TRUE(DT.dominates(&*BB1, &*BB2));
 182 }
 183
 184 TEST_F(MachineDomTreeUpdaterTest, LazyUpdateBasicOperations) {
 185   StringRef MIRString = R"(
 186 --- |
 187   define i64 @f0(i64 %i, ptr %p) {
 188   bb0:
 189     store i64 %i, ptr %p, align 4
 190     switch i64 %i, label %bb1 [
 191       i64 1, label %bb2
 192       i64 2, label %bb3
 193     ]
 194   bb1:                                              ; preds = %bb0
 195     ret i64 1
 196   bb2:                                              ; preds = %bb0
 197     ret i64 2
 198   bb3:                                              ; preds = %bb0
 199     ret i64 3
 200   }
 201 ...
 202 ---
 203 name:            f0
 204 body:             |
 205   bb.0.bb0:
 206     successors: %bb.2, %bb.4
 207     liveins: $rdi, $rsi
 208
 209     %1:gr32 = COPY $rsi
 210     %0:gr64 = COPY $rdi
 211     MOV64mr %1, 1, $noreg, 0, $noreg, %0 :: (store (s64) into %ir.p)
 212     %2:gr64 = SUB64ri32 %0, 1, implicit-def $eflags
 213     JCC_1 %bb.2, 4, implicit $eflags
 214     JMP_1 %bb.4
 215
 216   bb.4.bb0:
 217     successors: %bb.3, %bb.1
 218
 219     %3:gr64 = SUB64ri32 %0, 2, implicit-def $eflags
 220     JCC_1 %bb.3, 4, implicit $eflags
 221     JMP_1 %bb.1
 222
 223   bb.1.bb1:
 224     %6:gr64 = MOV32ri64 1
 225     $rax = COPY %6
 226     RET 0, $rax
 227
 228   bb.2.bb2:
 229     %5:gr64 = MOV32ri64 2
 230     $rax = COPY %5
 231     RET 0, $rax
 232
 233   bb.3.bb3:
 234     %4:gr64 = MOV32ri64 3
 235     $rax = COPY %4
 236     RET 0, $rax
 237
 238 ...
 239 )";
 240
 241   ASSERT_TRUE(parseMIR(MIRString));
 242
 243   auto &MF =
 244       FAM.getResult<MachineFunctionAnalysis>(*M->getFunction("f0")).getMF();
 245
 246   MachineDominatorTree DT(MF);
 247   MachinePostDominatorTree PDT(MF);
 248   MachineDomTreeUpdater DTU(DT, PDT,
 249                             MachineDomTreeUpdater::UpdateStrategy::Lazy);
 250
 251   ASSERT_TRUE(DTU.hasDomTree());
 252   ASSERT_TRUE(DTU.hasPostDomTree());
 253   ASSERT_FALSE(DTU.isEager());
 254   ASSERT_TRUE(DTU.isLazy());
 255   ASSERT_TRUE(DTU.getDomTree().verify());
 256   ASSERT_TRUE(DTU.getPostDomTree().verify());
 257   ASSERT_FALSE(DTU.hasPendingUpdates());
 258
 259   auto B = MF.begin();
 260   [[maybe_unused]] auto BB0 = B;
 261   auto BB1 = ++B;
 262   auto BB2 = ++B;
 263   [[maybe_unused]] auto BB3 = ++B;
 264   auto BB4 = ++B;
 265   EXPECT_EQ(BB1->succ_size(), 2u);
 266   ASSERT_TRUE(DT.dominates(&*BB1, &*BB2));
 267   ASSERT_TRUE(DT.dominates(&*BB1, &*BB4));
 268   BB1->removeSuccessor(&*BB4);
 269   DTU.deleteBB(&*BB4);
 270   ASSERT_TRUE(DTU.hasPendingDeletedBB());
 271   EXPECT_EQ(BB1->succ_size(), 1u);
 272   ASSERT_TRUE(DT.dominates(&*BB1, &*BB2));
 273   ASSERT_NE(DT.getNode(&*BB4), nullptr);
 274   DTU.flush();
 275 }