LLVM 19.0.0git
LatencyPriorityQueue.h
Go to the documentation of this file.
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
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 {
27 explicit latency_sort(LatencyPriorityQueue *pq) : PQ(pq) {}
28
29 bool operator()(const SUnit* LHS, const SUnit* RHS) const;
30 };
31
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(SUnits->size(), 0);
55 }
56
57 void addNode(const SUnit *SU) override {
58 NumNodesSolelyBlocking.resize(SUnits->size(), 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
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:529
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Value * RHS
Value * LHS
unsigned getNumSolelyBlockNodes(unsigned NodeNum) const
void push(SUnit *U) override
LLVM_DUMP_METHOD void dump(ScheduleDAG *DAG) const override
void remove(SUnit *SU) override
void scheduledNode(SUnit *SU) override
As each node is scheduled, this method is invoked.
void addNode(const SUnit *SU) override
void initNodes(std::vector< SUnit > &sunits) override
unsigned getLatency(unsigned NodeNum) const
bool empty() const override
void updateNode(const SUnit *SU) override
bool isBottomUp() const override
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:242
This interface is used to plug different priorities computation algorithms into the list scheduler.
Definition: ScheduleDAG.h:496
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
Sorting functions for the Available queue.
latency_sort(LatencyPriorityQueue *pq)
LatencyPriorityQueue * PQ
bool operator()(const SUnit *LHS, const SUnit *RHS) const