40#ifndef LLVM_CODEGEN_MACHINEPIPELINER_H
41#define LLVM_CODEGEN_MACHINEPIPELINER_H
121 bool Scheduled =
false;
125 unsigned II_setByPragma = 0;
135 int ZeroLatencyDepth = 0;
136 int ZeroLatencyHeight = 0;
138 NodeInfo() =
default;
141 std::vector<NodeInfo> ScheduleInfo;
143 enum OrderKind { BottomUp = 0, TopDown = 1 };
160 std::vector<std::unique_ptr<ScheduleDAGMutation>> Mutations;
164 std::vector<SUnit> &SUnits;
170 std::vector<int> *Node2Idx;
171 unsigned NumPaths = 0u;
172 static unsigned MaxPaths;
176 : SUnits(SUs), Blocked(SUs.size()), B(SUs.size()), AdjK(SUs.size()) {
177 Node2Idx =
new std::vector<int>(SUs.size());
179 for (
const auto &NodeNum : Topo)
180 Node2Idx->at(NodeNum) =
Idx++;
182 Circuits &operator=(
const Circuits &other) =
delete;
183 Circuits(
const Circuits &other) =
delete;
184 ~Circuits() {
delete Node2Idx; }
195 bool circuit(
int V,
int S,
NodeSetType &NodeSets,
bool HasBackedge =
false);
208 RegClassInfo(rci), II_setByPragma(II), LoopPipelinerInfo(PLI),
210 P.MF->getSubtarget().getSMSMutations(Mutations);
212 Mutations.push_back(std::make_unique<CopyToPhiMutation>());
237 return ScheduleInfo[
Node->NodeNum].ZeroLatencyDepth;
246 return ScheduleInfo[
Node->NodeNum].ZeroLatencyHeight;
278 InstrChanges.
find(SU);
279 if (It != InstrChanges.
end())
280 return It->second.first;
285 Mutations.push_back(std::move(
Mutation));
291 void addLoopCarriedDependences(
AAResults *AA);
292 void updatePhiDependences();
293 void changeDependences();
294 unsigned calculateResMII();
295 unsigned calculateRecMII(NodeSetType &RecNodeSets);
296 void findCircuits(NodeSetType &NodeSets);
297 void fuseRecs(NodeSetType &NodeSets);
298 void removeDuplicateNodes(NodeSetType &NodeSets);
299 void computeNodeFunctions(NodeSetType &NodeSets);
300 void registerPressureFilter(NodeSetType &NodeSets);
301 void colocateNodeSets(NodeSetType &NodeSets);
302 void checkNodeSets(NodeSetType &NodeSets);
303 void groupRemainingNodes(NodeSetType &NodeSets);
306 void computeNodeOrder(NodeSetType &NodeSets);
307 void checkValidNodeOrder(
const NodeSetType &Circuits)
const;
312 unsigned &OffsetPos,
unsigned &NewBase,
314 void postProcessDAG();
316 void setMII(
unsigned ResMII,
unsigned RecMII);
325 bool HasRecurrence =
false;
328 unsigned MaxDepth = 0;
329 unsigned Colocate = 0;
330 SUnit *ExceedPressure =
nullptr;
331 unsigned Latency = 0;
341 for (
const SDep &Succ :
Node->Succs) {
343 if (!Nodes.count(SuccSUnit))
346 unsigned MaxLatency = 0;
347 if (SuccSUnitLatency.
count(SuccSUnit))
348 MaxLatency = SuccSUnitLatency[SuccSUnit];
349 if (CurLatency > MaxLatency)
350 SuccSUnitLatency[SuccSUnit] = CurLatency;
352 for (
auto SUnitLatency : SuccSUnitLatency)
353 Latency += SUnitLatency.second;
361 template <
typename UnaryPredicate>
bool remove_if(UnaryPredicate
P) {
389 for (
SUnit *SU : *
this) {
390 MaxMOV = std::max(MaxMOV, SSD->
getMOV(SU));
391 MaxDepth = std::max(MaxDepth, SSD->
getDepth(SU));
402 HasRecurrence =
false;
406 ExceedPressure =
nullptr;
416 if (RecMII ==
RHS.RecMII) {
417 if (Colocate != 0 &&
RHS.Colocate != 0 && Colocate !=
RHS.Colocate)
418 return Colocate <
RHS.Colocate;
419 if (MaxMOV ==
RHS.MaxMOV)
420 return MaxDepth >
RHS.MaxDepth;
421 return MaxMOV <
RHS.MaxMOV;
423 return RecMII >
RHS.RecMII;
427 return RecMII ==
RHS.RecMII && MaxMOV ==
RHS.MaxMOV &&
428 MaxDepth ==
RHS.MaxDepth;
437#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
468 int InitiationInterval = 0;
472 int calculateResMIIDFA()
const;
474 bool isOverbooked()
const;
483 int positiveModulo(
int Dividend,
int Divisor)
const {
485 int R = Dividend % Divisor;
491#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
497 : STI(ST), SM(ST->getSchedModel()), ST(ST),
TII(ST->getInstrInfo()),
498 DAG(DAG), UseDFA(ST->useDFAforSMS()),
499 ProcResourceMasks(SM.getNumProcResourceKinds(), 0),
500 IssueWidth(SM.IssueWidth) {
540 std::map<SUnit *, int> InstrToCycle;
550 int InitiationInterval = 0;
562 : ST(mf->getSubtarget()),
MRI(mf->getRegInfo()),
563 ProcItinResources(&ST, DAG) {}
566 ScheduledInstrs.
clear();
567 InstrToCycle.clear();
570 InitiationInterval = 0;
575 InitiationInterval = ii;
576 ProcItinResources.
init(ii);
599 bool insert(
SUnit *SU,
int StartCycle,
int EndCycle,
int II);
614 std::map<SUnit *, int>::const_iterator it = InstrToCycle.find(SU);
615 if (it == InstrToCycle.end())
617 return (it->second - FirstCycle) / InitiationInterval;
623 std::map<SUnit *, int>::const_iterator it = InstrToCycle.find(SU);
624 assert(it != InstrToCycle.end() &&
"Instruction hasn't been scheduled.");
625 return (it->second - FirstCycle) % InitiationInterval;
630 return (LastCycle - FirstCycle) / InitiationInterval;
635 return ScheduledInstrs[cycle];
648 std::deque<SUnit *> &Insts);
unsigned const MachineRegisterInfo * MRI
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
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
const HexagonInstrInfo * TII
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file implements a set that has insertion order iteration characteristics.
Represent the analysis usage information of a pass.
iterator find(const_arg_type_t< KeyT > Val)
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
A possibly irreducible generalization of a Loop.
Itinerary data supplied by a subtarget to be used by a target.
Represents a single loop in the control flow graph.
Generic base class for all target subtargets.
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Representation of each machine instruction.
MachineOperand class - Representation of each machine instruction operand.
The main class in the implementation of the target independent software pipeliner pass.
const TargetInstrInfo * TII
bool runOnMachineFunction(MachineFunction &MF) override
The "main" function for implementing Swing Modulo Scheduling.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
const MachineDominatorTree * MDT
const MachineLoopInfo * MLI
MachineOptimizationRemarkEmitter * ORE
RegisterClassInfo RegClassInfo
const InstrItineraryData * InstrItins
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
A NodeSet contains a set of SUnit DAG nodes with additional information that assigns a priority to th...
SUnit * getNode(unsigned i) const
SetVector< SUnit * >::const_iterator iterator
void print(raw_ostream &os) const
bool isExceedSU(SUnit *SU)
void insert(iterator S, iterator E)
void setRecMII(unsigned mii)
void computeNodeSetInfo(SwingSchedulerDAG *SSD)
Summarize node functions for the entire node set.
unsigned count(SUnit *SU) const
void setColocate(unsigned c)
bool operator>(const NodeSet &RHS) const
Sort the node sets by importance.
int compareRecMII(NodeSet &RHS)
NodeSet(iterator S, iterator E)
bool operator!=(const NodeSet &RHS) const
LLVM_DUMP_METHOD void dump() const
bool operator==(const NodeSet &RHS) const
bool remove_if(UnaryPredicate P)
void setExceedPressure(SUnit *SU)
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Pass interface - Implemented by all 'passes'.
Wrapper class representing virtual and physical registers.
int calculateResMII() const
void initProcResourceVectors(const MCSchedModel &SM, SmallVectorImpl< uint64_t > &Masks)
ResourceManager(const TargetSubtargetInfo *ST, SwingSchedulerDAG *DAG)
void init(int II)
Initialize resources with the initiation interval II.
bool canReserveResources(SUnit &SU, int Cycle)
Check if the resources occupied by a machine instruction are available in the current state.
Kind getKind() const
Returns an enum value representing the kind of the dependence.
@ Anti
A register anti-dependence (aka WAR).
unsigned getLatency() const
Returns the latency value for this edge, which roughly means the minimum number of cycles that must e...
This class represents the scheduled code.
int earliestCycleInChain(const SDep &Dep)
Return the cycle of the earliest scheduled instruction in the dependence chain.
void setInitiationInterval(int ii)
Set the initiation interval for this schedule.
SmallSet< SUnit *, 8 > computeUnpipelineableNodes(SwingSchedulerDAG *SSD, TargetInstrInfo::PipelinerLoopInfo *PLI)
Determine transitive dependences of unpipelineable instructions.
bool isLoopCarriedDefOfUse(SwingSchedulerDAG *SSD, MachineInstr *Def, MachineOperand &MO)
Return true if the instruction is a definition that is loop carried and defines the use on the next i...
void dump() const
Utility function used for debugging to print the schedule.
bool insert(SUnit *SU, int StartCycle, int EndCycle, int II)
Try to schedule the node at the specified StartCycle and continue until the node is schedule or the E...
unsigned getMaxStageCount()
Return the maximum stage count needed for this schedule.
void print(raw_ostream &os) const
Print the schedule information to the given output.
int latestCycleInChain(const SDep &Dep)
Return the cycle of the latest scheduled instruction in the dependence chain.
int stageScheduled(SUnit *SU) const
Return the stage for a scheduled instruction.
bool isScheduledAtStage(SUnit *SU, unsigned StageNum)
Return true if the instruction is scheduled at the specified stage.
void computeStart(SUnit *SU, int *MaxEarlyStart, int *MinLateStart, int *MinEnd, int *MaxStart, int II, SwingSchedulerDAG *DAG)
Compute the scheduling start slot for the instruction.
bool isValidSchedule(SwingSchedulerDAG *SSD)
int getInitiationInterval() const
Return the initiation interval for this schedule.
std::deque< SUnit * > & getInstructions(int cycle)
Return the instructions that are scheduled at the specified cycle.
int getFirstCycle() const
Return the first cycle in the completed schedule.
unsigned cycleScheduled(SUnit *SU) const
Return the cycle for a scheduled instruction.
bool isLoopCarried(SwingSchedulerDAG *SSD, MachineInstr &Phi)
Return true if the scheduled Phi has a loop carried operand.
SMSchedule(MachineFunction *mf, SwingSchedulerDAG *DAG)
bool normalizeNonPipelinedInstructions(SwingSchedulerDAG *SSD, TargetInstrInfo::PipelinerLoopInfo *PLI)
int getFinalCycle() const
Return the last cycle in the finalized schedule.
void orderDependence(SwingSchedulerDAG *SSD, SUnit *SU, std::deque< SUnit * > &Insts)
Order the instructions within a cycle so that the definitions occur before the uses.
void finalizeSchedule(SwingSchedulerDAG *SSD)
After the schedule has been formed, call this function to combine the instructions from the different...
Scheduling unit. This is a node in the scheduling DAG.
MachineInstr * getInstr() const
Returns the representative MachineInstr for this SUnit.
A ScheduleDAG for scheduling lists of MachineInstr.
const MachineLoopInfo * MLI
Mutate the DAG as a postpass after normal DAG building.
This class can compute a topological ordering for SUnits and provides methods for dynamically updatin...
std::vector< SUnit > SUnits
The scheduling units.
MachineFunction & MF
Machine function.
SUnit ExitSU
Special node for the region exit.
A vector that has set insertion semantics.
bool remove_if(UnaryPredicate P)
Remove items from the set vector based on a predicate function.
size_type size() const
Determine the number of elements in the SetVector.
iterator end()
Get an iterator to the end of the SetVector.
typename vector_type::const_iterator const_iterator
void clear()
Completely clear the SetVector.
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
bool empty() const
Determine if the SetVector is empty or not.
iterator begin()
Get an iterator to the beginning of the SetVector.
bool insert(const value_type &X)
Insert a new element into the SetVector.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
This class builds the dependence graph for the instructions in a loop, and attempts to schedule the i...
unsigned getDepth(SUnit *Node)
The depth, in the dependence graph, for a node.
unsigned getInstrBaseReg(SUnit *SU)
Return the new base register that was stored away for the changed instruction.
int getASAP(SUnit *Node)
Return the earliest time an instruction may be scheduled.
void applyInstrChange(MachineInstr *MI, SMSchedule &Schedule)
Apply changes to the instruction if needed.
void finishBlock() override
Clean up after the software pipeliner runs.
void fixupRegisterOverlaps(std::deque< SUnit * > &Instrs)
Attempt to fix the degenerate cases when the instruction serialization causes the register lifetimes ...
bool hasNewSchedule()
Return true if the loop kernel has been scheduled.
void addMutation(std::unique_ptr< ScheduleDAGMutation > Mutation)
SwingSchedulerDAG(MachinePipeliner &P, MachineLoop &L, LiveIntervals &lis, const RegisterClassInfo &rci, unsigned II, TargetInstrInfo::PipelinerLoopInfo *PLI)
int getZeroLatencyDepth(SUnit *Node)
The maximum unweighted length of a path from an arbitrary node to the given node in which each edge h...
bool isLoopCarriedDep(SUnit *Source, const SDep &Dep, bool isSucc=true)
Return true for an order or output dependence that is loop carried potentially.
unsigned getDistance(SUnit *U, SUnit *V, const SDep &Dep)
The distance function, which indicates that operation V of iteration I depends on operations U of ite...
void schedule() override
We override the schedule function in ScheduleDAGInstrs to implement the scheduling part of the Swing ...
int getMOV(SUnit *Node)
The mobility function, which the number of slots in which an instruction may be scheduled.
int getZeroLatencyHeight(SUnit *Node)
The maximum unweighted length of a path from the given node to an arbitrary node in which each edge h...
bool isBackedge(SUnit *Source, const SDep &Dep)
Return true if the dependence is a back-edge in the data dependence graph.
static bool classof(const ScheduleDAGInstrs *DAG)
unsigned getHeight(SUnit *Node)
The height, in the dependence graph, for a node.
int getALAP(SUnit *Node)
Return the latest time an instruction my be scheduled.
Object returned by analyzeLoopForPipelining.
TargetInstrInfo - Interface to description of machine instruction set.
TargetSubtargetInfo - Generic base class for all target subtargets.
This class implements an extremely fast bulk output stream that can only output to a stream.
std::set< NodeId > NodeSet
This is an optimization pass for GlobalISel generic memory operations.
void initializeMachinePipelinerPass(PassRegistry &)
cl::opt< bool > SwpEnableCopyToPhi
static const int DefaultProcResSize
cl::opt< int > SwpForceIssueWidth
A command line argument to force pipeliner to use specified issue width.
Summarize the scheduling resources required for an instruction of a particular scheduling class.
Machine model for scheduling, bundling, and heuristics.
Cache the target analysis information about the loop.
MachineInstr * LoopInductionVar
SmallVector< MachineOperand, 4 > BrCond
MachineInstr * LoopCompare
std::unique_ptr< TargetInstrInfo::PipelinerLoopInfo > LoopPipelinerInfo