interprocedural.c File Reference

#include <stdlib.h>
#include <stdio.h>
#include "genC.h"
#include "linear.h"
#include "ri.h"
#include "effects.h"
#include "misc.h"
#include "properties.h"
#include "ri-util.h"
#include "effects-util.h"
#include "effects-generic.h"
#include "pipsdbm.h"
#include "prettyprint.h"
#include "points-to.h"
#include "transformer.h"
#include "semantics.h"

Include dependency graph for interprocedural.c:

Go to the source code of this file.

Functions
list	points_to_cells_parameters (list dl)
	Transform a list of parameters of type "entity" to a list of cells. More...
list	points_to_cells_pointer_arguments (list al)
	Transform a list of arguments of type "expression" to a list of cells. More...
points_to_graph	user_call_to_points_to (call c, points_to_graph pt_in, list el)
	FI: limited to the interprocedural option. More...
list	user_call_to_points_to_sinks (call c, type et __attribute__((unused)), pt_map in __attribute__((unused)), bool eval_p)
	FI: I assume we do not need the eval_p parameter here. More...
void	remove_arcs_from_pt_map (points_to pts, set pt_out)
pt_map	user_call_to_points_to_fast_interprocedural (call c, pt_map pt_in, list csel __attribute__((unused)))
	ompute the points to relations in a fast interprocedural way More...
bool	recursive_filter_formal_context_according_to_actual_context (list fcl, set pt_in, set pt_binded, set binding, set filtered)
	This function looks for successors of elements of list "fcl" both in points-to relations "pt_in" and "pt_binded". More...
static type	constant_string_type_to_string_type (type t)
	We have to handle constant strings such as "Hello!" and not to forget functional parameters or other types. More...
set	filter_formal_context_according_to_actual_context (list fpcl, set pt_in, set pt_binded, set binding)
	Filter "pt_in" according to "pt_binded". More...
static bool	new_recursive_filter_formal_context_according_to_actual_context (cell fc, cell ac, approximation ap, set pt_in, set pt_binded, set binding, set filtered)
	The code is derived from generic_points_to_cell_to_useful_pointer_cell() with no filtering and a direct processing of the pairs of pointers obtained. More...
static bool	merge_actual_and_formal_sinks (cell fc, list *pfcl, cell ac, list *pacl, set pt_in, set pt_binded, set filtered)
	Handle constant cells such as NULL and UNDEFINED (nowhere) in "fcl" and "acl". More...
static bool	new_recursive_filter_formal_context_according_to_actual_context_for_pointer_pair (cell fc, cell ac, approximation ap, set pt_in, set pt_binded, set binding, set filtered)
	fc and ac are two pointer cells with same or compatible pointer type More...
set	new_filter_formal_context_according_to_actual_context (list fpcl, set pt_in, set pt_binded, set binding)
set	filter_formal_out_context_according_to_formal_in_context (set out, set in, list wpl, entity f)
	If an address has not been written, i.e. More...
void	points_to_translation_of_struct_formal_parameter (cell fc, cell ac, approximation a, type st, set translation)
bool	points_to_translation_mapping_is_typed_p (set translation)
void	points_to_translation_of_formal_parameters (list fpcl, list al, pt_map pt_in, set translation)
	List al and fpcl are assumed consistent, and consistent with the formal parameter ranks. More...
void	add_implicitly_killed_arcs_to_kill_set (set pt_kill, list wpl, set pt_caller, set pt_out_callee_filtered, set binding, entity f)
	Initial comments: add arcs of set "pt_caller" to set "pt_kill" if their origin cells are not in the list of written pointers "wpl" but is the origin of some exact arc in "pt_out_callee_filtered". More...
list	translation_transitive_closure (cell c, set translation)
bool	aliased_translation_p (list fpcl, set translation)
	See if two cells in "fpcl" point toward the same location via the transitive closure of "translation". More...
static set	lower_points_to_approximations_according_to_write_effects (set pt_end, list wpl)
	It is partly a kill and partly a gen operation. More...
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...
pt_map	user_call_to_points_to_interprocedural (call c, pt_map pt_caller)
	Compute the points-to relations in a complete interprocedural way: be as accurate as possible. More...
pt_map	user_call_to_points_to_intraprocedural (call c, pt_map pt_in, list el __attribute__((unused)))
set	compute_points_to_kill_set (list written_must_translated, set pt_caller, set binding __attribute__((unused)))
	Translate the "out" set into the scope of the caller. More...
list	points_to_cell_translation (cell sr1, set binding, entity f)
	Compute the list of cells that correspond to cell "sr1" according to the translation mapping "bm" when function "f" is called. More...
list	generic_points_to_cells_translation (list cl, set binding, entity f, bool exact_p)
	Allocate a new list with the translations of the cells in cl, when their translation make sense. More...
list	points_to_cells_translation (list cl, set binding, entity f)
	Allocate a new list with the translations of the cells in cl, when their translation make sense. More...
list	points_to_cells_exact_translation (list cl, set binding, entity f)
	Allocate a new list with the translations of the cells in cl, when their translation make sense and is unique (one-to-one mapping). More...
set	compute_points_to_gen_set (set pt_out, list Written, set binding, entity f)
	Translate the out set in the scope of the caller using the binding information, but eliminate irrelevant arcs using Written and the type of the source. More...
set	points_to_binding_arguments (cell c1, cell c2, set in, set pt_binded)
	Recursively find all the arcs, "ai", starting from the argument "c1" using "in", find all the arcs, "aj", starting from the parameter "c2" using "pt_binded", map each node "ai" to its corresponding "aj" and store the "ai->aj" arc in a new set, "bm". More...
static list	generic_written_pointers_set (list eff, bool exact_p)
	Filter out written effects on pointers. More...
list	written_pointers_set (list eff)
	Filter out written effects on pointers. More...
list	certainly_written_pointers_set (list eff)
	Filter out certainly written effects on pointers. More...
set	compute_points_to_binded_set (entity called_func, list real_args, set pt_caller, bool *success_p)
	For each actual argument "r" and its corresponding formal one "f", create the assignment "f = r;" and then compute the points-to set "s" generated by the assignment. More...
