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/MC/TargetRegistry.h" 20 #include "llvm/Passes/PassBuilder.h" 21 #include "llvm/Support/SourceMgr.h" 22 #include "llvm/Support/TargetSelect.h" 23 #include "llvm/Target/TargetMachine.h" 24 #include "gtest/gtest.h" 25 26 using namespace llvm; 27 28 class MachineDomTreeUpdaterTest : public testing::Test { 29 public: 30 LLVMContext Context; 31 std::unique_ptr<TargetMachine> TM; 32 std::unique_ptr<Module> M; 33 std::unique_ptr<MachineModuleInfo> MMI; 34 std::unique_ptr<MIRParser> MIR; 35 36 LoopAnalysisManager LAM; 37 MachineFunctionAnalysisManager MFAM; 38 FunctionAnalysisManager FAM; 39 CGSCCAnalysisManager CGAM; 40 ModuleAnalysisManager MAM; 41 42 ModulePassManager MPM; 43 FunctionPassManager FPM; 44 MachineFunctionPassManager MFPM; 45 46 static void SetUpTestCase() { 47 InitializeAllTargets(); 48 InitializeAllTargetMCs(); 49 } 50 51 void SetUp() override { 52 Triple TargetTriple("x86_64-unknown-linux-gnu"); 53 std::string Error; 54 const Target *T = TargetRegistry::lookupTarget("", TargetTriple, Error); 55 if (!T) 56 GTEST_SKIP(); 57 TargetOptions Options; 58 TM = std::unique_ptr<TargetMachine>( 59 T->createTargetMachine("X86", "", "", Options, std::nullopt)); 60 if (!TM) 61 GTEST_SKIP(); 62 MMI = std::make_unique<MachineModuleInfo>( 63 static_cast<LLVMTargetMachine *>(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, const char *FnName) { 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, "f0")); 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 ASSERT_EQ(DT.getNode(&*BB4), nullptr); 183 } 184 185 TEST_F(MachineDomTreeUpdaterTest, LazyUpdateBasicOperations) { 186 StringRef MIRString = R"( 187 --- | 188 define i64 @f0(i64 %i, ptr %p) { 189 bb0: 190 store i64 %i, ptr %p, align 4 191 switch i64 %i, label %bb1 [ 192 i64 1, label %bb2 193 i64 2, label %bb3 194 ] 195 bb1: ; preds = %bb0 196 ret i64 1 197 bb2: ; preds = %bb0 198 ret i64 2 199 bb3: ; preds = %bb0 200 ret i64 3 201 } 202 ... 203 --- 204 name: f0 205 body: | 206 bb.0.bb0: 207 successors: %bb.2, %bb.4 208 liveins: $rdi, $rsi 209 210 %1:gr32 = COPY $rsi 211 %0:gr64 = COPY $rdi 212 MOV64mr %1, 1, $noreg, 0, $noreg, %0 :: (store (s64) into %ir.p) 213 %2:gr64 = SUB64ri32 %0, 1, implicit-def $eflags 214 JCC_1 %bb.2, 4, implicit $eflags 215 JMP_1 %bb.4 216 217 bb.4.bb0: 218 successors: %bb.3, %bb.1 219 220 %3:gr64 = SUB64ri32 %0, 2, implicit-def $eflags 221 JCC_1 %bb.3, 4, implicit $eflags 222 JMP_1 %bb.1 223 224 bb.1.bb1: 225 %6:gr64 = MOV32ri64 1 226 $rax = COPY %6 227 RET 0, $rax 228 229 bb.2.bb2: 230 %5:gr64 = MOV32ri64 2 231 $rax = COPY %5 232 RET 0, $rax 233 234 bb.3.bb3: 235 %4:gr64 = MOV32ri64 3 236 $rax = COPY %4 237 RET 0, $rax 238 239 ... 240 )"; 241 242 ASSERT_TRUE(parseMIR(MIRString, "f0")); 243 244 auto &MF = 245 FAM.getResult<MachineFunctionAnalysis>(*M->getFunction("f0")).getMF(); 246 247 MachineDominatorTree DT(MF); 248 MachinePostDominatorTree PDT(MF); 249 MachineDomTreeUpdater DTU(DT, PDT, 250 MachineDomTreeUpdater::UpdateStrategy::Lazy); 251 252 ASSERT_TRUE(DTU.hasDomTree()); 253 ASSERT_TRUE(DTU.hasPostDomTree()); 254 ASSERT_FALSE(DTU.isEager()); 255 ASSERT_TRUE(DTU.isLazy()); 256 ASSERT_TRUE(DTU.getDomTree().verify()); 257 ASSERT_TRUE(DTU.getPostDomTree().verify()); 258 ASSERT_FALSE(DTU.hasPendingUpdates()); 259 260 auto B = MF.begin(); 261 [[maybe_unused]] auto BB0 = B; 262 auto BB1 = ++B; 263 auto BB2 = ++B; 264 [[maybe_unused]] auto BB3 = ++B; 265 auto BB4 = ++B; 266 EXPECT_EQ(BB1->succ_size(), 2u); 267 ASSERT_TRUE(DT.dominates(&*BB1, &*BB2)); 268 ASSERT_TRUE(DT.dominates(&*BB1, &*BB4)); 269 BB1->removeSuccessor(&*BB4); 270 DTU.deleteBB(&*BB4); 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 ASSERT_EQ(DT.getNode(&*BB4), nullptr); 276 } 277