Coverage Report

Created: 2017-10-03 07:32

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