points_to.c File Reference

#include <stdio.h>
#include <string.h>
#include "genC.h"
#include "linear.h"
#include "misc.h"
#include "properties.h"
#include "ri.h"
#include "effects.h"
#include "ri-util.h"
#include "prettyprint.h"
#include "effects-util.h"
#include "text-util.h"
#include "effects-simple.h"
#include "pips-libs.h"
#include "transformer.h"

Include dependency graph for points_to.c:

Go to the source code of this file.

Functions
points_to_graph	get_points_to_graph_from_statement (_UNUSED_ statement st)
	Interface with points-to library. More...
list	expression_to_points_to_sinks (_UNUSED_ expression e, _UNUSED_ points_to_graph in)
list	expression_to_points_to_sources (_UNUSED_ expression e, _UNUSED_ points_to_graph in)
set	user_call_to_points_to_interprocedural_binding_set (call c, pt_map pt_caller)
	Compute the binding relations in a complete interprocedural way: be as accurate as possible. More...
list	semantics_expression_to_points_to_sources (expression e)
	Special wrapping for the semantics analyses. More...
list	semantics_expression_to_points_to_sinks (expression e)
	Returns a list of cells. More...
transformer	substitute_scalar_stub_in_transformer (transformer tf, entity se, entity de, bool backward_p, list *ppl)
	If both "se", source entity, and "de", destination entity, are defined, substitute the values of "se" by the values of "de" in "backward_p" mode, when translating a callee transformer at a call site of a caller. More...
transformer	substitute_struct_stub_in_transformer (transformer t, reference l, type lt, reference r, type rt __attribute__((unused)), bool backward_p, list *ppl)
static bool	relevant_translation_pair_p (points_to pt, list ll)
	The sources of the relevant points-to. More...
transformer	substitute_stubs_in_transformer (transformer tf, call c, statement s, bool backward_p)
	Exploit the binding map to substitute calles's stubs by actual arguments, which may be stubs of the callers,. More...
static transformer	substitute_stubs_in_transformer_with_translation_binding (transformer tf, pt_map binding_g, bool backward_p)
transformer	new_substitute_stubs_in_transformer (transformer tf, call c, statement s, bool backward_p)

Function Documentation

expression_to_points_to_sinks()

list expression_to_points_to_sinks	(	_UNUSED_ expression	e,
		_UNUSED_ points_to_graph	in
	)

Definition at line 63 of file points_to.c.

{
  pips_internal_error("points-to library not available");
  return NIL;
}

References NIL, and pips_internal_error.

Referenced by semantics_expression_to_points_to_sinks().

Here is the caller graph for this function:

expression_to_points_to_sources()

list expression_to_points_to_sources	(	_UNUSED_ expression	e,
		_UNUSED_ points_to_graph	in
	)

Definition at line 71 of file points_to.c.

{
  pips_internal_error("points-to library not available");
  return NIL;
}

References NIL, and pips_internal_error.

Referenced by semantics_expression_to_points_to_sources().

Here is the caller graph for this function:

get_points_to_graph_from_statement()

points_to_graph get_points_to_graph_from_statement

(

_UNUSED_ statement

st

)

Interface with points-to library.

Definition at line 56 of file points_to.c.

{
  pips_internal_error("points-to library not available");
  return NULL;
}

References pips_internal_error.

Referenced by new_substitute_stubs_in_transformer(), semantics_expression_to_points_to_sinks(), semantics_expression_to_points_to_sources(), and substitute_stubs_in_transformer().

Here is the caller graph for this function:

new_substitute_stubs_in_transformer()

transformer new_substitute_stubs_in_transformer	(	transformer	tf,
		call	c,
		statement	s,
		bool	backward_p
	)

This leads to an empty transformer because the statement is unreachable. Some kind of dereferencement error has occured earlier in the execution

Parameters

tf	f
backward_p	ackward_p

Definition at line 417 of file points_to.c.

{
  if(pt_to_list_undefined_p()) {
    // Return tf as is
  }
  else {
    points_to_graph ptg = get_points_to_graph_from_statement(s);
    bool bottom_p = points_to_graph_bottom(ptg);
 
    if(bottom_p) {
      /* This leads to an empty transformer because the statement is
       * unreachable. Some kind of dereferencement error has occured
       * earlier in the execution
       */
      free_transformer(tf);
      tf = transformer_empty();
    }
    else {
      set binding = user_call_to_points_to_interprocedural_binding_set(c, ptg);
      pt_map binding_g = make_points_to_graph(false, binding);
      tf = substitute_stubs_in_transformer_with_translation_binding(tf, binding_g, backward_p);
      free_points_to_graph(binding_g);
    }
  }
  return tf;
}

