LLVM  13.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 
68 #include <deque>
69 #include <vector>
70 
71 namespace llvm {
72 class MachineBasicBlock;
73 class MachineInstr;
74 class LiveIntervals;
75 
76 /// Represents a schedule for a single-block loop. For every instruction we
77 /// maintain a Cycle and Stage.
79 private:
80  /// The block containing the loop instructions.
82 
83  /// The instructions to be generated, in total order. Cycle provides a partial
84  /// order; the total order within cycles has been decided by the schedule
85  /// producer.
86  std::vector<MachineInstr *> ScheduledInstrs;
87 
88  /// The cycle for each instruction.
90 
91  /// The stage for each instruction.
93 
94  /// The number of stages in this schedule (Max(Stage) + 1).
95  int NumStages;
96 
97 public:
98  /// Create a new ModuloSchedule.
99  /// \arg ScheduledInstrs The new loop instructions, in total resequenced
100  /// order.
101  /// \arg Cycle Cycle index for all instructions in ScheduledInstrs. Cycle does
102  /// not need to start at zero. ScheduledInstrs must be partially ordered by
103  /// Cycle.
104  /// \arg Stage Stage index for all instructions in ScheduleInstrs.
106  std::vector<MachineInstr *> ScheduledInstrs,
109  : Loop(Loop), ScheduledInstrs(ScheduledInstrs), Cycle(std::move(Cycle)),
110  Stage(std::move(Stage)) {
111  NumStages = 0;
112  for (auto &KV : this->Stage)
113  NumStages = std::max(NumStages, KV.second);
114  ++NumStages;
115  }
116 
117  /// Return the single-block loop being scheduled.
118  MachineLoop *getLoop() const { return Loop; }
119 
120  /// Return the number of stages contained in this schedule, which is the
121  /// largest stage index + 1.
122  int getNumStages() const { return NumStages; }
123 
124  /// Return the first cycle in the schedule, which is the cycle index of the
125  /// first instruction.
126  int getFirstCycle() { return Cycle[ScheduledInstrs.front()]; }
127 
128  /// Return the final cycle in the schedule, which is the cycle index of the
129  /// last instruction.
130  int getFinalCycle() { return Cycle[ScheduledInstrs.back()]; }
131 
132  /// Return the stage that MI is scheduled in, or -1.
134  auto I = Stage.find(MI);
135  return I == Stage.end() ? -1 : I->second;
136  }
137 
138  /// Return the cycle that MI is scheduled at, or -1.
140  auto I = Cycle.find(MI);
141  return I == Cycle.end() ? -1 : I->second;
142  }
143 
144  /// Set the stage of a newly created instruction.
145  void setStage(MachineInstr *MI, int MIStage) {
146  assert(Stage.count(MI) == 0);
147  Stage[MI] = MIStage;
148  }
149 
150  /// Return the rescheduled instructions in order.
151  ArrayRef<MachineInstr *> getInstructions() { return ScheduledInstrs; }
152 
153  void dump() { print(dbgs()); }
154  void print(raw_ostream &OS);
155 };
156 
157 /// The ModuloScheduleExpander takes a ModuloSchedule and expands it in-place,
158 /// rewriting the old loop and inserting prologs and epilogs as required.
160 public:
162 
163 private:
167 
168  ModuloSchedule &Schedule;
169  MachineFunction &MF;
170  const TargetSubtargetInfo &ST;
171  MachineRegisterInfo &MRI;
172  const TargetInstrInfo *TII;
173  LiveIntervals &LIS;
174 
175  MachineBasicBlock *BB;
176  MachineBasicBlock *Preheader;
177  MachineBasicBlock *NewKernel = nullptr;
178  std::unique_ptr<TargetInstrInfo::PipelinerLoopInfo> LoopInfo;
179 
180  /// Map for each register and the max difference between its uses and def.
181  /// The first element in the pair is the max difference in stages. The
182  /// second is true if the register defines a Phi value and loop value is
183  /// scheduled before the Phi.
184  std::map<unsigned, std::pair<unsigned, bool>> RegToStageDiff;
185 
186  /// Instructions to change when emitting the final schedule.
187  InstrChangesTy InstrChanges;
188 
189  void generatePipelinedLoop();
190  void generateProlog(unsigned LastStage, MachineBasicBlock *KernelBB,
191  ValueMapTy *VRMap, MBBVectorTy &PrologBBs);
192  void generateEpilog(unsigned LastStage, MachineBasicBlock *KernelBB,
193  ValueMapTy *VRMap, MBBVectorTy &EpilogBBs,
194  MBBVectorTy &PrologBBs);
195  void generateExistingPhis(MachineBasicBlock *NewBB, MachineBasicBlock *BB1,
196  MachineBasicBlock *BB2, MachineBasicBlock *KernelBB,
197  ValueMapTy *VRMap, InstrMapTy &InstrMap,
198  unsigned LastStageNum, unsigned CurStageNum,
199  bool IsLast);
200  void generatePhis(MachineBasicBlock *NewBB, MachineBasicBlock *BB1,
201  MachineBasicBlock *BB2, MachineBasicBlock *KernelBB,
202  ValueMapTy *VRMap, InstrMapTy &InstrMap,
203  unsigned LastStageNum, unsigned CurStageNum, bool IsLast);
204  void removeDeadInstructions(MachineBasicBlock *KernelBB,
205  MBBVectorTy &EpilogBBs);
206  void splitLifetimes(MachineBasicBlock *KernelBB, MBBVectorTy &EpilogBBs);
207  void addBranches(MachineBasicBlock &PreheaderBB, MBBVectorTy &PrologBBs,
208  MachineBasicBlock *KernelBB, MBBVectorTy &EpilogBBs,
209  ValueMapTy *VRMap);
210  bool computeDelta(MachineInstr &MI, unsigned &Delta);
211  void updateMemOperands(MachineInstr &NewMI, MachineInstr &OldMI,
212  unsigned Num);
213  MachineInstr *cloneInstr(MachineInstr *OldMI, unsigned CurStageNum,
214  unsigned InstStageNum);
215  MachineInstr *cloneAndChangeInstr(MachineInstr *OldMI, unsigned CurStageNum,
216  unsigned InstStageNum);
217  void updateInstruction(MachineInstr *NewMI, bool LastDef,
218  unsigned CurStageNum, unsigned InstrStageNum,
219  ValueMapTy *VRMap);
220  MachineInstr *findDefInLoop(unsigned Reg);
221  unsigned getPrevMapVal(unsigned StageNum, unsigned PhiStage, unsigned LoopVal,
222  unsigned LoopStage, ValueMapTy *VRMap,
223  MachineBasicBlock *BB);
224  void rewritePhiValues(MachineBasicBlock *NewBB, unsigned StageNum,
225  ValueMapTy *VRMap, InstrMapTy &InstrMap);
226  void rewriteScheduledInstr(MachineBasicBlock *BB, InstrMapTy &InstrMap,
227  unsigned CurStageNum, unsigned PhiNum,
228  MachineInstr *Phi, unsigned OldReg,
229  unsigned NewReg, unsigned PrevReg = 0);
230  bool isLoopCarried(MachineInstr &Phi);
231 
232  /// Return the max. number of stages/iterations that can occur between a
233  /// register definition and its uses.
234  unsigned getStagesForReg(int Reg, unsigned CurStage) {
235  std::pair<unsigned, bool> Stages = RegToStageDiff[Reg];
236  if ((int)CurStage > Schedule.getNumStages() - 1 && Stages.first == 0 &&
237  Stages.second)
238  return 1;
239  return Stages.first;
240  }
241 
242  /// The number of stages for a Phi is a little different than other
243  /// instructions. The minimum value computed in RegToStageDiff is 1
244  /// because we assume the Phi is needed for at least 1 iteration.
245  /// This is not the case if the loop value is scheduled prior to the
246  /// Phi in the same stage. This function returns the number of stages
247  /// or iterations needed between the Phi definition and any uses.
248  unsigned getStagesForPhi(int Reg) {
249  std::pair<unsigned, bool> Stages = RegToStageDiff[Reg];
250  if (Stages.second)
251  return Stages.first;
252  return Stages.first - 1;
253  }
254 
255 public:
256  /// Create a new ModuloScheduleExpander.
257  /// \arg InstrChanges Modifications to make to instructions with memory
258  /// operands.
259  /// FIXME: InstrChanges is opaque and is an implementation detail of an
260  /// optimization in MachinePipeliner that crosses abstraction boundaries.
262  LiveIntervals &LIS, InstrChangesTy InstrChanges)
263  : Schedule(S), MF(MF), ST(MF.getSubtarget()), MRI(MF.getRegInfo()),
264  TII(ST.getInstrInfo()), LIS(LIS),
265  InstrChanges(std::move(InstrChanges)) {}
266 
267  /// Performs the actual expansion.
268  void expand();
269  /// Performs final cleanup after expansion.
270  void cleanup();
271 
272  /// Returns the newly rewritten kernel block, or nullptr if this was
273  /// optimized away.
274  MachineBasicBlock *getRewrittenKernel() { return NewKernel; }
275 };
276 
277 /// A reimplementation of ModuloScheduleExpander. It works by generating a
278 /// standalone kernel loop and peeling out the prologs and epilogs.
280 public:
283  : Schedule(S), MF(MF), ST(MF.getSubtarget()), MRI(MF.getRegInfo()),
284  TII(ST.getInstrInfo()), LIS(LIS) {}
285 
286  void expand();
287 
288  /// Runs ModuloScheduleExpander and treats it as a golden input to validate
289  /// aspects of the code generated by PeelingModuloScheduleExpander.
291 
292 protected:
299 
300  /// The original loop block that gets rewritten in-place.
302  /// The original loop preheader.
304  /// All prolog and epilog blocks.
306  /// For every block, the stages that are produced.
308  /// For every block, the stages that are available. A stage can be available
309  /// but not produced (in the epilog) or produced but not available (in the
310  /// prolog).
312  /// When peeling the epilogue keep track of the distance between the phi
313  /// nodes and the kernel.
315 
316  /// CanonicalMIs and BlockMIs form a bidirectional map between any of the
317  /// loop kernel clones.
321 
322  /// State passed from peelKernel to peelPrologAndEpilogs().
323  std::deque<MachineBasicBlock *> PeeledFront, PeeledBack;
324  /// Illegal phis that need to be deleted once we re-link stages.
326 
327  /// Converts BB from the original loop body to the rewritten, pipelined
328  /// steady-state.
329  void rewriteKernel();
330 
331  /// Peels one iteration of the rewritten kernel (BB) in the specified
332  /// direction.
334  // Delete instructions whose stage is less than MinStage in the given basic
335  // block.
336  void filterInstructions(MachineBasicBlock *MB, int MinStage);
337  // Move instructions of the given stage from sourceBB to DestBB. Remap the phi
338  // instructions to keep a valid IR.
340  MachineBasicBlock *SourceBB, unsigned Stage);
341  /// Peel the kernel forwards and backwards to produce prologs and epilogs,
342  /// and stitch them together.
343  void peelPrologAndEpilogs();
344  /// All prolog and epilog blocks are clones of the kernel, so any produced
345  /// register in one block has an corollary in all other blocks.
347  /// Change all users of MI, if MI is predicated out
348  /// (LiveStages[MI->getParent()] == false).
350  /// Insert branches between prologs, kernel and epilogs.
351  void fixupBranches();
352  /// Create a poor-man's LCSSA by cloning only the PHIs from the kernel block
353  /// to a block dominated by all prologs and epilogs. This allows us to treat
354  /// the loop exiting block as any other kernel clone.
356  /// Helper to get the stage of an instruction in the schedule.
357  unsigned getStage(MachineInstr *MI) {
358  if (CanonicalMIs.count(MI))
359  MI = CanonicalMIs[MI];
360  return Schedule.getStage(MI);
361  }
362  /// Helper function to find the right canonical register for a phi instruction
363  /// coming from a peeled out prologue.
365  /// Target loop info before kernel peeling.
366  std::unique_ptr<TargetInstrInfo::PipelinerLoopInfo> LoopInfo;
367 };
368 
369 /// Expander that simply annotates each scheduled instruction with a post-instr
370 /// symbol that can be consumed by the ModuloScheduleTest pass.
371 ///
372 /// The post-instr symbol is a way of annotating an instruction that can be
373 /// roundtripped in MIR. The syntax is:
374 /// MYINST %0, post-instr-symbol <mcsymbol Stage-1_Cycle-5>
376  MachineFunction &MF;
377  ModuloSchedule &S;
378 
379 public:
381  : MF(MF), S(S) {}
382 
383  /// Performs the annotation.
384  void annotate();
385 };
386 
387 } // end namespace llvm
388 
389 #endif // LLVM_CODEGEN_MODULOSCHEDULE_H
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:100
llvm::PeelingModuloScheduleExpander::LoopInfo
std::unique_ptr< TargetInstrInfo::PipelinerLoopInfo > LoopInfo
Target loop info before kernel peeling.
Definition: ModuloSchedule.h:366
llvm
Definition: AllocatorList.h:23
Reg
unsigned Reg
Definition: MachineSink.cpp:1566
llvm::PeelingModuloScheduleExpander::rewriteKernel
void rewriteKernel()
Converts BB from the original loop body to the rewritten, pipelined steady-state.
Definition: ModuloSchedule.cpp:1983
llvm::ModuloScheduleExpander::cleanup
void cleanup()
Performs final cleanup after expansion.
Definition: ModuloSchedule.cpp:181
llvm::ModuloSchedule
Represents a schedule for a single-block loop.
Definition: ModuloSchedule.h:78
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:52
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
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:105
MachineLoopUtils.h
TargetInstrInfo.h
llvm::PeelingModuloScheduleExpander::Epilogs
SmallVector< MachineBasicBlock *, 4 > Epilogs
Definition: ModuloSchedule.h:305
llvm::PeelingModuloScheduleExpander::getStage
unsigned getStage(MachineInstr *MI)
Helper to get the stage of an instruction in the schedule.
Definition: ModuloSchedule.h:357
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:145
llvm::PeelingModuloScheduleExpander::TII
const TargetInstrInfo * TII
Definition: ModuloSchedule.h:297
llvm::PeelingModuloScheduleExpander
A reimplementation of ModuloScheduleExpander.
Definition: ModuloSchedule.h:279
llvm::ModuloScheduleExpander::expand
void expand()
Performs the actual expansion.
Definition: ModuloSchedule.cpp:66
llvm::PeelingModuloScheduleExpander::PeeledFront
std::deque< MachineBasicBlock * > PeeledFront
State passed from peelKernel to peelPrologAndEpilogs().
Definition: ModuloSchedule.h:323
llvm::PeelingModuloScheduleExpander::moveStageBetweenBlocks
void moveStageBetweenBlocks(MachineBasicBlock *DestBB, MachineBasicBlock *SourceBB, unsigned Stage)
Definition: ModuloSchedule.cpp:1623
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
llvm::ModuloSchedule::dump
void dump()
Definition: ModuloSchedule.h:153
llvm::PeelingModuloScheduleExpander::AvailableStages
DenseMap< MachineBasicBlock *, BitVector > AvailableStages
For every block, the stages that are available.
Definition: ModuloSchedule.h:311
llvm::TargetInstrInfo
TargetInstrInfo - Interface to description of machine instruction set.
Definition: TargetInstrInfo.h:97
MachineLoopInfo.h
llvm::PeelingModuloScheduleExpander::Schedule
ModuloSchedule & Schedule
Definition: ModuloSchedule.h:293
llvm::PeelingModuloScheduleExpander::PeeledBack
std::deque< MachineBasicBlock * > PeeledBack
Definition: ModuloSchedule.h:323
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:314
llvm::ModuloScheduleExpander::ModuloScheduleExpander
ModuloScheduleExpander(MachineFunction &MF, ModuloSchedule &S, LiveIntervals &LIS, InstrChangesTy InstrChanges)
Create a new ModuloScheduleExpander.
Definition: ModuloSchedule.h:261
llvm::PeelingModuloScheduleExpander::BlockMIs
DenseMap< std::pair< MachineBasicBlock *, MachineInstr * >, MachineInstr * > BlockMIs
Definition: ModuloSchedule.h:320
llvm::PeelingModuloScheduleExpander::BB
MachineBasicBlock * BB
The original loop block that gets rewritten in-place.
Definition: ModuloSchedule.h:301
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:129
llvm::PeelingModuloScheduleExpander::Prologs
SmallVector< MachineBasicBlock *, 4 > Prologs
All prolog and epilog blocks.
Definition: ModuloSchedule.h:305
llvm::PeelingModuloScheduleExpander::filterInstructions
void filterInstructions(MachineBasicBlock *MB, int MinStage)
Definition: ModuloSchedule.cpp:1594
llvm::ModuloSchedule::setStage
void setStage(MachineInstr *MI, int MIStage)
Set the stage of a newly created instruction.
Definition: ModuloSchedule.h:145
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:50
llvm::ModuloSchedule::getInstructions
ArrayRef< MachineInstr * > getInstructions()
Return the rescheduled instructions in order.
Definition: ModuloSchedule.h:151
llvm::PeelingModuloScheduleExpander::peelKernel
MachineBasicBlock * peelKernel(LoopPeelDirection LPD)
Peels one iteration of the rewritten kernel (BB) in the specified direction.
Definition: ModuloSchedule.cpp:1578
llvm::ModuloSchedule::getFinalCycle
int getFinalCycle()
Return the final cycle in the schedule, which is the cycle index of the last instruction.
Definition: ModuloSchedule.h:130
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
llvm::PeelingModuloScheduleExpander::Preheader
MachineBasicBlock * Preheader
The original loop preheader.
Definition: ModuloSchedule.h:303
llvm::PeelingModuloScheduleExpander::fixupBranches
void fixupBranches()
Insert branches between prologs, kernel and epilogs.
Definition: ModuloSchedule.cpp:1936
llvm::PeelingModuloScheduleExpander::ST
const TargetSubtargetInfo & ST
Definition: ModuloSchedule.h:295
llvm::ModuloScheduleExpander::getRewrittenKernel
MachineBasicBlock * getRewrittenKernel()
Returns the newly rewritten kernel block, or nullptr if this was optimized away.
Definition: ModuloSchedule.h:274
llvm::MachineLoop
Definition: MachineLoopInfo.h:45
llvm::PeelingModuloScheduleExpander::rewriteUsesOf
void rewriteUsesOf(MachineInstr *MI)
Change all users of MI, if MI is predicated out (LiveStages[MI->getParent()] == false).
Definition: ModuloSchedule.cpp:1893
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:64
llvm::ModuloScheduleTestAnnotater::annotate
void annotate()
Performs the annotation.
Definition: ModuloSchedule.cpp:2187
llvm::DenseMap
Definition: DenseMap.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::ModuloSchedule::getFirstCycle
int getFirstCycle()
Return the first cycle in the schedule, which is the cycle index of the first instruction.
Definition: ModuloSchedule.h:126
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:150
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:1563
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:1842
llvm::LoopPeelDirection
LoopPeelDirection
Definition: MachineLoopUtils.h:18
llvm::MachineFunction
Definition: MachineFunction.h:227
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:1886
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:33
llvm::ModuloScheduleTestAnnotater
Expander that simply annotates each scheduled instruction with a post-instr symbol that can be consum...
Definition: ModuloSchedule.h:375
llvm::LoopInfo
Definition: LoopInfo.h:1080
llvm::PeelingModuloScheduleExpander::expand
void expand()
Definition: ModuloSchedule.cpp:1988
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:281
llvm::TargetSubtargetInfo
TargetSubtargetInfo - Generic base class for all target subtargets.
Definition: TargetSubtargetInfo.h:59
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:298
std
Definition: BitVector.h:838
llvm::PeelingModuloScheduleExpander::MRI
MachineRegisterInfo & MRI
Definition: ModuloSchedule.h:296
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:83
llvm::ModuloSchedule::getCycle
int getCycle(MachineInstr *MI)
Return the cycle that MI is scheduled at, or -1.
Definition: ModuloSchedule.h:139
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:122
llvm::PeelingModuloScheduleExpander::IllegalPhisToDelete
SmallVector< MachineInstr *, 4 > IllegalPhisToDelete
Illegal phis that need to be deleted once we re-link stages.
Definition: ModuloSchedule.h:325
llvm::ModuloSchedule::getLoop
MachineLoop * getLoop() const
Return the single-block loop being scheduled.
Definition: ModuloSchedule.h:118
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:1725
llvm::PeelingModuloScheduleExpander::validateAgainstModuloScheduleExpander
void validateAgainstModuloScheduleExpander()
Runs ModuloScheduleExpander and treats it as a golden input to validate aspects of the code generated...
Definition: ModuloSchedule.cpp:2000
llvm::ModuloSchedule::print
void print(raw_ostream &OS)
Definition: ModuloSchedule.cpp:24
llvm::PeelingModuloScheduleExpander::LiveStages
DenseMap< MachineBasicBlock *, BitVector > LiveStages
For every block, the stages that are produced.
Definition: ModuloSchedule.h:307
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:350
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
llvm::PeelingModuloScheduleExpander::MF
MachineFunction & MF
Definition: ModuloSchedule.h:294
llvm::ModuloScheduleExpander
The ModuloScheduleExpander takes a ModuloSchedule and expands it in-place, rewriting the old loop and...
Definition: ModuloSchedule.h:159
llvm::ModuloSchedule::getStage
int getStage(MachineInstr *MI)
Return the stage that MI is scheduled in, or -1.
Definition: ModuloSchedule.h:133
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:1708
llvm::ModuloScheduleTestAnnotater::ModuloScheduleTestAnnotater
ModuloScheduleTestAnnotater(MachineFunction &MF, ModuloSchedule &S)
Definition: ModuloSchedule.h:380
llvm::PeelingModuloScheduleExpander::CanonicalMIs
DenseMap< MachineInstr *, MachineInstr * > CanonicalMIs
CanonicalMIs and BlockMIs form a bidirectional map between any of the loop kernel clones.
Definition: ModuloSchedule.h:318