lib/Target/SparcV9/InstrSched/InstrScheduling.cpp

   1 //===- InstrScheduling.cpp - Generic Instruction Scheduling support -------===//
   2 //
   3 // This file implements the llvm/CodeGen/InstrScheduling.h interface, along with
   4 // generic support routines for instruction scheduling.
   5 //
   6 //===----------------------------------------------------------------------===//
   7
   8 #include "SchedPriorities.h"
   9 #include "llvm/CodeGen/MachineInstr.h"
  10 #include "llvm/CodeGen/MachineCodeForInstruction.h"
  11 #include "llvm/CodeGen/MachineCodeForBasicBlock.h"
  12 #include "llvm/CodeGen/MachineCodeForMethod.h"
  13 #include "llvm/Analysis/LiveVar/FunctionLiveVarInfo.h" // FIXME: Remove when modularized better
  14 #include "llvm/Target/TargetMachine.h"
  15 #include "llvm/BasicBlock.h"
  16 #include "Support/CommandLine.h"
  17 #include <algorithm>
  18 using std::cerr;
  19 using std::vector;
  20
  21 SchedDebugLevel_t SchedDebugLevel;
  22
  23 static cl::opt<SchedDebugLevel_t, true>
  24 SDL_opt("dsched", cl::Hidden, cl::location(SchedDebugLevel),
  25         cl::desc("enable instruction scheduling debugging information"),
  26         cl::values(
  27  clEnumValN(Sched_NoDebugInfo,      "n", "disable debug output"),
  28  clEnumValN(Sched_PrintMachineCode, "y", "print machine code after scheduling"),
  29  clEnumValN(Sched_PrintSchedTrace,  "t", "print trace of scheduling actions"),
  30  clEnumValN(Sched_PrintSchedGraphs, "g", "print scheduling graphs"),
  31                    0));
  32
  33
  34 //************************* Internal Data Types *****************************/
  35
  36 class InstrSchedule;
  37 class SchedulingManager;
  38
  39
  40 //----------------------------------------------------------------------
  41 // class InstrGroup:
  42 //
  43 // Represents a group of instructions scheduled to be issued
  44 // in a single cycle.
  45 //----------------------------------------------------------------------
  46
  47 class InstrGroup: public NonCopyable {
  48 public:
  49   inline const SchedGraphNode* operator[](unsigned int slotNum) const {
  50     assert(slotNum  < group.size());
  51     return group[slotNum];
  52   }
  53
  54 private:
  55   friend class InstrSchedule;
  56
  57   inline void   addInstr(const SchedGraphNode* node, unsigned int slotNum) {
  58     assert(slotNum < group.size());
  59     group[slotNum] = node;
  60   }
  61
  62   /*ctor*/      InstrGroup(unsigned int nslots)
  63     : group(nslots, NULL) {}
  64
  65   /*ctor*/      InstrGroup();           // disable: DO NOT IMPLEMENT
  66
  67 private:
  68   vector<const SchedGraphNode*> group;
  69 };
  70
  71
  72 //----------------------------------------------------------------------
  73 // class ScheduleIterator:
  74 //
  75 // Iterates over the machine instructions in the for a single basic block.
  76 // The schedule is represented by an InstrSchedule object.
  77 //----------------------------------------------------------------------
  78
  79 template<class _NodeType>
  80 class ScheduleIterator : public forward_iterator<_NodeType, ptrdiff_t> {
  81 private:
  82   unsigned cycleNum;
  83   unsigned slotNum;
  84   const InstrSchedule& S;
  85 public:
  86   typedef ScheduleIterator<_NodeType> _Self;
  87
  88   /*ctor*/ inline ScheduleIterator(const InstrSchedule& _schedule,
  89                                    unsigned _cycleNum,
  90                                    unsigned _slotNum)
  91     : cycleNum(_cycleNum), slotNum(_slotNum), S(_schedule) {
  92     skipToNextInstr();
  93   }
  94
  95   /*ctor*/ inline ScheduleIterator(const _Self& x)
  96     : cycleNum(x.cycleNum), slotNum(x.slotNum), S(x.S) {}
  97
  98   inline bool operator==(const _Self& x) const {
  99     return (slotNum == x.slotNum && cycleNum== x.cycleNum && &S==&x.S);
 100   }
 101
 102   inline bool operator!=(const _Self& x) const { return !operator==(x); }
 103
 104   inline _NodeType* operator*() const {
 105     assert(cycleNum < S.groups.size());
 106     return (*S.groups[cycleNum])[slotNum];
 107   }
 108   inline _NodeType* operator->() const { return operator*(); }
 109
 110          _Self& operator++();                           // Preincrement
 111   inline _Self operator++(int) {                        // Postincrement
 112     _Self tmp(*this); ++*this; return tmp;
 113   }
 114
 115   static _Self begin(const InstrSchedule& _schedule);
 116   static _Self end(  const InstrSchedule& _schedule);
 117
 118 private:
 119   inline _Self& operator=(const _Self& x); // DISABLE -- DO NOT IMPLEMENT
 120   void  skipToNextInstr();
 121 };
 122
 123
 124 //----------------------------------------------------------------------
 125 // class InstrSchedule:
 126 //
 127 // Represents the schedule of machine instructions for a single basic block.
 128 //----------------------------------------------------------------------
 129
 130 class InstrSchedule: public NonCopyable {
 131 private:
 132   const unsigned int nslots;
 133   unsigned int numInstr;
 134   vector<InstrGroup*> groups;           // indexed by cycle number
 135   vector<cycles_t> startTime;           // indexed by node id
 136
 137 public: // iterators
 138   typedef ScheduleIterator<SchedGraphNode> iterator;
 139   typedef ScheduleIterator<const SchedGraphNode> const_iterator;
 140
 141         iterator begin();
 142   const_iterator begin() const;
 143         iterator end();
 144   const_iterator end()   const;
 145
 146 public: // constructors and destructor
 147   /*ctor*/              InstrSchedule   (unsigned int _nslots,
 148                                          unsigned int _numNodes);
 149   /*dtor*/              ~InstrSchedule  ();
 150
 151 public: // accessor functions to query chosen schedule
 152   const SchedGraphNode* getInstr        (unsigned int slotNum,
 153                                          cycles_t c) const {
 154     const InstrGroup* igroup = this->getIGroup(c);
 155     return (igroup == NULL)? NULL : (*igroup)[slotNum];
 156   }
 157
 158   inline InstrGroup*    getIGroup       (cycles_t c) {
 159     if ((unsigned)c >= groups.size())
 160       groups.resize(c+1);
 161     if (groups[c] == NULL)
 162       groups[c] = new InstrGroup(nslots);
 163     return groups[c];
 164   }
 165
 166   inline const InstrGroup* getIGroup    (cycles_t c) const {
 167     assert((unsigned)c < groups.size());
 168     return groups[c];
 169   }
 170
 171   inline cycles_t       getStartTime    (unsigned int nodeId) const {
 172     assert(nodeId < startTime.size());
 173     return startTime[nodeId];
 174   }
 175
 176   unsigned int          getNumInstructions() const {
 177     return numInstr;
 178   }
 179
 180   inline void           scheduleInstr   (const SchedGraphNode* node,
 181                                          unsigned int slotNum,
 182                                          cycles_t cycle) {
 183     InstrGroup* igroup = this->getIGroup(cycle);
 184     assert((*igroup)[slotNum] == NULL &&  "Slot already filled?");
 185     igroup->addInstr(node, slotNum);
 186     assert(node->getNodeId() < startTime.size());
 187     startTime[node->getNodeId()] = cycle;
 188     ++numInstr;
 189   }
 190
 191 private:
 192   friend class iterator;
 193   friend class const_iterator;
 194   /*ctor*/      InstrSchedule   ();     // Disable: DO NOT IMPLEMENT.
 195 };
 196
 197
 198 /*ctor*/
 199 InstrSchedule::InstrSchedule(unsigned int _nslots, unsigned int _numNodes)
 200   : nslots(_nslots),
 201     numInstr(0),
 202     groups(2 * _numNodes / _nslots),            // 2 x lower-bound for #cycles
 203     startTime(_numNodes, (cycles_t) -1)         // set all to -1
 204 {
 205 }
 206
 207
 208 /*dtor*/
 209 InstrSchedule::~InstrSchedule()
 210 {
 211   for (unsigned c=0, NC=groups.size(); c < NC; c++)
 212     if (groups[c] != NULL)
 213       delete groups[c];                 // delete InstrGroup objects
 214 }
 215
 216
 217 template<class _NodeType>
 218 inline
 219 void
 220 ScheduleIterator<_NodeType>::skipToNextInstr()
 221 {
 222   while(cycleNum < S.groups.size() && S.groups[cycleNum] == NULL)
 223     ++cycleNum;                 // skip cycles with no instructions
 224
 225   while (cycleNum < S.groups.size() &&
 226          (*S.groups[cycleNum])[slotNum] == NULL)
 227     {
 228       ++slotNum;
 229       if (slotNum == S.nslots)
 230         {
 231           ++cycleNum;
 232           slotNum = 0;
 233           while(cycleNum < S.groups.size() && S.groups[cycleNum] == NULL)
 234             ++cycleNum;                 // skip cycles with no instructions
 235         }
 236     }
 237 }
 238
 239 template<class _NodeType>
 240 inline
 241 ScheduleIterator<_NodeType>&
 242 ScheduleIterator<_NodeType>::operator++()       // Preincrement
 243 {
 244   ++slotNum;
 245   if (slotNum == S.nslots)
 246     {
 247       ++cycleNum;
 248       slotNum = 0;
 249     }
 250   skipToNextInstr();
 251   return *this;
 252 }
 253
 254 template<class _NodeType>
 255 ScheduleIterator<_NodeType>
 256 ScheduleIterator<_NodeType>::begin(const InstrSchedule& _schedule)
 257 {
 258   return _Self(_schedule, 0, 0);
 259 }
 260
 261 template<class _NodeType>
 262 ScheduleIterator<_NodeType>
 263 ScheduleIterator<_NodeType>::end(const InstrSchedule& _schedule)
 264 {
 265   return _Self(_schedule, _schedule.groups.size(), 0);
 266 }
 267
 268 InstrSchedule::iterator
 269 InstrSchedule::begin()
 270 {
 271   return iterator::begin(*this);
 272 }
 273
 274 InstrSchedule::const_iterator
 275 InstrSchedule::begin() const
 276 {
 277   return const_iterator::begin(*this);
 278 }
 279
 280 InstrSchedule::iterator
 281 InstrSchedule::end()
 282 {
 283   return iterator::end(*this);
 284 }
 285
 286 InstrSchedule::const_iterator
 287 InstrSchedule::end() const
 288 {
 289   return const_iterator::end(  *this);
 290 }
 291
 292
 293 //----------------------------------------------------------------------
 294 // class DelaySlotInfo:
 295 //
 296 // Record information about delay slots for a single branch instruction.
 297 // Delay slots are simply indexed by slot number 1 ... numDelaySlots
 298 //----------------------------------------------------------------------
 299
 300 class DelaySlotInfo: public NonCopyable {
 301 private:
 302   const SchedGraphNode* brNode;
 303   unsigned int ndelays;
 304   vector<const SchedGraphNode*> delayNodeVec;
 305   cycles_t delayedNodeCycle;
 306   unsigned int delayedNodeSlotNum;
 307
 308 public:
 309   /*ctor*/      DelaySlotInfo           (const SchedGraphNode* _brNode,
 310                                          unsigned _ndelays)
 311     : brNode(_brNode), ndelays(_ndelays),
 312       delayedNodeCycle(0), delayedNodeSlotNum(0) {}
 313
 314   inline unsigned getNumDelays  () {
 315     return ndelays;
 316   }
 317
 318   inline const vector<const SchedGraphNode*>& getDelayNodeVec() {
 319     return delayNodeVec;
 320   }
 321
 322   inline void   addDelayNode            (const SchedGraphNode* node) {
 323     delayNodeVec.push_back(node);
 324     assert(delayNodeVec.size() <= ndelays && "Too many delay slot instrs!");
 325   }
 326
 327   inline void   recordChosenSlot        (cycles_t cycle, unsigned slotNum) {
 328     delayedNodeCycle = cycle;
 329     delayedNodeSlotNum = slotNum;
 330   }
 331
 332   unsigned      scheduleDelayedNode     (SchedulingManager& S);
 333 };
 334
 335
 336 //----------------------------------------------------------------------
 337 // class SchedulingManager:
 338 //
 339 // Represents the schedule of machine instructions for a single basic block.
 340 //----------------------------------------------------------------------
 341
 342 class SchedulingManager: public NonCopyable {
 343 public: // publicly accessible data members
 344   const unsigned int nslots;
 345   const MachineSchedInfo& schedInfo;
 346   SchedPriorities& schedPrio;
 347   InstrSchedule isched;
 348
 349 private:
 350   unsigned int totalInstrCount;
 351   cycles_t curTime;
 352   cycles_t nextEarliestIssueTime;               // next cycle we can issue
 353   vector<hash_set<const SchedGraphNode*> > choicesForSlot; // indexed by slot#
 354   vector<const SchedGraphNode*> choiceVec;      // indexed by node ptr
 355   vector<int> numInClass;                       // indexed by sched class
 356   vector<cycles_t> nextEarliestStartTime;       // indexed by opCode
 357   hash_map<const SchedGraphNode*, DelaySlotInfo*> delaySlotInfoForBranches;
 358                                                 // indexed by branch node ptr
 359
 360 public:
 361   SchedulingManager(const TargetMachine& _target, const SchedGraph* graph,
 362                     SchedPriorities& schedPrio);
 363   ~SchedulingManager() {
 364     for (hash_map<const SchedGraphNode*,
 365            DelaySlotInfo*>::iterator I = delaySlotInfoForBranches.begin(),
 366            E = delaySlotInfoForBranches.end(); I != E; ++I)
 367       delete I->second;
 368   }
 369
 370   //----------------------------------------------------------------------
 371   // Simplify access to the machine instruction info
 372   //----------------------------------------------------------------------
 373
 374   inline const MachineInstrInfo& getInstrInfo   () const {
 375     return schedInfo.getInstrInfo();
 376   }
 377
 378   //----------------------------------------------------------------------
 379   // Interface for checking and updating the current time
 380   //----------------------------------------------------------------------
 381
 382   inline cycles_t       getTime                 () const {
 383     return curTime;
 384   }
 385
 386   inline cycles_t       getEarliestIssueTime() const {
 387     return nextEarliestIssueTime;
 388   }
 389
 390   inline cycles_t       getEarliestStartTimeForOp(MachineOpCode opCode) const {
 391     assert(opCode < (int) nextEarliestStartTime.size());
 392     return nextEarliestStartTime[opCode];
 393   }
 394
 395   // Update current time to specified cycle
 396   inline void   updateTime              (cycles_t c) {
 397     curTime = c;
 398     schedPrio.updateTime(c);
 399   }
 400
 401   //----------------------------------------------------------------------
 402   // Functions to manage the choices for the current cycle including:
 403   // -- a vector of choices by priority (choiceVec)
 404   // -- vectors of the choices for each instruction slot (choicesForSlot[])
 405   // -- number of choices in each sched class, used to check issue conflicts
 406   //    between choices for a single cycle
 407   //----------------------------------------------------------------------
 408
 409   inline unsigned int getNumChoices     () const {
 410     return choiceVec.size();
 411   }
 412
 413   inline unsigned getNumChoicesInClass  (const InstrSchedClass& sc) const {
 414     assert(sc < (int) numInClass.size() && "Invalid op code or sched class!");
 415     return numInClass[sc];
 416   }
 417
 418   inline const SchedGraphNode* getChoice(unsigned int i) const {
 419     // assert(i < choiceVec.size());    don't check here.
 420     return choiceVec[i];
 421   }
 422
 423   inline hash_set<const SchedGraphNode*>& getChoicesForSlot(unsigned slotNum) {
 424     assert(slotNum < nslots);
 425     return choicesForSlot[slotNum];
 426   }
 427
 428   inline void   addChoice               (const SchedGraphNode* node) {
 429     // Append the instruction to the vector of choices for current cycle.
 430     // Increment numInClass[c] for the sched class to which the instr belongs.
 431     choiceVec.push_back(node);
 432     const InstrSchedClass& sc = schedInfo.getSchedClass(node->getOpCode());
 433     assert(sc < (int) numInClass.size());
 434     numInClass[sc]++;
 435   }
 436
 437   inline void   addChoiceToSlot         (unsigned int slotNum,
 438                                          const SchedGraphNode* node) {
 439     // Add the instruction to the choice set for the specified slot
 440     assert(slotNum < nslots);
 441     choicesForSlot[slotNum].insert(node);
 442   }
 443
 444   inline void   resetChoices            () {
 445     choiceVec.clear();
 446     for (unsigned int s=0; s < nslots; s++)
 447       choicesForSlot[s].clear();
 448     for (unsigned int c=0; c < numInClass.size(); c++)
 449       numInClass[c] = 0;
 450   }
 451
 452   //----------------------------------------------------------------------
 453   // Code to query and manage the partial instruction schedule so far
 454   //----------------------------------------------------------------------
 455
 456   inline unsigned int   getNumScheduled () const {
 457     return isched.getNumInstructions();
 458   }
 459
 460   inline unsigned int   getNumUnscheduled() const {
 461     return totalInstrCount - isched.getNumInstructions();
 462   }
 463
 464   inline bool           isScheduled     (const SchedGraphNode* node) const {
 465     return (isched.getStartTime(node->getNodeId()) >= 0);
 466   }
 467
 468   inline void   scheduleInstr           (const SchedGraphNode* node,
 469                                          unsigned int slotNum,
 470                                          cycles_t cycle)
 471   {
 472     assert(! isScheduled(node) && "Instruction already scheduled?");
 473
 474     // add the instruction to the schedule
 475     isched.scheduleInstr(node, slotNum, cycle);
 476
 477     // update the earliest start times of all nodes that conflict with `node'
 478     // and the next-earliest time anything can issue if `node' causes bubbles
 479     updateEarliestStartTimes(node, cycle);
 480
 481     // remove the instruction from the choice sets for all slots
 482     for (unsigned s=0; s < nslots; s++)
 483       choicesForSlot[s].erase(node);
 484
 485     // and decrement the instr count for the sched class to which it belongs
 486     const InstrSchedClass& sc = schedInfo.getSchedClass(node->getOpCode());
 487     assert(sc < (int) numInClass.size());
 488     numInClass[sc]--;
 489   }
 490
 491   //----------------------------------------------------------------------
 492   // Create and retrieve delay slot info for delayed instructions
 493   //----------------------------------------------------------------------
 494
 495   inline DelaySlotInfo* getDelaySlotInfoForInstr(const SchedGraphNode* bn,
 496                                                  bool createIfMissing=false)
 497   {
 498     hash_map<const SchedGraphNode*, DelaySlotInfo*>::const_iterator
 499       I = delaySlotInfoForBranches.find(bn);
 500     if (I != delaySlotInfoForBranches.end())
 501       return I->second;
 502
 503     if (!createIfMissing) return 0;
 504
 505     DelaySlotInfo *dinfo =
 506       new DelaySlotInfo(bn, getInstrInfo().getNumDelaySlots(bn->getOpCode()));
 507     return delaySlotInfoForBranches[bn] = dinfo;
 508   }
 509
 510 private:
 511   SchedulingManager();     // DISABLED: DO NOT IMPLEMENT
 512   void updateEarliestStartTimes(const SchedGraphNode* node, cycles_t schedTime);
 513 };
 514
 515
 516 /*ctor*/
 517 SchedulingManager::SchedulingManager(const TargetMachine& target,
 518                                      const SchedGraph* graph,
 519                                      SchedPriorities& _schedPrio)
 520   : nslots(target.getSchedInfo().getMaxNumIssueTotal()),
 521     schedInfo(target.getSchedInfo()),
 522     schedPrio(_schedPrio),
 523     isched(nslots, graph->getNumNodes()),
 524     totalInstrCount(graph->getNumNodes() - 2),
 525     nextEarliestIssueTime(0),
 526     choicesForSlot(nslots),
 527     numInClass(target.getSchedInfo().getNumSchedClasses(), 0),  // set all to 0
 528     nextEarliestStartTime(target.getInstrInfo().getNumRealOpCodes(),
 529                           (cycles_t) 0)                         // set all to 0
 530 {
 531   updateTime(0);
 532
 533   // Note that an upper bound on #choices for each slot is = nslots since
 534   // we use this vector to hold a feasible set of instructions, and more
 535   // would be infeasible. Reserve that much memory since it is probably small.
 536   for (unsigned int i=0; i < nslots; i++)
 537     choicesForSlot[i].resize(nslots);
 538 }
 539
 540
 541 void
 542 SchedulingManager::updateEarliestStartTimes(const SchedGraphNode* node,
 543                                             cycles_t schedTime)
 544 {
 545   if (schedInfo.numBubblesAfter(node->getOpCode()) > 0)
 546     { // Update next earliest time before which *nothing* can issue.
 547       nextEarliestIssueTime = std::max(nextEarliestIssueTime,
 548                   curTime + 1 + schedInfo.numBubblesAfter(node->getOpCode()));
 549     }
 550
 551   const std::vector<MachineOpCode>&
 552     conflictVec = schedInfo.getConflictList(node->getOpCode());
 553
 554   for (unsigned i=0; i < conflictVec.size(); i++)
 555     {
 556       MachineOpCode toOp = conflictVec[i];
 557       cycles_t est=schedTime + schedInfo.getMinIssueGap(node->getOpCode(),toOp);
 558       assert(toOp < (int) nextEarliestStartTime.size());
 559       if (nextEarliestStartTime[toOp] < est)
 560         nextEarliestStartTime[toOp] = est;
 561     }
 562 }
 563
 564 //************************* Internal Functions *****************************/
 565
 566
 567 static void
 568 AssignInstructionsToSlots(class SchedulingManager& S, unsigned maxIssue)
 569 {
 570   // find the slot to start from, in the current cycle
 571   unsigned int startSlot = 0;
 572   cycles_t curTime = S.getTime();
 573
 574   assert(maxIssue > 0 && maxIssue <= S.nslots - startSlot);
 575
 576   // If only one instruction can be issued, do so.
 577   if (maxIssue == 1)
 578     for (unsigned s=startSlot; s < S.nslots; s++)
 579       if (S.getChoicesForSlot(s).size() > 0)
 580         {// found the one instruction
 581           S.scheduleInstr(*S.getChoicesForSlot(s).begin(), s, curTime);
 582           return;
 583         }
 584
 585   // Otherwise, choose from the choices for each slot
 586   //
 587   InstrGroup* igroup = S.isched.getIGroup(S.getTime());
 588   assert(igroup != NULL && "Group creation failed?");
 589
 590   // Find a slot that has only a single choice, and take it.
 591   // If all slots have 0 or multiple choices, pick the first slot with
 592   // choices and use its last instruction (just to avoid shifting the vector).
 593   unsigned numIssued;
 594   for (numIssued = 0; numIssued < maxIssue; numIssued++)
 595     {
 596       int chosenSlot = -1;
 597       for (unsigned s=startSlot; s < S.nslots; s++)
 598         if ((*igroup)[s] == NULL && S.getChoicesForSlot(s).size() == 1)
 599           {
 600             chosenSlot = (int) s;
 601             break;
 602           }
 603
 604       if (chosenSlot == -1)
 605         for (unsigned s=startSlot; s < S.nslots; s++)
 606           if ((*igroup)[s] == NULL && S.getChoicesForSlot(s).size() > 0)
 607             {
 608               chosenSlot = (int) s;
 609               break;
 610             }
 611
 612       if (chosenSlot != -1)
 613         { // Insert the chosen instr in the chosen slot and
 614           // erase it from all slots.
 615           const SchedGraphNode* node= *S.getChoicesForSlot(chosenSlot).begin();
 616           S.scheduleInstr(node, chosenSlot, curTime);
 617         }
 618     }
 619
 620   assert(numIssued > 0 && "Should not happen when maxIssue > 0!");
 621 }
 622
 623
 624 //
 625 // For now, just assume we are scheduling within a single basic block.
 626 // Get the machine instruction vector for the basic block and clear it,
 627 // then append instructions in scheduled order.
 628 // Also, re-insert the dummy PHI instructions that were at the beginning
 629 // of the basic block, since they are not part of the schedule.
 630 //
 631 static void
 632 RecordSchedule(const BasicBlock* bb, const SchedulingManager& S)
 633 {
 634   MachineCodeForBasicBlock& mvec = MachineCodeForBasicBlock::get(bb);
 635   const MachineInstrInfo& mii = S.schedInfo.getInstrInfo();
 636
 637 #ifndef NDEBUG
 638   // Lets make sure we didn't lose any instructions, except possibly
 639   // some NOPs from delay slots.  Also, PHIs are not included in the schedule.
 640   unsigned numInstr = 0;
 641   for (MachineCodeForBasicBlock::iterator I=mvec.begin(); I != mvec.end(); ++I)
 642     if (! mii.isNop((*I)->getOpCode()) &&
 643         ! mii.isDummyPhiInstr((*I)->getOpCode()))
 644       ++numInstr;
 645   assert(S.isched.getNumInstructions() >= numInstr &&
 646          "Lost some non-NOP instructions during scheduling!");
 647 #endif
 648
 649   if (S.isched.getNumInstructions() == 0)
 650     return;                             // empty basic block!
 651
 652   // First find the dummy instructions at the start of the basic block
 653   MachineCodeForBasicBlock::iterator I = mvec.begin();
 654   for ( ; I != mvec.end(); ++I)
 655     if (! mii.isDummyPhiInstr((*I)->getOpCode()))
 656       break;
 657
 658   // Erase all except the dummy PHI instructions from mvec, and
 659   // pre-allocate create space for the ones we will put back in.
 660   mvec.erase(I, mvec.end());
 661
 662   InstrSchedule::const_iterator NIend = S.isched.end();
 663   for (InstrSchedule::const_iterator NI = S.isched.begin(); NI != NIend; ++NI)
 664     mvec.push_back(const_cast<MachineInstr*>((*NI)->getMachineInstr()));
 665 }
 666
 667
 668
 669 static void
 670 MarkSuccessorsReady(SchedulingManager& S, const SchedGraphNode* node)
 671 {
 672   // Check if any successors are now ready that were not already marked
 673   // ready before, and that have not yet been scheduled.
 674   //
 675   for (sg_succ_const_iterator SI = succ_begin(node); SI !=succ_end(node); ++SI)
 676     if (! (*SI)->isDummyNode()
 677         && ! S.isScheduled(*SI)
 678         && ! S.schedPrio.nodeIsReady(*SI))
 679       {// successor not scheduled and not marked ready; check *its* preds.
 680
 681         bool succIsReady = true;
 682         for (sg_pred_const_iterator P=pred_begin(*SI); P != pred_end(*SI); ++P)
 683           if (! (*P)->isDummyNode()
 684               && ! S.isScheduled(*P))
 685             {
 686               succIsReady = false;
 687               break;
 688             }
 689
 690         if (succIsReady)        // add the successor to the ready list
 691           S.schedPrio.insertReady(*SI);
 692       }
 693 }
 694
 695
 696 // Choose up to `nslots' FEASIBLE instructions and assign each
 697 // instruction to all possible slots that do not violate feasibility.
 698 // FEASIBLE means it should be guaranteed that the set
 699 // of chosen instructions can be issued in a single group.
 700 //
 701 // Return value:
 702 //      maxIssue : total number of feasible instructions
 703 //      S.choicesForSlot[i=0..nslots] : set of instructions feasible in slot i
 704 //
 705 static unsigned
 706 FindSlotChoices(SchedulingManager& S,
 707                 DelaySlotInfo*& getDelaySlotInfo)
 708 {
 709   // initialize result vectors to empty
 710   S.resetChoices();
 711
 712   // find the slot to start from, in the current cycle
 713   unsigned int startSlot = 0;
 714   InstrGroup* igroup = S.isched.getIGroup(S.getTime());
 715   for (int s = S.nslots - 1; s >= 0; s--)
 716     if ((*igroup)[s] != NULL)
 717       {
 718         startSlot = s+1;
 719         break;
 720       }
 721
 722   // Make sure we pick at most one instruction that would break the group.
 723   // Also, if we do pick one, remember which it was.
 724   unsigned int indexForBreakingNode = S.nslots;
 725   unsigned int indexForDelayedInstr = S.nslots;
 726   DelaySlotInfo* delaySlotInfo = NULL;
 727
 728   getDelaySlotInfo = NULL;
 729
 730   // Choose instructions in order of priority.
 731   // Add choices to the choice vector in the SchedulingManager class as
 732   // we choose them so that subsequent choices will be correctly tested
 733   // for feasibility, w.r.t. higher priority choices for the same cycle.
 734   //
 735   while (S.getNumChoices() < S.nslots - startSlot)
 736     {
 737       const SchedGraphNode* nextNode=S.schedPrio.getNextHighest(S,S.getTime());
 738       if (nextNode == NULL)
 739         break;                  // no more instructions for this cycle
 740
 741       if (S.getInstrInfo().getNumDelaySlots(nextNode->getOpCode()) > 0)
 742         {
 743           delaySlotInfo = S.getDelaySlotInfoForInstr(nextNode);
 744           if (delaySlotInfo != NULL)
 745             {
 746               if (indexForBreakingNode < S.nslots)
 747                 // cannot issue a delayed instr in the same cycle as one
 748                 // that breaks the issue group or as another delayed instr
 749                 nextNode = NULL;
 750               else
 751                 indexForDelayedInstr = S.getNumChoices();
 752             }
 753         }
 754       else if (S.schedInfo.breaksIssueGroup(nextNode->getOpCode()))
 755         {
 756           if (indexForBreakingNode < S.nslots)
 757             // have a breaking instruction already so throw this one away
 758             nextNode = NULL;
 759           else
 760             indexForBreakingNode = S.getNumChoices();
 761         }
 762
 763       if (nextNode != NULL)
 764         {
 765           S.addChoice(nextNode);
 766
 767           if (S.schedInfo.isSingleIssue(nextNode->getOpCode()))
 768             {
 769               assert(S.getNumChoices() == 1 &&
 770                      "Prioritizer returned invalid instr for this cycle!");
 771               break;
 772             }
 773         }
 774
 775       if (indexForDelayedInstr < S.nslots)
 776         break;                  // leave the rest for delay slots
 777     }
 778
 779   assert(S.getNumChoices() <= S.nslots);
 780   assert(! (indexForDelayedInstr < S.nslots &&
 781             indexForBreakingNode < S.nslots) && "Cannot have both in a cycle");
 782
 783   // Assign each chosen instruction to all possible slots for that instr.
 784   // But if only one instruction was chosen, put it only in the first
 785   // feasible slot; no more analysis will be needed.
 786   //
 787   if (indexForDelayedInstr >= S.nslots &&
 788       indexForBreakingNode >= S.nslots)
 789     { // No instructions that break the issue group or that have delay slots.
 790       // This is the common case, so handle it separately for efficiency.
 791
 792       if (S.getNumChoices() == 1)
 793         {
 794           MachineOpCode opCode = S.getChoice(0)->getOpCode();
 795           unsigned int s;
 796           for (s=startSlot; s < S.nslots; s++)
 797             if (S.schedInfo.instrCanUseSlot(opCode, s))
 798               break;
 799           assert(s < S.nslots && "No feasible slot for this opCode?");
 800           S.addChoiceToSlot(s, S.getChoice(0));
 801         }
 802       else
 803         {
 804           for (unsigned i=0; i < S.getNumChoices(); i++)
 805             {
 806               MachineOpCode opCode = S.getChoice(i)->getOpCode();
 807               for (unsigned int s=startSlot; s < S.nslots; s++)
 808                 if (S.schedInfo.instrCanUseSlot(opCode, s))
 809                   S.addChoiceToSlot(s, S.getChoice(i));
 810             }
 811         }
 812     }
 813   else if (indexForDelayedInstr < S.nslots)
 814     {
 815       // There is an instruction that needs delay slots.
 816       // Try to assign that instruction to a higher slot than any other
 817       // instructions in the group, so that its delay slots can go
 818       // right after it.
 819       //
 820
 821       assert(indexForDelayedInstr == S.getNumChoices() - 1 &&
 822              "Instruction with delay slots should be last choice!");
 823       assert(delaySlotInfo != NULL && "No delay slot info for instr?");
 824
 825       const SchedGraphNode* delayedNode = S.getChoice(indexForDelayedInstr);
 826       MachineOpCode delayOpCode = delayedNode->getOpCode();
 827       unsigned ndelays= S.getInstrInfo().getNumDelaySlots(delayOpCode);
 828
 829       unsigned delayedNodeSlot = S.nslots;
 830       int highestSlotUsed;
 831
 832       // Find the last possible slot for the delayed instruction that leaves
 833       // at least `d' slots vacant after it (d = #delay slots)
 834       for (int s = S.nslots-ndelays-1; s >= (int) startSlot; s--)
 835         if (S.schedInfo.instrCanUseSlot(delayOpCode, s))
 836           {
 837             delayedNodeSlot = s;
 838             break;
 839           }
 840
 841       highestSlotUsed = -1;
 842       for (unsigned i=0; i < S.getNumChoices() - 1; i++)
 843         {
 844           // Try to assign every other instruction to a lower numbered
 845           // slot than delayedNodeSlot.
 846           MachineOpCode opCode =S.getChoice(i)->getOpCode();
 847           bool noSlotFound = true;
 848           unsigned int s;
 849           for (s=startSlot; s < delayedNodeSlot; s++)
 850             if (S.schedInfo.instrCanUseSlot(opCode, s))
 851               {
 852                 S.addChoiceToSlot(s, S.getChoice(i));
 853                 noSlotFound = false;
 854               }
 855
 856           // No slot before `delayedNodeSlot' was found for this opCode
 857           // Use a later slot, and allow some delay slots to fall in
 858           // the next cycle.
 859           if (noSlotFound)
 860             for ( ; s < S.nslots; s++)
 861               if (S.schedInfo.instrCanUseSlot(opCode, s))
 862                 {
 863                   S.addChoiceToSlot(s, S.getChoice(i));
 864                   break;
 865                 }
 866
 867           assert(s < S.nslots && "No feasible slot for instruction?");
 868
 869           highestSlotUsed = std::max(highestSlotUsed, (int) s);
 870         }
 871
 872       assert(highestSlotUsed <= (int) S.nslots-1 && "Invalid slot used?");
 873
 874       // We will put the delayed node in the first slot after the
 875       // highest slot used.  But we just mark that for now, and
 876       // schedule it separately because we want to schedule the delay
 877       // slots for the node at the same time.
 878       cycles_t dcycle = S.getTime();
 879       unsigned int dslot = highestSlotUsed + 1;
 880       if (dslot == S.nslots)
 881         {
 882           dslot = 0;
 883           ++dcycle;
 884         }
 885       delaySlotInfo->recordChosenSlot(dcycle, dslot);
 886       getDelaySlotInfo = delaySlotInfo;
 887     }
 888   else
 889     { // There is an instruction that breaks the issue group.
 890       // For such an instruction, assign to the last possible slot in
 891       // the current group, and then don't assign any other instructions
 892       // to later slots.
 893       assert(indexForBreakingNode < S.nslots);
 894       const SchedGraphNode* breakingNode=S.getChoice(indexForBreakingNode);
 895       unsigned breakingSlot = INT_MAX;
 896       unsigned int nslotsToUse = S.nslots;
 897
 898       // Find the last possible slot for this instruction.
 899       for (int s = S.nslots-1; s >= (int) startSlot; s--)
 900         if (S.schedInfo.instrCanUseSlot(breakingNode->getOpCode(), s))
 901           {
 902             breakingSlot = s;
 903             break;
 904           }
 905       assert(breakingSlot < S.nslots &&
 906              "No feasible slot for `breakingNode'?");
 907
 908       // Higher priority instructions than the one that breaks the group:
 909       // These can be assigned to all slots, but will be assigned only
 910       // to earlier slots if possible.
 911       for (unsigned i=0;
 912            i < S.getNumChoices() && i < indexForBreakingNode; i++)
 913         {
 914           MachineOpCode opCode =S.getChoice(i)->getOpCode();
 915
 916           // If a higher priority instruction cannot be assigned to
 917           // any earlier slots, don't schedule the breaking instruction.
 918           //
 919           bool foundLowerSlot = false;
 920           nslotsToUse = S.nslots;           // May be modified in the loop
 921           for (unsigned int s=startSlot; s < nslotsToUse; s++)
 922             if (S.schedInfo.instrCanUseSlot(opCode, s))
 923               {
 924                 if (breakingSlot < S.nslots && s < breakingSlot)
 925                   {
 926                     foundLowerSlot = true;
 927                     nslotsToUse = breakingSlot; // RESETS LOOP UPPER BOUND!
 928                   }
 929
 930                 S.addChoiceToSlot(s, S.getChoice(i));
 931               }
 932
 933           if (!foundLowerSlot)
 934             breakingSlot = INT_MAX;             // disable breaking instr
 935         }
 936
 937       // Assign the breaking instruction (if any) to a single slot
 938       // Otherwise, just ignore the instruction.  It will simply be
 939       // scheduled in a later cycle.
 940       if (breakingSlot < S.nslots)
 941         {
 942           S.addChoiceToSlot(breakingSlot, breakingNode);
 943           nslotsToUse = breakingSlot;
 944         }
 945       else
 946         nslotsToUse = S.nslots;
 947
 948       // For lower priority instructions than the one that breaks the
 949       // group, only assign them to slots lower than the breaking slot.
 950       // Otherwise, just ignore the instruction.
 951       for (unsigned i=indexForBreakingNode+1; i < S.getNumChoices(); i++)
 952         {
 953           MachineOpCode opCode = S.getChoice(i)->getOpCode();
 954           for (unsigned int s=startSlot; s < nslotsToUse; s++)
 955             if (S.schedInfo.instrCanUseSlot(opCode, s))
 956               S.addChoiceToSlot(s, S.getChoice(i));
 957         }
 958     } // endif (no delay slots and no breaking slots)
 959
 960   return S.getNumChoices();
 961 }
 962
 963
 964 static unsigned
 965 ChooseOneGroup(SchedulingManager& S)
 966 {
 967   assert(S.schedPrio.getNumReady() > 0
 968          && "Don't get here without ready instructions.");
 969
 970   cycles_t firstCycle = S.getTime();
 971   DelaySlotInfo* getDelaySlotInfo = NULL;
 972
 973   // Choose up to `nslots' feasible instructions and their possible slots.
 974   unsigned numIssued = FindSlotChoices(S, getDelaySlotInfo);
 975
 976   while (numIssued == 0)
 977     {
 978       S.updateTime(S.getTime()+1);
 979       numIssued = FindSlotChoices(S, getDelaySlotInfo);
 980     }
 981
 982   AssignInstructionsToSlots(S, numIssued);
 983
 984   if (getDelaySlotInfo != NULL)
 985     numIssued += getDelaySlotInfo->scheduleDelayedNode(S);
 986
 987   // Print trace of scheduled instructions before newly ready ones
 988   if (SchedDebugLevel >= Sched_PrintSchedTrace)
 989     {
 990       for (cycles_t c = firstCycle; c <= S.getTime(); c++)
 991         {
 992           cerr << "    Cycle " << (long)c << " : Scheduled instructions:\n";
 993           const InstrGroup* igroup = S.isched.getIGroup(c);
 994           for (unsigned int s=0; s < S.nslots; s++)
 995             {
 996               cerr << "        ";
 997               if ((*igroup)[s] != NULL)
 998                 cerr << * ((*igroup)[s])->getMachineInstr() << "\n";
 999               else
1000                 cerr << "<none>\n";
1001             }
1002         }
1003     }
1004
1005   return numIssued;
1006 }
1007
1008
1009 static void
1010 ForwardListSchedule(SchedulingManager& S)
1011 {
1012   unsigned N;
1013   const SchedGraphNode* node;
1014
1015   S.schedPrio.initialize();
1016
1017   while ((N = S.schedPrio.getNumReady()) > 0)
1018     {
1019       cycles_t nextCycle = S.getTime();
1020
1021       // Choose one group of instructions for a cycle, plus any delay slot
1022       // instructions (which may overflow into successive cycles).
1023       // This will advance S.getTime() to the last cycle in which
1024       // instructions are actually issued.
1025       //
1026       unsigned numIssued = ChooseOneGroup(S);
1027       assert(numIssued > 0 && "Deadlock in list scheduling algorithm?");
1028
1029       // Notify the priority manager of scheduled instructions and mark
1030       // any successors that may now be ready
1031       //
1032       for (cycles_t c = nextCycle; c <= S.getTime(); c++)
1033         {
1034           const InstrGroup* igroup = S.isched.getIGroup(c);
1035           for (unsigned int s=0; s < S.nslots; s++)
1036             if ((node = (*igroup)[s]) != NULL)
1037               {
1038                 S.schedPrio.issuedReadyNodeAt(S.getTime(), node);
1039                 MarkSuccessorsReady(S, node);
1040               }
1041         }
1042
1043       // Move to the next the next earliest cycle for which
1044       // an instruction can be issued, or the next earliest in which
1045       // one will be ready, or to the next cycle, whichever is latest.
1046       //
1047       S.updateTime(std::max(S.getTime() + 1,
1048                             std::max(S.getEarliestIssueTime(),
1049                                      S.schedPrio.getEarliestReadyTime())));
1050     }
1051 }
1052
1053
1054 //---------------------------------------------------------------------
1055 // Code for filling delay slots for delayed terminator instructions
1056 // (e.g., BRANCH and RETURN).  Delay slots for non-terminator
1057 // instructions (e.g., CALL) are not handled here because they almost
1058 // always can be filled with instructions from the call sequence code
1059 // before a call.  That's preferable because we incur many tradeoffs here
1060 // when we cannot find single-cycle instructions that can be reordered.
1061 //----------------------------------------------------------------------
1062
1063 static bool
1064 NodeCanFillDelaySlot(const SchedulingManager& S,
1065                      const SchedGraphNode* node,
1066                      const SchedGraphNode* brNode,
1067                      bool nodeIsPredecessor)
1068 {
1069   assert(! node->isDummyNode());
1070
1071   // don't put a branch in the delay slot of another branch
1072   if (S.getInstrInfo().isBranch(node->getOpCode()))
1073     return false;
1074
1075   // don't put a single-issue instruction in the delay slot of a branch
1076   if (S.schedInfo.isSingleIssue(node->getOpCode()))
1077     return false;
1078
1079   // don't put a load-use dependence in the delay slot of a branch
1080   const MachineInstrInfo& mii = S.getInstrInfo();
1081
1082   for (SchedGraphNode::const_iterator EI = node->beginInEdges();
1083        EI != node->endInEdges(); ++EI)
1084     if (! (*EI)->getSrc()->isDummyNode()
1085         && mii.isLoad((*EI)->getSrc()->getOpCode())
1086         && (*EI)->getDepType() == SchedGraphEdge::CtrlDep)
1087       return false;
1088
1089   // for now, don't put an instruction that does not have operand
1090   // interlocks in the delay slot of a branch
1091   if (! S.getInstrInfo().hasOperandInterlock(node->getOpCode()))
1092     return false;
1093
1094   // Finally, if the instruction preceeds the branch, we make sure the
1095   // instruction can be reordered relative to the branch.  We simply check
1096   // if the instr. has only 1 outgoing edge, viz., a CD edge to the branch.
1097   //
1098   if (nodeIsPredecessor)
1099     {
1100       bool onlyCDEdgeToBranch = true;
1101       for (SchedGraphNode::const_iterator OEI = node->beginOutEdges();
1102            OEI != node->endOutEdges(); ++OEI)
1103         if (! (*OEI)->getSink()->isDummyNode()
1104             && ((*OEI)->getSink() != brNode
1105                 || (*OEI)->getDepType() != SchedGraphEdge::CtrlDep))
1106           {
1107             onlyCDEdgeToBranch = false;
1108             break;
1109           }
1110
1111       if (!onlyCDEdgeToBranch)
1112         return false;
1113     }
1114
1115   return true;
1116 }
1117
1118
1119 static void
1120 MarkNodeForDelaySlot(SchedulingManager& S,
1121                      SchedGraph* graph,
1122                      SchedGraphNode* node,
1123                      const SchedGraphNode* brNode,
1124                      bool nodeIsPredecessor)
1125 {
1126   if (nodeIsPredecessor)
1127     { // If node is in the same basic block (i.e., preceeds brNode),
1128       // remove it and all its incident edges from the graph.  Make sure we
1129       // add dummy edges for pred/succ nodes that become entry/exit nodes.
1130       graph->eraseIncidentEdges(node, /*addDummyEdges*/ true);
1131     }
1132   else
1133     { // If the node was from a target block, add the node to the graph
1134       // and add a CD edge from brNode to node.
1135       assert(0 && "NOT IMPLEMENTED YET");
1136     }
1137
1138   DelaySlotInfo* dinfo = S.getDelaySlotInfoForInstr(brNode, /*create*/ true);
1139   dinfo->addDelayNode(node);
1140 }
1141
1142
1143 void
1144 FindUsefulInstructionsForDelaySlots(SchedulingManager& S,
1145                                     SchedGraphNode* brNode,
1146                                     vector<SchedGraphNode*>& sdelayNodeVec)
1147 {
1148   const MachineInstrInfo& mii = S.getInstrInfo();
1149   unsigned ndelays =
1150     mii.getNumDelaySlots(brNode->getOpCode());
1151
1152   if (ndelays == 0)
1153     return;
1154
1155   sdelayNodeVec.reserve(ndelays);
1156
1157   // Use a separate vector to hold the feasible multi-cycle nodes.
1158   // These will be used if not enough single-cycle nodes are found.
1159   //
1160   vector<SchedGraphNode*> mdelayNodeVec;
1161
1162   for (sg_pred_iterator P = pred_begin(brNode);
1163        P != pred_end(brNode) && sdelayNodeVec.size() < ndelays; ++P)
1164     if (! (*P)->isDummyNode() &&
1165         ! mii.isNop((*P)->getOpCode()) &&
1166         NodeCanFillDelaySlot(S, *P, brNode, /*pred*/ true))
1167       {
1168         if (mii.maxLatency((*P)->getOpCode()) > 1)
1169           mdelayNodeVec.push_back(*P);
1170         else
1171           sdelayNodeVec.push_back(*P);
1172       }
1173
1174   // If not enough single-cycle instructions were found, select the
1175   // lowest-latency multi-cycle instructions and use them.
1176   // Note that this is the most efficient code when only 1 (or even 2)
1177   // values need to be selected.
1178   //
1179   while (sdelayNodeVec.size() < ndelays && mdelayNodeVec.size() > 0)
1180     {
1181       unsigned lmin =
1182         mii.maxLatency(mdelayNodeVec[0]->getOpCode());
1183       unsigned minIndex   = 0;
1184       for (unsigned i=1; i < mdelayNodeVec.size(); i++)
1185         {
1186           unsigned li =
1187             mii.maxLatency(mdelayNodeVec[i]->getOpCode());
1188           if (lmin >= li)
1189             {
1190               lmin = li;
1191               minIndex = i;
1192             }
1193         }
1194       sdelayNodeVec.push_back(mdelayNodeVec[minIndex]);
1195       if (sdelayNodeVec.size() < ndelays) // avoid the last erase!
1196         mdelayNodeVec.erase(mdelayNodeVec.begin() + minIndex);
1197     }
1198 }
1199
1200
1201 // Remove the NOPs currently in delay slots from the graph.
1202 // Mark instructions specified in sdelayNodeVec to replace them.
1203 // If not enough useful instructions were found, mark the NOPs to be used
1204 // for filling delay slots, otherwise, otherwise just discard them.
1205 //
1206 void
1207 ReplaceNopsWithUsefulInstr(SchedulingManager& S,
1208                            SchedGraphNode* node,
1209                            vector<SchedGraphNode*> sdelayNodeVec,
1210                            SchedGraph* graph)
1211 {
1212   vector<SchedGraphNode*> nopNodeVec;   // this will hold unused NOPs
1213   const MachineInstrInfo& mii = S.getInstrInfo();
1214   const MachineInstr* brInstr = node->getMachineInstr();
1215   unsigned ndelays= mii.getNumDelaySlots(brInstr->getOpCode());
1216   assert(ndelays > 0 && "Unnecessary call to replace NOPs");
1217
1218   // Remove the NOPs currently in delay slots from the graph.
1219   // If not enough useful instructions were found, use the NOPs to
1220   // fill delay slots, otherwise, just discard them.
1221   //
1222   unsigned int firstDelaySlotIdx = node->getOrigIndexInBB() + 1;
1223   MachineCodeForBasicBlock& bbMvec = MachineCodeForBasicBlock::get(node->getBB());
1224   assert(bbMvec[firstDelaySlotIdx - 1] == brInstr &&
1225          "Incorrect instr. index in basic block for brInstr");
1226
1227   // First find all useful instructions already in the delay slots
1228   // and USE THEM.  We'll throw away the unused alternatives below
1229   //
1230   for (unsigned i=firstDelaySlotIdx; i < firstDelaySlotIdx + ndelays; ++i)
1231     if (! mii.isNop(bbMvec[i]->getOpCode()))
1232       sdelayNodeVec.insert(sdelayNodeVec.begin(),
1233                            graph->getGraphNodeForInstr(bbMvec[i]));
1234
1235   // Then find the NOPs and keep only as many as are needed.
1236   // Put the rest in nopNodeVec to be deleted.
1237   for (unsigned i=firstDelaySlotIdx; i < firstDelaySlotIdx + ndelays; ++i)
1238     if (mii.isNop(bbMvec[i]->getOpCode()))
1239       if (sdelayNodeVec.size() < ndelays)
1240         sdelayNodeVec.push_back(graph->getGraphNodeForInstr(bbMvec[i]));
1241       else
1242         {
1243           nopNodeVec.push_back(graph->getGraphNodeForInstr(bbMvec[i]));
1244
1245           //remove the MI from the Machine Code For Instruction
1246           MachineCodeForInstruction& llvmMvec =
1247             MachineCodeForInstruction::get((Instruction *)
1248                                            (node->getBB()->getTerminator()));
1249           for(MachineCodeForInstruction::iterator mciI=llvmMvec.begin(),
1250                 mciE=llvmMvec.end(); mciI!=mciE; ++mciI){
1251             if(*mciI==bbMvec[i])
1252               llvmMvec.erase(mciI);
1253           }
1254         }
1255
1256   assert(sdelayNodeVec.size() >= ndelays);
1257
1258   // If some delay slots were already filled, throw away that many new choices
1259   if (sdelayNodeVec.size() > ndelays)
1260     sdelayNodeVec.resize(ndelays);
1261
1262   // Mark the nodes chosen for delay slots.  This removes them from the graph.
1263   for (unsigned i=0; i < sdelayNodeVec.size(); i++)
1264     MarkNodeForDelaySlot(S, graph, sdelayNodeVec[i], node, true);
1265
1266   // And remove the unused NOPs from the graph.
1267   for (unsigned i=0; i < nopNodeVec.size(); i++)
1268     graph->eraseIncidentEdges(nopNodeVec[i], /*addDummyEdges*/ true);
1269 }
1270
1271
1272 // For all delayed instructions, choose instructions to put in the delay
1273 // slots and pull those out of the graph.  Mark them for the delay slots
1274 // in the DelaySlotInfo object for that graph node.  If no useful work
1275 // is found for a delay slot, use the NOP that is currently in that slot.
1276 //
1277 // We try to fill the delay slots with useful work for all instructions
1278 // EXCEPT CALLS AND RETURNS.
1279 // For CALLs and RETURNs, it is nearly always possible to use one of the
1280 // call sequence instrs and putting anything else in the delay slot could be
1281 // suboptimal.  Also, it complicates generating the calling sequence code in
1282 // regalloc.
1283 //
1284 static void
1285 ChooseInstructionsForDelaySlots(SchedulingManager& S,
1286                                 const BasicBlock *bb,
1287                                 SchedGraph *graph)
1288 {
1289   const MachineInstrInfo& mii = S.getInstrInfo();
1290   const Instruction *termInstr = (Instruction*)bb->getTerminator();
1291   MachineCodeForInstruction &termMvec=MachineCodeForInstruction::get(termInstr);
1292   vector<SchedGraphNode*> delayNodeVec;
1293   const MachineInstr* brInstr = NULL;
1294
1295   if (termInstr->getOpcode() != Instruction::Ret)
1296     {
1297       // To find instructions that need delay slots without searching the full
1298       // machine code, we assume that the only delayed instructions are CALLs
1299       // or instructions generated for the terminator inst.
1300       // Find the first branch instr in the sequence of machine instrs for term
1301       //
1302       unsigned first = 0;
1303       while (first < termMvec.size() &&
1304              ! mii.isBranch(termMvec[first]->getOpCode()))
1305         {
1306           ++first;
1307         }
1308       assert(first < termMvec.size() &&
1309          "No branch instructions for BR?  Ok, but weird!  Delete assertion.");
1310
1311       brInstr = (first < termMvec.size())? termMvec[first] : NULL;
1312
1313       // Compute a vector of the nodes chosen for delay slots and then
1314       // mark delay slots to replace NOPs with these useful instructions.
1315       //
1316       if (brInstr != NULL)
1317         {
1318           SchedGraphNode* brNode = graph->getGraphNodeForInstr(brInstr);
1319           FindUsefulInstructionsForDelaySlots(S, brNode, delayNodeVec);
1320           ReplaceNopsWithUsefulInstr(S, brNode, delayNodeVec, graph);
1321         }
1322     }
1323
1324   // Also mark delay slots for other delayed instructions to hold NOPs.
1325   // Simply passing in an empty delayNodeVec will have this effect.
1326   //
1327   delayNodeVec.clear();
1328   const MachineCodeForBasicBlock& bbMvec = MachineCodeForBasicBlock::get(bb);
1329   for (unsigned i=0; i < bbMvec.size(); i++)
1330     if (bbMvec[i] != brInstr &&
1331         mii.getNumDelaySlots(bbMvec[i]->getOpCode()) > 0)
1332       {
1333         SchedGraphNode* node = graph->getGraphNodeForInstr(bbMvec[i]);
1334         ReplaceNopsWithUsefulInstr(S, node, delayNodeVec, graph);
1335       }
1336 }
1337
1338
1339 //
1340 // Schedule the delayed branch and its delay slots
1341 //
1342 unsigned
1343 DelaySlotInfo::scheduleDelayedNode(SchedulingManager& S)
1344 {
1345   assert(delayedNodeSlotNum < S.nslots && "Illegal slot for branch");
1346   assert(S.isched.getInstr(delayedNodeSlotNum, delayedNodeCycle) == NULL
1347          && "Slot for branch should be empty");
1348
1349   unsigned int nextSlot = delayedNodeSlotNum;
1350   cycles_t nextTime = delayedNodeCycle;
1351
1352   S.scheduleInstr(brNode, nextSlot, nextTime);
1353
1354   for (unsigned d=0; d < ndelays; d++)
1355     {
1356       ++nextSlot;
1357       if (nextSlot == S.nslots)
1358         {
1359           nextSlot = 0;
1360           nextTime++;
1361         }
1362
1363       // Find the first feasible instruction for this delay slot
1364       // Note that we only check for issue restrictions here.
1365       // We do *not* check for flow dependences but rely on pipeline
1366       // interlocks to resolve them.  Machines without interlocks
1367       // will require this code to be modified.
1368       for (unsigned i=0; i < delayNodeVec.size(); i++)
1369         {
1370           const SchedGraphNode* dnode = delayNodeVec[i];
1371           if ( ! S.isScheduled(dnode)
1372                && S.schedInfo.instrCanUseSlot(dnode->getOpCode(), nextSlot)
1373                && instrIsFeasible(S, dnode->getOpCode()))
1374             {
1375               assert(S.getInstrInfo().hasOperandInterlock(dnode->getOpCode())
1376                      && "Instructions without interlocks not yet supported "
1377                      "when filling branch delay slots");
1378               S.scheduleInstr(dnode, nextSlot, nextTime);
1379               break;
1380             }
1381         }
1382     }
1383
1384   // Update current time if delay slots overflowed into later cycles.
1385   // Do this here because we know exactly which cycle is the last cycle
1386   // that contains delay slots.  The next loop doesn't compute that.
1387   if (nextTime > S.getTime())
1388     S.updateTime(nextTime);
1389
1390   // Now put any remaining instructions in the unfilled delay slots.
1391   // This could lead to suboptimal performance but needed for correctness.
1392   nextSlot = delayedNodeSlotNum;
1393   nextTime = delayedNodeCycle;
1394   for (unsigned i=0; i < delayNodeVec.size(); i++)
1395     if (! S.isScheduled(delayNodeVec[i]))
1396       {
1397         do { // find the next empty slot
1398           ++nextSlot;
1399           if (nextSlot == S.nslots)
1400             {
1401               nextSlot = 0;
1402               nextTime++;
1403             }
1404         } while (S.isched.getInstr(nextSlot, nextTime) != NULL);
1405
1406         S.scheduleInstr(delayNodeVec[i], nextSlot, nextTime);
1407         break;
1408       }
1409
1410   return 1 + ndelays;
1411 }
1412
1413
1414 // Check if the instruction would conflict with instructions already
1415 // chosen for the current cycle
1416 //
1417 static inline bool
1418 ConflictsWithChoices(const SchedulingManager& S,
1419                      MachineOpCode opCode)
1420 {
1421   // Check if the instruction must issue by itself, and some feasible
1422   // choices have already been made for this cycle
1423   if (S.getNumChoices() > 0 && S.schedInfo.isSingleIssue(opCode))
1424     return true;
1425
1426   // For each class that opCode belongs to, check if there are too many
1427   // instructions of that class.
1428   //
1429   const InstrSchedClass sc = S.schedInfo.getSchedClass(opCode);
1430   return (S.getNumChoicesInClass(sc) == S.schedInfo.getMaxIssueForClass(sc));
1431 }
1432
1433
1434 //************************* External Functions *****************************/
1435
1436
1437 //---------------------------------------------------------------------------
1438 // Function: ViolatesMinimumGap
1439 //
1440 // Purpose:
1441 //   Check minimum gap requirements relative to instructions scheduled in
1442 //   previous cycles.
1443 //   Note that we do not need to consider `nextEarliestIssueTime' here because
1444 //   that is also captured in the earliest start times for each opcode.
1445 //---------------------------------------------------------------------------
1446
1447 static inline bool
1448 ViolatesMinimumGap(const SchedulingManager& S,
1449                    MachineOpCode opCode,
1450                    const cycles_t inCycle)
1451 {
1452   return (inCycle < S.getEarliestStartTimeForOp(opCode));
1453 }
1454
1455
1456 //---------------------------------------------------------------------------
1457 // Function: instrIsFeasible
1458 //
1459 // Purpose:
1460 //   Check if any issue restrictions would prevent the instruction from
1461 //   being issued in the current cycle
1462 //---------------------------------------------------------------------------
1463
1464 bool
1465 instrIsFeasible(const SchedulingManager& S,
1466                 MachineOpCode opCode)
1467 {
1468   // skip the instruction if it cannot be issued due to issue restrictions
1469   // caused by previously issued instructions
1470   if (ViolatesMinimumGap(S, opCode, S.getTime()))
1471     return false;
1472
1473   // skip the instruction if it cannot be issued due to issue restrictions
1474   // caused by previously chosen instructions for the current cycle
1475   if (ConflictsWithChoices(S, opCode))
1476     return false;
1477
1478   return true;
1479 }
1480
1481 //---------------------------------------------------------------------------
1482 // Function: ScheduleInstructionsWithSSA
1483 //
1484 // Purpose:
1485 //   Entry point for instruction scheduling on SSA form.
1486 //   Schedules the machine instructions generated by instruction selection.
1487 //   Assumes that register allocation has not been done, i.e., operands
1488 //   are still in SSA form.
1489 //---------------------------------------------------------------------------
1490
1491 namespace {
1492   class InstructionSchedulingWithSSA : public FunctionPass {
1493     const TargetMachine &target;
1494   public:
1495     inline InstructionSchedulingWithSSA(const TargetMachine &T) : target(T) {}
1496
1497     const char *getPassName() const { return "Instruction Scheduling"; }
1498
1499     // getAnalysisUsage - We use LiveVarInfo...
1500     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
1501       AU.addRequired<FunctionLiveVarInfo>();
1502     }
1503
1504     bool runOnFunction(Function &F);
1505   };
1506 } // end anonymous namespace
1507
1508
1509 bool InstructionSchedulingWithSSA::runOnFunction(Function &F)
1510 {
1511   SchedGraphSet graphSet(&F, target);
1512
1513   if (SchedDebugLevel >= Sched_PrintSchedGraphs)
1514     {
1515       cerr << "\n*** SCHEDULING GRAPHS FOR INSTRUCTION SCHEDULING\n";
1516       graphSet.dump();
1517     }
1518
1519   for (SchedGraphSet::const_iterator GI=graphSet.begin(), GE=graphSet.end();
1520        GI != GE; ++GI)
1521     {
1522       SchedGraph* graph = (*GI);
1523       const vector<const BasicBlock*> &bbvec = graph->getBasicBlocks();
1524       assert(bbvec.size() == 1 && "Cannot schedule multiple basic blocks");
1525       const BasicBlock* bb = bbvec[0];
1526
1527       if (SchedDebugLevel >= Sched_PrintSchedTrace)
1528         cerr << "\n*** TRACE OF INSTRUCTION SCHEDULING OPERATIONS\n\n";
1529
1530       // expensive!
1531       SchedPriorities schedPrio(&F, graph,getAnalysis<FunctionLiveVarInfo>());
1532       SchedulingManager S(target, graph, schedPrio);
1533
1534       ChooseInstructionsForDelaySlots(S, bb, graph); // modifies graph
1535
1536       ForwardListSchedule(S);               // computes schedule in S
1537
1538       RecordSchedule(bb, S);                // records schedule in BB
1539     }
1540
1541   if (SchedDebugLevel >= Sched_PrintMachineCode)
1542     {
1543       cerr << "\n*** Machine instructions after INSTRUCTION SCHEDULING\n";
1544       MachineCodeForMethod::get(&F).dump();
1545     }
1546
1547   return false;
1548 }
1549
1550
1551 Pass *createInstructionSchedulingWithSSAPass(const TargetMachine &tgt) {
1552   return new InstructionSchedulingWithSSA(tgt);
1553 }