Effects

Functions
void	set_conflict_testing_properties ()
	conflicts.c More...
bool	effects_must_conflict_p (effect eff1, effect eff2)
	Intersection tests. More...
bool	effects_might_conflict_even_read_only_p (effect eff1, effect eff2)
	Check if two effect might conflict, even if they are read only @description Two effects may conflict if their abstract two location sets has a non-empty intersection. More...
bool	effects_may_conflict_p (effect eff1, effect eff2)
	Check if two effect may conflict @description Two effects may conflict if their abstract two location sets has a non-empty intersection and if at least one of them is a write. More...
static bool	old_effects_conflict_p (effect eff1, effect eff2)
	OBSOLETE, was never used !! More...
bool	effects_conflict_p (effect eff1, effect eff2)
	Synonym for effects_may_conflict_p(). More...
bool	array_references_may_conflict_p (list sl1, list sl2)
	Check if there may be a conflict between two array references. More...
bool	variable_references_may_conflict_p (entity v, list sl1, list sl2)
	FIXME ? More...
bool	references_may_conflict_p (reference r1, reference r2)
	Check if two references may conflict. More...
bool	references_must_conflict_p (reference r1, reference r2)
	Check if two references may conflict. More...
static bool	cells_maymust_conflict_p (cell c1, cell c2, bool must_p)
	Check if two cell may or must conflict. More...
bool	cells_may_conflict_p (cell c1, cell c2)
	Check if two cell may conflict. More...
bool	points_to_cell_lists_may_conflict_p (list l1, list l2)
	Same as above, but for lists. More...
bool	cells_must_conflict_p (cell c1, cell c2)
	Check if two cell must conflict. More...
bool	points_to_cell_lists_must_conflict_p (list l1, list l2)
	Same as above, but for lists. More...
bool	entities_maymust_conflict_p (entity e1, entity e2, bool must_p)
	Check if two entities may or must conflict. More...
bool	entities_may_conflict_p (entity e1, entity e2)
	Check if two entities may conflict. More...
bool	entities_must_conflict_p (entity e1, entity e2)
	Check if two entities must conflict. More...
static bool	first_reference_certainly_includes_second_reference_p (reference r1, reference r2)
	Inclusion tests. More...
static bool	first_cell_certainly_includes_second_cell_p (cell c1, cell c2)
	tests whether first cell certainly includes second one More...
bool	first_effect_certainly_includes_second_effect_p (effect eff1, effect eff2)
	tests whether first effect certainly includes second one. More...
bool	first_exact_scalar_effect_certainly_includes_second_effect_p (effect eff1, effect eff2)
bool	effect_may_read_or_write_memory_paths_from_entity_p (effect ef, entity e)
	misc functions More...
bool	effects_may_read_or_write_memory_paths_from_entity_p (list l_eff, entity e)
	tests whether the input effects list may contain effects with a memory path from the input entity e; this is currently a mere syntactic test. More...
bool	generic_effects_maymust_read_or_write_scalar_entity_p (list fx, entity e, bool must_p, bool concrete_p)
bool	effects_maymust_read_or_write_scalar_entity_p (list fx, entity e, bool must_p)
bool	concrete_effects_maymust_read_or_write_scalar_entity_p (list fx, entity e, bool must_p)
bool	effects_may_read_or_write_scalar_entity_p (list fx, entity e)
	check whether scalar entity e may be read or written by effects fx or cannot be accessed at all More...
bool	concrete_effects_may_read_or_write_scalar_entity_p (list fx, entity e)
bool	effects_must_read_or_write_scalar_entity_p (list fx, entity e)
	check whether scalar entity e must be read or written by any effect of fx or if it simply might be accessed. More...
static list	generic_effects_entities_which_may_conflict_with_scalar_entity (list fx, entity e, bool concrete_p)
	Returns the list of entities used in effect list fx and potentially conflicting with e. More...
list	effects_entities_which_may_conflict_with_scalar_entity (list fx, entity e)
list	concrete_effects_entities_which_may_conflict_with_scalar_entity (list fx, entity e)

Variables
static bool	constant_path_effects_p = true
	Properties settings for conflict testing functions. More...
static bool	trust_constant_path_effects_p = false
static bool	user_effects_on_std_files_p = false
static bool	aliasing_across_types_p = true
static bool	aliasing_across_formal_parameters_p = false

Detailed Description

Function Documentation

array_references_may_conflict_p()

bool array_references_may_conflict_p	(	list	sl1,
		list	sl2
	)

Check if there may be a conflict between two array references.

@description May the two references to array a using subscript list sl1 and sl2 access the same memory locations?

Subscript list sl1 and sl2 can be evaluated in two different stores.

It is assumed that dim(a)=length(sl1)=length(sl2);

If the nth subscript expression can be statically evaluated in both sl1 and sl2 and if the subscript values are different, there is not conflict. For instance a[i][0] does not conflict with a[j][1]. SG: this is only true if you assume no out-of-bound indices e.g int a[2][2]; a[1][0] conflict with a[0][2] ..

This is about the old references_conflict_p()

Parameters

sl1	l1
sl2	l2

Definition at line 276 of file conflicts.c.

                                                           {
  bool conflict_p = true;
 
  list cind1 = list_undefined;
  list cind2 = list_undefined;
  for ( cind1 = sl1, cind2 = sl2; conflict_p && !ENDP(cind1) && !ENDP(cind2); POP(cind1), POP(cind2) ) {
    expression e1 = EXPRESSION(CAR(cind1));
    expression e2 = EXPRESSION(CAR(cind2));
    if ( unbounded_expression_p( e1 ) || unbounded_expression_p( e2 ) )
      conflict_p = true;
    else {
      intptr_t i1 = -1;
      intptr_t i2 = -1;
      bool i1_p = false;
      bool i2_p = false;
 
      i1_p = expression_integer_value( e1, &i1 );
      i2_p = expression_integer_value( e2, &i2 );
      if ( i1_p && i2_p )
        conflict_p = ( i1 == i2 );
      else
        conflict_p = true;
    }
  }
  return conflict_p;
}

References CAR, ENDP, EXPRESSION, expression_integer_value(), intptr_t, list_undefined, POP, and unbounded_expression_p().

Referenced by variable_references_may_conflict_p().

Here is the call graph for this function:

Here is the caller graph for this function:

cells_may_conflict_p()

bool cells_may_conflict_p	(	cell	c1,
		cell	c2
	)

Check if two cell may conflict.

Parameters

c1	1
c2	2

Definition at line 696 of file conflicts.c.

                                              {
  bool conflict_p = cells_maymust_conflict_p( c1, c2, false );
  return conflict_p;
}

References cells_maymust_conflict_p().

Referenced by effects_might_conflict_even_read_only_p(), gen_may_set(), points_to_cell_lists_may_conflict_p(), and statement_with_side_effect_p().

Here is the call graph for this function:

Here is the caller graph for this function:

cells_maymust_conflict_p()

static bool cells_maymust_conflict_p ( cell  c1, cell  c2, bool  must_p  )

static

Check if two cell may or must conflict.

Parameters

must_p

if set to true, we enforce a must conflict

Definition at line 667 of file conflicts.c.

                                                                      {
  bool conflict_p = false;
  reference r1 = reference_undefined;
  reference r2 = reference_undefined;
 
  if ( cell_reference_p(c1) )
    r1 = cell_reference(c1);
  else if ( cell_preference_p(c1) )
    r1 = preference_reference(cell_preference(c1));
 
  if ( cell_reference_p(c2) )
    r2 = cell_reference(c2);
  else if ( cell_preference_p(c2) )
    r2 = preference_reference(cell_preference(c2));
 
  if ( reference_undefined_p(r1) || reference_undefined_p(r2) ) {
    pips_internal_error("either undefined references or gap "
        "not implemented yet\n");
  }
 
  conflict_p = must_p ? references_must_conflict_p( r1, r2 )
                      : references_may_conflict_p( r1, r2 );
 
  return conflict_p;
}

