1 | //===- ScheduleDAGInstrs.h - MachineInstr Scheduling ------------*- C++ -*-===// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | // |
9 | /// \file Implements the ScheduleDAGInstrs class, which implements scheduling |
10 | /// for a MachineInstr-based dependency graph. |
11 | // |
12 | //===----------------------------------------------------------------------===// |
13 | |
14 | #ifndef LLVM_CODEGEN_SCHEDULEDAGINSTRS_H |
15 | #define LLVM_CODEGEN_SCHEDULEDAGINSTRS_H |
16 | |
17 | #include "llvm/ADT/DenseMap.h" |
18 | #include "llvm/ADT/PointerIntPair.h" |
19 | #include "llvm/ADT/SmallVector.h" |
20 | #include "llvm/ADT/SparseMultiSet.h" |
21 | #include "llvm/ADT/SparseSet.h" |
22 | #include "llvm/ADT/identity.h" |
23 | #include "llvm/CodeGen/LivePhysRegs.h" |
24 | #include "llvm/CodeGen/MachineBasicBlock.h" |
25 | #include "llvm/CodeGen/ScheduleDAG.h" |
26 | #include "llvm/CodeGen/TargetRegisterInfo.h" |
27 | #include "llvm/CodeGen/TargetSchedule.h" |
28 | #include "llvm/MC/LaneBitmask.h" |
29 | #include <cassert> |
30 | #include <cstdint> |
31 | #include <list> |
32 | #include <string> |
33 | #include <utility> |
34 | #include <vector> |
35 | |
36 | namespace llvm { |
37 | |
38 | class AAResults; |
39 | class LiveIntervals; |
40 | class MachineFrameInfo; |
41 | class MachineFunction; |
42 | class MachineInstr; |
43 | class MachineLoopInfo; |
44 | class MachineOperand; |
45 | struct MCSchedClassDesc; |
46 | class PressureDiffs; |
47 | class PseudoSourceValue; |
48 | class RegPressureTracker; |
49 | class UndefValue; |
50 | class Value; |
51 | |
52 | /// An individual mapping from virtual register number to SUnit. |
53 | struct VReg2SUnit { |
54 | unsigned VirtReg; |
55 | LaneBitmask LaneMask; |
56 | SUnit *SU; |
57 | |
58 | VReg2SUnit(unsigned VReg, LaneBitmask LaneMask, SUnit *SU) |
59 | : VirtReg(VReg), LaneMask(LaneMask), SU(SU) {} |
60 | |
61 | unsigned getSparseSetIndex() const { |
62 | return Register::virtReg2Index(Reg: VirtReg); |
63 | } |
64 | }; |
65 | |
66 | /// Mapping from virtual register to SUnit including an operand index. |
67 | struct VReg2SUnitOperIdx : public VReg2SUnit { |
68 | unsigned OperandIndex; |
69 | |
70 | VReg2SUnitOperIdx(unsigned VReg, LaneBitmask LaneMask, |
71 | unsigned OperandIndex, SUnit *SU) |
72 | : VReg2SUnit(VReg, LaneMask, SU), OperandIndex(OperandIndex) {} |
73 | }; |
74 | |
75 | /// Record a physical register access. |
76 | /// For non-data-dependent uses, OpIdx == -1. |
77 | struct PhysRegSUOper { |
78 | SUnit *SU; |
79 | int OpIdx; |
80 | unsigned RegUnit; |
81 | |
82 | PhysRegSUOper(SUnit *su, int op, unsigned R) |
83 | : SU(su), OpIdx(op), RegUnit(R) {} |
84 | |
85 | unsigned getSparseSetIndex() const { return RegUnit; } |
86 | }; |
87 | |
88 | /// Use a SparseMultiSet to track physical registers. Storage is only |
89 | /// allocated once for the pass. It can be cleared in constant time and reused |
90 | /// without any frees. |
91 | using RegUnit2SUnitsMap = |
92 | SparseMultiSet<PhysRegSUOper, identity<unsigned>, uint16_t>; |
93 | |
94 | /// Use SparseSet as a SparseMap by relying on the fact that it never |
95 | /// compares ValueT's, only unsigned keys. This allows the set to be cleared |
96 | /// between scheduling regions in constant time as long as ValueT does not |
97 | /// require a destructor. |
98 | using VReg2SUnitMap = SparseSet<VReg2SUnit, VirtReg2IndexFunctor>; |
99 | |
100 | /// Track local uses of virtual registers. These uses are gathered by the DAG |
101 | /// builder and may be consulted by the scheduler to avoid iterating an entire |
102 | /// vreg use list. |
103 | using VReg2SUnitMultiMap = SparseMultiSet<VReg2SUnit, VirtReg2IndexFunctor>; |
104 | |
105 | using VReg2SUnitOperIdxMultiMap = |
106 | SparseMultiSet<VReg2SUnitOperIdx, VirtReg2IndexFunctor>; |
107 | |
108 | using ValueType = PointerUnion<const Value *, const PseudoSourceValue *>; |
109 | |
110 | struct UnderlyingObject : PointerIntPair<ValueType, 1, bool> { |
111 | UnderlyingObject(ValueType V, bool MayAlias) |
112 | : PointerIntPair<ValueType, 1, bool>(V, MayAlias) {} |
113 | |
114 | ValueType getValue() const { return getPointer(); } |
115 | bool mayAlias() const { return getInt(); } |
116 | }; |
117 | |
118 | using UnderlyingObjectsVector = SmallVector<UnderlyingObject, 4>; |
119 | |
120 | /// A ScheduleDAG for scheduling lists of MachineInstr. |
121 | class ScheduleDAGInstrs : public ScheduleDAG { |
122 | protected: |
123 | const MachineLoopInfo *MLI = nullptr; |
124 | const MachineFrameInfo &MFI; |
125 | |
126 | /// TargetSchedModel provides an interface to the machine model. |
127 | TargetSchedModel SchedModel; |
128 | |
129 | /// True if the DAG builder should remove kill flags (in preparation for |
130 | /// rescheduling). |
131 | bool RemoveKillFlags; |
132 | |
133 | /// The standard DAG builder does not normally include terminators as DAG |
134 | /// nodes because it does not create the necessary dependencies to prevent |
135 | /// reordering. A specialized scheduler can override |
136 | /// TargetInstrInfo::isSchedulingBoundary then enable this flag to indicate |
137 | /// it has taken responsibility for scheduling the terminator correctly. |
138 | bool CanHandleTerminators = false; |
139 | |
140 | /// Whether lane masks should get tracked. |
141 | bool TrackLaneMasks = false; |
142 | |
143 | // State specific to the current scheduling region. |
144 | // ------------------------------------------------ |
145 | |
146 | /// The block in which to insert instructions |
147 | MachineBasicBlock *BB = nullptr; |
148 | |
149 | /// The beginning of the range to be scheduled. |
150 | MachineBasicBlock::iterator RegionBegin; |
151 | |
152 | /// The end of the range to be scheduled. |
153 | MachineBasicBlock::iterator RegionEnd; |
154 | |
155 | /// Instructions in this region (distance(RegionBegin, RegionEnd)). |
156 | unsigned NumRegionInstrs = 0; |
157 | |
158 | /// After calling BuildSchedGraph, each machine instruction in the current |
159 | /// scheduling region is mapped to an SUnit. |
160 | DenseMap<MachineInstr*, SUnit*> MISUnitMap; |
161 | |
162 | // State internal to DAG building. |
163 | // ------------------------------- |
164 | |
165 | /// Defs, Uses - Remember where defs and uses of each register are as we |
166 | /// iterate upward through the instructions. This is allocated here instead |
167 | /// of inside BuildSchedGraph to avoid the need for it to be initialized and |
168 | /// destructed for each block. |
169 | RegUnit2SUnitsMap Defs; |
170 | RegUnit2SUnitsMap Uses; |
171 | |
172 | /// Tracks the last instruction(s) in this region defining each virtual |
173 | /// register. There may be multiple current definitions for a register with |
174 | /// disjunct lanemasks. |
175 | VReg2SUnitMultiMap CurrentVRegDefs; |
176 | /// Tracks the last instructions in this region using each virtual register. |
177 | VReg2SUnitOperIdxMultiMap CurrentVRegUses; |
178 | |
179 | AAResults *AAForDep = nullptr; |
180 | |
181 | /// Remember a generic side-effecting instruction as we proceed. |
182 | /// No other SU ever gets scheduled around it (except in the special |
183 | /// case of a huge region that gets reduced). |
184 | SUnit *BarrierChain = nullptr; |
185 | |
186 | public: |
187 | /// A list of SUnits, used in Value2SUsMap, during DAG construction. |
188 | /// Note: to gain speed it might be worth investigating an optimized |
189 | /// implementation of this data structure, such as a singly linked list |
190 | /// with a memory pool (SmallVector was tried but slow and SparseSet is not |
191 | /// applicable). |
192 | using SUList = std::list<SUnit *>; |
193 | |
194 | protected: |
195 | /// A map from ValueType to SUList, used during DAG construction, as |
196 | /// a means of remembering which SUs depend on which memory locations. |
197 | class Value2SUsMap; |
198 | |
199 | /// Reduces maps in FIFO order, by N SUs. This is better than turning |
200 | /// every Nth memory SU into BarrierChain in buildSchedGraph(), since |
201 | /// it avoids unnecessary edges between seen SUs above the new BarrierChain, |
202 | /// and those below it. |
203 | void reduceHugeMemNodeMaps(Value2SUsMap &stores, |
204 | Value2SUsMap &loads, unsigned N); |
205 | |
206 | /// Adds a chain edge between SUa and SUb, but only if both |
207 | /// AAResults and Target fail to deny the dependency. |
208 | void addChainDependency(SUnit *SUa, SUnit *SUb, |
209 | unsigned Latency = 0); |
210 | |
211 | /// Adds dependencies as needed from all SUs in list to SU. |
212 | void addChainDependencies(SUnit *SU, SUList &SUs, unsigned Latency) { |
213 | for (SUnit *Entry : SUs) |
214 | addChainDependency(SUa: SU, SUb: Entry, Latency); |
215 | } |
216 | |
217 | /// Adds dependencies as needed from all SUs in map, to SU. |
218 | void addChainDependencies(SUnit *SU, Value2SUsMap &Val2SUsMap); |
219 | |
220 | /// Adds dependencies as needed to SU, from all SUs mapped to V. |
221 | void addChainDependencies(SUnit *SU, Value2SUsMap &Val2SUsMap, |
222 | ValueType V); |
223 | |
224 | /// Adds barrier chain edges from all SUs in map, and then clear the map. |
225 | /// This is equivalent to insertBarrierChain(), but optimized for the common |
226 | /// case where the new BarrierChain (a global memory object) has a higher |
227 | /// NodeNum than all SUs in map. It is assumed BarrierChain has been set |
228 | /// before calling this. |
229 | void addBarrierChain(Value2SUsMap &map); |
230 | |
231 | /// Inserts a barrier chain in a huge region, far below current SU. |
232 | /// Adds barrier chain edges from all SUs in map with higher NodeNums than |
233 | /// this new BarrierChain, and remove them from map. It is assumed |
234 | /// BarrierChain has been set before calling this. |
235 | void insertBarrierChain(Value2SUsMap &map); |
236 | |
237 | /// For an unanalyzable memory access, this Value is used in maps. |
238 | UndefValue *UnknownValue; |
239 | |
240 | |
241 | /// Topo - A topological ordering for SUnits which permits fast IsReachable |
242 | /// and similar queries. |
243 | ScheduleDAGTopologicalSort Topo; |
244 | |
245 | using DbgValueVector = |
246 | std::vector<std::pair<MachineInstr *, MachineInstr *>>; |
247 | /// Remember instruction that precedes DBG_VALUE. |
248 | /// These are generated by buildSchedGraph but persist so they can be |
249 | /// referenced when emitting the final schedule. |
250 | DbgValueVector DbgValues; |
251 | MachineInstr *FirstDbgValue = nullptr; |
252 | |
253 | /// Set of live physical registers for updating kill flags. |
254 | LivePhysRegs LiveRegs; |
255 | |
256 | public: |
257 | explicit ScheduleDAGInstrs(MachineFunction &mf, |
258 | const MachineLoopInfo *mli, |
259 | bool RemoveKillFlags = false); |
260 | |
261 | ~ScheduleDAGInstrs() override = default; |
262 | |
263 | /// Gets the machine model for instruction scheduling. |
264 | const TargetSchedModel *getSchedModel() const { return &SchedModel; } |
265 | |
266 | /// Resolves and cache a resolved scheduling class for an SUnit. |
267 | const MCSchedClassDesc *getSchedClass(SUnit *SU) const { |
268 | if (!SU->SchedClass && SchedModel.hasInstrSchedModel()) |
269 | SU->SchedClass = SchedModel.resolveSchedClass(MI: SU->getInstr()); |
270 | return SU->SchedClass; |
271 | } |
272 | |
273 | /// IsReachable - Checks if SU is reachable from TargetSU. |
274 | bool IsReachable(SUnit *SU, SUnit *TargetSU) { |
275 | return Topo.IsReachable(SU, TargetSU); |
276 | } |
277 | |
278 | /// Returns an iterator to the top of the current scheduling region. |
279 | MachineBasicBlock::iterator begin() const { return RegionBegin; } |
280 | |
281 | /// Returns an iterator to the bottom of the current scheduling region. |
282 | MachineBasicBlock::iterator end() const { return RegionEnd; } |
283 | |
284 | /// Creates a new SUnit and return a ptr to it. |
285 | SUnit *newSUnit(MachineInstr *MI); |
286 | |
287 | /// Returns an existing SUnit for this MI, or nullptr. |
288 | SUnit *getSUnit(MachineInstr *MI) const; |
289 | |
290 | /// If this method returns true, handling of the scheduling regions |
291 | /// themselves (in case of a scheduling boundary in MBB) will be done |
292 | /// beginning with the topmost region of MBB. |
293 | virtual bool doMBBSchedRegionsTopDown() const { return false; } |
294 | |
295 | /// Prepares to perform scheduling in the given block. |
296 | virtual void startBlock(MachineBasicBlock *BB); |
297 | |
298 | /// Cleans up after scheduling in the given block. |
299 | virtual void finishBlock(); |
300 | |
301 | /// Initialize the DAG and common scheduler state for a new |
302 | /// scheduling region. This does not actually create the DAG, only clears |
303 | /// it. The scheduling driver may call BuildSchedGraph multiple times per |
304 | /// scheduling region. |
305 | virtual void enterRegion(MachineBasicBlock *bb, |
306 | MachineBasicBlock::iterator begin, |
307 | MachineBasicBlock::iterator end, |
308 | unsigned regioninstrs); |
309 | |
310 | /// Called when the scheduler has finished scheduling the current region. |
311 | virtual void exitRegion(); |
312 | |
313 | /// Builds SUnits for the current region. |
314 | /// If \p RPTracker is non-null, compute register pressure as a side effect. |
315 | /// The DAG builder is an efficient place to do it because it already visits |
316 | /// operands. |
317 | void buildSchedGraph(AAResults *AA, |
318 | RegPressureTracker *RPTracker = nullptr, |
319 | PressureDiffs *PDiffs = nullptr, |
320 | LiveIntervals *LIS = nullptr, |
321 | bool TrackLaneMasks = false); |
322 | |
323 | /// Adds dependencies from instructions in the current list of |
324 | /// instructions being scheduled to scheduling barrier. We want to make sure |
325 | /// instructions which define registers that are either used by the |
326 | /// terminator or are live-out are properly scheduled. This is especially |
327 | /// important when the definition latency of the return value(s) are too |
328 | /// high to be hidden by the branch or when the liveout registers used by |
329 | /// instructions in the fallthrough block. |
330 | void addSchedBarrierDeps(); |
331 | |
332 | /// Orders nodes according to selected style. |
333 | /// |
334 | /// Typically, a scheduling algorithm will implement schedule() without |
335 | /// overriding enterRegion() or exitRegion(). |
336 | virtual void schedule() = 0; |
337 | |
338 | /// Allow targets to perform final scheduling actions at the level of the |
339 | /// whole MachineFunction. By default does nothing. |
340 | virtual void finalizeSchedule() {} |
341 | |
342 | void dumpNode(const SUnit &SU) const override; |
343 | void dump() const override; |
344 | |
345 | /// Returns a label for a DAG node that points to an instruction. |
346 | std::string getGraphNodeLabel(const SUnit *SU) const override; |
347 | |
348 | /// Returns a label for the region of code covered by the DAG. |
349 | std::string getDAGName() const override; |
350 | |
351 | /// Fixes register kill flags that scheduling has made invalid. |
352 | void fixupKills(MachineBasicBlock &MBB); |
353 | |
354 | /// True if an edge can be added from PredSU to SuccSU without creating |
355 | /// a cycle. |
356 | bool canAddEdge(SUnit *SuccSU, SUnit *PredSU); |
357 | |
358 | /// Add a DAG edge to the given SU with the given predecessor |
359 | /// dependence data. |
360 | /// |
361 | /// \returns true if the edge may be added without creating a cycle OR if an |
362 | /// equivalent edge already existed (false indicates failure). |
363 | bool addEdge(SUnit *SuccSU, const SDep &PredDep); |
364 | |
365 | protected: |
366 | void initSUnits(); |
367 | void addPhysRegDataDeps(SUnit *SU, unsigned OperIdx); |
368 | void addPhysRegDeps(SUnit *SU, unsigned OperIdx); |
369 | void addVRegDefDeps(SUnit *SU, unsigned OperIdx); |
370 | void addVRegUseDeps(SUnit *SU, unsigned OperIdx); |
371 | |
372 | /// Returns a mask for which lanes get read/written by the given (register) |
373 | /// machine operand. |
374 | LaneBitmask getLaneMaskForMO(const MachineOperand &MO) const; |
375 | |
376 | /// Returns true if the def register in \p MO has no uses. |
377 | bool deadDefHasNoUse(const MachineOperand &MO); |
378 | }; |
379 | |
380 | /// Creates a new SUnit and return a ptr to it. |
381 | inline SUnit *ScheduleDAGInstrs::newSUnit(MachineInstr *MI) { |
382 | #ifndef NDEBUG |
383 | const SUnit *Addr = SUnits.empty() ? nullptr : &SUnits[0]; |
384 | #endif |
385 | SUnits.emplace_back(args&: MI, args: (unsigned)SUnits.size()); |
386 | assert((Addr == nullptr || Addr == &SUnits[0]) && |
387 | "SUnits std::vector reallocated on the fly!" ); |
388 | return &SUnits.back(); |
389 | } |
390 | |
391 | /// Returns an existing SUnit for this MI, or nullptr. |
392 | inline SUnit *ScheduleDAGInstrs::getSUnit(MachineInstr *MI) const { |
393 | return MISUnitMap.lookup(Val: MI); |
394 | } |
395 | |
396 | } // end namespace llvm |
397 | |
398 | #endif // LLVM_CODEGEN_SCHEDULEDAGINSTRS_H |
399 | |