aboutsummaryrefslogtreecommitdiff
path: root/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.h
blob: b5f68f3055cf9901ef648d8058409dfad41b5cc3 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
//===---- ScheduleDAGSDNodes.h - SDNode Scheduling --------------*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements the ScheduleDAGSDNodes class, which implements
// scheduling for an SDNode-based dependency graph.
//
//===----------------------------------------------------------------------===//

#ifndef SCHEDULEDAGSDNODES_H
#define SCHEDULEDAGSDNODES_H

#include "llvm/CodeGen/ScheduleDAG.h"
#include "llvm/CodeGen/SelectionDAG.h"

namespace llvm {
  /// ScheduleDAGSDNodes - A ScheduleDAG for scheduling SDNode-based DAGs.
  ///
  /// Edges between SUnits are initially based on edges in the SelectionDAG,
  /// and additional edges can be added by the schedulers as heuristics.
  /// SDNodes such as Constants, Registers, and a few others that are not
  /// interesting to schedulers are not allocated SUnits.
  ///
  /// SDNodes with MVT::Glue operands are grouped along with the flagged
  /// nodes into a single SUnit so that they are scheduled together.
  ///
  /// SDNode-based scheduling graphs do not use SDep::Anti or SDep::Output
  /// edges.  Physical register dependence information is not carried in
  /// the DAG and must be handled explicitly by schedulers.
  ///
  class ScheduleDAGSDNodes : public ScheduleDAG {
  public:
    SelectionDAG *DAG;                    // DAG of the current basic block
    const InstrItineraryData *InstrItins;

    explicit ScheduleDAGSDNodes(MachineFunction &mf);

    virtual ~ScheduleDAGSDNodes() {}

    /// Run - perform scheduling.
    ///
    void Run(SelectionDAG *dag, MachineBasicBlock *bb,
             MachineBasicBlock::iterator insertPos);

    /// isPassiveNode - Return true if the node is a non-scheduled leaf.
    ///
    static bool isPassiveNode(SDNode *Node) {
      if (isa<ConstantSDNode>(Node))       return true;
      if (isa<ConstantFPSDNode>(Node))     return true;
      if (isa<RegisterSDNode>(Node))       return true;
      if (isa<GlobalAddressSDNode>(Node))  return true;
      if (isa<BasicBlockSDNode>(Node))     return true;
      if (isa<FrameIndexSDNode>(Node))     return true;
      if (isa<ConstantPoolSDNode>(Node))   return true;
      if (isa<JumpTableSDNode>(Node))      return true;
      if (isa<ExternalSymbolSDNode>(Node)) return true;
      if (isa<BlockAddressSDNode>(Node))   return true;
      if (Node->getOpcode() == ISD::EntryToken ||
          isa<MDNodeSDNode>(Node)) return true;
      return false;
    }

    /// NewSUnit - Creates a new SUnit and return a ptr to it.
    ///
    SUnit *NewSUnit(SDNode *N);

    /// Clone - Creates a clone of the specified SUnit. It does not copy the
    /// predecessors / successors info nor the temporary scheduling states.
    ///
    SUnit *Clone(SUnit *N);

    /// BuildSchedGraph - Build the SUnit graph from the selection dag that we
    /// are input.  This SUnit graph is similar to the SelectionDAG, but
    /// excludes nodes that aren't interesting to scheduling, and represents
    /// flagged together nodes with a single SUnit.
    virtual void BuildSchedGraph(AliasAnalysis *AA);

    /// InitVRegCycleFlag - Set isVRegCycle if this node's single use is
    /// CopyToReg and its only active data operands are CopyFromReg within a
    /// single block loop.
    ///
    void InitVRegCycleFlag(SUnit *SU);

    /// InitNumRegDefsLeft - Determine the # of regs defined by this node.
    ///
    void InitNumRegDefsLeft(SUnit *SU);

    /// ComputeLatency - Compute node latency.
    ///
    virtual void ComputeLatency(SUnit *SU);

    /// ComputeOperandLatency - Override dependence edge latency using
    /// operand use/def information
    ///
    virtual void ComputeOperandLatency(SUnit *Def, SUnit *Use,
                                       SDep& dep) const { }

    virtual void ComputeOperandLatency(SDNode *Def, SDNode *Use,
                                       unsigned OpIdx, SDep& dep) const;

    virtual MachineBasicBlock *EmitSchedule();

    /// Schedule - Order nodes according to selected style, filling
    /// in the Sequence member.
    ///
    virtual void Schedule() = 0;

    virtual void dumpNode(const SUnit *SU) const;

    virtual std::string getGraphNodeLabel(const SUnit *SU) const;

    virtual void getCustomGraphFeatures(GraphWriter<ScheduleDAG*> &GW) const;

    /// RegDefIter - In place iteration over the values defined by an
    /// SUnit. This does not need copies of the iterator or any other STLisms.
    /// The iterator creates itself, rather than being provided by the SchedDAG.
    class RegDefIter {
      const ScheduleDAGSDNodes *SchedDAG;
      const SDNode *Node;
      unsigned DefIdx;
      unsigned NodeNumDefs;
      EVT ValueType;
    public:
      RegDefIter(const SUnit *SU, const ScheduleDAGSDNodes *SD);

      bool IsValid() const { return Node != NULL; }

      EVT GetValue() const {
        assert(IsValid() && "bad iterator");
        return ValueType;
      }

      void Advance();
    private:
      void InitNodeNumDefs();
    };

  private:
    /// ClusterNeighboringLoads - Cluster loads from "near" addresses into
    /// combined SUnits.
    void ClusterNeighboringLoads(SDNode *Node);
    /// ClusterNodes - Cluster certain nodes which should be scheduled together.
    ///
    void ClusterNodes();

    /// BuildSchedUnits, AddSchedEdges - Helper functions for BuildSchedGraph.
    void BuildSchedUnits();
    void AddSchedEdges();
  };
}

#endif