Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/SelectionDAG/ResourcePriorityQueue.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- ResourcePriorityQueue.cpp - A DFA-oriented priority queue -*- C++ -*-==//
2
//
3
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8
//
9
// This file implements the ResourcePriorityQueue class, which is a
10
// SchedulingPriorityQueue that prioritizes instructions using DFA state to
11
// reduce the length of the critical path through the basic block
12
// on VLIW platforms.
13
// The scheduler is basically a top-down adaptable list scheduler with DFA
14
// resource tracking added to the cost function.
15
// DFA is queried as a state machine to model "packets/bundles" during
16
// schedule. Currently packets/bundles are discarded at the end of
17
// scheduling, affecting only order of instructions.
18
//
19
//===----------------------------------------------------------------------===//
20
21
#include "llvm/CodeGen/ResourcePriorityQueue.h"
22
#include "llvm/CodeGen/MachineInstr.h"
23
#include "llvm/CodeGen/SelectionDAGNodes.h"
24
#include "llvm/CodeGen/TargetLowering.h"
25
#include "llvm/CodeGen/TargetSubtargetInfo.h"
26
#include "llvm/Support/CommandLine.h"
27
#include "llvm/Support/Debug.h"
28
#include "llvm/Support/raw_ostream.h"
29
#include "llvm/Target/TargetMachine.h"
30
31
using namespace llvm;
32
33
#define DEBUG_TYPE "scheduler"
34
35
static cl::opt<bool> DisableDFASched("disable-dfa-sched", cl::Hidden,
36
  cl::ZeroOrMore, cl::init(false),
37
  cl::desc("Disable use of DFA during scheduling"));
38
39
static cl::opt<int> RegPressureThreshold(
40
  "dfa-sched-reg-pressure-threshold", cl::Hidden, cl::ZeroOrMore, cl::init(5),
41
  cl::desc("Track reg pressure and switch priority to in-depth"));
