constant-path-utils.c File Reference

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

Include dependency graph for constant-path-utils.c:

Go to the source code of this file.

Functions
cell	make_nowhere_cell ()
	This file contains all the operators defining constant paths : More...
cell	make_typed_nowhere_cell (type t)
cell	cell_to_nowhere_sink (cell source)
	assuming source is a reference to a pointer, build the corresponding sink when the pointer is not initialized, i.e. More...
set	points_to_anywhere_typed (list lhs_list, set input)
	Already exists in points_to_general_algorithm.c, to be removed later... More...
set	points_to_anywhere (list lhs_list, set input)
list	array_to_constant_paths (expression e, set in __attribute__((__unused__)))
	input : expression e and a set of points_to output : a set of constant paths translates an expression into a set of constant paths by first changing operators like . More...
cell	max_module (cell m1, cell m2)
	we define operator max fot the lattice Module which has any_module as top and a bottom which is not yet clearly defined (maybe no_module) max_module : Module * Module -> Module Side effects on m1 if we have an anywhere location to return. More...
bool	entity_any_module_p (entity e)
	operator kill for the dimension Module: More...
bool	opkill_may_module (cell m1, cell m2)
bool	opkill_must_module (cell m1, cell m2)
cell	op_gen_module (cell m1, __attribute__((__unused__)) cell m2)
	Operator gen for modules: m1 is the sink, m2 the source (m2 points to m1) opkill_gen_module : Module * Module -> Module. More...
bool	opkill_may_name (cell n1, cell n2)
	We define operators for the lattice Name which can be a: -variable of a the program -malloc -NULL /0 -STATIC/STACK/DYNAMIC/HEAP/FORMAL -nowhere/anywhere. More...
bool	opkill_must_name (cell n1, cell n2)
type	max_type (type t1, type t2)
bool	opkill_may_type (type t1, type t2)
bool	opkill_must_type (type t1, type t2)
	opkill_must_type is the same as op_kill_may_type... More...
type	opgen_may_type (type t1, type t2)
type	opgen_must_type (type t1, type t2)
	the same as opgen_may_type More...
bool	opkill_may_reference (cell c1, cell c2)
bool	opkill_must_reference (cell c1, cell c2)
bool	opkill_may_vreference (cell c1, cell c2)
	FI: really weird and unefficient. More...
bool	opkill_must_vreference (cell c1, cell c2)
	returns true if c2 must kills c1 because of the subscript expressions More...
bool	opkill_may_constant_path (cell c1, cell c2)
bool	opkill_must_constant_path (cell c1, cell c2)
	returns true if c2 kills c1 More...
set	kill_may_set (list L, set in_may)
	Compute the set of arcs in the input points-to relation "in" whose approximation must be changed from "exact" to "may". More...
set	kill_must_set (list L, set in)
	Generate the subset of arcs that must be removed from the points-to graph "in". More...
set	points_to_may_filter (set in)
	returns a set which contains all the MAY points to More...
set	points_to_must_filter (set in)
	returns a set which contains all the EXACT points to More...
bool	address_of_expression_p (expression e)
	shoud be moved to expression.c More...
bool	subscript_expression_p (expression e)
set	gen_may_set (list L, list R, set in_may, bool *address_of_p)
	Should be moved to anywhere_abstract_locations.c. More...
set	gen_must_set (list L, list R, set in_must, bool *address_of_p)
bool	unique_location_cell_p (cell c)
	Does cell "c" represent a unique memory location or a set of memory locations? More...
set	gen_may_constant_paths (cell l, list R, set in_may, bool *address_of_p, int Lc)
set	gen_must_constant_paths (cell l, list R, set in_must, bool *address_of_p, int Lc)
	Build a set of arcs from cell l towards cells in list R if *address_p is true, or towards cells pointed by cells in list R if not. More...
points_to	opgen_may_constant_path (cell l __attribute__((__unused__)), cell r __attribute__((__unused__)))
points_to	opgen_must_constant_path (cell l __attribute__((__unused__)), cell r __attribute__((__unused__)))
bool	opgen_may_module (entity e1, entity e2)
bool	opgen_must_module (entity e1, entity e2)
bool	opgen_may_name (entity e1, entity e2)
bool	opgen_must_name (entity e1, entity e2)
bool	opgen_may_vreference (list vr1, list vr2)
bool	atomic_constant_path_p (cell cp)
	Could be replaced by abstract_location_p() but this later don't take into account the null location. More...
set	opgen_null_location (set L, cell r)
set	points_to_independent_store (set s)
bool	equal_must_vreference (cell c1, cell c2)
set	points_to_nowhere (list lhs_list, set input)
	arg1: list of cells arg2: set of points-to Create a points-to set with elements of lhs_list as source and NOWHERE as sink. More...

Function Documentation

address_of_expression_p()

bool address_of_expression_p

(

expression

e

)

shoud be moved to expression.c

Definition at line 741 of file constant-path-utils.c.

{
  bool address_of_p = false;
  syntax s = expression_syntax(e);
  if (syntax_call_p(s)) {
    if (entity_an_operator_p(call_function(syntax_call(s)), ADDRESS_OF))
       address_of_p = true;
  }
    return address_of_p;
}

References call_function, entity_an_operator_p, expression_syntax, syntax_call, and syntax_call_p.

array_to_constant_paths()

list array_to_constant_paths	(	expression	e,
		set in	__attribute__(__unused__)
	)

input : expression e and a set of points_to output : a set of constant paths translates an expression into a set of constant paths by first changing operators like .

and -> into p[0](get_memory_path()). Then evaluate this path by using points_toÚrelations already computed (eval_cell_with_points_to()). Finaly construct a set of constant paths according to the list returned by eval_cell_with_points_to().

Definition at line 176 of file constant-path-utils.c.

{
  list l = NIL;
  bool changed = false;
  //effect ef = effect_undefined;
  //reference r = reference_undefined;
  cell c = cell_undefined;
  cell c_new = cell_undefined;
  //int i;
  reference er = expression_reference(e);
  set_methods_for_proper_simple_effects();
  if(array_reference_p(er)) {
    c = make_cell_reference(er);
    c_new = simple_cell_to_store_independent_cell(c, &changed);
  }
  else {
    c_new = make_cell_reference(er);
  }
  generic_effects_reset_all_methods();
  l = CONS(CELL, c_new, NIL);
 
  return l;
}

References array_reference_p(), CELL, cell_undefined, CONS, expression_reference(), generic_effects_reset_all_methods(), make_cell_reference(), NIL, set_methods_for_proper_simple_effects(), and simple_cell_to_store_independent_cell().

Here is the call graph for this function:

atomic_constant_path_p()

bool atomic_constant_path_p

(

cell

cp

)

Could be replaced by abstract_location_p() but this later don't take into account the null location.

Parameters

cp

p

Definition at line 1243 of file constant-path-utils.c.

{
  bool atomic_cp_p = true;
  reference r = cell_any_reference(cp);
  entity e = reference_variable(r);
 
  if(entity_abstract_location_p(e)|| entity_null_locations_p(e))
    atomic_cp_p = false;
  return atomic_cp_p;
}

References cell_any_reference(), cp, entity_abstract_location_p(), entity_null_locations_p(), and reference_variable.

Here is the call graph for this function:

cell_to_nowhere_sink()

cell cell_to_nowhere_sink

(

cell

source

)

assuming source is a reference to a pointer, build the corresponding sink when the pointer is not initialized, i.e.

is undefined.

Parameters

source

ource

Definition at line 55 of file constant-path-utils.c.

{
  bool type_sensitive_p = !get_bool_property("ALIASING_ACROSS_TYPES");
  cell sink = cell_undefined;
  if(type_sensitive_p) {
    // FI: let's hope we create neither sharing nor memory leak
    bool to_be_freed_p = true;
    type t = type_to_pointed_type(cell_to_type(source, &to_be_freed_p));
    sink = make_typed_nowhere_cell(copy_type(t));
    if(to_be_freed_p) free_type(t);
  }
  else
    sink = make_nowhere_cell();
  return sink;
}

References cell_to_type(), cell_undefined, copy_type(), free_type(), get_bool_property(), make_nowhere_cell(), make_typed_nowhere_cell(), and type_to_pointed_type().

Referenced by declaration_statement_to_points_to(), malloc_to_points_to_sinks(), and user_call_to_points_to_fast_interprocedural().

Here is the call graph for this function:

Here is the caller graph for this function:

entity_any_module_p()

bool entity_any_module_p

(

entity

e

)

operator kill for the dimension Module:

• modules should be different from any_module otherwise we return false
• when modules are different from any_module we test the equality of their names opkill_may_module : Module * Module -> Bool opkill_must_module : Module * Module -> Bool test if a module is the any_module location, to be moved to anywhere_abstract_locations.c later...

