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