Implementation of instruction scheduling for LLVM.

Currently schedules one basic block at a time.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@396 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 1464 insertions, 0 deletions

diff --git a/lib/CodeGen/InstrSched/InstrScheduling.cpp b/lib/CodeGen/InstrSched/InstrScheduling.cpp
new file mode 100644
index 0000000000..d58988e460
--- /dev/null
+++ b/lib/CodeGen/InstrSched/InstrScheduling.cpp
@@ -0,0 +1,1464 @@
+// $Id$
+//***************************************************************************
+// File:
+//	InstrScheduling.cpp
+// 
+// Purpose:
+//	
+// History:
+//	7/23/01	 -  Vikram Adve  -  Created
+//***************************************************************************
+
+
+//************************* System Include Files ***************************/
+
+#include <hash_set>
+#include <vector>
+#include <algorithm>
+#include <iterator>
+
+//*************************** User Include Files ***************************/
+
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Method.h"
+#include "llvm/BasicBlock.h"
+#include "llvm/Instruction.h"
+#include "llvm/Analysis/LiveVar/BBLiveVar.h"
+#include "llvm/CodeGen/TargetMachine.h"
+#include "llvm/CodeGen/MachineInstr.h"
+#include "llvm/CodeGen/SchedGraph.h"
+#include "llvm/CodeGen/SchedPriorities.h"
+#include "llvm/CodeGen/InstrScheduling.h"
+
+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);
+
+static bool	ConflictsWithChoices	(const SchedulingManager& S,
+					 MachineOpCode opCode);
+
+static void	ChooseInstructionsForDelaySlots(SchedulingManager& S,
+					 const BasicBlock* bb,
+					 SchedGraph* graph);
+
+static bool	NodeCanFillDelaySlot	(const SchedulingManager& S,
+					 const SchedGraphNode* node,
+					 const SchedGraphNode* brNode,
+					 bool nodeIsPredecessor);
+
+static void	MarkNodeForDelaySlot	(SchedulingManager& S,
+					 SchedGraphNode* node,
+					 const SchedGraphNode* brNode,
+					 bool nodeIsPredecessor);
+
+//************************* Internal Data Types *****************************/
+
+
+//----------------------------------------------------------------------
+// class InstrGroup:
+// 
+// Represents a group of instructions scheduled to be issued
+// in a single cycle.
+//----------------------------------------------------------------------
+
+class InstrGroup: public NonCopyable {
+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:
+  vector<const SchedGraphNode*> group;
+};
+
+
+//----------------------------------------------------------------------
+// class ScheduleIterator:
+// 
+// Iterates over the machine instructions in the for a single basic block.
+// The schedule is represented by an InstrSchedule object.
+//----------------------------------------------------------------------
+
+template<class _NodeType>
+class ScheduleIterator: public std::forward_iterator<_NodeType, ptrdiff_t> {
+private:
+  unsigned cycleNum;
+  unsigned slotNum;
+  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(); 
+  }
+  
+  /*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 {
+    assert(cycleNum < S.groups.size());
+    return (*S.groups[cycleNum])[slotNum];
+  }
+  inline _NodeType* operator->() const { return operator*(); }
+  
+         _Self& operator++();				// Preincrement
+  inline _Self operator++(int) {			// Postincrement
+    _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();
+};
+
+
+//----------------------------------------------------------------------
+// class InstrSchedule:
+// 
+// Represents the schedule of machine instructions for a single basic block.
+//----------------------------------------------------------------------
+
+class InstrSchedule: public NonCopyable {
+private:
+  const unsigned int nslots;
+  unsigned int numInstr;
+  vector<InstrGroup*> groups;		// indexed by cycle number
+  vector<cycles_t> startTime;		// indexed by node id
+  
+public: // iterators
+  typedef ScheduleIterator<SchedGraphNode> iterator;
+  typedef ScheduleIterator<const SchedGraphNode> const_iterator;
+  
+        iterator begin();
+  const_iterator begin() const;
+        iterator end();
+  const_iterator end()   const;
+  
+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,
+					 cycles_t c) const {
+    const InstrGroup* igroup = this->getIGroup(c);
+    return (igroup == NULL)? NULL : (*igroup)[slotNum];
+  }
+  
+  inline InstrGroup*	getIGroup	(cycles_t c) {
+    if (c >= groups.size())
+      groups.resize(c+1);
+    if (groups[c] == NULL)
+      groups[c] = new InstrGroup(nslots);
+    return groups[c];
+  }
+  
+  inline const InstrGroup* getIGroup	(cycles_t c) const {
+    assert(c < groups.size());
+    return groups[c];
+  }
+  
+  inline cycles_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,
+					 cycles_t cycle) {
+    InstrGroup* igroup = this->getIGroup(cycle);
+    assert((*igroup)[slotNum] == NULL &&  "Slot already filled?");
+    igroup->addInstr(node, slotNum);
+    assert(node->getNodeId() < startTime.size());
+    startTime[node->getNodeId()] = cycle;
+    ++numInstr;
+  }
+  
+private:
+  friend class iterator;
+  friend class const_iterator;
+  /*ctor*/	InstrSchedule	();	// Disable: DO NOT IMPLEMENT.
+};
+
+
+/*ctor*/
+InstrSchedule::InstrSchedule(unsigned int _nslots, unsigned int _numNodes)
+  : nslots(_nslots),
+    numInstr(0),
+    groups(2 * _numNodes / _nslots),		// 2 x lower-bound for #cycles
+    startTime(_numNodes, (cycles_t) -1)		// set all to -1
+{
+}
+
+
+/*dtor*/
+InstrSchedule::~InstrSchedule()
+{
+  for (unsigned c=0, NC=groups.size(); c < NC; c++)
+    if (groups[c] != NULL)
+      delete groups[c];			// delete InstrGroup objects
+}
+
+
+template<class _NodeType>
+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)
+    {
+      ++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>
+inline 
+ScheduleIterator<_NodeType>&
+ScheduleIterator<_NodeType>::operator++()	// Preincrement
+{
+  ++slotNum;
+  if (slotNum == S.nslots)
+    {
+      ++cycleNum;
+      slotNum = 0;
+    }
+  skipToNextInstr(); 
+  return *this;
+}
+
+template<class _NodeType>
+ScheduleIterator<_NodeType>
+ScheduleIterator<_NodeType>::begin(const InstrSchedule& _schedule)
+{
+  return _Self(_schedule, 0, 0);
+}
+
+template<class _NodeType>
+ScheduleIterator<_NodeType>
+ScheduleIterator<_NodeType>::end(const InstrSchedule& _schedule)
+{
+  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:
+// 
+// Record information about delay slots for a single branch instruction.
+// Delay slots are simply indexed by slot number 1 ... numDelaySlots
+//----------------------------------------------------------------------
+
+class DelaySlotInfo: public NonCopyable {
+private:
+  const SchedGraphNode* brNode;
+  unsigned int ndelays;
+  vector<const SchedGraphNode*> delayNodeVec;
+  cycles_t delayedNodeCycle;
+  unsigned int delayedNodeSlotNum;
+  
+public:
+  /*ctor*/	DelaySlotInfo		(const SchedGraphNode* _brNode,
+					 unsigned _ndelays)
+    : brNode(_brNode), ndelays(_ndelays),
+      delayedNodeCycle(0), delayedNodeSlotNum(0) {}
+  
+  inline unsigned getNumDelays	() {
+    return ndelays;
+  }
+  
+  inline const 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	(cycles_t cycle, unsigned slotNum) {
+    delayedNodeCycle = cycle;
+    delayedNodeSlotNum = slotNum;
+  }
+  
+  void		scheduleDelayedNode	(SchedulingManager& S);
+};
+
+
+//----------------------------------------------------------------------
+// class SchedulingManager:
+// 
+// Represents the schedule of machine instructions for a single basic block.
+//----------------------------------------------------------------------
+
+class SchedulingManager: public NonCopyable {
+public: // publicly accessible data members
+  const unsigned int nslots;
+  const MachineSchedInfo& schedInfo;
+  SchedPriorities& schedPrio;
+  InstrSchedule isched;
+  
+private:
+  unsigned int 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
+  hash_map<const SchedGraphNode*, DelaySlotInfo*> delaySlotInfoForBranches;
+						// indexed by branch node ptr 
+  
+public:
+  /*ctor*/	SchedulingManager	(const TargetMachine& _target,
+					 const SchedGraph* graph,
+					 SchedPriorities& schedPrio);
+  /*dtor*/	~SchedulingManager	() {}
+  
+  //----------------------------------------------------------------------
+  // Simplify access to the machine instruction info
+  //----------------------------------------------------------------------
+  
+  inline const MachineInstrInfo& getInstrInfo	() const {
+    return schedInfo.getInstrInfo();
+  }
+  
+  //----------------------------------------------------------------------
+  // Interface for checking and updating the current time
+  //----------------------------------------------------------------------
+  
+  inline cycles_t	getTime			() const {
+    return curTime;
+  }
+  
+  inline cycles_t	getEarliestIssueTime() const {
+    return nextEarliestIssueTime;
+  }
+  
+  inline cycles_t	getEarliestStartTimeForOp(MachineOpCode opCode) const {
+    assert(opCode < (int) nextEarliestStartTime.size());
+    return nextEarliestStartTime[opCode];
+  }
+  
+  // Update current time to specified cycle
+  inline void	updateTime		(cycles_t c) {
+    curTime = c;
+    schedPrio.updateTime(c);
+  }
+  
+  //----------------------------------------------------------------------
+  // Functions to manage the choices for the current cycle including:
+  // -- a vector of choices by priority (choiceVec)
+  // -- vectors of the choices for each instruction slot (choicesForSlot[])
+  // -- 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 < (int) 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.
+    choiceVec.push_back(node);
+    const InstrSchedClass& sc = schedInfo.getSchedClass(node->getOpCode());
+    assert(sc < (int) 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++)
+      choicesForSlot[s].clear();
+    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,
+					 cycles_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 < (int) numInClass.size());
+    numInClass[sc]--;
+  }
+  
+  //----------------------------------------------------------------------
+  // Create and retrieve delay slot info for delayed instructions
+  //----------------------------------------------------------------------
+  
+  inline DelaySlotInfo* getDelaySlotInfoForInstr(const SchedGraphNode* bn,
+						 bool createIfMissing=false)
+  {
+    DelaySlotInfo* dinfo;
+    hash_map<const SchedGraphNode*, DelaySlotInfo* >::const_iterator
+      I = delaySlotInfoForBranches.find(bn);
+    if (I == delaySlotInfoForBranches.end())
+      {
+	if (createIfMissing)
+	  {
+	    dinfo = new DelaySlotInfo(bn,
+			  getInstrInfo().getNumDelaySlots(bn->getOpCode()));
+	    delaySlotInfoForBranches[bn] = dinfo;
+	  }
+	else
+	  dinfo = NULL;
+      }
+    else
+      dinfo = (*I).second;
+    
+    return dinfo;
+  }
+  
+private:
+  /*ctor*/	SchedulingManager	();	// Disable: DO NOT IMPLEMENT.
+  void		updateEarliestStartTimes(const SchedGraphNode* node,
+					 cycles_t schedTime);
+};
+
+
+/*ctor*/
+SchedulingManager::SchedulingManager(const TargetMachine& target,
+				     const SchedGraph* graph,
+				     SchedPriorities& _schedPrio)
+  : nslots(target.getSchedInfo().getMaxNumIssueTotal()),
+    schedInfo(target.getSchedInfo()),
+    schedPrio(_schedPrio),
+    isched(nslots, graph->getNumNodes()),
+    totalInstrCount(graph->getNumNodes() - 2),
+    nextEarliestIssueTime(0),
+    choicesForSlot(nslots),
+    numInClass(target.getSchedInfo().getNumSchedClasses(), 0),	// set all to 0
+    nextEarliestStartTime(target.getInstrInfo().getNumRealOpCodes(),
+			  (cycles_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.
+  for (unsigned int i=0; i < nslots; i++)
+    choicesForSlot[i].resize(nslots);
+}
+
+
+void
+SchedulingManager::updateEarliestStartTimes(const SchedGraphNode* node,
+					    cycles_t schedTime)
+{
+  if (schedInfo.numBubblesAfter(node->getOpCode()) > 0)
+    { // Update next earliest time before which *nothing* can issue.
+      nextEarliestIssueTime = max(nextEarliestIssueTime,
+		  curTime + 1 + schedInfo.numBubblesAfter(node->getOpCode()));
+    }
+  
+  const vector<MachineOpCode>*
+    conflictVec = schedInfo.getConflictList(node->getOpCode());
+  
+  if (conflictVec != NULL)
+    for (unsigned i=0; i < conflictVec->size(); i++)
+      {
+	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;
+      }
+}
+
+//************************* 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)
+{
+  SchedGraphSet graphSet(method, target);	
+  
+  if (SchedDebugLevel >= Sched_PrintSchedGraphs)
+    {
+      cout << endl << "*** SCHEDULING GRAPHS FOR INSTRUCTION SCHEDULING"
+	   << endl;
+      graphSet.dump();
+    }
+  
+  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, graph, schedPrio);
+      
+      ChooseInstructionsForDelaySlots(S, bb, graph); // modifies graph
+      
+      ForwardListSchedule(S);			     // computes schedule in S
+      
+      RecordSchedule((*GI).first, S);		     // records schedule in BB
+    }
+  
+  if (SchedDebugLevel >= Sched_PrintMachineCode)
+    {
+      cout << endl
+	   << "*** Machine instructions after INSTRUCTION SCHEDULING" << endl;
+      PrintMachineInstructions(method);
+    }
+  
+  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)
+{
+  unsigned N;
+  const SchedGraphNode* node;
+  
+  S.schedPrio.initialize();
+  
+  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?");
+      
+      // 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);
+	  }
+      
+      // 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())));
+    }
+}
+
+
+// 
+// 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(const BasicBlock* bb, const SchedulingManager& S)
+{
+  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()))
+      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());
+  
+  InstrSchedule::const_iterator NIend = S.isched.end();
+  for (InstrSchedule::const_iterator NI = S.isched.begin(); NI != NIend; ++NI)
+    mvec.push_back((*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)
+    {
+      printIndent(2);
+      cout << "Cycle " << S.getTime() << " : Scheduled instructions:\n";
+      const InstrGroup* igroup = S.isched.getIGroup(S.getTime());
+      for (unsigned int s=0; s < S.nslots; s++)
+	{
+	  printIndent(4);
+	  if ((*igroup)[s] != NULL)
+	    cout << * ((*igroup)[s])->getMachineInstr() << endl;
+	  else
+	    cout << "<none>" << endl;
+	}
+    }
+  
+  return numIssued;
+}
+
+
+static void
+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)
+	&& ! S.schedPrio.nodeIsReady(*SI))
+      {// 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;
+	    }
+	
+	if (succIsReady)	// add the successor to the ready list
+	  S.schedPrio.insertReady(*SI);
+      }
+}
+
+
+// Choose up to `nslots' FEASIBLE instructions and assign each
+// 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());
+  for (int s = S.nslots - 1; s >= 0; s--)
+    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.
+  unsigned int indexForBreakingNode = S.nslots;
+  unsigned int indexForDelayedInstr = S.nslots;
+  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)
+	    {
+	      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 (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 && 
+      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;
+	  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?");
+      
+      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--)
+	if (S.schedInfo.instrCanUseSlot(delayOpCode, s))
+	  {