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 More...
bool	isRec (Tree t, Tree &body)
	is t a de Bruijn recursive tree More...
Tree	ref (int level)
	create a de Bruijn recursive reference More...
bool	isRef (Tree t, int &level)
	is t a de Bruijn recursive reference More...
Tree	rec (Tree var, Tree body)
	create a symbolic recursive tree More...
bool	isRec (Tree t, Tree &var, Tree &body)
	is t a symbolic recursive tree More...
Tree	ref (Tree id)
	create a symbolic recursive reference More...
bool	isRef (Tree t, Tree &v)
	is t a symbolic recursive reference More...
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().

{
    Tree    body, var;
    int     i;

    if (isRec(t,body)) {

        var = tree(unique("W"));
        return rec(var, deBruijn2Sym(substitute(body,1,ref(var))));

    } else if (isRef(t,var)) {

        return t;

    } else if (isRef(t,i)) {

        fprintf(stderr, "ERREUR, une reference de Bruijn touvee ! : ");
        printSignal(t, stderr);
        fprintf(stderr, ")\n");
        exit(1);
        return t;

    } else {

        //Tree  br[4];
        int     a = t->arity();
        tvec    br(a);

        for (int i = 0; i < a; i++) {
            br[i] = deBruijn2Sym(t->branch(i));
        }
        //return CTree::make(t->node(), a, br);
        return CTree::make(t->node(), br);
    }
}

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().

{
    int     n;
    Tree    u;

    if (isClosed(t)) {

        return t;

    } else if (isRef(t,n)) {

        if (n < threshold) {
            // it is a bounded reference
            return t;
        } else {
            // it is a free reference
            return ref(n+1);
        }

    } else if (isRec(t,u)) {

        return rec(liftn(u, threshold+1));

    } else {
        int n = t->arity();
        //Tree  br[4];
        tvec    br(n);
        for (int i = 0; i < n; i++) {
            br[i] = liftn(t->branch(i), threshold);
        }
        //return CTree::make(t->node(), n, br);
        return CTree::make(t->node(), br);
    }

}

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().

{
    int     l;
    Tree    body;

    if (t->aperture()<level) {
//      fprintf(stderr, "aperture %d < level %d !!\n", t->aperture(), level);
        return t;
    }
    if (isRef(t,l))          return (l == level) ? id : t;
    if (isRec(t,body))       return rec(substitute(body, level+1, id));

    int     ar = t->arity();
    //Tree  br[4];
    tvec    br(ar);
    for (int i = 0; i < ar; i++) {
        br[i] = substitute(t->branch(i), level, id);
    }
    //return CTree::make(t->node(), ar, br);
    return CTree::make(t->node(), br);
}

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().

{
    assert(isClosed(t));
    Tree t2 = t->getProperty(DEBRUIJN2SYM);

    if (!t2) {
        t2 = calcDeBruijn2Sym(t);
        t->setProperty(DEBRUIJN2SYM, t2);
    }
    return t2;
}

Here is the call graph for this function:

Here is the caller 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(), VectorCompiler::generateCodeRecursions(), ScalarCompiler::generateRecProj(), DocCompiler::generateRecProj(), getSubSignals(), infereSigOrder(), infereSigType(), ppsig::print(), printSignal(), recdraw(), recomputeAperture(), sigLabel(), sigMap(), sigMapRename(), symlistVisit(), typeAnnotation(), and sigvisitor::visit().

{
    return isTree(t, DEBRUIJN, body);
}

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().

{
    if (isTree(t, SYMREC, var)) {
        body = t->getProperty(RECDEF);
        return true;
    } else {
        return false;
    }
}

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().

{
    Tree    u;

    if (isTree(t, DEBRUIJNREF, u)) {
        return isInt(u->node(), &level);
    } else {
        return false;
    }
}

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().

{
    return isTree(t, SYMREC, v);
}

Here is the call graph for this function:

Tree lift

(

Tree

t

)

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

References liftn().

Referenced by listLift(), and realPropagate().

{ 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().

{
    Tree L  = tree( Node(SYMLIFTN), tree(Node(threshold)) );
    Tree t2 = t->getProperty(L);

    if (!t2) {
        t2 = calcliftn(t, threshold);
        t->setProperty(L, t2);
    }
    return t2;
    
}

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().

{
    if (t->aperture() == INT_MAX) return;
    t->setAperture(INT_MAX);
    int ar = t->arity();
    for (int i = 0; i < ar; i++) {
        markOpen(t->branch(i));
    }
}

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().

{
    if (p == NULL) return 0;
    if (t == p->fTree) return 1;

    int pos = 1;
    while (p != NULL) {
        if (t == p->fTree) return pos;
        p = p->fNext;
        pos++;
    }
    return 0;
}

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().

{
    int     i;
    double  r;
    Tree     x, y, z, u, le, id;
        
         if ( isSigInt(sig, &i) )           { fprintf(out, "%d", i);    }
    else if ( isSigReal(sig, &r) )          { fprintf(out, "%f", r);    }
    else if ( isSigInput(sig, &i) )         { fprintf(out, "IN%d", i);  }
    else if ( isSigOutput(sig, &i, x) )     { fprintf(out, "OUT%d := ", i); printSignal(x, out, 0); }
    
    else if ( isSigBinOp(sig, &i, x, y) )   { 
        if (prec > binopprec[i]) fputs("(", out); 
        printSignal(x,out,binopprec[i]); fputs(binopname[i], out); printSignal(y, out, binopprec[i]); 
        if (prec > binopprec[i]) fputs(")", out);   
    }
    else if ( isSigDelay1(sig, x) )         { fputs("mem(", out); printSignal(x,out,0); fputs(")", out);        }
    else if ( isSigPrefix(sig, x, y) )      { fputs("prefix(", out); printSignal(x,out,0); fputs(",", out);  printSignal(y,out,0); fputs(")", out);     }
    else if ( isSigAttach(sig, x, y) )      { fputs("attach(", out); printSignal(x,out,0); fputs(",", out);  printSignal(y,out,0); fputs(")", out);     }
    else if ( isSigFixDelay(sig, x, y) )    { 
        if (prec > 4) fputs("(", out); 
        printSignal(x,out,4); fputs("@", out); printSignal(y, out, 4); 
        if (prec > 4) fputs(")", out);  
    }

    else if ( isProj(sig, &i, x) )          { printSignal(x,out,prec); fprintf(out, "#%d", i);      }
    else if ( isRef(sig, i) )               { fprintf(out, "$%d", i);   }
    else if ( isRef(sig, x) )               { print(x, out);            }
    else if ( isRec(sig, le))               { fputs("\\_.", out); printSignal(le, out, prec);   }
    else if ( isRec(sig, x, le))            { fputs("\\", out); print(x,out); fputs(".", out); printSignal(le, out, prec);  }
    
    else if ( isSigTable(sig, id, x, y) )   { fputs("table(", out); printSignal(x,out,0); fputc(',', out); printSignal(y,out,0); fputc(')', out);   }
    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);   }
    else if ( isSigRDTbl(sig, x, y) )       { printSignal(x,out,0); fputc('[', out); printSignal(y,out,0); fputc(']', out);   }

    else if (isSigDocConstantTbl(sig,x,y))  { fputs("sigDocConstantTbl(", out); printSignal(x,out,0); fputc(',', out);
                                                                                printSignal(y,out,0); fputc(')', out);   }

    else if (isSigDocWriteTbl(sig,x,y,z,u)) { fputs("sigDocWriteTbl(", out);    printSignal(x,out,0); fputc(',', out);
                                                                                printSignal(y,out,0); fputc(',', out);
                                                                                printSignal(z,out,0); fputc(',', out);
                                                                                printSignal(u,out,0); fputc(')', out);   }

    else if (isSigDocAccessTbl(sig,x,y))    { fputs("sigDocAccessTbl(", out);   printSignal(x,out,0); fputc(',', out);
                                                                                printSignal(y,out,0); fputc(')', out);   }


    else if ( isSigGen(sig, x) )            { printSignal(x,out,prec);              }
 
    else if ( isSigIntCast(sig, x) )        { fputs("int(", out); printSignal(x,out,0); fputs(")", out);        }
    else if ( isSigFloatCast(sig, x) )      { fputs("float(", out); printSignal(x,out,0); fputs(")", out);      }

    else if (isList(sig)) {
        char sep = '{';
        do { 
            fputc(sep, out);
            printSignal(hd(sig), out, 0);
            sep=',';
            sig = tl(sig);
        } while (isList(sig));
        fputc('}', out);
    }
    else
        print(sig, out);
}

Here is the call graph for this function:

Here is the caller 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(), realPropagate(), sigMap(), and sigMapRename().

{
    return tree(DEBRUIJN, body);
}

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().

{
    Tree t = tree(SYMREC, var);
    t->setProperty(RECDEF, body);
    return t;
}

Here is the call 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().

{
    Tree    var, body;

    if (t->aperture() == 0) return 0;

    if (isRef(t, var)) {

        return orderof(var, env);

    } else if (isRec(t, var, body)) {

        Env e(var,env);
        int a = recomputeAperture(body, &e) - 1;
        if (a<=0) { /*print(t, stderr);*/ t->setAperture(0); }
        return a;

    } else {
        // return max aperture of branches
        int ma = 0;
        int ar = t->arity();
        for (int i = 0; i<ar; i++) {
            int a = recomputeAperture(t->branch(i), env);
            if (ma < a) ma = a;
        }
        if (ma <= 0)  { /*print(t, stderr);*/ t->setAperture(0); }
        return ma;
    }
}

Here is the call graph for this function:

Here is the caller 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(), realPropagate(), and sigMapRename().

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

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().

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

Here is the call 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().

Referenced by calcDeBruijn2Sym(), and calcsubstitute().

{
    Tree S  = tree( Node(SUBSTITUTE), tree(Node(level)), id );
    Tree t2 = t->getProperty(S);

    if (!t2) {
        t2 = calcsubstitute(t, level, id);
        t->setProperty(S, t2);
    }
    return t2;
    
}

Here is the call graph for this function:

Here is the caller graph for this function:

void updateAperture

(

Tree

t

)

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

References markOpen(), and recomputeAperture().

{
    markOpen(t);
    recomputeAperture(t, NULL);
}

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.