42
43
ResourcePriorityQueue::ResourcePriorityQueue(SelectionDAGISel *IS)
44
0
    : Picker(this), InstrItins(IS->MF->getSubtarget().getInstrItineraryData()) {
45
0
  const TargetSubtargetInfo &STI = IS->MF->getSubtarget();
46
0
  TRI = STI.getRegisterInfo();
47
0
  TLI = IS->TLI;
48
0
  TII = STI.getInstrInfo();
49
0
  ResourcesModel.reset(TII->CreateTargetScheduleState(STI));
50
0
  // This hard requirement could be relaxed, but for now
51
0
  // do not let it proceed.
52
0
  assert(ResourcesModel && "Unimplemented CreateTargetScheduleState.");
53
0
54
0
  unsigned NumRC = TRI->getNumRegClasses();
55
0
  RegLimit.resize(NumRC);
56
0
  RegPressure.resize(NumRC);
57
0
  std::fill(RegLimit.begin(), RegLimit.end(), 0);
58
0
  std::fill(RegPressure.begin(), RegPressure.end(), 0);
59
0
  for (const TargetRegisterClass *RC : TRI->regclasses())
60
0
    RegLimit[RC->getID()] = TRI->getRegPressureLimit(RC, *IS->MF);
61
0
62
0
  ParallelLiveRanges = 0;
63
0
  HorizontalVerticalBalance = 0;
64
0
}
65
66
unsigned
67
0
ResourcePriorityQueue::numberRCValPredInSU(SUnit *SU, unsigned RCId) {
68
0
  unsigned NumberDeps = 0;
69
0
  for (SDep &Pred : SU->Preds) {
70
0
    if (Pred.isCtrl())
71
0
      continue;
72
0
73
0
    SUnit *PredSU = Pred.getSUnit();
74
0
    const SDNode *ScegN = PredSU->getNode();
75
0
76
0
    if (!ScegN)
77
0
      continue;
78
0
79
0
    // If value is passed to CopyToReg, it is probably
80
0
    // live outside BB.
81
0
    switch (ScegN->getOpcode()) {
82
0
      default:  break;
83
0
      case ISD::TokenFactor:    break;
84
0
      case ISD::CopyFromReg:    NumberDeps++;  break;
85
0
      case ISD::CopyToReg:      break;
86
0
      case ISD::INLINEASM:      break;
87
0
      case ISD::INLINEASM_BR:   break;
88
0
    }
89
0
    if (!ScegN->isMachineOpcode())
90
0
      continue;
91
0
92
0
    for (unsigned i = 0, e = ScegN->getNumValues(); i != e; ++i) {
93
0
      MVT VT = ScegN->getSimpleValueType(i);
94
0
      if (TLI->isTypeLegal(VT)
95
0
          && (TLI->getRegClassFor(VT)->getID() == RCId)) {
96
0
        NumberDeps++;
97
0
        break;
98
0
      }
99
0
    }
100
0
  }
101
0
  return NumberDeps;
102
0
}
103
104
unsigned ResourcePriorityQueue::numberRCValSuccInSU(SUnit *SU,
105
0
                                                    unsigned RCId) {
106
0
  unsigned NumberDeps = 0;
107
0
  for (const SDep &Succ : SU->Succs) {
108
0
    if (Succ.isCtrl())
109
0
      continue;
110
0
111
0
    SUnit *SuccSU = Succ.getSUnit();
112
0
    const SDNode *ScegN = SuccSU->getNode();
113
0
    if (!ScegN)
114
0
      continue;
115
0
116
0
    // If value is passed to CopyToReg, it is probably
117
0
    // live outside BB.
118
0
    switch (ScegN->getOpcode()) {
119
0
      default:  break;
120
0
      case ISD::TokenFactor:    break;
121
0
      case ISD::CopyFromReg:    break;
122
0
      case ISD::CopyToReg:      NumberDeps++;  break;
123
0
      case ISD::INLINEASM:      break;
124
0
      case ISD::INLINEASM_BR:   break;
125
0
    }
126
0
    if (!ScegN->isMachineOpcode())
127
0
      continue;
128
0
129
0
    for (unsigned i = 0, e = ScegN->getNumOperands(); i != e; ++i) {
130
0
      const SDValue &Op = ScegN->getOperand(i);
131
0
      MVT VT = Op.getNode()->getSimpleValueType(Op.getResNo());
132
0
      if (TLI->isTypeLegal(VT)
133
0
          && (TLI->getRegClassFor(VT)->getID() == RCId)) {
134
0
        NumberDeps++;
135
0
        break;
136
0
      }
137
0
    }
138
0
  }
139
0
  return NumberDeps;
140
0
}
141
142
0
static unsigned numberCtrlDepsInSU(SUnit *SU) {
143
0
  unsigned NumberDeps = 0;
144
0
  for (const SDep &Succ : SU->Succs)
145
0
    if (Succ.isCtrl())
146
0
      NumberDeps++;
147
0
148
0
  return NumberDeps;
149
0
}
150
151
0
static unsigned numberCtrlPredInSU(SUnit *SU) {
152
0
  unsigned NumberDeps = 0;
153
0
  for (SDep &Pred : SU->Preds)
154
0
    if (Pred.isCtrl())
155
0
      NumberDeps++;
156
0
157
0
  return NumberDeps;
158
0
}
159
160
///
161
/// Initialize nodes.
162
///
163
0
void ResourcePriorityQueue::initNodes(std::vector<SUnit> &sunits) {
164
0
  SUnits = &sunits;
165
0
  NumNodesSolelyBlocking.resize(SUnits->size(), 0);
166
0
167
0
  for (unsigned i = 0, e = SUnits->size(); i != e; ++i) {
168
0
    SUnit *SU = &(*SUnits)[i];
169
0
    initNumRegDefsLeft(SU);
170
0
    SU->NodeQueueId = 0;
171
0
  }
172
0
}
173
174
/// This heuristic is used if DFA scheduling is not desired
175
/// for some VLIW platform.
176
0
bool resource_sort::operator()(const SUnit *LHS, const SUnit *RHS) const {
177
0
  // The isScheduleHigh flag allows nodes with wraparound dependencies that
178
0
  // cannot easily be modeled as edges with latencies to be scheduled as
179
0
  // soon as possible in a top-down schedule.
180
0
  if (LHS->isScheduleHigh && !RHS->isScheduleHigh)
181
0
    return false;
182
0
183
0
  if (!LHS->isScheduleHigh && RHS->isScheduleHigh)
184
0
    return true;
185
0
186
0
  unsigned LHSNum = LHS->NodeNum;
187
0
  unsigned RHSNum = RHS->NodeNum;
188
0
189
0
  // The most important heuristic is scheduling the critical path.
190
0
  unsigned LHSLatency = PQ->getLatency(LHSNum);
191
0
  unsigned RHSLatency = PQ->getLatency(RHSNum);
192
0
  if (LHSLatency < RHSLatency) return true;
193
0
  if (LHSLatency > RHSLatency) return false;
194
0
195
0
  // After that, if two nodes have identical latencies, look to see if one will
196
0
  // unblock more other nodes than the other.
197
0
  unsigned LHSBlocked = PQ->getNumSolelyBlockNodes(LHSNum);
198
0
  unsigned RHSBlocked = PQ->getNumSolelyBlockNodes(RHSNum);
199
0
  if (LHSBlocked < RHSBlocked) return true;
200
0
  if (LHSBlocked > RHSBlocked) return false;
201
0
202
0
  // Finally, just to provide a stable ordering, use the node number as a
203
0
  // deciding factor.
204
0
  return LHSNum < RHSNum;
205
0
}
206
207
208
/// getSingleUnscheduledPred - If there is exactly one unscheduled predecessor
209
/// of SU, return it, otherwise return null.
210
0
SUnit *ResourcePriorityQueue::getSingleUnscheduledPred(SUnit *SU) {
211
0
  SUnit *OnlyAvailablePred = nullptr;
212
0
  for (const SDep &Pred : SU->Preds) {
213
0
    SUnit &PredSU = *Pred.getSUnit();
214
0
    if (!PredSU.isScheduled) {
215
0
      // We found an available, but not scheduled, predecessor.  If it's the
216
0
      // only one we have found, keep track of it... otherwise give up.
217
0
      if (OnlyAvailablePred && OnlyAvailablePred != &PredSU)
218
0
        return nullptr;
219
0
      OnlyAvailablePred = &PredSU;
220
0
    }
221
0
  }
222
0
  return OnlyAvailablePred;
223
0
}
224
225
0
void ResourcePriorityQueue::push(SUnit *SU) {
226
0
  // Look at all of the successors of this node.  Count the number of nodes that
227
0
  // this node is the sole unscheduled node for.
228
0
  unsigned NumNodesBlocking = 0;
229
0
  for (const SDep &Succ : SU->Succs)
230
0
    if (getSingleUnscheduledPred(Succ.getSUnit()) == SU)
231
0
      ++NumNodesBlocking;
232
0
233
0
  NumNodesSolelyBlocking[SU->NodeNum] = NumNodesBlocking;
234
0
  Queue.push_back(SU);
235
0
}
236
237
/// Check if scheduling of this SU is possible
238
/// in the current packet.
239
0
bool ResourcePriorityQueue::isResourceAvailable(SUnit *SU) {
240
0
  if (!SU || !SU->getNode())
241
0
    return false;
242
0
243
0
  // If this is a compound instruction,
244
0
  // it is likely to be a call. Do not delay it.
245
0
  if (SU->getNode()->getGluedNode())
246
0
    return true;
247
0
248
0
  // First see if the pipeline could receive this instruction
249
0
  // in the current cycle.
250
0
  if (SU->getNode()->isMachineOpcode())
251
0
    switch (SU->getNode()->getMachineOpcode()) {
252
0
    default:
253
0
      if (!ResourcesModel->canReserveResources(&TII->get(
254
0
          SU->getNode()->getMachineOpcode())))
255
0
           return false;
256
0
      break;
257
0
    case TargetOpcode::EXTRACT_SUBREG:
258
0
    case TargetOpcode::INSERT_SUBREG:
259
0
    case TargetOpcode::SUBREG_TO_REG:
260
0
    case TargetOpcode::REG_SEQUENCE:
261
0
    case TargetOpcode::IMPLICIT_DEF:
262
0
        break;
263
0
    }
264
0
265
0
  // Now see if there are no other dependencies
266
0
  // to instructions already in the packet.
267
0
  for (unsigned i = 0, e = Packet.size(); i != e; ++i)
268
0
    for (const SDep &Succ : Packet[i]->Succs) {
269
0
      // Since we do not add pseudos to packets, might as well
270
0
      // ignore order deps.
271
0
      if (Succ.isCtrl())
272
0
        continue;
273
0
274
0
      if (Succ.getSUnit() == SU)
275
0
        return false;
276
0
    }
277
0
278
0
  return true;
279
0
}
280
281
/// Keep track of available resources.
282
0
void ResourcePriorityQueue::reserveResources(SUnit *SU) {
283
0
  // If this SU does not fit in the packet
284
0
  // start a new one.
285
0
  if (!isResourceAvailable(SU) || SU->getNode()->getGluedNode()) {
286
0
    ResourcesModel->clearResources();
287
0
    Packet.clear();
288
0
  }
289
0
290
0
  if (SU->getNode() && SU->getNode()->isMachineOpcode()) {
291
0
    switch (SU->getNode()->getMachineOpcode()) {
292
0
    default:
293
0
      ResourcesModel->reserveResources(&TII->get(
294
0
        SU->getNode()->getMachineOpcode()));
295
0
      break;
296
0
    case TargetOpcode::EXTRACT_SUBREG:
297
0
    case TargetOpcode::INSERT_SUBREG:
298
0
    case TargetOpcode::SUBREG_TO_REG:
299
0
    case TargetOpcode::REG_SEQUENCE:
300
0
    case TargetOpcode::IMPLICIT_DEF:
301
0
      break;
302
0
    }
303
0
    Packet.push_back(SU);
304
0
  }
305
0
  // Forcefully end packet for PseudoOps.
306
0
  else {
307
0
    ResourcesModel->clearResources();
308
0
    Packet.clear();
309
0
  }
310
0
311
0
  // If packet is now full, reset the state so in the next cycle
312
0
  // we start fresh.
313
0
  if (Packet.size() >= InstrItins->SchedModel.IssueWidth) {
314
0
    ResourcesModel->clearResources();
315
0
    Packet.clear();
316
0
  }
317
0
}
318
319
0
int ResourcePriorityQueue::rawRegPressureDelta(SUnit *SU, unsigned RCId) {
320
0
  int RegBalance = 0;
321
0
322
0
  if (!SU || !SU->getNode() || !SU->getNode()->isMachineOpcode())
323
0
    return RegBalance;
324
0
325
0
  // Gen estimate.
326
0
  for (unsigned i = 0, e = SU->getNode()->getNumValues(); i != e; ++i) {
327
0
      MVT VT = SU->getNode()->getSimpleValueType(i);
328
0
      if (TLI->isTypeLegal(VT)
329
0
          && TLI->getRegClassFor(VT)
330
0
          && TLI->getRegClassFor(VT)->getID() == RCId)
331
0
        RegBalance += numberRCValSuccInSU(SU, RCId);
332
0
  }
333
0
  // Kill estimate.
334
0
  for (unsigned i = 0, e = SU->getNode()->getNumOperands(); i != e; ++i) {
335
0
      const SDValue &Op = SU->getNode()->getOperand(i);
336
0
      MVT VT = Op.getNode()->getSimpleValueType(Op.getResNo());
337
0
      if (isa<ConstantSDNode>(Op.getNode()))
338
0
        continue;
339
0
340
0
      if (TLI->isTypeLegal(VT) && TLI->getRegClassFor(VT)
341
0
          && TLI->getRegClassFor(VT)->getID() == RCId)
342
0
        RegBalance -= numberRCValPredInSU(SU, RCId);
343
0
  }
344
0
  return RegBalance;
345
0
}
346
347
/// Estimates change in reg pressure from this SU.
348
/// It is achieved by trivial tracking of defined
349
/// and used vregs in dependent instructions.
350
/// The RawPressure flag makes this function to ignore
351
/// existing reg file sizes, and report raw def/use
352
/// balance.
353
0
int ResourcePriorityQueue::regPressureDelta(SUnit *SU, bool RawPressure) {
354
0
  int RegBalance = 0;
355
0
356
0
  if (!SU || !SU->getNode() || !SU->getNode()->isMachineOpcode())
357
0
    return RegBalance;
358
0
359
0
  if (RawPressure) {
360
0
    for (const TargetRegisterClass *RC : TRI->regclasses())
361
0
      RegBalance += rawRegPressureDelta(SU, RC->getID());
362
0
  }
363
0
  else {
364
0
    for (const TargetRegisterClass *RC : TRI->regclasses()) {
365
0
      if ((RegPressure[RC->getID()] +
366
0
           rawRegPressureDelta(SU, RC->getID()) > 0) &&
367
0
          (RegPressure[RC->getID()] +
368
0
           rawRegPressureDelta(SU, RC->getID())  >= RegLimit[RC->getID()]))
369
0
        RegBalance += rawRegPressureDelta(SU, RC->getID());
370
0
    }
371
0
  }
372
0
373
0
  return RegBalance;
374
0
}
375
376
// Constants used to denote relative importance of
377
// heuristic components for cost computation.
378
static const unsigned PriorityOne = 200;
379
static const unsigned PriorityTwo = 50;
380
static const unsigned PriorityThree = 15;
381
static const unsigned PriorityFour = 5;
382
static const unsigned ScaleOne = 20;
383
static const unsigned ScaleTwo = 10;
384
static const unsigned ScaleThree = 5;
385
static const unsigned FactorOne = 2;
386
387
/// Returns single number reflecting benefit of scheduling SU
388
/// in the current cycle.
389
0
int ResourcePriorityQueue::SUSchedulingCost(SUnit *SU) {
390
0
  // Initial trivial priority.
391
0
  int ResCount = 1;
392
0
393
0
  // Do not waste time on a node that is already scheduled.
394
0
  if (SU->isScheduled)
395
0
    return ResCount;
396
0
397
0
  // Forced priority is high.
398
0
  if (SU->isScheduleHigh)
399
0
    ResCount += PriorityOne;
400
0
401
0
  // Adaptable scheduling
402
0
  // A small, but very parallel
403
0
  // region, where reg pressure is an issue.
404
0
  if (HorizontalVerticalBalance > RegPressureThreshold) {
405
0
    // Critical path first
406
0
    ResCount += (SU->getHeight() * ScaleTwo);
407
0
    // If resources are available for it, multiply the
408
0
    // chance of scheduling.
409
0
    if (isResourceAvailable(SU))
410
0
      ResCount <<= FactorOne;
411
0
412
0
    // Consider change to reg pressure from scheduling
413
0
    // this SU.
414
0
    ResCount -= (regPressureDelta(SU,true) * ScaleOne);
415
0
  }
416
0
  // Default heuristic, greeady and
417
0
  // critical path driven.
418
0
  else {
419
0
    // Critical path first.
420
0
    ResCount += (SU->getHeight() * ScaleTwo);
421
0
    // Now see how many instructions is blocked by this SU.
422
0
    ResCount += (NumNodesSolelyBlocking[SU->NodeNum] * ScaleTwo);
423
0
    // If resources are available for it, multiply the
424
0
    // chance of scheduling.
425
0
    if (isResourceAvailable(SU))
426
0
      ResCount <<= FactorOne;
427
0
428
0
    ResCount -= (regPressureDelta(SU) * ScaleTwo);
429
0
  }
430
0
431
0
  // These are platform-specific things.
432
0
  // Will need to go into the back end
433
0
  // and accessed from here via a hook.
434
0
  for (SDNode *N = SU->getNode(); N; N = N->getGluedNode()) {
435
0
    if (N->isMachineOpcode()) {
436
0
      const MCInstrDesc &TID = TII->get(N->getMachineOpcode());
437
0
      if (TID.isCall())
438
0
        ResCount += (PriorityTwo + (ScaleThree*N->getNumValues()));
439
0
    }
440
0
    else
441
0
      switch (N->getOpcode()) {
442
0
      default:  break;
443
0
      case ISD::TokenFactor:
444
0
      case ISD::CopyFromReg:
445
0
      case ISD::CopyToReg:
446
0
        ResCount += PriorityFour;
447
0
        break;
448
0
449
0
      case ISD::INLINEASM:
450
0
      case ISD::INLINEASM_BR:
451
0
        ResCount += PriorityThree;
452
0
        break;
453
0
      }
454
0
  }
455
0
  return ResCount;
456
0
}
457
458
459
/// Main resource tracking point.
460
0
void ResourcePriorityQueue::scheduledNode(SUnit *SU) {
461
0
  // Use NULL entry as an event marker to reset
462
0
  // the DFA state.
463
0
  if (!SU) {
464
0
    ResourcesModel->clearResources();
465
0
    Packet.clear();
466
0
    return;
467
0
  }
468
0
469
0
  const SDNode *ScegN = SU->getNode();
470
0
  // Update reg pressure tracking.
471
0
  // First update current node.
472
0
  if (ScegN->isMachineOpcode()) {
473
0
    // Estimate generated regs.
474
0
    for (unsigned i = 0, e = ScegN->getNumValues(); i != e; ++i) {
475
0
      MVT VT = ScegN->getSimpleValueType(i);
476
0
477
0
      if (TLI->isTypeLegal(VT)) {
478
0
        const TargetRegisterClass *RC = TLI->getRegClassFor(VT);
479
0
        if (RC)
480
0
          RegPressure[RC->getID()] += numberRCValSuccInSU(SU, RC->getID());
481
0
      }
482
0
    }
483
0
    // Estimate killed regs.
484
0
    for (unsigned i = 0, e = ScegN->getNumOperands(); i != e; ++i) {
485
0
      const SDValue &Op = ScegN->getOperand(i);
486
0
      MVT VT = Op.getNode()->getSimpleValueType(Op.getResNo());
487
0
488
0
      if (TLI->isTypeLegal(VT)) {
489
0
        const TargetRegisterClass *RC = TLI->getRegClassFor(VT);
490
0
        if (RC) {
491
0
          if (RegPressure[RC->getID()] >
492
0
            (numberRCValPredInSU(SU, RC->getID())))
493
0
            RegPressure[RC->getID()] -= numberRCValPredInSU(SU, RC->getID());
494
0
          else RegPressure[RC->getID()] = 0;
495
0
        }
496
0
      }
497
0
    }
498
0
    for (SDep &Pred : SU->Preds) {
499
0
      if (Pred.isCtrl() || (Pred.getSUnit()->NumRegDefsLeft == 0))
500
0
        continue;
501
0
      --Pred.getSUnit()->NumRegDefsLeft;
502
0
    }
503
0
  }
504
0
505
0
  // Reserve resources for this SU.
506
0
  reserveResources(SU);
507
0
508
0
  // Adjust number of parallel live ranges.
509
0
  // Heuristic is simple - node with no data successors reduces
510
0
  // number of live ranges. All others, increase it.
511
0
  unsigned NumberNonControlDeps = 0;
512
0
513
0
  for (const SDep &Succ : SU->Succs) {
514
0
    adjustPriorityOfUnscheduledPreds(Succ.getSUnit());
515
0
    if (!Succ.isCtrl())
516
0
      NumberNonControlDeps++;
517
0
  }
518
0
519
0
  if (!NumberNonControlDeps) {
520
0
    if (ParallelLiveRanges >= SU->NumPreds)
521
0
      ParallelLiveRanges -= SU->NumPreds;
522
0
    else
523
0
      ParallelLiveRanges = 0;
524
0
525
0
  }
526
0
  else
527
0
    ParallelLiveRanges += SU->NumRegDefsLeft;
528
0
529
0
  // Track parallel live chains.
530
0
  HorizontalVerticalBalance += (SU->Succs.size() - numberCtrlDepsInSU(SU));
531
0
  HorizontalVerticalBalance -= (SU->Preds.size() - numberCtrlPredInSU(SU));
532
0
}
533
534
0
void ResourcePriorityQueue::initNumRegDefsLeft(SUnit *SU) {
535
0
  unsigned  NodeNumDefs = 0;
536
0
  for (SDNode *N = SU->getNode(); N; N = N->getGluedNode())
537
0
    if (N->isMachineOpcode()) {
538
0
      const MCInstrDesc &TID = TII->get(N->getMachineOpcode());
539
0
      // No register need be allocated for this.
540
0
      if (N->getMachineOpcode() == TargetOpcode::IMPLICIT_DEF) {
541
0
        NodeNumDefs = 0;
542
0
        break;
543
0
      }
544
0
      NodeNumDefs = std::min(N->getNumValues(), TID.getNumDefs());
545
0
    }
546
0
    else
547
0
      switch(N->getOpcode()) {
548
0
        default:     break;
549
0
        case ISD::CopyFromReg:
550
0
          NodeNumDefs++;
551
0
          break;
552
0
        case ISD::INLINEASM:
553
0
        case ISD::INLINEASM_BR:
554
0
          NodeNumDefs++;
555
0
          break;
556
0
      }
557
0
558
0
  SU->NumRegDefsLeft = NodeNumDefs;
559
0
}
560
561
/// adjustPriorityOfUnscheduledPreds - One of the predecessors of SU was just
562
/// scheduled.  If SU is not itself available, then there is at least one
563
/// predecessor node that has not been scheduled yet.  If SU has exactly ONE
564
/// unscheduled predecessor, we want to increase its priority: it getting
565
/// scheduled will make this node available, so it is better than some other
566
/// node of the same priority that will not make a node available.
567
0
void ResourcePriorityQueue::adjustPriorityOfUnscheduledPreds(SUnit *SU) {
568
0
  if (SU->isAvailable) return;  // All preds scheduled.
569
0
570
0
  SUnit *OnlyAvailablePred = getSingleUnscheduledPred(SU);
571
0
  if (!OnlyAvailablePred || !OnlyAvailablePred->isAvailable)
572
0
    return;
573
0
574
0
  // Okay, we found a single predecessor that is available, but not scheduled.
575
0
  // Since it is available, it must be in the priority queue.  First remove it.
576
0
  remove(OnlyAvailablePred);
577
0
578
0
  // Reinsert the node into the priority queue, which recomputes its
579
0
  // NumNodesSolelyBlocking value.
580
0
  push(OnlyAvailablePred);
581
0
}
582
583
584
/// Main access point - returns next instructions
585
/// to be placed in scheduling sequence.
586
0
SUnit *ResourcePriorityQueue::pop() {
587
0
  if (empty())
588
0
    return nullptr;
589
0
590
0
  std::vector<SUnit *>::iterator Best = Queue.begin();
591
0
  if (!DisableDFASched) {
592
0
    int BestCost = SUSchedulingCost(*Best);
593
0
    for (auto I = std::next(Queue.begin()), E = Queue.end(); I != E; ++I) {
594
0
595
0
      if (SUSchedulingCost(*I) > BestCost) {
596
0
        BestCost = SUSchedulingCost(*I);
597
0
        Best = I;
598
0
      }
599
0
    }
600
0
  }
601
0
  // Use default TD scheduling mechanism.
602
0
  else {
603
0
    for (auto I = std::next(Queue.begin()), E = Queue.end(); I != E; ++I)
604
0
      if (Picker(*Best, *I))
605
0
        Best = I;
606
0
  }
607
0
608
0
  SUnit *V = *Best;
609
0
  if (Best != std::prev(Queue.end()))
610
0
    std::swap(*Best, Queue.back());
611
0
612
0
  Queue.pop_back();
613
0
614
0
  return V;
615
0
}
616
617
618
0
void ResourcePriorityQueue::remove(SUnit *SU) {
619
0
  assert(!Queue.empty() && "Queue is empty!");
620
0
  std::vector<SUnit *>::iterator I = find(Queue, SU);
621
0
  if (I != std::prev(Queue.end()))
622
0
    std::swap(*I, Queue.back());
623
0
624
0
  Queue.pop_back();
625
0
}