#include "graphds.h"
#include "tree-chrec.h"
#include "opt-problem.h"

Include dependency graph for tree-data-ref.h:

This graph shows which files directly or indirectly include this file:

Data Structures
struct	innermost_loop_behavior

struct	indices

struct	dr_alias

struct	data_reference

class	dr_with_seg_len

class	dr_with_seg_len_pair_t

struct	conflict_function

struct	subscript

struct	data_dependence_relation

Macros
#define	DR_STMT(DR) (DR)->stmt

#define	DR_REF(DR) (DR)->ref

#define	DR_BASE_OBJECT(DR) (DR)->indices.base_object

#define	DR_UNCONSTRAINED_BASE(DR) (DR)->indices.unconstrained_base

#define	DR_ACCESS_FNS(DR) (DR)->indices.access_fns

#define	DR_ACCESS_FN(DR, I) DR_ACCESS_FNS (DR)[I]

#define	DR_NUM_DIMENSIONS(DR) DR_ACCESS_FNS (DR).length ()

#define	DR_IS_READ(DR) (DR)->is_read

#define	DR_IS_WRITE(DR) (!DR_IS_READ (DR))

#define	DR_IS_CONDITIONAL_IN_STMT(DR) (DR)->is_conditional_in_stmt

#define	DR_BASE_ADDRESS(DR) (DR)->innermost.base_address

#define	DR_OFFSET(DR) (DR)->innermost.offset

#define	DR_INIT(DR) (DR)->innermost.init

#define	DR_STEP(DR) (DR)->innermost.step

#define	DR_PTR_INFO(DR) (DR)->alias.ptr_info

#define	DR_BASE_ALIGNMENT(DR) (DR)->innermost.base_alignment

#define	DR_BASE_MISALIGNMENT(DR) (DR)->innermost.base_misalignment

#define	DR_OFFSET_ALIGNMENT(DR) (DR)->innermost.offset_alignment

#define	DR_STEP_ALIGNMENT(DR) (DR)->innermost.step_alignment

#define	DR_INNERMOST(DR) (DR)->innermost

#define	MAX_DIM 2

#define	NO_DEPENDENCE 0

#define	NOT_KNOWN (MAX_DIM + 1)

#define	CF_NONTRIVIAL_P(CF) ((CF)->n != NO_DEPENDENCE && (CF)->n != NOT_KNOWN)

#define	CF_NOT_KNOWN_P(CF) ((CF)->n == NOT_KNOWN)

#define	CF_NO_DEPENDENCE_P(CF) ((CF)->n == NO_DEPENDENCE)

#define	SUB_ACCESS_FN(SUB, I) (SUB)->access_fn[I]

#define	SUB_CONFLICTS_IN_A(SUB) (SUB)->conflicting_iterations_in_a

#define	SUB_CONFLICTS_IN_B(SUB) (SUB)->conflicting_iterations_in_b

#define	SUB_LAST_CONFLICT(SUB) (SUB)->last_conflict

#define	SUB_DISTANCE(SUB) (SUB)->distance

#define	DDR_A(DDR) (DDR)->a

#define	DDR_B(DDR) (DDR)->b

#define	DDR_AFFINE_P(DDR) (DDR)->affine_p

#define	DDR_ARE_DEPENDENT(DDR) (DDR)->are_dependent

#define	DDR_OBJECT_A(DDR) (DDR)->object_a

#define	DDR_OBJECT_B(DDR) (DDR)->object_b

#define	DDR_SUBSCRIPTS(DDR) (DDR)->subscripts

#define	DDR_SUBSCRIPT(DDR, I) DDR_SUBSCRIPTS (DDR)[I]

#define	DDR_NUM_SUBSCRIPTS(DDR) DDR_SUBSCRIPTS (DDR).length ()

#define	DDR_LOOP_NEST(DDR) (DDR)->loop_nest

#define	DDR_NB_LOOPS(DDR) (DDR_LOOP_NEST (DDR).length ())

#define	DDR_SELF_REFERENCE(DDR) (DDR)->self_reference_p

#define	DDR_DIST_VECTS(DDR) ((DDR)->dist_vects)

#define	DDR_DIR_VECTS(DDR) ((DDR)->dir_vects)

#define	DDR_NUM_DIST_VECTS(DDR) (DDR_DIST_VECTS (DDR).length ())

#define	DDR_NUM_DIR_VECTS(DDR) (DDR_DIR_VECTS (DDR).length ())

#define	DDR_DIR_VECT(DDR, I) DDR_DIR_VECTS (DDR)[I]

#define	DDR_DIST_VECT(DDR, I) DDR_DIST_VECTS (DDR)[I]

#define	DDR_REVERSED_P(DDR) (DDR)->reversed_p

#define	DDR_COULD_BE_INDEPENDENT_P(DDR) (DDR)->could_be_independent_p

Enumerations
enum	data_dependence_direction { dir_positive , dir_negative , dir_equal , dir_positive_or_negative , dir_positive_or_equal , dir_negative_or_equal , dir_star , dir_independent }

Functions
opt_result	dr_analyze_innermost (innermost_loop_behavior , tree, class loop , const gimple *)

bool	compute_data_dependences_for_loop (class loop , bool, vec< loop_p > , vec< data_reference_p > , vec< ddr_p > )

void	debug_ddrs (vec< ddr_p >)

void	dump_data_reference (FILE , struct data_reference )

void	debug (data_reference &ref)

void	debug (data_reference *ptr)

void	debug_data_reference (struct data_reference *)

void	debug_data_references (vec< data_reference_p >)

void	debug (vec< data_reference_p > &ref)

void	debug (vec< data_reference_p > *ptr)

void	debug_data_dependence_relation (const data_dependence_relation *)

void	dump_data_dependence_relations (FILE *, const vec< ddr_p > &)

void	debug (vec< ddr_p > &ref)

void	debug (vec< ddr_p > *ptr)

void	debug_data_dependence_relations (vec< ddr_p >)

void	free_dependence_relation (struct data_dependence_relation *)

void	free_dependence_relations (vec< ddr_p > &)

void	free_data_ref (data_reference_p)

void	free_data_refs (vec< data_reference_p > &)

opt_result	find_data_references_in_stmt (class loop , gimple , vec< data_reference_p > *)

bool	graphite_find_data_references_in_stmt (edge, loop_p, gimple , vec< data_reference_p > )

tree	find_data_references_in_loop (class loop , vec< data_reference_p > )

bool	loop_nest_has_data_refs (loop_p loop)

struct data_reference *	create_data_ref (edge, loop_p, tree, gimple *, bool, bool)

bool	find_loop_nest (class loop , vec< loop_p > )

struct data_dependence_relation *	initialize_data_dependence_relation (struct data_reference , struct data_reference , vec< loop_p >)

void	compute_affine_dependence (struct data_dependence_relation *, loop_p)

void	compute_self_dependence (struct data_dependence_relation *)

bool	compute_all_dependences (const vec< data_reference_p > &, vec< ddr_p > *, const vec< loop_p > &, bool)

tree	find_data_references_in_bb (class loop , basic_block, vec< data_reference_p > )

unsigned int	dr_alignment (innermost_loop_behavior *)

tree	get_base_for_alignment (tree, unsigned int *)

unsigned int	dr_alignment (data_reference *dr)

bool	dr_may_alias_p (const struct data_reference , const struct data_reference , class loop *)

bool	dr_equal_offsets_p (struct data_reference , struct data_reference )

opt_result	runtime_alias_check_p (ddr_p, class loop *, bool)

int	data_ref_compare_tree (tree, tree)

void	prune_runtime_alias_test_list (vec< dr_with_seg_len_pair_t > *, poly_uint64)

void	create_runtime_alias_checks (class loop , const vec< dr_with_seg_len_pair_t > , tree *)

tree	dr_direction_indicator (struct data_reference *)

tree	dr_zero_step_indicator (struct data_reference *)

bool	dr_known_forward_stride_p (struct data_reference *)

bool	same_data_refs_base_objects (data_reference_p a, data_reference_p b)

bool	same_data_refs (data_reference_p a, data_reference_p b, int offset=0)

bool	known_dependences_p (vec< ddr_p > dependence_relations)

unsigned	dependence_level (lambda_vector dist_vect, int length)

unsigned	ddr_dependence_level (ddr_p ddr)

int	index_in_loop_nest (int var, const vec< loop_p > &loop_nest)

bool	adjacent_dr_p (struct data_reference *dr)

void	split_constant_offset (tree, tree , tree )

lambda_int	lambda_vector_gcd (lambda_vector vector, int size)

lambda_vector	lambda_vector_new (int size)

void	lambda_vector_clear (lambda_vector vec1, int size)

bool	lambda_vector_lexico_pos (lambda_vector v, unsigned n)

bool	lambda_vector_zerop (lambda_vector vec1, int size)

lambda_matrix	lambda_matrix_new (int m, int n, struct obstack *lambda_obstack)

Variables
const unsigned int	DR_ALIAS_RAW = 1U << 0

const unsigned int	DR_ALIAS_WAR = 1U << 1

const unsigned int	DR_ALIAS_WAW = 1U << 2

const unsigned int	DR_ALIAS_ARBITRARY = 1U << 3

const unsigned int	DR_ALIAS_SWAPPED = 1U << 4

const unsigned int	DR_ALIAS_UNSWAPPED = 1U << 5

const unsigned int	DR_ALIAS_MIXED_STEPS = 1U << 6

Macro Definition Documentation

◆ CF_NO_DEPENDENCE_P

#define CF_NO_DEPENDENCE_P ( CF ) ((CF)->n == NO_DEPENDENCE)

Referenced by analyze_miv_subscript(), analyze_siv_subscript(), and subscript_dependence_tester_1().

◆ CF_NONTRIVIAL_P

#define CF_NONTRIVIAL_P ( CF ) ((CF)->n != NO_DEPENDENCE && (CF)->n != NOT_KNOWN)

Referenced by common_affine_function(), dump_subscript(), and free_conflict_function().

◆ CF_NOT_KNOWN_P

#define CF_NOT_KNOWN_P ( CF ) ((CF)->n == NOT_KNOWN)

Referenced by analyze_miv_subscript(), analyze_siv_subscript(), and subscript_dependence_tester_1().

◆ DDR_A

◆ DDR_AFFINE_P

#define DDR_AFFINE_P ( DDR ) (DDR)->affine_p

Referenced by add_multivariate_self_dist(), add_other_self_distances(), dump_dist_dir_vectors(), initialize_data_dependence_relation(), and non_affine_dependence_relation().

◆ DDR_ARE_DEPENDENT

#define DDR_ARE_DEPENDENT ( DDR ) (DDR)->are_dependent

Referenced by add_other_self_distances(), adjust_unroll_factor(), build_classic_dist_vector(), loop_distribution::classify_builtin_ldst(), compute_affine_dependence(), compute_subscript_distance(), cond_if_else_store_replacement(), loop_distribution::data_dep_in_cycle_p(), dependence_distance_ge_vf(), determine_loop_nest_reuse(), dump_data_dependence_relation(), dump_dist_dir_vectors(), finalize_ddr_dependent(), initialize_data_dependence_relation(), initialize_data_dependence_relation(), known_dependences_p(), lambda_transform_legal_p(), loop_distribution::pg_add_dependence_edges(), pcom_worker::split_data_refs_to_components(), tree_loop_unroll_and_jam(), tree_loop_interchange::update_data_info(), tree_loop_interchange::valid_data_dependences(), vect_analyze_data_ref_dependence(), and vect_slp_analyze_data_ref_dependence().

◆ DDR_B

◆ DDR_COULD_BE_INDEPENDENT_P

#define DDR_COULD_BE_INDEPENDENT_P ( DDR ) (DDR)->could_be_independent_p

Referenced by dependence_distance_ge_vf(), determine_loop_nest_reuse(), initialize_data_dependence_relation(), and vect_analyze_data_ref_dependence().

◆ DDR_DIR_VECT

#define DDR_DIR_VECT	(		DDR,
			I ) DDR_DIR_VECTS (DDR)[I]

Referenced by dump_data_dependence_relation().

◆ DDR_DIR_VECTS

#define DDR_DIR_VECTS ( DDR ) ((DDR)->dir_vects)

Referenced by dump_dist_dir_vectors(), free_dependence_relation(), initialize_data_dependence_relation(), and save_dir_v().

◆ DDR_DIST_VECT

#define DDR_DIST_VECT	(		DDR,
			I ) DDR_DIST_VECTS (DDR)[I]

Referenced by build_classic_dist_vector(), loop_distribution::data_dep_in_cycle_p(), ddr_dependence_level(), determine_loop_nest_reuse(), dump_data_dependence_relation(), lambda_transform_legal_p(), loop_distribution::pg_add_dependence_edges(), tree_loop_interchange::update_data_info(), and tree_loop_interchange::valid_data_dependences().

◆ DDR_DIST_VECTS

#define DDR_DIST_VECTS ( DDR ) ((DDR)->dist_vects)

Referenced by adjust_unroll_factor(), build_classic_dir_vector(), loop_distribution::classify_builtin_ldst(), ddr_dependence_level(), dependence_distance_ge_vf(), dump_dist_dir_vectors(), free_dependence_relation(), initialize_data_dependence_relation(), save_dist_v(), vect_analyze_data_ref_dependence(), and vect_analyze_possibly_independent_ddr().

◆ DDR_LOOP_NEST

#define DDR_LOOP_NEST ( DDR ) (DDR)->loop_nest

Referenced by add_multivariate_self_dist(), add_other_self_distances(), build_classic_dist_vector_1(), loop_distribution::classify_builtin_ldst(), dump_data_dependence_relation(), initialize_data_dependence_relation(), initialize_data_dependence_relation(), loop_distribution::pg_add_dependence_edges(), and vect_analyze_data_ref_dependence().

◆ DDR_NB_LOOPS

#define DDR_NB_LOOPS ( DDR ) (DDR_LOOP_NEST (DDR).length ())

The size of the direction/distance vectors: the number of loops in
the loop nest.

Referenced by add_multivariate_self_dist(), add_other_self_distances(), add_outer_distances(), adjust_unroll_factor(), build_classic_dir_vector(), build_classic_dist_vector(), build_classic_dist_vector_1(), loop_distribution::data_dep_in_cycle_p(), ddr_dependence_level(), dump_data_dependence_relation(), dump_dist_dir_vectors(), insert_innermost_unit_dist_vector(), loop_distribution::pg_add_dependence_edges(), save_dir_v(), and save_dist_v().

◆ DDR_NUM_DIR_VECTS

#define DDR_NUM_DIR_VECTS ( DDR ) (DDR_DIR_VECTS (DDR).length ())

Referenced by dump_data_dependence_relation().

◆ DDR_NUM_DIST_VECTS

#define DDR_NUM_DIST_VECTS ( DDR ) (DDR_DIST_VECTS (DDR).length ())

Referenced by adjust_unroll_factor(), build_classic_dist_vector(), loop_distribution::classify_builtin_ldst(), loop_distribution::data_dep_in_cycle_p(), ddr_dependence_level(), dependence_distance_ge_vf(), determine_loop_nest_reuse(), dump_data_dependence_relation(), lambda_transform_legal_p(), loop_distribution::pg_add_dependence_edges(), pcom_worker::split_data_refs_to_components(), tree_loop_interchange::update_data_info(), tree_loop_interchange::valid_data_dependences(), and vect_analyze_data_ref_dependence().

◆ DDR_NUM_SUBSCRIPTS

#define DDR_NUM_SUBSCRIPTS ( DDR ) DDR_SUBSCRIPTS (DDR).length ()

Referenced by add_distance_for_zero_overlaps(), add_other_self_distances(), build_classic_dist_vector_1(), and compute_subscript_distance().

◆ DDR_OBJECT_A

#define DDR_OBJECT_A ( DDR ) (DDR)->object_a

Referenced by initialize_data_dependence_relation(), and vect_prune_runtime_alias_test_list().

◆ DDR_OBJECT_B

#define DDR_OBJECT_B ( DDR ) (DDR)->object_b

Referenced by initialize_data_dependence_relation(), and vect_prune_runtime_alias_test_list().

◆ DDR_REVERSED_P

#define DDR_REVERSED_P ( DDR ) (DDR)->reversed_p

Referenced by build_classic_dist_vector(), loop_distribution::classify_builtin_ldst(), loop_distribution::data_dep_in_cycle_p(), dependence_distance_ge_vf(), loop_distribution::pg_add_dependence_edges(), tree_loop_interchange::valid_data_dependences(), vect_analyze_data_ref_dependence(), and vect_analyze_possibly_independent_ddr().

◆ DDR_SELF_REFERENCE

#define DDR_SELF_REFERENCE ( DDR ) (DDR)->self_reference_p

Referenced by initialize_data_dependence_relation().

◆ DDR_SUBSCRIPT

#define DDR_SUBSCRIPT	(		DDR,
			I ) DDR_SUBSCRIPTS (DDR)[I]

Referenced by add_distance_for_zero_overlaps(), add_other_self_distances(), build_classic_dist_vector_1(), and compute_subscript_distance().

◆ DDR_SUBSCRIPTS

#define DDR_SUBSCRIPTS ( DDR ) (DDR)->subscripts

Referenced by add_other_self_distances(), dump_data_dependence_relation(), finalize_ddr_dependent(), free_dependence_relation(), initialize_data_dependence_relation(), initialize_data_dependence_relation(), invariant_access_functions(), same_access_functions(), and subscript_dependence_tester_1().

◆ DR_ACCESS_FN

#define DR_ACCESS_FN	(		DR,
			I ) DR_ACCESS_FNS (DR)[I]

Referenced by create_data_ref(), create_intersect_range_checks_index(), dump_data_reference(), and same_data_refs().

◆ DR_ACCESS_FNS

#define DR_ACCESS_FNS ( DR ) (DR)->indices.access_fns

Referenced by access_functions_are_affine_or_constant_p(), any_access_function_variant_p(), free_data_ref(), self_reuse_distance(), and tree_loop_unroll_and_jam().

◆ DR_BASE_ADDRESS

#define DR_BASE_ADDRESS ( DR ) (DR)->innermost.base_address

Referenced by loop_distribution::build_rdg_partition_for_vertex(), check_scan_store(), comp_dr_with_seg_len_pair(), create_data_ref(), create_ifn_alias_checks(), create_waw_or_war_checks(), pcom_worker::determine_offset(), dr_align_group_sort_cmp(), dr_group_sort_cmp(), dr_may_alias_p(), get_segment_min_max(), if_convertible_loop_p_1(), ifcvt_memrefs_wont_trap(), operator==(), loop_distribution::pg_add_dependence_edges(), prune_runtime_alias_test_list(), ref_at_iteration(), runtime_alias_check_p(), loop_distribution::share_memory_accesses(), update_epilogue_loop_vinfo(), pcom_worker::valid_initializer_p(), vect_analyze_data_ref_accesses(), vect_analyze_data_refs(), vect_create_data_ref_ptr(), vect_dr_aligned_if_peeled_dr_is(), vect_enhance_data_refs_alignment(), vect_find_stmt_data_reference(), vect_prune_runtime_alias_test_list(), vectorizable_load(), vectorizable_scan_store(), vectorizable_store(), and vectorizable_with_step_bound_p().

◆ DR_BASE_ALIGNMENT

#define DR_BASE_ALIGNMENT ( DR ) (DR)->innermost.base_alignment

Referenced by create_data_ref().

◆ DR_BASE_MISALIGNMENT

#define DR_BASE_MISALIGNMENT ( DR ) (DR)->innermost.base_misalignment

Referenced by create_data_ref().

◆ DR_BASE_OBJECT

#define DR_BASE_OBJECT ( DR ) (DR)->indices.base_object

Referenced by create_data_ref(), create_intersect_range_checks_index(), dr_may_alias_p(), dump_data_reference(), hash_memrefs_baserefs_and_store_DRs_read_written_info(), ifcvt_memrefs_wont_trap(), same_data_refs_base_objects(), and vect_create_data_ref_ptr().

◆ DR_INIT

#define DR_INIT ( DR ) (DR)->innermost.init

Referenced by pcom_worker::aff_combination_dr_offset(), loop_distribution::build_rdg_partition_for_vertex(), check_scan_store(), comp_dr_with_seg_len_pair(), create_data_ref(), create_ifn_alias_checks(), create_waw_or_war_checks(), pcom_worker::determine_offset(), dr_align_group_sort_cmp(), dr_group_sort_cmp(), dr_may_alias_p(), dr_misalignment(), get_segment_min_max(), if_convertible_loop_p_1(), ifcvt_memrefs_wont_trap(), operator==(), loop_distribution::pg_add_dependence_edges(), prune_runtime_alias_test_list(), ref_at_iteration(), loop_distribution::share_memory_accesses(), pcom_worker::valid_initializer_p(), vect_analyze_data_ref_accesses(), vect_analyze_data_refs(), vect_analyze_group_access_1(), vect_compile_time_alias(), vect_dissolve_slp_only_groups(), vect_dr_aligned_if_related_peeled_dr_is(), vect_find_stmt_data_reference(), vectorizable_load(), vectorizable_store(), and vectorizable_with_step_bound_p().

◆ DR_INNERMOST

#define DR_INNERMOST ( DR ) (DR)->innermost

Referenced by create_data_ref(), dr_alignment(), pcom_worker::find_looparound_phi(), hash_memrefs_baserefs_and_store_DRs_read_written_info(), if_convertible_loop_p_1(), ifcvt_memrefs_wont_trap(), vect_dr_behavior(), and vect_record_base_alignments().

◆ DR_IS_CONDITIONAL_IN_STMT

#define DR_IS_CONDITIONAL_IN_STMT ( DR ) (DR)->is_conditional_in_stmt

Referenced by create_data_ref(), vect_find_stmt_data_reference(), and vect_record_base_alignments().

◆ DR_IS_READ

#define DR_IS_READ ( DR ) (DR)->is_read

Referenced by adjust_unroll_factor(), cond_if_else_store_replacement(), create_data_ref(), loop_distribution::create_rdg_vertices(), pcom_worker::determine_roots_comp(), dr_group_sort_cmp(), dr_may_alias_p(), dr_with_seg_len_pair_t::dr_with_seg_len_pair_t(), dump_dref(), execute_load_motion(), pcom_worker::find_looparound_phi(), find_single_drs(), ifcvt_memrefs_wont_trap(), vect_optimize_slp_pass::internal_node_cost(), lambda_transform_legal_p(), name_for_ref(), loop_distribution::pg_add_dependence_edges(), pcom_worker::split_data_refs_to_components(), loop_distribution::update_type_for_merge(), vect_analyze_data_ref_access(), vect_analyze_data_ref_accesses(), vect_analyze_data_ref_dependence(), vect_analyze_data_refs(), vect_analyze_early_break_dependences(), vect_analyze_group_access_1(), vect_bb_slp_scalar_cost(), vect_build_slp_tree_1(), vect_build_slp_tree_2(), vect_check_gather_scatter(), vect_compute_single_scalar_iteration_cost(), vect_find_stmt_data_reference(), vect_gather_slp_loads(), vect_get_data_access_cost(), vect_is_extending_load(), vect_is_slp_load_node(), vect_preserves_scalar_order_p(), vect_recog_gather_scatter_pattern(), vect_schedule_slp_node(), vect_slp_analyze_data_ref_dependence(), vect_slp_analyze_load_dependences(), vect_supportable_dr_alignment(), and vect_truncate_gather_scatter_offset().

◆ DR_IS_WRITE

#define DR_IS_WRITE ( DR ) (!DR_IS_READ (DR))

Referenced by add_ref_to_chain(), compute_all_dependences(), cond_if_else_store_replacement(), pcom_worker::determine_roots_comp(), dr_may_alias_p(), dr_with_seg_len_pair_t::dr_with_seg_len_pair_t(), execute_load_motion(), pcom_worker::execute_pred_commoning_chain(), get_chain_last_write_at(), get_chain_last_write_before_load(), loop_distribution::get_data_dependence(), hash_memrefs_baserefs_and_store_DRs_read_written_info(), pcom_worker::split_data_refs_to_components(), pcom_worker::suitable_component_p(), tree_loop_unroll_and_jam(), vect_analyze_data_ref_dependence(), vect_analyze_data_refs(), vect_analyze_early_break_dependences(), vect_analyze_group_access_1(), vect_build_slp_tree_1(), vect_dissolve_slp_only_groups(), vect_enhance_data_refs_alignment(), vect_is_store_elt_extraction(), vect_preserves_scalar_order_p(), vect_schedule_slp(), and vect_slp_analyze_store_dependences().

◆ DR_NUM_DIMENSIONS

#define DR_NUM_DIMENSIONS ( DR ) DR_ACCESS_FNS (DR).length ()

Referenced by create_data_ref(), create_intersect_range_checks_index(), dump_data_reference(), same_data_refs(), and same_data_refs_base_objects().

◆ DR_OFFSET

#define DR_OFFSET ( DR ) (DR)->innermost.offset

Referenced by pcom_worker::aff_combination_dr_offset(), loop_distribution::build_rdg_partition_for_vertex(), comp_dr_with_seg_len_pair(), create_data_ref(), create_ifn_alias_checks(), create_waw_or_war_checks(), pcom_worker::determine_offset(), dr_align_group_sort_cmp(), dr_equal_offsets_p(), dr_group_sort_cmp(), dr_may_alias_p(), get_segment_min_max(), if_convertible_loop_p_1(), ifcvt_memrefs_wont_trap(), operator==(), loop_distribution::pg_add_dependence_edges(), prune_runtime_alias_test_list(), ref_at_iteration(), loop_distribution::share_memory_accesses(), pcom_worker::valid_initializer_p(), vect_analyze_data_ref_accesses(), vect_analyze_data_refs(), vect_dr_aligned_if_peeled_dr_is(), vect_enhance_data_refs_alignment(), vect_find_stmt_data_reference(), vect_prune_runtime_alias_test_list(), and vectorizable_with_step_bound_p().

◆ DR_OFFSET_ALIGNMENT

#define DR_OFFSET_ALIGNMENT ( DR ) (DR)->innermost.offset_alignment

Referenced by create_data_ref(), and vect_find_stmt_data_reference().

◆ DR_PTR_INFO

#define DR_PTR_INFO ( DR ) (DR)->alias.ptr_info

Referenced by bump_vector_ptr(), dr_analyze_alias(), vect_create_addr_base_for_vector_ref(), vect_create_data_ref_ptr(), and vect_duplicate_ssa_name_ptr_info().

◆ DR_REF

#define DR_REF ( DR ) (DR)->ref

Referenced by adjacent_dr_p(), check_scan_store(), loop_distribution::classify_builtin_ldst(), compute_access_range(), compute_access_stride(), compute_affine_dependence(), compute_alias_check_pairs(), create_data_ref(), create_runtime_alias_checks(), dependence_distance_ge_vf(), pcom_worker::determine_offset(), dr_analyze_alias(), dr_group_sort_cmp(), dr_may_alias_p(), dump_access_strides(), dump_alias_pair(), dump_data_reference(), dump_dref(), pcom_worker::find_looparound_phi(), find_single_drs(), generate_rawmemchr_builtin(), get_group_alias_ptr_type(), if_convertible_loop_p_1(), ifcvt_memrefs_wont_trap(), initialize_data_dependence_relation(), initialize_root_vars(), initialize_root_vars_lm(), initialize_root_vars_store_elim_2(), prune_runtime_alias_test_list(), ref_at_iteration(), runtime_alias_check_p(), same_data_refs(), self_reuse_distance(), should_interchange_loops(), pcom_worker::split_data_refs_to_components(), pcom_worker::suitable_component_p(), suitable_reference_p(), loop_distribution::transform_reduction_loop(), update_epilogue_loop_vinfo(), vect_analyze_data_ref_access(), vect_analyze_data_ref_accesses(), vect_analyze_data_ref_dependence(), vect_analyze_data_refs(), vect_analyze_early_break_dependences(), vect_analyze_group_access_1(), vect_build_slp_instance(), vect_check_gather_scatter(), vect_compute_data_ref_alignment(), vect_create_addr_base_for_vector_ref(), vect_create_data_ref_ptr(), vect_describe_gather_scatter_call(), vect_dissolve_slp_only_groups(), vect_find_stmt_data_reference(), vect_get_scalar_dr_size(), vect_get_vector_types_for_stmt(), vect_known_alignment_in_bytes(), vect_prune_runtime_alias_test_list(), vect_setup_realignment(), vect_slp_analyze_data_ref_dependence(), vect_slp_analyze_load_dependences(), vect_slp_analyze_store_dependences(), vect_slp_prefer_store_lanes_p(), vect_supportable_dr_alignment(), vect_truncate_gather_scatter_offset(), vect_vfa_access_size(), vector_alignment_reachable_p(), vectorizable_load(), vectorizable_scan_store(), and vectorizable_store().

◆ DR_STEP

#define DR_STEP ( DR ) (DR)->innermost.step

Referenced by adjacent_dr_p(), loop_distribution::build_rdg_partition_for_vertex(), comp_dr_with_seg_len_pair(), create_data_ref(), create_ifn_alias_checks(), create_intersect_range_checks(), create_intersect_range_checks_index(), create_waw_or_war_checks(), data_ref_segment_size(), pcom_worker::determine_offset(), dr_align_group_sort_cmp(), dr_group_sort_cmp(), dr_may_alias_p(), dr_step_indicator(), get_misalign_in_elems(), if_convertible_loop_p_1(), ifcvt_memrefs_wont_trap(), loop_distribution::pg_add_dependence_edges(), prune_runtime_alias_test_list(), ref_at_iteration(), loop_distribution::share_memory_accesses(), pcom_worker::suitable_component_p(), suitable_reference_p(), pcom_worker::valid_initializer_p(), vect_analyze_data_ref_access(), vect_analyze_data_ref_accesses(), vect_analyze_data_refs(), vect_analyze_group_access_1(), vect_compile_time_alias(), vect_create_cond_for_align_checks(), vect_create_data_ref_ptr(), vect_dr_aligned_if_peeled_dr_is(), vect_dr_misalign_for_aligned_access(), vect_enhance_data_refs_alignment(), vect_find_stmt_data_reference(), vect_gen_prolog_loop_niters(), vect_get_peeling_costs_all_drs(), vect_get_strided_load_store_ops(), vect_peeling_supportable(), vect_preserves_scalar_order_p(), vect_prune_runtime_alias_test_list(), vect_relevant_for_alignment_p(), vect_supportable_dr_alignment(), vect_truncate_gather_scatter_offset(), vect_update_init_of_dr(), vect_update_misalignment_for_peel(), vect_vfa_segment_size(), vectorizable_load(), vectorizable_store(), and vectorizable_with_step_bound_p().

◆ DR_STEP_ALIGNMENT

#define DR_STEP_ALIGNMENT ( DR ) (DR)->innermost.step_alignment

Referenced by create_data_ref(), vect_compute_data_ref_alignment(), vect_enhance_data_refs_alignment(), vect_find_stmt_data_reference(), and vectorizable_load().

◆ DR_STMT

#define DR_STMT ( DR ) (DR)->stmt

Referenced by classify_builtin_st(), loop_distribution::classify_partition(), compute_access_range(), compute_access_stride(), compute_affine_dependence(), cond_if_else_store_replacement(), create_data_ref(), loop_distribution::data_dep_in_cycle_p(), dr_align_group_sort_cmp(), dr_group_sort_cmp(), dump_data_reference(), pcom_worker::find_looparound_phi(), find_single_drs(), fuse_memset_builtins(), generate_memset_builtin(), loop_distribution::get_data_dependence(), hash_memrefs_baserefs_and_store_DRs_read_written_info(), if_convertible_loop_p_1(), ifcvt_memrefs_wont_trap(), initialize_data_dependence_relation(), latch_dominated_by_data_ref(), vec_info::lookup_dr(), loop_distribution::pg_add_dependence_edges(), runtime_alias_check_p(), pcom_worker::split_data_refs_to_components(), loop_distribution::transform_reduction_loop(), update_epilogue_loop_vinfo(), vect_analyze_data_ref_accesses(), vect_analyze_data_refs(), and vect_dissolve_slp_only_groups().

◆ DR_UNCONSTRAINED_BASE

#define DR_UNCONSTRAINED_BASE ( DR ) (DR)->indices.unconstrained_base

Referenced by dr_may_alias_p().

◆ MAX_DIM

#define MAX_DIM 2

The description of the grid of iterations that overlap.  At most
two loops are considered at the same time just now, hence at most
two functions are needed.  For each of the functions, we store
the vector of coefficients, f[0] + x * f[1] + y * f[2] + ...,
where x, y, ... are variables.

Referenced by conflict_fn().

◆ NO_DEPENDENCE

#define NO_DEPENDENCE 0

Special values of N.

Referenced by conflict_fn_no_dependence(), and dump_conflict_function().

◆ NOT_KNOWN

#define NOT_KNOWN (MAX_DIM + 1)

Referenced by conflict_fn_not_known(), and dump_conflict_function().

◆ SUB_ACCESS_FN

#define SUB_ACCESS_FN	(		SUB,
			I ) (SUB)->access_fn[I]

Referenced by add_other_self_distances(), build_classic_dist_vector_1(), dump_data_dependence_relation(), initialize_data_dependence_relation(), invariant_access_functions(), same_access_functions(), and subscript_dependence_tester_1().

◆ SUB_CONFLICTS_IN_A

#define SUB_CONFLICTS_IN_A ( SUB ) (SUB)->conflicting_iterations_in_a

Referenced by add_distance_for_zero_overlaps(), compute_subscript_distance(), dump_subscript(), initialize_data_dependence_relation(), and subscript_dependence_tester_1().

◆ SUB_CONFLICTS_IN_B

#define SUB_CONFLICTS_IN_B ( SUB ) (SUB)->conflicting_iterations_in_b

Referenced by add_distance_for_zero_overlaps(), compute_subscript_distance(), dump_subscript(), initialize_data_dependence_relation(), and subscript_dependence_tester_1().

◆ SUB_DISTANCE

#define SUB_DISTANCE ( SUB ) (SUB)->distance

Referenced by build_classic_dist_vector_1(), compute_subscript_distance(), dump_subscript(), and initialize_data_dependence_relation().

◆ SUB_LAST_CONFLICT

#define SUB_LAST_CONFLICT ( SUB ) (SUB)->last_conflict

Referenced by dump_subscript(), initialize_data_dependence_relation(), and subscript_dependence_tester_1().

Typedef Documentation

◆ affine_fn

typedef vec<tree> affine_fn

◆ data_reference_p

typedef struct data_reference* data_reference_p

◆ ddr_p

typedef struct data_dependence_relation* ddr_p

◆ lambda_int

typedef HOST_WIDE_INT lambda_int

An integer vector.  A vector formally consists of an element of a vector
space. A vector space is a set that is closed under vector addition
and scalar multiplication.  In this vector space, an element is a list of
integers.

◆ lambda_matrix

typedef lambda_vector* lambda_matrix

An integer matrix.  A matrix consists of m vectors of length n (IE
all vectors are the same length).

◆ lambda_vector

typedef lambda_int* lambda_vector

◆ subscript_p

typedef struct subscript* subscript_p

Enumeration Type Documentation

◆ data_dependence_direction

enum data_dependence_direction

Enumerator
dir_positive
dir_negative
dir_equal
dir_positive_or_negative
dir_positive_or_equal
dir_negative_or_equal
dir_star
dir_independent

Function Documentation

◆ adjacent_dr_p()

bool adjacent_dr_p ( struct data_reference * dr )

inline

Returns true when the data reference DR the form "A[i] = ..."
with a stride equal to its unit type size.

References DECL_BIT_FIELD, DR_REF, DR_STEP, fold_unary, ggc_alloc(), TREE_CODE, tree_int_cst_equal(), TREE_OPERAND, TREE_TYPE, and TYPE_SIZE_UNIT.

◆ compute_affine_dependence()

void compute_affine_dependence	(	struct data_dependence_relation *	,
		loop_p	)

extern

◆ 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 )

extern

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, ggc_alloc(), 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 )

extern

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.

Referenced by loop_parallel_p(), tree_loop_unroll_and_jam(), and pcom_worker::tree_predictive_commoning_loop().

◆ compute_self_dependence()

void compute_self_dependence ( struct data_dependence_relation * )

extern

◆ 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, ggc_alloc(), 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_runtime_alias_checks()

void create_runtime_alias_checks	(	class loop *	loop,
		const vec< dr_with_seg_len_pair_t > *	alias_pairs,
		tree *	cond_expr )

extern

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, ggc_alloc(), and MSG_NOTE.

Referenced by vect_create_cond_for_alias_checks(), and version_loop_by_alias_check().

◆ data_ref_compare_tree()

int data_ref_compare_tree	(	tree	t1,
		tree	t2 )

extern

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, ggc_alloc(), 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().

◆ ddr_dependence_level()

unsigned ddr_dependence_level ( ddr_p ddr )

inline

Return the dependence level for the DDR relation.

References DDR_DIST_VECT, DDR_DIST_VECTS, DDR_NB_LOOPS, DDR_NUM_DIST_VECTS, dependence_level(), ggc_alloc(), and MIN.

◆ debug() [1/6]

void debug ( data_reference & ref )

extern

Unified dump function for a DATA_REFERENCE structure.

References dump_data_reference(), and ggc_alloc().

◆ debug() [2/6]

void debug ( data_reference * ptr )

extern

References debug, and ggc_alloc().

◆ debug() [3/6]

void debug ( vec< data_reference_p > & ref )

extern

Unified dump into FILE all the data references from DATAREFS.

References dump_data_references(), and ggc_alloc().

◆ debug() [4/6]

void debug ( vec< data_reference_p > * ptr )

extern

References debug, and ggc_alloc().

◆ debug() [5/6]

void debug ( vec< ddr_p > & ref )

extern

References dump_data_dependence_relations(), and ggc_alloc().

◆ debug() [6/6]

void debug ( vec< ddr_p > * ptr )

extern

References debug, and ggc_alloc().

◆ debug_data_dependence_relation()

void debug_data_dependence_relation ( const data_dependence_relation * )

extern

◆ debug_data_dependence_relations()

void debug_data_dependence_relations ( vec< ddr_p > ddrs )

extern

Dump to STDERR all the dependence relations from DDRS.

References dump_data_dependence_relations(), and ggc_alloc().

◆ debug_data_reference()

void debug_data_reference ( struct data_reference * dr )

extern

Print to STDERR the data_reference DR.

References dump_data_reference(), and ggc_alloc().

◆ debug_data_references()

void debug_data_references ( vec< data_reference_p > datarefs )

extern

Dump into STDERR all the data references from DATAREFS.

References dump_data_references(), and ggc_alloc().

◆ debug_ddrs()

void debug_ddrs ( vec< ddr_p > ddrs )

extern

References dump_ddrs(), and ggc_alloc().

◆ dependence_level()

unsigned dependence_level	(	lambda_vector	dist_vect,
		int	length )

inline

Returns the dependence level for a vector DIST of size LENGTH.
LEVEL = 0 means a lexicographic dependence, i.e. a dependence due
to the sequence of statements, not carried by any loop.

References ggc_alloc(), and i.

Referenced by loop_distribution::classify_builtin_ldst(), ddr_dependence_level(), and tree_loop_interchange::valid_data_dependences().

◆ dr_alignment() [1/2]

unsigned int dr_alignment ( data_reference * dr )

inline

Return the alignment in bytes that DR is guaranteed to have at all
times.

References dr_alignment(), and DR_INNERMOST.

◆ dr_alignment() [2/2]

unsigned int dr_alignment ( innermost_loop_behavior * drb )

extern

Return the alignment in bytes that DRB is guaranteed to have at all
times.

References ggc_alloc(), integer_zerop(), MIN, and TREE_INT_CST_LOW.

Referenced by dr_alignment(), vect_vfa_align(), vectorizable_load(), and vectorizable_store().

◆ 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 build_fold_addr_expr, canonicalize_base_object_address(), dump_file, dump_flags, opt_result::failure_at(), fold_convert, gcc_assert, get_inner_reference(), get_object_alignment_1(), get_pointer_alignment_1(), ggc_alloc(), highest_pow2_factor(), integer_zerop(), may_be_nonaddressable_p(), mem_ref_offset(), NULL_TREE, loop::num, simple_iv(), size_binop, sizetype, split_constant_offset(), ssize_int, ssizetype, 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 )

extern

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 )

extern

Check if DRA and DRB have equal offsets.

References dr_equal_offsets_p1(), DR_OFFSET, and ggc_alloc().

◆ dr_known_forward_stride_p()

bool dr_known_forward_stride_p ( struct data_reference * dr )

extern

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, ggc_alloc(), 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 )

extern

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(), ggc_alloc(), 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_zero_step_indicator()

tree dr_zero_step_indicator ( struct data_reference * dr )

extern

Return a value that is zero iff DR has a zero step.

References dr_step_indicator().

Referenced by vect_analyze_data_ref_dependence().

◆ dump_data_dependence_relations()

void dump_data_dependence_relations	(	FILE *	file,
		const vec< ddr_p > &	ddrs )

extern

Dump into FILE all the dependence relations from DDRS.

References dump_data_dependence_relation(), and ggc_alloc().

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 )

extern

Dump function for a DATA_REFERENCE structure.

References DR_ACCESS_FN, DR_BASE_OBJECT, DR_NUM_DIMENSIONS, DR_REF, DR_STMT, ggc_alloc(), 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().

◆ find_data_references_in_bb()

tree find_data_references_in_bb	(	class loop *	loop,
		basic_block	bb,
		vec< data_reference_p > *	datarefs )

extern

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(), ggc_alloc(), 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 )

extern

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(), ggc_alloc(), 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()

bool find_loop_nest	(	class loop *	loop,
		vec< loop_p > *	loop_nest )

extern

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().

◆ free_data_ref()

void free_data_ref ( data_reference_p dr )

extern

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 )

extern

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 )

extern

Free the memory used by a data dependence relation DDR.

References DDR_DIR_VECTS, DDR_DIST_VECTS, DDR_SUBSCRIPTS, free(), free_subscripts(), ggc_alloc(), 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()

void free_dependence_relations ( vec< ddr_p > & dependence_relations )

extern

Free the memory used by the data dependence relations from
DEPENDENCE_RELATIONS.

References free_dependence_relation(), and ggc_alloc().

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().

◆ get_base_for_alignment()

tree get_base_for_alignment	(	tree	addr,
		unsigned int *	max_alignment )

extern

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(), ggc_alloc(), MAX_OFILE_ALIGNMENT, TREE_CODE, and TREE_OPERAND.

Referenced by vect_compute_data_ref_alignment().

◆ 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 )

extern

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(), ggc_alloc(), and NULL.

◆ index_in_loop_nest()

int index_in_loop_nest	(	int	var,
		const vec< loop_p > &	loop_nest )

inline

Return the index of the variable VAR in the LOOP_NEST array.

References gcc_unreachable, and ggc_alloc().

Referenced by add_multivariate_self_dist(), add_other_self_distances(), build_classic_dist_vector_1(), loop_distribution::pg_add_dependence_edges(), vect_analyze_data_ref_dependence(), and vect_prune_runtime_alias_test_list().

◆ initialize_data_dependence_relation()

struct data_dependence_relation * initialize_data_dependence_relation	(	struct data_reference *	a,
		struct data_reference *	b,
		vec< loop_p >	loop_nest )

extern

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(), ggc_alloc(), initialize_data_dependence_relation(), data_dependence_relation::loop_nest, and NULL.

◆ known_dependences_p()

bool known_dependences_p ( vec< ddr_p > dependence_relations )

inline

Returns true when all the dependences are computable.

References chrec_dont_know, DDR_ARE_DEPENDENT, FOR_EACH_VEC_ELT, ggc_alloc(), and i.

◆ lambda_matrix_new()

lambda_matrix lambda_matrix_new	(	int	m,
		int	n,
		struct obstack *	lambda_obstack )

inline

Allocate a matrix of M rows x  N cols.

References ggc_alloc(), and i.

Referenced by analyze_subscript_affine_affine(), and lambda_trans_matrix_new().

◆ lambda_vector_clear()

void lambda_vector_clear	(	lambda_vector	vec1,
		int	size )

inline

Clear out vector VEC1 of length SIZE.

References ggc_alloc().

Referenced by lambda_matrix_vector_mult(), and lambda_vector_mult_const().

◆ lambda_vector_gcd()

lambda_int lambda_vector_gcd	(	lambda_vector	vector,
		int	size )

inline

Compute the greatest common divisor of a VECTOR of SIZE numbers.

References gcd(), ggc_alloc(), and i.

◆ lambda_vector_lexico_pos()

bool lambda_vector_lexico_pos	(	lambda_vector	v,
		unsigned	n )

inline

Returns true when the vector V is lexicographically positive, in
other words, when the first nonzero element is positive.

References i.

Referenced by adjust_unroll_factor(), build_classic_dist_vector(), and lambda_transform_legal_p().

◆ lambda_vector_new()

lambda_vector lambda_vector_new ( int size )

inline

Allocate a new vector of given SIZE.

References ggc_alloc().

Referenced by add_multivariate_self_dist(), add_other_self_distances(), add_outer_distances(), build_classic_dir_vector(), build_classic_dist_vector(), build_classic_dist_vector_1(), insert_innermost_unit_dist_vector(), and lambda_transform_legal_p().

◆ lambda_vector_zerop()

bool lambda_vector_zerop	(	lambda_vector	vec1,
		int	size )

inline

Return true if vector VEC1 of length SIZE is the zero vector.

References ggc_alloc(), and i.

Referenced by adjust_unroll_factor(), loop_distribution::data_dep_in_cycle_p(), determine_loop_nest_reuse(), and loop_distribution::pg_add_dependence_edges().

◆ loop_nest_has_data_refs()

bool loop_nest_has_data_refs ( loop_p loop )

Returns true if the loop-nest has any data reference.

References free(), get_loop_body(), get_references_in_stmt(), ggc_alloc(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_stmt(), i, and loop::num_nodes.

◆ prune_runtime_alias_test_list()

void prune_runtime_alias_test_list	(	vec< dr_with_seg_len_pair_t > *	alias_pairs,
		poly_uint64	)

extern

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 alias_pairs, build_int_cst(), comp_dr_with_seg_len_pair(), data_ref_compare_tree(), 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(), FOR_EACH_VEC_ELT, ggc_alloc(), i, last, maybe_gt, MIN, MSG_NOTE, operand_equal_p(), poly_int_tree_p(), TREE_CODE, tree_int_cst_sgn(), and TREE_TYPE.

Referenced by compute_alias_check_pairs(), and vect_prune_runtime_alias_test_list().

◆ runtime_alias_check_p()

opt_result runtime_alias_check_p	(	ddr_p	ddr,
		class loop *	loop,
		bool	speed_p )

extern

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(), ggc_alloc(), 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_data_refs()

bool same_data_refs	(	data_reference_p	a,
		data_reference_p	b,
		int	offset = 0 )

inline

Return true when the data references A and B are accessing the same
memory object with the same access functions.  Optionally skip the
last OFFSET dimensions in the data reference.

References a, b, DR_ACCESS_FN, DR_NUM_DIMENSIONS, DR_REF, eq_evolutions_p(), i, offset, operand_equal_p(), and same_data_refs_base_objects().

Referenced by compatible_complex_nodes_p().

◆ same_data_refs_base_objects()

bool same_data_refs_base_objects	(	data_reference_p	a,
		data_reference_p	b )

inline

Return true when the base objects of data references A and B are
the same memory object.

References a, b, DR_BASE_OBJECT, DR_NUM_DIMENSIONS, and operand_equal_p().

Referenced by same_data_refs().

◆ split_constant_offset()

void split_constant_offset	(	tree	exp,
		tree *	var,
		tree *	off )

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, ggc_alloc(), split_constant_offset(), and TREE_TYPE.

Variable Documentation

◆ DR_ALIAS_ARBITRARY

const unsigned int DR_ALIAS_ARBITRARY = 1U << 3

Referenced by dr_with_seg_len_pair_t::dr_with_seg_len_pair_t(), dump_alias_pair(), and prune_runtime_alias_test_list().

◆ DR_ALIAS_MIXED_STEPS

const unsigned int DR_ALIAS_MIXED_STEPS = 1U << 6

Referenced by create_intersect_range_checks_index(), dump_alias_pair(), and prune_runtime_alias_test_list().

◆ DR_ALIAS_RAW

const unsigned int DR_ALIAS_RAW = 1U << 0

Flags that describe a potential alias between two dr_with_seg_lens.
In general, each pair of dr_with_seg_lens represents a composite of
multiple access pairs P, so testing flags like DR_IS_READ on the DRs
does not give meaningful information.

DR_ALIAS_RAW:
     There is a pair in P for which the second reference is a read
     and the first is a write.

DR_ALIAS_WAR:
     There is a pair in P for which the second reference is a write
     and the first is a read.

DR_ALIAS_WAW:
     There is a pair in P for which both references are writes.

DR_ALIAS_ARBITRARY:
     Either
     (a) it isn't possible to classify one pair in P as RAW, WAW or WAR; or
     (b) there is a pair in P that breaks the ordering assumption below.

     This flag overrides the RAW, WAR and WAW flags above.

DR_ALIAS_UNSWAPPED:
DR_ALIAS_SWAPPED:
     Temporary flags that indicate whether there is a pair P whose
     DRs have or haven't been swapped around.

DR_ALIAS_MIXED_STEPS:
     The DR_STEP for one of the data references in the pair does not
     accurately describe that reference for all members of P.  (Note
     that the flag does not say anything about whether the DR_STEPs
     of the two references in the pair are the same.)

The ordering assumption mentioned above is that for every pair
(DR_A, DR_B) in P:

(1) The original code accesses n elements for DR_A and n elements for DR_B,
    interleaved as follows:

      one access of size DR_A.access_size at DR_A.dr
      one access of size DR_B.access_size at DR_B.dr
      one access of size DR_A.access_size at DR_A.dr + STEP_A
      one access of size DR_B.access_size at DR_B.dr + STEP_B
      one access of size DR_A.access_size at DR_A.dr + STEP_A * 2
      one access of size DR_B.access_size at DR_B.dr + STEP_B * 2
      ...

(2) The new code accesses the same data in exactly two chunks:

      one group of accesses spanning |DR_A.seg_len| + DR_A.access_size
      one group of accesses spanning |DR_B.seg_len| + DR_B.access_size

A pair might break this assumption if the DR_A and DR_B accesses
in the original or the new code are mingled in some way.  For example,
if DR_A.access_size represents the effect of two individual writes
to nearby locations, the pair breaks the assumption if those writes
occur either side of the access for DR_B.

Note that DR_ALIAS_ARBITRARY describes whether the ordering assumption
fails to hold for any individual pair in P.  If the assumption *does*
hold for every pair in P, it doesn't matter whether it holds for the
composite pair or not.  In other words, P should represent the complete
set of pairs that the composite pair is testing, so only the ordering
of two accesses in the same member of P matters.

Referenced by create_ifn_alias_checks(), dr_with_seg_len_pair_t::dr_with_seg_len_pair_t(), and dump_alias_pair().

◆ DR_ALIAS_SWAPPED

const unsigned int DR_ALIAS_SWAPPED = 1U << 4

Referenced by dump_alias_pair(), and prune_runtime_alias_test_list().

◆ DR_ALIAS_UNSWAPPED

const unsigned int DR_ALIAS_UNSWAPPED = 1U << 5

Referenced by dump_alias_pair(), and prune_runtime_alias_test_list().

◆ DR_ALIAS_WAR

const unsigned int DR_ALIAS_WAR = 1U << 1

Referenced by create_ifn_alias_checks(), create_intersect_range_checks_index(), create_waw_or_war_checks(), dr_with_seg_len_pair_t::dr_with_seg_len_pair_t(), and dump_alias_pair().

◆ DR_ALIAS_WAW

const unsigned int DR_ALIAS_WAW = 1U << 2

Referenced by create_ifn_alias_checks(), create_intersect_range_checks_index(), create_waw_or_war_checks(), dr_with_seg_len_pair_t::dr_with_seg_len_pair_t(), and dump_alias_pair().

Typedefs
typedef HOST_WIDE_INT	lambda_int

typedef lambda_int *	lambda_vector

typedef lambda_vector *	lambda_matrix

typedef struct data_reference *	data_reference_p

typedef vec< tree >	affine_fn

typedef struct subscript *	subscript_p

typedef struct data_dependence_relation *	ddr_p

Data Structures

Macros

Typedefs

Enumerations

Functions

Variables

Macro Definition Documentation

◆ CF_NO_DEPENDENCE_P

◆ CF_NONTRIVIAL_P

◆ CF_NOT_KNOWN_P

◆ DDR_A

◆ DDR_AFFINE_P

◆ DDR_ARE_DEPENDENT

◆ DDR_B

◆ DDR_COULD_BE_INDEPENDENT_P

◆ DDR_DIR_VECT

◆ DDR_DIR_VECTS

◆ DDR_DIST_VECT

◆ DDR_DIST_VECTS

◆ DDR_LOOP_NEST

◆ DDR_NB_LOOPS

◆ DDR_NUM_DIR_VECTS

◆ DDR_NUM_DIST_VECTS

◆ DDR_NUM_SUBSCRIPTS

◆ DDR_OBJECT_A

◆ DDR_OBJECT_B

◆ DDR_REVERSED_P

◆ DDR_SELF_REFERENCE

◆ DDR_SUBSCRIPT

◆ DDR_SUBSCRIPTS

◆ DR_ACCESS_FN

◆ DR_ACCESS_FNS

◆ 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_IS_WRITE

◆ DR_NUM_DIMENSIONS

◆ DR_OFFSET

◆ DR_OFFSET_ALIGNMENT

◆ DR_PTR_INFO

◆ DR_REF

◆ DR_STEP

◆ DR_STEP_ALIGNMENT

◆ DR_STMT

◆ DR_UNCONSTRAINED_BASE

◆ MAX_DIM

◆ NO_DEPENDENCE

◆ NOT_KNOWN

◆ SUB_ACCESS_FN

◆ SUB_CONFLICTS_IN_A

◆ SUB_CONFLICTS_IN_B

◆ SUB_DISTANCE

◆ SUB_LAST_CONFLICT

Typedef Documentation

◆ affine_fn

◆ data_reference_p

◆ ddr_p

◆ lambda_int

◆ lambda_matrix

◆ lambda_vector

◆ subscript_p

Enumeration Type Documentation

◆ data_dependence_direction

Function Documentation

◆ adjacent_dr_p()

◆ compute_affine_dependence()

◆ compute_all_dependences()

◆ compute_data_dependences_for_loop()

◆ compute_self_dependence()

◆ create_data_ref()

◆ create_runtime_alias_checks()

◆ data_ref_compare_tree()

◆ ddr_dependence_level()

◆ debug() [1/6]

◆ debug() [2/6]