ScheduleDAGInstrs.h revision 263508 
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/SparseSet.h"
19#include "llvm/ADT/SparseMultiSet.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    /// The standard DAG builder does not normally include terminators as DAG
92    /// nodes because it does not create the necessary dependencies to prevent
93    /// reordering. A specialized scheduler can overide
94    /// TargetInstrInfo::isSchedulingBoundary then enable this flag to indicate
95    /// it has taken responsibility for scheduling the terminator correctly.
96    bool CanHandleTerminators;
97
98    /// State specific to the current scheduling region.
99    /// ------------------------------------------------
100
101    /// The block in which to insert instructions
102    MachineBasicBlock *BB;
103
104    /// The beginning of the range to be scheduled.
105    MachineBasicBlock::iterator RegionBegin;
106
107    /// The end of the range to be scheduled.
108    MachineBasicBlock::iterator RegionEnd;
109
110    /// Instructions in this region (distance(RegionBegin, RegionEnd)).
111    unsigned NumRegionInstrs;
112
113    /// After calling BuildSchedGraph, each machine instruction in the current
114    /// scheduling region is mapped to an SUnit.
115    DenseMap<MachineInstr*, SUnit*> MISUnitMap;
116
117    /// After calling BuildSchedGraph, each vreg used in the scheduling region
118    /// is mapped to a set of SUnits. These include all local vreg uses, not
119    /// just the uses for a singly defined vreg.
120    VReg2UseMap VRegUses;
121
122    /// State internal to DAG building.
123    /// -------------------------------
124
125    /// Defs, Uses - Remember where defs and uses of each register are as we
126    /// iterate upward through the instructions. This is allocated here instead
127    /// of inside BuildSchedGraph to avoid the need for it to be initialized and
128    /// destructed for each block.
129    Reg2SUnitsMap Defs;
130    Reg2SUnitsMap Uses;
131
132    /// Track the last instruction in this region defining each virtual register.
133    VReg2SUnitMap VRegDefs;
134
135    /// PendingLoads - Remember where unknown loads are after the most recent
136    /// unknown store, as we iterate. As with Defs and Uses, this is here
137    /// to minimize construction/destruction.
138    std::vector<SUnit *> PendingLoads;
139
140    /// DbgValues - Remember instruction that precedes DBG_VALUE.
141    /// These are generated by buildSchedGraph but persist so they can be
142    /// referenced when emitting the final schedule.
143    typedef std::vector<std::pair<MachineInstr *, MachineInstr *> >
144      DbgValueVector;
145    DbgValueVector DbgValues;
146    MachineInstr *FirstDbgValue;
147
148  public:
149    explicit ScheduleDAGInstrs(MachineFunction &mf,
150                               const MachineLoopInfo &mli,
151                               const MachineDominatorTree &mdt,
152                               bool IsPostRAFlag,
153                               LiveIntervals *LIS = 0);
154
155    virtual ~ScheduleDAGInstrs() {}
156
157    /// \brief Expose LiveIntervals for use in DAG mutators and such.
158    LiveIntervals *getLIS() const { return LIS; }
159
160    /// \brief Get the machine model for instruction scheduling.
161    const TargetSchedModel *getSchedModel() const { return &SchedModel; }
162
163    /// \brief Resolve and cache a resolved scheduling class for an SUnit.
164    const MCSchedClassDesc *getSchedClass(SUnit *SU) const {
165      if (!SU->SchedClass && SchedModel.hasInstrSchedModel())
166        SU->SchedClass = SchedModel.resolveSchedClass(SU->getInstr());
167      return SU->SchedClass;
168    }
169
170    /// begin - Return an iterator to the top of the current scheduling region.
171    MachineBasicBlock::iterator begin() const { return RegionBegin; }
172
173    /// end - Return an iterator to the bottom of the current scheduling region.
174    MachineBasicBlock::iterator end() const { return RegionEnd; }
175
176    /// newSUnit - Creates a new SUnit and return a ptr to it.
177    SUnit *newSUnit(MachineInstr *MI);
178
179    /// getSUnit - Return an existing SUnit for this MI, or NULL.
180    SUnit *getSUnit(MachineInstr *MI) const;
181
182    /// startBlock - Prepare to perform scheduling in the given block.
183    virtual void startBlock(MachineBasicBlock *BB);
184
185    /// finishBlock - Clean up after scheduling in the given block.
186    virtual void finishBlock();
187
188    /// Initialize the scheduler state for the next scheduling region.
189    virtual void enterRegion(MachineBasicBlock *bb,
190                             MachineBasicBlock::iterator begin,
191                             MachineBasicBlock::iterator end,
192                             unsigned regioninstrs);
193
194    /// Notify that the scheduler has finished scheduling the current region.
195    virtual void exitRegion();
196
197    /// buildSchedGraph - Build SUnits from the MachineBasicBlock that we are
198    /// input.
199    void buildSchedGraph(AliasAnalysis *AA, RegPressureTracker *RPTracker = 0,
200                         PressureDiffs *PDiffs = 0);
201
202    /// addSchedBarrierDeps - Add dependencies from instructions in the current
203    /// list of instructions being scheduled to scheduling barrier. We want to
204    /// make sure instructions which define registers that are either used by
205    /// the terminator or are live-out are properly scheduled. This is
206    /// especially important when the definition latency of the return value(s)
207    /// are too high to be hidden by the branch or when the liveout registers
208    /// used by instructions in the fallthrough block.
209    void addSchedBarrierDeps();
210
211    /// schedule - Order nodes according to selected style, filling
212    /// in the Sequence member.
213    ///
214    /// Typically, a scheduling algorithm will implement schedule() without
215    /// overriding enterRegion() or exitRegion().
216    virtual void schedule() = 0;
217
218    /// finalizeSchedule - Allow targets to perform final scheduling actions at
219    /// the level of the whole MachineFunction. By default does nothing.
220    virtual void finalizeSchedule() {}
221
222    virtual void dumpNode(const SUnit *SU) const;
223
224    /// Return a label for a DAG node that points to an instruction.
225    virtual std::string getGraphNodeLabel(const SUnit *SU) const;
226
227    /// Return a label for the region of code covered by the DAG.
228    virtual std::string getDAGName() const;
229
230  protected:
231    void initSUnits();
232    void addPhysRegDataDeps(SUnit *SU, unsigned OperIdx);
233    void addPhysRegDeps(SUnit *SU, unsigned OperIdx);
234    void addVRegDefDeps(SUnit *SU, unsigned OperIdx);
235    void addVRegUseDeps(SUnit *SU, unsigned OperIdx);
236  };
237
238  /// newSUnit - Creates a new SUnit and return a ptr to it.
239  inline SUnit *ScheduleDAGInstrs::newSUnit(MachineInstr *MI) {
240#ifndef NDEBUG
241    const SUnit *Addr = SUnits.empty() ? 0 : &SUnits[0];
242#endif
243    SUnits.push_back(SUnit(MI, (unsigned)SUnits.size()));
244    assert((Addr == 0 || Addr == &SUnits[0]) &&
245           "SUnits std::vector reallocated on the fly!");
246    SUnits.back().OrigNode = &SUnits.back();
247    return &SUnits.back();
248  }
249
250  /// getSUnit - Return an existing SUnit for this MI, or NULL.
251  inline SUnit *ScheduleDAGInstrs::getSUnit(MachineInstr *MI) const {
252    DenseMap<MachineInstr*, SUnit*>::const_iterator I = MISUnitMap.find(MI);
253    if (I == MISUnitMap.end())
254      return 0;
255    return I->second;
256  }
257} // namespace llvm
258
259#endif
260