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