LatencyPriorityQueue.h revision 341825 
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
19#include "llvm/CodeGen/ScheduleDAG.h"
20#include "llvm/Config/llvm-config.h"
21
22namespace llvm {
23  class LatencyPriorityQueue;
24
25  /// Sorting functions for the Available queue.
26  struct latency_sort {
27    LatencyPriorityQueue *PQ;
28    explicit latency_sort(LatencyPriorityQueue *pq) : PQ(pq) {}
29
30    bool operator()(const SUnit* LHS, const SUnit* RHS) const;
31  };
32
33  class LatencyPriorityQueue : public SchedulingPriorityQueue {
34    // SUnits - The SUnits for the current graph.
35    std::vector<SUnit> *SUnits;
36
37    /// NumNodesSolelyBlocking - This vector contains, for every node in the
38    /// Queue, the number of nodes that the node is the sole unscheduled
39    /// predecessor for.  This is used as a tie-breaker heuristic for better
40    /// mobility.
41    std::vector<unsigned> NumNodesSolelyBlocking;
42
43    /// Queue - The queue.
44    std::vector<SUnit*> Queue;
45    latency_sort Picker;
46
47  public:
48    LatencyPriorityQueue() : Picker(this) {
49    }
50
51    bool isBottomUp() const override { return false; }
52
53    void initNodes(std::vector<SUnit> &sunits) override {
54      SUnits = &sunits;
55      NumNodesSolelyBlocking.resize(SUnits->size(), 0);
56    }
57
58    void addNode(const SUnit *SU) override {
59      NumNodesSolelyBlocking.resize(SUnits->size(), 0);
60    }
61
62    void updateNode(const SUnit *SU) override {
63    }
64
65    void releaseState() override {
66      SUnits = nullptr;
67    }
68
69    unsigned getLatency(unsigned NodeNum) const {
70      assert(NodeNum < (*SUnits).size());
71      return (*SUnits)[NodeNum].getHeight();
72    }
73
74    unsigned getNumSolelyBlockNodes(unsigned NodeNum) const {
75      assert(NodeNum < NumNodesSolelyBlocking.size());
76      return NumNodesSolelyBlocking[NodeNum];
77    }
78
79    bool empty() const override { return Queue.empty(); }
80
81    void push(SUnit *U) override;
82
83    SUnit *pop() override;
84
85    void remove(SUnit *SU) override;
86
87#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
88    LLVM_DUMP_METHOD void dump(ScheduleDAG *DAG) const override;
89#endif
90
91    // scheduledNode - As nodes are scheduled, we look to see if there are any
92    // successor nodes that have a single unscheduled predecessor.  If so, that
93    // single predecessor has a higher priority, since scheduling it will make
94    // the node available.
95    void scheduledNode(SUnit *SU) override;
96
97private:
98    void AdjustPriorityOfUnscheduledPreds(SUnit *SU);
99    SUnit *getSingleUnscheduledPred(SUnit *SU);
100  };
101}
102
103#endif
104