Allow the APInt form of ComputeMaskedBits to operate on i128 types.

[oota-llvm.git] / lib / CodeGen / SelectionDAG / ScheduleDAGList.cpp

diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
index 369b05c5e9cb7211871a9c552b6a951165e90b51..3ae5e13c1cfe6c6321258d3e0eb8ac552c926e9f 100644 (file)
--- 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,8 +22,7 @@
 #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"
@@ -170,7 +169,7 @@ void ScheduleDAGList::ListScheduleTopDown() {
   // 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() && &SUnits[i] != Entry) {
       AvailableQueue->push(&SUnits[i]);
       SUnits[i].isAvailable = SUnits[i].isPending = true;
     }
@@ -443,22 +442,57 @@ int LatencyPriorityQueue::CalcLatency(const SUnit &SU) {
   int &Latency = Latencies[SU.NodeNum];
   if (Latency != -1)
     return Latency;
-  
-  int MaxSuccLatency = 0;
-  for (SUnit::const_succ_iterator I = SU.Succs.begin(), E = SU.Succs.end();
-       I != E; ++I)
-    MaxSuccLatency = std::max(MaxSuccLatency, CalcLatency(*I->Dep));
 
-  return Latency = MaxSuccLatency + SU.Latency;
+  std::vector<const SUnit*> WorkList;
+  WorkList.push_back(&SU);
+  while (!WorkList.empty()) {
+    const SUnit *Cur = WorkList.back();
+    bool AllDone = true;
+    int MaxSuccLatency = 0;
+    for (SUnit::const_succ_iterator I = Cur->Succs.begin(),E = Cur->Succs.end();
+         I != E; ++I) {
+      int SuccLatency = Latencies[I->Dep->NodeNum];
+      if (SuccLatency == -1) {
+        AllDone = false;
+        WorkList.push_back(I->Dep);
+      } else {
+        MaxSuccLatency = std::max(MaxSuccLatency, SuccLatency);
+      }
+    }
+    if (AllDone) {
+      Latencies[Cur->NodeNum] = MaxSuccLatency + Cur->Latency;
+      WorkList.pop_back();
+    }
+  }
+
+  return Latency;
 }
 
 /// CalculatePriorities - Calculate priorities of all scheduling units.
 void LatencyPriorityQueue::CalculatePriorities() {
   Latencies.assign(SUnits->size(), -1);
   NumNodesSolelyBlocking.assign(SUnits->size(), 0);
-  
-  for (unsigned i = 0, e = SUnits->size(); i != e; ++i)
-    CalcLatency((*SUnits)[i]);
+
+  // For each node, calculate the maximal path from the node to the exit.
+  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.empty())
+      WorkList.push_back(std::make_pair(SU, 0U));
+  }
+
+  while (!WorkList.empty()) {
+    const SUnit *SU = WorkList.back().first;
+    unsigned SuccLat = WorkList.back().second;
+    WorkList.pop_back();
+    int &Latency = Latencies[SU->NodeNum];
+    if (Latency == -1 || (SU->Latency + SuccLat) > (unsigned)Latency) {
+      Latency = SU->Latency + SuccLat;
+      for (SUnit::const_pred_iterator I = SU->Preds.begin(),E = SU->Preds.end();
+           I != E; ++I)
+        WorkList.push_back(std::make_pair(I->Dep, Latency));
+    }
+  }
 }
 
 /// getSingleUnscheduledPred - If there is exactly one unscheduled predecessor