1//===----- ResourcePriorityQueue.h - A DFA-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 implements the ResourcePriorityQueue class, which is a
11// SchedulingPriorityQueue that schedules using DFA state to
12// reduce the length of the critical path through the basic block
13// on VLIW platforms.
14//
15//===----------------------------------------------------------------------===//
16
17#ifndef LLVM_CODEGEN_RESOURCEPRIORITYQUEUE_H
18#define LLVM_CODEGEN_RESOURCEPRIORITYQUEUE_H
19
20#include "llvm/CodeGen/DFAPacketizer.h"
21#include "llvm/CodeGen/ScheduleDAG.h"
22#include "llvm/CodeGen/SelectionDAGISel.h"
23#include "llvm/MC/MCInstrItineraries.h"
24#include "llvm/Target/TargetInstrInfo.h"
25#include "llvm/Target/TargetRegisterInfo.h"
26
27namespace llvm {
28  class ResourcePriorityQueue;
29
30  /// Sorting functions for the Available queue.
31  struct resource_sort : public std::binary_function<SUnit*, SUnit*, bool> {
32    ResourcePriorityQueue *PQ;
33    explicit resource_sort(ResourcePriorityQueue *pq) : PQ(pq) {}
34
35    bool operator()(const SUnit* left, const SUnit* right) const;
36  };
37
38  class ResourcePriorityQueue : public SchedulingPriorityQueue {
39    /// SUnits - The SUnits for the current graph.
40    std::vector<SUnit> *SUnits;
41
42    /// NumNodesSolelyBlocking - This vector contains, for every node in the
43    /// Queue, the number of nodes that the node is the sole unscheduled
44    /// predecessor for.  This is used as a tie-breaker heuristic for better
45    /// mobility.
46    std::vector<unsigned> NumNodesSolelyBlocking;
47
48    /// Queue - The queue.
49    std::vector<SUnit*> Queue;
50
51    /// RegPressure - Tracking current reg pressure per register class.
52    ///
53    std::vector<unsigned> RegPressure;
54
55    /// RegLimit - Tracking the number of allocatable registers per register
56    /// class.
57    std::vector<unsigned> RegLimit;
58
59    resource_sort Picker;
60    const TargetRegisterInfo *TRI;
61    const TargetLowering *TLI;
62    const TargetInstrInfo *TII;
63    const InstrItineraryData* InstrItins;
64    /// ResourcesModel - Represents VLIW state.
65    /// Not limited to VLIW targets per say, but assumes
66    /// definition of DFA by a target.
67    DFAPacketizer *ResourcesModel;
68
69    /// Resource model - packet/bundle model. Purely
70    /// internal at the time.
71    std::vector<SUnit*> Packet;
72
73    /// Heuristics for estimating register pressure.
74    unsigned ParallelLiveRanges;
75    signed HorizontalVerticalBalance;
76
77  public:
78    ResourcePriorityQueue(SelectionDAGISel *IS);
79
80    ~ResourcePriorityQueue() {
81      delete ResourcesModel;
82    }
83
84    bool isBottomUp() const { return false; }
85
86    void initNodes(std::vector<SUnit> &sunits);
87
88    void addNode(const SUnit *SU) {
89      NumNodesSolelyBlocking.resize(SUnits->size(), 0);
90    }
91
92    void updateNode(const SUnit *SU) {}
93
94    void releaseState() {
95      SUnits = 0;
96    }
97
98    unsigned getLatency(unsigned NodeNum) const {
99      assert(NodeNum < (*SUnits).size());
100      return (*SUnits)[NodeNum].getHeight();
101    }
102
103    unsigned getNumSolelyBlockNodes(unsigned NodeNum) const {
104      assert(NodeNum < NumNodesSolelyBlocking.size());
105      return NumNodesSolelyBlocking[NodeNum];
106    }
107
108    /// Single cost function reflecting benefit of scheduling SU
109    /// in the current cycle.
110    signed SUSchedulingCost (SUnit *SU);
111
112    /// InitNumRegDefsLeft - Determine the # of regs defined by this node.
113    ///
114    void initNumRegDefsLeft(SUnit *SU);
115    void updateNumRegDefsLeft(SUnit *SU);
116    signed regPressureDelta(SUnit *SU, bool RawPressure = false);
117    signed rawRegPressureDelta (SUnit *SU, unsigned RCId);
118
119    bool empty() const { return Queue.empty(); }
120
121    virtual void push(SUnit *U);
122
123    virtual SUnit *pop();
124
125    virtual void remove(SUnit *SU);
126
127    virtual void dump(ScheduleDAG* DAG) const;
128
129    /// scheduledNode - Main resource tracking point.
130    void scheduledNode(SUnit *Node);
131    bool isResourceAvailable(SUnit *SU);
132    void reserveResources(SUnit *SU);
133
134private:
135    void adjustPriorityOfUnscheduledPreds(SUnit *SU);
136    SUnit *getSingleUnscheduledPred(SUnit *SU);
137    unsigned numberRCValPredInSU (SUnit *SU, unsigned RCId);
138    unsigned numberRCValSuccInSU (SUnit *SU, unsigned RCId);
139  };
140}
141
142#endif
143