Polaris: EvolutionGraph Class Reference

EvolutionGraph Class Reference

A graph in which nodes are program values (as SSA symbols) and edges are evolutions. More...

#include <EvolutionGraph.h>

Inheritance diagram for EvolutionGraph:

[legend]List of all members.


Public Types
typedef map< const Symbol , map< const Symbol , Evolution< Expression > > >	EvolutionMap
enum	SequenceType { ST_UNKNOWN, ST_INCREASING, ST_NONDECREASING, ST_NONINCREASING, ST_DECREASING }
Public Member Functions
Expression *	_global_range_per_iteration (Expression expr, DoStmt domain)
	Compute the range of an expression at the given level, but for just one iteration.
Expression *	_global_range (Expression *expr)
	Compute the range of an expression at the outermost level where at least one symbol within it is defined.
Expression *	_global_range (Expression expr, DoStmt domain)
	Compute the range of an expression at the given level.
Expression *	range_from_input (Symbol &s)
	Compute the range of the given expression if it can be inferred from input values only. If so, do not express the input values using RangeDictionary. Otherwise, return 0.
	EvolutionGraph (ProgramUnit &pgm, Statement *loop=0)
	Construct the graph.
	~EvolutionGraph ()
	Destroy the graph.
void	print_graph (const char *filename)
	Prints the graph to a DOT (GraphViz) file.
Expression *	min_distance (const Symbol &left, const Symbol &right)
	Returns the minimum distance between two elements in left and right across two successive iterations of '_loop'.
bool	increasing (const Symbol &value)
	Returns true if the given variables takes constantly increasing values within the given loop. If the value is not defined within the loop, it returns true.
SequenceType	sequence_type (const Symbol &value)
	Returns sequence type for the given symbol.
void	enhance (map< Symbol , Symbol > &imposed_edges)
	Conditional pruning.
void	undo_enhancement ()
	Restore after conditional pruning.
void	trace_from_input (Symbol node, pair< RangeExpr , bool > &range, list< Symbol * > &trace)
	Find all possible traces from input values to given node so that the input value + evolutions on the road are within the given range.
void	traces_from_mu (Symbol node, pair< RangeExpr , bool > &range, map< Symbol , list< list< Symbol > > > &trace)
	Find traces from all MUs to given node within given range.
void	perfect_trace_from_mu (Symbol node, pair< RangeExpr , bool > &total_range, list< Symbol * > &trace)
	Finds a perfect backwards trace (a trace that must repeat in each iteration) given the range for a BACK node.
void	perfect_trace_from_mu (Symbol mu, Symbol node, const Expression &given_length, list< Symbol * > &trace)
	Composes a perfect backwards trace.
void	_possible_ranges (const Symbol &sym, list< pair< list< Symbol * >, RangeExpr * > > &result)
	Finds all the ways to compute the value of the given 'sym'. Returns the list of pairs(path, result). 'path' may be an INPUT symbol, a MU symbol, or a sequence INPUT, MU1, MU2, ...
void	backtrack (Symbol node, pair< RangeExpr , bool > &range, list< Symbol * > &trace)
	Finds all possible back traces.
void	get_trace_details (list< Symbol * > &trace, Evolution< Expression > &ev, Expression *&length, List< Expression > &preds)
	Given a trace, it returns the aggregated evolution across it as a range, the accurate length of the trace as an expression, and the predicates collected at GAMMA sites.
void	export_evolutions (Symbol node, map< const Symbol , Evolution< Expression > > &muevs, list< pair< const Symbol *, Evolution< Expression > > > &ievs)
	Export evolution knowledge for a node.
bool	find_unique_mu (Symbol node, Symbol &mu, Symbol *&back)
	Return the reaching MU and BACK for this intermediate symbol and return TRUE if they are unique. Also, only return TRUE if MU cannot be reached from any other MU. Also, only return TRUE if MU cannot be reached from any input.
Expression *	substitute (Symbol *given)
	Performs forward substitution on demand.
Protected Member Functions
void	_p_abort (const char file, int line, const char str) __attribute__((noreturn))
	Custom program abort routine.
bool	_loop_invariant (const Expression &expr)
bool	_contains_unknown_variants (const Expression &expr)
	Returns whether given expression contains at least one symbol that is loop variant and is not scalar or is not integer.
void	_add_evolution (const Symbol from, const Symbol to, const Evolution< Expression > &evolution)
	Adds an edge if both nodes are in the graph. If the 'from' node is outside the graph, it adds it to the input value set corresponding to node 'to'.
void	_add_evolutions (const Expression &from, const Symbol *to)
	Extracs evolutions from "to = from".
void	_add_evolutions (AssignmentStmt &stmt)
	Extracts all evolutions from the given assignment statement.
void	_add_evolutions (DoStmt &loop)
	Add evolutions from inner loop.
void	_add_evolutions (Statement &callsite, ProgramUnit &callee)
	Add evolutions from called subprogram.
void	_add_evolutions (Statement &first, Statement &last)
	Add evolutions for this loop level.
bool	_add_approximations ()
	Add approximations for evolutions of this type: var1 = var2 + var3.
void	_build ()
	Build the graph.
void	_verify_preconditions ()
	Make sure the graph shape fits our assumptions.
void	_topsort (vector< unsigned int > &topsorted, bool forward=true)
	Sort the vertices topologically. This leads to O(n) shortest path computation.
bool	_back_edge (const Symbol , const Symbol )
	Is there a loop back edge from first to second argument?
bool	_relax (unsigned int nleft, unsigned int nright, const EdgeType &ev, RELAX_OP op, vector< Expression * > &best_path)
	Shortest path single step relaxation (as in bellman-ford).
void	_bellman_ford (unsigned int source, vector< Evolution< Expression > > &best, vector< unsigned int > &topsorted, bool forward=true)
void	_compact_zero_paths ()
	Eliminate all nodes that are on a path containing only 0-valued edges (and they are not on any other paths).
void	_compute_acyclic_evolutions ()
	Computes all the evolutions in the graph. It builds the following databases: _mu_evolutions, _evolutions_from_mu, _evolutions_to_mu.
void	_compute_cyclic_evolutions (EvolutionMap &, map< const Symbol *, Evolution< Expression > > &)
	Aggregates the effect of evolutions across all iterations.
Expression *	_local_range (const Symbol &sym)
	Compute the range of a variable within myself.
Expression *	_eliminate_vars (Expression expr, set< Symbol > &syms)
	Compute the range of an expression.
Protected Attributes
bool	_acyclic_evs_computed
bool	_cyclic_evs_computed
stack< map< const Symbol , const Symbol > >	_newly_imposed_edges

Detailed Description

A graph in which nodes are program values (as SSA symbols) and edges are evolutions.

