Merge branch 'newtree'
[Faustine.git] / interpretor / preprocessor / faust-0.9.47mr3 / compiler / generator / compile_vect.cpp
1 /************************************************************************
2 ************************************************************************
3 FAUST compiler
4 Copyright (C) 2003-2004 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
23
24 #include "compile_vect.hh"
25 #include "floats.hh"
26 #include "ppsig.hh"
27
28 extern int gVecSize;
29
30 void VectorCompiler::compileMultiSignal (Tree L)
31 {
32 //contextor recursivness(0);
33 L = prepare(L); // optimize, share and annotate expression
34
35 for (int i = 0; i < fClass->inputs(); i++) {
36 fClass->addZone3(subst("$1* input$0 = &input[$0][index];", T(i), xfloat()));
37 }
38 for (int i = 0; i < fClass->outputs(); i++) {
39 fClass->addZone3(subst("$1* output$0 = &output[$0][index];", T(i), xfloat()));
40 }
41
42 fClass->addSharedDecl("fullcount");
43 fClass->addSharedDecl("input");
44 fClass->addSharedDecl("output");
45
46 for (int i = 0; isList(L); L = tl(L), i++) {
47 Tree sig = hd(L);
48 fClass->openLoop("count");
49 fClass->addExecCode(subst("output$0[i] = $2$1;", T(i), CS(sig), xcast()));
50 fClass->closeLoop(sig);
51 }
52
53 generateUserInterfaceTree(prepareUserInterfaceTree(fUIRoot));
54 generateMacroInterfaceTree("", prepareUserInterfaceTree(fUIRoot));
55 if (fDescription) {
56 fDescription->ui(prepareUserInterfaceTree(fUIRoot));
57 }
58 }
59
60
61 /**
62 * Compile a signal
63 * @param sig the signal expression to compile.
64 * @return the C code translation of sig as a string
65 */
66 string VectorCompiler::CS (Tree sig)
67 {
68 string code;
69 //cerr << "ENTER VectorCompiler::CS : "<< ppsig(sig) << endl;
70 if (!getCompiledExpression(sig, code)) {
71 code = generateCode(sig);
72 //cerr << "CS : " << code << " for " << ppsig(sig) << endl;
73 setCompiledExpression(sig, code);
74 } else {
75 // we require an already compiled expression
76 // therefore we must update the dependencies of
77 // the current loop
78 int i;
79 Tree x, d, r;
80 Loop* ls;
81 Loop* tl = fClass->topLoop();
82
83 if (fClass->getLoopProperty(sig,ls)) {
84 // sig has a loop property
85 //cerr << "CASE SH : fBackwardLoopDependencies.insert : " << tl << " --depend(A)son--> " << ls << endl;
86 tl->fBackwardLoopDependencies.insert(ls);
87
88 } else if (isSigFixDelay(sig, x, d) && fClass->getLoopProperty(x,ls)) {
89 //cerr << "CASE DL : fBackwardLoopDependencies.insert : " << tl << " --depend(B)son--> " << ls << endl;
90 tl->fBackwardLoopDependencies.insert(ls);
91
92 } else if (isSigFixDelay(sig, x, d) && isProj(x, &i, r) && fClass->getLoopProperty(r,ls)) {
93 //cerr << "CASE DR : fBackwardLoopDependencies.insert : " << tl << " --depend(B)son--> " << ls << endl;
94 tl->fBackwardLoopDependencies.insert(ls);
95
96 } else if (isProj(sig, &i, r) && fClass->getLoopProperty(r,ls)) {
97 //cerr << "CASE R* : fBackwardLoopDependencies.insert : " << tl << " --depend(B)son--> " << ls << endl;
98 tl->fBackwardLoopDependencies.insert(ls);
99
100 } else {
101 if (isProj(sig, &i, r)) {
102 //cerr << "SYMBOL RECURSIF EN COURS ??? " << *r << endl;
103 } else if (getCertifiedSigType(sig)->variability()<kSamp) {
104 //cerr << "SLOW EXPRESSION " << endl;
105 } else {
106 //cerr << "Expression absorbée" << *sig << endl;
107 }
108
109 }
110 }
111 //cerr << "EXIT VectorCompiler::CS : "<< ppsig(sig) << "---code---> " << code << endl;
112 return code;
113 }
114
115 string VectorCompiler::generateCode (Tree sig)
116 {
117 generateCodeRecursions(sig);
118 return generateCodeNonRec(sig);
119 }
120
121 void VectorCompiler::generateCodeRecursions (Tree sig)
122 {
123 Tree id, body;
124 string code;
125 //cerr << "VectorCompiler::generateCodeRecursions( " << ppsig(sig) << " )" << endl;
126 if (getCompiledExpression(sig, code)) {
127 //cerr << "** ALREADY VISITED : " << code << " ===> " << ppsig(sig) << endl;
128 return;
129 } else if( isRec(sig, id, body) ) {
130 //cerr << "we have a recursive expression non compiled yet : " << ppsig(sig) << endl;
131 setCompiledExpression(sig, "[RecursionVisited]");
132 fClass->openLoop(sig, "count");
133 generateRec(sig, id, body);
134 fClass->closeLoop(sig);
135 } else {
136 // we go down the expression
137 vector<Tree> subsigs;
138 int n = getSubSignals(sig, subsigs, false);
139 for (int i=0; i<n; i++) { generateCodeRecursions(subsigs[i]); }
140 }
141 }
142
143 string VectorCompiler::generateCodeNonRec (Tree sig)
144 {
145 string code;
146 if (getCompiledExpression(sig, code)) {
147 // already visited
148 return code;
149 } else {
150 //cerr << "VectorCompiler::generateCodeNonRec( " << ppsig(sig) << " )" << endl;
151 code = generateLoopCode(sig);
152 setCompiledExpression(sig, code);
153 return code;
154 }
155 }
156
157 /**
158 * Compile a signal
159 * @param sig the signal expression to compile.
160 * @return the C code translation of sig as a string
161 */
162 string VectorCompiler::generateLoopCode (Tree sig)
163 {
164 int i;
165 Tree x;
166 Loop* l;
167
168 l = fClass->topLoop();
169 assert(l);
170 //cerr << "VectorCompiler::OLDgenerateCode " << ppsig(sig) << endl;
171 if (needSeparateLoop(sig)) {
172 // we need a separate loop unless it's an old recursion
173 if (isProj(sig, &i, x)) {
174 // projection of a recursive group x
175 if (l->hasRecDependencyIn(singleton(x))) {
176 // x is already in the loop stack
177 return ScalarCompiler::generateCode(sig);
178 } else {
179 // x must be defined
180 fClass->openLoop(x, "count");
181 string c = ScalarCompiler::generateCode(sig);
182 fClass->closeLoop(sig);
183 return c;
184 }
185 } else {
186 fClass->openLoop("count");
187 string c = ScalarCompiler::generateCode(sig);
188 fClass->closeLoop(sig);
189 return c;
190 }
191 } else {
192 return ScalarCompiler::generateCode(sig);
193 }
194 }
195
196
197 /**
198 * Generate cache code for a signal if needed
199 * @param sig the signal expression.
200 * @param exp the corresponding C code.
201 * @return the cached C code
202 */
203 string VectorCompiler::generateCacheCode(Tree sig, const string& exp)
204 {
205 string vname, ctype;
206 int sharing = getSharingCount(sig);
207 Type t = getCertifiedSigType(sig);
208 Occurences* o = fOccMarkup.retrieve(sig);
209 int d = o->getMaxDelay();
210
211 if (t->variability() < kSamp) {
212 if (d==0) {
213 // non-sample, not delayed : same as scalar cache
214 return ScalarCompiler::generateCacheCode(sig,exp);
215
216 } else {
217 // it is a non-sample expressions but used delayed
218 // we need a delay line
219 getTypedNames(getCertifiedSigType(sig), "Vec", ctype, vname);
220 if ((sharing > 1) && !verySimple(sig)) {
221 // first cache this expression because it
222 // it is shared and complex
223 string cachedexp = generateVariableStore(sig, exp);
224 generateDelayLine(ctype, vname, d, cachedexp);
225 setVectorNameProperty(sig, vname);
226 return cachedexp;
227 } else {
228 // no need to cache this expression because
229 // it is either not shared or very simple
230 generateDelayLine(ctype, vname, d, exp);
231 setVectorNameProperty(sig, vname);
232 return exp;
233 }
234 }
235 } else {
236 // sample-rate signal
237 if (d > 0) {
238 // used delayed : we need a delay line
239 getTypedNames(getCertifiedSigType(sig), "Yec", ctype, vname);
240 generateDelayLine(ctype, vname, d, exp);
241 setVectorNameProperty(sig, vname);
242
243 if (verySimple(sig)) {
244 return exp;
245 } else {
246 if (d < gMaxCopyDelay) {
247 return subst("$0[i]", vname);
248 } else {
249 // we use a ring buffer
250 string mask = T(pow2limit(d + gVecSize)-1);
251 return subst("$0[($0_idx+i) & $1]", vname, mask);
252 }
253 }
254 } else {
255 // not delayed
256 if ( sharing > 1 && ! verySimple(sig) ) {
257 // shared and not simple : we need a vector
258 // cerr << "ZEC : " << ppsig(sig) << endl;
259 getTypedNames(getCertifiedSigType(sig), "Zec", ctype, vname);
260 generateDelayLine(ctype, vname, d, exp);
261 setVectorNameProperty(sig, vname);
262 return subst("$0[i]", vname);
263 } else {
264 // not shared or simple : no cache needed
265 return exp;
266 }
267 }
268 }
269 }
270
271 /**
272 * Test if a signal need to be compiled in a separate loop.
273 * @param sig the signal expression to test.
274 * @return true if a separate loop is needed
275 */
276 bool VectorCompiler::needSeparateLoop(Tree sig)
277 {
278 Occurences* o = fOccMarkup.retrieve(sig);
279 Type t = getCertifiedSigType(sig);
280 int c = getSharingCount(sig);
281 bool b;
282
283 int i;
284 Tree x,y;
285
286
287 if (o->getMaxDelay()>0) {
288 //cerr << "DLY "; // delayed expressions require a separate loop
289 b = true;
290 } else if (verySimple(sig) || t->variability()<kSamp) {
291 b = false; // non sample computation never require a loop
292 } else if (isSigFixDelay(sig, x, y)) {
293 b = false; //
294 } else if (isProj(sig, &i ,x)) {
295 //cerr << "REC "; // recursive expressions require a separate loop
296 b = true;
297 } else if (c > 1) {
298 //cerr << "SHA(" << c << ") "; // expressions used several times required a separate loop
299 b = true;
300 } else {
301 // sample expressions that are not recursive, not delayed
302 // and not shared, doesn't require a separate loop.
303 b = false;
304 }
305 /* if (b) {
306 cerr << "Separate Loop for " << ppsig(sig) << endl;
307 } else {
308 cerr << "Same Loop for " << ppsig(sig) << endl;
309 }*/
310 return b;
311 }
312
313 void VectorCompiler::generateDelayLine(const string& ctype, const string& vname, int mxd, const string& exp)
314 {
315 if (mxd == 0) {
316 vectorLoop(ctype, vname, exp);
317 } else {
318 dlineLoop(ctype, vname, mxd, exp);
319 }
320 }
321
322 string VectorCompiler::generateVariableStore(Tree sig, const string& exp)
323 {
324 Type t = getCertifiedSigType(sig);
325
326 if (getCertifiedSigType(sig)->variability() == kSamp) {
327 string vname, ctype;
328 getTypedNames(t, "Vector", ctype, vname);
329 vectorLoop(ctype, vname, exp);
330 return subst("$0[i]", vname);
331 } else {
332 return ScalarCompiler::generateVariableStore(sig, exp);
333 }
334 }
335
336
337 /**
338 * Generate code for accessing a delayed signal. The generated code depend of
339 * the maximum delay attached to exp and the gLessTempSwitch.
340 */
341
342 string VectorCompiler::generateFixDelay (Tree sig, Tree exp, Tree delay)
343 {
344 int mxd, d;
345 string vecname;
346
347 //cerr << "VectorCompiler::generateFixDelay " << ppsig(sig) << endl;
348
349 CS(exp); // ensure exp is compiled to have a vector name
350
351 mxd = fOccMarkup.retrieve(exp)->getMaxDelay();
352
353 if (! getVectorNameProperty(exp, vecname)) {
354 cerr << "ERROR no vector name for " << ppsig(exp) << endl;
355 exit(1);
356 }
357
358 if (mxd == 0) {
359 // not a real vector name but a scalar name
360 return subst("$0[i]", vecname);
361
362 } else if (mxd < gMaxCopyDelay){
363 if (isSigInt(delay, &d)) {
364 if (d == 0) {
365 return subst("$0[i]", vecname);
366 } else {
367 return subst("$0[i-$1]", vecname, T(d));
368 }
369 } else {
370 return subst("$0[i-$1]", vecname, CS(delay));
371 }
372
373 } else {
374
375 // long delay : we use a ring buffer of size 2^x
376 int N = pow2limit( mxd+gVecSize );
377
378 if (isSigInt(delay, &d)) {
379 if (d == 0) {
380 return subst("$0[($0_idx+i)&$1]", vecname, T(N-1));
381 } else {
382 return subst("$0[($0_idx+i-$2)&$1]", vecname, T(N-1), T(d));
383 }
384 } else {
385 return subst("$0[($0_idx+i-$2)&$1]", vecname, T(N-1), CS(delay));
386 }
387 }
388 }
389
390
391 /**
392 * Generate code for the delay mecchanism. The generated code depend of the
393 * maximum delay attached to exp and the "less temporaries" switch
394 */
395
396 string VectorCompiler::generateDelayVec(Tree sig, const string& exp, const string& ctype, const string& vname, int mxd)
397 {
398 // it is a non-sample but used delayed
399 // we need a delay line
400 generateDelayLine(ctype, vname, mxd, exp);
401 setVectorNameProperty(sig, vname);
402 if (verySimple(sig)) {
403 return exp;
404 } else {
405 return subst("$0[i]", vname);
406 }
407 }
408
409 #if 0
410 static int pow2limit(int x)
411 {
412 int n = 2;
413 while (n < x) { n = 2*n; }
414 return n;
415 }
416 #endif
417
418 /**
419 * Generate the code for a (short) delay line
420 * @param k the c++ class where the delay line will be placed.
421 * @param l the loop where the code will be placed.
422 * @param tname the name of the C++ type (float or int)
423 * @param dlname the name of the delay line (vector) to be used.
424 * @param delay the maximum delay
425 * @param cexp the content of the signal as a C++ expression
426 */
427 void VectorCompiler::vectorLoop (const string& tname, const string& vecname, const string& cexp)
428 {
429 // -- declare the vector
430 fClass->addSharedDecl(vecname);
431
432 // -- variables moved as class fields...
433 fClass->addZone1(subst("$0 \t$1[$2];", tname, vecname, T(gVecSize)));
434
435 // -- compute the new samples
436 fClass->addExecCode(subst("$0[i] = $1;", vecname, cexp));
437 }
438
439
440 /**
441 * Generate the code for a (short) delay line
442 * @param k the c++ class where the delay line will be placed.
443 * @param l the loop where the code will be placed.
444 * @param tname the name of the C++ type (float or int)
445 * @param dlname the name of the delay line (vector) to be used.
446 * @param delay the maximum delay
447 * @param cexp the content of the signal as a C++ expression
448 */
449 void VectorCompiler::dlineLoop (const string& tname, const string& dlname, int delay, const string& cexp)
450 {
451 if (delay < gMaxCopyDelay) {
452
453 // Implementation of a copy based delayline
454
455 // create names for temporary and permanent storage
456 string buf = subst("$0_tmp", dlname);
457 string pmem= subst("$0_perm", dlname);
458
459 // constraints delay size to be multiple of 4
460 delay = (delay+3)&-4;
461
462 // allocate permanent storage for delayed samples
463 string dsize = T(delay);
464 fClass->addDeclCode(subst("$0 \t$1[$2];", tname, pmem, dsize));
465
466 // init permanent memory
467 fClass->addInitCode(subst("for (int i=0; i<$1; i++) $0[i]=0;", pmem, dsize));
468
469 // compute method
470
471 // -- declare a buffer and a "shifted" vector
472 fClass->addSharedDecl(buf);
473
474 // -- variables moved as class fields...
475 fClass->addZone1(subst("$0 \t$1[$2+$3];", tname, buf, T(gVecSize), dsize));
476
477 fClass->addFirstPrivateDecl(dlname);
478 fClass->addZone2(subst("$0* \t$1 = &$2[$3];", tname, dlname, buf, dsize));
479
480 // -- copy the stored samples to the delay line
481 fClass->addPreCode(subst("for (int i=0; i<$2; i++) $0[i]=$1[i];", buf, pmem, dsize));
482
483 // -- compute the new samples
484 fClass->addExecCode(subst("$0[i] = $1;", dlname, cexp));
485
486 // -- copy back to stored samples
487 fClass->addPostCode(subst("for (int i=0; i<$2; i++) $0[i]=$1[count+i];", pmem, buf, dsize));
488
489 } else {
490
491 // Implementation of a ring-buffer delayline
492
493 // the size should be large enough and aligned on a power of two
494 delay = pow2limit(delay + gVecSize);
495 string dsize = T(delay);
496 string mask = T(delay-1);
497
498 // create names for temporary and permanent storage
499 string idx = subst("$0_idx", dlname);
500 string idx_save = subst("$0_idx_save", dlname);
501
502 // allocate permanent storage for delayed samples
503 fClass->addDeclCode(subst("$0 \t$1[$2];", tname, dlname, dsize));
504 fClass->addDeclCode(subst("int \t$0;", idx));
505 fClass->addDeclCode(subst("int \t$0;", idx_save));
506
507 // init permanent memory
508 fClass->addInitCode(subst("for (int i=0; i<$1; i++) $0[i]=0;", dlname, dsize));
509 fClass->addInitCode(subst("$0 = 0;", idx));
510 fClass->addInitCode(subst("$0 = 0;", idx_save));
511
512 // -- update index
513 fClass->addPreCode(subst("$0 = ($0+$1)&$2;", idx, idx_save, mask));
514
515 // -- compute the new samples
516 fClass->addExecCode(subst("$0[($2+i)&$3] = $1;", dlname, cexp, idx, mask));
517
518 // -- save index
519 fClass->addPostCode(subst("$0 = count;", idx_save));
520 }
521 }
522