lib/Target/SparcV9/InstrSched/InstrScheduling.cpp

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