Module: ppl/ppl Branch: master Commit: 236efc9ce1d06358f0d0313abd2661423ff9249e URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=236efc9ce1d06...

Author: Patricia Hill p.m.hill@leeds.ac.uk Date: Tue May 12 08:37:29 2009 +0100

Several improvements for the wrap_assign() operator for grids.

---

doc/definitions.dox | 63 ++++++++++++++++++++++++-------------------------- src/Grid_public.cc | 13 +++++----- 2 files changed, 36 insertions(+), 40 deletions(-)

diff --git a/doc/definitions.dox b/doc/definitions.dox index a1cc335..e3148c0 100644 --- a/doc/definitions.dox +++ b/doc/definitions.dox @@ -2313,46 +2313,43 @@ A grid \f$\cL\f$ <EM>subsumes</EM> a (polyhedron) ray or line \f$g\f$ if adding the corresponding grid line to any grid generator system representing \f$\cL\f$ does not change \f$\cL\f$.

-\subsection Wrapping_Operator Wrapping Operator +\subsection Grid_Wrapping_Operator Wrapping Operator

The operator <CODE>wrap_assign</CODE> provided by the library, allows -for the wrapping of a subset of the set of space dimensions so to fit +for the wrapping of a subset of the set of space dimensions so as to fit the given bounded integer type and have the specified overflow behavior.

Suppose \f$\cL \in \Gset_n\f$ is a grid and \f$J\f$ a subset of the set of space dimensions \f${0, \ldots, n-1}\f$. Suppose also that the width of the bounded integer type is \f$w\f$ so that -the range of values can be \f$0 - 2^w-1\f$ if the type is unsigned -and \f$-2^{w-1} - 2^{w-1} - 1\f$ otherwise. -Consider a space dimension \f$j \in J\f$. - -If the value in \f$\cL\f$ for the dimension \f$j\f$ is bounded and -hence a constant, no wrapping can take place; in this case the -grid is unchanged. - -Otherwise the value for the dimension \f$j\f$ will be unbounded and -the result of the operation will depend on which of -three possible overflow behaviors has been specified. - -- Overflow impossible: in this case, it is known that no wrapping can - occur; if the grid has exactly one possible value for the given - bounded integer type, then the dimension \f$j\f$ is set equal to - that value, otherwise, the grid is unchanged. - -- Overflow undefined: in this case, the wrapped value can be any - integer within the range of the bounded integer type, so that the - parameter \f$(0, \ldots, 0, v_j, 0, \dots, 0)\f$, where - \f$v_j = 1\f$ is added to the generator system. - -- Overflow wraps: in this case, the \f$j\f$ dimension can be wrapped to - a value modulo \f$2^w\f$, so that the parameter - \f$(0, \ldots, 0, v_j, 0, \dots, 0)\f$, where \f$v_j = 2^w\f$ - is added to the generator system. - -Note that the <CODE>wrap_assign</CODE> is intended for dimensions that -can take integral values; if this not the case for any of the -dimensions in \f$J\f$ for the grid \f$\cL\f$, the behavior is -undefined. +the range of values \f$R = {0, \ldots, 2^w-1}\f$ +if the type is unsigned +and \f$R = {-2^{w-1},\ldots, 0, \ldots, 2^{w-1} - 1}\f$ otherwise. +Consider a space dimension \f$j \in J\f$ and a variable \f$v_j\f$ +for dimension \f$j\f$. + +If the value in \f$\cL\f$ for the variable \f$v_j\f$ is +a constant in the range \f$R\f$, then it is unchanged. +Otherwise the result of the operation will depend on the +specified overflow behavior. + +- Overflow impossible. In this case, it is known that no wrapping can + occur. If the grid \f$\cL\f$ has no value for the variable \f$v_j\f$ in the + range \f$R\f$, then \f$\cL\f$ is set empty. If \f$v_j\f$ has exactly + one value \f$a \in R\f$ in \f$\cL\f$, then \f$v_j\f$ is set + equal to \f$a\f$. Otherwise, \f$\cL\f$ is unchanged. + +- Overflow undefined. In this case, for each value \f$a\f$ for + \f$v_j\f$ in the grid \f$\cL\f$, the wrapped value can be any value + \f$a + z \in R\f$ where \f$z \in \Zset\f$. + Therefore the parameter \f$(0, \ldots, 0, v_j, 0, \dots, 0)\f$, + where \f$v_j = 1\f$ is added to the generator system for \f$\cL\f$. + +- Overflow wraps. In this case, for each value \f$a\f$ for + \f$v_j\f$ in the grid \f$\cL\f$, the wrapped value can be any value + \f$a + z 2^{w-1} \in R\f$ where \f$z \in \Zset\f$. + Therefore the parameter \f$(0, \ldots, 0, v_j, 0, \dots, 0)\f$, + where \f$v_j = 2^{w-1}\f$ is added to the generator system for \f$\cL\f$.

\subsection Grid_Widening Widening Operators

diff --git a/src/Grid_public.cc b/src/Grid_public.cc index 1e181b2..8d54946 100644 --- a/src/Grid_public.cc +++ b/src/Grid_public.cc @@ -2745,21 +2745,20 @@ PPL::Grid::wrap_assign(const Variables_Set& vars, // `x' is not a constant in `gr'. if (gr.constrains(x)) // We know that `x' is not a constant, so `x' may wrap to any - // integral value. + // value `x + z' where z is an integer. add_grid_generator(parameter(x)); } else { - // `x' is a constant in `gr'. + // `x' is a constant `v' in `gr'. PPL_DIRTY_TEMP_COEFFICIENT(coeff_x); PPL_DIRTY_TEMP_COEFFICIENT(div_x); coeff_x = gen_sys[0].coefficient(x); div_x = gen_sys[0].divisor(); - // If the value of `x' is not within the range for the bounded - // integer type, then `x' can take any integral value; - // otherwise `x' is unchanged. + // If the value `v' for `x' is not within the range for the + // bounded integer type, then `x' may wrap to any value `v + z' + // where `z' is an integer; otherwise `x' is unchanged. if (coeff_x > max_value * div_x || coeff_x < min_value * div_x) { - unconstrain(x); - add_congruence(x %= 0); + add_grid_generator(parameter(x)); } } }