29 #include "llvm/Config/llvm-config.h" 36 #define DEBUG_TYPE "pre-RA-sched" 38 STATISTIC(LoadsClustered,
"Number of loads clustered together");
45 cl::desc(
"Roughly estimate the number of cycles that 'long latency'" 46 "instructions take for targets with no itinerary"));
50 InstrItins(mf.getSubtarget().getInstrItineraryData()) {}
70 const SUnit *Addr =
nullptr;
76 "SUnits std::vector reallocated on the fly!");
113 unsigned &PhysReg,
int &Cost) {
143 if (ExtraOper.getNode())
165 if (GlueDestNode == N)
return false;
189 "expected an unused glue value");
200 void ScheduleDAGSDNodes::ClusterNeighboringLoads(
SDNode *Node) {
211 auto hasTiedInput = [
this](
const SDNode *
N) {
226 bool Cluster =
false;
229 if (hasTiedInput(Base))
234 unsigned UseCount = 0;
236 I !=
E && UseCount < 100; ++
I, ++UseCount) {
238 if (User == Node || !Visited.
insert(User).second)
240 int64_t Offset1, Offset2;
242 Offset1 == Offset2 ||
243 hasTiedInput(User)) {
248 if (O2SMap.
insert(std::make_pair(Offset1, Base)).second)
250 O2SMap.
insert(std::make_pair(Offset2, User));
252 if (Offset2 < Offset1)
267 unsigned NumLoads = 0;
268 int64_t BaseOff = Offsets[0];
269 SDNode *BaseLoad = O2SMap[BaseOff];
271 for (
unsigned i = 1,
e = Offsets.
size(); i !=
e; ++i) {
272 int64_t
Offset = Offsets[i];
287 if (
AddGlue(Lead, InGlue,
true, DAG))
289 for (
unsigned I = 1,
E = Loads.
size();
I !=
E; ++
I) {
290 bool OutGlue =
I <
E - 1;
295 if (
AddGlue(Load, InGlue, OutGlue, DAG)) {
301 else if (!OutGlue && InGlue.
getNode())
308 void ScheduleDAGSDNodes::ClusterNodes() {
318 ClusterNeighboringLoads(Node);
322 void ScheduleDAGSDNodes::BuildSchedUnits() {
326 unsigned NumNodes = 0;
337 SUnits.reserve(NumNodes * 2);
346 while (!Worklist.
empty()) {
383 bool HasGlueUse =
false;
386 if (GlueVal.isOperandOf(*UI)) {
395 if (!HasGlueUse)
break;
422 while (!CallSUnits.
empty()) {
436 void ScheduleDAGSDNodes::AddSchedEdges() {
443 for (
unsigned su = 0,
e =
SUnits.size(); su !=
e; ++su) {
476 assert(OpSU &&
"Node has no SUnit!");
477 if (OpSU == SU)
continue;
483 unsigned PhysReg = 0;
487 assert((PhysReg == 0 || !isChain) &&
488 "Chain dependence via physreg data?");
498 unsigned OpLatency = isChain ? 1 : OpSU->
Latency;
506 if (!isChain && !UnitLatencies) {
541 void ScheduleDAGSDNodes::RegDefIter::InitNodeNumDefs() {
554 if (POpc == TargetOpcode::IMPLICIT_DEF) {
559 if (POpc == TargetOpcode::PATCHPOINT &&
567 unsigned NRegDefs = SchedDAG->TII->get(Node->
getMachineOpcode()).getNumDefs();
577 : SchedDAG(SD), Node(SU->getNode()), DefIdx(0), NodeNumDefs(0) {
585 for (;DefIdx < NodeNumDefs; ++DefIdx) {
643 unsigned OpIdx,
SDep& dep)
const{
663 Latency = (Latency > 1) ? Latency - 1 : 1;
670 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 675 dbgs() <<
"PHYS REG COPY\n";
684 while (!GluedNodes.
empty()) {
686 GluedNodes.
back()->dump(DAG);
694 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 704 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 706 for (
unsigned i = 0,
e =
Sequence.size(); i !=
e; i++) {
710 dbgs() <<
"**** NOOP ****\n";
722 for (
unsigned i = 0,
e =
Sequence.size(); i !=
e; ++i)
726 "The number of nodes scheduled doesn't match the expected number!");
745 unsigned DVOrder = DV->getOrder();
746 if (!Order || DVOrder == Order) {
749 Orders.push_back({DVOrder, DbgMI});
750 BB->
insert(InsertPos, DbgMI);
765 if (!Order || Seen.
count(Order)) {
778 Orders.push_back({Order, NewInsn});
786 void ScheduleDAGSDNodes::
791 if (
I->isCtrl())
continue;
792 if (
I->getSUnit()->CopyDstRC) {
795 assert(VRI != VRBaseMap.
end() &&
"Node emitted out of order - late");
799 EE = SU->
Succs.end(); II != EE; ++II) {
800 if (II->isCtrl())
continue;
807 .addReg(VRI->second);
810 assert(
I->getReg() &&
"Unknown physical register!");
812 bool isNew = VRBaseMap.
insert(std::make_pair(SU, VRBase)).second;
814 assert(isNew &&
"Node emitted out of order - early");
816 .addReg(
I->getReg());
838 [&](
SDNode *Node,
bool IsClone,
bool IsCloned,
849 Emitter.
EmitNode(Node, IsClone, IsCloned, VRBaseMap);
857 if (Before ==
BB->
end()) {
863 MI = &*std::next(Before);
876 for (; PDI != PDE; ++PDI) {
882 (*PDI)->clearIsEmitted();
887 for (
unsigned i = 0,
e =
Sequence.size(); i !=
e; i++) {
899 EmitPhysRegCopy(SU, CopyVRBaseMap, InsertPos);
906 while (!GluedNodes.
empty()) {
914 if (NewInsn && NewInsn->isCall())
927 if (NewInsn && NewInsn->isCall())
943 return LHS->
getOrder() < RHS->getOrder();
949 unsigned LastOrder = 0;
950 for (
unsigned i = 0,
e = Orders.
size(); i !=
e && DI != DE; ++i) {
951 unsigned Order = Orders[i].first;
955 for (; DI != DE; ++DI) {
956 if ((*DI)->getOrder() < LastOrder || (*DI)->getOrder() >= Order)
958 if ((*DI)->isEmitted())
979 for (; DI != DE; ++DI) {
980 if ((*DI)->isEmitted())
982 assert((*DI)->getOrder() >= LastOrder &&
983 "emitting DBG_VALUE out of order");
996 for (
const auto &InstrOrder : Orders) {
997 unsigned Order = InstrOrder.first;
1003 for (; DLI != DLE &&
1004 (*DLI)->getOrder() >= LastOrder && (*DLI)->getOrder() < Order;
SDNode * MorphNodeTo(SDNode *N, unsigned Opc, SDVTList VTs, ArrayRef< SDValue > Ops)
This mutates the specified node to have the specified return type, opcode, and operands.
static cl::opt< int > HighLatencyCycles("sched-high-latency-cycles", cl::Hidden, cl::init(10), cl::desc("Roughly estimate the number of cycles that 'long latency'" "instructions take for targets with no itinerary"))
void dumpNode(const SUnit &SU) const override
EVT getValueType() const
Return the ValueType of the referenced return value.
virtual bool areLoadsFromSameBasePtr(SDNode *Load1, SDNode *Load2, int64_t &Offset1, int64_t &Offset2) const
This is used by the pre-regalloc scheduler to determine if two loads are loading from the same base a...
unsigned getOpcode() const
Return the SelectionDAG opcode value for this node.
bool isCall(QueryType Type=AnyInBundle) const
void setNode(SDNode *N)
Assigns the representative SDNode for this SUnit.
This class represents lattice values for constants.
value_iterator value_end() const
unsigned EnableDebugEntryValues
Emit debug info about parameter's entry values.
bool isCommutable() const
Return true if this may be a 2- or 3-address instruction (of the form "X = op Y, Z, ..."), which produces the same result if Y and Z are exchanged.
MachineInstr & instr_front()
Register createVirtualRegister(const TargetRegisterClass *RegClass, StringRef Name="")
createVirtualRegister - Create and return a new virtual register in the function with the specified r...
SDNode * getNode() const
Returns the representative SDNode for this SUnit.
Sched::Preference getSchedulingPreference() const
Return target scheduling preference.
unsigned getIROrder() const
Return the node ordering.
EVT getValueType(unsigned ResNo) const
Return the type of a specified result.
void push_back(const T &Elt)
bool isTwoAddress
Is a two-address instruction.
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
Describe properties that are true of each instruction in the target description file.
static unsigned CountResults(SDNode *Node)
CountResults - The results of target nodes have register or immediate operands first, then an optional chain, and optional flag operands (which do not go into the machine instrs.)
STATISTIC(NumFunctions, "Total number of functions")
MVT getSimpleValueType(unsigned ResNo) const
Return the type of a specified result as a simple type.
SDDbgInfo::DbgLabelIterator DbgLabelBegin() const
void setNodeId(int Id)
Set unique node id.
SDNode * getNode() const
get the SDNode which holds the desired result
bool mayLoad() const
Return true if this instruction could possibly read memory.
SmallVectorImpl< SDDbgLabel * >::iterator DbgLabelIterator
const TargetRegisterClass * CopyDstRC
Is a special copy node if != nullptr.
SmallVector< SDep, 4 > Preds
All sunit predecessors.
virtual bool isHighLatencyDef(int opc) const
Return true if this opcode has high latency to its result.
virtual void adjustSchedDependency(SUnit *def, SUnit *use, SDep &dep) const
MachineBasicBlock * getBlock()
getBlock - Return the current basic block.
static void CloneNodeWithValues(SDNode *N, SelectionDAG *DAG, ArrayRef< EVT > VTs, SDValue ExtraOper=SDValue())
MachineFunction & MF
Machine function.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
void InitNumRegDefsLeft(SUnit *SU)
InitNumRegDefsLeft - Determine the # of regs defined by this node.
void dump() const override
SDDbgInfo::DbgIterator DbgEnd() const
unsigned getNumOperands() const
Return the number of declared MachineOperands for this MachineInstruction.
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
A Use represents the edge between a Value definition and its users.
CallSiteInfo getSDCallSiteInfo(const SDNode *CallNode)
SmallVectorImpl< SDep >::const_iterator const_pred_iterator
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Regular data dependence (aka true-dependence).
CopyToReg - This node has three operands: a chain, a register number to set to this value...
op_iterator op_end() const
bool hasPhysRegDefs
Has physreg defs that are being used.
SmallVectorImpl< SDDbgValue * >::iterator DbgIterator
SDVTList getVTList(EVT VT)
Return an SDVTList that represents the list of values specified.
ScheduleDAGSDNodes(MachineFunction &mf)
This class defines information used to lower LLVM code to legal SelectionDAG operators that the targe...
This represents a list of ValueType's that has been intern'd by a SelectionDAG.
iterator_range< allnodes_iterator > allnodes()
void assign(size_type NumElts, const T &Elt)
SUnit * OrigNode
If not this, the node from which this node was cloned.
static void CheckForPhysRegDependency(SDNode *Def, SDNode *User, unsigned Op, const TargetRegisterInfo *TRI, const TargetInstrInfo *TII, unsigned &PhysReg, int &Cost)
CheckForPhysRegDependency - Check if the dependency between def and use of a specified operand is a p...
const TargetMachine & getTarget() const
virtual unsigned getInstrLatency(const InstrItineraryData *ItinData, const MachineInstr &MI, unsigned *PredCost=nullptr) const
Compute the instruction latency of a given instruction.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
std::string getDAGName() const override
Return the basic block label.
bool isCtrl() const
Shorthand for getKind() != SDep::Data.
op_iterator op_begin() const
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
SDDbgInfo::DbgIterator DbgBegin() const
bool getHasDebugValue() const
mmo_iterator memoperands_end() const
static void ProcessSDDbgValues(SDNode *N, SelectionDAG *DAG, InstrEmitter &Emitter, SmallVectorImpl< std::pair< unsigned, MachineInstr *> > &Orders, DenseMap< SDValue, unsigned > &VRBaseMap, unsigned Order)
ProcessSDDbgValues - Process SDDbgValues associated with this node.
BasicBlockListType::iterator iterator
TargetInstrInfo - Interface to description of machine instruction set.
iterator find(const_arg_type_t< KeyT > Val)
void dumpNodeAll(const SUnit &SU) const
unsigned getNumValues() const
Return the number of values defined/returned by this operator.
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
initializer< Ty > init(const Ty &Val)
bool isCall
Is a function call.
ScheduleDAGSDNodes - A ScheduleDAG for scheduling SDNode-based DAGs.
std::vector< SUnit * > Sequence
The schedule. Null SUnit*'s represent noop instructions.
SUnit * newSUnit(SDNode *N)
NewSUnit - Creates a new SUnit and return a ptr to it.
void clearDAG()
Clears the DAG state (between regions).
use_iterator use_begin() const
Provide iteration support to walk over all uses of an SDNode.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
unsigned short Latency
Node latency.
bool hasAnyUseOfValue(unsigned Value) const
Return true if there are any use of the indicated value.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
iterator_range< value_op_iterator > op_values() const
bool hasDebugValues() const
Return true if there are any SDDbgValue nodes associated with this SelectionDAG.
const SDValue & getOperand(unsigned Num) const
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
virtual void computeOperandLatency(SDNode *Def, SDNode *Use, unsigned OpIdx, SDep &dep) const
const MCPhysReg * ImplicitDefs
const InstrItineraryData * InstrItins
bool isVRegCycle
May use and def the same vreg.
This class provides iterator support for SDUse operands that use a specific SDNode.
virtual void computeLatency(SUnit *SU)
computeLatency - Compute node latency.
void addCallArgsForwardingRegs(const MachineInstr *CallI, CallSiteInfoImpl &&CallInfo)
bool isCloned
True if this node has been cloned.
SDDbgInfo::DbgIterator ByvalParmDbgEnd() const
static void ProcessSourceNode(SDNode *N, SelectionDAG *DAG, InstrEmitter &Emitter, DenseMap< SDValue, unsigned > &VRBaseMap, SmallVectorImpl< std::pair< unsigned, MachineInstr *>> &Orders, SmallSet< unsigned, 8 > &Seen, MachineInstr *NewInsn)
SDNode * getGluedNode() const
If this node has a glue operand, return the node to which the glue operand points.
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
void dumpNodeName(const SUnit &SU) const
Sched::Preference SchedulingPref
Scheduling preference.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
RegDefIter - In place iteration over the values defined by an SUnit.
bool isMachineOpcode() const
Test if this node has a post-isel opcode, directly corresponding to a MachineInstr opcode...
unsigned getNumOperands() const
Return the number of values used by this operation.
void sort(IteratorTy Start, IteratorTy End)
An unknown scheduling barrier.
static void RemoveUnusedGlue(SDNode *N, SelectionDAG *DAG)
int getOperandConstraint(unsigned OpNum, MCOI::OperandConstraint Constraint) const
Returns the value of the specific constraint if it is set.
TokenFactor - This node takes multiple tokens as input and produces a single token result...
void dump() const
Dump this node, for debugging.
bool isScheduleHigh
True if preferable to schedule high.
bool isCommutable
Is a commutable instruction.
const TargetLowering & getTargetLoweringInfo() const
MDNode * getHeapAllocSite(const SDNode *Node)
Return the HeapAllocSite type associated with the SDNode, if it exists.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
void BuildSchedGraph(AAResults *AA)
BuildSchedGraph - Build the SUnit graph from the selection dag that we are input. ...
This is used to represent a portion of an LLVM function in a low-level Data Dependence DAG representa...
value_iterator value_begin() const
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small...
void dumpSchedule() const
int getCopyCost() const
Return the cost of copying a value between two registers in this class.
An SDNode that represents everything that will be needed to construct a MachineInstr.
LLVM_NODISCARD T pop_back_val()
SUnit * Clone(SUnit *Old)
Clone - Creates a clone of the specified SUnit.
unsigned getNumDefs() const
Return the number of MachineOperands that are register definitions.
Represents one node in the SelectionDAG.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
virtual bool forceUnitLatencies() const
ForceUnitLatencies - Return true if all scheduling edges should be given a latency value of one...
static unsigned getReg(const void *D, unsigned RC, unsigned RegNo)
void addCodeViewHeapAllocSite(MachineInstr *I, const MDNode *MD)
Record heapallocsites.
static use_iterator use_end()
SmallVectorImpl< SDep >::const_iterator const_succ_iterator
SDDbgInfo::DbgLabelIterator DbgLabelEnd() const
bool isCallOp
Is a function call operand.
bool isEmpty() const
Returns true if there are no itineraries.
void setLatency(unsigned Lat)
Sets the latency for this edge.
const MachineBasicBlock * getParent() const
static bool isPassiveNode(SDNode *Node)
isPassiveNode - Return true if the node is a non-scheduled leaf.
TargetSubtargetInfo - Generic base class for all target subtargets.
int getNodeId() const
Return the unique node id.
SUnit EntrySU
Special node for the region entry.
unsigned VerifyScheduledDAG(bool isBottomUp)
Verifies that all SUnits were scheduled and that their state is consistent.
virtual void insertNoop(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI) const
Insert a noop into the instruction stream at the specified point.
Representation of each machine instruction.
SUnit ExitSU
Special node for the region exit.
mmo_iterator memoperands_begin() const
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
const TargetRegisterInfo * TRI
Target processor register info.
void EmitNode(SDNode *Node, bool IsClone, bool IsCloned, DenseMap< SDValue, unsigned > &VRBaseMap)
EmitNode - Generate machine code for a node and needed dependencies.
LLVM_NODISCARD bool empty() const
RegDefIter(const SUnit *SU, const ScheduleDAGSDNodes *SD)
const MCInstrDesc & get(unsigned Opcode) const
Return the machine instruction descriptor that corresponds to the specified instruction opcode...
unsigned short NumRegDefsLeft
of reg defs with no scheduled use.
SDDbgInfo::DbgIterator ByvalParmDbgBegin() const
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
void Run(SelectionDAG *dag, MachineBasicBlock *bb)
Run - perform scheduling.
MachineInstr * EmitDbgLabel(SDDbgLabel *SD)
Generate machine instruction for a dbg_label node.
iterator getFirstNonPHI()
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
const TargetInstrInfo * TII
Target instruction information.
Kind getKind() const
Returns an enum value representing the kind of the dependence.
CopyFromReg - This node indicates that the input value is a virtual or physical register that is defi...
const SDValue & getRoot() const
Return the root tag of the SelectionDAG.
const TargetRegisterClass * getMinimalPhysRegClass(unsigned Reg, MVT VT=MVT::Other) const
Returns the Register Class of a physical register of the given type, picking the most sub register cl...
unsigned NodeNum
Entry # of node in the node vector.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
MachineInstr * EmitDbgValue(SDDbgValue *SD, DenseMap< SDValue, unsigned > &VRBaseMap)
EmitDbgValue - Generate machine instruction for a dbg_value node.
bool addPred(const SDep &D, bool Required=true)
Adds the specified edge as a pred of the current node if not already.
void stable_sort(R &&Range)
std::string getFullName() const
Return a formatted string to identify this block and its parent function.
MachineBasicBlock::iterator getInsertPos()
getInsertPos - Return the current insertion position.
unsigned getResNo() const
get the index which selects a specific result in the SDNode
unsigned getMachineOpcode() const
This may only be called if isMachineOpcode returns true.
virtual MachineBasicBlock * EmitSchedule(MachineBasicBlock::iterator &InsertPos)
EmitSchedule - Insert MachineInstrs into the MachineBasicBlock according to the order specified in Se...
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
SmallVector< SDep, 4 > Succs
All sunit successors.
ArrayRef< SDDbgValue * > GetDbgValues(const SDNode *SD) const
Get the debug values which reference the given SDNode.
bool isScheduleLow
True if preferable to schedule low.
MachineRegisterInfo & MRI
Virtual/real register map.
std::vector< SUnit > SUnits
The scheduling units.
void setNodeMemRefs(MachineSDNode *N, ArrayRef< MachineMemOperand *> NewMemRefs)
Mutate the specified machine node's memory references to the provided list.
Unlike LLVM values, Selection DAG nodes may return multiple values as the result of a computation...
bool hasPhysRegClobbers
Has any physreg defs, used or not.
Holds the information from a dbg_value node through SDISel.
virtual void Schedule()=0
Schedule - Order nodes according to selected style, filling in the Sequence member.
virtual int getOperandLatency(const InstrItineraryData *ItinData, SDNode *DefNode, unsigned DefIdx, SDNode *UseNode, unsigned UseIdx) const
Function object to check whether the first component of a std::pair compares less than the first comp...
virtual bool shouldScheduleLoadsNear(SDNode *Load1, SDNode *Load2, int64_t Offset1, int64_t Offset2, unsigned NumLoads) const
This is a used by the pre-regalloc scheduler to determine (in conjunction with areLoadsFromSameBasePt...
unsigned getOrder() const
Returns the SDNodeOrder.
Scheduling unit. This is a node in the scheduling DAG.
Wrapper class representing virtual and physical registers.
static bool AddGlue(SDNode *N, SDValue Glue, bool AddGlue, SelectionDAG *DAG)
This file describes how to lower LLVM code to machine code.
void VerifyScheduledSequence(bool isBottomUp)
VerifyScheduledSequence - Verify that all SUnits are scheduled and consistent with the Sequence of sc...
A discriminated union of two or more pointer types, with the discriminator in the low bit of the poin...
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.