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