set	points_to_binding (list args, set in, set pt_binded)
	Apply points_to_binding_arguments() to each pair (, complete the process of binding each element of "in" to its corresponding memory address at the call site. More...
list	generic_points_to_set_to_stub_cell_list (entity f, set s, list osl)
	Add cells referencing a points-to stub found in parameter "s" are copied and added to list "osl". More...
list	points_to_set_to_stub_cell_list (set s, list osl)
list	points_to_set_to_module_stub_cell_list (entity m, set s, list osl)
cell	points_to_source_alias (points_to pt, set pt_binded)
	Let "pt_binded" be the results of assignments of actual arguments to formal arguments (see compute_points_to_binded_set()). More...

Function Documentation

add_implicitly_killed_arcs_to_kill_set()

void add_implicitly_killed_arcs_to_kill_set	(	set	pt_kill,
		list	wpl,
		set	pt_caller,
		set	pt_out_callee_filtered,
		set	binding,
		entity	f
	)

Initial comments: add arcs of set "pt_caller" to set "pt_kill" if their origin cells are not in the list of written pointers "wpl" but is the origin of some exact arc in "pt_out_callee_filtered".

This is beneficial when "pt_out" is more precise than "pt_caller" because of a free or a test. This is detrimental when "pt_caller" is more precise than "pt_out_callee_filtered" because the intraprocedural analysis of the callee had to assume a possible NULL pointer that did not really exist (see Mensi.sub/struct_inter03.c). So it would be better to compute the intersection of "pt_caller" and "translation(pt_out, binding)" and to kill all arcs in "pt_caller" minus this intersection... if they are related in some way to the callee... Some more thinking needed.

Equations retrieved from the C code

K = { c | \exits pt c=source(pt) !\in Written ^ |translation(source(pt), binding, f)|==1 ^ atomic(translation(source(pt), binding, f) }

pt_kill = {pt in pt_caller | \exists c \in K binding(c)==source(pt)}

K is a set of cells defined in the frame of the callee and pt_kill a set of points-to defined in the frame of the caller.

Examples:

Indirect free of a pointed cell

"main() {p = malloc(); * my_free(p);}" with "my_free(int * p) {free(p);}".

p->heap in pt_caller must be removed from pt_end, hence p->heap belongs to pt_kill

Other possibilities must be linked to tests and executions errors.

void foo(int * ap) {bar(ap);}

void bar(int * fp) { *p = 1;}

As a result ap->_ap_1, EXACT because ap->NULL has been killed

void bar(int * fp) {if(fp==NULL) exit(1); return;}

The result should be the same as above.

Arc out_pt has been implicitly obtained

Parameters

pt_kill	t_kill
wpl	pl
pt_caller	t_caller
pt_out_callee_filtered	t_out_callee_filtered
binding	inding

Definition at line 1663 of file interprocedural.c.

{
  SET_FOREACH(points_to, out_pt, pt_out_callee_filtered) {
    cell source = points_to_source(out_pt);
    if(!points_to_cell_in_list_p(source, wpl)) {
      /* Arc out_pt has been implicitly obtained */
      approximation a = points_to_approximation(out_pt);
      // FI: let's assume that approximation subsumes atomicity
      if(approximation_exact_p(a)) {
        // source is defined in the formal context
        //points_to_graph binding_g =
        //   make_points_to_graph(false, binding);
        // list tl = points_to_source_to_sinks(source, binding_g, false);
        list tl = points_to_cell_translation(source, binding, f);
        int  ntl = (int) gen_length(tl);
        cell t_source = cell_undefined;
        if(ntl==1) {
          t_source = CELL(CAR(tl));
          if(generic_atomic_points_to_cell_p(t_source, false)) {
            SET_FOREACH(points_to, pt, pt_caller) {
              cell pt_source = points_to_source(pt);
              if(points_to_cell_equal_p(t_source, pt_source)) {
                // FI: do not worry about sharing of arcs
                add_arc_to_simple_pt_map(pt, pt_kill);
              }
            }
          }
          gen_free_list(tl);
        }
      }
    }
  }
}

References add_arc_to_simple_pt_map, approximation_exact_p, CAR, CELL, cell_undefined, f(), gen_free_list(), gen_length(), generic_atomic_points_to_cell_p(), int, points_to_approximation, points_to_cell_equal_p(), points_to_cell_in_list_p(), points_to_cell_translation(), points_to_source, and SET_FOREACH.

Referenced by user_call_to_points_to_interprocedural().

Here is the call graph for this function:

Here is the caller graph for this function:

aliased_translation_p()

bool aliased_translation_p	(	list	fpcl,
		set	translation
	)

See if two cells in "fpcl" point toward the same location via the transitive closure of "translation".

| must_conflict_p

Print the transitive closures

Clean up the hash-table...

Parameters

fpcl	pcl
translation	ranslation

Definition at line 1735 of file interprocedural.c.

{
  bool alias_p = false;
  hash_table closure = hash_table_make(hash_pointer, 0);
  list c_fpcl = fpcl;
  list p_fpcl = fpcl;
 
  for( ; !ENDP(c_fpcl); POP(c_fpcl)) {
    cell c = CELL(CAR(c_fpcl));
    list succ_l = translation_transitive_closure(c, translation);
    hash_put(closure, (void *) c, (void *) succ_l);
    for(p_fpcl = fpcl; p_fpcl!=c_fpcl; POP(p_fpcl)) {
      cell p_c = CELL(CAR(p_fpcl));
      list p_succ_l = (list) hash_get(closure, (void *) p_c);
      list c_succ_l = gen_copy_seq(succ_l);
      // FI: this is not sufficient, conflicts between cells should be
      // checked to take into account abstract locations.
      // gen_list_and(&c_succ_l, p_succ_l);
      bool may_conflict_p = points_to_cell_lists_may_conflict_p(c_succ_l, p_succ_l);
      bool must_conflict_p = points_to_cell_lists_must_conflict_p(c_succ_l, p_succ_l);
      //if(!ENDP(c_succ_l)) {
      if(may_conflict_p /*|| must_conflict_p*/ ) { // must implies may I guess
        alias_p = true;
        gen_free_list(c_succ_l);
        entity fp1 = reference_variable(cell_any_reference(c));
        entity fp2 = reference_variable(cell_any_reference(p_c));
        
        if(statement_points_to_context_defined_p())
          pips_user_warning("%saliasing detected between formal parameters "
                            "\"%s\" and \"%s\" at line %d.\n",
                            must_conflict_p? "" : "possible ",
                            entity_user_name(fp1),
                            entity_user_name(fp2),
                            points_to_context_statement_line_number());
        else {
          // In case this function is used in an effect context
          pips_user_warning("%saliasing detected between formal parameters "
                            "\"%s\" and \"%s\".\n",
                            must_conflict_p? "" : "possible ",
                            entity_user_name(fp1),
                            entity_user_name(fp2));
        }
        break;
      }
      gen_free_list(c_succ_l);
    }
  }
 
  if(alias_p) {
    /* Print the transitive closures */
    HASH_MAP(c, succs,
             { entity fp = reference_variable(cell_any_reference((cell) c));
               fprintf(stderr, "\"%s\" -> ", entity_user_name(fp));
               print_points_to_cells((list) succs);
               fprintf(stderr, "\n");
             }, closure);
  }
 
  /* Clean up the hash-table... */
  HASH_MAP(c, succs, {gen_free_list((list) succs);}, closure);
 
  hash_table_free(closure);
  return alias_p;
}

References CAR, CELL, cell_any_reference(), ENDP, entity_user_name(), fprintf(), gen_copy_seq(), gen_free_list(), hash_get(), HASH_MAP, hash_pointer, hash_put(), hash_table_free(), hash_table_make(), pips_user_warning, points_to_cell_lists_may_conflict_p(), points_to_cell_lists_must_conflict_p(), points_to_context_statement_line_number(), POP, print_points_to_cells, reference_variable, statement_points_to_context_defined_p(), and translation_transitive_closure().

Referenced by user_call_to_points_to_interprocedural().

Here is the call graph for this function:

Here is the caller graph for this function:

certainly_written_pointers_set()

list certainly_written_pointers_set

(

list

eff

)

Filter out certainly written effects on pointers.

Parameters

eff

ff

Definition at line 2614 of file interprocedural.c.

                                              {
  return generic_written_pointers_set(eff, true);
}

References generic_written_pointers_set().

Referenced by user_call_to_points_to_interprocedural().

Here is the call graph for this function:

Here is the caller graph for this function:

compute_points_to_binded_set()

set compute_points_to_binded_set	(	entity	called_func,
		list	real_args,
		set	pt_caller,
		bool *	success_p
	)

For each actual argument "r" and its corresponding formal one "f", create the assignment "f = r;" and then compute the points-to set "s" generated by the assignment.

The result is the union of "pt_caller" and "s".

Be careful with vararags

This is not sufficient to handle varargs. Much more thinking needed. And corect examples.

C does not support array assignments...

This may happen with a constant string as actual parameter and an array, bounded or not, as formal parameter.

A formal array can be called with a dereferencing expression

See Pointers/Mensi.sub/array_pointer_free01: array fp is associated to &p[0] or to p->q or to c.a ...

It would be nice to build an assignment of rhs to fp and to let it deal with the many possible kinds of assignments. But if it is a pure points-to function, the symbolic subscripts are going to be lost. This is fine for points-to translation, but not OK for effects translation.

In the short term, build the assignment...

The assignment failed because the call site is not compatible with the caller.

Parameters

called_func	alled_func
real_args	eal_args
pt_caller	t_caller
success_p	uccess_p

Definition at line 2623 of file interprocedural.c.

{ 
  set s = set_generic_make(set_private, points_to_equal_p,
                           points_to_rank);
  set pt_binded = set_generic_make(set_private, points_to_equal_p,
                                   points_to_rank);
 
  *success_p = true; // default value
 
  /* Be careful with vararags
   *
   * This is not sufficient to handle varargs. Much more thinking
   * needed. And corect examples.
   */
  type ft = entity_basic_concrete_type(called_func); // function type
  functional fft = type_functional(ft);
  list ptl = functional_parameters(fft); // parameter type list
  int mnp = (int) gen_length(ptl); // maximum number of formal parameters
  if(!ENDP(ptl)) {
    // last parameter type
    type lpt = parameter_type(PARAMETER(CAR(gen_last(ptl))));
    if(type_varargs_p(lpt))
      mnp--;
  }
 
  cons *pc;
  int ipc;
  s = set_assign(s, pt_caller);
  for (ipc = 1, pc = real_args; pc != NIL; pc = CDR(pc), ipc++) {
    expression rhs = EXPRESSION(CAR(pc));
    int tr = ipc>mnp? mnp : ipc;
    entity fp = find_ith_parameter(called_func, tr);
    type fpt = entity_basic_concrete_type(fp);
    if(array_type_p(fpt)) {
      /* C does not support array assignments... */
      if(expression_reference_p(rhs)) {
        reference r = expression_reference(rhs);
        entity v = reference_variable(r);
        list nptl = NIL; // New points-to list
        SET_FOREACH(points_to, pt, pt_caller) {
          cell c = points_to_source(pt);
          reference cr = cell_any_reference(c);
          entity cv = reference_variable(cr);
          if(cv==v) {
            points_to npt = copy_points_to(pt);
            cell nc = points_to_source(npt);
            reference ncr = cell_any_reference(nc);
            reference_variable(ncr) = fp;
            nptl = CONS(POINTS_TO, npt, nptl);
          }
        }
        FOREACH(POINTS_TO, npt, nptl)
          add_arc_to_simple_pt_map(npt, s);
        gen_free_list(nptl);
      }
      else if(expression_call_p(rhs) && expression_string_constant_p(rhs)) {
        /* This may happen with a constant string as actual parameter
           and an array, bounded or not, as formal parameter. */
        ; // Nothing to do: the constant string does not point to anything
      }
      else if(expression_call_p(rhs)) {
        type et = array_type_to_element_type(fpt);
        if(struct_type_p(et)) {
          /* A formal array can be called with a dereferencing expression
           *
           * See Pointers/Mensi.sub/array_pointer_free01: array fp is
           * associated to &p[0] or to p->q or to c.a ...
           */
          call c = expression_call(rhs);
          entity f = call_function(c);
          pips_internal_error("Not implemented yet. Function \"%s\".\n",
                              entity_user_name(f));
        }
        else if(pointer_type_p(et)) {
          call c = expression_call(rhs);
          entity f = call_function(c);
          pips_internal_error("Not implemented yet. Function \"%s\".\n",
                              entity_user_name(f));
        }
        else {
          // No pointer related information
          ;
        }
      }
      else
        pips_internal_error("Not implemented yet.\n");
    }
    else {
      /* It would be nice to build an assignment of rhs to fp and to
         let it deal with the many possible kinds of assignments. But
         if it is a pure points-to function, the symbolic subscripts
         are going to be lost. This is fine for points-to translation,
         but not OK for effects translation. */
 
      if(pointer_type_p(fpt)) {
        points_to_graph s_g = make_points_to_graph(false, s);
        list sinks = expression_to_points_to_cells(rhs, s_g, true, false);
        int nsinks = (int) gen_length(sinks);
        FOREACH(CELL, sink, sinks) {
          cell o = make_cell_reference(make_reference(fp, NIL));
          cell d = copy_cell(sink);
          bool anywhere_p = anywhere_cell_p(d)
            || cell_typed_anywhere_locations_p(d);
          bool heap_p = heap_cell_p(d);
          approximation a = (nsinks==1 && !anywhere_p && !heap_p) ? make_approximation_exact() :
            make_approximation_may();
          descriptor desc = make_descriptor_none();
          points_to pt = make_points_to(o, d, a, desc);
          add_subscript_dependent_arc_to_simple_pt_map(pt, s);
        }
      }
      else if(struct_type_p(fpt)) {
        /* In the short term, build the assignment... */
        expression lhs = entity_to_expression(fp);
        points_to_graph s_g = make_points_to_graph(false, s);
        points_to_graph a_g = assignment_to_points_to(lhs, rhs, s_g);
        if(points_to_graph_bottom(a_g)) {
          /* The assignment failed because the call site is not
             compatible with the caller. */
          *success_p = false;
        }
        else {
          s = set_assign(s, points_to_graph_set(a_g));
        }
      }
      else {
        ; // do nothing for other types
      }
    }
  }
 
  SET_FOREACH(points_to, pt, s) {
    reference r = cell_any_reference(points_to_sink(pt));
    entity e = reference_variable(r);
    if(stub_entity_of_module_p(e, called_func))
      s = set_del_element(s,s,(void*)pt);
  }
  pt_binded = set_union(pt_binded, s, pt_caller);
  return pt_binded;
}

References add_arc_to_simple_pt_map, add_subscript_dependent_arc_to_simple_pt_map(), anywhere_cell_p(), array_type_p(), array_type_to_element_type(), assignment_to_points_to(), call_function, CAR, CDR, CELL, cell_any_reference(), cell_typed_anywhere_locations_p(), CONS, copy_cell(), copy_points_to(), ENDP, entity_basic_concrete_type(), entity_to_expression(), entity_user_name(), EXPRESSION, expression_call(), expression_call_p(), expression_reference(), expression_reference_p(), expression_string_constant_p(), expression_to_points_to_cells(), f(), find_ith_parameter(), FOREACH, functional_parameters, gen_free_list(), gen_last(), gen_length(), heap_cell_p(), int, make_approximation_exact(), make_approximation_may(), make_cell_reference(), make_descriptor_none(), make_points_to(), make_points_to_graph(), make_reference(), NIL, PARAMETER, parameter_type, pips_internal_error, pointer_type_p(), POINTS_TO, points_to_equal_p(), points_to_graph_bottom, points_to_graph_set, points_to_rank(), points_to_sink, points_to_source, reference_variable, set_assign(), set_del_element(), SET_FOREACH, set_generic_make(), set_private, set_union(), struct_type_p(), stub_entity_of_module_p(), type_functional, and type_varargs_p.

Referenced by user_call_to_points_to_fast_interprocedural(), user_call_to_points_to_interprocedural(), and user_call_to_points_to_interprocedural_binding_set().

Here is the call graph for this function:

Here is the caller graph for this function:

compute_points_to_gen_set()

set compute_points_to_gen_set	(	set	pt_out,
		list	Written,
		set	binding,
		entity	f
	)

Translate the out set in the scope of the caller using the binding information, but eliminate irrelevant arcs using Written and the type of the source.

This is pt_gen_1 in Amira Mensi's dissertation.

Also, pay attention to translation errors because they are related to programming bugs, such as pointer arithmetic applied to pointers to scalar.

Consider all points-to arcs "(sr1, sk1)" in "pt_out"

Keep arcs whose source is:

• an array, because it has certainly not been passed by copy;
• not a scalar formal parameter: again, no copy passing;
• not written by the procedure, because, even if it passed by copy, the actual parameter is aliased.

In other word, get rid of scalar formal parameter that are written.

Translate sr1

Translate sk1 if needed

The translation of pt's sink failed.

Note: the piece of code below is replicated

The caller does not have to have counterparts for all hypothetical stubs that may be developped in callee.

The translation of pt's source failed. This may occur because the callee had to assume a pointer points to an array, whereas the call site associates it to a scalar.

See for instance Pointers/formal_parameter01.c

But this may also occur because the formal parameter cannot be translated because the effective argument is an address_of expression. See for instance EffectsWithPointsTO/call01.c.

We have no way to guess here the reason for the translation failure...

Could be a user error, but you may prefer to go on with the points-to analysis to perform some dead code elimination later...

Parameters

pt_out	t_out
Written	ritten
binding	inding

Definition at line 2342 of file interprocedural.c.

{
  set gen = new_simple_pt_map();                
  // To avoid redundant error messages
  list translation_failures = NIL;
 
  /* Consider all points-to arcs "(sr1, sk1)" in "pt_out" */
  SET_FOREACH(points_to, p, pt_out) {
    cell sr1 = points_to_source(p); 
    reference r_1 = cell_any_reference(sr1);
    entity v_1 = reference_variable(r_1);
    type t_1 = entity_basic_concrete_type(v_1);
    /* Keep arcs whose source is:
     *
     *  - an array, because it has certainly not been passed by copy;
     *
     *  - not a scalar formal parameter: again, no copy passing;
     *
     *  - not written by the procedure, because, even if it passed by
     *    copy, the actual parameter is aliased.
     *
     * In other word, get rid of scalar formal parameter that are written.
     */
    if(array_type_p(t_1)
       || !formal_parameter_p(v_1)
       || !points_to_cell_in_list_p(sr1, Written)) {
      list new_sk_l = NIL;
      approximation a = copy_approximation(points_to_approximation(p));
      cell sk1 = points_to_sink(p); 
 
      /* Translate sr1 */
      list new_sr_l = points_to_cell_translation(sr1, binding, f);
 
      if(!ENDP(new_sr_l)) {
        /* Translate sk1 if needed */
        reference r_2 = cell_any_reference(sk1);
        entity v_2 = reference_variable(r_2);
        if (null_cell_p(sk1) || nowhere_cell_p(sk1) || heap_cell_p(sk1)
            || anywhere_cell_p(sk1) || cell_typed_anywhere_locations_p(sk1)
            || entity_to_module_entity(v_2)!=f) {
          cell new_sk = copy_cell(sk1);
          new_sk_l = CONS(CELL, new_sk, new_sk_l);
        }
        else
          new_sk_l = points_to_cell_translation(sk1, binding, f);
 
        if(!ENDP(new_sk_l)) {
          int new_sk_n = (int) gen_length(new_sk_l);
          FOREACH(CELL, new_sr, new_sr_l) {
            approximation na = approximation_undefined;
            if(!atomic_points_to_cell_p(new_sr)
               || new_sk_n>1
               || (new_sk_n==1
                   && !atomic_points_to_cell_p(CELL(CAR(new_sk_l))))) {
              na = make_approximation_may();
            }
            else
              na = copy_approximation(a);
            FOREACH(CELL, new_sk, new_sk_l) {
              points_to new_pt = make_points_to(copy_cell(new_sr),
                                                copy_cell(new_sk),
                                                na,
                                                make_descriptor_none());
              set_add_element(gen, gen, (void*)new_pt);
            }
          }
          // gen_full_free_list(new_sr_l);
          // gen_full_free_list(new_sk_l);
          free_approximation(a);
        }
        else {
          /* The translation of pt's sink failed. */
          /* Note: the piece of code below is replicated */
          approximation a = points_to_approximation(p);
          if(approximation_may_p(a)) {
            if(!points_to_cell_in_list_p(sk1, translation_failures)) {
              /* The caller does not have to have counterparts for all
                 hypothetical stubs that *may* be developped in
                 callee. */
              pips_user_warning("Points-to sink cell sk1=\"%s\" could not be translated.\n",
                                points_to_cell_name(sk1));
              translation_failures = CONS(CELL, sk1, translation_failures);
            }
          }
          else {
            pips_user_warning("Points-to sink cell sk1=\"%s\" could not be translated but has to be.\n",
                            points_to_cell_name(sk1));
            set_free(gen);
            gen = set_undefined;
            break;
          }
        }
      }
      else {
        /* The translation of pt's source failed. This may occur
         * because the callee had to assume a pointer points to an
         * array, whereas the call site associates it to a scalar.
         *
         * See for instance Pointers/formal_parameter01.c
         *
         * But this may also occur because the formal parameter cannot
         * be translated because the effective argument is an
         * address_of expression. See for instance
         * EffectsWithPointsTO/call01.c.
         *
         * We have no way to guess here the reason for the translation
         * failure...
         */
        entity v = reference_variable(cell_any_reference(sr1));
        // FI: we should check that it is a formal parameter of "f"...
        if(!formal_parameter_p(v)) {
        approximation a = points_to_approximation(p);
        if(approximation_may_p(a)) {
          if(!points_to_cell_in_list_p(sr1, translation_failures)) {
            pips_user_warning("Points-to source cell sr1=\"%s\" could not be translated.\n",
                              points_to_cell_name(sr1));
            translation_failures = CONS(CELL, sr1, translation_failures);
          }
        }
        else {
          /* Could be a user error, but you may prefer to go on with
           * the points-to analysis to perform some dead code
           * elimination later...
           */
          pips_user_warning("Points-to source cell sr1=\"%s\" could not be translated but has to be.\n",
                          points_to_cell_name(sr1));
          set_free(gen);
          gen = set_undefined;
        break;
        }
        }
      }
    }
  }
 
  gen_free_list(translation_failures);
 
  ifdebug(1) {
    if(set_undefined_p(gen))
      fprintf(stderr, "pt_gen is bottom\n");
    else
      print_points_to_set("pt_gen_1", gen);
  }
 
  return gen;  
}

References anywhere_cell_p(), approximation_may_p, approximation_undefined, array_type_p(), atomic_points_to_cell_p(), CAR, CELL, cell_any_reference(), cell_typed_anywhere_locations_p(), CONS, copy_approximation(), copy_cell(), ENDP, entity_basic_concrete_type(), entity_to_module_entity(), f(), FOREACH, formal_parameter_p(), fprintf(), free_approximation(), gen(), gen_free_list(), gen_length(), heap_cell_p(), ifdebug, int, make_approximation_may(), make_descriptor_none(), make_points_to(), new_simple_pt_map, NIL, nowhere_cell_p(), null_cell_p(), pips_user_warning, points_to_approximation, points_to_cell_in_list_p(), points_to_cell_name(), points_to_cell_translation(), points_to_sink, points_to_source, print_points_to_set(), reference_variable, set_add_element(), SET_FOREACH, set_free(), set_undefined, and set_undefined_p.

Referenced by user_call_to_points_to_interprocedural().

Here is the call graph for this function:

Here is the caller graph for this function:

compute_points_to_kill_set()

set compute_points_to_kill_set	(	list	written_must_translated,
		set	pt_caller,
		set binding	__attribute__(unused)
	)

Translate the "out" set into the scope of the caller.

Shouldn't it be the "written" list that needs to be translated?

Remove all points-to arc from pt_caller whose origin has been fully written

Definition at line 2146 of file interprocedural.c.

{
  set kill = new_simple_pt_map();       
  list written_cs = written_must_translated;
#if 0
  list written_cs = NIL;
  set bm = binding;
 
  FOREACH(CELL, c, written) {
    cell new_sr = cell_undefined; 
    reference r_1 = cell_any_reference(c);
    entity v_1 = reference_variable(r_1);
    if(!formal_parameter_p(v_1)) {
      list ind1 = reference_indices(r_1);
      SET_FOREACH(points_to, pp, bm) {
        cell sr2 = points_to_source(pp); 
        cell sk2 = points_to_sink(pp); 
        reference r22 = copy_reference(cell_to_reference(sk2));
        /* FI->AM: this test is loop invariant... and performed within the loop */
        if(!source_in_set_p(c, bm)) {
          reference r_12 = cell_any_reference(sr2);
          entity v_12 = reference_variable( r_12 );
          if(same_string_p(entity_local_name(v_1),entity_local_name(v_12))) { 
            reference_indices(r22) = gen_nconc(reference_indices(r22),
                                               gen_full_copy_list(ind1));
            new_sr = make_cell_reference(r22);
            // FI->AM: I guess this statement was forgotten
            written_cs = CONS(CELL, new_sr, written_cs);
            break;
          }
          else if (heap_cell_p(c)) {
            written_cs = CONS(CELL, c, written_cs);
          }
        }
        else if(points_to_compare_cell(c,sr2)) {
          written_cs = CONS(CELL, points_to_sink(pp), written_cs);
          // break; // FI: why not look for other possible translations?
        }
      }
    }
  }
#endif
  
  /* Remove all points-to arc from pt_caller whose origin has been
     fully written */
  FOREACH(CELL, c, written_cs) {
    SET_FOREACH(points_to, pt, pt_caller) {
      if(points_to_cell_equal_p(c, points_to_source(pt))
         && atomic_points_to_cell_p(c))
        set_add_element(kill, kill, (void*)pt);
    }
  }
 
  return kill;
}

References atomic_points_to_cell_p(), CELL, cell_any_reference(), cell_to_reference(), cell_undefined, CONS, copy_reference(), entity_local_name(), FOREACH, formal_parameter_p(), gen_full_copy_list(), gen_nconc(), heap_cell_p(), make_cell_reference(), new_simple_pt_map, NIL, points_to_cell_equal_p(), points_to_compare_cell(), points_to_sink, points_to_source, reference_indices, reference_variable, same_string_p, set_add_element(), SET_FOREACH, source_in_set_p(), and written.

Referenced by user_call_to_points_to_fast_interprocedural(), and user_call_to_points_to_interprocedural().

Here is the call graph for this function:

Here is the caller graph for this function:

constant_string_type_to_string_type()

static type constant_string_type_to_string_type ( type  t )

static

We have to handle constant strings such as "Hello!" and not to forget functional parameters or other types.

Basically, type "t" is returned unchanged, unless "t" is a functional type "void->string".

The initial implementation of this function used the cell "ac" and the variable "a" whose type is sought and was safer:

reference ar = cell_any_reference(ac); entity a = reference_variable(ar); if(constant_string_entity_p(a)) nt = ...

Any function of type "void->string" is considered a "string" object. Let's hope it is ok in the points-to environment. Else, an additional parameter must be passed.

This function is located in the points-to library because it is where it is useful. It would be even more useful if it returned a "char *" or a "char[]", but this would imply a type allocation. As it is, no new type is allocated.

To be fully effective, the argument must be a basic concrete type.

Definition at line 543 of file interprocedural.c.

{
  type nt = t; // default returned value: no change
  if(type_functional_p(t)) {
    functional f = type_functional(t);
    type rt = functional_result(f);
    list pl = functional_parameters(f);
    if(ENDP(pl) && string_type_p(rt))
      nt = rt;
  }
  return nt;
}

References ENDP, f(), functional_parameters, functional_result, pl, string_type_p(), type_functional, and type_functional_p.

Referenced by filter_formal_context_according_to_actual_context(), new_filter_formal_context_according_to_actual_context(), and points_to_translation_mapping_is_typed_p().

Here is the call graph for this function:

Here is the caller graph for this function:

filter_formal_context_according_to_actual_context()

set filter_formal_context_according_to_actual_context	(	list	fpcl,
		set	pt_in,
		set	pt_binded,
		set	binding
	)

Filter "pt_in" according to "pt_binded".

For instance, a formal parameter can point to NULL in "pt_in" only if it also points to NULL in "pt_binded". In the same way, a formal parameter can point to a points-to stub in "pt_in" only if it points to a non-NULL target in "pt_binded". Also, a formal parameter cannot points exactly to UNDEFINED in "pt_binded" as it would be useless (not clear if we can remove such an arc when it is a may arc...). Finally, each formal parameter must still point to something.

The context of the caller may be insufficiently developped because its does not use explictly a pointer that is a formal parameter for it. For instance:

foo(int ***p) {bar(int ***p);}

The formal context of "foo()" must be developped when the formal context of "bar()" is imported. For instance, *p, **p and ***p may be accessed in "bar()", generating points-to stub in "bar". Similar stubs must be generated here for "foo()" before the translation can be performed.

This is also true for global variables. pt_in may contain arcs that should exist in pt_binded, and hence pt_caller. It may also contain arcs that deny the existence of some arcs in pt_caller.

Copy arcs "pt" from "pt_in" into the "filtered" set if they are compatible with "pt_binded". The set "pt_in" is reduced.

Do we have the same arc in pt_binded?

We have to deal recursively with stubs of the formal context and first with the global variables...although they, or their stubs, do not require any translation? Why is the points-to information about q lost in the translation of the call site to call03 in main (PointersWithEffects/call03.c)

FI: I do not understand why I have to do this for EffectsWithPointsTo/pointer_modif04.c. Because the arc "pt" in "pt_in" is more precise than the information available in "pt_caller". For instance, "pt_in" may contain "stderr->_stderr_0[0], Exact", while "pt_caller" may contain "stderr->_stderr_0[0], May", "stderr->NULL, May". Basically, we have not thought about the kill set generated for the global variables.

Useless when called from effects... In fact, it should never be called from effects...

FI: we do not know what we really do here... An arc is not taken into account, but it might be taken into account recursively below.

Compute the binding relation for sinks of the formal arguments and global variables

We have to handle constant strings such as "Hello!" and not to forget functional parameters.

If "fc" is not a pointer, look for pointers in "fc"

Now, we have to call about the same function recursively on the list of formal sinks

Some arcs have been removed, so other arcs may be promoted from "may" to "exact".

Parameters

fpcl	pcl
pt_in	t_in
pt_binded	t_binded
binding	inding

Definition at line 582 of file interprocedural.c.

{
  bool ok_p = true;
  set filtered = new_simple_pt_map();
  // list gvcl = NIL; // global variable cell list
 
  /* Copy arcs "pt" from "pt_in" into the "filtered" set if they are
     compatible with "pt_binded". The set "pt_in" is reduced. */
  SET_FOREACH(points_to, pt, pt_in) {
    cell source = points_to_source(pt);
    if(related_points_to_cell_in_list_p(source, fpcl)) {
      cell sink = points_to_sink(pt);
      if(null_cell_p(sink)) {
        /* Do we have the same arc in pt_binded? */
        if(arc_in_points_to_set_p(pt, pt_binded)) {
          points_to npt = copy_points_to(pt);
          add_arc_to_simple_pt_map(npt, filtered);
        }
        else {
          ; // do not copy this arc in filtered set
        }
      }
      else {
        if(cell_points_to_non_null_sink_in_set_p(source, pt_binded)) {
          points_to npt = copy_points_to(pt);
          add_arc_to_simple_pt_map(npt, filtered);
        }
        else {
          ; // do not copy this arc in filtered set
        }
      }
    }
    else {
      /* We have to deal recursively with stubs of the formal context
         and first with the global variables...although they, or their
         stubs, do not require any translation? Why is the points-to
         information about q lost in the translation of the call site
         to call03 in main (PointersWithEffects/call03.c) */
      reference r = cell_any_reference(source);
      entity v = reference_variable(r);
      if(!arc_in_points_to_set_p(pt, pt_binded)) {
        // FI: necessary for Pointers/global10
        if(static_global_variable_p(v) || global_variable_p(v)) {
          //gvcl = CONS(CELL, source, gvcl);
          points_to npt = copy_points_to(pt);
          add_arc_to_simple_pt_map(npt, filtered);
          /* FI: I do not understand why I have to do this for
             EffectsWithPointsTo/pointer_modif04.c. Because the arc "pt"
             in "pt_in" is more precise than the information available
             in "pt_caller". For instance, "pt_in" may contain
             "stderr->_stderr_0[0], Exact", while "pt_caller" may
             contain "stderr->_stderr_0[0], May", "stderr->NULL,
             May". Basically, we have not thought about the kill set
             generated for the global variables. */
          if(statement_points_to_context_defined_p()) {
            /* Useless when called from effects... In fact, it should
               never be called from effects... */
            //add_arc_to_points_to_context(npt);
            update_points_to_context_with_arc(npt);
          }
          else {
            // pips_internal_error("This function should not reach this point"
            //                  " when called from effects, simple or generic.");
            // update_points_to_context_with_arc(npt);
            ; // Do nothing
          }
        }
        else {
          /* FI: we do not know what we really do here... An arc is not
             taken into account, but it might be taken into account
             recursively below. */
          ;
        }
      }
    }
  }
 
  /* Compute the binding relation for sinks of the formal
     arguments and global variables */
  //list fpgvcl = gen_nconc(fpcl, gvcl);
  list fcl = NIL;
  points_to_graph filtered_g = make_points_to_graph(false, filtered);
  points_to_graph pt_binded_g = make_points_to_graph(false, pt_binded);
  FOREACH(CELL, c, fpcl) {
  //FOREACH(CELL, c, fpgvcl) {
    list fl = points_to_source_to_any_sinks(c, filtered_g, false); // formal list
    list al = points_to_source_to_any_sinks(c, pt_binded_g, false); // actual list
    int nfl = (int) gen_length(fl);
    int nal = (int) gen_length(al);
    approximation approx = approximation_undefined;
 
    // FI: que fait-on avec nfl==0, comme dans
    // Pointers/StrictTyping.sub/struct08.c ou nfl vaut 0 parce que le
    // parametre effectif est undefined?
 
    if(nfl==1 && nal==1)
      approx = make_approximation_exact();
    else
      approx = make_approximation_may();
    FOREACH(CELL, fc, fl) {
      if(!null_cell_p(fc)) {
        FOREACH(CELL, ac, al) {
          if(!null_cell_p(ac) && !nowhere_cell_p(ac)) {
            type fc_t = points_to_cell_to_concrete_type(fc);
            type iac_t = points_to_cell_to_concrete_type(ac);
            type ac_t = constant_string_type_to_string_type(iac_t);
            /* We have to handle constant strings such as "Hello!"
               and not to forget functional parameters. */
            if(type_functional_p(ac_t)) {
              reference ar = cell_any_reference(ac);
              entity a = reference_variable(ar);
              if(constant_string_entity_p(a)) {
                ac_t = functional_result(type_functional(iac_t));
              }
            }
            // FI: which type equality should be chosen ?
            // if(!type_structurally_equal_p(fc_t, ac_t)
            if(!array_pointer_string_type_equal_p(fc_t, ac_t)
               && !overloaded_type_p(ac_t)) {
              if(array_type_p(ac_t)) {
                points_to_cell_add_zero_subscript(ac);
                type ac_nt = points_to_cell_to_concrete_type(ac);
                if(!type_structurally_equal_p(fc_t, ac_nt) && !overloaded_type_p(ac_nt)) {
                  // Pointers/pointer14.c
                  // FI: I am not sure it is the best translation
                  // It might be better to remove some zero subscripts from fc
                  points_to_cell_complete_with_zero_subscripts(ac);
                  type ac_nnt = points_to_cell_to_concrete_type(ac);
                  if(!type_structurally_equal_p(fc_t, ac_nnt) && !overloaded_type_p(ac_nnt))
                    pips_internal_error("translation failure for an array.\n");
                }
              }
              else {
                reference fr = cell_any_reference(fc);
                if(adapt_reference_to_type(fr, ac_t, points_to_context_statement_line_number))
                  ;
                else {
                  type fr_t = points_to_reference_to_concrete_type(fr);
                  reference ar = cell_any_reference(ac);
                  semantics_user_warning("Type \"%s\" for formal reference \"%s\" is incompatible with type \"%s\" for actual reference \"%s\".\n",
                                         type_to_full_string_definition(fr_t),
                                         reference_to_string(fr),
                                         type_to_full_string_definition(ac_t),
                                         reference_to_string(ar));
                  if(get_bool_property("POINTS_TO_STRICT_POINTER_TYPES")) {
                    pips_user_error
                      ("Translation failure for actual parameter \"%s\" at line %d.\n"
                       "Maybe property POINTS_TO_STRICT_POINTER_TYPES should be reset.\n",
                       reference_to_string(ar),
                       points_to_context_statement_line_number());
                    // pips_internal_error("translation failure.\n");
                  }
                  else {
                  pips_user_error
                    ("Translation failure for actual parameter \"%s\" at line %d.\n",
                     reference_to_string(ar),
                     points_to_context_statement_line_number());
                  }
                }
              }
            }
            points_to tr = make_points_to(copy_cell(fc), 
                                          copy_cell(ac), 
                                          copy_approximation(approx),
                                          make_descriptor_none());
            add_subscript_dependent_arc_to_simple_pt_map(tr, binding);
          }
        }
        /* If "fc" is  not a pointer, look for pointers in "fc" */
        list pcl = points_to_cell_to_useful_pointer_cells(fc, pt_in);
        fcl = gen_nconc(fcl, pcl);
        //fcl = CONS(CELL, fc, fcl);
      }
    }
    free_approximation(approx);
  }
 
  ifdebug(8) {
    pips_debug(8, "First filtered IN set for callee at call site:\n");
    print_points_to_set("", filtered);
    pips_debug(8, "First translation mapping for call site:\n");
    print_points_to_set("", binding);
  }
 
  pips_assert("The points-to translation mapping is well typed",
              points_to_translation_mapping_is_typed_p(binding));
 
  /* Now, we have to call about the same function recursively on the
     list of formal sinks */
  if(!ENDP(fcl)) {
    ok_p = recursive_filter_formal_context_according_to_actual_context
      (fcl, pt_in, pt_binded, binding, filtered);
    gen_free_list(fcl);
  }
 
  if(ok_p) {
  /* Some arcs have been removed, so other arcs may be promoted from
     "may" to "exact". */
    upgrade_approximations_in_points_to_set(filtered_g);
  }
  else {
    set_free(filtered);
    filtered = set_undefined;
  }
 
  ifdebug(8) {
    pips_debug(8, "Final filtered IN set for callee at call site:\n");
    print_points_to_set("", filtered);
    pips_debug(8, "Final mapping for call site:\n");
    print_points_to_set("", binding);
  }
    
  return filtered;
}

References adapt_reference_to_type(), add_arc_to_simple_pt_map, add_subscript_dependent_arc_to_simple_pt_map(), approximation_undefined, arc_in_points_to_set_p(), array_pointer_string_type_equal_p(), array_type_p(), CELL, cell_any_reference(), cell_points_to_non_null_sink_in_set_p(), constant_string_entity_p(), constant_string_type_to_string_type(), copy_approximation(), copy_cell(), copy_points_to(), ENDP, FOREACH, free_approximation(), functional_result, gen_free_list(), gen_length(), gen_nconc(), get_bool_property(), global_variable_p(), ifdebug, int, make_approximation_exact(), make_approximation_may(), make_descriptor_none(), make_points_to(), make_points_to_graph(), new_simple_pt_map, NIL, nowhere_cell_p(), null_cell_p(), overloaded_type_p(), pips_assert, pips_debug, pips_internal_error, pips_user_error, points_to_cell_add_zero_subscript(), points_to_cell_complete_with_zero_subscripts(), points_to_cell_to_concrete_type(), points_to_cell_to_useful_pointer_cells(), points_to_context_statement_line_number(), points_to_reference_to_concrete_type(), points_to_sink, points_to_source, points_to_source_to_any_sinks(), points_to_translation_mapping_is_typed_p(), print_points_to_set(), recursive_filter_formal_context_according_to_actual_context(), reference_to_string(), reference_variable, related_points_to_cell_in_list_p(), semantics_user_warning, SET_FOREACH, set_free(), set_undefined, statement_points_to_context_defined_p(), static_global_variable_p(), type_functional, type_functional_p, type_structurally_equal_p(), type_to_full_string_definition(), update_points_to_context_with_arc(), and upgrade_approximations_in_points_to_set().

Here is the call graph for this function:

filter_formal_out_context_according_to_formal_in_context()

set filter_formal_out_context_according_to_formal_in_context	(	set	out,
		set	in,
		list	wpl,
		entity	f
	)

If an address has not been written, i.e.

it is not in list "wpl", then the points-to information is the intersection of the in and out information.

The set "in" may be modified by side effect. A new set, "filtered_out" is computed. By definition, they are equivalent for the addresses that are not in list "wpl".

The arcs are shared by the different sets. But I may allocate new ones: yet another potential memory leak...

First, filter out according to in

The source of the arc may not have been modified but the sink probably has been freed: the arc must be preserved

The source of the arc has been modified: the arc must be preserved

the arc defining the return value must be preserved: no!

Is this points-to arc also in set "in"? With or without the same approximation?

Second, filter set "in" with respect to new set "filtered_out".

Is this points-to arc also in set "in"? With or without the same approximation?

Parameters

out	ut
in	n
wpl	pl

Definition at line 1263 of file interprocedural.c.

{
  set out_filtered = new_simple_pt_map();
 
  /* First, filter out according to in */
  SET_FOREACH(points_to, pt, out) {
    cell source = points_to_source(pt);
    entity se = reference_variable(cell_any_reference(source));
    entity rv = any_function_to_return_value(f);
    cell sink = points_to_sink(pt);
    if(nowhere_cell_p(sink)) {
      /* The source of the arc may not have been modified but the sink
         probably has been freed: the arc must be preserved */
      add_arc_to_simple_pt_map(pt, out_filtered);
    }
    else if(points_to_cell_in_list_p(source, wpl)) {
      /* The source of the arc has been modified: the arc must be preserved */
      add_arc_to_simple_pt_map(pt, out_filtered);
    }
    else if(se==rv) {
      /* the arc defining the return value must be preserved: no! */
      add_arc_to_simple_pt_map(pt, out_filtered);
    }
    else {
      /* Is this points-to arc also in set "in"? With or without the
         same approximation? */
      approximation a = approximation_undefined;
      if(similar_arc_in_points_to_set_p(pt, in, &a)) {
        approximation oa = points_to_approximation(pt);
        if(approximation_exact_p(oa)) {
          add_arc_to_simple_pt_map(pt, out_filtered);
        }
        else if(approximation_exact_p(a)) {
          cell nsource = copy_cell(source);
          cell nsink = copy_cell(points_to_sink(pt));
          approximation na = copy_approximation(a);
          points_to npt = make_points_to(nsource, nsink, na,
                                         make_descriptor_none());
          add_arc_to_simple_pt_map(npt, out_filtered);
        }
        else {
          add_arc_to_simple_pt_map(pt, out_filtered);
        }
      }
      else {
        ; // This arc cannot be preserved in "out_filtered"
      }
    }
  }
 
  /* Second, filter set "in" with respect to new set "filtered_out". */
  list to_be_removed = NIL;
  list to_be_added = NIL; // FI: why do you want to add stuff?
  SET_FOREACH(points_to, ipt, in) {
  /*
  hash_table _hash_ = set_private_get_hash_table(in);
  void * _point_ = NULL;
  for (points_to ipt;
       (_point_ =  hash_table_scan(_hash_, _point_, (void **) &ipt, NULL));) {
  */
    cell source = points_to_source(ipt);
    if(points_to_cell_in_list_p(source, wpl))
      ; // do nothing
    else {
      /* Is this points-to arc also in set "in"? With or without the
         same approximation? */
      approximation a = approximation_undefined;
      if(similar_arc_in_points_to_set_p(ipt, out, &a)) {
        approximation oa = points_to_approximation(ipt);
        if(approximation_exact_p(oa)) {
          ; // Do nothing
        }
        else if(approximation_exact_p(a)) {
          cell nsource = copy_cell(source);
          cell nsink = copy_cell(points_to_sink(ipt));
          approximation na = copy_approximation(a);
          points_to npt = make_points_to(nsource, nsink, na,
                                         make_descriptor_none());
          //add_arc_to_simple_pt_map(npt, in);
          to_be_added = CONS(POINTS_TO, npt, to_be_added);
          to_be_removed = CONS(POINTS_TO, ipt, to_be_removed);
        }
        else {
          ; // do nothing
        }
      }
      else {
        to_be_removed = CONS(POINTS_TO, ipt, to_be_removed);
      }
    }
  }
 
  FOREACH(POINTS_TO, pt, to_be_removed)
    remove_arc_from_simple_pt_map(pt, in);
 
  FOREACH(POINTS_TO, pt, to_be_added)
    add_arc_to_simple_pt_map(pt, in);
 
  return out_filtered;
}

References add_arc_to_simple_pt_map, any_function_to_return_value(), approximation_exact_p, approximation_undefined, cell_any_reference(), CONS, copy_approximation(), copy_cell(), f(), FOREACH, make_descriptor_none(), make_points_to(), new_simple_pt_map, NIL, nowhere_cell_p(), out, POINTS_TO, points_to_approximation, points_to_cell_in_list_p(), points_to_sink, points_to_source, reference_variable, remove_arc_from_simple_pt_map, SET_FOREACH, and similar_arc_in_points_to_set_p().

Referenced by user_call_to_points_to_interprocedural().

Here is the call graph for this function:

Here is the caller graph for this function:

generic_points_to_cells_translation()

list generic_points_to_cells_translation	(	list	cl,
		set	binding,
		entity	f,
		bool	exact_p
	)

Allocate a new list with the translations of the cells in cl, when their translation make sense.

Effects on copied parameters are discarded.

If exact_p is required, translate only cells that can be translated exactly.

Parameters

cl	l
binding	inding
exact_p	xact_p

Definition at line 2286 of file interprocedural.c.

{
  list tcl = NIL;
  FOREACH(CELL, c, cl) {
    reference r = cell_any_reference(c);
    entity v = reference_variable(r);
    list ptcl = NIL;
    if(formal_parameter_p(v)) {
      type t = entity_basic_concrete_type(v);
      if(array_type_p(t)) {
        // Passing by reference
        ptcl = points_to_cell_translation(c, binding, f);
      }
      else {
        // Passing by value: no need to translate information about a copy
        ;
      }
    }
    else
      ptcl = points_to_cell_translation(c, binding, f);
    if(exact_p && gen_length(ptcl)>1)
      gen_free_list(ptcl);
    else
      tcl = gen_nconc(tcl, ptcl);
  }
  return tcl;
}

References array_type_p(), CELL, cell_any_reference(), entity_basic_concrete_type(), f(), FOREACH, formal_parameter_p(), gen_free_list(), gen_length(), gen_nconc(), NIL, points_to_cell_translation(), and reference_variable.

Referenced by points_to_cells_exact_translation(), and points_to_cells_translation().

Here is the call graph for this function:

Here is the caller graph for this function:

generic_points_to_set_to_stub_cell_list()

list generic_points_to_set_to_stub_cell_list	(	entity	f,
		set	s,
		list	osl
	)

Add cells referencing a points-to stub found in parameter "s" are copied and added to list "osl".

The stubs are returned as cells not as entities.

New cells are allocated. No sharing is created between parameter "s" and result "sl".

Parameters

osl

sl

Definition at line 2829 of file interprocedural.c.

{
  list sl = osl;
  SET_FOREACH(points_to, pt, s) {
    cell sink = points_to_sink(pt);
    reference r1 = cell_any_reference(sink);
    entity e1 = reference_variable(r1);
    if( ( (entity_undefined_p(f) && entity_stub_sink_p(e1))
          || stub_entity_of_module_p(e1, f) )
        && !points_to_cell_in_list_p(sink, sl) )
      sl = CONS(CELL, copy_cell(sink), sl);
      
    cell source = points_to_source(pt);
    reference r2 = cell_any_reference(source);
    entity e2 = reference_variable(r2);
    if( ( (entity_undefined_p(f) && entity_stub_sink_p(e2))
          || stub_entity_of_module_p(e2, f) )
        && !points_to_cell_in_list_p(source, sl) )
      sl = CONS(CELL, copy_cell(source), sl);
  }
  
  gen_sort_list(sl, (gen_cmp_func_t) points_to_compare_ptr_cell );
  ifdebug(1) print_points_to_cells(sl);
  return sl;
}

References CELL, cell_any_reference(), CONS, copy_cell(), entity_stub_sink_p(), entity_undefined_p, f(), gen_sort_list(), ifdebug, points_to_cell_in_list_p(), points_to_compare_ptr_cell(), points_to_sink, points_to_source, print_points_to_cells, reference_variable, SET_FOREACH, and stub_entity_of_module_p().

Referenced by points_to_set_to_module_stub_cell_list(), and points_to_set_to_stub_cell_list().

Here is the call graph for this function:

Here is the caller graph for this function:

generic_written_pointers_set()

static list generic_written_pointers_set ( list  eff, bool  exact_p  )

static

Filter out written effects on pointers.

Definition at line 2590 of file interprocedural.c.

{
  list written_l = NIL;
  debug_on("EFFECTS_DEBUG_LEVEL");
  list wr_eff = effects_write_effects(eff);
  FOREACH(effect, ef, wr_eff) {
    approximation a = effect_approximation(ef);
    if(!exact_p || approximation_must_p(a) || approximation_exact_p(a)) {
      if(effect_pointer_type_p(ef)){
        cell c = effect_cell(ef);
        written_l = gen_nconc(CONS(CELL, c, NIL), written_l);
      }
    }
  }
  debug_off();
  return written_l; 
}

References approximation_exact_p, approximation_must_p, CELL, CONS, debug_off, debug_on, effect_approximation, effect_cell, effect_pointer_type_p(), effects_write_effects(), FOREACH, gen_nconc(), and NIL.

Referenced by certainly_written_pointers_set(), and written_pointers_set().

Here is the call graph for this function:

Here is the caller graph for this function:

lower_points_to_approximations_according_to_write_effects()

static set lower_points_to_approximations_according_to_write_effects ( set  pt_end, list  wpl  )

static

It is partly a kill and partly a gen operation.

FI: the very same function must exist for pointer assignments I guess

Definition at line 1804 of file interprocedural.c.

{
  list optl = NIL, nptl = NIL;
  SET_FOREACH(points_to, pt, pt_end) {
    cell source = points_to_source(pt);
    // FI->FI: en fait, il faudrait prendre en compte le treillis et
    // tester les conflits,
    // written_effects_conflict_with_points_to_cell()
    if(points_to_cell_in_list_p(source, wpl)) {
      optl = CONS(POINTS_TO, pt, optl);
      cell sink = points_to_sink(pt);
      points_to npt = make_points_to(copy_cell(source),
                                     copy_cell(sink),
                                     make_approximation_may(),
                                     make_descriptor_none());
      nptl = CONS(POINTS_TO, npt, nptl);
    }
  }
  FOREACH(POINTS_TO, opt, optl)
    remove_arc_from_simple_pt_map(opt, pt_end);
  FOREACH(POINTS_TO, npt, nptl)
    add_arc_to_simple_pt_map(npt, pt_end);
  return pt_end;
}

References add_arc_to_simple_pt_map, CONS, copy_cell(), FOREACH, make_approximation_may(), make_descriptor_none(), make_points_to(), NIL, POINTS_TO, points_to_cell_in_list_p(), points_to_sink, points_to_source, remove_arc_from_simple_pt_map, and SET_FOREACH.

Referenced by user_call_to_points_to_interprocedural().

Here is the call graph for this function:

Here is the caller graph for this function:

merge_actual_and_formal_sinks()

static bool merge_actual_and_formal_sinks ( cell  fc, list *  pfcl, cell  ac, list *  pacl, set  pt_in, set  pt_binded, set  filtered  )

static

Handle constant cells such as NULL and UNDEFINED (nowhere) in "fcl" and "acl".

Update "fcl" is needed, as well as "pt_binded" and "filtered", a subset of "pt_in".

A points-to arc should be removed from pt_binded and/or added to a pt_kill set...

Definition at line 809 of file interprocedural.c.

{
  bool ok_p = true;
 
  list acl = *pacl;
  int nacl = 0;
  bool a_null_p = false;
  bool a_nowhere_p = false;
 
  list fcl = *pfcl;
  bool f_null_p = false;
  int nfcl = 0;
 
  FOREACH(CELL, ac, acl) {
    nacl++;
    if(null_cell_p(fc))
      a_null_p = true;
    else if(nowhere_cell_p(fc))
      a_nowhere_p = true;
  }
 
  cell null_c = cell_undefined;
  FOREACH(CELL, fc, fcl) {
    nfcl++;
    if(null_cell_p(fc)) {
      f_null_p = true;
      if(!a_null_p)
        null_c = fc;
    }
  }
 
  if(nfcl>0 && nacl==1 && a_nowhere_p) {
    // The callee dereferences an undefined pointer
    ok_p = false;
  }
  else if(nfcl>0 && a_nowhere_p) {
    /* A points-to arc should be removed from pt_binded and/or added
     * to a pt_kill set...
     */
    SET_FOREACH(points_to, pt, pt_binded) {
      cell s = points_to_source(pt);
      if(s==ac) {
        pt_binded = remove_arc_from_simple_pt_map(pt, pt_binded);
      }
    }
  }
 
  // A points-to arc should not be copied from "pt_in" into "filtered"
  bool no_null_p = f_null_p && !a_null_p;
 
  SET_FOREACH(points_to, pt, pt_in) {
    cell s = points_to_source(pt);
    if(s==fc) {
      cell d = points_to_sink(pt);
      if(!no_null_p || !null_cell_p(d)) {
        points_to npt = copy_points_to(pt);
        add_arc_to_simple_pt_map(npt, filtered);
      }
    }
  }
 
  if(no_null_p) {
    // Remove the NULL cell from "fcl" list
    // fcl = fcl - null_c
    gen_remove(pfcl, (void *) null_c);
  }
 
  return ok_p;
}

References add_arc_to_simple_pt_map, CELL, cell_undefined, copy_points_to(), FOREACH, gen_remove(), nowhere_cell_p(), null_cell_p(), points_to_sink, points_to_source, remove_arc_from_simple_pt_map, and SET_FOREACH.

Referenced by new_recursive_filter_formal_context_according_to_actual_context_for_pointer_pair().

Here is the call graph for this function:

Here is the caller graph for this function:

new_filter_formal_context_according_to_actual_context()

set new_filter_formal_context_according_to_actual_context	(	list	fpcl,
		set	pt_in,
		set	pt_binded,
		set	binding
	)

Copy arcs "pt" from "pt_in" into the "filtered" set if they are compatible with "pt_binded". The set "filtered" is a subset of "pt_in".

Do we have the same arc in pt_binded?

We have to deal recursively with stubs of the formal context and first with the global variables... although they, or their stubs, do not require any translation? Why is the points-to information about q lost in the translation of the call site to call03 in main (PointersWithEffects/call03.c)

FI: I do not understand why I have to do this for EffectsWithPointsTo/pointer_modif04.c. Because the arc "pt" in "pt_in" is more precise than the information available in "pt_caller". For instance, "pt_in" may contain "stderr->_stderr_0[0], Exact", while "pt_caller" may contain "stderr->_stderr_0[0], May", "stderr->NULL, May". Basically, we have not thought about the kill set generated for the global variables.

Useless when called from effects... In fact, it should never be called from effects...

FI: we do not know what we really do here... An arc is not taken into account, but it might be taken into account recursively below.

Compute the binding relation for sinks of the formal arguments and global variables

We have to handle constant strings such as "Hello!" and not to forget functional parameters.

Some arcs have been removed, so other arcs may be promoted from "may" to "exact".

Parameters

fpcl	pcl
pt_in	t_in
pt_binded	t_binded
binding	inding

Definition at line 1039 of file interprocedural.c.

{
  bool ok_p = true;
  set filtered = new_simple_pt_map();
 
  /* Copy arcs "pt" from "pt_in" into the "filtered" set if they are
     compatible with "pt_binded". The set "filtered" is a subset of
     "pt_in". */
  SET_FOREACH(points_to, pt, pt_in) {
    cell source = points_to_source(pt);
    if(related_points_to_cell_in_list_p(source, fpcl)) {
      cell sink = points_to_sink(pt);
      if(null_cell_p(sink)) {
        /* Do we have the same arc in pt_binded? */
        if(arc_in_points_to_set_p(pt, pt_binded)) {
          points_to npt = copy_points_to(pt);
          add_arc_to_simple_pt_map(npt, filtered);
        }
        else {
          ; // do not copy this arc in filtered set
        }
      }
      else {
        if(cell_points_to_non_null_sink_in_set_p(source, pt_binded)) {
          points_to npt = copy_points_to(pt);
          add_arc_to_simple_pt_map(npt, filtered);
        }
        else {
          ; // do not copy this arc in filtered set
        }
      }
    }
    else {
      /* We have to deal recursively with stubs of the formal context
         and first with the global variables... although they, or their
         stubs, do not require any translation? Why is the points-to
         information about q lost in the translation of the call site
         to call03 in main (PointersWithEffects/call03.c) */
      reference r = cell_any_reference(source);
      entity v = reference_variable(r);
      if(!arc_in_points_to_set_p(pt, pt_binded)) {
        // FI: necessary for Pointers/global10
        if(static_global_variable_p(v) || global_variable_p(v)) {
          //gvcl = CONS(CELL, source, gvcl);
          points_to npt = copy_points_to(pt);
          add_arc_to_simple_pt_map(npt, filtered);
          /* FI: I do not understand why I have to do this for
             EffectsWithPointsTo/pointer_modif04.c. Because the arc "pt"
             in "pt_in" is more precise than the information available
             in "pt_caller". For instance, "pt_in" may contain
             "stderr->_stderr_0[0], Exact", while "pt_caller" may
             contain "stderr->_stderr_0[0], May", "stderr->NULL,
             May". Basically, we have not thought about the kill set
             generated for the global variables. */
          if(statement_points_to_context_defined_p()) {
            /* Useless when called from effects... In fact, it should
               never be called from effects... */
            //add_arc_to_points_to_context(npt);
            update_points_to_context_with_arc(npt);
          }
          else {
            // pips_internal_error("This function should not reach this point"
            //                  " when called from effects, simple or generic.");
            // update_points_to_context_with_arc(npt);
            ; // Do nothing
          }
        }
        else {
          /* FI: we do not know what we really do here... An arc is not
             taken into account, but it might be taken into account
             recursively below. */
          ;
        }
      }
    }
  }
 
  /* Compute the binding relation for sinks of the formal arguments
     and global variables */
  points_to_graph filtered_g = make_points_to_graph(false, filtered);
  points_to_graph pt_binded_g = make_points_to_graph(false, pt_binded);
  FOREACH(CELL, c, fpcl) {
    list fl = points_to_source_to_any_sinks(c, filtered_g, false); // formal list
    list al = points_to_source_to_any_sinks(c, pt_binded_g, false); // actual list
    int nfl = (int) gen_length(fl);
    int nal = (int) gen_length(al);
    approximation approx = approximation_undefined;
 
    // FI: que fait-on avec nfl==0, comme dans
    // Pointers/StrictTyping.sub/struct08.c ou nfl vaut 0 parce que le
    // parametre effectif est undefined?
 
    if(nfl==1 && nal==1)
      approx = make_approximation_exact();
    else
      approx = make_approximation_may();
    FOREACH(CELL, fc, fl) {
      if(!null_cell_p(fc)) {
        FOREACH(CELL, ac, al) {
          if(!null_cell_p(ac) && !nowhere_cell_p(ac)) {
            type fc_t = points_to_cell_to_concrete_type(fc);
            type iac_t = points_to_cell_to_concrete_type(ac);
            type ac_t = constant_string_type_to_string_type(iac_t);
            /* We have to handle constant strings such as "Hello!"
               and not to forget functional parameters. */
            if(type_functional_p(ac_t)) {
              reference ar = cell_any_reference(ac);
              entity a = reference_variable(ar);
              if(constant_string_entity_p(a)) {
                ac_t = functional_result(type_functional(iac_t));
              }
            }
            // FI: which type equality should be chosen ?
            // if(!type_structurally_equal_p(fc_t, ac_t)
            if(!array_pointer_string_type_equal_p(fc_t, ac_t)
               && !overloaded_type_p(ac_t)) {
              if(array_type_p(ac_t)) {
                points_to_cell_add_zero_subscript(ac);
                type ac_nt = points_to_cell_to_concrete_type(ac);
                if(!type_structurally_equal_p(fc_t, ac_nt) && !overloaded_type_p(ac_nt)) {
                  // Pointers/pointer14.c
                  // FI: I am not sure it is the best translation
                  // It might be better to remove some zero subscripts from fc
                  points_to_cell_complete_with_zero_subscripts(ac);
                  type ac_nnt = points_to_cell_to_concrete_type(ac);
                  if(!type_structurally_equal_p(fc_t, ac_nnt) && !overloaded_type_p(ac_nnt))
                    pips_internal_error("translation failure for an array.\n");
                }
              }
              else {
                reference fr = cell_any_reference(fc);
                if(adapt_reference_to_type(fr, ac_t, points_to_context_statement_line_number))
                  ;
                else {
                  type fr_t = points_to_reference_to_concrete_type(fr);
                  reference ar = cell_any_reference(ac);
                  semantics_user_warning("Type \"%s\" for formal reference \"%s\" is incompatible with type \"%s\" for actual reference \"%s\".\n",
                                         type_to_full_string_definition(fr_t),
                                         reference_to_string(fr),
                                         type_to_full_string_definition(ac_t),
                                         reference_to_string(ar));
                  if(get_bool_property("POINTS_TO_STRICT_POINTER_TYPES")) {
                    pips_user_error
                      ("Translation failure for actual parameter \"%s\" at line %d.\n"
                       "Maybe property POINTS_TO_STRICT_POINTER_TYPES should be reset.\n",
                       reference_to_string(ar),
                       points_to_context_statement_line_number());
                    // pips_internal_error("translation failure.\n");
                  }
                  else {
                  pips_user_error
                    ("Translation failure for actual parameter \"%s\" at line %d.\n",
                     reference_to_string(ar),
                     points_to_context_statement_line_number());
                  }
                }
              }
            }
            points_to tr = make_points_to(copy_cell(fc), 
                                          copy_cell(ac), 
                                          copy_approximation(approx),
                                          make_descriptor_none());
            add_subscript_dependent_arc_to_simple_pt_map(tr, binding);
            ok_p = new_recursive_filter_formal_context_according_to_actual_context
              (fc, ac, approx, pt_in, pt_binded, binding, filtered);
          }
          else if(null_cell_p(ac)) {
            ; // What should be done?
          }
          else {
            // nowhere_cell_p(ac)
            ; // What should be done?
          }
        }
      }
    }
 
    free_approximation(approx);
  }
 
  ifdebug(8) {
    pips_debug(8, "First filtered IN set for callee at call site:\n");
    print_points_to_set("", filtered);
    pips_debug(8, "First translation mapping for call site:\n");
    print_points_to_set("", binding);
  }
 
  pips_assert("The points-to translation mapping is well typed",
              points_to_translation_mapping_is_typed_p(binding));
 
  if(ok_p) {
  /* Some arcs have been removed, so other arcs may be promoted from
     "may" to "exact". */
    upgrade_approximations_in_points_to_set(filtered_g);
  }
  else {
    set_free(filtered);
    filtered = set_undefined;
  }
 
  ifdebug(8) {
    pips_debug(8, "Final filtered IN set for callee at call site:\n");
    print_points_to_set("", filtered);
    pips_debug(8, "Final mapping for call site:\n");
    print_points_to_set("", binding);
  }
    
  return filtered;
}

References adapt_reference_to_type(), add_arc_to_simple_pt_map, add_subscript_dependent_arc_to_simple_pt_map(), approximation_undefined, arc_in_points_to_set_p(), array_pointer_string_type_equal_p(), array_type_p(), CELL, cell_any_reference(), cell_points_to_non_null_sink_in_set_p(), constant_string_entity_p(), constant_string_type_to_string_type(), copy_approximation(), copy_cell(), copy_points_to(), FOREACH, free_approximation(), functional_result, gen_length(), get_bool_property(), global_variable_p(), ifdebug, int, make_approximation_exact(), make_approximation_may(), make_descriptor_none(), make_points_to(), make_points_to_graph(), new_recursive_filter_formal_context_according_to_actual_context(), new_simple_pt_map, nowhere_cell_p(), null_cell_p(), overloaded_type_p(), pips_assert, pips_debug, pips_internal_error, pips_user_error, points_to_cell_add_zero_subscript(), points_to_cell_complete_with_zero_subscripts(), points_to_cell_to_concrete_type(), points_to_context_statement_line_number(), points_to_reference_to_concrete_type(), points_to_sink, points_to_source, points_to_source_to_any_sinks(), points_to_translation_mapping_is_typed_p(), print_points_to_set(), reference_to_string(), reference_variable, related_points_to_cell_in_list_p(), semantics_user_warning, SET_FOREACH, set_free(), set_undefined, statement_points_to_context_defined_p(), static_global_variable_p(), type_functional, type_functional_p, type_structurally_equal_p(), type_to_full_string_definition(), update_points_to_context_with_arc(), and upgrade_approximations_in_points_to_set().

Referenced by user_call_to_points_to_interprocedural(), and user_call_to_points_to_interprocedural_binding_set().

Here is the call graph for this function:

Here is the caller graph for this function:

new_recursive_filter_formal_context_according_to_actual_context()

static bool new_recursive_filter_formal_context_according_to_actual_context ( cell  fc, cell  ac, approximation  ap, set  pt_in, set  pt_binded, set  binding, set  filtered  )

static

The code is derived from generic_points_to_cell_to_useful_pointer_cell() with no filtering and a direct processing of the pairs of pointers obtained.

cells fc and ac are assumed type compatible.

Look for pointer and struct and array of pointers or struct fields

transformer

Definition at line 971 of file interprocedural.c.

{
  bool ok_p = true;
  type fc_t = points_to_cell_to_concrete_type(fc);
  type ac_t = points_to_cell_to_concrete_type(ac);
  if(null_cell_p(ac)) {
    pips_internal_error("Cannot be called with a null cell.\n");
  }
  // array_pointer_string_type_equal_p() ?
  else if(!type_equal_p(fc_t, ac_t)
          && !char_star_constant_function_type_p(ac_t))
    if(overloaded_type_p(ac_t)) {
      // Something has failed and probably led to an anywhere astract location
      ;
    }
    else {
      pips_internal_error("Incompatible types for binded cells.\n");
    }
  else if(pointer_type_p(fc_t)) {
    ok_p = new_recursive_filter_formal_context_according_to_actual_context_for_pointer_pair
      (fc, ac, ap, pt_in, pt_binded, binding, filtered);
  }
  else if(struct_type_p(fc_t)) {
    /* Look for pointer and struct and array of pointers or struct fields */
    list fl = struct_type_to_fields(fc_t);
    FOREACH(ENTITY, f, fl) {
      type f_t = entity_basic_concrete_type(f);
      if(pointer_type_p(f_t) || struct_type_p(f_t)
         || array_of_pointers_type_p(f_t)
         || array_of_struct_type_p(f_t)) {
        cell nfc = copy_cell(fc);
        points_to_cell_add_field_dimension(nfc, f);
        cell nac = copy_cell(ac);
        points_to_cell_add_field_dimension(nac, f);
        if(pointer_type_p(f_t)) {
          approximation nap = copy_approximation(ap);
          descriptor d = make_descriptor_none();
          points_to npt = make_points_to(nfc, nac, nap, d);
          add_arc_to_simple_pt_map(npt, binding);
          ok_p = new_recursive_filter_formal_context_according_to_actual_context_for_pointer_pair
            (nfc, nac, nap, pt_in, pt_binded, binding, filtered);
        }
        else {
          ok_p = new_recursive_filter_formal_context_according_to_actual_context
            (nfc, nac, ap, pt_in, pt_binded, binding, filtered);
        }
      }
    }
  }
  else if(array_of_pointers_type_p(fc_t) || array_of_struct_type_p(fc_t)) {
    /* transformer */
    cell nfc = copy_cell(fc);
    points_to_cell_add_unbounded_subscripts(nfc);
    cell nac = copy_cell(ac);
    points_to_cell_add_unbounded_subscripts(nac);
    if(array_of_pointers_type_p(fc_t)) {
      ok_p = new_recursive_filter_formal_context_according_to_actual_context_for_pointer_pair
        (nfc, nac, ap, pt_in, pt_binded, binding, filtered);
    }
    else {
      ok_p = new_recursive_filter_formal_context_according_to_actual_context
        (nfc, nac, ap, pt_in, pt_binded, binding, filtered);
    }
  }
  return ok_p;
}

References add_arc_to_simple_pt_map, array_of_pointers_type_p(), array_of_struct_type_p(), char_star_constant_function_type_p(), copy_approximation(), copy_cell(), ENTITY, entity_basic_concrete_type(), f(), FOREACH, make_descriptor_none(), make_points_to(), new_recursive_filter_formal_context_according_to_actual_context_for_pointer_pair(), null_cell_p(), overloaded_type_p(), pips_internal_error, pointer_type_p(), points_to_cell_add_field_dimension(), points_to_cell_add_unbounded_subscripts(), points_to_cell_to_concrete_type(), struct_type_p(), struct_type_to_fields(), and type_equal_p().

Referenced by new_filter_formal_context_according_to_actual_context(), and new_recursive_filter_formal_context_according_to_actual_context_for_pointer_pair().

Here is the call graph for this function:

Here is the caller graph for this function:

new_recursive_filter_formal_context_according_to_actual_context_for_pointer_pair()

static bool new_recursive_filter_formal_context_according_to_actual_context_for_pointer_pair ( cell  fc, cell  ac, approximation  ap, set  pt_in, set  pt_binded, set  binding, set  filtered  )

static

fc and ac are two pointer cells with same or compatible pointer type

Update binding and filtered according to their sinks.

For instance, if "ac" only points to the undefined cells, the call site is not consistent because "fc" is assumed by the caller to point to a defined cell. "ok_p" is set to false.

if "fc" points to NULL in pt_in, but "ac" does not point to NULL, the corresponding arc is not copied in "filtered".

if "fc" points to "nfc" in "pt_in" and "ac" points to "nac" in "pt_binded", then arc "fc->nfc" is copied in "pt_binded" and arc "nfc->nac" is added in "binding".

No optimization in number of scans for the different sets

pointer fc is not dereferenced, no need to go down

FI: the algorithm seems wrong because a dynamic allocation can occur in the callee and be unknown from pt_binded. See Ancourt3009.sub/call09 and call10. I do not understand why call10 provides a result... and call09 fails utterly.

The caller may not have had yet a need for the corresponding stub

Definition at line 896 of file interprocedural.c.

{
  bool ok_p = true;
  points_to_graph pt_in_g = make_points_to_graph(false, pt_in);
  list fcl = points_to_source_to_some_sinks(fc, pt_in_g, false);
  if(ENDP(fcl)) {
    /* pointer fc is not dereferenced, no need to go down */
    ;
  }
  else {
    /* FI: the algorithm seems wrong because a dynamic allocation can
       occur in the callee and be unknown from pt_binded. See
       Ancourt3009.sub/call09 and call10. I do not understand why
       call10 provides a result... and call09 fails utterly. */
    points_to_graph pt_binded_g = make_points_to_graph(false, pt_binded);
    list acl = points_to_source_to_some_sinks(ac, pt_binded_g, false);
    if(ENDP(acl)) {
      /* The caller may not have had yet a need for the corresponding stub */
      points_to npt = create_stub_points_to(ac, type_undefined, true);
      cell d = points_to_sink(npt);
      acl = CONS(CELL, d, NIL);
      // add_arc_to_simple_pt_map(npt, pt_binded); // FI: not sure it is useful
 
      // Add arc to the points-to in set of the caller and of the
      // current statement
      update_points_to_context_with_arc(npt);
    }
    ok_p = merge_actual_and_formal_sinks(fc, &fcl, ac, &acl, pt_in, pt_binded, filtered);
    if(ok_p) {
      // Update binding
      int nfcl = gen_length(fcl);
      int nacl = gen_length(acl);
      FOREACH(CELL, dfc, fcl) { // destination cells
        FOREACH(CELL, dac, acl) { // destination cells
          if(nowhere_cell_p(dac)) {
            if(nacl==1) {
              semantics_user_warning("An undefined pointer \"%s\" (formal: \"%s\") has been dereferenced to reach \"%s\".\n", points_to_cell_to_string(ac), points_to_cell_to_string(fc), points_to_cell_to_string(dfc));
              ok_p = false;
              // FI: the choice is to let the analysis proceeds
              // although a user error has been detected; it may occur
              // in dead code... The opposite choice has been made in
              // effects analyses
            }
            else {
              semantics_user_warning("An undefined pointer \"%s\" (formal: \"%s\") may be dereferenced to reach \"%s\".\n", points_to_cell_to_string(ac), points_to_cell_to_string(fc), points_to_cell_to_string(dfc));
            }
          }
          else {
          cell nfc = copy_cell(dfc);
          cell nac = copy_cell(dac);
          approximation nap = (nfcl==1 && nacl==1 && approximation_exact_p(ap)) ?
            make_approximation_exact() :
            make_approximation_may();
          descriptor d = make_descriptor_none();
          points_to npt = make_points_to(nfc, nac, nap, d);
          add_arc_to_simple_pt_map(npt, binding);
          ok_p = new_recursive_filter_formal_context_according_to_actual_context(nfc, nac, nap, pt_in, pt_binded, binding, filtered);
          }
        }
      }
    }
    // Free pt_binded_g but not pt_binded
  }
  // Free pt_in_g but not pt_in
 
  return ok_p;
}

References add_arc_to_simple_pt_map, approximation_exact_p, CELL, CONS, copy_cell(), create_stub_points_to(), ENDP, FOREACH, gen_length(), make_approximation_exact(), make_approximation_may(), make_descriptor_none(), make_points_to(), make_points_to_graph(), merge_actual_and_formal_sinks(), new_recursive_filter_formal_context_according_to_actual_context(), NIL, nowhere_cell_p(), points_to_cell_to_string(), points_to_sink, points_to_source_to_some_sinks(), semantics_user_warning, type_undefined, and update_points_to_context_with_arc().

Referenced by new_recursive_filter_formal_context_according_to_actual_context().

Here is the call graph for this function:

Here is the caller graph for this function:

points_to_binding()

set points_to_binding	(	list	args,
		set	in,
		set	pt_binded
	)

Apply points_to_binding_arguments() to each pair (, complete the process of binding each element of "in" to its corresponding memory address at the call site.

Necessary to translate the fields of structures.

"args": list of formal parameters of some callee

"in": points-to in of the callee

"pt_binded": points-to from formal to actual parameters for a specific call site

A new set is allocated.

Process each formal parameter and look for its actual values in "pt_binded"

Parameters

args	rgs
in	n
pt_binded	t_binded

Definition at line 2780 of file interprocedural.c.

{
 
  set bm = new_simple_pt_map();
  //set bm1 = new_simple_pt_map();
 
  /* Process each formal parameter and look for its actual values in
     "pt_binded" */
  SET_FOREACH(points_to, pt, pt_binded) {
    FOREACH(CELL, c1, args) {
      cell source = points_to_source(pt);
      if(cell_equal_p(c1, source)) {
        cell c2 = points_to_source_alias(pt, pt_binded);
        // FI: We end up with c1=c2=one formal parameter...
        // No need to add "p->p" in "bm"...
        //approximation a = make_approximation_exact();
        //points_to new_pt = make_points_to(c1, c2, a, make_descriptor_none());
        //add_arc_to_simple_pt_map(new_pt, bm);
        set c1c2 = points_to_binding_arguments(c1, c2,  in, pt_binded);
        bm = set_union(bm, bm, c1c2);
        set_clear(c1c2), set_free(c1c2);
      }
      else if(cell_entity_equal_p(c1, source)) {
        pips_assert("c1 is a reference with no indices",
                    ENDP(reference_indices(cell_any_reference(c1))));
        cell c2 = copy_cell(source);
        // FI: We end up with c1=c2=one formal parameter...
        // No need to add "p->p" in "bm"...
        //approximation a = make_approximation_exact();
        //points_to new_pt = make_points_to(c1, c2, a, make_descriptor_none());
        //add_arc_to_simple_pt_map(new_pt, bm);
        set c1c2 = points_to_binding_arguments(source, c2,  in, pt_binded);
        bm = set_union(bm, bm, c1c2);
        set_clear(c1c2), set_free(c1c2);
      }
    }
  }
 
  return bm;
}

References CELL, cell_any_reference(), cell_entity_equal_p(), cell_equal_p(), copy_cell(), ENDP, FOREACH, new_simple_pt_map, pips_assert, points_to_binding_arguments(), points_to_source, points_to_source_alias(), reference_indices, set_clear(), SET_FOREACH, set_free(), and set_union().

Referenced by user_call_to_points_to_fast_interprocedural().

Here is the call graph for this function:

Here is the caller graph for this function:

points_to_binding_arguments()

set points_to_binding_arguments	(	cell	c1,
		cell	c2,
		set	in,
		set	pt_binded
	)

Recursively find all the arcs, "ai", starting from the argument "c1" using "in", find all the arcs, "aj", starting from the parameter "c2" using "pt_binded", map each node "ai" to its corresponding "aj" and store the "ai->aj" arc in a new set, "bm".

"pt_binded" contains the correspondance between formal and actual parameters, e.g. "fp->ap", with some information about the possible approximations because one formal parameter can points toward several actual memory locations of the caller.

"in" contains the formal context of the callee, as it stands at its entry point (DBR_POINTS_TO_IN).

"bm" is the binding relationship between references of the formal context of the callees towards addresses of the caller. For instance, when function "void foo(int ** fp)" is called as "ap=&q; foo(ap);", bm = {(_ap_1, q)}.

See Amira Mensi's PhD dissertation, chapter about interprocedural analysis

Recursive call down the different points_to paths

Here we have, for instance, "q[*]" in "c1" for "q[4]" in "in".

FI: I do not see how to handle incompatibility between assumptions...

(!source_in_set_p(c1, in) && !source_subset_in_set_p(c1, in))

c1 is not a pointer: it is simply mapped to c2

Parameters

c1	1
c2	2
in	n
pt_binded	t_binded

Definition at line 2513 of file interprocedural.c.

{
  set bm = new_simple_pt_map();
 
  if(source_in_set_p(c1, in) || source_subset_in_set_p(c1, in)) {
    // FI: impedance problem... and memory leak
    points_to_graph in_g = make_points_to_graph(false, in);
    points_to_graph pt_binded_g = make_points_to_graph(false, pt_binded);
    // FI: allocate a new copy for sink1 and sink2
    //list c1_children = cell_to_pointer_cells(c1);
    //list c2_children = cell_to_pointer_cells(c2);
    list c1_children = recursive_cell_to_pointer_cells(c1);
    list c2_children = recursive_cell_to_pointer_cells(c2);
    FOREACH(CELL,c1c, c1_children) {
      FOREACH(CELL,c2c, c2_children) {
        list sinks1 = points_to_source_to_some_sinks(c1c, in_g, true);
        list sinks2 = points_to_source_to_some_sinks(c2c, pt_binded_g, true);
        pips_assert("sinks1 is not empty", !ENDP(sinks1));
        pips_assert("sinks2 is not empty", !ENDP(sinks2));
        // FI Allocate more copies
        list tmp1 = gen_full_copy_list(sinks1);
        list tmp2 = gen_full_copy_list(sinks2);
 
        FOREACH(CELL, s1, sinks1) { // Formal cell: fp->_fp_1 or fp->NULL
          // FI: no need to translate constants NULL and UNDEFINED
          if(!null_cell_p(s1) && !nowhere_cell_p(s1)) {
            FOREACH(CELL, s2, sinks2) { // Actual cell: ap-> i... NOWHERE... NULL...
              // FI: _fp_1 may or not exist since it is neither null nor undefined
              if(!null_cell_p(s2) && !nowhere_cell_p(s2)) {
                approximation a = approximation_undefined;
                if((size_t)gen_length(sinks2)>1) // FI->FI: atomicity should be tested too
                  a = make_approximation_may();
                else
                  a = make_approximation_exact();
                cell sink1 = copy_cell(s1);
                cell sink2 = copy_cell(s2);
                // Build arc _fp_1->... NOWHERE ... NULL ...
                points_to pt = make_points_to(sink1, sink2, a, make_descriptor_none());
                add_arc_to_simple_pt_map(pt, bm);
              }
              //gen_remove(&sinks2, (void*)s2);
            }
          }
          //gen_remove(&sinks1, (void*)s1);
        }
 
        /* Recursive call down the different points_to paths*/
        FOREACH(CELL, sr1, tmp1) {
          if(!null_cell_p(sr1) && !nowhere_cell_p(sr1)) {
            FOREACH(CELL, sr2, tmp2) {
              if(!null_cell_p(sr2) && !nowhere_cell_p(sr2)) {
                set sr1sr2 = points_to_binding_arguments(sr1, sr2, in, pt_binded);
                bm = set_union(bm, sr1sr2, bm);
                set_clear(sr1sr2), set_free(sr1sr2);
              }
            }
          }
        }
      }
    }
  }
  else if(source_subset_in_set_p(c1, in)) { // Not reachable
    /* Here we have, for instance, "q[*]" in "c1" for "q[4]" in "in". */
    /* FI: I do not see how to handle incompatibility between assumptions... */
    pips_internal_error("Do not know how to handle subsets...\n");
  }
  else /* (!source_in_set_p(c1, in) && !source_subset_in_set_p(c1, in)) */ {
    // FI: this has already been performed
    /* c1 is not a pointer: it is simply mapped to c2 */
    // points_to pt = make_points_to(c1, c2, make_approximation_exact(), make_descriptor_none());
    // add_arc_to_simple_pt_map(pt, bm);
    ;
  }
  return bm;
}

References add_arc_to_simple_pt_map, approximation_undefined, CELL, copy_cell(), ENDP, FOREACH, gen_full_copy_list(), gen_length(), make_approximation_exact(), make_approximation_may(), make_descriptor_none(), make_points_to(), make_points_to_graph(), new_simple_pt_map, nowhere_cell_p(), null_cell_p(), pips_assert, pips_internal_error, points_to_source_to_some_sinks(), recursive_cell_to_pointer_cells(), s1, set_clear(), set_free(), set_union(), source_in_set_p(), and source_subset_in_set_p().

Referenced by points_to_binding().

Here is the call graph for this function:

Here is the caller graph for this function:

points_to_cell_translation()

list points_to_cell_translation	(	cell	sr1,
		set	binding,
		entity	f
	)

Compute the list of cells that correspond to cell "sr1" according to the translation mapping "bm" when function "f" is called.

The check with rv may be useless, for instance when a sink cell is checked, as it is impossible (in C at least) to points toward the return value.

Translate sr1 if needed

No translation is needed.

We assume here that the subscript list of sr1, the reference to translate, is longer than the subscript list of sr2, the source of its translation.

Parameters

sr1	r1
binding	inding

Definition at line 2211 of file interprocedural.c.

{
  list new_sr_l = NIL;
  entity rv = any_function_to_return_value(f);
 
  /* Translate sr1 if needed */
  reference r_1 = cell_any_reference(sr1);
  entity v_1 = reference_variable(r_1);
  if(entity_anywhere_locations_p(v_1)
     || entity_typed_anywhere_locations_p(v_1)
     || heap_cell_p(sr1)
     || v_1 == rv
     || entity_to_module_entity(v_1)!=f) {
    /* No translation is needed. */
    cell new_sr = copy_cell(sr1);
    new_sr_l = CONS(CELL, new_sr, new_sr_l);
  }
  else {
    list ind1 = reference_indices(r_1);
    SET_FOREACH(points_to, pp, binding) {
      cell sr2 = points_to_source(pp); 
      cell sk2 = points_to_sink(pp); 
      reference r22 = copy_reference(cell_to_reference(sk2));
      // FI: this test should be factored out
      if(!source_in_set_p(sr1, binding)) {
        // sr1 cannot be translated directly, let's try to remove
        // (some) subscripts
        reference r_12 = cell_any_reference(sr2);
        entity v_12 = reference_variable( r_12 );
        if(same_string_p(entity_local_name(v_1),entity_local_name(v_12))) {
          /* We assume here that the subscript list of sr1, the
             reference to translate, is longer than the subscript
             list of sr2, the source of its translation. */
          list ind2 = reference_indices(r_12);
          pips_assert("The effective subscript list is longer than "
                      "the translated subscript list",
                      gen_length(ind1)>=gen_length(ind2));
          // Either we check the subscript compatibility or we trust it
          // Let's trust it: no!
          list cind1 = ind1, cind2 = ind2;
          bool compatible_p = true;
          while(!ENDP(cind2)) {
            expression s1 = EXPRESSION(CAR(cind1));
            expression s2 = EXPRESSION(CAR(cind2));
            if(!compatible_points_to_subscripts_p(s1, s2)) {
              compatible_p = false;
              break;
            }
            POP(cind1), POP(cind2);
          }
          if(compatible_p) {
            // Propagate the remaining subscripts on the translation target
            reference_indices(r22) = gen_nconc(reference_indices(r22),cind1);
            cell new_sr = make_cell_reference(r22);
            new_sr_l = CONS(CELL, new_sr, new_sr_l);
          }
        }
      }
      else if(points_to_compare_cell(sr1,sr2)) {
        // sr1 can be translated directly as sk2
        cell new_sr = copy_cell(points_to_sink(pp));
        new_sr_l = CONS(CELL, new_sr, new_sr_l);
      }
    }
  }
  return new_sr_l;
}

References any_function_to_return_value(), CAR, CELL, cell_any_reference(), cell_to_reference(), compatible_points_to_subscripts_p(), CONS, copy_cell(), copy_reference(), ENDP, entity_anywhere_locations_p(), entity_local_name(), entity_to_module_entity(), entity_typed_anywhere_locations_p(), EXPRESSION, f(), gen_length(), gen_nconc(), heap_cell_p(), make_cell_reference(), NIL, pips_assert, points_to_compare_cell(), points_to_sink, points_to_source, POP, reference_indices, reference_variable, s1, same_string_p, SET_FOREACH, and source_in_set_p().

Referenced by add_implicitly_killed_arcs_to_kill_set(), compute_points_to_gen_set(), and generic_points_to_cells_translation().

Here is the call graph for this function:

Here is the caller graph for this function:

points_to_cells_exact_translation()

list points_to_cells_exact_translation	(	list	cl,
		set	binding,
		entity	f
	)

Allocate a new list with the translations of the cells in cl, when their translation make sense and is unique (one-to-one mapping).

Effects on copied parameters are discarded.

Parameters

cl	l
binding	inding

Definition at line 2327 of file interprocedural.c.

{
  return generic_points_to_cells_translation(cl, binding, f, true);
}

References f(), and generic_points_to_cells_translation().

Referenced by user_call_to_points_to_interprocedural().

Here is the call graph for this function:

Here is the caller graph for this function:

points_to_cells_parameters()

list points_to_cells_parameters

(

list

dl

)

Transform a list of parameters of type "entity" to a list of cells.

interprocedural.c

The list is not sorted. It is probably a reversed list.

Parameters

dl

l

Definition at line 68 of file interprocedural.c.

{
  list fpcl = NIL;
  FOREACH(ENTITY, fp, dl) {
    if(formal_parameter_p(fp) && !location_entity_p(fp)) {
      type fpt = entity_basic_concrete_type(fp);
      // FI: not all formal parameter may impact points-to
      if(pointer_type_p(fpt) || struct_type_p(fpt) || array_type_p(fpt)) {
        reference r = make_reference(fp, NIL);
        cell c = make_cell_reference(r);
        fpcl = gen_nconc(CONS(CELL, c, NULL), fpcl);
      }
    }
  }
  return fpcl;
}

References array_type_p(), CELL, CONS, ENTITY, entity_basic_concrete_type(), FOREACH, formal_parameter_p(), gen_nconc(), location_entity_p(), make_cell_reference(), make_reference(), NIL, pointer_type_p(), and struct_type_p().

Referenced by user_call_to_points_to(), user_call_to_points_to_fast_interprocedural(), user_call_to_points_to_interprocedural(), and user_call_to_points_to_interprocedural_binding_set().

Here is the call graph for this function:

Here is the caller graph for this function:

points_to_cells_pointer_arguments()

list points_to_cells_pointer_arguments

(

list

al

)

Transform a list of arguments of type "expression" to a list of cells.

The list is not sorted. It is probably a reversed list.

Parameters

al

l

Definition at line 90 of file interprocedural.c.

{
  list apcl = NIL;
  FOREACH(EXPRESSION, ap, al) {
    if(expression_pointer_p(ap) && expression_reference_p(ap)) {
      reference r = expression_reference(ap);
      cell c = make_cell_reference(r);
      apcl = gen_nconc(CONS(CELL, c, NULL), apcl);
    }
  }
  return apcl;
}

References CELL, CONS, EXPRESSION, expression_pointer_p(), expression_reference(), expression_reference_p(), FOREACH, gen_nconc(), make_cell_reference(), and NIL.

Referenced by user_call_to_points_to_fast_interprocedural().

Here is the call graph for this function:

Here is the caller graph for this function:

points_to_cells_translation()

list points_to_cells_translation	(	list	cl,
		set	binding,
		entity	f
	)

Allocate a new list with the translations of the cells in cl, when their translation make sense.

Effects on copied parameters are discarded.

Parameters

cl	l
binding	inding

Definition at line 2318 of file interprocedural.c.

{
  return generic_points_to_cells_translation(cl, binding, f, false);
}

References f(), and generic_points_to_cells_translation().

Referenced by user_call_to_points_to_interprocedural().

Here is the call graph for this function:

Here is the caller graph for this function:

points_to_set_to_module_stub_cell_list()

list points_to_set_to_module_stub_cell_list	(	entity	m,
		set	s,
		list	osl
	)

Parameters

osl

sl

Definition at line 2860 of file interprocedural.c.

{
  return generic_points_to_set_to_stub_cell_list(m, s, osl);
}

References generic_points_to_set_to_stub_cell_list().

Referenced by user_call_to_points_to_interprocedural().

Here is the call graph for this function:

Here is the caller graph for this function:

points_to_set_to_stub_cell_list()

list points_to_set_to_stub_cell_list	(	set	s,
		list	osl
	)

Parameters

osl

sl

Definition at line 2855 of file interprocedural.c.

{
  return generic_points_to_set_to_stub_cell_list(entity_undefined, s, osl);
}

References entity_undefined, and generic_points_to_set_to_stub_cell_list().

Here is the call graph for this function:

points_to_source_alias()

cell points_to_source_alias	(	points_to	pt,
		set	pt_binded
	)

Let "pt_binded" be the results of assignments of actual arguments to formal arguments (see compute_points_to_binded_set()).

Let "pt" be a points-to arc in "pt_binded".

Find for the source of p its corresponding alias, which means finding another source that points to the same location.

Parameters

pt	t
pt_binded	t_binded

Definition at line 2873 of file interprocedural.c.

{
  cell source = cell_undefined;
  cell sink1 = points_to_sink(pt);
  SET_FOREACH(points_to, p, pt_binded) {
    cell sink2 =  points_to_sink(p);
    if(cell_equal_p(sink1, sink2)) {
      source = points_to_source(p);
      break;
      }
  }
  if(cell_undefined_p(source))
    pips_internal_error("At least one alias should be found.\n");
 
  return source;
}

References cell_equal_p(), cell_undefined, cell_undefined_p, pips_internal_error, points_to_sink, points_to_source, and SET_FOREACH.

Referenced by points_to_binding().

Here is the call graph for this function:

Here is the caller graph for this function:

points_to_translation_mapping_is_typed_p()

bool points_to_translation_mapping_is_typed_p

(

set

translation

)

FI: for some reason, the translation was built wrongly to express the fact that the source points to any element of the sink as in Semantics-New/Ancourt3009/memcpy09c where pointer arithmetic is used in the actual argument expression.

out -> buffer_out[*]

out cannot be replaced by buffer_out, because out[i] would result in buffer_out[i] instead of buffer_out[*].

Parameters

translation

ranslation

Definition at line 1433 of file interprocedural.c.

{
  bool typed_p = true;
  SET_FOREACH(points_to, pt, translation) {
    cell source = points_to_source(pt);
    cell sink = points_to_sink(pt);
    type source_t = points_to_cell_to_concrete_type(source);
    type isink_t = points_to_cell_to_concrete_type(sink);
    type sink_t = constant_string_type_to_string_type(isink_t);
#if 0
    if(type_functional_p(isink_t)) {
      reference ar = cell_any_reference(ac);
      entity a = reference_variable(ar);
      if(constant_string_entity_p(a)) {
        sink_t = ...;
      }
    }
#endif
    if(char_type_p(source_t) && char_star_constant_function_type_p(isink_t)) {
      // an array of char points to a constant string, e.g. "YES"
      typed_p = true;
    }
    else if(!array_pointer_string_type_equal_p(source_t, sink_t)
       && !overloaded_type_p(sink_t)) {
      /* FI: for some reason, the translation was built wrongly to
       * express the fact that the source points to any element of the
       * sink as in Semantics-New/Ancourt3009/memcpy09c where pointer
       * arithmetic is used in the actual argument expression.
       *
       * out -> buffer_out[*]
       *
       * out cannot be replaced by buffer_out, because out[i] would
       * result in buffer_out[i] instead of buffer_out[*].
       */
      type st = type_to_pointed_type(source_t);
      // FI: if(type_structurally_equal_p(source_t, sink_t)? slower?
      if(array_pointer_string_type_equal_p(st, sink_t))
        typed_p = true;
      else {
        typed_p = false;
        pips_internal_error("Badly typed points-to translation mapping.\n");
      }
      break;
    }
  }
  return typed_p;
}

References array_pointer_string_type_equal_p(), cell_any_reference(), char_star_constant_function_type_p(), char_type_p(), constant_string_entity_p(), constant_string_type_to_string_type(), overloaded_type_p(), pips_internal_error, points_to_cell_to_concrete_type(), points_to_sink, points_to_source, reference_variable, SET_FOREACH, type_functional_p, and type_to_pointed_type().

Referenced by filter_formal_context_according_to_actual_context(), new_filter_formal_context_according_to_actual_context(), points_to_translation_of_formal_parameters(), and recursive_filter_formal_context_according_to_actual_context().

Here is the call graph for this function:

Here is the caller graph for this function:

points_to_translation_of_formal_parameters()

void points_to_translation_of_formal_parameters	(	list	fpcl,
		list	al,
		pt_map	pt_in,
		set	translation
	)

List al and fpcl are assumed consistent, and consistent with the formal parameter ranks.

assumption about fpcl

This function does not return constant memory paths... This could fixed below with calls to points_to_indices_to_unbounded_indices(), but it could/should also be fixed later in the processing, at callees level. See EffectsWithPointsTo.sub/call05.c

See also EffectsWithPointsTo.sub/call08.c: &y[i][1] You need expression_to_points_to_sinks() on such a lhs expression...

This occurs with actual argument "&e": when the address-of operator is used, the relation between the formal parameter, let say "p", and "e" cannot be expressed unless we build a location entity with name "&e".

Beware of constant character strings

Likely to be wrong whe the formal parameter is a pointer and the actual parameter is a simple pointer, or a pointer to an array with fewer dimensions.

Parameters

fpcl	pcl
al	l
pt_in	t_in
translation	ranslation

Definition at line 1483 of file interprocedural.c.

{
  FOREACH(CELL, fc, fpcl) {
    /* assumption about fpcl */
    entity v = reference_variable(cell_any_reference(fc));
    int n = formal_offset(storage_formal(entity_storage(v)));
    expression a = EXPRESSION(gen_nth(n-1, al));
    /* This function does not return constant memory paths... This
     * could fixed below with calls to
     * points_to_indices_to_unbounded_indices(), but it could/should also be
     * fixed later in the processing, at callees level. See
     * EffectsWithPointsTo.sub/call05.c
     *
     * See also EffectsWithPointsTo.sub/call08.c: &y[i][1]
     * You need expression_to_points_to_sinks() on such a lhs expression...
     */
    list acl = expression_to_points_to_sources(a, pt_in);
    if(false && ENDP(acl)) {
      /* This occurs with actual argument "&e": when the address-of
         operator is used, the relation between the formal parameter,
         let say "p", and "e" cannot be expressed unless we build a
         location entity with name "&e". */
      acl = expression_to_points_to_sinks(a, pt_in);
    }
    int nacl = (int) gen_length(acl);
    // FI->FI: you should check nacl==0... OK, but to do what ?
    approximation ap = nacl==1? make_approximation_exact() :
      make_approximation_may();
    FOREACH(CELL, ac, acl) {
      cell source = copy_cell(fc);
      //bool to_be_freed;
      //type a_source_t = points_to_cell_to_type(ac, &to_be_freed);
      //type source_t = compute_basic_concrete_type(a_source_t);
      type source_t = points_to_cell_to_concrete_type(source);
      if(pointer_type_p(source_t)) {
        cell n_source = copy_cell(fc);
        cell n_sink = copy_cell(ac);
        type e_sink_t = points_to_cell_to_concrete_type(n_sink);
        type sink_t = e_sink_t;
        /* Beware of constant character strings */
        if(type_functional_p(e_sink_t)) {
          functional f = type_functional(sink_t);
          if(ENDP(functional_parameters(f)))
            sink_t = functional_result(f);
        }
        //reference n_sink_r = cell_any_reference(n_sink);
        // points_to_indices_to_unbounded_indices(reference_indices(n_sink_r));
        if(type_equal_p(source_t, sink_t)) {
          if(array_pointer_string_type_equal_p(source_t, sink_t))
            ; // do nothing: a 1D array is equivalent to a pointer
          else if(array_type_p(sink_t)) {
            // FI: I do not remember in which case I needed this
            points_to_cell_add_zero_subscript(n_sink);
          }
          else if(scalar_type_p(sink_t)) {
            // Pointers/dereferencing11.c:
            // "i", double *, and "fifi[3][0]", double [2][3]
            reference n_sink_r = cell_any_reference(n_sink);
            list n_sink_sl = reference_indices(n_sink_r);
            bool succeed_p = false;
            if(!ENDP(n_sink_sl)) {
              expression ls = EXPRESSION(CAR(gen_last(n_sink_sl)));
              if(zero_expression_p(ls)) {
                // points_to_cell_remove_last_zero_subscript(n_sink);
                gen_remove_once(&reference_indices(n_sink_r), ls);
                succeed_p = true;
              }
            }
            if(!succeed_p)
              pips_internal_error("Not implemented yet.\n");
          }
          else
            pips_internal_error("Not implemented yet.\n");
        }
        points_to pt = make_points_to(n_source, n_sink, copy_approximation(ap),
                                      make_descriptor_none());
        add_subscript_dependent_arc_to_simple_pt_map(pt, translation);
      }
      else if(array_type_p(source_t)) {
        if(array_of_pointers_type_p(source_t)) {
          /* Likely to be wrong whe the formal parameter is a pointer
             and the actual parameter is a simple pointer, or a
             pointer to an array with fewer dimensions. */
          cell n_source = copy_cell(fc);
          cell n_sink = copy_cell(ac);
          //reference n_sink_r = cell_any_reference(n_sink);
          // points_to_indices_to_unbounded_indices(reference_indices(n_sink_r));
          points_to pt = make_points_to(n_source, n_sink, copy_approximation(ap),
                                        make_descriptor_none());
          add_arc_to_simple_pt_map(pt, translation);
        //pips_internal_error("Not implemented yet.\n");
        }
        else if(array_of_struct_type_p(source_t)) {
          list fl = struct_type_to_fields(source_t);
          FOREACH(ENTITY, f, fl) {
            type ft = entity_basic_concrete_type(f);
            if(pointer_type_p(ft))
              pips_internal_error("Not implemented yet.\n");
            if(struct_type_p(ft))
              pips_internal_error("Not implemented yet.\n");
            else {
              ; // ignore
            }
          }
        }
        else {
          ; // Do no worry about these arrays
        }
      }
      else if(struct_type_p(source_t)) {
        // Can we make an artificial lhs and rhs and call
        // assign_to_points_to() in that specific case?
        // Or do we have to program yet another recursive descent in structs?
        // How do we keep track of the approximation?
        points_to_translation_of_struct_formal_parameter(fc,
                                                         ac,
                                                         ap,
                                                         source_t,
                                                         translation);
      }
      else {
        ; // No need
      }
      //if(to_be_freed) free_type(a_source_t);
    }
    free_approximation(ap);
  }
  pips_assert("The points-to translation mapping is well typed",
              points_to_translation_mapping_is_typed_p(translation));
}

References add_arc_to_simple_pt_map, add_subscript_dependent_arc_to_simple_pt_map(), array_of_pointers_type_p(), array_of_struct_type_p(), array_pointer_string_type_equal_p(), array_type_p(), CAR, CELL, cell_any_reference(), copy_approximation(), copy_cell(), ENDP, ENTITY, entity_basic_concrete_type(), entity_storage, EXPRESSION, expression_to_points_to_sinks(), expression_to_points_to_sources(), f(), FOREACH, formal_offset, free_approximation(), functional_parameters, functional_result, gen_last(), gen_length(), gen_nth(), gen_remove_once(), int, make_approximation_exact(), make_approximation_may(), make_descriptor_none(), make_points_to(), pips_assert, pips_internal_error, pointer_type_p(), points_to_cell_add_zero_subscript(), points_to_cell_to_concrete_type(), points_to_translation_mapping_is_typed_p(), points_to_translation_of_struct_formal_parameter(), reference_indices, reference_variable, scalar_type_p(), storage_formal, struct_type_p(), struct_type_to_fields(), type_equal_p(), type_functional, type_functional_p, and zero_expression_p().

Referenced by user_call_to_points_to_interprocedural(), and user_call_to_points_to_interprocedural_binding_set().

Here is the call graph for this function:

Here is the caller graph for this function:

points_to_translation_of_struct_formal_parameter()

void points_to_translation_of_struct_formal_parameter	(	cell	fc,
		cell	ac,
		approximation	a,
		type	st,
		set	translation
	)

We assume that cell fc and cell ac are of type st and that st is a struct type.

Parameters

fc	c
ac	c
st	t
translation	ranslation

Definition at line 1365 of file interprocedural.c.

{
  /* We assume that cell fc and cell ac are of type st and that st is
     a struct type. */
  // pips_internal_error("Not implemented yet.\n");
  list fl = struct_type_to_fields(st);
 
  FOREACH(ENTITY, f, fl) {
    type ft = entity_basic_concrete_type(f);
    if(pointer_type_p(ft)) {
      cell nfc = copy_cell(fc);
      cell nac = copy_cell(ac);
      points_to_cell_add_field_dimension(nfc, f);
      points_to_cell_add_field_dimension(nac, f);
      points_to pt = make_points_to(nfc, nac, copy_approximation(a),
                                    make_descriptor_none());
      add_arc_to_simple_pt_map(pt, translation);
    }
    else if(struct_type_p(ft)) {
      cell nfc = copy_cell(fc);
      cell nac = copy_cell(ac);
      points_to_cell_add_field_dimension(nfc, f);
      points_to_cell_add_field_dimension(nac, f);
      points_to_translation_of_struct_formal_parameter(fc,
                                                       ac,
                                                       a,
                                                       ft,
                                                       translation);
      free_cell(nfc), free_cell(nac);
    }
    else if(array_of_pointers_type_p(ft)) {
      cell nfc = copy_cell(fc);
      cell nac = copy_cell(ac);
      points_to_cell_add_field_dimension(nfc, f);
      points_to_cell_add_field_dimension(nac, f);
      points_to_cell_add_unbounded_subscripts(nfc);
      points_to_cell_add_unbounded_subscripts(nac);
      points_to pt = make_points_to(nfc, nac, copy_approximation(a),
                                    make_descriptor_none());
      add_arc_to_simple_pt_map(pt, translation);
    }
    else if(array_of_struct_type_p(ft)) {
      cell nfc = copy_cell(fc);
      cell nac = copy_cell(ac);
      points_to_cell_add_field_dimension(nfc, f);
      points_to_cell_add_field_dimension(nac, f);
      points_to_cell_add_unbounded_subscripts(nfc);
      points_to_cell_add_unbounded_subscripts(nac);
      type et = array_type_to_element_type(ft);
      type cet = compute_basic_concrete_type(et);
      points_to_translation_of_struct_formal_parameter(fc,
                                                       ac,
                                                       a,
                                                       cet,
                                                       translation);
      free_cell(nfc), free_cell(nac);
    }
    else {
      ; // do nothing
    }
  }
 
}

References add_arc_to_simple_pt_map, array_of_pointers_type_p(), array_of_struct_type_p(), array_type_to_element_type(), compute_basic_concrete_type(), copy_approximation(), copy_cell(), ENTITY, entity_basic_concrete_type(), f(), FOREACH, free_cell(), make_descriptor_none(), make_points_to(), pointer_type_p(), points_to_cell_add_field_dimension(), points_to_cell_add_unbounded_subscripts(), struct_type_p(), and struct_type_to_fields().

Referenced by points_to_translation_of_formal_parameters().

Here is the call graph for this function:

Here is the caller graph for this function:

recursive_filter_formal_context_according_to_actual_context()

bool recursive_filter_formal_context_according_to_actual_context	(	list	fcl,
		set	pt_in,
		set	pt_binded,
		set	binding,
		set	filtered
	)

This function looks for successors of elements of list "fcl" both in points-to relations "pt_in" and "pt_binded".

Update the formal context defined by "pt_binded" on demand as necessary according to "pt_in", update the translation mapping "binding" according to the new pairs found, and go down recursively with a new list of constant paths, "nfcl", the possible successors in the formal context of the callee of elements in "fcl" when possible. In fact, the elements in "nfcl" must be pointers and are not necessarily the successors of elements of "fcl", but pointers contained in them.

This function is very similar to filter_formal_context_according_to_actual_context(), but a little bit more tricky. Amira Mensi unified both in her own version, but the unification makes the maintenance more difficult.

Copy only possible arcs "pt" from "pt_in" into the "filtered" set

FI: this assert may be too strong FI: This assert is too strong for Pointers/formal_parameter01 and its message is misleading because "source" is not an element of "fcl". Elements of "fcl" must be translated, but related elements may not be translatable because the effective context is not as rich as the formal context. For instance, the formal context may expect an array for each formal scalar pointer, but the effective target may be a scalar. And an error must be raised if pointer arithmetic is used in the callee.

Make sure pt_binded is large enough: the pointer may be initialized before the call to the caller and used only in the callee. Because of the on-demand approach, pt_binded does not contain enough elements.

Do we have a similar arc in pt_binded?

Compute the binding relation for sinks of the formal context list "fcl"

If "fc" is not a pointer, look for pointers in "fc"

Now, we have to call about the same function recursively on the list of formal sinks

Parameters

fcl	cl
pt_in	t_in
pt_binded	t_binded
binding	inding
filtered	iltered

Definition at line 362 of file interprocedural.c.

{
  bool ok_p = true;
  points_to_graph binding_g = make_points_to_graph(false, binding);
 
  /* Copy only possible arcs "pt" from "pt_in" into the "filtered" set */
  SET_FOREACH(points_to, pt, pt_in) {
    cell source = points_to_source(pt);
    if(related_points_to_cell_in_list_p(source, fcl)) {
      cell sink = points_to_sink(pt);
      list ptsl = points_to_source_to_sinks(source, binding_g, false);
 
      /* FI: this assert may be too strong FI: This assert is too
       * strong for Pointers/formal_parameter01 and its message is
       * misleading because "source" is not an element of
       * "fcl". Elements of "fcl" must be translated, but related
       * elements may not be translatable because the effective
       * context is not as rich as the formal context. For instance,
       * the formal context may expect an array for each formal scalar
       * pointer, but the effective target may be a scalar. And an
       * error must be raised if pointer arithmetic is used in the
       * callee.
       */
      if(points_to_cell_in_list_p(source, fcl ))
        pips_assert("Elements of \"fcl\" can be translated", !ENDP(ptsl));
 
      list tsl = points_to_cells_to_pointer_cells(ptsl);
      gen_free_list(ptsl);
 
      if(!ENDP(tsl)) {
        /* Make sure pt_binded is large enough: the pointer may be
           initialized before the call to the caller and used only in
           the callee. Because of the on-demand approach, pt_binded
           does not contain enough elements. */
        pt_map pt_binded_g = make_points_to_graph(false, pt_binded);
        FOREACH(CELL, c, tsl) {
          list sinks = any_source_to_sinks(c, pt_binded_g, false);
          gen_free_list(sinks);
        }
 
        if(null_cell_p(sink)) {
          /* Do we have a similar arc in pt_binded? */
          FOREACH(CELL, tc, tsl) {
            if(cell_points_to_null_sink_in_set_p(tc, pt_binded)) {
              points_to npt = copy_points_to(pt);
              add_arc_to_simple_pt_map(npt, filtered);
              break;
            }
            else {
              ; // do not copy this arc in filtered set
            }
          }
        }
        else {
          FOREACH(CELL, tc, tsl) {
            if(cell_must_point_to_nowhere_sink_in_set_p(tc, pt_binded)) {
              /* */
              semantics_user_warning("An uninitialized pointer, \"%s\", may be reached.\n ", points_to_cell_to_string(tc));
              //ok_p = false;
            }
            else if(cell_points_to_non_null_sink_in_set_p(tc, pt_binded)) {
              if(cell_points_to_nowhere_sink_in_set_p(tc, pt_binded)) {
                /* */
                semantics_user_warning("An uninitialized pointer, \"%s\", might be reached.\n ", points_to_cell_to_string(tc));
              }
              points_to npt = copy_points_to(pt);
              add_arc_to_simple_pt_map(npt, filtered);
              break;
            }
            else {
              ; // do not copy this arc in filtered set
            }
          }
        }
        gen_free_list(tsl);
      }
      else {
        ; // do not copy this arc in filtered set
      }
    }
  }
 
  /* Compute the binding relation for sinks of the formal context list "fcl" */
  list nfcl = NIL;
  FOREACH(CELL, c, fcl) {
    points_to_graph filtered_g = make_points_to_graph(false, filtered);
    list fl = points_to_source_to_some_sinks(c, filtered_g, false); // formal list
    if(!ENDP(fl)) {
      // FI: I am in trouble with _nl_1 and _nl_1[next]; the first one
      // is not recognized in the second one.
      //list tsl = points_to_source_to_sinks(c, binding_g, false);
      list tsl = points_to_source_to_some_sinks(c, binding_g, false);
      //list tsl = source_to_sinks(c, binding_g, false);
      FOREACH(CELL, tc, tsl) {
        points_to_graph pt_binded_g = make_points_to_graph(false, pt_binded);
        list al = points_to_source_to_some_sinks(tc, pt_binded_g, false); // formal list
        int nfl = (int) gen_length(fl);
        int nal = (int) gen_length(al);
        approximation a = approximation_undefined;
        if(nfl==1 && nal==1)
          a = make_approximation_exact();
        else
          a = make_approximation_may();
        FOREACH(CELL, fc, fl) {
          if(!null_cell_p(fc)) {
            FOREACH(CELL, ac, al) {
              if(!null_cell_p(ac) && !nowhere_cell_p(ac)) {
                type fc_t = points_to_cell_to_concrete_type(fc);
                type ac_t = points_to_cell_to_concrete_type(ac);
                // FI: why not use array_pointer_string_type_equal_p()?
                if(!type_equal_p(fc_t, ac_t) && !overloaded_type_p(ac_t)) {
                  points_to_cell_add_zero_subscript(ac);
                  type ac_nt = points_to_cell_to_concrete_type(ac);
                  if(!type_equal_p(fc_t, ac_nt))
                    pips_internal_error("translation failure.\n");
                }
                points_to tr = make_points_to(copy_cell(fc), copy_cell(ac), 
                                              copy_approximation(a),
                                              make_descriptor_none());
                add_arc_to_simple_pt_map(tr, binding);
              }
            }
            /* If "fc" is  not a pointer, look for pointers in "fc" */
            list pcl = points_to_cell_to_useful_pointer_cells(fc, pt_in);
            nfcl = gen_nconc(nfcl, pcl);
            //nfcl = CONS(CELL, fc, nfcl);
          }
        }
        free_approximation(a);
      }
    }
    else {
      ; // No need to go down... if we stop with a good reason, not
      // because of a bug
      // pips_internal_error("Translation error.\n");
    }
  }
 
  pips_assert("The points-to translation mapping is well typed",
              points_to_translation_mapping_is_typed_p(binding));
 
  /* Now, we have to call about the same function recursively on the
     list of formal sinks */
  if(ok_p && !ENDP(nfcl)) {
    ok_p = recursive_filter_formal_context_according_to_actual_context
      (nfcl, pt_in, pt_binded, binding, filtered);
    gen_free_list(nfcl);
  }
 
  // FI binding_g should be freed, but not the set in it...
 
  return ok_p;
}

References add_arc_to_simple_pt_map, any_source_to_sinks(), approximation_undefined, CELL, cell_must_point_to_nowhere_sink_in_set_p(), cell_points_to_non_null_sink_in_set_p(), cell_points_to_nowhere_sink_in_set_p(), cell_points_to_null_sink_in_set_p(), copy_approximation(), copy_cell(), copy_points_to(), ENDP, FOREACH, free_approximation(), gen_free_list(), gen_length(), gen_nconc(), int, make_approximation_exact(), make_approximation_may(), make_descriptor_none(), make_points_to(), make_points_to_graph(), NIL, nowhere_cell_p(), null_cell_p(), overloaded_type_p(), pips_assert, pips_internal_error, points_to_cell_add_zero_subscript(), points_to_cell_in_list_p(), points_to_cell_to_concrete_type(), points_to_cell_to_string(), points_to_cell_to_useful_pointer_cells(), points_to_cells_to_pointer_cells(), points_to_sink, points_to_source, points_to_source_to_sinks(), points_to_source_to_some_sinks(), points_to_translation_mapping_is_typed_p(), related_points_to_cell_in_list_p(), semantics_user_warning, SET_FOREACH, tc, and type_equal_p().

Referenced by filter_formal_context_according_to_actual_context().

Here is the call graph for this function:

Here is the caller graph for this function:

remove_arcs_from_pt_map()

void remove_arcs_from_pt_map	(	points_to	pts,
		set	pt_out
	)

Parameters

pts	ts
pt_out	t_out

Definition at line 231 of file interprocedural.c.

{
  cell sink = points_to_sink(pts);
  cell source = points_to_source(pts);
  
 
  SET_FOREACH(points_to, pt, pt_out) {
    if(cell_equal_p(points_to_source(pt), sink) ||cell_equal_p(points_to_source(pt), source) ) {
      remove_arc_from_simple_pt_map(pts, pt_out);
      entity e = entity_anywhere_locations();
      reference r = make_reference(e, NIL);
      cell source = make_cell_reference(r);
      cell sink = copy_cell(source);
      approximation a = make_approximation_exact();
      points_to npt = make_points_to(source, sink, a, make_descriptor_none());
      add_arc_to_simple_pt_map(npt, pt_out);
      remove_arcs_from_pt_map(pt, pt_out);
    }
  }
}

References add_arc_to_simple_pt_map, cell_equal_p(), copy_cell(), entity_anywhere_locations(), make_approximation_exact(), make_cell_reference(), make_descriptor_none(), make_points_to(), make_reference(), NIL, points_to_sink, points_to_source, remove_arc_from_simple_pt_map, and SET_FOREACH.

Referenced by user_call_to_points_to_intraprocedural().

Here is the call graph for this function:

Here is the caller graph for this function:

translation_transitive_closure()

list translation_transitive_closure	(	cell	c,
		set	translation
	)

We are done

Parameters

translation

ranslation

Definition at line 1702 of file interprocedural.c.

{
  list succ = CONS(CELL, c, NIL);
  list n_succ = gen_copy_seq(succ);
  bool finished_p = false;
  while(!finished_p) {
    points_to_graph translation_g = make_points_to_graph(false, translation);
    // Do not worry about sharing due to NULL or UNDEFINED/NOWHERE
    // Potentially new successors
    list pn_succ = points_to_sources_to_effective_sinks(n_succ, translation_g, false);
    list n_succ = NIL; // Reealy new successors
    // FI: does not work in general because the content is not used, shallow
    // gen_list_and_not(&n_succ, succ);
    FOREACH(CELL, c, pn_succ) {
      if(!points_to_cell_in_list_p(c, succ))
        n_succ = CONS(CELL, c, n_succ);
    }
    gen_free_list(pn_succ);
    if(ENDP(n_succ)) {
      /* We are done */
      finished_p = true;
      break;
    }
    else {
      succ = gen_nconc(succ, n_succ);
      n_succ = gen_copy_seq(n_succ);
    }
  }
  return succ;
}

References CELL, CONS, ENDP, FOREACH, gen_copy_seq(), gen_free_list(), gen_nconc(), make_points_to_graph(), NIL, points_to_cell_in_list_p(), and points_to_sources_to_effective_sinks().

Referenced by aliased_translation_p().

Here is the call graph for this function:

Here is the caller graph for this function:

user_call_to_points_to()

points_to_graph user_call_to_points_to	(	call	c,
		points_to_graph	pt_in,
		list	el
	)

FI: limited to the interprocedural option.

pcl =

Using memory effects does not simplify the points-to analysis, which is a preliminary analusis wrt memory effects

Parameters

pt_in	t_in
el	l

Definition at line 106 of file interprocedural.c.

{
  points_to_graph pt_out = pt_in;
  if(!points_to_graph_bottom(pt_in)) {
    entity f = call_function(c);
    //list al = call_arguments(c);
 
    // FI: intraprocedural, use effects
    // FI: interprocedural, check alias compatibility, generate gen and kill sets,...
    pt_out = pt_in;
 
    // Code by Amira
    //list fpcl = NIL; // Formal parameter cell list
    type t = entity_basic_concrete_type(f);
    if(type_functional_p(t)) {
      list dl = code_declarations(value_code(entity_initial(f)));
      /*fpcl = */points_to_cells_parameters(dl);   
    }
    else {
      pips_internal_error("Function has not a functional type.\n");
    }
 
    /* Using memory effects does not simplify the points-to analysis,
       which is a preliminary analusis wrt memory effects */
    if(interprocedural_points_to_analysis_p()) {
      pt_out = user_call_to_points_to_interprocedural(c, pt_in);
    }
    else if(fast_interprocedural_points_to_analysis_p()) {
      pt_out = user_call_to_points_to_fast_interprocedural(c, pt_in, el);
    }
    else {
      pt_out = user_call_to_points_to_intraprocedural(c, pt_in, el);
    }
  }
 
  return pt_out;
}

References call_function, code_declarations, entity_basic_concrete_type(), entity_initial, f(), fast_interprocedural_points_to_analysis_p(), interprocedural_points_to_analysis_p(), pips_internal_error, points_to_cells_parameters(), points_to_graph_bottom, type_functional_p, user_call_to_points_to_fast_interprocedural(), user_call_to_points_to_interprocedural(), user_call_to_points_to_intraprocedural(), and value_code.

Referenced by call_to_points_to(), and user_call_condition_to_points_to().

Here is the call graph for this function:

Here is the caller graph for this function:

user_call_to_points_to_fast_interprocedural()

pt_map user_call_to_points_to_fast_interprocedural	(	call	c,
		pt_map	pt_in,
		list csel	__attribute__(unused)
	)

ompute the points to relations in a fast interprocedural way

"c" is the call site

"pt_in" is the points-to information available before the call site is executed.

"csel" is the call site effect list

Compute kill_1 = effective parameters of pointer type should point to nowhere in case the function call the free routine.

Definition at line 262 of file interprocedural.c.

{
  set pt_in_s = points_to_graph_set(pt_in);
  pt_map pt_out = pt_in;
  set kill_1 =  set_generic_make(set_private, points_to_equal_p, points_to_rank);
  set gen_1 =  set_generic_make(set_private, points_to_equal_p, points_to_rank);
  set gen_2 =  set_generic_make(set_private, points_to_equal_p, points_to_rank);
  entity f = call_function(c);
  list al = call_arguments(c);
  list dl = code_declarations(value_code(entity_initial(f)));
  list fpcl = points_to_cells_parameters(dl);   
  /* Compute kill_1 = effective parameters of pointer type should point to
     nowhere in case the function call the free routine.
  */
  list apcl = points_to_cells_pointer_arguments(al);
  FOREACH(CELL, ac, apcl) {
    SET_FOREACH(points_to, pt, pt_in_s) {
      if(points_to_cell_equal_p(ac, points_to_source(pt)) ) {
        points_to npt = copy_points_to(pt);
        (void) add_arc_to_simple_pt_map(npt, kill_1);
      }
    }
  }
  ifdebug(8) print_points_to_set("kill_1",kill_1);
  
  SET_FOREACH(points_to, pt_to, kill_1) {
    approximation a = make_approximation_may();
    cell sr = copy_cell(points_to_source(pt_to));
    cell sk = copy_cell(points_to_sink(pt_to));
    points_to npt = make_points_to(sr, sk, a, make_descriptor_none());
    (void) add_arc_to_simple_pt_map(npt, gen_1);
  }
  ifdebug(8) print_points_to_set("gen_1",gen_1);
 
  
  SET_FOREACH(points_to, pt_to1, gen_1) {
    cell source = copy_cell(points_to_source(pt_to1));
    cell nc = cell_to_nowhere_sink(source);
    approximation a = make_approximation_may();
    points_to npt = make_points_to(source, nc, a, make_descriptor_none());
    (void) add_arc_to_simple_pt_map(npt, gen_2);
  }
  ifdebug(8) print_points_to_set("gen_1",gen_2);
 
 
 
  extern list load_summary_effects(entity e);
  list el = load_summary_effects(f);
  list wpl = written_pointers_set(el);
  points_to_list pts_to_in = (points_to_list)
    db_get_memory_resource(DBR_POINTS_TO_IN, module_local_name(f), true);
  list l_pt_to_in = gen_full_copy_list(points_to_list_list(pts_to_in));
  set pt_in_callee = new_simple_pt_map();
  pt_in_callee = set_assign_list(pt_in_callee, l_pt_to_in);
  // list l_pt_to_out = gen_full_copy_list(points_to_list_list(pts_to_out));
  // pt_map pt_out_callee = set_assign_list(pt_out_callee, l_pt_to_out);
  bool success_p = false;
  set pts_binded = compute_points_to_binded_set(f, al, pt_in_s, & success_p);
  // FI->AM: for the time being, ignore success_p...
  ifdebug(8) print_points_to_set("pt_binded", pts_binded);
  set bm = points_to_binding(fpcl, pt_in_callee, pts_binded);
  set pts_kill = compute_points_to_kill_set(wpl, pt_in_s, bm);
  ifdebug(8) print_points_to_set("pts_kill", pts_kill);
  set pts_gen = new_simple_pt_map();
  SET_FOREACH(points_to, pt, pts_kill) {
    cell source = points_to_source(pt);
    cell nc = cell_to_nowhere_sink(source);
    approximation a = make_approximation_exact();
    points_to npt = make_points_to(source, nc, a, make_descriptor_none());
    (void) add_arc_to_simple_pt_map(npt, pts_gen);
  }
  set pt_end = new_simple_pt_map();
  pts_kill = set_union(pts_kill, pts_kill, kill_1);
  pt_end = set_difference(pt_end, pt_in_s, pts_kill);
  pts_gen = set_union(pts_gen, pts_gen, gen_1);
  pts_gen = set_union(pts_gen, pts_gen, gen_2);
  pt_end = set_union(pt_end, pt_end, pts_gen);
  ifdebug(8) print_points_to_set("pt_end =", pt_end);
  points_to_graph_set(pt_out) = pt_end;
  return pt_out;
}

References add_arc_to_simple_pt_map, call_arguments, call_function, CELL, cell_to_nowhere_sink(), code_declarations, compute_points_to_binded_set(), compute_points_to_kill_set(), copy_cell(), copy_points_to(), db_get_memory_resource(), entity_initial, f(), FOREACH, gen_full_copy_list(), ifdebug, load_summary_effects(), make_approximation_exact(), make_approximation_may(), make_descriptor_none(), make_points_to(), module_local_name(), new_simple_pt_map, points_to_binding(), points_to_cell_equal_p(), points_to_cells_parameters(), points_to_cells_pointer_arguments(), points_to_equal_p(), points_to_graph_set, points_to_list_list, points_to_rank(), points_to_sink, points_to_source, print_points_to_set(), set_assign_list(), set_difference(), SET_FOREACH, set_generic_make(), set_private, set_union(), value_code, and written_pointers_set().

Referenced by user_call_to_points_to().

Here is the call graph for this function:

Here is the caller graph for this function:

user_call_to_points_to_interprocedural()

pt_map user_call_to_points_to_interprocedural	(	call	c,
		pt_map	pt_caller
	)

Compute the points-to relations in a complete interprocedural way: be as accurate as possible.

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

This used to be only useful when a free occurs with the callee, since information about formal parameters used to be normally projected out.

Global variables do not require any translation in C, but it might more convenient to apply translation uniformly, without checking for global variables... Or the other way round?

Filter "pt_in" according to "pt_binded". For instance, a formal parameter can point to NULL in "pt_in" only if it also points to NULL in pt_binded. In the same way, a formal parameter can point to a points-to stub in "pt_in" only if it points to a non-NULL target in pt_binded. Also, a formal parameter cannot points exactly to UNDEFINED in "pt_binded" as it would be useless (not clear if we can remove such an arc when it is a may arc...). Finally, each formal parameter must still point to something. The mapping "binding" is augmented as needed. as well as "pt_caller" because of the on-demand approach. But "pt_binded" is not updated accordingly (?).

set pt_in_filtered =

filter_formal_context_according_to_actual_context(fpcl,

pt_in,

pt_binded,

binding);

We have to test if pt_binded is compatible with pt_in_callee

We have to start by computing all the elements of E (stubs)

See if two formal parameters can reach the same memory cell, i.e. transitive closure of binding map. We should take care of global variables too...

If no pointer is written, aliasing is not an issue

Explicitly written pointers imply some arc removals; pointer assignments directly or indirectly in the callee.

FI: pt_caller_s may have been modified implictly because the formal context has been increased according to the needs of the callee. But pt_caller_s may also have been updated by what has happened prevously when analyzing the current statement. See for instance Pointers/sort01.c.

Compute pt_kill_2

Implicitly written pointers imply some arc removals: free(), tests and exits. These are the elements of pt_kill_1, although the equations do not seem to fit at all since pt_in_filtered is not an argument...

Translation failure, incompatibility between the call site and the callee.

Some check

Use written/wpl to reduce the precision of exact arcs in pt_end. This is equivalent to pt_kill_3 and pt_gen_3.

FI: I do not understand why the precision of the write is not exploited. We may need to use mwpl instead of wpl

Some check

This cannot be performed earlier because the points-to precondition of the caller may have to be enriched according to the formal context of the callee, or the effect computation is going to fail.

Parameters

pt_caller

t_caller

Definition at line 1892 of file interprocedural.c.

{
  pt_map pt_end_f = pt_caller;
  pips_assert("pt_caller is valid", !points_to_graph_bottom(pt_caller));
  pips_assert("pt_caller is consistent", consistent_pt_map_p(pt_caller));
  entity f = call_function(c);
  list al = call_arguments(c);
  list dl = code_declarations(value_code(entity_initial(f)));
  list fpcl = points_to_cells_parameters(dl);   
  points_to_list pts_to_in = (points_to_list)
    db_get_memory_resource(DBR_POINTS_TO_IN, module_local_name(f), true);
  list l_pt_to_in = gen_full_copy_list(points_to_list_list(pts_to_in));
  points_to_list pts_to_out = (points_to_list)
    db_get_memory_resource(DBR_POINTS_TO_OUT, module_local_name(f), true);
  bool out_bottom_p = points_to_list_bottom(pts_to_out);
 
  list l_pt_to_out = gen_full_copy_list(points_to_list_list(pts_to_out));
 
  /* Not much to do if both IN and OUT are empty, except if OUT is
     bottom (see below) */
  if(!(ENDP(l_pt_to_out) && ENDP(l_pt_to_in))) {
    // FI: this function should be moved from semantics into effects-util
    extern list load_body_effects(entity e);
    list el = load_body_effects(f);
    list wpl = written_pointers_set(el);
    list cwpl = certainly_written_pointers_set(el);
    set pt_caller_s = points_to_graph_set(pt_caller);
    set pt_in = set_assign_list(new_simple_pt_map(), l_pt_to_in);
    set pt_out = set_assign_list(new_simple_pt_map(), l_pt_to_out);
 
    // FI: function name... set or list?
    bool success_p = false;
    set pt_binded = compute_points_to_binded_set(f, al, pt_caller_s, &success_p);
    ifdebug(8) print_points_to_set("pt_binded", pt_binded);
 
    if(success_p) {
      set binding = new_simple_pt_map();
      /* This used to be only useful when a free occurs with the
         callee, since information about formal parameters used to be
         normally projected out. */
      points_to_translation_of_formal_parameters(fpcl, al, pt_caller, binding);
 
      /* Global variables do not require any translation in C, but it
         might more convenient to apply translation uniformly, without
         checking for global variables... Or the other way round? */
      //points_to_translation_of_global_variables(pt_out, pt_caller, binding);
 
      /* Filter "pt_in" according to "pt_binded". For instance, a
         formal parameter can point to NULL in "pt_in" only if it
         also points to NULL in pt_binded. In the same way, a formal
         parameter can point to a points-to stub in "pt_in" only
         if it points to a non-NULL target in pt_binded. Also, a
         formal parameter cannot points exactly to UNDEFINED in
         "pt_binded" as it would be useless (not clear if we can remove
         such an arc when it is a may arc...). Finally, each formal
         parameter must still point to something. The mapping
         "binding" is augmented as needed. as well as "pt_caller"
         because of the on-demand approach. But "pt_binded" is not
         updated accordingly (?). */
      /* set pt_in_filtered = */
      /*        filter_formal_context_according_to_actual_context(fpcl, */
      /*                                                          pt_in, */
      /*                                                          pt_binded, */
      /*                                                          binding); */
      set pt_in_filtered =
        new_filter_formal_context_according_to_actual_context(fpcl,
                                                              pt_in,
                                                              pt_binded,
                                                              binding);
 
      /* We have to test if pt_binded is compatible with pt_in_callee */
      /* We have to start by computing all the elements of E (stubs) */
      //list stubs = stubs_list(pt_in_callee, pt_out_callee);
      // bool compatible_p = true;
      // FI: I do not understand Amira's test
      // = sets_binded_and_in_compatible_p(stubs, fpcl, pt_binded,
      //                                        pt_in_callee_filtered, pt_out_callee,
      //                                        binding);
      /* See if two formal parameters can reach the same memory cell,
       * i.e. transitive closure of binding map. We should take care
       * of global variables too... */
      // compatible_p = compatible_p && !aliased_translation_p(fpcl, pt_binded);
 
      // pt_binded and pt_in are incompatible for instance because the
      // caller not initialized a pointer
      if(set_undefined_p(pt_in_filtered)) {
        out_bottom_p = true;
      }
      /* If no pointer is written, aliasing is not an issue */
      else if(ENDP(wpl) || !aliased_translation_p(fpcl, pt_binded)) {
 
        set pt_out_filtered =
          filter_formal_out_context_according_to_formal_in_context
          (pt_out, pt_in_filtered, wpl, f);
 
        /* Explicitly written pointers imply some arc removals; pointer
           assignments directly or indirectly in the callee. */
        // pt_end = set_difference(pt_end, pt_caller_s, pts_kill);
 
        /* FI: pt_caller_s may have been modified implictly because the
         * formal context has been increased according to the needs of
         * the callee. But pt_caller_s may also have been updated by what
         * has happened prevously when analyzing the current
         * statement. See for instance Pointers/sort01.c.
         */
        set c_pt_caller_s = points_to_graph_set(points_to_context_statement_in());
        c_pt_caller_s = set_union(c_pt_caller_s, c_pt_caller_s, pt_caller_s);
 
        list tcwpl = points_to_cells_exact_translation(cwpl, binding, f);
        /* Compute pt_kill_2 */
        set pt_kill = compute_points_to_kill_set(tcwpl, c_pt_caller_s, binding);
        /* Implicitly written pointers imply some arc removals:
         * free(), tests and exits. These are the elements of
         * pt_kill_1, although the equations do not seem to fit at
         * all since pt_in_filtered is not an argument...
         */
        add_implicitly_killed_arcs_to_kill_set(pt_kill, 
                                               wpl,
                                               c_pt_caller_s,
                                               pt_out_filtered,
                                               binding,
                                               f);
        ifdebug(8) print_points_to_set("pt_kill", pt_kill);
 
        set pt_end = new_simple_pt_map();
        // FI: c_pr_in_s is probably pt_{caller} in the dissertation
        pt_end = set_difference(pt_end, c_pt_caller_s, pt_kill);
 
        set pt_gen_1 = compute_points_to_gen_set(pt_out_filtered,
                                                 wpl,
                                                 binding, f);
 
        if(set_undefined_p(pt_gen_1)) {
          /* Translation failure, incompatibility between the call site
             and the callee. */
          pips_user_warning("Incompatibility between call site and "
                            "callee's output.\n");
          out_bottom_p = true;
        }
        else {
          pips_assert("pt_gen_1 is consistent", consistent_points_to_set(pt_gen_1));
 
          // FI->FI: Not satisfying; kludge to solve issue with Pointers/inter04
          // FI->FI: this causes a core dump for Pointers/formal_parameter01.c
          // A lot should be said about this test case, which is revealing
          // because of the test it contains, and because of the
          // pointer arithmetic, and because the useless primature
          // expansion of_pi_1[1] in _pi_1[*] which is semantically
          // correct but fuzzy as it implies possible unexisting arcs
          // for _pi_1[0], _pi_1[2], etc...
          // FI->FI: the upgrade must be postponed
          /*
          pt_map pt_gen_1_g = make_points_to_graph(false, pt_gen_1);
          upgrade_approximations_in_points_to_set(pt_gen_1_g);
 
          pips_assert("pt_gen_1 is consistent after upgrade",
                      consistent_points_to_set(pt_gen_1));
          */
 
          /* Some check */
          list stubs = points_to_set_to_module_stub_cell_list(f, pt_gen_1, NIL);
          if(!ENDP(stubs)) {
            pips_internal_error("Translation failure in pt_gen_1.\n");
          }
 
          /* Use written/wpl to reduce the precision of exact arcs in
           * pt_end. This is equivalent to pt_kill_3 and pt_gen_3.
           *
           *
           * FI: I do not understand why the precision of the write is not
           * exploited. We may need to use mwpl instead of wpl
           *
           */
          list twpl = points_to_cells_translation(wpl, binding, f);
          pt_end =
            lower_points_to_approximations_according_to_write_effects(pt_end, twpl);
          // FI: I keep it temporarily for debugging purposes
          // gen_free_list(twpl);
 
          // FI: set_union is unsafe; the union of two consistent
          // points-to graph is not a consistent points-to graph
          pt_end = set_union(pt_end, pt_end, pt_gen_1);
          pips_assert("pt_end is consistent", consistent_points_to_set(pt_end));
          ifdebug(8) print_points_to_set("pt_end =",pt_end);
          /* Some check */
          stubs = points_to_set_to_module_stub_cell_list(f, pt_end, NIL);
          if(!ENDP(stubs)) {
            pips_internal_error("Translation failure in pt_end.\n");
          }
          points_to_graph_set(pt_end_f) = pt_end;
        }
      }
      else {
        pips_user_warning("Aliasing between arguments at line %d.\n"
                          "We would have to create a new formal context "
                          "and to restart the points-to analysis "
                          "and to modify the IN and OUT data structures...\n"
                          "Or use a simpler analysis, here an intraprocedural one.\n",
                          points_to_context_statement_line_number());
 
        pt_end_f = user_call_to_points_to_intraprocedural(c, pt_caller, el);
      }
    }
    else
      out_bottom_p = true;
  }
  else {
    // FI: I do not think we want this warning in general!
    pips_user_warning("Function \"%s\" has no side effect on its formal context "
                      "via pointer variables.\n", entity_user_name(f));
  }
 
  /* This cannot be performed earlier because the points-to
     precondition of the caller may have to be enriched according to
     the formal context of the callee, or the effect computation is
     going to fail. */
  if(out_bottom_p) {
    clear_pt_map(pt_end_f);
    points_to_graph_bottom(pt_end_f) = true;
  }
 
  return pt_end_f;
}

References add_implicitly_killed_arcs_to_kill_set(), aliased_translation_p(), call_arguments, call_function, certainly_written_pointers_set(), clear_pt_map, code_declarations, compute_points_to_binded_set(), compute_points_to_gen_set(), compute_points_to_kill_set(), consistent_points_to_set(), consistent_pt_map_p, db_get_memory_resource(), ENDP, entity_initial, entity_user_name(), f(), filter_formal_out_context_according_to_formal_in_context(), gen_full_copy_list(), ifdebug, load_body_effects(), lower_points_to_approximations_according_to_write_effects(), module_local_name(), new_filter_formal_context_according_to_actual_context(), new_simple_pt_map, NIL, pips_assert, pips_internal_error, pips_user_warning, points_to_cells_exact_translation(), points_to_cells_parameters(), points_to_cells_translation(), points_to_context_statement_in(), points_to_context_statement_line_number(), points_to_graph_bottom, points_to_graph_set, points_to_list_bottom, points_to_list_list, points_to_set_to_module_stub_cell_list(), points_to_translation_of_formal_parameters(), print_points_to_set(), set_assign_list(), set_difference(), set_undefined_p, set_union(), user_call_to_points_to_intraprocedural(), value_code, and written_pointers_set().

Referenced by user_call_to_points_to().

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 1835 of file interprocedural.c.

{
  set binding = new_simple_pt_map();
  pips_assert("pt_caller is valid", !points_to_graph_bottom(pt_caller));
  pips_assert("pt_caller is consistent", consistent_pt_map_p(pt_caller));
  entity f = call_function(c);
  list al = call_arguments(c);
  list dl = code_declarations(value_code(entity_initial(f)));
  list fpcl = points_to_cells_parameters(dl);   
  points_to_list pts_to_in = (points_to_list)
    db_get_memory_resource(DBR_POINTS_TO_IN, module_local_name(f), true);
  list l_pt_to_in = gen_full_copy_list(points_to_list_list(pts_to_in));
  points_to_list pts_to_out = (points_to_list)
    db_get_memory_resource(DBR_POINTS_TO_OUT, module_local_name(f), true);
 
  list l_pt_to_out = gen_full_copy_list(points_to_list_list(pts_to_out));
 
  /* Not much to do if both IN and OUT are empty, except if OUT is
     bottom (see below) */
  if(!(ENDP(l_pt_to_out) && ENDP(l_pt_to_in))) {
    set pt_caller_s = points_to_graph_set(pt_caller);
    set pt_in = set_assign_list(new_simple_pt_map(), l_pt_to_in);
 
    bool success_p = false;
    set pt_binded = compute_points_to_binded_set(f, al, pt_caller_s, &success_p);
    ifdebug(8) print_points_to_set("pt_binded", pt_binded);
 
    if(success_p) {
      points_to_translation_of_formal_parameters(fpcl, al, pt_caller, binding);
      /* For the side effect on binding */
      /* set pt_in_filtered = */
      /*        filter_formal_context_according_to_actual_context(fpcl, */
      /*                                                          pt_in, */
      /*                                                          pt_binded, */
      /*                                                          binding); */
      set pt_in_filtered =
        new_filter_formal_context_according_to_actual_context(fpcl,
                                                              pt_in,
                                                              pt_binded,
                                                              binding);
      if(!set_undefined_p(pt_in_filtered))
        set_free(pt_in_filtered);
      else {
        // Part of the effects can/could be translated...
        entity m = get_current_module_entity();
        semantics_user_warning("Call site in \"%s\" incompatible with callee \"%s\".", entity_user_name(m), entity_user_name(f));
      }
    }
  }
  return binding;
}

References call_arguments, call_function, code_declarations, compute_points_to_binded_set(), consistent_pt_map_p, db_get_memory_resource(), ENDP, entity_initial, entity_user_name(), f(), gen_full_copy_list(), get_current_module_entity(), ifdebug, module_local_name(), new_filter_formal_context_according_to_actual_context(), new_simple_pt_map, pips_assert, points_to_cells_parameters(), points_to_graph_bottom, points_to_graph_set, points_to_list_list, points_to_translation_of_formal_parameters(), print_points_to_set(), semantics_user_warning, set_assign_list(), set_free(), set_undefined_p, and value_code.

Here is the call graph for this function:

user_call_to_points_to_intraprocedural()

pt_map user_call_to_points_to_intraprocedural	(	call	c,
		pt_map	pt_in,
		list el	__attribute__(unused)
	)

Definition at line 2117 of file interprocedural.c.

{
  pt_map pt_out = pt_in;
  list al = call_arguments(c);
 
  FOREACH(expression, arg, al) {
    list l_sink = expression_to_points_to_sources(arg, pt_out);
    set pt_out_s = points_to_graph_set(pt_out);
    SET_FOREACH(points_to, pts, pt_out_s) {
      FOREACH(cell, cel, l_sink) {
        cell source = points_to_source(pts);
        if(cell_equal_p(source, cel)) {
          cell sink = points_to_sink(pts);
          if(source_in_graph_p(sink, pt_out))
            remove_arcs_from_pt_map(pts, pt_out_s);
        }
      }
    }
  }
  return pt_out;
}

References call_arguments, cell_equal_p(), expression_to_points_to_sources(), FOREACH, points_to_graph_set, points_to_sink, points_to_source, remove_arcs_from_pt_map(), SET_FOREACH, and source_in_graph_p().

Referenced by user_call_to_points_to(), and user_call_to_points_to_interprocedural().

Here is the call graph for this function:

Here is the caller graph for this function:

user_call_to_points_to_sinks()

list user_call_to_points_to_sinks	(	call	c,
		type et	__attribute__(unused),
		pt_map in	__attribute__(unused),
		bool	eval_p
	)

FI: I assume we do not need the eval_p parameter here.

No, we return either the return value, or the cells pointed by the return value.

This is a very convoluted way to return the return value...

Remove all arcs related to the return value of the callee. This never happens when eval_p is false because rvptl is NIL

FI: definitely the intraprocedural version

Definition at line 150 of file interprocedural.c.

{
  bool type_sensitive_p = !get_bool_property("ALIASING_ACROSS_TYPES");
  type t = entity_basic_concrete_type(call_function(c));
  type rt = compute_basic_concrete_type(functional_result(type_functional(t)));
  entity ne = entity_undefined;
  list sinks = NIL;
  entity f = call_function(c);
  // Interprocedural version
  // Check if there is a return value at the level of POINTS TO OUT, if yes return its sink
  if(!eval_p) {
    // Return the return value
    entity rv = function_to_return_value(f);
    reference rvr = make_reference(rv, NIL);
    cell rvc = make_cell_reference(rvr);
    sinks = CONS(CELL, rvc, NIL);
  }
  else if(interprocedural_points_to_analysis_p()
     ||fast_interprocedural_points_to_analysis_p() ) {
    const char* mn = entity_local_name(f);
    // FI: Warning, they are not translated into the caller's frame...
    // FI: An up-to-date version of in should be better
    //points_to_list pts_to_out = (points_to_list)
    //db_get_memory_resource(DBR_POINTS_TO_OUT, module_local_name(f), true);
    //list l_pt_to_out = gen_full_copy_list(points_to_list_list(pts_to_out));
    //set pt_out_callee = new_simple_pt_map();
    //pt_out_callee = set_assign_list(pt_out_callee, l_pt_to_out);
    // SET_FOREACH( points_to, pt, pt_out_callee) {
    set in_s = points_to_graph_set(in);
    list rvptl = NIL;
    SET_FOREACH( points_to, pt, in_s) {
      cell s = points_to_source(pt);
      reference sr = cell_any_reference(s);
      entity se = reference_variable(sr);
      const char* sn = entity_local_name(se);
      if( strcmp(mn, sn)==0) {
        if(eval_p) {
          cell sc = copy_cell(points_to_sink(pt));
          sinks = gen_nconc(CONS(CELL, sc, NULL), sinks);
          rvptl = CONS(POINTS_TO, pt, rvptl);
        }
        else {
          /* This is a very convoluted way to return the return value... */
          cell sc = copy_cell(points_to_source(pt));
          reference scr = cell_any_reference(sc);
          free_expressions(reference_indices(scr));
          reference_indices(scr) = NIL;
          sinks = gen_nconc(CONS(CELL, sc, NULL), sinks);
        }
      }
    }
    /* Remove all arcs related to the return value of the callee. This
       never happens when eval_p is false because rvptl is NIL*/
    FOREACH(POINTS_TO, rvpt, rvptl) {
      remove_arc_from_simple_pt_map(rvpt, in_s);
    }
    gen_free_list(rvptl);
  /* FI: definitely the intraprocedural version */
  }
  else {
    if(type_sensitive_p) {
      if(eval_p) {
        type prt = ultimate_type(type_to_pointed_type(rt));
        ne = entity_all_xxx_locations_typed(ANYWHERE_LOCATION,prt);
      }
      else
        ne = entity_all_xxx_locations_typed(ANYWHERE_LOCATION,rt);
    }
    else
      ne = entity_all_xxx_locations(ANYWHERE_LOCATION);
    
    sinks = entity_to_sinks(ne);
  }
  return sinks;
}

References ANYWHERE_LOCATION, call_function, CELL, cell_any_reference(), compute_basic_concrete_type(), CONS, copy_cell(), entity_all_xxx_locations(), entity_all_xxx_locations_typed(), entity_basic_concrete_type(), entity_local_name(), entity_to_sinks(), entity_undefined, f(), fast_interprocedural_points_to_analysis_p(), FOREACH, free_expressions(), function_to_return_value(), functional_result, gen_free_list(), gen_nconc(), get_bool_property(), interprocedural_points_to_analysis_p(), make_cell_reference(), make_reference(), NIL, POINTS_TO, points_to_graph_set, points_to_sink, points_to_source, reference_indices, reference_variable, remove_arc_from_simple_pt_map, SET_FOREACH, type_functional, type_to_pointed_type(), and ultimate_type().

Referenced by call_to_points_to_sinks().

Here is the call graph for this function:

Here is the caller graph for this function:

written_pointers_set()

list written_pointers_set

(

list

eff

)

Filter out written effects on pointers.

Parameters

eff

ff

Definition at line 2609 of file interprocedural.c.

                                    {
  return generic_written_pointers_set(eff, false);
}

References generic_written_pointers_set().

Referenced by user_call_to_points_to_fast_interprocedural(), and user_call_to_points_to_interprocedural().

Here is the call graph for this function:

Here is the caller graph for this function: