sc_intersection.c File Reference

#include <stdlib.h>
#include <string.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_intersection.c:

Go to the source code of this file.

Functions
Psysteme	sc_fusion (Psysteme s1, Psysteme s2)
	package sc More...
Psysteme	sc_intersection (Psysteme s1, Psysteme s2, Psysteme s3)
	Psysteme sc_intersection(Psysteme s1, Psysteme s2, Psysteme s3): calcul d'un systeme de contraintes s1 representant l'intersection des polyedres convexes definis par les systemes de contraintes s2 et s3. More...
Psysteme	sc_append (Psysteme s1, Psysteme s2)
	Psysteme sc_append(Psysteme s1, Psysteme s2): calcul de l'intersection des polyedres definis par s1 et par s2 sous forme d'un systeme de contraintes et renvoi de s1. More...
Psysteme	sc_safe_intersection (Psysteme s1, Psysteme s2, Psysteme s3)
	Psysteme sc_safe_intersection(Psysteme s1, Psysteme s2, Psysteme s3) input : output : calcul d'un systeme de contraintes s1 representant l'intersection des polyedres convexes definis par les systemes de contraintes s2 et s3. More...
Psysteme	sc_safe_append (Psysteme s1, Psysteme s2)
	Psysteme sc_safe_append(Psysteme s1, Psysteme s2) input : output : calcul de l'intersection des polyedres definis par s1 et par s2 sous forme d'un systeme de contraintes et renvoi de s1. More...
bool	sc_intersection_empty_p_ofl (Psysteme ps1, Psysteme ps2)
	bool sc_intersection_empty_p_ofl(ps1, ps2) input : two polyhedra output : true if their intersection is empty, false otherwise. More...
Psysteme	extract_common_syst (Psysteme s1, Psysteme s2)
	returns the common subsystem if appropriate... More...

Function Documentation

extract_common_syst()

Psysteme extract_common_syst	(	Psysteme	s1,
		Psysteme	s2
	)

returns the common subsystem if appropriate...

s1 and s2 are modified accordingly.

Definition at line 335 of file sc_intersection.c.

{
  Pcontrainte 
    e = extract_common_constraints(&s1->egalites, &s2->egalites, true),
    i = extract_common_constraints(&s1->inegalites, &s2->inegalites, false);
 
  sc_fix(s1);
  sc_fix(s2);
 
  return sc_make(e, i);
}

References Ssysteme::egalites, extract_common_constraints(), Ssysteme::inegalites, s1, sc_fix(), and sc_make().

Referenced by sc_cute_convex_hull().

Here is the call graph for this function:

Here is the caller graph for this function:

sc_append()

Psysteme sc_append	(	Psysteme	s1,
		Psysteme	s2
	)

Psysteme sc_append(Psysteme s1, Psysteme s2): calcul de l'intersection des polyedres definis par s1 et par s2 sous forme d'un systeme de contraintes et renvoi de s1.

s1 := intersection(s1,s2) return s1;

Attention, SC_RN est un element neutre et SC_EMPTY un element absorbant. SC_UNDEFINED devrait aussi etre teste proprement.

Modifications:

• mise a jour de la base de s1 (FI, 2/1/90)

ne rien faire et renvoyer s2

ne rien faire et renvoyer s1

ne rien faire et renvoyer s1

on ne devrait jamais passer la dans le futur proche car SC_EMPTY==SC_RN

desallouer s1 et renvoyer SC_EMPTY

ni s1 ni s2 ne sont des systemes particuliers

update s1 basis with s2's vectors

Definition at line 157 of file sc_intersection.c.

{
    Pcontrainte c;
 
    if(SC_RN_P(s1))
        /* ne rien faire et renvoyer s2 */
        s1 = sc_copy(s2);
    else if(SC_RN_P(s2))
        /* ne rien faire et renvoyer s1 */
        ;
    else if(SC_EMPTY_P(s1)) {
        /* ne rien faire et renvoyer s1 */
        /* on ne devrait jamais passer la dans le futur proche car
           SC_EMPTY==SC_RN */
        assert(false);
        ;
    }
    else if(SC_EMPTY_P(s2)) {
        /* desallouer s1 et renvoyer SC_EMPTY */
        assert(false);
        sc_rm(s1);
        s1 = SC_EMPTY;
    }
    else {
 
        /* ni s1 ni s2 ne sont des systemes particuliers */
        for(c = sc_egalites(s2); c != (Pcontrainte) NULL; c = c->succ) {
            sc_add_egalite(s1,contrainte_copy(c));
        }
        for(c = sc_inegalites(s2); c != (Pcontrainte) NULL; c = c->succ) {
            sc_add_inegalite(s1,contrainte_copy(c));
        }
 
        /* update s1 basis with s2's vectors */
        base_append(&s1->base, s2->base);
        s1->dimension = vect_size(s1->base);
    }
 
    return s1;
}

References assert, Ssysteme::base, base_append(), contrainte_copy(), s1, sc_add_egalite(), sc_add_inegalite(), sc_copy(), sc_rm(), Scontrainte::succ, and vect_size().

Referenced by adg_compact_quast(), adg_dataflowgraph(), adg_dataflowgraph_with_extremities(), adg_get_conjonctions(), adg_make_disjunctions(), adg_suppress_2nd_in_1st_ps(), adg_update_dfg(), algorithm_row_echelon_generic(), analyze_quast(), build_list_of_min(), build_third_comb(), build_third_subcomb(), compatible_pc_p(), dataflows_on_reference(), dj_intersection_ofl_ctrl(), edge_weight(), generate_distributed_io_system(), generate_remapping_system(), generate_shared_io_system(), generate_system_for_distributed_variable(), get_unsatisfied_system(), include_results_in_bdt(), interlaced_basic_workchunk_regions_p(), intersect(), make_causal_external(), make_causal_internal(), make_movements_loop_body_wp65(), make_scanning_over_one_tile(), make_scanning_over_tiles(), pa_intersect_system(), parallel_tiling(), prepare_reindexing(), recompute_loop_transformer(), sc_image_computation(), sc_intersection(), sc_projection_concat_proj_on_variables(), search_scc_bdt(), separate_variables(), separate_variables_2(), standard_whileloop_to_transformer(), suppress_sc_in_sc(), tiling_transformation(), transformer_combine(), transformer_general_intersection(), and transformer_intersect_range_with_domain().

Here is the call graph for this function:

Here is the caller graph for this function:

sc_fusion()

Psysteme sc_fusion	(	Psysteme	s1,
		Psysteme	s2
	)

package sc

Psysteme sc_fusion(Psysteme s1, Psysteme s2): fusion de deux systemes de contraintes afin d'obtenir un systeme contenant les egalites et les inegalites des deux systemes donnes; aucune elimination de redondance n'est effectuee.

attention: les deux systemes donnes, s1 et s2, sont detruits.

Note: sc_fusion() est considere comme obsolete; voir sc_intersection() et sc_append().

The base is not updated.

Definition at line 54 of file sc_intersection.c.

{
    Pcontrainte eq;
 
    if (SC_UNDEFINED_P(s1))
      return s2;
 
    if (sc_rn_p(s1)) {
      free(s1);
      return s2;
    }
 
    if (SC_UNDEFINED_P(s2))
      return s1;
 
    if (sc_rn_p(s2)) {
      free(s2);
      return s1;
    }
 
    if (s1->nb_eq != 0)
    {
        for (eq = s1->egalites;
             eq->succ != (Pcontrainte) NULL;
             eq = eq->succ)
            ;
        eq->succ = s2->egalites,
        s1->nb_eq += s2->nb_eq;
    }
    else
        s1->egalites = s2->egalites,
        s1->nb_eq = s2->nb_eq;
 
    if (s1->nb_ineq != 0)
    {
        for (eq = s1->inegalites;
             eq->succ != (Pcontrainte)NULL;
             eq = eq->succ)
            ;
        eq->succ = s2->inegalites,
        s1->nb_ineq += s2->nb_ineq;
    } 
    else 
        s1->inegalites = s2->inegalites,
        s1->nb_ineq = s2->nb_ineq;
 
    s2->inegalites = NULL;
    s2->egalites = NULL;
    sc_rm(s2);
 
    return(s1);
}

References Ssysteme::egalites, eq, free(), Ssysteme::inegalites, Ssysteme::nb_eq, Ssysteme::nb_ineq, s1, sc_rm(), sc_rn_p(), and Scontrainte::succ.

Referenced by build_and_test_dependence_context(), new_loop_bound(), and sc_cute_convex_hull().

Here is the call graph for this function:

Here is the caller graph for this function:

sc_intersection()

Psysteme sc_intersection	(	Psysteme	s1,
		Psysteme	s2,
		Psysteme	s3
	)

Psysteme sc_intersection(Psysteme s1, Psysteme s2, Psysteme s3): calcul d'un systeme de contraintes s1 representant l'intersection des polyedres convexes definis par les systemes de contraintes s2 et s3.

s1 := intersection(s2,s3); return s1;

Les listes d'egalites et d'inegalites de s2 et de s3 sont simplement concatenees. Aucun test de redondance n'est effectuee. Cependant, les valeurs particulieres SC_RN (element neutre) et SC_EMPTY (element absorbant) sont traitees de maniere a donner des resultats corrects.

Attention: le systeme s1 est d'abord vide de ses egalites et inegalites s'il est different de s2 et de s3; sinon, les modifications sont faites en place, sur s2 ou sur s3.

on pourrait se contenter de desallouer les deux listes d'egalites et d'inegalites a condition d'avoir un sc_copy()

Definition at line 124 of file sc_intersection.c.

{
    if(s1==s2) {
        s1 = sc_append(s2,s3);
    }
    else if(s1==s3) {
        s1 = sc_append(s3,s2);
    }
    else {
        if(!SC_EMPTY_P(s1)) {
            /* on pourrait se contenter de desallouer les deux listes
               d'egalites et d'inegalites a condition d'avoir un sc_copy() */
            sc_rm(s1);
        }
        s1 = sc_copy(s2);
        s1 = sc_append(s1,s3);
    }
    return(s1);
}

References s1, sc_append(), sc_copy(), and sc_rm().

Referenced by broadcast_of_dataflow(), contexts_mapping_of_statement(), effects_to_dma(), movement_computation(), parallel_tiling(), and plc_make_distance().

Here is the call graph for this function:

Here is the caller graph for this function:

sc_intersection_empty_p_ofl()

bool sc_intersection_empty_p_ofl	(	Psysteme	ps1,
		Psysteme	ps2
	)

bool sc_intersection_empty_p_ofl(ps1, ps2) input : two polyhedra output : true if their intersection is empty, false otherwise.

modifies : nothing comment : calls sc_faisabilite_ofl in order to trap overflow errors BC, 1994.

Definition at line 316 of file sc_intersection.c.

{
    Psysteme ps = SC_UNDEFINED;
    bool result;
    ps1 = sc_copy(ps1);
    ps2 = sc_copy(ps2);
    ps = sc_safe_intersection(ps,ps1,ps2);
    result = !(sc_faisabilite_ofl(ps));
    sc_rm(ps1);
    sc_rm(ps2);
    sc_rm(ps);
    ps1 = ps2 = ps = NULL;
    return result;
}

References sc_copy(), sc_rm(), and sc_safe_intersection().

Referenced by region_sup_difference().

Here is the call graph for this function:

Here is the caller graph for this function:

sc_safe_append()

Psysteme sc_safe_append	(	Psysteme	s1,
		Psysteme	s2
	)

Psysteme sc_safe_append(Psysteme s1, Psysteme s2) input : output : calcul de l'intersection des polyedres definis par s1 et par s2 sous forme d'un systeme de contraintes et renvoi de s1.

s1 := intersection(s1,s2) return s1; modifies : s1. comment : sc_rn et sc_empty sont traite's de maniere particuliere pour tenir compte de leur se'mantique.

ne rien faire et renvoyer s2 apres mise a jour de la base

ne rien faire et renvoyer s1 apres mise a jour de la base

ne rien faire et renvoyer s1 apres mise a jour de la base

ne rien faire et renvoyer s2 apres mise a jour de la base

ni s1 ni s2 ne sont des systemes particuliers : on ajoute a` s1 les e'galite's et ine'galite's de s2

update s1 basis with s2's vectors

Definition at line 259 of file sc_intersection.c.

{
    Pcontrainte c;
    Pbase b;
    Pvecteur coord;
 
    assert(!SC_UNDEFINED_P(s1) && !SC_UNDEFINED_P(s2));
 
    if(sc_rn_p(s1)) {
        /* ne rien faire et renvoyer s2 apre`s mise a` jour de la base */
        sc_rm(s1);
        s1 = sc_copy(s2);
    }
    else if(sc_rn_p(s2))
        /* ne rien faire et renvoyer s1 apre`s mise a` jour de la base */
        ;
    else if(sc_empty_p(s1))
        /* ne rien faire et renvoyer s1 apre`s mise a` jour de la base */
        ;
    else if(sc_empty_p(s2)) {
        /* ne rien faire et renvoyer s2 apre`s mise a` jour de la base */
        sc_rm(s1);
        s1 = sc_copy(s2);
    }
    else {
        /* ni s1 ni s2 ne sont des systemes particuliers :
         * on ajoute a` s1 les e'galite's et ine'galite's de s2 */
        for(c = sc_egalites(s2); c != (Pcontrainte) NULL; c = c->succ) {
            sc_add_egalite(s1,contrainte_copy(c));
        }
        for(c = sc_inegalites(s2); c != (Pcontrainte) NULL; c = c->succ) {
            sc_add_inegalite(s1,contrainte_copy(c));
        }
    }
 
    /* update s1 basis with s2's vectors */
    b = s1->base;
    for(coord = s2->base; !VECTEUR_NUL_P(coord); coord = coord->succ) {
        Variable v = vecteur_var(coord);
        b = base_add_variable(b, v);
    }
    s1->base = b;
    s1->dimension = vect_size(b);
 
    return(s1);
}

References assert, Ssysteme::base, base_add_variable(), contrainte_copy(), s1, sc_add_egalite(), sc_add_inegalite(), sc_copy(), sc_empty_p(), sc_rm(), sc_rn_p(), Scontrainte::succ, Svecteur::succ, vect_size(), VECTEUR_NUL_P, and vecteur_var.

Referenced by array_must_fully_written_by_regions_p(), do_array_expansion(), loop_regions_normalize(), pa_path_to_few_disjunct_ofl_ctrl(), pa_reduce_simple_complement(), region_translation(), sc_safe_intersection(), sc_strong_normalize2(), and sc_strong_normalize_and_check_feasibility2().

Here is the call graph for this function:

Here is the caller graph for this function:

sc_safe_intersection()

Psysteme sc_safe_intersection	(	Psysteme	s1,
		Psysteme	s2,
		Psysteme	s3
	)

Psysteme sc_safe_intersection(Psysteme s1, Psysteme s2, Psysteme s3) input : output : calcul d'un systeme de contraintes s1 representant l'intersection des polyedres convexes definis par les systemes de contraintes s2 et s3.

s1 := intersection(s2,s3); return s1;

modifies : s1 is modified if it is not undefined. comment :
calcul d'un systeme de contraintes s1 representant l'intersection des polyedres convexes definis par les systemes de contraintes s2 et s3.

Les listes d'egalites et d'inegalites de s2 et de s3 sont simplement concatenees. Aucun test de redondance n'est effectuee. Cependant, les valeurs particulieres sc_rn (element neutre) et sc_empty (element absorbant) sont traitees de maniere a donner des resultats corrects ( different de sc_intercestion).

Attention: le systeme s1 est d'abord vide de ses egalites et inegalites s'il est different de s2 et de s3; sinon, les modifications sont faites en place, sur s2 ou sur s3.

on pourrait se contenter de desallouer les deux listes d'egalites et d'inegalites a condition d'avoir un sc_copy()

Definition at line 224 of file sc_intersection.c.

{
    if(s1==s2) {
        s1 = sc_safe_append(s2,s3);
    }
    else if(s1==s3) {
        s1 = sc_safe_append(s3,s2);
    }
    else {
        if(!SC_UNDEFINED_P(s1)) {
            /* on pourrait se contenter de desallouer les deux listes
               d'egalites et d'inegalites a condition d'avoir un sc_copy() */
            sc_rm(s1);
        }
        s1 = sc_copy(s2);
        s1 = sc_safe_append(s1,s3);
    }
    return(s1);
}

References s1, sc_copy(), sc_rm(), and sc_safe_append().

Referenced by algorithm_tiling(), and sc_intersection_empty_p_ofl().

Here is the call graph for this function:

Here is the caller graph for this function: