/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h
Line | Count | Source (jump to first uncovered line) |
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" |
18 | | #include "llvm/ADT/PointerIntPair.h" |
19 | | #include "llvm/ADT/STLExtras.h" |
20 | | #include "llvm/ADT/SmallVector.h" |
21 | | #include "llvm/ADT/SparseMultiSet.h" |
22 | | #include "llvm/ADT/SparseSet.h" |
23 | | #include "llvm/CodeGen/LivePhysRegs.h" |
24 | | #include "llvm/CodeGen/MachineBasicBlock.h" |
25 | | #include "llvm/CodeGen/ScheduleDAG.h" |
26 | | #include "llvm/CodeGen/TargetRegisterInfo.h" |
27 | | #include "llvm/CodeGen/TargetSchedule.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; |
53 | | LaneBitmask LaneMask; |
54 | | SUnit *SU; |
55 | | |
56 | | VReg2SUnit(unsigned VReg, LaneBitmask LaneMask, SUnit *SU) |
57 | 17.1M | : VirtReg(VReg), LaneMask(LaneMask), SU(SU) {} |
58 | | |
59 | 57.9M | unsigned getSparseSetIndex() const { |
60 | 57.9M | return TargetRegisterInfo::virtReg2Index(VirtReg); |
61 | 57.9M | } |
62 | | }; |
63 | | |
64 | | /// Mapping from virtual register to SUnit including an operand index. |
65 | | struct VReg2SUnitOperIdx : public VReg2SUnit { |
66 | | unsigned OperandIndex; |
67 | | |
68 | | VReg2SUnitOperIdx(unsigned VReg, LaneBitmask LaneMask, |
69 | | unsigned OperandIndex, SUnit *SU) |
70 | 11.9M | : 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 { |
76 | | SUnit *SU; |
77 | | int OpIdx; |
78 | | unsigned Reg; |
79 | | |
80 | 13.4M | PhysRegSUOper(SUnit *su, int op, unsigned R): SU(su), OpIdx(op), Reg(R) {} |
81 | | |
82 | 111M | 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 = |
89 | | SparseMultiSet<PhysRegSUOper, identity<unsigned>, uint16_t>; |
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. |
95 | | using VReg2SUnitMap = SparseSet<VReg2SUnit, VirtReg2IndexFunctor>; |
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. |
100 | | using VReg2SUnitMultiMap = SparseMultiSet<VReg2SUnit, VirtReg2IndexFunctor>; |
101 | | |
102 | | using VReg2SUnitOperIdxMultiMap = |
103 | | SparseMultiSet<VReg2SUnitOperIdx, VirtReg2IndexFunctor>; |
104 | | |
105 | | using ValueType = PointerUnion<const Value *, const PseudoSourceValue *>; |
106 | | |
107 | | struct UnderlyingObject : PointerIntPair<ValueType, 1, bool> { |
108 | | UnderlyingObject(ValueType V, bool MayAlias) |
109 | 1.10M | : PointerIntPair<ValueType, 1, bool>(V, MayAlias) {} |
110 | | |
111 | 1.85M | ValueType getValue() const { return getPointer(); } |
112 | 1.85M | bool mayAlias() const { return getInt(); } |
113 | | }; |
114 | | |
115 | | using UnderlyingObjectsVector = SmallVector<UnderlyingObject, 4>; |
116 | | |
117 | | /// A ScheduleDAG for scheduling lists of MachineInstr. |
118 | | class ScheduleDAGInstrs : public ScheduleDAG { |
119 | | protected: |
120 | | const MachineLoopInfo *MLI; |
121 | | const MachineFrameInfo &MFI; |
122 | | |
123 | | /// TargetSchedModel provides an interface to the machine model. |
124 | | TargetSchedModel SchedModel; |
125 | | |
126 | | /// True if the DAG builder should remove kill flags (in preparation for |
127 | | /// rescheduling). |
128 | | bool RemoveKillFlags; |
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 |
144 | | MachineBasicBlock *BB; |
145 | | |
146 | | /// The beginning of the range to be scheduled. |
147 | | MachineBasicBlock::iterator RegionBegin; |
148 | | |
149 | | /// The end of the range to be scheduled. |
150 | | MachineBasicBlock::iterator RegionEnd; |
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. |
157 | | DenseMap<MachineInstr*, SUnit*> MISUnitMap; |
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. |
166 | | Reg2SUnitsMap Defs; |
167 | | Reg2SUnitsMap Uses; |
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. |
172 | | VReg2SUnitMultiMap CurrentVRegDefs; |
173 | | /// Tracks the last instructions in this region using each virtual register. |
174 | | VReg2SUnitOperIdxMultiMap CurrentVRegUses; |
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 | 1.35M | void addChainDependencies(SUnit *SU, SUList &SUs, unsigned Latency) { |
210 | 1.35M | for (SUnit *Entry : SUs) |
211 | 16.5M | addChainDependency(SU, Entry, Latency); |
212 | 1.35M | } |
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. |
235 | | UndefValue *UnknownValue; |
236 | | |
237 | | |
238 | | /// Topo - A topological ordering for SUnits which permits fast IsReachable |
239 | | /// and similar queries. |
240 | | ScheduleDAGTopologicalSort Topo; |
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. |
247 | | DbgValueVector DbgValues; |
248 | | MachineInstr *FirstDbgValue = nullptr; |
249 | | |
250 | | /// Set of live physical registers for updating kill flags. |
251 | | LivePhysRegs LiveRegs; |
252 | | |
253 | | public: |
254 | | explicit ScheduleDAGInstrs(MachineFunction &mf, |
255 | | const MachineLoopInfo *mli, |
256 | | bool RemoveKillFlags = false); |
257 | | |
258 | 526k | ~ScheduleDAGInstrs() override = default; |
259 | | |
260 | | /// Gets the machine model for instruction scheduling. |
261 | 2.69M | const TargetSchedModel *getSchedModel() const { return &SchedModel; } |
262 | | |
263 | | /// Resolves and cache a resolved scheduling class for an SUnit. |
264 | 50.7M | const MCSchedClassDesc *getSchedClass(SUnit *SU) const { |
265 | 50.7M | if (!SU->SchedClass && SchedModel.hasInstrSchedModel()12.3M ) |
266 | 11.1M | SU->SchedClass = SchedModel.resolveSchedClass(SU->getInstr()); |
267 | 50.7M | return SU->SchedClass; |
268 | 50.7M | } |
269 | | |
270 | | /// Returns an iterator to the top of the current scheduling region. |
271 | 5.41M | MachineBasicBlock::iterator begin() const { return RegionBegin; } |
272 | | |
273 | | /// Returns an iterator to the bottom of the current scheduling region. |
274 | 8.03M | 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 | 0 | 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, |
298 | | MachineBasicBlock::iterator begin, |
299 | | MachineBasicBlock::iterator end, |
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 | 448k | 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. |
380 | 12.9M | inline SUnit *ScheduleDAGInstrs::newSUnit(MachineInstr *MI) { |
381 | | #ifndef NDEBUG |
382 | | const SUnit *Addr = SUnits.empty() ? nullptr : &SUnits[0]; |
383 | | #endif |
384 | | SUnits.emplace_back(MI, (unsigned)SUnits.size()); |
385 | 12.9M | assert((Addr == nullptr || Addr == &SUnits[0]) && |
386 | 12.9M | "SUnits std::vector reallocated on the fly!"); |
387 | 12.9M | return &SUnits.back(); |
388 | 12.9M | } |
389 | | |
390 | | /// Returns an existing SUnit for this MI, or nullptr. |
391 | 369k | inline SUnit *ScheduleDAGInstrs::getSUnit(MachineInstr *MI) const { |
392 | 369k | DenseMap<MachineInstr*, SUnit*>::const_iterator I = MISUnitMap.find(MI); |
393 | 369k | if (I == MISUnitMap.end()) |
394 | 62.3k | return nullptr; |
395 | 307k | return I->second; |
396 | 307k | } |
397 | | |
398 | | } // end namespace llvm |
399 | | |
400 | | #endif // LLVM_CODEGEN_SCHEDULEDAGINSTRS_H |