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