LLVM  6.0.0svn
ScheduleDAGInstrs.h
Go to the documentation of this file.
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"
20 #include "llvm/ADT/STLExtras.h"
21 #include "llvm/ADT/SmallVector.h"
23 #include "llvm/ADT/SparseSet.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;
56 
57  VReg2SUnit(unsigned VReg, LaneBitmask LaneMask, SUnit *SU)
58  : VirtReg(VReg), LaneMask(LaneMask), SU(SU) {}
59 
60  unsigned getSparseSetIndex() const {
61  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 
70  unsigned OperandIndex, SUnit *SU)
71  : 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 {
78  int OpIdx;
79  unsigned Reg;
80 
81  PhysRegSUOper(SUnit *su, int op, unsigned R): SU(su), OpIdx(op), Reg(R) {}
82 
83  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 =
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.
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.
102 
105 
107 
108  struct UnderlyingObject : PointerIntPair<ValueType, 1, bool> {
110  : PointerIntPair<ValueType, 1, bool>(V, MayAlias) {}
111 
112  ValueType getValue() const { return getPointer(); }
113  bool mayAlias() const { return getInt(); }
114  };
115 
117 
118  /// A ScheduleDAG for scheduling lists of MachineInstr.
120  protected:
123 
124  /// TargetSchedModel provides an interface to the machine model.
126 
127  /// True if the DAG builder should remove kill flags (in preparation for
128  /// rescheduling).
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
146 
147  /// The beginning of the range to be scheduled.
149 
150  /// The end of the range to be scheduled.
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.
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.
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.
174  /// Tracks the last instructions in this region using each virtual register.
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  /// \brief 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  /// \brief 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  for (SUnit *Entry : SUs)
212  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.
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.
244  MachineInstr *FirstDbgValue = nullptr;
245 
246  /// Set of live physical registers for updating kill flags.
248 
249  public:
250  explicit ScheduleDAGInstrs(MachineFunction &mf,
251  const MachineLoopInfo *mli,
252  bool RemoveKillFlags = false);
253 
254  ~ScheduleDAGInstrs() override = default;
255 
256  /// Gets the machine model for instruction scheduling.
257  const TargetSchedModel *getSchedModel() const { return &SchedModel; }
258 
259  /// Resolves and cache a resolved scheduling class for an SUnit.
261  if (!SU->SchedClass && SchedModel.hasInstrSchedModel())
262  SU->SchedClass = SchedModel.resolveSchedClass(SU->getInstr());
263  return SU->SchedClass;
264  }
265 
266  /// Returns an iterator to the top of the current scheduling region.
267  MachineBasicBlock::iterator begin() const { return RegionBegin; }
268 
269  /// Returns an iterator to the bottom of the current scheduling region.
270  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  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  /// \brief 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,
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  /// \brief 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  virtual void finalizeSchedule() {}
329 
330  void dumpNode(const SUnit *SU) const override;
331 
332  /// Returns a label for a DAG node that points to an instruction.
333  std::string getGraphNodeLabel(const SUnit *SU) const override;
334 
335  /// Returns a label for the region of code covered by the DAG.
336  std::string getDAGName() const override;
337 
338  /// Fixes register kill flags that scheduling has made invalid.
339  void fixupKills(MachineBasicBlock &MBB);
340 
341  protected:
342  void initSUnits();
343  void addPhysRegDataDeps(SUnit *SU, unsigned OperIdx);
344  void addPhysRegDeps(SUnit *SU, unsigned OperIdx);
345  void addVRegDefDeps(SUnit *SU, unsigned OperIdx);
346  void addVRegUseDeps(SUnit *SU, unsigned OperIdx);
347 
348  /// Initializes register live-range state for updating kills.
349  /// PostRA helper for rewriting kill flags.
350  void startBlockForKills(MachineBasicBlock *BB);
351 
352  /// Toggles a register operand kill flag.
353  ///
354  /// Other adjustments may be made to the instruction if necessary. Return
355  /// true if the operand has been deleted, false if not.
356  void toggleKillFlag(MachineInstr &MI, MachineOperand &MO);
357 
358  /// Returns a mask for which lanes get read/written by the given (register)
359  /// machine operand.
360  LaneBitmask getLaneMaskForMO(const MachineOperand &MO) const;
361  };
362 
363  /// Creates a new SUnit and return a ptr to it.
365 #ifndef NDEBUG
366  const SUnit *Addr = SUnits.empty() ? nullptr : &SUnits[0];
367 #endif
368  SUnits.emplace_back(MI, (unsigned)SUnits.size());
369  assert((Addr == nullptr || Addr == &SUnits[0]) &&
370  "SUnits std::vector reallocated on the fly!");
371  return &SUnits.back();
372  }
373 
374  /// Returns an existing SUnit for this MI, or nullptr.
377  if (I == MISUnitMap.end())
378  return nullptr;
379  return I->second;
380  }
381 
382 } // end namespace llvm
383 
384 #endif // LLVM_CODEGEN_SCHEDULEDAGINSTRS_H
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:244
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:235
static unsigned virtReg2Index(unsigned Reg)
Convert a virtual register number to a 0-based index.
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
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
TargetSchedModel SchedModel
TargetSchedModel provides an interface to the machine model.
#define op(i)
unsigned NumRegionInstrs
Instructions in this region (distance(RegionBegin, RegionEnd)).
The two locations may or may not alias. This is the least precise result.
Definition: AliasAnalysis.h:87
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:1247
An individual mapping from virtual register number to SUnit.
static unsigned getInt(StringRef R)
Get an unsigned integer, including error checks.
Definition: DataLayout.cpp:209
Reg
All possible values of the reg field in the ModR/M byte.
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
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.
MachineInstr * getInstr() const
Returns the representative MachineInstr for this SUnit.
Definition: ScheduleDAG.h:378
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:101
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:258
const MachineFrameInfo & MFI
This file implements the LivePhysRegs utility for tracking liveness of physical registers.
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:864
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:59
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:49
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
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:247
A discriminated union of two pointer types, with the discriminator in the low bit of the pointer...
Definition: PointerUnion.h:87