Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2026-05-10 08:44:45 

0001 //===- DependencyGraph.h ----------------------------------------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 // This file declares the dependency graph used by the vectorizer's instruction
0010 // scheduler.
0011 //
0012 // The nodes of the graph are objects of the `DGNode` class. Each `DGNode`
0013 // object points to an instruction.
0014 // The edges between `DGNode`s are implicitly defined by an ordered set of
0015 // predecessor nodes, to save memory.
0016 // Finally the whole dependency graph is an object of the `DependencyGraph`
0017 // class, which also provides the API for creating/extending the graph from
0018 // input Sandbox IR.
0019 //
0020 //===----------------------------------------------------------------------===//
0021 
0022 #ifndef LLVM_TRANSFORMS_VECTORIZE_SANDBOXVECTORIZER_DEPENDENCYGRAPH_H
0023 #define LLVM_TRANSFORMS_VECTORIZE_SANDBOXVECTORIZER_DEPENDENCYGRAPH_H
0024 
0025 #include "llvm/ADT/DenseMap.h"
0026 #include "llvm/ADT/iterator_range.h"
0027 #include "llvm/Analysis/AliasAnalysis.h"
0028 #include "llvm/SandboxIR/Instruction.h"
0029 #include "llvm/SandboxIR/IntrinsicInst.h"
0030 #include "llvm/Transforms/Vectorize/SandboxVectorizer/Interval.h"
0031 
0032 namespace llvm::sandboxir {
0033 
0034 class DependencyGraph;
0035 class MemDGNode;
0036 class SchedBundle;
0037 
0038 /// SubclassIDs for isa/dyn_cast etc.
0039 enum class DGNodeID {
0040   DGNode,
0041   MemDGNode,
0042 };
0043 
0044 class DGNode;
0045 class MemDGNode;
0046 class DependencyGraph;
0047 
0048 /// While OpIt points to a Value that is not an Instruction keep incrementing
0049 /// it. \Returns the first iterator that points to an Instruction, or end.
0050 [[nodiscard]] static User::op_iterator skipNonInstr(User::op_iterator OpIt,
0051                                                     User::op_iterator OpItE) {
0052   while (OpIt != OpItE && !isa<Instruction>((*OpIt).get()))
0053     ++OpIt;
0054   return OpIt;
0055 }
0056 
0057 /// Iterate over both def-use and mem dependencies.
0058 class PredIterator {
0059   User::op_iterator OpIt;
0060   User::op_iterator OpItE;
0061   DenseSet<MemDGNode *>::iterator MemIt;
0062   DGNode *N = nullptr;
0063   DependencyGraph *DAG = nullptr;
0064 
0065   PredIterator(const User::op_iterator &OpIt, const User::op_iterator &OpItE,
0066                const DenseSet<MemDGNode *>::iterator &MemIt, DGNode *N,
0067                DependencyGraph &DAG)
0068       : OpIt(OpIt), OpItE(OpItE), MemIt(MemIt), N(N), DAG(&DAG) {}
0069   PredIterator(const User::op_iterator &OpIt, const User::op_iterator &OpItE,
0070                DGNode *N, DependencyGraph &DAG)
0071       : OpIt(OpIt), OpItE(OpItE), N(N), DAG(&DAG) {}
0072   friend class DGNode;    // For constructor
0073   friend class MemDGNode; // For constructor
0074 
0075 public:
0076   using difference_type = std::ptrdiff_t;
0077   using value_type = DGNode *;
0078   using pointer = value_type *;
0079   using reference = value_type &;
0080   using iterator_category = std::input_iterator_tag;
0081   value_type operator*();
0082   PredIterator &operator++();
0083   PredIterator operator++(int) {
0084     auto Copy = *this;
0085     ++(*this);
0086     return Copy;
0087   }
0088   bool operator==(const PredIterator &Other) const;
0089   bool operator!=(const PredIterator &Other) const { return !(*this == Other); }
0090 };
0091 
0092 /// A DependencyGraph Node that points to an Instruction and contains memory
0093 /// dependency edges.
0094 class DGNode {
0095 protected:
0096   Instruction *I;
0097   // TODO: Use a PointerIntPair for SubclassID and I.
0098   /// For isa/dyn_cast etc.
0099   DGNodeID SubclassID;
0100   /// The number of unscheduled successors.
0101   unsigned UnscheduledSuccs = 0;
0102   /// This is true if this node has been scheduled.
0103   bool Scheduled = false;
0104   /// The scheduler bundle that this node belongs to.
0105   SchedBundle *SB = nullptr;
0106 
0107   void setSchedBundle(SchedBundle &SB) { this->SB = &SB; }
0108   void clearSchedBundle() { this->SB = nullptr; }
0109   friend class SchedBundle; // For setSchedBundle(), clearSchedBundle().
0110 
0111   DGNode(Instruction *I, DGNodeID ID) : I(I), SubclassID(ID) {}
0112   friend class MemDGNode;       // For constructor.
0113   friend class DependencyGraph; // For UnscheduledSuccs
0114 
0115 public:
0116   DGNode(Instruction *I) : I(I), SubclassID(DGNodeID::DGNode) {
0117     assert(!isMemDepNodeCandidate(I) && "Expected Non-Mem instruction, ");
0118   }
0119   DGNode(const DGNode &Other) = delete;
0120   virtual ~DGNode();
0121   /// \Returns the number of unscheduled successors.
0122   unsigned getNumUnscheduledSuccs() const { return UnscheduledSuccs; }
0123   void decrUnscheduledSuccs() {
0124     assert(UnscheduledSuccs > 0 && "Counting error!");
0125     --UnscheduledSuccs;
0126   }
0127   /// \Returns true if all dependent successors have been scheduled.
0128   bool ready() const { return UnscheduledSuccs == 0; }
0129   /// \Returns true if this node has been scheduled.
0130   bool scheduled() const { return Scheduled; }
0131   void setScheduled(bool NewVal) { Scheduled = NewVal; }
0132   /// \Returns the scheduling bundle that this node belongs to, or nullptr.
0133   SchedBundle *getSchedBundle() const { return SB; }
0134   /// \Returns true if this is before \p Other in program order.
0135   bool comesBefore(const DGNode *Other) { return I->comesBefore(Other->I); }
0136   using iterator = PredIterator;
0137   virtual iterator preds_begin(DependencyGraph &DAG) {
0138     return PredIterator(skipNonInstr(I->op_begin(), I->op_end()), I->op_end(),
0139                         this, DAG);
0140   }
0141   virtual iterator preds_end(DependencyGraph &DAG) {
0142     return PredIterator(I->op_end(), I->op_end(), this, DAG);
0143   }
0144   iterator preds_begin(DependencyGraph &DAG) const {
0145     return const_cast<DGNode *>(this)->preds_begin(DAG);
0146   }
0147   iterator preds_end(DependencyGraph &DAG) const {
0148     return const_cast<DGNode *>(this)->preds_end(DAG);
0149   }
0150   /// \Returns a range of DAG predecessors nodes. If this is a MemDGNode then
0151   /// this will also include the memory dependency predecessors.
0152   /// Please note that this can include the same node more than once, if for
0153   /// example it's both a use-def predecessor and a mem dep predecessor.
0154   iterator_range<iterator> preds(DependencyGraph &DAG) const {
0155     return make_range(preds_begin(DAG), preds_end(DAG));
0156   }
0157 
0158   static bool isStackSaveOrRestoreIntrinsic(Instruction *I) {
0159     if (auto *II = dyn_cast<IntrinsicInst>(I)) {
0160       auto IID = II->getIntrinsicID();
0161       return IID == Intrinsic::stackrestore || IID == Intrinsic::stacksave;
0162     }
0163     return false;
0164   }
0165 
0166   /// \Returns true if intrinsic \p I touches memory. This is used by the
0167   /// dependency graph.
0168   static bool isMemIntrinsic(IntrinsicInst *I) {
0169     auto IID = I->getIntrinsicID();
0170     return IID != Intrinsic::sideeffect && IID != Intrinsic::pseudoprobe;
0171   }
0172 
0173   /// We consider \p I as a Memory Dependency Candidate instruction if it
0174   /// reads/write memory or if it has side-effects. This is used by the
0175   /// dependency graph.
0176   static bool isMemDepCandidate(Instruction *I) {
0177     IntrinsicInst *II;
0178     return I->mayReadOrWriteMemory() &&
0179            (!(II = dyn_cast<IntrinsicInst>(I)) || isMemIntrinsic(II));
0180   }
0181 
0182   /// \Returns true if \p I is fence like. It excludes non-mem intrinsics.
0183   static bool isFenceLike(Instruction *I) {
0184     IntrinsicInst *II;
0185     return I->isFenceLike() &&
0186            (!(II = dyn_cast<IntrinsicInst>(I)) || isMemIntrinsic(II));
0187   }
0188 
0189   /// \Returns true if \p I is a memory dependency candidate instruction.
0190   static bool isMemDepNodeCandidate(Instruction *I) {
0191     AllocaInst *Alloca;
0192     return isMemDepCandidate(I) ||
0193            ((Alloca = dyn_cast<AllocaInst>(I)) &&
0194             Alloca->isUsedWithInAlloca()) ||
0195            isStackSaveOrRestoreIntrinsic(I) || isFenceLike(I);
0196   }
0197 
0198   Instruction *getInstruction() const { return I; }
0199 
0200 #ifndef NDEBUG
0201   virtual void print(raw_ostream &OS, bool PrintDeps = true) const;
0202   friend raw_ostream &operator<<(raw_ostream &OS, DGNode &N) {
0203     N.print(OS);
0204     return OS;
0205   }
0206   LLVM_DUMP_METHOD void dump() const;
0207 #endif // NDEBUG
0208 };
0209 
0210 /// A DependencyGraph Node for instructions that may read/write memory, or have
0211 /// some ordering constraints, like with stacksave/stackrestore and
0212 /// alloca/inalloca.
0213 class MemDGNode final : public DGNode {
0214   MemDGNode *PrevMemN = nullptr;
0215   MemDGNode *NextMemN = nullptr;
0216   /// Memory predecessors.
0217   DenseSet<MemDGNode *> MemPreds;
0218   friend class PredIterator; // For MemPreds.
0219   /// Creates both edges: this<->N.
0220   void setNextNode(MemDGNode *N) {
0221     assert(N != this && "About to point to self!");
0222     NextMemN = N;
0223     if (NextMemN != nullptr)
0224       NextMemN->PrevMemN = this;
0225   }
0226   /// Creates both edges: N<->this.
0227   void setPrevNode(MemDGNode *N) {
0228     assert(N != this && "About to point to self!");
0229     PrevMemN = N;
0230     if (PrevMemN != nullptr)
0231       PrevMemN->NextMemN = this;
0232   }
0233   friend class DependencyGraph; // For setNextNode(), setPrevNode().
0234   void detachFromChain() {
0235     if (PrevMemN != nullptr)
0236       PrevMemN->NextMemN = NextMemN;
0237     if (NextMemN != nullptr)
0238       NextMemN->PrevMemN = PrevMemN;
0239     PrevMemN = nullptr;
0240     NextMemN = nullptr;
0241   }
0242 
0243 public:
0244   MemDGNode(Instruction *I) : DGNode(I, DGNodeID::MemDGNode) {
0245     assert(isMemDepNodeCandidate(I) && "Expected Mem instruction!");
0246   }
0247   static bool classof(const DGNode *Other) {
0248     return Other->SubclassID == DGNodeID::MemDGNode;
0249   }
0250   iterator preds_begin(DependencyGraph &DAG) override {
0251     auto OpEndIt = I->op_end();
0252     return PredIterator(skipNonInstr(I->op_begin(), OpEndIt), OpEndIt,
0253                         MemPreds.begin(), this, DAG);
0254   }
0255   iterator preds_end(DependencyGraph &DAG) override {
0256     return PredIterator(I->op_end(), I->op_end(), MemPreds.end(), this, DAG);
0257   }
0258   /// \Returns the previous Mem DGNode in instruction order.
0259   MemDGNode *getPrevNode() const { return PrevMemN; }
0260   /// \Returns the next Mem DGNode in instruction order.
0261   MemDGNode *getNextNode() const { return NextMemN; }
0262   /// Adds the mem dependency edge PredN->this. This also increments the
0263   /// UnscheduledSuccs counter of the predecessor if this node has not been
0264   /// scheduled.
0265   void addMemPred(MemDGNode *PredN) {
0266     [[maybe_unused]] auto Inserted = MemPreds.insert(PredN).second;
0267     assert(Inserted && "PredN already exists!");
0268     if (!Scheduled) {
0269       ++PredN->UnscheduledSuccs;
0270     }
0271   }
0272   /// \Returns true if there is a memory dependency N->this.
0273   bool hasMemPred(DGNode *N) const {
0274     if (auto *MN = dyn_cast<MemDGNode>(N))
0275       return MemPreds.count(MN);
0276     return false;
0277   }
0278   /// \Returns all memory dependency predecessors. Used by tests.
0279   iterator_range<DenseSet<MemDGNode *>::const_iterator> memPreds() const {
0280     return make_range(MemPreds.begin(), MemPreds.end());
0281   }
0282 #ifndef NDEBUG
0283   virtual void print(raw_ostream &OS, bool PrintDeps = true) const override;
0284 #endif // NDEBUG
0285 };
0286 
0287 /// Convenience builders for a MemDGNode interval.
0288 class MemDGNodeIntervalBuilder {
0289 public:
0290   /// Scans the instruction chain in \p Intvl top-down, returning the top-most
0291   /// MemDGNode, or nullptr.
0292   static MemDGNode *getTopMemDGNode(const Interval<Instruction> &Intvl,
0293                                     const DependencyGraph &DAG);
0294   /// Scans the instruction chain in \p Intvl bottom-up, returning the
0295   /// bottom-most MemDGNode, or nullptr.
0296   static MemDGNode *getBotMemDGNode(const Interval<Instruction> &Intvl,
0297                                     const DependencyGraph &DAG);
0298   /// Given \p Instrs it finds their closest mem nodes in the interval and
0299   /// returns the corresponding mem range. Note: BotN (or its neighboring mem
0300   /// node) is included in the range.
0301   static Interval<MemDGNode> make(const Interval<Instruction> &Instrs,
0302                                   DependencyGraph &DAG);
0303   static Interval<MemDGNode> makeEmpty() { return {}; }
0304 };
0305 
0306 class DependencyGraph {
0307 private:
0308   DenseMap<Instruction *, std::unique_ptr<DGNode>> InstrToNodeMap;
0309   /// The DAG spans across all instructions in this interval.
0310   Interval<Instruction> DAGInterval;
0311 
0312   Context *Ctx = nullptr;
0313   std::optional<Context::CallbackID> CreateInstrCB;
0314   std::optional<Context::CallbackID> EraseInstrCB;
0315   std::optional<Context::CallbackID> MoveInstrCB;
0316 
0317   std::unique_ptr<BatchAAResults> BatchAA;
0318 
0319   enum class DependencyType {
0320     ReadAfterWrite,  ///> Memory dependency write -> read
0321     WriteAfterWrite, ///> Memory dependency write -> write
0322     WriteAfterRead,  ///> Memory dependency read -> write
0323     Control,         ///> Control-related dependency, like with PHI/Terminator
0324     Other,           ///> Currently used for stack related instrs
0325     None,            ///> No memory/other dependency
0326   };
0327   /// \Returns the dependency type depending on whether instructions may
0328   /// read/write memory or whether they are some specific opcode-related
0329   /// restrictions.
0330   /// Note: It does not check whether a memory dependency is actually correct,
0331   /// as it won't call AA. Therefore it returns the worst-case dep type.
0332   static DependencyType getRoughDepType(Instruction *FromI, Instruction *ToI);
0333 
0334   // TODO: Implement AABudget.
0335   /// \Returns true if there is a memory/other dependency \p SrcI->DstI.
0336   bool alias(Instruction *SrcI, Instruction *DstI, DependencyType DepType);
0337 
0338   bool hasDep(sandboxir::Instruction *SrcI, sandboxir::Instruction *DstI);
0339 
0340   /// Go through all mem nodes in \p SrcScanRange and try to add dependencies to
0341   /// \p DstN.
0342   void scanAndAddDeps(MemDGNode &DstN, const Interval<MemDGNode> &SrcScanRange);
0343 
0344   /// Sets the UnscheduledSuccs of all DGNodes in \p NewInterval based on
0345   /// def-use edges.
0346   void setDefUseUnscheduledSuccs(const Interval<Instruction> &NewInterval);
0347 
0348   /// Create DAG nodes for instrs in \p NewInterval and update the MemNode
0349   /// chain.
0350   void createNewNodes(const Interval<Instruction> &NewInterval);
0351 
0352   /// Helper for `notify*Instr()`. \Returns the first MemDGNode that comes
0353   /// before \p N, skipping \p SkipN, including or excluding \p N based on
0354   /// \p IncludingN, or nullptr if not found.
0355   MemDGNode *getMemDGNodeBefore(DGNode *N, bool IncludingN,
0356                                 MemDGNode *SkipN = nullptr) const;
0357   /// Helper for `notifyMoveInstr()`. \Returns the first MemDGNode that comes
0358   /// after \p N, skipping \p SkipN, including or excluding \p N based on \p
0359   /// IncludingN, or nullptr if not found.
0360   MemDGNode *getMemDGNodeAfter(DGNode *N, bool IncludingN,
0361                                MemDGNode *SkipN = nullptr) const;
0362 
0363   /// Called by the callbacks when a new instruction \p I has been created.
0364   void notifyCreateInstr(Instruction *I);
0365   /// Called by the callbacks when instruction \p I is about to get
0366   /// deleted.
0367   void notifyEraseInstr(Instruction *I);
0368   /// Called by the callbacks when instruction \p I is about to be moved to
0369   /// \p To.
0370   void notifyMoveInstr(Instruction *I, const BBIterator &To);
0371 
0372 public:
0373   /// This constructor also registers callbacks.
0374   DependencyGraph(AAResults &AA, Context &Ctx)
0375       : Ctx(&Ctx), BatchAA(std::make_unique<BatchAAResults>(AA)) {
0376     CreateInstrCB = Ctx.registerCreateInstrCallback(
0377         [this](Instruction *I) { notifyCreateInstr(I); });
0378     EraseInstrCB = Ctx.registerEraseInstrCallback(
0379         [this](Instruction *I) { notifyEraseInstr(I); });
0380     MoveInstrCB = Ctx.registerMoveInstrCallback(
0381         [this](Instruction *I, const BBIterator &To) {
0382           notifyMoveInstr(I, To);
0383         });
0384   }
0385   ~DependencyGraph() {
0386     if (CreateInstrCB)
0387       Ctx->unregisterCreateInstrCallback(*CreateInstrCB);
0388     if (EraseInstrCB)
0389       Ctx->unregisterEraseInstrCallback(*EraseInstrCB);
0390     if (MoveInstrCB)
0391       Ctx->unregisterMoveInstrCallback(*MoveInstrCB);
0392   }
0393 
0394   DGNode *getNode(Instruction *I) const {
0395     auto It = InstrToNodeMap.find(I);
0396     return It != InstrToNodeMap.end() ? It->second.get() : nullptr;
0397   }
0398   /// Like getNode() but returns nullptr if \p I is nullptr.
0399   DGNode *getNodeOrNull(Instruction *I) const {
0400     if (I == nullptr)
0401       return nullptr;
0402     return getNode(I);
0403   }
0404   DGNode *getOrCreateNode(Instruction *I) {
0405     auto [It, NotInMap] = InstrToNodeMap.try_emplace(I);
0406     if (NotInMap) {
0407       if (DGNode::isMemDepNodeCandidate(I))
0408         It->second = std::make_unique<MemDGNode>(I);
0409       else
0410         It->second = std::make_unique<DGNode>(I);
0411     }
0412     return It->second.get();
0413   }
0414   /// Build/extend the dependency graph such that it includes \p Instrs. Returns
0415   /// the range of instructions added to the DAG.
0416   Interval<Instruction> extend(ArrayRef<Instruction *> Instrs);
0417   /// \Returns the range of instructions included in the DAG.
0418   Interval<Instruction> getInterval() const { return DAGInterval; }
0419   void clear() {
0420     InstrToNodeMap.clear();
0421     DAGInterval = {};
0422   }
0423 #ifndef NDEBUG
0424   /// \Returns true if the DAG's state is clear. Used in assertions.
0425   bool empty() const {
0426     bool IsEmpty = InstrToNodeMap.empty();
0427     assert(IsEmpty == DAGInterval.empty() &&
0428            "Interval and InstrToNodeMap out of sync!");
0429     return IsEmpty;
0430   }
0431   void print(raw_ostream &OS) const;
0432   LLVM_DUMP_METHOD void dump() const;
0433 #endif // NDEBUG
0434 };
0435 
0436 } // namespace llvm::sandboxir
0437 
0438 #endif // LLVM_TRANSFORMS_VECTORIZE_SANDBOXVECTORIZER_DEPENDENCYGRAPH_H
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!