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
|
// ModuloScheduling.h -------------------------------------------*- C++ -*-===//
//
// This header defines the the classes ModuloScheduling and
// ModuloSchedulingSet's structure
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_CODEGEN_MODULOSCHEDULING_H
#define LLVM_CODEGEN_MODULOSCHEDULING_H
#include "ModuloSchedGraph.h"
#include <iostream>
#include <vector>
//#define DEBUG_PRINT(x) x
#define DEBUG_PRINT(x)
// for debug information selecton
enum ModuloSchedDebugLevel_t {
ModuloSchedDebugLevel_NoDebugInfo,
ModuloSchedDebugLevel_PrintSchedule,
ModuloSchedDebugLevel_PrintScheduleProcess,
};
class ModuloScheduling: NonCopyable {
private:
typedef std::vector<ModuloSchedGraphNode*> NodeVec;
typedef std::vector<std::vector<unsigned> > Resources;
// The graph to feed in
ModuloSchedGraph &graph;
const TargetMachine ⌖
// The BasicBlock to be scheduled
BasicBlock *bb;
// Iteration Interval
// FIXME: II may be a better name for its meaning
unsigned II;
// The vector containing the nodes which have been scheduled
NodeVec nodeScheduled;
// The remaining unscheduled nodes
const NodeVec &oNodes;
// The machine resource table
std::vector<std::vector<std::pair<int,int> > > resourceTable;
///the schedule( with many schedule stage)
std::vector<std::vector<ModuloSchedGraphNode*> > schedule;
///the kernel(core) schedule(length = II)
std::vector<std::vector<ModuloSchedGraphNode*> > coreSchedule;
typedef BasicBlock::InstListType InstListType;
typedef std::vector<std::vector<ModuloSchedGraphNode*> > vvNodeType;
public:
ModuloScheduling(ModuloSchedGraph & _graph):
graph(_graph), target(graph.getTarget()), oNodes(graph.getONodes())
{
II = graph.getMII();
bb = graph.getBasicBlock();
instrScheduling();
};
~ModuloScheduling() {};
static bool
printSchedule() {
//return ModuloScheduling::DebugLevel >= DebugLevel_PrintSchedule;
return true;
}
static bool
printScheduleProcess() {
//return DebugLevel >= DebugLevel_PrintScheduleProcess;
return true;
}
// The method to compute schedule and instert epilogue and prologue
void instrScheduling();
// Debug functions:
// Dump the schedule and core schedule
void dumpScheduling();
void dumpFinalSchedule();
// Dump the input vector of nodes
// sch: the input vector of nodes
void dumpSchedule(std::vector<std::vector<ModuloSchedGraphNode*> > sch);
// Dump the resource usage table
void dumpResourceUsageTable();
//*******************internal functions*******************************
private:
//clear memory from the last round and initialize if necessary
void clearInitMem(const TargetSchedInfo&);
//compute schedule and coreSchedule with the current II
bool computeSchedule();
BasicBlock *getSuccBB(BasicBlock *);
BasicBlock *getPredBB(BasicBlock *);
void constructPrologue(BasicBlock *prologue);
void constructKernel(BasicBlock *prologue,
BasicBlock *kernel,
BasicBlock *epilogue);
void constructEpilogue(BasicBlock *epilogue, BasicBlock *succ_bb);
// update the resource table at the startCycle
// vec: the resouce usage
// startCycle: the start cycle the resouce usage is
void updateResourceTable(std::vector<std::vector<unsigned> > vec,
int startCycle);
// un-do the update in the resource table in the startCycle
// vec: the resouce usage
// startCycle: the start cycle the resouce usage is
void undoUpdateResourceTable(std::vector<std::vector<unsigned> > vec,
int startCycle);
// return whether the resourcetable has negative element
// this function is called after updateResouceTable() to determine whether a
// node can be scheduled at certain cycle
bool resourceTableNegative();
// try to Schedule the node starting from start to end cycle(inclusive)
// if it can be scheduled, put it in the schedule and update nodeScheduled
// node: the node to be scheduled
// start: start cycle
// end : end cycle
// nodeScheduled: a vector storing nodes which has been scheduled
bool ScheduleNode(ModuloSchedGraphNode * node, unsigned start,
unsigned end, NodeVec &nodeScheduled);
//each instruction has a memory of the latest clone instruction
//the clone instruction can be get using getClone()
//this function clears the memory, i.e. getClone() after calling this function
//returns null
void clearCloneMemory();
//this fuction make a clone of this input Instruction and update the clone
//memory
//inst: the instrution to be cloned
Instruction *cloneInstSetMemory(Instruction *inst);
//this function update each instrutions which uses ist as its operand
//after update, each instruction will use ist's clone as its operand
void updateUseWithClone(Instruction * ist);
};
class ModuloSchedulingSet:
NonCopyable {
private:
//the graphSet to feed in
ModuloSchedGraphSet & graphSet;
public:
//constructor
//Scheduling graph one by one
ModuloSchedulingSet(ModuloSchedGraphSet _graphSet): graphSet(_graphSet) {
for (unsigned i = 0; i < graphSet.size(); i++) {
ModuloSchedGraph & graph = *(graphSet[i]);
if (graph.isLoop(graph.getBasicBlock()))
ModuloScheduling ModuloScheduling(graph);
}
};
~ModuloSchedulingSet() {};
};
#endif
|
