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::verify(DependencyGraph &DAG) const {
156 if (!Scheduled) {
157 assert(UnscheduledDeps.has_value() && "Expected actual value");
158 // Check UnscheduledDeps.
159 switch (DAG.Dir) {
160 case SchedDirection::BottomUp: {
161 // UnscheduledDeps counts the number of nodes this node depends on.
162 unsigned CntUnschedDeps = 0;
163 for (DGNode *SuccN : succs(DAG))
164 if (!SuccN->scheduled())
165 ++CntUnschedDeps;
166 assert(*UnscheduledDeps == CntUnschedDeps && "Inconsistent UnschedDeps");
167 break;
168 }
169 case SchedDirection::TopDown: {
170 unsigned CntUnschedDeps = 0;
171 for (DGNode *PredN : preds(DAG))
172 if (!PredN->scheduled())
173 ++CntUnschedDeps;
174 assert(*UnscheduledDeps == CntUnschedDeps && "Inconsistent UnschedDeps");
175 break;
176 }
177 }
178 } else {
179 assert(!UnscheduledDeps.has_value() && "Expected nullopt");
180 }
181}
182void DGNode::print(raw_ostream &OS, bool PrintDeps) const {
183 OS << *I << " Unsched:";
184 if (UnscheduledDeps)
185 OS << UnscheduledDeps;
186 else
187 OS << "N/A";
188 OS << " Sched:" << Scheduled << "\n";
189}
190void DGNode::dump() const { print(dbgs()); }
191void MemDGNode::print(raw_ostream &OS, bool PrintDeps) const {
192 DGNode::print(OS, false);
193 if (PrintDeps) {
194 // Print memory preds.
195 static constexpr unsigned Indent = 4;
196 for (auto *Pred : MemPreds)
197 OS.indent(Indent) << "<-" << *Pred->getInstruction() << "\n";
198 for (auto *Succ : MemSuccs)
199 OS.indent(Indent) << "->" << *Succ->getInstruction() << "\n";
200 }
201}
202#endif // NDEBUG
203
204MemDGNode *
205MemDGNodeIntervalBuilder::getTopMemDGNode(const Interval<Instruction> &Intvl,
206 const DependencyGraph &DAG) {
207 Instruction *I = Intvl.top();
208 Instruction *BeforeI = Intvl.bottom();
209 // Walk down the chain looking for a mem-dep candidate instruction.
210 while (!DGNode::isMemDepNodeCandidate(I) && I != BeforeI)
211 I = I->getNextNode();
212 if (!DGNode::isMemDepNodeCandidate(I))
213 return nullptr;
214 return cast<MemDGNode>(Val: DAG.getNode(I));
215}
216
217MemDGNode *
218MemDGNodeIntervalBuilder::getBotMemDGNode(const Interval<Instruction> &Intvl,
219 const DependencyGraph &DAG) {
220 Instruction *I = Intvl.bottom();
221 Instruction *AfterI = Intvl.top();
222 // Walk up the chain looking for a mem-dep candidate instruction.
223 while (!DGNode::isMemDepNodeCandidate(I) && I != AfterI)
224 I = I->getPrevNode();
225 if (!DGNode::isMemDepNodeCandidate(I))
226 return nullptr;
227 return cast<MemDGNode>(Val: DAG.getNode(I));
228}
229
230Interval<MemDGNode>
231MemDGNodeIntervalBuilder::make(const Interval<Instruction> &Instrs,
232 DependencyGraph &DAG) {
233 if (Instrs.empty())
234 return {};
235 auto *TopMemN = getTopMemDGNode(Intvl: Instrs, DAG);
236 // If we couldn't find a mem node in range TopN - BotN then it's empty.
237 if (TopMemN == nullptr)
238 return {};
239 auto *BotMemN = getBotMemDGNode(Intvl: Instrs, DAG);
240 assert(BotMemN != nullptr && "TopMemN should be null too!");
241 // Now that we have the mem-dep nodes, create and return the range.
242 return Interval<MemDGNode>(TopMemN, BotMemN);
243}
244
245DependencyGraph::DependencyType
246DependencyGraph::getRoughDepType(Instruction *FromI, Instruction *ToI) {
247 // TODO: Perhaps compile-time improvement by skipping if neither is mem?
248 if (FromI->mayWriteToMemory()) {
249 if (ToI->mayReadFromMemory())
250 return DependencyType::ReadAfterWrite;
251 if (ToI->mayWriteToMemory())
252 return DependencyType::WriteAfterWrite;
253 } else if (FromI->mayReadFromMemory()) {
254 if (ToI->mayWriteToMemory())
255 return DependencyType::WriteAfterRead;
256 }
257 if (isa<sandboxir::PHINode>(Val: FromI) || isa<sandboxir::PHINode>(Val: ToI))
258 return DependencyType::Control;
259 if (ToI->isTerminator())
260 return DependencyType::Control;
261 if (DGNode::isStackSaveOrRestoreIntrinsic(I: FromI) ||
262 DGNode::isStackSaveOrRestoreIntrinsic(I: ToI))
263 return DependencyType::Other;
264 return DependencyType::None;
265}
266
267static bool isOrdered(Instruction *I) {
268 auto IsOrdered = [](Instruction *I) {
269 if (auto *LI = dyn_cast<LoadInst>(Val: I))
270 return !LI->isUnordered();
271 if (auto *SI = dyn_cast<StoreInst>(Val: I))
272 return !SI->isUnordered();
273 if (DGNode::isFenceLike(I))
274 return true;
275 return false;
276 };
277 bool Is = IsOrdered(I);
278 assert((!Is || DGNode::isMemDepCandidate(I)) &&
279 "An ordered instruction must be a MemDepCandidate!");
280 return Is;
281}
282
283bool DependencyGraph::alias(Instruction *SrcI, Instruction *DstI,
284 DependencyType DepType) {
285 std::optional<MemoryLocation> DstLocOpt =
286 Utils::memoryLocationGetOrNone(I: DstI);
287 if (!DstLocOpt)
288 return true;
289 // Check aliasing.
290 assert((SrcI->mayReadFromMemory() || SrcI->mayWriteToMemory()) &&
291 "Expected a mem instr");
292 // TODO: Check AABudget
293 ModRefInfo SrcModRef =
294 isOrdered(I: SrcI)
295 ? ModRefInfo::ModRef
296 : Utils::aliasAnalysisGetModRefInfo(BatchAA&: *BatchAA, I: SrcI, OptLoc: *DstLocOpt);
297 switch (DepType) {
298 case DependencyType::ReadAfterWrite:
299 case DependencyType::WriteAfterWrite:
300 return isModSet(MRI: SrcModRef);
301 case DependencyType::WriteAfterRead:
302 return isRefSet(MRI: SrcModRef);
303 default:
304 llvm_unreachable("Expected only RAW, WAW and WAR!");
305 }
306}
307
308bool DependencyGraph::hasDep(Instruction *SrcI, Instruction *DstI) {
309 DependencyType RoughDepType = getRoughDepType(FromI: SrcI, ToI: DstI);
310 switch (RoughDepType) {
311 case DependencyType::ReadAfterWrite:
312 case DependencyType::WriteAfterWrite:
313 case DependencyType::WriteAfterRead:
314 return alias(SrcI, DstI, DepType: RoughDepType);
315 case DependencyType::Control:
316 // Adding actual dep edges from PHIs/to terminator would just create too
317 // many edges, which would be bad for compile-time.
318 // So we ignore them in the DAG formation but handle them in the
319 // scheduler, while sorting the ready list.
320 return false;
321 case DependencyType::Other:
322 return true;
323 case DependencyType::None:
324 return false;
325 }
326 llvm_unreachable("Unknown DependencyType enum");
327}
328
329void DependencyGraph::scanAndAddDeps(MemDGNode &DstN,
330 const Interval<MemDGNode> &SrcScanRange) {
331 assert(isa<MemDGNode>(DstN) &&
332 "DstN is the mem dep destination, so it must be mem");
333 Instruction *DstI = DstN.getInstruction();
334 // Walk up the instruction chain from ScanRange bottom to top, looking for
335 // memory instrs that may alias.
336 for (MemDGNode &SrcN : reverse(C: SrcScanRange)) {
337 Instruction *SrcI = SrcN.getInstruction();
338 if (hasDep(SrcI, DstI))
339 DstN.addMemPred(PredN: &SrcN, Dir);
340 }
341}
342
343void DependencyGraph::setDefUseUnscheduledSuccs(
344 const Interval<Instruction> &NewInterval) {
345 // +---+
346 // | | Def
347 // | | |
348 // | | v
349 // | | Use
350 // +---+
351 // Set the intra-interval counters in NewInterval.
352 for (Instruction &I : NewInterval) {
353 unsigned CntUnschedPreds = 0;
354 for (Value *Op : I.operands()) {
355 auto *OpI = dyn_cast<Instruction>(Val: Op);
356 if (OpI == nullptr)
357 continue;
358 // TODO: For now don't cross BBs.
359 if (OpI->getParent() != I.getParent())
360 continue;
361 if (!NewInterval.contains(I: OpI))
362 continue;
363 auto *OpN = getNode(I: OpI);
364 if (OpN == nullptr)
365 continue;
366 if (Dir == SchedDirection::BottomUp)
367 OpN->incrUnscheduledDeps();
368 if (!OpN->scheduled())
369 ++CntUnschedPreds;
370 }
371 if (Dir == SchedDirection::TopDown)
372 getNode(I: &I)->UnscheduledDeps = CntUnschedPreds;
373 }
374
375 // Now handle the cross-interval edges.
376 bool NewIsAbove = DAGInterval.empty() || NewInterval.comesBefore(Other: DAGInterval);
377 const auto &TopInterval = NewIsAbove ? NewInterval : DAGInterval;
378 const auto &BotInterval = NewIsAbove ? DAGInterval : NewInterval;
379 // +---+
380 // |Top|
381 // | | Def
382 // +---+ |
383 // | | v
384 // |Bot| Use
385 // | |
386 // +---+
387 // Walk over all instructions in "BotInterval" and update the counter
388 // of operands that are in "TopInterval".
389 for (Instruction &BotI : BotInterval) {
390 auto *BotN = getNode(I: &BotI);
391 // Skip scheduled nodes.
392 if (BotN->scheduled())
393 continue;
394 unsigned CntUnscheduledPreds = 0;
395 for (Value *Op : BotI.operands()) {
396 auto *OpI = dyn_cast<Instruction>(Val: Op);
397 if (OpI == nullptr)
398 continue;
399 auto *OpN = getNode(I: OpI);
400 if (OpN == nullptr)
401 continue;
402 if (!TopInterval.contains(I: OpI))
403 continue;
404 if (!OpN->scheduled()) {
405 if (Dir == SchedDirection::BottomUp)
406 OpN->incrUnscheduledDeps();
407 ++CntUnscheduledPreds;
408 }
409 }
410 if (Dir == SchedDirection::TopDown)
411 *BotN->UnscheduledDeps += CntUnscheduledPreds;
412 }
413}
414
415void DependencyGraph::createNewNodes(const Interval<Instruction> &NewInterval) {
416 // Create Nodes only for the new sections of the DAG.
417 DGNode *LastN = getOrCreateNode(I: NewInterval.top());
418 MemDGNode *LastMemN = dyn_cast<MemDGNode>(Val: LastN);
419 for (Instruction &I : drop_begin(RangeOrContainer: NewInterval)) {
420 auto *N = getOrCreateNode(I: &I);
421 // Build the Mem node chain.
422 if (auto *MemN = dyn_cast<MemDGNode>(Val: N)) {
423 MemN->setPrevNode(LastMemN);
424 LastMemN = MemN;
425 }
426 }
427 // Link new MemDGNode chain with the old one, if any.
428 if (!DAGInterval.empty()) {
429 bool NewIsAbove = NewInterval.comesBefore(Other: DAGInterval);
430 const auto &TopInterval = NewIsAbove ? NewInterval : DAGInterval;
431 const auto &BotInterval = NewIsAbove ? DAGInterval : NewInterval;
432 MemDGNode *LinkTopN =
433 MemDGNodeIntervalBuilder::getBotMemDGNode(Intvl: TopInterval, DAG: *this);
434 MemDGNode *LinkBotN =
435 MemDGNodeIntervalBuilder::getTopMemDGNode(Intvl: BotInterval, DAG: *this);
436 assert((LinkTopN == nullptr || LinkBotN == nullptr ||
437 LinkTopN->comesBefore(LinkBotN)) &&
438 "Wrong order!");
439 if (LinkTopN != nullptr && LinkBotN != nullptr) {
440 LinkTopN->setNextNode(LinkBotN);
441 }
442#ifndef NDEBUG
443 // TODO: Remove this once we've done enough testing.
444 // Check that the chain is well formed.
445 auto UnionIntvl = DAGInterval.getUnionInterval(NewInterval);
446 MemDGNode *ChainTopN =
447 MemDGNodeIntervalBuilder::getTopMemDGNode(UnionIntvl, *this);
448 MemDGNode *ChainBotN =
449 MemDGNodeIntervalBuilder::getBotMemDGNode(UnionIntvl, *this);
450 if (ChainTopN != nullptr && ChainBotN != nullptr) {
451 for (auto *N = ChainTopN->getNextNode(), *LastN = ChainTopN; N != nullptr;
452 LastN = N, N = N->getNextNode()) {
453 assert(N == LastN->getNextNode() && "Bad chain!");
454 assert(N->getPrevNode() == LastN && "Bad chain!");
455 }
456 }
457#endif // NDEBUG
458 }
459
460 setDefUseUnscheduledSuccs(NewInterval);
461}
462
463MemDGNode *DependencyGraph::getMemDGNodeBefore(DGNode *N, bool IncludingN,
464 MemDGNode *SkipN) const {
465 auto *I = N->getInstruction();
466 for (auto *PrevI = IncludingN ? I : I->getPrevNode(); PrevI != nullptr;
467 PrevI = PrevI->getPrevNode()) {
468 auto *PrevN = getNodeOrNull(I: PrevI);
469 if (PrevN == nullptr)
470 return nullptr;
471 auto *PrevMemN = dyn_cast<MemDGNode>(Val: PrevN);
472 if (PrevMemN != nullptr && PrevMemN != SkipN)
473 return PrevMemN;
474 }
475 return nullptr;
476}
477
478MemDGNode *DependencyGraph::getMemDGNodeAfter(DGNode *N, bool IncludingN,
479 MemDGNode *SkipN) const {
480 auto *I = N->getInstruction();
481 for (auto *NextI = IncludingN ? I : I->getNextNode(); NextI != nullptr;
482 NextI = NextI->getNextNode()) {
483 auto *NextN = getNodeOrNull(I: NextI);
484 if (NextN == nullptr)
485 return nullptr;
486 auto *NextMemN = dyn_cast<MemDGNode>(Val: NextN);
487 if (NextMemN != nullptr && NextMemN != SkipN)
488 return NextMemN;
489 }
490 return nullptr;
491}
492
493void DependencyGraph::notifyCreateInstr(Instruction *I) {
494 if (Ctx->getTracker().getState() == Tracker::TrackerState::Reverting)
495 // We don't maintain the DAG while reverting.
496 return;
497 // Nothing to do if the node is not in the focus range of the DAG.
498 if (!(DAGInterval.contains(I) || DAGInterval.touches(Elm: I)))
499 return;
500 // Include `I` into the interval.
501 DAGInterval = DAGInterval.getUnionInterval(Other: {I, I});
502 auto *N = getOrCreateNode(I);
503 auto *MemN = dyn_cast<MemDGNode>(Val: N);
504
505 if (Sched)
506 Sched->notifyCreateInstrBeforeDAGUpdates(N);
507
508 // Update the MemDGNode chain if this is a memory node.
509 if (MemN != nullptr) {
510 if (auto *PrevMemN = getMemDGNodeBefore(N: MemN, /*IncludingN=*/false)) {
511 PrevMemN->NextMemN = MemN;
512 MemN->PrevMemN = PrevMemN;
513 }
514 if (auto *NextMemN = getMemDGNodeAfter(N: MemN, /*IncludingN=*/false)) {
515 NextMemN->PrevMemN = MemN;
516 MemN->NextMemN = NextMemN;
517 }
518
519 // Add Mem dependencies.
520 // 1. Scan for deps above `I` for deps to `I`: AboveN->MemN.
521 if (DAGInterval.top()->comesBefore(Other: I)) {
522 Interval<Instruction> AboveIntvl(DAGInterval.top(), I->getPrevNode());
523 auto SrcInterval = MemDGNodeIntervalBuilder::make(Instrs: AboveIntvl, DAG&: *this);
524 scanAndAddDeps(DstN&: *MemN, SrcScanRange: SrcInterval);
525 }
526 // 2. Scan for deps below `I` for deps from `I`: MemN->BelowN.
527 if (I->comesBefore(Other: DAGInterval.bottom())) {
528 Interval<Instruction> BelowIntvl(I->getNextNode(), DAGInterval.bottom());
529 for (MemDGNode &BelowN :
530 MemDGNodeIntervalBuilder::make(Instrs: BelowIntvl, DAG&: *this))
531 scanAndAddDeps(DstN&: BelowN, SrcScanRange: Interval<MemDGNode>(MemN, MemN));
532 }
533 }
534 // scanAndAddDeps() updates UnscheduledDeps only for mem dependencies.
535 // During regular DAG creation the UnscheduledDeps for def-used dependencies
536 // are handled by setDefUseUnscheduledSuccs(NewInterval).
537 // Since we are not following that path we need to update UnscheduledDeps for
538 // def-use deps here.
539 if (!N->scheduled()) {
540 switch (Dir) {
541 case SchedDirection::BottomUp:
542 for (Value *Op : I->operands()) {
543 Instruction *OpI = dyn_cast<Instruction>(Val: Op);
544 if (OpI == nullptr)
545 continue;
546 DGNode *OpN = getNode(I: OpI);
547 if (OpN == nullptr)
548 continue;
549 if (!OpN->scheduled())
550 OpN->incrUnscheduledDeps();
551 }
552 for (User *U : I->users()) {
553 Instruction *UI = dyn_cast<Instruction>(Val: U);
554 if (UI == nullptr)
555 continue;
556 DGNode *UN = getNode(I: UI);
557 if (UN == nullptr)
558 continue;
559 if (!UN->scheduled())
560 N->incrUnscheduledDeps();
561 }
562 break;
563 case SchedDirection::TopDown:
564 for (Value *Op : I->operands()) {
565 Instruction *OpI = dyn_cast<Instruction>(Val: Op);
566 if (OpI == nullptr)
567 continue;
568 DGNode *OpN = getNode(I: OpI);
569 if (OpN == nullptr)
570 continue;
571 if (!OpN->scheduled())
572 N->incrUnscheduledDeps();
573 }
574 for (User *U : I->users()) {
575 Instruction *UI = dyn_cast<Instruction>(Val: U);
576 if (UI == nullptr)
577 continue;
578 DGNode *UN = getNode(I: UI);
579 if (UN == nullptr)
580 continue;
581 if (!UN->scheduled())
582 N->incrUnscheduledDeps();
583 }
584 break;
585 }
586 }
587
588 if (Sched != nullptr) {
589 Sched->notifyCreateInstrAfterDAGUpdates(N);
590 }
591#ifndef NDEBUG
592 // TODO: Remove some of the verifiers eventually to save compilation time.
593 verify();
594#endif
595}
596
597void DependencyGraph::notifyMoveInstr(Instruction *I, const BBIterator &To) {
598 if (Ctx->getTracker().getState() == Tracker::TrackerState::Reverting)
599 // We don't maintain the DAG while reverting.
600 return;
601 if (empty())
602 // Nothing to do if already empty.
603 return;
604 // NOTE: This function runs before `I` moves to its new destination.
605 BasicBlock *BB = To.getNodeParent();
606 assert(!(To != BB->end() && &*To == I->getNextNode()) &&
607 !(To == BB->end() && std::next(I->getIterator()) == BB->end()) &&
608 "Should not have been called if destination is same as origin.");
609
610 // TODO: We can only handle fully internal movements within DAGInterval or at
611 // the borders, i.e., right before the top or right after the bottom.
612 assert(To.getNodeParent() == I->getParent() &&
613 "TODO: We don't support movement across BBs!");
614 assert(
615 (To == std::next(DAGInterval.bottom()->getIterator()) ||
616 (To != BB->end() && std::next(To) == DAGInterval.top()->getIterator()) ||
617 (To != BB->end() && DAGInterval.contains(&*To))) &&
618 "TODO: To should be either within the DAGInterval or right "
619 "before/after it.");
620
621 // Make a copy of the DAGInterval before we update it.
622 auto OrigDAGInterval = DAGInterval;
623
624 // Maintain the DAGInterval.
625 DAGInterval.notifyMoveInstr(I, BeforeIt: To);
626
627 // TODO: Perhaps check if this is legal by checking the dependencies?
628
629 // Update the MemDGNode chain to reflect the instr movement if necessary.
630 DGNode *N = getNodeOrNull(I);
631 if (N == nullptr)
632 return;
633 MemDGNode *MemN = dyn_cast<MemDGNode>(Val: N);
634 if (MemN == nullptr)
635 return;
636
637 // First safely detach it from the existing chain.
638 MemN->detachFromChain();
639
640 // Now insert it back into the chain at the new location.
641 //
642 // We won't always have a DGNode to insert before it. If `To` is BB->end() or
643 // if it points to an instr after DAGInterval.bottom() then we will have to
644 // find a node to insert *after*.
645 //
646 // BB: BB:
647 // I1 I1 ^
648 // I2 I2 | DAGInteval [I1 to I3]
649 // I3 I3 V
650 // I4 I4 <- `To` == right after DAGInterval
651 // <- `To` == BB->end()
652 //
653 if (To == BB->end() ||
654 To == std::next(x: OrigDAGInterval.bottom()->getIterator())) {
655 // If we don't have a node to insert before, find a node to insert after and
656 // update the chain.
657 DGNode *InsertAfterN = getNode(I: &*std::prev(x: To));
658 MemN->setPrevNode(
659 getMemDGNodeBefore(N: InsertAfterN, /*IncludingN=*/true, /*SkipN=*/MemN));
660 } else {
661 // We have a node to insert before, so update the chain.
662 DGNode *BeforeToN = getNode(I: &*To);
663 MemN->setPrevNode(
664 getMemDGNodeBefore(N: BeforeToN, /*IncludingN=*/false, /*SkipN=*/MemN));
665 MemN->setNextNode(
666 getMemDGNodeAfter(N: BeforeToN, /*IncludingN=*/true, /*SkipN=*/MemN));
667 }
668#ifndef NDEBUG
669 // TODO: Remove some of the verifiers eventually to save compilation time.
670 verify();
671#endif
672}
673
674void DependencyGraph::notifyEraseInstr(Instruction *I) {
675 if (Ctx->getTracker().getState() == Tracker::TrackerState::Reverting)
676 // We don't maintain the DAG while reverting.
677 return;
678 auto *N = getNode(I);
679 if (N == nullptr)
680 // Early return if there is no DAG node for `I`.
681 return;
682
683#ifndef NDEBUG
684 // TODO: Remove some of the verifiers eventually to save compilation time.
685 verify();
686#endif
687
688 if (auto *MemN = dyn_cast<MemDGNode>(Val: getNode(I))) {
689 // Update the MemDGNode chain if this is a memory node.
690 auto *PrevMemN = getMemDGNodeBefore(N: MemN, /*IncludingN=*/false);
691 auto *NextMemN = getMemDGNodeAfter(N: MemN, /*IncludingN=*/false);
692 if (PrevMemN != nullptr)
693 PrevMemN->NextMemN = NextMemN;
694 if (NextMemN != nullptr)
695 NextMemN->PrevMemN = PrevMemN;
696
697 // Drop the memory dependencies from both predecessors and successors.
698 while (!MemN->memPreds().empty()) {
699 auto *PredN = *MemN->memPreds().begin();
700 MemN->removeMemPred(PredN, Dir);
701 }
702 while (!MemN->memSuccs().empty()) {
703 auto *SuccN = *MemN->memSuccs().begin();
704 SuccN->removeMemPred(PredN: MemN, Dir);
705 }
706 // NOTE: The unscheduled succs for MemNodes get updated be setMemPred().
707 }
708
709 if (!N->scheduled()) {
710 // Update UnscheduledDeps for def-use edges. The UnscheduledDeps has already
711 // been updated for the memory dependency edges.
712 if (Dir == SchedDirection::BottomUp) {
713 for (Value *Op : I->operands()) {
714 if (!isa<Instruction>(Val: Op))
715 continue;
716 DGNode *PredN = getNode(I: cast<Instruction>(Val: Op));
717 if (PredN && !PredN->scheduled())
718 PredN->decrUnscheduledDeps();
719 }
720 } else if (Dir == SchedDirection::TopDown) {
721 for (User *U : I->users()) {
722 if (!isa<Instruction>(Val: U))
723 continue;
724 DGNode *SuccN = getNode(I: cast<Instruction>(Val: U));
725 if (SuccN && !SuccN->scheduled())
726 SuccN->decrUnscheduledDeps();
727 }
728 }
729 }
730
731 if (Sched != nullptr)
732 Sched->notifyEraseInstr(I);
733
734 // Finally erase the Node.
735 InstrToNodeMap.erase(Val: I);
736}
737
738void DependencyGraph::notifySetUse(const Use &U, Value *NewSrc) {
739 // TODO: We should eventually move the UnschedDep logic to the scheduler.
740
741 // If U.User is not in the DAG, then we should not attempt to decrement
742 // CurrSrcN's unscheduled successors.
743 // ------- ------- -
744 // CurrSrc | DAG interval
745 // | NewSrc |
746 // ---|--- ---|--- -
747 // U.User U.User
748 auto *UserI = dyn_cast_or_null<Instruction>(Val: U.getUser());
749 if (UserI == nullptr)
750 return;
751 auto *UserN = getNode(I: UserI);
752 if (UserN == nullptr)
753 return;
754 // If UserN is marked as scheduled then we should not update CrrSrcN' or
755 // NewSrcN's unscheduled successors.
756 if (UserN->scheduled())
757 return;
758 // Update the UnscheduledSuccs counter for both the current source and
759 // NewSrc if needed.
760 if (auto *CurrSrcI = dyn_cast<Instruction>(Val: U.get())) {
761 if (auto *CurrSrcN = getNode(I: CurrSrcI)) {
762 // If CurrSrcN is scheduled there is no point in updating UnscheduledDeps.
763 if (!CurrSrcN->scheduled()) {
764 if (Dir == SchedDirection::BottomUp)
765 CurrSrcN->decrUnscheduledDeps();
766 else
767 UserN->decrUnscheduledDeps();
768 }
769 }
770 }
771 if (auto *NewSrcI = dyn_cast<Instruction>(Val: NewSrc)) {
772 if (auto *NewSrcN = getNode(I: NewSrcI)) {
773 // If CurrSrcN is scheduled there is no point in updating UnscheduleDeps.
774 if (!NewSrcN->scheduled()) {
775 if (Dir == SchedDirection::BottomUp)
776 NewSrcN->incrUnscheduledDeps();
777 else
778 UserN->incrUnscheduledDeps();
779 }
780 }
781 }
782}
783
784Interval<Instruction> DependencyGraph::extend(BndlRef<Instruction *> Instrs) {
785 if (Instrs.empty())
786 return {};
787
788 Interval<Instruction> InstrsInterval(Instrs);
789 Interval<Instruction> Union = DAGInterval.getUnionInterval(Other: InstrsInterval);
790 auto NewInterval = Union.getSingleDiff(Other: DAGInterval);
791 if (NewInterval.empty())
792 return {};
793
794 createNewNodes(NewInterval);
795
796 // Create the dependencies.
797 //
798 // 1. This is a new DAG, DAGInterval is empty. Fully scan the whole interval.
799 // +---+ - -
800 // | | SrcN | |
801 // | | | | SrcRange |
802 // |New| v | | DstRange
803 // | | DstN - |
804 // | | |
805 // +---+ -
806 // We are scanning for deps with destination in NewInterval and sources in
807 // NewInterval until DstN, for each DstN.
808 auto FullScan = [this](const Interval<Instruction> Intvl) {
809 auto DstRange = MemDGNodeIntervalBuilder::make(Instrs: Intvl, DAG&: *this);
810 if (!DstRange.empty()) {
811 for (MemDGNode &DstN : drop_begin(RangeOrContainer&: DstRange)) {
812 auto SrcRange = Interval<MemDGNode>(DstRange.top(), DstN.getPrevNode());
813 scanAndAddDeps(DstN, SrcScanRange: SrcRange);
814 }
815 }
816 };
817 auto MemDAGInterval = MemDGNodeIntervalBuilder::make(Instrs: DAGInterval, DAG&: *this);
818 if (MemDAGInterval.empty()) {
819 FullScan(NewInterval);
820 }
821 // 2. The new section is below the old section.
822 // +---+ -
823 // | | |
824 // |Old| SrcN |
825 // | | | |
826 // +---+ | | SrcRange
827 // +---+ | | -
828 // | | | | |
829 // |New| v | | DstRange
830 // | | DstN - |
831 // | | |
832 // +---+ -
833 // We are scanning for deps with destination in NewInterval because the deps
834 // in DAGInterval have already been computed. We consider sources in the whole
835 // range including both NewInterval and DAGInterval until DstN, for each DstN.
836 else if (DAGInterval.bottom()->comesBefore(Other: NewInterval.top())) {
837 auto DstRange = MemDGNodeIntervalBuilder::make(Instrs: NewInterval, DAG&: *this);
838 auto SrcRangeFull = MemDAGInterval.getUnionInterval(Other: DstRange);
839 for (MemDGNode &DstN : DstRange) {
840 auto SrcRange =
841 Interval<MemDGNode>(SrcRangeFull.top(), DstN.getPrevNode());
842 scanAndAddDeps(DstN, SrcScanRange: SrcRange);
843 }
844 }
845 // 3. The new section is above the old section.
846 else if (NewInterval.bottom()->comesBefore(Other: DAGInterval.top())) {
847 // +---+ - -
848 // | | SrcN | |
849 // |New| | | SrcRange | DstRange
850 // | | v | |
851 // | | DstN - |
852 // | | |
853 // +---+ -
854 // +---+
855 // |Old|
856 // | |
857 // +---+
858 // When scanning for deps with destination in NewInterval we need to fully
859 // scan the interval. This is the same as the scanning for a new DAG.
860 FullScan(NewInterval);
861
862 // +---+ -
863 // | | |
864 // |New| SrcN | SrcRange
865 // | | | |
866 // | | | |
867 // | | | |
868 // +---+ | -
869 // +---+ | -
870 // |Old| v | DstRange
871 // | | DstN |
872 // +---+ -
873 // When scanning for deps with destination in DAGInterval we need to
874 // consider sources from the NewInterval only, because all intra-DAGInterval
875 // dependencies have already been created.
876 auto DstRangeOld = MemDAGInterval;
877 auto SrcRange = MemDGNodeIntervalBuilder::make(Instrs: NewInterval, DAG&: *this);
878 for (MemDGNode &DstN : DstRangeOld)
879 scanAndAddDeps(DstN, SrcScanRange: SrcRange);
880 } else {
881 llvm_unreachable("We don't expect extending in both directions!");
882 }
883
884 DAGInterval = Union;
885 return NewInterval;
886}
887
888#ifndef NDEBUG
889void DependencyGraph::verify() {
890 auto Dependency = [this](DGNode *FromN, DGNode *ToN) {
891 for (DGNode *FromSuccN : FromN->succs(*this)) {
892 if (FromSuccN == ToN)
893 return true;
894 }
895 for (DGNode *ToPredN : ToN->preds(*this)) {
896 if (ToPredN == FromN)
897 return true;
898 }
899 return false;
900 };
901 for (const auto &[I1, NPtr1] : InstrToNodeMap) {
902 NPtr1->verify(*this);
903 for (const auto &[I2, NPtr2] : InstrToNodeMap) {
904 if (Dependency(NPtr1.get(), NPtr2.get())) {
905 assert(I1->comesBefore(I2) &&
906 "Instruction ordering violates dependency!");
907 }
908 }
909 }
910}
911void DependencyGraph::print(raw_ostream &OS) const {
912 // InstrToNodeMap is unordered so we need to create an ordered vector.
913 SmallVector<DGNode *> Nodes;
914 Nodes.reserve(InstrToNodeMap.size());
915 for (const auto &Pair : InstrToNodeMap)
916 Nodes.push_back(Pair.second.get());
917 // Sort them based on which one comes first in the BB.
918 sort(Nodes, [](DGNode *N1, DGNode *N2) {
919 return N1->getInstruction()->comesBefore(N2->getInstruction());
920 });
921 for (auto *N : Nodes)
922 N->print(OS, /*PrintDeps=*/true);
923}
924
925void DependencyGraph::dump() const {
926 print(dbgs());
927 dbgs() << "\n";
928}
929#endif // NDEBUG
930
931} // namespace llvm::sandboxir
932