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"
26 SchedPriorities::SchedPriorities(const Method* method,
27 const SchedGraph* _graph)
30 methodLiveVarInfo(method), // expensive!
31 nodeDelayVec(_graph->getNumNodes(), INVALID_LATENCY), // make errors obvious
32 earliestForNode(_graph->getNumNodes(), 0),
34 nextToTry(candsAsHeap.begin())
36 methodLiveVarInfo.analyze();
42 SchedPriorities::initialize()
44 initializeReadyHeap(graph);
49 SchedPriorities::computeDelays(const SchedGraph* graph)
51 po_iterator<const SchedGraph*> poIter = po_begin(graph), poEnd =po_end(graph);
52 for ( ; poIter != poEnd; ++poIter)
54 const SchedGraphNode* node = *poIter;
56 if (node->beginOutEdges() == node->endOutEdges())
57 nodeDelay = node->getLatency();
60 // Iterate over the out-edges of the node to compute delay
62 for (SchedGraphNode::const_iterator E=node->beginOutEdges();
63 E != node->endOutEdges(); ++E)
65 cycles_t sinkDelay = getNodeDelayRef((*E)->getSink());
66 nodeDelay = std::max(nodeDelay, sinkDelay + (*E)->getMinDelay());
69 getNodeDelayRef(node) = nodeDelay;
75 SchedPriorities::initializeReadyHeap(const SchedGraph* graph)
77 const SchedGraphNode* graphRoot = graph->getRoot();
78 assert(graphRoot->getMachineInstr() == NULL && "Expect dummy root");
80 // Insert immediate successors of dummy root, which are the actual roots
81 sg_succ_const_iterator SEnd = succ_end(graphRoot);
82 for (sg_succ_const_iterator S = succ_begin(graphRoot); S != SEnd; ++S)
83 this->insertReady(*S);
85 #undef TEST_HEAP_CONVERSION
86 #ifdef TEST_HEAP_CONVERSION
87 cerr << "Before heap conversion:\n";
88 copy(candsAsHeap.begin(), candsAsHeap.end(),
89 ostream_iterator<NodeDelayPair*>(cerr,"\n"));
92 candsAsHeap.makeHeap();
94 #ifdef TEST_HEAP_CONVERSION
95 cerr << "After heap conversion:\n";
96 copy(candsAsHeap.begin(), candsAsHeap.end(),
97 ostream_iterator<NodeDelayPair*>(cerr,"\n"));
102 SchedPriorities::insertReady(const SchedGraphNode* node)
104 candsAsHeap.insert(node, nodeDelayVec[node->getNodeId()]);
105 candsAsSet.insert(node);
106 mcands.clear(); // ensure reset choices is called before any more choices
107 earliestReadyTime = std::min(earliestReadyTime,
108 earliestForNode[node->getNodeId()]);
110 if (SchedDebugLevel >= Sched_PrintSchedTrace)
112 cerr << " Cycle " << (long)getTime() << ": "
113 << " Node " << node->getNodeId() << " is ready; "
114 << " Delay = " << (long)getNodeDelayRef(node) << "; Instruction: \n";
115 cerr << " " << *node->getMachineInstr() << "\n";
120 SchedPriorities::issuedReadyNodeAt(cycles_t curTime,
121 const SchedGraphNode* node)
123 candsAsHeap.removeNode(node);
124 candsAsSet.erase(node);
125 mcands.clear(); // ensure reset choices is called before any more choices
127 if (earliestReadyTime == getEarliestForNodeRef(node))
128 {// earliestReadyTime may have been due to this node, so recompute it
129 earliestReadyTime = HUGE_LATENCY;
130 for (NodeHeap::const_iterator I=candsAsHeap.begin();
131 I != candsAsHeap.end(); ++I)
132 if (candsAsHeap.getNode(I))
133 earliestReadyTime = std::min(earliestReadyTime,
134 getEarliestForNodeRef(candsAsHeap.getNode(I)));
137 // Now update ready times for successors
138 for (SchedGraphNode::const_iterator E=node->beginOutEdges();
139 E != node->endOutEdges(); ++E)
141 cycles_t& etime = getEarliestForNodeRef((*E)->getSink());
142 etime = std::max(etime, curTime + (*E)->getMinDelay());
147 //----------------------------------------------------------------------
148 // Priority ordering rules:
149 // (1) Max delay, which is the order of the heap S.candsAsHeap.
150 // (2) Instruction that frees up a register.
151 // (3) Instruction that has the maximum number of dependent instructions.
152 // Note that rules 2 and 3 are only used if issue conflicts prevent
153 // choosing a higher priority instruction by rule 1.
154 //----------------------------------------------------------------------
157 SchedPriorities::chooseByRule1(std::vector<candIndex>& mcands)
159 return (mcands.size() == 1)? 0 // only one choice exists so take it
160 : -1; // -1 indicates multiple choices
164 SchedPriorities::chooseByRule2(std::vector<candIndex>& mcands)
166 assert(mcands.size() >= 1 && "Should have at least one candidate here.");
167 for (unsigned i=0, N = mcands.size(); i < N; i++)
168 if (instructionHasLastUse(methodLiveVarInfo,
169 candsAsHeap.getNode(mcands[i])))
175 SchedPriorities::chooseByRule3(std::vector<candIndex>& mcands)
177 assert(mcands.size() >= 1 && "Should have at least one candidate here.");
178 int maxUses = candsAsHeap.getNode(mcands[0])->getNumOutEdges();
179 int indexWithMaxUses = 0;
180 for (unsigned i=1, N = mcands.size(); i < N; i++)
182 int numUses = candsAsHeap.getNode(mcands[i])->getNumOutEdges();
183 if (numUses > maxUses)
186 indexWithMaxUses = i;
189 return indexWithMaxUses;
192 const SchedGraphNode*
193 SchedPriorities::getNextHighest(const SchedulingManager& S,
197 const SchedGraphNode* nextChoice = NULL;
199 if (mcands.size() == 0)
200 findSetWithMaxDelay(mcands, S);
202 while (nextIdx < 0 && mcands.size() > 0)
204 nextIdx = chooseByRule1(mcands); // rule 1
207 nextIdx = chooseByRule2(mcands); // rule 2
210 nextIdx = chooseByRule3(mcands); // rule 3
213 nextIdx = 0; // default to first choice by delays
215 // We have found the next best candidate. Check if it ready in
216 // the current cycle, and if it is feasible.
217 // If not, remove it from mcands and continue. Refill mcands if
219 nextChoice = candsAsHeap.getNode(mcands[nextIdx]);
220 if (getEarliestForNodeRef(nextChoice) > curTime
221 || ! instrIsFeasible(S, nextChoice->getMachineInstr()->getOpCode()))
223 mcands.erase(mcands.begin() + nextIdx);
225 if (mcands.size() == 0)
226 findSetWithMaxDelay(mcands, S);
232 mcands.erase(mcands.begin() + nextIdx);
241 SchedPriorities::findSetWithMaxDelay(std::vector<candIndex>& mcands,
242 const SchedulingManager& S)
244 if (mcands.size() == 0 && nextToTry != candsAsHeap.end())
245 { // out of choices at current maximum delay;
246 // put nodes with next highest delay in mcands
247 candIndex next = nextToTry;
248 cycles_t maxDelay = candsAsHeap.getDelay(next);
249 for (; next != candsAsHeap.end()
250 && candsAsHeap.getDelay(next) == maxDelay; ++next)
251 mcands.push_back(next);
255 if (SchedDebugLevel >= Sched_PrintSchedTrace)
257 cerr << " Cycle " << (long)getTime() << ": "
258 << "Next highest delay = " << (long)maxDelay << " : "
259 << mcands.size() << " Nodes with this delay: ";
260 for (unsigned i=0; i < mcands.size(); i++)
261 cerr << candsAsHeap.getNode(mcands[i])->getNodeId() << ", ";
269 SchedPriorities::instructionHasLastUse(MethodLiveVarInfo& methodLiveVarInfo,
270 const SchedGraphNode* graphNode)
272 const MachineInstr* minstr = graphNode->getMachineInstr();
274 std::hash_map<const MachineInstr*, bool>::const_iterator
275 ui = lastUseMap.find(minstr);
276 if (ui != lastUseMap.end())
279 // else check if instruction is a last use and save it in the hash_map
280 bool hasLastUse = false;
281 const BasicBlock* bb = graphNode->getBB();
282 const LiveVarSet* liveVars =
283 methodLiveVarInfo.getLiveVarSetBeforeMInst(minstr, bb);
285 for (MachineInstr::val_const_op_iterator vo(minstr); ! vo.done(); ++vo)
286 if (liveVars->find(*vo) == liveVars->end())
292 lastUseMap[minstr] = hasLastUse;