convex_hull.c File Reference

#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"
#include "transformer.h"

Include dependency graph for convex_hull.c:

Go to the source code of this file.

Functions
static transformer	transformer_convex_hulls (transformer t1, transformer t2, Psysteme(*method)(Psysteme, Psysteme))
	temporarily, for ifdebug More...
transformer	transformer_convex_hull (transformer t1, transformer t2)
	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 More...

Function Documentation

transformer_convex_hull()

transformer transformer_convex_hull	(	transformer	t1,
		transformer	t2
	)

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

convex_hull.c

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);

Parameters

t1	1
t2	2

Definition at line 216 of file convex_hull.c.

{
  /* 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);
}

References cute_convex_union(), transformer_convex_hulls(), and transformer_normalize().

Referenced by add_module_call_site_precondition(), any_assign_to_transformer(), any_basic_update_to_transformer(), any_conditional_to_transformer(), any_loop_to_k_transformer(), any_loop_to_postcondition(), any_transformer_to_k_closure(), any_update_to_transformer(), complete_loop_transformer(), complete_loop_transformer_list(), condition_to_transformer(), conditional_to_transformer(), dag_or_cycle_to_flow_sensitive_postconditions_or_transformers(), dag_to_flow_sensitive_preconditions(), generic_transformer_list_to_transformer(), generic_unary_operation_to_transformer(), get_control_precondition(), lhs_expression_to_transformer(), loop_body_transformer_add_entry_and_iteration_information(), loop_to_postcondition(), loop_to_total_precondition(), main(), new_array_elements_backward_substitution_in_transformer(), new_array_elements_forward_substitution_in_transformer(), old_complete_whileloop_transformer(), points_to_unary_operation_to_transformer(), process_call_for_summary_precondition(), process_ready_node(), repeatloop_to_postcondition(), repeatloop_to_transformer(), statement_to_transformer(), statement_to_transformer_list(), struct_reference_assignment_or_equality_to_transformer(), test_to_postcondition(), test_to_total_precondition(), test_to_transformer(), transformer_add_anded_conditions_updown(), transformer_add_any_relation_information(), transformer_add_integer_relation_information(), transformer_add_ored_conditions_updown(), transformer_halbwachs_fix_point(), transformer_list_closure_to_precondition_depth_two(), transformer_list_closure_to_precondition_max_depth(), unstructured_to_flow_insensitive_transformer(), update_summary_precondition(), update_temporary_precondition(), and whileloop_to_postcondition().

Here is the call graph for this function:

Here is the caller graph for this function:

transformer_convex_hulls()

static transformer transformer_convex_hulls ( transformer  t1, transformer  t2, Psysteme(*)(Psysteme, Psysteme)  method  )

static

temporarily, for ifdebug

This function used to have side effects on arguments t1 and t2

If one of the transformers is empty, you do not want to union the arguments

Pbase b_min;

Could be used if useless dimensions are not detected at lower level(s)

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?.

add implicit constraints for bool variables

add implicit constraints for bool variables

update bases using their "union"; convex hull has to be computed relatively to ONE space

b is duplicated because it may be later freed by (*method)() FI->CA: To be changed when (*method)() is cleaned up

please, no sharing between Psysteme's

meet operation (with no side-effect on arguments r1 and r2)

There is no way to distinguish between SC_RN and SC_EMPY since both are defined as NULL

FI: this could be eliminated if SC_EMPTY was really usable; 27/5/93

and replaced by a SC_UNDEFINED_P() and pips_error()

To eliminate the arguments in case r is really empty

Definition at line 56 of file convex_hull.c.

{
  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;
}

References arguments_union(), b1, b2, Ssysteme::base, base_contains_variable_p(), base_dimension, base_dup(), BASE_NULLE, base_rm, base_union(), basic_logical_p, contrainte_make(), dump_transformer, empty_transformer(), ENTITY, entity_is_argument_p(), entity_to_new_value(), entity_to_old_value(), entity_type, eq, FOREACH, ifdebug, pips_debug, predicate_system, sc_dup(), sc_empty(), sc_empty_p(), sc_equation_add(), sc_inequality_add(), sc_rm(), sc_to_minimal_basis(), TCST, transformer_arguments, transformer_dup(), transformer_empty_p(), transformer_identity(), transformer_relation, transformer_undefined, type_variable, VALUE_MONE, VALUE_ONE, variable_basic, vect_add_elem(), vect_chg_coeff(), and vect_new().

Referenced by transformer_convex_hull().

Here is the call graph for this function:

Here is the caller graph for this function: