ricedg.c File Reference

#include "genC.h"
#include "local.h"
#include "workspace-util.h"
#include "prettyprint.h"

Include dependency graph for ricedg.c:

Go to the source code of this file.

Macros
#define	Psysteme_undefined   SC_UNDEFINED
	to map statements to execution contexts More...
#define	DG_FAST   1
	Different types of dependence tests: More...
#define	DG_FULL   2
#define	DG_SEMANTICS   3

Functions
static bool	rice_dependence_graph (char *)
	INTERFACE FUNCTIONS More...
bool	rice_fast_dependence_graph (char *mod_name)
bool	rice_full_dependence_graph (char *mod_name)
bool	rice_semantics_dependence_graph (char *mod_name)
bool	rice_regions_dependence_graph (char *mod_name)
static void	rdg_unstructured (unstructured)
	STATIC FUNCTION DECLARATIONS More...
static void	rdg_statement (statement)
static void	rdg_loop (statement)
static void	rice_update_dependence_graph (statement stat, set region)
	Update of dependence graph. More...
static list	TestCoupleOfEffects (statement s1, effect e1, statement s2, effect e2, list llv, Ptsg *gs, list *levelsop, Ptsg *gsop)
	DEPENDENCE TEST More...
static list	TestDependence (list n1, Psysteme sc1, statement s1, effect ef1, reference r1, list n2, Psysteme sc2, statement s2, effect ef2, reference r2, list llv, Ptsg *gs, list *levelsop, Ptsg *gsop)
	static list TestDependence(list n1, n2, Psysteme sc1, sc2, statement s1, s2, effect ef1, ef2, reference r1, r2, list llv, list *levelsop, Ptsg *gs,*gsop) input : list n1, n2 : enclosing loops for statements s1 and s2; Psysteme sc1, sc2: current context for each statement; statement s1, s2 : currently analyzed statements; effect ef1, ef2 : effects of each statement upon the current variable; (maybe array regions) reference r1, r2 : current variables references; list llv : loop variant list (variables that vary in loop nests n1 and n2?); list *levelsop : dependence levels from s2 to s1 Ptsg *gs,*gsop : dependence cones from s1 to s2 and from s2 to s1 output : dependence levels from s1 to s2 modifies : levelsop, gsop, gs and returns levels More...
static bool	build_and_test_dependence_context (reference r1, reference r2, Psysteme sc1, Psysteme sc2, Psysteme *psc_dep, list llv, list s2_enc_loops)
	static bool build_and_test_dependence_context(reference r1, r2, Psystem sc1, sc2, *psc_dep, list llv, s2_enc_loops) input : reference r1, r2 : current array references; Psystem sc1, sc2 : context systems for r1 and r2; they might be modified and even be freed (!) by normalization procedures Psystem *psc_dep : pointer toward the dependence context systeme; list llv : current loop nest variant list; list s2_enc_loops : statement s2 enclosing loops; More...
static bool	gcd_and_constant_dependence_test (reference r1, reference r2, list llv, list s2_enc_loops, Psysteme *psc_dep)
	static bool gcd_and_constant_dependence_test(references r1, r2, list llv, s2_enc_loops, Psysteme *psc_dep) input : references r1, r2 : current references; list llv : loop nest variant list; list s2_enc_loops : enclosing loops for statement s2; Psysteme *psc_dep : pointer toward the depedence system; output : true if there is no dependence (GCD and constant test successful); false if independence could not be proved. More...
static void	dependence_system_add_lci_and_di (Psysteme *psc_dep, list s1_enc_loops, Pvecteur *p_DiIncNonCons)
	static void dependence_system_add_lci_and_di(Psysteme *psc_dep, list s1_enc_loops, Pvecteur *p_DiIncNonCons) input : Psysteme *psc_dep : pointer toward the dependence system; list s1_enc_loops : statement s1 enclosing loops; Pvecteur *p_DiIncNonCons : pointer toward DiIncNonCons. More...
static list	TestDiVariables (Psysteme, int, statement, effect, statement, effect)
static Ptsg	dependence_cone_positive (Psysteme dep_sc)
	Ptsg dependence_cone_positive(Psysteme dept_syst) More...
static list	loop_variant_list (statement)
static bool	TestDiCnst (Psysteme, int, statement, effect, statement, effect)
list	TestCoupleOfReferences (list n1, Psysteme sc1 __attribute__((unused)), statement s1, effect ef1, reference r1, list n2, Psysteme sc2 __attribute__((unused)), statement s2, effect ef2, reference r2, list llv, Ptsg *gs __attribute__((unused)), list *levelsop __attribute__((unused)), Ptsg *gsop __attribute__((unused)))
static list	TestDiVariables (Psysteme ps, int cl, statement s1, effect ef1 __attribute__((unused)), statement s2, effect ef2 __attribute__((unused)))
static bool	TestDiCnst (Psysteme ps, int cl, statement s1, effect ef1 __attribute__((unused)), statement s2, effect ef2 __attribute__((unused)))
	this function detects intra-statement, non loop carried dependence ( Di=(0,0,...0) and s1 = s2). More...
void	writeresult (char *mod_name)
graph	compute_dg_on_statement_from_chains_in_place (statement s, graph chains)
graph	compute_dg_on_statement_from_chains (statement s, graph chains)

Variables
int	NbrArrayDepInit = 0
	Dependence Graph computation for Allen & Kennedy algorithm. More...
int	NbrIndepFind = 0
int	NbrAllEquals = 0
int	NbrDepCnst = 0
int	NbrTestExact = 0
int	NbrDepInexactEq = 0
int	NbrDepInexactFM = 0
int	NbrDepInexactEFM = 0
int	NbrScalDep = 0
int	NbrIndexDep = 0
int	deptype [5][3]
int	constdep [5][3]
int	NbrTestCnst = 0
int	NbrTestGcd = 0
int	NbrTestSimple = 0
int	NbrTestDiCnst = 0
	by sc_normalize() More...
int	NbrTestProjEqDi = 0
int	NbrTestProjFMDi = 0
int	NbrTestProjEq = 0
int	NbrTestProjFM = 0
int	NbrTestDiVar = 0
int	NbrProjFMTotal = 0
int	NbrFMSystNonAug = 0
int	FMComp [18]
bool	is_test_exact = true
	or counting the number of F-M complexity less than 16. More...
bool	is_test_inexact_eq = false
bool	is_test_inexact_fm = false
bool	is_dep_cnst = false
bool	is_test_Di
bool	Finds2s1
static graph	dg
	to map statements to enclosing loops More...
static bool	PRINT_RSDG = false
static int	dg_type = DG_FAST
int	Nbrdo
	loop.c More...

Macro Definition Documentation

DG_FAST

#define DG_FAST   1

Different types of dependence tests:

switch dg_type:

 DG_FAST: no context constraints are added
 DG_FULL: use loop bounds as context
 DG_SEMANTICS : use preconditions as context

The use of the variable dg_type allows to add more cases in the future.

Definition at line 124 of file ricedg.c.

DG_FULL

#define DG_FULL   2

Definition at line 125 of file ricedg.c.

DG_SEMANTICS

#define DG_SEMANTICS   3

Definition at line 126 of file ricedg.c.

Psysteme_undefined

#define Psysteme_undefined   SC_UNDEFINED

to map statements to execution contexts

Psysteme_undefined is not defined in sc.h; as Psysteme is external, I define it here. BA, September 1993

Definition at line 103 of file ricedg.c.

Function Documentation

build_and_test_dependence_context()

static bool build_and_test_dependence_context ( reference  r1, reference  r2, Psysteme  sc1, Psysteme  sc2, Psysteme *  psc_dep, list  llv, list  s2_enc_loops  )

static

static bool build_and_test_dependence_context(reference r1, r2, Psystem sc1, sc2, *psc_dep, list llv, s2_enc_loops) input : reference r1, r2 : current array references; Psystem sc1, sc2 : context systems for r1 and r2; they might be modified and even be freed (!) by normalization procedures Psystem *psc_dep : pointer toward the dependence context systeme; list llv : current loop nest variant list; list s2_enc_loops : statement s2 enclosing loops;

output : bool : false if one of the initial systems is unfeasible after normalization; true otherwise; *psc_dep : dependence system is the function value is true; SC_EMPTY otherwise; no need to sc_rm() in the latter case.

side effects : psc_dep : points toward the dependence context system built from sc1 and sc2, r1 and r2, and llv. Dependence distance variables (di) are introduced in sc2, along with the dsi variables to take care of variables in llv modified in the loop nest; irrelevant (?) existencial constraints are removed. in order to make further manipulations easier. sc1 : side_effect of sc_normalize() sc2 : side_effect of sc_normalize()

Comment :

Modifications:

• sc1 and sc2 cannot be sc_normalized because they may be part of statement preconditions or regions; sc_normalize() is replaced by sc_empty_p(); since regions and preconditions are normalized with stronger normalization procedure, and since the feasibility of the dependence test will be tested with an even stronger test, this should have no accuracy impact (FI, 12 December 1995)

Construction of initial systems sc_dep and sc_tmp from sc1 and sc2 if not undefined

sc_dep = sc1, but: we keep only useful constraints in the predicate (To avoid overflow errors, and to make projections easier)

sc_tmp = sc2, but: we keep only useful constraints in the predicate (To avoid overflow errors, and to make projections easier)

FI: I'm not sure this is correct. I'm afraid sc2 might be unfeasible and become feasible due to a careless elimination... It all depends on:

sc_restricted_to_variables_transitive_closure()

There might be a better function for that purpose

introduce dependence distance variable if loop increment value is known or ...

FI: a more powerful evaluation function for inc should be called when preconditions are available. For instance, mdg could be handled without having to partial_evaluate it

It's not clear whether sc1 or sc2 should be used to estimate a variable increment like N.

It's not clear whether it's correct or not. You would like N (or other variables in the increment expression) to be constant within the loop nest.

It would be better to know the precondition associated to the corresponding loop statement, but the information is lost in this low-level function.

FI: this is not true, you have sc1 and sc2 at hand to call sc_minmax_of_variable()

take care of variables modified in the loop

sc_tmp is emptied and freed by sc_fusion()

Definition at line 1580 of file ricedg.c.

                                                                 {
  Psysteme sc_dep, sc_tmp;
  list pc;
  int l, inc;
 
  /* *psc_dep must be undefined */pips_assert("build_and_test_dependence_context", SC_UNDEFINED_P(*psc_dep));
 
  /* Construction of initial systems sc_dep and sc_tmp from sc1 and sc2
   if not undefined
   */
  if(SC_UNDEFINED_P(sc1) && SC_UNDEFINED_P(sc2)) {
    sc_dep = sc_new();
  } else {
    if(SC_UNDEFINED_P(sc1))
      sc_dep = sc_new();
    else {
      /* sc_dep = sc1, but:
       * we keep only useful constraints in the predicate
       * (To avoid overflow errors, and to make projections easier)
       */
      Pbase variables = BASE_UNDEFINED;
 
      if(sc_empty_p(sc1)) {
        *psc_dep = SC_EMPTY;
        pips_debug(4,
            "first initial normalized system sc1 not feasible\n");
        return (false);
      }
 
      ifdebug(6) {
        debug(6, "", "Initial system sc1 before restrictions : \n");
        sc_syst_debug(sc1);
      }
 
      FOREACH(EXPRESSION, ex1,reference_indices(r1)) {
        normalized x1 = NORMALIZE_EXPRESSION(ex1);
 
        if(normalized_linear_p(x1)) {
          Pvecteur v1;
          Pvecteur v;
          v1 = (Pvecteur)normalized_linear(x1);
          for (v = v1; !VECTEUR_NUL_P(v); v = v->succ) {
            if(vecteur_var(v) != TCST)
              variables = base_add_variable(variables, vecteur_var(v));
          }
        }
      }
 
      sc_dep = sc_restricted_to_variables_transitive_closure(sc1, variables);
    }
 
    if(SC_UNDEFINED_P(sc2))
      sc_tmp = sc_new();
    else {
      /* sc_tmp = sc2, but:
       * we keep only useful constraints in the predicate
       * (To avoid overflow errors, and to make projections easier)
       *
       * FI: I'm not sure this is correct. I'm afraid sc2 might
       * be unfeasible and become feasible due to a careless
       * elimination... It all depends on:
       *
       *     sc_restricted_to_variables_transitive_closure()
       *
       * There might be a better function for that purpose
       */
      Pbase variables = BASE_UNDEFINED;
 
      if(sc_empty_p(sc2)) {
        *psc_dep = SC_EMPTY;
        pips_debug(4,
            "second initial normalized system not feasible\n");
        return (false);
      }
 
      ifdebug(6) {
        debug(6, "", "Initial system sc2 before restrictions : \n");
        sc_syst_debug(sc2);
      }
 
      FOREACH(EXPRESSION, ex2, reference_indices(r2)) {
        normalized x2 = NORMALIZE_EXPRESSION(ex2);
 
        if(normalized_linear_p(x2)) {
          Pvecteur v2;
          Pvecteur v;
 
          v2 = (Pvecteur)normalized_linear(x2);
          for (v = v2; !VECTEUR_NUL_P(v); v = v->succ) {
            if(vecteur_var(v) != TCST)
              variables = base_add_variable(variables, vecteur_var(v));
          }
 
        }
      }
 
 
      sc_tmp = sc_restricted_to_variables_transitive_closure(sc2, variables);
    }
 
    ifdebug(6) {
      debug(6, "", "Initial systems after restrictions : \n");
      sc_syst_debug(sc_dep);
      sc_syst_debug(sc_tmp);
    }
 
    /* introduce dependence distance variable if loop increment value
     is known or ... */
    for (pc = s2_enc_loops, l = 1; pc != NIL; pc = CDR(pc), l++) {
      loop lo = statement_loop(STATEMENT(CAR(pc)));
      entity i2 = loop_index(lo);
      /* FI: a more powerful evaluation function for inc should be called
       * when preconditions are available. For instance, mdg could
       * be handled without having to partial_evaluate it
       *
       * It's not clear whether sc1 or sc2 should be used to
       * estimate a variable increment like N.
       *
       * It's not clear whether it's correct or not. You would like
       * N (or other variables in the increment expression) to be
       * constant within the loop nest.
       *
       * It would be better to know the precondition associated
       * to the corresponding loop statement, but the information
       * is lost in this low-level function.
       *
       * FI: this is not true, you have sc1 and sc2 at hand to call
       * sc_minmax_of_variable()
       */
      inc = loop_increment_value(lo);
      if(inc != 0)
        sc_add_di(l, i2, sc_tmp, inc);
      else
        sc_chg_var(sc_tmp, (Variable)i2, (Variable)GetLiVar(l));
    }
 
    /* take care of variables modified in the loop */
    for (pc = llv, l = 1; pc != NIL; pc = CDR(pc), l++) {
      sc_add_dsi(l, ENTITY(CAR(pc)), sc_tmp);
    }
 
    /* sc_tmp is emptied and freed by sc_fusion() */
    sc_dep = sc_fusion(sc_dep, sc_tmp);
    vect_rm(sc_dep->base);
    sc_dep->base = BASE_NULLE;
    sc_creer_base(sc_dep);
 
  }
 
  ifdebug(6) {
    pips_debug(6,
        "\ndependence context is:\n");
    sc_syst_debug(sc_dep);
  }
 
  *psc_dep = sc_dep;
  return (true);
}

