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