LLVM 20.0.0git
ScheduleDAGInstrs.h
Go to the documentation of this file.
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"
21#include "llvm/ADT/identity.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
36namespace 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;
57
59 : VirtReg(VReg), LaneMask(LaneMask), SU(SU) {}
60
61 unsigned getSparseSetIndex() const {
63 }
64 };
65
66 /// Mapping from virtual register to SUnit including an operand index.
67 struct VReg2SUnitOperIdx : public VReg2SUnit {
68 unsigned OperandIndex;
69
71 unsigned OperandIndex, SUnit *SU)
73 };
74
75 /// Record a physical register access.
76 /// For non-data-dependent uses, OpIdx == -1.
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.
93
94 /// Track local uses of virtual registers. These uses are gathered by the DAG
95 /// builder and may be consulted by the scheduler to avoid iterating an entire
96 /// vreg use list.
98
101
103
104 struct UnderlyingObject : PointerIntPair<ValueType, 1, bool> {
105 UnderlyingObject(ValueType V, bool MayAlias)
106 : PointerIntPair<ValueType, 1, bool>(V, MayAlias) {}
107
108 ValueType getValue() const { return getPointer(); }
109 bool mayAlias() const { return getInt(); }
110 };
111
113
114 /// A ScheduleDAG for scheduling lists of MachineInstr.
116 protected:
117 const MachineLoopInfo *MLI = nullptr;
119
120 /// TargetSchedModel provides an interface to the machine model.
122
123 /// True if the DAG builder should remove kill flags (in preparation for
124 /// rescheduling).
126
127 /// The standard DAG builder does not normally include terminators as DAG
128 /// nodes because it does not create the necessary dependencies to prevent
129 /// reordering. A specialized scheduler can override
130 /// TargetInstrInfo::isSchedulingBoundary then enable this flag to indicate
131 /// it has taken responsibility for scheduling the terminator correctly.
133
134 /// Whether lane masks should get tracked.
135 bool TrackLaneMasks = false;
136
137 // State specific to the current scheduling region.
138 // ------------------------------------------------
139
140 /// The block in which to insert instructions
142
143 /// The beginning of the range to be scheduled.
145
146 /// The end of the range to be scheduled.
148
149 /// Instructions in this region (distance(RegionBegin, RegionEnd)).
150 unsigned NumRegionInstrs = 0;
151
152 /// After calling BuildSchedGraph, each machine instruction in the current
153 /// scheduling region is mapped to an SUnit.
155
156 // State internal to DAG building.
157 // -------------------------------
158
159 /// Defs, Uses - Remember where defs and uses of each register are as we
160 /// iterate upward through the instructions. This is allocated here instead
161 /// of inside BuildSchedGraph to avoid the need for it to be initialized and
162 /// destructed for each block.
165
166 /// Tracks the last instruction(s) in this region defining each virtual
167 /// register. There may be multiple current definitions for a register with
168 /// disjunct lanemasks.
170 /// Tracks the last instructions in this region using each virtual register.
172
173 mutable std::optional<BatchAAResults> AAForDep;
174
175 /// Remember a generic side-effecting instruction as we proceed.
176 /// No other SU ever gets scheduled around it (except in the special
177 /// case of a huge region that gets reduced).
178 SUnit *BarrierChain = nullptr;
179
180 public:
181 /// A list of SUnits, used in Value2SUsMap, during DAG construction.
182 /// Note: to gain speed it might be worth investigating an optimized
183 /// implementation of this data structure, such as a singly linked list
184 /// with a memory pool (SmallVector was tried but slow and SparseSet is not
185 /// applicable).
186 using SUList = std::list<SUnit *>;
187
188 /// The direction that should be used to dump the scheduled Sequence.
194 };
195
197
198 protected:
200
201 /// A map from ValueType to SUList, used during DAG construction, as
202 /// a means of remembering which SUs depend on which memory locations.
203 class Value2SUsMap;
204
205 /// Returns a (possibly null) pointer to the current BatchAAResults.
207 if (AAForDep.has_value())
208 return &AAForDep.value();
209 return nullptr;
210 }
211
212 /// Reduces maps in FIFO order, by N SUs. This is better than turning
213 /// every Nth memory SU into BarrierChain in buildSchedGraph(), since
214 /// it avoids unnecessary edges between seen SUs above the new BarrierChain,
215 /// and those below it.
216 void reduceHugeMemNodeMaps(Value2SUsMap &stores,
217 Value2SUsMap &loads, unsigned N);
218
219 /// Adds a chain edge between SUa and SUb, but only if both
220 /// AAResults and Target fail to deny the dependency.
221 void addChainDependency(SUnit *SUa, SUnit *SUb,
222 unsigned Latency = 0);
223
224 /// Adds dependencies as needed from all SUs in list to SU.
225 void addChainDependencies(SUnit *SU, SUList &SUs, unsigned Latency) {
226 for (SUnit *Entry : SUs)
227 addChainDependency(SU, Entry, Latency);
228 }
229
230 /// Adds dependencies as needed from all SUs in map, to SU.
231 void addChainDependencies(SUnit *SU, Value2SUsMap &Val2SUsMap);
232
233 /// Adds dependencies as needed to SU, from all SUs mapped to V.
234 void addChainDependencies(SUnit *SU, Value2SUsMap &Val2SUsMap,
235 ValueType V);
236
237 /// Adds barrier chain edges from all SUs in map, and then clear the map.
238 /// This is equivalent to insertBarrierChain(), but optimized for the common
239 /// case where the new BarrierChain (a global memory object) has a higher
240 /// NodeNum than all SUs in map. It is assumed BarrierChain has been set
241 /// before calling this.
242 void addBarrierChain(Value2SUsMap &map);
243
244 /// Inserts a barrier chain in a huge region, far below current SU.
245 /// Adds barrier chain edges from all SUs in map with higher NodeNums than
246 /// this new BarrierChain, and remove them from map. It is assumed
247 /// BarrierChain has been set before calling this.
248 void insertBarrierChain(Value2SUsMap &map);
249
250 /// For an unanalyzable memory access, this Value is used in maps.
252
253
254 /// Topo - A topological ordering for SUnits which permits fast IsReachable
255 /// and similar queries.
257
259 std::vector<std::pair<MachineInstr *, MachineInstr *>>;
260 /// Remember instruction that precedes DBG_VALUE.
261 /// These are generated by buildSchedGraph but persist so they can be
262 /// referenced when emitting the final schedule.
265
266 /// Set of live physical registers for updating kill flags.
268
269 public:
271 const MachineLoopInfo *mli,
272 bool RemoveKillFlags = false);
273
274 ~ScheduleDAGInstrs() override = default;
275
276 /// Gets the machine model for instruction scheduling.
277 const TargetSchedModel *getSchedModel() const { return &SchedModel; }
278
279 /// Resolves and cache a resolved scheduling class for an SUnit.
283 return SU->SchedClass;
284 }
285
286 /// IsReachable - Checks if SU is reachable from TargetSU.
287 bool IsReachable(SUnit *SU, SUnit *TargetSU) {
288 return Topo.IsReachable(SU, TargetSU);
289 }
290
291 /// Returns an iterator to the top of the current scheduling region.
293
294 /// Returns an iterator to the bottom of the current scheduling region.
296
297 /// Creates a new SUnit and return a ptr to it.
299
300 /// Returns an existing SUnit for this MI, or nullptr.
301 SUnit *getSUnit(MachineInstr *MI) const;
302
303 /// If this method returns true, handling of the scheduling regions
304 /// themselves (in case of a scheduling boundary in MBB) will be done
305 /// beginning with the topmost region of MBB.
306 virtual bool doMBBSchedRegionsTopDown() const { return false; }
307
308 /// Prepares to perform scheduling in the given block.
309 virtual void startBlock(MachineBasicBlock *BB);
310
311 /// Cleans up after scheduling in the given block.
312 virtual void finishBlock();
313
314 /// Initialize the DAG and common scheduler state for a new
315 /// scheduling region. This does not actually create the DAG, only clears
316 /// it. The scheduling driver may call BuildSchedGraph multiple times per
317 /// scheduling region.
318 virtual void enterRegion(MachineBasicBlock *bb,
321 unsigned regioninstrs);
322
323 /// Called when the scheduler has finished scheduling the current region.
324 virtual void exitRegion();
325
326 /// Builds SUnits for the current region.
327 /// If \p RPTracker is non-null, compute register pressure as a side effect.
328 /// The DAG builder is an efficient place to do it because it already visits
329 /// operands.
330 void buildSchedGraph(AAResults *AA,
331 RegPressureTracker *RPTracker = nullptr,
332 PressureDiffs *PDiffs = nullptr,
333 LiveIntervals *LIS = nullptr,
334 bool TrackLaneMasks = false);
335
336 /// Adds dependencies from instructions in the current list of
337 /// instructions being scheduled to scheduling barrier. We want to make sure
338 /// instructions which define registers that are either used by the
339 /// terminator or are live-out are properly scheduled. This is especially
340 /// important when the definition latency of the return value(s) are too
341 /// high to be hidden by the branch or when the liveout registers used by
342 /// instructions in the fallthrough block.
343 void addSchedBarrierDeps();
344
345 /// Orders nodes according to selected style.
346 ///
347 /// Typically, a scheduling algorithm will implement schedule() without
348 /// overriding enterRegion() or exitRegion().
349 virtual void schedule() = 0;
350
351 /// Allow targets to perform final scheduling actions at the level of the
352 /// whole MachineFunction. By default does nothing.
353 virtual void finalizeSchedule() {}
354
355 void dumpNode(const SUnit &SU) const override;
356 void dump() const override;
357
358 /// Returns a label for a DAG node that points to an instruction.
359 std::string getGraphNodeLabel(const SUnit *SU) const override;
360
361 /// Returns a label for the region of code covered by the DAG.
362 std::string getDAGName() const override;
363
364 /// Fixes register kill flags that scheduling has made invalid.
366
367 /// True if an edge can be added from PredSU to SuccSU without creating
368 /// a cycle.
369 bool canAddEdge(SUnit *SuccSU, SUnit *PredSU);
370
371 /// Add a DAG edge to the given SU with the given predecessor
372 /// dependence data.
373 ///
374 /// \returns true if the edge may be added without creating a cycle OR if an
375 /// equivalent edge already existed (false indicates failure).
376 bool addEdge(SUnit *SuccSU, const SDep &PredDep);
377
378 protected:
379 void initSUnits();
380 void addPhysRegDataDeps(SUnit *SU, unsigned OperIdx);
381 void addPhysRegDeps(SUnit *SU, unsigned OperIdx);
382 void addVRegDefDeps(SUnit *SU, unsigned OperIdx);
383 void addVRegUseDeps(SUnit *SU, unsigned OperIdx);
384
385 /// Returns a mask for which lanes get read/written by the given (register)
386 /// machine operand.
388
389 /// Returns true if the def register in \p MO has no uses.
390 bool deadDefHasNoUse(const MachineOperand &MO);
391 };
392
393 /// Creates a new SUnit and return a ptr to it.
395#ifndef NDEBUG
396 const SUnit *Addr = SUnits.empty() ? nullptr : &SUnits[0];
397#endif
398 SUnits.emplace_back(MI, (unsigned)SUnits.size());
399 assert((Addr == nullptr || Addr == &SUnits[0]) &&
400 "SUnits std::vector reallocated on the fly!");
401 return &SUnits.back();
402 }
403
404 /// Returns an existing SUnit for this MI, or nullptr.
406 return MISUnitMap.lookup(MI);
407 }
408
409} // end namespace llvm
410
411#endif // LLVM_CODEGEN_SCHEDULEDAGINSTRS_H
MachineBasicBlock & MBB
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
This file defines the DenseMap class.
uint64_t Addr
#define op(i)
hexagon widen Hexagon Store false hexagon widen loads
hexagon widen stores
IRTranslator LLVM IR MI
A common definition of LaneBitmask for use in TableGen and CodeGen.
A set of register units.
This file defines the PointerIntPair class.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
This file defines the SparseMultiSet class, which adds multiset behavior to the SparseSet.
This class is a wrapper over an AAResults, and it is intended to be used only when there are no IR ch...
A set of register units used to track register liveness.
Definition: LiveRegUnits.h:30
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted.
Representation of each machine instruction.
Definition: MachineInstr.h:71
MachineOperand class - Representation of each machine instruction operand.
PointerIntPair - This class implements a pair of a pointer and small integer.
Array of PressureDiffs.
Track the current register pressure at some position in the instruction stream, and remember the high...
static unsigned virtReg2Index(Register Reg)
Convert a virtual register number to a 0-based index.
Definition: Register.h:77
Scheduling dependency.
Definition: ScheduleDAG.h:49
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:242
const MCSchedClassDesc * SchedClass
nullptr or resolved SchedClass.
Definition: ScheduleDAG.h:255
MachineInstr * getInstr() const
Returns the representative MachineInstr for this SUnit.
Definition: ScheduleDAG.h:390
A ScheduleDAG for scheduling lists of MachineInstr.
LiveRegUnits LiveRegs
Set of live physical registers for updating kill flags.
DenseMap< MachineInstr *, SUnit * > MISUnitMap
After calling BuildSchedGraph, each machine instruction in the current scheduling region is mapped to...
void addVRegUseDeps(SUnit *SU, unsigned OperIdx)
Adds a register data dependency if the instruction that defines the virtual register used at OperIdx ...
void addVRegDefDeps(SUnit *SU, unsigned OperIdx)
Adds register output and data dependencies from this SUnit to instructions that occur later in the sa...
virtual void finishBlock()
Cleans up after scheduling in the given block.
MachineBasicBlock::iterator end() const
Returns an iterator to the bottom of the current scheduling region.
std::string getDAGName() const override
Returns a label for the region of code covered by the DAG.
MachineBasicBlock * BB
The block in which to insert instructions.
virtual void startBlock(MachineBasicBlock *BB)
Prepares to perform scheduling in the given block.
bool CanHandleTerminators
The standard DAG builder does not normally include terminators as DAG nodes because it does not creat...
void addBarrierChain(Value2SUsMap &map)
Adds barrier chain edges from all SUs in map, and then clear the map.
void reduceHugeMemNodeMaps(Value2SUsMap &stores, Value2SUsMap &loads, unsigned N)
Reduces maps in FIFO order, by N SUs.
void addPhysRegDeps(SUnit *SU, unsigned OperIdx)
Adds register dependencies (data, anti, and output) from this SUnit to following instructions in the ...
const TargetSchedModel * getSchedModel() const
Gets the machine model for instruction scheduling.
MachineBasicBlock::iterator RegionEnd
The end of the range to be scheduled.
VReg2SUnitOperIdxMultiMap CurrentVRegUses
Tracks the last instructions in this region using each virtual register.
void addChainDependencies(SUnit *SU, SUList &SUs, unsigned Latency)
Adds dependencies as needed from all SUs in list to SU.
const MCSchedClassDesc * getSchedClass(SUnit *SU) const
Resolves and cache a resolved scheduling class for an SUnit.
void fixupKills(MachineBasicBlock &MBB)
Fixes register kill flags that scheduling has made invalid.
~ScheduleDAGInstrs() override=default
void addPhysRegDataDeps(SUnit *SU, unsigned OperIdx)
MO is an operand of SU's instruction that defines a physical register.
std::vector< std::pair< MachineInstr *, MachineInstr * > > DbgValueVector
LaneBitmask getLaneMaskForMO(const MachineOperand &MO) const
Returns a mask for which lanes get read/written by the given (register) machine operand.
DbgValueVector DbgValues
Remember instruction that precedes DBG_VALUE.
SUnit * newSUnit(MachineInstr *MI)
Creates a new SUnit and return a ptr to it.
void initSUnits()
Creates an SUnit for each real instruction, numbered in top-down topological order.
virtual void finalizeSchedule()
Allow targets to perform final scheduling actions at the level of the whole MachineFunction.
bool addEdge(SUnit *SuccSU, const SDep &PredDep)
Add a DAG edge to the given SU with the given predecessor dependence data.
ScheduleDAGTopologicalSort Topo
Topo - A topological ordering for SUnits which permits fast IsReachable and similar queries.
DumpDirection
The direction that should be used to dump the scheduled Sequence.
std::list< SUnit * > SUList
A list of SUnits, used in Value2SUsMap, during DAG construction.
SUnit * BarrierChain
Remember a generic side-effecting instruction as we proceed.
BatchAAResults * getAAForDep() const
Returns a (possibly null) pointer to the current BatchAAResults.
bool TrackLaneMasks
Whether lane masks should get tracked.
void dumpNode(const SUnit &SU) const override
bool IsReachable(SUnit *SU, SUnit *TargetSU)
IsReachable - Checks if SU is reachable from TargetSU.
RegUnit2SUnitsMap Defs
Defs, Uses - Remember where defs and uses of each register are as we iterate upward through the instr...
UndefValue * UnknownValue
For an unanalyzable memory access, this Value is used in maps.
VReg2SUnitMultiMap CurrentVRegDefs
Tracks the last instruction(s) in this region defining each virtual register.
MachineBasicBlock::iterator begin() const
Returns an iterator to the top of the current scheduling region.
void buildSchedGraph(AAResults *AA, RegPressureTracker *RPTracker=nullptr, PressureDiffs *PDiffs=nullptr, LiveIntervals *LIS=nullptr, bool TrackLaneMasks=false)
Builds SUnits for the current region.
SUnit * getSUnit(MachineInstr *MI) const
Returns an existing SUnit for this MI, or nullptr.
TargetSchedModel SchedModel
TargetSchedModel provides an interface to the machine model.
virtual void exitRegion()
Called when the scheduler has finished scheduling the current region.
virtual void schedule()=0
Orders nodes according to selected style.
bool canAddEdge(SUnit *SuccSU, SUnit *PredSU)
True if an edge can be added from PredSU to SuccSU without creating a cycle.
void insertBarrierChain(Value2SUsMap &map)
Inserts a barrier chain in a huge region, far below current SU.
const MachineLoopInfo * MLI
bool RemoveKillFlags
True if the DAG builder should remove kill flags (in preparation for rescheduling).
std::optional< BatchAAResults > AAForDep
MachineBasicBlock::iterator RegionBegin
The beginning of the range to be scheduled.
void addSchedBarrierDeps()
Adds dependencies from instructions in the current list of instructions being scheduled to scheduling...
virtual void enterRegion(MachineBasicBlock *bb, MachineBasicBlock::iterator begin, MachineBasicBlock::iterator end, unsigned regioninstrs)
Initialize the DAG and common scheduler state for a new scheduling region.
void dump() const override
void addChainDependency(SUnit *SUa, SUnit *SUb, unsigned Latency=0)
Adds a chain edge between SUa and SUb, but only if both AAResults and Target fail to deny the depende...
unsigned NumRegionInstrs
Instructions in this region (distance(RegionBegin, RegionEnd)).
const MachineFrameInfo & MFI
virtual bool doMBBSchedRegionsTopDown() const
If this method returns true, handling of the scheduling regions themselves (in case of a scheduling b...
bool deadDefHasNoUse(const MachineOperand &MO)
Returns true if the def register in MO has no uses.
std::string getGraphNodeLabel(const SUnit *SU) const override
Returns a label for a DAG node that points to an instruction.
void setDumpDirection(DumpDirection D)
This class can compute a topological ordering for SUnits and provides methods for dynamically updatin...
Definition: ScheduleDAG.h:720
bool IsReachable(const SUnit *SU, const SUnit *TargetSU)
Checks if SU is reachable from TargetSU.
std::vector< SUnit > SUnits
The scheduling units.
Definition: ScheduleDAG.h:579
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1196
Provide an instruction scheduling machine model to CodeGen passes.
bool hasInstrSchedModel() const
Return true if this machine model includes an instruction-level scheduling model.
const MCSchedClassDesc * resolveSchedClass(const MachineInstr *MI) const
Return the MCSchedClassDesc for this instruction.
'undef' values are things that do not have specified contents.
Definition: Constants.h:1412
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
#define N
Summarize the scheduling resources required for an instruction of a particular scheduling class.
Definition: MCSchedule.h:121
Record a physical register access.
unsigned getSparseSetIndex() const
PhysRegSUOper(SUnit *su, int op, unsigned R)
UnderlyingObject(ValueType V, bool MayAlias)
ValueType getValue() const
Mapping from virtual register to SUnit including an operand index.
VReg2SUnitOperIdx(unsigned VReg, LaneBitmask LaneMask, unsigned OperandIndex, SUnit *SU)
An individual mapping from virtual register number to SUnit.
LaneBitmask LaneMask
unsigned getSparseSetIndex() const
VReg2SUnit(unsigned VReg, LaneBitmask LaneMask, SUnit *SU)