liveness_analysis_engine.c File Reference

#include <stdio.h>
#include <string.h>
#include "genC.h"
#include "linear.h"
#include "ri.h"
#include "effects.h"
#include "database.h"
#include "misc.h"
#include "ri-util.h"
#include "effects-util.h"
#include "constants.h"
#include "text-util.h"
#include "text.h"
#include "properties.h"
#include "pipsdbm.h"
#include "resources.h"
#include "pointer_values.h"
#include "effects-generic.h"
#include "prettyprint.h"

Include dependency graph for liveness_analysis_engine.c:

Go to the source code of this file.

Data Structures
struct	live_paths_analysis_context
struct	live_out_summary_engine_context

Functions
static void	init_live_paths_context (live_paths_analysis_context *ctxt, effects_representation_val representation)
static void	reset_live_paths_context (live_paths_analysis_context *ctxt)
static list	convert_rw_effects (list lrw, live_paths_analysis_context *ctxt)
static void	reset_converted_rw_effects (list *lrw, live_paths_analysis_context *ctxt)
static list	convert_in_effects (list lin, live_paths_analysis_context *ctxt)
static void	reset_converted_in_effects (list *lin, live_paths_analysis_context *ctxt)
bool	live_in_summary_paths_engine (const char *module_name)
	liveness_analysis_engine.c More...
static void	set_live_out_summary_engine_context (live_out_summary_engine_context *ctxt, entity callee)
static void	reset_live_out_summary_engine_context (live_out_summary_engine_context *ctxt)
static void	update_live_out_summary_engine_context_paths (live_out_summary_engine_context *ctxt, list l_paths)
static bool	live_out_paths_from_call_site_to_callee (call c, live_out_summary_engine_context *ctxt)
static bool	live_out_summary_paths_stmt_filter (statement s, __attribute__((unused)) live_out_summary_engine_context *ctxt)
static void	live_out_paths_from_caller_to_callee (entity caller, entity callee, live_out_summary_engine_context *ctxt)
bool	live_out_summary_paths_engine (const char *module_name)
static void	live_in_paths_of_statement (statement s, live_paths_analysis_context *ctxt)
static bool	live_out_paths_from_unstructured_to_nodes (unstructured unstr, live_paths_analysis_context *ctxt)
static bool	live_out_paths_from_forloop_to_body (forloop l, live_paths_analysis_context *ctxt)
static bool	live_out_paths_from_whileloop_to_body (whileloop l, live_paths_analysis_context *ctxt)
static void	live_in_paths_of_whileloop (whileloop l, live_paths_analysis_context *ctxt)
static bool	live_out_paths_from_loop_to_body (loop l, live_paths_analysis_context *ctxt)
static void	live_in_paths_of_loop (loop l, live_paths_analysis_context *ctxt)
static bool	live_out_paths_from_test_to_branches (test t, _UNUSED_ live_paths_analysis_context *ctxt)
static bool	live_paths_from_block_to_statements (sequence seq, live_paths_analysis_context *ctxt)
static void	live_paths_of_module_statement (statement stmt, live_paths_analysis_context *ctxt)
bool	live_paths_engine (const char *module_name, effects_representation_val representation)
static Psysteme	new_system_with_only_live_variable (Psysteme sc, reference ref, list llivein, list lliveout)
	Create a new nsc system from the sc system of a region. More...
static bool	filter_live_out_regions_statement (statement st)
	For each statement store the new live_out_regions. More...
bool	live_out_region_engine (const char *module_name, __attribute__((unused)) effects_representation_val representation)

Function Documentation

convert_in_effects()

static list convert_in_effects ( list  lin, live_paths_analysis_context *  ctxt  )

static

Definition at line 108 of file liveness_analysis_engine.c.

{
  if (!ctxt->memory_effects_only
      && !ctxt->memory_in_out_effects_only)
    lin = effects_store_effects(lin);
 
  return lin;
}

References effects_store_effects(), live_paths_analysis_context::memory_effects_only, and live_paths_analysis_context::memory_in_out_effects_only.

Referenced by live_in_paths_of_statement(), live_out_paths_from_forloop_to_body(), live_out_paths_from_loop_to_body(), live_out_paths_from_unstructured_to_nodes(), and live_out_paths_from_whileloop_to_body().

Here is the call graph for this function:

Here is the caller graph for this function:

convert_rw_effects()

static list convert_rw_effects ( list  lrw, live_paths_analysis_context *  ctxt  )

static

Definition at line 92 of file liveness_analysis_engine.c.

{
  if (!ctxt->memory_effects_only)
    lrw = effects_store_effects(lrw);
 
  return lrw;
}

References effects_store_effects(), and live_paths_analysis_context::memory_effects_only.

Referenced by live_in_paths_of_loop(), live_in_paths_of_statement(), live_in_paths_of_whileloop(), live_out_paths_from_forloop_to_body(), live_out_paths_from_loop_to_body(), and live_out_paths_from_whileloop_to_body().

Here is the call graph for this function:

Here is the caller graph for this function:

filter_live_out_regions_statement()

static bool filter_live_out_regions_statement ( statement  st )

static

For each statement store the new live_out_regions.

Definition at line 1339 of file liveness_analysis_engine.c.

                                                            {
  ifdebug(1) {
    pips_debug(1, "begin with statement:\n");
    print_statement(st);
  }
  list llivein = load_live_in_paths_list(st);
  list lliveout = load_live_out_paths_list(st);
  list loutregions = load_statement_out_regions(st);
  list lliveoutreg = NIL;
 
  FOREACH(EFFECT, reg, loutregions) {
    reference rreg = effect_any_reference(reg);
    descriptor dreg = effect_descriptor(reg);
    switch (descriptor_tag(dreg)) {
      case is_descriptor_none:
        pips_debug(3, "scalar region");
        lliveoutreg = CONS(EFFECT, (*effect_dup_func)(reg), lliveoutreg);
        break;
      case is_descriptor_convex:
      {
        pips_debug(3, "convex region");
        Psysteme sc = descriptor_convex(dreg);
        Psysteme nsc = new_system_with_only_live_variable(sc, rreg, llivein, lliveout);
        effect r = make_effect(
            copy_cell(effect_cell(reg)),
            copy_action(effect_action(reg)),
            copy_approximation(effect_approximation(reg)),
            make_descriptor_convex(nsc) );
        lliveoutreg = CONS(EFFECT, r, lliveoutreg);
        break;
      }
      case is_descriptor_convexunion:
        pips_debug(3, "convex union region");
        pips_internal_error("Not done yet...\n");
        //can use new_system_with_only_live_variable for each sc
        break;
      default:
        pips_internal_error("This case never occurs\n descriptor = %d\n", descriptor_tag(dreg));
        break;
    }
  }
 
  // memorize the new live_out_regions for the statement.
  store_live_out_regions_list(st, lliveoutreg);
 
  ifdebug(1) {
    pips_debug(1, "end statement:\n");
    print_statement(st);
  }
  return true;
}

References CONS, copy_action(), copy_approximation(), copy_cell(), descriptor_convex, descriptor_tag, EFFECT, effect_action, effect_any_reference, effect_approximation, effect_cell, effect_descriptor, effect_dup_func, FOREACH, ifdebug, is_descriptor_convex, is_descriptor_convexunion, is_descriptor_none, load_live_in_paths_list(), load_live_out_paths_list(), load_statement_out_regions(), make_descriptor_convex(), make_effect(), new_system_with_only_live_variable(), NIL, pips_debug, pips_internal_error, print_statement(), and store_live_out_regions_list().

Referenced by live_out_region_engine().

Here is the call graph for this function:

Here is the caller graph for this function:

init_live_paths_context()

static void init_live_paths_context ( live_paths_analysis_context *  ctxt, effects_representation_val  representation  )

static

Definition at line 67 of file liveness_analysis_engine.c.

{
  ctxt->memory_effects_only = get_bool_property("MEMORY_EFFECTS_ONLY");
  ctxt->memory_in_out_effects_only = get_bool_property("MEMORY_IN_OUT_EFFECTS_ONLY");
  if (!  ctxt->memory_effects_only)
    // if the MEMORY_EFFECTS_ONLY is FALSE on input,
    // we have to temporarily set MEMORY_EFFECTS_ONLY to
    // TRUE so that functions computing R/W effects
    // do not compute non memory effects which would have to be filtered.
    set_bool_property("MEMORY_EFFECTS_ONLY", true);
  ctxt->representation = representation;
}

References get_bool_property(), live_paths_analysis_context::memory_effects_only, live_paths_analysis_context::memory_in_out_effects_only, live_paths_analysis_context::representation, and set_bool_property().

Referenced by live_paths_engine().

Here is the call graph for this function:

Here is the caller graph for this function:

live_in_paths_of_loop()

static void live_in_paths_of_loop ( loop  l, live_paths_analysis_context *  ctxt  )

static

The live in paths of a loop statement are the live in paths of its header plus the live in paths of its first iteration if it is exectuted

If the loop belongs to a sequence of statements, which is generally the case, its live in paths have already been computed. I don't yet know if they may be much more precisely computed here. For performance reasons, I don't try to recompute them if they are already available. The code below is likely to be seldom executed; however, it has been tested on small cases.

Live in effects of header

We assume that there is no side effect in the loop header; thus the live in effects of the header are similar to its proper read effects

