recursive-tree.cpp File Reference

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include "tlib.hh"
Include dependency graph for recursive-tree.cpp:

Go to the source code of this file.

Classes

struct  Env

Functions

static Tree calcDeBruijn2Sym (Tree t)
static Tree substitute (Tree t, int n, Tree id)
static Tree calcsubstitute (Tree t, int level, Tree id)
static Tree liftn (Tree t, int threshold)
static Tree calcliftn (Tree t, int threshold)
Tree rec (Tree body)
 create a de Bruijn recursive tree
bool isRec (Tree t, Tree &body)
 is t a de Bruijn recursive tree
Tree ref (int level)
 create a de Bruijn recursive reference
bool isRef (Tree t, int &level)
 is t a de Bruijn recursive reference
Tree rec (Tree var, Tree body)
 create a symbolic recursive tree
bool isRec (Tree t, Tree &var, Tree &body)
 is t a symbolic recursive tree
Tree ref (Tree id)
 create a symbolic recursive reference
bool isRef (Tree t, Tree &v)
 is t a symbolic recursive reference
Tree lift (Tree t)
void printSignal (Tree sig, FILE *out, int prec=0)
Tree deBruijn2Sym (Tree t)
static void markOpen (Tree t)
static int recomputeAperture (Tree t, Env *p)
static int orderof (Tree t, Env *p)
void updateAperture (Tree t)

Variables

Sym DEBRUIJN = symbol ("DEBRUIJN")
Sym DEBRUIJNREF = symbol ("DEBRUIJNREF")
Sym SUBSTITUTE = symbol ("SUBSTITUTE")
Sym SYMREC = symbol ("SYMREC")
Sym SYMRECREF = symbol ("SYMRECREF")
Sym SYMLIFTN = symbol ("LIFTN")
Tree RECDEF = tree(symbol("RECDEF"))
Tree DEBRUIJN2SYM = tree(symbol("deBruijn2Sym"))

Function Documentation

static Tree calcDeBruijn2Sym ( Tree  t  )  [static]

Definition at line 235 of file recursive-tree.cpp.

References CTree::arity(), CTree::branch(), deBruijn2Sym(), isRec(), isRef(), CTree::make(), CTree::node(), printSignal(), rec(), ref(), substitute(), tree(), and unique().

Referenced by deBruijn2Sym().

00236 {
00237     Tree    body, var;
00238     int     i;
00239 
00240     if (isRec(t,body)) {
00241 
00242         var = tree(unique("W"));
00243         return rec(var, deBruijn2Sym(substitute(body,1,ref(var))));
00244 
00245     } else if (isRef(t,var)) {
00246 
00247         return t;
00248 
00249     } else if (isRef(t,i)) {
00250 
00251         fprintf(stderr, "ERREUR, une reference de Bruijn touvee ! : ");
00252         printSignal(t, stderr);
00253         fprintf(stderr, ")\n");
00254         exit(1);
00255         return t;
00256 
00257     } else {
00258 
00259         //Tree  br[4];
00260         int     a = t->arity();
00261         tvec    br(a);
00262 
00263         for (int i = 0; i < a; i++) {
00264             br[i] = deBruijn2Sym(t->branch(i));
00265         }
00266         //return CTree::make(t->node(), a, br);
00267         return CTree::make(t->node(), br);
00268     }
00269 }

Here is the call graph for this function:

Here is the caller graph for this function:

static Tree calcliftn ( Tree  t,
int  threshold 
) [static]

Definition at line 182 of file recursive-tree.cpp.

References CTree::arity(), CTree::branch(), isClosed(), isRec(), isRef(), liftn(), CTree::make(), CTree::node(), rec(), and ref().

Referenced by liftn().

00183 {
00184     int     n;
00185     Tree    u;
00186 
00187     if (isClosed(t)) {
00188 
00189         return t;
00190 
00191     } else if (isRef(t,n)) {
00192 
00193         if (n < threshold) {
00194             // it is a bounded reference
00195             return t;
00196         } else {
00197             // it is a free reference
00198             return ref(n+1);
00199         }
00200 
00201     } else if (isRec(t,u)) {
00202 
00203         return rec(liftn(u, threshold+1));
00204 
00205     } else {
00206         int n = t->arity();
00207         //Tree  br[4];
00208         tvec    br(n);
00209         for (int i = 0; i < n; i++) {
00210             br[i] = liftn(t->branch(i), threshold);
00211         }
00212         //return CTree::make(t->node(), n, br);
00213         return CTree::make(t->node(), br);
00214     }
00215 
00216 }

