41#include "llvm/Config/llvm-config.h"
63#define DEBUG_TYPE "machine-scheduler"
67 cl::desc(
"Enable use of AA during MI DAG construction"));
80 "prior to scheduling, at which point a trade-off "
81 "is made to avoid excessive compile time."));
85 cl::desc(
"A huge scheduling region will have maps reduced by this many "
86 "nodes at a time. Defaults to HugeRegion / 2."));
88#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
91 cl::desc(
"Report top/bottom cycles when dumping SUnit instances"));
103#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
105 for (
const SUnit *SU : L) {
106 dbgs() <<
"SU(" << SU->NodeNum <<
")";
116 bool RemoveKillFlags)
117 :
ScheduleDAG(mf), MLI(mli), MFI(mf.getFrameInfo()),
118 RemoveKillFlags(RemoveKillFlags),
120 Type::getVoidTy(mf.
getFunction().getContext()))), Topo(SUnits, &ExitSU) {
135 auto AllMMOsOkay = [&]() {
138 if (MMO->isVolatile() || MMO->isAtomic())
153 if (PSV->isAliased(&MFI))
156 bool MayAlias = PSV->mayAlias(&MFI);
158 }
else if (
const Value *V = MMO->getValue()) {
163 for (
Value *V : Objs) {
173 if (!AllMMOsOkay()) {
193 unsigned regioninstrs) {
194 assert(bb ==
BB &&
"startBlock should set BB");
214 if (Reg.isPhysical()) {
217 }
else if (Reg.isVirtual() && MO.readsReg()) {
226 for (
const auto &LI : Succ->liveins()) {
228 auto [Unit, Mask] = *U;
250 bool ImplicitPseudoDef = (OperIdx >= DefMIDesc.
getNumOperands() &&
262 int UseOpIdx =
I->OpIdx;
263 bool ImplicitPseudoUse =
false;
275 ImplicitPseudoUse = UseOpIdx >= ((int)UseMIDesc.
getNumOperands()) &&
280 if (!ImplicitPseudoDef && !ImplicitPseudoUse) {
282 UseInstr, UseOpIdx));
286 ST.adjustSchedDependency(SU, OperIdx, UseSU, UseOpIdx, Dep, &
SchedModel);
327 ST.adjustSchedDependency(SU, OperIdx, DefSU,
I->OpIdx, Dep,
363 for (
bool isBegin =
I ==
B; !isBegin; ) {
364 isBegin = (--
I) ==
B;
426 if (OtherMO.isReg() && OtherMO.isDef() && OtherMO.getReg() == Reg)
427 KillLaneMask &= ~getLaneMaskForMO(OtherMO);
447 if ((LaneMask & KillLaneMask).
none()) {
452 if ((LaneMask & DefLaneMask).any()) {
458 ST.adjustSchedDependency(SU, OperIdx, UseSU,
I->OperandIndex, Dep,
463 LaneMask &= ~KillLaneMask;
465 if (LaneMask.
any()) {
466 I->LaneMask = LaneMask;
488 if ((V2SU.LaneMask & LaneMask).none())
491 SUnit *DefSU = V2SU.SU;
507 LaneBitmask OverlapMask = V2SU.LaneMask & LaneMask;
508 LaneBitmask NonOverlapMask = V2SU.LaneMask & ~LaneMask;
510 V2SU.LaneMask = OverlapMask;
511 if (NonOverlapMask.
any())
527 assert(!
MI->isDebugOrPseudoInstr());
542 if ((PrevDefLaneMask & LaneMask).
none())
579 if (
MI.isDebugOrPseudoInstr())
622 unsigned NumNodes = 0;
625 unsigned TrueMemOrderLatency;
646 assert(NumNodes >= Itr->second.size());
647 NumNodes -= Itr->second.size();
659 unsigned inline size()
const {
return NumNodes; }
664 for (
auto &
I : *
this)
665 NumNodes +=
I.second.size();
669 return TrueMemOrderLatency;
677 for (
auto &
I : Val2SUsMap)
686 if (Itr != Val2SUsMap.
end())
694 for (
auto &[V, SUs] : map) {
708 SUList &sus = CurrItr->second;
709 SUList::iterator SUItr = sus.begin(), SUEE = sus.end();
710 for (; SUItr != SUEE; ++SUItr) {
723 if (SUItr != sus.begin())
724 sus.erase(sus.begin(), SUItr);
728 map.
remove_if([&](std::pair<ValueType, SUList> &mapEntry) {
729 return (mapEntry.second.empty()); });
739 bool TrackLaneMasks) {
791 "Only BuildGraph should update Defs/Uses");
815 if (
MI.isDebugValue() ||
MI.isDebugPHI()) {
820 if (
MI.isDebugLabel() ||
MI.isDebugRef() ||
MI.isPseudoProbe())
824 assert(SU &&
"No SUnit mapped to this MI");
833 if (PDiffs !=
nullptr)
839 RPTracker->
recede(RegOpers);
844 "Cannot schedule terminators or labels!");
851 bool HasVRegDef =
false;
852 for (
unsigned j = 0, n =
MI.getNumOperands(); j != n; ++j) {
857 if (Reg.isPhysical()) {
859 }
else if (Reg.isVirtual()) {
865 for (
unsigned j = 0, n =
MI.getNumOperands(); j != n; ++j) {
874 if (Reg.isPhysical()) {
876 }
else if (Reg.isVirtual() && MO.
readsReg()) {
906 LLVM_DEBUG(
dbgs() <<
"Global memory object and new barrier chain: SU("
921 if (
MI.mayRaiseFPException()) {
935 if (!
MI.mayStore() &&
936 !(
MI.mayLoad() && !
MI.isDereferenceableInvariantLoad()))
965 bool ThisMayAlias = UnderlObj.mayAlias();
975 bool ThisMayAlias = UnderlObj.mayAlias();
978 (ThisMayAlias ? Stores : NonAliasStores).insert(SU, V);
995 bool ThisMayAlias = UnderlObj.mayAlias();
1002 (ThisMayAlias ? Loads : NonAliasLoads).insert(SU, V);
1015 LLVM_DEBUG(
dbgs() <<
"Reducing NonAliasStores and NonAliasLoads maps.\n");
1032 PSV->printCustom(
OS);
1037 for (
const auto &[ValType, SUs] : *
this) {
1038 if (isa<const Value *>(ValType)) {
1039 const Value *V = cast<const Value *>(ValType);
1040 if (isa<UndefValue>(V))
1041 dbgs() <<
"Unknown";
1043 V->printAsOperand(
dbgs());
1044 }
else if (isa<const PseudoSourceValue *>(ValType))
1045 dbgs() << cast<const PseudoSourceValue *>(ValType);
1057 dbgs() <<
"Loading SUnits:\n";
loads.dump());
1060 std::vector<unsigned> NodeNums;
1062 for (
const auto &[V, SUs] :
stores) {
1064 for (
const auto *SU : SUs)
1065 NodeNums.push_back(SU->NodeNum);
1067 for (
const auto &[V, SUs] :
loads) {
1069 for (
const auto *SU : SUs)
1070 NodeNums.push_back(SU->NodeNum);
1078 SUnit *newBarrierChain = &
SUnits[*(NodeNums.end() -
N)];
1101 dbgs() <<
"Loading SUnits:\n";
loads.dump());
1107 if (!MO.isReg() || !MO.readsReg())
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';
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)
hexagon widen Hexagon Store false hexagon widen loads
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 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(MCRegister Reg) const
Return true if this instruction implicitly uses the specified physical register.
bool hasImplicitDefOfPhysReg(MCRegister 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.
typename VectorType::iterator iterator
ValueT & operator[](const KeyT &Key)
iterator find(const KeyT &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).
const TargetInstrInfo * TII
Target instruction information.
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.
TargetInstrInfo - Interface to description of machine instruction set.
virtual bool isGlobalMemoryObject(const MachineInstr *MI) const
Returns true if MI is an instruction we are unable to reason about (like a call or something with unm...
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.
int getNumOccurrences() const
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.
A MapVector that performs no allocations if smaller than a certain size.
Mapping from virtual register to SUnit including an operand index.
An individual mapping from virtual register number to SUnit.