llvm/CodeGen/LatencyPriorityQueue.h

0001 //===---- LatencyPriorityQueue.h - A latency-oriented priority queue ------===//
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 LatencyPriorityQueue class, which is a
0010 // SchedulingPriorityQueue that schedules using latency information to
0011 // reduce the length of the critical path through the basic block.
0012 //
0013 //===----------------------------------------------------------------------===//
0014
0015 #ifndef LLVM_CODEGEN_LATENCYPRIORITYQUEUE_H
0016 #define LLVM_CODEGEN_LATENCYPRIORITYQUEUE_H
0017
0018 #include "llvm/CodeGen/ScheduleDAG.h"
0019 #include "llvm/Config/llvm-config.h"
0020
0021 namespace llvm {
0022   class LatencyPriorityQueue;
0023
0024   /// Sorting functions for the Available queue.
0025   struct latency_sort {
0026     LatencyPriorityQueue *PQ;
0027     explicit latency_sort(LatencyPriorityQueue *pq) : PQ(pq) {}
0028
0029     bool operator()(const SUnit* LHS, const SUnit* RHS) const;
0030   };
0031
0032   class LatencyPriorityQueue : public SchedulingPriorityQueue {
0033     // SUnits - The SUnits for the current graph.
0034     std::vector<SUnit> *SUnits = nullptr;
0035
0036     /// NumNodesSolelyBlocking - This vector contains, for every node in the
0037     /// Queue, the number of nodes that the node is the sole unscheduled
0038     /// predecessor for.  This is used as a tie-breaker heuristic for better
0039     /// mobility.
0040     std::vector<unsigned> NumNodesSolelyBlocking;
0041
0042     /// Queue - The queue.
0043     std::vector<SUnit*> Queue;
0044     latency_sort Picker;
0045
0046   public:
0047     LatencyPriorityQueue() : Picker(this) {
0048     }
0049
0050     bool isBottomUp() const override { return false; }
0051
0052     void initNodes(std::vector<SUnit> &sunits) override {
0053       SUnits = &sunits;
0054       NumNodesSolelyBlocking.resize(SUnits->size(), 0);
0055     }
0056
0057     void addNode(const SUnit *SU) override {
0058       NumNodesSolelyBlocking.resize(SUnits->size(), 0);
0059     }
0060
0061     void updateNode(const SUnit *SU) override {
0062     }
0063
0064     void releaseState() override {
0065       SUnits = nullptr;
0066     }
0067
0068     unsigned getLatency(unsigned NodeNum) const {
0069       assert(NodeNum < (*SUnits).size());
0070       return (*SUnits)[NodeNum].getHeight();
0071     }
0072
0073     unsigned getNumSolelyBlockNodes(unsigned NodeNum) const {
0074       assert(NodeNum < NumNodesSolelyBlocking.size());
0075       return NumNodesSolelyBlocking[NodeNum];
0076     }
0077
0078     bool empty() const override { return Queue.empty(); }
0079
0080     void push(SUnit *U) override;
0081
0082     SUnit *pop() override;
0083
0084     void remove(SUnit *SU) override;
0085
0086 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
0087     LLVM_DUMP_METHOD void dump(ScheduleDAG *DAG) const override;
0088 #endif
0089
0090     // scheduledNode - As nodes are scheduled, we look to see if there are any
0091     // successor nodes that have a single unscheduled predecessor.  If so, that
0092     // single predecessor has a higher priority, since scheduling it will make
0093     // the node available.
0094     void scheduledNode(SUnit *SU) override;
0095
0096 private:
0097     void AdjustPriorityOfUnscheduledPreds(SUnit *SU);
0098     SUnit *getSingleUnscheduledPred(SUnit *SU);
0099   };
0100 }
0101
0102 #endif