Line data Source code
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 : /// \file Implements the ScheduleDAGInstrs class, which implements scheduling
11 : /// 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/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"
30 : #include <cassert>
31 : #include <cstdint>
32 : #include <list>
33 : #include <utility>
34 : #include <vector>
35 :
36 : namespace llvm {
37 :
38 : class LiveIntervals;
39 : class MachineFrameInfo;
40 : class MachineFunction;
41 : class MachineInstr;
42 : class MachineLoopInfo;
43 : class MachineOperand;
44 : struct MCSchedClassDesc;
45 : class PressureDiffs;
46 : class PseudoSourceValue;
47 : class RegPressureTracker;
48 : class UndefValue;
49 : class Value;
50 :
51 : /// An individual mapping from virtual register number to SUnit.
52 : struct VReg2SUnit {
53 : unsigned VirtReg;
54 : LaneBitmask LaneMask;
55 : SUnit *SU;
56 :
57 : VReg2SUnit(unsigned VReg, LaneBitmask LaneMask, SUnit *SU)
58 2266333 : : VirtReg(VReg), LaneMask(LaneMask), SU(SU) {}
59 :
60 0 : unsigned getSparseSetIndex() const {
61 0 : return TargetRegisterInfo::virtReg2Index(VirtReg);
62 : }
63 : };
64 :
65 : /// Mapping from virtual register to SUnit including an operand index.
66 : struct VReg2SUnitOperIdx : public VReg2SUnit {
67 : unsigned OperandIndex;
68 :
69 : VReg2SUnitOperIdx(unsigned VReg, LaneBitmask LaneMask,
70 : unsigned OperandIndex, SUnit *SU)
71 2392078 : : VReg2SUnit(VReg, LaneMask, SU), OperandIndex(OperandIndex) {}
72 : };
73 :
74 : /// Record a physical register access.
75 : /// For non-data-dependent uses, OpIdx == -1.
76 : struct PhysRegSUOper {
77 : SUnit *SU;
78 : int OpIdx;
79 : unsigned Reg;
80 :
81 6154555 : PhysRegSUOper(SUnit *su, int op, unsigned R): SU(su), OpIdx(op), Reg(R) {}
82 :
83 0 : unsigned getSparseSetIndex() const { return Reg; }
84 : };
85 :
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.
89 : using Reg2SUnitsMap =
90 : SparseMultiSet<PhysRegSUOper, identity<unsigned>, uint16_t>;
91 :
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>;
97 :
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
100 : /// vreg use list.
101 : using VReg2SUnitMultiMap = SparseMultiSet<VReg2SUnit, VirtReg2IndexFunctor>;
102 :
103 : using VReg2SUnitOperIdxMultiMap =
104 : SparseMultiSet<VReg2SUnitOperIdx, VirtReg2IndexFunctor>;
105 :
106 : using ValueType = PointerUnion<const Value *, const PseudoSourceValue *>;
107 :
108 : struct UnderlyingObject : PointerIntPair<ValueType, 1, bool> {
109 : UnderlyingObject(ValueType V, bool MayAlias)
110 : : PointerIntPair<ValueType, 1, bool>(V, MayAlias) {}
111 :
112 3247004 : ValueType getValue() const { return getPointer(); }
113 : bool mayAlias() const { return getInt(); }
114 : };
115 :
116 : using UnderlyingObjectsVector = SmallVector<UnderlyingObject, 4>;
117 :
118 : /// A ScheduleDAG for scheduling lists of MachineInstr.
119 : class ScheduleDAGInstrs : public ScheduleDAG {
120 : protected:
121 : const MachineLoopInfo *MLI;
122 : const MachineFrameInfo &MFI;
123 :
124 : /// TargetSchedModel provides an interface to the machine model.
125 : TargetSchedModel SchedModel;
126 :
127 : /// True if the DAG builder should remove kill flags (in preparation for
128 : /// rescheduling).
129 : bool RemoveKillFlags;
130 :
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;
137 :
138 : /// Whether lane masks should get tracked.
139 : bool TrackLaneMasks = false;
140 :
141 : // State specific to the current scheduling region.
142 : // ------------------------------------------------
143 :
144 : /// The block in which to insert instructions
145 : MachineBasicBlock *BB;
146 :
147 : /// The beginning of the range to be scheduled.
148 : MachineBasicBlock::iterator RegionBegin;
149 :
150 : /// The end of the range to be scheduled.
151 : MachineBasicBlock::iterator RegionEnd;
152 :
153 : /// Instructions in this region (distance(RegionBegin, RegionEnd)).
154 : unsigned NumRegionInstrs;
155 :
156 : /// After calling BuildSchedGraph, each machine instruction in the current
157 : /// scheduling region is mapped to an SUnit.
158 : DenseMap<MachineInstr*, SUnit*> MISUnitMap;
159 :
160 : // State internal to DAG building.
161 : // -------------------------------
162 :
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.
167 : Reg2SUnitsMap Defs;
168 : Reg2SUnitsMap Uses;
169 :
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;
176 :
177 : AliasAnalysis *AAForDep = nullptr;
178 :
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;
183 :
184 : public:
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
189 : /// applicable).
190 : using SUList = std::list<SUnit *>;
191 :
192 : protected:
193 : /// A map from ValueType to SUList, used during DAG construction, as
194 : /// a means of remembering which SUs depend on which memory locations.
195 : class Value2SUsMap;
196 :
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);
203 :
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);
208 :
209 : /// Adds dependencies as needed from all SUs in list to SU.
210 : void addChainDependencies(SUnit *SU, SUList &SUs, unsigned Latency) {
211 5250137 : for (SUnit *Entry : SUs)
212 4132405 : addChainDependency(SU, Entry, Latency);
213 : }
214 :
215 : /// Adds dependencies as needed from all SUs in map, to SU.
216 : void addChainDependencies(SUnit *SU, Value2SUsMap &Val2SUsMap);
217 :
218 : /// Adds dependencies as needed to SU, from all SUs mapped to V.
219 : void addChainDependencies(SUnit *SU, Value2SUsMap &Val2SUsMap,
220 : ValueType V);
221 :
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);
228 :
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);
234 :
235 : /// For an unanalyzable memory access, this Value is used in maps.
236 : UndefValue *UnknownValue;
237 :
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;
245 :
246 : /// Set of live physical registers for updating kill flags.
247 : LivePhysRegs LiveRegs;
248 :
249 : public:
250 : explicit ScheduleDAGInstrs(MachineFunction &mf,
251 : const MachineLoopInfo *mli,
252 : bool RemoveKillFlags = false);
253 :
254 703002 : ~ScheduleDAGInstrs() override = default;
255 :
256 : /// Gets the machine model for instruction scheduling.
257 462993 : const TargetSchedModel *getSchedModel() const { return &SchedModel; }
258 :
259 : /// Resolves and cache a resolved scheduling class for an SUnit.
260 5030667 : const MCSchedClassDesc *getSchedClass(SUnit *SU) const {
261 5030667 : if (!SU->SchedClass && SchedModel.hasInstrSchedModel())
262 1331801 : SU->SchedClass = SchedModel.resolveSchedClass(SU->getInstr());
263 5030667 : return SU->SchedClass;
264 : }
265 :
266 : /// Returns an iterator to the top of the current scheduling region.
267 0 : MachineBasicBlock::iterator begin() const { return RegionBegin; }
268 :
269 : /// Returns an iterator to the bottom of the current scheduling region.
270 0 : MachineBasicBlock::iterator end() const { return RegionEnd; }
271 :
272 : /// Creates a new SUnit and return a ptr to it.
273 : SUnit *newSUnit(MachineInstr *MI);
274 :
275 : /// Returns an existing SUnit for this MI, or nullptr.
276 : SUnit *getSUnit(MachineInstr *MI) const;
277 :
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 0 : virtual bool doMBBSchedRegionsTopDown() const { return false; }
282 :
283 : /// Prepares to perform scheduling in the given block.
284 : virtual void startBlock(MachineBasicBlock *BB);
285 :
286 : /// Cleans up after scheduling in the given block.
287 : virtual void finishBlock();
288 :
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);
297 :
298 : /// Called when the scheduler has finished scheduling the current region.
299 : virtual void exitRegion();
300 :
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
304 : /// operands.
305 : void buildSchedGraph(AliasAnalysis *AA,
306 : RegPressureTracker *RPTracker = nullptr,
307 : PressureDiffs *PDiffs = nullptr,
308 : LiveIntervals *LIS = nullptr,
309 : bool TrackLaneMasks = false);
310 :
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();
319 :
320 : /// Orders nodes according to selected style.
321 : ///
322 : /// Typically, a scheduling algorithm will implement schedule() without
323 : /// overriding enterRegion() or exitRegion().
324 : virtual void schedule() = 0;
325 :
326 : /// Allow targets to perform final scheduling actions at the level of the
327 : /// whole MachineFunction. By default does nothing.
328 170006 : virtual void finalizeSchedule() {}
329 :
330 : void dumpNode(const SUnit &SU) const override;
331 : void dump() const override;
332 :
333 : /// Returns a label for a DAG node that points to an instruction.
334 : std::string getGraphNodeLabel(const SUnit *SU) const override;
335 :
336 : /// Returns a label for the region of code covered by the DAG.
337 : std::string getDAGName() const override;
338 :
339 : /// Fixes register kill flags that scheduling has made invalid.
340 : void fixupKills(MachineBasicBlock &MBB);
341 :
342 : protected:
343 : void initSUnits();
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);
348 :
349 : /// Initializes register live-range state for updating kills.
350 : /// PostRA helper for rewriting kill flags.
351 : void startBlockForKills(MachineBasicBlock *BB);
352 :
353 : /// Toggles a register operand kill flag.
354 : ///
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);
358 :
359 : /// Returns a mask for which lanes get read/written by the given (register)
360 : /// machine operand.
361 : LaneBitmask getLaneMaskForMO(const MachineOperand &MO) const;
362 : };
363 :
364 : /// Creates a new SUnit and return a ptr to it.
365 : inline SUnit *ScheduleDAGInstrs::newSUnit(MachineInstr *MI) {
366 : #ifndef NDEBUG
367 : const SUnit *Addr = SUnits.empty() ? nullptr : &SUnits[0];
368 : #endif
369 7634052 : 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();
373 : }
374 :
375 : /// Returns an existing SUnit for this MI, or nullptr.
376 : inline SUnit *ScheduleDAGInstrs::getSUnit(MachineInstr *MI) const {
377 39198 : DenseMap<MachineInstr*, SUnit*>::const_iterator I = MISUnitMap.find(MI);
378 39198 : if (I == MISUnitMap.end())
379 : return nullptr;
380 34367 : return I->second;
381 : }
382 :
383 : } // end namespace llvm
384 :
385 : #endif // LLVM_CODEGEN_SCHEDULEDAGINSTRS_H
|
