LLVM  16.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  ValueMapTy *VRMapPhi, MBBVectorTy &EpilogBBs,
196  MBBVectorTy &PrologBBs);
197  void generateExistingPhis(MachineBasicBlock *NewBB, MachineBasicBlock *BB1,
198  MachineBasicBlock *BB2, MachineBasicBlock *KernelBB,
199  ValueMapTy *VRMap, InstrMapTy &InstrMap,
200  unsigned LastStageNum, unsigned CurStageNum,
201  bool IsLast);
202  void generatePhis(MachineBasicBlock *NewBB, MachineBasicBlock *BB1,
203  MachineBasicBlock *BB2, MachineBasicBlock *KernelBB,
204  ValueMapTy *VRMap, ValueMapTy *VRMapPhi,
205  InstrMapTy &InstrMap, unsigned LastStageNum,
206  unsigned CurStageNum, bool IsLast);
207  void removeDeadInstructions(MachineBasicBlock *KernelBB,
208  MBBVectorTy &EpilogBBs);
209  void splitLifetimes(MachineBasicBlock *KernelBB, MBBVectorTy &EpilogBBs);
210  void addBranches(MachineBasicBlock &PreheaderBB, MBBVectorTy &PrologBBs,
211  MachineBasicBlock *KernelBB, MBBVectorTy &EpilogBBs,
212  ValueMapTy *VRMap);
213  bool computeDelta(MachineInstr &MI, unsigned &Delta);
214  void updateMemOperands(MachineInstr &NewMI, MachineInstr &OldMI,
215  unsigned Num);
216  MachineInstr *cloneInstr(MachineInstr *OldMI, unsigned CurStageNum,
217  unsigned InstStageNum);
218  MachineInstr *cloneAndChangeInstr(MachineInstr *OldMI, unsigned CurStageNum,
219  unsigned InstStageNum);
220  void updateInstruction(MachineInstr *NewMI, bool LastDef,
221  unsigned CurStageNum, unsigned InstrStageNum,
222  ValueMapTy *VRMap);
223  MachineInstr *findDefInLoop(unsigned Reg);
224  unsigned getPrevMapVal(unsigned StageNum, unsigned PhiStage, unsigned LoopVal,
225  unsigned LoopStage, ValueMapTy *VRMap,
226  MachineBasicBlock *BB);
227  void rewritePhiValues(MachineBasicBlock *NewBB, unsigned StageNum,
228  ValueMapTy *VRMap, InstrMapTy &InstrMap);
229  void rewriteScheduledInstr(MachineBasicBlock *BB, InstrMapTy &InstrMap,
230  unsigned CurStageNum, unsigned PhiNum,
231  MachineInstr *Phi, unsigned OldReg,
232  unsigned NewReg, unsigned PrevReg = 0);
233  bool isLoopCarried(MachineInstr &Phi);
234 
235  /// Return the max. number of stages/iterations that can occur between a
236  /// register definition and its uses.
237  unsigned getStagesForReg(int Reg, unsigned CurStage) {
238  std::pair<unsigned, bool> Stages = RegToStageDiff[Reg];
239  if ((int)CurStage > Schedule.getNumStages() - 1 && Stages.first == 0 &&
240  Stages.second)
241  return 1;
242  return Stages.first;
243  }
244 
245  /// The number of stages for a Phi is a little different than other
246  /// instructions. The minimum value computed in RegToStageDiff is 1
247  /// because we assume the Phi is needed for at least 1 iteration.
248  /// This is not the case if the loop value is scheduled prior to the
249  /// Phi in the same stage. This function returns the number of stages
250  /// or iterations needed between the Phi definition and any uses.
251  unsigned getStagesForPhi(int Reg) {
252  std::pair<unsigned, bool> Stages = RegToStageDiff[Reg];
253  if (Stages.second)
254  return Stages.first;
255  return Stages.first - 1;
256  }
257 
258 public:
259  /// Create a new ModuloScheduleExpander.
260  /// \arg InstrChanges Modifications to make to instructions with memory
261  /// operands.
262  /// FIXME: InstrChanges is opaque and is an implementation detail of an
263  /// optimization in MachinePipeliner that crosses abstraction boundaries.
265  LiveIntervals &LIS, InstrChangesTy InstrChanges)
266  : Schedule(S), MF(MF), ST(MF.getSubtarget()), MRI(MF.getRegInfo()),
267  TII(ST.getInstrInfo()), LIS(LIS),
268  InstrChanges(std::move(InstrChanges)) {}
269 
270  /// Performs the actual expansion.
271  void expand();
272  /// Performs final cleanup after expansion.
273  void cleanup();
274 
275  /// Returns the newly rewritten kernel block, or nullptr if this was
276  /// optimized away.
277  MachineBasicBlock *getRewrittenKernel() { return NewKernel; }
278 };
279 
280 /// A reimplementation of ModuloScheduleExpander. It works by generating a
281 /// standalone kernel loop and peeling out the prologs and epilogs.
283 public:
286  : Schedule(S), MF(MF), ST(MF.getSubtarget()), MRI(MF.getRegInfo()),
287  TII(ST.getInstrInfo()), LIS(LIS) {}
288 
289  void expand();
290 
291  /// Runs ModuloScheduleExpander and treats it as a golden input to validate
292  /// aspects of the code generated by PeelingModuloScheduleExpander.
294 
295 protected:
302 
303  /// The original loop block that gets rewritten in-place.
305  /// The original loop preheader.
307  /// All prolog and epilog blocks.
309  /// For every block, the stages that are produced.
311  /// For every block, the stages that are available. A stage can be available
312  /// but not produced (in the epilog) or produced but not available (in the
313  /// prolog).
315  /// When peeling the epilogue keep track of the distance between the phi
316  /// nodes and the kernel.
318 
319  /// CanonicalMIs and BlockMIs form a bidirectional map between any of the
320  /// loop kernel clones.
324 
325  /// State passed from peelKernel to peelPrologAndEpilogs().
326  std::deque<MachineBasicBlock *> PeeledFront, PeeledBack;
327  /// Illegal phis that need to be deleted once we re-link stages.
329 
330  /// Converts BB from the original loop body to the rewritten, pipelined
331  /// steady-state.
332  void rewriteKernel();
333 
334  /// Peels one iteration of the rewritten kernel (BB) in the specified
335  /// direction.
337  // Delete instructions whose stage is less than MinStage in the given basic
338  // block.
339  void filterInstructions(MachineBasicBlock *MB, int MinStage);
340  // Move instructions of the given stage from sourceBB to DestBB. Remap the phi
341  // instructions to keep a valid IR.
343  MachineBasicBlock *SourceBB, unsigned Stage);
344  /// Peel the kernel forwards and backwards to produce prologs and epilogs,
345  /// and stitch them together.
346  void peelPrologAndEpilogs();
347  /// All prolog and epilog blocks are clones of the kernel, so any produced
348  /// register in one block has an corollary in all other blocks.
350  /// Change all users of MI, if MI is predicated out
351  /// (LiveStages[MI->getParent()] == false).
353  /// Insert branches between prologs, kernel and epilogs.
354  void fixupBranches();
355  /// Create a poor-man's LCSSA by cloning only the PHIs from the kernel block
356  /// to a block dominated by all prologs and epilogs. This allows us to treat
357  /// the loop exiting block as any other kernel clone.
359  /// Helper to get the stage of an instruction in the schedule.
360  unsigned getStage(MachineInstr *MI) {
361  if (CanonicalMIs.count(MI))
362  MI = CanonicalMIs[MI];
363  return Schedule.getStage(MI);
364  }
365  /// Helper function to find the right canonical register for a phi instruction
366  /// coming from a peeled out prologue.
368  /// Target loop info before kernel peeling.
369  std::unique_ptr<TargetInstrInfo::PipelinerLoopInfo> LoopInfo;
370 };
371 
372 /// Expander that simply annotates each scheduled instruction with a post-instr
373 /// symbol that can be consumed by the ModuloScheduleTest pass.
374 ///
375 /// The post-instr symbol is a way of annotating an instruction that can be
376 /// roundtripped in MIR. The syntax is:
377 /// MYINST %0, post-instr-symbol <mcsymbol Stage-1_Cycle-5>
379  MachineFunction &MF;
380  ModuloSchedule &S;
381 
382 public:
384  : MF(MF), S(S) {}
385 
386  /// Performs the annotation.
387  void annotate();
388 };
389 
390 } // end namespace llvm
391 
392 #endif // LLVM_CODEGEN_MODULOSCHEDULE_H
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:109
llvm::PeelingModuloScheduleExpander::LoopInfo
std::unique_ptr< TargetInstrInfo::PipelinerLoopInfo > LoopInfo
Target loop info before kernel peeling.
Definition: ModuloSchedule.h:369
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::PeelingModuloScheduleExpander::rewriteKernel
void rewriteKernel()
Converts BB from the original loop body to the rewritten, pipelined steady-state.
Definition: ModuloSchedule.cpp:2002
llvm::ModuloScheduleExpander::cleanup
void cleanup()
Performs final cleanup after expansion.
Definition: ModuloSchedule.cpp:184
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:547
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
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:308
llvm::PeelingModuloScheduleExpander::getStage
unsigned getStage(MachineInstr *MI)
Helper to get the stage of an instruction in the schedule.
Definition: ModuloSchedule.h:360
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::max
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:337
llvm::PeelingModuloScheduleExpander::TII
const TargetInstrInfo * TII
Definition: ModuloSchedule.h:300
llvm::PeelingModuloScheduleExpander
A reimplementation of ModuloScheduleExpander.
Definition: ModuloSchedule.h:282
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:326
llvm::PeelingModuloScheduleExpander::moveStageBetweenBlocks
void moveStageBetweenBlocks(MachineBasicBlock *DestBB, MachineBasicBlock *SourceBB, unsigned Stage)
Definition: ModuloSchedule.cpp:1642
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:314
llvm::TargetInstrInfo
TargetInstrInfo - Interface to description of machine instruction set.
Definition: TargetInstrInfo.h:98
llvm::PeelingModuloScheduleExpander::Schedule
ModuloSchedule & Schedule
Definition: ModuloSchedule.h:296
llvm::PeelingModuloScheduleExpander::PeeledBack
std::deque< MachineBasicBlock * > PeeledBack
Definition: ModuloSchedule.h:326
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:317
llvm::ModuloScheduleExpander::ModuloScheduleExpander
ModuloScheduleExpander(MachineFunction &MF, ModuloSchedule &S, LiveIntervals &LIS, InstrChangesTy InstrChanges)
Create a new ModuloScheduleExpander.
Definition: ModuloSchedule.h:264
llvm::PeelingModuloScheduleExpander::BlockMIs
DenseMap< std::pair< MachineBasicBlock *, MachineInstr * >, MachineInstr * > BlockMIs
Definition: ModuloSchedule.h:323
llvm::PeelingModuloScheduleExpander::BB
MachineBasicBlock * BB
The original loop block that gets rewritten in-place.
Definition: ModuloSchedule.h:304
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:125
llvm::PeelingModuloScheduleExpander::Prologs
SmallVector< MachineBasicBlock *, 4 > Prologs
All prolog and epilog blocks.
Definition: ModuloSchedule.h:308
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:1613
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:53
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:1597
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:306
llvm::PeelingModuloScheduleExpander::fixupBranches
void fixupBranches()
Insert branches between prologs, kernel and epilogs.
Definition: ModuloSchedule.cpp:1955
llvm::PeelingModuloScheduleExpander::ST
const TargetSubtargetInfo & ST
Definition: ModuloSchedule.h:298
llvm::ModuloScheduleExpander::getRewrittenKernel
MachineBasicBlock * getRewrittenKernel()
Returns the newly rewritten kernel block, or nullptr if this was optimized away.
Definition: ModuloSchedule.h:277
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:1912
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:66
llvm::ModuloScheduleTestAnnotater::annotate
void annotate()
Performs the annotation.
Definition: ModuloSchedule.cpp:2206
llvm::DenseMap
Definition: DenseMap.h:714
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: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:1861
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:1861
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:1905
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:378
llvm::LoopInfo
Definition: LoopInfo.h:1108
llvm::PeelingModuloScheduleExpander::expand
void expand()
Definition: ModuloSchedule.cpp:2007
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:284
llvm::TargetSubtargetInfo
TargetSubtargetInfo - Generic base class for all target subtargets.
Definition: TargetSubtargetInfo.h:62
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:301
std
Definition: BitVector.h:851
llvm::PeelingModuloScheduleExpander::MRI
MachineRegisterInfo & MRI
Definition: ModuloSchedule.h:299
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:328
llvm::ModuloSchedule::getLoop
MachineLoop * getLoop() const
Return the single-block loop being scheduled.
Definition: ModuloSchedule.h:119
llvm::LiveIntervals
Definition: LiveIntervals.h:53
llvm::PeelingModuloScheduleExpander::peelPrologAndEpilogs
void peelPrologAndEpilogs()
Peel the kernel forwards and backwards to produce prologs and epilogs, and stitch them together.
Definition: ModuloSchedule.cpp:1744
llvm::PeelingModuloScheduleExpander::validateAgainstModuloScheduleExpander
void validateAgainstModuloScheduleExpander()
Runs ModuloScheduleExpander and treats it as a golden input to validate aspects of the code generated...
Definition: ModuloSchedule.cpp:2019
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:310
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:297
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:1727
llvm::ModuloScheduleTestAnnotater::ModuloScheduleTestAnnotater
ModuloScheduleTestAnnotater(MachineFunction &MF, ModuloSchedule &S)
Definition: ModuloSchedule.h:383
llvm::PeelingModuloScheduleExpander::CanonicalMIs
DenseMap< MachineInstr *, MachineInstr * > CanonicalMIs
CanonicalMIs and BlockMIs form a bidirectional map between any of the loop kernel clones.
Definition: ModuloSchedule.h:321