References Ssysteme::base, base_add_variable(), BASE_NULLE, BASE_UNDEFINED, CAR, CDR, debug(), ENTITY, EXPRESSION, FOREACH, GetLiVar(), ifdebug, loop_increment_value(), loop_index, NIL, NORMALIZE_EXPRESSION, normalized_linear, normalized_linear_p, pips_assert, pips_debug, reference_indices, sc_add_di(), sc_add_dsi(), sc_chg_var(), sc_creer_base(), sc_empty_p(), sc_fusion(), sc_new(), sc_restricted_to_variables_transitive_closure(), sc_syst_debug(), STATEMENT, statement_loop(), Svecteur::succ, TCST, variables, vect_rm(), 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:

compute_dg_on_statement_from_chains()

graph compute_dg_on_statement_from_chains	(	statement	s,
		graph	chains
	)

Parameters

chains

hains

Definition at line 2363 of file ricedg.c.

                                                                     {
  dg = copy_graph(chains);
  return compute_dg_on_statement_from_chains_in_place(s, dg);
}

References chains(), compute_dg_on_statement_from_chains_in_place(), copy_graph(), and dg.

Here is the call graph for this function:

compute_dg_on_statement_from_chains_in_place()

graph compute_dg_on_statement_from_chains_in_place	(	statement	s,
		graph	chains
	)

Parameters

chains

hains

Definition at line 2342 of file ricedg.c.

                                                                              {
  dg = chains;
  dg_type = DG_FAST; //FIXME
 
  debug_on("QUICK_PRIVATIZER_DEBUG_LEVEL");
  quick_privatize_graph(dg);
  debug_off();
 
  memset(deptype,0,sizeof(deptype));
  memset(constdep,0,sizeof(deptype));
 
  rdg_statement(s);
 
  return dg;
}

References chains(), constdep, debug_off, debug_on, deptype, dg, DG_FAST, dg_type, memset(), quick_privatize_graph(), and rdg_statement().

Referenced by compute_dg_on_statement_from_chains().

Here is the call graph for this function:

Here is the caller graph for this function:

dependence_cone_positive()

static Ptsg dependence_cone_positive ( Psysteme  dep_sc )

static

Ptsg dependence_cone_positive(Psysteme dept_syst)

add the contraints bj = 0 (1<=j<i)

add the contraints - bi <= -1 (1<=j<i)

dans le cas d'une erreur d'overflow, on fait comme si le test avait renvoye' true. bc.

to mimic previous behavior of sc_normalize

We get a normalized sub lexico-positive dependence system

Parameters

dep_sc

ep_sc

Definition at line 2096 of file ricedg.c.

                   {
  Psysteme volatile sc_env = SC_UNDEFINED;
  Ptsg volatile sg_env = NULL;
  Pbase b;
  int n, j;
  int volatile i;
 
  if(SC_UNDEFINED_P(dep_sc))
    return (sg_new());
 
  sc_env = sc_empty(base_dup(dep_sc->base));
  n = dep_sc->dimension;
  b = dep_sc->base;
 
  for (i = 1; i <= n; i++) {
    volatile Psysteme sub_sc = sc_dup(dep_sc);
    Pvecteur v;
    Pcontrainte pc;
    Pbase b1;
 
    for (j = 1, b1 = b; j <= i - 1; j++, b1 = b1->succ) {
      /* add the contraints  bj = 0 (1<=j<i) */
      v = vect_new(b1->var, 1);
      pc = contrainte_make(v);
      sc_add_eg(sub_sc,pc);
    }
    /* add the contraints - bi <= -1 (1<=j<i) */
    v = vect_new(b1->var, -1);
    vect_add_elem(&v, TCST, 1);
    pc = contrainte_make(v);
    sc_add_ineg(sub_sc,pc);
 
    ifdebug(7) {
      fprintf(stderr, "\nInitial sub lexico-positive dependence system:\n");
      sc_syst_debug(sub_sc);
    }
 
    /* dans le cas d'une erreur d'overflow, on fait comme si le test
     *  avait renvoye' true. bc.
     */CATCH(overflow_error) {
      pips_debug(1, "overflow error.\n");
    } TRY
    {
      if(!sc_integer_feasibility_ofl_ctrl(sub_sc, FWD_OFL_CTRL, true)) {
        sc_rm(sub_sc);
        pips_debug(7,"sub lexico-positive dependence system not feasible\n");
 
        UNCATCH(overflow_error);
        continue;
      } else
        UNCATCH(overflow_error);
 
    }
 
    if(sc_empty_p(sub_sc = sc_normalize(sub_sc))) {
      sc_rm(sub_sc); /* to mimic previous behavior of sc_normalize */
      pips_debug(7, "normalized system not feasible\n");
 
      continue;
    }
 
    /* We get a normalized sub lexico-positive dependence system */ifdebug(7) {
      fprintf(stderr, "Normalized sub lexico-positive dependence system :\n");
      sc_syst_debug(sub_sc);
    }
 
    {
      Psysteme old_sc_env = sc_env;
      sc_env = sc_enveloppe_chernikova(sc_env, sub_sc);
      sc_rm(old_sc_env);
    }
 
    sc_rm(sub_sc);
 
    ifdebug(7) {
      fprintf(stderr, "Dependence system of the enveloppe of subs "
        "lexico-positive dependence:\n");
      sc_syst_debug(sc_env);
 
      if(!SC_UNDEFINED_P(sc_env) && !sc_rn_p(sc_env)) {
        sg_env = sc_to_sg_chernikova(sc_env);
        fprintf(stderr, "Enveloppe of the subs lexico-positive "
          "dependence cones:\n");
        if(!SG_UNDEFINED_P(sg_env) && vect_size(sg_env->base) != 0) {
          print_dependence_cone(stderr, sg_env, sg_env->base);
          sg_rm(sg_env);
          sg_env = (Ptsg)NULL;
        }
      }
    }
 
  }
 
  if(!SC_UNDEFINED_P(sc_env) && sc_dimension(sc_env) != 0) {
 
    sg_env = sc_to_sg_chernikova(sc_env);
    sc_rm(sc_env);
  } else {
    sg_env = sg_new();
  }
 
  return (sg_env);
}

References b1, type_sg::base, base_dup(), CATCH, contrainte_make(), fprintf(), FWD_OFL_CTRL, ifdebug, overflow_error, pips_debug, print_dependence_cone(), sc_dup(), sc_empty(), sc_empty_p(), sc_enveloppe_chernikova(), sc_integer_feasibility_ofl_ctrl(), sc_normalize(), sc_rm(), sc_rn_p(), sc_syst_debug(), sc_to_sg_chernikova(), sg_new(), sg_rm(), SG_UNDEFINED_P, TCST, TRY, UNCATCH, vect_add_elem(), vect_new(), and vect_size().

Referenced by TestDependence().

Here is the call graph for this function:

Here is the caller graph for this function:

dependence_system_add_lci_and_di()

static void dependence_system_add_lci_and_di ( Psysteme *  psc_dep, list  s1_enc_loops, Pvecteur *  p_DiIncNonCons  )

static

static void dependence_system_add_lci_and_di(Psysteme *psc_dep, list s1_enc_loops, Pvecteur *p_DiIncNonCons) input : Psysteme *psc_dep : pointer toward the dependence system; list s1_enc_loops : statement s1 enclosing loops; Pvecteur *p_DiIncNonCons : pointer toward DiIncNonCons.

output : none

modifies :

*psc_dep, the dependence systeme (addition of constraints with lci and di variables, if useful; lci is a loop counter, di an iteration difference variable);

DiIncNonCons: di variables are added to DiIncNonCons (means Di variables for loops with non constant increment, i.e. unknown increment), if any such loop exists.

comment : DiIncNonCons must be undefined on entry.

Addition of lck, the loop counters, and di, the iteration difference, variables (if useful).

If the loop increment is not trivial, express the current index value as the sum of the lower bound and the product of the loop counter by the loop increment.

Else, this new equation would be redundant

make nl + inc*lc# - ind = 0

If the loop increment is unknown, which is expressed by inc==0, well, I do not understand what li variables are, not how they work

make d::i - l::i + ind = 0 , add d::i in list of DiIncNonCons

Update basis

Definition at line 1883 of file ricedg.c.

                                                                {
  int l;
  list pc;
 
  pips_assert("dependence_system_add_lci_and_di",
      VECTEUR_UNDEFINED_P(*p_DiIncNonCons));
 
  /* Addition of lck, the loop counters, and di, the iteration difference,
   * variables (if useful).
   */
  for (pc = s1_enc_loops, l = 1; pc != NIL; pc = CDR(pc), l++) {
    loop lo = statement_loop(STATEMENT(CAR(pc)));
    entity ind = loop_index(lo);
    int inc = loop_increment_value(lo);
 
    expression lb = range_lower(loop_range(lo));
    normalized nl = NORMALIZE_EXPRESSION(lb);
 
    /* If the loop increment is not trivial, express the current
     * index value as the sum of the lower bound and the product
     * of the loop counter by the loop increment.
     *
     * Else, this new equation would be redundant
     */
    /* make   nl + inc*lc# - ind = 0 */
    if(inc != 0 && inc != 1 && inc != -1 && normalized_linear_p(nl)) {
      Pcontrainte pc;
      entity lc;
      Pvecteur pv;
 
      lc = MakeLoopCounter();
      pv = vect_dup((Pvecteur)normalized_linear(nl));
      vect_add_elem(&pv, (Variable)lc, inc);
      vect_add_elem(&pv, (Variable)ind, -1);
      pc = contrainte_make(pv);
      sc_add_eg(*psc_dep, pc);
    }
 
    /* If the loop increment is unknown, which is expressed by inc==0,
     * well, I do not understand what li variables are, not how they work
     */
    /* make d#i - l#i + ind = 0 ,
     add d#i in list of DiIncNonCons*/
    if(inc == 0) {
      Pcontrainte pc;
      Pvecteur pv = NULL;
      entity di;
 
      di = GetDiVar(l);
      vect_add_elem(&pv, (Variable)di, 1);
      vect_add_elem(&pv, (Variable)GetLiVar(l), -1);
      vect_add_elem(&pv, (Variable)ind, 1);
      pc = contrainte_make(pv);
      sc_add_eg(*psc_dep, pc);
 
      vect_add_elem(p_DiIncNonCons, (Variable)di, 1);
    }
 
  }
 
  /* Update basis */
  if(!BASE_NULLE_P((*psc_dep)->base)) {
    vect_rm((*psc_dep)->base);
    (*psc_dep)->base = BASE_UNDEFINED;
  }
  sc_creer_base(*psc_dep);
}

References BASE_NULLE_P, BASE_UNDEFINED, CAR, CDR, contrainte_make(), GetDiVar(), GetLiVar(), loop_increment_value(), loop_index, loop_range, MakeLoopCounter(), NIL, NORMALIZE_EXPRESSION, normalized_linear, normalized_linear_p, pips_assert, range_lower, sc_creer_base(), STATEMENT, statement_loop(), vect_add_elem(), vect_dup(), vect_rm(), and VECTEUR_UNDEFINED_P.

Referenced by TestDependence().

Here is the call graph for this function:

Here is the caller graph for this function:

gcd_and_constant_dependence_test()

static bool gcd_and_constant_dependence_test ( reference  r1, reference  r2, list  llv, list  s2_enc_loops, Psysteme *  psc_dep  )

static

static bool gcd_and_constant_dependence_test(references r1, r2, list llv, s2_enc_loops, Psysteme *psc_dep) input : references r1, r2 : current references; list llv : loop nest variant list; list s2_enc_loops : enclosing loops for statement s2; Psysteme *psc_dep : pointer toward the depedence system; output : true if there is no dependence (GCD and constant test successful); false if independence could not be proved.

modifies : *psc_dep; at least adds dependence equations on phi variables comment :

• *psc_dep must be defined on entry; it must have been initialized by build_and_test_dependence_context.
• no side effects on r1, r2,...

Further construction of the dependence system; Constant and GCD tests at the same time.

case of T(3)=... et T(4)=...

test of GCD

C assumed

Update base of *psc_dep

Definition at line 1761 of file ricedg.c.

                                                                 {
  list pc1, pc2, pc;
  int l;
 
  /* Further construction of the dependence system; Constant and GCD tests
   * at the same time.
   */
  pc1 = reference_indices(r1);
  pc2 = reference_indices(r2);
 
  while(pc1 != NIL && pc2 != NIL) {
    expression ex1, ex2;
    normalized x1, x2;
 
    ex1 = EXPRESSION(CAR(pc1));
    x1 = NORMALIZE_EXPRESSION(ex1);
 
    ex2 = EXPRESSION(CAR(pc2));
    x2 = NORMALIZE_EXPRESSION(ex2);
 
    if(normalized_linear_p(x1) && normalized_linear_p(x2)) {
      Pvecteur v1, v2, v;
 
      v1 = (Pvecteur)normalized_linear(x1);
      v2 = vect_dup((Pvecteur)normalized_linear(x2));
 
      for (pc = s2_enc_loops, l = 1; pc != NIL; pc = CDR(pc), l++) {
        loop lo = statement_loop(STATEMENT(CAR(pc)));
        entity i = loop_index(lo);
        int li = loop_increment_value(lo);
        Value vli = int_to_value(li);
        if(value_notzero_p(vli)) {
          Value v = vect_coeff((Variable)i, v2);
          value_product(v,vli);
          vect_add_elem(&v2, (Variable)GetDiVar(l), v);
        } else
          vect_chg_var(&v2, (Variable)i, (Variable)GetLiVar(l));
      }
 
      for (pc = llv, l = 1; pc != NIL; pc = CDR(pc), l++) {
        vect_add_elem(&v2,
                      (Variable)GetDsiVar(l),
                      vect_coeff((Variable)ENTITY(CAR(pc)), v2));
      }
 
      if(!VECTEUR_UNDEFINED_P(v = vect_substract(v1, v2))) {
        Pcontrainte c = contrainte_make(v);
 
        /* case of T(3)=... et T(4)=... */
        if(contrainte_constante_p(c) && value_notzero_p(COEFF_CST(c))) {
          NbrTestCnst++;
          pips_debug(4,"TestCnst succeeded!");
          return (true);
        }
        /* test of GCD */
        if(egalite_normalize(c) == false) {
          NbrTestGcd++;
          pips_debug(4,"TestGcd succeeded!\n");
          return (true);
        }
        sc_add_eg(*psc_dep, c);
      }
      vect_rm(v2);
    }
 
    pc1 = CDR(pc1);
    pc2 = CDR(pc2);
  }
 
  if(pc1 != NIL || pc2 != NIL) {
    if(fortran_module_p(get_current_module_entity())) {
      pips_internal_error("numbers of subscript expressions differ");
    } else {
      /* C assumed */
      pips_user_warning("dependence tested between two memory access paths"
                        " of different lengths for variable \"%s\".\n",
                        entity_user_name(reference_variable(r1)));
    }
  }
 
  /* Update base of *psc_dep */
  Pbase mb = sc_to_minimal_basis(*psc_dep);
  Pbase cb = sc_base(*psc_dep);
  if(!vect_in_basis_p(mb, cb)) {
    Pbase nb = base_union(cb, mb);
    sc_base(*psc_dep) = nb;
    sc_dimension(*psc_dep) = vect_size(nb); // base_dimension(nb);
    vect_rm(cb);
  }
  vect_rm(mb);
 
  pips_assert("The dependence system is consistent", sc_consistent_p(*psc_dep));
 
  return (false);
}

References base_union(), CAR, CDR, COEFF_CST, contrainte_constante_p(), contrainte_make(), egalite_normalize(), ENTITY, entity_user_name(), EXPRESSION, fortran_module_p(), get_current_module_entity(), GetDiVar(), GetDsiVar(), GetLiVar(), int_to_value, loop_increment_value(), loop_index, NbrTestCnst, NbrTestGcd, NIL, NORMALIZE_EXPRESSION, normalized_linear, normalized_linear_p, pips_assert, pips_debug, pips_internal_error, pips_user_warning, reference_indices, reference_variable, sc_consistent_p(), sc_to_minimal_basis(), STATEMENT, statement_loop(), value_notzero_p, value_product, vect_add_elem(), vect_chg_var(), vect_coeff(), vect_dup(), vect_in_basis_p(), vect_rm(), vect_size(), vect_substract(), and VECTEUR_UNDEFINED_P.

Referenced by TestDependence().

Here is the call graph for this function:

Here is the caller graph for this function:

loop_variant_list()

static list loop_variant_list ( statement  stat )

static

Parameters

stat

tat

Definition at line 2201 of file ricedg.c.

                  {
  list lv = NIL;
  loop l;
  list locals;
 
  pips_assert("statement stat is a loop", statement_loop_p(stat));
  FOREACH (EFFECT, ef, load_cumulated_rw_effects_list(stat)) {
    entity en = effect_entity(ef);
    if(action_write_p( effect_action( ef )) && !entity_all_locations_p(en)
        && entity_integer_scalar_p(en))
      lv = gen_nconc(lv, CONS(ENTITY, en, NIL));
  }
  l = statement_loop(stat);
  locals = loop_locals(l);
  FOREACH (ENTITY, v, locals) {
    if(gen_find_eq(v, lv) == entity_undefined)
      lv = CONS(ENTITY, v, lv);
  }
  locals = statement_declarations(loop_body(l));
  FOREACH (ENTITY, v, locals) {
    if(gen_find_eq(v, lv) == entity_undefined)
      lv = CONS(ENTITY, v, lv);
  }
  return (lv);
}

References action_write_p, CONS, EFFECT, effect_action, effect_entity(), ENTITY, entity_all_locations_p(), entity_integer_scalar_p(), entity_undefined, FOREACH, gen_find_eq(), gen_nconc(), load_cumulated_rw_effects_list(), loop_body, loop_locals, NIL, pips_assert, statement_declarations, statement_loop(), and statement_loop_p().

Referenced by rice_update_dependence_graph().

Here is the call graph for this function:

Here is the caller graph for this function:

rdg_loop()

static void rdg_loop ( statement  stat )

static

Parameters

stat

tat

Definition at line 452 of file ricedg.c.

                                     {
  set region;
 
  if(get_bool_property("COMPUTE_ALL_DEPENDENCES")) {
    region = region_of_loop(stat);
    ifdebug(7) {
      fprintf(stderr, "[rdg_loop] applied on region:\n");
      print_statement_set(stderr, region);
    }
    rice_update_dependence_graph(stat, region);
  } else {
    if((region = distributable_loop(stat)) == set_undefined) {
      ifdebug(1) {
        fprintf(stderr,
                "[rdg_loop] skipping loop %td (but recursing)\n",
                statement_number(stat));
      }
      rdg_statement(loop_body(statement_loop(stat)));
    } else {
      rice_update_dependence_graph(stat, region);
      set_free(region);
    }
  }
}

References distributable_loop(), fprintf(), get_bool_property(), ifdebug, loop_body, print_statement_set(), rdg_statement(), region, region_of_loop(), rice_update_dependence_graph(), set_free(), set_undefined, statement_loop(), and statement_number.

Referenced by rdg_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

rdg_statement()

static void rdg_statement ( statement  stat )

static

Parameters

stat

tat

Definition at line 409 of file ricedg.c.

                                          {
  forloop fl = forloop_undefined;
  whileloop wl = whileloop_undefined;
  statement body = statement_undefined;
  instruction istat = statement_instruction(stat);
 
  switch(instruction_tag(istat)) {
    case is_instruction_block: {
      FOREACH (STATEMENT, s, instruction_block(istat))
        rdg_statement(s);
      break;
    }
    case is_instruction_test:
      rdg_statement(test_true(instruction_test(istat)));
      rdg_statement(test_false(instruction_test(istat)));
      break;
    case is_instruction_loop:
      rdg_loop(stat);
      break;
    case is_instruction_whileloop:
      wl = instruction_whileloop (istat);
      body = whileloop_body (wl);
      rdg_statement(body);
      break;
    case is_instruction_forloop:
      fl = instruction_forloop (istat);
      body = forloop_body (fl);
      rdg_statement(body);
      break;
    case is_instruction_goto:
    case is_instruction_call:
    case is_instruction_expression:
      break;
    case is_instruction_unstructured:
      rdg_unstructured(instruction_unstructured(istat));
      break;
    default:
      pips_internal_error("case default reached with tag %d",
          instruction_tag(istat));
      break;
  }
}

References FOREACH, forloop_body, forloop_undefined, instruction_block, instruction_forloop, instruction_tag, instruction_test, instruction_unstructured, instruction_whileloop, is_instruction_block, is_instruction_call, is_instruction_expression, is_instruction_forloop, is_instruction_goto, is_instruction_loop, is_instruction_test, is_instruction_unstructured, is_instruction_whileloop, pips_internal_error, rdg_loop(), rdg_unstructured(), STATEMENT, statement_instruction, statement_undefined, test_false, test_true, whileloop_body, and whileloop_undefined.

Referenced by compute_dg_on_statement_from_chains_in_place(), rdg_loop(), rdg_unstructured(), and rice_dependence_graph().

Here is the call graph for this function:

Here is the caller graph for this function:

rdg_unstructured()

static void rdg_unstructured ( unstructured  u )

static

STATIC FUNCTION DECLARATIONS

Definition at line 399 of file ricedg.c.

                                             {
  list blocs = NIL;
 
  CONTROL_MAP(c, {
        rdg_statement(control_statement(c));
      }, unstructured_control(u), blocs);
 
  gen_free_list(blocs);
}

References CONTROL_MAP, control_statement, gen_free_list(), NIL, rdg_statement(), and unstructured_control.

Referenced by rdg_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

rice_dependence_graph()

static bool rice_dependence_graph ( char *  mod_name )

static

INTERFACE FUNCTIONS

The supplementary call to init_ordering_to_statement should be avoided if ordering.c were more clever.

we need to access the statements from their ordering for the dependance-graph:

Do this as late as possible as it is also used by pipsdbm...

walk thru mod_stat to find well structured loops. update dependence graph for these loops.

write the result to the file correspondant in the order of : module,NbrArrayDeptInit,NbrIndeptFind,NbrArrayDepInit,NbrScalDep, NbrIndexDep,deptype[5][3]

FI: this is not a proper way to do it

Parameters

mod_name

od_name

Definition at line 230 of file ricedg.c.

                                                  {
  FILE *fp;
 
  statement mod_stat;
  int i, j;
  graph chains;
  string dg_name;
  entity module = local_name_to_top_level_entity(mod_name);
 
  set_current_module_entity(module);
 
  set_current_module_statement((statement)db_get_memory_resource(DBR_CODE,
                                                                 mod_name,
                                                                 true));
  mod_stat = get_current_module_statement();
 
  chains = (graph)db_get_memory_resource(DBR_CHAINS, mod_name, true);
 
  ResetLoopCounter();
 
  debug_on("RICEDG_DEBUG_LEVEL");
  pips_debug(1, "Computing Rice dependence graph for %s\n", mod_name);
 
  ifdebug(2) {
    hash_warn_on_redefinition();
    graph_consistent_p(chains);
  }
 
  ifdebug(1) {
    fprintf(stderr,
            "Space for chains: %d bytes\n",
            gen_allocated_memory((gen_chunk *)chains));
    fprintf(stderr,
            "Space for obj_table: %d bytes\n",
            current_shared_obj_table_size());
  }
 
  hash_warn_on_redefinition();
  dg = copy_graph(chains);
 
  ifdebug(1) {
    fprintf(stderr,
            "Space for chains's copy: %d bytes\n",
            gen_allocated_memory((gen_chunk *)dg));
    fprintf(stderr,
            "Space for obj_table: %d bytes\n",
            current_shared_obj_table_size());
  }
 
  pips_debug(8,"original graph\n");
  ifdebug(8) {
    set_ordering_to_statement(mod_stat);
    prettyprint_dependence_graph(stderr, mod_stat, dg);
    reset_ordering_to_statement();
  }
 
  debug_off();
 
  if(dg_type == DG_SEMANTICS)
    set_precondition_map((statement_mapping)db_get_memory_resource(DBR_PRECONDITIONS,
                                                                   mod_name,
                                                                   true));
 
  set_cumulated_rw_effects((statement_effects)db_get_memory_resource(DBR_CUMULATED_EFFECTS,
                                                                     mod_name,
                                                                     true));
 
  debug_on("RICEDG_DEBUG_LEVEL");
  pips_debug(1, "finding enclosing loops ...\n");
 
  set_enclosing_loops_map(loops_mapping_of_statement(mod_stat));
  ifdebug(3) {
    fprintf(stderr, "\nThe number of DOs :\n");
    fprintf(stderr, " Nbrdo=%d", Nbrdo);
  }
  debug_on("QUICK_PRIVATIZER_DEBUG_LEVEL");
 
  /* we need to access the statements from their ordering for the
   dependance-graph: */
  /* Do this as late as possible as it is also used by pipsdbm... */
  set_ordering_to_statement(mod_stat);
 
  quick_privatize_graph(dg);
  debug_off();
 
  for (i = 0; i <= 4; i++) {
    for (j = 0; j <= 2; j++) {
      deptype[i][j] = 0;
      constdep[i][j] = 0;
    }
  }
 
  /* walk thru mod_stat to find well structured loops.
   update dependence graph for these loops. */
 
  rdg_statement(mod_stat);
 
  ifdebug(3) {
    fprintf(stderr, "\nThe results of statistique of test of dependence are:\n");
    fprintf(stderr, "NbrArrayDepInit = %d\n", NbrArrayDepInit);
    fprintf(stderr, "NbrIndepFind = %d\n", NbrIndepFind);
    fprintf(stderr, "NbrAllEquals = %d\n", NbrAllEquals);
    fprintf(stderr, "NbrDepCnst = %d\n", NbrDepCnst);
    fprintf(stderr, "NbrTestExact= %d\n", NbrTestExact);
    fprintf(stderr, "NbrDepInexactEq= %d\n", NbrDepInexactEq);
    fprintf(stderr, "NbrDepInexactFM= %d\n", NbrDepInexactFM);
    fprintf(stderr, "NbrDepInexactEFM= %d\n", NbrDepInexactEFM);
    fprintf(stderr, "NbrScalDep = %d\n", NbrScalDep);
    fprintf(stderr, "NbrIndexDep = %d\n", NbrIndexDep);
    fprintf(stderr, "deptype[][]");
    for (i = 0; i <= 4; i++)
      for (j = 0; j <= 2; j++)
        fprintf(stderr, "%d  ", deptype[i][j]);
    fprintf(stderr, "\nconstdep[][]");
    for (i = 0; i <= 4; i++)
      for (j = 0; j <= 2; j++)
        fprintf(stderr, "%d  ", constdep[i][j]);
    fprintf(stderr, "\nNbrTestCnst = %d\n", NbrTestCnst);
    fprintf(stderr, "NbrTestGcd = %d\n", NbrTestGcd);
    fprintf(stderr, "NbrTestSimple = %d\n", NbrTestSimple);
    fprintf(stderr, "NbrTestDiCnst = %d\n", NbrTestDiCnst);
    fprintf(stderr, "NbrTestProjEqDi = %d\n", NbrTestProjEqDi);
    fprintf(stderr, "NbrTestProjFMDi = %d\n", NbrTestProjFMDi);
    fprintf(stderr, "NbrTestProjEq = %d\n", NbrTestProjEq);
    fprintf(stderr, "NbrTestProjFM = %d\n", NbrTestProjFM);
    fprintf(stderr, "NbrTestDiVar = %d\n", NbrTestDiVar);
    fprintf(stderr, "NbrProjFMTotal = %d\n", NbrProjFMTotal);
    fprintf(stderr, "NbrFMSystNonAug = %d\n", NbrFMSystNonAug);
    fprintf(stderr, "FMComp[]");
    for (i = 0; i < 18; i++)
      fprintf(stderr, "%d ", FMComp[i]);
  }
  /* write the result to the file correspondant in the order of :
   module,NbrArrayDeptInit,NbrIndeptFind,NbrArrayDepInit,NbrScalDep,
   NbrIndexDep,deptype[5][3]*/
  if(get_bool_property(RICEDG_PROVIDE_STATISTICS))
    writeresult(mod_name);
 
  ifdebug(2) {
    fprintf(stderr, "updated graph\n");
    prettyprint_dependence_graph(stderr, mod_stat, dg);
  }
 
  /* FI: this is not a proper way to do it */
  if(get_bool_property("PRINT_DEPENDENCE_GRAPH") || PRINT_RSDG) {
    dg_name = strdup(concatenate(db_get_current_workspace_directory(),
                                 "/",
                                 mod_name,
                                 ".dg",
                                 NULL));
    fp = safe_fopen(dg_name, "w");
    prettyprint_dependence_graph(fp, mod_stat, dg);
    safe_fclose(fp, dg_name);
  }
 
  debug_off();
 
  DB_PUT_MEMORY_RESOURCE(DBR_DG, mod_name, (char*) dg);
 
  reset_ordering_to_statement();
  reset_current_module_entity();
  reset_current_module_statement();
  reset_precondition_map();
  reset_cumulated_rw_effects();
  clean_enclosing_loops();
 
  return true;
}

References chains(), clean_enclosing_loops(), concatenate(), constdep, copy_graph(), current_shared_obj_table_size(), db_get_current_workspace_directory(), db_get_memory_resource(), DB_PUT_MEMORY_RESOURCE, debug_off, debug_on, deptype, dg, DG_SEMANTICS, dg_type, FMComp, fprintf(), gen_allocated_memory(), get_bool_property(), get_current_module_statement(), graph_consistent_p(), hash_warn_on_redefinition(), ifdebug, local_name_to_top_level_entity(), loops_mapping_of_statement(), mod_stat, module, NbrAllEquals, NbrArrayDepInit, NbrDepCnst, NbrDepInexactEFM, NbrDepInexactEq, NbrDepInexactFM, Nbrdo, NbrFMSystNonAug, NbrIndepFind, NbrIndexDep, NbrProjFMTotal, NbrScalDep, NbrTestCnst, NbrTestDiCnst, NbrTestDiVar, NbrTestExact, NbrTestGcd, NbrTestProjEq, NbrTestProjEqDi, NbrTestProjFM, NbrTestProjFMDi, NbrTestSimple, pips_debug, prettyprint_dependence_graph(), PRINT_RSDG, quick_privatize_graph(), rdg_statement(), reset_cumulated_rw_effects(), reset_current_module_entity(), reset_current_module_statement(), reset_ordering_to_statement(), reset_precondition_map(), ResetLoopCounter(), RICEDG_PROVIDE_STATISTICS, safe_fclose(), safe_fopen(), set_cumulated_rw_effects(), set_current_module_entity(), set_current_module_statement(), set_enclosing_loops_map(), set_ordering_to_statement(), set_precondition_map(), strdup(), and writeresult().

Referenced by rice_fast_dependence_graph(), rice_full_dependence_graph(), rice_regions_dependence_graph(), and rice_semantics_dependence_graph().

Here is the call graph for this function:

Here is the caller graph for this function:

rice_fast_dependence_graph()

bool rice_fast_dependence_graph

(

char *

mod_name

)

Parameters

mod_name

od_name

Definition at line 139 of file ricedg.c.

                                                {
  dg_type = DG_FAST;
  return rice_dependence_graph(mod_name);
}

References DG_FAST, dg_type, and rice_dependence_graph().

Here is the call graph for this function:

rice_full_dependence_graph()

bool rice_full_dependence_graph

(

char *

mod_name

)

Parameters

mod_name

od_name

Definition at line 144 of file ricedg.c.

                                                {
  dg_type = DG_FULL;
  return rice_dependence_graph(mod_name);
}

References DG_FULL, dg_type, and rice_dependence_graph().

Here is the call graph for this function:

rice_regions_dependence_graph()

bool rice_regions_dependence_graph

(

char *

mod_name

)

Parameters

mod_name

od_name

Definition at line 154 of file ricedg.c.

                                                   {
  if(!same_string_p(rule_phase(find_rule_by_resource("CHAINS")),
      "REGION_CHAINS"))
    pips_user_warning("Region chains not selected - using effects instead\n");
 
  dg_type = DG_FAST;
  return rice_dependence_graph(mod_name);
}

References DG_FAST, dg_type, find_rule_by_resource(), pips_user_warning, rice_dependence_graph(), rule_phase, and same_string_p.

Here is the call graph for this function:

rice_semantics_dependence_graph()

bool rice_semantics_dependence_graph

(

char *

mod_name

)

Parameters

mod_name

od_name

Definition at line 149 of file ricedg.c.

                                                     {
  dg_type = DG_SEMANTICS;
  return rice_dependence_graph(mod_name);
}

References DG_SEMANTICS, dg_type, and rice_dependence_graph().

Here is the call graph for this function:

rice_update_dependence_graph()

static void rice_update_dependence_graph ( statement  stat, set  region  )

static

Update of dependence graph.

The update of conflict information is performed for all statements in a loop. This set of statements seems to be defined by "region", while the loop is defined by "stat".

Let v denote a vertex, a an arc, s a statement attached to a vertex and c a conflict, i.e. a pair of effects (e1,e2). Each arc is labelled by a list of statements. Each vertex points to a list of arcs. Each arc points to a list of conflicts. See dg.f.tex and graph.f.tex in Documentation/Newgen for more details.

The procedure is quite complex because:

• each dependence arc carries a list of conflicts; when a conflict is found non-existent, it has to be removed from the conflict list and the arc may also have to be removed from the arc list associated to the current vertex if its associated conflict list becomes empty; removing an element from a list is a pain because you need to know the previous element and to handle the special case of the list first element removal;
• the same conflict may appear twice, once as a def-use conflict and once as a use-def conflicts; since dependence testing may be long, the conflict and its symmetric conflict are processed simultaneously; of course, conflict list and dependence arc updates become tricky,
• especially if the two vertices of the dependence arc are only one: you can have a s1->s1 dependence; thus you might be scanning and updating the very same list of arcs and conflicts twice... but there is a test on pchead and pchead1 to avoid it (pchead and pchead1 points to the heads of the current conflict list and of the conflict list containing the symmetrical conflict); remember, you have no guarantee that s1!=s2 and/or v1=!v2 and/or a1!=a2
• note that there also is a test about symmetry: def-def and use-use conflicts cannot have symmetric conflicts;
• because of the use-def/def-use symmetry, a conflict may already have been processed when it is accessed;
• due to a strange feature in the NewGen declarations, the arcs are called "successors"; variables in the procedure are named with the same convention except... except when they are not; so a so-called "successor" may be either an arc or a vertex (or a statement since each vertex points to a statement)
• you don't know if dg is a graph or a multigraph; apparently it's a multigraph but there is no clear semantics attaches to the different arcs joining a pair of vertices (Pierre Jouvelot, help!)
• conflicts are assumed uniquely identifiable by the addresses of their two effects (and by labelling the same pair of vertices - but not the same arc); that calls for tricky bugs if some sharing between effects exists.

The procedure is made of many too many nested loops and tests:

for all vertex v1 in graph dg if statement s1 associated to v1 in region for all arcs a1 outgoing from v1 let v2 be the sink of a1 and s2 the statement associated to v2 if s2 in region for all conflicts c12 carried by a1 if c12 has not yet been refined if c12 may have a symmetric conflict for all arcs a2 outgoing from the sink v2 of a1 if sink(a2) equals v1 for all conflicts c21 if c21 equal c12 halleluia! compute refined dependence information for c12 and possibly c21 possibly update c21 and possibly remove a2 update c12 and possibly remove a1

Good luck for the restructuring! I'm not sure the current procedure might not end up removing as a2 the very same arc a1 it uses to iterate...

This conflict cone has been updated.

ompute this conflit and the opposite one

ooking for the opposite dependence from (s2,e2) to (s1,e1)

Make sure that you do not try to find the very same conflict: eliminate symmetric conflicts like dd's, and, if the KEEP-READ-READ-DEPENDENCE option is on, the unusual uu's.

&& (reference_indices(effect_any_reference(e1))) != NIL)

if (!Finds2s1) pips_internal_error("Expected opposite dependence are not found");

freed in of leaked.

updating DG for the dependence (s1,e1)-->(s2,e2)

updating DG for the dependence (s2,e2)-->(s1,e1)

en_free(cs2s1);

They are in the same conflicts list

This successor has only one conflict that has been killed.

gen_free_list(dg_arc_label_conflicts(dal));

fdebug(4){ prettyprint_dependence_graph(stderr, mod_stat, dg); }

