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