Live in effects of first iteration if it exists minus read effects on the loop index, which are masked by its initialization in the header, and read effects on loop locals if the loop is parallel;

beware: potential sharing with loop_locals(l)

free l_masked_vars: beware of the potential sharing with loop_locals

put them together

Definition at line 952 of file liveness_analysis_engine.c.

{
  /* The live in paths of a loop statement are the live in paths of its header
   * plus the live in paths of its first iteration if it is exectuted
   */
 
  statement
  current_stmt = (statement) gen_get_ancestor(statement_domain, l);
  statement
  body = loop_body(l);
  entity
  index = loop_index(l);
 
  pips_debug(1,"begin\n");
 
  /* If the loop belongs to a sequence of statements, which is
   * generally the case, its live in paths have already been computed.
   * I don't yet know if they may be much more precisely computed here.
   * For performance reasons, I don't try to recompute them if they
   * are already available.
   * The code below is likely to be seldom executed;
   * however, it has been tested on small cases.
   */
  if ( !bound_live_in_paths_p(current_stmt) )
  {
 
    /* Live in effects of header  */
    /* We assume that there is no side effect in the loop header;
     * thus the live in effects of the header are similar to its proper read effects
     */
    list l_prop_header = convert_rw_effects(load_proper_rw_effects_list(current_stmt),
        ctxt);
    list l_live_in_header =
        proper_to_summary_effects(effects_read_effects_dup(l_prop_header));
    reset_converted_rw_effects(&l_prop_header, ctxt);
    pips_debug_effects(3, "live in paths of loop header:\n", l_live_in_header);
 
    /* Live in effects of first iteration if it exists minus read effects
     * on the loop index, which are masked by its initialization in the header,
     * and read effects on loop locals if the loop is parallel;
     */
    list l_masked_vars = NIL;
    if(loop_parallel_p(l))
      l_masked_vars = loop_locals(l);
    /* beware: potential sharing with loop_locals(l) */
    l_masked_vars = CONS(ENTITY, index, l_masked_vars);
 
    list l_live_in_first_iter =
        effects_dup_without_variables(load_live_in_paths_list(body),
            l_masked_vars);
 
    /* free l_masked_vars: beware of the potential sharing with loop_locals */
    if (loop_parallel_p(l) && !ENDP(l_masked_vars))
      CDR(l_masked_vars) = NIL;
    gen_free_list(l_masked_vars);
 
    if (! normalizable_and_linear_loop_p(index, loop_range(l)))
    {
      pips_debug(7, "non linear loop range.\n");
      effects_to_may_effects(l_live_in_first_iter);
    }
    // functions that can be pointed by loop_descriptor_make_func:
    // loop_undefined_descriptor_make
    // loop_convex_descriptor_make
    else if(loop_descriptor_make_func == loop_undefined_descriptor_make)
    {
      if (loop_executed_never_p(l)) {
        //l_live_in_first_iter must had been a duplicated effect, so need to free them
        gen_full_free_list(l_live_in_first_iter);
        l_live_in_first_iter = NIL;
      }
      else if (!loop_executed_at_least_once_p(l))
        effects_to_may_effects(l_live_in_first_iter);
    }
    else
    {
      pips_internal_error("live paths of loop not implemented for convex paths\n");
    }
 
    pips_debug_effects(3, "live in paths of loop first iteration:\n", l_live_in_header);
 
    /* put them together */
    // functions that can be pointed by effects_union_op:
    // ProperEffectsMustUnion
    // RegionsMustUnion
    // ReferenceUnion
    // EffectsMustUnion
    list l_live_in_loop = (*effects_union_op)(l_live_in_header,
        l_live_in_first_iter,
        effects_same_action_p);
 
    pips_debug_effects(3, "live in paths of loop:\n", l_live_in_loop);
 
    store_live_in_paths_list(current_stmt, l_live_in_loop);
  }
 
  pips_debug(1,"end\n");
}

References bound_live_in_paths_p(), CDR, CONS, convert_rw_effects(), current_stmt, effects_dup_without_variables(), effects_read_effects_dup(), effects_same_action_p(), effects_to_may_effects(), ENDP, ENTITY, gen_free_list(), gen_full_free_list(), gen_get_ancestor(), load_live_in_paths_list(), load_proper_rw_effects_list(), loop_body, loop_descriptor_make_func, loop_executed_at_least_once_p(), loop_executed_never_p(), loop_index, loop_locals, loop_parallel_p(), loop_range, loop_undefined_descriptor_make(), NIL, normalizable_and_linear_loop_p(), pips_debug, pips_debug_effects, pips_internal_error, proper_to_summary_effects(), reset_converted_rw_effects(), statement_domain, and store_live_in_paths_list().

Referenced by live_paths_of_module_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

live_in_paths_of_statement()

static void live_in_paths_of_statement ( statement  s, live_paths_analysis_context *  ctxt  )

static

live in paths may have already been computed, for instance for sequences

First, we get the live out paths of the statement

Live_in(S) = (live_out(S) o T(S) - W(S)) U IN (S)

first take care of declarations

Definition at line 361 of file liveness_analysis_engine.c.

{
  /* live in paths may have already been computed,
   * for instance for sequences
   */
  pips_debug(1,"begin for statement with ordering: %03zd and number: %03zd\n",
      statement_ordering(s), statement_number(s));
 
  if ( !bound_live_in_paths_p(s) )
  {
    pips_debug(1, "not bound\n");
    /* First, we get the live out paths of the statement */
    list l_live_out = effects_dup(load_live_out_paths_list(s));
 
    /* Live_in(S) = (live_out(S) o T(S) - W(S)) U IN (S) */
 
    /* first take care of declarations */
    if (c_module_p(get_current_module_entity()) &&
        (declaration_statement_p(s) ))
    {
      FOREACH(ENTITY, decl, statement_declarations(s)) {
        storage decl_storage = entity_storage(decl);
        if (storage_ram_p(decl_storage)
            // keep paths on static variables
            && !static_area_p(ram_section(storage_ram(decl_storage))))
          l_live_out = filter_effects_with_declaration(l_live_out, decl);
      }
    }
 
    // then move the live_out effects of the statement in the store
    // before the statement
    transformer t = (*load_completed_transformer_func)(s);
 
    // functions that can be pointed by effects_transformer_composition_op:
    // effects_composition_with_transformer_nop
    // effects_undefined_composition_with_transformer
    // convex_regions_transformer_compose
    // simple_effects_composition_with_effect_transformer
    (*effects_transformer_composition_op)(l_live_out, t);
 
    // next, remove the effects written by the statement
    // and add the in effects of the statement
    list l_rw =  convert_rw_effects(load_rw_effects_list(s),ctxt);
    list l_write = effects_write_effects_dup(l_rw);
    pips_debug_effects(5, "write effects:\n", l_write);
 
    list l_in = convert_in_effects(load_in_effects_list(s), ctxt);
    pips_debug_effects(5, "in effects:\n", l_in);
 
    // functions that can be pointed by effects_union_op:
    // ProperEffectsMustUnion
    // RegionsMustUnion
    // ReferenceUnion
    // EffectsMustUnion
    // functions that can be pointed by effects_sup_difference_op:
    // effects_undefined_binary_operator
    // RegionsSupDifference
    // EffectsSupDifference
    list l_live_in = (*effects_union_op)(
        effects_dup(l_in),
        (*effects_sup_difference_op)(l_live_out, l_write,
            r_w_combinable_p),
            effects_same_action_p);
    pips_debug_effects(5, "resulting live in paths:\n", l_live_in);
 
 
    store_live_in_paths_list(s, l_live_in);
 
    reset_converted_rw_effects(&l_rw, ctxt);
    reset_converted_in_effects(&l_in, ctxt);
 
  }
  pips_debug(1,"end\n");
  return;
}

References bound_live_in_paths_p(), c_module_p(), convert_in_effects(), convert_rw_effects(), declaration_statement_p(), effects_dup(), effects_same_action_p(), effects_write_effects_dup(), ENTITY, entity_storage, filter_effects_with_declaration(), FOREACH, get_current_module_entity(), load_in_effects_list(), load_live_out_paths_list(), load_rw_effects_list(), pips_debug, pips_debug_effects, r_w_combinable_p(), ram_section, reset_converted_in_effects(), reset_converted_rw_effects(), statement_declarations, statement_number, statement_ordering, static_area_p(), storage_ram, storage_ram_p, and store_live_in_paths_list().

Referenced by live_paths_from_block_to_statements(), and live_paths_of_module_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

live_in_paths_of_whileloop()

static void live_in_paths_of_whileloop ( whileloop  l, live_paths_analysis_context *  ctxt  )

static

If the loop belongs to a sequence of statements, which is generally the case, its live in paths have already been computed. I don't yet know if they may be much more precisely computed here. For performance reasons, I don't try to recompute them if they are already available. see also the comment inside the else branch of if (!before_p) about the way of computing live in paths. The code below is likely to be seldom executed; however, it has been tested on small cases.

the live in paths of the loop are either those of the first iteration if there is one, or the live out paths of the whole loop is there is no iteration; we must remove the write effects and add the in effects of the condition evaluation

As we currently only compute simple live paths, I wonder if there is a difference with the live out paths of the loop body...

Get the live out paths of the whole loop

It may be executed...

...or the first iteration of the loop body

Take into account the effects of the condition

We don't have the in effects of the condition evaluation we safely approximate them by its may read proper effects if there are write effects during its evaluation

Definition at line 725 of file liveness_analysis_engine.c.

{
  statement
  current_stmt = (statement) gen_get_ancestor(statement_domain, l);
  bool before_p = evaluation_before_p(whileloop_evaluation(l));
  statement body = whileloop_body(l);
 
  list l_live_in_loop = NIL;
 
  pips_debug(1,"begin\n");
 
  /* If the loop belongs to a sequence of statements, which is
   * generally the case, its live in paths have already been computed.
   * I don't yet know if they may be much more precisely computed here.
   * For performance reasons, I don't try to recompute them if they
   * are already available.
   * see also the comment inside the else branch of if (!before_p)
   * about the way of computing live in paths.
   * The code below is likely to be seldom executed;
   * however, it has been tested on small cases.
   */
  if ( !bound_live_in_paths_p(current_stmt) )
  {
    list l_live_in_body = effects_dup(load_live_in_paths_list(body));
    pips_debug_effects(3, "live in paths of loop body:\n", l_live_in_body);
 
    if (!before_p)
    {
      pips_debug(1, "do while loop: live in paths are those of the body\n");
      l_live_in_loop = l_live_in_body;
    }
    else
    {
      /* the live in paths of the loop are either those of the
       * first iteration if there is one, or the live out paths
       * of the whole loop is there is no iteration;
       * we must remove the write effects and add the in effects
       * of the condition evaluation
       */
 
      /* As we currently only compute simple live paths,
       * I wonder if there is a difference with the live out paths
       * of the loop body...
       */
 
      /* Get the live out paths of the whole loop
       */
      list l_live_out_loop = effects_dup(load_live_out_paths_list(current_stmt));
      pips_debug_effects(3, "live out paths of whole loop:\n", l_live_out_loop);
      effects_to_may_effects(l_live_out_loop); /* It may be executed... */
 
      /* ...or the first iteration of the loop body */
      effects_to_may_effects(l_live_in_body);
 
      // functions that can be pointed by effects_union_op:
      // ProperEffectsMustUnion
      // RegionsMustUnion
      // ReferenceUnion
      // EffectsMustUnion
      list l_live_out_after_cond =
          (*effects_union_op)(l_live_out_loop,
              l_live_in_body,
              effects_same_action_p);
 
      pips_debug_effects(3, "live out paths after first condition evaluation:\n",
          l_live_out_after_cond);
 
      /* Take into account the effects of the condition */
      list l_prop_cond =
          convert_rw_effects(load_proper_rw_effects_list(current_stmt), ctxt);
 
      list l_write_cond =
          proper_to_summary_effects(effects_write_effects_dup(l_prop_cond));
      pips_debug_effects(3, "write effects of condition:\n", l_write_cond);
 
      /* We don't have the in effects of the condition evaluation
       * we safely approximate them by its may read proper effects
       * if there are write effects during its evaluation
       */
      list l_in_cond =
          proper_to_summary_effects(effects_read_effects_dup(l_prop_cond));
      if (!ENDP(l_write_cond)) effects_to_may_effects(l_in_cond);
      pips_debug_effects(3, "approximation of in effects of condition:\n",
          l_in_cond);
 
      // functions that can be pointed by effects_union_op:
      // ProperEffectsMustUnion
      // RegionsMustUnion
      // ReferenceUnion
      // EffectsMustUnion
      // functions that can be pointed by effects_sup_difference_op:
      // effects_undefined_binary_operator
      // RegionsSupDifference
      // EffectsSupDifference
      l_live_in_loop =
          (*effects_union_op)(l_in_cond,
              (*effects_sup_difference_op)(l_live_out_after_cond,
                  l_write_cond,
                  r_w_combinable_p),
                  effects_same_action_p);
 
      reset_converted_rw_effects(&l_prop_cond, ctxt);
    }
 
    pips_debug_effects(3, "live in paths of loop:\n", l_live_in_loop);
 
    store_live_in_paths_list(current_stmt, l_live_in_loop);
  }
  else
  {
    pips_debug(1, "already bound\n");
  }
 
  pips_debug(1,"end\n");
 
  return;
}

References bound_live_in_paths_p(), convert_rw_effects(), current_stmt, effects_dup(), effects_read_effects_dup(), effects_same_action_p(), effects_to_may_effects(), effects_write_effects_dup(), ENDP, evaluation_before_p, gen_get_ancestor(), load_live_in_paths_list(), load_live_out_paths_list(), load_proper_rw_effects_list(), NIL, pips_debug, pips_debug_effects, proper_to_summary_effects(), r_w_combinable_p(), reset_converted_rw_effects(), statement_domain, store_live_in_paths_list(), whileloop_body, and whileloop_evaluation.

Referenced by live_paths_of_module_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

live_in_summary_paths_engine()

bool live_in_summary_paths_engine

(

const char *

module_name

)

liveness_analysis_engine.c

Parameters

module_name

odule_name

Definition at line 130 of file liveness_analysis_engine.c.

{
  list l_glob = NIL, l_loc = NIL;
  statement module_stat;
 
  set_current_module_entity(module_name_to_entity(module_name));
  set_current_module_statement( (statement)
      db_get_memory_resource(DBR_CODE, module_name, true) );
  module_stat = get_current_module_statement();
 
  // functions that can be pointed by effects_computation_init_func:
  // effects_computation_no_init
  // init_convex_in_out_regions
  // init_convex_rw_regions
  (*effects_computation_init_func)(module_name);
 
  set_live_in_paths((*db_get_live_in_paths_func)(module_name));
 
  l_loc = load_live_in_paths_list(module_stat);
 
  // functions that can be pointed by effects_local_to_global_translation_op:
  // effects_dynamic_elim
  // regions_dynamic_elim
  l_glob = (*effects_local_to_global_translation_op)(l_loc);
 
  (*db_put_live_in_summary_paths_func)(module_name, l_glob);
 
  reset_current_module_entity();
  reset_current_module_statement();
  reset_live_in_paths();
 
  // functions that can be pointed by effects_computation_reset_func:
  // effects_computation_no_reset
  // reset_convex_in_out_regions
  // reset_convex_rw_regions
  (*effects_computation_reset_func)(module_name);
 
  return true;
}

References db_get_live_in_paths_func, db_get_memory_resource(), get_current_module_statement(), load_live_in_paths_list(), module_name(), module_name_to_entity(), NIL, reset_current_module_entity(), reset_current_module_statement(), reset_live_in_paths(), set_current_module_entity(), set_current_module_statement(), and set_live_in_paths().

Here is the call graph for this function:

live_out_paths_from_call_site_to_callee()

static bool live_out_paths_from_call_site_to_callee ( call  c, live_out_summary_engine_context *  ctxt  )

static

there is a problem here because the context is in the store preceding the statement whereas live_out_paths hold after the statement. So I think I must apply the transformer to get the post-condition. That's ok for simple paths since they are store independent. BC.

There may also be a problem here in C, because calls may be anywhere inside an expression, and not solely as standalone statements. It may be better to call this function during the intraprocedural analysis of callers and not during a standalone phase which would have to deal with calls in sub-expressions, and thus also with store/pointers modifications. BC.

Definition at line 209 of file liveness_analysis_engine.c.

{
  pips_debug(1, "considering call to %s\n", entity_name(call_function(c)));
  pips_debug(2, "current context callee: %s\n",  entity_name(ctxt->current_callee));
 
  if (call_function(c) != ctxt->current_callee)
  {
    return (true);
  }
  pips_debug(1, "good candidate\n");
 
  statement current_stmt = (statement) gen_get_ancestor(statement_domain, c);
 
  /* there is a problem here because the context is in the store preceding the statement
   * whereas live_out_paths hold after the statement.
   * So I think I must apply the transformer to get the post-condition.
   * That's ok for simple paths since they are store independent. BC.
   */
  transformer stmt_context = (*load_context_func)(current_stmt);
 
  /* There may also be a problem here in C, because calls may be
   * anywhere inside an expression, and not solely as standalone
   * statements.  It may be better to call this function during the
   * intraprocedural analysis of callers and not during a standalone
   * phase which would have to deal with calls in sub-expressions,
   * and thus also with store/pointers modifications.
   * BC.
   */
  list l_out = load_live_out_paths_list(current_stmt);
 
  pips_debug_effects(3, "current statement live_out_paths:\n", l_out);
  list l_paths = generic_effects_forward_translation(ctxt->current_callee,
      call_arguments(c), l_out,
      stmt_context);
  update_live_out_summary_engine_context_paths(ctxt, l_paths);
  return true;
}

References call_arguments, call_function, live_out_summary_engine_context::current_callee, current_stmt, entity_name, gen_get_ancestor(), generic_effects_forward_translation(), load_live_out_paths_list(), pips_debug, pips_debug_effects, statement_domain, and update_live_out_summary_engine_context_paths().

Referenced by live_out_paths_from_caller_to_callee().

Here is the call graph for this function:

Here is the caller graph for this function:

live_out_paths_from_caller_to_callee()

static void live_out_paths_from_caller_to_callee ( entity  caller, entity  callee, live_out_summary_engine_context *  ctxt  )

static

All we need to perform the translation

Definition at line 256 of file liveness_analysis_engine.c.

