December 2011 - PPL-devel - BUGSENG Mailman

[GIT] ppl/ppl(master): Style improvements for Grid::relation_with( const Congruence& cg) const.
by Enea Zaffanella 03 Dec '11

03 Dec '11

Module: ppl/ppl Branch: master Commit: b384ace64d3a140ad3f7af3022f7afcb596d68f0 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=b384ace64d3a… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Sat Dec 3 09:24:39 2011 +0100 Style improvements for Grid::relation_with(const Congruence& cg) const. No functionality change. --- src/Grid_public.cc | 95 +++++++++++++++++++++++++--------------------------- 1 files changed, 46 insertions(+), 49 deletions(-) diff --git a/src/Grid_public.cc b/src/Grid_public.cc index 85b3566..9b98765 100644 --- a/src/Grid_public.cc +++ b/src/Grid_public.cc @@ -396,87 +396,85 @@ PPL::Grid::relation_with(const Congruence& cg) const { PPL_DIRTY_TEMP_COEFFICIENT(point_sp); point_sp = 0; - const Coefficient& modulus = cg.modulus(); - PPL_DIRTY_TEMP_COEFFICIENT(div); - div = modulus; + div = cg.modulus(); PPL_DIRTY_TEMP_COEFFICIENT(sp); bool known_to_intersect = false; - for (Grid_Generator_System::const_iterator g = gen_sys.begin(), - gen_sys_end = gen_sys.end(); g != gen_sys_end; ++g) { - Scalar_Products::assign(sp, cg, *g); + for (Grid_Generator_System::const_iterator i = gen_sys.begin(), + i_end = gen_sys.end(); i != i_end; ++i) { + const Grid_Generator& g = *i; + Scalar_Products::assign(sp, cg, g); - switch (g->type()) { + switch (g.type()) { case Grid_Generator::POINT: if (cg.is_proper_congruence()) sp %= div; - if (sp == 0) + if (sp == 0) { // The point satisfies the congruence. if (point_sp == 0) // Any previous points satisfied the congruence. known_to_intersect = true; else return Poly_Con_Relation::strictly_intersects(); - else - if (point_sp == 0) { - if (known_to_intersect) - return Poly_Con_Relation::strictly_intersects(); - // Assign `sp' to `point_sp' as `sp' is the scalar product - // of cg and a point g and is non-zero. - point_sp = sp; - } - else { - // A previously considered point p failed to satisfy cg such that - // `point_sp' = `scalar_prod(p, cg)' - // so, if we consider the parameter g-p instead of g, we have - // scalar_prod(g-p, cg) = scalar_prod(g, cg) - scalar_prod(p, cg) - // = sp - point_sp - sp -= point_sp; - - if (sp != 0) { - // Find the GCD between sp and the previous GCD. - gcd_assign(div, div, sp); - if (point_sp % div == 0) - // There is a point in the grid satisfying cg. - return Poly_Con_Relation::strictly_intersects(); - } + } + else { + if (point_sp == 0) { + if (known_to_intersect) + return Poly_Con_Relation::strictly_intersects(); + // Assign `sp' to `point_sp' as `sp' is the scalar product + // of cg and a point g and is non-zero. + point_sp = sp; } + else { + // A previously considered point p failed to satisfy cg such that + // `point_sp' = `scalar_prod(p, cg)' + // so, if we consider the parameter g-p instead of g, we have + // scalar_prod(g-p, cg) = scalar_prod(g, cg) - scalar_prod(p, cg) + // = sp - point_sp + sp -= point_sp; + + if (sp != 0) { + // Find the GCD between sp and the previous GCD. + gcd_assign(div, div, sp); + if (point_sp % div == 0) + // There is a point in the grid satisfying cg. + return Poly_Con_Relation::strictly_intersects(); + } + } + } break; case Grid_Generator::PARAMETER: if (cg.is_proper_congruence()) - sp %= (div * g->divisor()); + sp %= (div * g.divisor()); if (sp == 0) // Parameter g satisfies the cg so the relation depends // entirely on the other generators. break; - if (known_to_intersect) - // At least one point satisfies cg. However, the sum of such - // a point and the parameter g fails to satisfy cg (due to g). - return Poly_Con_Relation::strictly_intersects(); - + // At least one point satisfies cg. However, the sum of such + // a point and the parameter g fails to satisfy cg (due to g). + return Poly_Con_Relation::strictly_intersects(); // Find the GCD between sp and the previous GCD. gcd_assign(div, div, sp); - if (point_sp != 0) - // At least one of any previously encountered points fails to - // satisfy cg. - if (point_sp % div == 0) - ////// if (point_sp == div) - // There is also a grid point that satisfies cg. - return Poly_Con_Relation::strictly_intersects(); - + if (point_sp != 0) { + // At least one of any previously encountered points fails to + // satisfy cg. + if (point_sp % div == 0) + // There is also a grid point that satisfies cg. + return Poly_Con_Relation::strictly_intersects(); + } break; case Grid_Generator::LINE: if (sp == 0) - // Line g satisfies the cg so the relation depends entirely on - // the other generators. - break; + // Line g satisfies the cg so the relation depends entirely on + // the other generators. + break; // Line g intersects the congruence. // @@ -490,7 +488,6 @@ PPL::Grid::relation_with(const Congruence& cg) const { // *this that does not satisfy `cg' and hence `p+g' is a point // in *this not in the grid defined by `cg'; therefore `*this' // strictly intersects the `cg' grid. - return Poly_Con_Relation::strictly_intersects(); } }

1 0

[GIT] ppl/ppl(master): Corrected errors in method Grid::relation_with( const Constraint&) const.
by Enea Zaffanella 03 Dec '11

03 Dec '11

Module: ppl/ppl Branch: master Commit: b67af6c1ba5a560e2ab48a37cccf8fc18782a257 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=b67af6c1ba5a… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Sat Dec 3 09:17:12 2011 +0100 Corrected errors in method Grid::relation_with(const Constraint&) const. The method was affected by two problems: 1) when working on a non-minimized grid generator system, the points after the first one were transformed into parameters that were not satisfying the Grid_Generator invariant (reported by Marco Poletti); 2) the method was providing an incorrect result when comparing a grid generator line/parameter with a (strict) inequality constraint, as happens for test20() in tests/Grid/relations3.cc. --- src/Grid_public.cc | 75 ++++++++++++++++++++++++++++++++-------------------- 1 files changed, 46 insertions(+), 29 deletions(-) diff --git a/src/Grid_public.cc b/src/Grid_public.cc index e05731c..85b3566 100644 --- a/src/Grid_public.cc +++ b/src/Grid_public.cc @@ -623,53 +623,70 @@ PPL::Grid::relation_with(const Constraint& c) const { bool point_is_included = false; bool point_saturates = false; - const Grid_Generator* first_point = NULL; - - for (Grid_Generator_System::const_iterator g = gen_sys.begin(), - gen_sys_end = gen_sys.end(); g != gen_sys_end; ++g) - switch (g->type()) { + const Grid_Generator* first_point = 0; + for (Grid_Generator_System::const_iterator i = gen_sys.begin(), + i_end = gen_sys.end(); i != i_end; ++i) { + const Grid_Generator& g = *i; + switch (g.type()) { case Grid_Generator::POINT: { - Grid_Generator& gen = const_cast<Grid_Generator&>(*g); - if (first_point == NULL) { - first_point = &gen; - const int sign = Scalar_Products::sign(c, gen); - Constraint::Type type = c.type(); - if ((type == Constraint::NONSTRICT_INEQUALITY && sign == 0)) { - point_saturates = true; - } + if (first_point == 0) { + first_point = &g; + const int sign = Scalar_Products::sign(c, g); + if (sign == 0) + point_saturates = !c.is_strict_inequality(); else if (sign > 0) - point_is_included = true; + point_is_included = !c.is_equality(); break; } - // Else convert g to a parameter, and continue into the - // parameter case. + // Not the first point: convert `g' to be a parameter ... + Grid_Generator& gen = const_cast<Grid_Generator&>(g); + const Grid_Generator& point = *first_point; + const Coefficient& p_div = g[0]; + if (p_div != Coefficient_one()) { + for (dimension_type j = gen.size() - 1; j-- > 1; ) + gen[j] *= p_div; + } + const Coefficient& g_div = gen[0]; + if (g_div == Coefficient_one()) { + for (dimension_type j = gen.size() - 1; j-- > 1; ) + gen[j] -= point[j]; + } + else { + for (dimension_type j = gen.size() - 1; j-- > 1; ) + sub_mul_assign(gen[j], g_div, point[j]); + } + gen[0] *= p_div; + gen.strong_normalize(); gen.set_is_parameter(); - const Grid_Generator& first = *first_point; - for (dimension_type i = gen.size() - 1; i-- > 0; ) - gen[i] -= first[i]; + PPL_ASSERT(gen.OK()); + // ... and fall through into the parameter case. } case Grid_Generator::PARAMETER: case Grid_Generator::LINE: - Grid_Generator& gen = const_cast<Grid_Generator&>(*g); - if (gen.is_line_or_parameter()) - for (dimension_type i = c.space_dimension(); i-- > 0; ) { - Variable v(i); - if (c.coefficient(v) != 0 && gen.coefficient(v) != 0) - return Poly_Con_Relation::strictly_intersects(); - } + { + const int sign = c.is_strict_inequality() + ? Scalar_Products::reduced_sign(c, g) + : Scalar_Products::sign(c, g); + if (sign != 0) + return Poly_Con_Relation::strictly_intersects(); + } break; - } + } // switch + } + // If this program point is reached, then all lines and parameters + // saturate the constraint. Hence, the result is determined by + // the previosly computed relation with the point. if (point_saturates) - // Any parameters and lines are also included. return Poly_Con_Relation::saturates() && Poly_Con_Relation::is_included(); + if (point_is_included) - // Any parameters and lines are also included. return Poly_Con_Relation::is_included(); + return Poly_Con_Relation::is_disjoint(); }

1 0

[GIT] ppl/ppl(master): Added new test showing an error in Grid:: relation_with(const Constraint&).
by Enea Zaffanella 03 Dec '11

03 Dec '11

Module: ppl/ppl Branch: master Commit: 856eabd63f477b4ada10bd2c75f58a3e594c355b URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=856eabd63f47… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Sat Dec 3 09:13:58 2011 +0100 Added new test showing an error in Grid::relation_with(const Constraint&). --- tests/Grid/relations3.cc | 24 ++++++++++++++++++++++++ 1 files changed, 24 insertions(+), 0 deletions(-) diff --git a/tests/Grid/relations3.cc b/tests/Grid/relations3.cc index 05e8e60..bd0bd11 100644 --- a/tests/Grid/relations3.cc +++ b/tests/Grid/relations3.cc @@ -438,6 +438,29 @@ test19() { return ok; } +// A variant of test06. +bool +test20() { + Variable A(0); + Variable B(1); + + Grid gr(2, EMPTY); + gr.add_grid_generator(grid_point()); + gr.add_grid_generator(grid_point(2*A + 5*B)); + // Force minimization. + (void) gr.minimized_grid_generators(); + print_generators(gr, "*** gr ***"); + + bool ok = (gr.relation_with(5*A - 2*B == 1) + == Poly_Con_Relation::is_disjoint() + && gr.relation_with(5*A - 2*B > 1) + == Poly_Con_Relation::is_disjoint() + && gr.relation_with(5*A - 2*B >= 1) + == Poly_Con_Relation::is_disjoint()); + + return ok; +} + } // namespace BEGIN_MAIN @@ -460,4 +483,5 @@ BEGIN_MAIN DO_TEST(test17); DO_TEST(test18); DO_TEST(test19); + DO_TEST(test20); END_MAIN

1 0