LLVM 24.0.0git
DependencyGraph.h
Go to the documentation of this file.
1//===- DependencyGraph.h ----------------------------------------*- C++ -*-===//
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// This file declares the dependency graph used by the vectorizer's instruction
10// scheduler.
11//
12// The nodes of the graph are objects of the `DGNode` class. Each `DGNode`
13// object points to an instruction.
14// The edges between `DGNode`s are implicitly defined by an ordered set of
15// predecessor nodes, to save memory.
16// Finally the whole dependency graph is an object of the `DependencyGraph`
17// class, which also provides the API for creating/extending the graph from
18// input Sandbox IR.
19//
20//===----------------------------------------------------------------------===//
21
22#ifndef LLVM_TRANSFORMS_VECTORIZE_SANDBOXVECTORIZER_DEPENDENCYGRAPH_H
23#define LLVM_TRANSFORMS_VECTORIZE_SANDBOXVECTORIZER_DEPENDENCYGRAPH_H
24
25#include "llvm/ADT/DenseMap.h"
33
34namespace llvm::sandboxir {
35
36class DependencyGraph;
37class MemDGNode;
38class SchedBundle;
39
44#ifndef NDEBUG
45StringLiteral schedDirectionToStr(SchedDirection Dir);
46#endif
47
48/// SubclassIDs for isa/dyn_cast etc.
49enum class DGNodeID {
52};
53
54class DGNode;
55class MemDGNode;
56class DependencyGraph;
57
58// Defined in Transforms/Vectorize/SandboxVectorizer/Interval.cpp
59extern template class LLVM_TEMPLATE_ABI Interval<MemDGNode>;
60
61/// Iterate over both def-use and mem dependencies.
62class PredIterator {
66 DGNode *N = nullptr;
67 DependencyGraph *DAG = nullptr;
68
69 PredIterator(const User::op_iterator &OpIt, const User::op_iterator &OpItE,
71 DependencyGraph &DAG)
72 : OpIt(OpIt), OpItE(OpItE), MemIt(MemIt), N(N), DAG(&DAG) {}
73 PredIterator(const User::op_iterator &OpIt, const User::op_iterator &OpItE,
74 DGNode *N, DependencyGraph &DAG)
75 : OpIt(OpIt), OpItE(OpItE), N(N), DAG(&DAG) {}
76 friend class DGNode; // For constructor
77 friend class MemDGNode; // For constructor
78
79 /// Skip iterators that don't point instructions or are outside \p DAG,
80 /// starting from \p OpIt and ending before \p OpItE.n
81 LLVM_ABI static User::op_iterator skipBadIt(User::op_iterator OpIt,
83 const DependencyGraph &DAG);
84
85public:
86 using difference_type = std::ptrdiff_t;
87 using value_type = DGNode *;
90 using iterator_category = std::input_iterator_tag;
92 LLVM_ABI PredIterator &operator++();
93 PredIterator operator++(int) {
94 auto Copy = *this;
95 ++(*this);
96 return Copy;
97 }
98 LLVM_ABI bool operator==(const PredIterator &Other) const;
99 bool operator!=(const PredIterator &Other) const { return !(*this == Other); }
100};
101
102/// Iterate over both def-use and mem dependencies.
103class SuccIterator {
104 User::user_iterator UserIt;
105 User::user_iterator UserItE;
107 DGNode *N = nullptr;
108 DependencyGraph *DAG = nullptr;
109
110 SuccIterator(const Value::user_iterator &UserIt,
111 const Value::user_iterator &UserItE,
113 DependencyGraph &DAG)
114 : UserIt(UserIt), UserItE(UserItE), MemIt(MemIt), N(N), DAG(&DAG) {}
115 SuccIterator(const User::user_iterator &UserIt,
116 const User::user_iterator &UserItE, DGNode *N,
117 DependencyGraph &DAG)
118 : UserIt(UserIt), UserItE(UserItE), N(N), DAG(&DAG) {}
119 friend class DGNode; // For constructor
120 friend class MemDGNode; // For constructor
121
122 /// Skip iterators that don't point to instructions or are outside \p DAG,
123 /// starting from \p OpIt and ending before \p OpItE.
125 skipOutOfScope(User::user_iterator UserIt, User::user_iterator UserItE,
126 const DependencyGraph &DAG);
127
128public:
129 using difference_type = std::ptrdiff_t;
133 using iterator_category = std::input_iterator_tag;
135 LLVM_ABI SuccIterator &operator++();
136 SuccIterator operator++(int) {
137 auto Copy = *this;
138 ++(*this);
139 return Copy;
140 }
141 LLVM_ABI bool operator==(const SuccIterator &Other) const;
142 bool operator!=(const SuccIterator &Other) const { return !(*this == Other); }
143};
144
145/// A DependencyGraph Node that points to an Instruction and contains memory
146/// dependency edges.
148protected:
150 // TODO: Use a PointerIntPair for SubclassID and I.
151 /// For isa/dyn_cast etc.
153 /// The number of unscheduled successors in the bottom-up scheduling direction
154 /// (or predecessors in top-down). A value of 0 means that all its dependent
155 /// nodes have been scheduled so this node is ready to be scheduled. Optional
156 /// represents whether the value is meaningless, e.g., after a node gets
157 /// scheduled.
158 std::optional<unsigned> UnscheduledDeps = 0;
159 /// This is true if this node has been scheduled.
160 bool Scheduled = false;
161 /// The scheduler bundle that this node belongs to.
162 SchedBundle *SB = nullptr;
163
165 void clearSchedBundle() { this->SB = nullptr; }
166 friend class SchedBundle; // For setSchedBundle(), clearSchedBundle().
167
169 friend class MemDGNode; // For constructor.
170 friend class DependencyGraph; // For UnscheduledSuccs
171
172public:
174 assert(!isMemDepNodeCandidate(I) && "Expected Non-Mem instruction, ");
175 }
176 DGNode(const DGNode &Other) = delete;
177 virtual ~DGNode();
178 /// \Returns the number of unscheduled successors.
179 unsigned getNumUnscheduledDeps() const {
180 assert((bool)UnscheduledDeps && "Invalid UnscheduledDeps!");
181 return *UnscheduledDeps;
182 }
183#ifndef NDEBUG
184 /// \returns true if unscheduled successors(predecessors) contains valid data
185 /// (for testing).
186 bool validUnscheduledDeps() const { return (bool)UnscheduledDeps; }
187#endif
188 // TODO: Make this private?
190 assert(*UnscheduledDeps > 0 && "Counting error!");
192 }
194
196 UnscheduledDeps = 0;
197 Scheduled = false;
198 }
199 /// \Returns true if all dependent successors (or predecessors during top-down
200 /// scheduling) have been scheduled.
201 bool ready() const { return UnscheduledDeps == 0; }
202 /// \Returns true if this node has been scheduled.
203 bool scheduled() const { return Scheduled; }
205 assert(UnscheduledDeps == 0 && "Node not ready!");
206 Scheduled = true;
207 // UnscheduledDeps is meaningless from this point on, so prohibit its use.
208 UnscheduledDeps = std::nullopt;
209 }
210 /// \Returns the scheduling bundle that this node belongs to, or nullptr.
211 SchedBundle *getSchedBundle() const { return SB; }
212 /// \Returns true if this is before \p Other in program order.
213 bool comesBefore(const DGNode *Other) { return I->comesBefore(Other->I); }
216 return PredIterator(
217 PredIterator::skipBadIt(I->op_begin(), I->op_end(), DAG), I->op_end(),
218 this, DAG);
219 }
221 return PredIterator(I->op_end(), I->op_end(), this, DAG);
222 }
224 return const_cast<DGNode *>(this)->preds_begin(DAG);
225 }
227 return const_cast<DGNode *>(this)->preds_end(DAG);
228 }
229 /// \Returns a range of DAG predecessors nodes. If this is a MemDGNode then
230 /// this will also include the memory dependency predecessors.
231 /// Please note that this can include the same node more than once, if for
232 /// example it's both a use-def predecessor and a mem dep predecessor.
236
239 return SuccIterator(
240 SuccIterator::skipOutOfScope(I->user_begin(), I->user_end(), DAG),
241 I->user_end(), this, DAG);
242 }
244 return SuccIterator(I->user_end(), I->user_end(), this, DAG);
245 }
247 return const_cast<DGNode *>(this)->succs_begin(DAG);
248 }
250 return const_cast<DGNode *>(this)->succs_end(DAG);
251 }
252 /// \Returns a range of DAG successor nodes. If this is a MemDGNode then
253 /// this will also include the memory dependency successors.
254 /// Please note that this can include the same node more than once, if for
255 /// example it's both a use-def predecessor and a mem dep successor.
259
261 if (auto *II = dyn_cast<IntrinsicInst>(I)) {
262 auto IID = II->getIntrinsicID();
263 return IID == Intrinsic::stackrestore || IID == Intrinsic::stacksave;
264 }
265 return false;
266 }
267
268 /// \Returns true if intrinsic \p I touches memory. This is used by the
269 /// dependency graph.
271 auto IID = I->getIntrinsicID();
272 return IID != Intrinsic::sideeffect && IID != Intrinsic::pseudoprobe;
273 }
274
275 /// We consider \p I as a Memory Dependency Candidate instruction if it
276 /// reads/write memory or if it has side-effects. This is used by the
277 /// dependency graph.
280 return I->mayReadOrWriteMemory() &&
282 }
283
284 /// \Returns true if \p I is fence like. It excludes non-mem intrinsics.
285 static bool isFenceLike(Instruction *I) {
287 return I->isFenceLike() &&
289 }
290
291 /// \Returns true if \p I is a memory dependency candidate instruction.
293 AllocaInst *Alloca;
294 return isMemDepCandidate(I) ||
295 ((Alloca = dyn_cast<AllocaInst>(I)) &&
296 Alloca->isUsedWithInAlloca()) ||
298 }
299
300 Instruction *getInstruction() const { return I; }
301
302#ifndef NDEBUG
303 void verify(DependencyGraph &DAG) const;
304 virtual void print(raw_ostream &OS, bool PrintDeps = true) const;
306 N.print(OS);
307 return OS;
308 }
309 LLVM_DUMP_METHOD void dump() const;
310#endif // NDEBUG
311};
312
313/// A DependencyGraph Node for instructions that may read/write memory, or have
314/// some ordering constraints, like with stacksave/stackrestore and
315/// alloca/inalloca.
316class MemDGNode final : public DGNode {
317 MemDGNode *PrevMemN = nullptr;
318 MemDGNode *NextMemN = nullptr;
319 /// Memory predecessors.
320 DenseSet<MemDGNode *> MemPreds;
321 /// Memory successors.
322 DenseSet<MemDGNode *> MemSuccs;
323 friend class PredIterator; // For MemPreds.
324 friend class SuccIterator; // For MemSuccs.
325 /// Creates both edges: this<->N.
326 void setNextNode(MemDGNode *N) {
327 assert(N != this && "About to point to self!");
328 NextMemN = N;
329 if (NextMemN != nullptr)
330 NextMemN->PrevMemN = this;
331 }
332 /// Creates both edges: N<->this.
333 void setPrevNode(MemDGNode *N) {
334 assert(N != this && "About to point to self!");
335 PrevMemN = N;
336 if (PrevMemN != nullptr)
337 PrevMemN->NextMemN = this;
338 }
339 friend class DependencyGraph; // For setNextNode(), setPrevNode().
340 void detachFromChain() {
341 if (PrevMemN != nullptr)
342 PrevMemN->NextMemN = NextMemN;
343 if (NextMemN != nullptr)
344 NextMemN->PrevMemN = PrevMemN;
345 PrevMemN = nullptr;
346 NextMemN = nullptr;
347 }
348
349public:
351 assert(isMemDepNodeCandidate(I) && "Expected Mem instruction!");
352 }
353 static bool classof(const DGNode *Other) {
354 return Other->SubclassID == DGNodeID::MemDGNode;
355 }
357 auto OpEndIt = I->op_end();
358 return PredIterator(PredIterator::skipBadIt(I->op_begin(), OpEndIt, DAG),
359 OpEndIt, MemPreds.begin(), this, DAG);
360 }
362 return PredIterator(I->op_end(), I->op_end(), MemPreds.end(), this, DAG);
363 }
365 auto UserEndIt = I->user_end();
366 return SuccIterator(
367 SuccIterator::skipOutOfScope(I->user_begin(), UserEndIt, DAG),
368 UserEndIt, MemSuccs.begin(), this, DAG);
369 }
371 return SuccIterator(I->user_end(), I->user_end(), MemSuccs.end(), this,
372 DAG);
373 }
374 /// \Returns the previous Mem DGNode in instruction order.
375 MemDGNode *getPrevNode() const { return PrevMemN; }
376 /// \Returns the next Mem DGNode in instruction order.
377 MemDGNode *getNextNode() const { return NextMemN; }
378
379 // TODO: addMemPred() and removeMemPred() should be private.
380 /// Adds the mem dependency edge PredN->this. This also increments the
381 /// UnscheduledDeps counter of the predecessor if this node has not been
382 /// scheduled.
384 [[maybe_unused]] auto Inserted = MemPreds.insert(PredN).second;
385 assert(Inserted && "PredN already exists!");
386 assert(PredN != this && "Trying to add a dependency to self!");
387 PredN->MemSuccs.insert(this);
388 if (!Scheduled) {
389 if (!PredN->Scheduled) {
390 if (Dir == SchedDirection::BottomUp)
391 PredN->incrUnscheduledDeps();
392 else
394 }
395 }
396 }
397 /// Removes the memory dependency PredN->this. This also updates the
398 /// UnscheduledSuccs counter of PredN if this node has not been scheduled.
400 MemPreds.erase(PredN);
401 PredN->MemSuccs.erase(this);
402 if (!Scheduled) {
403 if (!PredN->Scheduled) {
404 if (Dir == SchedDirection::BottomUp)
405 PredN->decrUnscheduledDeps();
406 else
408 }
409 }
410 }
411
412 /// \Returns true if there is a memory dependency N->this.
413 bool hasMemPred(DGNode *N) const {
414 if (auto *MN = dyn_cast<MemDGNode>(N))
415 return MemPreds.count(MN);
416 return false;
417 }
418 /// \Returns all memory dependency predecessors. Used by tests.
420 return make_range(MemPreds.begin(), MemPreds.end());
421 }
422 /// \Returns all memory dependency successors.
424 return make_range(MemSuccs.begin(), MemSuccs.end());
425 }
426#ifndef NDEBUG
427 void print(raw_ostream &OS, bool PrintDeps = true) const override;
428#endif // NDEBUG
429};
430
431/// Convenience builders for a MemDGNode interval.
433public:
434 /// Scans the instruction chain in \p Intvl top-down, returning the top-most
435 /// MemDGNode, or nullptr.
437 const DependencyGraph &DAG);
438 /// Scans the instruction chain in \p Intvl bottom-up, returning the
439 /// bottom-most MemDGNode, or nullptr.
441 const DependencyGraph &DAG);
442 /// Given \p Instrs it finds their closest mem nodes in the interval and
443 /// returns the corresponding mem range. Note: BotN (or its neighboring mem
444 /// node) is included in the range.
446 DependencyGraph &DAG);
447 static Interval<MemDGNode> makeEmpty() { return {}; }
448};
449
450class Scheduler;
451
453private:
455 /// The DAG spans across all instructions in this interval.
456 Interval<Instruction> DAGInterval;
457
458 SchedDirection Dir;
459#ifndef NDEBUG
460 friend void DGNode::verify(DependencyGraph &DAG) const; // For Dir.
461#endif
462 Context *Ctx = nullptr;
463 Scheduler *Sched = nullptr;
464
465 std::optional<Context::CallbackID> CreateInstrCB;
466 std::optional<Context::CallbackID> EraseInstrCB;
467 std::optional<Context::CallbackID> MoveInstrCB;
468 std::optional<Context::CallbackID> SetUseCB;
469
470 std::unique_ptr<BatchAAResults> BatchAA;
471
472 enum class DependencyType {
473 ReadAfterWrite, ///> Memory dependency write -> read
474 WriteAfterWrite, ///> Memory dependency write -> write
475 WriteAfterRead, ///> Memory dependency read -> write
476 Control, ///> Control-related dependency, like with PHI/Terminator
477 Other, ///> Currently used for stack related instrs
478 None, ///> No memory/other dependency
479 };
480 /// \Returns the dependency type depending on whether instructions may
481 /// read/write memory or whether they are some specific opcode-related
482 /// restrictions.
483 /// Note: It does not check whether a memory dependency is actually correct,
484 /// as it won't call AA. Therefore it returns the worst-case dep type.
485 static DependencyType getRoughDepType(Instruction *FromI, Instruction *ToI);
486
487 // TODO: Implement AABudget.
488 /// \Returns true if there is a memory/other dependency \p SrcI->DstI.
489 bool alias(Instruction *SrcI, Instruction *DstI, DependencyType DepType);
490
491 bool hasDep(sandboxir::Instruction *SrcI, sandboxir::Instruction *DstI);
492
493 /// Go through all mem nodes in \p SrcScanRange and try to add dependencies to
494 /// \p DstN.
495 void scanAndAddDeps(MemDGNode &DstN, const Interval<MemDGNode> &SrcScanRange);
496
497 /// Sets the UnscheduledSuccs of all DGNodes in \p NewInterval based on
498 /// def-use edges.
499 void setDefUseUnscheduledSuccs(const Interval<Instruction> &NewInterval);
500
501 /// Create DAG nodes for instrs in \p NewInterval and update the MemNode
502 /// chain.
503 void createNewNodes(const Interval<Instruction> &NewInterval);
504
505 /// Helper for `notify*Instr()`. \Returns the first MemDGNode that comes
506 /// before \p N, skipping \p SkipN, including or excluding \p N based on
507 /// \p IncludingN, or nullptr if not found.
508 MemDGNode *getMemDGNodeBefore(DGNode *N, bool IncludingN,
509 MemDGNode *SkipN = nullptr) const;
510 /// Helper for `notifyMoveInstr()`. \Returns the first MemDGNode that comes
511 /// after \p N, skipping \p SkipN, including or excluding \p N based on \p
512 /// IncludingN, or nullptr if not found.
513 MemDGNode *getMemDGNodeAfter(DGNode *N, bool IncludingN,
514 MemDGNode *SkipN = nullptr) const;
515
516 /// Called by the callbacks when a new instruction \p I has been created.
517 LLVM_ABI void notifyCreateInstr(Instruction *I);
518 /// Called by the callbacks when instruction \p I is about to get
519 /// deleted.
520 LLVM_ABI void notifyEraseInstr(Instruction *I);
521 /// Called by the callbacks when instruction \p I is about to be moved to
522 /// \p To.
523 LLVM_ABI void notifyMoveInstr(Instruction *I, const BBIterator &To);
524 /// Called by the callbacks when \p U's source is about to be set to \p NewSrc
525 LLVM_ABI void notifySetUse(const Use &U, Value *NewSrc);
526
527public:
528 /// This constructor also registers callbacks.
530 Scheduler *Sched = nullptr)
531 : Dir(Dir), Ctx(&Ctx), Sched(Sched),
532 BatchAA(std::make_unique<BatchAAResults>(AA)) {
533 CreateInstrCB = Ctx.registerCreateInstrCallback(
534 [this](Instruction *I) { notifyCreateInstr(I); }, "DAG");
535 EraseInstrCB = Ctx.registerEraseInstrCallback(
536 [this](Instruction *I) { notifyEraseInstr(I); }, "DAG");
537 MoveInstrCB = Ctx.registerMoveInstrCallback(
538 [this](Instruction *I, const BBIterator &To) {
539 notifyMoveInstr(I, To);
540 },
541 "DAG");
542 SetUseCB = Ctx.registerSetUseCallback(
543 [this](const Use &U, Value *NewSrc) { notifySetUse(U, NewSrc); },
544 "DAG");
545 }
547 if (CreateInstrCB)
548 Ctx->unregisterCreateInstrCallback(*CreateInstrCB);
549 if (EraseInstrCB)
550 Ctx->unregisterEraseInstrCallback(*EraseInstrCB);
551 if (MoveInstrCB)
552 Ctx->unregisterMoveInstrCallback(*MoveInstrCB);
553 if (SetUseCB)
554 Ctx->unregisterSetUseCallback(*SetUseCB);
555 }
556
558 auto It = InstrToNodeMap.find(I);
559 return It != InstrToNodeMap.end() ? It->second.get() : nullptr;
560 }
561 /// Like getNode() but returns nullptr if \p I is nullptr.
563 if (I == nullptr)
564 return nullptr;
565 return getNode(I);
566 }
568 auto [It, NotInMap] = InstrToNodeMap.try_emplace(I);
569 if (NotInMap) {
571 It->second = std::make_unique<MemDGNode>(I);
572 else
573 It->second = std::make_unique<DGNode>(I);
574 }
575 return It->second.get();
576 }
577 /// Build/extend the dependency graph such that it includes \p Instrs. Returns
578 /// the range of instructions added to the DAG.
580 /// \Returns the range of instructions included in the DAG.
581 Interval<Instruction> getInterval() const { return DAGInterval; }
582 void clear() {
583 InstrToNodeMap.clear();
584 DAGInterval = {};
585 }
586 /// \Returns true if the DAG's state is clear. Used in assertions.
587 bool empty() const {
588 bool IsEmpty = InstrToNodeMap.empty();
589 assert(IsEmpty == DAGInterval.empty() &&
590 "Interval and InstrToNodeMap out of sync!");
591 return IsEmpty;
592 }
593#ifndef NDEBUG
594 void verify();
595 void print(raw_ostream &OS) const;
596 LLVM_DUMP_METHOD void dump() const;
597#endif // NDEBUG
598};
599} // namespace llvm::sandboxir
600
601#endif // LLVM_TRANSFORMS_VECTORIZE_SANDBOXVECTORIZER_DEPENDENCYGRAPH_H
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
#define LLVM_ABI
Definition Compiler.h:211
#define LLVM_TEMPLATE_ABI
Definition Compiler.h:212
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition Compiler.h:702
This file defines the DenseMap class.
#define I(x, y, z)
Definition MD5.cpp:57
PostRA Machine Instruction Scheduler
std::pair< uint64_t, uint64_t > Interval
uint64_t IntrinsicInst * II
This class is a wrapper over an AAResults, and it is intended to be used only when there are no IR ch...
Represent a node in the directed graph.
Implements a dense probed hash-table based set.
Definition DenseSet.h:283
A wrapper around a string literal that serves as a proxy for constructing global tables of StringRefs...
Definition StringRef.h:888
A range adaptor for a pair of iterators.
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition raw_ostream.h:53
bool isUsedWithInAlloca() const
Return true if this alloca is used as an inalloca argument to a call.
An ArrayRef of Values or Instructions that we can print/dump for debugging.
Definition VecUtils.h:39
A DependencyGraph Node that points to an Instruction and contains memory dependency edges.
static bool isMemDepCandidate(Instruction *I)
We consider I as a Memory Dependency Candidate instruction if it reads/write memory or if it has side...
virtual iterator preds_end(DependencyGraph &DAG)
static bool isMemIntrinsic(IntrinsicInst *I)
\Returns true if intrinsic I touches memory.
bool validUnscheduledDeps() const
iterator preds_begin(DependencyGraph &DAG) const
std::optional< unsigned > UnscheduledDeps
The number of unscheduled successors in the bottom-up scheduling direction (or predecessors in top-do...
DGNode(Instruction *I, DGNodeID ID)
unsigned getNumUnscheduledDeps() const
\Returns the number of unscheduled successors.
void setSchedBundle(SchedBundle &SB)
bool scheduled() const
\Returns true if this node has been scheduled.
virtual succ_iterator succs_end(DependencyGraph &DAG)
void verify(DependencyGraph &DAG) const
bool ready() const
\Returns true if all dependent successors (or predecessors during top-down scheduling) have been sche...
succ_iterator succs_end(DependencyGraph &DAG) const
iterator_range< iterator > preds(DependencyGraph &DAG) const
\Returns a range of DAG predecessors nodes.
iterator preds_end(DependencyGraph &DAG) const
SchedBundle * SB
The scheduler bundle that this node belongs to.
bool Scheduled
This is true if this node has been scheduled.
static bool isMemDepNodeCandidate(Instruction *I)
\Returns true if I is a memory dependency candidate instruction.
SchedBundle * getSchedBundle() const
\Returns the scheduling bundle that this node belongs to, or nullptr.
iterator_range< succ_iterator > succs(DependencyGraph &DAG) const
\Returns a range of DAG successor nodes.
DGNodeID SubclassID
For isa/dyn_cast etc.
DGNode(const DGNode &Other)=delete
static bool isFenceLike(Instruction *I)
\Returns true if I is fence like. It excludes non-mem intrinsics.
Instruction * getInstruction() const
static bool isStackSaveOrRestoreIntrinsic(Instruction *I)
bool comesBefore(const DGNode *Other)
\Returns true if this is before Other in program order.
virtual succ_iterator succs_begin(DependencyGraph &DAG)
friend raw_ostream & operator<<(raw_ostream &OS, DGNode &N)
virtual iterator preds_begin(DependencyGraph &DAG)
succ_iterator succs_begin(DependencyGraph &DAG) const
Interval< Instruction > getInterval() const
\Returns the range of instructions included in the DAG.
bool empty() const
\Returns true if the DAG's state is clear. Used in assertions.
LLVM_DUMP_METHOD void dump() const
DGNode * getNode(Instruction *I) const
LLVM_ABI Interval< Instruction > extend(BndlRef< Instruction * > Instrs)
Build/extend the dependency graph such that it includes Instrs.
DGNode * getNodeOrNull(Instruction *I) const
Like getNode() but returns nullptr if I is nullptr.
void print(raw_ostream &OS) const
DGNode * getOrCreateNode(Instruction *I)
DependencyGraph(SchedDirection Dir, AAResults &AA, Context &Ctx, Scheduler *Sched=nullptr)
This constructor also registers callbacks.
A sandboxir::User with operands, opcode and linked with previous/next instructions in an instruction ...
Definition Instruction.h:43
Convenience builders for a MemDGNode interval.
static LLVM_ABI MemDGNode * getBotMemDGNode(const Interval< Instruction > &Intvl, const DependencyGraph &DAG)
Scans the instruction chain in Intvl bottom-up, returning the bottom-most MemDGNode,...
static Interval< MemDGNode > makeEmpty()
static LLVM_ABI MemDGNode * getTopMemDGNode(const Interval< Instruction > &Intvl, const DependencyGraph &DAG)
Scans the instruction chain in Intvl top-down, returning the top-most MemDGNode, or nullptr.
static LLVM_ABI Interval< MemDGNode > make(const Interval< Instruction > &Instrs, DependencyGraph &DAG)
Given Instrs it finds their closest mem nodes in the interval and returns the corresponding mem range...
A DependencyGraph Node for instructions that may read/write memory, or have some ordering constraints...
iterator preds_end(DependencyGraph &DAG) override
iterator preds_begin(DependencyGraph &DAG) override
bool hasMemPred(DGNode *N) const
\Returns true if there is a memory dependency N->this.
static bool classof(const DGNode *Other)
void addMemPred(MemDGNode *PredN, SchedDirection Dir)
Adds the mem dependency edge PredN->this.
void removeMemPred(MemDGNode *PredN, SchedDirection Dir)
Removes the memory dependency PredN->this.
iterator_range< DenseSet< MemDGNode * >::const_iterator > memPreds() const
\Returns all memory dependency predecessors. Used by tests.
MemDGNode * getNextNode() const
\Returns the next Mem DGNode in instruction order.
iterator_range< DenseSet< MemDGNode * >::const_iterator > memSuccs() const
\Returns all memory dependency successors.
succ_iterator succs_begin(DependencyGraph &DAG) override
MemDGNode * getPrevNode() const
\Returns the previous Mem DGNode in instruction order.
succ_iterator succs_end(DependencyGraph &DAG) override
Iterate over both def-use and mem dependencies.
bool operator!=(const PredIterator &Other) const
LLVM_ABI PredIterator & operator++()
std::input_iterator_tag iterator_category
The nodes that need to be scheduled back-to-back in a single scheduling cycle form a SchedBundle.
Definition Scheduler.h:128
The list scheduler.
Definition Scheduler.h:302
Iterate over both def-use and mem dependencies.
LLVM_ABI SuccIterator & operator++()
bool operator!=(const SuccIterator &Other) const
std::input_iterator_tag iterator_category
Represents a Def-use/Use-def edge in SandboxIR.
Definition Use.h:43
OperandUseIterator op_iterator
Definition User.h:98
A SandboxIR Value has users. This is the base class.
Definition Value.h:72
mapped_iterator< sandboxir::UserUseIterator, UseToUser > user_iterator
Definition Value.h:238
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
Abstract Attribute helper functions.
Definition Attributor.h:166
StringLiteral schedDirectionToStr(SchedDirection Dir)
void verify() const final
DGNodeID
SubclassIDs for isa/dyn_cast etc.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr, unsigned DynamicVGPRBlockSize=0)
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:643
APInt operator*(APInt a, uint64_t RHS)
Definition APInt.h:2261
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
@ Other
Any other memory.
Definition ModRef.h:68
Implement std::hash so that hash_code can be used in STL containers.
Definition BitVector.h:879
#define N