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 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
294