static cl::opt<bool>
EnablePostRAHazardAvoidance("avoid-hazards",
cl::desc("Enable exact hazard avoidance"),
- cl::init(false), cl::Hidden);
+ cl::init(true), cl::Hidden);
+
+// If DebugDiv > 0 then only schedule MBB with (ID % DebugDiv) == DebugMod
+static cl::opt<int>
+DebugDiv("postra-sched-debugdiv",
+ cl::desc("Debug control MBBs that are scheduled"),
+ cl::init(0), cl::Hidden);
+static cl::opt<int>
+DebugMod("postra-sched-debugmod",
+ cl::desc("Debug control MBBs that are scheduled"),
+ cl::init(0), cl::Hidden);
namespace {
class VISIBILITY_HIDDEN PostRAScheduler : public MachineFunctionPass {
///
void FinishBlock();
- /// GenerateLivenessForKills - If true then generate Def/Kill
- /// information for use in updating register kill. If false then
- /// generate Def/Kill information for anti-dependence breaking.
- bool GenerateLivenessForKills;
-
private:
void PrescanInstruction(MachineInstr *MI);
void ScanInstruction(MachineInstr *MI, unsigned Count);
unsigned findSuitableFreeRegister(unsigned AntiDepReg,
unsigned LastNewReg,
const TargetRegisterClass *);
+ void StartBlockForKills(MachineBasicBlock *BB);
};
}
// Loop over all of the basic blocks
for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
MBB != MBBe; ++MBB) {
+#ifndef NDEBUG
+ // If DebugDiv > 0 then only schedule MBB with (ID % DebugDiv) == DebugMod
+ if (DebugDiv > 0) {
+ static int bbcnt = 0;
+ if (bbcnt++ % DebugDiv != DebugMod)
+ continue;
+ errs() << "*** DEBUG scheduling " << Fn.getFunction()->getNameStr() <<
+ ":MBB ID#" << MBB->getNumber() << " ***\n";
+ }
+#endif
+
// Initialize register live-range state for scheduling in this block.
- Scheduler.GenerateLivenessForKills = false;
Scheduler.StartBlock(MBB);
// Schedule each sequence of instructions not interrupted by a label
// Clean up register live-range state.
Scheduler.FinishBlock();
- // Initialize register live-range state again and update register kills
- Scheduler.GenerateLivenessForKills = true;
- Scheduler.StartBlock(MBB);
+ // Update register kills
Scheduler.FixupKills(MBB);
- Scheduler.FinishBlock();
}
return true;
}
}
- if (!GenerateLivenessForKills) {
- // Consider callee-saved registers as live-out, since we're running after
- // prologue/epilogue insertion so there's no way to add additional
- // saved registers.
- //
- // TODO: If the callee saves and restores these, then we can potentially
- // use them between the save and the restore. To do that, we could scan
- // the exit blocks to see which of these registers are defined.
- // Alternatively, callee-saved registers that aren't saved and restored
- // could be marked live-in in every block.
- for (const unsigned *I = TRI->getCalleeSavedRegs(); *I; ++I) {
- unsigned Reg = *I;
- Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1);
- KillIndices[Reg] = BB->size();
- DefIndices[Reg] = ~0u;
- // Repeat, for all aliases.
- for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) {
- unsigned AliasReg = *Alias;
- Classes[AliasReg] = reinterpret_cast<TargetRegisterClass *>(-1);
- KillIndices[AliasReg] = BB->size();
- DefIndices[AliasReg] = ~0u;
- }
+ // Consider callee-saved registers as live-out, since we're running after
+ // prologue/epilogue insertion so there's no way to add additional
+ // saved registers.
+ //
+ // TODO: there is a new method
+ // MachineFrameInfo::getPristineRegs(MBB). It gives you a list of
+ // CSRs that have not been saved when entering the MBB. The
+ // remaining CSRs have been saved and can be treated like call
+ // clobbered registers.
+ for (const unsigned *I = TRI->getCalleeSavedRegs(); *I; ++I) {
+ unsigned Reg = *I;
+ Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1);
+ KillIndices[Reg] = BB->size();
+ DefIndices[Reg] = ~0u;
+ // Repeat, for all aliases.
+ for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) {
+ unsigned AliasReg = *Alias;
+ Classes[AliasReg] = reinterpret_cast<TargetRegisterClass *>(-1);
+ KillIndices[AliasReg] = BB->size();
+ DefIndices[AliasReg] = ~0u;
}
}
}
Classes[SubregReg] = 0;
RegRefs.erase(SubregReg);
}
- // Conservatively mark super-registers as unusable. If
- // initializing for kill updating, then mark all supers as defined
- // as well.
+ // Conservatively mark super-registers as unusable.
for (const unsigned *Super = TRI->getSuperRegisters(Reg);
*Super; ++Super) {
unsigned SuperReg = *Super;
Classes[SuperReg] = reinterpret_cast<TargetRegisterClass *>(-1);
- if (GenerateLivenessForKills) {
- DefIndices[SuperReg] = Count;
- KillIndices[SuperReg] = ~0u;
- }
}
}
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
return Changed;
}
+/// StartBlockForKills - Initialize register live-range state for updating kills
+///
+void SchedulePostRATDList::StartBlockForKills(MachineBasicBlock *BB) {
+ // Initialize the indices to indicate that no registers are live.
+ std::fill(KillIndices, array_endof(KillIndices), ~0u);
+
+ // Determine the live-out physregs for this block.
+ if (!BB->empty() && BB->back().getDesc().isReturn()) {
+ // In a return block, examine the function live-out regs.
+ for (MachineRegisterInfo::liveout_iterator I = MRI.liveout_begin(),
+ E = MRI.liveout_end(); I != E; ++I) {
+ unsigned Reg = *I;
+ KillIndices[Reg] = BB->size();
+ // Repeat, for all subregs.
+ for (const unsigned *Subreg = TRI->getSubRegisters(Reg);
+ *Subreg; ++Subreg) {
+ KillIndices[*Subreg] = BB->size();
+ }
+ }
+ }
+ else {
+ // In a non-return block, 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;
+ KillIndices[Reg] = BB->size();
+ // Repeat, for all subregs.
+ for (const unsigned *Subreg = TRI->getSubRegisters(Reg);
+ *Subreg; ++Subreg) {
+ KillIndices[*Subreg] = BB->size();
+ }
+ }
+ }
+ }
+}
+
/// FixupKills - Fix the register kill flags, they may have been made
/// incorrect by instruction reordering.
///
std::set<unsigned> killedRegs;
BitVector ReservedRegs = TRI->getReservedRegs(MF);
+ 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;
- // After regalloc, IMPLICIT_DEF instructions aren't safe to treat as
- // dependence-breaking. In the case of an INSERT_SUBREG, the IMPLICIT_DEF
- // is left behind appearing to clobber the super-register, while the
- // subregister needs to remain live. So we just ignore them.
- if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF)
- continue;
-
- PrescanInstruction(MI);
- ScanInstruction(MI, Count);
+ // 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.isReg()) continue;
+ unsigned Reg = MO.getReg();
+ if (Reg == 0) continue;
+ if (!MO.isDef()) continue;
+ // Ignore two-addr defs.
+ if (MI->isRegTiedToUseOperand(i)) continue;
+
+ KillIndices[Reg] = ~0u;
+
+ // Repeat for all subregs.
+ for (const unsigned *Subreg = TRI->getSubRegisters(Reg);
+ *Subreg; ++Subreg) {
+ KillIndices[*Subreg] = ~0u;
+ }
+ }
// Examine all used registers and set kill flag. When a register
// is used multiple times we only set the kill flag on the first
unsigned Reg = MO.getReg();
if ((Reg == 0) || ReservedRegs.test(Reg)) continue;
- bool kill = ((KillIndices[Reg] == Count) &&
- (killedRegs.find(Reg) == killedRegs.end()));
+ bool kill = false;
+ if (killedRegs.find(Reg) == killedRegs.end()) {
+ kill = true;
+ // A register is not killed if any subregs are live...
+ for (const unsigned *Subreg = TRI->getSubRegisters(Reg);
+ *Subreg; ++Subreg) {
+ if (KillIndices[*Subreg] != ~0u) {
+ kill = false;
+ break;
+ }
+ }
+
+ // If subreg is not live, then register is killed if it became
+ // live in this instruction
+ if (kill)
+ kill = (KillIndices[Reg] == ~0u);
+ }
+
if (MO.isKill() != kill) {
MO.setIsKill(kill);
DEBUG(errs() << "Fixed " << MO << " in ");
DEBUG(MI->dump());
}
-
+
killedRegs.insert(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) || ReservedRegs.test(Reg)) continue;
+
+ KillIndices[Reg] = Count;
+
+ for (const unsigned *Subreg = TRI->getSubRegisters(Reg);
+ *Subreg; ++Subreg) {
+ KillIndices[*Subreg] = Count;
+ }
+ }
}
}
// In any cycle where we can't schedule any instructions, we must
// stall or emit a noop, depending on the target.
- bool CycleInstCnt = 0;
+ bool CycleHasInsts = false;
// While Available queue is not empty, grab the node with the highest
// priority. If it is not ready put it back. Schedule the node.
if (FoundSUnit) {
ScheduleNodeTopDown(FoundSUnit, CurCycle);
HazardRec->EmitInstruction(FoundSUnit);
- CycleInstCnt++;
+ CycleHasInsts = true;
// If we are using the target-specific hazards, then don't
// advance the cycle time just because we schedule a node. If
++CurCycle;
}
} else {
- if (CycleInstCnt > 0) {
+ if (CycleHasInsts) {
DEBUG(errs() << "*** Finished cycle " << CurCycle << '\n');
HazardRec->AdvanceCycle();
} else if (!HasNoopHazards) {
}
++CurCycle;
- CycleInstCnt = 0;
+ CycleHasInsts = false;
}
}