testdep_util.c File Reference

#include "local.h"
#include "prettyprint.h"

Include dependency graph for testdep_util.c:

Go to the source code of this file.

Macros
#define	ILCMAX   100000
	Management of loop counters. More...

Functions
entity	MakeDiVar (int l)
	This function creates di variables. More...
entity	GetDiVar (int l)
	This functions looks up a di variable of nesting level l in table DiVars. More...
entity	MakeLiVar (int l)
	This function creates li variables(thee ith loop index variable). More...
entity	GetLiVar (int l)
entity	MakeDsiVar (int l)
	This function creates dsi variables. More...
entity	GetDsiVar (int l)
int	DiVarLevel (entity e)
	this function returns the nesting level of a given di variable e. More...
void	sc_add_di (int l, entity e, Psysteme s, int li)
void	sc_add_dsi (int l, entity e, Psysteme s)
int	sc_proj_on_di (int cl, Psysteme s)
Pbase	MakeDibaseinorder (int n)
	Pbase MakeDibaseinorder(int n) make a base of D#1 ... More...
int	FindMaximumCommonLevel (cons *n1, cons *n2)
void	ResetLoopCounter ()
entity	MakeLoopCounter ()
	Create a new loop counter variable. More...
int	dep_type (action ac1, action ac2)
	int dep_type(action ac1,action ac2) This function test the type of the dependence. More...
int	sc_proj_optim_on_di_ofl (int cl, Psysteme *psc)
	int sc_proj_optim_on_di_ofl(cl, sc) More...
bool	sc_faisabilite_optim (Psysteme sc)
	bool sc_faisabilite_optim (Psysteme sc) : More...
static bool	combiner_ofl_with_test (Psysteme sc, Variable v)
	bool combiner_ofl_with_test(Psysteme sc, Variable v): More...
Psysteme	sc_projection_optim_along_vecteur_ofl (Psysteme sc, Pvecteur pv)
	Psysteme sc_projection_optim_along_vecteur_ofl(Psysteme sc, Pvecteur pv) More...
bool	sc_minmax_of_variable_optim (Psysteme volatile ps, Variable var, Value *pmin, Value *pmax)
	void sc_minmax_of_variable_optim(Psysteme ps, Variable var, Value *pmin, *pmax): examine un systeme pour trouver le minimum et le maximum d'une variable apparaissant dans ce systeme par projection a la Fourier-Motzkin. More...
Psysteme	sc_invers (Psysteme ps)
	Psysteme sc_invers(Psysteme ps): calcul un systeme des contraintes qui est l'invers du systeme initial. More...
void	vect_chg_var_sign (Pvecteur *ppv, Variable var)
	void vect_chg_var_sign(Pvecteur *ppv, Variable var) changement de signe de la coordonnee var du vecteur *ppv More...

Variables
entity	DiVars [MAXDEPTH]
	here is a collection of function intended to create and manipulate "di" variables and test of dependence. More...
entity	LiVars [MAXDEPTH]
entity	DsiVars [MAXSV]
static int	ilc = ILCMAX

Macro Definition Documentation

ILCMAX

#define ILCMAX   100000

Management of loop counters.

Definition at line 325 of file testdep_util.c.

Function Documentation

combiner_ofl_with_test()

static bool combiner_ofl_with_test ( Psysteme  sc, Variable  v  )

static

bool combiner_ofl_with_test(Psysteme sc, Variable v):

the copy of combiner() adding the test of suffisants conditions of integer combination.

It returns true if exact

apres les combinaisons eliminer les elements devenus inutiles

mise a jour du systeme

Definition at line 533 of file testdep_util.c.

{
  Psysteme sc1;
  Pcontrainte pos, neg, nul;
  Pcontrainte pc, pcp, pcn;
  Value c;
  int nnul, np, nn, i;
 
  pc = sc->inegalites;
 
  if(pc == NULL) {
    FMComp[0]++;
    return (true);
  }
 
  sc1 = sc_dup(sc);
  pos = neg = nul = NULL;
  nnul = 0;
  while(pc != NULL) {
    Pcontrainte pcs = pc->succ;
 
    if(value_pos_p(c = vect_coeff(v,pc->vecteur))) {
      pc->succ = pos;
      pos = pc;
    }
    else if(value_neg_p(c)) {
      pc->succ = neg;
      neg = pc;
    }
    else {
      pc->succ = nul;
      nul = pc;
      nnul += 1;
    }
 
    pc = pcs;
  }
  sc->inegalites = NULL;
  sc->nb_ineq = 0;
 
  np = nb_elems_list(pos);
  nn = nb_elems_list(neg);
 
  if((i = np * nn) <= 16)
    FMComp[i]++;
  else
    FMComp[17]++;
 
  for (pcp = pos; pcp != NULL; pcp = pcp->succ) {
    for (pcn = neg; pcn != NULL; pcn = pcn->succ) {
      bool int_comb_p = true;
      Pcontrainte pcnew =
          sc_integer_inequalities_combination_ofl_ctrl(sc1,
                                                       pcp,
                                                       pcn,
                                                       v,
                                                       &int_comb_p,
                                                       FWD_OFL_CTRL);
 
      if(contrainte_constante_p(pcnew)) {
        if(contrainte_verifiee(pcnew, false)) {
          contrainte_free(pcnew);
        } else {
          contraintes_free(pos);
          contraintes_free(neg);
          contraintes_free(nul);
          contraintes_free(pcnew);
          sc_rm(sc1);
          return (false);
        }
      } else {
        pcnew->succ = nul;
        nul = pcnew;
        nnul += 1;
        if(!int_comb_p) {
          if(is_test_exact)
            is_test_exact = false;
          if(is_test_inexact_fm == false)
            is_test_inexact_fm = true;
        }
      }
    }
  }
 
  /* apres les combinaisons eliminer les elements devenus inutiles */
  contraintes_free(pos);
  contraintes_free(neg);
 
  /* mise a jour du systeme */
  sc->inegalites = nul;
  sc->nb_ineq = nnul;
  sc_rm(sc1);
  return (true);
}

References contrainte_constante_p(), contrainte_free(), contrainte_verifiee(), contraintes_free(), FMComp, FWD_OFL_CTRL, Ssysteme::inegalites, is_test_exact, is_test_inexact_fm, nb_elems_list(), Ssysteme::nb_ineq, sc_dup(), sc_rm(), Scontrainte::succ, value_neg_p, value_pos_p, vect_coeff(), and Scontrainte::vecteur.

Referenced by sc_projection_optim_along_vecteur_ofl().

Here is the call graph for this function:

Here is the caller graph for this function:

dep_type()

int dep_type	(	action	ac1,
		action	ac2
	)

int dep_type(action ac1,action ac2) This function test the type of the dependence.

ac1, ac2 are the action of two references.The representations of the result are as follows. 0 -— def-use dependence 1 -— use-def dependence 2 -— def-def dependence 3 -— use-use dependence (added in 20/01/92) FI->YY: we also have use-use dependence (also called input dependence); there is no reason to abort here; input dependences should just be ignored for parallelization, but not for tiling or cache optimization

to please gcc

Parameters

ac1	c1
ac2	c2

Definition at line 378 of file testdep_util.c.

                   {
  if(action_write_p(ac1) && action_read_p(ac2))
    return (0);
  else if(action_read_p(ac1) && action_write_p(ac2))
    return (1);
  else if(action_write_p(ac1) && action_write_p(ac2))
    return (2);
  else if(action_read_p(ac1) && action_read_p(ac2))
    return (3);
  else
    pips_internal_error("A undefined chain ---chains fault");
 
  /* to please gcc */
  return -1;
}

References action_read_p, action_write_p, and pips_internal_error.

Referenced by insert_impact_description_as_comment(), and TestCoupleOfReferences().

Here is the caller graph for this function:

DiVarLevel()

int DiVarLevel

(

entity

e

)

this function returns the nesting level of a given di variable e.

Definition at line 185 of file testdep_util.c.

            {
  int i;
 
  for (i = 0; i < MAXDEPTH; i++)
    if(e == DiVars[i])
      return (i + 1);
 
  return (0);
}

References DiVars, and MAXDEPTH.

Referenced by sc_proj_on_di(), sc_proj_optim_on_di_ofl(), and TestDependence().

Here is the caller graph for this function:

FindMaximumCommonLevel()

int FindMaximumCommonLevel	(	cons *	n1,
		cons *	n2
	)

Parameters

n1	1
n2	2

Definition at line 307 of file testdep_util.c.

                 {
  int cl = 0;
 
  while(n1 != NIL && n2 != NIL) {
    if(LOOP(CAR(n1)) != LOOP(CAR(n2)))
      break;
    n1 = CDR(n1);
    n2 = CDR(n2);
    cl += 1;
  }
 
  return (cl);
}

References CAR, CDR, LOOP, and NIL.

Referenced by prettyprint_dependence_graph_view(), prettyprint_dot_dependence_graph(), search_parallel_loops(), TestCoupleOfReferences(), and TestDependence().

Here is the caller graph for this function:

GetDiVar()

entity GetDiVar

(

int

l

)

This functions looks up a di variable of nesting level l in table DiVars.

di variables are created if they do not exist.

Definition at line 79 of file testdep_util.c.

         {
  entity e;
 
  if(l < 1 || l > MAXDEPTH)
    user_error("parallelize", "too many nested loops\n");
 
  if((e = DiVars[l - 1]) == (entity)0) {
    int i;
    for (i = 0; i < MAXDEPTH; i++)
      DiVars[i] = MakeDiVar(i + 1);
 
    e = DiVars[l - 1];
  }
 
  return (e);
}

References DiVars, MakeDiVar(), MAXDEPTH, and user_error.

Referenced by dependence_system_add_lci_and_di(), gcd_and_constant_dependence_test(), MakeDibaseinorder(), sc_add_di(), TestDiCnst(), and TestDiVariables().

Here is the call graph for this function:

Here is the caller graph for this function:

GetDsiVar()

entity GetDsiVar

(

int

l

)

Definition at line 164 of file testdep_util.c.

         {
  entity e;
 
  if(l < 1 || l > MAXSV)
    user_error("parallelize", "too many scalar variables\n");
 
  if((e = DsiVars[l - 1]) == (entity)0) {
    int i;
    for (i = 0; i < MAXSV; i++)
      DsiVars[i] = MakeDsiVar(i + 1);
 
    e = DsiVars[l - 1];
  }
 
  return (e);
}

References DsiVars, MakeDsiVar(), MAXSV, and user_error.

Referenced by gcd_and_constant_dependence_test(), and sc_add_dsi().

Here is the call graph for this function:

Here is the caller graph for this function:

GetLiVar()

entity GetLiVar

(

int

l

)

Definition at line 121 of file testdep_util.c.

         {
  entity e;
 
  if(l < 1 || l > MAXDEPTH)
    user_error("parallelize", "too many nested loops\n");
 
  if((e = LiVars[l - 1]) == (entity)0) {
    int i;
    for (i = 0; i < MAXDEPTH; i++)
      LiVars[i] = MakeLiVar(i + 1);
 
    e = LiVars[l - 1];
  }
 
  return (e);
}

References LiVars, MakeLiVar(), MAXDEPTH, and user_error.

Referenced by build_and_test_dependence_context(), dependence_system_add_lci_and_di(), and gcd_and_constant_dependence_test().

Here is the call graph for this function:

Here is the caller graph for this function:

MakeDibaseinorder()

Pbase MakeDibaseinorder

(

int

n

)

Pbase MakeDibaseinorder(int n) make a base of D#1 ...

D::n in order of D#1-> D#2, ...-> D::n.

Definition at line 296 of file testdep_util.c.

         {
  Pbase Dibase = BASE_NULLE;
  int i;
 
  for (i = 1; i <= n; i++) {
    Dibase = vect_add_variable(Dibase, (Variable)GetDiVar(n - i + 1));
  }
  return (Dibase);
}

References BASE_NULLE, GetDiVar(), and vect_add_variable().

Referenced by TestDependence().

Here is the call graph for this function:

Here is the caller graph for this function:

MakeDiVar()

entity MakeDiVar

(

int

l

)

This function creates di variables.

There are MAXDEPTH di variables which means that programs with more than MAXDEPTH nested loops cannot be parallelized by pips.

Parameters

l	is the nesting level of the variable to create

Create a variable of this format: "d#X"

Definition at line 63 of file testdep_util.c.

                        {
  entity e;
  string s;
  /* Create a variable of this format: "d#X" */
  asprintf(&s, "%s%sd#%d", DI_VAR_MODULE_NAME, MODULE_SEP_STRING, l);
 
  if((e = gen_find_tabulated(s, entity_domain)) == entity_undefined)
    e = make_entity(s, type_undefined, storage_undefined, value_undefined);
  else
    free(s);
 
  return (e);
}

References asprintf, DI_VAR_MODULE_NAME, entity_domain, entity_undefined, free(), gen_find_tabulated(), make_entity, MODULE_SEP_STRING, storage_undefined, type_undefined, and value_undefined.

Referenced by GetDiVar().

Here is the call graph for this function:

Here is the caller graph for this function:

MakeDsiVar()

entity MakeDsiVar

(

int

l

)

This function creates dsi variables.

There are MAXSV dsi variables which means that programs with more than MAXSV scalar variables cannot be parallelized by PIPS.

Parameters

l	means to create Dsi[l] variable

Create a variable of this format: "ds#XXXX"

Definition at line 146 of file testdep_util.c.

                         {
  entity e;
  string s;
  /* Create a variable of this format: "ds#XXXX" */
  asprintf(&s, "%s%sds#%.4d", DI_VAR_MODULE_NAME, MODULE_SEP_STRING, l);
 
  if((e = gen_find_tabulated(s, entity_domain)) == entity_undefined)
    e = make_entity(s, type_undefined, storage_undefined, value_undefined);
  else
    free(s);
 
  return (e);
}

References asprintf, DI_VAR_MODULE_NAME, entity_domain, entity_undefined, free(), gen_find_tabulated(), make_entity, MODULE_SEP_STRING, storage_undefined, type_undefined, and value_undefined.

Referenced by GetDsiVar().

Here is the call graph for this function:

Here is the caller graph for this function:

MakeLiVar()

entity MakeLiVar

(

int

l

)

This function creates li variables(thee ith loop index variable).

There are MAXDEPTH li variables which means that programs with more than MAXDEPTH nested loops cannot be parallelized by pips.

Parameters

l	is the nesting level of the variable to create

Create a variable of this format: "l#X"

Definition at line 103 of file testdep_util.c.

                        {
  entity e;
  string s;
  /* Create a variable of this format: "l#X" */
  asprintf(&s, "%s%sl#%d", DI_VAR_MODULE_NAME, MODULE_SEP_STRING, l);
 
  if((e = gen_find_tabulated(s, entity_domain)) == entity_undefined)
    e = make_entity(s, type_undefined, storage_undefined, value_undefined);
  else
    free(s);
 
  return (e);
}

References asprintf, DI_VAR_MODULE_NAME, entity_domain, entity_undefined, free(), gen_find_tabulated(), make_entity, MODULE_SEP_STRING, storage_undefined, type_undefined, and value_undefined.

Referenced by GetLiVar().

Here is the call graph for this function:

Here is the caller graph for this function:

MakeLoopCounter()

entity MakeLoopCounter

(

void

)

Create a new loop counter variable.

Create a variable of this format: "lc#XXXXXX"

Try a new free one:

Definition at line 334 of file testdep_util.c.

                         {
  entity e;
  string s;
  //static char lcn[] = "lc#XXXXXX";
 
  while(1) {
    /* Create a variable of this format: "lc#XXXXXX" */
    asprintf(&s,
             "%s%slc#%06d",
             LOOP_COUNTER_MODULE_NAME,
             MODULE_SEP_STRING,
             ilc);
 
    if((e = gen_find_tabulated(s, entity_domain)) == entity_undefined) {
      pips_debug(8, "loop counter is %s\n", s);
      return make_entity(strdup(s),
                         type_undefined,
                         storage_undefined,
                         value_undefined);
    } else
      free(s);
 
    /* Try a new free one: */
    if((ilc += 1) == ILCMAX)
      break;
  }
 
  pips_internal_error("too many loop counters");
  return (entity_undefined);
}

References asprintf, entity_domain, entity_undefined, free(), gen_find_tabulated(), ilc, ILCMAX, LOOP_COUNTER_MODULE_NAME, make_entity, MODULE_SEP_STRING, pips_debug, pips_internal_error, storage_undefined, strdup(), type_undefined, and value_undefined.

Referenced by dependence_system_add_lci_and_di().

Here is the call graph for this function:

Here is the caller graph for this function:

ResetLoopCounter()

void ResetLoopCounter

(

void

)

Definition at line 329 of file testdep_util.c.

                        {
  ilc = 0;
}

References ilc.

Referenced by rice_dependence_graph().

Here is the caller graph for this function:

sc_add_di()

