dereferencing.c File Reference

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

Include dependency graph for dereferencing.c:

Go to the source code of this file.

Functions
pt_map	dereferencing_subscript_to_points_to (subscript sub, pt_map in)
	FI: As usual in dereferencing.c, it is not clear that this piece of code has not been implemented somewhere else because of the early restriction to pointer type only expressions. More...
pt_map	dereferencing_to_points_to (expression p, pt_map in)
	Make sure that expression p can be dereferenced in points-to graph "in". More...
bool	pointer_points_to_reference_p (reference r __attribute__((unused)))
	see if a points_to_reference includes a pointer dereferencing: this is impossible if the points-to reference is consistent. More...
void	pointer_reference_dereferencing_to_points_to (reference r, pt_map in)
pt_map	reference_dereferencing_to_points_to (reference r, pt_map in, bool nowhere_dereferencing_p, bool null_dereferencing_p)
	Can we execute the reference r in points-to context "in" without segfaulting? More...
bool	expression_to_points_to_cell_p (expression e)
	Can expression e be reduced to a reference, without requiring an evaluation? More...
list	dereferencing_to_sinks (expression a, pt_map in, bool eval_p)
	Returns "sinks", the list of cells pointed to by expression "a" according to points-to graph "in". More...

Function Documentation

dereferencing_subscript_to_points_to()

pt_map dereferencing_subscript_to_points_to	(	subscript	sub,
		pt_map	in
	)

FI: As usual in dereferencing.c, it is not clear that this piece of code has not been implemented somewhere else because of the early restriction to pointer type only expressions.

dereferencing.c

But all pointer values must be generated, whether they point to pointers or anything else.

This piece of code is designed to handle pointer19.c, and hence pointer14.c, where arrays of pointers toward arrays of pointers are used.

It generates too many arcs, useless arcs, when the subscript list is broken down into many subscript constructs by PIPS C parser. This shows in Pointers/pointer14, 15 and 19.

a cannot evaluate to null or undefined

FI: we may need a special case for stubs...

We have to take "sel" into account since only the base of the target array is pointed to.

We have to bother with the source if it is an array, not if it is simply a pointer dereferenced by some subscripts as in dereferencing18.c.

Look for points-to arcs that must be duplicated using the subscripts as offsets

We must generate a new source with the offset defined by sel, and a new sink, with or without a an offset

Update the source cell

Is the source cell already known in the points-to relation?

Update the sink cell if necessary

Build the new points-to arc

Do not update set "in" while you are enumerating its elements

Update sets "in" with the new arcs. The arc must pre-exist the reference for the effects to be able to translate a non-constant effect. Thus, it should pre-exist the call site.

FI: I am not sure this is useful...

Parameters

sub	ub
in	n

Definition at line 71 of file dereferencing.c.