References free_points_to_graph(), free_transformer(), get_points_to_graph_from_statement(), make_points_to_graph(), points_to_graph_bottom, pt_to_list_undefined_p(), substitute_stubs_in_transformer_with_translation_binding(), transformer_empty(), and user_call_to_points_to_interprocedural_binding_set().

Referenced by c_user_call_to_transformer().

Here is the call graph for this function:

Here is the caller graph for this function:

relevant_translation_pair_p()

static bool relevant_translation_pair_p ( points_to  pt, list  ll  )

static

The sources of the relevant points-to.

Definition at line 226 of file points_to.c.

{
  bool relevant_p = false;
  cell d = points_to_sink(pt); // callee if backward_p
  reference dr = cell_any_reference(d);
  entity de = reference_variable(dr);
  relevant_p = gen_in_list_p((const void *) de, ll);
 
  return relevant_p;
}

References cell_any_reference(), gen_in_list_p(), points_to_sink, and reference_variable.

Referenced by substitute_stubs_in_transformer().

Here is the call graph for this function:

Here is the caller graph for this function:

semantics_expression_to_points_to_sinks()

list semantics_expression_to_points_to_sinks

(

expression

e

)

Returns a list of cells.

Definition at line 112 of file points_to.c.

{
  list ll = list_undefined;
  if(pt_to_list_undefined_p()) {
    type t = points_to_expression_to_concrete_type(e);
    cell c = make_anywhere_points_to_cell(t);
    ll = CONS(CELL, c, NIL);
  }
  else {
    statement curstat =  get_current_statement_from_statement_global_stack();
    points_to_graph ptg = get_points_to_graph_from_statement(curstat);
    ll = expression_to_points_to_sinks(e, ptg);
  }
  return ll;
}

References CELL, CONS, expression_to_points_to_sinks(), get_current_statement_from_statement_global_stack(), get_points_to_graph_from_statement(), list_undefined, make_anywhere_points_to_cell(), NIL, points_to_expression_to_concrete_type(), and pt_to_list_undefined_p().

Referenced by generic_unary_operation_to_transformer(), and points_to_unary_operation_to_transformer().

Here is the call graph for this function:

Here is the caller graph for this function:

semantics_expression_to_points_to_sources()

list semantics_expression_to_points_to_sources

(

expression

e

)

Special wrapping for the semantics analyses.

points_to.c

FI: check if new cells are allocated to build the returned location list ll...

Definition at line 94 of file points_to.c.

{
  points_to_graph ptg = points_to_graph_undefined;
  if (!pt_to_list_undefined_p()) {
    statement curstat =  get_current_statement_from_statement_global_stack();
    if(statement_undefined_p(curstat)) {
      // The points-to IN information should be used
      ;
    }
    else
      ptg = get_points_to_graph_from_statement(curstat);
  }
 
  list ll = expression_to_points_to_sources(e, ptg);
  return ll;
}

References expression_to_points_to_sources(), get_current_statement_from_statement_global_stack(), get_points_to_graph_from_statement(), points_to_graph_undefined, pt_to_list_undefined_p(), and statement_undefined_p.

Referenced by any_assign_to_transformer(), any_basic_update_to_transformer(), any_update_to_transformer(), lhs_expression_to_transformer(), new_array_elements_backward_substitution_in_transformer(), new_array_elements_forward_substitution_in_transformer(), and struct_reference_assignment_or_equality_to_transformer().

Here is the call graph for this function:

Here is the caller graph for this function:

substitute_scalar_stub_in_transformer()

transformer substitute_scalar_stub_in_transformer	(	transformer	tf,
		entity	se,
		entity	de,
		bool	backward_p,
		list *	ppl
	)

If both "se", source entity, and "de", destination entity, are defined, substitute the values of "se" by the values of "de" in "backward_p" mode, when translating a callee transformer at a call site of a caller.

If the "se" entity cannot be substituted, its value must be project.

Parameters

tf	f
se	e
de	e
backward_p	ackward_p
ppl	pl

Definition at line 136 of file points_to.c.

{
  if(entity_undefined_p(se))
    ;
  else if(entity_undefined_p(de))
    *ppl = CONS(ENTITY, se, *ppl);
  else if(entity_has_values_p(de)) {
    // Not in the caller's frame
    // entity nsv = entity_to_new_value(se);
    entity nsv = se;
    entity ndv = entity_to_new_value(de);
    if(backward_p) { // For transformers
      tf = transformer_value_substitute(tf, nsv, ndv);
    }
    else { // For preconditions
      tf = transformer_value_substitute(tf, ndv, nsv);
    }
    // Careful, se has been substituted in the argument too
    if(entity_is_argument_p(de, transformer_arguments(tf))) {
      entity osv = global_new_value_to_global_old_value(nsv);
      entity odv = entity_to_old_value(de);
      if(backward_p) { // For transformers
        tf = transformer_value_substitute(tf, osv, odv);
      }
      else { // For preconditions
        tf = transformer_value_substitute(tf, odv, osv);
      }
    }
  }
  else {
    // FI: could be some debugging stuff
    pips_user_warning("Stub \"%s\" cannot be substituted.\n",
                      entity_user_name(de));
    // FI: entity "de" must be projected
    *ppl = CONS(ENTITY, se, *ppl);
  }
  return tf;
}

References CONS, ENTITY, entity_has_values_p(), entity_is_argument_p(), entity_to_new_value(), entity_to_old_value(), entity_undefined_p, entity_user_name(), global_new_value_to_global_old_value(), pips_user_warning, transformer_arguments, and transformer_value_substitute().

Referenced by forward_substitute_array_location_in_transformer(), new_array_element_backward_substitution_in_transformer(), substitute_struct_stub_in_transformer(), and substitute_stubs_in_transformer().

Here is the call graph for this function:

Here is the caller graph for this function:

substitute_struct_stub_in_transformer()

transformer substitute_struct_stub_in_transformer	(	transformer	t,
		reference	l,
		type	lt,
		reference	r,
		type rt	__attribute__(unused),
		bool	backward_p,
		list *	ppl
	)

Definition at line 175 of file points_to.c.

{
  list fl = struct_type_to_fields(lt);
  FOREACH(ENTITY, f, fl) {
    type ft = entity_basic_concrete_type(f);
    if(analyzed_type_p(ft)) {
      reference r1 = add_subscript_to_reference(copy_reference(l), 
                                                entity_to_expression(f));
      reference r2 = add_subscript_to_reference(copy_reference(r), 
                                                entity_to_expression(f));
      entity l1 = constant_memory_access_path_to_location_entity(r1);
      entity l2 = constant_memory_access_path_to_location_entity(r2);
 
      if(!entity_undefined_p(l1)) {
        if(!entity_undefined_p(l2)) {
          t = substitute_scalar_stub_in_transformer(t, l1, l2, backward_p, ppl);
        }
      }
      else {
        // pips_internal_error("Not implemented yet.\n");
        // Do nothing, this field may simply be not used
        ;
      }
      free_reference(r1);
      free_reference(r2); // another option would be to remove the last subscript
    }
    else if(type_struct_variable_p(ft)) {
      // This piece of code could be integrate in the previous
      // alternative to share most of its code
      reference l1 = add_subscript_to_reference(copy_reference(l), 
                                                entity_to_expression(f));
      reference r1 = add_subscript_to_reference(copy_reference(r), 
                                                entity_to_expression(f));
      if(array_type_p(ft)) {
        // FI: how do we guess the subscript values? we could try to
        // infer them from the values used in the transformer or we
        // can generate all possible subscripts...
 
        // FI: a special case, used for debugging only
        l1 = add_subscript_to_reference(l1, int_to_expression(1));
        r1 = add_subscript_to_reference(r1, int_to_expression(1));
      }
 
      // GO down recursively
      t = substitute_struct_stub_in_transformer(t, l1, ft, r1, ft, backward_p, ppl);
    }
  }
  return t;
}

References add_subscript_to_reference(), analyzed_type_p(), array_type_p(), constant_memory_access_path_to_location_entity(), copy_reference(), ENTITY, entity_basic_concrete_type(), entity_to_expression(), entity_undefined_p, f(), FOREACH, free_reference(), int_to_expression(), struct_type_to_fields(), substitute_scalar_stub_in_transformer(), and type_struct_variable_p().

Referenced by substitute_stubs_in_transformer().

Here is the call graph for this function:

Here is the caller graph for this function:

substitute_stubs_in_transformer()

transformer substitute_stubs_in_transformer	(	transformer	tf,
		call	c,
		statement	s,
		bool	backward_p
	)

Exploit the binding map to substitute calles's stubs by actual arguments, which may be stubs of the callers,.

backward_p request a substitution from the callees' frame into the caller's frame, which is useful for transformers. Flag backward_p is set to false to compute summary preconditions.

FI: this function is now only used for preconditions. It has been rewritten for transformers to speed up the process when array elements are involved. It is better to start from the needs, the stubs used in the transformer, than from all possible stubs, but it is much easier for a backward translation. With a forward translation, regular variables may have to be translated into stubs.

FI: A quick improvement would to return when no translation is needed... but you do not always know it when backward_p is set to false.

Parameters

tf	f
backward_p	ackward_p

Definition at line 256 of file points_to.c.

{
  entity m = get_current_module_entity();
  list ll = backward_p? transformer_to_analyzed_locations(tf)
    : transformer_to_potential_stub_translation(tf, m);
  if(ENDP(ll)) {
    // Return tf as is
    ;
  }
  else if(pt_to_list_undefined_p()) {
    // Return tf as is
  }
  else {
    points_to_graph ptg = get_points_to_graph_from_statement(s);
    bool bottom_p = points_to_graph_bottom(ptg);
 
    if(bottom_p) {
      // FI: should this lead to an empty transformer?
      pips_internal_error("Not implemented yet.\n");
    }
    else {
      set binding = user_call_to_points_to_interprocedural_binding_set(c, ptg);
      list pl = NIL; // FI: I am not sure we can managed forward and
                     // backward projections with one variable
      SET_FOREACH(points_to, pt, binding) {
        approximation ap = points_to_approximation(pt);
        if(relevant_translation_pair_p(pt, ll) 
           && (approximation_exact_p(ap) || approximation_must_p(ap))) {
          cell s = points_to_source(pt); // callee if backward_p
          cell d = points_to_sink(pt); // caller if backward_p
          reference sr = cell_any_reference(s);
          reference dr = cell_any_reference(d);
          // This test should be useless because this is guaranteed by
          // the approximation, except if binding is corrupted.
          if(atomic_points_to_reference_p(dr)) {
            list srs = reference_indices(sr);
            list drs = reference_indices(dr);
            if(ENDP(srs) && ENDP(drs)) {
              entity se = reference_variable(sr);
              entity de = reference_variable(dr);
              //type se_t = entity_basic_concrete_type(se);
              //type de_t = entity_basic_concrete_type(de);
              if(entity_has_values_p(de))
                tf = substitute_scalar_stub_in_transformer(tf, se, de, backward_p, &pl);
              else {
                type se_t = entity_basic_concrete_type(se);
                type de_t = entity_basic_concrete_type(de);
                if(type_struct_variable_p(se_t)) {
                  tf = substitute_struct_stub_in_transformer(tf, sr, se_t, dr, de_t, backward_p, &pl);
                }
                else
                  pl = CONS(ENTITY, se, pl);
              }
            }
            else if(ENDP(srs) && !ENDP(drs)) {
              entity se = reference_variable(sr);
              if(analyzed_reference_p(dr)) {
                entity de = constant_memory_access_path_to_location_entity(dr);
                tf = substitute_scalar_stub_in_transformer(tf, se, de, backward_p, &pl);
              }
              else {
                pl = CONS(ENTITY, se, pl);
              }
            }
            else if(!ENDP(srs) && ENDP(drs)) {
              entity de = reference_variable(dr);
              if(entity_has_values_p(de)) {
                entity se = constant_memory_access_path_to_location_entity(sr);
                if(!entity_undefined_p(se))
                  tf = substitute_scalar_stub_in_transformer(tf, se, de, backward_p, &pl);
                else
                  pips_internal_error("Not implemented yet.\n");
              }
              else {
                type de_t = entity_basic_concrete_type(de);
                if(type_struct_variable_p(de_t)) {
                  tf = substitute_struct_stub_in_transformer(tf, sr, de_t, dr, de_t, backward_p, &pl);
                  // tf = substitute_struct_stub_reference_in_transformer(tf, sr, de, backward_p, &pl);
                }
                else {
                  // Do nothing
                  // entity se = reference_variable(sr);
                  // pl = CONS(ENTITY, se, pl);
                  ;
                }
              }
            }
            else { // !ENDP(srs) & !ENDP(drs)
              if(analyzed_reference_p(dr)) {
                entity se = constant_memory_access_path_to_location_entity(sr);
                entity de = constant_memory_access_path_to_location_entity(dr);
                tf = substitute_scalar_stub_in_transformer(tf, se, de, backward_p, &pl);
              }
              else {
                type st = reference_to_type(sr);
                type cst = compute_basic_concrete_type(st);
                if(type_struct_variable_p(cst))
                  tf = substitute_struct_stub_in_transformer(tf, sr, cst, dr, cst, backward_p, &pl);
                else {
                  // No useful information in this binding
                  ;
                }
              }
            }
          }
        }
      }
      if(!ENDP(pl)) {
        // Get rid on untranslatable entities
        tf = safe_transformer_projection(tf, pl);
      }
    }
  }
 
  gen_free_list(ll);
 
  return tf;
}

References analyzed_reference_p(), approximation_exact_p, approximation_must_p, atomic_points_to_reference_p(), cell_any_reference(), compute_basic_concrete_type(), CONS, constant_memory_access_path_to_location_entity(), ENDP, ENTITY, entity_basic_concrete_type(), entity_has_values_p(), entity_undefined_p, gen_free_list(), get_current_module_entity(), get_points_to_graph_from_statement(), NIL, pips_internal_error, pl, points_to_approximation, points_to_graph_bottom, points_to_sink, points_to_source, pt_to_list_undefined_p(), reference_indices, reference_to_type(), reference_variable, relevant_translation_pair_p(), safe_transformer_projection(), SET_FOREACH, substitute_scalar_stub_in_transformer(), substitute_struct_stub_in_transformer(), transformer_to_analyzed_locations(), transformer_to_potential_stub_translation(), type_struct_variable_p(), and user_call_to_points_to_interprocedural_binding_set().

Referenced by process_call_for_summary_precondition().

Here is the call graph for this function:

Here is the caller graph for this function:

substitute_stubs_in_transformer_with_translation_binding()

static transformer substitute_stubs_in_transformer_with_translation_binding ( transformer  tf, pt_map  binding_g, bool  backward_p  )

static

Definition at line 375 of file points_to.c.

{
  pips_assert("Backward only", backward_p);
  list ll = transformer_to_analyzed_locations(tf);
  FOREACH(ENTITY, l, ll) {
    type lt = entity_basic_concrete_type(l);
    value val = entity_initial(l);
    entity v = l;
    list sl = NIL;
    if(value_reference_p(val)) {
      reference r = value_reference(val); // By definition of list ll
      v = reference_variable(r);
      sl = reference_indices(r);
    }
    list tcrl = reference_to_points_to_translations(v, sl, binding_g);
    FOREACH(CELL, tcr, tcrl) {
      reference tr = cell_any_reference(tcr);
      type trt = points_to_reference_to_concrete_type(tr);
      // FI: The type checking should be useless, but for constant
      // character strings which appear as a pointer to a char,
      // i.e. an integer, and is analyzed as such in the callee
      if(type_equal_p(lt, trt)
         && generic_atomic_points_to_reference_p(tr, false)) {
        entity tl = constant_memory_access_path_to_location_entity(tr);
        if(!entity_undefined_p(tl)) {
          entity nlv = external_entity_to_new_value(l);
          entity ntlv = entity_to_new_value(tl);
          tf = transformer_value_substitute(tf, nlv, ntlv);
          if(entity_is_argument_p(ntlv, transformer_arguments(tf))) {
            entity olv = external_entity_to_old_value(l);
            entity otlv = entity_to_old_value(tl);
            tf = transformer_value_substitute(tf, olv, otlv);
          }
        }
      }
    }
    gen_free_list(tcrl);
  }
  gen_free_list(ll);
  return tf;
}

References CELL, cell_any_reference(), constant_memory_access_path_to_location_entity(), ENTITY, entity_basic_concrete_type(), entity_initial, entity_is_argument_p(), entity_to_new_value(), entity_to_old_value(), entity_undefined_p, external_entity_to_new_value(), external_entity_to_old_value(), FOREACH, gen_free_list(), generic_atomic_points_to_reference_p(), NIL, pips_assert, points_to_reference_to_concrete_type(), reference_indices, reference_to_points_to_translations(), reference_variable, transformer_arguments, transformer_to_analyzed_locations(), transformer_value_substitute(), type_equal_p(), value_reference, and value_reference_p.

Referenced by new_substitute_stubs_in_transformer().

Here is the call graph for this function:

Here is the caller graph for this function:

user_call_to_points_to_interprocedural_binding_set()

set user_call_to_points_to_interprocedural_binding_set	(	call	c,
		pt_map	pt_caller
	)

Compute the binding relations in a complete interprocedural way: be as accurate as possible.

This piece of code has been copied from user_call_to_points_to_interprocedural(), which should be modularized...

Not much to do if both IN and OUT are empty, except if OUT is bottom (see below)

For the side effect on binding

set pt_in_filtered =

filter_formal_context_according_to_actual_context(fpcl,

pt_in,

pt_binded,

binding);

Parameters

pt_caller

t_caller

Definition at line 79 of file points_to.c.

{
  pips_internal_error("points-to library not available");
  return NIL;
}

References NIL, and pips_internal_error.

Referenced by new_substitute_stubs_in_transformer(), and substitute_stubs_in_transformer().

Here is the caller graph for this function: