← Back to branch summary

~ubuntu-branches/ubuntu/quantal/llvm-3.1/quantal

« back to all changes in this revision

Viewing changes to include/llvm/CodeGen/ScheduleDAG.h

  • Committer: Package Import Robot
  • Author(s): Sylvestre Ledru
  • Date: 2012-03-29 19:09:51 UTC
  • Revision ID: package-import@ubuntu.com-20120329190951-aq83ivog4cg8bxun
Tags: upstream-3.1~svn153643
Import upstream version 3.1~svn153643

Show diffs side-by-side

added added

removed removed

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