-// $Id$ -*-C++-*-
-//***************************************************************************
-// File:
-// SchedPriorities.h
+//===-- SchedPriorities.h - Encapsulate scheduling heuristics -------------===//
//
-// Purpose:
-// Encapsulate heuristics for instruction scheduling.
+// The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
//
// Strategy:
// Priority ordering rules:
// (3) Instruction that has the maximum number of dependent instructions.
// Note that rules 2 and 3 are only used if issue conflicts prevent
// choosing a higher priority instruction by rule 1.
-//
-// History:
-// 7/30/01 - Vikram Adve - Created
-//**************************************************************************/
+//
+//===----------------------------------------------------------------------===//
#include "SchedPriorities.h"
+#include "llvm/CodeGen/FunctionLiveVarInfo.h"
+#include "llvm/CodeGen/MachineBasicBlock.h"
+#include "llvm/Support/CFG.h"
#include "Support/PostOrderIterator.h"
+using std::cerr;
+
+std::ostream &operator<<(std::ostream &os, const NodeDelayPair* nd) {
+ return os << "Delay for node " << nd->node->getNodeId()
+ << " = " << (long)nd->delay << "\n";
+}
-SchedPriorities::SchedPriorities(const Method* method,
- const SchedGraph* _graph)
- : curTime(0),
- graph(_graph),
- methodLiveVarInfo(method), // expensive!
- lastUseMap(),
- nodeDelayVec(_graph->getNumNodes(),INVALID_LATENCY), //make errors obvious
- earliestForNode(_graph->getNumNodes(), 0),
+SchedPriorities::SchedPriorities(const Function *, const SchedGraph *G,
+ FunctionLiveVarInfo &LVI)
+ : curTime(0), graph(G), methodLiveVarInfo(LVI),
+ nodeDelayVec(G->getNumNodes(), INVALID_LATENCY), // make errors obvious
+ earliestReadyTimeForNode(G->getNumNodes(), 0),
earliestReadyTime(0),
- candsAsHeap(),
- candsAsSet(),
- mcands(),
nextToTry(candsAsHeap.begin())
{
- methodLiveVarInfo.analyze();
computeDelays(graph);
}
const SchedGraphNode* node = *poIter;
cycles_t nodeDelay;
if (node->beginOutEdges() == node->endOutEdges())
- nodeDelay = node->getLatency();
+ nodeDelay = node->getLatency();
else
{
// Iterate over the out-edges of the node to compute delay
for (SchedGraphNode::const_iterator E=node->beginOutEdges();
E != node->endOutEdges(); ++E)
{
- cycles_t sinkDelay = getNodeDelayRef((*E)->getSink());
- nodeDelay = max(nodeDelay, sinkDelay + (*E)->getMinDelay());
+ cycles_t sinkDelay = getNodeDelay((SchedGraphNode*)(*E)->getSink());
+ nodeDelay = std::max(nodeDelay, sinkDelay + (*E)->getMinDelay());
}
}
getNodeDelayRef(node) = nodeDelay;
void
SchedPriorities::initializeReadyHeap(const SchedGraph* graph)
{
- const SchedGraphNode* graphRoot = graph->getRoot();
+ const SchedGraphNode* graphRoot = (const SchedGraphNode*)graph->getRoot();
assert(graphRoot->getMachineInstr() == NULL && "Expect dummy root");
// Insert immediate successors of dummy root, which are the actual roots
#undef TEST_HEAP_CONVERSION
#ifdef TEST_HEAP_CONVERSION
- cout << "Before heap conversion:" << endl;
+ cerr << "Before heap conversion:\n";
copy(candsAsHeap.begin(), candsAsHeap.end(),
- ostream_iterator<NodeDelayPair*>(cout,"\n"));
+ ostream_iterator<NodeDelayPair*>(cerr,"\n"));
#endif
candsAsHeap.makeHeap();
+ nextToTry = candsAsHeap.begin();
+
#ifdef TEST_HEAP_CONVERSION
- cout << "After heap conversion:" << endl;
+ cerr << "After heap conversion:\n";
copy(candsAsHeap.begin(), candsAsHeap.end(),
- ostream_iterator<NodeDelayPair*>(cout,"\n"));
+ ostream_iterator<NodeDelayPair*>(cerr,"\n"));
#endif
}
+void
+SchedPriorities::insertReady(const SchedGraphNode* node)
+{
+ candsAsHeap.insert(node, nodeDelayVec[node->getNodeId()]);
+ candsAsSet.insert(node);
+ mcands.clear(); // ensure reset choices is called before any more choices
+ earliestReadyTime = std::min(earliestReadyTime,
+ getEarliestReadyTimeForNode(node));
+
+ if (SchedDebugLevel >= Sched_PrintSchedTrace)
+ {
+ cerr << " Node " << node->getNodeId() << " will be ready in Cycle "
+ << getEarliestReadyTimeForNode(node) << "; "
+ << " Delay = " <<(long)getNodeDelay(node) << "; Instruction: \n";
+ cerr << " " << *node->getMachineInstr() << "\n";
+ }
+}
void
SchedPriorities::issuedReadyNodeAt(cycles_t curTime,
candsAsSet.erase(node);
mcands.clear(); // ensure reset choices is called before any more choices
- if (earliestReadyTime == getEarliestForNodeRef(node))
+ if (earliestReadyTime == getEarliestReadyTimeForNode(node))
{// earliestReadyTime may have been due to this node, so recompute it
earliestReadyTime = HUGE_LATENCY;
for (NodeHeap::const_iterator I=candsAsHeap.begin();
I != candsAsHeap.end(); ++I)
if (candsAsHeap.getNode(I))
- earliestReadyTime = min(earliestReadyTime,
- getEarliestForNodeRef(candsAsHeap.getNode(I)));
+ earliestReadyTime = std::min(earliestReadyTime,
+ getEarliestReadyTimeForNode(candsAsHeap.getNode(I)));
}
// Now update ready times for successors
for (SchedGraphNode::const_iterator E=node->beginOutEdges();
E != node->endOutEdges(); ++E)
{
- cycles_t& etime = getEarliestForNodeRef((*E)->getSink());
- etime = max(etime, curTime + (*E)->getMinDelay());
+ cycles_t& etime = getEarliestReadyTimeForNodeRef((SchedGraphNode*)(*E)->getSink());
+ etime = std::max(etime, curTime + (*E)->getMinDelay());
}
}
//----------------------------------------------------------------------
inline int
-SchedPriorities::chooseByRule1(vector<candIndex>& mcands)
+SchedPriorities::chooseByRule1(std::vector<candIndex>& mcands)
{
return (mcands.size() == 1)? 0 // only one choice exists so take it
: -1; // -1 indicates multiple choices
}
inline int
-SchedPriorities::chooseByRule2(vector<candIndex>& mcands)
+SchedPriorities::chooseByRule2(std::vector<candIndex>& mcands)
{
assert(mcands.size() >= 1 && "Should have at least one candidate here.");
for (unsigned i=0, N = mcands.size(); i < N; i++)
}
inline int
-SchedPriorities::chooseByRule3(vector<candIndex>& mcands)
+SchedPriorities::chooseByRule3(std::vector<candIndex>& mcands)
{
assert(mcands.size() >= 1 && "Should have at least one candidate here.");
int maxUses = candsAsHeap.getNode(mcands[0])->getNumOutEdges();
// If not, remove it from mcands and continue. Refill mcands if
// it becomes empty.
nextChoice = candsAsHeap.getNode(mcands[nextIdx]);
- if (getEarliestForNodeRef(nextChoice) > curTime
+ if (getEarliestReadyTimeForNode(nextChoice) > curTime
|| ! instrIsFeasible(S, nextChoice->getMachineInstr()->getOpCode()))
{
mcands.erase(mcands.begin() + nextIdx);
void
-SchedPriorities::findSetWithMaxDelay(vector<candIndex>& mcands,
+SchedPriorities::findSetWithMaxDelay(std::vector<candIndex>& mcands,
const SchedulingManager& S)
{
if (mcands.size() == 0 && nextToTry != candsAsHeap.end())
if (SchedDebugLevel >= Sched_PrintSchedTrace)
{
- cout << " Cycle " << this->getTime() << ": "
- << "Next highest delay = " << maxDelay << " : "
+ cerr << " Cycle " << (long)getTime() << ": "
+ << "Next highest delay = " << (long)maxDelay << " : "
<< mcands.size() << " Nodes with this delay: ";
for (unsigned i=0; i < mcands.size(); i++)
- cout << candsAsHeap.getNode(mcands[i])->getNodeId() << ", ";
- cout << endl;
+ cerr << candsAsHeap.getNode(mcands[i])->getNodeId() << ", ";
+ cerr << "\n";
}
}
}
bool
-SchedPriorities::instructionHasLastUse(MethodLiveVarInfo& methodLiveVarInfo,
- const SchedGraphNode* graphNode)
-{
- const MachineInstr* minstr = graphNode->getMachineInstr();
+SchedPriorities::instructionHasLastUse(FunctionLiveVarInfo &LVI,
+ const SchedGraphNode* graphNode) {
+ const MachineInstr *MI = graphNode->getMachineInstr();
hash_map<const MachineInstr*, bool>::const_iterator
- ui = lastUseMap.find(minstr);
+ ui = lastUseMap.find(MI);
if (ui != lastUseMap.end())
- return (*ui).second;
+ return ui->second;
// else check if instruction is a last use and save it in the hash_map
bool hasLastUse = false;
- const BasicBlock* bb = graphNode->getBB();
- const LiveVarSet* liveVars =
- methodLiveVarInfo.getLiveVarSetBeforeMInst(minstr, bb);
-
- for (MachineInstr::val_op_const_iterator vo(minstr); ! vo.done(); ++vo)
- if (liveVars->find(*vo) == liveVars->end())
- {
- hasLastUse = true;
- break;
- }
+ const BasicBlock* bb = graphNode->getMachineBasicBlock().getBasicBlock();
+ const ValueSet &LVs = LVI.getLiveVarSetBeforeMInst(MI, bb);
- lastUseMap[minstr] = hasLastUse;
- return hasLastUse;
+ for (MachineInstr::const_val_op_iterator OI = MI->begin(), OE = MI->end();
+ OI != OE; ++OI)
+ if (!LVs.count(*OI)) {
+ hasLastUse = true;
+ break;
+ }
+
+ return lastUseMap[MI] = hasLastUse;
}
projects / oota-llvm.git / blobdiff