References cell_preference, cell_preference_p, cell_reference, cell_reference_p, pips_internal_error, preference_reference, reference_undefined, reference_undefined_p, references_may_conflict_p(), and references_must_conflict_p().

Referenced by cells_may_conflict_p(), and cells_must_conflict_p().

Here is the call graph for this function:

Here is the caller graph for this function:

cells_must_conflict_p()

bool cells_must_conflict_p	(	cell	c1,
		cell	c2
	)

Check if two cell must conflict.

Parameters

c1	1
c2	2

Definition at line 722 of file conflicts.c.

                                               {
  bool conflict_p = cells_maymust_conflict_p( c1, c2, true );
  return conflict_p;
}

References cells_maymust_conflict_p().

Referenced by effects_must_conflict_p(), and points_to_cell_lists_must_conflict_p().

Here is the call graph for this function:

Here is the caller graph for this function:

concrete_effects_entities_which_may_conflict_with_scalar_entity()

list concrete_effects_entities_which_may_conflict_with_scalar_entity	(	list	fx,
		entity	e
	)

Parameters

fx

x

Definition at line 1278 of file conflicts.c.

{
  return generic_effects_entities_which_may_conflict_with_scalar_entity(fx, e, true);
}

References generic_effects_entities_which_may_conflict_with_scalar_entity().

Referenced by precondition_intra_to_inter().

Here is the call graph for this function:

Here is the caller graph for this function:

concrete_effects_may_read_or_write_scalar_entity_p()

bool concrete_effects_may_read_or_write_scalar_entity_p	(	list	fx,
		entity	e
	)

Parameters

fx

x

Definition at line 1220 of file conflicts.c.

{
  bool read_or_write = concrete_effects_maymust_read_or_write_scalar_entity_p(fx, e, false);
  return read_or_write;
}

References concrete_effects_maymust_read_or_write_scalar_entity_p(), and read_or_write().

Referenced by generic_transformer_intra_to_inter().

Here is the call graph for this function:

Here is the caller graph for this function:

concrete_effects_maymust_read_or_write_scalar_entity_p()

bool concrete_effects_maymust_read_or_write_scalar_entity_p	(	list	fx,
		entity	e,
		bool	must_p
	)

Parameters

fx	x
must_p	ust_p

Definition at line 1202 of file conflicts.c.

{
  return generic_effects_maymust_read_or_write_scalar_entity_p(fx, e, must_p, true);
}

References generic_effects_maymust_read_or_write_scalar_entity_p().

Referenced by concrete_effects_may_read_or_write_scalar_entity_p().

Here is the call graph for this function:

Here is the caller graph for this function:

effect_may_read_or_write_memory_paths_from_entity_p()

bool effect_may_read_or_write_memory_paths_from_entity_p	(	effect	ef,
		entity	e
	)

misc functions

tests whether the input effect has a memory path from the input entity e; this is currently a mere syntactic test.

other strategies could be implemented, such as building all the memory locations reachable from "e" using generic_effect_generate_all_accessible_paths_effects_with_level, and then testing whether in the resulting effects there is an effect which may conflict with en effect from the input list. However, this would be very costly.

Parameters

ef

f

Definition at line 1103 of file conflicts.c.

{
  bool read_or_write = false;
  if(entity_variable_p(e))
    {
      entity e_used = reference_variable(effect_any_reference(ef));
      if(store_effect_p(ef) && same_entity_p(e, e_used))
        {
          read_or_write = true;
        }
    }
 
  return read_or_write;
}

References effect_any_reference, entity_variable_p, read_or_write(), reference_variable, same_entity_p(), and store_effect_p().

Referenced by effects_may_read_or_write_memory_paths_from_entity_p(), and mask_effects().

Here is the call graph for this function:

Here is the caller graph for this function:

effects_conflict_p()

bool effects_conflict_p	(	effect	eff1,
		effect	eff2
	)

Synonym for effects_may_conflict_p().

@description Name preserved to limit rewriting of source code using the old version. Also checks results of new implementation wrt the old implementation FIXME : to be removed: was never used until now !

In general, there is no reason to have the same results... This is only a first debugging step.

Parameters

eff1	ff1
eff2	ff2

Definition at line 246 of file conflicts.c.

                                                    {
  bool conflict_p = effects_may_conflict_p( eff1, eff2 );
  bool old_conflict_p = old_effects_conflict_p( eff1, eff2 );
 
  /* In general, there is no reason to have the same results... This
   is only a first debugging step. */
  if ( conflict_p != old_conflict_p )
    pips_internal_error("Inconsistent conflict detection.");
 
  return conflict_p;
}

References effects_may_conflict_p(), old_effects_conflict_p(), and pips_internal_error.

Here is the call graph for this function:

effects_entities_which_may_conflict_with_scalar_entity()

list effects_entities_which_may_conflict_with_scalar_entity	(	list	fx,
		entity	e
	)

Parameters

fx

x

Definition at line 1273 of file conflicts.c.

{
  return generic_effects_entities_which_may_conflict_with_scalar_entity(fx, e, false);
}

References generic_effects_entities_which_may_conflict_with_scalar_entity().

Here is the call graph for this function:

effects_may_conflict_p()

bool effects_may_conflict_p	(	effect	eff1,
		effect	eff2
	)

Check if two effect may conflict @description Two effects may conflict if their abstract two location sets has a non-empty intersection and if at least one of them is a write.

This function is conservative: it is always correct to declare a conflict.

Parameters

eff1	ff1
eff2	ff2

Definition at line 162 of file conflicts.c.

                                                        {
  action ac1 = effect_action(eff1);
  action ac2 = effect_action(eff2);
  bool conflict_p = true;
 
  if ( action_read_p(ac1) && action_read_p(ac2) ) {
    // Two read won't conflict
    conflict_p = false;
  } else {
    conflict_p = effects_might_conflict_even_read_only_p(eff1,eff2);
  }
  return conflict_p;
}

References action_read_p, effect_action, and effects_might_conflict_even_read_only_p().

Referenced by conflict_is_a_real_conflict_p(), effects_conflict_p(), and two_addresses_code_generator().

Here is the call graph for this function:

Here is the caller graph for this function:

effects_may_read_or_write_memory_paths_from_entity_p()

bool effects_may_read_or_write_memory_paths_from_entity_p	(	list	l_eff,
		entity	e
	)

tests whether the input effects list may contain effects with a memory path from the input entity e; this is currently a mere syntactic test.

other strategies could be implemented, such as building all the memory locations reachable from "e" using generic_effect_generate_all_accessible_paths_effects_with_level, and then testing whether in the resulting effects there is an effect which may conflict with en effect from the input list. However, this would be very costly.

Parameters

l_eff

_eff

Definition at line 1130 of file conflicts.c.

{
  bool read_or_write = false;
  if(entity_variable_p(e))
    {
      FOREACH(EFFECT, ef, l_eff)
        {
          read_or_write = effect_may_read_or_write_memory_paths_from_entity_p(ef, e);
          if (read_or_write) break;
        }
    }
  return read_or_write;
}

References EFFECT, effect_may_read_or_write_memory_paths_from_entity_p(), entity_variable_p, FOREACH, and read_or_write().

Referenced by compute_one_summary_reduction(), and compute_summary_reductions().

Here is the call graph for this function:

Here is the caller graph for this function:

effects_may_read_or_write_scalar_entity_p()

bool effects_may_read_or_write_scalar_entity_p	(	list	fx,
		entity	e
	)

check whether scalar entity e may be read or written by effects fx or cannot be accessed at all

In semantics, e can be a functional entity such as constant string or constant float.

Parameters

fx

x

Definition at line 1214 of file conflicts.c.

{
  bool read_or_write = effects_maymust_read_or_write_scalar_entity_p(fx, e, false);
  return read_or_write;
}

References effects_maymust_read_or_write_scalar_entity_p(), and read_or_write().

Referenced by generic_transformer_intra_to_inter().

Here is the call graph for this function:

Here is the caller graph for this function:

effects_maymust_read_or_write_scalar_entity_p()

bool effects_maymust_read_or_write_scalar_entity_p	(	list	fx,
		entity	e,
		bool	must_p
	)

Parameters

fx	x
must_p	ust_p

Definition at line 1197 of file conflicts.c.

{
  return generic_effects_maymust_read_or_write_scalar_entity_p(fx, e, must_p, false);
}

References generic_effects_maymust_read_or_write_scalar_entity_p().

Referenced by effects_may_read_or_write_scalar_entity_p(), and effects_must_read_or_write_scalar_entity_p().

Here is the call graph for this function:

Here is the caller graph for this function:

effects_might_conflict_even_read_only_p()

bool effects_might_conflict_even_read_only_p	(	effect	eff1,
		effect	eff2
	)

Check if two effect might conflict, even if they are read only @description Two effects may conflict if their abstract two location sets has a non-empty intersection.

This function is conservative: it is always correct to declare a conflict.

For environment and type declarations, the references are empty and the conflict is only based on the referenced entity

Parameters

eff1	ff1
eff2	ff2

Definition at line 123 of file conflicts.c.

                                                                       {
  action ac1 = effect_action(eff1);
  action ac2 = effect_action(eff2);
  bool conflict_p = true;
 
  action_kind ak1 = action_to_action_kind(ac1);
  action_kind ak2 = action_to_action_kind(ac2);
 
  if(action_kind_tag(ak1) != action_kind_tag(ak2)) {
    // A store mutation cannot conflict with an environment or type
    // declaration mutation
    conflict_p = false;
  } else {
    if(action_kind_store_p(ak1)) {
      cell cell1 = effect_cell(eff1);
      cell cell2 = effect_cell(eff2);
      if(!cells_may_conflict_p(cell1, cell2)) {
        conflict_p = false;
      }
    } else {
      /* For environment and type declarations, the references are
       empty and the conflict is only based on the referenced
       entity */
      entity v1 = effect_variable(eff1);
      entity v2 = effect_variable(eff2);
      conflict_p = v1 == v2;
    }
  }
  return conflict_p;
}

References action_kind_store_p, action_kind_tag, action_to_action_kind(), cells_may_conflict_p(), effect_action, effect_cell, and effect_variable.

Referenced by add_conflicts(), and effects_may_conflict_p().

Here is the call graph for this function:

Here is the caller graph for this function:

effects_must_conflict_p()

bool effects_must_conflict_p	(	effect	eff1,
		effect	eff2
	)

Intersection tests.

Check if two effects always conflict. @descriptionTwo effects will always conflict if their two abstract locations has a non-empty intersection and if at least one of them is a write. The approximation must also be "MUST", if one of them is a "MAY" there is no conflict

This function is conservative: it is always correct not to declare a conflict.

Returns

true if there is always a conflict between eff1 and eff2

We enforce must approximation for the two effects

We enforce that at least one effect is a write

Check that the cells conflicts

Parameters

eff1	ff1
eff2	ff2

Definition at line 93 of file conflicts.c.

                                                         {
  action ac1 = effect_action(eff1);
  action ac2 = effect_action(eff2);
  approximation ap1 = effect_approximation(eff1);
  approximation ap2 = effect_approximation(eff2);
  bool conflict_p = false;
 
  /* We enforce must approximation for the two effects */
  if ( approximation_exact_p(ap1) && approximation_exact_p(ap2) ) {
    /* We enforce that at least one effect is a write */
    if ( action_write_p(ac1) || action_write_p(ac2) ) {
      cell cell1 = effect_cell(eff1);
      cell cell2 = effect_cell(eff2);
      /* Check that the cells conflicts */
      if ( cells_must_conflict_p( cell1, cell2 ) ) {
        conflict_p = true;
      }
    }
  }
  return conflict_p;
}

References action_write_p, approximation_exact_p, cells_must_conflict_p(), effect_action, effect_approximation, and effect_cell.

Here is the call graph for this function:

effects_must_read_or_write_scalar_entity_p()

bool effects_must_read_or_write_scalar_entity_p	(	list	fx,
		entity	e
	)

check whether scalar entity e must be read or written by any effect of fx or if it simply might be accessed.

In semantics, e can be a functional entity such as constant string or constant float.

Parameters

fx

x

Definition at line 1235 of file conflicts.c.

{
  bool read_or_write = effects_maymust_read_or_write_scalar_entity_p(fx, e, false);
  return read_or_write;
}

References effects_maymust_read_or_write_scalar_entity_p(), and read_or_write().

Here is the call graph for this function:

entities_may_conflict_p()

bool entities_may_conflict_p	(	entity	e1,
		entity	e2
	)

Check if two entities may conflict.

Parameters

e1	1
e2	2

Definition at line 984 of file conflicts.c.

                                                     {
  return entities_maymust_conflict_p( e1, e2, false);
}

References entities_maymust_conflict_p().

Referenced by add_conflicts(), add_implicit_interprocedural_write_effects(), add_or_kill_equivalenced_variables(), apply_abstract_effect_to_transformer(), check_for_effected_statement(), direct_written_reference(), effects_read_variable_p(), effects_write_variable_p(), entity_may_conflict_with_a_formal_parameter_p(), find_covering_reference_path(), find_reduction_of_var(), functionnal_on_effects(), generic_effects_entities_which_may_conflict_with_scalar_entity(), generic_effects_maymust_read_or_write_scalar_entity_p(), get_effect_read_of_statement_on_variable(), get_effect_write_of_statement_on_variable(), initialize_and_verify_common_variable(), interference_on(), list_of_same_or_equivalence_arguments(), no_other_effects_on_references(), no_write_effects_on_var(), old_effects_conflict_p(), points_to_cells_intersect_p(), reference_rwt(), references_may_conflict_p(), remove_unread_variable(), there_is_a_conflict(), transformer_general_consistency_p(), update_compatible_reduction(), update_compatible_reduction_with(), update_reduction_under_effect(), value_alias(), and verify_formal_and_common_variables().

Here is the call graph for this function:

Here is the caller graph for this function:

entities_maymust_conflict_p()

bool entities_maymust_conflict_p	(	entity	e1,
		entity	e2,
		bool	must_p
	)

Check if two entities may or must conflict.

FI->MA: we certainly said a lot more during the February 2010 meeting, when abstract locations were added. And now we have store and type declaration dependencies...

Parameters

must_p

define if we enforce must conflict or only may one

Be careful because entity_variable_p(e) does not guarantee that e is a variable defined by the programmer. Maybe another function is needed to make sure that the conversion to an abstract location generates a useful result... variable_entity_p() is not necessarily good either because it uses the entity storage to make a decision. Formal parameters and return values are not taken into account.

There no abstract locations for formal parameters and return values, which may not be a good idea if C let you pick up the address of a formal parameter. They have to be handled in a specific way.

Beware: this function should only be used for scalar entities. however, I do not add an assert for this time, because I don't yet know what damages it may cause...

Constant strings may be tested because they are used to represent the underlying buffers. The effect should always be a read effect.

FI: Either we need an new abstract location for the formal parameters or we need to deal explictly with this case here and declare conflict with anywhere.

FIXME : variable_entity_must_conflict_p does not exist yet

A must conflict is useful to guarantee a kill, but this shows that it is not related to the definition of the may case: two variables may share exactly the same set of memory locations but a reference to one of them does not necessarily imply that all locations are read or written. More comments (thinking) are needed to distinguish between entity and reference conflicts.

We assume that e1 and e2 are program variables. Because we do not have enough comments, we do not know if this only hold for variables and arrays of one element. It is easy to argue that an array cannot must conflict with itself. The test below does not solve the case of struct, and maybe union.

FI: should always be the case here but a struct variable is a scalar, as well as the location entities representing its field. They are aliased as equivalenced Fortran variables. The case of struct and struct field can be solved at a higher level by converting effects to their location entities when it makes sense instead of relying on the effect base variable.

FI: we end up here if references linked to environment or type declarations are tested for conflicts. Should we perform such tests, basically e1==e2, or assume that they should have been handled at a higher level?

There are no conflicts between entities of different kinds

Since this implies e1!=e2, this case could be merged with the next one, but the spec would be less clear

Environment and type declaration conflicts imply that the very same entity is involved.

