tree-data-ref.cc File Reference

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "rtl.h"
#include "tree.h"
#include "gimple.h"
#include "gimple-pretty-print.h"
#include "alias.h"
#include "fold-const.h"
#include "expr.h"
#include "gimple-iterator.h"
#include "tree-ssa-loop-niter.h"
#include "tree-ssa-loop.h"
#include "tree-ssa.h"
#include "cfgloop.h"
#include "tree-data-ref.h"
#include "tree-scalar-evolution.h"
#include "dumpfile.h"
#include "tree-affine.h"
#include "builtins.h"
#include "tree-eh.h"
#include "ssa.h"
#include "internal-fn.h"
#include "vr-values.h"
#include "range-op.h"
#include "tree-ssa-loop-ivopts.h"
#include "calls.h"

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

Data Structures
struct	datadep_stats
struct	data_ref_loc

Macros
#define	INCLUDE_ALGORITHM
#define	FLOOR_DIV(x, y)

Functions
static bool	subscript_dependence_tester_1 (struct data_dependence_relation *, unsigned int, unsigned int, class loop *)
static bool	tree_fold_divides_p (const_tree a, const_tree b)
static bool	int_divides_p (lambda_int a, lambda_int b)
static bool	ref_contains_union_access_p (tree ref)
static void	dump_data_references (FILE *file, vec< data_reference_p > datarefs)
DEBUG_FUNCTION void	debug (vec< data_reference_p > &ref)
DEBUG_FUNCTION void	debug (vec< data_reference_p > *ptr)
DEBUG_FUNCTION void	debug_data_references (vec< data_reference_p > datarefs)
DEBUG_FUNCTION void	debug_data_reference (struct data_reference *dr)
void	dump_data_reference (FILE *outf, struct data_reference *dr)
DEBUG_FUNCTION void	debug (data_reference &ref)
DEBUG_FUNCTION void	debug (data_reference *ptr)
DEBUG_FUNCTION void	dump_affine_function (FILE *outf, affine_fn fn)
DEBUG_FUNCTION void	dump_conflict_function (FILE *outf, conflict_function *cf)
DEBUG_FUNCTION void	dump_subscript (FILE *outf, struct subscript *subscript)
DEBUG_FUNCTION void	print_direction_vector (FILE *outf, lambda_vector dirv, int length)
DEBUG_FUNCTION void	print_dir_vectors (FILE *outf, vec< lambda_vector > dir_vects, int length)
DEBUG_FUNCTION void	print_lambda_vector (FILE *outfile, lambda_vector vector, int n)
DEBUG_FUNCTION void	print_dist_vectors (FILE *outf, vec< lambda_vector > dist_vects, int length)
DEBUG_FUNCTION void	dump_data_dependence_relation (FILE *outf, const data_dependence_relation *ddr)
DEBUG_FUNCTION void	debug_data_dependence_relation (const struct data_dependence_relation *ddr)
DEBUG_FUNCTION void	dump_data_dependence_relations (FILE *file, const vec< ddr_p > &ddrs)
DEBUG_FUNCTION void	debug (vec< ddr_p > &ref)
DEBUG_FUNCTION void	debug (vec< ddr_p > *ptr)
DEBUG_FUNCTION void	debug_data_dependence_relations (vec< ddr_p > ddrs)
DEBUG_FUNCTION void	dump_dist_dir_vectors (FILE *file, vec< ddr_p > ddrs)
DEBUG_FUNCTION void	dump_ddrs (FILE *file, vec< ddr_p > ddrs)
DEBUG_FUNCTION void	debug_ddrs (vec< ddr_p > ddrs)
static bool	compute_distributive_range (tree type, irange &op0_range, tree_code code, irange &op1_range, tree *off, irange *result_range)
static bool	nop_conversion_for_offset_p (tree to_type, tree from_type, irange &range)
static void	split_constant_offset (tree type, tree *var, tree *off, irange *result_range, hash_map< tree, std::pair< tree, tree > > &cache, unsigned *limit)
static bool	split_constant_offset_1 (tree type, tree op0, enum tree_code code, tree op1, tree *var, tree *off, irange *result_range, hash_map< tree, std::pair< tree, tree > > &cache, unsigned *limit)
void	split_constant_offset (tree exp, tree *var, tree *off)
static tree	canonicalize_base_object_address (tree addr)
opt_result	dr_analyze_innermost (innermost_loop_behavior *drb, tree ref, class loop *loop, const gimple *stmt)
static bool	access_fn_component_p (tree op)
static bool	base_supports_access_fn_components_p (tree base)
static void	dr_analyze_indices (struct indices *dri, tree ref, edge nest, loop_p loop)
static void	dr_analyze_alias (struct data_reference *dr)
void	free_data_ref (data_reference_p dr)
struct data_reference *	create_data_ref (edge nest, loop_p loop, tree memref, gimple *stmt, bool is_read, bool is_conditional_in_stmt)
int	data_ref_compare_tree (tree t1, tree t2)
opt_result	runtime_alias_check_p (ddr_p ddr, class loop *loop, bool speed_p)
static bool	operator== (const dr_with_seg_len &d1, const dr_with_seg_len &d2)
static int	comp_dr_with_seg_len_pair (const void *pa_, const void *pb_)
static void	dump_alias_pair (dr_with_seg_len_pair_t *alias_pair, const char *indent)
void	prune_runtime_alias_test_list (vec< dr_with_seg_len_pair_t > *alias_pairs, poly_uint64)
static bool	create_ifn_alias_checks (tree *cond_expr, const dr_with_seg_len_pair_t &alias_pair)
static bool	create_intersect_range_checks_index (class loop *loop, tree *cond_expr, const dr_with_seg_len_pair_t &alias_pair)
static bool	create_waw_or_war_checks (tree *cond_expr, const dr_with_seg_len_pair_t &alias_pair)
static void	get_segment_min_max (const dr_with_seg_len &d, tree *seg_min_out, tree *seg_max_out, HOST_WIDE_INT align)
static void	create_intersect_range_checks (class loop *loop, tree *cond_expr, const dr_with_seg_len_pair_t &alias_pair)
void	create_runtime_alias_checks (class loop *loop, const vec< dr_with_seg_len_pair_t > *alias_pairs, tree *cond_expr)
static bool	dr_equal_offsets_p1 (tree offset1, tree offset2)
bool	dr_equal_offsets_p (struct data_reference *dra, struct data_reference *drb)
static bool	affine_function_equal_p (affine_fn fna, affine_fn fnb)
static affine_fn	common_affine_function (conflict_function *cf)
static tree	affine_function_base (affine_fn fn)
static bool	affine_function_constant_p (affine_fn fn)
static bool	affine_function_zero_p (affine_fn fn)
static tree	signed_type_for_types (tree ta, tree tb)
static affine_fn	affine_fn_op (enum tree_code op, affine_fn fna, affine_fn fnb)
static affine_fn	affine_fn_plus (affine_fn fna, affine_fn fnb)
static affine_fn	affine_fn_minus (affine_fn fna, affine_fn fnb)
static void	affine_fn_free (affine_fn fn)
static void	compute_subscript_distance (struct data_dependence_relation *ddr)
static conflict_function *	conflict_fn_not_known (void)
static conflict_function *	conflict_fn_no_dependence (void)
static bool	object_address_invariant_in_loop_p (const class loop *loop, const_tree obj)
static bool	contains_ssa_ref_p_1 (tree, tree *idx, void *data)
static bool	contains_ssa_ref_p (tree ref)
bool	dr_may_alias_p (const struct data_reference *a, const struct data_reference *b, class loop *loop_nest)
static bool	access_fn_components_comparable_p (tree ref_a, tree ref_b)
struct data_dependence_relation *	initialize_data_dependence_relation (struct data_dependence_relation *res, vec< loop_p > loop_nest, bool use_alt_indices)
struct data_dependence_relation *	initialize_data_dependence_relation (struct data_reference *a, struct data_reference *b, vec< loop_p > loop_nest)
static void	free_conflict_function (conflict_function *f)
static void	free_subscripts (vec< subscript_p > subscripts)
static void	finalize_ddr_dependent (struct data_dependence_relation *ddr, tree chrec)
static void	non_affine_dependence_relation (struct data_dependence_relation *ddr)
static bool	ziv_subscript_p (const_tree chrec_a, const_tree chrec_b)
static bool	siv_subscript_p (const_tree chrec_a, const_tree chrec_b)
static conflict_function *	conflict_fn (unsigned n,...)
static affine_fn	affine_fn_cst (tree cst)
static affine_fn	affine_fn_univar (tree cst, unsigned dim, tree coef)
static void	analyze_ziv_subscript (tree chrec_a, tree chrec_b, conflict_function **overlaps_a, conflict_function **overlaps_b, tree *last_conflicts)
static tree	max_stmt_executions_tree (class loop *loop)
static bool	chrec_is_positive (tree chrec, bool *value)
static void	analyze_siv_subscript_cst_affine (tree chrec_a, tree chrec_b, conflict_function **overlaps_a, conflict_function **overlaps_b, tree *last_conflicts)
static tree	initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult)
static void	compute_overlap_steps_for_affine_univar (HOST_WIDE_INT niter, HOST_WIDE_INT step_a, HOST_WIDE_INT step_b, affine_fn *overlaps_a, affine_fn *overlaps_b, tree *last_conflicts, int dim)
static void	compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b, conflict_function **overlaps_a, conflict_function **overlaps_b, tree *last_conflicts)
static void	lambda_vector_copy (lambda_vector vec1, lambda_vector vec2, int size)
static void	lambda_matrix_copy (lambda_matrix mat1, lambda_matrix mat2, int m, int n)
static void	lambda_matrix_id (lambda_matrix mat, int size)
static int	lambda_vector_first_nz (lambda_vector vec1, int n, int start)
static bool	lambda_matrix_row_add (lambda_matrix mat, int n, int r1, int r2, lambda_int const1)
static void	lambda_vector_mult_const (lambda_vector vec1, lambda_vector vec2, int size, lambda_int const1)
static void	lambda_vector_negate (lambda_vector vec1, lambda_vector vec2, int size)
static void	lambda_matrix_row_negate (lambda_matrix mat, int n, int r1)
static bool	lambda_vector_equal (lambda_vector vec1, lambda_vector vec2, int size)
static bool	lambda_matrix_right_hermite (lambda_matrix A, int m, int n, lambda_matrix S, lambda_matrix U)
static void	analyze_subscript_affine_affine (tree chrec_a, tree chrec_b, conflict_function **overlaps_a, conflict_function **overlaps_b, tree *last_conflicts)
static bool	can_use_analyze_subscript_affine_affine (tree *chrec_a, tree *chrec_b)
static void	analyze_siv_subscript (tree chrec_a, tree chrec_b, conflict_function **overlaps_a, conflict_function **overlaps_b, tree *last_conflicts, int loop_nest_num)
static bool	gcd_of_steps_may_divide_p (const_tree chrec, const_tree cst)
static void	analyze_miv_subscript (tree chrec_a, tree chrec_b, conflict_function **overlaps_a, conflict_function **overlaps_b, tree *last_conflicts, class loop *loop_nest)
static void	analyze_overlapping_iterations (tree chrec_a, tree chrec_b, conflict_function **overlap_iterations_a, conflict_function **overlap_iterations_b, tree *last_conflicts, class loop *loop_nest)
static void	save_dist_v (struct data_dependence_relation *ddr, lambda_vector dist_v)
static void	save_dir_v (struct data_dependence_relation *ddr, lambda_vector dir_v)
static void	add_outer_distances (struct data_dependence_relation *ddr, lambda_vector dist_v, int index)
static bool	build_classic_dist_vector_1 (struct data_dependence_relation *ddr, unsigned int a_index, unsigned int b_index, lambda_vector dist_v, bool *init_b, int *index_carry)
static bool	invariant_access_functions (const struct data_dependence_relation *ddr, int lnum)
static void	add_multivariate_self_dist (struct data_dependence_relation *ddr, tree c_2)
static void	add_other_self_distances (struct data_dependence_relation *ddr)
static void	insert_innermost_unit_dist_vector (struct data_dependence_relation *ddr)
static void	add_distance_for_zero_overlaps (struct data_dependence_relation *ddr)
static bool	same_access_functions (const struct data_dependence_relation *ddr)
static bool	build_classic_dist_vector (struct data_dependence_relation *ddr, class loop *loop_nest)
static enum data_dependence_direction	dir_from_dist (int dist)
static void	build_classic_dir_vector (struct data_dependence_relation *ddr)
static void	subscript_dependence_tester (struct data_dependence_relation *ddr, class loop *loop_nest)
static bool	access_functions_are_affine_or_constant_p (const struct data_reference *a, const class loop *loop_nest)
void	compute_affine_dependence (struct data_dependence_relation *ddr, class loop *loop_nest)
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)
static bool	get_references_in_stmt (gimple *stmt, vec< data_ref_loc, va_heap > *references)
bool	loop_nest_has_data_refs (loop_p loop)
opt_result	find_data_references_in_stmt (class loop *nest, gimple *stmt, vec< data_reference_p > *datarefs)
bool	graphite_find_data_references_in_stmt (edge nest, loop_p loop, gimple *stmt, vec< data_reference_p > *datarefs)
tree	find_data_references_in_bb (class loop *loop, basic_block bb, vec< data_reference_p > *datarefs)
tree	find_data_references_in_loop (class loop *loop, vec< data_reference_p > *datarefs)
unsigned int	dr_alignment (innermost_loop_behavior *drb)
static tree	get_base_for_alignment_1 (tree base, unsigned int *alignment_out)
tree	get_base_for_alignment (tree addr, unsigned int *max_alignment)
static bool	find_loop_nest_1 (class loop *loop, vec< loop_p > *loop_nest)
bool	find_loop_nest (class loop *loop, vec< loop_p > *loop_nest)
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)
void	free_dependence_relation (struct data_dependence_relation *ddr)
void	free_dependence_relations (vec< ddr_p > &dependence_relations)
void	free_data_refs (vec< data_reference_p > &datarefs)
static tree	dr_step_indicator (struct data_reference *dr, int useful_min)
tree	dr_direction_indicator (struct data_reference *dr)
tree	dr_zero_step_indicator (struct data_reference *dr)
bool	dr_known_forward_stride_p (struct data_reference *dr)

Variables
static struct datadep_stats	dependence_stats

Macro Definition Documentation

FLOOR_DIV

#define FLOOR_DIV	(		x,
			y )

Value:

((x) / (y))

Referenced by compute_overlap_steps_for_affine_univar().

INCLUDE_ALGORITHM

#define INCLUDE_ALGORITHM

Data references and dependences detectors.
   Copyright (C) 2003-2026 Free Software Foundation, Inc.
   Contributed by Sebastian Pop <pop@cri.ensmp.fr>

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
Software Foundation; either version 3, or (at your option) any later
version.

GCC is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
for more details.

You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3.  If not see
<http://www.gnu.org/licenses/>.   

This pass walks a given loop structure searching for array
  references.  The information about the array accesses is recorded
  in DATA_REFERENCE structures.

  The basic test for determining the dependences is:
  given two access functions chrec1 and chrec2 to a same array, and
  x and y two vectors from the iteration domain, the same element of
  the array is accessed twice at iterations x and y if and only if:
  |             chrec1 (x) == chrec2 (y).

  The goals of this analysis are:

  - to determine the independence: the relation between two
    independent accesses is qualified with the chrec_known (this
    information allows a loop parallelization),

  - when two data references access the same data, to qualify the
    dependence relation with classic dependence representations:

      - distance vectors
      - direction vectors
      - loop carried level dependence
      - polyhedron dependence
    or with the chains of recurrences based representation,

  - to define a knowledge base for storing the data dependence
    information,

  - to define an interface to access this data.


  Definitions:

  - subscript: given two array accesses a subscript is the tuple
  composed of the access functions for a given dimension.  Example:
  Given A[f1][f2][f3] and B[g1][g2][g3], there are three subscripts:
  (f1, g1), (f2, g2), (f3, g3).

  - Diophantine equation: an equation whose coefficients and
  solutions are integer constants, for example the equation
  |   3*x + 2*y = 1
  has an integer solution x = 1 and y = -1.

  References:

  - "Advanced Compilation for High Performance Computing" by Randy
  Allen and Ken Kennedy.
  http://citeseer.ist.psu.edu/goff91practical.html

  - "Loop Transformations for Restructuring Compilers - The Foundations"
  by Utpal Banerjee.

Function Documentation

access_fn_component_p()

bool access_fn_component_p ( tree op )

static

Return true if OP is a valid component reference for a DR access
function.  This accepts a subset of what handled_component_p accepts.   

References access_fn_component_p(), AGGREGATE_TYPE_P, TREE_CODE, TREE_OPERAND, and TREE_TYPE.

Referenced by access_fn_component_p(), and initialize_data_dependence_relation().

access_fn_components_comparable_p()

bool access_fn_components_comparable_p ( tree ref_a, tree ref_b )

static

REF_A and REF_B both satisfy access_fn_component_p.  Return true
if it is meaningful to compare their associated access functions
when checking for dependencies.   

References access_fn_components_comparable_p(), DECL_CONTEXT, TREE_CODE, TREE_OPERAND, TREE_TYPE, and types_compatible_p().

Referenced by access_fn_components_comparable_p(), and initialize_data_dependence_relation().

access_functions_are_affine_or_constant_p()

bool access_functions_are_affine_or_constant_p ( const struct data_reference * a, const class loop * loop_nest )

static

Returns true when all the access functions of A are affine or
constant with respect to LOOP_NEST.   

References a, access_functions_are_affine_or_constant_p(), DR_ACCESS_FNS, evolution_function_is_affine_multivariate_p(), evolution_function_is_invariant_p(), and loop::num.

Referenced by access_functions_are_affine_or_constant_p(), and compute_affine_dependence().

add_distance_for_zero_overlaps()

void add_distance_for_zero_overlaps ( struct data_dependence_relation * ddr )

static

Adds a unit distance vector to DDR when there is a 0 overlap.  This
is the case for example when access functions are the same and
equal to a constant, as in:

| loop_1
|   A[3] = ...
|   ... = A[3]
| endloop_1

in which case the distance vectors are (0) and (1).   

References add_distance_for_zero_overlaps(), affine_function_zero_p(), DDR_NUM_SUBSCRIPTS, DDR_SUBSCRIPT, conflict_function::fns, i, insert_innermost_unit_dist_vector(), conflict_function::n, SUB_CONFLICTS_IN_A, and SUB_CONFLICTS_IN_B.

Referenced by add_distance_for_zero_overlaps(), and build_classic_dist_vector().

add_multivariate_self_dist()

void add_multivariate_self_dist ( struct data_dependence_relation * ddr, tree c_2 )

static

Helper function for the case where DDR_A and DDR_B are the same
multivariate access function with a constant step.  For an example
see pr34635-1.c.   

References add_multivariate_self_dist(), add_outer_distances(), CHREC_LEFT, CHREC_RIGHT, CHREC_VARIABLE, DDR_AFFINE_P, DDR_LOOP_NEST, DDR_NB_LOOPS, gcd(), index_in_loop_nest(), int_cst_value(), lambda_vector_new(), save_dist_v(), and TREE_CODE.

Referenced by add_multivariate_self_dist(), and add_other_self_distances().

add_other_self_distances()

void add_other_self_distances ( struct data_dependence_relation * ddr )

static

Helper function for the case where DDR_A and DDR_B are the same
access functions.   

References add_multivariate_self_dist(), add_other_self_distances(), add_outer_distances(), cfun, chrec_dont_know, CHREC_LEFT, CHREC_VARIABLE, DDR_AFFINE_P, DDR_ARE_DEPENDENT, DDR_LOOP_NEST, DDR_NB_LOOPS, DDR_NUM_SUBSCRIPTS, DDR_SUBSCRIPT, DDR_SUBSCRIPTS, evolution_function_is_univariate_p(), flow_loop_nested_p(), FOR_EACH_VEC_ELT, get_loop(), i, index_in_loop_nest(), lambda_vector_new(), MIN, loop::num, SUB_ACCESS_FN, and TREE_CODE.

Referenced by add_other_self_distances(), and build_classic_dist_vector().

add_outer_distances()

void add_outer_distances ( struct data_dependence_relation * ddr, lambda_vector dist_v, int index )

static

Add a distance of 1 on all the loops outer than INDEX.  If we
haven't yet determined a distance for this outer loop, push a new
distance vector composed of the previous distance, and a distance
of 1 for this outer loop.  Example:

| loop_1
|   loop_2
|     A[10]
|   endloop_2
| endloop_1

Saved vectors are of the form (dist_in_1, dist_in_2).  First, we
save (0, 1), then we have to save (1, 0).   

References add_outer_distances(), DDR_NB_LOOPS, lambda_vector_copy(), lambda_vector_new(), and save_dist_v().

Referenced by add_multivariate_self_dist(), add_other_self_distances(), add_outer_distances(), and build_classic_dist_vector().

affine_fn_cst()

affine_fn affine_fn_cst ( tree cst )

static

Returns constant affine function with value CST.   

References affine_fn_cst().

Referenced by affine_fn_cst(), analyze_miv_subscript(), analyze_overlapping_iterations(), analyze_siv_subscript_cst_affine(), analyze_subscript_affine_affine(), analyze_ziv_subscript(), compute_overlap_steps_for_affine_1_2(), and compute_overlap_steps_for_affine_univar().

affine_fn_free()

void affine_fn_free ( affine_fn fn )

static

Frees affine function FN.   

References affine_fn_free().

Referenced by affine_fn_free(), compute_overlap_steps_for_affine_1_2(), compute_subscript_distance(), and free_conflict_function().

affine_fn_minus()

affine_fn affine_fn_minus ( affine_fn fna, affine_fn fnb )

static

Returns the difference of affine functions FNA and FNB.   

References affine_fn_minus(), and affine_fn_op().

Referenced by affine_fn_minus(), and compute_subscript_distance().

affine_fn_op()

affine_fn affine_fn_op ( enum tree_code op, affine_fn fna, affine_fn fnb )

static

Applies operation OP on affine functions FNA and FNB, and returns the
result.   

References affine_fn_op(), fold_build2, i, integer_zero_node, signed_type_for(), signed_type_for_types(), and TREE_TYPE.

Referenced by affine_fn_minus(), affine_fn_op(), and affine_fn_plus().

affine_fn_plus()

affine_fn affine_fn_plus ( affine_fn fna, affine_fn fnb )

static

Returns the sum of affine functions FNA and FNB.   

References affine_fn_op(), and affine_fn_plus().

Referenced by affine_fn_plus(), and compute_overlap_steps_for_affine_1_2().

affine_fn_univar()

affine_fn affine_fn_univar ( tree cst, unsigned dim, tree coef )

static

Returns affine function with single variable, CST + COEF * x_DIM.   

References affine_fn_univar(), gcc_assert, i, and integer_zero_node.

Referenced by affine_fn_univar(), analyze_subscript_affine_affine(), and compute_overlap_steps_for_affine_univar().

affine_function_base()

tree affine_function_base ( affine_fn fn )

static

Returns the base of the affine function FN.   

References affine_function_base().

Referenced by affine_function_base(), affine_function_zero_p(), and compute_subscript_distance().

affine_function_constant_p()

bool affine_function_constant_p ( affine_fn fn )

static

Returns true if FN is a constant.   

References affine_function_constant_p(), i, and integer_zerop().

Referenced by affine_function_constant_p(), affine_function_zero_p(), and compute_subscript_distance().

affine_function_equal_p()

bool affine_function_equal_p ( affine_fn fna, affine_fn fnb )

static

Returns true if FNA == FNB.   

References affine_function_equal_p(), i, and operand_equal_p().

Referenced by affine_function_equal_p(), and common_affine_function().

affine_function_zero_p()

bool affine_function_zero_p ( affine_fn fn )

static

Returns true if FN is the zero constant function.   

References affine_function_base(), affine_function_constant_p(), affine_function_zero_p(), and integer_zerop().

Referenced by add_distance_for_zero_overlaps(), and affine_function_zero_p().

analyze_miv_subscript()

void analyze_miv_subscript ( tree chrec_a, tree chrec_b, conflict_function ** overlaps_a, conflict_function ** overlaps_b, tree * last_conflicts, class loop * loop_nest )

static

Analyze a MIV (Multiple Index Variable) subscript with respect to
LOOP_NEST.  *OVERLAPS_A and *OVERLAPS_B are initialized to the
functions that describe the relation between the elements accessed
twice by CHREC_A and CHREC_B.  For k >= 0, the following property
is verified:

CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).   

References affine_fn_cst(), analyze_miv_subscript(), analyze_subscript_affine_affine(), CF_NO_DEPENDENCE_P, CF_NOT_KNOWN_P, chrec_contains_symbols(), chrec_convert(), chrec_dont_know, chrec_fold_minus(), conflict_fn(), conflict_fn_no_dependence(), conflict_fn_not_known(), dependence_stats, dump_file, dump_flags, eq_evolutions_p(), evolution_function_is_affine_in_loop(), evolution_function_is_affine_multivariate_p(), evolution_function_is_constant_p(), gcd_of_steps_may_divide_p(), get_chrec_loop(), integer_zero_node, max_stmt_executions_tree(), NULL, loop::num, datadep_stats::num_miv, datadep_stats::num_miv_dependent, datadep_stats::num_miv_independent, datadep_stats::num_miv_unimplemented, signed_type_for_types(), TDF_DETAILS, and TREE_TYPE.

Referenced by analyze_miv_subscript(), and analyze_overlapping_iterations().

analyze_overlapping_iterations()

void analyze_overlapping_iterations ( tree chrec_a, tree chrec_b, conflict_function ** overlap_iterations_a, conflict_function ** overlap_iterations_b, tree * last_conflicts, class loop * loop_nest )

static

Determines the iterations for which CHREC_A is equal to CHREC_B in
  with respect to LOOP_NEST.  OVERLAP_ITERATIONS_A and
  OVERLAP_ITERATIONS_B are initialized with two functions that
  describe the iterations that contain conflicting elements.

  Remark: For an integer k >= 0, the following equality is true:

  CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).

References affine_fn_cst(), analyze_miv_subscript(), analyze_overlapping_iterations(), analyze_siv_subscript(), analyze_ziv_subscript(), chrec_contains_symbols(), chrec_contains_undetermined(), chrec_dont_know, conflict_fn(), conflict_fn_not_known(), dependence_stats, dump_conflict_function(), dump_file, dump_flags, eq_evolutions_p(), evolution_function_is_affine_multivariate_p(), integer_zero_node, NULL_TREE, loop::num, datadep_stats::num_same_subscript_function, datadep_stats::num_subscript_tests, datadep_stats::num_subscript_undetermined, operand_equal_p(), print_generic_expr(), siv_subscript_p(), TDF_DETAILS, and ziv_subscript_p().

Referenced by analyze_overlapping_iterations(), and subscript_dependence_tester_1().

analyze_siv_subscript()

void analyze_siv_subscript ( tree chrec_a, tree chrec_b, conflict_function ** overlaps_a, conflict_function ** overlaps_b, tree * last_conflicts, int loop_nest_num )

static

Analyze a SIV (Single Index Variable) subscript.  *OVERLAPS_A and
*OVERLAPS_B are initialized to the functions that describe the
relation between the elements accessed twice by CHREC_A and
CHREC_B.  For k >= 0, the following property is verified:

CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).   

References analyze_siv_subscript(), analyze_siv_subscript_cst_affine(), analyze_subscript_affine_affine(), can_use_analyze_subscript_affine_affine(), CF_NO_DEPENDENCE_P, CF_NOT_KNOWN_P, chrec_contains_symbols(), chrec_dont_know, conflict_fn_not_known(), dependence_stats, dump_file, dump_flags, evolution_function_is_affine_in_loop(), evolution_function_is_constant_p(), datadep_stats::num_siv, datadep_stats::num_siv_dependent, datadep_stats::num_siv_independent, datadep_stats::num_siv_unimplemented, and TDF_DETAILS.

Referenced by analyze_overlapping_iterations(), and analyze_siv_subscript().

analyze_siv_subscript_cst_affine()

void analyze_siv_subscript_cst_affine ( tree chrec_a, tree chrec_b, conflict_function ** overlaps_a, conflict_function ** overlaps_b, tree * last_conflicts )

static

Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
constant, and CHREC_B is an affine function.  *OVERLAPS_A and
*OVERLAPS_B are initialized to the functions that describe the
relation between the elements accessed twice by CHREC_A and
CHREC_B.  For k >= 0, the following property is verified:

CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).   

References affine_fn_cst(), analyze_siv_subscript_cst_affine(), chrec_convert(), chrec_dont_know, chrec_fold_minus(), chrec_is_positive(), CHREC_RIGHT, compare_tree_int(), conflict_fn(), conflict_fn_no_dependence(), conflict_fn_not_known(), dependence_stats, dump_file, dump_flags, fold_build1, fold_build2, free_conflict_function(), get_chrec_loop(), initial_condition(), integer_one_node, integer_zero_node, integer_zerop(), max_stmt_executions_int(), NULL, datadep_stats::num_siv_dependent, datadep_stats::num_siv_independent, datadep_stats::num_siv_unimplemented, signed_type_for_types(), TDF_DETAILS, TREE_CODE, tree_fold_divides_p(), and TREE_TYPE.

Referenced by analyze_siv_subscript(), and analyze_siv_subscript_cst_affine().

analyze_subscript_affine_affine()

void analyze_subscript_affine_affine ( tree chrec_a, tree chrec_b, conflict_function ** overlaps_a, conflict_function ** overlaps_b, tree * last_conflicts )

static

Determines the overlapping elements due to accesses CHREC_A and
CHREC_B, that are affine functions.  This function cannot handle
symbolic evolution functions, ie. when initial conditions are
parameters, because it uses lambda matrices of integers.   

References affine_fn_cst(), affine_fn_univar(), analyze_subscript_affine_affine(), build_int_cst(), CEIL, chrec_dont_know, CHREC_RIGHT, compute_overlap_steps_for_affine_1_2(), compute_overlap_steps_for_affine_univar(), conflict_fn(), conflict_fn_no_dependence(), conflict_fn_not_known(), dump_conflict_function(), dump_file, dump_flags, eq_evolutions_p(), gcc_obstack_init, get_chrec_loop(), i1, initialize_matrix_A(), int_cst_value(), int_divides_p(), integer_type_node, integer_zero_node, lambda_matrix_new(), lambda_matrix_right_hermite(), lambda_matrix_row_negate(), MAX, max_stmt_executions_int(), MIN, wi::min_precision(), nb_vars_in_chrec(), NULL, S, wi::sdiv_floor(), SIGNED, wi::smin(), wi::sub(), TDF_DETAILS, generic_wide_int< storage >::to_shwi(), and TYPE_PRECISION.

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

analyze_ziv_subscript()

void analyze_ziv_subscript ( tree chrec_a, tree chrec_b, conflict_function ** overlaps_a, conflict_function ** overlaps_b, tree * last_conflicts )

static

Analyze a ZIV (Zero Index Variable) subscript.  *OVERLAPS_A and
*OVERLAPS_B are initialized to the functions that describe the
relation between the elements accessed twice by CHREC_A and
CHREC_B.  For k >= 0, the following property is verified:

CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).   

References affine_fn_cst(), analyze_ziv_subscript(), chrec_convert(), chrec_dont_know, chrec_fold_minus(), conflict_fn(), conflict_fn_no_dependence(), conflict_fn_not_known(), dependence_stats, dump_file, dump_flags, integer_zero_node, integer_zerop(), NULL, datadep_stats::num_ziv, datadep_stats::num_ziv_dependent, datadep_stats::num_ziv_independent, datadep_stats::num_ziv_unimplemented, signed_type_for_types(), TDF_DETAILS, TREE_CODE, and TREE_TYPE.

Referenced by analyze_overlapping_iterations(), and analyze_ziv_subscript().

base_supports_access_fn_components_p()

bool base_supports_access_fn_components_p ( tree base )

static

Returns whether BASE can have a access_fn_component_p with BASE
as base.   

References base_supports_access_fn_components_p(), TREE_CODE, and TREE_TYPE.

Referenced by base_supports_access_fn_components_p(), and initialize_data_dependence_relation().

build_classic_dir_vector()

void build_classic_dir_vector ( struct data_dependence_relation * ddr )

static

Compute the classic per loop direction vector.  DDR is the data
dependence relation to build a vector from.   

References build_classic_dir_vector(), DDR_DIST_VECTS, DDR_NB_LOOPS, dir_from_dist(), FOR_EACH_VEC_ELT, i, lambda_vector_new(), and save_dir_v().

Referenced by build_classic_dir_vector(), and subscript_dependence_tester().

build_classic_dist_vector()

bool build_classic_dist_vector ( struct data_dependence_relation * ddr, class loop * loop_nest )

static

Compute the classic per loop distance vector.  DDR is the data
dependence relation to build a vector from.  Return false when fail
to represent the data dependence as a distance vector.   

References add_distance_for_zero_overlaps(), add_other_self_distances(), add_outer_distances(), build_classic_dist_vector(), build_classic_dist_vector_1(), compute_subscript_distance(), DDR_ARE_DEPENDENT, DDR_NB_LOOPS, DDR_REVERSED_P, invariant_access_functions(), lambda_vector_copy(), lambda_vector_first_nz(), lambda_vector_lexico_pos(), lambda_vector_new(), NULL_TREE, loop::num, same_access_functions(), save_dist_v(), and subscript_dependence_tester_1().

Referenced by build_classic_dist_vector(), and subscript_dependence_tester().

build_classic_dist_vector_1()

bool build_classic_dist_vector_1 ( struct data_dependence_relation * ddr, unsigned int a_index, unsigned int b_index, lambda_vector dist_v, bool * init_b, int * index_carry )

static

Return false when fail to represent the data dependence as a
distance vector.  A_INDEX is the index of the first reference
(0 for DDR_A, 1 for DDR_B) and B_INDEX is the index of the
second reference.  INIT_B is set to true when a component has been
added to the distance vector DIST_V.  INDEX_CARRY is then set to
the index in DIST_V that carries the dependence.   

References build_classic_dist_vector_1(), cfun, chrec_contains_undetermined(), chrec_known, CHREC_VARIABLE, DDR_LOOP_NEST, DDR_NB_LOOPS, DDR_NUM_SUBSCRIPTS, DDR_SUBSCRIPT, finalize_ddr_dependent(), flow_loop_nested_p(), get_loop(), i, index_in_loop_nest(), int_cst_value(), lambda_vector_new(), MIN, non_affine_dependence_relation(), operand_equal_p(), SUB_ACCESS_FN, SUB_DISTANCE, and TREE_CODE.

Referenced by build_classic_dist_vector(), and build_classic_dist_vector_1().

can_use_analyze_subscript_affine_affine()

bool can_use_analyze_subscript_affine_affine ( tree * chrec_a, tree * chrec_b )

static

Returns true when analyze_subscript_affine_affine can be used for
  determining the dependence relation between chrec_a and chrec_b,
  that contain symbols.  This function modifies chrec_a and chrec_b
  such that the analysis result is the same, and such that they don't
  contain symbols, and then can safely be passed to the analyzer.

  Example: The analysis of the following tuples of evolutions produce
  the same results: {x+1, +, 1}_1 vs. {x+3, +, 1}_1, and {-2, +, 1}_1
  vs. {0, +, 1}_1

  {x+1, +, 1}_1 ({2, +, 1}_1) = {x+3, +, 1}_1 ({0, +, 1}_1)
  {-2, +, 1}_1 ({2, +, 1}_1) = {0, +, 1}_1 ({0, +, 1}_1)

References build_int_cst(), build_polynomial_chrec(), can_use_analyze_subscript_affine_affine(), chrec_contains_symbols(), chrec_convert(), chrec_fold_minus(), CHREC_LEFT, CHREC_RIGHT, chrec_type(), CHREC_VARIABLE, dump_file, dump_flags, evolution_function_is_constant_p(), NULL, and TDF_DETAILS.

Referenced by analyze_siv_subscript(), and can_use_analyze_subscript_affine_affine().

canonicalize_base_object_address()

tree canonicalize_base_object_address ( tree addr )

static

Returns the address ADDR of an object in a canonical shape (without nop
casts, and with type of pointer to the object).   

References build_fold_addr_expr, canonicalize_base_object_address(), POINTER_TYPE_P, STRIP_NOPS, TREE_CODE, TREE_OPERAND, and TREE_TYPE.

Referenced by canonicalize_base_object_address(), and dr_analyze_innermost().

chrec_is_positive()

bool chrec_is_positive ( tree chrec, bool * value )

static

Determine whether the CHREC is always positive/negative.  If the expression
cannot be statically analyzed, return false, otherwise set the answer into
VALUE.   

References build_int_cst(), chrec_apply(), chrec_contains_undetermined(), chrec_fold_minus(), chrec_is_positive(), CHREC_LEFT, CHREC_RIGHT, CHREC_VARIABLE, evolution_function_is_affine_p(), get_chrec_loop(), number_of_latch_executions(), TREE_CODE, and tree_int_cst_sgn().

Referenced by analyze_siv_subscript_cst_affine(), and chrec_is_positive().

common_affine_function()

affine_fn common_affine_function ( conflict_function * cf )

static

If all the functions in CF are the same, returns one of them,
otherwise returns NULL.   

References affine_function_equal_p(), CF_NONTRIVIAL_P, common_affine_function(), conflict_function::fns, i, and conflict_function::n.

Referenced by common_affine_function(), and compute_subscript_distance().

comp_dr_with_seg_len_pair()

int comp_dr_with_seg_len_pair ( const void * pa_, const void * pb_ )

static

Comparison function for sorting objects of dr_with_seg_len_pair_t
so that we can combine aliasing checks in one scan.   

References comp_dr_with_seg_len_pair(), data_ref_compare_tree(), dr_with_seg_len::dr, DR_BASE_ADDRESS, DR_INIT, DR_OFFSET, DR_STEP, dr_with_seg_len_pair_t::first, and dr_with_seg_len_pair_t::second.

Referenced by comp_dr_with_seg_len_pair(), and prune_runtime_alias_test_list().

compute_affine_dependence()

void compute_affine_dependence	(	struct data_dependence_relation *	ddr,
		class loop *	loop_nest )

This computes the affine dependence relation between A and B with
respect to LOOP_NEST.  CHREC_KNOWN is used for representing the
independence between two accesses, while CHREC_DONT_KNOW is used
for representing the unknown relation.

Note that it is possible to stop the computation of the dependence
relation the first time we detect a CHREC_KNOWN element for a given
subscript.   

References access_functions_are_affine_or_constant_p(), chrec_dont_know, chrec_known, compute_affine_dependence(), DDR_A, DDR_ARE_DEPENDENT, DDR_B, dependence_stats, DR_REF, DR_STMT, dump_data_reference(), dump_file, dump_flags, finalize_ddr_dependent(), NULL_TREE, datadep_stats::num_dependence_tests, datadep_stats::num_dependence_undetermined, print_generic_expr(), print_gimple_stmt(), subscript_dependence_tester(), TDF_DETAILS, and TDF_SLIM.

Referenced by compute_affine_dependence(), compute_affine_dependence(), compute_all_dependences(), and loop_distribution::get_data_dependence().

compute_all_dependences()

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

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

References a, b, compute_affine_dependence(), compute_all_dependences(), DR_IS_WRITE, FOR_EACH_VEC_ELT, i, initialize_data_dependence_relation(), data_dependence_relation::loop_nest, and NULL.

Referenced by compute_all_dependences(), compute_data_dependences_for_loop(), compute_self_dependence(), cond_if_else_store_replacement(), determine_loop_nest_reuse(), and vect_analyze_data_ref_dependences().

compute_data_dependences_for_loop()

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

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

References chrec_dont_know, compute_all_dependences(), compute_data_dependences_for_loop(), dependence_stats, dump_file, dump_flags, find_data_references_in_loop(), find_loop_nest(), datadep_stats::num_dependence_dependent, datadep_stats::num_dependence_independent, datadep_stats::num_dependence_tests, datadep_stats::num_dependence_undetermined, datadep_stats::num_miv, datadep_stats::num_miv_dependent, datadep_stats::num_miv_independent, datadep_stats::num_miv_unimplemented, datadep_stats::num_same_subscript_function, datadep_stats::num_siv, datadep_stats::num_siv_dependent, datadep_stats::num_siv_independent, datadep_stats::num_siv_unimplemented, datadep_stats::num_subscript_tests, datadep_stats::num_subscript_undetermined, datadep_stats::num_ziv, datadep_stats::num_ziv_dependent, datadep_stats::num_ziv_independent, datadep_stats::num_ziv_unimplemented, and TDF_STATS.

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

compute_distributive_range()

bool compute_distributive_range ( tree type, irange & op0_range, tree_code code, irange & op1_range, tree * off, irange * result_range )

static

If RESULT_RANGE is nonnull, set *RESULT_RANGE to the range of
OP0 CODE OP1, where:

- OP0 CODE OP1 has integral type TYPE
- the range of OP0 is given by OP0_RANGE and
- the range of OP1 is given by OP1_RANGE.

Independently of RESULT_RANGE, try to compute:

  DELTA = ((sizetype) OP0 CODE (sizetype) OP1)
          - (sizetype) (OP0 CODE OP1)

as a constant and subtract DELTA from the ssizetype constant in *OFF.
Return true on success, or false if DELTA is not known at compile time.

Truncation and sign changes are known to distribute over CODE, i.e.

  (itype) (A CODE B) == (itype) A CODE (itype) B

for any integral type ITYPE whose precision is no greater than the
precision of A and B.   

References compute_distributive_range(), range_op_handler::fold_range(), gcc_assert, wide_int_storage::get_precision(), INTEGRAL_TYPE_P, irange::lower_bound(), wi::mask(), irange::num_pairs(), op1_range(), range_cast(), irange::set_varying(), sizetype, ssizetype, wi::to_wide(), TYPE_OVERFLOW_TRAPS, TYPE_OVERFLOW_UNDEFINED, TYPE_PRECISION, TYPE_UNSIGNED, vrange::undefined_p(), irange::upper_bound(), vrange::varying_p(), and wide_int_to_tree().

Referenced by compute_distributive_range(), and split_constant_offset_1().

compute_overlap_steps_for_affine_1_2()

void compute_overlap_steps_for_affine_1_2 ( tree chrec_a, tree chrec_b, conflict_function ** overlaps_a, conflict_function ** overlaps_b, tree * last_conflicts )

static

Solves the special case of a Diophantine equation where CHREC_A is
an affine bivariate function, and CHREC_B is an affine univariate
function.  For example,

| {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z

has the following overlapping functions:

| x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
| y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
| z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v

FORNOW: This is a specialized implementation for a case occurring in
a common benchmark.  Implement the general algorithm.   

References affine_fn_cst(), affine_fn_free(), affine_fn_plus(), chrec_dont_know, CHREC_LEFT, CHREC_RIGHT, compute_overlap_steps_for_affine_1_2(), compute_overlap_steps_for_affine_univar(), conflict_fn(), conflict_fn_not_known(), dump_file, dump_flags, get_chrec_loop(), int_cst_value(), integer_zero_node, integer_zerop(), max_stmt_executions_int(), MIN, and TDF_DETAILS.

Referenced by analyze_subscript_affine_affine(), and compute_overlap_steps_for_affine_1_2().

compute_overlap_steps_for_affine_univar()

void compute_overlap_steps_for_affine_univar ( HOST_WIDE_INT niter, HOST_WIDE_INT step_a, HOST_WIDE_INT step_b, affine_fn * overlaps_a, affine_fn * overlaps_b, tree * last_conflicts, int dim )

static

Solves the special case of the Diophantine equation:
| {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)

Computes the descriptions OVERLAPS_A and OVERLAPS_B.  NITER is the
number of iterations that loops X and Y run.  The overlaps will be
constructed as evolutions in dimension DIM.   

References affine_fn_cst(), affine_fn_univar(), build_int_cst(), chrec_dont_know, compute_overlap_steps_for_affine_univar(), FLOOR_DIV, gcd(), integer_type_node, integer_zero_node, and MIN.

Referenced by analyze_subscript_affine_affine(), compute_overlap_steps_for_affine_1_2(), and compute_overlap_steps_for_affine_univar().

compute_subscript_distance()

void compute_subscript_distance ( struct data_dependence_relation * ddr )

static

Determine for each subscript in the data dependence relation DDR
the distance.   

References affine_fn_free(), affine_fn_minus(), affine_function_base(), affine_function_constant_p(), chrec_dont_know, common_affine_function(), compute_subscript_distance(), DDR_ARE_DEPENDENT, DDR_NUM_SUBSCRIPTS, DDR_SUBSCRIPT, i, NULL_TREE, SUB_CONFLICTS_IN_A, SUB_CONFLICTS_IN_B, and SUB_DISTANCE.

Referenced by build_classic_dist_vector(), compute_subscript_distance(), and subscript_dependence_tester().

conflict_fn()

conflict_function * conflict_fn ( unsigned n, ... )

static

Creates a conflict function with N dimensions.  The affine functions
in each dimension follow.   

References ap, conflict_fn(), conflict_function::fns, gcc_assert, i, MAX_DIM, and conflict_function::n.

Referenced by analyze_miv_subscript(), analyze_overlapping_iterations(), analyze_siv_subscript_cst_affine(), analyze_subscript_affine_affine(), analyze_ziv_subscript(), compute_overlap_steps_for_affine_1_2(), and conflict_fn().

conflict_fn_no_dependence()

conflict_function * conflict_fn_no_dependence ( void )

static

Returns the conflict function for "independent".   

References conflict_fn_no_dependence(), conflict_function::n, and NO_DEPENDENCE.

Referenced by analyze_miv_subscript(), analyze_siv_subscript_cst_affine(), analyze_subscript_affine_affine(), analyze_ziv_subscript(), and conflict_fn_no_dependence().

conflict_fn_not_known()

conflict_function * conflict_fn_not_known ( void )

static

Returns the conflict function for "unknown".   

References conflict_fn_not_known(), conflict_function::n, and NOT_KNOWN.

Referenced by analyze_miv_subscript(), analyze_overlapping_iterations(), analyze_siv_subscript(), analyze_siv_subscript_cst_affine(), analyze_subscript_affine_affine(), analyze_ziv_subscript(), compute_overlap_steps_for_affine_1_2(), conflict_fn_not_known(), and initialize_data_dependence_relation().

contains_ssa_ref_p()

bool contains_ssa_ref_p ( tree ref )

static

Returns true if the reference REF contains a SSA index.  

References contains_ssa_ref_p(), contains_ssa_ref_p_1(), and for_each_index().

Referenced by contains_ssa_ref_p(), and dr_may_alias_p().

contains_ssa_ref_p_1()

bool contains_ssa_ref_p_1 ( tree , tree * idx, void * data )

static

Helper for contains_ssa_ref_p.   

References contains_ssa_ref_p_1(), and TREE_CODE.

Referenced by contains_ssa_ref_p(), and contains_ssa_ref_p_1().

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 create_data_ref(), DR_ACCESS_FN, dr_analyze_alias(), dr_analyze_indices(), dr_analyze_innermost(), DR_BASE_ADDRESS, DR_BASE_ALIGNMENT, DR_BASE_MISALIGNMENT, DR_BASE_OBJECT, DR_INIT, DR_INNERMOST, DR_IS_CONDITIONAL_IN_STMT, DR_IS_READ, DR_NUM_DIMENSIONS, DR_OFFSET, DR_OFFSET_ALIGNMENT, DR_REF, DR_STEP, DR_STEP_ALIGNMENT, DR_STMT, dump_file, dump_flags, i, data_reference::indices, data_reference::is_conditional_in_stmt, data_reference::is_read, NULL, print_generic_expr(), print_generic_stmt(), data_reference::stmt, TDF_DETAILS, and TDF_SLIM.

Referenced by create_data_ref(), debug_data_dependence_relation(), determine_loop_nest_reuse(), dse_classify_store(), find_data_references_in_stmt(), graphite_find_data_references_in_stmt(), vect_find_stmt_data_reference(), and vect_slp_analyze_instance_dependence().

create_ifn_alias_checks()

bool create_ifn_alias_checks ( tree * cond_expr, const dr_with_seg_len_pair_t & alias_pair )

static

A subroutine of create_intersect_range_checks, with a subset of the
same arguments.  Try to use IFN_CHECK_RAW_PTRS and IFN_CHECK_WAR_PTRS
to optimize cases in which the references form a simple RAW, WAR or
WAR dependence.   

References dr_with_seg_len::access_size, dr_with_seg_len::align, boolean_type_node, build_call_expr_internal_loc(), create_ifn_alias_checks(), dr_with_seg_len::dr, DR_ALIAS_RAW, DR_ALIAS_WAR, DR_ALIAS_WAW, DR_BASE_ADDRESS, DR_INIT, DR_OFFSET, DR_STEP, dump_enabled_p(), dump_printf(), fold_build_pointer_plus, internal_check_ptrs_fn_supported_p(), MIN, MSG_NOTE, operand_equal_p(), poly_int_tree_p(), dr_with_seg_len::seg_len, size_int, tree_fits_uhwi_p(), tree_to_uhwi(), TREE_TYPE, and UNKNOWN_LOCATION.

Referenced by create_ifn_alias_checks(), and create_intersect_range_checks().

create_intersect_range_checks()

void create_intersect_range_checks ( class loop * loop, tree * cond_expr, const dr_with_seg_len_pair_t & alias_pair )

static

Generate a runtime condition that is true if ALIAS_PAIR is free of aliases,
storing the condition in *COND_EXPR.  The fallback is to generate a
a test that the two accesses do not overlap:

  end_a <= start_b || end_b <= start_a.   

References dr_with_seg_len::align, boolean_type_node, create_ifn_alias_checks(), create_intersect_range_checks(), create_intersect_range_checks_index(), create_waw_or_war_checks(), dr_with_seg_len::dr, DR_STEP, dump_enabled_p(), dump_printf(), fold_build2, get_segment_min_max(), MSG_NOTE, NULL_TREE, and TREE_CODE.

Referenced by create_intersect_range_checks(), and create_runtime_alias_checks().

create_intersect_range_checks_index()

bool create_intersect_range_checks_index ( class loop * loop, tree * cond_expr, const dr_with_seg_len_pair_t & alias_pair )

static

Try to generate a runtime condition that is true if ALIAS_PAIR is
free of aliases, using a condition based on index values instead
of a condition based on addresses.  Return true on success,
storing the condition in *COND_EXPR.

This can only be done if the two data references in ALIAS_PAIR access
the same array object and the index is the only difference.  For example,
if the two data references are DR_A and DR_B:

                    DR_A                           DR_B
   data-ref         arr[i]                         arr[j]
   base_object      arr                            arr
   index            {i_0, +, 1}_loop               {j_0, +, 1}_loop

The addresses and their index are like:

     |<- ADDR_A    ->|          |<- ADDR_B    ->|
  ------------------------------------------------------->
     |   |   |   |   |          |   |   |   |   |
  ------------------------------------------------------->
     i_0 ...         i_0+4      j_0 ...         j_0+4

We can create expression based on index rather than address:

  (unsigned) (i_0 - j_0 + 3) <= 6

i.e. the indices are less than 4 apart.

Note evolution step of index needs to be considered in comparison.   

References dr_with_seg_len::access_size, boolean_type_node, CHREC_LEFT, CHREC_RIGHT, CHREC_VARIABLE, create_intersect_range_checks_index(), dr_with_seg_len::dr, DR_ACCESS_FN, DR_ALIAS_MIXED_STEPS, DR_ALIAS_WAR, DR_ALIAS_WAW, DR_BASE_OBJECT, DR_NUM_DIMENSIONS, DR_STEP, dump_enabled_p(), dump_printf(), wi::fits_to_tree_p(), fold_build2, fold_convert, gcc_assert, i, integer_zerop(), known_ge, MSG_NOTE, loop::num, operand_equal_p(), poly_int_tree_p(), dr_with_seg_len::seg_len, SIGNED, size_zero_node, wi::to_offset(), wi::to_poly_wide(), wi::to_wide(), TREE_CODE, tree_fits_shwi_p(), tree_int_cst_compare(), tree_int_cst_sign_bit(), tree_to_shwi(), TREE_TYPE, types_compatible_p(), unsigned_type_for(), and wide_int_to_tree().

Referenced by create_intersect_range_checks(), and create_intersect_range_checks_index().

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(), create_runtime_alias_checks(), DR_REF, dump_enabled_p(), dump_printf(), fold_build2, gcc_assert, and MSG_NOTE.

Referenced by create_runtime_alias_checks(), vect_create_cond_for_alias_checks(), and version_loop_by_alias_check().

create_waw_or_war_checks()

bool create_waw_or_war_checks ( tree * cond_expr, const dr_with_seg_len_pair_t & alias_pair )

static

A subroutine of create_intersect_range_checks, with a subset of the
same arguments.  Try to optimize cases in which the second access
is a write and in which some overlap is valid.   

References dr_with_seg_len::access_size, dr_with_seg_len::align, boolean_type_node, build1(), CONSTANT_CLASS_P, create_waw_or_war_checks(), dr_with_seg_len::dr, DR_ALIAS_WAR, DR_ALIAS_WAW, DR_BASE_ADDRESS, dr_direction_indicator(), DR_INIT, DR_OFFSET, DR_STEP, dump_enabled_p(), dump_printf(), fold_build2, fold_build3, fold_build_pointer_plus, fold_convert, MIN, MSG_NOTE, operand_equal_p(), rewrite_to_non_trapping_overflow(), dr_with_seg_len::seg_len, size_int, size_zero_node, sizetype, ssize_int, ssizetype, TREE_TYPE, and TYPE_PRECISION.

Referenced by create_intersect_range_checks(), and create_waw_or_war_checks().

data_ref_compare_tree()

int data_ref_compare_tree	(	tree	t1,
		tree	t2 )

A helper function computes order between two tree expressions T1 and T2.
This is used in comparator functions sorting objects based on the order
of tree expressions.  The function returns -1, 0, or 1.   

References CONVERT_EXPR_P, data_ref_compare_tree(), DECL_UID, gcc_unreachable, i, IS_EXPR_CODE_CLASS, NULL, POLY_INT_CST_P, SSA_NAME_VERSION, STRIP_USELESS_TYPE_CONVERSION, tcc_declaration, wi::to_poly_widest(), TREE_CODE, TREE_CODE_CLASS, tree_int_cst_compare(), TREE_OPERAND, TREE_OPERAND_LENGTH, TREE_STRING_LENGTH, and TREE_STRING_POINTER.

Referenced by comp_dr_with_seg_len_pair(), data_ref_compare_tree(), dr_align_group_sort_cmp(), dr_group_sort_cmp(), operator==(), loop_distribution::pg_add_dependence_edges(), prune_runtime_alias_test_list(), and vect_analyze_data_ref_accesses().

debug() [1/6]

DEBUG_FUNCTION void debug

(

data_reference &

ref

)

Unified dump function for a DATA_REFERENCE structure.   

References debug, and dump_data_reference().

debug() [2/6]

DEBUG_FUNCTION void debug

(

data_reference *

ptr

)

References debug.

debug() [3/6]

DEBUG_FUNCTION void debug

(

vec< data_reference_p > &

ref

)

Unified dump into FILE all the data references from DATAREFS.   

References debug, and dump_data_references().

debug() [4/6]

DEBUG_FUNCTION void debug

(

vec< data_reference_p > *

ptr

)

References debug.

debug() [5/6]

DEBUG_FUNCTION void debug

(

vec< ddr_p > &

ref

)

References debug, and dump_data_dependence_relations().

debug() [6/6]

DEBUG_FUNCTION void debug

(

vec< ddr_p > *

ptr

)

References debug.

debug_data_dependence_relation()

DEBUG_FUNCTION void debug_data_dependence_relation

(

const struct data_dependence_relation *

ddr

)

Debug version.   

References debug_data_dependence_relation(), and dump_data_dependence_relation().

Referenced by debug_data_dependence_relation(), and debug_data_dependence_relation().

debug_data_dependence_relations()

DEBUG_FUNCTION void debug_data_dependence_relations

(

vec< ddr_p >

ddrs

)

Dump to STDERR all the dependence relations from DDRS.   

References debug_data_dependence_relations(), and dump_data_dependence_relations().

Referenced by debug_data_dependence_relation(), and debug_data_dependence_relations().

debug_data_reference()

DEBUG_FUNCTION void debug_data_reference

(

struct data_reference *

dr

)

Print to STDERR the data_reference DR.   

References debug_data_reference(), and dump_data_reference().

Referenced by debug_data_reference().

debug_data_references()

DEBUG_FUNCTION void debug_data_references

(

vec< data_reference_p >

datarefs

)

Dump into STDERR all the data references from DATAREFS.   

References debug_data_references(), and dump_data_references().

Referenced by debug_data_references().

debug_ddrs()

DEBUG_FUNCTION void debug_ddrs

(

vec< ddr_p >

ddrs

)

References debug_ddrs(), and dump_ddrs().

Referenced by debug_ddrs().

dir_from_dist()

enum data_dependence_direction dir_from_dist ( int dist )

inlinestatic

Return the direction for a given distance.
FIXME: Computing dir this way is suboptimal, since dir can catch
cases that dist is unable to represent.   

References dir_equal, dir_from_dist(), dir_negative, and dir_positive.

Referenced by build_classic_dir_vector(), and dir_from_dist().

dr_alignment()

unsigned int dr_alignment

(

innermost_loop_behavior *

drb

)

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

References innermost_loop_behavior::base_alignment, innermost_loop_behavior::base_misalignment, dr_alignment(), innermost_loop_behavior::init, integer_zerop(), MIN, innermost_loop_behavior::offset, innermost_loop_behavior::offset_alignment, innermost_loop_behavior::step, innermost_loop_behavior::step_alignment, and TREE_INT_CST_LOW.

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

dr_analyze_alias()

void dr_analyze_alias ( struct data_reference * dr )

static

Extracts the alias analysis information from the memory reference DR.   

References dr_analyze_alias(), DR_PTR_INFO, DR_REF, get_base_address(), INDIRECT_REF_P, SSA_NAME_PTR_INFO, TREE_CODE, and TREE_OPERAND.

Referenced by create_data_ref(), and dr_analyze_alias().

dr_analyze_indices()

void dr_analyze_indices ( struct indices * dri, tree ref, edge nest, loop_p loop )

static

Determines the base object and the list of indices of memory reference
DR, analyzed in LOOP and instantiated before NEST.   

References indices::access_fns, AGGREGATE_TYPE_P, analyze_scalar_evolution(), indices::base_object, bitsize_int, bitsize_zero_node, bitsizetype, build2(), build_fold_addr_expr, build_int_cst(), chrec_replace_initial_condition(), component_ref_field_offset(), DECL_FIELD_BIT_OFFSET, DECL_P, dr_analyze_indices(), EXPR_LOCATION, fold_build2_loc(), fold_convert, handled_component_p(), initial_condition(), instantiate_scev(), integer_one_node, integer_zero_node, integer_zerop(), wi::mod_trunc(), MR_DEPENDENCE_BASE, MR_DEPENDENCE_CLIQUE, reference_alias_ptr_type(), SIGNED, size_binop, split_constant_offset(), ssizetype, STRIP_NOPS, STRIP_USELESS_TYPE_CONVERSION, wi::to_wide(), TREE_CODE, TREE_OPERAND, TREE_TYPE, TYPE_SIZE_UNIT, indices::unconstrained_base, vNULL, and wide_int_to_tree().

Referenced by create_data_ref(), dr_analyze_indices(), and initialize_data_dependence_relation().

dr_analyze_innermost()

opt_result dr_analyze_innermost	(	innermost_loop_behavior *	drb,
		tree	ref,
		class loop *	loop,
		const gimple *	stmt )

Analyze the behavior of memory reference REF within STMT.
There are two modes:

- BB analysis.  In this case we simply split the address into base,
  init and offset components, without reference to any containing loop.
  The resulting base and offset are general expressions and they can
  vary arbitrarily from one iteration of the containing loop to the next.
  The step is always zero.

- loop analysis.  In this case we analyze the reference both wrt LOOP
  and on the basis that the reference occurs (is "used") in LOOP;
  see the comment above analyze_scalar_evolution_in_loop for more
  information about this distinction.  The base, init, offset and
  step fields are all invariant in LOOP.

Perform BB analysis if LOOP is null, or if LOOP is the function's
dummy outermost loop.  In other cases perform loop analysis.

Return true if the analysis succeeded and store the results in DRB if so.
BB analysis can only fail for bitfield or reversed-storage accesses.   

References affine_iv::base, innermost_loop_behavior::base_address, innermost_loop_behavior::base_alignment, innermost_loop_behavior::base_misalignment, build_fold_addr_expr, canonicalize_base_object_address(), dr_analyze_innermost(), dump_file, dump_flags, opt_result::failure_at(), fold_convert, poly_int< N, C >::force_shwi(), gcc_assert, get_inner_reference(), get_object_alignment_1(), get_pointer_alignment_1(), highest_pow2_factor(), innermost_loop_behavior::init, integer_zerop(), may_be_nonaddressable_p(), mem_ref_offset(), affine_iv::no_overflow, NULL_TREE, loop::num, innermost_loop_behavior::offset, innermost_loop_behavior::offset_alignment, simple_iv(), size_binop, sizetype, split_constant_offset(), ssize_int, ssizetype, affine_iv::step, innermost_loop_behavior::step, innermost_loop_behavior::step_alignment, opt_result::success(), TDF_DETAILS, TREE_CODE, TREE_INT_CST_LOW, TREE_OPERAND, and wide_int_to_tree().

Referenced by create_data_ref(), dr_analyze_innermost(), 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_direction_indicator(), and dr_step_indicator().

Referenced by create_waw_or_war_checks(), dr_direction_indicator(), 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_p(), dr_equal_offsets_p1(), and DR_OFFSET.

Referenced by dr_equal_offsets_p().

dr_equal_offsets_p1()

bool dr_equal_offsets_p1 ( tree offset1, tree offset2 )

static

Check if OFFSET1 and OFFSET2 (DR_OFFSETs of some data-refs) are identical
expressions.   

References BINARY_CLASS_P, dr_equal_offsets_p1(), STRIP_NOPS, TREE_CODE, TREE_OPERAND, and UNARY_CLASS_P.

Referenced by dr_equal_offsets_p(), and dr_equal_offsets_p1().

dr_known_forward_stride_p()

bool dr_known_forward_stride_p

(

struct data_reference *

dr

)

Return true if DR is known to have a nonnegative (but possibly zero)
step.   

References boolean_type_node, dr_direction_indicator(), dr_known_forward_stride_p(), fold_binary, fold_convert, integer_zerop(), ssize_int, and ssizetype.

Referenced by dr_known_forward_stride_p(), and vect_prune_runtime_alias_test_list().

dr_may_alias_p()

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

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

References a, aff_comb_cannot_overlap_p(), aff_combination_add(), aff_combination_scale(), alias_sets_conflict_p(), b, build_fold_addr_expr, contains_ssa_ref_p(), DR_BASE_ADDRESS, DR_BASE_OBJECT, DR_INIT, DR_IS_READ, DR_IS_WRITE, dr_may_alias_p(), DR_OFFSET, DR_PTR_INFO, DR_REF, DR_STEP, DR_UNCONSTRAINED_BASE, gcc_assert, get_alias_set(), get_inner_reference_aff(), handled_component_p(), integer_zerop(), MR_DEPENDENCE_BASE, MR_DEPENDENCE_CLIQUE, operand_equal_p(), loop::owned_clique, poly_int_tree_p(), ptr_info_def::pt, pt_solutions_intersect(), 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 dr_may_alias_p(), dse_classify_store(), initialize_data_dependence_relation(), and vect_analyze_early_break_dependences().

dr_step_indicator()

tree dr_step_indicator ( struct data_reference * dr, int useful_min )

static

Common routine implementing both dr_direction_indicator and
dr_zero_step_indicator.  Return USEFUL_MIN if the indicator is known
to be >= USEFUL_MIN and -1 if the indicator is known to be negative.
Return the step as the indicator otherwise.   

References cfun, CONVERT_EXPR_P, DR_STEP, dr_step_indicator(), fold_convert, wi::ge_p(), wi::ges_p(), get_range_query(), INTEGRAL_TYPE_P, wi::les_p(), irange::lower_bound(), wi::lt_p(), NULL_TREE, ssize_int, ssizetype, STRIP_NOPS, wi::to_wide(), wi::to_widest(), TREE_CODE, tree_int_cst_sgn(), TREE_OPERAND, TREE_TYPE, TYPE_MAX_VALUE, TYPE_MIN_VALUE, TYPE_SIGN, vrange::undefined_p(), and irange::upper_bound().

Referenced by dr_direction_indicator(), dr_step_indicator(), and dr_zero_step_indicator().

dr_zero_step_indicator()

tree dr_zero_step_indicator

(

struct data_reference *

dr

)

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

References dr_step_indicator(), and dr_zero_step_indicator().

Referenced by dr_zero_step_indicator(), and vect_analyze_data_ref_dependence().

dump_affine_function()

DEBUG_FUNCTION void dump_affine_function	(	FILE *	outf,
		affine_fn	fn )

Dumps the affine function described by FN to the file OUTF.   

References dump_affine_function(), i, print_generic_expr(), and TDF_SLIM.

Referenced by dump_affine_function(), and dump_conflict_function().

dump_alias_pair()

void dump_alias_pair ( dr_with_seg_len_pair_t * alias_pair, const char * indent )

static

Dump information about ALIAS_PAIR, indenting each line by INDENT.   

References DR_ALIAS_ARBITRARY, DR_ALIAS_MIXED_STEPS, DR_ALIAS_RAW, DR_ALIAS_SWAPPED, DR_ALIAS_UNSWAPPED, DR_ALIAS_WAR, DR_ALIAS_WAW, DR_REF, dump_alias_pair(), dump_dec(), dump_printf(), MSG_NOTE, and operand_equal_p().

Referenced by dump_alias_pair(), and prune_runtime_alias_test_list().

dump_conflict_function()

DEBUG_FUNCTION void dump_conflict_function	(	FILE *	outf,
		conflict_function *	cf )

Dumps the conflict function CF to the file OUTF.   

References dump_affine_function(), dump_conflict_function(), conflict_function::fns, i, conflict_function::n, NO_DEPENDENCE, and NOT_KNOWN.

Referenced by analyze_overlapping_iterations(), analyze_subscript_affine_affine(), dump_conflict_function(), and dump_subscript().

dump_data_dependence_relation()

DEBUG_FUNCTION void dump_data_dependence_relation	(	FILE *	outf,
		const data_dependence_relation *	ddr )

Dump function for a DATA_DEPENDENCE_RELATION structure.   

References chrec_dont_know, chrec_known, DDR_A, DDR_ARE_DEPENDENT, DDR_B, DDR_DIR_VECT, DDR_DIST_VECT, DDR_LOOP_NEST, DDR_NB_LOOPS, DDR_NUM_DIR_VECTS, DDR_NUM_DIST_VECTS, DDR_SUBSCRIPTS, dump_data_dependence_relation(), dump_data_reference(), dump_subscript(), FOR_EACH_VEC_ELT, i, NULL_TREE, loop::num, print_direction_vector(), print_generic_stmt(), print_lambda_vector(), and SUB_ACCESS_FN.

Referenced by debug_data_dependence_relation(), dump_data_dependence_relation(), dump_data_dependence_relations(), and dump_ddrs().

dump_data_dependence_relations()

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

Dump into FILE all the dependence relations from DDRS.   

References dump_data_dependence_relation(), and dump_data_dependence_relations().

Referenced by loop_distribution::break_alias_scc_partitions(), debug(), debug_data_dependence_relation(), debug_data_dependence_relations(), dump_data_dependence_relations(), loop_parallel_p(), tree_loop_unroll_and_jam(), and pcom_worker::tree_predictive_commoning_loop().

dump_data_reference()

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

Dump function for a DATA_REFERENCE structure.   

References DR_ACCESS_FN, DR_BASE_OBJECT, DR_NUM_DIMENSIONS, DR_REF, DR_STMT, dump_data_reference(), gimple_bb(), i, print_generic_stmt(), and print_gimple_stmt().

Referenced by compute_affine_dependence(), debug(), debug_data_reference(), dump_data_dependence_relation(), dump_data_reference(), and dump_data_references().

dump_data_references()

void dump_data_references ( FILE * file, vec< data_reference_p > datarefs )

static

Dump into FILE all the data references from DATAREFS.   

References dump_data_reference(), and dump_data_references().

Referenced by debug(), debug_data_references(), and dump_data_references().

dump_ddrs()

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

Dumps the data dependence relations DDRS in FILE.   

References dump_data_dependence_relation(), and dump_ddrs().

Referenced by debug_ddrs(), and dump_ddrs().

dump_dist_dir_vectors()

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

Dumps the distance and direction vectors in FILE.  DDRS contains
the dependence relations, and VECT_SIZE is the size of the
dependence vectors, or in other words the number of loops in the
considered nest.   

References DDR_AFFINE_P, DDR_ARE_DEPENDENT, DDR_DIR_VECTS, DDR_DIST_VECTS, DDR_NB_LOOPS, dump_dist_dir_vectors(), NULL_TREE, print_direction_vector(), and print_lambda_vector().

Referenced by dump_dist_dir_vectors().

dump_subscript()

DEBUG_FUNCTION void dump_subscript	(	FILE *	outf,
		struct subscript *	subscript )

Dump function for a SUBSCRIPT structure.   

References CF_NONTRIVIAL_P, dump_conflict_function(), dump_subscript(), print_generic_expr(), SUB_CONFLICTS_IN_A, SUB_CONFLICTS_IN_B, SUB_DISTANCE, and SUB_LAST_CONFLICT.

Referenced by dump_data_dependence_relation(), and dump_subscript().

finalize_ddr_dependent()

void finalize_ddr_dependent ( struct data_dependence_relation * ddr, tree chrec )

inlinestatic

Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
description.   

References DDR_ARE_DEPENDENT, DDR_SUBSCRIPTS, finalize_ddr_dependent(), and free_subscripts().

Referenced by build_classic_dist_vector_1(), compute_affine_dependence(), finalize_ddr_dependent(), and subscript_dependence_tester_1().

find_data_references_in_bb()

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

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

References chrec_dont_know, find_data_references_in_bb(), find_data_references_in_stmt(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_stmt(), and NULL_TREE.

Referenced by compute_self_dependence(), cond_if_else_store_replacement(), find_data_references_in_bb(), 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(), find_data_references_in_loop(), free(), get_loop_body_in_dom_order(), i, NULL_TREE, and loop::num_nodes.

Referenced by compute_data_dependences_for_loop(), debug_data_dependence_relation(), find_data_references_in_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(), find_data_references_in_stmt(), gcc_assert, get_references_in_stmt(), loop_containing_stmt(), loop_preheader_edge(), NULL, and opt_result::success().

Referenced by loop_distribution::create_rdg_vertices(), debug_data_dependence_relation(), find_data_references_in_bb(), find_data_references_in_stmt(), 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(), find_loop_nest_1(), and loop::inner.

Referenced by compute_data_dependences_for_loop(), debug_data_dependence_relation(), determine_loop_nest_reuse(), loop_distribution::distribute_loop(), find_loop_nest(), and vect_analyze_loop().

find_loop_nest_1()

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

static

Recursive helper function.   

References find_loop_nest_1(), loop::inner, and loop::next.

Referenced by find_loop_nest(), and find_loop_nest_1().

free_conflict_function()

void free_conflict_function ( conflict_function * f )

static

Frees memory used by the conflict function F.   

References affine_fn_free(), CF_NONTRIVIAL_P, conflict_function::fns, free(), free_conflict_function(), i, and conflict_function::n.

Referenced by analyze_siv_subscript_cst_affine(), free_conflict_function(), free_subscripts(), and subscript_dependence_tester_1().

free_data_ref()

void free_data_ref

(

data_reference_p

dr

)

Frees data reference DR.   

References indices::access_fns, data_reference::alt_indices, indices::base_object, DR_ACCESS_FNS, free(), and free_data_ref().

Referenced by debug_data_dependence_relation(), dse_classify_store(), free_data_ref(), free_data_refs(), tree_if_conversion(), vect_find_stmt_data_reference(), and vect_slp_analyze_instance_dependence().

free_data_refs()

void free_data_refs

(

vec< data_reference_p > &

datarefs

)

Free the memory used by the data references from DATAREFS.   

References free_data_ref(), and free_data_refs().

Referenced by cond_if_else_store_replacement(), debug_data_dependence_relation(), determine_loop_nest_reuse(), loop_distribution::distribute_loop(), loop_distribution::execute(), free_data_refs(), free_data_refs_with_aux(), loop_parallel_p(), tree_loop_unroll_and_jam(), pcom_worker::~pcom_worker(), and vec_info_shared::~vec_info_shared().

free_dependence_relation()

void free_dependence_relation

(

struct data_dependence_relation *

ddr

)

Free the memory used by a data dependence relation DDR.   

References DDR_DIR_VECTS, DDR_DIST_VECTS, DDR_SUBSCRIPTS, free(), free_dependence_relation(), free_subscripts(), and NULL.

Referenced by debug_data_dependence_relation(), loop_distribution::distribute_loop(), free_dependence_relation(), 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

)

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

References free_dependence_relation(), and free_dependence_relations().

Referenced by cond_if_else_store_replacement(), debug_data_dependence_relation(), determine_loop_nest_reuse(), free_dependence_relations(), loop_parallel_p(), tree_loop_unroll_and_jam(), pcom_worker::~pcom_worker(), and vec_info_shared::~vec_info_shared().

free_subscripts()

void free_subscripts ( vec< subscript_p > subscripts )

static

Frees memory used by SUBSCRIPTS.   

References free(), free_conflict_function(), free_subscripts(), and data_dependence_relation::subscripts.

Referenced by finalize_ddr_dependent(), free_dependence_relation(), and free_subscripts().

gcd_of_steps_may_divide_p()

bool gcd_of_steps_may_divide_p ( const_tree chrec, const_tree cst )

static

Returns false if we can prove that the greatest common divisor of the steps
of CHREC does not divide CST, false otherwise.   

References CHREC_LEFT, CHREC_RIGHT, gcd(), gcd_of_steps_may_divide_p(), TREE_CODE, tree_fits_shwi_p(), and tree_to_shwi().

Referenced by analyze_miv_subscript(), and gcd_of_steps_may_divide_p().

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

Referenced by compute_self_dependence(), get_base_for_alignment(), and vect_compute_data_ref_alignment().

get_base_for_alignment_1()

tree get_base_for_alignment_1 ( tree base, unsigned int * alignment_out )

static

If BASE is a pointer-typed SSA name, try to find the object that it
is based on.  Return this object X on success and store the alignment
in bytes of BASE - &X in *ALIGNMENT_OUT.   

References analyze_scalar_evolution(), CHREC_LEFT, CHREC_RIGHT, fold_indirect_ref_1(), get_base_for_alignment_1(), get_inner_reference(), highest_pow2_factor(), loop_containing_stmt(), MAX_OFILE_ALIGNMENT, MIN, NULL, NULL_TREE, POINTER_TYPE_P, data_reference::ref, SSA_NAME_DEF_STMT, TREE_CODE, tree_contains_chrecs(), TREE_TYPE, and UNKNOWN_LOCATION.

Referenced by get_base_for_alignment(), and get_base_for_alignment_1().

get_references_in_stmt()

bool get_references_in_stmt ( gimple * stmt, vec< data_ref_loc, va_heap > * references )

static

Stores the locations of memory references in STMT to REFERENCES.  Returns
true if STMT clobbers memory, false otherwise.   

References as_a(), build_aligned_type(), build_int_cst(), DECL_P, ECF_CONST, flags_from_decl_or_type(), fold_build2, gcc_assert, gcc_fallthrough, get_base_address(), get_references_in_stmt(), gimple_asm_volatile_p(), gimple_assign_lhs(), gimple_assign_rhs1(), gimple_bb(), gimple_call_addr_fndecl(), gimple_call_arg(), gimple_call_builtin_p(), gimple_call_flags(), gimple_call_internal_fn(), gimple_call_internal_p(), gimple_call_lhs(), gimple_call_num_args(), gimple_vuse(), i, data_ref_loc::is_conditional_in_stmt, is_gimple_min_invariant(), data_ref_loc::is_read, basic_block_def::loop_father, NULL, NULL_TREE, data_ref_loc::ref, REFERENCE_CLASS_P, loop::simduid, SSA_NAME_VAR, TREE_CODE, tree_to_shwi(), TREE_TYPE, and TYPE_ALIGN.

Referenced by find_data_references_in_stmt(), get_references_in_stmt(), graphite_find_data_references_in_stmt(), and loop_nest_has_data_refs().

get_segment_min_max()

void get_segment_min_max ( const dr_with_seg_len & d, tree * seg_min_out, tree * seg_max_out, HOST_WIDE_INT align )

static

If ALIGN is nonzero, set up *SEQ_MIN_OUT and *SEQ_MAX_OUT so that for
every address ADDR accessed by D:

  *SEQ_MIN_OUT <= ADDR (== ADDR & -ALIGN) <= *SEQ_MAX_OUT

In this case, every element accessed by D is aligned to at least
ALIGN bytes.

If ALIGN is zero then instead set *SEG_MAX_OUT so that:

  *SEQ_MIN_OUT <= ADDR < *SEQ_MAX_OUT.   

References dr_with_seg_len::access_size, boolean_type_node, dr_with_seg_len::dr, DR_BASE_ADDRESS, dr_direction_indicator(), DR_INIT, DR_OFFSET, fold_build2, fold_build3, fold_build_pointer_plus, fold_convert, get_segment_min_max(), rewrite_to_non_trapping_overflow(), dr_with_seg_len::seg_len, size_int, size_zero_node, sizetype, ssize_int, and ssizetype.

Referenced by create_intersect_range_checks(), and get_segment_min_max().

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

Referenced by debug_data_dependence_relation(), and graphite_find_data_references_in_stmt().

initialize_data_dependence_relation() [1/2]

struct data_dependence_relation * initialize_data_dependence_relation	(	struct data_dependence_relation *	res,
		vec< loop_p >	loop_nest,
		bool	use_alt_indices )

Initialize a data dependence relation RES in LOOP_NEST.  USE_ALT_INDICES
is true when the main indices of A and B were not comparable so we try again
with alternate indices computed on an indirect reference.   

References a, access_fn_component_p(), access_fn_components_comparable_p(), indices::access_fns, b, indices::base_object, base_supports_access_fn_components_p(), build1(), build2(), build_int_cst(), chrec_dont_know, COMPLETE_TYPE_P, conflict_fn_not_known(), DDR_A, DDR_AFFINE_P, DDR_ARE_DEPENDENT, DDR_B, DDR_COULD_BE_INDEPENDENT_P, DDR_LOOP_NEST, DDR_OBJECT_A, DDR_OBJECT_B, DDR_SELF_REFERENCE, DDR_SUBSCRIPTS, dr_analyze_indices(), DR_REF, DR_STMT, gcc_assert, gcc_checking_assert, i, initialize_data_dependence_relation(), loop_containing_stmt(), loop_preheader_edge(), may_be_nonaddressable_p(), NULL_TREE, object_address_invariant_in_loop_p(), OEP_ADDRESS_OF, operand_equal_p(), ptr_type_node, ref_contains_union_access_p(), reference_alias_ptr_type(), SUB_ACCESS_FN, SUB_CONFLICTS_IN_A, SUB_CONFLICTS_IN_B, SUB_DISTANCE, SUB_LAST_CONFLICT, TREE_CODE, tree_fits_uhwi_p(), TREE_OPERAND, tree_to_uhwi(), TREE_TYPE, TYPE_SIZE, TYPE_SIZE_UNIT, types_compatible_p(), and indices::unconstrained_base.

Referenced by compute_all_dependences(), debug_data_dependence_relation(), loop_distribution::get_data_dependence(), initialize_data_dependence_relation(), initialize_data_dependence_relation(), vect_slp_analyze_load_dependences(), and vect_slp_analyze_store_dependences().

initialize_data_dependence_relation() [2/2]

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

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

References a, b, chrec_dont_know, chrec_known, DDR_A, DDR_ARE_DEPENDENT, DDR_B, DDR_DIR_VECTS, DDR_DIST_VECTS, DDR_LOOP_NEST, DDR_SUBSCRIPTS, dr_may_alias_p(), initialize_data_dependence_relation(), data_dependence_relation::loop_nest, and NULL.

initialize_matrix_A()

tree initialize_matrix_A ( lambda_matrix A, tree chrec, unsigned index, int mult )

static

Helper recursive function for initializing the matrix A.  Returns
the initial value of CHREC.   

References build_int_cst(), CASE_CONVERT, chrec_convert(), chrec_dont_know, chrec_fold_op(), CHREC_LEFT, CHREC_RIGHT, chrec_type(), cst_and_fits_in_hwi(), gcc_assert, gcc_unreachable, HOST_WIDE_INT_MIN, initialize_matrix_A(), int_cst_value(), NULL, NULL_TREE, TREE_CODE, TREE_OPERAND, and TREE_TYPE.

Referenced by analyze_subscript_affine_affine(), and initialize_matrix_A().

insert_innermost_unit_dist_vector()

void insert_innermost_unit_dist_vector ( struct data_dependence_relation * ddr )

static

References DDR_NB_LOOPS, insert_innermost_unit_dist_vector(), lambda_vector_new(), and save_dist_v().

Referenced by add_distance_for_zero_overlaps(), and insert_innermost_unit_dist_vector().

int_divides_p()

bool int_divides_p ( lambda_int a, lambda_int b )

inlinestatic

Returns true iff A divides B.   

References a, b, and int_divides_p().

Referenced by analyze_subscript_affine_affine(), and int_divides_p().

invariant_access_functions()

bool invariant_access_functions ( const struct data_dependence_relation * ddr, int lnum )

static

Return true when the DDR contains only invariant access functions wrto. loop
number LNUM.   

References DDR_SUBSCRIPTS, evolution_function_is_invariant_p(), invariant_access_functions(), and SUB_ACCESS_FN.

Referenced by build_classic_dist_vector(), and invariant_access_functions().

lambda_matrix_copy()

void lambda_matrix_copy ( lambda_matrix mat1, lambda_matrix mat2, int m, int n )

static

Copy the elements of M x N matrix MAT1 to MAT2.   

References i, lambda_matrix_copy(), and lambda_vector_copy().

Referenced by lambda_matrix_copy(), and lambda_matrix_right_hermite().

lambda_matrix_id()

void lambda_matrix_id ( lambda_matrix mat, int size )

static

Store the N x N identity matrix in MAT.   

References i, and lambda_matrix_id().

Referenced by lambda_matrix_id(), and lambda_matrix_right_hermite().

lambda_matrix_right_hermite()

bool lambda_matrix_right_hermite ( lambda_matrix A, int m, int n, lambda_matrix S, lambda_matrix U )

static

Given an M x N integer matrix A, this function determines an M x
M unimodular matrix U, and an M x N echelon matrix S such that
"U.A = S".  This decomposition is also known as "right Hermite".

Ref: Algorithm 2.1 page 33 in "Loop Transformations for
Restructuring Compilers" Utpal Banerjee.   

References a, b, gcc_assert, HOST_WIDE_INT_MIN, i, lambda_matrix_copy(), lambda_matrix_id(), lambda_matrix_right_hermite(), lambda_matrix_row_add(), lambda_vector_first_nz(), and S.

Referenced by analyze_subscript_affine_affine(), and lambda_matrix_right_hermite().

lambda_matrix_row_add()

bool lambda_matrix_row_add ( lambda_matrix mat, int n, int r1, int r2, lambda_int const1 )

static

Add a multiple of row R1 of matrix MAT with N columns to row R2:
R2 = R2 + CONST1 * R1.   

References add_hwi(), HOST_WIDE_INT_MIN, i, lambda_matrix_row_add(), and mul_hwi().

Referenced by lambda_matrix_right_hermite(), and lambda_matrix_row_add().

lambda_matrix_row_negate()

void lambda_matrix_row_negate ( lambda_matrix mat, int n, int r1 )

static

Negate row R1 of matrix MAT which has N columns.   

References lambda_matrix_row_negate(), and lambda_vector_negate().

Referenced by analyze_subscript_affine_affine(), and lambda_matrix_row_negate().

lambda_vector_copy()

void lambda_vector_copy ( lambda_vector vec1, lambda_vector vec2, int size )

static

Copy the elements of vector VEC1 with length SIZE to VEC2.   

References lambda_vector_copy().

Referenced by add_outer_distances(), build_classic_dist_vector(), lambda_matrix_copy(), and lambda_vector_copy().

lambda_vector_equal()

bool lambda_vector_equal ( lambda_vector vec1, lambda_vector vec2, int size )

static

Return true if two vectors are equal.   

References i, and lambda_vector_equal().

Referenced by lambda_vector_equal(), save_dir_v(), and save_dist_v().

lambda_vector_first_nz()

int lambda_vector_first_nz ( lambda_vector vec1, int n, int start )

static

Return the index of the first nonzero element of vector VEC1 between
START and N.  We must have START <= N.
Returns N if VEC1 is the zero vector.   

References lambda_vector_first_nz().

Referenced by build_classic_dist_vector(), lambda_matrix_right_hermite(), and lambda_vector_first_nz().

lambda_vector_mult_const()

void lambda_vector_mult_const ( lambda_vector vec1, lambda_vector vec2, int size, lambda_int const1 )

static

Multiply vector VEC1 of length SIZE by a constant CONST1,
and store the result in VEC2.   

References i, lambda_vector_clear(), and lambda_vector_mult_const().

Referenced by lambda_vector_mult_const(), and lambda_vector_negate().

lambda_vector_negate()

void lambda_vector_negate ( lambda_vector vec1, lambda_vector vec2, int size )

static

Negate vector VEC1 with length SIZE and store it in VEC2.   

References lambda_vector_mult_const(), and lambda_vector_negate().

Referenced by lambda_matrix_row_negate(), and lambda_vector_negate().

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(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_stmt(), i, loop_nest_has_data_refs(), and loop::num_nodes.

Referenced by debug_data_dependence_relation(), and loop_nest_has_data_refs().

max_stmt_executions_tree()

tree max_stmt_executions_tree ( class loop * loop )

static

Similar to max_stmt_executions_int, but returns the bound as a tree,
and only if it fits to the int type.  If this is not the case, or the
bound  on the number of iterations of LOOP could not be derived, returns
chrec_dont_know.   

References chrec_dont_know, wi::fits_to_tree_p(), max_stmt_executions(), max_stmt_executions_tree(), unsigned_type_node, and wide_int_to_tree().

Referenced by analyze_miv_subscript(), and max_stmt_executions_tree().

non_affine_dependence_relation()

void non_affine_dependence_relation ( struct data_dependence_relation * ddr )

inlinestatic

The dependence relation DDR cannot be represented by a distance
vector.   

References DDR_AFFINE_P, dump_file, dump_flags, non_affine_dependence_relation(), and TDF_DETAILS.

Referenced by build_classic_dist_vector_1(), and non_affine_dependence_relation().

nop_conversion_for_offset_p()

bool nop_conversion_for_offset_p ( tree to_type, tree from_type, irange & range )

static

Return true if (sizetype) OP == (sizetype) (TO_TYPE) OP,
given that OP has type FROM_TYPE and range RANGE.  Both TO_TYPE and
FROM_TYPE are integral types.   

References gcc_assert, INTEGRAL_TYPE_P, nop_conversion_for_offset_p(), range_fits_type_p(), sizetype, TYPE_OVERFLOW_TRAPS, TYPE_PRECISION, TYPE_SIGN, and TYPE_UNSIGNED.

Referenced by nop_conversion_for_offset_p(), and split_constant_offset_1().

object_address_invariant_in_loop_p()

bool object_address_invariant_in_loop_p ( const class loop * loop, const_tree obj )

static

Returns true if the address of OBJ is invariant in LOOP.   

References chrec_contains_symbols_defined_in_loop(), handled_component_p(), i, INDIRECT_REF_P, loop::num, object_address_invariant_in_loop_p(), TREE_CODE, and TREE_OPERAND.

Referenced by initialize_data_dependence_relation(), and object_address_invariant_in_loop_p().

operator==()

bool operator== ( const dr_with_seg_len & d1, const dr_with_seg_len & d2 )

static

Operator == between two dr_with_seg_len objects.

This equality operator is used to make sure two data refs
are the same one so that we will consider to combine the
aliasing checks of those two pairs of data dependent data
refs.   

References d1, d2, data_ref_compare_tree(), DR_BASE_ADDRESS, DR_INIT, DR_OFFSET, known_eq, and operand_equal_p().

print_dir_vectors()

DEBUG_FUNCTION void print_dir_vectors	(	FILE *	outf,
		vec< lambda_vector >	dir_vects,
		int	length )

Print a vector of direction vectors.   

References print_dir_vectors(), and print_direction_vector().

Referenced by print_dir_vectors().

print_direction_vector()

DEBUG_FUNCTION void print_direction_vector	(	FILE *	outf,
		lambda_vector	dirv,
		int	length )

Print the classic direction vector DIRV to OUTF.   

References dir_equal, dir_negative, dir_negative_or_equal, dir_positive, dir_positive_or_equal, dir_positive_or_negative, dir_star, and print_direction_vector().

Referenced by dump_data_dependence_relation(), dump_dist_dir_vectors(), print_dir_vectors(), and print_direction_vector().

print_dist_vectors()

DEBUG_FUNCTION void print_dist_vectors	(	FILE *	outf,
		vec< lambda_vector >	dist_vects,
		int	length )

Print a vector of distance vectors.   

References print_dist_vectors(), and print_lambda_vector().

Referenced by print_dist_vectors().

print_lambda_vector()

DEBUG_FUNCTION void print_lambda_vector	(	FILE *	outfile,
		lambda_vector	vector,
		int	n )

Print out a vector VEC of length N to OUTFILE.   

References HOST_WIDE_INT_PRINT_DEC, i, and print_lambda_vector().

Referenced by dump_data_dependence_relation(), dump_dist_dir_vectors(), print_dist_vectors(), print_lambda_vector(), and subscript_dependence_tester().

prune_runtime_alias_test_list()

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

Merge alias checks recorded in ALIAS_PAIRS and remove redundant ones.
FACTOR is number of iterations that each data reference is accessed.

Basically, for each pair of dependent data refs store_ptr_0 & load_ptr_0,
we create an expression:

((store_ptr_0 + store_segment_length_0) <= load_ptr_0)
|| (load_ptr_0 + load_segment_length_0) <= store_ptr_0))

