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