Go to the documentation of this file.
39 #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."));
96 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
98 for (
const SUnit *su : L) {
99 dbgs() <<
"SU(" << su->NodeNum <<
")";
109 bool RemoveKillFlags)
110 :
ScheduleDAG(mf), MLI(mli), MFI(mf.getFrameInfo()),
111 RemoveKillFlags(RemoveKillFlags),
113 Type::getVoidTy(mf.
getFunction().getContext()))), Topo(SUnits, &ExitSU) {
128 auto allMMOsOkay = [&]() {
131 if (MMO->isVolatile() || MMO->isAtomic())
146 if (PSV->isAliased(&MFI))
149 bool MayAlias = PSV->mayAlias(&MFI);
150 Objects.push_back(UnderlyingObjectsVector::value_type(PSV, MayAlias));
151 }
else if (
const Value *V = MMO->getValue()) {
156 for (
Value *V : Objs) {
158 Objects.push_back(UnderlyingObjectsVector::value_type(V,
true));
166 if (!allMMOsOkay()) {
186 unsigned regioninstrs) {
187 assert(
bb ==
BB &&
"startBlock should set BB");
206 if (!MO.isReg() || MO.isDef())
continue;
219 for (
const auto &LI : Succ->liveins()) {
239 bool ImplicitPseudoDef = (OperIdx >= DefMIDesc->
getNumOperands() &&
250 int UseOp =
I->OpIdx;
264 bool ImplicitPseudoUse =
267 if (!ImplicitPseudoDef && !ImplicitPseudoUse) {
273 ST.adjustSchedDependency(SU, OperIdx, UseSU, UseOp, Dep);
313 ST.adjustSchedDependency(SU, OperIdx, DefSU,
I->OpIdx, Dep);
346 for (
bool isBegin =
I ==
B; !isBegin; ) {
347 isBegin = (--
I) ==
B;
407 if (OtherMO.isReg() && OtherMO.isDef() && OtherMO.getReg() ==
Reg)
428 if ((LaneMask & KillLaneMask).none()) {
433 if ((LaneMask & DefLaneMask).
any()) {
439 ST.adjustSchedDependency(SU, OperIdx, UseSU,
I->OperandIndex, Dep);
443 LaneMask &= ~KillLaneMask;
445 if (LaneMask.
any()) {
446 I->LaneMask = LaneMask;
468 if ((V2SU.LaneMask & LaneMask).none())
471 SUnit *DefSU = V2SU.SU;
487 LaneBitmask OverlapMask = V2SU.LaneMask & LaneMask;
488 LaneBitmask NonOverlapMask = V2SU.LaneMask & ~LaneMask;
490 V2SU.LaneMask = OverlapMask;
491 if (NonOverlapMask.
any())
507 assert(!
MI->isDebugOrPseudoInstr());
522 if ((PrevDefLaneMask & LaneMask).none())
534 return MI->isCall() ||
MI->hasUnmodeledSideEffects() ||
535 (
MI->hasOrderedMemoryRef() && !
MI->isDereferenceableInvariantLoad(
AA));
565 if (
MI.isDebugOrPseudoInstr())
607 unsigned NumNodes = 0;
610 unsigned TrueMemOrderLatency;
631 assert(NumNodes >= Itr->second.size());
632 NumNodes -= Itr->second.size();
644 unsigned inline size()
const {
return NumNodes; }
649 for (
auto &
I : *
this)
650 NumNodes +=
I.second.size();
654 return TrueMemOrderLatency;
662 for (
auto &
I : Val2SUsMap)
664 Val2SUsMap.getTrueMemOrderLatency());
671 if (Itr != Val2SUsMap.
end())
679 for (
auto &
I : map) {
693 SUList &sus = CurrItr->second;
694 SUList::iterator SUItr = sus.begin(), SUEE = sus.end();
695 for (; SUItr != SUEE; ++SUItr) {
708 if (SUItr != sus.begin())
709 sus.erase(sus.begin(), SUItr);
713 map.
remove_if([&](std::pair<ValueType, SUList> &mapEntry) {
714 return (mapEntry.second.empty()); });
724 bool TrackLaneMasks) {
776 "Only BuildGraph should update Defs/Uses");
800 if (
MI.isDebugValue() ||
MI.isDebugPHI()) {
805 if (
MI.isDebugLabel() ||
MI.isDebugRef() ||
MI.isPseudoProbe())
809 assert(SU &&
"No SUnit mapped to this MI");
818 if (PDiffs !=
nullptr)
824 RPTracker->
recede(RegOpers);
829 "Cannot schedule terminators or labels!");
836 bool HasVRegDef =
false;
837 for (
unsigned j = 0,
n =
MI.getNumOperands();
j !=
n; ++
j) {
850 for (
unsigned j = 0,
n =
MI.getNumOperands();
j !=
n; ++
j) {
890 LLVM_DEBUG(
dbgs() <<
"Global memory object and new barrier chain: SU("
905 if (
MI.mayRaiseFPException()) {
919 if (!
MI.mayStore() &&
920 !(
MI.mayLoad() && !
MI.isDereferenceableInvariantLoad(
AA)))
949 bool ThisMayAlias = UnderlObj.mayAlias();
959 bool ThisMayAlias = UnderlObj.mayAlias();
962 (ThisMayAlias ? Stores : NonAliasStores).insert(SU, V);
979 bool ThisMayAlias = UnderlObj.mayAlias();
986 (ThisMayAlias ? Loads : NonAliasLoads).insert(SU, V);
1000 dbgs() <<
"Reducing NonAliasStores and NonAliasLoads maps.\n";);
1017 PSV->printCustom(OS);
1022 for (
auto &Itr : *
this) {
1023 if (Itr.first.is<
const Value*>()) {
1024 const Value *V = Itr.first.get<
const Value*>();
1025 if (isa<UndefValue>(V))
1026 dbgs() <<
"Unknown";
1043 dbgs() <<
"Loading SUnits:\n"; loads.
dump());
1046 std::vector<unsigned> NodeNums;
1047 NodeNums.reserve(
stores.size() + loads.
size());
1049 for (
auto *SU :
I.second)
1050 NodeNums.push_back(SU->NodeNum);
1051 for (
auto &
I : loads)
1052 for (
auto *SU :
I.second)
1053 NodeNums.push_back(SU->NodeNum);
1060 SUnit *newBarrierChain = &SUnits[*(NodeNums.end() -
N)];
1066 if (newBarrierChain->
NodeNum < BarrierChain->NodeNum) {
1068 BarrierChain = newBarrierChain;
1070 << BarrierChain->NodeNum <<
").\n";);
1074 << BarrierChain->NodeNum <<
").\n";);
1077 BarrierChain = newBarrierChain;
1079 insertBarrierChain(
stores);
1080 insertBarrierChain(loads);
1083 dbgs() <<
"Loading SUnits:\n"; loads.dump());
1089 if (!MO.isReg() || !MO.readsReg())
1097 MO.setIsKill(IsKill);
1106 LiveRegs.init(*
TRI);
1107 LiveRegs.addLiveOuts(
MBB);
1111 if (
MI.isDebugOrPseudoInstr())
1125 LiveRegs.removeReg(
Reg);
1127 LiveRegs.removeRegsInMask(MO);
1132 if (!
MI.isBundled()) {
1143 while (
I->isBundledWithSucc())
1146 if (!
I->isDebugOrPseudoInstr())
1149 }
while (
I != Bundle);
1154 void ScheduleDAGInstrs::dumpNode(
const SUnit &SU)
const {
1155 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1163 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1164 if (EntrySU.getInstr() !=
nullptr)
1165 dumpNodeAll(EntrySU);
1166 for (
const SUnit &SU : SUnits)
1168 if (ExitSU.getInstr() !=
nullptr)
1169 dumpNodeAll(ExitSU);
1173 std::string ScheduleDAGInstrs::getGraphNodeLabel(
const SUnit *SU)
const {
1178 else if (SU == &ExitSU)
1187 std::string ScheduleDAGInstrs::getDAGName()
const {
1188 return "dag." +
BB->getFullName();
1191 bool ScheduleDAGInstrs::canAddEdge(
SUnit *SuccSU,
SUnit *PredSU) {
1192 return SuccSU == &ExitSU || !Topo.IsReachable(PredSU, SuccSU);
1196 if (SuccSU != &ExitSU) {
1199 if (Topo.IsReachable(PredDep.
getSUnit(), SuccSU))
1201 Topo.AddPredQueued(SuccSU, PredDep.
getSUnit());
1221 std::vector<std::pair<const SUnit *, const SUnit*>> ConnectionPairs;
1225 unsigned ParentNodeID;
1226 unsigned SubInstrCount = 0;
1229 RootData(
unsigned id): NodeID(
id),
1230 ParentNodeID(SchedDFSResult::InvalidSubtreeID) {}
1232 unsigned getSparseSetIndex()
const {
return NodeID; }
1247 return R.DFSNodeData[SU->
NodeNum].SubtreeID
1248 != SchedDFSResult::InvalidSubtreeID;
1254 R.DFSNodeData[SU->
NodeNum].InstrCount =
1278 if ((
InstrCount -
R.DFSNodeData[PredNum].InstrCount) <
R.SubtreeLimit)
1279 joinPredSubtree(PredDep, SU,
false);
1282 if (
R.DFSNodeData[PredNum].SubtreeID == PredNum) {
1285 if (RootSet[PredNum].ParentNodeID == SchedDFSResult::InvalidSubtreeID)
1286 RootSet[PredNum].ParentNodeID = SU->
NodeNum;
1288 else if (RootSet.
count(PredNum)) {
1293 RData.SubInstrCount += RootSet[PredNum].SubInstrCount;
1294 RootSet.
erase(PredNum);
1304 R.DFSNodeData[Succ->
NodeNum].InstrCount
1306 joinPredSubtree(PredDep, Succ);
1311 ConnectionPairs.push_back(std::make_pair(PredDep.
getSUnit(), Succ));
1320 &&
"number of roots should match trees");
1321 for (
const RootData &Root : RootSet) {
1322 unsigned TreeID = SubtreeClasses[Root.NodeID];
1323 if (Root.ParentNodeID != SchedDFSResult::InvalidSubtreeID)
1324 R.DFSTreeData[TreeID].ParentTreeID = SubtreeClasses[Root.ParentNodeID];
1325 R.DFSTreeData[TreeID].SubInstrCount = Root.SubInstrCount;
1334 for (
unsigned Idx = 0, End =
R.DFSNodeData.size(); Idx != End; ++Idx) {
1335 R.DFSNodeData[Idx].SubtreeID = SubtreeClasses[Idx];
1337 <<
R.DFSNodeData[Idx].SubtreeID <<
'\n');
1339 for (
const std::pair<const SUnit*, const SUnit*> &
P : ConnectionPairs) {
1340 unsigned PredTree = SubtreeClasses[
P.first->NodeNum];
1341 unsigned SuccTree = SubtreeClasses[
P.second->NodeNum];
1342 if (PredTree == SuccTree)
1344 unsigned Depth =
P.first->getDepth();
1345 addConnection(PredTree, SuccTree,
Depth);
1346 addConnection(SuccTree, PredTree,
Depth);
1354 bool CheckLimit =
true) {
1359 unsigned PredNum = PredSU->
NodeNum;
1360 if (
R.DFSNodeData[PredNum].SubtreeID != PredNum)
1365 unsigned NumDataSucs = 0;
1366 for (
const SDep &SuccDep : PredSU->
Succs) {
1368 if (++NumDataSucs >= 4)
1372 if (CheckLimit &&
R.DFSNodeData[PredNum].InstrCount >
R.SubtreeLimit)
1374 R.DFSNodeData[PredNum].SubtreeID = Succ->
NodeNum;
1386 R.SubtreeConnections[FromTree];
1387 for (SchedDFSResult::Connection &
C : Connections) {
1388 if (
C.TreeID == ToTree) {
1393 Connections.push_back(SchedDFSResult::Connection(ToTree,
Depth));
1394 FromTree =
R.DFSTreeData[FromTree].ParentTreeID;
1395 }
while (FromTree != SchedDFSResult::InvalidSubtreeID);
1404 class SchedDAGReverseDFS {
1405 std::vector<std::pair<const SUnit *, SUnit::const_pred_iterator>> DFSStack;
1408 bool isComplete()
const {
return DFSStack.empty(); }
1410 void follow(
const SUnit *SU) {
1411 DFSStack.push_back(std::make_pair(SU, SU->
Preds.begin()));
1413 void advance() { ++DFSStack.back().second; }
1415 const SDep *backtrack() {
1416 DFSStack.pop_back();
1417 return DFSStack.empty() ? nullptr : std::prev(DFSStack.back().second);
1420 const SUnit *getCurr()
const {
return DFSStack.back().first; }
1425 return getCurr()->
Preds.end();
1447 for (
const SUnit &SU : SUnits) {
1451 SchedDAGReverseDFS DFS;
1456 while (DFS.getPred() != DFS.getPredEnd()) {
1457 const SDep &PredDep = *DFS.getPred();
1473 const SUnit *Child = DFS.getCurr();
1474 const SDep *PredDep = DFS.backtrack();
1478 if (DFS.isComplete())
1488 void SchedDFSResult::scheduleTree(
unsigned SubtreeID) {
1489 for (
const Connection &
C : SubtreeConnections[SubtreeID]) {
1490 SubtreeConnectLevels[
C.TreeID] =
1491 std::max(SubtreeConnectLevels[
C.TreeID],
C.Level);
1493 << SubtreeConnectLevels[
C.TreeID] <<
'\n');
1497 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1499 OS <<
InstrCount <<
" / " << Length <<
" = ";
1507 dbgs() << *
this <<
'\n';
void initSUnits()
Creates an SUnit for each real instruction, numbered in top-down topological order.
MachineInstr * FirstDbgValue
typename std::vector< std::pair< ValueType, SUList >> ::iterator iterator
void setUniverse(unsigned U)
Set the universe size which determines the largest key the set can hold.
MachineRegisterInfo & MRI
Virtual/real register map.
ProcResIter getWriteProcResBegin(const MCSchedClassDesc *SC) const
unsigned getOperandNo(const_mop_iterator I) const
Returns the number of the operand iterator I points to.
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
This is an optimization pass for GlobalISel generic memory operations.
void remove_if(Predicate Pred)
Remove the elements that match the predicate.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
void addBarrierChain(Value2SUsMap &map)
Adds barrier chain edges from all SUs in map, and then clear the map.
A parsed version of the target data layout string in and methods for querying it.
void addReg(MCPhysReg Reg)
Adds a physical register and all its sub-registers to the set.
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 void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
LaneBitmask getLaneMask() const
Returns the combination of all lane masks of register in this class.
@ Artificial
Arbitrary strong DAG edge (no real dependence).
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."))
VReg2SUnitOperIdxMultiMap CurrentVRegUses
Tracks the last instructions in this region using each virtual register.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
static Function * getFunction(Constant *C)
void buildSchedGraph(AAResults *AA, RegPressureTracker *RPTracker=nullptr, PressureDiffs *PDiffs=nullptr, LiveIntervals *LIS=nullptr, bool TrackLaneMasks=false)
Builds SUnits for the current region.
MachineBasicBlock::iterator begin() const
Returns an iterator to the top of the current scheduling region.
iterator find(const KeyT &Key)
Find an element by its key.
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
List of registers defined and used by a machine instruction.
A raw_ostream that writes to an std::string.
static bool isGlobalMemoryObject(AAResults *AA, MachineInstr *MI)
Returns true if MI is an instruction we are unable to reason about (like a call or something with unm...
static void addEdge(SmallVectorImpl< LazyCallGraph::Edge > &Edges, DenseMap< LazyCallGraph::Node *, int > &EdgeIndexMap, LazyCallGraph::Node &N, LazyCallGraph::Edge::Kind EK)
void setIsKill(bool Val=true)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
static bool hasDataSucc(const SUnit *SU)
void clear()
Clears map from all contents.
unsigned NumRegionInstrs
Instructions in this region (distance(RegionBegin, RegionEnd)).
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
Internal state used to compute SchedDFSResult.
void clear()
Clears the set.
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
Reg
All possible values of the reg field in the ModR/M byte.
SmallVectorImpl< SDep >::const_iterator const_pred_iterator
@ Anti
A register anti-dependence (aka WAR).
bool isCommutable
Is a commutable instruction.
void addConnection(unsigned FromTree, unsigned ToTree, unsigned Depth)
Called by finalize() to record a connection between trees.
bool isCall
Is a function call.
A set of physical registers with utility functions to track liveness when walking backward/forward th...
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.
static unsigned InstrCount
unsigned computeOutputLatency(const MachineInstr *DefMI, unsigned DefOperIdx, const MachineInstr *DepMI) const
Output dependency latency of a pair of defs of the same register.
Kind
These are the different kinds of scheduling dependencies.
void eraseAll(const KeyT &K)
Erase all elements with the given key.
Track the current register pressure at some position in the instruction stream, and remember the high...
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
The instances of the Type class are immutable: once they are created, they are never changed.
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
const_iterator end(StringRef path)
Get end iterator over path.
A description of a memory reference used in the backend.
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
void insert(SUnit *SU, ValueType V)
Adds SU to the SUList of V.
virtual void startBlock(MachineBasicBlock *BB)
Prepares to perform scheduling in the given block.
SmallVector< SDep, 4 > Succs
All sunit successors.
This class implements a map that also provides access to all stored values in a deterministic order.
unsigned getNumVirtRegs() const
getNumVirtRegs - Return the number of virtual registers created.
SchedDFSImpl(SchedDFSResult &r)
LaneBitmask getLaneMaskForMO(const MachineOperand &MO) const
Returns a mask for which lanes get read/written by the given (register) machine operand.
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Identify one of the processor resource kinds consumed by a particular scheduling class for the specif...
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
static void toggleKills(const MachineRegisterInfo &MRI, LivePhysRegs &LiveRegs, MachineInstr &MI, bool addToLiveRegs)
TargetSchedModel SchedModel
TargetSchedModel provides an interface to the machine model.
void init(unsigned N)
Initialize an array of N PressureDiffs.
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."))
unsigned const TargetRegisterInfo * TRI
unsigned join(unsigned a, unsigned b)
Join the equivalence classes of a and b.
MachineBasicBlock::iterator end() const
Returns an iterator to the bottom of the current scheduling region.
Predicate any(Predicate P0, Predicate P1)
True iff P0 or P1 are true.
void clearList(ValueType V)
Clears the list of SUs mapped to V.
SlotIndex getInstructionIndex(const MachineInstr &Instr) const
Returns the base index of the given instruction.
const MCProcResourceDesc * getProcResource(unsigned PIdx) const
Get a processor resource by ID for convenience.
void reComputeSize()
Counts the number of SUs in this map after a reduction.
bool isArtificial() const
Tests if this is an Order dependence that is marked as "artificial", meaning it isn't necessary for c...
void init(const TargetSubtargetInfo *TSInfo)
Initialize the machine model for instruction scheduling.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
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 MarkDirty()
Mark the ordering as temporarily broken, after a new node has been added.
size_type size() const
size - Returns the number of elements in the set.
std::pair< iterator, iterator > RangePair
bool isBoundaryNode() const
Boundary nodes are placeholders for the boundary of the scheduling region.
< i1 > br i1 label label bb bb
ScheduleDAGInstrs(MachineFunction &mf, const MachineLoopInfo *mli, bool RemoveKillFlags=false)
void addChainDependencies(SUnit *SU, SUList &SUs, unsigned Latency)
Adds dependencies as needed from all SUs in list to SU.
bool isCall(QueryType Type=AnyInBundle) const
void addVRegDefDeps(SUnit *SU, unsigned OperIdx)
Adds register output and data dependencies from this SUnit to instructions that occur later in the sa...
@ SC
CHAIN = SC CHAIN, Imm128 - System call.
bool isUnbuffered
Uses an unbuffered resource.
LaneBitmask getSubRegIndexLaneMask(unsigned SubIdx) const
Return a bitmask representing the parts of a register that are covered by SubIdx.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
void addSchedBarrierDeps()
Adds dependencies from instructions in the current list of instructions being scheduled to scheduling...
UndefValue * UnknownValue
For an unanalyzable memory access, this Value is used in maps.
Record a physical register access.
unsigned short Latency
Node latency.
(vector float) vec_cmpeq(*A, *B) C
const MachineOperand & getOperand(unsigned i) const
bool CanHandleTerminators
The standard DAG builder does not normally include terminators as DAG nodes because it does not creat...
virtual void exitRegion()
Called when the scheduler has finished scheduling the current region.
Clang compiles this i1 i64 store i64 i64 store i64 i64 store i64 i64 store i64 align Which gets codegen d xmm0 movaps rbp movaps rbp movaps rbp movaps rbp rbp rbp rbp rbp It would be better to have movq s of instead of the movaps s LLVM produces ret int
SUnit * BarrierChain
Remember a generic side-effecting instruction as we proceed.
unsigned NodeNum
Entry # of node in the node vector.
Summarize the scheduling resources required for an instruction of a particular scheduling class.
bool empty() const
Returns true if the set is empty.
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
bool mayAlias(AAResults *AA, const MachineInstr &Other, bool UseTBAA) const
Returns true if this instruction's memory access aliases the memory access of Other.
void addPhysRegDeps(SUnit *SU, unsigned OperIdx)
Adds register dependencies (data, anti, and output) from this SUnit to following instructions in the ...
Represent the ILP of the subDAG rooted at a DAG node.
Describe properties that are true of each instruction in the target description file.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
MachineOperand class - Representation of each machine instruction operand.
void setInstr(MachineInstr *MI)
Assigns the instruction for the SUnit.
This class implements an extremely fast bulk output stream that can only output to a stream.
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
int getNumOccurrences() const
@ Output
A register output-dependence (aka WAW).
@ Data
Regular data dependence (aka true-dependence).
MachineBasicBlock::iterator RegionEnd
The end of the range to be scheduled.
ProcResIter getWriteProcResEnd(const MCSchedClassDesc *SC) const
Special value supplied for machine level alias analysis.
void print(raw_ostream &OS) const
SlotIndex - An opaque wrapper around machine indexes.
An individual mapping from virtual register number to SUnit.
ValueT & operator[](const KeyT &Key)
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...
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
bool hasImplicitDefOfPhysReg(unsigned Reg, const MCRegisterInfo *MRI=nullptr) const
Return true if this instruction implicitly defines the specified physical register.
Value2SUsMap(unsigned lat=0)
iterator end()
Returns an iterator past this container.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void recedeSkipDebugValues()
Recede until we find an instruction which is not a DebugValue.
iterator insert(const ValueT &Val)
Insert a new element at the tail of the subset list.
iterator find(const ValueType &Key)
bool isReg() const
isReg - Tests if this is a MO_Register operand.
Representation of each machine instruction.
static unsigned getReductionSize()
multiplies can be turned into SHL s
void compress()
compress - Compress equivalence classes by numbering them 0 .
bool available(const MachineRegisterInfo &MRI, MCPhysReg Reg) const
Returns true if register Reg and no aliasing register is in the set.
const bool HasDisjunctSubRegs
Whether the class supports two (or more) disjunct subregister indices.
MachineInstr * getInstr() const
Returns the representative MachineInstr for this SUnit.
constexpr bool any() const
'undef' values are things that do not have specified contents.
iterator_base< SparseMultiSet * > iterator
initializer< Ty > init(const Ty &Val)
@ MayAliasMem
Nonvolatile load/Store instructions that may alias.
Reg2SUnitsMap Defs
Defs, Uses - Remember where defs and uses of each register are as we iterate upward through the instr...
void visitPostorderEdge(const SDep &PredDep, const SUnit *Succ)
Called once for each tree edge after calling visitPostOrderNode on the predecessor.
const MachineFrameInfo & MFI
bool joinPredSubtree(const SDep &PredDep, const SUnit *Succ, bool CheckLimit=true)
Joins the predecessor subtree with the successor that is its DFS parent.
void setUniverse(unsigned U)
setUniverse - Set the universe size which determines the largest key the set can hold.
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
bool hasPhysRegUses
Has physreg uses.
void finalize()
Sets each node's subtree ID to the representative ID and record connections between trees.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void visitPostorderNode(const SUnit *SU)
Called once for each node after all predecessors are visited.
void visitPreorder(const SUnit *SU)
Initializes this node's instruction count.
bool TrackLaneMasks
Whether lane masks should get tracked.
bool getUnderlyingObjectsForCodeGen(const Value *V, SmallVectorImpl< Value * > &Objects)
This is a wrapper around getUnderlyingObjects and adds support for basic ptrtoint+arithmetic+inttoptr...
bool isRegMask() const
isRegMask - Tests if this is a MO_RegisterMask operand.
Register getReg() const
getReg - Returns the register number.
bool hasOneDef(Register RegNo) const
Return true if there is exactly one operand defining the specified register.
DbgValueVector DbgValues
Remember instruction that precedes DBG_VALUE.
unsigned computeOperandLatency(const MachineInstr *DefMI, unsigned DefOperIdx, const MachineInstr *UseMI, unsigned UseOperIdx) const
Compute operand latency based on the available machine model.
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"))
void printAsOperand(raw_ostream &O, bool PrintType=true, const Module *M=nullptr) const
Print the name of this Value out to the specified raw_ostream.
RangePair equal_range(const KeyT &K)
The bounds of the range of items sharing Key K.
bool contains(const KeyT &Key) const
Returns true if this set contains an element identified by Key.
const TargetRegisterInfo * TRI
Target processor register info.
Mapping from virtual register to SUnit including an operand index.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
iterator_range< succ_iterator > successors()
MachineFunction & MF
Machine function.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
iterator erase(iterator I)
Erases an existing element identified by a valid iterator.
void setIsUndef(bool Val=true)
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
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.
format_object< Ts... > format(const char *Fmt, const Ts &... Vals)
These are helper functions used to produce formatted output.
MachineBasicBlock::const_iterator getPos() const
Get the MI position corresponding to this register pressure.
const MCSchedClassDesc * getSchedClass(SUnit *SU) const
Resolves and cache a resolved scheduling class for an SUnit.
TargetSubtargetInfo - Generic base class for all target subtargets.
DenseMap< MachineInstr *, SUnit * > MISUnitMap
After calling BuildSchedGraph, each machine instruction in the current scheduling region is mapped to...
unsigned const MachineRegisterInfo * MRI
Wrapper class representing virtual and physical registers.
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.
unsigned getSubReg() const
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 getTrueMemOrderLatency() const
SUnit * newSUnit(MachineInstr *MI)
Creates a new SUnit and return a ptr to it.
bool isConstantPhysReg(MCRegister PhysReg) const
Returns true if PhysReg is unallocatable and constant throughout the function.
bool RemoveKillFlags
True if the DAG builder should remove kill flags (in preparation for rescheduling).
std::vector< SUnit > SUnits
The scheduling units.
static cl::opt< bool > EnableAASchedMI("enable-aa-sched-mi", cl::Hidden, cl::desc("Enable use of AA during MI DAG construction"))
constexpr bool empty(const T &RangeOrContainer)
Test whether RangeOrContainer is empty. Similar to C++17 std::empty.
MachineBasicBlock::iterator RegionBegin
The beginning of the range to be scheduled.
bool isIdentifiedObject(const Value *V)
Return true if this pointer refers to a distinct and identifiable object.
bool readsReg() const
readsReg - Returns true if this operand reads the previous value of its register.
Should compile to something r4 addze r3 instead we get
bool hasImplicitUseOfPhysReg(unsigned Reg) const
Return true if this instruction implicitly uses the specified physical register.
ConstMIBundleOperands - Iterate over all operands in a const bundle of machine instructions.
Iterator for intrusive lists based on ilist_node.
void setLatency(unsigned Lat)
Sets the latency for this edge.
void sort(IteratorTy Start, IteratorTy End)
size_type count(const KeyT &Key) const
count - Returns 1 if this set contains an element identified by Key, 0 otherwise.
Compute the values of each DAG node for various metrics during DFS.
bool deadDefHasNoUse(const MachineOperand &MO)
Returns true if the def register in MO has no uses.
bool addPred(const SDep &D, bool Required=true)
Adds the specified edge as a pred of the current node if not already.
iterator erase(iterator I)
erase - Erases an existing element identified by a valid iterator.
bool hasPhysRegDefs
Has physreg defs that are being used.
bool addPredBarrier(SUnit *SU)
Adds a barrier edge to SU by calling addPred(), with latency 0 generally or latency 1 for a store fol...
Kind getKind() const
Returns an enum value representing the kind of the dependence.
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...
MachineBasicBlock * BB
The block in which to insert instructions.
MCSubRegIterator enumerates all sub-registers of Reg.
ValueType & operator[](const SUList &Key)
To keep NumNodes up to date, insert() is used instead of this operator w/ push_back().
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted.
bool hasReservedResource
Uses a reserved resource.
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...
static cl::opt< bool > UseAA("aarch64-use-aa", cl::init(true), cl::desc("Enable the use of AA during codegen."))
virtual void finishBlock()
Cleans up after scheduling in the given block.
void addPhysRegDataDeps(SUnit *SU, unsigned OperIdx)
MO is an operand of SU's instruction that defines a physical register.
VReg2SUnitMultiMap CurrentVRegDefs
Tracks the last instruction(s) in this region defining each virtual register.
void addVRegUseDeps(SUnit *SU, unsigned OperIdx)
Adds a register data dependency if the instruction that defines the virtual register used at OperIdx ...
const DataLayout & getDataLayout() const
Return the DataLayout attached to the Module associated to this MF.
unsigned getNumClasses() const
getNumClasses - Return the number of equivalence classes after compress() was called.
bool isTransient() const
Return true if this is a transient instruction that is either very likely to be eliminated during reg...
void visitCrossEdge(const SDep &PredDep, const SUnit *Succ)
Adds a connection for cross edges.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
static void dumpSUList(ScheduleDAGInstrs::SUList &L)
bool isVisited(const SUnit *SU) const
Returns true if this node been visited by the DFS traversal.
SmallVector< SDep, 4 > Preds
All sunit predecessors.
Scheduling unit. This is a node in the scheduling DAG.
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
bool hasTailCall() const
Returns true if the function contains a tail call.
void insertBarrierChain(Value2SUsMap &map)
Inserts a barrier chain in a huge region, far below current SU.
The same transformation can work with an even modulo with the addition of a and shrink the compare RHS by the same amount Unless the target supports that transformation probably isn t worthwhile The transformation can also easily be made to work with non zero equality for n
bool registerDefIsDead(Register Reg, const TargetRegisterInfo *TRI=nullptr) const
Returns true if the register is dead in this machine instruction.
std::string & str()
Returns the string's reference.
bool isBarrier(QueryType Type=AnyInBundle) const
Returns true if the specified instruction stops control flow from executing the instruction immediate...
void reduceHugeMemNodeMaps(Value2SUsMap &stores, Value2SUsMap &loads, unsigned N)
Reduces maps in FIFO order, by N SUs.
void clearDAG()
Clears the DAG state (between regions).
unsigned getNumOperands() const
Return the number of declared MachineOperands for this MachineInstruction.
iterator_range< mop_iterator > operands()
LLVM Value Representation.
void recede(SmallVectorImpl< RegisterMaskPair > *LiveUses=nullptr)
Recede across the previous instruction.
SUnit ExitSU
Special node for the region exit.
static constexpr LaneBitmask getAll()
bool hasInstrSchedModel() const
Return true if this machine model includes an instruction-level scheduling model.
MCRegAliasIterator enumerates all registers aliasing Reg.
A Use represents the edge between a Value definition and its users.