Definition at line 234 of file constant-path-utils.c.

{
  bool any_module_p;
  any_module_p =  same_string_p(entity_module_name(e), ANY_MODULE_NAME);
 
  return any_module_p;
}

References ANY_MODULE_NAME, entity_module_name(), and same_string_p.

Referenced by opgen_may_module(), opgen_must_module(), opkill_may_module(), and opkill_must_module().

Here is the call graph for this function:

Here is the caller graph for this function:

equal_must_vreference()

bool equal_must_vreference	(	cell	c1,
		cell	c2
	)

Parameters

c1	1
c2	2

Definition at line 1292 of file constant-path-utils.c.

{
  int i = 0;
  bool changed = false;
  set_methods_for_proper_simple_effects();
  c1 = simple_cell_to_store_independent_cell(c1, &changed);
  c2 = simple_cell_to_store_independent_cell(c2, &changed);
  generic_effects_reset_all_methods();
  reference r1 = cell_any_reference(c1);
  reference r2 = cell_any_reference(c2);
  entity v1 = reference_variable(r1);
  entity v2 = reference_variable(r2);
  list sl1 = NIL, sl2 = NIL;
  // FI: memory leak? generation of a new string?
  extern const char* entity_minimal_user_name(entity);
 
  i = strcmp(entity_minimal_user_name(v1), entity_minimal_user_name(v2));
  if (i==0) {
    sl1 = reference_indices(r1);
    sl2 = reference_indices(r2);
    if( (int)gen_length(sl1) == (int)gen_length(sl2) ) {
      for (;i==0 && !ENDP(sl1) && ! ENDP(sl2) ; POP(sl1), POP(sl2)){
        expression se1 = EXPRESSION(CAR(sl1));
        expression se2 = EXPRESSION(CAR(sl2));
        if( unbounded_expression_p(se1) ){
          i = 0;
        }
        else if (expression_constant_p(se1) && expression_constant_p(se2)){
          int i1 = expression_to_int(se1);
          int i2 = expression_to_int(se2);
          i = i2>i1? 1 : (i2<i1? -1 : 0);
          if (i==0){
            // FI: why not use expression_equal_p()? + memory leak
            string s1 = expression_to_string(se1);
            string s2 = expression_to_string(se2);
            i = strcmp(s1, s2);
          }
        }
        else {
          string s1 = expression_to_string(se1);
          string s2 = expression_to_string(se2);
          i = strcmp(s1, s2);
        }
      }
    }
    else
      i = 1;
  }
 
  return (i==0? true: false);
}

References CAR, cell_any_reference(), ENDP, entity_minimal_user_name(), EXPRESSION, expression_constant_p(), expression_to_int(), expression_to_string(), gen_length(), generic_effects_reset_all_methods(), NIL, POP, reference_indices, reference_variable, s1, set_methods_for_proper_simple_effects(), simple_cell_to_store_independent_cell(), and unbounded_expression_p().

Referenced by gen_may_constant_paths(), and gen_must_constant_paths().

Here is the call graph for this function:

Here is the caller graph for this function:

gen_may_constant_paths()

set gen_may_constant_paths	(	cell	l,
		list	R,
		set	in_may,
		bool *	address_of_p,
		int	Lc
	)

here we have x = y, then we generate (x,y1,a)|(y,y1,a) as points to relation

locations_equal_p

&& !entity_abstract_location_p(el)

Should be replaced by opgen_constant_path(l,r)

if(reference_unbounded_indices_p(ref))

a = make_approximation_may();

Make sure the types are compatible...

Parameters

in_may	n_may
address_of_p	ddress_of_p
Lc	c

Definition at line 1003 of file constant-path-utils.c.

{
  set gen_may_cps = set_generic_make(set_private, points_to_equal_p,
                                     points_to_rank);
  points_to pt = points_to_undefined;
  if(!(*address_of_p)){
    pips_internal_error("address_of_p should always be true in the new implementation/.\n");
    /* here we have x = y, then we generate (x,y1,a)|(y,y1,a) as
       points to relation */
    FOREACH(cell, r, R){
      SET_FOREACH(points_to, i, in_may){
        if (/* locations_equal_p */equal_must_vreference(r, points_to_source(i)) /* &&  !entity_abstract_location_p(el) */ ){
          cell nl = copy_cell(l);
          pt = make_points_to(nl,
                              copy_cell(points_to_sink(i)),
                              make_approximation_may(),
                              make_descriptor_none());
        }
        if(array_entity_p(reference_variable(cell_any_reference(r)))){
          reference ref = cell_any_reference(r);
          bool t_to_be_freed = false;
          type t = points_to_reference_to_type(ref, &t_to_be_freed);
          if(pointer_type_p(t)) {
            cell nl = copy_cell(l);
            pt = make_points_to(nl, r, make_approximation_may(), make_descriptor_none());
          }
          else {
            cell nl = copy_cell(l);
            pt = make_points_to(nl, points_to_sink(i), make_approximation_may(), make_descriptor_none());
          }
          if (t_to_be_freed) free_type(t);
        }
        if(!points_to_undefined_p(pt)) {
          set_add_element(gen_may_cps, gen_may_cps, (void*) pt);
        }
      }
    }
  }
  else {
    int Rc = (int) gen_length(R);
    FOREACH(cell, r, R){
      // FI: check the unicity of the locations
      // FI: relationship with atomic_points_to_cell_p()?
      approximation a = (Lc+Rc>2
                         || !unique_location_cell_p(l)
                         || !unique_location_cell_p(r)) ?
        make_approximation_may() : make_approximation_exact();
      /* Should be replaced by opgen_constant_path(l,r) */
      //reference ref = cell_any_reference(r);
      /* if(reference_unbounded_indices_p(ref)) */
      /*   a = make_approximation_may(); */
      cell nl = copy_cell(l);
      /* Make sure the types are compatible... */
      points_to_cell_types_compatibility(nl, r);
      pt = make_points_to(nl, copy_cell(r), a, make_descriptor_none());
      set_add_element(gen_may_cps, gen_may_cps, (void*)pt);
    }
  }
 
  return gen_may_cps;
}

References array_entity_p(), cell_any_reference(), copy_cell(), equal_must_vreference(), FOREACH, free_type(), gen_length(), int, make_approximation_exact(), make_approximation_may(), make_descriptor_none(), make_points_to(), pips_internal_error, pointer_type_p(), points_to_cell_types_compatibility(), points_to_equal_p(), points_to_rank(), points_to_reference_to_type(), points_to_sink, points_to_source, points_to_undefined, points_to_undefined_p, ref, reference_variable, set_add_element(), SET_FOREACH, set_generic_make(), set_private, and unique_location_cell_p().

Referenced by gen_may_set().

Here is the call graph for this function:

Here is the caller graph for this function:

gen_may_set()

set gen_may_set	(	list	L,
		list	R,
		set	in_may,
		bool *	address_of_p
	)

Should be moved to anywhere_abstract_locations.c.

‍**If the source is not precisely known *‍/

It is easier not to have to maintain the consistency between gen_may1 and kill_may.

Parameters

in_may	n_may
address_of_p	ddress_of_p

Definition at line 813 of file constant-path-utils.c.

{
  set gen_may1 = set_generic_make(set_private, points_to_equal_p,
                                  points_to_rank);
  set gen_may2 = set_generic_make(set_private, points_to_equal_p,
                                  points_to_rank);
  set gen_may3 = set_generic_make(set_private, points_to_equal_p,
                                  points_to_rank);
  int len = (int) gen_length(L);
 
  //if(len > 1) {
  ///* If the source is not precisely known */
  /* It is easier not to have to maintain the consistency between
     gen_may1 and kill_may. */
  if(false) {
    FOREACH(cell, l, L) {
      SET_FOREACH(points_to, pt, in_may){
        if(approximation_exact_p(points_to_approximation(pt))) {
          //if(!atomic_points_to_cell_p(points_to_source(pt))) {
            //if(points_to_compare_cell(points_to_source(pt),l)) {
            if(cells_may_conflict_p(points_to_source(pt),l)) {
              // FI: it would be much easier/efficient to modify the approximation of pt
              // But it is incompatible with the implementation of sets...
              points_to npt = make_points_to(copy_cell(points_to_source(pt)),
                                             copy_cell(points_to_sink(pt)),
                                             make_approximation_may(),
                                             make_descriptor_none());
              set_add_element(gen_may1, gen_may1, (void*)npt);
              //set_del_element(gen_may1, gen_may1, (void*)pt);
            }
            //    }
        }
      }
    }
  }
 
  // Possibly generate an error for dereferencing an undefined pointer
  bool error_p =
    !get_bool_property("POINTS_TO_UNINITIALIZED_POINTER_DEREFERENCING");
  int lc = (int) gen_length(L);
  FOREACH(cell, l, L){
    reference lr = cell_any_reference(l);
    entity lv = reference_variable(lr);
    bool null_p = entity_null_locations_p(lv);
    bool nowhere_p = entity_typed_nowhere_locations_p(lv)
      || entity_nowhere_locations_p(lv);
    string bug = null_p? "a null" : "";
    bug = nowhere_p? "an undefined" : "";
    // Can the lhs be accessed?
    if(null_p || nowhere_p) {
      // No: two options; either a user_error() for dereferencing an
      // unitialized pointer or a conversion to anywhere, typed or not
      // FI: why be tolerant of NULL pointer dereferencing? For may information
      if(lc==1) {
        if(error_p)
          pips_user_error("Dereferencing of %s pointer.\n", bug);
        else {
          pips_user_warning("Dereferencing of %s pointer.\n", bug);
        }
      }
      else {
        pips_user_warning("Possible dereferencing of %s pointer.\n", bug);
      }
      type t = entity_type(lv);
      cell nl = make_anywhere_points_to_cell(t);
      set gen_l = gen_may_constant_paths(nl, R, in_may, address_of_p, len);
      set_union(gen_may2, gen_may2, gen_l);
    }
    else {
      // FI: memory leak due to call to call to gen_may_constant_paths()
      set gen_l = gen_may_constant_paths(l, R, in_may, address_of_p, len);
      // FI: be careful, the union does not preserve consistency because
      // the same arc may appear with different approximations
      set_union(gen_may2, gen_may2, gen_l);
      // free_set(gen_l);
    }
  }
 
  set_union(gen_may2, gen_may2, gen_may1);
  set_union(gen_may2, gen_may2, gen_may3);
 
  return gen_may2;
}

References approximation_exact_p, cell_any_reference(), cells_may_conflict_p(), copy_cell(), entity_nowhere_locations_p(), entity_null_locations_p(), entity_type, entity_typed_nowhere_locations_p(), FOREACH, gen_length(), gen_may_constant_paths(), get_bool_property(), int, make_anywhere_points_to_cell(), make_approximation_may(), make_descriptor_none(), make_points_to(), pips_user_error, pips_user_warning, points_to_approximation, points_to_equal_p(), points_to_rank(), points_to_sink, points_to_source, reference_variable, set_add_element(), SET_FOREACH, set_generic_make(), set_private, and set_union().

Referenced by list_assignment_to_points_to().

Here is the call graph for this function:

Here is the caller graph for this function:

gen_must_constant_paths()

set gen_must_constant_paths	(	cell	l,
		list	R,
		set	in_must,
		bool *	address_of_p,
		int	Lc
	)

Build a set of arcs from cell l towards cells in list R if *address_p is true, or towards cells pointed by cells in list R if not.

Approximation is must if Lc==1. Lc is the cardinal of L, a set containing l.

FI->AM: I do not understand why the cardinal of R is not used too when deciding if the approximation is may or must. I decide to change the semantics of this function although it is used by the initial analysis.

FI: since *address_of_p is not modified, I do not understand why a pointer is passed.

FI->AM: sharing of a... A new approximation must be generated for each new arc

if we have x = &y then we generate (x,y,a) as points to relation

Should be replaced by opgen_constant_path(l,r)

if(reference_unbounded_indices_p(ref))

a = make_approximation_may();

here we have x = y, then we generate (x,y1,a)|(y,y1,a) as points to relation

locations_equal_p

&& !entity_abstract_location_p(el)

if(array_entity_p(reference_variable(cell_any_reference(r)))){

reference ref = cell_any_reference(r);

expression ex = reference_to_expression(ref);

if(!expression_pointer_p(ex))

pt = make_points_to(l, r, a, make_descriptor_none());

else

pt = make_points_to(l, points_to_sink(i), a, make_descriptor_none());

}

if(!points_to_undefined_p(pt))

set_add_element(gen_must_cps, gen_must_cps, (void*) pt);

if(reference_unbounded_indices_p(ref))

a = make_approximation_may();

Parameters

in_must	n_must
address_of_p	ddress_of_p
Lc	c

Definition at line 1088 of file constant-path-utils.c.

{
  set gen_must_cps = set_generic_make(set_private, points_to_equal_p,
                                      points_to_rank);
  points_to pt = points_to_undefined;
  //approximation a = approximation_undefined;
  bool changed = false;
  int Rc = (int) gen_length(R);
 
  // Rc = 0;
  if(*address_of_p){
    /* if we have x = &y then we generate (x,y,a) as points to relation*/
    FOREACH(cell, r, R){
      /* Should be replaced by opgen_constant_path(l,r) */
      //reference ref = cell_any_reference(r);
      /* if(reference_unbounded_indices_p(ref)) */
      /*        a = make_approximation_may(); */
      approximation a = (Lc+Rc>2
                         || !unique_location_cell_p(l)
                         || !unique_location_cell_p(r))?
        make_approximation_may(): make_approximation_exact();
      pt = make_points_to(l, r, a, make_descriptor_none());
      set_add_element(gen_must_cps, gen_must_cps, (void*)pt);
    }
  }
  else {
    /* here we have x = y, then we generate (x,y1,a)|(y,y1,a) as
       points to relation */
    FOREACH(cell, r, R){
      SET_FOREACH(points_to, i, in_must) {
        if (/* locations_equal_p */equal_must_vreference(r, points_to_source(i))/*  && !entity_abstract_location_p(el) */){
          set_methods_for_proper_simple_effects();
          l = simple_cell_to_store_independent_cell(l, &changed);
          generic_effects_reset_all_methods();
          approximation a = (Lc+Rc>2)?
            make_approximation_may() : make_approximation_exact();
          pt = make_points_to(l, points_to_sink(i), a, make_descriptor_none());
 
 
          /* if(array_entity_p(reference_variable(cell_any_reference(r)))){ */
          /*   reference ref = cell_any_reference(r); */
          /*   expression ex = reference_to_expression(ref); */
 
          /*   if(!expression_pointer_p(ex)) */
          /*     pt = make_points_to(l, r, a, make_descriptor_none()); */
          /*   else */
          /*     pt = make_points_to(l, points_to_sink(i), a, make_descriptor_none()); */
          /* } */
 
          /* if(!points_to_undefined_p(pt)) */
          /*   set_add_element(gen_must_cps, gen_must_cps, (void*) pt); */
 
          if(array_entity_p(reference_variable(cell_any_reference(r)))){
            reference ref = cell_any_reference(r);
            bool t_to_be_freed = false;
            type t = points_to_reference_to_type(ref, &t_to_be_freed);
            /* if(reference_unbounded_indices_p(ref)) */
            /*   a = make_approximation_may(); */
            if(!pointer_type_p(t))
              pt = make_points_to(l, r, a, make_descriptor_none());
            else
              pt = make_points_to(l, points_to_sink(i), a, make_descriptor_none());
 
            if (t_to_be_freed) free_type(t);
          }
          if(!points_to_undefined_p(pt))
            set_add_element(gen_must_cps, gen_must_cps, (void*) pt);
        }
      }
    }
  }
  
  return gen_must_cps;
}

References array_entity_p(), cell_any_reference(), equal_must_vreference(), FOREACH, free_type(), gen_length(), generic_effects_reset_all_methods(), int, make_approximation_exact(), make_approximation_may(), make_descriptor_none(), make_points_to(), pointer_type_p(), points_to_equal_p(), points_to_rank(), points_to_reference_to_type(), points_to_sink, points_to_source, points_to_undefined, points_to_undefined_p, ref, reference_variable, set_add_element(), SET_FOREACH, set_generic_make(), set_methods_for_proper_simple_effects(), set_private, simple_cell_to_store_independent_cell(), and unique_location_cell_p().

Referenced by gen_must_set().

Here is the call graph for this function:

Here is the caller graph for this function:

gen_must_set()

set gen_must_set	(	list	L,
		list	R,
		set	in_must,
		bool *	address_of_p
	)

if len > 1 we must iterate over in_must and change all points-to relations having L as lhs into may relations

Parameters

in_must	n_must
address_of_p	ddress_of_p

Definition at line 908 of file constant-path-utils.c.

