MachineScheduler: Allow independent scheduling of sub register defs
Note that this is disabled by default and still requires a patch to
handleMove() which is not upstreamed yet.
If the TrackLaneMasks policy/strategy is enabled the MachineScheduler
will build a schedule graph where definitions of independent
subregisters are no longer serialised.
Implementation comments:
- Without lane mask tracking a sub register def also counts as a use
(except for the first one with the read-undef flag set), with lane
mask tracking enabled this is no longer the case.
- Pressure Diffs where previously maintained per definition of a
vreg with the help of the SSA information contained in the
LiveIntervals. With lanemask tracking enabled we cannot do this
anymore and instead change the pressure diffs for all uses of the vreg
as it becomes live/dead. For this changed style to work correctly we
ignore uses of instructions that define the same register again: They
won't affect register pressure.
- With lanemask tracking we remove all read-undef flags from
sub register defs when building the graph and re-add them later when
all vreg lanes have become dead.
Differential Revision: http://reviews.llvm.org/D14969
llvm-svn: 258259
diff --git a/llvm/lib/CodeGen/MachineScheduler.cpp b/llvm/lib/CodeGen/MachineScheduler.cpp
index fa8e5ba..c266b74 100644
--- a/llvm/lib/CodeGen/MachineScheduler.cpp
+++ b/llvm/lib/CodeGen/MachineScheduler.cpp
@@ -869,13 +869,27 @@
SUPressureDiffs.clear();
ShouldTrackPressure = SchedImpl->shouldTrackPressure();
+ ShouldTrackLaneMasks = SchedImpl->shouldTrackLaneMasks();
+
+ if (ShouldTrackLaneMasks) {
+ if (!ShouldTrackPressure)
+ report_fatal_error("ShouldTrackLaneMasks requires ShouldTrackPressure");
+ // Dead subregister defs have no users and therefore no dependencies,
+ // moving them around may cause liveintervals to degrade into multiple
+ // components. Change independent components to have their own vreg to avoid
+ // this.
+ if (!DisconnectedComponentsRenamed)
+ LIS->renameDisconnectedComponents();
+ }
}
// Setup the register pressure trackers for the top scheduled top and bottom
// scheduled regions.
void ScheduleDAGMILive::initRegPressure() {
- TopRPTracker.init(&MF, RegClassInfo, LIS, BB, RegionBegin, false, false);
- BotRPTracker.init(&MF, RegClassInfo, LIS, BB, LiveRegionEnd, false, false);
+ TopRPTracker.init(&MF, RegClassInfo, LIS, BB, RegionBegin,
+ ShouldTrackLaneMasks, false);
+ BotRPTracker.init(&MF, RegClassInfo, LIS, BB, LiveRegionEnd,
+ ShouldTrackLaneMasks, false);
// Close the RPTracker to finalize live ins.
RPTracker.closeRegion();
@@ -972,46 +986,71 @@
void ScheduleDAGMILive::updatePressureDiffs(
ArrayRef<RegisterMaskPair> LiveUses) {
for (const RegisterMaskPair &P : LiveUses) {
- /// FIXME: Currently assuming single-use physregs.
unsigned Reg = P.RegUnit;
- assert(P.LaneMask != 0);
- DEBUG(dbgs() << " LiveReg: " << PrintVRegOrUnit(Reg, TRI) << "\n");
+ /// FIXME: Currently assuming single-use physregs.
if (!TRI->isVirtualRegister(Reg))
continue;
- // This may be called before CurrentBottom has been initialized. However,
- // BotRPTracker must have a valid position. We want the value live into the
- // instruction or live out of the block, so ask for the previous
- // instruction's live-out.
- const LiveInterval &LI = LIS->getInterval(Reg);
- VNInfo *VNI;
- MachineBasicBlock::const_iterator I =
- nextIfDebug(BotRPTracker.getPos(), BB->end());
- if (I == BB->end())
- VNI = LI.getVNInfoBefore(LIS->getMBBEndIdx(BB));
- else {
- LiveQueryResult LRQ = LI.Query(LIS->getInstructionIndex(I));
- VNI = LRQ.valueIn();
- }
- // RegisterPressureTracker guarantees that readsReg is true for LiveUses.
- assert(VNI && "No live value at use.");
- for (const VReg2SUnit &V2SU
- : make_range(VRegUses.find(Reg), VRegUses.end())) {
- SUnit *SU = V2SU.SU;
- // If this use comes before the reaching def, it cannot be a last use, so
- // descrease its pressure change.
- if (!SU->isScheduled && SU != &ExitSU) {
- LiveQueryResult LRQ
- = LI.Query(LIS->getInstructionIndex(SU->getInstr()));
- if (LRQ.valueIn() == VNI) {
- PressureDiff &PDiff = getPressureDiff(SU);
- PDiff.addPressureChange(Reg, true, &MRI);
- DEBUG(
- dbgs() << " UpdateRegP: SU(" << SU->NodeNum << ") "
- << *SU->getInstr();
- dbgs() << " to ";
- PDiff.dump(*TRI);
- );
+ if (ShouldTrackLaneMasks) {
+ // If the register has just become live then other uses won't change
+ // this fact anymore => decrement pressure.
+ // If the register has just become dead then other uses make it come
+ // back to life => increment pressure.
+ bool Decrement = P.LaneMask != 0;
+
+ for (const VReg2SUnit &V2SU
+ : make_range(VRegUses.find(Reg), VRegUses.end())) {
+ SUnit &SU = *V2SU.SU;
+ if (SU.isScheduled || &SU == &ExitSU)
+ continue;
+
+ PressureDiff &PDiff = getPressureDiff(&SU);
+ PDiff.addPressureChange(Reg, Decrement, &MRI);
+ DEBUG(
+ dbgs() << " UpdateRegP: SU(" << SU.NodeNum << ") "
+ << PrintReg(Reg, TRI) << ':' << PrintLaneMask(P.LaneMask)
+ << ' ' << *SU.getInstr();
+ dbgs() << " to ";
+ PDiff.dump(*TRI);
+ );
+ }
+ } else {
+ assert(P.LaneMask != 0);
+ DEBUG(dbgs() << " LiveReg: " << PrintVRegOrUnit(Reg, TRI) << "\n");
+ // This may be called before CurrentBottom has been initialized. However,
+ // BotRPTracker must have a valid position. We want the value live into the
+ // instruction or live out of the block, so ask for the previous
+ // instruction's live-out.
+ const LiveInterval &LI = LIS->getInterval(Reg);
+ VNInfo *VNI;
+ MachineBasicBlock::const_iterator I =
+ nextIfDebug(BotRPTracker.getPos(), BB->end());
+ if (I == BB->end())
+ VNI = LI.getVNInfoBefore(LIS->getMBBEndIdx(BB));
+ else {
+ LiveQueryResult LRQ = LI.Query(LIS->getInstructionIndex(I));
+ VNI = LRQ.valueIn();
+ }
+ // RegisterPressureTracker guarantees that readsReg is true for LiveUses.
+ assert(VNI && "No live value at use.");
+ for (const VReg2SUnit &V2SU
+ : make_range(VRegUses.find(Reg), VRegUses.end())) {
+ SUnit *SU = V2SU.SU;
+ // If this use comes before the reaching def, it cannot be a last use,
+ // so decrease its pressure change.
+ if (!SU->isScheduled && SU != &ExitSU) {
+ LiveQueryResult LRQ
+ = LI.Query(LIS->getInstructionIndex(SU->getInstr()));
+ if (LRQ.valueIn() == VNI) {
+ PressureDiff &PDiff = getPressureDiff(SU);
+ PDiff.addPressureChange(Reg, true, &MRI);
+ DEBUG(
+ dbgs() << " UpdateRegP: SU(" << SU->NodeNum << ") "
+ << *SU->getInstr();
+ dbgs() << " to ";
+ PDiff.dump(*TRI);
+ );
+ }
}
}
}
@@ -1113,14 +1152,14 @@
// Initialize the register pressure tracker used by buildSchedGraph.
RPTracker.init(&MF, RegClassInfo, LIS, BB, LiveRegionEnd,
- false, /*TrackUntiedDefs=*/true);
+ ShouldTrackLaneMasks, /*TrackUntiedDefs=*/true);
// Account for liveness generate by the region boundary.
if (LiveRegionEnd != RegionEnd)
RPTracker.recede();
// Build the DAG, and compute current register pressure.
- buildSchedGraph(AA, &RPTracker, &SUPressureDiffs);
+ buildSchedGraph(AA, &RPTracker, &SUPressureDiffs, LIS, ShouldTrackLaneMasks);
// Initialize top/bottom trackers after computing region pressure.
initRegPressure();
@@ -1239,7 +1278,18 @@
if (ShouldTrackPressure) {
// Update top scheduled pressure.
- TopRPTracker.advance();
+ RegisterOperands RegOpers;
+ RegOpers.collect(*MI, *TRI, MRI, ShouldTrackLaneMasks, false);
+ if (ShouldTrackLaneMasks) {
+ // Adjust liveness and add missing dead+read-undef flags.
+ SlotIndex SlotIdx = LIS->getInstructionIndex(MI).getRegSlot();
+ RegOpers.adjustLaneLiveness(*LIS, MRI, SlotIdx, MI);
+ } else {
+ // Adjust for missing dead-def flags.
+ RegOpers.detectDeadDefs(*MI, *LIS);
+ }
+
+ TopRPTracker.advance(RegOpers);
assert(TopRPTracker.getPos() == CurrentTop && "out of sync");
DEBUG(
dbgs() << "Top Pressure:\n";
@@ -1264,9 +1314,20 @@
CurrentBottom = MI;
}
if (ShouldTrackPressure) {
- // Update bottom scheduled pressure.
+ RegisterOperands RegOpers;
+ RegOpers.collect(*MI, *TRI, MRI, ShouldTrackLaneMasks, false);
+ if (ShouldTrackLaneMasks) {
+ // Adjust liveness and add missing dead+read-undef flags.
+ SlotIndex SlotIdx = LIS->getInstructionIndex(MI).getRegSlot();
+ RegOpers.adjustLaneLiveness(*LIS, MRI, SlotIdx, MI);
+ } else {
+ // Adjust for missing dead-def flags.
+ RegOpers.detectDeadDefs(*MI, *LIS);
+ }
+
+ BotRPTracker.recedeSkipDebugValues();
SmallVector<RegisterMaskPair, 8> LiveUses;
- BotRPTracker.recede(&LiveUses);
+ BotRPTracker.recede(RegOpers, &LiveUses);
assert(BotRPTracker.getPos() == CurrentBottom && "out of sync");
DEBUG(
dbgs() << "Bottom Pressure:\n";
diff --git a/llvm/lib/CodeGen/RegisterPressure.cpp b/llvm/lib/CodeGen/RegisterPressure.cpp
index 78a766e..8097926 100644
--- a/llvm/lib/CodeGen/RegisterPressure.cpp
+++ b/llvm/lib/CodeGen/RegisterPressure.cpp
@@ -352,6 +352,19 @@
}
}
+static void setRegZero(SmallVectorImpl<RegisterMaskPair> &RegUnits,
+ unsigned RegUnit) {
+ auto I = std::find_if(RegUnits.begin(), RegUnits.end(),
+ [RegUnit](const RegisterMaskPair Other) {
+ return Other.RegUnit == RegUnit;
+ });
+ if (I == RegUnits.end()) {
+ RegUnits.push_back(RegisterMaskPair(RegUnit, 0));
+ } else {
+ I->LaneMask = 0;
+ }
+}
+
static void removeRegLanes(SmallVectorImpl<RegisterMaskPair> &RegUnits,
RegisterMaskPair Pair) {
unsigned RegUnit = Pair.RegUnit;
@@ -510,7 +523,8 @@
void RegisterOperands::adjustLaneLiveness(const LiveIntervals &LIS,
const MachineRegisterInfo &MRI,
- SlotIndex Pos) {
+ SlotIndex Pos,
+ MachineInstr *AddFlagsMI) {
for (auto I = Defs.begin(); I != Defs.end(); ) {
LaneBitmask LiveAfter = getLiveLanesAt(LIS, MRI, true, I->RegUnit,
Pos.getDeadSlot());
@@ -519,10 +533,20 @@
if (DeadDef != 0)
addRegLanes(DeadDefs, RegisterMaskPair(I->RegUnit, DeadDef));
#endif
+ // If the the def is all that is live after the instruction, then in case
+ // of a subregister def we need a read-undef flag.
+ unsigned RegUnit = I->RegUnit;
+ if (TargetRegisterInfo::isVirtualRegister(RegUnit) &&
+ AddFlagsMI != nullptr && (LiveAfter & ~I->LaneMask) == 0)
+ AddFlagsMI->setRegisterDefReadUndef(RegUnit);
+
unsigned LaneMask = I->LaneMask & LiveAfter;
- if (LaneMask == 0)
+ if (LaneMask == 0) {
I = Defs.erase(I);
- else {
+ // Make sure the operand is properly marked as Dead.
+ if (AddFlagsMI != nullptr)
+ AddFlagsMI->addRegisterDead(RegUnit, MRI.getTargetRegisterInfo());
+ } else {
I->LaneMask = LaneMask;
++I;
}
@@ -538,6 +562,15 @@
++I;
}
}
+ if (AddFlagsMI != nullptr) {
+ for (const RegisterMaskPair &P : DeadDefs) {
+ unsigned RegUnit = P.RegUnit;
+ LaneBitmask LiveAfter = getLiveLanesAt(LIS, MRI, true, RegUnit,
+ Pos.getDeadSlot());
+ if (LiveAfter == 0)
+ AddFlagsMI->setRegisterDefReadUndef(RegUnit);
+ }
+ }
}
/// Initialize an array of N PressureDiffs.
@@ -684,6 +717,13 @@
PreviousMask = LiveOut;
}
+ if (NewMask == 0) {
+ // Add a 0 entry to LiveUses as a marker that the complete vreg has become
+ // dead.
+ if (TrackLaneMasks && LiveUses != nullptr)
+ setRegZero(*LiveUses, Reg);
+ }
+
decreaseRegPressure(Reg, PreviousMask, NewMask);
}
@@ -703,8 +743,22 @@
// Did the register just become live?
if (PreviousMask == 0) {
if (LiveUses != nullptr) {
- unsigned NewLanes = NewMask & ~PreviousMask;
- addRegLanes(*LiveUses, RegisterMaskPair(Reg, NewLanes));
+ if (!TrackLaneMasks) {
+ addRegLanes(*LiveUses, RegisterMaskPair(Reg, NewMask));
+ } else {
+ auto I = std::find_if(LiveUses->begin(), LiveUses->end(),
+ [Reg](const RegisterMaskPair Other) {
+ return Other.RegUnit == Reg;
+ });
+ bool IsRedef = I != LiveUses->end();
+ if (IsRedef) {
+ // ignore re-defs here...
+ assert(I->LaneMask == 0);
+ removeRegLanes(*LiveUses, RegisterMaskPair(Reg, NewMask));
+ } else {
+ addRegLanes(*LiveUses, RegisterMaskPair(Reg, NewMask));
+ }
+ }
}
// Discover live outs if this may be the first occurance of this register.
@@ -764,9 +818,8 @@
}
/// Advance across the current instruction.
-void RegPressureTracker::advance() {
+void RegPressureTracker::advance(const RegisterOperands &RegOpers) {
assert(!TrackUntiedDefs && "unsupported mode");
-
assert(CurrPos != MBB->end());
if (!isTopClosed())
closeTop();
@@ -783,11 +836,6 @@
static_cast<RegionPressure&>(P).openBottom(CurrPos);
}
- RegisterOperands RegOpers;
- RegOpers.collect(*CurrPos, *TRI, *MRI, TrackLaneMasks, false);
- if (TrackLaneMasks)
- RegOpers.adjustLaneLiveness(*LIS, *MRI, SlotIdx);
-
for (const RegisterMaskPair &Use : RegOpers.Uses) {
unsigned Reg = Use.RegUnit;
LaneBitmask LiveMask = LiveRegs.contains(Reg);
@@ -821,6 +869,17 @@
while (CurrPos != MBB->end() && CurrPos->isDebugValue());
}
+void RegPressureTracker::advance() {
+ const MachineInstr &MI = *CurrPos;
+ RegisterOperands RegOpers;
+ RegOpers.collect(MI, *TRI, *MRI, TrackLaneMasks, false);
+ if (TrackLaneMasks) {
+ SlotIndex SlotIdx = getCurrSlot();
+ RegOpers.adjustLaneLiveness(*LIS, *MRI, SlotIdx);
+ }
+ advance(RegOpers);
+}
+
/// Find the max change in excess pressure across all sets.
static void computeExcessPressureDelta(ArrayRef<unsigned> OldPressureVec,
ArrayRef<unsigned> NewPressureVec,
diff --git a/llvm/lib/CodeGen/ScheduleDAGInstrs.cpp b/llvm/lib/CodeGen/ScheduleDAGInstrs.cpp
index 130b8a6..e0aeb57 100644
--- a/llvm/lib/CodeGen/ScheduleDAGInstrs.cpp
+++ b/llvm/lib/CodeGen/ScheduleDAGInstrs.cpp
@@ -19,6 +19,7 @@
#include "llvm/ADT/SmallSet.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/ValueTracking.h"
+#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
@@ -808,6 +809,19 @@
if (!TargetRegisterInfo::isVirtualRegister(Reg))
continue;
+ // Ignore re-defs.
+ if (TrackLaneMasks) {
+ bool FoundDef = false;
+ for (const MachineOperand &MO2 : MI->operands()) {
+ if (MO2.isReg() && MO2.isDef() && MO2.getReg() == Reg && !MO2.isDead()) {
+ FoundDef = true;
+ break;
+ }
+ }
+ if (FoundDef)
+ continue;
+ }
+
// Record this local VReg use.
VReg2SUnitMultiMap::iterator UI = VRegUses.find(Reg);
for (; UI != VRegUses.end(); ++UI) {
@@ -825,6 +839,7 @@
void ScheduleDAGInstrs::buildSchedGraph(AliasAnalysis *AA,
RegPressureTracker *RPTracker,
PressureDiffs *PDiffs,
+ LiveIntervals *LIS,
bool TrackLaneMasks) {
const TargetSubtargetInfo &ST = MF.getSubtarget();
bool UseAA = EnableAASchedMI.getNumOccurrences() > 0 ? EnableAASchedMI
@@ -900,6 +915,10 @@
RegisterOperands RegOpers;
RegOpers.collect(*MI, *TRI, MRI, TrackLaneMasks, false);
+ if (TrackLaneMasks) {
+ SlotIndex SlotIdx = LIS->getInstructionIndex(MI);
+ RegOpers.adjustLaneLiveness(*LIS, MRI, SlotIdx);
+ }
if (PDiffs != nullptr)
PDiffs->addInstruction(SU->NodeNum, RegOpers, MRI);