1 //===- DependencyGraphTest.cpp --------------------------------------------===// 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/Vectorize/SandboxVectorizer/DependencyGraph.h" 10 #include "llvm/AsmParser/Parser.h" 11 #include "llvm/SandboxIR/Context.h" 12 #include "llvm/SandboxIR/Function.h" 13 #include "llvm/SandboxIR/Instruction.h" 14 #include "llvm/Support/SourceMgr.h" 15 #include "gmock/gmock-matchers.h" 16 #include "gtest/gtest.h" 17 18 using namespace llvm; 19 20 struct DependencyGraphTest : public testing::Test { 21 LLVMContext C; 22 std::unique_ptr<Module> M; 23 24 void parseIR(LLVMContext &C, const char *IR) { 25 SMDiagnostic Err; 26 M = parseAssemblyString(IR, Err, C); 27 if (!M) 28 Err.print("DependencyGraphTest", errs()); 29 } 30 }; 31 32 TEST_F(DependencyGraphTest, isStackSaveOrRestoreIntrinsic) { 33 parseIR(C, R"IR( 34 declare void @llvm.sideeffect() 35 define void @foo(i8 %v1, ptr %ptr) { 36 %add = add i8 %v1, %v1 37 %stacksave = call ptr @llvm.stacksave() 38 call void @llvm.stackrestore(ptr %stacksave) 39 call void @llvm.sideeffect() 40 ret void 41 } 42 )IR"); 43 llvm::Function *LLVMF = &*M->getFunction("foo"); 44 sandboxir::Context Ctx(C); 45 sandboxir::Function *F = Ctx.createFunction(LLVMF); 46 auto *BB = &*F->begin(); 47 auto It = BB->begin(); 48 auto *Add = cast<sandboxir::BinaryOperator>(&*It++); 49 auto *StackSave = cast<sandboxir::CallInst>(&*It++); 50 auto *StackRestore = cast<sandboxir::CallInst>(&*It++); 51 auto *Other = cast<sandboxir::CallInst>(&*It++); 52 auto *Ret = cast<sandboxir::ReturnInst>(&*It++); 53 54 using DGNode = sandboxir::DGNode; 55 EXPECT_FALSE(DGNode::isStackSaveOrRestoreIntrinsic(Add)); 56 EXPECT_TRUE(DGNode::isStackSaveOrRestoreIntrinsic(StackSave)); 57 EXPECT_TRUE(DGNode::isStackSaveOrRestoreIntrinsic(StackRestore)); 58 EXPECT_FALSE(DGNode::isStackSaveOrRestoreIntrinsic(Other)); 59 EXPECT_FALSE(DGNode::isStackSaveOrRestoreIntrinsic(Ret)); 60 } 61 62 TEST_F(DependencyGraphTest, Instruction_isMemDepCandidate) { 63 parseIR(C, R"IR( 64 declare void @llvm.fake.use(...) 65 declare void @llvm.sideeffect() 66 declare void @llvm.pseudoprobe(i64, i64, i32, i64) 67 declare void @bar() 68 define void @foo(i8 %v1, ptr %ptr) { 69 %add0 = add i8 %v1, %v1 70 %ld0 = load i8, ptr %ptr 71 store i8 %v1, ptr %ptr 72 call void @llvm.sideeffect() 73 call void @llvm.pseudoprobe(i64 42, i64 1, i32 0, i64 -1) 74 call void @llvm.fake.use(ptr %ptr) 75 call void @bar() 76 ret void 77 } 78 )IR"); 79 llvm::Function *LLVMF = &*M->getFunction("foo"); 80 sandboxir::Context Ctx(C); 81 sandboxir::Function *F = Ctx.createFunction(LLVMF); 82 auto *BB = &*F->begin(); 83 auto It = BB->begin(); 84 auto *Add0 = cast<sandboxir::BinaryOperator>(&*It++); 85 auto *Ld0 = cast<sandboxir::LoadInst>(&*It++); 86 auto *St0 = cast<sandboxir::StoreInst>(&*It++); 87 auto *SideEffect0 = cast<sandboxir::CallInst>(&*It++); 88 auto *PseudoProbe0 = cast<sandboxir::CallInst>(&*It++); 89 auto *OtherIntrinsic0 = cast<sandboxir::CallInst>(&*It++); 90 auto *CallBar = cast<sandboxir::CallInst>(&*It++); 91 auto *Ret = cast<sandboxir::ReturnInst>(&*It++); 92 93 using DGNode = sandboxir::DGNode; 94 95 EXPECT_FALSE(DGNode::isMemDepCandidate(Add0)); 96 EXPECT_TRUE(DGNode::isMemDepCandidate(Ld0)); 97 EXPECT_TRUE(DGNode::isMemDepCandidate(St0)); 98 EXPECT_FALSE(DGNode::isMemDepCandidate(SideEffect0)); 99 EXPECT_FALSE(DGNode::isMemDepCandidate(PseudoProbe0)); 100 EXPECT_TRUE(DGNode::isMemDepCandidate(OtherIntrinsic0)); 101 EXPECT_TRUE(DGNode::isMemDepCandidate(CallBar)); 102 EXPECT_FALSE(DGNode::isMemDepCandidate(Ret)); 103 } 104 105 TEST_F(DependencyGraphTest, Instruction_isMemIntrinsic) { 106 parseIR(C, R"IR( 107 declare void @llvm.sideeffect() 108 declare void @llvm.pseudoprobe(i64) 109 declare void @llvm.assume(i1) 110 111 define void @foo(ptr %ptr, i1 %cond) { 112 call void @llvm.sideeffect() 113 call void @llvm.pseudoprobe(i64 42) 114 call void @llvm.assume(i1 %cond) 115 ret void 116 } 117 )IR"); 118 llvm::Function *LLVMF = &*M->getFunction("foo"); 119 sandboxir::Context Ctx(C); 120 sandboxir::Function *F = Ctx.createFunction(LLVMF); 121 auto *BB = &*F->begin(); 122 auto It = BB->begin(); 123 auto *SideEffect = cast<sandboxir::IntrinsicInst>(&*It++); 124 auto *PseudoProbe = cast<sandboxir::IntrinsicInst>(&*It++); 125 auto *OtherIntrinsic = cast<sandboxir::IntrinsicInst>(&*It++); 126 127 using DGNode = sandboxir::DGNode; 128 EXPECT_FALSE(DGNode::isMemIntrinsic(SideEffect)); 129 EXPECT_FALSE(DGNode::isMemIntrinsic(PseudoProbe)); 130 EXPECT_TRUE(DGNode::isMemIntrinsic(OtherIntrinsic)); 131 } 132 133 TEST_F(DependencyGraphTest, MemDGNode) { 134 parseIR(C, R"IR( 135 declare void @llvm.sideeffect() 136 declare void @llvm.pseudoprobe(i64, i64, i32, i64) 137 declare void @llvm.fake.use(...) 138 declare void @bar() 139 define void @foo(i8 %v1, ptr %ptr) { 140 store i8 %v1, ptr %ptr 141 %ld0 = load i8, ptr %ptr 142 %add = add i8 %v1, %v1 143 %stacksave = call ptr @llvm.stacksave() 144 call void @llvm.stackrestore(ptr %stacksave) 145 call void @llvm.sideeffect() 146 call void @llvm.pseudoprobe(i64 42, i64 1, i32 0, i64 -1) 147 call void @llvm.fake.use(ptr %ptr) 148 call void @bar() 149 ret void 150 } 151 )IR"); 152 llvm::Function *LLVMF = &*M->getFunction("foo"); 153 sandboxir::Context Ctx(C); 154 auto *F = Ctx.createFunction(LLVMF); 155 auto *BB = &*F->begin(); 156 auto It = BB->begin(); 157 auto *Store = cast<sandboxir::StoreInst>(&*It++); 158 auto *Load = cast<sandboxir::LoadInst>(&*It++); 159 auto *Add = cast<sandboxir::BinaryOperator>(&*It++); 160 auto *StackSave = cast<sandboxir::CallInst>(&*It++); 161 auto *StackRestore = cast<sandboxir::CallInst>(&*It++); 162 auto *SideEffect = cast<sandboxir::CallInst>(&*It++); 163 auto *PseudoProbe = cast<sandboxir::CallInst>(&*It++); 164 auto *FakeUse = cast<sandboxir::CallInst>(&*It++); 165 auto *Call = cast<sandboxir::CallInst>(&*It++); 166 auto *Ret = cast<sandboxir::ReturnInst>(&*It++); 167 168 sandboxir::DependencyGraph DAG; 169 DAG.extend({&*BB->begin(), BB->getTerminator()}); 170 EXPECT_TRUE(isa<llvm::sandboxir::MemDGNode>(DAG.getNode(Store))); 171 EXPECT_TRUE(isa<llvm::sandboxir::MemDGNode>(DAG.getNode(Load))); 172 EXPECT_FALSE(isa<llvm::sandboxir::MemDGNode>(DAG.getNode(Add))); 173 EXPECT_TRUE(isa<llvm::sandboxir::MemDGNode>(DAG.getNode(StackSave))); 174 EXPECT_TRUE(isa<llvm::sandboxir::MemDGNode>(DAG.getNode(StackRestore))); 175 EXPECT_FALSE(isa<llvm::sandboxir::MemDGNode>(DAG.getNode(SideEffect))); 176 EXPECT_FALSE(isa<llvm::sandboxir::MemDGNode>(DAG.getNode(PseudoProbe))); 177 EXPECT_TRUE(isa<llvm::sandboxir::MemDGNode>(DAG.getNode(FakeUse))); 178 EXPECT_TRUE(isa<llvm::sandboxir::MemDGNode>(DAG.getNode(Call))); 179 EXPECT_FALSE(isa<llvm::sandboxir::MemDGNode>(DAG.getNode(Ret))); 180 } 181 182 TEST_F(DependencyGraphTest, Basic) { 183 parseIR(C, R"IR( 184 define void @foo(ptr %ptr, i8 %v0, i8 %v1) { 185 store i8 %v0, ptr %ptr 186 store i8 %v1, ptr %ptr 187 ret void 188 } 189 )IR"); 190 llvm::Function *LLVMF = &*M->getFunction("foo"); 191 sandboxir::Context Ctx(C); 192 auto *F = Ctx.createFunction(LLVMF); 193 auto *BB = &*F->begin(); 194 auto It = BB->begin(); 195 auto *S0 = cast<sandboxir::StoreInst>(&*It++); 196 auto *S1 = cast<sandboxir::StoreInst>(&*It++); 197 auto *Ret = cast<sandboxir::ReturnInst>(&*It++); 198 sandboxir::DependencyGraph DAG; 199 auto Span = DAG.extend({&*BB->begin(), BB->getTerminator()}); 200 // Check extend(). 201 EXPECT_EQ(Span.top(), &*BB->begin()); 202 EXPECT_EQ(Span.bottom(), BB->getTerminator()); 203 204 sandboxir::DGNode *N0 = DAG.getNode(S0); 205 sandboxir::DGNode *N1 = DAG.getNode(S1); 206 sandboxir::DGNode *N2 = DAG.getNode(Ret); 207 // Check getInstruction(). 208 EXPECT_EQ(N0->getInstruction(), S0); 209 EXPECT_EQ(N1->getInstruction(), S1); 210 // Check hasMemPred() 211 EXPECT_TRUE(N1->hasMemPred(N0)); 212 EXPECT_FALSE(N0->hasMemPred(N1)); 213 214 // Check memPreds(). 215 EXPECT_TRUE(N0->memPreds().empty()); 216 EXPECT_THAT(N1->memPreds(), testing::ElementsAre(N0)); 217 EXPECT_THAT(N2->memPreds(), testing::ElementsAre(N1)); 218 } 219 220 TEST_F(DependencyGraphTest, MemDGNode_getPrevNode_getNextNode) { 221 parseIR(C, R"IR( 222 define void @foo(ptr %ptr, i8 %v0, i8 %v1) { 223 store i8 %v0, ptr %ptr 224 add i8 %v0, %v0 225 store i8 %v1, ptr %ptr 226 ret void 227 } 228 )IR"); 229 llvm::Function *LLVMF = &*M->getFunction("foo"); 230 sandboxir::Context Ctx(C); 231 auto *F = Ctx.createFunction(LLVMF); 232 auto *BB = &*F->begin(); 233 auto It = BB->begin(); 234 auto *S0 = cast<sandboxir::StoreInst>(&*It++); 235 [[maybe_unused]] auto *Add = cast<sandboxir::BinaryOperator>(&*It++); 236 auto *S1 = cast<sandboxir::StoreInst>(&*It++); 237 [[maybe_unused]] auto *Ret = cast<sandboxir::ReturnInst>(&*It++); 238 239 sandboxir::DependencyGraph DAG; 240 DAG.extend({&*BB->begin(), BB->getTerminator()}); 241 242 auto *S0N = cast<sandboxir::MemDGNode>(DAG.getNode(S0)); 243 auto *S1N = cast<sandboxir::MemDGNode>(DAG.getNode(S1)); 244 245 EXPECT_EQ(S0N->getPrevNode(), nullptr); 246 EXPECT_EQ(S0N->getNextNode(), S1N); 247 248 EXPECT_EQ(S1N->getPrevNode(), S0N); 249 EXPECT_EQ(S1N->getNextNode(), nullptr); 250 } 251 252 TEST_F(DependencyGraphTest, DGNodeRange) { 253 parseIR(C, R"IR( 254 define void @foo(ptr %ptr, i8 %v0, i8 %v1) { 255 add i8 %v0, %v0 256 store i8 %v0, ptr %ptr 257 add i8 %v0, %v0 258 store i8 %v1, ptr %ptr 259 ret void 260 } 261 )IR"); 262 llvm::Function *LLVMF = &*M->getFunction("foo"); 263 sandboxir::Context Ctx(C); 264 auto *F = Ctx.createFunction(LLVMF); 265 auto *BB = &*F->begin(); 266 auto It = BB->begin(); 267 auto *Add0 = cast<sandboxir::BinaryOperator>(&*It++); 268 auto *S0 = cast<sandboxir::StoreInst>(&*It++); 269 auto *Add1 = cast<sandboxir::BinaryOperator>(&*It++); 270 auto *S1 = cast<sandboxir::StoreInst>(&*It++); 271 auto *Ret = cast<sandboxir::ReturnInst>(&*It++); 272 273 sandboxir::DependencyGraph DAG; 274 DAG.extend({&*BB->begin(), BB->getTerminator()}); 275 276 auto *S0N = cast<sandboxir::MemDGNode>(DAG.getNode(S0)); 277 auto *S1N = cast<sandboxir::MemDGNode>(DAG.getNode(S1)); 278 279 // Check empty range. 280 EXPECT_THAT(sandboxir::MemDGNodeIntervalBuilder::makeEmpty(), 281 testing::ElementsAre()); 282 283 // Returns the pointers in Range. 284 auto getPtrVec = [](const auto &Range) { 285 SmallVector<const sandboxir::DGNode *> Vec; 286 for (const sandboxir::DGNode &N : Range) 287 Vec.push_back(&N); 288 return Vec; 289 }; 290 // Both TopN and BotN are memory. 291 EXPECT_THAT( 292 getPtrVec(sandboxir::MemDGNodeIntervalBuilder::make({S0, S1}, DAG)), 293 testing::ElementsAre(S0N, S1N)); 294 // Only TopN is memory. 295 EXPECT_THAT( 296 getPtrVec(sandboxir::MemDGNodeIntervalBuilder::make({S0, Ret}, DAG)), 297 testing::ElementsAre(S0N, S1N)); 298 EXPECT_THAT( 299 getPtrVec(sandboxir::MemDGNodeIntervalBuilder::make({S0, Add1}, DAG)), 300 testing::ElementsAre(S0N)); 301 // Only BotN is memory. 302 EXPECT_THAT( 303 getPtrVec(sandboxir::MemDGNodeIntervalBuilder::make({Add0, S1}, DAG)), 304 testing::ElementsAre(S0N, S1N)); 305 EXPECT_THAT( 306 getPtrVec(sandboxir::MemDGNodeIntervalBuilder::make({Add0, S0}, DAG)), 307 testing::ElementsAre(S0N)); 308 // Neither TopN or BotN is memory. 309 EXPECT_THAT( 310 getPtrVec(sandboxir::MemDGNodeIntervalBuilder::make({Add0, Ret}, DAG)), 311 testing::ElementsAre(S0N, S1N)); 312 EXPECT_THAT( 313 getPtrVec(sandboxir::MemDGNodeIntervalBuilder::make({Add0, Add0}, DAG)), 314 testing::ElementsAre()); 315 } 316