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
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
|
// -*-C++-*-
//***************************************************************************
// File:
// SchedPriorities.h
//
// Purpose:
// Encapsulate heuristics for instruction scheduling.
//
// Strategy:
// Priority ordering rules:
// (1) Max delay, which is the order of the heap S.candsAsHeap.
// (2) Instruction that frees up a register.
// (3) Instruction that has the maximum number of dependent instructions.
// Note that rules 2 and 3 are only used if issue conflicts prevent
// choosing a higher priority instruction by rule 1.
//
// History:
// 7/30/01 - Vikram Adve - Created
//**************************************************************************/
#ifndef LLVM_CODEGEN_SCHEDPRIORITIES_H
#define LLVM_CODEGEN_SCHEDPRIORITIES_H
#include "SchedGraph.h"
#include "llvm/CodeGen/InstrScheduling.h"
#include "llvm/Analysis/LiveVar/MethodLiveVarInfo.h"
#include "llvm/Target/MachineSchedInfo.h"
#include "Support/CommandLine.h"
#include <list>
#include <hash_set>
class Method;
class MachineInstr;
class SchedulingManager;
//---------------------------------------------------------------------------
// Debug option levels for instruction scheduling
enum SchedDebugLevel_t {
Sched_NoDebugInfo,
Sched_PrintMachineCode,
Sched_PrintSchedTrace,
Sched_PrintSchedGraphs,
};
extern cl::Enum<SchedDebugLevel_t> SchedDebugLevel;
//---------------------------------------------------------------------------
// Function: instrIsFeasible
//
// Purpose:
// Used by the priority analysis to filter out instructions
// that are not feasible to issue in the current cycle.
// Should only be used during schedule construction..
//---------------------------------------------------------------------------
bool instrIsFeasible(const SchedulingManager &S, MachineOpCode opCode);
struct NodeDelayPair {
const SchedGraphNode* node;
cycles_t delay;
NodeDelayPair(const SchedGraphNode* n, cycles_t d) : node(n), delay(d) {}
inline bool operator<(const NodeDelayPair& np) { return delay < np.delay; }
};
inline bool
NDPLessThan(const NodeDelayPair* np1, const NodeDelayPair* np2)
{
return np1->delay < np2->delay;
}
class NodeHeap: public std::list<NodeDelayPair*>, public NonCopyable {
public:
typedef std::list<NodeDelayPair*>::iterator iterator;
typedef std::list<NodeDelayPair*>::const_iterator const_iterator;
public:
NodeHeap() : _size(0) {}
inline unsigned size() const { return _size; }
const SchedGraphNode* getNode (const_iterator i) const { return (*i)->node; }
cycles_t getDelay(const_iterator i) const { return (*i)->delay;}
inline void makeHeap() {
// make_heap(begin(), end(), NDPLessThan);
}
inline iterator findNode(const SchedGraphNode* node) {
for (iterator I=begin(); I != end(); ++I)
if (getNode(I) == node)
return I;
return end();
}
inline void removeNode (const SchedGraphNode* node) {
iterator ndpPtr = findNode(node);
if (ndpPtr != end())
{
delete *ndpPtr;
erase(ndpPtr);
--_size;
}
};
void insert(const SchedGraphNode* node, cycles_t delay) {
NodeDelayPair* ndp = new NodeDelayPair(node, delay);
if (_size == 0 || front()->delay < delay)
push_front(ndp);
else
{
iterator I=begin();
for ( ; I != end() && getDelay(I) >= delay; ++I)
;
std::list<NodeDelayPair*>::insert(I, ndp);
}
_size++;
}
private:
unsigned int _size;
};
class SchedPriorities: public NonCopyable {
public:
/*ctor*/ SchedPriorities (const Method* method,
const SchedGraph* _graph);
// This must be called before scheduling begins.
void initialize ();
cycles_t getTime () const { return curTime; }
cycles_t getEarliestReadyTime () const { return earliestReadyTime; }
unsigned getNumReady () const { return candsAsHeap.size(); }
bool nodeIsReady (const SchedGraphNode* node) const {
return (candsAsSet.find(node) != candsAsSet.end());
}
void issuedReadyNodeAt (cycles_t curTime,
const SchedGraphNode* node);
void insertReady (const SchedGraphNode* node);
void updateTime (cycles_t /*unused*/);
const SchedGraphNode* getNextHighest (const SchedulingManager& S,
cycles_t curTime);
// choose next highest priority instr
private:
typedef NodeHeap::iterator candIndex;
private:
cycles_t curTime;
const SchedGraph* graph;
MethodLiveVarInfo methodLiveVarInfo;
std::hash_map<const MachineInstr*, bool> lastUseMap;
std::vector<cycles_t> nodeDelayVec;
std::vector<cycles_t> earliestForNode;
cycles_t earliestReadyTime;
NodeHeap candsAsHeap; // candidate nodes, ready to go
std::hash_set<const SchedGraphNode*> candsAsSet;//same entries as candsAsHeap,
// but as set for fast lookup
std::vector<candIndex> mcands; // holds pointers into cands
candIndex nextToTry; // next cand after the last
// one tried in this cycle
int chooseByRule1 (std::vector<candIndex>& mcands);
int chooseByRule2 (std::vector<candIndex>& mcands);
int chooseByRule3 (std::vector<candIndex>& mcands);
void findSetWithMaxDelay (std::vector<candIndex>& mcands,
const SchedulingManager& S);
void computeDelays (const SchedGraph* graph);
void initializeReadyHeap (const SchedGraph* graph);
bool instructionHasLastUse (MethodLiveVarInfo& methodLiveVarInfo,
const SchedGraphNode* graphNode);
// NOTE: The next two return references to the actual vector entries.
// Use with care.
cycles_t& getNodeDelayRef (const SchedGraphNode* node) {
assert(node->getNodeId() < nodeDelayVec.size());
return nodeDelayVec[node->getNodeId()];
}
cycles_t& getEarliestForNodeRef (const SchedGraphNode* node) {
assert(node->getNodeId() < earliestForNode.size());
return earliestForNode[node->getNodeId()];
}
};
inline void SchedPriorities::updateTime(cycles_t c) {
curTime = c;
nextToTry = candsAsHeap.begin();
mcands.clear();
}
inline std::ostream &operator<<(std::ostream &os, const NodeDelayPair* nd) {
return os << "Delay for node " << nd->node->getNodeId()
<< " = " << (long)nd->delay << "\n";
}
#endif
|
