convex_hull.c

Go to the documentation of this file.

/*
 
  $Id: convex_hull.c 23065 2016-03-02 09:05:50Z coelho $
 
  Copyright 1989-2016 MINES ParisTech
 
  This file is part of PIPS.
 
  PIPS 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
  any later version.
 
  PIPS 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 PIPS.  If not, see <http://www.gnu.org/licenses/>.
 
*/
#ifdef HAVE_CONFIG_H
    #include "pips_config.h"
#endif
 /*
  * transformer package - convex hull computation
  *
  * Francois Irigoin, 21 April 1990
  */
 
#include <stdio.h>
 
#include "genC.h"
#include "linear.h"
 
#include "ri.h"
#include "ri-util.h"
 
#include "misc.h"
 
#include "boolean.h"
#include "vecteur.h"
#include "contrainte.h"
#include "sc.h"
#include "ray_dte.h"
#include "sommet.h"
#include "sg.h"
#include "polyedre.h"
 
/* temporarily, for ifdebug */
#include "transformer.h"
 
/* This function used to have side effects on arguments t1 and t2 */
static transformer transformer_convex_hulls
(transformer t1, transformer t2, Psysteme (*method)(Psysteme, Psysteme))
{
  transformer t = transformer_undefined;
 
 
  pips_debug(6,"begin\n");
  ifdebug(6) {
    pips_debug(6, "convex hull t1 (%p):\n", t1);
    dump_transformer(t1) ;
  }
  ifdebug(6) {
    pips_debug(6, "convex hull t2 (%p):\n", t2);
    dump_transformer(t2) ;
  }
 
  /* If one of the transformers is empty, you do not want to union
   * the arguments
   */
  if(transformer_empty_p(t1)) {
    t = transformer_dup(t2);
  }
  else if(transformer_empty_p(t2)) {
    t = transformer_dup(t1);
  }
  else {
    Psysteme r1 = sc_dup((Psysteme) predicate_system(transformer_relation(t1)));
    Psysteme r2 = sc_dup((Psysteme) predicate_system(transformer_relation(t2)));
    Psysteme r;
    Pbase b1;
    Pbase b2;
    Pbase b1_min = sc_to_minimal_basis(r1);
    Pbase b2_min = sc_to_minimal_basis(r2);
    Pbase b;
    /* Pbase b_min; */ /* Could be used if useless dimensions are not
       detected at lower level(s) */
    int eq_count1 = 0;
    int eq_count2 = 0;
    int ineq_count1 = 0;
    int ineq_count2 = 0;
 
    t = transformer_identity();
    transformer_arguments(t) = 
      arguments_union(transformer_arguments(t1),
                      transformer_arguments(t2));
 
    /* add implicit equality constraints in r1 and r2 */
    /* These equalities should only be added if the variable explicitly
       appears in at least one constraint in the other constraint
       system. Mathematical proof?. */
    FOREACH(ENTITY, a,  transformer_arguments(t1)) {
      if(!entity_is_argument_p(a, transformer_arguments(t2))) {
        entity a_new = entity_to_new_value(a);
        if(base_contains_variable_p(b1_min, (Variable) a_new)) {
          entity a_old = entity_to_old_value(a);
          Pvecteur eq = vect_new((Variable) a_new, -1);
          vect_chg_coeff(&eq, (Variable) a_old, 1);
          r2 = sc_equation_add(r2, contrainte_make(eq));
          eq_count2++;
          if(basic_logical_p(variable_basic(type_variable(entity_type(a))))) {
            /* add implicit constraints for bool variables */
            Pvecteur ineq1 = vect_new((Variable) a_new, VALUE_ONE);
            Pvecteur ineq2 = vect_new((Variable) a_new, VALUE_MONE);
 
            vect_add_elem(&ineq1, TCST, VALUE_MONE);
            r2 = sc_inequality_add(r2, contrainte_make(ineq1));
            r2 = sc_inequality_add(r2, contrainte_make(ineq2));
            ineq_count2++;
          }
        }
      }
    }
    base_rm(b1_min);
    FOREACH(ENTITY, a, transformer_arguments(t2)) {
      if(!entity_is_argument_p(a, transformer_arguments(t1))) {
        entity a_new = entity_to_new_value(a);
        if(base_contains_variable_p(b2_min, (Variable) a_new)) {
          entity a_old = entity_to_old_value(a);
          Pvecteur eq = vect_new((Variable) a_new, -1);
          vect_chg_coeff(&eq, (Variable) a_old, 1);
          r1 = sc_equation_add(r1, contrainte_make(eq));
          eq_count1++;
          if(basic_logical_p(variable_basic(type_variable(entity_type(a))))) {
            /* add implicit constraints for bool variables */
            Pvecteur ineq1 = vect_new((Variable) a_new, VALUE_ONE);
            Pvecteur ineq2 = vect_new((Variable) a_new, VALUE_MONE);
 
            vect_add_elem(&ineq1, TCST, VALUE_MONE);
            r1 = sc_inequality_add(r1, contrainte_make(ineq1));
            r1 = sc_inequality_add(r1, contrainte_make(ineq2));
            ineq_count1++;
          }
        }
      }
    }
    base_rm(b2_min);
 
    pips_debug(6,"Number of equations added to t1: %d, to t2: %d\n"
               "Number of inequalities added to t1: %d, to t2: %d\n", 
               eq_count1, eq_count2, ineq_count1, ineq_count2);
 
    /* update bases using their "union"; convex hull has to be computed 
       relatively to ONE space */
    b1 = r1->base;
    b2 = r2->base;
    b = base_union(b1, b2);
    base_rm(b1);
    base_rm(b2);
    /* b is duplicated because it may be later freed by (*method)()
     * FI->CA: To be changed when (*method)() is cleaned up
     */
    sc_base(r1) = base_dup(b);
    /* please, no sharing between Psysteme's */
    sc_base(r2) = base_dup(b);
    sc_dimension(r1) = base_dimension(b);
    sc_dimension(r2) = sc_dimension(r1);
 
    /* meet operation (with no side-effect on arguments r1 and r2) */
    r = (* method)(r1, r2);
 
    /* There is no way to distinguish between SC_RN and SC_EMPY since
       both are defined as NULL */
    if(SC_EMPTY_P(r)) {
      /* FI: this could be eliminated if SC_EMPTY was really usable; 27/5/93 */
      /* and replaced by a SC_UNDEFINED_P() and pips_error() */
      r = sc_empty(BASE_NULLE);
    }
    else {
      base_rm(b);
      b = BASE_NULLE;
    }
 
    sc_rm(r1);
    sc_rm(r2);
 
    if(sc_empty_p(r)) {
      /* To eliminate the arguments in case r is really empty */
      t = empty_transformer(t);
    }
    else
      predicate_system(transformer_relation(t)) = r;
 
  }
 
  ifdebug(6) {
    pips_debug(6, "convex hull, t (%p):\n", t);
    dump_transformer(t) ;
  }
 
  pips_debug(6, "end\n");
 
  return t;
}
 
/* transformer transformer_convex_hull(t1, t2): compute convex hull for t1
 * and t2; t1 and t2 are slightly modified to give them the same basis; else
 * convex hull means nothing; some of the work is duplicated in sc_enveloppe;
 * however their "relation" fields are preserved; the whole thing is pretty
 * badly designed; shame on Francois! FI, 24 August 1990
 */
transformer transformer_convex_hull(transformer t1, transformer t2)
{
  /* return transformer_convex_hulls(t1, t2, sc_enveloppe);  */
  /* return transformer_convex_hulls(t1, t2, sc_enveloppe_chernikova); */
  /* return transformer_convex_hulls(t1, t2, sc_common_projection_convex_hull);
   */
/*   t1 = transformer_normalize(t1, 4); */
/*   t2 = transformer_normalize(t2, 4); */
  t1 = transformer_normalize(t1, 2);
  t2 = transformer_normalize(t2, 2);
  return transformer_convex_hulls(t1, t2, cute_convex_union);
}
 
/* I removed this because I do not want to port the polyedre library
 * to use "Value". If you want this function, do the port! FC 07/96
 */
/*
transformer transformer_fast_convex_hull(t1, t2)
transformer t1;
transformer t2;
{
    return transformer_convex_hulls(t1, t2, sc_fast_convex_hull);
}
*/
 
/*
transformer transformer_chernikova_convex_hull(t1, t2)
transformer t1;
transformer t2;
{
    return transformer_convex_hulls(t1, t2, sc_enveloppe_chernikova);
}
*/