1 //===-- SchedPriorities.h - Encapsulate scheduling heuristics --*- C++ -*--===//
4 // Priority ordering rules:
5 // (1) Max delay, which is the order of the heap S.candsAsHeap.
6 // (2) Instruction that frees up a register.
7 // (3) Instruction that has the maximum number of dependent instructions.
8 // Note that rules 2 and 3 are only used if issue conflicts prevent
9 // choosing a higher priority instruction by rule 1.
11 //===----------------------------------------------------------------------===//
13 #ifndef LLVM_CODEGEN_SCHEDPRIORITIES_H
14 #define LLVM_CODEGEN_SCHEDPRIORITIES_H
16 #include "SchedGraph.h"
17 #include "llvm/CodeGen/InstrScheduling.h"
18 #include "llvm/Target/TargetSchedInfo.h"
19 #include "Support/hash_set"
24 class SchedulingManager;
25 class FunctionLiveVarInfo;
27 //---------------------------------------------------------------------------
28 // Debug option levels for instruction scheduling
30 enum SchedDebugLevel_t {
33 Sched_PrintMachineCode,
34 Sched_PrintSchedTrace,
35 Sched_PrintSchedGraphs,
38 extern SchedDebugLevel_t SchedDebugLevel;
40 //---------------------------------------------------------------------------
41 // Function: instrIsFeasible
44 // Used by the priority analysis to filter out instructions
45 // that are not feasible to issue in the current cycle.
46 // Should only be used during schedule construction..
47 //---------------------------------------------------------------------------
49 bool instrIsFeasible(const SchedulingManager &S, MachineOpCode opCode);
53 struct NodeDelayPair {
54 const SchedGraphNode* node;
56 NodeDelayPair(const SchedGraphNode* n, cycles_t d) : node(n), delay(d) {}
57 inline bool operator<(const NodeDelayPair& np) { return delay < np.delay; }
61 NDPLessThan(const NodeDelayPair* np1, const NodeDelayPair* np2)
63 return np1->delay < np2->delay;
66 class NodeHeap : public std::list<NodeDelayPair*> {
67 NodeHeap(const NodeHeap&); // DO NOT IMPLEMENT
68 void operator=(const NodeHeap&); // DO NOT IMPLEMENT
70 typedef std::list<NodeDelayPair*>::iterator iterator;
71 typedef std::list<NodeDelayPair*>::const_iterator const_iterator;
74 NodeHeap() : _size(0) {}
76 inline unsigned size() const { return _size; }
78 const SchedGraphNode* getNode (const_iterator i) const { return (*i)->node; }
79 cycles_t getDelay(const_iterator i) const { return (*i)->delay;}
81 inline void makeHeap() {
82 // make_heap(begin(), end(), NDPLessThan);
85 inline iterator findNode(const SchedGraphNode* node) {
86 for (iterator I=begin(); I != end(); ++I)
87 if (getNode(I) == node)
92 inline void removeNode (const SchedGraphNode* node) {
93 iterator ndpPtr = findNode(node);
102 void insert(const SchedGraphNode* node, cycles_t delay) {
103 NodeDelayPair* ndp = new NodeDelayPair(node, delay);
104 if (_size == 0 || front()->delay < delay)
109 for ( ; I != end() && getDelay(I) >= delay; ++I)
111 std::list<NodeDelayPair*>::insert(I, ndp);
120 class SchedPriorities {
121 SchedPriorities(const SchedPriorities&); // DO NOT IMPLEMENT
122 void operator=(const SchedPriorities &); // DO NOT IMPLEMENT
124 SchedPriorities(const Function *F, const SchedGraph *G,
125 FunctionLiveVarInfo &LVI);
128 // This must be called before scheduling begins.
131 cycles_t getTime () const { return curTime; }
132 cycles_t getEarliestReadyTime () const { return earliestReadyTime; }
133 unsigned getNumReady () const { return candsAsHeap.size(); }
134 bool nodeIsReady (const SchedGraphNode* node) const {
135 return (candsAsSet.find(node) != candsAsSet.end());
138 void issuedReadyNodeAt (cycles_t curTime,
139 const SchedGraphNode* node);
141 void insertReady (const SchedGraphNode* node);
143 void updateTime (cycles_t /*unused*/);
145 const SchedGraphNode* getNextHighest (const SchedulingManager& S,
147 // choose next highest priority instr
150 typedef NodeHeap::iterator candIndex;
154 const SchedGraph* graph;
155 FunctionLiveVarInfo &methodLiveVarInfo;
156 hash_map<const MachineInstr*, bool> lastUseMap;
157 std::vector<cycles_t> nodeDelayVec;
158 std::vector<cycles_t> nodeEarliestUseVec;
159 std::vector<cycles_t> earliestReadyTimeForNode;
160 cycles_t earliestReadyTime;
161 NodeHeap candsAsHeap; // candidate nodes, ready to go
162 hash_set<const SchedGraphNode*> candsAsSet; //same entries as candsAsHeap,
163 // but as set for fast lookup
164 std::vector<candIndex> mcands; // holds pointers into cands
165 candIndex nextToTry; // next cand after the last
166 // one tried in this cycle
168 int chooseByRule1 (std::vector<candIndex>& mcands);
169 int chooseByRule2 (std::vector<candIndex>& mcands);
170 int chooseByRule3 (std::vector<candIndex>& mcands);
172 void findSetWithMaxDelay (std::vector<candIndex>& mcands,
173 const SchedulingManager& S);
175 void computeDelays (const SchedGraph* graph);
177 void initializeReadyHeap (const SchedGraph* graph);
179 bool instructionHasLastUse (FunctionLiveVarInfo& LVI,
180 const SchedGraphNode* graphNode);
182 // NOTE: The next two return references to the actual vector entries.
183 // Use the following two if you don't need to modify the value.
184 cycles_t& getNodeDelayRef (const SchedGraphNode* node) {
185 assert(node->getNodeId() < nodeDelayVec.size());
186 return nodeDelayVec[node->getNodeId()];
188 cycles_t& getEarliestReadyTimeForNodeRef (const SchedGraphNode* node) {
189 assert(node->getNodeId() < earliestReadyTimeForNode.size());
190 return earliestReadyTimeForNode[node->getNodeId()];
193 cycles_t getNodeDelay (const SchedGraphNode* node) const {
194 return ((SchedPriorities*) this)->getNodeDelayRef(node);
196 cycles_t getEarliestReadyTimeForNode(const SchedGraphNode* node) const {
197 return ((SchedPriorities*) this)->getEarliestReadyTimeForNodeRef(node);
202 inline void SchedPriorities::updateTime(cycles_t c) {
204 nextToTry = candsAsHeap.begin();
208 std::ostream &operator<<(std::ostream &os, const NodeDelayPair* nd);