[PPL-devel] [GIT] ppl/ppl(master): Several improvements for the wrap_assign() operator for grids.

[Patricia Hill]

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

Author: Patricia Hill <p.m.hill at 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));
         }
       }
     }