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