Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/SelectionDAG/ScheduleDAGFast.cpp
Line
Count
Source (jump to first uncovered line)
1
//===----- ScheduleDAGFast.cpp - Fast poor 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 a fast scheduler.
10
//
11
//===----------------------------------------------------------------------===//
12
13
#include "InstrEmitter.h"
14
#include "ScheduleDAGSDNodes.h"
15
#include "SDNodeDbgValue.h"
16
#include "llvm/ADT/STLExtras.h"
17
#include "llvm/ADT/SmallSet.h"
18
#include "llvm/ADT/Statistic.h"
19
#include "llvm/CodeGen/SchedulerRegistry.h"
20
#include "llvm/CodeGen/SelectionDAGISel.h"
21
#include "llvm/CodeGen/TargetInstrInfo.h"
22
#include "llvm/CodeGen/TargetRegisterInfo.h"
23
#include "llvm/IR/DataLayout.h"
24
#include "llvm/IR/InlineAsm.h"
25
#include "llvm/Support/Debug.h"
26
#include "llvm/Support/ErrorHandling.h"
27
#include "llvm/Support/raw_ostream.h"
28
using namespace llvm;
29
30
#define DEBUG_TYPE "pre-RA-sched"
31
32
STATISTIC(NumUnfolds,    "Number of nodes unfolded");
33
STATISTIC(NumDups,       "Number of duplicated nodes");
34
STATISTIC(NumPRCopies,   "Number of physical copies");
35
36
static RegisterScheduler
37
  fastDAGScheduler("fast", "Fast suboptimal list scheduling",
38
                   createFastDAGScheduler);
39
static RegisterScheduler
40
  linearizeDAGScheduler("linearize", "Linearize DAG, no scheduling",
41
                        createDAGLinearizer);
