bound_generation.c File Reference

#include <stdio.h>
#include "linear.h"
#include "genC.h"
#include "misc.h"
#include "ri.h"
#include "ri-util.h"

Include dependency graph for bound_generation.c:

Go to the source code of this file.

Functions
int	bound_generation_compare_vector_component (Pvecteur *pv1, Pvecteur *pv2)
	Generation of bound expressions from constraint systems of the Linear library. More...
void	make_bound_expression (Variable index, Pbase base, Psysteme sc, expression *lower, expression *upper)
	void make_bound_expression(variable index, Pbase base, Psysteme sc, expression *lower, expression *upper) More...

Function Documentation

bound_generation_compare_vector_component()

int bound_generation_compare_vector_component	(	Pvecteur *	pv1,
		Pvecteur *	pv2
	)

Generation of bound expressions from constraint systems of the Linear library.

bound_generation.c

Used for sorting each constraint and in between constraints, hopefully

Parameters

pv1	v1
pv2	v2

Definition at line 40 of file bound_generation.c.

{
  entity e1 = (entity) vecteur_var(*pv1);
  entity e2 = (entity) vecteur_var(*pv2);
  // FI: is "less" a well-chosen name?
  // int less = strcmp(entity_local_name(e1), entity_local_name(e2));
  int less;
 
  if(e1==NULL) {
    if(e2==NULL)
      less = 0;
    else
      less = -1;
  }
  else if(e2==NULL)
    less = 1;
  else
    less = strcmp(entity_user_name(e1), entity_user_name(e2));
 
#if 0
  if(less==0) {
    Value v1 = vecteur_val(*pv1);
    Value v2 = vecteur_val(*pv2);
    if(value_gt(v1,v2))
      less = 1;
    else if(value_lt(v1,v2))
      less = -1;
    else
      /* To satisfy a later assert not so well designed */
      less = pv1<pv2? 1 : -1;
  }
#endif
 
  return less;
}

References entity_user_name(), value_gt, value_lt, vecteur_val, and vecteur_var.

Referenced by make_bound_expression().

Here is the call graph for this function:

Here is the caller graph for this function:

make_bound_expression()

void make_bound_expression	(	Variable	index,
		Pbase	base,
		Psysteme	sc,
		expression *	lower,
		expression *	upper
	)

void make_bound_expression(variable index, Pbase base, Psysteme sc, expression *lower, expression *upper)

build the expressions "lower" and "upper" for the lower and upper bounds of variable "index". Variable "index" must appear in "base" and have lower and upper bounds in "sc"

Beware of degenerated cases where constraints are reduced to equations because the upper and lower bounds are identical.

The constraints are sorted according to the lexicographic order using bound_generation_compare_vector_component().

see also constraints_to_loop_bound (in conversion system_to_code.c)

compute the rank d of the index in the basis

The constraints should be lexicographically sorted to avoid secondary variations in linear

search constraints referencing "index" among inequalities and create the list of expressions for lower and upper bounds

found

ifdebug(7) {

fprintf(stderr, "\n expression after :");

print_expression(ex);

}

add the expression to the list of lower bounds or to the list of upper bounds

search equation constraints referencing "index" and create the list of expressions for lower and upper bounds. We may have to generate useless loops with only one iteration.

found

ifdebug(7) {

fprintf(stderr, "\n expression after :");

print_expression(ex);

}

add the expression to the list of lower bounds and to the list of upper bounds

Reverse the expression order

build expressions for the lower and upper bounds

To avoid clash with Fortran intrinsics

pips_min and pips_max are supposed to be part of PIPS run-time. They are varargs and their first argument is the count of arguments

and memory leak... (cons lost)

idem...

print_expression(*lower);

print_expression(*upper);

Parameters

index	ndex
base	ase
sc	c
lower	ower
upper	pper

Definition at line 91 of file bound_generation.c.

{
    Pcontrainte pc;
    cons *ll = NIL;
    cons *lu = NIL;
 
    expression ex;
    entity min, max;
 
    int i;
    int rank_index ;
 
    /* compute the rank d of the index in the basis */
    rank_index =
      base_find_variable_rank(base, index,
                              (get_variable_name_t) entity_name_or_TCST);
 
    pips_debug(7, "index :%s\n", entity_name_or_TCST(index));
    pips_debug(8, "rank_index = %d\n", rank_index);
 
    /* The constraints should be lexicographically sorted to avoid
       secondary variations in linear */
    // contrainte_vect_sort(ll, bound_generation_compare_vector_component);
    ifdebug(7) {
      fprintf(stderr, "Constraints before sorting:\n");
      sc_dump(sc);
    }
    sc_lexicographic_sort(sc, bound_generation_compare_vector_component);
    ifdebug(7) {
      fprintf(stderr, "Constraints after sorting:\n");
      sc_dump(sc);
    }
 
    /* search constraints referencing "index" among inequalities and
      create the list of expressions for lower and upper bounds */
    for (pc=sc->inegalites; pc!=NULL; pc=pc->succ) {
        i = level_contrainte(pc, base);
        pips_debug(8,"level: %d\n",i);
        if (ABS(i)==rank_index){        /* found */
            ifdebug(7) {
                (void) fprintf(stderr, "\n constraint before :");
                contrainte_fprint(stderr, pc, true,
                                  (get_variable_name_t) entity_name_or_TCST);
            }
            ex = make_constraint_expression(pc->vecteur, (Variable) index);
            // FI: to avoid cycles betwen librairies ri-util and prettyprint
            /* ifdebug(7) { */
            /*  fprintf(stderr, "\n expression after :"); */
            /*  print_expression(ex); */
            /* } */
            /* add the expression to the list of  lower bounds
               or to the list of upper bounds*/
            if (i>0)
                lu = CONS(EXPRESSION, ex, lu);
            else
                ll = CONS(EXPRESSION, ex, ll);
        }
    }
 
    /* search equation constraints referencing "index" and create the
      list of expressions for lower and upper bounds. We may have to
      generate useless loops with only one iteration. */
    for (pc=sc->egalites; pc!=NULL; pc=pc->succ) {
        i = level_contrainte(pc, base);
        pips_debug(8,"level: %d\n",i);
        if (ABS(i)==rank_index){        /* found */
            ifdebug(7) {
                (void) fprintf(stderr, "\n constraint before :");
                contrainte_fprint(stderr, pc, true,
                                  (get_variable_name_t) entity_name_or_TCST);
            }
            if(i>0) {
              Pvecteur mv = vect_copy(pc->vecteur);
              mv = vect_multiply(mv, VALUE_MONE);
              ex = make_constraint_expression(mv, (Variable) index);
              vect_rm(mv);
            }
            else
              ex = make_constraint_expression(pc->vecteur, (Variable) index);
            // FI: to avoid cycles betwen librairies ri-util and prettyprint
            /* ifdebug(7) { */
            /*  fprintf(stderr, "\n expression after :"); */
            /*  print_expression(ex); */
            /* } */
 
            /* add the expression to the list of  lower bounds
               and to the list of upper bounds*/
            lu = CONS(EXPRESSION, ex, lu);
            ll = CONS(EXPRESSION, ex, ll);
        }
    }
 
    /* Reverse the expression order */
    ll = gen_nreverse(ll);
    lu = gen_nreverse(lu);
 
    /* build expressions for the lower and upper bounds */
    if(false && c_language_module_p(get_current_module_entity())) {
      /* To avoid clash with Fortran intrinsics */
      /* pips_min and pips_max are supposed to be part of PIPS
         run-time. They are varargs and their first argument is the
         count of arguments */
      min = entity_intrinsic(PIPS_C_MIN_OPERATOR_NAME);
      max = entity_intrinsic(PIPS_C_MAX_OPERATOR_NAME);
    }
    else { // Fortran case
      min = entity_intrinsic(MIN_OPERATOR_NAME);
      max = entity_intrinsic(MAX_OPERATOR_NAME);
    }
 
    pips_assert("entities for min and max are found",
                min != entity_undefined && max != entity_undefined);
 
    if (gen_length(ll) > 1) {
      if(false && c_language_module_p(get_current_module_entity())) {
        int c = gen_length(ll);
        expression ce = int_to_expression(c);
        ll = CONS(EXPRESSION, ce, ll);
      }
      *lower = make_expression(make_syntax(is_syntax_call,
                                           make_call(max,ll)),
                               normalized_undefined);
    }
    else {
        *lower = EXPRESSION(CAR(ll)); /* and memory leak... (cons lost) */
        gen_free_list(ll);
    }
 
    if (gen_length(lu) > 1 ) {
      if(false && c_language_module_p(get_current_module_entity())) {
        int c = gen_length(lu);
        expression ce = int_to_expression(c);
        lu = CONS(EXPRESSION, ce, lu);
      }
        *upper = make_expression(make_syntax(is_syntax_call,
                                             make_call(min,lu)),
                                 normalized_undefined );
    }
    else {
        *upper = EXPRESSION(CAR(lu)); /* idem... */
        gen_free_list(lu);
    }
 
    ifdebug(7) {
        pips_debug(9, "returning: \n");
        // FI: to avoid cycles betwen librairies ri-util and prettyprint
        /* print_expression(*lower); */
        /* print_expression(*upper); */
    }
}

References ABS, base, base_find_variable_rank(), bound_generation_compare_vector_component(), c_language_module_p(), CAR, CONS, contrainte_fprint(), Ssysteme::egalites, entity_intrinsic(), entity_name_or_TCST(), entity_undefined, EXPRESSION, fprintf(), gen_free_list(), gen_length(), gen_nreverse(), get_current_module_entity(), ifdebug, Ssysteme::inegalites, int_to_expression(), is_syntax_call, level_contrainte(), make_call(), make_constraint_expression(), make_expression(), make_syntax(), max, MAX_OPERATOR_NAME, min, MIN_OPERATOR_NAME, NIL, normalized_undefined, pips_assert, PIPS_C_MAX_OPERATOR_NAME, PIPS_C_MIN_OPERATOR_NAME, pips_debug, sc_dump(), sc_lexicographic_sort(), Scontrainte::succ, VALUE_MONE, vect_copy(), vect_multiply(), vect_rm(), and Scontrainte::vecteur.

Referenced by code_generation(), hyperplane(), make_scanning_over_one_tile(), make_scanning_over_tiles(), parallel_tiling(), tiling_transformation(), and unimodular().

Here is the call graph for this function:

Here is the caller graph for this function: