eval.c File Reference

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "genC.h"
#include "linear.h"
#include "ri.h"
#include "effects.h"
#include "ri-util.h"
#include "prettyprint.h"
#include "effects-util.h"
#include "misc.h"
#include "text-util.h"
#include "newgen_set.h"
#include "points_to_private.h"
#include "pointer_values.h"
#include "effects-generic.h"
#include "effects-convex.h"

Include dependency graph for eval.c:

Go to the source code of this file.

Functions
bool	convex_cell_reference_preceding_p (reference r1, descriptor d1, reference r2, descriptor d2, transformer current_precondition, bool strict_p, bool *exact_p)
	eval.c More...
bool	convex_cell_preceding_p (cell c1, descriptor d1, cell c2, descriptor d2, transformer current_precondition, bool strict_p, bool *exact_p)
void	simple_reference_to_convex_reference_conversion (reference ref, reference *output_ref, descriptor *output_desc)
void	simple_cell_to_convex_cell_conversion (cell input_cell, cell *output_cell, descriptor *output_desc)
list	eval_convex_cell_with_points_to (cell c, descriptor d, list ptl, bool *exact_p, transformer current_precondition)
list	convex_effect_to_constant_path_effects_with_points_to (effect eff)
list	convex_effect_find_aliased_paths_with_pointer_values (effect eff, statement s)
list	convex_effect_to_constant_path_effects_with_pointer_values (effect __attribute__((unused)) eff)

Function Documentation

convex_cell_preceding_p()

bool convex_cell_preceding_p	(	cell	c1,
		descriptor	d1,
		cell	c2,
		descriptor	d2,
		transformer	current_precondition,
		bool	strict_p,
		bool *	exact_p
	)

Parameters

c1	1
d1	1
c2	2
d2	2
current_precondition	urrent_precondition
strict_p	trict_p
exact_p	xact_p

Definition at line 191 of file eval.c.

{
  reference r1 = cell_any_reference(c1);
  reference r2 = cell_any_reference(c2);
 
  return convex_cell_reference_preceding_p(r1, d1, r2, d2, current_precondition,
                                           strict_p, exact_p);
}

References cell_any_reference(), convex_cell_reference_preceding_p(), and current_precondition.

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_cell_reference_preceding_p()

bool convex_cell_reference_preceding_p	(	reference	r1,
		descriptor	d1,
		reference	r2,
		descriptor	d2,
		transformer	current_precondition,
		bool	strict_p,
		bool *	exact_p
	)

eval.c

same entity and the path length of r1 is shorter than the path length of r2.

we now have to check that each common index matches

only matching reference indices have been found (phi variables or struct field entities).

we must now check the descriptors.

Parameters

r1	1
d1	1
r2	2
d2	2
current_precondition	urrent_precondition
strict_p	trict_p
exact_p	xact_p

Definition at line 67 of file eval.c.

