X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FScheduleDAGInstrs.cpp;h=aa45a6861cabfe8904f9a5533ab823dc00ac5a71;hb=661afe75e81431a66de3ed8e22d5aa91443367b3;hp=8cab9fbbe5f60832d4d5950097b68ea577c6a705;hpb=84b454d1a270a5d685e01686ed15e68c44b0b56a;p=oota-llvm.git diff --git a/lib/CodeGen/ScheduleDAGInstrs.cpp b/lib/CodeGen/ScheduleDAGInstrs.cpp index 8cab9fbbe5f..aa45a6861ca 100644 --- a/lib/CodeGen/ScheduleDAGInstrs.cpp +++ b/lib/CodeGen/ScheduleDAGInstrs.cpp @@ -13,7 +13,6 @@ //===----------------------------------------------------------------------===// #define DEBUG_TYPE "sched-instrs" -#include "ScheduleDAGInstrs.h" #include "llvm/Operator.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/ValueTracking.h" @@ -22,44 +21,38 @@ #include "llvm/CodeGen/MachineMemOperand.h" #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/PseudoSourceValue.h" +#include "llvm/CodeGen/RegisterPressure.h" +#include "llvm/CodeGen/ScheduleDAGInstrs.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/raw_ostream.h" #include "llvm/ADT/SmallSet.h" +#include "llvm/ADT/SmallPtrSet.h" using namespace llvm; +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")); + ScheduleDAGInstrs::ScheduleDAGInstrs(MachineFunction &mf, const MachineLoopInfo &mli, const MachineDominatorTree &mdt, bool IsPostRAFlag, LiveIntervals *lis) - : ScheduleDAG(mf), MLI(mli), MDT(mdt), MFI(mf.getFrameInfo()), - InstrItins(mf.getTarget().getInstrItineraryData()), IsPostRA(IsPostRAFlag), - LIS(lis), UnitLatencies(false), LoopRegs(MLI, 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"); -} -/// Run - perform scheduling. -/// -void ScheduleDAGInstrs::Run(MachineBasicBlock *bb, - MachineBasicBlock::iterator begin, - MachineBasicBlock::iterator end, - unsigned endcount) { - BB = bb; - Begin = begin; - InsertPosIndex = endcount; - - // Check to see if the scheduler cares about latencies. - UnitLatencies = ForceUnitLatencies(); - - ScheduleDAG::Run(bb, end); + const TargetSubtargetInfo &ST = TM.getSubtarget(); + SchedModel.init(*ST.getSchedModel(), &ST, TII); } /// getUnderlyingObjectFromInt - This is the function that does the work of @@ -141,28 +134,53 @@ static const Value *getUnderlyingObjectForInstr(const MachineInstr *MI, return 0; } -void ScheduleDAGInstrs::StartBlock(MachineBasicBlock *BB) { - LoopRegs.Deps.clear(); - if (MachineLoop *ML = MLI.getLoopFor(BB)) - if (BB == ML->getLoopLatch()) - LoopRegs.VisitLoop(ML); +void ScheduleDAGInstrs::startBlock(MachineBasicBlock *bb) { + BB = bb; +} + +void ScheduleDAGInstrs::finishBlock() { + // Subclasses should no longer refer to the old block. + BB = 0; } /// Initialize the map with the number of registers. -void ScheduleDAGInstrs::Reg2SUnitsMap::setRegLimit(unsigned Limit) { +void Reg2SUnitsMap::setRegLimit(unsigned Limit) { PhysRegSet.setUniverse(Limit); SUnits.resize(Limit); } /// Clear the map without deallocating storage. -void ScheduleDAGInstrs::Reg2SUnitsMap::clear() { +void Reg2SUnitsMap::clear() { for (const_iterator I = reg_begin(), E = reg_end(); I != E; ++I) { SUnits[*I].clear(); } PhysRegSet.clear(); } -/// AddSchedBarrierDeps - Add dependencies from instructions in the current +/// Initialize the DAG and common scheduler state for the current scheduling +/// region. This does not actually create the DAG, only clears it. The +/// scheduling driver may call BuildSchedGraph multiple times per scheduling +/// region. +void ScheduleDAGInstrs::enterRegion(MachineBasicBlock *bb, + MachineBasicBlock::iterator begin, + MachineBasicBlock::iterator end, + unsigned endcount) { + assert(bb == BB && "startBlock should set BB"); + RegionBegin = begin; + RegionEnd = end; + EndIndex = endcount; + MISUnitMap.clear(); + + ScheduleDAG::clearDAG(); +} + +/// Close the current scheduling region. Don't clear any state in case the +/// driver wants to refer to the previous scheduling region. +void ScheduleDAGInstrs::exitRegion() { + // Nothing to do. +} + +/// addSchedBarrierDeps - Add dependencies from instructions in the current /// list of instructions being scheduled to scheduling barrier by adding /// the exit SU to the register defs and use list. This is because we want to /// make sure instructions which define registers that are either used by @@ -170,8 +188,8 @@ void ScheduleDAGInstrs::Reg2SUnitsMap::clear() { /// especially important when the definition latency of the return value(s) /// 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 = InsertPos != BB->end() ? &*InsertPos : 0; +void ScheduleDAGInstrs::addSchedBarrierDeps() { + MachineInstr *ExitMI = RegionEnd != BB->end() ? &*RegionEnd : 0; ExitSU.setInstr(ExitMI); bool AllDepKnown = ExitMI && (ExitMI->isCall() || ExitMI->isBarrier()); @@ -185,70 +203,60 @@ void ScheduleDAGInstrs::AddSchedBarrierDeps() { if (Reg == 0) continue; if (TRI->isPhysicalRegister(Reg)) - Uses[Reg].push_back(&ExitSU); - else + Uses[Reg].push_back(PhysRegSUOper(&ExitSU, -1)); + else { assert(!IsPostRA && "Virtual register encountered after regalloc."); + addVRegUseDeps(&ExitSU, i); + } } } else { // For others, e.g. fallthrough, conditional branch, assume the exit // uses all the registers that are livein to the successor blocks. - SmallSet Seen; + 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 (Seen.insert(Reg)) - Uses[Reg].push_back(&ExitSU); + if (!Uses.contains(Reg)) + Uses[Reg].push_back(PhysRegSUOper(&ExitSU, -1)); } } } /// MO is an operand of SU's instruction that defines a physical register. Add /// data dependencies from SU to any uses of the physical register. -void ScheduleDAGInstrs::addPhysRegDataDeps(SUnit *SU, - const MachineOperand &MO) { +void ScheduleDAGInstrs::addPhysRegDataDeps(SUnit *SU, unsigned OperIdx) { + const MachineOperand &MO = SU->getInstr()->getOperand(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(); - unsigned SpecialAddressLatency = ST.getSpecialAddressLatency(); - unsigned DataLatency = SU->Latency; - for (const uint16_t *Alias = TRI->getOverlaps(MO.getReg()); *Alias; ++Alias) { + for (MCRegAliasIterator Alias(MO.getReg(), TRI, true); + Alias.isValid(); ++Alias) { if (!Uses.contains(*Alias)) continue; - std::vector &UseList = Uses[*Alias]; + std::vector &UseList = Uses[*Alias]; for (unsigned i = 0, e = UseList.size(); i != e; ++i) { - SUnit *UseSU = UseList[i]; + SUnit *UseSU = UseList[i].SU; if (UseSU == SU) continue; - 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) { - MachineInstr *UseMI = UseSU->getInstr(); - 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. - const SDep& dep = SDep(SU, SDep::Data, LDataLatency, *Alias); - if (!UnitLatencies) { - ComputeOperandLatency(SU, UseSU, const_cast(dep)); - ST.adjustSchedDependency(SU, UseSU, const_cast(dep)); - } + + SDep dep(SU, SDep::Data, 1, *Alias); + + // Adjust the dependence latency using operand def/use information, + // then allow the target to perform its own adjustments. + int UseOp = UseList[i].OpIdx; + MachineInstr *RegUse = UseOp < 0 ? 0 : UseSU->getInstr(); + dep.setLatency( + SchedModel.computeOperandLatency(SU->getInstr(), OperIdx, + RegUse, UseOp, /*FindMin=*/false)); + dep.setMinLatency( + SchedModel.computeOperandLatency(SU->getInstr(), OperIdx, + RegUse, UseOp, /*FindMin=*/true)); + + ST.adjustSchedDependency(SU, UseSU, dep); UseSU->addPred(dep); } } @@ -268,12 +276,13 @@ void ScheduleDAGInstrs::addPhysRegDeps(SUnit *SU, unsigned OperIdx) { // 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; - for (const uint16_t *Alias = TRI->getOverlaps(MO.getReg()); *Alias; ++Alias) { + for (MCRegAliasIterator Alias(MO.getReg(), TRI, true); + Alias.isValid(); ++Alias) { if (!Defs.contains(*Alias)) continue; - std::vector &DefList = Defs[*Alias]; + std::vector &DefList = Defs[*Alias]; for (unsigned i = 0, e = DefList.size(); i != e; ++i) { - SUnit *DefSU = DefList[i]; + SUnit *DefSU = DefList[i].SU; if (DefSU == &ExitSU) continue; if (DefSU != SU && @@ -282,8 +291,8 @@ void ScheduleDAGInstrs::addPhysRegDeps(SUnit *SU, unsigned OperIdx) { if (Kind == SDep::Anti) DefSU->addPred(SDep(SU, Kind, 0, /*Reg=*/*Alias)); else { - unsigned AOLat = TII->getOutputLatency(InstrItins, MI, OperIdx, - DefSU->getInstr()); + unsigned AOLat = + SchedModel.computeOutputLatency(MI, OperIdx, DefSU->getInstr()); DefSU->addPred(SDep(SU, Kind, AOLat, /*Reg=*/*Alias)); } } @@ -294,61 +303,14 @@ void ScheduleDAGInstrs::addPhysRegDeps(SUnit *SU, unsigned OperIdx) { // Either insert a new Reg2SUnits entry with an empty SUnits list, or // retrieve the existing SUnits list for this register's uses. // Push this SUnit on the use list. - Uses[MO.getReg()].push_back(SU); + Uses[MO.getReg()].push_back(PhysRegSUOper(SU, OperIdx)); } else { - addPhysRegDataDeps(SU, MO); + addPhysRegDataDeps(SU, OperIdx); // Either insert a new Reg2SUnits entry with an empty SUnits list, or // retrieve the existing SUnits list for this register's defs. - std::vector &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(); - 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); - } - } + std::vector &DefList = Defs[MO.getReg()]; // clear this register's use list if (Uses.contains(MO.getReg())) @@ -363,11 +325,11 @@ void ScheduleDAGInstrs::addPhysRegDeps(SUnit *SU, unsigned OperIdx) { // the block. Instead, we leave only one call at the back of the // DefList. if (SU->isCall) { - while (!DefList.empty() && DefList.back()->isCall) + while (!DefList.empty() && DefList.back().SU->isCall) DefList.pop_back(); } // Defs are pushed in the order they are visited and never reordered. - DefList.push_back(SU); + DefList.push_back(PhysRegSUOper(SU, OperIdx)); } } @@ -381,9 +343,10 @@ void ScheduleDAGInstrs::addVRegDefDeps(SUnit *SU, unsigned OperIdx) { const MachineInstr *MI = SU->getInstr(); unsigned Reg = MI->getOperand(OperIdx).getReg(); - // SSA defs do not have output/anti dependencies. + // Singly defined vregs do not have output/anti dependencies. // The current operand is a def, so we have at least one. - if (llvm::next(MRI.def_begin(Reg)) == MRI.def_end()) + // Check here if there are any others... + if (MRI.hasOneDef(Reg)) return; // Add output dependence to the next nearest def of this vreg. @@ -393,14 +356,14 @@ void ScheduleDAGInstrs::addVRegDefDeps(SUnit *SU, unsigned OperIdx) { // uses. We're conservative for now until we have a way to guarantee the uses // are not eliminated sometime during scheduling. The output dependence edge // is also useful if output latency exceeds def-use latency. - VReg2SUnitMap::iterator DefI = findVRegDef(Reg); + VReg2SUnitMap::iterator DefI = VRegDefs.find(Reg); if (DefI == VRegDefs.end()) VRegDefs.insert(VReg2SUnit(Reg, SU)); else { SUnit *DefSU = DefI->SU; if (DefSU != SU && DefSU != &ExitSU) { - unsigned OutLatency = TII->getOutputLatency(InstrItins, MI, OperIdx, - DefSU->getInstr()); + unsigned OutLatency = + SchedModel.computeOutputLatency(MI, OperIdx, DefSU->getInstr()); DefSU->addPred(SDep(SU, SDep::Output, OutLatency, Reg)); } DefI->SU = SU; @@ -419,10 +382,11 @@ void ScheduleDAGInstrs::addVRegUseDeps(SUnit *SU, unsigned OperIdx) { // Lookup this operand's reaching definition. assert(LIS && "vreg dependencies requires LiveIntervals"); - SlotIndex UseIdx = LIS->getInstructionIndex(MI).getRegSlot(); - LiveInterval *LI = &LIS->getInterval(Reg); - VNInfo *VNI = LI->getVNInfoBefore(UseIdx); + LiveRangeQuery LRQ(LIS->getInterval(Reg), LIS->getInstructionIndex(MI)); + VNInfo *VNI = LRQ.valueIn(); + // VNI will be valid because MachineOperand::readsReg() is checked by caller. + assert(VNI && "No value to read by operand"); MachineInstr *Def = LIS->getInstructionFromIndex(VNI->def); // Phis and other noninstructions (after coalescing) have a NULL Def. if (Def) { @@ -430,59 +394,270 @@ 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. - const SDep &dep = SDep(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. - ComputeOperandLatency(DefSU, SU, const_cast(dep)); - const TargetSubtargetInfo &ST = TM.getSubtarget(); - ST.adjustSchedDependency(DefSU, SU, const_cast(dep)); - } + SDep dep(DefSU, SDep::Data, 1, 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(); + ST.adjustSchedDependency(DefSU, SU, const_cast(dep)); SU->addPred(dep); } } // Add antidependence to the following def of the vreg it uses. - VReg2SUnitMap::iterator DefI = findVRegDef(Reg); + VReg2SUnitMap::iterator DefI = VRegDefs.find(Reg); if (DefI != VRegDefs.end() && DefI->SU != SU) DefI->SU->addPred(SDep(SU, SDep::Anti, 0, Reg)); } +/// Return true if MI is an instruction we are unable to reason about +/// (like a call or something with unmodeled side effects). +static inline bool isGlobalMemoryObject(AliasAnalysis *AA, MachineInstr *MI) { + if (MI->isCall() || MI->hasUnmodeledSideEffects() || + (MI->hasOrderedMemoryRef() && + (!MI->mayLoad() || !MI->isInvariantLoad(AA)))) + return true; + return false; +} + +// 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) { + if (!MI || MI->memoperands_empty()) + return true; + // We purposefully do no check for hasOneMemOperand() here + // in hope to trigger an assert downstream in order to + // finish implementation. + 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(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; + + return false; +} + +/// This returns true if the two MIs need a chain edge betwee 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, + MachineInstr *MIb) { + // Cover a trivial case - no edge is need to itself. + if (MIa == MIb) + return false; + + if (isUnsafeMemoryObject(MIa, MFI) || isUnsafeMemoryObject(MIb, MFI)) + return true; + + // If we are dealing with two "normal" loads, we do not need an edge + // between them - they could be reordered. + if (!MIa->mayStore() && !MIb->mayStore()) + return false; + + // To this point analysis is generic. From here on we do need AA. + if (!AA) + return true; + + 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."); + + // The following interface to AA is fashioned after DAGCombiner::isAlias + // and operates with MachineMemOperand offset with some important + // assumptions: + // - LLVM fundamentally assumes flat address spaces. + // - MachineOperand offset can *only* result from legalization and + // cannot affect queries other than the trivial case of overlap + // checking. + // - These offsets never wrap and never step outside + // of allocated objects. + // - There should never be any negative offsets here. + // + // FIXME: Modify API to hide this math from "user" + // FIXME: Even before we go to AA we can reason locally about some + // memory objects. It can save compile time, and possibly catch some + // corner cases not currently covered. + + assert ((MMOa->getOffset() >= 0) && "Negative MachineMemOperand offset"); + assert ((MMOb->getOffset() >= 0) && "Negative MachineMemOperand offset"); + + int64_t MinOffset = std::min(MMOa->getOffset(), MMOb->getOffset()); + 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())); + + return (AAResult != AliasAnalysis::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) { + if (!SUa || !SUb || SUb == ExitSU) + return *Depth; + + // Remember visited nodes. + if (!Visited.insert(SUb)) + return *Depth; + // If there is _some_ dependency already in place, do not + // descend any further. + // TODO: Need to make sure that if that dependency got eliminated or ignored + // for any reason in the future, we would not violate DAG topology. + // Currently it does not happen, but makes an implicit assumption about + // future implementation. + // + // Independently, if we encounter node that is some sort of global + // object (like a call) we already have full set of dependencies to it + // and we can stop descending. + if (SUa->isSucc(SUb) || + isGlobalMemoryObject(AA, SUb->getInstr())) + return *Depth; + + // If we do need an edge, or we have exceeded depth budget, + // add that edge to the predecessors chain of SUb, + // 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)); + return *Depth; + } + // Track current depth. + (*Depth)++; + // Iterate over chain 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); + return *Depth; +} + +/// This function assumes that "downward" from SU there exist +/// tail/leaf of already constructed DAG. It iterates downward and +/// 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, + unsigned LatencyToLoad) { + if (!SU) + return; + + SmallPtrSet Visited; + unsigned Depth = 0; + + for (std::set::iterator I = CheckList.begin(), IE = CheckList.end(); + I != IE; ++I) { + 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)); + } + // Now go through all the chain successors and iterate from them. + // 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); + } +} + +/// 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) { + // 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)); + else { + // Duplicate entries should be ignored. + RejectList.insert(SUb); + DEBUG(dbgs() << "\tReject chain dep between SU(" + << SUa->NodeNum << ") and SU(" + << SUb->NodeNum << ")\n"); + } +} + /// Create an SUnit for each real instruction, numbered in top-down toplological /// order. The instruction order A < B, implies that no edge exists from B to A. /// /// Map each real instruction to its SUnit. /// -/// After initSUnits, the SUnits vector is cannot be resized and the scheduler -/// may hang onto SUnit pointers. We may relax this in the future by using SUnit -/// IDs instead of pointers. +/// After initSUnits, the SUnits vector cannot be resized and the scheduler may +/// hang onto SUnit pointers. We may relax this in the future by using SUnit IDs +/// instead of pointers. +/// +/// MachineScheduler relies on initSUnits numbering the nodes by their order in +/// the original instruction list. 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()); - for (MachineBasicBlock::iterator I = Begin; I != InsertPos; ++I) { + for (MachineBasicBlock::iterator I = RegionBegin; I != RegionEnd; ++I) { MachineInstr *MI = I; if (MI->isDebugValue()) continue; - SUnit *SU = NewSUnit(MI); + SUnit *SU = newSUnit(MI); MISUnitMap[MI] = SU; SU->isCall = MI->isCall(); 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()); } } -void ScheduleDAGInstrs::BuildSchedGraph(AliasAnalysis *AA) { +/// 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) { // Create an SUnit for each real instruction. initSUnits(); @@ -498,6 +673,7 @@ void ScheduleDAGInstrs::BuildSchedGraph(AliasAnalysis *AA) { // that are known not to alias std::map AliasMemDefs, NonAliasMemDefs; std::map > AliasMemUses, NonAliasMemUses; + std::set RejectMemNodes; // Remove any stale debug info; sometimes BuildSchedGraph is called again // without emitting the info from the previous call. @@ -517,11 +693,11 @@ void ScheduleDAGInstrs::BuildSchedGraph(AliasAnalysis *AA) { // Model data dependencies between instructions being scheduled and the // ExitSU. - AddSchedBarrierDeps(); + addSchedBarrierDeps(); // Walk the list of instructions, from bottom moving up. MachineInstr *PrevMI = NULL; - for (MachineBasicBlock::iterator MII = InsertPos, MIE = Begin; + for (MachineBasicBlock::iterator MII = RegionEnd, MIE = RegionBegin; MII != MIE; --MII) { MachineInstr *MI = prior(MII); if (MI && PrevMI) { @@ -533,8 +709,12 @@ void ScheduleDAGInstrs::BuildSchedGraph(AliasAnalysis *AA) { PrevMI = MI; continue; } + if (RPTracker) { + RPTracker->recede(); + assert(RPTracker->getPos() == prior(MII) && "RPTracker can't find MI"); + } - assert(!MI->isTerminator() && !MI->isLabel() && + assert((!MI->isTerminator() || CanHandleTerminators) && !MI->isLabel() && "Cannot schedule terminators or labels!"); SUnit *SU = MISUnitMap[MI]; @@ -567,11 +747,8 @@ void ScheduleDAGInstrs::BuildSchedGraph(AliasAnalysis *AA) { // after stack slots are lowered to actual addresses. // TODO: Use an AliasAnalysis and do real alias-analysis queries, and // produce more precise dependence information. -#define STORE_LOAD_LATENCY 1 - unsigned TrueMemOrderLatency = 0; - if (MI->isCall() || MI->hasUnmodeledSideEffects() || - (MI->hasVolatileMemoryRef() && - (!MI->mayLoad() || !MI->isInvariantLoad(AA)))) { + unsigned TrueMemOrderLatency = MI->mayStore() ? 1 : 0; + 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::iterator I = @@ -583,36 +760,48 @@ void ScheduleDAGInstrs::BuildSchedGraph(AliasAnalysis *AA) { for (unsigned i = 0, e = I->second.size(); i != e; ++i) I->second[i]->addPred(SDep(SU, SDep::Order, TrueMemOrderLatency)); } - NonAliasMemDefs.clear(); - NonAliasMemUses.clear(); // Add SU to the barrier chain. if (BarrierChain) BarrierChain->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); 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, + TrueMemOrderLatency); + RejectMemNodes.clear(); + NonAliasMemDefs.clear(); + NonAliasMemUses.clear(); // fall-through new_alias_chain: // Chain all possibly aliasing memory references though SU. - if (AliasChain) - AliasChain->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); + if (AliasChain) { + unsigned ChainLatency = 0; + if (AliasChain->getInstr()->mayLoad()) + ChainLatency = TrueMemOrderLatency; + addChainDependency(AA, MFI, SU, AliasChain, RejectMemNodes, + ChainLatency); + } AliasChain = SU; for (unsigned k = 0, m = PendingLoads.size(); k != m; ++k) - PendingLoads[k]->addPred(SDep(SU, SDep::Order, TrueMemOrderLatency)); + addChainDependency(AA, MFI, SU, PendingLoads[k], RejectMemNodes, + TrueMemOrderLatency); for (std::map::iterator I = AliasMemDefs.begin(), - E = AliasMemDefs.end(); I != E; ++I) { - I->second->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); - } + E = AliasMemDefs.end(); I != E; ++I) + addChainDependency(AA, MFI, SU, I->second, RejectMemNodes); for (std::map >::iterator I = AliasMemUses.begin(), E = AliasMemUses.end(); I != E; ++I) { for (unsigned i = 0, e = I->second.size(); i != e; ++i) - I->second[i]->addPred(SDep(SU, SDep::Order, TrueMemOrderLatency)); + addChainDependency(AA, MFI, SU, I->second[i], RejectMemNodes, + TrueMemOrderLatency); } + adjustChainDeps(AA, MFI, SU, &ExitSU, RejectMemNodes, + TrueMemOrderLatency); PendingLoads.clear(); AliasMemDefs.clear(); AliasMemUses.clear(); } else if (MI->mayStore()) { bool MayAlias = true; - TrueMemOrderLatency = STORE_LOAD_LATENCY; if (const Value *V = getUnderlyingObjectForInstr(MI, MFI, MayAlias)) { // A store to a specific PseudoSourceValue. Add precise dependencies. // Record the def in MemDefs, first adding a dep if there is @@ -622,8 +811,8 @@ void ScheduleDAGInstrs::BuildSchedGraph(AliasAnalysis *AA) { std::map::iterator IE = ((MayAlias) ? AliasMemDefs.end() : NonAliasMemDefs.end()); if (I != IE) { - I->second->addPred(SDep(SU, SDep::Order, /*Latency=*/0, /*Reg=*/0, - /*isNormalMemory=*/true)); + addChainDependency(AA, MFI, SU, I->second, RejectMemNodes, + 0, true); I->second = SU; } else { if (MayAlias) @@ -638,20 +827,28 @@ void ScheduleDAGInstrs::BuildSchedGraph(AliasAnalysis *AA) { ((MayAlias) ? AliasMemUses.end() : NonAliasMemUses.end()); if (J != JE) { for (unsigned i = 0, e = J->second.size(); i != e; ++i) - J->second[i]->addPred(SDep(SU, SDep::Order, TrueMemOrderLatency, - /*Reg=*/0, /*isNormalMemory=*/true)); + 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) - PendingLoads[k]->addPred(SDep(SU, SDep::Order, TrueMemOrderLatency)); + addChainDependency(AA, MFI, SU, PendingLoads[k], RejectMemNodes, + TrueMemOrderLatency); // Add dependence on alias chain, if needed. if (AliasChain) - AliasChain->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); + 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 { @@ -668,7 +865,6 @@ void ScheduleDAGInstrs::BuildSchedGraph(AliasAnalysis *AA) { /*isArtificial=*/true)); } else if (MI->mayLoad()) { bool MayAlias = true; - TrueMemOrderLatency = 0; if (MI->isInvariantLoad(AA)) { // Invariant load, no chain dependencies needed! } else { @@ -680,8 +876,7 @@ void ScheduleDAGInstrs::BuildSchedGraph(AliasAnalysis *AA) { std::map::iterator IE = ((MayAlias) ? AliasMemDefs.end() : NonAliasMemDefs.end()); if (I != IE) - I->second->addPred(SDep(SU, SDep::Order, /*Latency=*/0, /*Reg=*/0, - /*isNormalMemory=*/true)); + addChainDependency(AA, MFI, SU, I->second, RejectMemNodes, 0, true); if (MayAlias) AliasMemUses[V].push_back(SU); else @@ -691,15 +886,16 @@ void ScheduleDAGInstrs::BuildSchedGraph(AliasAnalysis *AA) { // potentially aliasing stores. for (std::map::iterator I = AliasMemDefs.begin(), E = AliasMemDefs.end(); I != E; ++I) - I->second->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); + addChainDependency(AA, MFI, SU, I->second, RejectMemNodes); PendingLoads.push_back(SU); MayAlias = true; } - + if (MayAlias) + adjustChainDeps(AA, MFI, SU, &ExitSU, RejectMemNodes, /*Latency=*/0); // Add dependencies on alias and barrier chains, if needed. if (MayAlias && AliasChain) - AliasChain->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); + addChainDependency(AA, MFI, SU, AliasChain, RejectMemNodes); if (BarrierChain) BarrierChain->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); } @@ -712,88 +908,12 @@ void ScheduleDAGInstrs::BuildSchedGraph(AliasAnalysis *AA) { Uses.clear(); VRegDefs.clear(); PendingLoads.clear(); - MISUnitMap.clear(); -} - -void ScheduleDAGInstrs::FinishBlock() { - // Nothing to do. -} - -void ScheduleDAGInstrs::ComputeLatency(SUnit *SU) { - // Compute the latency for the node. - if (!InstrItins || InstrItins->isEmpty()) { - 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::ComputeOperandLatency(SUnit *Def, SUnit *Use, - SDep& dep) const { - if (!InstrItins || 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) { - const MachineOperand &MO = DefMI->getOperand(DefIdx); - if (MO.isReg() && MO.isImplicit() && - DefIdx >= (int)DefMI->getDesc().getNumOperands()) { - // This is an implicit def, getOperandLatency() won't return the correct - // latency. e.g. - // %D6, %D7 = VLD1q16 %R2, 0, ..., %Q3 - // %Q1 = VMULv8i16 %Q1, %Q3, ... - // What we want is to compute latency between def of %D6/%D7 and use of - // %Q3 instead. - unsigned Op2 = DefMI->findRegisterDefOperandIdx(Reg, false, true, TRI); - if (DefMI->getOperand(Op2).isReg()) - DefIdx = Op2; - } - MachineInstr *UseMI = Use->getInstr(); - // For all uses of the register, calculate the maxmimum latency - int Latency = -1; - if (UseMI) { - 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 = TII->getOperandLatency(InstrItins, DefMI, DefIdx, - UseMI, i); - Latency = std::max(Latency, UseCycle); - } - } else { - // UseMI is null, then it must be a scheduling barrier. - if (!InstrItins || InstrItins->isEmpty()) - return; - unsigned DefClass = DefMI->getDesc().getSchedClass(); - Latency = InstrItins->getOperandCycle(DefClass, DefIdx); - } - - // If we found a latency, then replace the existing dependence latency. - if (Latency >= 0) - dep.setLatency(Latency); - } } void ScheduleDAGInstrs::dumpNode(const SUnit *SU) const { +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) SU->getInstr()->dump(); +#endif } std::string ScheduleDAGInstrs::getGraphNodeLabel(const SUnit *SU) const {