Annotate a signal expression with recursivness information. More...

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include "recursivness.hh"
#include "property.hh"
#include "signals.hh"
#include "ppsig.hh"
#include "set"

Include dependency graph for recursivness.cpp:

Go to the source code of this file.

Functions
static int	annotate (Tree env, Tree sig)
	Annotate a signal with recursivness.
static int	position (Tree env, Tree t, int p)
	return the position of a signal in the current recursive environment
void	recursivnessAnnotation (Tree sig)
	Annotate a signal with recursivness.
int	getRecursivness (Tree sig)
	Return the recursivness of a previously annotated signal.
Tree	symlistVisit (Tree sig, set< Tree > &visited)
Tree	symlist (Tree sig)
Variables
Tree	RECURSIVNESS = tree(symbol("RecursivnessProp"))
property< Tree >	SymListProp
	return the set of recursive symbols appearing in a signal.

Detailed Description

Annotate a signal expression with recursivness information.

Recursiveness indicates the amount of recursive dependencies of a signal. A closed signal has a recursivness of 0 because is has no recursive dependencies. This means that the succesive samples of this signal can be computed in parallel. In a signal of type .(...F(x)...), F(x) has a recursivness of 1. In a signal of type .(... .(...F(x)...G(y)...)...) F(x) has a recursivness of 2 while G(y) has a recursivness of 1.

Definition in file recursivness.cpp.

Function Documentation

static int annotate	(	Tree	env,
		Tree	sig
	)		`[static]`

Annotate a signal with recursivness.

Parameters:

env	the current environment
sig	signal to annotate

Returns:: recursivness of the signal

Definition at line 89 of file recursivness.cpp.

References cons(), getProperty(), getSubSignals(), isRec(), position(), RECURSIVNESS, setProperty(), tree(), and tree2int().

Referenced by recursivnessAnnotation().

{
    Tree tr, var, body;

    if (getProperty(sig, RECURSIVNESS, tr)) {
        return tree2int(tr);    // already annotated
    } else if (isRec(sig, var, body)) {
        int p = position(env, sig);
        if (p > 0) {
            return p;   // we are inside \x.(...)
        } else {
            int r = annotate(cons(sig, env), body) - 1;
            if (r<0) r=0;
            setProperty(sig, RECURSIVNESS, tree(r));
            return r;
        }
    } else {
        int rmax = 0;
        vector<Tree> v; getSubSignals(sig, v);
        for (unsigned int i=0; i<v.size(); i++) {
            int r = annotate(env, v[i]);
            if (r>rmax) rmax=r;
        }
        setProperty(sig, RECURSIVNESS, tree(rmax));
        return rmax;
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

int getRecursivness ( Tree sig )

Return the recursivness of a previously annotated signal.

An error is generated if the signal has no recursivness property

Parameters:

sig signal

Returns:: recursivness of the signal

Definition at line 72 of file recursivness.cpp.

References getProperty(), RECURSIVNESS, and tree2int().

Referenced by OccMarkup::incOcc().

{
    Tree tr;
    if ( ! getProperty(sig, RECURSIVNESS, tr)) {
        cerr << "Error in getRecursivness of " << *sig << endl;
        exit(1);
    }
    return tree2int(tr);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int position	(	Tree	env,
		Tree	t,
		int	p
	)		`[static]`

return the position of a signal in the current recursive environment

Parameters:

env	the current recursive environment of the signal
t	signal we want to know the position

Returns:: the position in the recursive environment

Definition at line 125 of file recursivness.cpp.

References hd(), isNil(), and tl().

Referenced by annotate().

{
    if (isNil(env)) return 0;   // was not in the environment
    if (hd(env) == t) return p;
    else return position (tl(env), t, p+1);
}

Here is the call graph for this function:

Here is the caller graph for this function:

void recursivnessAnnotation ( Tree sig )

Annotate a signal with recursivness.

Should be used before calling getRecursivness

Parameters:

sig	signal to annotate

Definition at line 59 of file recursivness.cpp.

References annotate(), and nil.

Referenced by DocCompiler::annotate(), ScalarCompiler::prepare(), and ScalarCompiler::prepare2().

{
    annotate(nil, sig);
}

Here is the call graph for this function:

Here is the caller graph for this function:

Tree symlist ( Tree sig )

Definition at line 174 of file recursivness.cpp.

References property< Tree >::get(), property< Tree >::set(), SymListProp, and symlistVisit().

Referenced by Klass::closeLoop(), and typeAnnotation().

{
    Tree    S;
    if (!SymListProp.get(sig, S)) {
        set<Tree> visited;
        S = symlistVisit(sig, visited);
        SymListProp.set(sig, S);
    }
    //cerr << "SYMLIST " << *S << " OF " << ppsig(sig) << endl;
    return S;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Tree symlistVisit	(	Tree	sig,
		set< Tree > &	visited
	)

Definition at line 146 of file recursivness.cpp.

References property< Tree >::get(), getSubSignals(), isRec(), len(), nil, nth(), setUnion(), singleton(), and SymListProp.

Referenced by symlist().

{
    Tree S;
    if (SymListProp.get(sig, S)) {
        return S;
    } else if ( visited.count(sig) > 0 ){
        return nil;
    } else {
        visited.insert(sig);
        Tree id, body;
        if (isRec(sig, id, body)) {
            Tree U = singleton(sig);
            for (int i=0; i<len(body); i++) {
                U = setUnion(U, symlistVisit(nth(body,i), visited));
            }
            return U;
        } else {
            vector<Tree> subsigs;
            int n = getSubSignals(sig, subsigs, true); // il faut visiter aussi les tables
            Tree U = nil;
            for (int i=0; i<n; i++) {
                U = setUnion(U, symlistVisit(subsigs[i], visited));
            }
            return U;
        }
    }
}