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
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
|
//===---- 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/MachineBasicBlock.h"
#include "llvm/CodeGen/ScheduleDAG.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:
MachineBasicBlock *BB;
SelectionDAG *DAG; // DAG of the current basic block
const InstrItineraryData *InstrItins;
/// The schedule. Null SUnit*'s represent noop instructions.
std::vector<SUnit*> Sequence;
explicit ScheduleDAGSDNodes(MachineFunction &mf);
virtual ~ScheduleDAGSDNodes() {}
/// Run - perform scheduling.
///
void Run(SelectionDAG *dag, MachineBasicBlock *bb);
/// 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<RegisterMaskSDNode>(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<TargetIndexSDNode>(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.
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);
virtual void computeOperandLatency(SDNode *Def, SDNode *Use,
unsigned OpIdx, SDep& dep) const;
/// Schedule - Order nodes according to selected style, filling
/// in the Sequence member.
///
virtual void Schedule() = 0;
/// VerifyScheduledSequence - Verify that all SUnits are scheduled and
/// consistent with the Sequence of scheduled instructions.
void VerifyScheduledSequence(bool isBottomUp);
/// EmitSchedule - Insert MachineInstrs into the MachineBasicBlock
/// according to the order specified in Sequence.
///
virtual MachineBasicBlock*
EmitSchedule(MachineBasicBlock::iterator &InsertPos);
virtual void dumpNode(const SUnit *SU) const;
void dumpSchedule() const;
virtual std::string getGraphNodeLabel(const SUnit *SU) const;
virtual std::string getDAGName() 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;
MVT ValueType;
public:
RegDefIter(const SUnit *SU, const ScheduleDAGSDNodes *SD);
bool IsValid() const { return Node != NULL; }
MVT GetValue() const {
assert(IsValid() && "bad iterator");
return ValueType;
}
const SDNode *GetNode() const {
return Node;
}
unsigned GetIdx() const {
return DefIdx-1;
}
void Advance();
private:
void InitNodeNumDefs();
};
protected:
/// ForceUnitLatencies - Return true if all scheduling edges should be given
/// a latency value of one. The default is to return false; schedulers may
/// override this as needed.
virtual bool forceUnitLatencies() const { return false; }
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();
void EmitPhysRegCopy(SUnit *SU, DenseMap<SUnit*, unsigned> &VRBaseMap,
MachineBasicBlock::iterator InsertPos);
};
}
#endif
|
