lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp

   1 //===----- ScheduleDAGRRList.cpp - Reg pressure reduction list scheduler --===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This implements bottom-up and top-down register pressure reduction list
  11 // schedulers, using standard algorithms.  The basic approach uses a priority
  12 // queue of available nodes to schedule.  One at a time, nodes are taken from
  13 // the priority queue (thus in priority order), checked for legality to
  14 // schedule, and emitted if legal.
  15 //
  16 //===----------------------------------------------------------------------===//
  17
  18 #define DEBUG_TYPE "pre-RA-sched"
  19 #include "ScheduleDAGSDNodes.h"
  20 #include "llvm/InlineAsm.h"
  21 #include "llvm/CodeGen/SchedulerRegistry.h"
  22 #include "llvm/CodeGen/SelectionDAGISel.h"
  23 #include "llvm/Target/TargetRegisterInfo.h"
  24 #include "llvm/Target/TargetData.h"
  25 #include "llvm/Target/TargetMachine.h"
  26 #include "llvm/Target/TargetInstrInfo.h"
  27 #include "llvm/Target/TargetLowering.h"
  28 #include "llvm/ADT/SmallSet.h"
  29 #include "llvm/ADT/Statistic.h"
  30 #include "llvm/ADT/STLExtras.h"
  31 #include "llvm/Support/CommandLine.h"
  32 #include "llvm/Support/Debug.h"
  33 #include "llvm/Support/ErrorHandling.h"
  34 #include "llvm/Support/raw_ostream.h"
  35 #include <climits>
  36 using namespace llvm;
  37
  38 static cl::opt<bool> RegPressureAware("reg-pressure-aware-sched",
  39                                       cl::init(false), cl::Hidden);
  40
  41 STATISTIC(NumBacktracks, "Number of times scheduler backtracked");
  42 STATISTIC(NumUnfolds,    "Number of nodes unfolded");
  43 STATISTIC(NumDups,       "Number of duplicated nodes");
  44 STATISTIC(NumPRCopies,   "Number of physical register copies");
  45
  46 static RegisterScheduler
  47   burrListDAGScheduler("list-burr",
  48                        "Bottom-up register reduction list scheduling",
  49                        createBURRListDAGScheduler);
  50 static RegisterScheduler
  51   tdrListrDAGScheduler("list-tdrr",
  52                        "Top-down register reduction list scheduling",
  53                        createTDRRListDAGScheduler);
  54 static RegisterScheduler
  55   sourceListDAGScheduler("source",
  56                          "Similar to list-burr but schedules in source "
  57                          "order when possible",
  58                          createSourceListDAGScheduler);
  59
  60 static RegisterScheduler
  61   hybridListDAGScheduler("list-hybrid",
  62                          "Bottom-up rr list scheduling which avoid stalls for "
  63                          "long latency instructions",
  64                          createHybridListDAGScheduler);
  65
  66 namespace {
  67 //===----------------------------------------------------------------------===//
  68 /// ScheduleDAGRRList - The actual register reduction list scheduler
  69 /// implementation.  This supports both top-down and bottom-up scheduling.
  70 ///
  71 class ScheduleDAGRRList : public ScheduleDAGSDNodes {
  72 private:
  73   /// isBottomUp - This is true if the scheduling problem is bottom-up, false if
  74   /// it is top-down.
  75   bool isBottomUp;
  76
  77   /// NeedLatency - True if the scheduler will make use of latency information.
  78   ///
  79   bool NeedLatency;
  80
  81   /// AvailableQueue - The priority queue to use for the available SUnits.
  82   SchedulingPriorityQueue *AvailableQueue;
  83
  84   /// LiveRegDefs - A set of physical registers and their definition
  85   /// that are "live". These nodes must be scheduled before any other nodes that
  86   /// modifies the registers can be scheduled.
  87   unsigned NumLiveRegs;
  88   std::vector<SUnit*> LiveRegDefs;
  89   std::vector<unsigned> LiveRegCycles;
  90
  91   /// Topo - A topological ordering for SUnits which permits fast IsReachable
  92   /// and similar queries.
  93   ScheduleDAGTopologicalSort Topo;
  94
  95 public:
  96   ScheduleDAGRRList(MachineFunction &mf,
  97                     bool isbottomup, bool needlatency,
  98                     SchedulingPriorityQueue *availqueue)
  99     : ScheduleDAGSDNodes(mf), isBottomUp(isbottomup), NeedLatency(needlatency),
 100       AvailableQueue(availqueue), Topo(SUnits) {
 101     }
 102
 103   ~ScheduleDAGRRList() {
 104     delete AvailableQueue;
 105   }
 106
 107   void Schedule();
 108
 109   /// IsReachable - Checks if SU is reachable from TargetSU.
 110   bool IsReachable(const SUnit *SU, const SUnit *TargetSU) {
 111     return Topo.IsReachable(SU, TargetSU);
 112   }
 113
 114   /// WillCreateCycle - Returns true if adding an edge from SU to TargetSU will
 115   /// create a cycle.
 116   bool WillCreateCycle(SUnit *SU, SUnit *TargetSU) {
 117     return Topo.WillCreateCycle(SU, TargetSU);
 118   }
 119
 120   /// AddPred - adds a predecessor edge to SUnit SU.
 121   /// This returns true if this is a new predecessor.
 122   /// Updates the topological ordering if required.
 123   void AddPred(SUnit *SU, const SDep &D) {
 124     Topo.AddPred(SU, D.getSUnit());
 125     SU->addPred(D);
 126   }
 127
 128   /// RemovePred - removes a predecessor edge from SUnit SU.
 129   /// This returns true if an edge was removed.
 130   /// Updates the topological ordering if required.
 131   void RemovePred(SUnit *SU, const SDep &D) {
 132     Topo.RemovePred(SU, D.getSUnit());
 133     SU->removePred(D);
 134   }
 135
 136 private:
 137   void ReleasePred(SUnit *SU, const SDep *PredEdge);
 138   void ReleasePredecessors(SUnit *SU, unsigned CurCycle);
 139   void ReleaseSucc(SUnit *SU, const SDep *SuccEdge);
 140   void ReleaseSuccessors(SUnit *SU);
 141   void CapturePred(SDep *PredEdge);
 142   void ScheduleNodeBottomUp(SUnit*, unsigned);
 143   void ScheduleNodeTopDown(SUnit*, unsigned);
 144   void UnscheduleNodeBottomUp(SUnit*);
 145   void BacktrackBottomUp(SUnit*, unsigned, unsigned&);
 146   SUnit *CopyAndMoveSuccessors(SUnit*);
 147   void InsertCopiesAndMoveSuccs(SUnit*, unsigned,
 148                                 const TargetRegisterClass*,
 149                                 const TargetRegisterClass*,
 150                                 SmallVector<SUnit*, 2>&);
 151   bool DelayForLiveRegsBottomUp(SUnit*, SmallVector<unsigned, 4>&);
 152   void ListScheduleTopDown();
 153   void ListScheduleBottomUp();
 154
 155
 156   /// CreateNewSUnit - Creates a new SUnit and returns a pointer to it.
 157   /// Updates the topological ordering if required.
 158   SUnit *CreateNewSUnit(SDNode *N) {
 159     unsigned NumSUnits = SUnits.size();
 160     SUnit *NewNode = NewSUnit(N);
 161     // Update the topological ordering.
 162     if (NewNode->NodeNum >= NumSUnits)
 163       Topo.InitDAGTopologicalSorting();
 164     return NewNode;
 165   }
 166
 167   /// CreateClone - Creates a new SUnit from an existing one.
 168   /// Updates the topological ordering if required.
 169   SUnit *CreateClone(SUnit *N) {
 170     unsigned NumSUnits = SUnits.size();
 171     SUnit *NewNode = Clone(N);
 172     // Update the topological ordering.
 173     if (NewNode->NodeNum >= NumSUnits)
 174       Topo.InitDAGTopologicalSorting();
 175     return NewNode;
 176   }
 177
 178   /// ForceUnitLatencies - Register-pressure-reducing scheduling doesn't
 179   /// need actual latency information but the hybrid scheduler does.
 180   bool ForceUnitLatencies() const {
 181     return !NeedLatency;
 182   }
 183 };
 184 }  // end anonymous namespace
 185
 186
 187 /// Schedule - Schedule the DAG using list scheduling.
 188 void ScheduleDAGRRList::Schedule() {
 189   DEBUG(dbgs()
 190         << "********** List Scheduling BB#" << BB->getNumber()
 191         << " **********\n");
 192
 193   NumLiveRegs = 0;
 194   LiveRegDefs.resize(TRI->getNumRegs(), NULL);
 195   LiveRegCycles.resize(TRI->getNumRegs(), 0);
 196
 197   // Build the scheduling graph.
 198   BuildSchedGraph(NULL);
 199
 200   DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
 201           SUnits[su].dumpAll(this));
 202   Topo.InitDAGTopologicalSorting();
 203
 204   AvailableQueue->initNodes(SUnits);
 205
 206   // Execute the actual scheduling loop Top-Down or Bottom-Up as appropriate.
 207   if (isBottomUp)
 208     ListScheduleBottomUp();
 209   else
 210     ListScheduleTopDown();
 211
 212   AvailableQueue->releaseState();
 213 }
 214
 215 //===----------------------------------------------------------------------===//
 216 //  Bottom-Up Scheduling
 217 //===----------------------------------------------------------------------===//
 218
 219 /// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to
 220 /// the AvailableQueue if the count reaches zero. Also update its cycle bound.
 221 void ScheduleDAGRRList::ReleasePred(SUnit *SU, const SDep *PredEdge) {
 222   SUnit *PredSU = PredEdge->getSUnit();
 223
 224 #ifndef NDEBUG
 225   if (PredSU->NumSuccsLeft == 0) {
 226     dbgs() << "*** Scheduling failed! ***\n";
 227     PredSU->dump(this);
 228     dbgs() << " has been released too many times!\n";
 229     llvm_unreachable(0);
 230   }
 231 #endif
 232   --PredSU->NumSuccsLeft;
 233
 234   if (!ForceUnitLatencies()) {
 235     // Updating predecessor's height. This is now the cycle when the
 236     // predecessor can be scheduled without causing a pipeline stall.
 237     PredSU->setHeightToAtLeast(SU->getHeight() + PredEdge->getLatency());
 238   }
 239
 240   // If all the node's successors are scheduled, this node is ready
 241   // to be scheduled. Ignore the special EntrySU node.
 242   if (PredSU->NumSuccsLeft == 0 && PredSU != &EntrySU) {
 243     PredSU->isAvailable = true;
 244     AvailableQueue->push(PredSU);
 245   }
 246 }
 247
 248 void ScheduleDAGRRList::ReleasePredecessors(SUnit *SU, unsigned CurCycle) {
 249   // Bottom up: release predecessors
 250   for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
 251        I != E; ++I) {
 252     ReleasePred(SU, &*I);
 253     if (I->isAssignedRegDep()) {
 254       // This is a physical register dependency and it's impossible or
 255       // expensive to copy the register. Make sure nothing that can
 256       // clobber the register is scheduled between the predecessor and
 257       // this node.
 258       if (!LiveRegDefs[I->getReg()]) {
 259         ++NumLiveRegs;
 260         LiveRegDefs[I->getReg()] = I->getSUnit();
 261         LiveRegCycles[I->getReg()] = CurCycle;
 262       }
 263     }
 264   }
 265 }
 266
 267 /// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending
 268 /// count of its predecessors. If a predecessor pending count is zero, add it to
 269 /// the Available queue.
 270 void ScheduleDAGRRList::ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle) {
 271   DEBUG(dbgs() << "\n*** Scheduling [" << CurCycle << "]: ");
 272   DEBUG(SU->dump(this));
 273
 274 #ifndef NDEBUG
 275   if (CurCycle < SU->getHeight())
 276     DEBUG(dbgs() << "   Height [" << SU->getHeight() << "] pipeline stall!\n");
 277 #endif
 278
 279   // FIXME: Handle noop hazard.
 280   SU->setHeightToAtLeast(CurCycle);
 281   Sequence.push_back(SU);
 282
 283   AvailableQueue->ScheduledNode(SU);
 284
 285   ReleasePredecessors(SU, CurCycle);
 286
 287   // Release all the implicit physical register defs that are live.
 288   for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
 289        I != E; ++I) {
 290     if (I->isAssignedRegDep()) {
 291       if (LiveRegCycles[I->getReg()] == I->getSUnit()->getHeight()) {
 292         assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");
 293         assert(LiveRegDefs[I->getReg()] == SU &&
 294                "Physical register dependency violated?");
 295         --NumLiveRegs;
 296         LiveRegDefs[I->getReg()] = NULL;
 297         LiveRegCycles[I->getReg()] = 0;
 298       }
 299     }
 300   }
 301
 302   SU->isScheduled = true;
 303 }
 304
 305 /// CapturePred - This does the opposite of ReleasePred. Since SU is being
 306 /// unscheduled, incrcease the succ left count of its predecessors. Remove
 307 /// them from AvailableQueue if necessary.
 308 void ScheduleDAGRRList::CapturePred(SDep *PredEdge) {
 309   SUnit *PredSU = PredEdge->getSUnit();
 310   if (PredSU->isAvailable) {
 311     PredSU->isAvailable = false;
 312     if (!PredSU->isPending)
 313       AvailableQueue->remove(PredSU);
 314   }
 315
 316   assert(PredSU->NumSuccsLeft < UINT_MAX && "NumSuccsLeft will overflow!");
 317   ++PredSU->NumSuccsLeft;
 318 }
 319
 320 /// UnscheduleNodeBottomUp - Remove the node from the schedule, update its and
 321 /// its predecessor states to reflect the change.
 322 void ScheduleDAGRRList::UnscheduleNodeBottomUp(SUnit *SU) {
 323   DEBUG(dbgs() << "*** Unscheduling [" << SU->getHeight() << "]: ");
 324   DEBUG(SU->dump(this));
 325
 326   for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
 327        I != E; ++I) {
 328     CapturePred(&*I);
 329     if (I->isAssignedRegDep() && SU->getHeight() == LiveRegCycles[I->getReg()]){
 330       assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");
 331       assert(LiveRegDefs[I->getReg()] == I->getSUnit() &&
 332              "Physical register dependency violated?");
 333       --NumLiveRegs;
 334       LiveRegDefs[I->getReg()] = NULL;
 335       LiveRegCycles[I->getReg()] = 0;
 336     }
 337   }
 338
 339   for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
 340        I != E; ++I) {
 341     if (I->isAssignedRegDep()) {
 342       if (!LiveRegDefs[I->getReg()]) {
 343         LiveRegDefs[I->getReg()] = SU;
 344         ++NumLiveRegs;
 345       }
 346       if (I->getSUnit()->getHeight() < LiveRegCycles[I->getReg()])
 347         LiveRegCycles[I->getReg()] = I->getSUnit()->getHeight();
 348     }
 349   }
 350
 351   SU->setHeightDirty();
 352   SU->isScheduled = false;
 353   SU->isAvailable = true;
 354   AvailableQueue->push(SU);
 355   AvailableQueue->UnscheduledNode(SU);
 356 }
 357
 358 /// BacktrackBottomUp - Backtrack scheduling to a previous cycle specified in
 359 /// BTCycle in order to schedule a specific node.
 360 void ScheduleDAGRRList::BacktrackBottomUp(SUnit *SU, unsigned BtCycle,
 361                                           unsigned &CurCycle) {
 362   SUnit *OldSU = NULL;
 363   while (CurCycle > BtCycle) {
 364     OldSU = Sequence.back();
 365     Sequence.pop_back();
 366     if (SU->isSucc(OldSU))
 367       // Don't try to remove SU from AvailableQueue.
 368       SU->isAvailable = false;
 369     UnscheduleNodeBottomUp(OldSU);
 370     --CurCycle;
 371     AvailableQueue->setCurCycle(CurCycle);
 372   }
 373
 374   assert(!SU->isSucc(OldSU) && "Something is wrong!");
 375
 376   ++NumBacktracks;
 377 }
 378
 379 static bool isOperandOf(const SUnit *SU, SDNode *N) {
 380   for (const SDNode *SUNode = SU->getNode(); SUNode;
 381        SUNode = SUNode->getFlaggedNode()) {
 382     if (SUNode->isOperandOf(N))
 383       return true;
 384   }
 385   return false;
 386 }
 387
 388 /// CopyAndMoveSuccessors - Clone the specified node and move its scheduled
 389 /// successors to the newly created node.
 390 SUnit *ScheduleDAGRRList::CopyAndMoveSuccessors(SUnit *SU) {
 391   if (SU->getNode()->getFlaggedNode())
 392     return NULL;
 393
 394   SDNode *N = SU->getNode();
 395   if (!N)
 396     return NULL;
 397
 398   SUnit *NewSU;
 399   bool TryUnfold = false;
 400   for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) {
 401     EVT VT = N->getValueType(i);
 402     if (VT == MVT::Flag)
 403       return NULL;
 404     else if (VT == MVT::Other)
 405       TryUnfold = true;
 406   }
 407   for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
 408     const SDValue &Op = N->getOperand(i);
 409     EVT VT = Op.getNode()->getValueType(Op.getResNo());
 410     if (VT == MVT::Flag)
 411       return NULL;
 412   }
 413
 414   if (TryUnfold) {
 415     SmallVector<SDNode*, 2> NewNodes;
 416     if (!TII->unfoldMemoryOperand(*DAG, N, NewNodes))
 417       return NULL;
 418
 419     DEBUG(dbgs() << "Unfolding SU #" << SU->NodeNum << "\n");
 420     assert(NewNodes.size() == 2 && "Expected a load folding node!");
 421
 422     N = NewNodes[1];
 423     SDNode *LoadNode = NewNodes[0];
 424     unsigned NumVals = N->getNumValues();
 425     unsigned OldNumVals = SU->getNode()->getNumValues();
 426     for (unsigned i = 0; i != NumVals; ++i)
 427       DAG->ReplaceAllUsesOfValueWith(SDValue(SU->getNode(), i), SDValue(N, i));
 428     DAG->ReplaceAllUsesOfValueWith(SDValue(SU->getNode(), OldNumVals-1),
 429                                    SDValue(LoadNode, 1));
 430
 431     // LoadNode may already exist. This can happen when there is another
 432     // load from the same location and producing the same type of value
 433     // but it has different alignment or volatileness.
 434     bool isNewLoad = true;
 435     SUnit *LoadSU;
 436     if (LoadNode->getNodeId() != -1) {
 437       LoadSU = &SUnits[LoadNode->getNodeId()];
 438       isNewLoad = false;
 439     } else {
 440       LoadSU = CreateNewSUnit(LoadNode);
 441       LoadNode->setNodeId(LoadSU->NodeNum);
 442       ComputeLatency(LoadSU);
 443     }
 444
 445     SUnit *NewSU = CreateNewSUnit(N);
 446     assert(N->getNodeId() == -1 && "Node already inserted!");
 447     N->setNodeId(NewSU->NodeNum);
 448
 449     const TargetInstrDesc &TID = TII->get(N->getMachineOpcode());
 450     for (unsigned i = 0; i != TID.getNumOperands(); ++i) {
 451       if (TID.getOperandConstraint(i, TOI::TIED_TO) != -1) {
 452         NewSU->isTwoAddress = true;
 453         break;
 454       }
 455     }
 456     if (TID.isCommutable())
 457       NewSU->isCommutable = true;
 458     ComputeLatency(NewSU);
 459
 460     // Record all the edges to and from the old SU, by category.
 461     SmallVector<SDep, 4> ChainPreds;
 462     SmallVector<SDep, 4> ChainSuccs;
 463     SmallVector<SDep, 4> LoadPreds;
 464     SmallVector<SDep, 4> NodePreds;
 465     SmallVector<SDep, 4> NodeSuccs;
 466     for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
 467          I != E; ++I) {
 468       if (I->isCtrl())
 469         ChainPreds.push_back(*I);
 470       else if (isOperandOf(I->getSUnit(), LoadNode))
 471         LoadPreds.push_back(*I);
 472       else
 473         NodePreds.push_back(*I);
 474     }
 475     for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
 476          I != E; ++I) {
 477       if (I->isCtrl())
 478         ChainSuccs.push_back(*I);
 479       else
 480         NodeSuccs.push_back(*I);
 481     }
 482
 483     // Now assign edges to the newly-created nodes.
 484     for (unsigned i = 0, e = ChainPreds.size(); i != e; ++i) {
 485       const SDep &Pred = ChainPreds[i];
 486       RemovePred(SU, Pred);
 487       if (isNewLoad)
 488         AddPred(LoadSU, Pred);
 489     }
 490     for (unsigned i = 0, e = LoadPreds.size(); i != e; ++i) {
 491       const SDep &Pred = LoadPreds[i];
 492       RemovePred(SU, Pred);
 493       if (isNewLoad)
 494         AddPred(LoadSU, Pred);
 495     }
 496     for (unsigned i = 0, e = NodePreds.size(); i != e; ++i) {
 497       const SDep &Pred = NodePreds[i];
 498       RemovePred(SU, Pred);
 499       AddPred(NewSU, Pred);
 500     }
 501     for (unsigned i = 0, e = NodeSuccs.size(); i != e; ++i) {
 502       SDep D = NodeSuccs[i];
 503       SUnit *SuccDep = D.getSUnit();
 504       D.setSUnit(SU);
 505       RemovePred(SuccDep, D);
 506       D.setSUnit(NewSU);
 507       AddPred(SuccDep, D);
 508     }
 509     for (unsigned i = 0, e = ChainSuccs.size(); i != e; ++i) {
 510       SDep D = ChainSuccs[i];
 511       SUnit *SuccDep = D.getSUnit();
 512       D.setSUnit(SU);
 513       RemovePred(SuccDep, D);
 514       if (isNewLoad) {
 515         D.setSUnit(LoadSU);
 516         AddPred(SuccDep, D);
 517       }
 518     }
 519
 520     // Add a data dependency to reflect that NewSU reads the value defined
 521     // by LoadSU.
 522     AddPred(NewSU, SDep(LoadSU, SDep::Data, LoadSU->Latency));
 523
 524     if (isNewLoad)
 525       AvailableQueue->addNode(LoadSU);
 526     AvailableQueue->addNode(NewSU);
 527
 528     ++NumUnfolds;
 529
 530     if (NewSU->NumSuccsLeft == 0) {
 531       NewSU->isAvailable = true;
 532       return NewSU;
 533     }
 534     SU = NewSU;
 535   }
 536
 537   DEBUG(dbgs() << "    Duplicating SU #" << SU->NodeNum << "\n");
 538   NewSU = CreateClone(SU);
 539
 540   // New SUnit has the exact same predecessors.
 541   for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
 542        I != E; ++I)
 543     if (!I->isArtificial())
 544       AddPred(NewSU, *I);
 545
 546   // Only copy scheduled successors. Cut them from old node's successor
 547   // list and move them over.
 548   SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps;
 549   for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
 550        I != E; ++I) {
 551     if (I->isArtificial())
 552       continue;
 553     SUnit *SuccSU = I->getSUnit();
 554     if (SuccSU->isScheduled) {
 555       SDep D = *I;
 556       D.setSUnit(NewSU);
 557       AddPred(SuccSU, D);
 558       D.setSUnit(SU);
 559       DelDeps.push_back(std::make_pair(SuccSU, D));
 560     }
 561   }
 562   for (unsigned i = 0, e = DelDeps.size(); i != e; ++i)
 563     RemovePred(DelDeps[i].first, DelDeps[i].second);
 564
 565   AvailableQueue->updateNode(SU);
 566   AvailableQueue->addNode(NewSU);
 567
 568   ++NumDups;
 569   return NewSU;
 570 }
 571
 572 /// InsertCopiesAndMoveSuccs - Insert register copies and move all
 573 /// scheduled successors of the given SUnit to the last copy.
 574 void ScheduleDAGRRList::InsertCopiesAndMoveSuccs(SUnit *SU, unsigned Reg,
 575                                                const TargetRegisterClass *DestRC,
 576                                                const TargetRegisterClass *SrcRC,
 577                                                SmallVector<SUnit*, 2> &Copies) {
 578   SUnit *CopyFromSU = CreateNewSUnit(NULL);
 579   CopyFromSU->CopySrcRC = SrcRC;
 580   CopyFromSU->CopyDstRC = DestRC;
 581
 582   SUnit *CopyToSU = CreateNewSUnit(NULL);
 583   CopyToSU->CopySrcRC = DestRC;
 584   CopyToSU->CopyDstRC = SrcRC;
 585
 586   // Only copy scheduled successors. Cut them from old node's successor
 587   // list and move them over.
 588   SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps;
 589   for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
 590        I != E; ++I) {
 591     if (I->isArtificial())
 592       continue;
 593     SUnit *SuccSU = I->getSUnit();
 594     if (SuccSU->isScheduled) {
 595       SDep D = *I;
 596       D.setSUnit(CopyToSU);
 597       AddPred(SuccSU, D);
 598       DelDeps.push_back(std::make_pair(SuccSU, *I));
 599     }
 600   }
 601   for (unsigned i = 0, e = DelDeps.size(); i != e; ++i)
 602     RemovePred(DelDeps[i].first, DelDeps[i].second);
 603
 604   AddPred(CopyFromSU, SDep(SU, SDep::Data, SU->Latency, Reg));
 605   AddPred(CopyToSU, SDep(CopyFromSU, SDep::Data, CopyFromSU->Latency, 0));
 606
 607   AvailableQueue->updateNode(SU);
 608   AvailableQueue->addNode(CopyFromSU);
 609   AvailableQueue->addNode(CopyToSU);
 610   Copies.push_back(CopyFromSU);
 611   Copies.push_back(CopyToSU);
 612
 613   ++NumPRCopies;
 614 }
 615
 616 /// getPhysicalRegisterVT - Returns the ValueType of the physical register
 617 /// definition of the specified node.
 618 /// FIXME: Move to SelectionDAG?
 619 static EVT getPhysicalRegisterVT(SDNode *N, unsigned Reg,
 620                                  const TargetInstrInfo *TII) {
 621   const TargetInstrDesc &TID = TII->get(N->getMachineOpcode());
 622   assert(TID.ImplicitDefs && "Physical reg def must be in implicit def list!");
 623   unsigned NumRes = TID.getNumDefs();
 624   for (const unsigned *ImpDef = TID.getImplicitDefs(); *ImpDef; ++ImpDef) {
 625     if (Reg == *ImpDef)
 626       break;
 627     ++NumRes;
 628   }
 629   return N->getValueType(NumRes);
 630 }
 631
 632 /// CheckForLiveRegDef - Return true and update live register vector if the
 633 /// specified register def of the specified SUnit clobbers any "live" registers.
 634 static bool CheckForLiveRegDef(SUnit *SU, unsigned Reg,
 635                                std::vector<SUnit*> &LiveRegDefs,
 636                                SmallSet<unsigned, 4> &RegAdded,
 637                                SmallVector<unsigned, 4> &LRegs,
 638                                const TargetRegisterInfo *TRI) {
 639   bool Added = false;
 640   if (LiveRegDefs[Reg] && LiveRegDefs[Reg] != SU) {
 641     if (RegAdded.insert(Reg)) {
 642       LRegs.push_back(Reg);
 643       Added = true;
 644     }
 645   }
 646   for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias)
 647     if (LiveRegDefs[*Alias] && LiveRegDefs[*Alias] != SU) {
 648       if (RegAdded.insert(*Alias)) {
 649         LRegs.push_back(*Alias);
 650         Added = true;
 651       }
 652     }
 653   return Added;
 654 }
 655
 656 /// DelayForLiveRegsBottomUp - Returns true if it is necessary to delay
 657 /// scheduling of the given node to satisfy live physical register dependencies.
 658 /// If the specific node is the last one that's available to schedule, do
 659 /// whatever is necessary (i.e. backtracking or cloning) to make it possible.
 660 bool ScheduleDAGRRList::DelayForLiveRegsBottomUp(SUnit *SU,
 661                                                  SmallVector<unsigned, 4> &LRegs){
 662   if (NumLiveRegs == 0)
 663     return false;
 664
 665   SmallSet<unsigned, 4> RegAdded;
 666   // If this node would clobber any "live" register, then it's not ready.
 667   for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
 668        I != E; ++I) {
 669     if (I->isAssignedRegDep())
 670       CheckForLiveRegDef(I->getSUnit(), I->getReg(), LiveRegDefs,
 671                          RegAdded, LRegs, TRI);
 672   }
 673
 674   for (SDNode *Node = SU->getNode(); Node; Node = Node->getFlaggedNode()) {
 675     if (Node->getOpcode() == ISD::INLINEASM) {
 676       // Inline asm can clobber physical defs.
 677       unsigned NumOps = Node->getNumOperands();
 678       if (Node->getOperand(NumOps-1).getValueType() == MVT::Flag)
 679         --NumOps;  // Ignore the flag operand.
 680
 681       for (unsigned i = InlineAsm::Op_FirstOperand; i != NumOps;) {
 682         unsigned Flags =
 683           cast<ConstantSDNode>(Node->getOperand(i))->getZExtValue();
 684         unsigned NumVals = InlineAsm::getNumOperandRegisters(Flags);
 685
 686         ++i; // Skip the ID value.
 687         if (InlineAsm::isRegDefKind(Flags) ||
 688             InlineAsm::isRegDefEarlyClobberKind(Flags)) {
 689           // Check for def of register or earlyclobber register.
 690           for (; NumVals; --NumVals, ++i) {
 691             unsigned Reg = cast<RegisterSDNode>(Node->getOperand(i))->getReg();
 692             if (TargetRegisterInfo::isPhysicalRegister(Reg))
 693               CheckForLiveRegDef(SU, Reg, LiveRegDefs, RegAdded, LRegs, TRI);
 694           }
 695         } else
 696           i += NumVals;
 697       }
 698       continue;
 699     }
 700
 701     if (!Node->isMachineOpcode())
 702       continue;
 703     const TargetInstrDesc &TID = TII->get(Node->getMachineOpcode());
 704     if (!TID.ImplicitDefs)
 705       continue;
 706     for (const unsigned *Reg = TID.ImplicitDefs; *Reg; ++Reg)
 707       CheckForLiveRegDef(SU, *Reg, LiveRegDefs, RegAdded, LRegs, TRI);
 708   }
 709   return !LRegs.empty();
 710 }
 711
 712
 713 /// ListScheduleBottomUp - The main loop of list scheduling for bottom-up
 714 /// schedulers.
 715 void ScheduleDAGRRList::ListScheduleBottomUp() {
 716   unsigned CurCycle = 0;
 717
 718   // Release any predecessors of the special Exit node.
 719   ReleasePredecessors(&ExitSU, CurCycle);
 720
 721   // Add root to Available queue.
 722   if (!SUnits.empty()) {
 723     SUnit *RootSU = &SUnits[DAG->getRoot().getNode()->getNodeId()];
 724     assert(RootSU->Succs.empty() && "Graph root shouldn't have successors!");
 725     RootSU->isAvailable = true;
 726     AvailableQueue->push(RootSU);
 727   }
 728
 729   // While Available queue is not empty, grab the node with the highest
 730   // priority. If it is not ready put it back.  Schedule the node.
 731   SmallVector<SUnit*, 4> NotReady;
 732   DenseMap<SUnit*, SmallVector<unsigned, 4> > LRegsMap;
 733   Sequence.reserve(SUnits.size());
 734   while (!AvailableQueue->empty()) {
 735     bool Delayed = false;
 736     LRegsMap.clear();
 737     SUnit *CurSU = AvailableQueue->pop();
 738     while (CurSU) {
 739       SmallVector<unsigned, 4> LRegs;
 740       if (!DelayForLiveRegsBottomUp(CurSU, LRegs))
 741         break;
 742       Delayed = true;
 743       LRegsMap.insert(std::make_pair(CurSU, LRegs));
 744
 745       CurSU->isPending = true;  // This SU is not in AvailableQueue right now.
 746       NotReady.push_back(CurSU);
 747       CurSU = AvailableQueue->pop();
 748     }
 749
 750     // All candidates are delayed due to live physical reg dependencies.
 751     // Try backtracking, code duplication, or inserting cross class copies
 752     // to resolve it.
 753     if (Delayed && !CurSU) {
 754       for (unsigned i = 0, e = NotReady.size(); i != e; ++i) {
 755         SUnit *TrySU = NotReady[i];
 756         SmallVector<unsigned, 4> &LRegs = LRegsMap[TrySU];
 757
 758         // Try unscheduling up to the point where it's safe to schedule
 759         // this node.
 760         unsigned LiveCycle = CurCycle;
 761         for (unsigned j = 0, ee = LRegs.size(); j != ee; ++j) {
 762           unsigned Reg = LRegs[j];
 763           unsigned LCycle = LiveRegCycles[Reg];
 764           LiveCycle = std::min(LiveCycle, LCycle);
 765         }
 766         SUnit *OldSU = Sequence[LiveCycle];
 767         if (!WillCreateCycle(TrySU, OldSU))  {
 768           BacktrackBottomUp(TrySU, LiveCycle, CurCycle);
 769           // Force the current node to be scheduled before the node that
 770           // requires the physical reg dep.
 771           if (OldSU->isAvailable) {
 772             OldSU->isAvailable = false;
 773             AvailableQueue->remove(OldSU);
 774           }
 775           AddPred(TrySU, SDep(OldSU, SDep::Order, /*Latency=*/1,
 776                               /*Reg=*/0, /*isNormalMemory=*/false,
 777                               /*isMustAlias=*/false, /*isArtificial=*/true));
 778           // If one or more successors has been unscheduled, then the current
 779           // node is no longer avaialable. Schedule a successor that's now
 780           // available instead.
 781           if (!TrySU->isAvailable)
 782             CurSU = AvailableQueue->pop();
 783           else {
 784             CurSU = TrySU;
 785             TrySU->isPending = false;
 786             NotReady.erase(NotReady.begin()+i);
 787           }
 788           break;
 789         }
 790       }
 791
 792       if (!CurSU) {
 793         // Can't backtrack. If it's too expensive to copy the value, then try
 794         // duplicate the nodes that produces these "too expensive to copy"
 795         // values to break the dependency. In case even that doesn't work,
 796         // insert cross class copies.
 797         // If it's not too expensive, i.e. cost != -1, issue copies.
 798         SUnit *TrySU = NotReady[0];
 799         SmallVector<unsigned, 4> &LRegs = LRegsMap[TrySU];
 800         assert(LRegs.size() == 1 && "Can't handle this yet!");
 801         unsigned Reg = LRegs[0];
 802         SUnit *LRDef = LiveRegDefs[Reg];
 803         EVT VT = getPhysicalRegisterVT(LRDef->getNode(), Reg, TII);
 804         const TargetRegisterClass *RC =
 805           TRI->getMinimalPhysRegClass(Reg, VT);
 806         const TargetRegisterClass *DestRC = TRI->getCrossCopyRegClass(RC);
 807
 808         // If cross copy register class is null, then it must be possible copy
 809         // the value directly. Do not try duplicate the def.
 810         SUnit *NewDef = 0;
 811         if (DestRC)
 812           NewDef = CopyAndMoveSuccessors(LRDef);
 813         else
 814           DestRC = RC;
 815         if (!NewDef) {
 816           // Issue copies, these can be expensive cross register class copies.
 817           SmallVector<SUnit*, 2> Copies;
 818           InsertCopiesAndMoveSuccs(LRDef, Reg, DestRC, RC, Copies);
 819           DEBUG(dbgs() << "    Adding an edge from SU #" << TrySU->NodeNum
 820                        << " to SU #" << Copies.front()->NodeNum << "\n");
 821           AddPred(TrySU, SDep(Copies.front(), SDep::Order, /*Latency=*/1,
 822                               /*Reg=*/0, /*isNormalMemory=*/false,
 823                               /*isMustAlias=*/false,
 824                               /*isArtificial=*/true));
 825           NewDef = Copies.back();
 826         }
 827
 828         DEBUG(dbgs() << "    Adding an edge from SU #" << NewDef->NodeNum
 829                      << " to SU #" << TrySU->NodeNum << "\n");
 830         LiveRegDefs[Reg] = NewDef;
 831         AddPred(NewDef, SDep(TrySU, SDep::Order, /*Latency=*/1,
 832                              /*Reg=*/0, /*isNormalMemory=*/false,
 833                              /*isMustAlias=*/false,
 834                              /*isArtificial=*/true));
 835         TrySU->isAvailable = false;
 836         CurSU = NewDef;
 837       }
 838
 839       assert(CurSU && "Unable to resolve live physical register dependencies!");
 840     }
 841
 842     // Add the nodes that aren't ready back onto the available list.
 843     for (unsigned i = 0, e = NotReady.size(); i != e; ++i) {
 844       NotReady[i]->isPending = false;
 845       // May no longer be available due to backtracking.
 846       if (NotReady[i]->isAvailable)
 847         AvailableQueue->push(NotReady[i]);
 848     }
 849     NotReady.clear();
 850
 851     if (CurSU)
 852       ScheduleNodeBottomUp(CurSU, CurCycle);
 853     ++CurCycle;
 854     AvailableQueue->setCurCycle(CurCycle);
 855   }
 856
 857   // Reverse the order if it is bottom up.
 858   std::reverse(Sequence.begin(), Sequence.end());
 859
 860 #ifndef NDEBUG
 861   VerifySchedule(isBottomUp);
 862 #endif
 863 }
 864
 865 //===----------------------------------------------------------------------===//
 866 //  Top-Down Scheduling
 867 //===----------------------------------------------------------------------===//
 868
 869 /// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to
 870 /// the AvailableQueue if the count reaches zero. Also update its cycle bound.
 871 void ScheduleDAGRRList::ReleaseSucc(SUnit *SU, const SDep *SuccEdge) {
 872   SUnit *SuccSU = SuccEdge->getSUnit();
 873
 874 #ifndef NDEBUG
 875   if (SuccSU->NumPredsLeft == 0) {
 876     dbgs() << "*** Scheduling failed! ***\n";
 877     SuccSU->dump(this);
 878     dbgs() << " has been released too many times!\n";
 879     llvm_unreachable(0);
 880   }
 881 #endif
 882   --SuccSU->NumPredsLeft;
 883
 884   // If all the node's predecessors are scheduled, this node is ready
 885   // to be scheduled. Ignore the special ExitSU node.
 886   if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU) {
 887     SuccSU->isAvailable = true;
 888     AvailableQueue->push(SuccSU);
 889   }
 890 }
 891
 892 void ScheduleDAGRRList::ReleaseSuccessors(SUnit *SU) {
 893   // Top down: release successors
 894   for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
 895        I != E; ++I) {
 896     assert(!I->isAssignedRegDep() &&
 897            "The list-tdrr scheduler doesn't yet support physreg dependencies!");
 898
 899     ReleaseSucc(SU, &*I);
 900   }
 901 }
 902
 903 /// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending
 904 /// count of its successors. If a successor pending count is zero, add it to
 905 /// the Available queue.
 906 void ScheduleDAGRRList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) {
 907   DEBUG(dbgs() << "*** Scheduling [" << CurCycle << "]: ");
 908   DEBUG(SU->dump(this));
 909
 910   assert(CurCycle >= SU->getDepth() && "Node scheduled above its depth!");
 911   SU->setDepthToAtLeast(CurCycle);
 912   Sequence.push_back(SU);
 913
 914   ReleaseSuccessors(SU);
 915   SU->isScheduled = true;
 916   AvailableQueue->ScheduledNode(SU);
 917 }
 918
 919 /// ListScheduleTopDown - The main loop of list scheduling for top-down
 920 /// schedulers.
 921 void ScheduleDAGRRList::ListScheduleTopDown() {
 922   unsigned CurCycle = 0;
 923   AvailableQueue->setCurCycle(CurCycle);
 924
 925   // Release any successors of the special Entry node.
 926   ReleaseSuccessors(&EntrySU);
 927
 928   // All leaves to Available queue.
 929   for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
 930     // It is available if it has no predecessors.
 931     if (SUnits[i].Preds.empty()) {
 932       AvailableQueue->push(&SUnits[i]);
 933       SUnits[i].isAvailable = true;
 934     }
 935   }
 936
 937   // While Available queue is not empty, grab the node with the highest
 938   // priority. If it is not ready put it back.  Schedule the node.
 939   Sequence.reserve(SUnits.size());
 940   while (!AvailableQueue->empty()) {
 941     SUnit *CurSU = AvailableQueue->pop();
 942
 943     if (CurSU)
 944       ScheduleNodeTopDown(CurSU, CurCycle);
 945     ++CurCycle;
 946     AvailableQueue->setCurCycle(CurCycle);
 947   }
 948
 949 #ifndef NDEBUG
 950   VerifySchedule(isBottomUp);
 951 #endif
 952 }
 953
 954
 955 //===----------------------------------------------------------------------===//
 956 //                RegReductionPriorityQueue Implementation
 957 //===----------------------------------------------------------------------===//
 958 //
 959 // This is a SchedulingPriorityQueue that schedules using Sethi Ullman numbers
 960 // to reduce register pressure.
 961 //
 962 namespace {
 963   template<class SF>
 964   class RegReductionPriorityQueue;
 965
 966   /// Sorting functions for the Available queue.
 967   struct bu_ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> {
 968     RegReductionPriorityQueue<bu_ls_rr_sort> *SPQ;
 969     bu_ls_rr_sort(RegReductionPriorityQueue<bu_ls_rr_sort> *spq) : SPQ(spq) {}
 970     bu_ls_rr_sort(const bu_ls_rr_sort &RHS) : SPQ(RHS.SPQ) {}
 971
 972     bool operator()(const SUnit* left, const SUnit* right) const;
 973   };
 974
 975   struct td_ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> {
 976     RegReductionPriorityQueue<td_ls_rr_sort> *SPQ;
 977     td_ls_rr_sort(RegReductionPriorityQueue<td_ls_rr_sort> *spq) : SPQ(spq) {}
 978     td_ls_rr_sort(const td_ls_rr_sort &RHS) : SPQ(RHS.SPQ) {}
 979
 980     bool operator()(const SUnit* left, const SUnit* right) const;
 981   };
 982
 983   struct src_ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> {
 984     RegReductionPriorityQueue<src_ls_rr_sort> *SPQ;
 985     src_ls_rr_sort(RegReductionPriorityQueue<src_ls_rr_sort> *spq)
 986       : SPQ(spq) {}
 987     src_ls_rr_sort(const src_ls_rr_sort &RHS)
 988       : SPQ(RHS.SPQ) {}
 989
 990     bool operator()(const SUnit* left, const SUnit* right) const;
 991   };
 992
 993   struct hybrid_ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> {
 994     RegReductionPriorityQueue<hybrid_ls_rr_sort> *SPQ;
 995     hybrid_ls_rr_sort(RegReductionPriorityQueue<hybrid_ls_rr_sort> *spq)
 996       : SPQ(spq) {}
 997     hybrid_ls_rr_sort(const hybrid_ls_rr_sort &RHS)
 998       : SPQ(RHS.SPQ) {}
 999
1000     bool operator()(const SUnit* left, const SUnit* right) const;
1001   };
1002 }  // end anonymous namespace
1003
1004 /// CalcNodeSethiUllmanNumber - Compute Sethi Ullman number.
1005 /// Smaller number is the higher priority.
1006 static unsigned
1007 CalcNodeSethiUllmanNumber(const SUnit *SU, std::vector<unsigned> &SUNumbers) {
1008   unsigned &SethiUllmanNumber = SUNumbers[SU->NodeNum];
1009   if (SethiUllmanNumber != 0)
1010     return SethiUllmanNumber;
1011
1012   unsigned Extra = 0;
1013   for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
1014        I != E; ++I) {
1015     if (I->isCtrl()) continue;  // ignore chain preds
1016     SUnit *PredSU = I->getSUnit();
1017     unsigned PredSethiUllman = CalcNodeSethiUllmanNumber(PredSU, SUNumbers);
1018     if (PredSethiUllman > SethiUllmanNumber) {
1019       SethiUllmanNumber = PredSethiUllman;
1020       Extra = 0;
1021     } else if (PredSethiUllman == SethiUllmanNumber)
1022       ++Extra;
1023   }
1024
1025   SethiUllmanNumber += Extra;
1026
1027   if (SethiUllmanNumber == 0)
1028     SethiUllmanNumber = 1;
1029
1030   return SethiUllmanNumber;
1031 }
1032
1033 namespace {
1034   template<class SF>
1035   class RegReductionPriorityQueue : public SchedulingPriorityQueue {
1036     std::vector<SUnit*> Queue;
1037     SF Picker;
1038     unsigned CurQueueId;
1039     bool TracksRegPressure;
1040
1041   protected:
1042     // SUnits - The SUnits for the current graph.
1043     std::vector<SUnit> *SUnits;
1044
1045     MachineFunction &MF;
1046     const TargetInstrInfo *TII;
1047     const TargetRegisterInfo *TRI;
1048     const TargetLowering *TLI;
1049     ScheduleDAGRRList *scheduleDAG;
1050
1051     // SethiUllmanNumbers - The SethiUllman number for each node.
1052     std::vector<unsigned> SethiUllmanNumbers;
1053
1054     /// RegPressure - Tracking current reg pressure per register class.
1055     ///
1056     std::vector<unsigned> RegPressure;
1057
1058     /// RegLimit - Tracking the number of allocatable registers per register
1059     /// class.
1060     std::vector<unsigned> RegLimit;
1061
1062   public:
1063     RegReductionPriorityQueue(MachineFunction &mf,
1064                               bool tracksrp,
1065                               const TargetInstrInfo *tii,
1066                               const TargetRegisterInfo *tri,
1067                               const TargetLowering *tli)
1068       : Picker(this), CurQueueId(0), TracksRegPressure(tracksrp),
1069         MF(mf), TII(tii), TRI(tri), TLI(tli), scheduleDAG(NULL) {
1070       if (TracksRegPressure) {
1071         unsigned NumRC = TRI->getNumRegClasses();
1072         RegLimit.resize(NumRC);
1073         RegPressure.resize(NumRC);
1074         std::fill(RegLimit.begin(), RegLimit.end(), 0);
1075         std::fill(RegPressure.begin(), RegPressure.end(), 0);
1076         for (TargetRegisterInfo::regclass_iterator I = TRI->regclass_begin(),
1077                E = TRI->regclass_end(); I != E; ++I)
1078           RegLimit[(*I)->getID()] = tri->getAllocatableSet(MF, *I).count() - 1;
1079       }
1080     }
1081
1082     void initNodes(std::vector<SUnit> &sunits) {
1083       SUnits = &sunits;
1084       // Add pseudo dependency edges for two-address nodes.
1085       AddPseudoTwoAddrDeps();
1086       // Reroute edges to nodes with multiple uses.
1087       PrescheduleNodesWithMultipleUses();
1088       // Calculate node priorities.
1089       CalculateSethiUllmanNumbers();
1090     }
1091
1092     void addNode(const SUnit *SU) {
1093       unsigned SUSize = SethiUllmanNumbers.size();
1094       if (SUnits->size() > SUSize)
1095         SethiUllmanNumbers.resize(SUSize*2, 0);
1096       CalcNodeSethiUllmanNumber(SU, SethiUllmanNumbers);
1097     }
1098
1099     void updateNode(const SUnit *SU) {
1100       SethiUllmanNumbers[SU->NodeNum] = 0;
1101       CalcNodeSethiUllmanNumber(SU, SethiUllmanNumbers);
1102     }
1103
1104     void releaseState() {
1105       SUnits = 0;
1106       SethiUllmanNumbers.clear();
1107       std::fill(RegPressure.begin(), RegPressure.end(), 0);
1108     }
1109
1110     unsigned getNodePriority(const SUnit *SU) const {
1111       assert(SU->NodeNum < SethiUllmanNumbers.size());
1112       unsigned Opc = SU->getNode() ? SU->getNode()->getOpcode() : 0;
1113       if (Opc == ISD::TokenFactor || Opc == ISD::CopyToReg)
1114         // CopyToReg should be close to its uses to facilitate coalescing and
1115         // avoid spilling.
1116         return 0;
1117       if (Opc == TargetOpcode::EXTRACT_SUBREG ||
1118           Opc == TargetOpcode::SUBREG_TO_REG ||
1119           Opc == TargetOpcode::INSERT_SUBREG)
1120         // EXTRACT_SUBREG, INSERT_SUBREG, and SUBREG_TO_REG nodes should be
1121         // close to their uses to facilitate coalescing.
1122         return 0;
1123       if (SU->NumSuccs == 0 && SU->NumPreds != 0)
1124         // If SU does not have a register use, i.e. it doesn't produce a value
1125         // that would be consumed (e.g. store), then it terminates a chain of
1126         // computation.  Give it a large SethiUllman number so it will be
1127         // scheduled right before its predecessors that it doesn't lengthen
1128         // their live ranges.
1129         return 0xffff;
1130       if (SU->NumPreds == 0 && SU->NumSuccs != 0)
1131         // If SU does not have a register def, schedule it close to its uses
1132         // because it does not lengthen any live ranges.
1133         return 0;
1134       return SethiUllmanNumbers[SU->NodeNum];
1135     }
1136
1137     unsigned getNodeOrdering(const SUnit *SU) const {
1138       return scheduleDAG->DAG->GetOrdering(SU->getNode());
1139     }
1140
1141     bool empty() const { return Queue.empty(); }
1142
1143     void push(SUnit *U) {
1144       assert(!U->NodeQueueId && "Node in the queue already");
1145       U->NodeQueueId = ++CurQueueId;
1146       Queue.push_back(U);
1147     }
1148
1149     SUnit *pop() {
1150       if (empty()) return NULL;
1151       std::vector<SUnit *>::iterator Best = Queue.begin();
1152       for (std::vector<SUnit *>::iterator I = llvm::next(Queue.begin()),
1153            E = Queue.end(); I != E; ++I)
1154         if (Picker(*Best, *I))
1155           Best = I;
1156       SUnit *V = *Best;
1157       if (Best != prior(Queue.end()))
1158         std::swap(*Best, Queue.back());
1159       Queue.pop_back();
1160       V->NodeQueueId = 0;
1161       return V;
1162     }
1163
1164     void remove(SUnit *SU) {
1165       assert(!Queue.empty() && "Queue is empty!");
1166       assert(SU->NodeQueueId != 0 && "Not in queue!");
1167       std::vector<SUnit *>::iterator I = std::find(Queue.begin(), Queue.end(),
1168                                                    SU);
1169       if (I != prior(Queue.end()))
1170         std::swap(*I, Queue.back());
1171       Queue.pop_back();
1172       SU->NodeQueueId = 0;
1173     }
1174
1175     bool HighRegPressure(const SUnit *SU) const {
1176       if (!TLI)
1177         return false;
1178
1179       for (SUnit::const_pred_iterator I = SU->Preds.begin(),E = SU->Preds.end();
1180            I != E; ++I) {
1181         if (I->isCtrl())
1182           continue;
1183         SUnit *PredSU = I->getSUnit();
1184         const SDNode *PN = PredSU->getNode();
1185         if (!PN->isMachineOpcode()) {
1186           if (PN->getOpcode() == ISD::CopyToReg) {
1187             EVT VT = PN->getOperand(1).getValueType();
1188             unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
1189             unsigned Cost = TLI->getRepRegClassCostFor(VT);
1190             if (RegLimit[RCId] < (RegPressure[RCId] + Cost))
1191               return true;
1192           }
1193           continue;
1194         }
1195         unsigned NumDefs = TII->get(PN->getMachineOpcode()).getNumDefs();
1196         for (unsigned i = 0; i != NumDefs; ++i) {
1197           EVT VT = PN->getValueType(i);
1198           if (!PN->hasAnyUseOfValue(i))
1199             continue;
1200           unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
1201           unsigned Cost = TLI->getRepRegClassCostFor(VT);
1202           // Check if this increases register pressure of the specific register
1203           // class to the point where it would cause spills.
1204           if (RegLimit[RCId] < (RegPressure[RCId] + Cost))
1205             return true;
1206         }
1207       }
1208
1209       return false;
1210     }
1211
1212     void ScheduledNode(SUnit *SU) {
1213       if (!TracksRegPressure)
1214         return;
1215
1216       const SDNode *N = SU->getNode();
1217       if (!N->isMachineOpcode())
1218         return;
1219       unsigned Opc = N->getMachineOpcode();
1220       if (Opc == TargetOpcode::COPY_TO_REGCLASS ||
1221           Opc == TargetOpcode::REG_SEQUENCE ||
1222           Opc == TargetOpcode::IMPLICIT_DEF)
1223         return;
1224
1225       for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
1226            I != E; ++I) {
1227         if (I->isCtrl())
1228           continue;
1229         SUnit *PredSU = I->getSUnit();
1230         if (PredSU->NumSuccsLeft != PredSU->NumSuccs)
1231           continue;
1232         const SDNode *PN = PredSU->getNode();
1233         if (!PN->isMachineOpcode()) {
1234           if (PN->getOpcode() == ISD::CopyToReg) {
1235             EVT VT = PN->getOperand(1).getValueType();
1236             unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
1237             RegPressure[RCId] += TLI->getRepRegClassCostFor(VT);
1238           }
1239           continue;
1240         }
1241         unsigned POpc = PN->getMachineOpcode();
1242         if (POpc == TargetOpcode::IMPLICIT_DEF)
1243           continue;
1244         unsigned NumDefs = TII->get(PN->getMachineOpcode()).getNumDefs();
1245         for (unsigned i = 0; i != NumDefs; ++i) {
1246           EVT VT = PN->getValueType(i);
1247           if (!PN->hasAnyUseOfValue(i))
1248             continue;
1249           unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
1250           RegPressure[RCId] += TLI->getRepRegClassCostFor(VT);
1251         }
1252       }
1253
1254       if (!SU->NumSuccs)
1255         return;
1256       unsigned NumDefs = TII->get(N->getMachineOpcode()).getNumDefs();
1257       for (unsigned i = 0; i != NumDefs; ++i) {
1258         EVT VT = N->getValueType(i);
1259         if (!N->hasAnyUseOfValue(i))
1260           continue;
1261         unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
1262         if (RegPressure[RCId] < TLI->getRepRegClassCostFor(VT))
1263           // Register pressure tracking is imprecise. This can happen.
1264           RegPressure[RCId] = 0;
1265         else
1266           RegPressure[RCId] -= TLI->getRepRegClassCostFor(VT);
1267       }
1268
1269       dumpRegPressure();
1270     }
1271
1272     void UnscheduledNode(SUnit *SU) {
1273       if (!TracksRegPressure)
1274         return;
1275
1276       const SDNode *N = SU->getNode();
1277       if (!N->isMachineOpcode())
1278         return;
1279       unsigned Opc = N->getMachineOpcode();
1280       if (Opc == TargetOpcode::COPY_TO_REGCLASS ||
1281           Opc == TargetOpcode::REG_SEQUENCE ||
1282           Opc == TargetOpcode::IMPLICIT_DEF)
1283         return;
1284
1285       for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
1286            I != E; ++I) {
1287         if (I->isCtrl())
1288           continue;
1289         SUnit *PredSU = I->getSUnit();
1290         if (PredSU->NumSuccsLeft != PredSU->NumSuccs)
1291           continue;
1292         const SDNode *PN = PredSU->getNode();
1293         if (!PN->isMachineOpcode()) {
1294           if (PN->getOpcode() == ISD::CopyToReg) {
1295             EVT VT = PN->getOperand(1).getValueType();
1296             unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
1297             RegPressure[RCId] += TLI->getRepRegClassCostFor(VT);
1298           }
1299           continue;
1300         }
1301         unsigned POpc = PN->getMachineOpcode();
1302         if (POpc == TargetOpcode::IMPLICIT_DEF)
1303           continue;
1304         unsigned NumDefs = TII->get(PN->getMachineOpcode()).getNumDefs();
1305         for (unsigned i = 0; i != NumDefs; ++i) {
1306           EVT VT = PN->getValueType(i);
1307           if (!PN->hasAnyUseOfValue(i))
1308             continue;
1309           unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
1310           if (RegPressure[RCId] < TLI->getRepRegClassCostFor(VT))
1311             // Register pressure tracking is imprecise. This can happen.
1312             RegPressure[RCId] = 0;
1313           else
1314             RegPressure[RCId] -= TLI->getRepRegClassCostFor(VT);
1315         }
1316       }
1317
1318       if (!SU->NumSuccs)
1319         return;
1320       unsigned NumDefs = TII->get(N->getMachineOpcode()).getNumDefs();
1321       for (unsigned i = NumDefs, e = N->getNumValues(); i != e; ++i) {
1322         EVT VT = N->getValueType(i);
1323         if (VT == MVT::Flag || VT == MVT::Other)
1324           continue;
1325         if (!N->hasAnyUseOfValue(i))
1326           continue;
1327         unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
1328         RegPressure[RCId] += TLI->getRepRegClassCostFor(VT);
1329       }
1330
1331       dumpRegPressure();
1332     }
1333
1334     void setScheduleDAG(ScheduleDAGRRList *scheduleDag) {
1335       scheduleDAG = scheduleDag;
1336     }
1337
1338     void dumpRegPressure() const {
1339       for (TargetRegisterInfo::regclass_iterator I = TRI->regclass_begin(),
1340              E = TRI->regclass_end(); I != E; ++I) {
1341         const TargetRegisterClass *RC = *I;
1342         unsigned Id = RC->getID();
1343         unsigned RP = RegPressure[Id];
1344         if (!RP) continue;
1345         DEBUG(dbgs() << RC->getName() << ": " << RP << " / " << RegLimit[Id]
1346               << '\n');
1347       }
1348     }
1349
1350   protected:
1351     bool canClobber(const SUnit *SU, const SUnit *Op);
1352     void AddPseudoTwoAddrDeps();
1353     void PrescheduleNodesWithMultipleUses();
1354     void CalculateSethiUllmanNumbers();
1355   };
1356
1357   typedef RegReductionPriorityQueue<bu_ls_rr_sort>
1358     BURegReductionPriorityQueue;
1359
1360   typedef RegReductionPriorityQueue<td_ls_rr_sort>
1361     TDRegReductionPriorityQueue;
1362
1363   typedef RegReductionPriorityQueue<src_ls_rr_sort>
1364     SrcRegReductionPriorityQueue;
1365
1366   typedef RegReductionPriorityQueue<hybrid_ls_rr_sort>
1367     HybridBURRPriorityQueue;
1368 }
1369
1370 /// closestSucc - Returns the scheduled cycle of the successor which is
1371 /// closest to the current cycle.
1372 static unsigned closestSucc(const SUnit *SU) {
1373   unsigned MaxHeight = 0;
1374   for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
1375        I != E; ++I) {
1376     if (I->isCtrl()) continue;  // ignore chain succs
1377     unsigned Height = I->getSUnit()->getHeight();
1378     // If there are bunch of CopyToRegs stacked up, they should be considered
1379     // to be at the same position.
1380     if (I->getSUnit()->getNode() &&
1381         I->getSUnit()->getNode()->getOpcode() == ISD::CopyToReg)
1382       Height = closestSucc(I->getSUnit())+1;
1383     if (Height > MaxHeight)
1384       MaxHeight = Height;
1385   }
1386   return MaxHeight;
1387 }
1388
1389 /// calcMaxScratches - Returns an cost estimate of the worse case requirement
1390 /// for scratch registers, i.e. number of data dependencies.
1391 static unsigned calcMaxScratches(const SUnit *SU) {
1392   unsigned Scratches = 0;
1393   for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
1394        I != E; ++I) {
1395     if (I->isCtrl()) continue;  // ignore chain preds
1396     Scratches++;
1397   }
1398   return Scratches;
1399 }
1400
1401 template <typename RRSort>
1402 static bool BURRSort(const SUnit *left, const SUnit *right,
1403                      const RegReductionPriorityQueue<RRSort> *SPQ) {
1404   unsigned LPriority = SPQ->getNodePriority(left);
1405   unsigned RPriority = SPQ->getNodePriority(right);
1406   if (LPriority != RPriority)
1407     return LPriority > RPriority;
1408
1409   // Try schedule def + use closer when Sethi-Ullman numbers are the same.
1410   // e.g.
1411   // t1 = op t2, c1
1412   // t3 = op t4, c2
1413   //
1414   // and the following instructions are both ready.
1415   // t2 = op c3
1416   // t4 = op c4
1417   //
1418   // Then schedule t2 = op first.
1419   // i.e.
1420   // t4 = op c4
1421   // t2 = op c3
1422   // t1 = op t2, c1
1423   // t3 = op t4, c2
1424   //
1425   // This creates more short live intervals.
1426   unsigned LDist = closestSucc(left);
1427   unsigned RDist = closestSucc(right);
1428   if (LDist != RDist)
1429     return LDist < RDist;
1430
1431   // How many registers becomes live when the node is scheduled.
1432   unsigned LScratch = calcMaxScratches(left);
1433   unsigned RScratch = calcMaxScratches(right);
1434   if (LScratch != RScratch)
1435     return LScratch > RScratch;
1436
1437   if (left->getHeight() != right->getHeight())
1438     return left->getHeight() > right->getHeight();
1439
1440   if (left->getDepth() != right->getDepth())
1441     return left->getDepth() < right->getDepth();
1442
1443   assert(left->NodeQueueId && right->NodeQueueId &&
1444          "NodeQueueId cannot be zero");
1445   return (left->NodeQueueId > right->NodeQueueId);
1446 }
1447
1448 // Bottom up
1449 bool bu_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const {
1450   return BURRSort(left, right, SPQ);
1451 }
1452
1453 // Source order, otherwise bottom up.
1454 bool src_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const {
1455   unsigned LOrder = SPQ->getNodeOrdering(left);
1456   unsigned ROrder = SPQ->getNodeOrdering(right);
1457
1458   // Prefer an ordering where the lower the non-zero order number, the higher
1459   // the preference.
1460   if ((LOrder || ROrder) && LOrder != ROrder)
1461     return LOrder != 0 && (LOrder < ROrder || ROrder == 0);
1462
1463   return BURRSort(left, right, SPQ);
1464 }
1465
1466 bool hybrid_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const{
1467   bool LHigh = SPQ->HighRegPressure(left);
1468   bool RHigh = SPQ->HighRegPressure(right);
1469   if (LHigh && !RHigh)
1470     return true;
1471   else if (!LHigh && RHigh)
1472     return false;
1473   else if (!LHigh && !RHigh) {
1474     // Low register pressure situation, schedule for latency if possible.
1475     bool LStall = left->SchedulingPref == Sched::Latency &&
1476       SPQ->getCurCycle() < left->getHeight();
1477     bool RStall = right->SchedulingPref == Sched::Latency &&
1478       SPQ->getCurCycle() < right->getHeight();
1479     // If scheduling one of the node will cause a pipeline stall, delay it.
1480     // If scheduling either one of the node will cause a pipeline stall, sort
1481     // them according to their height.
1482     // If neither will cause a pipeline stall, try to reduce register pressure.
1483     if (LStall) {
1484       if (!RStall)
1485         return true;
1486       if (left->getHeight() != right->getHeight())
1487         return left->getHeight() > right->getHeight();
1488     } else if (RStall)
1489       return false;
1490
1491     // If either node is scheduling for latency, sort them by height and latency
1492     // first.
1493     if (left->SchedulingPref == Sched::Latency ||
1494         right->SchedulingPref == Sched::Latency) {
1495       if (left->getHeight() != right->getHeight())
1496         return left->getHeight() > right->getHeight();
1497       if (left->Latency != right->Latency)
1498         return left->Latency > right->Latency;
1499     }
1500   }
1501
1502   return BURRSort(left, right, SPQ);
1503 }
1504
1505 template<class SF>
1506 bool
1507 RegReductionPriorityQueue<SF>::canClobber(const SUnit *SU, const SUnit *Op) {
1508   if (SU->isTwoAddress) {
1509     unsigned Opc = SU->getNode()->getMachineOpcode();
1510     const TargetInstrDesc &TID = TII->get(Opc);
1511     unsigned NumRes = TID.getNumDefs();
1512     unsigned NumOps = TID.getNumOperands() - NumRes;
1513     for (unsigned i = 0; i != NumOps; ++i) {
1514       if (TID.getOperandConstraint(i+NumRes, TOI::TIED_TO) != -1) {
1515         SDNode *DU = SU->getNode()->getOperand(i).getNode();
1516         if (DU->getNodeId() != -1 &&
1517             Op->OrigNode == &(*SUnits)[DU->getNodeId()])
1518           return true;
1519       }
1520     }
1521   }
1522   return false;
1523 }
1524
1525 /// hasCopyToRegUse - Return true if SU has a value successor that is a
1526 /// CopyToReg node.
1527 static bool hasCopyToRegUse(const SUnit *SU) {
1528   for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
1529        I != E; ++I) {
1530     if (I->isCtrl()) continue;
1531     const SUnit *SuccSU = I->getSUnit();
1532     if (SuccSU->getNode() && SuccSU->getNode()->getOpcode() == ISD::CopyToReg)
1533       return true;
1534   }
1535   return false;
1536 }
1537
1538 /// canClobberPhysRegDefs - True if SU would clobber one of SuccSU's
1539 /// physical register defs.
1540 static bool canClobberPhysRegDefs(const SUnit *SuccSU, const SUnit *SU,
1541                                   const TargetInstrInfo *TII,
1542                                   const TargetRegisterInfo *TRI) {
1543   SDNode *N = SuccSU->getNode();
1544   unsigned NumDefs = TII->get(N->getMachineOpcode()).getNumDefs();
1545   const unsigned *ImpDefs = TII->get(N->getMachineOpcode()).getImplicitDefs();
1546   assert(ImpDefs && "Caller should check hasPhysRegDefs");
1547   for (const SDNode *SUNode = SU->getNode(); SUNode;
1548        SUNode = SUNode->getFlaggedNode()) {
1549     if (!SUNode->isMachineOpcode())
1550       continue;
1551     const unsigned *SUImpDefs =
1552       TII->get(SUNode->getMachineOpcode()).getImplicitDefs();
1553     if (!SUImpDefs)
1554       return false;
1555     for (unsigned i = NumDefs, e = N->getNumValues(); i != e; ++i) {
1556       EVT VT = N->getValueType(i);
1557       if (VT == MVT::Flag || VT == MVT::Other)
1558         continue;
1559       if (!N->hasAnyUseOfValue(i))
1560         continue;
1561       unsigned Reg = ImpDefs[i - NumDefs];
1562       for (;*SUImpDefs; ++SUImpDefs) {
1563         unsigned SUReg = *SUImpDefs;
1564         if (TRI->regsOverlap(Reg, SUReg))
1565           return true;
1566       }
1567     }
1568   }
1569   return false;
1570 }
1571
1572 /// PrescheduleNodesWithMultipleUses - Nodes with multiple uses
1573 /// are not handled well by the general register pressure reduction
1574 /// heuristics. When presented with code like this:
1575 ///
1576 ///      N
1577 ///    / |
1578 ///   /  |
1579 ///  U  store
1580 ///  |
1581 /// ...
1582 ///
1583 /// the heuristics tend to push the store up, but since the
1584 /// operand of the store has another use (U), this would increase
1585 /// the length of that other use (the U->N edge).
1586 ///
1587 /// This function transforms code like the above to route U's
1588 /// dependence through the store when possible, like this:
1589 ///
1590 ///      N
1591 ///      ||
1592 ///      ||
1593 ///     store
1594 ///       |
1595 ///       U
1596 ///       |
1597 ///      ...
1598 ///
1599 /// This results in the store being scheduled immediately
1600 /// after N, which shortens the U->N live range, reducing
1601 /// register pressure.
1602 ///
1603 template<class SF>
1604 void RegReductionPriorityQueue<SF>::PrescheduleNodesWithMultipleUses() {
1605   // Visit all the nodes in topological order, working top-down.
1606   for (unsigned i = 0, e = SUnits->size(); i != e; ++i) {
1607     SUnit *SU = &(*SUnits)[i];
1608     // For now, only look at nodes with no data successors, such as stores.
1609     // These are especially important, due to the heuristics in
1610     // getNodePriority for nodes with no data successors.
1611     if (SU->NumSuccs != 0)
1612       continue;
1613     // For now, only look at nodes with exactly one data predecessor.
1614     if (SU->NumPreds != 1)
1615       continue;
1616     // Avoid prescheduling copies to virtual registers, which don't behave
1617     // like other nodes from the perspective of scheduling heuristics.
1618     if (SDNode *N = SU->getNode())
1619       if (N->getOpcode() == ISD::CopyToReg &&
1620           TargetRegisterInfo::isVirtualRegister
1621             (cast<RegisterSDNode>(N->getOperand(1))->getReg()))
1622         continue;
1623
1624     // Locate the single data predecessor.
1625     SUnit *PredSU = 0;
1626     for (SUnit::const_pred_iterator II = SU->Preds.begin(),
1627          EE = SU->Preds.end(); II != EE; ++II)
1628       if (!II->isCtrl()) {
1629         PredSU = II->getSUnit();
1630         break;
1631       }
1632     assert(PredSU);
1633
1634     // Don't rewrite edges that carry physregs, because that requires additional
1635     // support infrastructure.
1636     if (PredSU->hasPhysRegDefs)
1637       continue;
1638     // Short-circuit the case where SU is PredSU's only data successor.
1639     if (PredSU->NumSuccs == 1)
1640       continue;
1641     // Avoid prescheduling to copies from virtual registers, which don't behave
1642     // like other nodes from the perspective of scheduling // heuristics.
1643     if (SDNode *N = SU->getNode())
1644       if (N->getOpcode() == ISD::CopyFromReg &&
1645           TargetRegisterInfo::isVirtualRegister
1646             (cast<RegisterSDNode>(N->getOperand(1))->getReg()))
1647         continue;
1648
1649     // Perform checks on the successors of PredSU.
1650     for (SUnit::const_succ_iterator II = PredSU->Succs.begin(),
1651          EE = PredSU->Succs.end(); II != EE; ++II) {
1652       SUnit *PredSuccSU = II->getSUnit();
1653       if (PredSuccSU == SU) continue;
1654       // If PredSU has another successor with no data successors, for
1655       // now don't attempt to choose either over the other.
1656       if (PredSuccSU->NumSuccs == 0)
1657         goto outer_loop_continue;
1658       // Don't break physical register dependencies.
1659       if (SU->hasPhysRegClobbers && PredSuccSU->hasPhysRegDefs)
1660         if (canClobberPhysRegDefs(PredSuccSU, SU, TII, TRI))
1661           goto outer_loop_continue;
1662       // Don't introduce graph cycles.
1663       if (scheduleDAG->IsReachable(SU, PredSuccSU))
1664         goto outer_loop_continue;
1665     }
1666
1667     // Ok, the transformation is safe and the heuristics suggest it is
1668     // profitable. Update the graph.
1669     DEBUG(dbgs() << "    Prescheduling SU #" << SU->NodeNum
1670                  << " next to PredSU #" << PredSU->NodeNum
1671                  << " to guide scheduling in the presence of multiple uses\n");
1672     for (unsigned i = 0; i != PredSU->Succs.size(); ++i) {
1673       SDep Edge = PredSU->Succs[i];
1674       assert(!Edge.isAssignedRegDep());
1675       SUnit *SuccSU = Edge.getSUnit();
1676       if (SuccSU != SU) {
1677         Edge.setSUnit(PredSU);
1678         scheduleDAG->RemovePred(SuccSU, Edge);
1679         scheduleDAG->AddPred(SU, Edge);
1680         Edge.setSUnit(SU);
1681         scheduleDAG->AddPred(SuccSU, Edge);
1682         --i;
1683       }
1684     }
1685   outer_loop_continue:;
1686   }
1687 }
1688
1689 /// AddPseudoTwoAddrDeps - If two nodes share an operand and one of them uses
1690 /// it as a def&use operand. Add a pseudo control edge from it to the other
1691 /// node (if it won't create a cycle) so the two-address one will be scheduled
1692 /// first (lower in the schedule). If both nodes are two-address, favor the
1693 /// one that has a CopyToReg use (more likely to be a loop induction update).
1694 /// If both are two-address, but one is commutable while the other is not
1695 /// commutable, favor the one that's not commutable.
1696 template<class SF>
1697 void RegReductionPriorityQueue<SF>::AddPseudoTwoAddrDeps() {
1698   for (unsigned i = 0, e = SUnits->size(); i != e; ++i) {
1699     SUnit *SU = &(*SUnits)[i];
1700     if (!SU->isTwoAddress)
1701       continue;
1702
1703     SDNode *Node = SU->getNode();
1704     if (!Node || !Node->isMachineOpcode() || SU->getNode()->getFlaggedNode())
1705       continue;
1706
1707     unsigned Opc = Node->getMachineOpcode();
1708     const TargetInstrDesc &TID = TII->get(Opc);
1709     unsigned NumRes = TID.getNumDefs();
1710     unsigned NumOps = TID.getNumOperands() - NumRes;
1711     for (unsigned j = 0; j != NumOps; ++j) {
1712       if (TID.getOperandConstraint(j+NumRes, TOI::TIED_TO) == -1)
1713         continue;
1714       SDNode *DU = SU->getNode()->getOperand(j).getNode();
1715       if (DU->getNodeId() == -1)
1716         continue;
1717       const SUnit *DUSU = &(*SUnits)[DU->getNodeId()];
1718       if (!DUSU) continue;
1719       for (SUnit::const_succ_iterator I = DUSU->Succs.begin(),
1720            E = DUSU->Succs.end(); I != E; ++I) {
1721         if (I->isCtrl()) continue;
1722         SUnit *SuccSU = I->getSUnit();
1723         if (SuccSU == SU)
1724           continue;
1725         // Be conservative. Ignore if nodes aren't at roughly the same
1726         // depth and height.
1727         if (SuccSU->getHeight() < SU->getHeight() &&
1728             (SU->getHeight() - SuccSU->getHeight()) > 1)
1729           continue;
1730         // Skip past COPY_TO_REGCLASS nodes, so that the pseudo edge
1731         // constrains whatever is using the copy, instead of the copy
1732         // itself. In the case that the copy is coalesced, this
1733         // preserves the intent of the pseudo two-address heurietics.
1734         while (SuccSU->Succs.size() == 1 &&
1735                SuccSU->getNode()->isMachineOpcode() &&
1736                SuccSU->getNode()->getMachineOpcode() ==
1737                  TargetOpcode::COPY_TO_REGCLASS)
1738           SuccSU = SuccSU->Succs.front().getSUnit();
1739         // Don't constrain non-instruction nodes.
1740         if (!SuccSU->getNode() || !SuccSU->getNode()->isMachineOpcode())
1741           continue;
1742         // Don't constrain nodes with physical register defs if the
1743         // predecessor can clobber them.
1744         if (SuccSU->hasPhysRegDefs && SU->hasPhysRegClobbers) {
1745           if (canClobberPhysRegDefs(SuccSU, SU, TII, TRI))
1746             continue;
1747         }
1748         // Don't constrain EXTRACT_SUBREG, INSERT_SUBREG, and SUBREG_TO_REG;
1749         // these may be coalesced away. We want them close to their uses.
1750         unsigned SuccOpc = SuccSU->getNode()->getMachineOpcode();
1751         if (SuccOpc == TargetOpcode::EXTRACT_SUBREG ||
1752             SuccOpc == TargetOpcode::INSERT_SUBREG ||
1753             SuccOpc == TargetOpcode::SUBREG_TO_REG)
1754           continue;
1755         if ((!canClobber(SuccSU, DUSU) ||
1756              (hasCopyToRegUse(SU) && !hasCopyToRegUse(SuccSU)) ||
1757              (!SU->isCommutable && SuccSU->isCommutable)) &&
1758             !scheduleDAG->IsReachable(SuccSU, SU)) {
1759           DEBUG(dbgs() << "    Adding a pseudo-two-addr edge from SU #"
1760                        << SU->NodeNum << " to SU #" << SuccSU->NodeNum << "\n");
1761           scheduleDAG->AddPred(SU, SDep(SuccSU, SDep::Order, /*Latency=*/0,
1762                                         /*Reg=*/0, /*isNormalMemory=*/false,
1763                                         /*isMustAlias=*/false,
1764                                         /*isArtificial=*/true));
1765         }
1766       }
1767     }
1768   }
1769 }
1770
1771 /// CalculateSethiUllmanNumbers - Calculate Sethi-Ullman numbers of all
1772 /// scheduling units.
1773 template<class SF>
1774 void RegReductionPriorityQueue<SF>::CalculateSethiUllmanNumbers() {
1775   SethiUllmanNumbers.assign(SUnits->size(), 0);
1776
1777   for (unsigned i = 0, e = SUnits->size(); i != e; ++i)
1778     CalcNodeSethiUllmanNumber(&(*SUnits)[i], SethiUllmanNumbers);
1779 }
1780
1781 /// LimitedSumOfUnscheduledPredsOfSuccs - Compute the sum of the unscheduled
1782 /// predecessors of the successors of the SUnit SU. Stop when the provided
1783 /// limit is exceeded.
1784 static unsigned LimitedSumOfUnscheduledPredsOfSuccs(const SUnit *SU,
1785                                                     unsigned Limit) {
1786   unsigned Sum = 0;
1787   for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
1788        I != E; ++I) {
1789     const SUnit *SuccSU = I->getSUnit();
1790     for (SUnit::const_pred_iterator II = SuccSU->Preds.begin(),
1791          EE = SuccSU->Preds.end(); II != EE; ++II) {
1792       SUnit *PredSU = II->getSUnit();
1793       if (!PredSU->isScheduled)
1794         if (++Sum > Limit)
1795           return Sum;
1796     }
1797   }
1798   return Sum;
1799 }
1800
1801
1802 // Top down
1803 bool td_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const {
1804   unsigned LPriority = SPQ->getNodePriority(left);
1805   unsigned RPriority = SPQ->getNodePriority(right);
1806   bool LIsTarget = left->getNode() && left->getNode()->isMachineOpcode();
1807   bool RIsTarget = right->getNode() && right->getNode()->isMachineOpcode();
1808   bool LIsFloater = LIsTarget && left->NumPreds == 0;
1809   bool RIsFloater = RIsTarget && right->NumPreds == 0;
1810   unsigned LBonus = (LimitedSumOfUnscheduledPredsOfSuccs(left,1) == 1) ? 2 : 0;
1811   unsigned RBonus = (LimitedSumOfUnscheduledPredsOfSuccs(right,1) == 1) ? 2 : 0;
1812
1813   if (left->NumSuccs == 0 && right->NumSuccs != 0)
1814     return false;
1815   else if (left->NumSuccs != 0 && right->NumSuccs == 0)
1816     return true;
1817
1818   if (LIsFloater)
1819     LBonus -= 2;
1820   if (RIsFloater)
1821     RBonus -= 2;
1822   if (left->NumSuccs == 1)
1823     LBonus += 2;
1824   if (right->NumSuccs == 1)
1825     RBonus += 2;
1826
1827   if (LPriority+LBonus != RPriority+RBonus)
1828     return LPriority+LBonus < RPriority+RBonus;
1829
1830   if (left->getDepth() != right->getDepth())
1831     return left->getDepth() < right->getDepth();
1832
1833   if (left->NumSuccsLeft != right->NumSuccsLeft)
1834     return left->NumSuccsLeft > right->NumSuccsLeft;
1835
1836   assert(left->NodeQueueId && right->NodeQueueId &&
1837          "NodeQueueId cannot be zero");
1838   return (left->NodeQueueId > right->NodeQueueId);
1839 }
1840
1841 //===----------------------------------------------------------------------===//
1842 //                         Public Constructor Functions
1843 //===----------------------------------------------------------------------===//
1844
1845 llvm::ScheduleDAGSDNodes *
1846 llvm::createBURRListDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level) {
1847   const TargetMachine &TM = IS->TM;
1848   const TargetInstrInfo *TII = TM.getInstrInfo();
1849   const TargetRegisterInfo *TRI = TM.getRegisterInfo();
1850
1851   BURegReductionPriorityQueue *PQ =
1852     new BURegReductionPriorityQueue(*IS->MF, false, TII, TRI, 0);
1853   ScheduleDAGRRList *SD = new ScheduleDAGRRList(*IS->MF, true, false, PQ);
1854   PQ->setScheduleDAG(SD);
1855   return SD;
1856 }
1857
1858 llvm::ScheduleDAGSDNodes *
1859 llvm::createTDRRListDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level) {
1860   const TargetMachine &TM = IS->TM;
1861   const TargetInstrInfo *TII = TM.getInstrInfo();
1862   const TargetRegisterInfo *TRI = TM.getRegisterInfo();
1863
1864   TDRegReductionPriorityQueue *PQ =
1865     new TDRegReductionPriorityQueue(*IS->MF, false, TII, TRI, 0);
1866   ScheduleDAGRRList *SD = new ScheduleDAGRRList(*IS->MF, false, false, PQ);
1867   PQ->setScheduleDAG(SD);
1868   return SD;
1869 }
1870
1871 llvm::ScheduleDAGSDNodes *
1872 llvm::createSourceListDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level) {
1873   const TargetMachine &TM = IS->TM;
1874   const TargetInstrInfo *TII = TM.getInstrInfo();
1875   const TargetRegisterInfo *TRI = TM.getRegisterInfo();
1876
1877   SrcRegReductionPriorityQueue *PQ =
1878     new SrcRegReductionPriorityQueue(*IS->MF, false, TII, TRI, 0);
1879   ScheduleDAGRRList *SD = new ScheduleDAGRRList(*IS->MF, true, false, PQ);
1880   PQ->setScheduleDAG(SD);
1881   return SD;
1882 }
1883
1884 llvm::ScheduleDAGSDNodes *
1885 llvm::createHybridListDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level) {
1886   const TargetMachine &TM = IS->TM;
1887   const TargetInstrInfo *TII = TM.getInstrInfo();
1888   const TargetRegisterInfo *TRI = TM.getRegisterInfo();
1889   const TargetLowering *TLI = &IS->getTargetLowering();
1890
1891   HybridBURRPriorityQueue *PQ =
1892     new HybridBURRPriorityQueue(*IS->MF, true, TII, TRI,
1893                                 (RegPressureAware ? TLI : 0));
1894   ScheduleDAGRRList *SD = new ScheduleDAGRRList(*IS->MF, true, true, PQ);
1895   PQ->setScheduleDAG(SD);
1896   return SD;
1897 }