// The next region starts above the previous region. Look backward in the
// instruction stream until we find the nearest boundary.
MachineBasicBlock::iterator I = RegionEnd;
- for(;I != MBB->begin(); --I) {
+ for(;I != MBB->begin(); --I, --RemainingCount) {
if (TII->isSchedulingBoundary(llvm::prior(I), MBB, *MF))
break;
}
- if (I == RegionEnd || I == llvm::prior(RegionEnd)) {
- // Skip empty or single instruction scheduling regions.
+ if (I == RegionEnd) {
+ // Skip empty scheduling regions.
RegionEnd = llvm::prior(RegionEnd);
+ --RemainingCount;
continue;
}
- DEBUG(dbgs() << "MachineScheduling " << MF->getFunction()->getName()
- << ":BB#" << MBB->getNumber() << "\n From: " << *I << " To: "
- << *RegionEnd << " Remaining: " << RemainingCount << "\n");
-
- // Inform ScheduleDAGInstrs of the region being scheduler. It calls back
- // to our Schedule() method.
- Scheduler->Run(MBB, I, RegionEnd, MBB->size());
+ // Schedule regions with more than one instruction.
+ if (I != llvm::prior(RegionEnd)) {
+ DEBUG(dbgs() << "MachineScheduling " << MF->getFunction()->getName()
+ << ":BB#" << MBB->getNumber() << "\n From: " << *I << " To: "
+ << *RegionEnd << " Remaining: " << RemainingCount << "\n");
+
+ // Inform ScheduleDAGInstrs of the region being scheduled. It calls back
+ // to our Schedule() method.
+ Scheduler->Run(MBB, I, RegionEnd, MBB->size());
+ }
RegionEnd = I;
}
assert(RemainingCount == 0 && "Instruction count mismatch!");
unsigned Reg = MO.getReg();
if (Reg == 0) continue;
- assert(TRI->isPhysicalRegister(Reg) && "Virtual register encountered!");
- Uses[Reg].push_back(&ExitSU);
+ if (TRI->isPhysicalRegister(Reg))
+ Uses[Reg].push_back(&ExitSU);
+ else
+ assert(!IsPostRA && "Virtual register encountered after regalloc.");
}
} else {
// For others, e.g. fallthrough, conditional branch, assume the exit
}
}
-/// addVirtRegDeps - Add register dependencies (data, anti, and output) from
-/// this SUnit to following instructions in the same scheduling region that
-/// depend the virtual register referenced at OperIdx.
-void ScheduleDAGInstrs::addVirtRegDeps(SUnit *SU, unsigned OperIdx) {
- assert(false && "unimplemented");
+/// addVRegDefDeps - Add register output and data dependencies from this SUnit
+/// to instructions that occur later in the same scheduling region if they read
+/// from or write to the virtual register defined at OperIdx.
+///
+/// TODO: Hoist loop induction variable increments. This has to be
+/// reevaluated. Generally, IV scheduling should be done before coalescing.
+void ScheduleDAGInstrs::addVRegDefDeps(SUnit *SU, unsigned OperIdx) {
+ const MachineInstr *MI = SU->getInstr();
+ unsigned Reg = MI->getOperand(OperIdx).getReg();
+
+ const TargetSubtargetInfo &ST = TM.getSubtarget<TargetSubtargetInfo>();
+
+ // Add output dependence to the next nearest def of this vreg.
+ //
+ // Unless this definition is dead, the output dependence should be
+ // transitively redundant with antidependencies from this definition's
+ // uses. We're conservative for now until we have a way to guarantee the uses
+ // are not eliminated sometime during scheduling. The output dependence edge
+ // is also useful if output latency exceeds def-use latency.
+ SUnit *DefSU = VRegDefs[Reg];
+ if (DefSU && DefSU != SU && DefSU != &ExitSU) {
+ unsigned OutLatency = TII->getOutputLatency(InstrItins, MI, OperIdx,
+ DefSU->getInstr());
+ DefSU->addPred(SDep(SU, SDep::Output, OutLatency, Reg));
+ }
+ VRegDefs[Reg] = SU;
+
+ // Add data dependence to any uses of this vreg before the next nearest def.
+ //
+ // TODO: Handle ExitSU properly.
+ //
+ // TODO: Data dependence could be handled more efficiently at the use-side.
+ std::vector<SUnit*> &UseList = VRegUses[Reg];
+ for (std::vector<SUnit*>::const_iterator UI = UseList.begin(),
+ UE = UseList.end(); UI != UE; ++UI) {
+ SUnit *UseSU = *UI;
+ if (UseSU == SU) continue;
+
+ // TODO: Handle "special" address latencies cleanly.
+ const SDep& dep = SDep(SU, SDep::Data, SU->Latency, Reg);
+ if (!UnitLatencies) {
+ // Adjust the dependence latency using operand def/use information, then
+ // allow the target to perform its own adjustments.
+ ComputeOperandLatency(SU, UseSU, const_cast<SDep &>(dep));
+ ST.adjustSchedDependency(SU, UseSU, const_cast<SDep &>(dep));
+ }
+ UseSU->addPred(dep);
+ }
+ UseList.clear();
+}
+
+/// addVRegUseDeps - Add register antidependencies from this SUnit to
+/// instructions that occur later in the same scheduling region if they
+/// write the virtual register referenced at OperIdx.
+void ScheduleDAGInstrs::addVRegUseDeps(SUnit *SU, unsigned OperIdx) {
+ unsigned Reg = SU->getInstr()->getOperand(OperIdx).getReg();
+
+ // Add antidependence to the following def of the vreg it uses.
+ SUnit *DefSU = VRegDefs[Reg];
+ if (DefSU && DefSU != SU)
+ DefSU->addPred(SDep(SU, SDep::Anti, 0, Reg));
+
+ // Add this SUnit to the use list of the vreg it uses.
+ //
+ // TODO: pinch the DAG before we see too many uses to avoid quadratic
+ // behavior. Limiting the scheduling window can accomplish the same thing.
+ VRegUses[Reg].push_back(SU);
}
void ScheduleDAGInstrs::BuildSchedGraph(AliasAnalysis *AA) {
assert(Defs[i].empty() && "Only BuildGraph should push/pop Defs");
}
+ // Reinitialize the large VReg vectors, while reusing the memory.
+ //
+ // Note: this can be an expensive part of DAG building. We may want to be more
+ // clever. Reevaluate after VRegUses goes away.
+ assert(VRegDefs.size() == 0 && VRegUses.size() == 0 &&
+ "Only BuildSchedGraph should access VRegDefs/Uses");
+ VRegDefs.resize(MF.getRegInfo().getNumVirtRegs());
+ VRegUses.resize(MF.getRegInfo().getNumVirtRegs());
+
// Walk the list of instructions, from bottom moving up.
MachineInstr *PrevMI = NULL;
for (MachineBasicBlock::iterator MII = InsertPos, MIE = Begin;
addPhysRegDeps(SU, j);
else {
assert(!IsPostRA && "Virtual register encountered!");
- addVirtRegDeps(SU, j);
+ if (MO.isDef())
+ addVRegDefDeps(SU, j);
+ else
+ addVRegUseDeps(SU, j);
}
}
Defs[i].clear();
Uses[i].clear();
}
+ VRegDefs.clear();
+ VRegUses.clear();
PendingLoads.clear();
}
#include "llvm/CodeGen/ScheduleDAG.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Target/TargetRegisterInfo.h"
+#include "llvm/ADT/IndexedMap.h"
#include "llvm/ADT/SmallSet.h"
#include <map>
/// isPostRA flag indicates vregs cannot be present.
bool IsPostRA;
- /// UnitLatencies flag forces single-cycle data dependencies.
+ /// UnitLatencies (misnamed) flag avoids computing def-use latencies, using
+ /// the def-side latency only.
bool UnitLatencies;
/// Defs, Uses - Remember where defs and uses of each register are as we
std::vector<std::vector<SUnit *> > Defs;
std::vector<std::vector<SUnit *> > Uses;
+ // Virtual register Defs and Uses.
+ //
+ // TODO: Eliminate VRegUses by creating SUnits in a prepass and looking up
+ // the live range's reaching def.
+ IndexedMap<SUnit*, VirtReg2IndexFunctor> VRegDefs;
+ IndexedMap<std::vector<SUnit*>, VirtReg2IndexFunctor> VRegUses;
+
/// PendingLoads - Remember where unknown loads are after the most recent
/// unknown store, as we iterate. As with Defs and Uses, this is here
/// to minimize construction/destruction.
protected:
void addPhysRegDeps(SUnit *SU, unsigned OperIdx);
- void addVirtRegDeps(SUnit *SU, unsigned OperIdx);
+ void addVRegDefDeps(SUnit *SU, unsigned OperIdx);
+ void addVRegUseDeps(SUnit *SU, unsigned OperIdx);
};
}
projects / oota-llvm.git / commitdiff