Definition at line 73 of file EvolutionGraph.h.

Member Typedef Documentation

typedef map<const Symbol*, map<const Symbol*, Evolution<Expression> > > EvolutionGraph::EvolutionMap

Definition at line 84 of file EvolutionGraph.h.

Member Enumeration Documentation

enum EvolutionGraph::SequenceType

Enumeration values:

ST_UNKNOWN Anything.

ST_INCREASING 1, 2, 5, 7

ST_NONDECREASING 1, 2, 2, 4

ST_NONINCREASING 4, 2, 2, 1

ST_DECREASING 7, 5, 2, 1

Definition at line 76 of file EvolutionGraph.h.

Constructor & Destructor Documentation

EvolutionGraph::EvolutionGraph ( ProgramUnit & pgm,

Statement * loop = 0

) [inline]

Construct the graph.

Definition at line 558 of file EvolutionGraph.h.
References _acyclic_evs_computed, _build(), _cyclic_evs_computed, List< T >::last_ref(), loop(), ProgramUnit::range_dict(), ProgramUnit::range_dict_guarded(), ProgramUnit::range_dict_valid(), and ProgramUnit::stmts().

EvolutionGraph::~EvolutionGraph ( ) [inline]

Destroy the graph.

Definition at line 575 of file EvolutionGraph.h.

Member Function Documentation

void EvolutionGraph::_p_abort ( const char * file,

int line,

const char * str

) [protected]

Custom program abort routine.

Definition at line 3609 of file EvolutionGraph.cc.
References line, loop_name(), print_graph(), program(), and ProgramUnit::routine_name_ref().

bool EvolutionGraph::_loop_invariant ( const Expression & expr ) [protected]

Definition at line 1046 of file EvolutionGraph.cc.
References Iterator< T >::current(), loop_variant(), referred_symbols(), and Iterator< T >::valid().
Referenced by _add_evolutions().

bool EvolutionGraph::_contains_unknown_variants ( const Expression & expr ) [protected]

Returns whether given expression contains at least one symbol that is loop variant and is not scalar or is not integer.

Definition at line 1061 of file EvolutionGraph.cc.
References Iterator< T >::current(), Type::data_type(), INTEGER_TYPE, Symbol::is_scalar(), loop_variant(), referred_symbols(), Symbol::type(), and Iterator< T >::valid().
Referenced by _add_evolutions().

void EvolutionGraph::_add_evolution ( const Symbol * from,

const Symbol * to,

const Evolution< Expression > & ev

) [protected]

Adds an edge if both nodes are in the graph. If the 'from' node is outside the graph, it adds it to the input value set corresponding to node 'to'.
cerr<<"\nAdd evolution from "<<from->name_ref() <<" to "<<to->name_ref();
cerr<<"\n\n\tBOO!";
Definition at line 1029 of file EvolutionGraph.cc.
References Graph< Symbol *, Evolution< Expression > >::add_edge(), and Graph< Symbol *, Evolution< Expression > >::contains().
Referenced by _add_approximations(), _add_evolutions(), and _compact_zero_paths().

void EvolutionGraph::_add_evolutions ( const Expression & rhs,

const Symbol * to

) [protected]

Extracs evolutions from "to = from".
If rhs is loop invariant, then no evolution is added, but the node must be marked as input.
cerr<<"\n1. in loop "<<loop_name(_loop) <<", set input value for "<<to->name_ref()<<" to "<<rhs;
If rhs contains any loop variants that are not scalar integers, then this node is marked as input with an initial value of Infinity.
cerr<<"\n\tIS UNKNOWN";
When it gets here: 1. All symbols in rhs are either loop invariant or evgraph nodes. 2. There is at least an evgraph node in rhs.
... Check for special case: x = i
... silvius: assume the loop has been normalized.
_input_values[to]=evolution(_loop->init(), _loop->limit());
... 0 edge.
cerr<<"\n to = "<<to->name_ref()<<", rhs = "<<rhs;
... Skip back edge. Input value is considered only when we compute ... the aggregated cyclic evolutions.
cerr<<"\neta gate: "<<rhs;
... Let it be treated as a regular PHI node.
... 0 edges.
cerr<<"\n\tto = "<<node_name(to) <<", rhs = "<<rhs <<", phi entries = "<<entries;
if (gsa_base(sit.current())!=&sit.current()){
}
... For x = y + exp, add y -> x.
... If it gets here, we could not analyze it well.
cerr<<"\n2. in loop "<<loop_name(_loop) <<", set input value for "<<to->name_ref()<<" to "<<rhs;
... For x = y - exp, add y -> x.
... If it gets here, we could not analyze it well.
... Unknown.
Definition at line 849 of file EvolutionGraph.cc.
References _add_evolution(), _contains_unknown_variants(), _loop_invariant(), ADD_OP, Expression::clone(), constant(), Graph< Symbol *, Evolution< Expression > >::contains(), Iterator< T >::current(), List< T >::entries(), ETA_OP, evolution(), List< T >::first_ref(), GAMMA_OP, get_phinode_entries(), ID_OP, Statement::index(), INTEGER_CONSTANT_OP, is_logical_false(), is_true(), List< T >::last_ref(), MU_OP, mul(), Expression::op(), simplify(), SUB_OP, Expression::symbol(), THETA_OP, Iterator< T >::valid(), Expression::value(), and ZERO.
Referenced by _add_evolutions(), and _build().

void EvolutionGraph::_add_evolutions ( AssignmentStmt & stmt ) [protected]

Extracts all evolutions from the given assignment statement.
cerr<<"\n\nlhs="<<lhs<<", rhs="<<rhs;
Definition at line 1125 of file EvolutionGraph.cc.
References _add_evolutions(), Type::data_type(), ID_OP, INTEGER_TYPE, Symbol::is_scalar(), Expression::op(), Expression::symbol(), and Symbol::type().

void EvolutionGraph::_add_evolutions ( DoStmt & loop ) [protected]

Add evolutions from inner loop.
Get graph for inner loop.
Get overall evolutions for the inner loop.
cerr<<"\ninner_ivs: "; print_input_values(inner_ivs, "", cerr);
Copy evolutions to outer domain.
Add input relations.
Definition at line 1091 of file EvolutionGraph.cc.
References _add_evolution(), _compute_cyclic_evolutions(), _get_eg(), and loop().

void EvolutionGraph::_add_evolutions ( Statement & callsite,

ProgramUnit & callee

) [protected]

Add evolutions from called subprogram.
1. There is a path from MU to BACK. (T/F) 2. There is a path from INPUT to BACK (T/F)
Get graph for called subprogram.
For now, the return value is set to [-Inf:+Inf].
silvius: must check here for a particular case: when a scalar integer is passed to a routine that sees it as something else. If so, we need to add unknown evolutions for them.
Forall MU symbols in called routine.
cerr<<"\n\nMU = "<<node_name(mu); ... Find corresponding symbol in caller.
cerr<<"\nActual = "<<actualsym->name_ref() <<" at call site: "<<callsite;
if (actualsym==0){ / ... This is just an IN argument, cannot carry an evolution. cerr<<"\nStmt: "<<callsite <<"\nactual: "<<*actual; }
... There is a path from incoming((*it).first) to outgoing(mu).
cerr<<"\n\n\npgm = "<<_pgm->routine_name_ref(); cerr<<"\ncallsite = "<<callsite; cerr<<"\nact = "<<*actualsym;
cerr<<"\nActual = "<<actualsym->name_ref() <<" at call site: "<<callsite;
print_evolutions(egloop->_input2mu_evolutions, "I2MU", cerr);
... There is a path from an input node to an outgoing.
... Get first evolution from input.
... Merge it with any other evolutions from other input nodes.
Definition at line 1170 of file EvolutionGraph.cc.
References _add_evolution(), _get_eg(), _input2mu_evolutions, _input_values, _mu_evolutions, _ra, ASSIGNMENT_STMT, Type::data_type(), evolution(), FUNCTION_CALL_OP, get_in(), get_in_out(), get_out(), get_translated_evolution(), gsa_base(), ID_OP, INTEGER_TYPE, Symbol::is_scalar(), merge_unite(), mu(), mu_this_loop, Graph< Node, Edge >::nodes(), Expression::op(), Expression::symbol(), translate_var(), and Symbol::type().

void EvolutionGraph::_add_evolutions ( Statement & first,

Statement & last

) [protected]

Add evolutions for this loop level.
Add evolutions.
... Call site, must import evolutions from called subprogram.
... Skip THETA assignments, they have been handled by now.
... Will add unknown input values for all definitions.
... tmp results
cerr<<*stit<<flush; print_graph("eg.dot"); system("dot -Tps -o t.ps eg.dot"); int tmp; cin>>tmp;
Definition at line 1292 of file EvolutionGraph.cc.
References _add_evolutions(), ASSIGNMENT_STMT, Expression::base_variable_ref(), called_pgm(), Iterator< T >::current(), Type::data_type(), DO_STMT, e, evolution(), Statement::follow_ref(), INTEGER_TYPE, Symbol::is_scalar(), Statement::next_ref(), Expression::op(), Statement::out_refs(), Statement::rhs(), Statement::stmt_class(), THETA_OP, Expression::type(), and Iterator< T >::valid().

bool EvolutionGraph::_add_approximations ( ) [protected]

Add approximations for evolutions of this type: var1 = var2 + var3.
At this point, we have set the value of var1 as [-Inf:Inf]. In case we know the range for var3, add an evolution from var2 to var1 with value range(var3).
Returns true if it added at least an approximation.
Definition at line 500 of file EvolutionGraph.cc.
References _add_evolution(), _bellman_ford(), _eg_forward_substitute(), _local_range(), _topsort(), ADD_OP, Expression::arg_list(), ASSIGNMENT_STMT, Expression::clone(), constant(), Graph< Symbol *, Evolution< Expression > >::contains(), Type::data_type(), DO_STMT, List< T >::entries(), evolution(), List< T >::first_ref(), Statement::follow_ref(), ID_OP, IF_STMT, Graph< Symbol *, Evolution< Expression > >::index(), infinity(), INFINITY_OP, INTEGER_CONSTANT_OP, INTEGER_TYPE, List< T >::last_ref(), RangeExpr::lb(), Statement::lhs(), Statement::matching_endif_ref(), Evolution< Value >::max_difference(), Evolution< Value >::min_difference(), MULT_OP, Statement::next_ref(), Expression::op(), POS_EXPR, RANGE_OP, Statement::rhs(), RangeComparator::sign(), Statement::stmt_class(), ProgramUnit::stmts(), Expression::symbol(), Expression::type(), RangeExpr::ub(), Expression::value(), and WHILE_STMT.
Referenced by _build().

void EvolutionGraph::_build ( ) [protected]

Build the graph.
cerr<<"\nGenerating EG for "<<_pgm->routine_name_ref() <<" and loop "<<loop_name(_loop); _pgm->write(cerr); Mark domain.
Add nodes. Add integer scalars and arrays only.
... Add only MU values for inner DO stmts.
cerr<<"\nAt statement: "<<*stit;
... If this is a call site, do not add the ones that will not ... be modified based on MAYMODs.
... Not modified.
cerr<<"\n\tAdding "<<node_name(sym);
If it is the whole program unit, add base gsa symbols for all commons and formals that may be defined in this subprogram. silvius: actually, add them all even if they are not defined because they may carry values in.
Set mu nodes.
... Find MU nodes defined in this loop.
cerr<<"\n\nIn routine "<<_pgm->routine_name_ref();
... Set as MU all symbols that may carry a definition outside the routine.
cerr<<"\n\tAdding mu node "<<(*it)->name_ref();
cerr<<" with index value "<<imu;
Add back edges.
cerr<<"\n\tAdding back edge from "; cerr<<node_name(outgoing_sym)<<" to "; cerr<<node_name(nodes()[incoming])<<endl;
cerr<<"\n\tAdding back node "<<outgoing_sym->name_ref();
Add evolutions.
Store indices of all nodes.
Set as input all nodes that have an input value AND are not MU.
... Compute evolutions.
... Add approximations.
... We have to recompute.
Draw the graph.
Definition at line 635 of file EvolutionGraph.cc.
References _add_approximations(), _add_evolutions(), _compute_acyclic_evolutions(), Graph< Symbol *, Evolution< Expression > >::add_node(), Expression::arg_list(), ASSIGNMENT_STMT, Expression::base_variable_ref(), Symbol::common_ref(), DictionaryIter< T >::current(), Iterator< T >::current(), Type::data_type(), DO_STMT, List< T >::first_ref(), Statement::follow_ref(), Symbol::formal(), FUNCTION_CALL_OP, Statement::get_loop_name(), gsa_base(), has_maymod(), Graph< Symbol *, Evolution< Expression > >::index(), Statement::index(), INTEGER_TYPE, Symbol::is_scalar(), is_var_in_maymod(), Symtab::iterator(), last_gsa_symbol(), List< T >::last_ref(), Statement::lhs(), loop(), MU_OP, Statement::next_ref(), Graph< Symbol *, Evolution< Expression > >::nodes(), Expression::op(), Statement::out_refs(), Expression::parameters_guarded(), print_graph(), Statement::rhs(), ProgramUnit::routine_name_ref(), Statement::stmt_class(), ProgramUnit::stmts(), Expression::symbol(), ProgramUnit::symtab(), Expression::type(), Symbol::type(), KeyIterator< String, T >::valid(), and Iterator< T >::valid().
Referenced by EvolutionGraph().

void EvolutionGraph::_verify_preconditions ( ) [protected]

Make sure the graph shape fits our assumptions.

Warning:
silvius: must state all assumptions here.

Definition at line 1347 of file EvolutionGraph.cc.
References evolution(), get_imu(), and Graph< Symbol *, Evolution< Expression > >::index().
Referenced by _compute_cyclic_evolutions().

void EvolutionGraph::_topsort ( vector< unsigned int > & topsorted,

bool forward = true

) [protected]

Sort the vertices topologically. This leads to O(n) shortest path computation.
First compute the in-degrees for every node.
... For each outgoing edge.
Now start at root nodes and add nodes to 'topsort' as they are available. Use indegrees as consumable dependency DAG.
... For each outgoing edge.
Sanity check.
Definition at line 346 of file EvolutionGraph.cc.
References _back_edge(), Graph< Symbol *, Evolution< Expression > >::get_edges(), Graph< Symbol *, Evolution< Expression > >::get_reversed_edges(), and Graph< Symbol *, Evolution< Expression > >::nodes().
Referenced by _add_approximations(), and _compute_acyclic_evolutions().

bool EvolutionGraph::_back_edge ( const Symbol * left,

const Symbol * right

) [protected]

Is there a loop back edge from first to second argument?
Check for loop index.
General.
Definition at line 325 of file EvolutionGraph.cc.
References Statement::index(), and Expression::symbol().
Referenced by _topsort().

bool EvolutionGraph::_relax ( unsigned int nleft,

unsigned int nright,

const EdgeType & ev,

RELAX_OP op,

vector< Expression * > & best_path

) [protected]

Shortest path single step relaxation (as in bellman-ford).
First check whether there is a path to nleft. Otherwise we will not perform the relaxation in order to avoid operations like (-Inf + Inf).
Get range information.
At this time we have best_left, best_right, and weight.
... Path through nleft is better.
... Previous path is better.
has_relaxed==false && has_not_relaxed==false => cannot compare.
... Did relax.
... Did not relax.
... We cannot tell which is shorter, will take the best.
Definition at line 187 of file EvolutionGraph.cc.
References add(), Expression::clone(), DO_STMT, DefLocMap::find_ref(), ProgramUnit::gsa_deflocs_guarded(), INFINITY_OP, List< T >::last_ref(), make_best(), MAX_OP, MIN_OP, Graph< Symbol *, Evolution< Expression > >::nodes(), Expression::op(), ProgramUnit::range_dict_guarded(), range_stmt(), Expression::sign(), simplify(), Statement::stmt_class(), DefLoc::stmt_guarded(), DefLoc::stmt_valid(), and ProgramUnit::stmts().
Referenced by _bellman_ford().

void EvolutionGraph::_bellman_ford ( unsigned int source,

vector< Evolution< Expression > > & best,

vector< unsigned int > & topsorted,

bool forward = true

) [protected]

Clear result list just in case.
Initialize shortest/longest path for every destination node.
Now chew it up.
... For each incident edge.
... Relaxation.
Save result.
Sanity check.
Definition at line 268 of file EvolutionGraph.cc.
References _relax(), constant(), evolution(), Graph< Symbol *, Evolution< Expression > >::get_edges(), Graph< Symbol *, Evolution< Expression > >::get_reversed_edges(), infinity(), MAX_OP, MIN_OP, and Graph< Symbol *, Evolution< Expression > >::nodes().
Referenced by _add_approximations(), and _compute_acyclic_evolutions().

void EvolutionGraph::_compact_zero_paths ( ) [protected]

Eliminate all nodes that are on a path containing only 0-valued edges (and they are not on any other paths).
For now, only if they start at ZERO.
Definition at line 1389 of file EvolutionGraph.cc.
References _add_evolution(), Graph< Symbol *, Evolution< Expression > >::get_edges(), Graph< Symbol *, Evolution< Expression > >::index(), loop(), Graph< Symbol *, Evolution< Expression > >::nodes(), Graph< Symbol *, Evolution< Expression > >::remove_edges(), and ZERO.

void EvolutionGraph::_compute_acyclic_evolutions ( ) [protected]

Computes all the evolutions in the graph. It builds the following databases: _mu_evolutions, _evolutions_from_mu, _evolutions_to_mu.
Assumes that all inner loops have been processed. Reads/writes from/to _mu_step.
Topsort the nodes.
Find root nodes.
print_evolutions(_mu_evolutions, "MU", cerr); Chew them up.
... Check whether 'to' is reachable from 'from'
... Unreachable.
... MU Node. ... Set evolutions from mu.
... Set mu evolutions.
... INPUT node.
... Set INPUT-to-MU evolutions.
... Manual reset for loop index. ... This is needed because our logic would otherwise detect a zero-length ... pass between 'ind' and 'ind' and overwrite the real step.
Now build _evolutions_to_mu.
... Check whether 'to' is reachable from 'from'
cerr<<"\nACYCLIC evs for loop "<<loop_name(_loop); print_evolutions(_evolutions_from_mu, "MU", cerr); print_evolutions(_mu_evolutions, "MU", cerr); print_evolutions(_input2mu_evolutions, "INPUT2MU", cerr); print_input_values(_input_values, "INPUT", cerr);
Definition at line 1426 of file EvolutionGraph.cc.
References _bellman_ford(), _topsort(), evolution(), Statement::index(), INFINITY_OP, mu(), Graph< Symbol *, Evolution< Expression > >::nodes(), Expression::op(), Expression::sign(), Statement::step(), and Expression::symbol().
Referenced by _build().

void EvolutionGraph::_compute_cyclic_evolutions ( EvolutionMap & evs,

map< const Symbol *, Evolution< Expression > > & ivs

) [protected]