Parameters

e1	1
e2	2
must_p	ust_p

Definition at line 771 of file conflicts.c.

{
  bool conflict_p = !must_p; // safe default value
 
  // effects package entities are not usual variables
  if (effects_package_entity_p(e1) || effects_package_entity_p(e2))
    conflict_p = (e1 == e2);
  // idem with "register" variables which are in a world of their own
  else if (entity_register_p(e1) || entity_register_p(e2))
    conflict_p = (e1 == e2);
  /* Constant strings may be tested because they are used to represent
     the underlying buffers. The effect should always be a read effect. */
  else if(constant_string_entity_p(e1) || constant_string_entity_p(e2))
    conflict_p = (e1 == e2);
  // With location entities, we may have static aliasing in C
  else if (!c_module_p(get_current_module_entity())) {
    pips_debug(5, "fortran case, C case with semantics constant path analysis\n");
    if (same_entity_p(e1, e2))
      conflict_p = true;
    else
      conflict_p = must_p ? false : variable_entities_may_conflict_p( e1, e2 );
  }
  else if(location_entity_p(e1)) {
    if(location_entity_p(e2)) {
      // No aliasing between locations
      conflict_p = e1==e2;
    }
    else {
      if(entity_abstract_location_p(e2)) {
        if(entity_anywhere_locations_p(e2)) {
          // This entity seems to have type area and not type overloaded
          // as expected from the lattice
          conflict_p = !must_p;
        }
        else {
          type t1 = entity_basic_concrete_type(e1);
          type t2 = entity_basic_concrete_type(e2);
          // FI: how about type_overloaded_p(t1)
          conflict_p = !must_p && (overloaded_type_p(t2) || type_equal_p(t1, t2));
        }
      }
      else {
        value v1 = entity_initial(e1);
        reference r1 = value_reference(v1);
        entity ne1 = reference_variable(r1);
        conflict_p =  entities_maymust_conflict_p(ne1, e2, must_p );
      }
    }
  }
  else if(location_entity_p(e2)) {
    if(entity_abstract_location_p(e1)) {
      if(entity_anywhere_locations_p(e1)) {
        // This entity seems to have type area and not type overloaded
        // as expected from the lattice
        conflict_p = !must_p;
      }
      else {
        type t1 = entity_basic_concrete_type(e1);
        type t2 = entity_basic_concrete_type(e2);
        // FI: the type lattice should be used
        conflict_p = !must_p && (overloaded_type_p(t1) || type_equal_p(t1, t2));
      }
    }
    else {
      value v2 = entity_initial(e2);
      reference r2 = value_reference(v2);
      entity ne2 = reference_variable(r2);
      conflict_p =  entities_maymust_conflict_p(e1, ne2, must_p );
    }
  }
  else {
    // these are costly function calls; call them only once.
    bool e1_abstract_location_p = entity_abstract_location_p( e1 );
    bool e2_abstract_location_p = entity_abstract_location_p( e2 );
 
    bool (*abstract_locations_conflict_p)(entity,entity);
    abstract_locations_conflict_p =
      must_p ? abstract_locations_must_conflict_p :
      abstract_locations_may_conflict_p;
 
    if (e1_abstract_location_p && e2_abstract_location_p)
    {
      // two abstract locations
      conflict_p = abstract_locations_conflict_p( e1, e2 );
    }
    else if (e1_abstract_location_p || e2_abstract_location_p)
    {
      // one abstract location and a concrete one
      entity abstract_location = e1_abstract_location_p? e1 : e2;
      entity concrete_location = e1_abstract_location_p? e2 : e1;
 
      if (entity_null_locations_p(concrete_location))
        conflict_p = entity_all_locations_p(abstract_location);
 
      else if ( type_variable_p(entity_basic_concrete_type(concrete_location)) )
            {
              if ( variable_return_p( concrete_location ) )
        {
          conflict_p = false;
        }
              else if ( entity_formal_p( concrete_location ) )
        {
          /* FI: Either we need an new abstract location for the formal
             parameters or we need to deal explictly with this case
             here and declare conflict with *anywhere*. */
          conflict_p = entity_all_locations_p(abstract_location);
          if(!conflict_p) {
            entity concrete_location_al =
              variable_to_abstract_location(concrete_location);
            conflict_p = abstract_locations_conflict_p(abstract_location,
                                                       concrete_location_al);
          }
        }
              else
        {
          entity concrete_location_al =
            variable_to_abstract_location(concrete_location);
          conflict_p = abstract_locations_conflict_p(abstract_location,
                                                     concrete_location_al);
        }
            }
      else if(entity_function_p(concrete_location)) {
              pips_internal_error("Meaningless conflict tested for function \"%s\".",
                            entity_user_name(concrete_location));
      }
      else
            {
              pips_internal_error("Unexpected case for variable \"%s\".",
                            entity_user_name(concrete_location));
            }
    }
    else
    {
      // two concrete locations
      if ( variable_return_p( e1 ) && variable_return_p( e2 ) )
            {
              conflict_p =  same_entity_p(e1,e2);
            }
      else if ( entity_formal_p( e1 ) && entity_formal_p( e2 ) )
            {
              conflict_p = same_entity_p(e1,e2);
            }
      else if( entity_null_locations_p(e1) || entity_null_locations_p(e2) )
            {
              conflict_p = same_entity_p(e1,e2);
            }
      else if ( type_variable_p(entity_basic_concrete_type(e1)) && type_variable_p(entity_basic_concrete_type(e2)) )
            {
              /* FIXME : variable_entity_must_conflict_p does not exist yet */
              if( !must_p)
                {
          conflict_p = variable_entities_may_conflict_p( e1, e2 );
                }
              else
                {
          /* A must conflict is useful to guarantee a kill, but this
             shows that it is not related to the definition of the
             may case: two variables may share exactly the same set
             of memory locations but a reference to one of them does
             not necessarily imply that all locations are read or
             written. More comments (thinking) are needed to
             distinguish between entity and reference conflicts. */
          /* We assume that e1 and e2 are program variables. Because
             we do not have enough comments, we do not know if this
             only hold for variables and arrays of one element. It is
             easy to argue that an array cannot must conflict with
             itself. The test below does not solve the case of
             struct, and maybe union. */
                  if(entity_scalar_p(e1)) {
                    /* FI: should always be the case here but a struct
                     * variable is a scalar, as well as the location
                     * entities representing its field. They are
                     * aliased as equivalenced Fortran variables. The
                     * case of struct and struct field can be solved
                     * at a higher level by converting effects to
                     * their location entities when it makes sense
                     * instead of relying on the effect base
                     * variable. */ 
                    conflict_p = same_entity_p(e1,e2);
                  }
                  else
                    conflict_p = false;
                }
            }
      else
        {
              /* FI: we end up here if references linked to environment or
           type declarations are tested for conflicts. Should we
           perform such tests, basically e1==e2, or assume that they
           should have been handled at a higher level? */
              if(!variable_entity_p(e1) || variable_entity_p(e2))
        {
          /* There are no conflicts between entities of different
             kinds */
          /* Since this implies e1!=e2, this case could be merged
             with the next one, but the spec would be less clear */
          conflict_p = false;
        }
              else {
          /* Environment and type declaration conflicts imply that
             the very same entity is involved. */
          conflict_p = same_entity_p(e1,e2);
              }
            }
    } // end: two concrete locations
  }
  return conflict_p;
}

References abstract_locations_may_conflict_p(), abstract_locations_must_conflict_p(), c_module_p(), constant_string_entity_p(), effects_package_entity_p(), entity_abstract_location_p(), entity_all_locations_p(), entity_anywhere_locations_p(), entity_basic_concrete_type(), entity_formal_p(), entity_function_p(), entity_initial, entity_null_locations_p(), entity_register_p(), entity_scalar_p(), entity_user_name(), false, get_current_module_entity(), location_entity_p(), overloaded_type_p(), pips_debug, pips_internal_error, reference_variable, same_entity_p(), type_equal_p(), type_variable_p, value_reference, variable_entities_may_conflict_p(), variable_entity_p(), variable_return_p(), and variable_to_abstract_location().

