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