X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FSelectionDAG%2FScheduleDAGList.cpp;h=067407b1eb84e5f27bf13eb1cb69066df6b20c22;hb=b3bc6352defdf1a5c6b1b0770d0c4d603f6524a8;hp=171ff3efdbce5379635c4e8d4ca98deecfddae3e;hpb=4859e277f773180924241beeb25fb4c37f7fa337;p=oota-llvm.git

diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
index 171ff3efdbc..067407b1eb8 100644
--- a/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
+++ b/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
@@ -2,8 +2,8 @@
 //
 //                     The LLVM Compiler Infrastructure
 //
-// This file was developed by Evan Cheng and is distributed under the
-// University of Illinois Open Source License. See LICENSE.TXT for details.
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
@@ -22,23 +22,22 @@
 #include "llvm/CodeGen/ScheduleDAG.h"
 #include "llvm/CodeGen/SchedulerRegistry.h"
 #include "llvm/CodeGen/SelectionDAGISel.h"
-#include "llvm/CodeGen/SSARegMap.h"
-#include "llvm/Target/MRegisterInfo.h"
+#include "llvm/Target/TargetRegisterInfo.h"
 #include "llvm/Target/TargetData.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Compiler.h"
+#include "llvm/ADT/PriorityQueue.h"
 #include "llvm/ADT/Statistic.h"
 #include <climits>
-#include <queue>
 using namespace llvm;
 
 STATISTIC(NumNoops , "Number of noops inserted");
 STATISTIC(NumStalls, "Number of pipeline stalls");
 
 static RegisterScheduler
-  tdListDAGScheduler("list-td", "  Top-down list scheduler",
+  tdListDAGScheduler("list-td", "Top-down list scheduler",
                      createTDListDAGScheduler);
    
 namespace {
@@ -95,18 +94,11 @@ void ScheduleDAGList::Schedule() {
   // Build scheduling units.
   BuildSchedUnits();
 
-  AvailableQueue->initNodes(SUnitMap, SUnits);
+  AvailableQueue->initNodes(SUnits);
   
   ListScheduleTopDown();
   
   AvailableQueue->releaseState();
-  
-  DOUT << "*** Final schedule ***\n";
-  DEBUG(dumpSchedule());
-  DOUT << "\n";
-  
-  // Emit in scheduled order
-  EmitSchedule();
 }
 
 //===----------------------------------------------------------------------===//
@@ -165,24 +157,20 @@ void ScheduleDAGList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) {
 /// schedulers.
 void ScheduleDAGList::ListScheduleTopDown() {
   unsigned CurCycle = 0;
-  SUnit *Entry = SUnitMap[DAG.getEntryNode().Val].front();
 
   // All leaves to Available queue.
   for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
     // It is available if it has no predecessors.
-    if (SUnits[i].Preds.size() == 0 && &SUnits[i] != Entry) {
+    if (SUnits[i].Preds.empty()) {
       AvailableQueue->push(&SUnits[i]);
       SUnits[i].isAvailable = SUnits[i].isPending = true;
     }
   }
   
-  // Emit the entry node first.
-  ScheduleNodeTopDown(Entry, CurCycle);
-  HazardRec->EmitInstruction(Entry->Node);
-  
   // While Available queue is not empty, grab the node with the highest
   // priority. If it is not ready put it back.  Schedule the node.
   std::vector<SUnit*> NotReady;
+  Sequence.reserve(SUnits.size());
   while (!AvailableQueue->empty() || !PendingQueue.empty()) {
     // Check to see if any of the pending instructions are ready to issue.  If
     // so, add them to the available queue.
@@ -218,7 +206,7 @@ void ScheduleDAGList::ListScheduleTopDown() {
       // If this is a pseudo op, like copyfromreg, look to see if there is a
       // real target node flagged to it.  If so, use the target node.
       for (unsigned i = 0, e = CurSUnit->FlaggedNodes.size(); 
-           FoundNode->getOpcode() < ISD::BUILTIN_OP_END && i != e; ++i)
+           !FoundNode->isMachineOpcode() && i != e; ++i)
         FoundNode = CurSUnit->FlaggedNodes[i];
       
       HazardRecognizer::HazardType HT = HazardRec->getHazardType(FoundNode);
@@ -320,13 +308,12 @@ namespace {
     /// mobility.
     std::vector<unsigned> NumNodesSolelyBlocking;
 
-    std::priority_queue<SUnit*, std::vector<SUnit*>, latency_sort> Queue;
+    PriorityQueue<SUnit*, std::vector<SUnit*>, latency_sort> Queue;
 public:
     LatencyPriorityQueue() : Queue(latency_sort(this)) {
     }
     
-    void initNodes(DenseMap<SDNode*, std::vector<SUnit*> > &sumap,
-                   std::vector<SUnit> &sunits) {
+    void initNodes(std::vector<SUnit> &sunits) {
       SUnits = &sunits;
       // Calculate node priorities.
       CalculatePriorities();
@@ -379,25 +366,9 @@ public:
       return V;
     }
 
-    /// remove - This is a really inefficient way to remove a node from a
-    /// priority queue.  We should roll our own heap to make this better or
-    /// something.
     void remove(SUnit *SU) {
-      std::vector<SUnit*> Temp;
-      
       assert(!Queue.empty() && "Not in queue!");
-      while (Queue.top() != SU) {
-        Temp.push_back(Queue.top());
-        Queue.pop();
-        assert(!Queue.empty() && "Not in queue!");
-      }
-
-      // Remove the node from the PQ.
-      Queue.pop();
-      
-      // Add all the other nodes back.
-      for (unsigned i = 0, e = Temp.size(); i != e; ++i)
-        Queue.push(Temp[i]);
+      Queue.erase_one(SU);
     }
 
     // ScheduledNode - As nodes are scheduled, we look to see if there are any
@@ -478,7 +449,7 @@ void LatencyPriorityQueue::CalculatePriorities() {
   std::vector<std::pair<const SUnit*, unsigned> > WorkList;
   for (unsigned i = 0, e = SUnits->size(); i != e; ++i) {
     const SUnit *SU = &(*SUnits)[i];
-    if (SU->Succs.size() == 0)
+    if (SU->Succs.empty())
       WorkList.push_back(std::make_pair(SU, 0U));
   }
 
@@ -570,7 +541,7 @@ void LatencyPriorityQueue::AdjustPriorityOfUnscheduledPreds(SUnit *SU) {
 /// recognizer and deletes it when done.
 ScheduleDAG* llvm::createTDListDAGScheduler(SelectionDAGISel *IS,
                                             SelectionDAG *DAG,
-                                            MachineBasicBlock *BB) {
+                                            MachineBasicBlock *BB, bool Fast) {
   return new ScheduleDAGList(*DAG, BB, DAG->getTarget(),
                              new LatencyPriorityQueue(),
                              IS->CreateTargetHazardRecognizer());