LatencyPriorityQueue.h revision 193323 
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 LATENCY_PRIORITY_QUEUE_H
17#define LATENCY_PRIORITY_QUEUE_H
18
19#include "llvm/CodeGen/ScheduleDAG.h"
20#include "llvm/ADT/PriorityQueue.h"
21
22namespace llvm {
23  class LatencyPriorityQueue;
24
25  /// Sorting functions for the Available queue.
26  struct latency_sort : public std::binary_function<SUnit*, SUnit*, bool> {
27    LatencyPriorityQueue *PQ;
28    explicit latency_sort(LatencyPriorityQueue *pq) : PQ(pq) {}
29
30    bool operator()(const SUnit* left, const SUnit* right) 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    PriorityQueue<SUnit*, std::vector<SUnit*>, latency_sort> Queue;
44public:
45    LatencyPriorityQueue() : Queue(latency_sort(this)) {
46    }
47
48    void initNodes(std::vector<SUnit> &sunits) {
49      SUnits = &sunits;
50      NumNodesSolelyBlocking.resize(SUnits->size(), 0);
51    }
52
53    void addNode(const SUnit *SU) {
54      NumNodesSolelyBlocking.resize(SUnits->size(), 0);
55    }
56
57    void updateNode(const SUnit *SU) {
58    }
59
60    void releaseState() {
61      SUnits = 0;
62    }
63
64    unsigned getLatency(unsigned NodeNum) const {
65      assert(NodeNum < (*SUnits).size());
66      return (*SUnits)[NodeNum].getHeight();
67    }
68
69    unsigned getNumSolelyBlockNodes(unsigned NodeNum) const {
70      assert(NodeNum < NumNodesSolelyBlocking.size());
71      return NumNodesSolelyBlocking[NodeNum];
72    }
73
74    unsigned size() const { return Queue.size(); }
75
76    bool empty() const { return Queue.empty(); }
77
78    virtual void push(SUnit *U) {
79      push_impl(U);
80    }
81    void push_impl(SUnit *U);
82
83    void push_all(const std::vector<SUnit *> &Nodes) {
84      for (unsigned i = 0, e = Nodes.size(); i != e; ++i)
85        push_impl(Nodes[i]);
86    }
87
88    SUnit *pop() {
89      if (empty()) return NULL;
90      SUnit *V = Queue.top();
91      Queue.pop();
92      return V;
93    }
94
95    void remove(SUnit *SU) {
96      assert(!Queue.empty() && "Not in queue!");
97      Queue.erase_one(SU);
98    }
99
100    // ScheduledNode - As nodes are scheduled, we look to see if there are any
101    // successor nodes that have a single unscheduled predecessor.  If so, that
102    // single predecessor has a higher priority, since scheduling it will make
103    // the node available.
104    void ScheduledNode(SUnit *Node);
105
106private:
107    void AdjustPriorityOfUnscheduledPreds(SUnit *SU);
108    SUnit *getSingleUnscheduledPred(SUnit *SU);
109  };
110}
111
112#endif
113