LLVM  10.0.0svn
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
This class represents lattice values for constants.
Definition: AllocatorList.h:23
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:484
This interface is used to plug different priorities computation algorithms into the list scheduler...
Definition: ScheduleDAG.h:496
bool operator()(const SUnit *LHS, const SUnit *RHS) const
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
static void push(SmallVectorImpl< uint64_t > &R, StringRef Str)
unsigned getLatency(unsigned NodeNum) const
latency_sort(LatencyPriorityQueue *pq)
Sorting functions for the Available queue.
LatencyPriorityQueue * PQ
unsigned getNumSolelyBlockNodes(unsigned NodeNum) const
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void addNode(const SUnit *SU) override
bool empty() const override
void initNodes(std::vector< SUnit > &sunits) override
bool isBottomUp() const override
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:242
void updateNode(const SUnit *SU) override