include/llvm/CodeGen/ScheduleDAGInstrs.h

   1 //==- ScheduleDAGInstrs.h - MachineInstr Scheduling --------------*- C++ -*-==//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the ScheduleDAGInstrs class, which implements
  11 // scheduling for a MachineInstr-based dependency graph.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef LLVM_CODEGEN_SCHEDULEDAGINSTRS_H
  16 #define LLVM_CODEGEN_SCHEDULEDAGINSTRS_H
  17
  18 #include "llvm/ADT/SparseMultiSet.h"
  19 #include "llvm/ADT/SparseSet.h"
  20 #include "llvm/CodeGen/ScheduleDAG.h"
  21 #include "llvm/CodeGen/TargetSchedule.h"
  22 #include "llvm/Support/Compiler.h"
  23 #include "llvm/Target/TargetRegisterInfo.h"
  24
  25 namespace llvm {
  26   class MachineFrameInfo;
  27   class MachineLoopInfo;
  28   class MachineDominatorTree;
  29   class RegPressureTracker;
  30   class PressureDiffs;
  31
  32   /// An individual mapping from virtual register number to SUnit.
  33   struct VReg2SUnit {
  34     unsigned VirtReg;
  35     LaneBitmask LaneMask;
  36     SUnit *SU;
  37
  38     VReg2SUnit(unsigned VReg, LaneBitmask LaneMask, SUnit *SU)
  39       : VirtReg(VReg), LaneMask(LaneMask), SU(SU) {}
  40
  41     unsigned getSparseSetIndex() const {
  42       return TargetRegisterInfo::virtReg2Index(VirtReg);
  43     }
  44   };
  45
  46   /// Mapping from virtual register to SUnit including an operand index.
  47   struct VReg2SUnitOperIdx : public VReg2SUnit {
  48     unsigned OperandIndex;
  49
  50     VReg2SUnitOperIdx(unsigned VReg, LaneBitmask LaneMask,
  51                       unsigned OperandIndex, SUnit *SU)
  52       : VReg2SUnit(VReg, LaneMask, SU), OperandIndex(OperandIndex) {}
  53   };
  54
  55   /// Record a physical register access.
  56   /// For non-data-dependent uses, OpIdx == -1.
  57   struct PhysRegSUOper {
  58     SUnit *SU;
  59     int OpIdx;
  60     unsigned Reg;
  61
  62     PhysRegSUOper(SUnit *su, int op, unsigned R): SU(su), OpIdx(op), Reg(R) {}
  63
  64     unsigned getSparseSetIndex() const { return Reg; }
  65   };
  66
  67   /// Use a SparseMultiSet to track physical registers. Storage is only
  68   /// allocated once for the pass. It can be cleared in constant time and reused
  69   /// without any frees.
  70   typedef SparseMultiSet<PhysRegSUOper, llvm::identity<unsigned>, uint16_t>
  71   Reg2SUnitsMap;
  72
  73   /// Use SparseSet as a SparseMap by relying on the fact that it never
  74   /// compares ValueT's, only unsigned keys. This allows the set to be cleared
  75   /// between scheduling regions in constant time as long as ValueT does not
  76   /// require a destructor.
  77   typedef SparseSet<VReg2SUnit, VirtReg2IndexFunctor> VReg2SUnitMap;
  78
  79   /// Track local uses of virtual registers. These uses are gathered by the DAG
  80   /// builder and may be consulted by the scheduler to avoid iterating an entire
  81   /// vreg use list.
  82   typedef SparseMultiSet<VReg2SUnit, VirtReg2IndexFunctor> VReg2SUnitMultiMap;
  83
  84   typedef SparseMultiSet<VReg2SUnitOperIdx, VirtReg2IndexFunctor>
  85     VReg2SUnitOperIdxMultiMap;
  86
  87   /// ScheduleDAGInstrs - A ScheduleDAG subclass for scheduling lists of
  88   /// MachineInstrs.
  89   class ScheduleDAGInstrs : public ScheduleDAG {
  90   protected:
  91     const MachineLoopInfo *MLI;
  92     const MachineFrameInfo *MFI;
  93
  94     /// TargetSchedModel provides an interface to the machine model.
  95     TargetSchedModel SchedModel;
  96
  97     /// True if the DAG builder should remove kill flags (in preparation for
  98     /// rescheduling).
  99     bool RemoveKillFlags;
 100
 101     /// The standard DAG builder does not normally include terminators as DAG
 102     /// nodes because it does not create the necessary dependencies to prevent
 103     /// reordering. A specialized scheduler can override
 104     /// TargetInstrInfo::isSchedulingBoundary then enable this flag to indicate
 105     /// it has taken responsibility for scheduling the terminator correctly.
 106     bool CanHandleTerminators;
 107
 108     /// Whether lane masks should get tracked.
 109     bool TrackLaneMasks;
 110
 111     /// State specific to the current scheduling region.
 112     /// ------------------------------------------------
 113
 114     /// The block in which to insert instructions
 115     MachineBasicBlock *BB;
 116
 117     /// The beginning of the range to be scheduled.
 118     MachineBasicBlock::iterator RegionBegin;
 119
 120     /// The end of the range to be scheduled.
 121     MachineBasicBlock::iterator RegionEnd;
 122
 123     /// Instructions in this region (distance(RegionBegin, RegionEnd)).
 124     unsigned NumRegionInstrs;
 125
 126     /// After calling BuildSchedGraph, each machine instruction in the current
 127     /// scheduling region is mapped to an SUnit.
 128     DenseMap<MachineInstr*, SUnit*> MISUnitMap;
 129
 130     /// After calling BuildSchedGraph, each vreg used in the scheduling region
 131     /// is mapped to a set of SUnits. These include all local vreg uses, not
 132     /// just the uses for a singly defined vreg.
 133     VReg2SUnitMultiMap VRegUses;
 134
 135     /// State internal to DAG building.
 136     /// -------------------------------
 137
 138     /// Defs, Uses - Remember where defs and uses of each register are as we
 139     /// iterate upward through the instructions. This is allocated here instead
 140     /// of inside BuildSchedGraph to avoid the need for it to be initialized and
 141     /// destructed for each block.
 142     Reg2SUnitsMap Defs;
 143     Reg2SUnitsMap Uses;
 144
 145     /// Tracks the last instruction(s) in this region defining each virtual
 146     /// register. There may be multiple current definitions for a register with
 147     /// disjunct lanemasks.
 148     VReg2SUnitMultiMap CurrentVRegDefs;
 149     /// Tracks the last instructions in this region using each virtual register.
 150     VReg2SUnitOperIdxMultiMap CurrentVRegUses;
 151
 152     /// PendingLoads - Remember where unknown loads are after the most recent
 153     /// unknown store, as we iterate. As with Defs and Uses, this is here
 154     /// to minimize construction/destruction.
 155     std::vector<SUnit *> PendingLoads;
 156
 157     /// DbgValues - Remember instruction that precedes DBG_VALUE.
 158     /// These are generated by buildSchedGraph but persist so they can be
 159     /// referenced when emitting the final schedule.
 160     typedef std::vector<std::pair<MachineInstr *, MachineInstr *> >
 161       DbgValueVector;
 162     DbgValueVector DbgValues;
 163     MachineInstr *FirstDbgValue;
 164
 165     /// Set of live physical registers for updating kill flags.
 166     BitVector LiveRegs;
 167
 168   public:
 169     explicit ScheduleDAGInstrs(MachineFunction &mf,
 170                                const MachineLoopInfo *mli,
 171                                bool RemoveKillFlags = false);
 172
 173     ~ScheduleDAGInstrs() override {}
 174
 175     /// \brief Get the machine model for instruction scheduling.
 176     const TargetSchedModel *getSchedModel() const { return &SchedModel; }
 177
 178     /// \brief Resolve and cache a resolved scheduling class for an SUnit.
 179     const MCSchedClassDesc *getSchedClass(SUnit *SU) const {
 180       if (!SU->SchedClass && SchedModel.hasInstrSchedModel())
 181         SU->SchedClass = SchedModel.resolveSchedClass(SU->getInstr());
 182       return SU->SchedClass;
 183     }
 184
 185     /// begin - Return an iterator to the top of the current scheduling region.
 186     MachineBasicBlock::iterator begin() const { return RegionBegin; }
 187
 188     /// end - Return an iterator to the bottom of the current scheduling region.
 189     MachineBasicBlock::iterator end() const { return RegionEnd; }
 190
 191     /// newSUnit - Creates a new SUnit and return a ptr to it.
 192     SUnit *newSUnit(MachineInstr *MI);
 193
 194     /// getSUnit - Return an existing SUnit for this MI, or NULL.
 195     SUnit *getSUnit(MachineInstr *MI) const;
 196
 197     /// startBlock - Prepare to perform scheduling in the given block.
 198     virtual void startBlock(MachineBasicBlock *BB);
 199
 200     /// finishBlock - Clean up after scheduling in the given block.
 201     virtual void finishBlock();
 202
 203     /// Initialize the scheduler state for the next scheduling region.
 204     virtual void enterRegion(MachineBasicBlock *bb,
 205                              MachineBasicBlock::iterator begin,
 206                              MachineBasicBlock::iterator end,
 207                              unsigned regioninstrs);
 208
 209     /// Notify that the scheduler has finished scheduling the current region.
 210     virtual void exitRegion();
 211
 212     /// buildSchedGraph - Build SUnits from the MachineBasicBlock that we are
 213     /// input.
 214     void buildSchedGraph(AliasAnalysis *AA,
 215                          RegPressureTracker *RPTracker = nullptr,
 216                          PressureDiffs *PDiffs = nullptr,
 217                          bool TrackLaneMasks = false);
 218
 219     /// addSchedBarrierDeps - Add dependencies from instructions in the current
 220     /// list of instructions being scheduled to scheduling barrier. We want to
 221     /// make sure instructions which define registers that are either used by
 222     /// the terminator or are live-out are properly scheduled. This is
 223     /// especially important when the definition latency of the return value(s)
 224     /// are too high to be hidden by the branch or when the liveout registers
 225     /// used by instructions in the fallthrough block.
 226     void addSchedBarrierDeps();
 227
 228     /// schedule - Order nodes according to selected style, filling
 229     /// in the Sequence member.
 230     ///
 231     /// Typically, a scheduling algorithm will implement schedule() without
 232     /// overriding enterRegion() or exitRegion().
 233     virtual void schedule() = 0;
 234
 235     /// finalizeSchedule - Allow targets to perform final scheduling actions at
 236     /// the level of the whole MachineFunction. By default does nothing.
 237     virtual void finalizeSchedule() {}
 238
 239     void dumpNode(const SUnit *SU) const override;
 240
 241     /// Return a label for a DAG node that points to an instruction.
 242     std::string getGraphNodeLabel(const SUnit *SU) const override;
 243
 244     /// Return a label for the region of code covered by the DAG.
 245     std::string getDAGName() const override;
 246
 247     /// \brief Fix register kill flags that scheduling has made invalid.
 248     void fixupKills(MachineBasicBlock *MBB);
 249   protected:
 250     void initSUnits();
 251     void addPhysRegDataDeps(SUnit *SU, unsigned OperIdx);
 252     void addPhysRegDeps(SUnit *SU, unsigned OperIdx);
 253     void addVRegDefDeps(SUnit *SU, unsigned OperIdx);
 254     void addVRegUseDeps(SUnit *SU, unsigned OperIdx);
 255
 256     /// \brief PostRA helper for rewriting kill flags.
 257     void startBlockForKills(MachineBasicBlock *BB);
 258
 259     /// \brief Toggle a register operand kill flag.
 260     ///
 261     /// Other adjustments may be made to the instruction if necessary. Return
 262     /// true if the operand has been deleted, false if not.
 263     bool toggleKillFlag(MachineInstr *MI, MachineOperand &MO);
 264
 265     /// Returns a mask for which lanes get read/written by the given (register)
 266     /// machine operand.
 267     LaneBitmask getLaneMaskForMO(const MachineOperand &MO) const;
 268
 269     void collectVRegUses(SUnit *SU);
 270   };
 271
 272   /// newSUnit - Creates a new SUnit and return a ptr to it.
 273   inline SUnit *ScheduleDAGInstrs::newSUnit(MachineInstr *MI) {
 274 #ifndef NDEBUG
 275     const SUnit *Addr = SUnits.empty() ? nullptr : &SUnits[0];
 276 #endif
 277     SUnits.emplace_back(MI, (unsigned)SUnits.size());
 278     assert((Addr == nullptr || Addr == &SUnits[0]) &&
 279            "SUnits std::vector reallocated on the fly!");
 280     SUnits.back().OrigNode = &SUnits.back();
 281     return &SUnits.back();
 282   }
 283
 284   /// getSUnit - Return an existing SUnit for this MI, or NULL.
 285   inline SUnit *ScheduleDAGInstrs::getSUnit(MachineInstr *MI) const {
 286     DenseMap<MachineInstr*, SUnit*>::const_iterator I = MISUnitMap.find(MI);
 287     if (I == MISUnitMap.end())
 288       return nullptr;
 289     return I->second;
 290   }
 291 } // namespace llvm
 292
 293 #endif