interpreter/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 }