sc_new_loop_bound.c File Reference

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

Include dependency graph for sc_new_loop_bound.c:

Go to the source code of this file.

Functions
Psysteme	new_loop_bound (Psysteme scn, Pbase base_index)
	Psysteme new_loop_bound(Psysteme scn, Pbase base_index) computation of the new iteration space (given the loop bounds) in the new basis G. More...
Psysteme	get_other_constraints (Psysteme *psyst, Pbase vars)
	Psysteme get_other_constraints(psyst, vars) Psysteme *psyst; Pbase vars;. More...
void	algorithm_row_echelon_generic (Psysteme scn, Pbase base_index, Psysteme *pcondition, Psysteme *penumeration, bool redundancy)
	each variable should be at least within one <= and one >=; scn IS NOT modified. More...
void	algorithm_row_echelon (Psysteme scn, Pbase base_index, Psysteme *pcondition, Psysteme *penumeration)
	see comments above. More...
void	sc_set_row_echelon_redundancy (bool b __attribute__((unused)))
void	algorithm_tiling (Psysteme syst, Pbase outer, Pbase inner, Psysteme *pcondition, Psysteme *ptile_enum, Psysteme *piter_enum)

Function Documentation

algorithm_row_echelon()

void algorithm_row_echelon	(	Psysteme	scn,
		Pbase	base_index,
		Psysteme *	pcondition,
		Psysteme *	penumeration
	)

see comments above.

Definition at line 248 of file sc_new_loop_bound.c.

{
  algorithm_row_echelon_generic
    (scn, base_index, pcondition, penumeration, false);
}

References algorithm_row_echelon_generic().

Referenced by build_third_comb(), copy_write_statement_with_cumulated_regions(), prepare_reindexing(), and verify_array_variable().

Here is the call graph for this function:

Here is the caller graph for this function:

algorithm_row_echelon_generic()

void algorithm_row_echelon_generic	(	Psysteme	scn,
		Pbase	base_index,
		Psysteme *	pcondition,
		Psysteme *	penumeration,
		bool	redundancy
	)

each variable should be at least within one <= and one >=; scn IS NOT modified.

---

ALGORITHM ROW ECHELON from Ancourt and Irigoin, PPoPP'91

The algorithm is slightly different:

conditions are taken out of the system built.

void algorithm_row_echelon(syst, scans, pcondition, penumeration) Psysteme syst; Pbase scans; Psysteme *pcondition, *penumeration;

IN: syst, scans

OUT: pcondition, penumeration

(c) FC 16/05/94

returns a a la Omega system, with no innerward redundancy. in fact this is just a quick approximation of that property. the way the system is computed may keep some outerward redundancies, because a constraint may be redundant with some not yet computed projection...

ELSE remove redundancy in the system...

include the original system again, to recover simple constraints that may have been removed. May not be interesting...

what is returned must be ok.

Parameters

base_index	initial system, which is not touched.
pcondition	enumeration variables, from outer to inner.
penumeration	returned condition (what remains from scn).
redundancy	returned enumeration system. whether to allow outwards redundancy.

Definition at line 134 of file sc_new_loop_bound.c.

{
  int i, dimension = vect_size(base_index);
  Psysteme ps_interm, ps_project, ps_tmp;
  Pbase reverse_base;
  Pvecteur pb;
  Pcontrainte   ineq = NULL,
    *c = (Pcontrainte*) malloc(sizeof(Pcontrainte)*(dimension+1));
 
  if (VECTEUR_NUL_P(base_index))
  {
    *penumeration = sc_rn(NULL);
    *pcondition = sc_dup(scn);
    return;
  }
 
  // check base consistency
  assert(vect_in_basis_p(base_index, scn->base));
 
  ps_project = sc_dup(scn);
  sc_transform_eg_in_ineg(ps_project);
  ps_project = sc_sort_constraints(ps_project, base_index);
  ps_project = sc_elim_redond(ps_project);
 
  if (SC_UNDEFINED_P(ps_project))
    ps_project = sc_empty(base_difference(sc_base(scn), base_index));
 
  if (sc_empty_p(ps_project))
  {
    *penumeration = sc_empty(base_index);
    *pcondition = ps_project;
    return;
  }
 
  reverse_base = base_reversal(base_index);
 
  for (pb=reverse_base, i=dimension;
       !VECTEUR_NUL_P(pb);
       pb=pb->succ, i--)
  {
    c[i] = contrainte_dup_extract(sc_inegalites(ps_project), pb->var);
 
    ps_project = sc_projection(ps_project, pb->var);
    vect_erase_var(&sc_base(ps_project), pb->var);
    ps_project->dimension--;
    ps_project = sc_triang_elim_redund(ps_project, base_index);
  }
 
  if (ps_project==NULL || sc_empty_p(ps_project))
  {
    *penumeration = sc_empty(base_index);
    *pcondition = ps_project;
    return;
  }
 
  c[0] = contrainte_dup_extract(sc_inegalites(ps_project), NULL);
  sc_rm(ps_project);
 
  for (i=0; i<dimension+1; i++)
    ineq = contrainte_append(c[i], ineq);
 
  ps_interm = sc_make(NULL, ineq);
 
  /* returns a a la Omega system, with no innerward redundancy.
   * in fact this is just a quick approximation of that property.
   * the way the system is computed may keep some outerward redundancies,
   * because a constraint may be redundant with some not yet computed
   * projection...
   */
  if (redundancy)
  {
    *pcondition = get_other_constraints(&ps_interm, base_index);
    sc_transform_ineg_in_eg(*pcondition);
    *penumeration = ps_interm;
 
    return;
  }
 
  /* ELSE remove redundancy in the system...
   *
   * include the original system again, to recover simple
   * constraints that may have been removed.
   * May not be interesting...
   */
  ps_tmp =  sc_dup(scn);
  sc_transform_eg_in_ineg(ps_tmp);
  //assert(sc_consistent_p(ps_tmp));
  //assert(sc_consistent_p(ps_interm));
  // sc_fusion() is declared obsolete: sc_append() and
  // sc_intersection() are suggested as replacements
  //ps_interm = sc_fusion(ps_interm, ps_tmp);
  ps_interm = sc_append(ps_interm, ps_tmp);
  //assert(sc_consistent_p(ps_interm));
  ps_interm = sc_triang_elim_redund(ps_interm, base_index);
 
  *pcondition = get_other_constraints(&ps_interm, base_index);
  sc_transform_ineg_in_eg(*pcondition); 
  *penumeration = ps_interm;
 
  base_rm(reverse_base), free(c);
 
  /*  what is returned must be ok.
   */
  assert(!SC_UNDEFINED_P(*pcondition) && !SC_UNDEFINED_P(*penumeration));
}

References assert, Ssysteme::base, base_difference(), base_reversal(), base_rm, contrainte_append(), contrainte_dup_extract(), Ssysteme::dimension, free(), get_other_constraints(), malloc(), sc_append(), sc_dup(), sc_empty(), sc_empty_p(), sc_make(), sc_rm(), sc_rn(), sc_sort_constraints(), sc_transform_eg_in_ineg(), sc_transform_ineg_in_eg(), sc_triang_elim_redund(), Svecteur::succ, Svecteur::var, vect_erase_var(), vect_in_basis_p(), vect_size(), and VECTEUR_NUL_P.

Referenced by algorithm_row_echelon(), algorithm_tiling(), hpfc_algorithm_row_echelon(), new_loop_bound(), and Psysteme_to_loop_nest().

Here is the call graph for this function:

Here is the caller graph for this function:

algorithm_tiling()

void algorithm_tiling	(	Psysteme	syst,
		Pbase	outer,
		Pbase	inner,
		Psysteme *	pcondition,
		Psysteme *	ptile_enum,
		Psysteme *	piter_enum
	)

---

ALGORITHM TILING from Ancourt and Irigoin, PPoPP'91

The algorithm is slightly different:

constraints may appear thru the projections that do not contain the desired loop variables. These constraints are taken out of the systems. The inner ones are reinjected to help for the outer loop, and those of the outer loop are stored as conditions to be checked before the loop nest. The intuition is that if these constraints are violated, the polyhedron is empty, and the loop nest must be avoided.

Corinne ANCOURT, Fabien COELHO, Apr 1 94.

• may be improved by recognizing equalities? then deducable variables could be rebuilt.
• there should be no equalities on the scanners...

void algorithm_tiling(syst, outer, inner, pcondition, ptile_enum, piter_enum) Psysteme syst; Pbase outer, inner; Psysteme *pcondition, *ptile_enum, *piter_enum;

 IN: syst, outer, inner
OUT: pcondition, ptile_enum, piter_enum

tiles iterations enumeration row echelon

project variables

tiles enumeration row echelon

clean bases

Definition at line 292 of file sc_new_loop_bound.c.

{
  Psysteme sc = SC_UNDEFINED,   transfer = SC_UNDEFINED;
  Pbase b = BASE_NULLE;
 
  /* tiles iterations enumeration row echelon
   */
  algorithm_row_echelon_generic(syst, inner, &transfer, piter_enum, true);
 
  if (sc_empty_p(transfer))
  {
    sc_rm(transfer), sc_rm(*piter_enum),
      *piter_enum = sc_empty(BASE_NULLE),
      *ptile_enum = sc_empty(BASE_NULLE),
      *pcondition = sc_empty(BASE_NULLE);
    return;
  }
 
  /* project variables
   */
  for(b=inner, sc=sc_safe_intersection(sc_rn(BASE_NULLE), syst, transfer);
      b!=BASE_NULLE;
      sc=sc_projection(sc, var_of(b)), b=b->succ);
 
  sc_rm(transfer);
  sc_nredund(&sc);
 
  /* tiles enumeration row echelon
   */
  algorithm_row_echelon_generic(sc, outer, pcondition, ptile_enum, true);
 
  if (sc_empty_p(*pcondition))
  {
    sc_rm(*piter_enum), sc_rm(*ptile_enum),
      *piter_enum = sc_empty(BASE_NULLE),
      *ptile_enum = sc_empty(BASE_NULLE);
    return;
  }
 
  /* clean bases
   */
  sc_base(*ptile_enum)=(base_rm(sc_base(*ptile_enum)), BASE_NULLE),
    sc_creer_base(*ptile_enum);
 
  sc_base(*piter_enum)=(base_rm(sc_base(*piter_enum)), BASE_NULLE),
    sc_creer_base(*piter_enum);
}

References algorithm_row_echelon_generic(), BASE_NULLE, base_rm, sc_creer_base(), sc_empty(), sc_empty_p(), sc_rm(), sc_rn(), sc_safe_intersection(), Svecteur::succ, and var_of.

Referenced by hpfc_algorithm_tiling().

Here is the call graph for this function:

Here is the caller graph for this function:

get_other_constraints()

Psysteme get_other_constraints	(	Psysteme *	psyst,
		Pbase	vars
	)

Psysteme get_other_constraints(psyst, vars) Psysteme *psyst; Pbase vars;.

    IN: vars
IN/OUT: psyst
   OUT: returned system

returns the constraints that do not contain any of the variables listed in Pbase vars, which are removed from the original Psysteme *psyst. if the original system is undefined, the same thing is returned.

(c) FC 16/05/94

else

result in built and syst is modified.

Definition at line 84 of file sc_new_loop_bound.c.

{
  Pcontrainte
    egothers = (Pcontrainte) NULL,
    inothers = (Pcontrainte) NULL,
    egsyst = (Pcontrainte) NULL,
    insyst = (Pcontrainte) NULL;
 
  assert(!SC_UNDEFINED_P(*psyst));
 
  if (sc_empty_p(*psyst))
    return(sc_empty(base_difference(sc_base(*psyst), vars)));
  /* else
   */
  Pcontrainte_separate_on_vars(sc_egalites(*psyst),
                               vars, &egsyst, &egothers);
  Pcontrainte_separate_on_vars(sc_inegalites(*psyst),
                               vars, &insyst, &inothers);
 
  /* result in built and syst is modified.
   */
  *psyst = (sc_rm(*psyst), sc_make(egsyst, insyst));
  return sc_make(egothers, inothers);
}

References assert, base_difference(), Pcontrainte_separate_on_vars(), sc_empty(), sc_empty_p(), sc_make(), and sc_rm().

Referenced by algorithm_row_echelon_generic().

Here is the call graph for this function:

Here is the caller graph for this function:

new_loop_bound()

Psysteme new_loop_bound	(	Psysteme	scn,
		Pbase	base_index
	)

Psysteme new_loop_bound(Psysteme scn, Pbase base_index) computation of the new iteration space (given the loop bounds) in the new basis G.

scn is destroyed

if the list of indexes is empty, the system is assumed to be a list of constraints that have to be verified for the set of solutions not to be empty, so scn is returned.

Reference about the algorithm PPoPP'91

Definition at line 51 of file sc_new_loop_bound.c.

{
  Psysteme
    result = NULL,
    condition = NULL,
    enumeration = NULL;
 
  algorithm_row_echelon_generic(scn, base_index,
                                &condition, &enumeration, false);
 
  sc_rm(scn);
  scn = NULL;
  result = sc_fusion(condition, enumeration);
 
  return result;
}

References algorithm_row_echelon_generic(), sc_fusion(), and sc_rm().

Referenced by hyperplane(), make_scanning_over_one_tile(), make_scanning_over_tiles(), terapix_loop_handler(), tiling_transformation(), and unimodular().

Here is the call graph for this function:

Here is the caller graph for this function:

sc_set_row_echelon_redundancy()

void sc_set_row_echelon_redundancy

(

bool b

__attribute__(unused)

)

Definition at line 258 of file sc_new_loop_bound.c.

{
  return;
}