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);
326 ST.adjustSchedDependency(SU, OperIdx, DefSU,
I->OpIdx, Dep);
361 for (
bool isBegin =
I ==
B; !isBegin; ) {
362 isBegin = (--
I) ==
B;
424 if (OtherMO.isReg() && OtherMO.isDef() && OtherMO.getReg() == Reg)
425 KillLaneMask &= ~getLaneMaskForMO(OtherMO);
445 if ((LaneMask & KillLaneMask).
none()) {
450 if ((LaneMask & DefLaneMask).any()) {
456 ST.adjustSchedDependency(SU, OperIdx, UseSU,
I->OperandIndex, Dep);
460 LaneMask &= ~KillLaneMask;
462 if (LaneMask.
any()) {
463 I->LaneMask = LaneMask;
485 if ((V2SU.LaneMask & LaneMask).none())
488 SUnit *DefSU = V2SU.SU;
504 LaneBitmask OverlapMask = V2SU.LaneMask & LaneMask;
505 LaneBitmask NonOverlapMask = V2SU.LaneMask & ~LaneMask;
507 V2SU.LaneMask = OverlapMask;
508 if (NonOverlapMask.
any())
524 assert(!
MI->isDebugOrPseudoInstr());
539 if ((PrevDefLaneMask & LaneMask).
none())
551 return MI->isCall() ||
MI->hasUnmodeledSideEffects() ||
552 (
MI->hasOrderedMemoryRef() && !
MI->isDereferenceableInvariantLoad());
582 if (
MI.isDebugOrPseudoInstr())
624 unsigned NumNodes = 0;
627 unsigned TrueMemOrderLatency;
648 assert(NumNodes >= Itr->second.size());
649 NumNodes -= Itr->second.size();
661 unsigned inline size()
const {
return NumNodes; }
666 for (
auto &
I : *
this)
667 NumNodes +=
I.second.size();
671 return TrueMemOrderLatency;
679 for (
auto &
I : Val2SUsMap)
688 if (Itr != Val2SUsMap.
end())
696 for (
auto &[V, SUs] : map) {
710 SUList &sus = CurrItr->second;
711 SUList::iterator SUItr = sus.begin(), SUEE = sus.end();
712 for (; SUItr != SUEE; ++SUItr) {
725 if (SUItr != sus.begin())
726 sus.erase(sus.begin(), SUItr);
730 map.
remove_if([&](std::pair<ValueType, SUList> &mapEntry) {
731 return (mapEntry.second.empty()); });
741 bool TrackLaneMasks) {
793 "Only BuildGraph should update Defs/Uses");
817 if (
MI.isDebugValue() ||
MI.isDebugPHI()) {
822 if (
MI.isDebugLabel() ||
MI.isDebugRef() ||
MI.isPseudoProbe())
826 assert(SU &&
"No SUnit mapped to this MI");
835 if (PDiffs !=
nullptr)
841 RPTracker->
recede(RegOpers);
846 "Cannot schedule terminators or labels!");
853 bool HasVRegDef =
false;
854 for (
unsigned j = 0, n =
MI.getNumOperands(); j != n; ++j) {
859 if (Reg.isPhysical()) {
861 }
else if (Reg.isVirtual()) {
867 for (
unsigned j = 0, n =
MI.getNumOperands(); j != n; ++j) {
876 if (Reg.isPhysical()) {
878 }
else if (Reg.isVirtual() && MO.
readsReg()) {
907 LLVM_DEBUG(
dbgs() <<
"Global memory object and new barrier chain: SU("
922 if (
MI.mayRaiseFPException()) {
936 if (!
MI.mayStore() &&
937 !(
MI.mayLoad() && !
MI.isDereferenceableInvariantLoad()))
966 bool ThisMayAlias = UnderlObj.mayAlias();
976 bool ThisMayAlias = UnderlObj.mayAlias();
979 (ThisMayAlias ? Stores : NonAliasStores).insert(SU, V);
996 bool ThisMayAlias = UnderlObj.mayAlias();
1003 (ThisMayAlias ? Loads : NonAliasLoads).insert(SU, V);
1017 dbgs() <<
"Reducing NonAliasStores and NonAliasLoads maps.\n";);
1034 PSV->printCustom(
OS);
1039 for (
const auto &[ValType, SUs] : *
this) {
1040 if (isa<const Value *>(ValType)) {
1041 const Value *V = cast<const Value *>(ValType);
1042 if (isa<UndefValue>(V))
1043 dbgs() <<
"Unknown";
1045 V->printAsOperand(
dbgs());
1046 }
else if (isa<const PseudoSourceValue *>(ValType))
1047 dbgs() << cast<const PseudoSourceValue *>(ValType);
1059 dbgs() <<
"Loading SUnits:\n"; loads.
dump());
1062 std::vector<unsigned> NodeNums;
1063 NodeNums.reserve(
stores.size() + loads.
size());
1064 for (
const auto &[V, SUs] :
stores) {
1066 for (
const auto *SU : SUs)
1067 NodeNums.push_back(SU->NodeNum);
1069 for (
const auto &[V, SUs] : loads) {
1071 for (
const auto *SU : SUs)
1072 NodeNums.push_back(SU->NodeNum);
1080 SUnit *newBarrierChain = &
SUnits[*(NodeNums.end() -
N)];
1103 dbgs() <<
"Loading SUnits:\n"; loads.
dump());
1109 if (!MO.isReg() || !MO.readsReg())
1117 MO.setIsKill(IsKill);
1131 if (
MI.isDebugOrPseudoInstr())
1152 if (!
MI.isBundled()) {
1163 while (
I->isBundledWithSucc())
1166 if (!
I->isDebugOrPseudoInstr())
1169 }
while (
I != Bundle);
1175#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1186#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1244 std::vector<std::pair<const SUnit *, const SUnit*>> ConnectionPairs;
1248 unsigned ParentNodeID;
1249 unsigned SubInstrCount = 0;
1252 RootData(
unsigned id): NodeID(
id),
1253 ParentNodeID(SchedDFSResult::InvalidSubtreeID) {}
1255 unsigned getSparseSetIndex()
const {
return NodeID; }
1270 return R.DFSNodeData[SU->
NodeNum].SubtreeID
1271 != SchedDFSResult::InvalidSubtreeID;
1277 R.DFSNodeData[SU->
NodeNum].InstrCount =
1301 if ((
InstrCount - R.DFSNodeData[PredNum].InstrCount) < R.SubtreeLimit)
1302 joinPredSubtree(PredDep, SU,
false);
1305 if (R.DFSNodeData[PredNum].SubtreeID == PredNum) {
1308 if (RootSet[PredNum].ParentNodeID == SchedDFSResult::InvalidSubtreeID)
1309 RootSet[PredNum].ParentNodeID = SU->
NodeNum;
1311 else if (RootSet.
count(PredNum)) {
1316 RData.SubInstrCount += RootSet[PredNum].SubInstrCount;
1317 RootSet.
erase(PredNum);
1327 R.DFSNodeData[Succ->
NodeNum].InstrCount
1329 joinPredSubtree(PredDep, Succ);
1334 ConnectionPairs.emplace_back(PredDep.
getSUnit(), Succ);
1343 &&
"number of roots should match trees");
1344 for (
const RootData &Root : RootSet) {
1345 unsigned TreeID = SubtreeClasses[Root.NodeID];
1346 if (Root.ParentNodeID != SchedDFSResult::InvalidSubtreeID)
1347 R.DFSTreeData[TreeID].ParentTreeID = SubtreeClasses[Root.ParentNodeID];
1348 R.DFSTreeData[TreeID].SubInstrCount = Root.SubInstrCount;
1354 R.SubtreeConnections.resize(SubtreeClasses.
getNumClasses());
1355 R.SubtreeConnectLevels.resize(SubtreeClasses.
getNumClasses());
1357 for (
unsigned Idx = 0,
End = R.DFSNodeData.size();
Idx !=
End; ++
Idx) {
1358 R.DFSNodeData[
Idx].SubtreeID = SubtreeClasses[
Idx];
1360 << R.DFSNodeData[
Idx].SubtreeID <<
'\n');
1362 for (
const auto &[Pred, Succ] : ConnectionPairs) {
1363 unsigned PredTree = SubtreeClasses[Pred->NodeNum];
1364 unsigned SuccTree = SubtreeClasses[Succ->NodeNum];
1365 if (PredTree == SuccTree)
1367 unsigned Depth = Pred->getDepth();
1368 addConnection(PredTree, SuccTree,
Depth);
1369 addConnection(SuccTree, PredTree,
Depth);
1377 bool CheckLimit =
true) {
1382 unsigned PredNum = PredSU->
NodeNum;
1383 if (R.DFSNodeData[PredNum].SubtreeID != PredNum)
1388 unsigned NumDataSucs = 0;
1389 for (
const SDep &SuccDep : PredSU->
Succs) {
1391 if (++NumDataSucs >= 4)
1395 if (CheckLimit && R.DFSNodeData[PredNum].InstrCount > R.SubtreeLimit)
1397 R.DFSNodeData[PredNum].SubtreeID = Succ->
NodeNum;
1409 R.SubtreeConnections[FromTree];
1410 for (SchedDFSResult::Connection &
C : Connections) {
1411 if (
C.TreeID == ToTree) {
1412 C.Level = std::max(
C.Level,
Depth);
1416 Connections.
push_back(SchedDFSResult::Connection(ToTree,
Depth));
1417 FromTree = R.DFSTreeData[FromTree].ParentTreeID;
1418 }
while (FromTree != SchedDFSResult::InvalidSubtreeID);
1427class SchedDAGReverseDFS {
1428 std::vector<std::pair<const SUnit *, SUnit::const_pred_iterator>> DFSStack;
1431 bool isComplete()
const {
return DFSStack.empty(); }
1433 void follow(
const SUnit *SU) {
1434 DFSStack.emplace_back(SU, SU->
Preds.begin());
1436 void advance() { ++DFSStack.back().second; }
1438 const SDep *backtrack() {
1439 DFSStack.pop_back();
1440 return DFSStack.empty() ? nullptr : std::prev(DFSStack.back().second);
1443 const SUnit *getCurr()
const {
return DFSStack.back().first; }
1448 return getCurr()->
Preds.end();
1474 SchedDAGReverseDFS DFS;
1479 while (DFS.getPred() != DFS.getPredEnd()) {
1480 const SDep &PredDep = *DFS.getPred();
1496 const SUnit *Child = DFS.getCurr();
1497 const SDep *PredDep = DFS.backtrack();
1501 if (DFS.isComplete())
1512 for (
const Connection &
C : SubtreeConnections[SubtreeID]) {
1513 SubtreeConnectLevels[
C.TreeID] =
1514 std::max(SubtreeConnectLevels[
C.TreeID],
C.Level);
1516 << SubtreeConnectLevels[
C.TreeID] <<
'\n');
1520#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1530 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)
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 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.
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.
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
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.
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).
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.
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.