/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 |