Definition at line 560 of file ricedg.c.

                                                                     {
  list pv1, ps, pss;
  list llv, llv1;
 
  pips_assert("statement is a loop", statement_loop_p(stat));
 
  pips_debug(1, "Begin\n");
 
  if(dg_type == DG_FULL) {
    pips_debug(1, "computing execution contexts\n");
    set_context_map(contexts_mapping_of_nest(stat));
  }
 
  llv = loop_variant_list(stat);
 
  ifdebug(6) {
    fprintf(stderr, "The list of loop variants is :\n");
    MAP(ENTITY, e, fprintf(stderr," %s", entity_local_name(e)), llv);
    fprintf(stderr, "\n");
  }
 
  for (pv1 = graph_vertices(dg); pv1 != NIL; pv1 = CDR(pv1)) {
    vertex v1 = VERTEX(CAR(pv1));
    dg_vertex_label dvl1 = (dg_vertex_label)vertex_vertex_label(v1);
    statement s1 = vertex_to_statement(v1);
 
    if(!set_belong_p(region, (char *)s1))
      continue;
 
    dg_vertex_label_sccflags(dvl1) = make_sccflags(scc_undefined, 0, 0, 0);
 
    ps = vertex_successors(v1);
    pss = NIL;
    while(ps != NIL) {
      successor su = SUCCESSOR(CAR(ps));
      vertex v2 = successor_vertex(su);
      statement s2 = vertex_to_statement(v2);
      dg_arc_label dal = (dg_arc_label)successor_arc_label(su);
      list true_conflicts = NIL;
      list pc, pchead;
 
      if(!set_belong_p(region, (char *)s2)) {
        pss = ps;
        ps = CDR(ps);
        continue;
      }
 
      pc = dg_arc_label_conflicts(dal);
      pchead = pc;
      while(pc != NIL) {
        conflict c = CONFLICT(CAR(pc));
        effect e1 = conflict_source(c);
        effect e2 = conflict_sink(c);
 
        ifdebug(4) {
          fprintf(stderr, "dep %02td (", statement_number(s1));
          print_words(stderr, words_effect(e1));
          fprintf(stderr, ") --> %02td (", statement_number(s2));
          print_words(stderr, words_effect(e2));
          fprintf(stderr, ") \n");
        }
 
        if(conflict_cone(c) != cone_undefined) {
          /* This conflict cone has been updated. */
          ifdebug(4) {
            fprintf(stderr, " \nThis dependence has been computed.\n");
          }
          true_conflicts = gen_nconc(true_conflicts, CONS(CONFLICT, c, NIL));
        } else { /*Compute this conflit and the opposite one */
          list ps2su = NIL, ps2sus = NIL, pcs2s1 = NIL, pchead1 = NIL;
          successor s2su = successor_undefined;
          vertex v1bis;
          statement s1bis;
          dg_arc_label dals2s1 = dg_arc_label_undefined;
          conflict cs2s1 = conflict_undefined;
          effect e1bis = effect_undefined, e2bis = effect_undefined;
          list levels = list_undefined;
          list levelsop = list_undefined;
          Ptsg gs = SG_UNDEFINED;
          Ptsg gsop = SG_UNDEFINED;
 
          Finds2s1 = false;
 
          /*looking for the opposite dependence from (s2,e2) to
           (s1,e1) */
 
          /* Make sure that you do not try to find the very same
           * conflict: eliminate symmetric conflicts like dd's,
           * and, if the KEEP-READ-READ-DEPENDENCE option is on,
           * the unusual uu's.
           */
          if(!((s1 == s2) && (action_write_p(effect_action(e1)))
              && (action_write_p(effect_action(e2)))) && !((s1 == s2)
              && (action_read_p(effect_action(e1)))
              && (action_read_p(effect_action(e2)))))
          /* && (reference_indices(effect_any_reference(e1))) != NIL) */
          {
            pips_debug (4, "looking for the opposite dependence");
 
            ps2su = vertex_successors(v2);
            ps2sus = NIL;
            while(ps2su != NIL && !Finds2s1) {
              s2su = SUCCESSOR(CAR(ps2su));
              v1bis = successor_vertex(s2su);
              s1bis = vertex_to_statement(v1bis);
              if(s1bis != s1) {
                ps2sus = ps2su;
                ps2su = CDR(ps2su);
                continue;
              } else {
                dals2s1 = (dg_arc_label)successor_arc_label(s2su);
                pcs2s1 = dg_arc_label_conflicts(dals2s1);
                pchead1 = pcs2s1;
                while((pcs2s1 != NIL) && !Finds2s1) {
                  cs2s1 = CONFLICT(CAR(pcs2s1));
                  e1bis = conflict_source(cs2s1);
                  e2bis = conflict_sink(cs2s1);
                  if(e1bis == e2 && e2bis == e1) {
                    Finds2s1 = true;
                    continue;
                  } else {
                    pcs2s1 = CDR(pcs2s1);
                    continue;
                  }
                }
                if(!Finds2s1) {
                  ps2sus = ps2su;
                  ps2su = CDR(ps2su);
                }
                continue;
              }
            }
 
            /* if (!Finds2s1)
             pips_internal_error("Expected opposite dependence are not found"); */
 
            if(Finds2s1) {
              ifdebug(4) {
                fprintf(stderr, "\n dep %02td (", statement_number(s2));
                print_words(stderr, words_effect(e1bis));
                fprintf(stderr, ") --> %02td (", statement_number(s1));
                print_words(stderr, words_effect(e2bis));
                fprintf(stderr, ") \n");
              }
            }
 
          }
 
          llv1 = gen_copy_seq(llv);
          /* freed in of leaked. */
          levels = TestCoupleOfEffects(s1,
                                       e1,
                                       s2,
                                       e2,
                                       llv1,
                                       &gs,
                                       &levelsop,
                                       &gsop);
 
          /* updating DG for the dependence (s1,e1)-->(s2,e2)*/
          if(levels == NIL) {
            debug(4, "", "\nThe dependence (s1,e1)-->(s2,e2)"
              " must be removed. \n");
 
            conflict_source(c) = effect_undefined;
            conflict_sink(c) = effect_undefined;
            free_conflict(c);
          } else {
            debug(4, "", "\nUpdating the dependence (s1,e1)-->(s2,e2)\n");
 
            if(!SG_UNDEFINED_P(gs))
              conflict_cone(c) = make_cone(levels, gs);
            else
              conflict_cone(c) = make_cone(levels, SG_UNDEFINED);
            true_conflicts = gen_nconc(true_conflicts, CONS(CONFLICT, c, NIL));
          }
 
          if(Finds2s1) {
            /* updating DG for the dependence (s2,e2)-->(s1,e1)*/
            if(levelsop == NIL) {
              debug(4, "", "\nThe dependence (s2,e2)-->(s1,e1)"
                " must be removed.\n");
 
              conflict_source(cs2s1) = effect_undefined;
              conflict_sink(cs2s1) = effect_undefined;
              /*gen_free(cs2s1);*/
 
              if(pchead == pchead1)
                /* They are in the same conflicts list */
                gen_remove(&pchead, cs2s1);
              else {
                gen_remove(&pchead1, cs2s1);
                if(pchead1 != NIL) {
                  dg_arc_label_conflicts(dals2s1) = pchead1;
                  successor_arc_label_(s2su) = newgen_arc_label(dals2s1);
                } else {
                  /* This successor has only one
                   conflict that has been killed.*/successor_vertex(s2su)
                      = vertex_undefined;
                  successor_arc_label_(s2su)
                      = (arc_label)dg_arc_label_undefined;
                  free_successor(s2su);
                  ps2su = CDR(ps2su);
                  if(ps2sus == NIL) {
                    vertex_successors(v2) = ps2su;
                  } else {
                    CDR(ps2sus) = ps2su;
                  }
                }
              }
            }
 
            else {
              debug(4, "", "\nUpdating the dependence (s2,e2)-->(s1,e1)\n");
 
              if(!SG_UNDEFINED_P(gsop))
                conflict_cone(cs2s1) = make_cone(levelsop, gsop);
              else
                conflict_cone(cs2s1) = make_cone(levelsop, SG_UNDEFINED);
            }
          }
        }
        pc = CDR(pc);
      }
 
      /* gen_free_list(dg_arc_label_conflicts(dal));*/
      if(true_conflicts != NIL) {
        dg_arc_label_conflicts(dal) = true_conflicts;
        pss = ps;
        ps = CDR(ps);
      } else {
        successor_vertex(su) = vertex_undefined;
        successor_arc_label_(su) = (arc_label)dg_arc_label_undefined;
        free_successor(su);
        ps = CDR(ps);
        if(pss == NIL)
          vertex_successors(v1) = ps;
        else
          CDR(pss) = ps;
      }
      /*ifdebug(4){ prettyprint_dependence_graph(stderr, mod_stat, dg); }*/
    }
  }
 
  ifdebug(8) {
    pips_debug(8,"updated graph\n");
    print_statement_set(stderr, region);
    prettyprint_dependence_graph(stderr, get_current_module_statement(), dg);
  }
 
  reset_context_map();
 
  // No leak
  gen_free_list(llv);
}

References action_read_p, action_write_p, CAR, CDR, cone_undefined, CONFLICT, conflict_cone, conflict_sink, conflict_source, conflict_undefined, CONS, contexts_mapping_of_nest(), debug(), dg, dg_arc_label_conflicts, dg_arc_label_undefined, DG_FULL, dg_type, dg_vertex_label_sccflags, effect_action, effect_undefined, ENTITY, entity_local_name(), Finds2s1, fprintf(), free_conflict(), free_successor(), gen_copy_seq(), gen_free_list(), gen_nconc(), gen_remove(), get_current_module_statement(), graph_vertices, ifdebug, list_undefined, loop_variant_list(), make_cone(), make_sccflags(), MAP, newgen_arc_label, NIL, pips_assert, pips_debug, prettyprint_dependence_graph(), print_statement_set(), print_words(), region, reset_context_map(), s1, scc_undefined, set_belong_p(), set_context_map(), SG_UNDEFINED, SG_UNDEFINED_P, statement_loop_p(), statement_number, SUCCESSOR, successor_arc_label, successor_arc_label_, successor_undefined, successor_vertex, TestCoupleOfEffects(), VERTEX, vertex_successors, vertex_to_statement(), vertex_undefined, vertex_vertex_label, and words_effect().

Referenced by rdg_loop().

Here is the call graph for this function:

Here is the caller graph for this function:

TestCoupleOfEffects()

static list TestCoupleOfEffects ( statement  s1, effect  e1, statement  s2, effect  e2, list  llv, Ptsg *  gs, list *  levelsop, Ptsg *  gsop  )

static

DEPENDENCE TEST

use region information if some is available

This is not correct because loop bounds should be frozen on loop entry; we assume variables used in loop bounds are not too often modified by the loop body

Parameters

s1	1
e1	1
s2	2
e2	2
llv	lv
gs	s
levelsop	evelsop
gsop	sop

Definition at line 821 of file ricedg.c.

                                             {
  list n1 = load_statement_enclosing_loops(s1);
  Psysteme sc1 = SC_UNDEFINED;
  reference r1 = effect_any_reference( e1 );
 
  list n2 = load_statement_enclosing_loops(s2);
  Psysteme sc2 = SC_UNDEFINED;
  reference r2 = effect_any_reference(e2);
 
  switch(dg_type) {
    case DG_FAST: {
      /* use region information if some is available */
      sc1 = effect_system(e1);
      sc2 = effect_system(e2);
      break;
    }
 
    case DG_FULL: {
      sc1 = load_statement_context(s1);
      sc2 = load_statement_context(s2);
      break;
    }
 
    case DG_SEMANTICS: {
      /* This is not correct because loop bounds should be frozen on
       loop entry; we assume variables used in loop bounds are not
       too often modified by the loop body */
      transformer t1 = load_statement_precondition(s1);
      transformer t2 = load_statement_precondition(s2);
 
      sc1 = (Psysteme)predicate_system(transformer_relation(t1));
      sc2 = (Psysteme)predicate_system(transformer_relation(t2));
      break;
    }
 
    default:
      pips_internal_error("Unknown dependence test %d\n", dg_type);
      break;
  }
 
  return TestCoupleOfReferences(n1,
                                sc1,
                                s1,
                                e1,
                                r1,
                                n2,
                                sc2,
                                s2,
                                e2,
                                r2,
                                llv,
                                gs,
                                levelsop,
                                gsop);
}

References DG_FAST, DG_FULL, DG_SEMANTICS, dg_type, effect_any_reference, effect_system, load_statement_context(), load_statement_enclosing_loops(), load_statement_precondition(), pips_internal_error, predicate_system, s1, TestCoupleOfReferences(), and transformer_relation.

Referenced by rice_update_dependence_graph().

Here is the call graph for this function:

Here is the caller graph for this function:

TestCoupleOfReferences()

list TestCoupleOfReferences	(	list	n1,
		Psysteme sc1	__attribute__(unused),
		statement	s1,
		effect	ef1,
		reference	r1,
		list	n2,
		Psysteme sc2	__attribute__(unused),
		statement	s2,
		effect	ef2,
		reference	r2,
		list	llv,
		Ptsg *gs	__attribute__(unused),
		list *levelsop	__attribute__(unused),
		Ptsg *gsop	__attribute__(unused)
	)

if (e1 == e2 && !entity_scalar_p(e1) && !entity_scalar_p(e2))

FI: Why have two tests under the condition e1==e2?

FI: this test must be modified to take pointer dereferencing such as p[i] into account, although p as an entity generates atomic references.

If chains.c were updated, we could also check that: gen_length(b1)==gen_length(b2).

A(*) reference appears in the dependence graph

llv is freed here

test the dependence type, constant dependence?

test the dependence type, constant dependence? exact dependence?

the case of scalar variables and equivalenced arrays

calar variable dependence

ase of scalar variable dependence

Definition at line 905 of file ricedg.c.

                                                                  {
  _int i, cl, dims, ty;
  list levels = NIL, levels1 = NIL;
 
  entity e1 = reference_variable(r1);
  entity e2 = reference_variable(r2);
 
  list b1 = reference_indices(r1);
  list b2 = reference_indices(r2);
 
  type t1 = ultimate_type(entity_type(e1));
 
  if(e1 != e2) {
    ifdebug(1) {
      fprintf(stderr, "dep %02td (", statement_number(s1));
      print_words(stderr, words_effect(ef1));
      fprintf(stderr, ") --> %02td (", statement_number(s2));
      print_words(stderr, words_effect(ef2));
      fprintf(stderr, ") \n");
    }
    pips_user_warning("Dependence between differents variables: "
        "%s and %s\nDependence assumed\n",
        entity_user_name(e1), entity_user_name(e2));
  }
 
  /* if (e1 == e2 && !entity_scalar_p(e1) && !entity_scalar_p(e2)) */
  /* FI: Why have two tests under the condition e1==e2? */
 
  /* FI: this test must be modified to take pointer dereferencing
   * such as p[i] into account, although p as an entity generates
   * atomic references.
   *
   * If chains.c were updated, we could also check that:
   * gen_length(b1)==gen_length(b2).
   */
  if(e1 == e2 && !entity_all_locations_p(e1) && !entity_all_locations_p(e2)
      && (!entity_atomic_reference_p(e1) || (pointer_type_p(t1)
          && gen_length(b1) > 0))) {
    if(get_bool_property("RICEDG_STATISTICS_ALL_ARRAYS")) {
      NbrArrayDepInit++;
    } else {
      if(b1 != NIL && b2 != NIL)
        NbrArrayDepInit++;
    }
 
    if(b1 == NIL || b2 == NIL) {
      /* A(*) reference appears in the dependence graph */
      cl = FindMaximumCommonLevel(n1, n2);
 
      for (i = 1; i <= cl; i++)
        levels = gen_nconc(levels, CONS(INT, i, NIL));
 
      if(statement_possible_less_p(s1, s2))
        levels = gen_nconc(levels, CONS(INT, cl+1, NIL));
 
      if(Finds2s1) {
        for (i = 1; i <= cl; i++)
          levels1 = gen_nconc(levels1, CONS(INT, i, NIL));
 
        if(statement_possible_less_p(s2, s1))
          levels1 = gen_nconc(levels1, CONS(INT, cl+1, NIL));
 
        *levelsop = levels1;
      }
 
      gen_free_list(llv);
    } else {
      /* llv is freed here */
      levels = TestDependence(n1,
                              sc1,
                              s1,
                              ef1,
                              r1,
                              n2,
                              sc2,
                              s2,
                              ef2,
                              r2,
                              llv,
                              gs,
                              levelsop,
                              gsop);
    }
 
    if(get_bool_property("RICEDG_STATISTICS_ALL_ARRAYS") || (b1 != NIL && b2
        != NIL)) {
      if(levels != NIL) {
        /* test the dependence type, constant dependence?  */
        dims = gen_length(b1);
        ty = dep_type(effect_action(ef1), effect_action(ef2));
        deptype[dims][ty]++;
        if(is_dep_cnst) {
          NbrDepCnst++;
          constdep[dims][ty]++;
        }
      }
 
      if(*levelsop != NIL) {
        /* test the dependence type, constant dependence?
         exact dependence? */
        dims = gen_length(b1);
        ty = dep_type(effect_action(ef2), effect_action(ef1));
        deptype[dims][ty]++;
        if(is_dep_cnst) {
          NbrDepCnst++;
          constdep[dims][ty]++;
        }
      }
 
      if(levels != NIL || *levelsop != NIL) {
        if(is_test_exact)
          NbrTestExact++;
        else {
          if(is_test_inexact_eq) {
            if(is_test_inexact_fm)
              NbrDepInexactEFM++;
            else
              NbrDepInexactEq++;
          } else
            NbrDepInexactFM++;
        }
      }
 
      ifdebug(6) {
        if(is_test_exact)
          fprintf(stderr, "\nThis test is exact! \n");
        else if(is_test_inexact_eq)
          fprintf(stderr, "\nTest not exact : "
            "non-exact elimination of equation!");
        else
          fprintf(stderr, "\nTest not exact : "
            "non-exact elimination of F-M!");
      }
    }
 
    return (levels);
  } else {
    /* the case of scalar variables and equivalenced arrays */
 
    // llv is no longer used
    gen_free_list(llv);
 
    cl = FindMaximumCommonLevel(n1, n2);
 
    for (i = 1; i <= cl; i++)
      levels = gen_nconc(levels, CONS(INT, i, NIL));
 
    if(statement_possible_less_p(s1, s2))
      levels = gen_nconc(levels, CONS(INT, cl+1, NIL));
 
    if((instruction_loop_p(statement_instruction(s1)))
        || instruction_loop_p(statement_instruction(s2)))
      NbrIndexDep++;
    else {/*scalar variable dependence */
      NbrScalDep++;
      ty = dep_type(effect_action(ef1), effect_action(ef2));
      deptype[0][ty]++;
    }
 
    if(Finds2s1) {
      for (i = 1; i <= cl; i++)
        levels1 = gen_nconc(levels1, CONS(INT, i, NIL));
 
      if(statement_possible_less_p(s2, s1))
        levels1 = gen_nconc(levels1, CONS(INT, cl+1, NIL));
 
      *levelsop = levels1;
      if((instruction_loop_p(statement_instruction(s1)))
          || instruction_loop_p(statement_instruction(s2)))
        NbrIndexDep++;
      else {/*case of scalar variable dependence */
        NbrScalDep++;
        ty = dep_type(effect_action(ef2), effect_action(ef1));
        deptype[0][ty]++;
      }
    }
 
    return (levels);
  }
}

References b1, b2, CONS, constdep, dep_type(), deptype, effect_action, entity_all_locations_p(), entity_atomic_reference_p(), entity_type, entity_user_name(), FindMaximumCommonLevel(), Finds2s1, fprintf(), gen_free_list(), gen_length(), gen_nconc(), get_bool_property(), ifdebug, instruction_loop_p, INT, is_dep_cnst, is_test_exact, is_test_inexact_eq, is_test_inexact_fm, NbrArrayDepInit, NbrDepCnst, NbrDepInexactEFM, NbrDepInexactEq, NbrDepInexactFM, NbrIndexDep, NbrScalDep, NbrTestExact, NIL, pips_user_warning, pointer_type_p(), print_words(), reference_indices, reference_variable, s1, statement_instruction, statement_number, statement_possible_less_p(), TestDependence(), ultimate_type(), and words_effect().

Referenced by TestCoupleOfEffects().

Here is the call graph for this function:

Here is the caller graph for this function:

TestDependence()

static list TestDependence ( list  n1, Psysteme  sc1, statement  s1, effect  ef1, reference  r1, list  n2, Psysteme  sc2, statement  s2, effect  ef2, reference  r2, list  llv, Ptsg *  gs, list *  levelsop, Ptsg *  gsop  )

static

static list TestDependence(list n1, n2, Psysteme sc1, sc2, statement s1, s2, effect ef1, ef2, reference r1, r2, list llv, list *levelsop, Ptsg *gs,*gsop) input : list n1, n2 : enclosing loops for statements s1 and s2; Psysteme sc1, sc2: current context for each statement; statement s1, s2 : currently analyzed statements; effect ef1, ef2 : effects of each statement upon the current variable; (maybe array regions) reference r1, r2 : current variables references; list llv : loop variant list (variables that vary in loop nests n1 and n2?); list *levelsop : dependence levels from s2 to s1 Ptsg *gs,*gsop : dependence cones from s1 to s2 and from s2 to s1 output : dependence levels from s1 to s2 modifies : levelsop, gsop, gs and returns levels

Comments :

This procedure has been amplified twice. The initial procedure only computed the dependence levels, "levels", for conflict s1->s2. The dependence cone computation was added by Yi-Qing Yang. She later added the computation of the dependence levels and the dependence cone for symetrical conflict, s2 -> s1, because both conflicts share the same dependence system and because a set of tests can be shared.

For her PhD, Yi-Qing Yang also added intermediate tests and instrumentation.

This much too long procedure is made of three parts: 0. The initialization of the dependence system

1. A set of feasibility tests applied to the dependence system
2. The computation of levels and cone for s1->s2
3. The very same computation for s2->s1

Modification :

• ajout des tests de faisabilites pour le systeme initial, avant la projection. Yi-Qing (18/10/91)
• decoupage de la procedure par Beatrice Creusillet
• (indirect) build_and_test_dependence_context(), in fact system, no longer has side effects on sc1 and sc2 thru sc_normalize(); FI (12/12/95)
• sc_rm() uncommented out after call to gcd_and_constant_dependence_test()
• base_rm(tmp_base) added after call to sc_proj_optim_on_di_ofl() just before returning with levels==NIL
• sc_rm() added for dep_syst, dep_syst1, dep_syst_op and dep_syst2

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

Elimination of loop indices from loop variants llv

We use n2 because we take care of variables modified in an iteration only for the second system.

llv is dead, must be freed...

Build the dependence context system from the two initial context systems sc1 and sc2. BC

the context system is not feasible : no dependence. BC

No dep_syst() to deallocate either, FI

Further construction of the dependence system; Constant and GCD tests at the same time.

independence proved

FI: the next statement was commented out...

Consistency Test

find independences (non loop carried dependence, intra-statement).

Such dependences are counted here as independence, but other parallelizer preserve them because they are useful for (assembly) instructon level scheduling

Some kind of arithmetic error, e.g. an integer overflow has occured. Assume dependence to be conservative.

FI: wouldn't it be simpler to enumerate the useful di variables?!?

eliminate non di variables from the basis

Here, the long jump overflow buffer is handled at a lower level!

keep DiIncNonCons variables if their value is unknown or different from zero. Otherwise eliminate them from the dep_syst

FI: I'm lost for this step. My guess DiIncNonCons==VECTEUR_NUL in 99.99 % of all cases...

