-// $Id$
-//***************************************************************************
-// File:
-// InstrScheduling.cpp
+//===- InstrScheduling.cpp - Generic Instruction Scheduling support -------===//
//
-// Purpose:
-//
-// History:
-// 7/23/01 - Vikram Adve - Created
-//***************************************************************************
-
-#include "llvm/CodeGen/InstrScheduling.h"
-#include "llvm/CodeGen/SchedPriorities.h"
-#include "llvm/Analysis/LiveVar/BBLiveVar.h"
-#include "llvm/Target/Machine.h"
+// 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
+// generic support routines for instruction scheduling.
+//
+//===----------------------------------------------------------------------===//
+
+#include "SchedPriorities.h"
#include "llvm/CodeGen/MachineInstr.h"
-#include "llvm/Support/CommandLine.h"
-#include "llvm/Instruction.h"
-#include <hash_set>
+#include "llvm/CodeGen/MachineCodeForInstruction.h"
+#include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/CodeGen/FunctionLiveVarInfo.h"
+#include "llvm/Target/TargetMachine.h"
+#include "llvm/BasicBlock.h"
+#include "Support/CommandLine.h"
#include <algorithm>
-#include <iterator>
-
-cl::Enum<enum SchedDebugLevel_t> SchedDebugLevel("dsched", cl::NoFlags,
- "enable instruction scheduling debugging information",
- clEnumValN(Sched_NoDebugInfo, "n", "disable debug output"),
- clEnumValN(Sched_PrintMachineCode, "y", "print machine code after scheduling"),
- clEnumValN(Sched_PrintSchedTrace, "t", "print trace of scheduling actions"),
- clEnumValN(Sched_PrintSchedGraphs, "g", "print scheduling graphs"), 0);
-
-
-//************************* Forward Declarations ***************************/
-
-class InstrSchedule;
-class SchedulingManager;
-class DelaySlotInfo;
-
-static void ForwardListSchedule (SchedulingManager& S);
-
-static void RecordSchedule (const BasicBlock* bb,
- const SchedulingManager& S);
-
-static unsigned ChooseOneGroup (SchedulingManager& S);
-
-static void MarkSuccessorsReady (SchedulingManager& S,
- const SchedGraphNode* node);
-
-static unsigned FindSlotChoices (SchedulingManager& S,
- DelaySlotInfo*& getDelaySlotInfo);
-
-static void AssignInstructionsToSlots(class SchedulingManager& S,
- unsigned maxIssue);
-
-static void ScheduleInstr (class SchedulingManager& S,
- const SchedGraphNode* node,
- unsigned int slotNum,
- cycles_t curTime);
-static bool ViolatesMinimumGap (const SchedulingManager& S,
- MachineOpCode opCode,
- const cycles_t inCycle);
+namespace llvm {
-static bool ConflictsWithChoices (const SchedulingManager& S,
- MachineOpCode opCode);
+SchedDebugLevel_t SchedDebugLevel;
-static void ChooseInstructionsForDelaySlots(SchedulingManager& S,
- const BasicBlock* bb,
- SchedGraph* graph);
+static cl::opt<bool> EnableFillingDelaySlots("sched-fill-delay-slots",
+ cl::desc("Fill branch delay slots during local scheduling"));
-static bool NodeCanFillDelaySlot (const SchedulingManager& S,
- const SchedGraphNode* node,
- const SchedGraphNode* brNode,
- bool nodeIsPredecessor);
+static cl::opt<SchedDebugLevel_t, true>
+SDL_opt("dsched", cl::Hidden, cl::location(SchedDebugLevel),
+ cl::desc("enable instruction scheduling debugging information"),
+ cl::values(
+ clEnumValN(Sched_NoDebugInfo, "n", "disable debug output"),
+ clEnumValN(Sched_PrintMachineCode, "y", "print machine code after scheduling"),
+ clEnumValN(Sched_PrintSchedTrace, "t", "print trace of scheduling actions"),
+ clEnumValN(Sched_PrintSchedGraphs, "g", "print scheduling graphs"),
+ 0));
-static void MarkNodeForDelaySlot (SchedulingManager& S,
- SchedGraphNode* node,
- const SchedGraphNode* brNode,
- bool nodeIsPredecessor);
//************************* Internal Data Types *****************************/
+class InstrSchedule;
+class SchedulingManager;
+
//----------------------------------------------------------------------
// class InstrGroup:
// in a single cycle.
//----------------------------------------------------------------------
-class InstrGroup: public NonCopyable {
+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());
/*ctor*/ InstrGroup(); // disable: DO NOT IMPLEMENT
private:
- vector<const SchedGraphNode*> group;
+ std::vector<const SchedGraphNode*> group;
};
//----------------------------------------------------------------------
template<class _NodeType>
-class ScheduleIterator: public std::forward_iterator<_NodeType, ptrdiff_t> {
+class ScheduleIterator : public forward_iterator<_NodeType, ptrdiff_t> {
private:
unsigned cycleNum;
unsigned slotNum;
inline bool operator!=(const _Self& x) const { return !operator==(x); }
- inline _NodeType* operator*() const {
- assert(cycleNum < S.groups.size());
- return (*S.groups[cycleNum])[slotNum];
- }
+ inline _NodeType* operator*() const;
inline _NodeType* operator->() const { return operator*(); }
_Self& operator++(); // Preincrement
// Represents the schedule of machine instructions for a single basic block.
//----------------------------------------------------------------------
-class InstrSchedule: public NonCopyable {
-private:
+class InstrSchedule {
const unsigned int nslots;
unsigned int numInstr;
- vector<InstrGroup*> groups; // indexed by cycle number
- vector<cycles_t> startTime; // indexed by node id
+ std::vector<InstrGroup*> groups; // indexed by cycle number
+ std::vector<cycles_t> startTime; // indexed by node id
+
+ 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();
- const_iterator begin() const;
- iterator end();
- const_iterator end() const;
+ 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,
}
inline InstrGroup* getIGroup (cycles_t c) {
- if (c >= groups.size())
+ if ((unsigned)c >= groups.size())
groups.resize(c+1);
if (groups[c] == NULL)
groups[c] = new InstrGroup(nslots);
}
inline const InstrGroup* getIGroup (cycles_t c) const {
- assert(c < groups.size());
+ assert((unsigned)c < groups.size());
return groups[c];
}
}
private:
- friend class iterator;
- friend class const_iterator;
+ friend class ScheduleIterator<SchedGraphNode>;
+ friend class ScheduleIterator<const SchedGraphNode>;
/*ctor*/ InstrSchedule (); // Disable: DO NOT IMPLEMENT.
};
+template<class NodeType>
+inline NodeType *ScheduleIterator<NodeType>::operator*() const {
+ assert(cycleNum < S.groups.size());
+ return (*S.groups[cycleNum])[slotNum];
+}
+
/*ctor*/
InstrSchedule::InstrSchedule(unsigned int _nslots, unsigned int _numNodes)
while (cycleNum < S.groups.size() &&
(*S.groups[cycleNum])[slotNum] == NULL)
- {
- ++slotNum;
- if (slotNum == S.nslots)
- {
- ++cycleNum;
- slotNum = 0;
- while(cycleNum < S.groups.size() && S.groups[cycleNum] == NULL)
- ++cycleNum; // skip cycles with no instructions
- }
+ {
+ ++slotNum;
+ if (slotNum == S.nslots) {
+ ++cycleNum;
+ slotNum = 0;
+ while(cycleNum < S.groups.size() && S.groups[cycleNum] == NULL)
+ ++cycleNum; // skip cycles with no instructions
}
+ }
}
template<class _NodeType>
ScheduleIterator<_NodeType>::operator++() // Preincrement
{
++slotNum;
- if (slotNum == S.nslots)
- {
- ++cycleNum;
- slotNum = 0;
- }
+ if (slotNum == S.nslots) {
+ ++cycleNum;
+ slotNum = 0;
+ }
skipToNextInstr();
return *this;
}
return _Self(_schedule, _schedule.groups.size(), 0);
}
-InstrSchedule::iterator
-InstrSchedule::begin()
-{
- return iterator::begin(*this);
-}
-
-InstrSchedule::const_iterator
-InstrSchedule::begin() const
-{
- return const_iterator::begin(*this);
-}
-
-InstrSchedule::iterator
-InstrSchedule::end()
-{
- return iterator::end(*this);
-}
-
-InstrSchedule::const_iterator
-InstrSchedule::end() const
-{
- return const_iterator::end( *this);
-}
-
//----------------------------------------------------------------------
// class DelaySlotInfo:
// Delay slots are simply indexed by slot number 1 ... numDelaySlots
//----------------------------------------------------------------------
-class DelaySlotInfo: public NonCopyable {
-private:
+class DelaySlotInfo {
const SchedGraphNode* brNode;
- unsigned int ndelays;
- vector<const SchedGraphNode*> delayNodeVec;
+ unsigned ndelays;
+ std::vector<const SchedGraphNode*> delayNodeVec;
cycles_t delayedNodeCycle;
- unsigned int delayedNodeSlotNum;
+ unsigned delayedNodeSlotNum;
+ DelaySlotInfo(const DelaySlotInfo &); // DO NOT IMPLEMENT
+ void operator=(const DelaySlotInfo&); // DO NOT IMPLEMENT
public:
/*ctor*/ DelaySlotInfo (const SchedGraphNode* _brNode,
unsigned _ndelays)
return ndelays;
}
- inline const vector<const SchedGraphNode*>& getDelayNodeVec() {
+ inline const std::vector<const SchedGraphNode*>& getDelayNodeVec() {
return delayNodeVec;
}
delayedNodeSlotNum = slotNum;
}
- void scheduleDelayedNode (SchedulingManager& S);
+ unsigned scheduleDelayedNode (SchedulingManager& S);
};
// Represents the schedule of machine instructions for a single basic block.
//----------------------------------------------------------------------
-class SchedulingManager: public NonCopyable {
+class SchedulingManager {
+ SchedulingManager(SchedulingManager &); // DO NOT IMPLEMENT
+ void operator=(const SchedulingManager &); // DO NOT IMPLEMENT
public: // publicly accessible data members
- const unsigned int nslots;
- const MachineSchedInfo& schedInfo;
+ const unsigned nslots;
+ const TargetSchedInfo& schedInfo;
SchedPriorities& schedPrio;
InstrSchedule isched;
private:
- unsigned int totalInstrCount;
+ unsigned totalInstrCount;
cycles_t curTime;
cycles_t nextEarliestIssueTime; // next cycle we can issue
- vector<hash_set<const SchedGraphNode*> > choicesForSlot; // indexed by slot#
- vector<const SchedGraphNode*> choiceVec; // indexed by node ptr
- vector<int> numInClass; // indexed by sched class
- vector<cycles_t> nextEarliestStartTime; // indexed by opCode
+ // indexed by slot#
+ std::vector<hash_set<const SchedGraphNode*> > choicesForSlot;
+ std::vector<const SchedGraphNode*> choiceVec; // indexed by node ptr
+ std::vector<int> numInClass; // indexed by sched class
+ std::vector<cycles_t> nextEarliestStartTime; // indexed by opCode
hash_map<const SchedGraphNode*, DelaySlotInfo*> delaySlotInfoForBranches;
// indexed by branch node ptr
public:
- /*ctor*/ SchedulingManager (const TargetMachine& _target,
- const MachineSchedInfo &schedinfo,
- const SchedGraph* graph,
- SchedPriorities& schedPrio);
- /*dtor*/ ~SchedulingManager () {}
+ SchedulingManager(const TargetMachine& _target, const SchedGraph* graph,
+ SchedPriorities& schedPrio);
+ ~SchedulingManager() {
+ for (hash_map<const SchedGraphNode*,
+ DelaySlotInfo*>::iterator I = delaySlotInfoForBranches.begin(),
+ E = delaySlotInfoForBranches.end(); I != E; ++I)
+ delete I->second;
+ }
//----------------------------------------------------------------------
// Simplify access to the machine instruction info
//----------------------------------------------------------------------
- inline const MachineInstrInfo& getInstrInfo () const {
+ inline const TargetInstrInfo& getInstrInfo () const {
return schedInfo.getInstrInfo();
}
}
inline unsigned getNumChoicesInClass (const InstrSchedClass& sc) const {
- assert(sc < (int) numInClass.size() && "Invalid op code or sched class!");
+ assert(sc < numInClass.size() && "Invalid op code or sched class!");
return numInClass[sc];
}
// Append the instruction to the vector of choices for current cycle.
// Increment numInClass[c] for the sched class to which the instr belongs.
choiceVec.push_back(node);
- const InstrSchedClass& sc = schedInfo.getSchedClass(node->getMachineInstr()->getOpCode());
- assert(sc < (int) numInClass.size());
+ const InstrSchedClass& sc = schedInfo.getSchedClass(node->getOpcode());
+ assert(sc < numInClass.size());
numInClass[sc]++;
}
choicesForSlot[s].erase(node);
// and decrement the instr count for the sched class to which it belongs
- const InstrSchedClass& sc = schedInfo.getSchedClass(node->getMachineInstr()->getOpCode());
- assert(sc < (int) numInClass.size());
+ const InstrSchedClass& sc = schedInfo.getSchedClass(node->getOpcode());
+ assert(sc < numInClass.size());
numInClass[sc]--;
}
inline DelaySlotInfo* getDelaySlotInfoForInstr(const SchedGraphNode* bn,
bool createIfMissing=false)
{
- DelaySlotInfo* dinfo;
- hash_map<const SchedGraphNode*, DelaySlotInfo* >::const_iterator
+ hash_map<const SchedGraphNode*, DelaySlotInfo*>::const_iterator
I = delaySlotInfoForBranches.find(bn);
- if (I == delaySlotInfoForBranches.end())
- {
- if (createIfMissing)
- {
- dinfo = new DelaySlotInfo(bn,
- getInstrInfo().getNumDelaySlots(bn->getMachineInstr()->getOpCode()));
- delaySlotInfoForBranches[bn] = dinfo;
- }
- else
- dinfo = NULL;
- }
- else
- dinfo = (*I).second;
-
- return dinfo;
+ if (I != delaySlotInfoForBranches.end())
+ return I->second;
+
+ if (!createIfMissing) return 0;
+
+ DelaySlotInfo *dinfo =
+ new DelaySlotInfo(bn, getInstrInfo().getNumDelaySlots(bn->getOpcode()));
+ return delaySlotInfoForBranches[bn] = dinfo;
}
private:
- /*ctor*/ SchedulingManager (); // Disable: DO NOT IMPLEMENT.
- void updateEarliestStartTimes(const SchedGraphNode* node,
- cycles_t schedTime);
+ SchedulingManager(); // DISABLED: DO NOT IMPLEMENT
+ void updateEarliestStartTimes(const SchedGraphNode* node, cycles_t schedTime);
};
/*ctor*/
SchedulingManager::SchedulingManager(const TargetMachine& target,
- const MachineSchedInfo &schedinfo,
const SchedGraph* graph,
SchedPriorities& _schedPrio)
- : nslots(schedinfo.getMaxNumIssueTotal()),
- schedInfo(schedinfo),
+ : nslots(target.getSchedInfo().getMaxNumIssueTotal()),
+ schedInfo(target.getSchedInfo()),
schedPrio(_schedPrio),
isched(nslots, graph->getNumNodes()),
totalInstrCount(graph->getNumNodes() - 2),
nextEarliestIssueTime(0),
choicesForSlot(nslots),
- numInClass(schedinfo.getNumSchedClasses(), 0), // set all to 0
+ numInClass(target.getSchedInfo().getNumSchedClasses(), 0), // set all to 0
nextEarliestStartTime(target.getInstrInfo().getNumRealOpCodes(),
(cycles_t) 0) // set all to 0
{
SchedulingManager::updateEarliestStartTimes(const SchedGraphNode* node,
cycles_t schedTime)
{
- if (schedInfo.numBubblesAfter(node->getMachineInstr()->getOpCode()) > 0)
+ if (schedInfo.numBubblesAfter(node->getOpcode()) > 0)
{ // Update next earliest time before which *nothing* can issue.
- nextEarliestIssueTime = max(nextEarliestIssueTime,
- curTime + 1 + schedInfo.numBubblesAfter(node->getMachineInstr()->getOpCode()));
- }
-
- const vector<MachineOpCode>*
- conflictVec = schedInfo.getConflictList(node->getMachineInstr()->getOpCode());
-
- if (conflictVec != NULL)
- for (unsigned i=0; i < conflictVec->size(); i++)
- {
- MachineOpCode toOp = (*conflictVec)[i];
- cycles_t est = schedTime + schedInfo.getMinIssueGap(node->getMachineInstr()->getOpCode(),
- toOp);
- assert(toOp < (int) nextEarliestStartTime.size());
- if (nextEarliestStartTime[toOp] < est)
- nextEarliestStartTime[toOp] = est;
- }
-}
-
-//************************* External Functions *****************************/
-
-
-//---------------------------------------------------------------------------
-// Function: ScheduleInstructionsWithSSA
-//
-// Purpose:
-// Entry point for instruction scheduling on SSA form.
-// Schedules the machine instructions generated by instruction selection.
-// Assumes that register allocation has not been done, i.e., operands
-// are still in SSA form.
-//---------------------------------------------------------------------------
-
-bool ScheduleInstructionsWithSSA(Method* method, const TargetMachine &target,
- const MachineSchedInfo &schedInfo) {
- SchedGraphSet graphSet(method, target);
-
- if (SchedDebugLevel >= Sched_PrintSchedGraphs)
- {
- cout << endl << "*** SCHEDULING GRAPHS FOR INSTRUCTION SCHEDULING"
- << endl;
- graphSet.dump();
+ nextEarliestIssueTime = std::max(nextEarliestIssueTime,
+ curTime + 1 + schedInfo.numBubblesAfter(node->getOpcode()));
}
- for (SchedGraphSet::const_iterator GI=graphSet.begin();
- GI != graphSet.end(); ++GI)
- {
- SchedGraph* graph = (*GI).second;
- const vector<const BasicBlock*>& bbvec = graph->getBasicBlocks();
- assert(bbvec.size() == 1 && "Cannot schedule multiple basic blocks");
- const BasicBlock* bb = bbvec[0];
-
- if (SchedDebugLevel >= Sched_PrintSchedTrace)
- cout << endl << "*** TRACE OF INSTRUCTION SCHEDULING OPERATIONS\n\n";
-
- SchedPriorities schedPrio(method, graph); // expensive!
- SchedulingManager S(target, schedInfo, graph, schedPrio);
-
- ChooseInstructionsForDelaySlots(S, bb, graph); // modifies graph
-
- ForwardListSchedule(S); // computes schedule in S
-
- RecordSchedule((*GI).first, S); // records schedule in BB
- }
+ const std::vector<MachineOpCode>&
+ conflictVec = schedInfo.getConflictList(node->getOpcode());
- if (SchedDebugLevel >= Sched_PrintMachineCode)
+ for (unsigned i=0; i < conflictVec.size(); i++)
{
- cout << endl
- << "*** Machine instructions after INSTRUCTION SCHEDULING" << endl;
- PrintMachineInstructions(method);
+ MachineOpCode toOp = conflictVec[i];
+ cycles_t est=schedTime + schedInfo.getMinIssueGap(node->getOpcode(),toOp);
+ assert(toOp < (int) nextEarliestStartTime.size());
+ if (nextEarliestStartTime[toOp] < est)
+ nextEarliestStartTime[toOp] = est;
}
-
- return false; // no reason to fail yet
-}
-
-
-// Check minimum gap requirements relative to instructions scheduled in
-// previous cycles.
-// Note that we do not need to consider `nextEarliestIssueTime' here because
-// that is also captured in the earliest start times for each opcode.
-//
-static inline bool
-ViolatesMinimumGap(const SchedulingManager& S,
- MachineOpCode opCode,
- const cycles_t inCycle)
-{
- return (inCycle < S.getEarliestStartTimeForOp(opCode));
-}
-
-
-// Check if the instruction would conflict with instructions already
-// chosen for the current cycle
-//
-static inline bool
-ConflictsWithChoices(const SchedulingManager& S,
- MachineOpCode opCode)
-{
- // Check if the instruction must issue by itself, and some feasible
- // choices have already been made for this cycle
- if (S.getNumChoices() > 0 && S.schedInfo.isSingleIssue(opCode))
- return true;
-
- // For each class that opCode belongs to, check if there are too many
- // instructions of that class.
- //
- const InstrSchedClass sc = S.schedInfo.getSchedClass(opCode);
- return (S.getNumChoicesInClass(sc) == S.schedInfo.getMaxIssueForClass(sc));
-}
-
-
-// Check if any issue restrictions would prevent the instruction from
-// being issued in the current cycle
-//
-bool
-instrIsFeasible(const SchedulingManager& S,
- MachineOpCode opCode)
-{
- // skip the instruction if it cannot be issued due to issue restrictions
- // caused by previously issued instructions
- if (ViolatesMinimumGap(S, opCode, S.getTime()))
- return false;
-
- // skip the instruction if it cannot be issued due to issue restrictions
- // caused by previously chosen instructions for the current cycle
- if (ConflictsWithChoices(S, opCode))
- return false;
-
- return true;
}
//************************* Internal Functions *****************************/
static void
-ForwardListSchedule(SchedulingManager& S)
+AssignInstructionsToSlots(class SchedulingManager& S, unsigned maxIssue)
{
- unsigned N;
- const SchedGraphNode* node;
+ // find the slot to start from, in the current cycle
+ unsigned int startSlot = 0;
+ cycles_t curTime = S.getTime();
- S.schedPrio.initialize();
+ assert(maxIssue > 0 && maxIssue <= S.nslots - startSlot);
- while ((N = S.schedPrio.getNumReady()) > 0)
- {
- // Choose one group of instructions for a cycle. This will
- // advance S.getTime() to the first cycle instructions can be issued.
- // It may also schedule delay slot instructions in later cycles,
- // but those are ignored here because they are outside the graph.
- //
- unsigned numIssued = ChooseOneGroup(S);
- assert(numIssued > 0 && "Deadlock in list scheduling algorithm?");
+ // If only one instruction can be issued, do so.
+ if (maxIssue == 1)
+ for (unsigned s=startSlot; s < S.nslots; s++)
+ if (S.getChoicesForSlot(s).size() > 0) {
+ // found the one instruction
+ 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).
+ unsigned numIssued;
+ for (numIssued = 0; numIssued < maxIssue; numIssued++) {
+ int chosenSlot = -1;
+ for (unsigned s=startSlot; s < S.nslots; s++)
+ if ((*igroup)[s] == NULL && S.getChoicesForSlot(s).size() == 1) {
+ chosenSlot = (int) s;
+ break;
+ }
- // Notify the priority manager of scheduled instructions and mark
- // any successors that may now be ready
- //
- const InstrGroup* igroup = S.isched.getIGroup(S.getTime());
- for (unsigned int s=0; s < S.nslots; s++)
- if ((node = (*igroup)[s]) != NULL)
- {
- S.schedPrio.issuedReadyNodeAt(S.getTime(), node);
- MarkSuccessorsReady(S, node);
- }
+ if (chosenSlot == -1)
+ for (unsigned s=startSlot; s < S.nslots; s++)
+ if ((*igroup)[s] == NULL && S.getChoicesForSlot(s).size() > 0) {
+ chosenSlot = (int) s;
+ break;
+ }
- // 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(max(S.getTime() + 1,
- max(S.getEarliestIssueTime(),
- S.schedPrio.getEarliestReadyTime())));
+ if (chosenSlot != -1) {
+ // Insert the chosen instr in the chosen slot and
+ // erase it from all slots.
+ const SchedGraphNode* node= *S.getChoicesForSlot(chosenSlot).begin();
+ S.scheduleInstr(node, chosenSlot, curTime);
}
+ }
+
+ assert(numIssued > 0 && "Should not happen when maxIssue > 0!");
}
// of the basic block, since they are not part of the schedule.
//
static void
-RecordSchedule(const BasicBlock* bb, const SchedulingManager& S)
+RecordSchedule(MachineBasicBlock &MBB, const SchedulingManager& S)
{
+ const TargetInstrInfo& mii = S.schedInfo.getInstrInfo();
+
+#ifndef NDEBUG
+ // 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;
+ for (MachineBasicBlock::iterator I=MBB.begin(); I != MBB.end(); ++I)
+ if (! mii.isNop(I->getOpcode()) &&
+ ! mii.isDummyPhiInstr(I->getOpcode()))
+ ++numInstr;
+ assert(S.isched.getNumInstructions() >= numInstr &&
+ "Lost some non-NOP instructions during scheduling!");
+#endif
+
if (S.isched.getNumInstructions() == 0)
return; // empty basic block!
- MachineCodeForBasicBlock& mvec = bb->getMachineInstrVec();
- unsigned int oldSize = mvec.size();
-
// First find the dummy instructions at the start of the basic block
- const MachineInstrInfo& mii = S.schedInfo.getInstrInfo();
- MachineCodeForBasicBlock::iterator I = mvec.begin();
- for ( ; I != mvec.end(); ++I)
- if (! mii.isDummyPhiInstr((*I)->getOpCode()))
+ MachineBasicBlock::iterator I = MBB.begin();
+ for ( ; I != MBB.end(); ++I)
+ if (! mii.isDummyPhiInstr(I->getOpcode()))
break;
- // Erase all except the dummy PHI instructions from mvec, and
- // pre-allocate create space for the ones we will be put back in.
- mvec.erase(I, mvec.end());
- mvec.reserve(mvec.size() + S.isched.getNumInstructions());
+ // 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)
- mvec.push_back(const_cast<MachineInstr*>((*NI)->getMachineInstr()));
+ MBB.push_back(const_cast<MachineInstr*>((*NI)->getMachineInstr()));
}
-static unsigned
-ChooseOneGroup(SchedulingManager& S)
-{
- assert(S.schedPrio.getNumReady() > 0
- && "Don't get here without ready instructions.");
-
- DelaySlotInfo* getDelaySlotInfo;
-
- // 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)
- getDelaySlotInfo->scheduleDelayedNode(S);
-
- // Print trace of scheduled instructions before newly ready ones
- if (SchedDebugLevel >= Sched_PrintSchedTrace)
- {
- cout << " Cycle " << S.getTime() << " : Scheduled instructions:\n";
- const InstrGroup* igroup = S.isched.getIGroup(S.getTime());
- for (unsigned int s=0; s < S.nslots; s++)
- {
- cout << " ";
- if ((*igroup)[s] != NULL)
- cout << * ((*igroup)[s])->getMachineInstr() << endl;
- else
- cout << "<none>" << endl;
- }
- }
-
- return numIssued;
-}
-
static void
MarkSuccessorsReady(SchedulingManager& S, const SchedGraphNode* node)
if (! (*SI)->isDummyNode()
&& ! S.isScheduled(*SI)
&& ! S.schedPrio.nodeIsReady(*SI))
- {// successor not scheduled and not marked ready; check *its* preds.
+ {
+ // successor not scheduled and not marked ready; check *its* preds.
- bool succIsReady = true;
- for (sg_pred_const_iterator P=pred_begin(*SI); P != pred_end(*SI); ++P)
- if (! (*P)->isDummyNode()
- && ! S.isScheduled(*P))
- {
- succIsReady = false;
- break;
- }
+ bool succIsReady = true;
+ for (sg_pred_const_iterator P=pred_begin(*SI); P != pred_end(*SI); ++P)
+ if (! (*P)->isDummyNode() && ! S.isScheduled(*P)) {
+ succIsReady = false;
+ break;
+ }
- if (succIsReady) // add the successor to the ready list
- S.schedPrio.insertReady(*SI);
- }
+ if (succIsReady) // add the successor to the ready list
+ S.schedPrio.insertReady(*SI);
+ }
}
unsigned int startSlot = 0;
InstrGroup* igroup = S.isched.getIGroup(S.getTime());
for (int s = S.nslots - 1; s >= 0; s--)
- if ((*igroup)[s] != NULL)
- {
- startSlot = s+1;
- break;
- }
+ if ((*igroup)[s] != NULL) {
+ 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.
// 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->getMachineInstr()->getOpCode()) > 0)
- {
- delaySlotInfo = S.getDelaySlotInfoForInstr(nextNode);
- if (delaySlotInfo != NULL)
- {
- if (indexForBreakingNode < S.nslots)
- // cannot issue a delayed instr in the same cycle as one
- // that breaks the issue group or as another delayed instr
- nextNode = NULL;
- else
- indexForDelayedInstr = S.getNumChoices();
- }
- }
- else if (S.schedInfo.breaksIssueGroup(nextNode->getMachineInstr()->getOpCode()))
- {
- if (indexForBreakingNode < S.nslots)
- // have a breaking instruction already so throw this one away
- nextNode = NULL;
- else
- indexForBreakingNode = S.getNumChoices();
- }
+ 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 (nextNode != NULL)
- S.addChoice(nextNode);
+ if (S.getInstrInfo().getNumDelaySlots(nextNode->getOpcode()) > 0) {
+ delaySlotInfo = S.getDelaySlotInfoForInstr(nextNode);
+ if (delaySlotInfo != NULL) {
+ if (indexForBreakingNode < S.nslots)
+ // cannot issue a delayed instr in the same cycle as one
+ // that breaks the issue group or as another delayed instr
+ nextNode = NULL;
+ else
+ indexForDelayedInstr = S.getNumChoices();
+ }
+ } else if (S.schedInfo.breaksIssueGroup(nextNode->getOpcode())) {
+ if (indexForBreakingNode < S.nslots)
+ // have a breaking instruction already so throw this one away
+ nextNode = NULL;
+ else
+ indexForBreakingNode = S.getNumChoices();
+ }
- if (S.schedInfo.isSingleIssue(nextNode->getMachineInstr()->getOpCode()))
- {
- assert(S.getNumChoices() == 1 &&
- "Prioritizer returned invalid instr for this cycle!");
- break;
- }
+ if (nextNode != NULL) {
+ S.addChoice(nextNode);
- if (indexForDelayedInstr < S.nslots)
- break; // leave the rest for delay slots
+ 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 &&
//
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.
+ { // 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)->getMachineInstr()->getOpCode();
- unsigned int s;
- for (s=startSlot; s < S.nslots; s++)
- if (S.schedInfo.instrCanUseSlot(opCode, s))
- break;
- assert(s < S.nslots && "No feasible slot for this opCode?");
- S.addChoiceToSlot(s, S.getChoice(0));
- }
- else
- {
- for (unsigned i=0; i < S.getNumChoices(); i++)
- {
- MachineOpCode opCode = S.getChoice(i)->getMachineInstr()->getOpCode();
- for (unsigned int s=startSlot; s < S.nslots; s++)
- if (S.schedInfo.instrCanUseSlot(opCode, s))
- S.addChoiceToSlot(s, S.getChoice(i));
- }
- }
+ if (S.getNumChoices() == 1) {
+ MachineOpCode opCode = S.getChoice(0)->getOpcode();
+ unsigned int s;
+ for (s=startSlot; s < S.nslots; s++)
+ if (S.schedInfo.instrCanUseSlot(opCode, s))
+ break;
+ assert(s < S.nslots && "No feasible slot for this opCode?");
+ S.addChoiceToSlot(s, S.getChoice(0));
+ } else {
+ for (unsigned i=0; i < S.getNumChoices(); i++) {
+ MachineOpCode opCode = S.getChoice(i)->getOpcode();
+ for (unsigned int s=startSlot; s < S.nslots; s++)
+ if (S.schedInfo.instrCanUseSlot(opCode, s))
+ S.addChoiceToSlot(s, S.getChoice(i));
+ }
}
- else if (indexForDelayedInstr < S.nslots)
- {
- // There is an instruction that needs delay slots.
- // 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?");
+ } else if (indexForDelayedInstr < S.nslots) {
+ // There is an instruction that needs delay slots.
+ // 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->getMachineInstr()->getOpCode();
- unsigned ndelays= S.getInstrInfo().getNumDelaySlots(delayOpCode);
+ const SchedGraphNode* delayedNode = S.getChoice(indexForDelayedInstr);
+ MachineOpCode delayOpCode = delayedNode->getOpcode();
+ unsigned ndelays= S.getInstrInfo().getNumDelaySlots(delayOpCode);
- unsigned delayedNodeSlot = S.nslots;
- int highestSlotUsed;
+ 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--)
- if (S.schedInfo.instrCanUseSlot(delayOpCode, s))
- {
- delayedNodeSlot = s;
- break;
- }
+ // 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--)
+ if (S.schedInfo.instrCanUseSlot(delayOpCode, 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
- // slot than delayedNodeSlot.
- MachineOpCode opCode = S.getChoice(i)->getMachineInstr()->getOpCode();
- bool noSlotFound = true;
- unsigned int s;
- for (s=startSlot; s < delayedNodeSlot; s++)
- if (S.schedInfo.instrCanUseSlot(opCode, s))
- {
- S.addChoiceToSlot(s, S.getChoice(i));
- noSlotFound = false;
- }
+ highestSlotUsed = -1;
+ for (unsigned i=0; i < S.getNumChoices() - 1; i++) {
+ // Try to assign every other instruction to a lower numbered
+ // slot than delayedNodeSlot.
+ MachineOpCode opCode =S.getChoice(i)->getOpcode();
+ bool noSlotFound = true;
+ unsigned int s;
+ for (s=startSlot; s < delayedNodeSlot; s++)
+ if (S.schedInfo.instrCanUseSlot(opCode, 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.
- if (noSlotFound)
- for ( ; s < S.nslots; s++)
- if (S.schedInfo.instrCanUseSlot(opCode, s))
- {
- S.addChoiceToSlot(s, S.getChoice(i));
- break;
- }
+ // No slot before `delayedNodeSlot' was found for this opCode
+ // Use a later slot, and allow some delay slots to fall in
+ // the next cycle.
+ if (noSlotFound)
+ for ( ; s < S.nslots; s++)
+ if (S.schedInfo.instrCanUseSlot(opCode, s)) {
+ S.addChoiceToSlot(s, S.getChoice(i));
+ break;
+ }
- assert(s < S.nslots && "No feasible slot for instruction?");
+ assert(s < S.nslots && "No feasible slot for instruction?");
- highestSlotUsed = max(highestSlotUsed, (int) s);
- }
+ highestSlotUsed = std::max(highestSlotUsed, (int) s);
+ }
- assert(highestSlotUsed <= (int) S.nslots-1 && "Invalid slot used?");
+ 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
- // slots for the node at the same time.
- cycles_t dcycle = S.getTime();
- unsigned int dslot = highestSlotUsed + 1;
- if (dslot == S.nslots)
- {
- dslot = 0;
- ++dcycle;
- }
- delaySlotInfo->recordChosenSlot(dcycle, dslot);
- getDelaySlotInfo = delaySlotInfo;
+ // 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
+ // slots for the node at the same time.
+ cycles_t dcycle = S.getTime();
+ unsigned int dslot = highestSlotUsed + 1;
+ if (dslot == S.nslots) {
+ dslot = 0;
+ ++dcycle;
}
- else
- { // There is an instruction that breaks the issue group.
- // For such an instruction, assign to the last possible slot in
- // the current group, and then don't assign any other instructions
- // to later slots.
- assert(indexForBreakingNode < S.nslots);
- const SchedGraphNode* breakingNode=S.getChoice(indexForBreakingNode);
- unsigned breakingSlot = INT_MAX;
- unsigned int nslotsToUse = S.nslots;
+ delaySlotInfo->recordChosenSlot(dcycle, dslot);
+ getDelaySlotInfo = delaySlotInfo;
+ } else {
+ // There is an instruction that breaks the issue group.
+ // For such an instruction, assign to the last possible slot in
+ // the current group, and then don't assign any other instructions
+ // to later slots.
+ assert(indexForBreakingNode < S.nslots);
+ 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->getMachineInstr()->getOpCode(), s))
- {
- breakingSlot = s;
- break;
- }
- assert(breakingSlot < S.nslots &&
- "No feasible slot for `breakingNode'?");
+ // 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)) {
+ breakingSlot = s;
+ break;
+ }
+ 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.
- for (unsigned i=0;
- i < S.getNumChoices() && i < indexForBreakingNode; i++)
- {
- MachineOpCode opCode = S.getChoice(i)->getMachineInstr()->getOpCode();
+ // 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.
+ for (unsigned i=0;
+ 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++)
- if (S.schedInfo.instrCanUseSlot(opCode, s))
- {
- if (breakingSlot < S.nslots && s < breakingSlot)
- {
- foundLowerSlot = true;
- nslotsToUse = breakingSlot; // RESETS LOOP UPPER BOUND!
- }
+ // 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++)
+ if (S.schedInfo.instrCanUseSlot(opCode, s)) {
+ if (breakingSlot < S.nslots && s < breakingSlot) {
+ foundLowerSlot = true;
+ nslotsToUse = breakingSlot; // RESETS LOOP UPPER BOUND!
+ }
- S.addChoiceToSlot(s, S.getChoice(i));
- }
+ S.addChoiceToSlot(s, S.getChoice(i));
+ }
- if (!foundLowerSlot)
- breakingSlot = INT_MAX; // disable breaking instr
- }
+ 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.
- if (breakingSlot < S.nslots)
- {
- S.addChoiceToSlot(breakingSlot, breakingNode);
- nslotsToUse = breakingSlot;
- }
- else
- nslotsToUse = S.nslots;
+ // Assign the breaking instruction (if any) to a single slot
+ // Otherwise, just ignore the instruction. It will simply be
+ // scheduled in a later cycle.
+ if (breakingSlot < S.nslots) {
+ S.addChoiceToSlot(breakingSlot, breakingNode);
+ 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.
- for (unsigned i=indexForBreakingNode+1; i < S.getNumChoices(); i++)
- {
- bool foundLowerSlot = false;
- MachineOpCode opCode = S.getChoice(i)->getMachineInstr()->getOpCode();
- for (unsigned int s=startSlot; s < nslotsToUse; s++)
- if (S.schedInfo.instrCanUseSlot(opCode, s))
- S.addChoiceToSlot(s, S.getChoice(i));
- }
- } // endif (no delay slots and no breaking slots)
+ // 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.
+ for (unsigned i=indexForBreakingNode+1; i < S.getNumChoices(); i++) {
+ MachineOpCode opCode = S.getChoice(i)->getOpcode();
+ for (unsigned int s=startSlot; s < nslotsToUse; s++)
+ if (S.schedInfo.instrCanUseSlot(opCode, s))
+ S.addChoiceToSlot(s, S.getChoice(i));
+ }
+ } // endif (no delay slots and no breaking slots)
return S.getNumChoices();
}
-static void
-AssignInstructionsToSlots(class SchedulingManager& S, unsigned maxIssue)
+static unsigned
+ChooseOneGroup(SchedulingManager& S)
{
- // find the slot to start from, in the current cycle
- unsigned int startSlot = 0;
- cycles_t curTime = S.getTime();
+ assert(S.schedPrio.getNumReady() > 0
+ && "Don't get here without ready instructions.");
- assert(maxIssue > 0 && maxIssue <= S.nslots - startSlot);
+ cycles_t firstCycle = S.getTime();
+ DelaySlotInfo* getDelaySlotInfo = NULL;
- // If only one instruction can be issued, do so.
- if (maxIssue == 1)
- for (unsigned s=startSlot; s < S.nslots; s++)
- if (S.getChoicesForSlot(s).size() > 0)
- {// found the one instruction
- S.scheduleInstr(*S.getChoicesForSlot(s).begin(), s, curTime);
- return;
- }
+ // Choose up to `nslots' feasible instructions and their possible slots.
+ unsigned numIssued = FindSlotChoices(S, getDelaySlotInfo);
- // Otherwise, choose from the choices for each slot
- //
- InstrGroup* igroup = S.isched.getIGroup(S.getTime());
- assert(igroup != NULL && "Group creation failed?");
+ while (numIssued == 0) {
+ S.updateTime(S.getTime()+1);
+ numIssued = FindSlotChoices(S, getDelaySlotInfo);
+ }
- // 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).
- unsigned numIssued;
- for (numIssued = 0; numIssued < maxIssue; numIssued++)
- {
- int chosenSlot = -1, chosenNodeIndex = -1;
- for (unsigned s=startSlot; s < S.nslots; s++)
- if ((*igroup)[s] == NULL && S.getChoicesForSlot(s).size() == 1)
- {
- 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.
- const SchedGraphNode* node= *S.getChoicesForSlot(chosenSlot).begin();
- S.scheduleInstr(node, chosenSlot, curTime);
- }
+ AssignInstructionsToSlots(S, numIssued);
+
+ if (getDelaySlotInfo != NULL)
+ numIssued += getDelaySlotInfo->scheduleDelayedNode(S);
+
+ // Print trace of scheduled instructions before newly ready ones
+ if (SchedDebugLevel >= Sched_PrintSchedTrace) {
+ for (cycles_t c = firstCycle; c <= S.getTime(); c++) {
+ std::cerr << " Cycle " << (long)c <<" : Scheduled instructions:\n";
+ const InstrGroup* igroup = S.isched.getIGroup(c);
+ for (unsigned int s=0; s < S.nslots; s++) {
+ std::cerr << " ";
+ if ((*igroup)[s] != NULL)
+ std::cerr << * ((*igroup)[s])->getMachineInstr() << "\n";
+ else
+ std::cerr << "<none>\n";
+ }
}
+ }
- assert(numIssued > 0 && "Should not happen when maxIssue > 0!");
+ return numIssued;
}
+static void
+ForwardListSchedule(SchedulingManager& S)
+{
+ unsigned N;
+ const SchedGraphNode* node;
+
+ S.schedPrio.initialize();
+
+ while ((N = S.schedPrio.getNumReady()) > 0) {
+ cycles_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 (cycles_t c = nextCycle; c <= S.getTime(); c++) {
+ const InstrGroup* igroup = S.isched.getIGroup(c);
+ for (unsigned int s=0; s < S.nslots; s++)
+ if ((node = (*igroup)[s]) != NULL) {
+ S.schedPrio.issuedReadyNodeAt(S.getTime(), node);
+ 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())));
+ }
+}
+
//---------------------------------------------------------------------
// Code for filling delay slots for delayed terminator instructions
// when we cannot find single-cycle instructions that can be reordered.
//----------------------------------------------------------------------
-static void
-ChooseInstructionsForDelaySlots(SchedulingManager& S,
- const BasicBlock* bb,
- SchedGraph* graph)
-{
- // Look for instructions that can be used for delay slots.
- // Remove them from the graph, and mark them to be used for delay slots.
- const MachineInstrInfo& mii = S.getInstrInfo();
- const TerminatorInst* term = bb->getTerminator();
- MachineCodeForVMInstr& termMvec = term->getMachineInstrVec();
-
- // Find the first branch instr in the sequence of machine instrs for term
- //
- unsigned first = 0;
- while (! mii.isBranch(termMvec[first]->getOpCode()))
- ++first;
- assert(first < termMvec.size() &&
- "No branch instructions for BR? Ok, but weird! Delete assertion.");
- if (first == termMvec.size())
- return;
-
- SchedGraphNode* brNode = graph->getGraphNodeForInstr(termMvec[first]);
- assert(! mii.isCall(brNode->getMachineInstr()->getOpCode()) && "Call used as terminator?");
-
- unsigned ndelays = mii.getNumDelaySlots(brNode->getMachineInstr()->getOpCode());
- if (ndelays == 0)
- return;
-
- // Use vectors to remember the nodes chosen for delay slots, and the
- // NOPs that will be unused. We cannot remove them from the graph while
- // walking through the preds and succs of the brNode here, so we
- // remember the nodes in the vectors and remove them later.
- // We use separate vectors for the single-cycle and multi-cycle nodes,
- // so that we can give preference to single-cycle nodes.
- //
- vector<SchedGraphNode*> sdelayNodeVec;
- vector<SchedGraphNode*> mdelayNodeVec;
- vector<SchedGraphNode*> nopNodeVec;
- unsigned numUseful = 0;
-
- sdelayNodeVec.reserve(ndelays);
-
- for (sg_pred_iterator P = pred_begin(brNode);
- P != pred_end(brNode) && sdelayNodeVec.size() < ndelays; ++P)
- if (! (*P)->isDummyNode() &&
- ! mii.isNop((*P)->getMachineInstr()->getOpCode()) &&
- NodeCanFillDelaySlot(S, *P, brNode, /*pred*/ true))
- {
- ++numUseful;
- if (mii.maxLatency((*P)->getMachineInstr()->getOpCode()) > 1)
- mdelayNodeVec.push_back(*P);
- 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 latency;
- unsigned minLatency = mii.maxLatency(mdelayNodeVec[0]->getMachineInstr()->getOpCode());
- unsigned minIndex = 0;
- for (unsigned i=1; i < mdelayNodeVec.size(); i++)
- if (minLatency >=
- (latency = mii.maxLatency(mdelayNodeVec[i]->getMachineInstr()->getOpCode())))
- {
- minLatency = latency;
- minIndex = i;
- }
- sdelayNodeVec.push_back(mdelayNodeVec[minIndex]);
- if (sdelayNodeVec.size() < ndelays) // avoid the last erase!
- mdelayNodeVec.erase(mdelayNodeVec.begin() + minIndex);
- }
-
- // Now, 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.
- for (sg_succ_iterator I=succ_begin(brNode); I != succ_end(brNode); ++I)
- if (! (*I)->isDummyNode()
- && mii.isNop((*I)->getMachineInstr()->getOpCode()))
- {
- if (sdelayNodeVec.size() < ndelays)
- sdelayNodeVec.push_back(*I);
- else
- nopNodeVec.push_back(*I);
- }
-
- // Mark the nodes chosen for delay slots. This removes them from the graph.
- for (unsigned i=0; i < sdelayNodeVec.size(); i++)
- MarkNodeForDelaySlot(S, sdelayNodeVec[i], brNode, true);
-
- // And remove the unused NOPs the graph.
- for (unsigned i=0; i < nopNodeVec.size(); i++)
- nopNodeVec[i]->eraseAllEdges();
-}
-
-
-bool
+static bool
NodeCanFillDelaySlot(const SchedulingManager& S,
const SchedGraphNode* node,
const SchedGraphNode* brNode,
assert(! node->isDummyNode());
// don't put a branch in the delay slot of another branch
- if (S.getInstrInfo().isBranch(node->getMachineInstr()->getOpCode()))
+ 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->getMachineInstr()->getOpCode()))
+ if (S.schedInfo.isSingleIssue(node->getOpcode()))
return false;
// don't put a load-use dependence in the delay slot of a branch
- const MachineInstrInfo& mii = S.getInstrInfo();
+ const TargetInstrInfo& mii = S.getInstrInfo();
for (SchedGraphNode::const_iterator EI = node->beginInEdges();
EI != node->endInEdges(); ++EI)
- if (! (*EI)->getSrc()->isDummyNode()
- && mii.isLoad((*EI)->getSrc()->getMachineInstr()->getOpCode())
+ if (! ((SchedGraphNode*)(*EI)->getSrc())->isDummyNode()
+ && mii.isLoad(((SchedGraphNode*)(*EI)->getSrc())->getOpcode())
&& (*EI)->getDepType() == SchedGraphEdge::CtrlDep)
return false;
// for now, don't put an instruction that does not have operand
// interlocks in the delay slot of a branch
- if (! S.getInstrInfo().hasOperandInterlock(node->getMachineInstr()->getOpCode()))
+ if (! S.getInstrInfo().hasOperandInterlock(node->getOpcode()))
return false;
- // Finally, if the instruction preceeds the branch, we make sure the
+ // 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();
- OEI != node->endOutEdges(); ++OEI)
- if (! (*OEI)->getSink()->isDummyNode()
- && ((*OEI)->getSink() != brNode
- || (*OEI)->getDepType() != SchedGraphEdge::CtrlDep))
- {
- onlyCDEdgeToBranch = false;
- break;
- }
+ if (nodeIsPredecessor) {
+ bool onlyCDEdgeToBranch = true;
+ for (SchedGraphNode::const_iterator OEI = node->beginOutEdges();
+ OEI != node->endOutEdges(); ++OEI)
+ if (! ((SchedGraphNode*)(*OEI)->getSink())->isDummyNode()
+ && ((*OEI)->getSink() != brNode
+ || (*OEI)->getDepType() != SchedGraphEdge::CtrlDep))
+ {
+ onlyCDEdgeToBranch = false;
+ break;
+ }
- if (!onlyCDEdgeToBranch)
- return false;
- }
+ if (!onlyCDEdgeToBranch)
+ return false;
+ }
return true;
}
-void
+static void
MarkNodeForDelaySlot(SchedulingManager& S,
+ SchedGraph* graph,
SchedGraphNode* node,
const SchedGraphNode* brNode,
bool nodeIsPredecessor)
{
- if (nodeIsPredecessor)
- { // If node is in the same basic block (i.e., preceeds brNode),
- // remove it and all its incident edges from the graph.
- node->eraseAllEdges();
- }
- 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");
- }
+ if (nodeIsPredecessor) {
+ // If node is in the same basic block (i.e., precedes brNode),
+ // 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 {
+ // 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);
}
+void
+FindUsefulInstructionsForDelaySlots(SchedulingManager& S,
+ SchedGraphNode* brNode,
+ std::vector<SchedGraphNode*>& sdelayNodeVec)
+{
+ 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() &&
+ ! mii.isNop((*P)->getOpcode()) &&
+ NodeCanFillDelaySlot(S, *P, brNode, /*pred*/ true))
+ {
+ if (mii.maxLatency((*P)->getOpcode()) > 1)
+ mdelayNodeVec.push_back(*P);
+ 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 =
+ mii.maxLatency(mdelayNodeVec[i]->getOpcode());
+ if (lmin >= li)
+ {
+ lmin = li;
+ minIndex = i;
+ }
+ }
+ sdelayNodeVec.push_back(mdelayNodeVec[minIndex]);
+ if (sdelayNodeVec.size() < ndelays) // avoid the last erase!
+ mdelayNodeVec.erase(mdelayNodeVec.begin() + minIndex);
+ }
+}
+
+
+// Remove the NOPs currently in delay slots from the graph.
+// 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!!!
+ std::vector<SchedGraphNode*> sdelayNodeVec,
+ SchedGraph* graph)
+{
+ std::vector<SchedGraphNode*> nopNodeVec; // this will hold unused NOPs
+ const TargetInstrInfo& mii = S.getInstrInfo();
+ 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();
+ assert(&MBB[firstDelaySlotIdx - 1] == brInstr &&
+ "Incorrect instr. index in basic block for brInstr");
+
+ // First find all useful instructions already in the delay slots
+ // and USE THEM. We'll throw away the unused alternatives below
+ //
+ for (unsigned i=firstDelaySlotIdx; i < firstDelaySlotIdx + ndelays; ++i)
+ if (! mii.isNop(MBB[i].getOpcode()))
+ sdelayNodeVec.insert(sdelayNodeVec.begin(),
+ graph->getGraphNodeForInstr(&MBB[i]));
+
+ // Then find the NOPs and keep only as many as are needed.
+ // Put the rest in nopNodeVec to be deleted.
+ for (unsigned i=firstDelaySlotIdx; i < firstDelaySlotIdx + ndelays; ++i)
+ if (mii.isNop(MBB[i].getOpcode()))
+ if (sdelayNodeVec.size() < ndelays)
+ sdelayNodeVec.push_back(graph->getGraphNodeForInstr(&MBB[i]));
+ else {
+ nopNodeVec.push_back(graph->getGraphNodeForInstr(&MBB[i]));
+
+ //remove the MI from the Machine Code For Instruction
+ const TerminatorInst *TI = MBB.getBasicBlock()->getTerminator();
+ MachineCodeForInstruction& llvmMvec =
+ MachineCodeForInstruction::get((const Instruction *)TI);
+
+ for(MachineCodeForInstruction::iterator mciI=llvmMvec.begin(),
+ mciE=llvmMvec.end(); mciI!=mciE; ++mciI){
+ if (*mciI == &MBB[i])
+ llvmMvec.erase(mciI);
+ }
+ }
+
+ assert(sdelayNodeVec.size() >= ndelays);
+
+ // If some delay slots were already filled, throw away that many new choices
+ if (sdelayNodeVec.size() > ndelays)
+ sdelayNodeVec.resize(ndelays);
+
+ // Mark the nodes chosen for delay slots. This removes them from the graph.
+ for (unsigned i=0; i < sdelayNodeVec.size(); i++)
+ MarkNodeForDelaySlot(S, graph, sdelayNodeVec[i], node, true);
+
+ // And remove the unused NOPs from the graph.
+ for (unsigned i=0; i < nopNodeVec.size(); i++)
+ graph->eraseIncidentEdges(nopNodeVec[i], /*addDummyEdges*/ true);
+}
+
+
+// For all delayed instructions, choose instructions to put in the delay
+// slots and pull those out of the graph. Mark them for the delay slots
+// in the DelaySlotInfo object for that graph node. If no useful work
+// is found for a delay slot, use the NOP that is currently in that slot.
+//
+// We try to fill the delay slots with useful work for all instructions
+// EXCEPT CALLS AND RETURNS.
+// For CALLs and RETURNs, it is nearly always possible to use one of the
+// call sequence instrs and putting anything else in the delay slot could be
+// suboptimal. Also, it complicates generating the calling sequence code in
+// regalloc.
+//
+static void
+ChooseInstructionsForDelaySlots(SchedulingManager& S, MachineBasicBlock &MBB,
+ SchedGraph *graph)
+{
+ const TargetInstrInfo& mii = S.getInstrInfo();
+
+ Instruction *termInstr = (Instruction*)MBB.getBasicBlock()->getTerminator();
+ MachineCodeForInstruction &termMvec=MachineCodeForInstruction::get(termInstr);
+ std::vector<SchedGraphNode*> delayNodeVec;
+ const MachineInstr* brInstr = NULL;
+
+ if (EnableFillingDelaySlots &&
+ termInstr->getOpcode() != Instruction::Ret)
+ {
+ // To find instructions that need delay slots without searching the full
+ // machine code, we assume that the only delayed instructions are CALLs
+ // or instructions generated for the terminator inst.
+ // Find the first branch instr in the sequence of machine instrs for term
+ //
+ unsigned first = 0;
+ while (first < termMvec.size() &&
+ ! mii.isBranch(termMvec[first]->getOpcode()))
+ {
+ ++first;
+ }
+ assert(first < termMvec.size() &&
+ "No branch instructions for BR? Ok, but weird! Delete assertion.");
+
+ brInstr = (first < termMvec.size())? termMvec[first] : NULL;
+
+ // Compute a vector of the nodes chosen for delay slots and then
+ // mark delay slots to replace NOPs with these useful instructions.
+ //
+ if (brInstr != NULL) {
+ SchedGraphNode* brNode = graph->getGraphNodeForInstr(brInstr);
+ FindUsefulInstructionsForDelaySlots(S, brNode, delayNodeVec);
+ ReplaceNopsWithUsefulInstr(S, brNode, delayNodeVec, graph);
+ }
+ }
+
+ // Also mark delay slots for other delayed instructions to hold NOPs.
+ // Simply passing in an empty delayNodeVec will have this effect.
+ // If brInstr is not handled above (EnableFillingDelaySlots == false),
+ // brInstr will be NULL so this will handle the branch instrs. as well.
+ //
+ delayNodeVec.clear();
+ for (unsigned i=0; i < MBB.size(); ++i)
+ if (&MBB[i] != brInstr &&
+ mii.getNumDelaySlots(MBB[i].getOpcode()) > 0)
+ {
+ SchedGraphNode* node = graph->getGraphNodeForInstr(&MBB[i]);
+ ReplaceNopsWithUsefulInstr(S, node, delayNodeVec, graph);
+ }
+}
+
+
//
// Schedule the delayed branch and its delay slots
//
-void
+unsigned
DelaySlotInfo::scheduleDelayedNode(SchedulingManager& S)
{
assert(delayedNodeSlotNum < S.nslots && "Illegal slot for branch");
S.scheduleInstr(brNode, nextSlot, nextTime);
- for (unsigned d=0; d < ndelays; d++)
- {
- ++nextSlot;
- if (nextSlot == S.nslots)
- {
- nextSlot = 0;
- nextTime++;
- }
+ for (unsigned d=0; d < ndelays; d++) {
+ ++nextSlot;
+ if (nextSlot == S.nslots) {
+ nextSlot = 0;
+ nextTime++;
+ }
- // Find the first feasible instruction for this delay slot
- // Note that we only check for issue restrictions here.
- // We do *not* check for flow dependences but rely on pipeline
- // interlocks to resolve them. Machines without interlocks
- // will require this code to be modified.
- for (unsigned i=0; i < delayNodeVec.size(); i++)
- {
- const SchedGraphNode* dnode = delayNodeVec[i];
- if ( ! S.isScheduled(dnode)
- && S.schedInfo.instrCanUseSlot(dnode->getMachineInstr()->getOpCode(), nextSlot)
- && instrIsFeasible(S, dnode->getMachineInstr()->getOpCode()))
- {
- assert(S.getInstrInfo().hasOperandInterlock(dnode->getMachineInstr()->getOpCode())
- && "Instructions without interlocks not yet supported "
- "when filling branch delay slots");
- S.scheduleInstr(dnode, nextSlot, nextTime);
- break;
- }
- }
+ // Find the first feasible instruction for this delay slot
+ // Note that we only check for issue restrictions here.
+ // We do *not* check for flow dependences but rely on pipeline
+ // interlocks to resolve them. Machines without interlocks
+ // will require this code to be modified.
+ for (unsigned i=0; i < delayNodeVec.size(); i++) {
+ const SchedGraphNode* dnode = delayNodeVec[i];
+ if ( ! S.isScheduled(dnode)
+ && S.schedInfo.instrCanUseSlot(dnode->getOpcode(), nextSlot)
+ && instrIsFeasible(S, dnode->getOpcode()))
+ {
+ assert(S.getInstrInfo().hasOperandInterlock(dnode->getOpcode())
+ && "Instructions without interlocks not yet supported "
+ "when filling branch delay slots");
+ S.scheduleInstr(dnode, nextSlot, nextTime);
+ break;
+ }
}
+ }
// Update current time if delay slots overflowed into later cycles.
// Do this here because we know exactly which cycle is the last cycle
nextSlot = delayedNodeSlotNum;
nextTime = delayedNodeCycle;
for (unsigned i=0; i < delayNodeVec.size(); i++)
- if (! S.isScheduled(delayNodeVec[i]))
- {
- do { // find the next empty slot
- ++nextSlot;
- if (nextSlot == S.nslots)
- {
- nextSlot = 0;
- nextTime++;
- }
- } while (S.isched.getInstr(nextSlot, nextTime) != NULL);
+ if (! S.isScheduled(delayNodeVec[i])) {
+ do { // find the next empty slot
+ ++nextSlot;
+ if (nextSlot == S.nslots) {
+ nextSlot = 0;
+ nextTime++;
+ }
+ } while (S.isched.getInstr(nextSlot, nextTime) != NULL);
- S.scheduleInstr(delayNodeVec[i], nextSlot, nextTime);
- break;
- }
+ S.scheduleInstr(delayNodeVec[i], nextSlot, nextTime);
+ break;
+ }
+
+ return 1 + ndelays;
}
+
+// Check if the instruction would conflict with instructions already
+// chosen for the current cycle
+//
+static inline bool
+ConflictsWithChoices(const SchedulingManager& S,
+ MachineOpCode opCode)
+{
+ // Check if the instruction must issue by itself, and some feasible
+ // choices have already been made for this cycle
+ if (S.getNumChoices() > 0 && S.schedInfo.isSingleIssue(opCode))
+ return true;
+
+ // For each class that opCode belongs to, check if there are too many
+ // instructions of that class.
+ //
+ const InstrSchedClass sc = S.schedInfo.getSchedClass(opCode);
+ return (S.getNumChoicesInClass(sc) == S.schedInfo.getMaxIssueForClass(sc));
+}
+
+
+//************************* External Functions *****************************/
+
+
+//---------------------------------------------------------------------------
+// Function: ViolatesMinimumGap
+//
+// Purpose:
+// Check minimum gap requirements relative to instructions scheduled in
+// previous cycles.
+// Note that we do not need to consider `nextEarliestIssueTime' here because
+// that is also captured in the earliest start times for each opcode.
+//---------------------------------------------------------------------------
+
+static inline bool
+ViolatesMinimumGap(const SchedulingManager& S,
+ MachineOpCode opCode,
+ const cycles_t inCycle)
+{
+ return (inCycle < S.getEarliestStartTimeForOp(opCode));
+}
+
+
+//---------------------------------------------------------------------------
+// Function: instrIsFeasible
+//
+// Purpose:
+// Check if any issue restrictions would prevent the instruction from
+// being issued in the current cycle
+//---------------------------------------------------------------------------
+
+bool
+instrIsFeasible(const SchedulingManager& S,
+ MachineOpCode opCode)
+{
+ // skip the instruction if it cannot be issued due to issue restrictions
+ // caused by previously issued instructions
+ if (ViolatesMinimumGap(S, opCode, S.getTime()))
+ return false;
+
+ // skip the instruction if it cannot be issued due to issue restrictions
+ // caused by previously chosen instructions for the current cycle
+ if (ConflictsWithChoices(S, opCode))
+ return false;
+
+ return true;
+}
+
+//---------------------------------------------------------------------------
+// Function: ScheduleInstructionsWithSSA
+//
+// Purpose:
+// Entry point for instruction scheduling on SSA form.
+// Schedules the machine instructions generated by instruction selection.
+// Assumes that register allocation has not been done, i.e., operands
+// are still in SSA form.
+//---------------------------------------------------------------------------
+
+namespace {
+ class InstructionSchedulingWithSSA : public FunctionPass {
+ const TargetMachine ⌖
+ public:
+ inline InstructionSchedulingWithSSA(const TargetMachine &T) : target(T) {}
+
+ const char *getPassName() const { return "Instruction Scheduling"; }
+
+ // getAnalysisUsage - We use LiveVarInfo...
+ virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.addRequired<FunctionLiveVarInfo>();
+ AU.setPreservesCFG();
+ }
+
+ bool runOnFunction(Function &F);
+ };
+} // end anonymous namespace
+
+
+bool InstructionSchedulingWithSSA::runOnFunction(Function &F)
+{
+ SchedGraphSet graphSet(&F, target);
+
+ if (SchedDebugLevel >= Sched_PrintSchedGraphs) {
+ std::cerr << "\n*** SCHEDULING GRAPHS FOR INSTRUCTION SCHEDULING\n";
+ graphSet.dump();
+ }
+
+ for (SchedGraphSet::const_iterator GI=graphSet.begin(), GE=graphSet.end();
+ GI != GE; ++GI)
+ {
+ SchedGraph* graph = (*GI);
+ MachineBasicBlock &MBB = graph->getBasicBlock();
+
+ if (SchedDebugLevel >= Sched_PrintSchedTrace)
+ std::cerr << "\n*** TRACE OF INSTRUCTION SCHEDULING OPERATIONS\n\n";
+
+ // expensive!
+ SchedPriorities schedPrio(&F, graph, getAnalysis<FunctionLiveVarInfo>());
+ SchedulingManager S(target, graph, schedPrio);
+
+ ChooseInstructionsForDelaySlots(S, MBB, graph); // modifies graph
+ ForwardListSchedule(S); // computes schedule in S
+ RecordSchedule(MBB, S); // records schedule in BB
+ }
+
+ if (SchedDebugLevel >= Sched_PrintMachineCode) {
+ std::cerr << "\n*** Machine instructions after INSTRUCTION SCHEDULING\n";
+ MachineFunction::get(&F).dump();
+ }
+
+ return false;
+}
+
+
+FunctionPass *createInstructionSchedulingWithSSAPass(const TargetMachine &tgt) {
+ return new InstructionSchedulingWithSSA(tgt);
+}
+
+} // End llvm namespace
+
projects / oota-llvm.git / blobdiff