/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h
Line | Count | Source (jump to first uncovered line) |
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" |
19 | | #include "llvm/ADT/PointerIntPair.h" |
20 | | #include "llvm/ADT/STLExtras.h" |
21 | | #include "llvm/ADT/SmallVector.h" |
22 | | #include "llvm/ADT/SparseMultiSet.h" |
23 | | #include "llvm/ADT/SparseSet.h" |
24 | | #include "llvm/CodeGen/LivePhysRegs.h" |
25 | | #include "llvm/CodeGen/MachineBasicBlock.h" |
26 | | #include "llvm/CodeGen/ScheduleDAG.h" |
27 | | #include "llvm/CodeGen/TargetSchedule.h" |
28 | | #include "llvm/MC/LaneBitmask.h" |
29 | | #include "llvm/Target/TargetRegisterInfo.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; |
54 | | LaneBitmask LaneMask; |
55 | | SUnit *SU; |
56 | | |
57 | | VReg2SUnit(unsigned VReg, LaneBitmask LaneMask, SUnit *SU) |
58 | 20.8M | : VirtReg(VReg), LaneMask(LaneMask), SU(SU) {} |
59 | | |
60 | 63.6M | unsigned getSparseSetIndex() const { |
61 | 63.6M | return TargetRegisterInfo::virtReg2Index(VirtReg); |
62 | 63.6M | } |
63 | | }; |
64 | | |
65 | | /// Mapping from virtual register to SUnit including an operand index. |
66 | | struct VReg2SUnitOperIdx : public VReg2SUnit { |
67 | | unsigned OperandIndex; |
68 | | |
69 | | VReg2SUnitOperIdx(unsigned VReg, LaneBitmask LaneMask, |
70 | | unsigned OperandIndex, SUnit *SU) |
71 | 15.7M | : 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 { |
77 | | SUnit *SU; |
78 | | int OpIdx; |
79 | | unsigned Reg; |
80 | | |
81 | 17.9M | PhysRegSUOper(SUnit *su, int op, unsigned R): SU(su), OpIdx(op), Reg(R) {} |
82 | | |
83 | 121M | 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 = |
90 | | SparseMultiSet<PhysRegSUOper, identity<unsigned>, uint16_t>; |
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. |
96 | | using VReg2SUnitMap = SparseSet<VReg2SUnit, VirtReg2IndexFunctor>; |
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. |
101 | | using VReg2SUnitMultiMap = SparseMultiSet<VReg2SUnit, VirtReg2IndexFunctor>; |
102 | | |
103 | | using VReg2SUnitOperIdxMultiMap = |
104 | | SparseMultiSet<VReg2SUnitOperIdx, VirtReg2IndexFunctor>; |
105 | | |
106 | | using ValueType = PointerUnion<const Value *, const PseudoSourceValue *>; |
107 | | |
108 | | struct UnderlyingObject : PointerIntPair<ValueType, 1, bool> { |
109 | | UnderlyingObject(ValueType V, bool MayAlias) |
110 | 1.58M | : PointerIntPair<ValueType, 1, bool>(V, MayAlias) {} |
111 | | |
112 | 2.65M | ValueType getValue() const { return getPointer(); } |
113 | 2.65M | bool mayAlias() const { return getInt(); } |
114 | | }; |
115 | | |
116 | | using UnderlyingObjectsVector = SmallVector<UnderlyingObject, 4>; |
117 | | |
118 | | /// A ScheduleDAG for scheduling lists of MachineInstr. |
119 | | class ScheduleDAGInstrs : public ScheduleDAG { |
120 | | protected: |
121 | | const MachineLoopInfo *MLI; |
122 | | const MachineFrameInfo &MFI; |
123 | | |
124 | | /// TargetSchedModel provides an interface to the machine model. |
125 | | TargetSchedModel SchedModel; |
126 | | |
127 | | /// True if the DAG builder should remove kill flags (in preparation for |
128 | | /// rescheduling). |
129 | | bool RemoveKillFlags; |
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 |
145 | | MachineBasicBlock *BB; |
146 | | |
147 | | /// The beginning of the range to be scheduled. |
148 | | MachineBasicBlock::iterator RegionBegin; |
149 | | |
150 | | /// The end of the range to be scheduled. |
151 | | MachineBasicBlock::iterator RegionEnd; |
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. |
158 | | DenseMap<MachineInstr*, SUnit*> MISUnitMap; |
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. |
167 | | Reg2SUnitsMap Defs; |
168 | | Reg2SUnitsMap Uses; |
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. |
173 | | VReg2SUnitMultiMap CurrentVRegDefs; |
174 | | /// Tracks the last instructions in this region using each virtual register. |
175 | | VReg2SUnitOperIdxMultiMap CurrentVRegUses; |
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 | 1.83M | void addChainDependencies(SUnit *SU, SUList &SUs, unsigned Latency) { |
211 | 1.83M | for (SUnit *Entry : SUs) |
212 | 26.6M | addChainDependency(SU, Entry, Latency); |
213 | 1.83M | } |
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. |
236 | | UndefValue *UnknownValue; |
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. |
243 | | DbgValueVector DbgValues; |
244 | | MachineInstr *FirstDbgValue = nullptr; |
245 | | |
246 | | /// Set of live physical registers for updating kill flags. |
247 | | LivePhysRegs LiveRegs; |
248 | | |
249 | | public: |
250 | | explicit ScheduleDAGInstrs(MachineFunction &mf, |
251 | | const MachineLoopInfo *mli, |
252 | | bool RemoveKillFlags = false); |
253 | | |
254 | 600k | ~ScheduleDAGInstrs() override = default; |
255 | | |
256 | | /// Gets the machine model for instruction scheduling. |
257 | 4.08M | const TargetSchedModel *getSchedModel() const { return &SchedModel; } |
258 | | |
259 | | /// Resolves and cache a resolved scheduling class for an SUnit. |
260 | 72.0M | const MCSchedClassDesc *getSchedClass(SUnit *SU) const { |
261 | 72.0M | if (!SU->SchedClass && 72.0M SchedModel.hasInstrSchedModel()16.7M ) |
262 | 16.1M | SU->SchedClass = SchedModel.resolveSchedClass(SU->getInstr()); |
263 | 72.0M | return SU->SchedClass; |
264 | 72.0M | } |
265 | | |
266 | | /// Returns an iterator to the top of the current scheduling region. |
267 | 8.21M | MachineBasicBlock::iterator begin() const { return RegionBegin; } |
268 | | |
269 | | /// Returns an iterator to the bottom of the current scheduling region. |
270 | 12.2M | 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 | 0 | 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, |
294 | | MachineBasicBlock::iterator begin, |
295 | | MachineBasicBlock::iterator end, |
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 | 548k | 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. |
364 | 17.1M | inline SUnit *ScheduleDAGInstrs::newSUnit(MachineInstr *MI) { |
365 | | #ifndef NDEBUG |
366 | | const SUnit *Addr = SUnits.empty() ? nullptr : &SUnits[0]; |
367 | | #endif |
368 | | SUnits.emplace_back(MI, (unsigned)SUnits.size()); |
369 | 17.1M | assert((Addr == nullptr || Addr == &SUnits[0]) && |
370 | 17.1M | "SUnits std::vector reallocated on the fly!"); |
371 | 17.1M | return &SUnits.back(); |
372 | 17.1M | } |
373 | | |
374 | | /// Returns an existing SUnit for this MI, or nullptr. |
375 | 285k | inline SUnit *ScheduleDAGInstrs::getSUnit(MachineInstr *MI) const { |
376 | 285k | DenseMap<MachineInstr*, SUnit*>::const_iterator I = MISUnitMap.find(MI); |
377 | 285k | if (I == MISUnitMap.end()) |
378 | 44.5k | return nullptr; |
379 | 241k | return I->second; |
380 | 285k | } |
381 | | |
382 | | } // end namespace llvm |
383 | | |
384 | | #endif // LLVM_CODEGEN_SCHEDULEDAGINSTRS_H |