xref: /llvm-project/llvm/unittests/Transforms/Vectorize/SandboxVectorizer/DependencyGraphTest.cpp (revision b41987beaedaa6ea78fd8dd11ba8c3b21eb8fa88) 
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), Ctx);
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), Ctx);
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   // Check decrUnscheduledSuccs.
259   N0->decrUnscheduledSuccs();
260   EXPECT_EQ(N0->getNumUnscheduledSuccs(), 0u);
261 #ifndef NDEBUG
262   EXPECT_DEATH(N0->decrUnscheduledSuccs(), ".*Counting.*");
263 #endif // NDEBUG
264 
265   // Check scheduled(), setScheduled().
266   EXPECT_FALSE(N0->scheduled());
267   N0->setScheduled(true);
268   EXPECT_TRUE(N0->scheduled());
269 }
270 
271 TEST_F(DependencyGraphTest, Preds) {
272   parseIR(C, R"IR(
273 declare ptr @bar(i8)
274 define i8 @foo(i8 %v0, i8 %v1) {
275   %add0 = add i8 %v0, %v0
276   %add1 = add i8 %v1, %v1
277   %add2 = add i8 %add0, %add1
278   %ptr = call ptr @bar(i8 %add1)
279   store i8 %add2, ptr %ptr
280   ret i8 %add2
281 }
282 )IR");
283   llvm::Function *LLVMF = &*M->getFunction("foo");
284   sandboxir::Context Ctx(C);
285   auto *F = Ctx.createFunction(LLVMF);
286   auto *BB = &*F->begin();
287   auto It = BB->begin();
288   sandboxir::DependencyGraph DAG(getAA(*LLVMF), Ctx);
289   DAG.extend({&*BB->begin(), BB->getTerminator()});
290 
291   auto *AddN0 = DAG.getNode(cast<sandboxir::BinaryOperator>(&*It++));
292   auto *AddN1 = DAG.getNode(cast<sandboxir::BinaryOperator>(&*It++));
293   auto *AddN2 = DAG.getNode(cast<sandboxir::BinaryOperator>(&*It++));
294   auto *CallN = DAG.getNode(cast<sandboxir::CallInst>(&*It++));
295   auto *StN = DAG.getNode(cast<sandboxir::StoreInst>(&*It++));
296   auto *RetN = DAG.getNode(cast<sandboxir::ReturnInst>(&*It++));
297 
298   // Check preds().
299   EXPECT_THAT(AddN0->preds(DAG), testing::ElementsAre());
300   EXPECT_THAT(AddN1->preds(DAG), testing::ElementsAre());
301   EXPECT_THAT(AddN2->preds(DAG), testing::ElementsAre(AddN0, AddN1));
302   EXPECT_THAT(CallN->preds(DAG), testing::ElementsAre(AddN1));
303   EXPECT_THAT(StN->preds(DAG),
304               testing::UnorderedElementsAre(CallN, CallN, AddN2));
305   EXPECT_THAT(RetN->preds(DAG), testing::ElementsAre(AddN2));
306 
307   // Check UnscheduledSuccs.
308   EXPECT_EQ(AddN0->getNumUnscheduledSuccs(), 1u); // AddN2
309   EXPECT_EQ(AddN1->getNumUnscheduledSuccs(), 2u); // AddN2, CallN
310   EXPECT_EQ(AddN2->getNumUnscheduledSuccs(), 2u); // StN, RetN
311   EXPECT_EQ(CallN->getNumUnscheduledSuccs(), 2u); // StN, StN
312   EXPECT_EQ(StN->getNumUnscheduledSuccs(), 0u);
313   EXPECT_EQ(RetN->getNumUnscheduledSuccs(), 0u);
314 }
315 
316 TEST_F(DependencyGraphTest, MemDGNode_getPrevNode_getNextNode) {
317   parseIR(C, R"IR(
318 define void @foo(ptr %ptr, i8 %v0, i8 %v1) {
319   store i8 %v0, ptr %ptr
320   add i8 %v0, %v0
321   store i8 %v1, ptr %ptr
322   ret void
323 }
324 )IR");
325   llvm::Function *LLVMF = &*M->getFunction("foo");
326   sandboxir::Context Ctx(C);
327   auto *F = Ctx.createFunction(LLVMF);
328   auto *BB = &*F->begin();
329   auto It = BB->begin();
330   auto *S0 = cast<sandboxir::StoreInst>(&*It++);
331   [[maybe_unused]] auto *Add = cast<sandboxir::BinaryOperator>(&*It++);
332   auto *S1 = cast<sandboxir::StoreInst>(&*It++);
333   [[maybe_unused]] auto *Ret = cast<sandboxir::ReturnInst>(&*It++);
334 
335   sandboxir::DependencyGraph DAG(getAA(*LLVMF), Ctx);
336   DAG.extend({&*BB->begin(), BB->getTerminator()});
337 
338   auto *S0N = cast<sandboxir::MemDGNode>(DAG.getNode(S0));
339   auto *S1N = cast<sandboxir::MemDGNode>(DAG.getNode(S1));
340 
341   EXPECT_EQ(S0N->getPrevNode(), nullptr);
342   EXPECT_EQ(S0N->getNextNode(), S1N);
343 
344   EXPECT_EQ(S1N->getPrevNode(), S0N);
345   EXPECT_EQ(S1N->getNextNode(), nullptr);
346 }
347 
348 TEST_F(DependencyGraphTest, DGNodeRange) {
349   parseIR(C, R"IR(
350 define void @foo(ptr %ptr, i8 %v0, i8 %v1) {
351   add i8 %v0, %v0
352   store i8 %v0, ptr %ptr
353   add i8 %v0, %v0
354   store i8 %v1, ptr %ptr
355   ret void
356 }
357 )IR");
358   llvm::Function *LLVMF = &*M->getFunction("foo");
359   sandboxir::Context Ctx(C);
360   auto *F = Ctx.createFunction(LLVMF);
361   auto *BB = &*F->begin();
362   auto It = BB->begin();
363   auto *Add0 = cast<sandboxir::BinaryOperator>(&*It++);
364   auto *S0 = cast<sandboxir::StoreInst>(&*It++);
365   auto *Add1 = cast<sandboxir::BinaryOperator>(&*It++);
366   auto *S1 = cast<sandboxir::StoreInst>(&*It++);
367   auto *Ret = cast<sandboxir::ReturnInst>(&*It++);
368 
369   sandboxir::DependencyGraph DAG(getAA(*LLVMF), Ctx);
370   DAG.extend({&*BB->begin(), BB->getTerminator()});
371 
372   auto *S0N = cast<sandboxir::MemDGNode>(DAG.getNode(S0));
373   auto *S1N = cast<sandboxir::MemDGNode>(DAG.getNode(S1));
374 
375   // Check getTopMemDGNode().
376   using B = sandboxir::MemDGNodeIntervalBuilder;
377   using InstrInterval = sandboxir::Interval<sandboxir::Instruction>;
378   EXPECT_EQ(B::getTopMemDGNode(InstrInterval(S0, S0), DAG), S0N);
379   EXPECT_EQ(B::getTopMemDGNode(InstrInterval(S0, Ret), DAG), S0N);
380   EXPECT_EQ(B::getTopMemDGNode(InstrInterval(Add0, Add1), DAG), S0N);
381   EXPECT_EQ(B::getTopMemDGNode(InstrInterval(Add0, Add0), DAG), nullptr);
382 
383   // Check getBotMemDGNode().
384   EXPECT_EQ(B::getBotMemDGNode(InstrInterval(S1, S1), DAG), S1N);
385   EXPECT_EQ(B::getBotMemDGNode(InstrInterval(Add0, S1), DAG), S1N);
386   EXPECT_EQ(B::getBotMemDGNode(InstrInterval(Add0, Ret), DAG), S1N);
387   EXPECT_EQ(B::getBotMemDGNode(InstrInterval(Ret, Ret), DAG), nullptr);
388 
389   // Check empty range.
390   EXPECT_THAT(sandboxir::MemDGNodeIntervalBuilder::makeEmpty(),
391               testing::ElementsAre());
392 
393   // Returns the pointers in Range.
394   auto getPtrVec = [](const auto &Range) {
395     SmallVector<const sandboxir::DGNode *> Vec;
396     for (const sandboxir::DGNode &N : Range)
397       Vec.push_back(&N);
398     return Vec;
399   };
400   // Both TopN and BotN are memory.
401   EXPECT_THAT(
402       getPtrVec(sandboxir::MemDGNodeIntervalBuilder::make({S0, S1}, DAG)),
403       testing::ElementsAre(S0N, S1N));
404   // Only TopN is memory.
405   EXPECT_THAT(
406       getPtrVec(sandboxir::MemDGNodeIntervalBuilder::make({S0, Ret}, DAG)),
407       testing::ElementsAre(S0N, S1N));
408   EXPECT_THAT(
409       getPtrVec(sandboxir::MemDGNodeIntervalBuilder::make({S0, Add1}, DAG)),
410       testing::ElementsAre(S0N));
411   // Only BotN is memory.
412   EXPECT_THAT(
413       getPtrVec(sandboxir::MemDGNodeIntervalBuilder::make({Add0, S1}, DAG)),
414       testing::ElementsAre(S0N, S1N));
415   EXPECT_THAT(
416       getPtrVec(sandboxir::MemDGNodeIntervalBuilder::make({Add0, S0}, DAG)),
417       testing::ElementsAre(S0N));
418   // Neither TopN or BotN is memory.
419   EXPECT_THAT(
420       getPtrVec(sandboxir::MemDGNodeIntervalBuilder::make({Add0, Ret}, DAG)),
421       testing::ElementsAre(S0N, S1N));
422   EXPECT_THAT(
423       getPtrVec(sandboxir::MemDGNodeIntervalBuilder::make({Add0, Add0}, DAG)),
424       testing::ElementsAre());
425 }
426 
427 TEST_F(DependencyGraphTest, AliasingStores) {
428   parseIR(C, R"IR(
429 define void @foo(ptr %ptr, i8 %v0, i8 %v1) {
430   store i8 %v0, ptr %ptr
431   store i8 %v1, ptr %ptr
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), Ctx);
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   EXPECT_TRUE(Store0N->memPreds().empty());
448   EXPECT_THAT(Store1N->memPreds(), testing::ElementsAre(Store0N));
449   EXPECT_TRUE(RetN->preds(DAG).empty());
450 }
451 
452 TEST_F(DependencyGraphTest, NonAliasingStores) {
453   parseIR(C, R"IR(
454 define void @foo(ptr noalias %ptr0, ptr noalias %ptr1, i8 %v0, i8 %v1) {
455   store i8 %v0, ptr %ptr0
456   store i8 %v1, ptr %ptr1
457   ret void
458 }
459 )IR");
460   llvm::Function *LLVMF = &*M->getFunction("foo");
461   sandboxir::Context Ctx(C);
462   auto *F = Ctx.createFunction(LLVMF);
463   auto *BB = &*F->begin();
464   sandboxir::DependencyGraph DAG(getAA(*LLVMF), Ctx);
465   DAG.extend({&*BB->begin(), BB->getTerminator()});
466   auto It = BB->begin();
467   auto *Store0N = cast<sandboxir::MemDGNode>(
468       DAG.getNode(cast<sandboxir::StoreInst>(&*It++)));
469   auto *Store1N = cast<sandboxir::MemDGNode>(
470       DAG.getNode(cast<sandboxir::StoreInst>(&*It++)));
471   auto *RetN = DAG.getNode(cast<sandboxir::ReturnInst>(&*It++));
472   // We expect no dependencies because the stores don't alias.
473   EXPECT_TRUE(Store0N->memPreds().empty());
474   EXPECT_TRUE(Store1N->memPreds().empty());
475   EXPECT_TRUE(RetN->preds(DAG).empty());
476 }
477 
478 TEST_F(DependencyGraphTest, VolatileLoads) {
479   parseIR(C, R"IR(
480 define void @foo(ptr noalias %ptr0, ptr noalias %ptr1) {
481   %ld0 = load volatile i8, ptr %ptr0
482   %ld1 = load volatile i8, 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), Ctx);
491   DAG.extend({&*BB->begin(), BB->getTerminator()});
492   auto It = BB->begin();
493   auto *Ld0N = cast<sandboxir::MemDGNode>(
494       DAG.getNode(cast<sandboxir::LoadInst>(&*It++)));
495   auto *Ld1N = cast<sandboxir::MemDGNode>(
496       DAG.getNode(cast<sandboxir::LoadInst>(&*It++)));
497   auto *RetN = DAG.getNode(cast<sandboxir::ReturnInst>(&*It++));
498   EXPECT_TRUE(Ld0N->memPreds().empty());
499   EXPECT_THAT(Ld1N->memPreds(), testing::ElementsAre(Ld0N));
500   EXPECT_TRUE(RetN->preds(DAG).empty());
501 }
502 
503 TEST_F(DependencyGraphTest, VolatileSotres) {
504   parseIR(C, R"IR(
505 define void @foo(ptr noalias %ptr0, ptr noalias %ptr1, i8 %v) {
506   store volatile i8 %v, ptr %ptr0
507   store volatile i8 %v, ptr %ptr1
508   ret void
509 }
510 )IR");
511   llvm::Function *LLVMF = &*M->getFunction("foo");
512   sandboxir::Context Ctx(C);
513   auto *F = Ctx.createFunction(LLVMF);
514   auto *BB = &*F->begin();
515   sandboxir::DependencyGraph DAG(getAA(*LLVMF), Ctx);
516   DAG.extend({&*BB->begin(), BB->getTerminator()});
517   auto It = BB->begin();
518   auto *Store0N = cast<sandboxir::MemDGNode>(
519       DAG.getNode(cast<sandboxir::StoreInst>(&*It++)));
520   auto *Store1N = cast<sandboxir::MemDGNode>(
521       DAG.getNode(cast<sandboxir::StoreInst>(&*It++)));
522   auto *RetN = DAG.getNode(cast<sandboxir::ReturnInst>(&*It++));
523   EXPECT_TRUE(Store0N->memPreds().empty());
524   EXPECT_THAT(Store1N->memPreds(), testing::ElementsAre(Store0N));
525   EXPECT_TRUE(RetN->preds(DAG).empty());
526 }
527 
528 TEST_F(DependencyGraphTest, Call) {
529   parseIR(C, R"IR(
530 declare void @bar1()
531 declare void @bar2()
532 define void @foo(float %v1, float %v2) {
533   call void @bar1()
534   %add = fadd float %v1, %v2
535   call void @bar2()
536   ret void
537 }
538 )IR");
539   Function *LLVMF = M->getFunction("foo");
540 
541   sandboxir::Context Ctx(C);
542   auto *F = Ctx.createFunction(LLVMF);
543   auto *BB = &*F->begin();
544 
545   sandboxir::DependencyGraph DAG(getAA(*LLVMF), Ctx);
546   DAG.extend({&*BB->begin(), BB->getTerminator()->getPrevNode()});
547 
548   auto It = BB->begin();
549   auto *Call1N = cast<sandboxir::MemDGNode>(DAG.getNode(&*It++));
550   auto *AddN = DAG.getNode(&*It++);
551   auto *Call2N = cast<sandboxir::MemDGNode>(DAG.getNode(&*It++));
552 
553   EXPECT_THAT(Call1N->memPreds(), testing::ElementsAre());
554   EXPECT_THAT(AddN->preds(DAG), testing::ElementsAre());
555   EXPECT_THAT(Call2N->memPreds(), testing::ElementsAre(Call1N));
556 }
557 
558 // Check that there is a dependency: stacksave -> alloca -> stackrestore.
559 TEST_F(DependencyGraphTest, StackSaveRestoreInAlloca) {
560   parseIR(C, R"IR(
561 declare ptr @llvm.stacksave()
562 declare void @llvm.stackrestore(ptr %ptr)
563 
564 define void @foo() {
565   %stack0 = call ptr @llvm.stacksave()        ; Should depend on store
566   %alloca0 = alloca inalloca i8               ; Should depend on stacksave
567   call void @llvm.stackrestore(ptr %stack0)   ; Should depend transiently on %alloca0
568   ret void
569 }
570 )IR");
571   Function *LLVMF = M->getFunction("foo");
572 
573   sandboxir::Context Ctx(C);
574   auto *F = Ctx.createFunction(LLVMF);
575   auto *BB = &*F->begin();
576 
577   sandboxir::DependencyGraph DAG(getAA(*LLVMF), Ctx);
578   DAG.extend({&*BB->begin(), BB->getTerminator()->getPrevNode()});
579 
580   auto It = BB->begin();
581   auto *StackSaveN = DAG.getNode(&*It++);
582   auto *AllocaN = DAG.getNode(&*It++);
583   auto *StackRestoreN = DAG.getNode(&*It++);
584 
585   EXPECT_TRUE(memDependency(AllocaN, StackRestoreN));
586   EXPECT_TRUE(memDependency(StackSaveN, AllocaN));
587 }
588 
589 // Checks that stacksave and stackrestore depend on other mem instrs.
590 TEST_F(DependencyGraphTest, StackSaveRestoreDependOnOtherMem) {
591   parseIR(C, R"IR(
592 declare ptr @llvm.stacksave()
593 declare void @llvm.stackrestore(ptr %ptr)
594 
595 define void @foo(i8 %v0, i8 %v1, ptr %ptr) {
596   store volatile i8 %v0, ptr %ptr, align 4
597   %stack0 = call ptr @llvm.stacksave()       ; Should depend on store
598   call void @llvm.stackrestore(ptr %stack0)  ; Should depend on stacksave
599   store volatile i8 %v1, ptr %ptr, align 4   ; Should depend on stackrestore
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), Ctx);
610   DAG.extend({&*BB->begin(), BB->getTerminator()->getPrevNode()});
611 
612   auto It = BB->begin();
613   auto *Store0N = DAG.getNode(&*It++);
614   auto *StackSaveN = DAG.getNode(&*It++);
615   auto *StackRestoreN = DAG.getNode(&*It++);
616   auto *Store1N = DAG.getNode(&*It++);
617 
618   EXPECT_TRUE(memDependency(Store0N, StackSaveN));
619   EXPECT_TRUE(memDependency(StackSaveN, StackRestoreN));
620   EXPECT_TRUE(memDependency(StackRestoreN, Store1N));
621 }
622 
623 // Make sure there is a dependency between a stackrestore and an alloca.
624 TEST_F(DependencyGraphTest, StackRestoreAndInAlloca) {
625   parseIR(C, R"IR(
626 declare void @llvm.stackrestore(ptr %ptr)
627 
628 define void @foo(ptr %ptr) {
629   call void @llvm.stackrestore(ptr %ptr)
630   %alloca0 = alloca inalloca i8              ; Should depend on stackrestore
631   ret void
632 }
633 )IR");
634   Function *LLVMF = M->getFunction("foo");
635 
636   sandboxir::Context Ctx(C);
637   auto *F = Ctx.createFunction(LLVMF);
638   auto *BB = &*F->begin();
639 
640   sandboxir::DependencyGraph DAG(getAA(*LLVMF), Ctx);
641   DAG.extend({&*BB->begin(), BB->getTerminator()->getPrevNode()});
642 
643   auto It = BB->begin();
644   auto *StackRestoreN = DAG.getNode(&*It++);
645   auto *AllocaN = DAG.getNode(&*It++);
646 
647   EXPECT_TRUE(memDependency(StackRestoreN, AllocaN));
648 }
649 
650 // Make sure there is a dependency between the alloca and stacksave
651 TEST_F(DependencyGraphTest, StackSaveAndInAlloca) {
652   parseIR(C, R"IR(
653 declare ptr @llvm.stacksave()
654 
655 define void @foo(ptr %ptr) {
656   %alloca0 = alloca inalloca i8              ; Should depend on stackrestore
657   %stack0 = call ptr @llvm.stacksave()       ; Should depend on alloca0
658   ret void
659 }
660 )IR");
661   Function *LLVMF = M->getFunction("foo");
662 
663   sandboxir::Context Ctx(C);
664   auto *F = Ctx.createFunction(LLVMF);
665   auto *BB = &*F->begin();
666 
667   sandboxir::DependencyGraph DAG(getAA(*LLVMF), Ctx);
668   DAG.extend({&*BB->begin(), BB->getTerminator()->getPrevNode()});
669 
670   auto It = BB->begin();
671   auto *AllocaN = DAG.getNode(&*It++);
672   auto *StackSaveN = DAG.getNode(&*It++);
673 
674   EXPECT_TRUE(memDependency(AllocaN, StackSaveN));
675 }
676 
677 // A non-InAlloca in a stacksave-stackrestore region does not need extra
678 // dependencies.
679 TEST_F(DependencyGraphTest, StackSaveRestoreNoInAlloca) {
680   parseIR(C, R"IR(
681 declare ptr @llvm.stacksave()
682 declare void @llvm.stackrestore(ptr %ptr)
683 declare void @use(ptr %ptr)
684 
685 define void @foo() {
686   %stack = call ptr @llvm.stacksave()
687   %alloca1 = alloca i8                         ; No dependency
688   call void @llvm.stackrestore(ptr %stack)
689   ret void
690 }
691 )IR");
692   Function *LLVMF = M->getFunction("foo");
693 
694   sandboxir::Context Ctx(C);
695   auto *F = Ctx.createFunction(LLVMF);
696   auto *BB = &*F->begin();
697 
698   sandboxir::DependencyGraph DAG(getAA(*LLVMF), Ctx);
699   DAG.extend({&*BB->begin(), BB->getTerminator()->getPrevNode()});
700 
701   auto It = BB->begin();
702   auto *StackSaveN = DAG.getNode(&*It++);
703   auto *AllocaN = DAG.getNode(&*It++);
704   auto *StackRestoreN = DAG.getNode(&*It++);
705 
706   EXPECT_FALSE(memDependency(StackSaveN, AllocaN));
707   EXPECT_FALSE(memDependency(AllocaN, StackRestoreN));
708 }
709 
710 TEST_F(DependencyGraphTest, Extend) {
711   parseIR(C, R"IR(
712 define void @foo(ptr %ptr, i8 %v1, i8 %v2, i8 %v3, i8 %v4, i8 %v5) {
713   store i8 %v1, ptr %ptr
714   store i8 %v2, ptr %ptr
715   store i8 %v3, ptr %ptr
716   store i8 %v4, ptr %ptr
717   store i8 %v5, ptr %ptr
718   ret void
719 }
720 )IR");
721   llvm::Function *LLVMF = &*M->getFunction("foo");
722   sandboxir::Context Ctx(C);
723   auto *F = Ctx.createFunction(LLVMF);
724   auto *BB = &*F->begin();
725   auto It = BB->begin();
726   auto *S1 = cast<sandboxir::StoreInst>(&*It++);
727   auto *S2 = cast<sandboxir::StoreInst>(&*It++);
728   auto *S3 = cast<sandboxir::StoreInst>(&*It++);
729   auto *S4 = cast<sandboxir::StoreInst>(&*It++);
730   auto *S5 = cast<sandboxir::StoreInst>(&*It++);
731   sandboxir::DependencyGraph DAG(getAA(*LLVMF), Ctx);
732   {
733     // Scenario 1: Build new DAG
734     auto NewIntvl = DAG.extend({S3, S3});
735     EXPECT_EQ(NewIntvl, sandboxir::Interval<sandboxir::Instruction>(S3, S3));
736     EXPECT_EQ(DAG.getInterval().top(), S3);
737     EXPECT_EQ(DAG.getInterval().bottom(), S3);
738     [[maybe_unused]] auto *S3N = cast<sandboxir::MemDGNode>(DAG.getNode(S3));
739     // Check UnscheduledSuccs.
740     EXPECT_EQ(S3N->getNumUnscheduledSuccs(), 0u);
741   }
742   {
743     // Scenario 2: Extend below
744     auto NewIntvl = DAG.extend({S5, S5});
745     EXPECT_EQ(NewIntvl, sandboxir::Interval<sandboxir::Instruction>(S4, S5));
746     auto *S3N = cast<sandboxir::MemDGNode>(DAG.getNode(S3));
747     auto *S4N = cast<sandboxir::MemDGNode>(DAG.getNode(S4));
748     auto *S5N = cast<sandboxir::MemDGNode>(DAG.getNode(S5));
749     EXPECT_TRUE(S4N->hasMemPred(S3N));
750     EXPECT_TRUE(S5N->hasMemPred(S4N));
751     EXPECT_TRUE(S5N->hasMemPred(S3N));
752     // Check UnscheduledSuccs.
753     EXPECT_EQ(S3N->getNumUnscheduledSuccs(), 2u); // S4N, S5N
754     EXPECT_EQ(S4N->getNumUnscheduledSuccs(), 1u); // S5N
755     EXPECT_EQ(S5N->getNumUnscheduledSuccs(), 0u);
756   }
757   {
758     // Scenario 3: Extend above
759     auto NewIntvl = DAG.extend({S1, S2});
760     EXPECT_EQ(NewIntvl, sandboxir::Interval<sandboxir::Instruction>(S1, S2));
761     auto *S1N = cast<sandboxir::MemDGNode>(DAG.getNode(S1));
762     auto *S2N = cast<sandboxir::MemDGNode>(DAG.getNode(S2));
763     auto *S3N = cast<sandboxir::MemDGNode>(DAG.getNode(S3));
764     auto *S4N = cast<sandboxir::MemDGNode>(DAG.getNode(S4));
765     auto *S5N = cast<sandboxir::MemDGNode>(DAG.getNode(S5));
766 
767     EXPECT_TRUE(S2N->hasMemPred(S1N));
768 
769     EXPECT_TRUE(S3N->hasMemPred(S2N));
770     EXPECT_TRUE(S3N->hasMemPred(S1N));
771 
772     EXPECT_TRUE(S4N->hasMemPred(S3N));
773     EXPECT_TRUE(S4N->hasMemPred(S2N));
774     EXPECT_TRUE(S4N->hasMemPred(S1N));
775 
776     EXPECT_TRUE(S5N->hasMemPred(S4N));
777     EXPECT_TRUE(S5N->hasMemPred(S3N));
778     EXPECT_TRUE(S5N->hasMemPred(S2N));
779     EXPECT_TRUE(S5N->hasMemPred(S1N));
780 
781     // Check UnscheduledSuccs.
782     EXPECT_EQ(S1N->getNumUnscheduledSuccs(), 4u); // S2N, S3N, S4N, S5N
783     EXPECT_EQ(S2N->getNumUnscheduledSuccs(), 3u); // S3N, S4N, S5N
784     EXPECT_EQ(S3N->getNumUnscheduledSuccs(), 2u); // S4N, S5N
785     EXPECT_EQ(S4N->getNumUnscheduledSuccs(), 1u); // S5N
786     EXPECT_EQ(S5N->getNumUnscheduledSuccs(), 0u);
787   }
788 
789   {
790     // Check UnscheduledSuccs when a node is scheduled
791     sandboxir::DependencyGraph DAG(getAA(*LLVMF), Ctx);
792     DAG.extend({S2, S2});
793     auto *S2N = cast<sandboxir::MemDGNode>(DAG.getNode(S2));
794     S2N->setScheduled(true);
795 
796     DAG.extend({S1, S1});
797     auto *S1N = cast<sandboxir::MemDGNode>(DAG.getNode(S1));
798     EXPECT_EQ(S1N->getNumUnscheduledSuccs(), 0u); // S1 is scheduled
799   }
800 }
801 
802 TEST_F(DependencyGraphTest, CreateInstrCallback) {
803   parseIR(C, R"IR(
804 define void @foo(ptr %ptr, ptr noalias %ptr2, i8 %v1, i8 %v2, i8 %v3, i8 %arg) {
805   store i8 %v1, ptr %ptr
806   store i8 %v2, ptr %ptr
807   store i8 %v3, ptr %ptr
808   ret void
809 }
810 )IR");
811   llvm::Function *LLVMF = &*M->getFunction("foo");
812   sandboxir::Context Ctx(C);
813   auto *F = Ctx.createFunction(LLVMF);
814   auto *BB = &*F->begin();
815   auto It = BB->begin();
816   auto *S1 = cast<sandboxir::StoreInst>(&*It++);
817   auto *S2 = cast<sandboxir::StoreInst>(&*It++);
818   auto *S3 = cast<sandboxir::StoreInst>(&*It++);
819   auto *Ret = cast<sandboxir::ReturnInst>(&*It++);
820 
821   // Check new instruction callback.
822   sandboxir::DependencyGraph DAG(getAA(*LLVMF), Ctx);
823   DAG.extend({S1, Ret});
824   auto *Arg = F->getArg(3);
825   auto *Ptr = S1->getPointerOperand();
826   {
827     sandboxir::StoreInst *NewS =
828         sandboxir::StoreInst::create(Arg, Ptr, Align(8), S3->getIterator(),
829                                      /*IsVolatile=*/true, Ctx);
830     auto *NewSN = DAG.getNode(NewS);
831     EXPECT_TRUE(NewSN != nullptr);
832 
833     // Check the MemDGNode chain.
834     auto *S2MemN = cast<sandboxir::MemDGNode>(DAG.getNode(S2));
835     auto *NewMemSN = cast<sandboxir::MemDGNode>(NewSN);
836     auto *S3MemN = cast<sandboxir::MemDGNode>(DAG.getNode(S3));
837     EXPECT_EQ(S2MemN->getNextNode(), NewMemSN);
838     EXPECT_EQ(NewMemSN->getPrevNode(), S2MemN);
839     EXPECT_EQ(NewMemSN->getNextNode(), S3MemN);
840     EXPECT_EQ(S3MemN->getPrevNode(), NewMemSN);
841   }
842 
843   {
844     // Also check if new node is at the end of the BB, after Ret.
845     sandboxir::StoreInst *NewS =
846         sandboxir::StoreInst::create(Arg, Ptr, Align(8), BB->end(),
847                                      /*IsVolatile=*/true, Ctx);
848     // Check the MemDGNode chain.
849     auto *S3MemN = cast<sandboxir::MemDGNode>(DAG.getNode(S3));
850     auto *NewMemSN = cast<sandboxir::MemDGNode>(DAG.getNode(NewS));
851     EXPECT_EQ(S3MemN->getNextNode(), NewMemSN);
852     EXPECT_EQ(NewMemSN->getPrevNode(), S3MemN);
853     EXPECT_EQ(NewMemSN->getNextNode(), nullptr);
854   }
855 
856   // TODO: Check the dependencies to/from NewSN after they land.
857 }
858 
859 TEST_F(DependencyGraphTest, EraseInstrCallback) {
860   parseIR(C, R"IR(
861 define void @foo(ptr %ptr, i8 %v1, i8 %v2, i8 %v3, i8 %arg) {
862   store i8 %v1, ptr %ptr
863   store i8 %v2, ptr %ptr
864   store i8 %v3, ptr %ptr
865   ret void
866 }
867 )IR");
868   llvm::Function *LLVMF = &*M->getFunction("foo");
869   sandboxir::Context Ctx(C);
870   auto *F = Ctx.createFunction(LLVMF);
871   auto *BB = &*F->begin();
872   auto It = BB->begin();
873   auto *S1 = cast<sandboxir::StoreInst>(&*It++);
874   auto *S2 = cast<sandboxir::StoreInst>(&*It++);
875   auto *S3 = cast<sandboxir::StoreInst>(&*It++);
876 
877   // Check erase instruction callback.
878   sandboxir::DependencyGraph DAG(getAA(*LLVMF), Ctx);
879   DAG.extend({S1, S3});
880   S2->eraseFromParent();
881   auto *DeletedN = DAG.getNodeOrNull(S2);
882   EXPECT_TRUE(DeletedN == nullptr);
883 
884   // Check the MemDGNode chain.
885   auto *S1MemN = cast<sandboxir::MemDGNode>(DAG.getNode(S1));
886   auto *S3MemN = cast<sandboxir::MemDGNode>(DAG.getNode(S3));
887   EXPECT_EQ(S1MemN->getNextNode(), S3MemN);
888   EXPECT_EQ(S3MemN->getPrevNode(), S1MemN);
889 
890   // Check the chain when we erase the top node.
891   S1->eraseFromParent();
892   EXPECT_EQ(S3MemN->getPrevNode(), nullptr);
893 
894   // TODO: Check the dependencies to/from NewSN after they land.
895 }
896 
897 TEST_F(DependencyGraphTest, MoveInstrCallback) {
898   parseIR(C, R"IR(
899 define void @foo(ptr %ptr, ptr %ptr2, i8 %v1, i8 %v2, i8 %v3, i8 %arg) {
900   %ld0 = load i8, ptr %ptr2
901   store i8 %v1, ptr %ptr
902   store i8 %v2, ptr %ptr
903   store i8 %v3, ptr %ptr
904   ret void
905 }
906 )IR");
907   llvm::Function *LLVMF = &*M->getFunction("foo");
908   sandboxir::Context Ctx(C);
909   auto *F = Ctx.createFunction(LLVMF);
910   auto *BB = &*F->begin();
911   auto It = BB->begin();
912   auto *Ld = cast<sandboxir::LoadInst>(&*It++);
913   auto *S1 = cast<sandboxir::StoreInst>(&*It++);
914   auto *S2 = cast<sandboxir::StoreInst>(&*It++);
915   auto *S3 = cast<sandboxir::StoreInst>(&*It++);
916 
917   sandboxir::DependencyGraph DAG(getAA(*LLVMF), Ctx);
918   DAG.extend({Ld, S3});
919   auto *LdN = cast<sandboxir::MemDGNode>(DAG.getNode(Ld));
920   auto *S1N = cast<sandboxir::MemDGNode>(DAG.getNode(S1));
921   auto *S2N = cast<sandboxir::MemDGNode>(DAG.getNode(S2));
922   EXPECT_EQ(S1N->getPrevNode(), LdN);
923   S1->moveBefore(Ld);
924   EXPECT_EQ(S1N->getPrevNode(), nullptr);
925   EXPECT_EQ(S1N->getNextNode(), LdN);
926   EXPECT_EQ(LdN->getPrevNode(), S1N);
927   EXPECT_EQ(LdN->getNextNode(), S2N);
928 }
929 
930 // Check that the mem chain is maintained correctly when the move destination is
931 // not a mem node.
932 TEST_F(DependencyGraphTest, MoveInstrCallbackWithNonMemInstrs) {
933   parseIR(C, R"IR(
934 define void @foo(ptr %ptr, i8 %v1, i8 %v2, i8 %arg) {
935   %ld = load i8, ptr %ptr
936   %zext1 = zext i8 %arg to i32
937   %zext2 = zext i8 %arg to i32
938   store i8 %v1, ptr %ptr
939   store i8 %v2, ptr %ptr
940   ret void
941 }
942 )IR");
943   llvm::Function *LLVMF = &*M->getFunction("foo");
944   sandboxir::Context Ctx(C);
945   auto *F = Ctx.createFunction(LLVMF);
946   auto *BB = &*F->begin();
947   auto It = BB->begin();
948   auto *Ld = cast<sandboxir::LoadInst>(&*It++);
949   [[maybe_unused]] auto *Zext1 = cast<sandboxir::CastInst>(&*It++);
950   auto *Zext2 = cast<sandboxir::CastInst>(&*It++);
951   auto *S1 = cast<sandboxir::StoreInst>(&*It++);
952   auto *S2 = cast<sandboxir::StoreInst>(&*It++);
953   auto *Ret = cast<sandboxir::ReturnInst>(&*It++);
954 
955   sandboxir::DependencyGraph DAG(getAA(*LLVMF), Ctx);
956   DAG.extend({Ld, S2});
957   auto *LdN = cast<sandboxir::MemDGNode>(DAG.getNode(Ld));
958   auto *S1N = cast<sandboxir::MemDGNode>(DAG.getNode(S1));
959   auto *S2N = cast<sandboxir::MemDGNode>(DAG.getNode(S2));
960   EXPECT_EQ(LdN->getNextNode(), S1N);
961   EXPECT_EQ(S1N->getNextNode(), S2N);
962 
963   S1->moveBefore(Zext2);
964   EXPECT_EQ(LdN->getNextNode(), S1N);
965   EXPECT_EQ(S1N->getNextNode(), S2N);
966 
967   // Try move right after the end of the DAGInterval.
968   S1->moveBefore(Ret);
969   EXPECT_EQ(S2N->getNextNode(), S1N);
970   EXPECT_EQ(S1N->getNextNode(), nullptr);
971 }
972