Coverage Report

Created: 2019-02-21 13:17

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/CodeGen/MachineScheduler.h
Line
Count
Source (jump to first uncovered line)
1
//===- MachineScheduler.h - MachineInstr Scheduling Pass --------*- 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
// This file provides an interface for customizing the standard MachineScheduler
10
// pass. Note that the entire pass may be replaced as follows:
11
//
12
// <Target>TargetMachine::createPassConfig(PassManagerBase &PM) {
13
//   PM.substitutePass(&MachineSchedulerID, &CustomSchedulerPassID);
14
//   ...}
15
//
16
// The MachineScheduler pass is only responsible for choosing the regions to be
17
// scheduled. Targets can override the DAG builder and scheduler without
18
// replacing the pass as follows:
19
//
20
// ScheduleDAGInstrs *<Target>PassConfig::
21
// createMachineScheduler(MachineSchedContext *C) {
22
//   return new CustomMachineScheduler(C);
23
// }
24
//
25
// The default scheduler, ScheduleDAGMILive, builds the DAG and drives list
26
// scheduling while updating the instruction stream, register pressure, and live
27
// intervals. Most targets don't need to override the DAG builder and list
28
// scheduler, but subtargets that require custom scheduling heuristics may
29
// plugin an alternate MachineSchedStrategy. The strategy is responsible for
30
// selecting the highest priority node from the list:
31
//
32
// ScheduleDAGInstrs *<Target>PassConfig::
33
// createMachineScheduler(MachineSchedContext *C) {
34
//   return new ScheduleDAGMILive(C, CustomStrategy(C));
35
// }
36
//
37
// The DAG builder can also be customized in a sense by adding DAG mutations
38
// that will run after DAG building and before list scheduling. DAG mutations
39
// can adjust dependencies based on target-specific knowledge or add weak edges
40
// to aid heuristics:
41
//
42
// ScheduleDAGInstrs *<Target>PassConfig::
43
// createMachineScheduler(MachineSchedContext *C) {
44
//   ScheduleDAGMI *DAG = createGenericSchedLive(C);
45
//   DAG->addMutation(new CustomDAGMutation(...));
46
//   return DAG;
47
// }
48
//
49
// A target that supports alternative schedulers can use the
50
// MachineSchedRegistry to allow command line selection. This can be done by
51
// implementing the following boilerplate:
52
//
53
// static ScheduleDAGInstrs *createCustomMachineSched(MachineSchedContext *C) {
54
//  return new CustomMachineScheduler(C);
55
// }
56
// static MachineSchedRegistry
57
// SchedCustomRegistry("custom", "Run my target's custom scheduler",
58
//                     createCustomMachineSched);
59
//
60
//
61
// Finally, subtargets that don't need to implement custom heuristics but would
62
// like to configure the GenericScheduler's policy for a given scheduler region,
63
// including scheduling direction and register pressure tracking policy, can do
64
// this:
65
//
66
// void <SubTarget>Subtarget::
67
// overrideSchedPolicy(MachineSchedPolicy &Policy,
68
//                     unsigned NumRegionInstrs) const {
69
//   Policy.<Flag> = true;
70
// }
71
//
72
//===----------------------------------------------------------------------===//
73
74
#ifndef LLVM_CODEGEN_MACHINESCHEDULER_H
75
#define LLVM_CODEGEN_MACHINESCHEDULER_H
76
77
#include "llvm/ADT/ArrayRef.h"
78
#include "llvm/ADT/BitVector.h"
79
#include "llvm/ADT/STLExtras.h"
80
#include "llvm/ADT/SmallVector.h"
81
#include "llvm/ADT/StringRef.h"
82
#include "llvm/ADT/Twine.h"
83
#include "llvm/Analysis/AliasAnalysis.h"
84
#include "llvm/CodeGen/MachineBasicBlock.h"
85
#include "llvm/CodeGen/MachinePassRegistry.h"
86
#include "llvm/CodeGen/RegisterPressure.h"
87
#include "llvm/CodeGen/ScheduleDAG.h"
88
#include "llvm/CodeGen/ScheduleDAGInstrs.h"
89
#include "llvm/CodeGen/ScheduleDAGMutation.h"
90
#include "llvm/CodeGen/TargetSchedule.h"
91
#include "llvm/Support/CommandLine.h"
92
#include "llvm/Support/ErrorHandling.h"
93
#include <algorithm>
94
#include <cassert>
95
#include <memory>
96
#include <string>
97
#include <vector>
98
99
namespace llvm {
100
101
extern cl::opt<bool> ForceTopDown;
102
extern cl::opt<bool> ForceBottomUp;
103
104
class LiveIntervals;
105
class MachineDominatorTree;
106
class MachineFunction;
107
class MachineInstr;
108
class MachineLoopInfo;
109
class RegisterClassInfo;
110
class SchedDFSResult;
111
class ScheduleHazardRecognizer;
112
class TargetInstrInfo;
113
class TargetPassConfig;
114
class TargetRegisterInfo;
115
116
/// MachineSchedContext provides enough context from the MachineScheduler pass
117
/// for the target to instantiate a scheduler.
118
struct MachineSchedContext {
119
  MachineFunction *MF = nullptr;
120
  const MachineLoopInfo *MLI = nullptr;
121
  const MachineDominatorTree *MDT = nullptr;
122
  const TargetPassConfig *PassConfig = nullptr;
123
  AliasAnalysis *AA = nullptr;
124
  LiveIntervals *LIS = nullptr;
125
126
  RegisterClassInfo *RegClassInfo;
127
128
  MachineSchedContext();
129
  virtual ~MachineSchedContext();
130
};
131
132
/// MachineSchedRegistry provides a selection of available machine instruction
133
/// schedulers.
134
class MachineSchedRegistry
135
    : public MachinePassRegistryNode<
136
          ScheduleDAGInstrs *(*)(MachineSchedContext *)> {
137
public:
138
  using ScheduleDAGCtor = ScheduleDAGInstrs *(*)(MachineSchedContext *);
139
140
  // RegisterPassParser requires a (misnamed) FunctionPassCtor type.
141
  using FunctionPassCtor = ScheduleDAGCtor;
142
143
  static MachinePassRegistry<ScheduleDAGCtor> Registry;
144
145
  MachineSchedRegistry(const char *N, const char *D, ScheduleDAGCtor C)
146
1.07M
      : MachinePassRegistryNode(N, D, C) {
147
1.07M
    Registry.Add(this);
148
1.07M
  }
149
150
1.07M
  ~MachineSchedRegistry() { Registry.Remove(this); }
151
152
  // Accessors.
153
  //
154
682k
  MachineSchedRegistry *getNext() const {
155
682k
    return (MachineSchedRegistry *)MachinePassRegistryNode::getNext();
156
682k
  }
157
158
97.8k
  static MachineSchedRegistry *getList() {
159
97.8k
    return (MachineSchedRegistry *)Registry.getList();
160
97.8k
  }
161
162
195k
  static void setListener(MachinePassRegistryListener<FunctionPassCtor> *L) {
163
195k
    Registry.setListener(L);
164
195k
  }
165
};
166
167
class ScheduleDAGMI;
168
169
/// Define a generic scheduling policy for targets that don't provide their own
170
/// MachineSchedStrategy. This can be overriden for each scheduling region
171
/// before building the DAG.
172
struct MachineSchedPolicy {
173
  // Allow the scheduler to disable register pressure tracking.
174
  bool ShouldTrackPressure = false;
175
  /// Track LaneMasks to allow reordering of independent subregister writes
176
  /// of the same vreg. \sa MachineSchedStrategy::shouldTrackLaneMasks()
177
  bool ShouldTrackLaneMasks = false;
178
179
  // Allow the scheduler to force top-down or bottom-up scheduling. If neither
180
  // is true, the scheduler runs in both directions and converges.
181
  bool OnlyTopDown = false;
182
  bool OnlyBottomUp = false;
183
184
  // Disable heuristic that tries to fetch nodes from long dependency chains
185
  // first.
186
  bool DisableLatencyHeuristic = false;
187
188
422k
  MachineSchedPolicy() = default;
189
};
190
191
/// MachineSchedStrategy - Interface to the scheduling algorithm used by
192
/// ScheduleDAGMI.
193
///
194
/// Initialization sequence:
195
///   initPolicy -> shouldTrackPressure -> initialize(DAG) -> registerRoots
196
class MachineSchedStrategy {
197
  virtual void anchor();
198
199
public:
200
452k
  virtual ~MachineSchedStrategy() = default;
201
202
  /// Optionally override the per-region scheduling policy.
203
  virtual void initPolicy(MachineBasicBlock::iterator Begin,
204
                          MachineBasicBlock::iterator End,
205
9.46k
                          unsigned NumRegionInstrs) {}
206
207
0
  virtual void dumpPolicy() const {}
208
209
  /// Check if pressure tracking is needed before building the DAG and
210
  /// initializing this strategy. Called after initPolicy.
211
9.45k
  virtual bool shouldTrackPressure() const { return true; }
212
213
  /// Returns true if lanemasks should be tracked. LaneMask tracking is
214
  /// necessary to reorder independent subregister defs for the same vreg.
215
  /// This has to be enabled in combination with shouldTrackPressure().
216
9.45k
  virtual bool shouldTrackLaneMasks() const { return false; }
217
218
  // If this method returns true, handling of the scheduling regions
219
  // themselves (in case of a scheduling boundary in MBB) will be done
220
  // beginning with the topmost region of MBB.
221
2.76M
  virtual bool doMBBSchedRegionsTopDown() const { return false; }
222
223
  /// Initialize the strategy after building the DAG for a new region.
224
  virtual void initialize(ScheduleDAGMI *DAG) = 0;
225
226
  /// Tell the strategy that MBB is about to be processed.
227
2.78M
  virtual void enterMBB(MachineBasicBlock *MBB) {};
228
229
  /// Tell the strategy that current MBB is done.
230
2.78M
  virtual void leaveMBB() {};
231
232
  /// Notify this strategy that all roots have been released (including those
233
  /// that depend on EntrySU or ExitSU).
234
9.10k
  virtual void registerRoots() {}
235
236
  /// Pick the next node to schedule, or return NULL. Set IsTopNode to true to
237
  /// schedule the node at the top of the unscheduled region. Otherwise it will
238
  /// be scheduled at the bottom.
239
  virtual SUnit *pickNode(bool &IsTopNode) = 0;
240
241
  /// Scheduler callback to notify that a new subtree is scheduled.
242
0
  virtual void scheduleTree(unsigned SubtreeID) {}
243
244
  /// Notify MachineSchedStrategy that ScheduleDAGMI has scheduled an
245
  /// instruction and updated scheduled/remaining flags in the DAG nodes.
246
  virtual void schedNode(SUnit *SU, bool IsTopNode) = 0;
247
248
  /// When all predecessor dependencies have been resolved, free this node for
249
  /// top-down scheduling.
250
  virtual void releaseTopNode(SUnit *SU) = 0;
251
252
  /// When all successor dependencies have been resolved, free this node for
253
  /// bottom-up scheduling.
254
  virtual void releaseBottomNode(SUnit *SU) = 0;
255
};
256
257
/// ScheduleDAGMI is an implementation of ScheduleDAGInstrs that simply
258
/// schedules machine instructions according to the given MachineSchedStrategy
259
/// without much extra book-keeping. This is the common functionality between
260
/// PreRA and PostRA MachineScheduler.
261
class ScheduleDAGMI : public ScheduleDAGInstrs {
262
protected:
263
  AliasAnalysis *AA;
264
  LiveIntervals *LIS;
265
  std::unique_ptr<MachineSchedStrategy> SchedImpl;
266
267
  /// Topo - A topological ordering for SUnits which permits fast IsReachable
268
  /// and similar queries.
269
  ScheduleDAGTopologicalSort Topo;
270
271
  /// Ordered list of DAG postprocessing steps.
272
  std::vector<std::unique_ptr<ScheduleDAGMutation>> Mutations;
273
274
  /// The top of the unscheduled zone.
275
  MachineBasicBlock::iterator CurrentTop;
276
277
  /// The bottom of the unscheduled zone.
278
  MachineBasicBlock::iterator CurrentBottom;
279
280
  /// Record the next node in a scheduled cluster.
281
  const SUnit *NextClusterPred = nullptr;
282
  const SUnit *NextClusterSucc = nullptr;
283
284
#ifndef NDEBUG
285
  /// The number of instructions scheduled so far. Used to cut off the
286
  /// scheduler at the point determined by misched-cutoff.
287
  unsigned NumInstrsScheduled = 0;
288
#endif
289
290
public:
291
  ScheduleDAGMI(MachineSchedContext *C, std::unique_ptr<MachineSchedStrategy> S,
292
                bool RemoveKillFlags)
293
      : ScheduleDAGInstrs(*C->MF, C->MLI, RemoveKillFlags), AA(C->AA),
294
452k
        LIS(C->LIS), SchedImpl(std::move(S)), Topo(SUnits, &ExitSU) {}
295
296
  // Provide a vtable anchor
297
  ~ScheduleDAGMI() override;
298
299
  /// If this method returns true, handling of the scheduling regions
300
  /// themselves (in case of a scheduling boundary in MBB) will be done
301
  /// beginning with the topmost region of MBB.
302
2.76M
  bool doMBBSchedRegionsTopDown() const override {
303
2.76M
    return SchedImpl->doMBBSchedRegionsTopDown();
304
2.76M
  }
305
306
  // Returns LiveIntervals instance for use in DAG mutators and such.
307
9.00M
  LiveIntervals *getLIS() const { return LIS; }
308
309
  /// Return true if this DAG supports VReg liveness and RegPressure.
310
0
  virtual bool hasVRegLiveness() const { return false; }
311
312
  /// Add a postprocessing step to the DAG builder.
313
  /// Mutations are applied in the order that they are added after normal DAG
314
  /// building and before MachineSchedStrategy initialization.
315
  ///
316
  /// ScheduleDAGMI takes ownership of the Mutation object.
317
1.38M
  void addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation) {
318
1.38M
    if (Mutation)
319
1.38M
      Mutations.push_back(std::move(Mutation));
320
1.38M
  }
321
322
  /// True if an edge can be added from PredSU to SuccSU without creating
323
  /// a cycle.
324
  bool canAddEdge(SUnit *SuccSU, SUnit *PredSU);
325
326
  /// Add a DAG edge to the given SU with the given predecessor
327
  /// dependence data.
328
  ///
329
  /// \returns true if the edge may be added without creating a cycle OR if an
330
  /// equivalent edge already existed (false indicates failure).
331
  bool addEdge(SUnit *SuccSU, const SDep &PredDep);
332
333
15.0M
  MachineBasicBlock::iterator top() const { return CurrentTop; }
334
15.0M
  MachineBasicBlock::iterator bottom() const { return CurrentBottom; }
335
336
  /// Implement the ScheduleDAGInstrs interface for handling the next scheduling
337
  /// region. This covers all instructions in a block, while schedule() may only
338
  /// cover a subset.
339
  void enterRegion(MachineBasicBlock *bb,
340
                   MachineBasicBlock::iterator begin,
341
                   MachineBasicBlock::iterator end,
342
                   unsigned regioninstrs) override;
343
344
  /// Implement ScheduleDAGInstrs interface for scheduling a sequence of
345
  /// reorderable instructions.
346
  void schedule() override;
347
348
  void startBlock(MachineBasicBlock *bb) override;
349
  void finishBlock() override;
350
351
  /// Change the position of an instruction within the basic block and update
352
  /// live ranges and region boundary iterators.
353
  void moveInstruction(MachineInstr *MI, MachineBasicBlock::iterator InsertPos);
354
355
66.2M
  const SUnit *getNextClusterPred() const { return NextClusterPred; }
356
357
32.7M
  const SUnit *getNextClusterSucc() const { return NextClusterSucc; }
358
359
  void viewGraph(const Twine &Name, const Twine &Title) override;
360
  void viewGraph() override;
361
362
protected:
363
  // Top-Level entry points for the schedule() driver...
364
365
  /// Apply each ScheduleDAGMutation step in order. This allows different
366
  /// instances of ScheduleDAGMI to perform custom DAG postprocessing.
367
  void postprocessDAG();
368
369
  /// Release ExitSU predecessors and setup scheduler queues.
370
  void initQueues(ArrayRef<SUnit*> TopRoots, ArrayRef<SUnit*> BotRoots);
371
372
  /// Update scheduler DAG and queues after scheduling an instruction.
373
  void updateQueues(SUnit *SU, bool IsTopNode);
374
375
  /// Reinsert debug_values recorded in ScheduleDAGInstrs::DbgValues.
376
  void placeDebugValues();
377
378
  /// dump the scheduled Sequence.
379
  void dumpSchedule() const;
380
381
  // Lesser helpers...
382
  bool checkSchedLimit();
383
384
  void findRootsAndBiasEdges(SmallVectorImpl<SUnit*> &TopRoots,
385
                             SmallVectorImpl<SUnit*> &BotRoots);
386
387
  void releaseSucc(SUnit *SU, SDep *SuccEdge);
388
  void releaseSuccessors(SUnit *SU);
389
  void releasePred(SUnit *SU, SDep *PredEdge);
390
  void releasePredecessors(SUnit *SU);
391
};
392
393
/// ScheduleDAGMILive is an implementation of ScheduleDAGInstrs that schedules
394
/// machine instructions while updating LiveIntervals and tracking regpressure.
395
class ScheduleDAGMILive : public ScheduleDAGMI {
396
protected:
397
  RegisterClassInfo *RegClassInfo;
398
399
  /// Information about DAG subtrees. If DFSResult is NULL, then SchedulerTrees
400
  /// will be empty.
401
  SchedDFSResult *DFSResult = nullptr;
402
  BitVector ScheduledTrees;
403
404
  MachineBasicBlock::iterator LiveRegionEnd;
405
406
  /// Maps vregs to the SUnits of their uses in the current scheduling region.
407
  VReg2SUnitMultiMap VRegUses;
408
409
  // Map each SU to its summary of pressure changes. This array is updated for
410
  // liveness during bottom-up scheduling. Top-down scheduling may proceed but
411
  // has no affect on the pressure diffs.
412
  PressureDiffs SUPressureDiffs;
413
414
  /// Register pressure in this region computed by initRegPressure.
415
  bool ShouldTrackPressure = false;
416
  bool ShouldTrackLaneMasks = false;
417
  IntervalPressure RegPressure;
418
  RegPressureTracker RPTracker;
419
420
  /// List of pressure sets that exceed the target's pressure limit before
421
  /// scheduling, listed in increasing set ID order. Each pressure set is paired
422
  /// with its max pressure in the currently scheduled regions.
423
  std::vector<PressureChange> RegionCriticalPSets;
424
425
  /// The top of the unscheduled zone.
426
  IntervalPressure TopPressure;
427
  RegPressureTracker TopRPTracker;
428
429
  /// The bottom of the unscheduled zone.
430
  IntervalPressure BotPressure;
431
  RegPressureTracker BotRPTracker;
432
433
  /// True if disconnected subregister components are already renamed.
434
  /// The renaming is only done on demand if lane masks are tracked.
435
  bool DisconnectedComponentsRenamed = false;
436
437
public:
438
  ScheduleDAGMILive(MachineSchedContext *C,
439
                    std::unique_ptr<MachineSchedStrategy> S)
440
      : ScheduleDAGMI(C, std::move(S), /*RemoveKillFlags=*/false),
441
        RegClassInfo(C->RegClassInfo), RPTracker(RegPressure),
442
428k
        TopRPTracker(TopPressure), BotRPTracker(BotPressure) {}
443
444
  ~ScheduleDAGMILive() override;
445
446
  /// Return true if this DAG supports VReg liveness and RegPressure.
447
0
  bool hasVRegLiveness() const override { return true; }
448
449
  /// Return true if register pressure tracking is enabled.
450
203M
  bool isTrackingPressure() const { return ShouldTrackPressure; }
451
452
  /// Get current register pressure for the top scheduled instructions.
453
0
  const IntervalPressure &getTopPressure() const { return TopPressure; }
454
2.83M
  const RegPressureTracker &getTopRPTracker() const { return TopRPTracker; }
455
456
  /// Get current register pressure for the bottom scheduled instructions.
457
0
  const IntervalPressure &getBotPressure() const { return BotPressure; }
458
6.43M
  const RegPressureTracker &getBotRPTracker() const { return BotRPTracker; }
459
460
  /// Get register pressure for the entire scheduling region before scheduling.
461
38.3M
  const IntervalPressure &getRegPressure() const { return RegPressure; }
462
463
38.3M
  const std::vector<PressureChange> &getRegionCriticalPSets() const {
464
38.3M
    return RegionCriticalPSets;
465
38.3M
  }
466
467
33.5M
  PressureDiff &getPressureDiff(const SUnit *SU) {
468
33.5M
    return SUPressureDiffs[SU->NodeNum];
469
33.5M
  }
470
0
  const PressureDiff &getPressureDiff(const SUnit *SU) const {
471
0
    return SUPressureDiffs[SU->NodeNum];
472
0
  }
473
474
  /// Compute a DFSResult after DAG building is complete, and before any
475
  /// queue comparisons.
476
  void computeDFSResult();
477
478
  /// Return a non-null DFS result if the scheduling strategy initialized it.
479
10
  const SchedDFSResult *getDFSResult() const { return DFSResult; }
480
481
10
  BitVector &getScheduledTrees() { return ScheduledTrees; }
482
483
  /// Implement the ScheduleDAGInstrs interface for handling the next scheduling
484
  /// region. This covers all instructions in a block, while schedule() may only
485
  /// cover a subset.
486
  void enterRegion(MachineBasicBlock *bb,
487
                   MachineBasicBlock::iterator begin,
488
                   MachineBasicBlock::iterator end,
489
                   unsigned regioninstrs) override;
490
491
  /// Implement ScheduleDAGInstrs interface for scheduling a sequence of
492
  /// reorderable instructions.
493
  void schedule() override;
494
495
  /// Compute the cyclic critical path through the DAG.
496
  unsigned computeCyclicCriticalPath();
497
498
  void dump() const override;
499
500
protected:
501
  // Top-Level entry points for the schedule() driver...
502
503
  /// Call ScheduleDAGInstrs::buildSchedGraph with register pressure tracking
504
  /// enabled. This sets up three trackers. RPTracker will cover the entire DAG
505
  /// region, TopTracker and BottomTracker will be initialized to the top and
506
  /// bottom of the DAG region without covereing any unscheduled instruction.
507
  void buildDAGWithRegPressure();
508
509
  /// Release ExitSU predecessors and setup scheduler queues. Re-position
510
  /// the Top RP tracker in case the region beginning has changed.
511
  void initQueues(ArrayRef<SUnit*> TopRoots, ArrayRef<SUnit*> BotRoots);
512
513
  /// Move an instruction and update register pressure.
514
  void scheduleMI(SUnit *SU, bool IsTopNode);
515
516
  // Lesser helpers...
517
518
  void initRegPressure();
519
520
  void updatePressureDiffs(ArrayRef<RegisterMaskPair> LiveUses);
521
522
  void updateScheduledPressure(const SUnit *SU,
523
                               const std::vector<unsigned> &NewMaxPressure);
524
525
  void collectVRegUses(SUnit &SU);
526
};
527
528
//===----------------------------------------------------------------------===//
529
///
530
/// Helpers for implementing custom MachineSchedStrategy classes. These take
531
/// care of the book-keeping associated with list scheduling heuristics.
532
///
533
//===----------------------------------------------------------------------===//
534
535
/// ReadyQueue encapsulates vector of "ready" SUnits with basic convenience
536
/// methods for pushing and removing nodes. ReadyQueue's are uniquely identified
537
/// by an ID. SUnit::NodeQueueId is a mask of the ReadyQueues the SUnit is in.
538
///
539
/// This is a convenience class that may be used by implementations of
540
/// MachineSchedStrategy.
541
class ReadyQueue {
542
  unsigned ID;
543
  std::string Name;
544
  std::vector<SUnit*> Queue;
545
546
public:
547
1.74M
  ReadyQueue(unsigned id, const Twine &name): ID(id), Name(name.str()) {}
548
549
440M
  unsigned getID() const { return ID; }
550
551
  StringRef getName() const { return Name; }
552
553
  // SU is in this queue if it's NodeQueueID is a superset of this ID.
554
19.5M
  bool isInQueue(SUnit *SU) const { return (SU->NodeQueueId & ID); }
555
556
19.6M
  bool empty() const { return Queue.empty(); }
557
558
12.5M
  void clear() { Queue.clear(); }
559
560
40.4M
  unsigned size() const { return Queue.size(); }
561
562
  using iterator = std::vector<SUnit*>::iterator;
563
564
29.6M
  iterator begin() { return Queue.begin(); }
565
566
66.6M
  iterator end() { return Queue.end(); }
567
568
22.9M
  ArrayRef<SUnit*> elements() { return Queue; }
569
570
19.5M
  iterator find(SUnit *SU) { return llvm::find(Queue, SU); }
571
572
22.5M
  void push(SUnit *SU) {
573
22.5M
    Queue.push_back(SU);
574
22.5M
    SU->NodeQueueId |= ID;
575
22.5M
  }
576
577
22.5M
  iterator remove(iterator I) {
578
22.5M
    (*I)->NodeQueueId &= ~ID;
579
22.5M
    *I = Queue.back();
580
22.5M
    unsigned idx = I - Queue.begin();
581
22.5M
    Queue.pop_back();
582
22.5M
    return Queue.begin() + idx;
583
22.5M
  }
584
585
  void dump() const;
586
};
587
588
/// Summarize the unscheduled region.
589
struct SchedRemainder {
590
  // Critical path through the DAG in expected latency.
591
  unsigned CriticalPath;
592
  unsigned CyclicCritPath;
593
594
  // Scaled count of micro-ops left to schedule.
595
  unsigned RemIssueCount;
596
597
  bool IsAcyclicLatencyLimited;
598
599
  // Unscheduled resources
600
  SmallVector<unsigned, 16> RemainingCounts;
601
602
444k
  SchedRemainder() { reset(); }
603
604
3.14M
  void reset() {
605
3.14M
    CriticalPath = 0;
606
3.14M
    CyclicCritPath = 0;
607
3.14M
    RemIssueCount = 0;
608
3.14M
    IsAcyclicLatencyLimited = false;
609
3.14M
    RemainingCounts.clear();
610
3.14M
  }
611
612
  void init(ScheduleDAGMI *DAG, const TargetSchedModel *SchedModel);
613
};
614
615
/// Each Scheduling boundary is associated with ready queues. It tracks the
616
/// current cycle in the direction of movement, and maintains the state
617
/// of "hazards" and other interlocks at the current cycle.
618
class SchedBoundary {
619
public:
620
  /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both)
621
  enum {
622
    TopQID = 1,
623
    BotQID = 2,
624
    LogMaxQID = 2
625
  };
626
627
  ScheduleDAGMI *DAG = nullptr;
628
  const TargetSchedModel *SchedModel = nullptr;
629
  SchedRemainder *Rem = nullptr;
630
631
  ReadyQueue Available;
632
  ReadyQueue Pending;
633
634
  ScheduleHazardRecognizer *HazardRec = nullptr;
635
636
private:
637
  /// True if the pending Q should be checked/updated before scheduling another
638
  /// instruction.
639
  bool CheckPending;
640
641
  /// Number of cycles it takes to issue the instructions scheduled in this
642
  /// zone. It is defined as: scheduled-micro-ops / issue-width + stalls.
643
  /// See getStalls().
644
  unsigned CurrCycle;
645
646
  /// Micro-ops issued in the current cycle
647
  unsigned CurrMOps;
648
649
  /// MinReadyCycle - Cycle of the soonest available instruction.
650
  unsigned MinReadyCycle;
651
652
  // The expected latency of the critical path in this scheduled zone.
653
  unsigned ExpectedLatency;
654
655
  // The latency of dependence chains leading into this zone.
656
  // For each node scheduled bottom-up: DLat = max DLat, N.Depth.
657
  // For each cycle scheduled: DLat -= 1.
658
  unsigned DependentLatency;
659
660
  /// Count the scheduled (issued) micro-ops that can be retired by
661
  /// time=CurrCycle assuming the first scheduled instr is retired at time=0.
662
  unsigned RetiredMOps;
663
664
  // Count scheduled resources that have been executed. Resources are
665
  // considered executed if they become ready in the time that it takes to
666
  // saturate any resource including the one in question. Counts are scaled
667
  // for direct comparison with other resources. Counts can be compared with
668
  // MOps * getMicroOpFactor and Latency * getLatencyFactor.
669
  SmallVector<unsigned, 16> ExecutedResCounts;
670
671
  /// Cache the max count for a single resource.
672
  unsigned MaxExecutedResCount;
673
674
  // Cache the critical resources ID in this scheduled zone.
675
  unsigned ZoneCritResIdx;
676
677
  // Is the scheduled region resource limited vs. latency limited.
678
  bool IsResourceLimited;
679
680
  // Record the highest cycle at which each resource has been reserved by a
681
  // scheduled instruction.
682
  SmallVector<unsigned, 16> ReservedCycles;
683
684
#ifndef NDEBUG
685
  // Remember the greatest possible stall as an upper bound on the number of
686
  // times we should retry the pending queue because of a hazard.
687
  unsigned MaxObservedStall;
688
#endif
689
690
public:
691
  /// Pending queues extend the ready queues with the same ID and the
692
  /// PendingFlag set.
693
  SchedBoundary(unsigned ID, const Twine &Name):
694
867k
    Available(ID, Name+".A"), Pending(ID << LogMaxQID, Name+".P") {
695
867k
    reset();
696
867k
  }
697
698
  ~SchedBoundary();
699
700
  void reset();
701
702
  void init(ScheduleDAGMI *dag, const TargetSchedModel *smodel,
703
            SchedRemainder *rem);
704
705
439M
  bool isTop() const {
706
439M
    return Available.getID() == TopQID;
707
439M
  }
708
709
  /// Number of cycles to issue the instructions scheduled in this zone.
710
32.9M
  unsigned getCurrCycle() const { return CurrCycle; }
711
712
  /// Micro-ops issued in the current cycle
713
305k
  unsigned getCurrMOps() const { return CurrMOps; }
714
715
  // The latency of dependence chains leading into this zone.
716
11.4M
  unsigned getDependentLatency() const { return DependentLatency; }
717
718
  /// Get the number of latency cycles "covered" by the scheduled
719
  /// instructions. This is the larger of the critical path within the zone
720
  /// and the number of cycles required to issue the instructions.
721
14.8M
  unsigned getScheduledLatency() const {
722
14.8M
    return std::max(ExpectedLatency, CurrCycle);
723
14.8M
  }
724
725
142M
  unsigned getUnscheduledLatency(SUnit *SU) const {
726
142M
    return isTop() ? 
SU->getHeight()89.8M
:
SU->getDepth()52.4M
;
727
142M
  }
728
729
172M
  unsigned getResourceCount(unsigned ResIdx) const {
730
172M
    return ExecutedResCounts[ResIdx];
731
172M
  }
732
733
  /// Get the scaled count of scheduled micro-ops and resources, including
734
  /// executed resources.
735
21.2M
  unsigned getCriticalCount() const {
736
21.2M
    if (!ZoneCritResIdx)
737
7.84M
      return RetiredMOps * SchedModel->getMicroOpFactor();
738
13.3M
    return getResourceCount(ZoneCritResIdx);
739
13.3M
  }
740
741
  /// Get a scaled count for the minimum execution time of the scheduled
742
  /// micro-ops that are ready to execute by getExecutedCount. Notice the
743
  /// feedback loop.
744
0
  unsigned getExecutedCount() const {
745
0
    return std::max(CurrCycle * SchedModel->getLatencyFactor(),
746
0
                    MaxExecutedResCount);
747
0
  }
748
749
11.7M
  unsigned getZoneCritResIdx() const { return ZoneCritResIdx; }
750
751
  // Is the scheduled region resource limited vs. latency limited.
752
5.01M
  bool isResourceLimited() const { return IsResourceLimited; }
753
754
  /// Get the difference between the given SUnit's ready time and the current
755
  /// cycle.
756
  unsigned getLatencyStallCycles(SUnit *SU);
757
758
  unsigned getNextResourceCycle(unsigned PIdx, unsigned Cycles);
759
760
  bool checkHazard(SUnit *SU);
761
762
  unsigned findMaxLatency(ArrayRef<SUnit*> ReadySUs);
763
764
  unsigned getOtherResourceCount(unsigned &OtherCritIdx);
765
766
  void releaseNode(SUnit *SU, unsigned ReadyCycle);
767
768
  void bumpCycle(unsigned NextCycle);
769
770
  void incExecutedResources(unsigned PIdx, unsigned Count);
771
772
  unsigned countResource(unsigned PIdx, unsigned Cycles, unsigned ReadyCycle);
773
774
  void bumpNode(SUnit *SU);
775
776
  void releasePending();
777
778
  void removeReady(SUnit *SU);
779
780
  /// Call this before applying any other heuristics to the Available queue.
781
  /// Updates the Available/Pending Q's if necessary and returns the single
782
  /// available instruction, or NULL if there are multiple candidates.
783
  SUnit *pickOnlyChoice();
784
785
  void dumpScheduledState() const;
786
};
787
788
/// Base class for GenericScheduler. This class maintains information about
789
/// scheduling candidates based on TargetSchedModel making it easy to implement
790
/// heuristics for either preRA or postRA scheduling.
791
class GenericSchedulerBase : public MachineSchedStrategy {
792
public:
793
  /// Represent the type of SchedCandidate found within a single queue.
794
  /// pickNodeBidirectional depends on these listed by decreasing priority.
795
  enum CandReason : uint8_t {
796
    NoCand, Only1, PhysReg, RegExcess, RegCritical, Stall, Cluster, Weak,
797
    RegMax, ResourceReduce, ResourceDemand, BotHeightReduce, BotPathReduce,
798
    TopDepthReduce, TopPathReduce, NextDefUse, NodeOrder};
799
800
#ifndef NDEBUG
801
  static const char *getReasonStr(GenericSchedulerBase::CandReason Reason);
802
#endif
803
804
  /// Policy for scheduling the next instruction in the candidate's zone.
805
0
  struct CandPolicy {
806
    bool ReduceLatency = false;
807
    unsigned ReduceResIdx = 0;
808
    unsigned DemandResIdx = 0;
809
810
85.7M
    CandPolicy() = default;
811
812
4.00M
    bool operator==(const CandPolicy &RHS) const {
813
4.00M
      return ReduceLatency == RHS.ReduceLatency &&
814
4.00M
             
ReduceResIdx == RHS.ReduceResIdx3.97M
&&
815
4.00M
             
DemandResIdx == RHS.DemandResIdx3.95M
;
816
4.00M
    }
817
4.00M
    bool operator!=(const CandPolicy &RHS) const {
818
4.00M
      return !(*this == RHS);
819
4.00M
    }
820
  };
821
822
  /// Status of an instruction's critical resource consumption.
823
0
  struct SchedResourceDelta {
Unexecuted instantiation: llvm::GenericSchedulerBase::SchedResourceDelta::operator=(llvm::GenericSchedulerBase::SchedResourceDelta&&)
Unexecuted instantiation: llvm::GenericSchedulerBase::SchedResourceDelta::operator=(llvm::GenericSchedulerBase::SchedResourceDelta const&)
824
    // Count critical resources in the scheduled region required by SU.
825
    unsigned CritResources = 0;
826
827
    // Count critical resources from another region consumed by SU.
828
    unsigned DemandedResources = 0;
829
830
156M
    SchedResourceDelta() = default;
831
832
19.9M
    bool operator==(const SchedResourceDelta &RHS) const {
833
19.9M
      return CritResources == RHS.CritResources
834
19.9M
        && 
DemandedResources == RHS.DemandedResources19.2M
;
835
19.9M
    }
836
0
    bool operator!=(const SchedResourceDelta &RHS) const {
837
0
      return !operator==(RHS);
838
0
    }
839
  };
840
841
  /// Store the state used by GenericScheduler heuristics, required for the
842
  /// lifetime of one invocation of pickNode().
843
  struct SchedCandidate {
844
    CandPolicy Policy;
845
846
    // The best SUnit candidate.
847
    SUnit *SU;
848
849
    // The reason for this candidate.
850
    CandReason Reason;
851
852
    // Whether this candidate should be scheduled at top/bottom.
853
    bool AtTop;
854
855
    // Register pressure values for the best candidate.
856
    RegPressureDelta RPDelta;
857
858
    // Critical resource consumption of the best candidate.
859
    SchedResourceDelta ResDelta;
860
861
1.12M
    SchedCandidate() { reset(CandPolicy()); }
862
62.6M
    SchedCandidate(const CandPolicy &Policy) { reset(Policy); }
863
864
72.9M
    void reset(const CandPolicy &NewPolicy) {
865
72.9M
      Policy = NewPolicy;
866
72.9M
      SU = nullptr;
867
72.9M
      Reason = NoCand;
868
72.9M
      AtTop = false;
869
72.9M
      RPDelta = RegPressureDelta();
870
72.9M
      ResDelta = SchedResourceDelta();
871
72.9M
    }
872
873
79.8M
    bool isValid() const { return SU; }
874
875
    // Copy the status of another candidate without changing policy.
876
20.6M
    void setBest(SchedCandidate &Best) {
877
20.6M
      assert(Best.Reason != NoCand && "uninitialized Sched candidate");
878
20.6M
      SU = Best.SU;
879
20.6M
      Reason = Best.Reason;
880
20.6M
      AtTop = Best.AtTop;
881
20.6M
      RPDelta = Best.RPDelta;
882
20.6M
      ResDelta = Best.ResDelta;
883
20.6M
    }
884
885
    void initResourceDelta(const ScheduleDAGMI *DAG,
886
                           const TargetSchedModel *SchedModel);
887
  };
888
889
protected:
890
  const MachineSchedContext *Context;
891
  const TargetSchedModel *SchedModel = nullptr;
892
  const TargetRegisterInfo *TRI = nullptr;
893
894
  SchedRemainder Rem;
895
896
444k
  GenericSchedulerBase(const MachineSchedContext *C) : Context(C) {}
897
898
  void setPolicy(CandPolicy &Policy, bool IsPostRA, SchedBoundary &CurrZone,
899
                 SchedBoundary *OtherZone);
900
901
#ifndef NDEBUG
902
  void traceCandidate(const SchedCandidate &Cand);
903
#endif
904
905
private:
906
  bool shouldReduceLatency(const CandPolicy &Policy, SchedBoundary &CurrZone,
907
                           bool ComputeRemLatency, unsigned &RemLatency) const;
908
};
909
910
// Utility functions used by heuristics in tryCandidate().
911
bool tryLess(int TryVal, int CandVal,
912
             GenericSchedulerBase::SchedCandidate &TryCand,
913
             GenericSchedulerBase::SchedCandidate &Cand,
914
             GenericSchedulerBase::CandReason Reason);
915
bool tryGreater(int TryVal, int CandVal,
916
                GenericSchedulerBase::SchedCandidate &TryCand,
917
                GenericSchedulerBase::SchedCandidate &Cand,
918
                GenericSchedulerBase::CandReason Reason);
919
bool tryLatency(GenericSchedulerBase::SchedCandidate &TryCand,
920
                GenericSchedulerBase::SchedCandidate &Cand,
921
                SchedBoundary &Zone);
922
bool tryPressure(const PressureChange &TryP,
923
                 const PressureChange &CandP,
924
                 GenericSchedulerBase::SchedCandidate &TryCand,
925
                 GenericSchedulerBase::SchedCandidate &Cand,
926
                 GenericSchedulerBase::CandReason Reason,
927
                 const TargetRegisterInfo *TRI,
928
                 const MachineFunction &MF);
