Go to the documentation of this file.
40 #ifndef LLVM_CODEGEN_MACHINEPIPELINER_H
41 #define LLVM_CODEGEN_MACHINEPIPELINER_H
113 bool Scheduled =
false;
117 unsigned II_setByPragma = 0;
126 int ZeroLatencyDepth = 0;
127 int ZeroLatencyHeight = 0;
129 NodeInfo() =
default;
132 std::vector<NodeInfo> ScheduleInfo;
134 enum OrderKind { BottomUp = 0, TopDown = 1 };
151 std::vector<std::unique_ptr<ScheduleDAGMutation>> Mutations;
155 std::vector<SUnit> &
SUnits;
161 std::vector<int> *Node2Idx;
163 static unsigned MaxPaths;
167 :
SUnits(SUs), Blocked(SUs.size()),
B(SUs.size()), AdjK(SUs.size()) {
168 Node2Idx =
new std::vector<int>(SUs.size());
170 for (
const auto &NodeNum : Topo)
171 Node2Idx->at(NodeNum) = Idx++;
174 ~Circuits() {
delete Node2Idx; }
185 bool circuit(
int V,
int S,
NodeSetType &NodeSets,
bool HasBackedge =
false);
197 RegClassInfo(rci), II_setByPragma(II), Topo(
SUnits, &
ExitSU) {
198 P.MF->getSubtarget().getSMSMutations(Mutations);
200 Mutations.push_back(std::make_unique<CopyToPhiMutation>());
225 return ScheduleInfo[
Node->NodeNum].ZeroLatencyDepth;
234 return ScheduleInfo[
Node->NodeNum].ZeroLatencyHeight;
266 InstrChanges.
find(SU);
267 if (It != InstrChanges.
end())
268 return It->second.first;
279 void addLoopCarriedDependences(
AAResults *AA);
280 void updatePhiDependences();
281 void changeDependences();
282 unsigned calculateResMII();
283 unsigned calculateRecMII(NodeSetType &RecNodeSets);
284 void findCircuits(NodeSetType &NodeSets);
285 void fuseRecs(NodeSetType &NodeSets);
286 void removeDuplicateNodes(NodeSetType &NodeSets);
287 void computeNodeFunctions(NodeSetType &NodeSets);
288 void registerPressureFilter(NodeSetType &NodeSets);
289 void colocateNodeSets(NodeSetType &NodeSets);
290 void checkNodeSets(NodeSetType &NodeSets);
291 void groupRemainingNodes(NodeSetType &NodeSets);
294 void computeNodeOrder(NodeSetType &NodeSets);
295 void checkValidNodeOrder(
const NodeSetType &Circuits)
const;
300 unsigned &OffsetPos,
unsigned &NewBase,
302 void postprocessDAG();
304 void setMII(
unsigned ResMII,
unsigned RecMII);
313 bool HasRecurrence =
false;
316 unsigned MaxDepth = 0;
317 unsigned Colocate = 0;
318 SUnit *ExceedPressure =
nullptr;
319 unsigned Latency = 0;
327 for (
unsigned i = 0,
e = Nodes.
size();
i <
e; ++
i) {
329 for (
const SDep &Succ : Nodes[
i]->Succs) {
330 auto SuccSUnit = Succ.getSUnit();
331 if (!Nodes.
count(SuccSUnit))
333 unsigned CurLatency = Succ.getLatency();
334 unsigned MaxLatency = 0;
335 if (SuccSUnitLatency.
count(SuccSUnit))
336 MaxLatency = SuccSUnitLatency[SuccSUnit];
337 if (CurLatency > MaxLatency)
338 SuccSUnitLatency[SuccSUnit] = CurLatency;
340 for (
auto SUnitLatency : SuccSUnitLatency)
341 Latency += SUnitLatency.second;
349 template <
typename UnaryPredicate>
bool remove_if(UnaryPredicate
P) {
377 for (
SUnit *SU : *
this) {
390 HasRecurrence =
false;
394 ExceedPressure =
nullptr;
404 if (RecMII == RHS.RecMII) {
405 if (Colocate != 0 && RHS.Colocate != 0 && Colocate != RHS.Colocate)
406 return Colocate < RHS.Colocate;
407 if (MaxMOV == RHS.MaxMOV)
408 return MaxDepth > RHS.MaxDepth;
409 return MaxMOV < RHS.MaxMOV;
411 return RecMII > RHS.RecMII;
415 return RecMII == RHS.RecMII && MaxMOV == RHS.MaxMOV &&
416 MaxDepth == RHS.MaxDepth;
425 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
439 std::unique_ptr<DFAPacketizer> DFAResources;
450 : STI(
ST), SM(
ST->getSchedModel()), UseDFA(
ST->useDFAforSMS()),
451 ProcResourceMasks(SM.getNumProcResourceKinds(), 0),
452 ProcResourceCount(SM.getNumProcResourceKinds(), 0) {
454 DFAResources.reset(
ST->getInstrInfo()->CreateTargetScheduleState(*
ST));
494 std::map<SUnit *, int> InstrToCycle;
504 int InitiationInterval = 0;
516 : ST(mf->getSubtarget()),
MRI(mf->getRegInfo()), ProcItinResources(&ST) {}
519 ScheduledInstrs.
clear();
520 InstrToCycle.clear();
523 InitiationInterval = 0;
549 bool insert(
SUnit *SU,
int StartCycle,
int EndCycle,
int II);
564 std::map<SUnit *, int>::const_iterator
it = InstrToCycle.find(SU);
565 if (
it == InstrToCycle.end())
567 return (
it->second - FirstCycle) / InitiationInterval;
573 std::map<SUnit *, int>::const_iterator
it = InstrToCycle.find(SU);
574 assert(
it != InstrToCycle.end() &&
"Instruction hasn't been scheduled.");
575 return (
it->second - FirstCycle) % InitiationInterval;
580 return (LastCycle - FirstCycle) / InitiationInterval;
585 return ScheduledInstrs[cycle];
591 std::deque<SUnit *> &Insts);
601 #endif // LLVM_CODEGEN_MACHINEPIPELINER_H
This class builds the dependence graph for the instructions in a loop, and attempts to schedule the i...
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
unsigned getHeight(SUnit *Node)
The height, in the dependence graph, for a node.
void finishBlock() override
Clean up after the software pipeliner runs.
void print(raw_ostream &os) const
LLVM_DUMP_METHOD void dump() const
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Represents a single loop in the control flow graph.
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
size_type size() const
Determine the number of elements in the SetVector.
Reference model for inliner Oz decision policy Note this model is also referenced by test Transforms Inline ML tests if replacing it
int compareRecMII(NodeSet &RHS)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
SetVector< SUnit * >::const_iterator iterator
@ Anti
A register anti-dependence (aka WAR).
void schedule() override
We override the schedule function in ScheduleDAGInstrs to implement the scheduling part of the Swing ...
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
typename vector_type::const_iterator const_iterator
bool isLoopCarriedDep(SUnit *Source, const SDep &Dep, bool isSucc=true)
Return true for an order or output dependence that is loop carried potentially.
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
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 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...
SmallVector< MachineOperand, 4 > BrCond
bool remove_if(UnaryPredicate P)
Remove items from the set vector based on a predicate function.
SMSchedule(MachineFunction *mf)
This class can compute a topological ordering for SUnits and provides methods for dynamically updatin...
ResourceManager(const TargetSubtargetInfo *ST)
TargetInstrInfo - Interface to description of machine instruction set.
void apply(Opt *O, const Mod &M, const Mods &... Ms)
iterator begin()
Get an iterator to the beginning of the SetVector.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
void dump() const
Utility function used for debugging to print the schedule.
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...
bool isBackedge(SUnit *Source, const SDep &Dep)
Return true if the dependence is a back-edge in the data dependence graph.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
int getMOV(SUnit *Node)
The mobility function, which the number of slots in which an instruction may be scheduled.
Represent the analysis usage information of a pass.
int getFinalCycle() const
Return the last cycle in the finalized schedule.
int getFirstCycle() const
Return the first cycle in the completed schedule.
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 setInitiationInterval(int ii)
Set the initiation interval for this schedule.
bool isValidSchedule(SwingSchedulerDAG *SSD)
This class implements an extremely fast bulk output stream that can only output to a stream.
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 initializeMachinePipelinerPass(PassRegistry &)
the resulting code requires compare and branches when and if the revised code is with conditional branches instead of More there is a byte word extend before each where there should be only and the condition codes are not remembered when the same two values are compared twice More LSR enhancements i8 and i32 load store addressing modes are identical int int c
A NodeSet contains a set of SUnit DAG nodes with additional information that assigns a priority to th...
bool empty() const
Determine if the SetVector is empty or not.
void setColocate(unsigned c)
bool isLoopCarried(SwingSchedulerDAG *SSD, MachineInstr &Phi)
Return true if the scheduled Phi has a loop carried operand.
bool operator!=(const NodeSet &RHS) const
void setExceedPressure(SUnit *SU)
The main class in the implementation of the target independent software pipeliner pass.
bool canReserveResources(const MCInstrDesc *MID) const
Check if the resources occupied by a MCInstrDesc are available in the current state.
void computeStart(SUnit *SU, int *MaxEarlyStart, int *MinLateStart, int *MinEnd, int *MaxStart, int II, SwingSchedulerDAG *DAG)
Compute the scheduling start slot for the instruction.
static bool classof(const ScheduleDAGInstrs *DAG)
static const int DefaultProcResSize
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Representation of each machine instruction.
int getInitiationInterval() const
Return the initiation interval for this schedule.
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
MachineOptimizationRemarkEmitter * ORE
const InstrItineraryData * InstrItins
MachineInstr * getInstr() const
Returns the representative MachineInstr for this SUnit.
int getALAP(SUnit *Node)
Return the latest time an instruction my be scheduled.
iterator find(const_arg_type_t< KeyT > Val)
MachineInstr * LoopCompare
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
MachineInstr * LoopInductionVar
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 setRecMII(unsigned mii)
std::deque< SUnit * > & getInstructions(int cycle)
Return the instructions that are scheduled at the specified cycle.
bool insert(const value_type &X)
Insert a new element into the SetVector.
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 operator==(const NodeSet &RHS) const
RegisterClassInfo RegClassInfo
cl::opt< bool > SwpEnableCopyToPhi
MachineFunction & MF
Machine function.
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
bool isScheduledAtStage(SUnit *SU, unsigned StageNum)
Return true if the instruction is scheduled at the specified stage.
unsigned count(SUnit *SU) const
void finalizeSchedule(SwingSchedulerDAG *SSD)
After the schedule has been formed, call this function to combine the instructions from the different...
TargetSubtargetInfo - Generic base class for all target subtargets.
void reserveResources(const MCInstrDesc *MID)
Reserve the resources occupied by a MCInstrDesc and change the current state to reflect that change.
unsigned const MachineRegisterInfo * MRI
Wrapper class representing virtual and physical registers.
void clear()
Completely clear the SetVector.
const MachineLoopInfo * MLI
bool remove_if(UnaryPredicate P)
std::vector< SUnit > SUnits
The scheduling units.
void initProcResourceVectors(const MCSchedModel &SM, SmallVectorImpl< uint64_t > &Masks)
unsigned getDepth(SUnit *Node)
The depth, in the dependence graph, for a node.
const TargetInstrInfo * TII
SwingSchedulerDAG(MachinePipeliner &P, MachineLoop &L, LiveIntervals &lis, const RegisterClassInfo &rci, unsigned II)
void addMutation(std::unique_ptr< ScheduleDAGMutation > Mutation)
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
void computeNodeSetInfo(SwingSchedulerDAG *SSD)
Summarize node functions for the entire node set.
void clearResources()
Reset the state.
Machine model for scheduling, bundling, and heuristics.
void print(raw_ostream &os) const
Print the schedule information to the given output.
void applyInstrChange(MachineInstr *MI, SMSchedule &Schedule)
Apply changes to the instruction if needed.
Kind getKind() const
Returns an enum value representing the kind of the dependence.
bool isExceedSU(SUnit *SU)
int earliestCycleInChain(const SDep &Dep)
Return the cycle of the earliest scheduled instruction in the dependence chain.
iterator end()
Get an iterator to the end of the SetVector.
Pass interface - Implemented by all 'passes'.
Cache the target analysis information about the loop.
std::set< NodeId > NodeSet
Align max(MaybeAlign Lhs, Align Rhs)
SUnit * getNode(unsigned i) const
bool runOnMachineFunction(MachineFunction &MF) override
The "main" function for implementing Swing Modulo Scheduling.
Mutate the DAG as a postpass after normal DAG building.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void insert(iterator S, iterator E)
Scheduling unit. This is a node in the scheduling DAG.
unsigned getMaxStageCount()
Return the maximum stage count needed for this schedule.
A ScheduleDAG for scheduling lists of MachineInstr.
unsigned cycleScheduled(SUnit *SU) const
Return the cycle for a scheduled instruction.
int latestCycleInChain(const SDep &Dep)
Return the cycle of the latest scheduled instruction in the dependence chain.
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
A vector that has set insertion semantics.
const MachineLoopInfo * MLI
void fixupRegisterOverlaps(std::deque< SUnit * > &Instrs)
Attempt to fix the degenerate cases when the instruction serialization causes the register lifetimes ...
bool operator>(const NodeSet &RHS) const
Sort the node sets by importance.
Generic base class for all target subtargets.
int getASAP(SUnit *Node)
Return the earliest time an instruction may be scheduled.
NodeSet(iterator S, iterator E)
SUnit ExitSU
Special node for the region exit.
Itinerary data supplied by a subtarget to be used by a target.
bool hasNewSchedule()
Return true if the loop kernel has been scheduled.
int stageScheduled(SUnit *SU) const
Return the stage for a scheduled instruction.
This class represents the scheduled code.
unsigned getInstrBaseReg(SUnit *SU)
Return the new base register that was stored away for the changed instruction.
const MachineDominatorTree * MDT