Referenced by entities_may_conflict_p(), and entities_must_conflict_p().

Here is the call graph for this function:

Here is the caller graph for this function:

entities_must_conflict_p()

bool entities_must_conflict_p	(	entity	e1,
		entity	e2
	)

Check if two entities must conflict.

Parameters

e1	1
e2	2

Definition at line 992 of file conflicts.c.

                                                      {
  return entities_maymust_conflict_p( e1, e2, true);
}

References entities_maymust_conflict_p().

Referenced by generic_effects_maymust_read_or_write_scalar_entity_p(), references_must_conflict_p(), and remove_unread_variable().

Here is the call graph for this function:

Here is the caller graph for this function:

first_cell_certainly_includes_second_cell_p()

static bool first_cell_certainly_includes_second_cell_p ( cell  c1, cell  c2  )

static

tests whether first cell certainly includes second one

See also

first_effect_certainly_includes_second_effect_p

safe result

Definition at line 1026 of file conflicts.c.

{
  bool cell1_certainly_includes_cell2_p = false; /* safe result */
 
  reference r1 = cell_to_reference(c1);
  reference r2 = cell_to_reference(c2);
 
  cell1_certainly_includes_cell2_p = first_reference_certainly_includes_second_reference_p(r1, r2);
  return cell1_certainly_includes_cell2_p;
}

References cell_to_reference(), and first_reference_certainly_includes_second_reference_p().

Referenced by first_effect_certainly_includes_second_effect_p(), and first_exact_scalar_effect_certainly_includes_second_effect_p().

Here is the call graph for this function:

Here is the caller graph for this function:

first_effect_certainly_includes_second_effect_p()

bool first_effect_certainly_includes_second_effect_p	(	effect	eff1,
		effect	eff2
	)

tests whether first effect certainly includes second one.

The effects are not necessarily functions of the same store.

This means that a[i]-exact does not necessarily contains a[i]-exact because i may not have the same value in the store to which the effects refer. This is the case for instance in the following code:

i = 1; a[i] = ...; // S1 i = 2; a[i] = ...; // S2

The assignment in S2 does not kill the assignment in S2;

This function could be improved for convex effects by eliminating from Psystems program variables which are not common inclosing loop variants. this would require much more information than what we currently have.

So in all cases, the function safely returns false for effects described with access paths which are not single entities.

safe result

Parameters

eff1	ff1
eff2	ff2

Definition at line 1060 of file conflicts.c.

{
  bool eff1_certainly_includes_eff2_p = false; /* safe result */
 
  if ( effect_exact_p(eff1) && effect_scalar_p(eff1)
       && effect_scalar_p(eff2)
       && first_cell_certainly_includes_second_cell_p(effect_cell(eff1), effect_cell(eff2)))
    {
      eff1_certainly_includes_eff2_p = true;
    }
 
  return eff1_certainly_includes_eff2_p;
}

References effect_cell, effect_exact_p, effect_scalar_p(), and first_cell_certainly_includes_second_cell_p().

Here is the call graph for this function:

first_exact_scalar_effect_certainly_includes_second_effect_p()

bool first_exact_scalar_effect_certainly_includes_second_effect_p	(	effect	eff1,
		effect	eff2
	)

safe result

Parameters

eff1	ff1
eff2	ff2

Definition at line 1074 of file conflicts.c.

{
  bool eff1_certainly_includes_eff2_p = false; /* safe result */
 
  if ( effect_scalar_p(eff2)
      && first_cell_certainly_includes_second_cell_p(effect_cell(eff1), effect_cell(eff2)))
    {
      pips_assert("the first effect is an exact and scalar effect",
                  effect_exact_p(eff1) && effect_scalar_p(eff1));
      eff1_certainly_includes_eff2_p = true;
    }
 
  return eff1_certainly_includes_eff2_p;
}

References effect_cell, effect_exact_p, effect_scalar_p(), first_cell_certainly_includes_second_cell_p(), and pips_assert.

Referenced by kill_effects().

Here is the call graph for this function:

Here is the caller graph for this function:

first_reference_certainly_includes_second_reference_p()

static bool first_reference_certainly_includes_second_reference_p ( reference  r1, reference  r2  )

static

Inclusion tests.

I'm not sure that testing must conflicts makes much sense with sets of memory locations. We cannot well define a symmetrical semantics. However, testing the inclusion makes sense! BC. tests whether first reference certainly includes second one

See also

first_effect_certainly_includes_second_effect_p

safe result

Definition at line 1010 of file conflicts.c.

{
  bool r1_certainly_includes_r2_p = false; /* safe result */
 
  if (  same_entity_p(reference_variable(r1), reference_variable(r2)) &&
          reference_scalar_p(r1) && reference_scalar_p(r2) )
    r1_certainly_includes_r2_p = true;
 
  return r1_certainly_includes_r2_p;
}

References reference_scalar_p(), reference_variable, and same_entity_p().

Referenced by first_cell_certainly_includes_second_cell_p().

Here is the call graph for this function:

Here is the caller graph for this function:

generic_effects_entities_which_may_conflict_with_scalar_entity()

static list generic_effects_entities_which_may_conflict_with_scalar_entity ( list  fx, entity  e, bool  concrete_p  )

static

Returns the list of entities used in effect list fx and potentially conflicting with e.

Of course, abstract location entities do conflict with many entities, possibly of different types.

if concrete_p==true, ignore abstract location entities.

Definition at line 1251 of file conflicts.c.

{
  list lconflict_e = NIL;
 
  FOREACH(EFFECT, ef, fx)
    {
      entity e_used = reference_variable(effect_any_reference(ef));
      if(!(entity_abstract_location_p(e_used) && concrete_p))
        {
          if(entities_may_conflict_p(e, e_used))
            {
              lconflict_e = gen_nconc(lconflict_e,
                                      CONS(ENTITY, e_used, NIL));
            }
        }
    }
 
  return lconflict_e;
}

References CONS, EFFECT, effect_any_reference, entities_may_conflict_p(), ENTITY, entity_abstract_location_p(), FOREACH, gen_nconc(), NIL, and reference_variable.

Referenced by concrete_effects_entities_which_may_conflict_with_scalar_entity(), and effects_entities_which_may_conflict_with_scalar_entity().

Here is the call graph for this function:

Here is the caller graph for this function:

generic_effects_maymust_read_or_write_scalar_entity_p()

bool generic_effects_maymust_read_or_write_scalar_entity_p	(	list	fx,
		entity	e,
		bool	must_p,
		bool	concrete_p
	)

Used to be a simple pointer equality test, but now we have to cope with abstract locations.

Parameters

fx	x
must_p	ust_p
concrete_p	oncrete_p

Definition at line 1144 of file conflicts.c.

{
  bool read_or_write = false;
  
  if(location_entity_p(e)) {
    reference lr = value_reference(entity_initial(e));
    FOREACH(EFFECT, ef, fx) {
      reference r = effect_any_reference(ef);
      if(must_p)
        read_or_write = references_must_conflict_p(r, lr);
      else
        read_or_write = references_may_conflict_p(r, lr);
      if(read_or_write)
        break;
    }
  }
  else if(entity_variable_p(e) && entity_scalar_p(e)) {
    FOREACH(EFFECT, ef, fx) {
      reference r = effect_any_reference(ef);
      entity e_used = entity_undefined;
      if(ENDP(reference_indices(r)))
        e_used = reference_variable(r);
      else {
        // FI: we are in effects-util and do no know if the semantics
        // analysis is using or not location entities...
        // is r a constant memory access path ?
        e_used = constant_memory_access_path_to_location_entity(r);
        if(entity_undefined_p(e_used))
          e_used = reference_variable(r);
      }
      if(!concrete_p || !entity_abstract_location_p(e_used)) {
        /* Used to be a simple pointer equality test, but now we have to
           cope with abstract locations. */
        if(store_effect_p(ef)) {
          if(must_p) {
            if(entity_scalar_p(e_used) && entities_must_conflict_p(e, e_used)) {
              read_or_write = true;
              break;
            }
          }
          else {
            if(entities_may_conflict_p(e, e_used)) {
              read_or_write = true;
              break;
            }
          }
        }
      }
    }
  }
  return read_or_write;
}

References constant_memory_access_path_to_location_entity(), EFFECT, effect_any_reference, ENDP, entities_may_conflict_p(), entities_must_conflict_p(), entity_abstract_location_p(), entity_initial, entity_scalar_p(), entity_undefined, entity_undefined_p, entity_variable_p, FOREACH, location_entity_p(), read_or_write(), reference_indices, reference_variable, references_may_conflict_p(), references_must_conflict_p(), store_effect_p(), and value_reference.

Referenced by concrete_effects_maymust_read_or_write_scalar_entity_p(), and effects_maymust_read_or_write_scalar_entity_p().

Here is the call graph for this function:

Here is the caller graph for this function:

old_effects_conflict_p()

static bool old_effects_conflict_p ( effect  eff1, effect  eff2  )

static

OBSOLETE, was never used !!

Do we point to the same area?

We do not bother with the offset and the array types

Definition at line 180 of file conflicts.c.

                                                               {
  action ac1 = effect_action(eff1);
  action ac2 = effect_action(eff2);
  bool conflict_p = false;
 
  if ( action_write_p(ac1) || action_write_p(ac2) ) {
    if ( anywhere_effect_p( eff1 ) || anywhere_effect_p( eff2 ) )
      conflict_p = true;
    else {
 
      reference r1 = effect_any_reference(eff1);
      entity v1 = reference_variable(r1);
      reference r2 = effect_any_reference(eff2);
      entity v2 = reference_variable(r2);
 
      /* Do we point to the same area? */
 
      if ( entities_may_conflict_p( v1, v2 ) ) {
        list ind1 = reference_indices(r1);
        list ind2 = reference_indices(r2);
        list cind1 = list_undefined;
        list cind2 = list_undefined;
 
        if ( v1 != v2 ) {
          /* We do not bother with the offset and the array types */
          conflict_p = true;
        } else {
          if ( !ENDP(ind1) && !ENDP(ind2) ) {
            for ( cind1 = ind1, cind2 = ind2; !ENDP(cind1) && !ENDP(cind2); POP(cind1), POP(cind2) ) {
              expression e1 = EXPRESSION(CAR(cind1));
              expression e2 = EXPRESSION(CAR(cind2));
              if ( unbounded_expression_p( e1 ) || unbounded_expression_p( e2 ) )
                conflict_p = true;
              else {
                intptr_t i1 = -1;
                intptr_t i2 = -1;
                bool i1_p = false;
                bool i2_p = false;
 
                i1_p = expression_integer_value( e1, &i1 );
                i2_p = expression_integer_value( e2, &i2 );
                if ( i1_p && i2_p )
                  conflict_p = ( i1 == i2 );
                else
                  conflict_p = true;
              }
            }
          } else
            conflict_p = true;
        }
      }
 
      else
        conflict_p = true;
    }
  }
  return conflict_p;
}

References action_write_p, anywhere_effect_p(), CAR, effect_action, effect_any_reference, ENDP, entities_may_conflict_p(), EXPRESSION, expression_integer_value(), intptr_t, list_undefined, POP, reference_indices, reference_variable, and unbounded_expression_p().

Referenced by effects_conflict_p().

Here is the call graph for this function:

Here is the caller graph for this function:

points_to_cell_lists_may_conflict_p()

bool points_to_cell_lists_may_conflict_p	(	list	l1,
		list	l2
	)

Same as above, but for lists.

Lists conflict if there exist at least one element in l1 and one element in l2 that conflict.

Parameters

l1	1
l2	2

Definition at line 703 of file conflicts.c.

{
  bool conflict_p = false;
  FOREACH(CELL, c1, l1) {
    FOREACH(CELL, c2, l2) {
      if(cells_may_conflict_p(c1, c2)) {
        conflict_p = true;
        break;
      }
    }
    if(conflict_p)
      break;
  }
  return conflict_p;
}

References CELL, cells_may_conflict_p(), and FOREACH.

Referenced by aliased_translation_p().

Here is the call graph for this function:

Here is the caller graph for this function:

points_to_cell_lists_must_conflict_p()

bool points_to_cell_lists_must_conflict_p	(	list	l1,
		list	l2
	)

Same as above, but for lists.

Lists conflict if there exist at least one element in l1 and one element in l2 that must conflict.

Parameters

l1	1
l2	2

Definition at line 729 of file conflicts.c.

{
  bool conflict_p = false;
  FOREACH(CELL, c1, l1) {
    FOREACH(CELL, c2, l2) {
      if(cells_must_conflict_p(c1, c2)) {
        conflict_p = true;
        break;
      }
    }
    if(conflict_p)
      break;
  }
  return conflict_p;
}

References CELL, cells_must_conflict_p(), and FOREACH.

Referenced by aliased_translation_p().

Here is the call graph for this function:

Here is the caller graph for this function:

references_may_conflict_p()

bool references_may_conflict_p	(	reference	r1,
		reference	r2
	)

Check if two references may conflict.

@description Can the two references r1 and r2 access the same memory location when evaluated in two different stores?

We have to deal with static aliasing for Fortran and with dynamic aliasing for C and Fortran95.

We have to deal with abstract locations used to represent sets of memory locations.

A PIPS reference is a memory access path rather than a reference as understood in programming languages:

• a field of a struct or a union d can be accessed by subscripting d with a field number or with a field entity
• a dereferencing is expressed by a zero subscript: *p is p[0]
• abstract locations such as foo:HEAP or foo:HEAP**MEMORY or foo:HEAP_v3 can be used
• heap modelization uses the malloc statement number as a subscript
• flow-sensitive heap modelization can use indices from the surrounding loops as subscripts
• context-sensitive heap modelization can also use function reference to record the call path

Three bool properties are involved:

• ALIASING_ACROSS_TYPES: if false objects of different types cannot be aliased
• ALIASING_INSIDE_DATA_STRUCTURE: if false, access paths starting from the same data structure are assumed disjoint as soon as they differ. This property holds even after pointer dereferencement. It is extremely strong and wrong for PIPS source code, unless persistant is taken into account.
• ALIASING_ACROSS_FORMAL_PARAMETERS: if false, access paths starting from different parameters cannot conflict.

calling entities_may_conflict_p is only valid for scalar entities

here, we have either two concrete locations, one of which at least has indices, or one abstract location and one concrete location with indices. BC

I'm not completely sure of that. Are numbered heap locations considered as abstract locations? And they may have indices. Heap locations testing is a mess. BC.

FI: Can we have some dynamic aliasing?

Do we have aliasing between types?

Do we have aliasing within a data structure? This should have been checked above with variable_references_may_conflict_p(v1,ind1,ind2)

A patch for effects_package references, which cannot conflict with user variables

well, strictly speaking, couldn't they conflict with an anywhere:anywhere effect? but then there should be other conflicts...

string operations are costly - perform them only once

