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