LLVM  6.0.0svn
LatencyPriorityQueue.h
Go to the documentation of this file.
1 //===---- LatencyPriorityQueue.h - A latency-oriented priority queue ------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file declares the LatencyPriorityQueue class, which is a
11 // SchedulingPriorityQueue that schedules using latency information to
12 // reduce the length of the critical path through the basic block.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #ifndef LLVM_CODEGEN_LATENCYPRIORITYQUEUE_H
17 #define LLVM_CODEGEN_LATENCYPRIORITYQUEUE_H
18 
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* left, const SUnit* right) 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  // scheduledNode - As nodes are scheduled, we look to see if there are any
87  // successor nodes that have a single unscheduled predecessor. If so, that
88  // single predecessor has a higher priority, since scheduling it will make
89  // the node available.
90  void scheduledNode(SUnit *Node) override;
91 
92 private:
93  void AdjustPriorityOfUnscheduledPreds(SUnit *SU);
94  SUnit *getSingleUnscheduledPred(SUnit *SU);
95  };
96 }
97 
98 #endif
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
This interface is used to plug different priorities computation algorithms into the list scheduler...
Definition: ScheduleDAG.h:506
unsigned getLatency(unsigned NodeNum) const
latency_sort(LatencyPriorityQueue *pq)
Sorting functions for the Available queue.
LatencyPriorityQueue * PQ
bool operator()(const SUnit *left, const SUnit *right) const
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:247
void updateNode(const SUnit *SU) override