003 File Manager
Current Path:
/usr/src/contrib/llvm-project/llvm/include/llvm/CodeGen
usr
/
src
/
contrib
/
llvm-project
/
llvm
/
include
/
llvm
/
CodeGen
/
📁
..
📄
AccelTable.h
(13.54 KB)
📄
Analysis.h
(6.04 KB)
📄
AntiDepBreaker.h
(3.78 KB)
📄
AsmPrinter.h
(27.35 KB)
📄
AsmPrinterHandler.h
(2.6 KB)
📄
AtomicExpandUtils.h
(2.49 KB)
📄
BasicTTIImpl.h
(73.64 KB)
📄
BuiltinGCs.h
(1008 B)
📄
CSEConfigBase.h
(1.09 KB)
📄
CalcSpillWeights.h
(4.69 KB)
📄
CallingConvLower.h
(21 KB)
📄
CommandFlags.h
(3.65 KB)
📄
CostTable.h
(1.87 KB)
📄
DAGCombine.h
(606 B)
📄
DFAPacketizer.h
(7.47 KB)
📄
DIE.h
(32.19 KB)
📄
DIEValue.def
(1.4 KB)
📄
DbgEntityHistoryCalculator.h
(4.37 KB)
📄
DebugHandlerBase.h
(4.68 KB)
📄
DwarfStringPoolEntry.h
(2.18 KB)
📄
EdgeBundles.h
(2.13 KB)
📄
ExecutionDomainFix.h
(7.72 KB)
📄
ExpandReductions.h
(726 B)
📄
FastISel.h
(22.87 KB)
📄
FaultMaps.h
(6.66 KB)
📄
FunctionLoweringInfo.h
(9.68 KB)
📄
GCMetadata.h
(7.24 KB)
📄
GCMetadataPrinter.h
(2.46 KB)
📄
GCStrategy.h
(5.25 KB)
📁
GlobalISel
📄
ISDOpcodes.h
(52.75 KB)
📄
IndirectThunks.h
(3.85 KB)
📄
IntrinsicLowering.h
(1.67 KB)
📄
LatencyPriorityQueue.h
(3.09 KB)
📄
LazyMachineBlockFrequencyInfo.h
(2.82 KB)
📄
LexicalScopes.h
(10.06 KB)
📄
LinkAllAsmWriterComponents.h
(1.34 KB)
📄
LinkAllCodegenComponents.h
(2.18 KB)
📄
LiveInterval.h
(37.24 KB)
📄
LiveIntervalCalc.h
(2.91 KB)
📄
LiveIntervalUnion.h
(6.93 KB)
📄
LiveIntervals.h
(19.86 KB)
📄
LivePhysRegs.h
(7.51 KB)
📄
LiveRangeCalc.h
(11.49 KB)
📄
LiveRangeEdit.h
(10.45 KB)
📄
LiveRegMatrix.h
(6.18 KB)
📄
LiveRegUnits.h
(6.24 KB)
📄
LiveStacks.h
(3.35 KB)
📄
LiveVariables.h
(12.98 KB)
📄
LoopTraversal.h
(4.38 KB)
📄
LowLevelType.h
(1.28 KB)
📄
MBFIWrapper.h
(1.58 KB)
📄
MIRFormatter.h
(3.13 KB)
📁
MIRParser
📄
MIRPrinter.h
(1.73 KB)
📄
MIRYamlMapping.h
(23.95 KB)
📄
MachORelocation.h
(2.19 KB)
📄
MachineBasicBlock.h
(42.95 KB)
📄
MachineBlockFrequencyInfo.h
(3.21 KB)
📄
MachineBranchProbabilityInfo.h
(2.69 KB)
📄
MachineCombinerPattern.h
(3.5 KB)
📄
MachineConstantPool.h
(5.25 KB)
📄
MachineDominanceFrontier.h
(2.93 KB)
📄
MachineDominators.h
(9.59 KB)
📄
MachineFrameInfo.h
(34.84 KB)
📄
MachineFunction.h
(42.94 KB)
📄
MachineFunctionPass.h
(2.93 KB)
📄
MachineInstr.h
(73.72 KB)
📄
MachineInstrBuilder.h
(22.84 KB)
📄
MachineInstrBundle.h
(10.16 KB)
📄
MachineInstrBundleIterator.h
(10.92 KB)
📄
MachineJumpTableInfo.h
(4.66 KB)
📄
MachineLoopInfo.h
(7.3 KB)
📄
MachineLoopUtils.h
(1.74 KB)
📄
MachineMemOperand.h
(12.69 KB)
📄
MachineModuleInfo.h
(9.88 KB)
📄
MachineModuleInfoImpls.h
(3.36 KB)
📄
MachineOperand.h
(37.64 KB)
📄
MachineOptimizationRemarkEmitter.h
(8.99 KB)
📄
MachineOutliner.h
(8.04 KB)
📄
MachinePassRegistry.h
(6.1 KB)
📄
MachinePipeliner.h
(21.17 KB)
📄
MachinePostDominators.h
(2.93 KB)
📄
MachineRegionInfo.h
(5.93 KB)
📄
MachineRegisterInfo.h
(46.75 KB)
📄
MachineSSAUpdater.h
(4.37 KB)
📄
MachineScheduler.h
(36.6 KB)
📄
MachineSizeOpts.h
(1.86 KB)
📄
MachineTraceMetrics.h
(17.17 KB)
📄
MacroFusion.h
(1.96 KB)
📄
ModuloSchedule.h
(15.8 KB)
📄
NonRelocatableStringpool.h
(2.9 KB)
📁
PBQP
📄
PBQPRAConstraint.h
(1.83 KB)
📄
ParallelCG.h
(1.66 KB)
📄
Passes.h
(18.96 KB)
📄
PreISelIntrinsicLowering.h
(944 B)
📄
PseudoSourceValue.h
(6.21 KB)
📄
RDFGraph.h
(33.73 KB)
📄
RDFLiveness.h
(5.01 KB)
📄
RDFRegisters.h
(6.51 KB)
📄
ReachingDefAnalysis.h
(10.68 KB)
📄
RegAllocPBQP.h
(16.47 KB)
📄
RegAllocRegistry.h
(2.27 KB)
📄
Register.h
(5.61 KB)
📄
RegisterClassInfo.h
(4.86 KB)
📄
RegisterPressure.h
(21.04 KB)
📄
RegisterScavenging.h
(8.73 KB)
📄
RegisterUsageInfo.h
(2.3 KB)
📄
ResourcePriorityQueue.h
(4.19 KB)
📄
RuntimeLibcalls.h
(3.05 KB)
📄
SDNodeProperties.td
(1.57 KB)
📄
ScheduleDAG.h
(28.92 KB)
📄
ScheduleDAGInstrs.h
(15.49 KB)
📄
ScheduleDAGMutation.h
(1021 B)
📄
ScheduleDFS.h
(5.79 KB)
📄
ScheduleHazardRecognizer.h
(4.65 KB)
📄
SchedulerRegistry.h
(4.27 KB)
📄
ScoreboardHazardRecognizer.h
(3.7 KB)
📄
SelectionDAG.h
(89.12 KB)
📄
SelectionDAGAddressAnalysis.h
(3.58 KB)
📄
SelectionDAGISel.h
(13.48 KB)
📄
SelectionDAGNodes.h
(91.77 KB)
📄
SelectionDAGTargetInfo.h
(7.99 KB)
📄
SlotIndexes.h
(24.12 KB)
📄
Spiller.h
(1.16 KB)
📄
StackMaps.h
(11.45 KB)
📄
StackProtector.h
(4.1 KB)
📄
SwiftErrorValueTracking.h
(3.87 KB)
📄
SwitchLoweringUtils.h
(9.51 KB)
📄
TailDuplicator.h
(5.54 KB)
📄
TargetCallingConv.h
(8.26 KB)
📄
TargetFrameLowering.h
(19.21 KB)
📄
TargetInstrInfo.h
(84.48 KB)
📄
TargetLowering.h
(194.17 KB)
📄
TargetLoweringObjectFileImpl.h
(11.63 KB)
📄
TargetOpcodes.h
(1.37 KB)
📄
TargetPassConfig.h
(17.9 KB)
📄
TargetRegisterInfo.h
(48.65 KB)
📄
TargetSchedule.h
(7.75 KB)
📄
TargetSubtargetInfo.h
(12.53 KB)
📄
UnreachableBlockElim.h
(1.39 KB)
📄
ValueTypes.h
(17.2 KB)
📄
ValueTypes.td
(11.42 KB)
📄
VirtRegMap.h
(6.37 KB)
📄
WasmEHFuncInfo.h
(1.92 KB)
📄
WinEHFuncInfo.h
(4.01 KB)
Editing: ModuloSchedule.h
//===- ModuloSchedule.h - Software pipeline schedule expansion ------------===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// // // Software pipelining (SWP) is an instruction scheduling technique for loops // that overlaps loop iterations and exploits ILP via compiler transformations. // // There are multiple methods for analyzing a loop and creating a schedule. // An example algorithm is Swing Modulo Scheduling (implemented by the // MachinePipeliner). The details of how a schedule is arrived at are irrelevant // for the task of actually rewriting a loop to adhere to the schedule, which // is what this file does. // // A schedule is, for every instruction in a block, a Cycle and a Stage. Note // that we only support single-block loops, so "block" and "loop" can be used // interchangably. // // The Cycle of an instruction defines a partial order of the instructions in // the remapped loop. Instructions within a cycle must not consume the output // of any instruction in the same cycle. Cycle information is assumed to have // been calculated such that the processor will execute instructions in // lock-step (for example in a VLIW ISA). // // The Stage of an instruction defines the mapping between logical loop // iterations and pipelined loop iterations. An example (unrolled) pipeline // may look something like: // // I0[0] Execute instruction I0 of iteration 0 // I1[0], I0[1] Execute I0 of iteration 1 and I1 of iteration 1 // I1[1], I0[2] // I1[2], I0[3] // // In the schedule for this unrolled sequence we would say that I0 was scheduled // in stage 0 and I1 in stage 1: // // loop: // [stage 0] x = I0 // [stage 1] I1 x (from stage 0) // // And to actually generate valid code we must insert a phi: // // loop: // x' = phi(x) // x = I0 // I1 x' // // This is a simple example; the rules for how to generate correct code given // an arbitrary schedule containing loop-carried values are complex. // // Note that these examples only mention the steady-state kernel of the // generated loop; prologs and epilogs must be generated also that prime and // flush the pipeline. Doing so is nontrivial. // //===----------------------------------------------------------------------===// #ifndef LLVM_LIB_CODEGEN_MODULOSCHEDULE_H #define LLVM_LIB_CODEGEN_MODULOSCHEDULE_H #include "llvm/CodeGen/MachineFunction.h" #include "llvm/CodeGen/MachineLoopInfo.h" #include "llvm/CodeGen/MachineLoopUtils.h" #include "llvm/CodeGen/TargetInstrInfo.h" #include "llvm/CodeGen/TargetSubtargetInfo.h" #include <deque> #include <vector> namespace llvm { class MachineBasicBlock; class MachineInstr; class LiveIntervals; /// Represents a schedule for a single-block loop. For every instruction we /// maintain a Cycle and Stage. class ModuloSchedule { private: /// The block containing the loop instructions. MachineLoop *Loop; /// The instructions to be generated, in total order. Cycle provides a partial /// order; the total order within cycles has been decided by the schedule /// producer. std::vector<MachineInstr *> ScheduledInstrs; /// The cycle for each instruction. DenseMap<MachineInstr *, int> Cycle; /// The stage for each instruction. DenseMap<MachineInstr *, int> Stage; /// The number of stages in this schedule (Max(Stage) + 1). int NumStages; public: /// Create a new ModuloSchedule. /// \arg ScheduledInstrs The new loop instructions, in total resequenced /// order. /// \arg Cycle Cycle index for all instructions in ScheduledInstrs. Cycle does /// not need to start at zero. ScheduledInstrs must be partially ordered by /// Cycle. /// \arg Stage Stage index for all instructions in ScheduleInstrs. ModuloSchedule(MachineFunction &MF, MachineLoop *Loop, std::vector<MachineInstr *> ScheduledInstrs, DenseMap<MachineInstr *, int> Cycle, DenseMap<MachineInstr *, int> Stage) : Loop(Loop), ScheduledInstrs(ScheduledInstrs), Cycle(std::move(Cycle)), Stage(std::move(Stage)) { NumStages = 0; for (auto &KV : this->Stage) NumStages = std::max(NumStages, KV.second); ++NumStages; } /// Return the single-block loop being scheduled. MachineLoop *getLoop() const { return Loop; } /// Return the number of stages contained in this schedule, which is the /// largest stage index + 1. int getNumStages() const { return NumStages; } /// Return the first cycle in the schedule, which is the cycle index of the /// first instruction. int getFirstCycle() { return Cycle[ScheduledInstrs.front()]; } /// Return the final cycle in the schedule, which is the cycle index of the /// last instruction. int getFinalCycle() { return Cycle[ScheduledInstrs.back()]; } /// Return the stage that MI is scheduled in, or -1. int getStage(MachineInstr *MI) { auto I = Stage.find(MI); return I == Stage.end() ? -1 : I->second; } /// Return the cycle that MI is scheduled at, or -1. int getCycle(MachineInstr *MI) { auto I = Cycle.find(MI); return I == Cycle.end() ? -1 : I->second; } /// Set the stage of a newly created instruction. void setStage(MachineInstr *MI, int MIStage) { assert(Stage.count(MI) == 0); Stage[MI] = MIStage; } /// Return the rescheduled instructions in order. ArrayRef<MachineInstr *> getInstructions() { return ScheduledInstrs; } void dump() { print(dbgs()); } void print(raw_ostream &OS); }; /// The ModuloScheduleExpander takes a ModuloSchedule and expands it in-place, /// rewriting the old loop and inserting prologs and epilogs as required. class ModuloScheduleExpander { public: using InstrChangesTy = DenseMap<MachineInstr *, std::pair<unsigned, int64_t>>; private: using ValueMapTy = DenseMap<unsigned, unsigned>; using MBBVectorTy = SmallVectorImpl<MachineBasicBlock *>; using InstrMapTy = DenseMap<MachineInstr *, MachineInstr *>; ModuloSchedule &Schedule; MachineFunction &MF; const TargetSubtargetInfo &ST; MachineRegisterInfo &MRI; const TargetInstrInfo *TII; LiveIntervals &LIS; MachineBasicBlock *BB; MachineBasicBlock *Preheader; MachineBasicBlock *NewKernel = nullptr; std::unique_ptr<TargetInstrInfo::PipelinerLoopInfo> LoopInfo; /// Map for each register and the max difference between its uses and def. /// The first element in the pair is the max difference in stages. The /// second is true if the register defines a Phi value and loop value is /// scheduled before the Phi. std::map<unsigned, std::pair<unsigned, bool>> RegToStageDiff; /// Instructions to change when emitting the final schedule. InstrChangesTy InstrChanges; void generatePipelinedLoop(); void generateProlog(unsigned LastStage, MachineBasicBlock *KernelBB, ValueMapTy *VRMap, MBBVectorTy &PrologBBs); void generateEpilog(unsigned LastStage, MachineBasicBlock *KernelBB, ValueMapTy *VRMap, MBBVectorTy &EpilogBBs, MBBVectorTy &PrologBBs); void generateExistingPhis(MachineBasicBlock *NewBB, MachineBasicBlock *BB1, MachineBasicBlock *BB2, MachineBasicBlock *KernelBB, ValueMapTy *VRMap, InstrMapTy &InstrMap, unsigned LastStageNum, unsigned CurStageNum, bool IsLast); void generatePhis(MachineBasicBlock *NewBB, MachineBasicBlock *BB1, MachineBasicBlock *BB2, MachineBasicBlock *KernelBB, ValueMapTy *VRMap, InstrMapTy &InstrMap, unsigned LastStageNum, unsigned CurStageNum, bool IsLast); void removeDeadInstructions(MachineBasicBlock *KernelBB, MBBVectorTy &EpilogBBs); void splitLifetimes(MachineBasicBlock *KernelBB, MBBVectorTy &EpilogBBs); void addBranches(MachineBasicBlock &PreheaderBB, MBBVectorTy &PrologBBs, MachineBasicBlock *KernelBB, MBBVectorTy &EpilogBBs, ValueMapTy *VRMap); bool computeDelta(MachineInstr &MI, unsigned &Delta); void updateMemOperands(MachineInstr &NewMI, MachineInstr &OldMI, unsigned Num); MachineInstr *cloneInstr(MachineInstr *OldMI, unsigned CurStageNum, unsigned InstStageNum); MachineInstr *cloneAndChangeInstr(MachineInstr *OldMI, unsigned CurStageNum, unsigned InstStageNum); void updateInstruction(MachineInstr *NewMI, bool LastDef, unsigned CurStageNum, unsigned InstrStageNum, ValueMapTy *VRMap); MachineInstr *findDefInLoop(unsigned Reg); unsigned getPrevMapVal(unsigned StageNum, unsigned PhiStage, unsigned LoopVal, unsigned LoopStage, ValueMapTy *VRMap, MachineBasicBlock *BB); void rewritePhiValues(MachineBasicBlock *NewBB, unsigned StageNum, ValueMapTy *VRMap, InstrMapTy &InstrMap); void rewriteScheduledInstr(MachineBasicBlock *BB, InstrMapTy &InstrMap, unsigned CurStageNum, unsigned PhiNum, MachineInstr *Phi, unsigned OldReg, unsigned NewReg, unsigned PrevReg = 0); bool isLoopCarried(MachineInstr &Phi); /// Return the max. number of stages/iterations that can occur between a /// register definition and its uses. unsigned getStagesForReg(int Reg, unsigned CurStage) { std::pair<unsigned, bool> Stages = RegToStageDiff[Reg]; if ((int)CurStage > Schedule.getNumStages() - 1 && Stages.first == 0 && Stages.second) return 1; return Stages.first; } /// The number of stages for a Phi is a little different than other /// instructions. The minimum value computed in RegToStageDiff is 1 /// because we assume the Phi is needed for at least 1 iteration. /// This is not the case if the loop value is scheduled prior to the /// Phi in the same stage. This function returns the number of stages /// or iterations needed between the Phi definition and any uses. unsigned getStagesForPhi(int Reg) { std::pair<unsigned, bool> Stages = RegToStageDiff[Reg]; if (Stages.second) return Stages.first; return Stages.first - 1; } public: /// Create a new ModuloScheduleExpander. /// \arg InstrChanges Modifications to make to instructions with memory /// operands. /// FIXME: InstrChanges is opaque and is an implementation detail of an /// optimization in MachinePipeliner that crosses abstraction boundaries. ModuloScheduleExpander(MachineFunction &MF, ModuloSchedule &S, LiveIntervals &LIS, InstrChangesTy InstrChanges) : Schedule(S), MF(MF), ST(MF.getSubtarget()), MRI(MF.getRegInfo()), TII(ST.getInstrInfo()), LIS(LIS), InstrChanges(std::move(InstrChanges)) {} /// Performs the actual expansion. void expand(); /// Performs final cleanup after expansion. void cleanup(); /// Returns the newly rewritten kernel block, or nullptr if this was /// optimized away. MachineBasicBlock *getRewrittenKernel() { return NewKernel; } }; /// A reimplementation of ModuloScheduleExpander. It works by generating a /// standalone kernel loop and peeling out the prologs and epilogs. class PeelingModuloScheduleExpander { public: PeelingModuloScheduleExpander(MachineFunction &MF, ModuloSchedule &S, LiveIntervals *LIS) : Schedule(S), MF(MF), ST(MF.getSubtarget()), MRI(MF.getRegInfo()), TII(ST.getInstrInfo()), LIS(LIS) {} void expand(); /// Runs ModuloScheduleExpander and treats it as a golden input to validate /// aspects of the code generated by PeelingModuloScheduleExpander. void validateAgainstModuloScheduleExpander(); protected: ModuloSchedule &Schedule; MachineFunction &MF; const TargetSubtargetInfo &ST; MachineRegisterInfo &MRI; const TargetInstrInfo *TII; LiveIntervals *LIS; /// The original loop block that gets rewritten in-place. MachineBasicBlock *BB; /// The original loop preheader. MachineBasicBlock *Preheader; /// All prolog and epilog blocks. SmallVector<MachineBasicBlock *, 4> Prologs, Epilogs; /// For every block, the stages that are produced. DenseMap<MachineBasicBlock *, BitVector> LiveStages; /// For every block, the stages that are available. A stage can be available /// but not produced (in the epilog) or produced but not available (in the /// prolog). DenseMap<MachineBasicBlock *, BitVector> AvailableStages; /// When peeling the epilogue keep track of the distance between the phi /// nodes and the kernel. DenseMap<MachineInstr *, unsigned> PhiNodeLoopIteration; /// CanonicalMIs and BlockMIs form a bidirectional map between any of the /// loop kernel clones. DenseMap<MachineInstr *, MachineInstr *> CanonicalMIs; DenseMap<std::pair<MachineBasicBlock *, MachineInstr *>, MachineInstr *> BlockMIs; /// State passed from peelKernel to peelPrologAndEpilogs(). std::deque<MachineBasicBlock *> PeeledFront, PeeledBack; /// Illegal phis that need to be deleted once we re-link stages. SmallVector<MachineInstr *, 4> IllegalPhisToDelete; /// Converts BB from the original loop body to the rewritten, pipelined /// steady-state. void rewriteKernel(); /// Peels one iteration of the rewritten kernel (BB) in the specified /// direction. MachineBasicBlock *peelKernel(LoopPeelDirection LPD); // Delete instructions whose stage is less than MinStage in the given basic // block. void filterInstructions(MachineBasicBlock *MB, int MinStage); // Move instructions of the given stage from sourceBB to DestBB. Remap the phi // instructions to keep a valid IR. void moveStageBetweenBlocks(MachineBasicBlock *DestBB, MachineBasicBlock *SourceBB, unsigned Stage); /// Peel the kernel forwards and backwards to produce prologs and epilogs, /// and stitch them together. void peelPrologAndEpilogs(); /// All prolog and epilog blocks are clones of the kernel, so any produced /// register in one block has an corollary in all other blocks. Register getEquivalentRegisterIn(Register Reg, MachineBasicBlock *BB); /// Change all users of MI, if MI is predicated out /// (LiveStages[MI->getParent()] == false). void rewriteUsesOf(MachineInstr *MI); /// Insert branches between prologs, kernel and epilogs. void fixupBranches(); /// Create a poor-man's LCSSA by cloning only the PHIs from the kernel block /// to a block dominated by all prologs and epilogs. This allows us to treat /// the loop exiting block as any other kernel clone. MachineBasicBlock *CreateLCSSAExitingBlock(); /// Helper to get the stage of an instruction in the schedule. unsigned getStage(MachineInstr *MI) { if (CanonicalMIs.count(MI)) MI = CanonicalMIs[MI]; return Schedule.getStage(MI); } /// Helper function to find the right canonical register for a phi instruction /// coming from a peeled out prologue. Register getPhiCanonicalReg(MachineInstr* CanonicalPhi, MachineInstr* Phi); /// Target loop info before kernel peeling. std::unique_ptr<TargetInstrInfo::PipelinerLoopInfo> LoopInfo; }; /// Expander that simply annotates each scheduled instruction with a post-instr /// symbol that can be consumed by the ModuloScheduleTest pass. /// /// The post-instr symbol is a way of annotating an instruction that can be /// roundtripped in MIR. The syntax is: /// MYINST %0, post-instr-symbol <mcsymbol Stage-1_Cycle-5> class ModuloScheduleTestAnnotater { MachineFunction &MF; ModuloSchedule &S; public: ModuloScheduleTestAnnotater(MachineFunction &MF, ModuloSchedule &S) : MF(MF), S(S) {} /// Performs the annotation. void annotate(); }; } // end namespace llvm #endif // LLVM_LIB_CODEGEN_MODULOSCHEDULE_H
Upload File
Create Folder