Compute the levels for dependence arc s1 to s2 and of the opposite dependence arc s2 to s1. Also compute the dependence cones if some level exists (FI: shouldn't it be a loop-carried level?).

For both cases, two systems are allocated, one is used to find the dependence levels, the other one to compute the dependence cone.

For s1->s2, dep_syst is used to compute the levels and dep_syst1 the cone.

For s2->s1, dep_syst_op (op==oppposite) is used to find the dependence levels, and dep_syst2 the dependence cone.

Build the dependence system for the opposite arc s2->s1 before dep_syst is modified

Start processing for arc s1->s2

Make a proper copy of dep_syst before it is destroyed to compute dependence levels. The basis must be in a specific order to check lexico-positivity.

Compute dependence levels for s1->s2

dep_syst is unfeasible or almost empty, and now useless

if (levels == NIL) NbrTestDiVar++; Qui l'a enleve', pourquoi ?

If the cone is not feasible, there are no loop-carried dependences. (FI: the cone is strictly positive then...)

This might not havebeen found by the previous test when computing levels.

But the dependence cone construction does not consider non-loop carried dependences; so we can only remove those levels that are smaller than the number of common levels

print results for arc s1->s2

Start the processing for arc s2->s1

if (*levelsop == NIL) NbrTestDiVar++; Pourquoi?

if the cone is not feasible, there are no loop-carried dependences; this was not found by the previous test when computing levels; but the dependence cone construction does not consider non-loop carried dependences; so we can only remove those levels that are smaller than the number of common levels

the case of "all equals" independence at the same statement

Definition at line 1151 of file ricedg.c.

                                        {
  Psysteme dep_syst = SC_UNDEFINED;
  Psysteme dep_syst1 = SC_UNDEFINED;
  Psysteme dep_syst2 = SC_UNDEFINED;
  volatile Psysteme dep_syst_op = SC_UNDEFINED;
  Pbase b, coord;
  /* Automatic variables read in a CATCH block need to be declared volatile as
   * specified by the documentation*/
  Pbase volatile tmp_base;
 
  int l, cl;
  list levels;
  Pvecteur DiIncNonCons = NULL;
 
  /* Elimination of loop indices from loop variants llv */
  /* We use n2 because we take care of variables modified in
   an iteration only for the second system. */
  FOREACH(STATEMENT, s, n2) {
    entity i = loop_index(statement_loop(s));
    gen_remove(&llv,i); /* llv is dead, must be freed... */
  }
 
  ifdebug(6) {
    pips_debug(6, "loop variants after removing loop indices :\n");
    print_arguments(llv);
  }
 
  /* Build the dependence context system from the two initial context systems
   * sc1 and sc2. BC
   */
  if(!build_and_test_dependence_context(r1, r2, sc1, sc2, &dep_syst, llv, n2)) {
    /* the context system is not feasible : no dependence. BC */
    /* No dep_syst() to deallocate either, FI */
    NbrIndepFind++;
    pips_debug(4, "context system not feasible\n");
    *levelsop = NIL;
 
    gen_free_list(llv);
    return NIL;
  }
 
  /* Further construction of the dependence system; Constant and GCD tests
   * at the same time.
   */
 
  // FI: why is dep_syst only weekly consistent here?
  assert(sc_weak_consistent_p(dep_syst));
 
  if(gcd_and_constant_dependence_test(r1, r2, llv, n2, &dep_syst)) {
    /* independence proved */
    /* FI: the next statement was commented out... */
    sc_rm(dep_syst);
    NbrIndepFind++;
    *levelsop = NIL;
 
    gen_free_list(llv);
    return NIL;
  }
 
  pips_assert("The dependence system is consistent", sc_consistent_p(dep_syst));
 
  gen_free_list(llv);
 
  dependence_system_add_lci_and_di(&dep_syst, n1, &DiIncNonCons);
 
  ifdebug(6) {
    fprintf(stderr, "\ninitial system is:\n");
    sc_syst_debug(dep_syst);
  }
 
  pips_assert("The dependence system is consistent", sc_consistent_p(dep_syst));
 
  /* Consistency Test */
  if(sc_empty_p(dep_syst = sc_normalize(dep_syst))) {
    sc_rm(dep_syst);
    NbrTestSimple++;
    NbrIndepFind++;
    pips_debug(4, "initial normalized system not feasible\n");
    *levelsop = NIL;
 
    return (NIL);
  }
 
  cl = FindMaximumCommonLevel(n1, n2);
 
  pips_assert("The dependence system is consistent", sc_consistent_p(dep_syst));
 
  if(TestDiCnst(dep_syst, cl, s1, ef1, s2, ef2) == true) {
    /* find independences (non loop carried dependence, intra-statement).*/
    /* Such dependences are counted here as independence, but other
     * parallelizer preserve them because they are useful for
     * (assembly) instructon level scheduling
     */
    NbrTestDiCnst++;
    NbrIndepFind++;
    pips_debug(4,"\nTestDiCnst succeeded!\n");
    *levelsop = NIL;
 
    return (NIL);
  }
 
  pips_assert("The dependence system is consistent", sc_consistent_p(dep_syst));
 
  is_test_exact = true;
  is_test_inexact_eq = false;
  is_test_inexact_fm = false;
  is_dep_cnst = false;
 
  tmp_base = base_dup(dep_syst->base);
 
  CATCH(overflow_error) {
    /* Some kind of arithmetic error, e.g. an integer overflow
     * has occured. Assume dependence to be conservative.
     */
    Pbase dep_syst_base = BASE_UNDEFINED;
 
    /* FI: wouldn't it be simpler to enumerate the useful di
     * variables?!?
     */
    /* eliminate non di variables from the basis */
    for (coord = tmp_base; !VECTEUR_NUL_P(coord); coord = coord->succ) {
      Variable v = vecteur_var(coord);
      l = DiVarLevel((entity)v);
      if(l <= 0 || l > cl)
        base_add_variable(dep_syst_base, v);
    }
    dep_syst = sc_rn(dep_syst_base);
  } TRY {
    if(sc_proj_optim_on_di_ofl(cl, &dep_syst) == false) {
      pips_debug(4,
          "projected system by sc_proj_optim_on_di() is not feasible\n");
      sc_rm(dep_syst);
      NbrIndepFind++;
      *levelsop = NIL;
 
      UNCATCH(overflow_error);
      base_rm(tmp_base);
      return (NIL);
    } else
      UNCATCH(overflow_error);
  }
 
  ifdebug(6) {
    fprintf(stderr, "projected system is:\n");
    sc_syst_debug(dep_syst);
  }
 
  pips_assert("The dependence system is consistent", sc_consistent_p(dep_syst));
 
  base_rm(tmp_base); // FI: delayed to help with debugging
 
  if(!sc_faisabilite_optim(dep_syst)) {
    /* Here, the long jump overflow buffer is handled at a lower level! */pips_debug(4, "projected system not feasible\n");
    NbrIndepFind++;
    *levelsop = NIL;
 
    return (NIL);
  }
 
  ifdebug(6) {
    fprintf(stderr, "normalised projected system is:\n");
    sc_syst_debug(dep_syst);
    fprintf(stderr, "The list of DiIncNonCons is :\n");
    vect_debug(DiIncNonCons);
  }
 
  /* keep DiIncNonCons variables if their value is unknown or different
   * from zero. Otherwise eliminate them from the dep_syst
   *
   * FI: I'm lost for this step. My guess DiIncNonCons==VECTEUR_NUL
   * in 99.99 % of all cases...
   */
  if(dep_syst != NULL) {
    while(DiIncNonCons != NULL) {
      Variable di;
      Value val;
 
      di = DiIncNonCons->var;
      if(sc_value_of_variable(dep_syst, di, &val) == true)
        if(value_notzero_p(val)) {
          sc_elim_var(dep_syst, di);
        }
      DiIncNonCons = DiIncNonCons->succ;
    }
  }
 
  ifdebug(4) {
    fprintf(stderr,
            "normalised projected system after DiIncNonCons elimination is:\n");
    sc_syst_debug(dep_syst);
  }
 
  /* Compute the levels for dependence arc s1 to s2 and of the opposite
   * dependence arc s2 to s1. Also compute the dependence cones if some
   * level exists (FI: shouldn't it be a loop-carried level?).
   *
   * For both cases, two systems are allocated, one is used to find the
   * dependence levels, the other one to compute the dependence cone.
   *
   * For s1->s2, dep_syst is used to compute the levels and dep_syst1
   * the cone.
   *
   * For s2->s1, dep_syst_op (op==oppposite) is used to find the dependence
   * levels, and dep_syst2 the dependence cone.
   */
 
  /* Build the dependence system for the opposite arc s2->s1
   * before dep_syst is modified
   */
 
  *levelsop = NIL;
  if(Finds2s1)
    dep_syst_op = sc_invers(sc_dup(dep_syst));
 
  /* Start processing for arc s1->s2 */
 
  ifdebug(4) {
    debug(4, "", "\nComputes the levels and DC for dep: (s1,e1)->(s2,e2)\n");
    fprintf(stderr, "\nThe distance system for dep is:\n");
    sc_syst_debug(dep_syst);
  }
 
  /* Make a proper copy of dep_syst before it is destroyed to compute
   * dependence levels. The basis must be in a specific order to check
   * lexico-positivity.
   */
  dep_syst1 = sc_dup(dep_syst);
  b = MakeDibaseinorder(cl);
  base_rm(dep_syst1->base);
  dep_syst1->base = b;
  dep_syst1->dimension = cl;
 
  if(dep_syst1->dimension == dep_syst1->nb_eq)
    is_dep_cnst = true;
 
  /* Compute dependence levels for s1->s2 */
  levels = TestDiVariables(dep_syst, cl, s1, ef1, s2, ef2);
  /* dep_syst is unfeasible or almost empty, and now useless */
  sc_rm(dep_syst);
 
  /* if (levels == NIL) NbrTestDiVar++;  Qui l'a enleve', pourquoi ? */
 
  if(levels != NIL) {
 
    *gs = dependence_cone_positive(dep_syst1);
 
    /* If the cone is not feasible, there are no loop-carried dependences.
     * (FI: the cone is strictly positive then...)
     *
     * This might not havebeen found by the previous test when computing
     * levels.
     *
     * But the dependence cone construction does not consider non-loop
     * carried dependences; so we can only remove those levels that are
     * smaller than the number of common levels
     */
    if(sg_empty(*gs)) {
      list l_tmp = levels;
      bool ok = false;
 
      pips_debug(5, "dependence cone not feasible\n");
      MAP(INT, ll, {if (ll == cl+1) ok = true;}, l_tmp);
 
      if(ok) {
        pips_debug(5, "innermost level found and kept\n");
        levels = CONS(INT, cl+1, NIL);
      } else {
        pips_debug(5, "innermost level not found, no dependences");
        levels = NIL;
      }
      gen_free_list(l_tmp);
      sg_rm(*gs);
      *gs = SG_UNDEFINED;
    }
  }
  sc_rm(dep_syst1);
 
  /* print results for arc s1->s2 */
 
  ifdebug(4) {
    fprintf(stderr, "\nThe levels for dep (s1,s2) are:");
    MAP(INT, pl,
        {
          fprintf(stderr, " %d", pl);
        }, levels);
 
    if(!SG_UNDEFINED_P(*gs)) {
      fprintf(stderr, "\nThe lexico-positive dependence cone for"
        " dep (s1,s2) :\n");
      print_dependence_cone(stderr, *gs, b);
    } else
      fprintf(stderr, "\nLexico-positive dependence cone"
        " doesn't exist for dep (s1,s2).\n");
  }
 
  /* Start the processing for arc s2->s1 */
 
  if(Finds2s1) {
 
    pips_debug(4,"Computes the levels and DC for dep_op: (s2,e2)->(s1,e1)\n");
    ifdebug(4) {
      fprintf(stderr, "\nThe invers distance system for dep_op is:\n");
      sc_syst_debug(dep_syst_op);
    }
 
    dep_syst2 = sc_dup(dep_syst_op);
    b = MakeDibaseinorder(cl);
    base_rm(dep_syst2->base);
    dep_syst2->base = b;
    dep_syst2->dimension = cl;
 
    *levelsop = TestDiVariables(dep_syst_op, cl, s2, ef2, s1, ef1);
    sc_rm(dep_syst_op);
    if(*levelsop != NIL) {
      /* if (*levelsop == NIL) NbrTestDiVar++;  Pourquoi? */
      *gsop = dependence_cone_positive(dep_syst2);
      sc_rm(dep_syst2);
 
      /* if the cone is not feasible, there are no loop-carried dependences;
       * this was not found by the previous test when computing levels;
       * but the dependence cone construction does not consider non-loop
       * carried dependences; so we can only remove those levels that are
       * smaller than the number of common levels
       */
      if(sg_empty(*gsop)) {
        list l_tmp = *levelsop;
        bool ok = false;
 
        MAP(INT, ll, {if (ll == cl+1) ok = true;}, l_tmp);
 
        if(ok) {
          *levelsop = CONS(INT, cl+1, NIL);
        } else {
          *levelsop = NIL;
        }
        gen_free_list(l_tmp);
        sg_rm(*gsop);
        *gsop = SG_UNDEFINED;
      }
    }
 
    ifdebug(4) {
      fprintf(stderr, "\nThe levels for dep_op (s2,s1) is:");
      MAP(INT, pl,
          {
            fprintf(stderr, " %d", pl);
          }, *levelsop);
 
      if(!SG_UNDEFINED_P(*gsop)) {
        fprintf(stderr, "\nThe lexico-positive Dependence "
          "cone for dep_op (s2,s1):\n");
        print_dependence_cone(stderr, *gsop, b);
      } else
        fprintf(stderr, "\nLexico-positive dependence cone "
          "does not exist for dep_op (s2,s1).\n");
 
    }
  }
 
  if(levels == NIL && *levelsop == NIL) {
    NbrTestDiVar++;
    NbrIndepFind++;
    if(s1 == s2) {
      /* the case of "all equals" independence at the same statement*/
      NbrAllEquals++;
    }
 
    return (NIL);
  }
 
  return (levels);
}

References assert, Ssysteme::base, base_add_variable(), base_dup(), base_rm, BASE_UNDEFINED, build_and_test_dependence_context(), CATCH, CONS, debug(), dependence_cone_positive(), dependence_system_add_lci_and_di(), Ssysteme::dimension, DiVarLevel(), FindMaximumCommonLevel(), Finds2s1, FOREACH, fprintf(), gcd_and_constant_dependence_test(), gen_free_list(), gen_remove(), ifdebug, INT, is_dep_cnst, is_test_exact, is_test_inexact_eq, is_test_inexact_fm, loop_index, MakeDibaseinorder(), MAP, Ssysteme::nb_eq, NbrAllEquals, NbrIndepFind, NbrTestDiCnst, NbrTestDiVar, NbrTestSimple, NIL, ok, overflow_error, pips_assert, pips_debug, pl, print_arguments(), print_dependence_cone(), s1, sc_consistent_p(), sc_dup(), sc_elim_var(), sc_empty_p(), sc_faisabilite_optim(), sc_invers(), sc_normalize(), sc_proj_optim_on_di_ofl(), sc_rm(), sc_rn(), sc_syst_debug(), sc_value_of_variable(), sc_weak_consistent_p(), sg_empty, sg_rm(), SG_UNDEFINED, SG_UNDEFINED_P, STATEMENT, statement_loop(), Svecteur::succ, TestDiCnst(), TestDiVariables(), TRY, UNCATCH, value_notzero_p, Svecteur::var, vect_debug(), VECTEUR_NUL_P, and vecteur_var.

Referenced by TestCoupleOfReferences().

Here is the call graph for this function:

Here is the caller graph for this function:

TestDiCnst() [1/2]

static bool TestDiCnst ( Psysteme  ps, int  cl, statement  s1, effect ef1   __attribute__(unused), statement  s2, effect ef2   __attribute__(unused)  )

static

this function detects intra-statement, non loop carried dependence ( Di=(0,0,...0) and s1 = s2).

case of di zero

Definition at line 2231 of file ricedg.c.

                                                            {
  int l;
 
  for (l = 1; l <= cl; l++) {
    Variable di = (Variable)GetDiVar(l);
    Psysteme pss;
    Value val;
    bool success_p = true;
 
    pss = sc_dup(ps);
    success_p = sc_value_of_variable(pss, di, &val);
    sc_rm(pss);
 
    if(success_p) {
      if(value_notzero_p(val)) {
        return (false);
      }
    } else {
      return (false);
    }
  }
 
  /* case of di zero */
  if(s1 == s2) {
    NbrAllEquals++;
    return (true);
  } else
    return (false);
}

References GetDiVar(), NbrAllEquals, s1, sc_dup(), sc_rm(), sc_value_of_variable(), and value_notzero_p.

Here is the call graph for this function:

TestDiCnst() [2/2]

static bool TestDiCnst ( Psysteme  , int  , statement  , effect  , statement  , effect    )

static

Referenced by TestDependence().

Here is the caller graph for this function:

TestDiVariables() [1/2]

static list TestDiVariables ( Psysteme  ps, int  cl, statement  s1, effect ef1   __attribute__(unused), statement  s2, effect ef2   __attribute__(unused)  )

static

FI: Keep a consistent interface in memory allocation

Psysteme pss = (l==cl) ? ps : sc_dup(ps);

This function does not test feasibility and does not deallocate ps

If there is no dependence at a common loop level: since the system is feasible, it can be a dependence at the innermost level (inside the common loop nest).

WARNING:

If the source and target statements are identical, we do not add the innermost level because the parallelization phase (rice) does not appreciate. In order to be correct, we should add this level 1) because the statement may be a call to an external routine, in which case we cannot be sure that all the writes are performed before the reads and 2) even in the case of a single assignement, the generated code must preserve the order of the write and read memory operations. BC.

