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