lib/Target/SparcV9/InstrSched/InstrScheduling.cpp

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