{
  const char *caller_name;
  statement caller_statement;
 
  reset_current_module_entity();
  set_current_module_entity(caller);
  caller_name = module_local_name(caller);
  pips_debug(2, "begin for caller: %s, and callee: %s\n", caller_name,
      entity_name(callee));
  pips_debug(2, "current context callee: %s\n",  entity_name(ctxt->current_callee));
  /* All we need to perform the translation */
  set_current_module_statement( (statement)
      db_get_memory_resource(DBR_CODE, caller_name, true) );
  caller_statement = get_current_module_statement();
 
  // functions that can be pointed by effects_computation_init_func:
  // effects_computation_no_init
  // init_convex_in_out_regions
  // init_convex_rw_regions
  (*effects_computation_init_func)(caller_name);
 
  set_live_out_paths( (*db_get_live_out_paths_func)(caller_name));
 
  make_statement_global_stack(); // in case the semantics library is used
 
  //ctxt->current_callee = callee;
  gen_context_multi_recurse(caller_statement, ctxt,
      statement_domain, live_out_summary_paths_stmt_filter, gen_null,
      call_domain, live_out_paths_from_call_site_to_callee, gen_null,
      NULL);
 
  free_statement_global_stack(); // in case the semantics library is used
 
  reset_live_out_paths();
  reset_current_module_entity();
  set_current_module_entity(callee);
  reset_current_module_statement();
 
  // functions that can be pointed by effects_computation_reset_func:
  // effects_computation_no_reset
  // reset_convex_in_out_regions
  // reset_convex_rw_regions
  (*effects_computation_reset_func)(caller_name);
}

References call_domain, callee, caller_name, live_out_summary_engine_context::current_callee, db_get_live_out_paths_func, db_get_memory_resource(), entity_name, free_statement_global_stack(), gen_context_multi_recurse(), gen_null(), get_current_module_statement(), live_out_paths_from_call_site_to_callee(), live_out_summary_paths_stmt_filter(), make_statement_global_stack(), module_local_name(), pips_debug, reset_current_module_entity(), reset_current_module_statement(), reset_live_out_paths(), set_current_module_entity(), set_current_module_statement(), set_live_out_paths(), and statement_domain.

Referenced by live_out_summary_paths_engine().

Here is the call graph for this function:

Here is the caller graph for this function:

live_out_paths_from_forloop_to_body()

static bool live_out_paths_from_forloop_to_body ( forloop  l, live_paths_analysis_context *  ctxt  )

static

The live out paths of an iteration are the paths that

• belong to the live in paths of the next iteration if it exists, that is to say if the condition evaluates to true; the write effects of the condition evaluation mask the live in paths of the next iteration; and the in effects of the condition evaluation must be added.
• or belong to the live out of the whole loop if the next iteration does not exist. However, the condition is evaluated, and its write effects mask the live out paths at the end of the whole loop.

First, we get the live out paths of the whole loop

It may be executed...

...or another next iteration of the loop body

Take into account the effects of the header

We don't have the in effects of the header evaluation we safely approximate them by its may read proper effects if there are write effects during its evaluation We could be much more precise here by distinguishing the three different components and re-computing their effects. However, for loops are generally converted to loops or while loops by the controlizer, so I leave this as it is for the time being.

Definition at line 532 of file liveness_analysis_engine.c.

{
  statement
  current_stmt = (statement) gen_get_ancestor(statement_domain, l);
  statement body = forloop_body(l);
 
  pips_debug(1,"begin\n");
 
  /* The live out paths of an iteration are the paths that
   *   - belong to the live in paths of the next iteration if it exists,
   *     that is to say if the condition evaluates to true;
   *     the write effects of the condition evaluation mask the
   *     live in paths of the next iteration; and the in effects
   *     of the condition evaluation must be added.
   *   - or belong to the live out of the whole loop if the next iteration
   *     does not exist. However, the condition is evaluated,
   *     and its write effects mask the live out paths at the end of the
   *     whole loop.
   */
 
  /* First, we get the live out paths of the whole loop
   */
  list l_live_out_loop = effects_dup(load_live_out_paths_list(current_stmt));
  pips_debug_effects(3, "live out paths of whole loop:\n", l_live_out_loop);
  effects_to_may_effects(l_live_out_loop); /* It may be executed... */
 
  /* ...or another next iteration of the loop body */
  list l_in_next_iter = convert_in_effects(load_invariant_in_effects_list(body), ctxt);
  list l_in_next_iter_may = effects_dup(l_in_next_iter);
  effects_to_may_effects(l_in_next_iter_may);
  pips_debug_effects(3, "(may) in effects of next iterations:\n",
      l_in_next_iter_may);
  reset_converted_in_effects(&l_in_next_iter, ctxt);
 
  // functions that can be pointed by effects_union_op:
  // ProperEffectsMustUnion
  // RegionsMustUnion
  // ReferenceUnion
  // EffectsMustUnion
  list l_live_out_after_cond =
      (*effects_union_op)(l_live_out_loop,
          l_in_next_iter_may,
          effects_same_action_p);
 
  pips_debug_effects(3, "live out paths after header evaluation:\n",
      l_live_out_after_cond);
 
  /* Take into account the effects of the header */
  list l_prop_cond = convert_rw_effects(load_proper_rw_effects_list(current_stmt),
      ctxt);
 
  list l_write_cond =
      proper_to_summary_effects(effects_write_effects_dup(l_prop_cond));
  pips_debug_effects(3, "write effects of condition:\n", l_write_cond);
 
 
  /* We don't have the in effects of the header evaluation
   * we safely approximate them by its may read proper effects
   * if there are write effects during its evaluation
   * We could be much more precise here by distinguishing
   * the three different components and re-computing their effects.
   * However, for loops are generally converted to loops or while loops
   * by the controlizer, so I leave this as it is for the time being.
   */
  list l_in_cond =
      proper_to_summary_effects(effects_read_effects_dup(l_prop_cond));
  if (!ENDP(l_write_cond)) effects_to_may_effects(l_in_cond);
  pips_debug_effects(3, "approximation of in effects of condition:\n", l_in_cond);
 
  // functions that can be pointed by effects_union_op:
  // ProperEffectsMustUnion
  // RegionsMustUnion
  // ReferenceUnion
  // EffectsMustUnion
  // functions that can be pointed by effects_sup_difference_op:
  // effects_undefined_binary_operator
  // RegionsSupDifference
  // EffectsSupDifference
  list l_live_out_body =
      (*effects_union_op)(l_in_cond,
          (*effects_sup_difference_op)(l_live_out_after_cond,
              l_write_cond,
              r_w_combinable_p),
              effects_same_action_p);
 
 
  reset_converted_rw_effects(&l_prop_cond, ctxt);
 
  pips_debug_effects(3, "live out paths of loop body:\n", l_live_out_body);
 
  store_live_out_paths_list(body, l_live_out_body);
 
  pips_debug(1,"end\n");
 
  return true;
}

References convert_in_effects(), convert_rw_effects(), current_stmt, effects_dup(), effects_read_effects_dup(), effects_same_action_p(), effects_to_may_effects(), effects_write_effects_dup(), ENDP, forloop_body, gen_get_ancestor(), load_invariant_in_effects_list(), load_live_out_paths_list(), load_proper_rw_effects_list(), pips_debug, pips_debug_effects, proper_to_summary_effects(), r_w_combinable_p(), reset_converted_in_effects(), reset_converted_rw_effects(), statement_domain, and store_live_out_paths_list().

Referenced by live_paths_of_module_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

live_out_paths_from_loop_to_body()

static bool live_out_paths_from_loop_to_body ( loop  l, live_paths_analysis_context *  ctxt  )

static

First, we get the live out paths of the statement corresponding to the whole loop

We then compute the live out paths of the loop body

The live out paths of an iteration are the paths that

• belong to the in effects of the next iterations if there exist some, except for the loop locals if the loop is parallel;
• or belong to the live out of the whole loop if the next iteration does not exist.
• to these, for the C language, we must add the read effects resulting from the evaluation of the incremental expression and of the upper bound. This includes an exact path for the loop index.

Definition at line 845 of file liveness_analysis_engine.c.

