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