Here is the call graph for this function:

Here is the caller graph for this function:

static Tree calcsubstitute ( Tree  t,
int  level,
Tree  id 
) [static]

Definition at line 284 of file recursive-tree.cpp.

References CTree::aperture(), CTree::arity(), CTree::branch(), isRec(), isRef(), CTree::make(), CTree::node(), rec(), and substitute().

Referenced by substitute().

00285 {
00286     int     l;
00287     Tree    body;
00288 
00289     if (t->aperture()<level) {
00290 //      fprintf(stderr, "aperture %d < level %d !!\n", t->aperture(), level);
00291         return t;
00292     }
00293     if (isRef(t,l))          return (l == level) ? id : t;
00294     if (isRec(t,body))       return rec(substitute(body, level+1, id));
00295 
00296     int     ar = t->arity();
00297     //Tree  br[4];
00298     tvec    br(ar);
00299     for (int i = 0; i < ar; i++) {
00300         br[i] = substitute(t->branch(i), level, id);
00301     }
00302     //return CTree::make(t->node(), ar, br);
00303     return CTree::make(t->node(), br);
00304 }

Here is the call graph for this function:

Here is the caller graph for this function:

Tree deBruijn2Sym ( Tree  t  ) 

Definition at line 223 of file recursive-tree.cpp.

References calcDeBruijn2Sym(), CTree::getProperty(), isClosed(), and CTree::setProperty().

Referenced by calcDeBruijn2Sym(), mapPrepareEqSig(), and ScalarCompiler::prepare().

00224 {
00225     assert(isClosed(t));
00226     Tree t2 = t->getProperty(DEBRUIJN2SYM);
00227 
00228     if (!t2) {
00229         t2 = calcDeBruijn2Sym(t);
00230         t->setProperty(DEBRUIJN2SYM, t2);
00231     }
00232     return t2;
00233 }

Here is the call graph for this function:

Here is the caller graph for this function:

bool isRec ( Tree  t,
Tree var,
Tree body 
)

is t a symbolic recursive tree

Definition at line 95 of file recursive-tree.cpp.

References CTree::getProperty(), and isTree().

00096 {
00097     if (isTree(t, SYMREC, var)) {
00098         body = t->getProperty(RECDEF);
00099         return true;
00100     } else {
00101         return false;
00102     }
00103 }

Here is the call graph for this function:

bool isRec ( Tree  t,
Tree body 
)

is t a de Bruijn recursive tree

Definition at line 59 of file recursive-tree.cpp.

References isTree().

Referenced by annotate(), calcDeBruijn2Sym(), calcliftn(), calcsubstitute(), computePrivatisation(), DocCompiler::generateRecProj(), ScalarCompiler::generateRecProj(), getSubSignals(), infereSigOrder(), infereSigType(), ppsig::print(), printSignal(), recomputeAperture(), sigMap(), sigMapRename(), and sigvisitor::visit().

00060 {
00061     return isTree(t, DEBRUIJN, body);
00062 }

Here is the call graph for this function:

Here is the caller graph for this function:

bool isRef ( Tree  t,
Tree v 
)

is t a symbolic recursive reference

Definition at line 111 of file recursive-tree.cpp.

References isTree().

00112 {
00113     return isTree(t, SYMREC, v);
00114 }

Here is the call graph for this function:

bool isRef ( Tree  t,
int &  level 
)

is t a de Bruijn recursive reference

Definition at line 70 of file recursive-tree.cpp.

References isInt(), isTree(), and CTree::node().

Referenced by calcDeBruijn2Sym(), calcliftn(), calcsubstitute(), infereSigOrder(), ppsig::print(), printSignal(), recomputeAperture(), sigMapRename(), and sigvisitor::visit().

00071 {
00072     Tree    u;
00073 
00074     if (isTree(t, DEBRUIJNREF, u)) {
00075         return isInt(u->node(), &level);
00076     } else {
00077         return false;
00078     }
00079 }

Here is the call graph for this function:

Here is the caller graph for this function:

Tree lift ( Tree  t  ) 

Definition at line 149 of file recursive-tree.cpp.

References liftn().

Referenced by listLift(), and propagate().

00149 { return liftn(t, 1); }

Here is the call graph for this function:

Here is the caller graph for this function:

static Tree liftn ( Tree  t,
int  threshold 
) [static]

Definition at line 169 of file recursive-tree.cpp.

References calcliftn(), CTree::getProperty(), CTree::setProperty(), and tree().

Referenced by calcliftn(), and lift().

00170 {
00171     Tree L  = tree( Node(SYMLIFTN), tree(Node(threshold)) );
00172     Tree t2 = t->getProperty(L);
00173 
00174     if (!t2) {
00175         t2 = calcliftn(t, threshold);
00176         t->setProperty(L, t2);
00177     }
00178     return t2;
00179     
00180 }

Here is the call graph for this function:

Here is the caller graph for this function:

static void markOpen ( Tree  t  )  [static]

Definition at line 328 of file recursive-tree.cpp.

References CTree::aperture(), CTree::arity(), CTree::branch(), and CTree::setAperture().

Referenced by updateAperture().

00329 {
00330     if (t->aperture() == INT_MAX) return;
00331     t->setAperture(INT_MAX);
00332     int ar = t->arity();
00333     for (int i = 0; i < ar; i++) {
00334         markOpen(t->branch(i));
00335     }
00336 }

Here is the call graph for this function:

Here is the caller graph for this function:

static int orderof ( Tree  t,
Env p 
) [static]

Definition at line 369 of file recursive-tree.cpp.

References Env::fNext, and Env::fTree.

Referenced by recomputeAperture().

00370 {
00371     if (p == NULL) return 0;
00372     if (t == p->fTree) return 1;
00373 
00374     int pos = 1;
00375     while (p != NULL) {
00376         if (t == p->fTree) return pos;
00377         p = p->fNext;
00378         pos++;
00379     }
00380     return 0;
00381 }

Here is the caller graph for this function:

void printSignal ( Tree  sig,
FILE *  out,
int  prec = 0 
)

Definition at line 85 of file sigprint.cpp.

References hd(), isList(), isProj(), isRec(), isRef(), isSigAttach(), isSigBinOp(), isSigDelay1(), isSigDocAccessTbl(), isSigDocConstantTbl(), isSigDocWriteTbl(), isSigFixDelay(), isSigFloatCast(), isSigGen(), isSigInput(), isSigInt(), isSigIntCast(), isSigOutput(), isSigPrefix(), isSigRDTbl(), isSigReal(), isSigTable(), isSigWRTbl(), print(), printSignal(), and tl().

Referenced by calcDeBruijn2Sym(), ScalarCompiler::generateCode(), main(), and printSignal().

00086 {
00087     int     i;
00088     double  r;
00089     Tree     x, y, z, u, le, id;
00090         
00091          if ( isSigInt(sig, &i) )           { fprintf(out, "%d", i);    }
00092     else if ( isSigReal(sig, &r) )          { fprintf(out, "%f", r);    }
00093     else if ( isSigInput(sig, &i) )         { fprintf(out, "IN%d", i);  }
00094     else if ( isSigOutput(sig, &i, x) )     { fprintf(out, "OUT%d := ", i); printSignal(x, out, 0); }
00095     
00096     else if ( isSigBinOp(sig, &i, x, y) )   { 
00097         if (prec > binopprec[i]) fputs("(", out); 
00098         printSignal(x,out,binopprec[i]); fputs(binopname[i], out); printSignal(y, out, binopprec[i]); 
00099         if (prec > binopprec[i]) fputs(")", out);   
00100     }
00101     else if ( isSigDelay1(sig, x) )         { fputs("mem(", out); printSignal(x,out,0); fputs(")", out);        }
00102     else if ( isSigPrefix(sig, x, y) )      { fputs("prefix(", out); printSignal(x,out,0); fputs(",", out);  printSignal(y,out,0); fputs(")", out);     }
00103     else if ( isSigAttach(sig, x, y) )      { fputs("attach(", out); printSignal(x,out,0); fputs(",", out);  printSignal(y,out,0); fputs(")", out);     }
00104     else if ( isSigFixDelay(sig, x, y) )    { 
00105         if (prec > 4) fputs("(", out); 
00106         printSignal(x,out,4); fputs("@", out); printSignal(y, out, 4); 
00107         if (prec > 4) fputs(")", out);  
00108     }
00109 
00110     else if ( isProj(sig, &i, x) )          { printSignal(x,out,prec); fprintf(out, "#%d", i);      }
00111     else if ( isRef(sig, i) )               { fprintf(out, "$%d", i);   }
00112     else if ( isRef(sig, x) )               { print(x, out);            }
00113     else if ( isRec(sig, le))               { fputs("\\_.", out); printSignal(le, out, prec);   }
00114     else if ( isRec(sig, x, le))            { fputs("\\", out); print(x,out); fputs(".", out); printSignal(le, out, prec);  }
00115     
00116     else if ( isSigTable(sig, id, x, y) )   { fputs("table(", out); printSignal(x,out,0); fputc(',', out); printSignal(y,out,0); fputc(')', out);   }
00117     else if ( isSigWRTbl(sig, id, x, y, z) ){ printSignal(x,out,0); fputc('[',out); printSignal(y,out,0); fputs("] := (", out); printSignal(z,out,0); fputc(')', out);   }
00118     else if ( isSigRDTbl(sig, x, y) )       { printSignal(x,out,0); fputc('[', out); printSignal(y,out,0); fputc(']', out);   }
00119 
00120     else if (isSigDocConstantTbl(sig,x,y))  { fputs("sigDocConstantTbl(", out); printSignal(x,out,0); fputc(',', out);
00121                                                                                 printSignal(y,out,0); fputc(')', out);   }
00122 
00123     else if (isSigDocWriteTbl(sig,x,y,z,u)) { fputs("sigDocWriteTbl(", out);    printSignal(x,out,0); fputc(',', out);
00124                                                                                 printSignal(y,out,0); fputc(',', out);
00125                                                                                 printSignal(z,out,0); fputc(',', out);
00126                                                                                 printSignal(u,out,0); fputc(')', out);   }
00127 
00128     else if (isSigDocAccessTbl(sig,x,y))    { fputs("sigDocAccessTbl(", out);   printSignal(x,out,0); fputc(',', out);
00129                                                                                 printSignal(y,out,0); fputc(')', out);   }
00130 
00131 
00132     else if ( isSigGen(sig, x) )            { printSignal(x,out,prec);              }
00133  
00134     else if ( isSigIntCast(sig, x) )        { fputs("int(", out); printSignal(x,out,0); fputs(")", out);        }
00135     else if ( isSigFloatCast(sig, x) )      { fputs("float(", out); printSignal(x,out,0); fputs(")", out);      }
00136 
00137     else if (isList(sig)) {
00138         char sep = '{';
00139         do { 
00140             fputc(sep, out);
00141             printSignal(hd(sig), out, 0);
00142             sep=',';
00143             sig = tl(sig);
00144         } while (isList(sig));
00145         fputc('}', out);
00146     }
00147     else
00148         print(sig, out);
00149 }

Here is the call graph for this function:

Here is the caller graph for this function:

Tree rec ( Tree  var,
Tree  body 
)

create a symbolic recursive tree

Definition at line 88 of file recursive-tree.cpp.

References CTree::setProperty(), and tree().

00089 {
00090     Tree t = tree(SYMREC, var);
00091     t->setProperty(RECDEF, body);
00092     return t;
00093 }

Here is the call graph for this function:

Tree rec ( Tree  body  ) 

create a de Bruijn recursive tree

Definition at line 54 of file recursive-tree.cpp.

References tree().

Referenced by calcDeBruijn2Sym(), calcliftn(), calcsubstitute(), computePrivatisation(), propagate(), sigMap(), and sigMapRename().

00055 {
00056     return tree(DEBRUIJN, body);
00057 }

Here is the call graph for this function:

Here is the caller graph for this function:

static int recomputeAperture ( Tree  t,
Env p 
) [static]

Definition at line 338 of file recursive-tree.cpp.

References CTree::aperture(), CTree::arity(), CTree::branch(), isRec(), isRef(), orderof(), and CTree::setAperture().

Referenced by updateAperture().

00339 {
00340     Tree    var, body;
00341 
00342     if (t->aperture() == 0) return 0;
00343 
00344     if (isRef(t, var)) {
00345 
00346         return orderof(var, env);
00347 
00348     } else if (isRec(t, var, body)) {
00349 
00350         Env e(var,env);
00351         int a = recomputeAperture(body, &e) - 1;
00352         if (a<=0) { /*print(t, stderr);*/ t->setAperture(0); }
00353         return a;
00354 
00355     } else {
00356         // return max aperture of branches
00357         int ma = 0;
00358         int ar = t->arity();
00359         for (int i = 0; i<ar; i++) {
00360             int a = recomputeAperture(t->branch(i), env);
00361             if (ma < a) ma = a;
00362         }
00363         if (ma <= 0)  { /*print(t, stderr);*/ t->setAperture(0); }
00364         return ma;
00365     }
00366 }

Here is the call graph for this function:

Here is the caller graph for this function:

Tree ref ( Tree  id  ) 

create a symbolic recursive reference

Definition at line 106 of file recursive-tree.cpp.

References tree().

00107 {
00108     return tree(SYMREC, id);            // reference to a symbolic id
00109 }

Here is the call graph for this function:

Tree ref ( int  level  ) 

create a de Bruijn recursive reference

Definition at line 64 of file recursive-tree.cpp.

References tree().

Referenced by calcDeBruijn2Sym(), calcliftn(), propagate(), and sigMapRename().

00065 {
00066     assert(level > 0);
00067     return tree(DEBRUIJNREF, tree(level));  // reference to enclosing recursive tree starting from 1
00068 }

Here is the call graph for this function:

Here is the caller graph for this function:

static Tree substitute ( Tree  t,
int  n,
Tree  id 
) [static]

Definition at line 271 of file recursive-tree.cpp.

References calcsubstitute(), CTree::getProperty(), CTree::setProperty(), and tree().

00272 {
00273     Tree S  = tree( Node(SUBSTITUTE), tree(Node(level)), id );
00274     Tree t2 = t->getProperty(S);
00275 
00276     if (!t2) {
00277         t2 = calcsubstitute(t, level, id);
00278         t->setProperty(S, t2);
00279     }
00280     return t2;
00281     
00282 }

Here is the call graph for this function:

void updateAperture ( Tree  t  ) 

Definition at line 320 of file recursive-tree.cpp.

References markOpen(), and recomputeAperture().

00321 {
00322     markOpen(t);
00323     recomputeAperture(t, NULL);
00324 }

Here is the call graph for this function:


Variable Documentation

Sym DEBRUIJN = symbol ("DEBRUIJN")

Definition at line 39 of file recursive-tree.cpp.

Tree DEBRUIJN2SYM = tree(symbol("deBruijn2Sym"))

Definition at line 221 of file recursive-tree.cpp.

Sym DEBRUIJNREF = symbol ("DEBRUIJNREF")

Definition at line 40 of file recursive-tree.cpp.

Tree RECDEF = tree(symbol("RECDEF"))

Definition at line 85 of file recursive-tree.cpp.

Sym SUBSTITUTE = symbol ("SUBSTITUTE")

Definition at line 41 of file recursive-tree.cpp.

Sym SYMLIFTN = symbol ("LIFTN")

Definition at line 45 of file recursive-tree.cpp.

Sym SYMREC = symbol ("SYMREC")

Definition at line 43 of file recursive-tree.cpp.

Sym SYMRECREF = symbol ("SYMRECREF")

Definition at line 44 of file recursive-tree.cpp.

Generated on Thu Jul 15 16:15:45 2010 for FAUST compiler by  doxygen 1.6.3