LLVM  9.0.0svn
MachinePipeliner.h
Go to the documentation of this file.
1 //===- MachinePipeliner.h - Machine Software Pipeliner Pass -------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // An implementation of the Swing Modulo Scheduling (SMS) software pipeliner.
10 //
11 // Software pipelining (SWP) is an instruction scheduling technique for loops
12 // that overlap loop iterations and exploits ILP via a compiler transformation.
13 //
14 // Swing Modulo Scheduling is an implementation of software pipelining
15 // that generates schedules that are near optimal in terms of initiation
16 // interval, register requirements, and stage count. See the papers:
17 //
18 // "Swing Modulo Scheduling: A Lifetime-Sensitive Approach", by J. Llosa,
19 // A. Gonzalez, E. Ayguade, and M. Valero. In PACT '96 Proceedings of the 1996
20 // Conference on Parallel Architectures and Compilation Techiniques.
21 //
22 // "Lifetime-Sensitive Modulo Scheduling in a Production Environment", by J.
23 // Llosa, E. Ayguade, A. Gonzalez, M. Valero, and J. Eckhardt. In IEEE
24 // Transactions on Computers, Vol. 50, No. 3, 2001.
25 //
26 // "An Implementation of Swing Modulo Scheduling With Extensions for
27 // Superblocks", by T. Lattner, Master's Thesis, University of Illinois at
28 // Urbana-Champaign, 2005.
29 //
30 //
31 // The SMS algorithm consists of three main steps after computing the minimal
32 // initiation interval (MII).
33 // 1) Analyze the dependence graph and compute information about each
34 // instruction in the graph.
35 // 2) Order the nodes (instructions) by priority based upon the heuristics
36 // described in the algorithm.
37 // 3) Attempt to schedule the nodes in the specified order using the MII.
38 //
39 //===----------------------------------------------------------------------===//
40 #ifndef LLVM_LIB_CODEGEN_MACHINEPIPELINER_H
41 #define LLVM_LIB_CODEGEN_MACHINEPIPELINER_H
42 
47 
48 namespace llvm {
49 
50 class NodeSet;
51 class SMSchedule;
52 
53 extern cl::opt<bool> SwpEnableCopyToPhi;
54 
55 /// The main class in the implementation of the target independent
56 /// software pipeliner pass.
58 public:
59  MachineFunction *MF = nullptr;
60  const MachineLoopInfo *MLI = nullptr;
61  const MachineDominatorTree *MDT = nullptr;
63  const TargetInstrInfo *TII = nullptr;
65  bool disabledByPragma = false;
66  unsigned II_setByPragma = 0;
67 
68 #ifndef NDEBUG
69  static int NumTries;
70 #endif
71 
72  /// Cache the target analysis information about the loop.
73  struct LoopInfo {
74  MachineBasicBlock *TBB = nullptr;
75  MachineBasicBlock *FBB = nullptr;
79  };
81 
82  static char ID;
83 
86  }
87 
88  bool runOnMachineFunction(MachineFunction &MF) override;
89 
90  void getAnalysisUsage(AnalysisUsage &AU) const override {
97  }
98 
99 private:
100  void preprocessPhiNodes(MachineBasicBlock &B);
101  bool canPipelineLoop(MachineLoop &L);
102  bool scheduleLoop(MachineLoop &L);
103  bool swingModuloScheduler(MachineLoop &L);
104  void setPragmaPipelineOptions(MachineLoop &L);
105 };
106 
107 /// This class builds the dependence graph for the instructions in a loop,
108 /// and attempts to schedule the instructions using the SMS algorithm.
111  /// The minimum initiation interval between iterations for this schedule.
112  unsigned MII = 0;
113  /// The maximum initiation interval between iterations for this schedule.
114  unsigned MAX_II = 0;
115  /// Set to true if a valid pipelined schedule is found for the loop.
116  bool Scheduled = false;
117  MachineLoop &Loop;
118  LiveIntervals &LIS;
120  unsigned II_setByPragma = 0;
121 
122  /// A toplogical ordering of the SUnits, which is needed for changing
123  /// dependences and iterating over the SUnits.
125 
126  struct NodeInfo {
127  int ASAP = 0;
128  int ALAP = 0;
129  int ZeroLatencyDepth = 0;
130  int ZeroLatencyHeight = 0;
131 
132  NodeInfo() = default;
133  };
134  /// Computed properties for each node in the graph.
135  std::vector<NodeInfo> ScheduleInfo;
136 
137  enum OrderKind { BottomUp = 0, TopDown = 1 };
138  /// Computed node ordering for scheduling.
140 
145 
146  /// Instructions to change when emitting the final schedule.
148 
149  /// We may create a new instruction, so remember it because it
150  /// must be deleted when the pass is finished.
152 
153  /// Ordered list of DAG postprocessing steps.
154  std::vector<std::unique_ptr<ScheduleDAGMutation>> Mutations;
155 
156  /// Helper class to implement Johnson's circuit finding algorithm.
157  class Circuits {
158  std::vector<SUnit> &SUnits;
159  SetVector<SUnit *> Stack;
160  BitVector Blocked;
163  // Node to Index from ScheduleDAGTopologicalSort
164  std::vector<int> *Node2Idx;
165  unsigned NumPaths;
166  static unsigned MaxPaths;
167 
168  public:
169  Circuits(std::vector<SUnit> &SUs, ScheduleDAGTopologicalSort &Topo)
170  : SUnits(SUs), Blocked(SUs.size()), B(SUs.size()), AdjK(SUs.size()) {
171  Node2Idx = new std::vector<int>(SUs.size());
172  unsigned Idx = 0;
173  for (const auto &NodeNum : Topo)
174  Node2Idx->at(NodeNum) = Idx++;
175  }
176 
177  ~Circuits() { delete Node2Idx; }
178 
179  /// Reset the data structures used in the circuit algorithm.
180  void reset() {
181  Stack.clear();
182  Blocked.reset();
183  B.assign(SUnits.size(), SmallPtrSet<SUnit *, 4>());
184  NumPaths = 0;
185  }
186 
187  void createAdjacencyStructure(SwingSchedulerDAG *DAG);
188  bool circuit(int V, int S, NodeSetType &NodeSets, bool HasBackedge = false);
189  void unblock(int U);
190  };
191 
192  struct CopyToPhiMutation : public ScheduleDAGMutation {
193  void apply(ScheduleDAGInstrs *DAG) override;
194  };
195 
196 public:
198  const RegisterClassInfo &rci, unsigned II)
199  : ScheduleDAGInstrs(*P.MF, P.MLI, false), Pass(P), Loop(L), LIS(lis),
200  RegClassInfo(rci), II_setByPragma(II), Topo(SUnits, &ExitSU) {
201  P.MF->getSubtarget().getSMSMutations(Mutations);
202  if (SwpEnableCopyToPhi)
203  Mutations.push_back(llvm::make_unique<CopyToPhiMutation>());
204  }
205 
206  void schedule() override;
207  void finishBlock() override;
208 
209  /// Return true if the loop kernel has been scheduled.
210  bool hasNewSchedule() { return Scheduled; }
211 
212  /// Return the earliest time an instruction may be scheduled.
213  int getASAP(SUnit *Node) { return ScheduleInfo[Node->NodeNum].ASAP; }
214 
215  /// Return the latest time an instruction my be scheduled.
216  int getALAP(SUnit *Node) { return ScheduleInfo[Node->NodeNum].ALAP; }
217 
218  /// The mobility function, which the number of slots in which
219  /// an instruction may be scheduled.
220  int getMOV(SUnit *Node) { return getALAP(Node) - getASAP(Node); }
221 
222  /// The depth, in the dependence graph, for a node.
223  unsigned getDepth(SUnit *Node) { return Node->getDepth(); }
224 
225  /// The maximum unweighted length of a path from an arbitrary node to the
226  /// given node in which each edge has latency 0
228  return ScheduleInfo[Node->NodeNum].ZeroLatencyDepth;
229  }
230 
231  /// The height, in the dependence graph, for a node.
232  unsigned getHeight(SUnit *Node) { return Node->getHeight(); }
233 
234  /// The maximum unweighted length of a path from the given node to an
235  /// arbitrary node in which each edge has latency 0
237  return ScheduleInfo[Node->NodeNum].ZeroLatencyHeight;
238  }
239 
240  /// Return true if the dependence is a back-edge in the data dependence graph.
241  /// Since the DAG doesn't contain cycles, we represent a cycle in the graph
242  /// using an anti dependence from a Phi to an instruction.
243  bool isBackedge(SUnit *Source, const SDep &Dep) {
244  if (Dep.getKind() != SDep::Anti)
245  return false;
246  return Source->getInstr()->isPHI() || Dep.getSUnit()->getInstr()->isPHI();
247  }
248 
249  bool isLoopCarriedDep(SUnit *Source, const SDep &Dep, bool isSucc = true);
250 
251  /// The distance function, which indicates that operation V of iteration I
252  /// depends on operations U of iteration I-distance.
253  unsigned getDistance(SUnit *U, SUnit *V, const SDep &Dep) {
254  // Instructions that feed a Phi have a distance of 1. Computing larger
255  // values for arrays requires data dependence information.
256  if (V->getInstr()->isPHI() && Dep.getKind() == SDep::Anti)
257  return 1;
258  return 0;
259  }
260 
261  void applyInstrChange(MachineInstr *MI, SMSchedule &Schedule);
262 
263  void fixupRegisterOverlaps(std::deque<SUnit *> &Instrs);
264 
265  /// Return the new base register that was stored away for the changed
266  /// instruction.
267  unsigned getInstrBaseReg(SUnit *SU) {
269  InstrChanges.find(SU);
270  if (It != InstrChanges.end())
271  return It->second.first;
272  return 0;
273  }
274 
275  void addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation) {
276  Mutations.push_back(std::move(Mutation));
277  }
278 
279  static bool classof(const ScheduleDAGInstrs *DAG) { return true; }
280 
281 private:
282  void addLoopCarriedDependences(AliasAnalysis *AA);
283  void updatePhiDependences();
284  void changeDependences();
285  unsigned calculateResMII();
286  unsigned calculateRecMII(NodeSetType &RecNodeSets);
287  void findCircuits(NodeSetType &NodeSets);
288  void fuseRecs(NodeSetType &NodeSets);
289  void removeDuplicateNodes(NodeSetType &NodeSets);
290  void computeNodeFunctions(NodeSetType &NodeSets);
291  void registerPressureFilter(NodeSetType &NodeSets);
292  void colocateNodeSets(NodeSetType &NodeSets);
293  void checkNodeSets(NodeSetType &NodeSets);
294  void groupRemainingNodes(NodeSetType &NodeSets);
295  void addConnectedNodes(SUnit *SU, NodeSet &NewSet,
296  SetVector<SUnit *> &NodesAdded);
297  void computeNodeOrder(NodeSetType &NodeSets);
298  void checkValidNodeOrder(const NodeSetType &Circuits) const;
299  bool schedulePipeline(SMSchedule &Schedule);
300  void generatePipelinedLoop(SMSchedule &Schedule);
301  void generateProlog(SMSchedule &Schedule, unsigned LastStage,
302  MachineBasicBlock *KernelBB, ValueMapTy *VRMap,
303  MBBVectorTy &PrologBBs);
304  void generateEpilog(SMSchedule &Schedule, unsigned LastStage,
305  MachineBasicBlock *KernelBB, ValueMapTy *VRMap,
306  MBBVectorTy &EpilogBBs, MBBVectorTy &PrologBBs);
307  void generateExistingPhis(MachineBasicBlock *NewBB, MachineBasicBlock *BB1,
308  MachineBasicBlock *BB2, MachineBasicBlock *KernelBB,
309  SMSchedule &Schedule, ValueMapTy *VRMap,
310  InstrMapTy &InstrMap, unsigned LastStageNum,
311  unsigned CurStageNum, bool IsLast);
312  void generatePhis(MachineBasicBlock *NewBB, MachineBasicBlock *BB1,
313  MachineBasicBlock *BB2, MachineBasicBlock *KernelBB,
314  SMSchedule &Schedule, ValueMapTy *VRMap,
315  InstrMapTy &InstrMap, unsigned LastStageNum,
316  unsigned CurStageNum, bool IsLast);
317  void removeDeadInstructions(MachineBasicBlock *KernelBB,
318  MBBVectorTy &EpilogBBs);
319  void splitLifetimes(MachineBasicBlock *KernelBB, MBBVectorTy &EpilogBBs,
320  SMSchedule &Schedule);
321  void addBranches(MBBVectorTy &PrologBBs, MachineBasicBlock *KernelBB,
322  MBBVectorTy &EpilogBBs, SMSchedule &Schedule,
323  ValueMapTy *VRMap);
324  bool computeDelta(MachineInstr &MI, unsigned &Delta);
325  void updateMemOperands(MachineInstr &NewMI, MachineInstr &OldMI,
326  unsigned Num);
327  MachineInstr *cloneInstr(MachineInstr *OldMI, unsigned CurStageNum,
328  unsigned InstStageNum);
329  MachineInstr *cloneAndChangeInstr(MachineInstr *OldMI, unsigned CurStageNum,
330  unsigned InstStageNum,
331  SMSchedule &Schedule);
332  void updateInstruction(MachineInstr *NewMI, bool LastDef,
333  unsigned CurStageNum, unsigned InstrStageNum,
334  SMSchedule &Schedule, ValueMapTy *VRMap);
335  MachineInstr *findDefInLoop(unsigned Reg);
336  unsigned getPrevMapVal(unsigned StageNum, unsigned PhiStage, unsigned LoopVal,
337  unsigned LoopStage, ValueMapTy *VRMap,
338  MachineBasicBlock *BB);
339  void rewritePhiValues(MachineBasicBlock *NewBB, unsigned StageNum,
340  SMSchedule &Schedule, ValueMapTy *VRMap,
341  InstrMapTy &InstrMap);
342  void rewriteScheduledInstr(MachineBasicBlock *BB, SMSchedule &Schedule,
343  InstrMapTy &InstrMap, unsigned CurStageNum,
344  unsigned PhiNum, MachineInstr *Phi,
345  unsigned OldReg, unsigned NewReg,
346  unsigned PrevReg = 0);
347  bool canUseLastOffsetValue(MachineInstr *MI, unsigned &BasePos,
348  unsigned &OffsetPos, unsigned &NewBase,
349  int64_t &NewOffset);
350  void postprocessDAG();
351  /// Set the Minimum Initiation Interval for this schedule attempt.
352  void setMII(unsigned ResMII, unsigned RecMII);
353  /// Set the Maximum Initiation Interval for this schedule attempt.
354  void setMAX_II();
355 };
356 
357 /// A NodeSet contains a set of SUnit DAG nodes with additional information
358 /// that assigns a priority to the set.
359 class NodeSet {
360  SetVector<SUnit *> Nodes;
361  bool HasRecurrence = false;
362  unsigned RecMII = 0;
363  int MaxMOV = 0;
364  unsigned MaxDepth = 0;
365  unsigned Colocate = 0;
366  SUnit *ExceedPressure = nullptr;
367  unsigned Latency = 0;
368 
369 public:
371 
372  NodeSet() = default;
373  NodeSet(iterator S, iterator E) : Nodes(S, E), HasRecurrence(true) {
374  Latency = 0;
375  for (unsigned i = 0, e = Nodes.size(); i < e; ++i)
376  for (const SDep &Succ : Nodes[i]->Succs)
377  if (Nodes.count(Succ.getSUnit()))
378  Latency += Succ.getLatency();
379  }
380 
381  bool insert(SUnit *SU) { return Nodes.insert(SU); }
382 
383  void insert(iterator S, iterator E) { Nodes.insert(S, E); }
384 
385  template <typename UnaryPredicate> bool remove_if(UnaryPredicate P) {
386  return Nodes.remove_if(P);
387  }
388 
389  unsigned count(SUnit *SU) const { return Nodes.count(SU); }
390 
391  bool hasRecurrence() { return HasRecurrence; };
392 
393  unsigned size() const { return Nodes.size(); }
394 
395  bool empty() const { return Nodes.empty(); }
396 
397  SUnit *getNode(unsigned i) const { return Nodes[i]; };
398 
399  void setRecMII(unsigned mii) { RecMII = mii; };
400 
401  void setColocate(unsigned c) { Colocate = c; };
402 
403  void setExceedPressure(SUnit *SU) { ExceedPressure = SU; }
404 
405  bool isExceedSU(SUnit *SU) { return ExceedPressure == SU; }
406 
407  int compareRecMII(NodeSet &RHS) { return RecMII - RHS.RecMII; }
408 
409  int getRecMII() { return RecMII; }
410 
411  /// Summarize node functions for the entire node set.
413  for (SUnit *SU : *this) {
414  MaxMOV = std::max(MaxMOV, SSD->getMOV(SU));
415  MaxDepth = std::max(MaxDepth, SSD->getDepth(SU));
416  }
417  }
418 
419  unsigned getLatency() { return Latency; }
420 
421  unsigned getMaxDepth() { return MaxDepth; }
422 
423  void clear() {
424  Nodes.clear();
425  RecMII = 0;
426  HasRecurrence = false;
427  MaxMOV = 0;
428  MaxDepth = 0;
429  Colocate = 0;
430  ExceedPressure = nullptr;
431  }
432 
433  operator SetVector<SUnit *> &() { return Nodes; }
434 
435  /// Sort the node sets by importance. First, rank them by recurrence MII,
436  /// then by mobility (least mobile done first), and finally by depth.
437  /// Each node set may contain a colocate value which is used as the first
438  /// tie breaker, if it's set.
439  bool operator>(const NodeSet &RHS) const {
440  if (RecMII == RHS.RecMII) {
441  if (Colocate != 0 && RHS.Colocate != 0 && Colocate != RHS.Colocate)
442  return Colocate < RHS.Colocate;
443  if (MaxMOV == RHS.MaxMOV)
444  return MaxDepth > RHS.MaxDepth;
445  return MaxMOV < RHS.MaxMOV;
446  }
447  return RecMII > RHS.RecMII;
448  }
449 
450  bool operator==(const NodeSet &RHS) const {
451  return RecMII == RHS.RecMII && MaxMOV == RHS.MaxMOV &&
452  MaxDepth == RHS.MaxDepth;
453  }
454 
455  bool operator!=(const NodeSet &RHS) const { return !operator==(RHS); }
456 
457  iterator begin() { return Nodes.begin(); }
458  iterator end() { return Nodes.end(); }
459  void print(raw_ostream &os) const;
460 
461 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
462  LLVM_DUMP_METHOD void dump() const;
463 #endif
464 };
465 
466 /// This class represents the scheduled code. The main data structure is a
467 /// map from scheduled cycle to instructions. During scheduling, the
468 /// data structure explicitly represents all stages/iterations. When
469 /// the algorithm finshes, the schedule is collapsed into a single stage,
470 /// which represents instructions from different loop iterations.
471 ///
472 /// The SMS algorithm allows negative values for cycles, so the first cycle
473 /// in the schedule is the smallest cycle value.
474 class SMSchedule {
475 private:
476  /// Map from execution cycle to instructions.
477  DenseMap<int, std::deque<SUnit *>> ScheduledInstrs;
478 
479  /// Map from instruction to execution cycle.
480  std::map<SUnit *, int> InstrToCycle;
481 
482  /// Map for each register and the max difference between its uses and def.
483  /// The first element in the pair is the max difference in stages. The
484  /// second is true if the register defines a Phi value and loop value is
485  /// scheduled before the Phi.
486  std::map<unsigned, std::pair<unsigned, bool>> RegToStageDiff;
487 
488  /// Keep track of the first cycle value in the schedule. It starts
489  /// as zero, but the algorithm allows negative values.
490  int FirstCycle = 0;
491 
492  /// Keep track of the last cycle value in the schedule.
493  int LastCycle = 0;
494 
495  /// The initiation interval (II) for the schedule.
496  int InitiationInterval = 0;
497 
498  /// Target machine information.
499  const TargetSubtargetInfo &ST;
500 
501  /// Virtual register information.
503 
504  std::unique_ptr<DFAPacketizer> Resources;
505 
506 public:
508  : ST(mf->getSubtarget()), MRI(mf->getRegInfo()),
509  Resources(ST.getInstrInfo()->CreateTargetScheduleState(ST)) {}
510 
511  void reset() {
512  ScheduledInstrs.clear();
513  InstrToCycle.clear();
514  RegToStageDiff.clear();
515  FirstCycle = 0;
516  LastCycle = 0;
517  InitiationInterval = 0;
518  }
519 
520  /// Set the initiation interval for this schedule.
521  void setInitiationInterval(int ii) { InitiationInterval = ii; }
522 
523  /// Return the first cycle in the completed schedule. This
524  /// can be a negative value.
525  int getFirstCycle() const { return FirstCycle; }
526 
527  /// Return the last cycle in the finalized schedule.
528  int getFinalCycle() const { return FirstCycle + InitiationInterval - 1; }
529 
530  /// Return the cycle of the earliest scheduled instruction in the dependence
531  /// chain.
532  int earliestCycleInChain(const SDep &Dep);
533 
534  /// Return the cycle of the latest scheduled instruction in the dependence
535  /// chain.
536  int latestCycleInChain(const SDep &Dep);
537 
538  void computeStart(SUnit *SU, int *MaxEarlyStart, int *MinLateStart,
539  int *MinEnd, int *MaxStart, int II, SwingSchedulerDAG *DAG);
540  bool insert(SUnit *SU, int StartCycle, int EndCycle, int II);
541 
542  /// Iterators for the cycle to instruction map.
544  using const_sched_iterator =
546 
547  /// Return true if the instruction is scheduled at the specified stage.
548  bool isScheduledAtStage(SUnit *SU, unsigned StageNum) {
549  return (stageScheduled(SU) == (int)StageNum);
550  }
551 
552  /// Return the stage for a scheduled instruction. Return -1 if
553  /// the instruction has not been scheduled.
554  int stageScheduled(SUnit *SU) const {
555  std::map<SUnit *, int>::const_iterator it = InstrToCycle.find(SU);
556  if (it == InstrToCycle.end())
557  return -1;
558  return (it->second - FirstCycle) / InitiationInterval;
559  }
560 
561  /// Return the cycle for a scheduled instruction. This function normalizes
562  /// the first cycle to be 0.
563  unsigned cycleScheduled(SUnit *SU) const {
564  std::map<SUnit *, int>::const_iterator it = InstrToCycle.find(SU);
565  assert(it != InstrToCycle.end() && "Instruction hasn't been scheduled.");
566  return (it->second - FirstCycle) % InitiationInterval;
567  }
568 
569  /// Return the maximum stage count needed for this schedule.
570  unsigned getMaxStageCount() {
571  return (LastCycle - FirstCycle) / InitiationInterval;
572  }
573 
574  /// Return the max. number of stages/iterations that can occur between a
575  /// register definition and its uses.
576  unsigned getStagesForReg(int Reg, unsigned CurStage) {
577  std::pair<unsigned, bool> Stages = RegToStageDiff[Reg];
578  if (CurStage > getMaxStageCount() && Stages.first == 0 && Stages.second)
579  return 1;
580  return Stages.first;
581  }
582 
583  /// The number of stages for a Phi is a little different than other
584  /// instructions. The minimum value computed in RegToStageDiff is 1
585  /// because we assume the Phi is needed for at least 1 iteration.
586  /// This is not the case if the loop value is scheduled prior to the
587  /// Phi in the same stage. This function returns the number of stages
588  /// or iterations needed between the Phi definition and any uses.
589  unsigned getStagesForPhi(int Reg) {
590  std::pair<unsigned, bool> Stages = RegToStageDiff[Reg];
591  if (Stages.second)
592  return Stages.first;
593  return Stages.first - 1;
594  }
595 
596  /// Return the instructions that are scheduled at the specified cycle.
597  std::deque<SUnit *> &getInstructions(int cycle) {
598  return ScheduledInstrs[cycle];
599  }
600 
601  bool isValidSchedule(SwingSchedulerDAG *SSD);
602  void finalizeSchedule(SwingSchedulerDAG *SSD);
603  void orderDependence(SwingSchedulerDAG *SSD, SUnit *SU,
604  std::deque<SUnit *> &Insts);
605  bool isLoopCarried(SwingSchedulerDAG *SSD, MachineInstr &Phi);
606  bool isLoopCarriedDefOfUse(SwingSchedulerDAG *SSD, MachineInstr *Def,
607  MachineOperand &MO);
608  void print(raw_ostream &os) const;
609  void dump() const;
610 };
611 
612 } // end namespace llvm
613 
614 #endif // LLVM_LIB_CODEGEN_MACHINEPIPELINER_H
RegisterClassInfo RegClassInfo
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
int getMOV(SUnit *Node)
The mobility function, which the number of slots in which an instruction may be scheduled.
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
unsigned getLatency()
This class represents lattice values for constants.
Definition: AllocatorList.h:23
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:464
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:77
bool empty() const
cl::opt< bool > SwpEnableCopyToPhi
unsigned getHeight(SUnit *Node)
The height, in the dependence graph, for a node.
unsigned getDepth() const
Returns the depth of this node, which is the length of the maximum path up to any node which has no p...
Definition: ScheduleDAG.h:398
unsigned Reg
const MachineLoopInfo * MLI
bool operator==(const NodeSet &RHS) const
Mutate the DAG as a postpass after normal DAG building.
block Block Frequency true
bool isPHI() const
iterator end()
Get an iterator to the end of the SetVector.
Definition: SetVector.h:92
SUnit * getNode(unsigned i) const
A register anti-dependence (aka WAR).
Definition: ScheduleDAG.h:54
int compareRecMII(NodeSet &RHS)
AnalysisUsage & addRequired()
unsigned getMaxDepth()
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
NodeSet(iterator S, iterator E)
void addMutation(std::unique_ptr< ScheduleDAGMutation > Mutation)
void apply(Opt *O, const Mod &M, const Mods &... Ms)
Definition: CommandLine.h:1185
unsigned cycleScheduled(SUnit *SU) const
Return the cycle for a scheduled instruction.
void assign(size_type NumElts, const T &Elt)
Definition: SmallVector.h:415
PowerPC VSX FMA Mutation
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
int getZeroLatencyDepth(SUnit *Node)
The maximum unweighted length of a path from an arbitrary node to the given node in which each edge h...
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...
iterator begin()
Get an iterator to the beginning of the SetVector.
Definition: SetVector.h:82
void dump() const
Definition: Pass.cpp:129
Itinerary data supplied by a subtarget to be used by a target.
SUnit * getSUnit() const
Definition: ScheduleDAG.h:480
iterator begin()
unsigned count(SUnit *SU) const
bool insert(SUnit *SU)
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Definition: SetVector.h:210
unsigned getDepth(SUnit *Node)
The depth, in the dependence graph, for a node.
TargetInstrInfo - Interface to description of machine instruction set.
const MachineDominatorTree * MDT
Scheduling dependency.
Definition: ScheduleDAG.h:49
SwingSchedulerDAG(MachinePipeliner &P, MachineLoop &L, LiveIntervals &lis, const RegisterClassInfo &rci, unsigned II)
#define P(N)
int getFirstCycle() const
Return the first cycle in the completed schedule.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
MachineInstr * getInstr() const
Returns the representative MachineInstr for this SUnit.
Definition: ScheduleDAG.h:373
The main class in the implementation of the target independent software pipeliner pass...
MachineFunction * MF
unsigned const MachineRegisterInfo * MRI
SMSchedule(MachineFunction *mf)
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
virtual void getSMSMutations(std::vector< std::unique_ptr< ScheduleDAGMutation >> &Mutations) const
unsigned getStagesForPhi(int Reg)
The number of stages for a Phi is a little different than other instructions.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
void computeNodeSetInfo(SwingSchedulerDAG *SSD)
Summarize node functions for the entire node set.
static int64_t computeDelta(SectionEntry *A, SectionEntry *B)
int stageScheduled(SUnit *SU) const
Return the stage for a scheduled instruction.
bool runOnMachineFunction(MachineFunction &MF) override
The "main" function for implementing Swing Modulo Scheduling.
Represent the analysis usage information of a pass.
BitVector & reset()
Definition: BitVector.h:438
unsigned getInstrBaseReg(SUnit *SU)
Return the new base register that was stored away for the changed instruction.
const TargetInstrInfo * TII
bool isScheduledAtStage(SUnit *SU, unsigned StageNum)
Return true if the instruction is scheduled at the specified stage.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
const InstrItineraryData * InstrItins
typename vector_type::const_iterator const_iterator
Definition: SetVector.h:49
static bool classof(const ScheduleDAGInstrs *DAG)
void insert(iterator S, iterator E)
const unsigned MaxDepth
SetVector< SUnit * >::const_iterator iterator
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
This class builds the dependence graph for the instructions in a loop, and attempts to schedule the i...
MachineOperand class - Representation of each machine instruction operand.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:839
bool remove_if(UnaryPredicate P)
void setRecMII(unsigned mii)
Pass(PassKind K, char &pid)
Definition: Pass.h:86
void clear()
Completely clear the SetVector.
Definition: SetVector.h:215
This class represents the scheduled code.
unsigned getStagesForReg(int Reg, unsigned CurStage)
Return the max.
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
void initializeMachinePipelinerPass(PassRegistry &)
TargetSubtargetInfo - Generic base class for all target subtargets.
void setExceedPressure(SUnit *SU)
void setColocate(unsigned c)
std::set< NodeId > NodeSet
Definition: RDFGraph.h:513
unsigned getHeight() const
Returns the height of this node, which is the length of the maximum path down to any node which has n...
Definition: ScheduleDAG.h:406
A ScheduleDAG for scheduling lists of MachineInstr.
Representation of each machine instruction.
Definition: MachineInstr.h:63
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:464
int getFinalCycle() const
Return the last cycle in the finalized schedule.
int getALAP(SUnit *Node)
Return the latest time an instruction my be scheduled.
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:72
virtual void print(raw_ostream &OS, const Module *M) const
print - Print out the internal state of the pass.
Definition: Pass.cpp:123
bool operator>(const NodeSet &RHS) const
Sort the node sets by importance.
int getASAP(SUnit *Node)
Return the earliest time an instruction may be scheduled.
Kind getKind() const
Returns an enum value representing the kind of the dependence.
Definition: ScheduleDAG.h:486
void setInitiationInterval(int ii)
Set the initiation interval for this schedule.
bool hasNewSchedule()
Return true if the loop kernel has been scheduled.
unsigned NodeNum
Entry # of node in the node vector.
Definition: ScheduleDAG.h:264
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
unsigned size() const
A vector that has set insertion semantics.
Definition: SetVector.h:40
bool remove_if(UnaryPredicate P)
Remove items from the set vector based on a predicate function.
Definition: SetVector.h:199
bool isExceedSU(SUnit *SU)
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
SmallVector< MachineOperand, 4 > BrCond
IRTranslator LLVM IR MI
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:1966
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object...
Cache the target analysis information about the loop.
bool operator!=(const NodeSet &RHS) const
This class can compute a topological ordering for SUnits and provides methods for dynamically updatin...
Definition: ScheduleDAG.h:689
unsigned getMaxStageCount()
Return the maximum stage count needed for this schedule.
std::deque< SUnit * > & getInstructions(int cycle)
Return the instructions that are scheduled at the specified cycle.
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:242
bool isBackedge(SUnit *Source, const SDep &Dep)
Return true if the dependence is a back-edge in the data dependence graph.
A NodeSet contains a set of SUnit DAG nodes with additional information that assigns a priority to th...
int getZeroLatencyHeight(SUnit *Node)
The maximum unweighted length of a path from the given node to an arbitrary node in which each edge h...