Aggregates the effect of evolutions across all iterations.
Consider the following: We have a MU that may have an incoming value, and may also be reached by another loop-invariant definition from within the loop body through the loop-back arc (BACK, MU). Let us denote by IMU the incoming value for the MU node and by INPUT the other input value.
Consider the following events: 1. There is a path from MU to BACK. (T/F) 2. The loop has at least 1 iteration. (T/F) 3. IMU is defined. (T/F) 4. There is a path from INPUT to BACK (T/F)
Here is a table describing the cyclic evolutions: ???F: MU = IMU + IC *muev T?TT: MU = INPUT + i2mu + (IC-1)*muev MU = IMU + IC *muev T?FT: MU = INPUT + i2mu + (IC-1)*muev FT?T: MU = INPUT + i2mu FFTT: MU = INPUT + i2mu MU = IMU FFFT: MU = INPUT + i2mu
if (_cyclic_evs_computed) { return; } _cyclic_evs_computed=true;
Check preconditions.
Forall MU symbols.
... Check for loop index.
... Check whether the loop has premature exits.
... Iteration space limit.
... Premature exit value.
... Check whether this is a parasite.
... Check whether this MU was marked as not computable.
cerr<<"\nAt pgm "<<_pgm->routine_name_ref(); cerr<<"\nAt loop "<<loop_name(_loop); cerr<<"\n\tFor MU symbol "<<node_name(mu)<<" : "; cerr<<"\n\tInput symbol "<<node_name(sym);
print_evolutions(_input2mu_evolutions, "I2MUs", cerr);
if (input.min_difference()==0){ p_abort("ERROR"); }
cerr<<"\nAt loop "<<loop_name(_loop); cerr<<"\n\tFor MU symbol "<<node_name(mu)<<" : "; if (there_is_a_path_from_mu_to_back) cerr<<"T"; else cerr<<"F"; if (the_loop_has_at_least_1_iteration) cerr<<"T"; else cerr<<"F"; if (imu_is_defined) cerr<<"T"; else cerr<<"F"; if (there_is_a_path_from_input_to_back) cerr<<"T"; else cerr<<"F";
... Let's roll. ... ???F
... ??FF
... T??T
... T?TT
... T?FT
cerr<<"\n\t1 ev = "<<ev; cerr<<"\n\t ic = "<<*ic;
... silvius: there are problems multiplying Inf with possibly negative ... numbers.
cerr<<"\n\t2 ev = "<<ev;
cerr<<"\n\t3 ev = "<<ev;
cerr<<"\nev = "<<ev; cerr<<"\ninput = "<<input;
cerr<<"\n1. setting "<<ev;
... FT?T
... Since the loop has an iteration and there is no way to get the BACK ... value from IMU (no path from MU to BACK), the only value possible ... is the INPUT one.
cerr<<"\n2. setting "<<input;
... FFTT
cerr<<"\n3. setting "<<input;
... FFFT
cerr<<"\n4. setting "<<input;
For the parasites.
... silvius: for now, do it for parasites only if the SCC that contains ... the parasite MU contains only 0-evolutions and has a single entry ... which is a MU itself.
cerr<<"\nFound host_mu: "<<host_mu->name_ref();
cerr<<"\n5. setting "<<ivs[host_mu];
... Copy evolution from host MU.
cerr<<"\nCould not find host_mu for parasite_mu "<<mu->name_ref();
cerr<<"\nCYCLIC evs for loop "<<loop_name(_loop); print_evolutions(evs, "MU", cerr); print_input_values(ivs, "CYCLIC", cerr);
Definition at line 1588 of file EvolutionGraph.cc.
References _verify_preconditions(), Expression::clone(), constant(), Type::data_type(), evolution(), get_imu(), has_known_iteration_space(), ID_OP, Statement::index(), infinity(), INFINITY_OP, INTEGER_TYPE, Symbol::is_scalar(), iteration_count(), last_value(), loop_name(), Evolution< Value >::max_difference(), Evolution< Value >::min_difference(), mu(), mul(), node_name(), Graph< Symbol *, Evolution< Expression > >::nodes(), Expression::op(), POS_EXPR, RangeComparator::signz(), simplify(), sub(), Expression::symbol(), and Symbol::type().
Referenced by _add_evolutions().

Expression * EvolutionGraph::_local_range ( const Symbol & sym ) [protected]

Compute the range of a variable within myself.
There are three ways to compute the value: 1. input + input_2_value 2. mu_input + mu_acyclic*(ic-1) + mu_2_value 3. input + input2mu + mu_acyclic*(ic-2) + mu_2_value
If this VEG corresponds to a whole routine, just case 1 is considered.

Warning:
Only works if given symbol is a node in this evolution graph.

cerr<<"\n\nEnter local_range in loop "<<loop_name(_loop) <<", for symbol "<<sym.name_ref(); For now, only do it if &sym is a node in *this.
... silvius: check for negative step!
Find total values in first class. First check whether it is an input itself.
... Return now, all other reaching values will be overwritten.
cerr<<"\n\tearly return."; print_input_values(_input_values, "INPUT", cerr);
... Find total values in second and third class.
cerr<<"\n\tparasite.";
cerr<<"\n\t mu = "<<mu->name_ref();
... Second class.
... silvius: check for negative step!
... There is a cycle from mu to itself.
cerr<<"\n\t2. ev = "<<ev;
cerr<<"\n\t3. ev = "<<ev;
... Third class. ... This only makes sense if there are inputs reaching mu.
... There is a cycle from mu to itself.
cerr<<"\n\t4. ev = "<<ev;
cerr<<"\n\t5. ev = "<<ev;
cerr<<"\n\t6. ev = "<<ev;
cerr<<"\n\t7. ev = OMEGA";
Definition at line 2172 of file EvolutionGraph.cc.
References Expression::clone(), constant(), Graph< Symbol *, Evolution< Expression > >::contains(), evolution(), get_imu(), Statement::index(), infinity(), Statement::init(), iteration_count(), Statement::limit(), Evolution< Value >::max_difference(), merge_unite(), Evolution< Value >::min_difference(), mu(), RangeExpr::RangeExpr(), simplify(), sub(), and Expression::symbol().
Referenced by _add_approximations(), and _eliminate_vars().

Expression * EvolutionGraph::_eliminate_vars ( Expression * expr,

set< Symbol * > & syms

) [protected]

Compute the range of an expression.

Warning:
All symbols referenced by the given expression must be defined in _loop.
We will take ownership over expr.

Eliminate all symbols defined here.
cerr<<"\n\t\tSetting local range for "<<(*sit)->name_ref() <<" to "<<*lr;
... Optimization. Try to detect (-Inf:+Inf) early.
Definition at line 2346 of file EvolutionGraph.cc.
References _local_range(), RangeComparator::eliminate_vars(), INFINITY_OP, RefSet< T >::ins(), RangeExpr::lb(), Expression::op(), RANGE_OP, RangeAccessor::set_range(), Expression::sign(), and RangeExpr::ub().
Referenced by _global_range(), and _global_range_per_iteration().

Expression * EvolutionGraph::_global_range_per_iteration ( Expression * expr,

DoStmt * domain

)

Compute the range of an expression at the given level, but for just one iteration.
If the given domain is 0, the range across the whole program unit is returned.
cerr<<"\n\n\nEntering EvolutionGraph::_global_range " <<"\n\texpr = "<<*expr <<"\n\tdomain = "<<loop_name(domain);
Iterate until we have no symbols defined in a loop within domain.
... No variables in expr.
... current <= ci
cerr<<"\n\tin loop "<<loop_name(ci); cerr<<"\n\tEG::rs: "<<syms;
... This test is a valid termination condition because we are going outer.
cerr<<"\n\tbefore elimination in loop "<<loop_name(ci)<<": "<<*expr;
cerr<<"\n\t result = "<<*expr;
if (expr){ cerr<<"\n\tfrom EvolutionGraph::_global_range: "<<*expr; }
silvius: optimization
... Does have an input value.
if (expr){ cerr<<"\n\tfrom EvolutionGraph::_global_range: "<<*expr; }
Definition at line 2494 of file EvolutionGraph.cc.
References _eliminate_vars(), _filter_arrays(), _get_eg(), Graph< Symbol *, Evolution< Expression > >::contains(), Iterator< T >::current(), def_loop(), RefList< T >::entries(), ID_OP, inner(), RangeExpr::RangeExpr(), referred_symbols(), Expression::symbol(), and Iterator< T >::valid().
Referenced by _find_scalar_sources().

Expression * EvolutionGraph::_global_range ( Expression * expr )

Compute the range of an expression at the outermost level where at least one symbol within it is defined.
Find the outermost loop.
... No variables.
Definition at line 2680 of file EvolutionGraph.cc.
References Iterator< T >::current(), def_loop(), outer(), referred_symbols(), and Iterator< T >::valid().
Referenced by eg_compare(), and eg_range().

Expression * EvolutionGraph::_global_range ( Expression * expr,

DoStmt * domain

)

Compute the range of an expression at the given level.
If the given domain is 0, the range across the whole program unit is returned.
if (domain){ if (domain->outer_ref()){ cerr<<"\n\n\nEntering EvolutionGraph::_global_range " <<"\n\texpr = "<<*expr <<"\n\tdomain = "<<loop_name(domain); } }
cerr<<"\nAfter _filter_arrays : "<<*expr; cerr<<"\nDomain = "<<loop_name(domain);
Iterate until we have no symbols defined in a loop within domain.
... No variables in expr.
... current <= ci
cerr<<"\n\tin loop "<<loop_name(ci); cerr<<"\n\tEG::rs: "<<syms;
... This test is a valid termination condition because we are going outer.
cerr<<"\n\tbefore elimination in loop "<<loop_name(ci)<<": "<<*expr;
cerr<<"\n\t result = "<<*expr;
if (expr){ cerr<<"\n\tfrom EvolutionGraph::_global_range: "<<*expr; }
silvius: optimization
... Does have an input value.
We are at the outermost level within domain.
if (expr){ if (domain){ if (domain->outer_ref()){ cerr<<"\n\tfrom EvolutionGraph::_global_range: "<<*expr; } } }
Definition at line 2573 of file EvolutionGraph.cc.
References _eliminate_vars(), _filter_arrays(), _get_eg(), Graph< Symbol *, Evolution< Expression > >::contains(), Iterator< T >::current(), def_loop(), RefList< T >::entries(), ID_OP, inner(), RangeExpr::RangeExpr(), referred_symbols(), Expression::symbol(), and Iterator< T >::valid().

Expression * EvolutionGraph::range_from_input ( Symbol & s )

Compute the range of the given expression if it can be inferred from input values only. If so, do not express the input values using RangeDictionary. Otherwise, return 0.
Quick check. If there are any MU nodes reaching this symbol, return 0.
... Symbol not in this VEG.
... Made it to the input.
... Got to a MU, get out.
... Go on.
... Pick up a parent.
Merge results.
Definition at line 3628 of file EvolutionGraph.cc.
References Expression::clone(), Graph< Symbol *, Evolution< Expression > >::contains(), evolution(), Graph< Symbol *, Evolution< Expression > >::get_reversed_edges(), Graph< Symbol *, Evolution< Expression > >::index(), Evolution< Value >::max_difference(), merge_unite(), Evolution< Value >::min_difference(), Graph< Symbol *, Evolution< Expression > >::nodes(), and RangeExpr::RangeExpr().
Referenced by eg_range(), and eg_range_from_input().

void EvolutionGraph::print_graph ( const char * filename )

Prints the graph to a DOT (GraphViz) file.
... Node info. ... Is it an INPUT node?
... Is it a MU node?
... Or is it a BACK node?
Edges.
... Look for back edges.
Definition at line 1942 of file EvolutionGraph.cc.
References Graph< Symbol *, Evolution< Expression > >::get_edges(), Graph< Symbol *, Evolution< Expression > >::index(), node_name(), and Graph< Symbol *, Evolution< Expression > >::nodes().
Referenced by _build(), and _p_abort().

Expression * EvolutionGraph::min_distance ( const Symbol & left,

const Symbol & right

)

Returns the minimum distance between two elements in left and right across two successive iterations of '_loop'.
Conservative result: constant(0). Aborts if _loop==0. A distance of Infinity means the symbols are not connected.
Definition at line 2805 of file EvolutionGraph.cc.
References _cleanup_map(), _evolutions_from_input, _evolutions_from_mu, _evolutions_to_mu, _get_eg(), add(), Expression::clone(), comma(), constant(), def_loop(), Symtab::find_ref(), infinity(), INFINITY_OP, intrinsic_call(), loop(), mu(), Expression::op(), outer(), Statement::outer_ref(), p_greater_than(), p_less_than(), simplify(), and ProgramUnit::symtab().
Referenced by eg_distance(), and increasing().

bool EvolutionGraph::increasing ( const Symbol & value )

Returns true if the given variables takes constantly increasing values within the given loop. If the value is not defined within the loop, it returns true.

Warning:
A return value of false does not imply anything.

Definition at line 2710 of file EvolutionGraph.cc.
References min_distance().

EvolutionGraph::SequenceType EvolutionGraph::sequence_type ( const Symbol & value )

Returns sequence type for the given symbol.
We look at: value_2_mu + mu_2_value > 0 Also, we make sure that there are no input values.
Let us bring the problem into our own domain.
... Let us get its range for the outermost domain within this loop.
... Defined within outer loop, it is invariant here.
... silvius: for now, return ST_UNKNOWN at this point.
If it gets here, 'node' was defined at this level. Make sure there are no reaching input values.
Find value_2_mu and mu_2_value.
For now, do it only if they have exactly one fromMU and exactly one toMU, and it is the same.
Let us compute the aggregated evolution from 'node' to itself.
Let us see where this evolution goes.
Just could not figure it out.
Definition at line 2724 of file EvolutionGraph.cc.
References constant(), Graph< Symbol *, Evolution< Expression > >::contains(), def_loop(), inner(), List< T >::ins_last(), loop(), Evolution< Value >::max_difference(), Evolution< Value >::min_difference(), mu(), p_greater_equal(), p_greater_than(), p_less_equal(), p_less_than(), ST_DECREASING, ST_INCREASING, ST_NONDECREASING, ST_NONINCREASING, and ST_UNKNOWN.
Referenced by eg_nondecreasing().

