LatencyPriorityQueue.h revision 198892 
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    /// IgnoreAntiDep - Ignore anti-dependencies
44    bool IgnoreAntiDep;
45
46    /// Queue - The queue.
47    PriorityQueue<SUnit*, std::vector<SUnit*>, latency_sort> Queue;
48
49public:
50  LatencyPriorityQueue() : IgnoreAntiDep(false), Queue(latency_sort(this)) {
51    }
52
53    void setIgnoreAntiDep(bool ignore) {
54      IgnoreAntiDep = ignore;
55    }
56
57    void initNodes(std::vector<SUnit> &sunits) {
58      SUnits = &sunits;
59      NumNodesSolelyBlocking.resize(SUnits->size(), 0);
60    }
61
62    void addNode(const SUnit *SU) {
63      NumNodesSolelyBlocking.resize(SUnits->size(), 0);
64    }
65
66    void updateNode(const SUnit *SU) {
67    }
68
69    void releaseState() {
70      SUnits = 0;
71    }
72
73    unsigned getLatency(unsigned NodeNum) const {
74      assert(NodeNum < (*SUnits).size());
75      return (*SUnits)[NodeNum].getHeight(IgnoreAntiDep);
76    }
77
78    unsigned getNumSolelyBlockNodes(unsigned NodeNum) const {
79      assert(NodeNum < NumNodesSolelyBlocking.size());
80      return NumNodesSolelyBlocking[NodeNum];
81    }
82
83    unsigned size() const { return Queue.size(); }
84
85    bool empty() const { return Queue.empty(); }
86
87    virtual void push(SUnit *U) {
88      push_impl(U);
89    }
90    void push_impl(SUnit *U);
91
92    void push_all(const std::vector<SUnit *> &Nodes) {
93      for (unsigned i = 0, e = Nodes.size(); i != e; ++i)
94        push_impl(Nodes[i]);
95    }
96
97    SUnit *pop() {
98      if (empty()) return NULL;
99      SUnit *V = Queue.top();
100      Queue.pop();
101      return V;
102    }
103
104    void remove(SUnit *SU) {
105      assert(!Queue.empty() && "Not in queue!");
106      Queue.erase_one(SU);
107    }
108
109    // ScheduledNode - As nodes are scheduled, we look to see if there are any
110    // successor nodes that have a single unscheduled predecessor.  If so, that
111    // single predecessor has a higher priority, since scheduling it will make
112    // the node available.
113    void ScheduledNode(SUnit *Node);
114
115private:
116    void AdjustPriorityOfUnscheduledPreds(SUnit *SU);
117    SUnit *getSingleUnscheduledPred(SUnit *SU);
118  };
119}
120
121#endif
122