1//===- DependencyGraph.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/ADT/ArrayRef.h"
11#include "llvm/SandboxIR/Instruction.h"
12#include "llvm/SandboxIR/Utils.h"
13#include "llvm/Transforms/Vectorize/SandboxVectorizer/Scheduler.h"
14
15namespace llvm::sandboxir {
16
17#ifndef NDEBUG
18StringLiteral schedDirectionToStr(SchedDirection Dir) {
19 switch (Dir) {
20 case SchedDirection::BottomUp:
21 return "BottomUp";
22 case SchedDirection::TopDown:
23 return "TopDown";
24 }
25 llvm_unreachable("Unhandled Dir!");
26}
27#endif // NDEBUG
28
29User::op_iterator PredIterator::skipBadIt(User::op_iterator OpIt,
30 User::op_iterator OpItE,
31 const DependencyGraph &DAG) {
32 auto Skip = [&DAG](auto OpIt) {
33 auto *I = dyn_cast<Instruction>((*OpIt).get());
34 return I == nullptr || DAG.getNode(I) == nullptr;
35 };
36 while (OpIt != OpItE && Skip(OpIt))
37 ++OpIt;
38 return OpIt;
39}
40
41PredIterator::value_type PredIterator::operator*() {
42 // If it's a DGNode then we dereference the operand iterator.
43 if (!isa<MemDGNode>(Val: N)) {
44 assert(OpIt != OpItE && "Can't dereference end iterator!");
45 return DAG->getNode(I: cast<Instruction>(Val: (Value *)*OpIt));
46 }
47 // It's a MemDGNode, so we check if we return either the use-def operand,
48 // or a mem predecessor.
49 if (OpIt != OpItE)
50 return DAG->getNode(I: cast<Instruction>(Val: (Value *)*OpIt));
51 // It's a MemDGNode with OpIt == end, so we need to use MemIt.
52 assert(MemIt != cast<MemDGNode>(N)->MemPreds.end() &&
53 "Cant' dereference end iterator!");
54 return *MemIt;
55}
56
57PredIterator &PredIterator::operator++() {
58 // If it's a DGNode then we increment the use-def iterator.
59 if (!isa<MemDGNode>(Val: N)) {
60 assert(OpIt != OpItE && "Already at end!");
61 ++OpIt;
62 // Skip operands that are not instructions or are outside the DAG.
63 OpIt = PredIterator::skipBadIt(OpIt, OpItE, DAG: *DAG);
64 return *this;
65 }
66 // It's a MemDGNode, so if we are not at the end of the use-def iterator we
67 // need to first increment that.
68 if (OpIt != OpItE) {
69 ++OpIt;
70 // Skip operands that are not instructions or are outside the DAG.
71 OpIt = PredIterator::skipBadIt(OpIt, OpItE, DAG: *DAG);
72 return *this;
73 }
74 // It's a MemDGNode with OpIt == end, so we need to increment MemIt.
75 assert(MemIt != cast<MemDGNode>(N)->MemPreds.end() && "Already at end!");
76 ++MemIt;
77 return *this;
78}
79
80bool PredIterator::operator==(const PredIterator &Other) const {
81 assert(DAG == Other.DAG && "Iterators of different DAGs!");
82 assert(N == Other.N && "Iterators of different nodes!");
83 return OpIt == Other.OpIt && MemIt == Other.MemIt;
84}
85
86User::user_iterator SuccIterator::skipOutOfScope(User::user_iterator UserIt,
87 User::user_iterator UserItE,
88 const DependencyGraph &DAG) {
89 auto Skip = [&DAG](User::user_iterator UserIt) {
90 auto *I = dyn_cast<Instruction>(Val: *UserIt);
91 return I == nullptr || DAG.getNode(I) == nullptr;
92 };
93 while (UserIt != UserItE && Skip(UserIt))
94 ++UserIt;
95 return UserIt;
96}
97
98SuccIterator::value_type SuccIterator::operator*() {
99 // If it's a DGNode then we dereference the user iterator.
100 if (!isa<MemDGNode>(Val: N)) {
101 assert(UserIt != UserItE && "Can't dereference end iterator!");
102 return DAG->getNode(I: cast<Instruction>(Val: (Value *)*UserIt));
103 }
104 // It's a MemDGNode, so we check if we return either the def-use operand,
105 // or a mem predecessor.
106 if (UserIt != UserItE)
107 return DAG->getNode(I: cast<Instruction>(Val: (Value *)*UserIt));
108 // It's a MemDGNode with UserIt == end, so we need to use MemIt.
109 assert(MemIt != cast<MemDGNode>(N)->MemSuccs.end() &&
110 "Cant' dereference end iterator!");
111 return *MemIt;
112}
113
114SuccIterator &SuccIterator::operator++() {
115 // If it's a DGNode then we increment the use-def iterator.
116 if (!isa<MemDGNode>(Val: N)) {
117 assert(UserIt != UserItE && "Already at end!");
118 ++UserIt;
119 // Skip users that are not instructions or are outside the DAG.
120 UserIt = SuccIterator::skipOutOfScope(UserIt, UserItE, DAG: *DAG);
121 return *this;
122 }
123 // It's a MemDGNode, so if we are not at the end of the def-use iterator we
124 // need to first increment that.
125 if (UserIt != UserItE) {
126 ++UserIt;
127 // Skip operands that are not instructions or are outside the DAG.
128 UserIt = SuccIterator::skipOutOfScope(UserIt, UserItE, DAG: *DAG);
129 return *this;
130 }
131 // It's a MemDGNode with UserIt == end, so we need to increment MemIt.
132 assert(MemIt != cast<MemDGNode>(N)->MemSuccs.end() && "Already at end!");
133 ++MemIt;
134 return *this;
135}
136
137bool SuccIterator::operator==(const SuccIterator &Other) const {
138 assert(DAG == Other.DAG && "Iterators of different DAGs!");
139 assert(N == Other.N && "Iterators of different nodes!");
140 return UserIt == Other.UserIt && MemIt == Other.MemIt;
141}
142
143void DGNode::setSchedBundle(SchedBundle &SB) {
144 if (this->SB != nullptr)
145 this->SB->eraseFromBundle(N: this);
146 this->SB = &SB;
147}
148
149DGNode::~DGNode() {
150 if (SB == nullptr)
151 return;
152 SB->eraseFromBundle(N: this);
153}
154
155#ifndef NDEBUG
156void DGNode::print(raw_ostream &OS, bool PrintDeps) const {
157 OS << *I << " Unsched:";
158 if (UnscheduledDeps)
159 OS << UnscheduledDeps;
160 else
161 OS << "N/A";
162 OS << " Sched:" << Scheduled << "\n";
163}
164void DGNode::dump() const { print(dbgs()); }
165void MemDGNode::print(raw_ostream &OS, bool PrintDeps) const {
166 DGNode::print(OS, false);
167 if (PrintDeps) {
168 // Print memory preds.
169 static constexpr unsigned Indent = 4;
170 for (auto *Pred : MemPreds)
171 OS.indent(Indent) << "<-" << *Pred->getInstruction() << "\n";
172 }
173}
174#endif // NDEBUG
175
176MemDGNode *
177MemDGNodeIntervalBuilder::getTopMemDGNode(const Interval<Instruction> &Intvl,
178 const DependencyGraph &DAG) {
179 Instruction *I = Intvl.top();
180 Instruction *BeforeI = Intvl.bottom();
181 // Walk down the chain looking for a mem-dep candidate instruction.
182 while (!DGNode::isMemDepNodeCandidate(I) && I != BeforeI)
183 I = I->getNextNode();
184 if (!DGNode::isMemDepNodeCandidate(I))
185 return nullptr;
186 return cast<MemDGNode>(Val: DAG.getNode(I));
187}
188
189MemDGNode *
190MemDGNodeIntervalBuilder::getBotMemDGNode(const Interval<Instruction> &Intvl,
191 const DependencyGraph &DAG) {
192 Instruction *I = Intvl.bottom();
193 Instruction *AfterI = Intvl.top();
194 // Walk up the chain looking for a mem-dep candidate instruction.
195 while (!DGNode::isMemDepNodeCandidate(I) && I != AfterI)
196 I = I->getPrevNode();
197 if (!DGNode::isMemDepNodeCandidate(I))
198 return nullptr;
199 return cast<MemDGNode>(Val: DAG.getNode(I));
200}
201
202Interval<MemDGNode>
203MemDGNodeIntervalBuilder::make(const Interval<Instruction> &Instrs,
204 DependencyGraph &DAG) {
205 if (Instrs.empty())
206 return {};
207 auto *TopMemN = getTopMemDGNode(Intvl: Instrs, DAG);
208 // If we couldn't find a mem node in range TopN - BotN then it's empty.
209 if (TopMemN == nullptr)
210 return {};
211 auto *BotMemN = getBotMemDGNode(Intvl: Instrs, DAG);
212 assert(BotMemN != nullptr && "TopMemN should be null too!");
213 // Now that we have the mem-dep nodes, create and return the range.
214 return Interval<MemDGNode>(TopMemN, BotMemN);
215}
216
217DependencyGraph::DependencyType
218DependencyGraph::getRoughDepType(Instruction *FromI, Instruction *ToI) {
219 // TODO: Perhaps compile-time improvement by skipping if neither is mem?
220 if (FromI->mayWriteToMemory()) {
221 if (ToI->mayReadFromMemory())
222 return DependencyType::ReadAfterWrite;
223 if (ToI->mayWriteToMemory())
224 return DependencyType::WriteAfterWrite;
225 } else if (FromI->mayReadFromMemory()) {
226 if (ToI->mayWriteToMemory())
227 return DependencyType::WriteAfterRead;
228 }
229 if (isa<sandboxir::PHINode>(Val: FromI) || isa<sandboxir::PHINode>(Val: ToI))
230 return DependencyType::Control;
231 if (ToI->isTerminator())
232 return DependencyType::Control;
233 if (DGNode::isStackSaveOrRestoreIntrinsic(I: FromI) ||
234 DGNode::isStackSaveOrRestoreIntrinsic(I: ToI))
235 return DependencyType::Other;
236 return DependencyType::None;
237}
238
239static bool isOrdered(Instruction *I) {
240 auto IsOrdered = [](Instruction *I) {
241 if (auto *LI = dyn_cast<LoadInst>(Val: I))
242 return !LI->isUnordered();
243 if (auto *SI = dyn_cast<StoreInst>(Val: I))
244 return !SI->isUnordered();
245 if (DGNode::isFenceLike(I))
246 return true;
247 return false;
248 };
249 bool Is = IsOrdered(I);
250 assert((!Is || DGNode::isMemDepCandidate(I)) &&
251 "An ordered instruction must be a MemDepCandidate!");
252 return Is;
253}
254
255bool DependencyGraph::alias(Instruction *SrcI, Instruction *DstI,
256 DependencyType DepType) {
257 std::optional<MemoryLocation> DstLocOpt =
258 Utils::memoryLocationGetOrNone(I: DstI);
259 if (!DstLocOpt)
260 return true;
261 // Check aliasing.
262 assert((SrcI->mayReadFromMemory() || SrcI->mayWriteToMemory()) &&
263 "Expected a mem instr");
264 // TODO: Check AABudget
265 ModRefInfo SrcModRef =
266 isOrdered(I: SrcI)
267 ? ModRefInfo::ModRef
268 : Utils::aliasAnalysisGetModRefInfo(BatchAA&: *BatchAA, I: SrcI, OptLoc: *DstLocOpt);
269 switch (DepType) {
270 case DependencyType::ReadAfterWrite:
271 case DependencyType::WriteAfterWrite:
272 return isModSet(MRI: SrcModRef);
273 case DependencyType::WriteAfterRead:
274 return isRefSet(MRI: SrcModRef);
275 default:
276 llvm_unreachable("Expected only RAW, WAW and WAR!");
277 }
278}
279
280bool DependencyGraph::hasDep(Instruction *SrcI, Instruction *DstI) {
281 DependencyType RoughDepType = getRoughDepType(FromI: SrcI, ToI: DstI);
282 switch (RoughDepType) {
283 case DependencyType::ReadAfterWrite:
284 case DependencyType::WriteAfterWrite:
285 case DependencyType::WriteAfterRead:
286 return alias(SrcI, DstI, DepType: RoughDepType);
287 case DependencyType::Control:
288 // Adding actual dep edges from PHIs/to terminator would just create too
289 // many edges, which would be bad for compile-time.
290 // So we ignore them in the DAG formation but handle them in the
291 // scheduler, while sorting the ready list.
292 return false;
293 case DependencyType::Other:
294 return true;
295 case DependencyType::None:
296 return false;
297 }
298 llvm_unreachable("Unknown DependencyType enum");
299}
300
301void DependencyGraph::scanAndAddDeps(MemDGNode &DstN,
302 const Interval<MemDGNode> &SrcScanRange) {
303 assert(isa<MemDGNode>(DstN) &&
304 "DstN is the mem dep destination, so it must be mem");
305 Instruction *DstI = DstN.getInstruction();
306 // Walk up the instruction chain from ScanRange bottom to top, looking for
307 // memory instrs that may alias.
308 for (MemDGNode &SrcN : reverse(C: SrcScanRange)) {
309 Instruction *SrcI = SrcN.getInstruction();
310 if (hasDep(SrcI, DstI))
311 DstN.addMemPred(PredN: &SrcN, Dir);
312 }
313}
314
315void DependencyGraph::setDefUseUnscheduledSuccs(
316 const Interval<Instruction> &NewInterval) {
317 // +---+
318 // | | Def
319 // | | |
320 // | | v
321 // | | Use
322 // +---+
323 // Set the intra-interval counters in NewInterval.
324 for (Instruction &I : NewInterval) {
325 unsigned CntUnschedPreds = 0;
326 for (Value *Op : I.operands()) {
327 auto *OpI = dyn_cast<Instruction>(Val: Op);
328 if (OpI == nullptr)
329 continue;
330 // TODO: For now don't cross BBs.
331 if (OpI->getParent() != I.getParent())
332 continue;
333 if (!NewInterval.contains(I: OpI))
334 continue;
335 auto *OpN = getNode(I: OpI);
336 if (OpN == nullptr)
337 continue;
338 if (Dir == SchedDirection::BottomUp)
339 OpN->incrUnscheduledDeps();
340 if (!OpN->scheduled())
341 ++CntUnschedPreds;
342 }
343 if (Dir == SchedDirection::TopDown)
344 getNode(I: &I)->UnscheduledDeps = CntUnschedPreds;
345 }
346
347 // Now handle the cross-interval edges.
348 bool NewIsAbove = DAGInterval.empty() || NewInterval.comesBefore(Other: DAGInterval);
349 const auto &TopInterval = NewIsAbove ? NewInterval : DAGInterval;
350 const auto &BotInterval = NewIsAbove ? DAGInterval : NewInterval;
351 // +---+
352 // |Top|
353 // | | Def
354 // +---+ |
355 // | | v
356 // |Bot| Use
357 // | |
358 // +---+
359 // Walk over all instructions in "BotInterval" and update the counter
360 // of operands that are in "TopInterval".
361 for (Instruction &BotI : BotInterval) {
362 auto *BotN = getNode(I: &BotI);
363 // Skip scheduled nodes.
364 if (BotN->scheduled())
365 continue;
366 unsigned CntUnscheduledPreds = 0;
367 for (Value *Op : BotI.operands()) {
368 auto *OpI = dyn_cast<Instruction>(Val: Op);
369 if (OpI == nullptr)
370 continue;
371 auto *OpN = getNode(I: OpI);
372 if (OpN == nullptr)
373 continue;
374 if (!TopInterval.contains(I: OpI))
375 continue;
376 if (!OpN->scheduled()) {
377 if (Dir == SchedDirection::BottomUp)
378 OpN->incrUnscheduledDeps();
379 ++CntUnscheduledPreds;
380 }
381 }
382 if (Dir == SchedDirection::TopDown)
383 *BotN->UnscheduledDeps += CntUnscheduledPreds;
384 }
385}
386
387void DependencyGraph::createNewNodes(const Interval<Instruction> &NewInterval) {
388 // Create Nodes only for the new sections of the DAG.
389 DGNode *LastN = getOrCreateNode(I: NewInterval.top());
390 MemDGNode *LastMemN = dyn_cast<MemDGNode>(Val: LastN);
391 for (Instruction &I : drop_begin(RangeOrContainer: NewInterval)) {
392 auto *N = getOrCreateNode(I: &I);
393 // Build the Mem node chain.
394 if (auto *MemN = dyn_cast<MemDGNode>(Val: N)) {
395 MemN->setPrevNode(LastMemN);
396 LastMemN = MemN;
397 }
398 }
399 // Link new MemDGNode chain with the old one, if any.
400 if (!DAGInterval.empty()) {
401 bool NewIsAbove = NewInterval.comesBefore(Other: DAGInterval);
402 const auto &TopInterval = NewIsAbove ? NewInterval : DAGInterval;
403 const auto &BotInterval = NewIsAbove ? DAGInterval : NewInterval;
404 MemDGNode *LinkTopN =
405 MemDGNodeIntervalBuilder::getBotMemDGNode(Intvl: TopInterval, DAG: *this);
406 MemDGNode *LinkBotN =
407 MemDGNodeIntervalBuilder::getTopMemDGNode(Intvl: BotInterval, DAG: *this);
408 assert((LinkTopN == nullptr || LinkBotN == nullptr ||
409 LinkTopN->comesBefore(LinkBotN)) &&
410 "Wrong order!");
411 if (LinkTopN != nullptr && LinkBotN != nullptr) {
412 LinkTopN->setNextNode(LinkBotN);
413 }
414#ifndef NDEBUG
415 // TODO: Remove this once we've done enough testing.
416 // Check that the chain is well formed.
417 auto UnionIntvl = DAGInterval.getUnionInterval(NewInterval);
418 MemDGNode *ChainTopN =
419 MemDGNodeIntervalBuilder::getTopMemDGNode(UnionIntvl, *this);
420 MemDGNode *ChainBotN =
421 MemDGNodeIntervalBuilder::getBotMemDGNode(UnionIntvl, *this);
422 if (ChainTopN != nullptr && ChainBotN != nullptr) {
423 for (auto *N = ChainTopN->getNextNode(), *LastN = ChainTopN; N != nullptr;
424 LastN = N, N = N->getNextNode()) {
425 assert(N == LastN->getNextNode() && "Bad chain!");
426 assert(N->getPrevNode() == LastN && "Bad chain!");
427 }
428 }
429#endif // NDEBUG
430 }
431
432 setDefUseUnscheduledSuccs(NewInterval);
433}
434
435MemDGNode *DependencyGraph::getMemDGNodeBefore(DGNode *N, bool IncludingN,
436 MemDGNode *SkipN) const {
437 auto *I = N->getInstruction();
438 for (auto *PrevI = IncludingN ? I : I->getPrevNode(); PrevI != nullptr;
439 PrevI = PrevI->getPrevNode()) {
440 auto *PrevN = getNodeOrNull(I: PrevI);
441 if (PrevN == nullptr)
442 return nullptr;
443 auto *PrevMemN = dyn_cast<MemDGNode>(Val: PrevN);
444 if (PrevMemN != nullptr && PrevMemN != SkipN)
445 return PrevMemN;
446 }
447 return nullptr;
448}
449
450MemDGNode *DependencyGraph::getMemDGNodeAfter(DGNode *N, bool IncludingN,
451 MemDGNode *SkipN) const {
452 auto *I = N->getInstruction();
453 for (auto *NextI = IncludingN ? I : I->getNextNode(); NextI != nullptr;
454 NextI = NextI->getNextNode()) {
455 auto *NextN = getNodeOrNull(I: NextI);
456 if (NextN == nullptr)
457 return nullptr;
458 auto *NextMemN = dyn_cast<MemDGNode>(Val: NextN);
459 if (NextMemN != nullptr && NextMemN != SkipN)
460 return NextMemN;
461 }
462 return nullptr;
463}
464
465void DependencyGraph::notifyCreateInstr(Instruction *I) {
466 if (Ctx->getTracker().getState() == Tracker::TrackerState::Reverting)
467 // We don't maintain the DAG while reverting.
468 return;
469 // Nothing to do if the node is not in the focus range of the DAG.
470 if (!(DAGInterval.contains(I) || DAGInterval.touches(Elm: I)))
471 return;
472 // Include `I` into the interval.
473 DAGInterval = DAGInterval.getUnionInterval(Other: {I, I});
474 auto *N = getOrCreateNode(I);
475 auto *MemN = dyn_cast<MemDGNode>(Val: N);
476
477 // Update the MemDGNode chain if this is a memory node.
478 if (MemN != nullptr) {
479 if (auto *PrevMemN = getMemDGNodeBefore(N: MemN, /*IncludingN=*/false)) {
480 PrevMemN->NextMemN = MemN;
481 MemN->PrevMemN = PrevMemN;
482 }
483 if (auto *NextMemN = getMemDGNodeAfter(N: MemN, /*IncludingN=*/false)) {
484 NextMemN->PrevMemN = MemN;
485 MemN->NextMemN = NextMemN;
486 }
487
488 // Add Mem dependencies.
489 // 1. Scan for deps above `I` for deps to `I`: AboveN->MemN.
490 if (DAGInterval.top()->comesBefore(Other: I)) {
491 Interval<Instruction> AboveIntvl(DAGInterval.top(), I->getPrevNode());
492 auto SrcInterval = MemDGNodeIntervalBuilder::make(Instrs: AboveIntvl, DAG&: *this);
493 scanAndAddDeps(DstN&: *MemN, SrcScanRange: SrcInterval);
494 }
495 // 2. Scan for deps below `I` for deps from `I`: MemN->BelowN.
496 if (I->comesBefore(Other: DAGInterval.bottom())) {
497 Interval<Instruction> BelowIntvl(I->getNextNode(), DAGInterval.bottom());
498 for (MemDGNode &BelowN :
499 MemDGNodeIntervalBuilder::make(Instrs: BelowIntvl, DAG&: *this))
500 scanAndAddDeps(DstN&: BelowN, SrcScanRange: Interval<MemDGNode>(MemN, MemN));
501 }
502 }
503}
504
505void DependencyGraph::notifyMoveInstr(Instruction *I, const BBIterator &To) {
506 if (Ctx->getTracker().getState() == Tracker::TrackerState::Reverting)
507 // We don't maintain the DAG while reverting.
508 return;
509 // NOTE: This function runs before `I` moves to its new destination.
510 BasicBlock *BB = To.getNodeParent();
511 assert(!(To != BB->end() && &*To == I->getNextNode()) &&
512 !(To == BB->end() && std::next(I->getIterator()) == BB->end()) &&
513 "Should not have been called if destination is same as origin.");
514
515 // TODO: We can only handle fully internal movements within DAGInterval or at
516 // the borders, i.e., right before the top or right after the bottom.
517 assert(To.getNodeParent() == I->getParent() &&
518 "TODO: We don't support movement across BBs!");
519 assert(
520 (To == std::next(DAGInterval.bottom()->getIterator()) ||
521 (To != BB->end() && std::next(To) == DAGInterval.top()->getIterator()) ||
522 (To != BB->end() && DAGInterval.contains(&*To))) &&
523 "TODO: To should be either within the DAGInterval or right "
524 "before/after it.");
525
526 // Make a copy of the DAGInterval before we update it.
527 auto OrigDAGInterval = DAGInterval;
528
529 // Maintain the DAGInterval.
530 DAGInterval.notifyMoveInstr(I, BeforeIt: To);
531
532 // TODO: Perhaps check if this is legal by checking the dependencies?
533
534 // Update the MemDGNode chain to reflect the instr movement if necessary.
535 DGNode *N = getNodeOrNull(I);
536 if (N == nullptr)
537 return;
538 MemDGNode *MemN = dyn_cast<MemDGNode>(Val: N);
539 if (MemN == nullptr)
540 return;
541
542 // First safely detach it from the existing chain.
543 MemN->detachFromChain();
544
545 // Now insert it back into the chain at the new location.
546 //
547 // We won't always have a DGNode to insert before it. If `To` is BB->end() or
548 // if it points to an instr after DAGInterval.bottom() then we will have to
549 // find a node to insert *after*.
550 //
551 // BB: BB:
552 // I1 I1 ^
553 // I2 I2 | DAGInteval [I1 to I3]
554 // I3 I3 V
555 // I4 I4 <- `To` == right after DAGInterval
556 // <- `To` == BB->end()
557 //
558 if (To == BB->end() ||
559 To == std::next(x: OrigDAGInterval.bottom()->getIterator())) {
560 // If we don't have a node to insert before, find a node to insert after and
561 // update the chain.
562 DGNode *InsertAfterN = getNode(I: &*std::prev(x: To));
563 MemN->setPrevNode(
564 getMemDGNodeBefore(N: InsertAfterN, /*IncludingN=*/true, /*SkipN=*/MemN));
565 } else {
566 // We have a node to insert before, so update the chain.
567 DGNode *BeforeToN = getNode(I: &*To);
568 MemN->setPrevNode(
569 getMemDGNodeBefore(N: BeforeToN, /*IncludingN=*/false, /*SkipN=*/MemN));
570 MemN->setNextNode(
571 getMemDGNodeAfter(N: BeforeToN, /*IncludingN=*/true, /*SkipN=*/MemN));
572 }
573}
574
575void DependencyGraph::notifyEraseInstr(Instruction *I) {
576 if (Ctx->getTracker().getState() == Tracker::TrackerState::Reverting)
577 // We don't maintain the DAG while reverting.
578 return;
579 auto *N = getNode(I);
580 if (N == nullptr)
581 // Early return if there is no DAG node for `I`.
582 return;
583 if (auto *MemN = dyn_cast<MemDGNode>(Val: getNode(I))) {
584 // Update the MemDGNode chain if this is a memory node.
585 auto *PrevMemN = getMemDGNodeBefore(N: MemN, /*IncludingN=*/false);
586 auto *NextMemN = getMemDGNodeAfter(N: MemN, /*IncludingN=*/false);
587 if (PrevMemN != nullptr)
588 PrevMemN->NextMemN = NextMemN;
589 if (NextMemN != nullptr)
590 NextMemN->PrevMemN = PrevMemN;
591
592 // Drop the memory dependencies from both predecessors and successors.
593 while (!MemN->memPreds().empty()) {
594 auto *PredN = *MemN->memPreds().begin();
595 MemN->removeMemPred(PredN, Dir);
596 }
597 while (!MemN->memSuccs().empty()) {
598 auto *SuccN = *MemN->memSuccs().begin();
599 SuccN->removeMemPred(PredN: MemN, Dir);
600 }
601 // NOTE: The unscheduled succs for MemNodes get updated be setMemPred().
602 } else {
603 // If this is a non-mem node we only need to update UnscheduledSuccs.
604 if (!N->scheduled()) {
605 for (auto *PredN : N->preds(DAG&: *this))
606 if (!PredN->scheduled())
607 PredN->decrUnscheduledDeps();
608 for (auto *SuccN : N->succs(DAG&: *this))
609 /// TODO: Does the successor also need to be guarded?
610 SuccN->decrUnscheduledDeps();
611 }
612 }
613 // Finally erase the Node.
614 InstrToNodeMap.erase(Val: I);
615}
616
617void DependencyGraph::notifySetUse(const Use &U, Value *NewSrc) {
618 // If U.User is not in the DAG, then we should not attempt to decrement
619 // CurrSrcN's unscheduled successors.
620 // ------- ------- -
621 // CurrSrc | DAG interval
622 // | NewSrc |
623 // ---|--- ---|--- -
624 // U.User U.User
625 auto *UserI = dyn_cast_or_null<Instruction>(Val: U.getUser());
626 if (UserI == nullptr)
627 return;
628 auto *UserN = getNode(I: UserI);
629 if (UserN == nullptr)
630 return;
631 // If UserN is marked as scheduled then we should not update CrrSrcN' or
632 // NewSrcN's unscheduled successors.
633 if (UserN->scheduled())
634 return;
635 // Update the UnscheduledSuccs counter for both the current source and
636 // NewSrc if needed.
637 if (auto *CurrSrcI = dyn_cast<Instruction>(Val: U.get())) {
638 if (auto *CurrSrcN = getNode(I: CurrSrcI)) {
639 // If CurrSrcN is scheduled there is no point in updating UnscheduledDeps.
640 if (!CurrSrcN->scheduled()) {
641 if (Dir == SchedDirection::BottomUp)
642 CurrSrcN->decrUnscheduledDeps();
643 else
644 UserN->decrUnscheduledDeps();
645 }
646 }
647 }
648 if (auto *NewSrcI = dyn_cast<Instruction>(Val: NewSrc)) {
649 if (auto *NewSrcN = getNode(I: NewSrcI)) {
650 // If CurrSrcN is scheduled there is no point in updating UnscheduleDeps.
651 if (!NewSrcN->scheduled()) {
652 if (Dir == SchedDirection::BottomUp)
653 NewSrcN->incrUnscheduledDeps();
654 else
655 UserN->incrUnscheduledDeps();
656 }
657 }
658 }
659}
660
661Interval<Instruction> DependencyGraph::extend(ArrayRef<Instruction *> Instrs) {
662 if (Instrs.empty())
663 return {};
664
665 Interval<Instruction> InstrsInterval(Instrs);
666 Interval<Instruction> Union = DAGInterval.getUnionInterval(Other: InstrsInterval);
667 auto NewInterval = Union.getSingleDiff(Other: DAGInterval);
668 if (NewInterval.empty())
669 return {};
670
671 createNewNodes(NewInterval);
672
673 // Create the dependencies.
674 //
675 // 1. This is a new DAG, DAGInterval is empty. Fully scan the whole interval.
676 // +---+ - -
677 // | | SrcN | |
678 // | | | | SrcRange |
679 // |New| v | | DstRange
680 // | | DstN - |
681 // | | |
682 // +---+ -
683 // We are scanning for deps with destination in NewInterval and sources in
684 // NewInterval until DstN, for each DstN.
685 auto FullScan = [this](const Interval<Instruction> Intvl) {
686 auto DstRange = MemDGNodeIntervalBuilder::make(Instrs: Intvl, DAG&: *this);
687 if (!DstRange.empty()) {
688 for (MemDGNode &DstN : drop_begin(RangeOrContainer&: DstRange)) {
689 auto SrcRange = Interval<MemDGNode>(DstRange.top(), DstN.getPrevNode());
690 scanAndAddDeps(DstN, SrcScanRange: SrcRange);
691 }
692 }
693 };
694 auto MemDAGInterval = MemDGNodeIntervalBuilder::make(Instrs: DAGInterval, DAG&: *this);
695 if (MemDAGInterval.empty()) {
696 FullScan(NewInterval);
697 }
698 // 2. The new section is below the old section.
699 // +---+ -
700 // | | |
701 // |Old| SrcN |
702 // | | | |
703 // +---+ | | SrcRange
704 // +---+ | | -
705 // | | | | |
706 // |New| v | | DstRange
707 // | | DstN - |
708 // | | |
709 // +---+ -
710 // We are scanning for deps with destination in NewInterval because the deps
711 // in DAGInterval have already been computed. We consider sources in the whole
712 // range including both NewInterval and DAGInterval until DstN, for each DstN.
713 else if (DAGInterval.bottom()->comesBefore(Other: NewInterval.top())) {
714 auto DstRange = MemDGNodeIntervalBuilder::make(Instrs: NewInterval, DAG&: *this);
715 auto SrcRangeFull = MemDAGInterval.getUnionInterval(Other: DstRange);
716 for (MemDGNode &DstN : DstRange) {
717 auto SrcRange =
718 Interval<MemDGNode>(SrcRangeFull.top(), DstN.getPrevNode());
719 scanAndAddDeps(DstN, SrcScanRange: SrcRange);
720 }
721 }
722 // 3. The new section is above the old section.
723 else if (NewInterval.bottom()->comesBefore(Other: DAGInterval.top())) {
724 // +---+ - -
725 // | | SrcN | |
726 // |New| | | SrcRange | DstRange
727 // | | v | |
728 // | | DstN - |
729 // | | |
730 // +---+ -
731 // +---+
732 // |Old|
733 // | |
734 // +---+
735 // When scanning for deps with destination in NewInterval we need to fully
736 // scan the interval. This is the same as the scanning for a new DAG.
737 FullScan(NewInterval);
738
739 // +---+ -
740 // | | |
741 // |New| SrcN | SrcRange
742 // | | | |
743 // | | | |
744 // | | | |
745 // +---+ | -
746 // +---+ | -
747 // |Old| v | DstRange
748 // | | DstN |
749 // +---+ -
750 // When scanning for deps with destination in DAGInterval we need to
751 // consider sources from the NewInterval only, because all intra-DAGInterval
752 // dependencies have already been created.
753 auto DstRangeOld = MemDAGInterval;
754 auto SrcRange = MemDGNodeIntervalBuilder::make(Instrs: NewInterval, DAG&: *this);
755 for (MemDGNode &DstN : DstRangeOld)
756 scanAndAddDeps(DstN, SrcScanRange: SrcRange);
757 } else {
758 llvm_unreachable("We don't expect extending in both directions!");
759 }
760
761 DAGInterval = Union;
762 return NewInterval;
763}
764
765#ifndef NDEBUG
766void DependencyGraph::print(raw_ostream &OS) const {
767 // InstrToNodeMap is unordered so we need to create an ordered vector.
768 SmallVector<DGNode *> Nodes;
769 Nodes.reserve(InstrToNodeMap.size());
770 for (const auto &Pair : InstrToNodeMap)
771 Nodes.push_back(Pair.second.get());
772 // Sort them based on which one comes first in the BB.
773 sort(Nodes, [](DGNode *N1, DGNode *N2) {
774 return N1->getInstruction()->comesBefore(N2->getInstruction());
775 });
776 for (auto *N : Nodes)
777 N->print(OS, /*PrintDeps=*/true);
778}
779
780void DependencyGraph::dump() const {
781 print(dbgs());
782 dbgs() << "\n";
783}
784#endif // NDEBUG
785
786} // namespace llvm::sandboxir
787