xref: /llvm-project/llvm/unittests/Transforms/Vectorize/SandboxVectorizer/DependencyGraphTest.cpp (revision fc08ad6610c66856f48559e543eb7be317e908e7) 
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/Analysis/AliasAnalysis.h"
11 #include "llvm/Analysis/AssumptionCache.h"
12 #include "llvm/Analysis/BasicAliasAnalysis.h"
13 #include "llvm/Analysis/TargetLibraryInfo.h"
14 #include "llvm/AsmParser/Parser.h"
15 #include "llvm/IR/DataLayout.h"
16 #include "llvm/IR/Dominators.h"
17 #include "llvm/SandboxIR/Context.h"
18 #include "llvm/SandboxIR/Function.h"
19 #include "llvm/SandboxIR/Instruction.h"
20 #include "llvm/Support/SourceMgr.h"
21 #include "gmock/gmock-matchers.h"
22 #include "gtest/gtest.h"
23 
24 using namespace llvm;
25 
26 struct DependencyGraphTest : public testing::Test {
27   LLVMContext C;
28   std::unique_ptr<Module> M;
29   std::unique_ptr<AssumptionCache> AC;
30   std::unique_ptr<DominatorTree> DT;
31   std::unique_ptr<BasicAAResult> BAA;
32   std::unique_ptr<AAResults> AA;
33 
34   void parseIR(LLVMContext &C, const char *IR) {
35     SMDiagnostic Err;
36     M = parseAssemblyString(IR, Err, C);
37     if (!M)
38       Err.print("DependencyGraphTest", errs());
39   }
40 
41   AAResults &getAA(llvm::Function &LLVMF) {
42     TargetLibraryInfoImpl TLII;
43     TargetLibraryInfo TLI(TLII);
44     AA = std::make_unique<AAResults>(TLI);
45     AC = std::make_unique<AssumptionCache>(LLVMF);
46     DT = std::make_unique<DominatorTree>(LLVMF);
47     BAA = std::make_unique<BasicAAResult>(M->getDataLayout(), LLVMF, TLI, *AC,
48                                           DT.get());
49     AA->addAAResult(*BAA);
50     return *AA;
51   }
52   /// \Returns true if there is a dependency: SrcN->DstN.
53   bool memDependency(sandboxir::DGNode *SrcN, sandboxir::DGNode *DstN) {
54     if (auto *MemDstN = dyn_cast<sandboxir::MemDGNode>(DstN))
55       return MemDstN->hasMemPred(SrcN);
56     return false;
57   }
58 };
59 
60 TEST_F(DependencyGraphTest, isStackSaveOrRestoreIntrinsic) {
61   parseIR(C, R"IR(
62 declare void @llvm.sideeffect()
63 define void @foo(i8 %v1, ptr %ptr) {
64   %add = add i8 %v1, %v1
65   %stacksave = call ptr @llvm.stacksave()
66   call void @llvm.stackrestore(ptr %stacksave)
67   call void @llvm.sideeffect()
68   ret void
69 }
70 )IR");
71   llvm::Function *LLVMF = &*M->getFunction("foo");
72   sandboxir::Context Ctx(C);
73   sandboxir::Function *F = Ctx.createFunction(LLVMF);
74   auto *BB = &*F->begin();
75   auto It = BB->begin();
76   auto *Add = cast<sandboxir::BinaryOperator>(&*It++);
77   auto *StackSave = cast<sandboxir::CallInst>(&*It++);
78   auto *StackRestore = cast<sandboxir::CallInst>(&*It++);
79   auto *Other = cast<sandboxir::CallInst>(&*It++);
80   auto *Ret = cast<sandboxir::ReturnInst>(&*It++);
81 
82   using DGNode = sandboxir::DGNode;
83   EXPECT_FALSE(DGNode::isStackSaveOrRestoreIntrinsic(Add));
84   EXPECT_TRUE(DGNode::isStackSaveOrRestoreIntrinsic(StackSave));
85   EXPECT_TRUE(DGNode::isStackSaveOrRestoreIntrinsic(StackRestore));
86   EXPECT_FALSE(DGNode::isStackSaveOrRestoreIntrinsic(Other));
87   EXPECT_FALSE(DGNode::isStackSaveOrRestoreIntrinsic(Ret));
88 }
89 
90 TEST_F(DependencyGraphTest, Instruction_isMemDepCandidate) {
91   parseIR(C, R"IR(
92 declare void @llvm.fake.use(...)
93 declare void @llvm.sideeffect()
94 declare void @llvm.pseudoprobe(i64, i64, i32, i64)
95 declare void @bar()
96 define void @foo(i8 %v1, ptr %ptr) {
97   %add0 = add i8 %v1, %v1
98   %ld0 = load i8, ptr %ptr
99   store i8 %v1, ptr %ptr
100   call void @llvm.sideeffect()
101   call void @llvm.pseudoprobe(i64 42, i64 1, i32 0, i64 -1)
102   call void @llvm.fake.use(ptr %ptr)
103   call void @bar()
104   ret void
105 }
106 )IR");
107   llvm::Function *LLVMF = &*M->getFunction("foo");
108   sandboxir::Context Ctx(C);
109   sandboxir::Function *F = Ctx.createFunction(LLVMF);
110   auto *BB = &*F->begin();
111   auto It = BB->begin();
112   auto *Add0 = cast<sandboxir::BinaryOperator>(&*It++);
113   auto *Ld0 = cast<sandboxir::LoadInst>(&*It++);
114   auto *St0 = cast<sandboxir::StoreInst>(&*It++);
115   auto *SideEffect0 = cast<sandboxir::CallInst>(&*It++);
116   auto *PseudoProbe0 = cast<sandboxir::CallInst>(&*It++);
117   auto *OtherIntrinsic0 = cast<sandboxir::CallInst>(&*It++);
118   auto *CallBar = cast<sandboxir::CallInst>(&*It++);
119   auto *Ret = cast<sandboxir::ReturnInst>(&*It++);
120 
121   using DGNode = sandboxir::DGNode;
122 
123   EXPECT_FALSE(DGNode::isMemDepCandidate(Add0));
124   EXPECT_TRUE(DGNode::isMemDepCandidate(Ld0));
125   EXPECT_TRUE(DGNode::isMemDepCandidate(St0));
126   EXPECT_FALSE(DGNode::isMemDepCandidate(SideEffect0));
127   EXPECT_FALSE(DGNode::isMemDepCandidate(PseudoProbe0));
128   EXPECT_TRUE(DGNode::isMemDepCandidate(OtherIntrinsic0));
129   EXPECT_TRUE(DGNode::isMemDepCandidate(CallBar));
130   EXPECT_FALSE(DGNode::isMemDepCandidate(Ret));
131 }
132 
133 TEST_F(DependencyGraphTest, Instruction_isMemIntrinsic) {
134   parseIR(C, R"IR(
135 declare void @llvm.sideeffect()
136 declare void @llvm.pseudoprobe(i64)
137 declare void @llvm.assume(i1)
138 
139 define void @foo(ptr %ptr, i1 %cond) {
140   call void @llvm.sideeffect()
141   call void @llvm.pseudoprobe(i64 42)
142   call void @llvm.assume(i1 %cond)
143   ret void
144 }
145 )IR");
146   llvm::Function *LLVMF = &*M->getFunction("foo");
147   sandboxir::Context Ctx(C);
148   sandboxir::Function *F = Ctx.createFunction(LLVMF);
149   auto *BB = &*F->begin();
150   auto It = BB->begin();
151   auto *SideEffect = cast<sandboxir::IntrinsicInst>(&*It++);
152   auto *PseudoProbe = cast<sandboxir::IntrinsicInst>(&*It++);
153   auto *OtherIntrinsic = cast<sandboxir::IntrinsicInst>(&*It++);
154 
155   using DGNode = sandboxir::DGNode;
156   EXPECT_FALSE(DGNode::isMemIntrinsic(SideEffect));
157   EXPECT_FALSE(DGNode::isMemIntrinsic(PseudoProbe));
158   EXPECT_TRUE(DGNode::isMemIntrinsic(OtherIntrinsic));
159 }
160 
161 TEST_F(DependencyGraphTest, MemDGNode) {
162   parseIR(C, R"IR(
163 declare void @llvm.sideeffect()
164 declare void @llvm.pseudoprobe(i64, i64, i32, i64)
165 declare void @llvm.fake.use(...)
166 declare void @bar()
167 define void @foo(i8 %v1, ptr %ptr) {
168   store i8 %v1, ptr %ptr
169   %ld0 = load i8, ptr %ptr
170   %add = add i8 %v1, %v1
171   %stacksave = call ptr @llvm.stacksave()
172   call void @llvm.stackrestore(ptr %stacksave)
173   call void @llvm.sideeffect()
174   call void @llvm.pseudoprobe(i64 42, i64 1, i32 0, i64 -1)
175   call void @llvm.fake.use(ptr %ptr)
176   call void @bar()
177   ret void
178 }
179 )IR");
180   llvm::Function *LLVMF = &*M->getFunction("foo");
181   sandboxir::Context Ctx(C);
182 
183   auto *F = Ctx.createFunction(LLVMF);
184   auto *BB = &*F->begin();
185   auto It = BB->begin();
186   auto *Store = cast<sandboxir::StoreInst>(&*It++);
187   auto *Load = cast<sandboxir::LoadInst>(&*It++);
188   auto *Add = cast<sandboxir::BinaryOperator>(&*It++);
189   auto *StackSave = cast<sandboxir::CallInst>(&*It++);
190   auto *StackRestore = cast<sandboxir::CallInst>(&*It++);
191   auto *SideEffect = cast<sandboxir::CallInst>(&*It++);
192   auto *PseudoProbe = cast<sandboxir::CallInst>(&*It++);
193   auto *FakeUse = cast<sandboxir::CallInst>(&*It++);
194   auto *Call = cast<sandboxir::CallInst>(&*It++);
195   auto *Ret = cast<sandboxir::ReturnInst>(&*It++);
196 
197   sandboxir::DependencyGraph DAG(getAA(*LLVMF));
198   DAG.extend({&*BB->begin(), BB->getTerminator()});
199   EXPECT_TRUE(isa<llvm::sandboxir::MemDGNode>(DAG.getNode(Store)));
200   EXPECT_TRUE(isa<llvm::sandboxir::MemDGNode>(DAG.getNode(Load)));
201   EXPECT_FALSE(isa<llvm::sandboxir::MemDGNode>(DAG.getNode(Add)));
202   EXPECT_TRUE(isa<llvm::sandboxir::MemDGNode>(DAG.getNode(StackSave)));
203   EXPECT_TRUE(isa<llvm::sandboxir::MemDGNode>(DAG.getNode(StackRestore)));
204   EXPECT_FALSE(isa<llvm::sandboxir::MemDGNode>(DAG.getNode(SideEffect)));
205   EXPECT_FALSE(isa<llvm::sandboxir::MemDGNode>(DAG.getNode(PseudoProbe)));
206   EXPECT_TRUE(isa<llvm::sandboxir::MemDGNode>(DAG.getNode(FakeUse)));
207   EXPECT_TRUE(isa<llvm::sandboxir::MemDGNode>(DAG.getNode(Call)));
208   EXPECT_FALSE(isa<llvm::sandboxir::MemDGNode>(DAG.getNode(Ret)));
209 }
210 
211 TEST_F(DependencyGraphTest, Basic) {
212   parseIR(C, R"IR(
213 define void @foo(ptr %ptr, i8 %v0, i8 %v1) {
214   store i8 %v0, ptr %ptr
215   store i8 %v1, ptr %ptr
216   ret void
217 }
218 )IR");
219   llvm::Function *LLVMF = &*M->getFunction("foo");
220   sandboxir::Context Ctx(C);
221   auto *F = Ctx.createFunction(LLVMF);
222   auto *BB = &*F->begin();
223   auto It = BB->begin();
224   auto *S0 = cast<sandboxir::StoreInst>(&*It++);
225   auto *S1 = cast<sandboxir::StoreInst>(&*It++);
226   auto *Ret = cast<sandboxir::ReturnInst>(&*It++);
227   sandboxir::DependencyGraph DAG(getAA(*LLVMF));
228   auto Span = DAG.extend({&*BB->begin(), BB->getTerminator()});
229   // Check extend().
230   EXPECT_EQ(Span.top(), &*BB->begin());
231   EXPECT_EQ(Span.bottom(), BB->getTerminator());
232 
233   auto *N0 = cast<sandboxir::MemDGNode>(DAG.getNode(S0));
234   auto *N1 = cast<sandboxir::MemDGNode>(DAG.getNode(S1));
235   auto *N2 = DAG.getNode(Ret);
236 
237   // Check getInstruction().
238   EXPECT_EQ(N0->getInstruction(), S0);
239   EXPECT_EQ(N1->getInstruction(), S1);
240   // Check hasMemPred()
241   EXPECT_TRUE(N1->hasMemPred(N0));
242   EXPECT_FALSE(N0->hasMemPred(N1));
243 
244   // Check preds().
245   EXPECT_TRUE(N0->preds(DAG).empty());
246   EXPECT_THAT(N1->preds(DAG), testing::ElementsAre(N0));
247 
248   // Check memPreds().
249   EXPECT_TRUE(N0->memPreds().empty());
250   EXPECT_THAT(N1->memPreds(), testing::ElementsAre(N0));
251   EXPECT_TRUE(N2->preds(DAG).empty());
252 
253   // Check UnscheduledSuccs.
254   EXPECT_EQ(N0->getNumUnscheduledSuccs(), 1u); // N1
255   EXPECT_EQ(N1->getNumUnscheduledSuccs(), 0u);
256   EXPECT_EQ(N2->getNumUnscheduledSuccs(), 0u);
257 }
258 
259 TEST_F(DependencyGraphTest, Preds) {
260   parseIR(C, R"IR(
261 declare ptr @bar(i8)
262 define i8 @foo(i8 %v0, i8 %v1) {
263   %add0 = add i8 %v0, %v0
264   %add1 = add i8 %v1, %v1
265   %add2 = add i8 %add0, %add1
266   %ptr = call ptr @bar(i8 %add1)
267   store i8 %add2, ptr %ptr
268   ret i8 %add2
269 }
270 )IR");
271   llvm::Function *LLVMF = &*M->getFunction("foo");
272   sandboxir::Context Ctx(C);
273   auto *F = Ctx.createFunction(LLVMF);
274   auto *BB = &*F->begin();
275   auto It = BB->begin();
276   sandboxir::DependencyGraph DAG(getAA(*LLVMF));
277   DAG.extend({&*BB->begin(), BB->getTerminator()});
278 
279   auto *AddN0 = DAG.getNode(cast<sandboxir::BinaryOperator>(&*It++));
280   auto *AddN1 = DAG.getNode(cast<sandboxir::BinaryOperator>(&*It++));
281   auto *AddN2 = DAG.getNode(cast<sandboxir::BinaryOperator>(&*It++));
282   auto *CallN = DAG.getNode(cast<sandboxir::CallInst>(&*It++));
283   auto *StN = DAG.getNode(cast<sandboxir::StoreInst>(&*It++));
284   auto *RetN = DAG.getNode(cast<sandboxir::ReturnInst>(&*It++));
285 
286   // Check preds().
287   EXPECT_THAT(AddN0->preds(DAG), testing::ElementsAre());
288   EXPECT_THAT(AddN1->preds(DAG), testing::ElementsAre());
289   EXPECT_THAT(AddN2->preds(DAG), testing::ElementsAre(AddN0, AddN1));
290   EXPECT_THAT(CallN->preds(DAG), testing::ElementsAre(AddN1));
291   EXPECT_THAT(StN->preds(DAG),
292               testing::UnorderedElementsAre(CallN, CallN, AddN2));
293   EXPECT_THAT(RetN->preds(DAG), testing::ElementsAre(AddN2));
294 
295   // Check UnscheduledSuccs.
296   EXPECT_EQ(AddN0->getNumUnscheduledSuccs(), 1u); // AddN2
297   EXPECT_EQ(AddN1->getNumUnscheduledSuccs(), 2u); // AddN2, CallN
298   EXPECT_EQ(AddN2->getNumUnscheduledSuccs(), 2u); // StN, RetN
299   EXPECT_EQ(CallN->getNumUnscheduledSuccs(), 2u); // StN, StN
300   EXPECT_EQ(StN->getNumUnscheduledSuccs(), 0u);
301   EXPECT_EQ(RetN->getNumUnscheduledSuccs(), 0u);
302 }
303 
304 TEST_F(DependencyGraphTest, MemDGNode_getPrevNode_getNextNode) {
305   parseIR(C, R"IR(
306 define void @foo(ptr %ptr, i8 %v0, i8 %v1) {
307   store i8 %v0, ptr %ptr
308   add i8 %v0, %v0
309   store i8 %v1, ptr %ptr
310   ret void
311 }
312 )IR");
313   llvm::Function *LLVMF = &*M->getFunction("foo");
314   sandboxir::Context Ctx(C);
315   auto *F = Ctx.createFunction(LLVMF);
316   auto *BB = &*F->begin();
317   auto It = BB->begin();
318   auto *S0 = cast<sandboxir::StoreInst>(&*It++);
319   [[maybe_unused]] auto *Add = cast<sandboxir::BinaryOperator>(&*It++);
320   auto *S1 = cast<sandboxir::StoreInst>(&*It++);
321   [[maybe_unused]] auto *Ret = cast<sandboxir::ReturnInst>(&*It++);
322 
323   sandboxir::DependencyGraph DAG(getAA(*LLVMF));
324   DAG.extend({&*BB->begin(), BB->getTerminator()});
325 
326   auto *S0N = cast<sandboxir::MemDGNode>(DAG.getNode(S0));
327   auto *S1N = cast<sandboxir::MemDGNode>(DAG.getNode(S1));
328 
329   EXPECT_EQ(S0N->getPrevNode(), nullptr);
330   EXPECT_EQ(S0N->getNextNode(), S1N);
331 
332   EXPECT_EQ(S1N->getPrevNode(), S0N);
333   EXPECT_EQ(S1N->getNextNode(), nullptr);
334 }
335 
336 TEST_F(DependencyGraphTest, DGNodeRange) {
337   parseIR(C, R"IR(
338 define void @foo(ptr %ptr, i8 %v0, i8 %v1) {
339   add i8 %v0, %v0
340   store i8 %v0, ptr %ptr
341   add i8 %v0, %v0
342   store i8 %v1, ptr %ptr
343   ret void
344 }
345 )IR");
346   llvm::Function *LLVMF = &*M->getFunction("foo");
347   sandboxir::Context Ctx(C);
348   auto *F = Ctx.createFunction(LLVMF);
349   auto *BB = &*F->begin();
350   auto It = BB->begin();
351   auto *Add0 = cast<sandboxir::BinaryOperator>(&*It++);
352   auto *S0 = cast<sandboxir::StoreInst>(&*It++);
353   auto *Add1 = cast<sandboxir::BinaryOperator>(&*It++);
354   auto *S1 = cast<sandboxir::StoreInst>(&*It++);
355   auto *Ret = cast<sandboxir::ReturnInst>(&*It++);
356 
357   sandboxir::DependencyGraph DAG(getAA(*LLVMF));
358   DAG.extend({&*BB->begin(), BB->getTerminator()});
359 
360   auto *S0N = cast<sandboxir::MemDGNode>(DAG.getNode(S0));
361   auto *S1N = cast<sandboxir::MemDGNode>(DAG.getNode(S1));
362 
363   // Check getTopMemDGNode().
364   using B = sandboxir::MemDGNodeIntervalBuilder;
365   using InstrInterval = sandboxir::Interval<sandboxir::Instruction>;
366   EXPECT_EQ(B::getTopMemDGNode(InstrInterval(S0, S0), DAG), S0N);
367   EXPECT_EQ(B::getTopMemDGNode(InstrInterval(S0, Ret), DAG), S0N);
368   EXPECT_EQ(B::getTopMemDGNode(InstrInterval(Add0, Add1), DAG), S0N);
369   EXPECT_EQ(B::getTopMemDGNode(InstrInterval(Add0, Add0), DAG), nullptr);
370 
371   // Check getBotMemDGNode().
372   EXPECT_EQ(B::getBotMemDGNode(InstrInterval(S1, S1), DAG), S1N);
373   EXPECT_EQ(B::getBotMemDGNode(InstrInterval(Add0, S1), DAG), S1N);
374   EXPECT_EQ(B::getBotMemDGNode(InstrInterval(Add0, Ret), DAG), S1N);
375   EXPECT_EQ(B::getBotMemDGNode(InstrInterval(Ret, Ret), DAG), nullptr);
376 
377   // Check empty range.
378   EXPECT_THAT(sandboxir::MemDGNodeIntervalBuilder::makeEmpty(),
379               testing::ElementsAre());
380 
381   // Returns the pointers in Range.
382   auto getPtrVec = [](const auto &Range) {
383     SmallVector<const sandboxir::DGNode *> Vec;
384     for (const sandboxir::DGNode &N : Range)
385       Vec.push_back(&N);
386     return Vec;
387   };
388   // Both TopN and BotN are memory.
389   EXPECT_THAT(
390       getPtrVec(sandboxir::MemDGNodeIntervalBuilder::make({S0, S1}, DAG)),
391       testing::ElementsAre(S0N, S1N));
392   // Only TopN is memory.
393   EXPECT_THAT(
394       getPtrVec(sandboxir::MemDGNodeIntervalBuilder::make({S0, Ret}, DAG)),
395       testing::ElementsAre(S0N, S1N));
396   EXPECT_THAT(
397       getPtrVec(sandboxir::MemDGNodeIntervalBuilder::make({S0, Add1}, DAG)),
398       testing::ElementsAre(S0N));
399   // Only BotN is memory.
400   EXPECT_THAT(
401       getPtrVec(sandboxir::MemDGNodeIntervalBuilder::make({Add0, S1}, DAG)),
402       testing::ElementsAre(S0N, S1N));
403   EXPECT_THAT(
404       getPtrVec(sandboxir::MemDGNodeIntervalBuilder::make({Add0, S0}, DAG)),
405       testing::ElementsAre(S0N));
406   // Neither TopN or BotN is memory.
407   EXPECT_THAT(
408       getPtrVec(sandboxir::MemDGNodeIntervalBuilder::make({Add0, Ret}, DAG)),
409       testing::ElementsAre(S0N, S1N));
410   EXPECT_THAT(
411       getPtrVec(sandboxir::MemDGNodeIntervalBuilder::make({Add0, Add0}, DAG)),
412       testing::ElementsAre());
413 }
414 
415 TEST_F(DependencyGraphTest, AliasingStores) {
416   parseIR(C, R"IR(
417 define void @foo(ptr %ptr, i8 %v0, i8 %v1) {
418   store i8 %v0, ptr %ptr
419   store i8 %v1, ptr %ptr
420   ret void
421 }
422 )IR");
423   llvm::Function *LLVMF = &*M->getFunction("foo");
424   sandboxir::Context Ctx(C);
425   auto *F = Ctx.createFunction(LLVMF);
426   auto *BB = &*F->begin();
427   sandboxir::DependencyGraph DAG(getAA(*LLVMF));
428   DAG.extend({&*BB->begin(), BB->getTerminator()});
429   auto It = BB->begin();
430   auto *Store0N = cast<sandboxir::MemDGNode>(
431       DAG.getNode(cast<sandboxir::StoreInst>(&*It++)));
432   auto *Store1N = cast<sandboxir::MemDGNode>(
433       DAG.getNode(cast<sandboxir::StoreInst>(&*It++)));
434   auto *RetN = DAG.getNode(cast<sandboxir::ReturnInst>(&*It++));
435   EXPECT_TRUE(Store0N->memPreds().empty());
436   EXPECT_THAT(Store1N->memPreds(), testing::ElementsAre(Store0N));
437   EXPECT_TRUE(RetN->preds(DAG).empty());
438 }
439 
440 TEST_F(DependencyGraphTest, NonAliasingStores) {
441   parseIR(C, R"IR(
442 define void @foo(ptr noalias %ptr0, ptr noalias %ptr1, i8 %v0, i8 %v1) {
443   store i8 %v0, ptr %ptr0
444   store i8 %v1, ptr %ptr1
445   ret void
446 }
447 )IR");
448   llvm::Function *LLVMF = &*M->getFunction("foo");
449   sandboxir::Context Ctx(C);
450   auto *F = Ctx.createFunction(LLVMF);
451   auto *BB = &*F->begin();
452   sandboxir::DependencyGraph DAG(getAA(*LLVMF));
453   DAG.extend({&*BB->begin(), BB->getTerminator()});
454   auto It = BB->begin();
455   auto *Store0N = cast<sandboxir::MemDGNode>(
456       DAG.getNode(cast<sandboxir::StoreInst>(&*It++)));
457   auto *Store1N = cast<sandboxir::MemDGNode>(
458       DAG.getNode(cast<sandboxir::StoreInst>(&*It++)));
459   auto *RetN = DAG.getNode(cast<sandboxir::ReturnInst>(&*It++));
460   // We expect no dependencies because the stores don't alias.
461   EXPECT_TRUE(Store0N->memPreds().empty());
462   EXPECT_TRUE(Store1N->memPreds().empty());
463   EXPECT_TRUE(RetN->preds(DAG).empty());
464 }
465 
466 TEST_F(DependencyGraphTest, VolatileLoads) {
467   parseIR(C, R"IR(
468 define void @foo(ptr noalias %ptr0, ptr noalias %ptr1) {
469   %ld0 = load volatile i8, ptr %ptr0
470   %ld1 = load volatile i8, ptr %ptr1
471   ret void
472 }
473 )IR");
474   llvm::Function *LLVMF = &*M->getFunction("foo");
475   sandboxir::Context Ctx(C);
476   auto *F = Ctx.createFunction(LLVMF);
477   auto *BB = &*F->begin();
478   sandboxir::DependencyGraph DAG(getAA(*LLVMF));
479   DAG.extend({&*BB->begin(), BB->getTerminator()});
480   auto It = BB->begin();
481   auto *Ld0N = cast<sandboxir::MemDGNode>(
482       DAG.getNode(cast<sandboxir::LoadInst>(&*It++)));
483   auto *Ld1N = cast<sandboxir::MemDGNode>(
484       DAG.getNode(cast<sandboxir::LoadInst>(&*It++)));
485   auto *RetN = DAG.getNode(cast<sandboxir::ReturnInst>(&*It++));
486   EXPECT_TRUE(Ld0N->memPreds().empty());
487   EXPECT_THAT(Ld1N->memPreds(), testing::ElementsAre(Ld0N));
488   EXPECT_TRUE(RetN->preds(DAG).empty());
489 }
490 
491 TEST_F(DependencyGraphTest, VolatileSotres) {
492   parseIR(C, R"IR(
493 define void @foo(ptr noalias %ptr0, ptr noalias %ptr1, i8 %v) {
494   store volatile i8 %v, ptr %ptr0
495   store volatile i8 %v, ptr %ptr1
496   ret void
497 }
498 )IR");
499   llvm::Function *LLVMF = &*M->getFunction("foo");
500   sandboxir::Context Ctx(C);
501   auto *F = Ctx.createFunction(LLVMF);
502   auto *BB = &*F->begin();
503   sandboxir::DependencyGraph DAG(getAA(*LLVMF));
504   DAG.extend({&*BB->begin(), BB->getTerminator()});
505   auto It = BB->begin();
506   auto *Store0N = cast<sandboxir::MemDGNode>(
507       DAG.getNode(cast<sandboxir::StoreInst>(&*It++)));
508   auto *Store1N = cast<sandboxir::MemDGNode>(
509       DAG.getNode(cast<sandboxir::StoreInst>(&*It++)));
510   auto *RetN = DAG.getNode(cast<sandboxir::ReturnInst>(&*It++));
511   EXPECT_TRUE(Store0N->memPreds().empty());
512   EXPECT_THAT(Store1N->memPreds(), testing::ElementsAre(Store0N));
513   EXPECT_TRUE(RetN->preds(DAG).empty());
514 }
515 
516 TEST_F(DependencyGraphTest, Call) {
517   parseIR(C, R"IR(
518 declare void @bar1()
519 declare void @bar2()
520 define void @foo(float %v1, float %v2) {
521   call void @bar1()
522   %add = fadd float %v1, %v2
523   call void @bar2()
524   ret void
525 }
526 )IR");
527   Function *LLVMF = M->getFunction("foo");
528 
529   sandboxir::Context Ctx(C);
530   auto *F = Ctx.createFunction(LLVMF);
531   auto *BB = &*F->begin();
532 
533   sandboxir::DependencyGraph DAG(getAA(*LLVMF));
534   DAG.extend({&*BB->begin(), BB->getTerminator()->getPrevNode()});
535 
536   auto It = BB->begin();
537   auto *Call1N = cast<sandboxir::MemDGNode>(DAG.getNode(&*It++));
538   auto *AddN = DAG.getNode(&*It++);
539   auto *Call2N = cast<sandboxir::MemDGNode>(DAG.getNode(&*It++));
540 
541   EXPECT_THAT(Call1N->memPreds(), testing::ElementsAre());
542   EXPECT_THAT(AddN->preds(DAG), testing::ElementsAre());
543   EXPECT_THAT(Call2N->memPreds(), testing::ElementsAre(Call1N));
544 }
545 
546 // Check that there is a dependency: stacksave -> alloca -> stackrestore.
547 TEST_F(DependencyGraphTest, StackSaveRestoreInAlloca) {
548   parseIR(C, R"IR(
549 declare ptr @llvm.stacksave()
550 declare void @llvm.stackrestore(ptr %ptr)
551 
552 define void @foo() {
553   %stack0 = call ptr @llvm.stacksave()        ; Should depend on store
554   %alloca0 = alloca inalloca i8               ; Should depend on stacksave
555   call void @llvm.stackrestore(ptr %stack0)   ; Should depend transiently on %alloca0
556   ret void
557 }
558 )IR");
559   Function *LLVMF = M->getFunction("foo");
560 
561   sandboxir::Context Ctx(C);
562   auto *F = Ctx.createFunction(LLVMF);
563   auto *BB = &*F->begin();
564 
565   sandboxir::DependencyGraph DAG(getAA(*LLVMF));
566   DAG.extend({&*BB->begin(), BB->getTerminator()->getPrevNode()});
567 
568   auto It = BB->begin();
569   auto *StackSaveN = DAG.getNode(&*It++);
570   auto *AllocaN = DAG.getNode(&*It++);
571   auto *StackRestoreN = DAG.getNode(&*It++);
572 
573   EXPECT_TRUE(memDependency(AllocaN, StackRestoreN));
574   EXPECT_TRUE(memDependency(StackSaveN, AllocaN));
575 }
576 
577 // Checks that stacksave and stackrestore depend on other mem instrs.
578 TEST_F(DependencyGraphTest, StackSaveRestoreDependOnOtherMem) {
579   parseIR(C, R"IR(
580 declare ptr @llvm.stacksave()
581 declare void @llvm.stackrestore(ptr %ptr)
582 
583 define void @foo(i8 %v0, i8 %v1, ptr %ptr) {
584   store volatile i8 %v0, ptr %ptr, align 4
585   %stack0 = call ptr @llvm.stacksave()       ; Should depend on store
586   call void @llvm.stackrestore(ptr %stack0)  ; Should depend on stacksave
587   store volatile i8 %v1, ptr %ptr, align 4   ; Should depend on stackrestore
588   ret void
589 }
590 )IR");
591   Function *LLVMF = M->getFunction("foo");
592 
593   sandboxir::Context Ctx(C);
594   auto *F = Ctx.createFunction(LLVMF);
595   auto *BB = &*F->begin();
596 
597   sandboxir::DependencyGraph DAG(getAA(*LLVMF));
598   DAG.extend({&*BB->begin(), BB->getTerminator()->getPrevNode()});
599 
600   auto It = BB->begin();
601   auto *Store0N = DAG.getNode(&*It++);
602   auto *StackSaveN = DAG.getNode(&*It++);
603   auto *StackRestoreN = DAG.getNode(&*It++);
604   auto *Store1N = DAG.getNode(&*It++);
605 
606   EXPECT_TRUE(memDependency(Store0N, StackSaveN));
607   EXPECT_TRUE(memDependency(StackSaveN, StackRestoreN));
608   EXPECT_TRUE(memDependency(StackRestoreN, Store1N));
609 }
610 
611 // Make sure there is a dependency between a stackrestore and an alloca.
612 TEST_F(DependencyGraphTest, StackRestoreAndInAlloca) {
613   parseIR(C, R"IR(
614 declare void @llvm.stackrestore(ptr %ptr)
615 
616 define void @foo(ptr %ptr) {
617   call void @llvm.stackrestore(ptr %ptr)
618   %alloca0 = alloca inalloca i8              ; Should depend on stackrestore
619   ret void
620 }
621 )IR");
622   Function *LLVMF = M->getFunction("foo");
623 
624   sandboxir::Context Ctx(C);
625   auto *F = Ctx.createFunction(LLVMF);
626   auto *BB = &*F->begin();
627 
628   sandboxir::DependencyGraph DAG(getAA(*LLVMF));
629   DAG.extend({&*BB->begin(), BB->getTerminator()->getPrevNode()});
630 
631   auto It = BB->begin();
632   auto *StackRestoreN = DAG.getNode(&*It++);
633   auto *AllocaN = DAG.getNode(&*It++);
634 
635   EXPECT_TRUE(memDependency(StackRestoreN, AllocaN));
636 }
637 
638 // Make sure there is a dependency between the alloca and stacksave
639 TEST_F(DependencyGraphTest, StackSaveAndInAlloca) {
640   parseIR(C, R"IR(
641 declare ptr @llvm.stacksave()
642 
643 define void @foo(ptr %ptr) {
644   %alloca0 = alloca inalloca i8              ; Should depend on stackrestore
645   %stack0 = call ptr @llvm.stacksave()       ; Should depend on alloca0
646   ret void
647 }
648 )IR");
649   Function *LLVMF = M->getFunction("foo");
650 
651   sandboxir::Context Ctx(C);
652   auto *F = Ctx.createFunction(LLVMF);
653   auto *BB = &*F->begin();
654 
655   sandboxir::DependencyGraph DAG(getAA(*LLVMF));
656   DAG.extend({&*BB->begin(), BB->getTerminator()->getPrevNode()});
657 
658   auto It = BB->begin();
659   auto *AllocaN = DAG.getNode(&*It++);
660   auto *StackSaveN = DAG.getNode(&*It++);
661 
662   EXPECT_TRUE(memDependency(AllocaN, StackSaveN));
663 }
664 
665 // A non-InAlloca in a stacksave-stackrestore region does not need extra
666 // dependencies.
667 TEST_F(DependencyGraphTest, StackSaveRestoreNoInAlloca) {
668   parseIR(C, R"IR(
669 declare ptr @llvm.stacksave()
670 declare void @llvm.stackrestore(ptr %ptr)
671 declare void @use(ptr %ptr)
672 
673 define void @foo() {
674   %stack = call ptr @llvm.stacksave()
675   %alloca1 = alloca i8                         ; No dependency
676   call void @llvm.stackrestore(ptr %stack)
677   ret void
678 }
679 )IR");
680   Function *LLVMF = M->getFunction("foo");
681 
682   sandboxir::Context Ctx(C);
683   auto *F = Ctx.createFunction(LLVMF);
684   auto *BB = &*F->begin();
685 
686   sandboxir::DependencyGraph DAG(getAA(*LLVMF));
687   DAG.extend({&*BB->begin(), BB->getTerminator()->getPrevNode()});
688 
689   auto It = BB->begin();
690   auto *StackSaveN = DAG.getNode(&*It++);
691   auto *AllocaN = DAG.getNode(&*It++);
692   auto *StackRestoreN = DAG.getNode(&*It++);
693 
694   EXPECT_FALSE(memDependency(StackSaveN, AllocaN));
695   EXPECT_FALSE(memDependency(AllocaN, StackRestoreN));
696 }
697 
698 TEST_F(DependencyGraphTest, Extend) {
699   parseIR(C, R"IR(
700 define void @foo(ptr %ptr, i8 %v1, i8 %v2, i8 %v3, i8 %v4, i8 %v5) {
701   store i8 %v1, ptr %ptr
702   store i8 %v2, ptr %ptr
703   store i8 %v3, ptr %ptr
704   store i8 %v4, ptr %ptr
705   store i8 %v5, ptr %ptr
706   ret void
707 }
708 )IR");
709   llvm::Function *LLVMF = &*M->getFunction("foo");
710   sandboxir::Context Ctx(C);
711   auto *F = Ctx.createFunction(LLVMF);
712   auto *BB = &*F->begin();
713   auto It = BB->begin();
714   auto *S1 = cast<sandboxir::StoreInst>(&*It++);
715   auto *S2 = cast<sandboxir::StoreInst>(&*It++);
716   auto *S3 = cast<sandboxir::StoreInst>(&*It++);
717   auto *S4 = cast<sandboxir::StoreInst>(&*It++);
718   auto *S5 = cast<sandboxir::StoreInst>(&*It++);
719   sandboxir::DependencyGraph DAG(getAA(*LLVMF));
720   {
721     // Scenario 1: Build new DAG
722     auto NewIntvl = DAG.extend({S3, S3});
723     EXPECT_EQ(NewIntvl, sandboxir::Interval<sandboxir::Instruction>(S3, S3));
724     EXPECT_EQ(DAG.getInterval().top(), S3);
725     EXPECT_EQ(DAG.getInterval().bottom(), S3);
726     [[maybe_unused]] auto *S3N = cast<sandboxir::MemDGNode>(DAG.getNode(S3));
727     // Check UnscheduledSuccs.
728     EXPECT_EQ(S3N->getNumUnscheduledSuccs(), 0u);
729   }
730   {
731     // Scenario 2: Extend below
732     auto NewIntvl = DAG.extend({S5, S5});
733     EXPECT_EQ(NewIntvl, sandboxir::Interval<sandboxir::Instruction>(S4, S5));
734     auto *S3N = cast<sandboxir::MemDGNode>(DAG.getNode(S3));
735     auto *S4N = cast<sandboxir::MemDGNode>(DAG.getNode(S4));
736     auto *S5N = cast<sandboxir::MemDGNode>(DAG.getNode(S5));
737     EXPECT_TRUE(S4N->hasMemPred(S3N));
738     EXPECT_TRUE(S5N->hasMemPred(S4N));
739     EXPECT_TRUE(S5N->hasMemPred(S3N));
740     // Check UnscheduledSuccs.
741     EXPECT_EQ(S3N->getNumUnscheduledSuccs(), 2u); // S4N, S5N
742     EXPECT_EQ(S4N->getNumUnscheduledSuccs(), 1u); // S5N
743     EXPECT_EQ(S5N->getNumUnscheduledSuccs(), 0u);
744   }
745   {
746     // Scenario 3: Extend above
747     auto NewIntvl = DAG.extend({S1, S2});
748     EXPECT_EQ(NewIntvl, sandboxir::Interval<sandboxir::Instruction>(S1, S2));
749     auto *S1N = cast<sandboxir::MemDGNode>(DAG.getNode(S1));
750     auto *S2N = cast<sandboxir::MemDGNode>(DAG.getNode(S2));
751     auto *S3N = cast<sandboxir::MemDGNode>(DAG.getNode(S3));
752     auto *S4N = cast<sandboxir::MemDGNode>(DAG.getNode(S4));
753     auto *S5N = cast<sandboxir::MemDGNode>(DAG.getNode(S5));
754 
755     EXPECT_TRUE(S2N->hasMemPred(S1N));
756 
757     EXPECT_TRUE(S3N->hasMemPred(S2N));
758     EXPECT_TRUE(S3N->hasMemPred(S1N));
759 
760     EXPECT_TRUE(S4N->hasMemPred(S3N));
761     EXPECT_TRUE(S4N->hasMemPred(S2N));
762     EXPECT_TRUE(S4N->hasMemPred(S1N));
763 
764     EXPECT_TRUE(S5N->hasMemPred(S4N));
765     EXPECT_TRUE(S5N->hasMemPred(S3N));
766     EXPECT_TRUE(S5N->hasMemPred(S2N));
767     EXPECT_TRUE(S5N->hasMemPred(S1N));
768 
769     // Check UnscheduledSuccs.
770     EXPECT_EQ(S1N->getNumUnscheduledSuccs(), 4u); // S2N, S3N, S4N, S5N
771     EXPECT_EQ(S2N->getNumUnscheduledSuccs(), 3u); // S3N, S4N, S5N
772     EXPECT_EQ(S3N->getNumUnscheduledSuccs(), 2u); // S4N, S5N
773     EXPECT_EQ(S4N->getNumUnscheduledSuccs(), 1u); // S5N
774     EXPECT_EQ(S5N->getNumUnscheduledSuccs(), 0u);
775   }
776 }
777