1 //===-- SchedPriorities.h - Encapsulate scheduling heuristics -------------===//
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 #include "SchedPriorities.h"
14 #include "llvm/Analysis/LiveVar/FunctionLiveVarInfo.h"
15 #include "llvm/CodeGen/MachineBasicBlock.h"
16 #include "llvm/Support/CFG.h"
17 #include "Support/PostOrderIterator.h"
20 SchedPriorities::SchedPriorities(const Function *, const SchedGraph *G,
21 FunctionLiveVarInfo &LVI)
22 : curTime(0), graph(G), methodLiveVarInfo(LVI),
23 nodeDelayVec(G->getNumNodes(), INVALID_LATENCY), // make errors obvious
24 earliestReadyTimeForNode(G->getNumNodes(), 0),
26 nextToTry(candsAsHeap.begin())
33 SchedPriorities::initialize()
35 initializeReadyHeap(graph);
40 SchedPriorities::computeDelays(const SchedGraph* graph)
42 po_iterator<const SchedGraph*> poIter = po_begin(graph), poEnd =po_end(graph);
43 for ( ; poIter != poEnd; ++poIter)
45 const SchedGraphNode* node = *poIter;
47 if (node->beginOutEdges() == node->endOutEdges())
48 nodeDelay = node->getLatency();
51 // Iterate over the out-edges of the node to compute delay
53 for (SchedGraphNode::const_iterator E=node->beginOutEdges();
54 E != node->endOutEdges(); ++E)
56 cycles_t sinkDelay = getNodeDelay((*E)->getSink());
57 nodeDelay = std::max(nodeDelay, sinkDelay + (*E)->getMinDelay());
60 getNodeDelayRef(node) = nodeDelay;
66 SchedPriorities::initializeReadyHeap(const SchedGraph* graph)
68 const SchedGraphNode* graphRoot = graph->getRoot();
69 assert(graphRoot->getMachineInstr() == NULL && "Expect dummy root");
71 // Insert immediate successors of dummy root, which are the actual roots
72 sg_succ_const_iterator SEnd = succ_end(graphRoot);
73 for (sg_succ_const_iterator S = succ_begin(graphRoot); S != SEnd; ++S)
74 this->insertReady(*S);
76 #undef TEST_HEAP_CONVERSION
77 #ifdef TEST_HEAP_CONVERSION
78 cerr << "Before heap conversion:\n";
79 copy(candsAsHeap.begin(), candsAsHeap.end(),
80 ostream_iterator<NodeDelayPair*>(cerr,"\n"));
83 candsAsHeap.makeHeap();
85 nextToTry = candsAsHeap.begin();
87 #ifdef TEST_HEAP_CONVERSION
88 cerr << "After heap conversion:\n";
89 copy(candsAsHeap.begin(), candsAsHeap.end(),
90 ostream_iterator<NodeDelayPair*>(cerr,"\n"));
95 SchedPriorities::insertReady(const SchedGraphNode* node)
97 candsAsHeap.insert(node, nodeDelayVec[node->getNodeId()]);
98 candsAsSet.insert(node);
99 mcands.clear(); // ensure reset choices is called before any more choices
100 earliestReadyTime = std::min(earliestReadyTime,
101 getEarliestReadyTimeForNode(node));
103 if (SchedDebugLevel >= Sched_PrintSchedTrace)
105 cerr << " Node " << node->getNodeId() << " will be ready in Cycle "
106 << getEarliestReadyTimeForNode(node) << "; "
107 << " Delay = " <<(long)getNodeDelay(node) << "; Instruction: \n";
108 cerr << " " << *node->getMachineInstr() << "\n";
113 SchedPriorities::issuedReadyNodeAt(cycles_t curTime,
114 const SchedGraphNode* node)
116 candsAsHeap.removeNode(node);
117 candsAsSet.erase(node);
118 mcands.clear(); // ensure reset choices is called before any more choices
120 if (earliestReadyTime == getEarliestReadyTimeForNode(node))
121 {// earliestReadyTime may have been due to this node, so recompute it
122 earliestReadyTime = HUGE_LATENCY;
123 for (NodeHeap::const_iterator I=candsAsHeap.begin();
124 I != candsAsHeap.end(); ++I)
125 if (candsAsHeap.getNode(I))
126 earliestReadyTime = std::min(earliestReadyTime,
127 getEarliestReadyTimeForNode(candsAsHeap.getNode(I)));
130 // Now update ready times for successors
131 for (SchedGraphNode::const_iterator E=node->beginOutEdges();
132 E != node->endOutEdges(); ++E)
134 cycles_t& etime = getEarliestReadyTimeForNodeRef((*E)->getSink());
135 etime = std::max(etime, curTime + (*E)->getMinDelay());
140 //----------------------------------------------------------------------
141 // Priority ordering rules:
142 // (1) Max delay, which is the order of the heap S.candsAsHeap.
143 // (2) Instruction that frees up a register.
144 // (3) Instruction that has the maximum number of dependent instructions.
145 // Note that rules 2 and 3 are only used if issue conflicts prevent
146 // choosing a higher priority instruction by rule 1.
147 //----------------------------------------------------------------------
150 SchedPriorities::chooseByRule1(std::vector<candIndex>& mcands)
152 return (mcands.size() == 1)? 0 // only one choice exists so take it
153 : -1; // -1 indicates multiple choices
157 SchedPriorities::chooseByRule2(std::vector<candIndex>& mcands)
159 assert(mcands.size() >= 1 && "Should have at least one candidate here.");
160 for (unsigned i=0, N = mcands.size(); i < N; i++)
161 if (instructionHasLastUse(methodLiveVarInfo,
162 candsAsHeap.getNode(mcands[i])))
168 SchedPriorities::chooseByRule3(std::vector<candIndex>& mcands)
170 assert(mcands.size() >= 1 && "Should have at least one candidate here.");
171 int maxUses = candsAsHeap.getNode(mcands[0])->getNumOutEdges();
172 int indexWithMaxUses = 0;
173 for (unsigned i=1, N = mcands.size(); i < N; i++)
175 int numUses = candsAsHeap.getNode(mcands[i])->getNumOutEdges();
176 if (numUses > maxUses)
179 indexWithMaxUses = i;
182 return indexWithMaxUses;
185 const SchedGraphNode*
186 SchedPriorities::getNextHighest(const SchedulingManager& S,
190 const SchedGraphNode* nextChoice = NULL;
192 if (mcands.size() == 0)
193 findSetWithMaxDelay(mcands, S);
195 while (nextIdx < 0 && mcands.size() > 0)
197 nextIdx = chooseByRule1(mcands); // rule 1
200 nextIdx = chooseByRule2(mcands); // rule 2
203 nextIdx = chooseByRule3(mcands); // rule 3
206 nextIdx = 0; // default to first choice by delays
208 // We have found the next best candidate. Check if it ready in
209 // the current cycle, and if it is feasible.
210 // If not, remove it from mcands and continue. Refill mcands if
212 nextChoice = candsAsHeap.getNode(mcands[nextIdx]);
213 if (getEarliestReadyTimeForNode(nextChoice) > curTime
214 || ! instrIsFeasible(S, nextChoice->getMachineInstr()->getOpCode()))
216 mcands.erase(mcands.begin() + nextIdx);
218 if (mcands.size() == 0)
219 findSetWithMaxDelay(mcands, S);
225 mcands.erase(mcands.begin() + nextIdx);
234 SchedPriorities::findSetWithMaxDelay(std::vector<candIndex>& mcands,
235 const SchedulingManager& S)
237 if (mcands.size() == 0 && nextToTry != candsAsHeap.end())
238 { // out of choices at current maximum delay;
239 // put nodes with next highest delay in mcands
240 candIndex next = nextToTry;
241 cycles_t maxDelay = candsAsHeap.getDelay(next);
242 for (; next != candsAsHeap.end()
243 && candsAsHeap.getDelay(next) == maxDelay; ++next)
244 mcands.push_back(next);
248 if (SchedDebugLevel >= Sched_PrintSchedTrace)
250 cerr << " Cycle " << (long)getTime() << ": "
251 << "Next highest delay = " << (long)maxDelay << " : "
252 << mcands.size() << " Nodes with this delay: ";
253 for (unsigned i=0; i < mcands.size(); i++)
254 cerr << candsAsHeap.getNode(mcands[i])->getNodeId() << ", ";
262 SchedPriorities::instructionHasLastUse(FunctionLiveVarInfo &LVI,
263 const SchedGraphNode* graphNode) {
264 const MachineInstr *MI = graphNode->getMachineInstr();
266 hash_map<const MachineInstr*, bool>::const_iterator
267 ui = lastUseMap.find(MI);
268 if (ui != lastUseMap.end())
271 // else check if instruction is a last use and save it in the hash_map
272 bool hasLastUse = false;
273 const BasicBlock* bb = graphNode->getMachineBasicBlock().getBasicBlock();
274 const ValueSet &LVs = LVI.getLiveVarSetBeforeMInst(MI, bb);
276 for (MachineInstr::const_val_op_iterator OI = MI->begin(), OE = MI->end();
278 if (!LVs.count(*OI)) {
283 return lastUseMap[MI] = hasLastUse;