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/Target/MachineSchedInfo.h"
28 #include <Support/hash_set>
32 class SchedulingManager;
33 class FunctionLiveVarInfo;
35 //---------------------------------------------------------------------------
36 // Debug option levels for instruction scheduling
38 enum SchedDebugLevel_t {
41 Sched_PrintMachineCode,
42 Sched_PrintSchedTrace,
43 Sched_PrintSchedGraphs,
46 extern SchedDebugLevel_t SchedDebugLevel;
48 //---------------------------------------------------------------------------
49 // Function: instrIsFeasible
52 // Used by the priority analysis to filter out instructions
53 // that are not feasible to issue in the current cycle.
54 // Should only be used during schedule construction..
55 //---------------------------------------------------------------------------
57 bool instrIsFeasible(const SchedulingManager &S, MachineOpCode opCode);
61 struct NodeDelayPair {
62 const SchedGraphNode* node;
64 NodeDelayPair(const SchedGraphNode* n, cycles_t d) : node(n), delay(d) {}
65 inline bool operator<(const NodeDelayPair& np) { return delay < np.delay; }
69 NDPLessThan(const NodeDelayPair* np1, const NodeDelayPair* np2)
71 return np1->delay < np2->delay;
74 class NodeHeap: public std::list<NodeDelayPair*>, public NonCopyable {
76 typedef std::list<NodeDelayPair*>::iterator iterator;
77 typedef std::list<NodeDelayPair*>::const_iterator const_iterator;
80 NodeHeap() : _size(0) {}
82 inline unsigned size() const { return _size; }
84 const SchedGraphNode* getNode (const_iterator i) const { return (*i)->node; }
85 cycles_t getDelay(const_iterator i) const { return (*i)->delay;}
87 inline void makeHeap() {
88 // make_heap(begin(), end(), NDPLessThan);
91 inline iterator findNode(const SchedGraphNode* node) {
92 for (iterator I=begin(); I != end(); ++I)
93 if (getNode(I) == node)
98 inline void removeNode (const SchedGraphNode* node) {
99 iterator ndpPtr = findNode(node);
108 void insert(const SchedGraphNode* node, cycles_t delay) {
109 NodeDelayPair* ndp = new NodeDelayPair(node, delay);
110 if (_size == 0 || front()->delay < delay)
115 for ( ; I != end() && getDelay(I) >= delay; ++I)
117 std::list<NodeDelayPair*>::insert(I, ndp);
126 class SchedPriorities: public NonCopyable {
128 SchedPriorities(const Function *F, const SchedGraph *G,
129 FunctionLiveVarInfo &LVI);
132 // This must be called before scheduling begins.
135 cycles_t getTime () const { return curTime; }
136 cycles_t getEarliestReadyTime () const { return earliestReadyTime; }
137 unsigned getNumReady () const { return candsAsHeap.size(); }
138 bool nodeIsReady (const SchedGraphNode* node) const {
139 return (candsAsSet.find(node) != candsAsSet.end());
142 void issuedReadyNodeAt (cycles_t curTime,
143 const SchedGraphNode* node);
145 void insertReady (const SchedGraphNode* node);
147 void updateTime (cycles_t /*unused*/);
149 const SchedGraphNode* getNextHighest (const SchedulingManager& S,
151 // choose next highest priority instr
154 typedef NodeHeap::iterator candIndex;
158 const SchedGraph* graph;
159 FunctionLiveVarInfo &methodLiveVarInfo;
160 hash_map<const MachineInstr*, bool> lastUseMap;
161 std::vector<cycles_t> nodeDelayVec;
162 std::vector<cycles_t> nodeEarliestUseVec;
163 std::vector<cycles_t> earliestReadyTimeForNode;
164 cycles_t earliestReadyTime;
165 NodeHeap candsAsHeap; // candidate nodes, ready to go
166 hash_set<const SchedGraphNode*> candsAsSet; //same entries as candsAsHeap,
167 // but as set for fast lookup
168 std::vector<candIndex> mcands; // holds pointers into cands
169 candIndex nextToTry; // next cand after the last
170 // one tried in this cycle
172 int chooseByRule1 (std::vector<candIndex>& mcands);
173 int chooseByRule2 (std::vector<candIndex>& mcands);
174 int chooseByRule3 (std::vector<candIndex>& mcands);
176 void findSetWithMaxDelay (std::vector<candIndex>& mcands,
177 const SchedulingManager& S);
179 void computeDelays (const SchedGraph* graph);
181 void initializeReadyHeap (const SchedGraph* graph);
183 bool instructionHasLastUse (FunctionLiveVarInfo& LVI,
184 const SchedGraphNode* graphNode);
186 // NOTE: The next two return references to the actual vector entries.
187 // Use the following two if you don't need to modify the value.
188 cycles_t& getNodeDelayRef (const SchedGraphNode* node) {
189 assert(node->getNodeId() < nodeDelayVec.size());
190 return nodeDelayVec[node->getNodeId()];
192 cycles_t& getEarliestReadyTimeForNodeRef (const SchedGraphNode* node) {
193 assert(node->getNodeId() < earliestReadyTimeForNode.size());
194 return earliestReadyTimeForNode[node->getNodeId()];
197 cycles_t getNodeDelay (const SchedGraphNode* node) const {
198 return ((SchedPriorities*) this)->getNodeDelayRef(node);
200 cycles_t getEarliestReadyTimeForNode(const SchedGraphNode* node) const {
201 return ((SchedPriorities*) this)->getEarliestReadyTimeForNodeRef(node);
206 inline void SchedPriorities::updateTime(cycles_t c) {
208 nextToTry = candsAsHeap.begin();
212 inline std::ostream &operator<<(std::ostream &os, const NodeDelayPair* nd) {
213 return os << "Delay for node " << nd->node->getNodeId()
214 << " = " << (long)nd->delay << "\n";