LLVM  14.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 
21 namespace 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;
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 
96 private:
97  void AdjustPriorityOfUnscheduledPreds(SUnit *SU);
98  SUnit *getSingleUnscheduledPred(SUnit *SU);
99  };
100 }
101 
102 #endif
ScheduleDAG.h
LLVM_DUMP_METHOD
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:506
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
llvm::LatencyPriorityQueue::getLatency
unsigned getLatency(unsigned NodeNum) const
Definition: LatencyPriorityQueue.h:68
llvm::LatencyPriorityQueue::push
void push(SUnit *U) override
Definition: LatencyPriorityQueue.cpp:72
llvm::latency_sort::PQ
LatencyPriorityQueue * PQ
Definition: LatencyPriorityQueue.h:26
llvm::LatencyPriorityQueue::dump
LLVM_DUMP_METHOD void dump(ScheduleDAG *DAG) const override
Definition: LatencyPriorityQueue.cpp:139
llvm::LatencyPriorityQueue::getNumSolelyBlockNodes
unsigned getNumSolelyBlockNodes(unsigned NodeNum) const
Definition: LatencyPriorityQueue.h:73
llvm::LatencyPriorityQueue::isBottomUp
bool isBottomUp() const override
Definition: LatencyPriorityQueue.h:50
llvm::LatencyPriorityQueue::addNode
void addNode(const SUnit *SU) override
Definition: LatencyPriorityQueue.h:57
llvm::LatencyPriorityQueue::empty
bool empty() const override
Definition: LatencyPriorityQueue.h:78
llvm::LatencyPriorityQueue::updateNode
void updateNode(const SUnit *SU) override
Definition: LatencyPriorityQueue.h:61
llvm::LatencyPriorityQueue::initNodes
void initNodes(std::vector< SUnit > &sunits) override
Definition: LatencyPriorityQueue.h:52
llvm::latency_sort
Sorting functions for the Available queue.
Definition: LatencyPriorityQueue.h:25
llvm::LatencyPriorityQueue::LatencyPriorityQueue
LatencyPriorityQueue()
Definition: LatencyPriorityQueue.h:47
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::LatencyPriorityQueue::pop
SUnit * pop() override
Definition: LatencyPriorityQueue.cpp:115
llvm::ScheduleDAG
Definition: ScheduleDAG.h:555
this
Analysis the ScalarEvolution expression for r is this
Definition: README.txt:8
llvm::LatencyPriorityQueue::releaseState
void releaseState() override
Definition: LatencyPriorityQueue.h:64
llvm::LatencyPriorityQueue::scheduledNode
void scheduledNode(SUnit *SU) override
As each node is scheduled, this method is invoked.
Definition: LatencyPriorityQueue.cpp:89
llvm::LatencyPriorityQueue::remove
void remove(SUnit *SU) override
Definition: LatencyPriorityQueue.cpp:129
llvm::SUnit
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:242
llvm::SchedulingPriorityQueue
This interface is used to plug different priorities computation algorithms into the list scheduler.
Definition: ScheduleDAG.h:496
llvm::LatencyPriorityQueue
Definition: LatencyPriorityQueue.h:32
llvm::latency_sort::operator()
bool operator()(const SUnit *LHS, const SUnit *RHS) const
Definition: LatencyPriorityQueue.cpp:23
llvm::latency_sort::latency_sort
latency_sort(LatencyPriorityQueue *pq)
Definition: LatencyPriorityQueue.h:27