[SystemZ] Add a SystemZ specific pre-RA scheduling strategy. #135076
Conversation
|
@llvm/pr-subscribers-llvm-regalloc @llvm/pr-subscribers-backend-systemz Author: Jonas Paulsson (JonPsson1) ChangesAs the heavy spilling in Cactus was found to be caused by the This time, a SystemZ specific MachineSchedStrategy has been developed, guided Finding that GenericScheduler fails to handle liveness despite all the work SPEC Results (omitting <1% changes): Compile time showed at first some heavy regressions that were due to a Patch is 211.25 KiB, truncated to 20.00 KiB below, full version: https://github.com/llvm/llvm-project/pull/135076.diff 58 Files Affected:
diff --git a/llvm/include/llvm/CodeGen/MachineScheduler.h b/llvm/include/llvm/CodeGen/MachineScheduler.h
index bc00d0b4ff852..8a819051f069a 100644
--- a/llvm/include/llvm/CodeGen/MachineScheduler.h
+++ b/llvm/include/llvm/CodeGen/MachineScheduler.h
@@ -1087,6 +1087,7 @@ class GenericSchedulerBase : public MachineSchedStrategy {
NoCand,
Only1,
PhysReg,
+ LivenessReduce,
RegExcess,
RegCritical,
Stall,
@@ -1218,6 +1219,7 @@ class GenericSchedulerBase : public MachineSchedStrategy {
};
// Utility functions used by heuristics in tryCandidate().
+unsigned computeRemLatency(SchedBoundary &CurrZone);
bool tryLess(int TryVal, int CandVal,
GenericSchedulerBase::SchedCandidate &TryCand,
GenericSchedulerBase::SchedCandidate &Cand,
diff --git a/llvm/lib/CodeGen/MachineScheduler.cpp b/llvm/lib/CodeGen/MachineScheduler.cpp
index 97f27277aface..579f787b0af9b 100644
--- a/llvm/lib/CodeGen/MachineScheduler.cpp
+++ b/llvm/lib/CodeGen/MachineScheduler.cpp
@@ -3168,31 +3168,6 @@ initResourceDelta(const ScheduleDAGMI *DAG,
}
}
-/// Compute remaining latency. We need this both to determine whether the
-/// overall schedule has become latency-limited and whether the instructions
-/// outside this zone are resource or latency limited.
-///
-/// The "dependent" latency is updated incrementally during scheduling as the
-/// max height/depth of scheduled nodes minus the cycles since it was
-/// scheduled:
-/// DLat = max (N.depth - (CurrCycle - N.ReadyCycle) for N in Zone
-///
-/// The "independent" latency is the max ready queue depth:
-/// ILat = max N.depth for N in Available|Pending
-///
-/// RemainingLatency is the greater of independent and dependent latency.
-///
-/// These computations are expensive, especially in DAGs with many edges, so
-/// only do them if necessary.
-static unsigned computeRemLatency(SchedBoundary &CurrZone) {
- unsigned RemLatency = CurrZone.getDependentLatency();
- RemLatency = std::max(RemLatency,
- CurrZone.findMaxLatency(CurrZone.Available.elements()));
- RemLatency = std::max(RemLatency,
- CurrZone.findMaxLatency(CurrZone.Pending.elements()));
- return RemLatency;
-}
-
/// Returns true if the current cycle plus remaning latency is greater than
/// the critical path in the scheduling region.
bool GenericSchedulerBase::shouldReduceLatency(const CandPolicy &Policy,
@@ -3278,6 +3253,7 @@ const char *GenericSchedulerBase::getReasonStr(
case NoCand: return "NOCAND ";
case Only1: return "ONLY1 ";
case PhysReg: return "PHYS-REG ";
+ case LivenessReduce: return "LIVE-REDUC";
case RegExcess: return "REG-EXCESS";
case RegCritical: return "REG-CRIT ";
case Stall: return "STALL ";
@@ -3351,6 +3327,31 @@ void GenericSchedulerBase::traceCandidate(const SchedCandidate &Cand) {
#endif
namespace llvm {
+/// Compute remaining latency. We need this both to determine whether the
+/// overall schedule has become latency-limited and whether the instructions
+/// outside this zone are resource or latency limited.
+///
+/// The "dependent" latency is updated incrementally during scheduling as the
+/// max height/depth of scheduled nodes minus the cycles since it was
+/// scheduled:
+/// DLat = max (N.depth - (CurrCycle - N.ReadyCycle) for N in Zone
+///
+/// The "independent" latency is the max ready queue depth:
+/// ILat = max N.depth for N in Available|Pending
+///
+/// RemainingLatency is the greater of independent and dependent latency.
+///
+/// These computations are expensive, especially in DAGs with many edges, so
+/// only do them if necessary.
+unsigned computeRemLatency(SchedBoundary &CurrZone) {
+ unsigned RemLatency = CurrZone.getDependentLatency();
+ RemLatency = std::max(RemLatency,
+ CurrZone.findMaxLatency(CurrZone.Available.elements()));
+ RemLatency = std::max(RemLatency,
+ CurrZone.findMaxLatency(CurrZone.Pending.elements()));
+ return RemLatency;
+}
+
/// Return true if this heuristic determines order.
/// TODO: Consider refactor return type of these functions as integer or enum,
/// as we may need to differentiate whether TryCand is better than Cand.
diff --git a/llvm/lib/Target/SystemZ/SystemZElimCompare.cpp b/llvm/lib/Target/SystemZ/SystemZElimCompare.cpp
index 81f0014dd83f2..149a7b2f451d5 100644
--- a/llvm/lib/Target/SystemZ/SystemZElimCompare.cpp
+++ b/llvm/lib/Target/SystemZ/SystemZElimCompare.cpp
@@ -151,30 +151,6 @@ Reference SystemZElimCompare::getRegReferences(MachineInstr &MI, unsigned Reg) {
return Ref;
}
-// Return true if this is a load and test which can be optimized the
-// same way as compare instruction.
-static bool isLoadAndTestAsCmp(MachineInstr &MI) {
- // If we during isel used a load-and-test as a compare with 0, the
- // def operand is dead.
- return (MI.getOpcode() == SystemZ::LTEBR ||
- MI.getOpcode() == SystemZ::LTDBR ||
- MI.getOpcode() == SystemZ::LTXBR) &&
- MI.getOperand(0).isDead();
-}
-
-// Return the source register of Compare, which is the unknown value
-// being tested.
-static unsigned getCompareSourceReg(MachineInstr &Compare) {
- unsigned reg = 0;
- if (Compare.isCompare())
- reg = Compare.getOperand(0).getReg();
- else if (isLoadAndTestAsCmp(Compare))
- reg = Compare.getOperand(1).getReg();
- assert(reg);
-
- return reg;
-}
-
// Compare compares the result of MI against zero. If MI is an addition
// of -1 and if CCUsers is a single branch on nonzero, eliminate the addition
// and convert the branch to a BRCT(G) or BRCTH. Return true on success.
@@ -207,7 +183,7 @@ bool SystemZElimCompare::convertToBRCT(
// We already know that there are no references to the register between
// MI and Compare. Make sure that there are also no references between
// Compare and Branch.
- unsigned SrcReg = getCompareSourceReg(Compare);
+ unsigned SrcReg = TII->getCompareSourceReg(Compare);
MachineBasicBlock::iterator MBBI = Compare, MBBE = Branch;
for (++MBBI; MBBI != MBBE; ++MBBI)
if (getRegReferences(*MBBI, SrcReg))
@@ -254,7 +230,7 @@ bool SystemZElimCompare::convertToLoadAndTrap(
// We already know that there are no references to the register between
// MI and Compare. Make sure that there are also no references between
// Compare and Branch.
- unsigned SrcReg = getCompareSourceReg(Compare);
+ unsigned SrcReg = TII->getCompareSourceReg(Compare);
MachineBasicBlock::iterator MBBI = Compare, MBBE = Branch;
for (++MBBI; MBBI != MBBE; ++MBBI)
if (getRegReferences(*MBBI, SrcReg))
@@ -495,25 +471,17 @@ bool SystemZElimCompare::adjustCCMasksForInstr(
return true;
}
-// Return true if Compare is a comparison against zero.
-static bool isCompareZero(MachineInstr &Compare) {
- if (isLoadAndTestAsCmp(Compare))
- return true;
- return Compare.getNumExplicitOperands() == 2 &&
- Compare.getOperand(1).isImm() && Compare.getOperand(1).getImm() == 0;
-}
-
// Try to optimize cases where comparison instruction Compare is testing
// a value against zero. Return true on success and if Compare should be
// deleted as dead. CCUsers is the list of instructions that use the CC
// value produced by Compare.
bool SystemZElimCompare::optimizeCompareZero(
MachineInstr &Compare, SmallVectorImpl<MachineInstr *> &CCUsers) {
- if (!isCompareZero(Compare))
+ if (!TII->isCompareZero(Compare))
return false;
// Search back for CC results that are based on the first operand.
- unsigned SrcReg = getCompareSourceReg(Compare);
+ unsigned SrcReg = TII->getCompareSourceReg(Compare);
MachineBasicBlock &MBB = *Compare.getParent();
Reference CCRefs;
Reference SrcRefs;
@@ -702,7 +670,7 @@ bool SystemZElimCompare::processBlock(MachineBasicBlock &MBB) {
MachineBasicBlock::iterator MBBI = MBB.end();
while (MBBI != MBB.begin()) {
MachineInstr &MI = *--MBBI;
- if (CompleteCCUsers && (MI.isCompare() || isLoadAndTestAsCmp(MI)) &&
+ if (CompleteCCUsers && (MI.isCompare() || TII->isLoadAndTestAsCmp(MI)) &&
(optimizeCompareZero(MI, CCUsers) ||
fuseCompareOperations(MI, CCUsers))) {
++MBBI;
diff --git a/llvm/lib/Target/SystemZ/SystemZInstrInfo.cpp b/llvm/lib/Target/SystemZ/SystemZInstrInfo.cpp
index 91a4aa9c73010..54a2adcc46198 100644
--- a/llvm/lib/Target/SystemZ/SystemZInstrInfo.cpp
+++ b/llvm/lib/Target/SystemZ/SystemZInstrInfo.cpp
@@ -2144,6 +2144,34 @@ unsigned SystemZInstrInfo::getFusedCompare(unsigned Opcode,
return 0;
}
+bool SystemZInstrInfo::isLoadAndTestAsCmp(const MachineInstr &MI) const {
+ // If we during isel used a load-and-test as a compare with 0, the
+ // def operand is dead.
+ return (MI.getOpcode() == SystemZ::LTEBR ||
+ MI.getOpcode() == SystemZ::LTDBR ||
+ MI.getOpcode() == SystemZ::LTXBR) &&
+ MI.getOperand(0).isDead();
+}
+
+bool SystemZInstrInfo::isCompareZero(const MachineInstr &Compare) const {
+ if (isLoadAndTestAsCmp(Compare))
+ return true;
+ return Compare.isCompare() && Compare.getNumExplicitOperands() == 2 &&
+ Compare.getOperand(1).isImm() && Compare.getOperand(1).getImm() == 0;
+}
+
+unsigned SystemZInstrInfo::
+getCompareSourceReg(const MachineInstr &Compare) const {
+ unsigned reg = 0;
+ if (Compare.isCompare())
+ reg = Compare.getOperand(0).getReg();
+ else if (isLoadAndTestAsCmp(Compare))
+ reg = Compare.getOperand(1).getReg();
+ assert(reg);
+
+ return reg;
+}
+
bool SystemZInstrInfo::
prepareCompareSwapOperands(MachineBasicBlock::iterator const MBBI) const {
assert(MBBI->isCompare() && MBBI->getOperand(0).isReg() &&
diff --git a/llvm/lib/Target/SystemZ/SystemZInstrInfo.h b/llvm/lib/Target/SystemZ/SystemZInstrInfo.h
index 8b82af61e669a..2030d52becc0e 100644
--- a/llvm/lib/Target/SystemZ/SystemZInstrInfo.h
+++ b/llvm/lib/Target/SystemZ/SystemZInstrInfo.h
@@ -356,6 +356,17 @@ class SystemZInstrInfo : public SystemZGenInstrInfo {
SystemZII::FusedCompareType Type,
const MachineInstr *MI = nullptr) const;
+ // Return true if this is a load and test which can be optimized the
+ // same way as compare instruction.
+ bool isLoadAndTestAsCmp(const MachineInstr &MI) const;
+
+ // Return true if Compare is a comparison against zero.
+ bool isCompareZero(const MachineInstr &Compare) const;
+
+ // Return the source register of Compare, which is the unknown value
+ // being tested.
+ unsigned getCompareSourceReg(const MachineInstr &Compare) const;
+
// Try to find all CC users of the compare instruction (MBBI) and update
// all of them to maintain equivalent behavior after swapping the compare
// operands. Return false if not all users can be conclusively found and
diff --git a/llvm/lib/Target/SystemZ/SystemZMachineScheduler.cpp b/llvm/lib/Target/SystemZ/SystemZMachineScheduler.cpp
index 5e2365f1dc513..85376ec70edc5 100644
--- a/llvm/lib/Target/SystemZ/SystemZMachineScheduler.cpp
+++ b/llvm/lib/Target/SystemZ/SystemZMachineScheduler.cpp
@@ -5,22 +5,421 @@
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
-//
-// -------------------------- Post RA scheduling ---------------------------- //
-// SystemZPostRASchedStrategy is a scheduling strategy which is plugged into
-// the MachineScheduler. It has a sorted Available set of SUs and a pickNode()
-// implementation that looks to optimize decoder grouping and balance the
-// usage of processor resources. Scheduler states are saved for the end
-// region of each MBB, so that a successor block can learn from it.
-//===----------------------------------------------------------------------===//
#include "SystemZMachineScheduler.h"
+#include "llvm/CodeGen/LiveInterval.h"
+#include "llvm/CodeGen/LiveIntervals.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
using namespace llvm;
#define DEBUG_TYPE "machine-scheduler"
+/// Pre-RA scheduling ///
+
+static cl::opt<unsigned> TinyRegionLim(
+ "tiny-region-lim", cl::Hidden, cl::init(10),
+ cl::desc("Run limited pre-ra scheduling on regions of this size or "
+ "smaller. Mainly for testing."));
+
+static bool isRegDef(const MachineOperand &MO) {
+ return MO.isReg() && MO.isDef();
+}
+
+static bool isVirtRegDef(const MachineOperand &MO) {
+ return isRegDef(MO) && MO.getReg().isVirtual();
+}
+
+static bool isPhysRegDef(const MachineOperand &MO) {
+ return isRegDef(MO) && MO.getReg().isPhysical();
+}
+
+static bool isVirtRegUse(const MachineOperand &MO) {
+ return MO.isReg() && MO.isUse() && MO.readsReg() && MO.getReg().isVirtual();
+}
+
+void SystemZPreRASchedStrategy::initializePrioRegClasses(
+ const TargetRegisterInfo *TRI) {
+ for (const TargetRegisterClass *RC : TRI->regclasses()) {
+ for (MVT VT : MVT::fp_valuetypes())
+ if (TRI->isTypeLegalForClass(*RC, VT)) {
+ PrioRegClasses.insert(RC->getID());
+ break;
+ }
+
+ // On SystemZ vector and FP registers overlap: add any vector RC.
+ if (!PrioRegClasses.count(RC->getID()))
+ for (MVT VT : MVT::fp_fixedlen_vector_valuetypes())
+ if (TRI->isTypeLegalForClass(*RC, VT)) {
+ PrioRegClasses.insert(RC->getID());
+ break;
+ }
+ }
+}
+
+void SystemZPreRASchedStrategy::VRegSet::dump(std::string Msg) {
+ dbgs() << Msg.c_str();
+ bool First = true;
+ for (auto R : *this) {
+ if (!First)
+ dbgs() << ", ";
+ else
+ First = false;
+ dbgs() << "%" << R.virtRegIndex();
+ }
+ dbgs() << "\n";
+}
+
+unsigned SystemZPreRASchedStrategy::getRemLat(SchedBoundary *Zone) const {
+ if (RemLat == ~0U)
+ RemLat = computeRemLatency(*Zone);
+ return RemLat;
+}
+
+void SystemZPreRASchedStrategy::initializeStoresGroup() {
+ StoresGroup.clear();
+ FirstStoreInGroupScheduled = false;
+
+ unsigned CurrMaxDepth = 0;
+ for (unsigned Idx = DAG->SUnits.size() - 1; Idx + 1 != 0; --Idx) {
+ const SUnit *SU = &DAG->SUnits[Idx];
+ const MachineInstr *MI = SU->getInstr();
+ if (!MI->getNumOperands() || MI->isCopy())
+ continue;
+
+ bool HasVirtDef = false;
+ bool HasVirtUse = false;
+ for (unsigned I = 0; I < MI->getDesc().getNumOperands(); ++I) {
+ const MachineOperand &MO = MI->getOperand(I);
+ if (isVirtRegDef(MO) && !MO.isDead())
+ HasVirtDef = true;
+ else if (isVirtRegUse(MO) &&
+ MI->getDesc().operands()[I].OperandType != MCOI::OPERAND_MEMORY)
+ HasVirtUse = true;
+ }
+ bool IsStore = !HasVirtDef && HasVirtUse;
+
+ // Find a group of stores that all are at the bottom while avoiding
+ // regions with any additional group of lesser depth.
+ if (SU->getDepth() > CurrMaxDepth) {
+ CurrMaxDepth = SU->getDepth();
+ bool PrevGroup = StoresGroup.size() > 1;
+ StoresGroup.clear();
+ if (PrevGroup)
+ return;
+ if (IsStore)
+ StoresGroup.insert(SU);
+ }
+ else if (IsStore && !StoresGroup.empty() && SU->getDepth() == CurrMaxDepth) {
+ // The group members should all have the same opcode.
+ if ((*StoresGroup.begin())->getInstr()->getOpcode() != MI->getOpcode()) {
+ StoresGroup.clear();
+ return;
+ }
+ StoresGroup.insert(SU);
+ }
+ }
+
+ // Value of 8 handles a known regression (with group of 20).
+ // TODO: Would some other value be better?
+ if (StoresGroup.size() < 8)
+ StoresGroup.clear();
+}
+
+static int biasPhysRegExtra(const SUnit *SU) {
+ if (int Res = biasPhysReg(SU, /*isTop=*/false))
+ return Res;
+
+ // Also recognize Load Address of stack slot. There are (at least
+ // currently) no instructions here defining a physreg that uses a vreg.
+ const MachineInstr *MI = SU->getInstr();
+ if (MI->getNumOperands() && !MI->isCopy()) {
+ const MachineOperand &DefMO = MI->getOperand(0);
+ if (isPhysRegDef(DefMO))
+ return 1;
+ }
+
+ return 0;
+}
+
+int SystemZPreRASchedStrategy::
+computeSULivenessScore(SchedCandidate &C, ScheduleDAGMILive *DAG,
+ SchedBoundary *Zone) const {
+ // Not all data deps are modelled around the SUnit - some data edges near
+ // boundaries are missing: Look directly at the MI operands instead.
+ const SUnit *SU = C.SU;
+ const MachineInstr *MI = SU->getInstr();
+ if (!MI->getNumOperands() || MI->isCopy())
+ return 0;
+
+ // Find uses of registers that are not already live (kills).
+ bool PrioKill = false;
+ bool GPRKill = false;
+ bool AddrKill = false;
+ bool HasPrioUse = false;
+ for (unsigned I = 0; I < MI->getDesc().getNumOperands(); ++I) {
+ const MachineOperand &MO = MI->getOperand(I);
+ if (!isVirtRegUse(MO))
+ continue;
+ HasPrioUse |= isPrioVirtReg(MO.getReg(), &DAG->MRI);
+ if (LiveRegs.count(MO.getReg()))
+ continue;
+ if (isPrioVirtReg(MO.getReg(), &DAG->MRI))
+ PrioKill = true;
+ else if (MI->getDesc().operands()[I].OperandType != MCOI::OPERAND_MEMORY)
+ GPRKill = true;
+ else
+ AddrKill = true;
+ }
+
+ // Find the interesting properties.
+ const MachineOperand &DefMO = MI->getOperand(0);
+ assert(!isPhysRegDef(DefMO) && "Did not expect physreg def!");
+ bool IsLoad =
+ isRegDef(DefMO) && !DefMO.isDead() && !IsRedefining[SU->NodeNum];
+ bool IsStore = (!isRegDef(DefMO) || DefMO.isDead());
+ // Prioritize FP: Ignore GPR/Addr kills with an FP def.
+ bool UsesLivePrio =
+ IsLoad && !PrioKill &&
+ (isPrioVirtReg(DefMO.getReg(), &DAG->MRI) || (!GPRKill && !AddrKill));
+ bool UsesLiveAll = !PrioKill && !GPRKill && !AddrKill;
+ bool PreservesSchedLat = SU->getHeight() <= Zone->getScheduledLatency();
+ const unsigned Cycles = 2;
+ unsigned Margin = SchedModel->getIssueWidth() * (Cycles + SU->Latency - 1);
+ bool HasDistToTop = NumLeft > Margin;
+
+ // Pull down a defining SU if it preserves the scheduled latency while not
+ // causing any (prioritized) register uses to become live. If however there
+ // will be relatively many SUs scheduled above this one and all uses are
+ // already live it should not be a problem to increase the scheduled
+ // latency given the OOO execution.
+ // TODO: Try schedulling small (DFSResult) subtrees as a unit.
+ bool SchedLow = IsLoad && ((PreservesSchedLat && UsesLivePrio) ||
+ (HasDistToTop && UsesLiveAll));
+
+ // This handles regions with many chained stores of the same depth at the
+ // bottom in the input order (cactus). Push them upwards during scheduling.
+ bool SchedHigh = IsStore && FirstStoreInGroupScheduled &&
+ StoresGroup.count(SU) &&
+ (PrioKill || (!HasPrioUse && GPRKill));
+
+ if (SchedLow)
+ return -1;
+ if (SchedHigh)
+ return 1;
+ return 0;
+}
+
+bool SystemZPreRASchedStrategy::tryCandidate(SchedCandidate &Cand,
+ SchedCandidate &TryCand,
+ SchedBoundary *Zone) const {
+ assert(Zone && !Zone->isTop() && "Bottom-Up scheduling only.");
+
+ // Initialize the candidate if needed.
+ if (!Cand.isValid()) {
+ TryCand.Reason = FirstValid;
+ return true;
+ }
+
+ // Bias physreg defs and copies to their uses and definitions respectively.
+ int TryCandPRegBias = biasPhysRegExtra(TryCand.SU);
+ int CandPRegBias = biasPhysRegExtra(Cand.SU);
+ if (tryGreater(TryCandPRegBias, CandPRegBias, TryCand, Cand, PhysReg))
+ return TryCand.Reason != NoCand;
+ if (TryCandPRegBias && CandPRegBias) {
+ // Both biased same way.
+ tryGreater(TryCand.SU->NodeNum, Cand.SU->NodeNum, TryCand, Cand, NodeOrder);
+ return TryCand.Reason != NoCand;
+ }
+
+ if (TinyRegion) {
+ // Prioritize instructions that read unbuffered resources by stall cycles.
+ // TODO: Try this in bigger regions as well.
+ if (tryLess(Zone->getLatencyStallCycles(TryCand.SU),
+ Zone->getLatencyStallCycles(Cand.SU), TryCand, Cand, Stall))
+ return TryCand.Reason != NoCand;
+ } else {
+ // Look for an opportunity to reduce register liveness.
+ int TryCandScore = computeSULivenessScore(TryCand, DAG, Zone);
+ int CandScore = computeSULivenessScore(Cand, DAG, Zone);
+ if (tryLess(TryCandScore, CandScore, TryCand, Cand, LivenessReduce))
+ return TryCand.Reason != NoCand;
+
+ // Don't extend the scheduled latency.
+ if (ShouldReduceLatency && TryC...
[truncated]
|
You can test this locally with the following command:git-clang-format --diff origin/main HEAD --extensions cpp,h -- llvm/include/llvm/CodeGen/MachineScheduler.h llvm/include/llvm/CodeGen/RegisterPressure.h llvm/lib/CodeGen/MachineScheduler.cpp llvm/lib/Target/SystemZ/SystemZMachineScheduler.cpp llvm/lib/Target/SystemZ/SystemZMachineScheduler.h llvm/lib/Target/SystemZ/SystemZTargetMachine.cpp llvm/lib/Target/SystemZ/SystemZTargetMachine.h
View the diff from clang-format here.diff --git a/llvm/lib/Target/SystemZ/SystemZMachineScheduler.cpp b/llvm/lib/Target/SystemZ/SystemZMachineScheduler.cpp
index cef7f2e17..e6ade21c2 100644
--- a/llvm/lib/Target/SystemZ/SystemZMachineScheduler.cpp
+++ b/llvm/lib/Target/SystemZ/SystemZMachineScheduler.cpp
@@ -191,8 +191,8 @@ int SystemZPreRASchedStrategy::computeSULivenessScore(
UsesLive = (PrioDefNoKill || (!PrioPressureChange && GPRDefNoKill));
}
- bool IsKillingStore = isStoreOfVReg(MI) &&
- !DAG->getBotRPTracker().isRegLive(MO0.getReg());
+ bool IsKillingStore =
+ isStoreOfVReg(MI) && !DAG->getBotRPTracker().isRegLive(MO0.getReg());
// Pull down a defining SU if it preserves the scheduled latency while not
// causing any (vector) registers to become live. It should also be ok if
@@ -202,8 +202,8 @@ int SystemZPreRASchedStrategy::computeSULivenessScore(
// This handles regions with many chained stores of the same depth at the
// bottom in the input order (cactus). Push them upwards during scheduling.
- bool SchedHigh = IsKillingStore && FirstStoreInGroupScheduled &&
- StoresGroup.count(SU);
+ bool SchedHigh =
+ IsKillingStore && FirstStoreInGroupScheduled && StoresGroup.count(SU);
if (SchedLow)
return -1;
@@ -250,10 +250,11 @@ bool SystemZPreRASchedStrategy::tryCandidate(SchedCandidate &Cand,
TryCand.SU->getHeight() != Cand.SU->getHeight() &&
(std::max(TryCand.SU->getHeight(), Cand.SU->getHeight()) >
Zone->getScheduledLatency())) {
- // Put the higher SU above only if its depth is less than what's remaining.
+ // Put the higher SU above only if its depth is less than what's
+ // remaining.
unsigned HigherSUDepth = TryCand.SU->getHeight() < Cand.SU->getHeight()
- ? Cand.SU->getDepth()
- : TryCand.SU->getDepth();
+ ? Cand.SU->getDepth()
+ : TryCand.SU->getDepth();
if (HigherSUDepth != getRemLat(Zone) &&
tryLess(TryCand.SU->getHeight(), Cand.SU->getHeight(), TryCand, Cand,
GenericSchedulerBase::BotHeightReduce)) {
|
|
@preames @wangpc-pp @michaelmaitland @arsenm @asb Any comments welcome. |
|
Note: |
| @@ -0,0 +1,200 @@ | |||
| # RUN: llc -o - %s -mtriple=s390x-linux-gnu -mcpu=z196 -verify-machineinstrs \ | |||
There was a problem hiding this comment.
Pre-commit these new tests so that we can see the effect of new scheduling strategy.
That's a good question... Maybe it is doing too little too late - it waits for certain limits to be reached but then it has already opened up many register intervals and for some reason it isn't enough to try to reduce register pressure at that point. It seems to work better to reduce liveness regardless of the current pressure, that is as soon as possible. I am not sure if the PSets themselves are overly complex and get in the way of things: On SystemZ, the simple approach I am using is to consider the fact of basically two sets of registers available: FP regs (which overlap the vector regs), and the GPR regs. The idea is to reduce FP pressure as much as possible by ignoring GPR regs in FP intensive regions. I see 5 PSets on SystemZ, but I am not sure that works the same as having just two, but ideally it should. Prioritizing FP regs seems to work well, and is maybe an important difference to the GenericScheduler. Another difference is that it seems to work better not to consider memory operands (GPR registers used to hold addresses), as they are not naturally part of the data flow. This is something PSets don't know about - how the register is actually used. But I don't think that is a major point in all this. I have also seen the handling of critical PSets go wrong with a large region which is very FP intensive. In the input order, it is the integer sets that have the most pressure, but there is a lot of potential FP overlap which results after scheduling (with increased heavy spilling). I tried fixing this however by providing the correct critical PSets, but it did not help much on that test case. Another option I haven't tried (suggested by @atrick, I think) is to have a second pass which could among other things maybe correct this if it goes wrong. This I haven't tried however. |
|
A patch with scripts that I have been working with as a tool for developing this strategy can be found here: #136483. @atrick Any comments from you (and others ofc) would be very welcome before committing this. Are there any "no-no":s in this strategy - for instance related to compile time? This strategy is now at a good point, but that doesn't mean that things can get |
|
@uweigand regarding compile time (per pass as reported by -ftime-report):
So far no compile time explosions seen. One speedup that might be worth trying (in initialize()) would be to find the live-in regs by testing regs touched in the region only (as opposed to testing all of them). But since there are no known cases of this being significantly slow, maybe that can wait, or? |
JonPsson1
force-pushed
the
misched_final
branch
from
631adc9 to
5f9a41f
Compare
|
@arsenm Thanks for review - patch updated accordingly. |
|
ping - any thoughts / objections before committing this? |
JonPsson1
force-pushed
the
misched_final
branch
from
5f9a41f to
f29d449
Compare
|
Rebase. |
|
I have made some progress around the reuse of existing common-code instead of using the LiveReg set I added:
Pros/Cons (PDiff vs operands liveness): operands/registers liveness:
PDiffs:
|
|
Sorry -- I'm way out of the loop on register allocation and can't be any help here. |
|
Hi @JonPsson1, I've started looking into this and have a few high-level questions:
|
shouldReduceLatency() can give a decision before each picked SU based on the remaining critical path in the given moment. This is based on the current cycle and remaining latency. The HasDataSequences I implemented looks at a region before scheduling and then triggers latency reduction across the entire region - before each picked node. I have generally tried to move away from the cycle-based scheduling heuristics used by GenericScheduler as they mostly make exact sense for an in-order target during pre-RA scheduling, I'd say. I could however not really make the argument for one or the other except by trying it out, which I did: First, I examined how many times in SystemZPreRASchedStrategy::tryCandidate() at the point of interest (below liveness reduction) these would yield "true": In other words, 4.8M times (note that this number includes all the iterations across the Available queue) would be "always true", barred the initial check to exclude some very "wide" DAGs. This is what was done before improving this recently. shouldReduceLatency() cuts that almost in half, while HasDataSequence is relatively rare. When I noticed a regression after returning to this project on lbm, I tried disabling this latency heuristic alltogether, and saw these results: The lbm problem went away, but other benchmarks suffered. After working with this and adding the (HasDataSequences || Rem.IsAcyclicLatencyLimited) guard (per the patch posted here currently), I see these numbers: Now, back to the experiment with shouldReduceLatency(). I tried two changes: using shouldReduceLatency() instead of HasDataSequences, or both combined like (HasDataSequences && shouldReduceLatency()). There is a slight (+2000 spills/reloads) increase in spilling with shouldReduceLatency(), which is sort of as expected. Performancewise, it seems to e.g. handle cactus equally well, but there are slight losses on two benchmarks: Given the results, it seems better to schedule more agressively for latency throughout the region than to do it per the cycle based critical path heuristic - if done only on the regions where this matters. I get some confidence in HasDataSequence as it gives better performance with a lot less involvement, and also better than the combination of the two. |
Final cleanup. MISched0, with -misched-gprloads. Simplified and refined. Remove previous versions. -tiny-region Disable pre-ra scheduling. Revert "Disable pre-ra scheduling." Try TinyRegion=10 without extra checks. Revert "Try TinyRegion=10 without extra checks." Try TinyRegion=10 with some exclusions. Tiny10Lat without chainpreds and hazard Was c0f4354
Add NumLiveReducePreRA/NumLiveReducePostRA statistics. Use new way of adding a target SchedStrategy. Update two SystemZ CodeGen tests.
This reverts commit ef587088f258c23121f2e013151733693bb76644.
Add tests for Pressure Diffs produced by buildSchedGraph().
Fix typo. clang-format.
…y when either there are many nodes in data-sequences, or when IsAcyclicLatencyLimited is true. - Remove the lengthy handling for tiny regions containing long latency instructions - it doesn't appear to be needed. - Slight refactoring of computeSULivenessScore() with PDiffs (NFC).
First of all, per the comment in RegisterPressure.cpp: "The register tracker is unaware of global liveness so ignores normal live-thru ranges...", there is (currently) no truly accurate awareness of the number of used / free registers. The OOO reasoning I am using to motivate e.g. pulling a VL down right before its user is that this shouldn't matter if there are many (30) instructions above the VL, in a big region ( I now made the experiment to try your idea, in two versions: The first one checks for 2 free regs, the second one for the pressure to be below half of the limit (it doesn't schedule the SU "low" if the register pressure is ok). If the current pressure was perfectly estimated, at least the second one should give no more spilling. I did get a few more spills/reloads with both versions: It doesn't seem to give much one way or the other performance-wise... (I also tried another version using the "2 regs rule" only in cases where latency reduction is not enabled, with similar mixed results). Both of these show f544.nab_r regressing. I tried this again on this benchmark, but only when latency reduction is not enabled and then the regression dissapeared. There were however only 5 more spill/reloads causing the 3.6% regression, so it's likely not a spilling problem, so not sure exactly what is the cause. I agree that this should in theory not hurt if done correctly, and maybe GenericScheduler would do better if it set up the global liveness also. At least it shouldn't have to cause a heavy increase in spilling given that it checks the pressure 'Excess' very early. Another problem in the GenericScheduler relating to this is however that RegPressureTracker:: getUpwardPressureDelta() that is used seems to just track one PressureSet that exceeds its limit. That means e.g. GRX32Bit could be tracked, but then VR16Bit ignored, IIUC. I think it would have to be able to check any Excess that the PressureDiff of an SU would affect. So with global liveness and better handling of pressure Excess it should do better, but then again it will not matter in many interesting cases where there will be Excess anyway where it will always be a matter of reducing it as much as possible. @atrick - have you tried this? @atrick has described the problem I saw in GenericScheduler as "backing itself into a corner". So the idea for me as been to not be so confident about the overall picture but rather do more as the opportunity arises. First reg-pressure as much as possible, and only after that latency reduction. For bigger regions (like in cactus), there will always be some spilling so in those cases it always makes sense to close the live range, and it seems to give good performance to do it under the given checks. |
JonPsson1
force-pushed
the
misched_final
branch
from
a863786 to
ff23871
Compare
|
Patch rebased.
|
|
Some minor fixes. It is all looking quite good now to me so the next step would be to decide on using PressureDiffs (or not). Given that the PressureDiffs give identical results, they make sense to me, I guess. I have now simplified SystemZPreRASchedStrategy::initializePressureSets() which should be ok, given that e.g. GCNSchedStrategy::pickNodeFromQueue() is hard-coding these sets by name. There is also a new SystemZ test for the PressureSets just in case they would change, coming from TableGen. |
- Rebase. - Tests updated and passing. Minor tweaks and fixes: - '-prera-lat-red' option for experiments with latency reduction. - Don't reduce latency with a wide DAG that is acyclically latency limited. - Simplify and factor out check for IsStore. - Disable IsRedefining[] with PressureDiffs. - Add check for vreg uses in biasPhysRegExtra() - NFC fix for ShouldTrackPressure init. - Remove lenghty code in initializePressureSets() - there is a test. - Remove changes in SystemZElimCompare as that is not used anymore.
JonPsson1
force-pushed
the
misched_final
branch
from
878e1bf to
8228743
Compare
Some experiments made with these, without any improvements seen.
This reverts commit 89d131e.
|
These are the latest real bencharking results, which show that this seems to have good impact on the spec-FP. |
This reverts commit c5ab432.
This reverts commit 2e545a3.
- The handling of FPd stalls for tiny regions still gives 1% on nab, but that isn't enough to motivate it. Wait with this until it works well on all regions. - Only apply one way of treating liveness of register uses in computeSULivenessScore(). What was previously UsesLiveAll is dropped and UsesLivePrio has become UsesLive.
|
Benchmark results of latest version ("Simplifications"): |
8 participants
As the heavy spilling in Cactus was found to be caused by the
MachineScheduler, it has been clear that there is room for improvement in
GenericScheduler. A first attempt was made with #90181, which however did not
materialize in anything actually useful.
This time, a SystemZ specific MachineSchedStrategy has been developed, guided
by experimentation and benchmarking.
Finding that GenericScheduler fails to handle liveness despite all the work
it is doing with PressureSets etc, I tried a simpler approach by keeping
track of live registers and scheduling e.g. a load immediately if it closed a
live range. If this is always done first, it then seems to work well to also
consider latencies as a second step. The final piece that makes it all work
well is the distinction of tiny regions, which remedies seen problems with
comparison elimination, phys-reg copys and even compile time. These regions
(with up to 10 instructions) are mainly left as they were.
SPEC Results (omitting <1% changes):
Compile time showed at first some heavy regressions that were due to a
large amount of LIS->getInterval() lookups in functions with many small
blocks (regions) and vregs. With the tiny regions handling however, this
problem went away and it seems to be now on par with GenericSched.
If needed there are likely things that could be sped up.