misched: implemented a framework for top-down or bottom-up scheduling.

New flags: -misched-topdown, -misched-bottomup. They can be used with
the default scheduler or with -misched=shuffle. Without either
topdown/bottomup flag -misched=shuffle now alternates scheduling
direction.

LiveIntervals update is unimplemented with bottom-up scheduling, so
only -misched-topdown currently works.

Capped the ScheduleDAG hierarchy with a concrete ScheduleDAGMI class.
ScheduleDAGMI is aware of the top and bottom of the unscheduled zone
within the current region. Scheduling policy can be plugged into
the ScheduleDAGMI driver by implementing MachineSchedStrategy.
ConvergingScheduler is now the default scheduling algorithm.
It exercises the new driver but still does no reordering.

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

1 files changed, 7 insertions, 4 deletions

diff --git a/lib/CodeGen/ScheduleDAGInstrs.cpp b/lib/CodeGen/ScheduleDAGInstrs.cpp
index ed06672437..54828e28d1 100644
--- a/lib/CodeGen/ScheduleDAGInstrs.cpp
+++ b/lib/CodeGen/ScheduleDAGInstrs.cpp
@@ -163,6 +163,7 @@ void ScheduleDAGInstrs::enterRegion(MachineBasicBlock *bb,
   RegionBegin = begin;
   RegionEnd = end;
   EndIndex = endcount;
+  MISUnitMap.clear();
 
   // Check to see if the scheduler cares about latencies.
   UnitLatencies = forceUnitLatencies();
@@ -469,9 +470,12 @@ void ScheduleDAGInstrs::addVRegUseDeps(SUnit *SU, unsigned OperIdx) {
 ///
 /// Map each real instruction to its SUnit.
 ///
-/// After initSUnits, the SUnits vector is cannot be resized and the scheduler
-/// may hang onto SUnit pointers. We may relax this in the future by using SUnit
-/// IDs instead of pointers.
+/// After initSUnits, the SUnits vector cannot be resized and the scheduler may
+/// hang onto SUnit pointers. We may relax this in the future by using SUnit IDs
+/// instead of pointers.
+///
+/// MachineScheduler relies on initSUnits numbering the nodes by their order in
+/// the original instruction list.
 void ScheduleDAGInstrs::initSUnits() {
   // We'll be allocating one SUnit for each real instruction in the region,
   // which is contained within a basic block.
@@ -726,7 +730,6 @@ void ScheduleDAGInstrs::buildSchedGraph(AliasAnalysis *AA) {
   Uses.clear();
   VRegDefs.clear();
   PendingLoads.clear();
-  MISUnitMap.clear();
 }
 
 void ScheduleDAGInstrs::computeLatency(SUnit *SU) {