void sc_add_di	(	int	l,
		entity	e,
		Psysteme	s,
		int	li
	)

Parameters

li

i

Definition at line 209 of file testdep_util.c.

                                    {
  Variable v = (Variable)GetDiVar(l);
  Value vli = int_to_value(li);
  Pcontrainte pc;
 
  for (pc = s->egalites; pc != NULL; pc = pc->succ) {
    Value ve = vect_coeff((Variable)e, pc->vecteur);
    value_product(ve, vli);
    vect_add_elem(&(pc->vecteur), v, ve);
  }
 
  for (pc = s->inegalites; pc != NULL; pc = pc->succ) {
    Value ve = vect_coeff((Variable)e, pc->vecteur);
    value_product(ve, vli);
    vect_add_elem(&(pc->vecteur), v, ve);
  }
}

References Ssysteme::egalites, GetDiVar(), Ssysteme::inegalites, int_to_value, Scontrainte::succ, value_product, vect_add_elem(), vect_coeff(), and Scontrainte::vecteur.

Referenced by build_and_test_dependence_context().

Here is the call graph for this function:

Here is the caller graph for this function:

sc_add_dsi()

void sc_add_dsi	(	int	l,
		entity	e,
		Psysteme	s
	)

Definition at line 238 of file testdep_util.c.

                             {
  Variable v = (Variable)GetDsiVar(l);
  Pcontrainte pc;
  for (pc = s->egalites; pc != NULL; pc = pc->succ) {
    vect_add_elem(&(pc->vecteur), v, vect_coeff((Variable)e, pc->vecteur));
  }
 
  for (pc = s->inegalites; pc != NULL; pc = pc->succ) {
    vect_add_elem(&(pc->vecteur), v, vect_coeff((Variable)e, pc->vecteur));
  }
}

References Ssysteme::egalites, GetDsiVar(), Ssysteme::inegalites, Scontrainte::succ, vect_add_elem(), vect_coeff(), and Scontrainte::vecteur.

Referenced by build_and_test_dependence_context().

Here is the call graph for this function:

Here is the caller graph for this function:

sc_faisabilite_optim()

bool sc_faisabilite_optim

(

Psysteme

sc

)

bool sc_faisabilite_optim (Psysteme sc) :

Test system sc feasibility by successive projections along all variables in its basis.

carry out the projection with function sc_projection_optim_along_vecteur().

sc_normalize() is called here before the projection, which means that sc may be deallocated

result :

boolean : true if system is faisable false else

Modification:

• call to sc_rm() added when sc_projection_optim_along_vecteur_ofl() returns sc_empty; necessary to have a consistent interface: when FALSE is returned, sc always has been freed.

Automatic variables read in a CATCH block need to be declared volatile as specified by the documentation

Parameters

sc

c

Definition at line 484 of file testdep_util.c.

               {
  debug(6, "sc_faisabilite_optim", "begin\n");
  sc = sc_normalize(sc);
  if(!sc_empty_p(sc)) {
    /* Automatic variables read in a CATCH block need to be declared volatile as
     * specified by the documentation*/
    Psysteme volatile sc1 = sc_dup(sc);
    is_test_Di = false;
 
    CATCH(overflow_error) {
      pips_debug(7, "overflow error, returning TRUE. \n");
      sc_rm(sc1);
      debug(6, "sc_faisabilite_optim", "end\n");
      return (true);
 
    } TRY {
      Pbase base_sc1 = base_dup(sc1->base);
      sc1 = sc_projection_optim_along_vecteur_ofl(sc1, base_sc1);
      base_rm(base_sc1);
      if(sc_empty_p(sc1)) {
        debug(7, "sc_faisabilite_optim", "system not feasible\n");
        debug(6, "sc_faisabilite_optim", "end\n");
        sc_rm(sc);
        UNCATCH(overflow_error);
        return (false);
      } else {
        sc_rm(sc1);
        debug(7, "sc_faisabilite_optim", "system feasible\n");
        debug(6, "sc_faisabilite_optim", "end\n");
        UNCATCH(overflow_error);
        return (true);
      }
    }
  } else {
    debug(7, "sc_faisabilite_optim", "normalized system not feasible\n");
    debug(6, "sc_faisabilite_optim", "end\n");
    sc_rm(sc);
    return (false);
  }
}

References Ssysteme::base, base_dup(), base_rm, CATCH, debug(), is_test_Di, overflow_error, pips_debug, sc_dup(), sc_empty_p(), sc_normalize(), sc_projection_optim_along_vecteur_ofl(), sc_rm(), TRY, and UNCATCH.

Referenced by TestDependence().

Here is the call graph for this function:

Here is the caller graph for this function:

sc_invers()

Psysteme sc_invers

(

Psysteme

ps

)

Psysteme sc_invers(Psysteme ps): calcul un systeme des contraintes qui est l'invers du systeme initial.

pour chaque element b dans le base initial, remplace b par -b dans le systeme initial.

Parameters

ps

s

Definition at line 1060 of file testdep_util.c.

               {
  Pbase b;
  Pcontrainte eq;
  Variable v;
 
  for (b = ps->base; !VECTEUR_NUL_P(b); b = b->succ) {
    v = vecteur_var(b);
    for (eq = ps->egalites; eq != NULL; eq = eq->succ)
      vect_chg_var_sign(&eq->vecteur, v);
    
    for (eq = ps->inegalites; eq != NULL; eq = eq->succ)
      vect_chg_var_sign(&eq->vecteur, v);
  }
  return (ps);
}

References eq, Scontrainte::succ, Svecteur::succ, vect_chg_var_sign(), Scontrainte::vecteur, VECTEUR_NUL_P, and vecteur_var.

Referenced by TestDependence().

Here is the call graph for this function:

Here is the caller graph for this function:

sc_minmax_of_variable_optim()

bool sc_minmax_of_variable_optim	(	Psysteme volatile	ps,
		Variable	var,
		Value *	pmin,
		Value *	pmax
	)

void sc_minmax_of_variable_optim(Psysteme ps, Variable var, Value *pmin, *pmax): examine un systeme pour trouver le minimum et le maximum d'une variable apparaissant dans ce systeme par projection a la Fourier-Motzkin.

la procedure retourne la valeur false si le systeme est infaisable et true sinon

le systeme ps est detruit.

projection sur toutes les variables sauf var

cette contrainte nous donne une borne max

cette contrainte nous donne une borne min

Parameters

ps	s
var	ar
pmin	min
pmax	max

Definition at line 975 of file testdep_util.c.

                                                        {
  Value val;
  Pcontrainte pc;
  Pbase b;
  Pvecteur pv = NULL;
 
  *pmax = VALUE_MAX;
  *pmin = VALUE_MIN;
 
  if(sc_value_of_variable(ps, var, &val) == true) {
    *pmin = val;
    *pmax = val;
    return true;
  }
 
  /* projection sur toutes les variables sauf var */
  for (b = ps->base; !VECTEUR_NUL_P(b); b = b->succ) {
    Variable v = vecteur_var(b);
    if(v != var) {
      vect_add_elem(&pv, v, 1);
    }
  }
 
  CATCH(overflow_error) {
    debug(6,
          "sc_minmax_of_variable_optim",
          " overflow error, returning INT_MAX and INT_MIN. \n");
    *pmax = INT_MAX;
    *pmin = INT_MIN;
  } TRY {
 
    ps = sc_projection_optim_along_vecteur_ofl(ps, pv);
    if(sc_empty_p(ps)) {
      sc_rm(ps);
      UNCATCH(overflow_error);
      return false;
    }
    if(sc_empty_p(ps = sc_normalize(ps))) {
      sc_rm(ps);
      UNCATCH(overflow_error);
      return false;
    }
 
    if(sc_value_of_variable(ps, var, &val) == true) {
      *pmin = val;
      *pmax = val;
      UNCATCH(overflow_error);
      return true;
    }
 
    for (pc = ps->inegalites; pc != NULL; pc = pc->succ) {
      Value cv = vect_coeff(var, pc->vecteur);
      Value cc = value_uminus(vect_coeff(TCST, pc->vecteur));
 
      if(value_pos_p(cv)) {
        /* cette contrainte nous donne une borne max */
        Value bs = value_pdiv(cc,cv);
        if(value_lt(bs,*pmax))
          *pmax = bs;
      } else if(value_neg_p(cv)) {
        /* cette contrainte nous donne une borne min */
        Value bi = value_pdiv(cc,cv);
        if(value_gt(bi,*pmin))
          *pmin = bi;
      }
    }
 
    UNCATCH(overflow_error);
    vect_rm(pv);
  }
 
  if(value_lt(*pmax,*pmin))
    return false;
 
  sc_rm(ps);
 
  return true;
}

References CATCH, debug(), overflow_error, sc_empty_p(), sc_normalize(), sc_projection_optim_along_vecteur_ofl(), sc_rm(), sc_value_of_variable(), Scontrainte::succ, Svecteur::succ, TCST, TRY, UNCATCH, value_gt, value_lt, VALUE_MAX, VALUE_MIN, value_neg_p, value_pdiv, value_pos_p, value_uminus, vect_add_elem(), vect_coeff(), vect_rm(), Scontrainte::vecteur, VECTEUR_NUL_P, and vecteur_var.

Referenced by TestDiVariables().

Here is the call graph for this function:

Here is the caller graph for this function:

sc_proj_on_di()

int sc_proj_on_di	(	int	cl,
		Psysteme	s
	)

Parameters

cl

l

Definition at line 267 of file testdep_util.c.

                     {
  Pbase coord;
 
  for (coord = s->base; !VECTEUR_NUL_P(coord); coord = coord->succ) {
    Variable v = vecteur_var(coord);
    int l = DiVarLevel((entity)v);
    
    if(l <= 0 || l > cl) {
      debug(8,
            "ProjectOnDi",
            "projection sur %s\n",
            entity_local_name((entity)v));
      if(SC_EMPTY_P(s = sc_projection_pure(s, v))) {
        debug(8, "ProjectOnDi", "infaisable\n");
        return (false);
      }
      debug(8, "ProjectOnDi", "faisable\n");
    }
  }
 
  return (true);
}

References Ssysteme::base, debug(), DiVarLevel(), entity_local_name(), Svecteur::succ, VECTEUR_NUL_P, and vecteur_var.

Here is the call graph for this function:

sc_proj_optim_on_di_ofl()

int sc_proj_optim_on_di_ofl	(	int	cl,
		Psysteme *	psc
	)

int sc_proj_optim_on_di_ofl(cl, sc)

This function projects a system onto a set of di variables. This set is defined by cl, the common nesting level of the two array references being tested: only di variables whose nesting level is less than or equal to cl are kept in the projected system (i.e. outermost loops).

The projection is performed by first eliminating variables in the equations. Variables whose coefficients are 1 or -1 are considered first. (in such case it's integer elimination). Remaining inequalities are projected by Fourier-Motzkin elimination.

cl is the common nesting level. sc is the system to project. sc is modified but psc always points to a consistent Psysteme on return (i.e. it's up to the caller to free it). *psc on return is sc_empty() if *psc on entry turns out to be non-feasible. a long jump buffer must have been initialized to handle overflows The value returned is true if the system is feasible, false otherwise.

find the set of variables to be eliminated

find one

Parameters

cl	l
psc	sc

Definition at line 415 of file testdep_util.c.

{
  Pbase coord;
  Pvecteur pv = VECTEUR_NUL;
  Variable v;
  int l;
  int res;
 
  pips_debug(6, "begin\n");
 
  /* find the set of variables to be eliminated */
  for (coord = (*psc)->base; !VECTEUR_NUL_P(coord); coord = coord->succ) {
    v = vecteur_var(coord);
    l = DiVarLevel((entity)v);
    
    if(l <= 0 || l > cl) /* find one */
      vect_add_elem(&pv, v, 1);
  }
 
  ifdebug(6) {
    fprintf(stderr, "The list of variables to be eliminated is :\n");
    vect_debug(pv);
  }
  is_test_Di = true;
 
  pips_assert("Dependence system *psc is consistent before projection",
              sc_consistent_p(*psc));
 
  *psc = sc_projection_optim_along_vecteur_ofl(*psc, pv);
 
  pips_assert("Dependence system *psc is consistent after projection",
              sc_consistent_p(*psc));
 
  if(sc_empty_p(*psc))
    res = false;
  else
    res = true;
 
 
  vect_rm(pv);
 
 
  pips_assert("Dependence system *psc is consistent after empty test",
              sc_consistent_p(*psc));
  pips_debug(6, "end\n");
 
  return res;
}

References DiVarLevel(), fprintf(), ifdebug, is_test_Di, pips_assert, pips_debug, sc_consistent_p(), sc_empty_p(), sc_projection_optim_along_vecteur_ofl(), Svecteur::succ, vect_add_elem(), vect_debug(), vect_rm(), VECTEUR_NUL, VECTEUR_NUL_P, and vecteur_var.

Referenced by TestDependence().

Here is the call graph for this function:

Here is the caller graph for this function:

sc_projection_optim_along_vecteur_ofl()

Psysteme sc_projection_optim_along_vecteur_ofl	(	Psysteme	sc,
		Pvecteur	pv
	)

Psysteme sc_projection_optim_along_vecteur_ofl(Psysteme sc, Pvecteur pv)

This fonction returns the projected system resulting of the SUCCESSIVE projections of the system sc along the variables contained in vecteur pv. Variables are only more or less projected according to their order in pv.

The projection is done first by eliminating variables constrained by equations. The variables whose coefficients are 1 (or -1?) are considered first (in such case it is a valide integer elimination), then variables appearing in equations with non unit coefficient, and finally all left over variables in pv using Fourier-Motzkin elimination. At each step, the order in pv is used.

If the system sc is not faisable, SC_EMPTY is returned.

FI: this function could be moved to linear... but for the debugging stuff. Also, it could be broken into three parts. And the number of return statements should be reduced to one.

The elimination of variables using equations

First,carry out the integer elimination possible

coeff == 1, do this integer elimination for variable v with the others contrainte(equations and inequations

remove v from the list of variables to be projected pve

it's in head

carry out the non-exact elimination if necessary and possible using other equations

find a variable which appears in the equations, eliminate it

liminate v in the list of variables pve

it's in head

carry out the elimination using Fourier-Motzkin for the other variables

detection of non feasability of Psysteme sc

sc->inegalites = contrainte_sort(sc->inegalites, sc->base, BASE_NULLE,

true, false);

ifdebug(8) {

debug(8, "", "Sorted system :\n");

sc_syst_debug(sc);

}

Are we done? This used to be always true, but sc_normalize() may promote inequalities as equations. Since the projection steps may reveal some implicit equations, we are not sure here that all projections have been performed by the three steps (equations, equations, inequalities).

See for instance the test dependence in SAC/sgemm for such an example.

Update the base and the dimension of the constraint system sc

Clean up auxiliary data structures

Parameters

sc	c
pv	v

Definition at line 648 of file testdep_util.c.

{
  Pcontrainte eq;
  Pvecteur pv1, prv, pve;
  Variable v;
  Value coeff;
  int syst_size_init;
  Pbase base_sc = base_dup(sc->base);
  Pbase lb = BASE_NULLE;
 
  pips_assert("The input constraint system is consistent", sc_consistent_p(sc));
  ifdebug(7) {
    pips_debug(7, "All variables to project: ");
    vect_dump(pv);
  }
 
  pve = vect_dup(pv);
  Pvecteur pve_to_free = pve;
 
  do {
    /* The elimination of variables using  equations */
    if(pve != NULL && sc->nb_eq != 0) {
 
      /* First,carry out the integer elimination possible */
      pips_debug(7, "carry out the integer elimination by equation:\n");
 
      prv = NULL;
      pv1 = pve;
      while(!VECTEUR_NUL_P(pv1) && (sc->nb_eq != 0)) {
        v = pv1->var;
        eq = contrainte_var_min_coeff(sc->egalites, v, &coeff, false);
        if((eq == NULL) || value_notone_p(coeff)) {
          prv = pv1;
          pv1 = pv1->succ;
        } else {
          ifdebug(7) {
            fprintf(stderr, "eliminate %s by :", entity_local_name((entity)v));
            egalite_debug(eq);
          }
          /* coeff == 1, do this integer elimination for variable
           * v with the others contrainte(equations and inequations */
          sc = sc_variable_substitution_with_eq_ofl_ctrl(sc, eq, v, FWD_OFL_CTRL);
 
          if(sc_empty_p(sc)) {
            if(is_test_Di)
              NbrTestProjEqDi++;
            else
              NbrTestProjEq++;
            pips_debug(7, "projection infaisable\n");
            for (pv1 = pv; pv1 != NULL; pv1 = pv1->succ) {
              v = pv1->var;
              sc_base_remove_variable(sc, v);
            }
            base_rm(base_sc);
            vect_rm(pve_to_free);
 
            pips_debug(7, "Return 1: empty\n");
            return (sc);
          }
          sc = sc_normalize(sc);
 
          if(sc_empty_p(sc)) { // FI: another normalization step is going to occur here
            if(is_test_Di)
              NbrTestProjEqDi++;
            else
              NbrTestProjEq++;
            pips_debug(7, "normalisation infaisable\n");
 
            for (pv1 = pv; pv1 != NULL; pv1 = pv1->succ) {
              v = pv1->var;
              sc_base_remove_variable(sc, v);
            }
 
            vect_rm(pve_to_free);
 
            pips_debug(7, "Return 2: empty\n");
            return (sc);
 
          }
 
          // The removal is delayed till the end of the function. sc is
          // still consistent. However, too many variables might be left if an
          // intermediate return occurs
          // sc_base_remove_variable(sc, v);
        
          ifdebug(7) {
            fprintf(stderr, "projected normalised system is:\n");
            sc_syst_debug(sc);
          }
 
          /* remove v from the list of variables to be projected pve */
          if(prv == NULL) /* it's in head */
            pve = pv1 = pv1->succ;
          else {
            prv->succ = pv1->succ;
            free(pv1);
            pv1 = prv->succ;
          }
        }
      }
    }
 
    pips_assert("sc is consistent after the first use of equations",
                sc_consistent_p(sc));
    ifdebug(7) {
      pips_debug(7, "Variables left to project after the first step: ");
      vect_dump(pv);
    }
 
    /* carry out the non-exact elimination if necessary and possible
       using other equations */
    if(pve != NULL && sc->egalites != NULL) {
      pips_debug(7, "carry out the non integer elimination by equation:\n");
      pv1 = pve;
      prv = NULL;
      while((sc->egalites != 0) && (pv1 != NULL)) {
        v = pv1->var;
        eq = contrainte_var_min_coeff(sc->egalites, v, &coeff, true);
        if(eq == NULL && pv1 != NULL) {
          prv = pv1;
          pv1 = pv1->succ;
        } else {
          if(eq != NULL) {
            /* find a variable which appears in the equations, eliminate it*/
            ifdebug(7) {
              fprintf(stderr, "eliminate %s by :", entity_local_name((entity)v));
              egalite_debug(eq);
            }
            if(is_test_inexact_eq == false)
              is_test_inexact_eq = true;
            if(is_test_exact)
              is_test_exact = false;
 
            sc = sc_variable_substitution_with_eq_ofl_ctrl(sc,
                                                           eq,
                                                           v,
                                                           FWD_OFL_CTRL);
            if(sc_empty_p(sc)) {
              if(is_test_Di)
                NbrTestProjEqDi++;
              else
                NbrTestProjEq++;
              pips_debug(7, "projection-infaisable\n");
 
              for (pv1 = pv; pv1 != NULL; pv1 = pv1->succ) {
                v = pv1->var;
                sc_base_remove_variable(sc, v);
              }
              base_rm(base_sc);
              vect_rm(pve_to_free);
 
              pips_debug(7, "Return 3: empty\n");
              return sc;
            }
 
            sc = sc_normalize(sc);
 
            if(sc_empty_p(sc)) { // FI: should be sc_is_empty_p... or
              // the normalization is repeated...
              pips_debug(7, "normalization detects a non-feasible constraint system\n");
              if(is_test_Di)
                NbrTestProjEqDi++;
              else
                NbrTestProjEq++;
 
              for (pv1 = pv; pv1 != NULL; pv1 = pv1->succ) {
                v = pv1->var;
                sc_base_remove_variable(sc, v);
              }
 
              vect_rm(pve_to_free);
 
              pips_debug(7, "Return 4: empty\n");
              return sc;
            }
 
            // FI: the removal is delayed to end of this function, but
            // sc is nevertheless consistent
            // sc_base_remove_variable(sc, v);
            ifdebug(7) {
              fprintf(stderr, "projected normalised system is:\n");
              sc_syst_debug(sc);
            }
            /*eliminate v in the list of variables pve*/
            if(prv == NULL) /* it's in head */
              pve = pv1 = pv1->succ;
            else
              prv->succ = pv1 = pv1->succ;
          }
        }
      }
    }
 
    pips_assert("sc is consistent after the second use of equations",
                sc_consistent_p(sc));
    ifdebug(7) {
      pips_debug(7, "Variables left to project with Fourier-Motzkin: ");
      vect_dump(pve);
    }
 
    /* carry out the elimination using Fourier-Motzkin for the other variables */
 
    if(pve != NULL) {
      pv1 = pve;
 
      while(pv1 != NULL) {
 
        NbrProjFMTotal++;
        syst_size_init = nb_elems_list(sc->inegalites);
        v = pv1->var;
 
        ifdebug(7) {
          fprintf(stderr, "eliminate %s by F-M\n", entity_local_name((entity)v));
          pips_debug(7, "is_test_exact before: ");
          if(is_test_exact)
            fprintf(stderr, "%s\n", "exact");
          else
            fprintf(stderr, "%s\n", "not exact");
        }
 
        if(combiner_ofl_with_test(sc, v) == false) {
          /* detection of non feasability of Psysteme sc */
          if(is_test_Di)
            NbrTestProjFMDi++;
          else
            NbrTestProjFM++;
          sc_rm(sc);
          sc = sc_empty(base_sc);
          for (pv1 = pv; pv1 != NULL; pv1 = pv1->succ) {
            v = pv1->var;
            sc_base_remove_variable(sc, v);
          }
 
          vect_rm(pve_to_free);
 
          pips_debug(7, "Return 5: empty\n");
          return sc;
        }
 
        sc = sc_normalize(sc);
 
        if(sc_empty_p(sc)) {
          if(is_test_Di)
            NbrTestProjFMDi++;
          else
            NbrTestProjFM++;
          pips_debug(7, "normalisation-infaisable\n");
          for (pv1 = pv; pv1 != NULL; pv1 = pv1->succ) {
            v = pv1->var;
            sc_base_remove_variable(sc, v);
          }
 
          vect_rm(pve_to_free);
 
          pips_debug(7, "Return 6: empty\n");
          return sc;
        }
 
        /*          sc->inegalites = contrainte_sort(sc->inegalites, sc->base, BASE_NULLE, */
        /*                                           true, false); */
 
        /*          ifdebug(8) { */
        /*              debug(8, "", "Sorted system :\n"); */
        /*              sc_syst_debug(sc); */
        /*          } */
 
        build_sc_nredund_2pass_ofl_ctrl(&sc, FWD_OFL_CTRL);
 
        ifdebug(7) {
          pips_debug(7, "is_test_exact after: ");
          if(is_test_exact)
            fprintf(stderr, "%s\n", "exact");
          else
            fprintf(stderr, "%s\n", "not exact");
          fprintf(stderr, "projected normalised system is:\n");
          sc_syst_debug(sc);
        }
        if(nb_elems_list(sc->inegalites) <= syst_size_init)
          NbrFMSystNonAug++;
        pv1 = pv1->succ;
      }
    }
 
    pips_assert("sc is consistent before base update", sc);
 
    /* Are we done? This used to be always true, but sc_normalize()
       may promote inequalities as equations. Since the projection
       steps may reveal some implicit equations, we are not sure here
       that all projections have been performed by the three steps
       (equations, equations, inequalities).
 
       See for instance the test dependence in SAC/sgemm for such an example.
    */
    Pbase mb = sc_to_minimal_basis(sc);
    lb = base_intersection(mb, pv);
    vect_rm(mb);
    
  } while(!BASE_NULLE_P(lb)); // No need to free lb since it is empty
 
  /* Update the base and the dimension of the constraint system sc */
 
  sc->nb_ineq = nb_elems_list(sc->inegalites);
  for (pv1 = pv; pv1 != NULL; pv1 = pv1->succ) {
    v = pv1->var;
    sc_base_remove_variable(sc, v);
  }
 
  pips_assert("sc is consistent after base update", sc);
 
  /* Clean up auxiliary data structures */
  vect_rm(pve_to_free);
  base_rm(base_sc);
 
  pips_debug(7, "final return: faisable\n");
 
  return sc;
}

References Ssysteme::base, base_dup(), base_intersection(), BASE_NULLE, BASE_NULLE_P, base_rm, build_sc_nredund_2pass_ofl_ctrl(), combiner_ofl_with_test(), contrainte_var_min_coeff(), egalite_debug(), Ssysteme::egalites, entity_local_name(), eq, fprintf(), free(), FWD_OFL_CTRL, ifdebug, Ssysteme::inegalites, is_test_Di, is_test_exact, is_test_inexact_eq, nb_elems_list(), Ssysteme::nb_eq, Ssysteme::nb_ineq, NbrFMSystNonAug, NbrProjFMTotal, NbrTestProjEq, NbrTestProjEqDi, NbrTestProjFM, NbrTestProjFMDi, pips_assert, pips_debug, prv(), sc_base_remove_variable(), sc_consistent_p(), sc_empty(), sc_empty_p(), sc_normalize(), sc_rm(), sc_syst_debug(), sc_to_minimal_basis(), Svecteur::succ, value_notone_p, Svecteur::var, vect_dump(), vect_dup(), vect_rm(), and VECTEUR_NUL_P.

Referenced by sc_faisabilite_optim(), sc_minmax_of_variable_optim(), and sc_proj_optim_on_di_ofl().

Here is the call graph for this function:

Here is the caller graph for this function:

vect_chg_var_sign()

void vect_chg_var_sign	(	Pvecteur *	ppv,
		Variable	var
	)

void vect_chg_var_sign(Pvecteur *ppv, Variable var) changement de signe de la coordonnee var du vecteur *ppv

Parameters

ppv	pv
var	ar

Definition at line 1080 of file testdep_util.c.

                              {
  Pvecteur pvcour;
 
  for (pvcour = (*ppv); pvcour != NULL; pvcour = pvcour->succ)
    if(pvcour->var == var)
      value_oppose(pvcour->val);
 
  return;
}

References Svecteur::succ, Svecteur::val, value_oppose, and Svecteur::var.

Referenced by sc_invers().

Here is the caller graph for this function:

Variable Documentation

DiVars

entity DiVars[MAXDEPTH]

here is a collection of function intended to create and manipulate "di" variables and test of dependence.

testdep_util.c

di variables are pseudo variables created by PIPS and not accessible to the user that represent the distance between two dependent statement iterations. the sign of this distance is sufficient for Kennedy's way of parallelizing programs, but the exact value migth be of interest for other algorithms such as systolic algorithms.

Written by Remi, Yi-Qing; reorganized by Yi-Qing (18/09/91) To deal with overflow errors occuring during the projection of a Psysteme along a variable The tables of di variables, li variables and ds variables.

Variable DiVars[i-1] or LiVars[i-1] is associated to the loop at nesting level i. A di variable represents the difference in iteration number between the two references considered.

The variable DsiVars[i] is associated to the ith element in the list of scalar variables modified in the loops

Definition at line 53 of file testdep_util.c.

Referenced by DiVarLevel(), and GetDiVar().

DsiVars

entity DsiVars[MAXSV]

Definition at line 55 of file testdep_util.c.

Referenced by GetDsiVar().

ilc

int ilc = ILCMAX

static

Definition at line 327 of file testdep_util.c.

Referenced by MakeLoopCounter(), and ResetLoopCounter().

LiVars

entity LiVars[MAXDEPTH]

Definition at line 54 of file testdep_util.c.

Referenced by GetLiVar().