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