interpreter/preprocessor/faust-0.9.47mr3/compiler/signals/recursivness.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 #include <assert.h>
  22 #include <stdio.h>
  23 #include <stdlib.h>
  24 #include <limits.h>
  25 #include "recursivness.hh"
  26 #include "property.hh"
  27
  28 #include "signals.hh"
  29 #include "ppsig.hh"
  30 #include "set"
  31
  32 using namespace std;
  33
  34
  35 /**
  36  * @file recursivness.cpp
  37  * Annotate a signal expression with recursivness information. Recursiveness
  38  * indicates the amount of recursive dependencies of a signal. A closed signal
  39  * has a recursivness of 0 because is has no recursive dependencies. This means
  40  * that the succesive samples of this signal can be computed in parallel.
  41  * In a signal of type \x.(...F(x)...), F(x) has a recursivness of 1. In a
  42  * signal of type \x.(... \y.(...F(x)...G(y)...)...) F(x) has a recursivness of 2
  43  * while G(y) has a recursivness of 1.
  44  */
  45
  46 //--------------------------------------------------------------------------
  47 static int annotate(Tree env, Tree sig);
  48 static int position (Tree env, Tree t, int p=1);
  49
  50 Tree RECURSIVNESS = tree(symbol("RecursivnessProp"));
  51 //--------------------------------------------------------------------------
  52
  53
  54 /**
  55  * Annotate a signal with recursivness. Should be used before
  56  * calling getRecursivness
  57  * @param sig signal to annotate
  58  */
  59 void recursivnessAnnotation(Tree sig)
  60 {
  61         annotate(nil, sig);
  62 }
  63
  64
  65 /**
  66  * Return the recursivness of a previously
  67  * annotated signal. An error is generated
  68  * if the signal has no recursivness property
  69  * @param sig signal
  70  * @return recursivness of the signal
  71  */
  72 int getRecursivness(Tree sig)
  73 {
  74         Tree tr;
  75         if ( ! getProperty(sig, RECURSIVNESS, tr)) {
  76                 cerr << "Error in getRecursivness of " << *sig << endl;
  77                 exit(1);
  78         }
  79         return tree2int(tr);
  80 }
  81
  82 //-------------------------------------- IMPLEMENTATION ------------------------------------
  83 /**
  84  * Annotate a signal with recursivness
  85  * @param env the current environment
  86  * @param sig signal to annotate
  87  * @return recursivness of the signal
  88  */
  89 static int annotate(Tree env, Tree sig)
  90 {
  91         Tree tr, var, body;
  92
  93         if (getProperty(sig, RECURSIVNESS, tr)) {
  94                 return tree2int(tr);    // already annotated
  95         } else if (isRec(sig, var, body)) {
  96                 int p = position(env, sig);
  97                 if (p > 0) {
  98                         return p;       // we are inside \x.(...)
  99                 } else {
 100                         int r = annotate(cons(sig, env), body) - 1;
 101                         if (r<0) r=0;
 102                         setProperty(sig, RECURSIVNESS, tree(r));
 103                         return r;
 104                 }
 105         } else {
 106                 int rmax = 0;
 107                 vector<Tree> v; getSubSignals(sig, v);
 108                 for (unsigned int i=0; i<v.size(); i++) {
 109                         int r = annotate(env, v[i]);
 110                         if (r>rmax) rmax=r;
 111                 }
 112                 setProperty(sig, RECURSIVNESS, tree(rmax));
 113                 return rmax;
 114         }
 115 }
 116
 117
 118
 119 /**
 120  * return the position of a signal in the current recursive environment
 121  * @param env the current recursive environment of the signal
 122  * @param t signal we want to know the position
 123  * @return the position in the recursive environment
 124  */
 125 static int position (Tree env, Tree t, int p)
 126 {
 127         if (isNil(env)) return 0;       // was not in the environment
 128         if (hd(env) == t) return p;
 129         else return position (tl(env), t, p+1);
 130 }
 131
 132
 133 //-----------------------------------list recursive symbols-----------------------
 134
 135
 136
 137 /**
 138  * return the set of recursive symbols appearing in a signal.
 139  * @param sig the signal to analyze
 140  * @return the set of symbols
 141  */
 142
 143 // the property used to memoize the results
 144 property<Tree>  SymListProp;
 145
 146 Tree    symlistVisit(Tree sig, set<Tree>& visited)
 147 {
 148     Tree S;
 149     if (SymListProp.get(sig, S)) {
 150         return S;
 151     } else if ( visited.count(sig) > 0 ){
 152         return nil;
 153     } else {
 154         visited.insert(sig);
 155         Tree id, body;
 156         if (isRec(sig, id, body)) {
 157             Tree U = singleton(sig);
 158             for (int i=0; i<len(body); i++) {
 159                 U = setUnion(U, symlistVisit(nth(body,i), visited));
 160             }
 161             return U;
 162         } else {
 163             vector<Tree> subsigs;
 164             int n = getSubSignals(sig, subsigs, true); // il faut visiter aussi les tables
 165             Tree U = nil;
 166             for (int i=0; i<n; i++) {
 167                 U = setUnion(U, symlistVisit(subsigs[i], visited));
 168             }
 169             return U;
 170         }
 171     }
 172 }
 173
 174 Tree    symlist(Tree sig)
 175 {
 176     Tree    S;
 177     if (!SymListProp.get(sig, S)) {
 178         set<Tree> visited;
 179         S = symlistVisit(sig, visited);
 180         SymListProp.set(sig, S);
 181     }
 182     //cerr << "SYMLIST " << *S << " OF " << ppsig(sig) << endl;
 183     return S;
 184 }