interpretor/preprocessor/faust-0.9.47mr3/compiler/signals/sigraterules.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 <stdio.h>
  25 #include <assert.h>
  26 #include <fstream>
  27 #include <time.h>
  28
  29
  30 #include "sigtype.hh"
  31 #include "sigprint.hh"
  32 #include "ppsig.hh"
  33 //#include "prim.hh"
  34 #include "prim2.hh"
  35 #include "xtended.hh"
  36 #include "recursivness.hh"
  37
  38 #include "sigtyperules.hh"
  39 #include "sigraterules.hh"
  40
  41
  42
  43 //--------------------------------------------------------------------------
  44 // Uncomment to activate type inference tracing
  45
  46 //#define TRACE(x) x
  47 #define TRACE(x) 0;
  48
  49
  50
  51
  52
  53 /**
  54
  55 ========================================== RATE INFERENCE =========================================
  56                                          [Public functions]
  57
  58
  59 */
  60
  61 /**************************************************************************************************
  62
  63                                         Internal prototypes
  64
  65  **************************************************************************************************/
  66
  67 static Tree inferreMultiRates(Tree lsig1, bool& success);
  68 static ostream&  printRateEnvironment(ostream& fout, Tree E);
  69 static ostream&  printRateEnvironmentList(ostream& fout, Tree LE);
  70 static void doInferreRate(Tree sig, int* rate, Tree& renv);
  71 static void inferreRate(Tree sig, int* rate, Tree& E);
  72 static Tree addToMultiRates(Tree E1, Tree LE, bool& success);
  73 static Tree addRecursiveSignals(Tree lsig);
  74 static Tree doAddRecursiveSignals(Tree sig, Tree accSig);
  75 static Tree flatRateEnvironmentList(Tree lre);
  76
  77 static int computeRate(Tree sig, Tree renv, property<int>& rateProperty);
  78
  79
  80
  81 /**************************************************************************************************
  82  **************************************************************************************************
  83  **************************************************************************************************
  84
  85                                         Public Functions
  86
  87  **************************************************************************************************
  88  **************************************************************************************************
  89  **************************************************************************************************/
  90
  91 /**
  92   * Inferre the rate of a list of signals.
  93   */
  94 Tree inferreMultiRates(Tree lsig1, bool& success)
  95 {
  96     vector<Tree>    sigs;
  97     vector<Tree>    envs;
  98     vector<int>     rates;
  99
 100     Tree lsig2 = addRecursiveSignals(lsig1);
 101     TRACE(cerr << "lsig2 = " << *lsig2 << endl);
 102
 103     while (isList(lsig2)) {
 104         Tree s = hd(lsig2); lsig2 = tl(lsig2);
 105         Tree E; int r; inferreRate(s, &r, E);
 106         if (r==0) {
 107             success = false;
 108             cerr << "ERROR inferreMultiRates failed 1" << endl;
 109             return nil;
 110         }
 111         sigs.push_back(s);
 112         envs.push_back(E);
 113         rates.push_back(r);
 114     }
 115
 116     // combines all the rate environements
 117     Tree LE = nil;
 118     success = true;
 119     for (unsigned int i=0; success && i<envs.size(); i++) {
 120         LE = addToMultiRates(envs[i], LE, success);
 121     }
 122     TRACE(cerr << "***multirates :"; printRateEnvironmentList(cerr, LE); cerr << endl);
 123     Tree RE = flatRateEnvironmentList(LE);
 124     TRACE(cerr << "***flat rate  :"; printRateEnvironment(cerr, RE); cerr << endl);
 125
 126     return RE;
 127 }
 128
 129
 130 /**
 131   * Print a rate environment
 132   */
 133 ostream&  printRateEnvironment(ostream& fout, Tree E)
 134 {
 135     string sep = "";
 136     fout << "rates {";
 137     while (isList(E)) {
 138         fout << sep << ppsig(hd(hd(E))) << ":" << tree2int(tl(hd(E)));
 139         sep=",";
 140         E = tl(E);
 141     }
 142     fout << "}";
 143     return fout;
 144 }
 145
 146
 147 /**
 148   * Print a list of rate environments
 149   */
 150 ostream&  printRateEnvironmentList(ostream& fout, Tree LE)
 151 {
 152     string sep = "";
 153     fout << "multi{";
 154     while (isList(LE)) {
 155         fout << sep; printRateEnvironment(fout, hd(LE));
 156         sep="++";
 157         LE = tl(LE);
 158     }
 159     fout << "}";
 160     return fout;
 161 }
 162
 163
 164
 165 /**************************************************************************************************
 166  **************************************************************************************************
 167  **************************************************************************************************
 168
 169                                         IMPLEMENTATION
 170
 171  **************************************************************************************************
 172  **************************************************************************************************
 173  **************************************************************************************************/
 174
 175
 176 /**
 177   * Greatest common divisor
 178   */
 179 static int TRACED_gcd(int a, int b);
 180
 181 static int gcd(int a, int b)
 182 {
 183     int r = TRACED_gcd(a,b);
 184     //cerr << TABBER << "gcd(" << a << ',' << b <<") = " << r << endl;
 185     return r;
 186 }
 187
 188
 189 static int TRACED_gcd(int a, int b)
 190 {
 191     return (b==0) ? a : gcd (b, a%b);
 192 }
 193
 194 /**
 195   * Least common multiple
 196   */
 197 static int lcm(int a, int b)
 198 {
 199     int r = (a*b)/gcd(a,b);
 200     //cerr << TABBER << "lcm(" << a << ',' << b <<") = " << r << endl;
 201     return r;
 202 }
 203
 204
 205 /**
 206  * Add to a list of existing signals lsig the list of recursive signals apprearing in lsig
 207  */
 208
 209 static Tree addRecursiveSignals(Tree lsig)
 210 {
 211     CTree::startNewVisit();
 212
 213     Tree lsig2 = lsig;
 214     while (isList(lsig)) {
 215         lsig2 = doAddRecursiveSignals(hd(lsig), lsig2);
 216         lsig = tl(lsig);
 217     }
 218     return lsig2;
 219 }
 220
 221
 222 static Tree doAddRecursiveSignals(Tree sig, Tree accSig)
 223 {
 224     TRACE(cerr << ++TABBER << "doAddRecursiveSignals(" << *sig << ',' << *accSig << ')' << endl);
 225     if ( ! sig->isAlreadyVisited() ) {
 226         int     i;
 227         Tree    rsig, id, body;
 228         sig->setVisited();
 229         if (isProj(sig,&i,rsig) && isRec(rsig, id, body)) {
 230             Tree p = nth(body,i);
 231             accSig = doAddRecursiveSignals(p, cons(p,accSig));
 232         } else {
 233             assert(!isProj(sig,&i,rsig));
 234
 235             vector<Tree>    subsigs;
 236             getSubSignals(sig,subsigs,false);
 237             for (unsigned int i=0; i<subsigs.size(); i++) {
 238                 accSig = doAddRecursiveSignals(subsigs[i], accSig);
 239             }
 240         }
 241     }
 242     TRACE(cerr << --TABBER << "doAddRecursiveSignals(" << *sig << ',' << *accSig << ") -> " << *accSig << endl);
 243     return accSig;
 244 }
 245
 246 /** *********************************** RATE ENVIRONMENTS ************************************************
 247
 248 A rate environement E = {(s1,r1), (s2,r2), ...} is a set of pairs associating a signal and a rate. The
 249 signals are unique : if (s1,r1) and (s2,r2) are in E then s1=s2 => r1=r2.
 250
 251 The environment is kept ordered
 252
 253
 254 **********************************************************************************************************/
 255
 256
 257
 258
 259 /**
 260   * Add a pair signal s1 x rate r1 to rate environment E
 261   */
 262 static Tree addRateEnv(Tree s1, int r1, Tree E)
 263 {
 264     if (isList(E)) {
 265         Tree s2 = hd(hd(E));
 266         if (s1 < s2) {
 267             return cons(cons(s1,tree(r1)),E);
 268         } else if (s1 == s2) {
 269             return cons(cons(s1,tree(r1)),tl(E));
 270         } else {
 271             return cons(hd(E), addRateEnv(s1,r1,tl(E)));
 272         }
 273     } else {
 274         return cons(cons(s1,tree(r1)),nil);
 275     }
 276 }
 277
 278
 279 /**
 280   * multiply by n all the rates of rate environment E
 281   * E={(s1,r1),...} -> E'={(s1,n.r1),...}
 282   */
 283 static Tree TRACED_multRateEnv(int n, Tree E);
 284
 285 static Tree multRateEnv(int n, Tree E)
 286 {
 287     TRACE(cerr << ++TABBER << "multRateEnv(" << n << ", " << *E << ")" << endl);
 288     Tree result = TRACED_multRateEnv(n, E);
 289     TRACE(cerr << --TABBER << "multRateEnv(" << n << ", " << *E << ") -> " << *result << endl);
 290     return result;
 291
 292 }
 293
 294
 295 static Tree TRACED_multRateEnv(int n, Tree E)
 296 {
 297     if (isList(E)) {
 298         Tree p = hd(E);
 299         Tree k = hd(p);
 300         int  r = tree2int(tl(p));
 301         Tree q = cons(k, tree(r*n));
 302         return cons(q, multRateEnv(n, tl(E)));
 303     } else {
 304         return nil;
 305     }
 306 }
 307
 308
 309 /**
 310   * Get value associated to key k in "function" l
 311   * returns true if a value was found.
 312   */
 313
 314 static bool getRateEnv(Tree k, int* i, Tree l)
 315 {
 316     if (isNil(l)) {
 317         return false;
 318     } else {
 319         assert (isList(l));
 320         Tree r = hd(hd(l));
 321         if (k < r) {
 322             return false;   // not found
 323         } else if (k == r) {
 324             *i = tree2int(tl(hd(l)));
 325             return true;
 326         } else {
 327             return getRateEnv(k,i,tl(l));
 328         }
 329     }
 330 }
 331
 332
 333
 334 /**
 335   * two rate environments are compatible if common rates
 336   * are linked by the same ratio
 337   */
 338
 339 static bool checkRatesCompatible(Tree R1, Tree R2, int n1, int n2)
 340 {
 341     if (isNil(R1) || isNil(R2)) {
 342         return true;
 343     } else {
 344         Tree p1 = hd (R1);
 345         Tree p2 = hd (R2);
 346
 347         Tree k1 = hd (p1);
 348         Tree k2 = hd (p2);
 349
 350         if (k1 < k2) {
 351             return checkRatesCompatible(tl(R1), R2, n1, n2);
 352         } else if (k1 > k2) {
 353             return checkRatesCompatible(R1, tl(R2), n1, n2);
 354         } else {
 355             Tree v1 = tl (p1);
 356             Tree v2 = tl (p2);
 357
 358             if (tree2int(v1)*n1 == tree2int(v2)*n2) {
 359                 return checkRatesCompatible(tl(R1), tl(R2), n1, n2);
 360             } else {
 361                 return false;
 362             }
 363         }
 364     }
 365 }
 366
 367
 368
 369 /**
 370   * Two rate environments are independent if they don't have any
 371   * signals in common
 372   */
 373
 374 static bool areRatesIndependent(Tree R1, Tree R2)
 375 {
 376     if (isNil(R1) || isNil(R2)) {
 377         return true;
 378     } else {
 379         Tree p1 = hd (R1);
 380         Tree p2 = hd (R2);
 381
 382         Tree s1 = hd (p1);
 383         Tree s2 = hd (p2);
 384
 385         if (s1 < s2) {
 386             return areRatesIndependent(tl(R1), R2);
 387         } else if (s2 < s1) {
 388             return areRatesIndependent(R1, tl(R2));
 389         } else {
 390             return false; // s1 and s2 are in common
 391         }
 392     }
 393 }
 394
 395
 396
 397
 398 /**
 399   * Two rate environments are compatible if common rates
 400   * are linked by the same ratio
 401   */
 402
 403 static bool areRatesCompatible(Tree R1, Tree R2, int& n1, int& n2)
 404 {
 405     if (isNil(R1) || isNil(R2)) {
 406
 407         n1 = 1; n2 = 1;
 408         return true;
 409
 410     } else {
 411
 412         Tree p1 = hd (R1);
 413         Tree p2 = hd (R2);
 414
 415         Tree k1 = hd (p1);
 416         Tree k2 = hd (p2);
 417
 418         if (k1 < k2) {
 419
 420             return areRatesCompatible(tl(R1), R2, n1, n2);
 421
 422         } else if (k1 > k2) {
 423
 424             return areRatesCompatible(R1, tl(R2), n1, n2);
 425
 426         } else {
 427
 428             // we have a common expression
 429             Tree v1 = tl (p1);
 430             Tree v2 = tl (p2);
 431
 432             int  r1 = tree2int(v1);
 433             int  r2 = tree2int(v2);
 434
 435             int  m = lcm(r1, r2);
 436
 437             // we update the n1 and n2 coefficients
 438             n1 = m/r1;
 439             n2 = m/r2;
 440
 441             // and we check that the rest of the environments are compatible
 442             return checkRatesCompatible(tl(R1), tl(R2), n1, n2);
 443         }
 444     }
 445 }
 446
 447
 448 /**
 449   * Merge two compatible rate environments.  Rate environments are
 450   * compatible if common expressions have same rate.
 451   * Returns the merge environment and success flag
 452   */
 453 static Tree TRACED_mergeRateEnvironment(Tree R1, Tree R2, bool& success);
 454
 455 static Tree mergeRateEnvironment(Tree R1, Tree R2, bool& success)
 456 {
 457     TRACE(cerr << ++TABBER << "mergeRateEnvironment(" << *R1 << ", " << *R2 << ")" << endl);
 458     Tree result = TRACED_mergeRateEnvironment(R1, R2, success);
 459     if (success) {
 460         TRACE(cerr << --TABBER << "mergeRateEnvironment(" << *R1 << ", " << *R2 << ") -> " << *result << endl);
 461     } else {
 462         TRACE(cerr << --TABBER << "mergeRateEnvironment(" << *R1 << ", " << *R2 << ") -> FAILED" << endl);
 463     }
 464     return result;
 465 }
 466
 467
 468
 469
 470 static Tree TRACED_mergeRateEnvironment(Tree R1, Tree R2, bool& success)
 471 {
 472     if (isNil(R1)) {
 473
 474         success = true;
 475         return R2;
 476
 477     } else if (isNil(R2)) {
 478
 479             success = true;
 480             return R1;
 481
 482     } else {
 483
 484         Tree p1 = hd (R1);
 485         Tree p2 = hd (R2);
 486
 487         Tree k1 = hd (p1);
 488         Tree k2 = hd (p2);
 489
 490         if (k1 < k2) {
 491
 492             return cons(p1, mergeRateEnvironment(tl(R1), R2, success));
 493
 494         } else if (k2 < k1) {
 495
 496             return cons(p2, mergeRateEnvironment(R1, tl(R2), success));
 497
 498         } else {
 499
 500             // we have a common expression
 501             Tree r1 = tl (p1);
 502             Tree r2 = tl (p2);
 503
 504             if (r1 == r2) {
 505                 // fine, same rate
 506                 return cons(p2, mergeRateEnvironment(tl(R1), tl(R2), success));
 507             } else {
 508                 success = false;
 509                 return nil;
 510             }
 511         }
 512     }
 513 }
 514
 515 /**
 516  * Merge a list of independent rate environments into a single rate environment
 517  */
 518 static Tree flatRateEnvironmentList(Tree lre)
 519 {
 520     Tree    e = nil;
 521     bool    success = true;
 522     while (isList(lre)) {
 523         e = mergeRateEnvironment(hd(lre),e, success);
 524         assert(success); // can't failed if environments are independant
 525         lre = tl(lre);
 526     }
 527     return e;
 528 }
 529
 530 /**
 531
 532 ========================================== RATE INFERENCE =========================================
 533
 534
 535 */
 536
 537
 538 property<Tree>   gInferreRateProperty;
 539
 540 static void setInferreRateProperty(Tree sig, int rate, Tree renv)
 541 {
 542     gInferreRateProperty.set(sig, cons(tree(rate),renv));
 543 }
 544
 545 static bool getInferreRateProperty(Tree sig, int* rate, Tree& renv)
 546 {
 547     Tree p;
 548     if (gInferreRateProperty.get(sig, p)) {
 549         *rate = tree2int(hd(p));
 550         renv = tl(p);
 551         return true;
 552     } else {
 553         return false;
 554     }
 555 }
 556
 557
 558 /**
 559   * Inferre rate (and rate environment) of a single signal.
 560   * Use a property to cache previous results
 561   */
 562 static void inferreRate(Tree sig, int* rate, Tree& E)
 563 {
 564     TRACE(cerr << ++TABBER << "inferreRate(" << ppsig(sig) << ")" << endl);
 565     if (! getInferreRateProperty(sig, rate, E)) {
 566         doInferreRate(sig, rate, E);
 567         setInferreRateProperty(sig, *rate, E);
 568     }
 569     TRACE(cerr << --TABBER << "inferreRate(" << ppsig(sig) << ") = " << *rate << " with " << *E << endl);
 570 }
 571
 572
 573 /**
 574   * Checks that w denotes a positive constant integer signal n
 575   * returns n or exit
 576   */
 577 static int checkSignalDenotesSize(Tree w, Tree sig)
 578 {
 579     // checks that w denotes a positive constant integer signal n
 580     SimpleType*  st = isSimpleType(getCertifiedSigType(w));
 581
 582     if (st && st->nature()==kInt) {
 583         interval i = st->getInterval();
 584         if (i.valid && i.lo >= 0 && i.lo == i.hi) {
 585             return int(i.lo);
 586         }
 587     }
 588     cerr << "ERROR in expression : " << ppsig(sig) << endl;
 589     cerr << *w << " is not a positive constant integer" << endl;
 590     exit(1);
 591 }
 592
 593 /**
 594   * Inferre the rate (and the rate environment) of a signal.
 595   * A zero rate indicates an impossibility
 596   */
 597 static void doInferreRate(Tree sig, int* rate, Tree& E)
 598 {
 599     Tree    w, x, rsig, id, body;
 600     int     i, in;
 601
 602     if ( isSigVectorize(sig, w, x) )  {
 603
 604         // -- rate(vectorize(n,x)) = rate(x)/n
 605
 606         VectorType* vt  = isVectorType(getCertifiedSigType(sig)); assert(vt);
 607         int         n   = vt->size(); assert(n>0);
 608
 609         int r; inferreRate(x, &r, E);
 610         if ((r%n) == 0) {
 611             // fine, the rate of x can be divided by n
 612             // (note: this is compatible with r==0 indicating that x has no rate)
 613             *rate = r/n;
 614         } else {
 615             // we need to scale the rates involved in x
 616             int m = lcm(n,r);
 617             *rate = m/n;
 618             E = multRateEnv(m/r, E);
 619         }
 620
 621     } else if ( isSigDownSample(sig, w, x) )  {
 622
 623         // -- rate(down(n,x) = rate(x)/n
 624
 625         int n = checkSignalDenotesSize(w, sig);
 626
 627         int r; inferreRate(x, &r, E);
 628
 629         if ((r%n) == 0) {
 630             // fine, the rate of x can be divided by n
 631             // (note: this is compatible with r==0 indicating that x has no rate)
 632             *rate = r/n;
 633         } else {
 634             // we need to scale the rates involved in x
 635             int m = lcm(n,r);
 636             *rate = m/n;
 637             E = multRateEnv(m/r, E);
 638         }
 639
 640     } else if ( isSigUpSample(sig, w, x) )  {
 641
 642         // -- rate(up(n,x) = rate(x)*n
 643
 644         int n = checkSignalDenotesSize(w, sig);
 645         int r; inferreRate(x, &r, E);
 646         *rate = r*n;
 647
 648     } else if ( isSigSerialize(sig, x)) {
 649
 650         // -- rate(serialize(x) = rate(x)*n    [with Type(x) = vector(n,T)]
 651
 652         VectorType* vt = isVectorType(getCertifiedSigType(x)); assert(vt);
 653
 654         int r; inferreRate(x, &r, E);
 655         *rate = vt->size() * r;
 656
 657     } else if ( isSigInput(sig, &in)) {
 658
 659         // -- rate(input(x)) = 1
 660
 661         *rate   = 1;
 662         E       = addRateEnv(sig,1,nil);
 663
 664     } else if (isProj(sig,&i,rsig) && isRec(rsig, id, body)) {
 665
 666         // -- rate(proj(i, x=(E0,E1,...))) = 1
 667
 668         *rate   = 1;
 669         E       = addRateEnv(sig,1,nil);
 670
 671     } else {
 672
 673         // -- rate(op())        = 1
 674         // -- rate(op(s1, s2))  = lcm(rate(s1), rate(s2))
 675
 676         vector<Tree> subsigs;
 677         unsigned int n = getSubSignals(sig, subsigs, false);
 678
 679         if (n == 0) {
 680             // -- rate(op())        = 1
 681            *rate = 1;
 682            E  = nil;
 683
 684         } else {
 685             // -- rate(op(s1, s2))  = lcm(rate(s1), rate(s2))
 686
 687             vector<int>     subrates(n);
 688             vector<Tree>    subenvs(n);
 689
 690             int lcmrate = 1;
 691             for (unsigned int i=0; i<n; i++) {
 692                 inferreRate(subsigs[i], &subrates[i], subenvs[i]);
 693                 lcmrate = lcm(subrates[i], lcmrate);
 694             }
 695
 696             // Try to merge all (scaled) rate environments
 697             Tree M = nil;
 698             bool success = false;
 699
 700             for (unsigned int i=0; i<n; i++) {
 701                 M = mergeRateEnvironment(M, multRateEnv(lcmrate/subrates[i], subenvs[i]), success);
 702                 if (! success) {
 703                     // merge failed
 704                     *rate = 0; E = nil;
 705                     return;
 706                 }
 707             }
 708             // merge successful
 709             *rate = lcmrate; E = M;
 710         }
 711     }
 712 }
 713
 714
 715 /**
 716   * Try to add a rate environment E1 to a list of independent rate environments LE
 717   * Returns a list of independent rate environments
 718   */
 719 static Tree addToMultiRates(Tree E1, Tree LE, bool& success);
 720 static Tree TRACED_addToMultiRates(Tree E1, Tree LE, bool& success);
 721
 722 static Tree addToMultiRates(Tree E1, Tree LE, bool& success)
 723 {
 724     TRACE(cerr << ++TABBER << "addToMultiRates(" << *E1 << ", " << *LE << ")" << endl);
 725     Tree result = TRACED_addToMultiRates(E1, LE, success);
 726     if (success) {
 727         TRACE(cerr << --TABBER << "addToMultiRates(" << *E1 << ", " << *LE << ") -> " << *result << endl);
 728     } else {
 729         TRACE(cerr << --TABBER << "addToMultiRates(" << *E1 << ", " << *LE << ") -> FAILED" << endl);
 730     }
 731     return result;
 732 }
 733
 734
 735 static Tree TRACED_addToMultiRates(Tree E1, Tree LE, bool& success)
 736 {
 737     if (isNil(LE)) {
 738         success = true;
 739         return cons(E1,nil);
 740     } else {
 741         Tree E2 = hd(LE);
 742         if (areRatesIndependent(E1,E2)) {
 743             return cons(E2, addToMultiRates(E1, tl(LE), success));
 744         } else {
 745             int n1, n2;
 746             if (areRatesCompatible(E1, E2, n1, n2)) {
 747                 Tree M = mergeRateEnvironment(multRateEnv(n1,E1), multRateEnv(n2,E2), success);
 748                 if (success) {
 749                     return addToMultiRates(M, tl(LE), success);
 750                 } else {
 751                     return nil;
 752                 }
 753             } else {
 754                 return nil;
 755             }
 756         }
 757     }
 758 }
 759
 760
 761
 762 RateInferrer::RateInferrer(Tree lsig)
 763 {
 764     TRACE(cerr << "ENTRE RateInferrer constructor of " << *lsig << endl);
 765     if (! (isList(lsig) | isNil(lsig))) {
 766         lsig = cons(lsig,nil);
 767     }
 768     fFullList = addRecursiveSignals(lsig);
 769     fRateEnv = inferreMultiRates(lsig, fSuccess);
 770     if (fSuccess) {
 771         // nit the rate properties for the expressions in the environment
 772         for (Tree L=fRateEnv; isList(L); L = tl(L)) {
 773             Tree p = hd(L);
 774             fRateProperty.set(hd(p),tree2int(tl(p)));
 775         }
 776     }
 777     TRACE(cerr << "EXIT RateInferrer constructor" << *lsig << endl);
 778 }
 779
 780 // returns the rate of sig assuming that sig is a subexpression of lsig
 781 int RateInferrer::rate(Tree sig)
 782 {
 783     int     r;
 784
 785     if (!fSuccess) {
 786         return 0;
 787     } else if (fRateProperty.get(sig, r)) {
 788         return r;
 789     } else {
 790         r = computeRate(sig);
 791         fRateProperty.set(sig, r);
 792         return r;
 793     }
 794 }
 795
 796 int RateInferrer::computeRate(Tree sig)
 797 {
 798     Tree    n, x, rsig, id, body;
 799     int     i;
 800
 801     if ( isSigInput(sig, &i)) {
 802
 803         TRACE(cerr << "ERROR: Input " << i << " should have a rate" << endl);
 804         return 0;
 805
 806     } else if ( isProj(sig,&i,rsig) && isRec(rsig, id, body) ) {
 807
 808         TRACE(cerr << "ERROR: Recursive signal " << *sig << " should have a rate" << endl);
 809         return 0;
 810
 811     } else if ( isSigVectorize(sig, n, x) ) {
 812
 813         VectorType* vt = isVectorType(getCertifiedSigType(sig));
 814         assert(vt);
 815         return rate(x) / vt->size();
 816
 817     } else if ( isSigSerialize(sig, x)) {
 818
 819         VectorType* vt = isVectorType(getCertifiedSigType(x));
 820         assert(vt);
 821         return vt->size() * rate(x);
 822
 823     } else if ( isSigUpSample(sig, n, x) ) {
 824
 825         int i = checkSignalDenotesSize(n,sig);
 826         return rate(x) * i;
 827
 828     } else if ( isSigDownSample(sig, n, x) ) {
 829
 830         int i = checkSignalDenotesSize(n,sig);
 831         int r = rate(x);
 832         assert(r%i == 0);
 833         return r/i;
 834
 835     } else {
 836
 837         vector<Tree> subsigs;
 838         vector<int> subrates;
 839         int n = getSubSignals(sig, subsigs, false);
 840         if (n == 0) {
 841             // we don't depend of any subsignals, then the rate is 1
 842             return 1;
 843         } else {
 844             // we depend on subsignals, the rate is the highest one
 845             // moreover the highest one is a multiple of all other
 846             // rates
 847             int maxrate = 1;
 848             int lcmrate = 1;
 849             for (unsigned int i=0; i<subsigs.size(); i++) {
 850                 int r = rate(subsigs[i]);
 851                 maxrate = max(r, maxrate);
 852                 lcmrate = lcm(r, lcmrate);
 853                 if (lcmrate != maxrate) {
 854                     return 0; // rates of arguments are incompatible
 855                 }
 856             }
 857             return maxrate;
 858         }
 859     }
 860 }
 861
 862