Go to the documentation of this file.
40 #ifndef LLVM_CODEGEN_MACHINEPIPELINER_H
41 #define LLVM_CODEGEN_MACHINEPIPELINER_H
119 bool Scheduled =
false;
123 unsigned II_setByPragma = 0;
133 int ZeroLatencyDepth = 0;
134 int ZeroLatencyHeight = 0;
136 NodeInfo() =
default;
139 std::vector<NodeInfo> ScheduleInfo;
141 enum OrderKind { BottomUp = 0, TopDown = 1 };
158 std::vector<std::unique_ptr<ScheduleDAGMutation>> Mutations;
162 std::vector<SUnit> &
SUnits;
168 std::vector<int> *Node2Idx;
170 static unsigned MaxPaths;
174 :
SUnits(SUs), Blocked(SUs.size()),
B(SUs.size()), AdjK(SUs.size()) {
175 Node2Idx =
new std::vector<int>(SUs.size());
177 for (
const auto &NodeNum : Topo)
178 Node2Idx->at(NodeNum) = Idx++;
181 ~Circuits() {
delete Node2Idx; }
192 bool circuit(
int V,
int S,
NodeSetType &NodeSets,
bool HasBackedge =
false);
205 RegClassInfo(rci), II_setByPragma(II), LoopPipelinerInfo(PLI),
207 P.MF->getSubtarget().getSMSMutations(Mutations);
209 Mutations.push_back(std::make_unique<CopyToPhiMutation>());
234 return ScheduleInfo[
Node->NodeNum].ZeroLatencyDepth;
243 return ScheduleInfo[
Node->NodeNum].ZeroLatencyHeight;
275 InstrChanges.
find(SU);
276 if (It != InstrChanges.
end())
277 return It->second.first;
289 void updatePhiDependences();
290 void changeDependences();
291 unsigned calculateResMII();
292 unsigned calculateRecMII(NodeSetType &RecNodeSets);
293 void findCircuits(NodeSetType &NodeSets);
294 void fuseRecs(NodeSetType &NodeSets);
295 void removeDuplicateNodes(NodeSetType &NodeSets);
296 void computeNodeFunctions(NodeSetType &NodeSets);
297 void registerPressureFilter(NodeSetType &NodeSets);
298 void colocateNodeSets(NodeSetType &NodeSets);
299 void checkNodeSets(NodeSetType &NodeSets);
300 void groupRemainingNodes(NodeSetType &NodeSets);
303 void computeNodeOrder(NodeSetType &NodeSets);
304 void checkValidNodeOrder(
const NodeSetType &Circuits)
const;
309 unsigned &OffsetPos,
unsigned &NewBase,
311 void postprocessDAG();
313 void setMII(
unsigned ResMII,
unsigned RecMII);
322 bool HasRecurrence =
false;
325 unsigned MaxDepth = 0;
326 unsigned Colocate = 0;
327 SUnit *ExceedPressure =
nullptr;
328 unsigned Latency = 0;
336 for (
unsigned i = 0,
e = Nodes.
size();
i <
e; ++
i) {
338 for (
const SDep &Succ : Nodes[
i]->Succs) {
339 auto SuccSUnit = Succ.getSUnit();
340 if (!Nodes.
count(SuccSUnit))
342 unsigned CurLatency = Succ.getLatency();
343 unsigned MaxLatency = 0;
344 if (SuccSUnitLatency.
count(SuccSUnit))
345 MaxLatency = SuccSUnitLatency[SuccSUnit];
346 if (CurLatency > MaxLatency)
347 SuccSUnitLatency[SuccSUnit] = CurLatency;
349 for (
auto SUnitLatency : SuccSUnitLatency)
350 Latency += SUnitLatency.second;
358 template <
typename UnaryPredicate>
bool remove_if(UnaryPredicate
P) {
386 for (
SUnit *SU : *
this) {
399 HasRecurrence =
false;
403 ExceedPressure =
nullptr;
413 if (RecMII ==
RHS.RecMII) {
414 if (Colocate != 0 &&
RHS.Colocate != 0 && Colocate !=
RHS.Colocate)
415 return Colocate <
RHS.Colocate;
416 if (MaxMOV ==
RHS.MaxMOV)
417 return MaxDepth >
RHS.MaxDepth;
418 return MaxMOV <
RHS.MaxMOV;
420 return RecMII >
RHS.RecMII;
424 return RecMII ==
RHS.RecMII && MaxMOV ==
RHS.MaxMOV &&
425 MaxDepth ==
RHS.MaxDepth;
434 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
448 std::unique_ptr<DFAPacketizer> DFAResources;
459 : STI(
ST), SM(
ST->getSchedModel()), UseDFA(
ST->useDFAforSMS()),
460 ProcResourceMasks(SM.getNumProcResourceKinds(), 0),
461 ProcResourceCount(SM.getNumProcResourceKinds(), 0) {
463 DFAResources.reset(
ST->getInstrInfo()->CreateTargetScheduleState(*
ST));
503 std::map<SUnit *, int> InstrToCycle;
513 int InitiationInterval = 0;
525 : ST(mf->getSubtarget()),
MRI(mf->getRegInfo()), ProcItinResources(&ST) {}
528 ScheduledInstrs.
clear();
529 InstrToCycle.clear();
532 InitiationInterval = 0;
558 bool insert(
SUnit *SU,
int StartCycle,
int EndCycle,
int II);
573 std::map<SUnit *, int>::const_iterator
it = InstrToCycle.find(SU);
574 if (
it == InstrToCycle.end())
576 return (
it->second - FirstCycle) / InitiationInterval;
582 std::map<SUnit *, int>::const_iterator
it = InstrToCycle.find(SU);
583 assert(
it != InstrToCycle.end() &&
"Instruction hasn't been scheduled.");
584 return (
it->second - FirstCycle) % InitiationInterval;
589 return (LastCycle - FirstCycle) / InitiationInterval;
594 return ScheduledInstrs[cycle];
607 std::deque<SUnit *> &Insts);
617 #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.
This is an optimization pass for GlobalISel generic memory operations.
into xmm2 addss xmm2 xmm1 xmm3 addss xmm3 movaps xmm0 unpcklps xmm0 ret seems silly when it could just be one addps Expand libm rounding functions main should enable SSE DAZ mode and other fast SSE modes Think about doing i64 math in SSE regs on x86 This testcase should have no SSE instructions in it
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
SwingSchedulerDAG(MachinePipeliner &P, MachineLoop &L, LiveIntervals &lis, const RegisterClassInfo &rci, unsigned II, TargetInstrInfo::PipelinerLoopInfo *PLI)
size_type size() const
Determine the number of elements in the SetVector.
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
bool normalizeNonPipelinedInstructions(SwingSchedulerDAG *SSD, TargetInstrInfo::PipelinerLoopInfo *PLI)
Reg
All possible values of the reg field in the ModR/M byte.
@ 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.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
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...
Object returned by analyzeLoopForPipelining.
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.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
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
std::unique_ptr< TargetInstrInfo::PipelinerLoopInfo > LoopPipelinerInfo
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
SmallSet< SUnit *, 8 > computeUnpipelineableNodes(SwingSchedulerDAG *SSD, TargetInstrInfo::PipelinerLoopInfo *PLI)
Determine transitive dependences of unpipelineable instructions.
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