{
  set gen_must1 = set_generic_make(set_private, points_to_equal_p,
                                   points_to_rank);
  set gen_must2 = set_generic_make(set_private, points_to_equal_p,
                                   points_to_rank);
  int len = (int) gen_length(L);
 
  /* if len > 1 we must iterate over in_must and change all points-to
     relations having L as lhs into may relations */
  if(len > 1){
    FOREACH(cell, l, L){
      SET_FOREACH(points_to, pt, in_must){
        if(points_to_compare_cell(points_to_source(pt),l)){
          points_to npt = make_points_to(l, points_to_sink(pt),
                                         make_approximation_may(),
                                         make_descriptor_none());
          set_add_element(gen_must1, gen_must1, (void*)npt);
        }
      }
    }
  }
 
  bool error_p = false; // generate an error for dereferencing an undefined pointer
  int lc = (int) gen_length(L);
  FOREACH(cell, l, L){
    // Can the lhs be accessed?
    reference lr = cell_any_reference(l);
    entity lv = reference_variable(lr);
    bool null_p = entity_null_locations_p(lv);
    bool nowhere_p = entity_typed_nowhere_locations_p(lv)
      || entity_nowhere_locations_p(lv);
    string bug = null_p? "a null" : "";
    bug = nowhere_p? "an undefined" : "";
    if(null_p || nowhere_p) {
      // No: two options; either a user_error() for dereferencing an
      // unitialized pointer or a conversion to anywhere, typed or not
      if(lc==1) {
        if(error_p)
          pips_user_error("Dereferencing of %s pointer.\n", bug);
        else {
          pips_user_warning("Dereferencing of %s pointer.\n", bug);
        }
      }
      else {
        pips_user_warning("Possible dereferencing of %s pointer.\n", bug);
      }
      type t = entity_type(lv);
      cell nl = make_anywhere_points_to_cell(t);
      set must_l = gen_must_constant_paths(nl, R, in_must, address_of_p, len);
      set_union(gen_must2, gen_must2, must_l);
    }
    else {
    set must_l = gen_must_constant_paths(l, R, in_must, address_of_p, len);
    set_union(gen_must2, gen_must2, must_l);
    // FI: shouldn't must_l be freed?
    }
  }
  set_union(gen_must2, gen_must2,gen_must1);
 
  return gen_must2;
}

References cell_any_reference(), entity_nowhere_locations_p(), entity_null_locations_p(), entity_type, entity_typed_nowhere_locations_p(), FOREACH, gen_length(), gen_must_constant_paths(), int, make_anywhere_points_to_cell(), make_approximation_may(), make_descriptor_none(), make_points_to(), pips_user_error, pips_user_warning, points_to_compare_cell(), points_to_equal_p(), points_to_rank(), points_to_sink, points_to_source, reference_variable, set_add_element(), SET_FOREACH, set_generic_make(), set_private, and set_union().

Here is the call graph for this function:

kill_may_set()

set kill_may_set	(	list	L,
		set	in_may
	)

Compute the set of arcs in the input points-to relation "in" whose approximation must be changed from "exact" to "may".

This set is linked to set "gen_may1", although consistency would be easier to maintain if only "kill_may" were used to generate the new arcs...

kill_may = { pt in "in"| exact(pt) ^ \exists l in L conflict(l, source(pt))}

The restriction to !atomic does not seem useful.

Parameters

in_may

n_may

Definition at line 668 of file constant-path-utils.c.

{
  set kill_may = set_generic_make(set_private, points_to_equal_p,
                             points_to_rank);
  FOREACH(cell, l, L) {
    SET_FOREACH(points_to, pt, in_may) {
      cell pt_source = points_to_source(pt);
      if (opkill_may_constant_path(pt_source,l)) {
        points_to npt = make_points_to(pt_source,
                                       points_to_sink(pt), 
                                       make_approximation_exact(),
                                       make_descriptor_none());
        set_add_element(kill_may, kill_may, (void*)npt);
      }
    }
  }
  return kill_may;
}

References FOREACH, make_approximation_exact(), make_descriptor_none(), make_points_to(), opkill_may_constant_path(), points_to_equal_p(), points_to_rank(), points_to_sink, points_to_source, set_add_element(), SET_FOREACH, set_generic_make(), and set_private.

Referenced by list_assignment_to_points_to().

Here is the call graph for this function:

Here is the caller graph for this function:

kill_must_set()

set kill_must_set	(	list	L,
		set	in
	)

Generate the subset of arcs that must be removed from the points-to graph "in".

Set "in_must" is the subset of set "in" with exact points-to arcs only.

kill_1 = kill_must = {pt in "in" | source(pt) in L ^ |L|=1 ^ atomic(L) }

where "atomic(L)" is a short cut for "atomic(l) forall l in L"

Here, correctly, the atomicity is not checked directly, but properly, using an operator of the lattice.

Parameters

in

n

Definition at line 700 of file constant-path-utils.c.

{
  set kill_must = new_simple_pt_map();
  int nL = (int) gen_length(L);
 
  if(nL==1) {
    cell l = CELL(CAR(L));
    SET_FOREACH(points_to, s, in) {
      if(opkill_must_constant_path(points_to_source(s),l))
        set_add_element(kill_must, kill_must,(void*)s);
    }
  }
  return kill_must;
}

References CAR, CELL, gen_length(), int, new_simple_pt_map, opkill_must_constant_path(), points_to_source, set_add_element(), and SET_FOREACH.

Referenced by list_assignment_to_points_to().

Here is the call graph for this function:

Here is the caller graph for this function:

make_nowhere_cell()

cell make_nowhere_cell

(

void

)

This file contains all the operators defining constant paths :

constant-path-utils.c

CP = Mdodule * Name * Type *Vref. To calculate the lattice PC operators we define these operators first on each of its dimensions. Each dimension represents a lattice with a bottom and a top.

Definition at line 35 of file constant-path-utils.c.

{
  entity e = entity_all_xxx_locations(NOWHERE_LOCATION);
  reference r = make_reference(e, NIL);
  cell sink = make_cell_reference(r);
  return sink;
}

References entity_all_xxx_locations(), make_cell_reference(), make_reference(), NIL, and NOWHERE_LOCATION.

Referenced by cell_to_nowhere_sink(), intrinsic_call_to_points_to(), points_to_nowhere(), remove_points_to_cell(), and unary_intrinsic_call_to_points_to_sinks().

Here is the call graph for this function:

Here is the caller graph for this function:

make_typed_nowhere_cell()

cell make_typed_nowhere_cell

(

type

t

)

Definition at line 43 of file constant-path-utils.c.

{
  entity e = entity_all_xxx_locations_typed(NOWHERE_LOCATION, t);
  reference r = make_reference(e, NIL);
  cell sink = make_cell_reference(r);
  return sink;
}

References entity_all_xxx_locations_typed(), make_cell_reference(), make_reference(), NIL, and NOWHERE_LOCATION.

Referenced by cell_to_nowhere_sink(), freed_list_to_points_to(), points_to_set_block_projection(), and remove_points_to_cell().

Here is the call graph for this function:

Here is the caller graph for this function:

max_module()

cell max_module	(	cell	m1,
		cell	m2
	)

we define operator max fot the lattice Module which has any_module as top and a bottom which is not yet clearly defined (maybe no_module) max_module : Module * Module -> Module Side effects on m1 if we have an anywhere location to return.

Parameters

m1	1
m2	2

Definition at line 207 of file constant-path-utils.c.

{
  reference r1 = cell_any_reference(m1);
  reference r2 = cell_any_reference(m2);
  entity e1 = reference_variable(r1);
  entity e2 = reference_variable(r2);
 
  if (same_string_p(entity_name(e1),entity_name(e2)))
    return m1;
  else {
    e1 = entity_all_locations();
    r1 = make_reference(e1,NIL);
    m1 = make_cell_reference(r1);
  }
  return m1;
}

References cell_any_reference(), entity_all_locations(), entity_name, make_cell_reference(), make_reference(), NIL, reference_variable, and same_string_p.

Here is the call graph for this function:

max_type()

type max_type	(	type	t1,
		type	t2
	)

Parameters

t1	1
t2	2

Definition at line 411 of file constant-path-utils.c.

{
  if (!type_unknown_p(t1) && ! type_unknown_p(t2) && type_equal_p(t1,t2))
    return t1;
  else {
    type t = MakeTypeUnknown();
    return t;
  }
}

References MakeTypeUnknown(), type_equal_p(), and type_unknown_p.

Here is the call graph for this function:

op_gen_module()

cell op_gen_module	(	cell	m1,
		__attribute__((__unused__)) cell	m2
	)

Operator gen for modules: m1 is the sink, m2 the source (m2 points to m1) opkill_gen_module : Module * Module -> Module.

we return the module m1 whatever is its type (#any_module, TOP-LEVEL, any_module)

Definition at line 282 of file constant-path-utils.c.

{
  /* we return the module m1 whatever is its type (#any_module,
     TOP-LEVEL, any_module) */
  return m1;
 
}

opgen_may_constant_path()

points_to opgen_may_constant_path	(	cell l	__attribute__(__unused__),
		cell r	__attribute__(__unused__)
	)

Definition at line 1167 of file constant-path-utils.c.

{
  points_to pt = points_to_undefined;
  return pt;
}

References points_to_undefined.

opgen_may_module()

bool opgen_may_module	(	entity	e1,
		entity	e2
	)

Parameters

e1	1
e2	2

Definition at line 1179 of file constant-path-utils.c.

{
  const char* m1 = entity_module_name(e1);
  const char* m2 = entity_module_name(e2);
 
  if(entity_any_module_p(e1) ||entity_any_module_p(e2))
    return true;
  else 
    return same_string_p(m1, m2);
}

References entity_any_module_p(), entity_module_name(), and same_string_p.

Here is the call graph for this function:

opgen_may_name()

bool opgen_may_name	(	entity	e1,
		entity	e2
	)

Parameters

e1	1
e2	2

Definition at line 1201 of file constant-path-utils.c.

{
  string n1 = entity_name(e1);
  string n2 = entity_name(e2);
 
  if(entity_abstract_location_p(e1) ||entity_abstract_location_p(e2))
    return true;
  else
    return same_string_p(n1, n2);
}

References entity_abstract_location_p(), entity_name, and same_string_p.

Here is the call graph for this function:

opgen_may_type()

type opgen_may_type	(	type	t1,
		type	t2
	)

Parameters

t1	1
t2	2

Definition at line 437 of file constant-path-utils.c.

{
  if (!type_unknown_p(t1)&& ! type_unknown_p(t2))
    return t1;
  else {
    type t = MakeTypeUnknown();
    return t;
  }
}

References MakeTypeUnknown(), and type_unknown_p.

Referenced by opgen_must_type().

Here is the call graph for this function:

Here is the caller graph for this function:

opgen_may_vreference()

bool opgen_may_vreference	(	list	vr1,
		list	vr2
	)

Parameters

vr1	r1
vr2	r2

Definition at line 1223 of file constant-path-utils.c.

{
  bool gen_may_p = true;
 
  if(ENDP(vr1) || ENDP(vr2))
    return gen_may_p;
  else{
    FOREACH(expression, e, vr1){
      if(extended_integer_constant_expression_p(e)) {
        gen_may_p = false;
        break;
      }
    }
  }
 
  return gen_may_p;
}

References ENDP, extended_integer_constant_expression_p(), and FOREACH.

Here is the call graph for this function:

opgen_must_constant_path()

points_to opgen_must_constant_path	(	cell l	__attribute__(__unused__),
		cell r	__attribute__(__unused__)
	)

Definition at line 1173 of file constant-path-utils.c.

{
  points_to pt = points_to_undefined;
  return pt;
}

References points_to_undefined.

opgen_must_module()

bool opgen_must_module	(	entity	e1,
		entity	e2
	)

Parameters

e1	1
e2	2

Definition at line 1190 of file constant-path-utils.c.

{
  const char* m1 = entity_module_name(e1);
  const char* m2 = entity_module_name(e2);
 
  if(entity_any_module_p(e1) || entity_any_module_p(e2))
    return false;
  else
    return same_string_p(m1, m2);
}

References entity_any_module_p(), entity_module_name(), and same_string_p.

Here is the call graph for this function:

opgen_must_name()

bool opgen_must_name	(	entity	e1,
		entity	e2
	)

Parameters

e1	1
e2	2

Definition at line 1212 of file constant-path-utils.c.

{
  string n1 = entity_name(e1);
  string n2 = entity_name(e2);
 
  if(entity_abstract_location_p(e1) ||entity_abstract_location_p(e2))
    return false;
  else
    return same_string_p(n1, n2);
}

References entity_abstract_location_p(), entity_name, and same_string_p.

Here is the call graph for this function:

opgen_must_type()

type opgen_must_type	(	type	t1,
		type	t2
	)

the same as opgen_may_type

Parameters

t1	1
t2	2

Definition at line 448 of file constant-path-utils.c.

{
  return opgen_may_type(t1,t2);
}

References opgen_may_type().

Here is the call graph for this function:

opgen_null_location()

set opgen_null_location	(	set	L,
		cell	r
	)

Definition at line 1254 of file constant-path-utils.c.

{
set gen_null =  set_generic_make(set_private, points_to_equal_p,
                             points_to_rank);
  SET_FOREACH(cell, l, L){
    points_to pt = make_points_to(l, r, make_approximation_exact(), make_descriptor_none());
    set_add_element(gen_null, gen_null, (void*) pt);
  }
 
  return gen_null;
}

References gen_null(), make_approximation_exact(), make_descriptor_none(), make_points_to(), points_to_equal_p(), points_to_rank(), set_add_element(), SET_FOREACH, set_generic_make(), and set_private.

Here is the call graph for this function:

opkill_may_constant_path()

bool opkill_may_constant_path	(	cell	c1,
		cell	c2
	)

Parameters

c1	1
c2	2

Definition at line 601 of file constant-path-utils.c.

{
  bool kill_may_p;
  reference r1 = cell_any_reference(c1);
  reference r2 = cell_any_reference(c2);
  type t1 = type_undefined;
  type t2 = type_undefined;
  entity v1 = reference_variable(r1);
  entity v2 = reference_variable(r2);
  bool type_equal_p = true;
 
  if (! type_area_p(entity_type(v1)) && !type_area_p(entity_type(v2))){
    bool to_be_freed1, to_be_freed2;
    t1 = points_to_reference_to_type(r1,&to_be_freed1);
    t2 = points_to_reference_to_type(r2,&to_be_freed2);
    type_equal_p = opkill_may_type(t1,t2);
    if(to_be_freed1) free_type(t1);
    if(to_be_freed2) free_type(t2);
  }
  kill_may_p = opkill_may_module(c1,c2) && opkill_may_name(c1,c2) &&
    type_equal_p && opkill_may_vreference(c1,c2);
 
  return kill_may_p;
}

References cell_any_reference(), entity_type, free_type(), opkill_may_module(), opkill_may_name(), opkill_may_type(), opkill_may_vreference(), points_to_reference_to_type(), reference_variable, type_area_p, type_equal_p(), and type_undefined.

Referenced by kill_may_set().

Here is the call graph for this function:

Here is the caller graph for this function:

opkill_may_module()

bool opkill_may_module	(	cell	m1,
		cell	m2
	)

if the lhs or the rhs is a nowhere location or a null/0 value we generate a pips_user_warning

Parameters

m1	1
m2	2

Definition at line 242 of file constant-path-utils.c.

{
  reference r1 = cell_any_reference(m1);
  reference r2 = cell_any_reference(m2);
  entity e1 = reference_variable(r1);
  entity e2 = reference_variable(r2);
  bool kill_may_p;
 
  /* if the lhs or the rhs is a nowhere location or a null/0 value we
     generate a pips_user_warning */
  if (entity_any_module_p(e1) && entity_any_module_p(e2))
    kill_may_p = true;
  else
    kill_may_p = same_string_p(entity_name(e1),entity_name(e2));
 
  return kill_may_p;
}

References cell_any_reference(), entity_any_module_p(), entity_name, reference_variable, and same_string_p.

Referenced by opkill_may_constant_path().

Here is the call graph for this function:

Here is the caller graph for this function:

opkill_may_name()

bool opkill_may_name	(	cell	n1,
		cell	n2
	)

We define operators for the lattice Name which can be a: -variable of a the program -malloc -NULL /0 -STATIC/STACK/DYNAMIC/HEAP/FORMAL -nowhere/anywhere.

We define the max between 2 names according to the order established by the lattice Name, already done by entity_locations_max() but we have to add a new abstract location for Formal area opkill for the lattice Name tests if 2 names are : -variables of the program then we return the result of the comparison their names. -abstract locations so we return FALSE. Name * Name-> Bool

if(entity_malloc_p(e2)) kill_may_p = false// function entity_malloc_p() have to be defined and different from entity_heap_location_p()

if(entity_malloc_p(e1)) kill_may_p = true// function entity_malloc_p() have to be defined and different from entity_heap_location_p()

Parameters

n1	1
n2	2

Definition at line 310 of file constant-path-utils.c.

{
 reference r1 = cell_any_reference(n1);
 reference r2 = cell_any_reference(n2);
 entity e1 = reference_variable(r1);
 entity e2 = reference_variable(r2);
 bool kill_may_p;
 
  if (entity_nowhere_locations_p(e1)||entity_nowhere_locations_p(e2)||
     entity_null_locations_p(e1) || entity_null_locations_p(e2))
    pips_user_error("NULL or ANYWHERE locations can't appear as an lvalue\n");
 
 if (entity_abstract_location_p(e2)) {
   if (entity_all_locations_p(e2))
     kill_may_p = true;
   if (entity_abstract_location_p(e1)) {
     if (entity_all_locations_p(e1))
       kill_may_p = true;
     else
       kill_may_p = same_string_p(entity_name(e1), entity_name(e2));
   }
   else {
       /* if(entity_malloc_p(e2)) kill_may_p = false// function
          entity_malloc_p() have to be defined and different from
          entity_heap_location_p() */
       e1 = variable_to_abstract_location(e1);
       r1 = make_reference(e1,NIL);
       n1 = make_cell_reference(r1);
       kill_may_p = opkill_may_name(n1, n2);
   }
 }
  else  if ( entity_abstract_location_p(e1) ) {
     if (entity_all_locations_p(e1))
       kill_may_p = true;
     else {
       /* if(entity_malloc_p(e1)) kill_may_p = true// function
          entity_malloc_p() have to be defined and different from
          entity_heap_location_p() */
       e2 = variable_to_abstract_location(e2);
       r2 = make_reference(e2,NIL);
       n2 = make_cell_reference(r2);
       kill_may_p = opkill_may_name(n1, n2);
     }
   }
   else
     kill_may_p = same_string_p(entity_name(e1), entity_name(e2));
 
 return kill_may_p ;
}

References cell_any_reference(), entity_abstract_location_p(), entity_all_locations_p(), entity_name, entity_nowhere_locations_p(), entity_null_locations_p(), make_cell_reference(), make_reference(), NIL, pips_user_error, reference_variable, same_string_p, and variable_to_abstract_location().

Referenced by opkill_may_constant_path(), and opkill_must_name().

Here is the call graph for this function:

Here is the caller graph for this function:

opkill_may_reference()

bool opkill_may_reference	(	cell	c1,
		cell	c2
	)

Parameters

c1	1
c2	2

Definition at line 454 of file constant-path-utils.c.

{
  reference r1 = reference_undefined;
  reference r2 = reference_undefined;
  bool kill_may_p = true;
 
  if (cell_reference_p(c1))
    r1 = cell_reference(c1);
  else
    r1 = preference_reference(cell_preference(c1));
  if (cell_reference_p(c2))
    r2 = cell_reference(c2);
  else
    r2 = preference_reference(cell_preference(c2));
 
  if (store_independent_reference_p(r1) || store_independent_reference_p(r2))
    return kill_may_p;
  else {
    kill_may_p = reference_equal_p(r1,r2);
    return kill_may_p;
      }
}

References cell_preference, cell_reference, cell_reference_p, preference_reference, reference_equal_p(), reference_undefined, and store_independent_reference_p().

Here is the call graph for this function:

opkill_may_type()

bool opkill_may_type	(	type	t1,
		type	t2
	)

Parameters

t1	1
t2	2

Definition at line 422 of file constant-path-utils.c.

{
  if (!type_unknown_p(t1) && ! type_unknown_p(t2))
    return type_equal_p(t1,t2);
  else
    return false;
 
}

References type_equal_p(), and type_unknown_p.

Referenced by opkill_may_constant_path(), and opkill_must_type().

Here is the call graph for this function:

Here is the caller graph for this function:

opkill_may_vreference()

bool opkill_may_vreference	(	cell	c1,
		cell	c2
	)

FI: really weird and unefficient.

Also I asummed that vreference was limited to the subscript list... FI->AM: to be checked wrt your dissertation.

Parameters

c1	1
c2	2

Definition at line 496 of file constant-path-utils.c.

{
  int i = 0;
  reference r1 = cell_any_reference(c1);
  reference r2 = cell_any_reference(c2);
  entity v1 = reference_variable(r1);
  entity v2 = reference_variable(r2);
  list sl1 = NIL, sl2 = NIL;
  // FI: memory leak? generation of a new string?
  extern const char* entity_minimal_user_name(entity);
 
  // FI: why not compare the entities v1==v2?
  i = strcmp(entity_minimal_user_name(v1), entity_minimal_user_name(v2));
  if ( i==0 ) {
    sl1 = reference_indices(r1);
    sl2 = reference_indices(r2);
    for (;i==0 && !ENDP(sl1) && ! ENDP(sl2) ; POP(sl1), POP(sl2)) {
      expression se1 = EXPRESSION(CAR(sl1));
      expression se2 = EXPRESSION(CAR(sl2));
      if (unbounded_expression_p(se2) && expression_constant_p(se1))
        i = 0;
      else if (unbounded_expression_p(se1) && expression_constant_p(se2))
        i = 0;
      else if (expression_constant_p(se1) && expression_constant_p(se2) ) {
        int i1 = expression_to_int(se1);
        int i2 = expression_to_int(se2);
        i = i2>i1? 1 : (i2<i1? -1 : 0);
 
        // FI: this piece of code seems out of place, if i==0, i==0
        if ( i==0 ) {
          string s1 = expression_to_string(se1);
          string s2 = expression_to_string(se2);
          i = strcmp(s1, s2);
        }
      }
      else if(field_expression_p(se1) && field_expression_p(se2))
        i = expression_equal_p(se1,se2)? 0 : 1;
    }
  }
 
  return (i==0? true: false);
}

References CAR, cell_any_reference(), ENDP, entity_minimal_user_name(), EXPRESSION, expression_constant_p(), expression_equal_p(), expression_to_int(), expression_to_string(), field_expression_p(), NIL, POP, reference_indices, reference_variable, s1, and unbounded_expression_p().

Referenced by opkill_may_constant_path().

Here is the call graph for this function:

Here is the caller graph for this function:

opkill_must_constant_path()

bool opkill_must_constant_path	(	cell	c1,
		cell	c2
	)

returns true if c2 kills c1

if (! type_area_p(entity_type(v1)) && !type_area_p(entity_type(v2))){

if (entity_abstract_location_p(v1))

t1 = entity_type(v1);

else

t1 = simple_effect_reference_type(r1);

if (entity_abstract_location_p(v2))

t2 = entity_type(v2);

else

t2 = simple_effect_reference_type(r2);

type_equal_p = opkill_must_type(t1,t2);

}

Parameters

c1	1
c2	2

Definition at line 627 of file constant-path-utils.c.

{
  bool kill_must_p;
  reference r1 = cell_any_reference(c1);
  reference r2 = cell_any_reference(c2);
  type t1 = type_undefined;
  type t2 = type_undefined;
  //entity v1 = reference_variable(r1);
  //entity v2 = reference_variable(r2);
  bool equal_p = true;
  t1 = points_to_reference_to_type(r1,&equal_p);
  t2 = points_to_reference_to_type(r2, &equal_p);
  equal_p = type_equal_p(t1,t2);
  /* if (! type_area_p(entity_type(v1)) && !type_area_p(entity_type(v2))){ */
  /*   if (entity_abstract_location_p(v1)) */
  /*     t1 = entity_type(v1); */
  /*   else */
  /*     t1 = simple_effect_reference_type(r1); */
  /*   if (entity_abstract_location_p(v2)) */
  /*     t2 = entity_type(v2); */
  /*   else */
  /*     t2 = simple_effect_reference_type(r2); */
  /*   type_equal_p = opkill_must_type(t1,t2); */
  /* } */
  kill_must_p = opkill_must_module(c1,c2) && opkill_must_name(c1,c2) &&
    equal_p && opkill_must_vreference(c1,c2);
 
   return kill_must_p;
}

References cell_any_reference(), opkill_must_module(), opkill_must_name(), opkill_must_vreference(), points_to_reference_to_type(), type_equal_p(), and type_undefined.

Referenced by kill_must_set().

Here is the call graph for this function:

Here is the caller graph for this function:

opkill_must_module()

bool opkill_must_module	(	cell	m1,
		cell	m2
	)

Parameters

m1	1
m2	2

Definition at line 260 of file constant-path-utils.c.

{
  reference r1 = cell_any_reference(m1);
  reference r2 = cell_any_reference(m2);
  entity e1 = reference_variable(r1);
  entity e2 = reference_variable(r2);
  bool kill_must_p;
 
  if (entity_any_module_p(e1) && entity_any_module_p(e2))
    kill_must_p = false;
  else
    kill_must_p = same_string_p(entity_name(e1),entity_name(e2));
 
  return kill_must_p;
}

References cell_any_reference(), entity_any_module_p(), entity_name, reference_variable, and same_string_p.

Referenced by opkill_must_constant_path().

Here is the call graph for this function:

Here is the caller graph for this function:

opkill_must_name()

bool opkill_must_name	(	cell	n1,
		cell	n2
	)

if(entity_malloc_p(e2)) kill_may_p = false// function entity_malloc_p() have to be defined and different from entity_heap_location_p()

if(entity_malloc_p(e1)) kill_may_p = true// function entity_malloc_p() have to be defined and different from entity_heap_location_p()

Parameters

n1	1
n2	2

Definition at line 361 of file constant-path-utils.c.

{
 reference r1 = cell_any_reference(n1);
 reference r2 = cell_any_reference(n2);
 entity e1 = reference_variable(r1);
 entity e2 = reference_variable(r2);
 bool kill_must_p;
 
 if (entity_nowhere_locations_p(e1)||entity_nowhere_locations_p(e2)||
     entity_null_locations_p(e1) || entity_null_locations_p(e2))
    pips_user_error("NULL or ANYWHERE locations can't appear as an lvalue\n");
 
 if (entity_abstract_location_p(e2)) {
   if (entity_all_locations_p(e2))
     kill_must_p = false;
   if (entity_abstract_location_p(e1)) {
     if(entity_all_locations_p(e1))
       kill_must_p = false;
     else
         kill_must_p = same_string_p(entity_name(e1), entity_name(e2));
   }
   else {
     /* if(entity_malloc_p(e2)) kill_may_p = false// function
        entity_malloc_p() have to be defined and different from
        entity_heap_location_p() */
     e1 = variable_to_abstract_location(e1);
     r1 = make_reference(e1,NIL);
     n1 = make_cell_reference(r1);
     kill_must_p = opkill_may_name(n1, n2);
   }
 }
  else if ( entity_abstract_location_p(e1) ) {
     if (entity_all_locations_p(e1))
       kill_must_p = false;
     else {
       /* if(entity_malloc_p(e1)) kill_may_p = true// function
          entity_malloc_p() have to be defined and different from
          entity_heap_location_p() */
       e2 = variable_to_abstract_location(e2);
       r2 = make_reference(e2,NIL);
       n2 = make_cell_reference(r2);
       kill_must_p = opkill_may_name(n1, n2);
     }
   }
   else
     kill_must_p = same_string_p(entity_name(e1), entity_name(e2));
 
 return kill_must_p ;
}

References cell_any_reference(), entity_abstract_location_p(), entity_all_locations_p(), entity_name, entity_nowhere_locations_p(), entity_null_locations_p(), make_cell_reference(), make_reference(), NIL, opkill_may_name(), pips_user_error, reference_variable, same_string_p, and variable_to_abstract_location().

Referenced by opkill_must_constant_path().

Here is the call graph for this function:

Here is the caller graph for this function:

opkill_must_reference()

bool opkill_must_reference	(	cell	c1,
		cell	c2
	)

Parameters

c1	1
c2	2

Definition at line 478 of file constant-path-utils.c.

{
  reference r1 = cell_any_reference(c1);
  reference r2 = cell_any_reference(c2);
  bool kill_must_p = false;
 
  if (store_independent_reference_p(r1) || store_independent_reference_p(r2))
    return kill_must_p;
  else {
    kill_must_p = reference_equal_p(r1,r2);
    return kill_must_p;
      }
}

References cell_any_reference(), reference_equal_p(), and store_independent_reference_p().

Here is the call graph for this function:

opkill_must_type()

bool opkill_must_type	(	type	t1,
		type	t2
	)

opkill_must_type is the same as op_kill_may_type...

Parameters

t1	1
t2	2

Definition at line 432 of file constant-path-utils.c.

{
  return opkill_may_type(t1,t2);
}

References opkill_may_type().

Here is the call graph for this function:

opkill_must_vreference()

bool opkill_must_vreference	(	cell	c1,
		cell	c2
	)

returns true if c2 must kills c1 because of the subscript expressions

This function should be rewritten from scratch, with a defined semantics for "*" as a subscript and possibly a larger use of expression_equal_p(). Also, we need to specify if the scopes for each rereference are equal or not.

Parameters

c1	1
c2	2

Definition at line 546 of file constant-path-utils.c.

{
  int i = 0;
  reference r1 = cell_any_reference(c1);
  reference r2 = cell_any_reference(c2);
  entity v1 = reference_variable(r1);
  entity v2 = reference_variable(r2);
  list sl1 = NIL, sl2 = NIL;
  // FI: memory leak? generation of a new string?
  extern const char* entity_minimal_user_name(entity);
 
  // FI: this step could be assumed performed earlier
  i = strcmp(entity_minimal_user_name(v1), entity_minimal_user_name(v2));
  if (i==0) {
    sl1 = reference_indices(r1);
    sl2 = reference_indices(r2);
    for (;i==0 && !ENDP(sl1) && ! ENDP(sl2) ; POP(sl1), POP(sl2)){
      expression se1 = EXPRESSION(CAR(sl1));
      expression se2 = EXPRESSION(CAR(sl2));
      if(expression_constant_p(se2) && unbounded_expression_p(se1)){
        //i = 0;
        i = 1;
      }
      else if(expression_constant_p(se1) && unbounded_expression_p(se2)){
        //i = 0; could be true if * is interpreted as "forall"
        i = 1;
      }
      else if (expression_constant_p(se1) && expression_constant_p(se2)){
        int i1 = expression_to_int(se1);
        int i2 = expression_to_int(se2);
        i = i2>i1? 1 : (i2<i1? -1 : 0);
        if (i==0){ // FI->AM: I do not understand this step
          string s1 = expression_to_string(se1);
          string s2 = expression_to_string(se2);
          i = strcmp(s1, s2);
        }
      }
      else {
        // FI->AM: very dangerous; only true if both references appear
        // exactly in the same scope; and "*" were not dealt with!
        if(unbounded_expression_p(se1)||unbounded_expression_p(se2))
          i = 1;
        else {
          i = expression_equal_p(se1, se2)? 0 : 1;
        }
      }
    }
  }
 
  return (i==0? true: false);
}

References CAR, cell_any_reference(), ENDP, entity_minimal_user_name(), EXPRESSION, expression_constant_p(), expression_equal_p(), expression_to_int(), expression_to_string(), NIL, POP, reference_indices, reference_variable, s1, and unbounded_expression_p().

Referenced by opkill_must_constant_path().

Here is the call graph for this function:

Here is the caller graph for this function:

points_to_anywhere()

set points_to_anywhere	(	list	lhs_list,
		set	input
	)

lhs_path matches the kill set.

input - kill

if the lhs_set or the rhs set contains more than an element, we set the approximation to MAY.

Computing the gen set

create a new points to with as source the current element of lhs_set and sink the null value .

gen + input_kill_diff

Parameters

lhs_list	hs_list
input	nput

Definition at line 122 of file constant-path-utils.c.

{
  /* lhs_path matches the kill set.*/
  set kill= set_generic_make(set_private, points_to_equal_p,
                             points_to_rank);
  set gen = set_generic_make(set_private, points_to_equal_p,
                             points_to_rank);
  set res = set_generic_make(set_private, points_to_equal_p,
                             points_to_rank);
  set input_kill_diff = set_generic_make(set_private, points_to_equal_p,
                                         points_to_rank);
  approximation a = make_approximation_exact();
 
  SET_FOREACH ( points_to, p, input ) {
    FOREACH ( cell, c, lhs_list ) {
      if ( points_to_compare_cell(points_to_source(p), c) )
        set_add_element(kill, kill, p);
    }
  }
 
  /* input - kill */
  set_difference(input_kill_diff, input, kill);
 
  /* if the lhs_set or the rhs set contains more than an element, we
     set the approximation to MAY. */
  if ( (int)gen_length(lhs_list) > 1 )// || set_size(rhs_set)>1)
    a = make_approximation_may();
 
  /* Computing the gen set*/
  FOREACH ( cell, c, lhs_list ) {
    /* create a new points to with as source the current
       element of lhs_set and sink the null value .*/
    entity e = entity_all_xxx_locations(ANYWHERE_LOCATION);
    reference r = make_reference(e, NIL);
    cell sink = make_cell_reference(r);
    points_to pt_to = make_points_to(c, sink, a, make_descriptor_none());
    set_add_element(gen, gen, (void*)pt_to);
  }
  /* gen + input_kill_diff*/
  set_union(res, gen, input_kill_diff);
 
  return res;
}

References ANYWHERE_LOCATION, entity_all_xxx_locations(), FOREACH, gen(), gen_length(), input(), make_approximation_exact(), make_approximation_may(), make_cell_reference(), make_descriptor_none(), make_points_to(), make_reference(), NIL, points_to_compare_cell(), points_to_equal_p(), points_to_rank(), points_to_source, set_add_element(), set_difference(), SET_FOREACH, set_generic_make(), set_private, and set_union().

Referenced by list_assignment_to_points_to().

Here is the call graph for this function:

Here is the caller graph for this function:

points_to_anywhere_typed()

set points_to_anywhere_typed	(	list	lhs_list,
		set	input
	)

Already exists in points_to_general_algorithm.c, to be removed later...

iterate over the lhs_set, if it contains more than an element approximations are set to MAY, otherwise it's set to EXACT Set the sink to anywhere .

input - kill

if the lhs_set or the rhs set contains more than an element, we set the approximation to MAY.

Computing the gen set

create a new points to with as source the current element of lhs_set and sink the null value .

Parameters

lhs_list	hs_list
input	nput

Definition at line 75 of file constant-path-utils.c.

{
  set kill= set_generic_make(set_private, points_to_equal_p,
                                    points_to_rank);
  set gen = set_generic_make(set_private, points_to_equal_p,
                                    points_to_rank);
  set res = set_generic_make(set_private, points_to_equal_p,
                                    points_to_rank);
  set input_kill_diff = set_generic_make(set_private, points_to_equal_p,
                           points_to_rank);
  approximation a = make_approximation_exact();
 
  SET_FOREACH(points_to, p, input) {
      FOREACH(cell, c, lhs_list) {
        if(points_to_compare_cell(points_to_source(p), c))
            set_add_element(kill, kill, p);
        }
    }
 
  /* input - kill */
  set_difference(input_kill_diff, input, kill);
 
  /* if the lhs_set or the rhs set contains more than an element, we
     set the approximation to MAY. */
  if((int)gen_length(lhs_list) > 1)// || set_size(rhs_set)>1)
    a = make_approximation_may();
 
  /* Computing the gen set*/
  FOREACH(cell, c, lhs_list) {
      /* create a new points to with as source the current
         element of lhs_set and sink the null value .*/
    reference cr = cell_any_reference(c);
    entity er = reference_variable(cr);
    type t = entity_type(er);
    entity e = entity_all_xxx_locations_typed(ANYWHERE_LOCATION,t);
    reference r = make_reference(e, NIL);
    cell sink = make_cell_reference(r);
    points_to pt_to = make_points_to(c, sink, a, make_descriptor_none());
    set_add_element(gen, gen, (void*)pt_to);
    }
 
  set_union(res, gen, input_kill_diff);
 
  return res;
}

References ANYWHERE_LOCATION, cell_any_reference(), entity_all_xxx_locations_typed(), entity_type, FOREACH, gen(), gen_length(), input(), make_approximation_exact(), make_approximation_may(), make_cell_reference(), make_descriptor_none(), make_points_to(), make_reference(), NIL, points_to_compare_cell(), points_to_equal_p(), points_to_rank(), points_to_source, reference_variable, set_add_element(), set_difference(), SET_FOREACH, set_generic_make(), set_private, and set_union().

Referenced by list_assignment_to_points_to().

Here is the call graph for this function:

Here is the caller graph for this function:

points_to_independent_store()

set points_to_independent_store

(

set

s

)

Definition at line 1273 of file constant-path-utils.c.

{
  set res =  set_generic_make(set_private, points_to_equal_p,
                              points_to_rank);
  bool changed = false;
 
  SET_FOREACH(points_to, pt, s){
    cell source = points_to_source(pt);
    cell sink = points_to_sink(pt);
    cell new_source = simple_cell_to_store_independent_cell(source, &changed);
    cell new_sink =  simple_cell_to_store_independent_cell(sink, &changed);
    points_to npt = make_points_to(new_source, new_sink, points_to_approximation(pt),points_to_descriptor(pt));
    set_add_element(res, res, (void*) npt);
  }
 
  return res;
}

References make_points_to(), points_to_approximation, points_to_descriptor, points_to_equal_p(), points_to_rank(), points_to_sink, points_to_source, set_add_element(), SET_FOREACH, set_generic_make(), set_private, and simple_cell_to_store_independent_cell().

Referenced by any_loop_to_points_to(), and new_any_loop_to_points_to().

Here is the call graph for this function:

Here is the caller graph for this function:

points_to_may_filter()

set points_to_may_filter

(

set

in

)

returns a set which contains all the MAY points to

Parameters

in

n

Definition at line 716 of file constant-path-utils.c.

{
  set in_may = set_generic_make(set_private, points_to_equal_p,
                             points_to_rank);
 
  SET_FOREACH(points_to, pt, in){
    if (approximation_may_p(points_to_approximation(pt)))
      set_add_element(in_may, in_may, (void*)pt);
  }
  return in_may;
}

References approximation_may_p, points_to_approximation, points_to_equal_p(), points_to_rank(), set_add_element(), SET_FOREACH, set_generic_make(), and set_private.

Referenced by list_assignment_to_points_to().

Here is the call graph for this function:

Here is the caller graph for this function:

points_to_must_filter()

set points_to_must_filter

(

set

in

)

returns a set which contains all the EXACT points to

Parameters

in

n

Definition at line 729 of file constant-path-utils.c.

{
  set in_must = set_generic_make(set_private, points_to_equal_p,
                             points_to_rank);
  SET_FOREACH(points_to, pt, in){
    if (approximation_exact_p(points_to_approximation(pt)))
      set_add_element(in_must, in_must, (void*)pt);
  }
  return in_must;
}

References approximation_exact_p, points_to_approximation, points_to_equal_p(), points_to_rank(), set_add_element(), SET_FOREACH, set_generic_make(), and set_private.

Referenced by list_assignment_to_points_to().

Here is the call graph for this function:

Here is the caller graph for this function:

points_to_nowhere()

set points_to_nowhere	(	list	lhs_list,
		set	input
	)

arg1: list of cells arg2: set of points-to Create a points-to set with elements of lhs_list as source and NOWHERE as sink.

Iterate over input and kill all points-to relations where sinks are elements of lhs_list.

if the lhs_set or the rhs set contains more than an element, we set the approximation to MAY.

Computing the gen set

Parameters

lhs_list	hs_list
input	nput

Definition at line 1351 of file constant-path-utils.c.

{
  set kill = set_generic_make(set_private, points_to_equal_p,
                                    points_to_rank);
  set gen = set_generic_make(set_private, points_to_equal_p,
                                    points_to_rank);
  set res = set_generic_make(set_private, points_to_equal_p,
                                    points_to_rank);
  set input_kill_diff = set_generic_make(set_private, points_to_equal_p,
                           points_to_rank);
  approximation a = make_approximation_exact();
 
  SET_FOREACH(points_to, p, input) {
      FOREACH(cell, c, lhs_list) {
          if(points_to_source(p) == c)
            set_add_element(kill, kill, p);
        }
    }
  set_difference(input_kill_diff, input, kill);
  /* if the lhs_set or the rhs set contains more than an element, we
     set the approximation to MAY. */
  if((int)gen_length(lhs_list) > 1)// || set_size(rhs_set)>1)
    a = make_approximation_may();
 
  /* Computing the gen set */
  FOREACH(cell, c, lhs_list) {
    cell sink = make_nowhere_cell();
    points_to pt_to = make_points_to(c, sink, copy_approximation(a), make_descriptor_none());
    set_add_element(gen, gen, (void*)pt_to);
  }
  free_approximation(a);
  set_union(res, gen, input_kill_diff);
 
  return res;
}

References copy_approximation(), FOREACH, free_approximation(), gen(), gen_length(), input(), make_approximation_exact(), make_approximation_may(), make_descriptor_none(), make_nowhere_cell(), make_points_to(), points_to_equal_p(), points_to_rank(), points_to_source, set_add_element(), set_difference(), SET_FOREACH, set_generic_make(), set_private, and set_union().

Here is the call graph for this function:

subscript_expression_p()

bool subscript_expression_p

(

expression

e

)

Definition at line 752 of file constant-path-utils.c.

{
  return syntax_subscript_p(expression_syntax(e));
}

References expression_syntax, and syntax_subscript_p.

unique_location_cell_p()

bool unique_location_cell_p

(

cell

c

)

Does cell "c" represent a unique memory location or a set of memory locations?

This is key to decide if a points-to arc is a must or a may arc.

Is it always possible to decide when heap abstract locations are concerned?

See also cell_abstract_location_p()

Definition at line 980 of file constant-path-utils.c.

{
  bool unique_p = !anywhere_cell_p(c)
    && !cell_typed_anywhere_locations_p(c)
    // FI: typed or not?
    // FI: how do you know when heap cells are unique and when they
    // represent a set of cells?
    && !heap_cell_p(c);
 
  // FI: how do you deal with arrays of pointers?
  if(unique_p) {
    reference r = cell_any_reference(c);
    list sl = reference_indices(r);
    FOREACH(EXPRESSION, s, sl) {
      if(unbounded_expression_p(s)) {
        unique_p = false;
        break;
      }
    }
  }
  return unique_p;
}

References anywhere_cell_p(), cell_any_reference(), cell_typed_anywhere_locations_p(), EXPRESSION, FOREACH, heap_cell_p(), reference_indices, and unbounded_expression_p().

Referenced by gen_may_constant_paths(), and gen_must_constant_paths().

Here is the call graph for this function:

Here is the caller graph for this function: