Various bits of framework needed for precise machine-level selection

DAG scheduling during isel. Most new functionality is currently
guarded by -enable-sched-cycles and -enable-sched-hazard.

Added InstrItineraryData::IssueWidth field, currently derived from
ARM itineraries, but could be initialized differently on other targets.

Added ScheduleHazardRecognizer::MaxLookAhead to indicate whether it is
active, and if so how many cycles of state it holds.

Added SchedulingPriorityQueue::HasReadyFilter to allowing gating entry
into the scheduler's available queue.

ScoreboardHazardRecognizer now accesses the ScheduleDAG in order to
get information about it's SUnits, provides RecedeCycle for bottom-up
scheduling, correctly computes scoreboard depth, tracks IssueCount, and
considers potential stall cycles when checking for hazards.

ScheduleDAGRRList now models machine cycles and hazards (under
flags). It tracks MinAvailableCycle, drives the hazard recognizer and
priority queue's ready filter, manages a new PendingQueue, properly
accounts for stall cycles, etc.

llvm-svn: 122541

6 files changed, 64 insertions, 16 deletions

diff --git a/llvm/lib/Target/ARM/ARMBaseInstrInfo.cpp b/llvm/lib/Target/ARM/ARMBaseInstrInfo.cpp
index 8edc0e7f121..fd13485d1f1 100644
--- a/llvm/lib/Target/ARM/ARMBaseInstrInfo.cpp
+++ b/llvm/lib/Target/ARM/ARMBaseInstrInfo.cpp
@@ -41,6 +41,13 @@ static cl::opt<bool>
 EnableARM3Addr("enable-arm-3-addr-conv", cl::Hidden,
                cl::desc("Enable ARM 2-addr to 3-addr conv"));
 
+// Other targets already have a hazard recognizer enabled by default, so this
+// flag currently only affects ARM. It will be generalized when it becomes a
+// disabled flag.
+static cl::opt<bool> EnableHazardRecognizer(
+  "enable-sched-hazard", cl::Hidden,
+  cl::desc("Enable hazard detection during preRA scheduling"),
+  cl::init(false));
 
 /// ARM_MLxEntry - Record information about MLA / MLS instructions.
 struct ARM_MLxEntry {
@@ -85,12 +92,25 @@ ARMBaseInstrInfo::ARMBaseInstrInfo(const ARMSubtarget& STI)
   }
 }
 
+// Use a ScoreboardHazardRecognizer for prepass ARM scheduling. TargetInstrImpl
+// currently defaults to no prepass hazard recognizer.
 ScheduleHazardRecognizer *ARMBaseInstrInfo::
