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