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 #include "SchedPriorities.h"
22 #include "Support/PostOrderIterator.h"
25 SchedPriorities::SchedPriorities(const Method* method,
26 const SchedGraph* _graph)
29 methodLiveVarInfo(method), // expensive!
31 nodeDelayVec(_graph->getNumNodes(),INVALID_LATENCY), //make errors obvious
32 earliestForNode(_graph->getNumNodes(), 0),
37 nextToTry(candsAsHeap.begin())
39 methodLiveVarInfo.analyze();
45 SchedPriorities::initialize()
47 initializeReadyHeap(graph);
52 SchedPriorities::computeDelays(const SchedGraph* graph)
54 po_iterator<const SchedGraph*> poIter = po_begin(graph), poEnd =po_end(graph);
55 for ( ; poIter != poEnd; ++poIter)
57 const SchedGraphNode* node = *poIter;
59 if (node->beginOutEdges() == node->endOutEdges())
60 nodeDelay = node->getLatency();
63 // Iterate over the out-edges of the node to compute delay
65 for (SchedGraphNode::const_iterator E=node->beginOutEdges();
66 E != node->endOutEdges(); ++E)
68 cycles_t sinkDelay = getNodeDelayRef((*E)->getSink());
69 nodeDelay = max(nodeDelay, sinkDelay + (*E)->getMinDelay());
72 getNodeDelayRef(node) = nodeDelay;
78 SchedPriorities::initializeReadyHeap(const SchedGraph* graph)
80 const SchedGraphNode* graphRoot = graph->getRoot();
81 assert(graphRoot->getMachineInstr() == NULL && "Expect dummy root");
83 // Insert immediate successors of dummy root, which are the actual roots
84 sg_succ_const_iterator SEnd = succ_end(graphRoot);
85 for (sg_succ_const_iterator S = succ_begin(graphRoot); S != SEnd; ++S)
86 this->insertReady(*S);
88 #undef TEST_HEAP_CONVERSION
89 #ifdef TEST_HEAP_CONVERSION
90 cout << "Before heap conversion:" << endl;
91 copy(candsAsHeap.begin(), candsAsHeap.end(),
92 ostream_iterator<NodeDelayPair*>(cout,"\n"));
95 candsAsHeap.makeHeap();
97 #ifdef TEST_HEAP_CONVERSION
98 cout << "After heap conversion:" << endl;
99 copy(candsAsHeap.begin(), candsAsHeap.end(),
100 ostream_iterator<NodeDelayPair*>(cout,"\n"));
106 SchedPriorities::issuedReadyNodeAt(cycles_t curTime,
107 const SchedGraphNode* node)
109 candsAsHeap.removeNode(node);
110 candsAsSet.erase(node);
111 mcands.clear(); // ensure reset choices is called before any more choices
113 if (earliestReadyTime == getEarliestForNodeRef(node))
114 {// earliestReadyTime may have been due to this node, so recompute it
115 earliestReadyTime = HUGE_LATENCY;
116 for (NodeHeap::const_iterator I=candsAsHeap.begin();
117 I != candsAsHeap.end(); ++I)
118 if (candsAsHeap.getNode(I))
119 earliestReadyTime = min(earliestReadyTime,
120 getEarliestForNodeRef(candsAsHeap.getNode(I)));
123 // Now update ready times for successors
124 for (SchedGraphNode::const_iterator E=node->beginOutEdges();
125 E != node->endOutEdges(); ++E)
127 cycles_t& etime = getEarliestForNodeRef((*E)->getSink());
128 etime = max(etime, curTime + (*E)->getMinDelay());
133 //----------------------------------------------------------------------
134 // Priority ordering rules:
135 // (1) Max delay, which is the order of the heap S.candsAsHeap.
136 // (2) Instruction that frees up a register.
137 // (3) Instruction that has the maximum number of dependent instructions.
138 // Note that rules 2 and 3 are only used if issue conflicts prevent
139 // choosing a higher priority instruction by rule 1.
140 //----------------------------------------------------------------------
143 SchedPriorities::chooseByRule1(vector<candIndex>& mcands)
145 return (mcands.size() == 1)? 0 // only one choice exists so take it
146 : -1; // -1 indicates multiple choices
150 SchedPriorities::chooseByRule2(vector<candIndex>& mcands)
152 assert(mcands.size() >= 1 && "Should have at least one candidate here.");
153 for (unsigned i=0, N = mcands.size(); i < N; i++)
154 if (instructionHasLastUse(methodLiveVarInfo,
155 candsAsHeap.getNode(mcands[i])))
161 SchedPriorities::chooseByRule3(vector<candIndex>& mcands)
163 assert(mcands.size() >= 1 && "Should have at least one candidate here.");
164 int maxUses = candsAsHeap.getNode(mcands[0])->getNumOutEdges();
165 int indexWithMaxUses = 0;
166 for (unsigned i=1, N = mcands.size(); i < N; i++)
168 int numUses = candsAsHeap.getNode(mcands[i])->getNumOutEdges();
169 if (numUses > maxUses)
172 indexWithMaxUses = i;
175 return indexWithMaxUses;
178 const SchedGraphNode*
179 SchedPriorities::getNextHighest(const SchedulingManager& S,
183 const SchedGraphNode* nextChoice = NULL;
185 if (mcands.size() == 0)
186 findSetWithMaxDelay(mcands, S);
188 while (nextIdx < 0 && mcands.size() > 0)
190 nextIdx = chooseByRule1(mcands); // rule 1
193 nextIdx = chooseByRule2(mcands); // rule 2
196 nextIdx = chooseByRule3(mcands); // rule 3
199 nextIdx = 0; // default to first choice by delays
201 // We have found the next best candidate. Check if it ready in
202 // the current cycle, and if it is feasible.
203 // If not, remove it from mcands and continue. Refill mcands if
205 nextChoice = candsAsHeap.getNode(mcands[nextIdx]);
206 if (getEarliestForNodeRef(nextChoice) > curTime
207 || ! instrIsFeasible(S, nextChoice->getMachineInstr()->getOpCode()))
209 mcands.erase(mcands.begin() + nextIdx);
211 if (mcands.size() == 0)
212 findSetWithMaxDelay(mcands, S);
218 mcands.erase(mcands.begin() + nextIdx);
227 SchedPriorities::findSetWithMaxDelay(vector<candIndex>& mcands,
228 const SchedulingManager& S)
230 if (mcands.size() == 0 && nextToTry != candsAsHeap.end())
231 { // out of choices at current maximum delay;
232 // put nodes with next highest delay in mcands
233 candIndex next = nextToTry;
234 cycles_t maxDelay = candsAsHeap.getDelay(next);
235 for (; next != candsAsHeap.end()
236 && candsAsHeap.getDelay(next) == maxDelay; ++next)
237 mcands.push_back(next);
241 if (SchedDebugLevel >= Sched_PrintSchedTrace)
243 cout << " Cycle " << this->getTime() << ": "
244 << "Next highest delay = " << maxDelay << " : "
245 << mcands.size() << " Nodes with this delay: ";
246 for (unsigned i=0; i < mcands.size(); i++)
247 cout << candsAsHeap.getNode(mcands[i])->getNodeId() << ", ";
255 SchedPriorities::instructionHasLastUse(MethodLiveVarInfo& methodLiveVarInfo,
256 const SchedGraphNode* graphNode)
258 const MachineInstr* minstr = graphNode->getMachineInstr();
260 hash_map<const MachineInstr*, bool>::const_iterator
261 ui = lastUseMap.find(minstr);
262 if (ui != lastUseMap.end())
265 // else check if instruction is a last use and save it in the hash_map
266 bool hasLastUse = false;
267 const BasicBlock* bb = graphNode->getBB();
268 const LiveVarSet* liveVars =
269 methodLiveVarInfo.getLiveVarSetBeforeMInst(minstr, bb);
271 for (MachineInstr::val_const_op_iterator vo(minstr); ! vo.done(); ++vo)
272 if (liveVars->find(*vo) == liveVars->end())
278 lastUseMap[minstr] = hasLastUse;