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