for aliasing checks.  However, in some cases we can decrease the number
of checks by combining two checks into one.  For example, suppose we have
another pair of data refs store_ptr_0 & load_ptr_1, and if the following
condition is satisfied:

load_ptr_0 < load_ptr_1  &&
load_ptr_1 - load_ptr_0 - load_segment_length_0 < store_segment_length_0

(this condition means, in each iteration of vectorized loop, the accessed
memory of store_ptr_0 cannot be between the memory of load_ptr_0 and
load_ptr_1.)

we then can use only the following expression to finish the aliasing checks
between store_ptr_0 & load_ptr_0 and store_ptr_0 & load_ptr_1:

((store_ptr_0 + store_segment_length_0) <= load_ptr_0)
|| (load_ptr_1 + load_segment_length_1 <= store_ptr_0))

Note that we only consider that load_ptr_0 and load_ptr_1 have the same
basic address.   

References dr_with_seg_len::access_size, alias_pairs, dr_with_seg_len::align, build_int_cst(), comp_dr_with_seg_len_pair(), data_ref_compare_tree(), dr_with_seg_len::dr, DR_ALIAS_ARBITRARY, DR_ALIAS_MIXED_STEPS, DR_ALIAS_SWAPPED, DR_ALIAS_UNSWAPPED, DR_BASE_ADDRESS, dr_direction_indicator(), DR_INIT, DR_OFFSET, DR_REF, DR_STEP, dump_alias_pair(), dump_enabled_p(), dump_printf(), dr_with_seg_len_pair_t::first, dr_with_seg_len_pair_t::flags, FOR_EACH_VEC_ELT, i, maybe_gt, MIN, MSG_NOTE, operand_equal_p(), poly_int_tree_p(), prune_runtime_alias_test_list(), dr_with_seg_len_pair_t::second, dr_with_seg_len::seg_len, TREE_CODE, tree_int_cst_sgn(), and TREE_TYPE.

Referenced by compute_alias_check_pairs(), prune_runtime_alias_test_list(), and vect_prune_runtime_alias_test_list().

ref_contains_union_access_p()

bool ref_contains_union_access_p ( tree ref )

static

Return true if reference REF contains a union access.   

References handled_component_p(), ref_contains_union_access_p(), TREE_CODE, TREE_OPERAND, and TREE_TYPE.

Referenced by initialize_data_dependence_relation(), and ref_contains_union_access_p().

runtime_alias_check_p()

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

Return TRUE it's possible to resolve data dependence DDR by runtime alias
check.   

References DDR_A, DDR_B, DR_BASE_ADDRESS, DR_REF, DR_STMT, dump_enabled_p(), dump_printf(), opt_result::failure_at(), loop::inner, MSG_NOTE, NULL, runtime_alias_check_p(), opt_result::success(), TREE_TYPE, and TYPE_ADDR_SPACE.

Referenced by loop_distribution::data_dep_in_cycle_p(), runtime_alias_check_p(), and vect_mark_for_runtime_alias_test().

same_access_functions()

bool same_access_functions ( const struct data_dependence_relation * ddr )

inlinestatic

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

References DDR_SUBSCRIPTS, eq_evolutions_p(), same_access_functions(), and SUB_ACCESS_FN.

Referenced by build_classic_dist_vector(), and same_access_functions().

save_dir_v()

void save_dir_v ( struct data_dependence_relation * ddr, lambda_vector dir_v )

static

Helper function for uniquely inserting direction vectors.   

References DDR_DIR_VECTS, DDR_NB_LOOPS, lambda_vector_equal(), and save_dir_v().

Referenced by build_classic_dir_vector(), and save_dir_v().

save_dist_v()

void save_dist_v ( struct data_dependence_relation * ddr, lambda_vector dist_v )

static

Helper function for uniquely inserting distance vectors.   

References DDR_DIST_VECTS, DDR_NB_LOOPS, lambda_vector_equal(), and save_dist_v().

Referenced by add_multivariate_self_dist(), add_outer_distances(), build_classic_dist_vector(), insert_innermost_unit_dist_vector(), and save_dist_v().

signed_type_for_types()

tree signed_type_for_types ( tree ta, tree tb )

static

Returns a signed integer type with the largest precision from TA
and TB.   

References signed_type_for(), signed_type_for_types(), and TYPE_PRECISION.

Referenced by affine_fn_op(), analyze_miv_subscript(), analyze_siv_subscript_cst_affine(), analyze_ziv_subscript(), and signed_type_for_types().

siv_subscript_p()

bool siv_subscript_p ( const_tree chrec_a, const_tree chrec_b )

static

Returns true iff CHREC_A and CHREC_B are dependent on an index
variable, i.e., if the SIV (Single Index Variable) test is true.   

References CHREC_VARIABLE, evolution_function_is_constant_p(), evolution_function_is_univariate_p(), siv_subscript_p(), and TREE_CODE.

Referenced by analyze_overlapping_iterations(), and siv_subscript_p().

split_constant_offset() [1/2]

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 hash_map< KeyId, Value, Traits >::empty(), exp(), fold_convert, split_constant_offset(), and TREE_TYPE.

split_constant_offset() [2/2]

void split_constant_offset ( tree exp, tree * var, tree * off, irange * exp_range, hash_map< tree, std::pair< tree, tree > > & cache, unsigned * limit )

static

If EXP has pointer type, try to express it as:

  POINTER_PLUS <*VAR, (sizetype) *OFF>

where:

- *VAR has the same type as EXP
- *OFF is a constant of type ssizetype.

If EXP has an integral type, try to express (sizetype) EXP as:

  *VAR + (sizetype) *OFF

where:

- *VAR has type sizetype
- *OFF is a constant of type ssizetype.

If EXP_RANGE is nonnull, set it to the range of EXP.

CACHE caches {*VAR, *OFF} pairs for SSA names that we've previously
visited.  LIMIT counts down the number of SSA names that we are
allowed to process before giving up.   

References cfun, exp(), extract_ops_from_tree(), fold_convert, get_gimple_rhs_class(), get_legacy_range(), get_nonzero_bits(), get_range_query(), GIMPLE_TERNARY_RHS, INTEGRAL_TYPE_P, intersect_range_with_nonzero_bits(), r, range_query::range_of_expr(), irange::set(), irange::set_varying(), sizetype, split_constant_offset(), split_constant_offset_1(), ssize_int, wi::to_wide(), TREE_CODE, tree_is_chrec(), TREE_TYPE, TYPE_SIGN, vrange::undefined_p(), VR_RANGE, and VR_VARYING.

Referenced by add_iv_candidate_for_use(), classify_builtin_st(), dr_analyze_indices(), dr_analyze_innermost(), loop_niter_by_eval(), record_group_use(), split_constant_offset(), split_constant_offset(), and split_constant_offset_1().

split_constant_offset_1()

bool split_constant_offset_1 ( tree type, tree op0, enum tree_code code, tree op1, tree * var, tree * off, irange * result_range, hash_map< tree, std::pair< tree, tree > > & cache, unsigned * limit )

static

Helper function for split_constant_offset.  If TYPE is a pointer type,
try to express OP0 CODE OP1 as:

  POINTER_PLUS <*VAR, (sizetype) *OFF>

where:

- *VAR has type TYPE
- *OFF is a constant of type ssizetype.

If TYPE is an integral type, try to express (sizetype) (OP0 CODE OP1) as:

  *VAR + (sizetype) *OFF

where:

- *VAR has type sizetype
- *OFF is a constant of type ssizetype.

In both cases, OP0 CODE OP1 has type TYPE.

Return true on success.  A false return value indicates that we can't
do better than set *OFF to zero.

When returning true, set RESULT_RANGE to the range of OP0 CODE OP1,
if RESULT_RANGE is nonnull and if we can do better than assume VR_VARYING.

CACHE caches {*VAR, *OFF} pairs for SSA names that we've previously
visited.  LIMIT counts down the number of SSA names that we are
allowed to process before giving up.   

References build_fold_addr_expr, CASE_CONVERT, compute_distributive_range(), CONVERT_EXPR_CODE_P, fold_build2, fold_build_pointer_plus, fold_convert, get_inner_reference(), gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_rhs_code(), has_single_use(), int_size_in_bytes(), integer_zerop(), INTEGRAL_TYPE_P, nop_conversion_for_offset_p(), NULL_TREE, op1_range(), POINTER_TYPE_P, range_cast(), size_binop, size_int, sizetype, split_constant_offset(), split_constant_offset_1(), SSA_NAME_DEF_STMT, SSA_NAME_OCCURS_IN_ABNORMAL_PHI, ssize_int, ssizetype, wi::to_wide(), TREE_CODE, TREE_OPERAND, TREE_TYPE, TYPE_OVERFLOW_TRAPS, and TYPE_PRECISION.

Referenced by split_constant_offset(), and split_constant_offset_1().

subscript_dependence_tester()

void subscript_dependence_tester ( struct data_dependence_relation * ddr, class loop * loop_nest )

static

Computes the conflicting iterations in LOOP_NEST, and initialize DDR.   

References build_classic_dir_vector(), build_classic_dist_vector(), compute_subscript_distance(), DDR_DIST_VECT, DDR_NB_LOOPS, DDR_NUM_DIST_VECTS, dependence_stats, dump_file, dump_flags, i, datadep_stats::num_dependence_dependent, print_lambda_vector(), subscript_dependence_tester(), subscript_dependence_tester_1(), and TDF_DETAILS.

Referenced by compute_affine_dependence(), and subscript_dependence_tester().

subscript_dependence_tester_1()

bool subscript_dependence_tester_1 ( struct data_dependence_relation * ddr, unsigned int a_index, unsigned int b_index, class loop * loop_nest )

static

Helper function.  Returns true when there is a dependence between the
data references.  A_INDEX is the index of the first reference (0 for
DDR_A, 1 for DDR_B) and B_INDEX is the index of the second reference.   

References analyze_overlapping_iterations(), CF_NO_DEPENDENCE_P, CF_NOT_KNOWN_P, chrec_dont_know, chrec_known, DDR_SUBSCRIPTS, dependence_stats, finalize_ddr_dependent(), free_conflict_function(), i, NULL_TREE, datadep_stats::num_dependence_independent, datadep_stats::num_dependence_undetermined, SUB_ACCESS_FN, SUB_CONFLICTS_IN_A, SUB_CONFLICTS_IN_B, SUB_LAST_CONFLICT, and subscript_dependence_tester_1().

Referenced by build_classic_dist_vector(), subscript_dependence_tester(), and subscript_dependence_tester_1().

tree_fold_divides_p()

bool tree_fold_divides_p ( const_tree a, const_tree b )

inlinestatic

Returns true iff A divides B.   

References a, b, gcc_assert, int_const_binop(), integer_zerop(), TREE_CODE, and tree_fold_divides_p().

Referenced by analyze_siv_subscript_cst_affine(), and tree_fold_divides_p().

ziv_subscript_p()

bool ziv_subscript_p ( const_tree chrec_a, const_tree chrec_b )

inlinestatic

This section contains the classic Banerjee tests.   

Returns true iff CHREC_A and CHREC_B are not dependent on any index
variables, i.e., if the ZIV (Zero Index Variable) test is true.   

References evolution_function_is_constant_p(), and ziv_subscript_p().

Referenced by analyze_overlapping_iterations(), and ziv_subscript_p().

Variable Documentation

dependence_stats

struct datadep_stats dependence_stats

static

Referenced by analyze_miv_subscript(), analyze_overlapping_iterations(), analyze_siv_subscript(), analyze_siv_subscript_cst_affine(), analyze_ziv_subscript(), compute_affine_dependence(), compute_data_dependences_for_loop(), subscript_dependence_tester(), and subscript_dependence_tester_1().