{
  bool res = true;
  entity e1 = reference_variable(r1);
  list ind1 = reference_indices(r1);
  size_t r1_path_length = gen_length(ind1);
  entity e2 = reference_variable(r2);
  list ind2 = reference_indices(r2);
  size_t r2_path_length = gen_length(ind2);
 
  pips_debug(8, "input references r1 : %s, r2: %s \n",
      reference_to_string(r1),
      reference_to_string(r2));
 
  *exact_p = true;
  if (same_entity_p(e1, e2)
      && ((r1_path_length < r2_path_length)
          || (!strict_p && r1_path_length == r2_path_length)))
  {
    /* same entity and the path length of r1 is shorter than the
     * path length of r2.
     *
     * we now have to check that each common index matches
     */
    pips_debug(8,"same entities, and r1 path is shorter than r2 path\n");
    while (res && !ENDP(ind1))
    {
      expression exp1 = EXPRESSION(CAR(ind1));
      expression exp2 = EXPRESSION(CAR(ind2));
 
      if(!expression_equal_p(exp1, exp2))
      {
        res = false;
        *exact_p = true;
      }
 
      POP(ind1);
      POP(ind2);
    }
    if (res)
    {
      /* only matching reference indices have been found (phi
       * variables or struct field entities).
       *
       * we must now check the descriptors.
       */
      region reg1 = make_effect(make_cell(is_cell_reference, r1),
          make_action_write_memory(),
          make_approximation_exact(), d1);
      region reg2 = make_effect(make_cell(is_cell_reference, r2),
          make_action_write_memory(),
          make_approximation_exact(), d2);
 
      pips_debug_effect(6, "reg1 = \n", reg1);
      pips_debug_effect(6, "reg2 = \n", reg1);
 
      list li = region_intersection(reg1, reg2);
      if (ENDP(li))
      {
        res = false;
        *exact_p = true;
      }
      else
      {
 
        pips_debug_effect(8, "reg2 before eliminating phi variables: \n ", reg2);
 
        effect reg2_dup = copy_effect(reg2);
        list l_reg2 = CONS(EFFECT,reg2_dup,NIL);
        list l_phi = phi_entities_list(r1_path_length+1,r2_path_length);
        project_regions_along_variables(l_reg2, l_phi);
        gen_free_list(l_reg2);
        gen_free_list(l_phi);
        pips_debug_effect(8, "reg2_dup after elimination: \n ", reg2_dup);
 
        effect reg1_dup = copy_effect(reg1);
        if (!transformer_undefined_p(current_precondition))
        {
          Psysteme sc_context = predicate_system(transformer_relation(current_precondition));
          region_sc_append(reg1_dup, sc_context, false);
        }
 
        pips_debug_effect(8, "reg1_dup after adding preconditions: \n ", reg1_dup);
        pips_debug_effect(8, "reg1 after adding preconditions: \n ", reg1);
 
        list ld = region_sup_difference(reg1_dup, reg2_dup);
        if (ENDP(ld))
        {
          res = true;
          *exact_p = true;
        }
        else
        {
          res = true;
          *exact_p = false;
        }
        gen_full_free_list(ld);
      }
      gen_full_free_list(li);
 
      cell_reference(effect_cell(reg1)) = reference_undefined;
      effect_descriptor(reg1) = descriptor_undefined;
      free_effect(reg1);
 
      cell_reference(effect_cell(reg2)) = reference_undefined;
      effect_descriptor(reg2) = descriptor_undefined;
      free_effect(reg2);
    }
  }
  else
  {
    res = false;
    *exact_p = true;
  }
 
  pips_debug(8, "end : r1 is %s a predecessor of r2 (%s exact)\n", res ? "":"not", *exact_p ? "":"not");
  return res;
}

References CAR, cell_reference, CONS, copy_effect(), current_precondition, descriptor_undefined, EFFECT, effect_cell, effect_descriptor, ENDP, EXPRESSION, expression_equal_p(), free_effect(), gen_free_list(), gen_full_free_list(), gen_length(), is_cell_reference, make_action_write_memory(), make_approximation_exact(), make_cell(), make_effect(), NIL, phi_entities_list(), pips_debug, pips_debug_effect, POP, predicate_system, project_regions_along_variables(), reference_indices, reference_to_string(), reference_undefined, reference_variable, region, region_intersection(), region_sc_append(), region_sup_difference(), same_entity_p(), transformer_relation, and transformer_undefined_p.

Referenced by convex_cell_preceding_p(), and eval_convex_cell_with_points_to().

Here is the call graph for this function:

Here is the caller graph for this function:

convex_effect_find_aliased_paths_with_pointer_values()

list convex_effect_find_aliased_paths_with_pointer_values	(	effect	eff,
		statement	s
	)

Parameters

eff

ff

Definition at line 326 of file eval.c.

{
  bool exact_p;
  list l_pv = cell_relations_list( load_pv(s));
  pv_context ctxt = make_simple_pv_context();
  list l_aliased = generic_effect_find_aliases_with_simple_pointer_values(eff, l_pv, &exact_p, transformer_undefined,
      convex_cell_preceding_p,
      convex_cell_with_address_of_cell_translation,
      convex_cell_with_value_of_cell_translation,
      convex_cells_intersection_p,
      convex_cells_inclusion_p,
      simple_cell_to_convex_cell_conversion);
 
  reset_pv_context(&ctxt);
  return l_aliased;
}

References cell_relations_list, convex_cell_preceding_p(), convex_cell_with_address_of_cell_translation(), convex_cell_with_value_of_cell_translation(), convex_cells_inclusion_p(), convex_cells_intersection_p(), generic_effect_find_aliases_with_simple_pointer_values(), load_pv(), make_simple_pv_context(), reset_pv_context(), simple_cell_to_convex_cell_conversion(), and transformer_undefined.

Referenced by convex_effect_to_constant_path_effects_with_pointer_values().

Here is the call graph for this function:

Here is the caller graph for this function:

convex_effect_to_constant_path_effects_with_pointer_values()

list convex_effect_to_constant_path_effects_with_pointer_values

(

effect __attribute__((unused))

eff

)

it should be a union here. However, we expect the caller to perform the contraction afterwards.

Definition at line 346 of file eval.c.

{
  list le = NIL;
  bool exact_p;
  reference ref = effect_any_reference(eff);
 
  if (effect_reference_dereferencing_p(ref, &exact_p))
  {
    pips_debug(8, "dereferencing case \n");
    bool exact_p = false;
    list l_aliased = convex_effect_find_aliased_paths_with_pointer_values(eff, effects_private_current_stmt_head());
    pips_debug_effects(8, "aliased effects\n", l_aliased);
 
    FOREACH(EFFECT, eff_alias, l_aliased)
    {
      entity ent_alias = effect_entity(eff_alias);
      if (undefined_pointer_value_entity_p(ent_alias)
          || null_pointer_value_entity_p(ent_alias))
      {
        // currently interpret them as anywhere effects since these values
        // are not yet well integrated in abstract locations lattice
        // and in effects computations
        // to be FIXED later.
        le = CONS(EFFECT, make_anywhere_effect(copy_action(effect_action(eff_alias))), le);
        free_effect(eff_alias);
      }
      else if (entity_abstract_location_p(effect_entity(eff_alias))
          || !effect_reference_dereferencing_p(effect_any_reference(eff_alias), &exact_p)) {
        le = CONS(EFFECT, eff_alias, le);
        /* it should be a union here.
         * However, we expect the caller
         * to perform the contraction afterwards. */
      }
      else
        free_effect(eff_alias);
    }
    gen_free_list(l_aliased);
  }
  else {
    // functions that can be pointed by effect_dup_func:
    // simple_effect_dup
    // region_dup
    // copy_effect
    le = CONS(EFFECT, (*effect_dup_func)(eff), le);
  }
 
  return le;
}

References CONS, convex_effect_find_aliased_paths_with_pointer_values(), copy_action(), EFFECT, effect_action, effect_any_reference, effect_dup_func, effect_entity(), effect_reference_dereferencing_p(), effects_private_current_stmt_head(), entity_abstract_location_p(), FOREACH, free_effect(), gen_free_list(), make_anywhere_effect(), NIL, null_pointer_value_entity_p(), pips_debug, pips_debug_effects, ref, and undefined_pointer_value_entity_p().

Here is the call graph for this function:

convex_effect_to_constant_path_effects_with_points_to()

list convex_effect_to_constant_path_effects_with_points_to

(

effect

eff

)

We have not found any equivalent constant path : it may point anywhere

We should maybe contract these effects later. Is it done by the callers ?

change the resulting effects action to the current effect action

Parameters

eff

ff

Definition at line 285 of file eval.c.

{
  list le = NIL;
  bool exact_p;
  reference ref = effect_any_reference(eff);
 
  if (effect_reference_dereferencing_p(ref, &exact_p))
  {
    pips_debug(8, "dereferencing case \n");
    bool exact_p = false;
    transformer context;
    if (effects_private_current_context_empty_p())
      context = transformer_undefined;
    else {
      context = effects_private_current_context_head();
    }
 
    list l_eval = eval_convex_cell_with_points_to(effect_cell(eff), effect_descriptor(eff),
        points_to_list_list(load_pt_to_list(effects_private_current_stmt_head())),
        &exact_p, context);
    if (ENDP(l_eval))
    {
      pips_debug(8, "no equivalent constant path found -> anywhere effect\n");
      /* We have not found any equivalent constant path : it may point anywhere */
      /* We should maybe contract these effects later. Is it done by the callers ? */
      le = CONS(EFFECT, make_anywhere_effect(copy_action(effect_action(eff))), le);
    }
    else
    {
      /* change the resulting effects action to the current effect action */
      if (effect_read_p(eff))
        effects_to_read_effects(l_eval);
      le = gen_nconc(l_eval,le);
    }
  }
  else
    le = CONS(EFFECT, copy_effect(eff), le);
  return le;
}

References CONS, copy_action(), copy_effect(), EFFECT, effect_action, effect_any_reference, effect_cell, effect_descriptor, effect_read_p, effect_reference_dereferencing_p(), effects_private_current_context_empty_p(), effects_private_current_context_head(), effects_private_current_stmt_head(), effects_to_read_effects(), ENDP, eval_convex_cell_with_points_to(), gen_nconc(), load_pt_to_list(), make_anywhere_effect(), NIL, pips_debug, points_to_list_list, ref, and transformer_undefined.

Referenced by set_methods_for_convex_effects().

Here is the call graph for this function:

Here is the caller graph for this function:

eval_convex_cell_with_points_to()

list eval_convex_cell_with_points_to	(	cell	c,
		descriptor	d,
		list	ptl,
		bool *	exact_p,
		transformer	current_precondition
	)

Parameters

ptl	tl
exact_p	xact_p
current_precondition	urrent_precondition

Definition at line 275 of file eval.c.

{
 
  return generic_eval_cell_with_points_to(c, d, ptl, exact_p, current_precondition,
                                          convex_cell_reference_preceding_p,
                                          convex_cell_reference_with_address_of_cell_reference_translation,
                                          simple_reference_to_convex_reference_conversion);
}

References convex_cell_reference_preceding_p(), convex_cell_reference_with_address_of_cell_reference_translation(), current_precondition, generic_eval_cell_with_points_to(), and simple_reference_to_convex_reference_conversion().

Referenced by convex_effect_to_constant_path_effects_with_points_to(), and set_methods_for_convex_effects().

Here is the call graph for this function:

Here is the caller graph for this function:

simple_cell_to_convex_cell_conversion()

void simple_cell_to_convex_cell_conversion	(	cell	input_cell,
		cell *	output_cell,
		descriptor *	output_desc
	)

Parameters

input_cell	nput_cell
output_cell	utput_cell
output_desc	utput_desc

Definition at line 234 of file eval.c.

{
 
  reference input_ref = cell_any_reference(input_cell);
  reference output_ref = reference_undefined;
 
  simple_reference_to_convex_reference_conversion(input_ref, &output_ref, output_desc);
  *output_cell = make_cell_reference(output_ref);
}

References cell_any_reference(), make_cell_reference(), reference_undefined, and simple_reference_to_convex_reference_conversion().

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:

simple_reference_to_convex_reference_conversion()

void simple_reference_to_convex_reference_conversion	(	reference	ref,
		reference *	output_ref,
		descriptor *	output_desc
	)

Parameters

ref	ef
output_ref	utput_ref
output_desc	utput_desc

Definition at line 205 of file eval.c.

{
 
  effect reg = make_effect(make_cell_reference(make_reference(reference_variable(ref), NIL)),
      make_action_write_memory(),
      make_approximation_exact(),
      make_descriptor_convex(sc_new()));
 
  FOREACH(EXPRESSION, exp, reference_indices(ref))
  {
    if((expression_reference_p(exp)
        && entity_field_p(reference_variable(expression_reference(exp)))))
    {
      entity e = reference_variable(expression_reference(exp));
      effect_add_field_dimension(reg, e);
    }
    else
      convex_region_add_expression_dimension(reg, exp);
  }
  *output_ref = effect_any_reference(reg);
  *output_desc = effect_descriptor(reg);
 
  pips_debug_effect(6, "reg = \n", reg);
 
  cell_reference(effect_cell(reg)) = reference_undefined;
  effect_descriptor(reg) = descriptor_undefined;
  free_effect(reg);
}

References cell_reference, convex_region_add_expression_dimension(), descriptor_undefined, effect_add_field_dimension(), effect_any_reference, effect_cell, effect_descriptor, entity_field_p(), exp, EXPRESSION, expression_reference(), expression_reference_p(), FOREACH, free_effect(), make_action_write_memory(), make_approximation_exact(), make_cell_reference(), make_descriptor_convex(), make_effect(), make_reference(), NIL, pips_debug_effect, ref, reference_indices, reference_undefined, reference_variable, and sc_new().

Referenced by eval_convex_cell_with_points_to(), and simple_cell_to_convex_cell_conversion().

Here is the call graph for this function:

Here is the caller graph for this function: