predicats.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 dependency graph for predicats.c:

Go to the source code of this file.

Functions
bool	eq_smg (Pcontrainte c1, Pcontrainte c2)
	package contrainte - tests sur des contraintes More...
bool	inequalities_opposite_p (Pcontrainte c1, Pcontrainte c2)
	bool inequalities_opposite_p(Pcontrainte c1, Pcontrainte c2): True if the non-constant part of c1 is the opposite of the non-constant part of c2. More...
bool	egalite_equal (Pcontrainte eg1, Pcontrainte eg2)
	bool egalite_equal(Pcontrainte eg1, Pcontrainte eg2): teste l'equivalence de deux egalites; leurs coefficients peuvent etre tous egaux ou tous opposes; pour obtenir une meilleure equivalence il faut commencer par reduire leurs coefficients par les PGCD More...
bool	contrainte_equal (Pcontrainte c1, Pcontrainte c2)
	bool contrainte_equal(Pcontrainte c1, Pcontrainte c2): test d'egalite des contraintes c1 et c2; elles sont egales si tous leurs coefficients et leur termes constants sont egaux; il faut les avoir normalisees auparavant pour etre sur de leur egalite; More...
bool	contrainte_parallele (Pcontrainte c1, Pcontrainte c2, Value *pa1, Value *pa2)
	Les deux contraintes c1 et c2 sont paralleles s'il existe deux coefficients a1 et a2 tels que a1 c1 + a2 c2 est reduit un terme constant K. More...
bool	contrainte_constante_p (Pcontrainte c)
	bool contrainte_constante_p(Pcontrainte c): test de contrainte triviale sans variables (ie du type 0<= K ou 0<=0 ou 0 == 0 ou 0 == K) More...
bool	vect_constant_p (Pvecteur v)
	bool vect_constant_p(Pvecteur v): v contains only a constant term, may be zero More...
bool	contrainte_verifiee (Pcontrainte ineg, bool eq_p)
	bool contrainte_verifiee(Pcontrainte ineg, bool eq_p): test de faisabilite d'inegalite (eq_p == false) ou d'egalite triviale More...
bool	contrainte_oppos (Pcontrainte ineg1, Pcontrainte ineg2)
	bool contrainte_oppos(Pcontrainte ineg1, Pcontrainte ineg2): indique si 2 inegalites forment une egalite ou si deux egalites sont equivalentes. More...
bool	constraint_without_vars (Pcontrainte c, Pbase vars)
	bool constraint_without_vars(c, vars) Pcontrainte c; Pbase vars; More...
bool	constraints_without_vars (Pcontrainte pc, Pbase vars)
	bool constraints_without_vars(pc, vars) Pcontrainte pc; Pbase vars; More...
Value	contrainte_eval (Pvecteur c, Pvecteur v)
	Evaluate constraint c according to values in v and return the constant obtained. More...
bool	contrainte_eval_p (Pvecteur c, Pvecteur v, bool is_equality_p)
	Evaluate constraint c according to values in v and return true if the constraint is met. More...
bool	equality_eval_p (Pvecteur c, Pvecteur v)
bool	inequality_eval_p (Pvecteur c, Pvecteur v)

Function Documentation

constraint_without_vars()

bool constraint_without_vars	(	Pcontrainte	c,
		Pbase	vars
	)

bool constraint_without_vars(c, vars) Pcontrainte c; Pbase vars;

IN: c, vars

OUT: returned boolean

returns if the current constraint uses none of the variables in vars.

(c) FC 16/05/94

Parameters

vars

ars

Definition at line 276 of file predicats.c.

{
    Pbase
        b = BASE_NULLE;
 
    for(b=vars;
        b!=BASE_NULLE;
        b=b->succ)
        if (vect_coeff(var_of(b), c->vecteur)!=(Value) 0) return(false);
 
    return(true);           
}

References BASE_NULLE, Svecteur::succ, var_of, and vect_coeff().

Referenced by constraints_without_vars(), and Pcontrainte_separate_on_vars().

Here is the call graph for this function:

Here is the caller graph for this function:

constraints_without_vars()

bool constraints_without_vars	(	Pcontrainte	pc,
		Pbase	vars
	)

bool constraints_without_vars(pc, vars) Pcontrainte pc; Pbase vars;

IN: c, vars

OUT: returned boolean

returns true if none of the constraints use the variables in vars.

Parameters

pc	c
vars	ars

Definition at line 300 of file predicats.c.

{
    Pcontrainte c;
 
    for (c=pc;
         c!=NULL;
         c=c->succ)
        if (!constraint_without_vars(c, vars)) return(false);
 
    return(true);
}       

References constraint_without_vars(), and Scontrainte::succ.

Here is the call graph for this function:

contrainte_constante_p()

bool contrainte_constante_p

(

Pcontrainte

c

)

bool contrainte_constante_p(Pcontrainte c): test de contrainte triviale sans variables (ie du type 0<= K ou 0<=0 ou 0 == 0 ou 0 == K)

Les equations non-faisables ne sont pas detectees.

Modifications:

• utilisation de CONTRAINTE_NULLE_P() Bugs:
• should assert !CONTRAINTE_UNDEFINED_P(c)

Definition at line 192 of file predicats.c.

{
 
    if (CONTRAINTE_NULLE_P(c))
        return(true);
    else {
        return vect_constant_p(contrainte_vecteur(c));
    }
}

References CONTRAINTE_NULLE_P, contrainte_vecteur, and vect_constant_p().

Referenced by combiner_ofl_with_test(), contrainte_subst_ofl_ctrl(), contrainte_verifiee(), gcd_and_constant_dependence_test(), sc_force_variable_to_zero(), and sc_strong_normalize_and_check_feasibility().

Here is the call graph for this function:

Here is the caller graph for this function:

contrainte_equal()

bool contrainte_equal	(	Pcontrainte	c1,
		Pcontrainte	c2
	)

bool contrainte_equal(Pcontrainte c1, Pcontrainte c2): test d'egalite des contraintes c1 et c2; elles sont egales si tous leurs coefficients et leur termes constants sont egaux; il faut les avoir normalisees auparavant pour etre sur de leur egalite;

La contrainte CONTRAINTE_UNDEFINED est assimilee a la contrainte nulle

Ancien nom: ineg_same()

Modifications:

• utilisation de CONTRAINTE_UNDEFINED_P() et contrainte_vecteur() (FI, 08/12/89)

Parameters

c1	1
c2	2

Definition at line 128 of file predicats.c.

{
    register bool 
        undef1 = CONTRAINTE_UNDEFINED_P(c1),
        undef2 = CONTRAINTE_UNDEFINED_P(c2);
 
    if (undef1 || undef2) 
        return(undef1 && undef2);
 
    return(vect_equal(contrainte_vecteur(c1),
                      contrainte_vecteur(c2)));
}

References CONTRAINTE_UNDEFINED_P, contrainte_vecteur, and vect_equal().

Referenced by extract_common_constraints(), sc_elim_db_constraints(), sc_elim_double_constraints(), sc_kill_db_eg(), sc_safe_elim_db_constraints(), and sc_safe_kill_db_eg().

Here is the call graph for this function:

Here is the caller graph for this function:

contrainte_eval()

Value contrainte_eval	(	Pvecteur	c,
		Pvecteur	v
	)

Evaluate constraint c according to values in v and return the constant obtained.

The constraint may be an equality or an inequality.

If c is an equality, the value return must be zero or the point does not belong to the hyperplane defined by c.

If c is an inequality, the value returned is negative if v belongs to the half-space defined by c. If it is zero, the point v belongs to the constraint, i.e. is on the boundary of any constraint system containing c, i.e. to the hyperplane defined by c. If the value returned is stricly positive, v does not belong to the half-space defined by c.

Note: this function is not a predicate but it is used by the next function, which is a predicate.

Definition at line 331 of file predicats.c.

{
  Value k = VALUE_ZERO;
  Pvecteur cc = VECTEUR_NUL;
 
  for(cc=c; !VECTEUR_NUL_P(cc); cc = vecteur_succ(cc)) {
    Variable var = vecteur_var(cc);
    Value coef = vecteur_val(cc);
    if(var==TCST) {
      value_addto(k, coef);
    }
    else {
      Value val = vect_coeff(var, v);
      value_addto(k, value_direct_multiply(coef, val));
    }
  }
 
  return k;
}

References TCST, value_addto, value_direct_multiply, VALUE_ZERO, vect_coeff(), VECTEUR_NUL, VECTEUR_NUL_P, vecteur_succ, vecteur_val, and vecteur_var.

Referenced by contrainte_eval_p(), and sc_internal_p().

Here is the call graph for this function:

Here is the caller graph for this function:

contrainte_eval_p()

bool contrainte_eval_p	(	Pvecteur	c,
		Pvecteur	v,
		bool	is_equality_p
	)

Evaluate constraint c according to values in v and return true if the constraint is met.

The constraint may be an equality or an inequality depending on is_equality_p

Parameters

is_equality_p

s_equality_p

Definition at line 354 of file predicats.c.

{
  Value k = VALUE_ZERO;
  bool is_met_p = true;
 
  k = contrainte_eval(c, v);
 
  if(is_equality_p)
    is_met_p = value_zero_p(k);
  else
    is_met_p = value_negz_p(k);
 
  return is_met_p;
}

References contrainte_eval(), value_negz_p, VALUE_ZERO, and value_zero_p.

Referenced by equality_eval_p(), and inequality_eval_p().

Here is the call graph for this function:

Here is the caller graph for this function:

contrainte_oppos()

bool contrainte_oppos	(	Pcontrainte	ineg1,
		Pcontrainte	ineg2
	)

bool contrainte_oppos(Pcontrainte ineg1, Pcontrainte ineg2): indique si 2 inegalites forment une egalite ou si deux egalites sont equivalentes.

return(ineg1 == -ineg2);

Parameters

ineg1	neg1
ineg2	neg2

Definition at line 258 of file predicats.c.

{
    return(vect_oppos(ineg1->vecteur,ineg2->vecteur));
}

References vect_oppos().

Here is the call graph for this function:

contrainte_parallele()

bool contrainte_parallele	(	Pcontrainte	c1,
		Pcontrainte	c2,
		Value *	pa1,
		Value *	pa2
	)

Les deux contraintes c1 et c2 sont paralleles s'il existe deux coefficients a1 et a2 tels que a1 c1 + a2 c2 est reduit un terme constant K.

On cherche une composante quelconque relative a une variable

Parameters

c1	1
c2	2
pa1	a1
pa2	a2

Definition at line 145 of file predicats.c.

{
  bool parallel_p = false;
  register bool 
    undef1 = CONTRAINTE_UNDEFINED_P(c1),
    undef2 = CONTRAINTE_UNDEFINED_P(c2);
 
  if (undef1 || undef2) 
    parallel_p = (undef1 && undef2);
  else {
    /* On cherche une composante quelconque relative a une variable */
    Pvecteur v1 = contrainte_vecteur(c1);
    Pvecteur v2 = contrainte_vecteur(c2);
    if(vect_constant_p(v1))
      parallel_p = vect_constant_p(v2);
    else if(vect_constant_p(v2))
      parallel_p = false;
    else {
      Pvecteur v;
      for(v=v1; !VECTEUR_NUL_P(v); v = vecteur_succ(v)) {
        if(vecteur_var(v)!=TCST)
          break;
      }
      Variable var = vecteur_var(v);
      *pa1 = vect_coeff(var, v1);
      *pa2 = -vect_coeff(var, v2);
      Pvecteur nv1 = vect_multiply(vect_copy(v1), *pa2);
      Pvecteur nv2 = vect_multiply(vect_copy(v2), *pa1);
      Pvecteur nv = vect_add(nv1, nv2);
      if(vect_size(nv)==0 || (vect_size(nv)==1 && vecteur_var(nv)==TCST))
        parallel_p = true;
      vect_rm(nv1), vect_rm(nv2), vect_rm(nv);
    }
  }
  return parallel_p;
}

References CONTRAINTE_UNDEFINED_P, contrainte_vecteur, TCST, vect_add(), vect_coeff(), vect_constant_p(), vect_copy(), vect_multiply(), vect_rm(), vect_size(), VECTEUR_NUL_P, vecteur_succ, and vecteur_var.

Referenced by sc_safe_elim_db_constraints().

Here is the call graph for this function:

Here is the caller graph for this function:

contrainte_verifiee()

bool contrainte_verifiee	(	Pcontrainte	ineg,
		bool	eq_p
	)

bool contrainte_verifiee(Pcontrainte ineg, bool eq_p): test de faisabilite d'inegalite (eq_p == false) ou d'egalite triviale

Le test est different pour les egalites.

Modifications:

• test de l'absence d'un successeur dans vecteur (ajout d'un test succ == NULL)
• changement de cote du terme constant (FI, 08/12/89)
• ajout d'un assert pour pallier partiellement le bug 1 (FI, 08/12/89)
• utilisation de la macro CONTRAINTE_NULLE_P() (FI, 08/12/89) Bugs:
• si on passe une inegalite non constante en argument, le resultat depend du premier terme du vecteur; il faudrait pouvoir retourner la valeur bottom pour les inegalites non constantes;
• le nom devrait etre inegalite_verifiee()

l'inegalite 0 <= 0 est representee par un vecteur nul

l'inegalite 0 <= K est representee par un vecteur a un element

Parameters

ineg	neg
eq_p	q_p

Definition at line 234 of file predicats.c.

{
    Value v;
    assert(contrainte_constante_p(ineg));
 
    /* l'inegalite 0 <= 0 est representee par un vecteur nul */
    if (CONTRAINTE_NULLE_P(ineg))
        return(true);
 
    /* l'inegalite 0 <= K est representee par un vecteur a un element */
    v = val_of(ineg->vecteur);
 
    return (!eq_p && value_negz_p(v) && ineg->vecteur->succ==NULL)
        || ( eq_p && value_zero_p(v) && ineg->vecteur->succ==NULL);
}

References assert, contrainte_constante_p(), CONTRAINTE_NULLE_P, val_of, value_negz_p, and value_zero_p.

Referenced by combiner_ofl_with_test(), contrainte_subst_ofl_ctrl(), and sc_strong_normalize_and_check_feasibility().

Here is the call graph for this function:

Here is the caller graph for this function:

egalite_equal()

bool egalite_equal	(	Pcontrainte	eg1,
		Pcontrainte	eg2
	)

bool egalite_equal(Pcontrainte eg1, Pcontrainte eg2): teste l'equivalence de deux egalites; leurs coefficients peuvent etre tous egaux ou tous opposes; pour obtenir une meilleure equivalence il faut commencer par reduire leurs coefficients par les PGCD

Soit eg1, sum a1i xi = b1, et eg2, sum a2i xi = b2. i i return a1i == a2i || a1i == -a2i; i i

Note: 2x=2 est different de x=1

Parameters

eg1	g1
eg2	g2

Definition at line 98 of file predicats.c.

{
    bool result;
 
    if(CONTRAINTE_UNDEFINED_P(eg1) && CONTRAINTE_UNDEFINED_P(eg2))
        result = true;
    else if(CONTRAINTE_UNDEFINED_P(eg1) || CONTRAINTE_UNDEFINED_P(eg2))
        result = false;
    else
        result = vect_equal(eg1->vecteur,eg2->vecteur) ||
            vect_oppos(eg1->vecteur,eg2->vecteur);
 
    return(result);
}

References CONTRAINTE_UNDEFINED_P, vect_equal(), vect_oppos(), and Scontrainte::vecteur.

Referenced by extract_common_constraints(), free_guards(), sc_elim_db_constraints(), sc_elim_double_constraints(), sc_kill_db_eg(), sc_safe_elim_db_constraints(), and sc_safe_kill_db_eg().

Here is the call graph for this function:

Here is the caller graph for this function:

eq_smg()

bool eq_smg	(	Pcontrainte	c1,
		Pcontrainte	c2
	)

package contrainte - tests sur des contraintes

predicats.c

INTLIBRARY bool eq_smg(Pcontrainte c1, Pcontrainte c2): comparaison des coefficients de deux contraintes pour savoir si elles ont le meme membre gauche.

Note: this works for inequalities. Similar equations may differ by a factor of -1.

Parameters

c1	1
c2	2

Definition at line 52 of file predicats.c.

{
    bool result;
 
    if(c1==NULL && c2==NULL)
        result = true;
    else if(c1==NULL || c2==NULL)
        result = false;
    else
        result = vect_equal_except(c1->vecteur,c2->vecteur,TCST);
 
    return result;
}

References TCST, and vect_equal_except().

Referenced by sc_check_inequality_redundancy(), sc_elim_double_constraints(), sc_elim_simple_redund_with_eq(), and sc_elim_simple_redund_with_ineq().

Here is the call graph for this function:

Here is the caller graph for this function:

equality_eval_p()

bool equality_eval_p	(	Pvecteur	c,
		Pvecteur	v
	)

Definition at line 369 of file predicats.c.

{
  return contrainte_eval_p(c, v, true);
}

References contrainte_eval_p().

Referenced by sc_belongs_p(), and sc_internal_p().

Here is the call graph for this function:

Here is the caller graph for this function:

inequalities_opposite_p()

bool inequalities_opposite_p	(	Pcontrainte	c1,
		Pcontrainte	c2
	)

bool inequalities_opposite_p(Pcontrainte c1, Pcontrainte c2): True if the non-constant part of c1 is the opposite of the non-constant part of c2.

Parameters

c1	1
c2	2

Definition at line 71 of file predicats.c.

{
    bool result;
 
    if(c1==NULL && c2==NULL)
        result = true;
    else if(c1==NULL || c2==NULL)
        result = false;
    else
        result = vect_opposite_except(c1->vecteur,c2->vecteur,TCST);
 
    return result;
}

References TCST, and vect_opposite_except().

Referenced by sc_check_inequality_redundancy().

Here is the call graph for this function:

Here is the caller graph for this function:

inequality_eval_p()

bool inequality_eval_p	(	Pvecteur	c,
		Pvecteur	v
	)

Definition at line 374 of file predicats.c.

{
  return contrainte_eval_p(c, v, false);
}

References contrainte_eval_p().

Referenced by sc_belongs_p().

Here is the call graph for this function:

Here is the caller graph for this function:

vect_constant_p()

bool vect_constant_p

(

Pvecteur

v

)

bool vect_constant_p(Pvecteur v): v contains only a constant term, may be zero

Bugs:

• this function should not be in contrainte.dir; it should be moved into vecteur.dir with TCST...
• should assert !VECTEUR_UNDEFINED_P(v)

Definition at line 211 of file predicats.c.

{
    return(VECTEUR_NUL_P(v) || (v->var == TCST && v->succ == NULL));
}

References TCST, and VECTEUR_NUL_P.

Referenced by add_declaration_list_information(), add_reference_information(), contrainte_constante_p(), contrainte_parallele(), convert_bound_expression(), dims_array_init(), expression_and_precondition_to_integer_interval(), expression_equal_in_context_p(), expression_less_than_in_context(), expression_to_int(), IsExprConst(), loop_index_domaine_to_contrainte(), loop_regions_normalize(), region_projection_along_index_safe_p(), sc_elim_double_constraints(), signed_integer_constant_expression_value(), text_equivalence_class(), and trivial_expression_p().

Here is the caller graph for this function: