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