aboutsummaryrefslogtreecommitdiff
path: root/lib/CodeGen/InstrSched/SchedPriorities.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'lib/CodeGen/InstrSched/SchedPriorities.cpp')
-rw-r--r--lib/CodeGen/InstrSched/SchedPriorities.cpp194
1 files changed, 88 insertions, 106 deletions
diff --git a/lib/CodeGen/InstrSched/SchedPriorities.cpp b/lib/CodeGen/InstrSched/SchedPriorities.cpp
index a35600c0f0..1644d5ecbc 100644
--- a/lib/CodeGen/InstrSched/SchedPriorities.cpp
+++ b/lib/CodeGen/InstrSched/SchedPriorities.cpp
@@ -22,7 +22,6 @@
#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()
@@ -43,41 +42,35 @@ SchedPriorities::SchedPriorities(const Function *, const SchedGraph *G,
void
-SchedPriorities::initialize()
-{
+SchedPriorities::initialize() {
initializeReadyHeap(graph);
}
void
-SchedPriorities::computeDelays(const SchedGraph* graph)
-{
+SchedPriorities::computeDelays(const SchedGraph* graph) {
po_iterator<const SchedGraph*> poIter = po_begin(graph), poEnd =po_end(graph);
- for ( ; poIter != poEnd; ++poIter)
- {
- const SchedGraphNode* node = *poIter;
- cycles_t nodeDelay;
- if (node->beginOutEdges() == node->endOutEdges())
- nodeDelay = node->getLatency();
- else
- {
- // Iterate over the out-edges of the node to compute delay
- nodeDelay = 0;
- for (SchedGraphNode::const_iterator E=node->beginOutEdges();
- E != node->endOutEdges(); ++E)
- {
- cycles_t sinkDelay = getNodeDelay((SchedGraphNode*)(*E)->getSink());
- nodeDelay = std::max(nodeDelay, sinkDelay + (*E)->getMinDelay());
- }
- }
- getNodeDelayRef(node) = nodeDelay;
+ for ( ; poIter != poEnd; ++poIter) {
+ const SchedGraphNode* node = *poIter;
+ cycles_t nodeDelay;
+ if (node->beginOutEdges() == node->endOutEdges())
+ nodeDelay = node->getLatency();
+ else {
+ // Iterate over the out-edges of the node to compute delay
+ nodeDelay = 0;
+ for (SchedGraphNode::const_iterator E=node->beginOutEdges();
+ E != node->endOutEdges(); ++E) {
+ cycles_t sinkDelay = getNodeDelay((SchedGraphNode*)(*E)->getSink());
+ nodeDelay = std::max(nodeDelay, sinkDelay + (*E)->getMinDelay());
+ }
}
+ getNodeDelayRef(node) = nodeDelay;
+ }
}
void
-SchedPriorities::initializeReadyHeap(const SchedGraph* graph)
-{
+SchedPriorities::initializeReadyHeap(const SchedGraph* graph) {
const SchedGraphNode* graphRoot = (const SchedGraphNode*)graph->getRoot();
assert(graphRoot->getMachineInstr() == NULL && "Expect dummy root");
@@ -88,9 +81,9 @@ SchedPriorities::initializeReadyHeap(const SchedGraph* graph)
#undef TEST_HEAP_CONVERSION
#ifdef TEST_HEAP_CONVERSION
- cerr << "Before heap conversion:\n";
+ std::cerr << "Before heap conversion:\n";
copy(candsAsHeap.begin(), candsAsHeap.end(),
- ostream_iterator<NodeDelayPair*>(cerr,"\n"));
+ ostream_iterator<NodeDelayPair*>(std::cerr,"\n"));
#endif
candsAsHeap.makeHeap();
@@ -98,55 +91,54 @@ SchedPriorities::initializeReadyHeap(const SchedGraph* graph)
nextToTry = candsAsHeap.begin();
#ifdef TEST_HEAP_CONVERSION
- cerr << "After heap conversion:\n";
+ std::cerr << "After heap conversion:\n";
copy(candsAsHeap.begin(), candsAsHeap.end(),
- ostream_iterator<NodeDelayPair*>(cerr,"\n"));
+ ostream_iterator<NodeDelayPair*>(std::cerr,"\n"));
#endif
}
void
-SchedPriorities::insertReady(const SchedGraphNode* node)
-{
+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";
- }
+ if (SchedDebugLevel >= Sched_PrintSchedTrace) {
+ std::cerr << " Node " << node->getNodeId() << " will be ready in Cycle "
+ << getEarliestReadyTimeForNode(node) << "; "
+ << " Delay = " <<(long)getNodeDelay(node) << "; Instruction: \n"
+ << " " << *node->getMachineInstr() << "\n";
+ }
}
void
SchedPriorities::issuedReadyNodeAt(cycles_t curTime,
- const SchedGraphNode* node)
-{
+ const SchedGraphNode* node) {
candsAsHeap.removeNode(node);
candsAsSet.erase(node);
mcands.clear(); // ensure reset choices is called before any more choices
- 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 = std::min(earliestReadyTime,
- getEarliestReadyTimeForNode(candsAsHeap.getNode(I)));
- }
+ 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 =
+ 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 = getEarliestReadyTimeForNodeRef((SchedGraphNode*)(*E)->getSink());
- etime = std::max(etime, curTime + (*E)->getMinDelay());
- }
+ E != node->endOutEdges(); ++E) {
+ cycles_t& etime =
+ getEarliestReadyTimeForNodeRef((SchedGraphNode*)(*E)->getSink());
+ etime = std::max(etime, curTime + (*E)->getMinDelay());
+ }
}
@@ -160,15 +152,13 @@ SchedPriorities::issuedReadyNodeAt(cycles_t curTime,
//----------------------------------------------------------------------
inline int
-SchedPriorities::chooseByRule1(std::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(std::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++)
if (instructionHasLastUse(methodLiveVarInfo,
@@ -178,67 +168,60 @@ SchedPriorities::chooseByRule2(std::vector<candIndex>& mcands)
}
inline int
-SchedPriorities::chooseByRule3(std::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();
int indexWithMaxUses = 0;
- for (unsigned i=1, N = mcands.size(); i < N; i++)
- {
- int numUses = candsAsHeap.getNode(mcands[i])->getNumOutEdges();
- if (numUses > maxUses)
- {
- maxUses = numUses;
- indexWithMaxUses = i;
- }
+ for (unsigned i=1, N = mcands.size(); i < N; i++) {
+ int numUses = candsAsHeap.getNode(mcands[i])->getNumOutEdges();
+ if (numUses > maxUses) {
+ maxUses = numUses;
+ indexWithMaxUses = i;
}
+ }
return indexWithMaxUses;
}
const SchedGraphNode*
SchedPriorities::getNextHighest(const SchedulingManager& S,
- cycles_t curTime)
-{
+ cycles_t curTime) {
int nextIdx = -1;
const SchedGraphNode* nextChoice = NULL;
if (mcands.size() == 0)
findSetWithMaxDelay(mcands, S);
- while (nextIdx < 0 && mcands.size() > 0)
- {
- nextIdx = chooseByRule1(mcands); // rule 1
+ while (nextIdx < 0 && mcands.size() > 0) {
+ nextIdx = chooseByRule1(mcands); // rule 1
- if (nextIdx == -1)
- nextIdx = chooseByRule2(mcands); // rule 2
+ if (nextIdx == -1)
+ nextIdx = chooseByRule2(mcands); // rule 2
- if (nextIdx == -1)
- nextIdx = chooseByRule3(mcands); // rule 3
+ if (nextIdx == -1)
+ nextIdx = chooseByRule3(mcands); // rule 3
- if (nextIdx == -1)
- nextIdx = 0; // default to first choice by delays
+ if (nextIdx == -1)
+ nextIdx = 0; // default to first choice by delays
- // We have found the next best candidate. Check if it ready in
- // the current cycle, and if it is feasible.
- // If not, remove it from mcands and continue. Refill mcands if
- // it becomes empty.
- nextChoice = candsAsHeap.getNode(mcands[nextIdx]);
- if (getEarliestReadyTimeForNode(nextChoice) > curTime
- || ! instrIsFeasible(S, nextChoice->getMachineInstr()->getOpCode()))
- {
- mcands.erase(mcands.begin() + nextIdx);
- nextIdx = -1;
- if (mcands.size() == 0)
- findSetWithMaxDelay(mcands, S);
- }
- }
-
- if (nextIdx >= 0)
+ // We have found the next best candidate. Check if it ready in
+ // the current cycle, and if it is feasible.
+ // If not, remove it from mcands and continue. Refill mcands if
+ // it becomes empty.
+ nextChoice = candsAsHeap.getNode(mcands[nextIdx]);
+ if (getEarliestReadyTimeForNode(nextChoice) > curTime
+ || ! instrIsFeasible(S, nextChoice->getMachineInstr()->getOpCode()))
{
mcands.erase(mcands.begin() + nextIdx);
- return nextChoice;
+ nextIdx = -1;
+ if (mcands.size() == 0)
+ findSetWithMaxDelay(mcands, S);
}
- else
+ }
+
+ if (nextIdx >= 0) {
+ mcands.erase(mcands.begin() + nextIdx);
+ return nextChoice;
+ } else
return NULL;
}
@@ -258,15 +241,14 @@ SchedPriorities::findSetWithMaxDelay(std::vector<candIndex>& mcands,
nextToTry = next;
- if (SchedDebugLevel >= Sched_PrintSchedTrace)
- {
- cerr << " Cycle " << (long)getTime() << ": "
- << "Next highest delay = " << (long)maxDelay << " : "
- << mcands.size() << " Nodes with this delay: ";
- for (unsigned i=0; i < mcands.size(); i++)
- cerr << candsAsHeap.getNode(mcands[i])->getNodeId() << ", ";
- cerr << "\n";
- }
+ if (SchedDebugLevel >= Sched_PrintSchedTrace) {
+ std::cerr << " Cycle " << (long)getTime() << ": "
+ << "Next highest delay = " << (long)maxDelay << " : "
+ << mcands.size() << " Nodes with this delay: ";
+ for (unsigned i=0; i < mcands.size(); i++)
+ std::cerr << candsAsHeap.getNode(mcands[i])->getNodeId() << ", ";
+ std::cerr << "\n";
+ }
}
}
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2025-11-04 12:47:44 +0000