alias_pairs.c

Go to the documentation of this file.

/*
 
  $Id: alias_pairs.c 23412 2017-08-09 15:07:09Z irigoin $
 
  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 <http://www.gnu.org/licenses/>.
 
*/
#ifdef HAVE_CONFIG_H
    #include "pips_config.h"
#endif
#include <stdio.h>
#include <string.h>
 
#include <setjmp.h>
 
#include "genC.h"
#include "linear.h"
#include "ri.h"
#include "effects.h"
#include "database.h"
 
#include "ri-util.h"
#include "effects-util.h"
#include "misc.h"
#include "text.h"
 
#include "effects-generic.h"
#include "effects-convex.h"
 
#include "semantics.h" // value_mappings..
#include "transformer.h" // free_value_mappings()
 
#include "pipsdbm.h"
 
/* Instantiation of the dependence graph: */
#include "dg.h"
typedef dg_arc_label arc_label;
typedef dg_vertex_label vertex_label;
 
#include "graph.h"
 
#define BACKWARD true
#define FORWARD false
 
 
static entity callee;
static list list_regions_callee = NIL;
static statement current_caller_stmt = statement_undefined;
static list list_pairs = NIL;
 
 
/* creation of a Pbase containing just the PHI variables of the region */
static Pbase
make_base_phi_variables(region reg)
{
    Pbase phi_variables;
    list indices;
 
    pips_debug(4,"begin\n");
    phi_variables = BASE_NULLE;
 
    indices = reference_indices(region_any_reference(reg));
    MAP(EXPRESSION, index,
        {
            entity e;
 
            e = reference_variable(syntax_reference(expression_syntax(index)));
            if (variable_phi_p(e))
            {
                pips_debug(9,"add: %s\n",entity_local_name(e));
 
                phi_variables = base_add_variable(phi_variables,(Variable) e);
            }
        },
            indices);
 
    pips_debug(4,"end\n");
 
    return phi_variables;
}
 
 
/* strips from the region all the constraints which do not affect
 * (even transitively) the PHI variables
 * i.e. the function representing the region no longer returns the
 * empty region if a branch condition is not satisfied
 * so the region becomes MAY-in-the-usual-dataflow-sense
 */
static region
restrict_to_phi_constraints(region reg)
{
    Pbase phi_variables;
    Psysteme sc;
    region new_reg;
 
    pips_debug(4,"begin\n");
 
 
    sc = region_system(reg);
    phi_variables = make_base_phi_variables(reg);
    new_reg = region_dup(reg);
 
    ifdebug(9)
        {
            set_action_interpretation(ACTION_IN,ACTION_OUT);
            pips_debug(9,"call sc_restricted_to_variables_transitive_closure for:\t\n");
            print_region(reg);
        }
 
    region_system(new_reg) =
        sc_restricted_to_variables_transitive_closure(sc,phi_variables);
 
    ifdebug(9)
        {
            pips_debug(9,"restricted region:\n\t");
            print_region(new_reg);
            reset_action_interpretation();
        }
 
    pips_debug(4,"end\n");
 
    return new_reg;
}
 
/* "convert" EXACT regions to exact representations of
 * MAY-in-the-usual-dataflow-sense regions
 */
static region
convert_exact_to_exact_may(region reg)
{
    region new_reg;
 
    pips_debug(4,"begin\n");
 
    new_reg = restrict_to_phi_constraints(reg);
    effect_approximation_tag(new_reg) = is_approximation_exact;
 
    pips_debug(4,"end\n");
 
    return(new_reg);
}
 
 
/* all MAY regions are "converted" to over-approximate representations of
 * MAY-in-the-usual-dataflow-sense regions (some regions may in fact be
 * precise representations  of MAY-in-the-usual-dataflow-sense regions after
 * this operation, but we cannot detect which)
 */
static region
approx_convert_may_to_approx_may(region reg)
{
    region new_reg;
 
    pips_debug(4,"begin\n");
 
    new_reg = restrict_to_phi_constraints(reg);
    effect_approximation_tag(new_reg) = is_approximation_may;
 
    pips_debug(4,"end\n");
 
    return(new_reg);
}
 
 
/* takes EXACT (i.e. precise representations of MUST in the usual
 * dataflow sense) and MAY (i.e. over-approximate representations of MUST
 * regions or either over-approximate or precise representations of
 * MAY-in-the-usual-dataflow-sense) regions and "converts" them to
 * exact or over-approximate representations of
 * MAY-in-the-usual-dataflow-sense) regions
 * by stripping all the constraints which do not affect
 * (even transitively) the PHI variables
 */
static region
approx_convert(region reg)
{
    region new_reg;
 
    pips_debug(4,"begin\n");
 
    if (region_scalar_p(reg))
    {
        pips_debug(9,"scalar\n");
 
        new_reg = reg;
        effect_approximation_tag(new_reg) = is_approximation_exact;
    }
    else
    {
        if ( effect_exact_p(reg) || effect_exact_p(reg) )
            new_reg = convert_exact_to_exact_may(reg);
        else
          {
            if (!effect_may_p(reg))
              pips_debug(4,"unknown approximation tag\n");
            new_reg = approx_convert_may_to_approx_may(reg);
          }
    }
    pips_debug(4,"end\n");
 
    return new_reg;
}
        
 
/* modifies global var current_caller_stmt */
static bool stmt_filter(s)
statement s;
{
    pips_debug(9, "statement %td\n", statement_number(s));
    
    current_caller_stmt = s;
    return(true);
}
 
 
/* static void
 * add_parameter_aliases_for_this_call_site(call call_site,
 * transformer context, list real_args)
 * constructs the alias pairs for the effective parameters (but not for
 * COMMON regions) at this call site and adds them to the list
 * input    : parameters: a call site and the calling context
 *            global variables: callee,list_regions_callee,list_pairs
 * output   : void
 * global vars IN: list_regions_callee and list_pairs
 * modifies : global var list_pairs
 *            for each region in list_regions_callee which is a region of a
 *            formal parameter (of the callee) and for which the corresponding
 *            real parameter is an expression with only one entity, this
 *            function performs
 *            the backward translation: callee_region -> real_region
 *            and adds an alias pair <callee_region,real_region> to list_pairs
 * comment  :   
 *
 * Algorithm :
 * -----------
 *    let list_regions_callee be the list of the regions on variables
 *    of callee
 *    let list_pairs be the list of alias pairs for the callee
 *
 *    FOR each expression real_exp IN real_args
 *        arg_num = number in the list of the function real arguments
 *        FOR each callee_region IN list_regions_callee
 *            callee_ent = entity of the region callee_region
 *            IF callee_ent is the formal parameter numbered arg_num
 *                IF real_exp is an lhs (expression with one entity)
 *                    real_region = translation of the region callee_region
 *                    list_pairs = list_pairs + <callee_region,real_region>
 *                ENDIF
 *            ENDIF
 *        ENDFOR
 *    ENDFOR
 */
static void
add_parameter_aliases_for_this_call_site(call call_site __attribute__ ((unused)),
                                         transformer context,
                                         list real_args)
{
    list r_args;
    int arg_num;
 
    pips_debug(4,"begin\n");
 
/*    real_args = call_arguments(call_site); */
 
    for (r_args = real_args, arg_num = 1; r_args != NIL;
         r_args = CDR(r_args), arg_num++) 
    {
        pips_debug(9,"compare formal parameter arg_num %03d\n",arg_num);
 
        MAP(EFFECT, callee_region,
         {
/*           entity callee_ent = region_entity(callee_region); */
             
             pips_debug(9,"\tand entity %s\n",
                        entity_name(region_entity(callee_region)));
 
             /* If the formal parameter corresponds to the real argument then
              * we perform the translation.
              */
             if (ith_parameter_p(callee,region_entity(callee_region),arg_num))
             {
                 expression real_exp = EXPRESSION(CAR(r_args));
                 syntax real_syn = expression_syntax(real_exp);
                 
                 pips_debug(9,"match\n");
 
                 /* If the real argument is a reference to an entity, then we
                  * translate the regions of the corresponding formal parameter
                  */
                 if (syntax_reference_p(real_syn)) 
                 {
                    reference real_ref = syntax_reference(real_syn);
                    entity real_ent = reference_variable(real_ref);
                    region trans;
                    region formal;
                    region actual;
                    list pair;
 
                    pips_debug(9,"arg refers to entity\n");
                    pips_debug(9,"\t%s\n",entity_name(real_ent));
 
                    trans =
                        region_translation(
                            callee_region,
                            callee,
                            reference_undefined,
                            real_ent,
                            get_current_module_entity(),
                            real_ref,
                            VALUE_ZERO,
                            BACKWARD);
 
                    pair = CONS(EFFECT,trans,NIL);
 
                    ifdebug(9)
                        {
                            pips_debug(9,"region translated to:\n\t");
                            print_inout_regions(pair);
                        }
 
                    /* the actual parameter must be expressed relative to
                       the store at the point of entry of the caller, so
                       that it can be compared to other regions */
 
                    pair =
                        convex_regions_transformer_compose(pair,context);
 
                    ifdebug(9)
                        {
                            pips_debug(9,"relative to initial store:\n\t");
                            print_inout_regions(pair);
                        }
 
                    /* convert actual and formal regions to
                       MAY-in-the-usual-dataflow-sense */
                    actual = approx_convert(EFFECT(CAR(pair)));
 
                    pair = CONS(EFFECT,actual,NIL);
 
                    ifdebug(9)
                        {
                            pips_debug(9,"restricted to:\n\t");
                            print_inout_regions(pair);
                        }
 
/* gave Newgen error
   formal = approx_convert(callee_region); */
 
                    formal = approx_convert(region_dup(callee_region));
 
                    pair = CONS(EFFECT,formal,pair);
 
                    ifdebug(9)
                        {
                            pips_debug(9,"alias pair:\n\t");
                            print_inout_regions(pair);
                        }
 
                    list_pairs = CONS(EFFECTS,make_effects(pair),list_pairs);
                }
             }
         }, list_regions_callee);
    }
 
    pips_debug(4,"end\n");
       
}
 
/* constructs the alias pairs for this call site and adds them to the list
 * global vars IN: callee, list_regions_callee, current_caller_stmt
 * and list_pairs
 * modifies global var: list_pairs
 */
 
static bool
add_alias_pairs_for_this_call_site(call call_site)
{
    transformer context;
    list real_args;
 
    if (call_function(call_site) != callee) return true;
 
    pips_debug(4,"begin\n");
 
/*    pips_debug(9,
               "try load_statement_precondition for statement %03d\n",
               statement_number(current_caller_stmt));
               */
 
    context = load_statement_precondition(current_caller_stmt);
 
/* transformer_to_string no longer implemented */
/*    pips_debug(9,"got context:\n\t%s\n",transformer_to_string(context)); */
 
/*    pips_debug(9,"try call_arguments\n"); */
 
    real_args = call_arguments(call_site);
 
/*    pips_debug(9,"try set_interprocedural_translation_context_sc\n");
    pips_debug(9,"\tfor callee %s\n",entity_name(callee)); */
 
    set_interprocedural_translation_context_sc(callee, real_args);
 
/*    pips_debug(9,"try set_backward_arguments_to_eliminate\n"); */
 
    set_backward_arguments_to_eliminate(callee);
 
    add_parameter_aliases_for_this_call_site(call_site,context,real_args);
/*    add_common_aliases_for_this_call_site(); */
 
    reset_translation_context_sc();
    reset_arguments_to_eliminate();
 
    pips_debug(4,"end\n");
 
    return true;
}
 
 
/* constructs the alias pairs for this caller and adds them to the list
 * global vars IN: callee, list_regions_callee and list_pairs
 * modifies global vars: list_pairs and current_caller_stmt
 */
static void
add_alias_pairs_for_this_caller( entity caller )
{
    const char *caller_name;
    statement caller_statement;
 
    reset_current_module_entity();
    set_current_module_entity(caller);
    caller_name = module_local_name(caller);
    pips_debug(4,"begin for caller: %s\n", caller_name);
 
    /* ATTENTION: we must do ALL this before calling 
     * set_interprocedural_translation_context_sc
     * (in add_alias_pairs_for_this_call_site
     * called by the gen_multi_recurse below) !!!
     */
    /* the current module becomes the caller */
    regions_init();
    get_in_out_regions_properties();
    set_current_module_statement( (statement)
        db_get_memory_resource(DBR_CODE, caller_name, true) );
    set_cumulated_rw_effects((statement_effects)
        db_get_memory_resource(DBR_CUMULATED_EFFECTS, caller_name, true));
    set_proper_rw_effects((statement_effects)
        db_get_memory_resource(DBR_PROPER_EFFECTS, caller_name, true));
    module_to_value_mappings(caller);
    set_precondition_map( (statement_mapping) 
        db_get_memory_resource(DBR_PRECONDITIONS, caller_name, true));
    /* that's it,
     * but we musn't forget to reset it all again below !
     */
    
    caller_statement = get_current_module_statement();
 
 
/*  gen_multi_recurse(obj,
 *                   [domain, filter, rewrite,]*
 *                    NULL);
 *
 *  recurse from object obj,
 *  applies filter_i on encountered domain_i objects,
 *  if true, recurses down from the domain_i object, 
 *       and applies rewrite_i on exit from the object.
 */
 
    gen_multi_recurse(caller_statement,
                      statement_domain,
                      stmt_filter,
                      gen_null,
                      call_domain,
                      add_alias_pairs_for_this_call_site,
                      gen_null,
                      NULL);
  
    reset_current_module_statement();
    reset_cumulated_rw_effects();
    reset_proper_rw_effects();
    free_value_mappings();
    reset_precondition_map();
    regions_end();
 
    reset_current_module_entity();
    set_current_module_entity(callee);    
 
    pips_debug(4,"end\n");
 
}
 
 
/* generic function (i.e. used for IN and OUT regions) for constructing
 * the list of alias pairs for this module
 * parameters: module name and list of regions
 * global vars IN: none
 * modifies global vars: callee, list_regions_callee, current_caller_stmt
 * and list_pairs
 */
static list
alias_pairs( const char* module_name, list l_reg )
{
 
    callees callers;
 
    pips_debug(4,"begin for module %s\n",module_name);
 
    set_current_module_entity( local_name_to_top_level_entity(module_name) );
    callee = get_current_module_entity();
    list_regions_callee = l_reg;
 
    ifdebug(9)
        {
            /* ATTENTION: we have to do ALL this
             * just to call print_inout_regions for debug !!
             */
            set_current_module_statement( (statement)
                                          db_get_memory_resource(DBR_CODE,
                                                                 module_name,
                                                                 true) );
            set_cumulated_rw_effects((statement_effects)
                                     db_get_memory_resource(
                                         DBR_CUMULATED_EFFECTS,
                                         module_name,
                                         true));
            set_proper_rw_effects((statement_effects)
                                     db_get_memory_resource(
                                         DBR_PROPER_EFFECTS,
                                         module_name,
                                         true));
            module_to_value_mappings(callee);
            /* that's it, but we musn't forget to reset everything below */
 
            pips_debug(9,"list_regions_callee is: \n");
            print_inout_regions(list_regions_callee);
 
            free_value_mappings();
            reset_cumulated_rw_effects();
            reset_proper_rw_effects();
            reset_current_module_statement();
        }
 
    /* we need the callers of the current module  */
    callers = (callees) db_get_memory_resource(DBR_CALLERS,
                                               module_name,
                                               true);
 
    /* we scan the callers to find the call sites,
     * and fill in the list of alias pairs (list_pairs)
     */
    list_pairs = NIL;
    MAP(STRING, caller_name,
    {
        entity caller = local_name_to_top_level_entity(caller_name);
        add_alias_pairs_for_this_caller(caller);
    },
        callees_callees(callers));
 
    reset_current_module_entity();
 
    pips_debug(4,"end\n");
 
    return list_pairs;
}
 
 
/* top-level creation of pairs of aliases of IN regions of the module
 * modifies global vars callee, list_regions_callee, list_pairs and
 * current_caller_stmt
 */
bool in_alias_pairs( const string module_name )
{
    list l_reg, l_pairs;
 
    debug_on("ALIAS_PAIRS_DEBUG_LEVEL");
    pips_debug(4,"begin for module %s\n",module_name);
 
    /* we need the IN summary regions*/
    l_reg = effects_to_list((effects)
                            db_get_memory_resource(DBR_IN_SUMMARY_REGIONS,
                                          module_name,
                                          true));
 
/* was (but didn't work)
    l_reg = (list) db_get_memory_resource(DBR_IN_SUMMARY_REGIONS,
                                          module_name,
                                          true);
                                          */
    
    l_pairs = alias_pairs(module_name, l_reg);
 
    DB_PUT_MEMORY_RESOURCE(DBR_IN_ALIAS_PAIRS, 
                           strdup(module_name),
                           (char*) make_effects_classes(l_pairs));
 
    pips_debug(4,"end\n");
    debug_off();
 
    return(true);
 
}
 
/* top-level creation of pairs of aliases of OUT regions of the module
 * modifies global vars callee, list_regions_callee, list_pairs and
 * current_caller_stmt
 */
bool out_alias_pairs( const char* module_name )
{
    list l_reg, l_pairs;
 
    debug_on("ALIAS_PAIRS_DEBUG_LEVEL");
    pips_debug(4,"begin for module %s\n",module_name);
 
    /* we need the OUT summary regions*/
    l_reg = effects_to_list((effects)
                            db_get_memory_resource(DBR_OUT_SUMMARY_REGIONS,
                                          module_name,
                                          true));
 
/* was (but didn't work)
    l_reg = (list) db_get_memory_resource(DBR_OUT_SUMMARY_REGIONS,
                                          module_name,
                                          true);
                                          */
 
    
    l_pairs = alias_pairs(module_name, l_reg);
 
    DB_PUT_MEMORY_RESOURCE(DBR_OUT_ALIAS_PAIRS, 
                           strdup(module_name),
                           (char*) make_effects_classes(l_pairs));
 
    pips_debug(4,"end\n");
    debug_off();
 
    return(true);
 
}