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 //************************** System Include Files **************************/
26 #include <sys/types.h>
28 //*************************** User Include Files ***************************/
30 #include "llvm/Method.h"
31 #include "llvm/CodeGen/MachineInstr.h"
32 #include "llvm/CodeGen/InstrScheduling.h"
33 #include "llvm/CodeGen/SchedPriorities.h"
35 //************************* Forward Declarations ***************************/
39 SchedPriorities::SchedPriorities(const Method* method,
40 const SchedGraph* _graph)
43 methodLiveVarInfo(method), // expensive!
45 nodeDelayVec(_graph->getNumNodes(),INVALID_LATENCY), //make errors obvious
46 earliestForNode(_graph->getNumNodes(), 0),
51 nextToTry(candsAsHeap.begin())
53 methodLiveVarInfo.analyze();
59 SchedPriorities::initialize()
61 initializeReadyHeap(graph);
66 SchedPriorities::computeDelays(const SchedGraph* graph)
68 sg_po_const_iterator poIter = sg_po_const_iterator::begin(graph->getRoot());
69 sg_po_const_iterator poEnd = sg_po_const_iterator::end( graph->getRoot());
70 for ( ; poIter != poEnd; ++poIter)
72 const SchedGraphNode* node = *poIter;
74 if (node->beginOutEdges() == node->endOutEdges())
75 nodeDelay = node->getLatency();
78 // Iterate over the out-edges of the node to compute delay
80 for (SchedGraphNode::const_iterator E=node->beginOutEdges();
81 E != node->endOutEdges(); ++E)
83 cycles_t sinkDelay = getNodeDelayRef((*E)->getSink());
84 nodeDelay = max(nodeDelay, sinkDelay + (*E)->getMinDelay());
87 getNodeDelayRef(node) = nodeDelay;
93 SchedPriorities::initializeReadyHeap(const SchedGraph* graph)
95 const SchedGraphNode* graphRoot = graph->getRoot();
96 assert(graphRoot->getMachineInstr() == NULL && "Expect dummy root");
98 // Insert immediate successors of dummy root, which are the actual roots
99 sg_succ_const_iterator SEnd = succ_end(graphRoot);
100 for (sg_succ_const_iterator S = succ_begin(graphRoot); S != SEnd; ++S)
101 this->insertReady(*S);
103 #undef TEST_HEAP_CONVERSION
104 #ifdef TEST_HEAP_CONVERSION
105 cout << "Before heap conversion:" << endl;
106 copy(candsAsHeap.begin(), candsAsHeap.end(),
107 ostream_iterator<NodeDelayPair*>(cout,"\n"));
110 candsAsHeap.makeHeap();
112 #ifdef TEST_HEAP_CONVERSION
113 cout << "After heap conversion:" << endl;
114 copy(candsAsHeap.begin(), candsAsHeap.end(),
115 ostream_iterator<NodeDelayPair*>(cout,"\n"));
121 SchedPriorities::issuedReadyNodeAt(cycles_t curTime,
122 const SchedGraphNode* node)
124 candsAsHeap.removeNode(node);
125 candsAsSet.erase(node);
126 mcands.clear(); // ensure reset choices is called before any more choices
128 if (earliestReadyTime == getEarliestForNodeRef(node))
129 {// earliestReadyTime may have been due to this node, so recompute it
130 earliestReadyTime = HUGE_LATENCY;
131 for (NodeHeap::const_iterator I=candsAsHeap.begin();
132 I != candsAsHeap.end(); ++I)
133 if (candsAsHeap.getNode(I))
134 earliestReadyTime = min(earliestReadyTime,
135 getEarliestForNodeRef(candsAsHeap.getNode(I)));
138 // Now update ready times for successors
139 for (SchedGraphNode::const_iterator E=node->beginOutEdges();
140 E != node->endOutEdges(); ++E)
142 cycles_t& etime = getEarliestForNodeRef((*E)->getSink());
143 etime = max(etime, curTime + (*E)->getMinDelay());
148 //----------------------------------------------------------------------
149 // Priority ordering rules:
150 // (1) Max delay, which is the order of the heap S.candsAsHeap.
151 // (2) Instruction that frees up a register.
152 // (3) Instruction that has the maximum number of dependent instructions.
153 // Note that rules 2 and 3 are only used if issue conflicts prevent
154 // choosing a higher priority instruction by rule 1.
155 //----------------------------------------------------------------------
158 SchedPriorities::chooseByRule1(vector<candIndex>& mcands)
160 return (mcands.size() == 1)? 0 // only one choice exists so take it
161 : -1; // -1 indicates multiple choices
165 SchedPriorities::chooseByRule2(vector<candIndex>& mcands)
167 assert(mcands.size() >= 1 && "Should have at least one candidate here.");
168 for (unsigned i=0, N = mcands.size(); i < N; i++)
169 if (instructionHasLastUse(methodLiveVarInfo,
170 candsAsHeap.getNode(mcands[i])))
176 SchedPriorities::chooseByRule3(vector<candIndex>& mcands)
178 assert(mcands.size() >= 1 && "Should have at least one candidate here.");
179 int maxUses = candsAsHeap.getNode(mcands[0])->getNumOutEdges();
180 int indexWithMaxUses = 0;
181 for (unsigned i=1, N = mcands.size(); i < N; i++)
183 int numUses = candsAsHeap.getNode(mcands[i])->getNumOutEdges();
184 if (numUses > maxUses)
187 indexWithMaxUses = i;
190 return indexWithMaxUses;
193 const SchedGraphNode*
194 SchedPriorities::getNextHighest(const SchedulingManager& S,
198 const SchedGraphNode* nextChoice = NULL;
200 if (mcands.size() == 0)
201 findSetWithMaxDelay(mcands, S);
203 while (nextIdx < 0 && mcands.size() > 0)
205 nextIdx = chooseByRule1(mcands); // rule 1
208 nextIdx = chooseByRule2(mcands); // rule 2
211 nextIdx = chooseByRule3(mcands); // rule 3
214 nextIdx = 0; // default to first choice by delays
216 // We have found the next best candidate. Check if it ready in
217 // the current cycle, and if it is feasible.
218 // If not, remove it from mcands and continue. Refill mcands if
220 nextChoice = candsAsHeap.getNode(mcands[nextIdx]);
221 if (getEarliestForNodeRef(nextChoice) > curTime
222 || ! instrIsFeasible(S, nextChoice->getOpCode()))
224 mcands.erase(mcands.begin() + nextIdx);
226 if (mcands.size() == 0)
227 findSetWithMaxDelay(mcands, S);
233 mcands.erase(mcands.begin() + nextIdx);
242 SchedPriorities::findSetWithMaxDelay(vector<candIndex>& mcands,
243 const SchedulingManager& S)
245 if (mcands.size() == 0 && nextToTry != candsAsHeap.end())
246 { // out of choices at current maximum delay;
247 // put nodes with next highest delay in mcands
248 candIndex next = nextToTry;
249 cycles_t maxDelay = candsAsHeap.getDelay(next);
250 for (; next != candsAsHeap.end()
251 && candsAsHeap.getDelay(next) == maxDelay; ++next)
252 mcands.push_back(next);
256 if (SchedDebugLevel >= Sched_PrintSchedTrace)
259 cout << "Cycle " << this->getTime() << ": "
260 << "Next highest delay = " << maxDelay << " : "
261 << mcands.size() << " Nodes with this delay: ";
262 for (unsigned i=0; i < mcands.size(); i++)
263 cout << candsAsHeap.getNode(mcands[i])->getNodeId() << ", ";
271 SchedPriorities::instructionHasLastUse(MethodLiveVarInfo& methodLiveVarInfo,
272 const SchedGraphNode* graphNode)
274 const MachineInstr* minstr = graphNode->getMachineInstr();
276 hash_map<const MachineInstr*, bool>::const_iterator
277 ui = lastUseMap.find(minstr);
278 if (ui != lastUseMap.end())
281 // else check if instruction is a last use and save it in the hash_map
282 bool hasLastUse = false;
283 const BasicBlock* bb = graphNode->getInstr()->getParent();
284 const LiveVarSet* liveVars =
285 methodLiveVarInfo.getLiveVarSetBeforeMInst(minstr, bb);
287 for (MachineInstr::val_op_const_iterator vo(minstr); ! vo.done(); ++vo)
288 if (liveVars->find(*vo) == liveVars->end())
294 lastUseMap[minstr] = hasLastUse;