lib/Target/SparcV9/InstrSched/InstrScheduling.cpp

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