sc.c File Reference

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

Include dependency graph for sc.c:

Go to the source code of this file.

Functions
void	norm_syst (Psysteme sc)
	norm_syst(Psysteme): division des contraintes, egalites ou inegalites, par le PGCD des coefficients de chaque contrainte; More...
Psysteme	sc_make (Pcontrainte leg, Pcontrainte lineg)
	Psysteme sc_make(Pcontrainte leg, Pcontrainte lineg): allocation et initialisation d'un systeme d'equations et inequations lineaires a partir de deux listes de contraintes, une liste d'egalites et une liste d'inegalites. More...
Psysteme	sc_translate (Psysteme s, Pbase b, char *(*variable_name)())
	Psysteme sc_translate(Psysteme s, Pbase b, char * (*variable_name)()): reecriture du systeme s dans la base b basee sur les noms des vecteurs de base; tous les vecteurs de base utilises dans s doivent avoir un vecteur de base de meme nom dans b. More...
Psysteme	sc_substitute_dimension (Psysteme s, Variable i, Pvecteur v)
	Psysteme sc_substitute_dimension(Psysteme s, Variable i, Pvecteur v): The ith dimension of all constraints c is updated: More...
Psysteme	sc_variable_rename (Psysteme s, Variable v_old, Variable v_new)
	Psysteme sc_variable_rename(Psysteme s, Variable v_old, Variable v_new): reecriture du systeme s remplacant toutes les occurences de la coordonnees v_old par des occurences de v_new. More...
Psysteme	sc_rename_variables (Psysteme s, bool(*renamed_p)(), Variable(*new_variable)())
	Psysteme sc_rename_variables(s, renamed_p, new_variable) Psysteme s; bool (*renamed_p)(Variable); Variable (*new_variable)(Variable);. More...
Psysteme	sc_variables_rename (Psysteme s, Pvecteur pv_old, Pvecteur pv_new, get_variable_name_t variable_name)
	Psysteme sc_variables_rename(Psysteme s, Pvecteur pv_old, Pvecteur pv_new): reecriture du systeme s remplacant toutes les occurences des coordonnees de pv_old par des occurences de pv_new. More...
void	sc_base_remove_variable (Psysteme sc, Variable v)
void	sc_base_add_variable (Psysteme sc, Variable var)
bool	sc_consistent_p (Psysteme sc)
	bool sc_consistent_p(Psysteme sc): check that sc is well defined, that the numbers of equalities and inequalities are consistent with the lists of equalities and inequalities, and that every variable in the constraints is in the base More...
bool	sc_weak_consistent_p (Psysteme sc)
	check that sc is well defined, that the numbers of equalities and inequalities are consistent with the lists of equalities and inequalities, that the dimension is consistent with the basis, that the basis itself is consistent (all coefficients must be 1), and that every variable in the constraints is in the basis. More...
void	sc_separate_on_vars (Psysteme s, Pbase b, Psysteme *pwith, Psysteme *pwithout)

Function Documentation

norm_syst()

void norm_syst

(

Psysteme

sc

)

norm_syst(Psysteme): division des contraintes, egalites ou inegalites, par le PGCD des coefficients de chaque contrainte;

la faisabilite ou la non-faisabilite n'est pas testee: le terme constant ne devrait pas etre pris en compte dans norm_eq().

Definition at line 53 of file sc.c.

{
    Pcontrainte eq;
 
    for (eq=sc->egalites;eq!=NULL;eq=eq->succ)
        norm_eq(eq);
    for (eq=sc->inegalites;eq!=NULL;eq=eq->succ)
        norm_eq(eq);
}

References eq, norm_eq(), and Scontrainte::succ.

Here is the call graph for this function:

sc_base_add_variable()

void sc_base_add_variable	(	Psysteme	sc,
		Variable	var
	)

Definition at line 248 of file sc.c.

{
 
    Pbase b1 = sc->base; 
 
    if (!VECTEUR_NUL_P(b1)) {
        for(; !VECTEUR_NUL_P(b1) && !variable_equal(vecteur_var(b1), var);
            b1 = b1->succ);
        if (VECTEUR_NUL_P(b1)) {
            for (b1 = sc->base; !VECTEUR_NUL_P(b1->succ); b1=b1->succ);
            b1->succ = vect_new(var, VALUE_ONE);
            sc_dimension(sc)++;
        } 
    }
    else {
        sc->base = vect_new(var, VALUE_ONE);
        sc_dimension(sc)++; }
}

References b1, VALUE_ONE, variable_equal(), vect_new(), VECTEUR_NUL_P, and vecteur_var.

Referenced by add_value_to_transformer_space(), fortran_user_call_to_transformer(), and sc_restricted_to_variables_transitive_closure().

Here is the call graph for this function:

Here is the caller graph for this function:

sc_base_remove_variable()

void sc_base_remove_variable	(	Psysteme	sc,
		Variable	v
	)

Definition at line 239 of file sc.c.

{
    sc_base(sc) = base_remove_variable(sc_base(sc),v);
    sc_dimension(sc) --;
}

References base_remove_variable().

Referenced by cell_reference_sc_exact_projection_along_variable(), loop_regions_normalize(), new_system_with_only_live_variable(), parametric_transformer_empty_p(), region_exact_projection_along_variable(), region_sc_projection_along_variables_ofl_ctrl(), region_sc_projection_ofl_along_parameters(), sc_projection_optim_along_vecteur_ofl(), 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_consistent_p()

bool sc_consistent_p

(

Psysteme

sc

)

bool sc_consistent_p(Psysteme sc): check that sc is well defined, that the numbers of equalities and inequalities are consistent with the lists of equalities and inequalities, and that every variable in the constraints is in the base

Francois Irigoin, 7 July 1993

Note:

• it also checks that every variable in the basis is used with a non-zero coefficient in at least one constraint (although there is no reason for that)
• there is no explicit check of TCST in the basis; TCST should not be in the basis

This assert is too bad ! I remove it.

Alexis Platonoff, 31 january 1995

assert(consistent);

Definition at line 282 of file sc.c.

{
  bool consistent;
  bool flawed = false; 
 
  consistent = !SC_UNDEFINED_P(sc);
 
  if(consistent) {
    if(sc->nb_eq != safe_nb_elems_list(sc_egalites(sc), sc->nb_eq)) {
      fprintf(stderr, "Inconsistent number of equalities\n");
      flawed = true;
    }
    if(sc->nb_ineq != safe_nb_elems_list(sc_inegalites(sc), sc->nb_ineq)) {
      fprintf(stderr, "Inconsistent number of inequalities\n");
      flawed = true;
    }
    if(sc_dimension(sc) != base_dimension(sc_base(sc))) {
      fprintf(stderr, "Inconsistent dimension\n");
      flawed = true;
    }
    if(!base_normalized_p(sc_base(sc))) {
      fprintf(stderr, "Inconsistent base\n");
      flawed = true;
    }
  }      
  consistent = consistent && !flawed;
 
  if(consistent) {
    Pcontrainte eq = CONTRAINTE_UNDEFINED;
    Pbase diagonale = BASE_UNDEFINED;
    Pvecteur pv = VECTEUR_UNDEFINED;
    Pbase diff = BASE_UNDEFINED;
 
    for(eq = sc->egalites; eq!= NULL; eq=eq->succ) {
      for (pv = eq->vecteur;pv!= NULL;pv=pv->succ)
        if (pv->var != TCST)
          vect_chg_coeff(&diagonale,pv->var, VALUE_ONE);
    }
    for(eq = sc->inegalites; eq!= NULL; eq=eq->succ) {
      for (pv = eq->vecteur;pv!= NULL;pv=pv->succ)
        if (pv->var != TCST)
          vect_chg_coeff(&diagonale,pv->var, VALUE_ONE);
    }
    diff = base_difference(diagonale, sc_base(sc));
    consistent = BASE_NULLE_P(diff);
    if(!consistent) {
      fprintf(stderr, "The base does not cover all the constraints\n");
      fprintf(stderr, "Current base\n");
      vect_dump(sc_base(sc));
      fprintf(stderr, "Necessary base\n");
      vect_dump(diagonale);
      fprintf(stderr, "Base difference\n");
      vect_dump(diff);
    }
  }
 
  /* This assert is too bad ! I remove it.
   *
   * Alexis Platonoff, 31 january 1995 */
  /*    assert(consistent); */
 
  return consistent;
}

References base_difference(), base_dimension, base_normalized_p(), BASE_NULLE_P, BASE_UNDEFINED, CONTRAINTE_UNDEFINED, Ssysteme::egalites, eq, fprintf(), Ssysteme::inegalites, Ssysteme::nb_eq, Ssysteme::nb_ineq, safe_nb_elems_list(), Scontrainte::succ, Svecteur::succ, TCST, VALUE_ONE, Svecteur::var, vect_chg_coeff(), vect_dump(), Scontrainte::vecteur, and VECTEUR_UNDEFINED.

Referenced by add_bounding_box_constraints(), build_third_comb(), gcd_and_constant_dependence_test(), prepare_reindexing(), sc_bounded_normalization(), sc_proj_optim_on_di_ofl(), sc_projection_optim_along_vecteur_ofl(), simplify_float_constraint_system(), and TestDependence().

Here is the call graph for this function:

Here is the caller graph for this function:

sc_make()

Psysteme sc_make	(	Pcontrainte	leg,
		Pcontrainte	lineg
	)

Psysteme sc_make(Pcontrainte leg, Pcontrainte lineg): allocation et initialisation d'un systeme d'equations et inequations lineaires a partir de deux listes de contraintes, une liste d'egalites et une liste d'inegalites.

ATTENTION: les deux listes leg et lineq ne sont pas dupliquees; un appel a cette fonction peut donc creer du sharing entre structures de donnees

Ancien nom: mk_syst()

Modifications:

• ajout de l'initialisation de base et de dimension par un appel a sc_creer_base()

Definition at line 78 of file sc.c.

{
    Psysteme s;
 
    s = (Psysteme ) MALLOC(sizeof(Ssysteme),SYSTEME,"sc_make");
    s->egalites = leg;
    s->inegalites = lineg;
    s->nb_eq = nb_elems_list(leg);
    s->nb_ineq = nb_elems_list(lineg);
    s->base = VECTEUR_UNDEFINED;
    sc_creer_base(s);
    return(s);
}

References Ssysteme::base, Ssysteme::egalites, Ssysteme::inegalites, MALLOC, nb_elems_list(), Ssysteme::nb_eq, Ssysteme::nb_ineq, sc_creer_base(), SYSTEME, and VECTEUR_UNDEFINED.

Referenced by adg_dataflowgraph(), adg_dataflowgraph_with_extremities(), adg_max_of_leaves(), adg_suppress_2nd_in_1st_ps(), affine_to_transformer(), algorithm_row_echelon_generic(), broadcast_conditions(), build_third_comb(), check_range_wrt_precondition(), constraint_to_bound(), constraints_to_loop_bound(), dj_simple_inegs_to_eg(), dj_system_complement(), expression_and_precondition_to_integer_interval(), extract_common_syst(), extract_nredund_subsystem(), fortran_user_function_call_to_transformer(), generic_equality_to_transformer(), generic_minmax_to_transformer(), get_other_constraints(), include_trans_on_LC_in_ref(), include_trans_on_LC_in_sc(), include_trans_on_LC_in_sc2(), integer_divide_to_transformer(), integer_expression_and_precondition_to_integer_interval(), integer_power_to_transformer(), integer_right_shift_to_transformer(), integer_value_and_precondition_to_integer_interval(), logical_binary_function_to_transformer(), logical_constant_to_transformer(), make_primal(), pa_path_to_few_disjunct_ofl_ctrl(), partial_broadcast_coefficients(), prepare_reindexing(), relation_to_transformer(), sc_empty(), sc_gen_write(), sc_separate_on_vars(), sc_strong_normalize2(), sc_strong_normalize_and_check_feasibility(), sc_strong_normalize_and_check_feasibility2(), sc_supress_parallel_redund_constraints(), sc_supress_same_constraints(), simple_addition_to_transformer(), simple_affine_to_transformer(), suppress_sc_in_sc(), system_inversion_restrict(), transformer_add_loop_index_initialization(), transformer_identity(), and transitive_closure_system().

Here is the call graph for this function:

sc_rename_variables()

Psysteme sc_rename_variables	(	Psysteme	s,
		bool (*)()	renamed_p,
		Variable (*)()	new_variable
	)

Psysteme sc_rename_variables(s, renamed_p, new_variable) Psysteme s; bool (*renamed_p)(Variable); Variable (*new_variable)(Variable);.

what: driven renaming of variables in s. how: scans, decides and replaces. input: Psysteme s, plus the decision and replacement functions output: s is returned. side effects:

• the system is modified in place. bugs or features:
• was written by FC...

Parameters

renamed_p	what: driven renaming of variables in s. how: scans, decides and replaces. input: Psysteme s, plus the decision and replacement functions output: s is returned. side effects: the system is modified in place. bugs or features: was written by FC... ariable
new_variable	what: driven renaming of variables in s. how: scans, decides and replaces. input: Psysteme s, plus the decision and replacement functions output: s is returned. side effects: the system is modified in place. bugs or features: was written by FC... ariable

Definition at line 198 of file sc.c.

{
    Pcontrainte c;
 
    if(SC_UNDEFINED_P(s)) return(s);
 
    for(c=sc_egalites(s); c!=NULL; c=c->succ)
        (void) vect_rename_variables(contrainte_vecteur(c),
                                     renamed_p, new_variable);
 
    for(c=sc_inegalites(s); c!=NULL; c=c->succ)
        (void) vect_rename_variables(contrainte_vecteur(c),
                                     renamed_p, new_variable);
 
    (void) vect_rename_variables(sc_base(s), renamed_p, new_variable);
 
    return(s);
}

References contrainte_vecteur, new_variable, Scontrainte::succ, and vect_rename_variables().

Referenced by shift_system_to_prime_variables().

Here is the call graph for this function:

Here is the caller graph for this function:

sc_separate_on_vars()

void sc_separate_on_vars	(	Psysteme	s,
		Pbase	b,
		Psysteme *	pwith,
		Psysteme *	pwithout
	)

Definition at line 418 of file sc.c.

{
    Pcontrainte i_with, e_with, i_without, e_without;
 
    Pcontrainte_separate_on_vars(sc_inegalites(s), b, &i_with, &i_without);
    Pcontrainte_separate_on_vars(sc_egalites(s), b, &e_with, &e_without);
 
    *pwith = sc_make(e_with, i_with),
    *pwithout = sc_make(e_without, i_without);
}

References Pcontrainte_separate_on_vars(), and sc_make().

Referenced by generate_remapping_code().

Here is the call graph for this function:

Here is the caller graph for this function:

sc_substitute_dimension()

Psysteme sc_substitute_dimension	(	Psysteme	s,
		Variable	i,
		Pvecteur	v
	)

Psysteme sc_substitute_dimension(Psysteme s, Variable i, Pvecteur v): The ith dimension of all constraints c is updated:

c = c + c_i v

Vector v is untouched

translate all equations

translate all inequalities

update basis in s

Definition at line 130 of file sc.c.

{
  Pcontrainte e;
  Pcontrainte c;
 
  if(!SC_UNDEFINED_P(s)) {
    //vect_add_elem(&v, i, VALUE_MONE);
    /* translate all equations */
    for(e=s->egalites; !CONTRAINTE_UNDEFINED_P(e); e = e->succ)
      (void) contrainte_substitute_dimension(e, i, v);
 
    /* translate all inequalities */
    for(c=s->inegalites; !CONTRAINTE_UNDEFINED_P(c); c = c->succ)
      (void) contrainte_substitute_dimension(c, i, v);
 
    /* update basis in s */
    vect_rm(s->base);
    s->base = (Pbase) NULL;
    sc_creer_base(s);
  }
  return s;
}

References Ssysteme::base, contrainte_substitute_dimension(), CONTRAINTE_UNDEFINED_P, Ssysteme::egalites, Ssysteme::inegalites, sc_creer_base(), Scontrainte::succ, and vect_rm().

Here is the call graph for this function:

sc_translate()

Psysteme sc_translate	(	Psysteme	s,
		Pbase	b,
		char * (*)()	variable_name
	)

Psysteme sc_translate(Psysteme s, Pbase b, char * (*variable_name)()): reecriture du systeme s dans la base b basee sur les noms des vecteurs de base; tous les vecteurs de base utilises dans s doivent avoir un vecteur de base de meme nom dans b.

translate all equations

translate all inequalities

update basis in s; its dimension should not change

Definition at line 99 of file sc.c.

{
    Pcontrainte e;
    Pcontrainte i;
 
    if(!SC_UNDEFINED_P(s)) {
 
        /* translate all equations */
        for(e=s->egalites; !CONTRAINTE_UNDEFINED_P(e); e = e->succ)
            (void) contrainte_translate(e, b, variable_name);
 
        /* translate all inequalities */
        for(i=s->inegalites; !CONTRAINTE_UNDEFINED_P(i); i = i->succ)
            (void) contrainte_translate(i, b, variable_name);
 
        /* update basis in s; its dimension should not change */
        s->base = vect_translate(s->base, b, variable_name);
    }
    return s;
}

References contrainte_translate(), CONTRAINTE_UNDEFINED_P, Scontrainte::succ, variable_name(), and vect_translate().

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

sc_variable_rename()

Psysteme sc_variable_rename	(	Psysteme	s,
		Variable	v_old,
		Variable	v_new
	)

Psysteme sc_variable_rename(Psysteme s, Variable v_old, Variable v_new): reecriture du systeme s remplacant toutes les occurences de la coordonnees v_old par des occurences de v_new.

v_new MUST NOT already be in the base.

rename all equations

rename all inequalities

update basis in s; its dimension should not change

Definition at line 157 of file sc.c.

{
    Pcontrainte e, i;
 
    /* v_new MUST NOT already be in the base. */
    assert(vect_coeff(v_new, s->base)==VALUE_ZERO);
 
    if(!SC_UNDEFINED_P(s)) 
    {
        /* rename all equations */
        for(e=s->egalites; !CONTRAINTE_UNDEFINED_P(e); e = e->succ)
            (void) contrainte_variable_rename(e, v_old, v_new);
 
        /* rename all inequalities */
        for(i=s->inegalites; !CONTRAINTE_UNDEFINED_P(i); i = i->succ)
            (void) contrainte_variable_rename(i, v_old, v_new);
 
        /* update basis in s; its dimension should not change */
        s->base = vect_variable_rename(s->base, v_old, v_new);
    }
 
    return s;
}

References assert, CONTRAINTE_UNDEFINED_P, contrainte_variable_rename(), Scontrainte::succ, VALUE_ZERO, vect_coeff(), and vect_variable_rename().

Referenced by adg_dataflowgraph(), c_convex_effects_on_actual_parameter_forward_translation(), copy_write_statement_with_cumulated_regions(), dj_variable_rename(), interlaced_basic_workchunk_regions_p(), sc_change_baseindex(), sc_variables_rename(), transformer_combine(), transformer_domain_intersection(), and transformer_value_substitute().

Here is the call graph for this function:

Here is the caller graph for this function:

sc_variables_rename()

Psysteme sc_variables_rename	(	Psysteme	s,
		Pvecteur	pv_old,
		Pvecteur	pv_new,
		get_variable_name_t	variable_name
	)

Psysteme sc_variables_rename(Psysteme s, Pvecteur pv_old, Pvecteur pv_new): reecriture du systeme s remplacant toutes les occurences des coordonnees de pv_old par des occurences de pv_new.

Definition at line 224 of file sc.c.

{
    Pvecteur pv;
    for (pv = pv_old; !VECTEUR_UNDEFINED_P(pv); pv = pv->succ) {
        Variable var_new = base_find_variable_name(pv_new, vecteur_var(pv),
                                                   variable_name);
        if (!VARIABLE_UNDEFINED_P(var_new))
            s = sc_variable_rename(s,pv->var,var_new);
    }  
    return s;
}

References base_find_variable_name(), sc_variable_rename(), Svecteur::succ, Svecteur::var, variable_name(), VARIABLE_UNDEFINED_P, VECTEUR_UNDEFINED_P, and vecteur_var.

Referenced by loop_nest_movement_generation(), loop_nest_to_wp65_code(), and movement_computation().

Here is the call graph for this function:

Here is the caller graph for this function:

sc_weak_consistent_p()

bool sc_weak_consistent_p

(

Psysteme

sc

)

check that sc is well defined, that the numbers of equalities and inequalities are consistent with the lists of equalities and inequalities, that the dimension is consistent with the basis, that the basis itself is consistent (all coefficients must be 1), and that every variable in the constraints is in the basis.

Each component in the basis should only appear once thanks to the specifications of Pvecteur (this is not checked).

Francois Irigoin, 13 November 1995

Note:

• there is no explicit check of TCST in the basis; TCST should not be in the basis for some use of Psystemes, like transformers in Linear/C3 Library.

The test is broken down into three lines to increase the information available when Valgrind detects a memory access error.

assert(weak_consistent);

Definition at line 362 of file sc.c.

{
    bool weak_consistent;
 
    weak_consistent = !SC_UNDEFINED_P(sc);
 
    if(weak_consistent) {
      /* The test is broken down into three lines to increase the
         information available when Valgrind detects a memory access
         error. */
      int neq =  nb_elems_list(sc_egalites(sc));
      int nineq = nb_elems_list(sc_inegalites(sc));
      int dim =  base_dimension(sc_base(sc));
 
      weak_consistent = (sc->nb_eq == neq);
      weak_consistent = weak_consistent
        && (sc->nb_ineq == nineq);
      weak_consistent = weak_consistent
        && (sc_dimension(sc) == dim);
    }
 
    if(weak_consistent && sc_dimension(sc) != 0) {
      Pbase b = sc_base(sc);
        weak_consistent = base_normalized_p(b);
    }
 
    if(weak_consistent) {
        Pcontrainte eq;
        Pvecteur pv;
        Pbase diagonale = BASE_NULLE;
 
        for(eq = sc->egalites; eq!= NULL; eq=eq->succ) {
            for (pv = eq->vecteur;pv!= NULL;pv=pv->succ)
                if (pv->var != TCST)
                    vect_chg_coeff(&diagonale,pv->var, VALUE_ONE);
        }
        for(eq = sc->inegalites; eq!= NULL; eq=eq->succ) {
            for (pv = eq->vecteur;pv!= NULL;pv=pv->succ)
                if (pv->var != TCST)
                    vect_chg_coeff(&diagonale,pv->var, VALUE_ONE);
        }
        weak_consistent =  base_included_p(diagonale, sc_base(sc));
        base_rm(diagonale);
    }
 
    /* assert(weak_consistent); */
 
    return weak_consistent;
}

References base_dimension, base_included_p(), base_normalized_p(), BASE_NULLE, base_rm, Ssysteme::egalites, eq, Ssysteme::inegalites, nb_elems_list(), Ssysteme::nb_eq, Ssysteme::nb_ineq, Scontrainte::succ, Svecteur::succ, TCST, VALUE_ONE, Svecteur::var, vect_chg_coeff(), and Scontrainte::vecteur.

Referenced by main(), region_consistent_p(), sc_elim_redund_with_first_ofl_ctrl(), sc_simplex_feasibility_ofl_ctrl_fixprec(), sc_strong_normalize2(), sc_strong_normalize_and_check_feasibility(), sc_strong_normalize_and_check_feasibility2(), TestDependence(), transformer_formal_parameter_projection(), transformer_general_consistency_p(), and transformer_return_value_projection().

Here is the call graph for this function:

Here is the caller graph for this function: