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

Author: Patricia Hill p.m.hill@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@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