2 //***************************************************************************
7 // Encapsulate heuristics for instruction scheduling.
10 // Priority ordering rules:
11 // (1) Max delay, which is the order of the heap S.candsAsHeap.
12 // (2) Instruction that frees up a register.
13 // (3) Instruction that has the maximum number of dependent instructions.
14 // Note that rules 2 and 3 are only used if issue conflicts prevent
15 // choosing a higher priority instruction by rule 1.
18 // 7/30/01 - Vikram Adve - Created
19 //**************************************************************************/
21 #ifndef LLVM_CODEGEN_SCHEDPRIORITIES_H
22 #define LLVM_CODEGEN_SCHEDPRIORITIES_H
24 #include "SchedGraph.h"
25 #include "llvm/CodeGen/InstrScheduling.h"
26 #include "llvm/Analysis/LiveVar/MethodLiveVarInfo.h"
27 #include "llvm/Target/MachineSchedInfo.h"
31 class SchedulingManager;
34 struct NodeDelayPair {
35 const SchedGraphNode* node;
37 NodeDelayPair(const SchedGraphNode* n, cycles_t d) : node(n), delay(d) {}
38 inline bool operator< (const NodeDelayPair& np) { return delay < np.delay; }
42 NDPLessThan(const NodeDelayPair* np1, const NodeDelayPair* np2)
44 return (np1->delay < np2->delay);
47 class NodeHeap: public list<NodeDelayPair*>, public NonCopyable {
49 typedef list<NodeDelayPair*>::iterator iterator;
50 typedef list<NodeDelayPair*>::const_iterator const_iterator;
53 /*ctor*/ NodeHeap () : list<NodeDelayPair*>(), _size(0) {}
54 /*dtor*/ ~NodeHeap () {}
56 inline unsigned int size () const { return _size; }
58 const SchedGraphNode* getNode (const_iterator i) const { return (*i)->node; }
59 cycles_t getDelay(const_iterator i) const { return (*i)->delay;}
61 inline void makeHeap() {
62 // make_heap(begin(), end(), NDPLessThan);
65 inline iterator findNode(const SchedGraphNode* node) {
66 for (iterator I=begin(); I != end(); ++I)
67 if (getNode(I) == node)
72 inline void removeNode (const SchedGraphNode* node) {
73 iterator ndpPtr = findNode(node);
82 void insert(const SchedGraphNode* node, cycles_t delay) {
83 NodeDelayPair* ndp = new NodeDelayPair(node, delay);
84 if (_size == 0 || front()->delay < delay)
89 for ( ; I != end() && getDelay(I) >= delay; ++I)
91 list<NodeDelayPair*>::insert(I, ndp);
100 class SchedPriorities: public NonCopyable {
102 /*ctor*/ SchedPriorities (const Method* method,
103 const SchedGraph* _graph);
105 // This must be called before scheduling begins.
108 cycles_t getTime () const { return curTime; }
109 cycles_t getEarliestReadyTime () const { return earliestReadyTime; }
110 unsigned getNumReady () const { return candsAsHeap.size(); }
111 bool nodeIsReady (const SchedGraphNode* node) const {
112 return (candsAsSet.find(node) != candsAsSet.end());
115 void issuedReadyNodeAt (cycles_t curTime,
116 const SchedGraphNode* node);
118 void insertReady (const SchedGraphNode* node);
120 void updateTime (cycles_t /*unused*/);
122 const SchedGraphNode* getNextHighest (const SchedulingManager& S,
124 // choose next highest priority instr
127 typedef NodeHeap::iterator candIndex;
131 const SchedGraph* graph;
132 MethodLiveVarInfo methodLiveVarInfo;
133 hash_map<const MachineInstr*, bool> lastUseMap;
134 vector<cycles_t> nodeDelayVec;
135 vector<cycles_t> earliestForNode;
136 cycles_t earliestReadyTime;
137 NodeHeap candsAsHeap; // candidate nodes, ready to go
138 hash_set<const SchedGraphNode*> candsAsSet; // same entries as candsAsHeap,
139 // but as set for fast lookup
140 vector<candIndex> mcands; // holds pointers into cands
141 candIndex nextToTry; // next cand after the last
142 // one tried in this cycle
144 int chooseByRule1 (vector<candIndex>& mcands);
145 int chooseByRule2 (vector<candIndex>& mcands);
146 int chooseByRule3 (vector<candIndex>& mcands);
148 void findSetWithMaxDelay (vector<candIndex>& mcands,
149 const SchedulingManager& S);
151 void computeDelays (const SchedGraph* graph);
153 void initializeReadyHeap (const SchedGraph* graph);
155 bool instructionHasLastUse (MethodLiveVarInfo& methodLiveVarInfo,
156 const SchedGraphNode* graphNode);
158 // NOTE: The next two return references to the actual vector entries.
160 cycles_t& getNodeDelayRef (const SchedGraphNode* node) {
161 assert(node->getNodeId() < nodeDelayVec.size());
162 return nodeDelayVec[node->getNodeId()];
164 cycles_t& getEarliestForNodeRef (const SchedGraphNode* node) {
165 assert(node->getNodeId() < earliestForNode.size());
166 return earliestForNode[node->getNodeId()];
172 SchedPriorities::insertReady(const SchedGraphNode* node)
174 candsAsHeap.insert(node, nodeDelayVec[node->getNodeId()]);
175 candsAsSet.insert(node);
176 mcands.clear(); // ensure reset choices is called before any more choices
177 earliestReadyTime = min(earliestReadyTime,
178 earliestForNode[node->getNodeId()]);
180 if (SchedDebugLevel >= Sched_PrintSchedTrace)
182 cout << " Cycle " << this->getTime() << ": "
183 << " Node " << node->getNodeId() << " is ready; "
184 << " Delay = " << this->getNodeDelayRef(node) << "; Instruction: "
186 cout << " " << *node->getMachineInstr() << endl;
190 inline void SchedPriorities::updateTime(cycles_t c) {
192 nextToTry = candsAsHeap.begin();
196 inline ostream& operator<< (ostream& os, const NodeDelayPair* nd) {
197 return os << "Delay for node " << nd->node->getNodeId()
198 << " = " << nd->delay << endl;
201 /***************************************************************************/