X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FScheduleDAGInstrs.cpp;h=11b246a8de250e159ea17bf59f3fec821afc62fd;hb=4adfe414ef79d6c457ff3307858396d214a536ac;hp=95f1a06e0c02dcd890eb094a863e784a891ffd1d;hpb=650c3a453d62c554624c04a287b051d467632f72;p=oota-llvm.git diff --git a/lib/CodeGen/ScheduleDAGInstrs.cpp b/lib/CodeGen/ScheduleDAGInstrs.cpp index 95f1a06e0c0..11b246a8de2 100644 --- a/lib/CodeGen/ScheduleDAGInstrs.cpp +++ b/lib/CodeGen/ScheduleDAGInstrs.cpp @@ -13,13 +13,14 @@ //===----------------------------------------------------------------------===// #include "llvm/CodeGen/ScheduleDAGInstrs.h" +#include "llvm/ADT/IntEqClasses.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" #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" @@ -27,7 +28,6 @@ #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" @@ -51,18 +51,13 @@ static cl::opt UseTBAA("use-tbaa-in-sched-mi", cl::Hidden, ScheduleDAGInstrs::ScheduleDAGInstrs(MachineFunction &mf, const MachineLoopInfo *mli, - bool IsPostRAFlag, - bool RemoveKillFlags, - LiveIntervals *lis) - : ScheduleDAG(mf), MLI(mli), MFI(mf.getFrameInfo()), LIS(lis), - IsPostRA(IsPostRAFlag), RemoveKillFlags(RemoveKillFlags), - CanHandleTerminators(false), FirstDbgValue(nullptr) { - assert((IsPostRA || LIS) && "PreRA scheduling requires LiveIntervals"); + bool RemoveKillFlags) + : ScheduleDAG(mf), MLI(mli), MFI(mf.getFrameInfo()), + RemoveKillFlags(RemoveKillFlags), CanHandleTerminators(false), + TrackLaneMasks(false), FirstDbgValue(nullptr) { DbgValues.clear(); - assert(!(IsPostRA && MRI.getNumVirtRegs()) && - "Virtual registers must be removed prior to PostRA scheduling"); - const TargetSubtargetInfo &ST = TM.getSubtarget(); + const TargetSubtargetInfo &ST = mf.getSubtarget(); SchedModel.init(ST.getSchedModel(), &ST, TII); } @@ -97,14 +92,15 @@ 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) { + 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) { @@ -133,7 +129,8 @@ 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())->getPseudoValue()) || @@ -142,6 +139,13 @@ static void getUnderlyingObjectsForInstr(const MachineInstr *MI, 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. @@ -157,12 +161,9 @@ static void getUnderlyingObjectsForInstr(const MachineInstr *MI, return; SmallVector Objs; - getUnderlyingObjects(V, Objs); - - for (SmallVectorImpl::iterator I = Objs.begin(), IE = Objs.end(); - I != IE; ++I) { - V = *I; + getUnderlyingObjects(V, Objs, DL); + for (Value *V : Objs) { if (!isIdentifiedObject(V)) { Objects.clear(); return; @@ -225,11 +226,8 @@ void ScheduleDAGInstrs::addSchedBarrierDeps() { if (TRI->isPhysicalRegister(Reg)) Uses.insert(PhysRegSUOper(&ExitSU, -1, Reg)); - else { - assert(!IsPostRA && "Virtual register encountered after regalloc."); - if (MO.readsReg()) // ignore undef operands - addVRegUseDeps(&ExitSU, i); - } + else if (MO.readsReg()) // ignore undef operands + addVRegUseDeps(&ExitSU, i); } } else { // For others, e.g. fallthrough, conditional branch, assume the exit @@ -237,11 +235,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)); } } } @@ -253,7 +249,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) { @@ -366,6 +362,20 @@ void ScheduleDAGInstrs::addPhysRegDeps(SUnit *SU, unsigned OperIdx) { } } +LaneBitmask ScheduleDAGInstrs::getLaneMaskForMO(const MachineOperand &MO) const +{ + unsigned Reg = MO.getReg(); + // No point in tracking lanemasks if we don't have interesting subregisters. + const TargetRegisterClass &RC = *MRI.getRegClass(Reg); + if (!RC.HasDisjunctSubRegs) + return ~0u; + + unsigned SubReg = MO.getSubReg(); + if (SubReg == 0) + return RC.getLaneMask(); + return TRI->getSubRegIndexLaneMask(SubReg); +} + /// addVRegDefDeps - Add register output and data dependencies from this SUnit /// to instructions that occur later in the same scheduling region if they read /// from or write to the virtual register defined at OperIdx. @@ -373,35 +383,106 @@ void ScheduleDAGInstrs::addPhysRegDeps(SUnit *SU, unsigned OperIdx) { /// TODO: Hoist loop induction variable increments. This has to be /// reevaluated. Generally, IV scheduling should be done before coalescing. void ScheduleDAGInstrs::addVRegDefDeps(SUnit *SU, unsigned OperIdx) { - const MachineInstr *MI = SU->getInstr(); - unsigned Reg = MI->getOperand(OperIdx).getReg(); + MachineInstr *MI = SU->getInstr(); + MachineOperand &MO = MI->getOperand(OperIdx); + unsigned Reg = MO.getReg(); + + LaneBitmask DefLaneMask; + LaneBitmask KillLaneMask; + if (TrackLaneMasks) { + bool IsKill = MO.getSubReg() == 0 || MO.isUndef(); + DefLaneMask = getLaneMaskForMO(MO); + // If we have a flag, none of the lane values comes from an + // earlier instruction. + KillLaneMask = IsKill ? ~0u : DefLaneMask; + + // Clear undef flag, we'll re-add it later once we know which subregister + // Def is first. + MO.setIsUndef(false); + } else { + DefLaneMask = ~0u; + KillLaneMask = ~0u; + } + + if (MO.isDead()) { + assert(CurrentVRegUses.find(Reg) == CurrentVRegUses.end() && + "Dead defs should have no uses"); + } else { + // Add data dependence to all uses we found so far. + const TargetSubtargetInfo &ST = MF.getSubtarget(); + for (VReg2SUnitOperIdxMultiMap::iterator I = CurrentVRegUses.find(Reg), + E = CurrentVRegUses.end(); I != E; /*empty*/) { + LaneBitmask LaneMask = I->LaneMask; + // Ignore uses of other lanes. + if ((LaneMask & KillLaneMask) == 0) { + ++I; + continue; + } + + if ((LaneMask & DefLaneMask) != 0) { + SUnit *UseSU = I->SU; + MachineInstr *Use = UseSU->getInstr(); + SDep Dep(SU, SDep::Data, Reg); + Dep.setLatency(SchedModel.computeOperandLatency(MI, OperIdx, Use, + I->OperandIndex)); + ST.adjustSchedDependency(SU, UseSU, Dep); + UseSU->addPred(Dep); + } - // Singly defined vregs do not have output/anti dependencies. - // The current operand is a def, so we have at least one. - // Check here if there are any others... + LaneMask &= ~KillLaneMask; + // If we found a Def for all lanes of this use, remove it from the list. + if (LaneMask != 0) { + I->LaneMask = LaneMask; + ++I; + } else + I = CurrentVRegUses.erase(I); + } + } + + // Shortcut: Singly defined vregs do not have output/anti dependencies. if (MRI.hasOneDef(Reg)) return; - // Add output dependence to the next nearest def of this vreg. + // Add output dependence to the next nearest defs of this vreg. // // Unless this definition is dead, the output dependence should be // transitively redundant with antidependencies from this definition's // uses. We're conservative for now until we have a way to guarantee the uses // are not eliminated sometime during scheduling. The output dependence edge // is also useful if output latency exceeds def-use latency. - 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) { - SDep Dep(SU, SDep::Output, Reg); - Dep.setLatency( - SchedModel.computeOutputLatency(MI, OperIdx, DefSU->getInstr())); - DefSU->addPred(Dep); - } - DefI->SU = SU; + LaneBitmask LaneMask = DefLaneMask; + for (VReg2SUnit &V2SU : make_range(CurrentVRegDefs.find(Reg), + CurrentVRegDefs.end())) { + // Ignore defs for other lanes. + if ((V2SU.LaneMask & LaneMask) == 0) + continue; + // Add an output dependence. + SUnit *DefSU = V2SU.SU; + // Ignore additional defs of the same lanes in one instruction. This can + // happen because lanemasks are shared for targets with too many + // subregisters. We also use some representration tricks/hacks where we + // add super-register defs/uses, to imply that although we only access parts + // of the reg we care about the full one. + if (DefSU == SU) + continue; + SDep Dep(SU, SDep::Output, Reg); + Dep.setLatency( + SchedModel.computeOutputLatency(MI, OperIdx, DefSU->getInstr())); + DefSU->addPred(Dep); + + // Update current definition. This can get tricky if the def was about a + // bigger lanemask before. We then have to shrink it and create a new + // VReg2SUnit for the non-overlapping part. + LaneBitmask OverlapMask = V2SU.LaneMask & LaneMask; + LaneBitmask NonOverlapMask = V2SU.LaneMask & ~LaneMask; + if (NonOverlapMask != 0) + CurrentVRegDefs.insert(VReg2SUnit(Reg, NonOverlapMask, V2SU.SU)); + V2SU.SU = SU; + V2SU.LaneMask = OverlapMask; } + // If there was no CurrentVRegDefs entry for some lanes yet, create one. + if (LaneMask != 0) + CurrentVRegDefs.insert(VReg2SUnit(Reg, LaneMask, SU)); } /// addVRegUseDeps - Add a register data dependency if the instruction that @@ -411,65 +492,41 @@ void ScheduleDAGInstrs::addVRegDefDeps(SUnit *SU, unsigned OperIdx) { /// /// TODO: Handle ExitSU "uses" properly. void ScheduleDAGInstrs::addVRegUseDeps(SUnit *SU, unsigned OperIdx) { - MachineInstr *MI = SU->getInstr(); - unsigned Reg = MI->getOperand(OperIdx).getReg(); + const MachineInstr *MI = SU->getInstr(); + const MachineOperand &MO = MI->getOperand(OperIdx); + unsigned Reg = MO.getReg(); + + // Remember the use. Data dependencies will be added when we find the def. + LaneBitmask LaneMask = TrackLaneMasks ? getLaneMaskForMO(MO) : ~0u; + CurrentVRegUses.insert(VReg2SUnitOperIdx(Reg, LaneMask, OperIdx, SU)); + + // Add antidependences to the following defs of the vreg. + for (VReg2SUnit &V2SU : make_range(CurrentVRegDefs.find(Reg), + CurrentVRegDefs.end())) { + // Ignore defs for unrelated lanes. + LaneBitmask PrevDefLaneMask = V2SU.LaneMask; + if ((PrevDefLaneMask & LaneMask) == 0) + continue; + if (V2SU.SU == SU) + continue; - // Record this local VReg use. - VReg2UseMap::iterator UI = VRegUses.find(Reg); - for (; UI != VRegUses.end(); ++UI) { - if (UI->SU == SU) - break; + V2SU.SU->addPred(SDep(SU, SDep::Anti, Reg)); } - if (UI == VRegUses.end()) - VRegUses.insert(VReg2SUnit(Reg, SU)); - - // Lookup this operand's reaching definition. - assert(LIS && "vreg dependencies requires LiveIntervals"); - LiveQueryResult LRQ - = LIS->getInterval(Reg).Query(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) { - SUnit *DefSU = getSUnit(Def); - if (DefSU) { - // The reaching Def lives within this scheduling region. - // Create a data dependence. - 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)); - - 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 = VRegDefs.find(Reg); - if (DefI != VRegDefs.end() && DefI->SU != SU) - DefI->SU->addPred(SDep(SU, SDep::Anti, 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; + return MI->isCall() || MI->hasUnmodeledSideEffects() || + (MI->hasOrderedMemoryRef() && + (!MI->mayLoad() || !MI->isInvariantLoad(AA))); } // 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 @@ -492,24 +549,23 @@ static inline bool isUnsafeMemoryObject(MachineInstr *MI, return true; SmallVector Objs; - getUnderlyingObjects(V, Objs); - for (SmallVectorImpl::iterator I = Objs.begin(), - IE = Objs.end(); I != IE; ++I) { + getUnderlyingObjects(V, Objs, DL); + for (Value *V : Objs) { // Does this pointer refer to a distinct and identifiable object? - if (!isIdentifiedObject(*I)) + if (!isIdentifiedObject(V)) return true; } 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(); @@ -528,7 +584,7 @@ static bool MIsNeedChainEdge(AliasAnalysis *AA, const MachineFrameInfo *MFI, 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 @@ -569,21 +625,21 @@ 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, - UseTBAA ? MMOa->getAAInfo() : AAMDNodes()), - AliasAnalysis::Location(MMOb->getValue(), Overlapb, - UseTBAA ? MMOb->getAAInfo() : AAMDNodes())); + 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, - SmallPtrSetImpl &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; @@ -608,17 +664,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; } @@ -627,7 +683,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; @@ -639,32 +696,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 (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); @@ -678,7 +736,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. @@ -736,17 +794,44 @@ void ScheduleDAGInstrs::initSUnits() { } } +void ScheduleDAGInstrs::collectVRegUses(SUnit *SU) { + const MachineInstr *MI = SU->getInstr(); + for (const MachineOperand &MO : MI->operands()) { + if (!MO.isReg()) + continue; + if (!MO.readsReg()) + continue; + if (TrackLaneMasks && !MO.isUse()) + continue; + + unsigned Reg = MO.getReg(); + if (!TargetRegisterInfo::isVirtualRegister(Reg)) + continue; + + // Record this local VReg use. + VReg2SUnitMultiMap::iterator UI = VRegUses.find(Reg); + for (; UI != VRegUses.end(); ++UI) { + if (UI->SU == SU) + break; + } + if (UI == VRegUses.end()) + VRegUses.insert(VReg2SUnit(Reg, 0, SU)); + } +} + /// 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, - PressureDiffs *PDiffs) { - const TargetSubtargetInfo &ST = TM.getSubtarget(); + PressureDiffs *PDiffs, + bool TrackLaneMasks) { + const TargetSubtargetInfo &ST = MF.getSubtarget(); bool UseAA = EnableAASchedMI.getNumOccurrences() > 0 ? EnableAASchedMI : ST.useAA(); AliasAnalysis *AAForDep = UseAA ? AA : nullptr; + this->TrackLaneMasks = TrackLaneMasks; MISUnitMap.clear(); ScheduleDAG::clearDAG(); @@ -759,7 +844,7 @@ void ScheduleDAGInstrs::buildSchedGraph(AliasAnalysis *AA, // 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. + // 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 @@ -780,10 +865,14 @@ void ScheduleDAGInstrs::buildSchedGraph(AliasAnalysis *AA, Defs.setUniverse(TRI->getNumRegs()); Uses.setUniverse(TRI->getNumRegs()); - assert(VRegDefs.empty() && "Only BuildSchedGraph may access VRegDefs"); + assert(CurrentVRegDefs.empty() && "nobody else should use CurrentVRegDefs"); + assert(CurrentVRegUses.empty() && "nobody else should use CurrentVRegUses"); + unsigned NumVirtRegs = MRI.getNumVirtRegs(); + CurrentVRegDefs.setUniverse(NumVirtRegs); + CurrentVRegUses.setUniverse(NumVirtRegs); + VRegUses.clear(); - VRegDefs.setUniverse(MRI.getNumVirtRegs()); - VRegUses.setUniverse(MRI.getNumVirtRegs()); + VRegUses.setUniverse(NumVirtRegs); // Model data dependencies between instructions being scheduled and the // ExitSU. @@ -807,10 +896,16 @@ void ScheduleDAGInstrs::buildSchedGraph(AliasAnalysis *AA, assert(SU && "No SUnit mapped to this MI"); if (RPTracker) { - PressureDiff *PDiff = PDiffs ? &(*PDiffs)[SU->NodeNum] : nullptr; - RPTracker->recede(/*LiveUses=*/nullptr, PDiff); - assert(RPTracker->getPos() == std::prev(MII) && - "RPTracker can't find MI"); + collectVRegUses(SU); + + RegisterOperands RegOpers; + RegOpers.collect(*MI, *TRI, MRI); + if (PDiffs != nullptr) + PDiffs->addInstruction(SU->NodeNum, RegOpers, MRI); + + RPTracker->recedeSkipDebugValues(); + assert(&*RPTracker->getPos() == MI && "RPTracker in sync"); + RPTracker->recede(RegOpers); } assert( @@ -828,7 +923,6 @@ void ScheduleDAGInstrs::buildSchedGraph(AliasAnalysis *AA, if (TRI->isPhysicalRegister(Reg)) addPhysRegDeps(SU, j); else { - assert(!IsPostRA && "Virtual register encountered!"); if (MO.isDef()) { HasVRegDef = true; addVRegDefDeps(SU, j); @@ -883,7 +977,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(); @@ -896,25 +990,30 @@ void ScheduleDAGInstrs::buildSchedGraph(AliasAnalysis *AA, unsigned ChainLatency = 0; if (AliasChain->getInstr()->mayLoad()) ChainLatency = TrueMemOrderLatency; - addChainDependency(AAForDep, 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(AAForDep, 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) { for (unsigned i = 0, e = I->second.size(); i != e; ++i) - addChainDependency(AAForDep, MFI, SU, I->second[i], RejectMemNodes); + 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(AAForDep, MFI, SU, I->second[i], RejectMemNodes, - TrueMemOrderLatency); + addChainDependency(AAForDep, MFI, MF.getDataLayout(), SU, + I->second[i], RejectMemNodes, TrueMemOrderLatency); } - adjustChainDeps(AA, MFI, SU, &ExitSU, RejectMemNodes, + // This call must come after calls to addChainDependency() since it + // consumes the 'RejectMemNodes' list that addChainDependency() possibly + // adds to. + adjustChainDeps(AA, MFI, MF.getDataLayout(), SU, &ExitSU, RejectMemNodes, TrueMemOrderLatency); PendingLoads.clear(); AliasMemDefs.clear(); @@ -928,7 +1027,7 @@ void ScheduleDAGInstrs::buildSchedGraph(AliasAnalysis *AA, 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. @@ -952,8 +1051,8 @@ void ScheduleDAGInstrs::buildSchedGraph(AliasAnalysis *AA, ((ThisMayAlias) ? AliasMemDefs.end() : NonAliasMemDefs.end()); if (I != IE) { for (unsigned i = 0, e = I->second.size(); i != e; ++i) - addChainDependency(AAForDep, MFI, SU, I->second[i], RejectMemNodes, - 0, true); + 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) @@ -977,7 +1076,8 @@ void ScheduleDAGInstrs::buildSchedGraph(AliasAnalysis *AA, ((ThisMayAlias) ? AliasMemUses.end() : NonAliasMemUses.end()); if (J != JE) { for (unsigned i = 0, e = J->second.size(); i != e; ++i) - addChainDependency(AAForDep, MFI, SU, J->second[i], RejectMemNodes, + addChainDependency(AAForDep, MFI, MF.getDataLayout(), SU, + J->second[i], RejectMemNodes, TrueMemOrderLatency, true); J->second.clear(); } @@ -986,23 +1086,26 @@ 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(AAForDep, 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(AAForDep, 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); } + // This call must come after calls to addChainDependency() since it + // consumes the 'RejectMemNodes' list that addChainDependency() possibly + // adds to. + 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 @@ -1010,8 +1113,8 @@ void ScheduleDAGInstrs::buildSchedGraph(AliasAnalysis *AA, 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, SU, I->second[i], - RejectMemNodes); + addChainDependency(AAForDep, MFI, MF.getDataLayout(), SU, + I->second[i], RejectMemNodes); PendingLoads.push_back(SU); MayAlias = true; @@ -1034,18 +1137,23 @@ void ScheduleDAGInstrs::buildSchedGraph(AliasAnalysis *AA, ((ThisMayAlias) ? AliasMemDefs.end() : NonAliasMemDefs.end()); if (I != IE) for (unsigned i = 0, e = I->second.size(); i != e; ++i) - addChainDependency(AAForDep, MFI, SU, I->second[i], - RejectMemNodes, 0, true); + 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); // Add dependencies on alias and barrier chains, if needed. if (MayAlias && AliasChain) - addChainDependency(AAForDep, MFI, SU, AliasChain, RejectMemNodes); + addChainDependency(AAForDep, MFI, MF.getDataLayout(), SU, AliasChain, + RejectMemNodes); + if (MayAlias) + // This call must come after calls to addChainDependency() since it + // consumes the 'RejectMemNodes' list that addChainDependency() + // possibly adds to. + adjustChainDeps(AA, MFI, MF.getDataLayout(), SU, &ExitSU, + RejectMemNodes, /*Latency=*/0); if (BarrierChain) BarrierChain->addPred(SDep(SU, SDep::Barrier)); } @@ -1056,7 +1164,8 @@ void ScheduleDAGInstrs::buildSchedGraph(AliasAnalysis *AA, Defs.clear(); Uses.clear(); - VRegDefs.clear(); + CurrentVRegDefs.clear(); + CurrentVRegUses.clear(); PendingLoads.clear(); } @@ -1068,33 +1177,74 @@ void ScheduleDAGInstrs::startBlockForKills(MachineBasicBlock *BB) { // Examine the live-in regs of all successors. 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; + for (const auto &LI : (*SI)->liveins()) { // Repeat, for reg and all subregs. - for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true); + 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->getIterator(); + 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); @@ -1105,8 +1255,10 @@ bool ScheduleDAGInstrs::toggleKillFlag(MachineInstr *MI, MachineOperand &MO) { } } - if(AllDead) + if(AllDead) { MO.setIsKill(true); + toggleBundleKillFlag(MI, MO.getReg(), true); + } return false; } @@ -1179,6 +1331,12 @@ void ScheduleDAGInstrs::fixupKills(MachineBasicBlock *MBB) { // Warning: toggleKillFlag may invalidate MO. toggleKillFlag(MI, MO); DEBUG(MI->dump()); + DEBUG(if (MI->getOpcode() == TargetOpcode::BUNDLE) { + MachineBasicBlock::instr_iterator Begin = MI->getIterator(); + MachineBasicBlock::instr_iterator End = getBundleEnd(MI); + while (++Begin != End) + DEBUG(Begin->dump()); + }); } killedRegs.set(Reg); @@ -1213,7 +1371,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(); }