{
  expression a = subscript_array(sub);
  type at = expression_to_type(a);
  type apt = type_to_pointed_type(at);
  list sel = subscript_indices(sub);
  /* a cannot evaluate to null or undefined */
  /* FI: we may need a special case for stubs... */
  in = dereferencing_to_points_to(a, in);
  /* We have to take "sel" into account since only the base of the
     target array is pointed to. */
  list source_l = expression_to_points_to_sources(a, in);
  list n_arc_l = NIL;
 
  FOREACH(CELL, source, source_l) {
    /* We have to bother with the source if it is an array, not if it
       is simply a pointer dereferenced by some subscripts as in
       dereferencing18.c. */
    reference source_r = cell_any_reference(source);
    entity source_v = reference_variable(source_r);
    type source_v_t =  entity_basic_concrete_type(source_v);
 
    if(array_type_p(source_v_t)) {
      /* Look for points-to arcs that must be duplicated using the
         subscripts as offsets */
      SET_FOREACH(points_to, pt, points_to_graph_set(in)) {
        cell pt_source = points_to_source(pt);
        //if(points_to_cell_in_list_p(pt_source, source_l)) {
        if(points_to_cell_equal_p(pt_source, source)) {
          /* We must generate a new source with the offset defined by sel,
             and a new sink, with or without a an offset */
          cell pt_sink = points_to_sink(pt);
          cell n_source = cell_undefined;
 
          /* Update the source cell */
          if(null_cell_p(pt_source)) {
            pips_internal_error("NULL cannot be a source cell.\n");;
          }
          else if(anywhere_cell_p(pt_source)
                  || cell_typed_anywhere_locations_p(pt_source)) {
            pips_internal_error("Not sure what should be done here!\n");
          }
          else {
            n_source = copy_cell(pt_source);
            reference n_source_r = cell_any_reference(n_source);
            if(adapt_reference_to_type(n_source_r, at,
                                       points_to_context_statement_line_number)) {
              reference_indices(n_source_r) = gen_nconc(reference_indices(n_source_r),
                                                        gen_full_copy_list(sel));
              complete_points_to_reference_with_zero_subscripts(n_source_r);
            }
            else
              pips_internal_error("No idea how to deal with this source cell.\n");
          }
 
          /* Is the source cell already known in the points-to relation? */
 
          if(!cell_undefined_p(n_source) && !source_in_pt_map_p(n_source, in)) {
            cell n_sink = copy_cell(pt_sink);
 
            /* Update the sink cell if necessary */
            if(null_cell_p(pt_sink)) {
              ;
            }
            else if(anywhere_cell_p(pt_sink)
                    || cell_typed_anywhere_locations_p(pt_sink)) {
              ;
            }
            else {
              reference n_sink_r = cell_any_reference(n_sink);
              if(adapt_reference_to_type(n_sink_r, apt,
                                         points_to_context_statement_line_number)) {
                reference_indices(n_sink_r) = gen_nconc(reference_indices(n_sink_r),
                                                        gen_full_copy_list(sel));
                complete_points_to_reference_with_zero_subscripts(n_sink_r);
              }
              else
                pips_internal_error("No idea how to deal with this sink cell.\n");
            }
 
            /* Build the new points-to arc */
            approximation ap = copy_approximation(points_to_approximation(pt));
            points_to n_pt = make_points_to(n_source, n_sink, ap,
                                            make_descriptor_none());
            /* Do not update set "in" while you are enumerating its elements */
            n_arc_l = CONS(POINTS_TO, n_pt, n_arc_l);
          }
          else
            free_cell(n_source);
        }
      }
    }
  }
 
  /* Update sets "in" with the new arcs. The arc must pre-exist the
     reference for the effects to be able to translate a non-constant
     effect. Thus, it should pre-exist the call site. */
  FOREACH(POINTS_TO, n_pt, n_arc_l) {
    add_arc_to_pt_map(n_pt, in);
    add_arc_to_statement_points_to_context(copy_points_to(n_pt));
    add_arc_to_points_to_context(copy_points_to(n_pt));
  }
  gen_free_list(n_arc_l);
 
  /* FI: I am not sure this is useful... */
  in = expression_to_points_to(a, in, false); // side effects
 
  in = expressions_to_points_to(sel, in, false);
 
  free_type(at);
  return in;
}

References adapt_reference_to_type(), add_arc_to_points_to_context(), add_arc_to_pt_map, add_arc_to_statement_points_to_context(), anywhere_cell_p(), array_type_p(), CELL, cell_any_reference(), cell_typed_anywhere_locations_p(), cell_undefined, cell_undefined_p, complete_points_to_reference_with_zero_subscripts(), CONS, copy_approximation(), copy_cell(), copy_points_to(), dereferencing_to_points_to(), entity_basic_concrete_type(), expression_to_points_to(), expression_to_points_to_sources(), expression_to_type(), expressions_to_points_to(), FOREACH, free_cell(), free_type(), gen_free_list(), gen_full_copy_list(), gen_nconc(), make_descriptor_none(), make_points_to(), NIL, null_cell_p(), pips_internal_error, POINTS_TO, points_to_approximation, points_to_cell_equal_p(), points_to_context_statement_line_number(), points_to_graph_set, points_to_sink, points_to_source, reference_indices, reference_variable, SET_FOREACH, source_in_pt_map_p, subscript_array, subscript_indices, and type_to_pointed_type().

Referenced by dereferencing_to_points_to().

Here is the call graph for this function:

Here is the caller graph for this function:

dereferencing_to_points_to()

pt_map dereferencing_to_points_to	(	expression	p,
		pt_map	in
	)

Make sure that expression p can be dereferenced in points-to graph "in".