{
  statement
  current_stmt = (statement) gen_get_ancestor(statement_domain, l);
  statement
  body = loop_body(l);
  entity
  index = loop_index(l);
 
  pips_debug(1,"begin\n");
 
  /* First, we get the live out paths of the statement corresponding to the
   * whole loop
   */
  list l_live_out_loop = effects_dup(load_live_out_paths_list(current_stmt));
  pips_debug_effects(3, "live out paths of whole loop:\n", l_live_out_loop);
 
  list l_rw_body = convert_rw_effects(load_rw_effects_list(body),
      ctxt);
  list l_w_body = effects_write_effects_dup(l_rw_body);
  reset_converted_rw_effects(&l_rw_body, ctxt);
 
  if (loop_executed_never_p(l)) {
    //l_w_body must had been a duplicated effect, so need to free them
    gen_full_free_list(l_w_body);
    l_w_body = NIL;
  }
  else if (!loop_executed_at_least_once_p(l))
    effects_to_may_effects(l_w_body);
  // functions that can be pointed by effects_sup_difference_op:
  // effects_undefined_binary_operator
  // RegionsSupDifference
  // EffectsSupDifference
  l_live_out_loop = (*effects_sup_difference_op)(l_live_out_loop, l_w_body,
      r_w_combinable_p);
  pips_debug_effects(3, "live out paths of an iteration due to live out paths of whole loop\n", l_live_out_loop);
 
 
  /* We then compute the live out paths of the loop body */
  /* The live out paths of an iteration are the paths that
   *   - belong to the in effects of the next iterations if there exist some,
   *     except for the loop locals if the loop is parallel;
   *   - or belong to the live out of the whole loop if the next iteration
   *     does not exist.
   *   - to these, for the C language, we must add the read effects resulting
   *     from the evaluation of the incremental expression and of the upper
   *     bound. This includes an exact path for the loop index.
   */
  list l_masked_vars = NIL;
  if(loop_parallel_p(l))
    l_masked_vars = loop_locals(l);
 
  list l_inv_in_body = convert_in_effects(load_invariant_in_effects_list(body), ctxt);
  list l_inv_in_body_may =
      effects_dup_without_variables(l_inv_in_body, l_masked_vars);
  effects_to_may_effects(l_inv_in_body_may);
  pips_debug_effects(3, "(may) live in paths of an iteration:\n", l_inv_in_body_may);
 
  // functions that can be pointed by effects_union_op:
  // ProperEffectsMustUnion
  // RegionsMustUnion
  // ReferenceUnion
  // EffectsMustUnion
  list l_live_out_body = (*effects_union_op)(l_live_out_loop,
      l_inv_in_body_may,
      effects_same_action_p);
  reset_converted_in_effects(&l_inv_in_body, ctxt);
 
  list l_prop_header = convert_rw_effects(load_proper_rw_effects_list(current_stmt),
      ctxt);
  list l_live_in_header =
      proper_to_summary_effects(effects_read_effects_dup(l_prop_header));
  reset_converted_rw_effects(&l_prop_header, ctxt);
  // functions that can be pointed by reference_to_effect_func:
  // reference_to_simple_effect
  // reference_to_convex_region
  // reference_to_reference_effect
  list l_index = CONS(EFFECT,
      (*reference_to_effect_func)(make_reference(index, NIL), make_action_read_memory(), false),
      NIL);
  // functions that can be pointed by effects_union_op:
  // ProperEffectsMustUnion
  // RegionsMustUnion
  // ReferenceUnion
  // EffectsMustUnion
  l_live_in_header = (*effects_union_op)(l_index, l_live_in_header, effects_same_action_p);
 
  pips_debug_effects(3, "live in paths of loop header:\n", l_live_in_header);
 
  // functions that can be pointed by effects_union_op:
  // ProperEffectsMustUnion
  // RegionsMustUnion
  // ReferenceUnion
  // EffectsMustUnion
  l_live_out_body = (*effects_union_op)(l_live_out_body,
      l_live_in_header,
      effects_same_action_p);
 
  pips_debug_effects(3, "live out paths of loop body:\n", l_live_out_body);
 
  store_live_out_paths_list(body, l_live_out_body);
 
  pips_debug(1,"end\n");
  return true;
}

References CONS, convert_in_effects(), convert_rw_effects(), current_stmt, EFFECT, effects_dup(), effects_dup_without_variables(), effects_read_effects_dup(), effects_same_action_p(), effects_to_may_effects(), effects_write_effects_dup(), gen_full_free_list(), gen_get_ancestor(), load_invariant_in_effects_list(), load_live_out_paths_list(), load_proper_rw_effects_list(), load_rw_effects_list(), loop_body, loop_executed_at_least_once_p(), loop_executed_never_p(), loop_index, loop_locals, loop_parallel_p(), make_action_read_memory(), make_reference(), NIL, pips_debug, pips_debug_effects, proper_to_summary_effects(), r_w_combinable_p(), reference_to_effect_func, reset_converted_in_effects(), reset_converted_rw_effects(), statement_domain, and store_live_out_paths_list().

Referenced by live_paths_of_module_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

live_out_paths_from_test_to_branches()

static bool live_out_paths_from_test_to_branches ( test  t, _UNUSED_ live_paths_analysis_context *  ctxt  )

static

First, we get the live out paths of the statement corresponding to the test

The live out paths for each branch are the live_out_paths of the test

The live in paths of the test are computed with the surrounding sequence live paths computation.

Definition at line 1052 of file liveness_analysis_engine.c.

{
  statement
    current_stmt = (statement) gen_get_ancestor(statement_domain, t);
 
  pips_debug(1,"begin\n");
 
  /* First, we get the live out paths of the statement corresponding to the test
   */
  list l_live_out_test = load_live_out_paths_list(current_stmt);
 
  /* The live out paths for each branch are the live_out_paths
     of the test
  */
  store_live_out_paths_list(test_true(t), effects_dup(l_live_out_test));
  store_live_out_paths_list(test_false(t), effects_dup(l_live_out_test));
  
 
  /* The live in paths of the test are computed with  the surrounding
     sequence live paths computation.
  */
  pips_debug(1,"end\n");
 
  return true;
}

References current_stmt, effects_dup(), gen_get_ancestor(), load_live_out_paths_list(), pips_debug, statement_domain, store_live_out_paths_list(), test_false, and test_true.

Referenced by live_paths_of_module_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

live_out_paths_from_unstructured_to_nodes()

static bool live_out_paths_from_unstructured_to_nodes ( unstructured  unstr, live_paths_analysis_context *  ctxt  )

static

Adopt a very conservative strategy: live_out(node)= live_out(unstructured)*may U (U_{n \in nodes} IN(nodes)) If convex paths were to be computed, transformers should be taken into account.

The exit node is a particular case: its live_out paths are the live_out paths of the unstructured.

there is only one statement in u;

It may be executed...

be sure live_out paths are not stored twice, in particular for the exit node

Definition at line 439 of file liveness_analysis_engine.c.

{
  pips_debug(1,"begin\n");
 
  /* Adopt a very conservative strategy:
   * live_out(node)=  live_out(unstructured)*may U (U_{n \in nodes} IN(nodes))
   * If convex paths were to be computed, transformers should be taken into account.
   */
  /* The exit node is a particular case: its live_out paths are the live_out paths
   * of the unstructured.
   */
 
  statement
  current_stmt = (statement) gen_get_ancestor(statement_domain, unstr);
  control exit_ctrl = unstructured_exit( unstr );
  statement exit_node = control_statement(exit_ctrl);
 
  list l_live_out_unstr = effects_dup(load_live_out_paths_list(current_stmt));
  pips_debug_effects(3, "live out paths of whole unstructured:\n", l_live_out_unstr);
  store_live_out_paths_list(exit_node, l_live_out_unstr);
 
  if(control_predecessors(exit_ctrl) == NIL && control_successors(exit_ctrl) == NIL)
  {
    /* there is only one statement in u; */
    pips_debug(6, "unique node\n");
  }
  else
  {
    l_live_out_unstr = effects_dup(l_live_out_unstr);
    effects_to_may_effects(l_live_out_unstr); /* It may be executed... */
 
    list l_in = NIL;
 
    list l_nodes = NIL;
    UNSTRUCTURED_CONTROL_MAP
    (ctrl, unstr, l_nodes,
        {
            statement node_stmt = control_statement(ctrl);
            pips_debug(3, "visiting node statement with ordering: "
                "%03zd and number: %03zd\n",
                statement_ordering(node_stmt),
                statement_number(node_stmt));
 
            list l_in_node = convert_in_effects(load_in_effects_list(node_stmt), ctxt);
            list l_in_node_may = effects_dup(l_in_node);
            effects_to_may_effects(l_in_node_may);
 
            // functions that can be pointed by effects_union_op:
            // ProperEffectsMustUnion
            // RegionsMustUnion
            // ReferenceUnion
            // EffectsMustUnion
            l_in = (*effects_union_op)(l_in_node_may, l_in,
                effects_same_action_p);
            pips_debug_effects(5, "current in effects:\n", l_in);
            reset_converted_in_effects(&l_in_node, ctxt);
        });
 
    // functions that can be pointed by effects_union_op:
    // ProperEffectsMustUnion
    // RegionsMustUnion
    // ReferenceUnion
    // EffectsMustUnion
    list l_live_out_nodes = (*effects_union_op)(l_in, l_live_out_unstr,
        effects_same_action_p);
    pips_debug_effects(3, "l_live_out_nodes:\n", l_live_out_nodes);
 
    FOREACH(CONTROL, ctrl, l_nodes)
    {
 
      statement node_stmt = control_statement(ctrl);
 
      /* be sure live_out paths are not stored twice, in particular
             for the exit node
       */
      if ( !bound_live_out_paths_p(node_stmt) )
      {
        pips_debug(3, "storing live out paths for node statement "
            "with ordering: %03zd and number: %03zd\n",
            statement_ordering(node_stmt),
            statement_number(node_stmt));
        store_live_out_paths_list(node_stmt, effects_dup(l_live_out_nodes));
      }
    }
  }
 
  pips_debug(1,"end\n");
 
  return true;
}

References bound_live_out_paths_p(), CONTROL, control_predecessors, control_statement, control_successors, convert_in_effects(), current_stmt, effects_dup(), effects_same_action_p(), effects_to_may_effects(), FOREACH, gen_get_ancestor(), load_in_effects_list(), load_live_out_paths_list(), NIL, pips_debug, pips_debug_effects, reset_converted_in_effects(), statement_domain, statement_number, statement_ordering, store_live_out_paths_list(), UNSTRUCTURED_CONTROL_MAP, and unstructured_exit.

Referenced by live_paths_of_module_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

live_out_paths_from_whileloop_to_body()

static bool live_out_paths_from_whileloop_to_body ( whileloop  l, live_paths_analysis_context *  ctxt  )

