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