interpreter/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