LLVM  10.0.0svn
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"
19 #include "llvm/ADT/STLExtras.h"
20 #include "llvm/ADT/SmallVector.h"
22 #include "llvm/ADT/SparseSet.h"
28 #include "llvm/MC/LaneBitmask.h"
29 #include <cassert>
30 #include <cstdint>
31 #include <list>
32 #include <utility>
33 #include <vector>
34 
35 namespace llvm {
36 
37  class LiveIntervals;
38  class MachineFrameInfo;
39  class MachineFunction;
40  class MachineInstr;
41  class MachineLoopInfo;
42  class MachineOperand;
43  struct MCSchedClassDesc;
44  class PressureDiffs;
45  class PseudoSourceValue;
46  class RegPressureTracker;
47  class UndefValue;
48  class Value;
49 
50  /// An individual mapping from virtual register number to SUnit.
51  struct VReg2SUnit {
52  unsigned VirtReg;
55 
56  VReg2SUnit(unsigned VReg, LaneBitmask LaneMask, SUnit *SU)
57  : VirtReg(VReg), LaneMask(LaneMask), SU(SU) {}
58 
59  unsigned getSparseSetIndex() const {
60  return TargetRegisterInfo::virtReg2Index(VirtReg);
61  }
62  };
63 
64  /// Mapping from virtual register to SUnit including an operand index.
65  struct VReg2SUnitOperIdx : public VReg2SUnit {
66  unsigned OperandIndex;
67 
69  unsigned OperandIndex, SUnit *SU)
70  : VReg2SUnit(VReg, LaneMask, SU), OperandIndex(OperandIndex) {}
71  };
72 
73  /// Record a physical register access.
74  /// For non-data-dependent uses, OpIdx == -1.
75  struct PhysRegSUOper {
77  int OpIdx;
78  unsigned Reg;
79 
80  PhysRegSUOper(SUnit *su, int op, unsigned R): SU(su), OpIdx(op), Reg(R) {}
81 
82  unsigned getSparseSetIndex() const { return Reg; }
83  };
84 
85  /// Use a SparseMultiSet to track physical registers. Storage is only
86  /// allocated once for the pass. It can be cleared in constant time and reused
87  /// without any frees.
88  using Reg2SUnitsMap =
90 
91  /// Use SparseSet as a SparseMap by relying on the fact that it never
92  /// compares ValueT's, only unsigned keys. This allows the set to be cleared
93  /// between scheduling regions in constant time as long as ValueT does not
94  /// require a destructor.
96 
97  /// Track local uses of virtual registers. These uses are gathered by the DAG
98  /// builder and may be consulted by the scheduler to avoid iterating an entire
99  /// vreg use list.
101 
104 
106 
107  struct UnderlyingObject : PointerIntPair<ValueType, 1, bool> {
109  : PointerIntPair<ValueType, 1, bool>(V, MayAlias) {}
110 
111  ValueType getValue() const { return getPointer(); }
112  bool mayAlias() const { return getInt(); }
113  };
114 
116 
117  /// A ScheduleDAG for scheduling lists of MachineInstr.
119  protected:
122 
123  /// TargetSchedModel provides an interface to the machine model.
125 
126  /// True if the DAG builder should remove kill flags (in preparation for
127  /// rescheduling).
129 
130  /// The standard DAG builder does not normally include terminators as DAG
131  /// nodes because it does not create the necessary dependencies to prevent
132  /// reordering. A specialized scheduler can override
133  /// TargetInstrInfo::isSchedulingBoundary then enable this flag to indicate
134  /// it has taken responsibility for scheduling the terminator correctly.
135  bool CanHandleTerminators = false;
136 
137  /// Whether lane masks should get tracked.
138  bool TrackLaneMasks = false;
139 
140  // State specific to the current scheduling region.
141  // ------------------------------------------------
142 
143  /// The block in which to insert instructions
145 
146  /// The beginning of the range to be scheduled.
148 
149  /// The end of the range to be scheduled.
151 
152  /// Instructions in this region (distance(RegionBegin, RegionEnd)).
153  unsigned NumRegionInstrs;
154 
155  /// After calling BuildSchedGraph, each machine instruction in the current
156  /// scheduling region is mapped to an SUnit.
158 
159  // State internal to DAG building.
160  // -------------------------------
161 
162  /// Defs, Uses - Remember where defs and uses of each register are as we
163  /// iterate upward through the instructions. This is allocated here instead
164  /// of inside BuildSchedGraph to avoid the need for it to be initialized and
165  /// destructed for each block.
168 
169  /// Tracks the last instruction(s) in this region defining each virtual
170  /// register. There may be multiple current definitions for a register with
171  /// disjunct lanemasks.
173  /// Tracks the last instructions in this region using each virtual register.
175 
176  AliasAnalysis *AAForDep = nullptr;
177 
178  /// Remember a generic side-effecting instruction as we proceed.
179  /// No other SU ever gets scheduled around it (except in the special
180  /// case of a huge region that gets reduced).
181  SUnit *BarrierChain = nullptr;
182 
183  public:
184  /// A list of SUnits, used in Value2SUsMap, during DAG construction.
185  /// Note: to gain speed it might be worth investigating an optimized
186  /// implementation of this data structure, such as a singly linked list
187  /// with a memory pool (SmallVector was tried but slow and SparseSet is not
188  /// applicable).
189  using SUList = std::list<SUnit *>;
190 
191  protected:
192  /// A map from ValueType to SUList, used during DAG construction, as
193  /// a means of remembering which SUs depend on which memory locations.
194  class Value2SUsMap;
195 
196  /// Reduces maps in FIFO order, by N SUs. This is better than turning
197  /// every Nth memory SU into BarrierChain in buildSchedGraph(), since
198  /// it avoids unnecessary edges between seen SUs above the new BarrierChain,
199  /// and those below it.
200  void reduceHugeMemNodeMaps(Value2SUsMap &stores,
201  Value2SUsMap &loads, unsigned N);
202 
203  /// Adds a chain edge between SUa and SUb, but only if both
204  /// AliasAnalysis and Target fail to deny the dependency.
205  void addChainDependency(SUnit *SUa, SUnit *SUb,
206  unsigned Latency = 0);
207 
208  /// Adds dependencies as needed from all SUs in list to SU.
209  void addChainDependencies(SUnit *SU, SUList &SUs, unsigned Latency) {
210  for (SUnit *Entry : SUs)
211  addChainDependency(SU, Entry, Latency);
212  }
213 
214  /// Adds dependencies as needed from all SUs in map, to SU.
215  void addChainDependencies(SUnit *SU, Value2SUsMap &Val2SUsMap);
216 
217  /// Adds dependencies as needed to SU, from all SUs mapped to V.
218  void addChainDependencies(SUnit *SU, Value2SUsMap &Val2SUsMap,
219  ValueType V);
220 
221  /// Adds barrier chain edges from all SUs in map, and then clear the map.
222  /// This is equivalent to insertBarrierChain(), but optimized for the common
223  /// case where the new BarrierChain (a global memory object) has a higher
224  /// NodeNum than all SUs in map. It is assumed BarrierChain has been set
225  /// before calling this.
226  void addBarrierChain(Value2SUsMap &map);
227 
228  /// Inserts a barrier chain in a huge region, far below current SU.
229  /// Adds barrier chain edges from all SUs in map with higher NodeNums than
230  /// this new BarrierChain, and remove them from map. It is assumed
231  /// BarrierChain has been set before calling this.
232  void insertBarrierChain(Value2SUsMap &map);
233 
234  /// For an unanalyzable memory access, this Value is used in maps.
236 
237 
238  /// Topo - A topological ordering for SUnits which permits fast IsReachable
239  /// and similar queries.
241 
242  using DbgValueVector =
243  std::vector<std::pair<MachineInstr *, MachineInstr *>>;
244  /// Remember instruction that precedes DBG_VALUE.
245  /// These are generated by buildSchedGraph but persist so they can be
246  /// referenced when emitting the final schedule.
248  MachineInstr *FirstDbgValue = nullptr;
249 
250  /// Set of live physical registers for updating kill flags.
252 
253  public:
254  explicit ScheduleDAGInstrs(MachineFunction &mf,
255  const MachineLoopInfo *mli,
256  bool RemoveKillFlags = false);
257 
258  ~ScheduleDAGInstrs() override = default;
259 
260  /// Gets the machine model for instruction scheduling.
261  const TargetSchedModel *getSchedModel() const { return &SchedModel; }
262 
263  /// Resolves and cache a resolved scheduling class for an SUnit.
265  if (!SU->SchedClass && SchedModel.hasInstrSchedModel())
266  SU->SchedClass = SchedModel.resolveSchedClass(SU->getInstr());
267  return SU->SchedClass;
268  }
269 
270  /// Returns an iterator to the top of the current scheduling region.
271  MachineBasicBlock::iterator begin() const { return RegionBegin; }
272 
273  /// Returns an iterator to the bottom of the current scheduling region.
274  MachineBasicBlock::iterator end() const { return RegionEnd; }
275 
276  /// Creates a new SUnit and return a ptr to it.
277  SUnit *newSUnit(MachineInstr *MI);
278 
279  /// Returns an existing SUnit for this MI, or nullptr.
280  SUnit *getSUnit(MachineInstr *MI) const;
281 
282  /// If this method returns true, handling of the scheduling regions
283  /// themselves (in case of a scheduling boundary in MBB) will be done
284  /// beginning with the topmost region of MBB.
285  virtual bool doMBBSchedRegionsTopDown() const { return false; }
286 
287  /// Prepares to perform scheduling in the given block.
288  virtual void startBlock(MachineBasicBlock *BB);
289 
290  /// Cleans up after scheduling in the given block.
291  virtual void finishBlock();
292 
293  /// Initialize the DAG and common scheduler state for a new
294  /// scheduling region. This does not actually create the DAG, only clears
295  /// it. The scheduling driver may call BuildSchedGraph multiple times per
296  /// scheduling region.
297  virtual void enterRegion(MachineBasicBlock *bb,
300  unsigned regioninstrs);
301 
302  /// Called when the scheduler has finished scheduling the current region.
303  virtual void exitRegion();
304 
305  /// Builds SUnits for the current region.
306  /// If \p RPTracker is non-null, compute register pressure as a side effect.
307  /// The DAG builder is an efficient place to do it because it already visits
308  /// operands.
309  void buildSchedGraph(AliasAnalysis *AA,
310  RegPressureTracker *RPTracker = nullptr,
311  PressureDiffs *PDiffs = nullptr,
312  LiveIntervals *LIS = nullptr,
313  bool TrackLaneMasks = false);
314 
315  /// Adds dependencies from instructions in the current list of
316  /// instructions being scheduled to scheduling barrier. We want to make sure
317  /// instructions which define registers that are either used by the
318  /// terminator or are live-out are properly scheduled. This is especially
319  /// important when the definition latency of the return value(s) are too
320  /// high to be hidden by the branch or when the liveout registers used by
321  /// instructions in the fallthrough block.
322  void addSchedBarrierDeps();
323 
324  /// Orders nodes according to selected style.
325  ///
326  /// Typically, a scheduling algorithm will implement schedule() without
327  /// overriding enterRegion() or exitRegion().
328  virtual void schedule() = 0;
329 
330  /// Allow targets to perform final scheduling actions at the level of the
331  /// whole MachineFunction. By default does nothing.
332  virtual void finalizeSchedule() {}
333 
334  void dumpNode(const SUnit &SU) const override;
335  void dump() const override;
336 
337  /// Returns a label for a DAG node that points to an instruction.
338  std::string getGraphNodeLabel(const SUnit *SU) const override;
339 
340  /// Returns a label for the region of code covered by the DAG.
341  std::string getDAGName() const override;
342 
343  /// Fixes register kill flags that scheduling has made invalid.
344  void fixupKills(MachineBasicBlock &MBB);
345 
346  /// True if an edge can be added from PredSU to SuccSU without creating
347  /// a cycle.
348  bool canAddEdge(SUnit *SuccSU, SUnit *PredSU);
349 
350  /// Add a DAG edge to the given SU with the given predecessor
351  /// dependence data.
352  ///
353  /// \returns true if the edge may be added without creating a cycle OR if an
354  /// equivalent edge already existed (false indicates failure).
355  bool addEdge(SUnit *SuccSU, const SDep &PredDep);
356 
357  protected:
358  void initSUnits();
359  void addPhysRegDataDeps(SUnit *SU, unsigned OperIdx);
360  void addPhysRegDeps(SUnit *SU, unsigned OperIdx);
361  void addVRegDefDeps(SUnit *SU, unsigned OperIdx);
362  void addVRegUseDeps(SUnit *SU, unsigned OperIdx);
363 
364  /// Initializes register live-range state for updating kills.
365  /// PostRA helper for rewriting kill flags.
366  void startBlockForKills(MachineBasicBlock *BB);
367 
368  /// Toggles a register operand kill flag.
369  ///
370  /// Other adjustments may be made to the instruction if necessary. Return
371  /// true if the operand has been deleted, false if not.
372  void toggleKillFlag(MachineInstr &MI, MachineOperand &MO);
373 
374  /// Returns a mask for which lanes get read/written by the given (register)
375  /// machine operand.
376  LaneBitmask getLaneMaskForMO(const MachineOperand &MO) const;
377  };
378 
379  /// Creates a new SUnit and return a ptr to it.
381 #ifndef NDEBUG
382  const SUnit *Addr = SUnits.empty() ? nullptr : &SUnits[0];
383 #endif
384  SUnits.emplace_back(MI, (unsigned)SUnits.size());
385  assert((Addr == nullptr || Addr == &SUnits[0]) &&
386  "SUnits std::vector reallocated on the fly!");
387  return &SUnits.back();
388  }
389 
390  /// Returns an existing SUnit for this MI, or nullptr.
393  if (I == MISUnitMap.end())
394  return nullptr;
395  return I->second;
396  }
397 
398 } // end namespace llvm
399 
400 #endif // LLVM_CODEGEN_SCHEDULEDAGINSTRS_H
ScheduleDAGTopologicalSort Topo
Topo - A topological ordering for SUnits which permits fast IsReachable and similar queries...
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:233
A common definition of LaneBitmask for use in TableGen and CodeGen.
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:224
static unsigned virtReg2Index(unsigned Reg)
Convert a virtual register number to a 0-based index.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Record a physical register access.
LivePhysRegs LiveRegs
Set of live physical registers for updating kill flags.
const MCSchedClassDesc * getSchedClass(SUnit *SU) const
Resolves and cache a resolved scheduling class for an SUnit.
unsigned getSparseSetIndex() const
unsigned Reg
TargetSchedModel SchedModel
TargetSchedModel provides an interface to the machine model.
#define op(i)
unsigned NumRegionInstrs
Instructions in this region (distance(RegionBegin, RegionEnd)).
MachineBasicBlock::iterator RegionEnd
The end of the range to be scheduled.
DenseMap< MachineInstr *, SUnit * > MISUnitMap
After calling BuildSchedGraph, each machine instruction in the current scheduling region is mapped to...
Provide an instruction scheduling machine model to CodeGen passes.
&#39;undef&#39; values are things that do not have specified contents.
Definition: Constants.h:1285
An individual mapping from virtual register number to SUnit.
static unsigned getInt(StringRef R)
Get an unsigned integer, including error checks.
Definition: DataLayout.cpp:214
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted...
DbgValueVector DbgValues
Remember instruction that precedes DBG_VALUE.
bool hasInstrSchedModel() const
Return true if this machine model includes an instruction-level scheduling model. ...
MachineBasicBlock::iterator RegionBegin
The beginning of the range to be scheduled.
MachineBasicBlock::iterator begin() const
Returns an iterator to the top of the current scheduling region.
ValueType getValue() const
static void addEdge(SmallVectorImpl< LazyCallGraph::Edge > &Edges, DenseMap< LazyCallGraph::Node *, int > &EdgeIndexMap, LazyCallGraph::Node &N, LazyCallGraph::Edge::Kind EK)
std::list< SUnit * > SUList
A list of SUnits, used in Value2SUsMap, during DAG construction.
SUnit * getSUnit(MachineInstr *MI) const
Returns an existing SUnit for this MI, or nullptr.
Scheduling dependency.
Definition: ScheduleDAG.h:49
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
MachineInstr * getInstr() const
Returns the representative MachineInstr for this SUnit.
Definition: ScheduleDAG.h:373
Array of PressureDiffs.
PointerIntPair - This class implements a pair of a pointer and small integer.
bool RemoveKillFlags
True if the DAG builder should remove kill flags (in preparation for rescheduling).
Summarize the scheduling resources required for an instruction of a particular scheduling class...
Definition: MCSchedule.h:110
virtual bool doMBBSchedRegionsTopDown() const
If this method returns true, handling of the scheduling regions themselves (in case of a scheduling b...
Track the current register pressure at some position in the instruction stream, and remember the high...
const TargetSchedModel * getSchedModel() const
Gets the machine model for instruction scheduling.
const MCSchedClassDesc * SchedClass
nullptr or resolved SchedClass.
Definition: ScheduleDAG.h:253
const MachineFrameInfo & MFI
This file implements the LivePhysRegs utility for tracking liveness of physical registers.
The two locations may or may not alias. This is the least precise result.
Definition: AliasAnalysis.h:86
PhysRegSUOper(SUnit *su, int op, unsigned R)
UndefValue * UnknownValue
For an unanalyzable memory access, this Value is used in maps.
MachineOperand class - Representation of each machine instruction operand.
LaneBitmask LaneMask
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
VReg2SUnitOperIdx(unsigned VReg, LaneBitmask LaneMask, unsigned OperandIndex, SUnit *SU)
Reg2SUnitsMap Defs
Defs, Uses - Remember where defs and uses of each register are as we iterate upward through the instr...
const MachineLoopInfo * MLI
VReg2SUnitOperIdxMultiMap CurrentVRegUses
Tracks the last instructions in this region using each virtual register.
virtual void finalizeSchedule()
Allow targets to perform final scheduling actions at the level of the whole MachineFunction.
VReg2SUnit(unsigned VReg, LaneBitmask LaneMask, SUnit *SU)
const MCSchedClassDesc * resolveSchedClass(const MachineInstr *MI) const
Return the MCSchedClassDesc for this instruction.
A ScheduleDAG for scheduling lists of MachineInstr.
Representation of each machine instruction.
Definition: MachineInstr.h:64
SparseSet - Fast set implmentation for objects that can be identified by small unsigned keys...
Definition: SparseSet.h:123
A set of physical registers with utility functions to track liveness when walking backward/forward th...
Definition: LivePhysRegs.h:48
void addChainDependencies(SUnit *SU, SUList &SUs, unsigned Latency)
Adds dependencies as needed from all SUs in list to SU.
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
Mapping from virtual register to SUnit including an operand index.
std::vector< std::pair< MachineInstr *, MachineInstr * > > DbgValueVector
MachineBasicBlock::iterator end() const
Returns an iterator to the bottom of the current scheduling region.
SUnit * newSUnit(MachineInstr *MI)
Creates a new SUnit and return a ptr to it.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
UnderlyingObject(ValueType V, bool MayAlias)
MachineBasicBlock * BB
The block in which to insert instructions.
IRTranslator LLVM IR MI
This class can compute a topological ordering for SUnits and provides methods for dynamically updatin...
Definition: ScheduleDAG.h:689
VReg2SUnitMultiMap CurrentVRegDefs
Tracks the last instruction(s) in this region defining each virtual register.
hexagon widen stores
unsigned getSparseSetIndex() const
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:242
A discriminated union of two or more pointer types, with the discriminator in the low bit of the poin...
Definition: PointerUnion.h:163