- Generated by
1.8.1.1
|
GCC Middle and Back End API Reference
|
Data Structures | |
| struct | datadep_stats |
| struct | data_ref_loc_d |
Typedefs | |
| typedef struct data_ref_loc_d | data_ref_loc |
Variables | |
| static struct datadep_stats | dependence_stats |
| typedef struct data_ref_loc_d data_ref_loc |
Describes a location of a memory reference.
|
static |
Returns true when all the access functions of A are affine or constant with respect to LOOP_NEST.
References DR_ACCESS_FNS, evolution_function_is_affine_multivariate_p(), evolution_function_is_invariant_p(), and loop::num.
Referenced by compute_affine_dependence().
|
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, insert_innermost_unit_dist_vector(), conflict_function::n, SUB_CONFLICTS_IN_A, and SUB_CONFLICTS_IN_B.
Referenced by build_classic_dist_vector().
|
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(), DDR_AFFINE_P, DDR_LOOP_NEST, DDR_NB_LOOPS, gcd(), index_in_loop_nest(), int_cst_value(), lambda_vector_new(), and save_dist_v().
Referenced by 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(), chrec_dont_know, DDR_A, DDR_AFFINE_P, DDR_ARE_DEPENDENT, DDR_LOOP_NEST, DDR_NB_LOOPS, DDR_NUM_SUBSCRIPTS, DR_ACCESS_FN, evolution_function_is_univariate_p(), index_in_loop_nest(), and lambda_vector_new().
Referenced by build_classic_dist_vector().
|
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().
|
static |
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().
|
static |
Frees affine function FN.
Referenced by compute_overlap_steps_for_affine_1_2(), compute_subscript_distance(), and free_conflict_function().
|
static |
Returns the difference of affine functions FNA and FNB.
References affine_fn_op().
Referenced by compute_subscript_distance().
|
static |
Applies operation OP on affine functions FNA and FNB, and returns the result.
References signed_type_for(), and signed_type_for_types().
Referenced by affine_fn_minus(), and affine_fn_plus().
|
static |
Returns the sum of affine functions FNA and FNB.
References affine_fn_op().
Referenced by compute_overlap_steps_for_affine_1_2().
|
static |
Returns affine function with single variable, CST + COEF * x_DIM.
Referenced by analyze_subscript_affine_affine(), and compute_overlap_steps_for_affine_univar().
|
static |
Returns the base of the affine function FN.
Referenced by affine_function_zero_p(), and compute_subscript_distance().
|
static |
Returns true if FN is a constant.
References integer_zerop().
Referenced by affine_function_zero_p(), and compute_subscript_distance().
|
static |
|
static |
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().
|
static |
Entry point (for testing only). Analyze all the data references and the dependence relations in LOOP. The data references are computed first. A relation on these nodes is represented by a complete graph. Some of the relations could be of no interest, thus the relations can be computed on demand. In the following function we compute all the relations. This is just a first implementation that is here for: - for showing how to ask for the dependence relations, - for the debugging the whole dependence graph, - for the dejagnu testcases and maintenance. It is possible to ask only for a part of the graph, avoiding to compute the whole dependence graph. The computed dependences are stored in a knowledge base (KB) such that later queries don't recompute the same information. The implementation of this KB is transparent to the optimizer, and thus the KB can be changed with a more efficient implementation, or the KB could be disabled.
References chrec_contains_undetermined(), chrec_known, compute_data_dependences_for_loop(), DDR_ARE_DEPENDENT, dump_data_dependence_relations(), dump_dist_dir_vectors(), dump_file, dump_flags, free_data_refs(), free_dependence_relations(), and gather_stats_on_scev_database().
Referenced by tree_check_data_deps().
|
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_multivariate_p(), evolution_function_is_constant_p(), gcd_of_steps_may_divide_p(), get_chrec_loop(), max_stmt_executions_tree(), 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(), and type().
Referenced by 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(), 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(), and ziv_subscript_p().
Referenced by subscript_dependence_tester_1().
|
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, and datadep_stats::num_siv_unimplemented.
Referenced by analyze_overlapping_iterations().
|
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(), compare_tree_int(), conflict_fn(), conflict_fn_no_dependence(), conflict_fn_not_known(), dependence_stats, dump_file, dump_flags, free_conflict_function(), get_chrec_loop(), HOST_WIDE_INT, initial_condition(), integer_zerop(), max_stmt_executions_int(), datadep_stats::num_siv_dependent, datadep_stats::num_siv_independent, datadep_stats::num_siv_unimplemented, signed_type_for_types(), tree_fold_divides_p(), and type().
Referenced by analyze_siv_subscript().
|
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(), chrec_dont_know, 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(), get_chrec_loop(), HOST_WIDE_INT, i1, initialize_matrix_A(), int_cst_value(), int_divides_p(), lambda_matrix_new(), lambda_matrix_right_hermite(), lambda_matrix_row_negate(), max_stmt_executions_int(), nb_vars_in_chrec(), and obstack.
Referenced by analyze_miv_subscript(), and analyze_siv_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_zerop(), datadep_stats::num_ziv, datadep_stats::num_ziv_dependent, datadep_stats::num_ziv_independent, datadep_stats::num_ziv_unimplemented, signed_type_for_types(), and type().
Referenced by analyze_overlapping_iterations().
|
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(), lambda_vector_new(), and save_dir_v().
Referenced by subscript_dependence_tester().
|
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(), constant_access_functions(), DDR_A, DDR_ARE_DEPENDENT, DDR_B, DDR_DIST_VECT, DDR_NB_LOOPS, DDR_NUM_DIST_VECTS, DDR_REVERSED_P, dump_file, dump_flags, lambda_vector_copy(), lambda_vector_first_nz(), lambda_vector_lexico_pos(), lambda_vector_new(), print_lambda_vector(), same_access_functions(), save_dist_v(), and subscript_dependence_tester_1().
Referenced by subscript_dependence_tester().
|
static |
Return false when fail to represent the data dependence as a distance vector. 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 chrec_contains_undetermined(), chrec_known, DDR_LOOP_NEST, DDR_NB_LOOPS, DDR_NUM_SUBSCRIPTS, DDR_SUBSCRIPT, DR_ACCESS_FN, finalize_ddr_dependent(), index_in_loop_nest(), int_cst_value(), lambda_vector_new(), non_affine_dependence_relation(), operand_equal_p(), and SUB_DISTANCE.
Referenced by build_classic_dist_vector().
|
read |
Build the Reduced Dependence Graph (RDG) with one vertex per statement of the loop nest, and one edge per data dependence or scalar dependence.
References new_graph().
Referenced by build_rdg().
|
read |
Build the Reduced Dependence Graph (RDG) with one vertex per statement of the loop nest, and one edge per data dependence or scalar dependence.
References build_empty_rdg(), compute_data_dependences_for_loop(), create_rdg_edges(), create_rdg_vertices(), known_dependences_p(), and stmts_from_loop().
Referenced by distribute_loop().
|
static |
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_type(), dump_file, dump_flags, evolution_function_is_constant_p(), and type().
Referenced by analyze_siv_subscript().
|
static |
Returns the address ADDR of an object in a canonical shape (without nop casts, and with type of pointer to the object).
Referenced by dr_analyze_innermost().
|
static |
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(), evolution_function_is_affine_p(), get_chrec_loop(), number_of_latch_executions(), and tree_int_cst_sgn().
Referenced by analyze_siv_subscript_cst_affine().
|
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, and conflict_function::n.
Referenced by compute_subscript_distance().
| void compute_affine_dependence | ( | struct data_dependence_relation * | ddr, |
| struct 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, ddr_consistent_p(), DDR_DIR_VECTS, DDR_DIST_VECTS, dependence_stats, DR_STMT, dump_data_dependence_relation(), dump_data_reference(), dump_file, dump_flags, finalize_ddr_dependent(), init_omega_for_ddr(), datadep_stats::num_dependence_tests, datadep_stats::num_dependence_undetermined, print_gimple_stmt(), and subscript_dependence_tester().
Referenced by classify_partition(), and compute_all_dependences().
| bool compute_all_dependences | ( | vec< data_reference_p > | datarefs, |
| vec< ddr_p > * | dependence_relations, | ||
| 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 compute_affine_dependence(), DR_IS_WRITE, and initialize_data_dependence_relation().
Referenced by compute_data_dependences_for_bb(), compute_data_dependences_for_loop(), cond_if_else_store_replacement(), determine_loop_nest_reuse(), vect_analyze_data_ref_dependences(), and vect_slp_analyze_data_ref_dependences().
| bool compute_data_dependences_for_bb | ( | basic_block | bb, |
| bool | compute_self_and_read_read_dependences, | ||
| vec< data_reference_p > * | datarefs, | ||
| vec< ddr_p > * | dependence_relations | ||
| ) |
Returns true when the data dependences for the basic block BB have been computed, false otherwise. DATAREFS is initialized to all the array elements contained in this basic block, 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(), find_data_references_in_bb(), and vNULL.
| bool compute_data_dependences_for_loop | ( | struct 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(), memset(), 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, and datadep_stats::num_ziv_unimplemented.
Referenced by analyze_all_data_dependences(), build_rdg(), if_convertible_loop_p_1(), loop_parallel_p(), and tree_predictive_commoning_loop().
|
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, compute_overlap_steps_for_affine_univar(), conflict_fn(), conflict_fn_not_known(), dump_file, dump_flags, get_chrec_loop(), HOST_WIDE_INT, int_cst_value(), integer_zerop(), and max_stmt_executions_int().
Referenced by analyze_subscript_affine_affine().
|
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, and gcd().
Referenced by analyze_subscript_affine_affine(), and compute_overlap_steps_for_affine_1_2().
|
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, SUB_CONFLICTS_IN_A, SUB_CONFLICTS_IN_B, and SUB_DISTANCE.
Referenced by build_classic_dist_vector(), and subscript_dependence_tester().
|
static |
Creates a conflict function with N dimensions. The affine functions in each dimension follow.
References conflict_function::fns, 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().
|
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().
|
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().
|
static |
Return true when the DDR contains only constant access functions.
References DDR_A, DDR_B, DDR_NUM_SUBSCRIPTS, DR_ACCESS_FN, and evolution_function_is_constant_p().
Referenced by build_classic_dist_vector().
|
read |
Analyzes memory reference MEMREF accessed in STMT. The reference is read if IS_READ is true, write otherwise. Returns 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_ALIGNED_TO, dr_analyze_alias(), dr_analyze_indices(), dr_analyze_innermost(), DR_BASE_ADDRESS, DR_BASE_OBJECT, DR_INIT, DR_IS_READ, DR_NUM_DIMENSIONS, DR_OFFSET, DR_REF, DR_STEP, DR_STMT, dump_file, dump_flags, data_reference::is_read, print_generic_expr(), print_generic_stmt(), and data_reference::stmt.
Referenced by create_rdg_vertices(), determine_loop_nest_reuse(), find_data_references_in_stmt(), graphite_find_data_references_in_stmt(), and vect_analyze_data_refs().
|
static |
Creates an edge in RDG for each distance vector from DDR. The order that we keep track of in the RDG is the order in which statements have to be executed.
References add_edge(), anti_dd, graph_edge::data, DDR_A, DDR_B, ddr_dependence_level(), DDR_REVERSED_P, DR_IS_READ, DR_IS_WRITE, DR_STMT, flow_dd, input_dd, output_dd, rdg_vertex_for_stmt(), RDGE_LEVEL, RDGE_RELATION, and RDGE_TYPE.
Referenced by create_rdg_edges().
|
static |
Creates the edges of the reduced dependence graph RDG.
References create_rdg_edge_for_ddr(), create_rdg_edges_for_scalar(), DDR_ARE_DEPENDENT, graph::n_vertices, and RDG_STMT.
Referenced by build_rdg().
|
static |
Creates dependence edges in RDG for all the uses of DEF. IDEF is the index of DEF in RDG.
References add_edge(), graph_edge::data, flow_dd, rdg_vertex_for_stmt(), RDGE_RELATION, and RDGE_TYPE.
Referenced by create_rdg_edges().
|
static |
Build the vertices of the reduced dependence graph RDG.
References create_data_ref(), vertex::data, get_references_in_stmt(), gimple_set_uid(), data_ref_loc_d::is_read, loop_containing_stmt(), data_ref_loc_d::pos, RDGV_DATAREFS, RDGV_HAS_MEM_READS, RDGV_HAS_MEM_WRITE, RDGV_STMT, and graph::vertices.
Referenced by build_rdg().
|
static |
Return true when DDR contains the same information as that stored in DIR_VECTS and in DIST_VECTS, return false otherwise.
References DDR_DIR_VECT, DDR_DIR_VECTS, DDR_DIST_VECT, DDR_DIST_VECTS, DDR_NB_LOOPS, DDR_NUM_DIR_VECTS, DDR_NUM_DIST_VECTS, dump_data_dependence_relation(), dump_file, dump_flags, lambda_vector_equal(), print_dir_vectors(), print_dist_vectors(), and print_lambda_vector().
Referenced by compute_affine_dependence().
| DEBUG_FUNCTION void debug | ( | ) |
Unified dump into FILE all the data references from DATAREFS.
Unified dump function for a DATA_REFERENCE structure.
References dump_data_references().
| DEBUG_FUNCTION void debug_data_dependence_relation | ( | ) |
Debug version.
References dump_data_dependence_relation().
| DEBUG_FUNCTION void debug_data_dependence_relations | ( | ) |
Dump to STDERR all the dependence relations from DDRS.
References dump_data_dependence_relations().
| DEBUG_FUNCTION void debug_data_reference | ( | ) |
Print to STDERR the data_reference DR.
References dump_data_reference().
| DEBUG_FUNCTION void debug_data_references | ( | ) |
Dump into STDERR all the data references from DATAREFS.
References dump_data_references().
| DEBUG_FUNCTION void debug_ddrs | ( | ) |
References dump_ddrs().
| DEBUG_FUNCTION void debug_rdg | ( | ) |
Call dump_rdg on stderr.
References dump_rdg().
| DEBUG_FUNCTION void debug_rdg_component | ( | ) |
Call dump_rdg_vertex on stderr.
References dump_rdg_component().
| DEBUG_FUNCTION void debug_rdg_vertex | ( | ) |
Call dump_rdg_vertex on stderr.
References dump_rdg_vertex().
|
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(), and omega_extract_distance_vectors().
| void dot_rdg | ( | struct graph * | ) |
Display the Reduced Dependence Graph using dotty.
| DEBUG_FUNCTION void dot_rdg | ( | ) |
References dot_rdg_1().
|
static |
References anti_dd, graph_edge::dest, flow_dd, input_dd, graph::n_vertices, output_dd, RDG_MEM_READS_STMT, RDG_MEM_WRITE_STMT, RDGE_TYPE, vertex::succ, graph_edge::succ_next, and graph::vertices.
Referenced by dot_rdg().
|
static |
Extracts the alias analysis information from the memory reference DR.
References DR_PTR_INFO, DR_REF, and get_base_address().
Referenced by create_data_ref().
|
static |
Determines the base object and the list of indices of memory reference DR, analyzed in LOOP and instantiated in loop nest NEST.
References analyze_scalar_evolution(), block_before_loop(), build_int_cst(), chrec_replace_initial_condition(), component_ref_field_offset(), DR_ACCESS_FNS, DR_BASE_OBJECT, DR_REF, DR_UNCONSTRAINED_BASE, handled_component_p(), initial_condition(), instantiate_scev(), integer_zerop(), reference_alias_ptr_type(), split_constant_offset(), and vNULL.
Referenced by create_data_ref().
| bool dr_analyze_innermost | ( | ) |
Analyzes the behavior of the memory reference DR in the innermost loop or basic block that contains it. Returns true if analysis succeed or false otherwise.
References affine_iv::base, canonicalize_base_object_address(), double_int_to_tree(), DR_ALIGNED_TO, DR_BASE_ADDRESS, DR_INIT, DR_OFFSET, DR_REF, DR_STEP, DR_STMT, dump_file, dump_flags, get_inner_reference(), highest_pow2_factor(), HOST_WIDE_INT, integer_zerop(), loop_containing_stmt(), mem_ref_offset(), affine_iv::no_overflow, loop::num, simple_iv(), split_constant_offset(), and affine_iv::step.
Referenced by create_data_ref(), and find_looparound_phi().
| 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.
Referenced by dr_group_sort_cmp(), vect_analyze_data_ref_accesses(), and vect_slp_analyze_data_ref_dependence().
|
static |
Check if OFFSET1 and OFFSET2 (DR_OFFSETs of some data-refs) are identical expressions.
Referenced by dr_equal_offsets_p().
| bool dr_may_alias_p | ( | const struct data_reference * | a, |
| const struct data_reference * | b, | ||
| bool | 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 aff_comb_cannot_overlap_p(), aff_combination_add(), aff_combination_scale(), DR_BASE_OBJECT, DR_IS_READ, DR_IS_WRITE, DR_REF, DR_UNCONSTRAINED_BASE, get_inner_reference_aff(), ptr_derefs_may_alias_p(), refs_anti_dependent_p(), refs_may_alias_p(), and refs_output_dependent_p().
Referenced by build_alias_set_optimal_p(), initialize_data_dependence_relation(), write_alias_graph_to_ascii_dimacs(), write_alias_graph_to_ascii_dot(), and write_alias_graph_to_ascii_ecc().
|
static |
Dumps the affine function described by FN to the file OUTF.
References print_generic_expr().
Referenced by dump_conflict_function().
|
static |
Dumps the conflict function CF to the file OUTF.
References dump_affine_function(), conflict_function::fns, conflict_function::n, NO_DEPENDENCE, and NOT_KNOWN.
Referenced by analyze_overlapping_iterations(), analyze_subscript_affine_affine(), and dump_subscript().
|
static |
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_INNER_LOOP, DDR_LOOP_NEST, DDR_NB_LOOPS, DDR_NUM_DIR_VECTS, DDR_NUM_DIST_VECTS, DDR_NUM_SUBSCRIPTS, DDR_SUBSCRIPT, DR_ACCESS_FN, dump_data_reference(), dump_subscript(), loop::num, print_direction_vector(), print_generic_stmt(), and print_lambda_vector().
Referenced by compute_affine_dependence(), ddr_consistent_p(), debug_data_dependence_relation(), dump_data_dependence_relations(), and dump_ddrs().
Dump into FILE all the dependence relations from DDRS.
References dump_data_dependence_relation().
Referenced by analyze_all_data_dependences(), debug_data_dependence_relations(), loop_parallel_p(), and tree_predictive_commoning_loop().
| 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, print_generic_stmt(), and print_gimple_stmt().
Referenced by compute_affine_dependence(), debug_data_reference(), dump_data_dependence_relation(), dump_data_references(), and print_pdr().
|
static |
Dump into FILE all the data references from DATAREFS.
References dump_data_reference().
Referenced by debug(), and debug_data_references().
|
static |
Dumps the data dependence relations DDRS in FILE.
References dump_data_dependence_relation().
Referenced by debug_ddrs().
|
static |
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, print_direction_vector(), and print_lambda_vector().
Referenced by analyze_all_data_dependences().
| void dump_rdg | ( | ) |
Dump the reduced dependence graph RDG to FILE.
References bitmap_bit_p(), vertex::component, dump_rdg_component(), graph::n_vertices, and graph::vertices.
Referenced by debug_rdg(), and distribute_loop().
|
static |
Dump component C of RDG to FILE. If DUMPED is non-null, set the dumped vertices to that bitmap.
References bitmap_set_bit(), vertex::component, dump_rdg_vertex(), graph::n_vertices, and graph::vertices.
Referenced by debug_rdg_component(), and dump_rdg().
|
static |
Dump vertex I in RDG to FILE.
References graph_edge::dest, vertex::pred, graph_edge::pred_next, print_gimple_stmt(), RDG_MEM_READS_STMT, RDG_MEM_WRITE_STMT, RDGV_STMT, graph_edge::src, vertex::succ, graph_edge::succ_next, and graph::vertices.
Referenced by debug_rdg_vertex(), and dump_rdg_component().
|
static |
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().
|
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().
| tree find_data_references_in_bb | ( | struct 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(), and gsi_stmt().
Referenced by compute_data_dependences_for_bb(), cond_if_else_store_replacement(), and find_data_references_in_loop().
| tree find_data_references_in_loop | ( | struct 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(), and loop::num_nodes.
Referenced by compute_data_dependences_for_loop(), and vect_analyze_data_refs().
| bool find_data_references_in_stmt | ( | struct 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(), get_references_in_stmt(), data_ref_loc_d::is_read, loop_containing_stmt(), and data_ref_loc_d::pos.
Referenced by find_data_references_in_bb(), and vect_analyze_data_refs().
| bool 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(), and vect_analyze_data_refs().
|
static |
|
static |
Frees memory used by the conflict function F.
References affine_fn_free(), CF_NONTRIVIAL_P, conflict_function::fns, free(), and conflict_function::n.
Referenced by analyze_siv_subscript_cst_affine(), free_subscripts(), and subscript_dependence_tester_1().
| void free_data_ref | ( | ) |
Frees data reference DR.
References DR_ACCESS_FNS, and free().
Referenced by free_data_refs(), and vect_analyze_data_refs().
| void free_data_refs | ( | ) |
Free the memory used by the data references from DATAREFS.
References free_data_ref().
Referenced by analyze_all_data_dependences(), cond_if_else_store_replacement(), destroy_bb_vec_info(), destroy_loop_vec_info(), determine_loop_nest_reuse(), distribute_loop(), free_gimple_bb(), free_rdg(), if_convertible_loop_p(), loop_parallel_p(), stmt_has_simple_data_refs_p(), and tree_predictive_commoning_loop().
| void free_dependence_relation | ( | ) |
Free the memory used by a data dependence relation DDR.
References DDR_DIR_VECTS, DDR_DIST_VECTS, DDR_SUBSCRIPTS, free(), and free_subscripts().
Referenced by classify_partition(), and free_dependence_relations().
| void free_dependence_relations | ( | ) |
Free the memory used by the data dependence relations from DEPENDENCE_RELATIONS.
References free_dependence_relation().
Referenced by analyze_all_data_dependences(), cond_if_else_store_replacement(), destroy_bb_vec_info(), destroy_loop_vec_info(), determine_loop_nest_reuse(), distribute_loop(), if_convertible_loop_p(), loop_parallel_p(), and tree_predictive_commoning_loop().
| void free_rdg | ( | ) |
Free the reduced dependence graph RDG.
References graph_edge::data, vertex::data, free(), free_data_refs(), free_graph(), gimple_set_uid(), graph::n_vertices, RDGV_DATAREFS, RDGV_STMT, vertex::succ, graph_edge::succ_next, and graph::vertices.
Referenced by distribute_loop().
|
static |
Frees memory used by SUBSCRIPTS.
References subscript::conflicting_iterations_in_a, subscript::conflicting_iterations_in_b, free(), and free_conflict_function().
Referenced by finalize_ddr_dependent(), and free_dependence_relation().
|
static |
Returns false if we can prove that the greatest common divisor of the steps of CHREC does not divide CST, false otherwise.
References gcd(), host_integerp(), HOST_WIDE_INT, and tree_low_cst().
Referenced by analyze_miv_subscript().
|
static |
Stores the locations of memory references in STMT to REFERENCES. Returns true if STMT clobbers memory, false otherwise.
References get_base_address(), gimple_asm_volatile_p(), gimple_assign_lhs_ptr(), gimple_assign_rhs1_ptr(), gimple_bb(), gimple_call_arg(), gimple_call_arg_ptr(), gimple_call_flags(), gimple_call_internal_fn(), gimple_call_internal_p(), gimple_call_lhs_ptr(), gimple_call_num_args(), gimple_vuse(), data_ref_loc_d::is_read, basic_block_def::loop_father, data_ref_loc_d::pos, and loop::simduid.
Referenced by create_rdg_vertices(), find_data_references_in_stmt(), and graphite_find_data_references_in_stmt().
| bool graphite_find_data_references_in_stmt | ( | loop_p | 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(), get_references_in_stmt(), data_ref_loc_d::is_read, and data_ref_loc_d::pos.
Referenced by analyze_drs_in_stmts(), stmt_has_simple_data_refs_p(), and try_generate_gimple_bb().
|
static |
Initializes an equation for an OMEGA problem using the information contained in the ACCESS_FUN. Returns true when the operation succeeded. PB is the omega constraint system. EQ is the number of the equation to be initialized. OFFSET is used for shifting the variables names in the constraints: a constrain is composed of 2 * the number of variables surrounding dependence accesses. OFFSET is set either to 0 for the first n variables, then it is set to n. ACCESS_FUN is expected to be an affine chrec.
References eqn_d::coef, DDR_INNER_LOOP, DDR_LOOP_NEST, DDR_NB_LOOPS, omega_pb_d::eqs, index_in_loop_nest(), and int_cst_value().
Referenced by omega_setup_subscript().
|
static |
Sets up the Omega dependence problem for the data dependence
relation DDR. Returns false when the constraint system cannot be
built, ie. when the test answers "don't know". Returns true
otherwise, and when independence has been proved (using one of the
trivial dependence test), set MAYBE_DEPENDENT to false, otherwise
set MAYBE_DEPENDENT to true.
Example: for setting up the dependence system corresponding to the
conflicting accesses
| loop_i
| loop_j
| A[i, i+1] = ...
| ... A[2*j, 2*(i + j)]
| endloop_j
| endloop_i
the following constraints come from the iteration domain:
0 <= i <= Ni
0 <= i + di <= Ni
0 <= j <= Nj
0 <= j + dj <= Nj
where di, dj are the distance variables. The constraints
representing the conflicting elements are:
i = 2 * (j + dj)
i + 1 = 2 * (i + di + j + dj)
For asking that the resulting distance vector (di, dj) be
lexicographically positive, we insert the constraint "di >= 0". If
"di = 0" in the solution, we fix that component to zero, and we
look at the inner loops: we set a new problem where all the outer
loop distances are zero, and fix this inner component to be
positive. When one of the components is positive, we save that
distance, and set a new problem where the distance on this loop is
zero, searching for other distances in the inner loops. Here is
the classic example that illustrates that we have to set for each
inner loop a new problem:
| loop_1
| loop_2
| A[10]
| endloop_2
| endloop_1
we have to save two distances (1, 0) and (0, 1).
Given two array references, refA and refB, we have to set the
dependence problem twice, refA vs. refB and refB vs. refA, and we
cannot do a single test, as refB might occur before refA in the
inner loops, and the contrary when considering outer loops: ex.
| loop_0
| loop_1
| loop_2
| T[{1,+,1}_2][{1,+,1}_1] // refA
| T[{2,+,1}_2][{0,+,1}_1] // refB
| endloop_2
| endloop_1
| endloop_0
refB touches the elements in T before refA, and thus for the same
loop_0 refB precedes refA: ie. the distance vector (0, 1, -1)
but for successive loop_0 iterations, we have (1, -1, 1)
The Omega solver expects the distance variables ("di" in the
previous example) to come first in the constraint system (as
variables to be protected, or "safe" variables), the constraint
system is built using the following layout:
"cst | distance vars | index vars".
References DDR_A, DDR_B, DDR_NB_LOOPS, dir_equal, init_omega_for_ddr_1(), lambda_vector_new(), omega_alloc_problem(), omega_free_problem(), same_access_functions(), save_dir_v(), and save_dist_v().
Referenced by compute_affine_dependence().
|
static |
Helper function, same as init_omega_for_ddr but specialized for data references A and B.
References chrec_known, eqn_d::coef, DDR_ARE_DEPENDENT, DDR_INNER_LOOP, DDR_LOOP_NEST, DDR_NB_LOOPS, DDR_NUM_SUBSCRIPTS, DR_ACCESS_FN, omega_pb_d::geqs, HOST_WIDE_INT, max_stmt_executions_int(), omega_add_zero_geq(), omega_black, omega_extract_distance_vectors(), and omega_setup_subscript().
Referenced by init_omega_for_ddr().
|
read |
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 data_dependence_relation::a, data_dependence_relation::b, chrec_dont_know, chrec_known, conflict_fn_not_known(), DDR_A, DDR_AFFINE_P, DDR_ARE_DEPENDENT, DDR_B, DDR_DIR_VECTS, DDR_DIST_VECTS, DDR_INNER_LOOP, DDR_LOOP_NEST, DDR_REVERSED_P, DDR_SELF_REFERENCE, DDR_SUBSCRIPTS, DR_BASE_OBJECT, dr_may_alias_p(), DR_NUM_DIMENSIONS, DR_REF, data_dependence_relation::loop_nest, object_address_invariant_in_loop_p(), operand_equal_p(), SUB_CONFLICTS_IN_A, SUB_CONFLICTS_IN_B, SUB_DISTANCE, and SUB_LAST_CONFLICT.
Referenced by classify_partition(), and compute_all_dependences().
|
static |
Helper recursive function for initializing the matrix A. Returns the initial value of CHREC.
References build_int_cst(), chrec_convert(), chrec_fold_op(), chrec_type(), and int_cst_value().
Referenced by analyze_subscript_affine_affine().
|
static |
References DDR_INNER_LOOP, DDR_NB_LOOPS, lambda_vector_new(), and save_dist_v().
Referenced by add_distance_for_zero_overlaps().
|
inlinestatic |
Returns true iff A divides B.
Referenced by analyze_subscript_affine_affine(), and omega_setup_subscript().
|
static |
Returns true when all the dependences are computable.
References chrec_dont_know, and DDR_ARE_DEPENDENT.
Referenced by build_rdg().
|
static |
Copy the elements of M x N matrix MAT1 to MAT2.
References lambda_vector_copy().
Referenced by lambda_matrix_right_hermite().
|
static |
Store the N x N identity matrix in MAT.
Referenced by 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 lambda_matrix_copy(), lambda_matrix_id(), lambda_matrix_row_add(), lambda_matrix_row_exchange(), and lambda_vector_first_nz().
Referenced by analyze_subscript_affine_affine().
|
static |
Add a multiple of row R1 of matrix MAT with N columns to row R2: R2 = R2 + CONST1 * R1.
Referenced by lambda_matrix_right_hermite().
|
static |
Swap rows R1 and R2 in matrix MAT.
Referenced by lambda_matrix_right_hermite().
|
static |
Negate row R1 of matrix MAT which has N columns.
References lambda_vector_negate().
Referenced by analyze_subscript_affine_affine().
|
static |
Copy the elements of vector VEC1 with length SIZE to VEC2.
References memcpy().
Referenced by add_outer_distances(), build_classic_dist_vector(), and lambda_matrix_copy().
|
static |
Return true if two vectors are equal.
Referenced by ddr_consistent_p(), save_dir_v(), and save_dist_v().
|
static |
Return 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().
|
static |
Multiply vector VEC1 of length SIZE by a constant CONST1, and store the result in VEC2.
References lambda_vector_clear().
Referenced by 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().
|
static |
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, double_int_fits_to_tree_p(), double_int_to_tree(), and max_stmt_executions().
Referenced by analyze_miv_subscript().
|
inlinestatic |
The dependence relation DDR cannot be represented by a distance vector.
References DDR_AFFINE_P, dump_file, and dump_flags.
Referenced by build_classic_dist_vector_1().
|
static |
Returns true if the address of OBJ is invariant in LOOP.
References chrec_contains_symbols_defined_in_loop(), handled_component_p(), and loop::num.
Referenced by initialize_data_dependence_relation().
|
static |
As explained in the comments preceding init_omega_for_ddr, we have to set up a system for each loop level, setting outer loops variation to zero, and current loop variation to positive or zero. Save each lexico positive distance vector.
References eqn_d::coef, copy(), DDR_INNER_LOOP, DDR_LOOP_NEST, DDR_NB_LOOPS, dir_from_dist(), omega_pb_d::eqs, omega_pb_d::geqs, eqn_d::key, lambda_vector_new(), omega_pb_d::num_geqs, omega_pb_d::num_subs, omega_add_zero_eq(), omega_add_zero_geq(), omega_alloc_problem(), omega_black, omega_copy_problem(), omega_false, omega_free_problem(), omega_simplify_problem(), omega_unknown, save_dir_v(), save_dist_v(), and omega_pb_d::subs.
Referenced by init_omega_for_ddr_1().
|
static |
This is called for each subscript of a tuple of data references: insert an equality for representing the conflicts.
References build_int_cst(), chrec_convert(), chrec_fold_minus(), chrec_fold_multiply(), eqn_d::coef, DDR_NB_LOOPS, omega_pb_d::eqs, init_omega_eq_with_af(), int_divides_p(), integer_zerop(), lambda_vector_gcd(), omega_add_zero_eq(), omega_black, signed_type_for_types(), and ziv_subscript_p().
Referenced by init_omega_for_ddr_1().
|
static |
Print a vector of direction vectors.
References print_direction_vector().
Referenced by ddr_consistent_p().
|
static |
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().
|
static |
Print a vector of distance vectors.
References print_lambda_vector().
Referenced by ddr_consistent_p().
|
inlinestatic |
Print out a vector VEC of length N to OUTFILE.
Referenced by build_classic_dist_vector(), ddr_consistent_p(), dump_data_dependence_relation(), dump_dist_dir_vectors(), and print_dist_vectors().
| bool rdg_defs_used_in_other_loops_p | ( | ) |
Determines whether the statement from vertex V of the RDG has a definition used outside the loop that contains this statement.
References loop_containing_stmt(), and RDG_STMT.
Referenced by rdg_build_partitions().
| int rdg_vertex_for_stmt | ( | ) |
Returns the index of STMT in RDG.
References gimple_uid(), and RDG_STMT.
Referenced by create_rdg_edge_for_ddr(), create_rdg_edges_for_scalar(), distribute_loop(), rdg_flag_loop_exits(), and rdg_flag_uses().
|
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(), init_omega_for_ddr(), and omega_extract_distance_vectors().
|
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(), init_omega_for_ddr(), insert_innermost_unit_dist_vector(), and omega_extract_distance_vectors().
|
static |
Returns a signed integer type with the largest precision from TA and TB.
References signed_type_for().
Referenced by affine_fn_op(), analyze_miv_subscript(), analyze_siv_subscript_cst_affine(), analyze_ziv_subscript(), and omega_setup_subscript().
|
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 evolution_function_is_constant_p(), and evolution_function_is_univariate_p().
Referenced by analyze_overlapping_iterations().
| void split_constant_offset | ( | ) |
Expresses EXP as VAR + OFF, where off is a constant. The type of OFF will be ssizetype.
References exp(), extract_ops_from_tree(), get_gimple_rhs_class(), GIMPLE_TERNARY_RHS, split_constant_offset_1(), and tree_is_chrec().
Referenced by dr_analyze_indices(), dr_analyze_innermost(), split_constant_offset_1(), and vect_analyze_data_refs().
|
static |
Helper function for split_constant_offset. Expresses OP0 CODE OP1 (the type of the result is TYPE) as VAR + OFF, where OFF is a nonzero constant of type ssizetype, and returns true. If we cannot do this with OFF nonzero, OFF and VAR are set to NULL_TREE instead and false is returned.
References build_int_cst(), get_inner_reference(), gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_rhs_code(), HOST_WIDE_INT, int_size_in_bytes(), and split_constant_offset().
Referenced by split_constant_offset().
|
static |
Initialize STMTS with all the statements of LOOP. When INCLUDE_PHIS is true, include also the PHI nodes. The order in which we discover statements is important as generate_loops_for_partition is using the same traversal for identifying statements.
References free(), get_loop_body_in_dom_order(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_start_phis(), gsi_stmt(), is_gimple_debug(), and loop::num_nodes.
Referenced by build_rdg().
|
static |
Computes the conflicting iterations in LOOP_NEST, and initialize DDR.
References build_classic_dir_vector(), build_classic_dist_vector(), compute_subscript_distance(), DDR_A, DDR_B, dependence_stats, datadep_stats::num_dependence_dependent, and subscript_dependence_tester_1().
Referenced by compute_affine_dependence().
|
static |
Helper function. Returns true when there is a dependence between data references DRA and DRB.
References analyze_overlapping_iterations(), CF_NO_DEPENDENCE_P, CF_NOT_KNOWN_P, chrec_dont_know, chrec_known, DDR_SUBSCRIPTS, dependence_stats, DR_ACCESS_FN, finalize_ddr_dependent(), free_conflict_function(), datadep_stats::num_dependence_independent, datadep_stats::num_dependence_undetermined, SUB_CONFLICTS_IN_A, SUB_CONFLICTS_IN_B, and SUB_LAST_CONFLICT.
Referenced by build_classic_dist_vector(), and subscript_dependence_tester().
| void tree_check_data_deps | ( | void | ) |
Computes all the data dependences and check that the results of several analyzers are the same.
References analyze_all_data_dependences().
Referenced by check_data_deps().
|
inlinestatic |
Returns true iff A divides B.
References int_const_binop(), and integer_zerop().
Referenced by analyze_siv_subscript_cst_affine().
|
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(), and omega_setup_subscript().
|
static |
1.8.1.1