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    std::unique_ptr<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    int HorizontalVerticalBalance;
76
77  public:
78    ResourcePriorityQueue(SelectionDAGISel *IS);
79
80    bool isBottomUp() const override { return false; }
81
82    void initNodes(std::vector<SUnit> &sunits) override;
83
84    void addNode(const SUnit *SU) override {
85      NumNodesSolelyBlocking.resize(SUnits->size(), 0);
86    }
87
88    void updateNode(const SUnit *SU) override {}
89
90    void releaseState() override {
91      SUnits = nullptr;
92    }
93
94    unsigned getLatency(unsigned NodeNum) const {
95      assert(NodeNum < (*SUnits).size());
96      return (*SUnits)[NodeNum].getHeight();
97    }
98
99    unsigned getNumSolelyBlockNodes(unsigned NodeNum) const {
100      assert(NodeNum < NumNodesSolelyBlocking.size());
101      return NumNodesSolelyBlocking[NodeNum];
102    }
103
104    /// Single cost function reflecting benefit of scheduling SU
105    /// in the current cycle.
106    int SUSchedulingCost (SUnit *SU);
107
108    /// InitNumRegDefsLeft - Determine the # of regs defined by this node.
109    ///
110    void initNumRegDefsLeft(SUnit *SU);
111    void updateNumRegDefsLeft(SUnit *SU);
112    int regPressureDelta(SUnit *SU, bool RawPressure = false);
113    int rawRegPressureDelta (SUnit *SU, unsigned RCId);
114
115    bool empty() const override { return Queue.empty(); }
116
117    void push(SUnit *U) override;
118
119    SUnit *pop() override;
120
121    void remove(SUnit *SU) override;
122
123    /// scheduledNode - Main resource tracking point.
124    void scheduledNode(SUnit *Node) override;
125    bool isResourceAvailable(SUnit *SU);
126    void reserveResources(SUnit *SU);
127
128private:
129    void adjustPriorityOfUnscheduledPreds(SUnit *SU);
130    SUnit *getSingleUnscheduledPred(SUnit *SU);
131    unsigned numberRCValPredInSU (SUnit *SU, unsigned RCId);
132    unsigned numberRCValSuccInSU (SUnit *SU, unsigned RCId);
133  };
134}
135
136#endif
137