1 //===- ScheduleDAGInstrs.h - MachineInstr Scheduling ------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 /// \file Implements the ScheduleDAGInstrs class, which implements scheduling
11 /// for a MachineInstr-based dependency graph.
13 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_CODEGEN_SCHEDULEDAGINSTRS_H
16 #define LLVM_CODEGEN_SCHEDULEDAGINSTRS_H
18 #include "llvm/ADT/DenseMap.h"
19 #include "llvm/ADT/PointerIntPair.h"
20 #include "llvm/ADT/STLExtras.h"
21 #include "llvm/ADT/SmallVector.h"
22 #include "llvm/ADT/SparseMultiSet.h"
23 #include "llvm/ADT/SparseSet.h"
24 #include "llvm/CodeGen/LivePhysRegs.h"
25 #include "llvm/CodeGen/MachineBasicBlock.h"
26 #include "llvm/CodeGen/ScheduleDAG.h"
27 #include "llvm/CodeGen/TargetRegisterInfo.h"
28 #include "llvm/CodeGen/TargetSchedule.h"
29 #include "llvm/MC/LaneBitmask.h"
39 class MachineFrameInfo;
40 class MachineFunction;
42 class MachineLoopInfo;
44 struct MCSchedClassDesc;
46 class PseudoSourceValue;
47 class RegPressureTracker;
51 /// An individual mapping from virtual register number to SUnit.
57 VReg2SUnit(unsigned VReg, LaneBitmask LaneMask, SUnit *SU)
58 : VirtReg(VReg), LaneMask(LaneMask), SU(SU) {}
60 unsigned getSparseSetIndex() const {
61 return TargetRegisterInfo::virtReg2Index(VirtReg);
65 /// Mapping from virtual register to SUnit including an operand index.
66 struct VReg2SUnitOperIdx : public VReg2SUnit {
67 unsigned OperandIndex;
69 VReg2SUnitOperIdx(unsigned VReg, LaneBitmask LaneMask,
70 unsigned OperandIndex, SUnit *SU)
71 : VReg2SUnit(VReg, LaneMask, SU), OperandIndex(OperandIndex) {}
74 /// Record a physical register access.
75 /// For non-data-dependent uses, OpIdx == -1.
76 struct PhysRegSUOper {
81 PhysRegSUOper(SUnit *su, int op, unsigned R): SU(su), OpIdx(op), Reg(R) {}
83 unsigned getSparseSetIndex() const { return Reg; }
86 /// Use a SparseMultiSet to track physical registers. Storage is only
87 /// allocated once for the pass. It can be cleared in constant time and reused
88 /// without any frees.
90 SparseMultiSet<PhysRegSUOper, identity<unsigned>, uint16_t>;
92 /// Use SparseSet as a SparseMap by relying on the fact that it never
93 /// compares ValueT's, only unsigned keys. This allows the set to be cleared
94 /// between scheduling regions in constant time as long as ValueT does not
95 /// require a destructor.
96 using VReg2SUnitMap = SparseSet<VReg2SUnit, VirtReg2IndexFunctor>;
98 /// Track local uses of virtual registers. These uses are gathered by the DAG
99 /// builder and may be consulted by the scheduler to avoid iterating an entire
101 using VReg2SUnitMultiMap = SparseMultiSet<VReg2SUnit, VirtReg2IndexFunctor>;
103 using VReg2SUnitOperIdxMultiMap =
104 SparseMultiSet<VReg2SUnitOperIdx, VirtReg2IndexFunctor>;
106 using ValueType = PointerUnion<const Value *, const PseudoSourceValue *>;
108 struct UnderlyingObject : PointerIntPair<ValueType, 1, bool> {
109 UnderlyingObject(ValueType V, bool MayAlias)
110 : PointerIntPair<ValueType, 1, bool>(V, MayAlias) {}
112 ValueType getValue() const { return getPointer(); }
113 bool mayAlias() const { return getInt(); }
116 using UnderlyingObjectsVector = SmallVector<UnderlyingObject, 4>;
118 /// A ScheduleDAG for scheduling lists of MachineInstr.
119 class ScheduleDAGInstrs : public ScheduleDAG {
121 const MachineLoopInfo *MLI;
122 const MachineFrameInfo &MFI;
124 /// TargetSchedModel provides an interface to the machine model.
125 TargetSchedModel SchedModel;
127 /// True if the DAG builder should remove kill flags (in preparation for
129 bool RemoveKillFlags;
131 /// The standard DAG builder does not normally include terminators as DAG
132 /// nodes because it does not create the necessary dependencies to prevent
133 /// reordering. A specialized scheduler can override
134 /// TargetInstrInfo::isSchedulingBoundary then enable this flag to indicate
135 /// it has taken responsibility for scheduling the terminator correctly.
136 bool CanHandleTerminators = false;
138 /// Whether lane masks should get tracked.
139 bool TrackLaneMasks = false;
141 // State specific to the current scheduling region.
142 // ------------------------------------------------
144 /// The block in which to insert instructions
145 MachineBasicBlock *BB;
147 /// The beginning of the range to be scheduled.
148 MachineBasicBlock::iterator RegionBegin;
150 /// The end of the range to be scheduled.
151 MachineBasicBlock::iterator RegionEnd;
153 /// Instructions in this region (distance(RegionBegin, RegionEnd)).
154 unsigned NumRegionInstrs;
156 /// After calling BuildSchedGraph, each machine instruction in the current
157 /// scheduling region is mapped to an SUnit.
158 DenseMap<MachineInstr*, SUnit*> MISUnitMap;
160 // State internal to DAG building.
161 // -------------------------------
163 /// Defs, Uses - Remember where defs and uses of each register are as we
164 /// iterate upward through the instructions. This is allocated here instead
165 /// of inside BuildSchedGraph to avoid the need for it to be initialized and
166 /// destructed for each block.
170 /// Tracks the last instruction(s) in this region defining each virtual
171 /// register. There may be multiple current definitions for a register with
172 /// disjunct lanemasks.
173 VReg2SUnitMultiMap CurrentVRegDefs;
174 /// Tracks the last instructions in this region using each virtual register.
175 VReg2SUnitOperIdxMultiMap CurrentVRegUses;
177 AliasAnalysis *AAForDep = nullptr;
179 /// Remember a generic side-effecting instruction as we proceed.
180 /// No other SU ever gets scheduled around it (except in the special
181 /// case of a huge region that gets reduced).
182 SUnit *BarrierChain = nullptr;
185 /// A list of SUnits, used in Value2SUsMap, during DAG construction.
186 /// Note: to gain speed it might be worth investigating an optimized
187 /// implementation of this data structure, such as a singly linked list
188 /// with a memory pool (SmallVector was tried but slow and SparseSet is not
190 using SUList = std::list<SUnit *>;
193 /// A map from ValueType to SUList, used during DAG construction, as
194 /// a means of remembering which SUs depend on which memory locations.
197 /// Reduces maps in FIFO order, by N SUs. This is better than turning
198 /// every Nth memory SU into BarrierChain in buildSchedGraph(), since
199 /// it avoids unnecessary edges between seen SUs above the new BarrierChain,
200 /// and those below it.
201 void reduceHugeMemNodeMaps(Value2SUsMap &stores,
202 Value2SUsMap &loads, unsigned N);
204 /// Adds a chain edge between SUa and SUb, but only if both
205 /// AliasAnalysis and Target fail to deny the dependency.
206 void addChainDependency(SUnit *SUa, SUnit *SUb,
207 unsigned Latency = 0);
209 /// Adds dependencies as needed from all SUs in list to SU.
210 void addChainDependencies(SUnit *SU, SUList &SUs, unsigned Latency) {
211 for (SUnit *Entry : SUs)
212 addChainDependency(SU, Entry, Latency);
215 /// Adds dependencies as needed from all SUs in map, to SU.
216 void addChainDependencies(SUnit *SU, Value2SUsMap &Val2SUsMap);
218 /// Adds dependencies as needed to SU, from all SUs mapped to V.
219 void addChainDependencies(SUnit *SU, Value2SUsMap &Val2SUsMap,
222 /// Adds barrier chain edges from all SUs in map, and then clear the map.
223 /// This is equivalent to insertBarrierChain(), but optimized for the common
224 /// case where the new BarrierChain (a global memory object) has a higher
225 /// NodeNum than all SUs in map. It is assumed BarrierChain has been set
226 /// before calling this.
227 void addBarrierChain(Value2SUsMap &map);
229 /// Inserts a barrier chain in a huge region, far below current SU.
230 /// Adds barrier chain edges from all SUs in map with higher NodeNums than
231 /// this new BarrierChain, and remove them from map. It is assumed
232 /// BarrierChain has been set before calling this.
233 void insertBarrierChain(Value2SUsMap &map);
235 /// For an unanalyzable memory access, this Value is used in maps.
236 UndefValue *UnknownValue;
238 using DbgValueVector =
239 std::vector<std::pair<MachineInstr *, MachineInstr *>>;
240 /// Remember instruction that precedes DBG_VALUE.
241 /// These are generated by buildSchedGraph but persist so they can be
242 /// referenced when emitting the final schedule.
243 DbgValueVector DbgValues;
244 MachineInstr *FirstDbgValue = nullptr;
246 /// Set of live physical registers for updating kill flags.
247 LivePhysRegs LiveRegs;
250 explicit ScheduleDAGInstrs(MachineFunction &mf,
251 const MachineLoopInfo *mli,
252 bool RemoveKillFlags = false);
254 ~ScheduleDAGInstrs() override = default;
256 /// Gets the machine model for instruction scheduling.
257 const TargetSchedModel *getSchedModel() const { return &SchedModel; }
259 /// Resolves and cache a resolved scheduling class for an SUnit.
260 const MCSchedClassDesc *getSchedClass(SUnit *SU) const {
261 if (!SU->SchedClass && SchedModel.hasInstrSchedModel())
262 SU->SchedClass = SchedModel.resolveSchedClass(SU->getInstr());
263 return SU->SchedClass;
266 /// Returns an iterator to the top of the current scheduling region.
267 MachineBasicBlock::iterator begin() const { return RegionBegin; }
269 /// Returns an iterator to the bottom of the current scheduling region.
270 MachineBasicBlock::iterator end() const { return RegionEnd; }
272 /// Creates a new SUnit and return a ptr to it.
273 SUnit *newSUnit(MachineInstr *MI);
275 /// Returns an existing SUnit for this MI, or nullptr.
276 SUnit *getSUnit(MachineInstr *MI) const;
278 /// If this method returns true, handling of the scheduling regions
279 /// themselves (in case of a scheduling boundary in MBB) will be done
280 /// beginning with the topmost region of MBB.
281 virtual bool doMBBSchedRegionsTopDown() const { return false; }
283 /// Prepares to perform scheduling in the given block.
284 virtual void startBlock(MachineBasicBlock *BB);
286 /// Cleans up after scheduling in the given block.
287 virtual void finishBlock();
289 /// Initialize the DAG and common scheduler state for a new
290 /// scheduling region. This does not actually create the DAG, only clears
291 /// it. The scheduling driver may call BuildSchedGraph multiple times per
292 /// scheduling region.
293 virtual void enterRegion(MachineBasicBlock *bb,
294 MachineBasicBlock::iterator begin,
295 MachineBasicBlock::iterator end,
296 unsigned regioninstrs);
298 /// Called when the scheduler has finished scheduling the current region.
299 virtual void exitRegion();
301 /// Builds SUnits for the current region.
302 /// If \p RPTracker is non-null, compute register pressure as a side effect.
303 /// The DAG builder is an efficient place to do it because it already visits
305 void buildSchedGraph(AliasAnalysis *AA,
306 RegPressureTracker *RPTracker = nullptr,
307 PressureDiffs *PDiffs = nullptr,
308 LiveIntervals *LIS = nullptr,
309 bool TrackLaneMasks = false);
311 /// Adds dependencies from instructions in the current list of
312 /// instructions being scheduled to scheduling barrier. We want to make sure
313 /// instructions which define registers that are either used by the
314 /// terminator or are live-out are properly scheduled. This is especially
315 /// important when the definition latency of the return value(s) are too
316 /// high to be hidden by the branch or when the liveout registers used by
317 /// instructions in the fallthrough block.
318 void addSchedBarrierDeps();
320 /// Orders nodes according to selected style.
322 /// Typically, a scheduling algorithm will implement schedule() without
323 /// overriding enterRegion() or exitRegion().
324 virtual void schedule() = 0;
326 /// Allow targets to perform final scheduling actions at the level of the
327 /// whole MachineFunction. By default does nothing.
328 virtual void finalizeSchedule() {}
330 void dumpNode(const SUnit &SU) const override;
331 void dump() const override;
333 /// Returns a label for a DAG node that points to an instruction.
334 std::string getGraphNodeLabel(const SUnit *SU) const override;
336 /// Returns a label for the region of code covered by the DAG.
337 std::string getDAGName() const override;
339 /// Fixes register kill flags that scheduling has made invalid.
340 void fixupKills(MachineBasicBlock &MBB);
344 void addPhysRegDataDeps(SUnit *SU, unsigned OperIdx);
345 void addPhysRegDeps(SUnit *SU, unsigned OperIdx);
346 void addVRegDefDeps(SUnit *SU, unsigned OperIdx);
347 void addVRegUseDeps(SUnit *SU, unsigned OperIdx);
349 /// Initializes register live-range state for updating kills.
350 /// PostRA helper for rewriting kill flags.
351 void startBlockForKills(MachineBasicBlock *BB);
353 /// Toggles a register operand kill flag.
355 /// Other adjustments may be made to the instruction if necessary. Return
356 /// true if the operand has been deleted, false if not.
357 void toggleKillFlag(MachineInstr &MI, MachineOperand &MO);
359 /// Returns a mask for which lanes get read/written by the given (register)
361 LaneBitmask getLaneMaskForMO(const MachineOperand &MO) const;
364 /// Creates a new SUnit and return a ptr to it.
365 inline SUnit *ScheduleDAGInstrs::newSUnit(MachineInstr *MI) {
367 const SUnit *Addr = SUnits.empty() ? nullptr : &SUnits[0];
369 SUnits.emplace_back(MI, (unsigned)SUnits.size());
370 assert((Addr == nullptr || Addr == &SUnits[0]) &&
371 "SUnits std::vector reallocated on the fly!");
372 return &SUnits.back();
375 /// Returns an existing SUnit for this MI, or nullptr.
376 inline SUnit *ScheduleDAGInstrs::getSUnit(MachineInstr *MI) const {
377 DenseMap<MachineInstr*, SUnit*>::const_iterator I = MISUnitMap.find(MI);
378 if (I == MISUnitMap.end())
383 } // end namespace llvm
385 #endif // LLVM_CODEGEN_SCHEDULEDAGINSTRS_H