array_bound_check_top_down.c File Reference

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "genC.h"
#include "linear.h"
#include "ri.h"
#include "effects.h"
#include "alias_private.h"
#include "ri-util.h"
#include "prettyprint.h"
#include "effects-util.h"
#include "database.h"
#include "pipsdbm.h"
#include "resources.h"
#include "misc.h"
#include "control.h"
#include "transformer.h"
#include "properties.h"
#include "pipsmake.h"
#include "instrumentation.h"
#include "abc_private.h"
#include "effects-generic.h"
#include "effects-convex.h"
#include "effects-simple.h"
#include "conversion.h"

Include dependency graph for array_bound_check_top_down.c:

Go to the source code of this file.

Data Structures
struct	top_down_abc_context_t
	The following data structure is the context of top_down_abc: The read_marked_list marks if one bound of one array's dimension is tested or not, for the READ regions. More...
struct	Bound_test

Typedefs
typedef struct top_down_abc_context_t *	top_down_abc_context_p
typedef struct Bound_test	Bound_test

Functions
static string	read_or_write (bool a)
string	bool_to_bound (bool b)
	array_bound_check_top_down.c More...
static void	initialize_top_down_abc_statistics ()
static void	display_top_down_abc_statistics ()
static abc_checked	initiliaze_marked_list ()
static void	set_array_dimension_checked (top_down_abc_context_p context, bool action, entity array, int dim, bool bound)
static Psysteme	my_system_remove_variables (Psysteme ps)
static void	top_down_abc_insert_before_statement (statement s, statement s1, top_down_abc_context_p context)
static list	top_down_abc_call (call c, entity array, dimension dim_i, int i, bool bound)
static Bound_test	top_down_abc_not_exact_case (statement s, top_down_abc_context_p context, bool action, entity array, dimension dim_i, int i, bool bound)
static Bound_test	top_down_abc_dimension (statement s, top_down_abc_context_p context, region re, bool action, entity array, int i, bool bound)
static bool	max_statement_write_flt (statement s)
static int	maximum_ordering (entity a, statement s)
	search for the maximum ordering of statement (after s) that writes on a More...
static bool	min_statement_write_flt (statement s)
static int	minimum_ordering (entity a, statement s)
	search for the minimum ordering of statement (after s) that writes on a More...
static bool	is_first_written_array_p (entity a, list l, statement s)
static entity	find_first_written_array (list l, statement s)
static void	top_down_abc_array (entity array, region re, statement s, top_down_abc_context_p context)
static bool	top_down_abc_flt (statement s, top_down_abc_context_p context)
	The old algorithm is false in the case of incorrect code, because regions are computed with the assumption that the code is correct. More...
static void	top_down_abc_rwt (statement s, top_down_abc_context_p context)
static bool	store_mapping (control c, top_down_abc_context_p context)
static bool	push_uns (unstructured u, top_down_abc_context_p context)
static void	pop_uns (unstructured __attribute__((unused)) u, top_down_abc_context_p context)
static void	top_down_abc_statement (statement module_statement)
bool	array_bound_check_top_down (const char *module_name)

Variables
static int	number_of_added_tests
	Statistic variables: More...
static int	number_of_bound_violations
static entity	current_entity = entity_undefined
static int	current_max
static int	current_min = 0
static statement	test_sequence = statement_undefined
static bool	godown = false
static list	lexp = NIL

Typedef Documentation

Bound_test

typedef struct Bound_test Bound_test

top_down_abc_context_p

typedef struct top_down_abc_context_t * top_down_abc_context_p

Function Documentation

array_bound_check_top_down()

bool array_bound_check_top_down

(

const char *

module_name

)

set and get the current properties concerning regions

Get the code of the module.

Get the READ and WRITE regions of the module

Reorder the module, because the bound checks have been added

Parameters

module_name

odule_name

Definition at line 1129 of file array_bound_check_top_down.c.

{
  statement module_statement;
  set_current_module_entity(local_name_to_top_level_entity(module_name));
  if (!same_string_p(rule_phase(find_rule_by_resource("REGIONS")),
                     "MUST_REGIONS"))
    pips_user_warning("\n MUST REGIONS not selected - "
                      "\n Do not expect wonderful results\n");
  /* set and get the current properties concerning regions */
  set_bool_property("MUST_REGIONS", true);
  set_bool_property("EXACT_REGIONS", true);
  get_regions_properties();
  /* Get the code of the module. */
  module_statement= (statement) db_get_memory_resource(DBR_CODE,
                                                       module_name,
                                                       true);
  set_current_module_statement(module_statement);
  set_ordering_to_statement(module_statement);
  /* Get the READ and WRITE regions of the module */
  set_rw_effects((statement_effects)
                 db_get_memory_resource(DBR_REGIONS, module_name, true));
  set_proper_rw_effects((statement_effects)
                        db_get_memory_resource(DBR_PROPER_EFFECTS,
                                               module_name,true));
  debug_on("ARRAY_BOUND_CHECK_TOP_DOWN_DEBUG_LEVEL");
  pips_debug(1, " Region based ABC, Begin for %s\n", module_name);
  pips_assert("Statement is consistent ...",
              statement_consistent_p(module_statement));
  initialize_top_down_abc_statistics();
  top_down_abc_statement(module_statement);
  display_top_down_abc_statistics();
  /* Reorder the module, because the bound checks have been added */
  module_reorder(module_statement);
  pips_debug(1, "end\n");
  debug_off();
  DB_PUT_MEMORY_RESOURCE(DBR_CODE,module_name, module_statement);
  reset_ordering_to_statement();
  reset_current_module_entity();
  reset_current_module_statement();
  reset_proper_rw_effects();
  reset_rw_effects();
  return true;
}

References db_get_memory_resource(), DB_PUT_MEMORY_RESOURCE, debug_off, debug_on, display_top_down_abc_statistics(), find_rule_by_resource(), get_regions_properties(), initialize_top_down_abc_statistics(), local_name_to_top_level_entity(), module_name(), module_reorder(), module_statement, pips_assert, pips_debug, pips_user_warning, reset_current_module_entity(), reset_current_module_statement(), reset_ordering_to_statement(), reset_proper_rw_effects(), reset_rw_effects(), rule_phase, same_string_p, set_bool_property(), set_current_module_entity(), set_current_module_statement(), set_ordering_to_statement(), set_proper_rw_effects(), set_rw_effects(), statement_consistent_p(), and top_down_abc_statement().

Here is the call graph for this function:

bool_to_bound()

string bool_to_bound

(

bool

b

)

array_bound_check_top_down.c

Definition at line 115 of file array_bound_check_top_down.c.

{
  if (b)
    return ", lower bound, ";
  return ", upper bound, ";
}

Referenced by make_bottom_up_abc_tests(), and top_down_abc_array().

Here is the caller graph for this function:

display_top_down_abc_statistics()

static void display_top_down_abc_statistics ( )

static

Definition at line 133 of file array_bound_check_top_down.c.

{
  if (number_of_added_tests > 0)
    user_log("* There %s %d array bound check%s added *\n",
             number_of_added_tests > 1 ? "are" : "is",
             number_of_added_tests,
             number_of_added_tests > 1 ? "s" : "");
 
  if (number_of_bound_violations > 0)
    user_log("* There %s %d bound violation%s *\n",
             number_of_bound_violations > 1 ? "are" : "is",
             number_of_bound_violations,
             number_of_bound_violations > 1 ? "s" : "");
}

