Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Target/Hexagon/HexagonMachineScheduler.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- HexagonMachineScheduler.cpp - MI Scheduler for Hexagon -------------===//
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
// MachineScheduler schedules machine instructions after phi elimination. It
10
// preserves LiveIntervals so it can be invoked before register allocation.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#include "HexagonMachineScheduler.h"
15
#include "HexagonInstrInfo.h"
16
#include "HexagonSubtarget.h"
17
#include "llvm/ADT/SmallVector.h"
18
#include "llvm/CodeGen/DFAPacketizer.h"
19
#include "llvm/CodeGen/MachineBasicBlock.h"
20
#include "llvm/CodeGen/MachineFunction.h"
21
#include "llvm/CodeGen/MachineInstr.h"
22
#include "llvm/CodeGen/MachineLoopInfo.h"
23
#include "llvm/CodeGen/RegisterClassInfo.h"
24
#include "llvm/CodeGen/RegisterPressure.h"
25
#include "llvm/CodeGen/ScheduleDAG.h"
26
#include "llvm/CodeGen/ScheduleHazardRecognizer.h"
27
#include "llvm/CodeGen/TargetInstrInfo.h"
28
#include "llvm/CodeGen/TargetOpcodes.h"
29
#include "llvm/CodeGen/TargetRegisterInfo.h"
30
#include "llvm/CodeGen/TargetSchedule.h"
31
#include "llvm/CodeGen/TargetSubtargetInfo.h"
32
#include "llvm/IR/Function.h"
33
#include "llvm/Support/CommandLine.h"
34
#include "llvm/Support/Debug.h"
35
#include "llvm/Support/raw_ostream.h"
36
#include <algorithm>
37
#include <cassert>
38
#include <iomanip>
39
#include <limits>
40
#include <memory>
41
#include <sstream>
42
43
using namespace llvm;
44
45
#define DEBUG_TYPE "machine-scheduler"
46
47
static cl::opt<bool> IgnoreBBRegPressure("ignore-bb-reg-pressure",
48
    cl::Hidden, cl::ZeroOrMore, cl::init(false));
49
50
static cl::opt<bool> UseNewerCandidate("use-newer-candidate",
51
    cl::Hidden, cl::ZeroOrMore, cl::init(true));
52
53
static cl::opt<unsigned> SchedDebugVerboseLevel("misched-verbose-level",
54
    cl::Hidden, cl::ZeroOrMore, cl::init(1));
55
56
// Check if the scheduler should penalize instructions that are available to
57
// early due to a zero-latency dependence.
58
static cl::opt<bool> CheckEarlyAvail("check-early-avail", cl::Hidden,
59
    cl::ZeroOrMore, cl::init(true));
60
61
// This value is used to determine if a register class is a high pressure set.
62
// We compute the maximum number of registers needed and divided by the total
63
// available. Then, we compare the result to this value.
64
static cl::opt<float> RPThreshold("hexagon-reg-pressure", cl::Hidden,
65
    cl::init(0.75f), cl::desc("High register pressure threhold."));
66
67
/// Return true if there is a dependence between SUd and SUu.
68
static bool hasDependence(const SUnit *SUd, const SUnit *SUu,
69
102k
                          const HexagonInstrInfo &QII) {
70
102k
  if (SUd->Succs.size() == 0)
71
23.3k
    return false;
72
79.4k
73
79.4k
  // Enable .cur formation.
74
79.4k
  if (QII.mayBeCurLoad(*SUd->getInstr()))
75
2.19k
    return false;
76
77.2k
77
77.2k
  if (QII.canExecuteInBundle(*SUd->getInstr(), *SUu->getInstr()))
78
1.83k
    return false;
79
75.4k
80
133k
  
for (const auto &S : SUd->Succs)75.4k
{
81
133k
    // Since we do not add pseudos to packets, might as well
82
133k
    // ignore order dependencies.
83
133k
    if (S.isCtrl())
84
43.9k
      continue;
85
89.6k
86
89.6k
    if (S.getSUnit() == SUu && 
S.getLatency() > 012.1k
)
87
0
      return true;
88
89.6k
  }
89
75.4k
  return false;
90
75.4k
}
91
92
/// Check if scheduling of this SU is possible
93
/// in the current packet.
94
/// It is _not_ precise (statefull), it is more like
95
/// another heuristic. Many corner cases are figured
96
/// empirically.
97
139k
bool VLIWResourceModel::isResourceAvailable(SUnit *SU, bool IsTop) {
98
139k
  if (!SU || !SU->getInstr())
99
0
    return false;
100
139k
101
139k
  // First see if the pipeline could receive this instruction
102
139k
  // in the current cycle.
103
139k
  switch (SU->getInstr()->getOpcode()) {
104
139k
  default:
105
111k
    if (!ResourcesModel->canReserveResources(*SU->getInstr()))
106
28.5k
      return false;
107
83.1k
    break;
108
83.1k
  case TargetOpcode::EXTRACT_SUBREG:
109
27.3k
  case TargetOpcode::INSERT_SUBREG:
110
27.3k
  case TargetOpcode::SUBREG_TO_REG:
111
27.3k
  case TargetOpcode::REG_SEQUENCE:
112
27.3k
  case TargetOpcode::IMPLICIT_DEF:
113
27.3k
  case TargetOpcode::COPY:
114
27.3k
  case TargetOpcode::INLINEASM:
115
27.3k
  case TargetOpcode::INLINEASM_BR:
116
27.3k
    break;
117
110k
  }
118
110k
119
110k
  MachineBasicBlock *MBB = SU->getInstr()->getParent();
120
110k
  auto &QST = MBB->getParent()->getSubtarget<HexagonSubtarget>();
121
110k
  const auto &QII = *QST.getInstrInfo();
122
110k
123
110k
  // Now see if there are no other dependencies to instructions already
124
110k
  // in the packet.
125
110k
  if (IsTop) {
126
85.7k
    for (unsigned i = 0, e = Packet.size(); i != e; 
++i41.3k
)
127
41.3k
      if (hasDependence(Packet[i], SU, QII))
128
0
        return false;
129
66.2k
  } else {
130
127k
    for (unsigned i = 0, e = Packet.size(); i != e; 
++i61.4k
)
131
61.4k
      if (hasDependence(SU, Packet[i], QII))
132
0
        return false;
133
66.2k
  }
134
110k
  return true;
135
110k
}
136
137
/// Keep track of available resources.
138
40.1k
bool VLIWResourceModel::reserveResources(SUnit *SU, bool IsTop) {
139
40.1k
  bool startNewCycle = false;
140
40.1k
  // Artificially reset state.
141
40.1k
  if (!SU) {
142
10.6k
    ResourcesModel->clearResources();
143
10.6k
    Packet.clear();
144
10.6k
    TotalPackets++;
145
10.6k
    return false;
146
10.6k
  }
147
29.4k
  // If this SU does not fit in the packet or the packet is now full
148
29.4k
  // start a new one.
149
29.4k
  if (!isResourceAvailable(SU, IsTop) ||
150
29.4k
      
Packet.size() >= SchedModel->getIssueWidth()28.6k
) {
151
1.31k
    ResourcesModel->clearResources();
152
1.31k
    Packet.clear();
153
1.31k
    TotalPackets++;
154
1.31k
    startNewCycle = true;
155
1.31k
  }
156
29.4k
157
29.4k
  switch (SU->getInstr()->getOpcode()) {
158
29.4k
  default:
159
20.5k
    ResourcesModel->reserveResources(*SU->getInstr());
160
20.5k
    break;
161
29.4k
  case TargetOpcode::EXTRACT_SUBREG:
162
8.89k
  case TargetOpcode::INSERT_SUBREG:
163
8.89k
  case TargetOpcode::SUBREG_TO_REG:
164
8.89k
  case TargetOpcode::REG_SEQUENCE:
165
8.89k
  case TargetOpcode::IMPLICIT_DEF:
166
8.89k
  case TargetOpcode::KILL:
167
8.89k
  case TargetOpcode::CFI_INSTRUCTION:
168
8.89k
  case TargetOpcode::EH_LABEL:
169
8.89k
  case TargetOpcode::COPY:
170
8.89k
  case TargetOpcode::INLINEASM:
171
8.89k
  case TargetOpcode::INLINEASM_BR:
172
8.89k
    break;
173
29.4k
  }
174
29.4k
  Packet.push_back(SU);
175
29.4k
176
#ifndef NDEBUG
177
  LLVM_DEBUG(dbgs() << "Packet[" << TotalPackets << "]:\n");
178
  for (unsigned i = 0, e = Packet.size(); i != e; ++i) {
179
    LLVM_DEBUG(dbgs() << "\t[" << i << "] SU(");
180
    LLVM_DEBUG(dbgs() << Packet[i]->NodeNum << ")\t");
181
    LLVM_DEBUG(Packet[i]->getInstr()->dump());
182
  }
183
#endif
184
185
29.4k
  return startNewCycle;
186
29.4k
}
187
188
/// schedule - Called back from MachineScheduler::runOnMachineFunction
189
/// after setting up the current scheduling region. [RegionBegin, RegionEnd)
190
/// only includes instructions that have DAG nodes, not scheduling boundaries.
191
5.01k
void VLIWMachineScheduler::schedule() {
192
5.01k
  LLVM_DEBUG(dbgs() << "********** MI Converging Scheduling VLIW "
193
5.01k
                    << printMBBReference(*BB) << " " << BB->getName()
194
5.01k
                    << " in_func " << BB->getParent()->getName()
195
5.01k
                    << " at loop depth " << MLI->getLoopDepth(BB) << " \n");
196
5.01k
197
5.01k
  buildDAGWithRegPressure();
198
5.01k
199
5.01k
  Topo.InitDAGTopologicalSorting();
200
5.01k
201
5.01k
  // Postprocess the DAG to add platform-specific artificial dependencies.
202
5.01k
  postprocessDAG();
203
5.01k
204
5.01k
  SmallVector<SUnit*, 8> TopRoots, BotRoots;
205
5.01k
  findRootsAndBiasEdges(TopRoots, BotRoots);
206
5.01k
207
5.01k
  // Initialize the strategy before modifying the DAG.
208
5.01k
  SchedImpl->initialize(this);
209
5.01k
210
5.01k
  LLVM_DEBUG(unsigned maxH = 0;
211
5.01k
             for (unsigned su = 0, e = SUnits.size(); su != e;
212
5.01k
                  ++su) if (SUnits[su].getHeight() > maxH) maxH =
213
5.01k
                 SUnits[su].getHeight();
214
5.01k
             dbgs() << "Max Height " << maxH << "\n";);
215
5.01k
  LLVM_DEBUG(unsigned maxD = 0;
216
5.01k
             for (unsigned su = 0, e = SUnits.size(); su != e;
217
5.01k
                  ++su) if (SUnits[su].getDepth() > maxD) maxD =
218
5.01k
                 SUnits[su].getDepth();
219
5.01k
             dbgs() << "Max Depth " << maxD << "\n";);
220
5.01k
  LLVM_DEBUG(dump());
221
5.01k
222
5.01k
  initQueues(TopRoots, BotRoots);
223
5.01k
224
5.01k
  bool IsTopNode = false;
225
34.5k
  while (true) {
226
34.5k
    LLVM_DEBUG(
227
34.5k
        dbgs() << "** VLIWMachineScheduler::schedule picking next node\n");
228
34.5k
    SUnit *SU = SchedImpl->pickNode(IsTopNode);
229
34.5k
    if (!SU) 
break5.01k
;
230
29.4k
231
29.4k
    if (!checkSchedLimit())
232
0
      break;
233
29.4k
234
29.4k
    scheduleMI(SU, IsTopNode);
235
29.4k
236
29.4k
    // Notify the scheduling strategy after updating the DAG.
237
29.4k
    SchedImpl->schedNode(SU, IsTopNode);
238
29.4k
239
29.4k
    updateQueues(SU, IsTopNode);
240
29.4k
  }
241
5.01k
  assert(CurrentTop == CurrentBottom && "Nonempty unscheduled zone.");
242
5.01k
243
5.01k
  placeDebugValues();
244
5.01k
245
5.01k
  LLVM_DEBUG({
246
5.01k
    dbgs() << "*** Final schedule for "
247
5.01k
           << printMBBReference(*begin()->getParent()) << " ***\n";
248
5.01k
    dumpSchedule();
249
5.01k
    dbgs() << '\n';
250
5.01k
  });
251
5.01k
}
252
253
5.01k
void ConvergingVLIWScheduler::initialize(ScheduleDAGMI *dag) {
254
5.01k
  DAG = static_cast<VLIWMachineScheduler*>(dag);
255
5.01k
  SchedModel = DAG->getSchedModel();
256
5.01k
257
5.01k
  Top.init(DAG, SchedModel);
258
5.01k
  Bot.init(DAG, SchedModel);
259
5.01k
260
5.01k
  // Initialize the HazardRecognizers. If itineraries don't exist, are empty, or
261
5.01k
  // are disabled, then these HazardRecs will be disabled.
262
5.01k
  const InstrItineraryData *Itin = DAG->getSchedModel()->getInstrItineraries();
263
5.01k
  const TargetSubtargetInfo &STI = DAG->MF.getSubtarget();
264
5.01k
  const TargetInstrInfo *TII = STI.getInstrInfo();
265
5.01k
  delete Top.HazardRec;
266
5.01k
  delete Bot.HazardRec;
267
5.01k
  Top.HazardRec = TII->CreateTargetMIHazardRecognizer(Itin, DAG);
268
5.01k
  Bot.HazardRec = TII->CreateTargetMIHazardRecognizer(Itin, DAG);
269
5.01k
270
5.01k
  delete Top.ResourceModel;
271
5.01k
  delete Bot.ResourceModel;
272
5.01k
  Top.ResourceModel = new VLIWResourceModel(STI, DAG->getSchedModel());
273
5.01k
  Bot.ResourceModel = new VLIWResourceModel(STI, DAG->getSchedModel());
274
5.01k
275
5.01k
  const std::vector<unsigned> &MaxPressure =
276
5.01k
    DAG->getRegPressure().MaxSetPressure;
277
5.01k
  HighPressureSets.assign(MaxPressure.size(), 0);
278
45.1k
  for (unsigned i = 0, e = MaxPressure.size(); i < e; 
++i40.1k
) {
279
40.1k
    unsigned Limit = DAG->getRegClassInfo()->getRegPressureSetLimit(i);
280
40.1k
    HighPressureSets[i] =
281
40.1k
      ((float) MaxPressure[i] > ((float) Limit * RPThreshold));
282
40.1k
  }
283
5.01k
284
5.01k
  assert((!ForceTopDown || !ForceBottomUp) &&
285
5.01k
         "-misched-topdown incompatible with -misched-bottomup");
286
5.01k
}
287
288
16.4k
void ConvergingVLIWScheduler::releaseTopNode(SUnit *SU) {
289
16.4k
  if (SU->isScheduled)
290
567
    return;
291
15.8k
292
15.8k
  for (const SDep &PI : SU->Preds) {
293
5.12k
    unsigned PredReadyCycle = PI.getSUnit()->TopReadyCycle;
294
5.12k
    unsigned MinLatency = PI.getLatency();
295
#ifndef NDEBUG
296
    Top.MaxMinLatency = std::max(MinLatency, Top.MaxMinLatency);
297
#endif
298
5.12k
    if (SU->TopReadyCycle < PredReadyCycle + MinLatency)
299
2
      SU->TopReadyCycle = PredReadyCycle + MinLatency;
300
5.12k
  }
301
15.8k
  Top.releaseNode(SU, SU->TopReadyCycle);
302
15.8k
}
303
304
27.5k
void ConvergingVLIWScheduler::releaseBottomNode(SUnit *SU) {
305
27.5k
  if (SU->isScheduled)
306
1.13k
    return;
307
26.3k
308
26.3k
  assert(SU->getInstr() && "Scheduled SUnit must have instr");
309
26.3k
310
26.3k
  for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
311
59.6k
       I != E; 
++I33.2k
) {
312
33.2k
    unsigned SuccReadyCycle = I->getSUnit()->BotReadyCycle;
313
33.2k
    unsigned MinLatency = I->getLatency();
314
#ifndef NDEBUG
315
    Bot.MaxMinLatency = std::max(MinLatency, Bot.MaxMinLatency);
316
#endif
317
33.2k
    if (SU->BotReadyCycle < SuccReadyCycle + MinLatency)
318
3
      SU->BotReadyCycle = SuccReadyCycle + MinLatency;
319
33.2k
  }
320
26.3k
  Bot.releaseNode(SU, SU->BotReadyCycle);
321
26.3k
}
322
323
/// Does this SU have a hazard within the current instruction group.
324
///
325
/// The scheduler supports two modes of hazard recognition. The first is the
326
/// ScheduleHazardRecognizer API. It is a fully general hazard recognizer that
327
/// supports highly complicated in-order reservation tables
328
/// (ScoreboardHazardRecognizer) and arbitrary target-specific logic.
329
///
330
/// The second is a streamlined mechanism that checks for hazards based on
331
/// simple counters that the scheduler itself maintains. It explicitly checks
332
/// for instruction dispatch limitations, including the number of micro-ops that
333
/// can dispatch per cycle.
334
///
335
/// TODO: Also check whether the SU must start a new group.
336
41.1k
bool ConvergingVLIWScheduler::VLIWSchedBoundary::checkHazard(SUnit *SU) {
337
41.1k
  if (HazardRec->isEnabled())
338
0
    return HazardRec->getHazardType(SU) != ScheduleHazardRecognizer::NoHazard;
339
41.1k
340
41.1k
  unsigned uops = SchedModel->getNumMicroOps(SU->getInstr());
341
41.1k
  if (IssueCount + uops > SchedModel->getIssueWidth())
342
29
    return true;
343
41.1k
344
41.1k
  return false;
345
41.1k
}
346
347
void ConvergingVLIWScheduler::VLIWSchedBoundary::releaseNode(SUnit *SU,
348
42.2k
                                                     unsigned ReadyCycle) {
349
42.2k
  if (ReadyCycle < MinReadyCycle)
350
7.59k
    MinReadyCycle = ReadyCycle;
351
42.2k
352
42.2k
  // Check for interlocks first. For the purpose of other heuristics, an
353
42.2k
  // instruction that cannot issue appears as if it's not in the ReadyQueue.
354
42.2k
  if (ReadyCycle > CurrCycle || 
checkHazard(SU)27.1k
)
355
15.1k
356
15.1k
    Pending.push(SU);
357
27.0k
  else
358
27.0k
    Available.push(SU);
359
42.2k
}
360
361
/// Move the boundary of scheduled code by one cycle.
362
11.9k
void ConvergingVLIWScheduler::VLIWSchedBoundary::bumpCycle() {
363
11.9k
  unsigned Width = SchedModel->getIssueWidth();
364
11.9k
  IssueCount = (IssueCount <= Width) ? 
011.8k
:
IssueCount - Width96
;
365
11.9k
366
11.9k
  assert(MinReadyCycle < std::numeric_limits<unsigned>::max() &&
367
11.9k
         "MinReadyCycle uninitialized");
368
11.9k
  unsigned NextCycle = std::max(CurrCycle + 1, MinReadyCycle);
369
11.9k
370
11.9k
  if (!HazardRec->isEnabled()) {
371
11.9k
    // Bypass HazardRec virtual calls.
372
11.9k
    CurrCycle = NextCycle;
373
11.9k
  } else {
374
0
    // Bypass getHazardType calls in case of long latency.
375
0
    for (; CurrCycle != NextCycle; ++CurrCycle) {
376
0
      if (isTop())
377
0
        HazardRec->AdvanceCycle();
378
0
      else
379
0
        HazardRec->RecedeCycle();
380
0
    }
381
0
  }
382
11.9k
  CheckPending = true;
383
11.9k
384
11.9k
  LLVM_DEBUG(dbgs() << "*** Next cycle " << Available.getName() << " cycle "
385
11.9k
                    << CurrCycle << '\n');
386
11.9k
}
387
388
/// Move the boundary of scheduled code by one SUnit.
389
29.4k
void ConvergingVLIWScheduler::VLIWSchedBoundary::bumpNode(SUnit *SU) {
390
29.4k
  bool startNewCycle = false;
391
29.4k
392
29.4k
  // Update the reservation table.
393
29.4k
  if (HazardRec->isEnabled()) {
394
0
    if (!isTop() && SU->isCall) {
395
0
      // Calls are scheduled with their preceding instructions. For bottom-up
396
0
      // scheduling, clear the pipeline state before emitting.
397
0
      HazardRec->Reset();
398
0
    }
399
0
    HazardRec->EmitInstruction(SU);
400
0
  }
401
29.4k
402
29.4k
  // Update DFA model.
403
29.4k
  startNewCycle = ResourceModel->reserveResources(SU, isTop());
404
29.4k
405
29.4k
  // Check the instruction group dispatch limit.
406
29.4k
  // TODO: Check if this SU must end a dispatch group.
407
29.4k
  IssueCount += SchedModel->getNumMicroOps(SU->getInstr());
408
29.4k
  if (startNewCycle) {
409
1.31k
    LLVM_DEBUG(dbgs() << "*** Max instrs at cycle " << CurrCycle << '\n');
410
1.31k
    bumpCycle();
411
1.31k
  }
412
29.4k
  else
413
29.4k
    LLVM_DEBUG(dbgs() << "*** IssueCount " << IssueCount << " at cycle "
414
29.4k
                      << CurrCycle << '\n');
415
29.4k
}
416
417
/// Release pending ready nodes in to the available queue. This makes them
418
/// visible to heuristics.
419
11.8k
void ConvergingVLIWScheduler::VLIWSchedBoundary::releasePending() {
420
11.8k
  // If the available queue is empty, it is safe to reset MinReadyCycle.
421
11.8k
  if (Available.empty())
422
10.3k
    MinReadyCycle = std::numeric_limits<unsigned>::max();
423
11.8k
424
11.8k
  // Check to see if any of the pending instructions are ready to issue.  If
425
11.8k
  // so, add them to the available queue.
426
28.1k
  for (unsigned i = 0, e = Pending.size(); i != e; 
++i16.2k
) {
427
16.2k
    SUnit *SU = *(Pending.begin()+i);
428
16.2k
    unsigned ReadyCycle = isTop() ? 
SU->TopReadyCycle2.04k
:
SU->BotReadyCycle14.2k
;
429
16.2k
430
16.2k
    if (ReadyCycle < MinReadyCycle)
431
10.5k
      MinReadyCycle = ReadyCycle;
432
16.2k
433
16.2k
    if (ReadyCycle > CurrCycle)
434
2.21k
      continue;
435
14.0k
436
14.0k
    if (checkHazard(SU))
437
0
      continue;
438
14.0k
439
14.0k
    Available.push(SU);
440
14.0k
    Pending.remove(Pending.begin()+i);
441
14.0k
    --i; --e;
442
14.0k
  }
443
11.8k
  CheckPending = false;
444
11.8k
}
445
446
/// Remove SU from the ready set for this boundary.
447
42.2k
void ConvergingVLIWScheduler::VLIWSchedBoundary::removeReady(SUnit *SU) {
448
42.2k
  if (Available.isInQueue(SU))
449
41.1k
    Available.remove(Available.find(SU));
450
1.08k
  else {
451
1.08k
    assert(Pending.isInQueue(SU) && "bad ready count");
452
1.08k
    Pending.remove(Pending.find(SU));
453
1.08k
  }
454
42.2k
}
455
456
/// If this queue only has one ready candidate, return it. As a side effect,
457
/// advance the cycle until at least one node is ready. If multiple instructions
458
/// are ready, return NULL.
459
41.0k
SUnit *ConvergingVLIWScheduler::VLIWSchedBoundary::pickOnlyChoice() {
460
41.0k
  if (CheckPending)
461
1.19k
    releasePending();
462
41.0k
463
51.6k
  auto AdvanceCycle = [this]() {
464
51.6k
    if (Available.empty())
465
10.1k
      return true;
466
41.4k
    if (Available.size() == 1 && 
Pending.size() > 019.0k
)
467
4.82k
      return !ResourceModel->isResourceAvailable(*Available.begin(), isTop()) ||
468
4.82k
        
getWeakLeft(*Available.begin(), isTop()) != 04.39k
;
469
36.6k
    return false;
470
36.6k
  };
471
51.6k
  for (unsigned i = 0; AdvanceCycle(); 
++i10.6k
) {
472
10.6k
    assert(i <= (HazardRec->getMaxLookAhead() + MaxMinLatency) &&
473
10.6k
           "permanent hazard"); (void)i;
474
10.6k
    ResourceModel->reserveResources(nullptr, isTop());
475
10.6k
    bumpCycle();
476
10.6k
    releasePending();
477
10.6k
  }
478
41.0k
  if (Available.size() == 1)
479
18.6k
    return *Available.begin();
480
22.4k
  return nullptr;
481
22.4k
}
482
483
#ifndef NDEBUG
484
void ConvergingVLIWScheduler::traceCandidate(const char *Label,
485
      const ReadyQueue &Q, SUnit *SU, int Cost, PressureChange P) {
486
  dbgs() << Label << " " << Q.getName() << " ";
487
  if (P.isValid())
488
    dbgs() << DAG->TRI->getRegPressureSetName(P.getPSet()) << ":"
489
           << P.getUnitInc() << " ";
490
  else
491
    dbgs() << "     ";
492
  dbgs() << "cost(" << Cost << ")\t";
493
  DAG->dumpNode(*SU);
494
}
495
496
// Very detailed queue dump, to be used with higher verbosity levels.
497
void ConvergingVLIWScheduler::readyQueueVerboseDump(
498
      const RegPressureTracker &RPTracker, SchedCandidate &Candidate,
499
      ReadyQueue &Q) {
500
  RegPressureTracker &TempTracker = const_cast<RegPressureTracker &>(RPTracker);
501
502
  dbgs() << ">>> " << Q.getName() << "\n";
503
  for (ReadyQueue::iterator I = Q.begin(), E = Q.end(); I != E; ++I) {
504
    RegPressureDelta RPDelta;
505
    TempTracker.getMaxPressureDelta((*I)->getInstr(), RPDelta,
506
                                    DAG->getRegionCriticalPSets(),
507
                                    DAG->getRegPressure().MaxSetPressure);
508
    std::stringstream dbgstr;
509
    dbgstr << "SU(" << std::setw(3) << (*I)->NodeNum << ")";
510
    dbgs() << dbgstr.str();
511
    SchedulingCost(Q, *I, Candidate, RPDelta, true);
512
    dbgs() << "\t";
513
    (*I)->getInstr()->dump();
514
  }
515
  dbgs() << "\n";
516
}
517
#endif
518
519
/// isSingleUnscheduledPred - If SU2 is the only unscheduled predecessor
520
/// of SU, return true (we may have duplicates)
521
29.4k
static inline bool isSingleUnscheduledPred(SUnit *SU, SUnit *SU2) {
522
29.4k
  if (SU->NumPredsLeft == 0)
523
256
    return false;
524
29.2k
525
47.1k
  
for (auto &Pred : SU->Preds)29.2k
{
526
47.1k
    // We found an available, but not scheduled, predecessor.
527
47.1k
    if (!Pred.getSUnit()->isScheduled && 
(Pred.getSUnit() != SU2)37.6k
)
528
17.3k
      return false;
529
47.1k
  }
530
29.2k
531
29.2k
  
return true11.8k
;
532
29.2k
}
533
534
/// isSingleUnscheduledSucc - If SU2 is the only unscheduled successor
535
/// of SU, return true (we may have duplicates)
536
22.8k
static inline bool isSingleUnscheduledSucc(SUnit *SU, SUnit *SU2) {
537
22.8k
  if (SU->NumSuccsLeft == 0)
538
125
    return false;
539
22.6k
540
40.3k
  
for (auto &Succ : SU->Succs)22.6k
{
541
40.3k
    // We found an available, but not scheduled, successor.
542
40.3k
    if (!Succ.getSUnit()->isScheduled && 
(Succ.getSUnit() != SU2)31.2k
)
543
10.9k
      return false;
544
40.3k
  }
545
22.6k
  
return true11.7k
;
546
22.6k
}
547
548
/// Check if the instruction changes the register pressure of a register in the
549
/// high pressure set. The function returns a negative value if the pressure
550
/// decreases and a positive value is the pressure increases. If the instruction
551
/// doesn't use a high pressure register or doesn't change the register
552
/// pressure, then return 0.
553
76.9k
int ConvergingVLIWScheduler::pressureChange(const SUnit *SU, bool isBotUp) {
554
76.9k
  PressureDiff &PD = DAG->getPressureDiff(SU);
555
954k
  for (auto &P : PD) {
556
954k
    if (!P.isValid())
557
877k
      continue;
558
76.7k
    // The pressure differences are computed bottom-up, so the comparision for
559
76.7k
    // an increase is positive in the bottom direction, but negative in the
560
76.7k
    //  top-down direction.
561
76.7k
    if (HighPressureSets[P.getPSet()])
562
18.4k
      return (isBotUp ? 
P.getUnitInc()11.3k
:
-P.getUnitInc()7.15k
);
563
76.7k
  }
564
76.9k
  
return 058.4k
;
565
76.9k
}
566
567
// Constants used to denote relative importance of
568
// heuristic components for cost computation.
569
static const unsigned PriorityOne = 200;
570
static const unsigned PriorityTwo = 50;
571
static const unsigned PriorityThree = 75;
572
static const unsigned ScaleTwo = 10;
573
574
/// Single point to compute overall scheduling cost.
575
/// TODO: More heuristics will be used soon.
576
int ConvergingVLIWScheduler::SchedulingCost(ReadyQueue &Q, SUnit *SU,
577
                                            SchedCandidate &Candidate,
578
                                            RegPressureDelta &Delta,
579
102k
                                            bool verbose) {
580
102k
  // Initial trivial priority.
581
102k
  int ResCount = 1;
582
102k
583
102k
  // Do not waste time on a node that is already scheduled.
584
102k
  if (!SU || SU->isScheduled)
585
0
    return ResCount;
586
102k
587
102k
  LLVM_DEBUG(if (verbose) dbgs()
588
102k
             << ((Q.getID() == TopQID) ? "(top|" : "(bot|"));
589
102k
  // Forced priority is high.
590
102k
  if (SU->isScheduleHigh) {
591
0
    ResCount += PriorityOne;
592
0
    LLVM_DEBUG(dbgs() << "H|");
593
0
  }
594
102k
595
102k
  unsigned IsAvailableAmt = 0;
596
102k
  // Critical path first.
597
102k
  if (Q.getID() == TopQID) {
598
54.7k
    if (Top.isLatencyBound(SU)) {
599
21.1k
      LLVM_DEBUG(if (verbose) dbgs() << "LB|");
600
21.1k
      ResCount += (SU->getHeight() * ScaleTwo);
601
21.1k
    }
602
54.7k
603
54.7k
    LLVM_DEBUG(if (verbose) {
604
54.7k
      std::stringstream dbgstr;
605
54.7k
      dbgstr << "h" << std::setw(3) << SU->getHeight() << "|";
606
54.7k
      dbgs() << dbgstr.str();
607
54.7k
    });
608
54.7k
609
54.7k
    // If resources are available for it, multiply the
610
54.7k
    // chance of scheduling.
611
54.7k
    if (Top.ResourceModel->isResourceAvailable(SU, true)) {
612
39.0k
      IsAvailableAmt = (PriorityTwo + PriorityThree);
613
39.0k
      ResCount += IsAvailableAmt;
614
39.0k
      LLVM_DEBUG(if (verbose) dbgs() << "A|");
615
39.0k
    } else
616
54.7k
      LLVM_DEBUG(if (verbose) dbgs() << " |");
617
54.7k
  } else {
618
47.9k
    if (Bot.isLatencyBound(SU)) {
619
19.1k
      LLVM_DEBUG(if (verbose) dbgs() << "LB|");
620
19.1k
      ResCount += (SU->getDepth() * ScaleTwo);
621
19.1k
    }
622
47.9k
623
47.9k
    LLVM_DEBUG(if (verbose) {
624
47.9k
      std::stringstream dbgstr;
625
47.9k
      dbgstr << "d" << std::setw(3) << SU->getDepth() << "|";
626
47.9k
      dbgs() << dbgstr.str();
627
47.9k
    });
628
47.9k
629
47.9k
    // If resources are available for it, multiply the
630
47.9k
    // chance of scheduling.
631
47.9k
    if (Bot.ResourceModel->isResourceAvailable(SU, false)) {
632
37.9k
      IsAvailableAmt = (PriorityTwo + PriorityThree);
633
37.9k
      ResCount += IsAvailableAmt;
634
37.9k
      LLVM_DEBUG(if (verbose) dbgs() << "A|");
635
37.9k
    } else
636
47.9k
      LLVM_DEBUG(if (verbose) dbgs() << " |");
637
47.9k
  }
638
102k
639
102k
  unsigned NumNodesBlocking = 0;
640
102k
  if (Q.getID() == TopQID) {
641
54.7k
    // How many SUs does it block from scheduling?
642
54.7k
    // Look at all of the successors of this node.
643
54.7k
    // Count the number of nodes that
644
54.7k
    // this node is the sole unscheduled node for.
645
54.7k
    if (Top.isLatencyBound(SU))
646
21.1k
      for (const SDep &SI : SU->Succs)
647
29.4k
        if (isSingleUnscheduledPred(SI.getSUnit(), SU))
648
11.8k
          ++NumNodesBlocking;
649
54.7k
  } else {
650
47.9k
    // How many unscheduled predecessors block this node?
651
47.9k
    if (Bot.isLatencyBound(SU))
652
19.1k
      for (const SDep &PI : SU->Preds)
653
22.8k
        if (isSingleUnscheduledSucc(PI.getSUnit(), SU))
654
11.7k
          ++NumNodesBlocking;
655
47.9k
  }
656
102k
  ResCount += (NumNodesBlocking * ScaleTwo);
657
102k
658
102k
  LLVM_DEBUG(if (verbose) {
659
102k
    std::stringstream dbgstr;
660
102k
    dbgstr << "blk " << std::setw(2) << NumNodesBlocking << ")|";
661
102k
    dbgs() << dbgstr.str();
662
102k
  });
663
102k
664
102k
  // Factor in reg pressure as a heuristic.
665
102k
  if (!IgnoreBBRegPressure) {
666
102k
    // Decrease priority by the amount that register pressure exceeds the limit.
667
102k
    ResCount -= (Delta.Excess.getUnitInc()*PriorityOne);
668
102k
    // Decrease priority if register pressure exceeds the limit.
669
102k
    ResCount -= (Delta.CriticalMax.getUnitInc()*PriorityOne);
670
102k
    // Decrease priority slightly if register pressure would increase over the
671
102k
    // current maximum.
672
102k
    ResCount -= (Delta.CurrentMax.getUnitInc()*PriorityTwo);
673
102k
    // If there are register pressure issues, then we remove the value added for
674
102k
    // the instruction being available. The rationale is that we really don't
675
102k
    // want to schedule an instruction that causes a spill.
676
102k
    if (IsAvailableAmt && 
pressureChange(SU, Q.getID() != TopQID) > 076.9k
&&
677
102k
        
(17.7k
Delta.Excess.getUnitInc()17.7k
||
Delta.CriticalMax.getUnitInc()17.6k
||
678
17.7k
         
Delta.CurrentMax.getUnitInc()5.86k
))
679
11.9k
      ResCount -= IsAvailableAmt;
680
102k
    LLVM_DEBUG(if (verbose) {
681
102k
      dbgs() << "RP " << Delta.Excess.getUnitInc() << "/"
682
102k
             << Delta.CriticalMax.getUnitInc() << "/"
683
102k
             << Delta.CurrentMax.getUnitInc() << ")|";
684
102k
    });
685
102k
  }
686
102k
687
102k
  // Give a little extra priority to a .cur instruction if there is a resource
688
102k
  // available for it.
689
102k
  auto &QST = DAG->MF.getSubtarget<HexagonSubtarget>();
690
102k
  auto &QII = *QST.getInstrInfo();
691
102k
  if (SU->isInstr() && QII.mayBeCurLoad(*SU->getInstr())) {
692
2.11k
    if (Q.getID() == TopQID &&
693
2.11k
        
Top.ResourceModel->isResourceAvailable(SU, true)1.34k
) {
694
271
      ResCount += PriorityTwo;
695
271
      LLVM_DEBUG(if (verbose) dbgs() << "C|");
696
1.84k
    } else if (Q.getID() == BotQID &&
697
1.84k
               
Bot.ResourceModel->isResourceAvailable(SU, false)772
) {
698
321
      ResCount += PriorityTwo;
699
321
      LLVM_DEBUG(if (verbose) dbgs() << "C|");
700
321
    }
701
2.11k
  }
702
102k
703
102k
  // Give preference to a zero latency instruction if the dependent
704
102k
  // instruction is in the current packet.
705
102k
  if (Q.getID() == TopQID && 
getWeakLeft(SU, true) == 054.7k
) {
706
54.3k
    for (const SDep &PI : SU->Preds) {
707
24.5k
      if (!PI.getSUnit()->getInstr()->isPseudo() && 
PI.isAssignedRegDep()19.4k
&&
708
24.5k
          
PI.getLatency() == 017.9k
&&
709
24.5k
          
Top.ResourceModel->isInPacket(PI.getSUnit())634
) {
710
285
        ResCount += PriorityThree;
711
285
        LLVM_DEBUG(if (verbose) dbgs() << "Z|");
712
285
      }
713
24.5k
    }
714
54.3k
  } else 
if (48.3k
Q.getID() == BotQID48.3k
&&
getWeakLeft(SU, false) == 047.9k
) {
715
43.5k
    for (const SDep &SI : SU->Succs) {
716
26.5k
      if (!SI.getSUnit()->getInstr()->isPseudo() && 
SI.isAssignedRegDep()21.3k
&&
717
26.5k
          
SI.getLatency() == 014.1k
&&
718
26.5k
          
Bot.ResourceModel->isInPacket(SI.getSUnit())3.19k
) {
719
2.54k
        ResCount += PriorityThree;
720
2.54k
        LLVM_DEBUG(if (verbose) dbgs() << "Z|");
721
2.54k
      }
722
26.5k
    }
723
43.5k
  }
724
102k
725
102k
  // If the instruction has a non-zero latency dependence with an instruction in
726
102k
  // the current packet, then it should not be scheduled yet. The case occurs
727
102k
  // when the dependent instruction is scheduled in a new packet, so the
728
102k
  // scheduler updates the current cycle and pending instructions become
729
102k
  // available.
730
102k
  if (CheckEarlyAvail) {
731
102k
    if (Q.getID() == TopQID) {
732
54.7k
      for (const auto &PI : SU->Preds) {
733
25.3k
        if (PI.getLatency() > 0 &&
734
25.3k
            
Top.ResourceModel->isInPacket(PI.getSUnit())18.5k
) {
735
0
          ResCount -= PriorityOne;
736
0
          LLVM_DEBUG(if (verbose) dbgs() << "D|");
737
0
        }
738
25.3k
      }
739
54.7k
    } else {
740
47.9k
      for (const auto &SI : SU->Succs) {
741
31.7k
        if (SI.getLatency() > 0 &&
742
31.7k
            
Bot.ResourceModel->isInPacket(SI.getSUnit())16.6k
) {
743
0
          ResCount -= PriorityOne;
744
0
          LLVM_DEBUG(if (verbose) dbgs() << "D|");
745
0
        }
746
31.7k
      }
747
47.9k
    }
748
102k
  }
749
102k
750
102k
  LLVM_DEBUG(if (verbose) {
751
102k
    std::stringstream dbgstr;
752
102k
    dbgstr << "Total " << std::setw(4) << ResCount << ")";
753
102k
    dbgs() << dbgstr.str();
754
102k
  });
755
102k
756
102k
  return ResCount;
757
102k
}
758
759
/// Pick the best candidate from the top queue.
760
///
761
/// TODO: getMaxPressureDelta results can be mostly cached for each SUnit during
762
/// DAG building. To adjust for the current scheduling location we need to
763
/// maintain the number of vreg uses remaining to be top-scheduled.
764
ConvergingVLIWScheduler::CandResult ConvergingVLIWScheduler::
765
pickNodeFromQueue(VLIWSchedBoundary &Zone, const RegPressureTracker &RPTracker,
766
21.6k
                  SchedCandidate &Candidate) {
767
21.6k
  ReadyQueue &Q = Zone.Available;
768
21.6k
  LLVM_DEBUG(if (SchedDebugVerboseLevel > 1)
769
21.6k
                 readyQueueVerboseDump(RPTracker, Candidate, Q);
770
21.6k
             else Q.dump(););
771
21.6k
772
21.6k
  // getMaxPressureDelta temporarily modifies the tracker.
773
21.6k
  RegPressureTracker &TempTracker = const_cast<RegPressureTracker&>(RPTracker);
774
21.6k
775
21.6k
  // BestSU remains NULL if no top candidates beat the best existing candidate.
776
21.6k
  CandResult FoundCandidate = NoCand;
777
124k
  for (ReadyQueue::iterator I = Q.begin(), E = Q.end(); I != E; 
++I102k
) {
778
102k
    RegPressureDelta RPDelta;
779
102k
    TempTracker.getMaxPressureDelta((*I)->getInstr(), RPDelta,
780
102k
                                    DAG->getRegionCriticalPSets(),
781
102k
                                    DAG->getRegPressure().MaxSetPressure);
782
102k
783
102k
    int CurrentCost = SchedulingCost(Q, *I, Candidate, RPDelta, false);
784
102k
785
102k
    // Initialize the candidate if needed.
786
102k
    if (!Candidate.SU) {
787
21.6k
      LLVM_DEBUG(traceCandidate("DCAND", Q, *I, CurrentCost));
788
21.6k
      Candidate.SU = *I;
789
21.6k
      Candidate.RPDelta = RPDelta;
790
21.6k
      Candidate.SCost = CurrentCost;
791
21.6k
      FoundCandidate = NodeOrder;
792
21.6k
      continue;
793
21.6k
    }
794
81.0k
795
81.0k
    // Choose node order for negative cost candidates. There is no good
796
81.0k
    // candidate in this case.
797
81.0k
    if (CurrentCost < 0 && 
Candidate.SCost < 016.7k
) {
798
13.9k
      if ((Q.getID() == TopQID && 
(*I)->NodeNum < Candidate.SU->NodeNum2.86k
)
799
13.9k
          || 
(13.0k
Q.getID() == BotQID13.0k
&&
(*I)->NodeNum > Candidate.SU->NodeNum11.0k
)) {
800
2.45k
        LLVM_DEBUG(traceCandidate("NCAND", Q, *I, CurrentCost));
801
2.45k
        Candidate.SU = *I;
802
2.45k
        Candidate.RPDelta = RPDelta;
803
2.45k
        Candidate.SCost = CurrentCost;
804
2.45k
        FoundCandidate = NodeOrder;
805
2.45k
      }
806
13.9k
      continue;
807
13.9k
    }
808
67.1k
809
67.1k
    // Best cost.
810
67.1k
    if (CurrentCost > Candidate.SCost) {
811
7.88k
      LLVM_DEBUG(traceCandidate("CCAND", Q, *I, CurrentCost));
812
7.88k
      Candidate.SU = *I;
813
7.88k
      Candidate.RPDelta = RPDelta;
814
7.88k
      Candidate.SCost = CurrentCost;
815
7.88k
      FoundCandidate = BestCost;
816
7.88k
      continue;
817
7.88k
    }
818
59.2k
819
59.2k
    // Choose an instruction that does not depend on an artificial edge.
820
59.2k
    unsigned CurrWeak = getWeakLeft(*I, (Q.getID() == TopQID));
821
59.2k
    unsigned CandWeak = getWeakLeft(Candidate.SU, (Q.getID() == TopQID));
822
59.2k
    if (CurrWeak != CandWeak) {
823
1.12k
      if (CurrWeak < CandWeak) {
824
210
        LLVM_DEBUG(traceCandidate("WCAND", Q, *I, CurrentCost));
825
210
        Candidate.SU = *I;
826
210
        Candidate.RPDelta = RPDelta;
827
210
        Candidate.SCost = CurrentCost;
828
210
        FoundCandidate = Weak;
829
210
      }
830
1.12k
      continue;
831
1.12k
    }
832
58.1k
833
58.1k
    if (CurrentCost == Candidate.SCost && 
Zone.isLatencyBound(*I)41.3k
) {
834
10.7k
      unsigned CurrSize, CandSize;
835
10.7k
      if (Q.getID() == TopQID) {
836
5.24k
        CurrSize = (*I)->Succs.size();
837
5.24k
        CandSize = Candidate.SU->Succs.size();
838
5.54k
      } else {
839
5.54k
        CurrSize = (*I)->Preds.size();
840
5.54k
        CandSize = Candidate.SU->Preds.size();
841
5.54k
      }
842
10.7k
      if (CurrSize > CandSize) {
843
531
        LLVM_DEBUG(traceCandidate("SPCAND", Q, *I, CurrentCost));
844
531
        Candidate.SU = *I;
845
531
        Candidate.RPDelta = RPDelta;
846
531
        Candidate.SCost = CurrentCost;
847
531
        FoundCandidate = BestCost;
848
531
      }
849
10.7k
      // Keep the old candidate if it's a better candidate. That is, don't use
850
10.7k
      // the subsequent tie breaker.
851
10.7k
      if (CurrSize != CandSize)
852
1.14k
        continue;
853
56.9k
    }
854
56.9k
855
56.9k
    // Tie breaker.
856
56.9k
    // To avoid scheduling indeterminism, we need a tie breaker
857
56.9k
    // for the case when cost is identical for two nodes.
858
56.9k
    if (UseNewerCandidate && CurrentCost == Candidate.SCost) {
859
40.1k
      if ((Q.getID() == TopQID && 
(*I)->NodeNum < Candidate.SU->NodeNum25.7k
)
860
40.1k
          || 
(35.1k
Q.getID() == BotQID35.1k
&&
(*I)->NodeNum > Candidate.SU->NodeNum14.3k
)) {
861
8.82k
        LLVM_DEBUG(traceCandidate("TCAND", Q, *I, CurrentCost));
862
8.82k
        Candidate.SU = *I;
863
8.82k
        Candidate.RPDelta = RPDelta;
864
8.82k
        Candidate.SCost = CurrentCost;
865
8.82k
        FoundCandidate = NodeOrder;
866
8.82k
        continue;
867
8.82k
      }
868
48.1k
    }
869
48.1k
870
48.1k
    // Fall through to original instruction order.
871
48.1k
    // Only consider node order if Candidate was chosen from this Q.
872
48.1k
    if (FoundCandidate == NoCand)
873
0
      continue;
874
48.1k
  }
875
21.6k
  return FoundCandidate;
876
21.6k
}
877
878
/// Pick the best candidate node from either the top or bottom queue.
879
29.4k
SUnit *ConvergingVLIWScheduler::pickNodeBidrectional(bool &IsTopNode) {
880
29.4k
  // Schedule as far as possible in the direction of no choice. This is most
881
29.4k
  // efficient, but also provides the best heuristics for CriticalPSets.
882
29.4k
  if (SUnit *SU = Bot.pickOnlyChoice()) {
883
17.9k
    LLVM_DEBUG(dbgs() << "Picked only Bottom\n");
884
17.9k
    IsTopNode = false;
885
17.9k
    return SU;
886
17.9k
  }
887
11.5k
  if (SUnit *SU = Top.pickOnlyChoice()) {
888
736
    LLVM_DEBUG(dbgs() << "Picked only Top\n");
889
736
    IsTopNode = true;
890
736
    return SU;
891
736
  }
892
10.8k
  SchedCandidate BotCand;
893
10.8k
  // Prefer bottom scheduling when heuristics are silent.
894
10.8k
  CandResult BotResult = pickNodeFromQueue(Bot,
895
10.8k
                                           DAG->getBotRPTracker(), BotCand);
896
10.8k
  assert(BotResult != NoCand && "failed to find the first candidate");
897
10.8k
898
10.8k
  // If either Q has a single candidate that provides the least increase in
899
10.8k
  // Excess pressure, we can immediately schedule from that Q.
900
10.8k
  //
901
10.8k
  // RegionCriticalPSets summarizes the pressure within the scheduled region and
902
10.8k
  // affects picking from either Q. If scheduling in one direction must
903
10.8k
  // increase pressure for one of the excess PSets, then schedule in that
904
10.8k
  // direction first to provide more freedom in the other direction.
905
10.8k
  if (BotResult == SingleExcess || BotResult == SingleCritical) {
906
0
    LLVM_DEBUG(dbgs() << "Prefered Bottom Node\n");
907
0
    IsTopNode = false;
908
0
    return BotCand.SU;
909
0
  }
910
10.8k
  // Check if the top Q has a better candidate.
911
10.8k
  SchedCandidate TopCand;
912
10.8k
  CandResult TopResult = pickNodeFromQueue(Top,
913
10.8k
                                           DAG->getTopRPTracker(), TopCand);
914
10.8k
  assert(TopResult != NoCand && "failed to find the first candidate");
915
10.8k
916
10.8k
  if (TopResult == SingleExcess || TopResult == SingleCritical) {
917
0
    LLVM_DEBUG(dbgs() << "Prefered Top Node\n");
918
0
    IsTopNode = true;
919
0
    return TopCand.SU;
920
0
  }
921
10.8k
  // If either Q has a single candidate that minimizes pressure above the
922
10.8k
  // original region's pressure pick it.
923
10.8k
  if (BotResult == SingleMax) {
924
0
    LLVM_DEBUG(dbgs() << "Prefered Bottom Node SingleMax\n");
925
0
    IsTopNode = false;
926
0
    return BotCand.SU;
927
0
  }
928
10.8k
  if (TopResult == SingleMax) {
929
0
    LLVM_DEBUG(dbgs() << "Prefered Top Node SingleMax\n");
930
0
    IsTopNode = true;
931
0
    return TopCand.SU;
932
0
  }
933
10.8k
  if (TopCand.SCost > BotCand.SCost) {
934
4.14k
    LLVM_DEBUG(dbgs() << "Prefered Top Node Cost\n");
935
4.14k
    IsTopNode = true;
936
4.14k
    return TopCand.SU;
937
4.14k
  }
938
6.69k
  // Otherwise prefer the bottom candidate in node order.
939
6.69k
  LLVM_DEBUG(dbgs() << "Prefered Bottom in Node order\n");
940
6.69k
  IsTopNode = false;
941
6.69k
  return BotCand.SU;
942
6.69k
}
943
944
/// Pick the best node to balance the schedule. Implements MachineSchedStrategy.
945
34.5k
SUnit *ConvergingVLIWScheduler::pickNode(bool &IsTopNode) {
946
34.5k
  if (DAG->top() == DAG->bottom()) {
947
5.01k
    assert(Top.Available.empty() && Top.Pending.empty() &&
948
5.01k
           Bot.Available.empty() && Bot.Pending.empty() && "ReadyQ garbage");
949
5.01k
    return nullptr;
950
5.01k
  }
951
29.4k
  SUnit *SU;
952
29.4k
  if (ForceTopDown) {
953
0
    SU = Top.pickOnlyChoice();
954
0
    if (!SU) {
955
0
      SchedCandidate TopCand;
956
0
      CandResult TopResult =
957
0
        pickNodeFromQueue(Top, DAG->getTopRPTracker(), TopCand);
958
0
      assert(TopResult != NoCand && "failed to find the first candidate");
959
0
      (void)TopResult;
960
0
      SU = TopCand.SU;
961
0
    }
962
0
    IsTopNode = true;
963
29.4k
  } else if (ForceBottomUp) {
964
0
    SU = Bot.pickOnlyChoice();
965
0
    if (!SU) {
966
0
      SchedCandidate BotCand;
967
0
      CandResult BotResult =
968
0
        pickNodeFromQueue(Bot, DAG->getBotRPTracker(), BotCand);
969
0
      assert(BotResult != NoCand && "failed to find the first candidate");
970
0
      (void)BotResult;
971
0
      SU = BotCand.SU;
972
0
    }
973
0
    IsTopNode = false;
974
29.4k
  } else {
975
29.4k
    SU = pickNodeBidrectional(IsTopNode);
976
29.4k
  }
977
29.4k
  if (SU->isTopReady())
978
15.8k
    Top.removeReady(SU);
979
29.4k
  if (SU->isBottomReady())
980
26.3k
    Bot.removeReady(SU);
981
29.4k
982
29.4k
  LLVM_DEBUG(dbgs() << "*** " << (IsTopNode ? "Top" : "Bottom")
983
29.4k
                    << " Scheduling instruction in cycle "
984
29.4k
                    << (IsTopNode ? Top.CurrCycle : Bot.CurrCycle) << " ("
985
29.4k
                    << reportPackets() << ")\n";
986
29.4k
             DAG->dumpNode(*SU));
987
29.4k
  return SU;
988
29.4k
}
989
990
/// Update the scheduler's state after scheduling a node. This is the same node
991
/// that was just returned by pickNode(). However, VLIWMachineScheduler needs
992
/// to update it's state based on the current cycle before MachineSchedStrategy
993
/// does.
994
29.4k
void ConvergingVLIWScheduler::schedNode(SUnit *SU, bool IsTopNode) {
995
29.4k
  if (IsTopNode) {
996
4.87k
    Top.bumpNode(SU);
997
4.87k
    SU->TopReadyCycle = Top.CurrCycle;
998
24.6k
  } else {
999
24.6k
    Bot.bumpNode(SU);
1000
24.6k
    SU->BotReadyCycle = Bot.CurrCycle;
1001
24.6k
  }
1002
29.4k
}