66 #define DEBUG_TYPE "machine-scheduler" 70 cl::desc(
"Enable use of AA during MI DAG construction"));
83 "prior to scheduling, at which point a trade-off " 84 "is made to avoid excessive compile time."));
88 cl::desc(
"A huge scheduling region will have maps reduced by this many " 89 "nodes at a time. Defaults to HugeRegion / 2."));
100 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 102 for (
const SUnit *su : L) {
103 dbgs() <<
"SU(" << su->NodeNum <<
")";
113 bool RemoveKillFlags)
114 :
ScheduleDAG(mf), MLI(mli), MFI(mf.getFrameInfo()),
115 RemoveKillFlags(RemoveKillFlags),
117 Type::getVoidTy(mf.getFunction().getContext()))) {
132 auto allMMOsOkay = [&]() {
134 if (MMO->isVolatile())
149 if (PSV->isAliased(&MFI))
152 bool MayAlias = PSV->mayAlias(&MFI);
154 }
else if (
const Value *V = MMO->getValue()) {
159 for (
Value *V : Objs) {
169 if (!allMMOsOkay()) {
189 unsigned regioninstrs) {
190 assert(bb ==
BB &&
"startBlock should set BB");
206 if (!MO.isReg() || MO.isDef())
continue;
207 unsigned Reg = MO.getReg();
219 for (
const auto &LI : Succ->liveins()) {
247 int UseOp =
I->OpIdx;
263 ST.adjustSchedDependency(SU, UseSU, Dep);
300 SDep Dep(SU, Kind, *Alias);
335 for (
bool isBegin = I == B; !isBegin; ) {
336 isBegin = (--
I) == B;
392 "Dead defs should have no uses");
400 if ((LaneMask & KillLaneMask).none()) {
405 if ((LaneMask & DefLaneMask).any()) {
415 LaneMask &= ~KillLaneMask;
417 if (LaneMask.
any()) {
418 I->LaneMask = LaneMask;
440 if ((V2SU.LaneMask & LaneMask).none())
443 SUnit *DefSU = V2SU.SU;
459 LaneBitmask OverlapMask = V2SU.LaneMask & LaneMask;
460 LaneBitmask NonOverlapMask = V2SU.LaneMask & ~LaneMask;
462 V2SU.LaneMask = OverlapMask;
463 if (NonOverlapMask.
any())
492 if ((PrevDefLaneMask & LaneMask).none())
535 if (
MI.isDebugValue())
577 unsigned NumNodes = 0;
580 unsigned TrueMemOrderLatency;
601 assert(NumNodes >= Itr->second.size());
602 NumNodes -= Itr->second.size();
614 unsigned inline size()
const {
return NumNodes; }
619 for (
auto &
I : *
this)
620 NumNodes +=
I.second.size();
624 return TrueMemOrderLatency;
632 for (
auto &
I : Val2SUsMap)
634 Val2SUsMap.getTrueMemOrderLatency());
641 if (Itr != Val2SUsMap.
end())
649 for (
auto &
I : map) {
663 SUList &sus = CurrItr->second;
664 SUList::iterator SUItr = sus.begin(), SUEE = sus.end();
665 for (; SUItr != SUEE; ++SUItr) {
678 if (SUItr != sus.begin())
679 sus.erase(sus.begin(), SUItr);
683 map.
remove_if([&](std::pair<ValueType, SUList> &mapEntry) {
684 return (mapEntry.second.empty()); });
738 "Only BuildGraph should update Defs/Uses");
758 DbgValues.push_back(std::make_pair(DbgMI, &MI));
767 assert(SU &&
"No SUnit mapped to this MI");
772 if (TrackLaneMasks) {
776 if (PDiffs !=
nullptr)
781 assert(&*RPTracker->
getPos() == &MI &&
"RPTracker in sync");
782 RPTracker->
recede(RegOpers);
787 "Cannot schedule terminators or labels!");
794 bool HasVRegDef =
false;
848 DEBUG(
dbgs() <<
"Global memory object and new barrier chain: SU(" 891 bool ThisMayAlias = UnderlObj.mayAlias();
901 bool ThisMayAlias = UnderlObj.mayAlias();
904 (ThisMayAlias ? Stores : NonAliasStores).insert(SU, V);
921 bool ThisMayAlias = UnderlObj.mayAlias();
928 (ThisMayAlias ? Loads : NonAliasLoads).insert(SU, V);
937 DEBUG(
dbgs() <<
"Reducing Stores and Loads maps.\n";);
941 DEBUG(
dbgs() <<
"Reducing NonAliasStores and NonAliasLoads maps.\n";);
956 PSV->printCustom(OS);
961 for (
auto &Itr : *
this) {
962 if (Itr.first.is<
const Value*>()) {
963 const Value *V = Itr.first.get<
const Value*>();
964 if (isa<UndefValue>(V))
981 DEBUG(
dbgs() <<
"Before reduction:\nStoring SUnits:\n";
983 dbgs() <<
"Loading SUnits:\n";
987 std::vector<unsigned> NodeNums;
988 NodeNums.reserve(stores.
size() + loads.
size());
989 for (
auto &
I : stores)
990 for (
auto *SU :
I.second)
991 NodeNums.push_back(SU->NodeNum);
992 for (
auto &
I : loads)
993 for (
auto *SU :
I.second)
994 NodeNums.push_back(SU->NodeNum);
1000 assert(N <= NodeNums.size());
1001 SUnit *newBarrierChain = &
SUnits[*(NodeNums.end() -
N)];
1010 DEBUG(
dbgs() <<
"Inserting new barrier chain: SU(" 1014 DEBUG(
dbgs() <<
"Keeping old barrier chain: SU(" 1023 DEBUG(
dbgs() <<
"After reduction:\nStoring SUnits:\n";
1025 dbgs() <<
"Loading SUnits:\n";
1032 if (!MO.isReg() || !MO.readsReg())
1034 unsigned Reg = MO.getReg();
1039 bool IsKill = LiveRegs.
available(MRI, Reg);
1040 MO.setIsKill(IsKill);
1054 if (
MI.isDebugValue())
1075 if (!
MI.isBundled()) {
1079 if (
MI.isBundle()) {
1087 while (I->isBundledWithSucc())
1090 if (!I->isDebugValue())
1093 }
while(I != First);
1100 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 1136 std::vector<std::pair<const SUnit *, const SUnit*>> ConnectionPairs;
1140 unsigned ParentNodeID;
1141 unsigned SubInstrCount = 0;
1144 RootData(
unsigned id): NodeID(
id),
1145 ParentNodeID(SchedDFSResult::InvalidSubtreeID) {}
1147 unsigned getSparseSetIndex()
const {
return NodeID; }
1162 return R.DFSNodeData[SU->
NodeNum].SubtreeID
1163 != SchedDFSResult::InvalidSubtreeID;
1169 R.DFSNodeData[SU->
NodeNum].InstrCount =
1193 if ((InstrCount - R.DFSNodeData[PredNum].InstrCount) < R.SubtreeLimit)
1194 joinPredSubtree(PredDep, SU,
false);
1197 if (R.DFSNodeData[PredNum].SubtreeID == PredNum) {
1200 if (RootSet[PredNum].ParentNodeID == SchedDFSResult::InvalidSubtreeID)
1201 RootSet[PredNum].ParentNodeID = SU->
NodeNum;
1203 else if (RootSet.
count(PredNum)) {
1208 RData.SubInstrCount += RootSet[PredNum].SubInstrCount;
1209 RootSet.
erase(PredNum);
1219 R.DFSNodeData[Succ->
NodeNum].InstrCount
1221 joinPredSubtree(PredDep, Succ);
1226 ConnectionPairs.push_back(std::make_pair(PredDep.
getSUnit(), Succ));
1235 &&
"number of roots should match trees");
1236 for (
const RootData &Root : RootSet) {
1237 unsigned TreeID = SubtreeClasses[Root.NodeID];
1238 if (Root.ParentNodeID != SchedDFSResult::InvalidSubtreeID)
1239 R.DFSTreeData[TreeID].ParentTreeID = SubtreeClasses[Root.ParentNodeID];
1240 R.DFSTreeData[TreeID].SubInstrCount = Root.SubInstrCount;
1246 R.SubtreeConnections.resize(SubtreeClasses.
getNumClasses());
1247 R.SubtreeConnectLevels.resize(SubtreeClasses.
getNumClasses());
1249 for (
unsigned Idx = 0,
End = R.DFSNodeData.size(); Idx !=
End; ++Idx) {
1250 R.DFSNodeData[Idx].SubtreeID = SubtreeClasses[Idx];
1251 DEBUG(
dbgs() <<
" SU(" << Idx <<
") in tree " 1252 << R.DFSNodeData[Idx].SubtreeID <<
'\n');
1254 for (
const std::pair<const SUnit*, const SUnit*> &
P : ConnectionPairs) {
1255 unsigned PredTree = SubtreeClasses[
P.first->NodeNum];
1256 unsigned SuccTree = SubtreeClasses[
P.second->NodeNum];
1257 if (PredTree == SuccTree)
1259 unsigned Depth =
P.first->getDepth();
1260 addConnection(PredTree, SuccTree, Depth);
1261 addConnection(SuccTree, PredTree, Depth);
1269 bool CheckLimit =
true) {
1274 unsigned PredNum = PredSU->
NodeNum;
1275 if (R.DFSNodeData[PredNum].SubtreeID != PredNum)
1280 unsigned NumDataSucs = 0;
1281 for (
const SDep &SuccDep : PredSU->Succs) {
1283 if (++NumDataSucs >= 4)
1287 if (CheckLimit && R.DFSNodeData[PredNum].InstrCount > R.SubtreeLimit)
1289 R.DFSNodeData[PredNum].SubtreeID = Succ->
NodeNum;
1301 R.SubtreeConnections[FromTree];
1302 for (SchedDFSResult::Connection &
C : Connections) {
1303 if (
C.TreeID == ToTree) {
1308 Connections.push_back(SchedDFSResult::Connection(ToTree, Depth));
1309 FromTree = R.DFSTreeData[FromTree].ParentTreeID;
1310 }
while (FromTree != SchedDFSResult::InvalidSubtreeID);
1319 class SchedDAGReverseDFS {
1320 std::vector<std::pair<const SUnit *, SUnit::const_pred_iterator>> DFSStack;
1323 bool isComplete()
const {
return DFSStack.
empty(); }
1325 void follow(
const SUnit *SU) {
1326 DFSStack.push_back(std::make_pair(SU, SU->
Preds.begin()));
1328 void advance() { ++DFSStack.back().second; }
1330 const SDep *backtrack() {
1331 DFSStack.pop_back();
1332 return DFSStack.empty() ? nullptr : std::prev(DFSStack.back().second);
1335 const SUnit *getCurr()
const {
return DFSStack.back().first; }
1340 return getCurr()->
Preds.end();
1362 for (
const SUnit &SU : SUnits) {
1366 SchedDAGReverseDFS
DFS;
1371 while (DFS.getPred() != DFS.getPredEnd()) {
1372 const SDep &PredDep = *DFS.getPred();
1388 const SUnit *Child = DFS.getCurr();
1389 const SDep *PredDep = DFS.backtrack();
1393 if (DFS.isComplete())
1404 for (
const Connection &
C : SubtreeConnections[SubtreeID]) {
1405 SubtreeConnectLevels[
C.TreeID] =
1406 std::max(SubtreeConnectLevels[
C.TreeID],
C.Level);
1408 <<
" @" << SubtreeConnectLevels[
C.TreeID] <<
'\n');
1412 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 1414 OS <<
InstrCount <<
" / " << Length <<
" = ";
1422 dbgs() << *
this <<
'\n';
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...
iterator end()
Returns an iterator past this container.
bool isRegMask() const
isRegMask - Tests if this is a MO_RegisterMask operand.
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 push_back(const T &Elt)
A parsed version of the target data layout string in and methods for querying it. ...
virtual void finishBlock()
Cleans up after scheduling in the given block.
unsigned computeOutputLatency(const MachineInstr *DefMI, unsigned DefIdx, const MachineInstr *DepMI) const
Output dependency latency of a pair of defs of the same register.
bool joinPredSubtree(const SDep &PredDep, const SUnit *Succ, bool CheckLimit=true)
Joins the predecessor subtree with the successor that is its DFS parent.
A common definition of LaneBitmask for use in TableGen and CodeGen.
ValueType & operator[](const SUList &Key)
To keep NumNodes up to date, insert() is used instead of this operator w/ push_back().
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
bool isCall(QueryType Type=AnyInBundle) const
iterator_base< SparseMultiSet *> iterator
ProcResIter getWriteProcResBegin(const MCSchedClassDesc *SC) const
const TargetRegisterClass * getRegClass(unsigned Reg) const
Return the register class of the specified virtual register.
iterator insert(const ValueT &Val)
Insert a new element at the tail of the subset list.
void insert(SUnit *SU, ValueType V)
Adds SU to the SUList of V.
bool available(const MachineRegisterInfo &MRI, unsigned Reg) const
Returns true if register Reg and no aliasing register is in the set.
Compute iterated dominance frontiers using a linear time algorithm.
void init(unsigned N)
Initialize an array of N PressureDiffs.
Record a physical register access.
bool contains(const KeyT &Key) const
Returns true if this set contains an element identified by Key.
void addVRegDefDeps(SUnit *SU, unsigned OperIdx)
Adds register output and data dependencies from this SUnit to instructions that occur later in the sa...
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."))
LivePhysRegs LiveRegs
Set of live physical registers for updating kill flags.
bool TrackLaneMasks
Whether lane masks should get tracked.
void dumpNode(const SUnit *SU) const override
const MCSchedClassDesc * getSchedClass(SUnit *SU) const
Resolves and cache a resolved scheduling class for an SUnit.
void removeRegsInMask(const MachineOperand &MO, SmallVectorImpl< std::pair< unsigned, const MachineOperand *>> *Clobbers=nullptr)
Removes physical registers clobbered by the regmask operand MO.
This provides a very simple, boring adaptor for a begin and end iterator into a range type...
unsigned getReg() const
getReg - Returns the register number.
unsigned getOperandNo(const_mop_iterator I) const
Returns the number of the operand iterator I points to.
void setIsUndef(bool Val=true)
Represent the ILP of the subDAG rooted at a DAG node.
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
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."))
TargetSchedModel SchedModel
TargetSchedModel provides an interface to the machine model.
void fixupKills(MachineBasicBlock &MBB)
Fixes register kill flags that scheduling has made invalid.
unsigned getSubReg() const
format_object< Ts... > format(const char *Fmt, const Ts &... Vals)
These are helper functions used to produce formatted output.
void compress()
compress - Compress equivalence classes by numbering them 0 .
bool CanHandleTerminators
The standard DAG builder does not normally include terminators as DAG nodes because it does not creat...
unsigned computeOperandLatency(const MachineInstr *DefMI, unsigned DefOperIdx, const MachineInstr *UseMI, unsigned UseOperIdx) const
Compute operand latency based on the available machine model.
ProcResIter getWriteProcResEnd(const MCSchedClassDesc *SC) const
bool isTransient() const
Return true if this is a transient instruction that is either very likely to be eliminated during reg...
This class implements a map that also provides access to all stored values in a deterministic order...
bool hasOneDef(unsigned RegNo) const
Return true if there is exactly one operand defining the specified register.
static cl::opt< bool > EnableAASchedMI("enable-aa-sched-mi", cl::Hidden, cl::ZeroOrMore, cl::init(false), cl::desc("Enable use of AA during MI DAG construction"))
static unsigned InstrCount
iterator_range< mmo_iterator > memoperands()
Kind
These are the different kinds of scheduling dependencies.
iterator_range< mop_iterator > operands()
unsigned NumRegionInstrs
Instructions in this region (distance(RegionBegin, RegionEnd)).
void addPhysRegDataDeps(SUnit *SU, unsigned OperIdx)
MO is an operand of SU's instruction that defines a physical register.
RangePair equal_range(const KeyT &K)
The bounds of the range of items sharing Key K.
SmallVector< SDep, 4 > Preds
All sunit predecessors.
virtual void startBlock(MachineBasicBlock *BB)
Prepares to perform scheduling in the given block.
virtual void adjustSchedDependency(SUnit *def, SUnit *use, SDep &dep) const
void clearList(ValueType V)
Clears the list of SUs mapped to V.
iterator_range< succ_iterator > successors()
A register anti-dependence (aka WAR).
void insertBarrierChain(Value2SUsMap &map)
Inserts a barrier chain in a huge region, far below current SU.
void recede(SmallVectorImpl< RegisterMaskPair > *LiveUses=nullptr)
Recede across the previous instruction.
MachineFunction & MF
Machine function.
void buildSchedGraph(AliasAnalysis *AA, RegPressureTracker *RPTracker=nullptr, PressureDiffs *PDiffs=nullptr, LiveIntervals *LIS=nullptr, bool TrackLaneMasks=false)
Builds SUnits for the current region.
A description of a memory reference used in the backend.
unsigned NumSuccs
of SDep::Data sucss.
MachineBasicBlock::iterator RegionEnd
The end of the range to be scheduled.
DenseMap< MachineInstr *, SUnit * > MISUnitMap
After calling BuildSchedGraph, each machine instruction in the current scheduling region is mapped to...
void addSchedBarrierDeps()
Adds dependencies from instructions in the current list of instructions being scheduled to scheduling...
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
'undef' values are things that do not have specified contents.
An individual mapping from virtual register number to SUnit.
unsigned getNumOperands() const
Access to explicit operands of the instruction.
void setInstr(MachineInstr *MI)
Assigns the instruction for the SUnit.
A Use represents the edge between a Value definition and its users.
SmallVectorImpl< SDep >::const_iterator const_pred_iterator
size_type count(const KeyT &Key) const
count - Returns 1 if this set contains an element identified by Key, 0 otherwise. ...
static bool hasDataSucc(const SUnit *SU)
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Regular data dependence (aka true-dependence).
bool hasPhysRegUses
Has physreg uses.
static constexpr LaneBitmask getAll()
Reg
All possible values of the reg field in the ModR/M byte.
bool isTerminator(QueryType Type=AnyInBundle) const
Returns true if this instruction part of the terminator for a basic block.
ValueT & operator[](const KeyT &Key)
bool hasPhysRegDefs
Has physreg defs that are being used.
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted...
DbgValueVector DbgValues
Remember instruction that precedes DBG_VALUE.
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
bool hasInstrSchedModel() const
Return true if this machine model includes an instruction-level scheduling model. ...
MachineBasicBlock::const_iterator getPos() const
Get the MI position corresponding to this register pressure.
bool isIdentifiedObject(const Value *V)
Return true if this pointer refers to a distinct and identifiable object.
Compute the values of each DAG node for various metrics during DFS.
Value2SUsMap(unsigned lat=0)
A register output-dependence (aka WAW).
bool readsReg() const
readsReg - Returns true if this operand reads the previous value of its register. ...
bool hasReservedResource
Uses a reserved resource.
MachineBasicBlock::iterator RegionBegin
The beginning of the range to be scheduled.
void addVRegUseDeps(SUnit *SU, unsigned OperIdx)
Adds a register data dependency if the instruction that defines the virtual register used at OperIdx ...
void print(raw_ostream &OS) const
size_type size() const
size - Returns the number of elements in the set.
SUnit * BarrierChain
Remember a generic side-effecting instruction as we proceed.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
MachineBasicBlock::iterator begin() const
Returns an iterator to the top of the current scheduling region.
static void toggleKills(const MachineRegisterInfo &MRI, LivePhysRegs &LiveRegs, MachineInstr &MI, bool addToLiveRegs)
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...
List of registers defined and used by a machine instruction.
LaneBitmask getLaneMask() const
Returns the combination of all lane masks of register in this class.
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 visitPostorderNode(const SUnit *SU)
Called once for each node after all predecessors are visited.
iterator find(const KeyT &Key)
unsigned getTrueMemOrderLatency() const
void visitPreorder(const SUnit *SU)
Initializes this node's instruction count.
bool mayAlias(AliasAnalysis *AA, MachineInstr &Other, bool UseTBAA)
Returns true if this instruction's memory access aliases the memory access of Other.
std::list< SUnit * > SUList
A list of SUnits, used in Value2SUsMap, during DAG construction.
bool isDereferenceableInvariantLoad(AliasAnalysis *AA) const
Return true if this load instruction never traps and points to a memory location whose value doesn't ...
reverse_iterator rbegin()
bool isBoundaryNode() const
Boundary nodes are placeholders for the boundary of the scheduling region.
unsigned getNumSubtrees() const
The number of subtrees detected in this DAG.
const DataLayout & getDataLayout() const
Return the DataLayout attached to the Module associated to this MF.
iterator erase(iterator I)
erase - Erases an existing element identified by a valid iterator.
void recedeSkipDebugValues()
Recede until we find an instruction which is not a DebugValue.
bool isUnbuffered
Uses an unbuffered resource.
bool mayStore(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly modify memory.
void remove_if(Predicate Pred)
Remove the elements that match the predicate.
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
initializer< Ty > init(const Ty &Val)
bool isCall
Is a function call.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
MachineInstr * getInstr() const
Returns the representative MachineInstr for this SUnit.
void clearDAG()
Clears the DAG state (between regions).
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
The instances of the Type class are immutable: once they are created, they are never changed...
static unsigned getReductionSize()
unsigned short Latency
Node latency.
Identify one of the processor resource kinds consumed by a particular scheduling class for the specif...
bool registerDefIsDead(unsigned Reg, const TargetRegisterInfo *TRI=nullptr) const
Returns true if the register is dead in this machine instruction.
bool RemoveKillFlags
True if the DAG builder should remove kill flags (in preparation for rescheduling).
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
void visitCrossEdge(const SDep &PredDep, const SUnit *Succ)
Adds a connection for cross edges.
Internal state used to compute SchedDFSResult.
void addLiveOuts(const MachineBasicBlock &MBB)
Adds all live-out registers of basic block MBB.
This file contains the declarations for the subclasses of Constant, which represent the different fla...
void reComputeSize()
Counts the number of SUs in this map after a reduction.
Summarize the scheduling resources required for an instruction of a particular scheduling class...
unsigned getNumClasses() const
getNumClasses - Return the number of equivalence classes after compress() was called.
void addConnection(unsigned FromTree, unsigned ToTree, unsigned Depth)
Called by finalize() to record a connection between trees.
bool getUnderlyingObjectsForCodeGen(const Value *V, SmallVectorImpl< Value *> &Objects, const DataLayout &DL)
This is a wrapper around GetUnderlyingObjects and adds support for basic ptrtoint+arithmetic+inttoptr...
void init(const TargetRegisterInfo &TRI)
(re-)initializes and clears the set.
void setUniverse(unsigned U)
Set the universe size which determines the largest key the set can hold.
MCRegAliasIterator enumerates all registers aliasing Reg.
static const unsigned End
Track the current register pressure at some position in the instruction stream, and remember the high...
virtual void exitRegion()
Called when the scheduler has finished scheduling the current region.
void setUniverse(unsigned U)
setUniverse - Set the universe size which determines the largest key the set can hold.
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.
const MachineFrameInfo & MFI
unsigned getNumVirtRegs() const
getNumVirtRegs - Return the number of virtual registers created.
void init(const TargetSubtargetInfo *TSInfo)
Initialize the machine model for instruction scheduling.
void clear()
Clears the set.
LaneBitmask getLaneMaskForMO(const MachineOperand &MO) const
Returns a mask for which lanes get read/written by the given (register) machine operand.
bool isVisited(const SUnit *SU) const
Returns true if this node been visited by the DFS traversal.
This file implements the LivePhysRegs utility for tracking liveness of physical registers.
auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
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.
std::string & str()
Flushes the stream contents to the target string and returns the string's reference.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
std::string getDAGName() const override
Returns a label for the region of code covered by the DAG.
bool isConstantPhysReg(unsigned PhysReg) const
Returns true if PhysReg is unallocatable and constant throughout the function.
void setIsKill(bool Val=true)
iterator find(const KeyT &Key)
Find an element by its key.
void sort(IteratorTy Start, IteratorTy End)
const bool HasDisjunctSubRegs
Whether the class supports two (or more) disjunct subregister indices.
The two locations may or may not alias. This is the least precise result.
void addPhysRegDeps(SUnit *SU, unsigned OperIdx)
Adds register dependencies (data, anti, and output) from this SUnit to following instructions in the ...
unsigned join(unsigned a, unsigned b)
Join the equivalence classes of a and b.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
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...
std::string getGraphNodeLabel(const SUnit *SU) const override
Returns a label for a DAG node that points to an instruction.
void reduceHugeMemNodeMaps(Value2SUsMap &stores, Value2SUsMap &loads, unsigned N)
Reduces maps in FIFO order, by N SUs.
bool isCommutable
Is a commutable instruction.
Iterator for intrusive lists based on ilist_node.
ConstMIBundleOperands - Iterate over all operands in a const bundle of machine instructions.
void compute(ArrayRef< SUnit > SUnits)
Compute various metrics for the DAG with given roots.
UndefValue * UnknownValue
For an unanalyzable memory access, this Value is used in maps.
bool isDebugValue() const
MachineOperand class - Representation of each machine instruction operand.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small...
Reg2SUnitsMap Defs
Defs, Uses - Remember where defs and uses of each register are as we iterate upward through the instr...
void eraseAll(const KeyT &K)
Erase all elements with the given key.
CHAIN = SC CHAIN, Imm128 - System call.
bool hasOrderedMemoryRef() const
Return true if this instruction may have an ordered or volatile memory reference, or if the informati...
LaneBitmask getSubRegIndexLaneMask(unsigned SubIdx) const
Return a bitmask representing the parts of a register that are covered by SubIdx. ...
Nonvolatile load/Store instructions that may alias.
typename std::vector< std::pair< ValueType, SUList >> ::iterator iterator
bool addPredBarrier(SUnit *SU)
Adds a barrier edge to SU by calling addPred(), with latency 0 generally or latency 1 for a store fol...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
VReg2SUnitOperIdxMultiMap CurrentVRegUses
Tracks the last instructions in this region using each virtual register.
Special value supplied for machine level alias analysis.
SlotIndex getInstructionIndex(const MachineInstr &Instr) const
Returns the base index of the given instruction.
void visitPostorderEdge(const SDep &PredDep, const SUnit *Succ)
Called once for each tree edge after calling visitPostOrderNode on the predecessor.
void setLatency(unsigned Lat)
Sets the latency for this edge.
**iterator erase(iterator I)
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
TargetSubtargetInfo - Generic base class for all target subtargets.
SUnit EntrySU
Special node for the region entry.
Representation of each machine instruction.
SUnit ExitSU
Special node for the region exit.
void finalize()
Sets each node's subtree ID to the representative ID and record connections between trees...
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
const TargetRegisterInfo * TRI
Target processor register info.
void removeReg(unsigned Reg)
Removes a physical register, all its sub-registers, and all its super-registers from the set...
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"))
A set of physical registers with utility functions to track liveness when walking backward/forward th...
LLVM_NODISCARD bool empty() const
std::pair< iterator, iterator > RangePair
void addChainDependencies(SUnit *SU, SUList &SUs, unsigned Latency)
Adds dependencies as needed from all SUs in list to SU.
constexpr bool any() const
bool empty() const
Returns true if the set is empty.
Mapping from virtual register to SUnit including an operand index.
void addChainDependency(SUnit *SUa, SUnit *SUb, unsigned Latency=0)
Adds a chain edge between SUa and SUb, but only if both AliasAnalysis and Target fail to deny the dep...
Kind getKind() const
Returns an enum value representing the kind of the dependence.
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
bool isReg() const
isReg - Tests if this is a MO_Register operand.
ScheduleDAGInstrs(MachineFunction &mf, const MachineLoopInfo *mli, bool RemoveKillFlags=false)
unsigned NodeNum
Entry # of node in the node vector.
MachineBasicBlock::iterator end() const
Returns an iterator to the bottom of the current scheduling region.
SUnit * newSUnit(MachineInstr *MI)
Creates a new SUnit and return a ptr to it.
void addBarrierChain(Value2SUsMap &map)
Adds barrier chain edges from all SUs in map, and then clear the map.
bool mayLoad(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly read memory.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
const MCProcResourceDesc * getProcResource(unsigned PIdx) const
Get a processor resource by ID for convenience.
bool addPred(const SDep &D, bool Required=true)
Adds the specified edge as a pred of the current node if not already.
A raw_ostream that writes to an std::string.
std::string getFullName() const
Return a formatted string to identify this block and its parent function.
LLVM Value Representation.
void clear()
Clears map from all contents.
void initSUnits()
Creates an SUnit for each real instruction, numbered in top-down topological order.
SmallVector< SDep, 4 > Succs
All sunit successors.
Arbitrary strong DAG edge (no real dependence).
void scheduleTree(unsigned SubtreeID)
Scheduler callback to update SubtreeConnectLevels when a tree is initially scheduled.
This class implements an extremely fast bulk output stream that can only output to a stream...
MachineInstr * FirstDbgValue
static bool isGlobalMemoryObject(AliasAnalysis *AA, MachineInstr *MI)
Returns true if MI is an instruction we are unable to reason about (like a call or something with unm...
bool hasUnmodeledSideEffects() const
Return true if this instruction has side effects that are not modeled by mayLoad / mayStore...
MachineBasicBlock * BB
The block in which to insert instructions.
virtual bool useAA() const
Enable use of alias analysis during code generation (during MI scheduling, DAGCombine, etc.).
bool isBarrier(QueryType Type=AnyInBundle) const
Returns true if the specified instruction stops control flow from executing the instruction immediate...
static void dumpSUList(ScheduleDAGInstrs::SUList &L)
MachineRegisterInfo & MRI
Virtual/real register map.
std::vector< SUnit > SUnits
The scheduling units.
SchedDFSImpl(SchedDFSResult &r)
const MachineOperand & getOperand(unsigned i) const
SlotIndex - An opaque wrapper around machine indexes.
VReg2SUnitMultiMap CurrentVRegDefs
Tracks the last instruction(s) in this region defining each virtual register.
bool hasTailCall() const
Returns true if the function contains a tail call.
Scheduling unit. This is a node in the scheduling DAG.
A discriminated union of two pointer types, with the discriminator in the low bit of the pointer...
void addReg(unsigned Reg)
Adds a physical register and all its sub-registers to the set.