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