PIPS
|
#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"
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 |
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 struct Bound_test Bound_test |
typedef struct top_down_abc_context_t * top_down_abc_context_p |
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
module_name | odule_name |
Definition at line 1129 of file array_bound_check_top_down.c.
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().
Definition at line 115 of file array_bound_check_top_down.c.
Referenced by make_bottom_up_abc_tests(), and top_down_abc_array().
|
static |
Definition at line 133 of file array_bound_check_top_down.c.
References number_of_added_tests, number_of_bound_violations, and user_log().
Referenced by array_bound_check_top_down().
Definition at line 716 of file array_bound_check_top_down.c.
References ENTITY, entity_undefined, gen_full_copy_list(), is_first_written_array_p(), and MAP.
Referenced by top_down_abc_flt().
|
static |
Definition at line 127 of file array_bound_check_top_down.c.
References number_of_added_tests, and number_of_bound_violations.
Referenced by array_bound_check_top_down().
|
static |
Definition at line 148 of file array_bound_check_top_down.c.
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().
Definition at line 690 of file array_bound_check_top_down.c.
References ENTITY, entity_name, fprintf(), ifdebug, MAP, max, maximum_ordering(), min, and minimum_ordering().
Referenced by find_first_written_array().
Definition at line 599 of file array_bound_check_top_down.c.
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().
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.
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().
Definition at line 645 of file array_bound_check_top_down.c.
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().
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.
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().
Project all PHI and init variables, ....in the system ps, there are 2 cases :
converts the phi list into a Pvecteur
Definition at line 224 of file array_bound_check_top_down.c.
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().
|
static |
Definition at line 1095 of file array_bound_check_top_down.c.
References stack_pop().
Referenced by top_down_abc_statement().
|
static |
Definition at line 1089 of file array_bound_check_top_down.c.
References stack_push().
Referenced by top_down_abc_statement().
Definition at line 108 of file array_bound_check_top_down.c.
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().
|
static |
Definition at line 182 of file array_bound_check_top_down.c.
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().
|
static |
Definition at line 1082 of file array_bound_check_top_down.c.
References control_statement, and extend_persistant_statement_to_control().
Referenced by top_down_abc_statement().
|
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.
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().
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
Definition at line 316 of file array_bound_check_top_down.c.
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().
|
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.
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().
|
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:
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.
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().
|
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.
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().
|
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.
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().
|
static |
Definition at line 1059 of file array_bound_check_top_down.c.
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().
|
static |
Definition at line 1102 of file array_bound_check_top_down.c.
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().
|
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().
|
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().
|
static |
Definition at line 597 of file array_bound_check_top_down.c.
Referenced by min_statement_write_flt(), and minimum_ordering().
Definition at line 728 of file array_bound_check_top_down.c.
Referenced by top_down_abc_array(), and top_down_abc_flt().
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().
|
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().
|
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().
|
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().