Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.h
Line
Count
Source (jump to first uncovered line)
1
//===---- ScheduleDAGSDNodes.h - SDNode Scheduling --------------*- C++ -*-===//
2
//
3
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8
//
9
// This file implements the ScheduleDAGSDNodes class, which implements
10
// scheduling for an SDNode-based dependency graph.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#ifndef LLVM_LIB_CODEGEN_SELECTIONDAG_SCHEDULEDAGSDNODES_H
15
#define LLVM_LIB_CODEGEN_SELECTIONDAG_SCHEDULEDAGSDNODES_H
16
17
#include "llvm/CodeGen/ISDOpcodes.h"
18
#include "llvm/CodeGen/MachineBasicBlock.h"
19
#include "llvm/CodeGen/ScheduleDAG.h"
20
#include "llvm/CodeGen/SelectionDAGNodes.h"
21
#include "llvm/Support/Casting.h"
22
#include "llvm/Support/MachineValueType.h"
23
#include <cassert>
24
#include <string>
25
#include <vector>
26
27
namespace llvm {
28
29
class InstrItineraryData;
30
31
  /// ScheduleDAGSDNodes - A ScheduleDAG for scheduling SDNode-based DAGs.
32
  ///
33
  /// Edges between SUnits are initially based on edges in the SelectionDAG,
34
  /// and additional edges can be added by the schedulers as heuristics.
35
  /// SDNodes such as Constants, Registers, and a few others that are not
36
  /// interesting to schedulers are not allocated SUnits.
37
  ///
38
  /// SDNodes with MVT::Glue operands are grouped along with the flagged
39
  /// nodes into a single SUnit so that they are scheduled together.
40
  ///
41
  /// SDNode-based scheduling graphs do not use SDep::Anti or SDep::Output
42
  /// edges.  Physical register dependence information is not carried in
43
  /// the DAG and must be handled explicitly by schedulers.
44
  ///
45
  class ScheduleDAGSDNodes : public ScheduleDAG {
46
  public:
47
    MachineBasicBlock *BB;
48
    SelectionDAG *DAG;                    // DAG of the current basic block
49
    const InstrItineraryData *InstrItins;
50
51
    /// The schedule. Null SUnit*'s represent noop instructions.
52
    std::vector<SUnit*> Sequence;
53
54
    explicit ScheduleDAGSDNodes(MachineFunction &mf);
55
56
1.24M
    ~ScheduleDAGSDNodes() override = default;
57
58
    /// Run - perform scheduling.
59
    ///
60
    void Run(SelectionDAG *dag, MachineBasicBlock *bb);
61
62
    /// isPassiveNode - Return true if the node is a non-scheduled leaf.
63
    ///
64
69.4M
    static bool isPassiveNode(SDNode *Node) {
65
69.4M
      if (isa<ConstantSDNode>(Node))       
return true13.1M
;
66
56.2M
      if (isa<ConstantFPSDNode>(Node))     
return true587
;
67
56.2M
      if (isa<RegisterSDNode>(Node))       
return true13.0M
;
68
43.1M
      if (isa<RegisterMaskSDNode>(Node))   
return true783k
;
69
42.4M
      if (isa<GlobalAddressSDNode>(Node))  
return true1.93M
;
70
40.4M
      if (isa<BasicBlockSDNode>(Node))     
return true2.46M
;
71
38.0M
      if (isa<FrameIndexSDNode>(Node))     
return true660k
;
72
37.3M
      if (isa<ConstantPoolSDNode>(Node))   
return true204k
;
73
37.1M
      if (isa<TargetIndexSDNode>(Node))    
return true0
;
74
37.1M
      if (isa<JumpTableSDNode>(Node))      
return true11.4k
;
75
37.1M
      if (isa<ExternalSymbolSDNode>(Node)) 
return true69.9k
;
76
37.0M
      if (isa<MCSymbolSDNode>(Node))       
return true200
;
77
37.0M
      if (isa<BlockAddressSDNode>(Node))   
return true319
;
78
37.0M
      if (Node->getOpcode() == ISD::EntryToken ||
79
37.0M
          
isa<MDNodeSDNode>(Node)31.2M
)
return true5.80M
;
80
31.2M
      return false;
81
31.2M
    }
82
83
    /// NewSUnit - Creates a new SUnit and return a ptr to it.
84
    ///
85
    SUnit *newSUnit(SDNode *N);
86
87
    /// Clone - Creates a clone of the specified SUnit. It does not copy the
88
    /// predecessors / successors info nor the temporary scheduling states.
89
    ///
90
    SUnit *Clone(SUnit *Old);
91
92
    /// BuildSchedGraph - Build the SUnit graph from the selection dag that we
93
    /// are input.  This SUnit graph is similar to the SelectionDAG, but
94
    /// excludes nodes that aren't interesting to scheduling, and represents
95
    /// flagged together nodes with a single SUnit.
96
    void BuildSchedGraph(AliasAnalysis *AA);
97
98
    /// InitNumRegDefsLeft - Determine the # of regs defined by this node.
99
    ///
100
    void InitNumRegDefsLeft(SUnit *SU);
101
102
    /// computeLatency - Compute node latency.
103
    ///
104
    virtual void computeLatency(SUnit *SU);
105
106
    virtual void computeOperandLatency(SDNode *Def, SDNode *Use,
107
                                       unsigned OpIdx, SDep& dep) const;
108
109
    /// Schedule - Order nodes according to selected style, filling
110
    /// in the Sequence member.
111
    ///
112
    virtual void Schedule() = 0;
113
114
    /// VerifyScheduledSequence - Verify that all SUnits are scheduled and
115
    /// consistent with the Sequence of scheduled instructions.
116
    void VerifyScheduledSequence(bool isBottomUp);
117
118
    /// EmitSchedule - Insert MachineInstrs into the MachineBasicBlock
119
    /// according to the order specified in Sequence.
120
    ///
121
    virtual MachineBasicBlock*
122
    EmitSchedule(MachineBasicBlock::iterator &InsertPos);
123
124
    void dumpNode(const SUnit &SU) const override;
125
    void dump() const override;
126
    void dumpSchedule() const;
127
128
    std::string getGraphNodeLabel(const SUnit *SU) const override;
129
130
    std::string getDAGName() const override;
131
132
    virtual void getCustomGraphFeatures(GraphWriter<ScheduleDAG*> &GW) const;
133
134
    /// RegDefIter - In place iteration over the values defined by an
135
    /// SUnit. This does not need copies of the iterator or any other STLisms.
136
    /// The iterator creates itself, rather than being provided by the SchedDAG.
137
    class RegDefIter {
138
      const ScheduleDAGSDNodes *SchedDAG;
139
      const SDNode *Node;
140
      unsigned DefIdx;
141
      unsigned NodeNumDefs;
142
      MVT ValueType;
143
144
    public:
145
      RegDefIter(const SUnit *SU, const ScheduleDAGSDNodes *SD);
146
147
20.6M
      bool IsValid() const { return Node != nullptr; }
148
149
1.78M
      MVT GetValue() const {
150
1.78M
        assert(IsValid() && "bad iterator");
151
1.78M
        return ValueType;
152
1.78M
      }
153
154
1.94k
      const SDNode *GetNode() const {
155
1.94k
        return Node;
156
1.94k
      }
157
158
1.47k
      unsigned GetIdx() const {
159
1.47k
        return DefIdx-1;
160
1.47k
      }
161
162
      void Advance();
163
164
    private:
165
      void InitNodeNumDefs();
166
    };
167
168
  protected:
169
    /// ForceUnitLatencies - Return true if all scheduling edges should be given
170
    /// a latency value of one.  The default is to return false; schedulers may
171
    /// override this as needed.
172
0
    virtual bool forceUnitLatencies() const { return false; }
173
174
  private:
175
    /// ClusterNeighboringLoads - Cluster loads from "near" addresses into
176
    /// combined SUnits.
177
    void ClusterNeighboringLoads(SDNode *Node);
178
    /// ClusterNodes - Cluster certain nodes which should be scheduled together.
179
    ///
180
    void ClusterNodes();
181
182
    /// BuildSchedUnits, AddSchedEdges - Helper functions for BuildSchedGraph.
183
    void BuildSchedUnits();
184
    void AddSchedEdges();
185
186
    void EmitPhysRegCopy(SUnit *SU, DenseMap<SUnit*, unsigned> &VRBaseMap,
187
                         MachineBasicBlock::iterator InsertPos);
188
  };
189
190
} // end namespace llvm
191
192
#endif // LLVM_LIB_CODEGEN_SELECTIONDAG_SCHEDULEDAGSDNODES_H