Definition at line 1997 of file ricedg.c.

                                                                 {
  list levels = NIL;
  _int l;
  bool all_level_founds = false;
 
  pips_debug(7, "maximum common level (cl): %d\n", cl);
 
  for (l = 1; !all_level_founds && l <= cl; l++) {
    Variable di = (Variable)GetDiVar(l);
    Value min, max;
    int IsPositif, IsNegatif, IsNull, NotPositif;
    /* FI: Keep a consistent interface in memory allocation */
    /* Psysteme pss = (l==cl) ? ps : sc_dup(ps); */
    Psysteme pss = sc_dup(ps);
 
    ifdebug(7) {
      pips_debug(7, "current level: %td, variable: %s\n",
          l, entity_local_name((entity) di));
    }
 
    if(sc_minmax_of_variable_optim(pss, di, &min, &max) == false) {
      pips_debug(7,"sc_minmax_of_variable_optim: non feasible system\n");
      all_level_founds = true;
      break;
    }
 
    IsPositif = value_pos_p(min);
    IsNegatif = value_neg_p(max);
    IsNull = value_zero_p(min) && value_zero_p(max);
    NotPositif = value_zero_p(max) && value_neg_p(min);
 
    ifdebug(7) {
      pips_debug(7, "values: ");
      fprint_string_Value(stderr, "min = ", min);
      fprint_string_Value(stderr, "  max = ", max);
      fprintf(stderr,
              "  ==> %s\n",
              IsPositif ? "positive" : (IsNegatif ? "negative"
                                                  : (IsNull ? "null"
                                                            : "undefined")));
    }
 
    if(IsNegatif) {
      all_level_founds = true;
      break;
    }
 
    if(IsPositif) {
      pips_debug(7, "adding level %td\n", l);
      levels = gen_nconc(levels, CONS(INT, l, NIL));
      all_level_founds = true;
      break;
    }
 
    if(!IsNull && !NotPositif) {
      pips_debug(7, "adding level %td\n", l);
      levels = gen_nconc(levels, CONS(INT, l, NIL));
    }
 
    if(!all_level_founds && l <= cl - 1) {
      pips_debug(7, "forcing variable %s to 0 (l < cl)\n",
          entity_local_name((entity) di));
      /* This function does not test feasibility and does not
       * deallocate ps
       */
      sc_force_variable_to_zero(ps, di);
    }
  }
 
  /* If there is no dependence at a common loop level: since the system
   * is feasible, it can be a dependence at the innermost level (inside the
   * common loop nest).
   *
   * WARNING:
   *
   * If the source and target statements are identical, we do not
   * add the innermost level because the parallelization phase
   * (rice) does not appreciate.  In order to be correct, we should
   * add this level 1) because the statement may be a call to an
   * external routine, in which case we cannot be sure that all the
   * writes are performed before the reads and 2) even in the case
   * of a single assignement, the generated code must preserve the
   * order of the write and read memory operations. BC.
   */
  if(!all_level_founds && s1 != s2 && statement_possible_less_p(s1, s2)) {
    pips_debug(7, "adding innermost level %td\n", l);
    levels = gen_nconc(levels, CONS(INT, l, NIL));
  }
 
  return (levels);
}

References CONS, entity_local_name(), fprint_string_Value(), fprintf(), gen_nconc(), GetDiVar(), ifdebug, INT, max, min, NIL, pips_debug, s1, sc_dup(), sc_force_variable_to_zero(), sc_minmax_of_variable_optim(), statement_possible_less_p(), value_neg_p, value_pos_p, and value_zero_p.

Here is the call graph for this function:

TestDiVariables() [2/2]

static list TestDiVariables ( Psysteme  , int  , statement  , effect  , statement  , effect    )

static

Referenced by TestDependence().

Here is the caller graph for this function:

writeresult()

void writeresult

(

char *

mod_name

)

to avoid warnings from compiler

Parameters

mod_name

od_name

Definition at line 2268 of file ricedg.c.

                                 {
  FILE *fp;
  string filename;
  int i, j;
 
  switch(dg_type) {
    case DG_FAST:
      filename = "resulttestfast";
      break;
    case DG_FULL:
      filename = "resulttestfull";
      break;
    case DG_SEMANTICS:
      filename = "resulttestseman";
      break;
    default:
      pips_internal_error("erroneous dg type.");
      return; /* to avoid warnings from compiler */
  }
 
  filename = strdup(concatenate(db_get_current_workspace_directory(),
                                "/",
                                mod_name,
                                ".",
                                filename,
                                0));
 
  fp = safe_fopen(filename, "w");
 
  fprintf(fp, "%s", mod_name);
  fprintf(fp,
          " %d %d %d %d %d %d %d %d %d %d",
          NbrArrayDepInit,
          NbrIndepFind,
          NbrAllEquals,
          NbrDepCnst,
          NbrTestExact,
          NbrDepInexactEq,
          NbrDepInexactFM,
          NbrDepInexactEFM,
          NbrScalDep,
          NbrIndexDep);
  for (i = 0; i <= 4; i++)
    for (j = 0; j <= 2; j++)
      fprintf(fp, " %d", deptype[i][j]);
  for (i = 0; i <= 4; i++)
    for (j = 0; j <= 2; j++)
      fprintf(fp, " %d", constdep[i][j]);
  fprintf(fp,
          " %d %d %d %d %d %d %d %d %d %d %d",
          NbrTestCnst,
          NbrTestGcd,
          NbrTestSimple,
          NbrTestDiCnst,
          NbrTestProjEqDi,
          NbrTestProjFMDi,
          NbrTestProjEq,
          NbrTestProjFM,
          NbrTestDiVar,
          NbrProjFMTotal,
          NbrFMSystNonAug);
  for (i = 0; i < 18; i++)
    fprintf(fp, " %d", FMComp[i]);
  fprintf(fp, "\n");
 
  safe_fclose(fp, filename);
  free(filename);
}

References concatenate(), constdep, db_get_current_workspace_directory(), deptype, DG_FAST, DG_FULL, DG_SEMANTICS, dg_type, FMComp, fprintf(), free(), NbrAllEquals, NbrArrayDepInit, NbrDepCnst, NbrDepInexactEFM, NbrDepInexactEq, NbrDepInexactFM, NbrFMSystNonAug, NbrIndepFind, NbrIndexDep, NbrProjFMTotal, NbrScalDep, NbrTestCnst, NbrTestDiCnst, NbrTestDiVar, NbrTestExact, NbrTestGcd, NbrTestProjEq, NbrTestProjEqDi, NbrTestProjFM, NbrTestProjFMDi, NbrTestSimple, pips_internal_error, safe_fclose(), safe_fopen(), and strdup().

Referenced by rice_dependence_graph().

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

constdep

int constdep[5][3]

Definition at line 74 of file ricedg.c.

Referenced by compute_dg_on_statement_from_chains_in_place(), rice_dependence_graph(), TestCoupleOfReferences(), and writeresult().

deptype

int deptype[5][3]

Definition at line 74 of file ricedg.c.

Referenced by compute_dg_on_statement_from_chains_in_place(), rice_dependence_graph(), TestCoupleOfReferences(), and writeresult().

dg

graph dg

static

to map statements to enclosing loops

DEFINE_CURRENT_MAPPING(loops, list) now defined in ri-util, BA, September 1993 the dependence graph being updated

Definition at line 110 of file ricedg.c.

Referenced by compute_dg_on_statement_from_chains(), compute_dg_on_statement_from_chains_in_place(), rice_dependence_graph(), and rice_update_dependence_graph().

dg_type

int dg_type = DG_FAST

static

Definition at line 128 of file ricedg.c.

Referenced by compute_dg_on_statement_from_chains_in_place(), rice_dependence_graph(), rice_fast_dependence_graph(), rice_full_dependence_graph(), rice_regions_dependence_graph(), rice_semantics_dependence_graph(), rice_update_dependence_graph(), TestCoupleOfEffects(), and writeresult().

Finds2s1

bool Finds2s1

Definition at line 97 of file ricedg.c.

Referenced by rice_update_dependence_graph(), TestCoupleOfReferences(), and TestDependence().

FMComp

int FMComp[18]

Definition at line 86 of file ricedg.c.

Referenced by combiner_ofl_with_test(), rice_dependence_graph(), and writeresult().

is_dep_cnst

bool is_dep_cnst = false

Definition at line 95 of file ricedg.c.

Referenced by TestCoupleOfReferences(), and TestDependence().

is_test_Di

bool is_test_Di

Definition at line 96 of file ricedg.c.

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

is_test_exact

bool is_test_exact = true

or counting the number of F-M complexity less than 16.

The complexity of one projection by F-M is multiply of the nbr. of inequations positive and the nbr. of inequations negatives who containe the variable eliminated.The last elem of the array (ie FMComp[17]) is used to count cases with complexity over 16

Definition at line 92 of file ricedg.c.

Referenced by combiner_ofl_with_test(), sc_projection_optim_along_vecteur_ofl(), TestCoupleOfReferences(), and TestDependence().

is_test_inexact_eq

bool is_test_inexact_eq = false

Definition at line 93 of file ricedg.c.

Referenced by sc_projection_optim_along_vecteur_ofl(), TestCoupleOfReferences(), and TestDependence().

is_test_inexact_fm

bool is_test_inexact_fm = false

Definition at line 94 of file ricedg.c.

Referenced by combiner_ofl_with_test(), TestCoupleOfReferences(), and TestDependence().

NbrAllEquals

int NbrAllEquals = 0

Definition at line 66 of file ricedg.c.

Referenced by rice_dependence_graph(), TestDependence(), TestDiCnst(), and writeresult().

NbrArrayDepInit

int NbrArrayDepInit = 0

Dependence Graph computation for Allen & Kennedy algorithm.

he variables for the statistics of test of dependence and parallelization

Remi Triolet, Yi-qing Yang

Modifications:

• new option to use semantics analysis results (Francois Irigoin, 12 April 1991)
• compute the dependence cone, the statistics. (Yi-Qing, August 1991)
• updated using DEFINE_CURRENT_MAPPING, BA, September 3, 1993
• dg_type introduced to replace dg_fast and dg_semantics; it is more general. (BC, August 1995).
• TestDependence split into different procedures for more readability. (BC, August 1995).
• creation of quick_privatize.c and prettyprint.c to reduce the size of ricedg.c (FI, Oct. 1995)

Notes:

• Many values seem to be assigned to StatementToContext and never be freed; local variables he variables for the statistics of test of dependence and parallelization they should not be global ? FC.

Definition at line 64 of file ricedg.c.

Referenced by rice_dependence_graph(), TestCoupleOfReferences(), and writeresult().

NbrDepCnst

int NbrDepCnst = 0

Definition at line 67 of file ricedg.c.

Referenced by rice_dependence_graph(), TestCoupleOfReferences(), and writeresult().

NbrDepInexactEFM

int NbrDepInexactEFM = 0

Definition at line 71 of file ricedg.c.

Referenced by rice_dependence_graph(), TestCoupleOfReferences(), and writeresult().

NbrDepInexactEq

int NbrDepInexactEq = 0

Definition at line 69 of file ricedg.c.

Referenced by rice_dependence_graph(), TestCoupleOfReferences(), and writeresult().

NbrDepInexactFM

int NbrDepInexactFM = 0

Definition at line 70 of file ricedg.c.

Referenced by rice_dependence_graph(), TestCoupleOfReferences(), and writeresult().

NbrFMSystNonAug

int NbrFMSystNonAug = 0

Definition at line 85 of file ricedg.c.

Referenced by rice_dependence_graph(), sc_projection_optim_along_vecteur_ofl(), and writeresult().

NbrIndepFind

int NbrIndepFind = 0

Definition at line 65 of file ricedg.c.

Referenced by rice_dependence_graph(), TestDependence(), and writeresult().

NbrIndexDep

int NbrIndexDep = 0

Definition at line 73 of file ricedg.c.

Referenced by rice_dependence_graph(), TestCoupleOfReferences(), and writeresult().

NbrProjFMTotal

int NbrProjFMTotal = 0

Definition at line 84 of file ricedg.c.

Referenced by rice_dependence_graph(), sc_projection_optim_along_vecteur_ofl(), and writeresult().

NbrScalDep

int NbrScalDep = 0

Definition at line 72 of file ricedg.c.

Referenced by rice_dependence_graph(), TestCoupleOfReferences(), and writeresult().

NbrTestCnst

int NbrTestCnst = 0

Definition at line 75 of file ricedg.c.

Referenced by gcd_and_constant_dependence_test(), rice_dependence_graph(), and writeresult().

NbrTestDiCnst

int NbrTestDiCnst = 0

by sc_normalize()

Definition at line 78 of file ricedg.c.

Referenced by rice_dependence_graph(), TestDependence(), and writeresult().

NbrTestDiVar

int NbrTestDiVar = 0

Definition at line 83 of file ricedg.c.

Referenced by rice_dependence_graph(), TestDependence(), and writeresult().

NbrTestExact

int NbrTestExact = 0

Definition at line 68 of file ricedg.c.

Referenced by rice_dependence_graph(), TestCoupleOfReferences(), and writeresult().

NbrTestGcd

int NbrTestGcd = 0

Definition at line 76 of file ricedg.c.

Referenced by gcd_and_constant_dependence_test(), rice_dependence_graph(), and writeresult().

NbrTestProjEq

int NbrTestProjEq = 0

Definition at line 81 of file ricedg.c.

Referenced by rice_dependence_graph(), sc_projection_optim_along_vecteur_ofl(), and writeresult().

NbrTestProjEqDi

int NbrTestProjEqDi = 0

Definition at line 79 of file ricedg.c.

Referenced by rice_dependence_graph(), sc_projection_optim_along_vecteur_ofl(), and writeresult().

NbrTestProjFM

int NbrTestProjFM = 0

Definition at line 82 of file ricedg.c.

Referenced by rice_dependence_graph(), sc_projection_optim_along_vecteur_ofl(), and writeresult().

NbrTestProjFMDi

int NbrTestProjFMDi = 0

Definition at line 80 of file ricedg.c.

Referenced by rice_dependence_graph(), sc_projection_optim_along_vecteur_ofl(), and writeresult().

NbrTestSimple

int NbrTestSimple = 0

Definition at line 77 of file ricedg.c.

Referenced by rice_dependence_graph(), TestDependence(), and writeresult().

PRINT_RSDG

bool PRINT_RSDG = false

static

Definition at line 112 of file ricedg.c.

Referenced by rice_dependence_graph().