[PPL-devel] [GIT] ppl/ppl(master): Added draft implementation for wrap_assign() for the grid domain.
Patricia Hill
p.m.hill at leeds.ac.uk
Thu May 7 18:58:24 CEST 2009
Module: ppl/ppl
Branch: master
Commit: ddecda47e763c5759190b167be835c9b77c82b49
URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=ddecda47e763c5759190b167be835c9b77c82b49
Author: Patricia Hill <p.m.hill at leeds.ac.uk>
Date: Thu May 7 17:55:07 2009 +0100
Added draft implementation for wrap_assign() for the grid domain.
---
src/Grid.defs.hh | 47 ++++++++++++++++
src/Grid_public.cc | 81 ++++++++++++++++++++++++++++
tests/Grid/Makefile.am | 5 ++-
tests/Grid/wrap1.cc | 137 ++++++++++++++++++++++++++++++++++++++++++++++++
4 files changed, 269 insertions(+), 1 deletions(-)
diff --git a/src/Grid.defs.hh b/src/Grid.defs.hh
index 0d3745f..1045bfa 100644
--- a/src/Grid.defs.hh
+++ b/src/Grid.defs.hh
@@ -1478,6 +1478,53 @@ public:
*/
void time_elapse_assign(const Grid& y);
+ /*! \brief
+ \ref Wrapping_Operator "Wraps" the specified dimensions of the
+ vector space.
+
+ \param vars
+ The set of Variable objects corresponding to the space dimensions
+ to be wrapped.
+
+ \param w
+ The width of the bounded integer type corresponding to
+ all the dimensions to be wrapped.
+
+ \param s
+ The signedness of the bounded integer type corresponding to
+ all the dimensions to be wrapped.
+
+ \param o
+ The overflow behavior of the bounded integer type corresponding to
+ all the dimensions to be wrapped.
+
+ \param pcs
+ Possibly null pointer to a constraint system.
+ This argument is for compatibility with wrap_assign()
+ for the other domains and is ignored.
+
+ \param complexity_threshold
+ A precision parameter of the \ref Wrapping_Operator "wrapping operator".
+ This argument is for compatibility with wrap_assign()
+ for the other domains and is ignored.
+
+ \param wrap_individually
+ <CODE>true</CODE> if the dimensions should be wrapped individually.
+ As wrapping dimensions collectively does not improve the precision,
+ this argument is ignored.
+
+ \exception std::invalid_argument
+ Thrown if \p *this is dimension-incompatible with one of the
+ Variable objects contained in \p vars or with <CODE>*pcs</CODE>.
+ */
+ void wrap_assign(const Variables_Set& vars,
+ Bounded_Integer_Type_Width w,
+ Bounded_Integer_Type_Signedness s,
+ Bounded_Integer_Type_Overflow o,
+ const Constraint_System* pcs = 0,
+ unsigned complexity_threshold = 16,
+ bool wrap_individually = true);
+
//! Assigns to \p *this its topological closure.
void topological_closure_assign();
diff --git a/src/Grid_public.cc b/src/Grid_public.cc
index cfc3d31..1f2cda5 100644
--- a/src/Grid_public.cc
+++ b/src/Grid_public.cc
@@ -2639,6 +2639,87 @@ PPL::Grid::external_memory_in_bytes() const {
+ gen_sys.external_memory_in_bytes();
}
+void
+PPL::Grid::wrap_assign(const Variables_Set& vars,
+ Bounded_Integer_Type_Width w,
+ Bounded_Integer_Type_Signedness s,
+ Bounded_Integer_Type_Overflow o,
+ const Constraint_System*,
+ unsigned,
+ bool) {
+
+ // If overflow is impossible do nothing.
+ if (o == OVERFLOW_IMPOSSIBLE)
+ // FIXME: CHECKME: If the grid frequency for x in vars is more than half
+ // the wrap frequency, then x can only take a unique (ie constant) value.
+ return;
+
+ // Wrapping no variable is a no-op.
+ if (vars.empty())
+ return;
+
+ const dimension_type space_dim = space_dimension();
+ // Dimension-compatibility check of `vars'.
+ if (space_dim < vars.space_dimension()) {
+ std::ostringstream s;
+ s << "PPL::Grid::wrap_assign(vars, ...):" << std::endl
+ << "this->space_dimension() == " << space_dim
+ << ", required space dimension == " << vars.space_dimension() << ".";
+ throw std::invalid_argument(s.str());
+ }
+
+ // Wrapping an empty polyhedron is a no-op.
+ if (marked_empty())
+ return;
+ if (!generators_are_up_to_date() && !update_generators())
+ // Updating found `this' empty.
+ return;
+
+ // Generators are up-to-date.
+ const Grid gr = *this;
+
+ // If overflow is undefined, then all we know is that the variable
+ // will be integral.
+ if (o == OVERFLOW_UNDEFINED) {
+ for (Variables_Set::const_iterator i = vars.begin(),
+ vars_end = vars.end(); i != vars.end(); ++i) {
+
+ const Variable x = Variable(*i);
+
+ // If x is a constant, do nothing.
+ if (!gr.bounds(x, "wrap_assign(...)")) {
+ if (gr.constrains(x))
+ // We know that x is not a constant,
+ // so x may wrap to any integral value.
+ add_grid_generator(parameter(x));
+ }
+ }
+ return;
+ }
+
+ // Overflow wraps.
+ assert(o == OVERFLOW_WRAPS);
+ // Set the wrap frequency for variables of width `w' and signedness `s'.
+ PPL_DIRTY_TEMP_COEFFICIENT(wrap_frequency);
+ if (s == UNSIGNED)
+ mul_2exp_assign(wrap_frequency, Coefficient_one(), w);
+ else {
+ assert(s == SIGNED_2_COMPLEMENT);
+ mul_2exp_assign(wrap_frequency, Coefficient_one(), w-1);
+ }
+
+ for (Variables_Set::const_iterator i = vars.begin(),
+ vars_end = vars.end(); i != vars.end(); ++i) {
+ const Variable x = Variable(*i);
+ // If x is a constant, do nothing.
+ if (!gr.bounds(x, "wrap_assign(...)")) {
+ if (gr.constrains(x))
+ // We know that x is not a constant, so x may wrap.
+ add_grid_generator(parameter(wrap_frequency * x));
+ }
+ }
+}
+
/*! \relates Parma_Polyhedra_Library::Grid */
std::ostream&
PPL::IO_Operators::operator<<(std::ostream& s, const Grid& gr) {
diff --git a/tests/Grid/Makefile.am b/tests/Grid/Makefile.am
index 2291f76..7189082 100644
--- a/tests/Grid/Makefile.am
+++ b/tests/Grid/Makefile.am
@@ -117,7 +117,8 @@ topclosed1 \
topclosure1 \
unconstrain1 \
upperbound1 upperbound2 \
-widening1 widening2 widening3\
+widening1 widening2 widening3 \
+wrap1 \
writecongruencesystem
XFAIL_TESTS =
@@ -280,6 +281,8 @@ widening3_SOURCES = widening3.cc
writecongruencesystem_SOURCES = writecongruencesystem.cc
+wrap1_SOURCES = wrap1.cc
+
check_PROGRAMS = $(TESTS)
MOSTLYCLEANFILES = \
diff --git a/tests/Grid/wrap1.cc b/tests/Grid/wrap1.cc
new file mode 100644
index 0000000..1a810dc
--- /dev/null
+++ b/tests/Grid/wrap1.cc
@@ -0,0 +1,137 @@
+/* Test Grid::wrap_assign().
+ Copyright (C) 2001-2009 Roberto Bagnara <bagnara at cs.unipr.it>
+
+This file is part of the Parma Polyhedra Library (PPL).
+
+The PPL is free software; you can redistribute it and/or modify it
+under the terms of the GNU General Public License as published by the
+Free Software Foundation; either version 3 of the License, or (at your
+option) any later version.
+
+The PPL is distributed in the hope that it will be useful, but WITHOUT
+ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with this program; if not, write to the Free Software Foundation,
+Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02111-1307, USA.
+
+For the most up-to-date information see the Parma Polyhedra Library
+site: http://www.cs.unipr.it/ppl/ . */
+
+#include "ppl_test.hh"
+
+namespace {
+
+bool
+test01() {
+ Variable x(0);
+ Variable y(1);
+ Grid gr(2);
+ gr.add_congruence((x + 24 %= 8*y) / 2);
+ gr.add_congruence((y %= 1) / 3);
+
+ print_congruences(gr, "*** gr ***");
+
+ Variables_Set vars(x, y);
+
+ gr.wrap_assign(vars, BITS_8, UNSIGNED, OVERFLOW_WRAPS);
+
+ Grid known_result(2);
+ known_result.add_congruence((x + 24 %= 8*y) / 2);
+ known_result.add_congruence((y %= 0) / 1);
+
+ bool ok = (gr == known_result);
+
+ print_congruences(gr, "*** gr.wrap_assign(...) ***");
+
+ return ok;
+}
+
+bool
+test02() {
+ Variable x(0);
+ Variable y(1);
+ Variable z(2);
+
+ Grid gr(3);
+ gr.add_congruence(x + 24 %= 8*y);
+ gr.add_congruence((y %= 1) / 2);
+
+ print_congruences(gr, "*** gr ***");
+
+ Variables_Set vars(x, y);
+
+ gr.wrap_assign(vars, BITS_8, UNSIGNED, OVERFLOW_UNDEFINED);
+
+ Grid known_result(3);
+ known_result.add_congruence(x %= 0);
+ known_result.add_congruence(y %= 0);
+
+ bool ok = (gr == known_result);
+
+ print_congruences(gr, "*** gr.wrap_assign(...) ***");
+
+ return ok;
+}
+
+bool
+test03() {
+ Variable x(0);
+ Variable y(1);
+ Grid gr(2);
+ gr.add_congruence((x + 24 %= 8*y) / 255);
+ gr.add_congruence(x %= 0);
+
+ print_congruences(gr, "*** gr ***");
+
+ Variables_Set vars(x, y);
+
+ gr.wrap_assign(vars, BITS_8, UNSIGNED, OVERFLOW_IMPOSSIBLE);
+
+ Grid known_result(2);
+ known_result.add_congruence(x %= 0);
+ known_result.add_congruence((x + 24 %= 8*y) / 255);
+
+ bool ok = (gr == known_result);
+
+ print_congruences(gr, "*** gr.wrap_assign(...) ***");
+
+ return ok;
+}
+
+bool
+test04() {
+ Variable x(0);
+ Variable y(1);
+ Variable z(2);
+ Variable w(3);
+
+ Grid gr(4);
+ gr.add_congruence((x %= 255) / 0);
+
+ print_congruences(gr, "*** gr ***");
+
+ Variables_Set vars(x, w);
+
+ gr.wrap_assign(vars, BITS_8, UNSIGNED, OVERFLOW_WRAPS);
+
+ Grid known_result(4);
+ known_result.add_congruence((x %= 255) / 0);
+
+ bool ok = (gr == known_result);
+
+ print_congruences(gr, "*** gr.wrap_assign(...) ***");
+
+ return ok;
+}
+
+} // namespace
+
+BEGIN_MAIN
+ DO_TEST(test01);
+ DO_TEST(test02);
+ DO_TEST(test03);
+ DO_TEST(test04);
+END_MAIN
More information about the PPL-devel
mailing list