diff options
Diffstat (limited to 'lib/CodeGen/ScheduleDAGInstrs.cpp')
| -rw-r--r-- | lib/CodeGen/ScheduleDAGInstrs.cpp | 765 |
1 files changed, 481 insertions, 284 deletions
diff --git a/lib/CodeGen/ScheduleDAGInstrs.cpp b/lib/CodeGen/ScheduleDAGInstrs.cpp index 2d8f235..662fc0e 100644 --- a/lib/CodeGen/ScheduleDAGInstrs.cpp +++ b/lib/CodeGen/ScheduleDAGInstrs.cpp @@ -12,8 +12,11 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "sched-instrs" -#include "llvm/Operator.h" +#define DEBUG_TYPE "misched" +#include "llvm/CodeGen/ScheduleDAGInstrs.h" +#include "llvm/ADT/MapVector.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallSet.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/CodeGen/LiveIntervalAnalysis.h" @@ -22,17 +25,17 @@ #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/PseudoSourceValue.h" #include "llvm/CodeGen/RegisterPressure.h" -#include "llvm/CodeGen/ScheduleDAGInstrs.h" +#include "llvm/CodeGen/ScheduleDFS.h" +#include "llvm/IR/Operator.h" #include "llvm/MC/MCInstrItineraries.h" -#include "llvm/Target/TargetMachine.h" -#include "llvm/Target/TargetInstrInfo.h" -#include "llvm/Target/TargetRegisterInfo.h" -#include "llvm/Target/TargetSubtargetInfo.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" +#include "llvm/Support/Format.h" #include "llvm/Support/raw_ostream.h" -#include "llvm/ADT/SmallSet.h" -#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetMachine.h" +#include "llvm/Target/TargetRegisterInfo.h" +#include "llvm/Target/TargetSubtargetInfo.h" using namespace llvm; static cl::opt<bool> EnableAASchedMI("enable-aa-sched-mi", cl::Hidden, @@ -44,14 +47,15 @@ ScheduleDAGInstrs::ScheduleDAGInstrs(MachineFunction &mf, const MachineDominatorTree &mdt, bool IsPostRAFlag, LiveIntervals *lis) - : ScheduleDAG(mf), MLI(mli), MDT(mdt), MFI(mf.getFrameInfo()), - InstrItins(mf.getTarget().getInstrItineraryData()), LIS(lis), - IsPostRA(IsPostRAFlag), UnitLatencies(false), CanHandleTerminators(false), - LoopRegs(MDT), FirstDbgValue(0) { + : ScheduleDAG(mf), MLI(mli), MDT(mdt), MFI(mf.getFrameInfo()), LIS(lis), + IsPostRA(IsPostRAFlag), CanHandleTerminators(false), FirstDbgValue(0) { assert((IsPostRA || LIS) && "PreRA scheduling requires LiveIntervals"); DbgValues.clear(); assert(!(IsPostRA && MRI.getNumVirtRegs()) && "Virtual registers must be removed prior to PostRA scheduling"); + + const TargetSubtargetInfo &ST = TM.getSubtarget<TargetSubtargetInfo>(); + SchedModel.init(*ST.getSchedModel(), &ST, TII); } /// getUnderlyingObjectFromInt - This is the function that does the work of @@ -63,15 +67,16 @@ static const Value *getUnderlyingObjectFromInt(const Value *V) { // regular getUnderlyingObjectFromInt. if (U->getOpcode() == Instruction::PtrToInt) return U->getOperand(0); - // If we find an add of a constant or a multiplied value, it's + // If we find an add of a constant, a multiplied value, or a phi, 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 by the multiply, // because our callers only care when the result is an - // identifibale object. + // identifiable object. if (U->getOpcode() != Instruction::Add || (!isa<ConstantInt>(U->getOperand(1)) && - Operator::getOpcode(U->getOperand(1)) != Instruction::Mul)) + Operator::getOpcode(U->getOperand(1)) != Instruction::Mul && + !isa<PHINode>(U->getOperand(1)))) return V; V = U->getOperand(0); } else { @@ -81,64 +86,81 @@ static const Value *getUnderlyingObjectFromInt(const Value *V) { } while (1); } -/// getUnderlyingObject - This is a wrapper around GetUnderlyingObject +/// getUnderlyingObjects - This is a wrapper around GetUnderlyingObjects /// and adds support for basic ptrtoint+arithmetic+inttoptr sequences. -static const Value *getUnderlyingObject(const Value *V) { - // First just call Value::getUnderlyingObject to let it do what it does. +static void getUnderlyingObjects(const Value *V, + SmallVectorImpl<Value *> &Objects) { + SmallPtrSet<const Value*, 16> Visited; + SmallVector<const Value *, 4> Working(1, V); do { - V = GetUnderlyingObject(V); - // If it found an inttoptr, use special code to continue climing. - 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. - if (!O->getType()->isPointerTy()) - break; - V = O; - } while (1); - return V; + V = Working.pop_back_val(); + + SmallVector<Value *, 4> Objs; + GetUnderlyingObjects(const_cast<Value *>(V), Objs); + + for (SmallVector<Value *, 4>::iterator I = Objs.begin(), IE = Objs.end(); + I != IE; ++I) { + V = *I; + if (!Visited.insert(V)) + continue; + if (Operator::getOpcode(V) == Instruction::IntToPtr) { + const Value *O = + getUnderlyingObjectFromInt(cast<User>(V)->getOperand(0)); + if (O->getType()->isPointerTy()) { + Working.push_back(O); + continue; + } + } + Objects.push_back(const_cast<Value *>(V)); + } + } while (!Working.empty()); } -/// getUnderlyingObjectForInstr - If this machine instr has memory reference +/// getUnderlyingObjectsForInstr - 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, - const MachineFrameInfo *MFI, - bool &MayAlias) { - MayAlias = true; +/// object, return the Value for that object. +static void getUnderlyingObjectsForInstr(const MachineInstr *MI, + const MachineFrameInfo *MFI, + SmallVectorImpl<std::pair<const Value *, bool> > &Objects) { if (!MI->hasOneMemOperand() || !(*MI->memoperands_begin())->getValue() || (*MI->memoperands_begin())->isVolatile()) - return 0; + return; const Value *V = (*MI->memoperands_begin())->getValue(); if (!V) - return 0; - - V = getUnderlyingObject(V); - 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; - - MayAlias = PSV->mayAlias(MFI); - return V; - } + return; + + SmallVector<Value *, 4> Objs; + getUnderlyingObjects(V, Objs); + + for (SmallVector<Value *, 4>::iterator I = Objs.begin(), IE = Objs.end(); + I != IE; ++I) { + bool MayAlias = true; + V = *I; + + 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 (isIdentifiedObject(V)) - return V; + if (PSV->isAliased(MFI)) { + Objects.clear(); + return; + } + + MayAlias = PSV->mayAlias(MFI); + } else if (!isIdentifiedObject(V)) { + Objects.clear(); + return; + } - return 0; + Objects.push_back(std::make_pair(V, MayAlias)); + } } void ScheduleDAGInstrs::startBlock(MachineBasicBlock *bb) { BB = bb; - LoopRegs.Deps.clear(); - if (MachineLoop *ML = MLI.getLoopFor(BB)) - if (BB == ML->getLoopLatch()) - LoopRegs.VisitLoop(ML); } void ScheduleDAGInstrs::finishBlock() { @@ -174,9 +196,6 @@ void ScheduleDAGInstrs::enterRegion(MachineBasicBlock *bb, EndIndex = endcount; MISUnitMap.clear(); - // Check to see if the scheduler cares about latencies. - UnitLatencies = forceUnitLatencies(); - ScheduleDAG::clearDAG(); } @@ -212,7 +231,8 @@ void ScheduleDAGInstrs::addSchedBarrierDeps() { Uses[Reg].push_back(PhysRegSUOper(&ExitSU, -1)); else { assert(!IsPostRA && "Virtual register encountered after regalloc."); - addVRegUseDeps(&ExitSU, i); + if (MO.readsReg()) // ignore undef operands + addVRegUseDeps(&ExitSU, i); } } } else { @@ -238,8 +258,6 @@ void ScheduleDAGInstrs::addPhysRegDataDeps(SUnit *SU, unsigned OperIdx) { // Ask the target if address-backscheduling is desirable, and if so how much. const TargetSubtargetInfo &ST = TM.getSubtarget<TargetSubtargetInfo>(); - unsigned SpecialAddressLatency = ST.getSpecialAddressLatency(); - unsigned DataLatency = SU->Latency; for (MCRegAliasIterator Alias(MO.getReg(), TRI, true); Alias.isValid(); ++Alias) { @@ -250,43 +268,27 @@ void ScheduleDAGInstrs::addPhysRegDataDeps(SUnit *SU, unsigned OperIdx) { SUnit *UseSU = UseList[i].SU; if (UseSU == SU) continue; - MachineInstr *UseMI = UseSU->getInstr(); + + // Adjust the dependence latency using operand def/use information, + // then allow the target to perform its own adjustments. int UseOp = UseList[i].OpIdx; - unsigned LDataLatency = DataLatency; - // Optionally add in a special extra latency for nodes that - // feed addresses. - // 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 && - UseSU != &ExitSU) { - const MCInstrDesc &UseMCID = UseMI->getDesc(); - int RegUseIndex = UseMI->findRegisterUseOperandIdx(*Alias); - assert(RegUseIndex >= 0 && "UseMI doesn't use register!"); - if (RegUseIndex >= 0 && - (UseMI->mayLoad() || UseMI->mayStore()) && - (unsigned)RegUseIndex < UseMCID.getNumOperands() && - UseMCID.OpInfo[RegUseIndex].isLookupPtrRegClass()) - LDataLatency += SpecialAddressLatency; - } - // Adjust the dependence latency using operand def/use - // information (if any), and then allow the target to - // perform its own adjustments. - SDep dep(SU, SDep::Data, LDataLatency, *Alias); - if (!UnitLatencies) { - unsigned Latency = - TII->computeOperandLatency(InstrItins, SU->getInstr(), OperIdx, - (UseOp < 0 ? 0 : UseMI), UseOp); - dep.setLatency(Latency); - unsigned MinLatency = - TII->computeOperandLatency(InstrItins, SU->getInstr(), OperIdx, - (UseOp < 0 ? 0 : UseMI), UseOp, - /*FindMin=*/true); - dep.setMinLatency(MinLatency); - - ST.adjustSchedDependency(SU, UseSU, dep); + MachineInstr *RegUse = 0; + SDep Dep; + if (UseOp < 0) + Dep = SDep(SU, SDep::Artificial); + else { + Dep = SDep(SU, SDep::Data, *Alias); + RegUse = UseSU->getInstr(); + Dep.setMinLatency( + SchedModel.computeOperandLatency(SU->getInstr(), OperIdx, + RegUse, UseOp, /*FindMin=*/true)); } - UseSU->addPred(dep); + Dep.setLatency( + SchedModel.computeOperandLatency(SU->getInstr(), OperIdx, + RegUse, UseOp, /*FindMin=*/false)); + + ST.adjustSchedDependency(SU, UseSU, Dep); + UseSU->addPred(Dep); } } } @@ -318,11 +320,14 @@ void ScheduleDAGInstrs::addPhysRegDeps(SUnit *SU, unsigned OperIdx) { (Kind != SDep::Output || !MO.isDead() || !DefSU->getInstr()->registerDefIsDead(*Alias))) { if (Kind == SDep::Anti) - DefSU->addPred(SDep(SU, Kind, 0, /*Reg=*/*Alias)); + DefSU->addPred(SDep(SU, Kind, /*Reg=*/*Alias)); else { - unsigned AOLat = TII->getOutputLatency(InstrItins, MI, OperIdx, - DefSU->getInstr()); - DefSU->addPred(SDep(SU, Kind, AOLat, /*Reg=*/*Alias)); + SDep Dep(SU, Kind, /*Reg=*/*Alias); + unsigned OutLatency = + SchedModel.computeOutputLatency(MI, OperIdx, DefSU->getInstr()); + Dep.setMinLatency(OutLatency); + Dep.setLatency(OutLatency); + DefSU->addPred(Dep); } } } @@ -341,53 +346,6 @@ void ScheduleDAGInstrs::addPhysRegDeps(SUnit *SU, unsigned OperIdx) { // retrieve the existing SUnits list for this register's defs. std::vector<PhysRegSUOper> &DefList = Defs[MO.getReg()]; - // If a def is going to wrap back around to the top of the loop, - // backschedule it. - if (!UnitLatencies && DefList.empty()) { - LoopDependencies::LoopDeps::iterator I = LoopRegs.Deps.find(MO.getReg()); - if (I != LoopRegs.Deps.end()) { - const MachineOperand *UseMO = I->second.first; - unsigned Count = I->second.second; - const MachineInstr *UseMI = UseMO->getParent(); - unsigned UseMOIdx = UseMO - &UseMI->getOperand(0); - const MCInstrDesc &UseMCID = UseMI->getDesc(); - const TargetSubtargetInfo &ST = - TM.getSubtarget<TargetSubtargetInfo>(); - unsigned SpecialAddressLatency = ST.getSpecialAddressLatency(); - // TODO: If we knew the total depth of the region here, we could - // handle the case where the whole loop is inside the region but - // is large enough that the isScheduleHigh trick isn't needed. - if (UseMOIdx < UseMCID.getNumOperands()) { - // Currently, we only support scheduling regions consisting of - // single basic blocks. Check to see if the instruction is in - // the same region by checking to see if it has the same parent. - if (UseMI->getParent() != MI->getParent()) { - unsigned Latency = SU->Latency; - if (UseMCID.OpInfo[UseMOIdx].isLookupPtrRegClass()) - Latency += SpecialAddressLatency; - // This is a wild guess as to the portion of the latency which - // will be overlapped by work done outside the current - // scheduling region. - Latency -= std::min(Latency, Count); - // Add the artificial edge. - ExitSU.addPred(SDep(SU, SDep::Order, Latency, - /*Reg=*/0, /*isNormalMemory=*/false, - /*isMustAlias=*/false, - /*isArtificial=*/true)); - } else if (SpecialAddressLatency > 0 && - UseMCID.OpInfo[UseMOIdx].isLookupPtrRegClass()) { - // The entire loop body is within the current scheduling region - // and the latency of this operation is assumed to be greater - // than the latency of the loop. - // TODO: Recursively mark data-edge predecessors as - // isScheduleHigh too. - SU->isScheduleHigh = true; - } - } - LoopRegs.Deps.erase(I); - } - } - // clear this register's use list if (Uses.contains(MO.getReg())) Uses[MO.getReg()].clear(); @@ -438,9 +396,12 @@ void ScheduleDAGInstrs::addVRegDefDeps(SUnit *SU, unsigned OperIdx) { else { SUnit *DefSU = DefI->SU; if (DefSU != SU && DefSU != &ExitSU) { - unsigned OutLatency = TII->getOutputLatency(InstrItins, MI, OperIdx, - DefSU->getInstr()); - DefSU->addPred(SDep(SU, SDep::Output, OutLatency, Reg)); + SDep Dep(SU, SDep::Output, Reg); + unsigned OutLatency = + SchedModel.computeOutputLatency(MI, OperIdx, DefSU->getInstr()); + Dep.setMinLatency(OutLatency); + Dep.setLatency(OutLatency); + DefSU->addPred(Dep); } DefI->SU = SU; } @@ -470,24 +431,17 @@ void ScheduleDAGInstrs::addVRegUseDeps(SUnit *SU, unsigned OperIdx) { if (DefSU) { // The reaching Def lives within this scheduling region. // Create a data dependence. - // - // TODO: Handle "special" address latencies cleanly. - SDep dep(DefSU, SDep::Data, DefSU->Latency, Reg); - if (!UnitLatencies) { - // Adjust the dependence latency using operand def/use information, then - // allow the target to perform its own adjustments. - int DefOp = Def->findRegisterDefOperandIdx(Reg); - unsigned Latency = - TII->computeOperandLatency(InstrItins, Def, DefOp, MI, OperIdx); - dep.setLatency(Latency); - unsigned MinLatency = - TII->computeOperandLatency(InstrItins, Def, DefOp, MI, OperIdx, - /*FindMin=*/true); - dep.setMinLatency(MinLatency); - - const TargetSubtargetInfo &ST = TM.getSubtarget<TargetSubtargetInfo>(); - ST.adjustSchedDependency(DefSU, SU, const_cast<SDep &>(dep)); - } + SDep dep(DefSU, SDep::Data, Reg); + // Adjust the dependence latency using operand def/use information, then + // allow the target to perform its own adjustments. + int DefOp = Def->findRegisterDefOperandIdx(Reg); + dep.setLatency( + SchedModel.computeOperandLatency(Def, DefOp, MI, OperIdx, false)); + dep.setMinLatency( + SchedModel.computeOperandLatency(Def, DefOp, MI, OperIdx, true)); + + const TargetSubtargetInfo &ST = TM.getSubtarget<TargetSubtargetInfo>(); + ST.adjustSchedDependency(DefSU, SU, const_cast<SDep &>(dep)); SU->addPred(dep); } } @@ -495,7 +449,7 @@ void ScheduleDAGInstrs::addVRegUseDeps(SUnit *SU, unsigned OperIdx) { // Add antidependence to the following def of the vreg it uses. VReg2SUnitMap::iterator DefI = VRegDefs.find(Reg); if (DefI != VRegDefs.end() && DefI->SU != SU) - DefI->SU->addPred(SDep(SU, SDep::Anti, 0, Reg)); + DefI->SU->addPred(SDep(SU, SDep::Anti, Reg)); } /// Return true if MI is an instruction we are unable to reason about @@ -520,23 +474,29 @@ static inline bool isUnsafeMemoryObject(MachineInstr *MI, if ((*MI->memoperands_begin())->isVolatile() || MI->hasUnmodeledSideEffects()) return true; - const Value *V = (*MI->memoperands_begin())->getValue(); if (!V) return true; - V = getUnderlyingObject(V); - if (const PseudoSourceValue *PSV = dyn_cast<PseudoSourceValue>(V)) { - // Similarly to getUnderlyingObjectForInstr: - // 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)) + SmallVector<Value *, 4> Objs; + getUnderlyingObjects(V, Objs); + for (SmallVector<Value *, 4>::iterator I = Objs.begin(), + IE = Objs.end(); I != IE; ++I) { + V = *I; + + if (const PseudoSourceValue *PSV = dyn_cast<PseudoSourceValue>(V)) { + // Similarly to getUnderlyingObjectForInstr: + // 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 true; + } + + // Does this pointer refer to a distinct and identifiable object? + if (!isIdentifiedObject(V)) return true; } - // Does this pointer refer to a distinct and identifiable object? - if (!isIdentifiedObject(V)) - return true; return false; } @@ -635,8 +595,7 @@ iterateChainSucc(AliasAnalysis *AA, const MachineFrameInfo *MFI, // and stop descending. if (*Depth > 200 || MIsNeedChainEdge(AA, MFI, SUa->getInstr(), SUb->getInstr())) { - SUb->addPred(SDep(SUa, SDep::Order, /*Latency=*/0, /*Reg=*/0, - /*isNormalMemory=*/true)); + SUb->addPred(SDep(SUa, SDep::MayAliasMem)); return *Depth; } // Track current depth. @@ -667,9 +626,9 @@ static void adjustChainDeps(AliasAnalysis *AA, const MachineFrameInfo *MFI, if (SU == *I) continue; if (MIsNeedChainEdge(AA, MFI, SU->getInstr(), (*I)->getInstr())) { - unsigned Latency = ((*I)->getInstr()->mayLoad()) ? LatencyToLoad : 0; - (*I)->addPred(SDep(SU, SDep::Order, Latency, /*Reg=*/0, - /*isNormalMemory=*/true)); + SDep Dep(SU, SDep::MayAliasMem); + Dep.setLatency(((*I)->getInstr()->mayLoad()) ? LatencyToLoad : 0); + (*I)->addPred(Dep); } // Now go through all the chain successors and iterate from them. // Keep track of visited nodes. @@ -692,9 +651,11 @@ void addChainDependency (AliasAnalysis *AA, const MachineFrameInfo *MFI, // If this is a false dependency, // do not add the edge, but rememeber the rejected node. if (!EnableAASchedMI || - MIsNeedChainEdge(AA, MFI, SUa->getInstr(), SUb->getInstr())) - SUb->addPred(SDep(SUa, SDep::Order, TrueMemOrderLatency, /*Reg=*/0, - isNormalMemory)); + MIsNeedChainEdge(AA, MFI, SUa->getInstr(), SUb->getInstr())) { + SDep Dep(SUa, isNormalMemory ? SDep::MayAliasMem : SDep::Barrier); + Dep.setLatency(TrueMemOrderLatency); + SUb->addPred(Dep); + } else { // Duplicate entries should be ignored. RejectList.insert(SUb); @@ -732,10 +693,7 @@ void ScheduleDAGInstrs::initSUnits() { SU->isCommutable = MI->isCommutable(); // Assign the Latency field of SU using target-provided information. - if (UnitLatencies) - SU->Latency = 1; - else - computeLatency(SU); + SU->Latency = SchedModel.computeInstrLatency(SU->getInstr()); } } @@ -757,8 +715,8 @@ void ScheduleDAGInstrs::buildSchedGraph(AliasAnalysis *AA, // so that they can be given more precise dependencies. We track // separately the known memory locations that may alias and those // that are known not to alias - std::map<const Value *, SUnit *> AliasMemDefs, NonAliasMemDefs; - std::map<const Value *, std::vector<SUnit *> > AliasMemUses, NonAliasMemUses; + MapVector<const Value *, SUnit *> AliasMemDefs, NonAliasMemDefs; + MapVector<const Value *, std::vector<SUnit *> > AliasMemUses, NonAliasMemUses; std::set<SUnit*> RejectMemNodes; // Remove any stale debug info; sometimes BuildSchedGraph is called again @@ -782,17 +740,17 @@ void ScheduleDAGInstrs::buildSchedGraph(AliasAnalysis *AA, addSchedBarrierDeps(); // Walk the list of instructions, from bottom moving up. - MachineInstr *PrevMI = NULL; + MachineInstr *DbgMI = NULL; for (MachineBasicBlock::iterator MII = RegionEnd, MIE = RegionBegin; MII != MIE; --MII) { MachineInstr *MI = prior(MII); - if (MI && PrevMI) { - DbgValues.push_back(std::make_pair(PrevMI, MI)); - PrevMI = NULL; + if (MI && DbgMI) { + DbgValues.push_back(std::make_pair(DbgMI, MI)); + DbgMI = NULL; } if (MI->isDebugValue()) { - PrevMI = MI; + DbgMI = MI; continue; } if (RPTracker) { @@ -807,6 +765,7 @@ void ScheduleDAGInstrs::buildSchedGraph(AliasAnalysis *AA, assert(SU && "No SUnit mapped to this MI"); // Add register-based dependencies (data, anti, and output). + bool HasVRegDef = false; for (unsigned j = 0, n = MI->getNumOperands(); j != n; ++j) { const MachineOperand &MO = MI->getOperand(j); if (!MO.isReg()) continue; @@ -817,12 +776,26 @@ void ScheduleDAGInstrs::buildSchedGraph(AliasAnalysis *AA, addPhysRegDeps(SU, j); else { assert(!IsPostRA && "Virtual register encountered!"); - if (MO.isDef()) + if (MO.isDef()) { + HasVRegDef = true; addVRegDefDeps(SU, j); + } else if (MO.readsReg()) // ignore undef operands addVRegUseDeps(SU, j); } } + // If we haven't seen any uses in this scheduling region, create a + // dependence edge to ExitSU to model the live-out latency. This is required + // for vreg defs with no in-region use, and prefetches with no vreg def. + // + // FIXME: NumDataSuccs would be more precise than NumSuccs here. This + // check currently relies on being called before adding chain deps. + if (SU->NumSuccs == 0 && SU->Latency > 1 + && (HasVRegDef || MI->mayLoad())) { + SDep Dep(SU, SDep::Artificial); + Dep.setLatency(SU->Latency - 1); + ExitSU.addPred(Dep); + } // Add chain dependencies. // Chain dependencies used to enforce memory order should have @@ -837,18 +810,21 @@ void ScheduleDAGInstrs::buildSchedGraph(AliasAnalysis *AA, if (isGlobalMemoryObject(AA, MI)) { // Be conservative with these and add dependencies on all memory // references, even those that are known to not alias. - for (std::map<const Value *, SUnit *>::iterator I = + for (MapVector<const Value *, SUnit *>::iterator I = NonAliasMemDefs.begin(), E = NonAliasMemDefs.end(); I != E; ++I) { - I->second->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); + I->second->addPred(SDep(SU, SDep::Barrier)); } - for (std::map<const Value *, std::vector<SUnit *> >::iterator I = + for (MapVector<const Value *, std::vector<SUnit *> >::iterator I = NonAliasMemUses.begin(), E = NonAliasMemUses.end(); I != E; ++I) { - for (unsigned i = 0, e = I->second.size(); i != e; ++i) - I->second[i]->addPred(SDep(SU, SDep::Order, TrueMemOrderLatency)); + for (unsigned i = 0, e = I->second.size(); i != e; ++i) { + SDep Dep(SU, SDep::Barrier); + Dep.setLatency(TrueMemOrderLatency); + I->second[i]->addPred(Dep); + } } // Add SU to the barrier chain. if (BarrierChain) - BarrierChain->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); + BarrierChain->addPred(SDep(SU, SDep::Barrier)); BarrierChain = SU; // This is a barrier event that acts as a pivotal node in the DAG, // so it is safe to clear list of exposed nodes. @@ -872,10 +848,10 @@ void ScheduleDAGInstrs::buildSchedGraph(AliasAnalysis *AA, for (unsigned k = 0, m = PendingLoads.size(); k != m; ++k) addChainDependency(AA, MFI, SU, PendingLoads[k], RejectMemNodes, TrueMemOrderLatency); - for (std::map<const Value *, SUnit *>::iterator I = AliasMemDefs.begin(), + for (MapVector<const Value *, SUnit *>::iterator I = AliasMemDefs.begin(), E = AliasMemDefs.end(); I != E; ++I) addChainDependency(AA, MFI, SU, I->second, RejectMemNodes); - for (std::map<const Value *, std::vector<SUnit *> >::iterator I = + for (MapVector<const Value *, std::vector<SUnit *> >::iterator I = AliasMemUses.begin(), E = AliasMemUses.end(); I != E; ++I) { for (unsigned i = 0, e = I->second.size(); i != e; ++i) addChainDependency(AA, MFI, SU, I->second[i], RejectMemNodes, @@ -887,95 +863,115 @@ void ScheduleDAGInstrs::buildSchedGraph(AliasAnalysis *AA, AliasMemDefs.clear(); AliasMemUses.clear(); } else if (MI->mayStore()) { - bool MayAlias = true; - if (const Value *V = getUnderlyingObjectForInstr(MI, MFI, MayAlias)) { + SmallVector<std::pair<const Value *, bool>, 4> Objs; + getUnderlyingObjectsForInstr(MI, MFI, Objs); + + if (Objs.empty()) { + // Treat all other stores conservatively. + goto new_alias_chain; + } + + bool MayAlias = false; + for (SmallVector<std::pair<const Value *, bool>, 4>::iterator + K = Objs.begin(), KE = Objs.end(); K != KE; ++K) { + const Value *V = K->first; + bool ThisMayAlias = K->second; + if (ThisMayAlias) + MayAlias = true; + // A store to a specific PseudoSourceValue. Add precise dependencies. // Record the def in MemDefs, first adding a dep if there is // an existing def. - std::map<const Value *, SUnit *>::iterator I = - ((MayAlias) ? AliasMemDefs.find(V) : NonAliasMemDefs.find(V)); - std::map<const Value *, SUnit *>::iterator IE = - ((MayAlias) ? AliasMemDefs.end() : NonAliasMemDefs.end()); + MapVector<const Value *, SUnit *>::iterator I = + ((ThisMayAlias) ? AliasMemDefs.find(V) : NonAliasMemDefs.find(V)); + MapVector<const Value *, SUnit *>::iterator IE = + ((ThisMayAlias) ? AliasMemDefs.end() : NonAliasMemDefs.end()); if (I != IE) { - addChainDependency(AA, MFI, SU, I->second, RejectMemNodes, - 0, true); + addChainDependency(AA, MFI, SU, I->second, RejectMemNodes, 0, true); I->second = SU; } else { - if (MayAlias) + if (ThisMayAlias) AliasMemDefs[V] = SU; else NonAliasMemDefs[V] = SU; } // Handle the uses in MemUses, if there are any. - std::map<const Value *, std::vector<SUnit *> >::iterator J = - ((MayAlias) ? AliasMemUses.find(V) : NonAliasMemUses.find(V)); - std::map<const Value *, std::vector<SUnit *> >::iterator JE = - ((MayAlias) ? AliasMemUses.end() : NonAliasMemUses.end()); + MapVector<const Value *, std::vector<SUnit *> >::iterator J = + ((ThisMayAlias) ? AliasMemUses.find(V) : NonAliasMemUses.find(V)); + MapVector<const Value *, std::vector<SUnit *> >::iterator JE = + ((ThisMayAlias) ? AliasMemUses.end() : NonAliasMemUses.end()); if (J != JE) { for (unsigned i = 0, e = J->second.size(); i != e; ++i) addChainDependency(AA, MFI, SU, J->second[i], RejectMemNodes, TrueMemOrderLatency, true); J->second.clear(); } - if (MayAlias) { - // Add dependencies from all the PendingLoads, i.e. loads - // with no underlying object. - for (unsigned k = 0, m = PendingLoads.size(); k != m; ++k) - addChainDependency(AA, MFI, SU, PendingLoads[k], RejectMemNodes, - TrueMemOrderLatency); - // Add dependence on alias chain, if needed. - if (AliasChain) - addChainDependency(AA, MFI, SU, AliasChain, RejectMemNodes); - // But we also should check dependent instructions for the - // SU in question. - adjustChainDeps(AA, MFI, SU, &ExitSU, RejectMemNodes, - TrueMemOrderLatency); - } - // Add dependence on barrier chain, if needed. - // There is no point to check aliasing on barrier event. Even if - // SU and barrier _could_ be reordered, they should not. In addition, - // we have lost all RejectMemNodes below barrier. - if (BarrierChain) - BarrierChain->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); - } else { - // Treat all other stores conservatively. - goto new_alias_chain; } + if (MayAlias) { + // Add dependencies from all the PendingLoads, i.e. loads + // with no underlying object. + for (unsigned k = 0, m = PendingLoads.size(); k != m; ++k) + addChainDependency(AA, MFI, SU, PendingLoads[k], RejectMemNodes, + TrueMemOrderLatency); + // Add dependence on alias chain, if needed. + if (AliasChain) + addChainDependency(AA, MFI, SU, AliasChain, RejectMemNodes); + // But we also should check dependent instructions for the + // SU in question. + adjustChainDeps(AA, MFI, SU, &ExitSU, RejectMemNodes, + TrueMemOrderLatency); + } + // Add dependence on barrier chain, if needed. + // There is no point to check aliasing on barrier event. Even if + // SU and barrier _could_ be reordered, they should not. In addition, + // we have lost all RejectMemNodes below barrier. + if (BarrierChain) + BarrierChain->addPred(SDep(SU, SDep::Barrier)); if (!ExitSU.isPred(SU)) // Push store's up a bit to avoid them getting in between cmp // and branches. - ExitSU.addPred(SDep(SU, SDep::Order, 0, - /*Reg=*/0, /*isNormalMemory=*/false, - /*isMustAlias=*/false, - /*isArtificial=*/true)); + ExitSU.addPred(SDep(SU, SDep::Artificial)); } else if (MI->mayLoad()) { bool MayAlias = true; if (MI->isInvariantLoad(AA)) { // Invariant load, no chain dependencies needed! } else { - if (const Value *V = - getUnderlyingObjectForInstr(MI, MFI, MayAlias)) { - // A load from a specific PseudoSourceValue. Add precise dependencies. - std::map<const Value *, SUnit *>::iterator I = - ((MayAlias) ? AliasMemDefs.find(V) : NonAliasMemDefs.find(V)); - std::map<const Value *, SUnit *>::iterator IE = - ((MayAlias) ? AliasMemDefs.end() : NonAliasMemDefs.end()); - if (I != IE) - addChainDependency(AA, MFI, SU, I->second, RejectMemNodes, 0, true); - if (MayAlias) - AliasMemUses[V].push_back(SU); - else - NonAliasMemUses[V].push_back(SU); - } else { + SmallVector<std::pair<const Value *, bool>, 4> Objs; + getUnderlyingObjectsForInstr(MI, MFI, Objs); + + if (Objs.empty()) { // A load with no underlying object. Depend on all // potentially aliasing stores. - for (std::map<const Value *, SUnit *>::iterator I = + for (MapVector<const Value *, SUnit *>::iterator I = AliasMemDefs.begin(), E = AliasMemDefs.end(); I != E; ++I) addChainDependency(AA, MFI, SU, I->second, RejectMemNodes); PendingLoads.push_back(SU); MayAlias = true; + } else { + MayAlias = false; + } + + for (SmallVector<std::pair<const Value *, bool>, 4>::iterator + J = Objs.begin(), JE = Objs.end(); J != JE; ++J) { + const Value *V = J->first; + bool ThisMayAlias = J->second; + + if (ThisMayAlias) + MayAlias = true; + + // A load from a specific PseudoSourceValue. Add precise dependencies. + MapVector<const Value *, SUnit *>::iterator I = + ((ThisMayAlias) ? AliasMemDefs.find(V) : NonAliasMemDefs.find(V)); + MapVector<const Value *, SUnit *>::iterator IE = + ((ThisMayAlias) ? AliasMemDefs.end() : NonAliasMemDefs.end()); + if (I != IE) + addChainDependency(AA, MFI, SU, I->second, RejectMemNodes, 0, true); + if (ThisMayAlias) + AliasMemUses[V].push_back(SU); + else + NonAliasMemUses[V].push_back(SU); } if (MayAlias) adjustChainDeps(AA, MFI, SU, &ExitSU, RejectMemNodes, /*Latency=*/0); @@ -983,12 +979,12 @@ void ScheduleDAGInstrs::buildSchedGraph(AliasAnalysis *AA, if (MayAlias && AliasChain) addChainDependency(AA, MFI, SU, AliasChain, RejectMemNodes); if (BarrierChain) - BarrierChain->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); + BarrierChain->addPred(SDep(SU, SDep::Barrier)); } } } - if (PrevMI) - FirstDbgValue = PrevMI; + if (DbgMI) + FirstDbgValue = DbgMI; Defs.clear(); Uses.clear(); @@ -996,23 +992,8 @@ void ScheduleDAGInstrs::buildSchedGraph(AliasAnalysis *AA, PendingLoads.clear(); } -void ScheduleDAGInstrs::computeLatency(SUnit *SU) { - // Compute the latency for the node. We only provide a default for missing - // itineraries. Empty itineraries still have latency properties. - if (!InstrItins) { - SU->Latency = 1; - - // Simplistic target-independent heuristic: assume that loads take - // extra time. - if (SU->getInstr()->mayLoad()) - SU->Latency += 2; - } else { - SU->Latency = TII->getInstrLatency(InstrItins, SU->getInstr()); - } -} - void ScheduleDAGInstrs::dumpNode(const SUnit *SU) const { -#ifndef NDEBUG +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) SU->getInstr()->dump(); #endif } @@ -1034,3 +1015,219 @@ std::string ScheduleDAGInstrs::getGraphNodeLabel(const SUnit *SU) const { std::string ScheduleDAGInstrs::getDAGName() const { return "dag." + BB->getFullName(); } + +//===----------------------------------------------------------------------===// +// SchedDFSResult Implementation +//===----------------------------------------------------------------------===// + +namespace llvm { +/// \brief Internal state used to compute SchedDFSResult. +class SchedDFSImpl { + SchedDFSResult &R; + + /// Join DAG nodes into equivalence classes by their subtree. + IntEqClasses SubtreeClasses; + /// List PredSU, SuccSU pairs that represent data edges between subtrees. + std::vector<std::pair<const SUnit*, const SUnit*> > ConnectionPairs; + +public: + SchedDFSImpl(SchedDFSResult &r): R(r), SubtreeClasses(R.DFSData.size()) {} + + /// SubtreID is initialized to zero, set to itself to flag the root of a + /// subtree, set to the parent to indicate an interior node, + /// then set to a representative subtree ID during finalization. + bool isVisited(const SUnit *SU) const { + return R.DFSData[SU->NodeNum].SubtreeID; + } + + /// Initialize this node's instruction count. We don't need to flag the node + /// visited until visitPostorder because the DAG cannot have cycles. + void visitPreorder(const SUnit *SU) { + R.DFSData[SU->NodeNum].InstrCount = SU->getInstr()->isTransient() ? 0 : 1; + } + + /// Mark this node as either the root of a subtree or an interior + /// node. Increment the parent node's instruction count. + void visitPostorder(const SUnit *SU, const SDep *PredDep, const SUnit *Parent) { + R.DFSData[SU->NodeNum].SubtreeID = SU->NodeNum; + + // Join the child to its parent if they are connected via data dependence + // and do not exceed the limit. + if (!Parent || PredDep->getKind() != SDep::Data) + return; + + unsigned PredCnt = R.DFSData[SU->NodeNum].InstrCount; + if (PredCnt > R.SubtreeLimit) + return; + + R.DFSData[SU->NodeNum].SubtreeID = Parent->NodeNum; + + // Add the recently finished predecessor's bottom-up descendent count. + R.DFSData[Parent->NodeNum].InstrCount += PredCnt; + SubtreeClasses.join(Parent->NodeNum, SU->NodeNum); + } + + /// Determine whether the DFS cross edge should be considered a subtree edge + /// or a connection between subtrees. + void visitCross(const SDep &PredDep, const SUnit *Succ) { + if (PredDep.getKind() == SDep::Data) { + // If this is a cross edge to a root, join the subtrees. This happens when + // the root was first reached by a non-data dependence. + unsigned NodeNum = PredDep.getSUnit()->NodeNum; + unsigned PredCnt = R.DFSData[NodeNum].InstrCount; + if (R.DFSData[NodeNum].SubtreeID == NodeNum && PredCnt < R.SubtreeLimit) { + R.DFSData[NodeNum].SubtreeID = Succ->NodeNum; + R.DFSData[Succ->NodeNum].InstrCount += PredCnt; + SubtreeClasses.join(Succ->NodeNum, NodeNum); + return; + } + } + ConnectionPairs.push_back(std::make_pair(PredDep.getSUnit(), Succ)); + } + + /// Set each node's subtree ID to the representative ID and record connections + /// between trees. + void finalize() { + SubtreeClasses.compress(); + R.SubtreeConnections.resize(SubtreeClasses.getNumClasses()); + R.SubtreeConnectLevels.resize(SubtreeClasses.getNumClasses()); + DEBUG(dbgs() << R.getNumSubtrees() << " subtrees:\n"); + for (unsigned Idx = 0, End = R.DFSData.size(); Idx != End; ++Idx) { + R.DFSData[Idx].SubtreeID = SubtreeClasses[Idx]; + DEBUG(dbgs() << " SU(" << Idx << ") in tree " + << R.DFSData[Idx].SubtreeID << '\n'); + } + for (std::vector<std::pair<const SUnit*, const SUnit*> >::const_iterator + I = ConnectionPairs.begin(), E = ConnectionPairs.end(); + I != E; ++I) { + unsigned PredTree = SubtreeClasses[I->first->NodeNum]; + unsigned SuccTree = SubtreeClasses[I->second->NodeNum]; + if (PredTree == SuccTree) + continue; + unsigned Depth = I->first->getDepth(); + addConnection(PredTree, SuccTree, Depth); + addConnection(SuccTree, PredTree, Depth); + } + } + +protected: + /// Called by finalize() to record a connection between trees. + void addConnection(unsigned FromTree, unsigned ToTree, unsigned Depth) { + if (!Depth) + return; + + SmallVectorImpl<SchedDFSResult::Connection> &Connections = + R.SubtreeConnections[FromTree]; + for (SmallVectorImpl<SchedDFSResult::Connection>::iterator + I = Connections.begin(), E = Connections.end(); I != E; ++I) { + if (I->TreeID == ToTree) { + I->Level = std::max(I->Level, Depth); + return; + } + } + Connections.push_back(SchedDFSResult::Connection(ToTree, Depth)); + } +}; +} // namespace llvm + +namespace { +/// \brief Manage the stack used by a reverse depth-first search over the DAG. +class SchedDAGReverseDFS { + std::vector<std::pair<const SUnit*, SUnit::const_pred_iterator> > DFSStack; +public: + bool isComplete() const { return DFSStack.empty(); } + + void follow(const SUnit *SU) { + DFSStack.push_back(std::make_pair(SU, SU->Preds.begin())); + } + void advance() { ++DFSStack.back().second; } + + const SDep *backtrack() { + DFSStack.pop_back(); + return DFSStack.empty() ? 0 : llvm::prior(DFSStack.back().second); + } + + const SUnit *getCurr() const { return DFSStack.back().first; } + + SUnit::const_pred_iterator getPred() const { return DFSStack.back().second; } + + SUnit::const_pred_iterator getPredEnd() const { + return getCurr()->Preds.end(); + } +}; +} // anonymous + +/// Compute an ILP metric for all nodes in the subDAG reachable via depth-first +/// search from this root. +void SchedDFSResult::compute(ArrayRef<SUnit *> Roots) { + if (!IsBottomUp) + llvm_unreachable("Top-down ILP metric is unimplemnted"); + + SchedDFSImpl Impl(*this); + for (ArrayRef<const SUnit*>::const_iterator + RootI = Roots.begin(), RootE = Roots.end(); RootI != RootE; ++RootI) { + SchedDAGReverseDFS DFS; + Impl.visitPreorder(*RootI); + DFS.follow(*RootI); + for (;;) { + // Traverse the leftmost path as far as possible. + while (DFS.getPred() != DFS.getPredEnd()) { + const SDep &PredDep = *DFS.getPred(); + DFS.advance(); + // If the pred is already valid, skip it. We may preorder visit a node + // with InstrCount==0 more than once, but it won't affect heuristics + // because we don't care about cross edges to leaf copies. + if (Impl.isVisited(PredDep.getSUnit())) { + Impl.visitCross(PredDep, DFS.getCurr()); + continue; + } + Impl.visitPreorder(PredDep.getSUnit()); + DFS.follow(PredDep.getSUnit()); + } + // Visit the top of the stack in postorder and backtrack. + const SUnit *Child = DFS.getCurr(); + const SDep *PredDep = DFS.backtrack(); + Impl.visitPostorder(Child, PredDep, PredDep ? DFS.getCurr() : 0); + if (DFS.isComplete()) + break; + } + } + Impl.finalize(); +} + +/// The root of the given SubtreeID was just scheduled. For all subtrees +/// connected to this tree, record the depth of the connection so that the +/// nearest connected subtrees can be prioritized. +void SchedDFSResult::scheduleTree(unsigned SubtreeID) { + for (SmallVectorImpl<Connection>::const_iterator + I = SubtreeConnections[SubtreeID].begin(), + E = SubtreeConnections[SubtreeID].end(); I != E; ++I) { + SubtreeConnectLevels[I->TreeID] = + std::max(SubtreeConnectLevels[I->TreeID], I->Level); + DEBUG(dbgs() << " Tree: " << I->TreeID + << " @" << SubtreeConnectLevels[I->TreeID] << '\n'); + } +} + +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) +void ILPValue::print(raw_ostream &OS) const { + OS << InstrCount << " / " << Length << " = "; + if (!Length) + OS << "BADILP"; + else + OS << format("%g", ((double)InstrCount / Length)); +} + +void ILPValue::dump() const { + dbgs() << *this << '\n'; +} + +namespace llvm { + +raw_ostream &operator<<(raw_ostream &OS, const ILPValue &Val) { + Val.print(OS); + return OS; +} + +} // namespace llvm +#endif // !NDEBUG || LLVM_ENABLE_DUMP |