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 "llvm/Analysis/LiveVar/MethodLiveVarInfo.h"
23 #include "llvm/Support/CFG.h"
24 #include "Support/PostOrderIterator.h"
28 SchedPriorities::SchedPriorities(const Method *method, const SchedGraph *G,
29 MethodLiveVarInfo &LVI)
30 : curTime(0), graph(G), methodLiveVarInfo(LVI),
31 nodeDelayVec(G->getNumNodes(), INVALID_LATENCY), // make errors obvious
32 earliestForNode(G->getNumNodes(), 0),
34 nextToTry(candsAsHeap.begin()) {
40 SchedPriorities::initialize()
42 initializeReadyHeap(graph);
47 SchedPriorities::computeDelays(const SchedGraph* graph)
49 po_iterator<const SchedGraph*> poIter = po_begin(graph), poEnd =po_end(graph);
50 for ( ; poIter != poEnd; ++poIter)
52 const SchedGraphNode* node = *poIter;
54 if (node->beginOutEdges() == node->endOutEdges())
55 nodeDelay = node->getLatency();
58 // Iterate over the out-edges of the node to compute delay
60 for (SchedGraphNode::const_iterator E=node->beginOutEdges();
61 E != node->endOutEdges(); ++E)
63 cycles_t sinkDelay = getNodeDelayRef((*E)->getSink());
64 nodeDelay = std::max(nodeDelay, sinkDelay + (*E)->getMinDelay());
67 getNodeDelayRef(node) = nodeDelay;
73 SchedPriorities::initializeReadyHeap(const SchedGraph* graph)
75 const SchedGraphNode* graphRoot = graph->getRoot();
76 assert(graphRoot->getMachineInstr() == NULL && "Expect dummy root");
78 // Insert immediate successors of dummy root, which are the actual roots
79 sg_succ_const_iterator SEnd = succ_end(graphRoot);
80 for (sg_succ_const_iterator S = succ_begin(graphRoot); S != SEnd; ++S)
81 this->insertReady(*S);
83 #undef TEST_HEAP_CONVERSION
84 #ifdef TEST_HEAP_CONVERSION
85 cerr << "Before heap conversion:\n";
86 copy(candsAsHeap.begin(), candsAsHeap.end(),
87 ostream_iterator<NodeDelayPair*>(cerr,"\n"));
90 candsAsHeap.makeHeap();
92 #ifdef TEST_HEAP_CONVERSION
93 cerr << "After heap conversion:\n";
94 copy(candsAsHeap.begin(), candsAsHeap.end(),
95 ostream_iterator<NodeDelayPair*>(cerr,"\n"));
100 SchedPriorities::insertReady(const SchedGraphNode* node)
102 candsAsHeap.insert(node, nodeDelayVec[node->getNodeId()]);
103 candsAsSet.insert(node);
104 mcands.clear(); // ensure reset choices is called before any more choices
105 earliestReadyTime = std::min(earliestReadyTime,
106 earliestForNode[node->getNodeId()]);
108 if (SchedDebugLevel >= Sched_PrintSchedTrace)
110 cerr << " Cycle " << (long)getTime() << ": "
111 << " Node " << node->getNodeId() << " is ready; "
112 << " Delay = " << (long)getNodeDelayRef(node) << "; Instruction: \n";
113 cerr << " " << *node->getMachineInstr() << "\n";
118 SchedPriorities::issuedReadyNodeAt(cycles_t curTime,
119 const SchedGraphNode* node)
121 candsAsHeap.removeNode(node);
122 candsAsSet.erase(node);
123 mcands.clear(); // ensure reset choices is called before any more choices
125 if (earliestReadyTime == getEarliestForNodeRef(node))
126 {// earliestReadyTime may have been due to this node, so recompute it
127 earliestReadyTime = HUGE_LATENCY;
128 for (NodeHeap::const_iterator I=candsAsHeap.begin();
129 I != candsAsHeap.end(); ++I)
130 if (candsAsHeap.getNode(I))
131 earliestReadyTime = std::min(earliestReadyTime,
132 getEarliestForNodeRef(candsAsHeap.getNode(I)));
135 // Now update ready times for successors
136 for (SchedGraphNode::const_iterator E=node->beginOutEdges();
137 E != node->endOutEdges(); ++E)
139 cycles_t& etime = getEarliestForNodeRef((*E)->getSink());
140 etime = std::max(etime, curTime + (*E)->getMinDelay());
145 //----------------------------------------------------------------------
146 // Priority ordering rules:
147 // (1) Max delay, which is the order of the heap S.candsAsHeap.
148 // (2) Instruction that frees up a register.
149 // (3) Instruction that has the maximum number of dependent instructions.
150 // Note that rules 2 and 3 are only used if issue conflicts prevent
151 // choosing a higher priority instruction by rule 1.
152 //----------------------------------------------------------------------
155 SchedPriorities::chooseByRule1(std::vector<candIndex>& mcands)
157 return (mcands.size() == 1)? 0 // only one choice exists so take it
158 : -1; // -1 indicates multiple choices
162 SchedPriorities::chooseByRule2(std::vector<candIndex>& mcands)
164 assert(mcands.size() >= 1 && "Should have at least one candidate here.");
165 for (unsigned i=0, N = mcands.size(); i < N; i++)
166 if (instructionHasLastUse(methodLiveVarInfo,
167 candsAsHeap.getNode(mcands[i])))
173 SchedPriorities::chooseByRule3(std::vector<candIndex>& mcands)
175 assert(mcands.size() >= 1 && "Should have at least one candidate here.");
176 int maxUses = candsAsHeap.getNode(mcands[0])->getNumOutEdges();
177 int indexWithMaxUses = 0;
178 for (unsigned i=1, N = mcands.size(); i < N; i++)
180 int numUses = candsAsHeap.getNode(mcands[i])->getNumOutEdges();
181 if (numUses > maxUses)
184 indexWithMaxUses = i;
187 return indexWithMaxUses;
190 const SchedGraphNode*
191 SchedPriorities::getNextHighest(const SchedulingManager& S,
195 const SchedGraphNode* nextChoice = NULL;
197 if (mcands.size() == 0)
198 findSetWithMaxDelay(mcands, S);
200 while (nextIdx < 0 && mcands.size() > 0)
202 nextIdx = chooseByRule1(mcands); // rule 1
205 nextIdx = chooseByRule2(mcands); // rule 2
208 nextIdx = chooseByRule3(mcands); // rule 3
211 nextIdx = 0; // default to first choice by delays
213 // We have found the next best candidate. Check if it ready in
214 // the current cycle, and if it is feasible.
215 // If not, remove it from mcands and continue. Refill mcands if
217 nextChoice = candsAsHeap.getNode(mcands[nextIdx]);
218 if (getEarliestForNodeRef(nextChoice) > curTime
219 || ! instrIsFeasible(S, nextChoice->getMachineInstr()->getOpCode()))
221 mcands.erase(mcands.begin() + nextIdx);
223 if (mcands.size() == 0)
224 findSetWithMaxDelay(mcands, S);
230 mcands.erase(mcands.begin() + nextIdx);
239 SchedPriorities::findSetWithMaxDelay(std::vector<candIndex>& mcands,
240 const SchedulingManager& S)
242 if (mcands.size() == 0 && nextToTry != candsAsHeap.end())
243 { // out of choices at current maximum delay;
244 // put nodes with next highest delay in mcands
245 candIndex next = nextToTry;
246 cycles_t maxDelay = candsAsHeap.getDelay(next);
247 for (; next != candsAsHeap.end()
248 && candsAsHeap.getDelay(next) == maxDelay; ++next)
249 mcands.push_back(next);
253 if (SchedDebugLevel >= Sched_PrintSchedTrace)
255 cerr << " Cycle " << (long)getTime() << ": "
256 << "Next highest delay = " << (long)maxDelay << " : "
257 << mcands.size() << " Nodes with this delay: ";
258 for (unsigned i=0; i < mcands.size(); i++)
259 cerr << candsAsHeap.getNode(mcands[i])->getNodeId() << ", ";
267 SchedPriorities::instructionHasLastUse(MethodLiveVarInfo& methodLiveVarInfo,
268 const SchedGraphNode* graphNode) {
269 const MachineInstr *MI = graphNode->getMachineInstr();
271 std::hash_map<const MachineInstr*, bool>::const_iterator
272 ui = lastUseMap.find(MI);
273 if (ui != lastUseMap.end())
276 // else check if instruction is a last use and save it in the hash_map
277 bool hasLastUse = false;
278 const BasicBlock* bb = graphNode->getBB();
279 const ValueSet &LVs = methodLiveVarInfo.getLiveVarSetBeforeMInst(MI, bb);
281 for (MachineInstr::const_val_op_iterator OI = MI->begin(), OE = MI->end();
283 if (!LVs.count(*OI)) {
288 return lastUseMap[MI] = hasLastUse;