1 //===-- SchedPriorities.h - Encapsulate scheduling heuristics -------------===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
11 // Priority ordering rules:
12 // (1) Max delay, which is the order of the heap S.candsAsHeap.
13 // (2) Instruction that frees up a register.
14 // (3) Instruction that has the maximum number of dependent instructions.
15 // Note that rules 2 and 3 are only used if issue conflicts prevent
16 // choosing a higher priority instruction by rule 1.
18 //===----------------------------------------------------------------------===//
20 #include "SchedPriorities.h"
21 #include "llvm/CodeGen/FunctionLiveVarInfo.h"
22 #include "llvm/CodeGen/MachineBasicBlock.h"
23 #include "llvm/Support/CFG.h"
24 #include "Support/PostOrderIterator.h"
28 std::ostream &operator<<(std::ostream &os, const NodeDelayPair* nd) {
29 return os << "Delay for node " << nd->node->getNodeId()
30 << " = " << (long)nd->delay << "\n";
34 SchedPriorities::SchedPriorities(const Function *, const SchedGraph *G,
35 FunctionLiveVarInfo &LVI)
36 : curTime(0), graph(G), methodLiveVarInfo(LVI),
37 nodeDelayVec(G->getNumNodes(), INVALID_LATENCY), // make errors obvious
38 earliestReadyTimeForNode(G->getNumNodes(), 0),
40 nextToTry(candsAsHeap.begin())
47 SchedPriorities::initialize() {
48 initializeReadyHeap(graph);
53 SchedPriorities::computeDelays(const SchedGraph* graph) {
54 po_iterator<const SchedGraph*> poIter = po_begin(graph), poEnd =po_end(graph);
55 for ( ; poIter != poEnd; ++poIter) {
56 const SchedGraphNode* node = *poIter;
58 if (node->beginOutEdges() == node->endOutEdges())
59 nodeDelay = node->getLatency();
61 // Iterate over the out-edges of the node to compute delay
63 for (SchedGraphNode::const_iterator E=node->beginOutEdges();
64 E != node->endOutEdges(); ++E) {
65 cycles_t sinkDelay = getNodeDelay((SchedGraphNode*)(*E)->getSink());
66 nodeDelay = std::max(nodeDelay, sinkDelay + (*E)->getMinDelay());
69 getNodeDelayRef(node) = nodeDelay;
75 SchedPriorities::initializeReadyHeap(const SchedGraph* graph) {
76 const SchedGraphNode* graphRoot = (const SchedGraphNode*)graph->getRoot();
77 assert(graphRoot->getMachineInstr() == NULL && "Expect dummy root");
79 // Insert immediate successors of dummy root, which are the actual roots
80 sg_succ_const_iterator SEnd = succ_end(graphRoot);
81 for (sg_succ_const_iterator S = succ_begin(graphRoot); S != SEnd; ++S)
82 this->insertReady(*S);
84 #undef TEST_HEAP_CONVERSION
85 #ifdef TEST_HEAP_CONVERSION
86 std::cerr << "Before heap conversion:\n";
87 copy(candsAsHeap.begin(), candsAsHeap.end(),
88 ostream_iterator<NodeDelayPair*>(std::cerr,"\n"));
91 candsAsHeap.makeHeap();
93 nextToTry = candsAsHeap.begin();
95 #ifdef TEST_HEAP_CONVERSION
96 std::cerr << "After heap conversion:\n";
97 copy(candsAsHeap.begin(), candsAsHeap.end(),
98 ostream_iterator<NodeDelayPair*>(std::cerr,"\n"));
103 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 getEarliestReadyTimeForNode(node));
110 if (SchedDebugLevel >= Sched_PrintSchedTrace) {
111 std::cerr << " Node " << node->getNodeId() << " will be ready in Cycle "
112 << getEarliestReadyTimeForNode(node) << "; "
113 << " Delay = " <<(long)getNodeDelay(node) << "; Instruction: \n"
114 << " " << *node->getMachineInstr() << "\n";
119 SchedPriorities::issuedReadyNodeAt(cycles_t curTime,
120 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 == getEarliestReadyTimeForNode(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)) {
132 std::min(earliestReadyTime,
133 getEarliestReadyTimeForNode(candsAsHeap.getNode(I)));
137 // Now update ready times for successors
138 for (SchedGraphNode::const_iterator E=node->beginOutEdges();
139 E != node->endOutEdges(); ++E) {
141 getEarliestReadyTimeForNodeRef((SchedGraphNode*)(*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) {
158 return (mcands.size() == 1)? 0 // only one choice exists so take it
159 : -1; // -1 indicates multiple choices
163 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) {
174 assert(mcands.size() >= 1 && "Should have at least one candidate here.");
175 int maxUses = candsAsHeap.getNode(mcands[0])->getNumOutEdges();
176 int indexWithMaxUses = 0;
177 for (unsigned i=1, N = mcands.size(); i < N; i++) {
178 int numUses = candsAsHeap.getNode(mcands[i])->getNumOutEdges();
179 if (numUses > maxUses) {
181 indexWithMaxUses = i;
184 return indexWithMaxUses;
187 const SchedGraphNode*
188 SchedPriorities::getNextHighest(const SchedulingManager& S,
191 const SchedGraphNode* nextChoice = NULL;
193 if (mcands.size() == 0)
194 findSetWithMaxDelay(mcands, S);
196 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);
224 mcands.erase(mcands.begin() + nextIdx);
232 SchedPriorities::findSetWithMaxDelay(std::vector<candIndex>& mcands,
233 const SchedulingManager& S)
235 if (mcands.size() == 0 && nextToTry != candsAsHeap.end())
236 { // out of choices at current maximum delay;
237 // put nodes with next highest delay in mcands
238 candIndex next = nextToTry;
239 cycles_t maxDelay = candsAsHeap.getDelay(next);
240 for (; next != candsAsHeap.end()
241 && candsAsHeap.getDelay(next) == maxDelay; ++next)
242 mcands.push_back(next);
246 if (SchedDebugLevel >= Sched_PrintSchedTrace) {
247 std::cerr << " Cycle " << (long)getTime() << ": "
248 << "Next highest delay = " << (long)maxDelay << " : "
249 << mcands.size() << " Nodes with this delay: ";
250 for (unsigned i=0; i < mcands.size(); i++)
251 std::cerr << candsAsHeap.getNode(mcands[i])->getNodeId() << ", ";
259 SchedPriorities::instructionHasLastUse(FunctionLiveVarInfo &LVI,
260 const SchedGraphNode* graphNode) {
261 const MachineInstr *MI = graphNode->getMachineInstr();
263 hash_map<const MachineInstr*, bool>::const_iterator
264 ui = lastUseMap.find(MI);
265 if (ui != lastUseMap.end())
268 // else check if instruction is a last use and save it in the hash_map
269 bool hasLastUse = false;
270 const BasicBlock* bb = graphNode->getMachineBasicBlock().getBasicBlock();
271 const ValueSet &LVs = LVI.getLiveVarSetBeforeMInst(MI, bb);
273 for (MachineInstr::const_val_op_iterator OI = MI->begin(), OE = MI->end();
275 if (!LVs.count(*OI)) {
280 return lastUseMap[MI] = hasLastUse;
283 } // End llvm namespace