xref: /llvm-project/llvm/unittests/Transforms/Vectorize/SandboxVectorizer/DependencyGraphTest.cpp (revision e8dd95e97bd45c8ee3cc2a3d95c9a6198a970d80) 
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 
254 TEST_F(DependencyGraphTest, Preds) {
255   parseIR(C, R"IR(
256 declare ptr @bar(i8)
257 define i8 @foo(i8 %v0, i8 %v1) {
258   %add0 = add i8 %v0, %v0
259   %add1 = add i8 %v1, %v1
260   %add2 = add i8 %add0, %add1
261   %ptr = call ptr @bar(i8 %add1)
262   store i8 %add2, ptr %ptr
263   ret i8 %add2
264 }
265 )IR");
266   llvm::Function *LLVMF = &*M->getFunction("foo");
267   sandboxir::Context Ctx(C);
268   auto *F = Ctx.createFunction(LLVMF);
269   auto *BB = &*F->begin();
270   auto It = BB->begin();
271   sandboxir::DependencyGraph DAG(getAA(*LLVMF));
272   DAG.extend({&*BB->begin(), BB->getTerminator()});
273 
274   auto *AddN0 = DAG.getNode(cast<sandboxir::BinaryOperator>(&*It++));
275   auto *AddN1 = DAG.getNode(cast<sandboxir::BinaryOperator>(&*It++));
276   auto *AddN2 = DAG.getNode(cast<sandboxir::BinaryOperator>(&*It++));
277   auto *CallN = DAG.getNode(cast<sandboxir::CallInst>(&*It++));
278   auto *StN = DAG.getNode(cast<sandboxir::StoreInst>(&*It++));
279   auto *RetN = DAG.getNode(cast<sandboxir::ReturnInst>(&*It++));
280 
281   // Check preds().
282   EXPECT_THAT(AddN0->preds(DAG), testing::ElementsAre());
283   EXPECT_THAT(AddN1->preds(DAG), testing::ElementsAre());
284   EXPECT_THAT(AddN2->preds(DAG), testing::ElementsAre(AddN0, AddN1));
285   EXPECT_THAT(CallN->preds(DAG), testing::ElementsAre(AddN1));
286   EXPECT_THAT(StN->preds(DAG),
287               testing::UnorderedElementsAre(CallN, CallN, AddN2));
288   EXPECT_THAT(RetN->preds(DAG), testing::ElementsAre(AddN2));
289 }
290 
291 TEST_F(DependencyGraphTest, MemDGNode_getPrevNode_getNextNode) {
292   parseIR(C, R"IR(
293 define void @foo(ptr %ptr, i8 %v0, i8 %v1) {
294   store i8 %v0, ptr %ptr
295   add i8 %v0, %v0
296   store i8 %v1, ptr %ptr
297   ret void
298 }
299 )IR");
300   llvm::Function *LLVMF = &*M->getFunction("foo");
301   sandboxir::Context Ctx(C);
302   auto *F = Ctx.createFunction(LLVMF);
303   auto *BB = &*F->begin();
304   auto It = BB->begin();
305   auto *S0 = cast<sandboxir::StoreInst>(&*It++);
306   [[maybe_unused]] auto *Add = cast<sandboxir::BinaryOperator>(&*It++);
307   auto *S1 = cast<sandboxir::StoreInst>(&*It++);
308   [[maybe_unused]] auto *Ret = cast<sandboxir::ReturnInst>(&*It++);
309 
310   sandboxir::DependencyGraph DAG(getAA(*LLVMF));
311   DAG.extend({&*BB->begin(), BB->getTerminator()});
312 
313   auto *S0N = cast<sandboxir::MemDGNode>(DAG.getNode(S0));
314   auto *S1N = cast<sandboxir::MemDGNode>(DAG.getNode(S1));
315 
316   EXPECT_EQ(S0N->getPrevNode(), nullptr);
317   EXPECT_EQ(S0N->getNextNode(), S1N);
318 
319   EXPECT_EQ(S1N->getPrevNode(), S0N);
320   EXPECT_EQ(S1N->getNextNode(), nullptr);
321 }
322 
323 TEST_F(DependencyGraphTest, DGNodeRange) {
324   parseIR(C, R"IR(
325 define void @foo(ptr %ptr, i8 %v0, i8 %v1) {
326   add i8 %v0, %v0
327   store i8 %v0, ptr %ptr
328   add i8 %v0, %v0
329   store i8 %v1, ptr %ptr
330   ret void
331 }
332 )IR");
333   llvm::Function *LLVMF = &*M->getFunction("foo");
334   sandboxir::Context Ctx(C);
335   auto *F = Ctx.createFunction(LLVMF);
336   auto *BB = &*F->begin();
337   auto It = BB->begin();
338   auto *Add0 = cast<sandboxir::BinaryOperator>(&*It++);
339   auto *S0 = cast<sandboxir::StoreInst>(&*It++);
340   auto *Add1 = cast<sandboxir::BinaryOperator>(&*It++);
341   auto *S1 = cast<sandboxir::StoreInst>(&*It++);
342   auto *Ret = cast<sandboxir::ReturnInst>(&*It++);
343 
344   sandboxir::DependencyGraph DAG(getAA(*LLVMF));
345   DAG.extend({&*BB->begin(), BB->getTerminator()});
346 
347   auto *S0N = cast<sandboxir::MemDGNode>(DAG.getNode(S0));
348   auto *S1N = cast<sandboxir::MemDGNode>(DAG.getNode(S1));
349 
350   // Check getTopMemDGNode().
351   using B = sandboxir::MemDGNodeIntervalBuilder;
352   using InstrInterval = sandboxir::Interval<sandboxir::Instruction>;
353   EXPECT_EQ(B::getTopMemDGNode(InstrInterval(S0, S0), DAG), S0N);
354   EXPECT_EQ(B::getTopMemDGNode(InstrInterval(S0, Ret), DAG), S0N);
355   EXPECT_EQ(B::getTopMemDGNode(InstrInterval(Add0, Add1), DAG), S0N);
356   EXPECT_EQ(B::getTopMemDGNode(InstrInterval(Add0, Add0), DAG), nullptr);
357 
358   // Check getBotMemDGNode().
359   EXPECT_EQ(B::getBotMemDGNode(InstrInterval(S1, S1), DAG), S1N);
360   EXPECT_EQ(B::getBotMemDGNode(InstrInterval(Add0, S1), DAG), S1N);
361   EXPECT_EQ(B::getBotMemDGNode(InstrInterval(Add0, Ret), DAG), S1N);
362   EXPECT_EQ(B::getBotMemDGNode(InstrInterval(Ret, Ret), DAG), nullptr);
363 
364   // Check empty range.
365   EXPECT_THAT(sandboxir::MemDGNodeIntervalBuilder::makeEmpty(),
366               testing::ElementsAre());
367 
368   // Returns the pointers in Range.
369   auto getPtrVec = [](const auto &Range) {
370     SmallVector<const sandboxir::DGNode *> Vec;
371     for (const sandboxir::DGNode &N : Range)
372       Vec.push_back(&N);
373     return Vec;
374   };
375   // Both TopN and BotN are memory.
376   EXPECT_THAT(
377       getPtrVec(sandboxir::MemDGNodeIntervalBuilder::make({S0, S1}, DAG)),
378       testing::ElementsAre(S0N, S1N));
379   // Only TopN is memory.
380   EXPECT_THAT(
381       getPtrVec(sandboxir::MemDGNodeIntervalBuilder::make({S0, Ret}, DAG)),
382       testing::ElementsAre(S0N, S1N));
383   EXPECT_THAT(
384       getPtrVec(sandboxir::MemDGNodeIntervalBuilder::make({S0, Add1}, DAG)),
385       testing::ElementsAre(S0N));
386   // Only BotN is memory.
387   EXPECT_THAT(
388       getPtrVec(sandboxir::MemDGNodeIntervalBuilder::make({Add0, S1}, DAG)),
389       testing::ElementsAre(S0N, S1N));
390   EXPECT_THAT(
391       getPtrVec(sandboxir::MemDGNodeIntervalBuilder::make({Add0, S0}, DAG)),
392       testing::ElementsAre(S0N));
393   // Neither TopN or BotN is memory.
394   EXPECT_THAT(
395       getPtrVec(sandboxir::MemDGNodeIntervalBuilder::make({Add0, Ret}, DAG)),
396       testing::ElementsAre(S0N, S1N));
397   EXPECT_THAT(
398       getPtrVec(sandboxir::MemDGNodeIntervalBuilder::make({Add0, Add0}, DAG)),
399       testing::ElementsAre());
400 }
401 
402 TEST_F(DependencyGraphTest, AliasingStores) {
403   parseIR(C, R"IR(
404 define void @foo(ptr %ptr, i8 %v0, i8 %v1) {
405   store i8 %v0, ptr %ptr
406   store i8 %v1, ptr %ptr
407   ret void
408 }
409 )IR");
410   llvm::Function *LLVMF = &*M->getFunction("foo");
411   sandboxir::Context Ctx(C);
412   auto *F = Ctx.createFunction(LLVMF);
413   auto *BB = &*F->begin();
414   sandboxir::DependencyGraph DAG(getAA(*LLVMF));
415   DAG.extend({&*BB->begin(), BB->getTerminator()});
416   auto It = BB->begin();
417   auto *Store0N = cast<sandboxir::MemDGNode>(
418       DAG.getNode(cast<sandboxir::StoreInst>(&*It++)));
419   auto *Store1N = cast<sandboxir::MemDGNode>(
420       DAG.getNode(cast<sandboxir::StoreInst>(&*It++)));
421   auto *RetN = DAG.getNode(cast<sandboxir::ReturnInst>(&*It++));
422   EXPECT_TRUE(Store0N->memPreds().empty());
423   EXPECT_THAT(Store1N->memPreds(), testing::ElementsAre(Store0N));
424   EXPECT_TRUE(RetN->preds(DAG).empty());
425 }
426 
427 TEST_F(DependencyGraphTest, NonAliasingStores) {
428   parseIR(C, R"IR(
429 define void @foo(ptr noalias %ptr0, ptr noalias %ptr1, i8 %v0, i8 %v1) {
430   store i8 %v0, ptr %ptr0
431   store i8 %v1, ptr %ptr1
432   ret void
433 }
434 )IR");
435   llvm::Function *LLVMF = &*M->getFunction("foo");
436   sandboxir::Context Ctx(C);
437   auto *F = Ctx.createFunction(LLVMF);
438   auto *BB = &*F->begin();
439   sandboxir::DependencyGraph DAG(getAA(*LLVMF));
440   DAG.extend({&*BB->begin(), BB->getTerminator()});
441   auto It = BB->begin();
442   auto *Store0N = cast<sandboxir::MemDGNode>(
443       DAG.getNode(cast<sandboxir::StoreInst>(&*It++)));
444   auto *Store1N = cast<sandboxir::MemDGNode>(
445       DAG.getNode(cast<sandboxir::StoreInst>(&*It++)));
446   auto *RetN = DAG.getNode(cast<sandboxir::ReturnInst>(&*It++));
447   // We expect no dependencies because the stores don't alias.
448   EXPECT_TRUE(Store0N->memPreds().empty());
449   EXPECT_TRUE(Store1N->memPreds().empty());
450   EXPECT_TRUE(RetN->preds(DAG).empty());
451 }
452 
453 TEST_F(DependencyGraphTest, VolatileLoads) {
454   parseIR(C, R"IR(
455 define void @foo(ptr noalias %ptr0, ptr noalias %ptr1) {
456   %ld0 = load volatile i8, ptr %ptr0
457   %ld1 = load volatile i8, ptr %ptr1
458   ret void
459 }
460 )IR");
461   llvm::Function *LLVMF = &*M->getFunction("foo");
462   sandboxir::Context Ctx(C);
463   auto *F = Ctx.createFunction(LLVMF);
464   auto *BB = &*F->begin();
465   sandboxir::DependencyGraph DAG(getAA(*LLVMF));
466   DAG.extend({&*BB->begin(), BB->getTerminator()});
467   auto It = BB->begin();
468   auto *Ld0N = cast<sandboxir::MemDGNode>(
469       DAG.getNode(cast<sandboxir::LoadInst>(&*It++)));
470   auto *Ld1N = cast<sandboxir::MemDGNode>(
471       DAG.getNode(cast<sandboxir::LoadInst>(&*It++)));
472   auto *RetN = DAG.getNode(cast<sandboxir::ReturnInst>(&*It++));
473   EXPECT_TRUE(Ld0N->memPreds().empty());
474   EXPECT_THAT(Ld1N->memPreds(), testing::ElementsAre(Ld0N));
475   EXPECT_TRUE(RetN->preds(DAG).empty());
476 }
477 
478 TEST_F(DependencyGraphTest, VolatileSotres) {
479   parseIR(C, R"IR(
480 define void @foo(ptr noalias %ptr0, ptr noalias %ptr1, i8 %v) {
481   store volatile i8 %v, ptr %ptr0
482   store volatile i8 %v, ptr %ptr1
483   ret void
484 }
485 )IR");
486   llvm::Function *LLVMF = &*M->getFunction("foo");
487   sandboxir::Context Ctx(C);
488   auto *F = Ctx.createFunction(LLVMF);
489   auto *BB = &*F->begin();
490   sandboxir::DependencyGraph DAG(getAA(*LLVMF));
491   DAG.extend({&*BB->begin(), BB->getTerminator()});
492   auto It = BB->begin();
493   auto *Store0N = cast<sandboxir::MemDGNode>(
494       DAG.getNode(cast<sandboxir::StoreInst>(&*It++)));
495   auto *Store1N = cast<sandboxir::MemDGNode>(
496       DAG.getNode(cast<sandboxir::StoreInst>(&*It++)));
497   auto *RetN = DAG.getNode(cast<sandboxir::ReturnInst>(&*It++));
498   EXPECT_TRUE(Store0N->memPreds().empty());
499   EXPECT_THAT(Store1N->memPreds(), testing::ElementsAre(Store0N));
500   EXPECT_TRUE(RetN->preds(DAG).empty());
501 }
502 
503 TEST_F(DependencyGraphTest, Call) {
504   parseIR(C, R"IR(
505 declare void @bar1()
506 declare void @bar2()
507 define void @foo(float %v1, float %v2) {
508   call void @bar1()
509   %add = fadd float %v1, %v2
510   call void @bar2()
511   ret void
512 }
513 )IR");
514   Function *LLVMF = M->getFunction("foo");
515 
516   sandboxir::Context Ctx(C);
517   auto *F = Ctx.createFunction(LLVMF);
518   auto *BB = &*F->begin();
519 
520   sandboxir::DependencyGraph DAG(getAA(*LLVMF));
521   DAG.extend({&*BB->begin(), BB->getTerminator()->getPrevNode()});
522 
523   auto It = BB->begin();
524   auto *Call1N = cast<sandboxir::MemDGNode>(DAG.getNode(&*It++));
525   auto *AddN = DAG.getNode(&*It++);
526   auto *Call2N = cast<sandboxir::MemDGNode>(DAG.getNode(&*It++));
527 
528   EXPECT_THAT(Call1N->memPreds(), testing::ElementsAre());
529   EXPECT_THAT(AddN->preds(DAG), testing::ElementsAre());
530   EXPECT_THAT(Call2N->memPreds(), testing::ElementsAre(Call1N));
531 }
532 
533 // Check that there is a dependency: stacksave -> alloca -> stackrestore.
534 TEST_F(DependencyGraphTest, StackSaveRestoreInAlloca) {
535   parseIR(C, R"IR(
536 declare ptr @llvm.stacksave()
537 declare void @llvm.stackrestore(ptr %ptr)
538 
539 define void @foo() {
540   %stack0 = call ptr @llvm.stacksave()        ; Should depend on store
541   %alloca0 = alloca inalloca i8               ; Should depend on stacksave
542   call void @llvm.stackrestore(ptr %stack0)   ; Should depend transiently on %alloca0
543   ret void
544 }
545 )IR");
546   Function *LLVMF = M->getFunction("foo");
547 
548   sandboxir::Context Ctx(C);
549   auto *F = Ctx.createFunction(LLVMF);
550   auto *BB = &*F->begin();
551 
552   sandboxir::DependencyGraph DAG(getAA(*LLVMF));
553   DAG.extend({&*BB->begin(), BB->getTerminator()->getPrevNode()});
554 
555   auto It = BB->begin();
556   auto *StackSaveN = DAG.getNode(&*It++);
557   auto *AllocaN = DAG.getNode(&*It++);
558   auto *StackRestoreN = DAG.getNode(&*It++);
559 
560   EXPECT_TRUE(memDependency(AllocaN, StackRestoreN));
561   EXPECT_TRUE(memDependency(StackSaveN, AllocaN));
562 }
563 
564 // Checks that stacksave and stackrestore depend on other mem instrs.
565 TEST_F(DependencyGraphTest, StackSaveRestoreDependOnOtherMem) {
566   parseIR(C, R"IR(
567 declare ptr @llvm.stacksave()
568 declare void @llvm.stackrestore(ptr %ptr)
569 
570 define void @foo(i8 %v0, i8 %v1, ptr %ptr) {
571   store volatile i8 %v0, ptr %ptr, align 4
572   %stack0 = call ptr @llvm.stacksave()       ; Should depend on store
573   call void @llvm.stackrestore(ptr %stack0)  ; Should depend on stacksave
574   store volatile i8 %v1, ptr %ptr, align 4   ; Should depend on stackrestore
575   ret void
576 }
577 )IR");
578   Function *LLVMF = M->getFunction("foo");
579 
580   sandboxir::Context Ctx(C);
581   auto *F = Ctx.createFunction(LLVMF);
582   auto *BB = &*F->begin();
583 
584   sandboxir::DependencyGraph DAG(getAA(*LLVMF));
585   DAG.extend({&*BB->begin(), BB->getTerminator()->getPrevNode()});
586 
587   auto It = BB->begin();
588   auto *Store0N = DAG.getNode(&*It++);
589   auto *StackSaveN = DAG.getNode(&*It++);
590   auto *StackRestoreN = DAG.getNode(&*It++);
591   auto *Store1N = DAG.getNode(&*It++);
592 
593   EXPECT_TRUE(memDependency(Store0N, StackSaveN));
594   EXPECT_TRUE(memDependency(StackSaveN, StackRestoreN));
595   EXPECT_TRUE(memDependency(StackRestoreN, Store1N));
596 }
597 
598 // Make sure there is a dependency between a stackrestore and an alloca.
599 TEST_F(DependencyGraphTest, StackRestoreAndInAlloca) {
600   parseIR(C, R"IR(
601 declare void @llvm.stackrestore(ptr %ptr)
602 
603 define void @foo(ptr %ptr) {
604   call void @llvm.stackrestore(ptr %ptr)
605   %alloca0 = alloca inalloca i8              ; Should depend on stackrestore
606   ret void
607 }
608 )IR");
609   Function *LLVMF = M->getFunction("foo");
610 
611   sandboxir::Context Ctx(C);
612   auto *F = Ctx.createFunction(LLVMF);
613   auto *BB = &*F->begin();
614 
615   sandboxir::DependencyGraph DAG(getAA(*LLVMF));
616   DAG.extend({&*BB->begin(), BB->getTerminator()->getPrevNode()});
617 
618   auto It = BB->begin();
619   auto *StackRestoreN = DAG.getNode(&*It++);
620   auto *AllocaN = DAG.getNode(&*It++);
621 
622   EXPECT_TRUE(memDependency(StackRestoreN, AllocaN));
623 }
624 
625 // Make sure there is a dependency between the alloca and stacksave
626 TEST_F(DependencyGraphTest, StackSaveAndInAlloca) {
627   parseIR(C, R"IR(
628 declare ptr @llvm.stacksave()
629 
630 define void @foo(ptr %ptr) {
631   %alloca0 = alloca inalloca i8              ; Should depend on stackrestore
632   %stack0 = call ptr @llvm.stacksave()       ; Should depend on alloca0
633   ret void
634 }
635 )IR");
636   Function *LLVMF = M->getFunction("foo");
637 
638   sandboxir::Context Ctx(C);
639   auto *F = Ctx.createFunction(LLVMF);
640   auto *BB = &*F->begin();
641 
642   sandboxir::DependencyGraph DAG(getAA(*LLVMF));
643   DAG.extend({&*BB->begin(), BB->getTerminator()->getPrevNode()});
644 
645   auto It = BB->begin();
646   auto *AllocaN = DAG.getNode(&*It++);
647   auto *StackSaveN = DAG.getNode(&*It++);
648 
649   EXPECT_TRUE(memDependency(AllocaN, StackSaveN));
650 }
651 
652 // A non-InAlloca in a stacksave-stackrestore region does not need extra
653 // dependencies.
654 TEST_F(DependencyGraphTest, StackSaveRestoreNoInAlloca) {
655   parseIR(C, R"IR(
656 declare ptr @llvm.stacksave()
657 declare void @llvm.stackrestore(ptr %ptr)
658 declare void @use(ptr %ptr)
659 
660 define void @foo() {
661   %stack = call ptr @llvm.stacksave()
662   %alloca1 = alloca i8                         ; No dependency
663   call void @llvm.stackrestore(ptr %stack)
664   ret void
665 }
666 )IR");
667   Function *LLVMF = M->getFunction("foo");
668 
669   sandboxir::Context Ctx(C);
670   auto *F = Ctx.createFunction(LLVMF);
671   auto *BB = &*F->begin();
672 
673   sandboxir::DependencyGraph DAG(getAA(*LLVMF));
674   DAG.extend({&*BB->begin(), BB->getTerminator()->getPrevNode()});
675 
676   auto It = BB->begin();
677   auto *StackSaveN = DAG.getNode(&*It++);
678   auto *AllocaN = DAG.getNode(&*It++);
679   auto *StackRestoreN = DAG.getNode(&*It++);
680 
681   EXPECT_FALSE(memDependency(StackSaveN, AllocaN));
682   EXPECT_FALSE(memDependency(AllocaN, StackRestoreN));
683 }
684 
685 TEST_F(DependencyGraphTest, Extend) {
686   parseIR(C, R"IR(
687 define void @foo(ptr %ptr, i8 %v1, i8 %v2, i8 %v3, i8 %v4, i8 %v5) {
688   store i8 %v1, ptr %ptr
689   store i8 %v2, ptr %ptr
690   store i8 %v3, ptr %ptr
691   store i8 %v4, ptr %ptr
692   store i8 %v5, ptr %ptr
693   ret void
694 }
695 )IR");
696   llvm::Function *LLVMF = &*M->getFunction("foo");
697   sandboxir::Context Ctx(C);
698   auto *F = Ctx.createFunction(LLVMF);
699   auto *BB = &*F->begin();
700   auto It = BB->begin();
701   auto *S1 = cast<sandboxir::StoreInst>(&*It++);
702   auto *S2 = cast<sandboxir::StoreInst>(&*It++);
703   auto *S3 = cast<sandboxir::StoreInst>(&*It++);
704   auto *S4 = cast<sandboxir::StoreInst>(&*It++);
705   auto *S5 = cast<sandboxir::StoreInst>(&*It++);
706   sandboxir::DependencyGraph DAG(getAA(*LLVMF));
707   {
708     // Scenario 1: Build new DAG
709     auto NewIntvl = DAG.extend({S3, S3});
710     EXPECT_EQ(NewIntvl, sandboxir::Interval<sandboxir::Instruction>(S3, S3));
711     EXPECT_EQ(DAG.getInterval().top(), S3);
712     EXPECT_EQ(DAG.getInterval().bottom(), S3);
713     [[maybe_unused]] auto *S3N = cast<sandboxir::MemDGNode>(DAG.getNode(S3));
714   }
715   {
716     // Scenario 2: Extend below
717     auto NewIntvl = DAG.extend({S5, S5});
718     EXPECT_EQ(NewIntvl, sandboxir::Interval<sandboxir::Instruction>(S4, S5));
719     auto *S3N = cast<sandboxir::MemDGNode>(DAG.getNode(S3));
720     auto *S4N = cast<sandboxir::MemDGNode>(DAG.getNode(S4));
721     auto *S5N = cast<sandboxir::MemDGNode>(DAG.getNode(S5));
722     EXPECT_TRUE(S4N->hasMemPred(S3N));
723     EXPECT_TRUE(S5N->hasMemPred(S4N));
724     EXPECT_TRUE(S5N->hasMemPred(S3N));
725   }
726   {
727     // Scenario 3: Extend above
728     auto NewIntvl = DAG.extend({S1, S2});
729     EXPECT_EQ(NewIntvl, sandboxir::Interval<sandboxir::Instruction>(S1, S2));
730     auto *S1N = cast<sandboxir::MemDGNode>(DAG.getNode(S1));
731     auto *S2N = cast<sandboxir::MemDGNode>(DAG.getNode(S2));
732     auto *S3N = cast<sandboxir::MemDGNode>(DAG.getNode(S3));
733     auto *S4N = cast<sandboxir::MemDGNode>(DAG.getNode(S4));
734     auto *S5N = cast<sandboxir::MemDGNode>(DAG.getNode(S5));
735 
736     EXPECT_TRUE(S2N->hasMemPred(S1N));
737 
738     EXPECT_TRUE(S3N->hasMemPred(S2N));
739     EXPECT_TRUE(S3N->hasMemPred(S1N));
740 
741     EXPECT_TRUE(S4N->hasMemPred(S3N));
742     EXPECT_TRUE(S4N->hasMemPred(S2N));
743     EXPECT_TRUE(S4N->hasMemPred(S1N));
744 
745     EXPECT_TRUE(S5N->hasMemPred(S4N));
746     EXPECT_TRUE(S5N->hasMemPred(S3N));
747     EXPECT_TRUE(S5N->hasMemPred(S2N));
748     EXPECT_TRUE(S5N->hasMemPred(S1N));
749   }
750 }
751