sc_unaires.c File Reference

#include <stdio.h>
#include <stdlib.h>
#include "linear_assert.h"
#include "boolean.h"
#include "arithmetique.h"
#include "vecteur.h"
#include "contrainte.h"
#include "sc.h"

Include dependency graph for sc_unaires.c:

Go to the source code of this file.

Functions
Psysteme	sc_elim_var (Psysteme sc, Variable v)
	package sur les systemes de contraintes sc More...
void	sc_chg_var (Psysteme s, Variable v_old, Variable v_new)
	void sc_chg_var(Psysteme s, Variable v_old, Variable v_new) this function replace the variable v_old in the system s by the variable v_new. More...
void	sc_vect_sort (Psysteme s, int(*compare)(Pvecteur *, Pvecteur *))
	the name is self explanatory, I guess. More...
void	sc_sort (Psysteme sc, Pbase sort_base, int(*compare)(Pvecteur *, Pvecteur *))
	SORT a Psysteme according to sort_base and compare (given to qsort). More...
static bool	vect_printout_order_decided_p (Pvecteur v)
Pvecteur	vect_printout_order (Pvecteur v, int(*compare)(Pvecteur *, Pvecteur *))
	Try to guess the print out order for an equality already lexicographically sorted. More...
void	sc_lexicographic_sort (Psysteme sc, int(*compare)(Pvecteur *, Pvecteur *))
	Minimize first the lexico-graphic weight of each constraint according to the comparison function "compare", and then sort the list of equalities and inequalities by increasing lexico-graphic weight. More...
bool	sc_remove_large_coef (Psysteme sc, Value val, bool equalities, bool inequalities)
	remove constraints with large coefs, possibly to avoid overflows and to keep systems as simple as possible More...

Function Documentation

sc_chg_var()

void sc_chg_var	(	Psysteme	s,
		Variable	v_old,
		Variable	v_new
	)

void sc_chg_var(Psysteme s, Variable v_old, Variable v_new) this function replace the variable v_old in the system s by the variable v_new.

Definition at line 98 of file sc_unaires.c.

{
  Pcontrainte pc;
  if (s != NULL){
    for (pc = s->egalites; pc != NULL; pc = pc->succ) {
            vect_chg_var(&(pc->vecteur), v_old, v_new);
    }
 
    for (pc = s->inegalites; pc != NULL; pc = pc->succ) {
            vect_chg_var(&(pc->vecteur), v_old, v_new);
    }
  }
}

References Ssysteme::egalites, Ssysteme::inegalites, Scontrainte::succ, vect_chg_var(), and Scontrainte::vecteur.

Referenced by build_and_test_dependence_context(), and build_third_comb().

Here is the call graph for this function:

Here is the caller graph for this function:

sc_elim_var()

Psysteme sc_elim_var	(	Psysteme	sc,
		Variable	v
	)

package sur les systemes de contraintes sc

Yi-Qing YANG, 20/05/92 Psysteme sc_elim_var(Psysteme sc, Variable v)` This function eliminate all the contraints containing the variable v

Definition at line 49 of file sc_unaires.c.

{
  Pcontrainte pr = NULL, eq;
 
  if (sc == NULL) return sc;
  else {
    eq = sc->egalites;
    while (eq != NULL) {
            if (vect_coeff(v,eq->vecteur) != 0) {
        if (pr == NULL) {
          sc->egalites = eq = eq->succ;
        }
        else {
          pr->succ = eq = eq->succ;
        }
            }
            else {
        pr = eq;
        eq = eq->succ;
            }
    }
 
    eq = sc->inegalites;
    pr = NULL;
    while (eq != NULL) {
            if (vect_coeff(v,eq->vecteur) != 0) {
        if (pr == NULL) {
          sc->inegalites = eq = eq->succ;
        }
        else {
          pr->succ = eq = eq->succ;
        }
            }
            else {
        pr = eq;
        eq = eq->succ;
            }
    }
 
    sc->nb_eq = nb_elems_list(sc->egalites);
    sc->nb_ineq = nb_elems_list(sc->inegalites);
    return sc;
  }
}

References Ssysteme::egalites, eq, Ssysteme::inegalites, nb_elems_list(), Ssysteme::nb_eq, Ssysteme::nb_ineq, Scontrainte::succ, vect_coeff(), and Scontrainte::vecteur.

Referenced by apply_abstract_effect_to_transformer(), parametric_transformer_empty_p(), sc_minmax_of_variable2(), sc_projection_concat_proj_on_variables(), TestDependence(), transformer_combine(), transformer_filter(), and transformer_projection_with_redundancy_elimination_and_check().

Here is the call graph for this function:

Here is the caller graph for this function:

sc_lexicographic_sort()

void sc_lexicographic_sort	(	Psysteme	sc,
		int(*)(Pvecteur *, Pvecteur *)	compare
	)

Minimize first the lexico-graphic weight of each constraint according to the comparison function "compare", and then sort the list of equalities and inequalities by increasing lexico-graphic weight.

Francois Irigoin

sort the system basis

sort each constraint

minimize equations: when equations are printed out, terms are moved to eliminate negative coefficients and the inner lexicographic order is broken. Furthermore, an equation can be multiplied by -1 and stay the same but be printed out differently.

we are in trouble: v1 and v2 are different but not comparable because the compare function is not strong enough

This may occur if the same local names are used for two different variables that can be live simultaneously. For instance, "predict!predict_mb:pict_struct" and "TOP-LEVEL:pict_struct" which are or seem to be both int variables in mpeg2enc. We could take a default action here or force the user to improve his/her comparison function where more information is available.

sort equalities and inequalities

Definition at line 206 of file sc_unaires.c.

{
  Pcontrainte c = CONTRAINTE_UNDEFINED;
 
  if (sc==NULL || sc_empty_p(sc) || sc_rn_p(sc))
    return;
 
  /* sort the system basis */
  vect_sort_in_place(&(sc->base), compare);
 
  /* sort each constraint */
  contrainte_vect_sort(sc_egalites(sc), compare);
  contrainte_vect_sort(sc_inegalites(sc), compare);
 
  /* minimize equations: when equations are printed out, terms are moved
     to eliminate negative coefficients and the inner lexicographic
     order is broken. Furthermore, an equation can be multiplied by -1
     and stay the same but be printed out differently. */
  for(c = sc_egalites(sc); !CONTRAINTE_UNDEFINED_P(c); c = contrainte_succ(c))
  {
    Pvecteur v = contrainte_vecteur(c);
 
    if(!VECTEUR_NUL_P(v) && !vect_printout_order_decided_p(v)) {
      int cmp = 0;
      Pvecteur v1 = vect_dup(v);
      Pvecteur v2 = vect_multiply(vect_dup(v), VALUE_MONE);
 
      v1 = vect_printout_order(v1, compare);
      v2 = vect_printout_order(v2, compare);
      cmp = vect_lexicographic_compare(v1, v2, compare);
      if(cmp>0) {
        contrainte_vecteur(c) =
          vect_multiply(contrainte_vecteur(c), VALUE_MONE);
        vect_rm(v1);
        vect_rm(v2);
      }
      else if(cmp<0) {
        vect_rm(v1);
        vect_rm(v2);
      }
      else {
        /* we are in trouble: v1 and v2 are different but not
           comparable because the compare function is not strong
           enough */
        /* This may occur if the same local names are used for two
           different variables that can be live simultaneously. For
           instance, "predict!predict_mb:pict_struct" and
           "TOP-LEVEL:pict_struct" which are or seem to be both int
           variables in mpeg2enc. We could take a default action here
           or force the user to improve his/her comparison function
           where more information is available. */
        assert(false);
      }
    }
  }
 
  /* sort equalities and inequalities */
  sc->egalites = equations_lexicographic_sort(sc->egalites, compare);
  sc->inegalites = inequalities_lexicographic_sort(sc->inegalites, compare);
}

References assert, Ssysteme::base, contrainte_succ, CONTRAINTE_UNDEFINED, CONTRAINTE_UNDEFINED_P, contrainte_vect_sort(), contrainte_vecteur, Ssysteme::egalites, equations_lexicographic_sort(), Ssysteme::inegalites, inequalities_lexicographic_sort(), sc_empty_p(), sc_rn_p(), VALUE_MONE, vect_dup(), vect_lexicographic_compare(), vect_multiply(), vect_printout_order(), vect_printout_order_decided_p(), vect_rm(), vect_sort_in_place(), and VECTEUR_NUL_P.

Referenced by make_bound_expression(), text_continuation(), text_pointer_value(), text_points_to_relation(), and text_transformer().

Here is the call graph for this function:

Here is the caller graph for this function:

sc_remove_large_coef()

bool sc_remove_large_coef	(	Psysteme	sc,
		Value	val,
		bool	equalities,
		bool	inequalities
	)

remove constraints with large coefs, possibly to avoid overflows and to keep systems as simple as possible

Parameters

sc	system to consider, which may be modified
val	maximum coef allowed, >=0, 0 meant to do nothing
equalities	whether to process equalities
inequalities	whether to process inequalities

Returns

whether the system was changed

Definition at line 277 of file sc_unaires.c.

{
  bool changed = false;
 
  // nothing to do in some simple cases
  if (sc==NULL || sc_empty_p(sc) || sc_rn_p(sc))
    return changed;
 
  if (equalities && sc->egalites) {
    int nb = sc->nb_eq;
    sc->egalites = contrainte_remove_large_coef(sc->egalites, val);
    sc->nb_eq = nb_elems_list(sc->egalites);
    changed |= nb!=sc->nb_eq;
  }
 
  if (inequalities && sc->inegalites) {
    int nb = sc->nb_ineq;
    sc->inegalites = contrainte_remove_large_coef(sc->inegalites, val);
    sc->nb_ineq = nb_elems_list(sc->inegalites);
    changed |= nb!=sc->nb_ineq;
  }
 
  return changed;
}

References contrainte_remove_large_coef(), Ssysteme::egalites, Ssysteme::inegalites, nb_elems_list(), Ssysteme::nb_eq, Ssysteme::nb_ineq, sc_empty_p(), and sc_rn_p().

Here is the call graph for this function:

sc_sort()

void sc_sort	(	Psysteme	sc,
		Pbase	sort_base,
		int(*)(Pvecteur *, Pvecteur *)	compare
	)

SORT a Psysteme according to sort_base and compare (given to qsort).

Each constraint is first sorted according to the compare function. Then list of constraints are sorted.

The only expected property is that two calls to this function with the same system (whatever its order) and same sort_base that covers all variables and same compare function should give the same result.

The function is quite peculiar and the order is relevant for some code generation issues...

Definition at line 137 of file sc_unaires.c.

{
  sc_vect_sort(sc, compare);
  sc->inegalites =
    contrainte_sort(sc->inegalites, sc->base, sort_base, true, true);
  sc->egalites =
    contrainte_sort(sc->egalites, sc->base, sort_base, true, true);
}

References Ssysteme::base, contrainte_sort(), Ssysteme::egalites, Ssysteme::inegalites, and sc_vect_sort().

Referenced by generate_io_collect_or_update().

Here is the call graph for this function:

Here is the caller graph for this function:

sc_vect_sort()

void sc_vect_sort	(	Psysteme	s,
		int(*)(Pvecteur *, Pvecteur *)	compare
	)

the name is self explanatory, I guess.

FC 24/11/94 the vectors of the system are sorted. see man qsort about the compare functions.

Definition at line 116 of file sc_unaires.c.

{
  if (s==NULL || sc_empty_p(s) || sc_rn_p(s))
    return;
 
  contrainte_vect_sort(sc_egalites(s), compare);
  contrainte_vect_sort(sc_inegalites(s), compare);
}

References contrainte_vect_sort(), sc_empty_p(), and sc_rn_p().

Referenced by generate_io_collect_or_update(), generate_io_system(), sc_sort(), and sort_psysteme().

Here is the call graph for this function:

Here is the caller graph for this function:

vect_printout_order()

Pvecteur vect_printout_order	(	Pvecteur	v,
		int(*)(Pvecteur *, Pvecteur *)	compare
	)

Try to guess the print out order for an equality already lexicographically sorted.

before cc might be freed

append v_neg to v

do not follow v_neg for ever

Definition at line 170 of file sc_unaires.c.

{
  Pvecteur v_neg = VECTEUR_NUL;
  Pvecteur cc = VECTEUR_UNDEFINED;
  Pvecteur succ = VECTEUR_UNDEFINED;
 
  for(cc = v; !VECTEUR_NUL_P(cc); cc = succ) {
    succ = vecteur_succ(cc); /* before cc might be freed */
    if(vecteur_val(cc) < 0 || vecteur_var(cc)==TCST) {
      vect_add_elem(&v_neg, vecteur_var(cc), vecteur_val(cc));
      vect_erase_var(&v, vecteur_var(cc));
    }
  }
 
  vect_sort_in_place(&v, compare);
  vect_sort_in_place(&v_neg, compare);
 
  /* append v_neg to v */
  for(cc=v; !VECTEUR_NUL_P(cc); cc = vecteur_succ(cc)) {
    if(VECTEUR_NUL_P(vecteur_succ(cc))) {
      vecteur_succ(cc) = v_neg;
      break; /* do not follow v_neg for ever */
    }
  }
 
  return v;
}

References TCST, vect_add_elem(), vect_erase_var(), vect_sort_in_place(), VECTEUR_NUL, VECTEUR_NUL_P, vecteur_succ, VECTEUR_UNDEFINED, vecteur_val, and vecteur_var.

Referenced by sc_lexicographic_sort().

Here is the call graph for this function:

Here is the caller graph for this function:

vect_printout_order_decided_p()

static bool vect_printout_order_decided_p ( Pvecteur  v )

static

constant vectors are considered decided

Definition at line 149 of file sc_unaires.c.

{
  bool decided_p = false;
  int positive_terms = 0;
  int negative_terms = 0;
  Pvecteur coord = VECTEUR_UNDEFINED;
 
  for(coord = v; !VECTEUR_NUL_P(coord); coord = coord->succ) {
    if(vecteur_var(coord)!= TCST)
      (value_pos_p(vecteur_val(coord))) ?
        positive_terms++ :  negative_terms++;
  }
  /* constant vectors are considered decided */
  decided_p = ((positive_terms!=negative_terms) ||
               (positive_terms==0 && negative_terms==0));
 
  return decided_p;
}

References Svecteur::succ, TCST, value_pos_p, VECTEUR_NUL_P, VECTEUR_UNDEFINED, vecteur_val, and vecteur_var.

Referenced by sc_lexicographic_sort().

Here is the caller graph for this function: