1 /************************************************************************
2 ************************************************************************
3 FAUST compiler
4 Copyright (C) 2003-2018 GRAME, Centre National de Creation Musicale
5 ---------------------------------------------------------------------
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2 of the License, or
9 (at your option) any later version.
10
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with this program; if not, write to the Free Software
18 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
19 ************************************************************************
20 ************************************************************************/
21
22 #include "loop.hh"
23 #include "Text.hh"
24 #include "global.hh"
25
26 using namespace std;
27
28 /**
29 * Print a list of lines.
30 * @param n number of tabs of indentation
31 * @param lines list of lines to be printed
32 * @param fout output stream
33 */
printlines(int n,list<Statement> & lines,ostream & fout)34 static void printlines(int n, list<Statement>& lines, ostream& fout)
35 {
36 list<Statement>::iterator s;
37 string ccond = "";
38 for (s = lines.begin(); s != lines.end(); s++) {
39 if (s->hasCondition(ccond)) {
40 tab(n, fout);
41 fout << s->code();
42 } else if (ccond == "") {
43 // debut d'une condition
44 ccond = s->condition();
45 tab(n, fout);
46 fout << "if (" << ccond << ") {";
47 n++;
48 tab(n, fout);
49 fout << s->code();
50 } else {
51 // fin précédente condition
52 n--;
53 tab(n, fout);
54 fout << "}";
55 // nouvelle condition courante
56 ccond = s->condition();
57 if (ccond != "") {
58 tab(n, fout);
59 fout << "if (" << ccond << ") {";
60 n++;
61 }
62 tab(n, fout);
63 fout << s->code();
64 }
65 }
66 if (ccond != "") {
67 n--;
68 tab(n, fout);
69 fout << "}";
70 }
71 }
72
73 /**
74 * Create a recursive loop.
75 * @param recsymbol the recursive symbol defined in this loop
76 * @param encl the enclosing loop
77 * @param size the number of iterations of the loop
78 */
Loop(Tree recsymbol,Loop * encl,const string & size)79 Loop::Loop(Tree recsymbol, Loop* encl, const string& size)
80 : fIsRecursive(true),
81 fRecSymbolSet(singleton(recsymbol)),
82 fEnclosingLoop(encl),
83 fSize(size),
84 fOrder(-1),
85 fIndex(-1),
86 fUseCount(0),
87 fPrinted(0)
88 {
89 }
90
91 /**
92 * Create a non recursive loop.
93 * @param encl the enclosing loop
94 * @param size the number of iterations of the loop
95 */
Loop(Loop * encl,const string & size)96 Loop::Loop(Loop* encl, const string& size)
97 : fIsRecursive(false),
98 fRecSymbolSet(gGlobal->nil),
99 fEnclosingLoop(encl),
100 fSize(size),
101 fOrder(-1),
102 fIndex(-1),
103 fUseCount(0),
104 fPrinted(0)
105 {
106 }
107
108 /**
109 * A loop with recursive dependencies can't be run alone.
110 * It must be included into another loop.
111 * returns true is this loop has recursive dependencies
112 * and must be included in an enclosing loop
113 */
114
hasRecDependencyIn(Tree S)115 bool Loop::hasRecDependencyIn(Tree S)
116 {
117 Loop* l = this;
118 while (l && isNil(setIntersection(l->fRecSymbolSet, S))) l = l->fEnclosingLoop;
119 return l != 0;
120 }
121
122 /**
123 * Test if a loop is empty that is if it contains no lines of code.
124 * @return true if the loop is empty
125 */
isEmpty()126 bool Loop::isEmpty()
127 {
128 return fPreCode.empty() && fExecCode.empty() && fPostCode.empty() && (fExtraLoops.begin() == fExtraLoops.end());
129 }
130
131 /**
132 * Add a line of pre code (begin of the loop)
133 */
addPreCode(const Statement & stmt)134 void Loop::addPreCode(const Statement& stmt)
135 {
136 // cerr << this << "->addExecCode " << str << endl;
137 fPreCode.push_back(stmt);
138 }
139
140 /**
141 * Add a line of exec code.
142 */
addExecCode(const Statement & stmt)143 void Loop::addExecCode(const Statement& stmt)
144 {
145 // cerr << this << "->addExecCode " << str << endl;
146 fExecCode.push_back(stmt);
147 }
148
149 /**
150 * Add a line of post exec code (end of the loop).
151 */
addPostCode(const Statement & stmt)152 void Loop::addPostCode(const Statement& stmt)
153 {
154 // cerr << this << "->addPostCode " << str << endl;
155 fPostCode.push_front(stmt);
156 }
157
158 /**
159 * Absorb a loop by copying its recursive dependencies, its loop dependencies
160 * and its lines of exec and post exec code.
161 * @param l the Loop to be absorbed
162 */
absorb(Loop * l)163 void Loop::absorb(Loop* l)
164 {
165 // the loops must have the same number of iterations
166 //cerr << "Loop absorbtion : " << this << " absorb " << l << endl;
167 faustassert(fSize == l->fSize);
168 fRecSymbolSet = setUnion(fRecSymbolSet, l->fRecSymbolSet);
169
170 // update loop dependencies by adding those from the absorbed loop
171 fBackwardLoopDependencies.insert(l->fBackwardLoopDependencies.begin(), l->fBackwardLoopDependencies.end());
172
173 // add the line of code of the absorbed loop
174 fPreCode.insert(fPreCode.end(), l->fPreCode.begin(), l->fPreCode.end());
175 fExecCode.insert(fExecCode.end(), l->fExecCode.begin(), l->fExecCode.end());
176 fPostCode.insert(fPostCode.begin(), l->fPostCode.begin(), l->fPostCode.end());
177 }
178
179 /**
180 * Print a loop (unless it is empty)
181 * @param n number of tabs of indentation
182 * @param fout output stream
183 */
println(int n,ostream & fout)184 void Loop::println(int n, ostream& fout)
185 {
186 for (Loop* l : fExtraLoops) {
187 l->println(n, fout);
188 }
189
190 tab(n, fout);
191 fout << "// Extra loops : ";
192 for (Loop* l : fExtraLoops) fout << l << " ";
193
194 tab(n, fout);
195 fout << "// Backward loops: ";
196 bool emptyflag = true;
197 for (Loop* l : fBackwardLoopDependencies) {
198 emptyflag = false;
199 fout << l << " ";
200 } ///< Loops that must be computed before this one
201 if (emptyflag) fout << "WARNING EMPTY";
202
203 tab(n, fout);
204 fout << "// Forward loops : ";
205 for (Loop* l : fForwardLoopDependencies) fout << l << " ";
206
207 tab(n, fout);
208 fout << "// " << ((fIsRecursive) ? "Recursive" : "Vectorizable") << " loop " << this;
209
210 if (fPreCode.size() + fExecCode.size() + fPostCode.size() > 0) {
211 if (fPreCode.size() > 0) {
212 tab(n, fout);
213 fout << "// pre processing";
214 printlines(n, fPreCode, fout);
215 }
216
217 tab(n, fout);
218 fout << "// exec code";
219 tab(n, fout);
220 fout << "for (int i=0; i<" << fSize << "; i++) {";
221 printlines(n + 1, fExecCode, fout);
222 tab(n, fout);
223 fout << "}";
224
225 if (fPostCode.size() > 0) {
226 tab(n, fout);
227 fout << "// post processing";
228 printlines(n, fPostCode, fout);
229 }
230 tab(n, fout);
231 } else {
232 fout << "// empty loop " << this;
233 }
234 }
235
236 /**
237 * Print a parallel loop (unless it is empty). Should be called only for loop.
238 * without pre and post processing
239 * @param n number of tabs of indentation
240 * @param fout output stream
241 */
printParLoopln(int n,ostream & fout)242 void Loop::printParLoopln(int n, ostream& fout)
243 {
244 for (list<Loop*>::const_iterator s = fExtraLoops.begin(); s != fExtraLoops.end(); s++) {
245 tab(n, fout);
246 fout << "#pragma omp single";
247 tab(n, fout);
248 fout << "{";
249 (*s)->println(n + 1, fout);
250 tab(n, fout);
251 fout << "}";
252 }
253
254 if (fPreCode.size() + fExecCode.size() + fPostCode.size() > 0) {
255 tab(n, fout);
256 fout << "// LOOP " << this;
257 if (fPreCode.size() > 0) {
258 tab(n, fout);
259 fout << "#pragma omp single";
260 tab(n, fout);
261 fout << "{";
262 tab(n + 1, fout);
263 fout << "// pre processing";
264 printlines(n + 1, fPreCode, fout);
265 tab(n, fout);
266 fout << "}";
267 }
268
269 tab(n, fout);
270 fout << "// exec code";
271 tab(n, fout);
272 fout << "#pragma omp for";
273 tab(n, fout);
274 fout << "for (int i=0; i<" << fSize << "; i++) {";
275 printlines(n + 1, fExecCode, fout);
276 tab(n, fout);
277 fout << "}";
278
279 if (fPostCode.size() > 0) {
280 tab(n, fout);
281 fout << "#pragma omp single";
282 tab(n, fout);
283 fout << "{";
284 tab(n + 1, fout);
285 fout << "// post processing";
286 printlines(n + 1, fPostCode, fout);
287 tab(n, fout);
288 fout << "}";
289 }
290 tab(n, fout);
291 }
292 }
293
294 /**
295 * Print a single loop (unless it is empty).
296 * @param n number of tabs of indentation
297 * @param fout output stream
298 */
printoneln(int n,ostream & fout)299 void Loop::printoneln(int n, ostream& fout)
300 {
301 if (fPreCode.size() + fExecCode.size() + fPostCode.size() > 0) {
302 tab(n, fout);
303 fout << "for (int i=0; i<" << fSize << "; i++) {";
304 if (fPreCode.size() > 0) {
305 tab(n + 1, fout);
306 fout << "// pre processing";
307 printlines(n + 1, fPreCode, fout);
308 }
309 printlines(n + 1, fExecCode, fout);
310 if (fPostCode.size() > 0) {
311 tab(n + 1, fout);
312 fout << "// post processing";
313 printlines(n + 1, fPostCode, fout);
314 }
315 tab(n, fout);
316 fout << "}";
317 }
318 }
319
320 //-------------------------------------------------------
concat(Loop * l)321 void Loop::concat(Loop* l)
322 {
323 faustassert(l->fUseCount == 1);
324 faustassert(fBackwardLoopDependencies.size() == 1);
325 faustassert((*fBackwardLoopDependencies.begin()) == l);
326
327 fExtraLoops.push_front(l);
328 fBackwardLoopDependencies = l->fBackwardLoopDependencies;
329 }
330