well type_equal_p does not perform a good job :-( BC

should ALIASING_ACROSS_DATA_STRUCTURES be also tested here?

Do we have some dereferencing in ind1 or ind2? Do we assume that p[0] conflicts with any reference? We might as well use reference_to_abstract_location()...

Could be improved with ALIASING_ACROSS_DATA_STRUCTURES?

We need to evaluate dereferencing in r2 only when a dereferencing have not been find in r1

In other words, we assume no conflict as soon as no pointer is dereferenced... even when aliasing across types is not ignored !

If aliasing across types is ignored, we know here that the two memory locations referenced are of the same type. If the pointer in one reference (let's assume only one pointer to start with) is not of type pointer to the common type, then there is no conflict.

Else, we have to assume a conflict no matter what, because simple cases should have been simplified via the points-to analysis.

Parameters

r1	1
r2	2

Definition at line 426 of file conflicts.c.

                                                             {
  bool conflict_p = true; // In doubt, conflict is assumed
  entity e1 = reference_variable(r1);
  entity e2 = reference_variable(r2);
  list ind1 = reference_indices(r1);
  list ind2 = reference_indices(r2);
  bool get_bool_property( string );
 
  pips_debug(5, " %s vs %s\n", effect_reference_to_string(r1), effect_reference_to_string(r2));
 
  if (!c_module_p(get_current_module_entity()))
    {
      pips_debug(5, "fortran case\n");
      if (same_entity_p(e1, e2))
        conflict_p = variable_references_may_conflict_p( e1, ind1, ind2 );
      else
        conflict_p =  variable_entities_may_conflict_p( e1, e2 );
    }
  else if (ENDP(ind1) && ENDP(ind2))   /* calling entities_may_conflict_p is only valid for scalar entities */
    {
      pips_debug(5, "scalar case\n");
      conflict_p = entities_may_conflict_p( e1, e2 );
    }
  else
    {
      /* here, we have either two concrete locations, one of which at least has indices,
         or one abstract location and one concrete location with indices. BC
      */
      /* I'm not completely sure of that. Are numbered heap locations considered as abstract locations?
         And they may have indices. Heap locations testing is a mess. BC.
      */
 
      // these are costly function calls; call them only once.
      bool e1_abstract_location_p = entity_abstract_location_p( e1 );
      bool e2_abstract_location_p = entity_abstract_location_p( e2 );
 
      bool e1_heap_location_p = e1_abstract_location_p
        && entity_flow_or_context_sentitive_heap_location_p(e1);
      bool e2_heap_location_p = e2_abstract_location_p
        && entity_flow_or_context_sentitive_heap_location_p(e2);
 
      pips_assert("there shouldn't be two abstract locations here.",
                  !( (e1_abstract_location_p && !e1_heap_location_p)
                     &&  (e2_abstract_location_p && !e2_heap_location_p)));
 
 
        /* FI: Can we have some dynamic aliasing? */
        /* Do we have aliasing between types? */
        /* Do we have aliasing within a data structure? This should have
           been checked above with
           variable_references_may_conflict_p(v1,ind1,ind2) */
 
      /* A patch for effects_package references, which cannot conflict with user variables */
      /* well, strictly speaking, couldn't they conflict with an anywhere:anywhere effect?
         but then there should be other conflicts... */
      if (effects_package_entity_p(e1) || effects_package_entity_p(e2))
        {
          if (!same_entity_p(e1, e2) || (ENDP(ind1) && ENDP(ind2)) )
            conflict_p = false;
          else // same entity, with indices
            conflict_p = variable_references_may_conflict_p( e1, ind1, ind2 );
        }
      else
        {
 
          /* string operations are costly - perform them only once */
          bool e1_null_p = entity_null_locations_p(e1);
          bool e2_null_p = entity_null_locations_p(e2);
 
          if (e1_null_p || e2_null_p)
            conflict_p = e1_null_p && e2_null_p;
          else if ((e1_abstract_location_p && !e1_heap_location_p )
                   || (e2_abstract_location_p && !e2_heap_location_p ))
            {
              entity abstract_location_e = e1_abstract_location_p? e1: e2;
              //entity concrete_location_e = e1_abstract_location_p? e2: e1;
 
              pips_debug(5, "abstract location vs. concrete location case\n");
 
              if (entity_all_locations_p(abstract_location_e))
                conflict_p = true;
              else
                // there should be a reference_to_abstract_location function
                // as there is a variable_to_abstract_location function
                // assume conflict, but much more work should be done here. BC.
                conflict_p = true;
            }
          else // two concrete locations
            {
              pips_debug(5, "two concrete locations case \n");
              if (same_entity_p(e1, e2))
                conflict_p = variable_references_may_conflict_p( e1, ind1, ind2 );
              else
                {
                  // there should be no conflict here with constant path effects
                  // however, this is still work in progress :-( and when
                  // CONSTANT_PATH_EFFECTS is set to FALSE, effects may be erroneous.
                  // so we need this to avoid over-optimistic program transformations
 
                  if (constant_path_effects_p || trust_constant_path_effects_p)
                    {
                      conflict_p = false;
                    }
                  else
                    {
                      bool t1_to_be_freed = false, t2_to_be_freed = false;
                      type t1 = cell_reference_to_type( r1, &t1_to_be_freed );
                      type t2 = cell_reference_to_type( r2, &t2_to_be_freed  );
 
                      if ( conflict_p && !aliasing_across_types_p
                           && !type_equal_p(t1, t2) )
                        {
                          pips_debug(5, "no conflict because types are not equal\n");
                          conflict_p = false; /* well type_equal_p does not perform a good job :-( BC*/
                        }
                      if (t1_to_be_freed) free_type(t1);
                      if (t2_to_be_freed) free_type(t2);
 
                      if ( conflict_p && !aliasing_across_formal_parameters_p
                                && entity_formal_p(e1) && entity_formal_p(e2) )
                        {
                          pips_debug(5, "no conflict because entities are formals\n");
                          conflict_p = false;
                        }
 
                      if (conflict_p && !user_effects_on_std_files_p
                               && (std_file_entity_p(e1) || std_file_entity_p(e2)))
                        {
                          if (!same_entity_p(e1, e2))
                            conflict_p = false;
                          else
                            conflict_p = variable_references_may_conflict_p( e1, ind1, ind2 );
                        }
 
                      /* should ALIASING_ACROSS_DATA_STRUCTURES be also tested here? */
                      if ( conflict_p )
                        {
                          /* Do we have some dereferencing in ind1 or ind2? Do we assume
                             that p[0] conflicts with any reference? We might as well use
                             reference_to_abstract_location()... */
                          /* Could be improved with ALIASING_ACROSS_DATA_STRUCTURES? */
                          bool exact;
                          // Check dereferencing in r1
                          conflict_p = effect_reference_dereferencing_p( r1, &exact );
                          if(!conflict_p) {
                            /* We need to evaluate dereferencing in r2 only when a dereferencing
                             * have not been find in r1 */
                            conflict_p = effect_reference_dereferencing_p( r2, &exact );
                          }
                          /* In other words, we assume no conflict as soon as no pointer is
                           * dereferenced... even when aliasing across types is not ignored !
                           *
                           * If aliasing across types is ignored, we know here that the
                           * two memory locations referenced are of the same type. If the
                           * pointer in one reference (let's assume only one pointer to
                           * start with) is not of type pointer to the common type, then
                           * there is no conflict.
                           *
                           * Else, we have to assume a conflict no matter what, because
                           * simple cases should have been simplified via the points-to
                           * analysis.
                           */
                        }
 
                    }
                }
            } // end: two concrete locations
 
        }
    }
 
  pips_debug(5, "there is %s may conflict\n", conflict_p? "a": "no");
  return conflict_p;
}

References aliasing_across_formal_parameters_p, aliasing_across_types_p, c_module_p(), cell_reference_to_type(), constant_path_effects_p, effect_reference_dereferencing_p(), effect_reference_to_string(), effects_package_entity_p(), ENDP, entities_may_conflict_p(), entity_abstract_location_p(), entity_all_locations_p(), entity_flow_or_context_sentitive_heap_location_p(), entity_formal_p(), entity_null_locations_p(), free_type(), get_bool_property(), get_current_module_entity(), pips_assert, pips_debug, reference_indices, reference_variable, same_entity_p(), std_file_entity_p(), trust_constant_path_effects_p, type_equal_p(), user_effects_on_std_files_p, variable_entities_may_conflict_p(), and variable_references_may_conflict_p().

Referenced by apply_array_effect_to_transformer(), cells_maymust_conflict_p(), do_atomize_call(), do_symbolic_tiling(), generic_effects_maymust_read_or_write_scalar_entity_p(), generic_reference_to_transformer(), and invalidate_expressions_in_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

references_must_conflict_p()

bool references_must_conflict_p	(	reference	r1,
		reference	r2
	)

Check if two references may conflict.

@description See references_may_conflict_p

pips_user_warning("Not completely implemented yet. " "Conservative under approximation is made\n");

Check for constant subscripts

Parameters

r1	1
r2	2

Definition at line 607 of file conflicts.c.

                                                              {
  bool conflict_p = false;
  entity e1 = reference_variable(r1);
  entity e2 = reference_variable(r2);
 
  pips_debug(5, " %s vs %s\n", effect_reference_to_string(r1), effect_reference_to_string(r2));
 
  // Do a simple check for scalar conflicts
  if ( reference_scalar_p( r1 ) && reference_scalar_p( r2 )
      && entities_must_conflict_p( e1, e2 ) ) {
    conflict_p = true;
  } else {
    /* pips_user_warning("Not completely implemented yet. "
       "Conservative under approximation is made\n");*/
    if(entities_must_conflict_p(e1, e2)) {
      /* Check for constant subscripts */
      list sl1 = reference_indices(r1);
      list sl2 = reference_indices(r2);
      int n1 = (int) gen_length(sl1);
      int n2 = (int) gen_length(sl2);
      if(n1==n2) {
        list csl2 = sl2;
        bool diff_p = false;
        FOREACH(EXPRESSION, se1, sl1) {
          expression se2 = EXPRESSION(CAR(csl2));
          if(expression_equal_p(se1, se2)) {
            if(extended_expression_constant_p(se1))
              ;
            else if(expression_reference_p(se1)) {
              reference se1r = expression_reference(se1);
              entity se1f = reference_variable(se1r);
              if(!entity_field_p(se1f)) {
                diff_p = true;
                break;
              }
            }
            else {
              diff_p = true;
              break;
            }
          }
          else {
            diff_p = true;
            break;
          }
          POP(csl2);
        }
        conflict_p = !diff_p;
      }
    }
  }
  pips_debug(5, "there is %s must conflict\n", conflict_p? "a": "no");
  return conflict_p;
}

References CAR, effect_reference_to_string(), entities_must_conflict_p(), entity_field_p(), EXPRESSION, expression_equal_p(), expression_reference(), expression_reference_p(), extended_expression_constant_p(), FOREACH, gen_length(), int, pips_debug, POP, reference_indices, reference_scalar_p(), and reference_variable.

Referenced by cells_maymust_conflict_p(), and generic_effects_maymust_read_or_write_scalar_entity_p().

Here is the call graph for this function:

Here is the caller graph for this function:

set_conflict_testing_properties()

void set_conflict_testing_properties

(

void

)

conflicts.c

Definition at line 68 of file conflicts.c.

{
  bool get_bool_property( string );
  constant_path_effects_p = get_bool_property("CONSTANT_PATH_EFFECTS");
  trust_constant_path_effects_p = get_bool_property("TRUST_CONSTANT_PATH_EFFECTS_IN_CONFLICTS");
  aliasing_across_types_p = get_bool_property( "ALIASING_ACROSS_TYPES" );
  aliasing_across_formal_parameters_p =
    get_bool_property( "ALIASING_ACROSS_FORMAL_PARAMETERS" );
  user_effects_on_std_files_p = get_bool_property("USER_EFFECTS_ON_STD_FILES");
}

References aliasing_across_formal_parameters_p, aliasing_across_types_p, constant_path_effects_p, get_bool_property(), trust_constant_path_effects_p, and user_effects_on_std_files_p.

Referenced by chains(), do_symbolic_tiling(), generate_two_addresses_code(), and simdizer().

Here is the call graph for this function:

Here is the caller graph for this function:

variable_references_may_conflict_p()

bool variable_references_may_conflict_p	(	entity	v,
		list	sl1,
		list	sl2
	)

FIXME ?

@description May the two references to v using subscript list sl1 and sl2 access the same memory locations?

Subscript list sl1 and sl2 can be evaluated in two different stores.

FI: this code seems to assume that ALIASING_ACROSS_DATA_STRUCTURES is set to FALSE.

This is equivalent to a simple Fortran-like array reference

FI: this is new not really designed (!) code

Because of heap modelization functions can be used as subscript. Because of struct and union modelization, fields can be used as subscripts.

context sensitive heap modelization

assume the code is correct... Assume no floating point index... a[i] vs a[x]...

Parameters

sl1	l1
sl2	l2

Definition at line 314 of file conflicts.c.

{
  bool conflict_p = true;
  type t = entity_type(v);
  int sl1n = gen_length( sl1 );
  int sl2n = gen_length( sl2 );
  int nd = gen_length( variable_dimensions(type_variable(t)) );
 
  if ( sl1n == sl2n && sl1n == nd ) {
    /* This is equivalent to a simple Fortran-like array reference */
    conflict_p = array_references_may_conflict_p( sl1, sl2 );
  } else {
    if ( !ENDP(sl1) && !ENDP(sl2) ) {
      list cind1 = list_undefined;
      list cind2 = list_undefined;
      /* FI: this is new not really designed (!) code */
      for ( cind1 = sl1, cind2 = sl2; !ENDP(cind1) && !ENDP(cind2)
              && conflict_p; POP(cind1), POP(cind2) ) {
        expression e1 = EXPRESSION(CAR(cind1));
        expression e2 = EXPRESSION(CAR(cind2));
        if ( unbounded_expression_p( e1 ) || unbounded_expression_p( e2 ) )
          conflict_p = true;
        else if ( expression_reference_p( e1 ) && expression_reference_p( e2 ) ) {
          /* Because of heap modelization functions can be used as
             subscript. Because of struct and union modelization,
             fields can be used as subscripts. */
          entity s1 = expression_variable( e1 ); // first subscript
          entity s2 = expression_variable( e2 ); // second subscript
          type s1t = entity_type(s1);
          type s2t = entity_type(s2);
 
          if ( type_equal_p( s1t, s2t ) ) {
            if ( type_functional_p(s1t) ) {
              /* context sensitive heap modelization */
              conflict_p = same_string_p(entity_name(s1), entity_name(s2));
            }
            else if( entity_field_p(s1) &&  entity_field_p(s2))
              {
                if(type_struct_variable_p(t)) conflict_p=same_entity_p(s1,s2);
                else if(type_union_variable_p(t)) conflict_p=true;
              }
          } else {
            /* assume the code is correct... Assume no floating
               point index... a[i] vs a[x]... */
            conflict_p = false;
          }
        } else {
          intptr_t i1 = -1;
          intptr_t i2 = -1;
          bool i1_p = false;
          bool i2_p = false;
 
          i1_p = expression_integer_value( e1, &i1 );
          i2_p = expression_integer_value( e2, &i2 );
          if ( i1_p && i2_p )
            conflict_p = ( i1 == i2 );
          else
            conflict_p = true;
        }
      }
    } else
      conflict_p = true;
  }
  return conflict_p;
}

References array_references_may_conflict_p(), CAR, ENDP, entity_field_p(), entity_name, entity_type, EXPRESSION, expression_integer_value(), expression_reference_p(), expression_variable(), gen_length(), intptr_t, list_undefined, POP, s1, same_entity_p(), same_string_p, type_equal_p(), type_functional_p, type_struct_variable_p(), type_union_variable_p(), type_variable, unbounded_expression_p(), and variable_dimensions.

Referenced by references_may_conflict_p().

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

aliasing_across_formal_parameters_p

bool aliasing_across_formal_parameters_p = false

static

Definition at line 66 of file conflicts.c.

Referenced by references_may_conflict_p(), and set_conflict_testing_properties().

aliasing_across_types_p

bool aliasing_across_types_p = true

static

Definition at line 65 of file conflicts.c.

Referenced by references_may_conflict_p(), and set_conflict_testing_properties().

constant_path_effects_p

bool constant_path_effects_p = true

static

Properties settings for conflict testing functions.

These settings are done for performance reasons, especially in chains initial values are current default values

Definition at line 62 of file conflicts.c.

Referenced by references_may_conflict_p(), and set_conflict_testing_properties().

trust_constant_path_effects_p

bool trust_constant_path_effects_p = false

static

Definition at line 63 of file conflicts.c.

Referenced by references_may_conflict_p(), and set_conflict_testing_properties().

user_effects_on_std_files_p

bool user_effects_on_std_files_p = false

static

Definition at line 64 of file conflicts.c.

Referenced by references_may_conflict_p(), and set_conflict_testing_properties().