Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- ScheduleDAGRRList.cpp - Reg pressure reduction list scheduler ------===//
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 implements bottom-up and top-down register pressure reduction list
10
// schedulers, using standard algorithms.  The basic approach uses a priority
11
// queue of available nodes to schedule.  One at a time, nodes are taken from
12
// the priority queue (thus in priority order), checked for legality to
13
// schedule, and emitted if legal.
14
//
15
//===----------------------------------------------------------------------===//
16
17
#include "ScheduleDAGSDNodes.h"
18
#include "llvm/ADT/ArrayRef.h"
19
#include "llvm/ADT/DenseMap.h"
20
#include "llvm/ADT/STLExtras.h"
21
#include "llvm/ADT/SmallSet.h"
22
#include "llvm/ADT/SmallVector.h"
23
#include "llvm/ADT/Statistic.h"
24
#include "llvm/CodeGen/ISDOpcodes.h"
25
#include "llvm/CodeGen/MachineFunction.h"
26
#include "llvm/CodeGen/MachineOperand.h"
27
#include "llvm/CodeGen/MachineRegisterInfo.h"
28
#include "llvm/CodeGen/ScheduleDAG.h"
29
#include "llvm/CodeGen/ScheduleHazardRecognizer.h"
30
#include "llvm/CodeGen/SchedulerRegistry.h"
31
#include "llvm/CodeGen/SelectionDAGISel.h"
32
#include "llvm/CodeGen/SelectionDAGNodes.h"
33
#include "llvm/CodeGen/TargetInstrInfo.h"
34
#include "llvm/CodeGen/TargetLowering.h"
35
#include "llvm/CodeGen/TargetOpcodes.h"
36
#include "llvm/CodeGen/TargetRegisterInfo.h"
37
#include "llvm/CodeGen/TargetSubtargetInfo.h"
38
#include "llvm/Config/llvm-config.h"
39
#include "llvm/IR/InlineAsm.h"
40
#include "llvm/MC/MCInstrDesc.h"
41
#include "llvm/MC/MCRegisterInfo.h"
42
#include "llvm/Support/Casting.h"
43
#include "llvm/Support/CodeGen.h"
44
#include "llvm/Support/CommandLine.h"
45
#include "llvm/Support/Compiler.h"
46
#include "llvm/Support/Debug.h"
47
#include "llvm/Support/ErrorHandling.h"
48
#include "llvm/Support/MachineValueType.h"
49
#include "llvm/Support/raw_ostream.h"
50
#include <algorithm>
51
#include <cassert>
52
#include <cstdint>
53
#include <cstdlib>
54
#include <iterator>
55
#include <limits>
56
#include <memory>
57
#include <utility>
58
#include <vector>
59
60
using namespace llvm;
61
62
#define DEBUG_TYPE "pre-RA-sched"
63
64
STATISTIC(NumBacktracks, "Number of times scheduler backtracked");
65
STATISTIC(NumUnfolds,    "Number of nodes unfolded");
66
STATISTIC(NumDups,       "Number of duplicated nodes");
67
STATISTIC(NumPRCopies,   "Number of physical register copies");
68
69
static RegisterScheduler
70
  burrListDAGScheduler("list-burr",
71
                       "Bottom-up register reduction list scheduling",
72
                       createBURRListDAGScheduler);
73
74
static RegisterScheduler
75
  sourceListDAGScheduler("source",
76
                         "Similar to list-burr but schedules in source "
77
                         "order when possible",
78
                         createSourceListDAGScheduler);
79
80
static RegisterScheduler
81
  hybridListDAGScheduler("list-hybrid",
82
                         "Bottom-up register pressure aware list scheduling "
83
                         "which tries to balance latency and register pressure",
84
                         createHybridListDAGScheduler);
85
86
static RegisterScheduler
87
  ILPListDAGScheduler("list-ilp",
88
                      "Bottom-up register pressure aware list scheduling "
89
                      "which tries to balance ILP and register pressure",
90
                      createILPListDAGScheduler);
91
92
static cl::opt<bool> DisableSchedCycles(
93
  "disable-sched-cycles", cl::Hidden, cl::init(false),
94
  cl::desc("Disable cycle-level precision during preRA scheduling"));
95
96
// Temporary sched=list-ilp flags until the heuristics are robust.
97
// Some options are also available under sched=list-hybrid.
98
static cl::opt<bool> DisableSchedRegPressure(
99
  "disable-sched-reg-pressure", cl::Hidden, cl::init(false),
100
  cl::desc("Disable regpressure priority in sched=list-ilp"));
101
static cl::opt<bool> DisableSchedLiveUses(
102
  "disable-sched-live-uses", cl::Hidden, cl::init(true),
103
  cl::desc("Disable live use priority in sched=list-ilp"));
104
static cl::opt<bool> DisableSchedVRegCycle(
105
  "disable-sched-vrcycle", cl::Hidden, cl::init(false),
106
  cl::desc("Disable virtual register cycle interference checks"));
107
static cl::opt<bool> DisableSchedPhysRegJoin(
108
  "disable-sched-physreg-join", cl::Hidden, cl::init(false),
109
  cl::desc("Disable physreg def-use affinity"));
110
static cl::opt<bool> DisableSchedStalls(
111
  "disable-sched-stalls", cl::Hidden, cl::init(true),
112
  cl::desc("Disable no-stall priority in sched=list-ilp"));
113
static cl::opt<bool> DisableSchedCriticalPath(
114
  "disable-sched-critical-path", cl::Hidden, cl::init(false),
115
  cl::desc("Disable critical path priority in sched=list-ilp"));
116
static cl::opt<bool> DisableSchedHeight(
117
  "disable-sched-height", cl::Hidden, cl::init(false),
118
  cl::desc("Disable scheduled-height priority in sched=list-ilp"));
119
static cl::opt<bool> Disable2AddrHack(
120
  "disable-2addr-hack", cl::Hidden, cl::init(true),
121
  cl::desc("Disable scheduler's two-address hack"));
122
123
static cl::opt<int> MaxReorderWindow(
124
  "max-sched-reorder", cl::Hidden, cl::init(6),
125
  cl::desc("Number of instructions to allow ahead of the critical path "
126
           "in sched=list-ilp"));
127
128
static cl::opt<unsigned> AvgIPC(
129
  "sched-avg-ipc", cl::Hidden, cl::init(1),
130
  cl::desc("Average inst/cycle whan no target itinerary exists."));
131
132
namespace {
133
134
//===----------------------------------------------------------------------===//
135
/// ScheduleDAGRRList - The actual register reduction list scheduler
136
/// implementation.  This supports both top-down and bottom-up scheduling.
137
///
138
class ScheduleDAGRRList : public ScheduleDAGSDNodes {
139
private:
140
  /// NeedLatency - True if the scheduler will make use of latency information.
141
  bool NeedLatency;
142
143
  /// AvailableQueue - The priority queue to use for the available SUnits.
144
  SchedulingPriorityQueue *AvailableQueue;
145
146
  /// PendingQueue - This contains all of the instructions whose operands have
147
  /// been issued, but their results are not ready yet (due to the latency of
148
  /// the operation).  Once the operands becomes available, the instruction is
149
  /// added to the AvailableQueue.
150
  std::vector<SUnit *> PendingQueue;
151
152
  /// HazardRec - The hazard recognizer to use.
153
  ScheduleHazardRecognizer *HazardRec;
154
155
  /// CurCycle - The current scheduler state corresponds to this cycle.
156
  unsigned CurCycle = 0;
157
158
  /// MinAvailableCycle - Cycle of the soonest available instruction.
159
  unsigned MinAvailableCycle;
160
161
  /// IssueCount - Count instructions issued in this cycle
162
  /// Currently valid only for bottom-up scheduling.
163
  unsigned IssueCount;
164
165
  /// LiveRegDefs - A set of physical registers and their definition
166
  /// that are "live". These nodes must be scheduled before any other nodes that
167
  /// modifies the registers can be scheduled.
168
  unsigned NumLiveRegs;
169
  std::unique_ptr<SUnit*[]> LiveRegDefs;
170
  std::unique_ptr<SUnit*[]> LiveRegGens;
171
172
  // Collect interferences between physical register use/defs.
173
  // Each interference is an SUnit and set of physical registers.
174
  SmallVector<SUnit*, 4> Interferences;
175
176
  using LRegsMapT = DenseMap<SUnit *, SmallVector<unsigned, 4>>;
177
178
  LRegsMapT LRegsMap;
179
180
  /// Topo - A topological ordering for SUnits which permits fast IsReachable
181
  /// and similar queries.
182
  ScheduleDAGTopologicalSort Topo;
183
184
  // Hack to keep track of the inverse of FindCallSeqStart without more crazy
185
  // DAG crawling.
186
  DenseMap<SUnit*, SUnit*> CallSeqEndForStart;
187
188
public:
189
  ScheduleDAGRRList(MachineFunction &mf, bool needlatency,
190
                    SchedulingPriorityQueue *availqueue,
191
                    CodeGenOpt::Level OptLevel)
192
    : ScheduleDAGSDNodes(mf),
193
      NeedLatency(needlatency), AvailableQueue(availqueue),
194
1.24M
      Topo(SUnits, nullptr) {
195
1.24M
    const TargetSubtargetInfo &STI = mf.getSubtarget();
196
1.24M
    if (DisableSchedCycles || 
!NeedLatency1.24M
)
197
1.16M
      HazardRec = new ScheduleHazardRecognizer();
198
84.6k
    else
199
84.6k
      HazardRec = STI.getInstrInfo()->CreateTargetHazardRecognizer(&STI, this);
200
1.24M
  }
201
202
1.24M
  ~ScheduleDAGRRList() override {
203
1.24M
    delete HazardRec;
204
1.24M
    delete AvailableQueue;
205
1.24M
  }
206
207
  void Schedule() override;
208
209
13.2M
  ScheduleHazardRecognizer *getHazardRec() { return HazardRec; }
210
211
  /// IsReachable - Checks if SU is reachable from TargetSU.
212
545
  bool IsReachable(const SUnit *SU, const SUnit *TargetSU) {
213
545
    return Topo.IsReachable(SU, TargetSU);
214
545
  }
215
216
  /// WillCreateCycle - Returns true if adding an edge from SU to TargetSU will
217
  /// create a cycle.
218
7.70k
  bool WillCreateCycle(SUnit *SU, SUnit *TargetSU) {
219
7.70k
    return Topo.WillCreateCycle(SU, TargetSU);
220
7.70k
  }
221
222
  /// AddPredQueued - Queues and update to add a predecessor edge to SUnit SU.
223
  /// This returns true if this is a new predecessor.
224
  /// Does *NOT* update the topological ordering! It just queues an update.
225
10.0k
  void AddPredQueued(SUnit *SU, const SDep &D) {
226
10.0k
    Topo.AddPredQueued(SU, D.getSUnit());
227
10.0k
    SU->addPred(D);
228
10.0k
  }
229
230
  /// AddPred - adds a predecessor edge to SUnit SU.
231
  /// This returns true if this is a new predecessor.
232
  /// Updates the topological ordering if required.
233
0
  void AddPred(SUnit *SU, const SDep &D) {
234
0
    Topo.AddPred(SU, D.getSUnit());
235
0
    SU->addPred(D);
236
0
  }
237
238
  /// RemovePred - removes a predecessor edge from SUnit SU.
239
  /// This returns true if an edge was removed.
240
  /// Updates the topological ordering if required.
241
3.30k
  void RemovePred(SUnit *SU, const SDep &D) {
242
3.30k
    Topo.RemovePred(SU, D.getSUnit());
243
3.30k
    SU->removePred(D);
244
3.30k
  }
245
246
private:
247
9.86M
  bool isReady(SUnit *SU) {
248
9.86M
    return DisableSchedCycles || 
!AvailableQueue->hasReadyFilter()9.86M
||
249
9.86M
      
AvailableQueue->isReady(SU)0
;
250
9.86M
  }
251
252
  void ReleasePred(SUnit *SU, const SDep *PredEdge);
253
  void ReleasePredecessors(SUnit *SU);
254
  void ReleasePending();
255
  void AdvanceToCycle(unsigned NextCycle);
256
  void AdvancePastStalls(SUnit *SU);
257
  void EmitNode(SUnit *SU);
258
  void ScheduleNodeBottomUp(SUnit*);
259
  void CapturePred(SDep *PredEdge);
260
  void UnscheduleNodeBottomUp(SUnit*);
261
  void RestoreHazardCheckerBottomUp();
262
  void BacktrackBottomUp(SUnit*, SUnit*);
263
  SUnit *TryUnfoldSU(SUnit *);
264
  SUnit *CopyAndMoveSuccessors(SUnit*);
265
  void InsertCopiesAndMoveSuccs(SUnit*, unsigned,
266
                                const TargetRegisterClass*,
267
                                const TargetRegisterClass*,
268
                                SmallVectorImpl<SUnit*>&);
269
  bool DelayForLiveRegsBottomUp(SUnit*, SmallVectorImpl<unsigned>&);
270
271
  void releaseInterferences(unsigned Reg = 0);
272
273
  SUnit *PickNodeToScheduleBottomUp();
274
  void ListScheduleBottomUp();
275
276
  /// CreateNewSUnit - Creates a new SUnit and returns a pointer to it.
277
1.38k
  SUnit *CreateNewSUnit(SDNode *N) {
278
1.38k
    unsigned NumSUnits = SUnits.size();
279
1.38k
    SUnit *NewNode = newSUnit(N);
280
1.38k
    // Update the topological ordering.
281
1.38k
    if (NewNode->NodeNum >= NumSUnits)
282
1.38k
      Topo.MarkDirty();
283
1.38k
    return NewNode;
284
1.38k
  }
285
286
  /// CreateClone - Creates a new SUnit from an existing one.
287
624
  SUnit *CreateClone(SUnit *N) {
288
624
    unsigned NumSUnits = SUnits.size();
289
624
    SUnit *NewNode = Clone(N);
290
624
    // Update the topological ordering.
291
624
    if (NewNode->NodeNum >= NumSUnits)
292
624
      Topo.MarkDirty();
293
624
    return NewNode;
294
624
  }
295
296
  /// forceUnitLatencies - Register-pressure-reducing scheduling doesn't
297
  /// need actual latency information but the hybrid scheduler does.
298
25.1M
  bool forceUnitLatencies() const override {
299
25.1M
    return !NeedLatency;
300
25.1M
  }
301
};
302
303
}  // end anonymous namespace
304
305
/// GetCostForDef - Looks up the register class and cost for a given definition.
306
/// Typically this just means looking up the representative register class,
307
/// but for untyped values (MVT::Untyped) it means inspecting the node's
308
/// opcode to determine what register class is being generated.
309
static void GetCostForDef(const ScheduleDAGSDNodes::RegDefIter &RegDefPos,
310
                          const TargetLowering *TLI,
311
                          const TargetInstrInfo *TII,
312
                          const TargetRegisterInfo *TRI,
313
                          unsigned &RegClass, unsigned &Cost,
314
1.47M
                          const MachineFunction &MF) {
315
1.47M
  MVT VT = RegDefPos.GetValue();
316
1.47M
317
1.47M
  // Special handling for untyped values.  These values can only come from
318
1.47M
  // the expansion of custom DAG-to-DAG patterns.
319
1.47M
  if (VT == MVT::Untyped) {
320
1.94k
    const SDNode *Node = RegDefPos.GetNode();
321
1.94k
322
1.94k
    // Special handling for CopyFromReg of untyped values.
323
1.94k
    if (!Node->isMachineOpcode() && 
Node->getOpcode() == ISD::CopyFromReg208
) {
324
208
      unsigned Reg = cast<RegisterSDNode>(Node->getOperand(1))->getReg();
325
208
      const TargetRegisterClass *RC = MF.getRegInfo().getRegClass(Reg);
326
208
      RegClass = RC->getID();
327
208
      Cost = 1;
328
208
      return;
329
208
    }
330
1.73k
331
1.73k
    unsigned Opcode = Node->getMachineOpcode();
332
1.73k
    if (Opcode == TargetOpcode::REG_SEQUENCE) {
333
261
      unsigned DstRCIdx = cast<ConstantSDNode>(Node->getOperand(0))->getZExtValue();
334
261
      const TargetRegisterClass *RC = TRI->getRegClass(DstRCIdx);
335
261
      RegClass = RC->getID();
336
261
      Cost = 1;
337
261
      return;
338
261
    }
339
1.47k
340
1.47k
    unsigned Idx = RegDefPos.GetIdx();
341
1.47k
    const MCInstrDesc Desc = TII->get(Opcode);
342
1.47k
    const TargetRegisterClass *RC = TII->getRegClass(Desc, Idx, TRI, MF);
343
1.47k
    RegClass = RC->getID();
344
1.47k
    // FIXME: Cost arbitrarily set to 1 because there doesn't seem to be a
345
1.47k
    // better way to determine it.
346
1.47k
    Cost = 1;
347
1.47M
  } else {
348
1.47M
    RegClass = TLI->getRepRegClassFor(VT)->getID();
349
1.47M
    Cost = TLI->getRepRegClassCostFor(VT);
350
1.47M
  }
351
1.47M
}
352
353
/// Schedule - Schedule the DAG using list scheduling.
354
1.24M
void ScheduleDAGRRList::Schedule() {
355
1.24M
  LLVM_DEBUG(dbgs() << "********** List Scheduling " << printMBBReference(*BB)
356
1.24M
                    << " '" << BB->getName() << "' **********\n");
357
1.24M
358
1.24M
  CurCycle = 0;
359
1.24M
  IssueCount = 0;
360
1.24M
  MinAvailableCycle =
361
1.24M
      DisableSchedCycles ? 
00
: std::numeric_limits<unsigned>::max();
362
1.24M
  NumLiveRegs = 0;
363
1.24M
  // Allocate slots for each physical register, plus one for a special register
364
1.24M
  // to track the virtual resource of a calling sequence.
365
1.24M
  LiveRegDefs.reset(new SUnit*[TRI->getNumRegs() + 1]());
366
1.24M
  LiveRegGens.reset(new SUnit*[TRI->getNumRegs() + 1]());
367
1.24M
  CallSeqEndForStart.clear();
368
1.24M
  assert(Interferences.empty() && LRegsMap.empty() && "stale Interferences");
369
1.24M
370
1.24M
  // Build the scheduling graph.
371
1.24M
  BuildSchedGraph(nullptr);
372
1.24M
373
1.24M
  LLVM_DEBUG(dump());
374
1.24M
  Topo.MarkDirty();
375
1.24M
376
1.24M
  AvailableQueue->initNodes(SUnits);
377
1.24M
378
1.24M
  HazardRec->Reset();
379
1.24M
380
1.24M
  // Execute the actual scheduling loop.
381
1.24M
  ListScheduleBottomUp();
382
1.24M
383
1.24M
  AvailableQueue->releaseState();
384
1.24M
385
1.24M
  LLVM_DEBUG({
386
1.24M
    dbgs() << "*** Final schedule ***\n";
387
1.24M
    dumpSchedule();
388
1.24M
    dbgs() << '\n';
389
1.24M
  });
390
1.24M
}
391
392
//===----------------------------------------------------------------------===//
393
//  Bottom-Up Scheduling
394
//===----------------------------------------------------------------------===//
395
396
/// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to
397
/// the AvailableQueue if the count reaches zero. Also update its cycle bound.
398
12.8M
void ScheduleDAGRRList::ReleasePred(SUnit *SU, const SDep *PredEdge) {
399
12.8M
  SUnit *PredSU = PredEdge->getSUnit();
400
12.8M
401
#ifndef NDEBUG
402
  if (PredSU->NumSuccsLeft == 0) {
403
    dbgs() << "*** Scheduling failed! ***\n";
404
    dumpNode(*PredSU);
405
    dbgs() << " has been released too many times!\n";
406
    llvm_unreachable(nullptr);
407
  }
408
#endif
409
  --PredSU->NumSuccsLeft;
410
12.8M
411
12.8M
  if (!forceUnitLatencies()) {
412
836k
    // Updating predecessor's height. This is now the cycle when the
413
836k
    // predecessor can be scheduled without causing a pipeline stall.
414
836k
    PredSU->setHeightToAtLeast(SU->getHeight() + PredEdge->getLatency());
415
836k
  }
416
12.8M
417
12.8M
  // If all the node's successors are scheduled, this node is ready
418
12.8M
  // to be scheduled. Ignore the special EntrySU node.
419
12.8M
  if (PredSU->NumSuccsLeft == 0 && 
PredSU != &EntrySU9.86M
) {
420
9.86M
    PredSU->isAvailable = true;
421
9.86M
422
9.86M
    unsigned Height = PredSU->getHeight();
423
9.86M
    if (Height < MinAvailableCycle)
424
4.24M
      MinAvailableCycle = Height;
425
9.86M
426
9.86M
    if (isReady(PredSU)) {
427
9.86M
      AvailableQueue->push(PredSU);
428
9.86M
    }
429
3
    // CapturePred and others may have left the node in the pending queue, avoid
430
3
    // adding it twice.
431
3
    else if (!PredSU->isPending) {
432
0
      PredSU->isPending = true;
433
0
      PendingQueue.push_back(PredSU);
434
0
    }
435
9.86M
  }
436
12.8M
}
437
438
/// IsChainDependent - Test if Outer is reachable from Inner through
439
/// chain dependencies.
440
static bool IsChainDependent(SDNode *Outer, SDNode *Inner,
441
                             unsigned NestLevel,
442
2.72k
                             const TargetInstrInfo *TII) {
443
2.72k
  SDNode *N = Outer;
444
5.52k
  while (true) {
445
5.52k
    if (N == Inner)
446
1
      return true;
447
5.52k
    // For a TokenFactor, examine each operand. There may be multiple ways
448
5.52k
    // to get to the CALLSEQ_BEGIN, but we need to find the path with the
449
5.52k
    // most nesting in order to ensure that we find the corresponding match.
450
5.52k
    if (N->getOpcode() == ISD::TokenFactor) {
451
426
      for (const SDValue &Op : N->op_values())
452
1.34k
        if (IsChainDependent(Op.getNode(), Inner, NestLevel, TII))
453
0
          return true;
454
426
      return false;
455
5.10k
    }
456
5.10k
    // Check for a lowered CALLSEQ_BEGIN or CALLSEQ_END.
457
5.10k
    if (N->isMachineOpcode()) {
458
4.18k
      if (N->getMachineOpcode() == TII->getCallFrameDestroyOpcode()) {
459
0
        ++NestLevel;
460
4.18k
      } else if (N->getMachineOpcode() == TII->getCallFrameSetupOpcode()) {
461
2.29k
        if (NestLevel == 0)
462
2.29k
          return false;
463
0
        --NestLevel;
464
0
      }
465
4.18k
    }
466
5.10k
    // Otherwise, find the chain and continue climbing.
467
5.10k
    
for (const SDValue &Op : N->op_values())2.80k
468
12.2k
      if (Op.getValueType() == MVT::Other) {
469
2.80k
        N = Op.getNode();
470
2.80k
        goto found_chain_operand;
471
2.80k
      }
472
2.80k
    
return false0
;
473
2.80k
  found_chain_operand:;
474
2.80k
    if (N->getOpcode() == ISD::EntryToken)
475
0
      return false;
476
2.80k
  }
477
2.72k
}
478
479
/// FindCallSeqStart - Starting from the (lowered) CALLSEQ_END node, locate
480
/// the corresponding (lowered) CALLSEQ_BEGIN node.
481
///
482
/// NestLevel and MaxNested are used in recursion to indcate the current level
483
/// of nesting of CALLSEQ_BEGIN and CALLSEQ_END pairs, as well as the maximum
484
/// level seen so far.
485
///
486
/// TODO: It would be better to give CALLSEQ_END an explicit operand to point
487
/// to the corresponding CALLSEQ_BEGIN to avoid needing to search for it.
488
static SDNode *
489
FindCallSeqStart(SDNode *N, unsigned &NestLevel, unsigned &MaxNest,
490
494k
                 const TargetInstrInfo *TII) {
491
2.14M
  while (true) {
492
2.14M
    // For a TokenFactor, examine each operand. There may be multiple ways
493
2.14M
    // to get to the CALLSEQ_BEGIN, but we need to find the path with the
494
2.14M
    // most nesting in order to ensure that we find the corresponding match.
495
2.14M
    if (N->getOpcode() == ISD::TokenFactor) {
496
28.3k
      SDNode *Best = nullptr;
497
28.3k
      unsigned BestMaxNest = MaxNest;
498
98.7k
      for (const SDValue &Op : N->op_values()) {
499
98.7k
        unsigned MyNestLevel = NestLevel;
500
98.7k
        unsigned MyMaxNest = MaxNest;
501
98.7k
        if (SDNode *New = FindCallSeqStart(Op.getNode(),
502
98.7k
                                           MyNestLevel, MyMaxNest, TII))
503
98.7k
          if (!Best || 
(MyMaxNest > BestMaxNest)70.4k
) {
504
28.3k
            Best = New;
505
28.3k
            BestMaxNest = MyMaxNest;
506
28.3k
          }
507
98.7k
      }
508
28.3k
      assert(Best);
509
28.3k
      MaxNest = BestMaxNest;
510
28.3k
      return Best;
511
28.3k
    }
512
2.11M
    // Check for a lowered CALLSEQ_BEGIN or CALLSEQ_END.
513
2.11M
    if (N->isMachineOpcode()) {
514
1.36M
      if (N->getMachineOpcode() == TII->getCallFrameDestroyOpcode()) {
515
395k
        ++NestLevel;
516
395k
        MaxNest = std::max(MaxNest, NestLevel);
517
968k
      } else if (N->getMachineOpcode() == TII->getCallFrameSetupOpcode()) {
518
466k
        assert(NestLevel != 0);
519
466k
        --NestLevel;
520
466k
        if (NestLevel == 0)
521
466k
          return N;
522
1.65M
      }
523
1.36M
    }
524
1.65M
    // Otherwise, find the chain and continue climbing.
525
1.65M
    for (const SDValue &Op : N->op_values())
526
4.75M
      if (Op.getValueType() == MVT::Other) {
527
1.65M
        N = Op.getNode();
528
1.65M
        goto found_chain_operand;
529
1.65M
      }
530
1.65M
    
return nullptr0
;
531
1.65M
  found_chain_operand:;
532
1.65M
    if (N->getOpcode() == ISD::EntryToken)
533
37
      return nullptr;
534
1.65M
  }
535
494k
}
536
537
/// Call ReleasePred for each predecessor, then update register live def/gen.
538
/// Always update LiveRegDefs for a register dependence even if the current SU
539
/// also defines the register. This effectively create one large live range
540
/// across a sequence of two-address node. This is important because the
541
/// entire chain must be scheduled together. Example:
542
///
543
/// flags = (3) add
544
/// flags = (2) addc flags
545
/// flags = (1) addc flags
546
///
547
/// results in
548
///
549
/// LiveRegDefs[flags] = 3
550
/// LiveRegGens[flags] = 1
551
///
552
/// If (2) addc is unscheduled, then (1) addc must also be unscheduled to avoid
553
/// interference on flags.
554
12.3M
void ScheduleDAGRRList::ReleasePredecessors(SUnit *SU) {
555
12.3M
  // Bottom up: release predecessors
556
12.8M
  for (SDep &Pred : SU->Preds) {
557
12.8M
    ReleasePred(SU, &Pred);
558
12.8M
    if (Pred.isAssignedRegDep()) {
559
412k
      // This is a physical register dependency and it's impossible or
560
412k
      // expensive to copy the register. Make sure nothing that can
561
412k
      // clobber the register is scheduled between the predecessor and
562
412k
      // this node.
563
412k
      SUnit *RegDef = LiveRegDefs[Pred.getReg()]; (void)RegDef;
564
412k
      assert((!RegDef || RegDef == SU || RegDef == Pred.getSUnit()) &&
565
412k
             "interference on register dependence");
566
412k
      LiveRegDefs[Pred.getReg()] = Pred.getSUnit();
567
412k
      if (!LiveRegGens[Pred.getReg()]) {
568
353k
        ++NumLiveRegs;
569
353k
        LiveRegGens[Pred.getReg()] = SU;
570
353k
      }
571
412k
    }
572
12.8M
  }
573
12.3M
574
12.3M
  // If we're scheduling a lowered CALLSEQ_END, find the corresponding
575
12.3M
  // CALLSEQ_BEGIN. Inject an artificial physical register dependence between
576
12.3M
  // these nodes, to prevent other calls from being interscheduled with them.
577
12.3M
  unsigned CallResource = TRI->getNumRegs();
578
12.3M
  if (!LiveRegDefs[CallResource])
579
21.9M
    
for (SDNode *Node = SU->getNode(); 11.1M
Node;
Node = Node->getGluedNode()10.7M
)
580
11.1M
      if (Node->isMachineOpcode() &&
581
11.1M
          
Node->getMachineOpcode() == TII->getCallFrameDestroyOpcode()6.94M
) {
582
395k
        unsigned NestLevel = 0;
583
395k
        unsigned MaxNest = 0;
584
395k
        SDNode *N = FindCallSeqStart(Node, NestLevel, MaxNest, TII);
585
395k
        assert(N && "Must find call sequence start");
586
395k
587
395k
        SUnit *Def = &SUnits[N->getNodeId()];
588
395k
        CallSeqEndForStart[Def] = SU;
589
395k
590
395k
        ++NumLiveRegs;
591
395k
        LiveRegDefs[CallResource] = Def;
592
395k
        LiveRegGens[CallResource] = SU;
593
395k
        break;
594
395k
      }
595
12.3M
}
596
597
/// Check to see if any of the pending instructions are ready to issue.  If
598
/// so, add them to the available queue.
599
10.8M
void ScheduleDAGRRList::ReleasePending() {
600
10.8M
  if (DisableSchedCycles) {
601
0
    assert(PendingQueue.empty() && "pending instrs not allowed in this mode");
602
0
    return;
603
0
  }
604
10.8M
605
10.8M
  // If the available queue is empty, it is safe to reset MinAvailableCycle.
606
10.8M
  if (AvailableQueue->empty())
607
5.33M
    MinAvailableCycle = std::numeric_limits<unsigned>::max();
608
10.8M
609
10.8M
  // Check to see if any of the pending instructions are ready to issue.  If
610
10.8M
  // so, add them to the available queue.
611
10.8M
  for (unsigned i = 0, e = PendingQueue.size(); i != e; 
++i0
) {
612
0
    unsigned ReadyCycle = PendingQueue[i]->getHeight();
613
0
    if (ReadyCycle < MinAvailableCycle)
614
0
      MinAvailableCycle = ReadyCycle;
615
0
616
0
    if (PendingQueue[i]->isAvailable) {
617
0
      if (!isReady(PendingQueue[i]))
618
0
          continue;
619
0
      AvailableQueue->push(PendingQueue[i]);
620
0
    }
621
0
    PendingQueue[i]->isPending = false;
622
0
    PendingQueue[i] = PendingQueue.back();
623
0
    PendingQueue.pop_back();
624
0
    --i; --e;
625
0
  }
626
10.8M
}
627
628
/// Move the scheduler state forward by the specified number of Cycles.
629
32.3M
void ScheduleDAGRRList::AdvanceToCycle(unsigned NextCycle) {
630
32.3M
  if (NextCycle <= CurCycle)
631
21.4M
    return;
632
10.8M
633
10.8M
  IssueCount = 0;
634
10.8M
  AvailableQueue->setCurCycle(NextCycle);
635
10.8M
  if (!HazardRec->isEnabled()) {
636
10.5M
    // Bypass lots of virtual calls in case of long latency.
637
10.5M
    CurCycle = NextCycle;
638
10.5M
  }
639
332k
  else {
640
772k
    for (; CurCycle != NextCycle; 
++CurCycle440k
) {
641
440k
      HazardRec->RecedeCycle();
642
440k
    }
643
332k
  }
644
10.8M
  // FIXME: Instead of visiting the pending Q each time, set a dirty flag on the
645
10.8M
  // available Q to release pending nodes at least once before popping.
646
10.8M
  ReleasePending();
647
10.8M
}
648
649
/// Move the scheduler state forward until the specified node's dependents are
650
/// ready and can be scheduled with no resource conflicts.
651
11.0M
void ScheduleDAGRRList::AdvancePastStalls(SUnit *SU) {
652
11.0M
  if (DisableSchedCycles)
653
0
    return;
654
11.0M
655
11.0M
  // FIXME: Nodes such as CopyFromReg probably should not advance the current
656
11.0M
  // cycle. Otherwise, we can wrongly mask real stalls. If the non-machine node
657
11.0M
  // has predecessors the cycle will be advanced when they are scheduled.
658
11.0M
  // But given the crude nature of modeling latency though such nodes, we
659
11.0M
  // currently need to treat these nodes like real instructions.
660
11.0M
  // if (!SU->getNode() || !SU->getNode()->isMachineOpcode()) return;
661
11.0M
662
11.0M
  unsigned ReadyCycle = SU->getHeight();
663
11.0M
664
11.0M
  // Bump CurCycle to account for latency. We assume the latency of other
665
11.0M
  // available instructions may be hidden by the stall (not a full pipe stall).
666
11.0M
  // This updates the hazard recognizer's cycle before reserving resources for
667
11.0M
  // this instruction.
668
11.0M
  AdvanceToCycle(ReadyCycle);
669
11.0M
670
11.0M
  // Calls are scheduled in their preceding cycle, so don't conflict with
671
11.0M
  // hazards from instructions after the call. EmitNode will reset the
672
11.0M
  // scoreboard state before emitting the call.
673
11.0M
  if (SU->isCall)
674
394k
    return;
675
10.6M
676
10.6M
  // FIXME: For resource conflicts in very long non-pipelined stages, we
677
10.6M
  // should probably skip ahead here to avoid useless scoreboard checks.
678
10.6M
  int Stalls = 0;
679
10.7M
  while (
true10.7M
) {
680
10.7M
    ScheduleHazardRecognizer::HazardType HT =
681
10.7M
      HazardRec->getHazardType(SU, -Stalls);
682
10.7M
683
10.7M
    if (HT == ScheduleHazardRecognizer::NoHazard)
684
10.6M
      break;
685
33.9k
686
33.9k
    ++Stalls;
687
33.9k
  }
688
10.6M
  AdvanceToCycle(CurCycle + Stalls);
689
10.6M
}
690
691
/// Record this SUnit in the HazardRecognizer.
692
/// Does not update CurCycle.
693
11.0M
void ScheduleDAGRRList::EmitNode(SUnit *SU) {
694
11.0M
  if (!HazardRec->isEnabled())
695
10.5M
    return;
696
552k
697
552k
  // Check for phys reg copy.
698
552k
  if (!SU->getNode())
699
2
    return;
700
552k
701
552k
  switch (SU->getNode()->getOpcode()) {
702
552k
  default:
703
353k
    assert(SU->getNode()->isMachineOpcode() &&
704
353k
           "This target-independent node should not be scheduled.");
705
353k
    break;
706
552k
  case ISD::MERGE_VALUES:
707
198k
  case ISD::TokenFactor:
708
198k
  case ISD::LIFETIME_START:
709
198k
  case ISD::LIFETIME_END:
710
198k
  case ISD::CopyToReg:
711
198k
  case ISD::CopyFromReg:
712
198k
  case ISD::EH_LABEL:
713
198k
    // Noops don't affect the scoreboard state. Copies are likely to be
714
198k
    // removed.
715
198k
    return;
716
198k
  case ISD::INLINEASM:
717
1.10k
  case ISD::INLINEASM_BR:
718
1.10k
    // For inline asm, clear the pipeline state.
719
1.10k
    HazardRec->Reset();
720
1.10k
    return;
721
353k
  }
722
353k
  if (SU->isCall) {
723
15.1k
    // Calls are scheduled with their preceding instructions. For bottom-up
724
15.1k
    // scheduling, clear the pipeline state before emitting.
725
15.1k
    HazardRec->Reset();
726
15.1k
  }
727
353k
728
353k
  HazardRec->EmitInstruction(SU);
729
353k
}
730
731
static void resetVRegCycle(SUnit *SU);
732
733
/// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending
734
/// count of its predecessors. If a predecessor pending count is zero, add it to
735
/// the Available queue.
736
11.0M
void ScheduleDAGRRList::ScheduleNodeBottomUp(SUnit *SU) {
737
11.0M
  LLVM_DEBUG(dbgs() << "\n*** Scheduling [" << CurCycle << "]: ");
738
11.0M
  LLVM_DEBUG(dumpNode(*SU));
739
11.0M
740
#ifndef NDEBUG
741
  if (CurCycle < SU->getHeight())
742
    LLVM_DEBUG(dbgs() << "   Height [" << SU->getHeight()
743
                      << "] pipeline stall!\n");
744
#endif
745
746
11.0M
  // FIXME: Do not modify node height. It may interfere with
747
11.0M
  // backtracking. Instead add a "ready cycle" to SUnit. Before scheduling the
748
11.0M
  // node its ready cycle can aid heuristics, and after scheduling it can
749
11.0M
  // indicate the scheduled cycle.
750
11.0M
  SU->setHeightToAtLeast(CurCycle);
751
11.0M
752
11.0M
  // Reserve resources for the scheduled instruction.
753
11.0M
  EmitNode(SU);
754
11.0M
755
11.0M
  Sequence.push_back(SU);
756
11.0M
757
11.0M
  AvailableQueue->scheduledNode(SU);
758
11.0M
759
11.0M
  // If HazardRec is disabled, and each inst counts as one cycle, then
760
11.0M
  // advance CurCycle before ReleasePredecessors to avoid useless pushes to
761
11.0M
  // PendingQueue for schedulers that implement HasReadyFilter.
762
11.0M
  if (!HazardRec->isEnabled() && 
AvgIPC < 210.5M
)
763
10.5M
    AdvanceToCycle(CurCycle + 1);
764
11.0M
765
11.0M
  // Update liveness of predecessors before successors to avoid treating a
766
11.0M
  // two-address node as a live range def.
767
11.0M
  ReleasePredecessors(SU);
768
11.0M
769
11.0M
  // Release all the implicit physical register defs that are live.
770
13.1M
  for (SDep &Succ : SU->Succs) {
771
13.1M
    // LiveRegDegs[Succ.getReg()] != SU when SU is a two-address node.
772
13.1M
    if (Succ.isAssignedRegDep() && 
LiveRegDefs[Succ.getReg()] == SU358k
) {
773
350k
      assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");
774
350k
      --NumLiveRegs;
775
350k
      LiveRegDefs[Succ.getReg()] = nullptr;
776
350k
      LiveRegGens[Succ.getReg()] = nullptr;
777
350k
      releaseInterferences(Succ.getReg());
778
350k
    }
779
13.1M
  }
780
11.0M
  // Release the special call resource dependence, if this is the beginning
781
11.0M
  // of a call.
782
11.0M
  unsigned CallResource = TRI->getNumRegs();
783
11.0M
  if (LiveRegDefs[CallResource] == SU)
784
794k
    
for (const SDNode *SUNode = SU->getNode(); 395k
SUNode;
785
399k
         SUNode = SUNode->getGluedNode()) {
786
399k
      if (SUNode->isMachineOpcode() &&
787
399k
          
SUNode->getMachineOpcode() == TII->getCallFrameSetupOpcode()397k
) {
788
395k
        assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");
789
395k
        --NumLiveRegs;
790
395k
        LiveRegDefs[CallResource] = nullptr;
791
395k
        LiveRegGens[CallResource] = nullptr;
792
395k
        releaseInterferences(CallResource);
793
395k
      }
794
399k
    }
795
11.0M
796
11.0M
  resetVRegCycle(SU);
797
11.0M
798
11.0M
  SU->isScheduled = true;
799
11.0M
800
11.0M
  // Conditions under which the scheduler should eagerly advance the cycle:
801
11.0M
  // (1) No available instructions
802
11.0M
  // (2) All pipelines full, so available instructions must have hazards.
803
11.0M
  //
804
11.0M
  // If HazardRec is disabled, the cycle was pre-advanced before calling
805
11.0M
  // ReleasePredecessors. In that case, IssueCount should remain 0.
806
11.0M
  //
807
11.0M
  // Check AvailableQueue after ReleasePredecessors in case of zero latency.
808
11.0M
  if (HazardRec->isEnabled() || 
AvgIPC > 110.5M
) {
809
552k
    if (SU->getNode() && 
SU->getNode()->isMachineOpcode()552k
)
810
352k
      ++IssueCount;
811
552k
    if ((HazardRec->isEnabled() && HazardRec->atIssueLimit())
812
552k
        || 
(508k
!HazardRec->isEnabled()508k
&&
IssueCount == AvgIPC0
))
813
43.9k
      AdvanceToCycle(CurCycle + 1);
814
552k
  }
815
11.0M
}
816
817
/// CapturePred - This does the opposite of ReleasePred. Since SU is being
818
/// unscheduled, increase the succ left count of its predecessors. Remove
819
/// them from AvailableQueue if necessary.
820
176k
void ScheduleDAGRRList::CapturePred(SDep *PredEdge) {
821
176k
  SUnit *PredSU = PredEdge->getSUnit();
822
176k
  if (PredSU->isAvailable) {
823
59.4k
    PredSU->isAvailable = false;
824
59.4k
    if (!PredSU->isPending)
825
3.70k
      AvailableQueue->remove(PredSU);
826
59.4k
  }
827
176k
828
176k
  assert(PredSU->NumSuccsLeft < std::numeric_limits<unsigned>::max() &&
829
176k
         "NumSuccsLeft will overflow!");
830
176k
  ++PredSU->NumSuccsLeft;
831
176k
}
832
833
/// UnscheduleNodeBottomUp - Remove the node from the schedule, update its and
834
/// its predecessor states to reflect the change.
835
68.4k
void ScheduleDAGRRList::UnscheduleNodeBottomUp(SUnit *SU) {
836
68.4k
  LLVM_DEBUG(dbgs() << "*** Unscheduling [" << SU->getHeight() << "]: ");
837
68.4k
  LLVM_DEBUG(dumpNode(*SU));
838
68.4k
839
176k
  for (SDep &Pred : SU->Preds) {
840
176k
    CapturePred(&Pred);
841
176k
    if (Pred.isAssignedRegDep() && 
SU == LiveRegGens[Pred.getReg()]54.8k
){
842
3.61k
      assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");
843
3.61k
      assert(LiveRegDefs[Pred.getReg()] == Pred.getSUnit() &&
844
3.61k
             "Physical register dependency violated?");
845
3.61k
      --NumLiveRegs;
846
3.61k
      LiveRegDefs[Pred.getReg()] = nullptr;
847
3.61k
      LiveRegGens[Pred.getReg()] = nullptr;
848
3.61k
      releaseInterferences(Pred.getReg());
849
3.61k
    }
850
176k
  }
851
68.4k
852
68.4k
  // Reclaim the special call resource dependence, if this is the beginning
853
68.4k
  // of a call.
854
68.4k
  unsigned CallResource = TRI->getNumRegs();
855
191k
  for (const SDNode *SUNode = SU->getNode(); SUNode;
856
123k
       SUNode = SUNode->getGluedNode()) {
857
123k
    if (SUNode->isMachineOpcode() &&
858
123k
        
SUNode->getMachineOpcode() == TII->getCallFrameSetupOpcode()67.0k
) {
859
36
      SUnit *SeqEnd = CallSeqEndForStart[SU];
860
36
      assert(SeqEnd && "Call sequence start/end must be known");
861
36
      assert(!LiveRegDefs[CallResource]);
862
36
      assert(!LiveRegGens[CallResource]);
863
36
      ++NumLiveRegs;
864
36
      LiveRegDefs[CallResource] = SU;
865
36
      LiveRegGens[CallResource] = SeqEnd;
866
36
    }
867
123k
  }
868
68.4k
869
68.4k
  // Release the special call resource dependence, if this is the end
870
68.4k
  // of a call.
871
68.4k
  if (LiveRegGens[CallResource] == SU)
872
0
    for (const SDNode *SUNode = SU->getNode(); SUNode;
873
0
         SUNode = SUNode->getGluedNode()) {
874
0
      if (SUNode->isMachineOpcode() &&
875
0
          SUNode->getMachineOpcode() == TII->getCallFrameDestroyOpcode()) {
876
0
        assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");
877
0
        assert(LiveRegDefs[CallResource]);
878
0
        assert(LiveRegGens[CallResource]);
879
0
        --NumLiveRegs;
880
0
        LiveRegDefs[CallResource] = nullptr;
881
0
        LiveRegGens[CallResource] = nullptr;
882
0
        releaseInterferences(CallResource);
883
0
      }
884
0
    }
885
68.4k
886
523k
  for (auto &Succ : SU->Succs) {
887
523k
    if (Succ.isAssignedRegDep()) {
888
565
      auto Reg = Succ.getReg();
889
565
      if (!LiveRegDefs[Reg])
890
0
        ++NumLiveRegs;
891
565
      // This becomes the nearest def. Note that an earlier def may still be
892
565
      // pending if this is a two-address node.
893
565
      LiveRegDefs[Reg] = SU;
894
565
895
565
      // Update LiveRegGen only if was empty before this unscheduling.
896
565
      // This is to avoid incorrect updating LiveRegGen set in previous run.
897
565
      if (!LiveRegGens[Reg]) {
898
0
        // Find the successor with the lowest height.
899
0
        LiveRegGens[Reg] = Succ.getSUnit();
900
0
        for (auto &Succ2 : SU->Succs) {
901
0
          if (Succ2.isAssignedRegDep() && Succ2.getReg() == Reg &&
902
0
              Succ2.getSUnit()->getHeight() < LiveRegGens[Reg]->getHeight())
903
0
            LiveRegGens[Reg] = Succ2.getSUnit();
904
0
        }
905
0
      }
906
565
    }
907
523k
  }
908
68.4k
  if (SU->getHeight() < MinAvailableCycle)
909
65.9k
    MinAvailableCycle = SU->getHeight();
910
68.4k
911
68.4k
  SU->setHeightDirty();
912
68.4k
  SU->isScheduled = false;
913
68.4k
  SU->isAvailable = true;
914
68.4k
  if (!DisableSchedCycles && AvailableQueue->hasReadyFilter()) {
915
0
    // Don't make available until backtracking is complete.
916
0
    SU->isPending = true;
917
0
    PendingQueue.push_back(SU);
918
0
  }
919
68.4k
  else {
920
68.4k
    AvailableQueue->push(SU);
921
68.4k
  }
922
68.4k
  AvailableQueue->unscheduledNode(SU);
923
68.4k
}
924
925
/// After backtracking, the hazard checker needs to be restored to a state
926
/// corresponding the current cycle.
927
3.61k
void ScheduleDAGRRList::RestoreHazardCheckerBottomUp() {
928
3.61k
  HazardRec->Reset();
929
3.61k
930
3.61k
  unsigned LookAhead = std::min((unsigned)Sequence.size(),
931
3.61k
                                HazardRec->getMaxLookAhead());
932
3.61k
  if (LookAhead == 0)
933
3.59k
    return;
934
28
935
28
  std::vector<SUnit *>::const_iterator I = (Sequence.end() - LookAhead);
936
28
  unsigned HazardCycle = (*I)->getHeight();
937
421
  for (auto E = Sequence.end(); I != E; 
++I393
) {
938
393
    SUnit *SU = *I;
939
624
    for (; SU->getHeight() > HazardCycle; 
++HazardCycle231
) {
940
231
      HazardRec->RecedeCycle();
941
231
    }
942
393
    EmitNode(SU);
943
393
  }
944
28
}
945
946
/// BacktrackBottomUp - Backtrack scheduling to a previous cycle specified in
947
/// BTCycle in order to schedule a specific node.
948
3.61k
void ScheduleDAGRRList::BacktrackBottomUp(SUnit *SU, SUnit *BtSU) {
949
3.61k
  SUnit *OldSU = Sequence.back();
950
68.4k
  while (true) {
951
68.4k
    Sequence.pop_back();
952
68.4k
    // FIXME: use ready cycle instead of height
953
68.4k
    CurCycle = OldSU->getHeight();
954
68.4k
    UnscheduleNodeBottomUp(OldSU);
955
68.4k
    AvailableQueue->setCurCycle(CurCycle);
956
68.4k
    if (OldSU == BtSU)
957
3.61k
      break;
958
64.7k
    OldSU = Sequence.back();
959
64.7k
  }
960
3.61k
961
3.61k
  assert(!SU->isSucc(OldSU) && "Something is wrong!");
962
3.61k
963
3.61k
  RestoreHazardCheckerBottomUp();
964
3.61k
965
3.61k
  ReleasePending();
966
3.61k
967
3.61k
  ++NumBacktracks;
968
3.61k
}
969
970
614
static bool isOperandOf(const SUnit *SU, SDNode *N) {
971
683
  for (const SDNode *SUNode = SU->getNode(); SUNode;
972
624
       
SUNode = SUNode->getGluedNode()69
) {
973
624
    if (SUNode->isOperandOf(N))
974
555
      return true;
975
624
  }
976
614
  
return false59
;
977
614
}
978
979
/// TryUnfold - Attempt to unfold
980
649
SUnit *ScheduleDAGRRList::TryUnfoldSU(SUnit *SU) {
981
649
  SDNode *N = SU->getNode();
982
649
  // Use while over if to ease fall through.
983
649
  SmallVector<SDNode *, 2> NewNodes;
984
649
  if (!TII->unfoldMemoryOperand(*DAG, N, NewNodes))
985
0
    return nullptr;
986
649
987
649
  // unfolding an x86 DEC64m operation results in store, dec, load which
988
649
  // can't be handled here so quit
989
649
  if (NewNodes.size() == 3)
990
9
    return nullptr;
991
640
992
640
  assert(NewNodes.size() == 2 && "Expected a load folding node!");
993
640
994
640
  N = NewNodes[1];
995
640
  SDNode *LoadNode = NewNodes[0];
996
640
  unsigned NumVals = N->getNumValues();
997
640
  unsigned OldNumVals = SU->getNode()->getNumValues();
998
640
999
640
  // LoadNode may already exist. This can happen when there is another
1000
640
  // load from the same location and producing the same type of value
1001
640
  // but it has different alignment or volatileness.
1002
640
  bool isNewLoad = true;
1003
640
  SUnit *LoadSU;
1004
640
  if (LoadNode->getNodeId() != -1) {
1005
2
    LoadSU = &SUnits[LoadNode->getNodeId()];
1006
2
    // If LoadSU has already been scheduled, we should clone it but
1007
2
    // this would negate the benefit to unfolding so just return SU.
1008
2
    if (LoadSU->isScheduled)
1009
1
      return SU;
1010
1
    isNewLoad = false;
1011
638
  } else {
1012
638
    LoadSU = CreateNewSUnit(LoadNode);
1013
638
    LoadNode->setNodeId(LoadSU->NodeNum);
1014
638
1015
638
    InitNumRegDefsLeft(LoadSU);
1016
638
    computeLatency(LoadSU);
1017
638
  }
1018
640
1019
640
  bool isNewN = true;
1020
639
  SUnit *NewSU;
1021
639
  // This can only happen when isNewLoad is false.
1022
639
  if (N->getNodeId() != -1) {
1023
1
    NewSU = &SUnits[N->getNodeId()];
1024
1
    // If NewSU has already been scheduled, we need to clone it, but this
1025
1
    // negates the benefit to unfolding so just return SU.
1026
1
    if (NewSU->isScheduled) {
1027
0
      return SU;
1028
0
    }
1029
1
    isNewN = false;
1030
638
  } else {
1031
638
    NewSU = CreateNewSUnit(N);
1032
638
    N->setNodeId(NewSU->NodeNum);
1033
638
1034
638
    const MCInstrDesc &MCID = TII->get(N->getMachineOpcode());
1035
1.85k
    for (unsigned i = 0; i != MCID.getNumOperands(); 
++i1.21k
) {
1036
1.27k
      if (MCID.getOperandConstraint(i, MCOI::TIED_TO) != -1) {
1037
58
        NewSU->isTwoAddress = true;
1038
58
        break;
1039
58
      }
1040
1.27k
    }
1041
638
    if (MCID.isCommutable())
1042
603
      NewSU->isCommutable = true;
1043
638
1044
638
    InitNumRegDefsLeft(NewSU);
1045
638
    computeLatency(NewSU);
1046
638
  }
1047
639
1048
639
  LLVM_DEBUG(dbgs() << "Unfolding SU #" << SU->NodeNum << "\n");
1049
639
1050
639
  // Now that we are committed to unfolding replace DAG Uses.
1051
1.33k
  for (unsigned i = 0; i != NumVals; 
++i698
)
1052
698
    DAG->ReplaceAllUsesOfValueWith(SDValue(SU->getNode(), i), SDValue(N, i));
1053
639
  DAG->ReplaceAllUsesOfValueWith(SDValue(SU->getNode(), OldNumVals - 1),
1054
639
                                 SDValue(LoadNode, 1));
1055
639
1056
639
  // Record all the edges to and from the old SU, by category.
1057
639
  SmallVector<SDep, 4> ChainPreds;
1058
639
  SmallVector<SDep, 4> ChainSuccs;
1059
639
  SmallVector<SDep, 4> LoadPreds;
1060
639
  SmallVector<SDep, 4> NodePreds;
1061
639
  SmallVector<SDep, 4> NodeSuccs;
1062
817
  for (SDep &Pred : SU->Preds) {
1063
817
    if (Pred.isCtrl())
1064
203
      ChainPreds.push_back(Pred);
1065
614
    else if (isOperandOf(Pred.getSUnit(), LoadNode))
1066
555
      LoadPreds.push_back(Pred);
1067
59
    else
1068
59
      NodePreds.push_back(Pred);
1069
817
  }
1070
1.34k
  for (SDep &Succ : SU->Succs) {
1071
1.34k
    if (Succ.isCtrl())
1072
622
      ChainSuccs.push_back(Succ);
1073
722
    else
1074
722
      NodeSuccs.push_back(Succ);
1075
1.34k
  }
1076
639
1077
639
  // Now assign edges to the newly-created nodes.
1078
639
  for (const SDep &Pred : ChainPreds) {
1079
203
    RemovePred(SU, Pred);
1080
203
    if (isNewLoad)
1081
203
      AddPredQueued(LoadSU, Pred);
1082
203
  }
1083
639
  for (const SDep &Pred : LoadPreds) {
1084
555
    RemovePred(SU, Pred);
1085
555
    if (isNewLoad)
1086
555
      AddPredQueued(LoadSU, Pred);
1087
555
  }
1088
639
  for (const SDep &Pred : NodePreds) {
1089
59
    RemovePred(SU, Pred);
1090
59
    AddPredQueued(NewSU, Pred);
1091
59
  }
1092
722
  for (SDep D : NodeSuccs) {
1093
722
    SUnit *SuccDep = D.getSUnit();
1094
722
    D.setSUnit(SU);
1095
722
    RemovePred(SuccDep, D);
1096
722
    D.setSUnit(NewSU);
1097
722
    AddPredQueued(SuccDep, D);
1098
722
    // Balance register pressure.
1099
722
    if (AvailableQueue->tracksRegPressure() && 
SuccDep->isScheduled0
&&
1100
722
        
!D.isCtrl()0
&&
NewSU->NumRegDefsLeft > 00
)
1101
0
      --NewSU->NumRegDefsLeft;
1102
722
  }
1103
639
  for (SDep D : ChainSuccs) {
1104
622
    SUnit *SuccDep = D.getSUnit();
1105
622
    D.setSUnit(SU);
1106
622
    RemovePred(SuccDep, D);
1107
622
    if (isNewLoad) {
1108
622
      D.setSUnit(LoadSU);
1109
622
      AddPredQueued(SuccDep, D);
1110
622
    }
1111
622
  }
1112
639
1113
639
  // Add a data dependency to reflect that NewSU reads the value defined
1114
639
  // by LoadSU.
1115
639
  SDep D(LoadSU, SDep::Data, 0);
1116
639
  D.setLatency(LoadSU->Latency);
1117
639
  AddPredQueued(NewSU, D);
1118
639
1119
639
  if (isNewLoad)
1120
638
    AvailableQueue->addNode(LoadSU);
1121
639
  if (isNewN)
1122
638
    AvailableQueue->addNode(NewSU);
1123
639
1124
639
  ++NumUnfolds;
1125
639
1126
639
  if (NewSU->NumSuccsLeft == 0)
1127
597
    NewSU->isAvailable = true;
1128
639
1129
639
  return NewSU;
1130
639
}
1131
1132
/// CopyAndMoveSuccessors - Clone the specified node and move its scheduled
1133
/// successors to the newly created node.
1134
1.27k
SUnit *ScheduleDAGRRList::CopyAndMoveSuccessors(SUnit *SU) {
1135
1.27k
  SDNode *N = SU->getNode();
1136
1.27k
  if (!N)
1137
0
    return nullptr;
1138
1.27k
1139
1.27k
  LLVM_DEBUG(dbgs() << "Considering duplicating the SU\n");
1140
1.27k
  LLVM_DEBUG(dumpNode(*SU));
1141
1.27k
1142
1.27k
  if (N->getGluedNode() &&
1143
1.27k
      
!TII->canCopyGluedNodeDuringSchedule(N)47
) {
1144
45
    LLVM_DEBUG(
1145
45
        dbgs()
1146
45
        << "Giving up because it has incoming glue and the target does not "
1147
45
           "want to copy it\n");
1148
45
    return nullptr;
1149
45
  }
1150
1.23k
1151
1.23k
  SUnit *NewSU;
1152
1.23k
  bool TryUnfold = false;
1153
3.44k
  for (unsigned i = 0, e = N->getNumValues(); i != e; 
++i2.21k
) {
1154
2.21k
    MVT VT = N->getSimpleValueType(i);
1155
2.21k
    if (VT == MVT::Glue) {
1156
0
      LLVM_DEBUG(dbgs() << "Giving up because it has outgoing glue\n");
1157
0
      return nullptr;
1158
2.21k
    } else if (VT == MVT::Other)
1159
649
      TryUnfold = true;
1160
2.21k
  }
1161
5.71k
  
for (const SDValue &Op : N->op_values())1.23k
{
1162
5.71k
    MVT VT = Op.getNode()->getSimpleValueType(Op.getResNo());
1163
5.71k
    if (VT == MVT::Glue && 
!TII->canCopyGluedNodeDuringSchedule(N)2
) {
1164
0
      LLVM_DEBUG(
1165
0
          dbgs() << "Giving up because it one of the operands is glue and "
1166
0
                    "the target does not want to copy it\n");
1167
0
      return nullptr;
1168
0
    }
1169
5.71k
  }
1170
1.23k
1171
1.23k
  // If possible unfold instruction.
1172
1.23k
  if (TryUnfold) {
1173
649
    SUnit *UnfoldSU = TryUnfoldSU(SU);
1174
649
    if (!UnfoldSU)
1175
9
      return nullptr;
1176
640
    SU = UnfoldSU;
1177
640
    N = SU->getNode();
1178
640
    // If this can be scheduled don't bother duplicating and just return
1179
640
    if (SU->NumSuccsLeft == 0)
1180
597
      return SU;
1181
624
  }
1182
624
1183
624
  LLVM_DEBUG(dbgs() << "    Duplicating SU #" << SU->NodeNum << "\n");
1184
624
  NewSU = CreateClone(SU);
1185
624
1186
624
  // New SUnit has the exact same predecessors.
1187
624
  for (SDep &Pred : SU->Preds)
1188
822
    if (!Pred.isArtificial())
1189
822
      AddPredQueued(NewSU, Pred);
1190
624
1191
624
  // Only copy scheduled successors. Cut them from old node's successor
1192
624
  // list and move them over.
1193
624
  SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps;
1194
2.45k
  for (SDep &Succ : SU->Succs) {
1195
2.45k
    if (Succ.isArtificial())
1196
0
      continue;
1197
2.45k
    SUnit *SuccSU = Succ.getSUnit();
1198
2.45k
    if (SuccSU->isScheduled) {
1199
913
      SDep D = Succ;
1200
913
      D.setSUnit(NewSU);
1201
913
      AddPredQueued(SuccSU, D);
1202
913
      D.setSUnit(SU);
1203
913
      DelDeps.push_back(std::make_pair(SuccSU, D));
1204
913
    }
1205
2.45k
  }
1206
624
  for (auto &DelDep : DelDeps)
1207
913
    RemovePred(DelDep.first, DelDep.second);
1208
624
1209
624
  AvailableQueue->updateNode(SU);
1210
624
  AvailableQueue->addNode(NewSU);
1211
624
1212
624
  ++NumDups;
1213
624
  return NewSU;
1214
624
}
1215
1216
/// InsertCopiesAndMoveSuccs - Insert register copies and move all
1217
/// scheduled successors of the given SUnit to the last copy.
1218
void ScheduleDAGRRList::InsertCopiesAndMoveSuccs(SUnit *SU, unsigned Reg,
1219
                                              const TargetRegisterClass *DestRC,
1220
                                              const TargetRegisterClass *SrcRC,
1221
54
                                              SmallVectorImpl<SUnit*> &Copies) {
1222
54
  SUnit *CopyFromSU = CreateNewSUnit(nullptr);
1223
54
  CopyFromSU->CopySrcRC = SrcRC;
1224
54
  CopyFromSU->CopyDstRC = DestRC;
1225
54
1226
54
  SUnit *CopyToSU = CreateNewSUnit(nullptr);
1227
54
  CopyToSU->CopySrcRC = DestRC;
1228
54
  CopyToSU->CopyDstRC = SrcRC;
1229
54
1230
54
  // Only copy scheduled successors. Cut them from old node's successor
1231
54
  // list and move them over.
1232
54
  SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps;
1233
189
  for (SDep &Succ : SU->Succs) {
1234
189
    if (Succ.isArtificial())
1235
0
      continue;
1236
189
    SUnit *SuccSU = Succ.getSUnit();
1237
189
    if (SuccSU->isScheduled) {
1238
96
      SDep D = Succ;
1239
96
      D.setSUnit(CopyToSU);
1240
96
      AddPredQueued(SuccSU, D);
1241
96
      DelDeps.push_back(std::make_pair(SuccSU, Succ));
1242
96
    }
1243
93
    else {
1244
93
      // Avoid scheduling the def-side copy before other successors. Otherwise
1245
93
      // we could introduce another physreg interference on the copy and
1246
93
      // continue inserting copies indefinitely.
1247
93
      AddPredQueued(SuccSU, SDep(CopyFromSU, SDep::Artificial));
1248
93
    }
1249
189
  }
1250
54
  for (auto &DelDep : DelDeps)
1251
96
    RemovePred(DelDep.first, DelDep.second);
1252
54
1253
54
  SDep FromDep(SU, SDep::Data, Reg);
1254
54
  FromDep.setLatency(SU->Latency);
1255
54
  AddPredQueued(CopyFromSU, FromDep);
1256
54
  SDep ToDep(CopyFromSU, SDep::Data, 0);
1257
54
  ToDep.setLatency(CopyFromSU->Latency);
1258
54
  AddPredQueued(CopyToSU, ToDep);
1259
54
1260
54
  AvailableQueue->updateNode(SU);
1261
54
  AvailableQueue->addNode(CopyFromSU);
1262
54
  AvailableQueue->addNode(CopyToSU);
1263
54
  Copies.push_back(CopyFromSU);
1264
54
  Copies.push_back(CopyToSU);
1265
54
1266
54
  ++NumPRCopies;
1267
54
}
1268
1269
/// getPhysicalRegisterVT - Returns the ValueType of the physical register
1270
/// definition of the specified node.
1271
/// FIXME: Move to SelectionDAG?
1272
static MVT getPhysicalRegisterVT(SDNode *N, unsigned Reg,
1273
1.27k
                                 const TargetInstrInfo *TII) {
1274
1.27k
  unsigned NumRes;
1275
1.27k
  if (N->getOpcode() == ISD::CopyFromReg) {
1276
14
    // CopyFromReg has: "chain, Val, glue" so operand 1 gives the type.
1277
14
    NumRes = 1;
1278
1.26k
  } else {
1279
1.26k
    const MCInstrDesc &MCID = TII->get(N->getMachineOpcode());
1280
1.26k
    assert(MCID.ImplicitDefs && "Physical reg def must be in implicit def list!");
1281
1.26k
    NumRes = MCID.getNumDefs();
1282
1.26k
    for (const MCPhysReg *ImpDef = MCID.getImplicitDefs(); *ImpDef; 
++ImpDef4
) {
1283
1.26k
      if (Reg == *ImpDef)
1284
1.26k
        break;
1285
4
      ++NumRes;
1286
4
    }
1287
1.26k
  }
1288
1.27k
  return N->getSimpleValueType(NumRes);
1289
1.27k
}
1290
1291
/// CheckForLiveRegDef - Return true and update live register vector if the
1292
/// specified register def of the specified SUnit clobbers any "live" registers.
1293
static void CheckForLiveRegDef(SUnit *SU, unsigned Reg,
1294
                               SUnit **LiveRegDefs,
1295
                               SmallSet<unsigned, 4> &RegAdded,
1296
                               SmallVectorImpl<unsigned> &LRegs,
1297
1.18M
                               const TargetRegisterInfo *TRI) {
1298
4.02M
  for (MCRegAliasIterator AliasI(Reg, TRI, true); AliasI.isValid(); 
++AliasI2.84M
) {
1299
2.84M
1300
2.84M
    // Check if Ref is live.
1301
2.84M
    if (!LiveRegDefs[*AliasI]) 
continue2.35M
;
1302
486k
1303
486k
    // Allow multiple uses of the same def.
1304
486k
    if (LiveRegDefs[*AliasI] == SU) 
continue407k
;
1305
79.0k
1306
79.0k
    // Add Reg to the set of interfering live regs.
1307
79.0k
    if (RegAdded.insert(*AliasI).second) {
1308
76.5k
      LRegs.push_back(*AliasI);
1309
76.5k
    }
1310
79.0k
  }
1311
1.18M
}
1312
1313
/// CheckForLiveRegDefMasked - Check for any live physregs that are clobbered
1314
/// by RegMask, and add them to LRegs.
1315
static void CheckForLiveRegDefMasked(SUnit *SU, const uint32_t *RegMask,
1316
                                     ArrayRef<SUnit*> LiveRegDefs,
1317
                                     SmallSet<unsigned, 4> &RegAdded,
1318
2.56k
                                     SmallVectorImpl<unsigned> &LRegs) {
1319
2.56k
  // Look at all live registers. Skip Reg0 and the special CallResource.
1320
764k
  for (unsigned i = 1, e = LiveRegDefs.size()-1; i != e; 
++i762k
) {
1321
762k
    if (!LiveRegDefs[i]) 
continue761k
;
1322
1.20k
    if (LiveRegDefs[i] == SU) 
continue0
;
1323
1.20k
    if (!MachineOperand::clobbersPhysReg(RegMask, i)) 
continue0
;
1324
1.20k
    if (RegAdded.insert(i).second)
1325
89
      LRegs.push_back(i);
1326
1.20k
  }
1327
2.56k
}
1328
1329
/// getNodeRegMask - Returns the register mask attached to an SDNode, if any.
1330
1.35M
static const uint32_t *getNodeRegMask(const SDNode *N) {
1331
1.35M
  for (const SDValue &Op : N->op_values())
1332
4.66M
    if (const auto *RegOp = dyn_cast<RegisterMaskSDNode>(Op.getNode()))
1333
2.56k
      return RegOp->getRegMask();
1334
1.35M
  
return nullptr1.34M
;
1335
1.35M
}
1336
1337
/// DelayForLiveRegsBottomUp - Returns true if it is necessary to delay
1338
/// scheduling of the given node to satisfy live physical register dependencies.
1339
/// If the specific node is the last one that's available to schedule, do
1340
/// whatever is necessary (i.e. backtracking or cloning) to make it possible.
1341
bool ScheduleDAGRRList::
1342
11.1M
DelayForLiveRegsBottomUp(SUnit *SU, SmallVectorImpl<unsigned> &LRegs) {
1343
11.1M
  if (NumLiveRegs == 0)
1344
9.38M
    return false;
1345
1.78M
1346
1.78M
  SmallSet<unsigned, 4> RegAdded;
1347
1.78M
  // If this node would clobber any "live" register, then it's not ready.
1348
1.78M
  //
1349
1.78M
  // If SU is the currently live definition of the same register that it uses,
1350
1.78M
  // then we are free to schedule it.
1351
1.86M
  for (SDep &Pred : SU->Preds) {
1352
1.86M
    if (Pred.isAssignedRegDep() && 
LiveRegDefs[Pred.getReg()] != SU65.6k
)
1353
61.8k
      CheckForLiveRegDef(Pred.getSUnit(), Pred.getReg(), LiveRegDefs.get(),
1354
61.8k
                         RegAdded, LRegs, TRI);
1355
1.86M
  }
1356
1.78M
1357
3.65M
  for (SDNode *Node = SU->getNode(); Node; 
Node = Node->getGluedNode()1.86M
) {
1358
1.86M
    if (Node->getOpcode() == ISD::INLINEASM ||
1359
1.86M
        
Node->getOpcode() == ISD::INLINEASM_BR1.86M
) {
1360
305
      // Inline asm can clobber physical defs.
1361
305
      unsigned NumOps = Node->getNumOperands();
1362
305
      if (Node->getOperand(NumOps-1).getValueType() == MVT::Glue)
1363
57
        --NumOps;  // Ignore the glue operand.
1364
305
1365
1.39k
      for (unsigned i = InlineAsm::Op_FirstOperand; i != NumOps;) {
1366
1.09k
        unsigned Flags =
1367
1.09k
          cast<ConstantSDNode>(Node->getOperand(i))->getZExtValue();
1368
1.09k
        unsigned NumVals = InlineAsm::getNumOperandRegisters(Flags);
1369
1.09k
1370
1.09k
        ++i; // Skip the ID value.
1371
1.09k
        if (InlineAsm::isRegDefKind(Flags) ||
1372
1.09k
            
InlineAsm::isRegDefEarlyClobberKind(Flags)1.02k
||
1373
1.09k
            
InlineAsm::isClobberKind(Flags)1.02k
) {
1374
975
          // Check for def of register or earlyclobber register.
1375
1.95k
          for (; NumVals; 
--NumVals, ++i975
) {
1376
975
            unsigned Reg = cast<RegisterSDNode>(Node->getOperand(i))->getReg();
1377
975
            if (TargetRegisterInfo::isPhysicalRegister(Reg))
1378
912
              CheckForLiveRegDef(SU, Reg, LiveRegDefs.get(), RegAdded, LRegs, TRI);
1379
975
          }
1380
975
        } else
1381
115
          i += NumVals;
1382
1.09k
      }
1383
305
      continue;
1384
305
    }
1385
1.86M
1386
1.86M
    if (!Node->isMachineOpcode())
1387
516k
      continue;
1388
1.35M
    // If we're in the middle of scheduling a call, don't begin scheduling
1389
1.35M
    // another call. Also, don't allow any physical registers to be live across
1390
1.35M
    // the call.
1391
1.35M
    if (Node->getMachineOpcode() == TII->getCallFrameDestroyOpcode()) {
1392
2.59k
      // Check the special calling-sequence resource.
1393
2.59k
      unsigned CallResource = TRI->getNumRegs();
1394
2.59k
      if (LiveRegDefs[CallResource]) {
1395
1.38k
        SDNode *Gen = LiveRegGens[CallResource]->getNode();
1396
5.33k
        while (SDNode *Glued = Gen->getGluedNode())
1397
3.94k
          Gen = Glued;
1398
1.38k
        if (!IsChainDependent(Gen, Node, 0, TII) &&
1399
1.38k
            
RegAdded.insert(CallResource).second1.38k
)
1400
1.38k
          LRegs.push_back(CallResource);
1401
1.38k
      }
1402
2.59k
    }
1403
1.35M
    if (const uint32_t *RegMask = getNodeRegMask(Node))
1404
2.56k
      CheckForLiveRegDefMasked(SU, RegMask,
1405
2.56k
                               makeArrayRef(LiveRegDefs.get(), TRI->getNumRegs()),
1406
2.56k
                               RegAdded, LRegs);
1407
1.35M
1408
1.35M
    const MCInstrDesc &MCID = TII->get(Node->getMachineOpcode());
1409
1.35M
    if (MCID.hasOptionalDef()) {
1410
32.4k
      // Most ARM instructions have an OptionalDef for CPSR, to model the S-bit.
1411
32.4k
      // This operand can be either a def of CPSR, if the S bit is set; or a use
1412
32.4k
      // of %noreg.  When the OptionalDef is set to a valid register, we need to
1413
32.4k
      // handle it in the same way as an ImplicitDef.
1414
65.7k
      for (unsigned i = 0; i < MCID.getNumDefs(); 
++i33.3k
)
1415
33.3k
        if (MCID.OpInfo[i].isOptionalDef()) {
1416
862
          const SDValue &OptionalDef = Node->getOperand(i - Node->getNumValues());
1417
862
          unsigned Reg = cast<RegisterSDNode>(OptionalDef)->getReg();
1418
862
          CheckForLiveRegDef(SU, Reg, LiveRegDefs.get(), RegAdded, LRegs, TRI);
1419
862
        }
1420
32.4k
    }
1421
1.35M
    if (!MCID.ImplicitDefs)
1422
508k
      continue;
1423
1.96M
    
for (const MCPhysReg *Reg = MCID.getImplicitDefs(); 843k
*Reg;
++Reg1.12M
)
1424
1.12M
      CheckForLiveRegDef(SU, *Reg, LiveRegDefs.get(), RegAdded, LRegs, TRI);
1425
843k
  }
1426
1.78M
1427
1.78M
  return !LRegs.empty();
1428
1.78M
}
1429
1430
749k
void ScheduleDAGRRList::releaseInterferences(unsigned Reg) {
1431
749k
  // Add the nodes that aren't ready back onto the available list.
1432
827k
  for (unsigned i = Interferences.size(); i > 0; 
--i78.0k
) {
1433
78.0k
    SUnit *SU = Interferences[i-1];
1434
78.0k
    LRegsMapT::iterator LRegsPos = LRegsMap.find(SU);
1435
78.0k
    if (Reg) {
1436
78.0k
      SmallVectorImpl<unsigned> &LRegs = LRegsPos->second;
1437
78.0k
      if (!is_contained(LRegs, Reg))
1438
8
        continue;
1439
78.0k
    }
1440
78.0k
    SU->isPending = false;
1441
78.0k
    // The interfering node may no longer be available due to backtracking.
1442
78.0k
    // Furthermore, it may have been made available again, in which case it is
1443
78.0k
    // now already in the AvailableQueue.
1444
78.0k
    if (SU->isAvailable && 
!SU->NodeQueueId22.2k
) {
1445
20.9k
      LLVM_DEBUG(dbgs() << "    Repushing SU #" << SU->NodeNum << '\n');
1446
20.9k
      AvailableQueue->push(SU);
1447
20.9k
    }
1448
78.0k
    if (i < Interferences.size())
1449
0
      Interferences[i-1] = Interferences.back();
1450
78.0k
    Interferences.pop_back();
1451
78.0k
    LRegsMap.erase(LRegsPos);
1452
78.0k
  }
1453
749k
}
1454
1455
/// Return a node that can be scheduled in this cycle. Requirements:
1456
/// (1) Ready: latency has been satisfied
1457
/// (2) No Hazards: resources are available
1458
/// (3) No Interferences: may unschedule to break register interferences.
1459
11.0M
SUnit *ScheduleDAGRRList::PickNodeToScheduleBottomUp() {
1460
11.0M
  SUnit *CurSU = AvailableQueue->empty() ? 
nullptr2.34k
:
AvailableQueue->pop()11.0M
;
1461
11.0M
  auto FindAvailableNode = [&]() {
1462
11.1M
    while (CurSU) {
1463
11.1M
      SmallVector<unsigned, 4> LRegs;
1464
11.1M
      if (!DelayForLiveRegsBottomUp(CurSU, LRegs))
1465
11.0M
        break;
1466
78.0k
      LLVM_DEBUG(dbgs() << "    Interfering reg ";
1467
78.0k
                 if (LRegs[0] == TRI->getNumRegs()) dbgs() << "CallResource";
1468
78.0k
                 else dbgs() << printReg(LRegs[0], TRI);
1469
78.0k
                 dbgs() << " SU #" << CurSU->NodeNum << '\n');
1470
78.0k
      std::pair<LRegsMapT::iterator, bool> LRegsPair =
1471
78.0k
        LRegsMap.insert(std::make_pair(CurSU, LRegs));
1472
78.0k
      if (LRegsPair.second) {
1473
78.0k
        CurSU->isPending = true;  // This SU is not in AvailableQueue right now.
1474
78.0k
        Interferences.push_back(CurSU);
1475
78.0k
      }
1476
0
      else {
1477
0
        assert(CurSU->isPending && "Interferences are pending");
1478
0
        // Update the interference with current live regs.
1479
0
        LRegsPair.first->second = LRegs;
1480
0
      }
1481
78.0k
      CurSU = AvailableQueue->pop();
1482
78.0k
    }
1483
11.0M
  };
1484
11.0M
  FindAvailableNode();
1485
11.0M
  if (CurSU)
1486
11.0M
    return CurSU;
1487
4.88k
1488
4.88k
  // We query the topological order in the loop body, so make sure outstanding
1489
4.88k
  // updates are applied before entering it (we only enter the loop if there
1490
4.88k
  // are some interferences). If we make changes to the ordering, we exit
1491
4.88k
  // the loop.
1492
4.88k
1493
4.88k
  // All candidates are delayed due to live physical reg dependencies.
1494
4.88k
  // Try backtracking, code duplication, or inserting cross class copies
1495
4.88k
  // to resolve it.
1496
7.70k
  
for (SUnit *TrySU : Interferences)4.88k
{
1497
7.70k
    SmallVectorImpl<unsigned> &LRegs = LRegsMap[TrySU];
1498
7.70k
1499
7.70k
    // Try unscheduling up to the point where it's safe to schedule
1500
7.70k
    // this node.
1501
7.70k
    SUnit *BtSU = nullptr;
1502
7.70k
    unsigned LiveCycle = std::numeric_limits<unsigned>::max();
1503
7.70k
    for (unsigned Reg : LRegs) {
1504
7.70k
      if (LiveRegGens[Reg]->getHeight() < LiveCycle) {
1505
7.70k
        BtSU = LiveRegGens[Reg];
1506
7.70k
        LiveCycle = BtSU->getHeight();
1507
7.70k
      }
1508
7.70k
    }
1509
7.70k
    if (!WillCreateCycle(TrySU, BtSU))  {
1510
3.61k
      // BacktrackBottomUp mutates Interferences!
1511
3.61k
      BacktrackBottomUp(TrySU, BtSU);
1512
3.61k
1513
3.61k
      // Force the current node to be scheduled before the node that
1514
3.61k
      // requires the physical reg dep.
1515
3.61k
      if (BtSU->isAvailable) {
1516
3.61k
        BtSU->isAvailable = false;
1517
3.61k
        if (!BtSU->isPending)
1518
3.61k
          AvailableQueue->remove(BtSU);
1519
3.61k
      }
1520
3.61k
      LLVM_DEBUG(dbgs() << "ARTIFICIAL edge from SU(" << BtSU->NodeNum
1521
3.61k
                        << ") to SU(" << TrySU->NodeNum << ")\n");
1522
3.61k
      AddPredQueued(TrySU, SDep(BtSU, SDep::Artificial));
1523
3.61k
1524
3.61k
      // If one or more successors has been unscheduled, then the current
1525
3.61k
      // node is no longer available.
1526
3.61k
      if (!TrySU->isAvailable || 
!TrySU->NodeQueueId2.09k
) {
1527
1.52k
        LLVM_DEBUG(dbgs() << "TrySU not available; choosing node from queue\n");
1528
1.52k
        CurSU = AvailableQueue->pop();
1529
2.09k
      } else {
1530
2.09k
        LLVM_DEBUG(dbgs() << "TrySU available\n");
1531
2.09k
        // Available and in AvailableQueue
1532
2.09k
        AvailableQueue->remove(TrySU);
1533
2.09k
        CurSU = TrySU;
1534
2.09k
      }
1535
3.61k
      FindAvailableNode();
1536
3.61k
      // Interferences has been mutated. We must break.
1537
3.61k
      break;
1538
3.61k
    }
1539
7.70k
  }
1540
4.88k
1541
4.88k
  if (!CurSU) {
1542
1.27k
    // Can't backtrack. If it's too expensive to copy the value, then try
1543
1.27k
    // duplicate the nodes that produces these "too expensive to copy"
1544
1.27k
    // values to break the dependency. In case even that doesn't work,
1545
1.27k
    // insert cross class copies.
1546
1.27k
    // If it's not too expensive, i.e. cost != -1, issue copies.
1547
1.27k
    SUnit *TrySU = Interferences[0];
1548
1.27k
    SmallVectorImpl<unsigned> &LRegs = LRegsMap[TrySU];
1549
1.27k
    assert(LRegs.size() == 1 && "Can't handle this yet!");
1550
1.27k
    unsigned Reg = LRegs[0];
1551
1.27k
    SUnit *LRDef = LiveRegDefs[Reg];
1552
1.27k
    MVT VT = getPhysicalRegisterVT(LRDef->getNode(), Reg, TII);
1553
1.27k
    const TargetRegisterClass *RC =
1554
1.27k
      TRI->getMinimalPhysRegClass(Reg, VT);
1555
1.27k
    const TargetRegisterClass *DestRC = TRI->getCrossCopyRegClass(RC);
1556
1.27k
1557
1.27k
    // If cross copy register class is the same as RC, then it must be possible
1558
1.27k
    // copy the value directly. Do not try duplicate the def.
1559
1.27k
    // If cross copy register class is not the same as RC, then it's possible to
1560
1.27k
    // copy the value but it require cross register class copies and it is
1561
1.27k
    // expensive.
1562
1.27k
    // If cross copy register class is null, then it's not possible to copy
1563
1.27k
    // the value at all.
1564
1.27k
    SUnit *NewDef = nullptr;
1565
1.27k
    if (DestRC != RC) {
1566
1.27k
      NewDef = CopyAndMoveSuccessors(LRDef);
1567
1.27k
      if (!DestRC && 
!NewDef0
)
1568
0
        report_fatal_error("Can't handle live physical register dependency!");
1569
1.27k
    }
1570
1.27k
    if (!NewDef) {
1571
54
      // Issue copies, these can be expensive cross register class copies.
1572
54
      SmallVector<SUnit*, 2> Copies;
1573
54
      InsertCopiesAndMoveSuccs(LRDef, Reg, DestRC, RC, Copies);
1574
54
      LLVM_DEBUG(dbgs() << "    Adding an edge from SU #" << TrySU->NodeNum
1575
54
                        << " to SU #" << Copies.front()->NodeNum << "\n");
1576
54
      AddPredQueued(TrySU, SDep(Copies.front(), SDep::Artificial));
1577
54
      NewDef = Copies.back();
1578
54
    }
1579
1.27k
1580
1.27k
    LLVM_DEBUG(dbgs() << "    Adding an edge from SU #" << NewDef->NodeNum
1581
1.27k
                      << " to SU #" << TrySU->NodeNum << "\n");
1582
1.27k
    LiveRegDefs[Reg] = NewDef;
1583
1.27k
    AddPredQueued(NewDef, SDep(TrySU, SDep::Artificial));
1584
1.27k
    TrySU->isAvailable = false;
1585
1.27k
    CurSU = NewDef;
1586
1.27k
  }
1587
4.88k
  assert(CurSU && "Unable to resolve live physical register dependencies!");
1588
4.88k
  return CurSU;
1589
4.88k
}
1590
1591
/// ListScheduleBottomUp - The main loop of list scheduling for bottom-up
1592
/// schedulers.
1593
1.24M
void ScheduleDAGRRList::ListScheduleBottomUp() {
1594
1.24M
  // Release any predecessors of the special Exit node.
1595
1.24M
  ReleasePredecessors(&ExitSU);
1596
1.24M
1597
1.24M
  // Add root to Available queue.
1598
1.24M
  if (!SUnits.empty()) {
1599
1.22M
    SUnit *RootSU = &SUnits[DAG->getRoot().getNode()->getNodeId()];
1600
1.22M
    assert(RootSU->Succs.empty() && "Graph root shouldn't have successors!");
1601
1.22M
    RootSU->isAvailable = true;
1602
1.22M
    AvailableQueue->push(RootSU);
1603
1.22M
  }
1604
1.24M
1605
1.24M
  // While Available queue is not empty, grab the node with the highest
1606
1.24M
  // priority. If it is not ready put it back.  Schedule the node.
1607
1.24M
  Sequence.reserve(SUnits.size());
1608
12.3M
  while (!AvailableQueue->empty() || 
!Interferences.empty()1.24M
) {
1609
11.0M
    LLVM_DEBUG(dbgs() << "\nExamining Available:\n";
1610
11.0M
               AvailableQueue->dump(this));
1611
11.0M
1612
11.0M
    // Pick the best node to schedule taking all constraints into
1613
11.0M
    // consideration.
1614
11.0M
    SUnit *SU = PickNodeToScheduleBottomUp();
1615
11.0M
1616
11.0M
    AdvancePastStalls(SU);
1617
11.0M
1618
11.0M
    ScheduleNodeBottomUp(SU);
1619
11.0M
1620
11.0M
    while (AvailableQueue->empty() && 
!PendingQueue.empty()1.22M
) {
1621
0
      // Advance the cycle to free resources. Skip ahead to the next ready SU.
1622
0
      assert(MinAvailableCycle < std::numeric_limits<unsigned>::max() &&
1623
0
             "MinAvailableCycle uninitialized");
1624
0
      AdvanceToCycle(std::max(CurCycle + 1, MinAvailableCycle));
1625
0
    }
1626
11.0M
  }
1627
1.24M
1628
1.24M
  // Reverse the order if it is bottom up.
1629
1.24M
  std::reverse(Sequence.begin(), Sequence.end());
1630
1.24M
1631
#ifndef NDEBUG
1632
  VerifyScheduledSequence(/*isBottomUp=*/true);
1633
#endif
1634
}
1635
1636
namespace {
1637
1638
class RegReductionPQBase;
1639
1640
struct queue_sort {
1641
0
  bool isReady(SUnit* SU, unsigned CurCycle) const { return true; }
1642
};
1643
1644
#ifndef NDEBUG
1645
template<class SF>
1646
struct reverse_sort : public queue_sort {
1647
  SF &SortFunc;
1648
1649
  reverse_sort(SF &sf) : SortFunc(sf) {}
1650
1651
  bool operator()(SUnit* left, SUnit* right) const {
1652
    // reverse left/right rather than simply !SortFunc(left, right)
1653
    // to expose different paths in the comparison logic.
1654
    return SortFunc(right, left);
1655
  }
1656
};
1657
#endif // NDEBUG
1658
1659
/// bu_ls_rr_sort - Priority function for bottom up register pressure
1660
// reduction scheduler.
1661
struct bu_ls_rr_sort : public queue_sort {
1662
  enum {
1663
    IsBottomUp = true,
1664
    HasReadyFilter = false
1665
  };
1666
1667
  RegReductionPQBase *SPQ;
1668
1669
19.7k
  bu_ls_rr_sort(RegReductionPQBase *spq) : SPQ(spq) {}
1670
1671
  bool operator()(SUnit* left, SUnit* right) const;
1672
};
1673
1674
// src_ls_rr_sort - Priority function for source order scheduler.
1675
struct src_ls_rr_sort : public queue_sort {
1676
  enum {
1677
    IsBottomUp = true,
1678
    HasReadyFilter = false
1679
  };
1680
1681
  RegReductionPQBase *SPQ;
1682
1683
1.14M
  src_ls_rr_sort(RegReductionPQBase *spq) : SPQ(spq) {}
1684
1685
  bool operator()(SUnit* left, SUnit* right) const;
1686
};
1687
1688
// hybrid_ls_rr_sort - Priority function for hybrid scheduler.
1689
struct hybrid_ls_rr_sort : public queue_sort {
1690
  enum {
1691
    IsBottomUp = true,
1692
    HasReadyFilter = false
1693
  };
1694
1695
  RegReductionPQBase *SPQ;
1696
1697
64.5k
  hybrid_ls_rr_sort(RegReductionPQBase *spq) : SPQ(spq) {}
1698
1699
  bool isReady(SUnit *SU, unsigned CurCycle) const;
1700
1701
  bool operator()(SUnit* left, SUnit* right) const;
1702
};
1703
1704
// ilp_ls_rr_sort - Priority function for ILP (instruction level parallelism)
1705
// scheduler.
1706
struct ilp_ls_rr_sort : public queue_sort {
1707
  enum {
1708
    IsBottomUp = true,
1709
    HasReadyFilter = false
1710
  };
1711
1712
  RegReductionPQBase *SPQ;
1713
1714
20.1k
  ilp_ls_rr_sort(RegReductionPQBase *spq) : SPQ(spq) {}
1715
1716
  bool isReady(SUnit *SU, unsigned CurCycle) const;
1717
1718
  bool operator()(SUnit* left, SUnit* right) const;
1719
};
1720
1721
class RegReductionPQBase : public SchedulingPriorityQueue {
1722
protected:
1723
  std::vector<SUnit *> Queue;
1724
  unsigned CurQueueId = 0;
1725
  bool TracksRegPressure;
1726
  bool SrcOrder;
1727
1728
  // SUnits - The SUnits for the current graph.
1729
  std::vector<SUnit> *SUnits;
1730
1731
  MachineFunction &MF;
1732
  const TargetInstrInfo *TII;
1733
  const TargetRegisterInfo *TRI;
1734
  const TargetLowering *TLI;
1735
  ScheduleDAGRRList *scheduleDAG = nullptr;
1736
1737
  // SethiUllmanNumbers - The SethiUllman number for each node.
1738
  std::vector<unsigned> SethiUllmanNumbers;
1739
1740
  /// RegPressure - Tracking current reg pressure per register class.
1741
  std::vector<unsigned> RegPressure;
1742
1743
  /// RegLimit - Tracking the number of allocatable registers per register
1744
  /// class.
1745
  std::vector<unsigned> RegLimit;
1746
1747
public:
1748
  RegReductionPQBase(MachineFunction &mf,
1749
                     bool hasReadyFilter,
1750
                     bool tracksrp,
1751
                     bool srcorder,
1752
                     const TargetInstrInfo *tii,
1753
                     const TargetRegisterInfo *tri,
1754
                     const TargetLowering *tli)
1755
    : SchedulingPriorityQueue(hasReadyFilter), TracksRegPressure(tracksrp),
1756
1.24M
      SrcOrder(srcorder), MF(mf), TII(tii), TRI(tri), TLI(tli) {
1757
1.24M
    if (TracksRegPressure) {
1758
84.6k
      unsigned NumRC = TRI->getNumRegClasses();
1759
84.6k
      RegLimit.resize(NumRC);
1760
84.6k
      RegPressure.resize(NumRC);
1761
84.6k
      std::fill(RegLimit.begin(), RegLimit.end(), 0);
1762
84.6k
      std::fill(RegPressure.begin(), RegPressure.end(), 0);
1763
84.6k
      for (const TargetRegisterClass *RC : TRI->regclasses())
1764
9.07M
        RegLimit[RC->getID()] = tri->getRegPressureLimit(RC, MF);
1765
84.6k
    }
1766
1.24M
  }
1767
1768
1.24M
  void setScheduleDAG(ScheduleDAGRRList *scheduleDag) {
1769
1.24M
    scheduleDAG = scheduleDag;
1770
1.24M
  }
1771
1772
13.2M
  ScheduleHazardRecognizer* getHazardRec() {
1773
13.2M
    return scheduleDAG->getHazardRec();
1774
13.2M
  }
1775
1776
  void initNodes(std::vector<SUnit> &sunits) override;
1777
1778
  void addNode(const SUnit *SU) override;
1779
1780
  void updateNode(const SUnit *SU) override;
1781
1782
1.24M
  void releaseState() override {
1783
1.24M
    SUnits = nullptr;
1784
1.24M
    SethiUllmanNumbers.clear();
1785
1.24M
    std::fill(RegPressure.begin(), RegPressure.end(), 0);
1786
1.24M
  }
1787
1788
  unsigned getNodePriority(const SUnit *SU) const;
1789
1790
68.7M
  unsigned getNodeOrdering(const SUnit *SU) const {
1791
68.7M
    if (!SU->getNode()) 
return 0104
;
1792
68.7M
1793
68.7M
    return SU->getNode()->getIROrder();
1794
68.7M
  }
1795
1796
45.3M
  bool empty() const override { return Queue.empty(); }
1797
1798
11.1M
  void push(SUnit *U) override {
1799
11.1M
    assert(!U->NodeQueueId && "Node in the queue already");
1800
11.1M
    U->NodeQueueId = ++CurQueueId;
1801
11.1M
    Queue.push_back(U);
1802
11.1M
  }
1803
1804
9.41k
  void remove(SUnit *SU) override {
1805
9.41k
    assert(!Queue.empty() && "Queue is empty!");
1806
9.41k
    assert(SU->NodeQueueId != 0 && "Not in queue!");
1807
9.41k
    std::vector<SUnit *>::iterator I = llvm::find(Queue, SU);
1808
9.41k
    if (I != std::prev(Queue.end()))
1809
726
      std::swap(*I, Queue.back());
1810
9.41k
    Queue.pop_back();
1811
9.41k
    SU->NodeQueueId = 0;
1812
9.41k
  }
1813
1814
722
  bool tracksRegPressure() const override { return TracksRegPressure; }
1815
1816
  void dumpRegPressure() const;
1817
1818
  bool HighRegPressure(const SUnit *SU) const;
1819
1820
  bool MayReduceRegPressure(SUnit *SU) const;
1821
1822
  int RegPressureDiff(SUnit *SU, unsigned &LiveUses) const;
1823
1824
  void scheduledNode(SUnit *SU) override;
1825
1826
  void unscheduledNode(SUnit *SU) override;
1827
1828
protected:
1829
  bool canClobber(const SUnit *SU, const SUnit *Op);
1830
  void AddPseudoTwoAddrDeps();
1831
  void PrescheduleNodesWithMultipleUses();
1832
  void CalculateSethiUllmanNumbers();
1833
};
1834
1835
template<class SF>
1836
11.1M
static SUnit *popFromQueueImpl(std::vector<SUnit *> &Q, SF &Picker) {
1837
11.1M
  std::vector<SUnit *>::iterator Best = Q.begin();
1838
46.8M
  for (auto I = std::next(Q.begin()), E = Q.end(); I != E; 
++I35.6M
)
1839
35.6M
    if (Picker(*Best, *I))
1840
14.2M
      Best = I;
1841
11.1M
  SUnit *V = *Best;
1842
11.1M
  if (Best != std::prev(Q.end()))
1843
2.59M
    std::swap(*Best, Q.back());
1844
11.1M
  Q.pop_back();
1845
11.1M
  return V;
1846
11.1M
}
ScheduleDAGRRList.cpp:llvm::SUnit* (anonymous namespace)::popFromQueueImpl<(anonymous namespace)::bu_ls_rr_sort>(std::__1::vector<llvm::SUnit*, std::__1::allocator<llvm::SUnit*> >&, (anonymous namespace)::bu_ls_rr_sort&)
Line
Count
Source
1836
163k
static SUnit *popFromQueueImpl(std::vector<SUnit *> &Q, SF &Picker) {
1837
163k
  std::vector<SUnit *>::iterator Best = Q.begin();
1838
396k
  for (auto I = std::next(Q.begin()), E = Q.end(); I != E; 
++I233k
)
1839
233k
    if (Picker(*Best, *I))
1840
117k
      Best = I;
1841
163k
  SUnit *V = *Best;
1842
163k
  if (Best != std::prev(Q.end()))
1843
37.9k
    std::swap(*Best, Q.back());
1844
163k
  Q.pop_back();
1845
163k
  return V;
1846
163k
}
ScheduleDAGRRList.cpp:llvm::SUnit* (anonymous namespace)::popFromQueueImpl<(anonymous namespace)::src_ls_rr_sort>(std::__1::vector<llvm::SUnit*, std::__1::allocator<llvm::SUnit*> >&, (anonymous namespace)::src_ls_rr_sort&)
Line
Count
Source
1836
10.2M
static SUnit *popFromQueueImpl(std::vector<SUnit *> &Q, SF &Picker) {
1837
10.2M
  std::vector<SUnit *>::iterator Best = Q.begin();
1838
44.8M
  for (auto I = std::next(Q.begin()), E = Q.end(); I != E; 
++I34.5M
)
1839
34.5M
    if (Picker(*Best, *I))
1840
13.7M
      Best = I;
1841
10.2M
  SUnit *V = *Best;
1842
10.2M
  if (Best != std::prev(Q.end()))
1843
2.37M
    std::swap(*Best, Q.back());
1844
10.2M
  Q.pop_back();
1845
10.2M
  return V;
1846
10.2M
}
ScheduleDAGRRList.cpp:llvm::SUnit* (anonymous namespace)::popFromQueueImpl<(anonymous namespace)::hybrid_ls_rr_sort>(std::__1::vector<llvm::SUnit*, std::__1::allocator<llvm::SUnit*> >&, (anonymous namespace)::hybrid_ls_rr_sort&)
Line
Count
Source
1836
554k
static SUnit *popFromQueueImpl(std::vector<SUnit *> &Q, SF &Picker) {
1837
554k
  std::vector<SUnit *>::iterator Best = Q.begin();
1838
1.16M
  for (auto I = std::next(Q.begin()), E = Q.end(); I != E; 
++I606k
)
1839
606k
    if (Picker(*Best, *I))
1840
269k
      Best = I;
1841
554k
  SUnit *V = *Best;
1842
554k
  if (Best != std::prev(Q.end()))
1843
142k
    std::swap(*Best, Q.back());
1844
554k
  Q.pop_back();
1845
554k
  return V;
1846
554k
}
ScheduleDAGRRList.cpp:llvm::SUnit* (anonymous namespace)::popFromQueueImpl<(anonymous namespace)::ilp_ls_rr_sort>(std::__1::vector<llvm::SUnit*, std::__1::allocator<llvm::SUnit*> >&, (anonymous namespace)::ilp_ls_rr_sort&)
Line
Count
Source
1836
158k
static SUnit *popFromQueueImpl(std::vector<SUnit *> &Q, SF &Picker) {
1837
158k
  std::vector<SUnit *>::iterator Best = Q.begin();
1838
382k
  for (auto I = std::next(Q.begin()), E = Q.end(); I != E; 
++I224k
)
1839
224k
    if (Picker(*Best, *I))
1840
108k
      Best = I;
1841
158k
  SUnit *V = *Best;
1842
158k
  if (Best != std::prev(Q.end()))
1843
34.9k
    std::swap(*Best, Q.back());
1844
158k
  Q.pop_back();
1845
158k
  return V;
1846
158k
}
1847
1848
template<class SF>
1849
11.1M
SUnit *popFromQueue(std::vector<SUnit *> &Q, SF &Picker, ScheduleDAG *DAG) {
1850
#ifndef NDEBUG
1851
  if (DAG->StressSched) {
1852
    reverse_sort<SF> RPicker(Picker);
1853
    return popFromQueueImpl(Q, RPicker);
1854
  }
1855
#endif
1856
  (void)DAG;
1857
11.1M
  return popFromQueueImpl(Q, Picker);
1858
11.1M
}
ScheduleDAGRRList.cpp:llvm::SUnit* (anonymous namespace)::popFromQueue<(anonymous namespace)::bu_ls_rr_sort>(std::__1::vector<llvm::SUnit*, std::__1::allocator<llvm::SUnit*> >&, (anonymous namespace)::bu_ls_rr_sort&, llvm::ScheduleDAG*)
Line
Count
Source
1849
163k
SUnit *popFromQueue(std::vector<SUnit *> &Q, SF &Picker, ScheduleDAG *DAG) {
1850
#ifndef NDEBUG
1851
  if (DAG->StressSched) {
1852
    reverse_sort<SF> RPicker(Picker);
1853
    return popFromQueueImpl(Q, RPicker);
1854
  }
1855
#endif
1856
  (void)DAG;
1857
163k
  return popFromQueueImpl(Q, Picker);
1858
163k
}
ScheduleDAGRRList.cpp:llvm::SUnit* (anonymous namespace)::popFromQueue<(anonymous namespace)::src_ls_rr_sort>(std::__1::vector<llvm::SUnit*, std::__1::allocator<llvm::SUnit*> >&, (anonymous namespace)::src_ls_rr_sort&, llvm::ScheduleDAG*)
Line
Count
Source
1849
10.2M
SUnit *popFromQueue(std::vector<SUnit *> &Q, SF &Picker, ScheduleDAG *DAG) {
1850
#ifndef NDEBUG
1851
  if (DAG->StressSched) {
1852
    reverse_sort<SF> RPicker(Picker);
1853
    return popFromQueueImpl(Q, RPicker);
1854
  }
1855
#endif
1856
  (void)DAG;
1857
10.2M
  return popFromQueueImpl(Q, Picker);
1858
10.2M
}
ScheduleDAGRRList.cpp:llvm::SUnit* (anonymous namespace)::popFromQueue<(anonymous namespace)::hybrid_ls_rr_sort>(std::__1::vector<llvm::SUnit*, std::__1::allocator<llvm::SUnit*> >&, (anonymous namespace)::hybrid_ls_rr_sort&, llvm::ScheduleDAG*)
Line
Count
Source
1849
554k
SUnit *popFromQueue(std::vector<SUnit *> &Q, SF &Picker, ScheduleDAG *DAG) {
1850
#ifndef NDEBUG
1851
  if (DAG->StressSched) {
1852
    reverse_sort<SF> RPicker(Picker);
1853
    return popFromQueueImpl(Q, RPicker);
1854
  }
1855
#endif
1856
  (void)DAG;
1857
554k
  return popFromQueueImpl(Q, Picker);
1858
554k
}
ScheduleDAGRRList.cpp:llvm::SUnit* (anonymous namespace)::popFromQueue<(anonymous namespace)::ilp_ls_rr_sort>(std::__1::vector<llvm::SUnit*, std::__1::allocator<llvm::SUnit*> >&, (anonymous namespace)::ilp_ls_rr_sort&, llvm::ScheduleDAG*)
Line
Count
Source
1849
158k
SUnit *popFromQueue(std::vector<SUnit *> &Q, SF &Picker, ScheduleDAG *DAG) {
1850
#ifndef NDEBUG
1851
  if (DAG->StressSched) {
1852
    reverse_sort<SF> RPicker(Picker);
1853
    return popFromQueueImpl(Q, RPicker);
1854
  }
1855
#endif
1856
  (void)DAG;
1857
158k
  return popFromQueueImpl(Q, Picker);
1858
158k
}
1859
1860
//===----------------------------------------------------------------------===//
1861
//                RegReductionPriorityQueue Definition
1862
//===----------------------------------------------------------------------===//
1863
//
1864
// This is a SchedulingPriorityQueue that schedules using Sethi Ullman numbers
1865
// to reduce register pressure.
1866
//
1867
template<class SF>
1868
class RegReductionPriorityQueue : public RegReductionPQBase {
1869
  SF Picker;
1870
1871
public:
1872
  RegReductionPriorityQueue(MachineFunction &mf,
1873
                            bool tracksrp,
1874
                            bool srcorder,
1875
                            const TargetInstrInfo *tii,
1876
                            const TargetRegisterInfo *tri,
1877
                            const TargetLowering *tli)
1878
    : RegReductionPQBase(mf, SF::HasReadyFilter, tracksrp, srcorder,
1879
                         tii, tri, tli),
1880
1.24M
      Picker(this) {}
ScheduleDAGRRList.cpp:(anonymous namespace)::RegReductionPriorityQueue<(anonymous namespace)::bu_ls_rr_sort>::RegReductionPriorityQueue(llvm::MachineFunction&, bool, bool, llvm::TargetInstrInfo const*, llvm::TargetRegisterInfo const*, llvm::TargetLowering const*)
Line
Count
Source
1880
19.7k
      Picker(this) {}
ScheduleDAGRRList.cpp:(anonymous namespace)::RegReductionPriorityQueue<(anonymous namespace)::src_ls_rr_sort>::RegReductionPriorityQueue(llvm::MachineFunction&, bool, bool, llvm::TargetInstrInfo const*, llvm::TargetRegisterInfo const*, llvm::TargetLowering const*)
Line
Count
Source
1880
1.14M
      Picker(this) {}
ScheduleDAGRRList.cpp:(anonymous namespace)::RegReductionPriorityQueue<(anonymous namespace)::hybrid_ls_rr_sort>::RegReductionPriorityQueue(llvm::MachineFunction&, bool, bool, llvm::TargetInstrInfo const*, llvm::TargetRegisterInfo const*, llvm::TargetLowering const*)
Line
Count
Source
1880
64.5k
      Picker(this) {}
ScheduleDAGRRList.cpp:(anonymous namespace)::RegReductionPriorityQueue<(anonymous namespace)::ilp_ls_rr_sort>::RegReductionPriorityQueue(llvm::MachineFunction&, bool, bool, llvm::TargetInstrInfo const*, llvm::TargetRegisterInfo const*, llvm::TargetLowering const*)
Line
Count
Source
1880
20.1k
      Picker(this) {}
1881
1882
0
  bool isBottomUp() const override { return SF::IsBottomUp; }
Unexecuted instantiation: ScheduleDAGRRList.cpp:(anonymous namespace)::RegReductionPriorityQueue<(anonymous namespace)::bu_ls_rr_sort>::isBottomUp() const
Unexecuted instantiation: ScheduleDAGRRList.cpp:(anonymous namespace)::RegReductionPriorityQueue<(anonymous namespace)::src_ls_rr_sort>::isBottomUp() const
Unexecuted instantiation: ScheduleDAGRRList.cpp:(anonymous namespace)::RegReductionPriorityQueue<(anonymous namespace)::hybrid_ls_rr_sort>::isBottomUp() const
Unexecuted instantiation: ScheduleDAGRRList.cpp:(anonymous namespace)::RegReductionPriorityQueue<(anonymous namespace)::ilp_ls_rr_sort>::isBottomUp() const
1883
1884
0
  bool isReady(SUnit *U) const override {
1885
0
    return Picker.HasReadyFilter && Picker.isReady(U, getCurCycle());
1886
0
  }
Unexecuted instantiation: ScheduleDAGRRList.cpp:(anonymous namespace)::RegReductionPriorityQueue<(anonymous namespace)::bu_ls_rr_sort>::isReady(llvm::SUnit*) const
Unexecuted instantiation: ScheduleDAGRRList.cpp:(anonymous namespace)::RegReductionPriorityQueue<(anonymous namespace)::src_ls_rr_sort>::isReady(llvm::SUnit*) const
Unexecuted instantiation: ScheduleDAGRRList.cpp:(anonymous namespace)::RegReductionPriorityQueue<(anonymous namespace)::hybrid_ls_rr_sort>::isReady(llvm::SUnit*) const
Unexecuted instantiation: ScheduleDAGRRList.cpp:(anonymous namespace)::RegReductionPriorityQueue<(anonymous namespace)::ilp_ls_rr_sort>::isReady(llvm::SUnit*) const
1887
1888
11.1M
  SUnit *pop() override {
1889
11.1M
    if (Queue.empty()) 
return nullptr2.55k
;
1890
11.1M
1891
11.1M
    SUnit *V = popFromQueue(Queue, Picker, scheduleDAG);
1892
11.1M
    V->NodeQueueId = 0;
1893
11.1M
    return V;
1894
11.1M
  }
ScheduleDAGRRList.cpp:(anonymous namespace)::RegReductionPriorityQueue<(anonymous namespace)::bu_ls_rr_sort>::pop()
Line
Count
Source
1888
163k
  SUnit *pop() override {
1889
163k
    if (Queue.empty()) 
return nullptr107
;
1890
163k
1891
163k
    SUnit *V = popFromQueue(Queue, Picker, scheduleDAG);
1892
163k
    V->NodeQueueId = 0;
1893
163k
    return V;
1894
163k
  }
ScheduleDAGRRList.cpp:(anonymous namespace)::RegReductionPriorityQueue<(anonymous namespace)::src_ls_rr_sort>::pop()
Line
Count
Source
1888
10.2M
  SUnit *pop() override {
1889
10.2M
    if (Queue.empty()) 
return nullptr2.42k
;
1890
10.2M
1891
10.2M
    SUnit *V = popFromQueue(Queue, Picker, scheduleDAG);
1892
10.2M
    V->NodeQueueId = 0;
1893
10.2M
    return V;
1894
10.2M
  }
ScheduleDAGRRList.cpp:(anonymous namespace)::RegReductionPriorityQueue<(anonymous namespace)::hybrid_ls_rr_sort>::pop()
Line
Count
Source
1888
554k
  SUnit *pop() override {
1889
554k
    if (Queue.empty()) 
return nullptr20
;
1890
554k
1891
554k
    SUnit *V = popFromQueue(Queue, Picker, scheduleDAG);
1892
554k
    V->NodeQueueId = 0;
1893
554k
    return V;
1894
554k
  }
ScheduleDAGRRList.cpp:(anonymous namespace)::RegReductionPriorityQueue<(anonymous namespace)::ilp_ls_rr_sort>::pop()
Line
Count
Source
1888
158k
  SUnit *pop() override {
1889
158k
    if (Queue.empty()) 
return nullptr2
;
1890
158k
1891
158k
    SUnit *V = popFromQueue(Queue, Picker, scheduleDAG);
1892
158k
    V->NodeQueueId = 0;
1893
158k
    return V;
1894
158k
  }
1895
1896
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1897
  LLVM_DUMP_METHOD void dump(ScheduleDAG *DAG) const override {
1898
    // Emulate pop() without clobbering NodeQueueIds.
1899
    std::vector<SUnit *> DumpQueue = Queue;
1900
    SF DumpPicker = Picker;
1901
    while (!DumpQueue.empty()) {
1902
      SUnit *SU = popFromQueue(DumpQueue, DumpPicker, scheduleDAG);
1903
      dbgs() << "Height " << SU->getHeight() << ": ";
1904
      DAG->dumpNode(*SU);
1905
    }
1906
  }
1907
#endif
1908
};
1909
1910
using BURegReductionPriorityQueue = RegReductionPriorityQueue<bu_ls_rr_sort>;
1911
using SrcRegReductionPriorityQueue = RegReductionPriorityQueue<src_ls_rr_sort>;
1912
using HybridBURRPriorityQueue = RegReductionPriorityQueue<hybrid_ls_rr_sort>;
1913
using ILPBURRPriorityQueue = RegReductionPriorityQueue<ilp_ls_rr_sort>;
1914
1915
} // end anonymous namespace
1916
1917
//===----------------------------------------------------------------------===//
1918
//           Static Node Priority for Register Pressure Reduction
1919
//===----------------------------------------------------------------------===//
1920
1921
// Check for special nodes that bypass scheduling heuristics.
1922
// Currently this pushes TokenFactor nodes down, but may be used for other
1923
// pseudo-ops as well.
1924
//
1925
// Return -1 to schedule right above left, 1 for left above right.
1926
// Return 0 if no bias exists.
1927
35.6M
static int checkSpecialNodes(const SUnit *left, const SUnit *right) {
1928
35.6M
  bool LSchedLow = left->isScheduleLow;
1929
35.6M
  bool RSchedLow = right->isScheduleLow;
1930
35.6M
  if (LSchedLow != RSchedLow)
1931
211k
    return LSchedLow < RSchedLow ? 
192.9k
:
-1118k
;
1932
35.4M
  return 0;
1933
35.4M
}
1934
1935
/// CalcNodeSethiUllmanNumber - Compute Sethi Ullman number.
1936
/// Smaller number is the higher priority.
1937
static unsigned
1938
11.0M
CalcNodeSethiUllmanNumber(const SUnit *SU, std::vector<unsigned> &SUNumbers) {
1939
11.0M
  if (SUNumbers[SU->NodeNum] != 0)
1940
6.50M
    return SUNumbers[SU->NodeNum];
1941
4.51M
1942
4.51M
  // Use WorkList to avoid stack overflow on excessively large IRs.
1943
4.51M
  struct WorkState {
1944
11.0M
    WorkState(const SUnit *SU) : SU(SU) {}
1945
4.51M
    const SUnit *SU;
1946
4.51M
    unsigned PredsProcessed = 0;
1947
4.51M
  };
1948
4.51M
1949
4.51M
  SmallVector<WorkState, 16> WorkList;
1950
4.51M
  WorkList.push_back(SU);
1951
22.0M
  while (!WorkList.empty()) {
1952
17.5M
    auto &Temp = WorkList.back();
1953
17.5M
    auto *TempSU = Temp.SU;
1954
17.5M
    bool AllPredsKnown = true;
1955
17.5M
    // Try to find a non-evaluated pred and push it into the processing stack.
1956
23.6M
    for (unsigned P = Temp.PredsProcessed; P < TempSU->Preds.size(); 
++P6.15M
) {
1957
12.6M
      auto &Pred = TempSU->Preds[P];
1958
12.6M
      if (Pred.isCtrl()) 
continue4.13M
; // ignore chain preds
1959
8.52M
      SUnit *PredSU = Pred.getSUnit();
1960
8.52M
      if (SUNumbers[PredSU->NodeNum] == 0) {
1961
#ifndef NDEBUG
1962
        // In debug mode, check that we don't have such element in the stack.
1963
        for (auto It : WorkList)
1964
          assert(It.SU != PredSU && "Trying to push an element twice?");
1965
#endif
1966
        // Next time start processing this one starting from the next pred.
1967
6.50M
        Temp.PredsProcessed = P + 1;
1968
6.50M
        WorkList.push_back(PredSU);
1969
6.50M
        AllPredsKnown = false;
1970
6.50M
        break;
1971
6.50M
      }
1972
8.52M
    }
1973
17.5M
1974
17.5M
    if (!AllPredsKnown)
1975
6.50M
      continue;
1976
11.0M
1977
11.0M
    // Once all preds are known, we can calculate the answer for this one.
1978
11.0M
    unsigned SethiUllmanNumber = 0;
1979
11.0M
    unsigned Extra = 0;
1980
12.6M
    for (const SDep &Pred : TempSU->Preds) {
1981
12.6M
      if (Pred.isCtrl()) 
continue4.13M
; // ignore chain preds
1982
8.52M
      SUnit *PredSU = Pred.getSUnit();
1983
8.52M
      unsigned PredSethiUllman = SUNumbers[PredSU->NodeNum];
1984
8.52M
      assert(PredSethiUllman > 0 && "We should have evaluated this pred!");
1985
8.52M
      if (PredSethiUllman > SethiUllmanNumber) {
1986
6.29M
        SethiUllmanNumber = PredSethiUllman;
1987
6.29M
        Extra = 0;
1988
6.29M
      } else 
if (2.22M
PredSethiUllman == SethiUllmanNumber2.22M
)
1989
1.69M
        ++Extra;
1990
8.52M
    }
1991
11.0M
1992
11.0M
    SethiUllmanNumber += Extra;
1993
11.0M
    if (SethiUllmanNumber == 0)
1994
5.02M
      SethiUllmanNumber = 1;
1995
11.0M
    SUNumbers[TempSU->NodeNum] = SethiUllmanNumber;
1996
11.0M
    WorkList.pop_back();
1997
11.0M
  }
1998
4.51M
1999
4.51M
  assert(SUNumbers[SU->NodeNum] > 0 && "SethiUllman should never be zero!");
2000
4.51M
  return SUNumbers[SU->NodeNum];
2001
4.51M
}
2002
2003
/// CalculateSethiUllmanNumbers - Calculate Sethi-Ullman numbers of all
2004
/// scheduling units.
2005
1.24M
void RegReductionPQBase::CalculateSethiUllmanNumbers() {
2006
1.24M
  SethiUllmanNumbers.assign(SUnits->size(), 0);
2007
1.24M
2008
1.24M
  for (const SUnit &SU : *SUnits)
2009
11.0M
    CalcNodeSethiUllmanNumber(&SU, SethiUllmanNumbers);
2010
1.24M
}
2011
2012
2.00k
void RegReductionPQBase::addNode(const SUnit *SU) {
2013
2.00k
  unsigned SUSize = SethiUllmanNumbers.size();
2014
2.00k
  if (SUnits->size() > SUSize)
2015
969
    SethiUllmanNumbers.resize(SUSize*2, 0);
2016
2.00k
  CalcNodeSethiUllmanNumber(SU, SethiUllmanNumbers);
2017
2.00k
}
2018
2019
678
void RegReductionPQBase::updateNode(const SUnit *SU) {
2020
678
  SethiUllmanNumbers[SU->NodeNum] = 0;
2021
678
  CalcNodeSethiUllmanNumber(SU, SethiUllmanNumbers);
2022
678
}
2023
2024
// Lower priority means schedule further down. For bottom-up scheduling, lower
2025
// priority SUs are scheduled before higher priority SUs.
2026
24.1M
unsigned RegReductionPQBase::getNodePriority(const SUnit *SU) const {
2027
24.1M
  assert(SU->NodeNum < SethiUllmanNumbers.size());
2028
24.1M
  unsigned Opc = SU->getNode() ? 
SU->getNode()->getOpcode()24.1M
:
04
;
2029
24.1M
  if (Opc == ISD::TokenFactor || 
Opc == ISD::CopyToReg24.1M
)
2030
875k
    // CopyToReg should be close to its uses to facilitate coalescing and
2031
875k
    // avoid spilling.
2032
875k
    return 0;
2033
23.2M
  if (Opc == TargetOpcode::EXTRACT_SUBREG ||
2034
23.2M
      Opc == TargetOpcode::SUBREG_TO_REG ||
2035
23.2M
      Opc == TargetOpcode::INSERT_SUBREG)
2036
0
    // EXTRACT_SUBREG, INSERT_SUBREG, and SUBREG_TO_REG nodes should be
2037
0
    // close to their uses to facilitate coalescing.
2038
0
    return 0;
2039
23.2M
  if (SU->NumSuccs == 0 && 
SU->NumPreds != 05.75M
)
2040
5.34M
    // If SU does not have a register use, i.e. it doesn't produce a value
2041
5.34M
    // that would be consumed (e.g. store), then it terminates a chain of
2042
5.34M
    // computation.  Give it a large SethiUllman number so it will be
2043
5.34M
    // scheduled right before its predecessors that it doesn't lengthen
2044
5.34M
    // their live ranges.
2045
5.34M
    return 0xffff;
2046
17.8M
  if (SU->NumPreds == 0 && 
SU->NumSuccs != 03.97M
)
2047
3.57M
    // If SU does not have a register def, schedule it close to its uses
2048
3.57M
    // because it does not lengthen any live ranges.
2049
3.57M
    return 0;
2050
14.3M
#if 1
2051
14.3M
  return SethiUllmanNumbers[SU->NodeNum];
2052
#else
2053
  unsigned Priority = SethiUllmanNumbers[SU->NodeNum];
2054
  if (SU->isCallOp) {
2055
    // FIXME: This assumes all of the defs are used as call operands.
2056
    int NP = (int)Priority - SU->getNode()->getNumValues();
2057
    return (NP > 0) ? NP : 0;
2058
  }
2059
  return Priority;
2060
#endif
2061
}
2062
2063
//===----------------------------------------------------------------------===//
2064
//                     Register Pressure Tracking
2065
//===----------------------------------------------------------------------===//
2066
2067
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2068
LLVM_DUMP_METHOD void RegReductionPQBase::dumpRegPressure() const {
2069
  for (const TargetRegisterClass *RC : TRI->regclasses()) {
2070
    unsigned Id = RC->getID();
2071
    unsigned RP = RegPressure[Id];
2072
    if (!RP) continue;
2073
    LLVM_DEBUG(dbgs() << TRI->getRegClassName(RC) << ": " << RP << " / "
2074
                      << RegLimit[Id] << '\n');
2075
  }
2076
}
2077
#endif
2078
2079
1.15M
bool RegReductionPQBase::HighRegPressure(const SUnit *SU) const {
2080
1.15M
  if (!TLI)
2081
0
    return false;
2082
1.15M
2083
1.30M
  
for (const SDep &Pred : SU->Preds)1.15M
{
2084
1.30M
    if (Pred.isCtrl())
2085
279k
      continue;
2086
1.02M
    SUnit *PredSU = Pred.getSUnit();
2087
1.02M
    // NumRegDefsLeft is zero when enough uses of this node have been scheduled
2088
1.02M
    // to cover the number of registers defined (they are all live).
2089
1.02M
    if (PredSU->NumRegDefsLeft == 0) {
2090
387k
      continue;
2091
387k
    }
2092
641k
    for (ScheduleDAGSDNodes::RegDefIter RegDefPos(PredSU, scheduleDAG);
2093
1.28M
         RegDefPos.IsValid(); 
RegDefPos.Advance()643k
) {
2094
684k
      unsigned RCId, Cost;
2095
684k
      GetCostForDef(RegDefPos, TLI, TII, TRI, RCId, Cost, MF);
2096
684k
2097
684k
      if ((RegPressure[RCId] + Cost) >= RegLimit[RCId])
2098
40.9k
        return true;
2099
684k
    }
2100
641k
  }
2101
1.15M
  
return false1.11M
;
2102
1.15M
}
2103
2104
0
bool RegReductionPQBase::MayReduceRegPressure(SUnit *SU) const {
2105
0
  const SDNode *N = SU->getNode();
2106
0
2107
0
  if (!N->isMachineOpcode() || !SU->NumSuccs)
2108
0
    return false;
2109
0
2110
0
  unsigned NumDefs = TII->get(N->getMachineOpcode()).getNumDefs();
2111
0
  for (unsigned i = 0; i != NumDefs; ++i) {
2112
0
    MVT VT = N->getSimpleValueType(i);
2113
0
    if (!N->hasAnyUseOfValue(i))
2114
0
      continue;
2115
0
    unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
2116
0
    if (RegPressure[RCId] >= RegLimit[RCId])
2117
0
      return true;
2118
0
  }
2119
0
  return false;
2120
0
}
2121
2122
// Compute the register pressure contribution by this instruction by count up
2123
// for uses that are not live and down for defs. Only count register classes
2124
// that are already under high pressure. As a side effect, compute the number of
2125
// uses of registers that are already live.
2126
//
2127
// FIXME: This encompasses the logic in HighRegPressure and MayReduceRegPressure
2128
// so could probably be factored.
2129
435k
int RegReductionPQBase::RegPressureDiff(SUnit *SU, unsigned &LiveUses) const {
2130
435k
  LiveUses = 0;
2131
435k
  int PDiff = 0;
2132
533k
  for (const SDep &Pred : SU->Preds) {
2133
533k
    if (Pred.isCtrl())
2134
78.4k
      continue;
2135
454k
    SUnit *PredSU = Pred.getSUnit();
2136
454k
    // NumRegDefsLeft is zero when enough uses of this node have been scheduled
2137
454k
    // to cover the number of registers defined (they are all live).
2138
454k
    if (PredSU->NumRegDefsLeft == 0) {
2139
150k
      if (PredSU->getNode()->isMachineOpcode())
2140
132k
        ++LiveUses;
2141
150k
      continue;
2142
150k
    }
2143
304k
    for (ScheduleDAGSDNodes::RegDefIter RegDefPos(PredSU, scheduleDAG);
2144
609k
         RegDefPos.IsValid(); 
RegDefPos.Advance()304k
) {
2145
304k
      MVT VT = RegDefPos.GetValue();
2146
304k
      unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
2147
304k
      if (RegPressure[RCId] >= RegLimit[RCId])
2148
172k
        ++PDiff;
2149
304k
    }
2150
304k
  }
2151
435k
  const SDNode *N = SU->getNode();
2152
435k
2153
435k
  if (!N || !N->isMachineOpcode() || 
!SU->NumSuccs320k
)
2154
244k
    return PDiff;
2155
191k
2156
191k
  unsigned NumDefs = TII->get(N->getMachineOpcode()).getNumDefs();
2157
382k
  for (unsigned i = 0; i != NumDefs; 
++i191k
) {
2158
191k
    MVT VT = N->getSimpleValueType(i);
2159
191k
    if (!N->hasAnyUseOfValue(i))
2160
16
      continue;
2161
190k
    unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
2162
190k
    if (RegPressure[RCId] >= RegLimit[RCId])
2163
88.7k
      --PDiff;
2164
190k
  }
2165
191k
  return PDiff;
2166
191k
}
2167
2168
11.0M
void RegReductionPQBase::scheduledNode(SUnit *SU) {
2169
11.0M
  if (!TracksRegPressure)
2170
10.3M
    return;
2171
712k
2172
712k
  if (!SU->getNode())
2173
2
    return;
2174
712k
2175
836k
  
for (const SDep &Pred : SU->Preds)712k
{
2176
836k
    if (Pred.isCtrl())
2177
327k
      continue;
2178
508k
    SUnit *PredSU = Pred.getSUnit();
2179
508k
    // NumRegDefsLeft is zero when enough uses of this node have been scheduled
2180
508k
    // to cover the number of registers defined (they are all live).
2181
508k
    if (PredSU->NumRegDefsLeft == 0) {
2182
113k
      continue;
2183
113k
    }
2184
394k
    // FIXME: The ScheduleDAG currently loses information about which of a
2185
394k
    // node's values is consumed by each dependence. Consequently, if the node
2186
394k
    // defines multiple register classes, we don't know which to pressurize
2187
394k
    // here. Instead the following loop consumes the register defs in an
2188
394k
    // arbitrary order. At least it handles the common case of clustered loads
2189
394k
    // to the same class. For precise liveness, each SDep needs to indicate the
2190
394k
    // result number. But that tightly couples the ScheduleDAG with the
2191
394k
    // SelectionDAG making updates tricky. A simpler hack would be to attach a
2192
394k
    // value type or register class to SDep.
2193
394k
    //
2194
394k
    // The most important aspect of register tracking is balancing the increase
2195
394k
    // here with the reduction further below. Note that this SU may use multiple
2196
394k
    // defs in PredSU. The can't be determined here, but we've already
2197
394k
    // compensated by reducing NumRegDefsLeft in PredSU during
2198
394k
    // ScheduleDAGSDNodes::AddSchedEdges.
2199
394k
    --PredSU->NumRegDefsLeft;
2200
394k
    unsigned SkipRegDefs = PredSU->NumRegDefsLeft;
2201
394k
    for (ScheduleDAGSDNodes::RegDefIter RegDefPos(PredSU, scheduleDAG);
2202
397k
         RegDefPos.IsValid(); 
RegDefPos.Advance(), --SkipRegDefs2.88k
) {
2203
397k
      if (SkipRegDefs)
2204
2.88k
        continue;
2205
394k
2206
394k
      unsigned RCId, Cost;
2207
394k
      GetCostForDef(RegDefPos, TLI, TII, TRI, RCId, Cost, MF);
2208
394k
      RegPressure[RCId] += Cost;
2209
394k
      break;
2210
394k
    }
2211
394k
  }
2212
712k
2213
712k
  // We should have this assert, but there may be dead SDNodes that never
2214
712k
  // materialize as SUnits, so they don't appear to generate liveness.
2215
712k
  //assert(SU->NumRegDefsLeft == 0 && "not all regdefs have scheduled uses");
2216
712k
  int SkipRegDefs = (int)SU->NumRegDefsLeft;
2217
712k
  for (ScheduleDAGSDNodes::RegDefIter RegDefPos(SU, scheduleDAG);
2218
1.11M
       RegDefPos.IsValid(); 
RegDefPos.Advance(), --SkipRegDefs399k
) {
2219
399k
    if (SkipRegDefs > 0)
2220
5
      continue;
2221
399k
    unsigned RCId, Cost;
2222
399k
    GetCostForDef(RegDefPos, TLI, TII, TRI, RCId, Cost, MF);
2223
399k
    if (RegPressure[RCId] < Cost) {
2224
5.20k
      // Register pressure tracking is imprecise. This can happen. But we try
2225
5.20k
      // hard not to let it happen because it likely results in poor scheduling.
2226
5.20k
      LLVM_DEBUG(dbgs() << "  SU(" << SU->NodeNum
2227
5.20k
                        << ") has too many regdefs\n");
2228
5.20k
      RegPressure[RCId] = 0;
2229
5.20k
    }
2230
394k
    else {
2231
394k
      RegPressure[RCId] -= Cost;
2232
394k
    }
2233
399k
  }
2234
712k
  LLVM_DEBUG(dumpRegPressure());
2235
712k
}
2236
2237
68.4k
void RegReductionPQBase::unscheduledNode(SUnit *SU) {
2238
68.4k
  if (!TracksRegPressure)
2239
68.2k
    return;
2240
152
2241
152
  const SDNode *N = SU->getNode();
2242
152
  if (!N) 
return0
;
2243
152
2244
152
  if (!N->isMachineOpcode()) {
2245
44
    if (N->getOpcode() != ISD::CopyToReg)
2246
35
      return;
2247
108
  } else {
2248
108
    unsigned Opc = N->getMachineOpcode();
2249
108
    if (Opc == TargetOpcode::EXTRACT_SUBREG ||
2250
108
        Opc == TargetOpcode::INSERT_SUBREG ||
2251
108
        Opc == TargetOpcode::SUBREG_TO_REG ||
2252
108
        Opc == TargetOpcode::REG_SEQUENCE ||
2253
108
        Opc == TargetOpcode::IMPLICIT_DEF)
2254
0
      return;
2255
117
  }
2256
117
2257
266
  
for (const SDep &Pred : SU->Preds)117
{
2258
266
    if (Pred.isCtrl())
2259
52
      continue;
2260
214
    SUnit *PredSU = Pred.getSUnit();
2261
214
    // NumSuccsLeft counts all deps. Don't compare it with NumSuccs which only
2262
214
    // counts data deps.
2263
214
    if (PredSU->NumSuccsLeft != PredSU->Succs.size())
2264
81
      continue;
2265
133
    const SDNode *PN = PredSU->getNode();
2266
133
    if (!PN->isMachineOpcode()) {
2267
28
      if (PN->getOpcode() == ISD::CopyFromReg) {
2268
28
        MVT VT = PN->getSimpleValueType(0);
2269
28
        unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
2270
28
        RegPressure[RCId] += TLI->getRepRegClassCostFor(VT);
2271
28
      }
2272
28
      continue;
2273
28
    }
2274
105
    unsigned POpc = PN->getMachineOpcode();
2275
105
    if (POpc == TargetOpcode::IMPLICIT_DEF)
2276
0
      continue;
2277
105
    if (POpc == TargetOpcode::EXTRACT_SUBREG ||
2278
105
        POpc == TargetOpcode::INSERT_SUBREG ||
2279
105
        POpc == TargetOpcode::SUBREG_TO_REG) {
2280
2
      MVT VT = PN->getSimpleValueType(0);
2281
2
      unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
2282
2
      RegPressure[RCId] += TLI->getRepRegClassCostFor(VT);
2283
2
      continue;
2284
2
    }
2285
103
    unsigned NumDefs = TII->get(PN->getMachineOpcode()).getNumDefs();
2286
205
    for (unsigned i = 0; i != NumDefs; 
++i102
) {
2287
102
      MVT VT = PN->getSimpleValueType(i);
2288
102
      if (!PN->hasAnyUseOfValue(i))
2289
0
        continue;
2290
102
      unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
2291
102
      if (RegPressure[RCId] < TLI->getRepRegClassCostFor(VT))
2292
24
        // Register pressure tracking is imprecise. This can happen.
2293
24
        RegPressure[RCId] = 0;
2294
78
      else
2295
78
        RegPressure[RCId] -= TLI->getRepRegClassCostFor(VT);
2296
102
    }
2297
103
  }
2298
117
2299
117
  // Check for isMachineOpcode() as PrescheduleNodesWithMultipleUses()
2300
117
  // may transfer data dependencies to CopyToReg.
2301
117
  if (SU->NumSuccs && 
N->isMachineOpcode()67
) {
2302
67
    unsigned NumDefs = TII->get(N->getMachineOpcode()).getNumDefs();
2303
104
    for (unsigned i = NumDefs, e = N->getNumValues(); i != e; 
++i37
) {
2304
37
      MVT VT = N->getSimpleValueType(i);
2305
37
      if (VT == MVT::Glue || VT == MVT::Other)
2306
6
        continue;
2307
31
      if (!N->hasAnyUseOfValue(i))
2308
30
        continue;
2309
1
      unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
2310
1
      RegPressure[RCId] += TLI->getRepRegClassCostFor(VT);
2311
1
    }
2312
67
  }
2313
117
2314
117
  LLVM_DEBUG(dumpRegPressure());
2315
117
}
2316
2317
//===----------------------------------------------------------------------===//
2318
//           Dynamic Node Priority for Register Pressure Reduction
2319
//===----------------------------------------------------------------------===//
2320
2321
/// closestSucc - Returns the scheduled cycle of the successor which is
2322
/// closest to the current cycle.
2323
22.4M
static unsigned closestSucc(const SUnit *SU) {
2324
22.4M
  unsigned MaxHeight = 0;
2325
49.1M
  for (const SDep &Succ : SU->Succs) {
2326
49.1M
    if (Succ.isCtrl()) 
continue29.7M
; // ignore chain succs
2327
19.4M
    unsigned Height = Succ.getSUnit()->getHeight();
2328
19.4M
    // If there are bunch of CopyToRegs stacked up, they should be considered
2329
19.4M
    // to be at the same position.
2330
19.4M
    if (Succ.getSUnit()->getNode() &&
2331
19.4M
        Succ.getSUnit()->getNode()->getOpcode() == ISD::CopyToReg)
2332
1.02M
      Height = closestSucc(Succ.getSUnit())+1;
2333
19.4M
    if (Height > MaxHeight)
2334
15.8M
      MaxHeight = Height;
2335
19.4M
  }
2336
22.4M
  return MaxHeight;
2337
22.4M
}
2338
2339
/// calcMaxScratches - Returns an cost estimate of the worse case requirement
2340
/// for scratch registers, i.e. number of data dependencies.
2341
8.91M
static unsigned calcMaxScratches(const SUnit *SU) {
2342
8.91M
  unsigned Scratches = 0;
2343
15.6M
  for (const SDep &Pred : SU->Preds) {
2344
15.6M
    if (Pred.isCtrl()) 
continue3.90M
; // ignore chain preds
2345
11.7M
    Scratches++;
2346
11.7M
  }
2347
8.91M
  return Scratches;
2348
8.91M
}
2349
2350
/// hasOnlyLiveInOpers - Return true if SU has only value predecessors that are
2351
/// CopyFromReg from a virtual register.
2352
1.15M
static bool hasOnlyLiveInOpers(const SUnit *SU) {
2353
1.15M
  bool RetVal = false;
2354
1.28M
  for (const SDep &Pred : SU->Preds) {
2355
1.28M
    if (Pred.isCtrl()) 
continue381k
;
2356
899k
    const SUnit *PredSU = Pred.getSUnit();
2357
899k
    if (PredSU->getNode() &&
2358
899k
        PredSU->getNode()->getOpcode() == ISD::CopyFromReg) {
2359
244k
      unsigned Reg =
2360
244k
        cast<RegisterSDNode>(PredSU->getNode()->getOperand(1))->getReg();
2361
244k
      if (TargetRegisterInfo::isVirtualRegister(Reg)) {
2362
240k
        RetVal = true;
2363
240k
        continue;
2364
240k
      }
2365
659k
    }
2366
659k
    return false;
2367
659k
  }
2368
1.15M
  
return RetVal495k
;
2369
1.15M
}
2370
2371
/// hasOnlyLiveOutUses - Return true if SU has only value successors that are
2372
/// CopyToReg to a virtual register. This SU def is probably a liveout and
2373
/// it has no other use. It should be scheduled closer to the terminator.
2374
145k
static bool hasOnlyLiveOutUses(const SUnit *SU) {
2375
145k
  bool RetVal = false;
2376
171k
  for (const SDep &Succ : SU->Succs) {
2377
171k
    if (Succ.isCtrl()) 
continue46.5k
;
2378
124k
    const SUnit *SuccSU = Succ.getSUnit();
2379
124k
    if (SuccSU->getNode() && SuccSU->getNode()->getOpcode() == ISD::CopyToReg) {
2380
27.2k
      unsigned Reg =
2381
27.2k
        cast<RegisterSDNode>(SuccSU->getNode()->getOperand(1))->getReg();
2382
27.2k
      if (TargetRegisterInfo::isVirtualRegister(Reg)) {
2383
27.2k
        RetVal = true;
2384
27.2k
        continue;
2385
27.2k
      }
2386
97.5k
    }
2387
97.5k
    return false;
2388
97.5k
  }
2389
145k
  
return RetVal47.9k
;
2390
145k
}
2391
2392
// Set isVRegCycle for a node with only live in opers and live out uses. Also
2393
// set isVRegCycle for its CopyFromReg operands.
2394
//
2395
// This is only relevant for single-block loops, in which case the VRegCycle
2396
// node is likely an induction variable in which the operand and target virtual
2397
// registers should be coalesced (e.g. pre/post increment values). Setting the
2398
// isVRegCycle flag helps the scheduler prioritize other uses of the same
2399
// CopyFromReg so that this node becomes the virtual register "kill". This
2400
// avoids interference between the values live in and out of the block and
2401
// eliminates a copy inside the loop.
2402
1.15M
static void initVRegCycle(SUnit *SU) {
2403
1.15M
  if (DisableSchedVRegCycle)
2404
0
    return;
2405
1.15M
2406
1.15M
  if (!hasOnlyLiveInOpers(SU) || 
!hasOnlyLiveOutUses(SU)145k
)
2407
1.13M
    return;
2408
21.8k
2409
21.8k
  LLVM_DEBUG(dbgs() << "VRegCycle: SU(" << SU->NodeNum << ")\n");
2410
21.8k
2411
21.8k
  SU->isVRegCycle = true;
2412
21.8k
2413
22.7k
  for (const SDep &Pred : SU->Preds) {
2414
22.7k
    if (Pred.isCtrl()) 
continue71
;
2415
22.6k
    Pred.getSUnit()->isVRegCycle = true;
2416
22.6k
  }
2417
21.8k
}
2418
2419
// After scheduling the definition of a VRegCycle, clear the isVRegCycle flag of
2420
// CopyFromReg operands. We should no longer penalize other uses of this VReg.
2421
11.0M
static void resetVRegCycle(SUnit *SU) {
2422
11.0M
  if (!SU->isVRegCycle)
2423
11.0M
    return;
2424
21.8k
2425
22.7k
  
for (const SDep &Pred : SU->Preds)21.8k
{
2426
22.7k
    if (Pred.isCtrl()) 
continue71
; // ignore chain preds
2427
22.6k
    SUnit *PredSU = Pred.getSUnit();
2428
22.6k
    if (PredSU->isVRegCycle) {
2429
22.5k
      assert(PredSU->getNode()->getOpcode() == ISD::CopyFromReg &&
2430
22.5k
             "VRegCycle def must be CopyFromReg");
2431
22.5k
      Pred.getSUnit()->isVRegCycle = false;
2432
22.5k
    }
2433
22.6k
  }
2434
21.8k
}
2435
2436
// Return true if this SUnit uses a CopyFromReg node marked as a VRegCycle. This
2437
// means a node that defines the VRegCycle has not been scheduled yet.
2438
9.84M
static bool hasVRegCycleUse(const SUnit *SU) {
2439
9.84M
  // If this SU also defines the VReg, don't hoist it as a "use".
2440
9.84M
  if (SU->isVRegCycle)
2441
1.89k
    return false;
2442
9.84M
2443
16.5M
  
for (const SDep &Pred : SU->Preds)9.84M
{
2444
16.5M
    if (Pred.isCtrl()) 
continue4.10M
; // ignore chain preds
2445
12.4M
    if (Pred.getSUnit()->isVRegCycle &&
2446
12.4M
        
Pred.getSUnit()->getNode()->getOpcode() == ISD::CopyFromReg3.76k
) {
2447
1.18k
      LLVM_DEBUG(dbgs() << "  VReg cycle use: SU (" << SU->NodeNum << ")\n");
2448
1.18k
      return true;
2449
1.18k
    }
2450
12.4M
  }
2451
9.84M
  
return false9.84M
;
2452
9.84M
}
2453
2454
// Check for either a dependence (latency) or resource (hazard) stall.
2455
//
2456
// Note: The ScheduleHazardRecognizer interface requires a non-const SU.
2457
8.98M
static bool BUHasStall(SUnit *SU, int Height, RegReductionPQBase *SPQ) {
2458
8.98M
  if ((int)SPQ->getCurCycle() < Height) 
return true217k
;
2459
8.77M
  if (SPQ->getHazardRec()->getHazardType(SU, 0)
2460
8.77M
      != ScheduleHazardRecognizer::NoHazard)
2461
159k
    return true;
2462
8.61M
  return false;
2463
8.61M
}
2464
2465
// Return -1 if left has higher priority, 1 if right has higher priority.
2466
// Return 0 if latency-based priority is equivalent.
2467
static int BUCompareLatency(SUnit *left, SUnit *right, bool checkPref,
2468
4.92M
                            RegReductionPQBase *SPQ) {
2469
4.92M
  // Scheduling an instruction that uses a VReg whose postincrement has not yet
2470
4.92M
  // been scheduled will induce a copy. Model this as an extra cycle of latency.
2471
4.92M
  int LPenalty = hasVRegCycleUse(left) ? 
1516
:
04.92M
;
2472
4.92M
  int RPenalty = hasVRegCycleUse(right) ? 
1673
:
04.92M
;
2473
4.92M
  int LHeight = (int)left->getHeight() + LPenalty;
2474
4.92M
  int RHeight = (int)right->getHeight() + RPenalty;
2475
4.92M
2476
4.92M
  bool LStall = (!checkPref || 
left->SchedulingPref == Sched::ILP546k
) &&
2477
4.92M
    
BUHasStall(left, LHeight, SPQ)4.50M
;
2478
4.92M
  bool RStall = (!checkPref || 
right->SchedulingPref == Sched::ILP546k
) &&
2479
4.92M
    
BUHasStall(right, RHeight, SPQ)4.48M
;
2480
4.92M
2481
4.92M
  // If scheduling one of the node will cause a pipeline stall, delay it.
2482
4.92M
  // If scheduling either one of the node will cause a pipeline stall, sort
2483
4.92M
  // them according to their height.
2484
4.92M
  if (LStall) {
2485
187k
    if (!RStall)
2486
47.7k
      return 1;
2487
140k
    if (LHeight != RHeight)
2488
11.7k
      return LHeight > RHeight ? 
12.98k
:
-18.78k
;
2489
4.73M
  } else if (RStall)
2490
48.5k
    return -1;
2491
4.81M
2492
4.81M
  // If either node is scheduling for latency, sort them by height/depth
2493
4.81M
  // and latency.
2494
4.81M
  if (!checkPref || 
(441k
left->SchedulingPref == Sched::ILP441k
||
2495
4.45M
                     
right->SchedulingPref == Sched::ILP377k
)) {
2496
4.45M
    // If neither instruction stalls (!LStall && !RStall) and HazardRecognizer
2497
4.45M
    // is enabled, grouping instructions by cycle, then its height is already
2498
4.45M
    // covered so only its depth matters. We also reach this point if both stall
2499
4.45M
    // but have the same height.
2500
4.45M
    if (!SPQ->getHazardRec()->isEnabled()) {
2501
4.12M
      if (LHeight != RHeight)
2502
499k
        return LHeight > RHeight ? 
1360k
:
-1139k
;
2503
3.95M
    }
2504
3.95M
    int LDepth = left->getDepth() - LPenalty;
2505
3.95M
    int RDepth = right->getDepth() - RPenalty;
2506
3.95M
    if (LDepth != RDepth) {
2507
353k
      LLVM_DEBUG(dbgs() << "  Comparing latency of SU (" << left->NodeNum
2508
353k
                        << ") depth " << LDepth << " vs SU (" << right->NodeNum
2509
353k
                        << ") depth " << RDepth << "\n");
2510
353k
      return LDepth < RDepth ? 
1159k
:
-1193k
;
2511
353k
    }
2512
3.59M
    if (left->Latency != right->Latency)
2513
25.1k
      return left->Latency > right->Latency ? 
118.1k
:
-16.95k
;
2514
3.93M
  }
2515
3.93M
  return 0;
2516
3.93M
}
2517
2518
12.1M
static bool BURRSort(SUnit *left, SUnit *right, RegReductionPQBase *SPQ) {
2519
12.1M
  // Schedule physical register definitions close to their use. This is
2520
12.1M
  // motivated by microarchitectures that can fuse cmp+jump macro-ops. But as
2521
12.1M
  // long as shortening physreg live ranges is generally good, we can defer
2522
12.1M
  // creating a subtarget hook.
2523
12.1M
  if (!DisableSchedPhysRegJoin) {
2524
12.1M
    bool LHasPhysReg = left->hasPhysRegDefs;
2525
12.1M
    bool RHasPhysReg = right->hasPhysRegDefs;
2526
12.1M
    if (LHasPhysReg != RHasPhysReg) {
2527
      #ifndef NDEBUG
2528
      static const char *const PhysRegMsg[] = { " has no physreg",
2529
                                                " defines a physreg" };
2530
      #endif
2531
46.0k
      LLVM_DEBUG(dbgs() << "  SU (" << left->NodeNum << ") "
2532
46.0k
                        << PhysRegMsg[LHasPhysReg] << " SU(" << right->NodeNum
2533
46.0k
                        << ") " << PhysRegMsg[RHasPhysReg] << "\n");
2534
46.0k
      return LHasPhysReg < RHasPhysReg;
2535
46.0k
    }
2536
12.0M
  }
2537
12.0M
2538
12.0M
  // Prioritize by Sethi-Ulmann number and push CopyToReg nodes down.
2539
12.0M
  unsigned LPriority = SPQ->getNodePriority(left);
2540
12.0M
  unsigned RPriority = SPQ->getNodePriority(right);
2541
12.0M
2542
12.0M
  // Be really careful about hoisting call operands above previous calls.
2543
12.0M
  // Only allows it if it would reduce register pressure.
2544
12.0M
  if (left->isCall && 
right->isCallOp20.6k
) {
2545
2.38k
    unsigned RNumVals = right->getNode()->getNumValues();
2546
2.38k
    RPriority = (RPriority > RNumVals) ? 
(RPriority - RNumVals)592
:
01.79k
;
2547
2.38k
  }
2548
12.0M
  if (right->isCall && 
left->isCallOp54.8k
) {
2549
2.80k
    unsigned LNumVals = left->getNode()->getNumValues();
2550
2.80k
    LPriority = (LPriority > LNumVals) ? 
(LPriority - LNumVals)506
:
02.29k
;
2551
2.80k
  }
2552
12.0M
2553
12.0M
  if (LPriority != RPriority)
2554
1.35M
    return LPriority > RPriority;
2555
10.7M
2556
10.7M
  // One or both of the nodes are calls and their sethi-ullman numbers are the
2557
10.7M
  // same, then keep source order.
2558
10.7M
  if (left->isCall || 
right->isCall10.6M
) {
2559
10.5k
    unsigned LOrder = SPQ->getNodeOrdering(left);
2560
10.5k
    unsigned ROrder = SPQ->getNodeOrdering(right);
2561
10.5k
2562
10.5k
    // Prefer an ordering where the lower the non-zero order number, the higher
2563
10.5k
    // the preference.
2564
10.5k
    if ((LOrder || 
ROrder52
) && LOrder != ROrder)
2565
3.95k
      return LOrder != 0 && 
(3.90k
LOrder < ROrder3.90k
||
ROrder == 01.98k
);
2566
10.7M
  }
2567
10.7M
2568
10.7M
  // Try schedule def + use closer when Sethi-Ullman numbers are the same.
2569
10.7M
  // e.g.
2570
10.7M
  // t1 = op t2, c1
2571
10.7M
  // t3 = op t4, c2
2572
10.7M
  //
2573
10.7M
  // and the following instructions are both ready.
2574
10.7M
  // t2 = op c3
2575
10.7M
  // t4 = op c4
2576
10.7M
  //
2577
10.7M
  // Then schedule t2 = op first.
2578
10.7M
  // i.e.
2579
10.7M
  // t4 = op c4
2580
10.7M
  // t2 = op c3
2581
10.7M
  // t1 = op t2, c1
2582
10.7M
  // t3 = op t4, c2
2583
10.7M
  //
2584
10.7M
  // This creates more short live intervals.
2585
10.7M
  unsigned LDist = closestSucc(left);
2586
10.7M
  unsigned RDist = closestSucc(right);
2587
10.7M
  if (LDist != RDist)
2588
6.24M
    return LDist < RDist;
2589
4.45M
2590
4.45M
  // How many registers becomes live when the node is scheduled.
2591
4.45M
  unsigned LScratch = calcMaxScratches(left);
2592
4.45M
  unsigned RScratch = calcMaxScratches(right);
2593
4.45M
  if (LScratch != RScratch)
2594
78.6k
    return LScratch > RScratch;
2595
4.37M
2596
4.37M
  // Comparing latency against a call makes little sense unless the node
2597
4.37M
  // is register pressure-neutral.
2598
4.37M
  if ((left->isCall && 
RPriority > 0787
) ||
(4.37M
right->isCall4.37M
&&
LPriority > 069
))
2599
752
    return (left->NodeQueueId > right->NodeQueueId);
2600
4.37M
2601
4.37M
  // Do not compare latencies when one or both of the nodes are calls.
2602
4.37M
  if (!DisableSchedCycles &&
2603
4.37M
      !(left->isCall || 
right->isCall4.37M
)) {
2604
4.37M
    int result = BUCompareLatency(left, right, false /*checkPref*/, SPQ);
2605
4.37M
    if (result != 0)
2606
834k
      return result > 0;
2607
65
  }
2608
65
  else {
2609
65
    if (left->getHeight() != right->getHeight())
2610
0
      return left->getHeight() > right->getHeight();
2611
65
2612
65
    if (left->getDepth() != right->getDepth())
2613
28
      return left->getDepth() < right->getDepth();
2614
3.54M
  }
2615
3.54M
2616
3.54M
  assert(left->NodeQueueId && right->NodeQueueId &&
2617
3.54M
         "NodeQueueId cannot be zero");
2618
3.54M
  return (left->NodeQueueId > right->NodeQueueId);
2619
3.54M
}
2620
2621
// Bottom up
2622
233k
bool bu_ls_rr_sort::operator()(SUnit *left, SUnit *right) const {
2623
233k
  if (int res = checkSpecialNodes(left, right))
2624
1.34k
    return res > 0;
2625
231k
2626
231k
  return BURRSort(left, right, SPQ);
2627
231k
}
2628
2629
// Source order, otherwise bottom up.
2630
34.5M
bool src_ls_rr_sort::operator()(SUnit *left, SUnit *right) const {
2631
34.5M
  if (int res = checkSpecialNodes(left, right))
2632
191k
    return res > 0;
2633
34.3M
2634
34.3M
  unsigned LOrder = SPQ->getNodeOrdering(left);
2635
34.3M
  unsigned ROrder = SPQ->getNodeOrdering(right);
2636
34.3M
2637
34.3M
  // Prefer an ordering where the lower the non-zero order number, the higher
2638
34.3M
  // the preference.
2639
34.3M
  if ((LOrder || 
ROrder608k
) &&
LOrder != ROrder34.2M
)
2640
23.1M
    return LOrder != 0 && 
(22.6M
LOrder < ROrder22.6M
||
ROrder == 014.7M
);
2641
11.2M
2642
11.2M
  return BURRSort(left, right, SPQ);
2643
11.2M
}
2644
2645
// If the time between now and when the instruction will be ready can cover
2646
// the spill code, then avoid adding it to the ready queue. This gives long
2647
// stalls highest priority and allows hoisting across calls. It should also
2648
// speed up processing the available queue.
2649
0
bool hybrid_ls_rr_sort::isReady(SUnit *SU, unsigned CurCycle) const {
2650
0
  static const unsigned ReadyDelay = 3;
2651
0
2652
0
  if (SPQ->MayReduceRegPressure(SU)) return true;
2653
0
2654
0
  if (SU->getHeight() > (CurCycle + ReadyDelay)) return false;
2655
0
2656
0
  if (SPQ->getHazardRec()->getHazardType(SU, -ReadyDelay)
2657
0
      != ScheduleHazardRecognizer::NoHazard)
2658
0
    return false;
2659
0
2660
0
  return true;
2661
0
}
2662
2663
// Return true if right should be scheduled with higher priority than left.
2664
606k
bool hybrid_ls_rr_sort::operator()(SUnit *left, SUnit *right) const {
2665
606k
  if (int res = checkSpecialNodes(left, right))
2666
15.9k
    return res > 0;
2667
590k
2668
590k
  if (left->isCall || 
right->isCall586k
)
2669
14.3k
    // No way to compute latency of calls.
2670
14.3k
    return BURRSort(left, right, SPQ);
2671
576k
2672
576k
  bool LHigh = SPQ->HighRegPressure(left);
2673
576k
  bool RHigh = SPQ->HighRegPressure(right);
2674
576k
  // Avoid causing spills. If register pressure is high, schedule for
2675
576k
  // register pressure reduction.
2676
576k
  if (LHigh && 
!RHigh15.9k
) {
2677
4.66k
    LLVM_DEBUG(dbgs() << "  pressure SU(" << left->NodeNum << ") > SU("
2678
4.66k
                      << right->NodeNum << ")\n");
2679
4.66k
    return true;
2680
4.66k
  }
2681
571k
  else if (!LHigh && 
RHigh560k
) {
2682
13.7k
    LLVM_DEBUG(dbgs() << "  pressure SU(" << right->NodeNum << ") > SU("
2683
13.7k
                      << left->NodeNum << ")\n");
2684
13.7k
    return false;
2685
13.7k
  }
2686
558k
  if (!LHigh && 
!RHigh546k
) {
2687
546k
    int result = BUCompareLatency(left, right, true /*checkPref*/, SPQ);
2688
546k
    if (result != 0)
2689
151k
      return result > 0;
2690
406k
  }
2691
406k
  return BURRSort(left, right, SPQ);
2692
406k
}
2693
2694
// Schedule as many instructions in each cycle as possible. So don't make an
2695
// instruction available unless it is ready in the current cycle.
2696
0
bool ilp_ls_rr_sort::isReady(SUnit *SU, unsigned CurCycle) const {
2697
0
  if (SU->getHeight() > CurCycle) return false;
2698
0
2699
0
  if (SPQ->getHazardRec()->getHazardType(SU, 0)
2700
0
      != ScheduleHazardRecognizer::NoHazard)
2701
0
    return false;
2702
0
2703
0
  return true;
2704
0
}
2705
2706
88.9k
static bool canEnableCoalescing(SUnit *SU) {
2707
88.9k
  unsigned Opc = SU->getNode() ? SU->getNode()->getOpcode() : 
00
;
2708
88.9k
  if (Opc == ISD::TokenFactor || Opc == ISD::CopyToReg)
2709
7.84k
    // CopyToReg should be close to its uses to facilitate coalescing and
2710
7.84k
    // avoid spilling.
2711
7.84k
    return true;
2712
81.1k
2713
81.1k
  if (Opc == TargetOpcode::EXTRACT_SUBREG ||
2714
81.1k
      Opc == TargetOpcode::SUBREG_TO_REG ||
2715
81.1k
      Opc == TargetOpcode::INSERT_SUBREG)
2716
0
    // EXTRACT_SUBREG, INSERT_SUBREG, and SUBREG_TO_REG nodes should be
2717
0
    // close to their uses to facilitate coalescing.
2718
0
    return true;
2719
81.1k
2720
81.1k
  if (SU->NumPreds == 0 && 
SU->NumSuccs != 00
)
2721
0
    // If SU does not have a register def, schedule it close to its uses
2722
0
    // because it does not lengthen any live ranges.
2723
0
    return true;
2724
81.1k
2725
81.1k
  return false;
2726
81.1k
}
2727
2728
// list-ilp is currently an experimental scheduler that allows various
2729
// heuristics to be enabled prior to the normal register reduction logic.
2730
224k
bool ilp_ls_rr_sort::operator()(SUnit *left, SUnit *right) const {
2731
224k
  if (int res = checkSpecialNodes(left, right))
2732
2.34k
    return res > 0;
2733
221k
2734
221k
  if (left->isCall || 
right->isCall219k
)
2735
3.94k
    // No way to compute latency of calls.
2736
3.94k
    return BURRSort(left, right, SPQ);
2737
217k
2738
217k
  unsigned LLiveUses = 0, RLiveUses = 0;
2739
217k
  int LPDiff = 0, RPDiff = 0;
2740
217k
  if (!DisableSchedRegPressure || 
!DisableSchedLiveUses0
) {
2741
217k
    LPDiff = SPQ->RegPressureDiff(left, LLiveUses);
2742
217k
    RPDiff = SPQ->RegPressureDiff(right, RLiveUses);
2743
217k
  }
2744
217k
  if (!DisableSchedRegPressure && LPDiff != RPDiff) {
2745
30.5k
    LLVM_DEBUG(dbgs() << "RegPressureDiff SU(" << left->NodeNum
2746
30.5k
                      << "): " << LPDiff << " != SU(" << right->NodeNum
2747
30.5k
                      << "): " << RPDiff << "\n");
2748
30.5k
    return LPDiff > RPDiff;
2749
30.5k
  }
2750
187k
2751
187k
  if (!DisableSchedRegPressure && (LPDiff > 0 || 
RPDiff > 0142k
)) {
2752
44.4k
    bool LReduce = canEnableCoalescing(left);
2753
44.4k
    bool RReduce = canEnableCoalescing(right);
2754
44.4k
    if (LReduce && 
!RReduce4.01k
)
return false224
;
2755
44.2k
    if (RReduce && 
!LReduce3.83k
)
return true42
;
2756
187k
  }
2757
187k
2758
187k
  if (!DisableSchedLiveUses && 
(LLiveUses != RLiveUses)0
) {
2759
0
    LLVM_DEBUG(dbgs() << "Live uses SU(" << left->NodeNum << "): " << LLiveUses
2760
0
                      << " != SU(" << right->NodeNum << "): " << RLiveUses
2761
0
                      << "\n");
2762
0
    return LLiveUses < RLiveUses;
2763
0
  }
2764
187k
2765
187k
  if (!DisableSchedStalls) {
2766
0
    bool LStall = BUHasStall(left, left->getHeight(), SPQ);
2767
0
    bool RStall = BUHasStall(right, right->getHeight(), SPQ);
2768
0
    if (LStall != RStall)
2769
0
      return left->getHeight() > right->getHeight();
2770
187k
  }
2771
187k
2772
187k
  if (!DisableSchedCriticalPath) {
2773
187k
    int spread = (int)left->getDepth() - (int)right->getDepth();
2774
187k
    if (std::abs(spread) > MaxReorderWindow) {
2775
2.53k
      LLVM_DEBUG(dbgs() << "Depth of SU(" << left->NodeNum << "): "
2776
2.53k
                        << left->getDepth() << " != SU(" << right->NodeNum
2777
2.53k
                        << "): " << right->getDepth() << "\n");
2778
2.53k
      return left->getDepth() < right->getDepth();
2779
2.53k
    }
2780
184k
  }
2781
184k
2782
184k
  if (!DisableSchedHeight && left->getHeight() != right->getHeight()) {
2783
49.8k
    int spread = (int)left->getHeight() - (int)right->getHeight();
2784
49.8k
    if (std::abs(spread) > MaxReorderWindow)
2785
8.72k
      return left->getHeight() > right->getHeight();
2786
175k
  }
2787
175k
2788
175k
  return BURRSort(left, right, SPQ);
2789
175k
}
2790
2791
1.24M
void RegReductionPQBase::initNodes(std::vector<SUnit> &sunits) {
2792
1.24M
  SUnits = &sunits;
2793
1.24M
  // Add pseudo dependency edges for two-address nodes.
2794
1.24M
  if (!Disable2AddrHack)
2795
0
    AddPseudoTwoAddrDeps();
2796
1.24M
  // Reroute edges to nodes with multiple uses.
2797
1.24M
  if (!TracksRegPressure && 
!SrcOrder1.16M
)
2798
19.7k
    PrescheduleNodesWithMultipleUses();
2799
1.24M
  // Calculate node priorities.
2800
1.24M
  CalculateSethiUllmanNumbers();
2801
1.24M
2802
1.24M
  // For single block loops, mark nodes that look like canonical IV increments.
2803
1.24M
  if (scheduleDAG->BB->isSuccessor(scheduleDAG->BB))
2804
59.6k
    for (SUnit &SU : sunits)
2805
1.15M
      initVRegCycle(&SU);
2806
1.24M
}
2807
2808
//===----------------------------------------------------------------------===//
2809
//                    Preschedule for Register Pressure
2810
//===----------------------------------------------------------------------===//
2811
2812
0
bool RegReductionPQBase::canClobber(const SUnit *SU, const SUnit *Op) {
2813
0
  if (SU->isTwoAddress) {
2814
0
    unsigned Opc = SU->getNode()->getMachineOpcode();
2815
0
    const MCInstrDesc &MCID = TII->get(Opc);
2816
0
    unsigned NumRes = MCID.getNumDefs();
2817
0
    unsigned NumOps = MCID.getNumOperands() - NumRes;
2818
0
    for (unsigned i = 0; i != NumOps; ++i) {
2819
0
      if (MCID.getOperandConstraint(i+NumRes, MCOI::TIED_TO) != -1) {
2820
0
        SDNode *DU = SU->getNode()->getOperand(i).getNode();
2821
0
        if (DU->getNodeId() != -1 &&
2822
0
            Op->OrigNode == &(*SUnits)[DU->getNodeId()])
2823
0
          return true;
2824
0
      }
2825
0
    }
2826
0
  }
2827
0
  return false;
2828
0
}
2829
2830
/// canClobberReachingPhysRegUse - True if SU would clobber one of it's
2831
/// successor's explicit physregs whose definition can reach DepSU.
2832
/// i.e. DepSU should not be scheduled above SU.
2833
static bool canClobberReachingPhysRegUse(const SUnit *DepSU, const SUnit *SU,
2834
                                         ScheduleDAGRRList *scheduleDAG,
2835
                                         const TargetInstrInfo *TII,
2836
0
                                         const TargetRegisterInfo *TRI) {
2837
0
  const MCPhysReg *ImpDefs
2838
0
    = TII->get(SU->getNode()->getMachineOpcode()).getImplicitDefs();
2839
0
  const uint32_t *RegMask = getNodeRegMask(SU->getNode());
2840
0
  if(!ImpDefs && !RegMask)
2841
0
    return false;
2842
0
2843
0
  for (const SDep &Succ : SU->Succs) {
2844
0
    SUnit *SuccSU = Succ.getSUnit();
2845
0
    for (const SDep &SuccPred : SuccSU->Preds) {
2846
0
      if (!SuccPred.isAssignedRegDep())
2847
0
        continue;
2848
0
2849
0
      if (RegMask &&
2850
0
          MachineOperand::clobbersPhysReg(RegMask, SuccPred.getReg()) &&
2851
0
          scheduleDAG->IsReachable(DepSU, SuccPred.getSUnit()))
2852
0
        return true;
2853
0
2854
0
      if (ImpDefs)
2855
0
        for (const MCPhysReg *ImpDef = ImpDefs; *ImpDef; ++ImpDef)
2856
0
          // Return true if SU clobbers this physical register use and the
2857
0
          // definition of the register reaches from DepSU. IsReachable queries
2858
0
          // a topological forward sort of the DAG (following the successors).
2859
0
          if (TRI->regsOverlap(*ImpDef, SuccPred.getReg()) &&
2860
0
              scheduleDAG->IsReachable(DepSU, SuccPred.getSUnit()))
2861
0
            return true;
2862
0
    }
2863
0
  }
2864
0
  return false;
2865
0
}
2866
2867
/// canClobberPhysRegDefs - True if SU would clobber one of SuccSU's
2868
/// physical register defs.
2869
static bool canClobberPhysRegDefs(const SUnit *SuccSU, const SUnit *SU,
2870
                                  const TargetInstrInfo *TII,
2871
1
                                  const TargetRegisterInfo *TRI) {
2872
1
  SDNode *N = SuccSU->getNode();
2873
1
  unsigned NumDefs = TII->get(N->getMachineOpcode()).getNumDefs();
2874
1
  const MCPhysReg *ImpDefs = TII->get(N->getMachineOpcode()).getImplicitDefs();
2875
1
  assert(ImpDefs && "Caller should check hasPhysRegDefs");
2876
2
  for (const SDNode *SUNode = SU->getNode(); SUNode;
2877
2
       
SUNode = SUNode->getGluedNode()1
) {
2878
2
    if (!SUNode->isMachineOpcode())
2879
0
      continue;
2880
2
    const MCPhysReg *SUImpDefs =
2881
2
      TII->get(SUNode->getMachineOpcode()).getImplicitDefs();
2882
2
    const uint32_t *SURegMask = getNodeRegMask(SUNode);
2883
2
    if (!SUImpDefs && 
!SURegMask1
)
2884
1
      continue;
2885
1
    for (unsigned i = NumDefs, e = N->getNumValues(); i != e; 
++i0
) {
2886
1
      MVT VT = N->getSimpleValueType(i);
2887
1
      if (VT == MVT::Glue || VT == MVT::Other)
2888
0
        continue;
2889
1
      if (!N->hasAnyUseOfValue(i))
2890
0
        continue;
2891
1
      unsigned Reg = ImpDefs[i - NumDefs];
2892
1
      if (SURegMask && 
MachineOperand::clobbersPhysReg(SURegMask, Reg)0
)
2893
0
        return true;
2894
1
      if (!SUImpDefs)
2895
0
        continue;
2896
1
      for (;*SUImpDefs; 
++SUImpDefs0
) {
2897
1
        unsigned SUReg = *SUImpDefs;
2898
1
        if (TRI->regsOverlap(Reg, SUReg))
2899
1
          return true;
2900
1
      }
2901
1
    }
2902
1
  }
2903
1
  
return false0
;
2904
1
}
2905
2906
/// PrescheduleNodesWithMultipleUses - Nodes with multiple uses
2907
/// are not handled well by the general register pressure reduction
2908
/// heuristics. When presented with code like this:
2909
///
2910
///      N
2911
///    / |
2912
///   /  |
2913
///  U  store
2914
///  |
2915
/// ...
2916
///
2917
/// the heuristics tend to push the store up, but since the
2918
/// operand of the store has another use (U), this would increase
2919
/// the length of that other use (the U->N edge).
2920
///
2921
/// This function transforms code like the above to route U's
2922
/// dependence through the store when possible, like this:
2923
///
2924
///      N
2925
///      ||
2926
///      ||
2927
///     store
2928
///       |
2929
///       U
2930
///       |
2931
///      ...
2932
///
2933
/// This results in the store being scheduled immediately
2934
/// after N, which shortens the U->N live range, reducing
2935
/// register pressure.
2936
19.7k
void RegReductionPQBase::PrescheduleNodesWithMultipleUses() {
2937
19.7k
  // Visit all the nodes in topological order, working top-down.
2938
163k
  for (SUnit &SU : *SUnits) {
2939
163k
    // For now, only look at nodes with no data successors, such as stores.
2940
163k
    // These are especially important, due to the heuristics in
2941
163k
    // getNodePriority for nodes with no data successors.
2942
163k
    if (SU.NumSuccs != 0)
2943
104k
      continue;
2944
58.7k
    // For now, only look at nodes with exactly one data predecessor.
2945
58.7k
    if (SU.NumPreds != 1)
2946
31.2k
      continue;
2947
27.4k
    // Avoid prescheduling copies to virtual registers, which don't behave
2948
27.4k
    // like other nodes from the perspective of scheduling heuristics.
2949
27.4k
    if (SDNode *N = SU.getNode())
2950
27.4k
      if (N->getOpcode() == ISD::CopyToReg &&
2951
27.4k
          TargetRegisterInfo::isVirtualRegister
2952
14.5k
            (cast<RegisterSDNode>(N->getOperand(1))->getReg()))
2953
14.4k
        continue;
2954
12.9k
2955
12.9k
    SDNode *PredFrameSetup = nullptr;
2956
12.9k
    for (const SDep &Pred : SU.Preds)
2957
16.9k
      if (Pred.isCtrl() && 
Pred.getSUnit()4.28k
) {
2958
4.28k
        // Find the predecessor which is not data dependence.
2959
4.28k
        SDNode *PredND = Pred.getSUnit()->getNode();
2960
4.28k
2961
4.28k
        // If PredND is FrameSetup, we should not pre-scheduled the node,
2962
4.28k
        // or else, when bottom up scheduling, ADJCALLSTACKDOWN and
2963
4.28k
        // ADJCALLSTACKUP may hold CallResource too long and make other
2964
4.28k
        // calls can't be scheduled. If there's no other available node
2965
4.28k
        // to schedule, the schedular will try to rename the register by
2966
4.28k
        // creating copy to avoid the conflict which will fail because
2967
4.28k
        // CallResource is not a real physical register.
2968
4.28k
        if (PredND && PredND->isMachineOpcode() &&
2969
4.28k
            
(PredND->getMachineOpcode() == TII->getCallFrameSetupOpcode())1.81k
) {
2970
425
          PredFrameSetup = PredND;
2971
425
          break;
2972
425
        }
2973
4.28k
      }
2974
12.9k
    // Skip the node has FrameSetup parent.
2975
12.9k
    if (PredFrameSetup != nullptr)
2976
425
      continue;
2977
12.5k
2978
12.5k
    // Locate the single data predecessor.
2979
12.5k
    SUnit *PredSU = nullptr;
2980
12.5k
    for (const SDep &Pred : SU.Preds)
2981
15.0k
      if (!Pred.isCtrl()) {
2982
12.5k
        PredSU = Pred.getSUnit();
2983
12.5k
        break;
2984
12.5k
      }
2985
12.5k
    assert(PredSU);
2986
12.5k
2987
12.5k
    // Don't rewrite edges that carry physregs, because that requires additional
2988
12.5k
    // support infrastructure.
2989
12.5k
    if (PredSU->hasPhysRegDefs)
2990
424
      continue;
2991
12.1k
    // Short-circuit the case where SU is PredSU's only data successor.
2992
12.1k
    if (PredSU->NumSuccs == 1)
2993
10.2k
      continue;
2994
1.84k
    // Avoid prescheduling to copies from virtual registers, which don't behave
2995
1.84k
    // like other nodes from the perspective of scheduling heuristics.
2996
1.84k
    if (SDNode *N = SU.getNode())
2997
1.84k
      if (N->getOpcode() == ISD::CopyFromReg &&
2998
1.84k
          TargetRegisterInfo::isVirtualRegister
2999
0
            (cast<RegisterSDNode>(N->getOperand(1))->getReg()))
3000
0
        continue;
3001
1.84k
3002
1.84k
    // Perform checks on the successors of PredSU.
3003
3.61k
    
for (const SDep &PredSucc : PredSU->Succs)1.84k
{
3004
3.61k
      SUnit *PredSuccSU = PredSucc.getSUnit();
3005
3.61k
      if (PredSuccSU == &SU) 
continue1.58k
;
3006
2.03k
      // If PredSU has another successor with no data successors, for
3007
2.03k
      // now don't attempt to choose either over the other.
3008
2.03k
      if (PredSuccSU->NumSuccs == 0)
3009
1.48k
        goto outer_loop_continue;
3010
546
      // Don't break physical register dependencies.
3011
546
      if (SU.hasPhysRegClobbers && 
PredSuccSU->hasPhysRegDefs159
)
3012
1
        if (canClobberPhysRegDefs(PredSuccSU, &SU, TII, TRI))
3013
1
          goto outer_loop_continue;
3014
545
      // Don't introduce graph cycles.
3015
545
      if (scheduleDAG->IsReachable(&SU, PredSuccSU))
3016
263
        goto outer_loop_continue;
3017
545
    }
3018
1.84k
3019
1.84k
    // Ok, the transformation is safe and the heuristics suggest it is
3020
1.84k
    // profitable. Update the graph.
3021
1.84k
    
LLVM_DEBUG92
(
3022
92
        dbgs() << "    Prescheduling SU #" << SU.NodeNum << " next to PredSU #"
3023
92
               << PredSU->NodeNum
3024
92
               << " to guide scheduling in the presence of multiple uses\n");
3025
330
    for (unsigned i = 0; i != PredSU->Succs.size(); 
++i238
) {
3026
238
      SDep Edge = PredSU->Succs[i];
3027
238
      assert(!Edge.isAssignedRegDep());
3028
238
      SUnit *SuccSU = Edge.getSUnit();
3029
238
      if (SuccSU != &SU) {
3030
136
        Edge.setSUnit(PredSU);
3031
136
        scheduleDAG->RemovePred(SuccSU, Edge);
3032
136
        scheduleDAG->AddPredQueued(&SU, Edge);
3033
136
        Edge.setSUnit(&SU);
3034
136
        scheduleDAG->AddPredQueued(SuccSU, Edge);
3035
136
        --i;
3036
136
      }
3037
238
    }
3038
1.84k
  outer_loop_continue:;
3039
1.84k
  }
3040
19.7k
}
3041
3042
/// AddPseudoTwoAddrDeps - If two nodes share an operand and one of them uses
3043
/// it as a def&use operand. Add a pseudo control edge from it to the other
3044
/// node (if it won't create a cycle) so the two-address one will be scheduled
3045
/// first (lower in the schedule). If both nodes are two-address, favor the
3046
/// one that has a CopyToReg use (more likely to be a loop induction update).
3047
/// If both are two-address, but one is commutable while the other is not
3048
/// commutable, favor the one that's not commutable.
3049
0
void RegReductionPQBase::AddPseudoTwoAddrDeps() {
3050
0
  for (SUnit &SU : *SUnits) {
3051
0
    if (!SU.isTwoAddress)
3052
0
      continue;
3053
0
3054
0
    SDNode *Node = SU.getNode();
3055
0
    if (!Node || !Node->isMachineOpcode() || SU.getNode()->getGluedNode())
3056
0
      continue;
3057
0
3058
0
    bool isLiveOut = hasOnlyLiveOutUses(&SU);
3059
0
    unsigned Opc = Node->getMachineOpcode();
3060
0
    const MCInstrDesc &MCID = TII->get(Opc);
3061
0
    unsigned NumRes = MCID.getNumDefs();
3062
0
    unsigned NumOps = MCID.getNumOperands() - NumRes;
3063
0
    for (unsigned j = 0; j != NumOps; ++j) {
3064
0
      if (MCID.getOperandConstraint(j+NumRes, MCOI::TIED_TO) == -1)
3065
0
        continue;
3066
0
      SDNode *DU = SU.getNode()->getOperand(j).getNode();
3067
0
      if (DU->getNodeId() == -1)
3068
0
        continue;
3069
0
      const SUnit *DUSU = &(*SUnits)[DU->getNodeId()];
3070
0
      if (!DUSU)
3071
0
        continue;
3072
0
      for (const SDep &Succ : DUSU->Succs) {
3073
0
        if (Succ.isCtrl())
3074
0
          continue;
3075
0
        SUnit *SuccSU = Succ.getSUnit();
3076
0
        if (SuccSU == &SU)
3077
0
          continue;
3078
0
        // Be conservative. Ignore if nodes aren't at roughly the same
3079
0
        // depth and height.
3080
0
        if (SuccSU->getHeight() < SU.getHeight() &&
3081
0
            (SU.getHeight() - SuccSU->getHeight()) > 1)
3082
0
          continue;
3083
0
        // Skip past COPY_TO_REGCLASS nodes, so that the pseudo edge
3084
0
        // constrains whatever is using the copy, instead of the copy
3085
0
        // itself. In the case that the copy is coalesced, this
3086
0
        // preserves the intent of the pseudo two-address heurietics.
3087
0
        while (SuccSU->Succs.size() == 1 &&
3088
0
               SuccSU->getNode()->isMachineOpcode() &&
3089
0
               SuccSU->getNode()->getMachineOpcode() ==
3090
0
                 TargetOpcode::COPY_TO_REGCLASS)
3091
0
          SuccSU = SuccSU->Succs.front().getSUnit();
3092
0
        // Don't constrain non-instruction nodes.
3093
0
        if (!SuccSU->getNode() || !SuccSU->getNode()->isMachineOpcode())
3094
0
          continue;
3095
0
        // Don't constrain nodes with physical register defs if the
3096
0
        // predecessor can clobber them.
3097
0
        if (SuccSU->hasPhysRegDefs && SU.hasPhysRegClobbers) {
3098
0
          if (canClobberPhysRegDefs(SuccSU, &SU, TII, TRI))
3099
0
            continue;
3100
0
        }
3101
0
        // Don't constrain EXTRACT_SUBREG, INSERT_SUBREG, and SUBREG_TO_REG;
3102
0
        // these may be coalesced away. We want them close to their uses.
3103
0
        unsigned SuccOpc = SuccSU->getNode()->getMachineOpcode();
3104
0
        if (SuccOpc == TargetOpcode::EXTRACT_SUBREG ||
3105
0
            SuccOpc == TargetOpcode::INSERT_SUBREG ||
3106
0
            SuccOpc == TargetOpcode::SUBREG_TO_REG)
3107
0
          continue;
3108
0
        if (!canClobberReachingPhysRegUse(SuccSU, &SU, scheduleDAG, TII, TRI) &&
3109
0
            (!canClobber(SuccSU, DUSU) ||
3110
0
             (isLiveOut && !hasOnlyLiveOutUses(SuccSU)) ||
3111
0
             (!SU.isCommutable && SuccSU->isCommutable)) &&
3112
0
            !scheduleDAG->IsReachable(SuccSU, &SU)) {
3113
0
          LLVM_DEBUG(dbgs()
3114
0
                     << "    Adding a pseudo-two-addr edge from SU #"
3115
0
                     << SU.NodeNum << " to SU #" << SuccSU->NodeNum << "\n");
3116
0
          scheduleDAG->AddPredQueued(&SU, SDep(SuccSU, SDep::Artificial));
3117
0
        }
3118
0
      }
3119
0
    }
3120
0
  }
3121
0
}
3122
3123
//===----------------------------------------------------------------------===//
3124
//                         Public Constructor Functions
3125
//===----------------------------------------------------------------------===//
3126
3127
ScheduleDAGSDNodes *
3128
llvm::createBURRListDAGScheduler(SelectionDAGISel *IS,
3129
19.7k
                                 CodeGenOpt::Level OptLevel) {
3130
19.7k
  const TargetSubtargetInfo &STI = IS->MF->getSubtarget();
3131
19.7k
  const TargetInstrInfo *TII = STI.getInstrInfo();
3132
19.7k
  const TargetRegisterInfo *TRI = STI.getRegisterInfo();
3133
19.7k
3134
19.7k
  BURegReductionPriorityQueue *PQ =
3135
19.7k
    new BURegReductionPriorityQueue(*IS->MF, false, false, TII, TRI, nullptr);
3136
19.7k
  ScheduleDAGRRList *SD = new ScheduleDAGRRList(*IS->MF, false, PQ, OptLevel);
3137
19.7k
  PQ->setScheduleDAG(SD);
3138
19.7k
  return SD;
3139
19.7k
}
3140
3141
ScheduleDAGSDNodes *
3142
llvm::createSourceListDAGScheduler(SelectionDAGISel *IS,
3143
1.14M
                                   CodeGenOpt::Level OptLevel) {
3144
1.14M
  const TargetSubtargetInfo &STI = IS->MF->getSubtarget();
3145
1.14M
  const TargetInstrInfo *TII = STI.getInstrInfo();
3146
1.14M
  const TargetRegisterInfo *TRI = STI.getRegisterInfo();
3147
1.14M
3148
1.14M
  SrcRegReductionPriorityQueue *PQ =
3149
1.14M
    new SrcRegReductionPriorityQueue(*IS->MF, false, true, TII, TRI, nullptr);
3150
1.14M
  ScheduleDAGRRList *SD = new ScheduleDAGRRList(*IS->MF, false, PQ, OptLevel);
3151
1.14M
  PQ->setScheduleDAG(SD);
3152
1.14M
  return SD;
3153
1.14M
}
3154
3155
ScheduleDAGSDNodes *
3156
llvm::createHybridListDAGScheduler(SelectionDAGISel *IS,
3157
64.5k
                                   CodeGenOpt::Level OptLevel) {
3158
64.5k
  const TargetSubtargetInfo &STI = IS->MF->getSubtarget();
3159
64.5k
  const TargetInstrInfo *TII = STI.getInstrInfo();
3160
64.5k
  const TargetRegisterInfo *TRI = STI.getRegisterInfo();
3161
64.5k
  const TargetLowering *TLI = IS->TLI;
3162
64.5k
3163
64.5k
  HybridBURRPriorityQueue *PQ =
3164
64.5k
    new HybridBURRPriorityQueue(*IS->MF, true, false, TII, TRI, TLI);
3165
64.5k
3166
64.5k
  ScheduleDAGRRList *SD = new ScheduleDAGRRList(*IS->MF, true, PQ, OptLevel);
3167
64.5k
  PQ->setScheduleDAG(SD);
3168
64.5k
  return SD;
3169
64.5k
}
3170
3171
ScheduleDAGSDNodes *
3172
llvm::createILPListDAGScheduler(SelectionDAGISel *IS,
3173
20.1k
                                CodeGenOpt::Level OptLevel) {
3174
20.1k
  const TargetSubtargetInfo &STI = IS->MF->getSubtarget();
3175
20.1k
  const TargetInstrInfo *TII = STI.getInstrInfo();
3176
20.1k
  const TargetRegisterInfo *TRI = STI.getRegisterInfo();
3177
20.1k
  const TargetLowering *TLI = IS->TLI;
3178
20.1k
3179
20.1k
  ILPBURRPriorityQueue *PQ =
3180
20.1k
    new ILPBURRPriorityQueue(*IS->MF, true, false, TII, TRI, TLI);
3181
20.1k
  ScheduleDAGRRList *SD = new ScheduleDAGRRList(*IS->MF, true, PQ, OptLevel);
3182
20.1k
  PQ->setScheduleDAG(SD);
3183
20.1k
  return SD;
3184
20.1k
}