Bugfix in Makefile.
[Faustine.git] / interpretor / faust-0.9.47mr3 / compiler / parallelize / loop.cpp
1 #include "loop.hh"
2 extern bool gVectorSwitch;
3 extern bool gOpenMPSwitch;
4 extern bool gOpenMPLoop;
5
6 using namespace std;
7
8 /**
9 * Print n tabs (for indentation purpose)
10 * @param n number of tabs to print
11 * @param fout output stream
12 */
13 static void tab (int n, ostream& fout)
14 {
15 fout << '\n';
16 while (n--) fout << '\t';
17 }
18
19
20 /**
21 * Print a list of lines
22 * @param n number of tabs of indentation
23 * @param lines list of lines to be printed
24 * @param fout output stream
25 */
26 static void printlines (int n, list<string>& lines, ostream& fout)
27 {
28 list<string>::iterator s;
29 for (s = lines.begin(); s != lines.end(); s++) {
30 tab(n, fout); fout << *s;
31 }
32 }
33
34
35 /**
36 * Create a recursive loop
37 * @param recsymbol the recursive symbol defined in this loop
38 * @param encl the enclosing loop
39 * @param size the number of iterations of the loop
40 */
41 Loop::Loop(Tree recsymbol, Loop* encl, const string& size)
42 : fIsRecursive(true), fRecSymbolSet(singleton(recsymbol)), fEnclosingLoop(encl), fSize(size), fOrder(-1), fIndex(-1), fUseCount(0), fPrinted(0)
43 {}
44
45
46 /**
47 * Create a non recursive loop
48 * @param encl the enclosing loop
49 * @param size the number of iterations of the loop
50 */
51 Loop::Loop(Loop* encl, const string& size)
52 : fIsRecursive(false), fRecSymbolSet(nil), fEnclosingLoop(encl), fSize(size), fOrder(-1), fIndex(-1), fUseCount(0), fPrinted(0)
53 {}
54
55
56 /**
57 * A loop with recursive dependencies can't be run alone.
58 * It must be included into another loop.
59 * returns true is this loop has recursive dependencies
60 * and must be included in an enclosing loop
61 */
62
63 bool Loop::hasRecDependencyIn(Tree S)
64 {
65 Loop* l = this;
66 while ( l && isNil(setIntersection(l->fRecSymbolSet,S)) ) l=l->fEnclosingLoop;
67 return l != 0;
68 }
69
70 /**
71 * Test if a loop is empty that is if it contains no lines of code).
72 * @return true if the loop is empty
73 */
74 bool Loop::isEmpty()
75 {
76 return fPreCode.empty() && fExecCode.empty() && fPostCode.empty() && (fExtraLoops.begin()==fExtraLoops.end());
77 }
78
79 /**
80 * Add a line of pre code (begin of the loop)
81 */
82 void Loop::addPreCode (const string& str)
83 {
84 // cerr << this << "->addExecCode " << str << endl;
85 fPreCode.push_back(str);
86 }
87
88 /**
89 * Add a line of exec code
90 */
91 void Loop::addExecCode (const string& str)
92 {
93 // cerr << this << "->addExecCode " << str << endl;
94 fExecCode.push_back(str);
95 }
96
97
98 /**
99 * Add a line of post exec code (end of the loop)
100 */
101 void Loop::addPostCode (const string& str)
102 {
103 // cerr << this << "->addPostCode " << str << endl;
104 fPostCode.push_front(str);
105 }
106
107
108 /**
109 * Absorb a loop by copying its recursive dependencies, its loop dependencies
110 * and its lines of exec and post exec code.
111 * @param l the Loop to be absorbed
112 */
113 void Loop::absorb (Loop* l)
114 {
115 // the loops must have the same number of iterations
116 assert(fSize == l->fSize);
117 fRecSymbolSet = setUnion(fRecSymbolSet, l->fRecSymbolSet);
118
119 // update loop dependencies by adding those from the absorbed loop
120 fBackwardLoopDependencies.insert(l->fBackwardLoopDependencies.begin(), l->fBackwardLoopDependencies.end());
121
122 // add the line of code of the absorbed loop
123 fPreCode.insert(fPreCode.end(), l->fPreCode.begin(), l->fPreCode.end());
124 fExecCode.insert(fExecCode.end(), l->fExecCode.begin(), l->fExecCode.end());
125 fPostCode.insert(fPostCode.begin(), l->fPostCode.begin(), l->fPostCode.end());
126 }
127
128
129 /**
130 * Print a loop (unless it is empty)
131 * @param n number of tabs of indentation
132 * @param fout output stream
133 */
134 void Loop::println(int n, ostream& fout)
135 {
136 for (list<Loop*>::const_iterator s = fExtraLoops.begin(); s != fExtraLoops.end(); s++) {
137 (*s)->println(n, fout);
138 }
139
140 if (fPreCode.size()+fExecCode.size()+fPostCode.size() > 0) {
141 /* if (gVectorSwitch) {
142 tab(n,fout);
143 fout << ((fIsRecursive) ? "// recursive loop" : "// vectorizable loop");
144 }*/
145
146 tab(n,fout); fout << "// LOOP " << this ;
147 if (fPreCode.size()>0) {
148 tab(n,fout); fout << "// pre processing";
149 printlines(n, fPreCode, fout);
150 }
151
152 tab(n,fout); fout << "// exec code";
153 tab(n,fout); fout << "for (int i=0; i<" << fSize << "; i++) {";
154 printlines(n+1, fExecCode, fout);
155 tab(n,fout); fout << "}";
156
157 if (fPostCode.size()>0) {
158 tab(n,fout); fout << "// post processing";
159 printlines(n, fPostCode, fout);
160 }
161 tab(n,fout);
162 }
163 }
164
165
166 /**
167 * Print a parallel loop (unless it is empty). Should be called only for loop
168 * without pre and post processing
169 * @param n number of tabs of indentation
170 * @param fout output stream
171 */
172 void Loop::printParLoopln(int n, ostream& fout)
173 {
174 for (list<Loop*>::const_iterator s = fExtraLoops.begin(); s != fExtraLoops.end(); s++) {
175 tab(n,fout); fout << "#pragma omp single";
176 tab(n,fout); fout << "{";
177 (*s)->println(n+1, fout);
178 tab(n,fout); fout << "}";
179 }
180
181 if (fPreCode.size()+fExecCode.size()+fPostCode.size() > 0) {
182
183 tab(n,fout); fout << "// LOOP " << this ;
184 if (fPreCode.size()>0) {
185 tab(n,fout); fout << "#pragma omp single";
186 tab(n,fout); fout << "{";
187 tab(n+1,fout); fout << "// pre processing";
188 printlines(n+1, fPreCode, fout);
189 tab(n,fout); fout << "}";
190 }
191
192 tab(n,fout); fout << "// exec code";
193 tab(n,fout); fout << "#pragma omp for";
194 tab(n,fout); fout << "for (int i=0; i<" << fSize << "; i++) {";
195 printlines(n+1, fExecCode, fout);
196 tab(n,fout); fout << "}";
197
198 if (fPostCode.size()>0) {
199 tab(n,fout); fout << "#pragma omp single";
200 tab(n,fout); fout << "{";
201 tab(n+1,fout); fout << "// post processing";
202 printlines(n+1, fPostCode, fout);
203 tab(n,fout); fout << "}";
204 }
205 tab(n,fout);
206 }
207 }
208
209 /**
210 * Print a single loop (unless it is empty)
211 * @param n number of tabs of indentation
212 * @param fout output stream
213 */
214 void Loop::printoneln(int n, ostream& fout)
215 {
216 if (fPreCode.size()+fExecCode.size()+fPostCode.size() > 0) {
217 /* if (gVectorSwitch) {
218 tab(n,fout);
219 fout << ((fIsRecursive) ? "// recursive loop" : "// vectorizable loop");
220 }*/
221
222 tab(n,fout); fout << "for (int i=0; i<" << fSize << "; i++) {";
223 if (fPreCode.size()>0) {
224 tab(n+1,fout); fout << "// pre processing";
225 printlines(n+1, fPreCode, fout);
226 }
227 printlines(n+1, fExecCode, fout);
228 if (fPostCode.size()>0) {
229 tab(n+1,fout); fout << "// post processing";
230 printlines(n+1, fPostCode, fout);
231 }
232 tab(n,fout); fout << "}";
233 }
234 }
235
236 //-------------------------------------------------------
237 void Loop::concat(Loop* l)
238 {
239 assert(l->fUseCount == 1);
240 assert(fBackwardLoopDependencies.size() == 1);
241 assert((*fBackwardLoopDependencies.begin()) == l);
242
243 fExtraLoops.push_front(l);
244 fBackwardLoopDependencies = l->fBackwardLoopDependencies;
245 }