static

The live out paths of an iteration are the paths that

• belong to the live in paths of the next iteration if it exists, that is to say if the condition evaluates to true; the write effects of the condition evaluation mask the live in paths of the next iteration; and the in effects of the condition evaluation must be added.
• or belong to the live out of the whole loop if the next iteration does not exist. However, the condition is evaluated, and its write effects mask the live out paths at the end of the whole loop.

First, we get the live out paths of the whole loop

It may be executed...

...or another next iteration of the loop body

Take into account the effects of the condition

We don't have the in effects of the condition evaluation we safely approximate them by its may read proper effects if there are write effects during its evaluation

Definition at line 631 of file liveness_analysis_engine.c.

{
  statement
  current_stmt = (statement) gen_get_ancestor(statement_domain, l);
  statement body = whileloop_body(l);
 
  pips_debug(1,"begin\n");
 
  /* The live out paths of an iteration are the paths that
   *   - belong to the live in paths of the next iteration if it exists,
   *     that is to say if the condition evaluates to true;
   *     the write effects of the condition evaluation mask the
   *     live in paths of the next iteration; and the in effects
   *     of the condition evaluation must be added.
   *   - or belong to the live out of the whole loop if the next iteration
   *     does not exist. However, the condition is evaluated,
   *     and its write effects mask the live out paths at the end of the
   *     whole loop.
   */
 
  /* First, we get the live out paths of the whole loop
   */
  list l_live_out_loop = effects_dup(load_live_out_paths_list(current_stmt));
  pips_debug_effects(3, "live out paths of whole loop:\n", l_live_out_loop);
  effects_to_may_effects(l_live_out_loop); /* It may be executed... */
 
  /* ...or another next iteration of the loop body */
  list l_in_next_iter = convert_in_effects(load_invariant_in_effects_list(body), ctxt);
  list l_in_next_iter_may = effects_dup(l_in_next_iter);
  effects_to_may_effects(l_in_next_iter_may);
  pips_debug_effects(3, "(may) in effects of next iterations:\n",
      l_in_next_iter_may);
  reset_converted_in_effects(&l_in_next_iter, ctxt);
 
  // functions that can be pointed by effects_union_op:
  // ProperEffectsMustUnion
  // RegionsMustUnion
  // ReferenceUnion
  // EffectsMustUnion
  list l_live_out_after_cond =
      (*effects_union_op)(l_live_out_loop,
          l_in_next_iter_may,
          effects_same_action_p);
 
  pips_debug_effects(3, "live out paths after any condition evaluation:\n",
      l_live_out_after_cond);
 
  /* Take into account the effects of the condition */
  list l_prop_cond = convert_rw_effects(load_proper_rw_effects_list(current_stmt),
      ctxt);
 
  list l_write_cond =
      proper_to_summary_effects(effects_write_effects_dup(l_prop_cond));
  pips_debug_effects(3, "write effects of condition:\n", l_write_cond);
 
 
  /* We don't have the in effects of the condition evaluation
   * we safely approximate them by its may read proper effects
   * if there are write effects during its evaluation
   */
  list l_in_cond =
      proper_to_summary_effects(effects_read_effects_dup(l_prop_cond));
  if (!ENDP(l_write_cond)) effects_to_may_effects(l_in_cond);
  pips_debug_effects(3, "approximation of in effects of condition:\n", l_in_cond);
 
  // functions that can be pointed by effects_union_op:
  // ProperEffectsMustUnion
  // RegionsMustUnion
  // ReferenceUnion
  // EffectsMustUnion
  // functions that can be pointed by effects_sup_difference_op:
  // effects_undefined_binary_operator
  // RegionsSupDifference
  // EffectsSupDifference
  list l_live_out_body =
      (*effects_union_op)(l_in_cond,
          (*effects_sup_difference_op)(l_live_out_after_cond,
              l_write_cond,
              r_w_combinable_p),
              effects_same_action_p);
 
 
  reset_converted_rw_effects(&l_prop_cond, ctxt);
 
  pips_debug_effects(3, "live out paths of loop body:\n", l_live_out_body);
 
  store_live_out_paths_list(body, l_live_out_body);
 
  pips_debug(1,"end\n");
 
  return true;
}

References convert_in_effects(), convert_rw_effects(), current_stmt, effects_dup(), effects_read_effects_dup(), effects_same_action_p(), effects_to_may_effects(), effects_write_effects_dup(), ENDP, gen_get_ancestor(), load_invariant_in_effects_list(), load_live_out_paths_list(), load_proper_rw_effects_list(), pips_debug, pips_debug_effects, proper_to_summary_effects(), r_w_combinable_p(), reset_converted_in_effects(), reset_converted_rw_effects(), statement_domain, store_live_out_paths_list(), and whileloop_body.

Referenced by live_paths_of_module_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

live_out_region_engine()

bool live_out_region_engine	(	const char *	module_name,
		__attribute__((unused)) effects_representation_val	representation
	)

Definition at line 1394 of file liveness_analysis_engine.c.

                                                                                                                        {
  statement module_statement;
  bool good_result_p = true;
 
  debug_on("GMRE_DEBUG_LEVEL");
  pips_debug(1, "begin\n");
 
  //-- configure environment --//
  set_current_module_entity(module_name_to_entity(module_name));
 
  set_current_module_statement( (statement)
      db_get_memory_resource(DBR_CODE, module_name, true) );
  module_statement = get_current_module_statement();
 
  pips_assert("Statement should be OK before...",
      statement_consistent_p(module_statement));
 
  init_live_out_regions();
 
  //-- get dependencies --//
  set_out_effects((statement_effects)
      db_get_memory_resource(DBR_OUT_REGIONS, module_name, true));
  set_live_out_paths((statement_effects)
      db_get_memory_resource(DBR_LIVE_OUT_PATHS, module_name, true));
  set_live_in_paths((statement_effects)
      db_get_memory_resource(DBR_LIVE_IN_PATHS, module_name, true));
 
 
  //-- Make the job -- //
  gen_recurse(module_statement, statement_domain,
      filter_live_out_regions_statement, gen_null);
 
  //-- Save modified code to database --//
  DB_PUT_MEMORY_RESOURCE(DBR_LIVE_OUT_REGIONS, module_name,
      (statement_effects) get_live_out_regions());
 
 
  //-- reset module and dependencies --//
  reset_current_module_statement();
  reset_current_module_entity();
 
  reset_out_effects();
  reset_live_out_paths();
  reset_live_in_paths();
  reset_live_out_regions();
 
  pips_debug(1, "end\n");
  debug_off();
 
  return (good_result_p);
}

References db_get_memory_resource(), DB_PUT_MEMORY_RESOURCE, debug_off, debug_on, filter_live_out_regions_statement(), gen_null(), gen_recurse, get_current_module_statement(), get_live_out_regions(), init_live_out_regions(), module_name(), module_name_to_entity(), module_statement, pips_assert, pips_debug, reset_current_module_entity(), reset_current_module_statement(), reset_live_in_paths(), reset_live_out_paths(), reset_live_out_regions(), reset_out_effects(), set_current_module_entity(), set_current_module_statement(), set_live_in_paths(), set_live_out_paths(), set_out_effects(), statement_consistent_p(), and statement_domain.

Here is the call graph for this function:

live_out_summary_paths_engine()

bool live_out_summary_paths_engine

(

const char *

module_name

)

Look for all call sites in the callers

Parameters

module_name

odule_name

Definition at line 304 of file liveness_analysis_engine.c.

{
  /* Look for all call sites in the callers */
  callees callers = (callees) db_get_memory_resource(DBR_CALLERS,
                                                     module_name,
                                                     true);
  entity callee = module_name_to_entity(module_name);
 
  set_current_module_entity(callee);
  make_effects_private_current_context_stack();
 
  ifdebug(1)
    {
      pips_debug(1, "begin for %s with %td callers\n",
                 module_name,
                 gen_length(callees_callees(callers)));
      FOREACH(STRING, caller_name, callees_callees(callers))
        {fprintf(stderr, "%s, ", caller_name);}
      fprintf(stderr, "\n");
    }
 
  live_out_summary_engine_context ctxt;
  set_live_out_summary_engine_context(&ctxt, callee);
  debug_on("LIVE_PATHS_DEBUG_LEVEL");
  FOREACH(STRING, caller_name, callees_callees(callers))
    {
      entity caller = module_name_to_entity(caller_name);
      live_out_paths_from_caller_to_callee(caller, callee, &ctxt);
    }
  debug_off();
  if (list_undefined_p(ctxt.l_current_paths))
    ctxt.l_current_paths = NIL;
  (*db_put_live_out_summary_paths_func)(module_name, ctxt.l_current_paths);
 
  ifdebug(1)
    {
      set_current_module_statement( (statement)
                                    db_get_memory_resource(DBR_CODE,
                                                           module_local_name(callee),
                                                           true) );
 
      pips_debug(1, "live out paths for module %s:\n", module_name);
      (*effects_prettyprint_func)(ctxt.l_current_paths);
      pips_debug(1, "end\n");
      reset_current_module_statement();
    }
 
  reset_live_out_summary_engine_context(&ctxt);
  reset_current_module_entity();
  free_effects_private_current_context_stack();
 
  return true;
}

References callee, callees_callees, caller_name, db_get_memory_resource(), debug_off, debug_on, FOREACH, fprintf(), free_effects_private_current_context_stack(), gen_length(), ifdebug, live_out_summary_engine_context::l_current_paths, list_undefined_p, live_out_paths_from_caller_to_callee(), make_effects_private_current_context_stack(), module_local_name(), module_name(), module_name_to_entity(), NIL, pips_debug, reset_current_module_entity(), reset_current_module_statement(), reset_live_out_summary_engine_context(), set_current_module_entity(), set_current_module_statement(), set_live_out_summary_engine_context(), and STRING.

Here is the call graph for this function:

live_out_summary_paths_stmt_filter()

static bool live_out_summary_paths_stmt_filter ( statement  s, __attribute__((unused)) live_out_summary_engine_context *  ctxt  )

static

Definition at line 248 of file liveness_analysis_engine.c.

{
    pips_debug(1, "statement %03zd\n", statement_number(s));
    return(true);
}

References pips_debug, and statement_number.

Referenced by live_out_paths_from_caller_to_callee().

Here is the caller graph for this function:

live_paths_engine()

bool live_paths_engine	(	const char *	module_name,
		effects_representation_val	representation
	)

Get the code of the module.

Get the various effects and in_effects of the module.

Initialize the map for live_out and live_int paths

Get the live_out_summary_paths of the current module

And stores them as the live out paths of the module statement

Compute the live paths of the module.

Parameters

module_name	odule_name
representation	epresentation

Definition at line 1178 of file liveness_analysis_engine.c.

{
  debug_on("LIVE_PATHS_DEBUG_LEVEL");
  pips_debug(1, "begin\n");
 
  set_current_module_entity(module_name_to_entity(module_name));
 
  /* Get the code of the module. */
  set_current_module_statement( (statement)
      db_get_memory_resource(DBR_CODE, module_name, true) );
  statement module_statement = get_current_module_statement();
 
 
  make_effects_private_current_context_stack();
  // functions that can be pointed by effects_computation_init_func:
  // effects_computation_no_init
  // init_convex_in_out_regions
  // init_convex_rw_regions
  (*effects_computation_init_func)(module_name);
 
  /* Get the various effects and in_effects of the module. */
 
  set_proper_rw_effects((*db_get_proper_rw_effects_func)(module_name));
  set_rw_effects((*db_get_rw_effects_func)(module_name));
  set_invariant_rw_effects((*db_get_invariant_rw_effects_func)(module_name));
 
  set_cumulated_in_effects((*db_get_cumulated_in_effects_func)(module_name));
  set_in_effects((*db_get_in_effects_func)(module_name));
  set_invariant_in_effects((*db_get_invariant_in_effects_func)(module_name));
 
 
  /* Initialize the map for live_out and live_int paths */
  init_live_in_paths();
  init_live_out_paths();
 
  /* Get the live_out_summary_paths of the current module */
  list l_sum_live_out = (*db_get_live_out_summary_paths_func)(module_name);
  /* And stores them as the live out paths of the module statement */
  store_live_out_paths_list(module_statement, effects_dup(l_sum_live_out));
 
  /* Compute the live paths of the module. */
  live_paths_analysis_context ctxt;
  init_live_paths_context(&ctxt, representation);
  live_paths_of_module_statement(module_statement, &ctxt);
  reset_live_paths_context(&ctxt);
 
  pips_debug(1, "end\n");
 
  (*db_put_live_out_paths_func)(module_name, get_live_out_paths());
  (*db_put_live_in_paths_func)(module_name, get_live_in_paths());
 
  reset_proper_rw_effects();
  reset_rw_effects();
  reset_invariant_rw_effects();
  reset_in_effects();
  reset_cumulated_in_effects();
  reset_invariant_in_effects();
  reset_live_in_paths();
  reset_live_out_paths();
  // functions that can be pointed by effects_computation_reset_func:
  // effects_computation_no_reset
  // reset_convex_in_out_regions
  // reset_convex_rw_regions
  (*effects_computation_reset_func)(module_name);
 
  free_effects_private_current_context_stack();
 
  reset_current_module_entity();
  reset_current_module_statement();
  pips_debug(1, "end\n");
 
  debug_off();
  return true;
}

References db_get_cumulated_in_effects_func, db_get_in_effects_func, db_get_invariant_in_effects_func, db_get_invariant_rw_effects_func, db_get_memory_resource(), db_get_proper_rw_effects_func, db_get_rw_effects_func, debug_off, debug_on, effects_dup(), free_effects_private_current_context_stack(), get_current_module_statement(), get_live_in_paths(), get_live_out_paths(), init_live_in_paths(), init_live_out_paths(), init_live_paths_context(), live_paths_of_module_statement(), make_effects_private_current_context_stack(), module_name(), module_name_to_entity(), module_statement, pips_debug, reset_cumulated_in_effects(), reset_current_module_entity(), reset_current_module_statement(), reset_in_effects(), reset_invariant_in_effects(), reset_invariant_rw_effects(), reset_live_in_paths(), reset_live_out_paths(), reset_live_paths_context(), reset_proper_rw_effects(), reset_rw_effects(), set_cumulated_in_effects(), set_current_module_entity(), set_current_module_statement(), set_in_effects(), set_invariant_in_effects(), set_invariant_rw_effects(), set_proper_rw_effects(), set_rw_effects(), and store_live_out_paths_list().

Here is the call graph for this function:

live_paths_from_block_to_statements()

static bool live_paths_from_block_to_statements ( sequence  seq, live_paths_analysis_context *  ctxt  )

static

reversed version of the sequence to avoid recursion

the live out paths of the current statement are the live in paths of the next statement (or the live out of the while block if last statement)

Now let us compute the live in paths

The block live in paths are the live in paths of the first statement which is the last visited statement. However, in case of nested sequences, which may be the case when there are macros for instance, the live_in paths may have already been computed. It's not yet clear if the effects we have just computed are more precise or not.

Definition at line 1080 of file liveness_analysis_engine.c.

{
  statement seq_stmt = (statement) gen_get_ancestor(statement_domain, seq);
  list l_stmt = sequence_statements(seq);
 
  pips_debug(1, "begin\n");
 
  if (ENDP(l_stmt))
    {
      if (get_bool_property("WARN_ABOUT_EMPTY_SEQUENCES"))
        pips_user_warning("empty sequence\n");
      store_live_in_paths_list(seq_stmt, NIL);
    }
  else
    {
      list l_rev_stmt = NIL; /* reversed version of the sequence to avoid recursion*/
      FOREACH(STATEMENT, stmt, l_stmt)
        {
          l_rev_stmt = CONS(STATEMENT, stmt, l_rev_stmt);
        }
 
      list l_next_stmt_live_in = load_live_out_paths_list(seq_stmt);
      FOREACH(STATEMENT, stmt, l_rev_stmt)
        {
          /* the live out paths of the current statement are the live in paths
             of the next statement (or the live out of the while block
             if last statement)
          */
          pips_debug(1,"dealing with statement with ordering: %03zd and number: %03zd\n",
                     statement_ordering(stmt), statement_number(stmt));
 
          list l_live_out = l_next_stmt_live_in;
          pips_debug_effects(2, "storing effects:\n", l_live_out);
          store_live_out_paths_list(stmt, effects_dup(l_live_out));
 
          /* Now let us compute the live in paths */
          live_in_paths_of_statement(stmt, ctxt);
          l_next_stmt_live_in = load_live_in_paths_list(stmt);
        }
 
      /* The block live in paths are the live in paths of the first statement
         which is the last visited statement.
         However, in case of nested sequences, which may be the case when there are
         macros for instance, the live_in paths may have already been computed.
         It's not yet clear if the effects we have just computed are more precise
         or not.
      */
      if ( !bound_live_in_paths_p(seq_stmt) )
        {
          pips_debug_effects(2, "storing live_in paths of sequence statement:\n", l_next_stmt_live_in);
          store_live_in_paths_list(seq_stmt, effects_dup(l_next_stmt_live_in));
        }
 
      gen_free_list(l_rev_stmt);
    }
  pips_debug(1, "end\n");
 
 return true;
}

References bound_live_in_paths_p(), CONS, effects_dup(), ENDP, FOREACH, gen_free_list(), gen_get_ancestor(), get_bool_property(), live_in_paths_of_statement(), load_live_in_paths_list(), load_live_out_paths_list(), NIL, pips_debug, pips_debug_effects, pips_user_warning, sequence_statements, STATEMENT, statement_domain, statement_number, statement_ordering, store_live_in_paths_list(), and store_live_out_paths_list().

Referenced by live_paths_of_module_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

live_paths_of_module_statement()

static void live_paths_of_module_statement ( statement  stmt, live_paths_analysis_context *  ctxt  )

static

for expression instructions solely, equivalent to gen_true otherwise

Stop on these nodes:

calls are treated in another phase

Definition at line 1155 of file liveness_analysis_engine.c.

{
 
  gen_context_multi_recurse
    (stmt, ctxt,
     statement_domain, gen_true, live_in_paths_of_statement,
     //instruction_domain, live_paths_from_instruction_to_expression, gen_null,
     /* for expression instructions solely, equivalent to gen_true otherwise */
     sequence_domain, live_paths_from_block_to_statements, gen_null,
     test_domain, live_out_paths_from_test_to_branches, gen_null,
     loop_domain, live_out_paths_from_loop_to_body, live_in_paths_of_loop,
     whileloop_domain, live_out_paths_from_whileloop_to_body, live_in_paths_of_whileloop,
     forloop_domain, live_out_paths_from_forloop_to_body, gen_null,
     unstructured_domain, live_out_paths_from_unstructured_to_nodes, gen_null,
 
     /* Stop on these nodes: */
     call_domain, gen_false, gen_null, /* calls are treated in another phase*/
     expression_domain, gen_false, gen_null,
     NULL);
 
  return;
}

References call_domain, expression_domain, forloop_domain, gen_context_multi_recurse(), gen_false(), gen_null(), gen_true(), live_in_paths_of_loop(), live_in_paths_of_statement(), live_in_paths_of_whileloop(), live_out_paths_from_forloop_to_body(), live_out_paths_from_loop_to_body(), live_out_paths_from_test_to_branches(), live_out_paths_from_unstructured_to_nodes(), live_out_paths_from_whileloop_to_body(), live_paths_from_block_to_statements(), loop_domain, sequence_domain, statement_domain, test_domain, unstructured_domain, and whileloop_domain.

Referenced by live_paths_engine().

Here is the call graph for this function:

Here is the caller graph for this function:

new_system_with_only_live_variable()

static Psysteme new_system_with_only_live_variable ( Psysteme  sc, reference  ref, list  llivein, list  lliveout  )

static

Create a new nsc system from the sc system of a region.

On this new nsc system only keep live variable. /param sc constraint system of the region /param ref reference variable that the region carry, have to keep on the new system of constraints /param llivein list of live in effect, variables to keep /param lliveout list of live out effect, variables to keep /return a new system of constraint for the region that only keep live variable

Definition at line 1264 of file liveness_analysis_engine.c.

                                                                                                            {
  Pbase base_keep = NULL;
  Pbase base_pj = base_copy(sc_base(sc));
  Psysteme nsc = sc_dup(sc);
 
  // Compute list of variable to keep
  entity ent = reference_variable(ref);
  if (base_contains_variable_p(base_pj, (Variable) ent))
    base_keep = base_add_variable(base_keep, (Variable) ent);
  list lind = reference_indices(ref);
  FOREACH(EXPRESSION, expind, lind) {
    entity entind = expression_to_entity(expind);
    if (base_contains_variable_p(base_pj, (Variable) entind))
      base_keep = base_add_variable(base_keep, (Variable) entind);
  }
 
  FOREACH(EFFECT, live, llivein) {
    reference liveref = effect_any_reference(live);
    entity liveent = reference_variable(liveref);
    if (base_contains_variable_p(base_pj, (Variable) liveent))
      base_keep = base_add_variable(base_keep, (Variable) liveent);
  }
 
  FOREACH(EFFECT, live, lliveout) {
    reference liveref = effect_any_reference(live);
    entity liveent = reference_variable(liveref);
    if (base_contains_variable_p(base_pj, (Variable) liveent))
      if (!base_contains_variable_p(base_keep, (Variable) liveent))
        base_keep = base_add_variable(base_keep, (Variable) liveent);
  }
 
  // Compute list of variable to project
  BASE_FOREACH(keep, base_keep) {
    vect_erase_var(&base_pj, keep);
  }
 
  ifdebug (4) {
    pips_debug(4, "Input system:\n");
    sc_print(sc, (get_variable_name_t) default_variable_to_string);
    pips_debug(4, "Variables to project:\n");
    vect_fprint(stderr, base_pj, (get_variable_name_t) default_variable_to_string);
  }
 
  // Project variable if possible
  // if not (overflow), keep the variable and generate a warning
  // if we use sc_projection_ofl_along_variables what we keep in case of overflow?
  //sc_projection_ofl_along_variables(nsc, elim); //add CATCH/TRY
  Psysteme scbackup = NULL;
  BASE_FOREACH(elim, base_pj) {
    scbackup = sc_dup(nsc);
    CATCH(overflow_error) {
      pips_user_warning("An overflow appear for the projection of %s. So this variable wasn't remove from the constraints system.\n", entity_name((entity) elim));
      nsc = sc_free(nsc);
      nsc = sc_dup(scbackup);
    }
    TRY {
      sc_projection_along_variable_ofl_ctrl(&nsc, elim, FWD_OFL_CTRL);
      sc_base_remove_variable(nsc, elim);
      nsc = sc_normalize(nsc);
      UNCATCH(overflow_error);
    }
    scbackup = sc_free(scbackup);
  }
 
  ifdebug (4) {
    pips_debug(4, "New system:\n");
    sc_print(nsc, (get_variable_name_t) default_variable_to_string);
  }
 
  return nsc;
}

References base_add_variable(), base_contains_variable_p(), base_copy(), BASE_FOREACH, CATCH, default_variable_to_string(), EFFECT, effect_any_reference, entity_name, EXPRESSION, expression_to_entity(), FOREACH, FWD_OFL_CTRL, ifdebug, keep, overflow_error, pips_debug, pips_user_warning, ref, reference_indices, reference_variable, sc_base_remove_variable(), sc_dup(), sc_free(), sc_normalize(), sc_print(), TRY, UNCATCH, vect_erase_var(), and vect_fprint().

Referenced by filter_live_out_regions_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

reset_converted_in_effects()

static void reset_converted_in_effects ( list *  lin, live_paths_analysis_context *  ctxt  )

static

Definition at line 118 of file liveness_analysis_engine.c.

{
  if (!ctxt->memory_effects_only
      && !ctxt->memory_in_out_effects_only)
    gen_free_list(*lin);
  *lin = NIL;
}

References gen_free_list(), live_paths_analysis_context::memory_effects_only, live_paths_analysis_context::memory_in_out_effects_only, and NIL.

Referenced by live_in_paths_of_statement(), live_out_paths_from_forloop_to_body(), live_out_paths_from_loop_to_body(), live_out_paths_from_unstructured_to_nodes(), and live_out_paths_from_whileloop_to_body().

Here is the call graph for this function:

Here is the caller graph for this function:

reset_converted_rw_effects()

static void reset_converted_rw_effects ( list *  lrw, live_paths_analysis_context *  ctxt  )

static

Definition at line 101 of file liveness_analysis_engine.c.

{
  if (!ctxt->memory_effects_only)
    gen_free_list(*lrw);
  *lrw = NIL;
}

References gen_free_list(), live_paths_analysis_context::memory_effects_only, and NIL.

Referenced by live_in_paths_of_loop(), live_in_paths_of_statement(), live_in_paths_of_whileloop(), live_out_paths_from_forloop_to_body(), live_out_paths_from_loop_to_body(), and live_out_paths_from_whileloop_to_body().

Here is the call graph for this function:

Here is the caller graph for this function:

reset_live_out_summary_engine_context()

static void reset_live_out_summary_engine_context ( live_out_summary_engine_context *  ctxt )

static

Definition at line 185 of file liveness_analysis_engine.c.

{
  ctxt->current_callee = entity_undefined;
  ctxt->l_current_paths = list_undefined;
}

References live_out_summary_engine_context::current_callee, entity_undefined, live_out_summary_engine_context::l_current_paths, and list_undefined.

Referenced by live_out_summary_paths_engine().

Here is the caller graph for this function:

reset_live_paths_context()

static void reset_live_paths_context ( live_paths_analysis_context *  ctxt )

static

Definition at line 81 of file liveness_analysis_engine.c.

{
  if (!  ctxt->memory_effects_only
      && ctxt->memory_in_out_effects_only)
    // if the MEMORY_EFFECTS_ONLY is FALSE on input, and
    // we did not want to compute IN non-memory effects,
    // we have to reset MEMORY_EFFECTS_ONLY to FALSE.
    set_bool_property("MEMORY_EFFECTS_ONLY", false);
}

References live_paths_analysis_context::memory_effects_only, live_paths_analysis_context::memory_in_out_effects_only, and set_bool_property().

Referenced by live_paths_engine().

Here is the call graph for this function:

Here is the caller graph for this function:

set_live_out_summary_engine_context()

static void set_live_out_summary_engine_context ( live_out_summary_engine_context *  ctxt, entity  callee  )

static

Definition at line 178 of file liveness_analysis_engine.c.

{
  ctxt->current_callee = callee;
  ctxt->l_current_paths = list_undefined;
}

References callee, live_out_summary_engine_context::current_callee, live_out_summary_engine_context::l_current_paths, and list_undefined.

Referenced by live_out_summary_paths_engine().

Here is the caller graph for this function:

update_live_out_summary_engine_context_paths()

static void update_live_out_summary_engine_context_paths ( live_out_summary_engine_context *  ctxt, list  l_paths  )

static

Definition at line 192 of file liveness_analysis_engine.c.

{
  pips_debug_effects(3, "adding paths\n", l_paths);
  if (list_undefined_p(ctxt->l_current_paths))
    ctxt->l_current_paths = l_paths;
  else
    // functions that can be pointed by effects_test_union_op:
    // EffectsMayUnion
    // RegionsMayUnion
    // ReferenceTestUnion
    ctxt->l_current_paths = (*effects_test_union_op)(ctxt->l_current_paths , l_paths,
        effects_same_action_p);
 
  pips_debug_effects(3, "current paths\n", ctxt->l_current_paths);
}

References effects_same_action_p(), live_out_summary_engine_context::l_current_paths, list_undefined_p, and pips_debug_effects.

Referenced by live_out_paths_from_call_site_to_callee().

Here is the call graph for this function:

Here is the caller graph for this function: