1234285Sdim//==- ScheduleDAGInstrs.h - MachineInstr Scheduling --------------*- C++ -*-==// 2234285Sdim// 3234285Sdim// The LLVM Compiler Infrastructure 4234285Sdim// 5234285Sdim// This file is distributed under the University of Illinois Open Source 6234285Sdim// License. See LICENSE.TXT for details. 7234285Sdim// 8234285Sdim//===----------------------------------------------------------------------===// 9234285Sdim// 10234285Sdim// This file implements the ScheduleDAGInstrs class, which implements 11234285Sdim// scheduling for a MachineInstr-based dependency graph. 12234285Sdim// 13234285Sdim//===----------------------------------------------------------------------===// 14234285Sdim 15252723Sdim#ifndef LLVM_CODEGEN_SCHEDULEDAGINSTRS_H 16252723Sdim#define LLVM_CODEGEN_SCHEDULEDAGINSTRS_H 17234285Sdim 18252723Sdim#include "llvm/ADT/SparseSet.h" 19252723Sdim#include "llvm/ADT/SparseMultiSet.h" 20234285Sdim#include "llvm/CodeGen/ScheduleDAG.h" 21245431Sdim#include "llvm/CodeGen/TargetSchedule.h" 22234285Sdim#include "llvm/Support/Compiler.h" 23234285Sdim#include "llvm/Target/TargetRegisterInfo.h" 24234285Sdim 25234285Sdimnamespace llvm { 26252723Sdim class MachineFrameInfo; 27234285Sdim class MachineLoopInfo; 28234285Sdim class MachineDominatorTree; 29234285Sdim class LiveIntervals; 30245431Sdim class RegPressureTracker; 31263509Sdim class PressureDiffs; 32234285Sdim 33234285Sdim /// An individual mapping from virtual register number to SUnit. 34234285Sdim struct VReg2SUnit { 35234285Sdim unsigned VirtReg; 36234285Sdim SUnit *SU; 37234285Sdim 38234285Sdim VReg2SUnit(unsigned reg, SUnit *su): VirtReg(reg), SU(su) {} 39234285Sdim 40245431Sdim unsigned getSparseSetIndex() const { 41234285Sdim return TargetRegisterInfo::virtReg2Index(VirtReg); 42234285Sdim } 43234285Sdim }; 44234285Sdim 45245431Sdim /// Record a physical register access. 46245431Sdim /// For non data-dependent uses, OpIdx == -1. 47245431Sdim struct PhysRegSUOper { 48245431Sdim SUnit *SU; 49245431Sdim int OpIdx; 50252723Sdim unsigned Reg; 51245431Sdim 52252723Sdim PhysRegSUOper(SUnit *su, int op, unsigned R): SU(su), OpIdx(op), Reg(R) {} 53252723Sdim 54252723Sdim unsigned getSparseSetIndex() const { return Reg; } 55245431Sdim }; 56245431Sdim 57252723Sdim /// Use a SparseMultiSet to track physical registers. Storage is only 58252723Sdim /// allocated once for the pass. It can be cleared in constant time and reused 59252723Sdim /// without any frees. 60263509Sdim typedef SparseMultiSet<PhysRegSUOper, llvm::identity<unsigned>, uint16_t> 61263509Sdim Reg2SUnitsMap; 62234285Sdim 63234285Sdim /// Use SparseSet as a SparseMap by relying on the fact that it never 64234285Sdim /// compares ValueT's, only unsigned keys. This allows the set to be cleared 65234285Sdim /// between scheduling regions in constant time as long as ValueT does not 66234285Sdim /// require a destructor. 67245431Sdim typedef SparseSet<VReg2SUnit, VirtReg2IndexFunctor> VReg2SUnitMap; 68234285Sdim 69263509Sdim /// Track local uses of virtual registers. These uses are gathered by the DAG 70263509Sdim /// builder and may be consulted by the scheduler to avoid iterating an entire 71263509Sdim /// vreg use list. 72263509Sdim typedef SparseMultiSet<VReg2SUnit, VirtReg2IndexFunctor> VReg2UseMap; 73263509Sdim 74234285Sdim /// ScheduleDAGInstrs - A ScheduleDAG subclass for scheduling lists of 75234285Sdim /// MachineInstrs. 76234285Sdim class ScheduleDAGInstrs : public ScheduleDAG { 77234285Sdim protected: 78234285Sdim const MachineLoopInfo &MLI; 79234285Sdim const MachineDominatorTree &MDT; 80234285Sdim const MachineFrameInfo *MFI; 81234285Sdim 82234285Sdim /// Live Intervals provides reaching defs in preRA scheduling. 83234285Sdim LiveIntervals *LIS; 84234285Sdim 85245431Sdim /// TargetSchedModel provides an interface to the machine model. 86245431Sdim TargetSchedModel SchedModel; 87245431Sdim 88234285Sdim /// isPostRA flag indicates vregs cannot be present. 89234285Sdim bool IsPostRA; 90234285Sdim 91235633Sdim /// The standard DAG builder does not normally include terminators as DAG 92235633Sdim /// nodes because it does not create the necessary dependencies to prevent 93235633Sdim /// reordering. A specialized scheduler can overide 94235633Sdim /// TargetInstrInfo::isSchedulingBoundary then enable this flag to indicate 95235633Sdim /// it has taken responsibility for scheduling the terminator correctly. 96235633Sdim bool CanHandleTerminators; 97235633Sdim 98234285Sdim /// State specific to the current scheduling region. 99234285Sdim /// ------------------------------------------------ 100234285Sdim 101234285Sdim /// The block in which to insert instructions 102234285Sdim MachineBasicBlock *BB; 103234285Sdim 104234285Sdim /// The beginning of the range to be scheduled. 105234285Sdim MachineBasicBlock::iterator RegionBegin; 106234285Sdim 107234285Sdim /// The end of the range to be scheduled. 108234285Sdim MachineBasicBlock::iterator RegionEnd; 109234285Sdim 110263509Sdim /// Instructions in this region (distance(RegionBegin, RegionEnd)). 111263509Sdim unsigned NumRegionInstrs; 112234285Sdim 113234285Sdim /// After calling BuildSchedGraph, each machine instruction in the current 114234285Sdim /// scheduling region is mapped to an SUnit. 115234285Sdim DenseMap<MachineInstr*, SUnit*> MISUnitMap; 116234285Sdim 117263509Sdim /// After calling BuildSchedGraph, each vreg used in the scheduling region 118263509Sdim /// is mapped to a set of SUnits. These include all local vreg uses, not 119263509Sdim /// just the uses for a singly defined vreg. 120263509Sdim VReg2UseMap VRegUses; 121263509Sdim 122234285Sdim /// State internal to DAG building. 123234285Sdim /// ------------------------------- 124234285Sdim 125234285Sdim /// Defs, Uses - Remember where defs and uses of each register are as we 126234285Sdim /// iterate upward through the instructions. This is allocated here instead 127234285Sdim /// of inside BuildSchedGraph to avoid the need for it to be initialized and 128234285Sdim /// destructed for each block. 129234285Sdim Reg2SUnitsMap Defs; 130234285Sdim Reg2SUnitsMap Uses; 131234285Sdim 132263509Sdim /// Track the last instruction in this region defining each virtual register. 133234285Sdim VReg2SUnitMap VRegDefs; 134234285Sdim 135234285Sdim /// PendingLoads - Remember where unknown loads are after the most recent 136234285Sdim /// unknown store, as we iterate. As with Defs and Uses, this is here 137234285Sdim /// to minimize construction/destruction. 138234285Sdim std::vector<SUnit *> PendingLoads; 139234285Sdim 140245431Sdim /// DbgValues - Remember instruction that precedes DBG_VALUE. 141234285Sdim /// These are generated by buildSchedGraph but persist so they can be 142234285Sdim /// referenced when emitting the final schedule. 143234285Sdim typedef std::vector<std::pair<MachineInstr *, MachineInstr *> > 144234285Sdim DbgValueVector; 145234285Sdim DbgValueVector DbgValues; 146234285Sdim MachineInstr *FirstDbgValue; 147234285Sdim 148234285Sdim public: 149234285Sdim explicit ScheduleDAGInstrs(MachineFunction &mf, 150234285Sdim const MachineLoopInfo &mli, 151234285Sdim const MachineDominatorTree &mdt, 152234285Sdim bool IsPostRAFlag, 153234285Sdim LiveIntervals *LIS = 0); 154234285Sdim 155234285Sdim virtual ~ScheduleDAGInstrs() {} 156234285Sdim 157252723Sdim /// \brief Expose LiveIntervals for use in DAG mutators and such. 158252723Sdim LiveIntervals *getLIS() const { return LIS; } 159252723Sdim 160245431Sdim /// \brief Get the machine model for instruction scheduling. 161245431Sdim const TargetSchedModel *getSchedModel() const { return &SchedModel; } 162245431Sdim 163245431Sdim /// \brief Resolve and cache a resolved scheduling class for an SUnit. 164245431Sdim const MCSchedClassDesc *getSchedClass(SUnit *SU) const { 165263509Sdim if (!SU->SchedClass && SchedModel.hasInstrSchedModel()) 166245431Sdim SU->SchedClass = SchedModel.resolveSchedClass(SU->getInstr()); 167245431Sdim return SU->SchedClass; 168245431Sdim } 169245431Sdim 170234285Sdim /// begin - Return an iterator to the top of the current scheduling region. 171234285Sdim MachineBasicBlock::iterator begin() const { return RegionBegin; } 172234285Sdim 173234285Sdim /// end - Return an iterator to the bottom of the current scheduling region. 174234285Sdim MachineBasicBlock::iterator end() const { return RegionEnd; } 175234285Sdim 176234285Sdim /// newSUnit - Creates a new SUnit and return a ptr to it. 177234285Sdim SUnit *newSUnit(MachineInstr *MI); 178234285Sdim 179234285Sdim /// getSUnit - Return an existing SUnit for this MI, or NULL. 180234285Sdim SUnit *getSUnit(MachineInstr *MI) const; 181234285Sdim 182234285Sdim /// startBlock - Prepare to perform scheduling in the given block. 183234285Sdim virtual void startBlock(MachineBasicBlock *BB); 184234285Sdim 185234285Sdim /// finishBlock - Clean up after scheduling in the given block. 186234285Sdim virtual void finishBlock(); 187234285Sdim 188234285Sdim /// Initialize the scheduler state for the next scheduling region. 189234285Sdim virtual void enterRegion(MachineBasicBlock *bb, 190234285Sdim MachineBasicBlock::iterator begin, 191234285Sdim MachineBasicBlock::iterator end, 192263509Sdim unsigned regioninstrs); 193234285Sdim 194234285Sdim /// Notify that the scheduler has finished scheduling the current region. 195234285Sdim virtual void exitRegion(); 196234285Sdim 197234285Sdim /// buildSchedGraph - Build SUnits from the MachineBasicBlock that we are 198234285Sdim /// input. 199263509Sdim void buildSchedGraph(AliasAnalysis *AA, RegPressureTracker *RPTracker = 0, 200263509Sdim PressureDiffs *PDiffs = 0); 201234285Sdim 202234285Sdim /// addSchedBarrierDeps - Add dependencies from instructions in the current 203234285Sdim /// list of instructions being scheduled to scheduling barrier. We want to 204234285Sdim /// make sure instructions which define registers that are either used by 205234285Sdim /// the terminator or are live-out are properly scheduled. This is 206234285Sdim /// especially important when the definition latency of the return value(s) 207234285Sdim /// are too high to be hidden by the branch or when the liveout registers 208234285Sdim /// used by instructions in the fallthrough block. 209234285Sdim void addSchedBarrierDeps(); 210234285Sdim 211234285Sdim /// schedule - Order nodes according to selected style, filling 212234285Sdim /// in the Sequence member. 213234285Sdim /// 214234285Sdim /// Typically, a scheduling algorithm will implement schedule() without 215234285Sdim /// overriding enterRegion() or exitRegion(). 216234285Sdim virtual void schedule() = 0; 217234285Sdim 218234285Sdim /// finalizeSchedule - Allow targets to perform final scheduling actions at 219234285Sdim /// the level of the whole MachineFunction. By default does nothing. 220234285Sdim virtual void finalizeSchedule() {} 221234285Sdim 222234285Sdim virtual void dumpNode(const SUnit *SU) const; 223234285Sdim 224234285Sdim /// Return a label for a DAG node that points to an instruction. 225234285Sdim virtual std::string getGraphNodeLabel(const SUnit *SU) const; 226234285Sdim 227234285Sdim /// Return a label for the region of code covered by the DAG. 228234285Sdim virtual std::string getDAGName() const; 229234285Sdim 230234285Sdim protected: 231234285Sdim void initSUnits(); 232245431Sdim void addPhysRegDataDeps(SUnit *SU, unsigned OperIdx); 233234285Sdim void addPhysRegDeps(SUnit *SU, unsigned OperIdx); 234234285Sdim void addVRegDefDeps(SUnit *SU, unsigned OperIdx); 235234285Sdim void addVRegUseDeps(SUnit *SU, unsigned OperIdx); 236234285Sdim }; 237234285Sdim 238234285Sdim /// newSUnit - Creates a new SUnit and return a ptr to it. 239234285Sdim inline SUnit *ScheduleDAGInstrs::newSUnit(MachineInstr *MI) { 240234285Sdim#ifndef NDEBUG 241234285Sdim const SUnit *Addr = SUnits.empty() ? 0 : &SUnits[0]; 242234285Sdim#endif 243234285Sdim SUnits.push_back(SUnit(MI, (unsigned)SUnits.size())); 244234285Sdim assert((Addr == 0 || Addr == &SUnits[0]) && 245234285Sdim "SUnits std::vector reallocated on the fly!"); 246234285Sdim SUnits.back().OrigNode = &SUnits.back(); 247234285Sdim return &SUnits.back(); 248234285Sdim } 249234285Sdim 250234285Sdim /// getSUnit - Return an existing SUnit for this MI, or NULL. 251234285Sdim inline SUnit *ScheduleDAGInstrs::getSUnit(MachineInstr *MI) const { 252234285Sdim DenseMap<MachineInstr*, SUnit*>::const_iterator I = MISUnitMap.find(MI); 253234285Sdim if (I == MISUnitMap.end()) 254234285Sdim return 0; 255234285Sdim return I->second; 256234285Sdim } 257234285Sdim} // namespace llvm 258234285Sdim 259234285Sdim#endif 260