Handling of NULL pointers according to property.

Handling of undefined pointers according to property.

"in" is modified by side effects. Arcs certainly incompatible with a dereferencing are removed. If dereferencing of p is no longer possible, return an empty points-to "in" as the expression cannot be evaluated.

This is conditional to two properties.

ut =

You must take care of s.tab, which is encoded by a call

EffectsWithPointsTo/struct08.c: ae = (e.champ)[i], fe = p

For side effects on "in"

Parameters

in

n

Definition at line 198 of file dereferencing.c.

{
  //pt_map out = in;
  bool null_dereferencing_p
    = get_bool_property("POINTS_TO_NULL_POINTER_DEREFERENCING");
  bool nowhere_dereferencing_p
    = get_bool_property("POINTS_TO_UNINITIALIZED_POINTER_DEREFERENCING");
  // FI: we cannot use expression_to_points_to_sources or sinks
  // because side effects are taken into acount each time they are
  // called.
  if(!nowhere_dereferencing_p && !null_dereferencing_p) {
    syntax s = expression_syntax(p);
    tag t = syntax_tag(s);
 
    switch(t) {
    case is_syntax_reference: {
      reference r = syntax_reference(s);
      /*out = */reference_dereferencing_to_points_to(r, in,
                                                 nowhere_dereferencing_p,
                                                 null_dereferencing_p);
      break;
    }
    case is_syntax_range: {
      //range r = syntax_range(s);
      // out = range_to_points_to(r, in);
      break;
    }
    case is_syntax_call: {
      call c = syntax_call(s);
      list al = call_arguments(c);
      
      // FI: you do not want to apply side-effects twice...
      // But you then miss the detection of pointers that are not NULL
      // because they are dereferenced and you miss the recursive descent
      //in = expressions_to_points_to(al, in, false);
      //in = call_to_points_to(c, in, el, false);
      
      /* You must take care of s.tab, which is encoded by a call */
      entity f = call_function(c);
      if(ENTITY_FIELD_P(f)) {
        expression ae = EXPRESSION(CAR(al));
        expression fe = EXPRESSION(CAR(CDR(al)));
        /* EffectsWithPointsTo/struct08.c: ae = (e.champ)[i], fe = p*/
        //pips_assert("ae and fe are references",
        //          expression_reference_p(ae) && expression_reference_p(fe));
        pips_assert("fe is a reference", expression_reference_p(fe));
        reference fr = expression_reference(fe);
        entity fv = reference_variable(fr);
        type ft = entity_basic_concrete_type(fv);
        if(pointer_type_p(ft) || struct_type_p(ft)
           || array_of_pointers_type_p(ft) 
           || array_of_struct_type_p(ft)) {
          in = dereferencing_to_points_to(ae, in);
          /* For side effects on "in" */
          list sink_l = expression_to_points_to_sinks(p, in);
          gen_free_list(sink_l);
        }
      }
      else {
        // Do not take side-effects into account or they will be applied twice
        in = expressions_to_points_to(al, in, false);
        in = call_to_points_to(c, in, NIL, false);
        list sl = expression_to_points_to_sinks(p, in);
        gen_free_list(sl);
      }
      break;
    }
    case is_syntax_cast: {
      //cast c = syntax_cast(s);
      //expression ce = cast_expression(c);
      //out = expression_to_points_to(ce, in);
      break;
    }
    case is_syntax_sizeofexpression: {
      //sizeofexpression soe = syntax_sizeofexpression(s);
      //if(sizeofexpression_type_p(soe))
      //; // in is not modified
      //else {
        // expression ne = sizeofexpression_expression(soe);
        // FI: we have a problem because sizeof(*p) does not imply that
        // *p is evaluated...
        // out = expression_to_points_to(ne, in);
      //;
      //}
      break;
    }
    case is_syntax_subscript: {
      subscript sub = syntax_subscript(s);
      in = dereferencing_subscript_to_points_to(sub, in);
      break;
    }
    case is_syntax_application: {
      // FI: we might have to go down here...
      //application a = syntax_application(s);
      //out = application_to_points_to(a, out);
      break;
    }
    case is_syntax_va_arg: {
      // The call to va_arg() does not create a points-to per se
      //list soel = syntax_va_arg(s);
      //sizeofexpression soe1 = SIZEOFEXPRESSION(CAR(soel));
      //sizeofexpression soe2 = SIZEOFEXPRESSION(CAR(CDR(soel)));
      //expression se = sizeofexpression_expression(soe1);
      // type t = sizeofexpression_type(soe2);
      //out = expression_to_points_to(se, out);
      break;
    }
    default:
      ;
    }
  }
  return in;
}

References array_of_pointers_type_p(), array_of_struct_type_p(), call_arguments, call_function, call_to_points_to(), CAR, CDR, dereferencing_subscript_to_points_to(), entity_basic_concrete_type(), ENTITY_FIELD_P, EXPRESSION, expression_reference(), expression_reference_p(), expression_syntax, expression_to_points_to_sinks(), expressions_to_points_to(), f(), gen_free_list(), get_bool_property(), is_syntax_application, is_syntax_call, is_syntax_cast, is_syntax_range, is_syntax_reference, is_syntax_sizeofexpression, is_syntax_subscript, is_syntax_va_arg, NIL, pips_assert, pointer_type_p(), reference_dereferencing_to_points_to(), reference_variable, struct_type_p(), syntax_call, syntax_reference, syntax_subscript, and syntax_tag.

Referenced by dereferencing_subscript_to_points_to(), expression_to_points_to(), intrinsic_call_condition_to_points_to(), intrinsic_call_to_points_to(), and reference_to_points_to().

Here is the call graph for this function:

Here is the caller graph for this function:

dereferencing_to_sinks()

list dereferencing_to_sinks	(	expression	a,
		pt_map	in,
		bool	eval_p
	)

Returns "sinks", the list of cells pointed to by expression "a" according to points-to graph "in".

If eval_p is true, perform a second dereferencing on the cells obtained with the first dereferencing.

Manage NULL and undefined (nowhere) cells.

Possibly update the points-to graph when some arcs are incompatible with the request, assuming the analyzed code is correct.

Locate the pointer, no dereferencing yet... unless no pointer can be found as in *(p+2) in which case an evaluation occurs/might occur/used to occur in expression_to_points_to_sources().

lse

Finds what it is pointing to, memory(p)

Do we want to dereference c?

Do not create sharing between elements of "in" and elements of "sinks".

The sinks list is empty, whether eval_p is true or not...

FI: New cells have been allocated by source_to_sinks(): side-effects are OK. In theory... The source code of source_to_sinks() seems to show that fresh_p is not exploited in all situations.

Parameters

in	n
eval_p	val_p

Definition at line 432 of file dereferencing.c.

{
  list sinks = NIL;
  /* Locate the pointer, no dereferencing yet... unless no pointer can
     be found as in *(p+2) in which case an evaluation occurs/might
     occur/used to occur in expression_to_points_to_sources(). */
  list cl = expression_to_points_to_sources(a, in);
  if(ENDP(cl)) {
    // The source may not be found, e.g. *(p+i)
    //sinks = expression_to_points_to_sinks(a, in);
    cl = expression_to_points_to_sinks(a, in);
  }
  /*else*/ { // Some sources have been found
    remove_impossible_arcs_to_null(&cl, in);
    bool evaluated_p = !expression_to_points_to_cell_p(a);
    // evaluated_p = false;
    if(!evaluated_p || eval_p) {
      bool null_dereferencing_p
        = get_bool_property("POINTS_TO_NULL_POINTER_DEREFERENCING");
      bool nowhere_dereferencing_p
        = get_bool_property("POINTS_TO_UNINITIALIZED_POINTER_DEREFERENCING");
 
      /* Finds what it is pointing to, memory(p) */
      FOREACH(CELL, c, cl) {
        /* Do we want to dereference c? */
        if( (null_dereferencing_p || !null_cell_p(c))
            && (nowhere_dereferencing_p || !nowhere_cell_p(c))) {
          list o_pointed = source_to_sinks(c, in, true);
          remove_impossible_arcs_to_null(&o_pointed, in);
          /* Do not create sharing between elements of "in" and elements of
             "sinks". */
          // list pointed = source_to_sinks(c, in, true);
          list pointed = gen_full_copy_list(o_pointed);
          gen_free_list(o_pointed);
          if(ENDP(pointed)) {
            reference r = cell_any_reference(c);
            entity v = reference_variable(r);
            string words_to_string(list);
            pips_user_warning("No pointed location for variable \"%s\" and reference \"%s\"\n",
                              entity_user_name(v),
                              reference_to_string(r));
            /* The sinks list is empty, whether eval_p is true or not... */
          }
          else {
            if(!evaluated_p && eval_p) {
              FOREACH(CELL, sc, pointed) {
                bool to_be_freed;
                type t = points_to_cell_to_type(sc, &to_be_freed);
                if(!pointer_type_p(t)) {
                  // FI: it might be necessary to allocate a new copy of sc
                  sinks = gen_nconc(sinks, CONS(CELL, sc, NIL));
                }
                else if(array_type_p(t) || struct_type_p(t)) {
                  /* FI: New cells have been allocated by
                     source_to_sinks(): side-effects are OK. In
                     theory... The source code of source_to_sinks() seems
                     to show that fresh_p is not exploited in all
                     situations. */
                  //cell nsc = copy_cell(sc);
                  //points_to_cell_add_zero_subscripts(nsc);
                  //sinks = gen_nconc(sinks, CONS(CELL, nsc, NIL));
                  pips_internal_error("sc assume saturated with 0 subscripts and/or field susbscripts.\n");
                }
                else {
                  list starpointed = pointer_source_to_sinks(sc, in);
                  // sinks = gen_nconc(sinks, starpointed);
                  sinks = merge_points_to_cell_lists(sinks, starpointed);
                }
                if(to_be_freed) free_type(t);
              }
            }
            else
              sinks = gen_nconc(sinks, pointed);
          }
        }
      }
    }
    else
      sinks = cl;
  }
 
  return sinks;
}

References array_type_p(), CELL, cell_any_reference(), CONS, ENDP, entity_user_name(), expression_to_points_to_cell_p(), expression_to_points_to_sinks(), expression_to_points_to_sources(), FOREACH, free_type(), gen_free_list(), gen_full_copy_list(), gen_nconc(), get_bool_property(), merge_points_to_cell_lists(), NIL, nowhere_cell_p(), null_cell_p(), pips_internal_error, pips_user_warning, pointer_source_to_sinks(), pointer_type_p(), points_to_cell_to_type(), reference_to_string(), reference_variable, remove_impossible_arcs_to_null(), source_to_sinks(), struct_type_p(), and words_to_string().

Referenced by unary_intrinsic_call_to_points_to_sinks().

Here is the call graph for this function:

Here is the caller graph for this function:

expression_to_points_to_cell_p()

bool expression_to_points_to_cell_p

(

expression

e

)

Can expression e be reduced to a reference, without requiring an evaluation?

For instance expression "p" can be reduced to reference "p".

Expression "p+i" cannot be reduced to a source reference, unless i==0.

Ad'hoc development for dereferencing_to_sinks.

Definition at line 406 of file dereferencing.c.

{
  bool source_p = true;
  syntax s = expression_syntax(e);
  if(syntax_reference_p(s))
    source_p = true;
  else if(syntax_call_p(s)) {
    call c = syntax_call(s);
    entity f = call_function(c);
    if(ENTITY_PLUS_C_P(f))
      source_p = false;
  }
  return source_p;
}

References call_function, ENTITY_PLUS_C_P, expression_syntax, f(), syntax_call, syntax_call_p, and syntax_reference_p.

Referenced by dereferencing_to_sinks(), and expression_to_points_to_sources().

Here is the call graph for this function:

Here is the caller graph for this function:

pointer_points_to_reference_p()

bool pointer_points_to_reference_p

(

reference r

__attribute__(unused)

)

see if a points_to_reference includes a pointer dereferencing: this is impossible if the points-to reference is consistent.

It must be a constant path.

Definition at line 313 of file dereferencing.c.

{
  return false;
}

Referenced by reference_dereferencing_to_points_to().

Here is the caller graph for this function:

pointer_reference_dereferencing_to_points_to()

void pointer_reference_dereferencing_to_points_to	(	reference	r,
		pt_map	in
	)

Parameters

in

n

Definition at line 318 of file dereferencing.c.

{
  expression pae = pointer_reference_to_expression(r);
  // FI: assume side effects are OK...
  (void) expression_to_points_to(pae, in, true);
  free_expression(pae);
}

References expression_to_points_to(), free_expression(), and pointer_reference_to_expression().

Referenced by reference_dereferencing_to_points_to().

Here is the call graph for this function:

Here is the caller graph for this function:

reference_dereferencing_to_points_to()

pt_map reference_dereferencing_to_points_to	(	reference	r,
		pt_map	in,
		bool	nowhere_dereferencing_p,
		bool	null_dereferencing_p
	)

Can we execute the reference r in points-to context "in" without segfaulting?

Do not go down in subscript expressions.

See also reference_to_points_to_sinks(). Unfortunate cut-and-paste.

Does the reference implies some dereferencing itself?

C syntactic sugar: *a is equivalent to a[0] when a is an array. No real dereferencing needed.

Remove store-dependent indices

Parameters

in	n
nowhere_dereferencing_p	owhere_dereferencing_p
null_dereferencing_p	ull_dereferencing_p

Definition at line 333 of file dereferencing.c.

{
  entity e = reference_variable(r);
  type t = entity_basic_concrete_type(e);
  list sl = reference_indices(r);
 
  /* Does the reference implies some dereferencing itself? */
  // FI: I do not remember what this means; examples are nice
  if(pointer_points_to_reference_p(r)) {
    pointer_reference_dereferencing_to_points_to(r, in);
  }
  else if(pointer_type_p(t) && !ENDP(sl)) {
    pointer_reference_dereferencing_to_points_to(r, in);
  }
  else if(array_of_pointers_type_p(t)
          && (int) gen_length(sl)>variable_dimension_number(type_variable(t))) {
    pointer_reference_dereferencing_to_points_to(r, in);
  }
  else if(array_type_p(t) && !array_of_pointers_type_p(t)) {
    /* C syntactic sugar: *a is equivalent to a[0] when a is an
       array. No real dereferencing needed. */
    ;
  }
  else {
    // FI: I am confused here
    // FI: we might have to do more when a struct or an array is referenced
    if(pointer_type_p(t) || array_of_pointers_type_p(t)) { // FI: implies ENDP(sl)
      reference nr = copy_reference(r);
      cell source = make_cell_reference(nr);
      /* Remove store-dependent indices */
      reference_indices(nr) =
        subscript_expressions_to_constant_subscript_expressions(reference_indices(nr));
      list sinks = source_to_sinks(source, in, false);
      int n = (int) gen_length(sinks);
      FOREACH(CELL, sink, sinks) {
        if(!nowhere_dereferencing_p && nowhere_cell_p(sink)) {
          remove_points_to_arcs(source, sink, in);
          n--;
        }
        if(!null_dereferencing_p && null_cell_p(sink)) {
          remove_points_to_arcs(source, sink, in);
          n--;
        }
      }
      if(n==0) {
        clear_pt_map(in);
        points_to_graph_bottom(in) = true;
        if(statement_points_to_context_defined_p())
          semantics_user_warning("Null or undefined pointer may be dereferenced because of \"%s\" at line %d.\n",
                            effect_reference_to_string(r),
                            points_to_context_statement_line_number());
        else
          semantics_user_warning("Null or undefined pointer may be dereferenced because of \"%s\".\n",
                            effect_reference_to_string(r));
      }
 
      gen_free_list(sinks);
    }
  }
  return in;
}

References array_of_pointers_type_p(), array_type_p(), CELL, clear_pt_map, copy_reference(), effect_reference_to_string(), ENDP, entity_basic_concrete_type(), FOREACH, gen_free_list(), gen_length(), int, make_cell_reference(), nowhere_cell_p(), null_cell_p(), pointer_points_to_reference_p(), pointer_reference_dereferencing_to_points_to(), pointer_type_p(), points_to_context_statement_line_number(), points_to_graph_bottom, reference_indices, reference_variable, remove_points_to_arcs(), semantics_user_warning, source_to_sinks(), statement_points_to_context_defined_p(), subscript_expressions_to_constant_subscript_expressions(), type_variable, and variable_dimension_number().

Referenced by dereferencing_to_points_to().

Here is the call graph for this function:

Here is the caller graph for this function: