X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FScheduleDAGInstrs.cpp;h=39cad7f35d20d46b12dc660d349e598991c5dcd3;hb=a3e49ea99afc3c9f43953bdc3b3bd77970ed510d;hp=892903c2388b807eeeb6ea9de2570a90cb5c7cba;hpb=f22fd3f7b557a967b1edc1fa9ae770006a39e97c;p=oota-llvm.git diff --git a/lib/CodeGen/ScheduleDAGInstrs.cpp b/lib/CodeGen/ScheduleDAGInstrs.cpp index 892903c2388..39cad7f35d2 100644 --- a/lib/CodeGen/ScheduleDAGInstrs.cpp +++ b/lib/CodeGen/ScheduleDAGInstrs.cpp @@ -12,7 +12,6 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "misched" #include "llvm/CodeGen/ScheduleDAGInstrs.h" #include "llvm/ADT/MapVector.h" #include "llvm/ADT/SmallPtrSet.h" @@ -21,13 +20,14 @@ #include "llvm/Analysis/ValueTracking.h" #include "llvm/CodeGen/LiveIntervalAnalysis.h" #include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/CodeGen/MachineFrameInfo.h" +#include "llvm/CodeGen/MachineInstrBuilder.h" #include "llvm/CodeGen/MachineMemOperand.h" #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/PseudoSourceValue.h" #include "llvm/CodeGen/RegisterPressure.h" #include "llvm/CodeGen/ScheduleDFS.h" #include "llvm/IR/Operator.h" -#include "llvm/MC/MCInstrItineraries.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/Format.h" @@ -36,26 +36,33 @@ #include "llvm/Target/TargetMachine.h" #include "llvm/Target/TargetRegisterInfo.h" #include "llvm/Target/TargetSubtargetInfo.h" +#include + using namespace llvm; +#define DEBUG_TYPE "misched" + static cl::opt EnableAASchedMI("enable-aa-sched-mi", cl::Hidden, cl::ZeroOrMore, cl::init(false), - cl::desc("Enable use of AA during MI GAD construction")); + cl::desc("Enable use of AA during MI DAG construction")); + +static cl::opt UseTBAA("use-tbaa-in-sched-mi", cl::Hidden, + cl::init(true), cl::desc("Enable use of TBAA during MI DAG construction")); ScheduleDAGInstrs::ScheduleDAGInstrs(MachineFunction &mf, - const MachineLoopInfo &mli, - const MachineDominatorTree &mdt, - bool IsPostRAFlag, + const MachineLoopInfo *mli, + bool IsPostRAFlag, bool RemoveKillFlags, LiveIntervals *lis) - : ScheduleDAG(mf), MLI(mli), MDT(mdt), MFI(mf.getFrameInfo()), LIS(lis), - IsPostRA(IsPostRAFlag), CanHandleTerminators(false), FirstDbgValue(0) { + : ScheduleDAG(mf), MLI(mli), MFI(mf.getFrameInfo()), LIS(lis), + IsPostRA(IsPostRAFlag), RemoveKillFlags(RemoveKillFlags), + CanHandleTerminators(false), FirstDbgValue(nullptr) { 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(); - SchedModel.init(*ST.getSchedModel(), &ST, TII); + const TargetSubtargetInfo &ST = mf.getSubtarget(); + SchedModel.init(ST.getSchedModel(), &ST, TII); } /// getUnderlyingObjectFromInt - This is the function that does the work of @@ -89,19 +96,20 @@ static const Value *getUnderlyingObjectFromInt(const Value *V) { /// getUnderlyingObjects - This is a wrapper around GetUnderlyingObjects /// and adds support for basic ptrtoint+arithmetic+inttoptr sequences. static void getUnderlyingObjects(const Value *V, - SmallVectorImpl &Objects) { - SmallPtrSet Visited; + SmallVectorImpl &Objects, + const DataLayout &DL) { + SmallPtrSet Visited; SmallVector Working(1, V); do { V = Working.pop_back_val(); SmallVector Objs; - GetUnderlyingObjects(const_cast(V), Objs); + GetUnderlyingObjects(const_cast(V), Objs, DL); for (SmallVectorImpl::iterator I = Objs.begin(), IE = Objs.end(); I != IE; ++I) { V = *I; - if (!Visited.insert(V)) + if (!Visited.insert(V).second) continue; if (Operator::getOpcode(V) == Instruction::IntToPtr) { const Value *O = @@ -116,7 +124,8 @@ static void getUnderlyingObjects(const Value *V, } while (!Working.empty()); } -typedef SmallVector, 4> +typedef PointerUnion ValueType; +typedef SmallVector, 4> UnderlyingObjectsVector; /// getUnderlyingObjectsForInstr - If this machine instr has memory reference @@ -124,41 +133,47 @@ UnderlyingObjectsVector; /// object, return the Value for that object. static void getUnderlyingObjectsForInstr(const MachineInstr *MI, const MachineFrameInfo *MFI, - UnderlyingObjectsVector &Objects) { + UnderlyingObjectsVector &Objects, + const DataLayout &DL) { if (!MI->hasOneMemOperand() || - !(*MI->memoperands_begin())->getValue() || + (!(*MI->memoperands_begin())->getValue() && + !(*MI->memoperands_begin())->getPseudoValue()) || (*MI->memoperands_begin())->isVolatile()) return; + if (const PseudoSourceValue *PSV = + (*MI->memoperands_begin())->getPseudoValue()) { + // Function that contain tail calls don't have unique PseudoSourceValue + // objects. Two PseudoSourceValues might refer to the same or overlapping + // locations. The client code calling this function assumes this is not the + // case. So return a conservative answer of no known object. + if (MFI->hasTailCall()) + return; + + // 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)) { + bool MayAlias = PSV->mayAlias(MFI); + Objects.push_back(UnderlyingObjectsVector::value_type(PSV, MayAlias)); + } + return; + } + const Value *V = (*MI->memoperands_begin())->getValue(); if (!V) return; SmallVector Objs; - getUnderlyingObjects(V, Objs); - - for (SmallVectorImpl::iterator I = Objs.begin(), IE = Objs.end(); - I != IE; ++I) { - bool MayAlias = true; - V = *I; - - if (const PseudoSourceValue *PSV = dyn_cast(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. + getUnderlyingObjects(V, Objs, DL); - if (PSV->isAliased(MFI)) { - Objects.clear(); - return; - } - - MayAlias = PSV->mayAlias(MFI); - } else if (!isIdentifiedObject(V)) { + for (Value *V : Objs) { + if (!isIdentifiedObject(V)) { Objects.clear(); return; } - Objects.push_back(UnderlyingObjectsVector::value_type(V, MayAlias)); + Objects.push_back(UnderlyingObjectsVector::value_type(V, true)); } } @@ -168,7 +183,7 @@ void ScheduleDAGInstrs::startBlock(MachineBasicBlock *bb) { void ScheduleDAGInstrs::finishBlock() { // Subclasses should no longer refer to the old block. - BB = 0; + BB = nullptr; } /// Initialize the DAG and common scheduler state for the current scheduling @@ -178,14 +193,11 @@ void ScheduleDAGInstrs::finishBlock() { void ScheduleDAGInstrs::enterRegion(MachineBasicBlock *bb, MachineBasicBlock::iterator begin, MachineBasicBlock::iterator end, - unsigned endcount) { + unsigned regioninstrs) { assert(bb == BB && "startBlock should set BB"); RegionBegin = begin; RegionEnd = end; - EndIndex = endcount; - MISUnitMap.clear(); - - ScheduleDAG::clearDAG(); + NumRegionInstrs = regioninstrs; } /// Close the current scheduling region. Don't clear any state in case the @@ -203,7 +215,7 @@ void ScheduleDAGInstrs::exitRegion() { /// are too high to be hidden by the branch or when the liveout registers /// used by instructions in the fallthrough block. void ScheduleDAGInstrs::addSchedBarrierDeps() { - MachineInstr *ExitMI = RegionEnd != BB->end() ? &*RegionEnd : 0; + MachineInstr *ExitMI = RegionEnd != BB->end() ? &*RegionEnd : nullptr; ExitSU.setInstr(ExitMI); bool AllDepKnown = ExitMI && (ExitMI->isCall() || ExitMI->isBarrier()); @@ -230,11 +242,9 @@ void ScheduleDAGInstrs::addSchedBarrierDeps() { assert(Uses.empty() && "Uses in set before adding deps?"); 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; - if (!Uses.contains(Reg)) - Uses.insert(PhysRegSUOper(&ExitSU, -1, Reg)); + for (const auto &LI : (*SI)->liveins()) { + if (!Uses.contains(LI.PhysReg)) + Uses.insert(PhysRegSUOper(&ExitSU, -1, LI.PhysReg)); } } } @@ -246,7 +256,7 @@ void ScheduleDAGInstrs::addPhysRegDataDeps(SUnit *SU, unsigned OperIdx) { assert(MO.isDef() && "expect physreg def"); // Ask the target if address-backscheduling is desirable, and if so how much. - const TargetSubtargetInfo &ST = TM.getSubtarget(); + const TargetSubtargetInfo &ST = MF.getSubtarget(); for (MCRegAliasIterator Alias(MO.getReg(), TRI, true); Alias.isValid(); ++Alias) { @@ -260,7 +270,7 @@ void ScheduleDAGInstrs::addPhysRegDataDeps(SUnit *SU, unsigned OperIdx) { // Adjust the dependence latency using operand def/use information, // then allow the target to perform its own adjustments. int UseOp = I->OpIdx; - MachineInstr *RegUse = 0; + MachineInstr *RegUse = nullptr; SDep Dep; if (UseOp < 0) Dep = SDep(SU, SDep::Artificial); @@ -285,8 +295,8 @@ void ScheduleDAGInstrs::addPhysRegDataDeps(SUnit *SU, unsigned OperIdx) { /// this SUnit to following instructions in the same scheduling region that /// depend the physical register referenced at OperIdx. void ScheduleDAGInstrs::addPhysRegDeps(SUnit *SU, unsigned OperIdx) { - const MachineInstr *MI = SU->getInstr(); - const MachineOperand &MO = MI->getOperand(OperIdx); + MachineInstr *MI = SU->getInstr(); + MachineOperand &MO = MI->getOperand(OperIdx); // Optionally add output and anti dependencies. For anti // dependencies we use a latency of 0 because for a multi-issue @@ -324,6 +334,8 @@ void ScheduleDAGInstrs::addPhysRegDeps(SUnit *SU, unsigned OperIdx) { // retrieve the existing SUnits list for this register's uses. // Push this SUnit on the use list. Uses.insert(PhysRegSUOper(SU, OperIdx, MO.getReg())); + if (RemoveKillFlags) + MO.setIsKill(false); } else { addPhysRegDataDeps(SU, OperIdx); @@ -405,9 +417,19 @@ void ScheduleDAGInstrs::addVRegUseDeps(SUnit *SU, unsigned OperIdx) { MachineInstr *MI = SU->getInstr(); unsigned Reg = MI->getOperand(OperIdx).getReg(); + // Record this local VReg use. + VReg2UseMap::iterator UI = VRegUses.find(Reg); + for (; UI != VRegUses.end(); ++UI) { + if (UI->SU == SU) + break; + } + if (UI == VRegUses.end()) + VRegUses.insert(VReg2SUnit(Reg, SU)); + // Lookup this operand's reaching definition. assert(LIS && "vreg dependencies requires LiveIntervals"); - LiveRangeQuery LRQ(LIS->getInterval(Reg), LIS->getInstructionIndex(MI)); + LiveQueryResult LRQ + = LIS->getInterval(Reg).Query(LIS->getInstructionIndex(MI)); VNInfo *VNI = LRQ.valueIn(); // VNI will be valid because MachineOperand::readsReg() is checked by caller. @@ -425,7 +447,7 @@ void ScheduleDAGInstrs::addVRegUseDeps(SUnit *SU, unsigned OperIdx) { int DefOp = Def->findRegisterDefOperandIdx(Reg); dep.setLatency(SchedModel.computeOperandLatency(Def, DefOp, MI, OperIdx)); - const TargetSubtargetInfo &ST = TM.getSubtarget(); + const TargetSubtargetInfo &ST = MF.getSubtarget(); ST.adjustSchedDependency(DefSU, SU, const_cast(dep)); SU->addPred(dep); } @@ -450,7 +472,8 @@ static inline bool isGlobalMemoryObject(AliasAnalysis *AA, MachineInstr *MI) { // This MI might have either incomplete info, or known to be unsafe // to deal with (i.e. volatile object). static inline bool isUnsafeMemoryObject(MachineInstr *MI, - const MachineFrameInfo *MFI) { + const MachineFrameInfo *MFI, + const DataLayout &DL) { if (!MI || MI->memoperands_empty()) return true; // We purposefully do no check for hasOneMemOperand() here @@ -459,25 +482,22 @@ static inline bool isUnsafeMemoryObject(MachineInstr *MI, if ((*MI->memoperands_begin())->isVolatile() || MI->hasUnmodeledSideEffects()) return true; + + if ((*MI->memoperands_begin())->getPseudoValue()) { + // 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. + return true; + } + const Value *V = (*MI->memoperands_begin())->getValue(); if (!V) return true; SmallVector Objs; - getUnderlyingObjects(V, Objs); - for (SmallVectorImpl::iterator I = Objs.begin(), - IE = Objs.end(); I != IE; ++I) { - V = *I; - - if (const PseudoSourceValue *PSV = dyn_cast(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; - } - + getUnderlyingObjects(V, Objs, DL); + for (Value *V : Objs) { // Does this pointer refer to a distinct and identifiable object? if (!isIdentifiedObject(V)) return true; @@ -486,19 +506,32 @@ static inline bool isUnsafeMemoryObject(MachineInstr *MI, return false; } -/// This returns true if the two MIs need a chain edge betwee them. +/// This returns true if the two MIs need a chain edge between them. /// If these are not even memory operations, we still may need /// chain deps between them. The question really is - could /// these two MIs be reordered during scheduling from memory dependency /// point of view. static bool MIsNeedChainEdge(AliasAnalysis *AA, const MachineFrameInfo *MFI, - MachineInstr *MIa, + const DataLayout &DL, MachineInstr *MIa, MachineInstr *MIb) { + const MachineFunction *MF = MIa->getParent()->getParent(); + const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo(); + // Cover a trivial case - no edge is need to itself. if (MIa == MIb) return false; + + // Let the target decide if memory accesses cannot possibly overlap. + if ((MIa->mayLoad() || MIa->mayStore()) && + (MIb->mayLoad() || MIb->mayStore())) + if (TII->areMemAccessesTriviallyDisjoint(MIa, MIb, AA)) + return false; + + // FIXME: Need to handle multiple memory operands to support all targets. + if (!MIa->hasOneMemOperand() || !MIb->hasOneMemOperand()) + return true; - if (isUnsafeMemoryObject(MIa, MFI) || isUnsafeMemoryObject(MIb, MFI)) + if (isUnsafeMemoryObject(MIa, MFI, DL) || isUnsafeMemoryObject(MIb, MFI, DL)) return true; // If we are dealing with two "normal" loads, we do not need an edge @@ -513,9 +546,8 @@ static bool MIsNeedChainEdge(AliasAnalysis *AA, const MachineFrameInfo *MFI, MachineMemOperand *MMOa = *MIa->memoperands_begin(); MachineMemOperand *MMOb = *MIb->memoperands_begin(); - // FIXME: Need to handle multiple memory operands to support all targets. - if (!MIa->hasOneMemOperand() || !MIb->hasOneMemOperand()) - llvm_unreachable("Multiple memory operands."); + if (!MMOa->getValue() || !MMOb->getValue()) + return true; // The following interface to AA is fashioned after DAGCombiner::isAlias // and operates with MachineMemOperand offset with some important @@ -540,26 +572,26 @@ static bool MIsNeedChainEdge(AliasAnalysis *AA, const MachineFrameInfo *MFI, int64_t Overlapa = MMOa->getSize() + MMOa->getOffset() - MinOffset; int64_t Overlapb = MMOb->getSize() + MMOb->getOffset() - MinOffset; - AliasAnalysis::AliasResult AAResult = AA->alias( - AliasAnalysis::Location(MMOa->getValue(), Overlapa, - MMOa->getTBAAInfo()), - AliasAnalysis::Location(MMOb->getValue(), Overlapb, - MMOb->getTBAAInfo())); + AliasResult AAResult = + AA->alias(MemoryLocation(MMOa->getValue(), Overlapa, + UseTBAA ? MMOa->getAAInfo() : AAMDNodes()), + MemoryLocation(MMOb->getValue(), Overlapb, + UseTBAA ? MMOb->getAAInfo() : AAMDNodes())); - return (AAResult != AliasAnalysis::NoAlias); + return (AAResult != NoAlias); } /// This recursive function iterates over chain deps of SUb looking for /// "latest" node that needs a chain edge to SUa. -static unsigned -iterateChainSucc(AliasAnalysis *AA, const MachineFrameInfo *MFI, - SUnit *SUa, SUnit *SUb, SUnit *ExitSU, unsigned *Depth, - SmallPtrSet &Visited) { +static unsigned iterateChainSucc(AliasAnalysis *AA, const MachineFrameInfo *MFI, + const DataLayout &DL, SUnit *SUa, SUnit *SUb, + SUnit *ExitSU, unsigned *Depth, + SmallPtrSetImpl &Visited) { if (!SUa || !SUb || SUb == ExitSU) return *Depth; // Remember visited nodes. - if (!Visited.insert(SUb)) + if (!Visited.insert(SUb).second) return *Depth; // If there is _some_ dependency already in place, do not // descend any further. @@ -579,17 +611,17 @@ iterateChainSucc(AliasAnalysis *AA, const MachineFrameInfo *MFI, // add that edge to the predecessors chain of SUb, // and stop descending. if (*Depth > 200 || - MIsNeedChainEdge(AA, MFI, SUa->getInstr(), SUb->getInstr())) { + MIsNeedChainEdge(AA, MFI, DL, SUa->getInstr(), SUb->getInstr())) { SUb->addPred(SDep(SUa, SDep::MayAliasMem)); return *Depth; } // Track current depth. (*Depth)++; - // Iterate over chain dependencies only. + // Iterate over memory dependencies only. for (SUnit::const_succ_iterator I = SUb->Succs.begin(), E = SUb->Succs.end(); I != E; ++I) - if (I->isCtrl()) - iterateChainSucc (AA, MFI, SUa, I->getSUnit(), ExitSU, Depth, Visited); + if (I->isNormalMemoryOrBarrier()) + iterateChainSucc(AA, MFI, DL, SUa, I->getSUnit(), ExitSU, Depth, Visited); return *Depth; } @@ -598,7 +630,8 @@ iterateChainSucc(AliasAnalysis *AA, const MachineFrameInfo *MFI, /// checks whether SU can be aliasing any node dominated /// by it. static void adjustChainDeps(AliasAnalysis *AA, const MachineFrameInfo *MFI, - SUnit *SU, SUnit *ExitSU, std::set &CheckList, + const DataLayout &DL, SUnit *SU, SUnit *ExitSU, + std::set &CheckList, unsigned LatencyToLoad) { if (!SU) return; @@ -610,33 +643,33 @@ static void adjustChainDeps(AliasAnalysis *AA, const MachineFrameInfo *MFI, I != IE; ++I) { if (SU == *I) continue; - if (MIsNeedChainEdge(AA, MFI, SU->getInstr(), (*I)->getInstr())) { + if (MIsNeedChainEdge(AA, MFI, DL, SU->getInstr(), (*I)->getInstr())) { 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. + + // Iterate recursively over all previously added memory chain + // successors. Keep track of visited nodes. for (SUnit::const_succ_iterator J = (*I)->Succs.begin(), JE = (*I)->Succs.end(); J != JE; ++J) - if (J->isCtrl()) - iterateChainSucc (AA, MFI, SU, J->getSUnit(), - ExitSU, &Depth, Visited); + if (J->isNormalMemoryOrBarrier()) + iterateChainSucc(AA, MFI, DL, SU, J->getSUnit(), ExitSU, &Depth, + Visited); } } /// Check whether two objects need a chain edge, if so, add it /// otherwise remember the rejected SU. -static inline -void addChainDependency (AliasAnalysis *AA, const MachineFrameInfo *MFI, - SUnit *SUa, SUnit *SUb, - std::set &RejectList, - unsigned TrueMemOrderLatency = 0, - bool isNormalMemory = false) { +static inline void addChainDependency(AliasAnalysis *AA, + const MachineFrameInfo *MFI, + const DataLayout &DL, SUnit *SUa, + SUnit *SUb, std::set &RejectList, + unsigned TrueMemOrderLatency = 0, + bool isNormalMemory = false) { // 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())) { + // do not add the edge, but remember the rejected node. + if (MIsNeedChainEdge(AA, MFI, DL, SUa->getInstr(), SUb->getInstr())) { SDep Dep(SUa, isNormalMemory ? SDep::MayAliasMem : SDep::Barrier); Dep.setLatency(TrueMemOrderLatency); SUb->addPred(Dep); @@ -650,7 +683,7 @@ void addChainDependency (AliasAnalysis *AA, const MachineFrameInfo *MFI, } } -/// Create an SUnit for each real instruction, numbered in top-down toplological +/// Create an SUnit for each real instruction, numbered in top-down topological /// order. The instruction order A < B, implies that no edge exists from B to A. /// /// Map each real instruction to its SUnit. @@ -664,7 +697,7 @@ void addChainDependency (AliasAnalysis *AA, const MachineFrameInfo *MFI, void ScheduleDAGInstrs::initSUnits() { // We'll be allocating one SUnit for each real instruction in the region, // which is contained within a basic block. - SUnits.reserve(BB->size()); + SUnits.reserve(NumRegionInstrs); for (MachineBasicBlock::iterator I = RegionBegin; I != RegionEnd; ++I) { MachineInstr *MI = I; @@ -679,35 +712,73 @@ void ScheduleDAGInstrs::initSUnits() { // Assign the Latency field of SU using target-provided information. SU->Latency = SchedModel.computeInstrLatency(SU->getInstr()); + + // If this SUnit uses a reserved or unbuffered resource, mark it as such. + // + // Reserved resources block an instruction from issuing and stall the + // entire pipeline. These are identified by BufferSize=0. + // + // Unbuffered resources prevent execution of subsequent instructions that + // require the same resources. This is used for in-order execution pipelines + // within an out-of-order core. These are identified by BufferSize=1. + if (SchedModel.hasInstrSchedModel()) { + const MCSchedClassDesc *SC = getSchedClass(SU); + for (TargetSchedModel::ProcResIter + PI = SchedModel.getWriteProcResBegin(SC), + PE = SchedModel.getWriteProcResEnd(SC); PI != PE; ++PI) { + switch (SchedModel.getProcResource(PI->ProcResourceIdx)->BufferSize) { + case 0: + SU->hasReservedResource = true; + break; + case 1: + SU->isUnbuffered = true; + break; + default: + break; + } + } + } } } -/// If RegPressure is non null, compute register pressure as a side effect. The +/// If RegPressure is non-null, compute register pressure as a side effect. The /// DAG builder is an efficient place to do it because it already visits /// operands. void ScheduleDAGInstrs::buildSchedGraph(AliasAnalysis *AA, - RegPressureTracker *RPTracker) { + RegPressureTracker *RPTracker, + PressureDiffs *PDiffs) { + const TargetSubtargetInfo &ST = MF.getSubtarget(); + bool UseAA = EnableAASchedMI.getNumOccurrences() > 0 ? EnableAASchedMI + : ST.useAA(); + AliasAnalysis *AAForDep = UseAA ? AA : nullptr; + + MISUnitMap.clear(); + ScheduleDAG::clearDAG(); + // Create an SUnit for each real instruction. initSUnits(); + if (PDiffs) + PDiffs->init(SUnits.size()); + // We build scheduling units by walking a block's instruction list from bottom // to top. - // Remember where a generic side-effecting instruction is as we procede. - SUnit *BarrierChain = 0, *AliasChain = 0; + // Remember where a generic side-effecting instruction is as we proceed. + SUnit *BarrierChain = nullptr, *AliasChain = nullptr; // Memory references to specific known memory locations are tracked // 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 - MapVector AliasMemDefs, NonAliasMemDefs; - MapVector > AliasMemUses, NonAliasMemUses; + MapVector > AliasMemDefs, NonAliasMemDefs; + MapVector > AliasMemUses, NonAliasMemUses; std::set RejectMemNodes; // Remove any stale debug info; sometimes BuildSchedGraph is called again // without emitting the info from the previous call. DbgValues.clear(); - FirstDbgValue = NULL; + FirstDbgValue = nullptr; assert(Defs.empty() && Uses.empty() && "Only BuildGraph should update Defs/Uses"); @@ -715,39 +786,41 @@ void ScheduleDAGInstrs::buildSchedGraph(AliasAnalysis *AA, Uses.setUniverse(TRI->getNumRegs()); assert(VRegDefs.empty() && "Only BuildSchedGraph may access VRegDefs"); - // FIXME: Allow SparseSet to reserve space for the creation of virtual - // registers during scheduling. Don't artificially inflate the Universe - // because we want to assert that vregs are not created during DAG building. + VRegUses.clear(); VRegDefs.setUniverse(MRI.getNumVirtRegs()); + VRegUses.setUniverse(MRI.getNumVirtRegs()); // Model data dependencies between instructions being scheduled and the // ExitSU. addSchedBarrierDeps(); // Walk the list of instructions, from bottom moving up. - MachineInstr *DbgMI = NULL; + MachineInstr *DbgMI = nullptr; for (MachineBasicBlock::iterator MII = RegionEnd, MIE = RegionBegin; MII != MIE; --MII) { - MachineInstr *MI = prior(MII); + MachineInstr *MI = std::prev(MII); if (MI && DbgMI) { DbgValues.push_back(std::make_pair(DbgMI, MI)); - DbgMI = NULL; + DbgMI = nullptr; } if (MI->isDebugValue()) { DbgMI = MI; continue; } + SUnit *SU = MISUnitMap[MI]; + assert(SU && "No SUnit mapped to this MI"); + if (RPTracker) { - RPTracker->recede(); - assert(RPTracker->getPos() == prior(MII) && "RPTracker can't find MI"); + PressureDiff *PDiff = PDiffs ? &(*PDiffs)[SU->NodeNum] : nullptr; + RPTracker->recede(/*LiveUses=*/nullptr, PDiff); + assert(RPTracker->getPos() == std::prev(MII) && + "RPTracker can't find MI"); } - assert((CanHandleTerminators || (!MI->isTerminator() && !MI->isLabel())) && - "Cannot schedule terminators or labels!"); - - SUnit *SU = MISUnitMap[MI]; - assert(SU && "No SUnit mapped to this MI"); + assert( + (CanHandleTerminators || (!MI->isTerminator() && !MI->isPosition())) && + "Cannot schedule terminators or labels!"); // Add register-based dependencies (data, anti, and output). bool HasVRegDef = false; @@ -795,11 +868,13 @@ 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 (MapVector::iterator I = + for (MapVector >::iterator I = NonAliasMemDefs.begin(), E = NonAliasMemDefs.end(); I != E; ++I) { - I->second->addPred(SDep(SU, SDep::Barrier)); + for (unsigned i = 0, e = I->second.size(); i != e; ++i) { + I->second[i]->addPred(SDep(SU, SDep::Barrier)); + } } - for (MapVector >::iterator I = + for (MapVector >::iterator I = NonAliasMemUses.begin(), E = NonAliasMemUses.end(); I != E; ++I) { for (unsigned i = 0, e = I->second.size(); i != e; ++i) { SDep Dep(SU, SDep::Barrier); @@ -813,7 +888,7 @@ void ScheduleDAGInstrs::buildSchedGraph(AliasAnalysis *AA, 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. - adjustChainDeps(AA, MFI, SU, &ExitSU, RejectMemNodes, + adjustChainDeps(AA, MFI, MF.getDataLayout(), SU, &ExitSU, RejectMemNodes, TrueMemOrderLatency); RejectMemNodes.clear(); NonAliasMemDefs.clear(); @@ -821,35 +896,46 @@ void ScheduleDAGInstrs::buildSchedGraph(AliasAnalysis *AA, // fall-through new_alias_chain: - // Chain all possibly aliasing memory references though SU. + // Chain all possibly aliasing memory references through SU. if (AliasChain) { unsigned ChainLatency = 0; if (AliasChain->getInstr()->mayLoad()) ChainLatency = TrueMemOrderLatency; - addChainDependency(AA, MFI, SU, AliasChain, RejectMemNodes, - ChainLatency); + addChainDependency(AAForDep, MFI, MF.getDataLayout(), SU, AliasChain, + RejectMemNodes, ChainLatency); } AliasChain = SU; for (unsigned k = 0, m = PendingLoads.size(); k != m; ++k) - addChainDependency(AA, MFI, SU, PendingLoads[k], RejectMemNodes, + addChainDependency(AAForDep, MFI, MF.getDataLayout(), SU, + PendingLoads[k], RejectMemNodes, TrueMemOrderLatency); - for (MapVector::iterator I = AliasMemDefs.begin(), - E = AliasMemDefs.end(); I != E; ++I) - addChainDependency(AA, MFI, SU, I->second, RejectMemNodes); - for (MapVector >::iterator I = + for (MapVector >::iterator I = + AliasMemDefs.begin(), E = AliasMemDefs.end(); I != E; ++I) { + for (unsigned i = 0, e = I->second.size(); i != e; ++i) + addChainDependency(AAForDep, MFI, MF.getDataLayout(), SU, + I->second[i], RejectMemNodes); + } + for (MapVector >::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, - TrueMemOrderLatency); + addChainDependency(AAForDep, MFI, MF.getDataLayout(), SU, + I->second[i], RejectMemNodes, TrueMemOrderLatency); } - adjustChainDeps(AA, MFI, SU, &ExitSU, RejectMemNodes, + adjustChainDeps(AA, MFI, MF.getDataLayout(), SU, &ExitSU, RejectMemNodes, TrueMemOrderLatency); PendingLoads.clear(); AliasMemDefs.clear(); AliasMemUses.clear(); } else if (MI->mayStore()) { + // 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)); + UnderlyingObjectsVector Objs; - getUnderlyingObjectsForInstr(MI, MFI, Objs); + getUnderlyingObjectsForInstr(MI, MFI, Objs, MF.getDataLayout()); if (Objs.empty()) { // Treat all other stores conservatively. @@ -859,7 +945,7 @@ void ScheduleDAGInstrs::buildSchedGraph(AliasAnalysis *AA, bool MayAlias = false; for (UnderlyingObjectsVector::iterator K = Objs.begin(), KE = Objs.end(); K != KE; ++K) { - const Value *V = K->getPointer(); + ValueType V = K->getPointer(); bool ThisMayAlias = K->getInt(); if (ThisMayAlias) MayAlias = true; @@ -867,27 +953,39 @@ void ScheduleDAGInstrs::buildSchedGraph(AliasAnalysis *AA, // A store to a specific PseudoSourceValue. Add precise dependencies. // Record the def in MemDefs, first adding a dep if there is // an existing def. - MapVector::iterator I = + MapVector >::iterator I = ((ThisMayAlias) ? AliasMemDefs.find(V) : NonAliasMemDefs.find(V)); - MapVector::iterator IE = + MapVector >::iterator IE = ((ThisMayAlias) ? AliasMemDefs.end() : NonAliasMemDefs.end()); if (I != IE) { - addChainDependency(AA, MFI, SU, I->second, RejectMemNodes, 0, true); - I->second = SU; + for (unsigned i = 0, e = I->second.size(); i != e; ++i) + addChainDependency(AAForDep, MFI, MF.getDataLayout(), SU, + I->second[i], RejectMemNodes, 0, true); + + // If we're not using AA, then we only need one store per object. + if (!AAForDep) + I->second.clear(); + I->second.push_back(SU); } else { - if (ThisMayAlias) - AliasMemDefs[V] = SU; - else - NonAliasMemDefs[V] = SU; + if (ThisMayAlias) { + if (!AAForDep) + AliasMemDefs[V].clear(); + AliasMemDefs[V].push_back(SU); + } else { + if (!AAForDep) + NonAliasMemDefs[V].clear(); + NonAliasMemDefs[V].push_back(SU); + } } // Handle the uses in MemUses, if there are any. - MapVector >::iterator J = + MapVector >::iterator J = ((ThisMayAlias) ? AliasMemUses.find(V) : NonAliasMemUses.find(V)); - MapVector >::iterator JE = + MapVector >::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, + addChainDependency(AAForDep, MFI, MF.getDataLayout(), SU, + J->second[i], RejectMemNodes, TrueMemOrderLatency, true); J->second.clear(); } @@ -896,41 +994,32 @@ void ScheduleDAGInstrs::buildSchedGraph(AliasAnalysis *AA, // 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, + addChainDependency(AAForDep, MFI, MF.getDataLayout(), 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); + addChainDependency(AAForDep, MFI, MF.getDataLayout(), SU, AliasChain, + RejectMemNodes); } - // 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::Artificial)); + adjustChainDeps(AA, MFI, MF.getDataLayout(), SU, &ExitSU, RejectMemNodes, + TrueMemOrderLatency); } else if (MI->mayLoad()) { bool MayAlias = true; if (MI->isInvariantLoad(AA)) { // Invariant load, no chain dependencies needed! } else { UnderlyingObjectsVector Objs; - getUnderlyingObjectsForInstr(MI, MFI, Objs); + getUnderlyingObjectsForInstr(MI, MFI, Objs, MF.getDataLayout()); if (Objs.empty()) { // A load with no underlying object. Depend on all // potentially aliasing stores. - for (MapVector::iterator I = + for (MapVector >::iterator I = AliasMemDefs.begin(), E = AliasMemDefs.end(); I != E; ++I) - addChainDependency(AA, MFI, SU, I->second, RejectMemNodes); + for (unsigned i = 0, e = I->second.size(); i != e; ++i) + addChainDependency(AAForDep, MFI, MF.getDataLayout(), SU, + I->second[i], RejectMemNodes); PendingLoads.push_back(SU); MayAlias = true; @@ -940,29 +1029,33 @@ void ScheduleDAGInstrs::buildSchedGraph(AliasAnalysis *AA, for (UnderlyingObjectsVector::iterator J = Objs.begin(), JE = Objs.end(); J != JE; ++J) { - const Value *V = J->getPointer(); + ValueType V = J->getPointer(); bool ThisMayAlias = J->getInt(); if (ThisMayAlias) MayAlias = true; // A load from a specific PseudoSourceValue. Add precise dependencies. - MapVector::iterator I = + MapVector >::iterator I = ((ThisMayAlias) ? AliasMemDefs.find(V) : NonAliasMemDefs.find(V)); - MapVector::iterator IE = + MapVector >::iterator IE = ((ThisMayAlias) ? AliasMemDefs.end() : NonAliasMemDefs.end()); if (I != IE) - addChainDependency(AA, MFI, SU, I->second, RejectMemNodes, 0, true); + for (unsigned i = 0, e = I->second.size(); i != e; ++i) + addChainDependency(AAForDep, MFI, MF.getDataLayout(), SU, + I->second[i], 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); + adjustChainDeps(AA, MFI, MF.getDataLayout(), SU, &ExitSU, + RejectMemNodes, /*Latency=*/0); // Add dependencies on alias and barrier chains, if needed. if (MayAlias && AliasChain) - addChainDependency(AA, MFI, SU, AliasChain, RejectMemNodes); + addChainDependency(AAForDep, MFI, MF.getDataLayout(), SU, AliasChain, + RejectMemNodes); if (BarrierChain) BarrierChain->addPred(SDep(SU, SDep::Barrier)); } @@ -977,6 +1070,194 @@ void ScheduleDAGInstrs::buildSchedGraph(AliasAnalysis *AA, PendingLoads.clear(); } +/// \brief Initialize register live-range state for updating kills. +void ScheduleDAGInstrs::startBlockForKills(MachineBasicBlock *BB) { + // Start with no live registers. + LiveRegs.reset(); + + // Examine the live-in regs of all successors. + for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), + SE = BB->succ_end(); SI != SE; ++SI) { + for (const auto &LI : (*SI)->liveins()) { + // Repeat, for reg and all subregs. + for (MCSubRegIterator SubRegs(LI.PhysReg, TRI, /*IncludeSelf=*/true); + SubRegs.isValid(); ++SubRegs) + LiveRegs.set(*SubRegs); + } + } +} + +/// \brief If we change a kill flag on the bundle instruction implicit register +/// operands, then we also need to propagate that to any instructions inside +/// the bundle which had the same kill state. +static void toggleBundleKillFlag(MachineInstr *MI, unsigned Reg, + bool NewKillState) { + if (MI->getOpcode() != TargetOpcode::BUNDLE) + return; + + // Walk backwards from the last instruction in the bundle to the first. + // Once we set a kill flag on an instruction, we bail out, as otherwise we + // might set it on too many operands. We will clear as many flags as we + // can though. + MachineBasicBlock::instr_iterator Begin = MI; + MachineBasicBlock::instr_iterator End = getBundleEnd(MI); + while (Begin != End) { + for (MachineOperand &MO : (--End)->operands()) { + if (!MO.isReg() || MO.isDef() || Reg != MO.getReg()) + continue; + + // DEBUG_VALUE nodes do not contribute to code generation and should + // always be ignored. Failure to do so may result in trying to modify + // KILL flags on DEBUG_VALUE nodes, which is distressing. + if (MO.isDebug()) + continue; + + // If the register has the internal flag then it could be killing an + // internal def of the register. In this case, just skip. We only want + // to toggle the flag on operands visible outside the bundle. + if (MO.isInternalRead()) + continue; + + if (MO.isKill() == NewKillState) + continue; + MO.setIsKill(NewKillState); + if (NewKillState) + return; + } + } +} + +bool ScheduleDAGInstrs::toggleKillFlag(MachineInstr *MI, MachineOperand &MO) { + // Setting kill flag... + if (!MO.isKill()) { + MO.setIsKill(true); + toggleBundleKillFlag(MI, MO.getReg(), true); + return false; + } + + // If MO itself is live, clear the kill flag... + if (LiveRegs.test(MO.getReg())) { + MO.setIsKill(false); + toggleBundleKillFlag(MI, MO.getReg(), false); + return false; + } + + // If any subreg of MO is live, then create an imp-def for that + // subreg and keep MO marked as killed. + MO.setIsKill(false); + toggleBundleKillFlag(MI, MO.getReg(), false); + bool AllDead = true; + const unsigned SuperReg = MO.getReg(); + MachineInstrBuilder MIB(MF, MI); + for (MCSubRegIterator SubRegs(SuperReg, TRI); SubRegs.isValid(); ++SubRegs) { + if (LiveRegs.test(*SubRegs)) { + MIB.addReg(*SubRegs, RegState::ImplicitDefine); + AllDead = false; + } + } + + if(AllDead) { + MO.setIsKill(true); + toggleBundleKillFlag(MI, MO.getReg(), true); + } + return false; +} + +// FIXME: Reuse the LivePhysRegs utility for this. +void ScheduleDAGInstrs::fixupKills(MachineBasicBlock *MBB) { + DEBUG(dbgs() << "Fixup kills for BB#" << MBB->getNumber() << '\n'); + + LiveRegs.resize(TRI->getNumRegs()); + BitVector killedRegs(TRI->getNumRegs()); + + 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; + if (MI->isDebugValue()) + continue; + + // 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.isRegMask()) + LiveRegs.clearBitsNotInMask(MO.getRegMask()); + 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; + + // Repeat for reg and all subregs. + for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true); + SubRegs.isValid(); ++SubRegs) + LiveRegs.reset(*SubRegs); + } + + // Examine all used registers and set/clear kill flag. When a + // register is used multiple times we only set the kill flag on + // the first use. Don't set kill flags on undef operands. + killedRegs.reset(); + 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) || MRI.isReserved(Reg)) continue; + + bool kill = false; + if (!killedRegs.test(Reg)) { + kill = true; + // A register is not killed if any subregs are live... + for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { + if (LiveRegs.test(*SubRegs)) { + kill = false; + break; + } + } + + // If subreg is not live, then register is killed if it became + // live in this instruction + if (kill) + kill = !LiveRegs.test(Reg); + } + + if (MO.isKill() != kill) { + DEBUG(dbgs() << "Fixing " << MO << " in "); + // Warning: toggleKillFlag may invalidate MO. + toggleKillFlag(MI, MO); + DEBUG(MI->dump()); + DEBUG(if (MI->getOpcode() == TargetOpcode::BUNDLE) { + MachineBasicBlock::instr_iterator Begin = MI; + MachineBasicBlock::instr_iterator End = getBundleEnd(MI); + while (++Begin != End) + DEBUG(Begin->dump()); + }); + } + + killedRegs.set(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) || MRI.isReserved(Reg)) continue; + + for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true); + SubRegs.isValid(); ++SubRegs) + LiveRegs.set(*SubRegs); + } + } +} + void ScheduleDAGInstrs::dumpNode(const SUnit *SU) const { #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) SU->getInstr()->dump(); @@ -991,7 +1272,7 @@ std::string ScheduleDAGInstrs::getGraphNodeLabel(const SUnit *SU) const { else if (SU == &ExitSU) oss << ""; else - SU->getInstr()->print(oss, &TM, /*SkipOpers=*/true); + SU->getInstr()->print(oss, /*SkipOpers=*/true); return oss.str(); } @@ -1212,7 +1493,7 @@ public: const SDep *backtrack() { DFSStack.pop_back(); - return DFSStack.empty() ? 0 : llvm::prior(DFSStack.back().second); + return DFSStack.empty() ? nullptr : std::prev(DFSStack.back().second); } const SUnit *getCurr() const { return DFSStack.back().first; } @@ -1295,7 +1576,7 @@ void SchedDFSResult::scheduleTree(unsigned SubtreeID) { } } -#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) +LLVM_DUMP_METHOD void ILPValue::print(raw_ostream &OS) const { OS << InstrCount << " / " << Length << " = "; if (!Length) @@ -1304,16 +1585,17 @@ void ILPValue::print(raw_ostream &OS) const { OS << format("%g", ((double)InstrCount / Length)); } +LLVM_DUMP_METHOD void ILPValue::dump() const { dbgs() << *this << '\n'; } namespace llvm { +LLVM_DUMP_METHOD raw_ostream &operator<<(raw_ostream &OS, const ILPValue &Val) { Val.print(OS); return OS; } } // namespace llvm -#endif // !NDEBUG || LLVM_ENABLE_DUMP