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. More...

static int	position (Tree env, Tree t, int p)
	return the position of a signal in the current recursive environment More...

void	recursivnessAnnotation (Tree sig)
	Annotate a signal with recursivness. More...

int	getRecursivness (Tree sig)
	Return the recursivness of a previously annotated signal. More...

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. More...

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;
         }
     }
 }