GCC Middle and Back End API Reference
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)   ((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_referencecreate_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_functionconflict_fn_not_known (void)
 
static conflict_functionconflict_fn_no_dependence (void)
 
static bool object_address_invariant_in_loop_p (const class loop *loop, const_tree obj)
 
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_relationinitialize_data_dependence_relation (struct data_dependence_relation *res, vec< loop_p > loop_nest, bool use_alt_indices)
 
struct data_dependence_relationinitialize_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_functionconflict_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 )   ((x) / (y))

◆ INCLUDE_ALGORITHM

#define INCLUDE_ALGORITHM
Data references and dependences detectors.
   Copyright (C) 2003-2024 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()

static 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 TREE_CODE, TREE_OPERAND, and TREE_TYPE.

Referenced by initialize_data_dependence_relation().

◆ access_fn_components_comparable_p()

static 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 DECL_CONTEXT, TREE_CODE, TREE_OPERAND, TREE_TYPE, and types_compatible_p().

Referenced by initialize_data_dependence_relation().

◆ access_functions_are_affine_or_constant_p()

static 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, DR_ACCESS_FNS, evolution_function_is_affine_multivariate_p(), evolution_function_is_invariant_p(), and loop::num.

Referenced by compute_affine_dependence().

◆ add_distance_for_zero_overlaps()

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

◆ add_multivariate_self_dist()

static 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_outer_distances(), cd, 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_other_self_distances().

◆ add_other_self_distances()

◆ add_outer_distances()

static 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 DDR_NB_LOOPS, lambda_vector_copy(), lambda_vector_new(), and save_dist_v().

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

◆ affine_fn_cst()

◆ affine_fn_free()

static void affine_fn_free ( affine_fn fn)
static

◆ affine_fn_minus()

static affine_fn affine_fn_minus ( affine_fn fna,
affine_fn fnb )
static
Returns the difference of affine functions FNA and FNB.   

References affine_fn_op().

Referenced by compute_subscript_distance().

◆ affine_fn_op()

static 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 fold_build2, i, integer_zero_node, signed_type_for(), signed_type_for_types(), and TREE_TYPE.

Referenced by affine_fn_minus(), and affine_fn_plus().

◆ affine_fn_plus()

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

Referenced by compute_overlap_steps_for_affine_1_2().

◆ affine_fn_univar()

static affine_fn affine_fn_univar ( tree cst,
unsigned dim,
tree coef )
static
Returns affine function with single variable, CST + COEF * x_DIM.   

References gcc_assert, i, and integer_zero_node.

Referenced by analyze_subscript_affine_affine(), and compute_overlap_steps_for_affine_univar().

◆ affine_function_base()

static tree affine_function_base ( affine_fn fn)
static
Returns the base of the affine function FN.   

Referenced by affine_function_zero_p(), and compute_subscript_distance().

◆ affine_function_constant_p()

static bool affine_function_constant_p ( affine_fn fn)
static
Returns true if FN is a constant.   

References i, and integer_zerop().

Referenced by affine_function_zero_p(), and compute_subscript_distance().

◆ affine_function_equal_p()

static bool affine_function_equal_p ( affine_fn fna,
affine_fn fnb )
static
Returns true if FNA == FNB.   

References i, and operand_equal_p().

Referenced by common_affine_function().

◆ affine_function_zero_p()

static 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(), and integer_zerop().

Referenced by add_distance_for_zero_overlaps().

◆ analyze_miv_subscript()

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

◆ analyze_overlapping_iterations()

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
Determines the iterations for which CHREC_A is equal to CHREC_B in
  with respect to LOOP_NEST.  OVERLAP_ITERATIONS_A and
  OVERLAP_ITERATIONS_B are initialized with two functions that
  describe the iterations that contain conflicting elements.

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

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

References affine_fn_cst(), analyze_miv_subscript(), analyze_siv_subscript(), analyze_ziv_subscript(), chrec_contains_symbols(), chrec_contains_undetermined(), chrec_dont_know, conflict_fn(), conflict_fn_not_known(), dependence_stats, dump_conflict_function(), dump_file, dump_flags, eq_evolutions_p(), evolution_function_is_affine_multivariate_p(), 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 subscript_dependence_tester_1().

◆ analyze_siv_subscript()

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

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

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

Referenced by analyze_overlapping_iterations().

◆ analyze_siv_subscript_cst_affine()

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

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

References affine_fn_cst(), chrec_convert(), chrec_dont_know, chrec_fold_minus(), chrec_is_positive(), 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(), TREE_TYPE, and type().

Referenced by analyze_siv_subscript().

◆ analyze_subscript_affine_affine()

◆ analyze_ziv_subscript()

static 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(), 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, TREE_TYPE, and type().

Referenced by analyze_overlapping_iterations().

◆ base_supports_access_fn_components_p()

static 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 TREE_CODE, and TREE_TYPE.

Referenced by initialize_data_dependence_relation().

◆ build_classic_dir_vector()

static 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 DDR_DIST_VECTS, DDR_NB_LOOPS, dir_from_dist(), FOR_EACH_VEC_ELT, i, lambda_vector_new(), and save_dir_v().

Referenced by subscript_dependence_tester().

◆ build_classic_dist_vector()

◆ build_classic_dist_vector_1()

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

◆ can_use_analyze_subscript_affine_affine()

static 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(), 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, TDF_DETAILS, and type().

Referenced by analyze_siv_subscript().

◆ canonicalize_base_object_address()

static 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, POINTER_TYPE_P, STRIP_NOPS, TREE_CODE, TREE_OPERAND, and TREE_TYPE.

Referenced by dr_analyze_innermost().

◆ chrec_is_positive()

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

static 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, conflict_function::fns, i, and conflict_function::n.

Referenced by compute_subscript_distance().

◆ comp_dr_with_seg_len_pair()

static 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 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 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, 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_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(), DR_IS_WRITE, FOR_EACH_VEC_ELT, i, initialize_data_dependence_relation(), data_dependence_relation::loop_nest, and NULL.

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

◆ compute_data_dependences_for_loop()

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

◆ compute_distributive_range()

static 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 range_op_handler::fold_range(), gcc_assert, wide_int_storage::get_precision(), INTEGRAL_TYPE_P, irange::lower_bound(), wi::mask(), irange::num_pairs(), 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 split_constant_offset_1().

◆ compute_overlap_steps_for_affine_1_2()

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

◆ compute_overlap_steps_for_affine_univar()

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
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, FLOOR_DIV, gcd(), integer_zero_node, MIN, and NULL_TREE.

Referenced by analyze_subscript_affine_affine(), and compute_overlap_steps_for_affine_1_2().

◆ compute_subscript_distance()

static void compute_subscript_distance ( struct data_dependence_relation * ddr)
static

◆ conflict_fn()

static conflict_function * conflict_fn ( unsigned n,
... )
static

◆ conflict_fn_no_dependence()

static conflict_function * conflict_fn_no_dependence ( void )
static

◆ conflict_fn_not_known()

◆ create_data_ref()

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

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

References DR_ACCESS_FN, dr_analyze_alias(), dr_analyze_indices(), dr_analyze_innermost(), DR_BASE_ADDRESS, DR_BASE_ALIGNMENT, DR_BASE_MISALIGNMENT, DR_BASE_OBJECT, DR_INIT, DR_INNERMOST, DR_IS_CONDITIONAL_IN_STMT, DR_IS_READ, DR_NUM_DIMENSIONS, DR_OFFSET, DR_OFFSET_ALIGNMENT, DR_REF, DR_STEP, DR_STEP_ALIGNMENT, DR_STMT, dump_file, dump_flags, i, data_reference::indices, data_reference::is_conditional_in_stmt, data_reference::is_read, NULL, print_generic_expr(), print_generic_stmt(), data_reference::stmt, TDF_DETAILS, and TDF_SLIM.

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

◆ create_ifn_alias_checks()

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

◆ create_intersect_range_checks()

static 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::access_size, dr_with_seg_len::align, boolean_type_node, create_ifn_alias_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(), min_align(), MSG_NOTE, NULL_TREE, and TREE_CODE.

Referenced by create_runtime_alias_checks().

◆ create_intersect_range_checks_index()

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

◆ create_runtime_alias_checks()

void create_runtime_alias_checks ( class loop * loop,
const vec< dr_with_seg_len_pair_t > * alias_pairs,
tree * cond_expr )
Create a conditional expression that represents the run-time checks for
overlapping of address ranges represented by a list of data references
pairs passed in ALIAS_PAIRS.  Data references are in LOOP.  The returned
COND_EXPR is the conditional expression to be used in the if statement
that controls which version of the loop gets executed at runtime.   

References alias_pairs, boolean_type_node, create_intersect_range_checks(), DR_REF, dump_enabled_p(), dump_printf(), fold_build2, fold_defer_overflow_warnings(), fold_undefer_and_ignore_overflow_warnings(), gcc_assert, and MSG_NOTE.

Referenced by vect_create_cond_for_alias_checks(), and version_loop_by_alias_check().

◆ create_waw_or_war_checks()

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

◆ data_ref_compare_tree()

◆ debug() [1/6]

DEBUG_FUNCTION void debug ( data_reference & ref)
Unified dump function for a DATA_REFERENCE structure.   

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

◆ 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 dump_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 dump_data_dependence_relations().

◆ debug_data_reference()

DEBUG_FUNCTION void debug_data_reference ( struct data_reference * dr)
Print to STDERR the data_reference DR.   

References dump_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 dump_data_references().

◆ debug_ddrs()

DEBUG_FUNCTION void debug_ddrs ( vec< ddr_p > ddrs)

References dump_ddrs().

◆ dir_from_dist()

static 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_negative, and dir_positive.

Referenced by build_classic_dir_vector().

◆ dr_alignment()

◆ dr_analyze_alias()

static void dr_analyze_alias ( struct data_reference * dr)
static
Extracts the alias analysis information from the memory reference DR.   

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

◆ dr_analyze_indices()

◆ 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(), 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(), pcom_worker::find_looparound_phi(), and vect_analyze_data_refs().

◆ dr_direction_indicator()

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

References dr_step_indicator().

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

◆ dr_equal_offsets_p()

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

References dr_equal_offsets_p1(), and DR_OFFSET.

◆ dr_equal_offsets_p1()

static 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(), fold_binary, fold_convert, integer_zerop(), ssize_int, and ssizetype.

Referenced by vect_prune_runtime_alias_test_list().

◆ dr_may_alias_p()

◆ dr_step_indicator()

static 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, 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, path_range_query::range_of_expr(), 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(), 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().

Referenced by 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 i, print_generic_expr(), and TDF_SLIM.

Referenced by dump_conflict_function().

◆ dump_alias_pair()

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

◆ dump_conflict_function()

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

◆ dump_data_dependence_relation()

◆ dump_data_dependence_relations()

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

◆ dump_data_reference()

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

◆ dump_data_references()

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

Referenced by debug(), and debug_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().

Referenced by debug_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, NULL_TREE, print_direction_vector(), and print_lambda_vector().

◆ dump_subscript()

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

◆ finalize_ddr_dependent()

static 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, and free_subscripts().

Referenced by build_classic_dist_vector_1(), compute_affine_dependence(), 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_stmt(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_stmt(), and NULL_TREE.

Referenced by cond_if_else_store_replacement(), and find_data_references_in_loop().

◆ find_data_references_in_loop()

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

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

References chrec_dont_know, find_data_references_in_bb(), free(), get_loop_body_in_dom_order(), i, NULL_TREE, and loop::num_nodes.

Referenced by compute_data_dependences_for_loop(), and tree_if_conversion().

◆ find_data_references_in_stmt()

opt_result find_data_references_in_stmt ( class loop * nest,
gimple * stmt,
vec< data_reference_p > * datarefs )
Stores the data references in STMT to DATAREFS.  If there is an unanalyzable
reference, returns false, otherwise returns true.  NEST is the outermost
loop of the loop nest in which the references should be analyzed.   

References create_data_ref(), opt_result::failure_at(), gcc_assert, get_references_in_stmt(), loop_containing_stmt(), loop_preheader_edge(), NULL, and opt_result::success().

Referenced by loop_distribution::create_rdg_vertices(), find_data_references_in_bb(), and vect_find_stmt_data_reference().

◆ find_loop_nest()

bool find_loop_nest ( class loop * loop,
vec< loop_p > * loop_nest )
Return false when the LOOP is not well nested.  Otherwise return
true and insert in LOOP_NEST the loops of the nest.  LOOP_NEST will
contain the loops from the outermost to the innermost, as they will
appear in the classic distance vector.   

References find_loop_nest_1(), and loop::inner.

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

◆ find_loop_nest_1()

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

static void free_conflict_function ( conflict_function * f)
static

◆ free_data_ref()

◆ free_data_refs()

◆ free_dependence_relation()

void free_dependence_relation ( struct data_dependence_relation * ddr)

◆ free_dependence_relations()

void free_dependence_relations ( vec< ddr_p > & dependence_relations)

◆ free_subscripts()

static void free_subscripts ( vec< subscript_p > subscripts)
static

◆ gcd_of_steps_may_divide_p()

static 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 cd, CHREC_LEFT, CHREC_RIGHT, gcd(), TREE_CODE, tree_fits_shwi_p(), and tree_to_shwi().

Referenced by analyze_miv_subscript().

◆ get_base_for_alignment()

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

References get_base_for_alignment_1(), MAX_OFILE_ALIGNMENT, TREE_CODE, and TREE_OPERAND.

Referenced by vect_compute_data_ref_alignment().

◆ get_base_for_alignment_1()

static 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_inner_reference(), highest_pow2_factor(), loop_containing_stmt(), MAX_OFILE_ALIGNMENT, MIN, NULL, NULL_TREE, offset, 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().

◆ get_references_in_stmt()

◆ get_segment_min_max()

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

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

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

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

◆ insert_innermost_unit_dist_vector()

static void insert_innermost_unit_dist_vector ( struct data_dependence_relation * ddr)
static

◆ int_divides_p()

static bool int_divides_p ( lambda_int a,
lambda_int b )
inlinestatic
Returns true iff A divides B.   

References a, and b.

Referenced by analyze_subscript_affine_affine().

◆ invariant_access_functions()

static 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(), and SUB_ACCESS_FN.

Referenced by build_classic_dist_vector().

◆ lambda_matrix_copy()

static 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, and lambda_vector_copy().

Referenced by lambda_matrix_right_hermite().

◆ lambda_matrix_id()

static void lambda_matrix_id ( lambda_matrix mat,
int size )
static
Store the N x N identity matrix in MAT.   

References i.

Referenced by lambda_matrix_right_hermite().

◆ lambda_matrix_right_hermite()

static 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_row_add(), lambda_vector_first_nz(), and S.

Referenced by analyze_subscript_affine_affine().

◆ lambda_matrix_row_add()

static 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, and mul_hwi().

Referenced by lambda_matrix_right_hermite().

◆ lambda_matrix_row_negate()

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

Referenced by analyze_subscript_affine_affine().

◆ lambda_vector_copy()

static void lambda_vector_copy ( lambda_vector vec1,
lambda_vector vec2,
int size )
static
Copy the elements of vector VEC1 with length SIZE to VEC2.   

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

◆ lambda_vector_equal()

static bool lambda_vector_equal ( lambda_vector vec1,
lambda_vector vec2,
int size )
static
Return true if two vectors are equal.   

References i.

Referenced by save_dir_v(), and save_dist_v().

◆ lambda_vector_first_nz()

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

Referenced by build_classic_dist_vector(), and lambda_matrix_right_hermite().

◆ lambda_vector_mult_const()

static 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, and lambda_vector_clear().

Referenced by lambda_vector_negate().

◆ lambda_vector_negate()

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

Referenced by lambda_matrix_row_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, and loop::num_nodes.

◆ max_stmt_executions_tree()

static 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(), unsigned_type_node, and wide_int_to_tree().

Referenced by analyze_miv_subscript().

◆ non_affine_dependence_relation()

static 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, and TDF_DETAILS.

Referenced by build_classic_dist_vector_1().

◆ nop_conversion_for_offset_p()

static 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, range_fits_type_p(), sizetype, TYPE_OVERFLOW_TRAPS, TYPE_PRECISION, TYPE_SIGN, and TYPE_UNSIGNED.

Referenced by split_constant_offset_1().

◆ object_address_invariant_in_loop_p()

static 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, TREE_CODE, and TREE_OPERAND.

Referenced by initialize_data_dependence_relation().

◆ operator==()

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

◆ print_direction_vector()

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

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

◆ 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, and i.

Referenced by build_classic_dist_vector(), dump_data_dependence_relation(), dump_dist_dir_vectors(), and print_dist_vectors().

◆ 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 alising checks
between store_ptr_0 & load_ptr_0 and store_ptr_0 & load_ptr_1:

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

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

References 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, last, maybe_gt, MIN, MSG_NOTE, operand_equal_p(), poly_int_tree_p(), 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(), and vect_prune_runtime_alias_test_list().

◆ ref_contains_union_access_p()

static bool ref_contains_union_access_p ( tree ref)
static
Return true if reference REF contains a union access.   

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

Referenced by initialize_data_dependence_relation().

◆ runtime_alias_check_p()

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

◆ same_access_functions()

static 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(), and SUB_ACCESS_FN.

Referenced by build_classic_dist_vector().

◆ save_dir_v()

static 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, and lambda_vector_equal().

Referenced by build_classic_dir_vector().

◆ save_dist_v()

static void save_dist_v ( struct data_dependence_relation * ddr,
lambda_vector dist_v )
static

◆ signed_type_for_types()

static 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(), and TYPE_PRECISION.

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

◆ siv_subscript_p()

static 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(), and TREE_CODE.

Referenced by analyze_overlapping_iterations().

◆ 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 cache, exp(), fold_convert, split_constant_offset(), and TREE_TYPE.

◆ split_constant_offset() [2/2]

static 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 cache, 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, path_range_query::range_of_expr(), irange::set(), irange::set_varying(), sizetype, 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(), record_group_use(), split_constant_offset(), and split_constant_offset_1().

◆ split_constant_offset_1()

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

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

◆ subscript_dependence_tester_1()

static 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, and SUB_LAST_CONFLICT.

Referenced by build_classic_dist_vector(), and subscript_dependence_tester().

◆ tree_fold_divides_p()

static 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(), and TREE_CODE.

Referenced by analyze_siv_subscript_cst_affine().

◆ ziv_subscript_p()

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

Referenced by analyze_overlapping_iterations().

Variable Documentation

◆ dependence_stats