References number_of_added_tests, number_of_bound_violations, and user_log().

Referenced by array_bound_check_top_down().

Here is the call graph for this function:

Here is the caller graph for this function:

find_first_written_array()

static entity find_first_written_array ( list  l, statement  s  )

static

Definition at line 716 of file array_bound_check_top_down.c.

{
  list l_tmp = gen_full_copy_list(l);
  MAP(ENTITY,a,
  {
    if (is_first_written_array_p(a,l,s))
      return a;
  },l_tmp);
  return entity_undefined;
}

References ENTITY, entity_undefined, gen_full_copy_list(), is_first_written_array_p(), and MAP.

Referenced by top_down_abc_flt().

Here is the call graph for this function:

Here is the caller graph for this function:

initialize_top_down_abc_statistics()

static void initialize_top_down_abc_statistics ( )

static

Definition at line 127 of file array_bound_check_top_down.c.

{
    number_of_added_tests = 0;
    number_of_bound_violations = 0;
}

References number_of_added_tests, and number_of_bound_violations.

Referenced by array_bound_check_top_down().

Here is the caller graph for this function:

initiliaze_marked_list()

static abc_checked initiliaze_marked_list ( )

static

Definition at line 148 of file array_bound_check_top_down.c.

{
  list retour = NIL;
  // get list of entities in the declaration part
  list ld =
    code_declarations(value_code(entity_initial(get_current_module_entity())));
  MAP(ENTITY,e,
  {
    type t = entity_type(e);
    if (type_variable_p(t))
      {
        list ldim = variable_dimensions(type_variable(t));
        int length = gen_length(ldim);
        if (length > 0)
          {
            dimension_checked dc = dimension_checked_undefined ;
            list dc_list = NIL;
            int i;
            array_dimension_checked adc;
            for(i=1; i <= length; i++ )
              {
                dc = make_dimension_checked(i,false,false);
                dc_list = gen_nconc(dc_list,
                                    CONS(DIMENSION_CHECKED,dc,NIL));
              }
            adc = make_array_dimension_checked(e, dc_list);
            retour = gen_nconc(retour,CONS(ARRAY_DIMENSION_CHECKED,adc,NIL));
          }
      }
  },
      ld);
  return make_abc_checked(retour);
}

References ARRAY_DIMENSION_CHECKED, code_declarations, CONS, DIMENSION_CHECKED, dimension_checked_undefined, ENTITY, entity_initial, entity_type, gen_length(), gen_nconc(), get_current_module_entity(), make_abc_checked(), make_array_dimension_checked(), make_dimension_checked(), MAP, NIL, type_variable, type_variable_p, value_code, and variable_dimensions.

Referenced by top_down_abc_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

is_first_written_array_p()

static bool is_first_written_array_p ( entity  a, list  l, statement  s  )

static

Definition at line 690 of file array_bound_check_top_down.c.

{
  int max = maximum_ordering(a,s);
  ifdebug(4)
    fprintf(stderr, " max of %s = %d ", entity_name(a), max);
  MAP(ENTITY,other,
  {
    if (strcmp(entity_name(a),entity_name(other))!=0)
      {
        int min = minimum_ordering(other,s);
        ifdebug(4)
          fprintf(stderr, " min of other %s  = %d ", entity_name(other), min);
        if (max >= min) return false;
      }
  },l);
  return true;
}

References ENTITY, entity_name, fprintf(), ifdebug, MAP, max, maximum_ordering(), min, and minimum_ordering().

Referenced by find_first_written_array().

Here is the call graph for this function:

Here is the caller graph for this function:

max_statement_write_flt()

static bool max_statement_write_flt ( statement  s )

static

Definition at line 599 of file array_bound_check_top_down.c.

{
  list effects_list = load_proper_rw_effects_list(s);
  MAP(EFFECT, eff,
  {
    action a = effect_action(eff);
    if (action_write_p(a))
      {
        reference r = effect_any_reference(eff);
        entity e = reference_variable(r);
        ifdebug(4)
          {
            fprintf(stderr,"\n MAX Write on entity %s :\n",entity_name(e));
            fprintf(stderr,"\n MAX Current entity %s :\n",entity_name(current_entity));
          }
        if (strcmp(entity_name(e),entity_name(current_entity))==0)
          {
            int n = statement_ordering(s);
            ifdebug(4)
              {
                fprintf(stderr,"a variable = current entity !!");
                fprintf(stderr,"This statement writes on %s with max ordering %d",
                        entity_name(current_entity),n);
              }
            if (n>current_max) current_max = n;
            break;
          }
      }
  },
      effects_list);
  return true;
}

References action_write_p, current_entity, current_max, EFFECT, effect_action, effect_any_reference, entity_name, fprintf(), ifdebug, load_proper_rw_effects_list(), MAP, reference_variable, and statement_ordering.

Referenced by maximum_ordering().

Here is the call graph for this function:

Here is the caller graph for this function:

maximum_ordering()

static int maximum_ordering ( entity  a, statement  s  )

static

search for the maximum ordering of statement (after s) that writes on a

Definition at line 633 of file array_bound_check_top_down.c.

{
  current_entity = a;
  current_max = 0;
  gen_recurse(s, statement_domain, max_statement_write_flt, gen_null);
  ifdebug(4)
    fprintf(stderr, " return current_max = %d of current entity %s ",
            current_max, entity_name(current_entity));
  current_entity = entity_undefined;
  return current_max;
}

References current_entity, current_max, entity_name, entity_undefined, fprintf(), gen_null(), gen_recurse, ifdebug, max_statement_write_flt(), and statement_domain.

Referenced by is_first_written_array_p().

Here is the call graph for this function:

Here is the caller graph for this function:

min_statement_write_flt()

static bool min_statement_write_flt ( statement  s )

static

Definition at line 645 of file array_bound_check_top_down.c.

{
  list effects_list = load_proper_rw_effects_list(s);
  MAP(EFFECT, eff,
  {
    action a = effect_action(eff);
    if (action_write_p(a))
      {
        reference r = effect_any_reference(eff);
        entity e = reference_variable(r);
        ifdebug(4)
          {
            fprintf(stderr,"\n MIN Write on entity %s :\n",entity_name(e));
            fprintf(stderr,"\n MIN Current entity %s :\n",entity_name(current_entity));
          }
        if (strcmp(entity_name(e),entity_name(current_entity))==0)
          {
            current_min = statement_ordering(s);
            ifdebug(4)
              {
                fprintf(stderr,"a variable = current entity !!");
                fprintf(stderr, " This statement writes on %s with min ordering %d",
                        entity_name(current_entity),current_min);
              }
            return false;
          }
      }
  },
      effects_list);
  return true;
}

References action_write_p, current_entity, current_min, EFFECT, effect_action, effect_any_reference, entity_name, fprintf(), ifdebug, load_proper_rw_effects_list(), MAP, reference_variable, and statement_ordering.

Referenced by minimum_ordering().

Here is the call graph for this function:

Here is the caller graph for this function:

minimum_ordering()

static int minimum_ordering ( entity  a, statement  s  )

static

search for the minimum ordering of statement (after s) that writes on a

Definition at line 678 of file array_bound_check_top_down.c.

{
  current_entity = a;
  current_min = 0;
  gen_recurse(s, statement_domain, min_statement_write_flt, gen_null);
  ifdebug(4)
    fprintf(stderr, " return current_min = %d of current entity %s",
            current_min, entity_name(current_entity));
  current_entity = entity_undefined;
  return current_min;
}

References current_entity, current_min, entity_name, entity_undefined, fprintf(), gen_null(), gen_recurse, ifdebug, min_statement_write_flt(), and statement_domain.

Referenced by is_first_written_array_p().

Here is the call graph for this function:

Here is the caller graph for this function:

my_system_remove_variables()

static Psysteme my_system_remove_variables ( Psysteme  ps )

static

Project all PHI and init variables, ....in the system ps, there are 2 cases :

1. The result is not sure , there are over flow Return the SC_UNDEFINED
2. The result is sure, three small cases: 2.1 The system is always false sc_empty => no bounds violation 2.2 The system is always true sc_rn => bounds violation 2.3 The system is parametric => test to put

converts the phi list into a Pvecteur

Definition at line 224 of file array_bound_check_top_down.c.

{
  /* Project all PHI and #init variables, ....in the system ps,
     there are 2 cases :
     1. The result is not sure , there are over flow
        Return the SC_UNDEFINED
     2. The result is sure, three small cases:
        2.1 The system is always false sc_empty => no bounds violation
        2.2 The system is always true sc_rn => bounds violation
        2.3 The system is parametric => test to put*/
 
  if (!sc_empty_p(ps)&& !sc_rn_p(ps))
  {
    list l_phi = phi_entities_list(1,7);
    list l_var = l_phi;
    Pvecteur pv_var = NULL;
    Pbase b = ps->base;
    /* converts the phi list into a Pvecteur */
    MAP(ENTITY, e,
        {
          if (base_contains_variable_p(ps->base, (Variable) e) )
            vect_add_elem(&pv_var, (Variable) e, VALUE_ONE);
        },l_var);
 
    for(; !VECTEUR_NUL_P(b);b = b->succ)
    {
      entity e = (entity) vecteur_var(b);
      if (old_value_entity_p(e))
        vect_add_elem(&pv_var, (Variable) e, VALUE_ONE);
    }
    ps = sc_system_projection_along_variables(ps, pv_var);
    vect_rm(pv_var);
    gen_free_list(l_phi);
  }
  return ps;
}

References Ssysteme::base, base_contains_variable_p(), ENTITY, gen_free_list(), MAP, old_value_entity_p(), phi_entities_list(), sc_empty_p(), sc_rn_p(), Svecteur::succ, VALUE_ONE, vect_add_elem(), vect_rm(), VECTEUR_NUL_P, and vecteur_var.

Referenced by top_down_abc_dimension().

Here is the call graph for this function:

Here is the caller graph for this function:

pop_uns()

static void pop_uns ( unstructured __attribute__((unused))  u, top_down_abc_context_p  context  )

static

Definition at line 1095 of file array_bound_check_top_down.c.

{
  stack_pop(context->uns);
}

References stack_pop().

Referenced by top_down_abc_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

push_uns()

static bool push_uns ( unstructured  u, top_down_abc_context_p  context  )

static

Definition at line 1089 of file array_bound_check_top_down.c.

{
  stack_push((char *) u, context->uns);
  return true;
}

References stack_push().

Referenced by top_down_abc_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

read_or_write()

static string read_or_write ( bool  a )

static

Definition at line 108 of file array_bound_check_top_down.c.

{
  if (a)
    return ", READING, ";
  return ", WRITING, ";
}

Referenced by concrete_effects_may_read_or_write_scalar_entity_p(), effect_may_read_or_write_memory_paths_from_entity_p(), effects_may_read_or_write_memory_paths_from_entity_p(), effects_may_read_or_write_scalar_entity_p(), effects_must_read_or_write_scalar_entity_p(), generic_effects_maymust_read_or_write_scalar_entity_p(), and top_down_abc_array().

Here is the caller graph for this function:

set_array_dimension_checked()

static void set_array_dimension_checked ( top_down_abc_context_p  context, bool  action, entity  array, int  dim, bool  bound  )

static

Definition at line 182 of file array_bound_check_top_down.c.

{
  if (action)
    {
      // read region
      MAP(ARRAY_DIMENSION_CHECKED, adc,
      {
        if (same_entity_p(array,array_dimension_checked_array(adc)))
          MAP(DIMENSION_CHECKED, dc,
          {
            if (dimension_checked_dim(dc) == dim)
              {
                if (bound)
                  dimension_checked_lower(dc) = true;
                else
                  dimension_checked_upper(dc) = true;
              }
          },array_dimension_checked_dims(adc));
      }, abc_checked_list(context->read_marked_list));
    }
  else
    {
      // write region
      MAP(ARRAY_DIMENSION_CHECKED, adc,
      {
        if (same_entity_p(array,array_dimension_checked_array(adc)))
          MAP(DIMENSION_CHECKED, dc,
          {
            if (dimension_checked_dim(dc) == dim)
              {
                if (bound)
                  dimension_checked_lower(dc) = true;
                else
                  dimension_checked_upper(dc) = true;
              }
          },array_dimension_checked_dims(adc));
      }, abc_checked_list(context->write_marked_list));
    }
}

References abc_checked_list, array, ARRAY_DIMENSION_CHECKED, array_dimension_checked_array, array_dimension_checked_dims, DIMENSION_CHECKED, dimension_checked_dim, dimension_checked_lower, dimension_checked_upper, MAP, and same_entity_p().

Referenced by top_down_abc_dimension(), and top_down_abc_not_exact_case().

Here is the call graph for this function:

Here is the caller graph for this function:

store_mapping()

static bool store_mapping ( control  c, top_down_abc_context_p  context  )

static

Definition at line 1082 of file array_bound_check_top_down.c.

{
  extend_persistant_statement_to_control(context->map,
                                         control_statement(c), c);
  return true;
}

References control_statement, and extend_persistant_statement_to_control().

Referenced by top_down_abc_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

top_down_abc_array()

static void top_down_abc_array ( entity  array, region  re, statement  s, top_down_abc_context_p  context  )

static

if we have a region like: <A(PHI)-EXACT-{}> it means that all declared elements are touched, although this is implicit. this occurs with io effects of "PRINT *, A". in such a case, the declaration constraints MUST be appended before the translation, otherwise the result might be false.

potential bug : if the declaration system cannot be generated, the region should be turned to MAY for the translation?

The upper bound of the dimension i is not marked TRUE

There is bounds violation ! Insert a STOP before s (bug in Examples/perma.f if replace s by STOP

The lower bound of the dimension i is not marked TRUE

There is bounds violation ! Insert a STOP before s (bug in Examples/perma.f if replace s by STOP

insert the test after the generated tests, the order of tests is important

If one bound of the dimension is marked false, we have to go down

Definition at line 731 of file array_bound_check_top_down.c.

{
  list marked_list = NIL;
  list dc_list = NIL;
  bool action = region_read_p(re);
  if (action)
    marked_list = abc_checked_list(context->read_marked_list);
  else
    marked_list = abc_checked_list(context->write_marked_list);
  MAP(ARRAY_DIMENSION_CHECKED,adc,
  {
    if (same_entity_p(array_dimension_checked_array(adc),array))
      {
        dc_list = array_dimension_checked_dims(adc);
        break;
      }
  },
      marked_list);
  // traverse each dimension
  while (!ENDP(dc_list))  {
    dimension_checked dc = DIMENSION_CHECKED(CAR(dc_list));
    int i = dimension_checked_dim(dc);
    Bound_test lower, upper;
    lower.test = expression_undefined;
    upper.test = expression_undefined;
    lower.bound = true;
    upper.bound = true;
 
    /* if we have a region like: <A(PHI)-EXACT-{}>
     * it means that all *declared* elements are touched, although
     * this is implicit. this occurs with io effects of "PRINT *, A".
     * in such a case, the declaration constraints MUST be appended
     * before the translation, otherwise the result might be false.
     *
     * potential bug : if the declaration system cannot be generated,
     *   the region should be turned to MAY for the translation? */
    append_declaration_sc_if_exact_without_constraints(re);
    if (!dimension_checked_upper(dc))
      {
        /* The upper bound of the dimension i is not marked TRUE*/
        upper = top_down_abc_dimension(s,context,re,action,array,i,false);
        if (!expression_undefined_p(upper.test))
          {
            statement sta;
            test t;
            string message =
              strdup(concatenate("\'Bound violation:",
                                 read_or_write(action), " array ",
                                 entity_name(array),
                                 bool_to_bound(false),
                                 int_to_dimension(i),"\'",NULL));
 
            if (true_expression_p(upper.test))
              {
                /* There is bounds violation !
                   Insert a STOP before s (bug in Examples/perma.f if replace s by STOP*/
                number_of_bound_violations ++;
                user_log("\n Bound violation !!! \n");
                if (get_bool_property("PROGRAM_VERIFICATION_WITH_PRINT_MESSAGE"))
                  sta  = make_print_statement(message);
                else
                  sta  = make_stop_statement(message);
                // top_down_abc_insert_before_statement(s,sta,context);
                if (statement_undefined_p(test_sequence))
                  test_sequence = copy_statement(sta);
                else
                  insert_statement(test_sequence,copy_statement(sta),false);
                //return false;  // follow the first strategy
              }
            // test if expression upper.test exists already in test_sequence
            else
              if (!same_expression_in_list_p(upper.test,lexp))
                {
                  ifdebug(2)
                    {
                      fprintf(stderr, "\n The upper test");
                      print_expression(upper.test);
                    }
                  number_of_added_tests++;
                  lexp = gen_nconc(lexp,CONS(EXPRESSION,upper.test,NIL));
                  if (get_bool_property("PROGRAM_VERIFICATION_WITH_PRINT_MESSAGE"))
                    t = make_test(upper.test,
                                  make_print_statement(message),
                                  make_block_statement(NIL));
                  else
                    t = make_test(upper.test,
                                  make_stop_statement(message),
                                  make_block_statement(NIL));
                  sta  = test_to_statement(t);
                  if (statement_undefined_p(test_sequence))
                    test_sequence = copy_statement(sta);
                  else
                    insert_statement(test_sequence,copy_statement(sta),false);
                }
          }
      }
    if (!dimension_checked_lower(dc))
      {
        /* The lower bound of the dimension i is not marked TRUE*/
        lower = top_down_abc_dimension(s,context,re,action,array,i,true);
        if (!expression_undefined_p(lower.test))
          {
            statement sta;
            test t;
            string message =
              strdup(concatenate("\'Bound violation:",
                                 read_or_write(action)," array ",
                                 entity_name(array),
                                 bool_to_bound(true),
                                 int_to_dimension(i),"\'",NULL));
 
            if (true_expression_p(lower.test))
              {
                /* There is bounds violation !
                   Insert a STOP before s (bug in Examples/perma.f if replace s by STOP*/
                number_of_bound_violations ++;
                user_log("\n Bound violation !!! \n");
                if (get_bool_property("PROGRAM_VERIFICATION_WITH_PRINT_MESSAGE"))
                  sta =  make_print_statement(message);
                else
                  sta = make_stop_statement(message);
                // top_down_abc_insert_before_statement(s,sta,context);
                if (statement_undefined_p(test_sequence))
                  test_sequence = copy_statement(sta);
                else
                  /* insert the test after the generated tests, the order of tests
                     is important */
                  insert_statement(test_sequence,copy_statement(sta),false);
                // return false;  // follow the first strategy
              }
            else
              // test if expression lower.test exists already in test_sequence
              if (!same_expression_in_list_p(lower.test,lexp))
                {
                  ifdebug(2)
                    {
                      fprintf(stderr, "\n The lower test");
                      print_expression(lower.test);
                    }
                  number_of_added_tests ++;
                  lexp = gen_nconc(lexp,CONS(EXPRESSION,lower.test,NIL));
                  if (get_bool_property("PROGRAM_VERIFICATION_WITH_PRINT_MESSAGE"))
                    t = make_test(lower.test,
                                  make_print_statement(message),
                                  make_block_statement(NIL));
                  else
                    t = make_test(lower.test,
                                  make_stop_statement(message),
                                  make_block_statement(NIL));
                  sta  = test_to_statement(t);
                  if (statement_undefined_p(test_sequence))
                    test_sequence = copy_statement(sta);
                  else
                    insert_statement(test_sequence,copy_statement(sta),false);
                }
          }
      }
        /* If one bound of the dimension is marked false,
           we have to go down*/
    if ((!lower.bound) || (!upper.bound)) godown = true;
    dc_list = CDR(dc_list);
  }
}

References abc_checked_list, append_declaration_sc_if_exact_without_constraints(), array, ARRAY_DIMENSION_CHECKED, array_dimension_checked_array, array_dimension_checked_dims, bool_to_bound(), Bound_test::bound, CAR, CDR, concatenate(), CONS, copy_statement(), DIMENSION_CHECKED, dimension_checked_dim, dimension_checked_lower, dimension_checked_upper, ENDP, entity_name, EXPRESSION, expression_undefined, expression_undefined_p, fprintf(), gen_nconc(), get_bool_property(), godown, ifdebug, insert_statement(), int_to_dimension(), lexp, make_block_statement(), make_print_statement(), make_stop_statement(), make_test(), MAP, NIL, number_of_added_tests, number_of_bound_violations, print_expression(), read_or_write(), region_read_p, same_entity_p(), same_expression_in_list_p(), statement_undefined_p, strdup(), Bound_test::test, test_sequence, test_to_statement, top_down_abc_dimension(), true_expression_p(), and user_log().

Referenced by top_down_abc_flt().

Here is the call graph for this function:

Here is the caller graph for this function:

top_down_abc_call()

static list top_down_abc_call ( call  c, entity  array, dimension  dim_i, int  i, bool  bound  )

static

There is nothing to check here

Make expression : ith < lower_bound

Make expression : upper_bound < ith

Remark : Doesn't like the 1st version of abc, we don't have to put a test for ith in the indirect case. F.e : for A(B(i)) = 0.0, we have 2 regions : < B(PHI1)-R-EXACT-{PHI1==I} > < A(PHI1)-W-MAY-{} > when we check for the inexact case of A, we don't have to check for B.

In case if there is another access of array B in the same statement, the region of B may be MAY => we check it for the read region of B.

In case of A(A(i)) , we have the different regions for read and write effect ??????? => ????? ATT : example Indirection.f

Test if exp is trivial or not

• If exp is always TRUE: there is certainly bound violation, return make_true_expression
• If exp is always false, we don't have to add it to retour
• Otherwise, we add it to retour.

Definition at line 316 of file array_bound_check_top_down.c.

{
  list retour = NIL;
  list args = call_arguments(c);
  MAP(EXPRESSION,e,
  {
    syntax s = expression_syntax(e);
    tag t = syntax_tag(s);
    switch (t){
    case is_syntax_call:
      {
        list tmp = top_down_abc_call(syntax_call(s),array,dim_i,i,bound);
        if (tmp != NIL)
          // add tmp to retour
          MAP(EXPRESSION, exp,
          {
            if (!same_expression_in_list_p(exp,retour))
              retour = gen_nconc(retour,CONS(EXPRESSION,exp,NIL));
          },
              tmp);
        break;
      }
    case is_syntax_range:
      /* There is nothing to check here*/
      break;
    case is_syntax_reference:
      {
        reference ref = syntax_reference(s);
        entity arr = reference_variable(ref);
        if (same_entity_p(arr,array))
          {
            list arrayinds = reference_indices(ref);
            expression ith = find_ith_argument(arrayinds,i);
            expression exp = expression_undefined;
            if (!expression_undefined_p(ith))
              {
                ifdebug(2)
                  {
                    fprintf(stderr, "\n The ith expression");
                    print_expression(ith);
                    fprintf(stderr, " \n array: %s ",entity_name(array));
                  }
                if (bound)
                  {
                    /* Make expression : ith < lower_bound */
                    exp = lt_expression(copy_expression(ith),
                                        dimension_lower(copy_dimension(dim_i)));
                    ifdebug(2)
                      {
                        fprintf(stderr, "\n The lower bound test");
                        print_expression(exp);
                      }
                  }
                else
                  // test if the upper bound is unbounded or not
                  if (!unbounded_dimension_p(dim_i))
                    {
                      /* Make expression  : upper_bound < ith */
                      exp = lt_expression(dimension_upper(copy_dimension(dim_i)),
                                          copy_expression(ith));
                      ifdebug(2)
                        {
                          fprintf(stderr, "\n The upper bound test");
                          print_expression(exp);
                        }
                      }
              }
 
            /* Remark : Doesn't like the 1st version of abc,
               we don't have to put a test for ith in the indirect case.
               F.e : for A(B(i)) = 0.0, we have 2 regions :
               < B(PHI1)-R-EXACT-{PHI1==I} >
               < A(PHI1)-W-MAY-{} >
               when we check for the inexact case of A, we don't have
               to check for B.
 
               In case if there is another access of array B in the same
               statement, the region of B may be MAY => we check it for
               the read region of B.
 
               In case of A(A(i)) , we have the different regions for read
               and write effect ??????? => ?????
               ATT : example Indirection.f */
 
            /* Test if exp is trivial or not
               + If exp is always TRUE: there is certainly bound violation,
               return  make_true_expression
               + If exp is always false, we don't have to add it to retour
               + Otherwise, we add it to retour.*/
            if (!expression_undefined_p(exp))
              {
                int tr = trivial_expression_p(exp);
                switch(tr){
                case 1:
                  return CONS(EXPRESSION,make_true_expression(),NIL);
                case 0:
                  {
                    // test if exp is already in retour
                    if (!same_expression_in_list_p(exp,retour))
                      retour = gen_nconc(retour,CONS(EXPRESSION,exp,NIL));
                    break;
                  }
                case -1:
                  break;
                }
              }
          }
        break;
      }
    }
  },
      args);
  return retour;
}

References array, call_arguments, CONS, copy_dimension(), copy_expression(), dimension_lower, dimension_upper, entity_name, exp, EXPRESSION, expression_syntax, expression_undefined, expression_undefined_p, find_ith_argument(), fprintf(), gen_nconc(), ifdebug, is_syntax_call, is_syntax_range, is_syntax_reference, lt_expression, make_true_expression(), MAP, NIL, print_expression(), ref, reference_indices, reference_variable, same_entity_p(), same_expression_in_list_p(), syntax_call, syntax_reference, syntax_tag, trivial_expression_p(), and unbounded_dimension_p().

Referenced by top_down_abc_not_exact_case().

Here is the call graph for this function:

Here is the caller graph for this function:

top_down_abc_dimension()

static Bound_test top_down_abc_dimension ( statement  s, top_down_abc_context_p  context, region  re, bool  action, entity  array, int  i, bool  bound  )

static

unbounded dimension, we don't have to check for this bound

try fast check

ok, redundant => there is certainly bound violation

ok, not feasible => there is no bound violation

no result, try slow version

Add the equation PHIi <= lower-1 (upper+1 <= PHIi) to the predicate of region re

Every expression is linear. Test the feasibility of P by using this function: sc_rational_feasibility_ofl_ctrl(sc, ofl_ctrl, ofl_res) in which

ofl_ctrl = OFL_CTRL means that the overflows are treated in the called procedure (sc_rational_feasibility_ofl_ctrl())

ofl_res = true means that if the overflows occur, function sc_rational_feasibility_ofl_ctrl will return the value TRUE we don't know if the system is feasible or not

The function sc_rational_feasibility_ofl_ctrl() is less expensive than the function sc_integer_feasibility_ofl_ctrl()

The system is not feasible (certainly) => no violation

The system is feasible or we don't know it is feasible or not Test if the region re is EXACT or MAY

EXACT region Remove all PHI variables, useless variables such as PIPS generated variables V::init, common variable from another subroutine ......

SUBROUTINE X CALL Y(I) <P(I) {I == FOO:J} END

SUBROUTINE Y(K) COMMON J K=J END

MAY region

Definition at line 461 of file array_bound_check_top_down.c.

{
  Bound_test retour;
  variable var = type_variable(entity_type(array));
  dimension dim_i = find_ith_dimension(variable_dimensions(var),i);
  retour.bound = true;
  retour.test = expression_undefined;
  if (!bound && unbounded_dimension_p(dim_i))
    /* unbounded dimension, we don't have to check for this bound */
    set_array_dimension_checked(context,action,array,i,bound);
  else
    {
      Psysteme P = sc_dup(region_system(re));
      Pcontrainte con_exp = CONTRAINTE_UNDEFINED;
      normalized nexpr = normalized_undefined;
      expression exp = expression_undefined;
      expression exp_1 = int_to_expression(1);
      if (bound)
        exp = binary_intrinsic_expression(MINUS_OPERATOR_NAME,
                                          dimension_lower(copy_dimension(dim_i)),
                                          exp_1);
      else
        exp = binary_intrinsic_expression(PLUS_OPERATOR_NAME,
                                          dimension_upper(copy_dimension(dim_i)),
                                          exp_1);
      clean_all_normalized(exp);
      // fast check: PHIi<=lower-1 (or upper+1<=PHIi) is trivial redundant wrt P or not
      // transform exp to Pcontrainte con_exp
      nexpr = NORMALIZE_EXPRESSION(exp);
      if (normalized_linear_p(nexpr))
        {
          entity phi = make_phi_entity(i);
          Pvecteur v1 = vect_new((Variable) phi, VALUE_ONE);
          Pvecteur v2 = normalized_linear(nexpr);
          Pvecteur vect;
          if (bound)
            vect = vect_substract(v1, v2);
          else
            vect = vect_substract(v2, v1);
          vect_rm(v1);
          con_exp = contrainte_make(vect);
          switch (sc_check_inequality_redundancy(con_exp, P)) {/* try fast check */
          case 1: /* ok, redundant => there is certainly bound violation */
            {
              set_array_dimension_checked(context,action,array,i,bound);
              retour.test = make_true_expression();
              break;
            }
          case 2: /* ok, not feasible => there is no bound violation*/
            {
              set_array_dimension_checked(context,action,array,i,bound);
              break;
            }
          case 0: /* no result, try slow version */
            {
              /* Add the equation  PHIi <= lower-1 (upper+1 <= PHIi)
                 to the predicate of region re */
              if (sc_add_phi_equation(&P,exp,i,false,bound))
                {
                  /* Every expression is linear.
                   * Test the feasibility of P by using this function:
                   * sc_rational_feasibility_ofl_ctrl(sc, ofl_ctrl, ofl_res) in which
                   *
                   * ofl_ctrl = OFL_CTRL means that the overflows are treated in the
                   * called procedure (sc_rational_feasibility_ofl_ctrl())
                   *
                   * ofl_res = true means that if the overflows occur, function
                   * sc_rational_feasibility_ofl_ctrl will return the value TRUE
                   * we don't know if the system is feasible or not
                   *
                   * The function sc_rational_feasibility_ofl_ctrl() is less
                   * expensive than the function sc_integer_feasibility_ofl_ctrl()*/
 
                  if (!sc_rational_feasibility_ofl_ctrl(P, OFL_CTRL, true))
                    /* The system is not feasible (certainly) => no violation */
                    set_array_dimension_checked(context,action,array,i,bound);
                  else
                    {
                      /* The system is feasible or we don't know it is feasible or not
                       * Test if the region re is EXACT or MAY */
                      if (region_exact_p(re))
                        {
                          /* EXACT region
                             Remove all PHI variables, useless variables such as
                             PIPS generated variables V#init, common variable
                             from another subroutine ......
 
                             SUBROUTINE X
                             CALL Y(I)
                             <P(I) {I == FOO:J}
                             END
 
                             SUBROUTINE Y(K)
                             COMMON J
                             K=J
                             END  */
                          Psysteme ps = my_system_remove_variables(P);
                          if (ps == SC_UNDEFINED)
                            // the projection is not exact
                            retour = top_down_abc_not_exact_case (s,context,action,array,dim_i,i,bound);
                          else
                            {
                                // the projection is exact
                              set_array_dimension_checked(context,action,array,i,bound);
                              if (!sc_empty_p(ps) && !sc_rn_p(ps))
                                // there is a test to put
                                // sc_normalized or sc_elim_redon ?????
                                retour.test = Psysteme_to_expression(ps);
                              else
                                if (sc_rn_p(ps))
                                  // the system is trivial true, there are bounds violation
                                  retour.test = make_true_expression();
                                //else, ps=sc_empty, the system is false, no bounds violation
                            }
                        }
                      else
                        /* MAY region */
                        retour = top_down_abc_not_exact_case(s,context,action,array,dim_i,i,bound);
                    }
                }
              else
                // the exp is not linear, we can't add to P
                retour.bound = false;
            }
          }
          contrainte_free(con_exp);
        }
      sc_rm(P);
    }
  return retour;
}

References array, binary_intrinsic_expression, Bound_test::bound, clean_all_normalized(), contrainte_free(), contrainte_make(), CONTRAINTE_UNDEFINED, copy_dimension(), dimension_lower, dimension_upper, entity_type, exp, expression_undefined, find_ith_dimension(), int_to_expression(), make_phi_entity(), make_true_expression(), MINUS_OPERATOR_NAME, my_system_remove_variables(), NORMALIZE_EXPRESSION, normalized_linear, normalized_linear_p, normalized_undefined, OFL_CTRL, PLUS_OPERATOR_NAME, Psysteme_to_expression(), region_exact_p, region_system, sc_add_phi_equation(), sc_check_inequality_redundancy(), sc_dup(), sc_empty_p(), sc_rational_feasibility_ofl_ctrl(), sc_rm(), sc_rn_p(), set_array_dimension_checked(), Bound_test::test, top_down_abc_not_exact_case(), type_variable, unbounded_dimension_p(), VALUE_ONE, variable_dimensions, vect_new(), vect_rm(), and vect_substract().

Referenced by top_down_abc_array().

Here is the call graph for this function:

Here is the caller graph for this function:

top_down_abc_flt()

static bool top_down_abc_flt ( statement  s, top_down_abc_context_p  context  )

static

The old algorithm is false in the case of incorrect code, because regions are computed with the assumption that the code is correct.

Here is an anti-example:

COMMON ITAB(10),J REAL A(10) C <A(PHI1)-W-EXACT-{PHI1==11}> C <ITAB(PHI1)-W-MAY-{1<=PHI1}> READ *, M J = 11 C <ITAB(PHI1)-W-EXACT-{1<=PHI1, PHI1<=M, J==11}> DO I = 1, M C <ITAB(PHI1)-W-EXACT-{PHI1==I, J==11, 1<=I, I<=M}> ITAB(I) = 1 ENDDO C <A(PHI1)-W-EXACT-{PHI1==J, J==11, 1+M<=I, 1<=I}> A(J) = 0

The region for array A can be false if there is a bound violation in ITAB for example with M=12, ITAB(11)=1=J, there will be no violation on A but on ITAB. Based on this false region, the algorithm will tell that there is a violation on A.

To keep the algorithm safe, we must take into account the order in which arrays are writen (bound violations on read arrays do not make transformers and array regions false). If bound checks on ITAB are inserted before checks on A, tests are checked earlier, so the region of A is not false any more. The tests must be:

COMMON ITAB(10),J REAL A(10) READ *, M IF (M.GT.10) STOP "Bound violation ITAB" STOP "Bound violation A" J = 11 DO I = 1, M ITAB(I) = 1 ENDDO A(J) = 0

Modify the algorithm: At each statement s, take its list of regions:

• If no array is written => apply the algorithm normally
• Else
  • Find the writing order
  • Apply the algorithm for the first written array, and then the second, ...
  • If the order is not found at s, go to the substatements of s

Compute the list of written arrays

while (!ENDP(l_copy)) { region re = REGION(CAR(l_copy)); reference ref = effect_any_reference(re); entity array = reference_variable(ref); if (array_reference_p(ref) && array_need_bound_check_p(array) && region_write_p(re)) l_written_arrays = CONS(ENTITY,array,l_written_arrays); l_copy = CDR(l_copy); } ifdebug(3) { fprintf(stderr, "\n List of written arrays : \n "); print_list_entities(l_written_arrays); }

If no array is written

check all arrays in l_regions

Choose the first written array and then generate checks for the read and write regions of this array. We can check the second array only when all dimensions of the written regions of the first array are checked

if there is no array that is always written before the others, we have to go down to substatements of s

Definition at line 942 of file array_bound_check_top_down.c.

{
  list l_regions = regions_dup(load_statement_local_regions(s));
  list l_copy = gen_full_copy_list(l_regions);
  list l_written_arrays = NIL;
  lexp = NIL;
  test_sequence = statement_undefined;
  godown = false;
  ifdebug(3)
    {
      fprintf(stderr, "\n list of regions ");
      print_effects(l_regions);
      fprintf(stderr, "\n for the statement");
      print_statement(s);
    }
  hash_put(context->read_saved_list,s,
           copy_abc_checked(context->read_marked_list));
  hash_put(context->write_saved_list,s,
           copy_abc_checked(context->write_marked_list));
 
  /* Compute the list of written arrays */
  /*  while (!ENDP(l_copy))
    {
      region re = REGION(CAR(l_copy));
      reference ref = effect_any_reference(re);
      entity array = reference_variable(ref);
      if (array_reference_p(ref)
      && array_need_bound_check_p(array)
      && region_write_p(re))
        l_written_arrays = CONS(ENTITY,array,l_written_arrays);
      l_copy = CDR(l_copy);
    }
  ifdebug(3)
    {
      fprintf(stderr, "\n List of written arrays : \n ");
      print_list_entities(l_written_arrays);
      }*/
 
  /* If no array is written */
  if (ENDP(l_written_arrays))
    {
      /* check all arrays in l_regions*/
      l_copy = gen_full_copy_list(l_regions);
      while (!ENDP(l_copy))
        {
          region re = REGION(CAR(l_copy));
          reference ref = effect_any_reference(re);
          entity array = reference_variable(ref);
          if (array_reference_p(ref) && array_need_bound_check_p(array))
            top_down_abc_array(array,re,s,context);
          l_copy = CDR(l_copy);
        }
    }
  else
    {
      /* Choose the first written array and then generate checks for
         the read and write regions of this array. We can check the
         second array only when all dimensions of the written regions
         of the first array are checked */
      while (!ENDP(l_written_arrays) && !godown)
        {
          entity first_array = find_first_written_array(l_written_arrays,s);
          /* if there is no array that is always written before the others,
             we have to go down to substatements of s*/
          if (entity_undefined_p(first_array))
            godown = true;
          else
            {
              ifdebug(3)
                {
                  fprintf(stderr, "\n First array: ");
                  fprintf(stderr, "%s ", entity_name(first_array));
                }
              gen_remove_once(&l_written_arrays,first_array);
              // check for the first array here
              l_copy = gen_full_copy_list(l_regions);
              while (!ENDP(l_copy))
                {
                  region re = REGION(CAR(l_copy));
                  reference ref = effect_any_reference(re);
                  entity array = reference_variable(ref);
                  //  if (same_entity_p(array,first_array))
                  if (strcmp(entity_name(array),entity_name(first_array))==0)
                    top_down_abc_array(array,re,s,context);
                  l_copy = CDR(l_copy);
                }
            }
        }
    }
  if (!statement_undefined_p(test_sequence))
    {
      ifdebug(3)
        {
          fprintf(stderr, "\n The sequence of test");
          print_statement(test_sequence);
        }
      if (!godown)
        // godown = false, insert new tests for the statement s here
        top_down_abc_insert_before_statement(s,test_sequence,context);
      else
        // insert new tests in function rwt
        hash_put(context->statement_check_list,s,test_sequence);
    }
  if (!godown)
    {
      context->read_marked_list =
        (abc_checked) hash_get(context->read_saved_list,s);
      context->write_marked_list =
        (abc_checked) hash_get(context->write_saved_list,s);
    }
  gen_free_list(l_regions);
  gen_free_list(lexp);
  lexp = NIL;
  test_sequence = statement_undefined;
  return godown;
}

References array, array_need_bound_check_p(), array_reference_p(), CAR, CDR, copy_abc_checked(), effect_any_reference, ENDP, entity_name, entity_undefined_p, find_first_written_array(), first_array, fprintf(), gen_free_list(), gen_full_copy_list(), gen_remove_once(), godown, hash_get(), hash_put(), ifdebug, lexp, load_statement_local_regions(), NIL, print_effects, print_statement(), ref, reference_variable, region, REGION, regions_dup(), statement_undefined, statement_undefined_p, test_sequence, top_down_abc_array(), and top_down_abc_insert_before_statement().

Referenced by top_down_abc_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

top_down_abc_insert_before_statement()

static void top_down_abc_insert_before_statement ( statement  s, statement  s1, top_down_abc_context_p  context  )

static

If s is in an unstructured instruction, we must pay attetion when inserting s1 before s.

take the control qui has s as statement

take the unstructured correspond to the control c

for a consistent unstructured, a test must have 2 successors, so if s1 is a test, we transform it into sequence in order to avoid this constraint. Then we create a new control for it, with the predecessors are those of c and the only one successor is c. The new predecessors of c are only the new control

if c is the entry node of the correspond unstructured u, the newc will become the new entry node of u

Definition at line 261 of file array_bound_check_top_down.c.

{
  /* If s is in an unstructured instruction, we must pay attetion
     when inserting s1 before s.  */
  if (bound_persistant_statement_to_control_p(context->map, s))
    {
      /* take the control qui has s as statement  */
      control c = apply_persistant_statement_to_control(context->map, s);
      if (stack_size(context->uns)>0)
        {
          /* take the unstructured correspond to the control c */
          unstructured u = (unstructured) stack_head(context->uns);
          control newc;
          /* for a consistent unstructured, a test must have 2 successors,
             so if s1 is a test, we transform it into sequence in order
             to avoid this constraint.
             Then we create a new control for it, with the predecessors
             are those of c and the only one successor is c.
             The new predecessors of c are only the new control*/
          if (statement_test_p(s1))
            {
              list seq = CONS(STATEMENT,s1,NIL);
              statement s2=
                instruction_to_statement(make_instruction(is_instruction_sequence,
                                                          make_sequence(seq)));
              newc = make_control(s2,control_predecessors(c),CONS(CONTROL,c,NIL));
            }
          else
            newc = make_control(s1,control_predecessors(c),CONS(CONTROL,c,NIL));
          // replace c by  newc as successor of each predecessor of c
          MAP(CONTROL, co,
          {
            MAPL(lc,
            {
              if (CONTROL(CAR(lc))==c) CONTROL_(CAR(lc)) = newc;
            }, control_successors(co));
          },control_predecessors(c));
          control_predecessors(c) = CONS(CONTROL,newc,NIL);
          /* if c is the entry node of the correspond unstructured u,
             the newc will become the new entry node of u */
          if (unstructured_control(u)==c)
            unstructured_control(u) = newc;
          gen_recurse_stop(newc); // ????????????
        }
      else
        // there is no unstructured (?)
        insert_statement(s,s1,true);
    }
  else
    // structured case
    insert_statement(s,s1,true);
}

References apply_persistant_statement_to_control(), bound_persistant_statement_to_control_p(), CAR, CONS, CONTROL, CONTROL_, control_predecessors, control_successors, gen_recurse_stop(), insert_statement(), instruction_to_statement(), is_instruction_sequence, make_control(), make_instruction(), make_sequence(), MAP, MAPL, NIL, s1, stack_head(), stack_size(), STATEMENT, statement_test_p(), and unstructured_control.

Referenced by top_down_abc_flt(), and top_down_abc_rwt().

Here is the call graph for this function:

Here is the caller graph for this function:

top_down_abc_not_exact_case()

static Bound_test top_down_abc_not_exact_case ( statement  s, top_down_abc_context_p  context, bool  action, entity  array, dimension  dim_i, int  i, bool  bound  )

static

Test if s is a call (elementary statement)

generate a lower/upper bound test expression for all array reference of this dimension of array

s is not a call, no conclusion for this bound, continue to go down

Definition at line 432 of file array_bound_check_top_down.c.

{
  Bound_test retour;
  retour.test = expression_undefined;
  retour.bound = true;
 
  /* Test if s is a call (elementary statement)*/
  if (statement_call_p(s))
    {
      /* generate a lower/upper bound test expression for all
         array reference of this dimension of array*/
      call c = instruction_call(statement_instruction(s));
      list l = top_down_abc_call(c,array,dim_i,i,bound);
      if (l!= NIL)
        retour.test = expression_list_to_binary_operator_call(l,
                                   entity_intrinsic(OR_OPERATOR_NAME));
      set_array_dimension_checked(context,action,array,i,bound);
      gen_free_list(l);
    }
  else
    /* s is not a call, no conclusion for this bound,
       continue to go down */
    retour.bound = false;
 
  return retour;
}

References array, Bound_test::bound, entity_intrinsic(), expression_list_to_binary_operator_call(), expression_undefined, gen_free_list(), instruction_call, NIL, OR_OPERATOR_NAME, set_array_dimension_checked(), statement_call_p(), statement_instruction, Bound_test::test, and top_down_abc_call().

Referenced by top_down_abc_dimension().

Here is the call graph for this function:

Here is the caller graph for this function:

top_down_abc_rwt()

static void top_down_abc_rwt ( statement  s, top_down_abc_context_p  context  )

static

Definition at line 1059 of file array_bound_check_top_down.c.

{
  statement test_sequence = statement_undefined;
  context->read_marked_list =
    (abc_checked) hash_get(context->read_saved_list,s);
  context->write_marked_list =
    (abc_checked) hash_get(context->write_saved_list,s);
  test_sequence = (statement) hash_get(context->statement_check_list,s);
  if (!statement_undefined_p(test_sequence))
    {
      ifdebug(3)
        {
          fprintf(stderr, "\n Rewrite : The sequence of test");
          print_statement(test_sequence);
          fprintf(stderr, "\n of statement");
          print_statement(s);
        }
      // insert the new sequence of tests before the current statement
      top_down_abc_insert_before_statement(s,test_sequence,context);
    }
}

References fprintf(), hash_get(), ifdebug, print_statement(), statement_undefined, statement_undefined_p, test_sequence, and top_down_abc_insert_before_statement().

Referenced by top_down_abc_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

top_down_abc_statement()

static void top_down_abc_statement ( statement  module_statement )

static

Definition at line 1102 of file array_bound_check_top_down.c.

{
  top_down_abc_context_t context;
  context.read_marked_list = initiliaze_marked_list();
  context.write_marked_list = copy_abc_checked(context.read_marked_list);
  context.read_saved_list =  hash_table_make(hash_pointer, 0);
  context.write_saved_list = hash_table_make(hash_pointer, 0);
 
  context.statement_check_list = hash_table_make(hash_pointer, 0);
  context.map = make_persistant_statement_to_control();
  context.uns = stack_make(unstructured_domain,0,0);
 
  gen_context_multi_recurse(module_statement, &context,
      unstructured_domain, push_uns, pop_uns,
      control_domain, store_mapping, gen_null,
      statement_domain, top_down_abc_flt, top_down_abc_rwt,
      NULL);
 
  free_abc_checked(context.read_marked_list);
  free_abc_checked(context.write_marked_list);
  hash_table_free(context.read_saved_list);
  hash_table_free(context.write_saved_list);
  hash_table_free(context.statement_check_list);
  free_persistant_statement_to_control(context.map);
  stack_free(&context.uns);
}

References control_domain, copy_abc_checked(), free_abc_checked(), free_persistant_statement_to_control(), gen_context_multi_recurse(), gen_null(), hash_pointer, hash_table_free(), hash_table_make(), initiliaze_marked_list(), make_persistant_statement_to_control(), module_statement, pop_uns(), push_uns(), stack_free(), stack_make(), statement_domain, store_mapping(), top_down_abc_flt(), top_down_abc_rwt(), and unstructured_domain.

Referenced by array_bound_check_top_down().

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

current_entity

entity current_entity = entity_undefined

static

Definition at line 595 of file array_bound_check_top_down.c.

Referenced by max_statement_write_flt(), maximum_ordering(), min_statement_write_flt(), and minimum_ordering().

current_max

int current_max

static

Definition at line 596 of file array_bound_check_top_down.c.

Referenced by max_size_of_processors(), max_statement_write_flt(), and maximum_ordering().

current_min

int current_min = 0

static

Definition at line 597 of file array_bound_check_top_down.c.

Referenced by min_statement_write_flt(), and minimum_ordering().

godown

bool godown = false

static

Definition at line 728 of file array_bound_check_top_down.c.

Referenced by top_down_abc_array(), and top_down_abc_flt().

lexp

list lexp = NIL

static

Definition at line 729 of file array_bound_check_top_down.c.

Referenced by assignation_filter(), build_bdt_null(), build_flag_assign(), build_flag_test(), build_global_time_test_with_exp(), build_local_time_test(), cmf_layout_align(), craft_layout_align(), ensure_comment_consistency(), expressions_to_vectors(), free_guards(), get_exp_schedule(), get_unsatisfied_system(), include_results_in_bdt(), include_trans_in_poly(), make_increment_instruction(), make_init_time(), MakeArrayExpression(), MakeWhileLoop(), prepare_reindexing(), reference_filter(), search_scc_bdt(), simplify_minmax(), system_new_var_subst(), top_down_abc_array(), top_down_abc_flt(), true_copy_schedule(), and vectors_to_expressions().

number_of_added_tests

int number_of_added_tests

static

Statistic variables:

Definition at line 124 of file array_bound_check_top_down.c.

Referenced by display_top_down_abc_statistics(), initialize_top_down_abc_statistics(), and top_down_abc_array().

number_of_bound_violations

int number_of_bound_violations

static

Definition at line 125 of file array_bound_check_top_down.c.

Referenced by display_top_down_abc_statistics(), initialize_top_down_abc_statistics(), and top_down_abc_array().

test_sequence

statement test_sequence = statement_undefined

static

Definition at line 727 of file array_bound_check_top_down.c.

Referenced by top_down_abc_array(), top_down_abc_flt(), and top_down_abc_rwt().