1 | //===---- LatencyPriorityQueue.h - A latency-oriented priority queue ------===// |
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 LatencyPriorityQueue class, which is a |
10 | // SchedulingPriorityQueue that schedules using latency information to |
11 | // reduce the length of the critical path through the basic block. |
12 | // |
13 | //===----------------------------------------------------------------------===// |
14 | |
15 | #ifndef LLVM_CODEGEN_LATENCYPRIORITYQUEUE_H |
16 | #define LLVM_CODEGEN_LATENCYPRIORITYQUEUE_H |
17 | |
18 | #include "llvm/CodeGen/ScheduleDAG.h" |
19 | #include "llvm/Config/llvm-config.h" |
20 | |
21 | namespace llvm { |
22 | class LatencyPriorityQueue; |
23 | |
24 | /// Sorting functions for the Available queue. |
25 | struct latency_sort { |
26 | LatencyPriorityQueue *PQ; |
27 | explicit latency_sort(LatencyPriorityQueue *pq) : PQ(pq) {} |
28 | |
29 | bool operator()(const SUnit* LHS, const SUnit* RHS) const; |
30 | }; |
31 | |
32 | class LatencyPriorityQueue : public SchedulingPriorityQueue { |
33 | // SUnits - The SUnits for the current graph. |
34 | std::vector<SUnit> *SUnits = nullptr; |
35 | |
36 | /// NumNodesSolelyBlocking - This vector contains, for every node in the |
37 | /// Queue, the number of nodes that the node is the sole unscheduled |
38 | /// predecessor for. This is used as a tie-breaker heuristic for better |
39 | /// mobility. |
40 | std::vector<unsigned> NumNodesSolelyBlocking; |
41 | |
42 | /// Queue - The queue. |
43 | std::vector<SUnit*> Queue; |
44 | latency_sort Picker; |
45 | |
46 | public: |
47 | LatencyPriorityQueue() : Picker(this) { |
48 | } |
49 | |
50 | bool isBottomUp() const override { return false; } |
51 | |
52 | void initNodes(std::vector<SUnit> &sunits) override { |
53 | SUnits = &sunits; |
54 | NumNodesSolelyBlocking.resize(new_size: SUnits->size(), x: 0); |
55 | } |
56 | |
57 | void addNode(const SUnit *SU) override { |
58 | NumNodesSolelyBlocking.resize(new_size: SUnits->size(), x: 0); |
59 | } |
60 | |
61 | void updateNode(const SUnit *SU) override { |
62 | } |
63 | |
64 | void releaseState() override { |
65 | SUnits = nullptr; |
66 | } |
67 | |
68 | unsigned getLatency(unsigned NodeNum) const { |
69 | assert(NodeNum < (*SUnits).size()); |
70 | return (*SUnits)[NodeNum].getHeight(); |
71 | } |
72 | |
73 | unsigned getNumSolelyBlockNodes(unsigned NodeNum) const { |
74 | assert(NodeNum < NumNodesSolelyBlocking.size()); |
75 | return NumNodesSolelyBlocking[NodeNum]; |
76 | } |
77 | |
78 | bool empty() const override { return Queue.empty(); } |
79 | |
80 | void push(SUnit *U) override; |
81 | |
82 | SUnit *pop() override; |
83 | |
84 | void remove(SUnit *SU) override; |
85 | |
86 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
87 | LLVM_DUMP_METHOD void dump(ScheduleDAG *DAG) const override; |
88 | #endif |
89 | |
90 | // scheduledNode - As nodes are scheduled, we look to see if there are any |
91 | // successor nodes that have a single unscheduled predecessor. If so, that |
92 | // single predecessor has a higher priority, since scheduling it will make |
93 | // the node available. |
94 | void scheduledNode(SUnit *SU) override; |
95 | |
96 | private: |
97 | void AdjustPriorityOfUnscheduledPreds(SUnit *SU); |
98 | SUnit *getSingleUnscheduledPred(SUnit *SU); |
99 | }; |
100 | } |
101 | |
102 | #endif |
103 | |