Coverage Report

Created: 2018-11-16 02:38

/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 LLVMTargetMachine;
37
class MachineFunction;
38
class MachineRegisterInfo;
39
class MCInstrDesc;
40
struct MCSchedClassDesc;
41
class SDNode;
42
class SUnit;
43
class ScheduleDAG;
44
class TargetInstrInfo;
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.55M
    SDep() : Dep(nullptr, Data) {}
103
104
    /// Constructs an SDep with the specified values.
105
    SDep(SUnit *S, Kind kind, unsigned Reg)
106
21.6M
      : Dep(S, kind), Contents() {
107
21.6M
      switch (kind) {
108
21.6M
      default:
109
0
        llvm_unreachable("Reg given for non-register dependence!");
110
21.6M
      case Anti:
111
2.08M
      case Output:
112
2.08M
        assert(Reg != 0 &&
113
2.08M
               "SDep::Anti and SDep::Output must use a non-zero Reg!");
114
2.08M
        Contents.Reg = Reg;
115
2.08M
        Latency = 0;
116
2.08M
        break;
117
19.5M
      case Data:
118
19.5M
        Contents.Reg = Reg;
119
19.5M
        Latency = 1;
120
19.5M
        break;
121
21.6M
      }
122
21.6M
    }
123
124
    SDep(SUnit *S, OrderKind kind)
125
19.3M
      : Dep(S, Order), Contents(), Latency(0) {
126
19.3M
      Contents.OrdKind = kind;
127
19.3M
    }
128
129
    /// Returns true if the specified SDep is equivalent except for latency.
130
    bool overlaps(const SDep &Other) const;
131
132
19.3k
    bool operator==(const SDep &Other) const {
133
19.3k
      return overlaps(Other) && 
Latency == Other.Latency11.6k
;
134
19.3k
    }
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
87.5M
    bool isCtrl() const {
163
87.5M
      return getKind() != Data;
164
87.5M
    }
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.0M
;
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.41M
;
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.85M
;
209
1.92M
    }
210
211
    /// Tests if this is a Data dependence that is associated with a register.
212
41.3M
    bool isAssignedRegDep() const {
213
41.3M
      return getKind() == Data && 
Contents.Reg != 025.9M
;
214
41.3M
    }
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.90M
    unsigned getReg() const {
220
4.90M
      assert((getKind() == Data || getKind() == Anti || getKind() == Output) &&
221
4.90M
             "getReg called on non-register dependence edge!");
222
4.90M
      return Contents.Reg;
223
4.90M
    }
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
    void dump(const TargetRegisterInfo *TRI = nullptr) const;
240
  };
241
242
  template <>
243
  struct isPodLike<SDep> { static const bool value = true; };
244
245
  /// Scheduling unit. This is a node in the scheduling DAG.
246
  class SUnit {
247
  private:
248
    enum : unsigned { BoundaryID = ~0u };
249
250
    SDNode *Node = nullptr;        ///< Representative node.
251
    MachineInstr *Instr = nullptr; ///< Alternatively, a MachineInstr.
252
253
  public:
254
    SUnit *OrigNode = nullptr; ///< If not this, the node from which this node
255
                               /// was cloned. (SD scheduling only)
256
257
    const MCSchedClassDesc *SchedClass =
258
        nullptr; ///< nullptr or resolved SchedClass.
259
260
    SmallVector<SDep, 4> Preds;  ///< All sunit predecessors.
261
    SmallVector<SDep, 4> Succs;  ///< All sunit successors.
262
263
    typedef SmallVectorImpl<SDep>::iterator pred_iterator;
264
    typedef SmallVectorImpl<SDep>::iterator succ_iterator;
265
    typedef SmallVectorImpl<SDep>::const_iterator const_pred_iterator;
266
    typedef SmallVectorImpl<SDep>::const_iterator const_succ_iterator;
267
268
    unsigned NodeNum = BoundaryID;     ///< Entry # of node in the node vector.
269
    unsigned NodeQueueId = 0;          ///< Queue id of node.
270
    unsigned NumPreds = 0;             ///< # of SDep::Data preds.
271
    unsigned NumSuccs = 0;             ///< # of SDep::Data sucss.
272
    unsigned NumPredsLeft = 0;         ///< # of preds not scheduled.
273
    unsigned NumSuccsLeft = 0;         ///< # of succs not scheduled.
274
    unsigned WeakPredsLeft = 0;        ///< # of weak preds not scheduled.
275
    unsigned WeakSuccsLeft = 0;        ///< # of weak succs not scheduled.
276
    unsigned short NumRegDefsLeft = 0; ///< # of reg defs with no scheduled use.
277
    unsigned short Latency = 0;        ///< Node latency.
278
    bool isVRegCycle      : 1;         ///< May use and def the same vreg.
279
    bool isCall           : 1;         ///< Is a function call.
280
    bool isCallOp         : 1;         ///< Is a function call operand.
281
    bool isTwoAddress     : 1;         ///< Is a two-address instruction.
282
    bool isCommutable     : 1;         ///< Is a commutable instruction.
283
    bool hasPhysRegUses   : 1;         ///< Has physreg uses.
284
    bool hasPhysRegDefs   : 1;         ///< Has physreg defs that are being used.
285
    bool hasPhysRegClobbers : 1;       ///< Has any physreg defs, used or not.
286
    bool isPending        : 1;         ///< True once pending.
287
    bool isAvailable      : 1;         ///< True once available.
288
    bool isScheduled      : 1;         ///< True once scheduled.
289
    bool isScheduleHigh   : 1;         ///< True if preferable to schedule high.
290
    bool isScheduleLow    : 1;         ///< True if preferable to schedule low.
291
    bool isCloned         : 1;         ///< True if this node has been cloned.
292
    bool isUnbuffered     : 1;         ///< Uses an unbuffered resource.
293
    bool hasReservedResource : 1;      ///< Uses a reserved resource.
294
    Sched::Preference SchedulingPref = Sched::None; ///< Scheduling preference.
295
296
  private:
297
    bool isDepthCurrent   : 1;         ///< True if Depth is current.
298
    bool isHeightCurrent  : 1;         ///< True if Height is current.
299
    unsigned Depth = 0;                ///< Node depth.
300
    unsigned Height = 0;               ///< Node height.
301
302
  public:
303
    unsigned TopReadyCycle = 0; ///< Cycle relative to start when node is ready.
304
    unsigned BotReadyCycle = 0; ///< Cycle relative to end when node is ready.
305
306
    const TargetRegisterClass *CopyDstRC =
307
        nullptr; ///< Is a special copy node if != nullptr.
308
    const TargetRegisterClass *CopySrcRC = nullptr;
309
310
    /// Constructs an SUnit for pre-regalloc scheduling to represent an
311
    /// SDNode and any nodes flagged to it.
312
    SUnit(SDNode *node, unsigned nodenum)
313
      : Node(node), NodeNum(nodenum), isVRegCycle(false), isCall(false),
314
        isCallOp(false), isTwoAddress(false), isCommutable(false),
315
        hasPhysRegUses(false), hasPhysRegDefs(false), hasPhysRegClobbers(false),
316
        isPending(false), isAvailable(false), isScheduled(false),
317
        isScheduleHigh(false), isScheduleLow(false), isCloned(false),
318
        isUnbuffered(false), hasReservedResource(false), isDepthCurrent(false),
319
16.4M
        isHeightCurrent(false) {}
320
321
    /// Constructs an SUnit for post-regalloc scheduling to represent a
322
    /// MachineInstr.
323
    SUnit(MachineInstr *instr, unsigned nodenum)
324
      : Instr(instr), NodeNum(nodenum), isVRegCycle(false), isCall(false),
325
        isCallOp(false), isTwoAddress(false), isCommutable(false),
326
        hasPhysRegUses(false), hasPhysRegDefs(false), hasPhysRegClobbers(false),
327
        isPending(false), isAvailable(false), isScheduled(false),
328
        isScheduleHigh(false), isScheduleLow(false), isCloned(false),
329
        isUnbuffered(false), hasReservedResource(false), isDepthCurrent(false),
330
12.7M
        isHeightCurrent(false) {}
331
332
    /// Constructs a placeholder SUnit.
333
    SUnit()
334
      : isVRegCycle(false), isCall(false), isCallOp(false), isTwoAddress(false),
335
        isCommutable(false), hasPhysRegUses(false), hasPhysRegDefs(false),
336
        hasPhysRegClobbers(false), isPending(false), isAvailable(false),
337
        isScheduled(false), isScheduleHigh(false), isScheduleLow(false),
338
        isCloned(false), isUnbuffered(false), hasReservedResource(false),
339
14.2M
        isDepthCurrent(false), isHeightCurrent(false) {}
340
341
    /// Boundary nodes are placeholders for the boundary of the
342
    /// scheduling region.
343
    ///
344
    /// BoundaryNodes can have DAG edges, including Data edges, but they do not
345
    /// correspond to schedulable entities (e.g. instructions) and do not have a
346
    /// valid ID. Consequently, always check for boundary nodes before accessing
347
    /// an associative data structure keyed on node ID.
348
1.04M
    bool isBoundaryNode() const { return NodeNum == BoundaryID; }
349
350
    /// Assigns the representative SDNode for this SUnit. This may be used
351
    /// during pre-regalloc scheduling.
352
16.4M
    void setNode(SDNode *N) {
353
16.4M
      assert(!Instr && "Setting SDNode of SUnit with MachineInstr!");
354
16.4M
      Node = N;
355
16.4M
    }
356
357
    /// Returns the representative SDNode for this SUnit. This may be used
358
    /// during pre-regalloc scheduling.
359
347M
    SDNode *getNode() const {
360
347M
      assert(!Instr && "Reading SDNode of SUnit with MachineInstr!");
361
347M
      return Node;
362
347M
    }
363
364
    /// Returns true if this SUnit refers to a machine instruction as
365
    /// opposed to an SDNode.
366
3.09M
    bool isInstr() const { return Instr; }
367
368
    /// Assigns the instruction for the SUnit. This may be used during
369
    /// post-regalloc scheduling.
370
3.02M
    void setInstr(MachineInstr *MI) {
371
3.02M
      assert(!Node && "Setting MachineInstr of SUnit with SDNode!");
372
3.02M
      Instr = MI;
373
3.02M
    }
374
375
    /// Returns the representative MachineInstr for this SUnit. This may be used
376
    /// during post-regalloc scheduling.
377
450M
    MachineInstr *getInstr() const {
378
450M
      assert(!Node && "Reading MachineInstr of SUnit with SDNode!");
379
450M
      return Instr;
380
450M
    }
381
382
    /// Adds the specified edge as a pred of the current node if not already.
383
    /// It also adds the current node as a successor of the specified node.
384
    bool addPred(const SDep &D, bool Required = true);
385
386
    /// Adds a barrier edge to SU by calling addPred(), with latency 0
387
    /// generally or latency 1 for a store followed by a load.
388
308k
    bool addPredBarrier(SUnit *SU) {
389
308k
      SDep Dep(SU, SDep::Barrier);
390
308k
      unsigned TrueMemOrderLatency =
391
308k
        ((SU->getInstr()->mayStore() && 
this->getInstr()->mayLoad()133k
) ?
161.3k
:
0247k
);
392
308k
      Dep.setLatency(TrueMemOrderLatency);
393
308k
      return addPred(Dep);
394
308k
    }
395
396
    /// Removes the specified edge as a pred of the current node if it exists.
397
    /// It also removes the current node as a successor of the specified node.
398
    void removePred(const SDep &D);
399
400
    /// Returns the depth of this node, which is the length of the maximum path
401
    /// up to any node which has no predecessors.
402
72.5M
    unsigned getDepth() const {
403
72.5M
      if (!isDepthCurrent)
404
8.71M
        const_cast<SUnit *>(this)->ComputeDepth();
405
72.5M
      return Depth;
406
72.5M
    }
407
408
    /// Returns the height of this node, which is the length of the
409
    /// maximum path down to any node which has no successors.
410
126M
    unsigned getHeight() const {
411
126M
      if (!isHeightCurrent)
412
26.0M
        const_cast<SUnit *>(this)->ComputeHeight();
413
126M
      return Height;
414
126M
    }
415
416
    /// If NewDepth is greater than this node's depth value, sets it to
417
    /// be the new depth value. This also recursively marks successor nodes
418
    /// dirty.
419
    void setDepthToAtLeast(unsigned NewDepth);
420
421
    /// If NewDepth is greater than this node's depth value, set it to be
422
    /// the new height value. This also recursively marks predecessor nodes
423
    /// dirty.
424
    void setHeightToAtLeast(unsigned NewHeight);
425
426
    /// Sets a flag in this node to indicate that its stored Depth value
427
    /// will require recomputation the next time getDepth() is called.
428
    void setDepthDirty();
429
430
    /// Sets a flag in this node to indicate that its stored Height value
431
    /// will require recomputation the next time getHeight() is called.
432
    void setHeightDirty();
433
434
    /// Tests if node N is a predecessor of this node.
435
6.87k
    bool isPred(const SUnit *N) const {
436
6.87k
      for (const SDep &Pred : Preds)
437
15.1k
        if (Pred.getSUnit() == N)
438
3.41k
          return true;
439
6.87k
      
return false3.45k
;
440
6.87k
    }
441
442
    /// Tests if node N is a successor of this node.
443
155k
    bool isSucc(const SUnit *N) const {
444
155k
      for (const SDep &Succ : Succs)
445
363k
        if (Succ.getSUnit() == N)
446
23.5k
          return true;
447
155k
      
return false131k
;
448
155k
    }
449
450
11.8M
    bool isTopReady() const {
451
11.8M
      return NumPredsLeft == 0;
452
11.8M
    }
453
11.8M
    bool isBottomReady() const {
454
11.8M
      return NumSuccsLeft == 0;
455
11.8M
    }
456
457
    /// Orders this node's predecessor edges such that the critical path
458
    /// edge occurs first.
459
    void biasCriticalPath();
460
461
    void dumpAttributes() const;
462
463
  private:
464
    void ComputeDepth();
465
    void ComputeHeight();
466
  };
467
468
  /// Returns true if the specified SDep is equivalent except for latency.
469
243M
  inline bool SDep::overlaps(const SDep &Other) const {
470
243M
    if (Dep != Other.Dep)
471
241M
      return false;
472
2.20M
    switch (Dep.getInt()) {
473
2.20M
    case Data:
474
804k
    case Anti:
475
804k
    case Output:
476
804k
      return Contents.Reg == Other.Contents.Reg;
477
1.40M
    case Order:
478
1.40M
      return Contents.OrdKind == Other.Contents.OrdKind;
479
0
    }
480
0
    llvm_unreachable("Invalid dependency kind!");
481
0
  }
482
483
  //// Returns the SUnit to which this edge points.
484
428M
  inline SUnit *SDep::getSUnit() const { return Dep.getPointer(); }
485
486
  //// Assigns the SUnit to which this edge points.
487
39.2M
  inline void SDep::setSUnit(SUnit *SU) { Dep.setPointer(SU); }
488
489
  /// Returns an enum value representing the kind of the dependence.
490
280M
  inline SDep::Kind SDep::getKind() const { return Dep.getInt(); }
491
492
  //===--------------------------------------------------------------------===//
493
494
  /// This interface is used to plug different priorities computation
495
  /// algorithms into the list scheduler. It implements the interface of a
496
  /// standard priority queue, where nodes are inserted in arbitrary order and
497
  /// returned in priority order.  The computation of the priority and the
498
  /// representation of the queue are totally up to the implementation to
499
  /// decide.
500
  class SchedulingPriorityQueue {
501
    virtual void anchor();
502
503
    unsigned CurCycle = 0;
504
    bool HasReadyFilter;
505
506
  public:
507
1.84M
    SchedulingPriorityQueue(bool rf = false) :  HasReadyFilter(rf) {}
508
509
1.84M
    virtual ~SchedulingPriorityQueue() = default;
510
511
    virtual bool isBottomUp() const = 0;
512
513
    virtual void initNodes(std::vector<SUnit> &SUnits) = 0;
514
    virtual void addNode(const SUnit *SU) = 0;
515
    virtual void updateNode(const SUnit *SU) = 0;
516
    virtual void releaseState() = 0;
517
518
    virtual bool empty() const = 0;
519
520
14.7M
    bool hasReadyFilter() const { return HasReadyFilter; }
521
522
0
    virtual bool tracksRegPressure() const { return false; }
523
524
0
    virtual bool isReady(SUnit *) const {
525
0
      assert(!HasReadyFilter && "The ready filter must override isReady()");
526
0
      return true;
527
0
    }
528
529
    virtual void push(SUnit *U) = 0;
530
531
41.1k
    void push_all(const std::vector<SUnit *> &Nodes) {
532
41.1k
      for (std::vector<SUnit *>::const_iterator I = Nodes.begin(),
533
108k
           E = Nodes.end(); I != E; 
++I66.8k
)
534
66.8k
        push(*I);
535
41.1k
    }
536
537
    virtual SUnit *pop() = 0;
538
539
    virtual void remove(SUnit *SU) = 0;
540
541
0
    virtual void dump(ScheduleDAG *) const {}
542
543
    /// As each node is scheduled, this method is invoked.  This allows the
544
    /// priority function to adjust the priority of related unscheduled nodes,
545
    /// for example.
546
0
    virtual void scheduledNode(SUnit *) {}
547
548
0
    virtual void unscheduledNode(SUnit *) {}
549
550
16.2M
    void setCurCycle(unsigned Cycle) {
551
16.2M
      CurCycle = Cycle;
552
16.2M
    }
553
554
7.98M
    unsigned getCurCycle() const {
555
7.98M
      return CurCycle;
556
7.98M
    }
557
  };
558
559
  class ScheduleDAG {
560
  public:
561
    const LLVMTargetMachine &TM;        ///< Target processor
562
    const TargetInstrInfo *TII;         ///< Target instruction information
563
    const TargetRegisterInfo *TRI;      ///< Target processor register info
564
    MachineFunction &MF;                ///< Machine function
565
    MachineRegisterInfo &MRI;           ///< Virtual/real register map
566
    std::vector<SUnit> SUnits;          ///< The scheduling units.
567
    SUnit EntrySU;                      ///< Special node for the region entry.
568
    SUnit ExitSU;                       ///< Special node for the region exit.
569
570
#ifdef NDEBUG
571
    static const bool StressSched = false;
572
#else
573
    bool StressSched;
574
#endif
575
576
    explicit ScheduleDAG(MachineFunction &mf);
577
578
    virtual ~ScheduleDAG();
579
580
    /// Clears the DAG state (between regions).
581
    void clearDAG();
582
583
    /// Returns the MCInstrDesc of this SUnit.
584
    /// Returns NULL for SDNodes without a machine opcode.
585
2.69M
    const MCInstrDesc *getInstrDesc(const SUnit *SU) const {
586
2.69M
      if (SU->isInstr()) 
return &SU->getInstr()->getDesc()1.07M
;
587
1.61M
      return getNodeDesc(SU->getNode());
588
1.61M
    }
589
590
    /// Pops up a GraphViz/gv window with the ScheduleDAG rendered using 'dot'.
591
    virtual void viewGraph(const Twine &Name, const Twine &Title);
592
    virtual void viewGraph();
593
594
    virtual void dumpNode(const SUnit &SU) const = 0;
595
    virtual void dump() const = 0;
596
    void dumpNodeName(const SUnit &SU) const;
597
598
    /// Returns a label for an SUnit node in a visualization of the ScheduleDAG.
599
    virtual std::string getGraphNodeLabel(const SUnit *SU) const = 0;
600
601
    /// Returns a label for the region of code covered by the DAG.
602
    virtual std::string getDAGName() const = 0;
603
604
    /// Adds custom features for a visualization of the ScheduleDAG.
605
0
    virtual void addCustomGraphFeatures(GraphWriter<ScheduleDAG*> &) const {}
606
607
#ifndef NDEBUG
608
    /// Verifies that all SUnits were scheduled and that their state is
609
    /// consistent. Returns the number of scheduled SUnits.
610
    unsigned VerifyScheduledDAG(bool isBottomUp);
611
#endif
612
613
  protected:
614
    void dumpNodeAll(const SUnit &SU) const;
615
616
  private:
617
    /// Returns the MCInstrDesc of this SDNode or NULL.
618
    const MCInstrDesc *getNodeDesc(const SDNode *Node) const;
619
  };
620
621
  class SUnitIterator : public std::iterator<std::forward_iterator_tag,
622
                                             SUnit, ptrdiff_t> {
623
    SUnit *Node;
624
    unsigned Operand;
625
626
    SUnitIterator(SUnit *N, unsigned Op) : Node(N), Operand(Op) {}
627
628
  public:
629
    bool operator==(const SUnitIterator& x) const {
630
      return Operand == x.Operand;
631
    }
632
    bool operator!=(const SUnitIterator& x) const { return !operator==(x); }
633
634
    pointer operator*() const {
635
      return Node->Preds[Operand].getSUnit();
636
    }
637
    pointer operator->() const { return operator*(); }
638
639
    SUnitIterator& operator++() {                // Preincrement
640
      ++Operand;
641
      return *this;
642
    }
643
    SUnitIterator operator++(int) { // Postincrement
644
      SUnitIterator tmp = *this; ++*this; return tmp;
645
    }
646
647
    static SUnitIterator begin(SUnit *N) { return SUnitIterator(N, 0); }
648
    static SUnitIterator end  (SUnit *N) {
649
      return SUnitIterator(N, (unsigned)N->Preds.size());
650
    }
651
652
    unsigned getOperand() const { return Operand; }
653
    const SUnit *getNode() const { return Node; }
654
655
    /// Tests if this is not an SDep::Data dependence.
656
0
    bool isCtrlDep() const {
657
0
      return getSDep().isCtrl();
658
0
    }
659
0
    bool isArtificialDep() const {
660
0
      return getSDep().isArtificial();
661
0
    }
662
0
    const SDep &getSDep() const {
663
0
      return Node->Preds[Operand];
664
0
    }
665
  };
666
667
  template <> struct GraphTraits<SUnit*> {
668
    typedef SUnit *NodeRef;
669
    typedef SUnitIterator ChildIteratorType;
670
    static NodeRef getEntryNode(SUnit *N) { return N; }
671
    static ChildIteratorType child_begin(NodeRef N) {
672
      return SUnitIterator::begin(N);
673
    }
674
    static ChildIteratorType child_end(NodeRef N) {
675
      return SUnitIterator::end(N);
676
    }
677
  };
678
679
  template <> struct GraphTraits<ScheduleDAG*> : public GraphTraits<SUnit*> {
680
    typedef pointer_iterator<std::vector<SUnit>::iterator> nodes_iterator;
681
    static nodes_iterator nodes_begin(ScheduleDAG *G) {
682
      return nodes_iterator(G->SUnits.begin());
683
    }
684
    static nodes_iterator nodes_end(ScheduleDAG *G) {
685
      return nodes_iterator(G->SUnits.end());
686
    }
687
  };
