Index: llvm/trunk/include/llvm/CodeGen/MachineScheduler.h =================================================================== --- llvm/trunk/include/llvm/CodeGen/MachineScheduler.h +++ llvm/trunk/include/llvm/CodeGen/MachineScheduler.h @@ -150,6 +150,9 @@ struct MachineSchedPolicy { // Allow the scheduler to disable register pressure tracking. bool ShouldTrackPressure; + /// Track LaneMasks to allow reordering of independent subregister writes + /// of the same vreg. \sa MachineSchedStrategy::shouldTrackLaneMasks() + bool ShouldTrackLaneMasks; // Allow the scheduler to force top-down or bottom-up scheduling. If neither // is true, the scheduler runs in both directions and converges. @@ -160,8 +163,8 @@ // first. bool DisableLatencyHeuristic; - MachineSchedPolicy(): ShouldTrackPressure(false), OnlyTopDown(false), - OnlyBottomUp(false), DisableLatencyHeuristic(false) {} + MachineSchedPolicy(): ShouldTrackPressure(false), ShouldTrackLaneMasks(false), + OnlyTopDown(false), OnlyBottomUp(false), DisableLatencyHeuristic(false) {} }; /// MachineSchedStrategy - Interface to the scheduling algorithm used by @@ -185,6 +188,11 @@ /// initializing this strategy. Called after initPolicy. virtual bool shouldTrackPressure() const { return true; } + /// Returns true if lanemasks should be tracked. LaneMask tracking is + /// necessary to reorder independent subregister defs for the same vreg. + /// This has to be enabled in combination with shouldTrackPressure(). + virtual bool shouldTrackLaneMasks() const { return false; } + /// Initialize the strategy after building the DAG for a new region. virtual void initialize(ScheduleDAGMI *DAG) = 0; @@ -371,6 +379,7 @@ /// Register pressure in this region computed by initRegPressure. bool ShouldTrackPressure; + bool ShouldTrackLaneMasks; IntervalPressure RegPressure; RegPressureTracker RPTracker; @@ -387,13 +396,18 @@ IntervalPressure BotPressure; RegPressureTracker BotRPTracker; + /// True if disconnected subregister components are already renamed. + /// The renaming is only done on demand if lane masks are tracked. + bool DisconnectedComponentsRenamed; + public: ScheduleDAGMILive(MachineSchedContext *C, std::unique_ptr S) : ScheduleDAGMI(C, std::move(S), /*RemoveKillFlags=*/false), RegClassInfo(C->RegClassInfo), DFSResult(nullptr), - ShouldTrackPressure(false), RPTracker(RegPressure), - TopRPTracker(TopPressure), BotRPTracker(BotPressure) {} + ShouldTrackPressure(false), ShouldTrackLaneMasks(false), + RPTracker(RegPressure), TopRPTracker(TopPressure), + BotRPTracker(BotPressure), DisconnectedComponentsRenamed(false) {} ~ScheduleDAGMILive() override; @@ -874,6 +888,10 @@ return RegionPolicy.ShouldTrackPressure; } + bool shouldTrackLaneMasks() const override { + return RegionPolicy.ShouldTrackLaneMasks; + } + void initialize(ScheduleDAGMI *dag) override; SUnit *pickNode(bool &IsTopNode) override; Index: llvm/trunk/include/llvm/CodeGen/RegisterPressure.h =================================================================== --- llvm/trunk/include/llvm/CodeGen/RegisterPressure.h +++ llvm/trunk/include/llvm/CodeGen/RegisterPressure.h @@ -173,9 +173,11 @@ /// Use liveness information to find out which uses/defs are partially /// undefined/dead and adjust the RegisterMaskPairs accordingly. + /// If \p AddFlagsMI is given then missing read-undef and dead flags will be + /// added to the instruction. void adjustLaneLiveness(const LiveIntervals &LIS, - const MachineRegisterInfo &MRI, SlotIndex Pos); - + const MachineRegisterInfo &MRI, SlotIndex Pos, + MachineInstr *AddFlagsMI = nullptr); }; /// Array of PressureDiffs. @@ -420,6 +422,11 @@ /// Advance across the current instruction. void advance(); + /// Advance across the current instruction. + /// This is a "low-level" variant of advance() which takes precomputed + /// RegisterOperands of the instruction. + void advance(const RegisterOperands &RegOpers); + /// Finalize the region boundaries and recored live ins and live outs. void closeRegion(); Index: llvm/trunk/include/llvm/CodeGen/ScheduleDAGInstrs.h =================================================================== --- llvm/trunk/include/llvm/CodeGen/ScheduleDAGInstrs.h +++ llvm/trunk/include/llvm/CodeGen/ScheduleDAGInstrs.h @@ -214,6 +214,7 @@ void buildSchedGraph(AliasAnalysis *AA, RegPressureTracker *RPTracker = nullptr, PressureDiffs *PDiffs = nullptr, + LiveIntervals *LIS = nullptr, bool TrackLaneMasks = false); /// addSchedBarrierDeps - Add dependencies from instructions in the current Index: llvm/trunk/lib/CodeGen/MachineScheduler.cpp =================================================================== --- llvm/trunk/lib/CodeGen/MachineScheduler.cpp +++ llvm/trunk/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 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 LiveUses; - BotRPTracker.recede(&LiveUses); + BotRPTracker.recede(RegOpers, &LiveUses); assert(BotRPTracker.getPos() == CurrentBottom && "out of sync"); DEBUG( dbgs() << "Bottom Pressure:\n"; Index: llvm/trunk/lib/CodeGen/RegisterPressure.cpp =================================================================== --- llvm/trunk/lib/CodeGen/RegisterPressure.cpp +++ llvm/trunk/lib/CodeGen/RegisterPressure.cpp @@ -352,6 +352,19 @@ } } +static void setRegZero(SmallVectorImpl &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 &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(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 OldPressureVec, ArrayRef NewPressureVec, Index: llvm/trunk/lib/CodeGen/ScheduleDAGInstrs.cpp =================================================================== --- llvm/trunk/lib/CodeGen/ScheduleDAGInstrs.cpp +++ llvm/trunk/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);