42
43
44
namespace {
45
  /// FastPriorityQueue - A degenerate priority queue that considers
46
  /// all nodes to have the same priority.
47
  ///
48
  struct FastPriorityQueue {
49
    SmallVector<SUnit *, 16> Queue;
50
51
448
    bool empty() const { return Queue.empty(); }
52
53
201
    void push(SUnit *U) {
54
201
      Queue.push_back(U);
55
201
    }
56
57
214
    SUnit *pop() {
58
214
      if (empty()) 
return nullptr13
;
59
201
      SUnit *V = Queue.back();
60
201
      Queue.pop_back();
61
201
      return V;
62
201
    }
63
  };
64
65
//===----------------------------------------------------------------------===//
66
/// ScheduleDAGFast - The actual "fast" list scheduler implementation.
67
///
68
class ScheduleDAGFast : public ScheduleDAGSDNodes {
69
private:
70
  /// AvailableQueue - The priority queue to use for the available SUnits.
71
  FastPriorityQueue AvailableQueue;
72
73
  /// LiveRegDefs - A set of physical registers and their definition
74
  /// that are "live". These nodes must be scheduled before any other nodes that
75
  /// modifies the registers can be scheduled.
76
  unsigned NumLiveRegs;
77
  std::vector<SUnit*> LiveRegDefs;
78
  std::vector<unsigned> LiveRegCycles;
79
80
public:
81
  ScheduleDAGFast(MachineFunction &mf)
82
34
    : ScheduleDAGSDNodes(mf) {}
83
84
  void Schedule() override;
85
86
  /// AddPred - adds a predecessor edge to SUnit SU.
87
  /// This returns true if this is a new predecessor.
88
73
  void AddPred(SUnit *SU, const SDep &D) {
89
73
    SU->addPred(D);
90
73
  }
91
92
  /// RemovePred - removes a predecessor edge from SUnit SU.
93
  /// This returns true if an edge was removed.
94
23
  void RemovePred(SUnit *SU, const SDep &D) {
95
23
    SU->removePred(D);
96
23
  }
97
98
private:
99
  void ReleasePred(SUnit *SU, SDep *PredEdge);
100
  void ReleasePredecessors(SUnit *SU, unsigned CurCycle);
101
  void ScheduleNodeBottomUp(SUnit*, unsigned);
102
  SUnit *CopyAndMoveSuccessors(SUnit*);
103
  void InsertCopiesAndMoveSuccs(SUnit*, unsigned,
104
                                const TargetRegisterClass*,
105
                                const TargetRegisterClass*,
106
                                SmallVectorImpl<SUnit*>&);
107
  bool DelayForLiveRegsBottomUp(SUnit*, SmallVectorImpl<unsigned>&);
108
  void ListScheduleBottomUp();
109
110
  /// forceUnitLatencies - The fast scheduler doesn't care about real latencies.
111
203
  bool forceUnitLatencies() const override { return true; }
112
};
113
}  // end anonymous namespace
114
115
116
/// Schedule - Schedule the DAG using list scheduling.
117
34
void ScheduleDAGFast::Schedule() {
118
34
  LLVM_DEBUG(dbgs() << "********** List Scheduling **********\n");
119
34
120
34
  NumLiveRegs = 0;
121
34
  LiveRegDefs.resize(TRI->getNumRegs(), nullptr);
122
34
  LiveRegCycles.resize(TRI->getNumRegs(), 0);
123
34
124
34
  // Build the scheduling graph.
125
34
  BuildSchedGraph(nullptr);
126
34
127
34
  LLVM_DEBUG(dump());
128
34
129
34
  // Execute the actual scheduling loop.
130
34
  ListScheduleBottomUp();
131
34
}
132
133
//===----------------------------------------------------------------------===//
134
//  Bottom-Up Scheduling
135
//===----------------------------------------------------------------------===//
136
137
/// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to
138
/// the AvailableQueue if the count reaches zero. Also update its cycle bound.
139
225
void ScheduleDAGFast::ReleasePred(SUnit *SU, SDep *PredEdge) {
140
225
  SUnit *PredSU = PredEdge->getSUnit();
141
225
142
#ifndef NDEBUG
143
  if (PredSU->NumSuccsLeft == 0) {
144
    dbgs() << "*** Scheduling failed! ***\n";
145
    dumpNode(*PredSU);
146
    dbgs() << " has been released too many times!\n";
147
    llvm_unreachable(nullptr);
148
  }
149
#endif
150
  --PredSU->NumSuccsLeft;
151
225
152
225
  // If all the node's successors are scheduled, this node is ready
153
225
  // to be scheduled. Ignore the special EntrySU node.
154
225
  if (PredSU->NumSuccsLeft == 0 && 
PredSU != &EntrySU170
) {
155
170
    PredSU->isAvailable = true;
156
170
    AvailableQueue.push(PredSU);
157
170
  }
158
225
}
159
160
234
void ScheduleDAGFast::ReleasePredecessors(SUnit *SU, unsigned CurCycle) {
161
234
  // Bottom up: release predecessors
162
234
  for (SDep &Pred : SU->Preds) {
163
225
    ReleasePred(SU, &Pred);
164
225
    if (Pred.isAssignedRegDep()) {
165
30
      // This is a physical register dependency and it's impossible or
166
30
      // expensive to copy the register. Make sure nothing that can
167
30
      // clobber the register is scheduled between the predecessor and
168
30
      // this node.
169
30
      if (!LiveRegDefs[Pred.getReg()]) {
170
30
        ++NumLiveRegs;
171
30
        LiveRegDefs[Pred.getReg()] = Pred.getSUnit();
172
30
        LiveRegCycles[Pred.getReg()] = CurCycle;
173
30
      }
174
30
    }
175
225
  }
176
234
}
177
178
/// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending
179
/// count of its predecessors. If a predecessor pending count is zero, add it to
180
/// the Available queue.
181
200
void ScheduleDAGFast::ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle) {
182
200
  LLVM_DEBUG(dbgs() << "*** Scheduling [" << CurCycle << "]: ");
183
200
  LLVM_DEBUG(dumpNode(*SU));
184
200
185
200
  assert(CurCycle >= SU->getHeight() && "Node scheduled below its height!");
186
200
  SU->setHeightToAtLeast(CurCycle);
187
200
  Sequence.push_back(SU);
188
200
189
200
  ReleasePredecessors(SU, CurCycle);
190
200
191
200
  // Release all the implicit physical register defs that are live.
192
247
  for (SDep &Succ : SU->Succs) {
193
247
    if (Succ.isAssignedRegDep()) {
194
48
      if (LiveRegCycles[Succ.getReg()] == Succ.getSUnit()->getHeight()) {
195
30
        assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");
196
30
        assert(LiveRegDefs[Succ.getReg()] == SU &&
197
30
               "Physical register dependency violated?");
198
30
        --NumLiveRegs;
199
30
        LiveRegDefs[Succ.getReg()] = nullptr;
200
30
        LiveRegCycles[Succ.getReg()] = 0;
201
30
      }
202
48
    }
203
247
  }
204
200
205
200
  SU->isScheduled = true;
206
200
}
207
208
/// CopyAndMoveSuccessors - Clone the specified node and move its scheduled
209
/// successors to the newly created node.
210
13
SUnit *ScheduleDAGFast::CopyAndMoveSuccessors(SUnit *SU) {
211
13
  if (SU->getNode()->getGluedNode())
212
12
    return nullptr;
213
1
214
1
  SDNode *N = SU->getNode();
215
1
  if (!N)
216
0
    return nullptr;
217
1
218
1
  SUnit *NewSU;
219
1
  bool TryUnfold = false;
220
3
  for (unsigned i = 0, e = N->getNumValues(); i != e; 
++i2
) {
221
2
    MVT VT = N->getSimpleValueType(i);
222
2
    if (VT == MVT::Glue)
223
0
      return nullptr;
224
2
    else if (VT == MVT::Other)
225
0
      TryUnfold = true;
226
2
  }
227
2
  
for (const SDValue &Op : N->op_values())1
{
228
2
    MVT VT = Op.getNode()->getSimpleValueType(Op.getResNo());
229
2
    if (VT == MVT::Glue)
230
0
      return nullptr;
231
2
  }
232
1
233
1
  if (TryUnfold) {
234
0
    SmallVector<SDNode*, 2> NewNodes;
235
0
    if (!TII->unfoldMemoryOperand(*DAG, N, NewNodes))
236
0
      return nullptr;
237
0
238
0
    LLVM_DEBUG(dbgs() << "Unfolding SU # " << SU->NodeNum << "\n");
239
0
    assert(NewNodes.size() == 2 && "Expected a load folding node!");
240
0
241
0
    N = NewNodes[1];
242
0
    SDNode *LoadNode = NewNodes[0];
243
0
    unsigned NumVals = N->getNumValues();
244
0
    unsigned OldNumVals = SU->getNode()->getNumValues();
245
0
    for (unsigned i = 0; i != NumVals; ++i)
246
0
      DAG->ReplaceAllUsesOfValueWith(SDValue(SU->getNode(), i), SDValue(N, i));
247
0
    DAG->ReplaceAllUsesOfValueWith(SDValue(SU->getNode(), OldNumVals-1),
248
0
                                   SDValue(LoadNode, 1));
249
0
250
0
    SUnit *NewSU = newSUnit(N);
251
0
    assert(N->getNodeId() == -1 && "Node already inserted!");
252
0
    N->setNodeId(NewSU->NodeNum);
253
0
254
0
    const MCInstrDesc &MCID = TII->get(N->getMachineOpcode());
255
0
    for (unsigned i = 0; i != MCID.getNumOperands(); ++i) {
256
0
      if (MCID.getOperandConstraint(i, MCOI::TIED_TO) != -1) {
257
0
        NewSU->isTwoAddress = true;
258
0
        break;
259
0
      }
260
0
    }
261
0
    if (MCID.isCommutable())
262
0
      NewSU->isCommutable = true;
263
0
264
0
    // LoadNode may already exist. This can happen when there is another
265
0
    // load from the same location and producing the same type of value
266
0
    // but it has different alignment or volatileness.
267
0
    bool isNewLoad = true;
268
0
    SUnit *LoadSU;
269
0
    if (LoadNode->getNodeId() != -1) {
270
0
      LoadSU = &SUnits[LoadNode->getNodeId()];
271
0
      isNewLoad = false;
272
0
    } else {
273
0
      LoadSU = newSUnit(LoadNode);
274
0
      LoadNode->setNodeId(LoadSU->NodeNum);
275
0
    }
276
0
277
0
    SDep ChainPred;
278
0
    SmallVector<SDep, 4> ChainSuccs;
279
0
    SmallVector<SDep, 4> LoadPreds;
280
0
    SmallVector<SDep, 4> NodePreds;
281
0
    SmallVector<SDep, 4> NodeSuccs;
282
0
    for (SDep &Pred : SU->Preds) {
283
0
      if (Pred.isCtrl())
284
0
        ChainPred = Pred;
285
0
      else if (Pred.getSUnit()->getNode() &&
286
0
               Pred.getSUnit()->getNode()->isOperandOf(LoadNode))
287
0
        LoadPreds.push_back(Pred);
288
0
      else
289
0
        NodePreds.push_back(Pred);
290
0
    }
291
0
    for (SDep &Succ : SU->Succs) {
292
0
      if (Succ.isCtrl())
293
0
        ChainSuccs.push_back(Succ);
294
0
      else
295
0
        NodeSuccs.push_back(Succ);
296
0
    }
297
0
298
0
    if (ChainPred.getSUnit()) {
299
0
      RemovePred(SU, ChainPred);
300
0
      if (isNewLoad)
301
0
        AddPred(LoadSU, ChainPred);
302
0
    }
303
0
    for (unsigned i = 0, e = LoadPreds.size(); i != e; ++i) {
304
0
      const SDep &Pred = LoadPreds[i];
305
0
      RemovePred(SU, Pred);
306
0
      if (isNewLoad) {
307
0
        AddPred(LoadSU, Pred);
308
0
      }
309
0
    }
310
0
    for (unsigned i = 0, e = NodePreds.size(); i != e; ++i) {
311
0
      const SDep &Pred = NodePreds[i];
312
0
      RemovePred(SU, Pred);
313
0
      AddPred(NewSU, Pred);
314
0
    }
315
0
    for (unsigned i = 0, e = NodeSuccs.size(); i != e; ++i) {
316
0
      SDep D = NodeSuccs[i];
317
0
      SUnit *SuccDep = D.getSUnit();
318
0
      D.setSUnit(SU);
319
0
      RemovePred(SuccDep, D);
320
0
      D.setSUnit(NewSU);
321
0
      AddPred(SuccDep, D);
322
0
    }
323
0
    for (unsigned i = 0, e = ChainSuccs.size(); i != e; ++i) {
324
0
      SDep D = ChainSuccs[i];
325
0
      SUnit *SuccDep = D.getSUnit();
326
0
      D.setSUnit(SU);
327
0
      RemovePred(SuccDep, D);
328
0
      if (isNewLoad) {
329
0
        D.setSUnit(LoadSU);
330
0
        AddPred(SuccDep, D);
331
0
      }
332
0
    }
333
0
    if (isNewLoad) {
334
0
      SDep D(LoadSU, SDep::Barrier);
335
0
      D.setLatency(LoadSU->Latency);
336
0
      AddPred(NewSU, D);
337
0
    }
338
0
339
0
    ++NumUnfolds;
340
0
341
0
    if (NewSU->NumSuccsLeft == 0) {
342
0
      NewSU->isAvailable = true;
343
0
      return NewSU;
344
0
    }
345
0
    SU = NewSU;
346
0
  }
347
1
348
1
  LLVM_DEBUG(dbgs() << "Duplicating SU # " << SU->NodeNum << "\n");
349
1
  NewSU = Clone(SU);
350
1
351
1
  // New SUnit has the exact same predecessors.
352
1
  for (SDep &Pred : SU->Preds)
353
1
    if (!Pred.isArtificial())
354
1
      AddPred(NewSU, Pred);
355
1
356
1
  // Only copy scheduled successors. Cut them from old node's successor
357
1
  // list and move them over.
358
1
  SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps;
359
2
  for (SDep &Succ : SU->Succs) {
360
2
    if (Succ.isArtificial())
361
0
      continue;
362
2
    SUnit *SuccSU = Succ.getSUnit();
363
2
    if (SuccSU->isScheduled) {
364
1
      SDep D = Succ;
365
1
      D.setSUnit(NewSU);
366
1
      AddPred(SuccSU, D);
367
1
      D.setSUnit(SU);
368
1
      DelDeps.push_back(std::make_pair(SuccSU, D));
369
1
    }
370
2
  }
371
2
  for (unsigned i = 0, e = DelDeps.size(); i != e; 
++i1
)
372
1
    RemovePred(DelDeps[i].first, DelDeps[i].second);
373
1
374
1
  ++NumDups;
375
1
  return NewSU;
376
1
}
377
378
/// InsertCopiesAndMoveSuccs - Insert register copies and move all
379
/// scheduled successors of the given SUnit to the last copy.
380
void ScheduleDAGFast::InsertCopiesAndMoveSuccs(SUnit *SU, unsigned Reg,
381
                                              const TargetRegisterClass *DestRC,
382
                                              const TargetRegisterClass *SrcRC,
383
12
                                              SmallVectorImpl<SUnit*> &Copies) {
384
12
  SUnit *CopyFromSU = newSUnit(static_cast<SDNode *>(nullptr));
385
12
  CopyFromSU->CopySrcRC = SrcRC;
386
12
  CopyFromSU->CopyDstRC = DestRC;
387
12
388
12
  SUnit *CopyToSU = newSUnit(static_cast<SDNode *>(nullptr));
389
12
  CopyToSU->CopySrcRC = DestRC;
390
12
  CopyToSU->CopyDstRC = SrcRC;
391
12
392
12
  // Only copy scheduled successors. Cut them from old node's successor
393
12
  // list and move them over.
394
12
  SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps;
395
38
  for (SDep &Succ : SU->Succs) {
396
38
    if (Succ.isArtificial())
397
0
      continue;
398
38
    SUnit *SuccSU = Succ.getSUnit();
399
38
    if (SuccSU->isScheduled) {
400
22
      SDep D = Succ;
401
22
      D.setSUnit(CopyToSU);
402
22
      AddPred(SuccSU, D);
403
22
      DelDeps.push_back(std::make_pair(SuccSU, Succ));
404
22
    }
405
38
  }
406
34
  for (unsigned i = 0, e = DelDeps.size(); i != e; 
++i22
) {
407
22
    RemovePred(DelDeps[i].first, DelDeps[i].second);
408
22
  }
409
12
  SDep FromDep(SU, SDep::Data, Reg);
410
12
  FromDep.setLatency(SU->Latency);
411
12
  AddPred(CopyFromSU, FromDep);
412
12
  SDep ToDep(CopyFromSU, SDep::Data, 0);
413
12
  ToDep.setLatency(CopyFromSU->Latency);
414
12
  AddPred(CopyToSU, ToDep);
415
12
416
12
  Copies.push_back(CopyFromSU);
417
12
  Copies.push_back(CopyToSU);
418
12
419
12
  ++NumPRCopies;
420
12
}
421
422
/// getPhysicalRegisterVT - Returns the ValueType of the physical register
423
/// definition of the specified node.
424
/// FIXME: Move to SelectionDAG?
425
static MVT getPhysicalRegisterVT(SDNode *N, unsigned Reg,
426
13
                                 const TargetInstrInfo *TII) {
427
13
  unsigned NumRes;
428
13
  if (N->getOpcode() == ISD::CopyFromReg) {
429
12
    // CopyFromReg has: "chain, Val, glue" so operand 1 gives the type.
430
12
    NumRes = 1;
431
12
  } else {
432
1
    const MCInstrDesc &MCID = TII->get(N->getMachineOpcode());
433
1
    assert(MCID.ImplicitDefs && "Physical reg def must be in implicit def list!");
434
1
    NumRes = MCID.getNumDefs();
435
1
    for (const MCPhysReg *ImpDef = MCID.getImplicitDefs(); *ImpDef; 
++ImpDef0
) {
436
1
      if (Reg == *ImpDef)
437
1
        break;
438
0
      ++NumRes;
439
0
    }
440
1
  }
441
13
  return N->getSimpleValueType(NumRes);
442
13
}
443
444
/// CheckForLiveRegDef - Return true and update live register vector if the
445
/// specified register def of the specified SUnit clobbers any "live" registers.
446
static bool CheckForLiveRegDef(SUnit *SU, unsigned Reg,
447
                               std::vector<SUnit*> &LiveRegDefs,
448
                               SmallSet<unsigned, 4> &RegAdded,
449
                               SmallVectorImpl<unsigned> &LRegs,
450
65
                               const TargetRegisterInfo *TRI) {
451
65
  bool Added = false;
452
350
  for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); 
