LLVM  15.0.0git
ModuloSchedule.h
Go to the documentation of this file.
1 //===- ModuloSchedule.h - Software pipeline schedule expansion ------------===//
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 // Software pipelining (SWP) is an instruction scheduling technique for loops
10 // that overlaps loop iterations and exploits ILP via compiler transformations.
11 //
12 // There are multiple methods for analyzing a loop and creating a schedule.
13 // An example algorithm is Swing Modulo Scheduling (implemented by the
14 // MachinePipeliner). The details of how a schedule is arrived at are irrelevant
15 // for the task of actually rewriting a loop to adhere to the schedule, which
16 // is what this file does.
17 //
18 // A schedule is, for every instruction in a block, a Cycle and a Stage. Note
19 // that we only support single-block loops, so "block" and "loop" can be used
20 // interchangably.
21 //
22 // The Cycle of an instruction defines a partial order of the instructions in
23 // the remapped loop. Instructions within a cycle must not consume the output
24 // of any instruction in the same cycle. Cycle information is assumed to have
25 // been calculated such that the processor will execute instructions in
26 // lock-step (for example in a VLIW ISA).
27 //
28 // The Stage of an instruction defines the mapping between logical loop
29 // iterations and pipelined loop iterations. An example (unrolled) pipeline
30 // may look something like:
31 //
32 // I0[0] Execute instruction I0 of iteration 0
33 // I1[0], I0[1] Execute I0 of iteration 1 and I1 of iteration 1
34 // I1[1], I0[2]
35 // I1[2], I0[3]
36 //
37 // In the schedule for this unrolled sequence we would say that I0 was scheduled
38 // in stage 0 and I1 in stage 1:
39 //
40 // loop:
41 // [stage 0] x = I0
42 // [stage 1] I1 x (from stage 0)
43 //
44 // And to actually generate valid code we must insert a phi:
45 //
46 // loop:
47 // x' = phi(x)
48 // x = I0
49 // I1 x'
50 //
51 // This is a simple example; the rules for how to generate correct code given
52 // an arbitrary schedule containing loop-carried values are complex.
53 //
54 // Note that these examples only mention the steady-state kernel of the
55 // generated loop; prologs and epilogs must be generated also that prime and
56 // flush the pipeline. Doing so is nontrivial.
57 //
58 //===----------------------------------------------------------------------===//
59 
60 #ifndef LLVM_CODEGEN_MODULOSCHEDULE_H
61 #define LLVM_CODEGEN_MODULOSCHEDULE_H
62 
67 #include <deque>
68 #include <vector>
69 
70 namespace llvm {
71 class MachineBasicBlock;
72 class MachineLoop;
73 class MachineRegisterInfo;
74 class MachineInstr;
75 class LiveIntervals;
76 
77 /// Represents a schedule for a single-block loop. For every instruction we
78 /// maintain a Cycle and Stage.
80 private:
81  /// The block containing the loop instructions.
83 
84  /// The instructions to be generated, in total order. Cycle provides a partial
85  /// order; the total order within cycles has been decided by the schedule
86  /// producer.
87  std::vector<MachineInstr *> ScheduledInstrs;
88 
89  /// The cycle for each instruction.
91 
92  /// The stage for each instruction.
94 
95  /// The number of stages in this schedule (Max(Stage) + 1).
96  int NumStages;
97 
98 public:
99  /// Create a new ModuloSchedule.
100  /// \arg ScheduledInstrs The new loop instructions, in total resequenced
101  /// order.
102  /// \arg Cycle Cycle index for all instructions in ScheduledInstrs. Cycle does
103  /// not need to start at zero. ScheduledInstrs must be partially ordered by
104  /// Cycle.
105  /// \arg Stage Stage index for all instructions in ScheduleInstrs.
107  std::vector<MachineInstr *> ScheduledInstrs,
110  : Loop(Loop), ScheduledInstrs(ScheduledInstrs), Cycle(std::move(Cycle)),
111  Stage(std::move(Stage)) {
112  NumStages = 0;
113  for (auto &KV : this->Stage)
114  NumStages = std::max(NumStages, KV.second);
115  ++NumStages;
116  }
117 
118  /// Return the single-block loop being scheduled.
119  MachineLoop *getLoop() const { return Loop; }
120 
121  /// Return the number of stages contained in this schedule, which is the
122  /// largest stage index + 1.
123  int getNumStages() const { return NumStages; }
124 
125  /// Return the first cycle in the schedule, which is the cycle index of the
126  /// first instruction.
127  int getFirstCycle() { return Cycle[ScheduledInstrs.front()]; }
128 
129  /// Return the final cycle in the schedule, which is the cycle index of the
130  /// last instruction.
131  int getFinalCycle() { return Cycle[ScheduledInstrs.back()]; }
132 
133  /// Return the stage that MI is scheduled in, or -1.
135  auto I = Stage.find(MI);
136  return I == Stage.end() ? -1 : I->second;
137  }
138 
139  /// Return the cycle that MI is scheduled at, or -1.
141  auto I = Cycle.find(MI);
142  return I == Cycle.end() ? -1 : I->second;
143  }
144 
145  /// Set the stage of a newly created instruction.
146  void setStage(MachineInstr *MI, int MIStage) {
147  assert(Stage.count(MI) == 0);
148  Stage[MI] = MIStage;
149  }
150 
151  /// Return the rescheduled instructions in order.
152  ArrayRef<MachineInstr *> getInstructions() { return ScheduledInstrs; }
153 
154  void dump() { print(dbgs()); }
155  void print(raw_ostream &OS);
156 };
157 
158 /// The ModuloScheduleExpander takes a ModuloSchedule and expands it in-place,
159 /// rewriting the old loop and inserting prologs and epilogs as required.
161 public:
163 
164 private:
168 
169  ModuloSchedule &Schedule;
170  MachineFunction &MF;
171  const TargetSubtargetInfo &ST;
172  MachineRegisterInfo &MRI;
173  const TargetInstrInfo *TII;
174  LiveIntervals &LIS;
175 
176  MachineBasicBlock *BB;
177  MachineBasicBlock *Preheader;
178  MachineBasicBlock *NewKernel = nullptr;
179  std::unique_ptr<TargetInstrInfo::PipelinerLoopInfo> LoopInfo;
180 
181  /// Map for each register and the max difference between its uses and def.
182  /// The first element in the pair is the max difference in stages. The
183  /// second is true if the register defines a Phi value and loop value is
184  /// scheduled before the Phi.
185  std::map<unsigned, std::pair<unsigned, bool>> RegToStageDiff;
186 
187  /// Instructions to change when emitting the final schedule.
188  InstrChangesTy InstrChanges;
189 
190  void generatePipelinedLoop();
191  void generateProlog(unsigned LastStage, MachineBasicBlock *KernelBB,
192  ValueMapTy *VRMap, MBBVectorTy &PrologBBs);
193  void generateEpilog(unsigned LastStage, MachineBasicBlock *KernelBB,
194  MachineBasicBlock *OrigBB, ValueMapTy *VRMap,
195  MBBVectorTy &EpilogBBs, MBBVectorTy &PrologBBs);
196  void generateExistingPhis(MachineBasicBlock *NewBB, MachineBasicBlock *BB1,
197  MachineBasicBlock *BB2, MachineBasicBlock *KernelBB,
198  ValueMapTy *VRMap, InstrMapTy &InstrMap,
199  unsigned LastStageNum, unsigned CurStageNum,
200  bool IsLast);
201  void generatePhis(MachineBasicBlock *NewBB, MachineBasicBlock *BB1,
202  MachineBasicBlock *BB2, MachineBasicBlock *KernelBB,
203  ValueMapTy *VRMap, InstrMapTy &InstrMap,
204  unsigned LastStageNum, unsigned CurStageNum, bool IsLast);
205  void removeDeadInstructions(MachineBasicBlock *KernelBB,
206  MBBVectorTy &EpilogBBs);
207  void splitLifetimes(MachineBasicBlock *KernelBB, MBBVectorTy &EpilogBBs);
208  void addBranches(MachineBasicBlock &PreheaderBB, MBBVectorTy &PrologBBs,
209  MachineBasicBlock *KernelBB, MBBVectorTy &EpilogBBs,
210  ValueMapTy *VRMap);
211  bool computeDelta(MachineInstr &MI, unsigned &Delta);
212  void updateMemOperands(MachineInstr &NewMI, MachineInstr &OldMI,
213  unsigned Num);
214  MachineInstr *cloneInstr(MachineInstr *OldMI, unsigned CurStageNum,
215  unsigned InstStageNum);
216  MachineInstr *cloneAndChangeInstr(MachineInstr *OldMI, unsigned CurStageNum,
217  unsigned InstStageNum);
218  void updateInstruction(MachineInstr *NewMI, bool LastDef,
219  unsigned CurStageNum, unsigned InstrStageNum,
220  ValueMapTy *VRMap);
221  MachineInstr *findDefInLoop(unsigned Reg);
222  unsigned getPrevMapVal(unsigned StageNum, unsigned PhiStage, unsigned LoopVal,
223  unsigned LoopStage, ValueMapTy *VRMap,
224  MachineBasicBlock *BB);
225  void rewritePhiValues(MachineBasicBlock *NewBB, unsigned StageNum,
226  ValueMapTy *VRMap, InstrMapTy &InstrMap);
227  void rewriteScheduledInstr(MachineBasicBlock *BB, InstrMapTy &InstrMap,
228  unsigned CurStageNum, unsigned PhiNum,
229  MachineInstr *Phi, unsigned OldReg,
230  unsigned NewReg, unsigned PrevReg = 0);
231  bool isLoopCarried(MachineInstr &Phi);
232 
233  /// Return the max. number of stages/iterations that can occur between a
234  /// register definition and its uses.
235  unsigned getStagesForReg(int Reg, unsigned CurStage) {
236  std::pair<unsigned, bool> Stages = RegToStageDiff[Reg];
237  if ((int)CurStage > Schedule.getNumStages() - 1 && Stages.first == 0 &&
238  Stages.second)
239  return 1;
240  return Stages.first;
241  }
242 
243  /// The number of stages for a Phi is a little different than other
244  /// instructions. The minimum value computed in RegToStageDiff is 1
245  /// because we assume the Phi is needed for at least 1 iteration.
246  /// This is not the case if the loop value is scheduled prior to the
247  /// Phi in the same stage. This function returns the number of stages
248  /// or iterations needed between the Phi definition and any uses.
249  unsigned getStagesForPhi(int Reg) {
250  std::pair<unsigned, bool> Stages = RegToStageDiff[Reg];
251  if (Stages.second)
252  return Stages.first;
253  return Stages.first - 1;
254  }
255 
256 public:
257  /// Create a new ModuloScheduleExpander.
258  /// \arg InstrChanges Modifications to make to instructions with memory
259  /// operands.
260  /// FIXME: InstrChanges is opaque and is an implementation detail of an
261  /// optimization in MachinePipeliner that crosses abstraction boundaries.
263  LiveIntervals &LIS, InstrChangesTy InstrChanges)
264  : Schedule(S), MF(MF), ST(MF.getSubtarget()), MRI(MF.getRegInfo()),
265  TII(ST.getInstrInfo()), LIS(LIS),
266  InstrChanges(std::move(InstrChanges)) {}
267 
268  /// Performs the actual expansion.
269  void expand();
270  /// Performs final cleanup after expansion.
271  void cleanup();
272 
273  /// Returns the newly rewritten kernel block, or nullptr if this was
274  /// optimized away.
275  MachineBasicBlock *getRewrittenKernel() { return NewKernel; }
276 };
277 
278 /// A reimplementation of ModuloScheduleExpander. It works by generating a
279 /// standalone kernel loop and peeling out the prologs and epilogs.
281 public:
284  : Schedule(S), MF(MF), ST(MF.getSubtarget()), MRI(MF.getRegInfo()),
285  TII(ST.getInstrInfo()), LIS(LIS) {}
286 
287  void expand();
288 
289  /// Runs ModuloScheduleExpander and treats it as a golden input to validate
290  /// aspects of the code generated by PeelingModuloScheduleExpander.
292 
293 protected:
300 
301  /// The original loop block that gets rewritten in-place.
303  /// The original loop preheader.
305  /// All prolog and epilog blocks.
307  /// For every block, the stages that are produced.
309  /// For every block, the stages that are available. A stage can be available
310  /// but not produced (in the epilog) or produced but not available (in the
311  /// prolog).
313  /// When peeling the epilogue keep track of the distance between the phi
314  /// nodes and the kernel.
316 
317  /// CanonicalMIs and BlockMIs form a bidirectional map between any of the
318  /// loop kernel clones.
322 
323  /// State passed from peelKernel to peelPrologAndEpilogs().
324  std::deque<MachineBasicBlock *> PeeledFront, PeeledBack;
325  /// Illegal phis that need to be deleted once we re-link stages.
327 
328  /// Converts BB from the original loop body to the rewritten, pipelined
329  /// steady-state.
330  void rewriteKernel();
331 
332  /// Peels one iteration of the rewritten kernel (BB) in the specified
333  /// direction.
335  // Delete instructions whose stage is less than MinStage in the given basic
336  // block.
337  void filterInstructions(MachineBasicBlock *MB, int MinStage);
338  // Move instructions of the given stage from sourceBB to DestBB. Remap the phi
339  // instructions to keep a valid IR.
341  MachineBasicBlock *SourceBB, unsigned Stage);
342  /// Peel the kernel forwards and backwards to produce prologs and epilogs,
343  /// and stitch them together.
344  void peelPrologAndEpilogs();
345  /// All prolog and epilog blocks are clones of the kernel, so any produced
346  /// register in one block has an corollary in all other blocks.
348  /// Change all users of MI, if MI is predicated out
349  /// (LiveStages[MI->getParent()] == false).
351  /// Insert branches between prologs, kernel and epilogs.
352  void fixupBranches();
353  /// Create a poor-man's LCSSA by cloning only the PHIs from the kernel block
354  /// to a block dominated by all prologs and epilogs. This allows us to treat
355  /// the loop exiting block as any other kernel clone.
357  /// Helper to get the stage of an instruction in the schedule.
358  unsigned getStage(MachineInstr *MI) {
359  if (CanonicalMIs.count(MI))
360  MI = CanonicalMIs[MI];
361  return Schedule.getStage(MI);
362  }
363  /// Helper function to find the right canonical register for a phi instruction
364  /// coming from a peeled out prologue.
366  /// Target loop info before kernel peeling.
367  std::unique_ptr<TargetInstrInfo::PipelinerLoopInfo> LoopInfo;
368 };
369 
370 /// Expander that simply annotates each scheduled instruction with a post-instr
371 /// symbol that can be consumed by the ModuloScheduleTest pass.
372 ///
373 /// The post-instr symbol is a way of annotating an instruction that can be
374 /// roundtripped in MIR. The syntax is:
375 /// MYINST %0, post-instr-symbol <mcsymbol Stage-1_Cycle-5>
377  MachineFunction &MF;
378  ModuloSchedule &S;
379 
380 public:
382  : MF(MF), S(S) {}
383 
384  /// Performs the annotation.
385  void annotate();
386 };
387 
388 } // end namespace llvm
389 
390 #endif // LLVM_CODEGEN_MODULOSCHEDULE_H
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:104
llvm::PeelingModuloScheduleExpander::LoopInfo
std::unique_ptr< TargetInstrInfo::PipelinerLoopInfo > LoopInfo
Target loop info before kernel peeling.
Definition: ModuloSchedule.h:367
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::PeelingModuloScheduleExpander::rewriteKernel
void rewriteKernel()
Converts BB from the original loop body to the rewritten, pipelined steady-state.
Definition: ModuloSchedule.cpp:1980
llvm::ModuloScheduleExpander::cleanup
void cleanup()
Performs final cleanup after expansion.
Definition: ModuloSchedule.cpp:176
llvm::ModuloSchedule
Represents a schedule for a single-block loop.
Definition: ModuloSchedule.h:79
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:50
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:546
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
llvm::X86Disassembler::Reg
Reg
All possible values of the reg field in the ModR/M byte.
Definition: X86DisassemblerDecoder.h:462
llvm::ModuloSchedule::ModuloSchedule
ModuloSchedule(MachineFunction &MF, MachineLoop *Loop, std::vector< MachineInstr * > ScheduledInstrs, DenseMap< MachineInstr *, int > Cycle, DenseMap< MachineInstr *, int > Stage)
Create a new ModuloSchedule.
Definition: ModuloSchedule.h:106
MachineLoopUtils.h
TargetInstrInfo.h
llvm::PeelingModuloScheduleExpander::Epilogs
SmallVector< MachineBasicBlock *, 4 > Epilogs
Definition: ModuloSchedule.h:306
llvm::PeelingModuloScheduleExpander::getStage
unsigned getStage(MachineInstr *MI)
Helper to get the stage of an instruction in the schedule.
Definition: ModuloSchedule.h:358
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::count
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:147
llvm::max
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:337
llvm::PeelingModuloScheduleExpander::TII
const TargetInstrInfo * TII
Definition: ModuloSchedule.h:298
llvm::PeelingModuloScheduleExpander
A reimplementation of ModuloScheduleExpander.
Definition: ModuloSchedule.h:280
llvm::ModuloScheduleExpander::expand
void expand()
Performs the actual expansion.
Definition: ModuloSchedule.cpp:67
llvm::PeelingModuloScheduleExpander::PeeledFront
std::deque< MachineBasicBlock * > PeeledFront
State passed from peelKernel to peelPrologAndEpilogs().
Definition: ModuloSchedule.h:324
llvm::PeelingModuloScheduleExpander::moveStageBetweenBlocks
void moveStageBetweenBlocks(MachineBasicBlock *DestBB, MachineBasicBlock *SourceBB, unsigned Stage)
Definition: ModuloSchedule.cpp:1620
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::ModuloSchedule::dump
void dump()
Definition: ModuloSchedule.h:154
llvm::PeelingModuloScheduleExpander::AvailableStages
DenseMap< MachineBasicBlock *, BitVector > AvailableStages
For every block, the stages that are available.
Definition: ModuloSchedule.h:312
llvm::TargetInstrInfo
TargetInstrInfo - Interface to description of machine instruction set.
Definition: TargetInstrInfo.h:97
llvm::PeelingModuloScheduleExpander::Schedule
ModuloSchedule & Schedule
Definition: ModuloSchedule.h:294
llvm::PeelingModuloScheduleExpander::PeeledBack
std::deque< MachineBasicBlock * > PeeledBack
Definition: ModuloSchedule.h:324
llvm::PeelingModuloScheduleExpander::PhiNodeLoopIteration
DenseMap< MachineInstr *, unsigned > PhiNodeLoopIteration
When peeling the epilogue keep track of the distance between the phi nodes and the kernel.
Definition: ModuloSchedule.h:315
llvm::ModuloScheduleExpander::ModuloScheduleExpander
ModuloScheduleExpander(MachineFunction &MF, ModuloSchedule &S, LiveIntervals &LIS, InstrChangesTy InstrChanges)
Create a new ModuloScheduleExpander.
Definition: ModuloSchedule.h:262
llvm::PeelingModuloScheduleExpander::BlockMIs
DenseMap< std::pair< MachineBasicBlock *, MachineInstr * >, MachineInstr * > BlockMIs
Definition: ModuloSchedule.h:321
llvm::PeelingModuloScheduleExpander::BB
MachineBasicBlock * BB
The original loop block that gets rewritten in-place.
Definition: ModuloSchedule.h:302
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:125
llvm::PeelingModuloScheduleExpander::Prologs
SmallVector< MachineBasicBlock *, 4 > Prologs
All prolog and epilog blocks.
Definition: ModuloSchedule.h:306
llvm::GenericCycle
A possibly irreducible generalization of a Loop.
Definition: GenericCycleInfo.h:48
llvm::PeelingModuloScheduleExpander::filterInstructions
void filterInstructions(MachineBasicBlock *MB, int MinStage)
Definition: ModuloSchedule.cpp:1591
llvm::ModuloSchedule::setStage
void setStage(MachineInstr *MI, int MIStage)
Set the stage of a newly created instruction.
Definition: ModuloSchedule.h:146
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:54
llvm::ModuloSchedule::getInstructions
ArrayRef< MachineInstr * > getInstructions()
Return the rescheduled instructions in order.
Definition: ModuloSchedule.h:152
llvm::PeelingModuloScheduleExpander::peelKernel
MachineBasicBlock * peelKernel(LoopPeelDirection LPD)
Peels one iteration of the rewritten kernel (BB) in the specified direction.
Definition: ModuloSchedule.cpp:1575
llvm::ModuloSchedule::getFinalCycle
int getFinalCycle()
Return the final cycle in the schedule, which is the cycle index of the last instruction.
Definition: ModuloSchedule.h:131
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:94
llvm::PeelingModuloScheduleExpander::Preheader
MachineBasicBlock * Preheader
The original loop preheader.
Definition: ModuloSchedule.h:304
llvm::PeelingModuloScheduleExpander::fixupBranches
void fixupBranches()
Insert branches between prologs, kernel and epilogs.
Definition: ModuloSchedule.cpp:1933
llvm::PeelingModuloScheduleExpander::ST
const TargetSubtargetInfo & ST
Definition: ModuloSchedule.h:296
llvm::ModuloScheduleExpander::getRewrittenKernel
MachineBasicBlock * getRewrittenKernel()
Returns the newly rewritten kernel block, or nullptr if this was optimized away.
Definition: ModuloSchedule.h:275
llvm::MachineLoop
Definition: MachineLoopInfo.h:44
llvm::PeelingModuloScheduleExpander::rewriteUsesOf
void rewriteUsesOf(MachineInstr *MI)
Change all users of MI, if MI is predicated out (LiveStages[MI->getParent()] == false).
Definition: ModuloSchedule.cpp:1890
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:66
llvm::ModuloScheduleTestAnnotater::annotate
void annotate()
Performs the annotation.
Definition: ModuloSchedule.cpp:2184
llvm::DenseMap
Definition: DenseMap.h:716
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::ModuloSchedule::getFirstCycle
int getFirstCycle()
Return the first cycle in the schedule, which is the cycle index of the first instruction.
Definition: ModuloSchedule.h:127
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:152
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::move
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1675
llvm::PeelingModuloScheduleExpander::CreateLCSSAExitingBlock
MachineBasicBlock * CreateLCSSAExitingBlock()
Create a poor-man's LCSSA by cloning only the PHIs from the kernel block to a block dominated by all ...
Definition: ModuloSchedule.cpp:1839
llvm::LoopPeelDirection
LoopPeelDirection
Definition: MachineLoopUtils.h:17
llvm::MachineFunction
Definition: MachineFunction.h:257
llvm::PeelingModuloScheduleExpander::getEquivalentRegisterIn
Register getEquivalentRegisterIn(Register Reg, MachineBasicBlock *BB)
All prolog and epilog blocks are clones of the kernel, so any produced register in one block has an c...
Definition: ModuloSchedule.cpp:1883
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::ModuloScheduleTestAnnotater
Expander that simply annotates each scheduled instruction with a post-instr symbol that can be consum...
Definition: ModuloSchedule.h:376
llvm::LoopInfo
Definition: LoopInfo.h:1102
llvm::PeelingModuloScheduleExpander::expand
void expand()
Definition: ModuloSchedule.cpp:1985
TargetSubtargetInfo.h
S
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
Definition: README.txt:210
llvm::PeelingModuloScheduleExpander::PeelingModuloScheduleExpander
PeelingModuloScheduleExpander(MachineFunction &MF, ModuloSchedule &S, LiveIntervals *LIS)
Definition: ModuloSchedule.h:282
llvm::TargetSubtargetInfo
TargetSubtargetInfo - Generic base class for all target subtargets.
Definition: TargetSubtargetInfo.h:60
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
llvm::PeelingModuloScheduleExpander::LIS
LiveIntervals * LIS
Definition: ModuloSchedule.h:299
std
Definition: BitVector.h:851
llvm::PeelingModuloScheduleExpander::MRI
MachineRegisterInfo & MRI
Definition: ModuloSchedule.h:297
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::end
iterator end()
Definition: DenseMap.h:84
llvm::ModuloSchedule::getCycle
int getCycle(MachineInstr *MI)
Return the cycle that MI is scheduled at, or -1.
Definition: ModuloSchedule.h:140
llvm::ModuloSchedule::getNumStages
int getNumStages() const
Return the number of stages contained in this schedule, which is the largest stage index + 1.
Definition: ModuloSchedule.h:123
llvm::PeelingModuloScheduleExpander::IllegalPhisToDelete
SmallVector< MachineInstr *, 4 > IllegalPhisToDelete
Illegal phis that need to be deleted once we re-link stages.
Definition: ModuloSchedule.h:326
llvm::ModuloSchedule::getLoop
MachineLoop * getLoop() const
Return the single-block loop being scheduled.
Definition: ModuloSchedule.h:119
llvm::LiveIntervals
Definition: LiveIntervals.h:54
llvm::PeelingModuloScheduleExpander::peelPrologAndEpilogs
void peelPrologAndEpilogs()
Peel the kernel forwards and backwards to produce prologs and epilogs, and stitch them together.
Definition: ModuloSchedule.cpp:1722
llvm::PeelingModuloScheduleExpander::validateAgainstModuloScheduleExpander
void validateAgainstModuloScheduleExpander()
Runs ModuloScheduleExpander and treats it as a golden input to validate aspects of the code generated...
Definition: ModuloSchedule.cpp:1997
llvm::ModuloSchedule::print
void print(raw_ostream &OS)
Definition: ModuloSchedule.cpp:25
llvm::PeelingModuloScheduleExpander::LiveStages
DenseMap< MachineBasicBlock *, BitVector > LiveStages
For every block, the stages that are produced.
Definition: ModuloSchedule.h:308
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
llvm::PeelingModuloScheduleExpander::MF
MachineFunction & MF
Definition: ModuloSchedule.h:295
llvm::ModuloScheduleExpander
The ModuloScheduleExpander takes a ModuloSchedule and expands it in-place, rewriting the old loop and...
Definition: ModuloSchedule.h:160
llvm::ModuloSchedule::getStage
int getStage(MachineInstr *MI)
Return the stage that MI is scheduled in, or -1.
Definition: ModuloSchedule.h:134
MachineFunction.h
llvm::PeelingModuloScheduleExpander::getPhiCanonicalReg
Register getPhiCanonicalReg(MachineInstr *CanonicalPhi, MachineInstr *Phi)
Helper function to find the right canonical register for a phi instruction coming from a peeled out p...
Definition: ModuloSchedule.cpp:1705
llvm::ModuloScheduleTestAnnotater::ModuloScheduleTestAnnotater
ModuloScheduleTestAnnotater(MachineFunction &MF, ModuloSchedule &S)
Definition: ModuloSchedule.h:381
llvm::PeelingModuloScheduleExpander::CanonicalMIs
DenseMap< MachineInstr *, MachineInstr * > CanonicalMIs
CanonicalMIs and BlockMIs form a bidirectional map between any of the loop kernel clones.
Definition: ModuloSchedule.h:319