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/MachineSchedInfo.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*>, public NonCopyable {
68 typedef std::list<NodeDelayPair*>::iterator iterator;
69 typedef std::list<NodeDelayPair*>::const_iterator const_iterator;
72 NodeHeap() : _size(0) {}
74 inline unsigned size() const { return _size; }
76 const SchedGraphNode* getNode (const_iterator i) const { return (*i)->node; }
77 cycles_t getDelay(const_iterator i) const { return (*i)->delay;}
79 inline void makeHeap() {
80 // make_heap(begin(), end(), NDPLessThan);
83 inline iterator findNode(const SchedGraphNode* node) {
84 for (iterator I=begin(); I != end(); ++I)
85 if (getNode(I) == node)
90 inline void removeNode (const SchedGraphNode* node) {
91 iterator ndpPtr = findNode(node);
100 void insert(const SchedGraphNode* node, cycles_t delay) {
101 NodeDelayPair* ndp = new NodeDelayPair(node, delay);
102 if (_size == 0 || front()->delay < delay)
107 for ( ; I != end() && getDelay(I) >= delay; ++I)
109 std::list<NodeDelayPair*>::insert(I, ndp);
118 class SchedPriorities: public NonCopyable {
120 SchedPriorities(const Function *F, const SchedGraph *G,
121 FunctionLiveVarInfo &LVI);
124 // This must be called before scheduling begins.
127 cycles_t getTime () const { return curTime; }
128 cycles_t getEarliestReadyTime () const { return earliestReadyTime; }
129 unsigned getNumReady () const { return candsAsHeap.size(); }
130 bool nodeIsReady (const SchedGraphNode* node) const {
131 return (candsAsSet.find(node) != candsAsSet.end());
134 void issuedReadyNodeAt (cycles_t curTime,
135 const SchedGraphNode* node);
137 void insertReady (const SchedGraphNode* node);
139 void updateTime (cycles_t /*unused*/);
141 const SchedGraphNode* getNextHighest (const SchedulingManager& S,
143 // choose next highest priority instr
146 typedef NodeHeap::iterator candIndex;
150 const SchedGraph* graph;
151 FunctionLiveVarInfo &methodLiveVarInfo;
152 hash_map<const MachineInstr*, bool> lastUseMap;
153 std::vector<cycles_t> nodeDelayVec;
154 std::vector<cycles_t> nodeEarliestUseVec;
155 std::vector<cycles_t> earliestReadyTimeForNode;
156 cycles_t earliestReadyTime;
157 NodeHeap candsAsHeap; // candidate nodes, ready to go
158 hash_set<const SchedGraphNode*> candsAsSet; //same entries as candsAsHeap,
159 // but as set for fast lookup
160 std::vector<candIndex> mcands; // holds pointers into cands
161 candIndex nextToTry; // next cand after the last
162 // one tried in this cycle
164 int chooseByRule1 (std::vector<candIndex>& mcands);
165 int chooseByRule2 (std::vector<candIndex>& mcands);
166 int chooseByRule3 (std::vector<candIndex>& mcands);
168 void findSetWithMaxDelay (std::vector<candIndex>& mcands,
169 const SchedulingManager& S);
171 void computeDelays (const SchedGraph* graph);
173 void initializeReadyHeap (const SchedGraph* graph);
175 bool instructionHasLastUse (FunctionLiveVarInfo& LVI,
176 const SchedGraphNode* graphNode);
178 // NOTE: The next two return references to the actual vector entries.
179 // Use the following two if you don't need to modify the value.
180 cycles_t& getNodeDelayRef (const SchedGraphNode* node) {
181 assert(node->getNodeId() < nodeDelayVec.size());
182 return nodeDelayVec[node->getNodeId()];
184 cycles_t& getEarliestReadyTimeForNodeRef (const SchedGraphNode* node) {
185 assert(node->getNodeId() < earliestReadyTimeForNode.size());
186 return earliestReadyTimeForNode[node->getNodeId()];
189 cycles_t getNodeDelay (const SchedGraphNode* node) const {
190 return ((SchedPriorities*) this)->getNodeDelayRef(node);
192 cycles_t getEarliestReadyTimeForNode(const SchedGraphNode* node) const {
193 return ((SchedPriorities*) this)->getEarliestReadyTimeForNodeRef(node);
198 inline void SchedPriorities::updateTime(cycles_t c) {
200 nextToTry = candsAsHeap.begin();
204 std::ostream &operator<<(std::ostream &os, const NodeDelayPair* nd);