++AI285
) {
453
285
    if (LiveRegDefs[*AI] && 
LiveRegDefs[*AI] != SU31
) {
454
14
      if (RegAdded.insert(*AI).second) {
455
14
        LRegs.push_back(*AI);
456
14
        Added = true;
457
14
      }
458
14
    }
459
285
  }
460
65
  return Added;
461
65
}
462
463
/// DelayForLiveRegsBottomUp - Returns true if it is necessary to delay
464
/// scheduling of the given node to satisfy live physical register dependencies.
465
/// If the specific node is the last one that's available to schedule, do
466
/// whatever is necessary (i.e. backtracking or cloning) to make it possible.
467
bool ScheduleDAGFast::DelayForLiveRegsBottomUp(SUnit *SU,
468
201
                                              SmallVectorImpl<unsigned> &LRegs){
469
201
  if (NumLiveRegs == 0)
470
162
    return false;
471
39
472
39
  SmallSet<unsigned, 4> RegAdded;
473
39
  // If this node would clobber any "live" register, then it's not ready.
474
65
  for (SDep &Pred : SU->Preds) {
475
65
    if (Pred.isAssignedRegDep()) {
476
0
      CheckForLiveRegDef(Pred.getSUnit(), Pred.getReg(), LiveRegDefs,
477
0
                         RegAdded, LRegs, TRI);
478
0
    }
479
65
  }
480
39
481
127
  for (SDNode *Node = SU->getNode(); Node; 
Node = Node->getGluedNode()88
) {
482
88
    if (Node->getOpcode() == ISD::INLINEASM ||
483
88
        
Node->getOpcode() == ISD::INLINEASM_BR86
) {
484
2
      // Inline asm can clobber physical defs.
485
2
      unsigned NumOps = Node->getNumOperands();
486
2
      if (Node->getOperand(NumOps-1).getValueType() == MVT::Glue)
487
2
        --NumOps;  // Ignore the glue operand.
488
2
489
8
      for (unsigned i = InlineAsm::Op_FirstOperand; i != NumOps;) {
490
6
        unsigned Flags =
491
6
          cast<ConstantSDNode>(Node->getOperand(i))->getZExtValue();
492
6
        unsigned NumVals = InlineAsm::getNumOperandRegisters(Flags);
493
6
494
6
        ++i; // Skip the ID value.
495
6
        if (InlineAsm::isRegDefKind(Flags) ||
496
6
            
InlineAsm::isRegDefEarlyClobberKind(Flags)4
||
497
6
            
InlineAsm::isClobberKind(Flags)4
) {
498
4
          // Check for def of register or earlyclobber register.
499
8
          for (; NumVals; 
--NumVals, ++i4
) {
500
4
            unsigned Reg = cast<RegisterSDNode>(Node->getOperand(i))->getReg();
501
4
            if (TargetRegisterInfo::isPhysicalRegister(Reg))
502
2
              CheckForLiveRegDef(SU, Reg, LiveRegDefs, RegAdded, LRegs, TRI);
503
4
          }
504
4
        } else
505
2
          i += NumVals;
506
6
      }
507
2
      continue;
508
2
    }
509
86
    if (!Node->isMachineOpcode())
510
48
      continue;
511
38
    const MCInstrDesc &MCID = TII->get(Node->getMachineOpcode());
512
38
    if (!MCID.ImplicitDefs)
513
9
      continue;
514
92
    
for (const MCPhysReg *Reg = MCID.getImplicitDefs(); 29
*Reg;
++Reg63
) {
515
63
      CheckForLiveRegDef(SU, *Reg, LiveRegDefs, RegAdded, LRegs, TRI);
516
63
    }
517
29
  }
518
39
  return !LRegs.empty();
519
39
}
520
521
522
/// ListScheduleBottomUp - The main loop of list scheduling for bottom-up
523
/// schedulers.
524
34
void ScheduleDAGFast::ListScheduleBottomUp() {
525
34
  unsigned CurCycle = 0;
526
34
527
34
  // Release any predecessors of the special Exit node.
528
34
  ReleasePredecessors(&ExitSU, CurCycle);
529
34
530
34
  // Add root to Available queue.
531
34
  if (!SUnits.empty()) {
532
30
    SUnit *RootSU = &SUnits[DAG->getRoot().getNode()->getNodeId()];
533
30
    assert(RootSU->Succs.empty() && "Graph root shouldn't have successors!");
534
30
    RootSU->isAvailable = true;
535
30
    AvailableQueue.push(RootSU);
536
30
  }
537
34
538
34
  // While Available queue is not empty, grab the node with the highest
539
34
  // priority. If it is not ready put it back.  Schedule the node.
540
34
  SmallVector<SUnit*, 4> NotReady;
541
34
  DenseMap<SUnit*, SmallVector<unsigned, 4> > LRegsMap;
542
34
  Sequence.reserve(SUnits.size());
543
234
  while (!AvailableQueue.empty()) {
544
200
    bool Delayed = false;
545
200
    LRegsMap.clear();
546
200
    SUnit *CurSU = AvailableQueue.pop();
547
214
    while (CurSU) {
548
201
      SmallVector<unsigned, 4> LRegs;
549
201
      if (!DelayForLiveRegsBottomUp(CurSU, LRegs))
550
187
        break;
551
14
      Delayed = true;
552
14
      LRegsMap.insert(std::make_pair(CurSU, LRegs));
553
14
554
14
      CurSU->isPending = true;  // This SU is not in AvailableQueue right now.
555
14
      NotReady.push_back(CurSU);
556
14
      CurSU = AvailableQueue.pop();
557
14
    }
558
200
559
200
    // All candidates are delayed due to live physical reg dependencies.
560
200
    // Try code duplication or inserting cross class copies
561
200
    // to resolve it.
562
200
    if (Delayed && 
!CurSU14
) {
563
13
      if (!CurSU) {
564
13
        // Try duplicating the nodes that produces these
565
13
        // "expensive to copy" values to break the dependency. In case even
566
13
        // that doesn't work, insert cross class copies.
567
13
        SUnit *TrySU = NotReady[0];
568
13
        SmallVectorImpl<unsigned> &LRegs = LRegsMap[TrySU];
569
13
        assert(LRegs.size() == 1 && "Can't handle this yet!");
570
13
        unsigned Reg = LRegs[0];
571
13
        SUnit *LRDef = LiveRegDefs[Reg];
572
13
        MVT VT = getPhysicalRegisterVT(LRDef->getNode(), Reg, TII);
573
13
        const TargetRegisterClass *RC =
574
13
          TRI->getMinimalPhysRegClass(Reg, VT);
575
13
        const TargetRegisterClass *DestRC = TRI->getCrossCopyRegClass(RC);
576
13
577
13
        // If cross copy register class is the same as RC, then it must be
578
13
        // possible copy the value directly. Do not try duplicate the def.
579
13
        // If cross copy register class is not the same as RC, then it's
580
13
        // possible to copy the value but it require cross register class copies
581
13
        // and it is expensive.
582
13
        // If cross copy register class is null, then it's not possible to copy
583
13
        // the value at all.
584
13
        SUnit *NewDef = nullptr;
585
13
        if (DestRC != RC) {
586
13
          NewDef = CopyAndMoveSuccessors(LRDef);
587
13
          if (!DestRC && 
!NewDef0
)
588
0
            report_fatal_error("Can't handle live physical "
589
0
                               "register dependency!");
590
13
        }
591
13
        if (!NewDef) {
592
12
          // Issue copies, these can be expensive cross register class copies.
593
12
          SmallVector<SUnit*, 2> Copies;
594
12
          InsertCopiesAndMoveSuccs(LRDef, Reg, DestRC, RC, Copies);
595
12
          LLVM_DEBUG(dbgs() << "Adding an edge from SU # " << TrySU->NodeNum
596
12
                            << " to SU #" << Copies.front()->NodeNum << "\n");
597
12
          AddPred(TrySU, SDep(Copies.front(), SDep::Artificial));
598
12
          NewDef = Copies.back();
599
12
        }
600
13
601
13
        LLVM_DEBUG(dbgs() << "Adding an edge from SU # " << NewDef->NodeNum
602
13
                          << " to SU #" << TrySU->NodeNum << "\n");
603
13
        LiveRegDefs[Reg] = NewDef;
604
13
        AddPred(NewDef, SDep(TrySU, SDep::Artificial));
605
13
        TrySU->isAvailable = false;
606
13
        CurSU = NewDef;
607
13
      }
608
13
609
13
      if (!CurSU) {
610
0
        llvm_unreachable("Unable to resolve live physical register dependencies!");
611
0
      }
612
200
    }
613
200
614
200
    // Add the nodes that aren't ready back onto the available list.
615
214
    
for (unsigned i = 0, e = NotReady.size(); 200
i != e;
++i14
) {
616
14
      NotReady[i]->isPending = false;
617
14
      // May no longer be available due to backtracking.
618
14
      if (NotReady[i]->isAvailable)
619
1
        AvailableQueue.push(NotReady[i]);
620
14
    }
621
200
    NotReady.clear();
622
200
623
200
    if (CurSU)
624
200
      ScheduleNodeBottomUp(CurSU, CurCycle);
625
200
    ++CurCycle;
626
200
  }
627
34
628
34
  // Reverse the order since it is bottom up.
629
34
  std::reverse(Sequence.begin(), Sequence.end());
630
34
631
#ifndef NDEBUG
632
  VerifyScheduledSequence(/*isBottomUp=*/true);
633
#endif
634
}
635
636
637
namespace {
638
//===----------------------------------------------------------------------===//
639
// ScheduleDAGLinearize - No scheduling scheduler, it simply linearize the
640
// DAG in topological order.
641
// IMPORTANT: this may not work for targets with phyreg dependency.
642
//
643
class ScheduleDAGLinearize : public ScheduleDAGSDNodes {
644
public:
645
48
  ScheduleDAGLinearize(MachineFunction &mf) : ScheduleDAGSDNodes(mf) {}
646
647
  void Schedule() override;
648
649
  MachineBasicBlock *
650
    EmitSchedule(MachineBasicBlock::iterator &InsertPos) override;
651
652
private:
653
  std::vector<SDNode*> Sequence;
654
  DenseMap<SDNode*, SDNode*> GluedMap;  // Cache glue to its user
655
656
  void ScheduleNode(SDNode *N);
657
};
658
} // end anonymous namespace
659
660
1.02k
void ScheduleDAGLinearize::ScheduleNode(SDNode *N) {
661
1.02k
  if (N->getNodeId() != 0)
662
1.02k
    
llvm_unreachable0
(nullptr);
663
1.02k
664
1.02k
  if (!N->isMachineOpcode() &&
665
1.02k
      
(683
N->getOpcode() == ISD::EntryToken683
||
isPassiveNode(N)635
))
666
450
    // These nodes do not need to be translated into MIs.
667
450
    return;
668
575
669
575
  LLVM_DEBUG(dbgs() << "\n*** Scheduling: ");
670
575
  LLVM_DEBUG(N->dump(DAG));
671
575
  Sequence.push_back(N);
672
575
673
575
  unsigned NumOps = N->getNumOperands();
674
575
  if (unsigned NumLeft = NumOps) {
675
563
    SDNode *GluedOpN = nullptr;
676
1.66k
    do {
677
1.66k
      const SDValue &Op = N->getOperand(NumLeft-1);
678
1.66k
      SDNode *OpN = Op.getNode();
679
1.66k
680
1.66k
      if (NumLeft == NumOps && 
Op.getValueType() == MVT::Glue563
) {
681
84
        // Schedule glue operand right above N.
682
84
        GluedOpN = OpN;
683
84
        assert(OpN->getNodeId() != 0 && "Glue operand not ready?");
684
84
        OpN->setNodeId(0);
685
84
        ScheduleNode(OpN);
686
84
        continue;
687
84
      }
688
1.58k
689
1.58k
      if (OpN == GluedOpN)
690
43
        // Glue operand is already scheduled.
691
43
        continue;
692
1.53k
693
1.53k
      DenseMap<SDNode*, SDNode*>::iterator DI = GluedMap.find(OpN);
694
1.53k
      if (DI != GluedMap.end() && 
DI->second != N5
)
695
5
        // Users of glues are counted against the glued users.
696
5
        OpN = DI->second;
697
1.53k
698
1.53k
      unsigned Degree = OpN->getNodeId();
699
1.53k
      assert(Degree > 0 && "Predecessor over-released!");
700
1.53k
      OpN->setNodeId(--Degree);
701
1.53k
      if (Degree == 0)
702
893
        ScheduleNode(OpN);
703
1.66k
    } while (--NumLeft);
704
563
  }
705
575
}
706
707
/// findGluedUser - Find the representative use of a glue value by walking
708
/// the use chain.
709
84
static SDNode *findGluedUser(SDNode *N) {
710
178
  while (SDNode *Glued = N->getGluedUser())
711
94
    N = Glued;
712
84
  return N;
713
84
}
714
715
48
void ScheduleDAGLinearize::Schedule() {
716
48
  LLVM_DEBUG(dbgs() << "********** DAG Linearization **********\n");
717
48
718
48
  SmallVector<SDNode*, 8> Glues;
719
48
  unsigned DAGSize = 0;
720
1.05k
  for (SDNode &Node : DAG->allnodes()) {
721
1.05k
    SDNode *N = &Node;
722
1.05k
723
1.05k
    // Use node id to record degree.
724
1.05k
    unsigned Degree = N->use_size();
725
1.05k
    N->setNodeId(Degree);
726
1.05k
    unsigned NumVals = N->getNumValues();
727
1.05k
    if (NumVals && N->getValueType(NumVals-1) == MVT::Glue &&
728
1.05k
        
N->hasAnyUseOfValue(NumVals-1)86
) {
729
84
      SDNode *User = findGluedUser(N);
730
84
      if (User) {
731
84
        Glues.push_back(N);
732
84
        GluedMap.insert(std::make_pair(N, User));
733
84
      }
734
84
    }
735
1.05k
736
1.05k
    if (N->isMachineOpcode() ||
737
1.05k
        
(717
N->getOpcode() != ISD::EntryToken717
&&
!isPassiveNode(N)669
))
738
575
      ++DAGSize;
739
1.05k
  }
740
48
741
132
  for (unsigned i = 0, e = Glues.size(); i != e; 
++i84
) {
742
84
    SDNode *Glue = Glues[i];
743
84
    SDNode *GUser = GluedMap[Glue];
744
84
    unsigned Degree = Glue->getNodeId();
745
84
    unsigned UDegree = GUser->getNodeId();
746
84
747
84
    // Glue user must be scheduled together with the glue operand. So other
748
84
    // users of the glue operand must be treated as its users.
749
84
    SDNode *ImmGUser = Glue->getGluedUser();
750
84
    for (const SDNode *U : Glue->uses())
751
132
      if (U == ImmGUser)
752
127
        --Degree;
753
84
    GUser->setNodeId(UDegree + Degree);
754
84
    Glue->setNodeId(1);
755
84
  }
756
48
757
48
  Sequence.reserve(DAGSize);
758
48
  ScheduleNode(DAG->getRoot().getNode());
759
48
}
760
761
MachineBasicBlock*
762
48
ScheduleDAGLinearize::EmitSchedule(MachineBasicBlock::iterator &InsertPos) {
763
48
  InstrEmitter Emitter(BB, InsertPos);
764
48
  DenseMap<SDValue, unsigned> VRBaseMap;
765
48
766
48
  LLVM_DEBUG({ dbgs() << "\n*** Final schedule ***\n"; });
767
48
768
48
  unsigned NumNodes = Sequence.size();
769
48
  MachineBasicBlock *BB = Emitter.getBlock();
770
623
  for (unsigned i = 0; i != NumNodes; 
++i575
) {
771
575
    SDNode *N = Sequence[NumNodes-i-1];
772
575
    LLVM_DEBUG(N->dump(DAG));
773
575
    Emitter.EmitNode(N, false, false, VRBaseMap);
774
575
775
575
    // Emit any debug values associated with the node.
776
575
    if (N->getHasDebugValue()) {
777
1
      MachineBasicBlock::iterator InsertPos = Emitter.getInsertPos();
778
2
      for (auto DV : DAG->GetDbgValues(N)) {
779
2
        if (!DV->isEmitted())
780
2
          if (auto *DbgMI = Emitter.EmitDbgValue(DV, VRBaseMap))
781
2
            BB->insert(InsertPos, DbgMI);
782
2
      }
783
1
    }
784
575
  }
785
48
786
48
  LLVM_DEBUG(dbgs() << '\n');
787
48
788
48
  InsertPos = Emitter.getInsertPos();
789
48
  return Emitter.getBlock();
790
48
}
791
792
//===----------------------------------------------------------------------===//
793
//                         Public Constructor Functions
794
//===----------------------------------------------------------------------===//
795
796
llvm::ScheduleDAGSDNodes *
797
34
llvm::createFastDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level) {
798
34
  return new ScheduleDAGFast(*IS->MF);
799
34
}
800
801
llvm::ScheduleDAGSDNodes *
802
48
llvm::createDAGLinearizer(SelectionDAGISel *IS, CodeGenOpt::Level) {
803
48
  return new ScheduleDAGLinearize(*IS->MF);
804
48
}