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");
213 if (Reg.isPhysical()) {
216 }
else if (Reg.isVirtual() && MO.readsReg()) {
225 for (
const auto &LI : Succ->liveins()) {
227 auto [Unit, Mask] = *U;
249 bool ImplicitPseudoDef = (OperIdx >= DefMIDesc.
getNumOperands() &&
261 int UseOpIdx =
I->OpIdx;
262 bool ImplicitPseudoUse =
false;
274 ImplicitPseudoUse = UseOpIdx >= ((int)UseMIDesc.
getNumOperands()) &&
279 if (!ImplicitPseudoDef && !ImplicitPseudoUse) {
281 UseInstr, UseOpIdx));
285 ST.adjustSchedDependency(SU, OperIdx, UseSU, UseOpIdx, Dep, &
SchedModel);
326 ST.adjustSchedDependency(SU, OperIdx, DefSU,
I->OpIdx, Dep,
362 for (
bool isBegin =
I ==
B; !isBegin; ) {
363 isBegin = (--
I) ==
B;
425 if (OtherMO.isReg() && OtherMO.isDef() && OtherMO.getReg() == Reg)
426 KillLaneMask &= ~getLaneMaskForMO(OtherMO);
446 if ((LaneMask & KillLaneMask).
none()) {
451 if ((LaneMask & DefLaneMask).any()) {
457 ST.adjustSchedDependency(SU, OperIdx, UseSU,
I->OperandIndex, Dep,
462 LaneMask &= ~KillLaneMask;
464 if (LaneMask.
any()) {
465 I->LaneMask = LaneMask;
487 if ((V2SU.LaneMask & LaneMask).none())
490 SUnit *DefSU = V2SU.SU;
506 LaneBitmask OverlapMask = V2SU.LaneMask & LaneMask;
507 LaneBitmask NonOverlapMask = V2SU.LaneMask & ~LaneMask;
509 V2SU.LaneMask = OverlapMask;
510 if (NonOverlapMask.
any())
526 assert(!
MI->isDebugOrPseudoInstr());
541 if ((PrevDefLaneMask & LaneMask).
none())
553 return MI->isCall() ||
MI->hasUnmodeledSideEffects() ||
554 (
MI->hasOrderedMemoryRef() && !
MI->isDereferenceableInvariantLoad());
584 if (
MI.isDebugOrPseudoInstr())
626 unsigned NumNodes = 0;
629 unsigned TrueMemOrderLatency;
650 assert(NumNodes >= Itr->second.size());
651 NumNodes -= Itr->second.size();
663 unsigned inline size()
const {
return NumNodes; }
668 for (
auto &
I : *
this)
669 NumNodes +=
I.second.size();
673 return TrueMemOrderLatency;
681 for (
auto &
I : Val2SUsMap)
690 if (Itr != Val2SUsMap.
end())
698 for (
auto &[V, SUs] : map) {
712 SUList &sus = CurrItr->second;
713 SUList::iterator SUItr = sus.begin(), SUEE = sus.end();
714 for (; SUItr != SUEE; ++SUItr) {
727 if (SUItr != sus.begin())
728 sus.erase(sus.begin(), SUItr);
732 map.
remove_if([&](std::pair<ValueType, SUList> &mapEntry) {
733 return (mapEntry.second.empty()); });
743 bool TrackLaneMasks) {
795 "Only BuildGraph should update Defs/Uses");
819 if (
MI.isDebugValue() ||
MI.isDebugPHI()) {
824 if (
MI.isDebugLabel() ||
MI.isDebugRef() ||
MI.isPseudoProbe())
828 assert(SU &&
"No SUnit mapped to this MI");
837 if (PDiffs !=
nullptr)
843 RPTracker->
recede(RegOpers);
848 "Cannot schedule terminators or labels!");
855 bool HasVRegDef =
false;
856 for (
unsigned j = 0, n =
MI.getNumOperands(); j != n; ++j) {
861 if (Reg.isPhysical()) {
863 }
else if (Reg.isVirtual()) {
869 for (
unsigned j = 0, n =
MI.getNumOperands(); j != n; ++j) {
878 if (Reg.isPhysical()) {
880 }
else if (Reg.isVirtual() && MO.
readsReg()) {
909 LLVM_DEBUG(
dbgs() <<
"Global memory object and new barrier chain: SU("
924 if (
MI.mayRaiseFPException()) {
938 if (!
MI.mayStore() &&
939 !(
MI.mayLoad() && !
MI.isDereferenceableInvariantLoad()))
968 bool ThisMayAlias = UnderlObj.mayAlias();
978 bool ThisMayAlias = UnderlObj.mayAlias();
981 (ThisMayAlias ? Stores : NonAliasStores).insert(SU, V);
998 bool ThisMayAlias = UnderlObj.mayAlias();
1005 (ThisMayAlias ? Loads : NonAliasLoads).insert(SU, V);
1019 dbgs() <<
"Reducing NonAliasStores and NonAliasLoads maps.\n";);
1036 PSV->printCustom(
OS);
1041 for (
const auto &[ValType, SUs] : *
this) {
1042 if (isa<const Value *>(ValType)) {
1043 const Value *V = cast<const Value *>(ValType);
1044 if (isa<UndefValue>(V))
1045 dbgs() <<
"Unknown";
1047 V->printAsOperand(
dbgs());
1048 }
else if (isa<const PseudoSourceValue *>(ValType))
1049 dbgs() << cast<const PseudoSourceValue *>(ValType);
1061 dbgs() <<
"Loading SUnits:\n"; loads.
dump());
1064 std::vector<unsigned> NodeNums;
1065 NodeNums.reserve(
stores.size() + loads.
size());
1066 for (
const auto &[V, SUs] :
stores) {
1068 for (
const auto *SU : SUs)
1069 NodeNums.push_back(SU->NodeNum);
1071 for (
const auto &[V, SUs] : loads) {
1073 for (
const auto *SU : SUs)
1074 NodeNums.push_back(SU->NodeNum);
1082 SUnit *newBarrierChain = &
SUnits[*(NodeNums.end() -
N)];
1105 dbgs() <<
"Loading SUnits:\n"; loads.
dump());
1111 if (!MO.isReg() || !MO.readsReg())
1135 if (
MI.isDebugOrPseudoInstr())
1156 if (!
MI.isBundled()) {
1167 while (
I->isBundledWithSucc())
1170 if (!
I->isDebugOrPseudoInstr())
1173 }
while (
I != Bundle);
1179#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1190#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1248 std::vector<std::pair<const SUnit *, const SUnit*>> ConnectionPairs;
1252 unsigned ParentNodeID;
1253 unsigned SubInstrCount = 0;
1256 RootData(
unsigned id): NodeID(
id),
1257 ParentNodeID(SchedDFSResult::InvalidSubtreeID) {}
1259 unsigned getSparseSetIndex()
const {
return NodeID; }
1274 return R.DFSNodeData[SU->
NodeNum].SubtreeID
1275 != SchedDFSResult::InvalidSubtreeID;
1281 R.DFSNodeData[SU->
NodeNum].InstrCount =
1305 if ((
InstrCount - R.DFSNodeData[PredNum].InstrCount) < R.SubtreeLimit)
1306 joinPredSubtree(PredDep, SU,
false);
1309 if (R.DFSNodeData[PredNum].SubtreeID == PredNum) {
1312 if (RootSet[PredNum].ParentNodeID == SchedDFSResult::InvalidSubtreeID)
1313 RootSet[PredNum].ParentNodeID = SU->
NodeNum;
1315 else if (RootSet.
count(PredNum)) {
1320 RData.SubInstrCount += RootSet[PredNum].SubInstrCount;
1321 RootSet.
erase(PredNum);
1331 R.DFSNodeData[Succ->
NodeNum].InstrCount
1333 joinPredSubtree(PredDep, Succ);
1338 ConnectionPairs.emplace_back(PredDep.
getSUnit(), Succ);
1347 &&
"number of roots should match trees");
1348 for (
const RootData &Root : RootSet) {
1349 unsigned TreeID = SubtreeClasses[Root.NodeID];
1350 if (Root.ParentNodeID != SchedDFSResult::InvalidSubtreeID)
1351 R.DFSTreeData[TreeID].ParentTreeID = SubtreeClasses[Root.ParentNodeID];
1352 R.DFSTreeData[TreeID].SubInstrCount = Root.SubInstrCount;
1358 R.SubtreeConnections.resize(SubtreeClasses.
getNumClasses());
1359 R.SubtreeConnectLevels.resize(SubtreeClasses.
getNumClasses());
1361 for (
unsigned Idx = 0,
End = R.DFSNodeData.size();
Idx !=
End; ++
Idx) {
1362 R.DFSNodeData[
Idx].SubtreeID = SubtreeClasses[
Idx];
1364 << R.DFSNodeData[
Idx].SubtreeID <<
'\n');
1366 for (
const auto &[Pred, Succ] : ConnectionPairs) {
1367 unsigned PredTree = SubtreeClasses[Pred->NodeNum];
1368 unsigned SuccTree = SubtreeClasses[Succ->NodeNum];
1369 if (PredTree == SuccTree)
1371 unsigned Depth = Pred->getDepth();
1372 addConnection(PredTree, SuccTree,
Depth);
1373 addConnection(SuccTree, PredTree,
Depth);
1381 bool CheckLimit =
true) {
1386 unsigned PredNum = PredSU->
NodeNum;
1387 if (R.DFSNodeData[PredNum].SubtreeID != PredNum)
1392 unsigned NumDataSucs = 0;
1393 for (
const SDep &SuccDep : PredSU->
Succs) {
1395 if (++NumDataSucs >= 4)
1399 if (CheckLimit && R.DFSNodeData[PredNum].InstrCount > R.SubtreeLimit)
1401 R.DFSNodeData[PredNum].SubtreeID = Succ->
NodeNum;
1413 R.SubtreeConnections[FromTree];
1414 for (SchedDFSResult::Connection &
C : Connections) {
1415 if (
C.TreeID == ToTree) {
1416 C.Level = std::max(
C.Level,
Depth);
1420 Connections.
push_back(SchedDFSResult::Connection(ToTree,
Depth));
1421 FromTree = R.DFSTreeData[FromTree].ParentTreeID;
1422 }
while (FromTree != SchedDFSResult::InvalidSubtreeID);
1431class SchedDAGReverseDFS {
1432 std::vector<std::pair<const SUnit *, SUnit::const_pred_iterator>> DFSStack;
1435 bool isComplete()
const {
return DFSStack.empty(); }
1437 void follow(
const SUnit *SU) {
1438 DFSStack.emplace_back(SU, SU->
Preds.begin());
1440 void advance() { ++DFSStack.back().second; }
1442 const SDep *backtrack() {
1443 DFSStack.pop_back();
1444 return DFSStack.empty() ? nullptr : std::prev(DFSStack.back().second);
1447 const SUnit *getCurr()
const {
return DFSStack.back().first; }
1452 return getCurr()->
Preds.end();
1478 SchedDAGReverseDFS DFS;
1483 while (DFS.getPred() != DFS.getPredEnd()) {
1484 const SDep &PredDep = *DFS.getPred();
1500 const SUnit *Child = DFS.getCurr();
1501 const SDep *PredDep = DFS.backtrack();
1505 if (DFS.isComplete())
1516 for (
const Connection &
C : SubtreeConnections[SubtreeID]) {
1517 SubtreeConnectLevels[
C.TreeID] =
1518 std::max(SubtreeConnectLevels[
C.TreeID],
C.Level);
1520 << SubtreeConnectLevels[
C.TreeID] <<
'\n');
1524#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1534 dbgs() << *
this <<
'\n';
static cl::opt< bool > UseAA("aarch64-use-aa", cl::init(true), cl::desc("Enable the use of AA during codegen."))
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-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)
static Register UseReg(const MachineOperand &MO)
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 void toggleKills(const MachineRegisterInfo &MRI, LiveRegUnits &LiveRegs, MachineInstr &MI, bool addToLiveRegs)
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 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 register units used to track register liveness.
bool available(MCPhysReg Reg) const
Returns true if no part of physical register Reg is live.
void init(const TargetRegisterInfo &TRI)
Initialize and clear the set.
void addReg(MCPhysReg Reg)
Adds register units covered by physical register Reg.
void addLiveOuts(const MachineBasicBlock &MBB)
Adds registers living out of block MBB.
void removeRegsNotPreserved(const uint32_t *RegMask)
Removes register units not preserved by the regmask RegMask.
void removeReg(MCPhysReg Reg)
Removes all register units covered by physical register Reg.
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.
MCRegUnitMaskIterator enumerates a list of register units and their associated lane masks for Reg.
iterator_range< MCRegUnitIterator > regunits(MCRegister Reg) const
Returns an iterator range over all regunits for Reg.
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
Instructions::iterator instr_iterator
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
iterator_range< filtered_mop_iterator > all_uses()
Returns an iterator range over all operands that are (explicit or implicit) register uses.
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.
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.
const uint32_t * getRegMask() const
getRegMask - Returns a bit mask of registers preserved by this RegMask operand.
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 isReserved(MCRegister PhysReg) const
isReserved - Returns true when PhysReg is a reserved 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.
LiveRegUnits LiveRegs
Set of live physical registers for updating kill flags.
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
RegUnit2SUnitsMap Defs
Defs, Uses - Remember where defs and uses of each register are as we iterate upward through the instr...
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.
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).
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.
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.
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.