#define DEBUG_TYPE "sched-instrs"
#include "ScheduleDAGInstrs.h"
+#include "llvm/Operator.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineMemOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/PseudoSourceValue.h"
#include "llvm/Target/TargetMachine.h"
ScheduleDAGInstrs::ScheduleDAGInstrs(MachineFunction &mf,
const MachineLoopInfo &mli,
const MachineDominatorTree &mdt)
- : ScheduleDAG(mf), MLI(mli), MDT(mdt), LoopRegs(MLI, MDT) {}
-
-/// getOpcode - If this is an Instruction or a ConstantExpr, return the
-/// opcode value. Otherwise return UserOp1.
-static unsigned getOpcode(const Value *V) {
- if (const Instruction *I = dyn_cast<Instruction>(V))
- return I->getOpcode();
- if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
- return CE->getOpcode();
- // Use UserOp1 to mean there's no opcode.
- return Instruction::UserOp1;
+ : ScheduleDAG(mf), MLI(mli), MDT(mdt), LoopRegs(MLI, MDT) {
+ MFI = mf.getFrameInfo();
+}
+
+/// Run - perform scheduling.
+///
+void ScheduleDAGInstrs::Run(MachineBasicBlock *bb,
+ MachineBasicBlock::iterator begin,
+ MachineBasicBlock::iterator end,
+ unsigned endcount) {
+ BB = bb;
+ Begin = begin;
+ InsertPosIndex = endcount;
+
+ ScheduleDAG::Run(bb, end);
}
/// getUnderlyingObjectFromInt - This is the function that does the work of
/// looking through basic ptrtoint+arithmetic+inttoptr sequences.
static const Value *getUnderlyingObjectFromInt(const Value *V) {
do {
- if (const User *U = dyn_cast<User>(V)) {
+ if (const Operator *U = dyn_cast<Operator>(V)) {
// If we find a ptrtoint, we can transfer control back to the
// regular getUnderlyingObjectFromInt.
- if (getOpcode(U) == Instruction::PtrToInt)
+ if (U->getOpcode() == Instruction::PtrToInt)
return U->getOperand(0);
// If we find an add of a constant or a multiplied value, it's
// likely that the other operand will lead us to the base
// object. We don't have to worry about the case where the
- // object address is somehow being computed bt the multiply,
+ // object address is somehow being computed by the multiply,
// because our callers only care when the result is an
// identifibale object.
- if (getOpcode(U) != Instruction::Add ||
+ if (U->getOpcode() != Instruction::Add ||
(!isa<ConstantInt>(U->getOperand(1)) &&
- getOpcode(U->getOperand(1)) != Instruction::Mul))
+ Operator::getOpcode(U->getOperand(1)) != Instruction::Mul))
return V;
V = U->getOperand(0);
} else {
do {
V = V->getUnderlyingObject();
// If it found an inttoptr, use special code to continue climing.
- if (getOpcode(V) != Instruction::IntToPtr)
+ if (Operator::getOpcode(V) != Instruction::IntToPtr)
break;
const Value *O = getUnderlyingObjectFromInt(cast<User>(V)->getOperand(0));
// If that succeeded in finding a pointer, continue the search.
/// getUnderlyingObjectForInstr - If this machine instr has memory reference
/// information and it can be tracked to a normal reference to a known
/// object, return the Value for that object. Otherwise return null.
-static const Value *getUnderlyingObjectForInstr(const MachineInstr *MI) {
+static const Value *getUnderlyingObjectForInstr(const MachineInstr *MI,
+ const MachineFrameInfo *MFI) {
if (!MI->hasOneMemOperand() ||
- !MI->memoperands_begin()->getValue() ||
- MI->memoperands_begin()->isVolatile())
+ !(*MI->memoperands_begin())->getValue() ||
+ (*MI->memoperands_begin())->isVolatile())
return 0;
- const Value *V = MI->memoperands_begin()->getValue();
+ const Value *V = (*MI->memoperands_begin())->getValue();
if (!V)
return 0;
V = getUnderlyingObject(V);
- if (!isa<PseudoSourceValue>(V) && !isIdentifiedObject(V))
- return 0;
+ if (const PseudoSourceValue *PSV = dyn_cast<PseudoSourceValue>(V)) {
+ // For now, ignore PseudoSourceValues which may alias LLVM IR values
+ // because the code that uses this function has no way to cope with
+ // such aliases.
+ if (PSV->isAliased(MFI))
+ return 0;
+ return V;
+ }
- return V;
+ if (isIdentifiedObject(V))
+ return V;
+
+ return 0;
}
void ScheduleDAGInstrs::StartBlock(MachineBasicBlock *BB) {
}
}
-void ScheduleDAGInstrs::BuildSchedGraph() {
+void ScheduleDAGInstrs::BuildSchedGraph(AliasAnalysis *AA) {
// We'll be allocating one SUnit for each instruction, plus one for
// the region exit node.
SUnits.reserve(BB->size());
bool UnitLatencies = ForceUnitLatencies();
// Ask the target if address-backscheduling is desirable, and if so how much.
- unsigned SpecialAddressLatency =
- TM.getSubtarget<TargetSubtarget>().getSpecialAddressLatency();
+ const TargetSubtarget &ST = TM.getSubtarget<TargetSubtarget>();
+ unsigned SpecialAddressLatency = ST.getSpecialAddressLatency();
// Walk the list of instructions, from bottom moving up.
- for (MachineBasicBlock::iterator MII = End, MIE = Begin;
+ for (MachineBasicBlock::iterator MII = InsertPos, MIE = Begin;
MII != MIE; --MII) {
MachineInstr *MI = prior(MII);
const TargetInstrDesc &TID = MI->getDesc();
assert(TRI->isPhysicalRegister(Reg) && "Virtual register encountered!");
std::vector<SUnit *> &UseList = Uses[Reg];
std::vector<SUnit *> &DefList = Defs[Reg];
- // Optionally add output and anti dependencies.
- // TODO: Using a latency of 1 here assumes there's no cost for
- // reusing registers.
+ // Optionally add output and anti dependencies. For anti
+ // dependencies we use a latency of 0 because for a multi-issue
+ // target we want to allow the defining instruction to issue
+ // in the same cycle as the using instruction.
+ // TODO: Using a latency of 1 here for output dependencies assumes
+ // there's no cost for reusing registers.
SDep::Kind Kind = MO.isUse() ? SDep::Anti : SDep::Output;
+ unsigned AOLatency = (Kind == SDep::Anti) ? 0 : 1;
for (unsigned i = 0, e = DefList.size(); i != e; ++i) {
SUnit *DefSU = DefList[i];
if (DefSU != SU &&
(Kind != SDep::Output || !MO.isDead() ||
!DefSU->getInstr()->registerDefIsDead(Reg)))
- DefSU->addPred(SDep(SU, Kind, /*Latency=*/1, /*Reg=*/Reg));
+ DefSU->addPred(SDep(SU, Kind, AOLatency, /*Reg=*/Reg));
}
for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) {
std::vector<SUnit *> &DefList = Defs[*Alias];
SUnit *DefSU = DefList[i];
if (DefSU != SU &&
(Kind != SDep::Output || !MO.isDead() ||
- !DefSU->getInstr()->registerDefIsDead(Reg)))
- DefSU->addPred(SDep(SU, Kind, /*Latency=*/1, /*Reg=*/ *Alias));
+ !DefSU->getInstr()->registerDefIsDead(*Alias)))
+ DefSU->addPred(SDep(SU, Kind, AOLatency, /*Reg=*/ *Alias));
}
}
// Optionally add in a special extra latency for nodes that
// feed addresses.
// TODO: Do this for register aliases too.
+ // TODO: Perhaps we should get rid of
+ // SpecialAddressLatency and just move this into
+ // adjustSchedDependency for the targets that care about
+ // it.
if (SpecialAddressLatency != 0 && !UnitLatencies) {
MachineInstr *UseMI = UseSU->getInstr();
const TargetInstrDesc &UseTID = UseMI->getDesc();
UseTID.OpInfo[RegUseIndex].isLookupPtrRegClass())
LDataLatency += SpecialAddressLatency;
}
- UseSU->addPred(SDep(SU, SDep::Data, LDataLatency, Reg));
+ // Adjust the dependence latency using operand def/use
+ // information (if any), and then allow the target to
+ // perform its own adjustments.
+ const SDep& dep = SDep(SU, SDep::Data, LDataLatency, Reg);
+ if (!UnitLatencies) {
+ ComputeOperandLatency(SU, UseSU, (SDep &)dep);
+ ST.adjustSchedDependency(SU, UseSU, (SDep &)dep);
+ }
+ UseSU->addPred(dep);
}
}
for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) {
std::vector<SUnit *> &UseList = Uses[*Alias];
for (unsigned i = 0, e = UseList.size(); i != e; ++i) {
SUnit *UseSU = UseList[i];
- if (UseSU != SU)
- UseSU->addPred(SDep(SU, SDep::Data, DataLatency, *Alias));
+ if (UseSU != SU) {
+ const SDep& dep = SDep(SU, SDep::Data, DataLatency, *Alias);
+ if (!UnitLatencies) {
+ ComputeOperandLatency(SU, UseSU, (SDep &)dep);
+ ST.adjustSchedDependency(SU, UseSU, (SDep &)dep);
+ }
+ UseSU->addPred(dep);
+ }
}
}
if (!ChainTID.isCall() &&
!ChainTID.hasUnmodeledSideEffects() &&
ChainMI->hasOneMemOperand() &&
- !ChainMI->memoperands_begin()->isVolatile() &&
- ChainMI->memoperands_begin()->getValue())
+ !(*ChainMI->memoperands_begin())->isVolatile() &&
+ (*ChainMI->memoperands_begin())->getValue())
// We know that the Chain accesses one specific memory location.
- ChainMMO = &*ChainMI->memoperands_begin();
+ ChainMMO = *ChainMI->memoperands_begin();
else
// Unknown memory accesses. Assume the worst.
ChainMMO = 0;
} else if (TID.mayStore()) {
- if (const Value *V = getUnderlyingObjectForInstr(MI)) {
+ if (const Value *V = getUnderlyingObjectForInstr(MI, MFI)) {
// A store to a specific PseudoSourceValue. Add precise dependencies.
// Handle the def in MemDefs, if there is one.
std::map<const Value *, SUnit *>::iterator I = MemDefs.find(V);
// Treat all other stores conservatively.
goto new_chain;
} else if (TID.mayLoad()) {
- if (TII->isInvariantLoad(MI)) {
+ if (MI->isInvariantLoad(AA)) {
// Invariant load, no chain dependencies needed!
- } else if (const Value *V = getUnderlyingObjectForInstr(MI)) {
+ } else if (const Value *V = getUnderlyingObjectForInstr(MI, MFI)) {
// A load from a specific PseudoSourceValue. Add precise dependencies.
std::map<const Value *, SUnit *>::iterator I = MemDefs.find(V);
if (I != MemDefs.end())
void ScheduleDAGInstrs::ComputeLatency(SUnit *SU) {
const InstrItineraryData &InstrItins = TM.getInstrItineraryData();
- // Compute the latency for the node. We use the sum of the latencies for
- // all nodes flagged together into this SUnit.
+ // Compute the latency for the node.
SU->Latency =
- InstrItins.getLatency(SU->getInstr()->getDesc().getSchedClass());
+ InstrItins.getStageLatency(SU->getInstr()->getDesc().getSchedClass());
// Simplistic target-independent heuristic: assume that loads take
// extra time.
SU->Latency += 2;
}
+void ScheduleDAGInstrs::ComputeOperandLatency(SUnit *Def, SUnit *Use,
+ SDep& dep) const {
+ const InstrItineraryData &InstrItins = TM.getInstrItineraryData();
+ if (InstrItins.isEmpty())
+ return;
+
+ // For a data dependency with a known register...
+ if ((dep.getKind() != SDep::Data) || (dep.getReg() == 0))
+ return;
+
+ const unsigned Reg = dep.getReg();
+
+ // ... find the definition of the register in the defining
+ // instruction
+ MachineInstr *DefMI = Def->getInstr();
+ int DefIdx = DefMI->findRegisterDefOperandIdx(Reg);
+ if (DefIdx != -1) {
+ int DefCycle = InstrItins.getOperandCycle(DefMI->getDesc().getSchedClass(), DefIdx);
+ if (DefCycle >= 0) {
+ MachineInstr *UseMI = Use->getInstr();
+ const unsigned UseClass = UseMI->getDesc().getSchedClass();
+
+ // For all uses of the register, calculate the maxmimum latency
+ int Latency = -1;
+ for (unsigned i = 0, e = UseMI->getNumOperands(); i != e; ++i) {
+ const MachineOperand &MO = UseMI->getOperand(i);
+ if (!MO.isReg() || !MO.isUse())
+ continue;
+ unsigned MOReg = MO.getReg();
+ if (MOReg != Reg)
+ continue;
+
+ int UseCycle = InstrItins.getOperandCycle(UseClass, i);
+ if (UseCycle >= 0)
+ Latency = std::max(Latency, DefCycle - UseCycle + 1);
+ }
+
+ // If we found a latency, then replace the existing dependence latency.
+ if (Latency >= 0)
+ dep.setLatency(Latency);
+ }
+ }
+}
+
void ScheduleDAGInstrs::dumpNode(const SUnit *SU) const {
SU->getInstr()->dump();
}
}
// EmitSchedule - Emit the machine code in scheduled order.
-MachineBasicBlock *ScheduleDAGInstrs::EmitSchedule() {
+MachineBasicBlock *ScheduleDAGInstrs::
+EmitSchedule(DenseMap<MachineBasicBlock*, MachineBasicBlock*> *EM) {
// For MachineInstr-based scheduling, we're rescheduling the instructions in
// the block, so start by removing them from the block.
- while (Begin != End) {
+ while (Begin != InsertPos) {
MachineBasicBlock::iterator I = Begin;
++Begin;
BB->remove(I);
continue;
}
- BB->insert(End, SU->getInstr());
+ BB->insert(InsertPos, SU->getInstr());
}
// Update the Begin iterator, as the first instruction in the block
projects / oota-llvm.git / blobdiff