/*
$Id$
Copyright 1989-2016 MINES ParisTech
This file is part of PIPS.
PIPS is free software: you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
any later version.
PIPS is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.
See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with PIPS. If not, see .
*/
#ifdef HAVE_CONFIG_H
#include "pips_config.h"
#endif
/* package simple effects : Be'atrice Creusillet 5/97
*
* File: interprocedural.c
* ~~~~~~~~~~~~~~~~~~~~~~~
*
* This File contains functions for the interprocedural computation of simple
* effects.
*/
#include
#include
#include "genC.h"
#include "linear.h"
#include "ri.h"
#include "effects.h"
#include "text.h"
#include "misc.h"
#include "text-util.h"
#include "ri-util.h"
#include "properties.h"
#include "prettyprint.h"
#include "effects-util.h"
#include "effects-generic.h"
#include "effects-simple.h"
/* Assume asl and isl have the same number of elements. Build
* subscript list osl by adding when possible the subscripts in asl
* and isl. See if the addition is exact.
*
* symbolic expressions are preserved at this stage, to be deleted
* later for simple effects because they will be replaced by
* *. However, it might be useful when descriptors are used.
*/
bool add_points_to_subscript_lists(list * posl, list asl, list isl)
{
list casl, cisl;
bool exact_p = true;
for(casl=asl, cisl=isl; !ENDP(casl) && !ENDP(cisl); POP(casl), POP(cisl)) {
expression a = EXPRESSION(CAR(casl));
expression i = EXPRESSION(CAR(cisl));
if(unbounded_expression_p(a) || unbounded_expression_p(i)) {
expression u = make_unbounded_expression();
*posl = CONS(EXPRESSION, u, *posl);
exact_p = false;
}
else if(expression_field_p(a)) {
if(expression_field_p(i)) {
pips_assert("Both expressions are identical", expression_equal_p(a,i));
expression f = copy_expression(a);
*posl = CONS(EXPRESSION, f, *posl); // exactitude unchanged
}
else
pips_internal_error("Unexpected case.\n");
}
else {
intptr_t as, is;
if(expression_integer_value(a,&as)) {
if(expression_integer_value(i, &is)) {
expression ns = int_to_expression((int)as+is);
*posl = CONS(EXPRESSION, ns, *posl); // exactitude unchanged
}
else {
expression ns = expression_undefined;
if(as==0) {
ns = copy_expression(i);
}
else {
ns = binary_intrinsic_expression(PLUS_OPERATOR_NAME,
copy_expression(a),
copy_expression(i));
}
*posl = CONS(EXPRESSION, ns, *posl); // exactitude unchanged
}
}
else {
expression ns = expression_undefined;
if(expression_integer_value(i, &is) && is==0)
ns = copy_expression(a);
else
ns = binary_intrinsic_expression(PLUS_OPERATOR_NAME,
copy_expression(a),
copy_expression(i));
*posl = CONS(EXPRESSION, ns, *posl); // exactitude unchanged
}
}
}
*posl = gen_nreverse(*posl);
return exact_p;
}
/* FI: Let's deal with simple cases I think I know how to deal with.
*/
bool simple_cell_reference_with_address_of_cell_reference_translation_fi
(reference input_ref, descriptor __attribute__ ((unused)) input_desc,
reference address_of_ref, descriptor __attribute__ ((unused)) address_of_desc,
int nb_common_indices,
reference *output_ref, descriptor __attribute__ ((unused)) * output_desc,
bool *exact_p)
{
list sl = reference_indices(address_of_ref);
bool ok_p = nb_common_indices==0 || ENDP(sl);
if(ok_p) {
list isl = reference_indices(input_ref);
list asl = reference_indices(address_of_ref);
int nis = (int) gen_length(isl);
int nas = (int) gen_length(asl);
if(nis==nas) {
type cit = points_to_reference_to_concrete_type(input_ref);
type cat = points_to_reference_to_concrete_type(address_of_ref);
if(type_equal_p(cit, cat)) {
*output_ref = make_reference(reference_variable(address_of_ref), NIL);
list osl = NIL;
*exact_p = add_points_to_subscript_lists(&osl, asl, isl);
reference_indices(*output_ref) = osl;
}
else
ok_p = false;
}
else if(nis==nas+1) {
// Not sure this is useful
type cit = points_to_reference_to_concrete_type(input_ref);
type cat = points_to_reference_to_concrete_type(address_of_ref);
if(type_equal_p(cit, cat)) {
*output_ref = make_reference(reference_variable(address_of_ref), NIL);
list osl = NIL;
*exact_p = add_points_to_subscript_lists(&osl, asl, CDR(isl));
reference_indices(*output_ref) = osl;
}
else
ok_p = false;
}
else if(nis>0 && nas==0) {
// EffectsWithPointsTo/array05a: input_ref "r[0][0][0][0]" and
// address_of_ref "t" where "r" is a pointer towards a 3-D array "t"
expression fs = EXPRESSION(CAR(isl));
if(zero_expression_p(fs)) {
reference n_input_ref = make_reference(reference_variable(input_ref),
CONS(EXPRESSION, copy_expression(fs), NIL));
type cit = points_to_reference_to_concrete_type(n_input_ref);
free_reference(n_input_ref);
type cat = points_to_reference_to_concrete_type(address_of_ref);
if(type_equal_p(cit, cat)) {
/* FI: this is not always correct because the index list may hide
* dereferencings... We should use only the indices that
* match the type of address_of_ref and call recursively the
* translation. Or rely on Beatrice's code.
*/
type rt = points_to_reference_to_concrete_type(address_of_ref);
int nd = maximal_type_depth(rt);
// FI: may be "nd" when POINTS_TO_STRICT_POINTER_TYPES is set to true
bool strict_p = get_bool_property("POINTS_TO_STRICT_POINTER_TYPES");
if(strict_p? nis<=nd : nis<=nd+1) {
*output_ref = copy_reference(address_of_ref); // No subscripts
*exact_p = exact_points_to_subscript_list_p(CDR(isl));
reference_indices(*output_ref) = gen_full_copy_list(CDR(isl));
}
else
ok_p = false; // Let Beatrice take care of it...
}
else
ok_p = false;
}
else
ok_p = false;
}
else
ok_p = false;
}
if(ok_p) {
ifdebug(1) {
type it = points_to_reference_to_concrete_type(input_ref);
type ot = points_to_reference_to_concrete_type(*output_ref);
if(!type_equal_up_to_qualifiers_p(it,ot))
pips_internal_error("Translation failure: the type of the translated cells is different from the type of the input cell.\n");
}
}
return ok_p;
}
/** @brief translates a simple memory access path reference from given indices
using an address_of memory access path reference
This function is used when we want to translate a cell or an effect on a[i][j][k] as input_ref,
knowing that a[i] = &address_of_ref. In this case nb_common_indices is 1 (which corresponds to [i])
@param input_ref is the input simple cell reference
@param input_desc is here for compatibility with the corresponding convex cells function.
@param address_of_ref is the simple cell reference giving the output base memory access path.
@param address_of_desc is here for compatibility with the corresponding convex cells function.
@param nb_common_indices is the number of indices of input_ref which must be skipped (why is it unique for all points-to arcs?)
@param output_ref is a pointer on the resulting reference
@param output_desc is here for compatibility with the corresponding convex cells function.
@param exact_p is a pointer on a bool which is set to true if the translation is exact, false otherwise.
FI->BC: more examples would be useful. For instance, let's have
"p->i[1]" as points-to and hence "i[1]" as "address_of_ref". Let's
have "p[0]" as input ref. The number of common indices is zero in
the points-to arc. However, the two indices should be fused and
not concatenated.
FI->BC: another example due to Pointers/array15.c. Input_ref is
b[0][3] and address_of_ref is _b_1[0][0]. nb_common_indices is
0. b is a pointer to an array and the thing to do is to add the
indices one by one, not to concatenate anything...
FI->BC: this function is way too long. It must handle very
different cases, e.g. arrays of pointers, struct as well as simple
scalar pointer to scalar or arrays. It would be nice to have an
example for each class of input.
*/
void simple_cell_reference_with_address_of_cell_reference_translation
(reference input_ref, descriptor __attribute__ ((unused)) input_desc,
reference address_of_ref, descriptor __attribute__ ((unused)) address_of_desc,
int nb_common_indices,
reference *output_ref, descriptor __attribute__ ((unused)) * output_desc,
bool *exact_p)
{
pips_debug(1, "input_ref: %s\n", reference_to_string(input_ref));
pips_debug(1, "address_of_ref: %s\n", reference_to_string(address_of_ref));
pips_debug(1, "nb_common_indices: %d \n", nb_common_indices);
if(simple_cell_reference_with_address_of_cell_reference_translation_fi(input_ref, input_desc, address_of_ref, address_of_desc, nb_common_indices, output_ref, output_desc, exact_p)) { // Francois' special case
;
}
else { // Beatrice's code
// For instance, we enter with nb_common_indices==0
// input_ref == m[0][tab2][0]
// address_of_ref == _m_1[0], which means m->_m_1[0]
/* assume exactness */
*exact_p = true;
/* */
*output_ref = copy_reference(address_of_ref);
// FI: this is already wrong for Pointers/array15.c
// We need output_indices=reference_indices(*output_ref)
list output_indices = gen_last(reference_indices(*output_ref));
list input_remaining_indices = reference_indices(input_ref);
for(int i = 0; i returning anywhere\n");
free_reference(*output_ref);
*output_ref = make_reference(entity_all_locations(), NIL);
*exact_p = false;
}
else
new_exp = last_output_indices_exp;
}
else if(!unbounded_expression_p(first_input_remaining_exp)) {
value v;
intptr_t i_last_output_indices_exp;
intptr_t i_first_input_remaining_exp;
bool b_i_last_output_indices_exp = expression_integer_value(last_output_indices_exp, &i_last_output_indices_exp);
bool b_i_first_input_remaining_exp = expression_integer_value(first_input_remaining_exp, &i_first_input_remaining_exp);
if (b_i_last_output_indices_exp && i_last_output_indices_exp == 0) {
new_exp = copy_expression(first_input_remaining_exp);
POP(input_remaining_indices);
}
else if (b_i_first_input_remaining_exp && i_first_input_remaining_exp == 0) {
new_exp = copy_expression(last_output_indices_exp);
POP(input_remaining_indices);
}
else {
new_exp = MakeBinaryCall
(entity_intrinsic(PLUS_OPERATOR_NAME),
copy_expression(last_output_indices_exp), copy_expression(first_input_remaining_exp));
/* Then we must try to evaluate the expression */
v = EvalExpression(new_exp);
if (! value_undefined_p(v) &&
value_constant_p(v)) {
constant vc = value_constant(v);
if (constant_int_p(vc)) {
free_expression(new_exp);
new_exp = int_to_expression(constant_int(vc));
}
}
POP(input_remaining_indices);
}
}
else {
new_exp = make_unbounded_expression();
*exact_p = false;
POP(input_remaining_indices);
}
if (! entity_all_locations_p(reference_variable(*output_ref))) {
/* FI->BC: this looks much more like a concatenation than
a substitution of the first subscript. */
//CAR(gen_last(reference_indices(*output_ref))).p
// = (void *) new_exp;
expression old_s = EXPRESSION(CAR(gen_last(reference_indices(*output_ref))));
free_expression(old_s);
// FI: I do not see why it should be a change of the last subscript
// I'd rather see a change of the first subscript...
EXPRESSION_(CAR(gen_last(reference_indices(*output_ref)))) = new_exp;
}
}
else {
*exact_p = false;
POP(input_remaining_indices); // a * subscript absorbs everything
}
}
else /* ENDP(output_indices) */ {
/* address_of_ref is a scalar: the first remaning index must be equal to 0 */
expression first_input_remaining_exp = EXPRESSION(CAR(input_remaining_indices));
if (!expression_equal_integer_p(first_input_remaining_exp, 0)) {
/* FI->BC: A much better job could be done using a function
similar to source_to_sinks(). See for instance
Pointers/properties03.c: if the analysis is performed at
points-to level, the result is precise; if the very same
analysis is performed by effects_with_points_to, an
anywhere results. */
pips_user_warning("potential memory overflow due to effect -> returning anywhere\n");
free_reference(*output_ref);
// FI->BC: conditionally to a property,
// ALIASING_ACROSS_TYPES, a typed anywhere should be generated
*output_ref = make_reference(entity_all_locations(), NIL);
*exact_p = false;
}
}
// FI->BC: something is missing here points-to
// If the target is an array, the first subscript at least should be
// replicated: if "p" in a pointer to an array "a", "p[0]" is "a[0]", not "a"
//
// This happens because "int * p;" defines implictly "p" as a
// pointer to an array
if (! entity_all_locations_p(reference_variable(*output_ref)))
{
entity v = reference_variable(*output_ref);
// type vt = entity_type(v); // FI: should probably be a concrete
// FI: see EffectWitPointsTo/call09.c
type vt = entity_basic_concrete_type(v);
// type, but hopefully this has been done earlier when computing
// points-to
// FI: under some circumstances, the first zero subscript must
// be ignored. See for instance EffectsWithPointsTo/call09.c
// list sl = (false && array_type_p(vt))? input_remaining_indices :
// CDR(input_remaining_indices);
list sl = input_remaining_indices; // default value
// FI->FI: Beatrice uses a more powerful zero detection
if(!array_type_p(vt)
&& !ENDP(sl)
&& zero_expression_p(EXPRESSION(CAR(sl))))
sl = CDR(input_remaining_indices);
FOREACH(EXPRESSION, input_ind, sl)
{
reference_indices(*output_ref) = gen_nconc(reference_indices(*output_ref),
CONS(EXPRESSION,
copy_expression(input_ind),
NIL));
}
}
}
// FI: the consistency of the regenerated reference should be checked
// by computing its type, if only, under a ifdebug() guard...
pips_debug(8, "output reference %s\n",
reference_to_string(*output_ref));
ifdebug(1) {
type it = points_to_reference_to_concrete_type(input_ref);
type ot = points_to_reference_to_concrete_type(*output_ref);
if(!anywhere_reference_p(*output_ref)
&& !type_equal_up_to_qualifiers_p(it,ot))
pips_internal_error("Translation failure: the type of the translated cells is different from the type of the input cell.\n");
}
return;
}
/** @brief translates a simple memory access path reference from given indices
using an value_of memory access path reference
This function is used when we want to translate a cell or an effect on a[i][j][k] as input_ref,
knowing that a[i] = value_of_ref. In this case nb_common_indices is 1 (which corresponds to [i])
@param input_ref is the input simple cell reference
@param input_desc is here for compatibility with the corresponding convex cells function.
@param value_of_ref is the simple cell reference giving the output base memory access path.
@param value_of_desc is here for compatibility with the corresponding convex cells function.
@param nb_common_indices is the number of indices of input_ref which must be skipped
@param output_ref is a pointer on the resulting reference
@param output_desc is here for compatibility with the corresponding convex cells function.
@param exact_p is a pointer on a bool which is set to true if the translation is exact, false otherwise.
*/
void simple_cell_reference_with_value_of_cell_reference_translation
(reference input_ref, descriptor __attribute__ ((unused)) input_desc,
reference value_of_ref, descriptor __attribute__ ((unused)) value_of_desc,
int nb_common_indices,
reference *output_ref, descriptor __attribute__ ((unused)) * output_desc,
bool *exact_p)
{
/* assume exactness */
*exact_p = true;
/* we do not handle yet the cases where the type of value_of_ref does not match
the type of a[i]. I need a special function to test if types are compatible,
because type_equal_p is much too strict.
moreover the signature of the function may not be adapted in case of the reshaping of a array
of structs into an array of char for instance.
*/
list input_inds = reference_indices(input_ref);
*output_ref = copy_reference(value_of_ref);
/* we add the indices of the input reference past the nb_common_indices
(they have already be poped out) to the copy of the value_of reference */
for(int i = 0; i