+++ /dev/null
-/************************************************************************
- ************************************************************************
- FAUST compiler
- Copyright (C) 2003-2004 GRAME, Centre National de Creation Musicale
- ---------------------------------------------------------------------
- This program is free software; you can redistribute it and/or modify
- it under the terms of the GNU General Public License as published by
- the Free Software Foundation; either version 2 of the License, or
- (at your option) any later version.
-
- This program is distributed in the hope that it will be useful,
- but WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- GNU General Public License for more details.
-
- You should have received a copy of the GNU General Public License
- along with this program; if not, write to the Free Software
- Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
- ************************************************************************
- ************************************************************************/
-#include <assert.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <limits.h>
-#include "recursivness.hh"
-#include "property.hh"
-
-#include "signals.hh"
-#include "ppsig.hh"
-#include "set"
-
-using namespace std;
-
-
-/**
- * @file recursivness.cpp
- * Annotate a signal expression with recursivness information. Recursiveness
- * indicates the amount of recursive dependencies of a signal. A closed signal
- * has a recursivness of 0 because is has no recursive dependencies. This means
- * that the succesive samples of this signal can be computed in parallel.
- * In a signal of type \x.(...F(x)...), F(x) has a recursivness of 1. In a
- * signal of type \x.(... \y.(...F(x)...G(y)...)...) F(x) has a recursivness of 2
- * while G(y) has a recursivness of 1.
- */
-
-//--------------------------------------------------------------------------
-static int annotate(Tree env, Tree sig);
-static int position (Tree env, Tree t, int p=1);
-
-Tree RECURSIVNESS = tree(symbol("RecursivnessProp"));
-//--------------------------------------------------------------------------
-
-
-/**
- * Annotate a signal with recursivness. Should be used before
- * calling getRecursivness
- * @param sig signal to annotate
- */
-void recursivnessAnnotation(Tree sig)
-{
- annotate(nil, sig);
-}
-
-
-/**
- * Return the recursivness of a previously
- * annotated signal. An error is generated
- * if the signal has no recursivness property
- * @param sig signal
- * @return recursivness of the signal
- */
-int getRecursivness(Tree sig)
-{
- Tree tr;
- if ( ! getProperty(sig, RECURSIVNESS, tr)) {
- cerr << "Error in getRecursivness of " << *sig << endl;
- exit(1);
- }
- return tree2int(tr);
-}
-
-//-------------------------------------- IMPLEMENTATION ------------------------------------
-/**
- * Annotate a signal with recursivness
- * @param env the current environment
- * @param sig signal to annotate
- * @return recursivness of the signal
- */
-static int annotate(Tree env, Tree sig)
-{
- Tree tr, var, body;
-
- if (getProperty(sig, RECURSIVNESS, tr)) {
- return tree2int(tr); // already annotated
- } else if (isRec(sig, var, body)) {
- int p = position(env, sig);
- if (p > 0) {
- return p; // we are inside \x.(...)
- } else {
- int r = annotate(cons(sig, env), body) - 1;
- if (r<0) r=0;
- setProperty(sig, RECURSIVNESS, tree(r));
- return r;
- }
- } else {
- int rmax = 0;
- vector<Tree> v; getSubSignals(sig, v);
- for (unsigned int i=0; i<v.size(); i++) {
- int r = annotate(env, v[i]);
- if (r>rmax) rmax=r;
- }
- setProperty(sig, RECURSIVNESS, tree(rmax));
- return rmax;
- }
-}
-
-
-
-/**
- * return the position of a signal in the current recursive environment
- * @param env the current recursive environment of the signal
- * @param t signal we want to know the position
- * @return the position in the recursive environment
- */
-static int position (Tree env, Tree t, int p)
-{
- if (isNil(env)) return 0; // was not in the environment
- if (hd(env) == t) return p;
- else return position (tl(env), t, p+1);
-}
-
-
-//-----------------------------------list recursive symbols-----------------------
-
-
-
-/**
- * return the set of recursive symbols appearing in a signal.
- * @param sig the signal to analyze
- * @return the set of symbols
- */
-
-// the property used to memoize the results
-property<Tree> SymListProp;
-
-Tree symlistVisit(Tree sig, set<Tree>& visited)
-{
- Tree S;
- if (SymListProp.get(sig, S)) {
- return S;
- } else if ( visited.count(sig) > 0 ){
- return nil;
- } else {
- visited.insert(sig);
- Tree id, body;
- if (isRec(sig, id, body)) {
- Tree U = singleton(sig);
- for (int i=0; i<len(body); i++) {
- U = setUnion(U, symlistVisit(nth(body,i), visited));
- }
- return U;
- } else {
- vector<Tree> subsigs;
- int n = getSubSignals(sig, subsigs, true); // il faut visiter aussi les tables
- Tree U = nil;
- for (int i=0; i<n; i++) {
- U = setUnion(U, symlistVisit(subsigs[i], visited));
- }
- return U;
- }
- }
-}
-
-Tree symlist(Tree sig)
-{
- Tree S;
- if (!SymListProp.get(sig, S)) {
- set<Tree> visited;
- S = symlistVisit(sig, visited);
- SymListProp.set(sig, S);
- }
- //cerr << "SYMLIST " << *S << " OF " << ppsig(sig) << endl;
- return S;
-}
projects / Faustine.git / blobdiff