InstrSched is SparcV9-specific and so has been moved to lib/Target/SparcV9/

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

1 files changed, 0 insertions, 1499 deletions

diff --git a/lib/CodeGen/InstrSched/InstrScheduling.cpp b/lib/CodeGen/InstrSched/InstrScheduling.cpp
deleted file mode 100644
index 69ecb90f31..0000000000
--- a/lib/CodeGen/InstrSched/InstrScheduling.cpp
+++ /dev/null
@@ -1,1499 +0,0 @@
-//===- InstrScheduling.cpp - Generic Instruction Scheduling support -------===//
-// 
-//                     The LLVM Compiler Infrastructure
-//
-// This file was developed by the LLVM research group and is distributed under
-// the University of Illinois Open Source License. See LICENSE.TXT for details.
-// 
-//===----------------------------------------------------------------------===//
-//
-// This file implements the llvm/CodeGen/InstrScheduling.h interface, along with
-// generic support routines for instruction scheduling.
-//
-//===----------------------------------------------------------------------===//
-
-#include "SchedPriorities.h"
-#include "llvm/BasicBlock.h"
-#include "llvm/CodeGen/MachineInstr.h"
-#include "llvm/CodeGen/MachineFunction.h"
-#include "llvm/Target/TargetMachine.h"
-#include "../../Target/SparcV9/MachineCodeForInstruction.h"
-#include "../../Target/SparcV9/LiveVar/FunctionLiveVarInfo.h"
-#include "../../Target/SparcV9/SparcV9InstrInfo.h"
-#include "llvm/Support/CommandLine.h"
-#include <algorithm>
-#include <iostream>
-
-namespace llvm {
-
-SchedDebugLevel_t SchedDebugLevel;
-
-static cl::opt<bool> EnableFillingDelaySlots("sched-fill-delay-slots",
-              cl::desc("Fill branch delay slots during local scheduling"));
-
-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"),
-                   clEnumValEnd));
-
-
-//************************* Internal Data Types *****************************/
-
-class InstrSchedule;
-class SchedulingManager;
-
-
-//----------------------------------------------------------------------
-// class InstrGroup:
-// 
-// Represents a group of instructions scheduled to be issued
-// in a single cycle.
-//----------------------------------------------------------------------
-
-class InstrGroup {
-  InstrGroup(const InstrGroup&);       // DO NOT IMPLEMENT
-  void operator=(const InstrGroup&);   // DO NOT IMPLEMENT
-  
-public:
-  inline const SchedGraphNode* operator[](unsigned int slotNum) const {
-    assert(slotNum  < group.size());
-    return group[slotNum];
-  }
-  
-private:
-  friend class InstrSchedule;
-  
-  inline void	addInstr(const SchedGraphNode* node, unsigned int slotNum) {
-    assert(slotNum < group.size());
-    group[slotNum] = node;
-  }
-  
-  /*ctor*/	InstrGroup(unsigned int nslots)
-    : group(nslots, NULL) {}
-  
-  /*ctor*/	InstrGroup();		// disable: DO NOT IMPLEMENT
-  
-private:
-  std::vector<const SchedGraphNode*> group;
-};
-
-
-//----------------------------------------------------------------------
-// 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 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;
-  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 {
-  const unsigned int nslots;
-  unsigned int numInstr;
-  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()       { return iterator::begin(*this); }
-  const_iterator begin() const { return const_iterator::begin(*this); }
-        iterator end()         { return iterator::end(*this); }
-  const_iterator end() const   { return const_iterator::end(*this); }
-  
-public: // constructors and destructor
-  /*ctor*/		InstrSchedule	(unsigned int _nslots,
-					 unsigned int _numNodes);
-  /*dtor*/		~InstrSchedule	();
-  
-public: // accessor functions to query chosen schedule
-  const SchedGraphNode* getInstr	(unsigned int slotNum,
-					 cycles_t c) const {
-    const InstrGroup* igroup = this->getIGroup(c);
-    return (igroup == NULL)? NULL : (*igroup)[slotNum];
-  }
-  
-  inline InstrGroup*	getIGroup	(cycles_t c) {
-    if ((unsigned)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((unsigned)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);
-    if (!((*igroup)[slotNum] == NULL)) {
-      std::cerr << "Slot already filled?\n";
-      abort();
-    }
-    igroup->addInstr(node, slotNum);
-    assert(node->getNodeId() < startTime.size());
-    startTime[node->getNodeId()] = cycle;
-    ++numInstr;
-  }
-  
-private:
-  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)
-  : 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);
-}
-
-
-//----------------------------------------------------------------------
-// class DelaySlotInfo:
-// 
-// Record information about delay slots for a single branch instruction.
-// Delay slots are simply indexed by slot number 1 ... numDelaySlots
-//----------------------------------------------------------------------
-
-class DelaySlotInfo {
-  const SchedGraphNode* brNode;
-  unsigned ndelays;
-  std::vector<const SchedGraphNode*> delayNodeVec;
-  cycles_t delayedNodeCycle;
-  unsigned delayedNodeSlotNum;
-  
-  DelaySlotInfo(const DelaySlotInfo &);  // DO NOT IMPLEMENT
-  void operator=(const DelaySlotInfo&);  // DO NOT IMPLEMENT
-public:
-  /*ctor*/	DelaySlotInfo		(const SchedGraphNode* _brNode,
-					 unsigned _ndelays)
-    : brNode(_brNode), ndelays(_ndelays),
-      delayedNodeCycle(0), delayedNodeSlotNum(0) {}
-  
-  inline unsigned getNumDelays	() {
-    return ndelays;
-  }
-  
-  inline const std::vector<const SchedGraphNode*>& getDelayNodeVec() {
-    return delayNodeVec;
-  }
-  
-  inline void	addDelayNode		(const SchedGraphNode* node) {
-    delayNodeVec.push_back(node);
-    assert(delayNodeVec.size() <= ndelays && "Too many delay slot instrs!");
-  }
-  
-  inline void	recordChosenSlot	(cycles_t cycle, unsigned slotNum) {
-    delayedNodeCycle = cycle;
-    delayedNodeSlotNum = slotNum;
-  }
-  
-  unsigned	scheduleDelayedNode	(SchedulingManager& S);
-};
-
-
-//----------------------------------------------------------------------
-// class SchedulingManager:
-// 
-// Represents the schedule of machine instructions for a single basic block.
-//----------------------------------------------------------------------
-
-class SchedulingManager {
-  SchedulingManager(SchedulingManager &);    // DO NOT IMPLEMENT
-  void operator=(const SchedulingManager &); // DO NOT IMPLEMENT
-public: // publicly accessible data members
-  const unsigned nslots;
-  const TargetSchedInfo& schedInfo;
-  SchedPriorities& schedPrio;
-  InstrSchedule isched;
-  
-private:
-  unsigned totalInstrCount;
-  cycles_t curTime;
-  cycles_t nextEarliestIssueTime;		// next cycle we can issue
-  // 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:
-  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 TargetInstrInfo& 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 < 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 < 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 < numInClass.size());
-    numInClass[sc]--;
-  }
-
-  //----------------------------------------------------------------------
-  // Create and retrieve delay slot info for delayed instructions
-  //----------------------------------------------------------------------
-  
-  inline DelaySlotInfo* getDelaySlotInfoForInstr(const SchedGraphNode* bn,
-						 bool createIfMissing=false)
-  {
-    hash_map<const SchedGraphNode*, DelaySlotInfo*>::const_iterator
-      I = delaySlotInfoForBranches.find(bn);
-    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:
-  SchedulingManager();     // DISABLED: 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()->getNumOpcodes(),
-			  (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 = std::max(nextEarliestIssueTime,
-		  curTime + 1 + schedInfo.numBubblesAfter(node->getOpcode()));
-    }
-  
-  const std::vector<MachineOpCode>&
-    conflictVec = schedInfo.getConflictList(node->getOpcode());
-  
-  for (unsigned i=0; i < conflictVec.size(); i++)
-    {
-      MachineOpCode toOp = conflictVec[i];
-      cycles_t est=schedTime + schedInfo.getMinIssueGap(node->getOpcode(),toOp);
-      assert(toOp < (int) nextEarliestStartTime.size());
-      if (nextEarliestStartTime[toOp] < est)
-        nextEarliestStartTime[toOp] = est;
-    }
-}
-
-//************************* Internal Functions *****************************/
-
-
-static void
-AssignInstructionsToSlots(class SchedulingManager& S, unsigned maxIssue)
-{
-  // find the slot to start from, in the current cycle
-  unsigned int startSlot = 0;
-  cycles_t curTime = S.getTime();
-  
-  assert(maxIssue > 0 && maxIssue <= S.nslots - startSlot);
-  
-  // If only one instruction can be issued, do so.
-  if (maxIssue == 1)
-    for (unsigned s=startSlot; s < S.nslots; s++)
-      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;
-      }
-      
-    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);
-    }
-  }
-  
-  assert(numIssued > 0 && "Should not happen when maxIssue > 0!");
-}
-
-
-// 
-// For now, just assume we are scheduling within a single basic block.
-// Get the machine instruction vector for the basic block and clear it,
-// then append instructions in scheduled order.
-// Also, re-insert the dummy PHI instructions that were at the beginning
-// of the basic block, since they are not part of the schedule.
-//   
-static void
-RecordSchedule(MachineBasicBlock &MBB, const SchedulingManager& S)
-{
-  const TargetInstrInfo& mii = S.schedInfo.getInstrInfo();
-  
-  // Lets make sure we didn't lose any instructions, except possibly
-  // some NOPs from delay slots.  Also, PHIs are not included in the schedule.
-  unsigned numInstr = 0;
-  for (MachineBasicBlock::iterator I=MBB.begin(); I != MBB.end(); ++I)
-    if (!(I->getOpcode() == V9::NOP || I->getOpcode() == V9::PHI))
-      ++numInstr;
-  assert(S.isched.getNumInstructions() >= numInstr &&
-	 "Lost some non-NOP instructions during scheduling!");
-  
-  if (S.isched.getNumInstructions() == 0)
-    return;				// empty basic block!
-  
-  // First find the dummy instructions at the start of the basic block
-  MachineBasicBlock::iterator I = MBB.begin();
-  for ( ; I != MBB.end(); ++I)
-    if (I->getOpcode() != V9::PHI)
-      break;
-  
-  // Remove all except the dummy PHI instructions from MBB, and
-  // pre-allocate create space for the ones we will put back in.
-  while (I != MBB.end())
-    MBB.remove(I++);
-  
-  InstrSchedule::const_iterator NIend = S.isched.end();
-  for (InstrSchedule::const_iterator NI = S.isched.begin(); NI != NIend; ++NI)
-    MBB.push_back(const_cast<MachineInstr*>((*NI)->getMachineInstr()));
-}
-
-
-
-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)) {
-        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)->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;
-          }
-	  
-      assert(s < S.nslots && "No feasible slot for instruction?");
-	  
-      highestSlotUsed = std::max(highestSlotUsed, (int) s);
-    }
-      
-    assert(highestSlotUsed <= (int) S.nslots-1 && "Invalid slot used?");
-      
-    // We will put the delayed node in the first slot after the
-    // highest slot used.  But we just mark that for now, and
-    // schedule it separately because we want to schedule the delay
-    // 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;
-  } 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->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)->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!
-          }
-		    
-          S.addChoiceToSlot(s, S.getChoice(i));
-        }
-	      
-      if (!foundLowerSlot)
-        breakingSlot = INT_MAX;		// disable breaking instr
-    }
-      
-    // Assign the breaking instruction (if any) to a single slot
-    // Otherwise, just ignore the instruction.  It will simply be
-    // scheduled in a later cycle.
-    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++) {
-      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 unsigned
-ChooseOneGroup(SchedulingManager& S)
-{
-  assert(S.schedPrio.getNumReady() > 0
-	 && "Don't get here without ready instructions.");
-  
-  cycles_t firstCycle = S.getTime();
-  DelaySlotInfo* getDelaySlotInfo = NULL;
-  
-  // Choose up to `nslots' feasible instructions and their possible slots.
-  unsigned numIssued = FindSlotChoices(S, getDelaySlotInfo);
-  
-  while (numIssued == 0) {
-    S.updateTime(S.getTime()+1);
-    numIssued = FindSlotChoices(S, getDelaySlotInfo);
-  }
-  
-  AssignInstructionsToSlots(S, numIssued);
-  
-  if (getDelaySlotInfo != NULL)
-    numIssued += getDelaySlotInfo->scheduleDelayedNode(S); 
-  
-  // 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";
-      }
-    }
-  }