Skeleton of the list schedule.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@25544 91177308-0d34-0410-b5e6-96231b3b80d8

3 files changed, 74 insertions, 3 deletions

diff --git a/include/llvm/CodeGen/ScheduleDAG.h b/include/llvm/CodeGen/ScheduleDAG.h
index 41c4872773..3401c7d812 100644
--- a/include/llvm/CodeGen/ScheduleDAG.h
+++ b/include/llvm/CodeGen/ScheduleDAG.h
@@ -37,9 +37,10 @@ namespace llvm {
 
   // Scheduling heuristics
   enum SchedHeuristics {
-    noScheduling,
-    simpleScheduling,
-    simpleNoItinScheduling
+    noScheduling,           // No scheduling, emit breath first sequence.
+    simpleScheduling,       // Two pass, min. critical path, max. utilization.
+    simpleNoItinScheduling, // Same as above exact using generic latency.
+    listSchedulingBURR,     // Bottom up reg reduction list scheduling.
   };
 
 
@@ -332,6 +333,11 @@ namespace llvm {
   ScheduleDAG* createSimpleDAGScheduler(SchedHeuristics Heuristic,
                                         SelectionDAG &DAG,
                                         MachineBasicBlock *BB);
+
+  /// createBURRListDAGScheduler - This creates a bottom up register usage
+  /// reduction list scheduler.
+  ScheduleDAG* createBURRListDAGScheduler(SelectionDAG &DAG,
+                                          MachineBasicBlock *BB);
 }
 
 #endif
diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
new file mode 100644
index 0000000000..dca430257c
--- /dev/null
+++ b/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
@@ -0,0 +1,61 @@
+//===-- ScheduleDAGSimple.cpp - Implement a list scheduler for isel DAG ---===//
+//
+//                     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 implements a simple two pass scheduler.  The first pass attempts to push
+// backward any lengthy instructions and critical paths.  The second pass packs
+// instructions into semi-optimal time slots.
+//
+//===----------------------------------------------------------------------===//
+
+#define DEBUG_TYPE "sched"
+#include "llvm/CodeGen/ScheduleDAG.h"
+#include "llvm/CodeGen/SelectionDAG.h"
+#include "llvm/Target/TargetMachine.h"
+#include "llvm/Target/TargetInstrInfo.h"
+#include <algorithm>
+#include <queue>
+using namespace llvm;
+
+
+namespace llvm {
+/// Sorting functions for ready queue.
+struct LSSortPred : public std::binary_function<SDOperand, SDOperand, bool> {
+  bool operator()(const SDOperand* left, const SDOperand* right) const {
+    return true;
+  }
+};
+
+/// ScheduleDAGList - List scheduler.
+
+class ScheduleDAGList : public ScheduleDAG {
+private:
+  LSSortPred &Cmp;
+
+  // Ready queue
+  std::priority_queue<SDOperand*, std::vector<SDOperand*>, LSSortPred> Ready;
+                      
+public:
+  ScheduleDAGList(SelectionDAG &dag, MachineBasicBlock *bb,
+                  const TargetMachine &tm, LSSortPred cmp)
+    : ScheduleDAG(listSchedulingBURR, dag, bb, tm), Cmp(cmp), Ready(Cmp)
+  {};
+
+  void Schedule();
+};
+}  // end namespace llvm
+
+void ScheduleDAGList::Schedule() {
+}
+  
+
+llvm::ScheduleDAG*
+llvm::createBURRListDAGScheduler(SelectionDAG &DAG,
+                                 MachineBasicBlock *BB) {
+  return new ScheduleDAGList(DAG, BB, DAG.getTarget(), LSSortPred());
+}
diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
index aa410bd0a6..6cc4d436e9 100644
--- a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
+++ b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
@@ -69,6 +69,8 @@ namespace {
       clEnumValN(simpleNoItinScheduling, "simple-noitin",
                  "Simple two pass scheduling: Same as simple "
                  "except using generic latency"),
+      clEnumValN(listSchedulingBURR, "list-BURR",
+                 "Bottom up register reduction list scheduling"),
       clEnumValEnd));
 } // namespace
 
@@ -1775,6 +1777,8 @@ void SelectionDAGISel::ScheduleAndEmitDAG(SelectionDAG &DAG) {
   case simpleNoItinScheduling:
     SL = createSimpleDAGScheduler(ISHeuristic, DAG, BB);
     break;
+  case listSchedulingBURR:
+    SL = createBURRListDAGScheduler(DAG, BB);
   }
   BB = SL->Run();
 }