-CreateTargetPostRAHazardRecognizer(const InstrItineraryData *II) const {
+CreateTargetHazardRecognizer(const TargetMachine *TM,
+                             const ScheduleDAG *DAG) const {
+  if (EnableHazardRecognizer) {
+    const InstrItineraryData *II = TM->getInstrItineraryData();
+    return new ScoreboardHazardRecognizer(II, DAG, "pre-RA-sched");
+  }
+  return TargetInstrInfoImpl::CreateTargetHazardRecognizer(TM, DAG);
+}
+
+ScheduleHazardRecognizer *ARMBaseInstrInfo::
+CreateTargetPostRAHazardRecognizer(const InstrItineraryData *II,
+                                   const ScheduleDAG *DAG) const {
   if (Subtarget.isThumb2() || Subtarget.hasVFP2())
     return (ScheduleHazardRecognizer *)
-      new ARMHazardRecognizer(II, *this, getRegisterInfo(), Subtarget);
-  return TargetInstrInfoImpl::CreateTargetPostRAHazardRecognizer(II);
+      new ARMHazardRecognizer(II, *this, getRegisterInfo(), Subtarget, DAG);
+  return TargetInstrInfoImpl::CreateTargetPostRAHazardRecognizer(II, DAG);
 }
 
 MachineInstr *
diff --git a/llvm/lib/Target/ARM/ARMBaseInstrInfo.h b/llvm/lib/Target/ARM/ARMBaseInstrInfo.h
index ca8b9a02405..0ea8a9600bf 100644
--- a/llvm/lib/Target/ARM/ARMBaseInstrInfo.h
+++ b/llvm/lib/Target/ARM/ARMBaseInstrInfo.h
@@ -211,7 +211,12 @@ public:
   const ARMSubtarget &getSubtarget() const { return Subtarget; }
 
   ScheduleHazardRecognizer *
-  CreateTargetPostRAHazardRecognizer(const InstrItineraryData *II) const;
+  CreateTargetHazardRecognizer(const TargetMachine *TM,
+                               const ScheduleDAG *DAG) const;
+
+  ScheduleHazardRecognizer *
+  CreateTargetPostRAHazardRecognizer(const InstrItineraryData *II,
+                                     const ScheduleDAG *DAG) const;
 
   // Branch analysis.
   virtual bool AnalyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB,
diff --git a/llvm/lib/Target/ARM/ARMHazardRecognizer.cpp b/llvm/lib/Target/ARM/ARMHazardRecognizer.cpp
index b8d385b6e3d..683a7cc1695 100644
--- a/llvm/lib/Target/ARM/ARMHazardRecognizer.cpp
+++ b/llvm/lib/Target/ARM/ARMHazardRecognizer.cpp
@@ -34,7 +34,9 @@ static bool hasRAWHazard(MachineInstr *DefMI, MachineInstr *MI,
 }
 
 ScheduleHazardRecognizer::HazardType
-ARMHazardRecognizer::getHazardType(SUnit *SU) {
+ARMHazardRecognizer::getHazardType(SUnit *SU, int Stalls) {
+  assert(Stalls == 0 && "ARM hazards don't support scoreboard lookahead");
+
   MachineInstr *MI = SU->getInstr();
 
   if (!MI->isDebugValue()) {
@@ -61,19 +63,19 @@ ARMHazardRecognizer::getHazardType(SUnit *SU) {
           (TII.canCauseFpMLxStall(MI->getOpcode()) ||
            hasRAWHazard(DefMI, MI, TRI))) {
         // Try to schedule another instruction for the next 4 cycles.
-        if (Stalls == 0)
-          Stalls = 4;
+        if (FpMLxStalls == 0)
+          FpMLxStalls = 4;
         return Hazard;
       }
     }
   }
 
-  return ScoreboardHazardRecognizer::getHazardType(SU);
+  return ScoreboardHazardRecognizer::getHazardType(SU, Stalls);
 }
 
 void ARMHazardRecognizer::Reset() {
   LastMI = 0;
-  Stalls = 0;
+  FpMLxStalls = 0;
   ITBlockSize = 0;
   ScoreboardHazardRecognizer::Reset();
 }
@@ -100,14 +102,14 @@ void ARMHazardRecognizer::EmitInstruction(SUnit *SU) {
 
   if (!MI->isDebugValue()) {
     LastMI = MI;
-    Stalls = 0;
+    FpMLxStalls = 0;
   }
 
   ScoreboardHazardRecognizer::EmitInstruction(SU);
 }
 
 void ARMHazardRecognizer::AdvanceCycle() {
-  if (Stalls && --Stalls == 0)
+  if (FpMLxStalls && --FpMLxStalls == 0)
     // Stalled for 4 cycles but still can't schedule any other instructions.
     LastMI = 0;
   ScoreboardHazardRecognizer::AdvanceCycle();
diff --git a/llvm/lib/Target/ARM/ARMHazardRecognizer.h b/llvm/lib/Target/ARM/ARMHazardRecognizer.h
index 9473bc52072..2bc218d8566 100644
--- a/llvm/lib/Target/ARM/ARMHazardRecognizer.h
+++ b/llvm/lib/Target/ARM/ARMHazardRecognizer.h
@@ -29,7 +29,7 @@ class ARMHazardRecognizer : public ScoreboardHazardRecognizer {
   const ARMSubtarget &STI;
 
   MachineInstr *LastMI;
-  unsigned Stalls;
+  unsigned FpMLxStalls;
   unsigned ITBlockSize;  // No. of MIs in current IT block yet to be scheduled.
   MachineInstr *ITBlockMIs[4];
 
@@ -37,11 +37,12 @@ public:
   ARMHazardRecognizer(const InstrItineraryData *ItinData,
                       const ARMBaseInstrInfo &tii,
                       const ARMBaseRegisterInfo &tri,
-                      const ARMSubtarget &sti) :
-    ScoreboardHazardRecognizer(ItinData), TII(tii), TRI(tri), STI(sti),
-    LastMI(0), ITBlockSize(0) {}
+                      const ARMSubtarget &sti,
+                      const ScheduleDAG *DAG) :
+    ScoreboardHazardRecognizer(ItinData, DAG, "post-RA-sched"), TII(tii),
+    TRI(tri), STI(sti), LastMI(0), ITBlockSize(0) {}
 
-  virtual HazardType getHazardType(SUnit *SU);
+  virtual HazardType getHazardType(SUnit *SU, int Stalls);
   virtual void Reset();
   virtual void EmitInstruction(SUnit *SU);
   virtual void AdvanceCycle();
diff --git a/llvm/lib/Target/ARM/ARMSubtarget.cpp b/llvm/lib/Target/ARM/ARMSubtarget.cpp
index b0057bd2093..6290e676758 100644
--- a/llvm/lib/Target/ARM/ARMSubtarget.cpp
+++ b/llvm/lib/Target/ARM/ARMSubtarget.cpp
@@ -140,6 +140,9 @@ ARMSubtarget::ARMSubtarget(const std::string &TT, const std::string &FS,
     FSWithArch = FS;
   CPUString = ParseSubtargetFeatures(FSWithArch, CPUString);
 
+  // After parsing Itineraries, set ItinData.IssueWidth.
+  computeIssueWidth();
+
   // Thumb2 implies at least V6T2.
   if (ARMArchVersion >= V6T2)
     ThumbMode = Thumb2;
@@ -224,6 +227,21 @@ unsigned ARMSubtarget::getMispredictionPenalty() const {
   return 10;
 }
 
+void ARMSubtarget::computeIssueWidth() {
+  unsigned allStage1Units = 0;
+  for (const InstrItinerary *itin = InstrItins.Itineraries;
+       itin->FirstStage != ~0U; ++itin) {
+    const InstrStage *IS = InstrItins.Stages + itin->FirstStage;
+    allStage1Units |= IS->getUnits();
+  }
+  InstrItins.IssueWidth = 0;
+  while (allStage1Units) {
+    ++InstrItins.IssueWidth;
+    // clear the lowest bit
+    allStage1Units ^= allStage1Units & ~(allStage1Units - 1);
+  }
+}
+
 bool ARMSubtarget::enablePostRAScheduler(
            CodeGenOpt::Level OptLevel,
            TargetSubtarget::AntiDepBreakMode& Mode,
diff --git a/llvm/lib/Target/ARM/ARMSubtarget.h b/llvm/lib/Target/ARM/ARMSubtarget.h
index fdd394dce3d..8d911d010a4 100644
--- a/llvm/lib/Target/ARM/ARMSubtarget.h
+++ b/llvm/lib/Target/ARM/ARMSubtarget.h
@@ -156,6 +156,8 @@ protected:
   std::string ParseSubtargetFeatures(const std::string &FS,
                                      const std::string &CPU);
 
+  void computeIssueWidth();
+
   bool hasV4TOps()  const { return ARMArchVersion >= V4T;  }
   bool hasV5TOps()  const { return ARMArchVersion >= V5T;  }
   bool hasV5TEOps() const { return ARMArchVersion >= V5TE; }