Google Git
Sign in
gnu / gcc / refs/tags/releases/gcc-8.2.0 / . / gcc / tree-data-ref.c
blob: 0917d6dff0148ce5729b38affe63a8417a98ce21 [file] [log] [blame]
/* Data references and dependences detectors.
Copyright (C) 2003-2018 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.
*/
#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 "params.h"
#include "builtins.h"
#include "stringpool.h"
#include "tree-vrp.h"
#include "tree-ssanames.h"
#include "tree-eh.h"
static struct datadep_stats
{
int num_dependence_tests;
int num_dependence_dependent;
int num_dependence_independent;
int num_dependence_undetermined;
int num_subscript_tests;
int num_subscript_undetermined;
int num_same_subscript_function;
int num_ziv;
int num_ziv_independent;
int num_ziv_dependent;
int num_ziv_unimplemented;
int num_siv;
int num_siv_independent;
int num_siv_dependent;
int num_siv_unimplemented;
int num_miv;
int num_miv_independent;
int num_miv_dependent;
int num_miv_unimplemented;
} dependence_stats;
static bool subscript_dependence_tester_1 (struct data_dependence_relation *,
unsigned int, unsigned int,
struct loop *);
/* Returns true iff A divides B. */
static inline bool
tree_fold_divides_p (const_tree a, const_tree b)
{
gcc_assert (TREE_CODE (a) == INTEGER_CST);
gcc_assert (TREE_CODE (b) == INTEGER_CST);
return integer_zerop (int_const_binop (TRUNC_MOD_EXPR, b, a));
}
/* Returns true iff A divides B. */
static inline bool
int_divides_p (int a, int b)
{
return ((b % a) == 0);
}
/* Return true if reference REF contains a union access. */
static bool
ref_contains_union_access_p (tree ref)
{
while (handled_component_p (ref))
{
ref = TREE_OPERAND (ref, 0);
if (TREE_CODE (TREE_TYPE (ref)) == UNION_TYPE
|| TREE_CODE (TREE_TYPE (ref)) == QUAL_UNION_TYPE)
return true;
}
return false;
}
/* Dump into FILE all the data references from DATAREFS. */
static void
dump_data_references (FILE *file, vec<data_reference_p> datarefs)
{
unsigned int i;
struct data_reference *dr;
FOR_EACH_VEC_ELT (datarefs, i, dr)
dump_data_reference (file, dr);
}
/* Unified dump into FILE all the data references from DATAREFS. */
DEBUG_FUNCTION void
debug (vec<data_reference_p> &ref)
{
dump_data_references (stderr, ref);
}
DEBUG_FUNCTION void
debug (vec<data_reference_p> *ptr)
{
if (ptr)
debug (*ptr);
else
fprintf (stderr, "<nil>\n");
}
/* Dump into STDERR all the data references from DATAREFS. */
DEBUG_FUNCTION void
debug_data_references (vec<data_reference_p> datarefs)
{
dump_data_references (stderr, datarefs);
}
/* Print to STDERR the data_reference DR. */
DEBUG_FUNCTION void
debug_data_reference (struct data_reference *dr)
{
dump_data_reference (stderr, dr);
}
/* Dump function for a DATA_REFERENCE structure. */
void
dump_data_reference (FILE *outf,
struct data_reference *dr)
{
unsigned int i;
fprintf (outf, "#(Data Ref: \n");
fprintf (outf, "# bb: %d \n", gimple_bb (DR_STMT (dr))->index);
fprintf (outf, "# stmt: ");
print_gimple_stmt (outf, DR_STMT (dr), 0);
fprintf (outf, "# ref: ");
print_generic_stmt (outf, DR_REF (dr));
fprintf (outf, "# base_object: ");
print_generic_stmt (outf, DR_BASE_OBJECT (dr));
for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
{
fprintf (outf, "# Access function %d: ", i);
print_generic_stmt (outf, DR_ACCESS_FN (dr, i));
}
fprintf (outf, "#)\n");
}
/* Unified dump function for a DATA_REFERENCE structure. */
DEBUG_FUNCTION void
debug (data_reference &ref)
{
dump_data_reference (stderr, &ref);
}
DEBUG_FUNCTION void
debug (data_reference *ptr)
{
if (ptr)
debug (*ptr);
else
fprintf (stderr, "<nil>\n");
}
/* Dumps the affine function described by FN to the file OUTF. */
DEBUG_FUNCTION void
dump_affine_function (FILE *outf, affine_fn fn)
{
unsigned i;
tree coef;
print_generic_expr (outf, fn[0], TDF_SLIM);
for (i = 1; fn.iterate (i, &coef); i++)
{
fprintf (outf, " + ");
print_generic_expr (outf, coef, TDF_SLIM);
fprintf (outf, " * x_%u", i);
}
}
/* Dumps the conflict function CF to the file OUTF. */
DEBUG_FUNCTION void
dump_conflict_function (FILE *outf, conflict_function *cf)
{
unsigned i;
if (cf->n == NO_DEPENDENCE)
fprintf (outf, "no dependence");
else if (cf->n == NOT_KNOWN)
fprintf (outf, "not known");
else
{
for (i = 0; i < cf->n; i++)
{
if (i != 0)
fprintf (outf, " ");
fprintf (outf, "[");
dump_affine_function (outf, cf->fns[i]);
fprintf (outf, "]");
}
}
}
/* Dump function for a SUBSCRIPT structure. */
DEBUG_FUNCTION void
dump_subscript (FILE *outf, struct subscript *subscript)
{
conflict_function *cf = SUB_CONFLICTS_IN_A (subscript);
fprintf (outf, "\n (subscript \n");
fprintf (outf, " iterations_that_access_an_element_twice_in_A: ");
dump_conflict_function (outf, cf);
if (CF_NONTRIVIAL_P (cf))
{
tree last_iteration = SUB_LAST_CONFLICT (subscript);
fprintf (outf, "\n last_conflict: ");
print_generic_expr (outf, last_iteration);
}
cf = SUB_CONFLICTS_IN_B (subscript);
fprintf (outf, "\n iterations_that_access_an_element_twice_in_B: ");
dump_conflict_function (outf, cf);
if (CF_NONTRIVIAL_P (cf))
{
tree last_iteration = SUB_LAST_CONFLICT (subscript);
fprintf (outf, "\n last_conflict: ");
print_generic_expr (outf, last_iteration);
}
fprintf (outf, "\n (Subscript distance: ");
print_generic_expr (outf, SUB_DISTANCE (subscript));
fprintf (outf, " ))\n");
}
/* Print the classic direction vector DIRV to OUTF. */
DEBUG_FUNCTION void
print_direction_vector (FILE *outf,
lambda_vector dirv,
int length)
{
int eq;
for (eq = 0; eq < length; eq++)
{
enum data_dependence_direction dir = ((enum data_dependence_direction)
dirv[eq]);
switch (dir)
{
case dir_positive:
fprintf (outf, " +");
break;
case dir_negative:
fprintf (outf, " -");
break;
case dir_equal:
fprintf (outf, " =");
break;
case dir_positive_or_equal:
fprintf (outf, " +=");
break;
case dir_positive_or_negative:
fprintf (outf, " +-");
break;
case dir_negative_or_equal:
fprintf (outf, " -=");
break;
case dir_star:
fprintf (outf, " *");
break;
default:
fprintf (outf, "indep");
break;
}
}
fprintf (outf, "\n");
}
/* Print a vector of direction vectors. */
DEBUG_FUNCTION void
print_dir_vectors (FILE *outf, vec<lambda_vector> dir_vects,
int length)
{
unsigned j;
lambda_vector v;
FOR_EACH_VEC_ELT (dir_vects, j, v)
print_direction_vector (outf, v, length);
}
/* Print out a vector VEC of length N to OUTFILE. */
DEBUG_FUNCTION void
print_lambda_vector (FILE * outfile, lambda_vector vector, int n)
{
int i;
for (i = 0; i < n; i++)
fprintf (outfile, "%3d ", vector[i]);
fprintf (outfile, "\n");
}
/* Print a vector of distance vectors. */
DEBUG_FUNCTION void
print_dist_vectors (FILE *outf, vec<lambda_vector> dist_vects,
int length)
{
unsigned j;
lambda_vector v;
FOR_EACH_VEC_ELT (dist_vects, j, v)
print_lambda_vector (outf, v, length);
}
/* Dump function for a DATA_DEPENDENCE_RELATION structure. */
DEBUG_FUNCTION void
dump_data_dependence_relation (FILE *outf,
struct data_dependence_relation *ddr)
{
struct data_reference *dra, *drb;
fprintf (outf, "(Data Dep: \n");
if (!ddr || DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
{
if (ddr)
{
dra = DDR_A (ddr);
drb = DDR_B (ddr);
if (dra)
dump_data_reference (outf, dra);
else
fprintf (outf, " (nil)\n");
if (drb)
dump_data_reference (outf, drb);
else
fprintf (outf, " (nil)\n");
}
fprintf (outf, " (don't know)\n)\n");
return;
}
dra = DDR_A (ddr);
drb = DDR_B (ddr);
dump_data_reference (outf, dra);
dump_data_reference (outf, drb);
if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
fprintf (outf, " (no dependence)\n");
else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
{
unsigned int i;
struct loop *loopi;
subscript *sub;
FOR_EACH_VEC_ELT (DDR_SUBSCRIPTS (ddr), i, sub)
{
fprintf (outf, " access_fn_A: ");
print_generic_stmt (outf, SUB_ACCESS_FN (sub, 0));
fprintf (outf, " access_fn_B: ");
print_generic_stmt (outf, SUB_ACCESS_FN (sub, 1));
dump_subscript (outf, sub);
}
fprintf (outf, " inner loop index: %d\n", DDR_INNER_LOOP (ddr));
fprintf (outf, " loop nest: (");
FOR_EACH_VEC_ELT (DDR_LOOP_NEST (ddr), i, loopi)
fprintf (outf, "%d ", loopi->num);
fprintf (outf, ")\n");
for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
{
fprintf (outf, " distance_vector: ");
print_lambda_vector (outf, DDR_DIST_VECT (ddr, i),
DDR_NB_LOOPS (ddr));
}
for (i = 0; i < DDR_NUM_DIR_VECTS (ddr); i++)
{
fprintf (outf, " direction_vector: ");
print_direction_vector (outf, DDR_DIR_VECT (ddr, i),
DDR_NB_LOOPS (ddr));
}
}
fprintf (outf, ")\n");
}
/* Debug version. */
DEBUG_FUNCTION void
debug_data_dependence_relation (struct data_dependence_relation *ddr)
{
dump_data_dependence_relation (stderr, ddr);
}
/* Dump into FILE all the dependence relations from DDRS. */
DEBUG_FUNCTION void
dump_data_dependence_relations (FILE *file,
vec<ddr_p> ddrs)
{
unsigned int i;
struct data_dependence_relation *ddr;
FOR_EACH_VEC_ELT (ddrs, i, ddr)
dump_data_dependence_relation (file, ddr);
}
DEBUG_FUNCTION void
debug (vec<ddr_p> &ref)
{
dump_data_dependence_relations (stderr, ref);
}
DEBUG_FUNCTION void
debug (vec<ddr_p> *ptr)
{
if (ptr)
debug (*ptr);
else
fprintf (stderr, "<nil>\n");
}
/* Dump to STDERR all the dependence relations from DDRS. */
DEBUG_FUNCTION void
debug_data_dependence_relations (vec<ddr_p> ddrs)
{
dump_data_dependence_relations (stderr, 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. */
DEBUG_FUNCTION void
dump_dist_dir_vectors (FILE *file, vec<ddr_p> ddrs)
{
unsigned int i, j;
struct data_dependence_relation *ddr;
lambda_vector v;
FOR_EACH_VEC_ELT (ddrs, i, ddr)
if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_AFFINE_P (ddr))
{
FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr), j, v)
{
fprintf (file, "DISTANCE_V (");
print_lambda_vector (file, v, DDR_NB_LOOPS (ddr));
fprintf (file, ")\n");
}
FOR_EACH_VEC_ELT (DDR_DIR_VECTS (ddr), j, v)
{
fprintf (file, "DIRECTION_V (");
print_direction_vector (file, v, DDR_NB_LOOPS (ddr));
fprintf (file, ")\n");
}
}
fprintf (file, "\n\n");
}
/* Dumps the data dependence relations DDRS in FILE. */
DEBUG_FUNCTION void
dump_ddrs (FILE *file, vec<ddr_p> ddrs)
{
unsigned int i;
struct data_dependence_relation *ddr;
FOR_EACH_VEC_ELT (ddrs, i, ddr)
dump_data_dependence_relation (file, ddr);
fprintf (file, "\n\n");
}
DEBUG_FUNCTION void
debug_ddrs (vec<ddr_p> ddrs)
{
dump_ddrs (stderr, ddrs);
}
/* Helper function for split_constant_offset. Expresses OP0 CODE OP1
(the type of the result is TYPE) as VAR + OFF, where OFF is a nonzero
constant of type ssizetype, and returns true. If we cannot do this
with OFF nonzero, OFF and VAR are set to NULL_TREE instead and false
is returned. */
static bool
split_constant_offset_1 (tree type, tree op0, enum tree_code code, tree op1,
tree *var, tree *off)
{
tree var0, var1;
tree off0, off1;
enum tree_code ocode = code;
*var = NULL_TREE;
*off = NULL_TREE;
switch (code)
{
case INTEGER_CST:
*var = build_int_cst (type, 0);
*off = fold_convert (ssizetype, op0);
return true;
case POINTER_PLUS_EXPR:
ocode = PLUS_EXPR;
/* FALLTHROUGH */
case PLUS_EXPR:
case MINUS_EXPR:
split_constant_offset (op0, &var0, &off0);
split_constant_offset (op1, &var1, &off1);
*var = fold_build2 (code, type, var0, var1);
*off = size_binop (ocode, off0, off1);
return true;
case MULT_EXPR:
if (TREE_CODE (op1) != INTEGER_CST)
return false;
split_constant_offset (op0, &var0, &off0);
*var = fold_build2 (MULT_EXPR, type, var0, op1);
*off = size_binop (MULT_EXPR, off0, fold_convert (ssizetype, op1));
return true;
case ADDR_EXPR:
{
tree base, poffset;
poly_int64 pbitsize, pbitpos, pbytepos;
machine_mode pmode;
int punsignedp, preversep, pvolatilep;
op0 = TREE_OPERAND (op0, 0);
base
= get_inner_reference (op0, &pbitsize, &pbitpos, &poffset, &pmode,
&punsignedp, &preversep, &pvolatilep);
if (!multiple_p (pbitpos, BITS_PER_UNIT, &pbytepos))
return false;
base = build_fold_addr_expr (base);
off0 = ssize_int (pbytepos);
if (poffset)
{
split_constant_offset (poffset, &poffset, &off1);
off0 = size_binop (PLUS_EXPR, off0, off1);
if (POINTER_TYPE_P (TREE_TYPE (base)))
base = fold_build_pointer_plus (base, poffset);
else
base = fold_build2 (PLUS_EXPR, TREE_TYPE (base), base,
fold_convert (TREE_TYPE (base), poffset));
}
var0 = fold_convert (type, base);
/* If variable length types are involved, punt, otherwise casts
might be converted into ARRAY_REFs in gimplify_conversion.
To compute that ARRAY_REF's element size TYPE_SIZE_UNIT, which
possibly no longer appears in current GIMPLE, might resurface.
This perhaps could run
if (CONVERT_EXPR_P (var0))
{
gimplify_conversion (&var0);
// Attempt to fill in any within var0 found ARRAY_REF's
// element size from corresponding op embedded ARRAY_REF,
// if unsuccessful, just punt.
} */
while (POINTER_TYPE_P (type))
type = TREE_TYPE (type);
if (int_size_in_bytes (type) < 0)
return false;
*var = var0;
*off = off0;
return true;
}
case SSA_NAME:
{
if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0))
return false;
gimple *def_stmt = SSA_NAME_DEF_STMT (op0);
enum tree_code subcode;
if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
return false;
var0 = gimple_assign_rhs1 (def_stmt);
subcode = gimple_assign_rhs_code (def_stmt);
var1 = gimple_assign_rhs2 (def_stmt);
return split_constant_offset_1 (type, var0, subcode, var1, var, off);
}
CASE_CONVERT:
{
/* We must not introduce undefined overflow, and we must not change the value.
Hence we're okay if the inner type doesn't overflow to start with
(pointer or signed), the outer type also is an integer or pointer
and the outer precision is at least as large as the inner. */
tree itype = TREE_TYPE (op0);
if ((POINTER_TYPE_P (itype)
|| (INTEGRAL_TYPE_P (itype) && !TYPE_OVERFLOW_TRAPS (itype)))
&& TYPE_PRECISION (type) >= TYPE_PRECISION (itype)
&& (POINTER_TYPE_P (type) || INTEGRAL_TYPE_P (type)))
{
if (INTEGRAL_TYPE_P (itype) && TYPE_OVERFLOW_WRAPS (itype))
{
/* Split the unconverted operand and try to prove that
wrapping isn't a problem. */
tree tmp_var, tmp_off;
split_constant_offset (op0, &tmp_var, &tmp_off);
/* See whether we have an SSA_NAME whose range is known
to be [A, B]. */
if (TREE_CODE (tmp_var) != SSA_NAME)
return false;
wide_int var_min, var_max;
value_range_type vr_type = get_range_info (tmp_var, &var_min,
&var_max);
wide_int var_nonzero = get_nonzero_bits (tmp_var);
signop sgn = TYPE_SIGN (itype);
if (intersect_range_with_nonzero_bits (vr_type, &var_min,
&var_max, var_nonzero,
sgn) != VR_RANGE)
return false;
/* See whether the range of OP0 (i.e. TMP_VAR + TMP_OFF)
is known to be [A + TMP_OFF, B + TMP_OFF], with all
operations done in ITYPE. The addition must overflow
at both ends of the range or at neither. */
bool overflow[2];
unsigned int prec = TYPE_PRECISION (itype);
wide_int woff = wi::to_wide (tmp_off, prec);
wide_int op0_min = wi::add (var_min, woff, sgn, &overflow[0]);
wi::add (var_max, woff, sgn, &overflow[1]);
if (overflow[0] != overflow[1])
return false;
/* Calculate (ssizetype) OP0 - (ssizetype) TMP_VAR. */
widest_int diff = (widest_int::from (op0_min, sgn)
- widest_int::from (var_min, sgn));
var0 = tmp_var;
*off = wide_int_to_tree (ssizetype, diff);
}
else
split_constant_offset (op0, &var0, off);
*var = fold_convert (type, var0);
return true;
}
return false;
}
default:
return false;
}
}
/* Expresses EXP as VAR + OFF, where off is a constant. The type of OFF
will be ssizetype. */
void
split_constant_offset (tree exp, tree *var, tree *off)
{
tree type = TREE_TYPE (exp), op0, op1, e, o;
enum tree_code code;
*var = exp;
*off = ssize_int (0);
if (tree_is_chrec (exp)
|| get_gimple_rhs_class (TREE_CODE (exp)) == GIMPLE_TERNARY_RHS)
return;
code = TREE_CODE (exp);
extract_ops_from_tree (exp, &code, &op0, &op1);
if (split_constant_offset_1 (type, op0, code, op1, &e, &o))
{
*var = e;
*off = o;
}
}
/* Returns the address ADDR of an object in a canonical shape (without nop
casts, and with type of pointer to the object). */
static tree
canonicalize_base_object_address (tree addr)
{
tree orig = addr;
STRIP_NOPS (addr);
/* The base address may be obtained by casting from integer, in that case
keep the cast. */
if (!POINTER_TYPE_P (TREE_TYPE (addr)))
return orig;
if (TREE_CODE (addr) != ADDR_EXPR)
return addr;
return build_fold_addr_expr (TREE_OPERAND (addr, 0));
}
/* Analyze the behavior of memory reference REF. 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. */
bool
dr_analyze_innermost (innermost_loop_behavior *drb, tree ref,
struct loop *loop)
{
poly_int64 pbitsize, pbitpos;
tree base, poffset;
machine_mode pmode;
int punsignedp, preversep, pvolatilep;
affine_iv base_iv, offset_iv;
tree init, dinit, step;
bool in_loop = (loop && loop->num);
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "analyze_innermost: ");
base = get_inner_reference (ref, &pbitsize, &pbitpos, &poffset, &pmode,
&punsignedp, &preversep, &pvolatilep);
gcc_assert (base != NULL_TREE);
poly_int64 pbytepos;
if (!multiple_p (pbitpos, BITS_PER_UNIT, &pbytepos))
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "failed: bit offset alignment.\n");
return false;
}
if (preversep)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "failed: reverse storage order.\n");
return false;
}
/* Calculate the alignment and misalignment for the inner reference. */
unsigned int HOST_WIDE_INT bit_base_misalignment;
unsigned int bit_base_alignment;
get_object_alignment_1 (base, &bit_base_alignment, &bit_base_misalignment);
/* There are no bitfield references remaining in BASE, so the values
we got back must be whole bytes. */
gcc_assert (bit_base_alignment % BITS_PER_UNIT == 0
&& bit_base_misalignment % BITS_PER_UNIT == 0);
unsigned int base_alignment = bit_base_alignment / BITS_PER_UNIT;
poly_int64 base_misalignment = bit_base_misalignment / BITS_PER_UNIT;
if (TREE_CODE (base) == MEM_REF)
{
if (!integer_zerop (TREE_OPERAND (base, 1)))
{
/* Subtract MOFF from the base and add it to POFFSET instead.
Adjust the misalignment to reflect the amount we subtracted. */
poly_offset_int moff = mem_ref_offset (base);
base_misalignment -= moff.force_shwi ();
tree mofft = wide_int_to_tree (sizetype, moff);
if (!poffset)
poffset = mofft;
else
poffset = size_binop (PLUS_EXPR, poffset, mofft);
}
base = TREE_OPERAND (base, 0);
}
else
base = build_fold_addr_expr (base);
if (in_loop)
{
if (!simple_iv (loop, loop, base, &base_iv, true))
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "failed: evolution of base is not affine.\n");
return false;
}
}
else
{
base_iv.base = base;
base_iv.step = ssize_int (0);
base_iv.no_overflow = true;
}
if (!poffset)
{
offset_iv.base = ssize_int (0);
offset_iv.step = ssize_int (0);
}
else
{
if (!in_loop)
{
offset_iv.base = poffset;
offset_iv.step = ssize_int (0);
}
else if (!simple_iv (loop, loop, poffset, &offset_iv, true))
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "failed: evolution of offset is not affine.\n");
return false;
}
}
init = ssize_int (pbytepos);
/* Subtract any constant component from the base and add it to INIT instead.
Adjust the misalignment to reflect the amount we subtracted. */
split_constant_offset (base_iv.base, &base_iv.base, &dinit);
init = size_binop (PLUS_EXPR, init, dinit);
base_misalignment -= TREE_INT_CST_LOW (dinit);
split_constant_offset (offset_iv.base, &offset_iv.base, &dinit);
init = size_binop (PLUS_EXPR, init, dinit);
step = size_binop (PLUS_EXPR,
fold_convert (ssizetype, base_iv.step),
fold_convert (ssizetype, offset_iv.step));
base = canonicalize_base_object_address (base_iv.base);
/* See if get_pointer_alignment can guarantee a higher alignment than
the one we calculated above. */
unsigned int HOST_WIDE_INT alt_misalignment;
unsigned int alt_alignment;
get_pointer_alignment_1 (base, &alt_alignment, &alt_misalignment);
/* As above, these values must be whole bytes. */
gcc_assert (alt_alignment % BITS_PER_UNIT == 0
&& alt_misalignment % BITS_PER_UNIT == 0);
alt_alignment /= BITS_PER_UNIT;
alt_misalignment /= BITS_PER_UNIT;
if (base_alignment < alt_alignment)
{
base_alignment = alt_alignment;
base_misalignment = alt_misalignment;
}
drb->base_address = base;
drb->offset = fold_convert (ssizetype, offset_iv.base);
drb->init = init;
drb->step = step;
if (known_misalignment (base_misalignment, base_alignment,
&drb->base_misalignment))
drb->base_alignment = base_alignment;
else
{
drb->base_alignment = known_alignment (base_misalignment);
drb->base_misalignment = 0;
}
drb->offset_alignment = highest_pow2_factor (offset_iv.base);
drb->step_alignment = highest_pow2_factor (step);
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "success.\n");
return true;
}
/* Return true if OP is a valid component reference for a DR access
function. This accepts a subset of what handled_component_p accepts. */
static bool
access_fn_component_p (tree op)
{
switch (TREE_CODE (op))
{
case REALPART_EXPR:
case IMAGPART_EXPR:
case ARRAY_REF:
return true;
case COMPONENT_REF:
return TREE_CODE (TREE_TYPE (TREE_OPERAND (op, 0))) == RECORD_TYPE;
default:
return false;
}
}
/* Determines the base object and the list of indices of memory reference
DR, analyzed in LOOP and instantiated before NEST. */
static void
dr_analyze_indices (struct data_reference *dr, edge nest, loop_p loop)
{
vec<tree> access_fns = vNULL;
tree ref, op;
tree base, off, access_fn;
/* If analyzing a basic-block there are no indices to analyze
and thus no access functions. */
if (!nest)
{
DR_BASE_OBJECT (dr) = DR_REF (dr);
DR_ACCESS_FNS (dr).create (0);
return;
}
ref = DR_REF (dr);
/* REALPART_EXPR and IMAGPART_EXPR can be handled like accesses
into a two element array with a constant index. The base is
then just the immediate underlying object. */
if (TREE_CODE (ref) == REALPART_EXPR)
{
ref = TREE_OPERAND (ref, 0);
access_fns.safe_push (integer_zero_node);
}
else if (TREE_CODE (ref) == IMAGPART_EXPR)
{
ref = TREE_OPERAND (ref, 0);
access_fns.safe_push (integer_one_node);
}
/* Analyze access functions of dimensions we know to be independent.
The list of component references handled here should be kept in
sync with access_fn_component_p. */
while (handled_component_p (ref))
{
if (TREE_CODE (ref) == ARRAY_REF)
{
op = TREE_OPERAND (ref, 1);
access_fn = analyze_scalar_evolution (loop, op);
access_fn = instantiate_scev (nest, loop, access_fn);
access_fns.safe_push (access_fn);
}
else if (TREE_CODE (ref) == COMPONENT_REF
&& TREE_CODE (TREE_TYPE (TREE_OPERAND (ref, 0))) == RECORD_TYPE)
{
/* For COMPONENT_REFs of records (but not unions!) use the
FIELD_DECL offset as constant access function so we can
disambiguate a[i].f1 and a[i].f2. */
tree off = component_ref_field_offset (ref);
off = size_binop (PLUS_EXPR,
size_binop (MULT_EXPR,
fold_convert (bitsizetype, off),
bitsize_int (BITS_PER_UNIT)),
DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref, 1)));
access_fns.safe_push (off);
}
else
/* If we have an unhandled component we could not translate
to an access function stop analyzing. We have determined
our base object in this case. */
break;
ref = TREE_OPERAND (ref, 0);
}
/* If the address operand of a MEM_REF base has an evolution in the
analyzed nest, add it as an additional independent access-function. */
if (TREE_CODE (ref) == MEM_REF)
{
op = TREE_OPERAND (ref, 0);
access_fn = analyze_scalar_evolution (loop, op);
access_fn = instantiate_scev (nest, loop, access_fn);
if (TREE_CODE (access_fn) == POLYNOMIAL_CHREC)
{
tree orig_type;
tree memoff = TREE_OPERAND (ref, 1);
base = initial_condition (access_fn);
orig_type = TREE_TYPE (base);
STRIP_USELESS_TYPE_CONVERSION (base);
split_constant_offset (base, &base, &off);
STRIP_USELESS_TYPE_CONVERSION (base);
/* Fold the MEM_REF offset into the evolutions initial
value to make more bases comparable. */
if (!integer_zerop (memoff))
{
off = size_binop (PLUS_EXPR, off,
fold_convert (ssizetype, memoff));
memoff = build_int_cst (TREE_TYPE (memoff), 0);
}
/* Adjust the offset so it is a multiple of the access type
size and thus we separate bases that can possibly be used
to produce partial overlaps (which the access_fn machinery
cannot handle). */
wide_int rem;
if (TYPE_SIZE_UNIT (TREE_TYPE (ref))
&& TREE_CODE (TYPE_SIZE_UNIT (TREE_TYPE (ref))) == INTEGER_CST
&& !integer_zerop (TYPE_SIZE_UNIT (TREE_TYPE (ref))))
rem = wi::mod_trunc
(wi::to_wide (off),
wi::to_wide (TYPE_SIZE_UNIT (TREE_TYPE (ref))),
SIGNED);
else
/* If we can't compute the remainder simply force the initial
condition to zero. */
rem = wi::to_wide (off);
off = wide_int_to_tree (ssizetype, wi::to_wide (off) - rem);
memoff = wide_int_to_tree (TREE_TYPE (memoff), rem);
/* And finally replace the initial condition. */
access_fn = chrec_replace_initial_condition
(access_fn, fold_convert (orig_type, off));
/* ??? This is still not a suitable base object for
dr_may_alias_p - the base object needs to be an
access that covers the object as whole. With
an evolution in the pointer this cannot be
guaranteed.
As a band-aid, mark the access so we can special-case
it in dr_may_alias_p. */
tree old = ref;
ref = fold_build2_loc (EXPR_LOCATION (ref),
MEM_REF, TREE_TYPE (ref),
base, memoff);
MR_DEPENDENCE_CLIQUE (ref) = MR_DEPENDENCE_CLIQUE (old);
MR_DEPENDENCE_BASE (ref) = MR_DEPENDENCE_BASE (old);
DR_UNCONSTRAINED_BASE (dr) = true;
access_fns.safe_push (access_fn);
}
}
else if (DECL_P (ref))
{
/* Canonicalize DR_BASE_OBJECT to MEM_REF form. */
ref = build2 (MEM_REF, TREE_TYPE (ref),
build_fold_addr_expr (ref),
build_int_cst (reference_alias_ptr_type (ref), 0));
}
DR_BASE_OBJECT (dr) = ref;
DR_ACCESS_FNS (dr) = access_fns;
}
/* Extracts the alias analysis information from the memory reference DR. */
static void
dr_analyze_alias (struct data_reference *dr)
{
tree ref = DR_REF (dr);
tree base = get_base_address (ref), addr;
if (INDIRECT_REF_P (base)
|| TREE_CODE (base) == MEM_REF)
{
addr = TREE_OPERAND (base, 0);
if (TREE_CODE (addr) == SSA_NAME)
DR_PTR_INFO (dr) = SSA_NAME_PTR_INFO (addr);
}
}
/* Frees data reference DR. */
void
free_data_ref (data_reference_p dr)
{
DR_ACCESS_FNS (dr).release ();
free (dr);
}
/* 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. */
struct data_reference *
create_data_ref (edge nest, loop_p loop, tree memref, gimple *stmt,
bool is_read, bool is_conditional_in_stmt)
{
struct data_reference *dr;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Creating dr for ");
print_generic_expr (dump_file, memref, TDF_SLIM);
fprintf (dump_file, "\n");
}
dr = XCNEW (struct data_reference);
DR_STMT (dr) = stmt;
DR_REF (dr) = memref;
DR_IS_READ (dr) = is_read;
DR_IS_CONDITIONAL_IN_STMT (dr) = is_conditional_in_stmt;
dr_analyze_innermost (&DR_INNERMOST (dr), memref,
nest != NULL ? loop : NULL);
dr_analyze_indices (dr, nest, loop);
dr_analyze_alias (dr);
if (dump_file && (dump_flags & TDF_DETAILS))
{
unsigned i;
fprintf (dump_file, "\tbase_address: ");
print_generic_expr (dump_file, DR_BASE_ADDRESS (dr), TDF_SLIM);
fprintf (dump_file, "\n\toffset from base address: ");
print_generic_expr (dump_file, DR_OFFSET (dr), TDF_SLIM);
fprintf (dump_file, "\n\tconstant offset from base address: ");
print_generic_expr (dump_file, DR_INIT (dr), TDF_SLIM);
fprintf (dump_file, "\n\tstep: ");
print_generic_expr (dump_file, DR_STEP (dr), TDF_SLIM);
fprintf (dump_file, "\n\tbase alignment: %d", DR_BASE_ALIGNMENT (dr));
fprintf (dump_file, "\n\tbase misalignment: %d",
DR_BASE_MISALIGNMENT (dr));
fprintf (dump_file, "\n\toffset alignment: %d",
DR_OFFSET_ALIGNMENT (dr));
fprintf (dump_file, "\n\tstep alignment: %d", DR_STEP_ALIGNMENT (dr));
fprintf (dump_file, "\n\tbase_object: ");
print_generic_expr (dump_file, DR_BASE_OBJECT (dr), TDF_SLIM);
fprintf (dump_file, "\n");
for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
{
fprintf (dump_file, "\tAccess function %d: ", i);
print_generic_stmt (dump_file, DR_ACCESS_FN (dr, i), TDF_SLIM);
}
}
return dr;
}
/* A helper function computes order between two tree epxressions 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. */
int
data_ref_compare_tree (tree t1, tree t2)
{
int i, cmp;
enum tree_code code;
char tclass;
if (t1 == t2)
return 0;
if (t1 == NULL)
return -1;
if (t2 == NULL)
return 1;
STRIP_USELESS_TYPE_CONVERSION (t1);
STRIP_USELESS_TYPE_CONVERSION (t2);
if (t1 == t2)
return 0;
if (TREE_CODE (t1) != TREE_CODE (t2)
&& ! (CONVERT_EXPR_P (t1) && CONVERT_EXPR_P (t2)))
return TREE_CODE (t1) < TREE_CODE (t2) ? -1 : 1;
code = TREE_CODE (t1);
switch (code)
{
case INTEGER_CST:
return tree_int_cst_compare (t1, t2);
case STRING_CST:
if (TREE_STRING_LENGTH (t1) != TREE_STRING_LENGTH (t2))
return TREE_STRING_LENGTH (t1) < TREE_STRING_LENGTH (t2) ? -1 : 1;
return memcmp (TREE_STRING_POINTER (t1), TREE_STRING_POINTER (t2),
TREE_STRING_LENGTH (t1));
case SSA_NAME:
if (SSA_NAME_VERSION (t1) != SSA_NAME_VERSION (t2))
return SSA_NAME_VERSION (t1) < SSA_NAME_VERSION (t2) ? -1 : 1;
break;
default:
if (POLY_INT_CST_P (t1))
return compare_sizes_for_sort (wi::to_poly_widest (t1),
wi::to_poly_widest (t2));
tclass = TREE_CODE_CLASS (code);
/* For decls, compare their UIDs. */
if (tclass == tcc_declaration)
{
if (DECL_UID (t1) != DECL_UID (t2))
return DECL_UID (t1) < DECL_UID (t2) ? -1 : 1;
break;
}
/* For expressions, compare their operands recursively. */
else if (IS_EXPR_CODE_CLASS (tclass))
{
for (i = TREE_OPERAND_LENGTH (t1) - 1; i >= 0; --i)
{
cmp = data_ref_compare_tree (TREE_OPERAND (t1, i),
TREE_OPERAND (t2, i));
if (cmp != 0)
return cmp;
}
}
else
gcc_unreachable ();
}
return 0;
}
/* Return TRUE it's possible to resolve data dependence DDR by runtime alias
check. */
bool
runtime_alias_check_p (ddr_p ddr, struct loop *loop, bool speed_p)
{
if (dump_enabled_p ())
{
dump_printf (MSG_NOTE, "consider run-time aliasing test between ");
dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (DDR_A (ddr)));
dump_printf (MSG_NOTE, " and ");
dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (DDR_B (ddr)));
dump_printf (MSG_NOTE, "\n");
}
if (!speed_p)
{
if (dump_enabled_p ())
dump_printf (MSG_MISSED_OPTIMIZATION,
"runtime alias check not supported when optimizing "
"for size.\n");
return false;
}
/* FORNOW: We don't support versioning with outer-loop in either
vectorization or loop distribution. */
if (loop != NULL && loop->inner != NULL)
{
if (dump_enabled_p ())
dump_printf (MSG_MISSED_OPTIMIZATION,
"runtime alias check not supported for outer loop.\n");
return false;
}
return true;
}
/* 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. */
static bool
operator == (const dr_with_seg_len& d1,
const dr_with_seg_len& d2)
{
return (operand_equal_p (DR_BASE_ADDRESS (d1.dr),
DR_BASE_ADDRESS (d2.dr), 0)
&& data_ref_compare_tree (DR_OFFSET (d1.dr), DR_OFFSET (d2.dr)) == 0
&& data_ref_compare_tree (DR_INIT (d1.dr), DR_INIT (d2.dr)) == 0
&& data_ref_compare_tree (d1.seg_len, d2.seg_len) == 0
&& known_eq (d1.access_size, d2.access_size)
&& d1.align == d2.align);
}
/* Comparison function for sorting objects of dr_with_seg_len_pair_t
so that we can combine aliasing checks in one scan. */
static int
comp_dr_with_seg_len_pair (const void *pa_, const void *pb_)
{
const dr_with_seg_len_pair_t* pa = (const dr_with_seg_len_pair_t *) pa_;
const dr_with_seg_len_pair_t* pb = (const dr_with_seg_len_pair_t *) pb_;
const dr_with_seg_len &a1 = pa->first, &a2 = pa->second;
const dr_with_seg_len &b1 = pb->first, &b2 = pb->second;
/* For DR pairs (a, b) and (c, d), we only consider to merge the alias checks
if a and c have the same basic address snd step, and b and d have the same
address and step. Therefore, if any a&c or b&d don't have the same address
and step, we don't care the order of those two pairs after sorting. */
int comp_res;
if ((comp_res = data_ref_compare_tree (DR_BASE_ADDRESS (a1.dr),
DR_BASE_ADDRESS (b1.dr))) != 0)
return comp_res;
if ((comp_res = data_ref_compare_tree (DR_BASE_ADDRESS (a2.dr),
DR_BASE_ADDRESS (b2.dr))) != 0)
return comp_res;
if ((comp_res = data_ref_compare_tree (DR_STEP (a1.dr),
DR_STEP (b1.dr))) != 0)
return comp_res;
if ((comp_res = data_ref_compare_tree (DR_STEP (a2.dr),
DR_STEP (b2.dr))) != 0)
return comp_res;
if ((comp_res = data_ref_compare_tree (DR_OFFSET (a1.dr),
DR_OFFSET (b1.dr))) != 0)
return comp_res;
if ((comp_res = data_ref_compare_tree (DR_INIT (a1.dr),
DR_INIT (b1.dr))) != 0)
return comp_res;
if ((comp_res = data_ref_compare_tree (DR_OFFSET (a2.dr),
DR_OFFSET (b2.dr))) != 0)
return comp_res;
if ((comp_res = data_ref_compare_tree (DR_INIT (a2.dr),
DR_INIT (b2.dr))) != 0)
return comp_res;
return 0;
}
/* 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. */
void
prune_runtime_alias_test_list (vec<dr_with_seg_len_pair_t> *alias_pairs,
poly_uint64)
{
/* Sort the collected data ref pairs so that we can scan them once to
combine all possible aliasing checks. */
alias_pairs->qsort (comp_dr_with_seg_len_pair);
/* Scan the sorted dr pairs and check if we can combine alias checks
of two neighboring dr pairs. */
for (size_t i = 1; i < alias_pairs->length (); ++i)
{
/* Deal with two ddrs (dr_a1, dr_b1) and (dr_a2, dr_b2). */
dr_with_seg_len *dr_a1 = &(*alias_pairs)[i-1].first,
*dr_b1 = &(*alias_pairs)[i-1].second,
*dr_a2 = &(*alias_pairs)[i].first,
*dr_b2 = &(*alias_pairs)[i].second;
/* Remove duplicate data ref pairs. */
if (*dr_a1 == *dr_a2 && *dr_b1 == *dr_b2)
{
if (dump_enabled_p ())
{
dump_printf (MSG_NOTE, "found equal ranges ");
dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_a1->dr));
dump_printf (MSG_NOTE, ", ");
dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_b1->dr));
dump_printf (MSG_NOTE, " and ");
dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_a2->dr));
dump_printf (MSG_NOTE, ", ");
dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_b2->dr));
dump_printf (MSG_NOTE, "\n");
}
alias_pairs->ordered_remove (i--);
continue;
}
if (*dr_a1 == *dr_a2 || *dr_b1 == *dr_b2)
{
/* We consider the case that DR_B1 and DR_B2 are same memrefs,
and DR_A1 and DR_A2 are two consecutive memrefs. */
if (*dr_a1 == *dr_a2)
{
std::swap (dr_a1, dr_b1);
std::swap (dr_a2, dr_b2);
}
poly_int64 init_a1, init_a2;
/* Only consider cases in which the distance between the initial
DR_A1 and the initial DR_A2 is known at compile time. */
if (!operand_equal_p (DR_BASE_ADDRESS (dr_a1->dr),
DR_BASE_ADDRESS (dr_a2->dr), 0)
|| !operand_equal_p (DR_OFFSET (dr_a1->dr),
DR_OFFSET (dr_a2->dr), 0)
|| !poly_int_tree_p (DR_INIT (dr_a1->dr), &init_a1)
|| !poly_int_tree_p (DR_INIT (dr_a2->dr), &init_a2))
continue;
/* Don't combine if we can't tell which one comes first. */
if (!ordered_p (init_a1, init_a2))
continue;
/* Make sure dr_a1 starts left of dr_a2. */
if (maybe_gt (init_a1, init_a2))
{
std::swap (*dr_a1, *dr_a2);
std::swap (init_a1, init_a2);
}
/* Work out what the segment length would be if we did combine
DR_A1 and DR_A2:
- If DR_A1 and DR_A2 have equal lengths, that length is
also the combined length.
- If DR_A1 and DR_A2 both have negative "lengths", the combined
length is the lower bound on those lengths.
- If DR_A1 and DR_A2 both have positive lengths, the combined
length is the upper bound on those lengths.
Other cases are unlikely to give a useful combination.
The lengths both have sizetype, so the sign is taken from
the step instead. */
if (!operand_equal_p (dr_a1->seg_len, dr_a2->seg_len, 0))
{
poly_uint64 seg_len_a1, seg_len_a2;
if (!poly_int_tree_p (dr_a1->seg_len, &seg_len_a1)
|| !poly_int_tree_p (dr_a2->seg_len, &seg_len_a2))
continue;
tree indicator_a = dr_direction_indicator (dr_a1->dr);
if (TREE_CODE (indicator_a) != INTEGER_CST)
continue;
tree indicator_b = dr_direction_indicator (dr_a2->dr);
if (TREE_CODE (indicator_b) != INTEGER_CST)
continue;
int sign_a = tree_int_cst_sgn (indicator_a);
int sign_b = tree_int_cst_sgn (indicator_b);
poly_uint64 new_seg_len;
if (sign_a <= 0 && sign_b <= 0)
new_seg_len = lower_bound (seg_len_a1, seg_len_a2);
else if (sign_a >= 0 && sign_b >= 0)
new_seg_len = upper_bound (seg_len_a1, seg_len_a2);
else
continue;
dr_a1->seg_len = build_int_cst (TREE_TYPE (dr_a1->seg_len),
new_seg_len);
dr_a1->align = MIN (dr_a1->align, known_alignment (new_seg_len));
}
/* This is always positive due to the swap above. */
poly_uint64 diff = init_a2 - init_a1;
/* The new check will start at DR_A1. Make sure that its access
size encompasses the initial DR_A2. */
if (maybe_lt (dr_a1->access_size, diff + dr_a2->access_size))
{
dr_a1->access_size = upper_bound (dr_a1->access_size,
diff + dr_a2->access_size);
unsigned int new_align = known_alignment (dr_a1->access_size);
dr_a1->align = MIN (dr_a1->align, new_align);
}
if (dump_enabled_p ())
{
dump_printf (MSG_NOTE, "merging ranges for ");
dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_a1->dr));
dump_printf (MSG_NOTE, ", ");
dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_b1->dr));
dump_printf (MSG_NOTE, " and ");
dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_a2->dr));
dump_printf (MSG_NOTE, ", ");
dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_b2->dr));
dump_printf (MSG_NOTE, "\n");
}
alias_pairs->ordered_remove (i);
i--;
}
}
}
/* Given LOOP's two data references and segment lengths described by DR_A
and DR_B, create expression checking if the two addresses ranges intersect
with each other based on index of the two addresses. This can only be
done if DR_A and DR_B referring to the same (array) object and the index
is the only difference. For example:
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:
(i_0 + 4 < j_0 || j_0 + 4 < i_0)
Note evolution step of index needs to be considered in comparison. */
static bool
create_intersect_range_checks_index (struct loop *loop, tree *cond_expr,
const dr_with_seg_len& dr_a,
const dr_with_seg_len& dr_b)
{
if (integer_zerop (DR_STEP (dr_a.dr))
|| integer_zerop (DR_STEP (dr_b.dr))
|| DR_NUM_DIMENSIONS (dr_a.dr) != DR_NUM_DIMENSIONS (dr_b.dr))
return false;
poly_uint64 seg_len1, seg_len2;
if (!poly_int_tree_p (dr_a.seg_len, &seg_len1)
|| !poly_int_tree_p (dr_b.seg_len, &seg_len2))
return false;
if (!tree_fits_shwi_p (DR_STEP (dr_a.dr)))
return false;
if (!operand_equal_p (DR_BASE_OBJECT (dr_a.dr), DR_BASE_OBJECT (dr_b.dr), 0))
return false;
if (!operand_equal_p (DR_STEP (dr_a.dr), DR_STEP (dr_b.dr), 0))
return false;
gcc_assert (TREE_CODE (DR_STEP (dr_a.dr)) == INTEGER_CST);
bool neg_step = tree_int_cst_compare (DR_STEP (dr_a.dr), size_zero_node) < 0;
unsigned HOST_WIDE_INT abs_step = tree_to_shwi (DR_STEP (dr_a.dr));
if (neg_step)
{
abs_step = -abs_step;
seg_len1 = -seg_len1;
seg_len2 = -seg_len2;
}
else
{
/* Include the access size in the length, so that we only have one
tree addition below. */
seg_len1 += dr_a.access_size;
seg_len2 += dr_b.access_size;
}
/* Infer the number of iterations with which the memory segment is accessed
by DR. In other words, alias is checked if memory segment accessed by
DR_A in some iterations intersect with memory segment accessed by DR_B
in the same amount iterations.
Note segnment length is a linear function of number of iterations with
DR_STEP as the coefficient. */
poly_uint64 niter_len1, niter_len2;
if (!can_div_trunc_p (seg_len1 + abs_step - 1, abs_step, &niter_len1)
|| !can_div_trunc_p (seg_len2 + abs_step - 1, abs_step, &niter_len2))
return false;
poly_uint64 niter_access1 = 0, niter_access2 = 0;
if (neg_step)
{
/* Divide each access size by the byte step, rounding up. */
if (!can_div_trunc_p (dr_a.access_size - abs_step - 1,
abs_step, &niter_access1)
|| !can_div_trunc_p (dr_b.access_size + abs_step - 1,
abs_step, &niter_access2))
return false;
}
unsigned int i;
for (i = 0; i < DR_NUM_DIMENSIONS (dr_a.dr); i++)
{
tree access1 = DR_ACCESS_FN (dr_a.dr, i);
tree access2 = DR_ACCESS_FN (dr_b.dr, i);
/* Two indices must be the same if they are not scev, or not scev wrto
current loop being vecorized. */
if (TREE_CODE (access1) != POLYNOMIAL_CHREC
|| TREE_CODE (access2) != POLYNOMIAL_CHREC
|| CHREC_VARIABLE (access1) != (unsigned)loop->num
|| CHREC_VARIABLE (access2) != (unsigned)loop->num)
{
if (operand_equal_p (access1, access2, 0))
continue;
return false;
}
/* The two indices must have the same step. */
if (!operand_equal_p (CHREC_RIGHT (access1), CHREC_RIGHT (access2), 0))
return false;
tree idx_step = CHREC_RIGHT (access1);
/* Index must have const step, otherwise DR_STEP won't be constant. */
gcc_assert (TREE_CODE (idx_step) == INTEGER_CST);
/* Index must evaluate in the same direction as DR. */
gcc_assert (!neg_step || tree_int_cst_sign_bit (idx_step) == 1);
tree min1 = CHREC_LEFT (access1);
tree min2 = CHREC_LEFT (access2);
if (!types_compatible_p (TREE_TYPE (min1), TREE_TYPE (min2)))
return false;
/* Ideally, alias can be checked against loop's control IV, but we
need to prove linear mapping between control IV and reference
index. Although that should be true, we check against (array)
index of data reference. Like segment length, index length is
linear function of the number of iterations with index_step as
the coefficient, i.e, niter_len * idx_step. */
tree idx_len1 = fold_build2 (MULT_EXPR, TREE_TYPE (min1), idx_step,
build_int_cst (TREE_TYPE (min1),
niter_len1));
tree idx_len2 = fold_build2 (MULT_EXPR, TREE_TYPE (min2), idx_step,
build_int_cst (TREE_TYPE (min2),
niter_len2));
tree max1 = fold_build2 (PLUS_EXPR, TREE_TYPE (min1), min1, idx_len1);
tree max2 = fold_build2 (PLUS_EXPR, TREE_TYPE (min2), min2, idx_len2);
/* Adjust ranges for negative step. */
if (neg_step)
{
/* IDX_LEN1 and IDX_LEN2 are negative in this case. */
std::swap (min1, max1);
std::swap (min2, max2);
/* As with the lengths just calculated, we've measured the access
sizes in iterations, so multiply them by the index step. */
tree idx_access1
= fold_build2 (MULT_EXPR, TREE_TYPE (min1), idx_step,
build_int_cst (TREE_TYPE (min1), niter_access1));
tree idx_access2
= fold_build2 (MULT_EXPR, TREE_TYPE (min2), idx_step,
build_int_cst (TREE_TYPE (min2), niter_access2));
/* MINUS_EXPR because the above values are negative. */
max1 = fold_build2 (MINUS_EXPR, TREE_TYPE (max1), max1, idx_access1);
max2 = fold_build2 (MINUS_EXPR, TREE_TYPE (max2), max2, idx_access2);
}
tree part_cond_expr
= fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
fold_build2 (LE_EXPR, boolean_type_node, max1, min2),
fold_build2 (LE_EXPR, boolean_type_node, max2, min1));
if (*cond_expr)
*cond_expr = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
*cond_expr, part_cond_expr);
else
*cond_expr = part_cond_expr;
}
return true;
}
/* 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. */
static void
get_segment_min_max (const dr_with_seg_len &d, tree *seg_min_out,
tree *seg_max_out, HOST_WIDE_INT align)
{
/* Each access has the following pattern:
<- |seg_len| ->
<--- A: -ve step --->
+-----+-------+-----+-------+-----+
| n-1 | ,.... | 0 | ..... | n-1 |
+-----+-------+-----+-------+-----+
<--- B: +ve step --->
<- |seg_len| ->
|
base address
where "n" is the number of scalar iterations covered by the segment.
(This should be VF for a particular pair if we know that both steps
are the same, otherwise it will be the full number of scalar loop
iterations.)
A is the range of bytes accessed when the step is negative,
B is the range when the step is positive.
If the access size is "access_size" bytes, the lowest addressed byte is:
base + (step < 0 ? seg_len : 0) [LB]
and the highest addressed byte is always below:
base + (step < 0 ? 0 : seg_len) + access_size [UB]
Thus:
LB <= ADDR < UB
If ALIGN is nonzero, all three values are aligned to at least ALIGN
bytes, so:
LB <= ADDR <= UB - ALIGN
where "- ALIGN" folds naturally with the "+ access_size" and often
cancels it out.
We don't try to simplify LB and UB beyond this (e.g. by using
MIN and MAX based on whether seg_len rather than the stride is
negative) because it is possible for the absolute size of the
segment to overflow the range of a ssize_t.
Keeping the pointer_plus outside of the cond_expr should allow
the cond_exprs to be shared with other alias checks. */
tree indicator = dr_direction_indicator (d.dr);
tree neg_step = fold_build2 (LT_EXPR, boolean_type_node,
fold_convert (ssizetype, indicator),
ssize_int (0));
tree addr_base = fold_build_pointer_plus (DR_BASE_ADDRESS (d.dr),
DR_OFFSET (d.dr));
addr_base = fold_build_pointer_plus (addr_base, DR_INIT (d.dr));
tree seg_len
= fold_convert (sizetype, rewrite_to_non_trapping_overflow (d.seg_len));
tree min_reach = fold_build3 (COND_EXPR, sizetype, neg_step,
seg_len, size_zero_node);
tree max_reach = fold_build3 (COND_EXPR, sizetype, neg_step,
size_zero_node, seg_len);
max_reach = fold_build2 (PLUS_EXPR, sizetype, max_reach,
size_int (d.access_size - align));
*seg_min_out = fold_build_pointer_plus (addr_base, min_reach);
*seg_max_out = fold_build_pointer_plus (addr_base, max_reach);
}
/* Given two data references and segment lengths described by DR_A and DR_B,
create expression checking if the two addresses ranges intersect with
each other:
((DR_A_addr_0 + DR_A_segment_length_0) <= DR_B_addr_0)
|| (DR_B_addr_0 + DER_B_segment_length_0) <= DR_A_addr_0)) */
static void
create_intersect_range_checks (struct loop *loop, tree *cond_expr,
const dr_with_seg_len& dr_a,
const dr_with_seg_len& dr_b)
{
*cond_expr = NULL_TREE;
if (create_intersect_range_checks_index (loop, cond_expr, dr_a, dr_b))
return;
unsigned HOST_WIDE_INT min_align;
tree_code cmp_code;
if (TREE_CODE (DR_STEP (dr_a.dr)) == INTEGER_CST
&& TREE_CODE (DR_STEP (dr_b.dr)) == INTEGER_CST)
{
/* In this case adding access_size to seg_len is likely to give
a simple X * step, where X is either the number of scalar
iterations or the vectorization factor. We're better off
keeping that, rather than subtracting an alignment from it.
In this case the maximum values are exclusive and so there is
no alias if the maximum of one segment equals the minimum
of another. */
min_align = 0;
cmp_code = LE_EXPR;
}
else
{
/* Calculate the minimum alignment shared by all four pointers,
then arrange for this alignment to be subtracted from the
exclusive maximum values to get inclusive maximum values.
This "- min_align" is cumulative with a "+ access_size"
in the calculation of the maximum values. In the best
(and common) case, the two cancel each other out, leaving
us with an inclusive bound based only on seg_len. In the
worst case we're simply adding a smaller number than before.
Because the maximum values are inclusive, there is an alias
if the maximum value of one segment is equal to the minimum
value of the other. */
min_align = MIN (dr_a.align, dr_b.align);
cmp_code = LT_EXPR;
}
tree seg_a_min, seg_a_max, seg_b_min, seg_b_max;
get_segment_min_max (dr_a, &seg_a_min, &seg_a_max, min_align);
get_segment_min_max (dr_b, &seg_b_min, &seg_b_max, min_align);
*cond_expr
= fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
fold_build2 (cmp_code, boolean_type_node, seg_a_max, seg_b_min),
fold_build2 (cmp_code, boolean_type_node, seg_b_max, seg_a_min));
}
/* 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. */
void
create_runtime_alias_checks (struct loop *loop,
vec<dr_with_seg_len_pair_t> *alias_pairs,
tree * cond_expr)
{
tree part_cond_expr;
fold_defer_overflow_warnings ();
for (size_t i = 0, s = alias_pairs->length (); i < s; ++i)
{
const dr_with_seg_len& dr_a = (*alias_pairs)[i].first;
const dr_with_seg_len& dr_b = (*alias_pairs)[i].second;
if (dump_enabled_p ())
{
dump_printf (MSG_NOTE, "create runtime check for data references ");
dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_a.dr));
dump_printf (MSG_NOTE, " and ");
dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_b.dr));
dump_printf (MSG_NOTE, "\n");
}
/* Create condition expression for each pair data references. */
create_intersect_range_checks (loop, &part_cond_expr, dr_a, dr_b);
if (*cond_expr)
*cond_expr = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
*cond_expr, part_cond_expr);
else
*cond_expr = part_cond_expr;
}
fold_undefer_and_ignore_overflow_warnings ();
}
/* Check if OFFSET1 and OFFSET2 (DR_OFFSETs of some data-refs) are identical
expressions. */
static bool
dr_equal_offsets_p1 (tree offset1, tree offset2)
{
bool res;
STRIP_NOPS (offset1);
STRIP_NOPS (offset2);
if (offset1 == offset2)
return true;
if (TREE_CODE (offset1) != TREE_CODE (offset2)
|| (!BINARY_CLASS_P (offset1) && !UNARY_CLASS_P (offset1)))
return false;
res = dr_equal_offsets_p1 (TREE_OPERAND (offset1, 0),
TREE_OPERAND (offset2, 0));
if (!res || !BINARY_CLASS_P (offset1))
return res;
res = dr_equal_offsets_p1 (TREE_OPERAND (offset1, 1),
TREE_OPERAND (offset2, 1));
return res;
}
/* Check if DRA and DRB have equal offsets. */
bool
dr_equal_offsets_p (struct data_reference *dra,
struct data_reference *drb)
{
tree offset1, offset2;
offset1 = DR_OFFSET (dra);
offset2 = DR_OFFSET (drb);
return dr_equal_offsets_p1 (offset1, offset2);
}
/* Returns true if FNA == FNB. */
static bool
affine_function_equal_p (affine_fn fna, affine_fn fnb)
{
unsigned i, n = fna.length ();
if (n != fnb.length ())
return false;
for (i = 0; i < n; i++)
if (!operand_equal_p (fna[i], fnb[i], 0))
return false;
return true;
}
/* If all the functions in CF are the same, returns one of them,
otherwise returns NULL. */
static affine_fn
common_affine_function (conflict_function *cf)
{
unsigned i;
affine_fn comm;
if (!CF_NONTRIVIAL_P (cf))
return affine_fn ();
comm = cf->fns[0];
for (i = 1; i < cf->n; i++)
if (!affine_function_equal_p (comm, cf->fns[i]))
return affine_fn ();
return comm;
}
/* Returns the base of the affine function FN. */
static tree
affine_function_base (affine_fn fn)
{
return fn[0];
}
/* Returns true if FN is a constant. */
static bool
affine_function_constant_p (affine_fn fn)
{
unsigned i;
tree coef;
for (i = 1; fn.iterate (i, &coef); i++)
if (!integer_zerop (coef))
return false;
return true;
}
/* Returns true if FN is the zero constant function. */
static bool
affine_function_zero_p (affine_fn fn)
{
return (integer_zerop (affine_function_base (fn))
&& affine_function_constant_p (fn));
}
/* Returns a signed integer type with the largest precision from TA
and TB. */
static tree
signed_type_for_types (tree ta, tree tb)
{
if (TYPE_PRECISION (ta) > TYPE_PRECISION (tb))
return signed_type_for (ta);
else
return signed_type_for (tb);
}
/* Applies operation OP on affine functions FNA and FNB, and returns the
result. */
static affine_fn
affine_fn_op (enum tree_code op, affine_fn fna, affine_fn fnb)
{
unsigned i, n, m;
affine_fn ret;
tree coef;
if (fnb.length () > fna.length ())
{
n = fna.length ();
m = fnb.length ();
}
else
{
n = fnb.length ();
m = fna.length ();
}
ret.create (m);
for (i = 0; i < n; i++)
{
tree type = signed_type_for_types (TREE_TYPE (fna[i]),
TREE_TYPE (fnb[i]));
ret.quick_push (fold_build2 (op, type, fna[i], fnb[i]));
}
for (; fna.iterate (i, &coef); i++)
ret.quick_push (fold_build2 (op, signed_type_for (TREE_TYPE (coef)),
coef, integer_zero_node));
for (; fnb.iterate (i, &coef); i++)
ret.quick_push (fold_build2 (op, signed_type_for (TREE_TYPE (coef)),
integer_zero_node, coef));
return ret;
}
/* Returns the sum of affine functions FNA and FNB. */
static affine_fn
affine_fn_plus (affine_fn fna, affine_fn fnb)
{
return affine_fn_op (PLUS_EXPR, fna, fnb);
}
/* Returns the difference of affine functions FNA and FNB. */
static affine_fn
affine_fn_minus (affine_fn fna, affine_fn fnb)
{
return affine_fn_op (MINUS_EXPR, fna, fnb);
}
/* Frees affine function FN. */
static void
affine_fn_free (affine_fn fn)
{
fn.release ();
}
/* Determine for each subscript in the data dependence relation DDR
the distance. */
static void
compute_subscript_distance (struct data_dependence_relation *ddr)
{
conflict_function *cf_a, *cf_b;
affine_fn fn_a, fn_b, diff;
if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
{
unsigned int i;
for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
{
struct subscript *subscript;
subscript = DDR_SUBSCRIPT (ddr, i);
cf_a = SUB_CONFLICTS_IN_A (subscript);
cf_b = SUB_CONFLICTS_IN_B (subscript);
fn_a = common_affine_function (cf_a);
fn_b = common_affine_function (cf_b);
if (!fn_a.exists () || !fn_b.exists ())
{
SUB_DISTANCE (subscript) = chrec_dont_know;
return;
}
diff = affine_fn_minus (fn_a, fn_b);
if (affine_function_constant_p (diff))
SUB_DISTANCE (subscript) = affine_function_base (diff);
else
SUB_DISTANCE (subscript) = chrec_dont_know;
affine_fn_free (diff);
}
}
}
/* Returns the conflict function for "unknown". */
static conflict_function *
conflict_fn_not_known (void)
{
conflict_function *fn = XCNEW (conflict_function);
fn->n = NOT_KNOWN;
return fn;
}
/* Returns the conflict function for "independent". */
static conflict_function *
conflict_fn_no_dependence (void)
{
conflict_function *fn = XCNEW (conflict_function);
fn->n = NO_DEPENDENCE;
return fn;
}
/* Returns true if the address of OBJ is invariant in LOOP. */
static bool
object_address_invariant_in_loop_p (const struct loop *loop, const_tree obj)
{
while (handled_component_p (obj))
{
if (TREE_CODE (obj) == ARRAY_REF)
{
for (int i = 1; i < 4; ++i)
if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, i),
loop->num))
return false;
}
else if (TREE_CODE (obj) == COMPONENT_REF)
{
if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 2),
loop->num))
return false;
}
obj = TREE_OPERAND (obj, 0);
}
if (!INDIRECT_REF_P (obj)
&& TREE_CODE (obj) != MEM_REF)
return true;
return !chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 0),
loop->num);
}
/* 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. */
bool
dr_may_alias_p (const struct data_reference *a, const struct data_reference *b,
bool loop_nest)
{
tree addr_a = DR_BASE_OBJECT (a);
tree addr_b = DR_BASE_OBJECT (b);
/* If we are not processing a loop nest but scalar code we
do not need to care about possible cross-iteration dependences
and thus can process the full original reference. Do so,
similar to how loop invariant motion applies extra offset-based
disambiguation. */
if (!loop_nest)
{
aff_tree off1, off2;
poly_widest_int size1, size2;
get_inner_reference_aff (DR_REF (a), &off1, &size1);
get_inner_reference_aff (DR_REF (b), &off2, &size2);
aff_combination_scale (&off1, -1);
aff_combination_add (&off2, &off1);
if (aff_comb_cannot_overlap_p (&off2, size1, size2))
return false;
}
if ((TREE_CODE (addr_a) == MEM_REF || TREE_CODE (addr_a) == TARGET_MEM_REF)
&& (TREE_CODE (addr_b) == MEM_REF || TREE_CODE (addr_b) == TARGET_MEM_REF)
&& MR_DEPENDENCE_CLIQUE (addr_a) == MR_DEPENDENCE_CLIQUE (addr_b)
&& MR_DEPENDENCE_BASE (addr_a) != MR_DEPENDENCE_BASE (addr_b))
return false;
/* If we had an evolution in a pointer-based MEM_REF BASE_OBJECT we
do not know the size of the base-object. So we cannot do any
offset/overlap based analysis but have to rely on points-to
information only. */
if (TREE_CODE (addr_a) == MEM_REF
&& (DR_UNCONSTRAINED_BASE (a)
|| TREE_CODE (TREE_OPERAND (addr_a, 0)) == SSA_NAME))
{
/* For true dependences we can apply TBAA. */
if (flag_strict_aliasing
&& DR_IS_WRITE (a) && DR_IS_READ (b)
&& !alias_sets_conflict_p (get_alias_set (DR_REF (a)),
get_alias_set (DR_REF (b))))
return false;
if (TREE_CODE (addr_b) == MEM_REF)
return ptr_derefs_may_alias_p (TREE_OPERAND (addr_a, 0),
TREE_OPERAND (addr_b, 0));
else
return ptr_derefs_may_alias_p (TREE_OPERAND (addr_a, 0),
build_fold_addr_expr (addr_b));
}
else if (TREE_CODE (addr_b) == MEM_REF
&& (DR_UNCONSTRAINED_BASE (b)
|| TREE_CODE (TREE_OPERAND (addr_b, 0)) == SSA_NAME))
{
/* For true dependences we can apply TBAA. */
if (flag_strict_aliasing
&& DR_IS_WRITE (a) && DR_IS_READ (b)
&& !alias_sets_conflict_p (get_alias_set (DR_REF (a)),
get_alias_set (DR_REF (b))))
return false;
if (TREE_CODE (addr_a) == MEM_REF)
return ptr_derefs_may_alias_p (TREE_OPERAND (addr_a, 0),
TREE_OPERAND (addr_b, 0));
else
return ptr_derefs_may_alias_p (build_fold_addr_expr (addr_a),
TREE_OPERAND (addr_b, 0));
}
/* Otherwise DR_BASE_OBJECT is an access that covers the whole object
that is being subsetted in the loop nest. */
if (DR_IS_WRITE (a) && DR_IS_WRITE (b))
return refs_output_dependent_p (addr_a, addr_b);
else if (DR_IS_READ (a) && DR_IS_WRITE (b))
return refs_anti_dependent_p (addr_a, addr_b);
return refs_may_alias_p (addr_a, addr_b);
}
/* 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. */
static bool
access_fn_components_comparable_p (tree ref_a, tree ref_b)
{
/* Allow pairs of component refs from the following sets:
{ REALPART_EXPR, IMAGPART_EXPR }
{ COMPONENT_REF }
{ ARRAY_REF }. */
tree_code code_a = TREE_CODE (ref_a);
tree_code code_b = TREE_CODE (ref_b);
if (code_a == IMAGPART_EXPR)
code_a = REALPART_EXPR;
if (code_b == IMAGPART_EXPR)
code_b = REALPART_EXPR;
if (code_a != code_b)
return false;
if (TREE_CODE (ref_a) == COMPONENT_REF)
/* ??? We cannot simply use the type of operand #0 of the refs here as
the Fortran compiler smuggles type punning into COMPONENT_REFs.
Use the DECL_CONTEXT of the FIELD_DECLs instead. */
return (DECL_CONTEXT (TREE_OPERAND (ref_a, 1))
== DECL_CONTEXT (TREE_OPERAND (ref_b, 1)));
return types_compatible_p (TREE_TYPE (TREE_OPERAND (ref_a, 0)),
TREE_TYPE (TREE_OPERAND (ref_b, 0)));
}
/* 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. */
struct data_dependence_relation *
initialize_data_dependence_relation (struct data_reference *a,
struct data_reference *b,
vec<loop_p> loop_nest)
{
struct data_dependence_relation *res;
unsigned int i;
res = XCNEW (struct data_dependence_relation);
DDR_A (res) = a;
DDR_B (res) = b;
DDR_LOOP_NEST (res).create (0);
DDR_SUBSCRIPTS (res).create (0);
DDR_DIR_VECTS (res).create (0);
DDR_DIST_VECTS (res).create (0);
if (a == NULL || b == NULL)
{
DDR_ARE_DEPENDENT (res) = chrec_dont_know;
return res;
}
/* If the data references do not alias, then they are independent. */
if (!dr_may_alias_p (a, b, loop_nest.exists ()))
{
DDR_ARE_DEPENDENT (res) = chrec_known;
return res;
}
unsigned int num_dimensions_a = DR_NUM_DIMENSIONS (a);
unsigned int num_dimensions_b = DR_NUM_DIMENSIONS (b);
if (num_dimensions_a == 0 || num_dimensions_b == 0)
{
DDR_ARE_DEPENDENT (res) = chrec_dont_know;
return res;
}
/* For unconstrained bases, the root (highest-indexed) subscript
describes a variation in the base of the original DR_REF rather
than a component access. We have no type that accurately describes
the new DR_BASE_OBJECT (whose TREE_TYPE describes the type *after*
applying this subscript) so limit the search to the last real
component access.
E.g. for:
void
f (int a[][8], int b[][8])
{
for (int i = 0; i < 8; ++i)
a[i * 2][0] = b[i][0];
}
the a and b accesses have a single ARRAY_REF component reference [0]
but have two subscripts. */
if (DR_UNCONSTRAINED_BASE (a))
num_dimensions_a -= 1;
if (DR_UNCONSTRAINED_BASE (b))
num_dimensions_b -= 1;
/* These structures describe sequences of component references in
DR_REF (A) and DR_REF (B). Each component reference is tied to a
specific access function. */
struct {
/* The sequence starts at DR_ACCESS_FN (A, START_A) of A and
DR_ACCESS_FN (B, START_B) of B (inclusive) and extends to higher
indices. In C notation, these are the indices of the rightmost
component references; e.g. for a sequence .b.c.d, the start
index is for .d. */
unsigned int start_a;
unsigned int start_b;
/* The sequence contains LENGTH consecutive access functions from
each DR. */
unsigned int length;
/* The enclosing objects for the A and B sequences respectively,
i.e. the objects to which DR_ACCESS_FN (A, START_A + LENGTH - 1)
and DR_ACCESS_FN (B, START_B + LENGTH - 1) are applied. */
tree object_a;
tree object_b;
} full_seq = {}, struct_seq = {};
/* Before each iteration of the loop:
- REF_A is what you get after applying DR_ACCESS_FN (A, INDEX_A) and
- REF_B is what you get after applying DR_ACCESS_FN (B, INDEX_B). */
unsigned int index_a = 0;
unsigned int index_b = 0;
tree ref_a = DR_REF (a);
tree ref_b = DR_REF (b);
/* Now walk the component references from the final DR_REFs back up to
the enclosing base objects. Each component reference corresponds
to one access function in the DR, with access function 0 being for
the final DR_REF and the highest-indexed access function being the
one that is applied to the base of the DR.
Look for a sequence of component references whose access functions
are comparable (see access_fn_components_comparable_p). If more
than one such sequence exists, pick the one nearest the base
(which is the leftmost sequence in C notation). Store this sequence
in FULL_SEQ.
For example, if we have:
struct foo { struct bar s; ... } (*a)[10], (*b)[10];
A: a[0][i].s.c.d
B: __real b[0][i].s.e[i].f
(where d is the same type as the real component of f) then the access
functions would be:
0 1 2 3
A: .d .c .s [i]
0 1 2 3 4 5
B: __real .f [i] .e .s [i]
The A0/B2 column isn't comparable, since .d is a COMPONENT_REF
and [i] is an ARRAY_REF. However, the A1/B3 column contains two
COMPONENT_REF accesses for struct bar, so is comparable. Likewise
the A2/B4 column contains two COMPONENT_REF accesses for struct foo,
so is comparable. The A3/B5 column contains two ARRAY_REFs that
index foo[10] arrays, so is again comparable. The sequence is
therefore:
A: [1, 3] (i.e. [i].s.c)
B: [3, 5] (i.e. [i].s.e)
Also look for sequences of component references whose access
functions are comparable and whose enclosing objects have the same
RECORD_TYPE. Store this sequence in STRUCT_SEQ. In the above
example, STRUCT_SEQ would be:
A: [1, 2] (i.e. s.c)
B: [3, 4] (i.e. s.e) */
while (index_a < num_dimensions_a && index_b < num_dimensions_b)
{
/* REF_A and REF_B must be one of the component access types
allowed by dr_analyze_indices. */
gcc_checking_assert (access_fn_component_p (ref_a));
gcc_checking_assert (access_fn_component_p (ref_b));
/* Get the immediately-enclosing objects for REF_A and REF_B,
i.e. the references *before* applying DR_ACCESS_FN (A, INDEX_A)
and DR_ACCESS_FN (B, INDEX_B). */
tree object_a = TREE_OPERAND (ref_a, 0);
tree object_b = TREE_OPERAND (ref_b, 0);
tree type_a = TREE_TYPE (object_a);
tree type_b = TREE_TYPE (object_b);
if (access_fn_components_comparable_p (ref_a, ref_b))
{
/* This pair of component accesses is comparable for dependence
analysis, so we can include DR_ACCESS_FN (A, INDEX_A) and
DR_ACCESS_FN (B, INDEX_B) in the sequence. */
if (full_seq.start_a + full_seq.length != index_a
|| full_seq.start_b + full_seq.length != index_b)
{
/* The accesses don't extend the current sequence,
so start a new one here. */
full_seq.start_a = index_a;
full_seq.start_b = index_b;
full_seq.length = 0;
}
/* Add this pair of references to the sequence. */
full_seq.length += 1;
full_seq.object_a = object_a;
full_seq.object_b = object_b;
/* If the enclosing objects are structures (and thus have the
same RECORD_TYPE), record the new sequence in STRUCT_SEQ. */
if (TREE_CODE (type_a) == RECORD_TYPE)
struct_seq = full_seq;
/* Move to the next containing reference for both A and B. */
ref_a = object_a;
ref_b = object_b;
index_a += 1;
index_b += 1;
continue;
}
/* Try to approach equal type sizes. */
if (!COMPLETE_TYPE_P (type_a)
|| !COMPLETE_TYPE_P (type_b)
|| !tree_fits_uhwi_p (TYPE_SIZE_UNIT (type_a))
|| !tree_fits_uhwi_p (TYPE_SIZE_UNIT (type_b)))
break;
unsigned HOST_WIDE_INT size_a = tree_to_uhwi (TYPE_SIZE_UNIT (type_a));
unsigned HOST_WIDE_INT size_b = tree_to_uhwi (TYPE_SIZE_UNIT (type_b));
if (size_a <= size_b)
{
index_a += 1;
ref_a = object_a;
}
if (size_b <= size_a)
{
index_b += 1;
ref_b = object_b;
}
}
/* See whether FULL_SEQ ends at the base and whether the two bases
are equal. We do not care about TBAA or alignment info so we can
use OEP_ADDRESS_OF to avoid false negatives. */
tree base_a = DR_BASE_OBJECT (a);
tree base_b = DR_BASE_OBJECT (b);
bool same_base_p = (full_seq.start_a + full_seq.length == num_dimensions_a
&& full_seq.start_b + full_seq.length == num_dimensions_b
&& DR_UNCONSTRAINED_BASE (a) == DR_UNCONSTRAINED_BASE (b)
&& operand_equal_p (base_a, base_b, OEP_ADDRESS_OF)
&& types_compatible_p (TREE_TYPE (base_a),
TREE_TYPE (base_b))
&& (!loop_nest.exists ()
|| (object_address_invariant_in_loop_p
(loop_nest[0], base_a))));
/* If the bases are the same, we can include the base variation too.
E.g. the b accesses in:
for (int i = 0; i < n; ++i)
b[i + 4][0] = b[i][0];
have a definite dependence distance of 4, while for:
for (int i = 0; i < n; ++i)
a[i + 4][0] = b[i][0];
the dependence distance depends on the gap between a and b.
If the bases are different then we can only rely on the sequence
rooted at a structure access, since arrays are allowed to overlap
arbitrarily and change shape arbitrarily. E.g. we treat this as
valid code:
int a[256];
...
((int (*)[4][3]) &a[1])[i][0] += ((int (*)[4][3]) &a[2])[i][0];
where two lvalues with the same int[4][3] type overlap, and where
both lvalues are distinct from the object's declared type. */
if (same_base_p)
{
if (DR_UNCONSTRAINED_BASE (a))
full_seq.length += 1;
}
else
full_seq = struct_seq;
/* Punt if we didn't find a suitable sequence. */
if (full_seq.length == 0)
{
DDR_ARE_DEPENDENT (res) = chrec_dont_know;
return res;
}
if (!same_base_p)
{
/* Partial overlap is possible for different bases when strict aliasing
is not in effect. It's also possible if either base involves a union
access; e.g. for:
struct s1 { int a[2]; };
struct s2 { struct s1 b; int c; };
struct s3 { int d; struct s1 e; };
union u { struct s2 f; struct s3 g; } *p, *q;
the s1 at "p->f.b" (base "p->f") partially overlaps the s1 at
"p->g.e" (base "p->g") and might partially overlap the s1 at
"q->g.e" (base "q->g"). */
if (!flag_strict_aliasing
|| ref_contains_union_access_p (full_seq.object_a)
|| ref_contains_union_access_p (full_seq.object_b))
{
DDR_ARE_DEPENDENT (res) = chrec_dont_know;
return res;
}
DDR_COULD_BE_INDEPENDENT_P (res) = true;
if (!loop_nest.exists ()
|| (object_address_invariant_in_loop_p (loop_nest[0],
full_seq.object_a)
&& object_address_invariant_in_loop_p (loop_nest[0],
full_seq.object_b)))
{
DDR_OBJECT_A (res) = full_seq.object_a;
DDR_OBJECT_B (res) = full_seq.object_b;
}
}
DDR_AFFINE_P (res) = true;
DDR_ARE_DEPENDENT (res) = NULL_TREE;
DDR_SUBSCRIPTS (res).create (full_seq.length);
DDR_LOOP_NEST (res) = loop_nest;
DDR_INNER_LOOP (res) = 0;
DDR_SELF_REFERENCE (res) = false;
for (i = 0; i < full_seq.length; ++i)
{
struct subscript *subscript;
subscript = XNEW (struct subscript);
SUB_ACCESS_FN (subscript, 0) = DR_ACCESS_FN (a, full_seq.start_a + i);
SUB_ACCESS_FN (subscript, 1) = DR_ACCESS_FN (b, full_seq.start_b + i);
SUB_CONFLICTS_IN_A (subscript) = conflict_fn_not_known ();
SUB_CONFLICTS_IN_B (subscript) = conflict_fn_not_known ();
SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
SUB_DISTANCE (subscript) = chrec_dont_know;
DDR_SUBSCRIPTS (res).safe_push (subscript);
}
return res;
}
/* Frees memory used by the conflict function F. */
static void
free_conflict_function (conflict_function *f)
{
unsigned i;
if (CF_NONTRIVIAL_P (f))
{
for (i = 0; i < f->n; i++)
affine_fn_free (f->fns[i]);
}
free (f);
}
/* Frees memory used by SUBSCRIPTS. */
static void
free_subscripts (vec<subscript_p> subscripts)
{
unsigned i;
subscript_p s;
FOR_EACH_VEC_ELT (subscripts, i, s)
{
free_conflict_function (s->conflicting_iterations_in_a);
free_conflict_function (s->conflicting_iterations_in_b);
free (s);
}
subscripts.release ();
}
/* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
description. */
static inline void
finalize_ddr_dependent (struct data_dependence_relation *ddr,
tree chrec)
{
DDR_ARE_DEPENDENT (ddr) = chrec;
free_subscripts (DDR_SUBSCRIPTS (ddr));
DDR_SUBSCRIPTS (ddr).create (0);
}
/* The dependence relation DDR cannot be represented by a distance
vector. */
static inline void
non_affine_dependence_relation (struct data_dependence_relation *ddr)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "(Dependence relation cannot be represented by distance vector.) \n");
DDR_AFFINE_P (ddr) = false;
}
/* 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. */
static inline bool
ziv_subscript_p (const_tree chrec_a, const_tree chrec_b)
{
return (evolution_function_is_constant_p (chrec_a)
&& evolution_function_is_constant_p (chrec_b));
}
/* 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. */
static bool
siv_subscript_p (const_tree chrec_a, const_tree chrec_b)
{
if ((evolution_function_is_constant_p (chrec_a)
&& evolution_function_is_univariate_p (chrec_b))
|| (evolution_function_is_constant_p (chrec_b)
&& evolution_function_is_univariate_p (chrec_a)))
return true;
if (evolution_function_is_univariate_p (chrec_a)
&& evolution_function_is_univariate_p (chrec_b))
{
switch (TREE_CODE (chrec_a))
{
case POLYNOMIAL_CHREC:
switch (TREE_CODE (chrec_b))
{
case POLYNOMIAL_CHREC:
if (CHREC_VARIABLE (chrec_a) != CHREC_VARIABLE (chrec_b))
return false;
/* FALLTHRU */
default:
return true;
}
default:
return true;
}
}
return false;
}
/* Creates a conflict function with N dimensions. The affine functions
in each dimension follow. */
static conflict_function *
conflict_fn (unsigned n, ...)
{
unsigned i;
conflict_function *ret = XCNEW (conflict_function);
va_list ap;
gcc_assert (n > 0 && n <= MAX_DIM);
va_start (ap, n);
ret->n = n;
for (i = 0; i < n; i++)
ret->fns[i] = va_arg (ap, affine_fn);
va_end (ap);
return ret;
}
/* Returns constant affine function with value CST. */
static affine_fn
affine_fn_cst (tree cst)
{
affine_fn fn;
fn.create (1);
fn.quick_push (cst);
return fn;
}
/* Returns affine function with single variable, CST + COEF * x_DIM. */
static affine_fn
affine_fn_univar (tree cst, unsigned dim, tree coef)
{
affine_fn fn;
fn.create (dim + 1);
unsigned i;
gcc_assert (dim > 0);
fn.quick_push (cst);
for (i = 1; i < dim; i++)
fn.quick_push (integer_zero_node);
fn.quick_push (coef);
return fn;
}
/* 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)). */
static void
analyze_ziv_subscript (tree chrec_a,
tree chrec_b,
conflict_function **overlaps_a,
conflict_function **overlaps_b,
tree *last_conflicts)
{
tree type, difference;
dependence_stats.num_ziv++;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "(analyze_ziv_subscript \n");
type = signed_type_for_types (TREE_TYPE (chrec_a), TREE_TYPE (chrec_b));
chrec_a = chrec_convert (type, chrec_a, NULL);
chrec_b = chrec_convert (type, chrec_b, NULL);
difference = chrec_fold_minus (type, chrec_a, chrec_b);
switch (TREE_CODE (difference))
{
case INTEGER_CST:
if (integer_zerop (difference))
{
/* The difference is equal to zero: the accessed index
overlaps for each iteration in the loop. */
*overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
*overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
*last_conflicts = chrec_dont_know;
dependence_stats.num_ziv_dependent++;
}
else
{
/* The accesses do not overlap. */
*overlaps_a = conflict_fn_no_dependence ();
*overlaps_b = conflict_fn_no_dependence ();
*last_conflicts = integer_zero_node;
dependence_stats.num_ziv_independent++;
}
break;
default:
/* We're not sure whether the indexes overlap. For the moment,
conservatively answer "don't know". */
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "ziv test failed: difference is non-integer.\n");
*overlaps_a = conflict_fn_not_known ();
*overlaps_b = conflict_fn_not_known ();
*last_conflicts = chrec_dont_know;
dependence_stats.num_ziv_unimplemented++;
break;
}
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, ")\n");
}
/* 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. */
static tree
max_stmt_executions_tree (struct loop *loop)
{
widest_int nit;
if (!max_stmt_executions (loop, &nit))
return chrec_dont_know;
if (!wi::fits_to_tree_p (nit, unsigned_type_node))
return chrec_dont_know;
return wide_int_to_tree (unsigned_type_node, nit);
}
/* Determine whether the CHREC is always positive/negative. If the expression
cannot be statically analyzed, return false, otherwise set the answer into
VALUE. */
static bool
chrec_is_positive (tree chrec, bool *value)
{
bool value0, value1, value2;
tree end_value, nb_iter;
switch (TREE_CODE (chrec))
{
case POLYNOMIAL_CHREC:
if (!chrec_is_positive (CHREC_LEFT (chrec), &value0)
|| !chrec_is_positive (CHREC_RIGHT (chrec), &value1))
return false;
/* FIXME -- overflows. */
if (value0 == value1)
{
*value = value0;
return true;
}
/* Otherwise the chrec is under the form: "{-197, +, 2}_1",
and the proof consists in showing that the sign never
changes during the execution of the loop, from 0 to
loop->nb_iterations. */
if (!evolution_function_is_affine_p (chrec))
return false;
nb_iter = number_of_latch_executions (get_chrec_loop (chrec));
if (chrec_contains_undetermined (nb_iter))
return false;
#if 0
/* TODO -- If the test is after the exit, we may decrease the number of
iterations by one. */
if (after_exit)
nb_iter = chrec_fold_minus (type, nb_iter, build_int_cst (type, 1));
#endif
end_value = chrec_apply (CHREC_VARIABLE (chrec), chrec, nb_iter);
if (!chrec_is_positive (end_value, &value2))
return false;
*value = value0;
return value0 == value1;
case INTEGER_CST:
switch (tree_int_cst_sgn (chrec))
{
case -1:
*value = false;
break;
case 1:
*value = true;
break;
default:
return false;
}
return true;
default:
return false;
}
}
/* 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)). */
static void
analyze_siv_subscript_cst_affine (tree chrec_a,
tree chrec_b,
conflict_function **overlaps_a,
conflict_function **overlaps_b,
tree *last_conflicts)
{
bool value0, value1, value2;
tree type, difference, tmp;
type = signed_type_for_types (TREE_TYPE (chrec_a), TREE_TYPE (chrec_b));
chrec_a = chrec_convert (type, chrec_a, NULL);
chrec_b = chrec_convert (type, chrec_b, NULL);
difference = chrec_fold_minus (type, initial_condition (chrec_b), chrec_a);
/* Special case overlap in the first iteration. */
if (integer_zerop (difference))
{
*overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
*overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
*last_conflicts = integer_one_node;
return;
}
if (!chrec_is_positive (initial_condition (difference), &value0))
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "siv test failed: chrec is not positive.\n");
dependence_stats.num_siv_unimplemented++;
*overlaps_a = conflict_fn_not_known ();
*overlaps_b = conflict_fn_not_known ();
*last_conflicts = chrec_dont_know;
return;
}
else
{
if (value0 == false)
{
if (TREE_CODE (chrec_b) != POLYNOMIAL_CHREC
|| !chrec_is_positive (CHREC_RIGHT (chrec_b), &value1))
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "siv test failed: chrec not positive.\n");
*overlaps_a = conflict_fn_not_known ();
*overlaps_b = conflict_fn_not_known ();
*last_conflicts = chrec_dont_know;
dependence_stats.num_siv_unimplemented++;
return;
}
else
{
if (value1 == true)
{
/* Example:
chrec_a = 12
chrec_b = {10, +, 1}
*/
if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
{
HOST_WIDE_INT numiter;
struct loop *loop = get_chrec_loop (chrec_b);
*overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
tmp = fold_build2 (EXACT_DIV_EXPR, type,
fold_build1 (ABS_EXPR, type, difference),
CHREC_RIGHT (chrec_b));
*overlaps_b = conflict_fn (1, affine_fn_cst (tmp));
*last_conflicts = integer_one_node;
/* Perform weak-zero siv test to see if overlap is
outside the loop bounds. */
numiter = max_stmt_executions_int (loop);
if (numiter >= 0
&& compare_tree_int (tmp, numiter) > 0)
{
free_conflict_function (*overlaps_a);
free_conflict_function (*overlaps_b);
*overlaps_a = conflict_fn_no_dependence ();
*overlaps_b = conflict_fn_no_dependence ();
*last_conflicts = integer_zero_node;
dependence_stats.num_siv_independent++;
return;
}
dependence_stats.num_siv_dependent++;
return;
}
/* When the step does not divide the difference, there are
no overlaps. */
else
{
*overlaps_a = conflict_fn_no_dependence ();
*overlaps_b = conflict_fn_no_dependence ();
*last_conflicts = integer_zero_node;
dependence_stats.num_siv_independent++;
return;
}
}
else
{
/* Example:
chrec_a = 12
chrec_b = {10, +, -1}
In this case, chrec_a will not overlap with chrec_b. */
*overlaps_a = conflict_fn_no_dependence ();
*overlaps_b = conflict_fn_no_dependence ();
*last_conflicts = integer_zero_node;
dependence_stats.num_siv_independent++;
return;
}
}
}
else
{
if (TREE_CODE (chrec_b) != POLYNOMIAL_CHREC
|| !chrec_is_positive (CHREC_RIGHT (chrec_b), &value2))
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "siv test failed: chrec not positive.\n");
*overlaps_a = conflict_fn_not_known ();
*overlaps_b = conflict_fn_not_known ();
*last_conflicts = chrec_dont_know;
dependence_stats.num_siv_unimplemented++;
return;
}
else
{
if (value2 == false)
{
/* Example:
chrec_a = 3
chrec_b = {10, +, -1}
*/
if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
{
HOST_WIDE_INT numiter;
struct loop *loop = get_chrec_loop (chrec_b);
*overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
tmp = fold_build2 (EXACT_DIV_EXPR, type, difference,
CHREC_RIGHT (chrec_b));
*overlaps_b = conflict_fn (1, affine_fn_cst (tmp));
*last_conflicts = integer_one_node;
/* Perform weak-zero siv test to see if overlap is
outside the loop bounds. */
numiter = max_stmt_executions_int (loop);
if (numiter >= 0
&& compare_tree_int (tmp, numiter) > 0)
{
free_conflict_function (*overlaps_a);
free_conflict_function (*overlaps_b);
*overlaps_a = conflict_fn_no_dependence ();
*overlaps_b = conflict_fn_no_dependence ();
*last_conflicts = integer_zero_node;
dependence_stats.num_siv_independent++;
return;
}
dependence_stats.num_siv_dependent++;
return;
}
/* When the step does not divide the difference, there
are no overlaps. */
else
{
*overlaps_a = conflict_fn_no_dependence ();
*overlaps_b = conflict_fn_no_dependence ();
*last_conflicts = integer_zero_node;
dependence_stats.num_siv_independent++;
return;
}
}
else
{
/* Example:
chrec_a = 3
chrec_b = {4, +, 1}
In this case, chrec_a will not overlap with chrec_b. */
*overlaps_a = conflict_fn_no_dependence ();
*overlaps_b = conflict_fn_no_dependence ();
*last_conflicts = integer_zero_node;
dependence_stats.num_siv_independent++;
return;
}
}
}
}
}
/* Helper recursive function for initializing the matrix A. Returns
the initial value of CHREC. */
static tree
initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult)
{
gcc_assert (chrec);
switch (TREE_CODE (chrec))
{
case POLYNOMIAL_CHREC:
A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec));
return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult);
case PLUS_EXPR:
case MULT_EXPR:
case MINUS_EXPR:
{
tree op0 = initialize_matrix_A (A, TREE_OPERAND (chrec, 0), index, mult);
tree op1 = initialize_matrix_A (A, TREE_OPERAND (chrec, 1), index, mult);
return chrec_fold_op (TREE_CODE (chrec), chrec_type (chrec), op0, op1);
}
CASE_CONVERT:
{
tree op = initialize_matrix_A (A, TREE_OPERAND (chrec, 0), index, mult);
return chrec_convert (chrec_type (chrec), op, NULL);
}
case BIT_NOT_EXPR:
{
/* Handle ~X as -1 - X. */
tree op = initialize_matrix_A (A, TREE_OPERAND (chrec, 0), index, mult);
return chrec_fold_op (MINUS_EXPR, chrec_type (chrec),
build_int_cst (TREE_TYPE (chrec), -1), op);
}
case INTEGER_CST:
return chrec;
default:
gcc_unreachable ();
return NULL_TREE;