10b57cec5SDimitry Andric //===- MachinePipeliner.h - Machine Software Pipeliner Pass -------------===// 20b57cec5SDimitry Andric // 30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 60b57cec5SDimitry Andric // 70b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 80b57cec5SDimitry Andric // 90b57cec5SDimitry Andric // An implementation of the Swing Modulo Scheduling (SMS) software pipeliner. 100b57cec5SDimitry Andric // 110b57cec5SDimitry Andric // Software pipelining (SWP) is an instruction scheduling technique for loops 120b57cec5SDimitry Andric // that overlap loop iterations and exploits ILP via a compiler transformation. 130b57cec5SDimitry Andric // 140b57cec5SDimitry Andric // Swing Modulo Scheduling is an implementation of software pipelining 150b57cec5SDimitry Andric // that generates schedules that are near optimal in terms of initiation 160b57cec5SDimitry Andric // interval, register requirements, and stage count. See the papers: 170b57cec5SDimitry Andric // 180b57cec5SDimitry Andric // "Swing Modulo Scheduling: A Lifetime-Sensitive Approach", by J. Llosa, 190b57cec5SDimitry Andric // A. Gonzalez, E. Ayguade, and M. Valero. In PACT '96 Proceedings of the 1996 200b57cec5SDimitry Andric // Conference on Parallel Architectures and Compilation Techiniques. 210b57cec5SDimitry Andric // 220b57cec5SDimitry Andric // "Lifetime-Sensitive Modulo Scheduling in a Production Environment", by J. 230b57cec5SDimitry Andric // Llosa, E. Ayguade, A. Gonzalez, M. Valero, and J. Eckhardt. In IEEE 240b57cec5SDimitry Andric // Transactions on Computers, Vol. 50, No. 3, 2001. 250b57cec5SDimitry Andric // 260b57cec5SDimitry Andric // "An Implementation of Swing Modulo Scheduling With Extensions for 270b57cec5SDimitry Andric // Superblocks", by T. Lattner, Master's Thesis, University of Illinois at 280b57cec5SDimitry Andric // Urbana-Champaign, 2005. 290b57cec5SDimitry Andric // 300b57cec5SDimitry Andric // 310b57cec5SDimitry Andric // The SMS algorithm consists of three main steps after computing the minimal 320b57cec5SDimitry Andric // initiation interval (MII). 330b57cec5SDimitry Andric // 1) Analyze the dependence graph and compute information about each 340b57cec5SDimitry Andric // instruction in the graph. 350b57cec5SDimitry Andric // 2) Order the nodes (instructions) by priority based upon the heuristics 360b57cec5SDimitry Andric // described in the algorithm. 370b57cec5SDimitry Andric // 3) Attempt to schedule the nodes in the specified order using the MII. 380b57cec5SDimitry Andric // 390b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 40fe6060f1SDimitry Andric #ifndef LLVM_CODEGEN_MACHINEPIPELINER_H 41fe6060f1SDimitry Andric #define LLVM_CODEGEN_MACHINEPIPELINER_H 420b57cec5SDimitry Andric 4381ad6265SDimitry Andric #include "llvm/ADT/SetVector.h" 44bdd1243dSDimitry Andric #include "llvm/CodeGen/DFAPacketizer.h" 450b57cec5SDimitry Andric #include "llvm/CodeGen/MachineDominators.h" 465ffd83dbSDimitry Andric #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h" 470b57cec5SDimitry Andric #include "llvm/CodeGen/RegisterClassInfo.h" 480b57cec5SDimitry Andric #include "llvm/CodeGen/ScheduleDAGInstrs.h" 4981ad6265SDimitry Andric #include "llvm/CodeGen/ScheduleDAGMutation.h" 500b57cec5SDimitry Andric #include "llvm/CodeGen/TargetInstrInfo.h" 51480093f4SDimitry Andric #include "llvm/InitializePasses.h" 520b57cec5SDimitry Andric 5381ad6265SDimitry Andric #include <deque> 5481ad6265SDimitry Andric 550b57cec5SDimitry Andric namespace llvm { 560b57cec5SDimitry Andric 57e8d8bef9SDimitry Andric class AAResults; 580b57cec5SDimitry Andric class NodeSet; 590b57cec5SDimitry Andric class SMSchedule; 600b57cec5SDimitry Andric 610b57cec5SDimitry Andric extern cl::opt<bool> SwpEnableCopyToPhi; 62bdd1243dSDimitry Andric extern cl::opt<int> SwpForceIssueWidth; 630b57cec5SDimitry Andric 640b57cec5SDimitry Andric /// The main class in the implementation of the target independent 650b57cec5SDimitry Andric /// software pipeliner pass. 660b57cec5SDimitry Andric class MachinePipeliner : public MachineFunctionPass { 670b57cec5SDimitry Andric public: 680b57cec5SDimitry Andric MachineFunction *MF = nullptr; 695ffd83dbSDimitry Andric MachineOptimizationRemarkEmitter *ORE = nullptr; 700b57cec5SDimitry Andric const MachineLoopInfo *MLI = nullptr; 710b57cec5SDimitry Andric const MachineDominatorTree *MDT = nullptr; 7206c3fb27SDimitry Andric const InstrItineraryData *InstrItins = nullptr; 730b57cec5SDimitry Andric const TargetInstrInfo *TII = nullptr; 740b57cec5SDimitry Andric RegisterClassInfo RegClassInfo; 750b57cec5SDimitry Andric bool disabledByPragma = false; 760b57cec5SDimitry Andric unsigned II_setByPragma = 0; 770b57cec5SDimitry Andric 780b57cec5SDimitry Andric #ifndef NDEBUG 790b57cec5SDimitry Andric static int NumTries; 800b57cec5SDimitry Andric #endif 810b57cec5SDimitry Andric 820b57cec5SDimitry Andric /// Cache the target analysis information about the loop. 830b57cec5SDimitry Andric struct LoopInfo { 840b57cec5SDimitry Andric MachineBasicBlock *TBB = nullptr; 850b57cec5SDimitry Andric MachineBasicBlock *FBB = nullptr; 860b57cec5SDimitry Andric SmallVector<MachineOperand, 4> BrCond; 870b57cec5SDimitry Andric MachineInstr *LoopInductionVar = nullptr; 880b57cec5SDimitry Andric MachineInstr *LoopCompare = nullptr; 8981ad6265SDimitry Andric std::unique_ptr<TargetInstrInfo::PipelinerLoopInfo> LoopPipelinerInfo = 9081ad6265SDimitry Andric nullptr; 910b57cec5SDimitry Andric }; 920b57cec5SDimitry Andric LoopInfo LI; 930b57cec5SDimitry Andric 940b57cec5SDimitry Andric static char ID; 950b57cec5SDimitry Andric MachinePipeliner()960b57cec5SDimitry Andric MachinePipeliner() : MachineFunctionPass(ID) { 970b57cec5SDimitry Andric initializeMachinePipelinerPass(*PassRegistry::getPassRegistry()); 980b57cec5SDimitry Andric } 990b57cec5SDimitry Andric 1000b57cec5SDimitry Andric bool runOnMachineFunction(MachineFunction &MF) override; 1010b57cec5SDimitry Andric 102e8d8bef9SDimitry Andric void getAnalysisUsage(AnalysisUsage &AU) const override; 1030b57cec5SDimitry Andric 1040b57cec5SDimitry Andric private: 1050b57cec5SDimitry Andric void preprocessPhiNodes(MachineBasicBlock &B); 1060b57cec5SDimitry Andric bool canPipelineLoop(MachineLoop &L); 1070b57cec5SDimitry Andric bool scheduleLoop(MachineLoop &L); 1080b57cec5SDimitry Andric bool swingModuloScheduler(MachineLoop &L); 1090b57cec5SDimitry Andric void setPragmaPipelineOptions(MachineLoop &L); 1100b57cec5SDimitry Andric }; 1110b57cec5SDimitry Andric 1120b57cec5SDimitry Andric /// This class builds the dependence graph for the instructions in a loop, 1130b57cec5SDimitry Andric /// and attempts to schedule the instructions using the SMS algorithm. 1140b57cec5SDimitry Andric class SwingSchedulerDAG : public ScheduleDAGInstrs { 1150b57cec5SDimitry Andric MachinePipeliner &Pass; 1160b57cec5SDimitry Andric /// The minimum initiation interval between iterations for this schedule. 1170b57cec5SDimitry Andric unsigned MII = 0; 1180b57cec5SDimitry Andric /// The maximum initiation interval between iterations for this schedule. 1190b57cec5SDimitry Andric unsigned MAX_II = 0; 1200b57cec5SDimitry Andric /// Set to true if a valid pipelined schedule is found for the loop. 1210b57cec5SDimitry Andric bool Scheduled = false; 1220b57cec5SDimitry Andric MachineLoop &Loop; 1230b57cec5SDimitry Andric LiveIntervals &LIS; 1240b57cec5SDimitry Andric const RegisterClassInfo &RegClassInfo; 1250b57cec5SDimitry Andric unsigned II_setByPragma = 0; 12681ad6265SDimitry Andric TargetInstrInfo::PipelinerLoopInfo *LoopPipelinerInfo = nullptr; 1270b57cec5SDimitry Andric 1280b57cec5SDimitry Andric /// A toplogical ordering of the SUnits, which is needed for changing 1290b57cec5SDimitry Andric /// dependences and iterating over the SUnits. 1300b57cec5SDimitry Andric ScheduleDAGTopologicalSort Topo; 1310b57cec5SDimitry Andric 1320b57cec5SDimitry Andric struct NodeInfo { 1330b57cec5SDimitry Andric int ASAP = 0; 1340b57cec5SDimitry Andric int ALAP = 0; 1350b57cec5SDimitry Andric int ZeroLatencyDepth = 0; 1360b57cec5SDimitry Andric int ZeroLatencyHeight = 0; 1370b57cec5SDimitry Andric 1380b57cec5SDimitry Andric NodeInfo() = default; 1390b57cec5SDimitry Andric }; 1400b57cec5SDimitry Andric /// Computed properties for each node in the graph. 1410b57cec5SDimitry Andric std::vector<NodeInfo> ScheduleInfo; 1420b57cec5SDimitry Andric 1430b57cec5SDimitry Andric enum OrderKind { BottomUp = 0, TopDown = 1 }; 1440b57cec5SDimitry Andric /// Computed node ordering for scheduling. 1450b57cec5SDimitry Andric SetVector<SUnit *> NodeOrder; 1460b57cec5SDimitry Andric 1470b57cec5SDimitry Andric using NodeSetType = SmallVector<NodeSet, 8>; 1480b57cec5SDimitry Andric using ValueMapTy = DenseMap<unsigned, unsigned>; 1490b57cec5SDimitry Andric using MBBVectorTy = SmallVectorImpl<MachineBasicBlock *>; 1500b57cec5SDimitry Andric using InstrMapTy = DenseMap<MachineInstr *, MachineInstr *>; 1510b57cec5SDimitry Andric 1520b57cec5SDimitry Andric /// Instructions to change when emitting the final schedule. 1530b57cec5SDimitry Andric DenseMap<SUnit *, std::pair<unsigned, int64_t>> InstrChanges; 1540b57cec5SDimitry Andric 1550b57cec5SDimitry Andric /// We may create a new instruction, so remember it because it 1560b57cec5SDimitry Andric /// must be deleted when the pass is finished. 1578bcb0991SDimitry Andric DenseMap<MachineInstr*, MachineInstr *> NewMIs; 1580b57cec5SDimitry Andric 1590b57cec5SDimitry Andric /// Ordered list of DAG postprocessing steps. 1600b57cec5SDimitry Andric std::vector<std::unique_ptr<ScheduleDAGMutation>> Mutations; 1610b57cec5SDimitry Andric 1620b57cec5SDimitry Andric /// Helper class to implement Johnson's circuit finding algorithm. 1630b57cec5SDimitry Andric class Circuits { 1640b57cec5SDimitry Andric std::vector<SUnit> &SUnits; 1650b57cec5SDimitry Andric SetVector<SUnit *> Stack; 1660b57cec5SDimitry Andric BitVector Blocked; 1670b57cec5SDimitry Andric SmallVector<SmallPtrSet<SUnit *, 4>, 10> B; 1680b57cec5SDimitry Andric SmallVector<SmallVector<int, 4>, 16> AdjK; 1690b57cec5SDimitry Andric // Node to Index from ScheduleDAGTopologicalSort 1700b57cec5SDimitry Andric std::vector<int> *Node2Idx; 17106c3fb27SDimitry Andric unsigned NumPaths = 0u; 1720b57cec5SDimitry Andric static unsigned MaxPaths; 1730b57cec5SDimitry Andric 1740b57cec5SDimitry Andric public: Circuits(std::vector<SUnit> & SUs,ScheduleDAGTopologicalSort & Topo)1750b57cec5SDimitry Andric Circuits(std::vector<SUnit> &SUs, ScheduleDAGTopologicalSort &Topo) 1760b57cec5SDimitry Andric : SUnits(SUs), Blocked(SUs.size()), B(SUs.size()), AdjK(SUs.size()) { 1770b57cec5SDimitry Andric Node2Idx = new std::vector<int>(SUs.size()); 1780b57cec5SDimitry Andric unsigned Idx = 0; 1790b57cec5SDimitry Andric for (const auto &NodeNum : Topo) 1800b57cec5SDimitry Andric Node2Idx->at(NodeNum) = Idx++; 1810b57cec5SDimitry Andric } 18206c3fb27SDimitry Andric Circuits &operator=(const Circuits &other) = delete; 18306c3fb27SDimitry Andric Circuits(const Circuits &other) = delete; ~Circuits()1840b57cec5SDimitry Andric ~Circuits() { delete Node2Idx; } 1850b57cec5SDimitry Andric 1860b57cec5SDimitry Andric /// Reset the data structures used in the circuit algorithm. reset()1870b57cec5SDimitry Andric void reset() { 1880b57cec5SDimitry Andric Stack.clear(); 1890b57cec5SDimitry Andric Blocked.reset(); 1900b57cec5SDimitry Andric B.assign(SUnits.size(), SmallPtrSet<SUnit *, 4>()); 1910b57cec5SDimitry Andric NumPaths = 0; 1920b57cec5SDimitry Andric } 1930b57cec5SDimitry Andric 1940b57cec5SDimitry Andric void createAdjacencyStructure(SwingSchedulerDAG *DAG); 1950b57cec5SDimitry Andric bool circuit(int V, int S, NodeSetType &NodeSets, bool HasBackedge = false); 1960b57cec5SDimitry Andric void unblock(int U); 1970b57cec5SDimitry Andric }; 1980b57cec5SDimitry Andric 1990b57cec5SDimitry Andric struct CopyToPhiMutation : public ScheduleDAGMutation { 2000b57cec5SDimitry Andric void apply(ScheduleDAGInstrs *DAG) override; 2010b57cec5SDimitry Andric }; 2020b57cec5SDimitry Andric 2030b57cec5SDimitry Andric public: SwingSchedulerDAG(MachinePipeliner & P,MachineLoop & L,LiveIntervals & lis,const RegisterClassInfo & rci,unsigned II,TargetInstrInfo::PipelinerLoopInfo * PLI)2040b57cec5SDimitry Andric SwingSchedulerDAG(MachinePipeliner &P, MachineLoop &L, LiveIntervals &lis, 20581ad6265SDimitry Andric const RegisterClassInfo &rci, unsigned II, 20681ad6265SDimitry Andric TargetInstrInfo::PipelinerLoopInfo *PLI) 2070b57cec5SDimitry Andric : ScheduleDAGInstrs(*P.MF, P.MLI, false), Pass(P), Loop(L), LIS(lis), 20881ad6265SDimitry Andric RegClassInfo(rci), II_setByPragma(II), LoopPipelinerInfo(PLI), 20981ad6265SDimitry Andric Topo(SUnits, &ExitSU) { 2100b57cec5SDimitry Andric P.MF->getSubtarget().getSMSMutations(Mutations); 2110b57cec5SDimitry Andric if (SwpEnableCopyToPhi) 2128bcb0991SDimitry Andric Mutations.push_back(std::make_unique<CopyToPhiMutation>()); 2130b57cec5SDimitry Andric } 2140b57cec5SDimitry Andric 2150b57cec5SDimitry Andric void schedule() override; 2160b57cec5SDimitry Andric void finishBlock() override; 2170b57cec5SDimitry Andric 2180b57cec5SDimitry Andric /// Return true if the loop kernel has been scheduled. hasNewSchedule()2190b57cec5SDimitry Andric bool hasNewSchedule() { return Scheduled; } 2200b57cec5SDimitry Andric 2210b57cec5SDimitry Andric /// Return the earliest time an instruction may be scheduled. getASAP(SUnit * Node)2220b57cec5SDimitry Andric int getASAP(SUnit *Node) { return ScheduleInfo[Node->NodeNum].ASAP; } 2230b57cec5SDimitry Andric 2240b57cec5SDimitry Andric /// Return the latest time an instruction my be scheduled. getALAP(SUnit * Node)2250b57cec5SDimitry Andric int getALAP(SUnit *Node) { return ScheduleInfo[Node->NodeNum].ALAP; } 2260b57cec5SDimitry Andric 2270b57cec5SDimitry Andric /// The mobility function, which the number of slots in which 2280b57cec5SDimitry Andric /// an instruction may be scheduled. getMOV(SUnit * Node)2290b57cec5SDimitry Andric int getMOV(SUnit *Node) { return getALAP(Node) - getASAP(Node); } 2300b57cec5SDimitry Andric 2310b57cec5SDimitry Andric /// The depth, in the dependence graph, for a node. getDepth(SUnit * Node)2320b57cec5SDimitry Andric unsigned getDepth(SUnit *Node) { return Node->getDepth(); } 2330b57cec5SDimitry Andric 2340b57cec5SDimitry Andric /// The maximum unweighted length of a path from an arbitrary node to the 2350b57cec5SDimitry Andric /// given node in which each edge has latency 0 getZeroLatencyDepth(SUnit * Node)2360b57cec5SDimitry Andric int getZeroLatencyDepth(SUnit *Node) { 2370b57cec5SDimitry Andric return ScheduleInfo[Node->NodeNum].ZeroLatencyDepth; 2380b57cec5SDimitry Andric } 2390b57cec5SDimitry Andric 2400b57cec5SDimitry Andric /// The height, in the dependence graph, for a node. getHeight(SUnit * Node)2410b57cec5SDimitry Andric unsigned getHeight(SUnit *Node) { return Node->getHeight(); } 2420b57cec5SDimitry Andric 2430b57cec5SDimitry Andric /// The maximum unweighted length of a path from the given node to an 2440b57cec5SDimitry Andric /// arbitrary node in which each edge has latency 0 getZeroLatencyHeight(SUnit * Node)2450b57cec5SDimitry Andric int getZeroLatencyHeight(SUnit *Node) { 2460b57cec5SDimitry Andric return ScheduleInfo[Node->NodeNum].ZeroLatencyHeight; 2470b57cec5SDimitry Andric } 2480b57cec5SDimitry Andric 2490b57cec5SDimitry Andric /// Return true if the dependence is a back-edge in the data dependence graph. 2500b57cec5SDimitry Andric /// Since the DAG doesn't contain cycles, we represent a cycle in the graph 2510b57cec5SDimitry Andric /// using an anti dependence from a Phi to an instruction. isBackedge(SUnit * Source,const SDep & Dep)2520b57cec5SDimitry Andric bool isBackedge(SUnit *Source, const SDep &Dep) { 2530b57cec5SDimitry Andric if (Dep.getKind() != SDep::Anti) 2540b57cec5SDimitry Andric return false; 2550b57cec5SDimitry Andric return Source->getInstr()->isPHI() || Dep.getSUnit()->getInstr()->isPHI(); 2560b57cec5SDimitry Andric } 2570b57cec5SDimitry Andric 2580b57cec5SDimitry Andric bool isLoopCarriedDep(SUnit *Source, const SDep &Dep, bool isSucc = true); 2590b57cec5SDimitry Andric 2600b57cec5SDimitry Andric /// The distance function, which indicates that operation V of iteration I 2610b57cec5SDimitry Andric /// depends on operations U of iteration I-distance. getDistance(SUnit * U,SUnit * V,const SDep & Dep)2620b57cec5SDimitry Andric unsigned getDistance(SUnit *U, SUnit *V, const SDep &Dep) { 2630b57cec5SDimitry Andric // Instructions that feed a Phi have a distance of 1. Computing larger 2640b57cec5SDimitry Andric // values for arrays requires data dependence information. 2650b57cec5SDimitry Andric if (V->getInstr()->isPHI() && Dep.getKind() == SDep::Anti) 2660b57cec5SDimitry Andric return 1; 2670b57cec5SDimitry Andric return 0; 2680b57cec5SDimitry Andric } 2690b57cec5SDimitry Andric 2700b57cec5SDimitry Andric void applyInstrChange(MachineInstr *MI, SMSchedule &Schedule); 2710b57cec5SDimitry Andric 2720b57cec5SDimitry Andric void fixupRegisterOverlaps(std::deque<SUnit *> &Instrs); 2730b57cec5SDimitry Andric 2740b57cec5SDimitry Andric /// Return the new base register that was stored away for the changed 2750b57cec5SDimitry Andric /// instruction. getInstrBaseReg(SUnit * SU)2767a6dacacSDimitry Andric unsigned getInstrBaseReg(SUnit *SU) const { 2777a6dacacSDimitry Andric DenseMap<SUnit *, std::pair<unsigned, int64_t>>::const_iterator It = 2780b57cec5SDimitry Andric InstrChanges.find(SU); 2790b57cec5SDimitry Andric if (It != InstrChanges.end()) 2800b57cec5SDimitry Andric return It->second.first; 2810b57cec5SDimitry Andric return 0; 2820b57cec5SDimitry Andric } 2830b57cec5SDimitry Andric addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation)2840b57cec5SDimitry Andric void addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation) { 2850b57cec5SDimitry Andric Mutations.push_back(std::move(Mutation)); 2860b57cec5SDimitry Andric } 2870b57cec5SDimitry Andric classof(const ScheduleDAGInstrs * DAG)2880b57cec5SDimitry Andric static bool classof(const ScheduleDAGInstrs *DAG) { return true; } 2890b57cec5SDimitry Andric 2900b57cec5SDimitry Andric private: 291e8d8bef9SDimitry Andric void addLoopCarriedDependences(AAResults *AA); 2920b57cec5SDimitry Andric void updatePhiDependences(); 2930b57cec5SDimitry Andric void changeDependences(); 2940b57cec5SDimitry Andric unsigned calculateResMII(); 2950b57cec5SDimitry Andric unsigned calculateRecMII(NodeSetType &RecNodeSets); 2960b57cec5SDimitry Andric void findCircuits(NodeSetType &NodeSets); 2970b57cec5SDimitry Andric void fuseRecs(NodeSetType &NodeSets); 2980b57cec5SDimitry Andric void removeDuplicateNodes(NodeSetType &NodeSets); 2990b57cec5SDimitry Andric void computeNodeFunctions(NodeSetType &NodeSets); 3000b57cec5SDimitry Andric void registerPressureFilter(NodeSetType &NodeSets); 3010b57cec5SDimitry Andric void colocateNodeSets(NodeSetType &NodeSets); 3020b57cec5SDimitry Andric void checkNodeSets(NodeSetType &NodeSets); 3030b57cec5SDimitry Andric void groupRemainingNodes(NodeSetType &NodeSets); 3040b57cec5SDimitry Andric void addConnectedNodes(SUnit *SU, NodeSet &NewSet, 3050b57cec5SDimitry Andric SetVector<SUnit *> &NodesAdded); 3060b57cec5SDimitry Andric void computeNodeOrder(NodeSetType &NodeSets); 3070b57cec5SDimitry Andric void checkValidNodeOrder(const NodeSetType &Circuits) const; 3080b57cec5SDimitry Andric bool schedulePipeline(SMSchedule &Schedule); 3090b57cec5SDimitry Andric bool computeDelta(MachineInstr &MI, unsigned &Delta); 310e8d8bef9SDimitry Andric MachineInstr *findDefInLoop(Register Reg); 3110b57cec5SDimitry Andric bool canUseLastOffsetValue(MachineInstr *MI, unsigned &BasePos, 3120b57cec5SDimitry Andric unsigned &OffsetPos, unsigned &NewBase, 3130b57cec5SDimitry Andric int64_t &NewOffset); 31406c3fb27SDimitry Andric void postProcessDAG(); 3150b57cec5SDimitry Andric /// Set the Minimum Initiation Interval for this schedule attempt. 3160b57cec5SDimitry Andric void setMII(unsigned ResMII, unsigned RecMII); 3170b57cec5SDimitry Andric /// Set the Maximum Initiation Interval for this schedule attempt. 3180b57cec5SDimitry Andric void setMAX_II(); 3190b57cec5SDimitry Andric }; 3200b57cec5SDimitry Andric 3210b57cec5SDimitry Andric /// A NodeSet contains a set of SUnit DAG nodes with additional information 3220b57cec5SDimitry Andric /// that assigns a priority to the set. 3230b57cec5SDimitry Andric class NodeSet { 3240b57cec5SDimitry Andric SetVector<SUnit *> Nodes; 3250b57cec5SDimitry Andric bool HasRecurrence = false; 3260b57cec5SDimitry Andric unsigned RecMII = 0; 3270b57cec5SDimitry Andric int MaxMOV = 0; 3280b57cec5SDimitry Andric unsigned MaxDepth = 0; 3290b57cec5SDimitry Andric unsigned Colocate = 0; 3300b57cec5SDimitry Andric SUnit *ExceedPressure = nullptr; 3310b57cec5SDimitry Andric unsigned Latency = 0; 3320b57cec5SDimitry Andric 3330b57cec5SDimitry Andric public: 3340b57cec5SDimitry Andric using iterator = SetVector<SUnit *>::const_iterator; 3350b57cec5SDimitry Andric 3360b57cec5SDimitry Andric NodeSet() = default; NodeSet(iterator S,iterator E)3370b57cec5SDimitry Andric NodeSet(iterator S, iterator E) : Nodes(S, E), HasRecurrence(true) { 3380b57cec5SDimitry Andric Latency = 0; 339fcaf7f86SDimitry Andric for (const SUnit *Node : Nodes) { 3405ffd83dbSDimitry Andric DenseMap<SUnit *, unsigned> SuccSUnitLatency; 341fcaf7f86SDimitry Andric for (const SDep &Succ : Node->Succs) { 3425ffd83dbSDimitry Andric auto SuccSUnit = Succ.getSUnit(); 3435ffd83dbSDimitry Andric if (!Nodes.count(SuccSUnit)) 3445ffd83dbSDimitry Andric continue; 3455ffd83dbSDimitry Andric unsigned CurLatency = Succ.getLatency(); 3465ffd83dbSDimitry Andric unsigned MaxLatency = 0; 3475ffd83dbSDimitry Andric if (SuccSUnitLatency.count(SuccSUnit)) 3485ffd83dbSDimitry Andric MaxLatency = SuccSUnitLatency[SuccSUnit]; 3495ffd83dbSDimitry Andric if (CurLatency > MaxLatency) 3505ffd83dbSDimitry Andric SuccSUnitLatency[SuccSUnit] = CurLatency; 3515ffd83dbSDimitry Andric } 3525ffd83dbSDimitry Andric for (auto SUnitLatency : SuccSUnitLatency) 3535ffd83dbSDimitry Andric Latency += SUnitLatency.second; 3545ffd83dbSDimitry Andric } 3550b57cec5SDimitry Andric } 3560b57cec5SDimitry Andric insert(SUnit * SU)3570b57cec5SDimitry Andric bool insert(SUnit *SU) { return Nodes.insert(SU); } 3580b57cec5SDimitry Andric insert(iterator S,iterator E)3590b57cec5SDimitry Andric void insert(iterator S, iterator E) { Nodes.insert(S, E); } 3600b57cec5SDimitry Andric remove_if(UnaryPredicate P)3610b57cec5SDimitry Andric template <typename UnaryPredicate> bool remove_if(UnaryPredicate P) { 3620b57cec5SDimitry Andric return Nodes.remove_if(P); 3630b57cec5SDimitry Andric } 3640b57cec5SDimitry Andric count(SUnit * SU)3650b57cec5SDimitry Andric unsigned count(SUnit *SU) const { return Nodes.count(SU); } 3660b57cec5SDimitry Andric hasRecurrence()3670b57cec5SDimitry Andric bool hasRecurrence() { return HasRecurrence; }; 3680b57cec5SDimitry Andric size()3690b57cec5SDimitry Andric unsigned size() const { return Nodes.size(); } 3700b57cec5SDimitry Andric empty()3710b57cec5SDimitry Andric bool empty() const { return Nodes.empty(); } 3720b57cec5SDimitry Andric getNode(unsigned i)3730b57cec5SDimitry Andric SUnit *getNode(unsigned i) const { return Nodes[i]; }; 3740b57cec5SDimitry Andric setRecMII(unsigned mii)3750b57cec5SDimitry Andric void setRecMII(unsigned mii) { RecMII = mii; }; 3760b57cec5SDimitry Andric setColocate(unsigned c)3770b57cec5SDimitry Andric void setColocate(unsigned c) { Colocate = c; }; 3780b57cec5SDimitry Andric setExceedPressure(SUnit * SU)3790b57cec5SDimitry Andric void setExceedPressure(SUnit *SU) { ExceedPressure = SU; } 3800b57cec5SDimitry Andric isExceedSU(SUnit * SU)3810b57cec5SDimitry Andric bool isExceedSU(SUnit *SU) { return ExceedPressure == SU; } 3820b57cec5SDimitry Andric compareRecMII(NodeSet & RHS)3830b57cec5SDimitry Andric int compareRecMII(NodeSet &RHS) { return RecMII - RHS.RecMII; } 3840b57cec5SDimitry Andric getRecMII()3850b57cec5SDimitry Andric int getRecMII() { return RecMII; } 3860b57cec5SDimitry Andric 3870b57cec5SDimitry Andric /// Summarize node functions for the entire node set. computeNodeSetInfo(SwingSchedulerDAG * SSD)3880b57cec5SDimitry Andric void computeNodeSetInfo(SwingSchedulerDAG *SSD) { 3890b57cec5SDimitry Andric for (SUnit *SU : *this) { 3900b57cec5SDimitry Andric MaxMOV = std::max(MaxMOV, SSD->getMOV(SU)); 3910b57cec5SDimitry Andric MaxDepth = std::max(MaxDepth, SSD->getDepth(SU)); 3920b57cec5SDimitry Andric } 3930b57cec5SDimitry Andric } 3940b57cec5SDimitry Andric getLatency()3950b57cec5SDimitry Andric unsigned getLatency() { return Latency; } 3960b57cec5SDimitry Andric getMaxDepth()3970b57cec5SDimitry Andric unsigned getMaxDepth() { return MaxDepth; } 3980b57cec5SDimitry Andric clear()3990b57cec5SDimitry Andric void clear() { 4000b57cec5SDimitry Andric Nodes.clear(); 4010b57cec5SDimitry Andric RecMII = 0; 4020b57cec5SDimitry Andric HasRecurrence = false; 4030b57cec5SDimitry Andric MaxMOV = 0; 4040b57cec5SDimitry Andric MaxDepth = 0; 4050b57cec5SDimitry Andric Colocate = 0; 4060b57cec5SDimitry Andric ExceedPressure = nullptr; 4070b57cec5SDimitry Andric } 4080b57cec5SDimitry Andric 4090b57cec5SDimitry Andric operator SetVector<SUnit *> &() { return Nodes; } 4100b57cec5SDimitry Andric 4110b57cec5SDimitry Andric /// Sort the node sets by importance. First, rank them by recurrence MII, 4120b57cec5SDimitry Andric /// then by mobility (least mobile done first), and finally by depth. 4130b57cec5SDimitry Andric /// Each node set may contain a colocate value which is used as the first 4140b57cec5SDimitry Andric /// tie breaker, if it's set. 4150b57cec5SDimitry Andric bool operator>(const NodeSet &RHS) const { 4160b57cec5SDimitry Andric if (RecMII == RHS.RecMII) { 4170b57cec5SDimitry Andric if (Colocate != 0 && RHS.Colocate != 0 && Colocate != RHS.Colocate) 4180b57cec5SDimitry Andric return Colocate < RHS.Colocate; 4190b57cec5SDimitry Andric if (MaxMOV == RHS.MaxMOV) 4200b57cec5SDimitry Andric return MaxDepth > RHS.MaxDepth; 4210b57cec5SDimitry Andric return MaxMOV < RHS.MaxMOV; 4220b57cec5SDimitry Andric } 4230b57cec5SDimitry Andric return RecMII > RHS.RecMII; 4240b57cec5SDimitry Andric } 4250b57cec5SDimitry Andric 4260b57cec5SDimitry Andric bool operator==(const NodeSet &RHS) const { 4270b57cec5SDimitry Andric return RecMII == RHS.RecMII && MaxMOV == RHS.MaxMOV && 4280b57cec5SDimitry Andric MaxDepth == RHS.MaxDepth; 4290b57cec5SDimitry Andric } 4300b57cec5SDimitry Andric 4310b57cec5SDimitry Andric bool operator!=(const NodeSet &RHS) const { return !operator==(RHS); } 4320b57cec5SDimitry Andric begin()4330b57cec5SDimitry Andric iterator begin() { return Nodes.begin(); } end()4340b57cec5SDimitry Andric iterator end() { return Nodes.end(); } 4350b57cec5SDimitry Andric void print(raw_ostream &os) const; 4360b57cec5SDimitry Andric 4370b57cec5SDimitry Andric #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 4380b57cec5SDimitry Andric LLVM_DUMP_METHOD void dump() const; 4390b57cec5SDimitry Andric #endif 4400b57cec5SDimitry Andric }; 4410b57cec5SDimitry Andric 4420b57cec5SDimitry Andric // 16 was selected based on the number of ProcResource kinds for all 4430b57cec5SDimitry Andric // existing Subtargets, so that SmallVector don't need to resize too often. 4440b57cec5SDimitry Andric static const int DefaultProcResSize = 16; 4450b57cec5SDimitry Andric 4460b57cec5SDimitry Andric class ResourceManager { 4470b57cec5SDimitry Andric private: 4480b57cec5SDimitry Andric const MCSubtargetInfo *STI; 4490b57cec5SDimitry Andric const MCSchedModel &SM; 450bdd1243dSDimitry Andric const TargetSubtargetInfo *ST; 451bdd1243dSDimitry Andric const TargetInstrInfo *TII; 452bdd1243dSDimitry Andric SwingSchedulerDAG *DAG; 4530b57cec5SDimitry Andric const bool UseDFA; 454bdd1243dSDimitry Andric /// DFA resources for each slot 455bdd1243dSDimitry Andric llvm::SmallVector<std::unique_ptr<DFAPacketizer>> DFAResources; 456bdd1243dSDimitry Andric /// Modulo Reservation Table. When a resource with ID R is consumed in cycle 457bdd1243dSDimitry Andric /// C, it is counted in MRT[C mod II][R]. (Used when UseDFA == F) 458bdd1243dSDimitry Andric llvm::SmallVector<llvm::SmallVector<uint64_t, DefaultProcResSize>> MRT; 459bdd1243dSDimitry Andric /// The number of scheduled micro operations for each slot. Micro operations 460bdd1243dSDimitry Andric /// are assumed to be scheduled one per cycle, starting with the cycle in 461bdd1243dSDimitry Andric /// which the instruction is scheduled. 462bdd1243dSDimitry Andric llvm::SmallVector<int> NumScheduledMops; 4630b57cec5SDimitry Andric /// Each processor resource is associated with a so-called processor resource 4640b57cec5SDimitry Andric /// mask. This vector allows to correlate processor resource IDs with 4650b57cec5SDimitry Andric /// processor resource masks. There is exactly one element per each processor 4660b57cec5SDimitry Andric /// resource declared by the scheduling model. 4670b57cec5SDimitry Andric llvm::SmallVector<uint64_t, DefaultProcResSize> ProcResourceMasks; 46806c3fb27SDimitry Andric int InitiationInterval = 0; 469bdd1243dSDimitry Andric /// The number of micro operations that can be scheduled at a cycle. 470bdd1243dSDimitry Andric int IssueWidth; 4710b57cec5SDimitry Andric 472bdd1243dSDimitry Andric int calculateResMIIDFA() const; 473bdd1243dSDimitry Andric /// Check if MRT is overbooked 474bdd1243dSDimitry Andric bool isOverbooked() const; 475bdd1243dSDimitry Andric /// Reserve resources on MRT 476bdd1243dSDimitry Andric void reserveResources(const MCSchedClassDesc *SCDesc, int Cycle); 477bdd1243dSDimitry Andric /// Unreserve resources on MRT 478bdd1243dSDimitry Andric void unreserveResources(const MCSchedClassDesc *SCDesc, int Cycle); 479bdd1243dSDimitry Andric 480bdd1243dSDimitry Andric /// Return M satisfying Dividend = Divisor * X + M, 0 < M < Divisor. 481bdd1243dSDimitry Andric /// The slot on MRT to reserve a resource for the cycle C is positiveModulo(C, 482bdd1243dSDimitry Andric /// II). positiveModulo(int Dividend,int Divisor)483bdd1243dSDimitry Andric int positiveModulo(int Dividend, int Divisor) const { 484bdd1243dSDimitry Andric assert(Divisor > 0); 485bdd1243dSDimitry Andric int R = Dividend % Divisor; 486bdd1243dSDimitry Andric if (R < 0) 487bdd1243dSDimitry Andric R += Divisor; 488bdd1243dSDimitry Andric return R; 489bdd1243dSDimitry Andric } 490bdd1243dSDimitry Andric 491bdd1243dSDimitry Andric #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 492bdd1243dSDimitry Andric LLVM_DUMP_METHOD void dumpMRT() const; 493bdd1243dSDimitry Andric #endif 4940b57cec5SDimitry Andric 4950b57cec5SDimitry Andric public: ResourceManager(const TargetSubtargetInfo * ST,SwingSchedulerDAG * DAG)496bdd1243dSDimitry Andric ResourceManager(const TargetSubtargetInfo *ST, SwingSchedulerDAG *DAG) 497bdd1243dSDimitry Andric : STI(ST), SM(ST->getSchedModel()), ST(ST), TII(ST->getInstrInfo()), 498bdd1243dSDimitry Andric DAG(DAG), UseDFA(ST->useDFAforSMS()), 4990b57cec5SDimitry Andric ProcResourceMasks(SM.getNumProcResourceKinds(), 0), 500bdd1243dSDimitry Andric IssueWidth(SM.IssueWidth) { 5010b57cec5SDimitry Andric initProcResourceVectors(SM, ProcResourceMasks); 502bdd1243dSDimitry Andric if (IssueWidth <= 0) 503bdd1243dSDimitry Andric // If IssueWidth is not specified, set a sufficiently large value 504bdd1243dSDimitry Andric IssueWidth = 100; 505bdd1243dSDimitry Andric if (SwpForceIssueWidth > 0) 506bdd1243dSDimitry Andric IssueWidth = SwpForceIssueWidth; 5070b57cec5SDimitry Andric } 5080b57cec5SDimitry Andric 5090b57cec5SDimitry Andric void initProcResourceVectors(const MCSchedModel &SM, 5100b57cec5SDimitry Andric SmallVectorImpl<uint64_t> &Masks); 5110b57cec5SDimitry Andric 5120b57cec5SDimitry Andric /// Check if the resources occupied by a machine instruction are available 5130b57cec5SDimitry Andric /// in the current state. 514bdd1243dSDimitry Andric bool canReserveResources(SUnit &SU, int Cycle); 5150b57cec5SDimitry Andric 5160b57cec5SDimitry Andric /// Reserve the resources occupied by a machine instruction and change the 5170b57cec5SDimitry Andric /// current state to reflect that change. 518bdd1243dSDimitry Andric void reserveResources(SUnit &SU, int Cycle); 5190b57cec5SDimitry Andric 520bdd1243dSDimitry Andric int calculateResMII() const; 521bdd1243dSDimitry Andric 522bdd1243dSDimitry Andric /// Initialize resources with the initiation interval II. 523bdd1243dSDimitry Andric void init(int II); 5240b57cec5SDimitry Andric }; 5250b57cec5SDimitry Andric 5260b57cec5SDimitry Andric /// This class represents the scheduled code. The main data structure is a 5270b57cec5SDimitry Andric /// map from scheduled cycle to instructions. During scheduling, the 5280b57cec5SDimitry Andric /// data structure explicitly represents all stages/iterations. When 5290b57cec5SDimitry Andric /// the algorithm finshes, the schedule is collapsed into a single stage, 5300b57cec5SDimitry Andric /// which represents instructions from different loop iterations. 5310b57cec5SDimitry Andric /// 5320b57cec5SDimitry Andric /// The SMS algorithm allows negative values for cycles, so the first cycle 5330b57cec5SDimitry Andric /// in the schedule is the smallest cycle value. 5340b57cec5SDimitry Andric class SMSchedule { 5350b57cec5SDimitry Andric private: 5360b57cec5SDimitry Andric /// Map from execution cycle to instructions. 5370b57cec5SDimitry Andric DenseMap<int, std::deque<SUnit *>> ScheduledInstrs; 5380b57cec5SDimitry Andric 5390b57cec5SDimitry Andric /// Map from instruction to execution cycle. 5400b57cec5SDimitry Andric std::map<SUnit *, int> InstrToCycle; 5410b57cec5SDimitry Andric 5420b57cec5SDimitry Andric /// Keep track of the first cycle value in the schedule. It starts 5430b57cec5SDimitry Andric /// as zero, but the algorithm allows negative values. 5440b57cec5SDimitry Andric int FirstCycle = 0; 5450b57cec5SDimitry Andric 5460b57cec5SDimitry Andric /// Keep track of the last cycle value in the schedule. 5470b57cec5SDimitry Andric int LastCycle = 0; 5480b57cec5SDimitry Andric 5490b57cec5SDimitry Andric /// The initiation interval (II) for the schedule. 5500b57cec5SDimitry Andric int InitiationInterval = 0; 5510b57cec5SDimitry Andric 5520b57cec5SDimitry Andric /// Target machine information. 5530b57cec5SDimitry Andric const TargetSubtargetInfo &ST; 5540b57cec5SDimitry Andric 5550b57cec5SDimitry Andric /// Virtual register information. 5560b57cec5SDimitry Andric MachineRegisterInfo &MRI; 5570b57cec5SDimitry Andric 5580b57cec5SDimitry Andric ResourceManager ProcItinResources; 5590b57cec5SDimitry Andric 5600b57cec5SDimitry Andric public: SMSchedule(MachineFunction * mf,SwingSchedulerDAG * DAG)561bdd1243dSDimitry Andric SMSchedule(MachineFunction *mf, SwingSchedulerDAG *DAG) 562bdd1243dSDimitry Andric : ST(mf->getSubtarget()), MRI(mf->getRegInfo()), 563bdd1243dSDimitry Andric ProcItinResources(&ST, DAG) {} 5640b57cec5SDimitry Andric reset()5650b57cec5SDimitry Andric void reset() { 5660b57cec5SDimitry Andric ScheduledInstrs.clear(); 5670b57cec5SDimitry Andric InstrToCycle.clear(); 5680b57cec5SDimitry Andric FirstCycle = 0; 5690b57cec5SDimitry Andric LastCycle = 0; 5700b57cec5SDimitry Andric InitiationInterval = 0; 5710b57cec5SDimitry Andric } 5720b57cec5SDimitry Andric 5730b57cec5SDimitry Andric /// Set the initiation interval for this schedule. setInitiationInterval(int ii)574bdd1243dSDimitry Andric void setInitiationInterval(int ii) { 575bdd1243dSDimitry Andric InitiationInterval = ii; 576bdd1243dSDimitry Andric ProcItinResources.init(ii); 577bdd1243dSDimitry Andric } 5780b57cec5SDimitry Andric 579fe6060f1SDimitry Andric /// Return the initiation interval for this schedule. getInitiationInterval()580fe6060f1SDimitry Andric int getInitiationInterval() const { return InitiationInterval; } 581fe6060f1SDimitry Andric 5820b57cec5SDimitry Andric /// Return the first cycle in the completed schedule. This 5830b57cec5SDimitry Andric /// can be a negative value. getFirstCycle()5840b57cec5SDimitry Andric int getFirstCycle() const { return FirstCycle; } 5850b57cec5SDimitry Andric 5860b57cec5SDimitry Andric /// Return the last cycle in the finalized schedule. getFinalCycle()5870b57cec5SDimitry Andric int getFinalCycle() const { return FirstCycle + InitiationInterval - 1; } 5880b57cec5SDimitry Andric 5890b57cec5SDimitry Andric /// Return the cycle of the earliest scheduled instruction in the dependence 5900b57cec5SDimitry Andric /// chain. 5910b57cec5SDimitry Andric int earliestCycleInChain(const SDep &Dep); 5920b57cec5SDimitry Andric 5930b57cec5SDimitry Andric /// Return the cycle of the latest scheduled instruction in the dependence 5940b57cec5SDimitry Andric /// chain. 5950b57cec5SDimitry Andric int latestCycleInChain(const SDep &Dep); 5960b57cec5SDimitry Andric 5970b57cec5SDimitry Andric void computeStart(SUnit *SU, int *MaxEarlyStart, int *MinLateStart, 5980b57cec5SDimitry Andric int *MinEnd, int *MaxStart, int II, SwingSchedulerDAG *DAG); 5990b57cec5SDimitry Andric bool insert(SUnit *SU, int StartCycle, int EndCycle, int II); 6000b57cec5SDimitry Andric 6010b57cec5SDimitry Andric /// Iterators for the cycle to instruction map. 6020b57cec5SDimitry Andric using sched_iterator = DenseMap<int, std::deque<SUnit *>>::iterator; 6030b57cec5SDimitry Andric using const_sched_iterator = 6040b57cec5SDimitry Andric DenseMap<int, std::deque<SUnit *>>::const_iterator; 6050b57cec5SDimitry Andric 6060b57cec5SDimitry Andric /// Return true if the instruction is scheduled at the specified stage. isScheduledAtStage(SUnit * SU,unsigned StageNum)6070b57cec5SDimitry Andric bool isScheduledAtStage(SUnit *SU, unsigned StageNum) { 6080b57cec5SDimitry Andric return (stageScheduled(SU) == (int)StageNum); 6090b57cec5SDimitry Andric } 6100b57cec5SDimitry Andric 6110b57cec5SDimitry Andric /// Return the stage for a scheduled instruction. Return -1 if 6120b57cec5SDimitry Andric /// the instruction has not been scheduled. stageScheduled(SUnit * SU)6130b57cec5SDimitry Andric int stageScheduled(SUnit *SU) const { 6140b57cec5SDimitry Andric std::map<SUnit *, int>::const_iterator it = InstrToCycle.find(SU); 6150b57cec5SDimitry Andric if (it == InstrToCycle.end()) 6160b57cec5SDimitry Andric return -1; 6170b57cec5SDimitry Andric return (it->second - FirstCycle) / InitiationInterval; 6180b57cec5SDimitry Andric } 6190b57cec5SDimitry Andric 6200b57cec5SDimitry Andric /// Return the cycle for a scheduled instruction. This function normalizes 6210b57cec5SDimitry Andric /// the first cycle to be 0. cycleScheduled(SUnit * SU)6220b57cec5SDimitry Andric unsigned cycleScheduled(SUnit *SU) const { 6230b57cec5SDimitry Andric std::map<SUnit *, int>::const_iterator it = InstrToCycle.find(SU); 6240b57cec5SDimitry Andric assert(it != InstrToCycle.end() && "Instruction hasn't been scheduled."); 6250b57cec5SDimitry Andric return (it->second - FirstCycle) % InitiationInterval; 6260b57cec5SDimitry Andric } 6270b57cec5SDimitry Andric 6280b57cec5SDimitry Andric /// Return the maximum stage count needed for this schedule. getMaxStageCount()6290b57cec5SDimitry Andric unsigned getMaxStageCount() { 6300b57cec5SDimitry Andric return (LastCycle - FirstCycle) / InitiationInterval; 6310b57cec5SDimitry Andric } 6320b57cec5SDimitry Andric 6330b57cec5SDimitry Andric /// Return the instructions that are scheduled at the specified cycle. getInstructions(int cycle)6340b57cec5SDimitry Andric std::deque<SUnit *> &getInstructions(int cycle) { 6350b57cec5SDimitry Andric return ScheduledInstrs[cycle]; 6360b57cec5SDimitry Andric } 6370b57cec5SDimitry Andric 63881ad6265SDimitry Andric SmallSet<SUnit *, 8> 63981ad6265SDimitry Andric computeUnpipelineableNodes(SwingSchedulerDAG *SSD, 64081ad6265SDimitry Andric TargetInstrInfo::PipelinerLoopInfo *PLI); 64181ad6265SDimitry Andric 6427a6dacacSDimitry Andric std::deque<SUnit *> 6437a6dacacSDimitry Andric reorderInstructions(const SwingSchedulerDAG *SSD, 6447a6dacacSDimitry Andric const std::deque<SUnit *> &Instrs) const; 6457a6dacacSDimitry Andric 64681ad6265SDimitry Andric bool 64781ad6265SDimitry Andric normalizeNonPipelinedInstructions(SwingSchedulerDAG *SSD, 64881ad6265SDimitry Andric TargetInstrInfo::PipelinerLoopInfo *PLI); 6490b57cec5SDimitry Andric bool isValidSchedule(SwingSchedulerDAG *SSD); 6500b57cec5SDimitry Andric void finalizeSchedule(SwingSchedulerDAG *SSD); 6517a6dacacSDimitry Andric void orderDependence(const SwingSchedulerDAG *SSD, SUnit *SU, 6527a6dacacSDimitry Andric std::deque<SUnit *> &Insts) const; 6537a6dacacSDimitry Andric bool isLoopCarried(const SwingSchedulerDAG *SSD, MachineInstr &Phi) const; 6547a6dacacSDimitry Andric bool isLoopCarriedDefOfUse(const SwingSchedulerDAG *SSD, MachineInstr *Def, 6557a6dacacSDimitry Andric MachineOperand &MO) const; 6560b57cec5SDimitry Andric void print(raw_ostream &os) const; 6570b57cec5SDimitry Andric void dump() const; 6580b57cec5SDimitry Andric }; 6590b57cec5SDimitry Andric 6600b57cec5SDimitry Andric } // end namespace llvm 6610b57cec5SDimitry Andric 662fe6060f1SDimitry Andric #endif // LLVM_CODEGEN_MACHINEPIPELINER_H 663