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 } 276