#include "config.h"#include "system.h"#include "coretypes.h"#include "backend.h"#include "rtl.h"#include "tree.h"#include "gimple.h"#include "gimple-pretty-print.h"#include "alias.h"#include "fold-const.h"#include "expr.h"#include "gimple-iterator.h"#include "tree-ssa-loop-niter.h"#include "tree-ssa-loop.h"#include "tree-ssa.h"#include "cfgloop.h"#include "tree-data-ref.h"#include "tree-scalar-evolution.h"#include "dumpfile.h"#include "tree-affine.h"#include "builtins.h"#include "tree-eh.h"#include "ssa.h"#include "internal-fn.h"#include "vr-values.h"#include "range-op.h"#include "tree-ssa-loop-ivopts.h"#include "calls.h"
Data Structures | |
| struct | datadep_stats |
| struct | data_ref_loc |
Macros | |
| #define | INCLUDE_ALGORITHM |
| #define | FLOOR_DIV(x, y) |
Variables | |
| static struct datadep_stats | dependence_stats |
Macro Definition Documentation
◆ FLOOR_DIV
| #define FLOOR_DIV | ( | x, | |
| y ) |
Referenced by compute_overlap_steps_for_affine_univar().
◆ INCLUDE_ALGORITHM
| #define INCLUDE_ALGORITHM |
Data references and dependences detectors. Copyright (C) 2003-2024 Free Software Foundation, Inc. Contributed by Sebastian Pop <pop@cri.ensmp.fr> This file is part of GCC. GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version. GCC is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with GCC; see the file COPYING3. If not see <http://www.gnu.org/licenses/>.
This pass walks a given loop structure searching for array
references. The information about the array accesses is recorded
in DATA_REFERENCE structures.
The basic test for determining the dependences is:
given two access functions chrec1 and chrec2 to a same array, and
x and y two vectors from the iteration domain, the same element of
the array is accessed twice at iterations x and y if and only if:
| chrec1 (x) == chrec2 (y).
The goals of this analysis are:
- to determine the independence: the relation between two
independent accesses is qualified with the chrec_known (this
information allows a loop parallelization),
- when two data references access the same data, to qualify the
dependence relation with classic dependence representations:
- distance vectors
- direction vectors
- loop carried level dependence
- polyhedron dependence
or with the chains of recurrences based representation,
- to define a knowledge base for storing the data dependence
information,
- to define an interface to access this data.
Definitions:
- subscript: given two array accesses a subscript is the tuple
composed of the access functions for a given dimension. Example:
Given A[f1][f2][f3] and B[g1][g2][g3], there are three subscripts:
(f1, g1), (f2, g2), (f3, g3).
- Diophantine equation: an equation whose coefficients and
solutions are integer constants, for example the equation
| 3*x + 2*y = 1
has an integer solution x = 1 and y = -1.
References:
- "Advanced Compilation for High Performance Computing" by Randy
Allen and Ken Kennedy.
http://citeseer.ist.psu.edu/goff91practical.html
- "Loop Transformations for Restructuring Compilers - The Foundations"
by Utpal Banerjee.
Function Documentation
◆ access_fn_component_p()
Return true if OP is a valid component reference for a DR access function. This accepts a subset of what handled_component_p accepts.
References TREE_CODE, TREE_OPERAND, and TREE_TYPE.
Referenced by initialize_data_dependence_relation().
◆ access_fn_components_comparable_p()
REF_A and REF_B both satisfy access_fn_component_p. Return true if it is meaningful to compare their associated access functions when checking for dependencies.
References DECL_CONTEXT, TREE_CODE, TREE_OPERAND, TREE_TYPE, and types_compatible_p().
Referenced by initialize_data_dependence_relation().
◆ access_functions_are_affine_or_constant_p()
|
static |
Returns true when all the access functions of A are affine or constant with respect to LOOP_NEST.
References a, DR_ACCESS_FNS, evolution_function_is_affine_multivariate_p(), evolution_function_is_invariant_p(), and loop::num.
Referenced by compute_affine_dependence().
◆ add_distance_for_zero_overlaps()
|
static |
Adds a unit distance vector to DDR when there is a 0 overlap. This is the case for example when access functions are the same and equal to a constant, as in: | loop_1 | A[3] = ... | ... = A[3] | endloop_1 in which case the distance vectors are (0) and (1).
References affine_function_zero_p(), DDR_NUM_SUBSCRIPTS, DDR_SUBSCRIPT, conflict_function::fns, i, insert_innermost_unit_dist_vector(), conflict_function::n, SUB_CONFLICTS_IN_A, and SUB_CONFLICTS_IN_B.
Referenced by build_classic_dist_vector().
◆ add_multivariate_self_dist()
|
static |
Helper function for the case where DDR_A and DDR_B are the same multivariate access function with a constant step. For an example see pr34635-1.c.
References add_outer_distances(), cd, CHREC_LEFT, CHREC_RIGHT, CHREC_VARIABLE, DDR_AFFINE_P, DDR_LOOP_NEST, DDR_NB_LOOPS, gcd(), index_in_loop_nest(), int_cst_value(), lambda_vector_new(), save_dist_v(), and TREE_CODE.
Referenced by add_other_self_distances().
◆ add_other_self_distances()
|
static |
Helper function for the case where DDR_A and DDR_B are the same access functions.
References add_multivariate_self_dist(), add_outer_distances(), cfun, chrec_dont_know, CHREC_LEFT, CHREC_VARIABLE, DDR_AFFINE_P, DDR_ARE_DEPENDENT, DDR_LOOP_NEST, DDR_NB_LOOPS, DDR_NUM_SUBSCRIPTS, DDR_SUBSCRIPT, DDR_SUBSCRIPTS, evolution_function_is_univariate_p(), flow_loop_nested_p(), FOR_EACH_VEC_ELT, get_loop(), i, index_in_loop_nest(), lambda_vector_new(), MIN, loop::num, SUB_ACCESS_FN, and TREE_CODE.
Referenced by build_classic_dist_vector().
◆ add_outer_distances()
|
static |
Add a distance of 1 on all the loops outer than INDEX. If we haven't yet determined a distance for this outer loop, push a new distance vector composed of the previous distance, and a distance of 1 for this outer loop. Example: | loop_1 | loop_2 | A[10] | endloop_2 | endloop_1 Saved vectors are of the form (dist_in_1, dist_in_2). First, we save (0, 1), then we have to save (1, 0).
References DDR_NB_LOOPS, lambda_vector_copy(), lambda_vector_new(), and save_dist_v().
Referenced by add_multivariate_self_dist(), add_other_self_distances(), and build_classic_dist_vector().
◆ affine_fn_cst()
Returns constant affine function with value CST.
Referenced by analyze_miv_subscript(), analyze_overlapping_iterations(), analyze_siv_subscript_cst_affine(), analyze_subscript_affine_affine(), analyze_ziv_subscript(), compute_overlap_steps_for_affine_1_2(), and compute_overlap_steps_for_affine_univar().
◆ affine_fn_free()
|
static |
Frees affine function FN.
Referenced by compute_overlap_steps_for_affine_1_2(), compute_subscript_distance(), and free_conflict_function().
◆ affine_fn_minus()
Returns the difference of affine functions FNA and FNB.
References affine_fn_op().
Referenced by compute_subscript_distance().
◆ affine_fn_op()
Applies operation OP on affine functions FNA and FNB, and returns the result.
References fold_build2, i, integer_zero_node, signed_type_for(), signed_type_for_types(), and TREE_TYPE.
Referenced by affine_fn_minus(), and affine_fn_plus().
◆ affine_fn_plus()
Returns the sum of affine functions FNA and FNB.
References affine_fn_op().
Referenced by compute_overlap_steps_for_affine_1_2().
◆ affine_fn_univar()
Returns affine function with single variable, CST + COEF * x_DIM.
References gcc_assert, i, and integer_zero_node.
Referenced by analyze_subscript_affine_affine(), and compute_overlap_steps_for_affine_univar().
◆ affine_function_base()
Returns the base of the affine function FN.
Referenced by affine_function_zero_p(), and compute_subscript_distance().
◆ affine_function_constant_p()
Returns true if FN is a constant.
References i, and integer_zerop().
Referenced by affine_function_zero_p(), and compute_subscript_distance().
◆ affine_function_equal_p()
Returns true if FNA == FNB.
References i, and operand_equal_p().
Referenced by common_affine_function().
◆ affine_function_zero_p()
Returns true if FN is the zero constant function.
References affine_function_base(), affine_function_constant_p(), and integer_zerop().
Referenced by add_distance_for_zero_overlaps().
◆ analyze_miv_subscript()
|
static |
Analyze a MIV (Multiple Index Variable) subscript with respect to LOOP_NEST. *OVERLAPS_A and *OVERLAPS_B are initialized to the functions that describe the relation between the elements accessed twice by CHREC_A and CHREC_B. For k >= 0, the following property is verified: CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).
References affine_fn_cst(), analyze_subscript_affine_affine(), CF_NO_DEPENDENCE_P, CF_NOT_KNOWN_P, chrec_contains_symbols(), chrec_convert(), chrec_dont_know, chrec_fold_minus(), conflict_fn(), conflict_fn_no_dependence(), conflict_fn_not_known(), dependence_stats, dump_file, dump_flags, eq_evolutions_p(), evolution_function_is_affine_in_loop(), evolution_function_is_affine_multivariate_p(), evolution_function_is_constant_p(), gcd_of_steps_may_divide_p(), get_chrec_loop(), integer_zero_node, max_stmt_executions_tree(), NULL, loop::num, datadep_stats::num_miv, datadep_stats::num_miv_dependent, datadep_stats::num_miv_independent, datadep_stats::num_miv_unimplemented, signed_type_for_types(), TDF_DETAILS, TREE_TYPE, and type().
Referenced by analyze_overlapping_iterations().
◆ analyze_overlapping_iterations()
|
static |
Determines the iterations for which CHREC_A is equal to CHREC_B in with respect to LOOP_NEST. OVERLAP_ITERATIONS_A and OVERLAP_ITERATIONS_B are initialized with two functions that describe the iterations that contain conflicting elements. Remark: For an integer k >= 0, the following equality is true: CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
References affine_fn_cst(), analyze_miv_subscript(), analyze_siv_subscript(), analyze_ziv_subscript(), chrec_contains_symbols(), chrec_contains_undetermined(), chrec_dont_know, conflict_fn(), conflict_fn_not_known(), dependence_stats, dump_conflict_function(), dump_file, dump_flags, eq_evolutions_p(), evolution_function_is_affine_multivariate_p(), integer_zero_node, NULL_TREE, loop::num, datadep_stats::num_same_subscript_function, datadep_stats::num_subscript_tests, datadep_stats::num_subscript_undetermined, operand_equal_p(), print_generic_expr(), siv_subscript_p(), TDF_DETAILS, and ziv_subscript_p().
Referenced by subscript_dependence_tester_1().
◆ analyze_siv_subscript()
|
static |
Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and *OVERLAPS_B are initialized to the functions that describe the relation between the elements accessed twice by CHREC_A and CHREC_B. For k >= 0, the following property is verified: CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).
References analyze_siv_subscript_cst_affine(), analyze_subscript_affine_affine(), can_use_analyze_subscript_affine_affine(), CF_NO_DEPENDENCE_P, CF_NOT_KNOWN_P, chrec_contains_symbols(), chrec_dont_know, conflict_fn_not_known(), dependence_stats, dump_file, dump_flags, evolution_function_is_affine_in_loop(), evolution_function_is_constant_p(), datadep_stats::num_siv, datadep_stats::num_siv_dependent, datadep_stats::num_siv_independent, datadep_stats::num_siv_unimplemented, and TDF_DETAILS.
Referenced by analyze_overlapping_iterations().
◆ analyze_siv_subscript_cst_affine()
|
static |
Analyze a SIV (Single Index Variable) subscript where CHREC_A is a constant, and CHREC_B is an affine function. *OVERLAPS_A and *OVERLAPS_B are initialized to the functions that describe the relation between the elements accessed twice by CHREC_A and CHREC_B. For k >= 0, the following property is verified: CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).
References affine_fn_cst(), chrec_convert(), chrec_dont_know, chrec_fold_minus(), chrec_is_positive(), CHREC_RIGHT, compare_tree_int(), conflict_fn(), conflict_fn_no_dependence(), conflict_fn_not_known(), dependence_stats, dump_file, dump_flags, fold_build1, fold_build2, free_conflict_function(), get_chrec_loop(), initial_condition(), integer_one_node, integer_zero_node, integer_zerop(), max_stmt_executions_int(), NULL, datadep_stats::num_siv_dependent, datadep_stats::num_siv_independent, datadep_stats::num_siv_unimplemented, signed_type_for_types(), TDF_DETAILS, TREE_CODE, tree_fold_divides_p(), TREE_TYPE, and type().
Referenced by analyze_siv_subscript().
◆ analyze_subscript_affine_affine()
|
static |
Determines the overlapping elements due to accesses CHREC_A and CHREC_B, that are affine functions. This function cannot handle symbolic evolution functions, ie. when initial conditions are parameters, because it uses lambda matrices of integers.
References affine_fn_cst(), affine_fn_univar(), build_int_cst(), CEIL, chrec_dont_know, CHREC_RIGHT, compute_overlap_steps_for_affine_1_2(), compute_overlap_steps_for_affine_univar(), conflict_fn(), conflict_fn_no_dependence(), conflict_fn_not_known(), dump_conflict_function(), dump_file, dump_flags, eq_evolutions_p(), gcc_obstack_init, get_chrec_loop(), i1, initialize_matrix_A(), int_cst_value(), int_divides_p(), integer_type_node, integer_zero_node, lambda_matrix_new(), lambda_matrix_right_hermite(), lambda_matrix_row_negate(), MAX, max_stmt_executions_int(), MIN, wi::min_precision(), nb_vars_in_chrec(), NULL, NULL_TREE, obstack, S, wi::sdiv_floor(), SIGNED, wi::smin(), wi::sub(), TDF_DETAILS, generic_wide_int< storage >::to_shwi(), and TYPE_PRECISION.
Referenced by analyze_miv_subscript(), and analyze_siv_subscript().
◆ analyze_ziv_subscript()
|
static |
Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and *OVERLAPS_B are initialized to the functions that describe the relation between the elements accessed twice by CHREC_A and CHREC_B. For k >= 0, the following property is verified: CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).
References affine_fn_cst(), chrec_convert(), chrec_dont_know, chrec_fold_minus(), conflict_fn(), conflict_fn_no_dependence(), conflict_fn_not_known(), dependence_stats, dump_file, dump_flags, integer_zero_node, integer_zerop(), NULL, datadep_stats::num_ziv, datadep_stats::num_ziv_dependent, datadep_stats::num_ziv_independent, datadep_stats::num_ziv_unimplemented, signed_type_for_types(), TDF_DETAILS, TREE_CODE, TREE_TYPE, and type().
Referenced by analyze_overlapping_iterations().
◆ base_supports_access_fn_components_p()
Returns whether BASE can have a access_fn_component_p with BASE as base.
References TREE_CODE, and TREE_TYPE.
Referenced by initialize_data_dependence_relation().
◆ build_classic_dir_vector()
|
static |
Compute the classic per loop direction vector. DDR is the data dependence relation to build a vector from.
References DDR_DIST_VECTS, DDR_NB_LOOPS, dir_from_dist(), FOR_EACH_VEC_ELT, i, lambda_vector_new(), and save_dir_v().
Referenced by subscript_dependence_tester().
◆ build_classic_dist_vector()
|
static |
Compute the classic per loop distance vector. DDR is the data dependence relation to build a vector from. Return false when fail to represent the data dependence as a distance vector.
References add_distance_for_zero_overlaps(), add_other_self_distances(), add_outer_distances(), build_classic_dist_vector_1(), compute_subscript_distance(), DDR_ARE_DEPENDENT, DDR_NB_LOOPS, DDR_REVERSED_P, invariant_access_functions(), lambda_vector_copy(), lambda_vector_first_nz(), lambda_vector_lexico_pos(), lambda_vector_new(), NULL_TREE, loop::num, same_access_functions(), save_dist_v(), and subscript_dependence_tester_1().
Referenced by subscript_dependence_tester().
◆ build_classic_dist_vector_1()
|
static |
Return false when fail to represent the data dependence as a distance vector. A_INDEX is the index of the first reference (0 for DDR_A, 1 for DDR_B) and B_INDEX is the index of the second reference. INIT_B is set to true when a component has been added to the distance vector DIST_V. INDEX_CARRY is then set to the index in DIST_V that carries the dependence.
References cfun, chrec_contains_undetermined(), chrec_known, CHREC_VARIABLE, DDR_LOOP_NEST, DDR_NB_LOOPS, DDR_NUM_SUBSCRIPTS, DDR_SUBSCRIPT, finalize_ddr_dependent(), flow_loop_nested_p(), get_loop(), i, index_in_loop_nest(), int_cst_value(), lambda_vector_new(), MIN, non_affine_dependence_relation(), operand_equal_p(), SUB_ACCESS_FN, SUB_DISTANCE, and TREE_CODE.
Referenced by build_classic_dist_vector().
◆ can_use_analyze_subscript_affine_affine()
Returns true when analyze_subscript_affine_affine can be used for
determining the dependence relation between chrec_a and chrec_b,
that contain symbols. This function modifies chrec_a and chrec_b
such that the analysis result is the same, and such that they don't
contain symbols, and then can safely be passed to the analyzer.
Example: The analysis of the following tuples of evolutions produce
the same results: {x+1, +, 1}_1 vs. {x+3, +, 1}_1, and {-2, +, 1}_1
vs. {0, +, 1}_1
{x+1, +, 1}_1 ({2, +, 1}_1) = {x+3, +, 1}_1 ({0, +, 1}_1)
{-2, +, 1}_1 ({2, +, 1}_1) = {0, +, 1}_1 ({0, +, 1}_1)
References build_int_cst(), build_polynomial_chrec(), chrec_contains_symbols(), chrec_convert(), chrec_fold_minus(), CHREC_LEFT, CHREC_RIGHT, chrec_type(), CHREC_VARIABLE, dump_file, dump_flags, evolution_function_is_constant_p(), NULL, TDF_DETAILS, and type().
Referenced by analyze_siv_subscript().
◆ canonicalize_base_object_address()
Returns the address ADDR of an object in a canonical shape (without nop casts, and with type of pointer to the object).
References build_fold_addr_expr, POINTER_TYPE_P, STRIP_NOPS, TREE_CODE, TREE_OPERAND, and TREE_TYPE.
Referenced by dr_analyze_innermost().
◆ chrec_is_positive()
Determine whether the CHREC is always positive/negative. If the expression cannot be statically analyzed, return false, otherwise set the answer into VALUE.
References build_int_cst(), chrec_apply(), chrec_contains_undetermined(), chrec_fold_minus(), chrec_is_positive(), CHREC_LEFT, CHREC_RIGHT, CHREC_VARIABLE, evolution_function_is_affine_p(), get_chrec_loop(), number_of_latch_executions(), TREE_CODE, and tree_int_cst_sgn().
Referenced by analyze_siv_subscript_cst_affine(), and chrec_is_positive().
◆ common_affine_function()
|
static |
If all the functions in CF are the same, returns one of them, otherwise returns NULL.
References affine_function_equal_p(), CF_NONTRIVIAL_P, conflict_function::fns, i, and conflict_function::n.
Referenced by compute_subscript_distance().
◆ comp_dr_with_seg_len_pair()
|
static |
Comparison function for sorting objects of dr_with_seg_len_pair_t so that we can combine aliasing checks in one scan.
References data_ref_compare_tree(), dr_with_seg_len::dr, DR_BASE_ADDRESS, DR_INIT, DR_OFFSET, DR_STEP, dr_with_seg_len_pair_t::first, and dr_with_seg_len_pair_t::second.
Referenced by prune_runtime_alias_test_list().
◆ compute_affine_dependence()
| void compute_affine_dependence | ( | struct data_dependence_relation * | ddr, |
| class loop * | loop_nest ) |
This computes the affine dependence relation between A and B with respect to LOOP_NEST. CHREC_KNOWN is used for representing the independence between two accesses, while CHREC_DONT_KNOW is used for representing the unknown relation. Note that it is possible to stop the computation of the dependence relation the first time we detect a CHREC_KNOWN element for a given subscript.
References access_functions_are_affine_or_constant_p(), chrec_dont_know, chrec_known, DDR_A, DDR_ARE_DEPENDENT, DDR_B, dependence_stats, DR_REF, DR_STMT, dump_data_reference(), dump_file, dump_flags, finalize_ddr_dependent(), NULL_TREE, datadep_stats::num_dependence_tests, datadep_stats::num_dependence_undetermined, print_generic_expr(), print_gimple_stmt(), subscript_dependence_tester(), TDF_DETAILS, and TDF_SLIM.
Referenced by compute_all_dependences(), and loop_distribution::get_data_dependence().
◆ compute_all_dependences()
| bool compute_all_dependences | ( | const vec< data_reference_p > & | datarefs, |
| vec< ddr_p > * | dependence_relations, | ||
| const vec< loop_p > & | loop_nest, | ||
| bool | compute_self_and_rr ) |
Compute in DEPENDENCE_RELATIONS the data dependence graph for all the data references in DATAREFS, in the LOOP_NEST. When COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self relations. Return true when successful, i.e. data references number is small enough to be handled.
References a, b, compute_affine_dependence(), DR_IS_WRITE, FOR_EACH_VEC_ELT, i, initialize_data_dependence_relation(), data_dependence_relation::loop_nest, and NULL.
Referenced by compute_data_dependences_for_loop(), cond_if_else_store_replacement(), determine_loop_nest_reuse(), and vect_analyze_data_ref_dependences().
◆ compute_data_dependences_for_loop()
| bool compute_data_dependences_for_loop | ( | class loop * | loop, |
| bool | compute_self_and_read_read_dependences, | ||
| vec< loop_p > * | loop_nest, | ||
| vec< data_reference_p > * | datarefs, | ||
| vec< ddr_p > * | dependence_relations ) |
Returns true when the data dependences have been computed, false otherwise. Given a loop nest LOOP, the following vectors are returned: DATAREFS is initialized to all the array elements contained in this loop, DEPENDENCE_RELATIONS contains the relations between the data references. Compute read-read and self relations if COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE.
References chrec_dont_know, compute_all_dependences(), dependence_stats, dump_file, dump_flags, find_data_references_in_loop(), find_loop_nest(), datadep_stats::num_dependence_dependent, datadep_stats::num_dependence_independent, datadep_stats::num_dependence_tests, datadep_stats::num_dependence_undetermined, datadep_stats::num_miv, datadep_stats::num_miv_dependent, datadep_stats::num_miv_independent, datadep_stats::num_miv_unimplemented, datadep_stats::num_same_subscript_function, datadep_stats::num_siv, datadep_stats::num_siv_dependent, datadep_stats::num_siv_independent, datadep_stats::num_siv_unimplemented, datadep_stats::num_subscript_tests, datadep_stats::num_subscript_undetermined, datadep_stats::num_ziv, datadep_stats::num_ziv_dependent, datadep_stats::num_ziv_independent, datadep_stats::num_ziv_unimplemented, and TDF_STATS.
Referenced by loop_parallel_p(), tree_loop_unroll_and_jam(), and pcom_worker::tree_predictive_commoning_loop().
◆ compute_distributive_range()
|
static |
If RESULT_RANGE is nonnull, set *RESULT_RANGE to the range of
OP0 CODE OP1, where:
- OP0 CODE OP1 has integral type TYPE
- the range of OP0 is given by OP0_RANGE and
- the range of OP1 is given by OP1_RANGE.
Independently of RESULT_RANGE, try to compute:
DELTA = ((sizetype) OP0 CODE (sizetype) OP1)
- (sizetype) (OP0 CODE OP1)
as a constant and subtract DELTA from the ssizetype constant in *OFF.
Return true on success, or false if DELTA is not known at compile time.
Truncation and sign changes are known to distribute over CODE, i.e.
(itype) (A CODE B) == (itype) A CODE (itype) B
for any integral type ITYPE whose precision is no greater than the
precision of A and B.
References range_op_handler::fold_range(), gcc_assert, wide_int_storage::get_precision(), INTEGRAL_TYPE_P, irange::lower_bound(), wi::mask(), irange::num_pairs(), range_cast(), irange::set_varying(), sizetype, ssizetype, wi::to_wide(), TYPE_OVERFLOW_TRAPS, TYPE_OVERFLOW_UNDEFINED, TYPE_PRECISION, TYPE_UNSIGNED, vrange::undefined_p(), irange::upper_bound(), vrange::varying_p(), and wide_int_to_tree().
Referenced by split_constant_offset_1().
◆ compute_overlap_steps_for_affine_1_2()
|
static |
Solves the special case of a Diophantine equation where CHREC_A is
an affine bivariate function, and CHREC_B is an affine univariate
function. For example,
| {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
has the following overlapping functions:
| x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
| y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
| z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
FORNOW: This is a specialized implementation for a case occurring in
a common benchmark. Implement the general algorithm.
References affine_fn_cst(), affine_fn_free(), affine_fn_plus(), chrec_dont_know, CHREC_LEFT, CHREC_RIGHT, compute_overlap_steps_for_affine_univar(), conflict_fn(), conflict_fn_not_known(), dump_file, dump_flags, get_chrec_loop(), int_cst_value(), integer_zero_node, integer_zerop(), max_stmt_executions_int(), MIN, and TDF_DETAILS.
Referenced by analyze_subscript_affine_affine().
◆ compute_overlap_steps_for_affine_univar()
|
static |
Solves the special case of the Diophantine equation:
| {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the
number of iterations that loops X and Y run. The overlaps will be
constructed as evolutions in dimension DIM.
References affine_fn_cst(), affine_fn_univar(), build_int_cst(), chrec_dont_know, FLOOR_DIV, gcd(), integer_zero_node, MIN, and NULL_TREE.
Referenced by analyze_subscript_affine_affine(), and compute_overlap_steps_for_affine_1_2().
◆ compute_subscript_distance()
|
static |
Determine for each subscript in the data dependence relation DDR the distance.
References affine_fn_free(), affine_fn_minus(), affine_function_base(), affine_function_constant_p(), chrec_dont_know, common_affine_function(), DDR_ARE_DEPENDENT, DDR_NUM_SUBSCRIPTS, DDR_SUBSCRIPT, i, NULL_TREE, SUB_CONFLICTS_IN_A, SUB_CONFLICTS_IN_B, and SUB_DISTANCE.
Referenced by build_classic_dist_vector(), and subscript_dependence_tester().
◆ conflict_fn()
|
static |
Creates a conflict function with N dimensions. The affine functions in each dimension follow.
References ap, conflict_function::fns, gcc_assert, i, MAX_DIM, and conflict_function::n.
Referenced by analyze_miv_subscript(), analyze_overlapping_iterations(), analyze_siv_subscript_cst_affine(), analyze_subscript_affine_affine(), analyze_ziv_subscript(), and compute_overlap_steps_for_affine_1_2().
◆ conflict_fn_no_dependence()
|
static |
Returns the conflict function for "independent".
References conflict_function::n, and NO_DEPENDENCE.
Referenced by analyze_miv_subscript(), analyze_siv_subscript_cst_affine(), analyze_subscript_affine_affine(), and analyze_ziv_subscript().
◆ conflict_fn_not_known()
|
static |
Returns the conflict function for "unknown".
References conflict_function::n, and NOT_KNOWN.
Referenced by analyze_miv_subscript(), analyze_overlapping_iterations(), analyze_siv_subscript(), analyze_siv_subscript_cst_affine(), analyze_subscript_affine_affine(), analyze_ziv_subscript(), compute_overlap_steps_for_affine_1_2(), and initialize_data_dependence_relation().
◆ create_data_ref()
| struct data_reference * create_data_ref | ( | edge | nest, |
| loop_p | loop, | ||
| tree | memref, | ||
| gimple * | stmt, | ||
| bool | is_read, | ||
| bool | is_conditional_in_stmt ) |
Analyze memory reference MEMREF, which is accessed in STMT. The reference is a read if IS_READ is true, otherwise it is a write. IS_CONDITIONAL_IN_STMT indicates that the reference is conditional within STMT, i.e. that it might not occur even if STMT is executed and runs to completion. Return the data_reference description of MEMREF. NEST is the outermost loop in which the reference should be instantiated, LOOP is the loop in which the data reference should be analyzed.
References DR_ACCESS_FN, dr_analyze_alias(), dr_analyze_indices(), dr_analyze_innermost(), DR_BASE_ADDRESS, DR_BASE_ALIGNMENT, DR_BASE_MISALIGNMENT, DR_BASE_OBJECT, DR_INIT, DR_INNERMOST, DR_IS_CONDITIONAL_IN_STMT, DR_IS_READ, DR_NUM_DIMENSIONS, DR_OFFSET, DR_OFFSET_ALIGNMENT, DR_REF, DR_STEP, DR_STEP_ALIGNMENT, DR_STMT, dump_file, dump_flags, i, data_reference::indices, data_reference::is_conditional_in_stmt, data_reference::is_read, NULL, print_generic_expr(), print_generic_stmt(), data_reference::stmt, TDF_DETAILS, and TDF_SLIM.
Referenced by determine_loop_nest_reuse(), dse_classify_store(), find_data_references_in_stmt(), graphite_find_data_references_in_stmt(), and vect_find_stmt_data_reference().
◆ create_ifn_alias_checks()
|
static |
A subroutine of create_intersect_range_checks, with a subset of the same arguments. Try to use IFN_CHECK_RAW_PTRS and IFN_CHECK_WAR_PTRS to optimize cases in which the references form a simple RAW, WAR or WAR dependence.
References dr_with_seg_len::access_size, dr_with_seg_len::align, boolean_type_node, build_call_expr_internal_loc(), dr_with_seg_len::dr, DR_ALIAS_RAW, DR_ALIAS_WAR, DR_ALIAS_WAW, DR_BASE_ADDRESS, DR_INIT, DR_OFFSET, DR_STEP, dump_enabled_p(), dump_printf(), fold_build_pointer_plus, internal_check_ptrs_fn_supported_p(), MIN, MSG_NOTE, operand_equal_p(), poly_int_tree_p(), dr_with_seg_len::seg_len, size_int, tree_fits_uhwi_p(), tree_to_uhwi(), TREE_TYPE, and UNKNOWN_LOCATION.
Referenced by create_intersect_range_checks().
◆ create_intersect_range_checks()
|
static |
Generate a runtime condition that is true if ALIAS_PAIR is free of aliases, storing the condition in *COND_EXPR. The fallback is to generate a a test that the two accesses do not overlap: end_a <= start_b || end_b <= start_a.
References dr_with_seg_len::access_size, dr_with_seg_len::align, boolean_type_node, create_ifn_alias_checks(), create_intersect_range_checks_index(), create_waw_or_war_checks(), dr_with_seg_len::dr, DR_STEP, dump_enabled_p(), dump_printf(), fold_build2, get_segment_min_max(), min_align(), MSG_NOTE, NULL_TREE, and TREE_CODE.
Referenced by create_runtime_alias_checks().
◆ create_intersect_range_checks_index()
|
static |
Try to generate a runtime condition that is true if ALIAS_PAIR is
free of aliases, using a condition based on index values instead
of a condition based on addresses. Return true on success,
storing the condition in *COND_EXPR.
This can only be done if the two data references in ALIAS_PAIR access
the same array object and the index is the only difference. For example,
if the two data references are DR_A and DR_B:
DR_A DR_B
data-ref arr[i] arr[j]
base_object arr arr
index {i_0, +, 1}_loop {j_0, +, 1}_loop
The addresses and their index are like:
|<- ADDR_A ->| |<- ADDR_B ->|
------------------------------------------------------->
| | | | | | | | | |
------------------------------------------------------->
i_0 ... i_0+4 j_0 ... j_0+4
We can create expression based on index rather than address:
(unsigned) (i_0 - j_0 + 3) <= 6
i.e. the indices are less than 4 apart.
Note evolution step of index needs to be considered in comparison.
References dr_with_seg_len::access_size, boolean_type_node, CHREC_LEFT, CHREC_RIGHT, CHREC_VARIABLE, dr_with_seg_len::dr, DR_ACCESS_FN, DR_ALIAS_MIXED_STEPS, DR_ALIAS_WAR, DR_ALIAS_WAW, DR_BASE_OBJECT, DR_NUM_DIMENSIONS, DR_STEP, dump_enabled_p(), dump_printf(), wi::fits_to_tree_p(), fold_build2, fold_convert, gcc_assert, i, integer_zerop(), known_ge, MSG_NOTE, loop::num, operand_equal_p(), poly_int_tree_p(), dr_with_seg_len::seg_len, SIGNED, size_zero_node, wi::to_offset(), wi::to_poly_wide(), wi::to_wide(), TREE_CODE, tree_fits_shwi_p(), tree_int_cst_compare(), tree_int_cst_sign_bit(), tree_to_shwi(), TREE_TYPE, types_compatible_p(), unsigned_type_for(), and wide_int_to_tree().
Referenced by create_intersect_range_checks().
◆ create_runtime_alias_checks()
| void create_runtime_alias_checks | ( | class loop * | loop, |
| const vec< dr_with_seg_len_pair_t > * | alias_pairs, | ||
| tree * | cond_expr ) |
Create a conditional expression that represents the run-time checks for overlapping of address ranges represented by a list of data references pairs passed in ALIAS_PAIRS. Data references are in LOOP. The returned COND_EXPR is the conditional expression to be used in the if statement that controls which version of the loop gets executed at runtime.
References alias_pairs, boolean_type_node, create_intersect_range_checks(), DR_REF, dump_enabled_p(), dump_printf(), fold_build2, fold_defer_overflow_warnings(), fold_undefer_and_ignore_overflow_warnings(), gcc_assert, and MSG_NOTE.
Referenced by vect_create_cond_for_alias_checks(), and version_loop_by_alias_check().
◆ create_waw_or_war_checks()
|
static |
A subroutine of create_intersect_range_checks, with a subset of the same arguments. Try to optimize cases in which the second access is a write and in which some overlap is valid.
References dr_with_seg_len::access_size, dr_with_seg_len::align, boolean_type_node, build1(), CONSTANT_CLASS_P, dr_with_seg_len::dr, DR_ALIAS_WAR, DR_ALIAS_WAW, DR_BASE_ADDRESS, dr_direction_indicator(), DR_INIT, DR_OFFSET, DR_STEP, dump_enabled_p(), dump_printf(), fold_build2, fold_build3, fold_build_pointer_plus, fold_convert, MIN, MSG_NOTE, operand_equal_p(), rewrite_to_non_trapping_overflow(), dr_with_seg_len::seg_len, size_int, size_zero_node, sizetype, ssize_int, ssizetype, TREE_TYPE, and TYPE_PRECISION.
Referenced by create_intersect_range_checks().
◆ data_ref_compare_tree()
A helper function computes order between two tree expressions T1 and T2. This is used in comparator functions sorting objects based on the order of tree expressions. The function returns -1, 0, or 1.
References CONVERT_EXPR_P, data_ref_compare_tree(), DECL_UID, gcc_unreachable, i, IS_EXPR_CODE_CLASS, NULL, POLY_INT_CST_P, SSA_NAME_VERSION, STRIP_USELESS_TYPE_CONVERSION, tcc_declaration, wi::to_poly_widest(), TREE_CODE, TREE_CODE_CLASS, tree_int_cst_compare(), TREE_OPERAND, TREE_OPERAND_LENGTH, TREE_STRING_LENGTH, and TREE_STRING_POINTER.
Referenced by comp_dr_with_seg_len_pair(), data_ref_compare_tree(), dr_align_group_sort_cmp(), dr_group_sort_cmp(), operator==(), loop_distribution::pg_add_dependence_edges(), prune_runtime_alias_test_list(), and vect_analyze_data_ref_accesses().
◆ debug() [1/6]
| DEBUG_FUNCTION void debug | ( | data_reference & | ref | ) |
Unified dump function for a DATA_REFERENCE structure.
References dump_data_reference().
◆ debug() [2/6]
| DEBUG_FUNCTION void debug | ( | data_reference * | ptr | ) |
References debug.
◆ debug() [3/6]
| DEBUG_FUNCTION void debug | ( | vec< data_reference_p > & | ref | ) |
Unified dump into FILE all the data references from DATAREFS.
References dump_data_references().
◆ debug() [4/6]
| DEBUG_FUNCTION void debug | ( | vec< data_reference_p > * | ptr | ) |
References debug.
◆ debug() [5/6]
| DEBUG_FUNCTION void debug | ( | vec< ddr_p > & | ref | ) |
References dump_data_dependence_relations().
◆ debug() [6/6]
| DEBUG_FUNCTION void debug | ( | vec< ddr_p > * | ptr | ) |
References debug.
◆ debug_data_dependence_relation()
| DEBUG_FUNCTION void debug_data_dependence_relation | ( | const struct data_dependence_relation * | ddr | ) |
Debug version.
References dump_data_dependence_relation().
◆ debug_data_dependence_relations()
| DEBUG_FUNCTION void debug_data_dependence_relations | ( | vec< ddr_p > | ddrs | ) |
Dump to STDERR all the dependence relations from DDRS.
References dump_data_dependence_relations().
◆ debug_data_reference()
| DEBUG_FUNCTION void debug_data_reference | ( | struct data_reference * | dr | ) |
Print to STDERR the data_reference DR.
References dump_data_reference().
◆ debug_data_references()
| DEBUG_FUNCTION void debug_data_references | ( | vec< data_reference_p > | datarefs | ) |
Dump into STDERR all the data references from DATAREFS.
References dump_data_references().
◆ debug_ddrs()
| DEBUG_FUNCTION void debug_ddrs | ( | vec< ddr_p > | ddrs | ) |
References dump_ddrs().
◆ dir_from_dist()
|
inlinestatic |
Return the direction for a given distance. FIXME: Computing dir this way is suboptimal, since dir can catch cases that dist is unable to represent.
References dir_equal, dir_negative, and dir_positive.
Referenced by build_classic_dir_vector().
◆ dr_alignment()
| unsigned int dr_alignment | ( | innermost_loop_behavior * | drb | ) |
Return the alignment in bytes that DRB is guaranteed to have at all times.
References innermost_loop_behavior::base_alignment, innermost_loop_behavior::base_misalignment, innermost_loop_behavior::init, integer_zerop(), MIN, innermost_loop_behavior::offset, innermost_loop_behavior::offset_alignment, innermost_loop_behavior::step, innermost_loop_behavior::step_alignment, and TREE_INT_CST_LOW.
Referenced by dr_alignment(), vect_vfa_align(), vectorizable_load(), and vectorizable_store().
◆ dr_analyze_alias()
|
static |
Extracts the alias analysis information from the memory reference DR.
References DR_PTR_INFO, DR_REF, get_base_address(), INDIRECT_REF_P, SSA_NAME_PTR_INFO, TREE_CODE, and TREE_OPERAND.
Referenced by create_data_ref().
◆ dr_analyze_indices()
Determines the base object and the list of indices of memory reference DR, analyzed in LOOP and instantiated before NEST.
References indices::access_fns, analyze_scalar_evolution(), indices::base_object, bitsize_int, bitsizetype, build2(), build_fold_addr_expr, build_int_cst(), chrec_replace_initial_condition(), component_ref_field_offset(), DECL_FIELD_BIT_OFFSET, DECL_P, EXPR_LOCATION, fold_build2_loc(), fold_convert, handled_component_p(), initial_condition(), instantiate_scev(), integer_one_node, integer_zero_node, integer_zerop(), wi::mod_trunc(), MR_DEPENDENCE_BASE, MR_DEPENDENCE_CLIQUE, reference_alias_ptr_type(), SIGNED, size_binop, split_constant_offset(), ssizetype, STRIP_NOPS, STRIP_USELESS_TYPE_CONVERSION, wi::to_wide(), TREE_CODE, TREE_OPERAND, TREE_TYPE, TYPE_SIZE_UNIT, indices::unconstrained_base, vNULL, and wide_int_to_tree().
Referenced by create_data_ref(), and initialize_data_dependence_relation().
◆ dr_analyze_innermost()
| opt_result dr_analyze_innermost | ( | innermost_loop_behavior * | drb, |
| tree | ref, | ||
| class loop * | loop, | ||
| const gimple * | stmt ) |
Analyze the behavior of memory reference REF within STMT. There are two modes: - BB analysis. In this case we simply split the address into base, init and offset components, without reference to any containing loop. The resulting base and offset are general expressions and they can vary arbitrarily from one iteration of the containing loop to the next. The step is always zero. - loop analysis. In this case we analyze the reference both wrt LOOP and on the basis that the reference occurs (is "used") in LOOP; see the comment above analyze_scalar_evolution_in_loop for more information about this distinction. The base, init, offset and step fields are all invariant in LOOP. Perform BB analysis if LOOP is null, or if LOOP is the function's dummy outermost loop. In other cases perform loop analysis. Return true if the analysis succeeded and store the results in DRB if so. BB analysis can only fail for bitfield or reversed-storage accesses.
References affine_iv::base, innermost_loop_behavior::base_address, innermost_loop_behavior::base_alignment, innermost_loop_behavior::base_misalignment, build_fold_addr_expr, canonicalize_base_object_address(), dump_file, dump_flags, opt_result::failure_at(), fold_convert, poly_int< N, C >::force_shwi(), gcc_assert, get_inner_reference(), get_object_alignment_1(), get_pointer_alignment_1(), highest_pow2_factor(), innermost_loop_behavior::init, integer_zerop(), may_be_nonaddressable_p(), mem_ref_offset(), affine_iv::no_overflow, NULL_TREE, loop::num, innermost_loop_behavior::offset, innermost_loop_behavior::offset_alignment, simple_iv(), size_binop, sizetype, split_constant_offset(), ssize_int, ssizetype, affine_iv::step, innermost_loop_behavior::step, innermost_loop_behavior::step_alignment, opt_result::success(), TDF_DETAILS, TREE_CODE, TREE_INT_CST_LOW, TREE_OPERAND, and wide_int_to_tree().
Referenced by create_data_ref(), pcom_worker::find_looparound_phi(), and vect_analyze_data_refs().
◆ dr_direction_indicator()
| tree dr_direction_indicator | ( | struct data_reference * | dr | ) |
Return a value that is negative iff DR has a negative step.
References dr_step_indicator().
Referenced by create_waw_or_war_checks(), dr_known_forward_stride_p(), get_segment_min_max(), and prune_runtime_alias_test_list().
◆ dr_equal_offsets_p()
| bool dr_equal_offsets_p | ( | struct data_reference * | dra, |
| struct data_reference * | drb ) |
Check if DRA and DRB have equal offsets.
References dr_equal_offsets_p1(), and DR_OFFSET.
◆ dr_equal_offsets_p1()
Check if OFFSET1 and OFFSET2 (DR_OFFSETs of some data-refs) are identical expressions.
References BINARY_CLASS_P, dr_equal_offsets_p1(), STRIP_NOPS, TREE_CODE, TREE_OPERAND, and UNARY_CLASS_P.
Referenced by dr_equal_offsets_p(), and dr_equal_offsets_p1().
◆ dr_known_forward_stride_p()
| bool dr_known_forward_stride_p | ( | struct data_reference * | dr | ) |
Return true if DR is known to have a nonnegative (but possibly zero) step.
References boolean_type_node, dr_direction_indicator(), fold_binary, fold_convert, integer_zerop(), ssize_int, and ssizetype.
Referenced by vect_prune_runtime_alias_test_list().
◆ dr_may_alias_p()
| bool dr_may_alias_p | ( | const struct data_reference * | a, |
| const struct data_reference * | b, | ||
| class loop * | loop_nest ) |
Returns false if we can prove that data references A and B do not alias, true otherwise. If LOOP_NEST is false no cross-iteration aliases are considered.
References a, aff_comb_cannot_overlap_p(), aff_combination_add(), aff_combination_scale(), alias_sets_conflict_p(), b, build_fold_addr_expr, DR_BASE_ADDRESS, DR_BASE_OBJECT, DR_INIT, DR_IS_READ, DR_IS_WRITE, DR_OFFSET, DR_REF, DR_STEP, DR_UNCONSTRAINED_BASE, gcc_assert, get_alias_set(), get_inner_reference_aff(), handled_component_p(), integer_zerop(), MR_DEPENDENCE_BASE, MR_DEPENDENCE_CLIQUE, operand_equal_p(), loop::owned_clique, poly_int_tree_p(), ptr_derefs_may_alias_p(), refs_anti_dependent_p(), refs_may_alias_p(), refs_output_dependent_p(), wi::to_poly_widest(), TREE_CODE, TREE_OPERAND, TREE_TYPE, and TYPE_SIZE_UNIT.
Referenced by dse_classify_store(), initialize_data_dependence_relation(), and vect_analyze_early_break_dependences().
◆ dr_step_indicator()
|
static |
Common routine implementing both dr_direction_indicator and dr_zero_step_indicator. Return USEFUL_MIN if the indicator is known to be >= USEFUL_MIN and -1 if the indicator is known to be negative. Return the step as the indicator otherwise.
References cfun, CONVERT_EXPR_P, DR_STEP, fold_convert, wi::ge_p(), wi::ges_p(), get_range_query(), INTEGRAL_TYPE_P, wi::les_p(), irange::lower_bound(), wi::lt_p(), NULL_TREE, ssize_int, ssizetype, STRIP_NOPS, wi::to_wide(), wi::to_widest(), TREE_CODE, tree_int_cst_sgn(), TREE_OPERAND, TREE_TYPE, TYPE_MAX_VALUE, TYPE_MIN_VALUE, TYPE_SIGN, vrange::undefined_p(), and irange::upper_bound().
Referenced by dr_direction_indicator(), and dr_zero_step_indicator().
◆ dr_zero_step_indicator()
| tree dr_zero_step_indicator | ( | struct data_reference * | dr | ) |
Return a value that is zero iff DR has a zero step.
References dr_step_indicator().
Referenced by vect_analyze_data_ref_dependence().
◆ dump_affine_function()
| DEBUG_FUNCTION void dump_affine_function | ( | FILE * | outf, |
| affine_fn | fn ) |
Dumps the affine function described by FN to the file OUTF.
References i, print_generic_expr(), and TDF_SLIM.
Referenced by dump_conflict_function().
◆ dump_alias_pair()
|
static |
Dump information about ALIAS_PAIR, indenting each line by INDENT.
References DR_ALIAS_ARBITRARY, DR_ALIAS_MIXED_STEPS, DR_ALIAS_RAW, DR_ALIAS_SWAPPED, DR_ALIAS_UNSWAPPED, DR_ALIAS_WAR, DR_ALIAS_WAW, DR_REF, dump_dec(), dump_printf(), MSG_NOTE, and operand_equal_p().
Referenced by prune_runtime_alias_test_list().
◆ dump_conflict_function()
| DEBUG_FUNCTION void dump_conflict_function | ( | FILE * | outf, |
| conflict_function * | cf ) |
Dumps the conflict function CF to the file OUTF.
References dump_affine_function(), conflict_function::fns, i, conflict_function::n, NO_DEPENDENCE, and NOT_KNOWN.
Referenced by analyze_overlapping_iterations(), analyze_subscript_affine_affine(), and dump_subscript().
◆ dump_data_dependence_relation()
| DEBUG_FUNCTION void dump_data_dependence_relation | ( | FILE * | outf, |
| const data_dependence_relation * | ddr ) |
Dump function for a DATA_DEPENDENCE_RELATION structure.
References chrec_dont_know, chrec_known, DDR_A, DDR_ARE_DEPENDENT, DDR_B, DDR_DIR_VECT, DDR_DIST_VECT, DDR_LOOP_NEST, DDR_NB_LOOPS, DDR_NUM_DIR_VECTS, DDR_NUM_DIST_VECTS, DDR_SUBSCRIPTS, dump_data_reference(), dump_subscript(), FOR_EACH_VEC_ELT, i, NULL_TREE, loop::num, print_direction_vector(), print_generic_stmt(), print_lambda_vector(), and SUB_ACCESS_FN.
Referenced by debug_data_dependence_relation(), dump_data_dependence_relations(), and dump_ddrs().
◆ dump_data_dependence_relations()
| DEBUG_FUNCTION void dump_data_dependence_relations | ( | FILE * | file, |
| const vec< ddr_p > & | ddrs ) |
Dump into FILE all the dependence relations from DDRS.
References dump_data_dependence_relation().
Referenced by loop_distribution::break_alias_scc_partitions(), debug(), debug_data_dependence_relations(), loop_parallel_p(), tree_loop_unroll_and_jam(), and pcom_worker::tree_predictive_commoning_loop().
◆ dump_data_reference()
| void dump_data_reference | ( | FILE * | outf, |
| struct data_reference * | dr ) |
Dump function for a DATA_REFERENCE structure.
References DR_ACCESS_FN, DR_BASE_OBJECT, DR_NUM_DIMENSIONS, DR_REF, DR_STMT, gimple_bb(), i, print_generic_stmt(), and print_gimple_stmt().
Referenced by compute_affine_dependence(), debug(), debug_data_reference(), dump_data_dependence_relation(), and dump_data_references().
◆ dump_data_references()
|
static |
Dump into FILE all the data references from DATAREFS.
References dump_data_reference().
Referenced by debug(), and debug_data_references().
◆ dump_ddrs()
| DEBUG_FUNCTION void dump_ddrs | ( | FILE * | file, |
| vec< ddr_p > | ddrs ) |
Dumps the data dependence relations DDRS in FILE.
References dump_data_dependence_relation().
Referenced by debug_ddrs().
◆ dump_dist_dir_vectors()
| DEBUG_FUNCTION void dump_dist_dir_vectors | ( | FILE * | file, |
| vec< ddr_p > | ddrs ) |
Dumps the distance and direction vectors in FILE. DDRS contains the dependence relations, and VECT_SIZE is the size of the dependence vectors, or in other words the number of loops in the considered nest.
References DDR_AFFINE_P, DDR_ARE_DEPENDENT, DDR_DIR_VECTS, DDR_DIST_VECTS, DDR_NB_LOOPS, NULL_TREE, print_direction_vector(), and print_lambda_vector().
◆ dump_subscript()
| DEBUG_FUNCTION void dump_subscript | ( | FILE * | outf, |
| struct subscript * | subscript ) |
Dump function for a SUBSCRIPT structure.
References CF_NONTRIVIAL_P, dump_conflict_function(), print_generic_expr(), SUB_CONFLICTS_IN_A, SUB_CONFLICTS_IN_B, SUB_DISTANCE, and SUB_LAST_CONFLICT.
Referenced by dump_data_dependence_relation().
◆ finalize_ddr_dependent()
|
inlinestatic |
Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap description.
References DDR_ARE_DEPENDENT, DDR_SUBSCRIPTS, and free_subscripts().
Referenced by build_classic_dist_vector_1(), compute_affine_dependence(), and subscript_dependence_tester_1().
◆ find_data_references_in_bb()
| tree find_data_references_in_bb | ( | class loop * | loop, |
| basic_block | bb, | ||
| vec< data_reference_p > * | datarefs ) |
Search the data references in LOOP, and record the information into DATAREFS. Returns chrec_dont_know when failing to analyze a difficult case, returns NULL_TREE otherwise.
References chrec_dont_know, find_data_references_in_stmt(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_stmt(), and NULL_TREE.
Referenced by cond_if_else_store_replacement(), and find_data_references_in_loop().
◆ find_data_references_in_loop()
| tree find_data_references_in_loop | ( | class loop * | loop, |
| vec< data_reference_p > * | datarefs ) |
Search the data references in LOOP, and record the information into DATAREFS. Returns chrec_dont_know when failing to analyze a difficult case, returns NULL_TREE otherwise. TODO: This function should be made smarter so that it can handle address arithmetic as if they were array accesses, etc.
References chrec_dont_know, find_data_references_in_bb(), free(), get_loop_body_in_dom_order(), i, NULL_TREE, and loop::num_nodes.
Referenced by compute_data_dependences_for_loop(), and tree_if_conversion().
◆ find_data_references_in_stmt()
| opt_result find_data_references_in_stmt | ( | class loop * | nest, |
| gimple * | stmt, | ||
| vec< data_reference_p > * | datarefs ) |
Stores the data references in STMT to DATAREFS. If there is an unanalyzable reference, returns false, otherwise returns true. NEST is the outermost loop of the loop nest in which the references should be analyzed.
References create_data_ref(), opt_result::failure_at(), gcc_assert, get_references_in_stmt(), loop_containing_stmt(), loop_preheader_edge(), NULL, and opt_result::success().
Referenced by loop_distribution::create_rdg_vertices(), find_data_references_in_bb(), and vect_find_stmt_data_reference().
◆ find_loop_nest()
Return false when the LOOP is not well nested. Otherwise return true and insert in LOOP_NEST the loops of the nest. LOOP_NEST will contain the loops from the outermost to the innermost, as they will appear in the classic distance vector.
References find_loop_nest_1(), and loop::inner.
Referenced by compute_data_dependences_for_loop(), determine_loop_nest_reuse(), loop_distribution::distribute_loop(), and vect_analyze_loop().
◆ find_loop_nest_1()
Recursive helper function.
References find_loop_nest_1(), loop::inner, and loop::next.
Referenced by find_loop_nest(), and find_loop_nest_1().
◆ free_conflict_function()
|
static |
Frees memory used by the conflict function F.
References affine_fn_free(), CF_NONTRIVIAL_P, conflict_function::fns, free(), i, and conflict_function::n.
Referenced by analyze_siv_subscript_cst_affine(), free_subscripts(), and subscript_dependence_tester_1().
◆ free_data_ref()
| void free_data_ref | ( | data_reference_p | dr | ) |
Frees data reference DR.
References indices::access_fns, data_reference::alt_indices, indices::base_object, DR_ACCESS_FNS, and free().
Referenced by dse_classify_store(), free_data_refs(), tree_if_conversion(), and vect_find_stmt_data_reference().
◆ free_data_refs()
| void free_data_refs | ( | vec< data_reference_p > & | datarefs | ) |
Free the memory used by the data references from DATAREFS.
References free_data_ref().
Referenced by cond_if_else_store_replacement(), determine_loop_nest_reuse(), loop_distribution::distribute_loop(), loop_distribution::execute(), free_data_refs_with_aux(), loop_parallel_p(), tree_loop_unroll_and_jam(), pcom_worker::~pcom_worker(), and vec_info_shared::~vec_info_shared().
◆ free_dependence_relation()
| void free_dependence_relation | ( | struct data_dependence_relation * | ddr | ) |
Free the memory used by a data dependence relation DDR.
References DDR_DIR_VECTS, DDR_DIST_VECTS, DDR_SUBSCRIPTS, free(), free_subscripts(), and NULL.
Referenced by loop_distribution::distribute_loop(), free_dependence_relations(), vect_slp_analyze_load_dependences(), and vect_slp_analyze_store_dependences().
◆ free_dependence_relations()
Free the memory used by the data dependence relations from DEPENDENCE_RELATIONS.
References free_dependence_relation().
Referenced by cond_if_else_store_replacement(), determine_loop_nest_reuse(), loop_parallel_p(), tree_loop_unroll_and_jam(), pcom_worker::~pcom_worker(), and vec_info_shared::~vec_info_shared().
◆ free_subscripts()
|
static |
Frees memory used by SUBSCRIPTS.
References free(), free_conflict_function(), and data_dependence_relation::subscripts.
Referenced by finalize_ddr_dependent(), and free_dependence_relation().
◆ gcd_of_steps_may_divide_p()
|
static |
Returns false if we can prove that the greatest common divisor of the steps of CHREC does not divide CST, false otherwise.
References cd, CHREC_LEFT, CHREC_RIGHT, gcd(), TREE_CODE, tree_fits_shwi_p(), and tree_to_shwi().
Referenced by analyze_miv_subscript().
◆ get_base_for_alignment()
Return the object whose alignment would need to be changed in order to increase the alignment of ADDR. Store the maximum achievable alignment in *MAX_ALIGNMENT.
References get_base_for_alignment_1(), MAX_OFILE_ALIGNMENT, TREE_CODE, and TREE_OPERAND.
Referenced by vect_compute_data_ref_alignment().
◆ get_base_for_alignment_1()
If BASE is a pointer-typed SSA name, try to find the object that it is based on. Return this object X on success and store the alignment in bytes of BASE - &X in *ALIGNMENT_OUT.
References analyze_scalar_evolution(), CHREC_LEFT, CHREC_RIGHT, fold_indirect_ref_1(), get_inner_reference(), highest_pow2_factor(), loop_containing_stmt(), MAX_OFILE_ALIGNMENT, MIN, NULL, NULL_TREE, offset, POINTER_TYPE_P, data_reference::ref, SSA_NAME_DEF_STMT, TREE_CODE, tree_contains_chrecs(), TREE_TYPE, and UNKNOWN_LOCATION.
Referenced by get_base_for_alignment().
◆ get_references_in_stmt()
|
static |
Stores the locations of memory references in STMT to REFERENCES. Returns true if STMT clobbers memory, false otherwise.
References as_a(), build_aligned_type(), build_int_cst(), DECL_P, ECF_CONST, flags_from_decl_or_type(), fold_build2, gcc_assert, gcc_fallthrough, get_base_address(), gimple_asm_volatile_p(), gimple_assign_lhs(), gimple_assign_rhs1(), gimple_bb(), gimple_call_addr_fndecl(), gimple_call_arg(), gimple_call_builtin_p(), gimple_call_flags(), gimple_call_internal_fn(), gimple_call_internal_p(), gimple_call_lhs(), gimple_call_num_args(), gimple_vuse(), i, data_ref_loc::is_conditional_in_stmt, is_gimple_min_invariant(), data_ref_loc::is_read, basic_block_def::loop_father, NULL, NULL_TREE, data_ref_loc::ref, REFERENCE_CLASS_P, loop::simduid, SSA_NAME_VAR, TREE_CODE, tree_to_shwi(), TREE_TYPE, type(), and TYPE_ALIGN.
Referenced by find_data_references_in_stmt(), graphite_find_data_references_in_stmt(), and loop_nest_has_data_refs().
◆ get_segment_min_max()
|
static |
If ALIGN is nonzero, set up *SEQ_MIN_OUT and *SEQ_MAX_OUT so that for every address ADDR accessed by D: *SEQ_MIN_OUT <= ADDR (== ADDR & -ALIGN) <= *SEQ_MAX_OUT In this case, every element accessed by D is aligned to at least ALIGN bytes. If ALIGN is zero then instead set *SEG_MAX_OUT so that: *SEQ_MIN_OUT <= ADDR < *SEQ_MAX_OUT.
References dr_with_seg_len::access_size, boolean_type_node, dr_with_seg_len::dr, DR_BASE_ADDRESS, dr_direction_indicator(), DR_INIT, DR_OFFSET, fold_build2, fold_build3, fold_build_pointer_plus, fold_convert, rewrite_to_non_trapping_overflow(), dr_with_seg_len::seg_len, size_int, size_zero_node, sizetype, ssize_int, and ssizetype.
Referenced by create_intersect_range_checks().
◆ graphite_find_data_references_in_stmt()
| bool graphite_find_data_references_in_stmt | ( | edge | nest, |
| loop_p | loop, | ||
| gimple * | stmt, | ||
| vec< data_reference_p > * | datarefs ) |
Stores the data references in STMT to DATAREFS. If there is an unanalyzable reference, returns false, otherwise returns true. NEST is the outermost loop of the loop nest in which the references should be instantiated, LOOP is the loop in which the references should be analyzed.
References create_data_ref(), gcc_assert, get_references_in_stmt(), and NULL.
◆ initialize_data_dependence_relation() [1/2]
| struct data_dependence_relation * initialize_data_dependence_relation | ( | struct data_dependence_relation * | res, |
| vec< loop_p > | loop_nest, | ||
| bool | use_alt_indices ) |
Initialize a data dependence relation RES in LOOP_NEST. USE_ALT_INDICES is true when the main indices of A and B were not comparable so we try again with alternate indices computed on an indirect reference.
References a, access_fn_component_p(), access_fn_components_comparable_p(), indices::access_fns, b, indices::base_object, base_supports_access_fn_components_p(), build1(), build2(), build_int_cst(), chrec_dont_know, COMPLETE_TYPE_P, conflict_fn_not_known(), DDR_A, DDR_AFFINE_P, DDR_ARE_DEPENDENT, DDR_B, DDR_COULD_BE_INDEPENDENT_P, DDR_LOOP_NEST, DDR_OBJECT_A, DDR_OBJECT_B, DDR_SELF_REFERENCE, DDR_SUBSCRIPTS, dr_analyze_indices(), DR_REF, DR_STMT, gcc_assert, gcc_checking_assert, i, initialize_data_dependence_relation(), loop_containing_stmt(), loop_preheader_edge(), may_be_nonaddressable_p(), NULL_TREE, object_address_invariant_in_loop_p(), OEP_ADDRESS_OF, operand_equal_p(), ptr_type_node, ref_contains_union_access_p(), reference_alias_ptr_type(), SUB_ACCESS_FN, SUB_CONFLICTS_IN_A, SUB_CONFLICTS_IN_B, SUB_DISTANCE, SUB_LAST_CONFLICT, TREE_CODE, tree_fits_uhwi_p(), TREE_OPERAND, tree_to_uhwi(), TREE_TYPE, TYPE_SIZE, TYPE_SIZE_UNIT, types_compatible_p(), and indices::unconstrained_base.
Referenced by compute_all_dependences(), loop_distribution::get_data_dependence(), initialize_data_dependence_relation(), initialize_data_dependence_relation(), vect_slp_analyze_load_dependences(), and vect_slp_analyze_store_dependences().
◆ initialize_data_dependence_relation() [2/2]
| struct data_dependence_relation * initialize_data_dependence_relation | ( | struct data_reference * | a, |
| struct data_reference * | b, | ||
| vec< loop_p > | loop_nest ) |
Initialize a data dependence relation between data accesses A and B. NB_LOOPS is the number of loops surrounding the references: the size of the classic distance/direction vectors.
References a, b, chrec_dont_know, chrec_known, DDR_A, DDR_ARE_DEPENDENT, DDR_B, DDR_DIR_VECTS, DDR_DIST_VECTS, DDR_LOOP_NEST, DDR_SUBSCRIPTS, dr_may_alias_p(), initialize_data_dependence_relation(), data_dependence_relation::loop_nest, and NULL.
◆ initialize_matrix_A()
|
static |
Helper recursive function for initializing the matrix A. Returns the initial value of CHREC.
References build_int_cst(), CASE_CONVERT, chrec_convert(), chrec_dont_know, chrec_fold_op(), CHREC_LEFT, CHREC_RIGHT, chrec_type(), cst_and_fits_in_hwi(), gcc_assert, gcc_unreachable, HOST_WIDE_INT_MIN, initialize_matrix_A(), int_cst_value(), NULL, NULL_TREE, TREE_CODE, TREE_OPERAND, and TREE_TYPE.
Referenced by analyze_subscript_affine_affine(), and initialize_matrix_A().
◆ insert_innermost_unit_dist_vector()
|
static |
References DDR_NB_LOOPS, lambda_vector_new(), and save_dist_v().
Referenced by add_distance_for_zero_overlaps().
◆ int_divides_p()
|
inlinestatic |
◆ invariant_access_functions()
|
static |
Return true when the DDR contains only invariant access functions wrto. loop number LNUM.
References DDR_SUBSCRIPTS, evolution_function_is_invariant_p(), and SUB_ACCESS_FN.
Referenced by build_classic_dist_vector().
◆ lambda_matrix_copy()
|
static |
Copy the elements of M x N matrix MAT1 to MAT2.
References i, and lambda_vector_copy().
Referenced by lambda_matrix_right_hermite().
◆ lambda_matrix_id()
|
static |
◆ lambda_matrix_right_hermite()
|
static |
Given an M x N integer matrix A, this function determines an M x M unimodular matrix U, and an M x N echelon matrix S such that "U.A = S". This decomposition is also known as "right Hermite". Ref: Algorithm 2.1 page 33 in "Loop Transformations for Restructuring Compilers" Utpal Banerjee.
References a, b, gcc_assert, HOST_WIDE_INT_MIN, i, lambda_matrix_copy(), lambda_matrix_id(), lambda_matrix_row_add(), lambda_vector_first_nz(), and S.
Referenced by analyze_subscript_affine_affine().
◆ lambda_matrix_row_add()
|
static |
Add a multiple of row R1 of matrix MAT with N columns to row R2: R2 = R2 + CONST1 * R1.
References add_hwi(), HOST_WIDE_INT_MIN, i, and mul_hwi().
Referenced by lambda_matrix_right_hermite().
◆ lambda_matrix_row_negate()
|
static |
Negate row R1 of matrix MAT which has N columns.
References lambda_vector_negate().
Referenced by analyze_subscript_affine_affine().
◆ lambda_vector_copy()
|
static |
Copy the elements of vector VEC1 with length SIZE to VEC2.
Referenced by add_outer_distances(), build_classic_dist_vector(), and lambda_matrix_copy().
◆ lambda_vector_equal()
|
static |
◆ lambda_vector_first_nz()
|
static |
Return the index of the first nonzero element of vector VEC1 between START and N. We must have START <= N. Returns N if VEC1 is the zero vector.
Referenced by build_classic_dist_vector(), and lambda_matrix_right_hermite().
◆ lambda_vector_mult_const()
|
static |
Multiply vector VEC1 of length SIZE by a constant CONST1, and store the result in VEC2.
References i, and lambda_vector_clear().
Referenced by lambda_vector_negate().
◆ lambda_vector_negate()
|
static |
Negate vector VEC1 with length SIZE and store it in VEC2.
References lambda_vector_mult_const().
Referenced by lambda_matrix_row_negate().
◆ loop_nest_has_data_refs()
Returns true if the loop-nest has any data reference.
References free(), get_loop_body(), get_references_in_stmt(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_stmt(), i, and loop::num_nodes.
◆ max_stmt_executions_tree()
Similar to max_stmt_executions_int, but returns the bound as a tree, and only if it fits to the int type. If this is not the case, or the bound on the number of iterations of LOOP could not be derived, returns chrec_dont_know.
References chrec_dont_know, wi::fits_to_tree_p(), max_stmt_executions(), unsigned_type_node, and wide_int_to_tree().
Referenced by analyze_miv_subscript().
◆ non_affine_dependence_relation()
|
inlinestatic |
The dependence relation DDR cannot be represented by a distance vector.
References DDR_AFFINE_P, dump_file, dump_flags, and TDF_DETAILS.
Referenced by build_classic_dist_vector_1().
◆ nop_conversion_for_offset_p()
Return true if (sizetype) OP == (sizetype) (TO_TYPE) OP, given that OP has type FROM_TYPE and range RANGE. Both TO_TYPE and FROM_TYPE are integral types.
References gcc_assert, INTEGRAL_TYPE_P, range_fits_type_p(), sizetype, TYPE_OVERFLOW_TRAPS, TYPE_PRECISION, TYPE_SIGN, and TYPE_UNSIGNED.
Referenced by split_constant_offset_1().
◆ object_address_invariant_in_loop_p()
|
static |
Returns true if the address of OBJ is invariant in LOOP.
References chrec_contains_symbols_defined_in_loop(), handled_component_p(), i, INDIRECT_REF_P, loop::num, TREE_CODE, and TREE_OPERAND.
Referenced by initialize_data_dependence_relation().
◆ operator==()
|
static |
Operator == between two dr_with_seg_len objects. This equality operator is used to make sure two data refs are the same one so that we will consider to combine the aliasing checks of those two pairs of data dependent data refs.
References d1, d2, data_ref_compare_tree(), DR_BASE_ADDRESS, DR_INIT, DR_OFFSET, known_eq, and operand_equal_p().
◆ print_dir_vectors()
| DEBUG_FUNCTION void print_dir_vectors | ( | FILE * | outf, |
| vec< lambda_vector > | dir_vects, | ||
| int | length ) |
Print a vector of direction vectors.
References print_direction_vector().
◆ print_direction_vector()
| DEBUG_FUNCTION void print_direction_vector | ( | FILE * | outf, |
| lambda_vector | dirv, | ||
| int | length ) |
Print the classic direction vector DIRV to OUTF.
References dir_equal, dir_negative, dir_negative_or_equal, dir_positive, dir_positive_or_equal, dir_positive_or_negative, and dir_star.
Referenced by dump_data_dependence_relation(), dump_dist_dir_vectors(), and print_dir_vectors().
◆ print_dist_vectors()
| DEBUG_FUNCTION void print_dist_vectors | ( | FILE * | outf, |
| vec< lambda_vector > | dist_vects, | ||
| int | length ) |
Print a vector of distance vectors.
References print_lambda_vector().
◆ print_lambda_vector()
| DEBUG_FUNCTION void print_lambda_vector | ( | FILE * | outfile, |
| lambda_vector | vector, | ||
| int | n ) |
Print out a vector VEC of length N to OUTFILE.
References HOST_WIDE_INT_PRINT_DEC, and i.
Referenced by dump_data_dependence_relation(), dump_dist_dir_vectors(), print_dist_vectors(), and subscript_dependence_tester().
◆ prune_runtime_alias_test_list()
| void prune_runtime_alias_test_list | ( | vec< dr_with_seg_len_pair_t > * | alias_pairs, |
| poly_uint64 | ) |
Merge alias checks recorded in ALIAS_PAIRS and remove redundant ones. FACTOR is number of iterations that each data reference is accessed. Basically, for each pair of dependent data refs store_ptr_0 & load_ptr_0, we create an expression: ((store_ptr_0 + store_segment_length_0) <= load_ptr_0) || (load_ptr_0 + load_segment_length_0) <= store_ptr_0)) for aliasing checks. However, in some cases we can decrease the number of checks by combining two checks into one. For example, suppose we have another pair of data refs store_ptr_0 & load_ptr_1, and if the following condition is satisfied: load_ptr_0 < load_ptr_1 && load_ptr_1 - load_ptr_0 - load_segment_length_0 < store_segment_length_0 (this condition means, in each iteration of vectorized loop, the accessed memory of store_ptr_0 cannot be between the memory of load_ptr_0 and load_ptr_1.) we then can use only the following expression to finish the alising checks between store_ptr_0 & load_ptr_0 and store_ptr_0 & load_ptr_1: ((store_ptr_0 + store_segment_length_0) <= load_ptr_0) || (load_ptr_1 + load_segment_length_1 <= store_ptr_0)) Note that we only consider that load_ptr_0 and load_ptr_1 have the same basic address.
References dr_with_seg_len::access_size, alias_pairs, dr_with_seg_len::align, build_int_cst(), comp_dr_with_seg_len_pair(), data_ref_compare_tree(), dr_with_seg_len::dr, DR_ALIAS_ARBITRARY, DR_ALIAS_MIXED_STEPS, DR_ALIAS_SWAPPED, DR_ALIAS_UNSWAPPED, DR_BASE_ADDRESS, dr_direction_indicator(), DR_INIT, DR_OFFSET, DR_REF, DR_STEP, dump_alias_pair(), dump_enabled_p(), dump_printf(), dr_with_seg_len_pair_t::first, dr_with_seg_len_pair_t::flags, FOR_EACH_VEC_ELT, i, last, maybe_gt, MIN, MSG_NOTE, operand_equal_p(), poly_int_tree_p(), dr_with_seg_len_pair_t::second, dr_with_seg_len::seg_len, TREE_CODE, tree_int_cst_sgn(), and TREE_TYPE.
Referenced by compute_alias_check_pairs(), and vect_prune_runtime_alias_test_list().
◆ ref_contains_union_access_p()
Return true if reference REF contains a union access.
References handled_component_p(), TREE_CODE, TREE_OPERAND, and TREE_TYPE.
Referenced by initialize_data_dependence_relation().
◆ runtime_alias_check_p()
| opt_result runtime_alias_check_p | ( | ddr_p | ddr, |
| class loop * | loop, | ||
| bool | speed_p ) |
Return TRUE it's possible to resolve data dependence DDR by runtime alias check.
References DDR_A, DDR_B, DR_BASE_ADDRESS, DR_REF, DR_STMT, dump_enabled_p(), dump_printf(), opt_result::failure_at(), loop::inner, MSG_NOTE, NULL, opt_result::success(), TREE_TYPE, and TYPE_ADDR_SPACE.
Referenced by loop_distribution::data_dep_in_cycle_p(), and vect_mark_for_runtime_alias_test().
◆ same_access_functions()
|
inlinestatic |
Return true when the DDR contains two data references that have the same access functions.
References DDR_SUBSCRIPTS, eq_evolutions_p(), and SUB_ACCESS_FN.
Referenced by build_classic_dist_vector().
◆ save_dir_v()
|
static |
Helper function for uniquely inserting direction vectors.
References DDR_DIR_VECTS, DDR_NB_LOOPS, and lambda_vector_equal().
Referenced by build_classic_dir_vector().
◆ save_dist_v()
|
static |
Helper function for uniquely inserting distance vectors.
References DDR_DIST_VECTS, DDR_NB_LOOPS, and lambda_vector_equal().
Referenced by add_multivariate_self_dist(), add_outer_distances(), build_classic_dist_vector(), and insert_innermost_unit_dist_vector().
◆ signed_type_for_types()
Returns a signed integer type with the largest precision from TA and TB.
References signed_type_for(), and TYPE_PRECISION.
Referenced by affine_fn_op(), analyze_miv_subscript(), analyze_siv_subscript_cst_affine(), and analyze_ziv_subscript().
◆ siv_subscript_p()
|
static |
Returns true iff CHREC_A and CHREC_B are dependent on an index variable, i.e., if the SIV (Single Index Variable) test is true.
References CHREC_VARIABLE, evolution_function_is_constant_p(), evolution_function_is_univariate_p(), and TREE_CODE.
Referenced by analyze_overlapping_iterations().
◆ split_constant_offset() [1/2]
Expresses EXP as VAR + OFF, where OFF is a constant. VAR has the same type as EXP while OFF has type ssizetype.
References cache, exp(), fold_convert, split_constant_offset(), and TREE_TYPE.
◆ split_constant_offset() [2/2]
|
static |
If EXP has pointer type, try to express it as:
POINTER_PLUS <*VAR, (sizetype) *OFF>
where:
- *VAR has the same type as EXP
- *OFF is a constant of type ssizetype.
If EXP has an integral type, try to express (sizetype) EXP as:
*VAR + (sizetype) *OFF
where:
- *VAR has type sizetype
- *OFF is a constant of type ssizetype.
If EXP_RANGE is nonnull, set it to the range of EXP.
CACHE caches {*VAR, *OFF} pairs for SSA names that we've previously
visited. LIMIT counts down the number of SSA names that we are
allowed to process before giving up.
References cache, cfun, exp(), extract_ops_from_tree(), fold_convert, get_gimple_rhs_class(), get_legacy_range(), get_nonzero_bits(), get_range_query(), GIMPLE_TERNARY_RHS, INTEGRAL_TYPE_P, intersect_range_with_nonzero_bits(), r, path_range_query::range_of_expr(), irange::set(), irange::set_varying(), sizetype, split_constant_offset_1(), ssize_int, wi::to_wide(), TREE_CODE, tree_is_chrec(), TREE_TYPE, TYPE_SIGN, vrange::undefined_p(), VR_RANGE, and VR_VARYING.
Referenced by add_iv_candidate_for_use(), classify_builtin_st(), dr_analyze_indices(), dr_analyze_innermost(), record_group_use(), split_constant_offset(), and split_constant_offset_1().
◆ split_constant_offset_1()
|
static |
Helper function for split_constant_offset. If TYPE is a pointer type,
try to express OP0 CODE OP1 as:
POINTER_PLUS <*VAR, (sizetype) *OFF>
where:
- *VAR has type TYPE
- *OFF is a constant of type ssizetype.
If TYPE is an integral type, try to express (sizetype) (OP0 CODE OP1) as:
*VAR + (sizetype) *OFF
where:
- *VAR has type sizetype
- *OFF is a constant of type ssizetype.
In both cases, OP0 CODE OP1 has type TYPE.
Return true on success. A false return value indicates that we can't
do better than set *OFF to zero.
When returning true, set RESULT_RANGE to the range of OP0 CODE OP1,
if RESULT_RANGE is nonnull and if we can do better than assume VR_VARYING.
CACHE caches {*VAR, *OFF} pairs for SSA names that we've previously
visited. LIMIT counts down the number of SSA names that we are
allowed to process before giving up.
References build_fold_addr_expr, cache, CASE_CONVERT, compute_distributive_range(), CONVERT_EXPR_CODE_P, fold_build2, fold_build_pointer_plus, fold_convert, get_inner_reference(), gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_rhs_code(), has_single_use(), int_size_in_bytes(), integer_zerop(), INTEGRAL_TYPE_P, nop_conversion_for_offset_p(), NULL_TREE, op1_range(), POINTER_TYPE_P, range_cast(), size_binop, size_int, sizetype, split_constant_offset(), split_constant_offset_1(), SSA_NAME_DEF_STMT, SSA_NAME_OCCURS_IN_ABNORMAL_PHI, ssize_int, ssizetype, wi::to_wide(), TREE_CODE, TREE_OPERAND, TREE_TYPE, TYPE_OVERFLOW_TRAPS, and TYPE_PRECISION.
Referenced by split_constant_offset(), and split_constant_offset_1().
◆ subscript_dependence_tester()
|
static |
Computes the conflicting iterations in LOOP_NEST, and initialize DDR.
References build_classic_dir_vector(), build_classic_dist_vector(), compute_subscript_distance(), DDR_DIST_VECT, DDR_NB_LOOPS, DDR_NUM_DIST_VECTS, dependence_stats, dump_file, dump_flags, i, datadep_stats::num_dependence_dependent, print_lambda_vector(), subscript_dependence_tester_1(), and TDF_DETAILS.
Referenced by compute_affine_dependence().
◆ subscript_dependence_tester_1()
|
static |
Helper function. Returns true when there is a dependence between the data references. A_INDEX is the index of the first reference (0 for DDR_A, 1 for DDR_B) and B_INDEX is the index of the second reference.
References analyze_overlapping_iterations(), CF_NO_DEPENDENCE_P, CF_NOT_KNOWN_P, chrec_dont_know, chrec_known, DDR_SUBSCRIPTS, dependence_stats, finalize_ddr_dependent(), free_conflict_function(), i, NULL_TREE, datadep_stats::num_dependence_independent, datadep_stats::num_dependence_undetermined, SUB_ACCESS_FN, SUB_CONFLICTS_IN_A, SUB_CONFLICTS_IN_B, and SUB_LAST_CONFLICT.
Referenced by build_classic_dist_vector(), and subscript_dependence_tester().
◆ tree_fold_divides_p()
|
inlinestatic |
Returns true iff A divides B.
References a, b, gcc_assert, int_const_binop(), integer_zerop(), and TREE_CODE.
Referenced by analyze_siv_subscript_cst_affine().
◆ ziv_subscript_p()
|
inlinestatic |
This section contains the classic Banerjee tests.
Returns true iff CHREC_A and CHREC_B are not dependent on any index variables, i.e., if the ZIV (Zero Index Variable) test is true.
References evolution_function_is_constant_p().
Referenced by analyze_overlapping_iterations().
Variable Documentation
◆ dependence_stats
|
static |
