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/CodeGen/SchedulerRegistry.h"
  21 #include "llvm/CodeGen/SelectionDAGISel.h"
  22 #include "llvm/Target/TargetRegisterInfo.h"
  23 #include "llvm/Target/TargetData.h"
  24 #include "llvm/Target/TargetMachine.h"
  25 #include "llvm/Target/TargetInstrInfo.h"
  26 #include "llvm/Support/Debug.h"
  27 #include "llvm/Support/Compiler.h"
  28 #include "llvm/ADT/PriorityQueue.h"
  29 #include "llvm/ADT/SmallSet.h"
  30 #include "llvm/ADT/Statistic.h"
  31 #include "llvm/ADT/STLExtras.h"
  32 #include <climits>
  33 #include "llvm/Support/CommandLine.h"
  34 using namespace llvm;
  35
  36 STATISTIC(NumBacktracks, "Number of times scheduler backtracked");
  37 STATISTIC(NumUnfolds,    "Number of nodes unfolded");
  38 STATISTIC(NumDups,       "Number of duplicated nodes");
  39 STATISTIC(NumPRCopies,   "Number of physical register copies");
  40
  41 static RegisterScheduler
  42   burrListDAGScheduler("list-burr",
  43                        "Bottom-up register reduction list scheduling",
  44                        createBURRListDAGScheduler);
  45 static RegisterScheduler
  46   tdrListrDAGScheduler("list-tdrr",
  47                        "Top-down register reduction list scheduling",
  48                        createTDRRListDAGScheduler);
  49
  50 namespace {
  51 //===----------------------------------------------------------------------===//
  52 /// ScheduleDAGRRList - The actual register reduction list scheduler
  53 /// implementation.  This supports both top-down and bottom-up scheduling.
  54 ///
  55 class VISIBILITY_HIDDEN ScheduleDAGRRList : public ScheduleDAGSDNodes {
  56 private:
  57   /// isBottomUp - This is true if the scheduling problem is bottom-up, false if
  58   /// it is top-down.
  59   bool isBottomUp;
  60
  61   /// AvailableQueue - The priority queue to use for the available SUnits.
  62   SchedulingPriorityQueue *AvailableQueue;
  63
  64   /// LiveRegDefs - A set of physical registers and their definition
  65   /// that are "live". These nodes must be scheduled before any other nodes that
  66   /// modifies the registers can be scheduled.
  67   unsigned NumLiveRegs;
  68   std::vector<SUnit*> LiveRegDefs;
  69   std::vector<unsigned> LiveRegCycles;
  70
  71   /// Topo - A topological ordering for SUnits which permits fast IsReachable
  72   /// and similar queries.
  73   ScheduleDAGTopologicalSort Topo;
  74
  75 public:
  76   ScheduleDAGRRList(MachineFunction &mf,
  77                     bool isbottomup,
  78                     SchedulingPriorityQueue *availqueue)
  79     : ScheduleDAGSDNodes(mf), isBottomUp(isbottomup),
  80       AvailableQueue(availqueue), Topo(SUnits) {
  81     }
  82
  83   ~ScheduleDAGRRList() {
  84     delete AvailableQueue;
  85   }
  86
  87   void Schedule();
  88
  89   /// IsReachable - Checks if SU is reachable from TargetSU.
  90   bool IsReachable(const SUnit *SU, const SUnit *TargetSU) {
  91     return Topo.IsReachable(SU, TargetSU);
  92   }
  93
  94   /// WillCreateCycle - Returns true if adding an edge from SU to TargetSU will
  95   /// create a cycle.
  96   bool WillCreateCycle(SUnit *SU, SUnit *TargetSU) {
  97     return Topo.WillCreateCycle(SU, TargetSU);
  98   }
  99
 100   /// AddPred - adds a predecessor edge to SUnit SU.
 101   /// This returns true if this is a new predecessor.
 102   /// Updates the topological ordering if required.
 103   void AddPred(SUnit *SU, const SDep &D) {
 104     Topo.AddPred(SU, D.getSUnit());
 105     SU->addPred(D);
 106   }
 107
 108   /// RemovePred - removes a predecessor edge from SUnit SU.
 109   /// This returns true if an edge was removed.
 110   /// Updates the topological ordering if required.
 111   void RemovePred(SUnit *SU, const SDep &D) {
 112     Topo.RemovePred(SU, D.getSUnit());
 113     SU->removePred(D);
 114   }
 115
 116 private:
 117   void ReleasePred(SUnit *SU, const SDep *PredEdge);
 118   void ReleaseSucc(SUnit *SU, const SDep *SuccEdge);
 119   void CapturePred(SDep *PredEdge);
 120   void ScheduleNodeBottomUp(SUnit*, unsigned);
 121   void ScheduleNodeTopDown(SUnit*, unsigned);
 122   void UnscheduleNodeBottomUp(SUnit*);
 123   void BacktrackBottomUp(SUnit*, unsigned, unsigned&);
 124   SUnit *CopyAndMoveSuccessors(SUnit*);
 125   void InsertCopiesAndMoveSuccs(SUnit*, unsigned,
 126                                 const TargetRegisterClass*,
 127                                 const TargetRegisterClass*,
 128                                 SmallVector<SUnit*, 2>&);
 129   bool DelayForLiveRegsBottomUp(SUnit*, SmallVector<unsigned, 4>&);
 130   void ListScheduleTopDown();
 131   void ListScheduleBottomUp();
 132
 133
 134   /// CreateNewSUnit - Creates a new SUnit and returns a pointer to it.
 135   /// Updates the topological ordering if required.
 136   SUnit *CreateNewSUnit(SDNode *N) {
 137     unsigned NumSUnits = SUnits.size();
 138     SUnit *NewNode = NewSUnit(N);
 139     // Update the topological ordering.
 140     if (NewNode->NodeNum >= NumSUnits)
 141       Topo.InitDAGTopologicalSorting();
 142     return NewNode;
 143   }
 144
 145   /// CreateClone - Creates a new SUnit from an existing one.
 146   /// Updates the topological ordering if required.
 147   SUnit *CreateClone(SUnit *N) {
 148     unsigned NumSUnits = SUnits.size();
 149     SUnit *NewNode = Clone(N);
 150     // Update the topological ordering.
 151     if (NewNode->NodeNum >= NumSUnits)
 152       Topo.InitDAGTopologicalSorting();
 153     return NewNode;
 154   }
 155
 156   /// ForceUnitLatencies - Return true, since register-pressure-reducing
 157   /// scheduling doesn't need actual latency information.
 158   bool ForceUnitLatencies() const { return true; }
 159 };
 160 }  // end anonymous namespace
 161
 162
 163 /// Schedule - Schedule the DAG using list scheduling.
 164 void ScheduleDAGRRList::Schedule() {
 165   DOUT << "********** List Scheduling **********\n";
 166
 167   NumLiveRegs = 0;
 168   LiveRegDefs.resize(TRI->getNumRegs(), NULL);
 169   LiveRegCycles.resize(TRI->getNumRegs(), 0);
 170
 171   // Build the scheduling graph.
 172   BuildSchedGraph();
 173
 174   DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
 175           SUnits[su].dumpAll(this));
 176   Topo.InitDAGTopologicalSorting();
 177
 178   AvailableQueue->initNodes(SUnits);
 179
 180   // Execute the actual scheduling loop Top-Down or Bottom-Up as appropriate.
 181   if (isBottomUp)
 182     ListScheduleBottomUp();
 183   else
 184     ListScheduleTopDown();
 185
 186   AvailableQueue->releaseState();
 187 }
 188
 189 //===----------------------------------------------------------------------===//
 190 //  Bottom-Up Scheduling
 191 //===----------------------------------------------------------------------===//
 192
 193 /// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to
 194 /// the AvailableQueue if the count reaches zero. Also update its cycle bound.
 195 void ScheduleDAGRRList::ReleasePred(SUnit *SU, const SDep *PredEdge) {
 196   SUnit *PredSU = PredEdge->getSUnit();
 197   --PredSU->NumSuccsLeft;
 198
 199 #ifndef NDEBUG
 200   if (PredSU->NumSuccsLeft < 0) {
 201     cerr << "*** Scheduling failed! ***\n";
 202     PredSU->dump(this);
 203     cerr << " has been released too many times!\n";
 204     assert(0);
 205   }
 206 #endif
 207
 208   if (PredSU->NumSuccsLeft == 0) {
 209     PredSU->isAvailable = true;
 210     AvailableQueue->push(PredSU);
 211   }
 212 }
 213
 214 /// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending
 215 /// count of its predecessors. If a predecessor pending count is zero, add it to
 216 /// the Available queue.
 217 void ScheduleDAGRRList::ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle) {
 218   DOUT << "*** Scheduling [" << CurCycle << "]: ";
 219   DEBUG(SU->dump(this));
 220
 221   assert(CurCycle >= SU->getHeight() && "Node scheduled below its height!");
 222   SU->setHeightToAtLeast(CurCycle);
 223   Sequence.push_back(SU);
 224
 225   // Bottom up: release predecessors
 226   for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
 227        I != E; ++I) {
 228     ReleasePred(SU, &*I);
 229     if (I->isAssignedRegDep()) {
 230       // This is a physical register dependency and it's impossible or
 231       // expensive to copy the register. Make sure nothing that can
 232       // clobber the register is scheduled between the predecessor and
 233       // this node.
 234       if (!LiveRegDefs[I->getReg()]) {
 235         ++NumLiveRegs;
 236         LiveRegDefs[I->getReg()] = I->getSUnit();
 237         LiveRegCycles[I->getReg()] = CurCycle;
 238       }
 239     }
 240   }
 241
 242   // Release all the implicit physical register defs that are live.
 243   for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
 244        I != E; ++I) {
 245     if (I->isAssignedRegDep()) {
 246       if (LiveRegCycles[I->getReg()] == I->getSUnit()->getHeight()) {
 247         assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");
 248         assert(LiveRegDefs[I->getReg()] == SU &&
 249                "Physical register dependency violated?");
 250         --NumLiveRegs;
 251         LiveRegDefs[I->getReg()] = NULL;
 252         LiveRegCycles[I->getReg()] = 0;
 253       }
 254     }
 255   }
 256
 257   SU->isScheduled = true;
 258   AvailableQueue->ScheduledNode(SU);
 259 }
 260
 261 /// CapturePred - This does the opposite of ReleasePred. Since SU is being
 262 /// unscheduled, incrcease the succ left count of its predecessors. Remove
 263 /// them from AvailableQueue if necessary.
 264 void ScheduleDAGRRList::CapturePred(SDep *PredEdge) {
 265   SUnit *PredSU = PredEdge->getSUnit();
 266   if (PredSU->isAvailable) {
 267     PredSU->isAvailable = false;
 268     if (!PredSU->isPending)
 269       AvailableQueue->remove(PredSU);
 270   }
 271
 272   ++PredSU->NumSuccsLeft;
 273 }
 274
 275 /// UnscheduleNodeBottomUp - Remove the node from the schedule, update its and
 276 /// its predecessor states to reflect the change.
 277 void ScheduleDAGRRList::UnscheduleNodeBottomUp(SUnit *SU) {
 278   DOUT << "*** Unscheduling [" << SU->getHeight() << "]: ";
 279   DEBUG(SU->dump(this));
 280
 281   AvailableQueue->UnscheduledNode(SU);
 282
 283   for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
 284        I != E; ++I) {
 285     CapturePred(&*I);
 286     if (I->isAssignedRegDep() && SU->getHeight() == LiveRegCycles[I->getReg()]) {
 287       assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");
 288       assert(LiveRegDefs[I->getReg()] == I->getSUnit() &&
 289              "Physical register dependency violated?");
 290       --NumLiveRegs;
 291       LiveRegDefs[I->getReg()] = NULL;
 292       LiveRegCycles[I->getReg()] = 0;
 293     }
 294   }
 295
 296   for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
 297        I != E; ++I) {
 298     if (I->isAssignedRegDep()) {
 299       if (!LiveRegDefs[I->getReg()]) {
 300         LiveRegDefs[I->getReg()] = SU;
 301         ++NumLiveRegs;
 302       }
 303       if (I->getSUnit()->getHeight() < LiveRegCycles[I->getReg()])
 304         LiveRegCycles[I->getReg()] = I->getSUnit()->getHeight();
 305     }
 306   }
 307
 308   SU->setHeightDirty();
 309   SU->isScheduled = false;
 310   SU->isAvailable = true;
 311   AvailableQueue->push(SU);
 312 }
 313
 314 /// BacktrackBottomUp - Backtrack scheduling to a previous cycle specified in
 315 /// BTCycle in order to schedule a specific node.
 316 void ScheduleDAGRRList::BacktrackBottomUp(SUnit *SU, unsigned BtCycle,
 317                                           unsigned &CurCycle) {
 318   SUnit *OldSU = NULL;
 319   while (CurCycle > BtCycle) {
 320     OldSU = Sequence.back();
 321     Sequence.pop_back();
 322     if (SU->isSucc(OldSU))
 323       // Don't try to remove SU from AvailableQueue.
 324       SU->isAvailable = false;
 325     UnscheduleNodeBottomUp(OldSU);
 326     --CurCycle;
 327   }
 328
 329   assert(!SU->isSucc(OldSU) && "Something is wrong!");
 330
 331   ++NumBacktracks;
 332 }
 333
 334 /// CopyAndMoveSuccessors - Clone the specified node and move its scheduled
 335 /// successors to the newly created node.
 336 SUnit *ScheduleDAGRRList::CopyAndMoveSuccessors(SUnit *SU) {
 337   if (SU->getNode()->getFlaggedNode())
 338     return NULL;
 339
 340   SDNode *N = SU->getNode();
 341   if (!N)
 342     return NULL;
 343
 344   SUnit *NewSU;
 345   bool TryUnfold = false;
 346   for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) {
 347     MVT VT = N->getValueType(i);
 348     if (VT == MVT::Flag)
 349       return NULL;
 350     else if (VT == MVT::Other)
 351       TryUnfold = true;
 352   }
 353   for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
 354     const SDValue &Op = N->getOperand(i);
 355     MVT VT = Op.getNode()->getValueType(Op.getResNo());
 356     if (VT == MVT::Flag)
 357       return NULL;
 358   }
 359
 360   if (TryUnfold) {
 361     SmallVector<SDNode*, 2> NewNodes;
 362     if (!TII->unfoldMemoryOperand(*DAG, N, NewNodes))
 363       return NULL;
 364
 365     DOUT << "Unfolding SU # " << SU->NodeNum << "\n";
 366     assert(NewNodes.size() == 2 && "Expected a load folding node!");
 367
 368     N = NewNodes[1];
 369     SDNode *LoadNode = NewNodes[0];
 370     unsigned NumVals = N->getNumValues();
 371     unsigned OldNumVals = SU->getNode()->getNumValues();
 372     for (unsigned i = 0; i != NumVals; ++i)
 373       DAG->ReplaceAllUsesOfValueWith(SDValue(SU->getNode(), i), SDValue(N, i));
 374     DAG->ReplaceAllUsesOfValueWith(SDValue(SU->getNode(), OldNumVals-1),
 375                                    SDValue(LoadNode, 1));
 376
 377     // LoadNode may already exist. This can happen when there is another
 378     // load from the same location and producing the same type of value
 379     // but it has different alignment or volatileness.
 380     bool isNewLoad = true;
 381     SUnit *LoadSU;
 382     if (LoadNode->getNodeId() != -1) {
 383       LoadSU = &SUnits[LoadNode->getNodeId()];
 384       isNewLoad = false;
 385     } else {
 386       LoadSU = CreateNewSUnit(LoadNode);
 387       LoadNode->setNodeId(LoadSU->NodeNum);
 388       ComputeLatency(LoadSU);
 389     }
 390
 391     SUnit *NewSU = CreateNewSUnit(N);
 392     assert(N->getNodeId() == -1 && "Node already inserted!");
 393     N->setNodeId(NewSU->NodeNum);
 394
 395     const TargetInstrDesc &TID = TII->get(N->getMachineOpcode());
 396     for (unsigned i = 0; i != TID.getNumOperands(); ++i) {
 397       if (TID.getOperandConstraint(i, TOI::TIED_TO) != -1) {
 398         NewSU->isTwoAddress = true;
 399         break;
 400       }
 401     }
 402     if (TID.isCommutable())
 403       NewSU->isCommutable = true;
 404     ComputeLatency(NewSU);
 405
 406     SDep ChainPred;
 407     SmallVector<SDep, 4> ChainSuccs;
 408     SmallVector<SDep, 4> LoadPreds;
 409     SmallVector<SDep, 4> NodePreds;
 410     SmallVector<SDep, 4> NodeSuccs;
 411     for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
 412          I != E; ++I) {
 413       if (I->isCtrl())
 414         ChainPred = *I;
 415       else if (I->getSUnit()->getNode() &&
 416                I->getSUnit()->getNode()->isOperandOf(LoadNode))
 417         LoadPreds.push_back(*I);
 418       else
 419         NodePreds.push_back(*I);
 420     }
 421     for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
 422          I != E; ++I) {
 423       if (I->isCtrl())
 424         ChainSuccs.push_back(*I);
 425       else
 426         NodeSuccs.push_back(*I);
 427     }
 428
 429     if (ChainPred.getSUnit()) {
 430       RemovePred(SU, ChainPred);
 431       if (isNewLoad)
 432         AddPred(LoadSU, ChainPred);
 433     }
 434     for (unsigned i = 0, e = LoadPreds.size(); i != e; ++i) {
 435       const SDep &Pred = LoadPreds[i];
 436       RemovePred(SU, Pred);
 437       if (isNewLoad) {
 438         AddPred(LoadSU, Pred);
 439       }
 440     }
 441     for (unsigned i = 0, e = NodePreds.size(); i != e; ++i) {
 442       const SDep &Pred = NodePreds[i];
 443       RemovePred(SU, Pred);
 444       AddPred(NewSU, Pred);
 445     }
 446     for (unsigned i = 0, e = NodeSuccs.size(); i != e; ++i) {
 447       SDep D = NodeSuccs[i];
 448       SUnit *SuccDep = D.getSUnit();
 449       D.setSUnit(SU);
 450       RemovePred(SuccDep, D);
 451       D.setSUnit(NewSU);
 452       AddPred(SuccDep, D);
 453     }
 454     for (unsigned i = 0, e = ChainSuccs.size(); i != e; ++i) {
 455       SDep D = ChainSuccs[i];
 456       SUnit *SuccDep = D.getSUnit();
 457       D.setSUnit(SU);
 458       RemovePred(SuccDep, D);
 459       if (isNewLoad) {
 460         D.setSUnit(LoadSU);
 461         AddPred(SuccDep, D);
 462       }
 463     }
 464     if (isNewLoad) {
 465       AddPred(NewSU, SDep(LoadSU, SDep::Order, LoadSU->Latency));
 466     }
 467
 468     if (isNewLoad)
 469       AvailableQueue->addNode(LoadSU);
 470     AvailableQueue->addNode(NewSU);
 471
 472     ++NumUnfolds;
 473
 474     if (NewSU->NumSuccsLeft == 0) {
 475       NewSU->isAvailable = true;
 476       return NewSU;
 477     }
 478     SU = NewSU;
 479   }
 480
 481   DOUT << "Duplicating SU # " << SU->NodeNum << "\n";
 482   NewSU = CreateClone(SU);
 483
 484   // New SUnit has the exact same predecessors.
 485   for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
 486        I != E; ++I)
 487     if (!I->isArtificial())
 488       AddPred(NewSU, *I);
 489
 490   // Only copy scheduled successors. Cut them from old node's successor
 491   // list and move them over.
 492   SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps;
 493   for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
 494        I != E; ++I) {
 495     if (I->isArtificial())
 496       continue;
 497     SUnit *SuccSU = I->getSUnit();
 498     if (SuccSU->isScheduled) {
 499       SDep D = *I;
 500       D.setSUnit(NewSU);
 501       AddPred(SuccSU, D);
 502       D.setSUnit(SU);
 503       DelDeps.push_back(std::make_pair(SuccSU, D));
 504     }
 505   }
 506   for (unsigned i = 0, e = DelDeps.size(); i != e; ++i)
 507     RemovePred(DelDeps[i].first, DelDeps[i].second);
 508
 509   AvailableQueue->updateNode(SU);
 510   AvailableQueue->addNode(NewSU);
 511
 512   ++NumDups;
 513   return NewSU;
 514 }
 515
 516 /// InsertCopiesAndMoveSuccs - Insert register copies and move all
 517 /// scheduled successors of the given SUnit to the last copy.
 518 void ScheduleDAGRRList::InsertCopiesAndMoveSuccs(SUnit *SU, unsigned Reg,
 519                                                const TargetRegisterClass *DestRC,
 520                                                const TargetRegisterClass *SrcRC,
 521                                                SmallVector<SUnit*, 2> &Copies) {
 522   SUnit *CopyFromSU = CreateNewSUnit(NULL);
 523   CopyFromSU->CopySrcRC = SrcRC;
 524   CopyFromSU->CopyDstRC = DestRC;
 525
 526   SUnit *CopyToSU = CreateNewSUnit(NULL);
 527   CopyToSU->CopySrcRC = DestRC;
 528   CopyToSU->CopyDstRC = SrcRC;
 529
 530   // Only copy scheduled successors. Cut them from old node's successor
 531   // list and move them over.
 532   SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps;
 533   for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
 534        I != E; ++I) {
 535     if (I->isArtificial())
 536       continue;
 537     SUnit *SuccSU = I->getSUnit();
 538     if (SuccSU->isScheduled) {
 539       SDep D = *I;
 540       D.setSUnit(CopyToSU);
 541       AddPred(SuccSU, D);
 542       DelDeps.push_back(std::make_pair(SuccSU, *I));
 543     }
 544   }
 545   for (unsigned i = 0, e = DelDeps.size(); i != e; ++i)
 546     RemovePred(DelDeps[i].first, DelDeps[i].second);
 547
 548   AddPred(CopyFromSU, SDep(SU, SDep::Data, SU->Latency, Reg));
 549   AddPred(CopyToSU, SDep(CopyFromSU, SDep::Data, CopyFromSU->Latency, 0));
 550
 551   AvailableQueue->updateNode(SU);
 552   AvailableQueue->addNode(CopyFromSU);
 553   AvailableQueue->addNode(CopyToSU);
 554   Copies.push_back(CopyFromSU);
 555   Copies.push_back(CopyToSU);
 556
 557   ++NumPRCopies;
 558 }
 559
 560 /// getPhysicalRegisterVT - Returns the ValueType of the physical register
 561 /// definition of the specified node.
 562 /// FIXME: Move to SelectionDAG?
 563 static MVT getPhysicalRegisterVT(SDNode *N, unsigned Reg,
 564                                  const TargetInstrInfo *TII) {
 565   const TargetInstrDesc &TID = TII->get(N->getMachineOpcode());
 566   assert(TID.ImplicitDefs && "Physical reg def must be in implicit def list!");
 567   unsigned NumRes = TID.getNumDefs();
 568   for (const unsigned *ImpDef = TID.getImplicitDefs(); *ImpDef; ++ImpDef) {
 569     if (Reg == *ImpDef)
 570       break;
 571     ++NumRes;
 572   }
 573   return N->getValueType(NumRes);
 574 }
 575
 576 /// DelayForLiveRegsBottomUp - Returns true if it is necessary to delay
 577 /// scheduling of the given node to satisfy live physical register dependencies.
 578 /// If the specific node is the last one that's available to schedule, do
 579 /// whatever is necessary (i.e. backtracking or cloning) to make it possible.
 580 bool ScheduleDAGRRList::DelayForLiveRegsBottomUp(SUnit *SU,
 581                                                  SmallVector<unsigned, 4> &LRegs){
 582   if (NumLiveRegs == 0)
 583     return false;
 584
 585   SmallSet<unsigned, 4> RegAdded;
 586   // If this node would clobber any "live" register, then it's not ready.
 587   for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
 588        I != E; ++I) {
 589     if (I->isAssignedRegDep()) {
 590       unsigned Reg = I->getReg();
 591       if (LiveRegDefs[Reg] && LiveRegDefs[Reg] != I->getSUnit()) {
 592         if (RegAdded.insert(Reg))
 593           LRegs.push_back(Reg);
 594       }
 595       for (const unsigned *Alias = TRI->getAliasSet(Reg);
 596            *Alias; ++Alias)
 597         if (LiveRegDefs[*Alias] && LiveRegDefs[*Alias] != I->getSUnit()) {
 598           if (RegAdded.insert(*Alias))
 599             LRegs.push_back(*Alias);
 600         }
 601     }
 602   }
 603
 604   for (SDNode *Node = SU->getNode(); Node; Node = Node->getFlaggedNode()) {
 605     if (!Node->isMachineOpcode())
 606       continue;
 607     const TargetInstrDesc &TID = TII->get(Node->getMachineOpcode());
 608     if (!TID.ImplicitDefs)
 609       continue;
 610     for (const unsigned *Reg = TID.ImplicitDefs; *Reg; ++Reg) {
 611       if (LiveRegDefs[*Reg] && LiveRegDefs[*Reg] != SU) {
 612         if (RegAdded.insert(*Reg))
 613           LRegs.push_back(*Reg);
 614       }
 615       for (const unsigned *Alias = TRI->getAliasSet(*Reg);
 616            *Alias; ++Alias)
 617         if (LiveRegDefs[*Alias] && LiveRegDefs[*Alias] != SU) {
 618           if (RegAdded.insert(*Alias))
 619             LRegs.push_back(*Alias);
 620         }
 621     }
 622   }
 623   return !LRegs.empty();
 624 }
 625
 626
 627 /// ListScheduleBottomUp - The main loop of list scheduling for bottom-up
 628 /// schedulers.
 629 void ScheduleDAGRRList::ListScheduleBottomUp() {
 630   unsigned CurCycle = 0;
 631   // Add root to Available queue.
 632   if (!SUnits.empty()) {
 633     SUnit *RootSU = &SUnits[DAG->getRoot().getNode()->getNodeId()];
 634     assert(RootSU->Succs.empty() && "Graph root shouldn't have successors!");
 635     RootSU->isAvailable = true;
 636     AvailableQueue->push(RootSU);
 637   }
 638
 639   // While Available queue is not empty, grab the node with the highest
 640   // priority. If it is not ready put it back.  Schedule the node.
 641   SmallVector<SUnit*, 4> NotReady;
 642   DenseMap<SUnit*, SmallVector<unsigned, 4> > LRegsMap;
 643   Sequence.reserve(SUnits.size());
 644   while (!AvailableQueue->empty()) {
 645     bool Delayed = false;
 646     LRegsMap.clear();
 647     SUnit *CurSU = AvailableQueue->pop();
 648     while (CurSU) {
 649       SmallVector<unsigned, 4> LRegs;
 650       if (!DelayForLiveRegsBottomUp(CurSU, LRegs))
 651         break;
 652       Delayed = true;
 653       LRegsMap.insert(std::make_pair(CurSU, LRegs));
 654
 655       CurSU->isPending = true;  // This SU is not in AvailableQueue right now.
 656       NotReady.push_back(CurSU);
 657       CurSU = AvailableQueue->pop();
 658     }
 659
 660     // All candidates are delayed due to live physical reg dependencies.
 661     // Try backtracking, code duplication, or inserting cross class copies
 662     // to resolve it.
 663     if (Delayed && !CurSU) {
 664       for (unsigned i = 0, e = NotReady.size(); i != e; ++i) {
 665         SUnit *TrySU = NotReady[i];
 666         SmallVector<unsigned, 4> &LRegs = LRegsMap[TrySU];
 667
 668         // Try unscheduling up to the point where it's safe to schedule
 669         // this node.
 670         unsigned LiveCycle = CurCycle;
 671         for (unsigned j = 0, ee = LRegs.size(); j != ee; ++j) {
 672           unsigned Reg = LRegs[j];
 673           unsigned LCycle = LiveRegCycles[Reg];
 674           LiveCycle = std::min(LiveCycle, LCycle);
 675         }
 676         SUnit *OldSU = Sequence[LiveCycle];
 677         if (!WillCreateCycle(TrySU, OldSU))  {
 678           BacktrackBottomUp(TrySU, LiveCycle, CurCycle);
 679           // Force the current node to be scheduled before the node that
 680           // requires the physical reg dep.
 681           if (OldSU->isAvailable) {
 682             OldSU->isAvailable = false;
 683             AvailableQueue->remove(OldSU);
 684           }
 685           AddPred(TrySU, SDep(OldSU, SDep::Order, /*Latency=*/1,
 686                               /*Reg=*/0, /*isNormalMemory=*/false,
 687                               /*isMustAlias=*/false, /*isArtificial=*/true));
 688           // If one or more successors has been unscheduled, then the current
 689           // node is no longer avaialable. Schedule a successor that's now
 690           // available instead.
 691           if (!TrySU->isAvailable)
 692             CurSU = AvailableQueue->pop();
 693           else {
 694             CurSU = TrySU;
 695             TrySU->isPending = false;
 696             NotReady.erase(NotReady.begin()+i);
 697           }
 698           break;
 699         }
 700       }
 701
 702       if (!CurSU) {
 703         // Can't backtrack. If it's too expensive to copy the value, then try
 704         // duplicate the nodes that produces these "too expensive to copy"
 705         // values to break the dependency. In case even that doesn't work,
 706         // insert cross class copies.
 707         // If it's not too expensive, i.e. cost != -1, issue copies.
 708         SUnit *TrySU = NotReady[0];
 709         SmallVector<unsigned, 4> &LRegs = LRegsMap[TrySU];
 710         assert(LRegs.size() == 1 && "Can't handle this yet!");
 711         unsigned Reg = LRegs[0];
 712         SUnit *LRDef = LiveRegDefs[Reg];
 713         MVT VT = getPhysicalRegisterVT(LRDef->getNode(), Reg, TII);
 714         const TargetRegisterClass *RC =
 715           TRI->getPhysicalRegisterRegClass(Reg, VT);
 716         const TargetRegisterClass *DestRC = TRI->getCrossCopyRegClass(RC);
 717
 718         // If cross copy register class is null, then it must be possible copy
 719         // the value directly. Do not try duplicate the def.
 720         SUnit *NewDef = 0;
 721         if (DestRC)
 722           NewDef = CopyAndMoveSuccessors(LRDef);
 723         else
 724           DestRC = RC;
 725         if (!NewDef) {
 726           // Issue copies, these can be expensive cross register class copies.
 727           SmallVector<SUnit*, 2> Copies;
 728           InsertCopiesAndMoveSuccs(LRDef, Reg, DestRC, RC, Copies);
 729           DOUT << "Adding an edge from SU #" << TrySU->NodeNum
 730                << " to SU #" << Copies.front()->NodeNum << "\n";
 731           AddPred(TrySU, SDep(Copies.front(), SDep::Order, /*Latency=*/1,
 732                               /*Reg=*/0, /*isNormalMemory=*/false,
 733                               /*isMustAlias=*/false,
 734                               /*isArtificial=*/true));
 735           NewDef = Copies.back();
 736         }
 737
 738         DOUT << "Adding an edge from SU #" << NewDef->NodeNum
 739              << " to SU #" << TrySU->NodeNum << "\n";
 740         LiveRegDefs[Reg] = NewDef;
 741         AddPred(NewDef, SDep(TrySU, SDep::Order, /*Latency=*/1,
 742                              /*Reg=*/0, /*isNormalMemory=*/false,
 743                              /*isMustAlias=*/false,
 744                              /*isArtificial=*/true));
 745         TrySU->isAvailable = false;
 746         CurSU = NewDef;
 747       }
 748
 749       assert(CurSU && "Unable to resolve live physical register dependencies!");
 750     }
 751
 752     // Add the nodes that aren't ready back onto the available list.
 753     for (unsigned i = 0, e = NotReady.size(); i != e; ++i) {
 754       NotReady[i]->isPending = false;
 755       // May no longer be available due to backtracking.
 756       if (NotReady[i]->isAvailable)
 757         AvailableQueue->push(NotReady[i]);
 758     }
 759     NotReady.clear();
 760
 761     if (CurSU)
 762       ScheduleNodeBottomUp(CurSU, CurCycle);
 763     ++CurCycle;
 764   }
 765
 766   // Reverse the order if it is bottom up.
 767   std::reverse(Sequence.begin(), Sequence.end());
 768
 769 #ifndef NDEBUG
 770   VerifySchedule(isBottomUp);
 771 #endif
 772 }
 773
 774 //===----------------------------------------------------------------------===//
 775 //  Top-Down Scheduling
 776 //===----------------------------------------------------------------------===//
 777
 778 /// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to
 779 /// the AvailableQueue if the count reaches zero. Also update its cycle bound.
 780 void ScheduleDAGRRList::ReleaseSucc(SUnit *SU, const SDep *SuccEdge) {
 781   SUnit *SuccSU = SuccEdge->getSUnit();
 782   --SuccSU->NumPredsLeft;
 783
 784 #ifndef NDEBUG
 785   if (SuccSU->NumPredsLeft < 0) {
 786     cerr << "*** Scheduling failed! ***\n";
 787     SuccSU->dump(this);
 788     cerr << " has been released too many times!\n";
 789     assert(0);
 790   }
 791 #endif
 792
 793   if (SuccSU->NumPredsLeft == 0) {
 794     SuccSU->isAvailable = true;
 795     AvailableQueue->push(SuccSU);
 796   }
 797 }
 798
 799 /// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending
 800 /// count of its successors. If a successor pending count is zero, add it to
 801 /// the Available queue.
 802 void ScheduleDAGRRList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) {
 803   DOUT << "*** Scheduling [" << CurCycle << "]: ";
 804   DEBUG(SU->dump(this));
 805
 806   assert(CurCycle >= SU->getDepth() && "Node scheduled above its depth!");
 807   SU->setDepthToAtLeast(CurCycle);
 808   Sequence.push_back(SU);
 809
 810   // Top down: release successors
 811   for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
 812        I != E; ++I) {
 813     assert(!I->isAssignedRegDep() &&
 814            "The list-tdrr scheduler doesn't yet support physreg dependencies!");
 815
 816     ReleaseSucc(SU, &*I);
 817   }
 818
 819   SU->isScheduled = true;
 820   AvailableQueue->ScheduledNode(SU);
 821 }
 822
 823 /// ListScheduleTopDown - The main loop of list scheduling for top-down
 824 /// schedulers.
 825 void ScheduleDAGRRList::ListScheduleTopDown() {
 826   unsigned CurCycle = 0;
 827
 828   // All leaves to Available queue.
 829   for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
 830     // It is available if it has no predecessors.
 831     if (SUnits[i].Preds.empty()) {
 832       AvailableQueue->push(&SUnits[i]);
 833       SUnits[i].isAvailable = true;
 834     }
 835   }
 836
 837   // While Available queue is not empty, grab the node with the highest
 838   // priority. If it is not ready put it back.  Schedule the node.
 839   Sequence.reserve(SUnits.size());
 840   while (!AvailableQueue->empty()) {
 841     SUnit *CurSU = AvailableQueue->pop();
 842
 843     if (CurSU)
 844       ScheduleNodeTopDown(CurSU, CurCycle);
 845     ++CurCycle;
 846   }
 847
 848 #ifndef NDEBUG
 849   VerifySchedule(isBottomUp);
 850 #endif
 851 }
 852
 853
 854 //===----------------------------------------------------------------------===//
 855 //                RegReductionPriorityQueue Implementation
 856 //===----------------------------------------------------------------------===//
 857 //
 858 // This is a SchedulingPriorityQueue that schedules using Sethi Ullman numbers
 859 // to reduce register pressure.
 860 //
 861 namespace {
 862   template<class SF>
 863   class RegReductionPriorityQueue;
 864
 865   /// Sorting functions for the Available queue.
 866   struct bu_ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> {
 867     RegReductionPriorityQueue<bu_ls_rr_sort> *SPQ;
 868     bu_ls_rr_sort(RegReductionPriorityQueue<bu_ls_rr_sort> *spq) : SPQ(spq) {}
 869     bu_ls_rr_sort(const bu_ls_rr_sort &RHS) : SPQ(RHS.SPQ) {}
 870
 871     bool operator()(const SUnit* left, const SUnit* right) const;
 872   };
 873
 874   struct td_ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> {
 875     RegReductionPriorityQueue<td_ls_rr_sort> *SPQ;
 876     td_ls_rr_sort(RegReductionPriorityQueue<td_ls_rr_sort> *spq) : SPQ(spq) {}
 877     td_ls_rr_sort(const td_ls_rr_sort &RHS) : SPQ(RHS.SPQ) {}
 878
 879     bool operator()(const SUnit* left, const SUnit* right) const;
 880   };
 881 }  // end anonymous namespace
 882
 883 static inline bool isCopyFromLiveIn(const SUnit *SU) {
 884   SDNode *N = SU->getNode();
 885   return N && N->getOpcode() == ISD::CopyFromReg &&
 886     N->getOperand(N->getNumOperands()-1).getValueType() != MVT::Flag;
 887 }
 888
 889 /// CalcNodeSethiUllmanNumber - Compute Sethi Ullman number.
 890 /// Smaller number is the higher priority.
 891 static unsigned
 892 CalcNodeSethiUllmanNumber(const SUnit *SU, std::vector<unsigned> &SUNumbers) {
 893   unsigned &SethiUllmanNumber = SUNumbers[SU->NodeNum];
 894   if (SethiUllmanNumber != 0)
 895     return SethiUllmanNumber;
 896
 897   unsigned Extra = 0;
 898   for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
 899        I != E; ++I) {
 900     if (I->isCtrl()) continue;  // ignore chain preds
 901     SUnit *PredSU = I->getSUnit();
 902     unsigned PredSethiUllman = CalcNodeSethiUllmanNumber(PredSU, SUNumbers);
 903     if (PredSethiUllman > SethiUllmanNumber) {
 904       SethiUllmanNumber = PredSethiUllman;
 905       Extra = 0;
 906     } else if (PredSethiUllman == SethiUllmanNumber && !I->isCtrl())
 907       ++Extra;
 908   }
 909
 910   SethiUllmanNumber += Extra;
 911
 912   if (SethiUllmanNumber == 0)
 913     SethiUllmanNumber = 1;
 914
 915   return SethiUllmanNumber;
 916 }
 917
 918 namespace {
 919   template<class SF>
 920   class VISIBILITY_HIDDEN RegReductionPriorityQueue
 921    : public SchedulingPriorityQueue {
 922     PriorityQueue<SUnit*, std::vector<SUnit*>, SF> Queue;
 923     unsigned currentQueueId;
 924
 925   protected:
 926     // SUnits - The SUnits for the current graph.
 927     std::vector<SUnit> *SUnits;
 928
 929     const TargetInstrInfo *TII;
 930     const TargetRegisterInfo *TRI;
 931     ScheduleDAGRRList *scheduleDAG;
 932
 933     // SethiUllmanNumbers - The SethiUllman number for each node.
 934     std::vector<unsigned> SethiUllmanNumbers;
 935
 936   public:
 937     RegReductionPriorityQueue(const TargetInstrInfo *tii,
 938                               const TargetRegisterInfo *tri) :
 939     Queue(SF(this)), currentQueueId(0),
 940     TII(tii), TRI(tri), scheduleDAG(NULL) {}
 941
 942     void initNodes(std::vector<SUnit> &sunits) {
 943       SUnits = &sunits;
 944       // Add pseudo dependency edges for two-address nodes.
 945       AddPseudoTwoAddrDeps();
 946       // Calculate node priorities.
 947       CalculateSethiUllmanNumbers();
 948     }
 949
 950     void addNode(const SUnit *SU) {
 951       unsigned SUSize = SethiUllmanNumbers.size();
 952       if (SUnits->size() > SUSize)
 953         SethiUllmanNumbers.resize(SUSize*2, 0);
 954       CalcNodeSethiUllmanNumber(SU, SethiUllmanNumbers);
 955     }
 956
 957     void updateNode(const SUnit *SU) {
 958       SethiUllmanNumbers[SU->NodeNum] = 0;
 959       CalcNodeSethiUllmanNumber(SU, SethiUllmanNumbers);
 960     }
 961
 962     void releaseState() {
 963       SUnits = 0;
 964       SethiUllmanNumbers.clear();
 965     }
 966
 967     unsigned getNodePriority(const SUnit *SU) const {
 968       assert(SU->NodeNum < SethiUllmanNumbers.size());
 969       unsigned Opc = SU->getNode() ? SU->getNode()->getOpcode() : 0;
 970       if (Opc == ISD::CopyFromReg && !isCopyFromLiveIn(SU))
 971         // CopyFromReg should be close to its def because it restricts
 972         // allocation choices. But if it is a livein then perhaps we want it
 973         // closer to its uses so it can be coalesced.
 974         return 0xffff;
 975       if (Opc == ISD::TokenFactor || Opc == ISD::CopyToReg)
 976         // CopyToReg should be close to its uses to facilitate coalescing and
 977         // avoid spilling.
 978         return 0;
 979       if (Opc == TargetInstrInfo::EXTRACT_SUBREG ||
 980           Opc == TargetInstrInfo::INSERT_SUBREG)
 981         // EXTRACT_SUBREG / INSERT_SUBREG should be close to its use to
 982         // facilitate coalescing.
 983         return 0;
 984       if (SU->NumSuccs == 0)
 985         // If SU does not have a use, i.e. it doesn't produce a value that would
 986         // be consumed (e.g. store), then it terminates a chain of computation.
 987         // Give it a large SethiUllman number so it will be scheduled right
 988         // before its predecessors that it doesn't lengthen their live ranges.
 989         return 0xffff;
 990       if (SU->NumPreds == 0)
 991         // If SU does not have a def, schedule it close to its uses because it
 992         // does not lengthen any live ranges.
 993         return 0;
 994       return SethiUllmanNumbers[SU->NodeNum];
 995     }
 996
 997     unsigned size() const { return Queue.size(); }
 998
 999     bool empty() const { return Queue.empty(); }
1000
1001     void push(SUnit *U) {
1002       assert(!U->NodeQueueId && "Node in the queue already");
1003       U->NodeQueueId = ++currentQueueId;
1004       Queue.push(U);
1005     }
1006
1007     void push_all(const std::vector<SUnit *> &Nodes) {
1008       for (unsigned i = 0, e = Nodes.size(); i != e; ++i)
1009         push(Nodes[i]);
1010     }
1011
1012     SUnit *pop() {
1013       if (empty()) return NULL;
1014       SUnit *V = Queue.top();
1015       Queue.pop();
1016       V->NodeQueueId = 0;
1017       return V;
1018     }
1019
1020     void remove(SUnit *SU) {
1021       assert(!Queue.empty() && "Queue is empty!");
1022       assert(SU->NodeQueueId != 0 && "Not in queue!");
1023       Queue.erase_one(SU);
1024       SU->NodeQueueId = 0;
1025     }
1026
1027     void setScheduleDAG(ScheduleDAGRRList *scheduleDag) {
1028       scheduleDAG = scheduleDag;
1029     }
1030
1031   protected:
1032     bool canClobber(const SUnit *SU, const SUnit *Op);
1033     void AddPseudoTwoAddrDeps();
1034     void CalculateSethiUllmanNumbers();
1035   };
1036
1037   typedef RegReductionPriorityQueue<bu_ls_rr_sort>
1038     BURegReductionPriorityQueue;
1039
1040   typedef RegReductionPriorityQueue<td_ls_rr_sort>
1041     TDRegReductionPriorityQueue;
1042 }
1043
1044 /// closestSucc - Returns the scheduled cycle of the successor which is
1045 /// closet to the current cycle.
1046 static unsigned closestSucc(const SUnit *SU) {
1047   unsigned MaxHeight = 0;
1048   for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
1049        I != E; ++I) {
1050     unsigned Height = I->getSUnit()->getHeight();
1051     // If there are bunch of CopyToRegs stacked up, they should be considered
1052     // to be at the same position.
1053     if (I->getSUnit()->getNode() &&
1054         I->getSUnit()->getNode()->getOpcode() == ISD::CopyToReg)
1055       Height = closestSucc(I->getSUnit())+1;
1056     if (Height > MaxHeight)
1057       MaxHeight = Height;
1058   }
1059   return MaxHeight;
1060 }
1061
1062 /// calcMaxScratches - Returns an cost estimate of the worse case requirement
1063 /// for scratch registers. Live-in operands and live-out results don't count
1064 /// since they are "fixed".
1065 static unsigned calcMaxScratches(const SUnit *SU) {
1066   unsigned Scratches = 0;
1067   for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
1068        I != E; ++I) {
1069     if (I->isCtrl()) continue;  // ignore chain preds
1070     if (!I->getSUnit()->getNode() ||
1071         I->getSUnit()->getNode()->getOpcode() != ISD::CopyFromReg)
1072       Scratches++;
1073   }
1074   for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
1075        I != E; ++I) {
1076     if (I->isCtrl()) continue;  // ignore chain succs
1077     if (!I->getSUnit()->getNode() ||
1078         I->getSUnit()->getNode()->getOpcode() != ISD::CopyToReg)
1079       Scratches += 10;
1080   }
1081   return Scratches;
1082 }
1083
1084 // Bottom up
1085 bool bu_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const {
1086   unsigned LPriority = SPQ->getNodePriority(left);
1087   unsigned RPriority = SPQ->getNodePriority(right);
1088   if (LPriority != RPriority)
1089     return LPriority > RPriority;
1090
1091   // Try schedule def + use closer when Sethi-Ullman numbers are the same.
1092   // e.g.
1093   // t1 = op t2, c1
1094   // t3 = op t4, c2
1095   //
1096   // and the following instructions are both ready.
1097   // t2 = op c3
1098   // t4 = op c4
1099   //
1100   // Then schedule t2 = op first.
1101   // i.e.
1102   // t4 = op c4
1103   // t2 = op c3
1104   // t1 = op t2, c1
1105   // t3 = op t4, c2
1106   //
1107   // This creates more short live intervals.
1108   unsigned LDist = closestSucc(left);
1109   unsigned RDist = closestSucc(right);
1110   if (LDist != RDist)
1111     return LDist < RDist;
1112
1113   // Intuitively, it's good to push down instructions whose results are
1114   // liveout so their long live ranges won't conflict with other values
1115   // which are needed inside the BB. Further prioritize liveout instructions
1116   // by the number of operands which are calculated within the BB.
1117   unsigned LScratch = calcMaxScratches(left);
1118   unsigned RScratch = calcMaxScratches(right);
1119   if (LScratch != RScratch)
1120     return LScratch > RScratch;
1121
1122   if (left->getHeight() != right->getHeight())
1123     return left->getHeight() > right->getHeight();
1124
1125   if (left->getDepth() != right->getDepth())
1126     return left->getDepth() < right->getDepth();
1127
1128   assert(left->NodeQueueId && right->NodeQueueId &&
1129          "NodeQueueId cannot be zero");
1130   return (left->NodeQueueId > right->NodeQueueId);
1131 }
1132
1133 template<class SF>
1134 bool
1135 RegReductionPriorityQueue<SF>::canClobber(const SUnit *SU, const SUnit *Op) {
1136   if (SU->isTwoAddress) {
1137     unsigned Opc = SU->getNode()->getMachineOpcode();
1138     const TargetInstrDesc &TID = TII->get(Opc);
1139     unsigned NumRes = TID.getNumDefs();
1140     unsigned NumOps = TID.getNumOperands() - NumRes;
1141     for (unsigned i = 0; i != NumOps; ++i) {
1142       if (TID.getOperandConstraint(i+NumRes, TOI::TIED_TO) != -1) {
1143         SDNode *DU = SU->getNode()->getOperand(i).getNode();
1144         if (DU->getNodeId() != -1 &&
1145             Op->OrigNode == &(*SUnits)[DU->getNodeId()])
1146           return true;
1147       }
1148     }
1149   }
1150   return false;
1151 }
1152
1153
1154 /// hasCopyToRegUse - Return true if SU has a value successor that is a
1155 /// CopyToReg node.
1156 static bool hasCopyToRegUse(const SUnit *SU) {
1157   for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
1158        I != E; ++I) {
1159     if (I->isCtrl()) continue;
1160     const SUnit *SuccSU = I->getSUnit();
1161     if (SuccSU->getNode() && SuccSU->getNode()->getOpcode() == ISD::CopyToReg)
1162       return true;
1163   }
1164   return false;
1165 }
1166
1167 /// canClobberPhysRegDefs - True if SU would clobber one of SuccSU's
1168 /// physical register defs.
1169 static bool canClobberPhysRegDefs(const SUnit *SuccSU, const SUnit *SU,
1170                                   const TargetInstrInfo *TII,
1171                                   const TargetRegisterInfo *TRI) {
1172   SDNode *N = SuccSU->getNode();
1173   unsigned NumDefs = TII->get(N->getMachineOpcode()).getNumDefs();
1174   const unsigned *ImpDefs = TII->get(N->getMachineOpcode()).getImplicitDefs();
1175   assert(ImpDefs && "Caller should check hasPhysRegDefs");
1176   const unsigned *SUImpDefs =
1177     TII->get(SU->getNode()->getMachineOpcode()).getImplicitDefs();
1178   if (!SUImpDefs)
1179     return false;
1180   for (unsigned i = NumDefs, e = N->getNumValues(); i != e; ++i) {
1181     MVT VT = N->getValueType(i);
1182     if (VT == MVT::Flag || VT == MVT::Other)
1183       continue;
1184     if (!N->hasAnyUseOfValue(i))
1185       continue;
1186     unsigned Reg = ImpDefs[i - NumDefs];
1187     for (;*SUImpDefs; ++SUImpDefs) {
1188       unsigned SUReg = *SUImpDefs;
1189       if (TRI->regsOverlap(Reg, SUReg))
1190         return true;
1191     }
1192   }
1193   return false;
1194 }
1195
1196 /// AddPseudoTwoAddrDeps - If two nodes share an operand and one of them uses
1197 /// it as a def&use operand. Add a pseudo control edge from it to the other
1198 /// node (if it won't create a cycle) so the two-address one will be scheduled
1199 /// first (lower in the schedule). If both nodes are two-address, favor the
1200 /// one that has a CopyToReg use (more likely to be a loop induction update).
1201 /// If both are two-address, but one is commutable while the other is not
1202 /// commutable, favor the one that's not commutable.
1203 template<class SF>
1204 void RegReductionPriorityQueue<SF>::AddPseudoTwoAddrDeps() {
1205   for (unsigned i = 0, e = SUnits->size(); i != e; ++i) {
1206     SUnit *SU = &(*SUnits)[i];
1207     if (!SU->isTwoAddress)
1208       continue;
1209
1210     SDNode *Node = SU->getNode();
1211     if (!Node || !Node->isMachineOpcode() || SU->getNode()->getFlaggedNode())
1212       continue;
1213
1214     unsigned Opc = Node->getMachineOpcode();
1215     const TargetInstrDesc &TID = TII->get(Opc);
1216     unsigned NumRes = TID.getNumDefs();
1217     unsigned NumOps = TID.getNumOperands() - NumRes;
1218     for (unsigned j = 0; j != NumOps; ++j) {
1219       if (TID.getOperandConstraint(j+NumRes, TOI::TIED_TO) == -1)
1220         continue;
1221       SDNode *DU = SU->getNode()->getOperand(j).getNode();
1222       if (DU->getNodeId() == -1)
1223         continue;
1224       const SUnit *DUSU = &(*SUnits)[DU->getNodeId()];
1225       if (!DUSU) continue;
1226       for (SUnit::const_succ_iterator I = DUSU->Succs.begin(),
1227            E = DUSU->Succs.end(); I != E; ++I) {
1228         if (I->isCtrl()) continue;
1229         SUnit *SuccSU = I->getSUnit();
1230         if (SuccSU == SU)
1231           continue;
1232         // Be conservative. Ignore if nodes aren't at roughly the same
1233         // depth and height.
1234         if (SuccSU->getHeight() < SU->getHeight() &&
1235             (SU->getHeight() - SuccSU->getHeight()) > 1)
1236           continue;
1237         if (!SuccSU->getNode() || !SuccSU->getNode()->isMachineOpcode())
1238           continue;
1239         // Don't constrain nodes with physical register defs if the
1240         // predecessor can clobber them.
1241         if (SuccSU->hasPhysRegDefs) {
1242           if (canClobberPhysRegDefs(SuccSU, SU, TII, TRI))
1243             continue;
1244         }
1245         // Don't constraint extract_subreg / insert_subreg these may be
1246         // coalesced away. We don't them close to their uses.
1247         unsigned SuccOpc = SuccSU->getNode()->getMachineOpcode();
1248         if (SuccOpc == TargetInstrInfo::EXTRACT_SUBREG ||
1249             SuccOpc == TargetInstrInfo::INSERT_SUBREG)
1250           continue;
1251         if ((!canClobber(SuccSU, DUSU) ||
1252              (hasCopyToRegUse(SU) && !hasCopyToRegUse(SuccSU)) ||
1253              (!SU->isCommutable && SuccSU->isCommutable)) &&
1254             !scheduleDAG->IsReachable(SuccSU, SU)) {
1255           DOUT << "Adding a pseudo-two-addr edge from SU # " << SU->NodeNum
1256                << " to SU #" << SuccSU->NodeNum << "\n";
1257           scheduleDAG->AddPred(SU, SDep(SuccSU, SDep::Order, /*Latency=*/0,
1258                                         /*Reg=*/0, /*isNormalMemory=*/false,
1259                                         /*isMustAlias=*/false,
1260                                         /*isArtificial=*/true));
1261         }
1262       }
1263     }
1264   }
1265 }
1266
1267 /// CalculateSethiUllmanNumbers - Calculate Sethi-Ullman numbers of all
1268 /// scheduling units.
1269 template<class SF>
1270 void RegReductionPriorityQueue<SF>::CalculateSethiUllmanNumbers() {
1271   SethiUllmanNumbers.assign(SUnits->size(), 0);
1272
1273   for (unsigned i = 0, e = SUnits->size(); i != e; ++i)
1274     CalcNodeSethiUllmanNumber(&(*SUnits)[i], SethiUllmanNumbers);
1275 }
1276
1277 /// LimitedSumOfUnscheduledPredsOfSuccs - Compute the sum of the unscheduled
1278 /// predecessors of the successors of the SUnit SU. Stop when the provided
1279 /// limit is exceeded.
1280 static unsigned LimitedSumOfUnscheduledPredsOfSuccs(const SUnit *SU,
1281                                                     unsigned Limit) {
1282   unsigned Sum = 0;
1283   for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
1284        I != E; ++I) {
1285     const SUnit *SuccSU = I->getSUnit();
1286     for (SUnit::const_pred_iterator II = SuccSU->Preds.begin(),
1287          EE = SuccSU->Preds.end(); II != EE; ++II) {
1288       SUnit *PredSU = II->getSUnit();
1289       if (!PredSU->isScheduled)
1290         if (++Sum > Limit)
1291           return Sum;
1292     }
1293   }
1294   return Sum;
1295 }
1296
1297
1298 // Top down
1299 bool td_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const {
1300   unsigned LPriority = SPQ->getNodePriority(left);
1301   unsigned RPriority = SPQ->getNodePriority(right);
1302   bool LIsTarget = left->getNode() && left->getNode()->isMachineOpcode();
1303   bool RIsTarget = right->getNode() && right->getNode()->isMachineOpcode();
1304   bool LIsFloater = LIsTarget && left->NumPreds == 0;
1305   bool RIsFloater = RIsTarget && right->NumPreds == 0;
1306   unsigned LBonus = (LimitedSumOfUnscheduledPredsOfSuccs(left,1) == 1) ? 2 : 0;
1307   unsigned RBonus = (LimitedSumOfUnscheduledPredsOfSuccs(right,1) == 1) ? 2 : 0;
1308
1309   if (left->NumSuccs == 0 && right->NumSuccs != 0)
1310     return false;
1311   else if (left->NumSuccs != 0 && right->NumSuccs == 0)
1312     return true;
1313
1314   if (LIsFloater)
1315     LBonus -= 2;
1316   if (RIsFloater)
1317     RBonus -= 2;
1318   if (left->NumSuccs == 1)
1319     LBonus += 2;
1320   if (right->NumSuccs == 1)
1321     RBonus += 2;
1322
1323   if (LPriority+LBonus != RPriority+RBonus)
1324     return LPriority+LBonus < RPriority+RBonus;
1325
1326   if (left->getDepth() != right->getDepth())
1327     return left->getDepth() < right->getDepth();
1328
1329   if (left->NumSuccsLeft != right->NumSuccsLeft)
1330     return left->NumSuccsLeft > right->NumSuccsLeft;
1331
1332   assert(left->NodeQueueId && right->NodeQueueId &&
1333          "NodeQueueId cannot be zero");
1334   return (left->NodeQueueId > right->NodeQueueId);
1335 }
1336
1337 //===----------------------------------------------------------------------===//
1338 //                         Public Constructor Functions
1339 //===----------------------------------------------------------------------===//
1340
1341 llvm::ScheduleDAG* llvm::createBURRListDAGScheduler(SelectionDAGISel *IS,
1342                                                     bool) {
1343   const TargetMachine &TM = IS->TM;
1344   const TargetInstrInfo *TII = TM.getInstrInfo();
1345   const TargetRegisterInfo *TRI = TM.getRegisterInfo();
1346
1347   BURegReductionPriorityQueue *PQ = new BURegReductionPriorityQueue(TII, TRI);
1348
1349   ScheduleDAGRRList *SD =
1350     new ScheduleDAGRRList(*IS->MF, true, PQ);
1351   PQ->setScheduleDAG(SD);
1352   return SD;
1353 }
1354
1355 llvm::ScheduleDAG* llvm::createTDRRListDAGScheduler(SelectionDAGISel *IS,
1356                                                     bool) {
1357   const TargetMachine &TM = IS->TM;
1358   const TargetInstrInfo *TII = TM.getInstrInfo();
1359   const TargetRegisterInfo *TRI = TM.getRegisterInfo();
1360
1361   TDRegReductionPriorityQueue *PQ = new TDRegReductionPriorityQueue(TII, TRI);
1362
1363   ScheduleDAGRRList *SD =
1364     new ScheduleDAGRRList(*IS->MF, false, PQ);
1365   PQ->setScheduleDAG(SD);
1366   return SD;
1367 }