binary_operators.c File Reference

#include <stdio.h>
#include <string.h>
#include "genC.h"
#include "linear.h"
#include "ri.h"
#include "effects.h"
#include "database.h"
#include "boolean.h"
#include "vecteur.h"
#include "contrainte.h"
#include "sc.h"
#include "sommet.h"
#include "ray_dte.h"
#include "sg.h"
#include "polyedre.h"
#include "union.h"
#include "constants.h"
#include "ri-util.h"
#include "prettyprint.h"
#include "effects-util.h"
#include "pipsdbm.h"
#include "misc.h"
#include "text.h"
#include "effects-generic.h"
#include "effects-convex.h"

Include dependency graph for binary_operators.c:

Go to the source code of this file.

Macros
#define	COMBINE   1
#define	UNUSED   2
#define	SUPER   true
#define	SUB   false

Functions
void	reset_binary_op_statistics ()
	binary_operators.c More...
void	print_umust_statistics (char *mod_name, char *prefix)
void	print_umay_statistics (char *mod_name, char *prefix)
void	print_dsup_statistics (char *mod_name, char *prefix)
void	print_dinf_statistics (char *mod_name, char *prefix)
list	RegionsMayUnion (list l1, list l2, bool(*union_combinable_p)(effect, effect))
	list RegionsMayUnion(list l1, list l2, union_combinable_p) input : two lists of regions output : a list of regions, may union of the two initial lists modifies : l1 and l2 and their regions. More...
list	RegionsMustUnion (list l1, list l2, bool(*union_combinable_p)(effect, effect))
	list RegionsMustUnion(list l1, list l2, union_combinable_p) input : two lists of regions output : a list of regions, must union of the two initial lists modifies : l1 and l2 and their regions. More...
list	RegionsIntersection (list l1, list l2, bool(*intersection_combinable_p)(effect, effect))
	list RegionsIntersection(list l1,l2, bool (*intersection_combinable_p)(effect, effect)) input : output : modifies : comment : More...
list	RegionsEntitiesIntersection (list l1, list l2, bool(*intersection_combinable_p)(effect, effect))
	list RegionsEntitiesIntersection(list l1,l2, bool (*intersection_combinable_p)(effect, effect)) input : two lists of regions output : a list of regions containing all the regions of l1 that have a corresponding region (i.e. More...
list	RegionsSupDifference (list l1, list l2, bool(*difference_combinable_p)(effect, effect))
	list RegionsSupDifference(list l1, l2) input : two lists of regions output : a list of region, representing the sup_difference of the initial regions. More...
list	RegionsInfDifference (list l1, list l2, bool(*difference_combinable_p)(effect, effect))
	list RegionsInfDifference(list l1, l2) input : two lists of regions output : a list of region, representing the inf_difference of the initial regions. More...
list	RegionsEntitiesInfDifference (list l1, list l2, bool(*difference_combinable_p)(effect, effect))
	list RegionsEntitiesInfDifference(list l1, l2) input : two lists of regions output : a list of regions, such that: if there is a region R concerning entity A in l1 and in l2, then R is removed from the result; if there is a region R concerning array A in l1, but not in l2, then it is kept in l1, and in the result. More...
effect	regions_must_convex_hull (region f1, region f2)
	1- Union : More...
static effect	regions_may_convex_hull (region r1, region r2)
	static effect regions_may_convex_hull(region r1,r2) input : two "effect" representing two regions. More...
list	region_must_union (region r1, region r2)
	computes the must union of two combinable array regions More...
list	region_may_union (region r1, region r2)
	computes the may union of two combinable array regions More...
list	region_union (region r1, region r2, bool must_p)
	computes the must or may union of two combinable array regions depending on the value of must_p More...
static Psysteme	region_sc_convex_hull (Psysteme ps1, Psysteme ps2)
	tatic Psysteme region_sc_convex_hull(Psysteme ps1, ps2) input : two systems of constraints output : another system of constraints representing their convex hull. More...
bool	convex_cells_inclusion_p (cell c1, descriptor d1, cell c2, descriptor d2, bool *exact_p)
	Inclusion test : More...
list	region_intersection (region reg1, region reg2)
	Intersection : More...
bool	convex_cells_intersection_p (cell c1, descriptor d1, cell c2, descriptor d2, bool *exact_p)
list	region_entities_intersection (region r1, region r2)
	list region_entities_intersection(region reg1, reg2) input : two regions output : a mere copy of the first region. More...
static list	disjunction_to_list_of_regions (Pdisjunct disjonction, effect reg, tag app, bool super_or_sub)
	3- Difference : More...
list	region_sup_difference (region reg1, region reg2)
	list region_sup_difference(effect reg1, reg2) input : two regions output : a list of regions containing their sup_difference. More...
list	region_inf_difference (region reg1, region reg2)
	list region_inf_difference(region reg1, reg2) input : two regions output : a list of regions containing their inf_difference. More...
static Psysteme	disjunction_to_region_sc (Pdisjunct disjonction, bool *p_exact)
	static Psysteme disjunction_to_region_sc(Pdisjunct disjonction, bool *b) input : a disjunction representing the union of several Psystemes output : a Psysteme representing the convex_hull of the disjunction of predicates. More...
static list	disjunction_to_list_of_regions (Pdisjunct disjonction, region reg, tag app, bool super_or_sub __attribute__((unused)))
	static list disjuction_to_list_of_regions(disjonction, reg, app, super_or_sub) input : a disjunction and a region output : a list of regions which contains a region identical with reg, but for the predicate which is given by the Psystemes of the disjunction and the approximation which depends on the exactness of the representation. More...

Variables
static int	nb_umust = 0
static int	nb_umust_must_must = 0
static int	nb_umust_must_must_must = 0
static int	nb_umust_must_may = 0
static int	nb_umust_must_may_must = 0
static int	nb_umust_sc_rn = 0
static int	nb_umay = 0
static int	nb_umay_must_must = 0
static int	nb_umay_must = 0
static int	nb_dsup = 0
static int	nb_dsup_pot_must = 0
static int	nb_dsup_must = 0
static int	nb_dinf = 0
static int	nb_dinf_pot_must = 0
static int	nb_dinf_must = 0

Macro Definition Documentation

COMBINE

#define COMBINE   1

Definition at line 65 of file binary_operators.c.

SUB

#define SUB   false

Definition at line 69 of file binary_operators.c.

SUPER

#define SUPER   true

Definition at line 68 of file binary_operators.c.

UNUSED

#define UNUSED   2

Definition at line 66 of file binary_operators.c.

Function Documentation

convex_cells_inclusion_p()

bool convex_cells_inclusion_p	(	cell	c1,
		descriptor	d1,
		cell	c2,
		descriptor	d2,
		bool *	exact_p
	)

Inclusion test :

returns true if c1 is included into c2, false otherwise. returns false if c1 may only be included into c2.

Parameters

exact_p

target is set to true if the result is exact, false otherwise.

In fact, this parameter would be useful only if there are overflows during the systems inclusion test. But it is not currently used.

default result

we have combinable concrete locations or assimilated (context sensitive heap locations)

they intersect if their descriptors intersection is not empty

if one of the systems is unfeasible, the result is false and exact

if one of the systems is not constrained, the result is true and exact

Parameters

c1	1
d1	1
c2	2
d2	2
exact_p	xact_p

Definition at line 1015 of file binary_operators.c.

{
  bool res = true; /* default result */
  *exact_p = true;
 
  bool concrete_locations_p = true;
 
  if (cells_combinable_p(c1, c2))
    {
      bool c1_abstract_location_p = cell_abstract_location_p(c1);
      bool c2_abstract_location_p = cell_abstract_location_p(c2);
 
      if (c1_abstract_location_p || c2_abstract_location_p)
        {
          entity e1 = cell_entity(c1);
          entity e2 = cell_entity(c2);
          bool heap1_context_sensitive_p = c1_abstract_location_p && entity_flow_or_context_sentitive_heap_location_p(e1);
          bool heap2_context_sensitive_p = c2_abstract_location_p && entity_flow_or_context_sentitive_heap_location_p(e2);
 
          if (heap1_context_sensitive_p && heap2_context_sensitive_p)
            {
              concrete_locations_p = true;
            }
          else
            {
              entity al_max = abstract_locations_max(e1, e2);
              res = same_entity_p(e2, al_max);
              concrete_locations_p = false;
            }
        }
 
      if (concrete_locations_p)
        {
          /* we have combinable concrete locations or assimilated (context sensitive heap locations) */
          /* they intersect if their descriptors intersection is not empty */
 
          Psysteme sc1 = descriptor_convex(d1);
          Psysteme sc2 = descriptor_convex(d2);
 
          /* if one of the systems is unfeasible, the result is false and exact */
          if (sc_empty_p(sc1) || sc_empty_p(sc2))
            {
              res = false;
            }
          /* if one of the systems is not constrained, the result is true and exact */
          else if (sc_rn_p(sc2))
            {
              res = true;
            }
          else if (sc_rn_p(sc1))
            {
              res = true;
            }
          else
            {
              res = sc_inclusion_p(sc1, sc2);
            }
        }
    }
  else
    {
      res = false;
    }
  return res;
}

References abstract_locations_max(), cell_abstract_location_p(), cell_entity(), cells_combinable_p(), descriptor_convex, entity_flow_or_context_sentitive_heap_location_p(), same_entity_p(), sc_empty_p(), sc_inclusion_p, and sc_rn_p().

Referenced by convex_effect_find_aliased_paths_with_pointer_values().

Here is the call graph for this function:

Here is the caller graph for this function:

convex_cells_intersection_p()

bool convex_cells_intersection_p	(	cell	c1,
		descriptor	d1,
		cell	c2,
		descriptor	d2,
		bool *	exact_p
	)

default safe result

can it be true if we have two null locations ?

we have combinable concrete locations or assimilated (context sensitive heap locations)

they intersect if their descriptors intersection is not empty

if one of the systems is unfeasible, the result is false and exact

if one of the systems is not constrained, the result is true and exact

else test the feasibility of the systems intersection

could be some other level?

Parameters

c1	1
d1	1
c2	2
d2	2
exact_p	xact_p

Definition at line 1201 of file binary_operators.c.

{
  bool res = true;
 
 /* default safe result */
  bool concrete_locations_p = true;
 
  if (cells_combinable_p(c1, c2))
    {
      bool c1_abstract_location_p = cell_abstract_location_p(c1);
      bool c2_abstract_location_p = cell_abstract_location_p(c2);
 
      if (c1_abstract_location_p || c2_abstract_location_p)
        {
          entity e1 = cell_entity(c1);
          entity e2 = cell_entity(c2);
          bool heap1_context_sensitive_p = c1_abstract_location_p && entity_flow_or_context_sentitive_heap_location_p(e1);
          bool heap2_context_sensitive_p = c2_abstract_location_p && entity_flow_or_context_sentitive_heap_location_p(e2);
 
          if (heap1_context_sensitive_p && heap2_context_sensitive_p)
            {
              concrete_locations_p = true;
            }
          else
            {
              concrete_locations_p = false;
              res = true;
              *exact_p = false; /* can it be true if we have two null locations ?*/
            }
        }
 
      if (concrete_locations_p)
        {
          /* we have combinable concrete locations or assimilated (context sensitive heap locations) */
          /* they intersect if their descriptors intersection is not empty */
 
          Psysteme sc1 = descriptor_convex(d1);
          Psysteme sc2 = descriptor_convex(d2);
 
 
          /* if one of the systems is unfeasible, the result is false and exact */
          if (sc_empty_p(sc1) || sc_empty_p(sc2))
            {
              pips_debug(8, "d1 or d2 sc_empty");
              res = false;
              *exact_p = true;
            }
 
          /* if one of the systems is not constrained, the result is true and exact */
          else if (sc_rn_p(sc1) || sc_rn_p(sc2))
            {
              pips_debug(8, "d1 or d2 sc_rn\n");
              res = true;
              *exact_p = true;
            }
          else
            {
              /* else test the feasibility of the systems intersection */
              Psysteme sc = cell_system_sc_append_and_normalize(sc_dup(sc1),sc2,2); /* could be some other level? */
 
              CATCH(overflow_error)
              {
                pips_debug(3, "overflow error \n");
                res = true;
                *exact_p = false;
              }
              TRY
                {
                  res = sc_integer_feasibility_ofl_ctrl(sc, FWD_OFL_CTRL, true);
                  *exact_p = true;
                  UNCATCH(overflow_error);
                  sc_rm(sc);
                }
            }
        }
    }
  else
    {
      res = false;
      *exact_p = true;
    }
  return res;
}

References CATCH, cell_abstract_location_p(), cell_entity(), cell_system_sc_append_and_normalize(), cells_combinable_p(), descriptor_convex, entity_flow_or_context_sentitive_heap_location_p(), FWD_OFL_CTRL, overflow_error, pips_debug, sc_dup(), sc_empty_p(), sc_integer_feasibility_ofl_ctrl(), sc_rm(), sc_rn_p(), TRY, and UNCATCH.

Referenced by convex_effect_find_aliased_paths_with_pointer_values().

Here is the call graph for this function:

Here is the caller graph for this function:

disjunction_to_list_of_regions() [1/2]

static list disjunction_to_list_of_regions ( Pdisjunct  disjonction, effect  reg, tag  app, bool  super_or_sub  )

static

3- Difference :

Referenced by region_inf_difference(), and region_sup_difference().

Here is the caller graph for this function:

disjunction_to_list_of_regions() [2/2]

static list disjunction_to_list_of_regions ( Pdisjunct  disjonction, region  reg, tag  app, bool super_or_sub   __attribute__(unused)  )

static

static list disjuction_to_list_of_regions(disjonction, reg, app, super_or_sub) input : a disjunction and a region output : a list of regions which contains a region identical with reg, but for the predicate which is given by the Psystemes of the disjunction and the approximation which depends on the exactness of the representation.

The latter is either a sub or a super approximation of the disjonction, depending on the value of the bool super_or_sub. modifies : the disjunction is freed by the call to disjunction_to_region_sc. comment : app is the tag if the disjunction is exact;

computation of a subapproximation

computation of the exact representation or of a super approximation

build_sc_nredund_2pass(&ps_tmp);

Definition at line 1656 of file binary_operators.c.

{
    Psysteme ps;
    region reg_ps;
    list l_reg = NIL;
    bool exact = true;
    Psysteme ps_tmp;
 
    ps_tmp = disjunction_to_region_sc(disjonction, &exact);
 
    /* computation of a subapproximation */
    if (!exact && SUB)
    {
        sc_rm(ps_tmp);
    }
    /* computation of the exact representation or of a super approximation */
    else
    {
        /* build_sc_nredund_2pass(&ps_tmp); */
        ps = ps_tmp;
 
        if (!sc_empty_p(ps))
        {
            reg_ps = region_dup(reg);
            sc_rm(region_system(reg_ps));
            region_system_(reg_ps) = newgen_Psysteme(ps);
            app = (exact && (app == is_approximation_exact))?
                is_approximation_exact : is_approximation_may;
            region_approximation_tag(reg_ps) = app;
            l_reg = CONS(EFFECT, reg_ps, l_reg);
        }
        else
            sc_rm(ps);
 
    }
    return l_reg;
}

References CONS, disjunction_to_region_sc(), EFFECT, is_approximation_exact, is_approximation_may, newgen_Psysteme, NIL, region, region_approximation_tag, region_dup(), region_system, region_system_, sc_empty_p(), sc_rm(), and SUB.

Here is the call graph for this function:

disjunction_to_region_sc()

static Psysteme disjunction_to_region_sc ( Pdisjunct  disjonction, bool *  p_exact  )

static

static Psysteme disjunction_to_region_sc(Pdisjunct disjonction, bool *b) input : a disjunction representing the union of several Psystemes output : a Psysteme representing the convex_hull of the disjunction of predicates.

modifies : frees the input disjuntion. comment : Exactness is now tested outside the loop.

no need to compute the hull if there is only one system in the disjunction

Exactness test

do not freee the inner Psysteme: it is the result

Definition at line 1606 of file binary_operators.c.

{
    Psysteme ps_res = SC_UNDEFINED;
 
    pips_assert("disjunction not undefined\n", !(disjonction == DJ_UNDEFINED));
 
    ps_res = disjonction->psys;
 
    /* no need to compute the hull if there is only one system in the
     * disjunction */
    if (disjonction->succ != NULL)
    {
        Ppath    chemin;
        Pdisjunct disj_tmp;
 
 
        for(disj_tmp = disjonction->succ;
            disj_tmp != DJ_UNDEFINED;
            disj_tmp = disj_tmp->succ)
        {
            ps_res = region_sc_convex_hull(ps_res, disj_tmp->psys);
        }
        /* Exactness test */
        chemin = pa_make(ps_res,disjonction);
        *p_exact = !(pa_feasibility_ofl_ctrl(chemin, FWD_OFL_CTRL));
        disjonction = dj_free(disjonction);
        chemin->pcomp = disjonction;
        chemin = pa_free1(chemin);
    }
    else
    {
        *p_exact = true;
        /* do not freee the inner Psysteme: it is the result */
        disjonction = dj_free1(disjonction);
    }
    return ps_res;
}

References dj_free(), dj_free1(), DJ_UNDEFINED, FWD_OFL_CTRL, pa_feasibility_ofl_ctrl(), pa_free1(), pa_make(), Spath::pcomp, pips_assert, Ssyslist::psys, region_sc_convex_hull(), and Ssyslist::succ.

Referenced by disjunction_to_list_of_regions().

Here is the call graph for this function:

Here is the caller graph for this function:

print_dinf_statistics()

void print_dinf_statistics	(	char *	mod_name,
		char *	prefix
	)

Parameters

mod_name	od_name
prefix	refix

Definition at line 177 of file binary_operators.c.

{
    FILE *fp;
    string filename;
 
    filename = "dinf_op_stat";
    filename = strdup(concatenate(db_get_current_workspace_directory(), "/",
                                  mod_name, ".", prefix, filename, NULL));
 
    fp = safe_fopen(filename, "w");
    fprintf(fp,"%s",mod_name);
 
    fprintf(fp," %d %d %d \n", nb_dinf, nb_dinf_pot_must, nb_dinf_must);
 
    safe_fclose(fp, filename);
    free(filename);
}

References concatenate(), db_get_current_workspace_directory(), fprintf(), free(), nb_dinf, nb_dinf_must, nb_dinf_pot_must, prefix, safe_fclose(), safe_fopen(), and strdup().

Here is the call graph for this function:

print_dsup_statistics()

void print_dsup_statistics	(	char *	mod_name,
		char *	prefix
	)

Parameters

mod_name	od_name
prefix	refix

Definition at line 158 of file binary_operators.c.

{
    FILE *fp;
    string filename;
 
    filename = "dsup_op_stat";
    filename = strdup(concatenate(db_get_current_workspace_directory(), "/",
                                  mod_name, ".", prefix, filename, NULL));
 
    fp = safe_fopen(filename, "w");
    fprintf(fp,"%s",mod_name);
 
    fprintf(fp," %d %d %d \n", nb_dsup, nb_dsup_pot_must, nb_dsup_must);
 
    safe_fclose(fp, filename);
    free(filename);
}

References concatenate(), db_get_current_workspace_directory(), fprintf(), free(), nb_dsup, nb_dsup_must, nb_dsup_pot_must, prefix, safe_fclose(), safe_fopen(), and strdup().

Here is the call graph for this function:

print_umay_statistics()

void print_umay_statistics	(	char *	mod_name,
		char *	prefix
	)

Parameters

mod_name	od_name
prefix	refix

Definition at line 139 of file binary_operators.c.

{
    FILE *fp;
    string filename;
 
    filename = "umay_op_stat";
    filename = strdup(concatenate(db_get_current_workspace_directory(), "/",
                                  mod_name, ".", prefix, filename, NULL));
 
    fp = safe_fopen(filename, "w");
    fprintf(fp,"%s",mod_name);
 
    fprintf(fp," %d %d %d \n", nb_umay, nb_umay_must_must, nb_umay_must);
 
    safe_fclose(fp, filename);
    free(filename);
}

References concatenate(), db_get_current_workspace_directory(), fprintf(), free(), nb_umay, nb_umay_must, nb_umay_must_must, prefix, safe_fclose(), safe_fopen(), and strdup().

Here is the call graph for this function:

print_umust_statistics()

void print_umust_statistics	(	char *	mod_name,
		char *	prefix
	)

Parameters

mod_name	od_name
prefix	refix

Definition at line 118 of file binary_operators.c.

{
    FILE *fp;
    string filename;
 
    filename = "umust_op_stat";
    filename = strdup(concatenate(db_get_current_workspace_directory(), "/",
                                  mod_name, ".", prefix, filename, NULL));
 
    fp = safe_fopen(filename, "w");
    fprintf(fp,"%s",mod_name);
 
    fprintf(fp," %d %d %d %d %d %d\n", nb_umust, nb_umust_must_must,
            nb_umust_must_must_must, nb_umust_must_may, nb_umust_must_may_must,
            nb_umust_sc_rn);
 
    safe_fclose(fp, filename);
    free(filename);
}

References concatenate(), db_get_current_workspace_directory(), fprintf(), free(), nb_umust, nb_umust_must_may, nb_umust_must_may_must, nb_umust_must_must, nb_umust_must_must_must, nb_umust_sc_rn, prefix, safe_fclose(), safe_fopen(), and strdup().

Here is the call graph for this function:

region_entities_intersection()

list region_entities_intersection	(	region	r1,
		region	r2
	)

list region_entities_intersection(region reg1, reg2) input : two regions output : a mere copy of the first region.

modifies : nothing. comment : We assume that both regions concern the same entity or that one of them is an anywhere effect.

Definition at line 1294 of file binary_operators.c.

{
  region reg;
 
  if (anywhere_effect_p(r1))
  {
    // functions that can be pointed by effect_dup_func:
    // simple_effect_dup
    // region_dup
    // copy_effect
    reg = (*effect_dup_func)(r2);
    effect_action(reg) = copy_action(effect_action(r1));
  }
  else
    reg = region_dup(r1);
 
  return(CONS(EFFECT, reg, NIL));
}

References anywhere_effect_p(), CONS, copy_action(), EFFECT, effect_action, NIL, region, and region_dup().

Referenced by RegionsEntitiesIntersection().

Here is the call graph for this function:

Here is the caller graph for this function:

region_inf_difference()

list region_inf_difference	(	region	reg1,
		region	reg2
	)

list region_inf_difference(region reg1, reg2) input : two regions output : a list of regions containing their inf_difference.

the action of the resulting regions is the action of the first region (reg1). modifies : comment : not debugged because not yet used.

approximation of the resulting region if the difference is exact

particular cases first

nothing minus something (or nothing) = nothing

something minus nothing = something

everything minus everything = nothing

something minus everything = nothing

general case

We cannot compute the under-approximation of the difference: we must assume that it is the empty set

Definition at line 1516 of file binary_operators.c.

{
    Psysteme sc1, sc2;
    /* approximation of the resulting region if the difference is exact */
    volatile tag app = region_approximation_tag(reg1);
 
    list l_res = NIL;
 
    ifdebug(6)
    {
        pips_debug(6, "Initial regions : \n");
        fprintf(stderr,"\t reg1 :\n");
        print_region(reg1);
        fprintf(stderr,"\t reg2 :\n");
        print_region(reg2);
    }
 
    if (anywhere_effect_p(reg1) || anywhere_effect_p(reg2))
      return NIL;
 
    /* particular cases first */
    sc1 = region_system(reg1);
    sc2 = region_system(reg2);
 
    /* nothing minus something (or nothing)  = nothing */
    if (sc_empty_p(sc1))
        return l_res;
 
    /*  something minus nothing = something */
    if (sc_empty_p(sc2))
    {
        l_res = region_to_list(region_dup(reg1));
        return l_res;
    }
 
    /* everything minus everything = nothing */
    if (sc_rn_p(sc1) && sc_rn_p(sc2))
        return l_res;
 
    /* something minus everything = nothing */
    if (sc_rn_p(sc2) )
        return l_res;
 
    /* general case */
    if (op_statistics_p())
    {
        nb_dinf++;
        if (app == is_approximation_exact) nb_dinf_pot_must++;
    }
 
    CATCH(overflow_error)
    {
        /* We cannot compute the under-approximation of the difference:
         *  we must assume that it is the empty set
         */
        pips_debug(1, "overflow error\n");
        app = is_approximation_may;
        l_res = NIL;
    }
    TRY
    {
        Pdisjunct disjonction;
        disjonction = sc_difference(sc1,sc2);
        l_res = disjunction_to_list_of_regions(disjonction, reg1, app, SUPER);
        UNCATCH(overflow_error);
    }
 
    if (op_statistics_p() && !ENDP(l_res))
        if (app == is_approximation_exact) nb_dinf_must++;
 
    ifdebug(6)
    {
        pips_debug(6, "Resulting regions : \n");
        fprintf(stderr,"\t l_res :\n");
        print_regions(l_res);
    }
 
    return l_res;
}

References anywhere_effect_p(), CATCH, disjunction_to_list_of_regions(), ENDP, fprintf(), ifdebug, is_approximation_exact, is_approximation_may, nb_dinf, nb_dinf_must, nb_dinf_pot_must, NIL, op_statistics_p(), overflow_error, pips_debug, print_region, print_regions(), region_approximation_tag, region_dup(), region_system, region_to_list(), sc_difference, sc_empty_p(), sc_rn_p(), SUPER, TRY, and UNCATCH.

Referenced by RegionsInfDifference().

Here is the call graph for this function:

Here is the caller graph for this function:

region_intersection()

list region_intersection	(	region	reg1,
		region	reg2
	)

Intersection :

list region_intersection(region reg1, reg2) input : two regions output : a list of regions containing their difference. the action of the resulting regions is the action of the first region (reg1). modifies : nothing. comment : not debugged, because not yet used. (funny, FC;-) (still up_to-date ? BC) of region

FI: Standard procedure for memory/store regions

memory leak?

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

if one of the regions is unfeasible, return an empty list

else return a list containing a region which predicate is the intersection of the two initial predicates, and which approximation is the "logical" and of the initial approximations.

could be some other level?

FI: extensions for the new action kinds on environment and store. Since they are combinable, reg1==reg2 and hence their intersection is equal to reg1

Definition at line 1096 of file binary_operators.c.

{
  list l_res = NIL;
 
  if(store_effect_p(reg1) && store_effect_p(reg2)) {
    /* FI: Standard procedure for memory/store regions */
    Psysteme sc1 = region_system(reg1);
    Psysteme sc2 = region_system(reg2);
    tag app1 = region_approximation_tag(reg1);
    tag app2 = region_approximation_tag(reg2);
    tag app_res = approximation_and(app1,app2);
 
    ifdebug(3){
      pips_debug(3,"initial regions :\n");
      print_region(reg1);
      print_region(reg2);
    }
 
    if (anywhere_effect_p(reg1))
    {
      // functions that can be pointed by effect_dup_func:
      // simple_effect_dup
      // region_dup
      // copy_effect
      region reg = (*effect_dup_func)(reg2);
      /* memory leak? */
      region_action(reg)= copy_action(region_action(reg1));
      region_approximation_tag(reg)= app_res;
      l_res = region_to_list(reg);
    }
    else if (anywhere_effect_p(reg2))
    {
      // functions that can be pointed by effect_dup_func:
      // simple_effect_dup
      // region_dup
      // copy_effect
      region reg = (*effect_dup_func)(reg1);
      region_approximation_tag(reg)= app_res;
      l_res = region_to_list(reg);
    }
    else
    {
 
      /* Automatic variables read in a CATCH block need to be declared volatile as
       * specified by the documentation*/
      region volatile reg;
      bool feasible = true;
 
 
      /* if one of the regions is unfeasible, return an empty list */
      if (sc_empty_p(sc1) || sc_empty_p(sc2))
      {
        pips_debug(8, "reg1 or reg 2 sc_empty");
        return(l_res);
      }
 
 
      /* else return a list containing a region which predicate is the
       * intersection of the two initial predicates, and which approximation
       * is the "logical" and of the initial approximations.
       */
      reg = region_dup(reg1);
      region_sc_append_and_normalize(reg,sc2,2); /* could be some other level? */
 
      CATCH(overflow_error)
      {
        pips_debug(3, "overflow error \n");
        feasible = true;
        debug_region_consistency(reg);
      }
      TRY
      {
        feasible = sc_integer_feasibility_ofl_ctrl(region_system(reg),
            FWD_OFL_CTRL, true);
        UNCATCH(overflow_error);
      }
 
      if (feasible)
      {
        region_approximation_tag(reg)= app_res;
        l_res = region_to_list(reg);
      }
      else
      {
        region_free(reg);
        l_res = NIL;
      }
    }
  } else {
    /* FI: extensions for the new action kinds on environment and
     * store. Since they are combinable, reg1==reg2 and hence their
     * intersection is equal to reg1 */
    effect reg = copy_effect(reg1);
    l_res = CONS(EFFECT, reg, NIL);
  }
 
  ifdebug(3)
  {
    pips_debug(3,"final region :\n");
    print_regions(l_res);
  }
  return(l_res);
}

References anywhere_effect_p(), approximation_and(), CATCH, CONS, copy_action(), copy_effect(), debug_region_consistency, EFFECT, FWD_OFL_CTRL, ifdebug, NIL, overflow_error, pips_debug, print_region, print_regions(), region, region_action, region_approximation_tag, region_dup(), region_free(), region_sc_append_and_normalize(), region_system, region_to_list(), sc_empty_p(), sc_integer_feasibility_ofl_ctrl(), store_effect_p(), TRY, and UNCATCH.

Referenced by convex_cell_reference_preceding_p(), RegionsIntersection(), and successor_only_has_rr_conflict_p().

Here is the call graph for this function:

Here is the caller graph for this function:

region_may_union()

list region_may_union	(	region	r1,
		region	r2
	)

computes the may union of two combinable array regions

Parameters

[in]	r1	input array region
[in]	r2	input array region

See also

effects_combinable_p

Returns

a new region with no sharing with the input regions

Definition at line 415 of file binary_operators.c.

{
  return region_union(r1, r2, false);
}

References region_union().

Referenced by RegionsMayUnion().

Here is the call graph for this function:

Here is the caller graph for this function:

region_must_union()

list region_must_union	(	region	r1,
		region	r2
	)

computes the must union of two combinable array regions

Parameters

[in]	r1	input array region
[in]	r2	input array region

See also

effects_combinable_p

Returns

a new region with no sharing with the input regions

Definition at line 403 of file binary_operators.c.

{
  return region_union(r1, r2, true);
}

References region_union().

Referenced by compute_regions_union(), and RegionsMustUnion().

Here is the call graph for this function:

Here is the caller graph for this function:

region_sc_convex_hull()

static Psysteme region_sc_convex_hull ( Psysteme  ps1, Psysteme  ps2  )

static

tatic Psysteme region_sc_convex_hull(Psysteme ps1, ps2) input : two systems of constraints output : another system of constraints representing their convex hull.

modifies : the bases of ps1 and ps2 : they are changed to their union, and reordered. comment : same as transformer_convex_hulls, except for the type of the arguments, and the reordering of the bases.

FI->BC: beware of callers that do not perform simplifications. Observed on Regions/chopped_square24.c where two equalities are encoded as four inequalities because a constant is divided by two. Maybe a function similar to expression_to_transformer should be used to analyze subscript expressions, if it is not already the case.

Definition at line 992 of file binary_operators.c.

{
  /* FI->BC: beware of callers that do not perform
     simplifications. Observed on Regions/chopped_square24.c where two
     equalities are encoded as four inequalities because a constant is
     divided by two. Maybe a function similar to
     expression_to_transformer should be used to analyze subscript
     expressions, if it is not already the case. */
  return cute_convex_union(ps1, ps2);
}

References cute_convex_union().

Referenced by disjunction_to_region_sc(), regions_may_convex_hull(), and regions_must_convex_hull().

Here is the call graph for this function:

Here is the caller graph for this function:

region_sup_difference()

list region_sup_difference	(	region	reg1,
		region	reg2
	)

list region_sup_difference(effect reg1, reg2) input : two regions output : a list of regions containing their sup_difference.

the action of the resulting regions is the action of the first region (reg1). modifies : comment :

This is the traditional case, limited to store/memory regions

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

approximation of the resulting regions if the difference is exact

At this point, we are sure that we have array regions

particular cases first

nothing minus (something or nothing) = nothing

something minus nothing = something

everything minus everything = everything (may) for an array and if app2 = may, = nothing otherwise

something minus everything must = nothing

something minus everything may = something may

general case

FI: Here we do need to extend the concept to environment and type declaration effect. I assume that the effect variable is the same, else the difference would be meaningless. If the action_kind is the same, then the difference must be empty, as I hope is the case for scalara variables in the above code. Else r1 is unchanged.

The output list is empty and stays empty

reg1 is not modified by reg2

This also could be considered an internal error

Definition at line 1328 of file binary_operators.c.

{
  list l_reg = NIL;
  if(store_effect_p(reg1) && store_effect_p(reg2)) {
    /* This is the traditional case, limited to store/memory regions */
    Psysteme sc1, sc2;
    /* Automatic variables read in a CATCH block need to be declared volatile as
     * specified by the documentation*/
    volatile tag app1 = region_approximation_tag(reg1);
    volatile tag app2 = region_approximation_tag(reg2);
 
    /* approximation of the resulting regions if the difference is exact */
    volatile tag app = -1;
    region reg;
 
 
    /* At this point, we are sure that we have array regions */
 
    ifdebug(6)
    {
      pips_debug(6, "Initial regions : \n");
      fprintf(stderr,"\t reg1 :\n");
      print_region(reg1);
      fprintf(stderr,"\t reg2 :\n");
      print_region(reg2);
    }
 
    if (anywhere_effect_p(reg1))
    {
      reg = make_anywhere_effect(copy_action(effect_action(reg1)));
      l_reg = region_to_list(reg);
    }
    else if (anywhere_effect_p(reg2))
    {
      // functions that can be pointed by effect_dup_func:
      // simple_effect_dup
      // region_dup
      // copy_effect
      reg = (*effect_dup_func)(reg1);
      l_reg = region_to_may_region_list(reg);
    }
    else
    {
 
      /* particular cases first */
      sc1 = region_system(reg1);
      sc2 = region_system(reg2);
 
      /* nothing minus (something or nothing)  = nothing */
      if (sc_empty_p(sc1))
        return l_reg;
 
      /*  something minus nothing = something */
      if (sc_empty_p(sc2))
      {
        l_reg = region_to_list(region_dup(reg1));
        return l_reg;
      }
 
 
      /* everything minus everything
       *             = everything (may) for an array and if app2 = may,
       *             = nothing otherwise */
      if (sc_rn_p(sc1) && sc_rn_p(sc2))
      {
        if (app2 == is_approximation_may)
          l_reg = region_to_may_region_list(region_dup(reg1));
        return l_reg;
      }
 
      /* something minus everything must = nothing */
      /* something minus everything may = something may*/
      if (sc_rn_p(sc2) )
      {
        if (app2 == is_approximation_may)
          l_reg = region_to_may_region_list(region_dup(reg1));
        return l_reg;
      }
 
 
      /* general case */
      if (op_statistics_p()) nb_dsup++;
 
      switch (app2)
      {
      case is_approximation_exact :
        if (app1 == is_approximation_exact)
        {
          app = is_approximation_exact;
          if (op_statistics_p()) nb_dsup_pot_must++;
        }
        else
          app = is_approximation_may;
        CATCH (overflow_error)
        {
          pips_debug(1, "overflow error\n");
          app = app1;
          l_reg = region_to_may_region_list(region_dup(reg1));
        }
        TRY
        {
          Pdisjunct disjonction;
          disjonction = sc_difference(sc1,sc2);
          l_reg = disjunction_to_list_of_regions
              (disjonction, reg1, app, SUPER);
          UNCATCH(overflow_error);
        }
 
        if (op_statistics_p() && app == is_approximation_exact &&
            (approximation_tag(effect_approximation(reg1)) ==
                is_approximation_exact))
          nb_dsup_must++;
 
        break;
 
      case is_approximation_may :
        CATCH(overflow_error)
        {
          pips_debug(1, "overflow error\n");
          app = is_approximation_may;
        }
        TRY
        {
          if (app1 == is_approximation_exact)
          {
            if (op_statistics_p()) nb_dsup_pot_must++;
            if (sc_intersection_empty_p_ofl(sc1,sc2))
            {
              app = is_approximation_exact;
              if (op_statistics_p()) nb_dsup_must++;
            }
            else app = is_approximation_may;
          }
          else
            app = is_approximation_may;
          UNCATCH(overflow_error);
        }
        reg = region_dup(reg1);
        approximation_tag(effect_approximation(reg)) = app;
        l_reg = CONS(EFFECT, reg, NIL);
        break;
      }
    }
  } else {
    /* FI: Here we do need to extend the concept to environment and
     * type declaration effect. I
     * assume that the effect variable is the same, else the
     * difference would be meaningless. If the action_kind is the
     * same, then the difference must be empty, as I hope is the case
     * for scalara variables in the above code. Else r1 is unchanged. */
    action a1 = effect_action(reg1);
    action a2 = effect_action(reg2);
    action_kind ak1 = action_to_action_kind(a1);
    action_kind ak2 = action_to_action_kind(a2);
    if(action_kind_tag(ak1)==action_kind_tag(ak2)) {
      /* The output list is empty and stays empty */
      l_reg = NIL; // redundant, but improves readability
    }
    else if(action_kind_tag(ak1)==is_action_kind_store
        || action_kind_tag(ak2)==is_action_kind_store)
      pips_internal_error("Unexpected mix of action kinds.");
    else {
      /* reg1 is not modified by reg2 */
      /* This also could be considered an internal error */
      effect reg = copy_effect(reg1);
      l_reg = CONS(EFFECT, reg, NIL);
    }
  }
 
  ifdebug(6)
  {
    pips_debug(6, "Resulting regions : \n");
    fprintf(stderr,"\t l_reg :\n");
    print_regions(l_reg);
  }
 
  return l_reg;
}

References action_kind_tag, action_to_action_kind(), anywhere_effect_p(), approximation_tag, CATCH, CONS, copy_action(), copy_effect(), disjunction_to_list_of_regions(), EFFECT, effect_action, effect_approximation, fprintf(), ifdebug, is_action_kind_store, is_approximation_exact, is_approximation_may, make_anywhere_effect(), nb_dsup, nb_dsup_must, nb_dsup_pot_must, NIL, op_statistics_p(), overflow_error, pips_debug, pips_internal_error, print_region, print_regions(), region, region_approximation_tag, region_dup(), region_system, region_to_list(), region_to_may_region_list(), sc_difference, sc_empty_p(), sc_intersection_empty_p_ofl(), sc_rn_p(), store_effect_p(), SUPER, TRY, and UNCATCH.

Referenced by array_must_fully_written_by_regions_p(), convex_cell_reference_preceding_p(), and RegionsSupDifference().

Here is the call graph for this function:

Here is the caller graph for this function:

region_union()

list region_union	(	region	r1,
		region	r2,
		bool	must_p
	)

computes the must or may union of two combinable array regions depending on the value of must_p

Parameters

[in]	r1	input array region
[in]	r2	input array region
[in]	must_p	bool to control the must/may behavior of the function

See also

effects_combinable_p

Returns

a new region with no sharing with the input regions

Abstract locations cases

In fact, we could have : if (al1_p || al_2_p) { entity e1 = effect_entity(e1); entity e2 = effect_entity(e2); new_ent = entity_locations_max(e1, e2);

eff = make_simple_effect(make_reference(new_ent, NIL), copy_action(effect_action(eff1)), make_approximation(approximation_and(app1,app2), UU)); }

but entity_locations_max involves string manipulations, which are always costly. So we treat apart the cases where (al1_p and ! al2_p) and (al2_p and ! al1_p) because we already know that the abstract location is the max of both locations (because they are combinable (see effects_combinable_p))

concrete locations cases

Definition at line 429 of file binary_operators.c.

{
  list l_res = NIL;
  effect r_res;
  tag app1 = effect_approximation_tag(r1);
  tag app2 = effect_approximation_tag(r2);
 
  if(store_effect_p(r1))
  {
    pips_assert("r2 is a store effect", store_effect_p(r2));
    bool al1_p = effect_abstract_location_p(r1);
    bool al2_p = effect_abstract_location_p(r2);
 
    /* Abstract locations cases */
    /* In fact, we could have :
         if (al1_p || al_2_p)
         {
         entity e1 = effect_entity(e1);
         entity e2 = effect_entity(e2);
         new_ent = entity_locations_max(e1, e2);
 
         eff = make_simple_effect(make_reference(new_ent, NIL),
         copy_action(effect_action(eff1)),
         make_approximation(approximation_and(app1,app2), UU));
         }
 
         but entity_locations_max involves string manipulations, which are always costly.
         So we treat apart the cases where (al1_p and ! al2_p) and (al2_p and ! al1_p) because
         we already know that the abstract location is the max of both locations
         (because they are combinable (see effects_combinable_p))
 
     */
    if (al1_p && al2_p)
    {
      entity e1 = effect_entity(r1);
      entity e2 = effect_entity(r2);
 
      entity new_ent = entity_locations_max(e1, e2);
 
      r_res = make_simple_effect(make_reference(new_ent, NIL),
          copy_action(effect_action(r1)),
          make_approximation(must_p?approximation_and(app1,app2):
              approximation_or(app1,app2), UU));
    }
    else if (al1_p) {
      // functions that can be pointed by effect_dup_func:
      // simple_effect_dup
      // region_dup
      // copy_effect
      r_res = (*effect_dup_func)(r1);
    }
    else if (al2_p) {
      // functions that can be pointed by effect_dup_func:
      // simple_effect_dup
      // region_dup
      // copy_effect
      r_res = (*effect_dup_func)(r2);
    }
 
    /* concrete locations cases */
    else
    {
      r_res = must_p ? regions_must_convex_hull(r1, r2)
          : regions_may_convex_hull(r1,r2);
      if(region_empty_p(r_res))
      {
        region_free(r_res);
        r_res = effect_undefined;
      }
    }
  }
  else
  {
    pips_assert("r2 is not a store effect", !store_effect_p(r2));
    r_res = copy_effect(r1);
  }
 
  if (!effect_undefined_p(r_res))
  {
    debug_region_consistency(r_res);
    l_res = region_to_list(r_res);
  }
 
  return(l_res);
}

References approximation_and(), approximation_or(), copy_action(), copy_effect(), debug_region_consistency, effect_abstract_location_p(), effect_action, effect_approximation_tag, effect_entity(), effect_undefined, effect_undefined_p, entity_locations_max(), make_approximation(), make_reference(), make_simple_effect, NIL, pips_assert, region_empty_p, region_free(), region_to_list(), regions_may_convex_hull(), regions_must_convex_hull(), store_effect_p(), and UU.

Referenced by region_may_union(), and region_must_union().

Here is the call graph for this function:

Here is the caller graph for this function:

regions_may_convex_hull()

static effect regions_may_convex_hull ( region  r1, region  r2  )

static

static effect regions_may_convex_hull(region r1,r2) input : two "effect" representing two regions.

output : an effect, which predicate is the convex hull of the predicates of the initial regions, and which approximation is function of the approximations of the original regions and, in some cases, of the relations between the two initial predicates. modifies : the basis of the predicates of r1 and r2 comment : always computes the convex hull, even if it leads to a may approximation.

region is a renaming of effect

result

Consistency check on regions for action kinds environment and type declaration which should be put in a specific function to enlarge region consistency checks.

sc_empty : no part of the array is accessed

sc_rn : the entire array is accessed

otherwise, we have to compute the convex-hull of the two predicates

if we want to preserve must approximations, then we must find the approximation of the resulting region ; it may depend on the approximations of the initial regions, on the precision (must union or may union), and on the relations between the two initial systems of constraints

we return a whole array region

U_may(must,must)

si s1 == s2 (ie repre'sentent le me^me ensemble) alors must sinon may

Definition at line 796 of file binary_operators.c.

{
  /* region is a renaming of effect */
    region reg = r1;  /* result */
 
    if(!store_effect_p(r1) || !store_effect_p(r2)) {
      ifdebug(1) {
        /* Consistency check on regions for action kinds environment
           and type declaration which should be put in a specific
           function to enlarge region consistency checks. */
      action a1 = effect_action(r1);
      action_kind ak1 = action_to_action_kind(a1);
      action a2 = effect_action(r2);
      action_kind ak2 = action_to_action_kind(a2);
      descriptor d1 = effect_descriptor(r1);
      descriptor d2 = effect_descriptor(r2);
      entity e1 = effect_variable(r1);
      entity e2 = effect_variable(r2);
 
      pips_assert("r1 and r2 have the same action",
                  action_tag(a1)==action_tag(a2));
      pips_assert("r1 and r2 have the same action kind",
                  action_kind_tag(ak1)==action_kind_tag(ak2));
      pips_assert("r1 and r2 refers to the same variable",
                  e1==e2);
      pips_assert("r1 and r2 have no descriptor",
                  descriptor_none_p(d1) && descriptor_none_p(d2));
      }
 
      reg = copy_effect(r1);
    } else {
    Psysteme s1 = region_system(r1);
    Psysteme s2 = region_system(r2);
    Psysteme sr;
    tag app1 = region_approximation_tag(r1);
    tag app2 = region_approximation_tag(r2);
    tag appr = is_approximation_may;
 
    pips_assert("systems not undefined\n",
                !(SC_UNDEFINED_P(s1) || SC_UNDEFINED_P(s2)));
 
    ifdebug(8)
    {
        pips_debug(8, "initial systems\n");
        sc_syst_debug(s1);
        sc_syst_debug(s2);
    }
 
    /* sc_empty : no part of the array is accessed */
    if (sc_empty_p(s1) && sc_empty_p(s2))
    {
        pips_debug(8, "s1 and s2 sc_empty\n");
        reg = region_dup(r1);
        region_approximation_tag(reg) = approximation_and(app1,app2);
        return(reg);
    }
 
    if (sc_empty_p(s1)) {
        pips_debug(8, "s1 sc_empty\n");
        reg = region_dup(r1);
        sc_rm(region_system(reg));
        region_system_(reg) = newgen_Psysteme(sc_dup(s2));
        region_approximation_tag(reg) = is_approximation_may;
        return(reg);
    }
 
    if (sc_empty_p(s2))
    {
        pips_debug(8, "s2 sc_empty\n");
        reg = region_dup(r1);
        region_approximation_tag(reg) = is_approximation_may;
        return(reg);
    }
 
    /* sc_rn : the entire array is accessed */
     if (sc_rn_p(s1) && sc_rn_p(s2))
     {
        pips_debug(8, "s1 and s2 sc_rn\n");
        reg = region_dup(r1);
        region_approximation_tag(reg) = approximation_and(app1,app2);
        return(reg);
    }
 
    if (sc_rn_p(s1))
    {
        pips_debug(8, "s1 sc_rn\n");
        reg = region_dup(r1);
        region_approximation_tag(reg) = is_approximation_may;
        return(reg);
    }
 
    if (sc_rn_p(s2))
    {
        pips_debug(8, "s2 sc_rn\n");
        reg = region_dup(r1);
        region_system_(reg) = newgen_Psysteme(sc_dup(s2));
        region_approximation_tag(reg) = is_approximation_may;
        return(reg);
    }
 
    /* otherwise, we have to compute the convex-hull of the two predicates */
    if (op_statistics_p()) nb_umay++;
 
    sr = region_sc_convex_hull(s1, s2);
    sc_nredund(&sr);
 
    /* if we want to preserve must approximations, then we must find the
     * approximation of the resulting region ;
     * it may depend on the approximations of the initial regions, on the
     * precision
     * (must union or may union), and on the relations between the two initial
     * systems of constraints */
 
    if(sc_rn_p(sr))
    {
        reference refr = copy_reference(region_any_reference(r1));
        action acr = region_action(r1);
 
        pips_debug(1,"sr sc_rn (maybe due to an overflow error)\n");
 
        if (op_statistics_p())
        {
            if (approximation_and(app1,app2) == is_approximation_exact)
                nb_umay_must_must++;
        }
 
        /* we return a whole array region */
        appr = is_approximation_may;
        reg = reference_whole_region(refr, acr);
        effect_to_may_effect(reg);
        ifdebug(8)
        {
            pips_debug(8, "final region : \n");
            print_region(reg);
        }
        sc_rm(sr);
        sr = NULL;
        return(reg);
    }
    else
    {
        if(!must_regions_p())
        {
            pips_debug(8,"may regions\n");
            appr = is_approximation_may;
        }
        else
        {
            if ((app1 == is_approximation_exact) &&
                (app2 == is_approximation_exact))
            {
                /* U_may(must,must) */
                /* si s1 == s2 (ie repre'sentent le me^me ensemble)
                 * alors must sinon may */
                if (sc_equal_p_ofl(s1,s2))
                    appr = is_approximation_exact;
                else
                    appr = is_approximation_may;
            }
            else
                appr = is_approximation_may;
        }
    }
    reg = region_dup(r1);
    sc_rm(region_system(reg));
    region_system_(reg) = newgen_Psysteme(sr);
    region_approximation_tag(reg) = appr;
 
    if (op_statistics_p())
    {
        if (approximation_and(app1,app2) == is_approximation_exact)
        {
            nb_umay_must_must++;
            if (appr == is_approximation_exact) nb_umay_must++;
        }
    }
    }
 
    ifdebug(8)
    {
        pips_debug(8, "final region : \n");
        print_region(reg);
    }
 
    return(reg);
}

References action_kind_tag, action_tag, action_to_action_kind(), approximation_and(), copy_effect(), copy_reference(), descriptor_none_p, effect_action, effect_descriptor, effect_to_may_effect(), effect_variable, ifdebug, is_approximation_exact, is_approximation_may, must_regions_p(), nb_umay, nb_umay_must, nb_umay_must_must, newgen_Psysteme, op_statistics_p(), pips_assert, pips_debug, print_region, reference_whole_region(), region, region_action, region_any_reference, region_approximation_tag, region_dup(), region_sc_convex_hull(), region_system, region_system_, s1, sc_dup(), sc_empty_p(), sc_equal_p_ofl, sc_rm(), sc_rn_p(), sc_syst_debug(), and store_effect_p().

Referenced by region_union().

Here is the call graph for this function:

Here is the caller graph for this function:

regions_must_convex_hull()

effect regions_must_convex_hull	(	region	r1,
		region	r2
	)

1- Union :

static effect regions_must_convex_hull(r1,r2) input : two "effect" representing two regions.

output : an effect, which predicate is the convex hull of the predicates of the initial regions, and which approximation is function of of the approximations of the original regions and, in some cases, of the relations between the two initial predicates. modifies : the basis of the predicates of r1 and r2 comment : always computes the convex hull, even if it leads to a may approximation.

FI: extension to support non-store effects without predicates

result

proper_effects_combine() free the arguments of region_sc_convex_hull()

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

sc_empty : no part of the array is accessed

sc_rn : the entire array is accessed

otherwise, we have to compute the convex-hull of the two predicates

to avoid problems in case of overflow error

if we want to preserve must approximations, then we must find the approximation of the resulting region ; it may depend on the approximations of the initial regions, and on the relations between the two initial systems of constraints

we return a whole array region

U_must(must, must)

si enveloppe convexe (s1, s2) exacte must sinon may

U_must(must,may)

U_must(may,must)

Definition at line 531 of file binary_operators.c.

{
  region reg = r1;  /* result */
 
  if(!store_effect_p(r1)) {
    /* proper_effects_combine() free the arguments of
       region_sc_convex_hull() */
    reg = copy_effect(r1);
  } else {
    /* Automatic variables read in a CATCH block need to be declared volatile as
     * specified by the documentation*/
    Psysteme volatile s1 = region_system(r1);
    Psysteme s2 = region_system(r2);
    Psysteme sr;
    tag app1 = region_approximation_tag(r1);
    tag app2 = region_approximation_tag(r2);
    tag appr = is_approximation_may;
 
    debug_region_consistency(r1);
    debug_region_consistency(r2);
 
    pips_assert("systems not undefined\n",
                !(SC_UNDEFINED_P(s1) || SC_UNDEFINED_P(s2)));
 
    ifdebug(8)
      {
        pips_debug(8, "syste`mes initiaux\n");
        sc_syst_debug(s1);
        sc_syst_debug(s2);
      }
 
    /* sc_empty : no part of the array is accessed */
    if (sc_empty_p(s1) && sc_empty_p(s2))
      {
        pips_debug(8, "s1 and s2 sc_empty\n");
        reg = region_dup(r1);
        region_approximation_tag(reg) = approximation_or(app1,app2);
        return(reg);
      }
 
    if (sc_empty_p(s1))
      {
        pips_debug(8, "s1 sc_empty\n");
        reg = region_dup(r1);
        sc_rm(region_system(reg));
        region_system_(reg) = newgen_Psysteme(sc_dup(s2));
        return(reg);
      }
 
    if (sc_empty_p(s2))
      {
        pips_debug(8, "s2 sc_empty\n");
        reg = region_dup(r1);
        return(reg);
      }
 
 
    /* sc_rn : the entire array is accessed */
    if (sc_rn_p(s1) && sc_rn_p(s2))
      {
        pips_debug(8, "s1 and s2 sc_rn\n");
        reg = region_dup(r1);
        region_approximation_tag(reg) = approximation_or(app1,app2);
        return(reg);
      }
 
    if (sc_rn_p(s1))
      {
        pips_debug(8, "s1 sc_rn\n");
        reg = region_dup(r1);
        region_approximation_tag(reg) = is_approximation_may;
        return(reg);
      }
 
    if (sc_rn_p(s2))
      {
        pips_debug(8, "s2 sc_rn\n");
        reg = region_dup(r1);
        region_system_(reg) =  newgen_Psysteme(sc_dup(s2));
        region_approximation_tag(reg) = app2;
        return(reg);
      }
 
 
    /* otherwise, we have to compute the convex-hull of the two predicates */
    if (op_statistics_p()) nb_umust++;
 
 
    Pbase b1 = s1->base;
    Pbase b2 = s2->base;
    Pbase volatile b = base_union(b1, b2);
    s1->base = b;
    sc_dimension(s1) = base_dimension(b);
    s2->base = base_copy(b);
    sc_dimension(s2) = sc_dimension(s1);
    base_rm(b1);
    base_rm(b2);
 
 
    CATCH(overflow_error)
    {
      pips_debug(1, "overflow error\n");
      sr = sc_rn(base_dup(b));
    }
    TRY
      {
        pips_debug(8, "compute the convex hull...\n");
        sr = region_sc_convex_hull(s1, s2);
        ifdebug(8)
          {
            pips_debug(8, "cute convex hull:\n");
            sc_syst_debug(sr);
          }
 
        pips_debug(8, "eliminate redudances...\n");
        sc_nredund(&sr);
        ifdebug(8)
          {
            pips_debug(8, "after redundancy elimination:\n");
            sc_syst_debug(sr);
          }
 
        UNCATCH(overflow_error);
      }
 
    /* to avoid problems in case of overflow error */
    appr = is_approximation_may;
 
    /* if we want to preserve must approximations, then we must find the
     * approximation of the resulting region ;
     * it may depend on the approximations of the initial regions, and on
     * the relations between the two initial systems of constraints */
 
    if(sc_rn_p(sr))
      {
        pips_debug(1, "sr sc_rn (maybe due to an overflow error)\n");
 
        if (op_statistics_p())
          {
            if ((app1 == is_approximation_exact) &&
                (app2 == is_approximation_exact))
              nb_umust_must_must++;
            else
              if (!((app1 == is_approximation_may)
                    && (app2 == is_approximation_may)))
                nb_umust_must_may++;
            nb_umust_sc_rn++;
          }
 
        /* we return a whole array region */
        appr = is_approximation_may;
        reg = region_dup(r1);
        sc_rm(region_system(reg));
        region_system_(reg) = newgen_Psysteme(sr);
        region_approximation_tag(reg) = appr;
        effect_to_may_effect(reg);
        ifdebug(8)
          {
            pips_debug(8, "final region : \n");
            print_region(reg);
          }
        return(reg);
      }
    else
      {
        if(!must_regions_p())
          {
            pips_debug(8, "may regions\n");
            appr = is_approximation_may;
          }
        else
          {
            switch (app1)
              {
              case is_approximation_exact:
 
                switch (app2)
                  {
                  case is_approximation_exact: /* U_must(must, must) */
                    /* si enveloppe convexe (s1, s2) exacte must sinon may */
                    if (sc_convex_hull_equals_union_p_ofl(sr,s1,s2))
                      {
                        pips_debug(8,"exact convex hull\n");
                        appr = is_approximation_exact;
                      }
                    else
                      {
                        pips_debug(8,"non exact convex hull\n");
                        appr = is_approximation_may;
                      }
                    if (op_statistics_p())
                      {
                        nb_umust_must_must++;
                        if (appr == is_approximation_exact)
                          nb_umust_must_must_must++;
                      }
                    break;
 
                  case is_approximation_may: /* U_must(must,may) */
                    if(sc_inclusion_p_ofl(s2,s1))
                      appr = is_approximation_exact;
                    else
                      appr = is_approximation_may;
                    if (op_statistics_p())
                      {
                        nb_umust_must_may++;
                        if (appr == is_approximation_exact)
                          nb_umust_must_may_must++;
                      }
                    break;
                  }
                break;
              case is_approximation_may:
 
                switch (app2)
                  {
                  case is_approximation_exact: /* U_must(may,must) */
                    if(sc_inclusion_p_ofl(s1,s2))
                      appr = is_approximation_exact;
                    else
                      appr = is_approximation_may;
                    if (op_statistics_p())
                      {
                        nb_umust_must_may++;
                        if (appr == is_approximation_exact)
                          nb_umust_must_may_must++;
                      }
                    break;
                  case is_approximation_may:
                    appr = is_approximation_may;
                    break;
                  }
                break;
              }
          }
      }
    reg = copy_effect(r1);
    sc_rm(region_system(reg));
    region_system_(reg) = newgen_Psysteme(sr);
    region_approximation_tag(reg) = appr;
  }
 
  ifdebug(8)
    {
      pips_debug(8, "final region : \n");
      print_region(reg);
      pips_assert("reg is consistent", effect_consistent_p(reg));
    }
 
  return(reg);
 
}

References approximation_or(), b1, b2, Ssysteme::base, base_copy(), base_dimension, base_dup(), base_rm, base_union(), CATCH, copy_effect(), debug_region_consistency, effect_consistent_p(), effect_to_may_effect(), ifdebug, is_approximation_exact, is_approximation_may, must_regions_p(), nb_umust, nb_umust_must_may, nb_umust_must_may_must, nb_umust_must_must, nb_umust_must_must_must, nb_umust_sc_rn, newgen_Psysteme, op_statistics_p(), overflow_error, pips_assert, pips_debug, print_region, region, region_approximation_tag, region_dup(), region_sc_convex_hull(), region_system, region_system_, s1, sc_convex_hull_equals_union_p_ofl, sc_dup(), sc_empty_p(), sc_inclusion_p_ofl, sc_rm(), sc_rn(), sc_rn_p(), sc_syst_debug(), store_effect_p(), TRY, and UNCATCH.

Referenced by do_solve_hardware_constraints_on_nb_proc(), do_solve_hardware_constraints_on_volume(), extended_regions_must_convex_hull(), region_union(), set_methods_for_convex_effects(), and set_methods_for_convex_rw_pointer_effects().

Here is the call graph for this function:

Here is the caller graph for this function:

RegionsEntitiesInfDifference()

list RegionsEntitiesInfDifference	(	list	l1,
		list	l2,
		bool(*)(effect, effect)	difference_combinable_p
	)

list RegionsEntitiesInfDifference(list l1, l2) input : two lists of regions output : a list of regions, such that: if there is a region R concerning entity A in l1 and in l2, then R is removed from the result; if there is a region R concerning array A in l1, but not in l2, then it is kept in l1, and in the result.

modifies : the regions of l2 may be freed. comment : we keep the regions of l1 that are not combinable with those of l2, but we don't keep the regions of l2 that are not combinable with those of l_reg1.

l_res = list_of_effects_generic_binary_op(l1, l2, difference_combinable_p, regions_to_nil_list, region_to_list, region_to_nil_list);

Parameters

l1	1
l2	2

Definition at line 366 of file binary_operators.c.

{
    list l_res = NIL;
 
    debug(3, "RegionsEntitiesInfDifference", "begin\n");
    /*    l_res = list_of_effects_generic_binary_op(l1, l2,
                                           difference_combinable_p,
                                           regions_to_nil_list,
                                           region_to_list,
                                           region_to_nil_list);*/
    l_res = list_of_effects_generic_cells_inf_difference_op(l1, l2,
                                           difference_combinable_p,
                                           regions_to_nil_list);
    debug(3, "RegionsEntitiesInfDifference", "end\n");
 
    return l_res;
}

References debug(), list_of_effects_generic_cells_inf_difference_op(), NIL, and regions_to_nil_list().

Referenced by internal_compute_distribution_context().

Here is the call graph for this function:

Here is the caller graph for this function:

RegionsEntitiesIntersection()

list RegionsEntitiesIntersection	(	list	l1,
		list	l2,
		bool(*)(effect, effect)	intersection_combinable_p
	)

list RegionsEntitiesIntersection(list l1,l2, bool (*intersection_combinable_p)(effect, effect)) input : two lists of regions output : a list of regions containing all the regions of l1 that have a corresponding region (i.e.

same entity) in l2. modifies : l1 and l2. comment :

l_res = list_of_effects_generic_binary_op(l1, l2, intersection_combinable_p, region_entities_intersection, region_to_nil_list, region_to_nil_list);

Parameters

l1	1
l2	2

Definition at line 275 of file binary_operators.c.

{
    list l_res = NIL;
 
    pips_debug(3, "begin\n");
    /*    l_res = list_of_effects_generic_binary_op(l1, l2,
                                           intersection_combinable_p,
                                           region_entities_intersection,
                                           region_to_nil_list,
                                           region_to_nil_list); */
 
    l_res = list_of_effects_generic_cells_intersection_op(l1, l2,
                                           intersection_combinable_p,
                                           region_entities_intersection);
    pips_debug(3, "end\n");
 
    return l_res;
}

References list_of_effects_generic_cells_intersection_op(), NIL, pips_debug, and region_entities_intersection().

Here is the call graph for this function:

RegionsInfDifference()

list RegionsInfDifference	(	list	l1,
		list	l2,
		bool(*)(effect, effect)	difference_combinable_p
	)

list RegionsInfDifference(list l1, l2) input : two lists of regions output : a list of region, representing the inf_difference of the initial regions.

modifies : the regions of l2 may be freed. comment : we keep the regions of l1 that are not combinable with those of l2, but we don't keep the regions of l2 that are not combinable with those of l_reg1.

l_res = list_of_effects_generic_binary_op(l1, l2, difference_combinable_p, region_inf_difference, region_to_list, region_to_nil_list);

Parameters

l1	1
l2	2

Definition at line 334 of file binary_operators.c.

{
    list l_res = NIL;
 
    debug(3, "RegionsInfDifference", "begin\n");
    /*    l_res = list_of_effects_generic_binary_op(l1, l2,
                                           difference_combinable_p,
                                           region_inf_difference,
                                           region_to_list,
                                           region_to_nil_list); */
    l_res = list_of_effects_generic_inf_difference_op(l1, l2,
                                           difference_combinable_p,
                                           region_inf_difference);
     debug(3, "RegionsInfDifference", "end\n");
 
    return l_res;
}

References debug(), list_of_effects_generic_inf_difference_op(), NIL, and region_inf_difference().

Referenced by set_methods_for_convex_effects(), and set_methods_for_convex_rw_pointer_effects().

Here is the call graph for this function:

Here is the caller graph for this function:

RegionsIntersection()

list RegionsIntersection	(	list	l1,
		list	l2,
		bool(*)(effect, effect)	intersection_combinable_p
	)

list RegionsIntersection(list l1,l2, bool (*intersection_combinable_p)(effect, effect)) input : output : modifies : comment :

Parameters

l1	1
l2	2

Definition at line 250 of file binary_operators.c.

{
    list l_res = NIL;
 
    debug(3, "RegionsIntersection", "begin\n");
    l_res = list_of_effects_generic_intersection_op(l1, l2,
                                           intersection_combinable_p,
                                           region_intersection);
 
 
    debug(3, "RegionsIntersection", "end\n");
 
    return l_res;
}

References debug(), list_of_effects_generic_intersection_op(), NIL, and region_intersection().

Referenced by compute_send_regions(), edge_cost(), edge_cost_polynome(), real_regions_forward_translation(), set_methods_for_convex_effects(), set_methods_for_convex_rw_pointer_effects(), test_dependence_using_regions(), and transfer_regions().

Here is the call graph for this function:

Here is the caller graph for this function:

RegionsMayUnion()

list RegionsMayUnion	(	list	l1,
		list	l2,
		bool(*)(effect, effect)	union_combinable_p
	)

list RegionsMayUnion(list l1, list l2, union_combinable_p) input : two lists of regions output : a list of regions, may union of the two initial lists modifies : l1 and l2 and their regions.

Regions that are not reused in the output list of regions are freed.nothing (no sharing introduced).

Parameters

l1	1
l2	2

Definition at line 207 of file binary_operators.c.

{
    list lr;
 
    debug(3, "RegionsMayUnion", "begin\n");
    lr = list_of_effects_generic_union_op(l1, l2,
                                           union_combinable_p,
                                           region_may_union,
                                           region_to_may_region_list);
    debug(3, "RegionsMayUnion", "end\n");
    return(lr);
}

References debug(), list_of_effects_generic_union_op(), region_may_union(), and region_to_may_region_list().

Referenced by set_methods_for_convex_effects(), set_methods_for_convex_rw_pointer_effects(), and update_out_summary_regions_list().

Here is the call graph for this function:

Here is the caller graph for this function:

RegionsMustUnion()

list RegionsMustUnion	(	list	l1,
		list	l2,
		bool(*)(effect, effect)	union_combinable_p
	)

list RegionsMustUnion(list l1, list l2, union_combinable_p) input : two lists of regions output : a list of regions, must union of the two initial lists modifies : l1 and l2 and their regions.

Regions that are not reused in the output list of regions are freed.

Parameters

l1	1
l2	2

Definition at line 228 of file binary_operators.c.

{
  list lr;
 
  debug(3, "RegionsMustUnion", "begin\n");
  lr = list_of_effects_generic_union_op(l1, l2,
      union_combinable_p,
      region_must_union,
      region_to_list);
  debug(3, "RegionsMustUnion", "end\n");
  return(lr);
}

References debug(), list_of_effects_generic_union_op(), region_must_union(), and region_to_list().

Referenced by allocate_task_to_cluster(), c_convex_effects_on_actual_parameter_forward_translation(), common_region_translation(), common_regions_backward_translation(), common_regions_forward_translation(), compute_recv_regions(), MCW(), move_task_to_cluster(), real_regions_forward_translation(), regions_backward_translation(), regions_forward_translation(), set_methods_for_convex_effects(), set_methods_for_convex_rw_pointer_effects(), and used_data().

Here is the call graph for this function:

Here is the caller graph for this function:

RegionsSupDifference()

list RegionsSupDifference	(	list	l1,
		list	l2,
		bool(*)(effect, effect)	difference_combinable_p
	)

list RegionsSupDifference(list l1, l2) input : two lists of regions output : a list of region, representing the sup_difference of the initial regions.

modifies : the regions of l2 may be freed. comment : we keep the regions of l1 that are not combinable with those of l2, but we don't keep the regions of l2 that are not combinable with those of l_reg1.

l_res = list_of_effects_generic_binary_op(l1, l2, difference_combinable_p, region_sup_difference, region_to_list, region_to_nil_list);

Parameters

l1	1
l2	2

Definition at line 305 of file binary_operators.c.

{
    list l_res = NIL;
 
    debug(3, "RegionsSupDifference", "begin\n");
    /* l_res = list_of_effects_generic_binary_op(l1, l2,
                                           difference_combinable_p,
                                           region_sup_difference,
                                           region_to_list,
                                           region_to_nil_list); */
    l_res = list_of_effects_generic_sup_difference_op(l1, l2,
                                           difference_combinable_p,
                                           region_sup_difference);
 
    debug(3, "RegionsSupDifference", "end\n");
 
    return l_res;
}

References debug(), list_of_effects_generic_sup_difference_op(), NIL, and region_sup_difference().

Referenced by set_methods_for_convex_effects(), and set_methods_for_convex_rw_pointer_effects().

Here is the call graph for this function:

Here is the caller graph for this function:

reset_binary_op_statistics()

void reset_binary_op_statistics

(

void

)

binary_operators.c

Definition at line 93 of file binary_operators.c.

{
    nb_umust = 0;
    nb_umust_must_must = 0;
    nb_umust_must_must_must = 0;
    nb_umust_must_may = 0;
    nb_umust_must_may_must = 0;
    nb_umust_sc_rn = 0;
 
    nb_umay = 0;
    nb_umay_must_must = 0;
    nb_umay_must = 0;
 
    nb_dsup = 0;
    nb_dsup_pot_must = 0;
    nb_dsup_must = 0;
 
    nb_dinf = 0;
    nb_dinf_pot_must = 0;
    nb_dinf_must = 0;
}

References nb_dinf, nb_dinf_must, nb_dinf_pot_must, nb_dsup, nb_dsup_must, nb_dsup_pot_must, nb_umay, nb_umay_must, nb_umay_must_must, nb_umust, nb_umust_must_may, nb_umust_must_may_must, nb_umust_must_must, nb_umust_must_must_must, and nb_umust_sc_rn.

Variable Documentation

nb_dinf

int nb_dinf = 0

static

Definition at line 88 of file binary_operators.c.

Referenced by print_dinf_statistics(), region_inf_difference(), and reset_binary_op_statistics().

nb_dinf_must

int nb_dinf_must = 0

static

Definition at line 90 of file binary_operators.c.

Referenced by print_dinf_statistics(), region_inf_difference(), and reset_binary_op_statistics().

nb_dinf_pot_must

int nb_dinf_pot_must = 0

static

Definition at line 89 of file binary_operators.c.

Referenced by print_dinf_statistics(), region_inf_difference(), and reset_binary_op_statistics().

nb_dsup

int nb_dsup = 0

static

Definition at line 84 of file binary_operators.c.

Referenced by print_dsup_statistics(), region_sup_difference(), and reset_binary_op_statistics().

nb_dsup_must

int nb_dsup_must = 0

static

Definition at line 86 of file binary_operators.c.

Referenced by print_dsup_statistics(), region_sup_difference(), and reset_binary_op_statistics().

nb_dsup_pot_must

int nb_dsup_pot_must = 0

static

Definition at line 85 of file binary_operators.c.

Referenced by print_dsup_statistics(), region_sup_difference(), and reset_binary_op_statistics().

nb_umay

int nb_umay = 0

static

Definition at line 80 of file binary_operators.c.

Referenced by print_umay_statistics(), regions_may_convex_hull(), and reset_binary_op_statistics().

nb_umay_must

int nb_umay_must = 0

static

Definition at line 82 of file binary_operators.c.

Referenced by print_umay_statistics(), regions_may_convex_hull(), and reset_binary_op_statistics().

nb_umay_must_must

int nb_umay_must_must = 0

static

Definition at line 81 of file binary_operators.c.

Referenced by print_umay_statistics(), regions_may_convex_hull(), and reset_binary_op_statistics().

nb_umust

int nb_umust = 0

static

Definition at line 73 of file binary_operators.c.

Referenced by print_umust_statistics(), regions_must_convex_hull(), and reset_binary_op_statistics().

nb_umust_must_may

int nb_umust_must_may = 0

static

Definition at line 76 of file binary_operators.c.

Referenced by print_umust_statistics(), regions_must_convex_hull(), and reset_binary_op_statistics().

nb_umust_must_may_must

int nb_umust_must_may_must = 0

static

Definition at line 77 of file binary_operators.c.

Referenced by print_umust_statistics(), regions_must_convex_hull(), and reset_binary_op_statistics().

nb_umust_must_must

int nb_umust_must_must = 0

static

Definition at line 74 of file binary_operators.c.

Referenced by print_umust_statistics(), regions_must_convex_hull(), and reset_binary_op_statistics().

nb_umust_must_must_must

int nb_umust_must_must_must = 0

static

Definition at line 75 of file binary_operators.c.

Referenced by print_umust_statistics(), regions_must_convex_hull(), and reset_binary_op_statistics().

nb_umust_sc_rn

int nb_umust_sc_rn = 0

static

Definition at line 78 of file binary_operators.c.

Referenced by print_umust_statistics(), regions_must_convex_hull(), and reset_binary_op_statistics().