[Schedule] Add a MultiHazardRecognizer

[dmgreen]

Summary

This adds a MultiHazardRecognizer and starts to make use of it in the ARM backend. The idea of the class is to allow multiple independent hazard recognizers to be added to a single base MultiHazardRecognizer, allowing them to all work in parallel without requiring them to be chained into subclasses. They can then be added or not based on cpu or subtarget features, which will become useful in the ARM backend once more hazard recognizers are being used for various things.

This also renames ARMHazardRecognizer to ARMHazardRecognizerFPMLx in the process, to more clearly explain what that recognizer is designed for.

[dmgreen]

Rebase

[SjoerdMeijer]

Hazard recognisers is not really my area, but this looks like a straightforward refactoring to me. Two nits: one is a style issue inlined, the other is just a quick question if you plan to use this extra flexibility any time soon?

llvm/lib/CodeGen/MultiHazardRecognizer.cpp

23

No need for the curly brackets. Same for all the other loops below.

[arsenm]

llvm/include/llvm/CodeGen/MultiHazardRecognizer.h

36

No virtual + override

llvm/lib/CodeGen/MultiHazardRecognizer.cpp

24

These should just be unique_ptr to begin with and avoid the explicit deletes here

[dmgreen]

Thanks for the suggestions. Changed to use unique_ptr's and cleaned up the brackets/virtuals.

[dmgreen]

just a quick question if you plan to use this extra flexibility any time soon?

Yep. Plan is to make use of it some Cortex-M7 scheduling we are aiming to upstream soon, along with hopefully more in the future.

[SjoerdMeijer]

LGTM, but please wait a day in case @arsenm has more comments.

llvm/include/llvm/CodeGen/MultiHazardRecognizer.h

+//=- llvm/CodeGen/MultiHazardRecognizer.h - Scheduling Support ----*- C++ -*-=//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the MultiHazardRecognizer class, which is a wrapper
+// for a set of ScheduleHazardRecognizer instances
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_MULTIHAZARDRECOGNIZER_H
+#define LLVM_CODEGEN_MULTIHAZARDRECOGNIZER_H
+
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/CodeGen/ScheduleHazardRecognizer.h"
+
+namespace llvm {
+
+class MachineInstr;
+class SUnit;
+
+class MultiHazardRecognizer : public ScheduleHazardRecognizer {
+  SmallVector<std::unique_ptr<ScheduleHazardRecognizer>, 4> Recognizers;
+
+public:
+  MultiHazardRecognizer() = default;
+  void AddHazardRecognizer(std::unique_ptr<ScheduleHazardRecognizer> &&);
+
+  bool atIssueLimit() const override;
+  HazardType getHazardType(SUnit *m, int Stalls = 0) override;
+  void Reset() override;
+  void EmitInstruction(SUnit *) override;
+  void EmitInstruction(MachineInstr *) override;
+  unsigned PreEmitNoops(SUnit *) override;
+  unsigned PreEmitNoops(MachineInstr *) override;
+  bool ShouldPreferAnother(SUnit *) override;
+  void AdvanceCycle() override;
+  void RecedeCycle() override;
+  void EmitNoop() override;
+};
+
+} // end namespace llvm
+
+#endif // LLVM_CODEGEN_MULTIHAZARDRECOGNIZER_H

llvm/lib/CodeGen/CMakeLists.txt

add_llvm_component_library(LLVMCodeGen
   MachineScheduler.cpp
   MachineSink.cpp
   MachineSizeOpts.cpp
   MachineSSAUpdater.cpp
   MachineStripDebug.cpp
   MachineTraceMetrics.cpp
   MachineVerifier.cpp
   ModuloSchedule.cpp
+  MultiHazardRecognizer.cpp
   PatchableFunction.cpp
   MBFIWrapper.cpp
   MIRPrinter.cpp
   MIRPrintingPass.cpp
   MacroFusion.cpp
   NonRelocatableStringpool.cpp
   OptimizePHIs.cpp
   ParallelCG.cpp

llvm/lib/CodeGen/MultiHazardRecognizer.cpp

+//===- MultiHazardRecognizer.cpp - Scheduler Support ----------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the MultiHazardRecognizer class, which is a wrapper
+// for a set of ScheduleHazardRecognizer instances
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/MultiHazardRecognizer.h"
+#include <algorithm>
+#include <functional>
+#include <numeric>
+
+using namespace llvm;
+
+void MultiHazardRecognizer::AddHazardRecognizer(
+    std::unique_ptr<ScheduleHazardRecognizer> &&R) {
+  MaxLookAhead = std::max(MaxLookAhead, R->getMaxLookAhead());
+  Recognizers.push_back(std::move(R));
+}
+
+bool MultiHazardRecognizer::atIssueLimit() const {
+  return std::any_of(Recognizers.begin(), Recognizers.end(),
+                     std::mem_fn(&ScheduleHazardRecognizer::atIssueLimit));
+}
+
+ScheduleHazardRecognizer::HazardType
+MultiHazardRecognizer::getHazardType(SUnit *SU, int Stalls) {
+  for (auto &R : Recognizers) {
+    auto res = R->getHazardType(SU, Stalls);
+    if (res != NoHazard)
+      return res;
+  }
+  return NoHazard;
+}
+
+void MultiHazardRecognizer::Reset() {
+  for (auto &R : Recognizers)
+    R->Reset();
+}
+
+void MultiHazardRecognizer::EmitInstruction(SUnit *SU) {
+  for (auto &R : Recognizers)
+    R->EmitInstruction(SU);
+}
+
+void MultiHazardRecognizer::EmitInstruction(MachineInstr *MI) {
+  for (auto &R : Recognizers)
+    R->EmitInstruction(MI);
+}
+
+unsigned MultiHazardRecognizer::PreEmitNoops(SUnit *SU) {
+  auto MN = [=](unsigned a, std::unique_ptr<ScheduleHazardRecognizer> &R) {
+    return std::max(a, R->PreEmitNoops(SU));
+  };
+  return std::accumulate(Recognizers.begin(), Recognizers.end(), 0u, MN);
+}
+
+unsigned MultiHazardRecognizer::PreEmitNoops(MachineInstr *MI) {
+  auto MN = [=](unsigned a, std::unique_ptr<ScheduleHazardRecognizer> &R) {
+    return std::max(a, R->PreEmitNoops(MI));
+  };
+  return std::accumulate(Recognizers.begin(), Recognizers.end(), 0u, MN);
+}
+
+bool MultiHazardRecognizer::ShouldPreferAnother(SUnit *SU) {
+  auto SPA = [=](std::unique_ptr<ScheduleHazardRecognizer> &R) {
+    return R->ShouldPreferAnother(SU);
+  };
+  return std::any_of(Recognizers.begin(), Recognizers.end(), SPA);
+}
+
+void MultiHazardRecognizer::AdvanceCycle() {
+  for (auto &R : Recognizers)
+    R->AdvanceCycle();
+}
+
+void MultiHazardRecognizer::RecedeCycle() {
+  for (auto &R : Recognizers)
+    R->RecedeCycle();
+}
+
+void MultiHazardRecognizer::EmitNoop() {
+  for (auto &R : Recognizers)
+    R->EmitNoop();
+}

llvm/lib/Target/ARM/ARMBaseInstrInfo.cpp

 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineMemOperand.h"
 #include "llvm/CodeGen/MachineModuleInfo.h"
 #include "llvm/CodeGen/MachineOperand.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/MachineScheduler.h"
+#include "llvm/CodeGen/MultiHazardRecognizer.h"
 #include "llvm/CodeGen/ScoreboardHazardRecognizer.h"
 #include "llvm/CodeGen/SelectionDAGNodes.h"
 #include "llvm/CodeGen/TargetInstrInfo.h"
 #include "llvm/CodeGen/TargetRegisterInfo.h"
 #include "llvm/CodeGen/TargetSchedule.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DebugLoc.h"
if (usePreRAHazardRecognizer()) {
     return new ScoreboardHazardRecognizer(II, DAG, "pre-RA-sched");
   }
   return TargetInstrInfo::CreateTargetHazardRecognizer(STI, DAG);
 }
 
 ScheduleHazardRecognizer *ARMBaseInstrInfo::
 CreateTargetPostRAHazardRecognizer(const InstrItineraryData *II,
                                    const ScheduleDAG *DAG) const {
+  MultiHazardRecognizer *MHR = new MultiHazardRecognizer();
+
   if (Subtarget.isThumb2() || Subtarget.hasVFP2Base())
-    return new ARMHazardRecognizer(II, DAG);
-  return TargetInstrInfo::CreateTargetPostRAHazardRecognizer(II, DAG);
+    MHR->AddHazardRecognizer(std::make_unique<ARMHazardRecognizerFPMLx>());
+
+  auto BHR = TargetInstrInfo::CreateTargetPostRAHazardRecognizer(II, DAG);
+  if (BHR)
+    MHR->AddHazardRecognizer(std::unique_ptr<ScheduleHazardRecognizer>(BHR));
+  return MHR;
 }
 
 MachineInstr *ARMBaseInstrInfo::convertToThreeAddress(
     MachineFunction::iterator &MFI, MachineInstr &MI, LiveVariables *LV) const {
   // FIXME: Thumb2 support.
 
   if (!EnableARM3Addr)
     return nullptr;

llvm/lib/Target/ARM/ARMHazardRecognizer.h

 //===-- ARMHazardRecognizer.h - ARM Hazard Recognizers ----------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file defines hazard recognizers for scheduling ARM functions.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_LIB_TARGET_ARM_ARMHAZARDRECOGNIZER_H
 #define LLVM_LIB_TARGET_ARM_ARMHAZARDRECOGNIZER_H
 
-#include "llvm/CodeGen/ScoreboardHazardRecognizer.h"
+#include "llvm/CodeGen/ScheduleHazardRecognizer.h"
 
 namespace llvm {
 
-class ARMBaseInstrInfo;
-class ARMBaseRegisterInfo;
-class ARMSubtarget;
-class MachineInstr;
-
-/// ARMHazardRecognizer handles special constraints that are not expressed in
-/// the scheduling itinerary. This is only used during postRA scheduling. The
-/// ARM preRA scheduler uses an unspecialized instance of the
-/// ScoreboardHazardRecognizer.
-class ARMHazardRecognizer : public ScoreboardHazardRecognizer {
+// Hazards related to FP MLx instructions
+class ARMHazardRecognizerFPMLx : public ScheduleHazardRecognizer {
   MachineInstr *LastMI = nullptr;
   unsigned FpMLxStalls = 0;
 
 public:
-  ARMHazardRecognizer(const InstrItineraryData *ItinData,
-                      const ScheduleDAG *DAG)
-      : ScoreboardHazardRecognizer(ItinData, DAG, "post-RA-sched") {}
+  ARMHazardRecognizerFPMLx() : ScheduleHazardRecognizer() { MaxLookAhead = 1; }
 
   HazardType getHazardType(SUnit *SU, int Stalls) override;
   void Reset() override;
   void EmitInstruction(SUnit *SU) override;
   void AdvanceCycle() override;
   void RecedeCycle() override;
 };
 
 } // end namespace llvm
 
 #endif

llvm/lib/Target/ARM/ARMHazardRecognizer.cpp

static bool hasRAWHazard(MachineInstr *DefMI, MachineInstr *MI,
   if (Opcode == ARM::VMOVRS || Opcode == ARM::VMOVRRD)
     return false;
   if ((Domain & ARMII::DomainVFP) || (Domain & ARMII::DomainNEON))
     return MI->readsRegister(DefMI->getOperand(0).getReg(), &TRI);
   return false;
 }
 
 ScheduleHazardRecognizer::HazardType
-ARMHazardRecognizer::getHazardType(SUnit *SU, int Stalls) {
+ARMHazardRecognizerFPMLx::getHazardType(SUnit *SU, int Stalls) {
   assert(Stalls == 0 && "ARM hazards don't support scoreboard lookahead");
 
   MachineInstr *MI = SU->getInstr();
 
   if (!MI->isDebugInstr()) {
     // Look for special VMLA / VMLS hazards. A VMUL / VADD / VSUB following
     // a VMLA / VMLS will cause 4 cycle stall.
     const MCInstrDesc &MCID = MI->getDesc();
if (LastMI && (MCID.TSFlags & ARMII::DomainMask) != ARMII::DomainGeneral) {
            hasRAWHazard(DefMI, MI, TII.getRegisterInfo()))) {
         // Try to schedule another instruction for the next 4 cycles.
         if (FpMLxStalls == 0)
           FpMLxStalls = 4;
         return Hazard;
       }
     }
   }
-
-  return ScoreboardHazardRecognizer::getHazardType(SU, Stalls);
+  return NoHazard;
 }
 
-void ARMHazardRecognizer::Reset() {
+void ARMHazardRecognizerFPMLx::Reset() {
   LastMI = nullptr;
   FpMLxStalls = 0;
-  ScoreboardHazardRecognizer::Reset();
 }
 
-void ARMHazardRecognizer::EmitInstruction(SUnit *SU) {
+void ARMHazardRecognizerFPMLx::EmitInstruction(SUnit *SU) {
   MachineInstr *MI = SU->getInstr();
   if (!MI->isDebugInstr()) {
     LastMI = MI;
     FpMLxStalls = 0;
   }
-
-  ScoreboardHazardRecognizer::EmitInstruction(SU);
 }
 
-void ARMHazardRecognizer::AdvanceCycle() {
+void ARMHazardRecognizerFPMLx::AdvanceCycle() {
   if (FpMLxStalls && --FpMLxStalls == 0)
     // Stalled for 4 cycles but still can't schedule any other instructions.
     LastMI = nullptr;
-  ScoreboardHazardRecognizer::AdvanceCycle();
 }
 
-void ARMHazardRecognizer::RecedeCycle() {
+void ARMHazardRecognizerFPMLx::RecedeCycle() {
   llvm_unreachable("reverse ARM hazard checking unsupported");
 }