void EvolutionGraph::enhance ( map< Symbol *, Symbol * > & imposed_edges )

Conditional pruning.

Definition at line 3600 of file EvolutionGraph.cc.

void EvolutionGraph::undo_enhancement ( )

Restore after conditional pruning.

Definition at line 3604 of file EvolutionGraph.cc.

void EvolutionGraph::trace_from_input ( Symbol * node,

pair< RangeExpr *, bool > & range,

list< Symbol * > & trace

)

Find all possible traces from input values to given node so that the input value + evolutions on the road are within the given range.
cerr<<"\n\n\tEnter trace_from_input ("; _print_range(node->name_ref(), range); cerr<<") in loop "<<loop_name(_loop); print_evolutions(_evolutions_from_input, "from input", cerr);
cerr<<"\n\t\t\tLooking at input: "<<isym->name_ref() <<" with total range "<<ev;
cerr<<"\nsolution count: "<<solutions.size();
... Could not find any trace for sure.
cerr<<"\n\t"<<(*solutions.begin())->name_ref();
... Find all edges on all the paths from 'solutions' to 'node' then ... go backwards until the first fork. ... silvius: will take a shortcut. This hopes that all the edges are 0 ... (but is conservative as it may only report more paths).
cerr<<"\n\t\tNow at current "<<current->name_ref();
... Pick up a parent.
cerr<<"\n\t\t\tcand= "<<cand->name_ref();
cerr<<"\n\t\t\t\ticand = "<<icand->name_ref();
... Check whether any of its reaching ivs is in 'solutions'
cerr<<"\n\t\t\t\thas reaching input with valid path.";
... It is on the path to an ivs.
... Dichotomy.
... Found a predecessor towards the ivs.
cerr<<"\n\t\t\t\tadd to trace: "<<pred->name_ref();
... Nowhere to go.
Definition at line 3367 of file EvolutionGraph.cc.
References _incompatible_ranges(), _range(), evolution(), Graph< Symbol *, Evolution< Expression > >::get_reversed_edges(), Graph< Symbol *, Evolution< Expression > >::index(), and Graph< Symbol *, Evolution< Expression > >::nodes().
Referenced by backtrack(), and eg_trace_from_input().

void EvolutionGraph::traces_from_mu ( Symbol * node,

pair< RangeExpr *, bool > & range,

map< Symbol *, list< list< Symbol * > > > & trace

)

Find traces from all MUs to given node within given range.
... Initialize the traces.
... For all old partial traces.
cerr<<"\n\tPartial trace: "; print_trace(*llit);
... BINGO, got a valid trace.
cerr<<"\n\t\tCOMPLETE.";
... No path to any MU. Discard partial trace, leads nowhere.
cerr<<"\n\t\tNo path to any MU. Discard.";
cerr<<"\n\t\tNo path to current MU. Discard.";
... No path to current MU. Discard partial trace.
... Cannot extend trace, it cannot be within the given range.
cerr<<"\n\t\ttotal = "<<total; cerr<<"\n\t\tgiven = "<<given; cerr<<"\n\t\tOutside given range. Discard.";
... Pick up a predecessor.
cerr<<"\n\t\t\tExtend trace to "<<cand->name_ref();
... Make up new trace by cloning the old one.
... Extend new trace.
... Add new trace to candidates.
Definition at line 3004 of file EvolutionGraph.cc.
References constant(), disjoint(), evolution(), Graph< Symbol *, Evolution< Expression > >::get_reversed_edges(), Graph< Symbol *, Evolution< Expression > >::index(), mu(), and Graph< Symbol *, Evolution< Expression > >::nodes().
Referenced by backtrack(), and eg_get_ev_summary().

void EvolutionGraph::perfect_trace_from_mu ( Symbol * node,

pair< RangeExpr *, bool > & range,

list< Symbol * > & trace

)

Finds a perfect backwards trace (a trace that must repeat in each iteration) given the range for a BACK node.
cerr<<"\nEnter perfect_trace_from_mu : "<<node->name_ref(); First, let us find whether there is a unique MU node that can reach 'node' such that the range of 'node' through that MU is within 'range'.
silvius: for now, only do it if it is reachable by exactly one MU.
... Unknown definition. No INPUT, no IMU, something is wrong.
For now, only do it if this MU is reachable by itself, and not by any other MU.
For now, the only thing we do is check the given range (less the mu input) against the extremes of the possible range. For instance, if the possible range for an iteration (muev) is [0:1], the iteration count is 10, and the given range is [0:0], then the range for each iteration is actually [0:0], so only paths made entirely of 0-edges are possible.
cerr<<"\nallev = "<<allev <<", r1 = "<<r1;
cerr<<"\n\tr = "<<r;
... Got it.
cerr<<"\n\tr = "<<r;
... Got it.
Definition at line 3158 of file EvolutionGraph.cc.
References add(), constant(), evolution(), get_imu(), infinity(), Relation::is_equal(), iteration_count(), List< T >::last_ref(), Evolution< Value >::max_difference(), Evolution< Value >::min_difference(), mu(), ProgramUnit::range_dict_guarded(), simplify(), ProgramUnit::stmts(), and sub().
Referenced by backtrack(), and perfect_trace_from_mu().

void EvolutionGraph::perfect_trace_from_mu ( Symbol * mu,

Symbol * node,

const Expression & given_length,

list< Symbol * > & trace

)

Composes a perfect backwards trace.
cerr<<"\nnode = "<<node->name_ref(); cerr<<"\nmu = "<<mu->name_ref();
cerr<<"\ncand = "<<cand->name_ref();
... No MU evs for this node.
... No path from 'mu'.
... Cannot go on edges with nontrivial range.
cerr<<"\ntotal = "<<total; cerr<<"\ngiven = "<<given_length;
... Let us see whether 'total' may contain 'given_length'
... Ambiguous.
p_abort("Ambiguous trace from MU.");
Definition at line 3094 of file EvolutionGraph.cc.
References Expression::clone(), Graph< Symbol *, Evolution< Expression > >::get_reversed_edges(), Graph< Symbol *, Evolution< Expression > >::index(), Evolution< Value >::max_difference(), Evolution< Value >::min_difference(), mu(), Graph< Symbol *, Evolution< Expression > >::nodes(), p_less_than(), perfect_trace_from_mu(), quick_pgm_entry(), ProgramUnit::range_dict_guarded(), range_stmt(), simplify(), and sub().

void EvolutionGraph::_possible_ranges ( const Symbol & sym,

list< pair< list< Symbol * >, RangeExpr * > > & result

)

Finds all the ways to compute the value of the given 'sym'. Returns the list of pairs(path, result). 'path' may be an INPUT symbol, a MU symbol, or a sequence INPUT, MU1, MU2, ...
If this VEG corresponds to a whole routine, just case 1 is considered.

Warning:
Only works if given symbol is a node in this evolution graph.

Only do it if &sym is a node in *this.
... silvius: check for negative step!
Find total values in first class. First check whether it is an input itself.
... Find total values in second and third class.
... Second class.
... silvius: check for negative step!
... There is a cycle from mu to itself.
... Third class. ... This only makes sense if there are inputs reaching mu.
... There is a cycle from mu to itself.
Definition at line 2022 of file EvolutionGraph.cc.
References _range(), Expression::clone(), constant(), Graph< Symbol *, Evolution< Expression > >::contains(), evolution(), get_imu(), Statement::index(), Statement::init(), iteration_count(), Statement::limit(), mu(), RangeExpr::RangeExpr(), simplify(), sub(), and Expression::symbol().
Referenced by backtrack().

void EvolutionGraph::backtrack ( Symbol * node,

pair< RangeExpr *, bool > & range,

list< Symbol * > & trace

)

Finds all possible back traces.
The final value of 'node' must stay within 'range'. Stop at the first ambiguity. Stop at this loop level (either MU or INPUT site). Skip called subprograms and inner loops.
First, let us find all the possible values for the given node, together with their sources (INPUT and MU).
... E.g. INPUT1, MU1, MU2, ..., MUn, [node]
cerr<<"\n\n\nSOURCES for "<<node->name_ref()<<" in "<< loop_name(_loop)<<": ";
cerr<<"\n\t";
cerr<<"\t:\t"<<*(*it).second;
cerr<<"\n\t\tINCOMPATIBLE";
cerr<<"\n\t\tCOMPATIBLE";
silvius: for now, do nothing if the loop contains both MU and INPUT sources for the given node.
cerr<<"\nBoth from_mu && from_input.";
... Trace from MU. ... First look for perfect traces.
... Now look for other traces.
... Traces from more than one MU.
cerr<<"\nTraces from more than one MU.";
... Multiple paths from this MU.
cerr<<"\nMultiple paths from this MU.";
... Trace from INPUT.
Definition at line 3289 of file EvolutionGraph.cc.
References _incompatible_ranges(), _possible_ranges(), perfect_trace_from_mu(), trace_from_input(), and traces_from_mu().
Referenced by eg_backtrack().

void EvolutionGraph::get_trace_details ( list< Symbol * > & trace,

Evolution< Expression > & ev,

Expression *& length,

List< Expression > & preds

)

Given a trace, it returns the aggregated evolution across it as a range, the accurate length of the trace as an expression, and the predicates collected at GAMMA sites.
The trace is assumed in reversed order.
Definition at line 3447 of file EvolutionGraph.cc.
References add(), Expression::arg_list(), ASSIGNMENT_STMT, Expression::clone(), constant(), evolution(), DefLocMap::find_ref(), GAMMA_OP, Expression::gate(), Graph< Symbol *, Evolution< Expression > >::get_reversed_edge(), ProgramUnit::gsa_deflocs_guarded(), List< T >::ins_last(), Evolution< Value >::max_difference(), Evolution< Value >::min_difference(), not(), Expression::op(), Expression::parameters_guarded(), Statement::rhs(), simplify(), Statement::stmt_class(), DefLoc::stmt_guarded(), DefLoc::stmt_valid(), sub(), and symbol().
Referenced by eg_get_ev_summary().

void EvolutionGraph::export_evolutions ( Symbol * node,

map< const Symbol *, Evolution< Expression > > & muevs,

list< pair< const Symbol *, Evolution< Expression > > > & ievs

)

Export evolution knowledge for a node.
MU evs.
INPUT evs.
Definition at line 3688 of file EvolutionGraph.cc.
References Graph< Symbol *, Evolution< Expression > >::contains().
Referenced by program_wide_range().

bool EvolutionGraph::find_unique_mu ( Symbol * node,

Symbol *& mu,

Symbol *& back

)

Return the reaching MU and BACK for this intermediate symbol and return TRUE if they are unique. Also, only return TRUE if MU cannot be reached from any other MU. Also, only return TRUE if MU cannot be reached from any input.
Find the unique reaching MU.
... Reaching MUs.
... GOOD.
cerr<<"\nRET 1";
... Cannot be reached by any MU
cerr<<"\nRET 2";
Make sure that MU can be reached by itself, but no other MUs.
... GOOD.
... MU can be reached by another MU.
cerr<<"\nRET 3";
cerr<<"\nRET 4";
... MU cannot be reached by any other MU.
cerr<<"\nRET 5";
Make sure that MU cannot be reached by any INPUT.
... BINGO.
... MU can be reached by an INPUT.
cerr<<"\nRET 6";
Definition at line 3544 of file EvolutionGraph.cc.
References mu().
Referenced by eg_get_ev_summary().

Expression * EvolutionGraph::substitute ( Symbol * given )

Performs forward substitution on demand.
x -> y, ev=[1,1] ==> y = x+1
Warning:
Returns 0 if no proper substitution can be found (rather than returning id(*given) as would seem fit).

Definition at line 3509 of file EvolutionGraph.cc.
References add(), Expression::clone(), Graph< Symbol *, Evolution< Expression > >::contains(), Graph< Symbol *, Evolution< Expression > >::get_reversed_edges(), id(), Graph< Symbol *, Evolution< Expression > >::index(), Evolution< Value >::max_difference(), Evolution< Value >::min_difference(), Graph< Symbol *, Evolution< Expression > >::nodes(), and simplify().
Referenced by eg_forward_substitute().

Member Data Documentation

bool EvolutionGraph::_acyclic_evs_computed [protected]

Definition at line 239 of file EvolutionGraph.h.
Referenced by EvolutionGraph().

bool EvolutionGraph::_cyclic_evs_computed [protected]

Definition at line 245 of file EvolutionGraph.h.
Referenced by EvolutionGraph().

stack<map<const Symbol*, const Symbol*> > EvolutionGraph::_newly_imposed_edges [protected]

Definition at line 259 of file EvolutionGraph.h.

The documentation for this class was generated from the following files:

Fri Mar 25 23:07:19 2005

EvolutionGraph Class Reference

Public Types

Public Member Functions