LLVM 22.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"
30#include <cassert>
31#include <cstdint>
32#include <list>
33#include <string>
34#include <utility>
35#include <vector>
36
37namespace llvm {
38
39 class AAResults;
40 class LiveIntervals;
41 class MachineFrameInfo;
42 class MachineFunction;
43 class MachineInstr;
44 class MachineLoopInfo;
45 class MachineOperand;
46 struct MCSchedClassDesc;
47 class PressureDiffs;
50 class UndefValue;
51 class Value;
52
53 /// An individual mapping from virtual register number to SUnit.
54 struct VReg2SUnit {
58
61
62 unsigned getSparseSetIndex() const {
63 return VirtReg.virtRegIndex();
64 }
65 };
66
67 /// Mapping from virtual register to SUnit including an operand index.
75
76 /// Record a physical register access.
77 /// For non-data-dependent uses, OpIdx == -1.
80 int OpIdx;
81 unsigned RegUnit;
82
83 PhysRegSUOper(SUnit *su, int op, unsigned R)
84 : SU(su), OpIdx(op), RegUnit(R) {}
85
86 unsigned getSparseSetIndex() const { return RegUnit; }
87 };
88
89 /// Use a SparseMultiSet to track physical registers. Storage is only
90 /// allocated once for the pass. It can be cleared in constant time and reused
91 /// without any frees.
94
95 /// Track local uses of virtual registers. These uses are gathered by the DAG
96 /// builder and may be consulted by the scheduler to avoid iterating an entire
97 /// vreg use list.
100
103
105
106 struct UnderlyingObject : PointerIntPair<ValueType, 1, bool> {
107 UnderlyingObject(ValueType V, bool MayAlias)
108 : PointerIntPair<ValueType, 1, bool>(V, MayAlias) {}
109
110 ValueType getValue() const { return getPointer(); }
111 bool mayAlias() const { return getInt(); }
112 };
113
115
116 /// A ScheduleDAG for scheduling lists of MachineInstr.
118 protected:
119 const MachineLoopInfo *MLI = nullptr;
121
122 /// TargetSchedModel provides an interface to the machine model.
124
125 /// True if the DAG builder should remove kill flags (in preparation for
126 /// rescheduling).
128
129 /// True if regions with a single MI should be scheduled.
131
132 /// The standard DAG builder does not normally include terminators as DAG
133 /// nodes because it does not create the necessary dependencies to prevent
134 /// reordering. A specialized scheduler can override
135 /// TargetInstrInfo::isSchedulingBoundary then enable this flag to indicate
136 /// it has taken responsibility for scheduling the terminator correctly.
138
139 /// Whether lane masks should get tracked.
140 bool TrackLaneMasks = false;
141
142 // State specific to the current scheduling region.
143 // ------------------------------------------------
144
145 /// The block in which to insert instructions
147
148 /// The beginning of the range to be scheduled.
150
151 /// The end of the range to be scheduled.
153
154 /// Instructions in this region (distance(RegionBegin, RegionEnd)).
155 unsigned NumRegionInstrs = 0;
156
157 /// After calling BuildSchedGraph, each machine instruction in the current
158 /// scheduling region is mapped to an SUnit.
160
161 // State internal to DAG building.
162 // -------------------------------
163
164 /// Defs, Uses - Remember where defs and uses of each register are as we
165 /// iterate upward through the instructions. This is allocated here instead
166 /// of inside BuildSchedGraph to avoid the need for it to be initialized and
167 /// destructed for each block.
170
171 /// Tracks the last instruction(s) in this region defining each virtual
172 /// register. There may be multiple current definitions for a register with
173 /// disjunct lanemasks.
175 /// Tracks the last instructions in this region using each virtual register.
177
178 mutable std::optional<BatchAAResults> AAForDep;
179
180 /// Remember a generic side-effecting instruction as we proceed.
181 /// No other SU ever gets scheduled around it (except in the special
182 /// case of a huge region that gets reduced).
183 SUnit *BarrierChain = nullptr;
184
186
187 public:
188 /// A list of SUnits, used in Value2SUsMap, during DAG construction.
189 /// Note: to gain speed it might be worth investigating an optimized
190 /// implementation of this data structure, such as a singly linked list
191 /// with a memory pool (SmallVector was tried but slow and SparseSet is not
192 /// applicable).
193 using SUList = std::list<SUnit *>;
194
195 /// The direction that should be used to dump the scheduled Sequence.
202
204
205 protected:
207
208 /// A map from ValueType to SUList, used during DAG construction, as
209 /// a means of remembering which SUs depend on which memory locations.
210 class Value2SUsMap;
211
212 /// Returns a (possibly null) pointer to the current BatchAAResults.
214 if (AAForDep.has_value())
215 return &AAForDep.value();
216 return nullptr;
217 }
218
219 /// Reduces maps in FIFO order, by N SUs. This is better than turning
220 /// every Nth memory SU into BarrierChain in buildSchedGraph(), since
221 /// it avoids unnecessary edges between seen SUs above the new BarrierChain,
222 /// and those below it.
223 void reduceHugeMemNodeMaps(Value2SUsMap &stores,
224 Value2SUsMap &loads, unsigned N);
225
226 /// Adds a chain edge between SUa and SUb, but only if both
227 /// AAResults and Target fail to deny the dependency.
228 void addChainDependency(SUnit *SUa, SUnit *SUb,
229 unsigned Latency = 0);
230
231 /// Adds dependencies as needed from all SUs in list to SU.
232 void addChainDependencies(SUnit *SU, SUList &SUs, unsigned Latency) {
233 for (SUnit *Entry : SUs)
234 addChainDependency(SU, Entry, Latency);
235 }
236
237 /// Adds dependencies as needed from all SUs in map, to SU.
238 void addChainDependencies(SUnit *SU, Value2SUsMap &Val2SUsMap);
239
240 /// Adds dependencies as needed to SU, from all SUs mapped to V.
241 void addChainDependencies(SUnit *SU, Value2SUsMap &Val2SUsMap,
242 ValueType V);
243
244 /// Adds barrier chain edges from all SUs in map, and then clear the map.
245 /// This is equivalent to insertBarrierChain(), but optimized for the common
246 /// case where the new BarrierChain (a global memory object) has a higher
247 /// NodeNum than all SUs in map. It is assumed BarrierChain has been set
248 /// before calling this.
249 void addBarrierChain(Value2SUsMap &map);
250
251 /// Inserts a barrier chain in a huge region, far below current SU.
252 /// Adds barrier chain edges from all SUs in map with higher NodeNums than
253 /// this new BarrierChain, and remove them from map. It is assumed
254 /// BarrierChain has been set before calling this.
255 void insertBarrierChain(Value2SUsMap &map);
256
257 /// For an unanalyzable memory access, this Value is used in maps.
259
260
261 /// Topo - A topological ordering for SUnits which permits fast IsReachable
262 /// and similar queries.
264
266 std::vector<std::pair<MachineInstr *, MachineInstr *>>;
267 /// Remember instruction that precedes DBG_VALUE.
268 /// These are generated by buildSchedGraph but persist so they can be
269 /// referenced when emitting the final schedule.
272
273 /// Set of live physical registers for updating kill flags.
275
276 public:
278 const MachineLoopInfo *mli,
279 bool RemoveKillFlags = false);
280
281 ~ScheduleDAGInstrs() override = default;
282
283 /// Gets the machine model for instruction scheduling.
284 const TargetSchedModel *getSchedModel() const { return &SchedModel; }
285
286 /// Resolves and cache a resolved scheduling class for an SUnit.
288 if (!SU->SchedClass && SchedModel.hasInstrSchedModel())
289 SU->SchedClass = SchedModel.resolveSchedClass(SU->getInstr());
290 return SU->SchedClass;
291 }
292
293 /// IsReachable - Checks if SU is reachable from TargetSU.
294 bool IsReachable(SUnit *SU, SUnit *TargetSU) {
295 return Topo.IsReachable(SU, TargetSU);
296 }
297
298 /// Whether regions with a single MI should be scheduled.
302
303 /// Returns an iterator to the top of the current scheduling region.
305
306 /// Returns an iterator to the bottom of the current scheduling region.
308
309 /// Creates a new SUnit and return a ptr to it.
310 SUnit *newSUnit(MachineInstr *MI);
311
312 /// Returns an existing SUnit for this MI, or nullptr.
313 SUnit *getSUnit(MachineInstr *MI) const;
314
315 /// If this method returns true, handling of the scheduling regions
316 /// themselves (in case of a scheduling boundary in MBB) will be done
317 /// beginning with the topmost region of MBB.
318 virtual bool doMBBSchedRegionsTopDown() const { return false; }
319
320 /// Prepares to perform scheduling in the given block.
321 virtual void startBlock(MachineBasicBlock *BB);
322
323 /// Cleans up after scheduling in the given block.
324 virtual void finishBlock();
325
326 /// Initialize the DAG and common scheduler state for a new
327 /// scheduling region. This does not actually create the DAG, only clears
328 /// it. The scheduling driver may call BuildSchedGraph multiple times per
329 /// scheduling region.
330 virtual void enterRegion(MachineBasicBlock *bb,
333 unsigned regioninstrs);
334
335 /// Called when the scheduler has finished scheduling the current region.
336 virtual void exitRegion();
337
338 /// Builds SUnits for the current region.
339 /// If \p RPTracker is non-null, compute register pressure as a side effect.
340 /// The DAG builder is an efficient place to do it because it already visits
341 /// operands.
342 void buildSchedGraph(AAResults *AA,
343 RegPressureTracker *RPTracker = nullptr,
344 PressureDiffs *PDiffs = nullptr,
345 LiveIntervals *LIS = nullptr,
346 bool TrackLaneMasks = false);
347
348 /// Adds dependencies from instructions in the current list of
349 /// instructions being scheduled to scheduling barrier. We want to make sure
350 /// instructions which define registers that are either used by the
351 /// terminator or are live-out are properly scheduled. This is especially
352 /// important when the definition latency of the return value(s) are too
353 /// high to be hidden by the branch or when the liveout registers used by
354 /// instructions in the fallthrough block.
355 void addSchedBarrierDeps();
356
357 /// Orders nodes according to selected style.
358 ///
359 /// Typically, a scheduling algorithm will implement schedule() without
360 /// overriding enterRegion() or exitRegion().
361 virtual void schedule() = 0;
362
363 /// Allow targets to perform final scheduling actions at the level of the
364 /// whole MachineFunction. By default does nothing.
365 virtual void finalizeSchedule() {}
366
367 void dumpNode(const SUnit &SU) const override;
368 void dump() const override;
369
370 /// Returns a label for a DAG node that points to an instruction.
371 std::string getGraphNodeLabel(const SUnit *SU) const override;
372
373 /// Returns a label for the region of code covered by the DAG.
374 std::string getDAGName() const override;
375
376 /// Fixes register kill flags that scheduling has made invalid.
377 void fixupKills(MachineBasicBlock &MBB);
378
379 /// True if an edge can be added from PredSU to SuccSU without creating
380 /// a cycle.
381 bool canAddEdge(SUnit *SuccSU, SUnit *PredSU);
382
383 /// Add a DAG edge to the given SU with the given predecessor
384 /// dependence data.
385 ///
386 /// \returns true if the edge may be added without creating a cycle OR if an
387 /// equivalent edge already existed (false indicates failure).
388 bool addEdge(SUnit *SuccSU, const SDep &PredDep);
389
390 /// Returns the array of the clusters.
392
393 /// Get the specific cluster, return nullptr for InvalidClusterId.
394 ClusterInfo *getCluster(unsigned Idx) {
395 return Idx != InvalidClusterId ? &Clusters[Idx] : nullptr;
396 }
397
398 protected:
399 void initSUnits();
400 void addPhysRegDataDeps(SUnit *SU, unsigned OperIdx);
401 void addPhysRegDeps(SUnit *SU, unsigned OperIdx);
402 void addVRegDefDeps(SUnit *SU, unsigned OperIdx);
403 void addVRegUseDeps(SUnit *SU, unsigned OperIdx);
404
405 /// Returns a mask for which lanes get read/written by the given (register)
406 /// machine operand.
407 LaneBitmask getLaneMaskForMO(const MachineOperand &MO) const;
408
409 /// Returns true if the def register in \p MO has no uses.
410 bool deadDefHasNoUse(const MachineOperand &MO);
411 };
412
413 /// Creates a new SUnit and return a ptr to it.
415#ifndef NDEBUG
416 const SUnit *Addr = SUnits.empty() ? nullptr : &SUnits[0];
417#endif
418 SUnits.emplace_back(MI, (unsigned)SUnits.size());
419 assert((Addr == nullptr || Addr == &SUnits[0]) &&
420 "SUnits std::vector reallocated on the fly!");
421 return &SUnits.back();
422 }
423
424 /// Returns an existing SUnit for this MI, or nullptr.
426 return MISUnitMap.lookup(MI);
427 }
428
429} // end namespace llvm
430
431#endif // LLVM_CODEGEN_SCHEDULEDAGINSTRS_H
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
MachineBasicBlock & MBB
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
#define LLVM_ABI
Definition Compiler.h:213
This file defines the DenseMap class.
#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.
static void addEdge(SmallVectorImpl< LazyCallGraph::Edge > &Edges, DenseMap< LazyCallGraph::Node *, int > &EdgeIndexMap, LazyCallGraph::Node &N, LazyCallGraph::Edge::Kind EK)
A set of register units.
This file defines the PointerIntPair class.
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.
MachineInstrBundleIterator< MachineInstr > iterator
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted.
Representation of each machine instruction.
MachineOperand class - Representation of each machine instruction operand.
A discriminated union of two or more pointer types, with the discriminator in the low bit of the poin...
Array of PressureDiffs.
Special value supplied for machine level alias analysis.
Track the current register pressure at some position in the instruction stream, and remember the high...
Wrapper class representing virtual and physical registers.
Definition Register.h:19
Scheduling dependency.
Definition ScheduleDAG.h:51
Scheduling unit. This is a node in the scheduling DAG.
const MCSchedClassDesc * SchedClass
nullptr or resolved SchedClass.
MachineInstr * getInstr() const
Returns the representative MachineInstr for this SUnit.
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...
SmallVector< ClusterInfo > & getClusters()
Returns the array of the clusters.
MachineBasicBlock::iterator end() const
Returns an iterator to the bottom of the current scheduling region.
MachineBasicBlock * BB
The block in which to insert instructions.
bool CanHandleTerminators
The standard DAG builder does not normally include terminators as DAG nodes because it does not creat...
bool ScheduleSingleMIRegions
True if regions with a single MI should be scheduled.
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.
~ScheduleDAGInstrs() override=default
ScheduleDAGInstrs(MachineFunction &mf, const MachineLoopInfo *mli, bool RemoveKillFlags=false)
bool shouldScheduleSingleMIRegions() const
Whether regions with a single MI should be scheduled.
DbgValueVector DbgValues
Remember instruction that precedes DBG_VALUE.
std::vector< std::pair< MachineInstr *, MachineInstr * > > DbgValueVector
SUnit * newSUnit(MachineInstr *MI)
Creates a new SUnit and return a ptr to it.
virtual void finalizeSchedule()
Allow targets to perform final scheduling actions at the level of the whole MachineFunction.
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.
ClusterInfo * getCluster(unsigned Idx)
Get the specific cluster, return nullptr for InvalidClusterId.
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.
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 schedule()=0
Orders nodes according to selected style.
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 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
SmallVector< ClusterInfo > Clusters
virtual bool doMBBSchedRegionsTopDown() const
If this method returns true, handling of the scheduling regions themselves (in case of a scheduling b...
void setDumpDirection(DumpDirection D)
This class can compute a topological ordering for SUnits and provides methods for dynamically updatin...
std::vector< SUnit > SUnits
The scheduling units.
ScheduleDAG(const ScheduleDAG &)=delete
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Fast multiset implementation for objects that can be identified by small unsigned keys.
Provide an instruction scheduling machine model to CodeGen passes.
'undef' values are things that do not have specified contents.
Definition Constants.h:1420
LLVM Value Representation.
Definition Value.h:75
Abstract Attribute helper functions.
Definition Attributor.h:165
This is an optimization pass for GlobalISel generic memory operations.
SparseMultiSet< VReg2SUnitOperIdx, Register, VirtReg2IndexFunctor > VReg2SUnitOperIdxMultiMap
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
SparseMultiSet< VReg2SUnit, Register, VirtReg2IndexFunctor > VReg2SUnitMultiMap
Track local uses of virtual registers.
constexpr unsigned InvalidClusterId
SmallVector< UnderlyingObject, 4 > UnderlyingObjectsVector
SparseMultiSet< PhysRegSUOper, unsigned, identity_cxx20, uint16_t > RegUnit2SUnitsMap
Use a SparseMultiSet to track physical registers.
SmallPtrSet< SUnit *, 8 > ClusterInfo
Keep record of which SUnit are in the same cluster group.
PointerUnion< const Value *, const PseudoSourceValue * > ValueType
#define N
Summarize the scheduling resources required for an instruction of a particular scheduling class.
Definition MCSchedule.h:123
unsigned getSparseSetIndex() const
PhysRegSUOper(SUnit *su, int op, unsigned R)
UnderlyingObject(ValueType V, bool MayAlias)
ValueType getValue() const
VReg2SUnitOperIdx(Register VReg, LaneBitmask LaneMask, unsigned OperandIndex, SUnit *SU)
VReg2SUnit(Register VReg, LaneBitmask LaneMask, SUnit *SU)
unsigned getSparseSetIndex() const