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
8 the Free Software Foundation; either version 2 of the License, or
9 (at your option) any later version.
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.
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"
28 #include "signals.hh"
29 #include "ppsig.hh"
30 #include "set"
32 using namespace std;
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 */
46 //--------------------------------------------------------------------------
47 static int annotate(Tree env, Tree sig);
48 static int position (Tree env, Tree t, int p=1);
50 Tree RECURSIVNESS = tree(symbol("RecursivnessProp"));
51 //--------------------------------------------------------------------------
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 }
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 }
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;
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 }
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 }
133 //-----------------------------------list recursive symbols-----------------------
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 */
143 // the property used to memoize the results
144 property<Tree> SymListProp;
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 }
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 }