[PPL-devel] [GIT] ppl/ppl(pip): Add new friend function add_mul_assign() for Linear_Expression.

[Enea Zaffanella]

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

Author: Enea Zaffanella <zaffanella at cs.unipr.it>
Date:   Fri Feb  5 15:59:56 2010 +0100

Add new friend function add_mul_assign() for Linear_Expression.
Used new function to optimize a couple of computations in PIP_Tree.cc.

---

 src/Linear_Expression.cc      |   19 ++++++++++++++++++
 src/Linear_Expression.defs.hh |   10 +++++++++
 src/PIP_Tree.cc               |   42 ++++++++++++++++++++++++++--------------
 3 files changed, 56 insertions(+), 15 deletions(-)

diff --git a/src/Linear_Expression.cc b/src/Linear_Expression.cc
index 4ffc709..f7d50a3 100644
--- a/src/Linear_Expression.cc
+++ b/src/Linear_Expression.cc
@@ -354,6 +354,25 @@ PPL::operator*=(Linear_Expression& e, Coefficient_traits::const_reference n) {
   return e;
 }
 
+/*! \relates Parma_Polyhedra_Library::Linear_Expression */
+PPL::Linear_Expression&
+PPL::add_mul_assign(Linear_Expression& e,
+                    Coefficient_traits::const_reference n,
+                    const Variable v) {
+  const dimension_type v_space_dim = v.space_dimension();
+  if (v_space_dim > Linear_Expression::max_space_dimension())
+    throw std::length_error("Linear_Expression& "
+                            "PPL::add_mul_assign(e, n, v):\n"
+			    "v exceeds the maximum allowed space dimension.");
+  const dimension_type e_size = e.size();
+  if (e_size <= v_space_dim) {
+    Linear_Expression new_e(e, v_space_dim+1);
+    e.swap(new_e);
+  }
+  e[v_space_dim] += n;
+  return e;
+}
+
 bool
 PPL::Linear_Expression::OK() const {
   return Linear_Row::OK();
diff --git a/src/Linear_Expression.defs.hh b/src/Linear_Expression.defs.hh
index 2367c94..b4ce1e0 100644
--- a/src/Linear_Expression.defs.hh
+++ b/src/Linear_Expression.defs.hh
@@ -166,6 +166,12 @@ operator-=(Linear_Expression& e, Coefficient_traits::const_reference n);
 Linear_Expression&
 operator*=(Linear_Expression& e, Coefficient_traits::const_reference n);
 
+//! Returns the linear expression \p e + \p n * \p v and assigns it to \p e.
+/*! \relates Linear_Expression */
+Linear_Expression&
+add_mul_assign(Linear_Expression& e,
+               Coefficient_traits::const_reference n, Variable v);
+
 namespace IO_Operators {
 
 //! Output operator.
@@ -451,6 +457,10 @@ private:
   friend Linear_Expression&
   operator*=(Linear_Expression& e, Coefficient_traits::const_reference n);
 
+  friend Linear_Expression&
+  add_mul_assign(Linear_Expression& e,
+                 Coefficient_traits::const_reference n, Variable v);
+
   friend std::ostream&
   Parma_Polyhedra_Library::IO_Operators
   ::operator<<(std::ostream& s, const Linear_Expression& e);
diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc
index c007c25..cb62db1 100644
--- a/src/PIP_Tree.cc
+++ b/src/PIP_Tree.cc
@@ -518,15 +518,21 @@ PIP_Tree_Node::OK() const {
 void
 PIP_Tree_Node
 ::add_constraint(const Row& row, const Variables_Set& parameters) {
-  const Variables_Set::const_iterator p_begin = parameters.begin();
-  const Variables_Set::const_iterator p_end = parameters.end();
-  PPL_ASSERT(static_cast<dimension_type>(std::distance(p_begin, p_end)) + 1
-             == row.size());
-  // FIXME: optimize the computation of expr.
+  const dimension_type num_params = parameters.size();
+  PPL_ASSERT(num_params + 1 == row.size());
+
+  // Compute the expression for the parameter constraint.
   Linear_Expression expr = Linear_Expression(row[0]);
-  dimension_type j = 1;
-  for (Variables_Set::const_iterator pj = p_begin; pj != p_end; ++pj, ++j)
-    expr += row[j] * Variable(*pj);
+  // NOTE: iterating downward on parameters to avoid reallocations.
+  Variables_Set::const_reverse_iterator p_j = parameters.rbegin();
+  // NOTE: index j spans [1..num_params] downwards.
+  for (dimension_type j = num_params; j > 0; --j) {
+    add_mul_assign(expr, row[j], Variable(*p_j));
+    // Move to previous parameter.
+    ++p_j;
+  }
+
+  // Add the parameter constraint.
   constraints_.insert(expr >= 0);
 }
 
@@ -1723,8 +1729,6 @@ PIP_Solution_Node::solve(const PIP_Problem& problem,
       }
 
       // Compute columns t[*][j] :
-      // t[i][j] -= t[i][pj] * t_pivot[j] / s_pivot_pj;
-      // ENEA: FIXME: according to code below, this comment should read:
       // t[i][j] -= s[i][pj] * t_pivot[j] / s_pivot_pj;
       for (dimension_type j = num_params; j-- > 0; ) {
         const Coefficient& t_pivot_j = t_pivot[j];
@@ -2094,6 +2098,7 @@ PIP_Solution_Node::generate_cut(const dimension_type index,
   const Coefficient& den = tableau.get_denominator();
 
   PPL_DIRTY_TEMP_COEFFICIENT(mod);
+  PPL_DIRTY_TEMP_COEFFICIENT(coeff);
 
 #ifdef NOISY_PIP
   std::cout << "Row " << index << " contains non-integer coefficients. "
@@ -2125,15 +2130,22 @@ PIP_Solution_Node::generate_cut(const dimension_type index,
     mod_assign(mod, row_t[0], den);
     Linear_Expression expr;
     if (mod != 0) {
+      // Optimizing computation: expr += (den - mod);
       expr += den;
       expr -= mod;
     }
-    Variables_Set::const_iterator p = parameters.begin();
-    for (dimension_type j = 1; j < num_params; ++j, ++p) {
+    // NOTE: iterating downwards on parameters to avoid reallocations.
+    Variables_Set::const_reverse_iterator p_j = parameters.rbegin();
+    // NOTE: index j spans [1..num_params-1] downwards.
+    for (dimension_type j = num_params; j-- > 1; ) {
       mod_assign(mod, row_t[j], den);
-      // FIXME: find a way to optimize the following.
-      if (mod != 0)
-        expr += (den - mod) * Variable(*p);
+      if (mod != 0) {
+        // Optimizing computation: expr += (den - mod) * Variable(*p_j);
+        coeff = den - mod;
+        add_mul_assign(expr, coeff, Variable(*p_j));
+      }
+      // Mode to previous parameter.
+      ++p_j;
     }
     // Generate new artificial parameter.
     Artificial_Parameter ap(expr, den);