929
unsigned getWeakLeft(const SUnit *SU, bool isTop);
930
int biasPhysReg(const SUnit *SU, bool isTop);
931
932
/// GenericScheduler shrinks the unscheduled zone using heuristics to balance
933
/// the schedule.
934
class GenericScheduler : public GenericSchedulerBase {
935
public:
936
  GenericScheduler(const MachineSchedContext *C):
937
    GenericSchedulerBase(C), Top(SchedBoundary::TopQID, "TopQ"),
938
422k
    Bot(SchedBoundary::BotQID, "BotQ") {}
939
940
  void initPolicy(MachineBasicBlock::iterator Begin,
941
                  MachineBasicBlock::iterator End,
942
                  unsigned NumRegionInstrs) override;
943
944
  void dumpPolicy() const override;
945
946
7.71M
  bool shouldTrackPressure() const override {
947
7.71M
    return RegionPolicy.ShouldTrackPressure;
948
7.71M
  }
949
950
7.71M
  bool shouldTrackLaneMasks() const override {
951
7.71M
    return RegionPolicy.ShouldTrackLaneMasks;
952
7.71M
  }
953
954
  void initialize(ScheduleDAGMI *dag) override;
955
956
  SUnit *pickNode(bool &IsTopNode) override;
957
958
  void schedNode(SUnit *SU, bool IsTopNode) override;
959
960
7.52M
  void releaseTopNode(SUnit *SU) override {
961
7.52M
    if (SU->isScheduled)
962
9.30k
      return;
963
7.51M
964
7.51M
    Top.releaseNode(SU, SU->TopReadyCycle);
965
7.51M
    TopCand.SU = nullptr;
966
7.51M
  }
967
968
12.0M
  void releaseBottomNode(SUnit *SU) override {
969
12.0M
    if (SU->isScheduled)
970
177k
      return;
971
11.9M
972
11.9M
    Bot.releaseNode(SU, SU->BotReadyCycle);
973
11.9M
    BotCand.SU = nullptr;
974
11.9M
  }
975
976
  void registerRoots() override;
977
978
protected:
979
  ScheduleDAGMILive *DAG = nullptr;
980
981
  MachineSchedPolicy RegionPolicy;
982
983
  // State of the top and bottom scheduled instruction boundaries.
984
  SchedBoundary Top;
985
  SchedBoundary Bot;
986
987
  /// Candidate last picked from Top boundary.
988
  SchedCandidate TopCand;
989
  /// Candidate last picked from Bot boundary.
990
  SchedCandidate BotCand;
991
992
  void checkAcyclicLatency();
993
994
  void initCandidate(SchedCandidate &Cand, SUnit *SU, bool AtTop,
995
                     const RegPressureTracker &RPTracker,
996
                     RegPressureTracker &TempTracker);
997
998
  virtual void tryCandidate(SchedCandidate &Cand, SchedCandidate &TryCand,
999
                            SchedBoundary *Zone) const;
1000
1001
  SUnit *pickNodeBidirectional(bool &IsTopNode);
1002
1003
  void pickNodeFromQueue(SchedBoundary &Zone,
1004
                         const CandPolicy &ZonePolicy,
1005
                         const RegPressureTracker &RPTracker,
1006
                         SchedCandidate &Candidate);
1007
1008
  void reschedulePhysReg(SUnit *SU, bool isTop);
1009
};
1010
1011
/// PostGenericScheduler - Interface to the scheduling algorithm used by
1012
/// ScheduleDAGMI.
1013
///
1014
/// Callbacks from ScheduleDAGMI:
1015
///   initPolicy -> initialize(DAG) -> registerRoots -> pickNode ...
1016
class PostGenericScheduler : public GenericSchedulerBase {
1017
  ScheduleDAGMI *DAG;
1018
  SchedBoundary Top;
1019
  SmallVector<SUnit*, 8> BotRoots;
1020
1021
public:
1022
  PostGenericScheduler(const MachineSchedContext *C):
1023
21.1k
    GenericSchedulerBase(C), Top(SchedBoundary::TopQID, "TopQ") {}
1024
1025
21.1k
  ~PostGenericScheduler() override = default;
1026
1027
  void initPolicy(MachineBasicBlock::iterator Begin,
1028
                  MachineBasicBlock::iterator End,
1029
42.3k
                  unsigned NumRegionInstrs) override {
1030
42.3k
    /* no configurable policy */
1031
42.3k
  }
1032
1033
  /// PostRA scheduling does not track pressure.
1034
0
  bool shouldTrackPressure() const override { return false; }
1035
1036
  void initialize(ScheduleDAGMI *Dag) override;
1037
1038
  void registerRoots() override;
1039
1040
  SUnit *pickNode(bool &IsTopNode) override;
1041
1042
0
  void scheduleTree(unsigned SubtreeID) override {
1043
0
    llvm_unreachable("PostRA scheduler does not support subtree analysis.");
1044
0
  }
1045
1046
  void schedNode(SUnit *SU, bool IsTopNode) override;
1047
1048
107k
  void releaseTopNode(SUnit *SU) override {
1049
107k
    if (SU->isScheduled)
1050
0
      return;
1051
107k
    Top.releaseNode(SU, SU->TopReadyCycle);
1052
107k
  }
1053
1054
  // Only called for roots.
1055
30.3k
  void releaseBottomNode(SUnit *SU) override {
1056
30.3k
    BotRoots.push_back(SU);
1057
30.3k
  }
1058
1059
protected:
1060
  void tryCandidate(SchedCandidate &Cand, SchedCandidate &TryCand);
1061
1062
  void pickNodeFromQueue(SchedCandidate &Cand);
1063
};
1064
1065
/// Create the standard converging machine scheduler. This will be used as the
1066
/// default scheduler if the target does not set a default.
1067
/// Adds default DAG mutations.
1068
ScheduleDAGMILive *createGenericSchedLive(MachineSchedContext *C);
1069
1070
/// Create a generic scheduler with no vreg liveness or DAG mutation passes.
1071
ScheduleDAGMI *createGenericSchedPostRA(MachineSchedContext *C);
1072
1073
std::unique_ptr<ScheduleDAGMutation>
1074
createLoadClusterDAGMutation(const TargetInstrInfo *TII,
1075
                             const TargetRegisterInfo *TRI);
1076
1077
std::unique_ptr<ScheduleDAGMutation>
1078
createStoreClusterDAGMutation(const TargetInstrInfo *TII,
1079
                              const TargetRegisterInfo *TRI);
1080
1081
std::unique_ptr<ScheduleDAGMutation>
1082
createCopyConstrainDAGMutation(const TargetInstrInfo *TII,
1083
                               const TargetRegisterInfo *TRI);
1084
1085
} // end namespace llvm
1086
1087
#endif // LLVM_CODEGEN_MACHINESCHEDULER_H