1343171Sdim//===- MachinePipeliner.h - Machine Software Pipeliner Pass -------------===// 2343171Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6343171Sdim// 7343171Sdim//===----------------------------------------------------------------------===// 8343171Sdim// 9343171Sdim// An implementation of the Swing Modulo Scheduling (SMS) software pipeliner. 10343171Sdim// 11343171Sdim// Software pipelining (SWP) is an instruction scheduling technique for loops 12343171Sdim// that overlap loop iterations and exploits ILP via a compiler transformation. 13343171Sdim// 14343171Sdim// Swing Modulo Scheduling is an implementation of software pipelining 15343171Sdim// that generates schedules that are near optimal in terms of initiation 16343171Sdim// interval, register requirements, and stage count. See the papers: 17343171Sdim// 18343171Sdim// "Swing Modulo Scheduling: A Lifetime-Sensitive Approach", by J. Llosa, 19343171Sdim// A. Gonzalez, E. Ayguade, and M. Valero. In PACT '96 Proceedings of the 1996 20343171Sdim// Conference on Parallel Architectures and Compilation Techiniques. 21343171Sdim// 22343171Sdim// "Lifetime-Sensitive Modulo Scheduling in a Production Environment", by J. 23343171Sdim// Llosa, E. Ayguade, A. Gonzalez, M. Valero, and J. Eckhardt. In IEEE 24343171Sdim// Transactions on Computers, Vol. 50, No. 3, 2001. 25343171Sdim// 26343171Sdim// "An Implementation of Swing Modulo Scheduling With Extensions for 27343171Sdim// Superblocks", by T. Lattner, Master's Thesis, University of Illinois at 28343171Sdim// Urbana-Champaign, 2005. 29343171Sdim// 30343171Sdim// 31343171Sdim// The SMS algorithm consists of three main steps after computing the minimal 32343171Sdim// initiation interval (MII). 33343171Sdim// 1) Analyze the dependence graph and compute information about each 34343171Sdim// instruction in the graph. 35343171Sdim// 2) Order the nodes (instructions) by priority based upon the heuristics 36343171Sdim// described in the algorithm. 37343171Sdim// 3) Attempt to schedule the nodes in the specified order using the MII. 38343171Sdim// 39343171Sdim//===----------------------------------------------------------------------===// 40343171Sdim#ifndef LLVM_LIB_CODEGEN_MACHINEPIPELINER_H 41343171Sdim#define LLVM_LIB_CODEGEN_MACHINEPIPELINER_H 42343171Sdim 43360784Sdim#include "llvm/Analysis/AliasAnalysis.h" 44360784Sdim 45343171Sdim#include "llvm/CodeGen/MachineDominators.h" 46343171Sdim#include "llvm/CodeGen/RegisterClassInfo.h" 47343171Sdim#include "llvm/CodeGen/ScheduleDAGInstrs.h" 48343171Sdim#include "llvm/CodeGen/TargetInstrInfo.h" 49360784Sdim#include "llvm/InitializePasses.h" 50343171Sdim 51343171Sdimnamespace llvm { 52343171Sdim 53343171Sdimclass NodeSet; 54343171Sdimclass SMSchedule; 55343171Sdim 56343171Sdimextern cl::opt<bool> SwpEnableCopyToPhi; 57343171Sdim 58343171Sdim/// The main class in the implementation of the target independent 59343171Sdim/// software pipeliner pass. 60343171Sdimclass MachinePipeliner : public MachineFunctionPass { 61343171Sdimpublic: 62343171Sdim MachineFunction *MF = nullptr; 63343171Sdim const MachineLoopInfo *MLI = nullptr; 64343171Sdim const MachineDominatorTree *MDT = nullptr; 65343171Sdim const InstrItineraryData *InstrItins; 66343171Sdim const TargetInstrInfo *TII = nullptr; 67343171Sdim RegisterClassInfo RegClassInfo; 68353358Sdim bool disabledByPragma = false; 69353358Sdim unsigned II_setByPragma = 0; 70343171Sdim 71343171Sdim#ifndef NDEBUG 72343171Sdim static int NumTries; 73343171Sdim#endif 74343171Sdim 75343171Sdim /// Cache the target analysis information about the loop. 76343171Sdim struct LoopInfo { 77343171Sdim MachineBasicBlock *TBB = nullptr; 78343171Sdim MachineBasicBlock *FBB = nullptr; 79343171Sdim SmallVector<MachineOperand, 4> BrCond; 80343171Sdim MachineInstr *LoopInductionVar = nullptr; 81343171Sdim MachineInstr *LoopCompare = nullptr; 82343171Sdim }; 83343171Sdim LoopInfo LI; 84343171Sdim 85343171Sdim static char ID; 86343171Sdim 87343171Sdim MachinePipeliner() : MachineFunctionPass(ID) { 88343171Sdim initializeMachinePipelinerPass(*PassRegistry::getPassRegistry()); 89343171Sdim } 90343171Sdim 91343171Sdim bool runOnMachineFunction(MachineFunction &MF) override; 92343171Sdim 93343171Sdim void getAnalysisUsage(AnalysisUsage &AU) const override { 94343171Sdim AU.addRequired<AAResultsWrapperPass>(); 95343171Sdim AU.addPreserved<AAResultsWrapperPass>(); 96343171Sdim AU.addRequired<MachineLoopInfo>(); 97343171Sdim AU.addRequired<MachineDominatorTree>(); 98343171Sdim AU.addRequired<LiveIntervals>(); 99343171Sdim MachineFunctionPass::getAnalysisUsage(AU); 100343171Sdim } 101343171Sdim 102343171Sdimprivate: 103343171Sdim void preprocessPhiNodes(MachineBasicBlock &B); 104343171Sdim bool canPipelineLoop(MachineLoop &L); 105343171Sdim bool scheduleLoop(MachineLoop &L); 106343171Sdim bool swingModuloScheduler(MachineLoop &L); 107353358Sdim void setPragmaPipelineOptions(MachineLoop &L); 108343171Sdim}; 109343171Sdim 110343171Sdim/// This class builds the dependence graph for the instructions in a loop, 111343171Sdim/// and attempts to schedule the instructions using the SMS algorithm. 112343171Sdimclass SwingSchedulerDAG : public ScheduleDAGInstrs { 113343171Sdim MachinePipeliner &Pass; 114343171Sdim /// The minimum initiation interval between iterations for this schedule. 115343171Sdim unsigned MII = 0; 116353358Sdim /// The maximum initiation interval between iterations for this schedule. 117353358Sdim unsigned MAX_II = 0; 118343171Sdim /// Set to true if a valid pipelined schedule is found for the loop. 119343171Sdim bool Scheduled = false; 120343171Sdim MachineLoop &Loop; 121343171Sdim LiveIntervals &LIS; 122343171Sdim const RegisterClassInfo &RegClassInfo; 123353358Sdim unsigned II_setByPragma = 0; 124343171Sdim 125343171Sdim /// A toplogical ordering of the SUnits, which is needed for changing 126343171Sdim /// dependences and iterating over the SUnits. 127343171Sdim ScheduleDAGTopologicalSort Topo; 128343171Sdim 129343171Sdim struct NodeInfo { 130343171Sdim int ASAP = 0; 131343171Sdim int ALAP = 0; 132343171Sdim int ZeroLatencyDepth = 0; 133343171Sdim int ZeroLatencyHeight = 0; 134343171Sdim 135343171Sdim NodeInfo() = default; 136343171Sdim }; 137343171Sdim /// Computed properties for each node in the graph. 138343171Sdim std::vector<NodeInfo> ScheduleInfo; 139343171Sdim 140343171Sdim enum OrderKind { BottomUp = 0, TopDown = 1 }; 141343171Sdim /// Computed node ordering for scheduling. 142343171Sdim SetVector<SUnit *> NodeOrder; 143343171Sdim 144343171Sdim using NodeSetType = SmallVector<NodeSet, 8>; 145343171Sdim using ValueMapTy = DenseMap<unsigned, unsigned>; 146343171Sdim using MBBVectorTy = SmallVectorImpl<MachineBasicBlock *>; 147343171Sdim using InstrMapTy = DenseMap<MachineInstr *, MachineInstr *>; 148343171Sdim 149343171Sdim /// Instructions to change when emitting the final schedule. 150343171Sdim DenseMap<SUnit *, std::pair<unsigned, int64_t>> InstrChanges; 151343171Sdim 152343171Sdim /// We may create a new instruction, so remember it because it 153343171Sdim /// must be deleted when the pass is finished. 154360784Sdim DenseMap<MachineInstr*, MachineInstr *> NewMIs; 155343171Sdim 156343171Sdim /// Ordered list of DAG postprocessing steps. 157343171Sdim std::vector<std::unique_ptr<ScheduleDAGMutation>> Mutations; 158343171Sdim 159343171Sdim /// Helper class to implement Johnson's circuit finding algorithm. 160343171Sdim class Circuits { 161343171Sdim std::vector<SUnit> &SUnits; 162343171Sdim SetVector<SUnit *> Stack; 163343171Sdim BitVector Blocked; 164343171Sdim SmallVector<SmallPtrSet<SUnit *, 4>, 10> B; 165343171Sdim SmallVector<SmallVector<int, 4>, 16> AdjK; 166343171Sdim // Node to Index from ScheduleDAGTopologicalSort 167343171Sdim std::vector<int> *Node2Idx; 168343171Sdim unsigned NumPaths; 169343171Sdim static unsigned MaxPaths; 170343171Sdim 171343171Sdim public: 172343171Sdim Circuits(std::vector<SUnit> &SUs, ScheduleDAGTopologicalSort &Topo) 173343171Sdim : SUnits(SUs), Blocked(SUs.size()), B(SUs.size()), AdjK(SUs.size()) { 174343171Sdim Node2Idx = new std::vector<int>(SUs.size()); 175343171Sdim unsigned Idx = 0; 176343171Sdim for (const auto &NodeNum : Topo) 177343171Sdim Node2Idx->at(NodeNum) = Idx++; 178343171Sdim } 179343171Sdim 180343171Sdim ~Circuits() { delete Node2Idx; } 181343171Sdim 182343171Sdim /// Reset the data structures used in the circuit algorithm. 183343171Sdim void reset() { 184343171Sdim Stack.clear(); 185343171Sdim Blocked.reset(); 186343171Sdim B.assign(SUnits.size(), SmallPtrSet<SUnit *, 4>()); 187343171Sdim NumPaths = 0; 188343171Sdim } 189343171Sdim 190343171Sdim void createAdjacencyStructure(SwingSchedulerDAG *DAG); 191343171Sdim bool circuit(int V, int S, NodeSetType &NodeSets, bool HasBackedge = false); 192343171Sdim void unblock(int U); 193343171Sdim }; 194343171Sdim 195343171Sdim struct CopyToPhiMutation : public ScheduleDAGMutation { 196343171Sdim void apply(ScheduleDAGInstrs *DAG) override; 197343171Sdim }; 198343171Sdim 199343171Sdimpublic: 200343171Sdim SwingSchedulerDAG(MachinePipeliner &P, MachineLoop &L, LiveIntervals &lis, 201353358Sdim const RegisterClassInfo &rci, unsigned II) 202343171Sdim : ScheduleDAGInstrs(*P.MF, P.MLI, false), Pass(P), Loop(L), LIS(lis), 203353358Sdim RegClassInfo(rci), II_setByPragma(II), Topo(SUnits, &ExitSU) { 204343171Sdim P.MF->getSubtarget().getSMSMutations(Mutations); 205343171Sdim if (SwpEnableCopyToPhi) 206360784Sdim Mutations.push_back(std::make_unique<CopyToPhiMutation>()); 207343171Sdim } 208343171Sdim 209343171Sdim void schedule() override; 210343171Sdim void finishBlock() override; 211343171Sdim 212343171Sdim /// Return true if the loop kernel has been scheduled. 213343171Sdim bool hasNewSchedule() { return Scheduled; } 214343171Sdim 215343171Sdim /// Return the earliest time an instruction may be scheduled. 216343171Sdim int getASAP(SUnit *Node) { return ScheduleInfo[Node->NodeNum].ASAP; } 217343171Sdim 218343171Sdim /// Return the latest time an instruction my be scheduled. 219343171Sdim int getALAP(SUnit *Node) { return ScheduleInfo[Node->NodeNum].ALAP; } 220343171Sdim 221343171Sdim /// The mobility function, which the number of slots in which 222343171Sdim /// an instruction may be scheduled. 223343171Sdim int getMOV(SUnit *Node) { return getALAP(Node) - getASAP(Node); } 224343171Sdim 225343171Sdim /// The depth, in the dependence graph, for a node. 226343171Sdim unsigned getDepth(SUnit *Node) { return Node->getDepth(); } 227343171Sdim 228343171Sdim /// The maximum unweighted length of a path from an arbitrary node to the 229343171Sdim /// given node in which each edge has latency 0 230343171Sdim int getZeroLatencyDepth(SUnit *Node) { 231343171Sdim return ScheduleInfo[Node->NodeNum].ZeroLatencyDepth; 232343171Sdim } 233343171Sdim 234343171Sdim /// The height, in the dependence graph, for a node. 235343171Sdim unsigned getHeight(SUnit *Node) { return Node->getHeight(); } 236343171Sdim 237343171Sdim /// The maximum unweighted length of a path from the given node to an 238343171Sdim /// arbitrary node in which each edge has latency 0 239343171Sdim int getZeroLatencyHeight(SUnit *Node) { 240343171Sdim return ScheduleInfo[Node->NodeNum].ZeroLatencyHeight; 241343171Sdim } 242343171Sdim 243343171Sdim /// Return true if the dependence is a back-edge in the data dependence graph. 244343171Sdim /// Since the DAG doesn't contain cycles, we represent a cycle in the graph 245343171Sdim /// using an anti dependence from a Phi to an instruction. 246343171Sdim bool isBackedge(SUnit *Source, const SDep &Dep) { 247343171Sdim if (Dep.getKind() != SDep::Anti) 248343171Sdim return false; 249343171Sdim return Source->getInstr()->isPHI() || Dep.getSUnit()->getInstr()->isPHI(); 250343171Sdim } 251343171Sdim 252343171Sdim bool isLoopCarriedDep(SUnit *Source, const SDep &Dep, bool isSucc = true); 253343171Sdim 254343171Sdim /// The distance function, which indicates that operation V of iteration I 255343171Sdim /// depends on operations U of iteration I-distance. 256343171Sdim unsigned getDistance(SUnit *U, SUnit *V, const SDep &Dep) { 257343171Sdim // Instructions that feed a Phi have a distance of 1. Computing larger 258343171Sdim // values for arrays requires data dependence information. 259343171Sdim if (V->getInstr()->isPHI() && Dep.getKind() == SDep::Anti) 260343171Sdim return 1; 261343171Sdim return 0; 262343171Sdim } 263343171Sdim 264343171Sdim void applyInstrChange(MachineInstr *MI, SMSchedule &Schedule); 265343171Sdim 266343171Sdim void fixupRegisterOverlaps(std::deque<SUnit *> &Instrs); 267343171Sdim 268343171Sdim /// Return the new base register that was stored away for the changed 269343171Sdim /// instruction. 270343171Sdim unsigned getInstrBaseReg(SUnit *SU) { 271343171Sdim DenseMap<SUnit *, std::pair<unsigned, int64_t>>::iterator It = 272343171Sdim InstrChanges.find(SU); 273343171Sdim if (It != InstrChanges.end()) 274343171Sdim return It->second.first; 275343171Sdim return 0; 276343171Sdim } 277343171Sdim 278343171Sdim void addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation) { 279343171Sdim Mutations.push_back(std::move(Mutation)); 280343171Sdim } 281343171Sdim 282343171Sdim static bool classof(const ScheduleDAGInstrs *DAG) { return true; } 283343171Sdim 284343171Sdimprivate: 285343171Sdim void addLoopCarriedDependences(AliasAnalysis *AA); 286343171Sdim void updatePhiDependences(); 287343171Sdim void changeDependences(); 288343171Sdim unsigned calculateResMII(); 289343171Sdim unsigned calculateRecMII(NodeSetType &RecNodeSets); 290343171Sdim void findCircuits(NodeSetType &NodeSets); 291343171Sdim void fuseRecs(NodeSetType &NodeSets); 292343171Sdim void removeDuplicateNodes(NodeSetType &NodeSets); 293343171Sdim void computeNodeFunctions(NodeSetType &NodeSets); 294343171Sdim void registerPressureFilter(NodeSetType &NodeSets); 295343171Sdim void colocateNodeSets(NodeSetType &NodeSets); 296343171Sdim void checkNodeSets(NodeSetType &NodeSets); 297343171Sdim void groupRemainingNodes(NodeSetType &NodeSets); 298343171Sdim void addConnectedNodes(SUnit *SU, NodeSet &NewSet, 299343171Sdim SetVector<SUnit *> &NodesAdded); 300343171Sdim void computeNodeOrder(NodeSetType &NodeSets); 301343171Sdim void checkValidNodeOrder(const NodeSetType &Circuits) const; 302343171Sdim bool schedulePipeline(SMSchedule &Schedule); 303343171Sdim bool computeDelta(MachineInstr &MI, unsigned &Delta); 304343171Sdim MachineInstr *findDefInLoop(unsigned Reg); 305343171Sdim bool canUseLastOffsetValue(MachineInstr *MI, unsigned &BasePos, 306343171Sdim unsigned &OffsetPos, unsigned &NewBase, 307343171Sdim int64_t &NewOffset); 308343171Sdim void postprocessDAG(); 309353358Sdim /// Set the Minimum Initiation Interval for this schedule attempt. 310353358Sdim void setMII(unsigned ResMII, unsigned RecMII); 311353358Sdim /// Set the Maximum Initiation Interval for this schedule attempt. 312353358Sdim void setMAX_II(); 313343171Sdim}; 314343171Sdim 315343171Sdim/// A NodeSet contains a set of SUnit DAG nodes with additional information 316343171Sdim/// that assigns a priority to the set. 317343171Sdimclass NodeSet { 318343171Sdim SetVector<SUnit *> Nodes; 319343171Sdim bool HasRecurrence = false; 320343171Sdim unsigned RecMII = 0; 321343171Sdim int MaxMOV = 0; 322343171Sdim unsigned MaxDepth = 0; 323343171Sdim unsigned Colocate = 0; 324343171Sdim SUnit *ExceedPressure = nullptr; 325343171Sdim unsigned Latency = 0; 326343171Sdim 327343171Sdimpublic: 328343171Sdim using iterator = SetVector<SUnit *>::const_iterator; 329343171Sdim 330343171Sdim NodeSet() = default; 331343171Sdim NodeSet(iterator S, iterator E) : Nodes(S, E), HasRecurrence(true) { 332343171Sdim Latency = 0; 333343171Sdim for (unsigned i = 0, e = Nodes.size(); i < e; ++i) 334343171Sdim for (const SDep &Succ : Nodes[i]->Succs) 335343171Sdim if (Nodes.count(Succ.getSUnit())) 336343171Sdim Latency += Succ.getLatency(); 337343171Sdim } 338343171Sdim 339343171Sdim bool insert(SUnit *SU) { return Nodes.insert(SU); } 340343171Sdim 341343171Sdim void insert(iterator S, iterator E) { Nodes.insert(S, E); } 342343171Sdim 343343171Sdim template <typename UnaryPredicate> bool remove_if(UnaryPredicate P) { 344343171Sdim return Nodes.remove_if(P); 345343171Sdim } 346343171Sdim 347343171Sdim unsigned count(SUnit *SU) const { return Nodes.count(SU); } 348343171Sdim 349343171Sdim bool hasRecurrence() { return HasRecurrence; }; 350343171Sdim 351343171Sdim unsigned size() const { return Nodes.size(); } 352343171Sdim 353343171Sdim bool empty() const { return Nodes.empty(); } 354343171Sdim 355343171Sdim SUnit *getNode(unsigned i) const { return Nodes[i]; }; 356343171Sdim 357343171Sdim void setRecMII(unsigned mii) { RecMII = mii; }; 358343171Sdim 359343171Sdim void setColocate(unsigned c) { Colocate = c; }; 360343171Sdim 361343171Sdim void setExceedPressure(SUnit *SU) { ExceedPressure = SU; } 362343171Sdim 363343171Sdim bool isExceedSU(SUnit *SU) { return ExceedPressure == SU; } 364343171Sdim 365343171Sdim int compareRecMII(NodeSet &RHS) { return RecMII - RHS.RecMII; } 366343171Sdim 367343171Sdim int getRecMII() { return RecMII; } 368343171Sdim 369343171Sdim /// Summarize node functions for the entire node set. 370343171Sdim void computeNodeSetInfo(SwingSchedulerDAG *SSD) { 371343171Sdim for (SUnit *SU : *this) { 372343171Sdim MaxMOV = std::max(MaxMOV, SSD->getMOV(SU)); 373343171Sdim MaxDepth = std::max(MaxDepth, SSD->getDepth(SU)); 374343171Sdim } 375343171Sdim } 376343171Sdim 377343171Sdim unsigned getLatency() { return Latency; } 378343171Sdim 379343171Sdim unsigned getMaxDepth() { return MaxDepth; } 380343171Sdim 381343171Sdim void clear() { 382343171Sdim Nodes.clear(); 383343171Sdim RecMII = 0; 384343171Sdim HasRecurrence = false; 385343171Sdim MaxMOV = 0; 386343171Sdim MaxDepth = 0; 387343171Sdim Colocate = 0; 388343171Sdim ExceedPressure = nullptr; 389343171Sdim } 390343171Sdim 391343171Sdim operator SetVector<SUnit *> &() { return Nodes; } 392343171Sdim 393343171Sdim /// Sort the node sets by importance. First, rank them by recurrence MII, 394343171Sdim /// then by mobility (least mobile done first), and finally by depth. 395343171Sdim /// Each node set may contain a colocate value which is used as the first 396343171Sdim /// tie breaker, if it's set. 397343171Sdim bool operator>(const NodeSet &RHS) const { 398343171Sdim if (RecMII == RHS.RecMII) { 399343171Sdim if (Colocate != 0 && RHS.Colocate != 0 && Colocate != RHS.Colocate) 400343171Sdim return Colocate < RHS.Colocate; 401343171Sdim if (MaxMOV == RHS.MaxMOV) 402343171Sdim return MaxDepth > RHS.MaxDepth; 403343171Sdim return MaxMOV < RHS.MaxMOV; 404343171Sdim } 405343171Sdim return RecMII > RHS.RecMII; 406343171Sdim } 407343171Sdim 408343171Sdim bool operator==(const NodeSet &RHS) const { 409343171Sdim return RecMII == RHS.RecMII && MaxMOV == RHS.MaxMOV && 410343171Sdim MaxDepth == RHS.MaxDepth; 411343171Sdim } 412343171Sdim 413343171Sdim bool operator!=(const NodeSet &RHS) const { return !operator==(RHS); } 414343171Sdim 415343171Sdim iterator begin() { return Nodes.begin(); } 416343171Sdim iterator end() { return Nodes.end(); } 417343171Sdim void print(raw_ostream &os) const; 418343171Sdim 419343171Sdim#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 420343171Sdim LLVM_DUMP_METHOD void dump() const; 421343171Sdim#endif 422343171Sdim}; 423343171Sdim 424353358Sdim// 16 was selected based on the number of ProcResource kinds for all 425353358Sdim// existing Subtargets, so that SmallVector don't need to resize too often. 426353358Sdimstatic const int DefaultProcResSize = 16; 427353358Sdim 428353358Sdimclass ResourceManager { 429353358Sdimprivate: 430353358Sdim const MCSubtargetInfo *STI; 431353358Sdim const MCSchedModel &SM; 432353358Sdim const bool UseDFA; 433353358Sdim std::unique_ptr<DFAPacketizer> DFAResources; 434353358Sdim /// Each processor resource is associated with a so-called processor resource 435353358Sdim /// mask. This vector allows to correlate processor resource IDs with 436353358Sdim /// processor resource masks. There is exactly one element per each processor 437353358Sdim /// resource declared by the scheduling model. 438353358Sdim llvm::SmallVector<uint64_t, DefaultProcResSize> ProcResourceMasks; 439353358Sdim 440353358Sdim llvm::SmallVector<uint64_t, DefaultProcResSize> ProcResourceCount; 441353358Sdim 442353358Sdimpublic: 443353358Sdim ResourceManager(const TargetSubtargetInfo *ST) 444353358Sdim : STI(ST), SM(ST->getSchedModel()), UseDFA(ST->useDFAforSMS()), 445353358Sdim ProcResourceMasks(SM.getNumProcResourceKinds(), 0), 446353358Sdim ProcResourceCount(SM.getNumProcResourceKinds(), 0) { 447353358Sdim if (UseDFA) 448353358Sdim DFAResources.reset(ST->getInstrInfo()->CreateTargetScheduleState(*ST)); 449353358Sdim initProcResourceVectors(SM, ProcResourceMasks); 450353358Sdim } 451353358Sdim 452353358Sdim void initProcResourceVectors(const MCSchedModel &SM, 453353358Sdim SmallVectorImpl<uint64_t> &Masks); 454353358Sdim /// Check if the resources occupied by a MCInstrDesc are available in 455353358Sdim /// the current state. 456353358Sdim bool canReserveResources(const MCInstrDesc *MID) const; 457353358Sdim 458353358Sdim /// Reserve the resources occupied by a MCInstrDesc and change the current 459353358Sdim /// state to reflect that change. 460353358Sdim void reserveResources(const MCInstrDesc *MID); 461353358Sdim 462353358Sdim /// Check if the resources occupied by a machine instruction are available 463353358Sdim /// in the current state. 464353358Sdim bool canReserveResources(const MachineInstr &MI) const; 465353358Sdim 466353358Sdim /// Reserve the resources occupied by a machine instruction and change the 467353358Sdim /// current state to reflect that change. 468353358Sdim void reserveResources(const MachineInstr &MI); 469353358Sdim 470353358Sdim /// Reset the state 471353358Sdim void clearResources(); 472353358Sdim}; 473353358Sdim 474343171Sdim/// This class represents the scheduled code. The main data structure is a 475343171Sdim/// map from scheduled cycle to instructions. During scheduling, the 476343171Sdim/// data structure explicitly represents all stages/iterations. When 477343171Sdim/// the algorithm finshes, the schedule is collapsed into a single stage, 478343171Sdim/// which represents instructions from different loop iterations. 479343171Sdim/// 480343171Sdim/// The SMS algorithm allows negative values for cycles, so the first cycle 481343171Sdim/// in the schedule is the smallest cycle value. 482343171Sdimclass SMSchedule { 483343171Sdimprivate: 484343171Sdim /// Map from execution cycle to instructions. 485343171Sdim DenseMap<int, std::deque<SUnit *>> ScheduledInstrs; 486343171Sdim 487343171Sdim /// Map from instruction to execution cycle. 488343171Sdim std::map<SUnit *, int> InstrToCycle; 489343171Sdim 490343171Sdim /// Keep track of the first cycle value in the schedule. It starts 491343171Sdim /// as zero, but the algorithm allows negative values. 492343171Sdim int FirstCycle = 0; 493343171Sdim 494343171Sdim /// Keep track of the last cycle value in the schedule. 495343171Sdim int LastCycle = 0; 496343171Sdim 497343171Sdim /// The initiation interval (II) for the schedule. 498343171Sdim int InitiationInterval = 0; 499343171Sdim 500343171Sdim /// Target machine information. 501343171Sdim const TargetSubtargetInfo &ST; 502343171Sdim 503343171Sdim /// Virtual register information. 504343171Sdim MachineRegisterInfo &MRI; 505343171Sdim 506353358Sdim ResourceManager ProcItinResources; 507343171Sdim 508343171Sdimpublic: 509343171Sdim SMSchedule(MachineFunction *mf) 510353358Sdim : ST(mf->getSubtarget()), MRI(mf->getRegInfo()), ProcItinResources(&ST) {} 511343171Sdim 512343171Sdim void reset() { 513343171Sdim ScheduledInstrs.clear(); 514343171Sdim InstrToCycle.clear(); 515343171Sdim FirstCycle = 0; 516343171Sdim LastCycle = 0; 517343171Sdim InitiationInterval = 0; 518343171Sdim } 519343171Sdim 520343171Sdim /// Set the initiation interval for this schedule. 521343171Sdim void setInitiationInterval(int ii) { InitiationInterval = ii; } 522343171Sdim 523343171Sdim /// Return the first cycle in the completed schedule. This 524343171Sdim /// can be a negative value. 525343171Sdim int getFirstCycle() const { return FirstCycle; } 526343171Sdim 527343171Sdim /// Return the last cycle in the finalized schedule. 528343171Sdim int getFinalCycle() const { return FirstCycle + InitiationInterval - 1; } 529343171Sdim 530343171Sdim /// Return the cycle of the earliest scheduled instruction in the dependence 531343171Sdim /// chain. 532343171Sdim int earliestCycleInChain(const SDep &Dep); 533343171Sdim 534343171Sdim /// Return the cycle of the latest scheduled instruction in the dependence 535343171Sdim /// chain. 536343171Sdim int latestCycleInChain(const SDep &Dep); 537343171Sdim 538343171Sdim void computeStart(SUnit *SU, int *MaxEarlyStart, int *MinLateStart, 539343171Sdim int *MinEnd, int *MaxStart, int II, SwingSchedulerDAG *DAG); 540343171Sdim bool insert(SUnit *SU, int StartCycle, int EndCycle, int II); 541343171Sdim 542343171Sdim /// Iterators for the cycle to instruction map. 543343171Sdim using sched_iterator = DenseMap<int, std::deque<SUnit *>>::iterator; 544343171Sdim using const_sched_iterator = 545343171Sdim DenseMap<int, std::deque<SUnit *>>::const_iterator; 546343171Sdim 547343171Sdim /// Return true if the instruction is scheduled at the specified stage. 548343171Sdim bool isScheduledAtStage(SUnit *SU, unsigned StageNum) { 549343171Sdim return (stageScheduled(SU) == (int)StageNum); 550343171Sdim } 551343171Sdim 552343171Sdim /// Return the stage for a scheduled instruction. Return -1 if 553343171Sdim /// the instruction has not been scheduled. 554343171Sdim int stageScheduled(SUnit *SU) const { 555343171Sdim std::map<SUnit *, int>::const_iterator it = InstrToCycle.find(SU); 556343171Sdim if (it == InstrToCycle.end()) 557343171Sdim return -1; 558343171Sdim return (it->second - FirstCycle) / InitiationInterval; 559343171Sdim } 560343171Sdim 561343171Sdim /// Return the cycle for a scheduled instruction. This function normalizes 562343171Sdim /// the first cycle to be 0. 563343171Sdim unsigned cycleScheduled(SUnit *SU) const { 564343171Sdim std::map<SUnit *, int>::const_iterator it = InstrToCycle.find(SU); 565343171Sdim assert(it != InstrToCycle.end() && "Instruction hasn't been scheduled."); 566343171Sdim return (it->second - FirstCycle) % InitiationInterval; 567343171Sdim } 568343171Sdim 569343171Sdim /// Return the maximum stage count needed for this schedule. 570343171Sdim unsigned getMaxStageCount() { 571343171Sdim return (LastCycle - FirstCycle) / InitiationInterval; 572343171Sdim } 573343171Sdim 574343171Sdim /// Return the instructions that are scheduled at the specified cycle. 575343171Sdim std::deque<SUnit *> &getInstructions(int cycle) { 576343171Sdim return ScheduledInstrs[cycle]; 577343171Sdim } 578343171Sdim 579343171Sdim bool isValidSchedule(SwingSchedulerDAG *SSD); 580343171Sdim void finalizeSchedule(SwingSchedulerDAG *SSD); 581343171Sdim void orderDependence(SwingSchedulerDAG *SSD, SUnit *SU, 582343171Sdim std::deque<SUnit *> &Insts); 583343171Sdim bool isLoopCarried(SwingSchedulerDAG *SSD, MachineInstr &Phi); 584343171Sdim bool isLoopCarriedDefOfUse(SwingSchedulerDAG *SSD, MachineInstr *Def, 585343171Sdim MachineOperand &MO); 586343171Sdim void print(raw_ostream &os) const; 587343171Sdim void dump() const; 588343171Sdim}; 589343171Sdim 590343171Sdim} // end namespace llvm 591343171Sdim 592343171Sdim#endif // LLVM_LIB_CODEGEN_MACHINEPIPELINER_H 593