Added a separate class (PBQPBuilder) for PBQP Problem construction. This class can...
[oota-llvm.git] / include / llvm / CodeGen / LatencyPriorityQueue.h
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
21 namespace llvm {
22   class LatencyPriorityQueue;
23   
24   /// Sorting functions for the Available queue.
25   struct latency_sort : public std::binary_function<SUnit*, SUnit*, bool> {
26     LatencyPriorityQueue *PQ;
27     explicit latency_sort(LatencyPriorityQueue *pq) : PQ(pq) {}
28     
29     bool operator()(const SUnit* left, const SUnit* right) const;
30   };
31
32   class LatencyPriorityQueue : public SchedulingPriorityQueue {
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     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     virtual SUnit *pop();
81
82     virtual void remove(SUnit *SU);
83
84     // ScheduledNode - As nodes are scheduled, we look to see if there are any
85     // successor nodes that have a single unscheduled predecessor.  If so, that
86     // single predecessor has a higher priority, since scheduling it will make
87     // the node available.
88     void ScheduledNode(SUnit *Node);
89
90 private:
91     void AdjustPriorityOfUnscheduledPreds(SUnit *SU);
92     SUnit *getSingleUnscheduledPred(SUnit *SU);
93   };
94 }
95
96 #endif