diff options
Diffstat (limited to 'lib/Target/SparcV9/InstrSched/InstrScheduling.cpp')
| -rw-r--r-- | lib/Target/SparcV9/InstrSched/InstrScheduling.cpp | 412 |
1 files changed, 206 insertions, 206 deletions
diff --git a/lib/Target/SparcV9/InstrSched/InstrScheduling.cpp b/lib/Target/SparcV9/InstrSched/InstrScheduling.cpp index f0ac384442..44f5c6ce4e 100644 --- a/lib/Target/SparcV9/InstrSched/InstrScheduling.cpp +++ b/lib/Target/SparcV9/InstrSched/InstrScheduling.cpp @@ -1,10 +1,10 @@ //===- InstrScheduling.cpp - Generic Instruction Scheduling support -------===// -// +// // 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. -// +// //===----------------------------------------------------------------------===// // // This file implements the llvm/CodeGen/InstrScheduling.h interface, along with @@ -50,7 +50,7 @@ class SchedulingManager; //---------------------------------------------------------------------- // class InstrGroup: -// +// // Represents a group of instructions scheduled to be issued // in a single cycle. //---------------------------------------------------------------------- @@ -58,26 +58,26 @@ class SchedulingManager; class InstrGroup { InstrGroup(const InstrGroup&); // DO NOT IMPLEMENT void operator=(const InstrGroup&); // DO NOT IMPLEMENT - + public: inline const SchedGraphNode* operator[](unsigned int slotNum) const { assert(slotNum < group.size()); return group[slotNum]; } - + private: friend class InstrSchedule; - + inline void addInstr(const SchedGraphNode* node, unsigned int slotNum) { assert(slotNum < group.size()); group[slotNum] = node; } - + /*ctor*/ InstrGroup(unsigned int nslots) : group(nslots, NULL) {} - + /*ctor*/ InstrGroup(); // disable: DO NOT IMPLEMENT - + private: std::vector<const SchedGraphNode*> group; }; @@ -85,7 +85,7 @@ private: //---------------------------------------------------------------------- // class ScheduleIterator: -// +// // Iterates over the machine instructions in the for a single basic block. // The schedule is represented by an InstrSchedule object. //---------------------------------------------------------------------- @@ -98,34 +98,34 @@ private: const InstrSchedule& S; public: typedef ScheduleIterator<_NodeType> _Self; - + /*ctor*/ inline ScheduleIterator(const InstrSchedule& _schedule, unsigned _cycleNum, unsigned _slotNum) : cycleNum(_cycleNum), slotNum(_slotNum), S(_schedule) { - skipToNextInstr(); + skipToNextInstr(); } - + /*ctor*/ inline ScheduleIterator(const _Self& x) : cycleNum(x.cycleNum), slotNum(x.slotNum), S(x.S) {} - + inline bool operator==(const _Self& x) const { return (slotNum == x.slotNum && cycleNum== x.cycleNum && &S==&x.S); } - + inline bool operator!=(const _Self& x) const { return !operator==(x); } - + inline _NodeType* operator*() const; inline _NodeType* operator->() const { return operator*(); } - + _Self& operator++(); // Preincrement inline _Self operator++(int) { // Postincrement - _Self tmp(*this); ++*this; return tmp; + _Self tmp(*this); ++*this; return tmp; } - + static _Self begin(const InstrSchedule& _schedule); static _Self end( const InstrSchedule& _schedule); - + private: inline _Self& operator=(const _Self& x); // DISABLE -- DO NOT IMPLEMENT void skipToNextInstr(); @@ -134,7 +134,7 @@ private: //---------------------------------------------------------------------- // class InstrSchedule: -// +// // Represents the schedule of machine instructions for a single basic block. //---------------------------------------------------------------------- @@ -146,28 +146,28 @@ class InstrSchedule { InstrSchedule(InstrSchedule&); // DO NOT IMPLEMENT void operator=(InstrSchedule&); // DO NOT IMPLEMENT - + public: // iterators typedef ScheduleIterator<SchedGraphNode> iterator; typedef ScheduleIterator<const SchedGraphNode> const_iterator; - + iterator begin() { return iterator::begin(*this); } const_iterator begin() const { return const_iterator::begin(*this); } iterator end() { return iterator::end(*this); } const_iterator end() const { return const_iterator::end(*this); } - + public: // constructors and destructor /*ctor*/ InstrSchedule (unsigned int _nslots, unsigned int _numNodes); /*dtor*/ ~InstrSchedule (); - + public: // accessor functions to query chosen schedule const SchedGraphNode* getInstr (unsigned int slotNum, CycleCount_t c) { const InstrGroup* igroup = this->getIGroup(c); return (igroup == NULL)? NULL : (*igroup)[slotNum]; } - + inline InstrGroup* getIGroup (CycleCount_t c) { if ((unsigned)c >= groups.size()) groups.resize(c+1); @@ -175,21 +175,21 @@ public: // accessor functions to query chosen schedule groups[c] = new InstrGroup(nslots); return groups[c]; } - + inline const InstrGroup* getIGroup (CycleCount_t c) const { assert((unsigned)c < groups.size()); return groups[c]; } - + inline CycleCount_t getStartTime (unsigned int nodeId) const { assert(nodeId < startTime.size()); return startTime[nodeId]; } - + unsigned int getNumInstructions() const { return numInstr; } - + inline void scheduleInstr (const SchedGraphNode* node, unsigned int slotNum, CycleCount_t cycle) { @@ -203,7 +203,7 @@ public: // accessor functions to query chosen schedule startTime[node->getNodeId()] = cycle; ++numInstr; } - + private: friend class ScheduleIterator<SchedGraphNode>; friend class ScheduleIterator<const SchedGraphNode>; @@ -237,13 +237,13 @@ InstrSchedule::~InstrSchedule() template<class _NodeType> -inline +inline void ScheduleIterator<_NodeType>::skipToNextInstr() { while(cycleNum < S.groups.size() && S.groups[cycleNum] == NULL) ++cycleNum; // skip cycles with no instructions - + while (cycleNum < S.groups.size() && (*S.groups[cycleNum])[slotNum] == NULL) { @@ -258,7 +258,7 @@ ScheduleIterator<_NodeType>::skipToNextInstr() } template<class _NodeType> -inline +inline ScheduleIterator<_NodeType>& ScheduleIterator<_NodeType>::operator++() // Preincrement { @@ -267,7 +267,7 @@ ScheduleIterator<_NodeType>::operator++() // Preincrement ++cycleNum; slotNum = 0; } - skipToNextInstr(); + skipToNextInstr(); return *this; } @@ -288,7 +288,7 @@ ScheduleIterator<_NodeType>::end(const InstrSchedule& _schedule) //---------------------------------------------------------------------- // class DelaySlotInfo: -// +// // Record information about delay slots for a single branch instruction. // Delay slots are simply indexed by slot number 1 ... numDelaySlots //---------------------------------------------------------------------- @@ -299,7 +299,7 @@ class DelaySlotInfo { std::vector<const SchedGraphNode*> delayNodeVec; CycleCount_t delayedNodeCycle; unsigned delayedNodeSlotNum; - + DelaySlotInfo(const DelaySlotInfo &); // DO NOT IMPLEMENT void operator=(const DelaySlotInfo&); // DO NOT IMPLEMENT public: @@ -307,32 +307,32 @@ public: unsigned _ndelays) : brNode(_brNode), ndelays(_ndelays), delayedNodeCycle(0), delayedNodeSlotNum(0) {} - + inline unsigned getNumDelays () { return ndelays; } - + inline const std::vector<const SchedGraphNode*>& getDelayNodeVec() { return delayNodeVec; } - + inline void addDelayNode (const SchedGraphNode* node) { delayNodeVec.push_back(node); assert(delayNodeVec.size() <= ndelays && "Too many delay slot instrs!"); } - + inline void recordChosenSlot (CycleCount_t cycle, unsigned slotNum) { delayedNodeCycle = cycle; delayedNodeSlotNum = slotNum; } - + unsigned scheduleDelayedNode (SchedulingManager& S); }; //---------------------------------------------------------------------- // class SchedulingManager: -// +// // Represents the schedule of machine instructions for a single basic block. //---------------------------------------------------------------------- @@ -344,7 +344,7 @@ public: // publicly accessible data members const TargetSchedInfo& schedInfo; SchedPriorities& schedPrio; InstrSchedule isched; - + private: unsigned totalInstrCount; CycleCount_t curTime; @@ -355,8 +355,8 @@ private: std::vector<int> numInClass; // indexed by sched class std::vector<CycleCount_t> nextEarliestStartTime; // indexed by opCode hash_map<const SchedGraphNode*, DelaySlotInfo*> delaySlotInfoForBranches; - // indexed by branch node ptr - + // indexed by branch node ptr + public: SchedulingManager(const TargetMachine& _target, const SchedGraph* graph, SchedPriorities& schedPrio); @@ -366,38 +366,38 @@ public: E = delaySlotInfoForBranches.end(); I != E; ++I) delete I->second; } - + //---------------------------------------------------------------------- // Simplify access to the machine instruction info //---------------------------------------------------------------------- - + inline const TargetInstrInfo& getInstrInfo () const { return schedInfo.getInstrInfo(); } - + //---------------------------------------------------------------------- // Interface for checking and updating the current time //---------------------------------------------------------------------- - + inline CycleCount_t getTime () const { return curTime; } - + inline CycleCount_t getEarliestIssueTime() const { return nextEarliestIssueTime; } - + inline CycleCount_t getEarliestStartTimeForOp(MachineOpCode opCode) const { assert(opCode < (int) nextEarliestStartTime.size()); return nextEarliestStartTime[opCode]; } - + // Update current time to specified cycle inline void updateTime (CycleCount_t c) { curTime = c; schedPrio.updateTime(c); } - + //---------------------------------------------------------------------- // Functions to manage the choices for the current cycle including: // -- a vector of choices by priority (choiceVec) @@ -405,26 +405,26 @@ public: // -- number of choices in each sched class, used to check issue conflicts // between choices for a single cycle //---------------------------------------------------------------------- - + inline unsigned int getNumChoices () const { return choiceVec.size(); } - + inline unsigned getNumChoicesInClass (const InstrSchedClass& sc) const { assert(sc < numInClass.size() && "Invalid op code or sched class!"); return numInClass[sc]; } - + inline const SchedGraphNode* getChoice(unsigned int i) const { // assert(i < choiceVec.size()); don't check here. return choiceVec[i]; } - + inline hash_set<const SchedGraphNode*>& getChoicesForSlot(unsigned slotNum) { assert(slotNum < nslots); return choicesForSlot[slotNum]; } - + inline void addChoice (const SchedGraphNode* node) { // Append the instruction to the vector of choices for current cycle. // Increment numInClass[c] for the sched class to which the instr belongs. @@ -433,14 +433,14 @@ public: assert(sc < numInClass.size()); numInClass[sc]++; } - + inline void addChoiceToSlot (unsigned int slotNum, const SchedGraphNode* node) { // Add the instruction to the choice set for the specified slot assert(slotNum < nslots); choicesForSlot[slotNum].insert(node); } - + inline void resetChoices () { choiceVec.clear(); for (unsigned int s=0; s < nslots; s++) @@ -448,40 +448,40 @@ public: for (unsigned int c=0; c < numInClass.size(); c++) numInClass[c] = 0; } - + //---------------------------------------------------------------------- // Code to query and manage the partial instruction schedule so far //---------------------------------------------------------------------- - + inline unsigned int getNumScheduled () const { return isched.getNumInstructions(); } - + inline unsigned int getNumUnscheduled() const { return totalInstrCount - isched.getNumInstructions(); } - + inline bool isScheduled (const SchedGraphNode* node) const { return (isched.getStartTime(node->getNodeId()) >= 0); } - + inline void scheduleInstr (const SchedGraphNode* node, unsigned int slotNum, CycleCount_t cycle) { assert(! isScheduled(node) && "Instruction already scheduled?"); - + // add the instruction to the schedule isched.scheduleInstr(node, slotNum, cycle); - + // update the earliest start times of all nodes that conflict with `node' // and the next-earliest time anything can issue if `node' causes bubbles updateEarliestStartTimes(node, cycle); - + // remove the instruction from the choice sets for all slots for (unsigned s=0; s < nslots; s++) choicesForSlot[s].erase(node); - + // and decrement the instr count for the sched class to which it belongs const InstrSchedClass& sc = schedInfo.getSchedClass(node->getOpcode()); assert(sc < numInClass.size()); @@ -491,7 +491,7 @@ public: //---------------------------------------------------------------------- // Create and retrieve delay slot info for delayed instructions //---------------------------------------------------------------------- - + inline DelaySlotInfo* getDelaySlotInfoForInstr(const SchedGraphNode* bn, bool createIfMissing=false) { @@ -506,7 +506,7 @@ public: new DelaySlotInfo(bn, getInstrInfo().getNumDelaySlots(bn->getOpcode())); return delaySlotInfoForBranches[bn] = dinfo; } - + private: SchedulingManager(); // DISABLED: DO NOT IMPLEMENT void updateEarliestStartTimes(const SchedGraphNode* node, CycleCount_t schedTime); @@ -529,7 +529,7 @@ SchedulingManager::SchedulingManager(const TargetMachine& target, (CycleCount_t) 0) // set all to 0 { updateTime(0); - + // Note that an upper bound on #choices for each slot is = nslots since // we use this vector to hold a feasible set of instructions, and more // would be infeasible. Reserve that much memory since it is probably small. @@ -547,10 +547,10 @@ SchedulingManager::updateEarliestStartTimes(const SchedGraphNode* node, nextEarliestIssueTime = std::max(nextEarliestIssueTime, curTime + 1 + schedInfo.numBubblesAfter(node->getOpcode())); } - + const std::vector<MachineOpCode>& conflictVec = schedInfo.getConflictList(node->getOpcode()); - + for (unsigned i=0; i < conflictVec.size(); i++) { MachineOpCode toOp = conflictVec[i]; @@ -570,9 +570,9 @@ AssignInstructionsToSlots(class SchedulingManager& S, unsigned maxIssue) // find the slot to start from, in the current cycle unsigned int startSlot = 0; CycleCount_t curTime = S.getTime(); - + assert(maxIssue > 0 && maxIssue <= S.nslots - startSlot); - + // If only one instruction can be issued, do so. if (maxIssue == 1) for (unsigned s=startSlot; s < S.nslots; s++) @@ -581,12 +581,12 @@ AssignInstructionsToSlots(class SchedulingManager& S, unsigned maxIssue) S.scheduleInstr(*S.getChoicesForSlot(s).begin(), s, curTime); return; } - + // Otherwise, choose from the choices for each slot - // + // InstrGroup* igroup = S.isched.getIGroup(S.getTime()); assert(igroup != NULL && "Group creation failed?"); - + // Find a slot that has only a single choice, and take it. // If all slots have 0 or multiple choices, pick the first slot with // choices and use its last instruction (just to avoid shifting the vector). @@ -598,14 +598,14 @@ AssignInstructionsToSlots(class SchedulingManager& S, unsigned maxIssue) chosenSlot = (int) s; break; } - + if (chosenSlot == -1) for (unsigned s=startSlot; s < S.nslots; s++) if ((*igroup)[s] == NULL && S.getChoicesForSlot(s).size() > 0) { chosenSlot = (int) s; break; } - + if (chosenSlot != -1) { // Insert the chosen instr in the chosen slot and // erase it from all slots. @@ -613,23 +613,23 @@ AssignInstructionsToSlots(class SchedulingManager& S, unsigned maxIssue) S.scheduleInstr(node, chosenSlot, curTime); } } - + assert(numIssued > 0 && "Should not happen when maxIssue > 0!"); } -// +// // For now, just assume we are scheduling within a single basic block. // Get the machine instruction vector for the basic block and clear it, // then append instructions in scheduled order. // Also, re-insert the dummy PHI instructions that were at the beginning // of the basic block, since they are not part of the schedule. -// +// static void RecordSchedule(MachineBasicBlock &MBB, const SchedulingManager& S) { const TargetInstrInfo& mii = S.schedInfo.getInstrInfo(); - + // Lets make sure we didn't lose any instructions, except possibly // some NOPs from delay slots. Also, PHIs are not included in the schedule. unsigned numInstr = 0; @@ -638,21 +638,21 @@ RecordSchedule(MachineBasicBlock &MBB, const SchedulingManager& S) ++numInstr; assert(S.isched.getNumInstructions() >= numInstr && "Lost some non-NOP instructions during scheduling!"); - + if (S.isched.getNumInstructions() == 0) return; // empty basic block! - + // First find the dummy instructions at the start of the basic block MachineBasicBlock::iterator I = MBB.begin(); for ( ; I != MBB.end(); ++I) if (I->getOpcode() != V9::PHI) break; - + // Remove all except the dummy PHI instructions from MBB, and // pre-allocate create space for the ones we will put back in. while (I != MBB.end()) MBB.remove(I++); - + InstrSchedule::const_iterator NIend = S.isched.end(); for (InstrSchedule::const_iterator NI = S.isched.begin(); NI != NIend; ++NI) MBB.push_back(const_cast<MachineInstr*>((*NI)->getMachineInstr())); @@ -665,7 +665,7 @@ MarkSuccessorsReady(SchedulingManager& S, const SchedGraphNode* node) { // Check if any successors are now ready that were not already marked // ready before, and that have not yet been scheduled. - // + // for (sg_succ_const_iterator SI = succ_begin(node); SI !=succ_end(node); ++SI) if (! (*SI)->isDummyNode() && ! S.isScheduled(*SI) @@ -690,18 +690,18 @@ MarkSuccessorsReady(SchedulingManager& S, const SchedGraphNode* node) // instruction to all possible slots that do not violate feasibility. // FEASIBLE means it should be guaranteed that the set // of chosen instructions can be issued in a single group. -// +// // Return value: // maxIssue : total number of feasible instructions // S.choicesForSlot[i=0..nslots] : set of instructions feasible in slot i -// +// static unsigned FindSlotChoices(SchedulingManager& S, DelaySlotInfo*& getDelaySlotInfo) { // initialize result vectors to empty S.resetChoices(); - + // find the slot to start from, in the current cycle unsigned int startSlot = 0; InstrGroup* igroup = S.isched.getIGroup(S.getTime()); @@ -710,7 +710,7 @@ FindSlotChoices(SchedulingManager& S, startSlot = s+1; break; } - + // Make sure we pick at most one instruction that would break the group. // Also, if we do pick one, remember which it was. unsigned int indexForBreakingNode = S.nslots; @@ -718,17 +718,17 @@ FindSlotChoices(SchedulingManager& S, DelaySlotInfo* delaySlotInfo = NULL; getDelaySlotInfo = NULL; - + // Choose instructions in order of priority. // Add choices to the choice vector in the SchedulingManager class as // we choose them so that subsequent choices will be correctly tested // for feasibility, w.r.t. higher priority choices for the same cycle. - // + // while (S.getNumChoices() < S.nslots - startSlot) { const SchedGraphNode* nextNode=S.schedPrio.getNextHighest(S,S.getTime()); if (nextNode == NULL) break; // no more instructions for this cycle - + if (S.getInstrInfo().getNumDelaySlots(nextNode->getOpcode()) > 0) { delaySlotInfo = S.getDelaySlotInfoForInstr(nextNode); if (delaySlotInfo != NULL) { @@ -746,34 +746,34 @@ FindSlotChoices(SchedulingManager& S, else indexForBreakingNode = S.getNumChoices(); } - + if (nextNode != NULL) { S.addChoice(nextNode); - + if (S.schedInfo.isSingleIssue(nextNode->getOpcode())) { assert(S.getNumChoices() == 1 && "Prioritizer returned invalid instr for this cycle!"); break; } } - + if (indexForDelayedInstr < S.nslots) break; // leave the rest for delay slots } - + assert(S.getNumChoices() <= S.nslots); assert(! (indexForDelayedInstr < S.nslots && indexForBreakingNode < S.nslots) && "Cannot have both in a cycle"); - + // Assign each chosen instruction to all possible slots for that instr. // But if only one instruction was chosen, put it only in the first // feasible slot; no more analysis will be needed. - // - if (indexForDelayedInstr >= S.nslots && + // + if (indexForDelayedInstr >= S.nslots && indexForBreakingNode >= S.nslots) { // No instructions that break the issue group or that have delay slots. // This is the common case, so handle it separately for efficiency. - + if (S.getNumChoices() == 1) { MachineOpCode opCode = S.getChoice(0)->getOpcode(); unsigned int s; @@ -795,19 +795,19 @@ FindSlotChoices(SchedulingManager& S, // Try to assign that instruction to a higher slot than any other // instructions in the group, so that its delay slots can go // right after it. - // + // assert(indexForDelayedInstr == S.getNumChoices() - 1 && "Instruction with delay slots should be last choice!"); assert(delaySlotInfo != NULL && "No delay slot info for instr?"); - + const SchedGraphNode* delayedNode = S.getChoice(indexForDelayedInstr); MachineOpCode delayOpCode = delayedNode->getOpcode(); unsigned ndelays= S.getInstrInfo().getNumDelaySlots(delayOpCode); - + unsigned delayedNodeSlot = S.nslots; int highestSlotUsed; - + // Find the last possible slot for the delayed instruction that leaves // at least `d' slots vacant after it (d = #delay slots) for (int s = S.nslots-ndelays-1; s >= (int) startSlot; s--) @@ -815,7 +815,7 @@ FindSlotChoices(SchedulingManager& S, delayedNodeSlot = s; break; } - + highestSlotUsed = -1; for (unsigned i=0; i < S.getNumChoices() - 1; i++) { // Try to assign every other instruction to a lower numbered @@ -828,7 +828,7 @@ FindSlotChoices(SchedulingManager& S, S.addChoiceToSlot(s, S.getChoice(i)); noSlotFound = false; } - + // No slot before `delayedNodeSlot' was found for this opCode // Use a later slot, and allow some delay slots to fall in // the next cycle. @@ -838,14 +838,14 @@ FindSlotChoices(SchedulingManager& S, S.addChoiceToSlot(s, S.getChoice(i)); break; } - + assert(s < S.nslots && "No feasible slot for instruction?"); - + highestSlotUsed = std::max(highestSlotUsed, (int) s); } - + assert(highestSlotUsed <= (int) S.nslots-1 && "Invalid slot used?"); - + // We will put the delayed node in the first slot after the // highest slot used. But we just mark that for now, and // schedule it separately because we want to schedule the delay @@ -867,7 +867,7 @@ FindSlotChoices(SchedulingManager& S, const SchedGraphNode* breakingNode=S.getChoice(indexForBreakingNode); unsigned breakingSlot = INT_MAX; unsigned int nslotsToUse = S.nslots; - + // Find the last possible slot for this instruction. for (int s = S.nslots-1; s >= (int) startSlot; s--) if (S.schedInfo.instrCanUseSlot(breakingNode->getOpcode(), s)) { @@ -876,7 +876,7 @@ FindSlotChoices(SchedulingManager& S, } assert(breakingSlot < S.nslots && "No feasible slot for `breakingNode'?"); - + // Higher priority instructions than the one that breaks the group: // These can be assigned to all slots, but will be assigned only // to earlier slots if possible. @@ -884,10 +884,10 @@ FindSlotChoices(SchedulingManager& S, i < S.getNumChoices() && i < indexForBreakingNode; i++) { MachineOpCode opCode =S.getChoice(i)->getOpcode(); - + // If a higher priority instruction cannot be assigned to // any earlier slots, don't schedule the breaking instruction. - // + // bool foundLowerSlot = false; nslotsToUse = S.nslots; // May be modified in the loop for (unsigned int s=startSlot; s < nslotsToUse; s++) @@ -896,14 +896,14 @@ FindSlotChoices(SchedulingManager& S, foundLowerSlot = true; nslotsToUse = breakingSlot; // RESETS LOOP UPPER BOUND! } - + S.addChoiceToSlot(s, S.getChoice(i)); } - + if (!foundLowerSlot) breakingSlot = INT_MAX; // disable breaking instr } - + // Assign the breaking instruction (if any) to a single slot // Otherwise, just ignore the instruction. It will simply be // scheduled in a later cycle. @@ -912,7 +912,7 @@ FindSlotChoices(SchedulingManager& S, nslotsToUse = breakingSlot; } else nslotsToUse = S.nslots; - + // For lower priority instructions than the one that breaks the // group, only assign them to slots lower than the breaking slot. // Otherwise, just ignore the instruction. @@ -923,7 +923,7 @@ FindSlotChoices(SchedulingManager& S, S.addChoiceToSlot(s, S.getChoice(i)); } } // endif (no delay slots and no breaking slots) - + return S.getNumChoices(); } @@ -933,23 +933,23 @@ ChooseOneGroup(SchedulingManager& S) { assert(S.schedPrio.getNumReady() > 0 && "Don't get here without ready instructions."); - + CycleCount_t firstCycle = S.getTime(); DelaySlotInfo* getDelaySlotInfo = NULL; - + // Choose up to `nslots' feasible instructions and their possible slots. unsigned numIssued = FindSlotChoices(S, getDelaySlotInfo); - + while (numIssued == 0) { S.updateTime(S.getTime()+1); numIssued = FindSlotChoices(S, getDelaySlotInfo); } - + AssignInstructionsToSlots(S, numIssued); - + if (getDelaySlotInfo != NULL) - numIssued += getDelaySlotInfo->scheduleDelayedNode(S); - + numIssued += getDelaySlotInfo->scheduleDelayedNode(S); + // Print trace of scheduled instructions before newly ready ones if (SchedDebugLevel >= Sched_PrintSchedTrace) { for (CycleCount_t c = firstCycle; c <= S.getTime(); c++) { @@ -964,7 +964,7 @@ ChooseOneGroup(SchedulingManager& S) } } } - + return numIssued; } @@ -974,23 +974,23 @@ ForwardListSchedule(SchedulingManager& S) { unsigned N; const SchedGraphNode* node; - + S.schedPrio.initialize(); - + while ((N = S.schedPrio.getNumReady()) > 0) { CycleCount_t nextCycle = S.getTime(); - + // Choose one group of instructions for a cycle, plus any delay slot // instructions (which may overflow into successive cycles). // This will advance S.getTime() to the last cycle in which // instructions are actually issued. - // + // unsigned numIssued = ChooseOneGroup(S); assert(numIssued > 0 && "Deadlock in list scheduling algorithm?"); - + // Notify the priority manager of scheduled instructions and mark // any successors that may now be ready - // + // for (CycleCount_t c = nextCycle; c <= S.getTime(); c++) { const InstrGroup* igroup = S.isched.getIGroup(c); for (unsigned int s=0; s < S.nslots; s++) @@ -999,11 +999,11 @@ ForwardListSchedule(SchedulingManager& S) MarkSuccessorsReady(S, node); } } - + // Move to the next the next earliest cycle for which // an instruction can be issued, or the next earliest in which // one will be ready, or to the next cycle, whichever is latest. - // + // S.updateTime(std::max(S.getTime() + 1, std::max(S.getEarliestIssueTime(), S.schedPrio.getEarliestReadyTime()))); @@ -1027,29 +1027,29 @@ NodeCanFillDelaySlot(const SchedulingManager& S, bool nodeIsPredecessor) { assert(! node->isDummyNode()); - + // don't put a branch in the delay slot of another branch if (S.getInstrInfo().isBranch(node->getOpcode())) return false; - + // don't put a single-issue instruction in the delay slot of a branch if (S.schedInfo.isSingleIssue(node->getOpcode())) return false; - + // don't put a load-use dependence in the delay slot of a branch const TargetInstrInfo& mii = S.getInstrInfo(); - + for (SchedGraphNode::const_iterator EI = node->beginInEdges(); EI != node->endInEdges(); ++EI) if (! ((SchedGraphNode*)(*EI)->getSrc())->isDummyNode() && mii.isLoad(((SchedGraphNode*)(*EI)->getSrc())->getOpcode()) && (*EI)->getDepType() == SchedGraphEdge::CtrlDep) return false; - + // Finally, if the instruction precedes the branch, we make sure the // instruction can be reordered relative to the branch. We simply check // if the instr. has only 1 outgoing edge, viz., a CD edge to the branch. - // + // if (nodeIsPredecessor) { bool onlyCDEdgeToBranch = true; for (SchedGraphNode::const_iterator OEI = node->beginOutEdges(); @@ -1061,11 +1061,11 @@ NodeCanFillDelaySlot(const SchedulingManager& S, onlyCDEdgeToBranch = false; break; } - + if (!onlyCDEdgeToBranch) return false; } - + return true; } @@ -1082,12 +1082,12 @@ MarkNodeForDelaySlot(SchedulingManager& S, // remove it and all its incident edges from the graph. Make sure we // add dummy edges for pred/succ nodes that become entry/exit nodes. graph->eraseIncidentEdges(node, /*addDummyEdges*/ true); - } else { + } else { // If the node was from a target block, add the node to the graph // and add a CD edge from brNode to node. assert(0 && "NOT IMPLEMENTED YET"); } - + DelaySlotInfo* dinfo = S.getDelaySlotInfoForInstr(brNode, /*create*/ true); dinfo->addDelayNode(node); } @@ -1101,17 +1101,17 @@ FindUsefulInstructionsForDelaySlots(SchedulingManager& S, const TargetInstrInfo& mii = S.getInstrInfo(); unsigned ndelays = mii.getNumDelaySlots(brNode->getOpcode()); - + if (ndelays == 0) return; - + sdelayNodeVec.reserve(ndelays); - + // Use a separate vector to hold the feasible multi-cycle nodes. // These will be used if not enough single-cycle nodes are found. - // + // std::vector<SchedGraphNode*> mdelayNodeVec; - + for (sg_pred_iterator P = pred_begin(brNode); P != pred_end(brNode) && sdelayNodeVec.size() < ndelays; ++P) if (! (*P)->isDummyNode() && @@ -1123,19 +1123,19 @@ FindUsefulInstructionsForDelaySlots(SchedulingManager& S, else sdelayNodeVec.push_back(*P); } - + // If not enough single-cycle instructions were found, select the // lowest-latency multi-cycle instructions and use them. // Note that this is the most efficient code when only 1 (or even 2) // values need to be selected. - // + // while (sdelayNodeVec.size() < ndelays && mdelayNodeVec.size() > 0) { unsigned lmin = mii.maxLatency(mdelayNodeVec[0]->getOpcode()); unsigned minIndex = 0; for (unsigned i=1; i < mdelayNodeVec.size(); i++) { - unsigned li = + unsigned li = mii.maxLatency(mdelayNodeVec[i]->getOpcode()); if (lmin >= li) { @@ -1154,7 +1154,7 @@ FindUsefulInstructionsForDelaySlots(SchedulingManager& S, // Mark instructions specified in sdelayNodeVec to replace them. // If not enough useful instructions were found, mark the NOPs to be used // for filling delay slots, otherwise, otherwise just discard them. -// +// static void ReplaceNopsWithUsefulInstr(SchedulingManager& S, SchedGraphNode* node, // FIXME: passing vector BY VALUE!!! @@ -1166,11 +1166,11 @@ static void ReplaceNopsWithUsefulInstr(SchedulingManager& S, const MachineInstr* brInstr = node->getMachineInstr(); unsigned ndelays= mii.getNumDelaySlots(brInstr->getOpcode()); assert(ndelays > 0 && "Unnecessary call to replace NOPs"); - + // Remove the NOPs currently in delay slots from the graph. // If not enough useful instructions were found, use the NOPs to // fill delay slots, otherwise, just discard them. - // + // unsigned int firstDelaySlotIdx = node->getOrigIndexInBB() + 1; MachineBasicBlock& MBB = node->getMachineBasicBlock(); MachineBasicBlock::iterator MBBI = MBB.begin(); |