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