From 56cf8686a1031e6cf8760a4aeb46fb022b8ccdfe Mon Sep 17 00:00:00 2001 From: Sebastian Pop Date: Tue, 13 Jul 2004 18:43:32 +0200 Subject: [PATCH] Makefile.in (OBJS-common): Add tree-data-ref.o. * Makefile.in (OBJS-common): Add tree-data-ref.o. (tree-scalar-evolution.o): Add missing dependences on tree-pass.h flags.h. (tree-data-ref.o): New rule. * lambda.h: New file. * tree-data-ref.c: New file. * tree-data-ref.h: New file. * tree.c (int_cst_value, tree_fold_gcd): New functions. * tree.h (int_cst_value, tree_fold_gcd): Declared here. From-SVN: r84630 --- gcc/ChangeLog | 11 + gcc/Makefile.in | 8 +- gcc/lambda.h | 57 ++ gcc/tree-data-ref.c | 1874 +++++++++++++++++++++++++++++++++++++++++++ gcc/tree-data-ref.h | 188 +++++ gcc/tree.c | 61 ++ gcc/tree.h | 2 + 7 files changed, 2199 insertions(+), 2 deletions(-) create mode 100644 gcc/lambda.h create mode 100644 gcc/tree-data-ref.c create mode 100644 gcc/tree-data-ref.h diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 0eb6facf719..5e87e5e3907 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,14 @@ +2004-07-13 Sebastian Pop + + * Makefile.in (OBJS-common): Add tree-data-ref.o. + (tree-scalar-evolution.o): Add missing dependences on tree-pass.h flags.h. + (tree-data-ref.o): New rule. + * lambda.h: New file. + * tree-data-ref.c: New file. + * tree-data-ref.h: New file. + * tree.c (int_cst_value, tree_fold_gcd): New functions. + * tree.h (int_cst_value, tree_fold_gcd): Declared here. + 2004-07-13 Eric Botcazou PR target/13926 diff --git a/gcc/Makefile.in b/gcc/Makefile.in index b9c0619ada5..68b7252ded9 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -888,7 +888,7 @@ C_OBJS = c-parse.o c-lang.o stub-objc.o $(C_AND_OBJC_OBJS) # Language-independent object files. OBJS-common = \ - tree-chrec.o tree-scalar-evolution.o \ + tree-chrec.o tree-scalar-evolution.o tree-data-ref.o \ tree-cfg.o tree-dfa.o tree-eh.o tree-ssa.o tree-optimize.o tree-gimple.o \ tree-alias-type.o gimplify.o tree-pretty-print.o tree-into-ssa.o \ tree-outof-ssa.o tree-alias-common.o tree-ssa-ccp.o tree-vn.o \ @@ -1722,7 +1722,11 @@ tree-chrec.o: tree-chrec.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \ tree-scalar-evolution.o: tree-scalar-evolution.c $(CONFIG_H) $(SYSTEM_H) \ coretypes.h $(TM_H) errors.h $(GGC_H) $(TREE_H) $(RTL_H) \ $(BASIC_BLOCK_H) diagnostic.h $(TREE_FLOW_H) $(TREE_DUMP_H) \ - $(TIMEVAR_H) cfgloop.h $(SCEV_H) + $(TIMEVAR_H) cfgloop.h $(SCEV_H) tree-pass.h flags.h +tree-data-ref.o: tree-data-ref.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \ + errors.h $(GGC_H) $(TREE_H) $(RTL_H) $(BASIC_BLOCK_H) diagnostic.h \ + $(TREE_FLOW_H) $(TREE_DUMP_H) $(TIMEVAR_H) cfgloop.h \ + tree-data-ref.h $(SCEV_H) tree-pass.h lambda.h tree-gimple.o : tree-gimple.c $(CONFIG_H) $(SYSTEM_H) $(TREE_H) $(EXPR_H) \ $(RTL_H) $(TREE_GIMPLE_H) $(TM_H) coretypes.h bitmap.h $(GGC_H) tree-mudflap.o : $(CONFIG_H) errors.h $(SYSTEM_H) $(TREE_H) tree-inline.h \ diff --git a/gcc/lambda.h b/gcc/lambda.h new file mode 100644 index 00000000000..60ed8accbf2 --- /dev/null +++ b/gcc/lambda.h @@ -0,0 +1,57 @@ +/* Lambda matrix interface. + Copyright (C) 2003, 2004 Free Software Foundation, Inc. + Contributed by Daniel Berlin + +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 2, 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 COPYING. If not, write to the Free +Software Foundation, 59 Temple Place - Suite 330, Boston, MA +02111-1307, USA. */ + +#ifndef LAMBDA_H +#define LAMBDA_H + +typedef int *lambda_vector; + +/* Allocate a new vector of given SIZE. */ + +static inline lambda_vector +lambda_vector_new (int size) +{ + return ggc_alloc_cleared (size * sizeof(int)); +} + +/* Clear out vector VEC1 of length SIZE. */ + +static inline void +lambda_vector_clear (lambda_vector vec1, int size) +{ + memset (vec1, 0, size * sizeof (int)); +} + +/* Print out a vector VEC of length N to OUTFILE. */ + +static inline 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"); +} + + +#endif /* LAMBDA_H */ + diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c new file mode 100644 index 00000000000..1f14bcb011d --- /dev/null +++ b/gcc/tree-data-ref.c @@ -0,0 +1,1874 @@ +/* Data references and dependences detectors. + Copyright (C) 2003, 2004 Free Software Foundation, Inc. + Contributed by Sebastian Pop + +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 2, 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 COPYING. If not, write to the Free +Software Foundation, 59 Temple Place - Suite 330, Boston, MA +02111-1307, USA. */ + +/* 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 dependeces + 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 "tm.h" +#include "errors.h" +#include "ggc.h" +#include "tree.h" + +/* These RTL headers are needed for basic-block.h. */ +#include "rtl.h" +#include "basic-block.h" +#include "diagnostic.h" +#include "tree-flow.h" +#include "tree-dump.h" +#include "timevar.h" +#include "cfgloop.h" +#include "tree-chrec.h" +#include "tree-data-ref.h" +#include "tree-scalar-evolution.h" +#include "tree-pass.h" +#include "lambda.h" + +static unsigned int data_ref_id = 0; + + + +/* Returns true iff A divides B. */ + +static inline bool +tree_fold_divides_p (tree type, + tree a, + tree b) +{ + if (integer_onep (a)) + return true; + + /* Determines whether (A == gcd (A, B)). */ + return integer_zerop + (fold (build (MINUS_EXPR, type, a, tree_fold_gcd (a, b)))); +} + +/* Bezout: Let A1 and A2 be two integers; there exist two integers U11 + and U12 such that, + + | U11 * A1 + U12 * A2 = gcd (A1, A2). + + This function computes the greatest common divisor using the + Blankinship algorithm. The gcd is returned, and the coefficients + of the unimodular matrix U are (U11, U12, U21, U22) such that, + + | U.A = S + + | (U11 U12) (A1) = (gcd) + | (U21 U22) (A2) (0) + + FIXME: Use lambda_..._hermite for implementing this function. +*/ + +static tree +tree_fold_bezout (tree a1, + tree a2, + tree *u11, tree *u12, + tree *u21, tree *u22) +{ + tree s1, s2; + + /* Initialize S with the coefficients of A. */ + s1 = a1; + s2 = a2; + + /* Initialize the U matrix */ + *u11 = integer_one_node; + *u12 = integer_zero_node; + *u21 = integer_zero_node; + *u22 = integer_one_node; + + if (integer_zerop (a1) + || integer_zerop (a2)) + return integer_zero_node; + + while (!integer_zerop (s2)) + { + int sign; + tree z, zu21, zu22, zs2; + + sign = tree_int_cst_sgn (s1) * tree_int_cst_sgn (s2); + z = fold (build (FLOOR_DIV_EXPR, integer_type_node, + fold (build1 (ABS_EXPR, integer_type_node, s1)), + fold (build1 (ABS_EXPR, integer_type_node, s2)))); + zu21 = fold (build (MULT_EXPR, integer_type_node, z, *u21)); + zu22 = fold (build (MULT_EXPR, integer_type_node, z, *u22)); + zs2 = fold (build (MULT_EXPR, integer_type_node, z, s2)); + + /* row1 -= z * row2. */ + if (sign < 0) + { + *u11 = fold (build (PLUS_EXPR, integer_type_node, *u11, zu21)); + *u12 = fold (build (PLUS_EXPR, integer_type_node, *u12, zu22)); + s1 = fold (build (PLUS_EXPR, integer_type_node, s1, zs2)); + } + else if (sign > 0) + { + *u11 = fold (build (MINUS_EXPR, integer_type_node, *u11, zu21)); + *u12 = fold (build (MINUS_EXPR, integer_type_node, *u12, zu22)); + s1 = fold (build (MINUS_EXPR, integer_type_node, s1, zs2)); + } + else + /* Should not happen. */ + abort (); + + /* Interchange row1 and row2. */ + { + tree flip; + + flip = *u11; + *u11 = *u21; + *u21 = flip; + + flip = *u12; + *u12 = *u22; + *u22 = flip; + + flip = s1; + s1 = s2; + s2 = flip; + } + } + + if (tree_int_cst_sgn (s1) < 0) + { + *u11 = fold (build (MULT_EXPR, integer_type_node, *u11, + integer_minus_one_node)); + *u12 = fold (build (MULT_EXPR, integer_type_node, *u12, + integer_minus_one_node)); + s1 = fold (build (MULT_EXPR, integer_type_node, s1, integer_minus_one_node)); + } + + return s1; +} + + + +/* Dump into FILE all the data references from DATAREFS. */ + +void +dump_data_references (FILE *file, + varray_type datarefs) +{ + unsigned int i; + + for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++) + dump_data_reference (file, VARRAY_GENERIC_PTR (datarefs, i)); +} + +/* Dump into FILE all the dependence relations from DDR. */ + +void +dump_data_dependence_relations (FILE *file, + varray_type ddr) +{ + unsigned int i; + + for (i = 0; i < VARRAY_ACTIVE_SIZE (ddr); i++) + dump_data_dependence_relation (file, VARRAY_GENERIC_PTR (ddr, i)); +} + +/* Dump function for a DATA_REFERENCE structure. */ + +void +dump_data_reference (FILE *outf, + struct data_reference *dr) +{ + unsigned int i; + + fprintf (outf, "(Data Ref %d: \n stmt: ", DR_ID (dr)); + print_generic_stmt (outf, DR_STMT (dr), 0); + fprintf (outf, " ref: "); + print_generic_stmt (outf, DR_REF (dr), 0); + fprintf (outf, " base_name: "); + print_generic_stmt (outf, DR_BASE_NAME (dr), 0); + + for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++) + { + fprintf (outf, " Access function %d: ", i); + print_generic_stmt (outf, DR_ACCESS_FN (dr, i), 0); + } + fprintf (outf, ")\n"); +} + +/* Dump function for a DATA_DEPENDENCE_RELATION structure. */ + +void +dump_data_dependence_relation (FILE *outf, + struct data_dependence_relation *ddr) +{ + unsigned int i; + struct data_reference *dra, *drb; + + dra = DDR_A (ddr); + drb = DDR_B (ddr); + + if (dra && drb) + fprintf (outf, "(Data Dep (A = %d, B = %d):", DR_ID (dra), DR_ID (drb)); + else + fprintf (outf, "(Data Dep:"); + + if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr))) + fprintf (outf, " (don't know)\n"); + + else if (DDR_ARE_DEPENDENT (ddr) == chrec_known) + fprintf (outf, " (no dependence)\n"); + + else + { + for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++) + { + tree chrec; + struct subscript *subscript = DDR_SUBSCRIPT (ddr, i); + + fprintf (outf, "\n (subscript %d:\n", i); + fprintf (outf, " access_fn_A: "); + print_generic_stmt (outf, DR_ACCESS_FN (dra, i), 0); + fprintf (outf, " access_fn_B: "); + print_generic_stmt (outf, DR_ACCESS_FN (drb, i), 0); + + chrec = SUB_CONFLICTS_IN_A (subscript); + fprintf (outf, " iterations_that_access_an_element_twice_in_A: "); + print_generic_stmt (outf, chrec, 0); + if (chrec == chrec_known) + fprintf (outf, " (no dependence)\n"); + else if (chrec_contains_undetermined (chrec)) + fprintf (outf, " (don't know)\n"); + else + { + tree last_iteration = SUB_LAST_CONFLICT_IN_A (subscript); + fprintf (outf, " last_iteration_that_access_an_element_twice_in_A: "); + print_generic_stmt (outf, last_iteration, 0); + } + + chrec = SUB_CONFLICTS_IN_B (subscript); + fprintf (outf, " iterations_that_access_an_element_twice_in_B: "); + print_generic_stmt (outf, chrec, 0); + if (chrec == chrec_known) + fprintf (outf, " (no dependence)\n"); + else if (chrec_contains_undetermined (chrec)) + fprintf (outf, " (don't know)\n"); + else + { + tree last_iteration = SUB_LAST_CONFLICT_IN_B (subscript); + fprintf (outf, " last_iteration_that_access_an_element_twice_in_B: "); + print_generic_stmt (outf, last_iteration, 0); + } + + fprintf (outf, " )\n"); + } + + fprintf (outf, " (Distance Vector: \n"); + for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++) + { + struct subscript *subscript = DDR_SUBSCRIPT (ddr, i); + + fprintf (outf, "("); + print_generic_stmt (outf, SUB_DISTANCE (subscript), 0); + fprintf (outf, ")\n"); + } + fprintf (outf, " )\n"); + } + + fprintf (outf, ")\n"); +} + + + +/* Dump function for a DATA_DEPENDENCE_DIRECTION structure. */ + +void +dump_data_dependence_direction (FILE *file, + enum data_dependence_direction dir) +{ + switch (dir) + { + case dir_positive: + fprintf (file, "+"); + break; + + case dir_negative: + fprintf (file, "-"); + break; + + case dir_equal: + fprintf (file, "="); + break; + + case dir_positive_or_negative: + fprintf (file, "+-"); + break; + + case dir_positive_or_equal: + fprintf (file, "+="); + break; + + case dir_negative_or_equal: + fprintf (file, "-="); + break; + + case dir_star: + fprintf (file, "*"); + break; + + default: + break; + } +} + + + +/* Given an ARRAY_REF node REF, records its access functions. + Example: given A[i][3], record in ACCESS_FNS the opnd1 function, + ie. the constant "3", then recursively call the function on opnd0, + ie. the ARRAY_REF "A[i]". The function returns the base name: + "A". */ + +static tree +analyze_array_indexes (struct loop *loop, + varray_type access_fns, + tree ref) +{ + tree opnd0, opnd1; + tree access_fn; + + opnd0 = TREE_OPERAND (ref, 0); + opnd1 = TREE_OPERAND (ref, 1); + + /* The detection of the evolution function for this data access is + postponed until the dependence test. This lazy strategy avoids + the computation of access functions that are of no interest for + the optimizers. */ + access_fn = instantiate_parameters + (loop, analyze_scalar_evolution (loop, opnd1)); + + VARRAY_PUSH_TREE (access_fns, access_fn); + + /* Recursively record other array access functions. */ + if (TREE_CODE (opnd0) == ARRAY_REF) + return analyze_array_indexes (loop, access_fns, opnd0); + + /* Return the base name of the data access. */ + else + return opnd0; +} + +/* For a data reference REF contained in the statemet STMT, initialize + a DATA_REFERENCE structure, and return it. IS_READ flag has to be + set to true when REF is in the right hand side of an + assignment. */ + +struct data_reference * +analyze_array (tree stmt, tree ref, bool is_read) +{ + struct data_reference *res; + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "(analyze_array \n"); + fprintf (dump_file, " (ref = "); + print_generic_stmt (dump_file, ref, 0); + fprintf (dump_file, ")\n"); + } + + res = ggc_alloc (sizeof (struct data_reference)); + + DR_ID (res) = data_ref_id++; + DR_STMT (res) = stmt; + DR_REF (res) = ref; + VARRAY_TREE_INIT (DR_ACCESS_FNS (res), 3, "access_fns"); + DR_BASE_NAME (res) = analyze_array_indexes + (loop_containing_stmt (stmt), DR_ACCESS_FNS (res), ref); + DR_IS_READ (res) = is_read; + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, ")\n"); + + return res; +} + +/* For a data reference REF contained in the statemet STMT, initialize + a DATA_REFERENCE structure, and return it. */ + +struct data_reference * +init_data_ref (tree stmt, + tree ref, + tree base, + tree access_fn) +{ + struct data_reference *res; + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "(init_data_ref \n"); + fprintf (dump_file, " (ref = "); + print_generic_stmt (dump_file, ref, 0); + fprintf (dump_file, ")\n"); + } + + res = ggc_alloc (sizeof (struct data_reference)); + + DR_ID (res) = data_ref_id++; + DR_STMT (res) = stmt; + DR_REF (res) = ref; + VARRAY_TREE_INIT (DR_ACCESS_FNS (res), 5, "access_fns"); + DR_BASE_NAME (res) = base; + VARRAY_PUSH_TREE (DR_ACCESS_FNS (res), access_fn); + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, ")\n"); + + return res; +} + + + +/* When there exists a dependence relation, determine its distance + vector. */ + +static void +compute_distance_vector (struct data_dependence_relation *ddr) +{ + if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE) + { + unsigned int i; + + for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++) + { + tree conflicts_a, conflicts_b, difference; + struct subscript *subscript; + + subscript = DDR_SUBSCRIPT (ddr, i); + conflicts_a = SUB_CONFLICTS_IN_A (subscript); + conflicts_b = SUB_CONFLICTS_IN_B (subscript); + difference = chrec_fold_minus + (integer_type_node, conflicts_b, conflicts_a); + + if (evolution_function_is_constant_p (difference)) + SUB_DISTANCE (subscript) = difference; + + else + SUB_DISTANCE (subscript) = chrec_dont_know; + } + } +} + +/* Initialize a ddr. */ + +struct data_dependence_relation * +initialize_data_dependence_relation (struct data_reference *a, + struct data_reference *b) +{ + struct data_dependence_relation *res; + + res = ggc_alloc (sizeof (struct data_dependence_relation)); + DDR_A (res) = a; + DDR_B (res) = b; + + if (a == NULL || b == NULL + || DR_BASE_NAME (a) == NULL_TREE + || DR_BASE_NAME (b) == NULL_TREE) + DDR_ARE_DEPENDENT (res) = chrec_dont_know; + + /* When the dimensions of A and B differ, we directly initialize + the relation to "there is no dependence": chrec_known. */ + else if (DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b) + || array_base_name_differ_p (a, b)) + DDR_ARE_DEPENDENT (res) = chrec_known; + + else + { + unsigned int i; + DDR_ARE_DEPENDENT (res) = NULL_TREE; + DDR_SUBSCRIPTS_VECTOR_INIT (res, DR_NUM_DIMENSIONS (a)); + + for (i = 0; i < DR_NUM_DIMENSIONS (a); i++) + { + struct subscript *subscript; + + subscript = ggc_alloc (sizeof (struct subscript)); + SUB_CONFLICTS_IN_A (subscript) = chrec_dont_know; + SUB_CONFLICTS_IN_B (subscript) = chrec_dont_know; + SUB_LAST_CONFLICT_IN_A (subscript) = chrec_dont_know; + SUB_LAST_CONFLICT_IN_B (subscript) = chrec_dont_know; + SUB_DISTANCE (subscript) = chrec_dont_know; + SUB_DIRECTION (subscript) = dir_star; + VARRAY_PUSH_GENERIC_PTR (DDR_SUBSCRIPTS (res), subscript); + } + } + + return res; +} + +/* 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; + varray_clear (DDR_SUBSCRIPTS (ddr)); +} + + + +/* 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 (tree chrec_a, + 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 (tree chrec_a, + 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; + + default: + return true; + } + + default: + return true; + } + } + + return false; +} + +/* 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, + tree *overlaps_a, + tree *overlaps_b) +{ + tree difference; + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "(analyze_ziv_subscript \n"); + + difference = chrec_fold_minus (integer_type_node, 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 = integer_zero_node; + *overlaps_b = integer_zero_node; + } + else + { + /* The accesses do not overlap. */ + *overlaps_a = chrec_known; + *overlaps_b = chrec_known; + } + break; + + default: + /* We're not sure whether the indexes overlap. For the moment, + conservatively answer "don't know". */ + *overlaps_a = chrec_dont_know; + *overlaps_b = chrec_dont_know; + break; + } + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, ")\n"); +} + +/* 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, + tree *overlaps_a, + tree *overlaps_b) +{ + bool value0, value1, value2; + tree difference = chrec_fold_minus + (integer_type_node, CHREC_LEFT (chrec_b), chrec_a); + + if (!chrec_is_positive (initial_condition (difference), &value0)) + { + *overlaps_a = chrec_dont_know; + *overlaps_b = chrec_dont_know; + return; + } + else + { + if (value0 == false) + { + if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value1)) + { + *overlaps_a = chrec_dont_know; + *overlaps_b = chrec_dont_know; + return; + } + else + { + if (value1 == true) + { + /* Example: + chrec_a = 12 + chrec_b = {10, +, 1} + */ + + if (tree_fold_divides_p + (integer_type_node, CHREC_RIGHT (chrec_b), difference)) + { + *overlaps_a = integer_zero_node; + *overlaps_b = fold + (build (EXACT_DIV_EXPR, integer_type_node, + fold (build1 (ABS_EXPR, integer_type_node, difference)), + CHREC_RIGHT (chrec_b))); + return; + } + + /* When the step does not divides the difference, there are + no overlaps. */ + else + { + *overlaps_a = chrec_known; + *overlaps_b = chrec_known; + return; + } + } + + else + { + /* Example: + chrec_a = 12 + chrec_b = {10, +, -1} + + In this case, chrec_a will not overlap with chrec_b. */ + *overlaps_a = chrec_known; + *overlaps_b = chrec_known; + return; + } + } + } + else + { + if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2)) + { + *overlaps_a = chrec_dont_know; + *overlaps_b = chrec_dont_know; + return; + } + else + { + if (value2 == false) + { + /* Example: + chrec_a = 3 + chrec_b = {10, +, -1} + */ + if (tree_fold_divides_p + (integer_type_node, CHREC_RIGHT (chrec_b), difference)) + { + *overlaps_a = integer_zero_node; + *overlaps_b = fold + (build (EXACT_DIV_EXPR, integer_type_node, difference, + CHREC_RIGHT (chrec_b))); + return; + } + + /* When the step does not divides the difference, there + are no overlaps. */ + else + { + *overlaps_a = chrec_known; + *overlaps_b = chrec_known; + return; + } + } + else + { + /* Example: + chrec_a = 3 + chrec_b = {4, +, 1} + + In this case, chrec_a will not overlap with chrec_b. */ + *overlaps_a = chrec_known; + *overlaps_b = chrec_known; + return; + } + } + } + } +} + +/* Analyze a SIV (Single Index Variable) subscript where CHREC_A is an + affine function, and CHREC_B is a constant. *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_affine_cst (tree chrec_a, + tree chrec_b, + tree *overlaps_a, + tree *overlaps_b) +{ + analyze_siv_subscript_cst_affine (chrec_b, chrec_a, overlaps_b, overlaps_a); +} + +/* Determines the overlapping elements due to accesses CHREC_A and + CHREC_B, that are affine functions. This is a part of the + subscript analyzer. */ + +static void +analyze_subscript_affine_affine (tree chrec_a, + tree chrec_b, + tree *overlaps_a, + tree *overlaps_b) +{ + tree left_a, left_b, right_a, right_b; + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "(analyze_subscript_affine_affine \n"); + + /* For determining the initial intersection, we have to solve a + Diophantine equation. This is the most time consuming part. + + For answering to the question: "Is there a dependence?" we have + to prove that there exists a solution to the Diophantine + equation, and that the solution is in the iteration domain, + ie. the solution is positive or zero, and that the solution + happens before the upper bound loop.nb_iterations. Otherwise + there is no dependence. This function outputs a description of + the iterations that hold the intersections. */ + + left_a = CHREC_LEFT (chrec_a); + left_b = CHREC_LEFT (chrec_b); + right_a = CHREC_RIGHT (chrec_a); + right_b = CHREC_RIGHT (chrec_b); + + if (chrec_zerop (chrec_fold_minus (integer_type_node, left_a, left_b))) + { + /* The first element accessed twice is on the first + iteration. */ + *overlaps_a = build_polynomial_chrec + (CHREC_VARIABLE (chrec_b), integer_zero_node, integer_one_node); + *overlaps_b = build_polynomial_chrec + (CHREC_VARIABLE (chrec_a), integer_zero_node, integer_one_node); + } + + else if (TREE_CODE (left_a) == INTEGER_CST + && TREE_CODE (left_b) == INTEGER_CST + && TREE_CODE (right_a) == INTEGER_CST + && TREE_CODE (right_b) == INTEGER_CST + + /* Both functions should have the same evolution sign. */ + && ((tree_int_cst_sgn (right_a) > 0 + && tree_int_cst_sgn (right_b) > 0) + || (tree_int_cst_sgn (right_a) < 0 + && tree_int_cst_sgn (right_b) < 0))) + { + /* Here we have to solve the Diophantine equation. Reference + book: "Loop Transformations for Restructuring Compilers - The + Foundations" by Utpal Banerjee, pages 59-80. + + ALPHA * X0 = BETA * Y0 + GAMMA. + + with: + ALPHA = RIGHT_A + BETA = RIGHT_B + GAMMA = LEFT_B - LEFT_A + CHREC_A = {LEFT_A, +, RIGHT_A} + CHREC_B = {LEFT_B, +, RIGHT_B} + + The Diophantine equation has a solution if and only if gcd + (ALPHA, BETA) divides GAMMA. This is commonly known under + the name of the "gcd-test". + */ + tree alpha, beta, gamma; + tree la, lb; + tree gcd_alpha_beta; + tree u11, u12, u21, u22; + + /* Both alpha and beta have to be integer_type_node. The gcd + function does not work correctly otherwise. */ + alpha = copy_node (right_a); + beta = copy_node (right_b); + la = copy_node (left_a); + lb = copy_node (left_b); + TREE_TYPE (alpha) = integer_type_node; + TREE_TYPE (beta) = integer_type_node; + TREE_TYPE (la) = integer_type_node; + TREE_TYPE (lb) = integer_type_node; + + gamma = fold (build (MINUS_EXPR, integer_type_node, lb, la)); + + /* FIXME: Use lambda_*_Hermite for implementing Bezout. */ + gcd_alpha_beta = tree_fold_bezout + (alpha, + fold (build (MULT_EXPR, integer_type_node, beta, + integer_minus_one_node)), + &u11, &u12, + &u21, &u22); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, " (alpha = "); + print_generic_expr (dump_file, alpha, 0); + fprintf (dump_file, ")\n (beta = "); + print_generic_expr (dump_file, beta, 0); + fprintf (dump_file, ")\n (gamma = "); + print_generic_expr (dump_file, gamma, 0); + fprintf (dump_file, ")\n (gcd_alpha_beta = "); + print_generic_expr (dump_file, gcd_alpha_beta, 0); + fprintf (dump_file, ")\n"); + } + + /* The classic "gcd-test". */ + if (!tree_fold_divides_p (integer_type_node, gcd_alpha_beta, gamma)) + { + /* The "gcd-test" has determined that there is no integer + solution, ie. there is no dependence. */ + *overlaps_a = chrec_known; + *overlaps_b = chrec_known; + } + + else + { + /* The solutions are given by: + | + | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [X] + | [u21 u22] [Y] + + For a given integer t. Using the following variables, + + | i0 = u11 * gamma / gcd_alpha_beta + | j0 = u12 * gamma / gcd_alpha_beta + | i1 = u21 + | j1 = u22 + + the solutions are: + + | x = i0 + i1 * t, + | y = j0 + j1 * t. */ + + tree i0, j0, i1, j1, t; + tree gamma_gcd; + + /* X0 and Y0 are the first iterations for which there is a + dependence. X0, Y0 are two solutions of the Diophantine + equation: chrec_a (X0) = chrec_b (Y0). */ + tree x0, y0; + + /* Exact div because in this case gcd_alpha_beta divides + gamma. */ + gamma_gcd = fold (build (EXACT_DIV_EXPR, integer_type_node, gamma, + gcd_alpha_beta)); + i0 = fold (build (MULT_EXPR, integer_type_node, u11, gamma_gcd)); + j0 = fold (build (MULT_EXPR, integer_type_node, u12, gamma_gcd)); + i1 = u21; + j1 = u22; + + if ((tree_int_cst_sgn (i1) == 0 + && tree_int_cst_sgn (i0) < 0) + || (tree_int_cst_sgn (j1) == 0 + && tree_int_cst_sgn (j0) < 0)) + { + /* There is no solution. + FIXME: The case "i0 > nb_iterations, j0 > nb_iterations" + falls in here, but for the moment we don't look at the + upper bound of the iteration domain. */ + *overlaps_a = chrec_known; + *overlaps_b = chrec_known; + } + + else + { + if (tree_int_cst_sgn (i1) > 0) + { + t = fold + (build (CEIL_DIV_EXPR, integer_type_node, + fold (build (MULT_EXPR, integer_type_node, i0, + integer_minus_one_node)), + i1)); + + if (tree_int_cst_sgn (j1) > 0) + { + t = fold + (build (MAX_EXPR, integer_type_node, t, + fold (build (CEIL_DIV_EXPR, integer_type_node, + fold (build + (MULT_EXPR, + integer_type_node, j0, + integer_minus_one_node)), + j1)))); + + x0 = fold + (build (PLUS_EXPR, integer_type_node, i0, + fold (build + (MULT_EXPR, integer_type_node, i1, t)))); + y0 = fold + (build (PLUS_EXPR, integer_type_node, j0, + fold (build + (MULT_EXPR, integer_type_node, j1, t)))); + + *overlaps_a = build_polynomial_chrec + (CHREC_VARIABLE (chrec_b), x0, u21); + *overlaps_b = build_polynomial_chrec + (CHREC_VARIABLE (chrec_a), y0, u22); + } + else + { + /* FIXME: For the moment, the upper bound of the + iteration domain for j is not checked. */ + *overlaps_a = chrec_dont_know; + *overlaps_b = chrec_dont_know; + } + } + + else + { + /* FIXME: For the moment, the upper bound of the + iteration domain for i is not checked. */ + *overlaps_a = chrec_dont_know; + *overlaps_b = chrec_dont_know; + } + } + } + } + + else + { + /* For the moment, "don't know". */ + *overlaps_a = chrec_dont_know; + *overlaps_b = chrec_dont_know; + } + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, " (overlaps_a = "); + print_generic_expr (dump_file, *overlaps_a, 0); + fprintf (dump_file, ")\n (overlaps_b = "); + print_generic_expr (dump_file, *overlaps_b, 0); + fprintf (dump_file, ")\n"); + } + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, ")\n"); +} + +/* 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)). */ + +static void +analyze_siv_subscript (tree chrec_a, + tree chrec_b, + tree *overlaps_a, + tree *overlaps_b) +{ + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "(analyze_siv_subscript \n"); + + if (evolution_function_is_constant_p (chrec_a) + && evolution_function_is_affine_p (chrec_b)) + analyze_siv_subscript_cst_affine (chrec_a, chrec_b, + overlaps_a, overlaps_b); + + else if (evolution_function_is_affine_p (chrec_a) + && evolution_function_is_constant_p (chrec_b)) + analyze_siv_subscript_affine_cst (chrec_a, chrec_b, + overlaps_a, overlaps_b); + + else if (evolution_function_is_affine_p (chrec_a) + && evolution_function_is_affine_p (chrec_b) + && (CHREC_VARIABLE (chrec_a) == CHREC_VARIABLE (chrec_b))) + analyze_subscript_affine_affine (chrec_a, chrec_b, + overlaps_a, overlaps_b); + else + { + *overlaps_a = chrec_dont_know; + *overlaps_b = chrec_dont_know; + } + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, ")\n"); +} + +/* Return true when the evolution steps of an affine CHREC divide the + constant CST. */ + +static bool +chrec_steps_divide_constant_p (tree chrec, + tree cst) +{ + switch (TREE_CODE (chrec)) + { + case POLYNOMIAL_CHREC: + return (tree_fold_divides_p (integer_type_node, CHREC_RIGHT (chrec), cst) + && chrec_steps_divide_constant_p (CHREC_LEFT (chrec), cst)); + + default: + /* On the initial condition, return true. */ + return true; + } +} + +/* Analyze a MIV (Multiple 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_miv_subscript (tree chrec_a, + tree chrec_b, + tree *overlaps_a, + tree *overlaps_b) +{ + /* FIXME: This is a MIV subscript, not yet handled. + Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from + (A[i] vs. A[j]). + + In the SIV test we had to solve a Diophantine equation with two + variables. In the MIV case we have to solve a Diophantine + equation with 2*n variables (if the subscript uses n IVs). + */ + tree difference; + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "(analyze_miv_subscript \n"); + + difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b); + + if (chrec_zerop (difference)) + { + /* Access functions are the same: all the elements are accessed + in the same order. */ + *overlaps_a = integer_zero_node; + *overlaps_b = integer_zero_node; + } + + else if (evolution_function_is_constant_p (difference) + /* For the moment, the following is verified: + evolution_function_is_affine_multivariate_p (chrec_a) */ + && !chrec_steps_divide_constant_p (chrec_a, difference)) + { + /* testsuite/.../ssa-chrec-33.c + {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2 + + The difference is 1, and the evolution steps are equal to 2, + consequently there are no overlapping elements. */ + *overlaps_a = chrec_known; + *overlaps_b = chrec_known; + } + + else if (evolution_function_is_univariate_p (chrec_a) + && evolution_function_is_univariate_p (chrec_b)) + { + /* testsuite/.../ssa-chrec-35.c + {0, +, 1}_2 vs. {0, +, 1}_3 + the overlapping elements are respectively located at iterations: + {0, +, 1}_3 and {0, +, 1}_2. + */ + if (evolution_function_is_affine_p (chrec_a) + && evolution_function_is_affine_p (chrec_b)) + analyze_subscript_affine_affine (chrec_a, chrec_b, + overlaps_a, overlaps_b); + else + { + *overlaps_a = chrec_dont_know; + *overlaps_b = chrec_dont_know; + } + } + + else + { + /* When the analysis is too difficult, answer "don't know". */ + *overlaps_a = chrec_dont_know; + *overlaps_b = chrec_dont_know; + } + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, ")\n"); +} + +/* Determines the iterations for which CHREC_A is equal to CHREC_B. + 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)). +*/ + +static void +analyze_overlapping_iterations (tree chrec_a, + tree chrec_b, + tree *overlap_iterations_a, + tree *overlap_iterations_b) +{ + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "(analyze_overlapping_iterations \n"); + fprintf (dump_file, " (chrec_a = "); + print_generic_expr (dump_file, chrec_a, 0); + fprintf (dump_file, ")\n chrec_b = "); + print_generic_expr (dump_file, chrec_b, 0); + fprintf (dump_file, ")\n"); + } + + if (chrec_a == NULL_TREE + || chrec_b == NULL_TREE + || chrec_contains_undetermined (chrec_a) + || chrec_contains_undetermined (chrec_b) + || chrec_contains_symbols (chrec_a) + || chrec_contains_symbols (chrec_b)) + { + *overlap_iterations_a = chrec_dont_know; + *overlap_iterations_b = chrec_dont_know; + } + + else if (ziv_subscript_p (chrec_a, chrec_b)) + analyze_ziv_subscript (chrec_a, chrec_b, + overlap_iterations_a, overlap_iterations_b); + + else if (siv_subscript_p (chrec_a, chrec_b)) + analyze_siv_subscript (chrec_a, chrec_b, + overlap_iterations_a, overlap_iterations_b); + + else + analyze_miv_subscript (chrec_a, chrec_b, + overlap_iterations_a, overlap_iterations_b); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, " (overlap_iterations_a = "); + print_generic_expr (dump_file, *overlap_iterations_a, 0); + fprintf (dump_file, ")\n (overlap_iterations_b = "); + print_generic_expr (dump_file, *overlap_iterations_b, 0); + fprintf (dump_file, ")\n"); + } +} + + + +/* This section contains the affine functions dependences detector. */ + +/* Computes the conflicting iterations, and initialize DDR. */ + +static void +subscript_dependence_tester (struct data_dependence_relation *ddr) +{ + unsigned int i; + struct data_reference *dra = DDR_A (ddr); + struct data_reference *drb = DDR_B (ddr); + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "(subscript_dependence_tester \n"); + + for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++) + { + tree overlaps_a, overlaps_b; + struct subscript *subscript = DDR_SUBSCRIPT (ddr, i); + + analyze_overlapping_iterations (DR_ACCESS_FN (dra, i), + DR_ACCESS_FN (drb, i), + &overlaps_a, &overlaps_b); + + if (chrec_contains_undetermined (overlaps_a) + || chrec_contains_undetermined (overlaps_b)) + { + finalize_ddr_dependent (ddr, chrec_dont_know); + break; + } + + else if (overlaps_a == chrec_known + || overlaps_b == chrec_known) + { + finalize_ddr_dependent (ddr, chrec_known); + break; + } + + else + { + SUB_CONFLICTS_IN_A (subscript) = overlaps_a; + SUB_CONFLICTS_IN_B (subscript) = overlaps_b; + } + } + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, ")\n"); +} + +/* Compute the classic per loop distance vector. + + RES is the data dependence relation to build a vector from. + CLASSIC_DIST is the varray to place the vector in. + NB_LOOPS is the total number of loops we are considering. + FIRST_LOOP is the loop->num of the first loop. */ + +static void +build_classic_dist_vector (struct data_dependence_relation *res, + varray_type *classic_dist, + int nb_loops, unsigned int first_loop) +{ + unsigned i; + lambda_vector dist_v, init_v; + + dist_v = lambda_vector_new (nb_loops); + init_v = lambda_vector_new (nb_loops); + lambda_vector_clear (dist_v, nb_loops); + lambda_vector_clear (init_v, nb_loops); + + if (DDR_ARE_DEPENDENT (res) != NULL_TREE) + return; + + for (i = 0; i < DDR_NUM_SUBSCRIPTS (res); i++) + { + struct subscript *subscript = DDR_SUBSCRIPT (res, i); + + if (chrec_contains_undetermined (SUB_DISTANCE (subscript))) + return; + + if (TREE_CODE (SUB_CONFLICTS_IN_A (subscript)) == POLYNOMIAL_CHREC) + { + int dist; + int loop_nb; + loop_nb = CHREC_VARIABLE (SUB_CONFLICTS_IN_A (subscript)); + loop_nb -= first_loop; + /* If the loop number is still greater than the number of + loops we've been asked to analyze, or negative, + something is borked. */ + if (loop_nb < 0 || loop_nb >= nb_loops) + abort (); + dist = int_cst_value (SUB_DISTANCE (subscript)); + + /* This is the subscript coupling test. + | loop i = 0, N, 1 + | T[i+1][i] = ... + | ... = T[i][i] + | endloop + There is no dependence. */ + if (init_v[loop_nb] != 0 + && dist_v[loop_nb] != dist) + { + finalize_ddr_dependent (res, chrec_known); + return; + } + + dist_v[loop_nb] = dist; + init_v[loop_nb] = 1; + } + } + + /* There is a distance of 1 on all the outer loops: + + Example: there is a dependence of distance 1 on loop_1 for the array A. + | loop_1 + | A[5] = ... + | endloop + */ + { + struct loop *lca, *loop_a, *loop_b; + struct data_reference *a = DDR_A (res); + struct data_reference *b = DDR_B (res); + int lca_nb; + loop_a = loop_containing_stmt (DR_STMT (a)); + loop_b = loop_containing_stmt (DR_STMT (b)); + + /* Get the common ancestor loop. */ + lca = find_common_loop (loop_a, loop_b); + + lca_nb = lca->num; + lca_nb -= first_loop; + if (lca_nb < 0 || lca_nb >= nb_loops) + abort (); + /* For each outer loop where init_v is not set, the accesses are + in dependence of distance 1 in the loop. */ + if (lca != loop_a + && lca != loop_b + && init_v[lca_nb] == 0) + dist_v[lca_nb] = 1; + + lca = lca->outer; + + if (lca) + { + lca_nb = lca->num - first_loop; + while (lca->depth != 0) + { + if (lca_nb < 0 || lca_nb >= nb_loops) + abort (); + if (init_v[lca_nb] == 0) + dist_v[lca_nb] = 1; + lca = lca->outer; + lca_nb = lca->num - first_loop; + + } + } + } + + VARRAY_PUSH_GENERIC_PTR (*classic_dist, dist_v); +} + +/* Compute the classic per loop direction vector. + + RES is the data dependence relation to build a vector from. + CLASSIC_DIR is the varray to place the vector in. + NB_LOOPS is the total number of loops we are considering. + FIRST_LOOP is the loop->num of the first loop. */ + +static void +build_classic_dir_vector (struct data_dependence_relation *res, + varray_type *classic_dir, + int nb_loops, unsigned int first_loop) +{ + unsigned i; + lambda_vector dir_v, init_v; + + dir_v = lambda_vector_new (nb_loops); + init_v = lambda_vector_new (nb_loops); + lambda_vector_clear (dir_v, nb_loops); + lambda_vector_clear (init_v, nb_loops); + + if (DDR_ARE_DEPENDENT (res) != NULL_TREE) + return; + + for (i = 0; i < DDR_NUM_SUBSCRIPTS (res); i++) + { + struct subscript *subscript = DDR_SUBSCRIPT (res, i); + + if (TREE_CODE (SUB_CONFLICTS_IN_A (subscript)) == POLYNOMIAL_CHREC + && TREE_CODE (SUB_CONFLICTS_IN_B (subscript)) == POLYNOMIAL_CHREC) + { + int loop_nb; + + enum data_dependence_direction dir = dir_star; + loop_nb = CHREC_VARIABLE (SUB_CONFLICTS_IN_A (subscript)); + loop_nb -= first_loop; + + /* If the loop number is still greater than the number of + loops we've been asked to analyze, or negative, + something is borked. */ + if (loop_nb < 0 || loop_nb >= nb_loops) + abort (); + if (chrec_contains_undetermined (SUB_DISTANCE (subscript))) + { + + } + else + { + int dist = int_cst_value (SUB_DISTANCE (subscript)); + + if (dist == 0) + dir = dir_equal; + else if (dist > 0) + dir = dir_positive; + else if (dist < 0) + dir = dir_negative; + } + + /* This is the subscript coupling test. + | loop i = 0, N, 1 + | T[i+1][i] = ... + | ... = T[i][i] + | endloop + There is no dependence. */ + if (init_v[loop_nb] != 0 + && dir != dir_star + && (enum data_dependence_direction) dir_v[loop_nb] != dir + && (enum data_dependence_direction) dir_v[loop_nb] != dir_star) + { + finalize_ddr_dependent (res, chrec_known); + return; + } + + dir_v[loop_nb] = dir; + init_v[loop_nb] = 1; + } + } + + /* There is a distance of 1 on all the outer loops: + + Example: there is a dependence of distance 1 on loop_1 for the array A. + | loop_1 + | A[5] = ... + | endloop + */ + { + struct loop *lca, *loop_a, *loop_b; + struct data_reference *a = DDR_A (res); + struct data_reference *b = DDR_B (res); + int lca_nb; + loop_a = loop_containing_stmt (DR_STMT (a)); + loop_b = loop_containing_stmt (DR_STMT (b)); + + /* Get the common ancestor loop. */ + lca = find_common_loop (loop_a, loop_b); + lca_nb = lca->num - first_loop; + + if (lca_nb < 0 || lca_nb >= nb_loops) + abort (); + /* For each outer loop where init_v is not set, the accesses are + in dependence of distance 1 in the loop. */ + if (lca != loop_a + && lca != loop_b + && init_v[lca_nb] == 0) + dir_v[lca_nb] = dir_positive; + + lca = lca->outer; + if (lca) + { + lca_nb = lca->num - first_loop; + while (lca->depth != 0) + { + if (lca_nb < 0 || lca_nb >= nb_loops) + abort (); + if (init_v[lca_nb] == 0) + dir_v[lca_nb] = dir_positive; + lca = lca->outer; + lca_nb = lca->num - first_loop; + + } + } + } + + VARRAY_PUSH_GENERIC_PTR (*classic_dir, dir_v); +} + +/* Returns true when all the access functions of A are affine or + constant. */ + +static bool +access_functions_are_affine_or_constant_p (struct data_reference *a) +{ + unsigned int i; + varray_type fns = DR_ACCESS_FNS (a); + + for (i = 0; i < VARRAY_ACTIVE_SIZE (fns); i++) + if (!evolution_function_is_constant_p (VARRAY_TREE (fns, i)) + && !evolution_function_is_affine_multivariate_p (VARRAY_TREE (fns, i))) + return false; + + return true; +} + +/* This computes the affine dependence relation between A and B. + 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. */ + +void +compute_affine_dependence (struct data_dependence_relation *ddr) +{ + struct data_reference *dra = DDR_A (ddr); + struct data_reference *drb = DDR_B (ddr); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "(compute_affine_dependence (%d, %d)\n", + DR_ID (dra), DR_ID (drb)); + fprintf (dump_file, " (stmt_a = \n"); + print_generic_expr (dump_file, DR_STMT (dra), 0); + fprintf (dump_file, ")\n (stmt_b = \n"); + print_generic_expr (dump_file, DR_STMT (drb), 0); + fprintf (dump_file, ")\n"); + } + + /* Analyze only when the dependence relation is not yet known. */ + if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE) + { + if (access_functions_are_affine_or_constant_p (dra) + && access_functions_are_affine_or_constant_p (drb)) + subscript_dependence_tester (ddr); + + /* As a last case, if the dependence cannot be determined, or if + the dependence is considered too difficult to determine, answer + "don't know". */ + else + finalize_ddr_dependent (ddr, chrec_dont_know); + } + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, ")\n"); +} + +/* Compute a subset of the data dependence relation graph. Don't + compute read-read relations, and avoid the computation of the + opposite relation, ie. when AB has been computed, don't compute BA. + DATAREFS contains a list of data references, and the result is set + in DEPENDENCE_RELATIONS. */ + +static void +compute_rw_wr_ww_dependences (varray_type datarefs, + varray_type *dependence_relations) +{ + unsigned int i, j, N; + + N = VARRAY_ACTIVE_SIZE (datarefs); + + for (i = 0; i < N; i++) + for (j = i; j < N; j++) + { + struct data_reference *a, *b; + struct data_dependence_relation *ddr; + + a = VARRAY_GENERIC_PTR (datarefs, i); + b = VARRAY_GENERIC_PTR (datarefs, j); + + /* Don't compute the "read-read" relations. */ + if (DR_IS_READ (a) && DR_IS_READ (b)) + continue; + + ddr = initialize_data_dependence_relation (a, b); + + VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr); + compute_affine_dependence (ddr); + compute_distance_vector (ddr); + } +} + +/* 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. + + FIXME: This is a "dumb" walker over all the trees in the loop body. + Find another technique that avoids this costly walk. This is + acceptable for the moment, since this function is used only for + debugging purposes. */ + +static tree +find_data_references_in_loop (struct loop *loop, varray_type *datarefs) +{ + basic_block bb; + block_stmt_iterator bsi; + + FOR_EACH_BB (bb) + { + if (!flow_bb_inside_loop_p (loop, bb)) + continue; + + for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) + { + tree stmt = bsi_stmt (bsi); + stmt_ann_t ann = stmt_ann (stmt); + + if (TREE_CODE (stmt) != MODIFY_EXPR) + continue; + + if (!VUSE_OPS (ann) + && !V_MUST_DEF_OPS (ann) + && !V_MAY_DEF_OPS (ann)) + continue; + + /* In the GIMPLE representation, a modify expression + contains a single load or store to memory. */ + if (TREE_CODE (TREE_OPERAND (stmt, 0)) == ARRAY_REF) + VARRAY_PUSH_GENERIC_PTR + (*datarefs, analyze_array (stmt, TREE_OPERAND (stmt, 0), + false)); + + else if (TREE_CODE (TREE_OPERAND (stmt, 1)) == ARRAY_REF) + VARRAY_PUSH_GENERIC_PTR + (*datarefs, analyze_array (stmt, TREE_OPERAND (stmt, 1), + true)); + + else + return chrec_dont_know; + } + } + + return NULL_TREE; +} + + + +/* This section contains all the entry points. */ + +/* Given a loop nest LOOP, the following vectors are returned: + *DATAREFS is initialized to all the array elements contained in this loop, + *DEPENDENCE_RELATIONS contains the relations between the data references, + *CLASSIC_DIST contains the set of distance vectors, + *CLASSIC_DIR contains the set of direction vectors. */ + +void +compute_data_dependences_for_loop (unsigned nb_loops, + struct loop *loop, + varray_type *datarefs, + varray_type *dependence_relations, + varray_type *classic_dist, + varray_type *classic_dir) +{ + unsigned int i; + + /* If one of the data references is not computable, give up without + spending time to compute other dependences. */ + if (find_data_references_in_loop (loop, datarefs) == chrec_dont_know) + { + struct data_dependence_relation *ddr; + + /* Insert a single relation into dependence_relations: + chrec_dont_know. */ + ddr = initialize_data_dependence_relation (NULL, NULL); + VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr); + build_classic_dist_vector (ddr, classic_dist, nb_loops, loop->num); + build_classic_dir_vector (ddr, classic_dir, nb_loops, loop->num); + return; + } + + compute_rw_wr_ww_dependences (*datarefs, dependence_relations); + + for (i = 0; i < VARRAY_ACTIVE_SIZE (*dependence_relations); i++) + { + struct data_dependence_relation *ddr; + ddr = VARRAY_GENERIC_PTR (*dependence_relations, i); + build_classic_dist_vector (ddr, classic_dist, nb_loops, loop->num); + build_classic_dir_vector (ddr, classic_dir, nb_loops, loop->num); + } +} + +/* Entry point (for testing only). Analyze all the data references + and the dependence relations. + + The data references are computed first. + + A relation on these nodes is represented by a complete graph. Some + of the relations could be of no interest, thus the relations can be + computed on demand. + + In the following function we compute all the relations. This is + just a first implementation that is here for: + - for showing how to ask for the dependence relations, + - for the debugging the whole dependence graph, + - for the dejagnu testcases and maintenance. + + It is possible to ask only for a part of the graph, avoiding to + compute the whole dependence graph. The computed dependences are + stored in a knowledge base (KB) such that later queries don't + recompute the same information. The implementation of this KB is + transparent to the optimizer, and thus the KB can be changed with a + more efficient implementation, or the KB could be disabled. */ + +void +analyze_all_data_dependences (struct loops *loops) +{ + unsigned int i; + varray_type datarefs; + varray_type dependence_relations; + varray_type classic_dist, classic_dir; + int nb_data_refs = 10; + + VARRAY_GENERIC_PTR_INIT (classic_dist, 10, "classic_dist"); + VARRAY_GENERIC_PTR_INIT (classic_dir, 10, "classic_dir"); + VARRAY_GENERIC_PTR_INIT (datarefs, nb_data_refs, "datarefs"); + VARRAY_GENERIC_PTR_INIT (dependence_relations, + nb_data_refs * nb_data_refs, + "dependence_relations"); + + /* Compute DDs on the whole function. */ + compute_data_dependences_for_loop (loops->num, loops->parray[0], + &datarefs, &dependence_relations, + &classic_dist, &classic_dir); + + if (dump_file) + { + dump_data_dependence_relations (dump_file, dependence_relations); + fprintf (dump_file, "\n\n"); + } + + /* Don't dump distances in order to avoid to update the + testsuite. */ + if (dump_file && (dump_flags & TDF_DETAILS)) + { + for (i = 0; i < VARRAY_ACTIVE_SIZE (classic_dist); i++) + { + fprintf (dump_file, "DISTANCE_V ("); + print_lambda_vector (dump_file, + VARRAY_GENERIC_PTR (classic_dist, i), + loops->num); + fprintf (dump_file, ")\n"); + } + for (i = 0; i < VARRAY_ACTIVE_SIZE (classic_dir); i++) + { + fprintf (dump_file, "DIRECTION_V ("); + print_lambda_vector (dump_file, + VARRAY_GENERIC_PTR (classic_dir, i), + loops->num); + fprintf (dump_file, ")\n"); + } + fprintf (dump_file, "\n\n"); + } + + if (dump_file && (dump_flags & TDF_STATS)) + { + unsigned nb_top_relations = 0; + unsigned nb_bot_relations = 0; + unsigned nb_basename_differ = 0; + unsigned nb_chrec_relations = 0; + + for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++) + { + struct data_dependence_relation *ddr; + ddr = VARRAY_GENERIC_PTR (dependence_relations, i); + + if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr))) + nb_top_relations++; + + else if (DDR_ARE_DEPENDENT (ddr) == chrec_known) + { + struct data_reference *a = DDR_A (ddr); + struct data_reference *b = DDR_B (ddr); + + if (DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b) + || array_base_name_differ_p (a, b)) + nb_basename_differ++; + else + nb_bot_relations++; + } + + else + nb_chrec_relations++; + } + + fprintf (dump_file, "\n(\n"); + fprintf (dump_file, "%d\tnb_top_relations\n", nb_top_relations); + fprintf (dump_file, "%d\tnb_bot_relations\n", nb_bot_relations); + fprintf (dump_file, "%d\tnb_basename_differ\n", nb_basename_differ); + fprintf (dump_file, "%d\tnb_distance_relations\n", (int) VARRAY_ACTIVE_SIZE (classic_dist)); + fprintf (dump_file, "%d\tnb_chrec_relations\n", nb_chrec_relations); + fprintf (dump_file, "\n)\n"); + + gather_stats_on_scev_database (); + } + + varray_clear (dependence_relations); + varray_clear (datarefs); + varray_clear (classic_dist); + varray_clear (classic_dir); +} + + diff --git a/gcc/tree-data-ref.h b/gcc/tree-data-ref.h new file mode 100644 index 00000000000..a31b0af32c3 --- /dev/null +++ b/gcc/tree-data-ref.h @@ -0,0 +1,188 @@ +/* Data references and dependences detectors. + Copyright (C) 2003, 2004 Free Software Foundation, Inc. + Contributed by Sebastian Pop + +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 2, 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 COPYING. If not, write to the Free +Software Foundation, 59 Temple Place - Suite 330, Boston, MA +02111-1307, USA. */ + +#ifndef GCC_TREE_DATA_REF_H +#define GCC_TREE_DATA_REF_H + +struct data_reference GTY(()) +{ + /* An identifier. */ + unsigned int id; + + /* A pointer to the statement that contains this DR. */ + tree stmt; + + /* A pointer to the ARRAY_REF node. */ + tree ref; + + /* The name of the array. */ + tree base_name; + + /* A list of chrecs. */ + varray_type access_fns; + + /* Auxiliary info specific to a pass. */ + int aux; + + /* True when the data reference is in RHS of a stmt. */ + bool is_read; + +}; + +#define DR_ID(DR) DR->id +#define DR_STMT(DR) DR->stmt +#define DR_REF(DR) DR->ref +#define DR_BASE_NAME(DR) DR->base_name +#define DR_ACCESS_FNS(DR) DR->access_fns +#define DR_ACCESS_FN(DR, I) VARRAY_TREE (DR_ACCESS_FNS (DR), I) +#define DR_NUM_DIMENSIONS(DR) VARRAY_ACTIVE_SIZE (DR_ACCESS_FNS (DR)) +#define DR_IS_READ(DR) DR->is_read + +enum data_dependence_direction { + dir_positive, + dir_negative, + dir_equal, + dir_positive_or_negative, + dir_positive_or_equal, + dir_negative_or_equal, + dir_star, + dir_independent +}; + +/* What is a 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). These three subscripts + are stored in the data_dependence_relation structure under the form + of an array of subscripts. */ + +struct subscript GTY(()) +{ + /* A description of the iterations for which the elements are + accessed twice. */ + tree conflicting_iterations_in_a; + tree conflicting_iterations_in_b; + + /* These fields store the information about the iteration domain + validity of the dependence relation. */ + tree last_conflict_in_a; + tree last_conflict_in_b; + + /* Distance from the iteration that access a conflicting element in + A to the iteration that access this same conflicting element in + B. The distance is a tree scalar expression, ie. a constant or a + symbolic expression, but certainly not a chrec function. */ + tree distance; + + /* Direction (or sign) of the distance. This more abstract (less + precise) information is extracted from the distance field, for + the convenience of some analyzers. */ + enum data_dependence_direction direction; +}; + +#define SUB_CONFLICTS_IN_A(SUB) SUB->conflicting_iterations_in_a +#define SUB_CONFLICTS_IN_B(SUB) SUB->conflicting_iterations_in_b +#define SUB_LAST_CONFLICT_IN_A(SUB) SUB->last_conflict_in_a +#define SUB_LAST_CONFLICT_IN_B(SUB) SUB->last_conflict_in_b +#define SUB_DISTANCE(SUB) SUB->distance +#define SUB_DIRECTION(SUB) SUB->direction + +/* A data_dependence_relation represents a relation between two + data_references A and B. */ + +struct data_dependence_relation GTY(()) +{ + + struct data_reference *a; + struct data_reference *b; + + /* A "yes/no/maybe" field for the dependence relation: + + - when "ARE_DEPENDENT == NULL_TREE", there exist a dependence + relation between A and B, and the description of this relation + is given in the SUBSCRIPTS array, + + - when "ARE_DEPENDENT == chrec_known", there is no dependence and + SUBSCRIPTS is empty, + + - when "ARE_DEPENDENT == chrec_dont_know", there may be a dependence, + but the analyzer cannot be more specific. */ + tree are_dependent; + + /* For each subscript in the dependence test, there is an element in + this array. This is the attribute that labels the edge A->B of + the data_dependence_relation. */ + varray_type subscripts; +}; + +#define DDR_A(DDR) DDR->a +#define DDR_B(DDR) DDR->b +#define DDR_ARE_DEPENDENT(DDR) DDR->are_dependent +#define DDR_SUBSCRIPTS(DDR) DDR->subscripts +#define DDR_SUBSCRIPTS_VECTOR_INIT(DDR, N) \ + VARRAY_GENERIC_PTR_INIT (DDR_SUBSCRIPTS (DDR), N, "subscripts_vector"); +#define DDR_SUBSCRIPT(DDR, I) VARRAY_GENERIC_PTR (DDR_SUBSCRIPTS (DDR), I) +#define DDR_NUM_SUBSCRIPTS(DDR) VARRAY_ACTIVE_SIZE (DDR_SUBSCRIPTS (DDR)) + + + +struct data_dependence_relation *initialize_data_dependence_relation +(struct data_reference *, struct data_reference *); +void compute_affine_dependence (struct data_dependence_relation *); +extern void analyze_all_data_dependences (struct loops *); +extern void compute_data_dependences_for_loop (unsigned, struct loop *, + varray_type *, varray_type *, + varray_type *, varray_type *); +extern struct data_reference * init_data_ref (tree, tree, tree, tree); +extern struct data_reference *analyze_array (tree, tree, bool); + +extern void dump_data_reference (FILE *, struct data_reference *); +extern void dump_data_references (FILE *, varray_type); +extern void dump_data_dependence_relation (FILE *, + struct data_dependence_relation *); +extern void dump_data_dependence_relations (FILE *, varray_type); +extern void dump_data_dependence_direction (FILE *, + enum data_dependence_direction); + + + +/* Inline functions. */ + +/* This is the simplest data dependence test: determines whether the + data references A and B access the same array. */ + +static inline bool +array_base_name_differ_p (struct data_reference *a, + struct data_reference *b) +{ + if (DR_BASE_NAME (a) == DR_BASE_NAME (b)) + return false; + + if (TREE_CODE (DR_BASE_NAME (a)) == INDIRECT_REF + && TREE_CODE (DR_BASE_NAME (b)) == INDIRECT_REF + && TREE_OPERAND (DR_BASE_NAME (a), 0) + == TREE_OPERAND (DR_BASE_NAME (b), 0)) + return false; + + return true; +} + +#endif /* GCC_TREE_DATA_REF_H */ diff --git a/gcc/tree.c b/gcc/tree.c index 30ddcc895a5..09a96330463 100644 --- a/gcc/tree.c +++ b/gcc/tree.c @@ -5737,5 +5737,66 @@ find_compatible_field (tree record, tree orig_field) return orig_field; } +/* Return value of a constant X. */ + +HOST_WIDE_INT +int_cst_value (tree x) +{ + unsigned bits = TYPE_PRECISION (TREE_TYPE (x)); + unsigned HOST_WIDE_INT val = TREE_INT_CST_LOW (x); + bool negative = ((val >> (bits - 1)) & 1) != 0; + + if (bits > HOST_BITS_PER_WIDE_INT) + abort (); + + if (negative) + val |= (~(unsigned HOST_WIDE_INT) 0) << (bits - 1) << 1; + else + val &= ~((~(unsigned HOST_WIDE_INT) 0) << (bits - 1) << 1); + + return val; +} + +/* Returns the greatest common divisor of A and B, which must be + INTEGER_CSTs. */ + +tree +tree_fold_gcd (tree a, tree b) +{ + tree a_mod_b; + tree type = TREE_TYPE (a); + +#if defined ENABLE_CHECKING + if (TREE_CODE (a) != INTEGER_CST + || TREE_CODE (b) != INTEGER_CST) + abort (); +#endif + + if (integer_zerop (a)) + return b; + + if (integer_zerop (b)) + return a; + + if (tree_int_cst_sgn (a) == -1) + a = fold (build (MULT_EXPR, type, a, + convert (type, integer_minus_one_node))); + + if (tree_int_cst_sgn (b) == -1) + b = fold (build (MULT_EXPR, type, b, + convert (type, integer_minus_one_node))); + + while (1) + { + a_mod_b = fold (build (CEIL_MOD_EXPR, type, a, b)); + + if (!TREE_INT_CST_LOW (a_mod_b) + && !TREE_INT_CST_HIGH (a_mod_b)) + return b; + + a = b; + b = a_mod_b; + } +} #include "gt-tree.h" diff --git a/gcc/tree.h b/gcc/tree.h index 13f97ce6779..d364434f3be 100644 --- a/gcc/tree.h +++ b/gcc/tree.h @@ -3480,6 +3480,8 @@ extern void build_common_tree_nodes (int); extern void build_common_tree_nodes_2 (int); extern tree build_nonstandard_integer_type (unsigned HOST_WIDE_INT, int); extern tree build_range_type (tree, tree, tree); +extern HOST_WIDE_INT int_cst_value (tree); +extern tree tree_fold_gcd (tree, tree); extern bool fields_compatible_p (tree, tree); extern tree find_compatible_field (tree, tree); -- 2.30.2