40#include "llvm/Config/llvm-config.h"
62#define DEBUG_TYPE "machine-scheduler"
66 cl::desc(
"Enable use of AA during MI DAG construction"));
79 "prior to scheduling, at which point a trade-off "
80 "is made to avoid excessive compile time."));
84 cl::desc(
"A huge scheduling region will have maps reduced by this many "
85 "nodes at a time. Defaults to HugeRegion / 2."));
87#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
90 cl::desc(
"Report top/bottom cycles when dumping SUnit instances"));
102#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
104 for (
const SUnit *SU : L) {
105 dbgs() <<
"SU(" << SU->NodeNum <<
")";
115 bool RemoveKillFlags)
116 :
ScheduleDAG(mf), MLI(mli), MFI(mf.getFrameInfo()),
117 RemoveKillFlags(RemoveKillFlags),
119 Type::getVoidTy(mf.
getFunction().getContext()))), Topo(SUnits, &ExitSU) {
134 auto AllMMOsOkay = [&]() {
137 if (MMO->isVolatile() || MMO->isAtomic())
152 if (PSV->isAliased(&MFI))
155 bool MayAlias = PSV->mayAlias(&MFI);
157 }
else if (
const Value *V = MMO->getValue()) {
162 for (
Value *V : Objs) {
172 if (!AllMMOsOkay()) {
192 unsigned regioninstrs) {
193 assert(bb ==
BB &&
"startBlock should set BB");
212 if (!MO.isReg() || MO.isDef())
continue;
214 if (Reg.isPhysical()) {
216 }
else if (Reg.isVirtual() && MO.readsReg()) {
225 for (
const auto &LI : Succ->liveins()) {
245 bool ImplicitPseudoDef = (OperIdx >= DefMIDesc->
getNumOperands() &&
256 int UseOp =
I->OpIdx;
270 bool ImplicitPseudoUse =
273 if (!ImplicitPseudoDef && !ImplicitPseudoUse) {
279 ST.adjustSchedDependency(SU, OperIdx, UseSU, UseOp, Dep);
315 SDep Dep(SU, Kind, *Alias);
319 ST.adjustSchedDependency(SU, OperIdx, DefSU,
I->OpIdx, Dep);
352 for (
bool isBegin =
I ==
B; !isBegin; ) {
353 isBegin = (--
I) ==
B;
413 if (OtherMO.isReg() && OtherMO.isDef() && OtherMO.getReg() == Reg)
414 KillLaneMask &= ~getLaneMaskForMO(OtherMO);
434 if ((LaneMask & KillLaneMask).
none()) {
439 if ((LaneMask & DefLaneMask).any()) {
445 ST.adjustSchedDependency(SU, OperIdx, UseSU,
I->OperandIndex, Dep);
449 LaneMask &= ~KillLaneMask;
451 if (LaneMask.
any()) {
452 I->LaneMask = LaneMask;
474 if ((V2SU.LaneMask & LaneMask).none())
477 SUnit *DefSU = V2SU.SU;
493 LaneBitmask OverlapMask = V2SU.LaneMask & LaneMask;
494 LaneBitmask NonOverlapMask = V2SU.LaneMask & ~LaneMask;
496 V2SU.LaneMask = OverlapMask;
497 if (NonOverlapMask.
any())
513 assert(!
MI->isDebugOrPseudoInstr());
528 if ((PrevDefLaneMask & LaneMask).
none())
540 return MI->isCall() ||
MI->hasUnmodeledSideEffects() ||
541 (
MI->hasOrderedMemoryRef() && !
MI->isDereferenceableInvariantLoad());
571 if (
MI.isDebugOrPseudoInstr())
613 unsigned NumNodes = 0;
616 unsigned TrueMemOrderLatency;
637 assert(NumNodes >= Itr->second.size());
638 NumNodes -= Itr->second.size();
650 unsigned inline size()
const {
return NumNodes; }
655 for (
auto &
I : *
this)
656 NumNodes +=
I.second.size();
660 return TrueMemOrderLatency;
668 for (
auto &
I : Val2SUsMap)
677 if (Itr != Val2SUsMap.
end())
685 for (
auto &[V, SUs] : map) {
699 SUList &sus = CurrItr->second;
700 SUList::iterator SUItr = sus.begin(), SUEE = sus.end();
701 for (; SUItr != SUEE; ++SUItr) {
714 if (SUItr != sus.begin())
715 sus.erase(sus.begin(), SUItr);
719 map.
remove_if([&](std::pair<ValueType, SUList> &mapEntry) {
720 return (mapEntry.second.empty()); });
730 bool TrackLaneMasks) {
782 "Only BuildGraph should update Defs/Uses");
806 if (
MI.isDebugValue() ||
MI.isDebugPHI()) {
811 if (
MI.isDebugLabel() ||
MI.isDebugRef() ||
MI.isPseudoProbe())
815 assert(SU &&
"No SUnit mapped to this MI");
824 if (PDiffs !=
nullptr)
830 RPTracker->
recede(RegOpers);
835 "Cannot schedule terminators or labels!");
842 bool HasVRegDef =
false;
843 for (
unsigned j = 0, n =
MI.getNumOperands(); j != n; ++j) {
848 if (Reg.isPhysical()) {
850 }
else if (Reg.isVirtual()) {
856 for (
unsigned j = 0, n =
MI.getNumOperands(); j != n; ++j) {
865 if (Reg.isPhysical()) {
867 }
else if (Reg.isVirtual() && MO.
readsReg()) {
896 LLVM_DEBUG(
dbgs() <<
"Global memory object and new barrier chain: SU("
911 if (
MI.mayRaiseFPException()) {
925 if (!
MI.mayStore() &&
926 !(
MI.mayLoad() && !
MI.isDereferenceableInvariantLoad()))
955 bool ThisMayAlias = UnderlObj.mayAlias();
965 bool ThisMayAlias = UnderlObj.mayAlias();
968 (ThisMayAlias ? Stores : NonAliasStores).insert(SU, V);
985 bool ThisMayAlias = UnderlObj.mayAlias();
992 (ThisMayAlias ? Loads : NonAliasLoads).insert(SU, V);
1006 dbgs() <<
"Reducing NonAliasStores and NonAliasLoads maps.\n";);
1023 PSV->printCustom(
OS);
1028 for (
const auto &[ValType, SUs] : *
this) {
1029 if (ValType.is<
const Value*>()) {
1030 const Value *V = ValType.get<
const Value*>();
1031 if (isa<UndefValue>(V))
1032 dbgs() <<
"Unknown";
1034 V->printAsOperand(
dbgs());
1049 dbgs() <<
"Loading SUnits:\n"; loads.
dump());
1052 std::vector<unsigned> NodeNums;
1053 NodeNums.reserve(
stores.size() + loads.
size());
1054 for (
const auto &[V, SUs] :
stores) {
1056 for (
const auto *SU : SUs)
1057 NodeNums.push_back(SU->NodeNum);
1059 for (
const auto &[V, SUs] : loads) {
1061 for (
const auto *SU : SUs)
1062 NodeNums.push_back(SU->NodeNum);
1070 SUnit *newBarrierChain = &
SUnits[*(NodeNums.end() -
N)];
1093 dbgs() <<
"Loading SUnits:\n"; loads.
dump());
1099 if (!MO.isReg() || !MO.readsReg())
1107 MO.setIsKill(IsKill);
1121 if (
MI.isDebugOrPseudoInstr())
1142 if (!
MI.isBundled()) {
1153 while (
I->isBundledWithSucc())
1156 if (!
I->isDebugOrPseudoInstr())
1159 }
while (
I != Bundle);
1165#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1176#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1234 std::vector<std::pair<const SUnit *, const SUnit*>> ConnectionPairs;
1238 unsigned ParentNodeID;
1239 unsigned SubInstrCount = 0;
1242 RootData(
unsigned id): NodeID(
id),
1243 ParentNodeID(SchedDFSResult::InvalidSubtreeID) {}
1245 unsigned getSparseSetIndex()
const {
return NodeID; }
1260 return R.DFSNodeData[SU->
NodeNum].SubtreeID
1261 != SchedDFSResult::InvalidSubtreeID;
1267 R.DFSNodeData[SU->
NodeNum].InstrCount =
1291 if ((
InstrCount - R.DFSNodeData[PredNum].InstrCount) < R.SubtreeLimit)
1292 joinPredSubtree(PredDep, SU,
false);
1295 if (R.DFSNodeData[PredNum].SubtreeID == PredNum) {
1298 if (RootSet[PredNum].ParentNodeID == SchedDFSResult::InvalidSubtreeID)
1299 RootSet[PredNum].ParentNodeID = SU->
NodeNum;
1301 else if (RootSet.
count(PredNum)) {
1306 RData.SubInstrCount += RootSet[PredNum].SubInstrCount;
1307 RootSet.
erase(PredNum);
1317 R.DFSNodeData[Succ->
NodeNum].InstrCount
1319 joinPredSubtree(PredDep, Succ);
1324 ConnectionPairs.emplace_back(PredDep.
getSUnit(), Succ);
1333 &&
"number of roots should match trees");
1334 for (
const RootData &Root : RootSet) {
1335 unsigned TreeID = SubtreeClasses[Root.NodeID];
1336 if (Root.ParentNodeID != SchedDFSResult::InvalidSubtreeID)
1337 R.DFSTreeData[TreeID].ParentTreeID = SubtreeClasses[Root.ParentNodeID];
1338 R.DFSTreeData[TreeID].SubInstrCount = Root.SubInstrCount;
1344 R.SubtreeConnections.resize(SubtreeClasses.
getNumClasses());
1345 R.SubtreeConnectLevels.resize(SubtreeClasses.
getNumClasses());
1347 for (
unsigned Idx = 0, End = R.DFSNodeData.size();
Idx != End; ++
Idx) {
1348 R.DFSNodeData[
Idx].SubtreeID = SubtreeClasses[
Idx];
1350 << R.DFSNodeData[
Idx].SubtreeID <<
'\n');
1352 for (
const auto &[Pred, Succ] : ConnectionPairs) {
1353 unsigned PredTree = SubtreeClasses[Pred->NodeNum];
1354 unsigned SuccTree = SubtreeClasses[Succ->NodeNum];
1355 if (PredTree == SuccTree)
1357 unsigned Depth = Pred->getDepth();
1358 addConnection(PredTree, SuccTree,
Depth);
1359 addConnection(SuccTree, PredTree,
Depth);
1367 bool CheckLimit =
true) {
1372 unsigned PredNum = PredSU->
NodeNum;
1373 if (R.DFSNodeData[PredNum].SubtreeID != PredNum)
1378 unsigned NumDataSucs = 0;
1379 for (
const SDep &SuccDep : PredSU->
Succs) {
1381 if (++NumDataSucs >= 4)
1385 if (CheckLimit && R.DFSNodeData[PredNum].InstrCount > R.SubtreeLimit)
1387 R.DFSNodeData[PredNum].SubtreeID = Succ->
NodeNum;
1399 R.SubtreeConnections[FromTree];
1400 for (SchedDFSResult::Connection &
C : Connections) {
1401 if (
C.TreeID == ToTree) {
1402 C.Level = std::max(
C.Level,
Depth);
1406 Connections.
push_back(SchedDFSResult::Connection(ToTree,
Depth));
1407 FromTree = R.DFSTreeData[FromTree].ParentTreeID;
1408 }
while (FromTree != SchedDFSResult::InvalidSubtreeID);
1417class SchedDAGReverseDFS {
1418 std::vector<std::pair<const SUnit *, SUnit::const_pred_iterator>> DFSStack;
1421 bool isComplete()
const {
return DFSStack.empty(); }
1423 void follow(
const SUnit *SU) {
1424 DFSStack.emplace_back(SU, SU->
Preds.begin());
1426 void advance() { ++DFSStack.back().second; }
1428 const SDep *backtrack() {
1429 DFSStack.pop_back();
1430 return DFSStack.empty() ? nullptr : std::prev(DFSStack.back().second);
1433 const SUnit *getCurr()
const {
return DFSStack.back().first; }
1438 return getCurr()->
Preds.end();
1464 SchedDAGReverseDFS DFS;
1469 while (DFS.getPred() != DFS.getPredEnd()) {
1470 const SDep &PredDep = *DFS.getPred();
1486 const SUnit *Child = DFS.getCurr();
1487 const SDep *PredDep = DFS.backtrack();
1491 if (DFS.isComplete())
1502 for (
const Connection &
C : SubtreeConnections[SubtreeID]) {
1503 SubtreeConnectLevels[
C.TreeID] =
1504 std::max(SubtreeConnectLevels[
C.TreeID],
C.Level);
1506 << SubtreeConnectLevels[
C.TreeID] <<
'\n');
1510#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1520 dbgs() << *
this <<
'\n';
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static cl::opt< bool > UseAA("aarch64-use-aa", cl::init(true), cl::desc("Enable the use of AA during codegen."))
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
#define LLVM_ATTRIBUTE_UNUSED
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static unsigned InstrCount
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
static Function * getFunction(Constant *C)
Equivalence classes for small integers.
A common definition of LaneBitmask for use in TableGen and CodeGen.
This file implements the LivePhysRegs utility for tracking liveness of physical registers.
This file implements a map that provides insertion order iteration.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static cl::opt< unsigned > ReductionSize("dag-maps-reduction-size", cl::Hidden, cl::desc("A huge scheduling region will have maps reduced by this many " "nodes at a time. Defaults to HugeRegion / 2."))
static bool getUnderlyingObjectsForInstr(const MachineInstr *MI, const MachineFrameInfo &MFI, UnderlyingObjectsVector &Objects, const DataLayout &DL)
If this machine instr has memory reference information and it can be tracked to a normal reference to...
static bool hasDataSucc(const SUnit *SU)
static cl::opt< bool > EnableAASchedMI("enable-aa-sched-mi", cl::Hidden, cl::desc("Enable use of AA during MI DAG construction"))
static cl::opt< unsigned > HugeRegion("dag-maps-huge-region", cl::Hidden, cl::init(1000), cl::desc("The limit to use while constructing the DAG " "prior to scheduling, at which point a trade-off " "is made to avoid excessive compile time."))
static unsigned getReductionSize()
static void dumpSUList(const ScheduleDAGInstrs::SUList &L)
static cl::opt< bool > UseTBAA("use-tbaa-in-sched-mi", cl::Hidden, cl::init(true), cl::desc("Enable use of TBAA during MI DAG construction"))
static bool isGlobalMemoryObject(MachineInstr *MI)
Returns true if MI is an instruction we are unable to reason about (like a call or something with unm...
static void toggleKills(const MachineRegisterInfo &MRI, LivePhysRegs &LiveRegs, MachineInstr &MI, bool addToLiveRegs)
static cl::opt< bool > SchedPrintCycles("sched-print-cycles", cl::Hidden, cl::init(false), cl::desc("Report top/bottom cycles when dumping SUnit instances"))
This file defines the SmallVector class.
This file defines the SparseSet class derived from the version described in Briggs,...
void reComputeSize()
Counts the number of SUs in this map after a reduction.
void insert(SUnit *SU, ValueType V)
Adds SU to the SUList of V.
void clear()
Clears map from all contents.
Value2SUsMap(unsigned lat=0)
void clearList(ValueType V)
Clears the list of SUs mapped to V.
ValueType & operator[](const SUList &Key)
To keep NumNodes up to date, insert() is used instead of this operator w/ push_back().
unsigned getTrueMemOrderLatency() const
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
ConstMIBundleOperands - Iterate over all operands in a const bundle of machine instructions.
A parsed version of the target data layout string in and methods for querying it.
void compress()
compress - Compress equivalence classes by numbering them 0 .
unsigned getNumClasses() const
getNumClasses - Return the number of equivalence classes after compress() was called.
unsigned join(unsigned a, unsigned b)
Join the equivalence classes of a and b.
SlotIndex getInstructionIndex(const MachineInstr &Instr) const
Returns the base index of the given instruction.
A set of physical registers with utility functions to track liveness when walking backward/forward th...
bool available(const MachineRegisterInfo &MRI, MCPhysReg Reg) const
Returns true if register Reg and no aliasing register is in the set.
void removeReg(MCPhysReg Reg)
Removes a physical register, all its sub-registers, and all its super-registers from the set.
void init(const TargetRegisterInfo &TRI)
(re-)initializes and clears the set.
void addLiveOuts(const MachineBasicBlock &MBB)
Adds all live-out registers of basic block MBB.
void addReg(MCPhysReg Reg)
Adds a physical register and all its sub-registers to the set.
void removeRegsInMask(const MachineOperand &MO, SmallVectorImpl< std::pair< MCPhysReg, const MachineOperand * > > *Clobbers=nullptr)
Removes physical registers clobbered by the regmask operand MO.
Describe properties that are true of each instruction in the target description file.
unsigned getNumOperands() const
Return the number of declared MachineOperands for this MachineInstruction.
bool hasImplicitUseOfPhysReg(unsigned Reg) const
Return true if this instruction implicitly uses the specified physical register.
bool hasImplicitDefOfPhysReg(unsigned Reg, const MCRegisterInfo *MRI=nullptr) const
Return true if this instruction implicitly defines the specified physical register.
MCRegAliasIterator enumerates all registers aliasing Reg.
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
MCSubRegIterator enumerates all sub-registers of Reg.
std::string getFullName() const
Return a formatted string to identify this block and its parent function.
iterator_range< succ_iterator > successors()
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted.
bool hasTailCall() const
Returns true if the function contains a tail call.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
const DataLayout & getDataLayout() const
Return the DataLayout attached to the Module associated to this MF.
Representation of each machine instruction.
bool isBarrier(QueryType Type=AnyInBundle) const
Returns true if the specified instruction stops control flow from executing the instruction immediate...
bool isCall(QueryType Type=AnyInBundle) const
bool registerDefIsDead(Register Reg, const TargetRegisterInfo *TRI=nullptr) const
Returns true if the register is dead in this machine instruction.
bool mayAlias(AAResults *AA, const MachineInstr &Other, bool UseTBAA) const
Returns true if this instruction's memory access aliases the memory access of Other.
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
iterator_range< mop_iterator > operands()
void print(raw_ostream &OS, bool IsStandalone=true, bool SkipOpers=false, bool SkipDebugLoc=false, bool AddNewLine=true, const TargetInstrInfo *TII=nullptr) const
Print this MI to OS.
bool isTransient() const
Return true if this is a transient instruction that is either very likely to be eliminated during reg...
const MachineOperand & getOperand(unsigned i) const
A description of a memory reference used in the backend.
MachineOperand class - Representation of each machine instruction operand.
unsigned getSubReg() const
bool readsReg() const
readsReg - Returns true if this operand reads the previous value of its register.
bool isReg() const
isReg - Tests if this is a MO_Register operand.
bool isRegMask() const
isRegMask - Tests if this is a MO_RegisterMask operand.
void setIsKill(bool Val=true)
void setIsUndef(bool Val=true)
Register getReg() const
getReg - Returns the register number.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
bool hasOneDef(Register RegNo) const
Return true if there is exactly one operand defining the specified register.
bool isConstantPhysReg(MCRegister PhysReg) const
Returns true if PhysReg is unallocatable and constant throughout the function.
unsigned getNumVirtRegs() const
getNumVirtRegs - Return the number of virtual registers created.
This class implements a map that also provides access to all stored values in a deterministic order.
typename VectorType::iterator iterator
ValueT & operator[](const KeyT &Key)
iterator find(const ValueType &Key)
void remove_if(Predicate Pred)
Remove the elements that match the predicate.
void addInstruction(unsigned Idx, const RegisterOperands &RegOpers, const MachineRegisterInfo &MRI)
Record pressure difference induced by the given operand list to node with index Idx.
void init(unsigned N)
Initialize an array of N PressureDiffs.
Special value supplied for machine level alias analysis.
Track the current register pressure at some position in the instruction stream, and remember the high...
void recede(SmallVectorImpl< RegisterMaskPair > *LiveUses=nullptr)
Recede across the previous instruction.
void recedeSkipDebugValues()
Recede until we find an instruction which is not a DebugValue.
MachineBasicBlock::const_iterator getPos() const
Get the MI position corresponding to this register pressure.
List of registers defined and used by a machine instruction.
void collect(const MachineInstr &MI, const TargetRegisterInfo &TRI, const MachineRegisterInfo &MRI, bool TrackLaneMasks, bool IgnoreDead)
Analyze the given instruction MI and fill in the Uses, Defs and DeadDefs list based on the MachineOpe...
void adjustLaneLiveness(const LiveIntervals &LIS, const MachineRegisterInfo &MRI, SlotIndex Pos, MachineInstr *AddFlagsMI=nullptr)
Use liveness information to find out which uses/defs are partially undefined/dead and adjust the Regi...
Wrapper class representing virtual and physical registers.
Kind getKind() const
Returns an enum value representing the kind of the dependence.
Kind
These are the different kinds of scheduling dependencies.
@ Output
A register output-dependence (aka WAW).
@ Anti
A register anti-dependence (aka WAR).
@ Data
Regular data dependence (aka true-dependence).
void setLatency(unsigned Lat)
Sets the latency for this edge.
@ Artificial
Arbitrary strong DAG edge (no real dependence).
@ MayAliasMem
Nonvolatile load/Store instructions that may alias.
bool isArtificial() const
Tests if this is an Order dependence that is marked as "artificial", meaning it isn't necessary for c...
Scheduling unit. This is a node in the scheduling DAG.
bool isCall
Is a function call.
bool addPredBarrier(SUnit *SU)
Adds a barrier edge to SU by calling addPred(), with latency 0 generally or latency 1 for a store fol...
unsigned TopReadyCycle
Cycle relative to start when node is ready.
unsigned NodeNum
Entry # of node in the node vector.
bool isUnbuffered
Uses an unbuffered resource.
SmallVectorImpl< SDep >::const_iterator const_pred_iterator
void setInstr(MachineInstr *MI)
Assigns the instruction for the SUnit.
unsigned short Latency
Node latency.
bool isBoundaryNode() const
Boundary nodes are placeholders for the boundary of the scheduling region.
bool hasPhysRegDefs
Has physreg defs that are being used.
unsigned BotReadyCycle
Cycle relative to end when node is ready.
SmallVector< SDep, 4 > Succs
All sunit successors.
bool hasReservedResource
Uses a reserved resource.
bool isCommutable
Is a commutable instruction.
bool hasPhysRegUses
Has physreg uses.
SmallVector< SDep, 4 > Preds
All sunit predecessors.
bool addPred(const SDep &D, bool Required=true)
Adds the specified edge as a pred of the current node if not already.
MachineInstr * getInstr() const
Returns the representative MachineInstr for this SUnit.
Internal state used to compute SchedDFSResult.
void visitPostorderNode(const SUnit *SU)
Called once for each node after all predecessors are visited.
bool joinPredSubtree(const SDep &PredDep, const SUnit *Succ, bool CheckLimit=true)
Joins the predecessor subtree with the successor that is its DFS parent.
void addConnection(unsigned FromTree, unsigned ToTree, unsigned Depth)
Called by finalize() to record a connection between trees.
void finalize()
Sets each node's subtree ID to the representative ID and record connections between trees.
void visitCrossEdge(const SDep &PredDep, const SUnit *Succ)
Adds a connection for cross edges.
void visitPostorderEdge(const SDep &PredDep, const SUnit *Succ)
Called once for each tree edge after calling visitPostOrderNode on the predecessor.
void visitPreorder(const SUnit *SU)
Initializes this node's instruction count.
bool isVisited(const SUnit *SU) const
Returns true if this node been visited by the DFS traversal.
SchedDFSImpl(SchedDFSResult &r)
Compute the values of each DAG node for various metrics during DFS.
void compute(ArrayRef< SUnit > SUnits)
Compute various metrics for the DAG with given roots.
void scheduleTree(unsigned SubtreeID)
Scheduler callback to update SubtreeConnectLevels when a tree is initially scheduled.
DenseMap< MachineInstr *, SUnit * > MISUnitMap
After calling BuildSchedGraph, each machine instruction in the current scheduling region is mapped to...
void addVRegUseDeps(SUnit *SU, unsigned OperIdx)
Adds a register data dependency if the instruction that defines the virtual register used at OperIdx ...
void addVRegDefDeps(SUnit *SU, unsigned OperIdx)
Adds register output and data dependencies from this SUnit to instructions that occur later in the sa...
virtual void finishBlock()
Cleans up after scheduling in the given block.
MachineBasicBlock::iterator end() const
Returns an iterator to the bottom of the current scheduling region.
std::string getDAGName() const override
Returns a label for the region of code covered by the DAG.
MachineBasicBlock * BB
The block in which to insert instructions.
MachineInstr * FirstDbgValue
virtual void startBlock(MachineBasicBlock *BB)
Prepares to perform scheduling in the given block.
bool CanHandleTerminators
The standard DAG builder does not normally include terminators as DAG nodes because it does not creat...
void addBarrierChain(Value2SUsMap &map)
Adds barrier chain edges from all SUs in map, and then clear the map.
void reduceHugeMemNodeMaps(Value2SUsMap &stores, Value2SUsMap &loads, unsigned N)
Reduces maps in FIFO order, by N SUs.
void addPhysRegDeps(SUnit *SU, unsigned OperIdx)
Adds register dependencies (data, anti, and output) from this SUnit to following instructions in the ...
MachineBasicBlock::iterator RegionEnd
The end of the range to be scheduled.
VReg2SUnitOperIdxMultiMap CurrentVRegUses
Tracks the last instructions in this region using each virtual register.
void addChainDependencies(SUnit *SU, SUList &SUs, unsigned Latency)
Adds dependencies as needed from all SUs in list to SU.
const MCSchedClassDesc * getSchedClass(SUnit *SU) const
Resolves and cache a resolved scheduling class for an SUnit.
void fixupKills(MachineBasicBlock &MBB)
Fixes register kill flags that scheduling has made invalid.
void addPhysRegDataDeps(SUnit *SU, unsigned OperIdx)
MO is an operand of SU's instruction that defines a physical register.
ScheduleDAGInstrs(MachineFunction &mf, const MachineLoopInfo *mli, bool RemoveKillFlags=false)
LaneBitmask getLaneMaskForMO(const MachineOperand &MO) const
Returns a mask for which lanes get read/written by the given (register) machine operand.
DbgValueVector DbgValues
Remember instruction that precedes DBG_VALUE.
SUnit * newSUnit(MachineInstr *MI)
Creates a new SUnit and return a ptr to it.
void initSUnits()
Creates an SUnit for each real instruction, numbered in top-down topological order.
bool addEdge(SUnit *SuccSU, const SDep &PredDep)
Add a DAG edge to the given SU with the given predecessor dependence data.
ScheduleDAGTopologicalSort Topo
Topo - A topological ordering for SUnits which permits fast IsReachable and similar queries.
std::list< SUnit * > SUList
A list of SUnits, used in Value2SUsMap, during DAG construction.
SUnit * BarrierChain
Remember a generic side-effecting instruction as we proceed.
bool TrackLaneMasks
Whether lane masks should get tracked.
void dumpNode(const SUnit &SU) const override
UndefValue * UnknownValue
For an unanalyzable memory access, this Value is used in maps.
VReg2SUnitMultiMap CurrentVRegDefs
Tracks the last instruction(s) in this region defining each virtual register.
LivePhysRegs LiveRegs
Set of live physical registers for updating kill flags.
MachineBasicBlock::iterator begin() const
Returns an iterator to the top of the current scheduling region.
void buildSchedGraph(AAResults *AA, RegPressureTracker *RPTracker=nullptr, PressureDiffs *PDiffs=nullptr, LiveIntervals *LIS=nullptr, bool TrackLaneMasks=false)
Builds SUnits for the current region.
TargetSchedModel SchedModel
TargetSchedModel provides an interface to the machine model.
virtual void exitRegion()
Called when the scheduler has finished scheduling the current region.
bool canAddEdge(SUnit *SuccSU, SUnit *PredSU)
True if an edge can be added from PredSU to SuccSU without creating a cycle.
void insertBarrierChain(Value2SUsMap &map)
Inserts a barrier chain in a huge region, far below current SU.
bool RemoveKillFlags
True if the DAG builder should remove kill flags (in preparation for rescheduling).
Reg2SUnitsMap Defs
Defs, Uses - Remember where defs and uses of each register are as we iterate upward through the instr...
MachineBasicBlock::iterator RegionBegin
The beginning of the range to be scheduled.
void addSchedBarrierDeps()
Adds dependencies from instructions in the current list of instructions being scheduled to scheduling...
virtual void enterRegion(MachineBasicBlock *bb, MachineBasicBlock::iterator begin, MachineBasicBlock::iterator end, unsigned regioninstrs)
Initialize the DAG and common scheduler state for a new scheduling region.
void dump() const override
void addChainDependency(SUnit *SUa, SUnit *SUb, unsigned Latency=0)
Adds a chain edge between SUa and SUb, but only if both AAResults and Target fail to deny the depende...
unsigned NumRegionInstrs
Instructions in this region (distance(RegionBegin, RegionEnd)).
const MachineFrameInfo & MFI
bool deadDefHasNoUse(const MachineOperand &MO)
Returns true if the def register in MO has no uses.
std::string getGraphNodeLabel(const SUnit *SU) const override
Returns a label for a DAG node that points to an instruction.
void MarkDirty()
Mark the ordering as temporarily broken, after a new node has been added.
bool IsReachable(const SUnit *SU, const SUnit *TargetSU)
Checks if SU is reachable from TargetSU.
void AddPredQueued(SUnit *Y, SUnit *X)
Queues an update to the topological ordering to accommodate an edge to be added from SUnit X to SUnit...
MachineRegisterInfo & MRI
Virtual/real register map.
void clearDAG()
Clears the DAG state (between regions).
std::vector< SUnit > SUnits
The scheduling units.
const TargetRegisterInfo * TRI
Target processor register info.
SUnit EntrySU
Special node for the region entry.
MachineFunction & MF
Machine function.
void dumpNodeAll(const SUnit &SU) const
void dumpNodeName(const SUnit &SU) const
SUnit ExitSU
Special node for the region exit.
SlotIndex - An opaque wrapper around machine indexes.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
reference emplace_back(ArgTypes &&... Args)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
iterator find(const KeyT &Key)
Find an element by its key.
bool empty() const
Returns true if the set is empty.
bool contains(const KeyT &Key) const
Returns true if this set contains an element identified by Key.
void clear()
Clears the set.
iterator erase(iterator I)
Erases an existing element identified by a valid iterator.
iterator end()
Returns an iterator past this container.
iterator insert(const ValueT &Val)
Insert a new element at the tail of the subset list.
void eraseAll(const KeyT &K)
Erase all elements with the given key.
RangePair equal_range(const KeyT &K)
The bounds of the range of items sharing Key K.
iterator_base< SparseMultiSet * > iterator
std::pair< iterator, iterator > RangePair
void setUniverse(unsigned U)
Set the universe size which determines the largest key the set can hold.
SparseSet - Fast set implementation for objects that can be identified by small unsigned keys.
size_type size() const
size - Returns the number of elements in the set.
iterator erase(iterator I)
erase - Erases an existing element identified by a valid iterator.
size_type count(const KeyT &Key) const
count - Returns 1 if this set contains an element identified by Key, 0 otherwise.
void setUniverse(unsigned U)
setUniverse - Set the universe size which determines the largest key the set can hold.
const bool HasDisjunctSubRegs
Whether the class supports two (or more) disjunct subregister indices.
LaneBitmask getLaneMask() const
Returns the combination of all lane masks of register in this class.
LaneBitmask getSubRegIndexLaneMask(unsigned SubIdx) const
Return a bitmask representing the parts of a register that are covered by SubIdx.
ProcResIter getWriteProcResEnd(const MCSchedClassDesc *SC) const
bool hasInstrSchedModel() const
Return true if this machine model includes an instruction-level scheduling model.
unsigned computeOutputLatency(const MachineInstr *DefMI, unsigned DefOperIdx, const MachineInstr *DepMI) const
Output dependency latency of a pair of defs of the same register.
void init(const TargetSubtargetInfo *TSInfo)
Initialize the machine model for instruction scheduling.
unsigned computeOperandLatency(const MachineInstr *DefMI, unsigned DefOperIdx, const MachineInstr *UseMI, unsigned UseOperIdx) const
Compute operand latency based on the available machine model.
const MCProcResourceDesc * getProcResource(unsigned PIdx) const
Get a processor resource by ID for convenience.
ProcResIter getWriteProcResBegin(const MCSchedClassDesc *SC) const
TargetSubtargetInfo - Generic base class for all target subtargets.
The instances of the Type class are immutable: once they are created, they are never changed.
'undef' values are things that do not have specified contents.
A Use represents the edge between a Value definition and its users.
LLVM Value Representation.
Iterator for intrusive lists based on ilist_node.
This class implements an extremely fast bulk output stream that can only output to a stream.
A raw_ostream that writes to an std::string.
std::string & str()
Returns the string's reference.
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ C
The default llvm calling convention, compatible with C.
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
bool getUnderlyingObjectsForCodeGen(const Value *V, SmallVectorImpl< Value * > &Objects)
This is a wrapper around getUnderlyingObjects and adds support for basic ptrtoint+arithmetic+inttoptr...
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
auto reverse(ContainerTy &&C)
decltype(auto) get(const PointerIntPair< PointerTy, IntBits, IntType, PtrTraits, Info > &Pair)
void sort(IteratorTy Start, IteratorTy End)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
IterT skipDebugInstructionsBackward(IterT It, IterT Begin, bool SkipPseudoOp=true)
Decrement It until it points to a non-debug instruction or to Begin and return the resulting iterator...
format_object< Ts... > format(const char *Fmt, const Ts &... Vals)
These are helper functions used to produce formatted output.
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
bool isIdentifiedObject(const Value *V)
Return true if this pointer refers to a distinct and identifiable object.
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
Represent the ILP of the subDAG rooted at a DAG node.
void print(raw_ostream &OS) const
static constexpr LaneBitmask getAll()
constexpr bool any() const
Summarize the scheduling resources required for an instruction of a particular scheduling class.
Identify one of the processor resource kinds consumed by a particular scheduling class for the specif...
Record a physical register access.
Mapping from virtual register to SUnit including an operand index.
An individual mapping from virtual register number to SUnit.