From 37866b34376c3143006efde1b544cfce688f7ea9 Mon Sep 17 00:00:00 2001 From: "Vikram S. Adve" Date: Tue, 28 Aug 2001 23:06:49 +0000 Subject: [PATCH] Class that encapsulates priority heuristics for instruction scheduling. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@395 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CodeGen/SchedPriorities.h | 225 +++++++++++++ lib/CodeGen/InstrSched/SchedPriorities.cpp | 297 ++++++++++++++++++ .../SparcV9/InstrSched/SchedPriorities.cpp | 297 ++++++++++++++++++ 3 files changed, 819 insertions(+) create mode 100644 include/llvm/CodeGen/SchedPriorities.h create mode 100644 lib/CodeGen/InstrSched/SchedPriorities.cpp create mode 100644 lib/Target/SparcV9/InstrSched/SchedPriorities.cpp diff --git a/include/llvm/CodeGen/SchedPriorities.h b/include/llvm/CodeGen/SchedPriorities.h new file mode 100644 index 00000000000..bfabdb8464c --- /dev/null +++ b/include/llvm/CodeGen/SchedPriorities.h @@ -0,0 +1,225 @@ +/* -*-C++-*- + **************************************************************************** + * File: + * SchedPriorities.h + * + * Purpose: + * Encapsulate heuristics for instruction scheduling. + * + * Strategy: + * Priority ordering rules: + * (1) Max delay, which is the order of the heap S.candsAsHeap. + * (2) Instruction that frees up a register. + * (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 + ***************************************************************************/ + +#ifndef LLVM_CODEGEN_SCHEDPRIORITIES_H +#define LLVM_CODEGEN_SCHEDPRIORITIES_H + +//************************** System Include Files **************************/ + +#include +#include +#include +#include + +//*************************** User Include Files ***************************/ + +#include "llvm/CFG.h" // just for graph iterators +#include "llvm/Support/NonCopyable.h" +#include "llvm/Support/HashExtras.h" +#include "llvm/Analysis/LiveVar/MethodLiveVarInfo.h" +#include "llvm/CodeGen/SchedGraph.h" +#include "llvm/CodeGen/InstrScheduling.h" + +//************************* Opaque Declarations ****************************/ + +class Method; +class MachineInstr; +class SchedulingManager; + +/******************** Exported Data Types and Constants ********************/ + + +//*********************** Public Class Declarations ************************/ + +struct NodeDelayPair { + const SchedGraphNode* node; + cycles_t delay; + NodeDelayPair(const SchedGraphNode* n, cycles_t d) : node(n), delay(d) {} + inline bool operator< (const NodeDelayPair& np) { return delay < np.delay; } +}; + +inline bool +NDPLessThan(const NodeDelayPair* np1, const NodeDelayPair* np2) +{ + return (np1->delay < np2->delay); +} + +class NodeHeap: public list, public NonCopyable { +public: + typedef list::iterator iterator; + typedef list::const_iterator const_iterator; + +public: + /*ctor*/ NodeHeap () : list(), _size(0) {} + /*dtor*/ ~NodeHeap () {} + + inline unsigned int size () const { return _size; } + + const SchedGraphNode* getNode (const_iterator i) const { return (*i)->node; } + cycles_t getDelay(const_iterator i) const { return (*i)->delay;} + + inline void makeHeap() { + // make_heap(begin(), end(), NDPLessThan); + } + + inline iterator findNode(const SchedGraphNode* node) { + for (iterator I=begin(); I != end(); ++I) + if (getNode(I) == node) + return I; + return end(); + } + + inline void removeNode (const SchedGraphNode* node) { + iterator ndpPtr = findNode(node); + if (ndpPtr != end()) + { + delete *ndpPtr; + erase(ndpPtr); + --_size; + } + }; + + void insert(const SchedGraphNode* node, cycles_t delay) { + NodeDelayPair* ndp = new NodeDelayPair(node, delay); + if (_size == 0 || front()->delay < delay) + push_front(ndp); + else + { + iterator I=begin(); + for ( ; I != end() && getDelay(I) >= delay; ++I) + ; + list::insert(I, ndp); + } + _size++; + } +private: + unsigned int _size; +}; + + +class SchedPriorities: public NonCopyable { +public: + /*ctor*/ SchedPriorities (const Method* method, + const SchedGraph* _graph); + + // This must be called before scheduling begins. + void initialize (); + + cycles_t getTime () const { return curTime; } + cycles_t getEarliestReadyTime () const { return earliestReadyTime; } + unsigned getNumReady () const { return candsAsHeap.size(); } + bool nodeIsReady (const SchedGraphNode* node) const { + return (candsAsSet.find(node) != candsAsSet.end()); + } + + void issuedReadyNodeAt (cycles_t curTime, + const SchedGraphNode* node); + + void insertReady (const SchedGraphNode* node); + + void updateTime (cycles_t /*unused*/); + + const SchedGraphNode* getNextHighest (const SchedulingManager& S, + cycles_t curTime); + // choose next highest priority instr + +private: + typedef NodeHeap::iterator candIndex; + +private: + cycles_t curTime; + const SchedGraph* graph; + MethodLiveVarInfo methodLiveVarInfo; + hash_map lastUseMap; + vector nodeDelayVec; + vector earliestForNode; + cycles_t earliestReadyTime; + NodeHeap candsAsHeap; // candidate nodes, ready to go + hash_set candsAsSet; // same entries as candsAsHeap, + // but as set for fast lookup + vector mcands; // holds pointers into cands + candIndex nextToTry; // next cand after the last + // one tried in this cycle + + int chooseByRule1 (vector& mcands); + int chooseByRule2 (vector& mcands); + int chooseByRule3 (vector& mcands); + + void findSetWithMaxDelay (vector& mcands, + const SchedulingManager& S); + + void computeDelays (const SchedGraph* graph); + + void initializeReadyHeap (const SchedGraph* graph); + + bool instructionHasLastUse (MethodLiveVarInfo& methodLiveVarInfo, + const SchedGraphNode* graphNode); + + // NOTE: The next two return references to the actual vector entries. + // Use with care. + cycles_t& getNodeDelayRef (const SchedGraphNode* node) { + assert(node->getNodeId() < nodeDelayVec.size()); + return nodeDelayVec[node->getNodeId()]; + } + cycles_t& getEarliestForNodeRef (const SchedGraphNode* node) { + assert(node->getNodeId() < earliestForNode.size()); + return earliestForNode[node->getNodeId()]; + } +}; + + +inline 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 = min(earliestReadyTime, + earliestForNode[node->getNodeId()]); + + if (SchedDebugLevel >= Sched_PrintSchedTrace) + { + printIndent(2); + cout << "Cycle " << this->getTime() << ": " + << " Node " << node->getNodeId() << " is ready; " + << " Delay = " << this->getNodeDelayRef(node) << "; Instruction: " + << endl; + printIndent(4); + cout << * node->getMachineInstr() << endl; + } +} + +inline void +SchedPriorities::updateTime(cycles_t c) +{ + curTime = c; + nextToTry = candsAsHeap.begin(); + mcands.clear(); +} + +inline ostream& operator<< (ostream& os, const NodeDelayPair* nd) { + os << "Delay for node " << nd->node->getNodeId() + << " = " << nd->delay << endl; + return os; +} + +/***************************************************************************/ + +#endif diff --git a/lib/CodeGen/InstrSched/SchedPriorities.cpp b/lib/CodeGen/InstrSched/SchedPriorities.cpp new file mode 100644 index 00000000000..fe039cc2a7b --- /dev/null +++ b/lib/CodeGen/InstrSched/SchedPriorities.cpp @@ -0,0 +1,297 @@ +/* -*-C++-*- + **************************************************************************** + * File: + * SchedPriorities.h + * + * Purpose: + * Encapsulate heuristics for instruction scheduling. + * + * Strategy: + * Priority ordering rules: + * (1) Max delay, which is the order of the heap S.candsAsHeap. + * (2) Instruction that frees up a register. + * (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 + ***************************************************************************/ + +//************************** System Include Files **************************/ + +#include +#include +#include +#include + +//*************************** User Include Files ***************************/ + +#include "llvm/Method.h" +#include "llvm/CodeGen/MachineInstr.h" +#include "llvm/CodeGen/InstrScheduling.h" +#include "llvm/CodeGen/SchedPriorities.h" + +//************************* Forward Declarations ***************************/ + + +/*ctor*/ +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), + earliestReadyTime(0), + candsAsHeap(), + candsAsSet(), + mcands(), + nextToTry(candsAsHeap.begin()) +{ + methodLiveVarInfo.analyze(); + computeDelays(graph); +} + + +void +SchedPriorities::initialize() +{ + initializeReadyHeap(graph); +} + + +void +SchedPriorities::computeDelays(const SchedGraph* graph) +{ + sg_po_const_iterator poIter = sg_po_const_iterator::begin(graph->getRoot()); + sg_po_const_iterator poEnd = sg_po_const_iterator::end( graph->getRoot()); + 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 = getNodeDelayRef((*E)->getSink()); + nodeDelay = max(nodeDelay, sinkDelay + (*E)->getMinDelay()); + } + } + getNodeDelayRef(node) = nodeDelay; + } +} + + +void +SchedPriorities::initializeReadyHeap(const SchedGraph* graph) +{ + const SchedGraphNode* graphRoot = graph->getRoot(); + assert(graphRoot->getMachineInstr() == NULL && "Expect dummy root"); + + // Insert immediate successors of dummy root, which are the actual roots + sg_succ_const_iterator SEnd = succ_end(graphRoot); + for (sg_succ_const_iterator S = succ_begin(graphRoot); S != SEnd; ++S) + this->insertReady(*S); + +#undef TEST_HEAP_CONVERSION +#ifdef TEST_HEAP_CONVERSION + cout << "Before heap conversion:" << endl; + copy(candsAsHeap.begin(), candsAsHeap.end(), + ostream_iterator(cout,"\n")); +#endif + + candsAsHeap.makeHeap(); + +#ifdef TEST_HEAP_CONVERSION + cout << "After heap conversion:" << endl; + copy(candsAsHeap.begin(), candsAsHeap.end(), + ostream_iterator(cout,"\n")); +#endif +} + + +void +SchedPriorities::issuedReadyNodeAt(cycles_t curTime, + const SchedGraphNode* node) +{ + candsAsHeap.removeNode(node); + candsAsSet.erase(node); + mcands.clear(); // ensure reset choices is called before any more choices + + if (earliestReadyTime == getEarliestForNodeRef(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))); + } + + // 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()); + } +} + + +//---------------------------------------------------------------------- +// Priority ordering rules: +// (1) Max delay, which is the order of the heap S.candsAsHeap. +// (2) Instruction that frees up a register. +// (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. +//---------------------------------------------------------------------- + +inline int +SchedPriorities::chooseByRule1(vector& mcands) +{ + return (mcands.size() == 1)? 0 // only one choice exists so take it + : -1; // -1 indicates multiple choices +} + +inline int +SchedPriorities::chooseByRule2(vector& 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, + candsAsHeap.getNode(mcands[i]))) + return i; + return -1; +} + +inline int +SchedPriorities::chooseByRule3(vector& 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; + } + } + return indexWithMaxUses; +} + +const SchedGraphNode* +SchedPriorities::getNextHighest(const SchedulingManager& S, + 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 + + if (nextIdx == -1) + nextIdx = chooseByRule2(mcands); // rule 2 + + if (nextIdx == -1) + nextIdx = chooseByRule3(mcands); // rule 3 + + 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 (getEarliestForNodeRef(nextChoice) > curTime + || ! instrIsFeasible(S, nextChoice->getOpCode())) + { + mcands.erase(mcands.begin() + nextIdx); + nextIdx = -1; + if (mcands.size() == 0) + findSetWithMaxDelay(mcands, S); + } + } + + if (nextIdx >= 0) + { + mcands.erase(mcands.begin() + nextIdx); + return nextChoice; + } + else + return NULL; +} + + +void +SchedPriorities::findSetWithMaxDelay(vector& mcands, + const SchedulingManager& S) +{ + if (mcands.size() == 0 && nextToTry != candsAsHeap.end()) + { // out of choices at current maximum delay; + // put nodes with next highest delay in mcands + candIndex next = nextToTry; + cycles_t maxDelay = candsAsHeap.getDelay(next); + for (; next != candsAsHeap.end() + && candsAsHeap.getDelay(next) == maxDelay; ++next) + mcands.push_back(next); + + nextToTry = next; + + if (SchedDebugLevel >= Sched_PrintSchedTrace) + { + printIndent(2); + cout << "Cycle " << this->getTime() << ": " + << "Next highest delay = " << maxDelay << " : " + << mcands.size() << " Nodes with this delay: "; + for (unsigned i=0; i < mcands.size(); i++) + cout << candsAsHeap.getNode(mcands[i])->getNodeId() << ", "; + cout << endl; + } + } +} + + +bool +SchedPriorities::instructionHasLastUse(MethodLiveVarInfo& methodLiveVarInfo, + const SchedGraphNode* graphNode) +{ + const MachineInstr* minstr = graphNode->getMachineInstr(); + + hash_map::const_iterator + ui = lastUseMap.find(minstr); + if (ui != lastUseMap.end()) + 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->getInstr()->getParent(); + 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; + } + + lastUseMap[minstr] = hasLastUse; + return hasLastUse; +} + diff --git a/lib/Target/SparcV9/InstrSched/SchedPriorities.cpp b/lib/Target/SparcV9/InstrSched/SchedPriorities.cpp new file mode 100644 index 00000000000..fe039cc2a7b --- /dev/null +++ b/lib/Target/SparcV9/InstrSched/SchedPriorities.cpp @@ -0,0 +1,297 @@ +/* -*-C++-*- + **************************************************************************** + * File: + * SchedPriorities.h + * + * Purpose: + * Encapsulate heuristics for instruction scheduling. + * + * Strategy: + * Priority ordering rules: + * (1) Max delay, which is the order of the heap S.candsAsHeap. + * (2) Instruction that frees up a register. + * (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 + ***************************************************************************/ + +//************************** System Include Files **************************/ + +#include +#include +#include +#include + +//*************************** User Include Files ***************************/ + +#include "llvm/Method.h" +#include "llvm/CodeGen/MachineInstr.h" +#include "llvm/CodeGen/InstrScheduling.h" +#include "llvm/CodeGen/SchedPriorities.h" + +//************************* Forward Declarations ***************************/ + + +/*ctor*/ +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), + earliestReadyTime(0), + candsAsHeap(), + candsAsSet(), + mcands(), + nextToTry(candsAsHeap.begin()) +{ + methodLiveVarInfo.analyze(); + computeDelays(graph); +} + + +void +SchedPriorities::initialize() +{ + initializeReadyHeap(graph); +} + + +void +SchedPriorities::computeDelays(const SchedGraph* graph) +{ + sg_po_const_iterator poIter = sg_po_const_iterator::begin(graph->getRoot()); + sg_po_const_iterator poEnd = sg_po_const_iterator::end( graph->getRoot()); + 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 = getNodeDelayRef((*E)->getSink()); + nodeDelay = max(nodeDelay, sinkDelay + (*E)->getMinDelay()); + } + } + getNodeDelayRef(node) = nodeDelay; + } +} + + +void +SchedPriorities::initializeReadyHeap(const SchedGraph* graph) +{ + const SchedGraphNode* graphRoot = graph->getRoot(); + assert(graphRoot->getMachineInstr() == NULL && "Expect dummy root"); + + // Insert immediate successors of dummy root, which are the actual roots + sg_succ_const_iterator SEnd = succ_end(graphRoot); + for (sg_succ_const_iterator S = succ_begin(graphRoot); S != SEnd; ++S) + this->insertReady(*S); + +#undef TEST_HEAP_CONVERSION +#ifdef TEST_HEAP_CONVERSION + cout << "Before heap conversion:" << endl; + copy(candsAsHeap.begin(), candsAsHeap.end(), + ostream_iterator(cout,"\n")); +#endif + + candsAsHeap.makeHeap(); + +#ifdef TEST_HEAP_CONVERSION + cout << "After heap conversion:" << endl; + copy(candsAsHeap.begin(), candsAsHeap.end(), + ostream_iterator(cout,"\n")); +#endif +} + + +void +SchedPriorities::issuedReadyNodeAt(cycles_t curTime, + const SchedGraphNode* node) +{ + candsAsHeap.removeNode(node); + candsAsSet.erase(node); + mcands.clear(); // ensure reset choices is called before any more choices + + if (earliestReadyTime == getEarliestForNodeRef(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))); + } + + // 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()); + } +} + + +//---------------------------------------------------------------------- +// Priority ordering rules: +// (1) Max delay, which is the order of the heap S.candsAsHeap. +// (2) Instruction that frees up a register. +// (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. +//---------------------------------------------------------------------- + +inline int +SchedPriorities::chooseByRule1(vector& mcands) +{ + return (mcands.size() == 1)? 0 // only one choice exists so take it + : -1; // -1 indicates multiple choices +} + +inline int +SchedPriorities::chooseByRule2(vector& 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, + candsAsHeap.getNode(mcands[i]))) + return i; + return -1; +} + +inline int +SchedPriorities::chooseByRule3(vector& 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; + } + } + return indexWithMaxUses; +} + +const SchedGraphNode* +SchedPriorities::getNextHighest(const SchedulingManager& S, + 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 + + if (nextIdx == -1) + nextIdx = chooseByRule2(mcands); // rule 2 + + if (nextIdx == -1) + nextIdx = chooseByRule3(mcands); // rule 3 + + 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 (getEarliestForNodeRef(nextChoice) > curTime + || ! instrIsFeasible(S, nextChoice->getOpCode())) + { + mcands.erase(mcands.begin() + nextIdx); + nextIdx = -1; + if (mcands.size() == 0) + findSetWithMaxDelay(mcands, S); + } + } + + if (nextIdx >= 0) + { + mcands.erase(mcands.begin() + nextIdx); + return nextChoice; + } + else + return NULL; +} + + +void +SchedPriorities::findSetWithMaxDelay(vector& mcands, + const SchedulingManager& S) +{ + if (mcands.size() == 0 && nextToTry != candsAsHeap.end()) + { // out of choices at current maximum delay; + // put nodes with next highest delay in mcands + candIndex next = nextToTry; + cycles_t maxDelay = candsAsHeap.getDelay(next); + for (; next != candsAsHeap.end() + && candsAsHeap.getDelay(next) == maxDelay; ++next) + mcands.push_back(next); + + nextToTry = next; + + if (SchedDebugLevel >= Sched_PrintSchedTrace) + { + printIndent(2); + cout << "Cycle " << this->getTime() << ": " + << "Next highest delay = " << maxDelay << " : " + << mcands.size() << " Nodes with this delay: "; + for (unsigned i=0; i < mcands.size(); i++) + cout << candsAsHeap.getNode(mcands[i])->getNodeId() << ", "; + cout << endl; + } + } +} + + +bool +SchedPriorities::instructionHasLastUse(MethodLiveVarInfo& methodLiveVarInfo, + const SchedGraphNode* graphNode) +{ + const MachineInstr* minstr = graphNode->getMachineInstr(); + + hash_map::const_iterator + ui = lastUseMap.find(minstr); + if (ui != lastUseMap.end()) + 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->getInstr()->getParent(); + 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; + } + + lastUseMap[minstr] = hasLastUse; + return hasLastUse; +} + -- 2.34.1