Add sinwave, fft and fft2d examples.
[Faustine.git] / interpretor / preprocessor / faust-0.9.47mr3 / compiler / normalize / simplify.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 "list.hh"
27 #include "signals.hh"
28 #include "sigtype.hh"
29 #include "recursivness.hh"
30 #include "sigtyperules.hh"
31 #include "sigorderrules.hh"
32 #include "sigprint.hh"
33 #include "ppsig.hh"
34 #include "simplify.hh"
35 #include "num.hh"
36 #include "xtended.hh"
37 #include <map>
38 #include "compatibility.hh"
39
40 #include "normalize.hh"
41
42 #undef TRACE
43
44 // declarations
45 Tree SIMPLIFIED = tree(symbol("sigSimplifiedProp"));
46 //static Tree binequiv (Tree sig, int opnum, Tree a, Tree b);
47 static Tree simplification (Tree sig);
48 static Tree sigMap (Tree key, tfun f, Tree t);
49
50 static Tree traced_simplification(Tree sig)
51 {
52 assert(sig);
53 #ifdef TRACE
54 cerr << ++TABBER << "Start simplification of : " << ppsig(sig) << endl;
55 /*
56 fprintf(stderr, "\nStart simplification of : ");
57 printSignal(sig, stderr);
58 fprintf(stderr, "\n");
59 */
60 #endif
61 Tree r = simplification(sig);
62 assert(r!=0);
63 #ifdef TRACE
64 cerr << --TABBER << "Simplification of : " << ppsig(sig) << " Returns : " << ppsig(r) << endl;
65 /*
66 fprintf(stderr, "Simplification of : ");
67 printSignal(sig, stderr);
68 fprintf(stderr, " -> ");
69 printSignal(r, stderr);
70 fprintf(stderr, "\n");
71 */
72 #endif
73 return r;
74 }
75
76 Tree simplify (Tree sig)
77 {
78 return sigMap(SIMPLIFIED, traced_simplification, sig);
79 }
80
81
82 // Implementation
83
84 static Tree simplification (Tree sig)
85 {
86 assert(sig);
87 int opnum;
88 Tree t1, t2, t3, t4;
89
90 xtended* xt = (xtended*) getUserData(sig);
91 // primitive elements
92 if (xt)
93 {
94 //return 3;
95 vector<Tree> args;
96 for (int i=0; i<sig->arity(); i++) { args.push_back( sig->branch(i) ); }
97
98 // to avoid negative power to further normalization
99 if (xt != gPowPrim) {
100 return xt->computeSigOutput(args);
101 } else {
102 return normalizeAddTerm(xt->computeSigOutput(args));
103 }
104
105 } else if (isSigBinOp(sig, &opnum, t1, t2)) {
106
107 BinOp* op = gBinOpTable[opnum];
108
109 Node n1 = t1->node();
110 Node n2 = t2->node();
111
112 if (isNum(n1) && isNum(n2)) return tree(op->compute(n1,n2));
113
114 else if (op->isLeftNeutral(n1)) return t2;
115
116 else if (op->isRightNeutral(n2)) return t1;
117
118 else return normalizeAddTerm(sig);
119
120 } else if (isSigDelay1(sig, t1)) {
121
122 return normalizeDelay1Term (t1);
123
124 } else if (isSigFixDelay(sig, t1, t2)) {
125
126 return normalizeFixedDelayTerm (t1, t2);
127
128 } else if (isSigIntCast(sig, t1)) {
129
130 Tree tx;
131 int i;
132 double x;
133 Node n1 = t1->node();
134
135 if (isInt(n1, &i)) return t1;
136 if (isDouble(n1, &x)) return tree(int(x));
137 if (isSigIntCast(t1, tx)) return t1;
138
139 return sig;
140
141 } else if (isSigFloatCast(sig, t1)) {
142
143 Tree tx;
144 int i;
145 double x;
146 Node n1 = t1->node();
147
148 if (isInt(n1, &i)) return tree(double(i));
149 if (isDouble(n1, &x)) return t1;
150 if (isSigFloatCast(t1, tx)) return t1;
151
152 return sig;
153
154 } else if (isSigSelect2(sig, t1, t2, t3)){
155
156 Node n1 = t1->node();
157
158 if (isZero(n1)) return t2;
159 if (isNum(n1)) return t3;
160
161 if (t2==t3) return t2;
162
163 return sig;
164
165 } else if (isSigSelect3(sig, t1, t2, t3, t4)){
166
167 Node n1 = t1->node();
168
169 if (isZero(n1)) return t2;
170 if (isOne(n1)) return t3;
171 if (isNum(n1)) return t4;
172
173 if (t3==t4) return simplification(sigSelect2(t1,t2,t3));
174
175 return sig;
176
177 } else {
178
179 return sig;
180 }
181 }
182
183 /**
184 * Recursively transform a graph by applying a function f.
185 * map(f, foo[t1..tn]) = f(foo[map(f,t1)..map(f,tn)])
186 */
187 static Tree sigMap (Tree key, tfun f, Tree t)
188 {
189 //printf("start sigMap\n");
190 Tree p,id,body;
191
192 if (getProperty(t, key, p)) {
193
194 return (isNil(p)) ? t : p; // truc pour eviter les boucles
195
196 } else if (isRec(t, id, body)) {
197
198 setProperty(t, key, nil); // avoid infinite loop
199 return rec(id, sigMap(key, f, body));
200
201 } else {
202
203 Tree r1=nil;
204 switch (t->arity()) {
205
206 case 0 :
207 r1 = t;
208 break;
209 case 1 :
210 r1 = tree(t->node(), sigMap(key,f,t->branch(0)));
211 break;
212 case 2 :
213 r1 = tree(t->node(), sigMap(key,f,t->branch(0)), sigMap(key,f,t->branch(1)));
214 break;
215 case 3 :
216 r1 = tree(t->node(), sigMap(key,f,t->branch(0)), sigMap(key,f,t->branch(1)),
217 sigMap(key,f,t->branch(2)));
218 break;
219 case 4 :
220 r1 = tree(t->node(), sigMap(key,f,t->branch(0)), sigMap(key,f,t->branch(1)),
221 sigMap(key,f,t->branch(2)), sigMap(key,f,t->branch(3)));
222 break;
223 }
224 Tree r2 = f(r1);
225 if (r2 == t) {
226 setProperty(t, key, nil);
227 } else {
228 setProperty(t, key, r2);
229 }
230 return r2;
231 }
232 }
233
234
235
236
237
238 /**
239 * Like SigMap, recursively transform a graph by applying a
240 * function f. But here recursive trees are also renamed.
241 * map(f, foo[t1..tn]) = f(foo[map(f,t1)..map(f,tn)])
242 */
243 static Tree sigMapRename (Tree key, Tree env, tfun f, Tree t)
244 {
245 //printf("start sigMap\n");
246 Tree p,id,body;
247
248 if (getProperty(t, key, p)) {
249
250 return (isNil(p)) ? t : p; // truc pour eviter les boucles
251
252 } else if (isRec(t, id, body)) {
253
254 assert(isRef(t,id)); // controle temporaire
255
256 Tree id2;
257 if (searchEnv(id, id2, env)) {
258 // déjà en cours de visite de cette recursion
259 return ref(id2);
260 } else {
261 // premiere visite de cette recursion
262 id2 = tree(Node(unique("renamed")));
263 Tree body2 = sigMapRename(key, pushEnv(id, id2, env), f, body);
264 return rec(id2,body2);
265 }
266
267 } else {
268
269 Tree r1=nil;
270 switch (t->arity()) {
271
272 case 0 :
273 r1 = t;
274 break;
275 case 1 :
276 r1 = tree(t->node(), sigMapRename(key,env,f,t->branch(0)));
277 break;
278 case 2 :
279 r1 = tree(t->node(), sigMapRename(key,env,f,t->branch(0)),
280 sigMapRename(key,env,f,t->branch(1)));
281 break;
282 case 3 :
283 r1 = tree(t->node(), sigMapRename(key,env,f,t->branch(0)),
284 sigMapRename(key,env,f,t->branch(1)),
285 sigMapRename(key,env,f,t->branch(2)));
286 break;
287 case 4 :
288 r1 = tree(t->node(), sigMapRename(key,env,f,t->branch(0)),
289 sigMapRename(key,env,f,t->branch(1)),
290 sigMapRename(key,env,f,t->branch(2)),
291 sigMapRename(key,env,f,t->branch(3)));
292 break;
293 }
294 Tree r2 = f(r1);
295 if (r2 == t) {
296 setProperty(t, key, nil);
297 } else {
298 setProperty(t, key, r2);
299 }
300 return r2;
301 }
302 }
303
304 #if 0
305 static void eraseProperties (Tree key, Tree t)
306 {
307 //printf("start sigMap\n");
308 Tree p,id,body;
309
310 if (getProperty(t, key, p)) {
311 // already erased, nothing to do
312
313 } else if (isRec(t, id, body)) {
314 t->clearProperties();
315 Tree r=rec(id, body);
316 assert(r==t);
317 setProperty(t, key, nil); // avoid infinite loop
318 eraseProperties(key, body);
319
320 } else {
321
322 for (int i=0; i<t->arity(); i++) {
323 eraseProperties(key,t->branch(i));
324 }
325 }
326 }
327
328 void eraseAllProperties(Tree t)
329 {
330 cerr << "begin eraseAllProperties" << endl;
331 eraseProperties(tree(Node(unique("erase_"))), t);
332 cerr << "end eraseAllProperties" << endl;
333 }
334 #endif
335
336 /**
337 * Converts regular tables into doc tables in order to
338 * facilitate the mathematical documentation generation
339 */
340
341 Tree DOCTABLES = tree(symbol("DocTablesProp"));
342
343 static Tree docTableConverter (Tree sig);
344
345 static Tree NULLENV = tree(symbol("NullRenameEnv"));
346
347 Tree docTableConvertion (Tree sig)
348 {
349 Tree r = sigMapRename(DOCTABLES, NULLENV, docTableConverter, sig);
350 return r;
351 }
352
353
354 // Implementation
355
356 static Tree docTableConverter (Tree sig)
357 {
358 Tree tbl, tbl2, id, id2, size, igen, isig, ridx, widx, wsig;
359
360 if (isSigRDTbl(sig, tbl, ridx)) {
361 // we are in a table to convert
362 if (isSigTable(tbl, id, size, igen)) {
363 // it's a read only table
364 assert(isSigGen(igen, isig));
365 return sigDocAccessTbl(sigDocConstantTbl(size,isig),ridx);
366 } else {
367 // it's a read write table
368 assert(isSigWRTbl(tbl,id,tbl2,widx,wsig));
369 assert(isSigTable(tbl2, id2, size, igen));
370 assert(isSigGen(igen, isig));
371
372 return sigDocAccessTbl(sigDocWriteTbl(size,isig,widx,wsig),ridx);
373 }
374
375 } else {
376 // nothing to convert
377 return sig;
378 }
379 }