Coverage Report

Created: 2018-09-17 19:50

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/CodeGen/ScheduleDAG.h
Line
Count
Source (jump to first uncovered line)
1
//===- llvm/CodeGen/ScheduleDAG.h - Common Base Class -----------*- 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
/// \file Implements the ScheduleDAG class, which is used as the common base
11
/// class for instruction schedulers. This encapsulates the scheduling DAG,
12
/// which is shared between SelectionDAG and MachineInstr scheduling.
13
//
14
//===----------------------------------------------------------------------===//
15
16
#ifndef LLVM_CODEGEN_SCHEDULEDAG_H
17
#define LLVM_CODEGEN_SCHEDULEDAG_H
18
19
#include "llvm/ADT/BitVector.h"
20
#include "llvm/ADT/GraphTraits.h"
21
#include "llvm/ADT/PointerIntPair.h"
22
#include "llvm/ADT/SmallVector.h"
23
#include "llvm/ADT/iterator.h"
24
#include "llvm/CodeGen/MachineInstr.h"
25
#include "llvm/CodeGen/TargetLowering.h"
26
#include "llvm/Support/ErrorHandling.h"
27
#include <cassert>
28
#include <cstddef>
29
#include <iterator>
30
#include <string>
31
#include <vector>
32
33
namespace llvm {
34
35
template<class Graph> class GraphWriter;
36
class MachineFunction;
37
class MachineRegisterInfo;
38
class MCInstrDesc;
39
struct MCSchedClassDesc;
40
class ScheduleDAG;
41
class SDNode;
42
class SUnit;
43
class TargetInstrInfo;
44
class TargetMachine;
45
class TargetRegisterClass;
46
class TargetRegisterInfo;
47
48
  /// Scheduling dependency. This represents one direction of an edge in the
49
  /// scheduling DAG.
50
  class SDep {
51
  public:
52
    /// These are the different kinds of scheduling dependencies.
53
    enum Kind {
54
      Data,        ///< Regular data dependence (aka true-dependence).
55
      Anti,        ///< A register anti-dependence (aka WAR).
56
      Output,      ///< A register output-dependence (aka WAW).
57
      Order        ///< Any other ordering dependency.
58
    };
59
60
    // Strong dependencies must be respected by the scheduler. Artificial
61
    // dependencies may be removed only if they are redundant with another
62
    // strong dependence.
63
    //
64
    // Weak dependencies may be violated by the scheduling strategy, but only if
65
    // the strategy can prove it is correct to do so.
66
    //
67
    // Strong OrderKinds must occur before "Weak".
68
    // Weak OrderKinds must occur after "Weak".
69
    enum OrderKind {
70
      Barrier,      ///< An unknown scheduling barrier.
71
      MayAliasMem,  ///< Nonvolatile load/Store instructions that may alias.
72
      MustAliasMem, ///< Nonvolatile load/Store instructions that must alias.
73
      Artificial,   ///< Arbitrary strong DAG edge (no real dependence).
74
      Weak,         ///< Arbitrary weak DAG edge.
75
      Cluster       ///< Weak DAG edge linking a chain of clustered instrs.
76
    };
77
78
  private:
79
    /// A pointer to the depending/depended-on SUnit, and an enum
80
    /// indicating the kind of the dependency.
81
    PointerIntPair<SUnit *, 2, Kind> Dep;
82
83
    /// A union discriminated by the dependence kind.
84
    union {
85
      /// For Data, Anti, and Output dependencies, the associated register. For
86
      /// Data dependencies that don't currently have a register/ assigned, this
87
      /// is set to zero.
88
      unsigned Reg;
89
90
      /// Additional information about Order dependencies.
91
      unsigned OrdKind; // enum OrderKind
92
    } Contents;
93
94
    /// The time associated with this edge. Often this is just the value of the
95
    /// Latency field of the predecessor, however advanced models may provide
96
    /// additional information about specific edges.
97
    unsigned Latency;
98
99
  public:
100
    /// Constructs a null SDep. This is only for use by container classes which
101
    /// require default constructors. SUnits may not/ have null SDep edges.
102
5.50M
    SDep() : Dep(nullptr, Data) {}
103
104
    /// Constructs an SDep with the specified values.
105
    SDep(SUnit *S, Kind kind, unsigned Reg)
106
21.3M
      : Dep(S, kind), Contents() {
107
21.3M
      switch (kind) {
108
21.3M
      default:
109
0
        llvm_unreachable("Reg given for non-register dependence!");
110
21.3M
      case Anti:
111
2.03M
      case Output:
112
2.03M
        assert(Reg != 0 &&
113
2.03M
               "SDep::Anti and SDep::Output must use a non-zero Reg!");
114
2.03M
        Contents.Reg = Reg;
115
2.03M
        Latency = 0;
116
2.03M
        break;
117
19.3M
      case Data:
118
19.3M
        Contents.Reg = Reg;
119
19.3M
        Latency = 1;
120
19.3M
        break;
121
21.3M
      }
122
21.3M
    }
123
124
    SDep(SUnit *S, OrderKind kind)
125
19.5M
      : Dep(S, Order), Contents(), Latency(0) {
126
19.5M
      Contents.OrdKind = kind;
127
19.5M
    }
128
129
    /// Returns true if the specified SDep is equivalent except for latency.
130
    bool overlaps(const SDep &Other) const;
131
132
18.8k
    bool operator==(const SDep &Other) const {
133
18.8k
      return overlaps(Other) && 
Latency == Other.Latency11.2k
;
134
18.8k
    }
135
136
0
    bool operator!=(const SDep &Other) const {
137
0
      return !operator==(Other);
138
0
    }
139
140
    /// Returns the latency value for this edge, which roughly means the
141
    /// minimum number of cycles that must elapse between the predecessor and
142
    /// the successor, given that they have this edge between them.
143
225M
    unsigned getLatency() const {
144
225M
      return Latency;
145
225M
    }
146
147
    /// Sets the latency for this edge.
148
40.7M
    void setLatency(unsigned Lat) {
149
40.7M
      Latency = Lat;
150
40.7M
    }
151
152
    //// Returns the SUnit to which this edge points.
153
    SUnit *getSUnit() const;
154
155
    //// Assigns the SUnit to which this edge points.
156
    void setSUnit(SUnit *SU);
157
158
    /// Returns an enum value representing the kind of the dependence.
159
    Kind getKind() const;
160
161
    /// Shorthand for getKind() != SDep::Data.
162
91.8M
    bool isCtrl() const {
163
91.8M
      return getKind() != Data;
164
91.8M
    }
165
166
    /// Tests if this is an Order dependence between two memory accesses
167
    /// where both sides of the dependence access memory in non-volatile and
168
    /// fully modeled ways.
169
0
    bool isNormalMemory() const {
170
0
      return getKind() == Order && (Contents.OrdKind == MayAliasMem
171
0
                                    || Contents.OrdKind == MustAliasMem);
172
0
    }
173
174
    /// Tests if this is an Order dependence that is marked as a barrier.
175
0
    bool isBarrier() const {
176
0
      return getKind() == Order && Contents.OrdKind == Barrier;
177
0
    }
178
179
    /// Tests if this is could be any kind of memory dependence.
180
0
    bool isNormalMemoryOrBarrier() const {
181
0
      return (isNormalMemory() || isBarrier());
182
0
    }
183
184
    /// Tests if this is an Order dependence that is marked as
185
    /// "must alias", meaning that the SUnits at either end of the edge have a
186
    /// memory dependence on a known memory location.
187
0
    bool isMustAlias() const {
188
0
      return getKind() == Order && Contents.OrdKind == MustAliasMem;
189
0
    }
190
191
    /// Tests if this a weak dependence. Weak dependencies are considered DAG
192
    /// edges for height computation and other heuristics, but do not force
193
    /// ordering. Breaking a weak edge may require the scheduler to compensate,
194
    /// for example by inserting a copy.
195
100M
    bool isWeak() const {
196
100M
      return getKind() == Order && 
Contents.OrdKind >= Weak50.3M
;
197
100M
    }
198
199
    /// Tests if this is an Order dependence that is marked as
200
    /// "artificial", meaning it isn't necessary for correctness.
201
1.51M
    bool isArtificial() const {
202
1.51M
      return getKind() == Order && 
Contents.OrdKind == Artificial1.42M
;
203
1.51M
    }
204
205
    /// Tests if this is an Order dependence that is marked as "cluster",
206
    /// meaning it is artificial and wants to be adjacent.
207
1.92M
    bool isCluster() const {
208
1.92M
      return getKind() == Order && 
Contents.OrdKind == Cluster1.86M
;
209
1.92M
    }
210
211
    /// Tests if this is a Data dependence that is associated with a register.
212
41.2M
    bool isAssignedRegDep() const {
213
41.2M
      return getKind() == Data && 
Contents.Reg != 025.7M
;
214
41.2M
    }
215
216
    /// Returns the register associated with this edge. This is only valid on
217
    /// Data, Anti, and Output edges. On Data edges, this value may be zero,
218
    /// meaning there is no associated register.
219
4.89M
    unsigned getReg() const {
220
4.89M
      assert((getKind() == Data || getKind() == Anti || getKind() == Output) &&
221
4.89M
             "getReg called on non-register dependence edge!");
222
4.89M
      return Contents.Reg;
223
4.89M
    }
224
225
    /// Assigns the associated register for this edge. This is only valid on
226
    /// Data, Anti, and Output edges. On Anti and Output edges, this value must
227
    /// not be zero. On Data edges, the value may be zero, which would mean that
228
    /// no specific register is associated with this edge.
229
0
    void setReg(unsigned Reg) {
230
0
      assert((getKind() == Data || getKind() == Anti || getKind() == Output) &&
231
0
             "setReg called on non-register dependence edge!");
232
0
      assert((getKind() != Anti || Reg != 0) &&
233
0
             "SDep::Anti edge cannot use the zero register!");
234
0
      assert((getKind() != Output || Reg != 0) &&
235
0
             "SDep::Output edge cannot use the zero register!");
236
0
      Contents.Reg = Reg;
237
0
    }
238
239
    raw_ostream &print(raw_ostream &O,
240
                       const TargetRegisterInfo *TRI = nullptr) const;
241
  };
242
243
  template <>
244
  struct isPodLike<SDep> { static const bool value = true; };
245
246
  /// Scheduling unit. This is a node in the scheduling DAG.
247
  class SUnit {
248
  private:
249
    enum : unsigned { BoundaryID = ~0u };
250
251
    SDNode *Node = nullptr;        ///< Representative node.
252
    MachineInstr *Instr = nullptr; ///< Alternatively, a MachineInstr.
253
254
  public:
255
    SUnit *OrigNode = nullptr; ///< If not this, the node from which this node
256
                               /// was cloned. (SD scheduling only)
257
258
    const MCSchedClassDesc *SchedClass =
259
        nullptr; ///< nullptr or resolved SchedClass.
260
261
    SmallVector<SDep, 4> Preds;  ///< All sunit predecessors.
262
    SmallVector<SDep, 4> Succs;  ///< All sunit successors.
263
264
    typedef SmallVectorImpl<SDep>::iterator pred_iterator;
265
    typedef SmallVectorImpl<SDep>::iterator succ_iterator;
266
    typedef SmallVectorImpl<SDep>::const_iterator const_pred_iterator;
267
    typedef SmallVectorImpl<SDep>::const_iterator const_succ_iterator;
268
269
    unsigned NodeNum = BoundaryID;     ///< Entry # of node in the node vector.
270
    unsigned NodeQueueId = 0;          ///< Queue id of node.
271
    unsigned NumPreds = 0;             ///< # of SDep::Data preds.
272
    unsigned NumSuccs = 0;             ///< # of SDep::Data sucss.
273
    unsigned NumPredsLeft = 0;         ///< # of preds not scheduled.
274
    unsigned NumSuccsLeft = 0;         ///< # of succs not scheduled.
275
    unsigned WeakPredsLeft = 0;        ///< # of weak preds not scheduled.
276
    unsigned WeakSuccsLeft = 0;        ///< # of weak succs not scheduled.
277
    unsigned short NumRegDefsLeft = 0; ///< # of reg defs with no scheduled use.
278
    unsigned short Latency = 0;        ///< Node latency.
279
    bool isVRegCycle      : 1;         ///< May use and def the same vreg.
280
    bool isCall           : 1;         ///< Is a function call.
281
    bool isCallOp         : 1;         ///< Is a function call operand.
282
    bool isTwoAddress     : 1;         ///< Is a two-address instruction.
283
    bool isCommutable     : 1;         ///< Is a commutable instruction.
284
    bool hasPhysRegUses   : 1;         ///< Has physreg uses.
285
    bool hasPhysRegDefs   : 1;         ///< Has physreg defs that are being used.
286
    bool hasPhysRegClobbers : 1;       ///< Has any physreg defs, used or not.
287
    bool isPending        : 1;         ///< True once pending.
288
    bool isAvailable      : 1;         ///< True once available.
289
    bool isScheduled      : 1;         ///< True once scheduled.
290
    bool isScheduleHigh   : 1;         ///< True if preferable to schedule high.
291
    bool isScheduleLow    : 1;         ///< True if preferable to schedule low.
292
    bool isCloned         : 1;         ///< True if this node has been cloned.
293
    bool isUnbuffered     : 1;         ///< Uses an unbuffered resource.
294
    bool hasReservedResource : 1;      ///< Uses a reserved resource.
295
    Sched::Preference SchedulingPref = Sched::None; ///< Scheduling preference.
296
297
  private:
298
    bool isDepthCurrent   : 1;         ///< True if Depth is current.
299
    bool isHeightCurrent  : 1;         ///< True if Height is current.
300
    unsigned Depth = 0;                ///< Node depth.
301
    unsigned Height = 0;               ///< Node height.
302
303
  public:
304
    unsigned TopReadyCycle = 0; ///< Cycle relative to start when node is ready.
305
    unsigned BotReadyCycle = 0; ///< Cycle relative to end when node is ready.
306
307
    const TargetRegisterClass *CopyDstRC =
308
        nullptr; ///< Is a special copy node if != nullptr.
309
    const TargetRegisterClass *CopySrcRC = nullptr;
310
311
    /// Constructs an SUnit for pre-regalloc scheduling to represent an
312
    /// SDNode and any nodes flagged to it.
313
    SUnit(SDNode *node, unsigned nodenum)
314
      : Node(node), NodeNum(nodenum), isVRegCycle(false), isCall(false),
315
        isCallOp(false), isTwoAddress(false), isCommutable(false),
316
        hasPhysRegUses(false), hasPhysRegDefs(false), hasPhysRegClobbers(false),
317
        isPending(false), isAvailable(false), isScheduled(false),
318
        isScheduleHigh(false), isScheduleLow(false), isCloned(false),
319
        isUnbuffered(false), hasReservedResource(false), isDepthCurrent(false),
320
16.3M
        isHeightCurrent(false) {}
321
322
    /// Constructs an SUnit for post-regalloc scheduling to represent a
323
    /// MachineInstr.
324
    SUnit(MachineInstr *instr, unsigned nodenum)
325
      : Instr(instr), NodeNum(nodenum), isVRegCycle(false), isCall(false),
326
        isCallOp(false), isTwoAddress(false), isCommutable(false),
327
        hasPhysRegUses(false), hasPhysRegDefs(false), hasPhysRegClobbers(false),
328
        isPending(false), isAvailable(false), isScheduled(false),
329
        isScheduleHigh(false), isScheduleLow(false), isCloned(false),
330
        isUnbuffered(false), hasReservedResource(false), isDepthCurrent(false),
331
12.6M
        isHeightCurrent(false) {}
332
333
    /// Constructs a placeholder SUnit.
334
    SUnit()
335
      : isVRegCycle(false), isCall(false), isCallOp(false), isTwoAddress(false),
336
        isCommutable(false), hasPhysRegUses(false), hasPhysRegDefs(false),
337
        hasPhysRegClobbers(false), isPending(false), isAvailable(false),
338
        isScheduled(false), isScheduleHigh(false), isScheduleLow(false),
339
        isCloned(false), isUnbuffered(false), hasReservedResource(false),
340
14.1M
        isDepthCurrent(false), isHeightCurrent(false) {}
341
342
    /// Boundary nodes are placeholders for the boundary of the
343
    /// scheduling region.
344
    ///
345
    /// BoundaryNodes can have DAG edges, including Data edges, but they do not
346
    /// correspond to schedulable entities (e.g. instructions) and do not have a
347
    /// valid ID. Consequently, always check for boundary nodes before accessing
348
    /// an associative data structure keyed on node ID.
349
1.05M
    bool isBoundaryNode() const { return NodeNum == BoundaryID; }
350
351
    /// Assigns the representative SDNode for this SUnit. This may be used
352
    /// during pre-regalloc scheduling.
353
16.3M
    void setNode(SDNode *N) {
354
16.3M
      assert(!Instr && "Setting SDNode of SUnit with MachineInstr!");
355
16.3M
      Node = N;
356
16.3M
    }
357
358
    /// Returns the representative SDNode for this SUnit. This may be used
359
    /// during pre-regalloc scheduling.
360
349M
    SDNode *getNode() const {
361
349M
      assert(!Instr && "Reading SDNode of SUnit with MachineInstr!");
362
349M
      return Node;
363
349M
    }
364
365
    /// Returns true if this SUnit refers to a machine instruction as
366
    /// opposed to an SDNode.
367
3.08M
    bool isInstr() const { return Instr; }
368
369
    /// Assigns the instruction for the SUnit. This may be used during
370
    /// post-regalloc scheduling.
371
3.01M
    void setInstr(MachineInstr *MI) {
372
3.01M
      assert(!Node && "Setting MachineInstr of SUnit with SDNode!");
373
3.01M
      Instr = MI;
374
3.01M
    }
375
376
    /// Returns the representative MachineInstr for this SUnit. This may be used
377
    /// during post-regalloc scheduling.
378
443M
    MachineInstr *getInstr() const {
379
443M
      assert(!Node && "Reading MachineInstr of SUnit with SDNode!");
380
443M
      return Instr;
381
443M
    }
382
383
    /// Adds the specified edge as a pred of the current node if not already.
384
    /// It also adds the current node as a successor of the specified node.
385
    bool addPred(const SDep &D, bool Required = true);
386
387
    /// Adds a barrier edge to SU by calling addPred(), with latency 0
388
    /// generally or latency 1 for a store followed by a load.
389
297k
    bool addPredBarrier(SUnit *SU) {
390
297k
      SDep Dep(SU, SDep::Barrier);
391
297k
      unsigned TrueMemOrderLatency =
392
297k
        ((SU->getInstr()->mayStore() && 
this->getInstr()->mayLoad()125k
) ?
158.7k
:
0238k
);
393
297k
      Dep.setLatency(TrueMemOrderLatency);
394
297k
      return addPred(Dep);
395
297k
    }
396
397
    /// Removes the specified edge as a pred of the current node if it exists.
398
    /// It also removes the current node as a successor of the specified node.
399
    void removePred(const SDep &D);
400
401
    /// Returns the depth of this node, which is the length of the maximum path
402
    /// up to any node which has no predecessors.
403
72.2M
    unsigned getDepth() const {
404
72.2M
      if (!isDepthCurrent)
405
8.62M
        const_cast<SUnit *>(this)->ComputeDepth();
406
72.2M
      return Depth;
407
72.2M
    }
408
409
    /// Returns the height of this node, which is the length of the
410
    /// maximum path down to any node which has no successors.
411
130M
    unsigned getHeight() const {
412
130M
      if (!isHeightCurrent)
413
25.8M
        const_cast<SUnit *>(this)->ComputeHeight();
414
130M
      return Height;
415
130M
    }
416
417
    /// If NewDepth is greater than this node's depth value, sets it to
418
    /// be the new depth value. This also recursively marks successor nodes
419
    /// dirty.
420
    void setDepthToAtLeast(unsigned NewDepth);
421
422
    /// If NewDepth is greater than this node's depth value, set it to be
423
    /// the new height value. This also recursively marks predecessor nodes
424
    /// dirty.
425
    void setHeightToAtLeast(unsigned NewHeight);
426
427
    /// Sets a flag in this node to indicate that its stored Depth value
428
    /// will require recomputation the next time getDepth() is called.
429
    void setDepthDirty();
430
431
    /// Sets a flag in this node to indicate that its stored Height value
432
    /// will require recomputation the next time getHeight() is called.
433
    void setHeightDirty();
434
435
    /// Tests if node N is a predecessor of this node.
436
7.89k
    bool isPred(const SUnit *N) const {
437
7.89k
      for (const SDep &Pred : Preds)
438
17.0k
        if (Pred.getSUnit() == N)
439
4.58k
          return true;
440
7.89k
      
return false3.30k
;
441
7.89k
    }
442
443
    /// Tests if node N is a successor of this node.
444
155k
    bool isSucc(const SUnit *N) const {
445
155k
      for (const SDep &Succ : Succs)
446
365k
        if (Succ.getSUnit() == N)
447
23.6k
          return true;
448
155k
      
return false132k
;
449
155k
    }
450
451
11.7M
    bool isTopReady() const {
452
11.7M
      return NumPredsLeft == 0;
453
11.7M
    }
454
11.7M
    bool isBottomReady() const {
455
11.7M
      return NumSuccsLeft == 0;
456
11.7M
    }
457
458
    /// Orders this node's predecessor edges such that the critical path
459
    /// edge occurs first.
460
    void biasCriticalPath();
461
462
    void dump(const ScheduleDAG *G) const;
463
    void dumpAll(const ScheduleDAG *G) const;
464
    raw_ostream &print(raw_ostream &O,
465
                       const SUnit *Entry = nullptr,
466
                       const SUnit *Exit = nullptr) const;
467
    raw_ostream &print(raw_ostream &O, const ScheduleDAG *G) const;
468
469
  private:
470
    void ComputeDepth();
471
    void ComputeHeight();
472
  };
473
474
  /// Returns true if the specified SDep is equivalent except for latency.
475
238M
  inline bool SDep::overlaps(const SDep &Other) const {
476
238M
    if (Dep != Other.Dep)
477
236M
      return false;
478
2.17M
    switch (Dep.getInt()) {
479
2.17M
    case Data:
480
772k
    case Anti:
481
772k
    case Output:
482
772k
      return Contents.Reg == Other.Contents.Reg;
483
1.39M
    case Order:
484
1.39M
      return Contents.OrdKind == Other.Contents.OrdKind;
485
0
    }
486
0
    llvm_unreachable("Invalid dependency kind!");
487
0
  }
488
489
  //// Returns the SUnit to which this edge points.
490
442M
  inline SUnit *SDep::getSUnit() const { return Dep.getPointer(); }
491
492
  //// Assigns the SUnit to which this edge points.
493
39.1M
  inline void SDep::setSUnit(SUnit *SU) { Dep.setPointer(SU); }
494
495
  /// Returns an enum value representing the kind of the dependence.
496
284M
  inline SDep::Kind SDep::getKind() const { return Dep.getInt(); }
497
498
  //===--------------------------------------------------------------------===//
499
500
  /// This interface is used to plug different priorities computation
501
  /// algorithms into the list scheduler. It implements the interface of a
502
  /// standard priority queue, where nodes are inserted in arbitrary order and
503
  /// returned in priority order.  The computation of the priority and the
504
  /// representation of the queue are totally up to the implementation to
505
  /// decide.
506
  class SchedulingPriorityQueue {
507
    virtual void anchor();
508
509
    unsigned CurCycle = 0;
510
    bool HasReadyFilter;
511
512
  public:
513
1.82M
    SchedulingPriorityQueue(bool rf = false) :  HasReadyFilter(rf) {}
514
515
1.82M
    virtual ~SchedulingPriorityQueue() = default;
516
517
    virtual bool isBottomUp() const = 0;
518
519
    virtual void initNodes(std::vector<SUnit> &SUnits) = 0;
520
    virtual void addNode(const SUnit *SU) = 0;
521
    virtual void updateNode(const SUnit *SU) = 0;
522
    virtual void releaseState() = 0;
523
524
    virtual bool empty() const = 0;
525
526
14.6M
    bool hasReadyFilter() const { return HasReadyFilter; }
527
528
0
    virtual bool tracksRegPressure() const { return false; }
529
530
0
    virtual bool isReady(SUnit *) const {
531
0
      assert(!HasReadyFilter && "The ready filter must override isReady()");
532
0
      return true;
533
0
    }
534
535
    virtual void push(SUnit *U) = 0;
536
537
40.4k
    void push_all(const std::vector<SUnit *> &Nodes) {
538
40.4k
      for (std::vector<SUnit *>::const_iterator I = Nodes.begin(),
539
106k
           E = Nodes.end(); I != E; 
++I65.8k
)
540
65.8k
        push(*I);
541
40.4k
    }
542
543
    virtual SUnit *pop() = 0;
544
545
    virtual void remove(SUnit *SU) = 0;
546
547
0
    virtual void dump(ScheduleDAG *) const {}
548
549
    /// As each node is scheduled, this method is invoked.  This allows the
550
    /// priority function to adjust the priority of related unscheduled nodes,
551
    /// for example.
552
0
    virtual void scheduledNode(SUnit *) {}
553
554
0
    virtual void unscheduledNode(SUnit *) {}
555
556
16.1M
    void setCurCycle(unsigned Cycle) {
557
16.1M
      CurCycle = Cycle;
558
16.1M
    }
559
560
7.90M
    unsigned getCurCycle() const {
561
7.90M
      return CurCycle;
562
7.90M
    }
563
  };
564
565
  class ScheduleDAG {
566
  public:
567
    const TargetMachine &TM;            ///< Target processor
568
    const TargetInstrInfo *TII;         ///< Target instruction information
569
    const TargetRegisterInfo *TRI;      ///< Target processor register info
570
    MachineFunction &MF;                ///< Machine function
571
    MachineRegisterInfo &MRI;           ///< Virtual/real register map
572
    std::vector<SUnit> SUnits;          ///< The scheduling units.
573
    SUnit EntrySU;                      ///< Special node for the region entry.
574
    SUnit ExitSU;                       ///< Special node for the region exit.
575
576
#ifdef NDEBUG
577
    static const bool StressSched = false;
578
#else
579
    bool StressSched;
580
#endif
581
582
    explicit ScheduleDAG(MachineFunction &mf);
583
584
    virtual ~ScheduleDAG();
585
586
    /// Clears the DAG state (between regions).
587
    void clearDAG();
588
589
    /// Returns the MCInstrDesc of this SUnit.
590
    /// Returns NULL for SDNodes without a machine opcode.
591
2.65M
    const MCInstrDesc *getInstrDesc(const SUnit *SU) const {
592
2.65M
      if (SU->isInstr()) 
return &SU->getInstr()->getDesc()1.06M
;
593
1.58M
      return getNodeDesc(SU->getNode());
594
1.58M
    }
595
596
    /// Pops up a GraphViz/gv window with the ScheduleDAG rendered using 'dot'.
597
    virtual void viewGraph(const Twine &Name, const Twine &Title);
598
    virtual void viewGraph();
599
600
    virtual void dumpNode(const SUnit *SU) const = 0;
601
602
    /// Returns a label for an SUnit node in a visualization of the ScheduleDAG.
603
    virtual std::string getGraphNodeLabel(const SUnit *SU) const = 0;
604
605
    /// Returns a label for the region of code covered by the DAG.
606
    virtual std::string getDAGName() const = 0;
607
608
    /// Adds custom features for a visualization of the ScheduleDAG.
609
0
    virtual void addCustomGraphFeatures(GraphWriter<ScheduleDAG*> &) const {}
610
611
#ifndef NDEBUG
612
    /// Verifies that all SUnits were scheduled and that their state is
613
    /// consistent. Returns the number of scheduled SUnits.
614
    unsigned VerifyScheduledDAG(bool isBottomUp);
615
#endif
616
617
  private:
618
    /// Returns the MCInstrDesc of this SDNode or NULL.
619
    const MCInstrDesc *getNodeDesc(const SDNode *Node) const;
620
  };
621
622
  class SUnitIterator : public std::iterator<std::forward_iterator_tag,
623
                                             SUnit, ptrdiff_t> {
624
    SUnit *Node;
625
    unsigned Operand;
626
627
    SUnitIterator(SUnit *N, unsigned Op) : Node(N), Operand(Op) {}
628
629
  public:
630
    bool operator==(const SUnitIterator& x) const {
631
      return Operand == x.Operand;
632
    }
633
    bool operator!=(const SUnitIterator& x) const { return !operator==(x); }
634
635
    pointer operator*() const {
636
      return Node->Preds[Operand].getSUnit();
637
    }
638
    pointer operator->() const { return operator*(); }
639
640
    SUnitIterator& operator++() {                // Preincrement
641
      ++Operand;
642
      return *this;
643
    }
644
    SUnitIterator operator++(int) { // Postincrement
645
      SUnitIterator tmp = *this; ++*this; return tmp;
646
    }
647
648
    static SUnitIterator begin(SUnit *N) { return SUnitIterator(N, 0); }
649
    static SUnitIterator end  (SUnit *N) {
650
      return SUnitIterator(N, (unsigned)N->Preds.size());
651
    }
652
653
    unsigned getOperand() const { return Operand; }
654
    const SUnit *getNode() const { return Node; }
655
656
    /// Tests if this is not an SDep::Data dependence.
657
0
    bool isCtrlDep() const {
658
0
      return getSDep().isCtrl();
659
0
    }
660
0
    bool isArtificialDep() const {
661
0
      return getSDep().isArtificial();
662
0
    }
663
0
    const SDep &getSDep() const {
664
0
      return Node->Preds[Operand];
665
0
    }
666
  };
667
668
  template <> struct GraphTraits<SUnit*> {
669
    typedef SUnit *NodeRef;
670
    typedef SUnitIterator ChildIteratorType;
671
    static NodeRef getEntryNode(SUnit *N) { return N; }
672
    static ChildIteratorType child_begin(NodeRef N) {
673
      return SUnitIterator::begin(N);
674
    }
675
    static ChildIteratorType child_end(NodeRef N) {
676
      return SUnitIterator::end(N);
677
    }
678
  };
679
680
  template <> struct GraphTraits<ScheduleDAG*> : public GraphTraits<SUnit*> {
681
    typedef pointer_iterator<std::vector<SUnit>::iterator> nodes_iterator;
682
    static nodes_iterator nodes_begin(ScheduleDAG *G) {
683
      return nodes_iterator(G->SUnits.begin());
684
    }
685
    static nodes_iterator nodes_end(ScheduleDAG *G) {
686
      return nodes_iterator(G->SUnits.end());
687
    }
688
  };
689
690
  /// This class can compute a topological ordering for SUnits and provides
691
  /// methods for dynamically updating the ordering as new edges are added.
692
  ///
693
  /// This allows a very fast implementation of IsReachable, for example.
694
  class ScheduleDAGTopologicalSort {
695
    /// A reference to the ScheduleDAG's SUnits.
696
    std::vector<SUnit> &SUnits;
697
    SUnit *ExitSU;
698
699
    /// Maps topological index to the node number.
700
    std::vector<int> Index2Node;
701
    /// Maps the node number to its topological index.
702
    std::vector<int> Node2Index;
703
    /// a set of nodes visited during a DFS traversal.
704
    BitVector Visited;
705
706
    /// Makes a DFS traversal and mark all nodes affected by the edge insertion.
707
    /// These nodes will later get new topological indexes by means of the Shift
708
    /// method.
709
    void DFS(const SUnit *SU, int UpperBound, bool& HasLoop);
710
711
    /// Reassigns topological indexes for the nodes in the DAG to
712
    /// preserve the topological ordering.
713
    void Shift(BitVector& Visited, int LowerBound, int UpperBound);
714
715
    /// Assigns the topological index to the node n.
716
    void Allocate(int n, int index);
717
718
  public:
719
    ScheduleDAGTopologicalSort(std::vector<SUnit> &SUnits, SUnit *ExitSU);
720
721
    /// Creates the initial topological ordering from the DAG to be scheduled.
722
    void InitDAGTopologicalSorting();
723
724
    /// Returns an array of SUs that are both in the successor
725
    /// subtree of StartSU and in the predecessor subtree of TargetSU.
726
    /// StartSU and TargetSU are not in the array.
727
    /// Success is false if TargetSU is not in the successor subtree of
728
    /// StartSU, else it is true.
729
    std::vector<int> GetSubGraph(const SUnit &StartSU, const SUnit &TargetSU,
730
                                 bool &Success);
731
732
    /// Checks if \p SU is reachable from \p TargetSU.
733
    bool IsReachable(const SUnit *SU, const SUnit *TargetSU);
734
735
    /// Returns true if addPred(TargetSU, SU) creates a cycle.
736
    bool WillCreateCycle(SUnit *TargetSU, SUnit *SU);
737
738
    /// Updates the topological ordering to accommodate an edge to be
739
    /// added from SUnit \p X to SUnit \p Y.
740
    void AddPred(SUnit *Y, SUnit *X);
741
742
    /// Updates the topological ordering to accommodate an an edge to be
743
    /// removed from the specified node \p N from the predecessors of the
744
    /// current node \p M.
745
    void RemovePred(SUnit *M, SUnit *N);
746
747
    typedef std::vector<int>::iterator iterator;
748
    typedef std::vector<int>::const_iterator const_iterator;
749
191
    iterator begin() { return Index2Node.begin(); }
750
0
    const_iterator begin() const { return Index2Node.begin(); }
751
191
    iterator end() { return Index2Node.end(); }
752
0
    const_iterator end() const { return Index2Node.end(); }
753
754
    typedef std::vector<int>::reverse_iterator reverse_iterator;
755
    typedef std::vector<int>::const_reverse_iterator const_reverse_iterator;
756
191
    reverse_iterator rbegin() { return Index2Node.rbegin(); }
757
0
    const_reverse_iterator rbegin() const { return Index2Node.rbegin(); }
758
191
    reverse_iterator rend() { return Index2Node.rend(); }
759
0
    const_reverse_iterator rend() const { return Index2Node.rend(); }
760
  };
761
762
} // end namespace llvm
763
764
#endif // LLVM_CODEGEN_SCHEDULEDAG_H