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
21namespace 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
96private:
97 void AdjustPriorityOfUnscheduledPreds(SUnit *SU);
98 SUnit *getSingleUnscheduledPred(SUnit *SU);
99 };
100}
101
102#endif
103

source code of llvm/include/llvm/CodeGen/LatencyPriorityQueue.h