lib/Target/SparcV9/InstrSched/InstrScheduling.cpp

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