//
//===----------------------------------------------------------------------===//
-#define DEBUG_TYPE "post-RA-sched"
#include "llvm/CodeGen/Passes.h"
#include "AggressiveAntiDepBreaker.h"
#include "AntiDepBreaker.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
-#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/RegisterClassInfo.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetLowering.h"
-#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/Target/TargetSubtargetInfo.h"
using namespace llvm;
+#define DEBUG_TYPE "post-RA-sched"
+
STATISTIC(NumNoops, "Number of noops inserted");
STATISTIC(NumStalls, "Number of pipeline stalls");
STATISTIC(NumFixedAnti, "Number of fixed anti-dependencies");
static char ID;
PostRAScheduler() : MachineFunctionPass(ID) {}
- void getAnalysisUsage(AnalysisUsage &AU) const {
+ void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.setPreservesCFG();
- AU.addRequired<AliasAnalysis>();
+ AU.addRequired<AAResultsWrapperPass>();
AU.addRequired<TargetPassConfig>();
AU.addRequired<MachineDominatorTree>();
AU.addPreserved<MachineDominatorTree>();
MachineFunctionPass::getAnalysisUsage(AU);
}
- bool runOnMachineFunction(MachineFunction &Fn);
+ bool runOnMachineFunction(MachineFunction &Fn) override;
+
+ bool enablePostRAScheduler(
+ const TargetSubtargetInfo &ST, CodeGenOpt::Level OptLevel,
+ TargetSubtargetInfo::AntiDepBreakMode &Mode,
+ TargetSubtargetInfo::RegClassVector &CriticalPathRCs) const;
};
char PostRAScheduler::ID = 0;
/// AA - AliasAnalysis for making memory reference queries.
AliasAnalysis *AA;
- /// LiveRegs - true if the register is live.
- BitVector LiveRegs;
-
/// The schedule. Null SUnit*'s represent noop instructions.
std::vector<SUnit*> Sequence;
public:
SchedulePostRATDList(
- MachineFunction &MF, MachineLoopInfo &MLI, MachineDominatorTree &MDT,
- AliasAnalysis *AA, const RegisterClassInfo&,
- TargetSubtargetInfo::AntiDepBreakMode AntiDepMode,
- SmallVectorImpl<const TargetRegisterClass*> &CriticalPathRCs);
+ MachineFunction &MF, MachineLoopInfo &MLI, AliasAnalysis *AA,
+ const RegisterClassInfo &,
+ TargetSubtargetInfo::AntiDepBreakMode AntiDepMode,
+ SmallVectorImpl<const TargetRegisterClass *> &CriticalPathRCs);
- ~SchedulePostRATDList();
+ ~SchedulePostRATDList() override;
/// startBlock - Initialize register live-range state for scheduling in
/// this block.
///
- void startBlock(MachineBasicBlock *BB);
+ void startBlock(MachineBasicBlock *BB) override;
// Set the index of RegionEnd within the current BB.
void setEndIndex(unsigned EndIdx) { EndIndex = EndIdx; }
/// Initialize the scheduler state for the next scheduling region.
- virtual void enterRegion(MachineBasicBlock *bb,
- MachineBasicBlock::iterator begin,
- MachineBasicBlock::iterator end,
- unsigned regioninstrs);
+ void enterRegion(MachineBasicBlock *bb,
+ MachineBasicBlock::iterator begin,
+ MachineBasicBlock::iterator end,
+ unsigned regioninstrs) override;
/// Notify that the scheduler has finished scheduling the current region.
- virtual void exitRegion();
+ void exitRegion() override;
/// Schedule - Schedule the instruction range using list scheduling.
///
- void schedule();
+ void schedule() override;
void EmitSchedule();
/// finishBlock - Clean up register live-range state.
///
- void finishBlock();
-
- /// FixupKills - Fix register kill flags that have been made
- /// invalid due to scheduling
- ///
- void FixupKills(MachineBasicBlock *MBB);
+ void finishBlock() override;
private:
void ReleaseSucc(SUnit *SU, SDep *SuccEdge);
void ReleaseSuccessors(SUnit *SU);
void ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle);
void ListScheduleTopDown();
- void StartBlockForKills(MachineBasicBlock *BB);
-
- // ToggleKillFlag - Toggle a register operand kill flag. Other
- // adjustments may be made to the instruction if necessary. Return
- // true if the operand has been deleted, false if not.
- bool ToggleKillFlag(MachineInstr *MI, MachineOperand &MO);
void dumpSchedule() const;
void emitNoop(unsigned CurCycle);
"Post RA top-down list latency scheduler", false, false)
SchedulePostRATDList::SchedulePostRATDList(
- MachineFunction &MF, MachineLoopInfo &MLI, MachineDominatorTree &MDT,
- AliasAnalysis *AA, const RegisterClassInfo &RCI,
- TargetSubtargetInfo::AntiDepBreakMode AntiDepMode,
- SmallVectorImpl<const TargetRegisterClass*> &CriticalPathRCs)
- : ScheduleDAGInstrs(MF, MLI, MDT, /*IsPostRA=*/true), AA(AA),
- LiveRegs(TRI->getNumRegs()), EndIndex(0)
-{
- const TargetMachine &TM = MF.getTarget();
- const InstrItineraryData *InstrItins = TM.getInstrItineraryData();
+ MachineFunction &MF, MachineLoopInfo &MLI, AliasAnalysis *AA,
+ const RegisterClassInfo &RCI,
+ TargetSubtargetInfo::AntiDepBreakMode AntiDepMode,
+ SmallVectorImpl<const TargetRegisterClass *> &CriticalPathRCs)
+ : ScheduleDAGInstrs(MF, &MLI), AA(AA), EndIndex(0) {
+
+ const InstrItineraryData *InstrItins =
+ MF.getSubtarget().getInstrItineraryData();
HazardRec =
- TM.getInstrInfo()->CreateTargetPostRAHazardRecognizer(InstrItins, this);
+ MF.getSubtarget().getInstrInfo()->CreateTargetPostRAHazardRecognizer(
+ InstrItins, this);
assert((AntiDepMode == TargetSubtargetInfo::ANTIDEP_NONE ||
MRI.tracksLiveness()) &&
((AntiDepMode == TargetSubtargetInfo::ANTIDEP_ALL) ?
(AntiDepBreaker *)new AggressiveAntiDepBreaker(MF, RCI, CriticalPathRCs) :
((AntiDepMode == TargetSubtargetInfo::ANTIDEP_CRITICAL) ?
- (AntiDepBreaker *)new CriticalAntiDepBreaker(MF, RCI) : NULL));
+ (AntiDepBreaker *)new CriticalAntiDepBreaker(MF, RCI) : nullptr));
}
SchedulePostRATDList::~SchedulePostRATDList() {
}
#endif
+bool PostRAScheduler::enablePostRAScheduler(
+ const TargetSubtargetInfo &ST,
+ CodeGenOpt::Level OptLevel,
+ TargetSubtargetInfo::AntiDepBreakMode &Mode,
+ TargetSubtargetInfo::RegClassVector &CriticalPathRCs) const {
+ Mode = ST.getAntiDepBreakMode();
+ ST.getCriticalPathRCs(CriticalPathRCs);
+ return ST.enablePostRAScheduler() &&
+ OptLevel >= ST.getOptLevelToEnablePostRAScheduler();
+}
+
bool PostRAScheduler::runOnMachineFunction(MachineFunction &Fn) {
- TII = Fn.getTarget().getInstrInfo();
+ if (skipOptnoneFunction(*Fn.getFunction()))
+ return false;
+
+ TII = Fn.getSubtarget().getInstrInfo();
MachineLoopInfo &MLI = getAnalysis<MachineLoopInfo>();
- MachineDominatorTree &MDT = getAnalysis<MachineDominatorTree>();
- AliasAnalysis *AA = &getAnalysis<AliasAnalysis>();
+ AliasAnalysis *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
TargetPassConfig *PassConfig = &getAnalysis<TargetPassConfig>();
RegClassInfo.runOnMachineFunction(Fn);
} else {
// Check that post-RA scheduling is enabled for this target.
// This may upgrade the AntiDepMode.
- const TargetSubtargetInfo &ST = Fn.getTarget().getSubtarget<TargetSubtargetInfo>();
- if (!ST.enablePostRAScheduler(PassConfig->getOptLevel(), AntiDepMode,
- CriticalPathRCs))
+ if (!enablePostRAScheduler(Fn.getSubtarget(), PassConfig->getOptLevel(),
+ AntiDepMode, CriticalPathRCs))
return false;
}
DEBUG(dbgs() << "PostRAScheduler\n");
- SchedulePostRATDList Scheduler(Fn, MLI, MDT, AA, RegClassInfo, AntiDepMode,
+ SchedulePostRATDList Scheduler(Fn, MLI, AA, RegClassInfo, AntiDepMode,
CriticalPathRCs);
// Loop over all of the basic blocks
- for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
- MBB != MBBe; ++MBB) {
+ for (auto &MBB : Fn) {
#ifndef NDEBUG
// If DebugDiv > 0 then only schedule MBB with (ID % DebugDiv) == DebugMod
if (DebugDiv > 0) {
if (bbcnt++ % DebugDiv != DebugMod)
continue;
dbgs() << "*** DEBUG scheduling " << Fn.getName()
- << ":BB#" << MBB->getNumber() << " ***\n";
+ << ":BB#" << MBB.getNumber() << " ***\n";
}
#endif
// Initialize register live-range state for scheduling in this block.
- Scheduler.startBlock(MBB);
+ Scheduler.startBlock(&MBB);
// Schedule each sequence of instructions not interrupted by a label
// or anything else that effectively needs to shut down scheduling.
- MachineBasicBlock::iterator Current = MBB->end();
- unsigned Count = MBB->size(), CurrentCount = Count;
- for (MachineBasicBlock::iterator I = Current; I != MBB->begin(); ) {
- MachineInstr *MI = llvm::prior(I);
+ MachineBasicBlock::iterator Current = MBB.end();
+ unsigned Count = MBB.size(), CurrentCount = Count;
+ for (MachineBasicBlock::iterator I = Current; I != MBB.begin();) {
+ MachineInstr *MI = std::prev(I);
--Count;
// Calls are not scheduling boundaries before register allocation, but
// post-ra we don't gain anything by scheduling across calls since we
// don't need to worry about register pressure.
- if (MI->isCall() || TII->isSchedulingBoundary(MI, MBB, Fn)) {
- Scheduler.enterRegion(MBB, I, Current, CurrentCount - Count);
+ if (MI->isCall() || TII->isSchedulingBoundary(MI, &MBB, Fn)) {
+ Scheduler.enterRegion(&MBB, I, Current, CurrentCount - Count);
Scheduler.setEndIndex(CurrentCount);
Scheduler.schedule();
Scheduler.exitRegion();
Count -= MI->getBundleSize();
}
assert(Count == 0 && "Instruction count mismatch!");
- assert((MBB->begin() == Current || CurrentCount != 0) &&
+ assert((MBB.begin() == Current || CurrentCount != 0) &&
"Instruction count mismatch!");
- Scheduler.enterRegion(MBB, MBB->begin(), Current, CurrentCount);
+ Scheduler.enterRegion(&MBB, MBB.begin(), Current, CurrentCount);
Scheduler.setEndIndex(CurrentCount);
Scheduler.schedule();
Scheduler.exitRegion();
Scheduler.finishBlock();
// Update register kills
- Scheduler.FixupKills(MBB);
+ Scheduler.fixupKills(&MBB);
}
return true;
// Reset the hazard recognizer and anti-dep breaker.
HazardRec->Reset();
- if (AntiDepBreak != NULL)
+ if (AntiDepBreak)
AntiDepBreak->StartBlock(BB);
}
// Build the scheduling graph.
buildSchedGraph(AA);
- if (AntiDepBreak != NULL) {
+ if (AntiDepBreak) {
unsigned Broken =
AntiDepBreak->BreakAntiDependencies(SUnits, RegionBegin, RegionEnd,
EndIndex, DbgValues);
}
DEBUG(dbgs() << "********** List Scheduling **********\n");
- DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
- SUnits[su].dumpAll(this));
+ DEBUG(
+ for (const SUnit &SU : SUnits) {
+ SU.dumpAll(this);
+ dbgs() << '\n';
+ }
+ );
AvailableQueue.initNodes(SUnits);
ListScheduleTopDown();
/// instruction, which will not be scheduled.
///
void SchedulePostRATDList::Observe(MachineInstr *MI, unsigned Count) {
- if (AntiDepBreak != NULL)
+ if (AntiDepBreak)
AntiDepBreak->Observe(MI, Count, EndIndex);
}
/// FinishBlock - Clean up register live-range state.
///
void SchedulePostRATDList::finishBlock() {
- if (AntiDepBreak != NULL)
+ if (AntiDepBreak)
AntiDepBreak->FinishBlock();
// Call the superclass.
ScheduleDAGInstrs::finishBlock();
}
-/// StartBlockForKills - Initialize register live-range state for updating kills
-///
-void SchedulePostRATDList::StartBlockForKills(MachineBasicBlock *BB) {
- // Start with no live registers.
- LiveRegs.reset();
-
- // Examine the live-in regs of all successors.
- for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(),
- SE = BB->succ_end(); SI != SE; ++SI) {
- for (MachineBasicBlock::livein_iterator I = (*SI)->livein_begin(),
- E = (*SI)->livein_end(); I != E; ++I) {
- unsigned Reg = *I;
- // Repeat, for reg and all subregs.
- for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
- SubRegs.isValid(); ++SubRegs)
- LiveRegs.set(*SubRegs);
- }
- }
-}
-
-bool SchedulePostRATDList::ToggleKillFlag(MachineInstr *MI,
- MachineOperand &MO) {
- // Setting kill flag...
- if (!MO.isKill()) {
- MO.setIsKill(true);
- return false;
- }
-
- // If MO itself is live, clear the kill flag...
- if (LiveRegs.test(MO.getReg())) {
- MO.setIsKill(false);
- return false;
- }
-
- // If any subreg of MO is live, then create an imp-def for that
- // subreg and keep MO marked as killed.
- MO.setIsKill(false);
- bool AllDead = true;
- const unsigned SuperReg = MO.getReg();
- MachineInstrBuilder MIB(MF, MI);
- for (MCSubRegIterator SubRegs(SuperReg, TRI); SubRegs.isValid(); ++SubRegs) {
- if (LiveRegs.test(*SubRegs)) {
- MIB.addReg(*SubRegs, RegState::ImplicitDefine);
- AllDead = false;
- }
- }
-
- if(AllDead)
- MO.setIsKill(true);
- return false;
-}
-
-/// FixupKills - Fix the register kill flags, they may have been made
-/// incorrect by instruction reordering.
-///
-void SchedulePostRATDList::FixupKills(MachineBasicBlock *MBB) {
- DEBUG(dbgs() << "Fixup kills for BB#" << MBB->getNumber() << '\n');
-
- BitVector killedRegs(TRI->getNumRegs());
-
- StartBlockForKills(MBB);
-
- // Examine block from end to start...
- unsigned Count = MBB->size();
- for (MachineBasicBlock::iterator I = MBB->end(), E = MBB->begin();
- I != E; --Count) {
- MachineInstr *MI = --I;
- if (MI->isDebugValue())
- continue;
-
- // Update liveness. Registers that are defed but not used in this
- // instruction are now dead. Mark register and all subregs as they
- // are completely defined.
- for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
- MachineOperand &MO = MI->getOperand(i);
- if (MO.isRegMask())
- LiveRegs.clearBitsNotInMask(MO.getRegMask());
- if (!MO.isReg()) continue;
- unsigned Reg = MO.getReg();
- if (Reg == 0) continue;
- if (!MO.isDef()) continue;
- // Ignore two-addr defs.
- if (MI->isRegTiedToUseOperand(i)) continue;
-
- // Repeat for reg and all subregs.
- for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
- SubRegs.isValid(); ++SubRegs)
- LiveRegs.reset(*SubRegs);
- }
-
- // Examine all used registers and set/clear kill flag. When a
- // register is used multiple times we only set the kill flag on
- // the first use. Don't set kill flags on undef operands.
- killedRegs.reset();
- for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
- MachineOperand &MO = MI->getOperand(i);
- if (!MO.isReg() || !MO.isUse() || MO.isUndef()) continue;
- unsigned Reg = MO.getReg();
- if ((Reg == 0) || MRI.isReserved(Reg)) continue;
-
- bool kill = false;
- if (!killedRegs.test(Reg)) {
- kill = true;
- // A register is not killed if any subregs are live...
- for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) {
- if (LiveRegs.test(*SubRegs)) {
- kill = false;
- break;
- }
- }
-
- // If subreg is not live, then register is killed if it became
- // live in this instruction
- if (kill)
- kill = !LiveRegs.test(Reg);
- }
-
- if (MO.isKill() != kill) {
- DEBUG(dbgs() << "Fixing " << MO << " in ");
- // Warning: ToggleKillFlag may invalidate MO.
- ToggleKillFlag(MI, MO);
- DEBUG(MI->dump());
- }
-
- killedRegs.set(Reg);
- }
-
- // Mark any used register (that is not using undef) and subregs as
- // now live...
- for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
- MachineOperand &MO = MI->getOperand(i);
- if (!MO.isReg() || !MO.isUse() || MO.isUndef()) continue;
- unsigned Reg = MO.getReg();
- if ((Reg == 0) || MRI.isReserved(Reg)) continue;
-
- for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
- SubRegs.isValid(); ++SubRegs)
- LiveRegs.set(*SubRegs);
- }
- }
-}
-
//===----------------------------------------------------------------------===//
// Top-Down Scheduling
//===----------------------------------------------------------------------===//
dbgs() << "*** Scheduling failed! ***\n";
SuccSU->dump(this);
dbgs() << " has been released too many times!\n";
- llvm_unreachable(0);
+ llvm_unreachable(nullptr);
}
#endif
--SuccSU->NumPredsLeft;
void SchedulePostRATDList::emitNoop(unsigned CurCycle) {
DEBUG(dbgs() << "*** Emitting noop in cycle " << CurCycle << '\n');
HazardRec->EmitNoop();
- Sequence.push_back(0); // NULL here means noop
+ Sequence.push_back(nullptr); // NULL here means noop
++NumNoops;
}
DEBUG(dbgs() << "\n*** Examining Available\n"; AvailableQueue.dump(this));
- SUnit *FoundSUnit = 0, *NotPreferredSUnit = 0;
+ SUnit *FoundSUnit = nullptr, *NotPreferredSUnit = nullptr;
bool HasNoopHazards = false;
while (!AvailableQueue.empty()) {
SUnit *CurSUnit = AvailableQueue.pop();
if (HT == ScheduleHazardRecognizer::NoHazard) {
if (HazardRec->ShouldPreferAnother(CurSUnit)) {
if (!NotPreferredSUnit) {
- // If this is the first non-preferred node for this cycle, then
- // record it and continue searching for a preferred node. If this
- // is not the first non-preferred node, then treat it as though
- // there had been a hazard.
+ // If this is the first non-preferred node for this cycle, then
+ // record it and continue searching for a preferred node. If this
+ // is not the first non-preferred node, then treat it as though
+ // there had been a hazard.
NotPreferredSUnit = CurSUnit;
continue;
}
AvailableQueue.push(NotPreferredSUnit);
}
- NotPreferredSUnit = 0;
+ NotPreferredSUnit = nullptr;
}
// Add the nodes that aren't ready back onto the available list.
// Update the Begin iterator, as the first instruction in the block
// may have been scheduled later.
if (i == 0)
- RegionBegin = prior(RegionEnd);
+ RegionBegin = std::prev(RegionEnd);
}
// Reinsert any remaining debug_values.
for (std::vector<std::pair<MachineInstr *, MachineInstr *> >::iterator
DI = DbgValues.end(), DE = DbgValues.begin(); DI != DE; --DI) {
- std::pair<MachineInstr *, MachineInstr *> P = *prior(DI);
+ std::pair<MachineInstr *, MachineInstr *> P = *std::prev(DI);
MachineInstr *DbgValue = P.first;
MachineBasicBlock::iterator OrigPrivMI = P.second;
BB->splice(++OrigPrivMI, BB, DbgValue);
}
DbgValues.clear();
- FirstDbgValue = NULL;
+ FirstDbgValue = nullptr;
}