GCC Middle and Back End API Reference
tree-data-ref.h File Reference
#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:

Go to the source code of 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


#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_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 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_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_REVERSED_P(DDR)   (DDR)->reversed_p
#define DDR_COULD_BE_INDEPENDENT_P(DDR)   (DDR)->could_be_independent_p


typedef HOST_WIDE_INT lambda_int
typedef lambda_intlambda_vector
typedef lambda_vectorlambda_matrix
typedef struct data_referencedata_reference_p
typedef vec< treeaffine_fn
typedef struct subscriptsubscript_p
typedef struct data_dependence_relationddr_p


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


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_referencecreate_data_ref (edge, loop_p, tree, gimple *, bool, bool)
bool find_loop_nest (class loop *, vec< loop_p > *)
struct data_dependence_relationinitialize_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)


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


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


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


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






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


#define DDR_DIR_VECT ( DDR,


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






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




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


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



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







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

Referenced by create_data_ref().


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

Referenced by create_data_ref().





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






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



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


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


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



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

Referenced by dr_may_alias_p().


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


#define NO_DEPENDENCE   0
Special values of N.   

Referenced by conflict_fn_no_dependence(), and dump_conflict_function().


#define NOT_KNOWN   (MAX_DIM + 1)






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

Typedef Documentation

◆ affine_fn

◆ data_reference_p

◆ ddr_p

◆ 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

◆ lambda_matrix

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

◆ lambda_vector

◆ subscript_p

Enumeration Type Documentation

◆ data_dependence_direction


Function Documentation

◆ adjacent_dr_p()

bool adjacent_dr_p ( struct data_reference * dr)
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  )

◆ compute_all_dependences()

bool compute_all_dependences ( const vec< data_reference_p > & datarefs,
vec< ddr_p > * dependence_relations,
const vec< loop_p > & loop_nest,
bool compute_self_and_rr )
Compute in DEPENDENCE_RELATIONS the data dependence graph for all
the data references in DATAREFS, in the LOOP_NEST.  When
COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
relations.  Return true when successful, i.e. data references number
is small enough to be handled.   

References a, b, compute_affine_dependence(), DR_IS_WRITE, FOR_EACH_VEC_ELT, 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 )

◆ compute_self_dependence()

void compute_self_dependence ( struct data_dependence_relation * )

◆ create_data_ref()

struct data_reference * create_data_ref ( edge nest,
loop_p loop,
tree memref,
gimple * stmt,
bool is_read,
bool is_conditional_in_stmt )
Analyze memory reference MEMREF, which is accessed in STMT.
The reference is a read if IS_READ is true, otherwise it is a write.
IS_CONDITIONAL_IN_STMT indicates that the reference is conditional
within STMT, i.e. that it might not occur even if STMT is executed
and runs to completion.

Return the data_reference description of MEMREF.  NEST is the outermost
loop in which the reference should be instantiated, LOOP is the loop
in which the data reference should be analyzed.   

References DR_ACCESS_FN, dr_analyze_alias(), dr_analyze_indices(), dr_analyze_innermost(), DR_BASE_ADDRESS, DR_BASE_ALIGNMENT, DR_BASE_MISALIGNMENT, DR_BASE_OBJECT, DR_INIT, DR_INNERMOST, DR_IS_CONDITIONAL_IN_STMT, DR_IS_READ, DR_NUM_DIMENSIONS, DR_OFFSET, DR_OFFSET_ALIGNMENT, DR_REF, DR_STEP, DR_STEP_ALIGNMENT, DR_STMT, dump_file, dump_flags, 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 )
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()

◆ ddr_dependence_level()

unsigned ddr_dependence_level ( ddr_p ddr)
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)
Unified dump function for a DATA_REFERENCE structure.   

References dump_data_reference(), and ggc_alloc().

◆ debug() [2/6]

void debug ( data_reference * ptr)

References debug, and ggc_alloc().

◆ debug() [3/6]

void debug ( vec< data_reference_p > & ref)
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)

References debug, and ggc_alloc().

◆ debug() [5/6]

void debug ( vec< ddr_p > & ref)

◆ debug() [6/6]

void debug ( vec< ddr_p > * ptr)

References debug, and ggc_alloc().

◆ debug_data_dependence_relation()

void debug_data_dependence_relation ( const data_dependence_relation * )

◆ debug_data_dependence_relations()

void debug_data_dependence_relations ( vec< ddr_p > ddrs)
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)
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)
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)

References dump_ddrs(), and ggc_alloc().

◆ dependence_level()

unsigned dependence_level ( lambda_vector dist_vect,
int length )
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)
Return the alignment in bytes that DR is guaranteed to have at all

References dr_alignment(), and DR_INNERMOST.

◆ dr_alignment() [2/2]

unsigned int dr_alignment ( innermost_loop_behavior * drb)
Return the alignment in bytes that DRB is guaranteed to have at all

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)
Return a value that is negative iff DR has a negative step.   

References dr_step_indicator().

Referenced by create_waw_or_war_checks(), dr_known_forward_stride_p(), get_segment_min_max(), and prune_runtime_alias_test_list().

◆ dr_equal_offsets_p()

bool dr_equal_offsets_p ( struct data_reference * dra,
struct data_reference * drb )
Check if DRA and DRB have equal offsets.   

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

◆ dr_known_forward_stride_p()

bool dr_known_forward_stride_p ( struct data_reference * dr)
Return true if DR is known to have a nonnegative (but possibly zero)

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

◆ dr_zero_step_indicator()

tree dr_zero_step_indicator ( struct data_reference * dr)
Return a value that is zero iff DR has a zero step.   

References dr_step_indicator().

Referenced by vect_analyze_data_ref_dependence().

◆ dump_data_dependence_relations()

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

◆ dump_data_reference()

◆ find_data_references_in_bb()

tree find_data_references_in_bb ( class loop * loop,
basic_block bb,
vec< data_reference_p > * datarefs )
Search the data references in LOOP, and record the information into
DATAREFS.  Returns chrec_dont_know when failing to analyze a
difficult case, returns NULL_TREE otherwise.   

References chrec_dont_know, find_data_references_in_stmt(), 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 )
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 )
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()

◆ free_data_refs()

◆ free_dependence_relation()

◆ free_dependence_relations()

void free_dependence_relations ( vec< ddr_p > & dependence_relations)

◆ get_base_for_alignment()

tree get_base_for_alignment ( tree addr,
unsigned int * max_alignment )
Return the object whose alignment would need to be changed in order
to increase the alignment of ADDR.  Store the maximum achievable
alignment in *MAX_ALIGNMENT.   

References get_base_for_alignment_1(), 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 )
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 )

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

bool lambda_vector_zerop ( lambda_vector vec1,
int size )
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  )
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

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 )

◆ same_data_refs()

bool same_data_refs ( data_reference_p a,
data_reference_p b,
int offset = 0 )
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 )
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




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.

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

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

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

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

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

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


const unsigned int DR_ALIAS_SWAPPED = 1U << 4


const unsigned int DR_ALIAS_UNSWAPPED = 1U << 5