#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include "tlib.hh"
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")) |
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 }
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 }
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 }
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 }
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 }
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().
is t a symbolic recursive reference
Definition at line 111 of file recursive-tree.cpp.
References isTree().
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 }
Definition at line 149 of file recursive-tree.cpp.
References liftn().
Referenced by listLift(), and propagate().
00149 { return liftn(t, 1); }
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 }
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 }
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 }
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 }
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 }
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().
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 }
create a symbolic recursive reference
Definition at line 106 of file recursive-tree.cpp.
References tree().
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 }
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 }
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 }
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.
Definition at line 85 of file recursive-tree.cpp.
Sym SUBSTITUTE = symbol ("SUBSTITUTE") |
Definition at line 41 of file recursive-tree.cpp.
Definition at line 45 of file recursive-tree.cpp.
Definition at line 43 of file recursive-tree.cpp.
Definition at line 44 of file recursive-tree.cpp.