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