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