688
689
  /// This class can compute a topological ordering for SUnits and provides
690
  /// methods for dynamically updating the ordering as new edges are added.
691
  ///
692
  /// This allows a very fast implementation of IsReachable, for example.
693
  class ScheduleDAGTopologicalSort {
694
    /// A reference to the ScheduleDAG's SUnits.
695
    std::vector<SUnit> &SUnits;
696
    SUnit *ExitSU;
697
698
    /// Maps topological index to the node number.
699
    std::vector<int> Index2Node;
700
    /// Maps the node number to its topological index.
701
    std::vector<int> Node2Index;
702
    /// a set of nodes visited during a DFS traversal.
703
    BitVector Visited;
704
705
    /// Makes a DFS traversal and mark all nodes affected by the edge insertion.
706
    /// These nodes will later get new topological indexes by means of the Shift
707
    /// method.
708
    void DFS(const SUnit *SU, int UpperBound, bool& HasLoop);
709
710
    /// Reassigns topological indexes for the nodes in the DAG to
711
    /// preserve the topological ordering.
712
    void Shift(BitVector& Visited, int LowerBound, int UpperBound);
713
714
    /// Assigns the topological index to the node n.
715
    void Allocate(int n, int index);
716
717
  public:
718
    ScheduleDAGTopologicalSort(std::vector<SUnit> &SUnits, SUnit *ExitSU);
719
720
    /// Creates the initial topological ordering from the DAG to be scheduled.
721
    void InitDAGTopologicalSorting();
722
723
    /// Returns an array of SUs that are both in the successor
724
    /// subtree of StartSU and in the predecessor subtree of TargetSU.
725
    /// StartSU and TargetSU are not in the array.
726
    /// Success is false if TargetSU is not in the successor subtree of
727
    /// StartSU, else it is true.
728
    std::vector<int> GetSubGraph(const SUnit &StartSU, const SUnit &TargetSU,
729
                                 bool &Success);
730
731
    /// Checks if \p SU is reachable from \p TargetSU.
732
    bool IsReachable(const SUnit *SU, const SUnit *TargetSU);
733
734
    /// Returns true if addPred(TargetSU, SU) creates a cycle.
735
    bool WillCreateCycle(SUnit *TargetSU, SUnit *SU);
736
737
    /// Updates the topological ordering to accommodate an edge to be
738
    /// added from SUnit \p X to SUnit \p Y.
739
    void AddPred(SUnit *Y, SUnit *X);
740
741
    /// Updates the topological ordering to accommodate an an edge to be
742
    /// removed from the specified node \p N from the predecessors of the
743
    /// current node \p M.
744
    void RemovePred(SUnit *M, SUnit *N);
745
746
    typedef std::vector<int>::iterator iterator;
747
    typedef std::vector<int>::const_iterator const_iterator;
748
380
    iterator begin() { return Index2Node.begin(); }
749
0
    const_iterator begin() const { return Index2Node.begin(); }
750
380
    iterator end() { return Index2Node.end(); }
751
0
    const_iterator end() const { return Index2Node.end(); }
752
753
    typedef std::vector<int>::reverse_iterator reverse_iterator;
754
    typedef std::vector<int>::const_reverse_iterator const_reverse_iterator;
755
190
    reverse_iterator rbegin() { return Index2Node.rbegin(); }
756
0
    const_reverse_iterator rbegin() const { return Index2Node.rbegin(); }
757
190
    reverse_iterator rend() { return Index2Node.rend(); }
758
0
    const_reverse_iterator rend() const { return Index2Node.rend(); }
759
  };
760
761
} // end namespace llvm
762
763
#endif // LLVM_CODEGEN_SCHEDULEDAG_H