tree-data-ref.h File Reference

#include "graphds.h"
#include "omega.h"
#include "tree-chrec.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	access_matrix
struct	data_reference
struct	conflict_function
struct	subscript
struct	data_dependence_relation

Macros
#define	AM_LOOP_NEST(M)   (M)->loop_nest
#define	AM_NB_INDUCTION_VARS(M)   (M)->nb_induction_vars
#define	AM_PARAMETERS(M)   (M)->parameters
#define	AM_MATRIX(M)   (M)->matrix
#define	AM_NB_PARAMETERS(M)   (AM_PARAMETERS (M)).length ()
#define	AM_CONST_COLUMN_INDEX(M)   (AM_NB_INDUCTION_VARS (M) + AM_NB_PARAMETERS (M))
#define	AM_NB_COLUMNS(M)   (AM_NB_INDUCTION_VARS (M) + AM_NB_PARAMETERS (M) + 1)
#define	AM_GET_SUBSCRIPT_ACCESS_VECTOR(M, I)   AM_MATRIX (M)[I]
#define	AM_GET_ACCESS_MATRIX_ELEMENT(M, I, J)   AM_GET_SUBSCRIPT_ACCESS_VECTOR (M, I)[J]
#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_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_ALIGNED_TO(DR)   (DR)->innermost.aligned_to
#define	DR_ACCESS_MATRIX(DR)   (DR)->access_matrix
#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_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_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_INNER_LOOP(DDR)   DDR->inner_loop
#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

Typedefs
typedef 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

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
static int	am_vector_index_for_loop ()
bool	dr_analyze_innermost (struct data_reference *, struct loop *)
bool	compute_data_dependences_for_loop (struct loop *, bool, vec< loop_p > *, vec< data_reference_p > *, vec< ddr_p > *)
bool	compute_data_dependences_for_bb (basic_block, bool, 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 (struct data_dependence_relation *)
void	dump_data_dependence_relations (FILE *, 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 >)
bool	find_data_references_in_stmt (struct loop *, gimple, vec< data_reference_p > *)
bool	graphite_find_data_references_in_stmt (loop_p, loop_p, gimple, vec< data_reference_p > *)
tree	find_data_references_in_loop (struct loop *, vec< data_reference_p > *)
struct data_reference *	create_data_ref (loop_p, loop_p, tree, gimple, bool)
bool	find_loop_nest (struct 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 (vec< data_reference_p >, vec< ddr_p > *, vec< loop_p >, bool)
tree	find_data_references_in_bb (struct loop *, basic_block, vec< data_reference_p > *)
bool	dr_may_alias_p (const struct data_reference *, const struct data_reference *, bool)
bool	dr_equal_offsets_p (struct data_reference *, struct data_reference *)
void	tree_check_data_deps (void)
static bool	same_data_refs_base_objects ()
static bool	same_data_refs ()
static bool	same_access_functions ()
static bool	ddr_is_anti_dependent ()
static bool	ddrs_have_anti_deps ()
bool	known_dependences_p ()
static unsigned	dependence_level ()
static unsigned	ddr_dependence_level ()
static int	index_in_loop_nest ()
static bool	adjacent_dr_p ()
void	split_constant_offset (tree, tree *, tree *)
static int	lambda_vector_gcd ()
static lambda_vector	lambda_vector_new ()
static void	lambda_vector_clear ()
static bool	lambda_vector_lexico_pos (lambda_vector v, unsigned n)
static bool	lambda_vector_zerop ()
static lambda_matrix	lambda_matrix_new ()

---

Macro Definition Documentation

#define AM_CONST_COLUMN_INDEX

(

M

)

(AM_NB_INDUCTION_VARS (M) + AM_NB_PARAMETERS (M))

#define AM_GET_ACCESS_MATRIX_ELEMENT	(		M,
			I,
			J
	)		AM_GET_SUBSCRIPT_ACCESS_VECTOR (M, I)[J]

#define AM_GET_SUBSCRIPT_ACCESS_VECTOR	(		M,
			I
	)		AM_MATRIX (M)[I]

#define AM_LOOP_NEST

(

M

)

(M)->loop_nest

#define AM_MATRIX

(

M

)

(M)->matrix

#define AM_NB_COLUMNS

(

M

)

(AM_NB_INDUCTION_VARS (M) + AM_NB_PARAMETERS (M) + 1)

#define AM_NB_INDUCTION_VARS

(

M

)

(M)->nb_induction_vars

#define AM_NB_PARAMETERS

(

M

)

(AM_PARAMETERS (M)).length ()

#define AM_PARAMETERS

(

M

)

(M)->parameters

#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_A

(

DDR

)

DDR->a

Referenced by omega_setup_subscript(), same_data_refs(), vect_analyze_data_ref_accesses(), vect_analyze_data_ref_dependences(), and vect_mark_for_runtime_alias_test().

#define DDR_AFFINE_P

(

DDR

)

DDR->affine_p

Referenced by save_dir_v().

#define DDR_ARE_DEPENDENT

(

DDR

)

DDR->are_dependent

Referenced by initialize_data_dependence_relation(), omega_extract_distance_vectors(), same_access_functions(), same_data_refs(), and vect_analyze_data_ref_dependences().

#define DDR_B

(

DDR

)

DDR->b

Referenced by omega_setup_subscript(), same_data_refs(), vect_analyze_data_ref_accesses(), vect_analyze_data_ref_dependences(), and vect_mark_for_runtime_alias_test().

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

#define DDR_DIR_VECTS

(

DDR

)

((DDR)->dir_vects)

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

Referenced by ddrs_have_anti_deps().

#define DDR_DIST_VECTS

(

DDR

)

((DDR)->dist_vects)

Referenced by ddrs_have_anti_deps().

#define DDR_INNER_LOOP

(

DDR

)

DDR->inner_loop

#define DDR_LOOP_NEST

(

DDR

)

DDR->loop_nest

Referenced by analyze_overlapping_iterations(), and subscript_dependence_tester_1().

#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(), analyze_overlapping_iterations(), ddrs_have_anti_deps(), debug_data_dependence_relations(), omega_setup_subscript(), and subscript_dependence_tester_1().

#define DDR_NUM_DIR_VECTS

(

DDR

)

(DDR_DIR_VECTS (DDR).length ())

#define DDR_NUM_DIST_VECTS

(

DDR

)

(DDR_DIST_VECTS (DDR).length ())

Referenced by ddrs_have_anti_deps().

#define DDR_NUM_SUBSCRIPTS

(

DDR

)

DDR_SUBSCRIPTS (DDR).length ()

Referenced by analyze_overlapping_iterations().

#define DDR_REVERSED_P

(

DDR

)

DDR->reversed_p

#define DDR_SELF_REFERENCE

(

DDR

)

DDR->self_reference_p

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

Referenced by analyze_overlapping_iterations().

#define DDR_SUBSCRIPTS

(

DDR

)

DDR->subscripts

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

Referenced by analyze_overlapping_iterations().

#define DR_ACCESS_FNS

(

DR

)

(DR)->indices.access_fns

#define DR_ACCESS_MATRIX

(

DR

)

(DR)->access_matrix

#define DR_ALIGNED_TO

(

DR

)

(DR)->innermost.aligned_to

#define DR_BASE_ADDRESS

(

DR

)

(DR)->innermost.base_address

Referenced by make_invariant_chain().

#define DR_BASE_OBJECT

(

DR

)

(DR)->indices.base_object

Referenced by conflict_fn_not_known().

#define DR_INIT

(

DR

)

(DR)->innermost.init

Referenced by make_invariant_chain(), and merge_comps().

#define DR_IS_READ

(

DR

)

(DR)->is_read

Referenced by build_rdg_partition_for_vertex(), destroy_bb_vec_info(), get_chain_root(), same_data_refs(), vect_analyze_data_ref_dependences(), vect_create_cond_for_alias_checks(), vect_find_same_alignment_drs(), and vect_update_misalignment_for_peel().

#define DR_IS_WRITE

(

DR

)

(!DR_IS_READ (DR))

Referenced by ddr_consistent_p(), same_data_refs(), and vect_slp_analyze_data_ref_dependence().

#define DR_NUM_DIMENSIONS

(

DR

)

DR_ACCESS_FNS (DR).length ()

#define DR_OFFSET

(

DR

)

(DR)->innermost.offset

Referenced by make_invariant_chain(), merge_comps(), and vect_gen_niters_for_prolog_loop().

#define DR_PTR_INFO

(

DR

)

(DR)->alias.ptr_info

#define DR_REF

(

DR

)

(DR)->ref

Referenced by component_of(), conflict_fn_no_dependence(), dependence_level(), determine_offset(), dr_group_sort_cmp(), predcom_tmp_var(), vect_analyze_data_ref_accesses(), vect_find_same_alignment_drs(), vect_mark_for_runtime_alias_test(), vect_permute_load_chain(), vect_permute_store_chain(), vect_slp_analyze_data_ref_dependence(), and vect_update_misalignment_for_peel().

#define DR_STEP

(

DR

)

(DR)->innermost.step

Referenced by component_of(), dependence_level(), make_invariant_chain(), vect_compute_data_ref_alignment(), vect_create_cond_for_alias_checks(), vect_do_peeling_for_loop_bound(), vect_find_same_alignment_drs(), vect_gen_niters_for_prolog_loop(), vect_get_new_vect_var(), and vect_permute_load_chain().

#define DR_STMT

(

DR

)

(DR)->stmt

Referenced by debug_data_reference(), vect_analyze_data_ref_dependences(), vect_do_peeling_for_loop_bound(), vect_find_same_alignment_drs(), vect_peeling_hash_choose_best_peeling(), vect_peeling_hash_insert(), vect_slp_analyze_data_ref_dependence(), and vect_update_misalignment_for_peel().

#define DR_UNCONSTRAINED_BASE

(

DR

)

(DR)->indices.unconstrained_base

Referenced by object_address_invariant_in_loop_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 finalize_ddr_dependent().

#define NO_DEPENDENCE   0

Special values of N.

Referenced by affine_fn_free().

#define NOT_KNOWN   (MAX_DIM + 1)

Referenced by affine_fn_minus().

#define SUB_CONFLICTS_IN_A

(

SUB

)

SUB->conflicting_iterations_in_a

#define SUB_CONFLICTS_IN_B

(

SUB

)

SUB->conflicting_iterations_in_b

#define SUB_DISTANCE

(

SUB

)

SUB->distance

Referenced by analyze_overlapping_iterations().

#define SUB_LAST_CONFLICT

(

SUB

)

SUB->last_conflict

---

Typedef Documentation

typedef vec<tree> affine_fn

typedef struct data_reference* data_reference_p

typedef struct data_dependence_relation* ddr_p

typedef lambda_vector* lambda_matrix

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

typedef int* lambda_vector

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.

typedef struct subscript* subscript_p

---

Enumeration Type Documentation

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

static bool adjacent_dr_p ( )

inlinestatic

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

If this is a bitfield store bail out.

static int am_vector_index_for_loop ( )

inlinestatic

Return the column in the access matrix of LOOP_NUM.

References data_reference::aux, data_reference::ref, and data_reference::stmt.

void compute_affine_dependence	(	struct data_dependence_relation *	,
		loop_p
	)

bool compute_all_dependences	(	vec< data_reference_p >	datarefs,
		vec< ddr_p > *	dependence_relations,
		vec< loop_p >	loop_nest,
		bool	compute_self_and_rr
	)

Compute in DEPENDENCE_RELATIONS the data dependence graph for all the data references in DATAREFS, in the LOOP_NEST. When COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self relations. Return true when successful, i.e. data references number is small enough to be handled.

Insert a single relation into dependence_relations: chrec_dont_know.

bool compute_data_dependences_for_bb	(	basic_block	bb,
		bool	compute_self_and_read_read_dependences,
		vec< data_reference_p > *	datarefs,
		vec< ddr_p > *	dependence_relations
	)

Returns true when the data dependences for the basic block BB have been computed, false otherwise. DATAREFS is initialized to all the array elements contained in this basic block, DEPENDENCE_RELATIONS contains the relations between the data references. Compute read-read and self relations if COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE.

bool compute_data_dependences_for_loop	(	struct loop *	loop,
		bool	compute_self_and_read_read_dependences,
		vec< loop_p > *	loop_nest,
		vec< data_reference_p > *	datarefs,
		vec< ddr_p > *	dependence_relations
	)

Returns true when the data dependences have been computed, false otherwise. Given a loop nest LOOP, the following vectors are returned: DATAREFS is initialized to all the array elements contained in this loop, DEPENDENCE_RELATIONS contains the relations between the data references. Compute read-read and self relations if COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE.

If the loop nest is not well formed, or one of the data references is not computable, give up without spending time to compute other dependences.

void compute_self_dependence

(

struct data_dependence_relation *

)

struct data_reference* create_data_ref ( loop_p  nest, loop_p  loop, tree  memref, gimple  stmt, bool  is_read  )

read

Analyzes memory reference MEMREF accessed in STMT. The reference is read if IS_READ is true, write otherwise. Returns the data_reference description of MEMREF. NEST is the outermost loop in which the reference should be instantiated, LOOP is the loop in which the data reference should be analyzed.

static unsigned ddr_dependence_level ( )

inlinestatic

Return the dependence level for the DDR relation.

static bool ddr_is_anti_dependent ( )

inlinestatic

Return true when DDR is an anti-dependence relation.

static bool ddrs_have_anti_deps ( )

inlinestatic

Return true when DEPENDENCE_RELATIONS contains an anti-dependence.

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

void debug

(

data_reference &

ref

)

void debug

(

data_reference *

ptr

)

void debug

(

vec< data_reference_p > &

ref

)

void debug

(

vec< data_reference_p > *

ptr

)

void debug

(

vec< ddr_p > &

ref

)

void debug

(

vec< ddr_p > *

ptr

)

void debug_data_dependence_relation

(

struct data_dependence_relation *

)

void debug_data_dependence_relations

(

vec< ddr_p >

)

void debug_data_reference

(

struct data_reference *

)

void debug_data_references

(

vec< data_reference_p >

)

void debug_ddrs

(

vec< ddr_p >

)

static unsigned dependence_level ( )

inlinestatic

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 DECL_BIT_FIELD, DR_REF, DR_STEP, TREE_CODE, and TREE_OPERAND.

Referenced by ddrs_have_anti_deps().

bool dr_analyze_innermost	(	struct data_reference *	,
		struct loop *
	)

bool dr_equal_offsets_p	(	struct data_reference *	dra,
		struct data_reference *	drb
	)

Check if DRA and DRB have equal offsets.

bool dr_may_alias_p	(	const struct data_reference *	a,
		const struct data_reference *	b,
		bool	loop_nest
	)

Returns false if we can prove that data references A and B do not alias, true otherwise. If LOOP_NEST is false no cross-iteration aliases are considered.

 If we are not processing a loop nest but scalar code we
 do not need to care about possible cross-iteration dependences
 and thus can process the full original reference.  Do so,
 similar to how loop invariant motion applies extra offset-based
 disambiguation.   

 If we had an evolution in a MEM_REF BASE_OBJECT we do not know
 the size of the base-object.  So we cannot do any offset/overlap
 based analysis but have to rely on points-to information only.   

 Otherwise DR_BASE_OBJECT is an access that covers the whole object
 that is being subsetted in the loop nest.   

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

Dump into FILE all the dependence relations from DDRS.

Referenced by debug_data_dependence_relation().

void dump_data_reference	(	FILE *	outf,
		struct data_reference *	dr
	)

Dump function for a DATA_REFERENCE structure.

Referenced by debug_data_references().

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

Search the data references in LOOP, and record the information into DATAREFS. Returns chrec_dont_know when failing to analyze a difficult case, returns NULL_TREE otherwise.

tree find_data_references_in_loop	(	struct loop *	loop,
		vec< data_reference_p > *	datarefs
	)

Search the data references in LOOP, and record the information into DATAREFS. Returns chrec_dont_know when failing to analyze a difficult case, returns NULL_TREE otherwise.

TODO: This function should be made smarter so that it can handle address arithmetic as if they were array accesses, etc.

bool find_data_references_in_stmt	(	struct loop *	nest,
		gimple	stmt,
		vec< data_reference_p > *	datarefs
	)

Stores the data references in STMT to DATAREFS. If there is an unanalyzable reference, returns false, otherwise returns true. NEST is the outermost loop of the loop nest in which the references should be analyzed.

Referenced by create_rdg_cd_edges().

bool find_loop_nest	(	struct loop *	,
		vec< loop_p > *
	)

void free_data_ref

(

data_reference_p

)

void free_data_refs

(

vec< data_reference_p >

)

void free_dependence_relation

(

struct data_dependence_relation *

)

void free_dependence_relations

(

vec< ddr_p >

)

bool graphite_find_data_references_in_stmt	(	loop_p	nest,
		loop_p	loop,
		gimple	stmt,
		vec< data_reference_p > *	datarefs
	)

Stores the data references in STMT to DATAREFS. If there is an unanalyzable reference, returns false, otherwise returns true. NEST is the outermost loop of the loop nest in which the references should be instantiated, LOOP is the loop in which the references should be analyzed.

static int index_in_loop_nest ( )

inlinestatic

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

Referenced by analyze_overlapping_iterations().

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

read

Initialize a data dependence relation between data accesses A and B. NB_LOOPS is the number of loops surrounding the references: the size of the classic distance/direction vectors.

 If the data references do not alias, then they are independent.   

 The case where the references are exactly the same.   

 If the references do not access the same object, we do not know
 whether they alias or not.   

 If the base of the object is not invariant in the loop nest, we cannot
 analyze it.  TODO – in fact, it would suffice to record that there may
 be arbitrary dependences in the loops where the base object varies.   

 If the number of dimensions of the access to not agree we can have
 a pointer access to a component of the array element type and an
 array access while the base-objects are still the same.  Punt.   

References chrec_dont_know, and DDR_ARE_DEPENDENT.

Referenced by ddr_consistent_p().

bool known_dependences_p ( )

inline

Returns true when all the dependences are computable.

static lambda_matrix lambda_matrix_new ( )

inlinestatic

Allocate a matrix of M rows x N cols.

static void lambda_vector_clear ( )

inlinestatic

Clear out vector VEC1 of length SIZE.

static int lambda_vector_gcd ( )

inlinestatic

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

static bool lambda_vector_lexico_pos ( lambda_vector  v, unsigned  n  )

inlinestatic

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

static lambda_vector lambda_vector_new ( )

inlinestatic

Allocate a new vector of given SIZE.

Referenced by add_multivariate_self_dist(), analyze_overlapping_iterations(), and omega_setup_subscript().

static bool lambda_vector_zerop ( )

inlinestatic

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

static bool same_access_functions ( )

inlinestatic

Return true when the DDR contains two data references that have the same access functions.

References chrec_dont_know, DDR_ARE_DEPENDENT, and FOR_EACH_VEC_ELT.

Referenced by omega_setup_subscript(), and same_data_refs().

static bool same_data_refs ( )

inlinestatic

Return true when the data references A and B are accessing the same memory object with the same access functions.

The references are exactly the same.

References DDR_A, DDR_ARE_DEPENDENT, DDR_B, DR_IS_READ, DR_IS_WRITE, NULL_TREE, and same_access_functions().

static bool same_data_refs_base_objects ( )

inlinestatic

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

void split_constant_offset	(	tree	,
		tree *	,
		tree *
	)

void tree_check_data_deps

(

void

)

Computes all the data dependences and check that the results of several analyzers are the same.

Referenced by make_pass_vectorize().