#include "llvm/Support/raw_ostream.h"
#include "llvm/ADT/Statistic.h"
#include <map>
+#include <set>
using namespace llvm;
STATISTIC(NumNoops, "Number of noops inserted");
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 {
/// Schedule - Schedule the instruction range using list scheduling.
///
void Schedule();
+
+ /// FixupKills - Fix register kill flags that have been made
+ /// invalid due to scheduling
+ ///
+ void FixupKills(MachineBasicBlock *MBB);
/// Observe - Update liveness information to account for the current
/// instruction, which will not be scheduled.
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.StartBlock(MBB);
// Clean up register live-range state.
Scheduler.FinishBlock();
+
+ // Update register kills
+ Scheduler.FixupKills(MBB);
}
return true;
// 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.
+ // 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);
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.
+///
+void SchedulePostRATDList::FixupKills(MachineBasicBlock *MBB) {
+ DEBUG(errs() << "Fixup kills for BB ID#" << MBB->getNumber() << '\n');
+
+ 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;
+
+ // 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
+ // use.
+ killedRegs.clear();
+ for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
+ MachineOperand &MO = MI->getOperand(i);
+ if (!MO.isReg() || !MO.isUse()) continue;
+ unsigned Reg = MO.getReg();
+ if ((Reg == 0) || ReservedRegs.test(Reg)) continue;
+
+ 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;
+ }
+ }
+ }
+}
+
//===----------------------------------------------------------------------===//
// Top-Down Scheduling
//===----------------------------------------------------------------------===//
#ifndef NDEBUG
if (SuccSU->NumPredsLeft < 0) {
- cerr << "*** Scheduling failed! ***\n";
+ errs() << "*** Scheduling failed! ***\n";
SuccSU->dump(this);
- cerr << " has been released too many times!\n";
+ errs() << " has been released too many times!\n";
llvm_unreachable(0);
}
#endif
}
}
+ // In any cycle where we can't schedule any instructions, we must
+ // stall or emit a noop, depending on the target.
+ 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.
std::vector<SUnit*> NotReady;
if (FoundSUnit) {
ScheduleNodeTopDown(FoundSUnit, CurCycle);
HazardRec->EmitInstruction(FoundSUnit);
+ CycleHasInsts = true;
// If we are using the target-specific hazards, then don't
// advance the cycle time just because we schedule a node. If
if (FoundSUnit->Latency) // Don't increment CurCycle for pseudo-ops!
++CurCycle;
}
- } else if (!HasNoopHazards) {
- // Otherwise, we have a pipeline stall, but no other problem, just advance
- // the current cycle and try again.
- DEBUG(errs() << "*** Advancing cycle, no work to do\n");
- HazardRec->AdvanceCycle();
- ++NumStalls;
- ++CurCycle;
} else {
- // Otherwise, we have no instructions to issue and we have instructions
- // that will fault if we don't do this right. This is the case for
- // processors without pipeline interlocks and other cases.
- DEBUG(errs() << "*** Emitting noop\n");
- HazardRec->EmitNoop();
- Sequence.push_back(0); // NULL here means noop
- ++NumNoops;
+ if (CycleHasInsts) {
+ DEBUG(errs() << "*** Finished cycle " << CurCycle << '\n');
+ HazardRec->AdvanceCycle();
+ } else if (!HasNoopHazards) {
+ // Otherwise, we have a pipeline stall, but no other problem,
+ // just advance the current cycle and try again.
+ DEBUG(errs() << "*** Stall in cycle " << CurCycle << '\n');
+ HazardRec->AdvanceCycle();
+ ++NumStalls;
+ } else {
+ // Otherwise, we have no instructions to issue and we have instructions
+ // that will fault if we don't do this right. This is the case for
+ // processors without pipeline interlocks and other cases.
+ DEBUG(errs() << "*** Emitting noop in cycle " << CurCycle << '\n');
+ HazardRec->EmitNoop();
+ Sequence.push_back(0); // NULL here means noop
+ ++NumNoops;
+ }
+
++CurCycle;
+ CycleHasInsts = false;
}
}
projects / oota-llvm.git / blobdiff